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

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

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

（3.3-1)

(3.3-2)

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

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

(3.3-5)

第二步建立初始單純形表第七頁，共二十六頁，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)性檢驗數(shù)25100000表3.3-1第八頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法9重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智此表對應(yīng)一個可行方案和該方案最優(yōu)檢驗結(jié)果?？尚蟹桨福簒1=x2=0,x3=12000,x4=4000,x5=6000.最優(yōu)性檢驗結(jié)果：檢驗值全部非負(fù)（若全部非正，則可行方案是最優(yōu)方案）第九頁，共二十六頁，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)性檢驗數(shù)03.750-62.50250000第三步：改進(jìn)當(dāng)前可行方案，計算下一張單純形表。表3.3-2第十頁，共二十六頁，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)性檢驗數(shù)000-62.5-9.375306250第四步：改進(jìn)當(dāng)前可行方案，計算下一張單純形表。表3.3-3第十一頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法12重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智最優(yōu)性檢驗結(jié)果：檢驗值全部為非正

最優(yōu)方案:

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

x3=x4=x5=0(件).

最大效益為:306250(美元)

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

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

具體做法是：

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

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

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

量。

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

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

（1）大M法

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

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

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

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

(3.3-6)第十六頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法17重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智具體解題步驟見下表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第十七頁，共二十六頁，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第十八頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法19重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智該問題的最優(yōu)解為：X*=(0，10)T；

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

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

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

（2）兩階段法

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

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

(3.3-7)

第一階段模型：

(3.3-8)

第二十一頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法22重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智具體解題步驟見下表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第二十二頁，共二十六頁，2022年，8月28日§3.3線性規(guī)劃求解方法23重慶大學(xué)經(jīng)濟(jì)與工商管理學(xué)院肖智表3.3-5續(xù)

第二階段模型：

(3.3-9)