第三節用單純形法求解目標規劃4.3用單純形法求解目標規劃本節內容的安排目標規劃單純形法的求解步驟例*題4.3用單純形法求解目標規劃目標規劃求解問題過程明確問題，列出(或修改)目標的優先級和權系數構造目標規劃的模型求出滿意解滿意否？分析各項目表完成情況據此制定出決策方案是否4.3用單純形法求解目標規劃

由目標規劃數學模型的標準型可看出，它實質上是最小化的線性規劃，所以可用單純形法求解．這時，我們應該把目標優先等級系數Pi（i=1,2,…,k）理解為一種特殊的正常數，且注意到各等級系數之間的關系：P1?P2?…?Pk．而檢驗數就是各優先因子P1,P2,…,Pk的線性組合。當所有檢驗數都滿足最優性條件（）時，從最終表上即可得出目標規劃的解．ci-zj=∑αkjPk,j=1,2,…,n;k=1,2,…,KPk是指不同數量的很大的數d-是松弛變量d+是剩余變量Pk>>MPk+1(M是任意大的正數）4.3用單純形法求解目標規劃例:

用單純形法求解下面目標規劃問題:

解：引入松馳變量x3,將它們化為標準型：4.3用單純形法求解目標規劃cj000P100P2P30CBXBbx1x2x30x3605101000000P10[1]-201-10000036440001-100P34868000001-1P1-120010000P2000000100P3-6-800000010x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-60001

單純形表14.3用單純形法求解目標規劃cj000P100P2P30CBXBbx1x2x30x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20P1000100000P2000000100P3000000010單純形表1全部檢驗數非負，計算結束。4.3用單純形法求解目標規劃2．最優性檢驗

目標規劃的最優性檢驗是分優先級進行的，從P1級開始依次到Pk級為止，具體檢驗Pi級目標時，可能有下述三種情況．

（1）若檢驗數矩陣的Pi

行系數均≥0，則Pi

級目標已達最優，應轉入對Pi+1

級目標的尋優，直到i=k，計算結束。

1、建立初始單純形表。

一般假定初始解在原點，即以約束條件中的所有負偏差變量或松弛變量為初始基變量，按目標優先等級從左至右分別計算出各列的檢驗數，填入表的下半部，得檢驗數矩陣。單純形法的計算步驟：4.3用單純形法求解目標規劃（2）若檢驗數矩陣的Pi中有負系數，且負系數所在列的前i-1行優先因子的系數全為0(例如-P2+223P3<0)

，可判定該檢驗數為負，則選該系數（若此類負系數有多個，則可選絕對值最大者）所在列對應的非基變量為入基變量，繼續進行基變換．

（3）若檢驗數矩陣的Pi行中有負系數，但負系數所在列的前i-1行優先因子的系數有0，也有正數，（例如P2-3P3>0），即整個檢驗數的值可判為正（因Pi-1?Pi），故也應轉入對Pi+1級目標的尋優，否則會使高優先級別的目標函數值劣化．4.3用單純形法求解目標規劃

3．基變換

①入基變量的確定：在Pk行，從那些上面沒有正檢驗數的負檢驗數中，選絕對值最大者，對應的變量xs就是進基變量。若Pk行中有幾個相同的絕對值最大者，則依次比較它們各列下部的檢驗數，取其絕對值最大的負檢驗數的所在列的xs為進基變量。假如仍無法確定，則選最左邊的變量（變量下標小者）為進基變量。4.3用單純形法求解目標規劃②出基變量的確定：按最小非負比值規則確定出基變量，當存在兩個或兩個以上相同的最小比值時，選取具有較高優先級別的變量為換出變量。③主元素的確定：出基變量與入基變量在系數矩陣中對應的交叉點上的元素即為主元素．④迭代變換：同線性規劃的單純形法．得到新的單純形表，獲得一組新解⑤對求得的解進行分析：若計算結果滿意，停止運算；若不滿意，需修改模型，即調整目標優先等級和權系數，或者改變目標值，重新進行第1步。4.3用單純形法求解目標規劃4．從表中找到基本可行解和相應于各優先級的目標函數值每個單純形表中常數列b，即為各基變量的相應取值．本題最后一個單純形表已為最優，它對應的基本可行解：x1=24/5,x2=12/5,x3=12,d2-=36/5，即為最優解．這與圖解法得到結果一致．

注意：在最優單純形表中非基變量d1+和d3+的檢驗數都是零，故知本題有多個最優解．如以d1+為入基變量繼續迭代，可得單純形表2，如以d3+為入基變量繼續迭代，可得單純形表3．4.3用單純形法求解目標規劃cj000P100P2P30CBXBbx1x2x30x3600201-5500000x101-201-100000360120-441-100P3480[20]0-66001-1P1000100000P2000000100P30-2006-600010x3120011-100-110x124/51002/5-2/5001/10-1/10036/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20P1000100000P2000000100P3000000010單純形表14.3用單純形法求解目標規劃cj000P100P2P30CBXBbx1x2x30x320010/310000

-5/65/60x181

4/3000001/6-1/6040

-4/30001-1

-2/32/30

8010/30-11001/6-1/6P1000100000P2000000100P3000000010表2續單純形表14.3用單純形法求解目標規劃cj000P100P2P30CBXBbx1x2x30

120011-100-110x16101/101/2-1/200000000-3/5-111-1000x23011/20-1/41/40000P1000100000P2000000100P3000000010表3續單純形表14.3用單純形法求解目標規劃例：用單純形法求解下列目標規劃問題4.3用單純形法求解目標規劃Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－1000000104.3用單純形法求解目標規劃Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

053/201－11/2-1/20000x251/21001/2-1/2000P3

63000-551－100

x3

63/2000-1/21/2001σkjP1

0000100000P2

0000011000P3

-6－30005-5010θ=min｛10/3,10,6/3,12/3｝=2,故為換出變量。4.3用單純形法求解目標規劃Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

02001－13-3-1/21/200x2401004/3-4/3-1/61/600x121000-5/35/31/3-1/300

x3

300002-2-1/21/21σkjP1

0000100000P2

0000011000P3

0000000100

最優解為x1＝2，x2＝4。但非基變量的檢驗數為零，故此題有無窮多最優解。θ=min｛4,24,－,6｝=4,故為換出變量。4.3用單純形法求解目標規劃Cj

000P1

P2

P2P3

00CBXBbx1x2

x3

04002-26-6-1100x210/301-1/31/31/3-1/30000x110/3102/3-2/31/3-1/30000

x3

100-1－1-11001σkjP1

0000100000P2

0000011000P3

000000100

最優解為x1＝10/3,，x2=10/3。則這兩個解得凸組合都是本例的滿意解。4.3用單純形法求解目標規劃例:

用單純形法求解下述目標規劃問題：解:

第一步：列出初始單純形表第二步：確定換入變量第三步：確定換出變量4.3用單純形法求解目標規劃第四步：用換入變量替換基變量中的換出變量4.3用單純形法求解目標規劃4.3用單純形法求解目標規劃

例、已知一個生產計劃的線性規劃模型為

其中目標函數為總利潤，x1,x2

為產品A、B產量。現有下列目標：

1、要求總利潤必須超過2500元；

2、考慮產品受市場影響，為避免積壓，A、B的生產量不超過60件和100件；

3、由于甲資源供應比較緊張，不要超過現有量140。試建立目標規劃模型，并用單純形法求解。4.3用單純形法求解目標規劃1、要求總利潤必須超過2500元；

2、考慮產品受市場影響，為避免積壓，A、B的生產量不超過60件和100件；

3、由于甲資源供應比較緊張，不要超過現有量140。4.3用單純形法求解目標規劃Cj00P100P302.5P20P2CBXBbx1x2P1250030121－1000000014021001－100000601000001－1000100010000001－1σkjP1

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。4.3用單純形法求解目標規劃Cj

00P100P302.5P20P2CBXBbx1x2P17000121－100－30300002001001－1－22000x1601000001－1000100010000001－1σkjP1

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。4.3用單純形法求解目標規劃Cj

00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1σkjP1

-400030115-150000P2

-250-5/400-5/45/45/2001P3

00000010000θ=min｛400/15,－,－,－｝=10,故為換出變量。4.3用單純形法求解目標規劃Cj

00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/300000000100010000001－1σkjP1

00010000000P2

-175/30-1-1/121/12002/5001P3

-80/301/5-1/151/15100000θ=min｛－,350/6,1250/6,100/1｝=75,故為換出變量。4.3用單純形法求解目標規劃Cj

00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000