第二章 線性規(guī)劃問(wèn)題的圖解法

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

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

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

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

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

8

x1

8△Ａ0B：設(shè)備沒(méi)有全部占用所生產(chǎn)Ⅰ、Ⅱ數(shù)量對(duì)應(yīng)的點(diǎn)的集合。1203x24123x18567Q4BA第7頁(yè)，課件共18頁(yè)，創(chuàng)作于2023年2月約束條件及

非負(fù)條件x1,x2

0

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

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

令Z=2x1+3x2=c,其中c為任選的一個(gè)常數(shù)，在圖中畫(huà)出直線2x1+3x2=c,即對(duì)應(yīng)著一個(gè)可行的生產(chǎn)結(jié)果，即使兩種產(chǎn)品的總利潤(rùn)達(dá)到c。這樣的直線有無(wú)數(shù)條，且相互平行，稱這樣的直線為目標(biāo)函數(shù)等值線。只要畫(huà)兩條目標(biāo)函數(shù)等值線，如令

c＝0和c=6，可看出目標(biāo)函數(shù)值變化的方向,

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

4+3

2=14就是目標(biāo)函數(shù)最優(yōu)值。

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

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

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

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

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

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