最優(yōu)化方法-線性規(guī)劃

1、線線性性規(guī)規(guī)劃劃模模型型.1標準型標準型. 2解解的的概概念念和和性性質質. 4單單純純形形算算法法. 5圖解法圖解法. 3線線性性規(guī)規(guī)劃劃模模型型一一.生生產產計計劃劃問問題題例例1利利潤潤最最大大？生生產產計計劃劃，才才能能使使所所獲獲安安排排千千元元。問問：該該廠廠應應如如何何、單單位位產產品品的的利利潤潤為為、同同，如如下下表表。耗耗費費的的加加工工時時間間各各不不相相產產品品所所需需材材料料的的數(shù)數(shù)量量和和三三種種產產品品，它它們們的的單單位位、生生產產某某工工廠廠利利用用某某種種原原材材料料754CBACBA產品產品資源資源原材料原材料工時工時ABC資源總量資源總量215 . 12

2、32100150解：解：確確定定目目標標函函數(shù)數(shù). 2確確定定決決策策變變量量.1。、的的產產量量分分別別為為、設設321xxxCBA，則則設設總總利利潤潤為為 S321754xxxS 確確定定約約束束條條件件. 310035 . 12321 xxx3 , 2 , 1,015022321 ixxxxi數(shù)數(shù)學學模模型型.4321754minxxxS 3 , 2 , 1, 01502210035 . 12.321321ixxxxxxxtsi線線性性規(guī)規(guī)劃劃模模型型：一一組組決決策策變變量量；)1(一一個個線線性性目目標標函函數(shù)數(shù)；)2(一一組組線線性性的的約約束束條條件件。)3(的的一一般般形形式

3、式：線線性性規(guī)規(guī)劃劃模模型型)(LP niiixc1(max)min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0),(),(),(),(.22112222212111212111標標準準型型二二.標標準準型型.1 niiixc1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111標標準準型型可可記記為為。則則線線性性規(guī)規(guī)劃劃記記nmijTnTmTnaAxxxxbbbbcccc )(,),(, 0),(,),(212121xcTmin 0.xbAxts化化標標準準型型.

4、2目目標標函函數(shù)數(shù)：)1(xcTmax:目標函數(shù)目標函數(shù)原問題原問題xcT min約約束束條條件件：)2(ininiibxaxaxai 2211)(：原問題條件原問題條件 02211iniinniniixbxxaxaxa稱稱為為松松弛弛變變量量。inx ininiibxaxaxaii 2211)(：原問題條件原問題條件 02211iniinniniixbxxaxaxa稱稱為為剩剩余余變變量量。inx 。無無非非負負約約束束，則則令令：原原問問題題 0,)(iiiiiivuvuxxiii為為標標準準型型。將將下下述述線線性性規(guī)規(guī)劃劃模模型型化化例例14321332maxxxxx 無約束無約束24

5、3143214214321,0,6347223332.xxxxxxxxxxxxxxxts解解：則則令令,222vux 432213332minxxvux 0,634472223332.22754317432214221543221vuxxxxxxxxvuxxvuxxxxvuxts圖解法圖解法三三.求求解解線線性性規(guī)規(guī)劃劃例例 2 0,5242.34max21212121xxxxxxtsxxz解：解：。畫畫出出可可行行解解的的范范圍圍)1(1x2xoABC求求極極值值點點。利利用用等等值值線線平平移移的的方方法法)2(表表示示一一族族等等值值平平行行線線。為為參參數(shù)數(shù)，則則方方程程以以zxxz

6、21344221 xx5221 xx。頂點頂點極大值點為極大值點為B。中中的的目目標標函函數(shù)數(shù)改改為為將將例例例例21223xxz 1x2xoABC4221 xx5221 xx解：解：。分分析析同同例例 2。等值線：等值線：zxx 212任任一一點點。上上的的極極大大值值點點為為線線段段 AB1x2xoABC221 xx221 xx解：解：。分分析析同同例例 2。等值線：等值線：zxx 2134求求解解線線性性規(guī)規(guī)劃劃例例 4 0,22.34max21212121xxxxxxtsxxz不不存存在在最最大大值值。原原問問題題無無界界。結結果果：線性規(guī)劃問題的解線性規(guī)劃問題的解 無無最最優(yōu)優(yōu)解解有

7、有最最優(yōu)優(yōu)解解 有有無無窮窮多多最最優(yōu)優(yōu)解解在在頂頂點點取取到到唯唯一一最最優(yōu)優(yōu)解解 可可行行域域為為空空集集解解無無界界質質線線性性規(guī)規(guī)劃劃解解的的概概念念和和性性四四.線線性性規(guī)規(guī)劃劃解解的的概概念念. 1)(LPxczT min 0.xbAxts)1()2()3(的的可可行行解解。稱稱為為）式式的的解解）、（滿滿足足（可可行行解解：)(),(3221LPxxxxTn 。可行域：可行域：0,| xbAxxD定理定理是是凸凸集集。線線性性規(guī)規(guī)劃劃問問題題的的可可行行域域 D證明：證明：。任取任取10,21 Dxx2121)1()1(AxAxxxA bbb )1( 是凸集。是凸集。即。即所以所

8、以DDxx 21)1( 的一個頂點。的一個頂點。為為則稱則稱，使使。及及，。如果不存在。如果不存在為凸集，為凸集，設設頂點：頂點：SxxxxSxxSxS2121)1(10 x1x2x一一個個基基。問問題題或或的的為為退退化化子子陣陣，則則稱稱階階的的非非中中為為若若。秩秩為為的的系系數(shù)數(shù)矩矩陣陣為為設設基基)(,:LPABmmABmnmA 非非基基變變量量。的的變變量量稱稱為為為為基基變變量量，不不是是基基變變量量對對應應的的變變量量為為基基向向量量，稱稱稱稱設設基基),1(),1(, ),(21mkxPmkPPPPBkkkmiiiiii 為為基基變變量量。為為基基，則則取取列列向向量量線線性

9、性無無關關，則則可可的的前前不不妨妨設設，已已知知mmnmxxPPPBmAmAr,),()(121 bAx 因為因為即即bxPxPxPxPnnmmmm 111所以所以nnmmmmxPxPbxPxP 111解得解得令非基變量令非基變量,01 nmxxbBxxTm11),( 的的基基本本解解。為為對對應應于于基基稱稱解解變變量量的的取取值值得得基基，令令非非基基變變量量取取零零，求求取取定定線線性性規(guī)規(guī)劃劃問問題題的的基基基基本本解解：BbBbBBT)0,(,11 解解。的的基基本本解解稱稱為為基基本本可可行行條條件件基基本本可可行行解解：滿滿足足非非負負問問題題給給定定例例)(LP 0,2222

10、842.22min4321432143214321xxxxxxxxxxxxtsxxxxz和一個基本可行解。和一個基本可行解。求此問題的一個基本解求此問題的一個基本解解：解：。系數(shù)矩陣系數(shù)矩陣 12224121A得得，則則令令非非基基變變量量取取,0222143 xxB 222822121xxxx 3731021xx可可行行解解。是是基基本本解解，但但不不是是基基本本Tx)0,0,37,310(1 得得，則則令令非非基基變變量量取取,0124132 xxB 22844141xxxx 91491641xx是是基基本本可可行行解解。Tx)914,0,0,916(2 可行解可行解基基本本解解基基本本可

11、可行行解解mnC 基本解數(shù)量基本解數(shù)量定定存存在在最最優(yōu)優(yōu)解解？是是否否在在基基本本可可行行解解中中一一退化退化：是非退化的。是非退化的。非退化的，稱非退化的，稱的所有基本解都是的所有基本解都是。如果。如果否則稱非退化的基本解否則稱非退化的基本解解；解；的基本解為退化的基本的基本解為退化的基本稱非零分量個數(shù)小于稱非零分量個數(shù)小于)()(LPLPm線線性性規(guī)規(guī)劃劃解解的的性性質質. 2的的頂頂點點?？煽尚行杏蛴蚴鞘浅涑浞址直乇匾獥l條件件是是是是基基本本可可行行解解的的的的解解線線性性規(guī)規(guī)劃劃問問題題定定理理DxxLP)(4線性無關。線性無關。的列向量的列向量對應的對應的的非零分量的非零分量解的

12、充要條件是解的充要條件是是基本是基本的一個解，則的一個解，則是是設設定理定理rriiiiiiTnpppAxxxxxbAxxxxx,),(1212121 可可行行解解?；颈救缛绻杏锌煽尚行薪饨猓瑒t則必必有有線線性性規(guī)規(guī)劃劃問問題題定定理理)(2LP的的基基本本可可行行解解。最最優(yōu)優(yōu)如如果果有有最最優(yōu)優(yōu)解解，則則必必有有線線性性規(guī)規(guī)劃劃問問題題定定理理)(3LP單單純純形形算算法法五五.判判斷斷出出不不存存在在最最優(yōu)優(yōu)解解。直直到到找找到到最最優(yōu)優(yōu)解解，或或者者基基本本可可行行解解，則則轉轉換換到到另另一一個個更更好好的的是是則則算算法法結結束束。不不是是，。，判判斷斷其其是是否否為為最最

13、優(yōu)優(yōu)解解從從一一個個基基本本可可行行解解開開始始算算法法思思路路：. 1問問題題：行行解解？如如何何得得到到第第一一個個基基本本可可)1(最最優(yōu)優(yōu)解解的的判判定定法法則則？)2(解解？變變換換到到另另一一個個基基本本可可行行如如何何從從一一個個基基本本可可行行解解)3()(1LP求求解解線線性性規(guī)規(guī)劃劃問問題題例例 0,5242.34min432142132121xxxxxxxxxxtsxxZ解解：。系數(shù)矩陣系數(shù)矩陣 10120121A。和和非非基基變變量量為為和和則則基基變變量量為為令令基基2143,1001xxxxB 2142132524xxxxxx代代入入目目標標函函數(shù)數(shù)得得21340

14、xxz 單單純純形形算算法法分分析析.2 54,04321xxxx則則令令。目目標標函函數(shù)數(shù)值值?；颈究煽尚行薪饨?)5,4,0,0(11 zxT是是否否為為最最優(yōu)優(yōu)解解？利利用用目目標標函函數(shù)數(shù)分分析析。21340 xxz 小小。則則目目標標函函數(shù)數(shù)值值就就可可以以減減取取值值可可以以增增大大為為正正數(shù)數(shù)，的的和和的的系系數(shù)數(shù)為為負負數(shù)數(shù)，因因此此若若和和目目標標函函數(shù)數(shù)中中非非基基變變量量2121xxxx 2142132524xxxxxx是是否否可可以以增增大大？不不變變，考考察察固固定定12xx 1413254xxxx 254001143xxxx251 x變?yōu)榉腔兞俊Ｗ優(yōu)榉腔兞俊?/p>

15、變?yōu)榛兞?，變?yōu)榛兞?，。即。即時，時，且且4141025xxxx 421423212125212323xxxxxx 2142132524xxxxxx42210 xxz 2325,03142xxxx則則令令。目目標標函函數(shù)數(shù)值值。基基本本可可行行解解10)0,23,0,25(22 zxT42210 xxz ，則則。固固定定增增大大的的系系數(shù)數(shù)為為負負，考考察察能能否否因因為為422xxx 421423212125212323xxxxxx 212321252323xxxx12 x變變?yōu)闉榉欠腔冏兞苛俊Ｗ冏優(yōu)闉榛冏兞苛?，。即即時時，且且323201xxxx 4314323231231321

16、xxxxxx43353211xxz 12,02143xxxx則則令令。目目標標函函數(shù)數(shù)值值。基基本本可可行行解解11)0,0,1,2(33 zxT減減小小，所所以以最最優(yōu)優(yōu)解解為為所所以以目目標標函函數(shù)數(shù)值值不不能能再再的的系系數(shù)數(shù)皆皆為為正正數(shù)數(shù)，和和其其中中因因為為目目標標函函數(shù)數(shù)4343,353211xxxxz 。最最優(yōu)優(yōu)的的目目標標函函數(shù)數(shù)值值為為，11*)0,0,1,2(*33 zzxxT最最優(yōu)優(yōu)性性條條件件)1()(LPxczT min0,. xbAxtsNBx非非基基變變量量指指標標集集基基變變量量指指標標集集,:,:1bAbxBB . 0: Nx.:1NBNAAA ,NNBxA

17、bx NTNNNTBTBxcxAcbcz min. 0, 0 NBxxs.ts.t. . bcTBNNTBTNxAcc)( ,1AAccBTBTT 定義定義稱為基本可行解 的檢驗數(shù)。x是是最最優(yōu)優(yōu)解解。，則則數(shù)數(shù)若若相相應應的的檢檢驗驗的的一一個個基基本本可可行行解解對對應應于于基基若若定定理理*0,*xBx 基基變變換換)2(對對應應的的變變量量，即即若若可可選選取取最最小小的的入入基基變變量量：j 為入基變量。為入基變量。對應的對應的也可任選也可任選為入基變量。為入基變量。則選取則選取jjeejjjxx0,0|min 注意到：注意到：0)2(;, 0)1(1 bANeBe eeBBBxpA

18、bAx11 考慮考慮，若若0)(1 eBpAa ，最最優(yōu)優(yōu)值值為為能能任任意意增增加加，問問題題無無界界ex exb 否則，否則，)( 0)( :)()(min111eBieBiBpApAbA 0, oxBo將將會會有有達達到到最最小小的的下下標標使使 優(yōu)優(yōu)解解。性性規(guī)規(guī)劃劃問問題題有有無無窮窮多多最最，則則線線，且且存存在在，有有任任意意的的果果對對的的一一個個基基本本可可行行解解。如如是是對對應應于于基基設設定定理理)(00*NkNjBxkj 。則則原原線線性性規(guī)規(guī)劃劃問問題題無無界界，且且，使使得得果果存存在在的的一一個個基基本本可可行行解解。如如是是對對應應于于基基設設定定理理00*1

19、 jBjpANjBx 單單純純形形表表和和單單純純形形算算法法. 3,11NNBBBxAAbAx NNBTBTNBTBxAAccbAcz)(min11 . 0, 0 NBxxs.ts.t. .可以用如下表格表示：可以用如下表格表示：AAccBTBT1 bAcBT1 BAAB1 bAB1 單單純純形形算算法法步步驟驟：建建立立初初始始單單純純形形表表。確確定定初初始始基基本本可可行行解解，）（1）。，算算法法結結束束；否否則則轉轉（基基本本可可行行解解就就是是最最優(yōu)優(yōu)解解則則當當前前的的，數(shù)數(shù)。如如果果檢檢驗驗各各非非基基變變量量的的檢檢驗驗）（3)(02Njj ）。（界界，算算法法結結束束；否

20、否則則轉轉則則線線性性規(guī)規(guī)劃劃問問題題的的解解無無，的的系系數(shù)數(shù)列列向向量量使使得得其其對對應應的的變變量量）如如果果存存在在（4003 kkkPx 為為入入基基變變量量。計計算算選選取取設設eejx,)0min()4( oeoieieiabaab 0|min ）。為為出出基基變變量量。轉轉（選選取取5ex的的列列。其其它它元元素素為為，個個系系數(shù)數(shù)列列向向量量變變換換為為變變換換將將第第為為主主元元旋旋轉轉。即即利利用用行行）以以（015 oeoeaea)(2LP求求解解線線性性規(guī)規(guī)劃劃問問題題例例 0,82463.2min321321321321xxxxxxxxxtsxxxZ解：解：化化標

21、標準準型型： 0,82463.2max5432153214321321xxxxxxxxxxxxxtsxxxZ初初始始基基本本可可行行解解的的計計算算. 4人工變量法人工變量法)(a)(LP niiixcz1min0. xbAxts規(guī)劃問題規(guī)劃問題個人工變量，得新線性個人工變量，得新線性對每個約束條件增加一對每個約束條件增加一) (LPuewT min0,0. uxbuAxts)(AxbeuewTT ：目目標標函函數(shù)數(shù)是是不不可可行行誤誤差差 niiixcz1min0. xbAxts)(LP) (LPuewT min0,0. uxbuAxts則則）有最優(yōu)解（有最優(yōu)解（若若,) (*uxLP0,)

22、(* wuxLP）充充要要條條件件有有可可行行解解（不含基變量不含基變量0, 0)1(* uw但但有有人人工工變變量量是是基基變變量量,0)2(* w.Bin 即即有有njaaji, 1,0)(, inxi 因因此此也也去去掉掉了了人人工工變變量量個個約約束束冗冗余余，可可去去掉掉，則則第第0)(, jiajb使使得得變變成成出出基基變變量量。而而為為中中心心做做轉轉軸軸運運算算，從從則則可可以以injixa , 0,312.2min212212121xxxxxxxtsxxZ)(3LP求求解解線線性性規(guī)規(guī)劃劃問問題題例例)(. 4兩兩階階段段法法初初始始基基本本可可行行解解的的計計算算法法大大

23、Mb)()(LP niiixcz1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111規(guī)劃問題規(guī)劃問題個人工變量，得新線性個人工變量，得新線性對每個約束條件增加一對每個約束條件增加一) (LP nimiiMuMuxcz11min mnixbuxaxaxabuxaxaxabuxaxaxatsimmnmnmmnnnn,2,1,0.2211222222121111212111 niiixcz1min0. xbAxts)(LP) (LPuMexcwTT min0,0. uxbuAxts則則）有最優(yōu)解（有最優(yōu)解（若若,)

24、 (*uxLP最優(yōu)解最優(yōu)解是是則則最優(yōu)解最優(yōu)解是是)(,)()0 ,)(1(*LPxPLx 無可行解無可行解則則最優(yōu)解且最優(yōu)解且是是)(, 0)(),)(2(*LPuPLux 則則無有限最優(yōu)解無有限最優(yōu)解若若,) (LP無有限最優(yōu)解無有限最優(yōu)解則則且且若若)(, 0, 00)1(*LPupkk 無可行解無可行解則則且且若若)(, 0, 00)2(*LPupkk )(4LP求求解解線線性性規(guī)規(guī)劃劃問問題題例例 0,24422.232min32132321321xxxxxxxxtsxxxZ改改進進單單純純形形算算法法. 5減少算法的計算量減少算法的計算量主要目的主要目的:.,eo進進基基變變量量為為若若選選定定出出基基變變量量為為.)1()1(,的的表表上上進進行行其其計計算算量量是是在在一一個個變變換換為為中中心心做做則則相相當當于于以以 nmJordanGaussaoeAAccBTBT1 bAcBT1 BAAB1 bAB1 回顧有初始基本可行解的單純形算法回顧有初始基本可行解的單純形算法, ,對于標準對于標準: :單純形表為單純形表為: :N,j , 數(shù)數(shù)計計算算過過程程需需要要計計算算檢檢驗驗 、系數(shù)矩陣系數(shù)矩陣AAAccBTBT1 bAcBT1 BAAB1 bAB1 、基本解基本解Bx