目標(biāo)規(guī)劃圖解法標(biāo)規(guī)劃單純形法

第二節(jié)目標(biāo)規(guī)劃問題的圖解法

minZ=d-100X1+80X2-d++d-=100004X1+2X2

4002X1+4X2

500X1,

X2,

d-,

d+0

d+.d-=0例11X2X1O50100501001252X1+4X2=5004X1+2X2=400CEB絕對約束可行域OBEC2X2X1O50100501001252X1+4X2=500100X1+80X2=100004X1+2X2=400CEBd+目標(biāo)約束滿意域BEC3(1)絕對約束可行域OBEC(2)目標(biāo)約束滿意域BEC(3)多個可行滿意解：

(60,50),10000;(70,50),11000;E(50,100),13000。(4)Zmin=04例2minZ=P1d1++P2(d2-+d2+)+P3(d3-)2X1+X211X1

-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+05111057X2X1AB2X1+X2=11O可行域⊿OAB6111010557X2X1ABCDEFd2+d1-d3+X1+2X2=10X1-X2=08X1+10X2=562X1+X2=11O可行域⊿OAB目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段G7解：①可行域⊿OAB②目標(biāo)1：⊿OBC目標(biāo)2：ED線段目標(biāo)3：GD線段③用8X1+10X2=56X1+2X2=10求G=(2,4)利潤=568

X1-X2=0

X1+2X2=10D=(10/3,10/3)利潤=60解為X==

α+(1-α)(0α1)X1210/3

X2410/3④Zmin=09例3minZ=P1d1-+P2d2++P3(2d3-+d4-)X1+X2+d1--d1+=40①

X1

+X2+d2--d2+=50②X1+d3--d3+=24③X2+d4--d4+=30④10X230304050X1OBACDEFd3+d4+d1+d2-X1+X2=40X1+X2=50X2=30X1=24解：G11(1)、、滿足目目標(biāo)①、②的滿意意域為ABCD(2)、、先考慮慮③的滿滿意域為為ABEF再考慮④④，無公公共滿意意域。(3)、EX1+X2=50X1=24E(24,26)GX1+X2=50X2=30G(20,30)12(4)、、d4-=30-X2+d4+=30-26=4>0因為X2+d4--d4+=30所以d4-=30––X2+d4+ZE=P3d4-=P3(30-x2+d4+)=P3(30-26)=4P3而因為x1+d3--d3+=24ZG=P3*2d3-=P3*2(24-20)=8P3所以，取取E點13§6.3目標(biāo)標(biāo)規(guī)劃問問題的單單純形法法目標(biāo)規(guī)劃劃的數(shù)學(xué)學(xué)模型，，特別是是約束的的結(jié)構(gòu)與與線性規(guī)規(guī)劃模型型沒有本本質(zhì)的區(qū)區(qū)別，只只是它的的目標(biāo)不不止是一一個，雖雖然其利利用優(yōu)先先因子和和權(quán)系數(shù)數(shù)把目標(biāo)標(biāo)寫成一一個函數(shù)數(shù)的形式式，但在在計算中中無法按按單目標(biāo)標(biāo)處理，，所以可可用單純純形法進進行適當(dāng)當(dāng)改進后后求解。。在組織織、構(gòu)造造算法時時，我們們要考慮慮目標(biāo)規(guī)規(guī)劃的數(shù)數(shù)學(xué)模型型一些特特點，作作以下規(guī)規(guī)定：(1)因因為目目標(biāo)規(guī)劃劃問題的的目標(biāo)函函數(shù)都是是求最小小化，所所以檢驗驗數(shù)的最最優(yōu)準(zhǔn)則則與線性性規(guī)劃是是相反的的；一、目標(biāo)標(biāo)規(guī)劃問問題單純純形法的的特點14(2)因因為非非基變量量的檢驗驗數(shù)中含含有不同同等級的的優(yōu)先因因子，Pi>>Pi+1，i=1,2,,L-1.于是是從每個個檢驗數(shù)數(shù)的整體體來看：：Pi+1（i=1,2,,L-1）優(yōu)先級級第k個檢驗數(shù)數(shù)的正、、負(fù)首先先決定于于P1，P2，…，，Pi優(yōu)先級第第k個檢驗數(shù)數(shù)的正、、負(fù)。若若P1級第k個檢驗數(shù)數(shù)為0，，則此檢檢驗數(shù)的的正、負(fù)負(fù)取決于于P2級第k個檢驗數(shù)數(shù)；若P2級第k個檢驗數(shù)數(shù)仍為0，則此此檢驗數(shù)數(shù)的正、、負(fù)取決決于P3級第k個檢驗數(shù)數(shù)，依次次類推。。換一句句話說，，當(dāng)某Pi級第k個檢驗數(shù)數(shù)為負(fù)數(shù)數(shù)時，計計算中不不必再考考察Pj（j>i）級第k個檢驗數(shù)數(shù)的正、、負(fù)情況況；15（3）根根據(jù)（LGP））模型特特征，當(dāng)當(dāng)不含絕絕對約束束時，di-（i=1,2,…,K）構(gòu)成了了一組基基本可行行解。在在尋找單單純形法法初始可可行點時時，這個個特點是是很有用用。16二、目標(biāo)標(biāo)規(guī)劃問問題單純純形法的的計算步步驟(1)建建立初始始單純形形表．在在表中將將檢驗數(shù)數(shù)行按優(yōu)優(yōu)先因子子個數(shù)分分別列成成K行。。初始的的檢驗數(shù)數(shù)需根據(jù)據(jù)初始可可行解計計算出來來，方法法同基本本單純形形法。當(dāng)當(dāng)不含絕絕對約束束時，di-（i=1,2,……,K）構(gòu)成了了一組基基本可行行解，即即可得到到初始單單純形表表。17(2)確確定換入入變量：：按優(yōu)先先級順序序，檢查查檢驗數(shù)數(shù)是否存存在負(fù)值值，選取取優(yōu)先級級最高的的最小負(fù)負(fù)值對應(yīng)應(yīng)的變量量入基；；(3)按按單純形形法中的的最小比比值規(guī)則則確定換換出變量量，當(dāng)存存在兩個個和兩個個以上相相同的最最小比值值時，選選取具有有較高優(yōu)優(yōu)先級別別的變量量為換出出變量；；18(4)按按單純形形法進行行基變換換運算，，建立新新的單純純形表；；(5)迭迭代計算算停止判判別準(zhǔn)則則：如果各優(yōu)優(yōu)先級的的檢驗數(shù)數(shù)均為非非負(fù)；某一優(yōu)先先級有負(fù)負(fù)檢驗數(shù)數(shù)，但是是該負(fù)檢檢驗數(shù)對對應(yīng)的上上一級優(yōu)優(yōu)先級的的檢驗數(shù)數(shù)為正檢檢驗數(shù)。。19三、應(yīng)用用實例Min{P1(d1-+d2+),P2d3-}x1+d1--d1+=102x1+x2+d2--d2+=403x1+2x2+d3--d3+=100x1,x2,di-,di+≥020例Min{P1d1-,P2d2+,P3d3-}5x1+10x2≤60x1-2x2+d1--d1+=04x1+4x2+d2--d2+=366x1+8x2+d3--d3+=48x1,x2,di-,di+≥0+x3=6021000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000122000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000p1d1-01-201-100000d2-36440001-100p3d3-4868000001-1σp1-120010000p2000000100p3-6-8000000123000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000124000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3600201-5500000x101-201-100000d2-360120-441-100p3d3-480200-66001-1σp1000100000p2000000100p30-2006-6000125000p100p2p30CBXBbx1x2x3d1-d1+d2-d2+d3-d3+0x3120011-100-110x124/51002/5-0.4000.1-0.10d2-36/5000-2/50.41-1-0.60.60x212/5010-0.30.3000.05-0.05σp1000100000p2000000100p300000001026因有兩個個非基變變量的檢檢驗數(shù)為為0，所所以，有有無窮多多解。27例試用用單純形形法來求求解Minz=P1（d1++d2+)+P2d3++P3d4-+P4（d1-+2d2-)x1+d1--d1+=9x2+d2--d2+=84x1+6x2+d3--d3+=6012x1+18x2+d4--d4+=252x1,x2,di-,di+0,i=1,2,3,4.28解:由于P1,P2優(yōu)先級對對應(yīng)的目目標(biāo)函數(shù)