1、目標(biāo)規(guī)劃方法與 優(yōu)化問(wèn)題的Matlab求解,內(nèi)容提要,8.1 線性規(guī)劃與目標(biāo)規(guī)劃 8.2 目標(biāo)規(guī)劃的數(shù)學(xué)模型 8.3 目標(biāo)規(guī)劃模型的實(shí)例 8.4 數(shù)據(jù)包絡(luò)分析,8.1 線性規(guī)劃與目標(biāo)規(guī)劃,線性規(guī)劃通常考慮一個(gè)目標(biāo)函數(shù)(問(wèn)題簡(jiǎn)單),目標(biāo)規(guī)劃考慮多個(gè)目標(biāo)函數(shù)(問(wèn)題復(fù)雜),線性規(guī)劃,目標(biāo)規(guī)劃,某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需要用到A,B,C三種設(shè)備，關(guān)于產(chǎn)品的盈利與使用設(shè)備的工時(shí)及限制如下表所示。,例8.1 生產(chǎn)安排問(wèn)題,問(wèn)該企業(yè)應(yīng)如何安排生產(chǎn)，使得在計(jì)劃期內(nèi)總利潤(rùn)最大？,1. 線性規(guī)劃建模,該例8.1是一個(gè)線性規(guī)劃問(wèn)題，直接考慮它的線性規(guī)劃模型,設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1, x2,建立線性規(guī)劃模型：

2、,用Lindo或Lingo軟件求解,得到最優(yōu)解,2. 目標(biāo)規(guī)劃建模,在上例8.1中，企業(yè)的經(jīng)營(yíng)目標(biāo)不僅要考慮利潤(rùn)，還需要考慮多個(gè)方面，因此增加下列因素(目標(biāo))：,力求使利潤(rùn)指標(biāo)不低于1500元,考慮到市場(chǎng)需求,甲、乙兩種產(chǎn)品的產(chǎn)量比應(yīng)盡量保持1:2,設(shè)備A為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用,設(shè)備C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上，設(shè)備B是設(shè)備C的3倍,從上述問(wèn)題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標(biāo)規(guī)劃的方法進(jìn)行建模求解,某汽車(chē)銷(xiāo)售公司委托一個(gè)廣告公司在電視上為其做廣告，汽車(chē)銷(xiāo)售公司提出三個(gè)目標(biāo)：,例8.2 汽車(chē)廣告費(fèi)問(wèn)題,廣告公司必須決定購(gòu)買(mǎi)兩種

3、類(lèi)型的電視廣告展播各多少分鐘？,第一個(gè)目標(biāo)，至少有40萬(wàn)高收入的男性公民(記為HIM)看到這個(gè)廣告,第二個(gè)目標(biāo)，至少有60萬(wàn)一般收入的公民(記為L(zhǎng)IP)看到這個(gè)廣告,第三個(gè)目標(biāo)，至少有35萬(wàn)高收入的女性公民(記為HIW)看到這個(gè)廣告,廣告公司可以從電視臺(tái)購(gòu)買(mǎi)兩種類(lèi)型的廣告展播：足球賽中插播廣告和電視系列劇插播廣告。廣告公司最多花費(fèi)60萬(wàn)元的電視廣告費(fèi)。每一類(lèi)廣告展播每一分鐘的花費(fèi)及潛在的觀眾人數(shù)如下表所示,3.嘗試線性規(guī)劃建模,對(duì)于例8.2考慮建立線性規(guī)劃模型,設(shè)x1, x2分別是足球賽和電視系列劇中插播的分鐘數(shù)，按照要求，可以列出相應(yīng)的線性規(guī)劃模型,用Lindo或Lingo軟件求解,會(huì)發(fā)現(xiàn)該

4、問(wèn)題不可行。,（可以任意目標(biāo)）,4. 線性規(guī)劃建模局限性,線性規(guī)劃要求所有求解的問(wèn)題必須滿足全部的約束，而實(shí)際問(wèn)題中并非所有約束都需要嚴(yán)格的滿足；,線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問(wèn)題，而對(duì)一些次目標(biāo)只能轉(zhuǎn)化為約束處理。但在實(shí)際問(wèn)題中，目標(biāo)和約束好似可以相互轉(zhuǎn)化的，處理時(shí)不一定要嚴(yán)格區(qū)分；,線性規(guī)劃在處理問(wèn)題時(shí)，將各個(gè)約束(也可看作目標(biāo))的地位看成同等重要，而在實(shí)際問(wèn)題中，各個(gè)目標(biāo)的重要性即有層次上的差別，也有在同一層次上不同權(quán)重的差別,線性規(guī)劃尋求最優(yōu)解，而許多實(shí)際問(wèn)題只需要找到滿意解就可以了。,8. 2 目標(biāo)規(guī)劃的數(shù)學(xué)模型,為了克服線性規(guī)劃的局限性,目標(biāo)規(guī)劃采用如下手段：,1. 設(shè)置偏差變量;

5、 2. 統(tǒng)一處理目標(biāo)與約束; 3. 目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù)。,目標(biāo)規(guī)劃的基本概念,1. 設(shè)置偏差變量,用偏差變量(Deviational variables)來(lái)表示實(shí)際值與目標(biāo)值 之間的差異，令 - 超出目標(biāo)的差值，稱為正偏差變量 - 未達(dá)到目標(biāo)的差值，稱為負(fù)偏差變量 其中 與 至少有一個(gè)為0,約定如下： 當(dāng)實(shí)際值超過(guò)目標(biāo)值時(shí)，有 當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)，有 當(dāng)實(shí)際值與目標(biāo)值一致時(shí)，有,2. 統(tǒng)一處理目標(biāo)與約束,在目標(biāo)規(guī)劃中，約束可分兩類(lèi)，一類(lèi)是對(duì)資源有嚴(yán)格限制 的，稱為剛性約束(Hard Constraint)；例如在用目標(biāo)規(guī)劃 求解例8.1中設(shè)備A禁止超時(shí)使用，則有剛性約束,另一類(lèi)是可以不嚴(yán)

6、格限制的，連同原線性規(guī)劃的目標(biāo),構(gòu) 成柔性約束(Soft Constraint).例如在求解例8.1中，我們 希望利潤(rùn)不低于1500元，則目標(biāo)可表示為,求解例8.1中甲、乙兩種產(chǎn)品 的產(chǎn)量盡量保持1:2的比例， 則目標(biāo)可表示為,設(shè)備C可以適當(dāng)加班，但要控制， 則目標(biāo)可表示為,設(shè)備B既要求充分利用，又盡可能 不加班，則目標(biāo)可表示為,從上面的分析可以看到： 如果希望不等式保持大于等于，則極小化負(fù)偏差； 如果希望不等式保持小于等于，則極小化正偏差； 如果希望保持等式，則同時(shí)極小化正、負(fù)偏差,3.目標(biāo)的優(yōu)先級(jí)與權(quán)系數(shù),在目標(biāo)規(guī)劃模型中，目標(biāo)的優(yōu)先分為兩個(gè)層次，第一個(gè)層次是目標(biāo)分成不同的優(yōu)先級(jí)，在計(jì)算目

7、標(biāo)規(guī)劃時(shí)，必須先優(yōu)化高優(yōu)先級(jí)的目標(biāo)，然后再優(yōu)化低優(yōu)先級(jí)的目標(biāo)。通常以P1,P2,.表示不同的因子,并規(guī)定PkPk+1，第二個(gè)層次是目標(biāo)處于同一優(yōu)先級(jí)，但兩個(gè)目標(biāo)的權(quán)重不一樣，因此兩目標(biāo)同時(shí)優(yōu)化，用權(quán)系數(shù)的大小來(lái)表示目標(biāo)重要性的差別。,解在例.1中設(shè)備A是剛性約束，其于是柔性約束首先，最重要的指標(biāo)是企業(yè)的利潤(rùn)，將它的優(yōu)先級(jí)列為第一級(jí)；其次，甲、乙兩種產(chǎn)品的產(chǎn)量保持1:2的比例，列為第二級(jí)；再次，設(shè)備 B和C的工作時(shí)間要有所控制，列為第三級(jí)，設(shè)備B的重要性是設(shè)備C的三倍，因此它們的權(quán)重不一樣。由此可以得到相應(yīng)的目標(biāo)規(guī)劃模型。,目標(biāo)規(guī)劃模型的建立,例8.3 用目標(biāo)規(guī)劃方法求解例8. 1,目標(biāo)規(guī)劃的一

8、般模型,目標(biāo)規(guī)劃模型的一般數(shù)學(xué)表達(dá)式為：,求解目標(biāo)規(guī)劃的序貫式算法,其算法是根據(jù)優(yōu)先級(jí)的先后次序，將目標(biāo)規(guī)劃問(wèn)題分解成 一系列的單目標(biāo)規(guī)劃問(wèn)題，然后再依次求解。 算法8.1 對(duì)于k=1,2,q,求解單目標(biāo)問(wèn)題,解因?yàn)槊總€(gè)單目標(biāo)問(wèn)題都是一個(gè)線性規(guī)劃問(wèn)題， 因此可以采用LINDO軟件進(jìn)行求解。按照算法8.1和 例8.3目標(biāo)規(guī)劃模型編寫(xiě)單個(gè)的線性規(guī)劃求解程序。 求第一級(jí)目標(biāo)企業(yè)利潤(rùn)最大，列出LINDO程序。 程序名：exam0804a.ltx,例8.4 用算法8.1求解例8. 3,目標(biāo),解因求出的目標(biāo)函數(shù)的最優(yōu)值為，即第一級(jí)偏差為 .再求第二級(jí)目標(biāo)，列出其LINDO程序。 程序名：exam0804b

9、.ltx,例8.4 用算法8.1求解例8. 3,修改的目標(biāo),增加的約束,解因求出的目標(biāo)函數(shù)的最優(yōu)值仍為，即第二級(jí)偏差 仍為. 繼續(xù)求第三級(jí)目標(biāo)，列出其LINDO程序。 程序名：exam0804c.ltx,例8.4 用算法8.1求解例8. 3,求出的目標(biāo)函數(shù)的最優(yōu)值為29,即第三級(jí)偏差為29,分 析結(jié)果, x1為2, x2為4, DPLUS1 為100,因此目標(biāo)規(guī)劃的 最優(yōu)解為x *=(2,4),最優(yōu)利潤(rùn)為1600.,修改的目標(biāo),增加的約束,解按照算法8.1和例8.3目標(biāo)規(guī)劃模型編寫(xiě)LINGO求解程 序，列出其LINGO程序, 程序名：exam0805.lg4,例8.5 (繼例8.4) 用算法8

10、.1求解例8. 3的LINGO程序,程序運(yùn)行說(shuō)明，分三次求解： 在做第一級(jí)目標(biāo)計(jì)算時(shí)，P(1),P(2)和P(3)分別輸入1,0和0，Goal(1)和Goal(2)輸入兩個(gè)較大的數(shù)，表示這兩項(xiàng)約束不起作用； 在做第二級(jí)目標(biāo)計(jì)算時(shí)，P(1),P(2)和P(3)分別輸入0,1和0，由于第一級(jí)的偏差為0，因此Goal(1)為0，Goal(2)輸入一個(gè)較大的數(shù)； 在做第三級(jí)計(jì)算時(shí)，P(1),P(2)和P(3)分別輸入0,0和1，由于第一級(jí)、第二級(jí)的偏差為0，因此Goal(1)和Goal(2)的輸入值也為0。 結(jié)果可以參見(jiàn)程序演示！,由于在例8.4中雖然給出了目標(biāo)規(guī)劃問(wèn)題的最優(yōu)解,但需要連續(xù)編幾個(gè)LIN

11、DO程序,在使用時(shí)不方便,下面使用LINGO軟件,編寫(xiě)一個(gè)通用程序。,8. 3 目標(biāo)規(guī)劃模型的實(shí)例,前面介紹了目標(biāo)規(guī)劃的求解方法，接著再介紹幾個(gè)目標(biāo)規(guī)劃模型的實(shí)例。,某音像商店有5名全職售貨員和4名兼職售貨員。全職售貨員每月工作160小時(shí)，兼職售貨員每月工作80小時(shí)。根據(jù)過(guò)去的工作記錄，全職售貨員每小時(shí)銷(xiāo)售CD25張，平均每小時(shí)工資15元，加班工資每小時(shí)22.5元。兼職售貨員每小時(shí)銷(xiāo)售CD10張，平均每小時(shí)工資10元，加班工資每小時(shí)10元?，F(xiàn)在預(yù)測(cè)下月CD銷(xiāo)售量為27500張，商店每周開(kāi)門(mén)營(yíng)業(yè)6天，所以可能要加班。另每出售一張CD盈利1.5元。,例8.6,該商店經(jīng)理認(rèn)為，保持穩(wěn)定的就業(yè)水平加上

12、必要的加班，比不加班但就業(yè)水平不穩(wěn)定要好。但全職售貨員如果加班過(guò)多，就會(huì)因疲勞過(guò)度而造成效率下降，因此不允許每月加班超過(guò)100小時(shí)。建立相應(yīng)的目標(biāo)規(guī)劃模型，并運(yùn)用LINGO軟件進(jìn)行求解。,解 首先建立目標(biāo)約束的優(yōu)先級(jí)。 P1：下月的CD銷(xiāo)售量達(dá)到27500張； P2： 限制全職售貨員加班時(shí)間不超過(guò)100小時(shí)； P3： 保持全體售貨員充分就業(yè)，因?yàn)槌浞止ぷ魇橇?好勞資關(guān)系的重要因素，但對(duì)全職售貨員要比 兼職售貨員加倍優(yōu)先考慮； P4： 盡量減少加班時(shí)間，但對(duì)兩種售貨員區(qū)別對(duì) 待，優(yōu)先權(quán)因子由他們對(duì)利潤(rùn)的貢獻(xiàn)而定。,例8.6,例8.6,第二，建立目標(biāo)約束。 (1) 銷(xiāo)售目標(biāo)約束。設(shè) x1 ：全體全

13、職售貨員下月的工作時(shí)間； x2 ：全體兼職售貨員下月的工作時(shí)間； ：達(dá)不到銷(xiāo)售目標(biāo)的偏差； ：超過(guò)銷(xiāo)售目標(biāo)的偏差。 希望下月的銷(xiāo)售量超過(guò)27500張CD片，因此銷(xiāo)售目標(biāo)為,例8.6,第二，建立目標(biāo)約束。 (2) 正常工作時(shí)間約束，設(shè) ：全體全職售貨員下月的停工時(shí)間； ：全體全職售貨員下月的加班時(shí)間； ：全體兼職售貨員下月的停工時(shí)間； ：全體兼職售貨員下月的加班時(shí)間。 由于希望保持全體售貨員充分就業(yè)，同時(shí)加倍優(yōu)先考慮全職售貨員,因此工作目標(biāo)約束為,例8.6,第二，建立目標(biāo)約束。 (3) 正常工作時(shí)間約束，設(shè) ：全體全職售貨員下月加班不足100小時(shí)的偏差； ：全體全職售貨員下月加班超過(guò)100小時(shí)的

14、偏差。 限制全職售貨員加班時(shí)間不超過(guò)100小時(shí)，將加班約束看成正常上班約束，不同的是右端加上100小時(shí)，因此加班目標(biāo)約束為,例8.6,第二，建立目標(biāo)約束。 接上(3) 另外，全職售貨員加班1小時(shí)，商店得到的利潤(rùn) 為15元(25*1.5-22.5=15)，兼職售貨員加班1小時(shí)，商店得 到的利潤(rùn)為5元(10*1.5-10=5)，因此加班1小時(shí)全職售貨員 獲得的利潤(rùn)是兼職售貨員的3倍，故權(quán)因子之比為,所以，另一個(gè)加班目標(biāo)約束為：,例8.6,第三，按目標(biāo)的優(yōu)先級(jí)，寫(xiě)出相應(yīng)的目標(biāo)規(guī)劃模型：,第四，寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0806.lg4.,程序運(yùn)行說(shuō)明，分四次求解： 在做第一級(jí)目標(biāo)計(jì)算

15、時(shí)，P(1),P(2),P(3)和P(4)分別輸入1,0,0和0，Goal(1), Goal(2)和Goal(3)輸入兩個(gè)較大的數(shù)，表示這兩項(xiàng)約束不起作用； 在做第二級(jí)目標(biāo)計(jì)算時(shí)，P(1),P(2),P(3)和P(4)分別輸入0,1,0和0，由于第一級(jí)的偏差為0，因此Goal(1)為0,Goal(2)和Goal(3)輸入一個(gè)較大的數(shù)； 在做第三級(jí)計(jì)算時(shí)，P(1),P(2),P(3)和P(4)分別輸入0,0,1和0，由于第一級(jí),第二級(jí)的偏差為0，因此Goal(1)和Goal(2)的輸入值也為0， Goal(3)輸入一個(gè)較大的數(shù)； 在做第四級(jí)計(jì)算時(shí)，P(1),P(2),P(3)和P(4)分別輸入0

16、,0,0和1，由于第一級(jí),第二級(jí)和第三級(jí)的偏差為0,因此Goal(1),Goal(2)和Goal(3)輸入值也為0； 全職售貨員總工作時(shí)間為900小時(shí)(加班100小時(shí))，兼職售貨員總工作 時(shí)間500小時(shí)(加班180小時(shí))，下月共銷(xiāo)售CD27500張，商店共獲得利潤(rùn) 27500*1.5-800*15-100*22.5-500*10=22000(元) 其結(jié)果可以參見(jiàn)程序演示！,某計(jì)算機(jī)公司生產(chǎn)三種型號(hào)的筆記本電腦A,B,C。這 三種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn) 1臺(tái)A,B,C型號(hào)的筆記本電腦分別需要5,8,12小時(shí)。 公司裝配線正常的生產(chǎn)時(shí)間是每月1700小時(shí)。公司 營(yíng)業(yè)部門(mén)估計(jì)A,B

17、,C三種筆記本電腦的利潤(rùn)分別是 每臺(tái)1000,1440,2520元，而公司預(yù)測(cè)這個(gè)月生產(chǎn)的筆 記本電腦能夠全部售出。,例8.7,例8.7,公司經(jīng)理考慮以下目標(biāo)： 第一目標(biāo)：充分利用正常的生產(chǎn)能力，避免開(kāi)工不足； 第二目標(biāo)：優(yōu)先滿足老客戶的需求，A,B,C三種型號(hào)的電腦 50,50,80臺(tái)，同時(shí)根據(jù)三種電腦的純利潤(rùn)分配不同的權(quán)因子； 第三目標(biāo)：限制裝配線加班時(shí)間，不允許超過(guò)200小時(shí)； 第四目標(biāo)：滿足各種型號(hào)電腦的銷(xiāo)售目標(biāo),A,B,C型號(hào)分別為 100,120,100臺(tái),再根據(jù)三種電腦的純利潤(rùn)分配不同的權(quán)因子； 第五目標(biāo)：裝配線的加班時(shí)間盡可能少。 請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型,并用LINGO軟件求

18、解。,例8.7,解 建立目標(biāo)約束。 (1) 裝配線正常生產(chǎn) 設(shè)生產(chǎn)A,B,C型號(hào)的電腦為x1, x2, x3臺(tái)， 裝配線正常生產(chǎn)時(shí)間未利用數(shù)， 裝配線加班時(shí)間， 希望裝配線正常生產(chǎn),避免開(kāi)工不足,因此裝配線 約束目標(biāo)為,例8.7,例8.7,(2) 銷(xiāo)售目標(biāo) (接上) 再考慮一般銷(xiāo)售，類(lèi)似上面的討論，得到,例8.7,(3) 加班限制 首先是限制裝配線加班時(shí)間，不允許超過(guò)200 小時(shí)，因此得到,其次裝配線的加班時(shí)間盡可能少，即,例8.7,寫(xiě)出相應(yīng)的目標(biāo)規(guī)劃模型：,寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0807.lg4.,程序運(yùn)行說(shuō)明： 經(jīng)5次計(jì)算得到x1=100, x2=55, x3=80。裝

19、配線生產(chǎn)時(shí)間為1900小時(shí)，滿足裝配線加班不超過(guò)200小時(shí)的要求。能夠滿足老客戶的需求，但未能達(dá)到銷(xiāo)售目標(biāo)。銷(xiāo)售總利潤(rùn)為 100 x1000+55x1440+80 x2520=380800(元),其結(jié)果可以參見(jiàn)程序演示！,例8.8,已知三個(gè)工廠生產(chǎn)的產(chǎn)品供應(yīng)給四個(gè)用戶，各工廠 生產(chǎn)量、用戶需求量及從各工廠到用戶的單位產(chǎn)品 的運(yùn)輸費(fèi)用如表所示。由于總生產(chǎn)量小于總需求量, 上級(jí)部門(mén)經(jīng)研究后，制定了調(diào)配方案的8項(xiàng)指標(biāo)，并 規(guī)定重要性的次序是:,例8.8,第一目標(biāo)：用戶4為重要部門(mén),需求量必須全部滿足； 第二目標(biāo)：供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少 于100個(gè)單位；第三目標(biāo)：每個(gè)用戶的滿足率不低于

20、80%；第四目標(biāo)：應(yīng)盡量滿足各用戶的需求； 第五目標(biāo)：新方案的總運(yùn)費(fèi)不超過(guò)原運(yùn)輸問(wèn)題的調(diào)度 方案的10%；第六目標(biāo)：因道路限制，工廠2到用戶4 的路線應(yīng)盡量避免運(yùn)輸任務(wù)； 第七目標(biāo)：用戶1和用戶3的滿足率應(yīng)盡量保持平衡； 第八目標(biāo)：力求減少總運(yùn)費(fèi)。 請(qǐng)列出相應(yīng)的目標(biāo)規(guī)劃模型，并用LINGO軟件求解。,例8.8,解 求解原運(yùn)輸問(wèn)題。 由于總生產(chǎn)量小于總需求量,虛設(shè)工廠4,生產(chǎn)量為100 個(gè)單位,到各個(gè)用戶間的運(yùn)輸單價(jià)為0,利用第7章介紹 的運(yùn)輸問(wèn)題的求解方法,用LINGO軟件求解,得到總 運(yùn)費(fèi)是2950元,運(yùn)輸方案如表所示.,例8.8,從上表可以看出，上述方案中，第一個(gè)目標(biāo)就不滿 足，用戶4的需

21、求量得不到滿足。下面按照目標(biāo)的 重要性的等級(jí)列出目標(biāo)規(guī)劃的約束和目標(biāo)函數(shù)。 設(shè) xi j 為工廠 i 調(diào)配給用戶 j 的運(yùn)量.,(1) 供應(yīng)約束應(yīng) 嚴(yán)格滿足, 即,(2) 供應(yīng)用戶1的產(chǎn)品中, 工廠3的產(chǎn)品不少于100 個(gè)單位, 即,例8.8,(3) 需求約束. 各用戶的滿 足率不低于 80%, 即,需求應(yīng)盡量 滿足各用戶 的需求，即,新方案的總運(yùn)費(fèi)不超過(guò)原運(yùn)方案的10%（原運(yùn)輸 方案的運(yùn)費(fèi)為2950元），即,(5) 工廠2到用戶4的路線 應(yīng)盡量避免運(yùn)輸任務(wù), 即,(6) 用戶1和用戶3的滿足率應(yīng)盡量保持平衡，即,(7)力求總運(yùn) 費(fèi)最少, 即,例8.8,寫(xiě)出相應(yīng)的目標(biāo)函數(shù)為,寫(xiě)出相應(yīng)的LING

22、O程序，程序名：exam0808.lg4.,程序運(yùn)行說(shuō)明,其結(jié)果可以參見(jiàn)程序演示！,經(jīng)8次計(jì)算，得到最終的計(jì)算結(jié)果，見(jiàn)下表所示。 總運(yùn)費(fèi)為3360元，高于原運(yùn)費(fèi)410元，超過(guò)原方案 10%的上限115元。,在經(jīng)濟(jì)研究中，常常需要考慮多個(gè)目標(biāo)，如經(jīng)濟(jì)效益目標(biāo)，生態(tài)效益目標(biāo)，社會(huì)效益目標(biāo)，等等。為了滿足這類(lèi)問(wèn)題研究之需要，對(duì)多目標(biāo)規(guī)劃方法作一些介紹。,第一節(jié) 多目標(biāo)規(guī)劃及其非劣解,多目標(biāo)規(guī)劃及其非劣解 多目標(biāo)規(guī)劃求解技術(shù)簡(jiǎn)介,一、多目標(biāo)規(guī)劃及其非劣解,（一）任何多目標(biāo)規(guī)劃問(wèn)題，都由兩個(gè)基本部分組成： （1）兩個(gè)以上的目標(biāo)函數(shù)； （2）若干個(gè)約束條件。 （二）多目標(biāo)決策的兩個(gè)較明顯的特點(diǎn)： （1）目

23、標(biāo)之間的不可公度性； （2）目標(biāo)之間的矛盾性。,（三）對(duì)于多目標(biāo)規(guī)劃問(wèn)題，可以將其數(shù)學(xué)模型一般地描寫(xiě)為如下形式：,（1.2）,（1.1）,式中： 為決策變量向量。,如果將（1.1）和（1.2）式進(jìn)一步縮寫(xiě)， 即： （1.3） （1.4） 式中： 是k維函數(shù)向量， k是目標(biāo)函數(shù)的個(gè)數(shù)； 是m維函數(shù)向量； 是m維常數(shù)向量；m是約束方程的 個(gè)數(shù)。,對(duì)于線性多目標(biāo)規(guī)劃問(wèn)題，（1.3）和（1.4）式可以進(jìn)一步用矩陣表示： （1.5） （1.6） 式中： 為n維決策變量向量； 為kn矩陣，即目標(biāo)函數(shù)系數(shù)矩陣； 為mn矩陣，即約束方程系數(shù)矩陣； 為m維的向量，約束向量。,二、多目標(biāo)規(guī)劃的非劣解,多目標(biāo)規(guī)劃問(wèn)

24、題的求解不能只追求一個(gè)目標(biāo)的最優(yōu)化（最大或最小），而不顧其它目標(biāo)。,在圖1.1中，就方案和來(lái)說(shuō)，的 目標(biāo)值比大，但其目標(biāo)值 比小，因此無(wú)法確定這兩個(gè)方案的優(yōu)與劣。在各個(gè)方案之間，顯然：比好，比好，比好，比好。而對(duì)于方案、之間則無(wú)法確定優(yōu)劣，而且又沒(méi)有比它們更好的其他方案，所以它們就被稱之為多目標(biāo)規(guī)劃問(wèn)題的非劣解或有效解，其余方案都稱為劣解。所有非劣解構(gòu)成的集合稱為非劣解集。,非劣解可以用圖1.1說(shuō)明。,圖1.1 多目標(biāo)規(guī)劃的劣解與非劣解,當(dāng)目標(biāo)函數(shù)處于沖突狀態(tài)時(shí)，就不會(huì)存在使所有目標(biāo)函數(shù)同時(shí)達(dá)到最大或最小值的最優(yōu)解，于是我們只能尋求非劣解（又稱非支配解或帕累托解）。,第二節(jié) 多目標(biāo)規(guī)劃求解技術(shù)

25、簡(jiǎn)介,為了求得多目標(biāo)規(guī)劃問(wèn)題的非劣解，常常需要將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題去處理。實(shí)現(xiàn)這種轉(zhuǎn)化，有如下幾種建模方法。 一、效用最優(yōu)化模型 (線性和加權(quán)法) 二、平方和加權(quán)法 三、約束模型 四、目標(biāo)規(guī)劃模型 五、目標(biāo)達(dá)到法,是與各目標(biāo)函數(shù)相關(guān)的效用函數(shù)的和函數(shù)。,一、效用最優(yōu)化模型（線性加權(quán)法） 建模依據(jù)：規(guī)劃問(wèn)題的各個(gè)目標(biāo)函數(shù)可以通過(guò)一定的方式進(jìn)行求和運(yùn)算。這種方法將一系列的目標(biāo)函數(shù)與效用函數(shù)建立相關(guān)關(guān)系，各目標(biāo)之間通過(guò)效用函數(shù)協(xié)調(diào)，使多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為傳統(tǒng)的單目標(biāo)規(guī)劃問(wèn)題：,（2.1）,（2.2）,在用效用函數(shù)作為規(guī)劃目標(biāo)時(shí)，需要確定一組權(quán)值 來(lái)反映原問(wèn)題中各目標(biāo)函數(shù)在總體目標(biāo)中的

26、權(quán)重，即： 式中，諸 應(yīng)滿足： 若采用向量與矩陣,規(guī)劃決策者對(duì)每一個(gè)目標(biāo)函數(shù)都能提出所期望的值（或稱滿意值）； 通過(guò)比較實(shí)際值 與期望值 之間的偏差來(lái)選擇問(wèn)題的解，其數(shù)學(xué)表達(dá)式如下：,二、平方和加權(quán)法,或?qū)懗删仃囆问剑?式中， 是與第i個(gè)目標(biāo)函數(shù)相關(guān)的權(quán)重； A是由 組成的mm對(duì) 角矩陣。,三、約束模型 理論依據(jù) ：若規(guī)劃問(wèn)題的某一目標(biāo)可以給出一個(gè)可供選擇的范圍，則該目標(biāo)就可以作為約束條件而被排除出目標(biāo)組，進(jìn)入約束條件組中。 假如，除第一個(gè)目標(biāo)外，其余目標(biāo)都可以提出一個(gè)可供選擇的范圍，則該多目標(biāo)規(guī)劃問(wèn)題就可以轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題：,采用矩陣可記為：,四、目標(biāo)規(guī)劃模型,也需要預(yù)先確定各個(gè)目標(biāo)的期

27、望值 ，同時(shí)給每一個(gè)目標(biāo)賦予一個(gè)優(yōu)先因子和權(quán)系數(shù)，假定有K個(gè)目標(biāo)，L個(gè)優(yōu)先級(jí) ，目標(biāo)規(guī)劃模型的數(shù)學(xué)形式為：,式中： 和 分別表示與 相應(yīng)的、與 相比 的目標(biāo)超過(guò)值和不足值，即正、負(fù)偏差變量； 表示第l個(gè)優(yōu)先級(jí)； 、 表示在同一優(yōu)先級(jí) 中，不同目標(biāo) 的正、負(fù)偏差變量的權(quán)系數(shù)。,五、目標(biāo)達(dá)到法,首先將多目標(biāo)規(guī)劃模型化為如下標(biāo)準(zhǔn)形式：,在求解之前，先設(shè)計(jì)與目標(biāo)函數(shù)相應(yīng)的一組 目標(biāo)值理想化的期望目標(biāo) ,每 一個(gè)目標(biāo)對(duì)應(yīng)的權(quán)重系數(shù)為 ， 再設(shè) 為一松弛因子。那么，多目標(biāo)規(guī)劃問(wèn) 題就轉(zhuǎn)化為：,用目標(biāo)達(dá)到法求解多目標(biāo)規(guī)劃的計(jì)算過(guò)程，可以通過(guò)調(diào)用Matlab軟件系統(tǒng)優(yōu)化工具箱中的fgoalattain函數(shù)實(shí)現(xiàn)

28、。,x = fgoalattain(fun,x0,goal,weight,A,b) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub) x = fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) x,fval = fgoalattain(.),第四節(jié) 多目標(biāo)規(guī)劃應(yīng)用實(shí)例,一、生產(chǎn)計(jì)劃問(wèn)題 二、投資問(wèn)題,某企業(yè)擬生產(chǎn)A和B兩種產(chǎn)品，其生產(chǎn)投資費(fèi)用分別為2100元/t和4800元/t。A、B兩種產(chǎn)品的利潤(rùn)分別為3600元/t和6500元/t。A、B產(chǎn)品每月的最大生產(chǎn)能力分別為5t和8t；市場(chǎng)對(duì)這兩種產(chǎn)品總量的需求每月不少于9t。試問(wèn)該企業(yè)應(yīng)該如何安排生產(chǎn)計(jì)