線性規(guī)劃問題的圖解法.ppt

一、 線性規(guī)劃的圖解法,解的幾何表示,1什麼是圖解法？ 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。 求解的思路是：先將約束條件加以圖解，求得滿足約束條件和非負條件的解的集合（即可行域），然后結合目標函數的要求從可行域中找出最優(yōu)解。,2. 圖解法舉例,實施圖解法，以求出最優(yōu)生產計劃（最優(yōu)解）, 給出最優(yōu)值。,例3-1,由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可以進行圖解了。,第一步：建立平面直角坐標系 標出坐標原點, 坐標軸的指向和單位長度。用x1軸表示產品A的產量，用x2軸表示產品B的產量。 第二步：對約束條件加以圖解。 第三步：畫出目標函數等值線，結合目標函數的要求求出最優(yōu)解：最優(yōu)生產方案。 第四步：最優(yōu)解帶入目標函數，得出最優(yōu)值。,約束條件的圖解: 每一個約束不等式在平面直角坐標系中都代表一個半平面，只要先畫出該半平面的邊界，然后確定是哪個半平面。,以第一個約束條件: 為例, 說明圖解過程。,代表一個半平面 其邊界: x1+2 x2 =8,點A、B 連線AB 經濟含義 ？ A0B,點A(8,0)：,連接AB：,設備全部占用所生產、數量對應的點的集合。,全部的設備都用來生產產品而不生產產品,那么產品的最大可能產量為8臺,計算過程為： x1+208 x18,0 B：,設備沒有全部占用所生產、數量對應的點的集合。,約束條件及 非負條件x1,x2 0 代表的公共部分圖中陰影區(qū)，就是滿足所有約束條件和非負條件的點的集合，即可行域。在這個區(qū)域中的每一個點都對應著一個可行的生產方案。,另兩個約束條件的邊界直線CD、EF: 4x116，4 x2 12,令 Z=2x1+3x2=c, 其中c為任選的一個常數，在圖 中畫出直線 2x1+3x2=c, 即對應著一個可行的生產結果，即使兩種產品的總利潤達到c。 這樣的直線有無數條，且相互平行，稱這樣的直線為目標函數等值線。只要畫兩條目標函數等值線，如令 c0和c=6，可看出目 標函數值變化的方向, 即虛線 l1和l2,箭頭為產 品的總利潤遞增的方向。,對應坐標x1=4, x2=2 是最佳的產品組合, 4,2T就是線性規(guī)劃模型的最優(yōu)解 使產品的總利潤達到最大值maxZ=24+32=14就是目標函數最優(yōu)值。,沿著箭頭方向平移目標函數等值線，達到可行域中的最遠點E, E點就是最優(yōu)點;,盡管最優(yōu)點的對應坐標可以直接從圖中給出，但是在大多數情況下，對實際問題精確地看出一個解答是比較困難的。所以，通?？偸怯媒饴?lián)立方程的方法求出最優(yōu)解的精確值。 比如C點對應的坐標值我們可以通過求解下面的聯(lián)立方程，即求直線AB和CD的交點來求得。 直線AB: x1+2x2=8 直線CD: 4x1=16,結果 有唯一最優(yōu)解 可行域是一個非空有界區(qū)域,可行域有幾種可能 ? 解有幾種可能 ?,唯一最優(yōu)解,例3-3 將例3-1中目標要求改為極小化，目標函數和約束條件均不變，則可行域與例3-1相同，目標函數等值線也完全相同，只是在求最優(yōu)解時，應沿著與箭頭相反的方向平移目標函數等值線，求得的結果是有唯一最優(yōu)解x1=4,x2=2,對應著圖中的坐標原點。,無窮多個最優(yōu)解,沿著箭頭的方向平移目標函數等值線，發(fā)現(xiàn)平移的最終結果是目標函數等值線將與可行域的一條邊界線段AB重合。,結果表明，該線性規(guī)劃有無窮多個最優(yōu)解線段AB上的所有點都是最優(yōu)點，它們都使目標函數取得相同的最大值Zmax=14。,無界解,如圖中可行域是一個無界區(qū)域，如陰影區(qū)所示。虛線為目表函數等值線，沿著箭頭指的方向平移可以使目標函數值無限制地增大，但是找不到最優(yōu)解。這種情況通常稱為無“有限最優(yōu)解” 或“最優(yōu)解無界”。,如果一個實際問題抽象成像例1-4這樣的線性規(guī)劃模型，比如是一個生產計劃問題，其經