線性規(guī)劃解概念和單純形法詳解演示文稿

線性規(guī)劃解概念和單純形法詳解演示文稿當(dāng)前第1頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)1（優(yōu)選）線性規(guī)劃解概念和單純形法當(dāng)前第2頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)2解的解析Maxz=2x1

+3x2+0x3+0x4+0x5s.t.2x1+2x2

+

x3

=12(A)4x1+x4

=16(B)5x2

+x5=15(C)

x1,x2，x3，x4，x5

≥0(D,E)當(dāng)前第3頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)3解的解析可行解滿足上述約束條件(A)、(B)、（C)的解x=(x1,x2，x3，x4，x5

)T稱為線性規(guī)劃問題的可行解，全部可行解的集合成為可行域。最優(yōu)解

是目標(biāo)函數(shù)z=15達(dá)到最大值的可行解x=(3

,3，0，4，0)T成為最優(yōu)解。當(dāng)前第4頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)4解的解析基設(shè)A為約束方程組3*5階系數(shù)矩陣

P1

P2

P3

P4

P5

22100A=4001005001設(shè)B=(P3

P4

P5)當(dāng)前第5頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)5A中其秩為3,B是A矩陣中的一個(gè)3階的滿秩矩陣,稱B是線性規(guī)劃問題的一個(gè)基，B中的每一個(gè)列向量(如P3

P4

P5)稱為基向量，與基向量對(duì)應(yīng)的變量稱為基變量，線性規(guī)劃中除基變量以外的其他變量稱為非基變量。當(dāng)前第6頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)6解的解析基解在約束方程組中，令所有非基變量為0,又因?yàn)橛蠦行列式不為0，由各約束方程可解出各基變量的唯一解。將這個(gè)解加上非基變量取0的值稱為線性規(guī)劃問題的基解，顯然，在基解中變量取非零值的個(gè)數(shù)不大于方程數(shù)，基解的總數(shù)不超過20個(gè)。當(dāng)前第7頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)7解的解析基可行解滿足變量非負(fù)約束條件的基解稱為基可行解?？尚谢鶎?duì)應(yīng)與基可行解的基成為可行基。當(dāng)前第8頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)8(回顧)例2.1問題：工廠應(yīng)如何安排生產(chǎn)可獲得最大的總利潤(rùn)？用圖解法求解。解：設(shè)變量xi為第i種（甲、乙）產(chǎn)品的生產(chǎn)件數(shù)（i＝1，2）。根據(jù)前面分析，可以建立如下的線性規(guī)劃模型：Maxz=1500x1+2500x2s.t.3x1+2x2≤65(A)2x1+x2≤40(B)3x2≤75(C)

x1,x2≥0(D,E)當(dāng)前第9頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)9

圖解法求解線性規(guī)劃102030405010203040OZ=0Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)當(dāng)前第10頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)10

(線性規(guī)劃的基、基本解與基本可行解)

在一般情況下，由于圖解法無法解決三個(gè)變量以上的線性規(guī)劃問題，對(duì)于n個(gè)變量的線性規(guī)劃問題，我們必須用解方程的辦法來求得可行域的極點(diǎn)。再來進(jìn)一步考察前例。例2.8把例2.1的線性規(guī)劃模型標(biāo)準(zhǔn)化，引入松馳變量x3，x4，x5

≥0，得到當(dāng)前第11頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)11Maxz=1500x1

+2500x2

s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75

x1

,x2

,x3,x4

,x5

≥0可見：等式約束條件的系數(shù)矩陣為當(dāng)前第12頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)12從其中取出不同的三列出來，有C53=10種取法當(dāng)前第13頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)13其中B1對(duì)應(yīng)的基變量為x1,x2,x3，非基變量為x4,x5

令非基變量x4=0,x5=0，則得對(duì)應(yīng)方程組3x1+2x2+x3=652x1+x2=403x2=75得對(duì)應(yīng)基本解該10個(gè)方陣中除B4外，其余均為滿秩矩陣，故均為線性規(guī)劃的基。x(1)=(7.5,25,-7.5,0,0)T類似，可得所有基本解為當(dāng)前第14頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)14X(3）=(15,10,0,0,45)TX(2)=(5,25,0,5,0)TX(9)=(0,32.5,0,7.5,-22.5)TX(6）=(65/3,0,0,-10/3,75)TX(1)=(7.5,25,-7.5,0,0)TX(8)=(0,40,-15,0,-45)T

X(5）=(20,0,5,0,75)T

X(10)=(0,0,65,40,75)T

X(7）=(0,25,15,15,0)T不是可行解是可行解,對(duì)應(yīng)頂點(diǎn)A是可行解,對(duì)應(yīng)頂點(diǎn)B是可行解,對(duì)應(yīng)頂點(diǎn)C不是可行解不是可行解不是可行解是可行解,對(duì)應(yīng)頂點(diǎn)D是可行解,對(duì)應(yīng)頂點(diǎn)E當(dāng)前第15頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)15

圖解法求解線性規(guī)劃102030405010203040OZ=0Z=25000A（5,25）B（15,10）C（20,0）D（0,25）E(0,0)當(dāng)前第16頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)16上圖各約束直線的交點(diǎn)是由以下方法得到：在標(biāo)準(zhǔn)化的等式約束中，令其中的非基變量為零，求出其他基變量的唯一解，得LP問題的基解

(x1,x2,x3,x4,x5)T,若其分量全為非負(fù)，則該解稱為基可行解,對(duì)應(yīng)于線性規(guī)劃可行域的一個(gè)極點(diǎn)（頂點(diǎn)）；若基解中至少有一個(gè)分量為負(fù)值則該交點(diǎn)不是可行域的極點(diǎn)。2.線性規(guī)劃解的概念

當(dāng)前第17頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)17下面討論線性規(guī)劃標(biāo)準(zhǔn)形式的基、基本解、基本可行解的概念。考慮線性規(guī)劃標(biāo)準(zhǔn)形式的約束條件：

Ax=b，x≥0其中A為m×n的矩陣，n>m，秩(A)

=m，b

Rm

。在約束等式中，令n維空間的解向量：

x=(x1，x2，…，xn)T2.線性規(guī)劃解的概念

（1）線性規(guī)劃的基：對(duì)于線性規(guī)劃的約束條件

Ax=b，x≥0

當(dāng)前第18頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)18設(shè)B是A矩陣中的一個(gè)非奇異（滿秩）的m×m子矩陣，則稱B為線性規(guī)劃的一個(gè)基。用前文的記號(hào)，A=(p1，p2，…，pn)，其中pj=(a1j，a2j，…，amj)T

Rm

，任取A中的m個(gè)線性無關(guān)列向量pj

Rm

構(gòu)成矩陣B=(pj1，pj2，…，pjm)。那么B為線性規(guī)劃的一個(gè)基。我們稱對(duì)應(yīng)于基B的變量xj1，xj2，…，xjm為基變量；而其他變量稱為非基變量。2.線性規(guī)劃解的概念

當(dāng)前第19頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)19可以用矩陣來描述這些概念。設(shè)B是線性規(guī)劃的一個(gè)基，則A可以表示為

A=[B,N

]

x也可相應(yīng)地分成

xBx=xN其中xB為m維列向量，它的各分量稱為基變量，與基B的列向量對(duì)應(yīng)；xN為n-m列向量，它的各分量稱為非基變量，與非基矩陣N的列向量對(duì)應(yīng)。

2.線性規(guī)劃解的概念當(dāng)前第20頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)20（2）線性規(guī)劃問題的基本解、基本可行解和可行基：對(duì)于線性規(guī)劃問題，設(shè)矩陣B=(pj1，pj2，…，pjm)為一個(gè)基，令所有非基變量為零，可以得到m個(gè)關(guān)于基變量xj1，xj2，…，xjm的線性方程，解這個(gè)線性方程組得到基變量的值。我們稱這個(gè)解為一個(gè)基本解；若得到的基變量的值均非負(fù)，則稱為基本可行解，同時(shí)稱這個(gè)基B為可行基。2.線性規(guī)劃解的概念

當(dāng)前第21頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)21矩陣描述為，對(duì)于線性規(guī)劃的解

xB

B-1b

x==

xN0

稱為線性規(guī)劃與基B對(duì)應(yīng)的基本解。若其中B-1b0，則稱以上的基本解為一基本可行解，相應(yīng)的基B稱為可行基。

2.線性規(guī)劃解的概念當(dāng)前第22頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)22

我們可以證明以下結(jié)論：線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。這個(gè)結(jié)論被稱為線性規(guī)劃的基本定理，它的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。2.線性規(guī)劃解的概念

當(dāng)前第23頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)23利用求解線性規(guī)劃問題基本可行解（極點(diǎn)）的方法來求解較大規(guī)模的問題是不可行的。單純形法的基本思路是有選擇地取基本可行解，即是從可行域的一個(gè)極點(diǎn)出發(fā)，沿著可行域的邊界移到另一個(gè)相鄰的極點(diǎn)（要求新極點(diǎn)的目標(biāo)函數(shù)值不比原目標(biāo)函數(shù)值差）。

3.單純形法當(dāng)前第24頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)243.單純形法初始基本可行解是否最優(yōu)解或無限最優(yōu)解?結(jié)束沿邊界找新的基本可行解NY單純形法的基本過程當(dāng)前第25頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)25需要解決的三個(gè)問題：（1）如何找到一個(gè)初始的基本可行解。（2）如何判別當(dāng)前的基本可行解是否已達(dá)到了最優(yōu)解。（3）若當(dāng)前解不是最優(yōu)解，如何去尋找一個(gè)改善了的基本可行解。單純型原理是由美國(guó)數(shù)學(xué)家丹齊格（G.B.Danzig）在1947年為研究美國(guó)空軍資源的優(yōu)化配置時(shí)提出的一種方法。當(dāng)前第26頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)26下面舉例說明單純型法的思想maxz=2x1+x2

(4.1)maxz=2x1+x2例：maxz=2x1+x2當(dāng)前第27頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)27將上式標(biāo)準(zhǔn)化為為基變量，將基變量用非基變量表示為

取令非基變量x1=0,令非基變量等于0，得到一個(gè)基本可行解當(dāng)前第28頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)28我們想讓x1從非基變量轉(zhuǎn)為基變量，今后我們稱之為進(jìn)基。因基變量只有三個(gè)，因此必須從原有的基x3，x4，x5，中選一個(gè)離開基轉(zhuǎn)為非基變量。下解決兩個(gè)問題：1)x1應(yīng)取多大的值？2)x1進(jìn)基，x3，x4，x5那一個(gè)出基？現(xiàn)在，還是非基變量，仍取零值。

現(xiàn)在，還是非基變量，仍取零值。

x1要增加，x3，x4，x5

≥0。

==4=最小比值規(guī)則當(dāng)前第29頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)29把以上的運(yùn)算制成一張表格，稱單純型表。

0

21000

基b

0150240505100[6]201011001

5

21000X1進(jìn)基，x4出基。當(dāng)前第30頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)30

0

21000

基b

01524010510012/601/6004/60-1/61

3123/2

01/30-1/30想一想：下一步應(yīng)選哪個(gè)變量進(jìn)基，又選哪個(gè)變量出基呢？下一步的單純形表又怎樣列呢？當(dāng)前第31頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)31

0

21000

基b0

15/227/213/2

0015/4-15/21001/4-1/2010-1/43/2

000-1/4-1/2

由上表得該LP問題的最優(yōu)解為：2X=(7/2,3/2,15/2,0,0)T,maxz=17/2當(dāng)前第32頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)32考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題：Maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2

...

am1x1+am2x2+…+amnxn

=bm

x1,x2,…,

xn

≥0

x1

c1

b1

a11a12..a1n

x2

c2

b2

a21a22..a2nX=.C=

.

B=.A=

.........

xn

cn

bn

am1am2..amn

3.單純形法Maxz=CXs.t.AX=bX≥0當(dāng)前第33頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)33這里，矩陣A表示為：A=(p1，p2，…，pn)，若找到一個(gè)可行基，無防設(shè)B=(p1，p2，…，pm)，則m個(gè)基變量為x1,x2,…,xm，n-m個(gè)非基變量為xm+1，xm+2，…，xn。通過運(yùn)算，所有的基變量都可以用非基變量來表示：3.單純形法當(dāng)前第34頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)34

x1=b’1-（a’1m+1xm+1+a’1m+2xm+2+…+a’1nxn）

x2=b’2-（a’2m+1xm+1+a’2m+2xm+2+…+a’2nxn）(2-11).`..

xm=b’m-（a’mm+1xm+1+a’mm+2xm+2+…+a’mnxn）

把它們代入目標(biāo)函數(shù)，得

z=z’+m+1xm+1+m+2xm+2+…+nxn

(2-12)其中

j=cj-（c1a’1j+c2a’2j+…+cma’mj）

我們把由非基變量表示的目標(biāo)函數(shù)形式稱為基B相應(yīng)的目標(biāo)函數(shù)形式。3.單純形法當(dāng)前第35頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)353、單純形法表格單純形法考慮：bi>0i=1,…,m

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

≤b1

a21x1+a22x2+…+a2nxn

≤b2…………

am1x1+am2x2+…+amnxn

≤bm

x1，x2，…，xn≥0當(dāng)前第36頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)363、單純形法加入松弛變量：Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn+xn+1=b1

a21x1+a22x2+…+a2nxn+xn+2=b2…………

am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m≥0當(dāng)前第37頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)37顯然，xj=0j=1,…,n;

xn+i=bii=1,…,m是基本可行解

對(duì)應(yīng)的基是單位矩陣。以下是初始單純形表：

mm其中：f=∑cn+ibi

j=cj-∑cn+iaij為檢驗(yàn)數(shù)cn+i

=0i=1,…,m

i=1i=1an+i,i=1,an+i,j=0(j≠i)i,j=1,…,m為約束方程系數(shù)3、單純形法b價(jià)值系數(shù)方程組右側(cè)常數(shù)比率計(jì)算值當(dāng)前第38頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)383、單純形法表格單純形法的計(jì)算步驟（1）找出初始可行基，確定初始基可行解，建立初始單純形表；（2）檢驗(yàn)各非基變量的檢驗(yàn)數(shù)，若所有σj≤0，則已達(dá)最優(yōu)解，停止計(jì)算；否則，轉(zhuǎn)入下一步；（3）若有某個(gè)σj>0，其對(duì)應(yīng)系數(shù)列向量≤0，則此問題是無界解，停止計(jì)算；否則，轉(zhuǎn)入下一步；（4）決定換入和換出基變量；（5）用矩陣的初等行變換法將xk所對(duì)應(yīng)的列向量變換為（0，0，…，1，…，0）T，換入新的基變量，得到新的單純形表，返回步驟（2）。當(dāng)前第39頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)39例2.10：用單純形法的基本思路解例2.8的線性規(guī)劃問題

Maxz=1500x1

+2500x2

s.t.3x1

+2x2

+x3

=652x1

+x2

+x4=403x2

+x5

=75

x1,x2,x3,x4,x5

≥03.單純形法當(dāng)前第40頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)40解列出單純形表并進(jìn)行單純形變換

最優(yōu)解x1=5x2=25x4=5（松弛標(biāo)量，表示B設(shè)備有5個(gè)機(jī)時(shí)的剩余）最優(yōu)值z(mì)*=700003、單純形法當(dāng)前第41頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)41注意：?jiǎn)渭冃畏ㄖ校?、每一步運(yùn)算只能用矩陣初等行變換；2、表中第三列（b列）的數(shù)總應(yīng)保持非負(fù)（≥0）；3、當(dāng)所有檢驗(yàn)數(shù)均非正（≤0）時(shí)，得到最優(yōu)單純形表。當(dāng)所有非基變量的檢驗(yàn)數(shù)均<0,則相應(yīng)的最優(yōu)解是唯一的。3、單純形法

當(dāng)前第42頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)424.單純形法的進(jìn)一步討論4.1大M法：引入人工變量xn+i

≥0（i=1,…,m）及充分大正數(shù)M。得到：Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m

s.t.

a11x1+a12x2+…+a1nxn

+xn+1

=b1a21x1+a22x2+…+a2nxn+xn+2=b2...am1x1+am2x2+…+amnxn+xn+m=bm

x1，x2，…，xn，xn+1，…，xn+m

≥0對(duì)于規(guī)模較大的問題，用試算的方法取得初始基可行解很困難，必須有一個(gè)初始可行基的系統(tǒng)化方法。當(dāng)前第43頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)43顯然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m

是基本可行解。對(duì)應(yīng)的基是單位矩陣。結(jié)論：由于

Max

z=c1x1+c2x2+…+cnxn-Mxn+1-…-Mxn+m則若得到的最優(yōu)解滿足

xn+i=0

i=1,…,m則是原問題的最優(yōu)解；否則，原問題無可行解。4.單純形法的進(jìn)一步討論當(dāng)前第44頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)44例2.11：（LP）Maxz=5x1

+2x2

+3x3

-x4

s.t.x1+

2x2+

3x3=152x1

+x2

+5x3=20

x1

+2x2

+4x3

+x4

=26

x1

,x2

,x3

,x4

≥04.單純形法的進(jìn)一步討論當(dāng)前第45頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)45

Max

z=5x1+2x2+3x3-x4-Mx5-Mx6

s.t.

x1+2x2+3x3+x5

=152x1+x2+5x3+x6=20

x1+2x2+4x3+x4

=26

x1,x2,x3,x4,x5,x6

≥0大M法問題(LP-M）4.單純形法的進(jìn)一步討論當(dāng)前第46頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)46大M法

（LP-M）

得到最優(yōu)解：(25/3，10/3，0，11)T

最優(yōu)目標(biāo)值：112/34.單純形法的進(jìn)一步討論當(dāng)前第47頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)47

4.2

兩階段法：

引入人工變量xn+i

≥0，i=1,…,m；

構(gòu)造:Maxz=-xn+1

-xn+2

-…-xn+m

s.t.

a11x1+a12x2+…+a1nxn+xn+1

=b1

a21x1+a22x2+…+a2nxn+xn+2

=b2

...

am1x1+am2x2+…+amnxn+xn+m

=bmx1,x2...

xn,xn+1,…,xn+m

≥04.單純形法的進(jìn)一步討論當(dāng)前第48頁(yè)\共有55頁(yè)\編于星期二\13點(diǎn)48第一階段求解上述問題：顯然，xj=0j=1,…,n;

xn+i=bi

i=1,…,m是基本可行解,它對(duì)應(yīng)的基是單位矩陣。結(jié)論：若得到的最優(yōu)解滿足xn+i=0

i=1,…,m則是原問題的基本可行解;否則，原問題無可行解。得到原問題的基本可行解后，第二階段求解原問題。當(dāng)前第49頁(yè)\共有55頁(yè)\編于星期二\