【正文】 推論 若（ LP）可行，那么（ LP） 無有限最優(yōu)解的充分必要條件是（ LD） 。 （ 1） 將模型統(tǒng)一為 “ max， ≤ ”或 “ min， ≥ ” 的形式 ， 對于其中的等式約束按下面 （ 2） 、 （ 3） 中的方法處理； 線性規(guī)劃的對偶 （ 2） 若原規(guī)劃的某個約束條件為等式約束 ， 則在對偶規(guī)劃中與此約束對應的那個變量取值沒有非負限制； （ 3） 若原規(guī)劃的某個變量的值沒有非負限制 ， 則在對偶問題中與此變量對應的那個約束為等式 。 線性規(guī)劃的對偶 非對稱形式 的對偶規(guī)劃 一般稱不具有對稱形式的一對線性規(guī)劃為非對稱形式的對偶規(guī)劃 。 (3)從數(shù)據(jù) b、 C的位置看：在兩個規(guī)劃模型中 ， b和 C的位置對換 。 線性規(guī)劃的對偶 (2)從約束系數(shù)矩陣看：一個模型中為 Ａ ， 則另一個模型中為 AT。 (1)若一個模型為目標求 “ 極大 ” ，約束為 “ 小于等于 ” 的不等式 ， 則它的對偶模型為目標求 “ 極小 ” ， 約束是“ 大于等于 ” 的不等式 。 求獲最大利潤的方案 。 線性規(guī)劃的對偶 線性規(guī)劃原問題 例 :某工廠擁有 A、 B、 C 三種類型的設備 ， 生產(chǎn)甲 、 乙兩種產(chǎn)品 。 ： 若 的設備都用于外協(xié)加工，工廠收取加工費。 單 純 形 法 例（ LP） Max z = 5x1 + 2x2 + 3x3 x4 . x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0 線性規(guī)劃的單純形法 Max z = 5x1+2x2+3x3x4Mx5Mx6 . x1+2x2+3x3+x5 =15 2x1+x2+5x3+x6 =20 x1+2x2+4x3+x4 =26 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ≥ 0 線性規(guī)劃的單純形法 5 2 3 1 M M CB XB x1 x2 x3 x4 x5 x6 θ i M x5 15 1 2 3 0 1 0 5 M x6 20 2 1 (5) 0 0 1 4 1 x4 26 1 2 4 1 0 0 6 .5 z 35 M +2 6 3 M +6 3 M +4 8 M +7 0 0 0 M x5 3 1 /5 (7/5 ) 0 0 1 3 /5 1 5 /7 3 x3 4 2 /5 1 /5 1 0 0 1 /5 20 1 x4 10 3 /5 6 /5 0 1 0 4 /5 25/ 3 z 3 M 2 M /5+1 6 /5 7 /5 M +1 3 /5 0 0 0 8 /5 M 7 /5 2 x2 1 5 /7 1 /7 1 0 0 5 /7 3 /7 3 x3 2 5 /7 (3/7 ) 0 1 0 1 /7 2 /7 2 5 /3 1 x4 5 2 /7 3 /7 0 0 1 6 /7 2 /7 z 5 3 /7 2 5 /7 0 0 0 M 1 3 /7 M 2 /7 2 x2 1 0 /3 0 1 1 /3 0 2 /3 1 /3 5 x1 2 5 /3 1 0 7 /3 0 1 /3 2 /3 1 x4 11 0 0 1 1 1 0 z 1 1 2 /3 0 0 2 5 /3 0 M 2 /3 M +8 /3 ?大 M法 （ LP M） ? 得到 最優(yōu)解 ： (25/3， 10/3， 0， 11)T ? 最優(yōu)目標值 ： 112/3 線性規(guī)劃的單純形法 第一階段問題（ LP 1） Max z = x5 x6 . x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 線性規(guī)劃的單純形法 0 0 0 0 1 1 CB XB x1 x2 x3 x4 x5 x6 θ i 1 x5 15 1 2 3 0 1 0 5 1 x6 20 2 1 (5) 0 0 1 4 0 x4 26 1 2 4 1 0 0 6 .5 z 35 3 3 8 0 0 0 1 x5 3 1 /5 (7/5 ) 0 0 1 3 /5 1 5 /7 0 x3 4 2 /5 1 /5 1 0 0 1 /5 20 0 x4 10 3 /5 6 /5 0 1 0 4 /5 2 5 /3 z 3 1 /5 7/ 5 0 0 0 8 /5 0 x2 1 5 /7 1 /7 1 0 0 5 /7 3 /7 0 x3 2 5 /7 3 /7 0 1 0 1 /7 2 /7 2 5 /3 0 x4 5 2 /7 3 /7 0 0 1 6 /7 2 /7 z 0 0 0 0 0 1 1 ?第一階段 (LP 1） ? 得到原問題的基本可行解 : (0， 15/7， 25/7， 52/7)T 線性規(guī)劃的單純形法 5 2 3 1 C B X B x 1 x 2 x 3 x 4 θi 2 x 2 1 5 /7 1 /7 1 0 0 3 x 3 2 5 /7 (3 /7 ) 0 1 0 2 5 /3 1 x 4 5 2 /7 3 /7 0 0 1 z 5 3 /7 2 5 /7 0 0 0 2 x 2 1 0 /3 0 1 1 /3 0 5 x 1 2 5 /3 1 0 7 /3 0 1 x 4 11 0 0 1 1 z 1 1 2 /3 0 0 2 5 /3 0 ?第二階段 把基本可行解填入表中 ? 得到原問題的最優(yōu)解 :(25/3， 10/3， 0， 11)T ?最優(yōu)目標值： 112/3 線性規(guī)劃的單純形法 線性規(guī)劃的對偶 對偶原理 對偶問題定義 —— 線性規(guī)劃問題寫出其對偶問題，要掌握在對稱形式和非對稱情況下由原問題寫出對偶問題的方法。否則，原問題無可行解。 xn+i = bi i =1 , … , m 是基本可行解 ,它對應的基 是單位矩陣。 結(jié)論： 若得到的最優(yōu)解滿足 xn+i = 0 i = 1 , … , m 則是原問題的最優(yōu)解；否則，原問題無可行解。 xn+i = bi i =1 , … , m 是基本可行解。 考慮一般問題： bi 0 i = 1 , … , m 線性規(guī)劃的單純形法 Max z = c1x1 + c2x2 + … + xn . a11x1+a12x2 +… +a1nxn = b1 a21x1+a22x2 +… +a2nxn = b2 . . . am1x1+am2x2+… +amnxn = bm x1 ， x2 ， … ， xn ≥ 0 線性規(guī)劃的單純形法 大 M法： 引入人工變量 xn+i ≥ 0 （ i = 1 , … , m）及充分大正數(shù) M 。 線性規(guī)劃的單純形法 一般情況的處理及注意事項的強調(diào)：主要是討論初始基本可行解不明顯時，常用的方法。 單純形法的基本思路是有選擇地取基本可行解 ， 即是從可行域的一個極點出發(fā) ， 沿著可行域的邊界移到另一個相鄰的極點 ， 要求新極點的目標函數(shù)值不比原目標函數(shù)值差 。 xn+i = bi i = 1 , … , m 是基本可行解 對應的基是單位矩陣。 用兩階段法求例 解 : 構造輔助線性規(guī)劃問題 min w =x6 + x7 x1－ 2x2 + x3 + x4 = 11 － 4x1 + x2 +2x3 － x5 + x6 = 3 － 2x1 + x3 +x7 = 1 x x x x x x x7≥0 利用單純形法求解該輔助線性規(guī)劃問題（極小化為標準形式）如表 1—13。 ?例：用單純形法（大 M法）求解 max z=3x1－ 2x2－ x3 x1 － 2x2 + x3 ≤ 11 － 4x1 + x2 +2x3 ≥ 3 － 2x1 x3 = 1 x x x3≥0 ?解：化為標準形式，并引入人工變量，構造如下模型： max z=3x1－ 2x2－ x3－ Mx6－ Mx7 x1－ 2x2 + x3 + x4 = 11 － 4x1 + x2 +2x3 － x5 + x6 = 3 － 2x1 x3 +x7 = 1 x x x3≥0 列表計算： Cj 3 1 1 0 0 M M b CB XB x1↓ x2↓ x3 x4 x5 x6 x7 0 x4 1 2 1 1 0 0 0 11 M x6 4 1 2 0 1 1 0 3 M x7 2 0 [1] 0 0 0 1 1 z 36M 1+M 1+3M 0 M 0 0 0 x4 3 2 0 1 0 0 1 10 M x6 0 [1] 0 0 1 1 2 1 1 x3 2 0 1 0 0 0 1 1 Z 1 1+M 0 0 M 0 3M+1 0 x4 [3] 0 0 1 2 2 5 12 1 x