優(yōu)化建模與LINDOLINGO軟件第8章目標(biāo)規(guī)劃模型要求

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ī)劃模型的實(shí)例8.4 數(shù)據(jù)包絡(luò)分析 8.1 線性規(guī)劃與目標(biāo)規(guī)劃線性規(guī)劃通?？紤]一個(gè)目標(biāo)函數(shù)(問題簡(jiǎn)單)目標(biāo)規(guī)劃考慮多個(gè)目標(biāo)函數(shù)(問題復(fù)雜)線性規(guī)劃目標(biāo)規(guī)劃發(fā)展演變某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，需要用到A,B,C三種設(shè)備，關(guān)于產(chǎn)品的盈利與使用設(shè)備的工時(shí)及限制如下表所示。 例 生產(chǎn)安排問題 問該企業(yè)應(yīng)如何安排生產(chǎn)，使得在計(jì)劃期內(nèi)總利潤(rùn)最大？ 2. 目標(biāo)規(guī)劃建模在上例中，企業(yè)的經(jīng)營(yíng)目標(biāo)不僅要考慮利潤(rùn)，還需要考慮多個(gè)方面，因此增加下列因素(目標(biāo))： 力求使利潤(rùn)指標(biāo)不低于15

2、00元 考慮到市場(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倍從上述問題可以看出，僅用線性規(guī)劃方法是不夠的，需要借助于目標(biāo)規(guī)劃的方法進(jìn)行建模求解某汽車銷售公司委托一個(gè)廣告公司在電視上為其做廣告，汽車銷售公司提出三個(gè)目標(biāo)： 例 汽車廣告費(fèi)問題 廣告公司必須決定購(gòu)買兩種類型的電視廣告展播各多少分鐘？第一個(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)高收入的女性

3、公民(記為HIW)看到這個(gè)廣告廣告公司可以從電視臺(tái)購(gòu)買兩種類型的廣告展播：足球賽中插播廣告和電視系列劇插播廣告。廣告公司最多花費(fèi)60萬(wàn)元的電視廣告費(fèi)。每一類廣告展播每一分鐘的花費(fèi)及潛在的觀眾人數(shù)如下表所示 4. 線性規(guī)劃建模局限性 線性規(guī)劃要求所有求解的問題必須滿足全部的約束，而實(shí)際問題中并非所有約束都需要嚴(yán)格的滿足； 線性規(guī)劃只能處理單目標(biāo)的優(yōu)化問題，而對(duì)一些次目標(biāo)只能轉(zhuǎn)化為約束處理。但在實(shí)際問題中，目標(biāo)和約束好似可以相互轉(zhuǎn)化的，處理時(shí)不一定要嚴(yán)格區(qū)分； 線性規(guī)劃在處理問題時(shí)，將各個(gè)約束(也可看作目標(biāo))的地位看成同等重要，而在實(shí)際問題中，各個(gè)目標(biāo)的重要性即有層次上的差別，也有在同一層次上不同

4、權(quán)重的差別 線性規(guī)劃尋求最優(yōu)解，而許多實(shí)際問題只需要找到滿意解就可以了。 8. 2 目標(biāo)規(guī)劃的數(shù)學(xué)模型為了克服線性規(guī)劃的局限性,目標(biāo)規(guī)劃采用如下手段：1. 設(shè)置偏差變量;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í)際值超過目標(biāo)值時(shí)，有當(dāng)實(shí)際值未達(dá)到目標(biāo)值時(shí)，有當(dāng)實(shí)際值與目標(biāo)值一致時(shí)，有 2. 統(tǒng)一處理目標(biāo)與約束在目標(biāo)規(guī)劃中，約束可分兩類，一類是對(duì)資

5、源有嚴(yán)格限制的，稱為剛性約束(Hard Constraint)；例如在用目標(biāo)規(guī)劃求解例中設(shè)備A禁止超時(shí)使用，則有剛性約束另一類是可以不嚴(yán)格限制的，連同原線性規(guī)劃的目標(biāo),構(gòu)成柔性約束(Soft Constraint).例如在求解例中，我們希望利潤(rùn)不低于1500元，則目標(biāo)可表示為求解例中甲、乙兩種產(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)

6、先級(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ī)定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)重要性的差別。解因?yàn)槊總€(gè)單目標(biāo)問題都是一個(gè)線性規(guī)劃問題，例8.3目標(biāo)規(guī)劃模型編寫單個(gè)的線性規(guī)劃求解程序。求第一級(jí)目標(biāo)企業(yè)利潤(rùn)最大，列出LINDO程序。 例 用算法求解例8. 3 MIN DMINUS1 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 -

7、DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 END求解結(jié)果可見程序演示目標(biāo)解因求出的目標(biāo)函數(shù)的最優(yōu)值為，即第一級(jí)偏差為.再求第二級(jí)目標(biāo)，列出其LINDO程序。 例 用算法求解例8. 3 MIN DPLUS2 + DMINUS2 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 =

8、0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 END求解結(jié)果可見程序演示修改的目標(biāo)增加的約束解因求出的目標(biāo)函數(shù)的最優(yōu)值仍為，即第二級(jí)偏差仍為. 繼續(xù)求第三級(jí)目標(biāo)，列出其LINDO程序。 例 用算法求解例8. 3 MIN 3DPLUS3 + 3DMINUS3+ DPLUS4 SUBJECT TO 2X1 + 2X2 0; yrj (r=1,2,.,s, j=1,2,., n)表示第j個(gè)決策單元對(duì)第r種輸出的產(chǎn)出量，并且滿足yrj0; vi(i=1,2,.,m)表示第i種輸入的一種度量(或稱為權(quán)); u

9、r(r=1,2,., s)表示第r種輸出的的一種度量(或稱為權(quán)). 將上表中的元素寫成向量形式，如下表所示. 數(shù)據(jù)包絡(luò)分析的基本概念X1X2.Xj.Xn v 1 2 . j . n uY1Y2.Yj.Yn在上表中, Xj, Yj(j=1,2,.,n)分別為決策單元j的輸入、輸出向量，v, u分別為輸入、輸出權(quán)重.對(duì)于前面講的向量表所給出的數(shù)據(jù)，設(shè) C2R模型為第j個(gè)決策單元的評(píng)價(jià)指數(shù)，總可以選擇適當(dāng)?shù)臋?quán)系數(shù)u,v, 使得第j個(gè)決策單元的評(píng)價(jià)指數(shù)hj的意義是：在權(quán)系數(shù)u,v下，投入為vTXj， 產(chǎn)出為uTYj的投入產(chǎn)出比。討論：我們需要考慮某個(gè)決策單元j0的效率評(píng)價(jià)指數(shù)hj為目標(biāo)，在約束hj 1的最大值，即分式線性規(guī)劃 C2R模型稱上述模型為C2R模型為了便于計(jì)算將分式線性規(guī)劃轉(zhuǎn)化成線性規(guī)劃模型 數(shù)據(jù)包絡(luò)分析的求解定義1: 若該模型中則稱決策單元 j0 是弱DEA有效的.定義2: 若該模型中存在最優(yōu)解并且, 有 則稱決策單元 j0 是弱DEA有效的.例8.10 (繼例8.9)運(yùn)用C2R模型求解例8.9.解 按照C2R模型寫出相應(yīng)的LINGO程序，程序名：exam0810.lg4. C2R模型的求解運(yùn)行程序時(shí)，P的值分別輸入(1,0,0,0,0,0), (