【正文】 束中 增加必要的人工變量 （如大 M方法一樣），以保證找到一個初始基本解。 29 兩階段法 大 M方法中懲罰值的使用，可能會導致大的求解誤差。 本例似乎取 M=100 24 基 x1 x2 x3 R1 R2 x4 解 z 4 1 0 100 100 0 0 R1 3 1 0 1 0 0 3 R2 4 3 1 0 1 0 6 x4 1 2 0 0 0 1 4 在進行單純形方法之前，需要將 z 行與表的其余部分保持一致！ 在表中， x1=x2=x3=0，初始基本解 (R1, R2, x4)=(3,6,4)，z=100*3+100*6=900（ 而不是 z行右端當前顯示的 0！ ），這種不一致是由于 R1, R2在目標函數(shù)中有非零系數(shù)（ 100, 100）造成的！（ 在所有松弛變量為初始解中， Z行的松弛變量系數(shù)為 0） 25 為此，在 z行選用適當?shù)募s束方程替換出 R1和 R2，注意到橙色部分，用 100乘以 R1和 R2行的每一行，求和之后加到 z行，替換出 R1和 R2, 即 基 x1 x2 x3 R1 R2 x4 解 z 4 1 0 100 100 0 0 R1 3 1 0 1 0 0 3 R2 4 3 1 0 1 0 6 x4 1 2 0 0 0 1 4 基 x1 x2 x3 R1 R2 x4 解 z 696 399 100 0 0 0 900 R1 3 1 0 1 0 0 3 R2 4 3 1 0 1 0 6 x4 1 2 0 0 0 1 4 X1為進基！ 最正系數(shù)！ 26 基 x1 x2 x3 R1 R2 x4 解 z 696 399 100 0 0 0 900 R1 3 1 0 1 0 0 3 R2 4 3 1 0 1 0 6 x4 1 2 0 0 0 1 4 基 x1 解 最小比 R1 3 3 3/3=1（最小值） R2 4 6 6/4= x4 1 4 4/1=4 可行性條件，選擇 R1為離基變量！ 27 基 x1 x2 x3 R1 R2 x4 解 z 0 167 100 232 0 0 204 x1 1 1/3 0 1/3 0 0 1 R2 0 5/3 1 4/3 1 0 2 x4 0 5/3 0 1/3 0 1 3 采用高斯 喬丹運算可以計算出如下 最后的單純形顯示 x2和 R2分別是進基變量與離基變量。 懲罰規(guī)則 已知 M為一個充分大的數(shù)，人工變量的目標系數(shù)表示為適當?shù)膽土P，如果 MM?????在 極 大 化 問 題 中人 工 變 量 的 目 標 系 數(shù)在 極 小 化 問 題 中22 Min z=4x1+x2 . 3x1+x2=3 4x1+3x2≥6 x1+2x2≤4 x1， x2≥0 Min z=4x1+x2 . 3x1+x2 =3 4x1+3x2x3 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4 ≥0 松弛變量 剩余變量 Min z=4x1+x2+MR1+MR2 . 3x1+x2 +R1 =3 4x1+3x2x3 + R2 =6 x1+2x2 + x4 =4 x1, x2 , x3, x4， R1， R2 ≥0 初始解 (R1, R2, x4)=(3,6,4) 23 M可以不采用代數(shù)運算的傳統(tǒng)，并用數(shù)值代替，以簡化表達 . M值應該多大？依賴于初始線性規(guī)劃的數(shù)據(jù)： ? M相對于初始目標系數(shù)必須充分大，使得 M能起到懲罰作用，迫使人工變量在最優(yōu)值為零。然后在目標函數(shù)中對他們指定非常大的懲罰，強迫人工變量在最優(yōu)解中等于零。 21 大 M方法 大 M方法以等式形式的線性規(guī)劃開始。轉(zhuǎn)到第 2步 20 單純形法的進一步拓展 ?所有約束是（ ≤）并且有非負右端的線性規(guī)劃方便地提供了全部為松弛變量的初始基本可行解。 第 3步 用可行性條件選擇離基變量。當非基變量的所有 Z行系數(shù)是非負的（非正的）時，迭代達到最優(yōu) 可行性條件 對于極大化（極小化）問題，離基變量都是具有最小非負比（帶有嚴格的正分母）的基變量，如有多個可任選其一 高斯 喬丹行運算 （ 1）樞軸行 a. 在基列中，用進基變量替換離基變量 b. 新的樞軸行 =當前樞軸行 247。 4/3； 2. 新的 Z行 =當前 Z行 (2/3) 新的 x2行； 3. 新的 x1行 =當前 x1行 (2/3) 新的 x2行； 4. 新的 s3行 =當前 s3行 (5/3) 新的 x2行； 5. 新的 s4行 =當前 s4行 (1) 新的 x2行； 16 這些計算產(chǎn)生新的單純形表為 基 Z x1 x2 s1 s2 s3 s4 解 Z 1 0 0 3/4 1/2 0 0 21 x1 0 1 0 1/4 1/2 0 0 3 x2 0 0 1 1/8 3/4 0 0 3/2 s3 0 0 0 3/8 5/4 1 0 5/2 s4 0 0 0 1/8 3/4 0 1 1/2 基于最優(yōu)性條件， Z行中相應于非基變量 s1和 s2的系數(shù)沒有一個是負的，因此最后的單純形表是最優(yōu)的 決策變量 最優(yōu)值 建議 x1 3 日生產(chǎn) 3 噸外墻涂料 x2 3/2 日生產(chǎn) 噸內(nèi)墻涂料 Z 21 利潤 17 資源 松弛變量的值 狀況 原料 M1 s1=0 匱乏 原料 M2 s2=0 匱乏 市場限制 s3=5/2 充裕 需求限制 s4=1/2 充裕 單純形的計算結果還給出了資源的使用情況： 如果松弛變量為零，表明資源全部用完，該資源是匱乏的 如果松弛變量為正，表明資源尚有余存，該資源是充裕的 18 單純形方法的總結 最優(yōu)性條件 在極大化（極小化）問題中，進基變量是 Z行中具有（最正）系數(shù)的非基變量。 樞軸元素 2. 其他所有行，包括 Z行 新的行 =當前行 當前樞軸列的系數(shù) 新的樞軸列 將該方法應用到上表 1. 在基列中，以 x1替換 s1 新的 x1行 =當前 s1行 247。 A→B，在 A處的非基變量 x2變成 B處的基變量，并且在 A處的基變量 s2變成在 A處的非基變量，稱 X2為進基變量， s2為離基變量，類似地，在點 B， x1進基， s1離基，因此到了 C點 7 Reddy Mikks公司使用 M1和 M2兩種原料生產(chǎn)內(nèi)、外墻涂料，其基本數(shù)據(jù)如下： 每噸產(chǎn)品使用原料噸數(shù) 日最大可用量（噸） 外墻涂料 內(nèi)墻涂料 原料 M1 6 4 24 原料 M1 1 2 6 每噸利潤（千美元） 5 4 市場調(diào)查表明，內(nèi)墻涂料日需求量不超過外墻涂料的日需求加上 1噸，內(nèi)墻涂料的最大日需求量是 2噸 定義 x1=外墻涂料的日生產(chǎn)噸數(shù)， x2=內(nèi)墻涂料的日生產(chǎn)噸數(shù) 8 完整的 Reddy Mikks模型是 Max Z=5x1+4x2 St 6x1+4x2≤24 （原料 M1） x1+2x2≤6 （ 原料 M1） x1+x2≤1 （市場限制） x2 ≤2 （需求限制） x1, x2≥0 9 單純形算法的計算細節(jié) 1 2 1 2 3 41 2 11 2 21 2 3241 2 1 2 3 4m a x 5 4 0 0 0 06 4 242612, , , , , 0z x x s s s sst x x sx x sx x sxsx x s s s s? ? ? ? ? ?? ? ?? ? ?? ? ? ????基 Z x1 x2 s1 s2 s3 s4 解 Z 1 5 4 0 0 0 0 0 Z 行 s1 0 6 4 1 0 0 0 24 s1 行 s2 0 1 2 0 1 0 0 6 s2 行 s3 0 1 1 0 0 1 0 1 s3 行 s4 0 0 1 0 0 0 1 2 s4 行 125 4 0z x x? ? ?初始解是最優(yōu)解嗎？ 目標函數(shù)表明可以增加 x1或 x2來改進這個解， 選擇具有最正的系數(shù)的變量 x1為進基變量 ，這個等價于將目標函數(shù)中最負系數(shù)的變量作為進基變量。因此單純形方法的路徑是沿著A→B→C。單純形方法每次要求增加一個變量，且選擇使得 Z有最大改善率的那個變量。而在很多實際的問題中，很多是有成百上千的變量和約束的問題。1 從圖形解到代數(shù)解的轉(zhuǎn)換 畫 出 所 有 約 束 ， 包 括 非 負 限 制解 空 間 由 無 窮 個 可 行 點 組 成識 別 解 空 間 的 可 行 角 點最 優(yōu) 解 的 候 選 點 為 有 限 個 角 點用 目 標 函 數(shù) 從 所 有 的 候 選 點 確 定 最 優(yōu) 角 點解 空 間 由 n 個 變 量 的 每 個 方 程 表示 ， 所 有 變 量 均 為 非 負方 程 組 有 無 窮 個 可 行 解確 定 方 程 的 基 本 可 行 解最 優(yōu) 解 由 有 限 個 基 本 可 行 解 給 出在 所 有 候 選 解 中 ， 用 目 標 函 數(shù) 確 定 最 優(yōu) 的基 本 可 行 解圖 解 法 代 數(shù) 法2 12121212m a x 2 32425,0z x xst x xxxxx???????2112212 1 212425, , , 0x x sx x sx x s s? ? ?? ? ??2x1xA B C D E F 1 0s ?最優(yōu)點 (1,2,0,0) 2 0s ?方程組有 m=2個方程和 n=4個變量。因此最大數(shù)目的角點為 4 ! / ( 2 ! 2 ! ) 6mnC ??解空間 到底令哪些點為零才能對應一個特定的角點？ (0， 0， 4， 5) (0， ， ， 0) (x1， x2， s1， s2) (2， 0， 0， 3) 3 非基（零）變量 基變量 基本解 相應的角點 可行否？ 目標值 Z （ x1, x2） （ s1, s2） (4, 5) A 是 0 （ x1, s1） （ x2, s2） (4, 3) F 否 （ x1, s2） （ x2, s1） (, ) B 是 （ x2, s1） （ x1, s2） (2, 3) D 是 4 （ x2, s2） （ x1, s1） (5, 6) E 否 （ s1, s2） （ x1, x2） (1, 2) C 是 8（最優(yōu)點） 可以看到，當問題的大小增加后（即 m與 n變大），枚舉所有角點的過程包含巨量的計算，如 m=10和 n=20，必須求解 184756個 10 10階的方程。 2x1xABCD EF10s ?最優(yōu)點（ x1=1 ， x2=2 ）20s ?， ）4 單純形方法 單純形方法的迭代本質(zhì) 2x1xA B C D E F 1 0s ?最優(yōu)點（ x1=1， x2=2） 2 0s ?12m ax 2 3z x x??正常情況下，單純形從原點（ A點）開始，此時 Z=0，能否在當前零值的基礎上，通過增加非基變量 x1和 x2來增加 Z值？ 圖形顯示，增加 x1和 x2將增加 Z。因此選擇增加 x2具有最大改善率，因此增加 x2直到角點 B，在點 B，再增加 X1的值，達到改進的角點 C，他是最優(yōu)點。 沿著路徑的每個角點與一步迭代是對應的，單純形方法是沿著解空間的邊緣移動，不能抄近路，直接A→C 5 2x1xA B C D E F 1 0s ?最優(yōu)點 (1,2,0,0) 2 0s ?(0， ， ， 0) (2， 0， 0， 3) x1 x2 s1 s2 A 0 0 4 5 B 0 0 C 1 2 0 0 D 2 0 0 3 (0， 0， 4， 5) 單純形方法的本質(zhì)就是換基！ 6 相應的角點 基變量 非基（零）變量 A （ s1, s2） （ x1, x2） B （ x2, s1） （ x1, s2） C （ x1, x2） （ s1, s2） 可以看到，在基變量和非基變量中的變化模式隨著解沿著路徑 A→B→C的移動而改變。