線性規(guī)劃的圖解法-文檔資料

1、1第三節(jié) 兩個(gè)變量問題的圖解法線性規(guī)劃問題的求解方法線性規(guī)劃問題的求解方法一 般 有兩種方法圖圖 解解 法法單純形法單純形法兩個(gè)變量、直角坐標(biāo)兩個(gè)變量、直角坐標(biāo)三個(gè)變量、立體坐標(biāo)三個(gè)變量、立體坐標(biāo)適用于任意變量、但必需將適用于任意變量、但必需將一般形式變成標(biāo)準(zhǔn)形式一般形式變成標(biāo)準(zhǔn)形式下面我們分析一下簡(jiǎn)單的情況 只有兩個(gè)決策變量的線性規(guī)劃問題，這時(shí)可以通過圖解的方法來求解。圖解法具有簡(jiǎn)單、直觀、便于初學(xué)者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點(diǎn)。2第三節(jié) 兩個(gè)變量問題的圖解法解（參見教材P21）解（參見教材P22）3第三節(jié) 兩個(gè)變量問題的圖解法解（參見教材P23）解（參見教材P23）4圖解法max

2、Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0練習(xí)：練習(xí)： 用圖解法求解線性規(guī)劃問題用圖解法求解線性規(guī)劃問題5圖解法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）Dmax Zmin Z此點(diǎn)是唯一最

3、優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值 max Z=17.2可行域可行域max Z = 2X1 + X26圖解法若max Z=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 max Z（3.8，4）34.2 = 3X1+5.7X2 藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解這種情形為有無(wú)窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=34.2是唯一的?？尚杏蚩尚杏?圖解法min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 +

4、 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此點(diǎn)是唯一最優(yōu)解8圖解法 006346321212121xxxxxxxx、246x1x2246無(wú)界解無(wú)界解( (無(wú)最優(yōu)解無(wú)最優(yōu)解) )max Z=x1+2x2練習(xí)：練習(xí)：x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Z9x1x2O10203040102030405050無(wú)可行解無(wú)可行解(即無(wú)最優(yōu)解即無(wú)最優(yōu)解)0,050305.140221212121 xxxxxxxxmax Z

5、=3x1+4x2練習(xí)：練習(xí)：10線性規(guī)劃的圖解法線性規(guī)劃的圖解法圖解法的基本步驟圖解法的基本步驟 X*= (4, , 6)Tz* = 42 1畫出可行域圖形畫出可行域圖形 2畫出目標(biāo)函數(shù)的畫出目標(biāo)函數(shù)的 等值線及其法線等值線及其法線 3確定最優(yōu)點(diǎn)確定最優(yōu)點(diǎn)max z = 3x1+5x2 x1 8 2 x2 12 3x1+ 4 x2 36 x1, , x2 0s.t.x1x2O(0, ,0)x1= 8A(8, ,0)2x2= 12D(0, ,6)3x1 + 4x2 = 36O(0, ,0)x1x2D(0, ,6)C(4, ,6)B(8, ,3)A(8, ,0)z = 15z = 30z 法向法向

6、z* = 4211線性規(guī)劃的圖解法線性規(guī)劃的圖解法幾點(diǎn)說明幾點(diǎn)說明實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn)實(shí)際運(yùn)用時(shí)還須注意以下幾點(diǎn): :(1)(1)若函數(shù)約束原型就是等式若函數(shù)約束原型就是等式, ,則其代表的區(qū)域僅為一直線則其代表的區(qū)域僅為一直線, ,而而且問題的整個(gè)可行域且問題的整個(gè)可行域( (若存在的話若存在的話) )也必然在此直線上。也必然在此直線上。(2)(2)在畫目標(biāo)函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向在畫目標(biāo)函數(shù)等值線時(shí)只須畫兩條就能確定其法線方向, ,為此為此, , 只須賦給只須賦給 兩個(gè)適當(dāng)?shù)闹怠蓚€(gè)適當(dāng)?shù)闹怠?3)(3)在找出最優(yōu)點(diǎn)后在找出最優(yōu)點(diǎn)后, ,關(guān)于其坐標(biāo)值有兩種確定方法關(guān)于

7、其坐標(biāo)值有兩種確定方法: : 在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值在圖上觀測(cè)最優(yōu)點(diǎn)坐標(biāo)值 通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值通過解方程組得出最優(yōu)點(diǎn)坐標(biāo)值12圖解法學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：1. 通過圖解法了解線性規(guī)劃有幾種解的形式通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）（唯一最優(yōu)解；無(wú)窮多最優(yōu)解；無(wú)界解；無(wú)可行解）2. 作圖的關(guān)鍵有三點(diǎn)：作圖的關(guān)鍵有三點(diǎn)： (1) 可行解區(qū)域要畫正確可行解區(qū)域要畫正確 (2) 目標(biāo)函數(shù)增加的方向不能畫錯(cuò)目標(biāo)函數(shù)增加的方向不能畫錯(cuò) (3) 目標(biāo)函數(shù)的直線怎樣平行移動(dòng)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)13線性規(guī)劃的圖解法線性規(guī)劃的圖解法幾種可能結(jié)果幾種可能結(jié)果一、唯一解一、唯一解如例如例1 1、例、例2 2都只有一個(gè)都只有一個(gè)最優(yōu)點(diǎn)，屬于唯一解的情形最優(yōu)點(diǎn)，屬于唯一解的情形s.t.max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0 二二多重解多重解z = 12z* = 36線段線段上無(wú)窮多個(gè)上無(wú)窮多個(gè)點(diǎn)