第四章線性規(guī)劃的求解法當(dāng)線性規(guī)劃的變量和約束條件比較多，而初始基本可行解又不知道時，是不容易用嘗試的方法得到初始基本可行解的，何況有可能基本可行解根本就不存在。在此時，大M法可能是應(yīng)付此類情況的一個行之有效的算法。§4.1大M法的原理當(dāng)初始基本可行解不知道時，則1.，2.兩個特點不能兼得，即下列兩條件不能兼得：中心部位具有單位子塊；右列元素非負(fù)；這時可以先用容許的運算使由列為非負(fù)，然后在中心部位人為添加一個單位子塊。如下例所述例4.1minz=一3x+x+2x1 2 3s.t.4.1.1)3x+2x一3x=6s.t.4.1.1)123一x+2x一x=一41 2 3x,x,x>01233 2-36-13 2-36-12-1-4-3 1 20列成表格：32-3632-3106>1-214>1-21014=>=>-3120-3120上述第三張表中人工增加了兩個變量x,x，稱為人工變量，即把原來的約束條件改為：45s.t. 3x+2x一3x+x=61 2 3 4x一2x+x+x=4 (4.1.2)1 2 3 5x,x,x,x,x>012345式(4.1)和(4.2)的約束方程組并不同解，但(4.1)的解和(4.2)中x=x=0的解45是相對應(yīng)的。只要找到以(4.2)為約束條件，且人工變量x,x均為自由變量的基本可行45解，也就找到了(4.1)的基本可行解，于是，要設(shè)法迫使x=x=0。45以上途徑通過修改(4.1)的目標(biāo)函數(shù)來實現(xiàn)。具體修改為：

minz=-3x+x+2x+Mx+Mx (4.1.3)1 2 3 4 5其中M為足夠大的正數(shù)，然后以(4.2)為約束條件，求(4.3)的最小值。只要x,x不為45零，就一定為正數(shù)，于是目標(biāo)函數(shù)的值就會增加它們和的M倍。由于M為足夠大的正數(shù)，所以只要原問題有基本可行解，就不會在x,x取正值時達(dá)到最小值。本例中把表改為：453 2-31061-21014-3 1 2 M M0通過運算使它具備第三個特點：底行相應(yīng)于單位子塊位置的元素為0，然后再嚴(yán)格按照單純形法的步驟求解：③2-31061-21014-3-4M*12+2M0010M由于M為足夠大的正數(shù)，所以-3-4M應(yīng)視為負(fù)數(shù)，故選它。經(jīng)過一次迭代：12/3-11/3020-8/3②-1/312083+一M-1-2M*41+一M0 6-2M33再經(jīng)過一次迭代：1-2/301/30 30-4/31-1/31/2105/305一+M-+M 762這時表已經(jīng)具備四個特點，且人工變量x,x亦已成為自由變量，所以從表上可直接讀45出(4.1)的最優(yōu)解：x=3,x=0,x=1，且x=x=0。把引進(jìn)的自由變量略去，則最12345優(yōu)解為x*=(3,0,1)T，最優(yōu)值為z*=-7。§4.2兩階段法的原理使用單純形方法，需要給定一個初始基本可行解，以便從這個基本可行解出發(fā)，求改進(jìn)的基本可行解，最終達(dá)到最優(yōu)解。下面介紹如何求出一個初始基本可行解，設(shè)標(biāo)準(zhǔn)形式的線性規(guī)劃問題

4.2.1)minz=cTx4.2.1)s.t.Ax=bx>0其中A是mxn矩陣，b>0。若A中含有m階單位矩陣，則初始基本可行解立即可得。比如：A=[i,N]=[B,N]，那么m就是一個基本可行解。若A中不包含m階單位矩陣，則可從兩階段法入手，先求得個初始基本可行解。先引入人工變量的概念。設(shè)A中不包含m階單位矩陣，為了使約束方程的系數(shù)矩陣中含有m階單位矩陣，把每一個方程增加一個非負(fù)變量，令4.2.2)Ax+x=b4.2.2)ax>0,x>0a即(A,I)(A,I)mx>0,=bxax>0

a4.2.3)顯然x-0—xba是（4.2.3）的一個基本可行解。當(dāng)然式子（4.2.3）已經(jīng)不是原來的約束，構(gòu)造（4.2.3）式的意義在于，若從（4.2.3）式的已知的基本可行解出發(fā)，能夠求出一個使得x=0的基本可行解，那么也就可以得到a（4.2.1）式的一個基本可行解。向量x>0是人為引進(jìn)的，它的每個分量稱為人工變量。人工變量與前面介紹的松弛a變量是兩個不同的概念。松弛變量的作用是把不等式約束改寫為等式約束，改寫前后的兩個問題是等價的。松弛變量的取值能夠表達(dá)現(xiàn)行的可行點是在可行域的內(nèi)部還是在其邊界。也就是說，在此可行解處，原來的約束是嚴(yán)格不等式成立還是等式成立的區(qū)別。因此松弛變量是“合法”的變量。而人工變量的引進(jìn)，改變了原來的約束條件，從這個意義上講，它們是不合法”的變量。兩階段法的第一階段是用單純形法消去人工變量，即把人工變量都變換成非基變量求出原問題的一個基本可行解。minf=eTxas.t.Ax+x=b (4.2.4)ax>0,x>0a其中e=(1,1,...,1)t是分量全是1的m維列向量，x=(xx )t是人工變量構(gòu)成a n+1 n+m的m維列向量。由于x=0,x=b是線性規(guī)劃(4.2.4)的一個基本可行解，目標(biāo)函數(shù)在可a行域上有下界，因此問題(4.2.4)必存在最優(yōu)基本可行解。設(shè)最優(yōu)基本可行解是(xT,xT)T，這時有三種情況。a1、x工0，這時線性規(guī)劃(4.2.1)無可行解，因為如果線性規(guī)劃(4.2.1)存在可行a解x，貝I」xxx0a是線性規(guī)劃(4.2.4)的可行解，在這一點上，問題(4.2.4)的目標(biāo)函數(shù)的值f=0Ox+eTDO<eTxa這和eTx是目標(biāo)函數(shù)的最優(yōu)值矛盾。a2、x=0且x的分量都是非基變量，這時m個基變量都是原來的變量，又知:aaxxx0a是線性規(guī)劃(4.2.4)的基本可行解，因此，x=x是線性規(guī)劃(4.2.1)的一個基本可行解。3、x=0且x的某些分量都是非基變量，這時可以用主元消去法，使原來變量中的某aa些非基變量進(jìn)基，替換出基變量中的人工變量，再開始兩階段法的第二階段。應(yīng)當(dāng)指出，為替換出基變量中的人工變量而采用的主元消去法，并不要求遵守單純形法確定的離基進(jìn)基變量的規(guī)貝。兩階段法的第二階段，用單純形法求線性規(guī)劃(4.2.1)的最優(yōu)解，初始的基本可行解就是從第一階段所得到的基本可行解。例4.2用兩階段法求下列線性規(guī)劃問題的最優(yōu)解maxz=2x一x12s.t. x+x>212x一x>1 （4.2.5）12x<31x,x>012先引進(jìn)松弛變量x,x,x，把問題化為標(biāo)準(zhǔn)形式。由于標(biāo)準(zhǔn)形式中約束方程的系數(shù)矩345陣并不包含三階單位矩陣，因此還要引進(jìn)人工變量x,x。下面先求解第一階段的問題：67minx+x67s.t.x1+x一x+x6=223x一x一x+x=11247x+x=315x,x,x,x,x,x,x>01234567用表格形式表示：11-1001021-10-100111000100300000110為了滿足單純形法的第三個特點：底行相應(yīng)于單位子塊位置的元素為0，對上表做初等11-100102①-10-1001110001003-2*011000-3由單純形法（或主元消去法），得：0②-1101-111-10-10011010110-120-2*1-1002-1再進(jìn)行一次：01-1/21/201/2-1/21/210-1/2-1/201/21/23/2001/21/21-1/2-1/23/200000110變換，使x,x所對應(yīng)的底行單位子塊位置的元素為0。得：67

這時已經(jīng)滿足單純形法的全部條件，達(dá)到最優(yōu)解。在第一階段的最優(yōu)解中，人工變量x,x都是非基變量，這樣得到初始基本可行解為：(31—(31—,0,0,(22(x,x,x,x,x)=12345第一階段結(jié)束后，修改最后的單純形表，去掉人工變量x,x下面的列，然后開始第二67階段的迭代，即求目標(biāo)函數(shù)minf=-2x+x。1201-1/21/201/210-1/2-1/203/2001/21/213/2-210000同理，為了滿足單純形法的第三個特點：底行相應(yīng)于單位子塊位置的元素為0，對上表做初等變換，使x,x所對應(yīng)的底行單位子塊位置的元素為0。得：1201-1/2?01/210-1/2-1/203/2001/21/213/200-1/2-3/2*05/2上表已經(jīng)具備單純形法的三個特點，于是在底行中任選一個負(fù)元素，02-110111-10020-1①01103-2*004再進(jìn)行一次迭代，得：0101121000130-11011010026上表已滿足單純形法的四個特點，從而得到線性規(guī)劃(4.2.5)的最優(yōu)解(x,x)=(3,0),12目標(biāo)函數(shù)的最優(yōu)值f=6。max§4.3靈敏度分析通過一個案例來理解靈敏度的問題。

例4.3設(shè)某廠在資源甲、乙的限制下，考慮制定能使總利潤達(dá)到最大的三種產(chǎn)品A、B、C的生產(chǎn)計劃，其有關(guān)數(shù)據(jù)如下：maxz=3x+x+4x1 2 3s.t. 6x+3x+5x<451 2 3 （4.3.1）3x+4x+5x<30

123x,x,x>0123化為標(biāo)準(zhǔn)形式：minf=一3x一x一4x1 2 3s.t. 6x+3x+5x+x=451234 （4.3.2）3x+4x+5x+x=301 2 3 5x,x,x,x,x>012345其中x,x分別是關(guān)于資源甲、乙而引進(jìn)的松弛變量，列成表格:4 5 _ _ - 小 ，一4563 5104534 50130-3-1 -4000用單純形法經(jīng)過兩次迭代即可終止，得1-1/3 01/3-1/35011-1/52/530201/53/527讀出的最優(yōu)解為:x=5,x=0,x=1233,x=0,4x=0，標(biāo)準(zhǔn)形的最優(yōu)值為f=-27，即原問題5的最大利潤為z=27。最優(yōu)解為x*=（5,0,3）T，即產(chǎn)品A生產(chǎn)5噸，產(chǎn)品B生產(chǎn)0噸，產(chǎn)品C生產(chǎn)3噸，這時的綜合利潤最大，為27千元。在此基礎(chǔ)上進(jìn)一步考慮一些問題，例如1、兩種資源中哪種資源的擁有量是制約利潤進(jìn)一步提高的因素？以x=5,x=0,x=3代入（4.4）約束:123s.t. 6x+3x+5x<45（資源甲的約束）1233x+4x+5x<30（資源乙的約束）123我們發(fā)現(xiàn)，約束條件中的不等式全部變成了等式，這說明在此生產(chǎn)計劃下的兩種資源均已用盡，故兩種資源的擁有量均是制約利潤進(jìn)一步提高的因素。關(guān)于最后的解是否使得不等式變成等式，可以簡單地以相應(yīng)的松弛變量是否取值為0加以判斷。在本例中，x=x=045說明兩個約束都達(dá)到了極限，都成為制約利潤進(jìn)一步提高的因素。2、 若在市場上能按比正常價貴0.5千元的單價買到資源甲、乙，問為了進(jìn)一步提高利潤是否應(yīng)買？我們從最后的一張表中可以看出原問題等價于在原有的約束條件下求：1 3maxz=-2x一x一x2 54 55注意到其中x,x分別表示資源甲、乙的數(shù)量，由此可以看出在最優(yōu)生產(chǎn)計劃的水平下，45資源甲的數(shù)量每變化一個單位對總利潤z的影響是1/5千元，相應(yīng)的資源乙的數(shù)量每變化一個單位對總利潤z的影響是3/5千元，在經(jīng)濟(jì)學(xué)上分別稱1/5千元、3/5千元為資源甲、乙的影子價格。對于目前所提的問題，由于單位利潤是在正常價格下計算的，所以若在市場上按高于正常價格購買資源甲、乙，則凈利潤就要在總利潤中減去高出的部分。資源甲在當(dāng)前的計劃生產(chǎn)水平下，每投入1噸甲資源對總利潤的貢獻(xiàn)為1/5=0.2千元，而購買成本要高出0.5千元，因此不合算；同樣的理由，每投入1噸乙資源對總利潤的貢獻(xiàn)為3/5=0.6千元，扣除高出的0.5千元的成本，還有0.1千元的利潤可賺，因此資源甲不應(yīng)購買、資源乙可以買。3、 若通過提高售價來提高B產(chǎn)品的單位利潤，問B產(chǎn)品的單位利潤要提高多少千元，才能仍在追求最大利潤的目標(biāo)下考慮生產(chǎn)B產(chǎn)品?解：設(shè)B產(chǎn)品的單位利潤要增加C千元才考慮生產(chǎn)B產(chǎn)品。則（4.5）式改為:4530-3 —(1+C) -4 0 0 "o"在底行的第二個系數(shù)上增加-C，經(jīng)過兩次迭代，得:1-1/301/3-1/35011-1/52/5302-C01/53/527

可以這樣分析，底行中若C<2,則上表已經(jīng)具有四個特點，運算終止，最優(yōu)解不變，x仍2為0只有當(dāng)C>2，上表不具備第四個特點，需要繼續(xù)運算，才能讓x作基變量，即x的22取值才可以不為0所以本問題的回答是C>2。123s.t.123s.t.2x一x+x>81232x+3x+2x<201234x一x=823x>j0,j1,2,3解：列成表格：2-11822 322020 4-18=>03 5703習(xí)題4.1用大M法計算以下線性規(guī)劃minf=3x+5x+7x（習(xí)題4.1）-11-1083 2 0 1204-1008=>5 7 0 002-11-102 3 2 0 12-11-102 3 2 0 10 4-10020835700MM~0~上述第一張表中，先引進(jìn)一個剩余變量x，一個松弛變量x，將問題化為標(biāo)準(zhǔn)型，變45成第二張表，其形式為：minf=3x+5x+7x123s.t. 2x一x+x一x=8TOC\o"1-5"\h\z1 2 3 42x+3x+2x+x=20 （習(xí)題4.2）1 2 3 54x一x =823x>0,j=1,2,3,4,5j松弛變量x可以作為初始基本變量，但是第二張表中沒有單位子陣，因而人工再增加5兩個變量x,x，稱為人工變量，即把原問題改為：67

minf=3x+5x+7x+Mx+Mx1 2 3 67s.t. 2x一x+x一x +x=81 2 3 4 62x+3x+2x +x=20（習(xí)題4.3）1 2 3 54x一x+x=8237x>0,j=1,2,3,4,5,6,7j式（習(xí)題4.1）和（習(xí)題4.3）的約束方程組并不同解，但（習(xí)題4.1）的解和（習(xí)題4.3）中x=x=x=x=0的解是相對應(yīng)的。只要找到以（習(xí)題4.3）為約束條件，且人工變4567量x,x,x,x均為自由變量的基本可行解，也就找到了（習(xí)題4.3）的基本可行解，于是,4567要設(shè)法迫使=x要設(shè)法迫使=x=0。（習(xí)題4.4）以上途徑通過修改（習(xí)題（習(xí)題4.4）minf=3x+5x+7x+Mx+Mx1 2 3 6 7其中M為足夠大的正數(shù)，然后以（習(xí)題4.3）為約束