【正文】 目 標(biāo) 規(guī) 劃 (Goal programming) 5. Lingo求解 4. 應(yīng)用問題舉例 1 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ? 引 例 1 某工廠生產(chǎn) Ⅰ ， Ⅱ 兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。 ? 解：這是求獲利最大的單目標(biāo)的規(guī)劃問題，用 x1，x2分別表示 Ⅰ ， Ⅱ 產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為： Ⅰ Ⅱ 擁有量 原材料 (kg) 設(shè)備 (hr) 2 1 1 2 11 10 利潤 ( 元 / 件 ) 8 10 ????????????0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：2 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ? 用圖解法求得最優(yōu)決策方案為： x1*=4, x2*=3, z*=62(元 )。 (4,3) ????????????0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：3 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 (IV)應(yīng)盡可能達(dá)到并超過計劃利潤指標(biāo)： 56元。 這樣的產(chǎn)品決策問題便構(gòu)成了一個 多目標(biāo)決策問題 ，目標(biāo)規(guī)劃方法正是解這類決策問題的方法之一。 實際上，工廠在作決策時，需要考慮包括市場因素在內(nèi)等一系列條件。例如 : (I)根據(jù)市場信息，產(chǎn)品 Ⅰ 的銷售量有下降的趨勢，因而希望產(chǎn)品 Ⅰ 的產(chǎn)量 不應(yīng)大于 產(chǎn)品 Ⅱ 。 (II)當(dāng)超過計劃供應(yīng)原材料時，需用高價采購，會使成本大幅度增加。 (III)應(yīng)盡可能充分利用設(shè)備臺時，但不希望加班。 4 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中多目標(biāo)決策的需要而逐步發(fā)展起來的一個分支。 線性規(guī)劃只討論一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個目標(biāo)決策，可求得更切合實際的解。 1 目標(biāo)規(guī)劃概述 （一）目標(biāo)規(guī)劃與線性規(guī)劃的比較 線性規(guī)劃建模的局限性： ? 線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實際問題中并非所有約束都需要嚴(yán)格的滿足； 5 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個 滿意解 。 ? 線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問題，而對一些次目標(biāo)只能轉(zhuǎn)化為約束處理。但在實際問題中，目標(biāo)和約束好似可以相互轉(zhuǎn)化的，處理時不一定要嚴(yán)格區(qū)分； ? 線性規(guī)劃在處理問題時，將各個約束 (也可看作目標(biāo) )的地位看成同等重要，而在實際問題中，各個目標(biāo)的重要性即有層次上的差別，也有在同一層次上不同權(quán)重的差別 6 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財力才能得到；實際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。 線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。 目前，已經(jīng)在經(jīng)濟(jì)計劃、生產(chǎn)管理、經(jīng)營管理、市場分析、財務(wù)管理等方面得到了廣泛的應(yīng)用。 7 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ? 目標(biāo)值和偏差變量 ? 目標(biāo)約束和絕對約束 ? 達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)） ? 優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) ? 滿意解（具有層次意義的解） （二）目標(biāo)規(guī)劃的基本概念 8 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。 目標(biāo)值：是指預(yù)先給定的某個目標(biāo)的一個期望值。 實現(xiàn)值或決策值：是指當(dāng)決策變量 xj 選定以后，目標(biāo)函數(shù)的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：是指實現(xiàn)值和目標(biāo)值之間的差異 ,記為 d 。 正偏差變量：表示實現(xiàn)值超過目標(biāo)值的部分，記為 d＋ 。 負(fù)偏差變量：表示實現(xiàn)值未達(dá)到目標(biāo)值的部分，記為 d－ 。 目標(biāo)值和偏差變量 9 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示： d＋ ≥0, d－ ＝ 0 當(dāng)未完成規(guī)定的指標(biāo)則表示： d＋ ＝ 0, d－ ≥0 當(dāng)恰好完成指標(biāo)時則表示： d＋ ＝ 0, d－ ＝ 0 ∴ d＋ d－ ＝ 0 成立。 引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有了新的限制，既目標(biāo)約束。 目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。 目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。 在一次決策中，實現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有 d＋ d－ ＝ 0,并規(guī)定 d＋ ≥0, d－ ≥0 目標(biāo)約束和絕對約束 10 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無可行解。所以，絕對約束是硬約束。 線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需要將絕對約束變換為目標(biāo)約束，例如：在 引例 1中，目標(biāo)值目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束，既 ????????????0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：目標(biāo)函數(shù) z=8x1+10x2 變換為目標(biāo)約束 8x1+10x2+d1??d1+=56 約束條件 2x1+x2≤11 變換為目標(biāo)約束 2x1+x2+d 2 ??d2+=11 11 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 達(dá)成函數(shù)是一個使總偏差量為最小的目標(biāo)函數(shù)，記為 minZ = f（ d＋ 、 d－ ）。 一般說來，有以下三種情況，但只能出現(xiàn)其中之一： ⑴ .要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則 minZ = f（ d＋ ＋ d－ ）。 ⑵ .要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則 minZ = f（ d＋ ）。 ⑶ .要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則 minZ = f（ d－ ）。 對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可。 達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)） 12 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 優(yōu)先因子 Pk 是將決策目標(biāo)按其重要程度排序并表示出來。 P1P2…P kPk+1…P K ， k=…K 。 權(quán)系數(shù) ω k 區(qū)別具有相同優(yōu)先因子的兩個目標(biāo)的差別，決策者可視具體情況而定。 對于這種解來說，前面的目標(biāo)可以保證實現(xiàn)或部分實現(xiàn)，而后面的目標(biāo)就不一定能保證實現(xiàn)或部分實現(xiàn)，有些可能就不能實現(xiàn)。 優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) 滿意解（具有層次意義的解） 13 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 某廠生產(chǎn) Ⅰ 、 Ⅱ 兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。 Ⅰ Ⅱ 擁有量 原材料 2 1 11 設(shè)備 (臺時 ) 1 2 10 單件利潤 8 10 經(jīng)研究提出下列要求： 產(chǎn)品 Ⅱ 的產(chǎn)量不低于產(chǎn)品 Ⅰ 的產(chǎn)量； 充分利用設(shè)備有效臺時，不加班； 利潤不小于 56 元。 例 2： （三）目標(biāo)規(guī)劃的數(shù)學(xué)模型 解：設(shè) x1， x2分別表示 產(chǎn)品 Ⅰ 和 產(chǎn)品 Ⅱ 的產(chǎn)量。 di+, di 分別為第 i個目標(biāo)的正、負(fù)偏差變量 建立目標(biāo)約束： 產(chǎn)品 Ⅱ 的產(chǎn)量不低于產(chǎn)品 Ⅰ 的產(chǎn)量 : 0 1121 ?????? ddxx 21 xx ?14 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 102 2221 ???? ?? ddxx 561083321 ???? ?? ddxx 11 2 21 ?? xx充分利用設(shè)備有效臺時 : 利潤不小于 56 元 : 原材料約束 : 102 21 ?? xx 5610821 ?? xx優(yōu)先等級 : 第一目標(biāo)： 即產(chǎn)品 Ⅰ 的產(chǎn)量不大于 Ⅱ 的產(chǎn)量。 ?11dP第二目標(biāo)： 即充分利用設(shè)備有效臺時，不加班 )( 222 ?? ? ddP第三目標(biāo)： 即利潤不小于 56 元 ?33dP15 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 達(dá)成函數(shù)： ??????????????????????????????????????????)3,2,1( 0 ,0,11 256108102 0 )(m in21213321222111213322211iddxxxxddxxddxxddxxdPddPdPZii目標(biāo)規(guī)劃模型： ???? ???? 3322211 )(m in dPddPdPZ16 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ???????????????????????????????? ???????? ?)( 0 .n)(j 0)( ).()( )(m in111 1LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk??????目標(biāo)規(guī)劃模型一般形式 17 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 建模的 步驟 根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束； ??klkl ?? 和 對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。 給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 Pk（ k=…K ）。 可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。 18 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 根據(jù)決策者的要求，按下列情況之一 ?? ? ll dd?ld ?ld⑴ .恰好達(dá)到目標(biāo)值，取 。 ⑵ .允許超過目標(biāo)值，取 。 ⑶ .不允許超過目標(biāo)值，取 。 構(gòu)造一個由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。 19 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 小結(jié) 線性規(guī)劃 LP 目標(biāo)規(guī)劃 GP 目標(biāo)函數(shù) min , max 系數(shù)可正負(fù) min , 偏差變量 系數(shù) ≥0 變量 xi, xs xa xi xs xa d 約束條件 系統(tǒng)約束 （絕對約束） 目標(biāo)約束 系統(tǒng)約束 解 最優(yōu) 最滿意 20 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 圖解法同樣適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。 圖解法解題步驟如下： 確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來； 2 目標(biāo)規(guī)劃的圖解法 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向； 21 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 重復(fù) 4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止； 求滿足最高優(yōu)先等級目標(biāo)的解； 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解； 確定最優(yōu)解和滿意解。 22 1運(yùn)籌學(xué)》 第四章 目標(biāo)規(guī)劃 ? 某電視機(jī)廠裝配黑白和彩色電視機(jī)，每裝配一臺電視機(jī)需占用裝配線