線性規(guī)劃及其應(yīng)用線性規(guī)劃求解方法

1第一頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法2重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智4、作用：線性規(guī)劃理論的幾何意義，并說(shuō)明線性規(guī)劃解的四種情況（唯一最優(yōu)解、無(wú)窮最優(yōu)解、有可行解而無(wú)最優(yōu)解、無(wú)可行解）。5、舉例說(shuō)明。三、單純形法

1、單純形法的概述1）適用范圍：線性規(guī)劃標(biāo)準(zhǔn)形問(wèn)題。2）基本原理：（1）目標(biāo)：使Z=CX最大，在AX=b,X≥0條件下；（2）理論：線性規(guī)劃基本理論（3）結(jié)論：第二頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法3重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

（3.3-1)

(3.3-2)

(3.3-3)第三頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法4重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智要使Z=CX達(dá)到最大，由(3.3-3)知只需去尋找一恰當(dāng)?shù)幕鵅使得(稱(chēng)為檢驗(yàn)數(shù)向量)3）基本思路：基于線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形，先確定一初始基可行解X0，并由此開(kāi)始在保證目標(biāo)函數(shù)值不下降的情況下逐次施行從一個(gè)基可行解到另一個(gè)基可行解的轉(zhuǎn)換。如此進(jìn)行下去，直到取得最優(yōu)解或判明問(wèn)題無(wú)最優(yōu)解為止。4）基本步驟：（1）對(duì)一般線性規(guī)劃問(wèn)題標(biāo)準(zhǔn)化；（2）確定一初始基可行解X0；（3）若所有檢驗(yàn)數(shù)σj≤0（σj為的第j個(gè)分量）,則X0是線性規(guī)劃問(wèn)題的最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)(4)第四頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法5重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智（4）若存在σt＜0所對(duì)應(yīng)的系數(shù)列向量pt≤O，則線性規(guī)劃問(wèn)題無(wú)最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)（5）。（5）按最大檢驗(yàn)數(shù)規(guī)則：確定進(jìn)基變量xk和主列pk；再按最小比值規(guī)則：確定出基變量xl和主元alk。（6）以主元alk進(jìn)行換基迭代得一新的基可行解x1,將x1記為x0返回到（3）。5）基本工具：計(jì)算機(jī)或單純形表。第五頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法6重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智2、單純形法應(yīng)用舉例：

(3.3-4)第六頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法7重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智第一步標(biāo)準(zhǔn)化

(3.3-5)

第二步建立初始單純形表第七頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法8重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

目標(biāo)函數(shù)系數(shù)2510000資源擁有量

決策變量x1x2x3x4x50(x3的目標(biāo)系數(shù)）x30.60.5100120000(x4的目標(biāo)系數(shù)）x40.40.101040000(x5的目標(biāo)系數(shù)）x50.00.40016000最優(yōu)性檢驗(yàn)數(shù)25100000表3.3-1第八頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法9重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智此表對(duì)應(yīng)一個(gè)可行方案和該方案最優(yōu)檢驗(yàn)結(jié)果?？尚蟹桨福簒1=x2=0,x3=12000,x4=4000,x5=6000.最優(yōu)性檢驗(yàn)結(jié)果：檢驗(yàn)值全部非負(fù)（若全部非正，則可行方案是最優(yōu)方案）第九頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法10重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

目標(biāo)函數(shù)系數(shù)2510000可行方案決策變量x1x2x3x4x50x300.351-1.50600025x110.2502.50100000x500.40016000最優(yōu)性檢驗(yàn)數(shù)03.750-62.50250000第三步：改進(jìn)當(dāng)前可行方案，計(jì)算下一張單純形表。表3.3-2第十頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法11重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智

目標(biāo)函數(shù)系數(shù)2510000可行方案決策變量x1x2x3x4x50x3001-1.5-0.87575025x11002.5-0.625625010x201002.515000最優(yōu)性檢驗(yàn)數(shù)000-62.5-9.375306250第四步：改進(jìn)當(dāng)前可行方案，計(jì)算下一張單純形表。表3.3-3第十一頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法12重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智最優(yōu)性檢驗(yàn)結(jié)果：檢驗(yàn)值全部為非正

最優(yōu)方案:

x1=6250(件),x2=15000(件),

x3=x4=x5=0(件).

最大效益為:306250(美元)

第十二頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法13重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智3、初始基可行解的求法：

在前邊的討論中我們總假定當(dāng)問(wèn)題化為標(biāo)準(zhǔn)型后，系數(shù)矩陣中有一個(gè)全部由松弛變量列向量構(gòu)成的單位矩陣，如果右邊項(xiàng)系數(shù)全都大于或等于零，只要取該單位矩陣為初始基就可以得到一個(gè)初始基本可行解。但在一般情況下，化為標(biāo)準(zhǔn)型的矩陣中不一定含有單位短陣。例如，當(dāng)線性規(guī)劃問(wèn)題有等式約束時(shí)就無(wú)法引入松弛變量；如果約束的右邊項(xiàng)系數(shù)出現(xiàn)負(fù)值時(shí)也無(wú)法直接得到一個(gè)初始可行解。在這種情況下，可引入人工變量來(lái)構(gòu)造一個(gè)初始基。

具體做法是：

1)將所有約束的右邊項(xiàng)值調(diào)整為大于或等于零：對(duì)右邊項(xiàng)第十三頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法14重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智為負(fù)的約束，約束兩邊同乘一l。

2)對(duì)小于等于型約束(≤)，仍引入一個(gè)松弛變量。

3)對(duì)大于等于型約束(≥)，引入一個(gè)剩余變量和一個(gè)人工變

量。

4)對(duì)等于型約束(＝)，引入一個(gè)人工變量。

通過(guò)以上調(diào)整后，每一個(gè)約束或者有一個(gè)松弛變量，或者有一個(gè)人工變量，它們構(gòu)成的單位矩陣可以作為一個(gè)初始基，可見(jiàn)，調(diào)整后的問(wèn)題一定有可行解。然而，對(duì)原問(wèn)題來(lái)說(shuō)，新引入的人工變量是多余的，如果人工變量在最后的結(jié)果中取正值，則表明該解不滿足原問(wèn)題約束條件。因此，盡管引入人工變量后我們可以很容易找到一個(gè)初始第十四頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法15重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智基，然而該基不一定是原問(wèn)題的可行基，只有當(dāng)人工變量都變?yōu)榉腔兞炕蚨紴榱銜r(shí)，引入人工變量的問(wèn)題才與原問(wèn)題等價(jià)。因此，應(yīng)通過(guò)某種方法把所有的人工變量從基中趕出去才能得到原問(wèn)題的一個(gè)可行基。常用的方法有以下兩種：

（1）大M法

大M法實(shí)質(zhì)上是一種罰函數(shù)法，它在目標(biāo)函數(shù)中賦予人工變量一個(gè)很大的負(fù)系數(shù)(一M)。由于人工變量對(duì)目標(biāo)函數(shù)

有很大的負(fù)影響，單純形方法的尋優(yōu)機(jī)制會(huì)自動(dòng)將人工變量趕到基外，從而找到一個(gè)原問(wèn)題的可行基。

用單純形表計(jì)算時(shí)，可直接在目標(biāo)函數(shù)中使用M參數(shù)，第十五頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法16重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智通過(guò)人的計(jì)算和判斷進(jìn)行單純形迭代。用計(jì)算機(jī)計(jì)算時(shí)，由于計(jì)算機(jī)無(wú)法直接使用參數(shù)計(jì)算，M必須賦予一個(gè)較大的值，并視求解的情況對(duì)M值進(jìn)行調(diào)整。如果給定M后，計(jì)算所得的最優(yōu)基已不含人工變量，該解即為最優(yōu)可行解。當(dāng)給定的M足夠大時(shí)，最優(yōu)解中仍含有人工變量，則可判斷原問(wèn)題無(wú)可行解。下面舉例說(shuō)明如何使用大M法。

例：用大M法求解下列線性規(guī)劃問(wèn)題：

(3.3-6)第十六頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法17重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智具體解題步驟見(jiàn)下表3.3-4cj2300-M-MbxBCBx1x2x3x4x5x6x3021100016x5-M130-11020x6-M11000110σj2+2M3+4M0-M00-30Mx305/3011/3-1/3028/3x231/310-1/31/3020/3x6-M2/3001/3-1/3110/3σj1+2M/3001+M/3-1-4M/3020-10M/3第十七頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法18重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智表3.3-4續(xù)cj2300-M-MbxBCBx1x2x3x4x5x6x30001-1/21/2-5/21x23010-1/21/2-1/25x121001/2-1/23/25σj0001/2-1/2-M-3/2-M25x3010100-16x2311000110x402001-1310σj-1000-M-3-M30第十八頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法19重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智該問(wèn)題的最優(yōu)解為：X*=(0，10)T；

最優(yōu)值為:Z*=30

與計(jì)算機(jī)計(jì)算結(jié)果相同。

大M法的優(yōu)點(diǎn)是方法比較直觀，易于理解和手工計(jì)算，缺點(diǎn)是當(dāng)使用計(jì)算機(jī)計(jì)算時(shí)，由于M值較大容易引起數(shù)值計(jì)算上的困難，所以幾乎所有商業(yè)線性規(guī)劃軟件都不使用大M法而使用另外一種方法—兩階段法。

（2）兩階段法

顧名思義，兩階段法是將線性規(guī)劃求解過(guò)程分為兩個(gè)階段。第一階段只是尋找一個(gè)初始可行基，第二階段再按正常方法尋找最優(yōu)解。第十九頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法20重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智第一階段：在原問(wèn)題中引入人工變量并找到一個(gè)初始基。另構(gòu)造一個(gè)新的求極小值的目標(biāo)函數(shù)，該目標(biāo)函數(shù)除人工變量的系數(shù)為1以外，其余變量的目標(biāo)函數(shù)系數(shù)都為零。求解該線性規(guī)劃問(wèn)題，在不退化的前提下，如果得到的最優(yōu)解值為零，表明所有的人工變量已經(jīng)不在基中。第一階段的最優(yōu)解即是原問(wèn)題的一個(gè)基可行解。

第二階段：將原目標(biāo)函數(shù)換回，以第一階段得到的可行基為初始基進(jìn)行迭代，直到找到最優(yōu)基為止。在第二階段的迭代中可以刪去所有人工變量，保留它們只會(huì)增加不必要的計(jì)算。下面舉例說(shuō)明兩階段法求解過(guò)程。第二十頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法21重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智例：用兩階段法求解下列線性規(guī)劃問(wèn)題：

(3.3-7)

第一階段模型：

(3.3-8)

第二十一頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法22重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智具體解題步驟見(jiàn)下表3.3-5cj0000-1-1bxBCBx1x2x3x4x5x6x3021100016x5-1130-11020x6-111000110σj240-100-30x305/3011/3-1/3028/3x201/310-1/31/3020/3x6-12/3001/3-1/3110/3σj2/3001/3-4/30-10/3第二十二頁(yè)，共二十六頁(yè)，2022年，8月28日§3.3線性規(guī)劃求解方法23重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智表3.3-5續(xù)

第二階段模型：

(3.3-9)