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