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

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

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

實(shí)施圖解法，以求出最優(yōu)生產(chǎn)計(jì)劃（最優(yōu)解）。

例1－1

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

第二步：對(duì)約束條件加以圖解。第三步：畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解－－最優(yōu)生產(chǎn)方案。

約束條件的圖解:

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

?以第一個(gè)約束條件

1/3x1+1/3x2

1為例說明約束條件的圖解過程。怎么畫邊界怎么確定半平面

如果全部的勞動(dòng)工時(shí)都用來生產(chǎn)A產(chǎn)品而不生產(chǎn)B產(chǎn)品，那么A產(chǎn)品的最大可能產(chǎn)量為3噸，計(jì)算過程為：1/3x1+1/3×01x13

這個(gè)結(jié)果對(duì)應(yīng)著右圖中的點(diǎn)A(3,0),同樣我們可以找到B產(chǎn)品最大可能產(chǎn)量對(duì)應(yīng)的點(diǎn)B(0,3)。連接A、B兩點(diǎn)得到約束

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)點(diǎn)ABCDEX1X20Ⅰ象限Ⅱ象限Ⅲ象限Ⅳ象限如何確定是哪個(gè)半平面？

兩個(gè)約束條件

及非負(fù)條件x1,x2

0所代表的公共部分

－－圖中黃色區(qū)域，就是滿足所有約束條件和非負(fù)條件的點(diǎn)的集合，即可行域。在這個(gè)區(qū)域中的每一個(gè)點(diǎn)都對(duì)應(yīng)著一個(gè)可行的生產(chǎn)方案。

第二個(gè)約束條件的邊界－－直線CD:1/3x1+4/3x2=312345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點(diǎn)ABCDEX1X20

令Z=2x1+3x2=c,其中c為任選的一個(gè)常數(shù)，在圖中畫出直線2x1+3x2=c,這條直線上的點(diǎn)即對(duì)應(yīng)著一個(gè)可行的生產(chǎn)方案，即使兩種產(chǎn)品的總利潤達(dá)到c。這樣的直線有無數(shù)條，而且相互平行，稱這樣的直線為目標(biāo)函數(shù)等值線。只要畫出兩條目標(biāo)函數(shù)等值線，比如令c＝0和c=6，就能看出

目標(biāo)函數(shù)值遞增的方向，用箭頭標(biāo)出這個(gè)方向。圖中兩條虛線

l1和l2就分別代表目標(biāo)函數(shù)等值線

2x1+3x2=0和2x1+3x2=6,

箭頭表示使兩種產(chǎn)品的總利潤遞增的方向。12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點(diǎn)ABCDEX1X20

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

12345678912345(1/3)x1+(4/3)x2=3(1/3)x1+(1/3)x2=1l1l2最優(yōu)點(diǎn)ABCDEX1X20

盡管最優(yōu)點(diǎn)的對(duì)應(yīng)坐標(biāo)可以直接從圖中給出，但是在大多數(shù)情況下，對(duì)實(shí)際問題精確地看出一個(gè)解答是比較困難的。所以，通?？偸怯媒饴?lián)立方程的方法求出最優(yōu)解的精確值。比如E點(diǎn)對(duì)應(yīng)的坐標(biāo)值我們可以通過求解下面的聯(lián)立方程，即求直線AB和CD的交點(diǎn)來求得。直線AB:1/3x1+1/3x2=1

直線CD:1/3x1+4/3x2=3

0123456789x1

54321x2（3，0）C=6（9，0）（0，9/4）E（1，2）C=0（0，3）例1-2用圖解法求解下面的線性規(guī)劃問題：復(fù)習(xí)直線方程：12345643215OX2X1X1-x2=2-x1+2x2=2x1+x2=4BCFADZ=0Z=10Z=14對(duì)偶規(guī)劃

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

它的圖解見右圖。其中L1和L2分別為兩個(gè)約束半平面的邊界，虛線為目標(biāo)函數(shù)等值線，可行域?yàn)閳D中陰影部分，沿著與箭頭（目標(biāo)函數(shù)值遞減的方向）的方向平移目標(biāo)函數(shù)等值線（注意：對(duì)偶規(guī)劃中要求對(duì)目標(biāo)函數(shù)極小化）得最優(yōu)點(diǎn)為E,

其對(duì)應(yīng)坐標(biāo)為y1=5,y2=1

Wmin=5+3×1=83(1/3)y1+(4/3)y2=3(1/3)y1+(1/3)y2=2ECDAB1234567891245最優(yōu)點(diǎn)y1y20L2L1

其經(jīng)濟(jì)意義：對(duì)包工工時(shí)及原材料的單位定價(jià)（影子價(jià)格），若工廠自己不生產(chǎn)產(chǎn)品A和B，將現(xiàn)有的工時(shí)及原材料轉(zhuǎn)而接受外來加工時(shí)，那么上述的價(jià)格系統(tǒng)能保證不虧本又最富有競爭力（包工及原材料的總價(jià)格最低）。可以看到，當(dāng)原問題和對(duì)偶問題都取得最優(yōu)解時(shí)，這對(duì)線性規(guī)劃對(duì)應(yīng)的目標(biāo)函數(shù)值是相等的：

Zmax=Wmin=8

考察原問題和對(duì)偶問題的解，給做決策的管理者另一個(gè)自由度，比如除了研究怎樣利用已有的資源以取得最大利潤的同時(shí)，還可以進(jìn)一步探討怎樣通過增加更多的資源或使用不同類型的資源來增加利潤。將例1-1稍作改動(dòng)形成案例1，仍使用圖解法來求解。

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

設(shè)三種產(chǎn)品的產(chǎn)量分別是x1、x2、x3噸，由于有三個(gè)決策變量，用圖解法求解下面的線性規(guī)劃時(shí)，必須首先建立空間直角坐標(biāo)系。

B點(diǎn)對(duì)應(yīng)著該線性規(guī)劃的最優(yōu)解：

X*=(1,2,0)T

即x1=1（產(chǎn)品A的產(chǎn)量）

x2=2（產(chǎn)品B的產(chǎn)量）

x3=0（產(chǎn)品C的產(chǎn)量）此時(shí)可得產(chǎn)品最大總利潤為：

Zmax=8

由右圖可知，可行域?yàn)橥刮迕骟wOABCDE,粗虛線所圍平面為目標(biāo)函數(shù)等值面，平移目標(biāo)函數(shù)等值面得最優(yōu)點(diǎn)為B點(diǎn)。結(jié)論

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

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

討論用圖解法求解線性規(guī)劃的各種可能的結(jié)果

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

(1/3)X1+(4/3)X2=3(1/3)X1+(1/3)X2=1ABCD12345678912345X1X20

該線性規(guī)劃的可行域?yàn)樯蠄D中四邊形OAED（即陰影區(qū)），虛線為目標(biāo)函數(shù)等值線，箭頭為目標(biāo)函數(shù)值遞增的方向。沿著箭頭的方向平移目標(biāo)函數(shù)等值線，發(fā)現(xiàn)平移的最終結(jié)果是目標(biāo)函數(shù)等值線將與可行域的一條邊界－－線段AE重合，這個(gè)結(jié)果表明，該線性規(guī)劃有無窮多個(gè)最優(yōu)解－－線段AE上的所有點(diǎn)都是最優(yōu)點(diǎn)，它們都使目標(biāo)函數(shù)取得相同的最大值Zmax=3。唯一最優(yōu)解

例1-3將例1-1中目標(biāo)要求改為極小化，目標(biāo)函數(shù)和約束條件均不變，則可行域與例1-1相同，目標(biāo)函數(shù)等值線也完全相同，只是在求最優(yōu)解時(shí)，應(yīng)沿著與箭頭相反的方向平移目標(biāo)函數(shù)等值線，求得的結(jié)果是有唯一最優(yōu)解x1=0,x2=0,對(duì)應(yīng)著圖1-6中的坐標(biāo)原點(diǎn)。無界解-2X1+X2=1AB12345612345X1X20

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

maxZ=－2x1+x2，而約束條件不變的例子。x1x2

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

用圖解法求解下面的線性規(guī)劃①畫約束條件1,2；畫約束條件3并標(biāo)明可行域；畫目標(biāo)函數(shù)等值線；說明如何得到最優(yōu)解,算出相應(yīng)的目標(biāo)函數(shù)最優(yōu)值。課堂練習(xí)1-3(2,2)

1