第二章線性規(guī)劃問題的圖解法第1頁，課件共18頁，創(chuàng)作于2023年2月1．什麼是圖解法？線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。求解的思路是：先將約束條件加以圖解，求得滿足約束條件和非負條件的解的集合（即可行域），然后結合目標函數的要求從可行域中找出最優(yōu)解。第2頁，課件共18頁，創(chuàng)作于2023年2月2.圖解法舉例

實施圖解法，以求出最優(yōu)生產計劃（最優(yōu)解）,給出最優(yōu)值。

例2-1第3頁，課件共18頁，創(chuàng)作于2023年2月由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可以進行圖解了。第一步：建立平面直角坐標系標出坐標原點,坐標軸的指向和單位長度。用x1軸表示產品A的產量，用x2軸表示產品B的產量。第二步：對約束條件加以圖解。第三步：畫出目標函數等值線，結合目標函數的要求求出最優(yōu)解：最優(yōu)生產方案。第四步：最優(yōu)解帶入目標函數，得出最優(yōu)值。第4頁，課件共18頁，創(chuàng)作于2023年2月約束條件的圖解:

每一個約束不等式在平面直角坐標系中都代表一個半平面，只要先畫出該半平面的邊界，然后確定是哪個半平面。

?以第一個約束條件:為例,說明圖解過程。怎麼畫邊界怎麼確定半平面第5頁，課件共18頁，創(chuàng)作于2023年2月 代表一個半平面其邊界:x1+2x2=8x1+2x2=8及x1，x2≥0△AOB點A、B連線AB經濟含義？△A0B1203x24123x18567Q4BA第6頁，課件共18頁，創(chuàng)作于2023年2月點A(8,0)：連接AB：設備全部占用所生產Ⅰ、Ⅱ數量對應的點的集合。全部的設備都用來生產Ⅰ產品而不生產Ⅱ產品,那么Ⅰ產品的最大可能產量為8臺,計算過程為：x1+2×0

8

x1

8△Ａ0B：設備沒有全部占用所生產Ⅰ、Ⅱ數量對應的點的集合。1203x24123x18567Q4BA第7頁，課件共18頁，創(chuàng)作于2023年2月約束條件及

非負條件x1,x2

0

代表的公共部分－－圖中陰影區(qū)，就是滿足所有約束條件和非負條件的點的集合，即可行域。在這個區(qū)域中的每一個點都對應著一個可行的生產方案。

另兩個約束條件的邊界直線CD、EF:4x1≤16，4x2≤128567x1A3x2BCDE4123102F第8頁，課件共18頁，創(chuàng)作于2023年2月

令Z=2x1+3x2=c,其中c為任選的一個常數，在圖中畫出直線2x1+3x2=c,即對應著一個可行的生產結果，即使兩種產品的總利潤達到c。這樣的直線有無數條，且相互平行，稱這樣的直線為目標函數等值線。只要畫兩條目標函數等值線，如令

c＝0和c=6，可看出目標函數值變化的方向,

即虛線l1和l2,箭頭為產品的總利潤遞增的方向。最優(yōu)點8567x1A3x2BCDE4123102F第9頁，課件共18頁，創(chuàng)作于2023年2月對應坐標x1=4,x2=2是最佳的產品組合,[4,2]T就是線性規(guī)劃模型的最優(yōu)解使產品的總利潤達到最大值maxZ=2

4+3

2=14就是目標函數最優(yōu)值。

沿著箭頭方向平移目標函數等值線，達到可行域中的最遠點E,E點就是最優(yōu)點;最優(yōu)點8567x1A3x2BCDE4123102F第10頁，課件共18頁，創(chuàng)作于2023年2月盡管最優(yōu)點的對應坐標可以直接從圖中給出，但是在大多數情況下，對實際問題精確地看出一個解答是比較困難的。所以，通?？偸怯媒饴?lián)立方程的方法求出最優(yōu)解的精確值。比如C點對應的坐標值我們可以通過求解下面的聯(lián)立方程，即求直線AB和CD的交點來求得。直線AB:x1+2x2=8

直線CD:4x1=16第11頁，課件共18頁，創(chuàng)作于2023年2月最優(yōu)點8567x1A3x2BCDE4123102F第12頁，課件共18頁，創(chuàng)作于2023年2月結果有唯一最優(yōu)解可行域是一個非空有界區(qū)域

用圖解法求解線性規(guī)劃的各種可能的結果可行域有幾種可能?解有幾種可能?討論第13頁，課件共18頁，創(chuàng)作于2023年2月唯一最優(yōu)解

例2-3將例2-1中目標要求改為極小化，目標函數和約束條件均不變，則可行域與例1-1相同，目標函數等值線也完全相同，只是在求最優(yōu)解時，應沿著與箭頭相反的方向平移目標函數等值線，求得的結果是有唯一最優(yōu)解x1=4,x2=2,對應著圖2-6中的坐標原點。第14頁，課件共18頁，創(chuàng)作于2023年2月

無窮多個最優(yōu)解

{c1,c2}8567x13x24123102BA第15頁，課件共18頁，創(chuàng)作于2023年2月沿著箭頭的方向平移目標函數等值線，發(fā)現平移的最終結果是目標函數等值線將與可行域的一條邊界線段AB重合。結果表明，該線性規(guī)劃有無窮多個最優(yōu)解－－線段AB上的所有點都是最優(yōu)點，它們都使目標函數取得相同的最大值Zmax=14。第16頁，課件共18頁，創(chuàng)作于2023年2月無界解2406x212543x1第17頁，課件共18頁，創(chuàng)作于2023年2月如圖中可行域是一個無界區(qū)域，如陰影區(qū)所示。虛線為目表函數等值線，沿著箭頭指的方向平移可以使目標函數值無限制地增大，但是找不到最優(yōu)解。這種情況通常稱為無“有限最優(yōu)解”或“最優(yōu)解無界”。如果一個實際問題抽象成像例1