4.3 用單純形法求解目標規(guī)劃課件

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

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

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

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

單純形表14.3用單純形法求解目標規(guī)劃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全部檢驗數(shù)非負，計算結束。4.3用單純形法求解目標規(guī)劃2．最優(yōu)性檢驗

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

（1）若檢驗數(shù)矩陣的Pi

行系數(shù)均≥0，則Pi

級目標已達最優(yōu)，應轉入對Pi+1

級目標的尋優(yōu)，直到i=k，計算結束。

1、建立初始單純形表。

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

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

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

3．基變換

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

注意：在最優(yōu)單純形表中非基變量d1+和d3+的檢驗數(shù)都是零，故知本題有多個最優(yōu)解．如以d1+為入基變量繼續(xù)迭代，可得單純形表2，如以d3+為入基變量繼續(xù)迭代，可得單純形表3．4.3用單純形法求解目標規(guī)劃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用單純形法求解目標規(guī)劃cj000P100P2P30CBXBbx1x2x30x320010/310000

-5/65/60x181

4/3000001/6-1/6040

-4/30001-1

-2/32/30

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

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

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－1000000104.3用單純形法求解目標規(guī)劃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用單純形法求解目標規(guī)劃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

最優(yōu)解為x1＝2，x2＝4。但非基變量的檢驗數(shù)為零，故此題有無窮多最優(yōu)解。θ=min｛4,24,－,6｝=4,故為換出變量。4.3用單純形法求解目標規(guī)劃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

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

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

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

例、已知一個生產(chǎn)計劃的線性規(guī)劃模型為

其中目標函數(shù)為總利潤，x1,x2

為產(chǎn)品A、B產(chǎn)量。現(xiàn)有下列目標：

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

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

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

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

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

-2500－30－1201000000P2

000000002.501P3

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

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

－7000－12010030－3000P2

000000002.501P3

00000010000θ=min｛700/30,20/2,－,－｝=10,故為換出變量。4.3用單純形法求解目標規(guī)劃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用單純形法求解目標規(guī)劃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用單純形法求解目標規(guī)劃Cj

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