【文章內(nèi)容簡(jiǎn)介】 30 x1 x2 O 10 20 30 40 10 20 30 40 50 50 0,05040221212121????????xxxxxxxx無(wú)可行解 即無(wú)最優(yōu)解 max Z=10x1+4x2 例 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 31 由以上例題可知，線性規(guī)劃的解有 4種形式 ： (例 ) (例 ) (例 ) (例 ) 2情形為有最優(yōu)解 4情形為無(wú)最優(yōu)解 圖解法 The Graphical Method 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 32 (1)可行解區(qū)域要畫(huà)正確 (2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò) (3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng) 作業(yè)：教材 P34 T7 圖解法 The Graphical Method 下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型 2/29/2023 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 34 在用單純法求解線性規(guī)劃問(wèn)題時(shí)，為了討論問(wèn)題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型為 : 1．目標(biāo)函數(shù)求最大值（或求最小值） 2．約束條件都為等式方程 3．變量 xj非負(fù) 4．常數(shù) bi非負(fù) 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 35 ?????????????????????????mibnjxbxaxaxabxaxaxabxaxaxaijmnmnmmnnnn,2,1,0,2,1,02211222222111212111????????????????max(或 min)Z=c1x1+c2x2+…+xn 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 注：本教材默認(rèn)目標(biāo)函數(shù)是 max 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 36 ???njjj xcZ1m axminjxbxajnjijij,2,1,2,1,01 ???????????????????0maxXbAXCXZ或?qū)懗上铝行问?： 或用矩陣形式 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 37 11 12 1 1 121 22 2 2 21212, , , )nnnm m m n n ma a a x ba a a x bA X b C c c ca a a x b? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?； ； ； ＝ (通常 X記為： 稱Ａ為約束方程的系數(shù)矩陣， m是約束方程的個(gè)數(shù)， n是決策變量的個(gè)數(shù)，一般情況 m≤n，且 r(Ａ )＝ m。 TnxxxX ), 21 ?＝（m a x0Z C XAX bX??????其中 : 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 38 【例 】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型 3213min xxxZ ????????????????????????無(wú)符號(hào)要求、32132132132100)3(523)2(3)1(82xxxxxxxxxxxx【解】（１）因?yàn)?x3無(wú)符號(hào)要求 ，即 x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令 0, 33333 ????????? xxxx 其中 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 39 (3)第二個(gè)約束條件是 ≥號(hào)，在 ≥號(hào) 左端減去剩余變量 (Surplus variable)x5， x5≥0。也稱松馳變量 321 3min xxxZ ????????????????????????無(wú)符號(hào)要求、 32132132132100)3(523)2(3)1(82xxxxxxxxxxxx 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP (2) 第一個(gè)約束條件是 ≤號(hào)，在 ≤左端加入松馳變量 (slack variable) x4，x4≥0,化為等式； (4)第三個(gè)約束條件是 ≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在 ≤左邊加入松馳變量 x6， x6≥0，同時(shí)兩邊乘以－ 1。 （ 5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令 Z′=－ Z,得到max Z′=－ Z，即當(dāng) Z達(dá)到最小值時(shí) Z′達(dá)到最大值，反之亦然。 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 40 綜合起來(lái)得到下列標(biāo)準(zhǔn)型 332133max xxxxZ ???????????????????????????????????????????05)(23382654321633215332143321xxxxxxxxxxxxxxxxxxxxxx、、 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 41 當(dāng)某個(gè)變量 xj≤0時(shí) ,令 x/j=－ xj 。 當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束 974 321 ??? xxx將其化為兩個(gè)不等式 ??????????974974321321xxxxxx再加入松馳變量化為等式。 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 42 【 例 】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型 ???????????無(wú)約束、 211212145||||maxxxxxxxxZ【 解】 此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。 令 ???????????????????????????????0000000000002222222211111111xxxxxxxxxxxxxxxx，，，－，，222222111111,||,||xxxxxxxxxxx???????????????????? 則有 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 43 得到線性規(guī)劃的標(biāo)準(zhǔn)形式 1 1 2 21 1 2 2 31 1 41 1 2 2 3 4m a x ( ) ( )540Z x x x xx x x x xx x xx x x x x x? ?? ? ??? ? ? ? ?? ?? ? ??? ? ? ? ???? ??? ? ??? ? ?? ? ?? ?? 、 、 、 、 、 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 對(duì)于 a≤x≤b(a、 b均大于零 )的有界變量化為標(biāo)準(zhǔn)形式有兩種方法，一種方法是增加兩個(gè)約束 x≥a及 x≤b，另一種方法是令 =x－ a，則 a≤x≤b等價(jià)于 0≤≤b－ a，增加一個(gè)約束 ≤b－ a并且將原問(wèn)題所有 x用 x=+a替換。 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 44 ？ 可以對(duì)照四條標(biāo)準(zhǔn)逐一判斷！ 標(biāo)準(zhǔn)形式是人為定義的，目標(biāo)函數(shù)可以是求最小值。 WinQSB軟件求解時(shí)，不必化成標(biāo)準(zhǔn)型。 圖解法時(shí)不必化為標(biāo)準(zhǔn)型。 。 作業(yè)：教材 P34 T 8 線性規(guī)劃的標(biāo)準(zhǔn)型 Standard form of LP 下一節(jié)：基本概念 2/29/2023 線性規(guī)劃的有關(guān)概念 Basic Concepts of LP 2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 46 設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型 max Z=CX （ ） AX=b （ ） X ≥0 （ ） 式中 A 是 m n矩陣 ， m≤n并且 r（ A） =m， 顯然 A中至少有一個(gè) m m子矩陣 B， 使得 r（ B） =m。 基本概念 Basic Concepts 基 (basis)A中 m m子矩陣 B并且有 r（ B） =m，則稱 B是線性規(guī)劃的一個(gè)基（或基矩陣 basis matrix ）。當(dāng) m=n時(shí)，基矩陣唯一，當(dāng) mn時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過(guò) mnC2/29/2023 制作與教學(xué) 線性規(guī)劃 Linear Programming Page 47 【例 】線性規(guī)劃 321 24max xxxZ ???????????????????5,1,0226103553214321?jxxxxxxxxxj 求所有基矩陣。 【解】約束方程的系數(shù)矩陣為 2 5矩陣 ?????????10261001115A,610 151 ????????B ,010 152 ????????B ,110 053 ????????B ????? 2614B ???????1009B ,12017 ?????? ,0218 ???????B ,16016 ??????? ,015 ???容易看出 r(A)=2， 2階子矩陣有 C52=10個(gè)，其中第 1列與第 3列構(gòu)成的 2階矩陣不是一個(gè)基，基矩陣只有 9個(gè)，即 基本概念