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

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

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

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

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

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

（LinearProgramming)1.1.1Lp的簡(jiǎn)單例子和模型

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

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

單位單位時(shí)耗資源

一

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

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

第7頁,共70頁，2024年2月25日，星期天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第8頁,共70頁，2024年2月25日，星期天9單臺(tái)運(yùn)費(fèi)B1(100)B2(80)B3(90,120)A1(200)152118A2(150)162516問題：如何調(diào)運(yùn)才能即滿足用戶需要，又使總運(yùn)費(fèi)最少？ 例1.2-2運(yùn)輸問題

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

1）和式

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

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

02、對(duì)標(biāo)準(zhǔn)型問題作出的假設(shè)第16頁,共70頁，2024年2月25日，星期天17

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

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

為負(fù)值，則在bi所在之方程的兩邊乘以-1。4、一般型變標(biāo)準(zhǔn)型的變換方法：1.目標(biāo)函數(shù)為min型時(shí)，價(jià)值系數(shù)一律反號(hào)。即令z

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

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

=0

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

，稱為剩余變量；同時(shí)令cn+i

=0

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

xj=xj

-xj

，xj

0，xj

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

xj=-xj

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

0第20頁,共70頁，2024年2月25日，星期天21原非標(biāo)準(zhǔn)型：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標(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.第22頁,共70頁，2024年2月25日，星期天23例2第23頁,共70頁，2024年2月25日，星期天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.第24頁,共70頁，2024年2月25日，星期天25

1.2求解LP問題的基本定理

1.2.1LP的圖解法

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

如：第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

為坐標(biāo)向量建立直角坐標(biāo)系。在直角坐標(biāo)系里，圖上任意一點(diǎn)的坐標(biāo)代表了決策變量的一組值，例1.3的每個(gè)約束條件都代表一個(gè)半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第27頁,共70頁，2024年2月25日，星期天28（2）對(duì)每個(gè)不等式(約束條件)，先取其等式在坐標(biāo)系中作直線，然后確定不等式所決定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第28頁,共70頁，2024年2月25日，星期天29（3）把五個(gè)圖合并成一個(gè)圖，取各約束條件的公共部分，如P7圖1-2所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400圖1-2第29頁,共70頁，2024年2月25日，星期天30（4）目標(biāo)函數(shù)z=50x1+100x2，當(dāng)z取某一固定值時(shí)得到一條直線，直線上的每一點(diǎn)都具有相同的目標(biāo)函數(shù)值，稱之為“等值線”。平行移動(dòng)等值線，當(dāng)移動(dòng)到B點(diǎn)時(shí)，z在可行域內(nèi)實(shí)現(xiàn)了最大化。A，B，C，D，E是可行域的頂點(diǎn)，對(duì)有限個(gè)約束條件則其可行域的頂點(diǎn)也是有限的。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)目標(biāo)值z(mì)=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說明：生產(chǎn)50單位Ⅰ產(chǎn)品和250單位Ⅱ產(chǎn)品將消耗完所有資源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無需化標(biāo)準(zhǔn)形

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

z=3x1+5x2

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

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

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

2、Lp問題的幾個(gè)特點(diǎn)(相關(guān)證明請(qǐng)看1.7節(jié))：

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

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

設(shè)X屬于S,若x=0,則一定為極點(diǎn)；若x

0，則為極點(diǎn)的充要條件是：x的正分量所對(duì)應(yīng)的系數(shù)列向量線性無關(guān)。

只要存在可行解，就一定存在極點(diǎn)

極點(diǎn)的個(gè)數(shù)是有限的第38頁,共70頁，2024年2月25日，星期天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個(gè)線性無關(guān)的向量。

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

基、基變量、非基變量——技術(shù)系數(shù)矩陣A（標(biāo)準(zhǔn)線性規(guī)劃模型）中m個(gè)線性無關(guān)的列向量所對(duì)應(yīng)的m個(gè)變量，構(gòu)成該LP問題的一個(gè)基，這m個(gè)變量的系數(shù)列向量組成的矩陣稱為基陣，記為B?；械拿總€(gè)變量稱為基變量,記為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時(shí)，稱為基可行解.

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

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

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

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

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

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

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

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

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

xj*

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

最小，則第i*行對(duì)應(yīng)的基變量稱為出基變量，第i*行稱為主行5迭代過程主行i*行與主列j*相交的元素ai*j*稱為主元，迭代以主元為中心進(jìn)行迭代的實(shí)質(zhì)是線性變換，即要將主元ai*j*變?yōu)?，主列上其它元素變?yōu)?，變換步驟如下：(1)變換主行第51頁,共70頁，2024年2月25日，星期天52(2)變換主列除主元保留為1，其余都置0(3)變換非主行、主列元素aij(包括bi)(4)變換CB，XB(5)計(jì)算目標(biāo)函數(shù)、機(jī)會(huì)成本zj和檢驗(yàn)數(shù)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基可行解的判別和改進(jìn)定理1.6

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

若存在某一個(gè)檢驗(yàn)數(shù)>0，而它所對(duì)應(yīng)的列向量的全部分量

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

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

當(dāng)約束條件為“

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

由于所添加的剩余變量的技術(shù)系數(shù)為

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

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

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

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