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

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

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

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

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

線性規(guī)劃解決的問題：1、生產的合理安排問題2、投資決策問題3、運輸問題第4頁,共70頁，2024年2月25日，星期天51.1什么是線性規(guī)劃

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

（1）數學模型

一個實際問題的數學模型，是依據客觀規(guī)律，對該問題中我們所關心的那些量進行科學的分析后得出的反映這些量之間本質聯(lián)系的數學關系式。第5頁,共70頁，2024年2月25日，星期天6

單位單位時耗資源

一

二現(xiàn)有工時攪拌機/小時3515成形機/小時215烘箱/小時2211利潤（百元/噸）54例1.2-1餅干生產問題第6頁,共70頁，2024年2月25日，星期天7

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

第7頁,共70頁，2024年2月25日，星期天8解：設由x1，x2

分別表示1，2型餅干每天的生產量。

max

z=5x1+4x2

s.t.3x1+5x2≤15,2x1+x2≤5,2x1+2x2≤11,x1,x2≥0.max——maximize,s.t.——subjectto第8頁,共70頁，2024年2月25日，星期天9單臺運費B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516問題：如何調運才能即滿足用戶需要，又使總運費最少？ 例1.2-2運輸問題

第9頁,共70頁，2024年2月25日，星期天10第10頁,共70頁，2024年2月25日，星期天111.1.2線性規(guī)劃數學模型的一般表示方式第11頁,共70頁，2024年2月25日，星期天121.1.3線性規(guī)劃數學模型的標準型第12頁,共70頁，2024年2月25日，星期天131、標準型的幾種不同的表示方式

1）和式

第13頁,共70頁，2024年2月25日，星期天142）向量式第14頁,共70頁，2024年2月25日，星期天153）矩陣第15頁,共70頁，2024年2月25日，星期天16

1）A中沒有多余方程；2）b

02、對標準型問題作出的假設第16頁,共70頁，2024年2月25日，星期天17

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

滿足約束條件和非負條件的解X稱為可行解，所有可行解組成的集合稱之為可行解集（可行域）3、LP問題解的幾個基本概念第17頁,共70頁，2024年2月25日，星期天182.第i個約束的bi

為負值，則在bi所在之方程的兩邊乘以-1。4、一般型變標準型的變換方法：1.目標函數為min型時，價值系數一律反號。即令z

(x)=-z(x)=-CX第18頁,共70頁，2024年2月25日，星期天193.第i個約束為型，在不等式左邊增加一個非負的變量xn+i

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

=0

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

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

=0

第19頁,共70頁，2024年2月25日，星期天206.若xj無符號限制，令

xj=xj

-xj

，xj

0，xj

0，代入非標準型5.若xj0，令

xj=-xj

，代入非標準型，則有xj

0第20頁,共70頁，2024年2月25日，星期天21原非標準型：maxz=5x1+4x2

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

變換舉例

例1.

第21頁,共70頁，2024年2月25日，星期天22標準型：maxz=5x1+4x2

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

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.第22頁,共70頁，2024年2月25日，星期天23例2第23頁,共70頁，2024年2月25日，星期天24標準型：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.第24頁,共70頁，2024年2月25日，星期天25

1.2求解LP問題的基本定理

1.2.1LP的圖解法

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

如：第25頁,共70頁，2024年2月25日，星期天26例1.3Maxz=50x1+100x2

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

x2≥0第26頁,共70頁，2024年2月25日，星期天27采用圖解法(1)分別取決策變量X1,X2

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

x1=50，x2=250

最優(yōu)目標值z=27500第31頁,共70頁，2024年2月25日，星期天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說明：生產50單位Ⅰ產品和250單位Ⅱ產品將消耗完所有資源1和3，但資源2還剩余50。第32頁,共70頁，2024年2月25日，星期天33maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5無需化標準形

例1.2-1求解餅干生產問題第33頁,共70頁，2024年2月25日，星期天34圖中的OABC即為滿足約束條件的可行解集S,需在S中找出最優(yōu)解,若z為一常數z0則z0=5x1+4x2為目標函數等值線（x1=10/7,x2=15/7,z*=110/7)。第34頁,共70頁，2024年2月25日，星期天35例1.2-2假設上例中的目標函數變?yōu)?/p>

z=3x1+5x2

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

見P18圖1.3若是求目標函數最小值，則有最優(yōu)解。若是求目標函數最大值，則無最優(yōu)解。若可行解集為空集，則無解，P19圖1.4第35頁,共70頁，2024年2月25日，星期天36求解LP問題的重要規(guī)律：一、解的存在性問題二、解的結構問題三、關于最優(yōu)解的獲得方法問題（在可行解集的某些“頂點”得到）第36頁,共70頁，2024年2月25日，星期天37關于LP問題求解的一些基本概念和特點：1、兩個基本概念凸集:實向量空間E中任意兩點連線上的一切點仍屬于E(見P20)

極點就是不能成為E中任何線段的內點的那種點第37頁,共70頁，2024年2月25日，星期天38

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

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

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

設X屬于S,若x=0,則一定為極點；若x

0，則為極點的充要條件是：x的正分量所對應的系數列向量線性無關。

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

極點的個數是有限的第38頁,共70頁，2024年2月25日，星期天392、“基”的概念在標準型中，技術系數矩陣有n+m列，即

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

關于標準型解的若干基本概念：1、標準型有n+m個變量，m個約束行第39頁,共70頁，2024年2月25日，星期天40

基、基變量、非基變量——技術系數矩陣A（標準線性規(guī)劃模型）中m個線性無關的列向量所對應的m個變量，構成該LP問題的一個基，這m個變量的系數列向量組成的矩陣稱為基陣，記為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時，稱為基可行解.

第40頁,共70頁，2024年2月25日，星期天41

若基可行解的所有基變量均取正值，則稱為非退化的基可行解，如果某些基變量取零值，則為退化的基可行解。第41頁,共70頁，2024年2月25日，星期天42可行解、基解和基可行解舉例第42頁,共70頁，2024年2月25日，星期天43可行解、基礎解和基礎可行解舉例第43頁,共70頁，2024年2月25日，星期天44X是極點的充分必要條件是：它是基可行解。由此，有關極點的結果可轉到基可行解上：

只要存在可行解，就一定存在基可行解；基可行解的個數是有限的；若LP問題有最優(yōu)解，則最優(yōu)解一定可以在基可行解中找到。第44頁,共70頁，2024年2月25日，星期天45

1.3單純型法的基本思路確定初始基可行解是否為最優(yōu)確定改善方向求新的基可行解求最優(yōu)解的目標函數值是否第45頁,共70頁，2024年2月25日，星期天46(1)單純形表的組成及形式設B是初始可行基向量，則目標函數可寫為兩部分(1)約束條件也寫為兩部分，經整理得XB的表達式(2)，注意XB中含有非基變量作參數把XB代入目標函數，整理得到(3)式若所有非基變量的檢驗數σi

0,則達到最優(yōu)第46頁,共70頁，2024年2月25日，星期天47單純形表第47頁,共70頁，2024年2月25日，星期天48例1.1試列出下面線性規(guī)劃問題的初始單純形表

第48頁,共70頁，2024年2月25日，星期天49

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

檢驗當前基礎可行解是否為最優(yōu)解所有檢驗數σj0，則為最優(yōu)解，否則1.3.2標準型的單純型法基本步驟

第49頁,共70頁，2024年2月25日，星期天504確定出基變量最小比例原則3確定入基變量從σj>0中找最大者，選中者稱為入基變量

xj*

第j*列稱為主列第50頁,共70頁，2024年2月25日，星期天51設第i*行使

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

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

若存在某一個檢驗數>0，而它所對應的列向量的全部分量

0，則所給問題無最優(yōu)解

除上述兩種情況外，若每個正檢驗數所對應的列向量中都有正分量，則為確定最優(yōu)解需要進行基的變換（換基）第54頁,共70頁，2024年2月25日，星期天55請查看教材P29中單純形表的組成形式。第55頁,共70頁，2024年2月25日，星期天56

當約束條件為“

”型，引入剩余變量和人工變量1.4人工變量的引入及其解法第56頁,共70頁，2024年2月25日，星期天57

由于所添加的剩余變量的技術系數為

1，不能作為初始可行基變量，為此引入一個人為的變量（注意，此時約束條件已為“=”型），以便取得初始基變量，故稱為人工變量.兩種方法：大M法兩階段法第57頁,共70頁，2024年2月25日，星期天58多個基礎可行解都是最優(yōu)解，這些解在同一個平面上，且該平面與目標函數等值面平行最優(yōu)單純形表中有非基變量的檢驗數為01.5單純形法應用的特例

1.5.1關于多重解問題第58頁,共70頁，2024年2月25日，星期天59第59頁,共70頁，2024年2月25日，星期天60例1.5.1的單純形表及其迭代過程第60頁,共70頁，2024年2月25日，星期天61

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

第61頁,共70頁，2024年2月25日，星期天62例1.5.2用單純形表求解下列線性規(guī)劃問題第62頁,共70頁，2024年2月25日，星期天63迭代次數基變量CBbx1x2x3s1s2s3比值203/20000s1s2s30002431-101002010101