線(xiàn)性規(guī)劃的圖解法課件

第三節(jié)兩個(gè)變量問(wèn)題的圖解法線(xiàn)性規(guī)劃問(wèn)題的求解方法一般有兩種方法圖解法單純形法兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況——

只有兩個(gè)決策變量的線(xiàn)性規(guī)劃問(wèn)題，這時(shí)可以通過(guò)圖解的方法來(lái)求解。圖解法具有簡(jiǎn)單、直觀(guān)、便于初學(xué)者窺探線(xiàn)性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。1可編輯課件PPT第三節(jié)兩個(gè)變量問(wèn)題的圖解法解（參見(jiàn)教材P21）解（參見(jiàn)教材P22）2可編輯課件PPT第三節(jié)兩個(gè)變量問(wèn)題的圖解法解（參見(jiàn)教材P23）解（參見(jiàn)教材P23）3可編輯課件PPT圖解法maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0練習(xí)：

用圖解法求解線(xiàn)性規(guī)劃問(wèn)題4可編輯課件PPT圖解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

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

maxZ=17.2可行域maxZ=2X1+X25可編輯課件PPT圖解法若maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

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

藍(lán)色線(xiàn)段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值maxZ=34.2是唯一的?？尚杏?可編輯課件PPT圖解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此點(diǎn)是唯一最優(yōu)解7可編輯課件PPT圖解法246x1x2246無(wú)界解(無(wú)最優(yōu)解)maxZ=x1+2x2練習(xí)：x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ8可編輯課件PPTx1x2O10203040102030405050無(wú)可行解(即無(wú)最優(yōu)解)maxZ=3x1+4x2練習(xí)：9可編輯課件PPT線(xiàn)性規(guī)劃的圖解法圖解法的基本步驟

X*=(4,6)Tz*=42

1°畫(huà)出可行域圖形

2°畫(huà)出目標(biāo)函數(shù)的等值線(xiàn)及其法線(xiàn)

3°確定最優(yōu)點(diǎn)max

z=3x1+5x2

x1

≤

8

2

x2≤

123x1+

4

x2≤

36

x1,

x2

≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42邊界方程10可編輯課件PPT線(xiàn)性規(guī)劃的圖解法幾點(diǎn)說(shuō)明實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn):(1)若函數(shù)約束原型就是等式,則其代表的區(qū)域僅為一直線(xiàn),而且問(wèn)題的整個(gè)可行域R(若存在的話(huà))也必然在此直線(xiàn)上。(2)在畫(huà)目標(biāo)函數(shù)等值線(xiàn)時(shí)只須畫(huà)兩條就能確定其法線(xiàn)方向,為此,

只須賦給z

兩個(gè)適當(dāng)?shù)闹怠?3)在找出最優(yōu)點(diǎn)后,關(guān)于其坐標(biāo)值有兩種確定方法:①

在圖上觀(guān)測(cè)最優(yōu)點(diǎn)坐標(biāo)值②

通過(guò)解方程組得出最優(yōu)點(diǎn)坐標(biāo)值11可編輯課件PPT圖解法

學(xué)習(xí)要點(diǎn)：

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

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

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

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

(3)目標(biāo)函數(shù)的直線(xiàn)怎樣平行移動(dòng)12可編輯課件PPT線(xiàn)性規(guī)劃的圖解法幾種可能結(jié)果一、唯一解

如例1、例2都只有一個(gè)最優(yōu)點(diǎn)，屬于唯一解的情形。s.t.max

z=3x1+4x2

x1≤82x2≤123x1+4x2≤

36

x1，x2≥0

二、多重解z=12z*=36線(xiàn)段BC上無(wú)窮多個(gè)點(diǎn)均為最優(yōu)解。O(0,0)x1x2R

D(0,6)C(4,6)B(8,3)A(8,0)13可編輯課件PPT線(xiàn)性規(guī)劃的圖解法x1x2z