線性規(guī)劃問題及單純形解法

關(guān)于線性規(guī)劃問題及單純形解法第一頁，共七十頁，編輯于2023年，星期三2

線性規(guī)劃及應(yīng)用簡介

線性規(guī)劃是運(yùn)籌學(xué)的一個最基本的分支，它已成為幫助各級管理人員進(jìn)行決策的·一種十分重要的工具．是一種目前最常用而又最為成功的定性分析和定量分析相結(jié)合的管理優(yōu)化技術(shù)。其原因有三：一、應(yīng)用廣泛．管理工作中的大量優(yōu)化問題可以用線性規(guī)劃的模型來表達(dá)第二頁，共七十頁，編輯于2023年，星期三3三、求解方法采用成熟的單純形法．目前，用單純形法解線性規(guī)劃的計算機(jī)程序已大量涌現(xiàn)，在計算機(jī)上求解此類問題已十分容易二、模型較為簡單，容易建立，容易學(xué)習(xí)和掌握．第三頁，共七十頁，編輯于2023年，星期三4

線性規(guī)劃的一種最大量、最普遍的應(yīng)用就是研究有限資源的合理利用問題，或說資源的最優(yōu)配置問題．資源分配問題有多種多樣的具體形式．例：

線性規(guī)劃解決的問題：1、生產(chǎn)的合理安排問題2、投資決策問題3、運(yùn)輸問題第四頁，共七十頁，編輯于2023年，星期三51.1什么是線性規(guī)劃

（LinearProgramming)1.1.1Lp的簡單例子和模型

（1）數(shù)學(xué)模型

一個實際問題的數(shù)學(xué)模型，是依據(jù)客觀規(guī)律，對該問題中我們所關(guān)心的那些量進(jìn)行科學(xué)的分析后得出的反映這些量之間本質(zhì)聯(lián)系的數(shù)學(xué)關(guān)系式。第五頁，共七十頁，編輯于2023年，星期三6

單位單位時耗資源

一

二現(xiàn)有工時攪拌機(jī)/小時3515成形機(jī)/小時215烘箱/小時2211利潤（百元/噸）54例1.2-1餅干生產(chǎn)問題第六頁，共七十頁，編輯于2023年，星期三7

問題：如何制訂生產(chǎn)計劃，才能使資源利用充分并使廠方獲最大利潤。

第七頁，共七十頁，編輯于2023年，星期三8解：設(shè)由x1，x2

分別表示1，2型餅干每天的生產(chǎn)量。

max

z=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.max——maximize,s.t.——subjectto第八頁，共七十頁，編輯于2023年，星期三9單臺運(yùn)費B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516問題：如何調(diào)運(yùn)才能即滿足用戶需要，又使總運(yùn)費最少？ 例1.2-2運(yùn)輸問題

第九頁，共七十頁，編輯于2023年，星期三10第十頁，共七十頁，編輯于2023年，星期三111.1.2線性規(guī)劃數(shù)學(xué)模型的一般表示方式第十一頁，共七十頁，編輯于2023年，星期三121.1.3線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型第十二頁，共七十頁，編輯于2023年，星期三131、標(biāo)準(zhǔn)型的幾種不同的表示方式

1）和式

第十三頁，共七十頁，編輯于2023年，星期三142）向量式第十四頁，共七十頁，編輯于2023年，星期三153）矩陣第十五頁，共七十頁，編輯于2023年，星期三16

1）A中沒有多余方程；2）b02、對標(biāo)準(zhǔn)型問題作出的假設(shè)第十六頁，共七十頁，編輯于2023年，星期三17

最優(yōu)解使z達(dá)到最優(yōu)的可行解就是最優(yōu)解（有解（給定的Lp問題有最優(yōu)解）、否則無解）可行解

滿足約束條件和非負(fù)條件的解X稱為可行解，所有可行解組成的集合稱之為可行解集（可行域）3、LP問題解的幾個基本概念第十七頁，共七十頁，編輯于2023年，星期三182.第i個約束的bi

為負(fù)值，則在bi所在之方程的兩邊乘以-1。4、一般型變標(biāo)準(zhǔn)型的變換方法：1.目標(biāo)函數(shù)為min型時，價值系數(shù)一律反號。即令z(x)=-z(x)=-CX第十八頁，共七十頁，編輯于2023年，星期三193.第i個約束為型，在不等式左邊增加一個非負(fù)的變量xn+i

，稱為松弛變量（原有變量為構(gòu)造變量）；同時令cn+i

=0

4.第i個約束為型，在不等式左邊減去一個非負(fù)的變量xn+i

，稱為剩余變量；同時令cn+i

=0

第十九頁，共七十頁，編輯于2023年，星期三206.若xj無符號限制，令

xj=xj-xj，xj

0，xj0，代入非標(biāo)準(zhǔn)型5.若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0第二十頁，共七十頁，編輯于2023年，星期三21原非標(biāo)準(zhǔn)型：maxz=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.5、

變換舉例

例1.

第二十一頁，共七十頁，編輯于2023年，星期三22標(biāo)準(zhǔn)型：maxz=5x1+4x2

s.t.3x1+5x2+x3=15,2x1+x2+

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.第二十二頁，共七十頁，編輯于2023年，星期三23例2第二十三頁，共七十頁，編輯于2023年，星期三24標(biāo)準(zhǔn)型：maxf(x)=-3x1+2x2-4x3′+4x3′′+0x4+0x5+0x6s.t.2x1+3x2+4x3′-4x3′′-x4=300,x1+5x2+6x3′-6x3′′+x5=400,x1+x2+x3′-x3′′+x6=200,x1,x2,x3′,x3′′,x4,x5,x6≥0.第二十四頁，共七十頁，編輯于2023年，星期三25

1.2求解LP問題的基本定理

1.2.1LP的圖解法

對于只有兩個決策變量的線性規(guī)劃問題，可以在平面直角坐標(biāo)系上作圖表示線性規(guī)劃問題的有關(guān)概念，并求解。

如：第二十五頁，共七十頁，編輯于2023年，星期三26例1.3Maxz=50x1+100x2

s.t.x1+x2≤3002x1+x2≤400x2≤250x1、

x2≥0第二十六頁，共七十頁，編輯于2023年，星期三27采用圖解法(1)分別取決策變量X1,X2

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點的坐標(biāo)代表了決策變量的一組值，例1.3的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第二十七頁，共七十頁，編輯于2023年，星期三28（2）對每個不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第二十八頁，共七十頁，編輯于2023年，星期三29（3）把五個圖合并成一個圖，取各約束條件的公共部分，如P7圖1-2所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖1-2第二十九頁，共七十頁，編輯于2023年，星期三30（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動等值線，當(dāng)移動到B點時，z在可行域內(nèi)實現(xiàn)了最大化。A，B，C，D，E是可行域的頂點，對有限個約束條件則其可行域的頂點也是有限的。x1x2z=20000=50x1+100x2圖1-3z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADEx1+x2=300第三十頁，共七十頁，編輯于2023年，星期三31得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標(biāo)值z=27500第三十一頁，共七十頁，編輯于2023年，星期三32若在上例模型中中引入松弛變量s1s2s3模型化為：Maxz=50x1+100x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

可求解得其最優(yōu)解為：

x1=50x2=250s1=0s2=50s3=0說明：生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有資源1和3，但資源2還剩余50。第三十二頁，共七十頁，編輯于2023年，星期三33maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5無需化標(biāo)準(zhǔn)形

例1.2-1求解餅干生產(chǎn)問題第三十三頁，共七十頁，編輯于2023年，星期三34圖中的OABC即為滿足約束條件的可行解集S,需在S中找出最優(yōu)解,若z為一常數(shù)z0則z0=5x1+4x2為目標(biāo)函數(shù)等值線（x1=10/7,x2=15/7,z*=110/7)。第三十四頁，共七十頁，編輯于2023年，星期三35例1.2-2假設(shè)上例中的目標(biāo)函數(shù)變?yōu)?/p>

z=3x1+5x2

此時最優(yōu)目標(biāo)函數(shù)等值線與AB邊重合，AB上每一點均為最優(yōu)解（無窮個）例1.2-3可行解集為一無界集合

見P18圖1.3若是求目標(biāo)函數(shù)最小值，則有最優(yōu)解。若是求目標(biāo)函數(shù)最大值，則無最優(yōu)解。若可行解集為空集，則無解，P19圖1.4第三十五頁，共七十頁，編輯于2023年，星期三36求解LP問題的重要規(guī)律：一、解的存在性問題二、解的結(jié)構(gòu)問題三、關(guān)于最優(yōu)解的獲得方法問題（在可行解集的某些“頂點”得到）第三十六頁，共七十頁，編輯于2023年，星期三37關(guān)于LP問題求解的一些基本概念和特點：1、兩個基本概念凸集:實向量空間E中任意兩點連線上的一切點仍屬于E(見P20)

極點就是不能成為E中任何線段的內(nèi)點的那種點第三十七頁，共七十頁，編輯于2023年，星期三38

2、Lp問題的幾個特點(相關(guān)證明請看1.7節(jié))：

最優(yōu)解只可能在凸集的極點上，而不可能發(fā)生在凸集的內(nèi)部

線性規(guī)劃問題的可行解集S是凸集

設(shè)X屬于S,若x=0,則一定為極點；若x0，則為極點的充要條件是：x的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。

只要存在可行解，就一定存在極點

極點的個數(shù)是有限的第三十八頁，共七十頁，編輯于2023年，星期三392、“基”的概念在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有n+m列，即

A=(P1,P2,…,Pn,Pn+1,,Pn+2,..Pn+m)因r(A)=m,所以A的極大無關(guān)組含有m個線性無關(guān)的向量。

關(guān)于標(biāo)準(zhǔn)型解的若干基本概念：1、標(biāo)準(zhǔn)型有n+m個變量，m個約束行第三十九頁，共七十頁，編輯于2023年，星期三40

基、基變量、非基變量——技術(shù)系數(shù)矩陣A（標(biāo)準(zhǔn)線性規(guī)劃模型）中m個線性無關(guān)的列向量所對應(yīng)的m個變量，構(gòu)成該LP問題的一個基，這m個變量的系數(shù)列向量組成的矩陣稱為基陣，記為B?；械拿總€變量稱為基變量,記為XB。其余的變量即為非基變量,記為XN

。如：Maxz=50x1+100x2s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0基解:令非基變量XN=0，求得基變量XB的值稱為基解.基可行解：若基解中所有的XB

都≥0時，稱為基可行解.

第四十頁，共七十頁，編輯于2023年，星期三41

若基可行解的所有基變量均取正值，則稱為非退化的基可行解，如果某些基變量取零值，則為退化的基可行解。第四十一頁，共七十頁，編輯于2023年，星期三42可行解、基解和基可行解舉例第四十二頁，共七十頁，編輯于2023年，星期三43可行解、基礎(chǔ)解和基礎(chǔ)可行解舉例第四十三頁，共七十頁，編輯于2023年，星期三44X是極點的充分必要條件是：它是基可行解。由此，有關(guān)極點的結(jié)果可轉(zhuǎn)到基可行解上：

只要存在可行解，就一定存在基可行解；基可行解的個數(shù)是有限的；若LP問題有最優(yōu)解，則最優(yōu)解一定可以在基可行解中找到。第四十四頁，共七十頁，編輯于2023年，星期三45

1.3單純型法的基本思路確定初始基可行解是否為最優(yōu)確定改善方向求新的基可行解求最優(yōu)解的目標(biāo)函數(shù)值是否第四十五頁，共七十頁，編輯于2023年，星期三46(1)單純形表的組成及形式設(shè)B是初始可行基向量，則目標(biāo)函數(shù)可寫為兩部分(1)約束條件也寫為兩部分，經(jīng)整理得XB的表達(dá)式(2)，注意XB中含有非基變量作參數(shù)把XB代入目標(biāo)函數(shù)，整理得到(3)式若所有非基變量的檢驗數(shù)σi0,則達(dá)到最優(yōu)第四十六頁，共七十頁，編輯于2023年，星期三47單純形表第四十七頁，共七十頁，編輯于2023年，星期三48例1.1試列出下面線性規(guī)劃問題的初始單純形表

第四十八頁，共七十頁，編輯于2023年，星期三49

找初始基礎(chǔ)可行基對于(max,)，松弛變量對應(yīng)的列構(gòu)成一個單位陣若有bi<0，則單位陣也不能構(gòu)成一個可行基

檢驗當(dāng)前基礎(chǔ)可行解是否為最優(yōu)解所有檢驗數(shù)σj0，則為最優(yōu)解，否則1.3.2標(biāo)準(zhǔn)型的單純型法基本步驟

第四十九頁，共七十頁，編輯于2023年，星期三504確定出基變量最小比例原則3確定入基變量從σj>0中找最大者，選中者稱為入基變量

xj*

第j*列稱為主列第五十頁，共七十頁，編輯于2023年，星期三51設(shè)第i*行使最小，則第i*行對應(yīng)的基變量稱為出基變量，第i*行稱為主行5迭代過程主行i*行與主列j*相交的元素ai*j*稱為主元，迭代以主元為中心進(jìn)行迭代的實質(zhì)是線性變換，即要將主元ai*j*變?yōu)?，主列上其它元素變?yōu)?，變換步驟如下：(1)變換主行第五十一頁，共七十頁，編輯于2023年，星期三52(2)變換主列除主元保留為1，其余都置0(3)變換非主行、主列元素aij(包括bi)(4)變換CB，XB(5)計算目標(biāo)函數(shù)、機(jī)會成本zj和檢驗數(shù)cjzj6、返回步驟2第五十二頁，共七十頁，編輯于2023年，星期三53例1.1單純形表的迭代過程答：最優(yōu)解為x1=20,x2=20,x3=0,OBJ=1700第五十三頁，共七十頁，編輯于2023年，星期三541.3.3基可行解的判別和改進(jìn)定理1.6

若所有檢驗數(shù)σj0，則為最優(yōu)解定理1.7

若存在某一個檢驗數(shù)>0，而它所對應(yīng)的列向量的全部分量0，則所給問題無最優(yōu)解

除上述兩種情況外，若每個正檢驗數(shù)所對應(yīng)的列向量中都有正分量，則為確定最優(yōu)解需要進(jìn)行基的變換（換基）第五十四頁，共七十頁，編輯于2023年，星期三55請查看教材P29中單純形表的組成形式。第五十五頁，共七十頁，編輯于2023年，星期三56

當(dāng)約束條件為“”型，引入剩余變量和人工變量1.4人工變量的引入及其解法第五十六頁，共七十頁，編輯于2023年，星期三57

由于所添加的剩余變量的技術(shù)系數(shù)為1，不能作為初始可行基變量，為此引入一個人為的變量（注意，此時約束條件已為“=”型），以便取得初始基變量，故稱為人工變量.兩種方法：大M法兩階段法第五十七頁，共七十頁，編輯于2023年，星期三58多個基礎(chǔ)可行解都是最優(yōu)解，這些解在同一個平面上，且該平面與目標(biāo)函數(shù)等值面平行最優(yōu)單純形表中有非基變量的檢驗數(shù)為01.5單純形法應(yīng)用的特例

1.5.1關(guān)于多重解問題第五十八頁，共七十頁，編輯于2023年，星期三59第五十九頁，共七十頁，編輯于2023年，星期三60例1.5.1的單純形表及其迭代過程第六十頁，共七十頁，編輯于2023年，星期三61

在單純形法計算過程中，確定出基變量時有時存在兩個以上的相同的最小比值，即同時有多個基變量可選作出基變量，這樣在下一次迭代中就有了一個或幾個基變量等于零，這稱之為退化。1.5.2關(guān)于退化問題

第六十一頁，共七十頁，編輯于2023年，星期三62例1.5.2用單純形表求解下列線性規(guī)劃問題第六十二頁，共七十頁，編輯于2023年，星期三63迭代次數(shù)基變量CBbx1x2x3s1s2s3比值203/20000s1s2s30002431-1010020101