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

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

只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。1可編輯課件PPT第三節(jié)兩個(gè)變量問題的圖解法解（參見教材P21）解（參見教材P22）2可編輯課件PPT第三節(jié)兩個(gè)變量問題的圖解法解（參見教材P23）解（參見教材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í)：

用圖解法求解線性規(guī)劃問題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)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無窮多最優(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無界解(無最優(yōu)解)maxZ=x1+2x2練習(xí)：x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ8可編輯課件PPTx1x2O10203040102030405050無可行解(即無最優(yōu)解)maxZ=3x1+4x2練習(xí)：9可編輯課件PPT線性規(guī)劃的圖解法圖解法的基本步驟

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

1°畫出可行域圖形

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

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線性規(guī)劃的圖解法幾點(diǎn)說明實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn):(1)若函數(shù)約束原型就是等式,則其代表的區(qū)域僅為一直線,而且問題的整個(gè)可行域R(若存在的話)也必然在此直線上。(2)在畫目標(biāo)函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向,為此,

只須賦給z

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

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

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

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

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

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

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

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

(3)目標(biāo)函數(shù)的直線怎樣平行移動12可編輯課件PPT線性規(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線段BC上無窮多個(gè)點(diǎn)均為最優(yōu)解。O(0,0)x1x2R

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