數(shù)據(jù)模型與決策課件2-2lp圖解法

1、 圖解法 線性規(guī)劃問題求解的 幾種可能結(jié)果 由圖解法得到的啟示第三節(jié) 線性規(guī)劃的圖解法繼續(xù)返回例1的數(shù)學(xué)模型 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 x29 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0) 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 04x1 164 x2 12圖解法9 8 7 6 5 4 3 2 1 0 x2 目標(biāo)函數(shù) Max Z = 2x1 + 3x

2、2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 12可行域圖解法9 8 7 6 5 4 3 2 1 0 |123456789BT 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 + 2x2 84x1 164 x2 12可行域BCDEA圖解法9 8 7 6 5 4 3 2 1 0 x2 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|12345

3、6789x1x1 + 2x2 84x1 164 x2 12BCDEA2x1 + 3x2 = 6圖解法9 8 7 6 5 4 3 2 1 0 x2 目標(biāo)函數(shù) Max Z = 2x1 + 3x2 約束條件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 12BCDEAx1+ 2x2=8 4x1 =16最優(yōu)解 (4, 2)圖解法圖解法求解步驟由全部約束條件作圖求出可行域；作目標(biāo)函數(shù)等值線，確定使目標(biāo)函數(shù)最優(yōu)的移動(dòng)方向；平移目標(biāo)函數(shù)的等值線，找出最優(yōu)點(diǎn)，算出最優(yōu)值。線性規(guī)劃問題求解的 幾種可能結(jié)果(a) 唯一最優(yōu)解 x

4、26 5 4 3 2 1 0 |123456789x1(b)無窮多最優(yōu)解6 5 4 3 2 1 0 x2|123456789x1線性規(guī)劃問題求解的 幾種可能結(jié)果 (c)無界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0 x2x1線性規(guī)劃問題求解的 幾種可能結(jié)果(d)無可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0可行域?yàn)榭占€性規(guī)劃問題求解的 幾種可能結(jié)果圖解法的幾點(diǎn)結(jié)論:（由圖解法得到的啟示）可行域是有界或無界的凸多邊形。若線性規(guī)劃問題存在最優(yōu)解，它一定

5、可以在可行域的頂點(diǎn)得到。若兩個(gè)頂點(diǎn)同時(shí)得到最優(yōu)解，則其連線上的所有點(diǎn)都是最優(yōu)解。解題思路：找出凸集的頂點(diǎn)，計(jì)算其目標(biāo)函數(shù)值，比較即得。練習(xí)：用圖解法求解LP問題 Max Z = 34 x1 + 40 x24 x1 + 6 x2 48 2 x1 + 2 x2 182 x1 + x2 16x1、 x2 0圖解法 （練習(xí)） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16圖解法 （練習(xí)） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x

6、2 482x1 + 2x2 182x1 + x2 16可行域ABCDE圖解法 （練習(xí)） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)34x1 + 40 x2 = 272圖解法 （練習(xí)） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)圖解法 （練習(xí)） x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 +