管理運(yùn)籌學(xué)02線性規(guī)劃課件

1.線性規(guī)劃問題及其數(shù)學(xué)模型2.線性規(guī)劃的圖解法3.線性規(guī)劃問題的標(biāo)準(zhǔn)形式4.線性規(guī)劃的解集特征5.線性規(guī)劃的單純形法6.單純形法的進(jìn)一步討論第二章線性規(guī)劃2/6/20231線性規(guī)劃問題及其數(shù)學(xué)模型

資源合理利用問題：第5頁例2-1質(zhì)量檢驗(yàn)問題：第6頁例2-2線性規(guī)劃數(shù)學(xué)模型的一般形式2/6/20232資源合理利用問題：第5頁例2-1

1.決策變量：x1和x22.目標(biāo)函數(shù)：max(2x1+3x2)3.約束條件：10

x1+20x2804x1166x218

x1，x202/6/20233線性規(guī)劃數(shù)學(xué)模型的一般形式1.決策變量是非負(fù)變量；2.目標(biāo)函數(shù)是線性函數(shù)；3.約束條件是線性等式或不等式組。一般形式為：

max(min)(c1

x1+c2

x2+…+

cnxn

)

a11

x1+a12

x2+…+a1nxn

(=,)b1

a21

x1+a22

x2+…+a2n

xn

(=,)b2

……

am1

x1+am2

x2+…+amnxn

(=,)bm

x1，

x2，

…，xn

0

2/6/20235

線性規(guī)劃的圖解法1.局限性：只能求解具有兩個(gè)變量的線性規(guī)劃問題。2.學(xué)習(xí)目的：圖解法只能求解具有兩個(gè)決策變量的線性規(guī)劃問題，其應(yīng)用具有很大的局限性，因此學(xué)習(xí)圖解法的目的并非是要掌握一種線性規(guī)劃問題的求解方法，而是要通過圖解法揭示線性規(guī)劃問題的內(nèi)在規(guī)律，為學(xué)習(xí)線性規(guī)劃問題的一般算法（單純形法）奠定基礎(chǔ)。3.線性規(guī)劃有關(guān)解的幾個(gè)概念4.圖解法的基本步驟5.圖解法所反映出的一般結(jié)論2/6/20236線性規(guī)劃有關(guān)解的幾個(gè)概念1.可行解：滿足約束條件的一組決策變量的取值；2.可行域：可行解所構(gòu)成的集合；3.最優(yōu)解：使目標(biāo)函數(shù)達(dá)到極值的可行解；4.最優(yōu)值：與最優(yōu)解相對應(yīng)的目標(biāo)函數(shù)的取值。2/6/20237用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/20239用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/202310用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/202311用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/202313用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/202314用圖解法求解例2-1x1x2

4

3

2

1

0123456782/6/202315圖解法所反應(yīng)出的一般結(jié)論1.線性規(guī)劃問題的可行域是凸多邊形；2.如果線性規(guī)劃問題有最優(yōu)解，其最優(yōu)解一定可以在其可行域的頂點(diǎn)上得到，而不會在可行域的內(nèi)部；3.如果線性規(guī)劃問題在其可行域的兩個(gè)頂點(diǎn)上得到最優(yōu)解，那么兩頂點(diǎn)連線上的所有點(diǎn)均為最優(yōu)解點(diǎn)；4.線性規(guī)劃問題的解可能有四種情況：唯一最優(yōu)解；無窮多最優(yōu)解；無界解和無可行解。2/6/202317線形規(guī)劃問題的標(biāo)準(zhǔn)形式1.標(biāo)準(zhǔn)形式的基本條件：（1）決策變量非負(fù)；（2）目標(biāo)函數(shù)極大化（或極小化）；（3）約束條件為嚴(yán)格等式，且右端項(xiàng)非負(fù)。2.標(biāo)準(zhǔn)形式的表示：

代數(shù)式；和式；向量式；矩陣式

3.標(biāo)準(zhǔn)形式的轉(zhuǎn)化2/6/202318線性規(guī)劃的標(biāo)準(zhǔn)型：代數(shù)式minz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2………

am1x1+am2x2+…+amnxn=bm

xj

≥0j=1,2,…,n2/6/202319線性規(guī)劃的標(biāo)準(zhǔn)型：向量式minz=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,n

C=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)Tnj=12/6/202321線性規(guī)劃的標(biāo)準(zhǔn)型：矩陣式

minz=CX

AX=b，X

≥0，

b≥0

其中：

b=(b1,b2,…,bm)T

a11

a12….a1n

A=a21

a22…a2n………

am1

am2…amn2/6/202322標(biāo)準(zhǔn)形式的轉(zhuǎn)化1.無約束變量x的處理：

x=y-z,其中y,z02.負(fù)數(shù)變量x的處理：

x=-y,其中y03.目標(biāo)函數(shù)極小化的處理：

MinCX=-Max(-CX)4.非等式約束條件的處理：加松弛變量或減剩余變量5.右端項(xiàng)為負(fù)：兩端同乘“-1”2/6/202323線性規(guī)劃基與解的概念1.基、基列、基變量和非基變量(1)基：MaxCX,AX=b,X0,b0Amn其秩為m，B是Amn中的一個(gè)mm階滿秩矩陣，則稱B是線性規(guī)劃問題的一個(gè)基(2)基列：基B中所包含的m個(gè)列向量(3)基變量：基列所對應(yīng)的決策變量(4)非基變量：基變量以外的決策變量2.基解、基可行解、可行基(1)基解：令所有的非基變量為零，所求得的一組解(2)基可行解：所有分量均為非負(fù)的基解(3)可行基：與基可行解所對應(yīng)的基2/6/202325凸集的概念與解集的基本定理1.凸集的概念：設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)k，X(2)k的連線上的一切點(diǎn)

X(1)+(1-)X(2)k，(0<<1)則稱k為凸集。2.解集的基本定理：(1)若線性規(guī)劃問題存在可行域，則其可行域是凸集；(2)線性規(guī)劃問題的基可行解對應(yīng)其可行域的頂點(diǎn)；(3)若線性規(guī)劃問題存在最優(yōu)解，則其最優(yōu)解一定能在基可行解中找到。2/6/202326第12頁例2-6Maxz=2x1+3x210x1+20x2+x3=804x1+x4=16

6x2+x5=18x1，x2，x3，x4，x50B=(p3，p4，p5)X(0)=(0，0，80，16，18)TZ(0)=0，z=2x1+3x2尋找相鄰的基可行解2/6/202329例2-6Max(2，3)=3x2入基Min(80/20，18/6)=3x5出基B=(p3，p4，p2)10x1+x3-10/3x5=204x1+x4=16x2+1/6x5=3X(1)=(0，3，20，16，0)TZ(1)=9，z=9+2x1-1/2x52/6/202330例2-6Max(2)=2x1入基Min(20/10，16/4)=2x3出基B=(p1，p4，p2)x1+1/10x3-1/3x5=2-2/5x3+x4+4/3x5=8x2+1/6x5=3X(2)=(2，3，0，8，0)TZ(2)=13，z=13-1/5x3+1/6x52/6/202331例2-6Max(1/6)=1/6x5入基Min(8/(4/3)，3/(1/6))=6x4出基B=(p1，p5，p2)x1+1/4x4=4-3/10x3+3/4x4+x5=6x2+1/20x3-1/8x4=2X(3)=(4，2，0，0，6)TZ(3)=14，z=14-9/10

x3

-1/8x42/6/202332最優(yōu)性檢驗(yàn)與解的判別2/6/202333單純形表2/6/202334單純形法的基本步驟1.數(shù)學(xué)模型標(biāo)準(zhǔn)化、正規(guī)化；2.建立初始單純形表；3.計(jì)算檢驗(yàn)數(shù)并判斷最優(yōu)性，結(jié)束或繼續(xù)；4.確定入基變量和出基變量，5.迭代運(yùn)算；6.重復(fù)3、4、5步，直至結(jié)束。2/6/202335用單純形法求解例2-62/6/202336用單純形法求解例2-62/6/202337用單純形法求解例2-62/6/202338用單純形法求解例2-62/6/202339課上習(xí)題1.Maxz=2x1+4x2+x3+x4x1+3x2

+x48

2x1+x2

6x2

+x3

+x4

6x1

+x2

+x3

9x1~4

02.第17頁例2-103.第19頁例2-112/6/202340單純形法的進(jìn)一步討論1.計(jì)算問題(1)入基變量的選擇(2)解的退化2.人工變量與初始正規(guī)基(1)大M法(2)兩階段法2/6/202341入基變量的選擇入基變量是根據(jù)最大正檢驗(yàn)數(shù)來選擇的，這樣做的目的是為了使目標(biāo)函數(shù)得到最大的增量，因此當(dāng)最大正檢驗(yàn)數(shù)有多個(gè)時(shí)，可主觀地選擇它們中的任意一個(gè)作為入基變量。其實(shí)具有正檢驗(yàn)數(shù)的所有非基變量都可作為入基變量。2/6/202342出基變量的選擇與解的退化1.退化解：部分基變量的值為零的基可行解稱為退化解。2.在選擇出基變量時(shí)，如果最小比值不唯一，可主觀確定出基變量，此時(shí)產(chǎn)生退化解。3.例2/6/202343例Maxz=2x4+(3/2)x6

x1+x4-x5=8

x2+2x4+x6=4

x3+x4+x5+x6=3

x1~602/6/202344例2/6/202345例2/6/202346例2/6/202347例2/6/202348例2/6/202349人工變量與初始正規(guī)基第21頁例2-13:

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x30(1)標(biāo)準(zhǔn)化2/6/202350例2-13的標(biāo)準(zhǔn)化

Minz=-3x1+x2+x3x1-2x2+x3+x4=11-4x1+x2+2x3-x5=3-2x1+x3=1x1~50(2)正規(guī)化2/6/202351例2-13的正規(guī)化人工變量：為構(gòu)造基變量（正規(guī)基）人為加入的變量x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~70初始正規(guī)基B=(p4,p6,p7)=E2/6/202352大M法1.大M法：令人工變量的價(jià)值系數(shù)為“-M”(極大值)或“M”(極小值)的單純形法即稱為大M法；例如：

Minz=-3x1+x2+x3+Mx人1+Mx人2

Maxz=2x1+x2+4x3-Mx人1+Mx人22.例2-13的大M法3.習(xí)題（大M法）2/6/202353用大M法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x3=-1x1，

x2，x302/6/202354用大M法求解例1.13

Minz=-3x1+x2+x3+Mx6+Mx7x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6

=3-2x1+x3+x7

=1x1~702/6/202355用大M法求解例1.132/6/202356用大M法求解例1.132/6/202357用大M法求解例1.132/6/202358用大M法求解例1.132/6/202359習(xí)題（用大M法求解）

Maxz=2x1+4x2+x3x1+x2+x36x1+x2-2x34x1-2x2+x38x1，

x2，x302/6/202360習(xí)題（用大M法求解）

Maxz=2x1+4x2+x3-Mx7x1+x2+x3+x4=6x1+x2-2x3+x5=4x1-2x2+x3-x6+x7

=8x1~702/6/202361習(xí)題（用大M法求解）2/6/202362習(xí)題（用大M法求解）2/6/202363習(xí)題（用大M法求解）2/6/202364兩階段法1.兩階段法：第一階段，在原約束條件下，求所有人工變量和的最小值；第一階段的目的是獲得問題的一個(gè)初始基可行解（人工變量和的最小值為零）或得出問題無可行解（人工變量和的最小值大于零）的結(jié)論；第二階段，去掉人工變量，在原目標(biāo)下從已得到的基可行解開始優(yōu)化。2.例2-13的兩階段法3.習(xí)題（兩階段法）2/6/202365用兩階段法求解例2-13

Minz=-3x1+x2+x3x1-2x2+x311-4x1+x2+2x332x1-x