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

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

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

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

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

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

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

（1）數(shù)學模型

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

單位單位時耗資源

一

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

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

第七頁，共六十七頁，編輯于2023年，星期一解：設由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第八頁，共六十七頁，編輯于2023年，星期一單臺運費B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516問題：如何調運才能即滿足用戶需要，又使總運費最少？ 例1.2-2運輸問題

第九頁，共六十七頁，編輯于2023年，星期一第十頁，共六十七頁，編輯于2023年，星期一1.1.2線性規(guī)劃數(shù)學模型的一般表示方式第十一頁，共六十七頁，編輯于2023年，星期一1.1.3線性規(guī)劃數(shù)學模型的標準型第十二頁，共六十七頁，編輯于2023年，星期一1、標準型的幾種不同的表示方式

1）和式

第十三頁，共六十七頁，編輯于2023年，星期一2）向量式第十四頁，共六十七頁，編輯于2023年，星期一3）矩陣第十五頁，共六十七頁，編輯于2023年，星期一

1）A中沒有多余方程；2）b02、對標準型問題作出的假設第十六頁，共六十七頁，編輯于2023年，星期一

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

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

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

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

=0

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

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

=0

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

xj=xj-xj，xj

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

xj=-xj

，代入非標準型，則有xj

0第二十頁，共六十七頁，編輯于2023年，星期一原非標準型：maxz=5x1+4x2

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

變換舉例

例1.

第二十一頁，共六十七頁，編輯于2023年，星期一標準型：maxz=5x1+4x2

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

x4=5,2x1+2x2+x5=11,x1，x2，x3，x4，x5≥0.第二十二頁，共六十七頁，編輯于2023年，星期一例2第二十三頁，共六十七頁，編輯于2023年，星期一標準型：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年，星期一

1.2求解LP問題的基本定理

1.2.1LP的圖解法

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

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

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

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

為坐標向量建立直角坐標系。在直角坐標系里，圖上任意一點的坐標代表了決策變量的一組值，例1.3的每個約束條件都代表一個半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第二十七頁，共六十七頁，編輯于2023年，星期一（2）對每個不等式(約束條件)，先取其等式在坐標系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第二十八頁，共六十七頁，編輯于2023年，星期一（3）把五個圖合并成一個圖，取各約束條件的公共部分，如P7圖1-2所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖1-2第二十九頁，共六十七頁，編輯于2023年，星期一（4）目標函數(shù)z=50x1+100x2，當z取某一固定值時得到一條直線，直線上的每一點都具有相同的目標函數(shù)值，稱之為“等值線”。平行移動等值線，當移動到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第三十頁，共六十七頁，編輯于2023年，星期一得到最優(yōu)解：

x1=50，x2=250

最優(yōu)目標值z=27500第三十一頁，共六十七頁，編輯于2023年，星期一若在上例模型中中引入松弛變量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。第三十二頁，共六十七頁，編輯于2023年，星期一maxz=5x1+4x21.1s.t.3x1+5x2≤15,1.22x1+x2≤5,1.32x1+2x2≤11,1.4x1,x2≥0.1.5無需化標準形

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

z=3x1+5x2

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

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

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

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

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

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

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

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

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

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

關于標準型解的若干基本概念：1、標準型有n+m個變量，m個約束行第三十九頁，共六十七頁，編輯于2023年，星期一

基、基變量、非基變量——技術系數(shù)矩陣A（標準線性規(guī)劃模型）中m個線性無關的列向量所對應的m個變量，構成該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年，星期一

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

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

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

第四十八頁，共六十七頁，編輯于2023年，星期一

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

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

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

xj*

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

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

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

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

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

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

1.5.1關于多重解問題第五十八頁，共六十七頁，編輯于2023年，星期一第五十九頁，共六十七頁，編輯于2023年，星期一例1.5.1的單純形表及其迭代過程第六十頁，共六十七頁，編輯于2023年，星期一

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

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