1、優(yōu)化建模與LINDO/LINGO軟件第 8 章目標(biāo)規(guī)劃模型內(nèi)容提要8.1線性規(guī)劃與目標(biāo)規(guī)劃8.2目標(biāo)規(guī)劃的數(shù)學(xué)模型8.3目標(biāo)規(guī)劃模型的實例8.4數(shù)據(jù)包絡(luò)分析 8.1 線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃通?？紤]一個目標(biāo)函數(shù)(問題簡單)目標(biāo)規(guī)劃考慮多個目標(biāo)函數(shù)(問題復(fù)雜)發(fā)展 線性規(guī)劃 目標(biāo)規(guī)劃演變 例8.1 生產(chǎn)安排問題 問該企業(yè)應(yīng)如何安排生產(chǎn)，使得在計劃期內(nèi)總利潤最大？甲乙設(shè)備的生產(chǎn)能力/hA/(h/件) B/(h/件) C/(h/件)贏利/(元/件)221240160515200300某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需要用到A,B,C三種設(shè)備，關(guān)于產(chǎn)品的盈利與使用設(shè)備的工時及限制如下表所示。 1. 線性規(guī)

2、劃建模該例8.1是一個線性規(guī)劃問題，直接考慮它的線性規(guī)劃模型設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1, x2,建立線性規(guī)劃模型：Maxz = 200 x1 + 300 x2 ;s. t.2x1 + 2x2 12 ,4x1 16,5x2 15,x1, x2 0.用Lindo或Lingo軟件求解,得到最優(yōu)解x= 3, x= 3, z* =1500.12 2. 目標(biāo)規(guī)劃建模在上例8.1中，企業(yè)的經(jīng)營目標(biāo)不僅要考慮利潤，還需要考慮多個方面，因此增加下列因素(目標(biāo))： 力求使利潤指標(biāo)不低于1500元 考慮到市場需求,甲、乙兩種產(chǎn)品的產(chǎn)量比應(yīng)盡量保持1:2 設(shè)備A為貴重設(shè)備，嚴(yán)格禁止超時使用 設(shè)備C可以適當(dāng)加班，但要

3、控制；設(shè)備B既要求充分利用，又盡可能不加班，在重要性上，設(shè)備B是設(shè)備C的3倍從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標(biāo)規(guī)劃的方法進(jìn)行建模求解 例8.2 汽車廣告費問題第一個目標(biāo)，至少有40萬高收入的男性公民(記為HIM)看到這個廣告第二個目標(biāo)，至少有60萬一般收入的公民(記為LIP)看到這個廣告第三個目標(biāo)，至少有35萬高收入的女性公民(記為HIW)看到這個廣告 廣告公司必須決定購買兩種類型的電視廣告展播各多少分鐘？HIMLIPHIW費用(萬元/分)足球賽中插播(萬人/分) 系列劇中插播(萬人/分)7105103546廣告公司可以從電視臺購買兩種類型的廣告展播：足球賽中插播廣告

4、和電視系列劇插播廣告。廣告公司最多花費60萬元的電視廣告費。每一類廣告展播每一分鐘的花費及潛在的觀眾人數(shù)如下表所示某汽車銷售公司委托一個廣告公司在電視上為其做廣告，汽車銷售公司提出三個目標(biāo)： 3.嘗試線性規(guī)劃建模對于例8.2考慮建立線性規(guī)劃模型設(shè)x1, x2分別是足球賽和電視系列劇中插播的分鐘數(shù)，按照要求，可以列出相應(yīng)的線性規(guī)劃模型Min0x1 + 0x2 ;10x1 + 6x2 60 ,7 x1 + 3x2 40,10 x1 + 5x2 60,5x1 + 4x2 35,x1 , x2 0.用Lindo或Lingo軟件求解,會發(fā)現(xiàn)該問題不可行。s. t. 4. 線性規(guī)劃建模局限性 線性規(guī)劃要求

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

6、 1. 設(shè)置偏差變量用偏差變量(Deviational variables)來表示實際值與目標(biāo)值之間的差異，令d +d - 超出目標(biāo)的差值，稱為正偏差變d 量+- 未達(dá)到目標(biāo)的差值，稱為負(fù)偏差變量其中d +與 d至- 少有一個為0約定如下： 當(dāng)實際值超過目標(biāo)值時，有d -= 0, d + 0;d +d -= 0, d - 0;= 0, d + = 0. 當(dāng)實際值未達(dá)到目標(biāo)值時，有 當(dāng)實際值與目標(biāo)值一致時，有 2. 統(tǒng)一處理目標(biāo)與約束在目標(biāo)規(guī)劃中，約束可分兩類，一類是對資源有嚴(yán)格限制的，稱為剛性約束(Hard Constraint)；例如在用目標(biāo)規(guī)劃求解例8.1中設(shè)備A禁止超時使用，則有剛性約束

7、2x1 + 2x2 12 .另一類是可以不嚴(yán)格限制的，連同原線性規(guī)劃的目標(biāo),構(gòu)成柔性約束(Soft Constraint).例如在求解例8.1中，我們希望利潤不低于1500元，則目標(biāo)可表示為mind -;200 x1 + 300x2 + d- d= 1500.-+求解例8.1中甲、乙兩種產(chǎn)品的產(chǎn)量盡量保持1:2的比例， 則目標(biāo)可表示為設(shè)備C可以適當(dāng)加班，但要控制， 則目標(biāo)可表示為設(shè)備B既要求充分利用，又盡可能不加班，則目標(biāo)可表示為從上面的分析可以看到：mind +;5x2 + d- d= 15.-+mind + d -;2x1 - x2-+ d- d= 0.mind + + d -;4x1 +

8、 d- d= 16.-+ 如果希望不等式保持大于等于，則極小化負(fù)偏差； 如果希望不等式保持小于等于，則極小化正偏差； 如果希望保持等式，則同時極小化正、負(fù)偏差 3.目標(biāo)的優(yōu)先級與權(quán)系數(shù)在目標(biāo)規(guī)劃模型中，目標(biāo)的優(yōu)先分為兩個層次，第一個 層次是目標(biāo)分成不同的優(yōu)先級，在計算目標(biāo)規(guī)劃時，必 須先優(yōu)化高優(yōu)先級的目標(biāo)，然后再優(yōu)化低優(yōu)先級的目標(biāo)。通常以P1,P2,.表示不同的因子,并規(guī)定PkPk+1，第二個層次是目標(biāo)處于同一優(yōu)先級，但兩個目標(biāo)的權(quán)重不一樣， 因此兩目標(biāo)同時優(yōu)化，用權(quán)系數(shù)的大小來表示目標(biāo)重要 性的差別。 目標(biāo)規(guī)劃模型的建立 例8.3 用目標(biāo)規(guī)劃方法求解例8. 1minz = Pd - + P

9、(d + + d - ) + P (3d + 3d - + 4d + );1222333 12 ,4s. t.2x1 + 2x2200x+ 300x+ d - - d += 1500,1211、2x- x+ d - - d + = 0,12224x+ d - - d + = 16,1335x+ d - - d + = 15,244x , x , d - , d + 0, i = 1,2,3,4.12ii解在例.1中設(shè)備A是剛性約束，其于是柔性約束首先，最重要的指標(biāo)是企業(yè)的利潤，將它的優(yōu)先級列為第一級；其次，甲乙兩種產(chǎn)品的產(chǎn)量保持1:2的比例，列為第二級；再次，設(shè)備 B 和C的工作時間要有所控制

10、，列為第三級，設(shè)備B的重要性是設(shè)備C的三倍，因此它們的權(quán)重不一樣。由此可以得到相應(yīng)的目標(biāo)規(guī)劃模型。 目標(biāo)規(guī)劃的一般模型目標(biāo)規(guī)劃模型的一般數(shù)學(xué)表達(dá)式為：ql-j+ w+ d + );z =minP(wdkkjkjjk =1j =1naij xj j =1n (=, )bi , i = 1,2,L, m,s. t.cx+ d - - d += g, i = 1,2,L, l,ijjiiij =1xj 0,j = 1,2,L, n,d - , d + 0, i = 1,2,L, l,ii 求解目標(biāo)規(guī)劃的序貫式算法其算法是根據(jù)優(yōu)先級的先后次序，將目標(biāo)規(guī)劃問題分解成一系列的單目標(biāo)規(guī)劃問題，然后再依次求解

11、。算法8.1min對于k=1,2,q,求解單目標(biāo)問題l-j+ w+ d + );z=aijj =1n(wdkjkjjj =1nxj (=, )bi , i = 1,2,L, m,s. t. cx+ d - - d += g, i = 1,2,L, l,ijjiiij =1l(wd+ w+ d + ) z* , s = 1,2,L, k -1,-sjjsjjj =1x j 0,j = 1,2,L, n,d - , d + 0, i = 1,2,L, l,ii 例8.4用算法8.1求解例8. 3程序名：exam0804a.ltx目標(biāo)求解結(jié)果可見程序演示MIN1SUBJECT TO2X1 +2X2=

12、 12200X1 + 300X2 - DPLUS1 + DMINUS1 = 15002X1 -X2 - DPLUS2 + DMINUS2 = 04X1- DPLUS3 + DMINUS3 = 165X2 - DPLUS4 + DMINUS4 = 15ENDDMINUS解 因為每個單目標(biāo)問題都是一個線性規(guī)劃問題， 因此可以采用LINDO軟件進(jìn)行求解。按照算法8.1 和例8.3目標(biāo)規(guī)劃模型編寫單個的線性規(guī)劃求解程序。求第一級目標(biāo)企業(yè)利潤最大，列出LINDO程序。 例8.4用算法8.1求解例8. 3修改的目標(biāo)增加的約束MIN SUBJECT TO2X1 +2X2= 12200X1 + 300X2 -

13、 DPLUS1 + DMINUS1 = 15002X1 -X2 - DPLUS2 + DMINUS2 = 04X1- DPLUS3 + DMINUS3 = 165X2 - DPLUS4 + DMINUS4 = 15ENDDMINUS1 = 0求解結(jié)果可見程序演示DPLUS2 + DMINUS2解因求出的目標(biāo)函數(shù)的最優(yōu)值為，即第一級偏差為.再求第二級目標(biāo)，列出其LINDO程序。程序名：exam0804b.ltxDPLUS2 + DMINUS2 = 0END程序演示 例8.4用算法8.1求解例8. 3解因求出的目標(biāo)函數(shù)的最優(yōu)值仍為，即第二級偏差仍為. 繼續(xù)求第三級目標(biāo)，列出其LINDO程序。程序名

14、：exam0804c.ltxMIN修改的目標(biāo)SUBJECT TO2X1 +2X20; yrj (r=1,2,.,s, j=1,2,., n)表示第j個決策單元對第r種輸出的產(chǎn)出量，并且滿足yrj0; vi(i=1,2,.,m)表示第i種輸入的一種度量(或稱為權(quán)); u r(r=1,2,., s)表示第r種輸出的的一種度量(或稱為權(quán)).將上表中的元素寫成向量形式，如下表所示.12.j.nvu在上表中, Xj, Yj(j=1,2,.,n)分別為決策單元j的輸入、輸出向量，v, u分別為輸入、輸出權(quán)重.Y1Y2.Yj.YnX1X2.Xj.XnC2R模型 對于前面講的向量表所給出的數(shù)據(jù)，設(shè)uTYjhj

15、= vT, j = 1,2,L, n,Xjhj 1, j = 1,2,L, n.第j個決策單元的評價指數(shù)hj的意義是：在權(quán)系數(shù)u,v下，投入為vTXj， 產(chǎn)出為uTYj的投入產(chǎn)出比。為第j個決策單元的評價指數(shù)，總可以選擇適當(dāng)?shù)臋?quán)系數(shù)u,v, 使得C2R模型uT YjVp=max 0;vTXj0uT Yj 1, j = 1,2,L, n,s.t.vTXju 0, v 0.稱上述模型為C2R模型討論：我們需要考慮某個決策單元j0的效率評價指數(shù)hj為 目標(biāo)，在約束hj 1的最大值，即分式線性規(guī)劃 數(shù)據(jù)包絡(luò)分析的求解 為了便于計算將分式線性規(guī)劃轉(zhuǎn)化成線性規(guī)劃模型= m T Yj0 ;Vmaxs.t.2CRw Tw T- m T Yj 0, j = 1,2,L, n,XXj= 1,j0w 0, m 0.定義1: 若該模型中VC 2 R= 1, 則稱決策單元 j0 是弱DEA 有效的.定義2: 若該模型中存在最優(yōu)解w 0, m 0,并且, 有VC 2 R= 1,則稱決策單元 j0 是弱DEA有效的.C2R模型的求解運行程序時，P的值分別輸入(1,0,0,0,0,0), (0,1,0,0,0,0), .,(0,0,0,0,0,1)，經(jīng)過6次計算，得到