運籌學(xué)多目標(biāo)規(guī)劃(1)

1、例4-1：一個企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達(dá)到最大？用單純形法求得最優(yōu)解=（20，20）最優(yōu)值=200（百元）1問題：該廠提出如下目標(biāo)（1）利潤達(dá)到280百元；（2）鋼材不超過100噸，工時不超過120小時；如何安排生產(chǎn)？2例4-2：某車間有A、B兩條設(shè)備相同的生產(chǎn)線，它們生產(chǎn)同一種產(chǎn)品。A生產(chǎn)線每小時可制造2件產(chǎn)品，B生產(chǎn)線每小時可制造1.5件產(chǎn)品。如果每周正常工作時數(shù)為45小時，要求制定完成下列目標(biāo)的生產(chǎn)計劃： （1）生產(chǎn)量達(dá)到210件/

2、周；（2） A生產(chǎn)線加班時間限制在15小時內(nèi)；（3）充分利用工時指標(biāo)，并依A、B產(chǎn)量的比例確定重要性。3例4-3：某電器公司經(jīng)營的唱機(jī)和錄音機(jī)均有車間A、B流水作業(yè)組裝。數(shù)據(jù)見下表。要求按以下目標(biāo)制訂月生產(chǎn)計劃：（1）庫存費用不超過4600元；（2）每月銷售唱機(jī)不少于80臺；（3）不使A、B車間停工（權(quán)數(shù)由生產(chǎn)費用確定）；（4）A車間加班時間限制在20小時內(nèi)；（5）每月銷售錄音機(jī)為100臺；（6）兩車間加班時數(shù)總和要盡可能?。?quán)數(shù)由生產(chǎn)費用確定）；4多目標(biāo)優(yōu)先級 先將目標(biāo)等級化：將目標(biāo)按重要性的程度不同依次分成一級目標(biāo)、二級目標(biāo).。最次要的目標(biāo)放在次要的等級中。目標(biāo)優(yōu)先級作如下約定：對同一個目

3、標(biāo)而言，若有幾個決策方案都能使其達(dá)到，可認(rèn)為這些方案就這個目標(biāo)而言都是最優(yōu)方案；若達(dá)不到，則與目標(biāo)差距越小的越好。不同級別的目標(biāo)的重要性是不可比的。即較高級別的目標(biāo)沒有達(dá)到的損失，任何較低級別的目標(biāo)上的收獲都不可彌補(bǔ)。所以在判斷最優(yōu)方案時，首先從較高級別的目標(biāo)達(dá)到的程度來決策，然后再其次級目標(biāo)的判斷。同一級別的目標(biāo)可以是多個。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級別的目標(biāo)的其中一個的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補(bǔ)。5多目標(biāo)規(guī)劃解的概念：若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達(dá)到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；若找不到滿足任何

4、一個目標(biāo)的解，就稱該問題為無解。6例4-1：一個企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達(dá)到最大？用單純形法求得最優(yōu)解=（20，20）最優(yōu)值=200（百元）7問題：該廠提出如下目標(biāo)（1）利潤達(dá)到280百元；（2）鋼材不超過100噸，工時不超過120小時；如何安排生產(chǎn)？8對例4-1的問題，設(shè)超過一噸鋼材與超過5個工時的損失相同。現(xiàn)有四個方案進(jìn)行比較優(yōu)劣？9目標(biāo)：（1）利潤達(dá)到280百元； （2）鋼材不超過100噸，工時不超過120小時；對于（1），只有方案

5、4沒有完成。排除方案4。對于（2），只有方案2達(dá)到了，因此方案2是最優(yōu)。10目標(biāo)：（1）利潤達(dá)到280百元； （2）鋼材不超過100噸，工時不超過120小時；方案1與方案3都達(dá)到了（1），又沒達(dá)到（2）方案1與（2）的差距：工時損失=（110-100）*5+（130-120）*1=60方案3與（2）的差距：工時損失=0*5+（190-120）*1=70方案1優(yōu)于方案3。方案2優(yōu)于方案1、優(yōu)于方案3、優(yōu)于方案411例4-4：繼續(xù)上例12目標(biāo)：（1）利潤達(dá)到280百元；（2）鋼材不超過100噸，工時不超過120小時；對于（1），三個方案都沒有完成。但方案3離目標(biāo)最遠(yuǎn)，方案3最差。方案5與（2）的差

6、距：工時損失=（108-100）*5+（130-120）*1=50方案6與（2）的差距：工時損失=0*5+（160-120）*1=40方案6優(yōu)于方案5方案6優(yōu)于方案5、優(yōu)于方案7134-2 多目標(biāo)規(guī)劃問題的數(shù)學(xué)模型多目標(biāo)的處理 為了將不同級別的目標(biāo)的重要性用數(shù)量表示，引進(jìn)P1，P2，.,用它表示一級目標(biāo)，二級目標(biāo)，.，的重要程度，規(guī)定P1P2 P3 .。稱P1，P2，.,為級別系數(shù)。約束方程的處理決策變量x超過目標(biāo)值b的部分記d+ ；決策變量x不足目標(biāo)值b的部分記d- 。 d+ 、 d-稱為差異變量。d+ 0, d- 0 。且 x- d+ + d-= b14多目標(biāo)的綜合若決策目標(biāo)中規(guī)定為 時,

7、 應(yīng)使 minZ=f( d+ ) 。若決策目標(biāo)中規(guī)定為 時,應(yīng)使 minZ=f( d- ) 。若決策目標(biāo)中規(guī)定為 =時,應(yīng)使 minZ=f(d+ + d- )。15例4-5（例4-4)解：引進(jìn)級別系數(shù)P1：（1）利潤達(dá)到280百元；P2：（2）鋼材不超過100噸，工時不超過120小時；（權(quán)數(shù)之比5：1）16數(shù)學(xué)模型：目標(biāo)函數(shù)：Min Z=P1d1-+P2(5d2+d3+)約束方程： 6X1+4X2+ d1- d1+=280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+=120 X1,X2,di-, di+ 0(i=1,2,3)17例4-6（例4-2) 某車間有A、

8、B兩條設(shè)備相同的生產(chǎn)線，它們生產(chǎn)同一種產(chǎn)品。A生產(chǎn)線每小時可制造2件產(chǎn)品，B生產(chǎn)線每小時可制造1.5件產(chǎn)品。如果每周正常工作時數(shù)為45小時，要求制定完成下列目標(biāo)的生產(chǎn)計劃： （1）生產(chǎn)量達(dá)到210件/周；（2） A生產(chǎn)線加班時間限制在15小時內(nèi)；（3）充分利用工時指標(biāo)，并依A、B產(chǎn)量的比例確定重要性。18解：設(shè)A，B生產(chǎn)線每周工作時間為X1，X2。A，B的產(chǎn)量比例2：1.5 = 4:3目標(biāo)函數(shù)：Min Z=P1d1-+P2d2+ P3（ 4 d3-+3 d4- ）約束方程： 2X1+1.5X2+ d1- d1+=210 （生產(chǎn)量達(dá)到210件/周） X1 + d2- d2+=60（A生產(chǎn)線加班時

9、間限制在15小時內(nèi)） X1 + d3- d3+=45 （充分利用A的工時指標(biāo)） X2 + d4- d4+=45 （充分利用B的工時指標(biāo)） X1,X2,di-, di+ 0(i=1,2,3,4) 19例4-3：某電器公司經(jīng)營的唱機(jī)和錄音機(jī)均有車間A、B流水作業(yè)組裝。數(shù)據(jù)見下表。要求按以下目標(biāo)制訂月生產(chǎn)計劃：（1）庫存費用不超過4600元；（2）每月銷售唱機(jī)不少于80臺；（3）不使A、B車間停工（權(quán)數(shù)由生產(chǎn)費用確定）；（4）A車間加班時間限制在20小時內(nèi)；（5）每月銷售錄音機(jī)為100臺；（6）兩車間加班時數(shù)總和要盡可能?。?quán)數(shù)由生產(chǎn)費用確定）；20解：設(shè)每月生產(chǎn)唱機(jī)、錄音機(jī)X1，X2臺。且A、B的

10、生產(chǎn)費用之比為100：50=2：1目標(biāo)函數(shù)：Min S=P1d1+P2d2-+P3（ 2 d4-+ d5- ） +P4d41+ P5 （ d3+ + d3- ） +P6 （ 2d4+ d5+ ）約束方程： 50X1+30X2+ d1- - d1+=4600 （庫存費用不超過4600元）X1 + d2- -d2+ =80 （每月銷售唱機(jī)不少于80臺）21 2X1 + X2+ d4- - d4+=180 （不使A車間停工） X1 + 3X2+ d5- - d5+=200 （不使B車間停工） d4+ d41- - d41+=20 （A車間加班時間限制在20小時內(nèi)） X2 + d3- - d3+=10

11、0 （每月銷售錄音機(jī)為100臺） X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5)22目標(biāo)函數(shù)：Min S=P1d1+P2d2-+P3（ 2 d4-+ d5- ） +P4d41+ P5 （ d3+ + d3- ） +P6 （ 2d4+ d5+ ）約束方程： 50X1+30X2+ d1- d1+=4600 X1 + d2- d2+=80 X2 + d3- d3+=100 2X1 + X2+ d4- d4+=180 X1 + 3X2+ d5- d5+=200 d4+ d41- d41+=20 X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4

12、,5)234-3 多目標(biāo)規(guī)劃問題的圖解法例4-8 Min Z = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0法24x1x204681021342X1+2X2 625x1x204681021342X1+X2 426x1x20468102134227x1x20468102134228x1x204681021342x1+2x2=105d1+d1-AB(2,2)29x1x204681021342x1+2x2=105d1+d1-AB(2,2)當(dāng) Min Z = d1+ 達(dá)到時 d1+ = 030 x1x204681021342x1

13、+2x2+d1- = 10 d1- = 25d1-AB(2,2)當(dāng) Min Z = d1+ 達(dá)到時 d1+ = 031x1x204681021342x1+2x2+d1- = 10 d1- = 45d1-AB(2,2)有無窮多解：點（0，3）和點（2，2）連線上的點都是最優(yōu)解。(0,3)32x1x204681021342x1+2x2+d1- = 10 d1- = 65d1-AB(2,2)有無窮多解：點（4，0）和點（0，2）連線上的點都是最優(yōu)解。(0,3)(4,0)(0,2)33x1x204681021342x1+2x2+d1- = 10 d1- = 75d1-AB(2,2)有無窮多解：點（0，

14、3/2） （3，0）連線上的點都是最優(yōu)解。(0,3)(4,0)(1,1)34例4-9 Min Z=P1d1-+P2d2+ P3（ 5 d3-+ d1+ ） X1+X2+ d1- d1+=40 X1+X2 + d2- d2+=50 X1 + d3- =30 X2 + d4- =30X1,X2,dI-, dI+ 0(I=1,2,3,4)35x1x2020304050101030402050d1-d1+X1+X2=4036x1x2020304050101030402050d1-d1+d2+d2-X1+X2=5037x1x2020304050101030402050d1-d1+d2+d2-d3-X1=

15、3038x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=3039x1x2020304050101030402050d1+d2+d2-d3-d4-Min d1- = 0可行域如圖40 x1x2020304050101030402050d1+d2-d3-d4-Min d2+ =0可行域如圖41x1x2020304050101030402050d1+d2-d4-Min d3- = 0 線段AB是可行域AB42x1x2020304050101030402050d2-d4-Min d1+ = 0P=(30,10)唯一最優(yōu)解。 d2- =10 d4- = 20P

16、43例4-10 Min Z=P1d1-+P2d2+ P3（d3-+ d4- ） 5X1+10X2+ d1- d1+=100 2X1 + X2 + d2- d2+=14 X1 + d3- d3+=6 X2+ d4- d4+=10 X1,X2,di-, di+ 0(i=1,2,3,4)44x1x20101520255515201025d1+d1-5X1+10X2=10045x1x20101520255515201025d1+d1-d2+d2-2X1 +X2 =1446x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1 =647x1x201015202555152

17、01025d1+d1-d2+d2-d3+d3-d4+d4-X2=1048x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Min d1- = 049x1x20101520255515201025d1+d2-d3+d3-d4+d4-Min d2+ = 0可行域如圖50 x1x20101520255515201025d1+d2-d3+d4+d4-Min d3- =0可行域為空如圖51x1x20101520255515201025d1+d2-d3+d4+Min d3- 0Min d4- = 0可行域如圖d3-(2,10)52x1x20101520255515201025d1+d2-d3+d4+Min d3- = 0Min d4- 0可行域為空如圖d4-53對于目標(biāo)P1與目標(biāo)P2很容易達(dá)到。目標(biāo)P3的兩個指標(biāo)不能同時滿足，否則無解。又因為P3中的兩個目標(biāo)同樣重要，要討論 （1）Min d3-=0 Min d4- 0 原問題無解。（2） Min d3- 0 Min d4-=0原問題(2,10)是次優(yōu)解。54例4-11 Min Z=P1 （ d1-+d2- ） X1 +d1- d1+=15 4X1 + 5X2 + d2- d2+=200 3X1 +4X2 120 X1 -2X2 15 X1,X2,di-, di+ 0(i=1,2)55x1x2020