1第三章目標(biāo)規(guī)劃2

線性規(guī)劃解決的都是單目標(biāo)優(yōu)化的問(wèn)題，但在實(shí)際的規(guī)劃中，還常常會(huì)遇到多個(gè)目標(biāo)的優(yōu)化問(wèn)題。目標(biāo)規(guī)劃（GoalProgramming）是解決多目標(biāo)優(yōu)化問(wèn)題的理論和方法。本章僅討論線性目標(biāo)規(guī)劃問(wèn)題，線性目標(biāo)規(guī)劃是一種特殊類型的線型規(guī)劃，它的特點(diǎn)是尋求使各目標(biāo)盡可能接近各預(yù)定期望值的滿意解。

3

目標(biāo)規(guī)劃由美國(guó)數(shù)學(xué)家Charnces和Cooper于1961年提出，他們?cè)谘芯坎豢尚蠰P問(wèn)題的近似解的時(shí)候形成這樣的概念。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，目標(biāo)規(guī)劃的應(yīng)用日益廣泛，在諸如企業(yè)管理、市場(chǎng)營(yíng)銷、交通運(yùn)輸、能源利用、醫(yī)療保健、綜合開(kāi)發(fā)等許多領(lǐng)域中，都取得了顯著的經(jīng)濟(jì)效益。4

§3-1數(shù)學(xué)模型

§3-2圖解法

§3-3擴(kuò)展單純形法

5§3-1數(shù)學(xué)模型一.基本思想目標(biāo)規(guī)劃方法的基本思想仍然是把多目標(biāo)化簡(jiǎn)成單目標(biāo)優(yōu)化的思路，但又不是簡(jiǎn)單的化簡(jiǎn)。其思路為：首先，對(duì)每一個(gè)目標(biāo)函數(shù)引進(jìn)一個(gè)期望值（預(yù)期希望達(dá)到的目標(biāo)值）。其次，由于受各種條件的限制與影響，各期望值往往不能同時(shí)正好達(dá)到，因此，引進(jìn)正負(fù)偏差量以描述目標(biāo)值超過(guò)或者低于期望值的程度；6

第三，因?yàn)楦髂繕?biāo)的重要程度不同，還要引進(jìn)各目標(biāo)的優(yōu)先級(jí)以及權(quán)重系數(shù)。最后，把所有的需要達(dá)到的目標(biāo)都化為相應(yīng)的約束方程，與原來(lái)的約束方程一起合并成新的約束條件。于是，多目標(biāo)優(yōu)化的問(wèn)題又變成了在新的約束條件下尋找各目標(biāo)值與希望目標(biāo)值之偏差最小解的單目標(biāo)優(yōu)化問(wèn)題。7二.基本步驟已知一目標(biāo)規(guī)劃問(wèn)題有j＝1，2，…，n個(gè)決策變量，i＝1，2，…，m個(gè)目標(biāo)的目標(biāo)規(guī)劃問(wèn)題，各目標(biāo)間共有個(gè)l＝1，2，…，r個(gè)優(yōu)先級(jí)別。根據(jù)目標(biāo)規(guī)劃的基本思想和方法，其建模的步驟可劃分為：（1）對(duì)各目標(biāo)引進(jìn)正、負(fù)偏差變量

為正偏差變量，表示第i個(gè)目標(biāo)超過(guò)期望值的盈余量；為負(fù)偏差變量，表示第i個(gè)目標(biāo)低于期望值的不足量。

很顯然，這兩個(gè)偏差量中至少有一個(gè)為0，即：用和分別表示達(dá)到i目標(biāo)的正、負(fù)偏差變量，其中：8（2）建立絕對(duì)約束和相對(duì)（目標(biāo)）約束方程由所給的目標(biāo)轉(zhuǎn)換成的約束方程稱為目標(biāo)約束，這類約束分為兩類：①絕對(duì)約束（也稱硬約束或剛性約束），該類約束是指必須不折不扣完成的約束，如用“＝”表示的約束：②相對(duì)約束（也稱為軟約束或柔性約束）是指希望盡可能去滿足的約束。如用“≤”

和“≥”表示的約束，這類約束可能正好滿足，也可能會(huì)出現(xiàn)差額，因此需引入正負(fù)偏差變量，如下式所示：注：硬約束也可以通過(guò)引入正負(fù)偏差量寫(xiě)成軟約束的形式：只要保證所引入的正負(fù)偏差變量同時(shí)為零便可保證該約束仍然是硬約束。9（3）確定目標(biāo)函數(shù)①目標(biāo)的優(yōu)先級(jí)別和權(quán)重系數(shù)由于多目標(biāo)中的各目標(biāo)有主次之分，所以在確定目標(biāo)函數(shù)的時(shí)候首先要根據(jù)各目標(biāo)的重要程度確定優(yōu)先級(jí)別，還要確定同一級(jí)目標(biāo)中不同變量的權(quán)重系數(shù)。不同級(jí)別的目標(biāo)重要性用優(yōu)先級(jí)別來(lái)表示。設(shè)Pk表示“第k級(jí)優(yōu)先級(jí)”，該符號(hào)僅表示對(duì)應(yīng)的目標(biāo)約束寫(xiě)入目標(biāo)函數(shù)中，但不能參加運(yùn)算。如果有k、q兩個(gè)層次的優(yōu)先級(jí)，且k<q，則Pk對(duì)應(yīng)的目標(biāo)重要性高于Pq對(duì)應(yīng)的目標(biāo)重要性，因此，只要Pk對(duì)應(yīng)的目標(biāo)實(shí)現(xiàn)后，才輪到考慮Pq所對(duì)應(yīng)的目標(biāo)。

10

由于同一個(gè)優(yōu)先級(jí)別中可以有多個(gè)目標(biāo)，那么，這些在同一優(yōu)先級(jí)別中的各目標(biāo)的重要程度也需要區(qū)別。同一級(jí)別中各目標(biāo)的重要程度用權(quán)重表示。設(shè)、為第k個(gè)優(yōu)先級(jí)別中第i個(gè)目標(biāo)正負(fù)偏差變量所對(duì)應(yīng)的權(quán)重系數(shù)，則該優(yōu)先級(jí)別中的某個(gè)目標(biāo)的權(quán)重可表示為：

11②目標(biāo)函數(shù)的通用表達(dá)形式

對(duì)于具有r個(gè)優(yōu)先級(jí)別，每個(gè)優(yōu)先級(jí)別最多有h個(gè)目標(biāo)的目標(biāo)規(guī)劃問(wèn)題，其目標(biāo)函數(shù)的通用表達(dá)形式為：③目標(biāo)函數(shù)的三種基本形式

根據(jù)目標(biāo)的不同要求，其在目標(biāo)函數(shù)中的表示形式可分為三種：

12★目標(biāo)要求超過(guò)期望值。即當(dāng)時(shí)，此時(shí)要求負(fù)偏差變量盡可能小，有：

其對(duì)應(yīng)的目標(biāo)函數(shù)可表示為：★目標(biāo)要求達(dá)到期望值，即當(dāng)時(shí)，此時(shí)要求正負(fù)偏差變量都盡可能小，有：和★目標(biāo)要求低于期望值。即當(dāng)時(shí)，此時(shí)要求正偏差變量盡可能小，有：和

其對(duì)應(yīng)的目標(biāo)函數(shù)可表示為：和

其對(duì)應(yīng)的目標(biāo)函數(shù)可表示為：13（4）基本數(shù)學(xué)表達(dá)式（數(shù)學(xué)模型）

綜上可得目標(biāo)規(guī)劃的一般形式可表示為：14三.范例例1某工廠生產(chǎn)A、B兩種產(chǎn)品，每種產(chǎn)品都需經(jīng)過(guò)甲、乙兩道工序，一直數(shù)據(jù)如表3-1所示：

根據(jù)市場(chǎng)預(yù)測(cè)、用戶合同及設(shè)備條件等情況，工廠做出如下考慮：

第一目標(biāo)：利潤(rùn)不小于165000元；第二目標(biāo)：兩道工序的加班費(fèi)用最?。话春贤a(chǎn)A、B產(chǎn)品工16000個(gè)。已知甲工序加班費(fèi)0.60元/min，乙工序加班費(fèi)0.72元/min，試建立工廠生產(chǎn)的數(shù)學(xué)模型。

工時(shí)產(chǎn)品工序AB最高總工時(shí)(分)甲2120000乙2336000單位產(chǎn)品利潤(rùn)（元）912表3-115解：確定決策變量以及原問(wèn)題的目標(biāo)函數(shù)及約束條件設(shè)A、B的產(chǎn)量為決策變量，分別用x1和x2表示，則根據(jù)題意可得：“利潤(rùn)不小于165000元”：“甲工序最高工時(shí)為20000”：“乙工序最高工時(shí)為36000”：

“共生產(chǎn)A、B產(chǎn)品16000個(gè)”：

“第二目標(biāo)－兩道工序的加班費(fèi)最小”在這里無(wú)法表示。

工時(shí)產(chǎn)品工序AB最高總工時(shí)(分)甲2120000乙2336000單位產(chǎn)品利潤(rùn)（元）34＝》＝》＝》＝》162.引入偏差變量，建立絕對(duì)約束和相對(duì)（目標(biāo)）約束方程由上面的目標(biāo)要求可得到的絕對(duì)約束條件和相對(duì)約束條件：（相對(duì)約束）（相對(duì)約束）（相對(duì)約束）（絕對(duì)約束）

其中，絕對(duì)約束也可通過(guò)引入正負(fù)偏差量，寫(xiě)成相對(duì)約束的形式：

只要保證其中的正負(fù)偏差變量同時(shí)為零，便可保證該約束仍然是絕對(duì)約束。、173.確定各目標(biāo)在目標(biāo)函數(shù)的表示形式、優(yōu)先級(jí)別以及權(quán)重系數(shù)第一目標(biāo)：利潤(rùn)不小于165000元。該目標(biāo)所涉及的偏差變量為

由“第一目標(biāo)”得：

由“利潤(rùn)不小于”得：和優(yōu)先級(jí)別為

P1在目標(biāo)函數(shù)中的表示應(yīng)為第三種形式，即：

且有：

又因?yàn)樵摷?jí)別只有單一目標(biāo)，所以有：＝》18第二目標(biāo)：兩道工序的加班費(fèi)用最小。

該目標(biāo)涉及到甲、乙兩道加工工序，因此涉及的偏差變量有

由“第二目標(biāo)”得：

由甲、乙工序的“總工時(shí)不大于”得

：和優(yōu)先級(jí)別為

P2在目標(biāo)函數(shù)中的表示應(yīng)為第二種形式，即：

＝》

由于、均為超過(guò)目標(biāo)值的盈余量，即為超出正常工時(shí)的加班工時(shí)，再由“甲工序加班費(fèi)0.60元/min，乙工序加班費(fèi)0.72元/min”得：

＝》甲工序：

乙工序：

＝》

19第三目標(biāo)：按合同生產(chǎn)A、B產(chǎn)品工16000個(gè)。該目標(biāo)為硬約束，所涉及的偏差變量為

由硬約束改為軟約束，和優(yōu)先級(jí)別最高為

P0要求達(dá)到期望值，在目標(biāo)函數(shù)中的表示應(yīng)為第一種形式，即：

且有：

又因?yàn)樵摷?jí)別只有單一目標(biāo)，所以有：＝》204.建立完整的數(shù)學(xué)模型

綜合上面的分析，可以得到該目標(biāo)規(guī)劃問(wèn)題完整的數(shù)學(xué)模型如下：21例2某工廠生產(chǎn)鼠標(biāo)和鍵盤(pán)，兩種產(chǎn)品均需要甲、乙兩個(gè)車間加工。已知相關(guān)數(shù)據(jù)如表3-2所示。

表3-2鼠標(biāo)鍵盤(pán)甲車間(小時(shí)/臺(tái))24乙車間(小時(shí)/臺(tái))2.51.5月庫(kù)存成本(元/臺(tái))1630銷售利潤(rùn)(元/臺(tái))4046市場(chǎng)需求量(臺(tái))15001000

甲車間有12臺(tái)機(jī)器，每臺(tái)機(jī)器工作8小時(shí)，每月正常運(yùn)行22天，運(yùn)轉(zhuǎn)成本36元/小時(shí)；乙車間有7臺(tái)機(jī)器，每臺(tái)機(jī)器工作16小時(shí)，每月正常運(yùn)行22天，運(yùn)轉(zhuǎn)成本30元/小時(shí)。22

P1－庫(kù)存成本不超過(guò)46000元；

P2－鼠標(biāo)銷售量不少于1500臺(tái)；

P3－兩個(gè)車間的設(shè)備應(yīng)充分運(yùn)用，以避免空閑時(shí)間，并按兩個(gè)車間機(jī)器運(yùn)作成本比例作為相應(yīng)的權(quán)系數(shù)；

P4－鍵盤(pán)銷售量不少于1000臺(tái)；

P5－甲車間全月加班時(shí)間不超過(guò)30小時(shí)；

P6－按兩個(gè)車間機(jī)器的運(yùn)轉(zhuǎn)成本比例作為相應(yīng)的權(quán)系數(shù)來(lái)限制其總加班時(shí)間。試建立工廠生產(chǎn)的目標(biāo)規(guī)劃模型。工廠已確定下個(gè)月中有關(guān)生產(chǎn)與銷售目標(biāo)的優(yōu)先等級(jí)：

23

1.確定決策變量及原始約束方程設(shè)鼠標(biāo)和鍵盤(pán)的產(chǎn)量為決策變量，分別用x1和x2表示，則各原始約束方程如下：（1）設(shè)備運(yùn)轉(zhuǎn)時(shí)間約束甲車間機(jī)器每月可工作總時(shí)間：

12(臺(tái))×8(小時(shí)/臺(tái)*天)×22(天)=2112(小時(shí))

乙車間機(jī)器每月可工作總時(shí)間：

7(臺(tái))×16(小時(shí)/臺(tái)*天)×22(天)=2464(小時(shí))

由此可得：

解：

①

②甲車間有12臺(tái)機(jī)器，每臺(tái)機(jī)器工作8小時(shí)，每月正常運(yùn)行22天，運(yùn)轉(zhuǎn)成本36元/小時(shí)；乙車間有7臺(tái)機(jī)器，每臺(tái)機(jī)器工作16小時(shí)，每月正常運(yùn)行22天，運(yùn)轉(zhuǎn)成本30元/小時(shí)。24（2）庫(kù)存成本約束

③（3）銷售目標(biāo)約束鼠標(biāo)的銷售目標(biāo)約束為：

④

鍵盤(pán)的銷售目標(biāo)約束為：（4）甲車間加班時(shí)間約束該約束涉及到第一個(gè)方程的正偏差變量，在引入正負(fù)正負(fù)偏差變量后討論。⑤鼠標(biāo)鍵盤(pán)甲車間(小時(shí)/臺(tái))24乙車間(小時(shí)/臺(tái))2.51.5月庫(kù)存成本(元/臺(tái))1630銷售利潤(rùn)(元/臺(tái))4046市場(chǎng)需求量(臺(tái)確定目標(biāo)約束方程對(duì)上面每個(gè)目標(biāo)引入正負(fù)偏差變量用

、表示，則上面各目標(biāo)轉(zhuǎn)換為如下約束方程：

①’

②’

③’

④’

⑤’

由“甲車間的加班時(shí)間不超過(guò)30小時(shí)”得：⑥再設(shè)甲車間加班時(shí)間的正負(fù)偏差變量為

、則可得其加班時(shí)間的約束為：

⑥’263.確定目標(biāo)函數(shù)各目標(biāo)的優(yōu)先級(jí)別已由題目給定，這里只需討論各級(jí)目標(biāo)的目標(biāo)函數(shù)表達(dá)形式，以及具有多個(gè)同級(jí)目標(biāo)間的權(quán)重確定。P1：“庫(kù)存成本不超過(guò)46000元”＝》“≤”應(yīng)采用第二種表示方式＝》即：“超過(guò)的部分盡可能減小”＝》P2：“鼠標(biāo)銷售量不少于1500臺(tái)”＝》“≥”應(yīng)采用第三種表示方式＝》即：“不足的部分盡可能減小”＝》27P3：“兩個(gè)車間的設(shè)備應(yīng)充分運(yùn)用，以避免空閑時(shí)間，并按兩個(gè)車間機(jī)器運(yùn)作成本比例作為相應(yīng)的權(quán)系數(shù)”由“兩個(gè)車間的設(shè)備應(yīng)充分運(yùn)用，以避免空閑時(shí)間”

＝》“甲、乙車間機(jī)器運(yùn)轉(zhuǎn)不小于可用時(shí)數(shù)，“≥”＝》采用第三種表示方式，“不足的部分盡可能減少”＝》再由“并按兩個(gè)車間機(jī)器運(yùn)作成本比例作為相應(yīng)的權(quán)系數(shù)”＝》已知甲車間的運(yùn)轉(zhuǎn)成本為36（元/臺(tái)），乙車間的運(yùn)轉(zhuǎn)成本為30（元/臺(tái)），則兩個(gè)車間的成本比例系數(shù)為：

36（元/臺(tái)）/30（元/臺(tái)）＝6/5取分子作為甲車間的權(quán)系數(shù)，分母為乙車間的權(quán)系數(shù)，則有：和＝》28P4：“鍵盤(pán)銷售量不少于1000臺(tái)”＝》“≥”采用第三種方式，“不足的部分盡可能減少”＝》P5：“甲車間全月加班時(shí)間不超過(guò)30小時(shí)”＝》“≤”采用第二種表示方式，“超過(guò)的部分盡可能減小”＝》P6：“按兩個(gè)車間機(jī)器的運(yùn)轉(zhuǎn)成本比例作為相應(yīng)的權(quán)系數(shù)來(lái)限制其總加班時(shí)間”＝》”≤”采用第二種表示方式，“超過(guò)的部分盡可能減小”，根據(jù)前面求得的甲乙兩車間的權(quán)系數(shù)得：＝》294.完整的數(shù)學(xué)模型綜合上面的分析，可得到該問(wèn)題完整的數(shù)學(xué)模型如下：30§3-2圖解法

從上面的表達(dá)式可以看到，如果把目標(biāo)函數(shù)求最小變換成求最大，該模型就是一個(gè)標(biāo)準(zhǔn)的線性規(guī)劃模型。因此，求解目標(biāo)規(guī)劃的思路和求解線性規(guī)劃的思路一樣，可采用單純形法或圖解法來(lái)求解。

對(duì)于只有兩個(gè)變量的問(wèn)題，采用圖解方法求解比較方便，對(duì)于變量多于兩個(gè)的問(wèn)題就必須采用單純形法來(lái)進(jìn)行求解。31

目標(biāo)規(guī)劃的圖解法和一般線性規(guī)劃的圖解法方法一樣，只是一般的線性規(guī)劃的圖解法可以求出最優(yōu)解（如果有的話），而目標(biāo)規(guī)劃只能求出滿意解。例3用圖解法求例1的解解：已知例1的數(shù)學(xué)模型如下所示：32其原始的約束條件為：由原始方程可得其各方程構(gòu)成的可行域如下圖所示：2462468108G(12)F(10)141412A(16)B(16)18H(18)E(20)20d0+d0-C(55/4)D(55/3)MNd1-d2+d3+X1X233P1滿足，3x1+4x2=5500的上方區(qū)域，且滿足P0的點(diǎn)只有M和N點(diǎn)。2462468108G(12)F(10)141412A(16)B(16)18H(18)E(20)20d0+d0-C(55/4)D(55/3)MNd1-d2+d3+X1X2最終可得滿意解M點(diǎn)的解值：X2=7000，x1=9000，獲得利潤(rùn)55000元；甲車間所用總工時(shí)25000（分），需要的加班時(shí)間為5000；乙車間所用總工時(shí)為39000（分），需要的加班時(shí)間為3000（分）。P0滿足，所有在x1+x2=16000上的點(diǎn)；如圖中紅線所示。P3中優(yōu)先滿足權(quán)重大的條件：d3+＝0－>2x1+3x2=36000的下方，和M、N點(diǎn)無(wú)交集。但M點(diǎn)和N點(diǎn)相比，M點(diǎn)使得d3+最小，因此，M點(diǎn)的解值為該問(wèn)題的滿意解。34例4：求例2中的目標(biāo)規(guī)劃解：由例2得其目標(biāo)規(guī)劃模型為：35其原始的約束條件為：由原始方程可得其各方程構(gòu)成的可行域如下圖所示：481248121620162028243034P1（d3+）P2（d4-）P6（5d2+）X1X2（1）（2）（3）（4）（5）P4（d5-）P6（6d1+）P3（5d2-）P3（6d1-）ABC36最終可得滿意解為x1=1500，x2=733.33，取整后，工廠應(yīng)生產(chǎn)1500臺(tái)鼠標(biāo)，733臺(tái)鍵盤(pán)，和所有的目標(biāo)最接近。481248121620162028243034P1（d3+）P2（d4-）P6（5d2+）X1X2（1）（2）（3）（4）（5）P4（d5-）P6（6d1+）P3（5d2-）P3（6d1-）ABC考慮上面的圖形以及各目標(biāo)的要求，同時(shí)滿足P1、P2和P3目標(biāo)的區(qū)域?yàn)閳D中A、B、C三點(diǎn)所包含的區(qū)域。在考慮P4目標(biāo)，和P1、P2和P3目標(biāo)滿足區(qū)域無(wú)交集，所以，該目標(biāo)不能完全滿足，使得最小的點(diǎn)為A點(diǎn)，因?yàn)?故P5和P6目標(biāo)不再考慮。

37§3-3擴(kuò)展單純形法

特點(diǎn)：1.目標(biāo)規(guī)劃中有幾級(jí)目標(biāo)，表中下半部分的檢驗(yàn)數(shù)就有幾行；2.與線性規(guī)劃單純形表的第二個(gè)不同之處時(shí)目標(biāo)函數(shù)的意義不同。在線性規(guī)劃中時(shí)實(shí)數(shù)，而在目標(biāo)規(guī)劃中決策變量的全部為0，而偏差變量的則由其所在目標(biāo)的優(yōu)先等級(jí)來(lái)表示，因此，檢驗(yàn)數(shù)也是優(yōu)先等級(jí)的函數(shù)；3.目標(biāo)規(guī)劃的單純形法求解的結(jié)果分別表示各決策變量的最優(yōu)取值和各目標(biāo)達(dá)到的程度。38例5用擴(kuò)展單純形法求例1的解解：已知例1的數(shù)學(xué)模型如下所示：變換后可得標(biāo)準(zhǔn)形式：39CBXBx1x2d0-d0+d1-d1+d2-d2+d3-d3+b-P0-P100d0-d1-d2-d3-19221121[3]1000-100001000-100001000-100001000-116000165002000036000

-zP0P1P21901120000-2000000-1000000-0.6000000-0.7216000165000040-P0-P100d0-d1-d2-x21/314/32/300011000-100001000-100001000-10-1/3-4-1/31/31/3[4]1/3-1/3400021000800012000

-zP0P1P21/310000000-2000000-1000000-0.60-1/3-401/34-0.724000210000CBXBx1x2d0-d0+d1-d1+d2-d2+d3-d3+b41CBXBx1x2d0-d0+d1-d1+d2-d2+d3-d3+b-P0-0.72P200d0-d3+d2-x21/41/4[5/4]3/400011000-1000-1/121/4-1/121/121/12-1/41/12-1/12001000-100-100010022505250625013750

-zP0P1P21/400.18000000-200-1/12-10.181/120-