1、第五章第五章目標(biāo)規(guī)劃目標(biāo)規(guī)劃學(xué)習(xí)目的了解了解目標(biāo)規(guī)劃在多目標(biāo)決策中的作用掌握掌握目標(biāo)規(guī)劃的建模方法和線性目標(biāo)規(guī)劃基本求解方法 了解了解目標(biāo)規(guī)劃在經(jīng)濟(jì)和管理中的基本應(yīng)用方法 線性規(guī)劃只有一個(gè)目標(biāo)函數(shù)，但實(shí)際問題中往往要考慮多個(gè)目標(biāo)，如設(shè)計(jì)一個(gè)新產(chǎn)品的工藝過程，不僅希望利潤大而且希望產(chǎn)量高、消耗低、質(zhì)量好、投入少等，由于同時(shí)考慮多個(gè)目標(biāo)，使這類多目標(biāo)問題要比單目標(biāo)問題復(fù)雜得多 另一方面，這一系列目標(biāo)之間，不僅有主次之分，而且有時(shí)會(huì)互相矛盾，這就給用傳統(tǒng)方法來解決目標(biāo)問題帶來了一定的困難第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型 目標(biāo)規(guī)劃正是為了解決這類多目標(biāo)問題而產(chǎn)生的一種方法。它要求決策者預(yù)先給

2、每個(gè)目標(biāo)定出一個(gè)理想值(期望值) 目標(biāo)規(guī)劃就是在滿足現(xiàn)有的一組約束條件下，求出盡可能接近理想值的解，這個(gè)解稱為滿意解(不稱為最優(yōu)解，因?yàn)橐话闱闆r不，它不是使每個(gè)目標(biāo)都達(dá)到最優(yōu)值的解)第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型與線性規(guī)劃的區(qū)別與線性規(guī)劃的區(qū)別n在線性規(guī)劃中，要求單個(gè)目標(biāo)的優(yōu)化，而目標(biāo)規(guī)劃則強(qiáng)調(diào)使多個(gè)目標(biāo)得到滿意的解答 n線性規(guī)劃中，為得到一個(gè)可行解，必須滿足所有的約束條件。n在目標(biāo)規(guī)劃中，并不認(rèn)為所有約束都是絕對(duì)的，因此對(duì)于非絕對(duì)的約束，目標(biāo)規(guī)劃并不要求絕對(duì)滿足，而是設(shè)法使各目標(biāo)離原先設(shè)定的意向指標(biāo)值的偏差盡可能的小。 第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型例1：某工廠生產(chǎn)甲

3、乙兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需要的原材料及占用設(shè)備臺(tái)時(shí)如下表所示，該工廠每天擁有設(shè)備臺(tái)時(shí)為10，原材料最大供應(yīng)量為11kg/天，已知生產(chǎn) 每單位甲產(chǎn)品可獲利800元，乙產(chǎn)品為1000元，工廠在安排生產(chǎn)計(jì)劃時(shí)，有如下一系列考慮：(1)由于市場(chǎng)信息反饋，產(chǎn)品甲銷售量有下降趨勢(shì)，故決定產(chǎn)品甲的生產(chǎn)量不超過產(chǎn)品乙的生產(chǎn)量(2)盡可能不超過計(jì)劃使用原材料，因?yàn)槌^計(jì)劃后，需高價(jià)采購原材料，使成本增加(3)盡可能充分利用設(shè)備，但不希望加班(4)盡可能達(dá)到并超過計(jì)劃利潤5600元一、實(shí)一、實(shí) 例例甲乙擁有量原材料2111(kg)設(shè)備1210(臺(tái)時(shí))利潤/元8001000第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模

4、型顯然這是一個(gè)多目標(biāo)問題，若設(shè)x1,x2分別為該廠每日生產(chǎn)甲，乙兩種產(chǎn)品的產(chǎn)量，則工廠決策者的考慮則可表示成：x1-x202x1+x2 11X1+2x2 108x1+10 x256第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型2、目標(biāo)規(guī)劃的基本概念與特點(diǎn)(1)理想值(期望值) 是指決策者事先對(duì)每個(gè)目標(biāo)都有個(gè)期望值 如上例的右端值：0,11,10,56(2)正負(fù)偏差變量d+,d- 目標(biāo)規(guī)劃不是對(duì)每個(gè)目標(biāo)求最優(yōu)值，而是尋找使每個(gè)目標(biāo)與各自的理想值之差盡可能小的解，為此對(duì)每個(gè)原始目標(biāo)表達(dá)式(等式或不等式)的左端都加上負(fù)偏差變量d-及減去正偏差變量d+后，都將變成等式.第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例

5、與模型如 8x1+10 x2568x1+10 x2+d-d+=56d-表示：當(dāng)決策變量x1,x2取定一組值后，由原始目標(biāo)式左端計(jì)算出來的值與理想值之偏差不足理想值的偏差d+表示超過理想值之偏差計(jì)算值與理想值關(guān)系：不足：d+=0超過：d-=0等于：d-=d+=0因此將總有：d+*d-=0必成立第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型(3)絕對(duì)約束與目標(biāo)約束 絕對(duì)約束(硬約束)是指必須嚴(yán)格滿足的等式或不等式約束，如線性規(guī)劃問題中的所有約束條件都是絕對(duì)約束。 如上例2x1+x2 11 目標(biāo)約束是目標(biāo)規(guī)劃特有的約束，它是把要追求的目標(biāo)的理想值作為右端常數(shù)項(xiàng)，在目標(biāo)表達(dá)式左端加減正負(fù)偏差變量構(gòu)成的等式

6、約束，目標(biāo)約束是由決策變量、正負(fù)偏差變量及理想值構(gòu)成的軟約束 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-+d3+=56第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型絕對(duì)約束與目標(biāo)約束從形式上可以轉(zhuǎn)化的如上例的絕對(duì)約束可以轉(zhuǎn)化為2x1+x2+d4-d4+=11 和附加約束d4+=0一般地 fi(x)+di-di+=bi附加約束 di-=0 相當(dāng)于絕對(duì)約束fi(x) bi附加約束di+=0 相當(dāng)于約束約束fi(x) bi附加約束di-=di+=0 相當(dāng)于fi(x)=bi第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型(4)優(yōu)先級(jí)與權(quán)因子 多個(gè)目標(biāo)之間有主次緩急

7、之分，凡要求首先達(dá)到的目標(biāo)，賦于優(yōu)先級(jí)p1,要求第2位達(dá)到的目標(biāo)賦于優(yōu)先級(jí)p2,設(shè)共有k0個(gè)優(yōu)先級(jí)則規(guī)定 p1p2p3Pk00 P1優(yōu)先級(jí)遠(yuǎn)遠(yuǎn)高于p2,p3，只有當(dāng)p1級(jí)完成優(yōu)化后，再考慮p2,p3。反之p2在優(yōu)化時(shí)不能破壞p1級(jí)的優(yōu)先值，p3級(jí)在優(yōu)化時(shí)不能破壞p1,p2已達(dá)到的優(yōu)值 由于絕對(duì)約束是必須滿足的約束，因此與絕對(duì)約束相應(yīng)的目標(biāo)函數(shù)總是放在p1級(jí)第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型 有時(shí)在同一優(yōu)先級(jí)中有幾個(gè)不同的偏差變量要求極小，而這幾個(gè)偏差變量之間重要性又有區(qū)別，這時(shí)可以用權(quán)因子來區(qū)別同一優(yōu)先級(jí)中不同偏差變量的重要性，重要性大的在偏差變量前賦予大的系數(shù)如P3(2d3-+d3+

8、)表示偏差變量d3-,d3+處于同一優(yōu)先級(jí)，但d3-的重要性比d3+的大，前者重要程度約為后者的2倍第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型(5)目標(biāo)函數(shù)準(zhǔn)則函數(shù)目標(biāo)函數(shù)是由各目標(biāo)約束的正負(fù)偏差變量及其相應(yīng)的優(yōu)先級(jí)、權(quán)因子構(gòu)成的函數(shù)，且對(duì)這個(gè)函數(shù)求極小值，其中不包含決策變量xi.因?yàn)闆Q策者的愿望總是希望盡可能縮小偏差，使目標(biāo)盡可能達(dá)到理想值，因此目標(biāo)函數(shù)總是極小化。有三種基本形式：第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型對(duì)fi(x)+di-di+=gi，要求選取一組x使：(1)若希望fi(x) gi，即fi(x)超過gi可以接受，不足則不能接受，則其對(duì)應(yīng)目標(biāo)函數(shù)為mindi-(2)若希望f

9、i(x) gi，即fi(x)不能超過gi值，不足可以接受，超過則不能接受，則其目標(biāo)函數(shù)為：mindi+(3)若希望fi(x)=gi，即fi(x)既不能超過也不能不足gi，只能恰好等于gi，則其目標(biāo)函數(shù)為：min(di-+di+)第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型對(duì)于上例目標(biāo)約束為：x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56考慮甲的生產(chǎn)量不能超過乙的生產(chǎn)量第1優(yōu)先級(jí)目標(biāo)函數(shù)為：minp1d1+考慮盡可能地充分利用設(shè)備，但不希望加班第2級(jí)的目標(biāo)函數(shù)為：minp2(d2-+d2+)工廠希望達(dá)到并超過計(jì)劃利潤5600 第3級(jí)的目標(biāo)函數(shù)為

10、:minp3(d3-)第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型因此其目標(biāo)規(guī)劃的數(shù)學(xué)模型：minz=p1d1+p2(d2-+d2+)+p3d3-s.t 2x1+x211 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1,x20,di-,di+0，i=1,2,3第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型看起來有點(diǎn)繁有點(diǎn)煩例2：設(shè)某公司生產(chǎn)兩種型號(hào)的電扇，一種為普通型，裝配一個(gè)需要1小時(shí)，另一種為豪華型，裝配一個(gè)需要2小時(shí)。正常的裝配時(shí)間每周限定為40小時(shí)。市場(chǎng)調(diào)查表明每周銷售普通型不超過30件，豪華型不超過15件。普通型每件的凈利潤為8

11、元，豪華型為每件12元。p公司經(jīng)理提出如下優(yōu)先次序的要求： n1總利潤最大n2裝配線盡可能少加班n3銷售盡可能多的電扇（這同盡可能獲取最大利潤一致）。 n4根據(jù)市場(chǎng)調(diào)研要求每周生產(chǎn)的產(chǎn)品數(shù)不能多于銷售的數(shù)量，即普通型電扇為30件，豪華型電扇為15件。第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型該問題的決策目標(biāo)是：該問題的決策目標(biāo)是：（1）總利潤最大；（2）盡可能少加工；（3）盡可能多銷售電扇；（4）生產(chǎn)數(shù)量不能超過預(yù)銷售數(shù)量。（5）絕對(duì)目標(biāo)約束。所謂絕對(duì)目標(biāo)約束絕對(duì)目標(biāo)約束就是必須要嚴(yán)格滿足的約束。絕對(duì)目標(biāo)約束是最高優(yōu)先級(jí)，在考慮較低優(yōu)先級(jí)的目標(biāo)之前它們必須首先得到滿足。第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型

12、目標(biāo)規(guī)劃實(shí)例與模型 0, 15 30 4021000128 . .)5 . 1(),(),(),(min21222111442133212144332211),(21ddxxddxddxddxxddxxtsddPdPdPddPxx第一優(yōu)先級(jí)決策目標(biāo) 正偏差：決策正偏差：決策值超過目標(biāo)值的值超過目標(biāo)值的偏差部分偏差部分 負(fù)偏差：決策值小于目標(biāo)值的偏差部分 指標(biāo)偏離函數(shù) 約束條件約束條件決決策策變變量量第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型二、建立目標(biāo)規(guī)劃模型的步驟二、建立目標(biāo)規(guī)劃模型的步驟 p第一步：定義決策變量和有關(guān)的常量第一步：定義決策變量和有關(guān)的常量定義決策變量和決策目標(biāo)約束等式右邊的

13、常數(shù)。等定義決策變量和決策目標(biāo)約束等式右邊的常數(shù)。等式右邊的常數(shù)是可利用的資源或是決策者特定的目標(biāo)值。式右邊的常數(shù)是可利用的資源或是決策者特定的目標(biāo)值。p第二步：建立決策目標(biāo)約束第二步：建立決策目標(biāo)約束 通過分析決策變量之間的關(guān)系以及決策變量與目標(biāo)值通過分析決策變量之間的關(guān)系以及決策變量與目標(biāo)值之間的關(guān)系，建立一組目標(biāo)約束。并從所有的決策目標(biāo)中，之間的關(guān)系，建立一組目標(biāo)約束。并從所有的決策目標(biāo)中，找出絕對(duì)決策目標(biāo)（即，如果不滿足將導(dǎo)致最終結(jié)果無法找出絕對(duì)決策目標(biāo)（即，如果不滿足將導(dǎo)致最終結(jié)果無法實(shí)現(xiàn)的目標(biāo)），將這些目標(biāo)作為第一優(yōu)先級(jí)。而后再確定實(shí)現(xiàn)的目標(biāo)），將這些目標(biāo)作為第一優(yōu)先級(jí)。而后再確定

14、其余目標(biāo)的優(yōu)先級(jí)。其余目標(biāo)的優(yōu)先級(jí)。p第三步：建立指標(biāo)偏差函數(shù)第三步：建立指標(biāo)偏差函數(shù)第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃的一般模型為：目標(biāo)規(guī)劃的一般模型為： ), 2 , 1( 0 , ), 2 , 1( 0 ), 2 , 1( ),( . .)(min1n111LlddnjxLleddxcbxatsdwdwPalljlllnjjljjjjijKkLllkllklk第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型其中其中x xj j（j=1,2,j=1,2,n n）為決策變量；）為決策變量；P Pk k（ k=1,2k=1,2.K.K）為第）為第k k級(jí)優(yōu)先因子；級(jí)優(yōu)先因子；WWkl

15、 kl+ +,w,wkl kl- - 分別為第分別為第l l個(gè)目標(biāo)約束的正負(fù)偏差變量的權(quán)個(gè)目標(biāo)約束的正負(fù)偏差變量的權(quán)系數(shù)，在同一等級(jí)的目標(biāo)中，根據(jù)對(duì)各因子考慮的先系數(shù)，在同一等級(jí)的目標(biāo)中，根據(jù)對(duì)各因子考慮的先后次序的不同，賦予不同權(quán)系數(shù)。后次序的不同，賦予不同權(quán)系數(shù)。 e el l（ l=1,2,l=1,2,.L .L）為目標(biāo)的預(yù)期目標(biāo)值；）為目標(biāo)的預(yù)期目標(biāo)值；b bj j 為系統(tǒng)的資源量。為系統(tǒng)的資源量。 第一節(jié)目標(biāo)規(guī)劃實(shí)例與模型目標(biāo)規(guī)劃實(shí)例與模型用圖解法求目標(biāo)規(guī)劃的數(shù)學(xué)模型：minz=p1d1+p2(d2-+d2+)+p3d3-s.t 2x1+x211 x1-x2+d1-d1+=0 x1+

16、2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1,x20,di-,di+0，i=1,2,3第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法一、圖解法第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法(1)先作硬約束與決策變量的非負(fù)約束，同一般線性規(guī)劃作圖法 即先作：2x1+x2=11 及 x10,x20(2)作目標(biāo)約束，此時(shí)，先讓di-=di+=0。然后標(biāo)出di- 及di+的增加方向(實(shí)際上是目標(biāo)值減少與增加的方向)對(duì)例1 x1-x2=0 x1+2x2=10 8x1+10 x2=56(3)按優(yōu)先級(jí)的次序，逐級(jí)讓目標(biāo)規(guī)劃的目標(biāo)函數(shù)中極小化偏差變量取0，從而逐步縮小可行域，最后找到問題的

17、解一、圖解法2x1+x2=11x1-x2=0d1-d1+x1+2x2=10d2+d2-CD8x1+10 x2=56FEGd3+d3-OABP1:mind1+P2:min(d2-+d2+)P3:min(d3-) 滿意解為線段DG上所有點(diǎn)(無窮多個(gè)解)第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法x1x2x1-x2=0 x1+2x2=108x1+10 x2=56p由上圖知G點(diǎn)坐標(biāo)方程組x1+2x2=108x1+10 x2=56 解得x1=2,x2=4D點(diǎn)坐標(biāo)方程組為：x1+2x2=10 x1-x2=0 解得x1=x2=10/3 此時(shí)d1+=0,d2-+d2+=0,d3-=0都已滿足第二節(jié)目標(biāo)規(guī)劃的求解

18、方法目標(biāo)規(guī)劃的求解方法 再滿足P4 ,使 , 極小化，由于 是 的1.5倍，先考慮先滿足P1 =0, =04d4d3d4d再滿足P2使 =01d3d再滿足P3使 極小化3d2d第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法單純形方法單純形方法問題問題 第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方法i ii ic cz z ciP15P33P3P4P2ziVBx1x2d1-d2-d3-d11-d1+d11+P1d1-80111-15P3d2-701 113P3d3-4511d11-1011-1P40-1P348553P20-1P18011-1 在選擇最優(yōu)列時(shí)，先從檢驗(yàn)數(shù)欄中最優(yōu)等級(jí) 行開始尋找最大正檢驗(yàn)數(shù)。如 行內(nèi)有最大正檢驗(yàn)數(shù)，就確定它為最優(yōu)列，進(jìn)行迭代。直到 行內(nèi)檢驗(yàn)數(shù)沒有正值為止，再轉(zhuǎn)入 行尋找最大檢驗(yàn)數(shù)。如此繼續(xù)下去，直到所有檢驗(yàn)數(shù)全部檢查完畢。1P1P1P2P檢驗(yàn)數(shù)的計(jì)算：以 列為例，此時(shí)， ， 所以， 。故在檢驗(yàn)數(shù)欄中的 行和 行與 列的交叉點(diǎn)處的數(shù)分別為1和5。 1x315PPzi0ic315PPczii1P3P1x第二節(jié)目標(biāo)規(guī)劃的求解方法目標(biāo)規(guī)劃的求解方