線性規(guī)劃問題的圖解法

線性規(guī)劃問題的圖解法第1頁，共50頁，2023年，2月20日，星期二線性規(guī)劃問題的幾何意義第2頁，共50頁，2023年，2月20日，星期二凸集凹集第3頁，共50頁，2023年，2月20日，星期二

頂點:若K是凸集，X∈K；若X不能用不同的兩點的線性組合表示為：

則X為頂點.

線性規(guī)劃問題的幾何意義第4頁，共50頁，2023年，2月20日，星期二

凸組合：

Xn=2，k=3線性規(guī)劃問題的幾何意義第5頁，共50頁，2023年，2月20日，星期二標(biāo)準(zhǔn)型可行解:滿足AX=b,X>=0的解X稱為線性規(guī)劃問題的可行解。所有可行解的集合稱為可行域。最優(yōu)解：使Z=CX達(dá)到最大值的可行解稱為最優(yōu)解。等值線：目標(biāo)函數(shù)為常數(shù)的光滑連續(xù)曲線。第6頁，共50頁，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

04x1

164x2

16圖解法第7頁，共50頁，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

12可行域圖解法第8頁，共50頁，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

16可行域BCDEA圖解法第9頁，共50頁，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEA2x1+3x2=6圖解法第10頁，共50頁，2023年，2月20日，星期二9—8—7—6—5—4—3—2—1—0x2

目標(biāo)函數(shù)MaxZ=2x1+3x2

約束條件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEA最優(yōu)解(4,2)圖解法第11頁，共50頁，2023年，2月20日，星期二圖解法求解步驟1.由全部約束條件作圖求出可行域；2.作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動方向；3.平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。第12頁，共50頁，2023年，2月20日，星期二圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤11.4X1-1.9X2≥-3.8X1，X2≥0例1用圖解法求解線性規(guī)劃問題第13頁，共50頁，2023年，2月20日，星期二圖解法---唯一最優(yōu)解

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=11.4(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此點是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值

maxZ=17.2可行域maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤11.4X1-1.9X2≥-3.8X1，X2≥0第14頁，共50頁，2023年，2月20日，星期二圖解法---唯一最優(yōu)解

minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=11.4(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點是唯一最優(yōu)解第15頁，共50頁，2023年，2月20日，星期二圖解法---無窮多最優(yōu)解maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=11.4(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）34.2=3X1+5.7X2

藍(lán)色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的。可行域第16頁，共50頁，2023年，2月20日，星期二圖解法---無界解246x1x2246無界解(無最優(yōu)解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ第17頁，共50頁，2023年，2月20日，星期二x1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2例1.7圖解法---無可行解第18頁，共50頁，2023年，2月20日，星期二小結(jié)

第19頁，共50頁，2023年，2月20日，星期二圖解法

學(xué)習(xí)要點：

1.通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）

2.作圖的關(guān)鍵有三點：

(1)可行解區(qū)域要畫正確

(2)目標(biāo)函數(shù)增加的方向不能畫錯

(3)目標(biāo)函數(shù)的直線怎樣平行移動第20頁，共50頁，2023年，2月20日，星期二圖解法的幾點結(jié)論:

（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。解題思路：找出凸集的頂點，計算其目標(biāo)函數(shù)值，比較即得。第21頁，共50頁，2023年，2月20日，星期二練習(xí)：設(shè)式中變量滿足下列條件①xyO求的最大值和最小值2x+y=0第22頁，共50頁，2023年，2月20日，星期二練習(xí)：設(shè)式中變量滿足下列條件①x-4y+3=03x+5y-25=0x=1xyO求的最大值和最小值2x+y=0A(5,2)B(1,1)第23頁，共50頁，2023年，2月20日，星期二單純形法基本原理定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）第24頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟單純形法的思路找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束第25頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟單純形表第26頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟例1.8用單純形法求下列線性規(guī)劃的最優(yōu)解解：1）將問題化為標(biāo)準(zhǔn)型，加入松馳變量x3、x4則標(biāo)準(zhǔn)型為:第27頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟2）求出線性規(guī)劃的初始基可行解，列出初始單純形表。cj3400θicB基bx1x2x3x40x34021100x43013013400檢驗數(shù)第28頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟3）進(jìn)行最優(yōu)性檢驗如果表中所有檢驗數(shù)，則表中的基可行解就是問題的最優(yōu)解，計算停止。否則繼續(xù)下一步。4）從一個基可行解轉(zhuǎn)換到另一個目標(biāo)值更大的基可行解，列出新的單純形表確定換入基的變量。選擇，對應(yīng)的變量xj作為換入變量，當(dāng)有一個以上檢驗數(shù)大于0時，一般選擇最大的一個檢驗數(shù)，即：，其對應(yīng)的xk作為換入變量。確定換出變量。根據(jù)下式計算并選擇θ

，選最小的θ對應(yīng)基變量作為換出變量。 第29頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟用換入變量xk替換基變量中的換出變量，得到一個新的基。對應(yīng)新的基可以找出一個新的基可行解，并相應(yīng)地可以畫出一個新的單純形表。5）重復(fù)3）、4）步直到計算結(jié)束為止。 第30頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟cj3400θicB基變量bx1x2x3x40x34021100x430130134000x34x23x14x2換入列bi/ai2，ai2>04010換出行將3化為15/311801/301/3101－1/3303005/30－4/3乘以1/3后得到103/5－1/51801－1/52/5400－1－1第31頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟例1.9用單純形法求解解：將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：不難看出x4、x5可作為初始基變量，列單純形表計算。第32頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟cj12100θicB基變量bx1x2x3x4x50x4152-32100x5201/31501121000x42x220－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第33頁，共50頁，2023年，2月20日，星期二單純形法的計算步驟

學(xué)習(xí)要點：

1.線性規(guī)劃解的概念以及3個基本定理

2.熟練掌握單純形法的解題思路及求解步驟第34頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法人工變量法： 前面討論了在標(biāo)準(zhǔn)型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。第35頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法例1.10用大M法解下列線性規(guī)劃解：首先將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式系數(shù)矩陣中不存在單位矩陣，無法建立初始單純形表。第36頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法故人為添加兩個單位向量，得到人工變量單純形法數(shù)學(xué)模型：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結(jié)果見下表。第37頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi0x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第38頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法

解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。4）無可行解的判斷：當(dāng)用大M單純形法計算得到最優(yōu)解并且存在Ri>0時，則表明原線性規(guī)劃無可行解。5）退化解的判別：存在某個基變量為零的基本可行解。第39頁，共50頁，2023年，2月20日，星期二單純形法的進(jìn)一步討論－人工變量法單純性法小結(jié):建立模型個數(shù)取值右端項等式或不等式極大或極小新加變量系數(shù)兩個三個以上xj≥0xj無約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa求解圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj’

=-xj不處理約束條件兩端同乘以-1加松弛變量xs加入人工變量xa減去xs加入xa不處理令z′=-ZminZ=－maxz′0-M第40頁，共50頁，2023年，2月20日，星期二A第41頁，共50頁，2023年，2月20日，星期二

線性規(guī)劃模型的應(yīng)用

一般而言，一個經(jīng)濟(jì)、管理問題凡是滿足以下條件時，才能建立線性規(guī)劃模型。

要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)存在著多種方案要求達(dá)到的目標(biāo)是在一定條件下實現(xiàn)的，這些約束可用線性等式或不等式描述第42頁，共50頁，2023年，2月20日，星期二

線性規(guī)劃在管理中的應(yīng)用

人力資源分配問題例1.11某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機(jī)和乘務(wù)人員人數(shù)如下表所示：班次時間所需人員16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030設(shè)司機(jī)和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作8小時，問該公交線路應(yīng)怎樣安排司機(jī)和乘務(wù)人員，即能滿足工作需要，又使配備司機(jī)和乘務(wù)人員的人數(shù)減少?第43頁，共50頁，2023年，2月20日，星期二

線性規(guī)劃在管理中的應(yīng)用解：設(shè)xi表示第i班次時開始上班的司機(jī)和乘務(wù)人員人數(shù)。此問題最優(yōu)解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司機(jī)和乘務(wù)員150人。第44頁，共50頁，2023年，2月20日，星期二

線性規(guī)劃在管理中的應(yīng)用2.