第一講目標(biāo)規(guī)劃模型

1、第一講 目標(biāo)規(guī)劃模型 目標(biāo)規(guī)劃是由線性規(guī)劃發(fā)展演變而來(lái)的。線性規(guī)劃考慮的是只有可以個(gè)目標(biāo)函數(shù)的問(wèn)題，而實(shí)際問(wèn)題中往往需要考慮多個(gè)目標(biāo)函數(shù)，這些目標(biāo)不僅有主次關(guān)系，而且有的還互相矛盾。這些問(wèn)題用線性規(guī)劃求解就比較困難，因而提出了目標(biāo)規(guī)劃。這里所討論的目標(biāo)規(guī)劃實(shí)質(zhì)上是線性目標(biāo)規(guī)劃。1.1線性規(guī)劃與目標(biāo)規(guī)劃為了進(jìn)一步了解目標(biāo)規(guī)劃的特點(diǎn)和性質(zhì)，下面對(duì)同一問(wèn)題分別考慮線性規(guī)劃建模和目標(biāo)規(guī)劃建模。1.1.1線性規(guī)劃建模與目標(biāo)規(guī)劃建模例1.1（生產(chǎn)安排問(wèn)題） 某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需要用到A、B、C三種設(shè)備，關(guān)于產(chǎn)品的盈利與使用設(shè)備的工時(shí)及限制如表1-1所示。問(wèn)：該企業(yè)應(yīng)如何安排生產(chǎn)，使得在計(jì)劃期內(nèi)總利

2、潤(rùn)最大？表1-1 生產(chǎn)產(chǎn)品使用設(shè)備的工時(shí)、限制和產(chǎn)品的盈利甲乙設(shè)備的生產(chǎn)能力/hA/（h/件）2212B/（h/件）4016C/（h/件）0515盈利/（元/件）2003001. 線性規(guī)劃建模例8.1是一個(gè)線性規(guī)劃問(wèn)題，直接考慮它的線性規(guī)劃模型。設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為，建立線性規(guī)劃模型：用LINDO或LINGO軟件求解，得到最優(yōu)解。2. 目標(biāo)規(guī)劃建模企業(yè)的經(jīng)營(yíng)目標(biāo)不僅僅是利潤(rùn)，還要考慮多個(gè)方面。例如在例8.1中，增加下列因素（目標(biāo)）：（1） 力求使利潤(rùn)指標(biāo)不低于1500元；（2） 考慮到市場(chǎng)需求，甲、乙兩種產(chǎn)品的產(chǎn)量比應(yīng)盡量保持1：2；（3） 設(shè)備A為貴重設(shè)備，嚴(yán)格禁止超時(shí)使用；（4） 設(shè)備

3、C可以適當(dāng)加班，但要控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上，設(shè)備B是設(shè)備C的3倍。從上述問(wèn)題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標(biāo)規(guī)劃的方法進(jìn)行建模求解。1.1.2 線性規(guī)劃建模的局限性例1.2（汽車廣告費(fèi)問(wèn)題） 某汽車銷售公司委托一個(gè)廣告公司在電視上為其做廣告。汽車銷售公司提出三個(gè)目標(biāo)：第一個(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)買兩種類型的廣告展播：足球賽中插播廣告和電視系列劇中插播廣

4、告。廣告公司最多花費(fèi)60萬(wàn)元的電視廣告費(fèi)。每一類廣告展播每分鐘的花費(fèi)及潛在的觀眾人數(shù)如表1-2所示。廣告公司必須決定為汽車銷售公司購(gòu)買兩種類型的電視廣告展播各多少分鐘？表1-2 廣告展播的花費(fèi)及潛在的觀眾人數(shù)HIMLIPHIW費(fèi)用/（萬(wàn)元/min）足球賽中插播/（萬(wàn)人/min）710510系列劇中插播/（萬(wàn)人/min）35461. 線性規(guī)劃建模對(duì)于例1.2考慮建立線性規(guī)劃模型。設(shè)分別是足球賽和系列劇中插播的分鐘數(shù)，按照要求，列出相應(yīng)的線性規(guī)劃問(wèn)題。用LINDO或LINGO軟件求解，會(huì)發(fā)現(xiàn)該問(wèn)題不可行。2. 線性規(guī)劃建模的局限性通過(guò)上述兩個(gè)例子可以看出，在求解問(wèn)題中，線性規(guī)劃模型存在很大的局限性

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

6、實(shí)際值與目標(biāo)值之間的差異，令d+為超出目標(biāo)的差值，稱為正偏差變量；d-為未達(dá)到目標(biāo)的差值，稱為負(fù)偏差變量。其中d+與d-至少有一個(gè)為0。當(dāng)實(shí)際值超過(guò)目標(biāo)值時(shí)，有d-=0，d+0;當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)，有d+=0，d-0；當(dāng)實(shí)際值與目標(biāo)值一致時(shí)，有d+=d-=0。2. 統(tǒng)一處理目標(biāo)與約束在目標(biāo)規(guī)劃中，約束有兩類，一類是對(duì)資源有嚴(yán)格限制的，同線性規(guī)劃的處理相同，用嚴(yán)格的等式或不等式約束來(lái)處理，例如，用目標(biāo)規(guī)劃求解例8.1，設(shè)備A禁止超時(shí)使用，則有剛性約束：另一類約束是可以不嚴(yán)格控制的，連同原線性規(guī)劃的目標(biāo)，構(gòu)成柔性約束。例如，在求解例8.1中，我們希望利潤(rùn)不低于1500元，則目標(biāo)可表示為甲，乙兩

7、種產(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ì)算目標(biāo)規(guī)劃時(shí)，必須先優(yōu)化高優(yōu)先級(jí)的目標(biāo)，然后再優(yōu)化低優(yōu)先級(jí)的目標(biāo)。通常以P1，P2，表示不同的因子，并規(guī)定。第二個(gè)層次是目標(biāo)處于同一優(yōu)先級(jí)，但兩個(gè)目標(biāo)的權(quán)重不一樣，因此兩目標(biāo)同時(shí)優(yōu)化，但用權(quán)系數(shù)的大

8、小來(lái)表示目標(biāo)重要性的差別。1.2.2 目標(biāo)規(guī)劃模型的建立總的來(lái)講，目標(biāo)規(guī)劃在建模中，除剛性約束必須嚴(yán)格滿足外，對(duì)所有目標(biāo)約束均允許有偏差。其求解過(guò)程要從高到低逐層優(yōu)化，在不增加高層次目標(biāo)的偏差值的情況下，逐次使低層次的偏差達(dá)到極小。例1.3 用目標(biāo)規(guī)劃方法求解例1.1，建立相應(yīng)的目標(biāo)規(guī)劃模型。解 ：在例1.1中設(shè)備A是剛性約束，其余是線性約束。首先，最重要的指標(biāo)是企業(yè)的利潤(rùn)，因此，將它的優(yōu)先級(jí)列為第一級(jí)；其次，甲、乙兩種產(chǎn)品的產(chǎn)量盡量保持1：2的比例，列為第二級(jí)；再次，設(shè)備C，B的工作時(shí)間要有所控制，列為第三級(jí)。在第三級(jí)中，設(shè)備B的重要性是設(shè)備C的三倍，因此，它們的權(quán)重不一樣，設(shè)備B前的系數(shù)是

9、設(shè)備C前系數(shù)的3倍。由此得到相應(yīng)的目標(biāo)規(guī)劃模型。通過(guò)上述實(shí)例，可以給出目標(biāo)規(guī)劃的一般數(shù)學(xué)表達(dá)式。1.2.3 目標(biāo)規(guī)劃的一般模型設(shè)是目標(biāo)規(guī)劃的決策變量，共有m個(gè)約束是剛性約束，可能是等式約束，也可能是不等式約束。設(shè)有l(wèi)個(gè)柔性目標(biāo)約束，其目標(biāo)規(guī)劃約束的偏差為，設(shè)有q個(gè)優(yōu)先級(jí)別，分別為在同一個(gè)優(yōu)先級(jí)中，有不同的權(quán)重，分別記為因此目標(biāo)規(guī)劃模型的一般數(shù)學(xué)表達(dá)式為：1.2.4 求解目標(biāo)規(guī)劃的序貫式算法序貫式算法是求解目標(biāo)規(guī)劃的一種早期算法，其核心是根據(jù)優(yōu)先級(jí)的先后次序，將目標(biāo)規(guī)劃問(wèn)題分解成一系列的單目標(biāo)規(guī)劃問(wèn)題，然后再依次求解。算法1.1（求解目標(biāo)規(guī)劃的序貫式算法）對(duì)于k=1,2,q, 求解單目標(biāo)規(guī)劃問(wèn)題

10、 其最優(yōu)目標(biāo)值為，當(dāng)k=1時(shí)，第三個(gè)約束為空約束。當(dāng)k=q時(shí)，所對(duì)應(yīng)的解為目標(biāo)規(guī)劃的最優(yōu)解。例1.4 用算法1.1求解例1.3。 相關(guān)LINDO程序?yàn)椋?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 計(jì)算結(jié)果如下： LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION

11、 VALUE 1) 0.E+00 VARIABLE VALUE REDUCED COST DMINUS1 0. 1. X1 3. 0. X2 3. 0. DPLUS1 0. 0. DPLUS2 3. 0. DMINUS2 0. 0. DPLUS3 0. 0. DMINUS3 4. 0. DPLUS4 0. 0. DMINUS4 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. NO. ITERATIONS= 5 目標(biāo)函數(shù)的最優(yōu)值為0，即第一級(jí)偏差為0。 求第二級(jí)偏差，列出LIN

12、GO程序如下： 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 計(jì)算結(jié)果如下： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 0.E+00 VARIABLE VALUE REDUCED COST DPL

13、US2 0. 1. DMINUS2 0. 1. X1 1. 0. X2 3. 0. DPLUS1 0. 0. DMINUS1 0. 0. DPLUS3 0. 0. DMINUS3 8. 0. DPLUS4 3. 0. DMINUS4 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. 7) 0. 0. NO. ITERATIONS= 2 目標(biāo)函數(shù)最優(yōu)值還是0，即二級(jí)偏差仍為0。 求第三級(jí)偏差，列出LINGO程序： MIN 3DPLUS3 + 3DMINUS3 + DPLUS4 S

14、UBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 DPLUS2 + DMINUS2 = 0 END計(jì)算結(jié)果如下： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 29.00000 VARIABLE VALUE REDUCED COST DPLUS3 0. 6

15、. DMINUS3 8. 0. DPLUS4 5. 0. X1 2. 0. X2 4. 0. DPLUS1 100. 0. DMINUS1 0. 0. DPLUS2 0. 0. DMINUS2 0. 11. DMINUS4 0. 1. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 5. 5) 0. -3. 6) 0. 1. 7) 0. 0. 8) 0. 5. NO. ITERATIONS= 2目標(biāo)函數(shù)最優(yōu)值為29，即第三級(jí)偏差為29。 分析結(jié)果知，X1為2，X2為4，DPLUS1為100，因此目標(biāo)規(guī)劃的最優(yōu)解為（2，4），最優(yōu)

16、利潤(rùn)為1600。例1.5按照算法1.1編寫求解例1.3的LINGO程序，給出相應(yīng)的計(jì)算結(jié)果，并將計(jì)算結(jié)果與LINDO軟件的計(jì)算結(jié)果相比較。 按照算法1.1編寫LINGO程序： sets: Level/1.3/: P, z, Goal; Variable/1.2/: x; H_Con_Num/1.1/: b; S_Con_Num/1.4/: g, dplus, dminus; H_Cons(H_Con_Num, Variable): A; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endsetsdat

17、a: P= ? ? ?; Goal = ? ? 0; b = 12; g= 1500 0 16 15; A = 2 2; C = 200 300 2 -1 4 0 0 5; Wplus = 0 0 0 0 0 1 0 0 0 0 3 1; Wminus = 1 0 0 0 0 1 0 0 0 0 3 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminus(j);for(H_Con_Num(i): su

18、m(Variable(j): A(i,j) * x(j) = b(i);for(S_Con_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););END根據(jù)此程序可進(jìn)行調(diào)試。1.3 目標(biāo)規(guī)劃模型的實(shí)例前面介紹了目標(biāo)規(guī)劃的求解方法，這里再介紹幾個(gè)目標(biāo)規(guī)劃模型的實(shí)例，幫助我們進(jìn)一步了解目標(biāo)規(guī)劃模型的建立和求解過(guò)程。由于選用LINGO軟件求解目標(biāo)規(guī)劃較為方便，因此在下面的求解過(guò)程中，所用的軟件均是LIN

19、GO軟件。如果讀者對(duì)LINDO軟件的編程方法感興趣，可按照1.2節(jié)介紹的方法編寫LINDO程序。例1.6 某音像商店有5名全職售貨員和4名兼職售貨員，全職售貨員每月工作160h，兼職售貨員每月工作80h,根據(jù)過(guò)去的工作記錄，全職售貨員每小時(shí)銷售CD25張，平均每小時(shí)工資15元，加班工資每小時(shí)22.5員，兼職售貨員每小時(shí)銷售CD10張，平均工資每小時(shí)10元，加班工資每小時(shí)10元，現(xiàn)在預(yù)測(cè)下月CD銷售量為27500張，商店每周開門營(yíng)業(yè)6天，所以可能要加班，每出售一張CD贏利1.5元。商店經(jīng)理認(rèn)為，保持穩(wěn)定的就業(yè)水平加上必要的加班，比不加班但就業(yè)水平不穩(wěn)定要好，但全職收獲員，如果加班過(guò)多，就會(huì)因?yàn)槠?/p>

20、勞過(guò)度而造成效率下降，因而不允許每月加班超過(guò)100h，建立相關(guān)的目標(biāo)規(guī)劃模型，并運(yùn)用LINGO軟件求解。解：首先，建立目標(biāo)規(guī)劃的優(yōu)先級(jí)。：下月的CD銷售量達(dá)到27500張。：限制全職售貨員加班時(shí)間不超過(guò)100h。：保持全體售貨員充分就業(yè)，因?yàn)槌浞止ぷ魇橇己脛谫Y關(guān)系的重要因素，但對(duì)全職售貨員要比兼職售貨員優(yōu)先考慮。：盡量減少加班時(shí)間，但對(duì)兩種售貨員區(qū)別對(duì)待，優(yōu)先權(quán)因子由他們對(duì)利潤(rùn)的貢獻(xiàn)而定。第二，建立目標(biāo)約束。（1） 銷售目標(biāo)約束。設(shè)：全體全職售貨員下月的工作時(shí)間；：全體兼職售貨員下月的工作時(shí)間；：大不到銷售目標(biāo)的偏差；：超過(guò)銷售目標(biāo)的偏差。希望下月的銷售量超過(guò)27500張CD片，因此銷售目標(biāo)為

21、 （25）（2） 正常工作時(shí)間約束。設(shè)：全體全職售貨員下月的停工時(shí)間；：全體全職售貨員下月的加班時(shí)間；：全體兼職售貨員下月的停工時(shí)間；：全體兼職售貨員下月的加班時(shí)間。由于希望保持全體售貨員充分就業(yè)，同時(shí)加倍優(yōu)先考慮全職售貨員，因此工作目標(biāo)約束為 （26）（3） 加班時(shí)間的限制。設(shè) ：全體全職售貨員下月加班不足100h的偏差； ：全體全職售貨員下月加班超過(guò)100h的偏差限制全體售貨員加班時(shí)間不超過(guò)100h，將加班約束看成正常班的約束，不同的是右端加上100h，因此加班目標(biāo)約束為 （27）另外，全職售貨員加班1h，商店得到的利潤(rùn)為15元（25*1.5-22.5=15），兼職售貨員加班1h，商店得到

22、的利潤(rùn)為5元，（10*1.5-10=5），因此加班1h全職售貨員獲得的利潤(rùn)是兼職售貨員的3倍，故權(quán)因子之比為 ，所以，另一個(gè)加班目標(biāo)約束為 （28）第三，按目標(biāo)的優(yōu)先級(jí)，寫出相應(yīng)的目標(biāo)規(guī)劃模型： （29）S.T （30） （31） （32） （33） （34）第四，寫出LINGO程序： sets: Level/1.4/: P, z, Goal; Variable/1.2/: x; S_Con_Num/1.4/: g, dplus, dminus; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endse

23、tsdata: P= ? ? ? ?; Goal = ?, ?, ?, 0; g= 27500 800 320 900; C = 25 10 1 0 0 1 1 0; Wplus = 0 0 0 0 0 0 0 1 0 0 0 0 0 1 3 0; Wminus = 1 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminus(j);for(S_C

24、on_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););END 然后進(jìn)行調(diào)試。最后得出，全職售貨員總工作時(shí)間為900h（加班100h）,兼職售貨員總工作時(shí)間500h（加班時(shí)間180h），下月共銷售CD盤27500張，商店獲得利潤(rùn) （元）。例 1.7 某計(jì)算機(jī)公司生產(chǎn)三種型號(hào)的筆記本電腦A，B，C。這3種筆記本電腦需要在復(fù)雜的裝配線上生產(chǎn)，生產(chǎn)一臺(tái)A，B，C型號(hào)的筆記本電腦分別需要5，8，12（

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

26、應(yīng)的目標(biāo)規(guī)劃模型，并用LINGO軟件求解。解 建立目標(biāo)約束：（1）裝配線正常生產(chǎn) 設(shè)生產(chǎn)A，B，C型號(hào)的電腦為(臺(tái))，為裝配線正常生產(chǎn)時(shí)間未利用數(shù)，為裝配線加班時(shí)間，希望裝配線正常生產(chǎn)，避免開工不足，因此裝配線目標(biāo)約束為 （35）（2）銷售目標(biāo)優(yōu)先滿足老客戶的需求。并根據(jù)三種電腦的純利潤(rùn)分配不同的權(quán)因子，S，B，C三種型號(hào)的電腦，每小時(shí)的利潤(rùn)是1000/5，1440/8，2520/12，因此，根據(jù)老客戶的銷售目標(biāo)建立約束。再考慮一般銷售，類似上面的討論，可得到約束。（3） 加班限制 首先是限制裝配線加班時(shí)間，不允許超過(guò)200h。再次裝配線的加班時(shí)間盡可能少。寫出目標(biāo)規(guī)劃的數(shù)學(xué)模型。參考LING

27、O程序：sets: Level/1.5/: P, z, Goal; Variable/1.3/: x; S_Con_Num/1.8/: g, dplus, dminus; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endsetsdata: P= ? ? ? ? ?; Goal = ?, ?, ?, ?, 0; g= 1700 50 50 80 100 120 100 1900; C = 5 8 12 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 5 8 12; Wplus

28、= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; Wminus = 1 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminu

29、s(j);for(S_Con_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););經(jīng)5次計(jì)算得到：=100，。裝配線生產(chǎn)時(shí)間為1900h，滿足裝配線加班不超過(guò)200h，能夠滿足老客戶的需求，但未能達(dá)到銷售目標(biāo)。銷售總利潤(rùn)為（元）。例1.8 已知3個(gè)工廠生產(chǎn)的產(chǎn)品供應(yīng)給4個(gè)客戶，各工廠生產(chǎn)量，用戶需求量及從工廠到用戶的單位產(chǎn)品的運(yùn)輸費(fèi)用如表1-3所示。由于總生產(chǎn)量小于小于總需求量，上級(jí)部門研究后，

30、制定了調(diào)配方案的8項(xiàng)指標(biāo)，并規(guī)定了重要性的秩序。表1.3 工廠生產(chǎn)量，用戶需求量及運(yùn)費(fèi)單價(jià)用戶1234生產(chǎn)量工廠15267300工廠23546200工廠34523200需求量200100450250第一目標(biāo)：用戶4為重要部門，需求量必須全部滿足；第二目標(biāo)：供應(yīng)用戶1的產(chǎn)品中，工廠3的產(chǎn)品不少于100個(gè)單位；第三目標(biāo)：每個(gè)用戶的滿足率不低于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ī)劃模

31、型，并用LINGO求解。解： 求解原運(yùn)輸問(wèn)題：由于總生產(chǎn)量小于總需求量，虛設(shè)工廠4，生產(chǎn)量為100個(gè)單位，到各個(gè)用戶間的運(yùn)費(fèi)單價(jià)為0.利用第七章介紹的運(yùn)輸問(wèn)題的求解方法，用LINGO軟件求解，得到總運(yùn)費(fèi)是2950元，運(yùn)輸方案如表1-4所示：表1-4 作為運(yùn)輸問(wèn)題的最優(yōu)方案用戶1234生產(chǎn)量工廠1100200300工廠2200200工廠3250150400工廠4100100需求量200100450250可看出上述方案中，第一個(gè)目標(biāo)就不能滿足，用戶4的需求量也得不到滿足，下面按照目標(biāo)性的等級(jí)列出目標(biāo)規(guī)劃的約束和目標(biāo)函數(shù)。 設(shè)為工廠i調(diào)配給用戶j的運(yùn)量。 建模過(guò)程略。參考程序：sets: Level

32、/1.8/: P, z, Goal; S_Con_Num/1.13/: dplus, dminus; Plant /1.3/: a; Customer /1.4/: b; Routes(Plant, Customer): c, x;endsetsdata: P= ? ? ? ? ? ? ? ?; Goal = ? ? ? ? ? ? ? 0; a = 300 200 400; b = 200 100 450 250; c = 5 2 6 7 3 5 4 6 4 5 2 3;enddatamin=sum(Level: P * z);z(1) = dminus(9);z(2) = dminus(1

33、);z(3) = dminus(2)+dminus(3)+dminus(4)+dminus(5);z(4) = dminus(6)+dminus(7)+dminus(8)+dminus(9);z(5) = dplus(10);z(6) = dplus(11);z(7) = dminus(12)+dplus(12);z(8) = dplus(13);for(Plant(i): sum(Customer(j): x(i,j) 0,vi(i=1,2,m)表示第j個(gè)決策單元對(duì)第r種輸出的參出量，并且滿足yrj0，vi(i=1,2,m)表示第i種輸入的一種度量（或稱為權(quán)），ur（r=1，2，s）表示第r

34、種輸出的一種度量（或稱為權(quán)）。將表1-7中的元素寫成向量的形式，如表1-8所示。表1-8 決策單元的矩陣形式 1 2 j n vX1 x2 xj xnY1 y2 yj yn u在表1-8中，Xj，Yj（j=1，2，n）分別為決策單元j的輸入，輸出向量，v，u分別為輸入，輸出的權(quán)重。1.4.2 模型1、引例考查某種燃燒置的燃燒比。設(shè)YR是給定X個(gè)單位煤產(chǎn)生熱量的理想值，設(shè)是某種燃燒裝置燃燒X個(gè)單位煤所產(chǎn)生熱量的實(shí)際值，則燃燒裝置的燃燒比（相對(duì)評(píng)價(jià)指標(biāo)數(shù)）為，為.（50）顯然有，YR即01?，F(xiàn)在用模型的方法推導(dǎo)出式（50）?？紤]優(yōu)化問(wèn)題Max ,（51）s.t （52）（53）u0，v0，.（54）其中u，v是權(quán)重，其目的是使約束（52）（53）成立。設(shè)（，）是優(yōu)化問(wèn)題（51）（54）的最優(yōu)解，由于YR，以及，得到。因此，優(yōu)化問(wèn)題（51）（54）的最優(yōu)解（，）滿足，其最優(yōu)目標(biāo)值為，即燃燒裝置的燃燒評(píng)價(jià)指數(shù)。2、模型類似上面的討論，對(duì)于表8-8所給出的數(shù)據(jù)，設(shè)，j=1，2，n，為第j個(gè)決策單元的評(píng)價(jià)指數(shù)?？偪梢赃x擇適當(dāng)?shù)臋?quán)系數(shù)u，v，使得，j=1，2，n，第j個(gè)決策單元的評(píng)價(jià)指數(shù)的意義是：在權(quán)系數(shù)