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

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

3

目標規(guī)劃由美國數(shù)學家Charnces和Cooper于1961年提出，他們在研究不可行LP問題的近似解的時候形成這樣的概念。隨著計算機技術的不斷發(fā)展，目標規(guī)劃的應用日益廣泛，在諸如企業(yè)管理、市場營銷、交通運輸、能源利用、醫(yī)療保健、綜合開發(fā)等許多領域中，都取得了顯著的經(jīng)濟效益。4

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

§3-2圖解法

§3-3擴展單純形法

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

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

為正偏差變量，表示第i個目標超過期望值的盈余量；為負偏差變量，表示第i個目標低于期望值的不足量。

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

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

10

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

11②目標函數(shù)的通用表達形式

對于具有r個優(yōu)先級別，每個優(yōu)先級別最多有h個目標的目標規(guī)劃問題，其目標函數(shù)的通用表達形式為：③目標函數(shù)的三種基本形式

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

12★目標要求超過期望值。即當時，此時要求負偏差變量盡可能小，有：

其對應的目標函數(shù)可表示為：★目標要求達到期望值，即當時，此時要求正負偏差變量都盡可能小，有：和★目標要求低于期望值。即當時，此時要求正偏差變量盡可能小，有：和

其對應的目標函數(shù)可表示為：和

其對應的目標函數(shù)可表示為：13（4）基本數(shù)學表達式（數(shù)學模型）

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

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

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

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

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

“第二目標－兩道工序的加班費最小”在這里無法表示。

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

其中，絕對約束也可通過引入正負偏差量，寫成相對約束的形式：

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

由“第一目標”得：

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

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

且有：

又因為該級別只有單一目標，所以有：＝》18第二目標：兩道工序的加班費用最小。

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

由“第二目標”得：

由甲、乙工序的“總工時不大于”得

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

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

＝》

由于、均為超過目標值的盈余量，即為超出正常工時的加班工時，再由“甲工序加班費0.60元/min，乙工序加班費0.72元/min”得：

＝》甲工序：

乙工序：

＝》

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

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

P0要求達到期望值，在目標函數(shù)中的表示應為第一種形式，即：

且有：

又因為該級別只有單一目標，所以有：＝》204.建立完整的數(shù)學模型

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

表3-2鼠標鍵盤甲車間(小時/臺)24乙車間(小時/臺)2.51.5月庫存成本(元/臺)1630銷售利潤(元/臺)4046市場需求量(臺)15001000

甲車間有12臺機器，每臺機器工作8小時，每月正常運行22天，運轉成本36元/小時；乙車間有7臺機器，每臺機器工作16小時，每月正常運行22天，運轉成本30元/小時。22

P1－庫存成本不超過46000元；

P2－鼠標銷售量不少于1500臺；

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

P4－鍵盤銷售量不少于1000臺；

P5－甲車間全月加班時間不超過30小時；

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

23

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

12(臺)×8(小時/臺*天)×22(天)=2112(小時)

乙車間機器每月可工作總時間：

7(臺)×16(小時/臺*天)×22(天)=2464(小時)

由此可得：

解：

①

②甲車間有12臺機器，每臺機器工作8小時，每月正常運行22天，運轉成本36元/小時；乙車間有7臺機器，每臺機器工作16小時，每月正常運行22天，運轉成本30元/小時。24（2）庫存成本約束

③（3）銷售目標約束鼠標的銷售目標約束為：

④

鍵盤的銷售目標約束為：（4）甲車間加班時間約束該約束涉及到第一個方程的正偏差變量，在引入正負正負偏差變量后討論。⑤鼠標鍵盤甲車間(小時/臺)24乙車間(小時/臺)2.51.5月庫存成本(元/臺)1630銷售利潤(元/臺)4046市場需求量(臺確定目標約束方程對上面每個目標引入正負偏差變量用

、表示，則上面各目標轉換為如下約束方程：

①’

②’

③’

④’

⑤’

由“甲車間的加班時間不超過30小時”得：⑥再設甲車間加班時間的正負偏差變量為

、則可得其加班時間的約束為：

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

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

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

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

對于只有兩個變量的問題，采用圖解方法求解比較方便，對于變量多于兩個的問題就必須采用單純形法來進行求解。31

目標規(guī)劃的圖解法和一般線性規(guī)劃的圖解法方法一樣，只是一般的線性規(guī)劃的圖解法可以求出最優(yōu)解（如果有的話），而目標規(guī)劃只能求出滿意解。例3用圖解法求例1的解解：已知例1的數(shù)學模型如下所示：32其原始的約束條件為：由原始方程可得其各方程構成的可行域如下圖所示：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的點只有M和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點的解值：X2=7000，x1=9000，獲得利潤55000元；甲車間所用總工時25000（分），需要的加班時間為5000；乙車間所用總工時為39000（分），需要的加班時間為3000（分）。P0滿足，所有在x1+x2=16000上的點；如圖中紅線所示。P3中優(yōu)先滿足權重大的條件：d3+＝0－>2x1+3x2=36000的下方，和M、N點無交集。但M點和N點相比，M點使得d3+最小，因此，M點的解值為該問題的滿意解。34例4：求例2中的目標規(guī)劃解：由例2得其目標規(guī)劃模型為：35其原始的約束條件為：由原始方程可得其各方程構成的可行域如下圖所示：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，取整后，工廠應生產(chǎn)1500臺鼠標，733臺鍵盤，和所有的目標最接近。481248121620162028243034P1（d3+）P2（d4-）P6（5d2+）X1X2（1）（2）（3）（4）（5）P4（d5-）P6（6d1+）P3（5d2-）P3（6d1-）ABC考慮上面的圖形以及各目標的要求，同時滿足P1、P2和P3目標的區(qū)域為圖中A、B、C三點所包含的區(qū)域。在考慮P4目標，和P1、P2和P3目標滿足區(qū)域無交集，所以，該目標不能完全滿足，使得最小的點為A點，因為,故P5和P6目標不再考慮。

37§3-3擴展單純形法

特點：1.目標規(guī)劃中有幾級目標，表中下半部分的檢驗數(shù)就有幾行；2.與線性規(guī)劃單純形表的第二個不同之處時目標函數(shù)的意義不同。在線性規(guī)劃中時實數(shù)，而在目標規(guī)劃中決策變量的全部為0，而偏差變量的則由其所在目標的優(yōu)先等級來表示，因此，檢驗數(shù)也是優(yōu)先等級的函數(shù)；3.目標規(guī)劃的單純形法求解的結果分別表示各決策變量的最優(yōu)取值和各目標達到的程度。38例5用擴展單純形法求例1的解解：已知例1的數(shù)學模型如下所示：變換后可得標準形式：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-