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

一、 線性規(guī)劃的圖解法,解的幾何表示,1什麼是圖解法？ 線性規(guī)劃的圖解法就是用幾何作圖的方法分析并求出其最優(yōu)解的過(guò)程。 求解的思路是：先將約束條件加以圖解，求得滿足約束條件和非負(fù)條件的解的集合（即可行域），然后結(jié)合目標(biāo)函數(shù)的要求從可行域中找出最優(yōu)解。,2. 圖解法舉例,實(shí)施圖解法，以求出最優(yōu)生產(chǎn)計(jì)劃（最優(yōu)解）, 給出最優(yōu)值。,例3-1,由于線性規(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ì)約束條件加以圖解。 第三步：畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解：最優(yōu)生產(chǎn)方案。 第四步：最優(yōu)解帶入目標(biāo)函數(shù)，得出最優(yōu)值。,約束條件的圖解: 每一個(gè)約束不等式在平面直角坐標(biāo)系中都代表一個(gè)半平面，只要先畫出該半平面的邊界，然后確定是哪個(gè)半平面。,以第一個(gè)約束條件: 為例, 說(shuō)明圖解過(guò)程。,代表一個(gè)半平面 其邊界: x1+2 x2 =8,點(diǎn)A、B 連線AB 經(jīng)濟(jì)含義 ？ A0B,點(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+208 x18,0 B：,設(shè)備沒(méi)有全部占用所生產(chǎn)、數(shù)量對(duì)應(yīng)的點(diǎn)的集合。,約束條件及 非負(fù)條件x1,x2 0 代表的公共部分圖中陰影區(qū)，就是滿足所有約束條件和非負(fù)條件的點(diǎn)的集合，即可行域。在這個(gè)區(qū)域中的每一個(gè)點(diǎn)都對(duì)應(yīng)著一個(gè)可行的生產(chǎn)方案。,另兩個(gè)約束條件的邊界直線CD、EF: 4x116，4 x2 12,令 Z=2x1+3x2=c, 其中c為任選的一個(gè)常數(shù)，在圖 中畫出直線 2x1+3x2=c, 即對(duì)應(yīng)著一個(gè)可行的生產(chǎn)結(jié)果，即使兩種產(chǎn)品的總利潤(rùn)達(dá)到c。 這樣的直線有無(wú)數(shù)條，且相互平行，稱這樣的直線為目標(biāo)函數(shù)等值線。只要畫兩條目標(biāo)函數(shù)等值線，如令 c0和c=6，可看出目 標(biāo)函數(shù)值變化的方向, 即虛線 l1和l2,箭頭為產(chǎn) 品的總利潤(rùn)遞增的方向。,對(duì)應(yīng)坐標(biāo)x1=4, x2=2 是最佳的產(chǎn)品組合, 4,2T就是線性規(guī)劃模型的最優(yōu)解 使產(chǎn)品的總利潤(rùn)達(dá)到最大值maxZ=24+32=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)的對(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,結(jié)果 有唯一最優(yōu)解 可行域是一個(gè)非空有界區(qū)域,可行域有幾種可能 ? 解有幾種可能 ?,唯一最優(yōu)解,例3-3 將例3-1中目標(biāo)要求改為極小化，目標(biāo)函數(shù)和約束條件均不變，則可行域與例3-1相同，目標(biāo)函數(shù)等值線也完全相同，只是在求最優(yōu)解時(shí)，應(yīng)沿著與箭頭相反的方向平移目標(biāo)函數(shù)等值線，求得的結(jié)果是有唯一最優(yōu)解x1=4,x2=2,對(duì)應(yīng)著圖中的坐標(biāo)原點(diǎn)。,無(wú)窮多個(gè)最優(yōu)解,沿著箭頭的方向平移目標(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。,無(wú)界解,如圖中可行域是一個(gè)無(wú)界區(qū)域，如陰影區(qū)所示。虛線為目表函數(shù)等值線，沿著箭頭指的方向平移可以使目標(biāo)函數(shù)值無(wú)限制地增大，但是找不到最優(yōu)解。這種情況通常稱為無(wú)“有限最優(yōu)解” 或“最優(yōu)解無(wú)界”。,如果一個(gè)實(shí)際問(wèn)題抽象成像例1-4這樣的線性規(guī)劃模型，比如是一個(gè)生產(chǎn)計(jì)劃問(wèn)題，其經(jīng)