【文章內(nèi)容簡介】 32m a x21212121xxxxxxxxZ 由于線性規(guī)劃模型中只有兩個決策變量，因此只需建立平面直角坐標(biāo)系就可以進(jìn)行圖解了。 第一步： 建立平面直角坐標(biāo)系 標(biāo)出坐標(biāo)原點 , 坐標(biāo)軸的指向和單位長度 。 用 x1軸表示產(chǎn)品 A的產(chǎn)量 ， 用 x2軸表示產(chǎn)品 B的產(chǎn)量 。 第二步： 對約束條件加以圖解。 第三步： 畫出目標(biāo)函數(shù)等值線，結(jié)合目標(biāo)函數(shù)的要求求出最優(yōu)解：最優(yōu)生產(chǎn)方案。 第四步： 最優(yōu)解帶入目標(biāo)函數(shù)，得出最優(yōu)值。 約束條件的圖解 : 每一個約束不等式在平面直角坐標(biāo)系中都代表一個半平面，只要 先畫出該半平面的邊界 ，然后 確定是哪個半平面 。 ? 以第一個約束條件 : 為例 , 說明圖解過程。 怎麼畫邊界 怎麼確定 半平面 82 21 ?? xx 代表一個半平面 其邊界 : 及 △ AOB 點 A、 B 連線 AB 經(jīng)濟(jì)含義 ？ △ A0B 1 2 0 3 x2 4 1 2 3 x1 8 5 6 7 82 21 ?? xxQ4 B A 82 21 ?? xx0, 21 ?xx82 21 ?? xx82 21 ?? xx點 A(8,0)： 連接 AB： 設(shè)備全部占用所生產(chǎn)Ⅰ 、 Ⅱ 數(shù)量對應(yīng)的點的集合 。 全部的設(shè)備都用來生產(chǎn) Ⅰ 產(chǎn)品而不生產(chǎn) Ⅱ產(chǎn)品 ,那么 Ⅰ 產(chǎn)品的最大可能產(chǎn)量為 8臺 ,計算過程為： x1+2 0?8 ?x1?8 △ Ａ 0 B： 設(shè)備沒有全部占用所生產(chǎn) Ⅰ 、 Ⅱ 數(shù)量對應(yīng)的點的集合 。 1 2 0 3 x2 4 1 2 3 x1 8 5 6 7 82 21 ?? xxQ4 B A 約束條件及 非負(fù)條件 代表的公共部分－－圖中陰影區(qū)，就是滿足所有約束條件和非負(fù)條件的點的集合，即可行域。在這個區(qū)域中的每一個點都對應(yīng)著一個可行的生產(chǎn)方案。 另兩個約束條件的邊界直線 CD、 EF: 4x1≤16， 4 x2 ≤12 124 2 ?x164 1 ?x8 5 6 7 82 21 ?? xxx1 A 3 x2 B C D E 4 1 2 3 1 0 2 F 0, 21 ?xx 令 Z=2x1+3x2=c, 其中 c為任選的一個常數(shù) ， 在圖 中畫出直線 2x1+3x2=c, 即對應(yīng)著一個可行的生產(chǎn)結(jié)果 ，即使兩種產(chǎn)品的總利潤達(dá)到 c。 這樣的直線有無數(shù)條 ， 且相互平行 ， 稱這樣的直線為 目標(biāo)函數(shù)等值線 。 只要 畫兩條目標(biāo)函數(shù) 等值線 ，如令 c＝ 0和 c=6， 可看出 目 標(biāo)函數(shù)值變化的方向 , 即虛線 l1和 l2,箭頭為產(chǎn) 品的總利潤遞增的方向 。 最優(yōu)點 124 2 ?x164 1 ?x8 5 6 7 82 21 ?? xxx1 A 3 x2 B C D E 4 1 2 3 1 0 2 F ? 對應(yīng)坐標(biāo) x1=4, x2=2 是最佳的產(chǎn)品組合 , [4,2]T就是線性規(guī)劃模型的 最優(yōu)解 ? 使產(chǎn)品的總利潤達(dá)到最大值 maxZ=2?4+3?2=14就是目標(biāo)函數(shù) 最優(yōu)值。 ? 沿著箭頭 方向 平移 目標(biāo)函數(shù)等值線，達(dá)到 可行域中的最遠(yuǎn)點 E, E點就是 最優(yōu)點 。 最優(yōu)點 124 2 ?x164 1 ?x8 5 6 7 82 21 ?? xxx1 A 3 x2 B C D E 4 1 2 3 1 0 2 F 盡管最優(yōu)點的對應(yīng)坐標(biāo)可以直接從圖中給出 ， 但是在大多數(shù)情況下 ， 對實際問題精確地看出一個解答是比較困難的 。 所以 ， 通常總是 用解聯(lián)立方程的方法求出最優(yōu)解的精確值 。 比如 C點對應(yīng)的坐標(biāo)值我們可以通過求解下面的聯(lián)立方程 ， 即求直線 AB和 CD的交點來求得 。 直線 AB: x1+2x2=8 直線 CD: 4x1=16 121212284 164 12, 0xxxxxx????????≤≤≤≥12m a x 2 3Z x x??最優(yōu)點 124 2 ?x164 1 ?x8 5 6 7 82 21 ?? xxx1 A 3 x2 B C D E 4 1 2 3 1 0 2 F 將例 11稍作改動形成案例 1，仍使用圖解法來求解。 （案例 1）某工廠生產(chǎn) A、 B、 C三種產(chǎn)品，每噸的利潤分別為 2022元、 3000元、 1000元，生產(chǎn)單位產(chǎn)品所需的工時及原材料如表 12所示。應(yīng)如何制定日生產(chǎn)計劃，使三種產(chǎn)品的總利潤最大？ 表 1 2 生產(chǎn)單位產(chǎn)品所需的工時及原材料表 12 1 4 0 材料 B（ kg） 16 1 0 4 材料 A（ kg） 8 1 2 1 設(shè)備（臺） 資源 限量 Ⅲ Ⅱ Ⅰ 產(chǎn)品 資源 M a x Z = 2 x 1 + 3 x 2 +x 3 ???????????0x,x, x12x+4x16x+4x8x+2x+x3213231321 設(shè)三種產(chǎn)品的產(chǎn)量分別是 x x x3噸，由于有三個決策變量，用圖解法求解下面的線性規(guī)劃時，必須首先建立空間直角坐標(biāo)系。 結(jié)果 有唯一最優(yōu)解 可行域是一個非空有界區(qū)域 用圖解法求解線性規(guī)劃的各種可能的結(jié)果 可行域有幾種可能 ? 解有幾種可能 ? 討論 唯一最優(yōu)解 例 13 將例 11中目標(biāo)要求改為極小化，目標(biāo)函數(shù)和約束條件均不變，則可行域與例 11相同，目標(biāo)函數(shù)等值線也完全相同，只是在求最優(yōu)解時，應(yīng)沿著與箭頭相反的方向平移目標(biāo)函數(shù)等值線，求得的結(jié)果是有 唯一最優(yōu)解 x1=0,x2=0,對應(yīng)著圖 16中的坐標(biāo)原點。 無窮多個最優(yōu)解 {c1,c2} 12m a x 2 3Z x x??121212284 164 12, 0xxxxxx????????≤≤≤≥21 2m a x xxZ ??8 5 6 7 82 21 ?? xxx1 3 x2 4 1 2 3 1 0 2 B A 沿著箭頭的方向平移目標(biāo)函數(shù)等值線 ，發(fā)現(xiàn)平移的最終結(jié)果是目標(biāo)函數(shù)等值線將與可行域的一條邊界線段 AB重合 。 結(jié)果表明 ， 該線性規(guī)劃有 無窮多個最優(yōu)解 －－線段 AB上的所有點都是最優(yōu)點 ， 它們都使目標(biāo)函數(shù)取得相同的最大值Zmax=14。 無界解 121212242,0xxxxxx????????≤≤≥12m ax Z x x??2 4 0 6 x2 1 2 5 4 3 x1 如圖中可行域是一個無界區(qū)域 ， 如陰影區(qū)所示 。 虛線為目表函數(shù)等值線 ， 沿著箭頭指的方向平移可以使目標(biāo)函數(shù)值無限制地增大 ， 但是找不到最優(yōu)解 。 這種情況通常稱為 無 “ 有限最優(yōu)解 ” 或 “ 最優(yōu)解無界 ” 。 如果一個實際問題抽象成像例 14這樣的線性規(guī)劃模型 ， 比如是一個生產(chǎn)計劃問題 ， 其經(jīng)濟(jì)含義就是某些資源是無限的 ， 產(chǎn)品的產(chǎn)量可以無限大 。 此時應(yīng)重新檢查和修改模型 ， 否則就沒有實際意義 。 注意 ， 對于無界可行域的情況 ， 也可能有唯一最優(yōu)解或無窮多個最優(yōu)解 。 1947年 單純形法 提供了方便 、 有效的通用算法求解線性規(guī)劃 。 2 單純形法 一、單純形法的基本思想 頂點的逐步轉(zhuǎn)移 即從可行域的一個頂點（基本可行解）開始，轉(zhuǎn)移到另一個頂點（另一個基本可行解）的迭代過程， 轉(zhuǎn)移的條件 是使目標(biāo)函數(shù)值得到改善（逐步變優(yōu)），當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時，問題也就得到了最優(yōu)解。 2． 需要解決的問題： (1)為了使目標(biāo)函數(shù)逐步變優(yōu) ， 怎么轉(zhuǎn)移 ？ (2)目標(biāo)函數(shù)何時達(dá)到最優(yōu) —— 判斷標(biāo)準(zhǔn)是什么 ？ 二、單純形法原理（用代數(shù)方法求解 LP） 例： ??????????????0,1241648232m a x21212121xxxxxxxxZ第一步：引入非負(fù)的松弛變量和剩余變量 x3,x4,x5, 將該 LP化為標(biāo)準(zhǔn)型 1 2 3 4 51 2 31425m a x 2 3 0 0 0284 164 120 , 1 , 2 , , 5jZ x x x x xx x xxxxxxj? ? ? ? ?? ? ??????????? ??≥第二步：尋求初始可行基 ， 確定基變量 對應(yīng)的基變量是 x3 x4 x5 第三步：寫出初始基本可行解和相應(yīng)的 目標(biāo)函數(shù)值 1 2 3 4 51 2 1 0 0( ) 4 0 0 1 00 4 0 0 1??????????， ， ， ，A P P P P P兩個關(guān)鍵的基本表達(dá)式： ① 用非基變量表示基變量的表達(dá)式 T X (0,0,8,16,12) ) 0 ( ? ? 初始基本可行解 3 1 24152821 6 41 2 4x x xxxxx? ? ?????② 用非基變量表示目標(biāo)函數(shù)的表達(dá)式 請解釋結(jié)果的經(jīng)濟(jì)含義 —— 不生產(chǎn)任何產(chǎn)品，資源全部節(jié)余（ x3=8 x4=16， x5=12），產(chǎn)品的總利潤為 0！ 12m a x 2 3Z x x??0 ) 0 ( ? Z 當(dāng)前的目標(biāo)函數(shù)值 第四步：分析兩個基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？ ① 分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式 非基變量前面的系數(shù)均為正數(shù)，所以任何一個非基變量進(jìn)基都能使 Z值增加 通常把非基變量前面的系數(shù)叫“檢驗數(shù)” ； 12m a x 2 3Z x x??② 選哪一個非基變量進(jìn)基？ 選 x1為 進(jìn)基變量 （ 換入變量 ） 問題討論： 能否選