1、目目 標(biāo)標(biāo) 規(guī)規(guī) 劃劃(Goal programming)2.目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法3.目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的單純形法1.目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃概述5. Lingo求解求解4. 應(yīng)用問題舉例應(yīng)用問題舉例11運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 引引例例1 1 某工廠生產(chǎn)某工廠生產(chǎn)，兩種產(chǎn)品，已知有關(guān)兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。 解：這是求獲利最大的單目標(biāo)的規(guī)劃問題，用解：這是求獲利最大的單目標(biāo)的規(guī)劃問題，用x1，x2分別表示分別表示，產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為：表述為：0,102

2、112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：21運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 用圖解法求得最優(yōu)決策方案為：用圖解法求得最優(yōu)決策方案為：x1*=4, x2*=3, z*=62(元元)。(4,3)0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)函數(shù)：31運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 ( (IVIV) )應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)：應(yīng)盡可能達(dá)到并超過計(jì)劃利潤指標(biāo)：5656元。元。這樣的產(chǎn)品決策問題便構(gòu)成了一個(gè)多目標(biāo)決策問題，目標(biāo)規(guī)劃方法正是解這類決策問題的方法之一。實(shí)際上，工廠在作決策時(shí)，需要考慮包括

3、市場因素在內(nèi)等一系列實(shí)際上，工廠在作決策時(shí)，需要考慮包括市場因素在內(nèi)等一系列條件。例如條件。例如:(I)根據(jù)市場信息，產(chǎn)品根據(jù)市場信息，產(chǎn)品的銷售量有下降的趨勢，因而的銷售量有下降的趨勢，因而希望產(chǎn)品希望產(chǎn)品的產(chǎn)量的產(chǎn)量不應(yīng)大于不應(yīng)大于產(chǎn)品產(chǎn)品。(II)當(dāng)超過計(jì)劃供應(yīng)原材料時(shí)，需用高價(jià)采購，會使成本當(dāng)超過計(jì)劃供應(yīng)原材料時(shí)，需用高價(jià)采購，會使成本大幅度增加。大幅度增加。(III)應(yīng)盡可能充分利用設(shè)備臺時(shí)，但不希望加班。應(yīng)盡可能充分利用設(shè)備臺時(shí)，但不希望加班。41運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟(jì)管理中

4、多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。中多目標(biāo)決策的需要而逐步發(fā)展起來的一個(gè)分支。 1 1、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約、線性規(guī)劃只討論一個(gè)線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可束條件下的極值問題；而目標(biāo)規(guī)劃是多個(gè)目標(biāo)決策，可求得更切合實(shí)際的解。求得更切合實(shí)際的解。1 目標(biāo)規(guī)劃概述目標(biāo)規(guī)劃概述（一）目標(biāo)規(guī)劃與線性規(guī)劃的比較（一）目標(biāo)規(guī)劃與線性規(guī)劃的比較線性規(guī)劃建模的局限性：線性規(guī)劃建模的局限性： 線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實(shí)線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實(shí)際問題中并非所有約束都需要嚴(yán)格的滿足；際問題中并

5、非所有約束都需要嚴(yán)格的滿足；51運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 2 2、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)、線性規(guī)劃求最優(yōu)解；目標(biāo)規(guī)劃是找到一個(gè)滿意解滿意解。 線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問題，而對一些次目標(biāo)只線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問題，而對一些次目標(biāo)只能轉(zhuǎn)化為約束處理。但在實(shí)際問題中，目標(biāo)和約束好似可以能轉(zhuǎn)化為約束處理。但在實(shí)際問題中，目標(biāo)和約束好似可以相互轉(zhuǎn)化的，處理時(shí)不一定要嚴(yán)格區(qū)分；相互轉(zhuǎn)化的，處理時(shí)不一定要嚴(yán)格區(qū)分； 線性規(guī)劃在處理問題時(shí)，將各個(gè)約束線性規(guī)劃在處理問題時(shí)，將各個(gè)約束(也可看作目標(biāo)也可看作目標(biāo))的地的地位看成同等重要，而在實(shí)際問題中，各個(gè)目標(biāo)的重要

6、性即位看成同等重要，而在實(shí)際問題中，各個(gè)目標(biāo)的重要性即有層次上的差別，也有在同一層次上不同權(quán)重的差別有層次上的差別，也有在同一層次上不同權(quán)重的差別61運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 4 4、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花、線性規(guī)劃的最優(yōu)解是絕對意義下的最優(yōu)，但需花去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只去大量的人力、物力、財(cái)力才能得到；實(shí)際過程中，只要求得滿意解，就能滿足需要（或更能滿足需要）。要求得滿意解，就能滿足需要（或更能滿足需要）。 3 3、線性規(guī)劃中的約束條件是同等重要的，是硬約束；、線性規(guī)劃中的約束條件是同等重要的，是硬約束；而目標(biāo)規(guī)劃中有輕重緩急

7、和主次之分，即有優(yōu)先權(quán)。而目標(biāo)規(guī)劃中有輕重緩急和主次之分，即有優(yōu)先權(quán)。目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營管理、市場目前，已經(jīng)在經(jīng)濟(jì)計(jì)劃、生產(chǎn)管理、經(jīng)營管理、市場分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。分析、財(cái)務(wù)管理等方面得到了廣泛的應(yīng)用。71運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 目標(biāo)值和偏差變量目標(biāo)值和偏差變量 目標(biāo)約束和絕對約束目標(biāo)約束和絕對約束 達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)） 優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) 滿意解（具有層次意義的解）滿意解（具有層次意義的解）（二）目標(biāo)規(guī)劃的基本概念（二）目標(biāo)規(guī)劃的基本概念81

8、運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)目標(biāo)規(guī)劃通過引入目標(biāo)值和偏差變量，可以將目標(biāo)函數(shù)轉(zhuǎn)化為目標(biāo)約束。函數(shù)轉(zhuǎn)化為目標(biāo)約束。 目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。目標(biāo)值：是指預(yù)先給定的某個(gè)目標(biāo)的一個(gè)期望值。 實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量實(shí)現(xiàn)值或決策值：是指當(dāng)決策變量xj 選定以后，目選定以后，目標(biāo)函數(shù)的對應(yīng)值。標(biāo)函數(shù)的對應(yīng)值。 偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值偏差變量（事先無法確定的未知數(shù)）：是指實(shí)現(xiàn)值和目標(biāo)值之間的差異和目標(biāo)值之間的差異, ,記為記為 d d 。 正偏差變量：表示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為正偏差變量：表

9、示實(shí)現(xiàn)值超過目標(biāo)值的部分，記為 d d。 負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記負(fù)偏差變量：表示實(shí)現(xiàn)值未達(dá)到目標(biāo)值的部分，記為為 d d。1 1、目標(biāo)值和偏差變量、目標(biāo)值和偏差變量91運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：當(dāng)完成或超額完成規(guī)定的指標(biāo)則表示：d d0, d d0 當(dāng)未完成規(guī)定的指標(biāo)則表示：當(dāng)未完成規(guī)定的指標(biāo)則表示： d d0, d d0 當(dāng)恰好完成指標(biāo)時(shí)則表示：當(dāng)恰好完成指標(biāo)時(shí)則表示： d d0, d d0 d d d d 0 0 成立。成立。 引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問引入了目標(biāo)值和正、負(fù)偏差變量后，就對某一問題有

10、了新的限制，既目標(biāo)約束。題有了新的限制，既目標(biāo)約束。 目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束目標(biāo)約束即可對原目標(biāo)函數(shù)起作用，也可對原約束起作用。起作用。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。目標(biāo)約束是目標(biāo)規(guī)劃中特有的，是軟約束。在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)在一次決策中，實(shí)現(xiàn)值不可能既超過目標(biāo)值又未達(dá)到目標(biāo)值，故有到目標(biāo)值，故有 d d d d 0,0,并規(guī)定并規(guī)定d d0, d d02 2、目標(biāo)約束和絕對約束、目標(biāo)約束和絕對約束101運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 絕對約束（系統(tǒng)約束）是指絕對約束（系統(tǒng)約束）是指必須嚴(yán)格滿足的等式或不等式必須嚴(yán)格滿足的等式或

11、不等式約束。如線性規(guī)劃中的所有約約束。如線性規(guī)劃中的所有約束條件都是絕對約束，否則無束條件都是絕對約束，否則無可行解。所以，絕對約束是硬可行解。所以，絕對約束是硬約束。約束。線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需要將絕對約束變換為目標(biāo)約束，例如：在要將絕對約束變換為目標(biāo)約束，例如：在引例引例1中，目中，目標(biāo)值目標(biāo)函數(shù)可以轉(zhuǎn)換為標(biāo)值目標(biāo)函數(shù)可以轉(zhuǎn)換為目標(biāo)約束目標(biāo)約束，既，既0,102112108max21212121xxxxxxxxz滿足約束條件：目標(biāo)

12、函數(shù)：目標(biāo)函數(shù)目標(biāo)函數(shù) z=8x1+10 x2變換為目標(biāo)約束變換為目標(biāo)約束 8x1+10 x2+d1d1+=56約束條件約束條件 2x1+x211變換為目標(biāo)約束變換為目標(biāo)約束 2x1+x2+d 2 d2+=11111運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為達(dá)成函數(shù)是一個(gè)使總偏差量為最小的目標(biāo)函數(shù)，記為 minZ = f（d、d）。）。 一般說來，有以下三種情況，但只能出現(xiàn)其中之一：一般說來，有以下三種情況，但只能出現(xiàn)其中之一： .要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要要求恰好達(dá)到規(guī)定的目標(biāo)值，即正、負(fù)偏差變量要盡可能小，則盡可能小，則m

13、inZ = f（d d）。）。 .要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，也就是正偏差變量盡可能小，則正偏差變量盡可能小，則minZ = f（d）。）。 .要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，要求超過目標(biāo)值，即超過量不限，但不低于目標(biāo)值，也就是負(fù)偏差變量盡可能小，則也就是負(fù)偏差變量盡可能小，則minZ = f（d）。）。 對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即對于由絕對約束轉(zhuǎn)化而來的目標(biāo)函數(shù)，也照上述處理即可?？?。3 3、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）、達(dá)成函數(shù)（即目標(biāo)規(guī)劃中的目標(biāo)函數(shù)）121運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃

14、目標(biāo)規(guī)劃 優(yōu)先因子優(yōu)先因子Pk 是將決策目標(biāo)按其重要程度排序并表是將決策目標(biāo)按其重要程度排序并表示出來。示出來。P1P2PkPk+1PK ，k=1.2K。 權(quán)系數(shù)權(quán)系數(shù)k 區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，決策者可視具體情況而定。別，決策者可視具體情況而定。 對于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分對于這種解來說，前面的目標(biāo)可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，實(shí)現(xiàn)，而后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn)。有些可能就不能實(shí)現(xiàn)。4 4、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù)、優(yōu)先因子（優(yōu)先等級）與優(yōu)先權(quán)系數(shù) 5

15、 5、滿意解（具有層次意義的解）、滿意解（具有層次意義的解）131運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 某廠生產(chǎn)某廠生產(chǎn)、兩兩種產(chǎn)品，有關(guān)數(shù)據(jù)如表種產(chǎn)品，有關(guān)數(shù)據(jù)如表所示。所示。擁有量擁有量原材料原材料2111設(shè)備設(shè)備(臺時(shí)臺時(shí))1210單件利潤單件利潤810 經(jīng)研究提出下列要求：經(jīng)研究提出下列要求： 1、產(chǎn)品、產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量；的產(chǎn)量； 2、充分利用設(shè)備有效臺時(shí)，不加班；、充分利用設(shè)備有效臺時(shí)，不加班； 3、利潤不小于、利潤不小于 56 元。元。例例2：（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型（三）目標(biāo)規(guī)劃的數(shù)學(xué)模型解：設(shè)解：設(shè)x1， x2分別表示分別表示產(chǎn)品產(chǎn)品和和產(chǎn)品產(chǎn)

16、品的產(chǎn)量。的產(chǎn)量。 di+, di- 分別為第分別為第i個(gè)目標(biāo)的正、負(fù)偏差變量個(gè)目標(biāo)的正、負(fù)偏差變量建立目標(biāo)約束：建立目標(biāo)約束：產(chǎn)品產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量不低于產(chǎn)品的產(chǎn)量的產(chǎn)量:0 1121ddxx21 xx 141運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 102 2221ddxx561083321ddxx11 221xx充分利用設(shè)備有效臺時(shí)充分利用設(shè)備有效臺時(shí):利潤不小于利潤不小于 56 元元:原材料約束原材料約束:102 21xx5610821xx優(yōu)先等級優(yōu)先等級: : 第一目標(biāo)：第一目標(biāo)： 即產(chǎn)品即產(chǎn)品的產(chǎn)量不大于的產(chǎn)量不大于的產(chǎn)量。的產(chǎn)量。 11dP第二目標(biāo)：第二目標(biāo)：即充分利

17、用設(shè)備有效臺時(shí)，不加班即充分利用設(shè)備有效臺時(shí)，不加班)(222ddP第三目標(biāo)：第三目標(biāo)：即利潤不小于即利潤不小于 56 元元33dP151運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 達(dá)成函數(shù)：達(dá)成函數(shù)：)3,2, 1( 0 ,0,11 256108102 0 )(min21213321222111213322211iddxxxxddxxddxxddxxdPddPdPZii目標(biāo)規(guī)劃模型：目標(biāo)規(guī)劃模型：3322211)(mindPddPdPZ161運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 )2 .1( 0 .n)1.2(j 0)2 .1( ).()2 .1( )(min1111Llddxmi

18、bxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk目標(biāo)規(guī)劃模型一般形式目標(biāo)規(guī)劃模型一般形式171運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 建模的建模的步驟步驟 1 1、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定、根據(jù)要研究的問題所提出的各目標(biāo)與條件，確定目標(biāo)值，列出目標(biāo)約束與絕對約束；目標(biāo)值，列出目標(biāo)約束與絕對約束； klkl和和 4 4、對同一優(yōu)先等級中的各偏差變量，若需要可按其對同一優(yōu)先等級中的各偏差變量，若需要可按其重要程度的不同，賦予相應(yīng)的權(quán)系數(shù)重要程度的不同，賦予相應(yīng)的權(quán)系數(shù) 。 3 3、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子、給各目標(biāo)賦予相應(yīng)的優(yōu)先因子 P

19、 Pk k（k=1.2K）。）。 2 2、可根據(jù)決策者的需要，將某些或全部絕對約束、可根據(jù)決策者的需要，將某些或全部絕對約束轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對約束加上負(fù)偏差轉(zhuǎn)化為目標(biāo)約束。這時(shí)只需要給絕對約束加上負(fù)偏差變量和減去正偏差變量即可。變量和減去正偏差變量即可。181運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 5 5、根據(jù)決策者的要求，按下列情況之一、根據(jù)決策者的要求，按下列情況之一llddldld. .恰好達(dá)到目標(biāo)值，取恰好達(dá)到目標(biāo)值，取 。. .允許超過目標(biāo)值，取允許超過目標(biāo)值，取 。. .不允許超過目標(biāo)值，取不允許超過目標(biāo)值，取 。構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的

20、，要構(gòu)造一個(gè)由優(yōu)先因子和權(quán)系數(shù)相對應(yīng)的偏差變量組成的，要求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。求實(shí)現(xiàn)極小化的目標(biāo)函數(shù)，即達(dá)成函數(shù)。191運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 小結(jié)小結(jié)線性規(guī)劃線性規(guī)劃LPLP目標(biāo)規(guī)劃目標(biāo)規(guī)劃GPGP目標(biāo)函數(shù)目標(biāo)函數(shù)min , max系數(shù)可正負(fù)系數(shù)可正負(fù)min , 偏差變量偏差變量系數(shù)系數(shù)0 0變量變量xi, xs xa xi xs xa d約束條件約束條件系統(tǒng)約束系統(tǒng)約束（絕對約束）（絕對約束）目標(biāo)約束目標(biāo)約束系統(tǒng)約束系統(tǒng)約束解解最優(yōu)最優(yōu)最滿意最滿意201運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 圖解法同樣適用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操圖解法同樣適

21、用兩個(gè)變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時(shí)，也有助于理解一般目作簡單，原理一目了然。同時(shí)，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。標(biāo)規(guī)劃的求解原理和過程。 圖解法解題步驟如下：圖解法解題步驟如下： 1、確定各約束條件的可行域，即將所有約束條件、確定各約束條件的可行域，即將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）（包括目標(biāo)約束和絕對約束，暫不考慮正負(fù)偏差變量）在坐標(biāo)平面上表示出來；在坐標(biāo)平面上表示出來；2 目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的圖解法 2、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負(fù)偏差變量值增大的方向；負(fù)偏差變

22、量值增大的方向；211運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 5、重復(fù)、重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止；止；3、求滿足最高優(yōu)先等級目標(biāo)的解；、求滿足最高優(yōu)先等級目標(biāo)的解；4、轉(zhuǎn)到下一個(gè)優(yōu)先等級的目標(biāo)，再不破壞所有較高、轉(zhuǎn)到下一個(gè)優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解；優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解； 6、確定最優(yōu)解和滿意解。、確定最優(yōu)解和滿意解。221運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 某電視機(jī)廠裝配黑白和彩色電視機(jī)，每裝配一臺某電視機(jī)廠裝配黑白和彩色電視機(jī)，每裝配一臺電視

23、機(jī)需占用裝配線電視機(jī)需占用裝配線1 1小時(shí)，裝配線每周計(jì)劃開動小時(shí)，裝配線每周計(jì)劃開動4040小時(shí)。預(yù)計(jì)市場每周彩色電視機(jī)的銷量是小時(shí)。預(yù)計(jì)市場每周彩色電視機(jī)的銷量是2424臺，臺，每臺可獲利每臺可獲利8080元；黑白電視機(jī)的銷量是元；黑白電視機(jī)的銷量是3030臺，每臺臺，每臺可獲利可獲利4040元。該企業(yè)決策者確定的目標(biāo)為：元。該企業(yè)決策者確定的目標(biāo)為： 第一優(yōu)先級：充分利用裝配線每周計(jì)劃開動第一優(yōu)先級：充分利用裝配線每周計(jì)劃開動40小時(shí)；小時(shí)； 第二優(yōu)先級：允許裝配線加班；但加班時(shí)間每周盡第二優(yōu)先級：允許裝配線加班；但加班時(shí)間每周盡量不超過量不超過10小時(shí)；小時(shí)； 第三優(yōu)先級：裝配電視機(jī)的

24、數(shù)量盡量滿足市場需要。第三優(yōu)先級：裝配電視機(jī)的數(shù)量盡量滿足市場需要。因彩色電視機(jī)的利潤高，取其權(quán)數(shù)為因彩色電視機(jī)的利潤高，取其權(quán)數(shù)為2。 試建立該問題的目標(biāo)規(guī)劃模型，并求解試建立該問題的目標(biāo)規(guī)劃模型，并求解黑白和彩色黑白和彩色電視機(jī)的產(chǎn)量。電視機(jī)的產(chǎn)量。例例3231運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 A010 20 30 40 50 60 70 80 10 20 30 40 50 60 x2 x1B1d1d2d2dC 3d 3d 4d 4dDEFHGE(24 ,26)E(24 ,26)為所求的滿意解。為所求的滿意解。)41(0, 0,302450 40)2(min2144233122

25、2111214332211iddxxddxddxddxxddxxddPdPdPZii解：設(shè)解：設(shè)x1， x2分別表示彩色和黑白電視機(jī)的產(chǎn)量。分別表示彩色和黑白電視機(jī)的產(chǎn)量。241運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 線段上線段上的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。的所有點(diǎn)均是該問題的解（無窮多最優(yōu)解）。 )2 . 1(0, 0,8 2 102 5 .621210)(min21212221112122111ldd

26、xxxxddxxddxxdPddPZll例例4、用圖解法求解目標(biāo)規(guī)劃問題、用圖解法求解目標(biāo)規(guī)劃問題251運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 例例5、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為、已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為 01006014021230max21212121xxxxxxxZ)( )( )( 丙丙資資源源乙乙資資源源甲甲資資源源 其中目標(biāo)函數(shù)為總利潤，其中目標(biāo)函數(shù)為總利潤，x1,x2 為產(chǎn)品為產(chǎn)品A、B產(chǎn)量。現(xiàn)產(chǎn)量?，F(xiàn)有下列目標(biāo)：有下列目標(biāo)： 1、要求總利潤必須超過、要求總利潤必須超過 2500 元；元； 2、考慮產(chǎn)品受市場影響，為避免積壓，、考慮產(chǎn)品受市場影響，為避免積壓，A

27、、B的生產(chǎn)生產(chǎn)量不超過量不超過 60 件和件和 100 件；件； 3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。261運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 解：以產(chǎn)品解：以產(chǎn)品 A A、B B 的單件利潤比的單件利潤比 2.5 2.5 ：1 1 為權(quán)系數(shù)，為權(quán)系數(shù)，模型模型如下：如下： )4 .3 .2 .1(0,010060140225001230)5 .2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 2

28、71運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 0 x2 0 x11401201008060402020 40 60 80 1002d2d1d1d3d3d4d4dABCD 結(jié)論：結(jié)論：C(60 ,58.3)C(60 ,58.3)為所求的滿意解。為所求的滿意解。作圖：作圖： ) 4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 281運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 檢驗(yàn)：將上述結(jié)果帶入模型，因檢驗(yàn)：將上述結(jié)果帶入模型，因 0； 0； 0，

29、 存在；存在； 0， 存在。所以，存在。所以，有下式：有下式： min Z=P3 2d2d1d1d3d3d4d4d 將將 x160， x2 58.3 帶入約束條件，得帶入約束條件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。說明第說明第k k個(gè)優(yōu)先等級的目標(biāo)尚個(gè)優(yōu)先等級的目標(biāo)尚未達(dá)到未達(dá)到, ,必須檢查必須檢查Pk這一的檢驗(yàn)數(shù)這一的檢驗(yàn)數(shù)kj(j=1.2n+2m).(j=1.2n+2m).若若Pk這這一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）一行某些負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改

30、進(jìn)，轉(zhuǎn)沒有正檢驗(yàn)數(shù)，說明未得到滿意解，應(yīng)繼續(xù)改進(jìn)，轉(zhuǎn)到第到第3 3步；若步；若Pk這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高這一行全部負(fù)檢驗(yàn)數(shù)的同列上面（較高優(yōu)先等級）都有正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已優(yōu)先等級）都有正檢驗(yàn)數(shù)，說明目標(biāo)雖沒達(dá)到，但已不能改進(jìn)，故得滿意解，轉(zhuǎn)到第不能改進(jìn)，故得滿意解，轉(zhuǎn)到第6 6步。步。 3 3、確定進(jìn)基變量。、確定進(jìn)基變量。 在在Pk行行，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，從那些上面沒有正檢驗(yàn)數(shù)的負(fù)檢驗(yàn)數(shù)中，選絕對值最大者，對應(yīng)的變量選絕對值最大者，對應(yīng)的變量xs就是進(jìn)基變量。若就是進(jìn)基變量。若Pk行行中有幾個(gè)相同的絕對值最大者，則依次比較它們各列中有幾個(gè)相同的絕對

31、值最大者，則依次比較它們各列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列下部的檢驗(yàn)數(shù)，取其絕對值最大的負(fù)檢驗(yàn)數(shù)的所在列的的xs為進(jìn)基變量。假如仍無法確定，則選最左邊的變量為進(jìn)基變量。假如仍無法確定，則選最左邊的變量（變量下標(biāo)小者）為進(jìn)基變量。（變量下標(biāo)小者）為進(jìn)基變量。331運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 4 4、確定出基變量、確定出基變量 其方法同線性規(guī)劃，即依據(jù)最小比值法則其方法同線性規(guī)劃，即依據(jù)最小比值法則故確定故確定xr為出基變量，為出基變量，arsrs為主元素。若有幾個(gè)相同的為主元素。若有幾個(gè)相同的行可供選擇時(shí)，選最上面那一行所對應(yīng)得變量為行可供選擇時(shí)，選最上面那一行

32、所對應(yīng)得變量為xr 。rsorisissiabaab 0/min 5 5、旋轉(zhuǎn)變換（變量迭代）。、旋轉(zhuǎn)變換（變量迭代）。 以為主元素進(jìn)行變換，得到新的單純形表，獲得一組以為主元素進(jìn)行變換，得到新的單純形表，獲得一組新解，返回到第新解，返回到第2 2步。步。 6 6、對求得的解進(jìn)行分析、對求得的解進(jìn)行分析 若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模若計(jì)算結(jié)果滿意，停止運(yùn)算；若不滿意，需修改模型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，型，即調(diào)整目標(biāo)優(yōu)先等級和權(quán)系數(shù)，或者改變目標(biāo)值，重新進(jìn)行第重新進(jìn)行第1 1步。步。341運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 )4 . 3 . 2 .

33、 1( 0, 0100 60 140 2 250012305 . 2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例例6、用單純形法求解下列目標(biāo)規(guī)劃問題、用單純形法求解下列目標(biāo)規(guī)劃問題351運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 CjCBXBbx1x21d1d2d2d3d3d4d4d= min2500/30,140/2,60/1=60 ,故故 為換出變量。為換出變量。3di00P100P302.5P20P230121-100000021001-100001000001-100010000001-1)4.3.2.1( 0,0

34、100 60 140 2 250012305.2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll2500140601001d2d3d4dP1000P1P2P332111111003030)1000102030(0PPPPPacciB -3000-120000000000000010000102.50010-2500002500/30140/260/1/361運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x16

35、0100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10 ,故故 為換出變量。為換出變量。2d371運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2

36、 -250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故故 為換出變量。為換出變量。3d1d381運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/

37、301/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 為換出變量。為換出變量。2d3d3d391運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/1

38、2101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中3115/30，說明說明P3 優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，優(yōu)先等級目標(biāo)沒有實(shí)現(xiàn)，但已無法改進(jìn)，得到滿意解得到滿意解 x1 60， x2 175/3， 115/3， 125/3。4d2d401運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)結(jié)果分析：計(jì)算結(jié)果表明，工廠應(yīng)生產(chǎn)A產(chǎn)品產(chǎn)品60件，件，B產(chǎn)品產(chǎn)品175/3件，件，2500元的利潤目標(biāo)剛好達(dá)到。元的利潤目標(biāo)剛好達(dá)到。 125/3，表明產(chǎn)品比最高限額少，表明產(chǎn)品比最高限額少125/3件，滿足要求。件，滿足要求。 115/3 表明甲

39、資源超過庫存表明甲資源超過庫存115/3公斤，該目標(biāo)沒有達(dá)公斤，該目標(biāo)沒有達(dá)到。到。 從表中還可以看到，從表中還可以看到，P3 的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高的檢驗(yàn)數(shù)還有負(fù)數(shù)，但其高等級的檢驗(yàn)數(shù)卻是正數(shù)，要保證等級的檢驗(yàn)數(shù)卻是正數(shù)，要保證 P1目標(biāo)實(shí)現(xiàn)，目標(biāo)實(shí)現(xiàn)，P3等級等級目標(biāo)則無法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存目標(biāo)則無法實(shí)現(xiàn)。所以，按現(xiàn)有消耗水平和資源庫存量，無法實(shí)現(xiàn)量，無法實(shí)現(xiàn)25002500元的利潤目標(biāo)。元的利潤目標(biāo)。 可考慮如下措施：降低可考慮如下措施：降低A、B產(chǎn)品對甲資源的消耗產(chǎn)品對甲資源的消耗量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變量，以滿足現(xiàn)有甲資源庫存量的目標(biāo)；或改變P3等

40、級目等級目標(biāo)的指標(biāo)值，增加甲資源標(biāo)的指標(biāo)值，增加甲資源115/3115/3公斤。公斤。 若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等若很難實(shí)現(xiàn)上述措施，則需改變現(xiàn)有目標(biāo)的優(yōu)先等級，以取得可行的滿意結(jié)果。級，以取得可行的滿意結(jié)果。4d2d411運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 4 應(yīng)用舉例應(yīng)用舉例例例7（人事問題）（人事問題）某單位領(lǐng)導(dǎo)在考慮本單位職工的升某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時(shí)，依次遵守以下規(guī)定：級調(diào)資方案時(shí)，依次遵守以下規(guī)定：1、不超過年工資總額、不超過年工資總額60000元；元；2、每級的人數(shù)不超過定編規(guī)定的人數(shù)；、每級的人數(shù)不超過定編規(guī)定的人數(shù)；3、II，I

41、II級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無越級提升；，且無越級提升；4、III級級不足編制的人數(shù)可錄用新職工，又不足編制的人數(shù)可錄用新職工，又I級級職工中有職工中有10%要退休要退休。有關(guān)資料匯總于下表，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個(gè)滿意的方案。有關(guān)資料匯總于下表，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個(gè)滿意的方案。等級等級工資額（元工資額（元/年）年） 現(xiàn)有人數(shù)現(xiàn)有人數(shù)編制人數(shù)編制人數(shù)IIIIII200015001000101215121515合計(jì)合計(jì)3742421運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 解：設(shè)解：設(shè)x1， x2 ， x3分別表示提升分別表示提升I，II級和錄用

42、到級和錄用到III級的級的新職工人數(shù)。新職工人數(shù)。 di+, di-分別為第分別為第i個(gè)目標(biāo)的負(fù)、正偏差變量個(gè)目標(biāo)的負(fù)、正偏差變量第一優(yōu)先級第一優(yōu)先級P1：不超過年工資總額不超過年工資總額60000元；元；第二優(yōu)先級第二優(yōu)先級P2 ：每級的人數(shù)不超過定編規(guī)定的人數(shù)；每級的人數(shù)不超過定編規(guī)定的人數(shù)；第三優(yōu)先級第三優(yōu)先級P3 ： II，III級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。確定優(yōu)先因子：確定優(yōu)先因子：60000)15(1000)12(1500)1 . 01010(20001132211 ddxxxxx建立目標(biāo)約束：建立目標(biāo)約束：年工資總額不超過年工資總額不超過6

43、0000元元每級的人數(shù)不超過定編規(guī)定的人數(shù)：每級的人數(shù)不超過定編規(guī)定的人數(shù)：對對I級級有：有：12)1 . 01010(221 ddx對對II級有：級有：15123321 ddxx對對III級有：級有：15154432 ddxx431運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 II，III級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%：達(dá)成函數(shù)：達(dá)成函數(shù)：對對II級有：級有：2.012551 ddx對對III級有：級有：2 . 015662 ddx)()(min653432211 ddPdddPdPZ目標(biāo)規(guī)劃模型：目標(biāo)規(guī)劃模型： )61(0,0,34.2033475.05

44、.0)()(min3216625514432332122111321653432211iddxxxddxddxddxxddxxddxddxxxddPdddPdPZii第一優(yōu)先級第一優(yōu)先級P1：不超過年工資總額不超過年工資總額60000元；元；第二優(yōu)先級第二優(yōu)先級P2 ：每級的人數(shù)不超過定編規(guī)定的人數(shù)；每級的人數(shù)不超過定編規(guī)定的人數(shù)；第三優(yōu)先級第三優(yōu)先級P3 ： II，III級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的級的升級面盡可能達(dá)到現(xiàn)有人數(shù)的20%。441運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 用用單純形法求解得多重解，如下表單純形法求解得多重解，如下表變量變量含義含義解解1解解2解解3解解4x1

45、x2x3d1-d2-d3-d4-d5+d6+晉升到晉升到I的人數(shù)的人數(shù)晉升到晉升到II的人數(shù)的人數(shù)新招收新招收III的人數(shù)的人數(shù)工資總額的結(jié)余額工資總額的結(jié)余額I級缺編人數(shù)級缺編人數(shù)II級缺編人數(shù)級缺編人數(shù)III級缺編人數(shù)級缺編人數(shù)II級超編人數(shù)級超編人數(shù)III級超編人數(shù)級超編人數(shù)2.43063000.62.43002.43333000.62.40003333000030.60035500100.62451運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 目標(biāo)約束中偏差變量的選擇目標(biāo)約束中偏差變量的選擇 目前的有關(guān)目標(biāo)規(guī)劃的文獻(xiàn)往往給人們這目前的有關(guān)目標(biāo)規(guī)劃的文獻(xiàn)往往給人們這樣一種印象，似乎模型中

46、目標(biāo)約束中的正樣一種印象，似乎模型中目標(biāo)約束中的正負(fù)偏差變量要成對出現(xiàn)。而實(shí)際上決策者負(fù)偏差變量要成對出現(xiàn)。而實(shí)際上決策者在解決實(shí)際多目標(biāo)決策問題時(shí)，模型中目在解決實(shí)際多目標(biāo)決策問題時(shí)，模型中目標(biāo)約束中的正負(fù)偏差變量可能只出現(xiàn)一個(gè)標(biāo)約束中的正負(fù)偏差變量可能只出現(xiàn)一個(gè)（正偏變量或負(fù)偏差變量）或成對出現(xiàn)。（正偏變量或負(fù)偏差變量）或成對出現(xiàn)。目標(biāo)約束中偏差變量的正確選擇對于多目目標(biāo)約束中偏差變量的正確選擇對于多目標(biāo)決策問題的求解結(jié)果有很大的影響，決標(biāo)決策問題的求解結(jié)果有很大的影響，決策者應(yīng)該根據(jù)實(shí)際決策情況選擇目標(biāo)約束策者應(yīng)該根據(jù)實(shí)際決策情況選擇目標(biāo)約束中的偏差變量中的偏差變量. .461運(yùn)籌學(xué)運(yùn)籌

47、學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 例例8 某企業(yè)在計(jì)劃期內(nèi)生產(chǎn)兩種產(chǎn)品。每生產(chǎn)一某企業(yè)在計(jì)劃期內(nèi)生產(chǎn)兩種產(chǎn)品。每生產(chǎn)一件產(chǎn)品件產(chǎn)品1 1可以獲利可以獲利1212元，每生產(chǎn)一件產(chǎn)品元，每生產(chǎn)一件產(chǎn)品2 2可以獲可以獲利利1414元，生產(chǎn)一件產(chǎn)品元，生產(chǎn)一件產(chǎn)品1 1所需設(shè)備所需設(shè)備A A和設(shè)備和設(shè)備B B的臺時(shí)的臺時(shí)分別分別為為8 8臺時(shí)和臺時(shí)和1010臺時(shí)，生產(chǎn)一件產(chǎn)品臺時(shí)，生產(chǎn)一件產(chǎn)品2 2所需設(shè)備所需設(shè)備A A和設(shè)備和設(shè)備B B的臺時(shí)分別為的臺時(shí)分別為1010臺時(shí)和臺時(shí)和6 6臺時(shí)。設(shè)備臺時(shí)。設(shè)備A A和設(shè)和設(shè)備備B B的有效臺時(shí)分別為的有效臺時(shí)分別為15001500臺時(shí)和臺時(shí)和1000

48、1000臺時(shí)，該企臺時(shí)，該企業(yè)決策者確定的目標(biāo)優(yōu)先級為：業(yè)決策者確定的目標(biāo)優(yōu)先級為： 第一優(yōu)先級：實(shí)現(xiàn)利潤不低于第一優(yōu)先級：實(shí)現(xiàn)利潤不低于50005000元；元； 第二優(yōu)先級：充分利用設(shè)備第二優(yōu)先級：充分利用設(shè)備A A和設(shè)備和設(shè)備B B的有效臺時(shí)的有效臺時(shí) 問問: :如何安排產(chǎn)品如何安排產(chǎn)品1 1和產(chǎn)品和產(chǎn)品2 2的生產(chǎn)的生產(chǎn). .471運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 設(shè)產(chǎn)品設(shè)產(chǎn)品1 1的產(chǎn)量為的產(chǎn)量為x1，產(chǎn)品產(chǎn)品2 2的產(chǎn)量為的產(chǎn)量為x2 ，短期規(guī)劃決策目標(biāo)規(guī)劃模型為：短期規(guī)劃決策目標(biāo)規(guī)劃模型為：)(min32211ddPdPz0,1000610150010850001412

49、321213212211121dddxxdxxdxxddxx第一優(yōu)先級：實(shí)現(xiàn)利潤不低于第一優(yōu)先級：實(shí)現(xiàn)利潤不低于5000元；元；第二優(yōu)先級：充分利用設(shè)備第二優(yōu)先級：充分利用設(shè)備A和設(shè)備和設(shè)備B的有效臺時(shí)的有效臺時(shí)481運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 利用解目標(biāo)規(guī)劃的單純形法，模型的滿意解為，利用解目標(biāo)規(guī)劃的單純形法，模型的滿意解為， 其余變量為零，即產(chǎn)品其余變量為零，即產(chǎn)品1的產(chǎn)量的產(chǎn)量為為19.23單位單位,產(chǎn)品產(chǎn)品2的產(chǎn)量為的產(chǎn)量為134.62單位。可以驗(yàn)證，實(shí)際利潤為單位?？梢则?yàn)證，實(shí)際利潤為2115.38元元,第一優(yōu)先級的目標(biāo)沒有完成，設(shè)備第一優(yōu)先級的目標(biāo)沒有完成，設(shè)備A

50、和和設(shè)備設(shè)備B的有效臺時(shí)得到充分的利用的有效臺時(shí)得到充分的利用,第二優(yōu)先級的第二優(yōu)先級的目標(biāo)完成。這說明了在短期內(nèi)，即使現(xiàn)有設(shè)備的目標(biāo)完成。這說明了在短期內(nèi)，即使現(xiàn)有設(shè)備的生產(chǎn)能力得到充分的利用，仍然不能實(shí)現(xiàn)決策者生產(chǎn)能力得到充分的利用，仍然不能實(shí)現(xiàn)決策者所提出的利潤目標(biāo)。所提出的利潤目標(biāo)。 62.2884,62.134,23.191*2*1dxx491運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 與短期規(guī)劃決策目標(biāo)模型不同，因?yàn)樵O(shè)備的生產(chǎn)與短期規(guī)劃決策目標(biāo)模型不同，因?yàn)樵O(shè)備的生產(chǎn)能力在長期可以改變，長期規(guī)劃決策目標(biāo)規(guī)劃模能力在長期可以改變，長期規(guī)劃決策目標(biāo)規(guī)劃模型在設(shè)備生產(chǎn)能力目標(biāo)約束中同時(shí)

51、考慮了正負(fù)偏型在設(shè)備生產(chǎn)能力目標(biāo)約束中同時(shí)考慮了正負(fù)偏差變量，其模型為：差變量，其模型為： )(min32211ddPdPz0,100061015001085000141232132121332122211121ddddddxxddxxddxxddxx501運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 可以求出模型的滿意解為，可以求出模型的滿意解為， 其余變量為零，即產(chǎn)品其余變量為零，即產(chǎn)品1 1的產(chǎn)量為的產(chǎn)量為416.67416.67單位，不單位，不生產(chǎn)產(chǎn)品生產(chǎn)產(chǎn)品2 2，兩個(gè)優(yōu)先級的目標(biāo)都得到完成。由兩，兩個(gè)優(yōu)先級的目標(biāo)都得到完成。由兩個(gè)正偏差變量的值可以看出：從長期來看，要實(shí)個(gè)正偏差變量

52、的值可以看出：從長期來看，要實(shí)現(xiàn)決策者既定的利潤目標(biāo)，現(xiàn)有設(shè)備現(xiàn)決策者既定的利潤目標(biāo)，現(xiàn)有設(shè)備A A的生產(chǎn)能力的生產(chǎn)能力應(yīng)該應(yīng)該由由15001500臺時(shí)增加臺時(shí)增加到到3333.333333.33臺時(shí)臺時(shí), ,設(shè)備設(shè)備B B的生產(chǎn)的生產(chǎn)能力應(yīng)該由能力應(yīng)該由10001000臺時(shí)增加到臺時(shí)增加到4166.674166.67臺時(shí)。比較兩臺時(shí)。比較兩模型可以看出：目標(biāo)約束中偏差變量是單個(gè)出現(xiàn)模型可以看出：目標(biāo)約束中偏差變量是單個(gè)出現(xiàn)還是成對出現(xiàn)，對于模型的求解結(jié)果和求解結(jié)果還是成對出現(xiàn)，對于模型的求解結(jié)果和求解結(jié)果的分析有很大的影響。的分析有很大的影響。67.3166,33.1833,67.41632

53、*1ddx511運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 5 Lingo求解目標(biāo)規(guī)劃求解目標(biāo)規(guī)劃 求解目標(biāo)規(guī)劃的序貫式算法求解目標(biāo)規(guī)劃的序貫式算法其算法是根據(jù)優(yōu)先級的先后次序，將目標(biāo)規(guī)劃問題分解成一系列的單目標(biāo)規(guī)其算法是根據(jù)優(yōu)先級的先后次序，將目標(biāo)規(guī)劃問題分解成一系列的單目標(biāo)規(guī)劃問題，然后再依次求解。劃問題，然后再依次求解。算法算法5.1 對于對于k=1,2,q,求解單目標(biāo)問題求解單目標(biāo)問題; )(min1ljjkjjkjdwdwz,2, 1,),(.1mibxatsijnjij,2,1,0,2,1,0,1,2,1,)(,2,1,*11liddnjxkszdwdwligddxciijljj

54、sjjsjiiijnjij521運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 例例5.1 用Lingo求解： )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 531運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 解：用“序貫式”算法求求第一級目標(biāo)。寫出Lingo程序(程序名exam1.lg4)min=dminus1;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus

55、3-dplus3=60;x2+dminus4-dplus4=100;計(jì)算結(jié)果(只列出相關(guān)部分)為Global optimal solution found. Objective value: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost DMINUS1 0.000000 1.000000 X2 208.3333 0.000000目標(biāo)函數(shù)的最優(yōu)值為0，即第一級偏差為0。541運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 求第二級目標(biāo)。寫出Lingo程序(程序名exam2.lg4)min=2.5*dplus3+dpl

56、us4;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0;計(jì)算結(jié)果(只列出相關(guān)部分)為目標(biāo)函數(shù)的最優(yōu)值為0，即第二級偏差仍為0。Global optimal solution found. Objective value: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost X2 58.33333 0.000000551運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章

57、目標(biāo)規(guī)劃目標(biāo)規(guī)劃 求第三級目標(biāo)。寫出Lingo程序(程序名exam3.lg4)min=dplus2;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0; 2.5*dplus3+dplus4=0;計(jì)算結(jié)果(只列出相關(guān)部分)為目標(biāo)函數(shù)的最優(yōu)值為最優(yōu)值為38.333338.3333，第三級偏差為38.3333。得到滿意解：x1=60, x2=58.3333。Global optimal solution found. Object

58、ive value: 38.33333 Total solver iterations: 1 Variable Value Reduced Cost DPLUS2 38.33333 0.000000 X1 60.00000 0.000000 X2 58.33333 0.000000561運(yùn)籌學(xué)運(yùn)籌學(xué) 第四章第四章 目標(biāo)規(guī)劃目標(biāo)規(guī)劃 例例5.25.2 某計(jì)算機(jī)公司生產(chǎn)三種型號的筆記本電腦某計(jì)算機(jī)公司生產(chǎn)三種型號的筆記本電腦A A、B B、C C。這三。這三種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)1 1臺臺A A、B B和和C C型型號的筆記本電腦分別需

59、要號的筆記本電腦分別需要5 5小時(shí)、小時(shí)、8 8小時(shí)和小時(shí)和1212小時(shí)。公司裝配線小時(shí)。公司裝配線正常的生產(chǎn)時(shí)間是每月正常的生產(chǎn)時(shí)間是每月17001700小時(shí)。公司營業(yè)部門估計(jì)小時(shí)。公司營業(yè)部門估計(jì)A A、B B和和C C三三種筆記本電腦的利潤分別是每臺種筆記本電腦的利潤分別是每臺10001000元、元、14401440元和元和25202520元，而元，而公司預(yù)測這個(gè)月生產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考公司預(yù)測這個(gè)月生產(chǎn)的筆記本電腦能夠全部售出。公司經(jīng)理考慮：慮：P1:充分利用正常的生產(chǎn)能力，避免開工不足；充分利用正常的生產(chǎn)能力，避免開工不足；P2:優(yōu)先滿足老客戶的需求，優(yōu)先滿足老客戶

60、的需求，A、B和和C三種型號的電腦三種型號的電腦50、50和和80臺，同臺，同時(shí)根據(jù)三種電腦的純利潤分配不同的權(quán)因子；時(shí)根據(jù)三種電腦的純利潤分配不同的權(quán)因子；P3:限制裝配線的加班時(shí)間，盡量不超過限制裝配線的加班時(shí)間，盡量不超過200小時(shí)；小時(shí)；P4:滿足各種型號電腦的銷售目標(biāo)，滿足各種型號電腦的銷售目標(biāo)， A、B和和C型號的電腦分別為型號的電腦分別為100、120和和100臺，再根據(jù)三種電腦的純利潤分配不同的權(quán)因子；臺，再根據(jù)三種電腦的純利潤分配不同的權(quán)因子；P5:裝配線的加班時(shí)間盡可能少。裝配線的加班時(shí)間盡可能少。列出相應(yīng)的目標(biāo)規(guī)劃模型，并用列出相應(yīng)的目標(biāo)規(guī)劃模型，并用Lingo程序求解。