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

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

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

用單純形法求解下面目標(biāo)規(guī)劃問(wèn)題:

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

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

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

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

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

級(jí)目標(biāo)已達(dá)最優(yōu)，應(yīng)轉(zhuǎn)入對(duì)Pi+1

級(jí)目標(biāo)的尋優(yōu)，直到i=k，計(jì)算結(jié)束。

1、建立初始單純形表。

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

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

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

3．基變換

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

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

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

000P1

P2

P2P3

00CBXBbx1x2

x3

001－11－100000P21012001－1000P3

5681000001－100

x3

11210000001σkjP1

0000100000P2

-10－1－20002000P3

-56－8－1000000104.3用單純形法求解目標(biāo)規(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用單純形法求解目標(biāo)規(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。但非基變量的檢驗(yàn)數(shù)為零，故此題有無(wú)窮多最優(yōu)解。θ=min｛4,24,－,6｝=4,故為換出變量。4.3用單純形法求解目標(biāo)規(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。則這兩個(gè)解得凸組合都是本例的滿意解。4.3用單純形法求解目標(biāo)規(guī)劃例:

用單純形法求解下述目標(biāo)規(guī)劃問(wèn)題：解:

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

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

其中目標(biāo)函數(shù)為總利潤(rùn)，x1,x2

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

1、要求總利潤(rùn)必須超過(guò)2500元；

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

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

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

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

-2500－30－1201000000P2

000000002.501P3

00000010000θ=min｛2500/30,140/2,60/1｝=60,故為換出變量。4.3用單純形法求解目標(biāo)規(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用單純形法求解目標(biāo)規(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用單純形法求解目標(biāo)規(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用單純形法求解目標(biāo)規(guī)劃Cj

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