第2部分-線性的規(guī)劃圖解法課件

二、線性規(guī)劃的圖解法

－－－解的幾何表示2020年9月28日11．什么是圖解法？線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過程。求解的思路是：先將約束條件加以圖解，求得滿足約束條件的解的集合（即可行域），然后結合目標函數的要求從可行域中找出最優(yōu)解。2020年9月28日22.圖解法舉例

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

例1－12020年9月28日3

由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標系就可進行圖解了。第一步：建立平面直角坐標系，標出坐標原點,坐標軸的指向和單位長度。用x1軸表示產品A的產量，用x2軸表示產品B的產量。

第二步：對約束條件加以圖解。第三步：畫出目標函數等值線，結合目標函數的要求求出最優(yōu)解－－最優(yōu)生產方案。2020年9月28日4

約束條件的圖解:

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

?以第一個約束條件1/3x1+1/3x2

1為例說明約束條件的圖解過程。怎么畫邊界怎么確定半平面2020年9月28日5

如果全部的勞動工時都用來生產A產品而不生產B產品，那么A產品的最大可能產量為3噸，計算過程為：1/3x1+1/3×01x13這個結果對應著右圖中的點A(3,0),同樣我們可以找到B產品最大可能產量對應的點B(0,3)。連接A、B兩點得到約束1/3x1+1/3x2

1所代表的半平面的邊界:1/3x1+1/3x2＝1，即直線AB。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點ABCDEX1X202020年9月28日6Ⅰ象限Ⅱ象限Ⅲ象限Ⅳ象限如何確定是哪個半平面？2020年9月28日7

兩個約束條件

及非負條件x1,x2

0所代表的公共部分

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

第二個約束條件的邊界－－直線CD:1/3x1+4/3x2=312345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點ABCDEX1X202020年9月28日8

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

目標函數值遞增的方向，用箭頭標出這個方向。圖中兩條虛線l1和l2就分別代表目標函數等值線2x1+3x2=0和2x1+3x2=6,箭頭表示使兩種產品的總利潤遞增的方向。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點ABCDEX1X202020年9月28日9

沿著箭頭的方向平移目標函數等值線，使其達到可行域中的最遠點E,E點就是要求的最優(yōu)點，它對應的相應坐標x1=1,x2=2就是最有利的產品組合，即生產A產品1噸，B產品2噸能使兩種產品的總利潤達到最大值Zmax=21+32=8（千元），x1=1,x2=2就是線性規(guī)劃模型的最優(yōu)解，Zmax=8就是相應的目標函數最優(yōu)值。

12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點ABCDEX1X202020年9月28日10

盡管最優(yōu)點的對應坐標可以直接從圖中給出，但是在大多數情況下，對實際問題精確地看出一個解答是比較困難的。所以，通?？偸怯媒饴摿⒎匠痰姆椒ㄇ蟪鲎顑?yōu)解的精確值。比如E點對應的坐標值我們可以通過求解下面的聯立方程，即求直線AB和CD的交點來求得。直線AB:1/3x1+1/3x2=1直線CD:1/3x1+4/3x2=32020年9月28日110123456789x1

54321x2（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）2020年9月28日12例1-2用圖解法求解下面的線性規(guī)劃問題：復習直線方程：2020年9月28日1312345643215OX2X1X1-x2=2-x1+2x2=2x1+x2=4BCFADZ=0Z=10Z=142020年9月28日14對偶規(guī)劃

順便提及，每一個線性規(guī)劃都有一個“影像”（一個伴生的線性規(guī)劃），稱之為線性規(guī)劃的對偶規(guī)劃。當建立一個線性規(guī)劃并達到最優(yōu)目標值時，同時也就解出了對偶規(guī)劃并達到了另一個不同意義的目標。如例1-1是尋求一個生產計劃方案，使得在勞動力和原材料可能供應的范圍內，產品的總利潤最大，它的對偶問題就是一個價格系統(tǒng)，使在平衡了勞動力和原材料的直接成本后，所確定的價格系統(tǒng)最具有競爭力。2020年9月28日15例1-1的對偶規(guī)劃如下：

2020年9月28日16

它的圖解見右圖。其中L1和L2分別為兩個約束半平面的邊界，虛線為目標函數等值線，可行域為圖中陰影部分，沿著與箭頭（目標函數值遞減的方向）的方向平移目標函數等值線（注意：對偶規(guī)劃中要求對目標函數極小化）得最優(yōu)點為E,其對應坐標為y1=5,y2=1Wmin=5+3×1=83(1/3)y1+(4/3)y2=3(1/3)y1+(1/3)y2=2ECDAB1234567891245最優(yōu)點y1y20L2L12020年9月28日17

其經濟意義：對包工工時及原材料的單位定價（影子價格），若工廠自己不生產產品A和B，將現有的工時及原材料轉而接受外來加工時，那么上述的價格系統(tǒng)能保證不虧本又最富有競爭力（包工及原材料的總價格最低）?？梢钥吹?，當原問題和對偶問題都取得最優(yōu)解時，這對線性規(guī)劃對應的目標函數值是相等的：Zmax=Wmin=8考察原問題和對偶問題的解，給做決策的管理者另一個自由度，比如除了研究怎樣利用已有的資源以取得最大利潤的同時，還可以進一步探討怎樣通過增加更多的資源或使用不同類型的資源來增加利潤。2020年9月28日18將例1-1稍作改動形成案例1，仍使用圖解法來求解。

（案例1）某工廠生產A、B、C三種產品，每噸的利潤分別為2000元、3000元、1000元，生產單位產品所需的工時及原材料如表1－2所示。若供應的原材料每天不超過3噸，所能利用的勞動力總工時是固定的，應如何制定日生產計劃，使三種產品的總利潤最大？

2020年9月28日19

設三種產品的產量分別是x1、x2、x3噸，由于有三個決策變量，用圖解法求解下面的線性規(guī)劃時，必須首先建立空間直角坐標系。2020年9月28日202020年9月28日21

B點對應著該線性規(guī)劃的最優(yōu)解：X*=(1,2,0)T即x1=1（產品A的產量）x2=2（產品B的產量）x3=0（產品C的產量）此時可得產品最大總利潤為：Zmax=8

由右圖可知，可行域為凸五面體OABCDE,粗虛線所圍平面為目標函數等值面，平移目標函數等值面得最優(yōu)點為B點。2020年9月28日22結論

從上面用圖解法求解案例1的過程中明顯感覺到對具有三個決策變量的線性規(guī)劃進行圖解就麻煩得多了。因此，盡管圖解法具有簡單、直觀的優(yōu)點，但它的使用是有局限性的，對僅含有兩個至多不超過三個決策變量的線性規(guī)劃才適于使用圖解法，大多數情況下僅對含有兩個決策變量的線性規(guī)劃才使用圖解法求解，而對含有三個及三個以上決策變量的線性規(guī)劃則應考慮使用更加有效的通用算法－－單純形法來進行求解，這將在§1-3節(jié)加以介紹。2020年9月28日23

例1-1和案例1所描述的都是有唯一最優(yōu)解且可行域是一個非空有界區(qū)域的情況。實際上，可行域不僅僅只有這一種可能，解的情況也是各種各樣的。

討論用圖解法求解線性規(guī)劃的各種可能的結果2020年9月28日24

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

(1/3)X1+(4/3)X2=3(1/3)X1+(1/3)X2=1ABCD12345678912345X1X202020年9月28日25

該線性規(guī)劃的可行域為上圖中四邊形OAED（即陰影區(qū)），虛線為目標函數等值線，箭頭為目標函數值遞增的方向。沿著箭頭的方向平移目標函數等值線，發(fā)現平移的最終結果是目標函數等值線將與可行域的一條邊界－－線段AE重合，這個結果表明，該線性規(guī)劃有無窮多個最優(yōu)解－－線段AE上的所有點都是最優(yōu)點，它們都使目標函數取得相同的最大值Zmax=3。2020年9月28日26唯一最優(yōu)解

例1-3將例1-1中目標要求改為極小化，目標函數和約束條件均不變，則可行域與例1-1相同，目標函數等值線也完全相同，只是在求最優(yōu)解時，應沿著與箭頭相反的方向平移目標函數等值線，求得的結果是有唯一最優(yōu)解x1=0,x2=0,對應著圖1-6中的坐標原點。2020年9月28日27無界解-2X1+X2=1AB12345612345X1X202020年9月28日28

本例中的可行域是一個無界區(qū)域，如圖中陰影區(qū)所示。虛線為目函數等值線，沿著箭頭所指的方向平移可以使目標函數值無限制地增大，因此找不到最優(yōu)解。這種情況通常稱為無“有限最優(yōu)解”或“最優(yōu)解無界”。如果一個實際問題抽象成像例1－4這樣的線性規(guī)劃模型，比如是一個生產計劃問題，其經濟含義就是某些資源是無限的，產品的產量可以無限大，解釋不合理。此時應重新檢查和修改模型，否則就沒有實際意義。注意，對于無界可行域的情況，也可能有唯一最優(yōu)解或無窮多個最優(yōu)解。比如目標要求為minZ=x1+2x2或maxZ=－2x1+x2，而約束條件不變的例子。x1x22020年9月28日29

綜上，用圖解法求解線性規(guī)劃時，各種求解結果與各種類型的可行域之間的對應關系可以用下圖加以描述：

2020年9月28日30用圖解法求解下面的線性規(guī)劃①畫約束條件1,2；畫約束條件3并標明可行域；畫目標函數等值線；說明如何得到最優(yōu)解,算出相應的目標函數最優(yōu)值。課堂練習1-32020年9月28日31(2,2)

12345x1X2

543210C=2C=102020年9月28日32a,b,cd,e

4、用圖解法求解線性規(guī)劃時需特別注意：

第一、線性