§2 線性規(guī)劃的圖解法.ppt

1、圖解法 線性規(guī)劃問題求解的 幾種可能結(jié)果 由圖解法得到的啟示,2 線性規(guī)劃的圖解法,例1的數(shù)學模型,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 2x1 + 2x2 12 4x1 16 5x2 15 x1、 x2 0,x1,x2,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,2x1 + 2x2 12,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 2x1 + 2x2 12 4x1 16 5x2 15 x1、 x2 0,4x1 16,5 x2 15,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標函數(shù) Max Z = 2x1 + 3x2

2、約束條件 2x1 + 2x2 12 4x1 16 5x2 15 x1、 x2 0,可行域,圖解法,9 8 7 6 5 4 3 2 1 0,| 123456789,x1,x2,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 2x1 + 2x2 12 4x1 16 4x2 15 x1、 x2 0,可行域,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標函數(shù) Max Z = 2x1 + 3x2 約束條件 2x1 + 2x2 12 4x1 16 4x2 15 x1、 x2 0,2x1 + 3x2 = 6,圖解法,9 8 7 6 5 4 3 2 1 0,x2,目標函數(shù) Max Z =

3、2x1 + 3x2 約束條件 2 x1 + 2x2 12 4x1 16 5x2 15 x1、 x2 0,圖解法,圖解法求解步驟,由全部約束條件作圖求出可行域； 作目標函數(shù)等值線，確定使目標函數(shù)最優(yōu)的移動方向； 平移目標函數(shù)的等值線，找出最優(yōu)點，算出最優(yōu)值。,線性規(guī)劃問題求解的 幾種可能結(jié)果,(a) 唯一最優(yōu)解,(b)無窮多最優(yōu)解,線性規(guī)劃問題求解的 幾種可能結(jié)果,(c)無界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0,x1,線性規(guī)劃問題求解的 幾種可能結(jié)果,(d)無可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 1

4、6 4x2 12 -2x1 + x2 4 x1、 x2 0 可行域為空集,線性規(guī)劃問題求解的 幾種可能結(jié)果,圖解法的幾點結(jié)論:（由圖解法得到的啟示）,可行域是有界或無界的凸多邊形。 若線性規(guī)劃問題存在最優(yōu)解，它一定可以在可行域的頂點得到。 若兩個頂點同時得到最優(yōu)解，則其連線上的所有點都是最優(yōu)解。 解題思路：找出凸集的頂點，計算其目標函數(shù)值，比較即得。,練習：用圖解法求解LP問題,圖解法 （練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,圖解法 （練習）,18 16

5、 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,可行域,A,B,C,D,E,圖解法 （練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),34x1 + 40 x2 = 272,圖解法 （練習）,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,x2,4x1 + 6x2 48,2x1 + 2x2 18,2x1 + x2 16,A,B,C,D,E (8,0),(0,6.8),圖解法 （練習）,x2,18 16 14 12 10 8 6 4 2 0,| 24681012141618,x1,4x1 + 6x2 48,2x1 + 2x2 18