優化建模與LINDO/LINGO軟件第8章目標規劃模型內容提要8.1線性規劃與目標規劃8.2目標規劃的數學模型8.3目標規劃模型的實例8.4數據包絡分析8.1線性規劃與目標規劃線性規劃通常考慮一個目標函數(問題簡單)目標規劃考慮多個目標函數(問題復雜)線性規劃目標規劃發展演變某企業生產甲、乙兩種產品，需要用到A,B,C三種設備，關于產品的盈利與使用設備的工時及限制如下表所示。

例8.1

生產安排問題

問該企業應如何安排生產，使得在計劃期內總利潤最大？1.線性規劃建模該例8.1是一個線性規劃問題，直接考慮它的線性規劃模型設甲、乙產品的產量分別為x1,x2,建立線性規劃模型：用Lindo或Lingo軟件求解,得到最優解2.目標規劃建模在上例8.1中，企業的經營目標不僅要考慮利潤，還需要考慮多個方面，因此增加下列因素(目標)：

力求使利潤指標不低于1500元

考慮到市場需求,甲、乙兩種產品的產量比應盡量保持1:2

設備A為貴重設備，嚴格禁止超時使用

設備C可以適當加班，但要控制；設備B既要求充分利用，又盡可能不加班，在重要性上，設備B是設備C的3倍從上述問題可以看出，僅用線性規劃方法是不夠的，需要借助于目標規劃的方法進行建模求解某汽車銷售公司委托一個廣告公司在電視上為其做廣告，汽車銷售公司提出三個目標：

例8.2

汽車廣告費問題

廣告公司必須決定購買兩種類型的電視廣告展播各多少分鐘？第一個目標，至少有40萬高收入的男性公民(記為HIM)看到這個廣告第二個目標，至少有60萬一般收入的公民(記為LIP)看到這個廣告第三個目標，至少有35萬高收入的女性公民(記為HIW)看到這個廣告廣告公司可以從電視臺購買兩種類型的廣告展播：足球賽中插播廣告和電視系列劇插播廣告。廣告公司最多花費60萬元的電視廣告費。每一類廣告展播每一分鐘的花費及潛在的觀眾人數如下表所示3.嘗試線性規劃建模對于例8.2考慮建立線性規劃模型設x1,x2分別是足球賽和電視系列劇中插播的分鐘數，按照要求，可以列出相應的線性規劃模型用Lindo或Lingo軟件求解,會發現該問題不可行。4.線性規劃建模局限性

線性規劃要求所有求解的問題必須滿足全部的約束，而實際問題中并非所有約束都需要嚴格的滿足；

線性規劃只能處理單目標的優化問題，而對一些次目標只能轉化為約束處理。但在實際問題中，目標和約束好似可以相互轉化的，處理時不一定要嚴格區分；

線性規劃在處理問題時，將各個約束(也可看作目標)的地位看成同等重要，而在實際問題中，各個目標的重要性即有層次上的差別，也有在同一層次上不同權重的差別

線性規劃尋求最優解，而許多實際問題只需要找到滿意解就可以了。8.2目標規劃的數學模型為了克服線性規劃的局限性,目標規劃采用如下手段：1.

設置偏差變量;2.

統一處理目標與約束;3.

目標的優先級與權系數。目標規劃的基本概念

1.

設置偏差變量用偏差變量(Deviationalvariables)來表示實際值與目標值之間的差異，令

----超出目標的差值，稱為正偏差變量

----未達到目標的差值，稱為負偏差變量其中與至少有一個為0約定如下：當實際值超過目標值時，有當實際值未達到目標值時，有當實際值與目標值一致時，有

2.

統一處理目標與約束在目標規劃中，約束可分兩類，一類是對資源有嚴格限制的，稱為剛性約束(HardConstraint)；例如在用目標規劃求解例8.1中設備A禁止超時使用，則有剛性約束另一類是可以不嚴格限制的，連同原線性規劃的目標,構成柔性約束(SoftConstraint).例如在求解例8.1中，我們希望利潤不低于1500元，則目標可表示為求解例8.1中甲、乙兩種產品的產量盡量保持1:2的比例，則目標可表示為設備C可以適當加班，但要控制，則目標可表示為設備B既要求充分利用，又盡可能不加班，則目標可表示為從上面的分析可以看到：如果希望不等式保持大于等于，則極小化負偏差；如果希望不等式保持小于等于，則極小化正偏差；如果希望保持等式，則同時極小化正、負偏差．3.目標的優先級與權系數在目標規劃模型中，目標的優先分為兩個層次，第一個層次是目標分成不同的優先級，在計算目標規劃時，必須先優化高優先級的目標，然后再優化低優先級的目標。通常以P1,P2,...表示不同的因子,并規定Pk>>Pk+1，第二個層次是目標處于同一優先級，但兩個目標的權重不一樣，因此兩目標同時優化，用權系數的大小來表示目標重要性的差別。解在例８.1中設備A是剛性約束，其于是柔性約束．首先，最重要的指標是企業的利潤，將它的優先級列為第一級；其次，甲、乙兩種產品的產量保持1:2的比例，列為第二級；再次，設備

B和C的工作時間要有所控制，列為第三級，設備B的重要性是設備C的三倍，因此它們的權重不一樣。由此可以得到相應的目標規劃模型。

目標規劃模型的建立例8.3

用目標規劃方法求解例8.1

目標規劃的一般模型目標規劃模型的一般數學表達式為：

求解目標規劃的序貫式算法其算法是根據優先級的先后次序，將目標規劃問題分解成一系列的單目標規劃問題，然后再依次求解。算法8.1

對于k=1,2,…,q,求解單目標問題解因為每個單目標問題都是一個線性規劃問題，因此可以采用LINDO軟件進行求解。按照算法8.1和例8.3目標規劃模型編寫單個的線性規劃求解程序。求第一級目標企業利潤最大，列出LINDO程序。程序名：exam0804a.ltx

例8.4

用算法8.1求解例8.3MINDMINUS1SUBJECTTO2X1+2X2<=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15END求解結果可見程序演示目標解因求出的目標函數的最優值為０，即第一級偏差為０.再求第二級目標，列出其LINDO程序。程序名：exam0804b.ltx

例8.4

用算法8.1求解例8.3MINDPLUS2+DMINUS2SUBJECTTO

2X1+2X2

<=12200X1+300X2-DPLUS1+DMINUS1=1500

2X1-

X2-DPLUS2+DMINUS2=0

4X1

-DPLUS3+DMINUS3=16

5X2-DPLUS4+DMINUS4=15

DMINUS1=0END求解結果可見程序演示修改的目標增加的約束解因求出的目標函數的最優值仍為０，即第二級偏差仍為０.繼續求第三級目標，列出其LINDO程序。程序名：exam0804c.ltx

例8.4

用算法8.1求解例8.3MIN3DPLUS3+3DMINUS3+DPLUS4SUBJECTTO

2X1+

2X2

<=12200X1+300X2-DPLUS1+DMINUS1=1500

2X1-

X2-DPLUS2+DMINUS2=0

4X1

-DPLUS3+DMINUS3=16

5X2-DPLUS4+DMINUS4=15

DMINUS1=0

DPLUS2+DMINUS2=0END求解結果可見程序演示求出的目標函數的最優值為29,即第三級偏差為29,分析結果,x1為2,x2為4,DPLUS1為100,因此目標規劃的最優解為x

*=(2,4),最優利潤為1600.修改的目標增加的約束解按照算法8.1和例8.3目標規劃模型編寫LINGO求解程序，列出其LINGO程序,程序名：exam0805.lg4

例8.5(繼例8.4)用算法8.1求解例8.3的LINGO程序程序運行說明，分三次求解：在做第一級目標計算時，P(1),P(2)和P(3)分別輸入1,0和0，Goal(1)和Goal(2)輸入兩個較大的數，表示這兩項約束不起作用；在做第二級目標計算時，P(1),P(2)和P(3)分別輸入0,1和0，由于第一級的偏差為0，因此Goal(1)為0，Goal(2)輸入一個較大的數；在做第三級計算時，P(1),P(2)和P(3)分別輸入0,0和1，由于第一級、第二級的偏差為0，因此Goal(1)和Goal(2)的輸入值也為0。結果可以參見程序演示！??！

由于在例8.4中雖然給出了目標規劃問題的最優解,但需要連續編幾個LINDO程序,在使用時不方便,下面使用LINGO軟件,編寫一個通用程序。8.3目標規劃模型的實例前面介紹了目標規劃的求解方法，接著再介紹幾個目標規劃模型的實例。某音像商店有5名全職售貨員和4名兼職售貨員。全職售貨員每月工作160小時，兼職售貨員每月工作80小時。根據過去的工作記錄，全職售貨員每小時銷售CD25張，平均每小時工資15元，加班工資每小時22.5元。兼職售貨員每小時銷售CD10張，平均每小時工資10元，加班工資每小時10元。現在預測下月CD銷售量為27500張，商店每周開門營業6天，所以可能要加班。另每出售一張CD盈利1.5元。

例8.6該商店經理認為，保持穩定的就業水平加上必要的加班，比不加班但就業水平不穩定要好。但全職售貨員如果加班過多，就會因疲勞過度而造成效率下降，因此不允許每月加班超過100小時。建立相應的目標規劃模型，并運用LINGO軟件進行求解。解首先建立目標約束的優先級。P1：下月的CD銷售量達到27500張；P2：

限制全職售貨員加班時間不超過100小時；P3：

保持全體售貨員充分就業，因為充分工作是良

好勞資關系的重要因素，但對全職售貨員要比

兼職售貨員加倍優先考慮；P4：

盡量減少加班時間，但對兩種售貨員區別對

待，優先權因子由他們對利潤的貢獻而定。

例8.6

例8.6第二，建立目標約束。(1)

銷售目標約束。設

x1

：全體全職售貨員下月的工作時間；

x2

：全體兼職售貨員下月的工作時間；：達不到銷售目標的偏差；：超過銷售目標的偏差。

希望下月的銷售量超過27500張CD片，因此銷售目標為

例8.6第二，建立目標約束。(2)

正常工作時間約束，設：全體全職售貨員下月的停工時間；：全體全職售貨員下月的加班時間；：全體兼職售貨員下月的停工時間；：全體兼職售貨員下月的加班時間。

由于希望保持全體售貨員充分就業，同時加倍優先考慮全職售貨員,因此工作目標約束為

例8.6第二，建立目標約束。(3)

正常工作時間約束，設：全體全職售貨員下月加班不足100小時的偏差；：全體全職售貨員下月加班超過100小時的偏差。

限制全職售貨員加班時間不超過100小時，將加班約束看成正常上班約束，不同的是右端加上100小時，因此加班目標約束為

例8.6第二，建立目標約束。接上(3)

另外，全職售貨員加班1小時，商店得到的利潤為15元(25*1.5-22.5=15)，兼職售貨員加班1小時，商店得到的利潤為5元(10*1.5-10=5)，因此加班1小時全職售貨員獲得的利潤是兼職售貨員的3倍，故權因子之比為

所以，另一個加班目標約束為：

例8.6

第三，按目標的優先級，寫出相應的目標規劃模型：

第四，寫出相應的LINGO程序，程序名：exam0806.lg4.程序運行說明，分四次求解：在做第一級目標計算時，P(1),P(2),P(3)和P(4)分別輸入1,0,0和0，Goal(1),Goal(2)和Goal(3)輸入兩個較大的數，表示這兩項約束不起作用；在做第二級目標計算時，P(1),P(2),P(3)和P(4)分別輸入0,1,0和0，由于第一級的偏差為0，因此Goal(1)為0,Goal(2)和Goal(3)輸入一個較大的數；在做第三級計算時，P(1),P(2),P(3)和P(4)分別輸入0,0,1和0，由于第一級,第二級的偏差為0，因此Goal(1)和Goal(2)的輸入值也為0，Goal(3)輸入一個較大的數；在做第四級計算時，P(1),P(2),P(3)和P(4)分別輸入0,0,0和1，由于第一級,第二級和第三級的偏差為0,因此Goal(1),Goal(2)和Goal(3)輸入值也為0；全職售貨員總工作時間為900小時(加班100小時)，兼職售貨員總工作時間500小時(加班180小時)，下月共銷售CD27500張，商店共獲得利潤

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

例8.7

例8.7公司經理考慮以下目標：第一目標：充分利用正常的生產能力，避免開工不足；第二目標：優先滿足老客戶的需求，A,B,C三種型號的電腦50,50,80臺，同時根據三種電腦的純利潤分配不同的權因子；第三目標：限制裝配線加班時間，不允許超過200小時；第四目標：滿足各種型號電腦的銷售目標,A,B,C型號分別為100,120,100臺,再根據三種電腦的純利潤分配不同的權因子；第五目標：裝配線的加班時間盡可能少。請列出相應的目標規劃模型,并用LINGO軟件求解。

例8.7解建立目標約束。(1)裝配線正常生產設生產A,B,C型號的電腦為x1,x2,x3臺，裝配線正常生產時間未利用數，裝配線加班時間，希望裝配線正常生產,避免開工不足,因此裝配線約束目標為

例8.7(2)

銷售目標優先滿足老客戶的需求，并根據三種電腦的純利潤分配不同的權因子，A,B,C三種型號的電腦每小時的利潤是因此,老客戶的銷售目標約束為

例8.7(2)

銷售目標

(接上)

再考慮一般銷售，類似上面的討論，得到

例8.7(3)

加班限制首先是限制裝配線加班時間，不允許超過200小時，因此得到其次裝配線的加班時間盡可能少，即例8.7

寫出相應的目標規劃模型：

寫出相應的LINGO程序，程序名：exam0807.lg4.程序運行說明：經5次計算得到x1=100,x2=55,x3=80。裝配線生產時間為1900小時，滿足裝配線加班不超過200小時的要求。能夠滿足老客戶的需求，但未能達到銷售目標。銷售總利潤為

100x1000+55x1440+80x2520=380800(元)

其結果可以參見程序演示！??！

例8.8已知三個工廠生產的產品供應給四個用戶，各工廠生產量、用戶需求量及從各工廠到用戶的單位產品的運輸費用如表所示。由于總生產量小于總需求量,上級部門經研究后，制定了調配方案的8項指標，并規定重要性的次序是:

例8.8第一目標：用戶4為重要部門,需求量必須全部滿足；第二目標：供應用戶1的產品中，工廠3的產品不少于100個單位；第三目標：每個用戶的滿足率不低于80%；第四目標：應盡量滿足各用戶的需求；第五目標：新方案的總運費不超過原運輸問題的調度方案的10%；第六目標：因道路限制，工廠2到用戶4的路線應盡量避免運輸任務；第七目標：用戶1和用戶3的滿足率應盡量保持平衡；第八目標：力求減少總運費。請列出相應的目標規劃模型，并用LINGO軟件求解。

例8.8解求解原運輸問題。由于總生產量小于總需求量,虛設工廠4,生產量為100個單位,到各個用戶間的運輸單價為0,利用第7章介紹的運輸問題的求解方法,用LINGO軟件求解,得到總運費是2950元,運輸方案如表所示.

例8.8從上表可以看出，上述方案中，第一個目標就不滿足，用戶4的需求量得不到滿足。下面按照目標的重要性的等級列出目標規劃的約束和目標函數。設xij

為工廠i調配給用戶j的運量.(1)供應約束應嚴格滿足,即(2)供應用戶1的產品中,工廠3的產品不少于100個單位,即

例8.8(3)需求約束.

各用戶的滿足率不低于

80%,即

需求應盡量

滿足各用戶

的需求，即新方案的總運費不超過原運方案的10%（原運輸方案的運費為2950元），即(5)工廠2到用戶4的路線應盡量避免運輸任務,即(6)用戶1和用戶3的滿足率應盡量保持平衡，即(7)力求總運費最少,即

例8.8

寫出相應的目標函數為

寫出相應的LINGO程序，程序名：exam0808.lg4.

程序運行說明

其結果可以參見程序演示！??！經8次計算，得到最終的計算結果，見下表所示?？傔\費為3360元，高于原運費410元，超過原方案10%的上限115元。8.4數據包絡分析1978年A.Charnes,W.W.Cooper和E.Rhodes給出了評價決策單元相對有效性的數據包絡分析方法(DataEnvelopmentAnalysis),即DEA.目前，數據包絡分析(DEA)是評價具有多指標輸入和多指標輸出系統的較為有效的方法。例8.9(多指標評價問題)某市教委需要對六所重點中學進行評價,其相應的指標如下表所示,表中的生均投入和非低收入家庭百分比是輸入指標,生均寫作得分和生均科技得分是輸出指標.請根據這些指標,評價中哪些學校是相對有效的.

相對有效評價問題

例8.9為求解例8.9,先對例表作簡單的分析。學校C的兩項輸出指標都是最高的,達到29.4和317,應該說,學校C是最有效的.但從另一方面說,對它的投入也是最高的,達到108.13和99.6,因此,它的效率也可能是最低的.究竟如何評價這六所學校呢？這還需要仔細地分析.這是一個多指標輸入和多指標輸出的問題,對于這類評價問題,A.Charnes,W.W.Cooper和E.Rhodes建立了評價決策單元相對有效性的C2R模型。假設有n個部門或單位(稱為決策單元,DecisionMakingUnits),這n個單元都具有可比性.每個單元有m個輸入變量和s個輸出變量,如下表所示.

數據包絡分析的基本概念x11x12...x1j...x1nx21x22...x2j...x2n：：：：：：xm1xm2...xmj...xmnv11→v22

→

：：vmm

→12...j...n→1u1→2u2

：：

→susy11y12...y1j...y1ny21y22...y2j...y2n：：：：：：xm1ym2...ymj...ymn在上表中,xij(i=1,2,...,m,j=1,2,...,n)表示第j個決策單元對第i種輸入的投入量，并且滿足xij>0;yrj(r=1,2,...,s,j=1,2,...,n)表示第j個決策單元對第r種輸出的產出量，并且滿足yrj>0;vi(i=1,2,...,m)表示第i種輸入的一種度量(或稱為權);u

r(r=1,2,...,s)表示第r種輸出的的一種度量(或稱