目標規(guī)劃模型與一些優(yōu)化問題的Matlab求解

1、目標規(guī)劃方法與目標規(guī)劃方法與優(yōu)化問題的優(yōu)化問題的Matlab求解求解內容提要內容提要8.1 線性規(guī)劃與目標規(guī)劃線性規(guī)劃與目標規(guī)劃8.2 目標規(guī)劃的數(shù)學模型目標規(guī)劃的數(shù)學模型8.3 目標規(guī)劃模型的實例目標規(guī)劃模型的實例8.4 數(shù)據(jù)包絡分析數(shù)據(jù)包絡分析 8.1 線性規(guī)劃與目標規(guī)劃線性規(guī)劃與目標規(guī)劃線性規(guī)劃通?？紤]一個目標函數(shù)線性規(guī)劃通?？紤]一個目標函數(shù)(問題簡單問題簡單)目標規(guī)劃考慮多個目標函數(shù)目標規(guī)劃考慮多個目標函數(shù)(問題復雜問題復雜)線性規(guī)劃線性規(guī)劃目標規(guī)劃目標規(guī)劃發(fā)展發(fā)展演變演變某企業(yè)生產甲、乙兩種產品，需要用到某企業(yè)生產甲、乙兩種產品，需要用到A,B,C三種設備，關三種設備，關于產品的盈利

2、與使用設備的工時及限制如下表所示。于產品的盈利與使用設備的工時及限制如下表所示。 例例8.18.1 生產安排問題生產安排問題 問該企業(yè)應如何安排生產，使得在計劃期內總利潤最大？問該企業(yè)應如何安排生產，使得在計劃期內總利潤最大？ 1. 線性規(guī)劃建模線性規(guī)劃建模該例該例8.1是一個線性規(guī)劃問題，直接考慮它的線性規(guī)劃模型是一個線性規(guī)劃問題，直接考慮它的線性規(guī)劃模型設甲、乙產品的產量分別為設甲、乙產品的產量分別為x1, x2,建立線性規(guī)劃模型：建立線性規(guī)劃模型：;30020021xxzMax,1222.21 xxts. 0,155,1642121xxxx用用Lindo或或Lingo軟件求解軟件求解,得

3、到最優(yōu)解得到最優(yōu)解.1500, 3, 3*21zxx 2. 目標規(guī)劃建模目標規(guī)劃建模在上例在上例8.1中，企業(yè)的經營目標不僅要考慮利潤，還需要考中，企業(yè)的經營目標不僅要考慮利潤，還需要考慮多個方面，因此增加下列因素慮多個方面，因此增加下列因素(目標目標)： 力求使利潤指標不低于力求使利潤指標不低于1500元元 考慮到市場需求考慮到市場需求,甲、乙兩種產品的產量比應盡量保持甲、乙兩種產品的產量比應盡量保持1:2 設備設備A為貴重設備，嚴格禁止超時使用為貴重設備，嚴格禁止超時使用 設備設備C可以適當加班，但要控制；設備可以適當加班，但要控制；設備B既要求充分利用，又盡既要求充分利用，又盡可能不加班

4、，在重要性上，設備可能不加班，在重要性上，設備B是設備是設備C的的3倍倍從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標規(guī)劃的方法進行建模求解借助于目標規(guī)劃的方法進行建模求解某汽車銷售公司委托一個廣告公司在電視上為其做廣告，汽某汽車銷售公司委托一個廣告公司在電視上為其做廣告，汽車銷售公司提出三個目標：車銷售公司提出三個目標： 例例8.2 汽車廣告費問題汽車廣告費問題 廣告公司必須決定購買兩種類型的電視廣告展播各多少分鐘？廣告公司必須決定購買兩種類型的電視廣告展播各多少分鐘？第一個目標，至少有第一個目標，至少有40萬高收入的男性公民萬

5、高收入的男性公民(記為記為HIM)看到這個廣告看到這個廣告第二個目標，至少有第二個目標，至少有60萬一般收入的公民萬一般收入的公民(記為記為LIP)看到這個廣告看到這個廣告第三個目標，至少有第三個目標，至少有35萬高收入的女性公民萬高收入的女性公民(記為記為HIW)看到這個廣告看到這個廣告廣告公司可以從電視臺購買兩種類型的廣告展播：足球賽中廣告公司可以從電視臺購買兩種類型的廣告展播：足球賽中插播廣告和電視系列劇插播廣告。廣告公司最多花費插播廣告和電視系列劇插播廣告。廣告公司最多花費6060萬元萬元的電視廣告費。每一類廣告展播每一分鐘的花費及潛在的觀的電視廣告費。每一類廣告展播每一分鐘的花費及潛

6、在的觀眾人數(shù)如下表所示眾人數(shù)如下表所示 3.嘗試線性規(guī)劃建模嘗試線性規(guī)劃建模對于例對于例8.2考慮建立線性規(guī)劃模型考慮建立線性規(guī)劃模型設設x1, x2分別是足球賽和電視系列劇中插播的分鐘數(shù)，按照分別是足球賽和電視系列劇中插播的分鐘數(shù)，按照要求，可以列出相應的線性規(guī)劃模型要求，可以列出相應的線性規(guī)劃模型;0021xxMin,60610.21xxts. 0,3545,60510,403721212121xxxxxxxx用用Lindo或或Lingo軟件求解軟件求解,會發(fā)現(xiàn)該問題不可行。會發(fā)現(xiàn)該問題不可行。（可以任意目標）（可以任意目標） 4. 線性規(guī)劃建模局限性線性規(guī)劃建模局限性 線性規(guī)劃要求所有求

7、解的問題必須滿足全部的約束，而實線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實際問題中并非所有約束都需要嚴格的滿足；際問題中并非所有約束都需要嚴格的滿足； 線性規(guī)劃只能處理單目標的優(yōu)化問題，而對一些次目標只線性規(guī)劃只能處理單目標的優(yōu)化問題，而對一些次目標只能轉化為約束處理。但在實際問題中，目標和約束好似可以能轉化為約束處理。但在實際問題中，目標和約束好似可以相互轉化的，處理時不一定要嚴格區(qū)分；相互轉化的，處理時不一定要嚴格區(qū)分； 線性規(guī)劃在處理問題時，將各個約束線性規(guī)劃在處理問題時，將各個約束(也可看作目標也可看作目標)的地的地位看成同等重要，而在實際問題中，各個目標的重要性即位看成同等重

8、要，而在實際問題中，各個目標的重要性即有層次上的差別，也有在同一層次上不同權重的差別有層次上的差別，也有在同一層次上不同權重的差別 線性規(guī)劃尋求最優(yōu)解，而許多實際問題只需要找到滿意解線性規(guī)劃尋求最優(yōu)解，而許多實際問題只需要找到滿意解就可以了。就可以了。 8. 2 目標規(guī)劃的數(shù)學模型目標規(guī)劃的數(shù)學模型為了克服線性規(guī)劃的局限性為了克服線性規(guī)劃的局限性,目標規(guī)劃采用如下手段：目標規(guī)劃采用如下手段：1. 設置偏差變量設置偏差變量; ;2. 統(tǒng)一處理目標與約束統(tǒng)一處理目標與約束; ;3. 目標的優(yōu)先級與權系數(shù)。目標的優(yōu)先級與權系數(shù)。目標規(guī)劃的基本概念目標規(guī)劃的基本概念 1. 設置偏差變量設置偏差變量用偏

9、差變量用偏差變量( (Deviational variables) )來表示實際值與目標值來表示實際值與目標值之間的差異，令之間的差異，令 - - 超出目標的差值，稱為超出目標的差值，稱為正偏差變量正偏差變量 - - 未達到目標的差值，稱為未達到目標的差值，稱為負偏差變量負偏差變量其中其中 與與 至少有一個為至少有一個為0 0約定如下：約定如下：當實際值超過目標值時，有當實際值超過目標值時，有當實際值未達到目標值時，有當實際值未達到目標值時，有當實際值與目標值一致時，有當實際值與目標值一致時，有ddddd; 0, 0dd; 0, 0dd. 0, 0dd 2. 統(tǒng)一處理目標與約束統(tǒng)一處理目標與約

10、束在目標規(guī)劃中，約束可分兩類，一類是對資源有嚴格限制在目標規(guī)劃中，約束可分兩類，一類是對資源有嚴格限制的，稱為剛性約束的，稱為剛性約束(Hard Constraint)；例如在用目標規(guī)劃；例如在用目標規(guī)劃求解例求解例8.1中設備中設備A禁止超時使用，則有剛性約束禁止超時使用，則有剛性約束另一類是可以不嚴格限制的，連同原線性規(guī)劃的目標另一類是可以不嚴格限制的，連同原線性規(guī)劃的目標,構構成柔性約束成柔性約束(Soft Constraint).例如在求解例例如在求解例8.1中，我們中，我們希望利潤不低于希望利潤不低于1500元，則目標可表示為元，則目標可表示為.122221xx.1500300200

11、;min21ddxxd求解例求解例8.1中甲、乙兩種產品中甲、乙兩種產品的產量盡量保持的產量盡量保持1:2的比例，的比例，則目標可表示為則目標可表示為設備設備C可以適當加班，但要控制，可以適當加班，但要控制，則目標可表示為則目標可表示為. 02;min21ddxxdd.155;min2ddxd設備設備B既要求充分利用，又盡可能既要求充分利用，又盡可能不加班，則目標可表示為不加班，則目標可表示為.164;min1ddxdd從上面的分析可以看到：從上面的分析可以看到：如果希望不等式保持大于等于，則極小化負偏差；如果希望不等式保持大于等于，則極小化負偏差；如果希望不等式保持小于等于，則極小化正偏差；

12、如果希望不等式保持小于等于，則極小化正偏差；如果希望保持等式，則同時極小化正、負偏差如果希望保持等式，則同時極小化正、負偏差 3.目標的優(yōu)先級與權系數(shù)目標的優(yōu)先級與權系數(shù)在目標規(guī)劃模型中，目標的優(yōu)先分為兩個層次，第一個在目標規(guī)劃模型中，目標的優(yōu)先分為兩個層次，第一個層次是目標分成不同的優(yōu)先級，在計算目標規(guī)劃時，必層次是目標分成不同的優(yōu)先級，在計算目標規(guī)劃時，必須先優(yōu)化高優(yōu)先級的目標，然后再優(yōu)化低優(yōu)先級的目標。須先優(yōu)化高優(yōu)先級的目標，然后再優(yōu)化低優(yōu)先級的目標。通常以通常以P1,P2,.表示不同的因子表示不同的因子,并規(guī)定并規(guī)定PkPk+1，第二個，第二個層次是目標處于同一優(yōu)先級，但兩個目標的權重

13、不一樣，層次是目標處于同一優(yōu)先級，但兩個目標的權重不一樣，因此兩目標同時優(yōu)化，用權系數(shù)的大小來表示目標重要因此兩目標同時優(yōu)化，用權系數(shù)的大小來表示目標重要性的差別。性的差別。解在例解在例.1.1中設備中設備A是是剛性約剛性約束，其于是柔性約束首先，最束，其于是柔性約束首先，最重要的指標是企業(yè)的利潤，將它重要的指標是企業(yè)的利潤，將它的優(yōu)先級列為第一級；其次，甲、的優(yōu)先級列為第一級；其次，甲、乙兩種產品的產量保持乙兩種產品的產量保持1:2的比的比例，列為第二級；再次，例，列為第二級；再次，設備設備 B和和C的工作時間要有所控制，列的工作時間要有所控制，列為第三級，設備為第三級，設備B的重要性是設的

14、重要性是設備備C的三倍，因此它們的權重不的三倍，因此它們的權重不一樣。由此可以得到相應的目標一樣。由此可以得到相應的目標規(guī)劃模型。規(guī)劃模型。 目標規(guī)劃模型的建立目標規(guī)劃模型的建立例例8.3 用目標規(guī)劃方法求解例用目標規(guī)劃方法求解例8. 1);433()(min43332221dddPddPdPz,1222.21 xxts. 4 , 3 , 2 , 1, 0,155,164, 02,15003002002144233122211121iddxxddxddxddxxddxxii 目標規(guī)劃的一般模型目標規(guī)劃的一般模型目標規(guī)劃模型的一般數(shù)學表達式為：目標規(guī)劃模型的一般數(shù)學表達式為：; )(min11l

15、jjkjjkjqkkdwdwPz, 2 , 1,),(.1mibxatsijnjij,2, 1,0,2, 1,0,2, 1,1liddnjxligddxciijiiijnjij 求解目標規(guī)劃的序貫式算法求解目標規(guī)劃的序貫式算法其算法是根據(jù)優(yōu)先級的先后次序，將目標規(guī)劃問題分解成其算法是根據(jù)優(yōu)先級的先后次序，將目標規(guī)劃問題分解成一系列的單目標規(guī)劃問題，然后再依次求解。一系列的單目標規(guī)劃問題，然后再依次求解。算法算法8.1 對于對于k=1,2,q,求解單目標問題求解單目標問題; )(min1ljjkjjkjdwdwz,2, 1,),(.1mibxatsijnjij,2,1,0,2,1,0,1,2,1

16、,)(,2,1,*11liddnjxkszdwdwligddxciijljjsjjsjiiijnjij解因為每個單目標問題都是一個線性規(guī)劃問題，解因為每個單目標問題都是一個線性規(guī)劃問題，因此可以采用因此可以采用LINDOLINDO軟件進行求解。按照算法軟件進行求解。按照算法8.18.1和和例例8.38.3目標規(guī)劃模型編寫單個的線性規(guī)劃求解程序。目標規(guī)劃模型編寫單個的線性規(guī)劃求解程序。求第一級目標企業(yè)利潤最大，列出求第一級目標企業(yè)利潤最大，列出LINDOLINDO程序。程序。程序名：程序名：exam0804a.ltxexam0804a.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3

17、MIN DMINUS1 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 END求解結果可見求解結果可見程序演示程序演示目標目標解因求出的目標函數(shù)的最優(yōu)值為，即第一級偏差為解因求出的目標函數(shù)的最優(yōu)值為，即第一級偏差為. .再求第二級目標，列出其再求第二級目標，列出其LINDOLINDO程序。程序。程序名：程序名：exam0804b.ltxe

18、xam0804b.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3 MIN DPLUS2 + DMINUS2 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 END求解結果可見求解結果可見程序演示程序演示修改的目標修改的目標增加的約束增加的約束解因求出的目標函數(shù)的最優(yōu)值仍為，即第二級偏差解因求出的目標函數(shù)

19、的最優(yōu)值仍為，即第二級偏差仍為仍為. . 繼續(xù)求第三級目標，列出其繼續(xù)求第三級目標，列出其LINDOLINDO程序。程序。程序名：程序名：exam0804c.ltxexam0804c.ltx 例例8.4 用算法用算法8.1求解例求解例8. 3 MIN 3DPLUS3 + 3DMINUS3+ DPLUS4 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS

20、4 = 15 DMINUS1 = 0 DPLUS2 + DMINUS2 = 0 END求解結果可見求解結果可見程序演示程序演示求出的目標函數(shù)的最優(yōu)值為求出的目標函數(shù)的最優(yōu)值為29,即第三級偏差為即第三級偏差為29,分分析結果析結果, x1為為2, x2為為4, DPLUS1 為為100,因此目標規(guī)劃的因此目標規(guī)劃的最優(yōu)解為最優(yōu)解為x *=(2,4),最優(yōu)利潤為最優(yōu)利潤為1600.修改的目標修改的目標增加的約束增加的約束解按照算法解按照算法8.1和例和例8.3目標規(guī)劃模型編寫目標規(guī)劃模型編寫LINGO求解程求解程序，列出其序，列出其LINGO程序程序, 程序名：程序名：exam0805.lg4

21、例例8.5 (繼例繼例8.4) 用算法用算法8.1求解例求解例8. 3的的LINGO程序程序程序運行說明，分三次求解：程序運行說明，分三次求解： 在做第一級目標計算時，在做第一級目標計算時，P(1),P(2)和和P(3)分別輸入分別輸入1,0和和0，Goal(1)和和Goal(2)輸入兩個較大的數(shù)，表示這兩項約束不起作用；輸入兩個較大的數(shù)，表示這兩項約束不起作用； 在做第二級目標計算時，在做第二級目標計算時，P(1),P(2)和和P(3)分別輸入分別輸入0,1和和0，由于第，由于第一級的偏差為一級的偏差為0，因此，因此Goal(1)為為0，Goal(2)輸入一個較大的數(shù)；輸入一個較大的數(shù)； 在

22、做第三級計算時，在做第三級計算時，P(1),P(2)和和P(3)分別輸入分別輸入0,0和和1，由于第一級、，由于第一級、第二級的偏差為第二級的偏差為0，因此，因此Goal(1)和和Goal(2)的輸入值也為的輸入值也為0。結果可以參見程序演示！結果可以參見程序演示！ 由于在例由于在例8.4中雖然給出了目標規(guī)劃問題的最優(yōu)解中雖然給出了目標規(guī)劃問題的最優(yōu)解, ,但需但需要連續(xù)編幾個要連續(xù)編幾個LINDO程序程序, ,在使用時不方便在使用時不方便, ,下面使用下面使用LINGO軟件軟件,編寫一個通用程序。編寫一個通用程序。 8. 3 目標規(guī)劃模型的實例目標規(guī)劃模型的實例前面介紹了目標規(guī)劃的求解方法，

23、接著再介紹前面介紹了目標規(guī)劃的求解方法，接著再介紹幾個目標規(guī)劃模型的實例。幾個目標規(guī)劃模型的實例。某音像商店有某音像商店有5名全職售貨員和名全職售貨員和4名兼職售貨員。全職售貨員名兼職售貨員。全職售貨員每月工作每月工作160小時，兼職售貨員每月工作小時，兼職售貨員每月工作80小時。根據(jù)過去的小時。根據(jù)過去的工作記錄，全職售貨員每小時銷售工作記錄，全職售貨員每小時銷售CD25張，平均每小時工資張，平均每小時工資15元，加班工資每小時元，加班工資每小時22.5元。兼職售貨員每小時銷售元。兼職售貨員每小時銷售CD10張，平均每小時工資張，平均每小時工資10元，加班工資每小時元，加班工資每小時10元。

24、現(xiàn)在預測元?，F(xiàn)在預測下月下月CD銷售量為銷售量為27500張，商店每周開門營業(yè)張，商店每周開門營業(yè)6天，所以可能天，所以可能要加班。另每出售一張要加班。另每出售一張CD盈利盈利1.5元。元。 例例8.6該商店經理認為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比該商店經理認為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班但就業(yè)水平不穩(wěn)定要好。但全職售貨員如果加班過多，不加班但就業(yè)水平不穩(wěn)定要好。但全職售貨員如果加班過多，就會因疲勞過度而造成效率下降，因此不允許每月加班超過就會因疲勞過度而造成效率下降，因此不允許每月加班超過100小時。建立相應的目標規(guī)劃模型，并運用小時。建立相應的目標規(guī)劃模型，并運用LI

25、NGO軟件進軟件進行求解。行求解。解解 首先建立目標約束的優(yōu)先級。首先建立目標約束的優(yōu)先級。P1：下月的：下月的CD銷售量達到銷售量達到27500張；張；P2： 限制全職售貨員加班時間不超過限制全職售貨員加班時間不超過100小時；小時；P3： 保持全體售貨員充分就業(yè)，因為充分工作是良保持全體售貨員充分就業(yè)，因為充分工作是良 好勞資關系的重要因素，但對全職售貨員要比好勞資關系的重要因素，但對全職售貨員要比 兼職售貨員加倍優(yōu)先考慮；兼職售貨員加倍優(yōu)先考慮； P4： 盡量減少加班時間，但對兩種售貨員區(qū)別對盡量減少加班時間，但對兩種售貨員區(qū)別對 待，優(yōu)先權因子由他們對利潤的貢獻而定。待，優(yōu)先權因子由他

26、們對利潤的貢獻而定。 例例8.6 例例8.6第二，建立目標約束。第二，建立目標約束。(1) 銷售目標約束。設銷售目標約束。設 x1 ：全體全職售貨員下月的工作時間；：全體全職售貨員下月的工作時間； x2 ：全體兼職售貨員下月的工作時間；：全體兼職售貨員下月的工作時間； ：達不到銷售目標的偏差；：達不到銷售目標的偏差； ：超過銷售目標的偏差。：超過銷售目標的偏差。 希望下月的銷售量超過希望下月的銷售量超過27500張張CD片，因此銷售片，因此銷售目標為目標為1d1d.275001025;min11211ddxxd 例例8.6.320,800;2min33222132ddxddxdd第二，建立目標

27、約束。第二，建立目標約束。(2) 正常工作時間約束，設正常工作時間約束，設 ：全體全職售貨員下月的停工時間；：全體全職售貨員下月的停工時間； ：全體全職售貨員下月的加班時間；：全體全職售貨員下月的加班時間； ：全體兼職售貨員下月的停工時間；：全體兼職售貨員下月的停工時間； ：全體兼職售貨員下月的加班時間。：全體兼職售貨員下月的加班時間。 由于希望保持全體售貨員充分就業(yè)，同時加倍優(yōu)由于希望保持全體售貨員充分就業(yè)，同時加倍優(yōu)先考慮全職售貨員先考慮全職售貨員, ,因此工作目標約束為因此工作目標約束為3d3d2d2d 例例8.6第二，建立目標約束。第二，建立目標約束。(3) 正常工作時間約束，設正常工

28、作時間約束，設 ：全體全職售貨員下月加班不足：全體全職售貨員下月加班不足100小時的偏差；小時的偏差； ：全體全職售貨員下月加班超過：全體全職售貨員下月加班超過100小時的偏差。小時的偏差。 限制全職售貨員加班時間不超過限制全職售貨員加班時間不超過100小時，將加班約小時，將加班約束看成正常上班約束，不同的是右端加上束看成正常上班約束，不同的是右端加上100小時，因此小時，因此加班目標約束為加班目標約束為4d4d.900;min4414ddxd 例例8.6第二，建立目標約束。第二，建立目標約束。接上接上(3) 另外，全職售貨員加班另外，全職售貨員加班1小時，商店得到的利潤小時，商店得到的利潤為

29、為15元元(25*1.5-22.5=15)，兼職售貨員加班，兼職售貨員加班1小時，商店得小時，商店得到的利潤為到的利潤為5元元(10*1.5-10=5)，因此加班，因此加班1小時全職售貨員小時全職售貨員獲得的利潤是兼職售貨員的獲得的利潤是兼職售貨員的3倍，故權因子之比為倍，故權因子之比為 , 3:1:32dd 所以，另一個加班目標約束為：所以，另一個加班目標約束為：.320,800;2min33222132ddxddxdd 例例8.6 第三，按目標的優(yōu)先級，寫出相應的目標規(guī)劃模型：第三，按目標的優(yōu)先級，寫出相應的目標規(guī)劃模型：);3()2(min3243234211ddPddPdPdPz,27

30、5001025.1121ddxxts. 4 , 3 , 2 , 1, 0,900,320,80021441332221iddxxddxddxddxii 第四，寫出相應的第四，寫出相應的LINGO程序，程序名：程序，程序名：exam0806.lg4.程序運行說明，分四次求解：程序運行說明，分四次求解： 在做第一級目標計算時，在做第一級目標計算時，P(1),P(2),P(3)和和P(4)分別輸入分別輸入1,0,0和和0，Goal(1), Goal(2)和和Goal(3)輸入兩個較大的數(shù)，表示這兩項約束不起作用；輸入兩個較大的數(shù)，表示這兩項約束不起作用； 在做第二級目標計算時，在做第二級目標計算時，

31、P(1),P(2),P(3)和和P(4)分別輸入分別輸入0,1,0和和0，由于，由于第一級的偏差為第一級的偏差為0，因此，因此Goal(1)為為0,Goal(2)和和Goal(3)輸入一個較大的數(shù)；輸入一個較大的數(shù)； 在做第三級計算時，在做第三級計算時，P(1),P(2),P(3)和和P(4)分別輸入分別輸入0,0,1和和0，由于第一，由于第一級級,第二級的偏差為第二級的偏差為0，因此，因此Goal(1)和和Goal(2)的輸入值也為的輸入值也為0， Goal(3)輸入輸入一個較大的數(shù)；一個較大的數(shù)； 在做第四級計算時，在做第四級計算時，P(1),P(2),P(3)和和P(4)分別輸入分別輸入

32、0,0,0和和1，由于第一，由于第一級級,第二級和第三級的偏差為第二級和第三級的偏差為0,因此因此Goal(1),Goal(2)和和Goal(3)輸入值也為輸入值也為0； 全職售貨員總工作時間為全職售貨員總工作時間為900900小時小時( (加班加班100100小時小時) )，兼職售貨員總工作，兼職售貨員總工作時間時間500500小時小時( (加班加班180180小時小時) )，下月共銷售，下月共銷售CD27500CD27500張，商店共獲得利潤張，商店共獲得利潤 2750027500* *1.5-8001.5-800* *15-10015-100* *22.5-50022.5-500* *1

33、0=22000(10=22000(元元) )其結果可以參見程序演示！其結果可以參見程序演示！某計算機公司生產三種型號的筆記本電腦某計算機公司生產三種型號的筆記本電腦A,B,C。這。這三種筆記本電腦需要在復雜的裝配線上生產，生產三種筆記本電腦需要在復雜的裝配線上生產，生產1臺臺A,B,C型號的筆記本電腦分別需要型號的筆記本電腦分別需要5,8,12小時。小時。公司裝配線正常的生產時間是每月公司裝配線正常的生產時間是每月1700小時。公司小時。公司營業(yè)部門估計營業(yè)部門估計A,B,C三種筆記本電腦的利潤分別是三種筆記本電腦的利潤分別是每臺每臺1000,1440,2520元，而公司預測這個月生產的筆元，

34、而公司預測這個月生產的筆記本電腦能夠全部售出。記本電腦能夠全部售出。 例例8.7 例例8.7公司經理考慮以下目標：公司經理考慮以下目標：第一目標：充分利用正常的生產能力，避免開工不足；第一目標：充分利用正常的生產能力，避免開工不足；第二目標：優(yōu)先滿足老客戶的需求，第二目標：優(yōu)先滿足老客戶的需求，A,B,C三種型號的電腦三種型號的電腦50,50,80臺，同時根據(jù)三種電腦的純利潤分配不同的權因子；臺，同時根據(jù)三種電腦的純利潤分配不同的權因子；第三目標：限制裝配線加班時間，不允許超過第三目標：限制裝配線加班時間，不允許超過200小時；小時；第四目標：滿足各種型號電腦的銷售目標第四目標：滿足各種型號電

35、腦的銷售目標,A,B,C型號分別為型號分別為100,120,100臺臺,再根據(jù)三種電腦的純利潤分配不同的權因子；再根據(jù)三種電腦的純利潤分配不同的權因子；第五目標：裝配線的加班時間盡可能少。第五目標：裝配線的加班時間盡可能少。請列出相應的目標規(guī)劃模型請列出相應的目標規(guī)劃模型,并用并用LINGO軟件求解。軟件求解。 例例8.7解解 建立目標約束。建立目標約束。(1) 裝配線正常生產裝配線正常生產 設生產設生產A,B,C型號的電腦為型號的電腦為x1, x2, x3臺，臺， 裝配線正常生產時間未利用數(shù)，裝配線正常生產時間未利用數(shù)， 裝配線加班時間，裝配線加班時間， 希望裝配線正常生產希望裝配線正常生產

36、,避免開工不足避免開工不足,因此裝配線因此裝配線約束目標為約束目標為1d1d.17001285;min113211ddxxxd 例例8.7.80,50,50;211820min443332221432ddxddxddxddd(2) 銷售目標銷售目標 優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純優(yōu)先滿足老客戶的需求，并根據(jù)三種電腦的純利潤分配不同的權因子，利潤分配不同的權因子，A,B,C三種型號的電腦每三種型號的電腦每小時的利潤是小時的利潤是 因此因此,老客戶的老客戶的,122520,81440,51000銷售目標約束為銷售目標約束為 例例8.7(2) 銷售目標銷售目標 (接上接上) 再考慮一般銷售

37、，類似上面的討論，得到再考慮一般銷售，類似上面的討論，得到.100,120,100;211820min773662551765ddxddxddxddd 例例8.7(3) 加班限制加班限制 首先是限制裝配線加班時間，不允許超過首先是限制裝配線加班時間，不允許超過200小時，因此得到小時，因此得到.19001285;min883218ddxxxd其次裝配線的加班時間盡可能少，即其次裝配線的加班時間盡可能少，即.17001285;min113211ddxxxd例例8.7 寫出相應的目標規(guī)劃模型：寫出相應的目標規(guī)劃模型：;)211820()211820(min15765483432211dPdddPd

38、PdddPdPz,17001285.11321ddxxxts. 8 , 2 , 1, 0,19001285,100,120,100,80,50,502188321773662551443332221iddxxddxxxddxddxddxddxddxddxii 寫出相應的寫出相應的LINGO程序，程序名：程序，程序名：exam0807.lg4.程序運行說明：程序運行說明： 經經5次計算得到次計算得到x1=100, x2=55, x3=80。裝配線生產時間。裝配線生產時間為為1900小時，滿足裝配線加班不超過小時，滿足裝配線加班不超過200小時的要求。能夠小時的要求。能夠滿足老客戶的需求，但未能達

39、到銷售目標。銷售總利潤為滿足老客戶的需求，但未能達到銷售目標。銷售總利潤為 100 x1000+55x1440+80 x2520=380800(元元) 其結果可以參見程序演示！其結果可以參見程序演示！ 例例8.8已知三個工廠生產的產品供應給四個用戶，各工廠已知三個工廠生產的產品供應給四個用戶，各工廠生產量、用戶需求量及從各工廠到用戶的單位產品生產量、用戶需求量及從各工廠到用戶的單位產品的運輸費用如表所示。由于總生產量小于總需求量的運輸費用如表所示。由于總生產量小于總需求量,上級部門經研究后，制定了調配方案的上級部門經研究后，制定了調配方案的8項指標，并項指標，并規(guī)定重要性的次序是規(guī)定重要性的次

40、序是: 例例8.8第一目標：用戶第一目標：用戶4為重要部門為重要部門,需求量必須全部滿足；需求量必須全部滿足；第二目標：供應用戶第二目標：供應用戶1的產品中，工廠的產品中，工廠3的產品不少的產品不少于于100個單位；第三目標：每個用戶的滿足率不低于個單位；第三目標：每個用戶的滿足率不低于80%；第四目標：應盡量滿足各用戶的需求；第四目標：應盡量滿足各用戶的需求；第五目標：新方案的總運費不超過原運輸問題的調度第五目標：新方案的總運費不超過原運輸問題的調度方案的方案的10%；第六目標：因道路限制，工廠；第六目標：因道路限制，工廠2到用戶到用戶4的路線應盡量避免運輸任務；的路線應盡量避免運輸任務；第

41、七目標：用戶第七目標：用戶1和用戶和用戶3的滿足率應盡量保持平衡；的滿足率應盡量保持平衡；第八目標：力求減少總運費。第八目標：力求減少總運費。請列出相應的目標規(guī)劃模型，并用請列出相應的目標規(guī)劃模型，并用LINGO軟件求解。軟件求解。 例例8.8解解 求解原運輸問題。求解原運輸問題。由于總生產量小于總需求量由于總生產量小于總需求量,虛設工廠虛設工廠4,生產量為生產量為100個單位個單位,到各個用戶間的運輸單價為到各個用戶間的運輸單價為0,利用第利用第7章介紹章介紹的運輸問題的求解方法的運輸問題的求解方法,用用LINGO軟件求解軟件求解,得到總得到總運費是運費是2950元元,運輸方案如表所示運輸方

42、案如表所示. 例例8.8.400,200,300343332312413222114131211xxxxxxxxxxxx從上表可以看出，上述方案中，第一個目標就不滿從上表可以看出，上述方案中，第一個目標就不滿足，用戶足，用戶4的需求量得不到滿足。下面按照目標的的需求量得不到滿足。下面按照目標的重要性的等級列出目標規(guī)劃的約束和目標函數(shù)。重要性的等級列出目標規(guī)劃的約束和目標函數(shù)。設設 xi j 為工廠為工廠 i 調配給用戶調配給用戶 j 的運量的運量.1001131ddx(1) 供應約束應供應約束應嚴格滿足嚴格滿足, 即即(2) 供應用戶供應用戶1的產品中的產品中,工廠工廠3的產品不少于的產品不少

43、于100個單位個單位, 即即 例例8.8.200,360,80,16055342414443323133332221222312111ddxxxddxxxddxxxddxxx(3) 需求約束需求約束. 各用戶的滿各用戶的滿 足率不低于足率不低于 80%, 即即.250,450,100,20099342414883323137732221266312111ddxxxddxxxddxxxddxxx 需求應盡量需求應盡量 滿足各用戶滿足各用戶 的需求，即的需求，即.324510103141 ddxcijijij新方案的總運費不超過原運方案的新方案的總運費不超過原運方案的10%（原運輸（原運輸方案的運

44、費為方案的運費為2950元），即元），即.0)(450200)(1212332313312111ddxxxxxx(5) 工廠工廠2到用戶到用戶4的路線的路線應盡量避免運輸任務應盡量避免運輸任務, 即即(6) 用戶用戶1和用戶和用戶3的滿足率應盡量保持平衡，即的滿足率應盡量保持平衡，即 .0111124ddx(7)力求總運力求總運費最少費最少, 即即.295013133141 ddxcijijij 例例8.8 寫出相應的目標函數(shù)為寫出相應的目標函數(shù)為.)()()(min1381212711610598764543231291dPddPdPdPddddPddddPdPdPz 寫出相應的寫出相應的L

45、INGO程序，程序名：程序，程序名：exam0808.lg4. 程序運行說明程序運行說明 其結果可以參見程序演示！其結果可以參見程序演示！經經8 8次計算，得到最終的計算結果，見下表所示。次計算，得到最終的計算結果，見下表所示?？傔\費為總運費為33603360元，高于原運費元，高于原運費410410元，超過原方案元，超過原方案10%10%的上限的上限115115元。元。 在經濟研究中，常常需要考慮多個目標，如經濟效益目標，生態(tài)效益目標，社會效益目標，等等。為了滿足這類問題研究之需要，對多目標規(guī)劃方法作一些介紹。第一節(jié)第一節(jié) 多目標規(guī)劃及其非劣解多目標規(guī)劃及其非劣解 多目標規(guī)劃及其非劣解多目標規(guī)

46、劃及其非劣解 多目標規(guī)劃求解技術簡介多目標規(guī)劃求解技術簡介一、多目標規(guī)劃及其非劣解一、多目標規(guī)劃及其非劣解（一）任何多目標規(guī)劃問題，都由兩個基本部分組成： （1）兩個以上的目標函數(shù)； （2）若干個約束條件。（二）多目標決策的兩個較明顯的特點： （1）目標之間的不可公度性； （2）目標之間的矛盾性。（三）對于多目標規(guī)劃問題，可以將其數(shù)學模型一般地描寫為如下形式： （1.21.2）)(max(min)(max(min)(max(min)(21XfXfXfXFZkmmgggGXXXX2121)()()()(（1.11.1）式中： 為決策變量向量。 TnxxxX,21 如果將（1.1）和（1.2）式進

47、一步縮寫， 即： （1.3） （1.4） 式中： 是k維函數(shù)向量， k是目標函數(shù)的個數(shù)； 是m維函數(shù)向量； 是m維常數(shù)向量；m是約束方程的 個數(shù)。 )(max(min)XFZ GX )()(XFZ )(XG 對于線性多目標規(guī)劃問題，（1.3）和（1.4）式可以進一步用矩陣表示： （1.51.5） （1.61.6）式中： 為n維決策變量向量； 為kn矩陣，即目標函數(shù)系數(shù)矩陣； 為mn矩陣，即約束方程系數(shù)矩陣； 為m維的向量，約束向量。 AXZ max(min)bBX XABb二、多目標規(guī)劃的非劣解二、多目標規(guī)劃的非劣解多目標規(guī)劃問題的求解不能只追求一個目標的最優(yōu)化（最大或最?。?，而不顧其它目標。

48、 在圖1.1中，就方案和來說，的 目標值比大，但其目標值 比小，因此無法確定這兩個方案的優(yōu)與劣。在各個方案之間，顯然：比好，比好，比好，比好。而對于方案而對于方案、之間則無之間則無法確定優(yōu)劣，而且又沒有比它們法確定優(yōu)劣，而且又沒有比它們更好的其他方案，所以它們就被更好的其他方案，所以它們就被稱之為多目標規(guī)劃問題的非劣解稱之為多目標規(guī)劃問題的非劣解或有效解，其余方案都稱為劣解?；蛴行Ы猓溆喾桨付挤Q為劣解。所有非劣解構成的集合稱為非劣所有非劣解構成的集合稱為非劣解集。解集。2f1f非劣解非劣解可以用圖1.1說明。圖圖1.1 多目標規(guī)劃的劣解與非劣解多目標規(guī)劃的劣解與非劣解 當目標函數(shù)處于沖突狀態(tài)

49、時，就不會存在使所有目標函數(shù)同時達到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。 第二節(jié)第二節(jié) 多目標規(guī)劃求解技術簡介多目標規(guī)劃求解技術簡介 為了求得多目標規(guī)劃問題的非劣解，常常需要將多目標規(guī)劃問題轉化為單目標規(guī)劃問題去處理。實現(xiàn)這種轉化，有如下幾種建模方法。 一、效用最優(yōu)化模型一、效用最優(yōu)化模型 (線性和加權法線性和加權法) 二、平方和加權法二、平方和加權法 三、約束模型三、約束模型 四、目標規(guī)劃模型四、目標規(guī)劃模型 五、目標達到法五、目標達到法)(maxXZGX )(是與各目標函數(shù)相關的效用函數(shù)的和函數(shù)。 一、效用最優(yōu)化模型（線性加權法）一、效用最優(yōu)化模型（線性

50、加權法） 建模依據(jù)：規(guī)劃問題的各個目標函數(shù)可以通過一定的方式進行求和運算。這種方法將一系列的目標函數(shù)與效用函數(shù)建立相關關系，各目標之間通過效用函數(shù)協(xié)調，使多目標規(guī)劃問題轉化為傳統(tǒng)的單目標規(guī)劃問題： （2.12.1） （2.22.2） 在用效用函數(shù)作為規(guī)劃目標時，需要確定一組權值 來反映原問題中各目標函數(shù)在總體目標中的權重，即：式中，諸 應滿足：若采用向量與矩陣 ikiii1max), 2 , 1(),(21migxxxiniikii11TmaxGX)(規(guī)劃決策者對每一個目標函數(shù)都能提出所期望的值（或稱滿意值）；通過比較實際值 與期望值 之間的偏差來選擇問題的解，其數(shù)學表達式如下：ifif21)

51、(minkiiiiffaZ), 2 , 1(),(21migxxxini二、平方和加權法二、平方和加權法或寫成矩陣形式： 式中， 是與第i個目標函數(shù)相關的權重； A是由 組成的mm對 角矩陣。)()(minFFAFFZTGX )(ia), 2 , 1(kiai三、約束模型三、約束模型 理論依據(jù) ：若規(guī)劃問題的某一目標可以給出一個可供選擇的范圍，則該目標就可以作為約束條件而被排除出目標組，進入約束條件組中。假如，除第一個目標外，其余目標都可以提出一個可供選擇的范圍，則該多目標規(guī)劃問題就可以轉化為單目標規(guī)劃問題： )(max(min)1XfZ GX )(max11min1FFF),(max(min

52、)211nxxxfZ), 2 , 1(),(21migxxxini), 3 , 2(maxminkjfffjjj采用矩陣可記為：四、目標規(guī)劃模型四、目標規(guī)劃模型 也需要預先確定各個目標的期望值 ，同時給每一個目標賦予一個優(yōu)先因子和權系數(shù)，假定有K個目標，L個優(yōu)先級 ，目標規(guī)劃模型的數(shù)學形式為： if)(KL LlKkklkklklddpZ11)(min), 2 , 1(),(21migxxxini), 2 , 1(Kifddfiiii式中： 和 分別表示與 相應的、與 相比 的目標超過值和不足值，即正、負偏差變量； 表示第l個優(yōu)先級； 、 表示在同一優(yōu)先級 中，不同目標 的正、負偏差變量的權系數(shù)。 ididif*iflplklklp五、目標達到法 首先將多目標規(guī)劃模型化為如下標準形式： )()()(min)(min21XfXfXfxFk000)()()()(21XXXXm在求解之前，先設計與目標函數(shù)相應的一組目標值理想化的期望目標 ,每一個目標對應的權重系數(shù)為 ，再設 為一松弛因子。那么，多目標規(guī)劃問題就轉化為： ), 2 , 1(*kifi), 2 , 1(kiwi,minX), 2 , 1()(*kifwXfiii), 2 , 1(0)(mjXj 用目標達到法求解多目標規(guī)劃的計算過程，可以通過調用Matlab軟