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

1、目 標(biāo) 規(guī) 劃(Goal programming)目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃概述目 標(biāo) 規(guī) 劃目標(biāo)規(guī)劃的數(shù)學(xué)模型目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī) 同時考慮多個決策目標(biāo)時，稱為多目標(biāo)規(guī)劃問題。 同時考慮多個決策目標(biāo)時，稱為多目標(biāo)規(guī)劃問題。4-0 引言從線性規(guī)劃問題可看出： 線性規(guī)劃只研究在滿足一定條件下，單一目標(biāo)函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標(biāo)決策問題，如擬訂生產(chǎn)計劃時，不僅考慮總產(chǎn)值，同時要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標(biāo)之間的重要程度（即優(yōu)先順序）也不相同，有些目標(biāo)之間往往相互發(fā)生矛盾。4-0 引言線性規(guī)劃致力于某個目標(biāo)函數(shù)的最優(yōu)解，這個最優(yōu)解

2、若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。線性規(guī)劃致力于某個目標(biāo)函數(shù)的最優(yōu)解，這個最優(yōu)解若是超過了實際求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進行，這將給人們進一步應(yīng)用線性規(guī)劃方法帶來困難。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標(biāo)之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標(biāo)規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題

3、得到滿意的解答。為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標(biāo)之間的矛4-1 多目標(biāo)規(guī)劃問題多目標(biāo)規(guī)劃問題的提出 在實際問題中，可能會同時考慮幾個方面都達到最優(yōu)：產(chǎn)量最高，成本最低，質(zhì)量最好，利潤最大，環(huán)境達標(biāo)，運輸滿足等。多目標(biāo)規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標(biāo)的關(guān)系，求得更切合實際要求的解。 目標(biāo)規(guī)劃可根據(jù)實際情況，分主次地、輕重緩急地考慮問題。4-1 多目標(biāo)規(guī)劃問題例4-1：一個企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達到最大？例4-1：一個企

4、業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單如何安排生產(chǎn)，使利潤達到最大。用單純形法求得最優(yōu)解=（20，20）最優(yōu)值=200（百元）如何安排生產(chǎn)，使利潤達到最大。問題：該廠提出如下目標(biāo)（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；如何安排生產(chǎn)？問題：該廠提出如下目標(biāo)例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)計劃： 例4-2：某車間有A、B兩條設(shè)備相同的生產(chǎn)線，它們生產(chǎn)同一種（1）生產(chǎn)量達到210件/周；（2） A生產(chǎn)線加班

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

6、級 先將目標(biāo)等級化：將目標(biāo)按重要性的程度不同依次分成一級目標(biāo)、二級目標(biāo).。最次要的目標(biāo)放在次要的等級中。多目標(biāo)優(yōu)先級目標(biāo)優(yōu)先級作如下約定：對同一個目標(biāo)而言，若有幾個決策方案都能使其達到，可認為這些方案就這個目標(biāo)而言都是最優(yōu)方案；若達不到，則與目標(biāo)差距越小的越好。目標(biāo)優(yōu)先級作如下約定：目標(biāo)優(yōu)先級作如下約定： 不同級別的目標(biāo)的重要性是不可比的。即較高級別的目標(biāo)沒有達到的損失，任何較低級別的目標(biāo)上的收獲都不可彌補。所以在判斷最優(yōu)方案時，首先從較高級別的目標(biāo)達到的程度來決策，然后再其次級目標(biāo)的判斷。目標(biāo)優(yōu)先級作如下約定：目標(biāo)優(yōu)先級作如下約定：同一級別的目標(biāo)可以是多個。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）

7、來描述。因此，同一級別的目標(biāo)的其中一個的損失，可有其余目標(biāo)的適當(dāng)收獲來彌補。目標(biāo)優(yōu)先級作如下約定：多目標(biāo)規(guī)劃解的概念：若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；多目標(biāo)規(guī)劃解的概念：多目標(biāo)規(guī)劃解的概念：若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；多目標(biāo)規(guī)劃解的概念：多目標(biāo)規(guī)劃解的概念：若多目標(biāo)規(guī)劃問題的解能使所有的目標(biāo)都達到，就稱該解為多目標(biāo)規(guī)劃的最優(yōu)解；若解只能滿足部分目標(biāo)，就稱該解為多目標(biāo)規(guī)劃的次優(yōu)解；若找不到滿足任何一個目標(biāo)的解，就稱該問題為無解。多目標(biāo)規(guī)劃解的概念：例4-4：（例

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

9、4-1的問題，設(shè)超過一噸鋼材與超過5個工時的損失相同?，F(xiàn)目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；對于（1），只有方案4沒有完成。排除方案4。對于（2），只有方案2達到了，因此方案2是最優(yōu)。目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；方案1與方案3都達到了（1），又沒達到（2）方案1與（2）的差距：工時損失=（110-100）*5+（130-120）*1=60目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工方案3與（2）的差距：工時損失=0*5+（1

10、90-120）*1=70方案1優(yōu)于方案3。方案2優(yōu)于方案1優(yōu)于方案3優(yōu)于方案4方案3與（2）的差距：例4-4：繼續(xù)上例例4-4：繼續(xù)上例目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；對于（1），三個方案都沒有完成。但方案3離目標(biāo)最遠，方案3最差。方案1與（2）的差距：工時損失=（108-100）*5+（130-120）*1=50目標(biāo)：（1）利潤達到280百元；（2）鋼材不超過100噸，工方案2與（2）的差距：工時損失=0*5+（160-120）*1=40方案2優(yōu)于方案1方案2優(yōu)于方案1優(yōu)于方案3方案2與（2）的差距：4-2 多目標(biāo)規(guī)劃問題的數(shù)學(xué)模型多目標(biāo)的處理

11、 為了將不同級別的目標(biāo)的重要性用數(shù)量表示，引進P1，P2，.,用它表示一級目標(biāo)，二級目標(biāo)，.，的重要程度，規(guī)定P1P2 P3 .。稱P1，P2，.,為級別系數(shù)。4-2 多目標(biāo)規(guī)劃問題的數(shù)學(xué)模型約束方程的處理差異變量：決策變量x超過目標(biāo)值b的部分記d+決策變量x不足目標(biāo)值b的部分記d-d+ 0, d- 0 且 x- d+ + d-= b約束方程的處理多目標(biāo)的綜合若決策目標(biāo)中規(guī)定 x b, 當(dāng) d+ = 0 時目標(biāo)才算達到。多目標(biāo)的綜合多目標(biāo)的綜合若決策目標(biāo)中規(guī)定 x b, 當(dāng) y+=0 時目標(biāo)才算達到。若決策目標(biāo)中規(guī)定 x b, 當(dāng) d- = 0 時目標(biāo)才算達到。多目標(biāo)的綜合多目標(biāo)的綜合若決策目

12、標(biāo)中規(guī)定 x b, 當(dāng) y+=0 時目標(biāo)才算達到。若決策目標(biāo)中規(guī)定 x b, 當(dāng) y-=0 時目標(biāo)才算達到。若決策目標(biāo)中規(guī)定 x = b, 當(dāng) d+ = d- = 0 時目標(biāo)才算達到。多目標(biāo)的綜合例4-5（例4-4)解：引進級別系數(shù)P1：（1）利潤達到280百元；P2：（2）鋼材不超過100噸，工時不超過120小時；（權(quán)數(shù)之比5：1）例4-5（例4-4)數(shù)學(xué)模型：目標(biāo)函數(shù)：Min S=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

13、,2,3)數(shù)學(xué)模型：例4-6（例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)計劃： 例4-6（例4-2) 某車間有A、B兩條設(shè)備相同的生產(chǎn)線，它（1）生產(chǎn)量達到210件/周；（2） A生產(chǎn)線加班時間限制在15小時內(nèi)；（3）充分利用工時指標(biāo)，并依A、B產(chǎn)量的比例確定重要性。（1）生產(chǎn)量達到210件/周；解：設(shè)A，B生產(chǎn)線每周工作時間為X1，X2。A，B的產(chǎn)量比例2：1.5 = 4:3目標(biāo)函數(shù)：Min S=P1d1-+P2d2+4 P3d3-+3 P3d4

14、-約束方程： 2X1+1.5X2+ d1- d1+=210 （生產(chǎn)量達到210件/周） X1 + d2- d2+=60（A生產(chǎn)線加班時間限制在15小時內(nèi)） 解：設(shè)A，B生產(chǎn)線每周工作時間為X1，X2。A，B的產(chǎn)量比例 X1 + d3- d3+=45 （充分利用A的工時指標(biāo)） X2+ d4- d4+=45 （充分利用B的工時指標(biāo)） X1,X2,di-, di+ 0(i=1,2,3,4) X1 A，B的產(chǎn)量比例2：1.5 = 4:3目標(biāo)函數(shù)： Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-約束方程： 2X1+1.5X2+ d1- d1+= 210 X1 + d2- d2+= 60

15、 X1 + d3- d3+= 45 X2+ d4- d4+= 45 X1,X2,di-, di+ 0 (i=1,2,3,4)A，B的產(chǎn)量比例2：1.5 = 4:3例4-7(例4-3)：(1)庫存費用不超過4600元；(2)每月銷售唱機不少于80臺；(3)不使A、B車間停工（權(quán)數(shù)由生產(chǎn)費用確定）；(4)A車間加班時間限制在20小時內(nèi)；例4-7(例4-3)：（5）每月銷售錄音機為100臺；（6）兩車間加班時數(shù)總和要盡可能?。?quán)數(shù)由生產(chǎn)費用確定）；解：設(shè)每月生產(chǎn)唱機、錄音機X1，X2臺。且A、B的生產(chǎn)費用之比為100：50=2：1（5）每月銷售錄音機為100臺；目標(biāo)函數(shù)：Min S=P1d1+P2d

16、2-+2 P3d4-+ P3d5- +P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+約束方程： 50X1+30X2+ d1- d1+=4600 （庫存費用不超過4600元） X1 + d2- d2+=80 （每月銷售唱機不少于80臺）目標(biāo)函數(shù)： X2 + d3- d3+=100 （每月銷售錄音機為100臺） 2X1 + X2+ d4- d4+=180 （不使A車間停工） X1 + 3X2+ d5- d5+=200 （不使B車間停工） d4+ d41- d41+=20 （A車間加班時間限制在20小時內(nèi)） X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,

17、5) 目標(biāo)函數(shù)：Min S=P1d1+P2d2-+2 P3d4-+ P3d5- +P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+約束方程： 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,5)目標(biāo)函數(shù)：Min S=P1d1+P2d2-+2 P3d44-3 多目標(biāo)規(guī)劃問題的求解多目標(biāo)規(guī)劃問題的圖解法例4-8 Min S

18、= d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 04-3 多目標(biāo)規(guī)劃問題的求解x1x204681021342X1+2X2 6x1x204681021342X1+2X2 6x1x204681021342X1+X2 4x1x204681021342X1+X2 4x1x204681021342x1x204681021342x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1+d1x1x20468

19、1021342x1+2x2=105d1+d1-AB(2,2)當(dāng) Min S = d1+ 達到時 d1+ = 0 x1x204681021342x1+2x2=105d1+d1x1x204681021342x1+2x2=105d1-AB(2,2)當(dāng) Min S = d1+ 達到時 d1+ = 0 x1x204681021342x1+2x2=105d1-ABx1x204681021342x1+2x2+d1- = 10 d1- = 25d1-AB(2,2)當(dāng) Min S = d1+ 達到時 d1+ = 0 x1x204681021342x1+2x2+d1- = 10 x1x204681021342x1

20、+2x2+d1- = 10 d1- = 45d1-AB(2,2)有無窮多解：點（0，3）和點（2，2）連線上的點都是最優(yōu)解。(0,3)x1x204681021342x1+2x2+d1- = 10 x1x204681021342x1+2x2+d1- = 10 d1- = 65d1-AB(2,2)有無窮多解：點（4，0）和點（0，2）連線上的點都是最優(yōu)解。(0,3)(4,0)(0,2)x1x204681021342x1+2x2+d1- = 10 x1x204681021342x1+2x2+d1- = 10 d1- = 75d1-AB(2,2)有無窮多解：點（1，1）和點（0，3/2） （3，0）連

21、線上的點都是最優(yōu)解。(0,3)(4,0)(1,1)x1x204681021342x1+2x2+d1- = 10例4-9 Min S=P1d1-+P2d2+5 P3d3-+ P3d1+ X1+X2+ d1- d1+=40 X1+X2 + d2- d2+=50 X1 + d3- =30 X2+ d4- =30 X1,X2,dI-, dI+ 0(I=1,2,3,4)例4-9 x1x2020304050101030402050d1-d1+X1+X2=40 x1x2020304050101030402050d1-d1x1x2020304050101030402050d1-d1+d2+d2-X1+X2=5

22、0 x1x2020304050101030402050d1-d1x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30 x1x2020304050101030402050d1-d1x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30 x1x2020304050101030402050d1-d1x1x2020304050101030402050d1+d2+d2-d3-d4-Min d1- = 0可行域如圖x1x2020304050101030402050d1+d2x1x2020304050101030402050d1

23、+d2-d3-d4-Min d2+ =0可行域如圖x1x2020304050101030402050d1+d2x1x2020304050101030402050d1+d2-d4-Min d3- = 0 線段AB是可行域ABx1x2020304050101030402050d1+d2x1x2020304050101030402050d2-d4-Min d1+ = 0P=(30,10)唯一最優(yōu)解。 d2- =10 d4- = 20Px1x2020304050101030402050d2-d4例4-10 Min S=P1d1-+P2d2+ P3d3-+ P3d4- 5X1+10X2+ d1- d1+

24、=100 2X1 + X2 + d2- d2+=14 X1 + d3- d3+=6 X2+ d4- d4+=10 X1,X2,di-, di+ 0(i=1,2,3,4)例4-10 x1x20101520255515201025d1+d1-5X1+10X2=100 x1x20101520255515201025d1+d1-5x1x20101520255515201025d1+d1-d2+d2-2X1 +X2 =14x1x20101520255515201025d1+d1-dx1x20101520255515201025d1+d1-d2+d2-d3+d3-X1 =6x1x2010152025551

25、5201025d1+d1-dx1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10 x1x20101520255515201025d1+d1-dx1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Min d1- = 0 x1x20101520255515201025d1+d2+dx1x20101520255515201025d1+d2-d3+d3-d4+d4-Min d2+ = 0可行域如圖x1x20101520255515201025d1+d2-dx1x20101520255515201025d1+d2-d3+d4+d4-Min d3- =0可行域為空如圖x1x20101520255515201025d1+d2-dx1x20101520255515201025d1+d2-d3+d4+Min d3- 0Min d4- = 0可行域如圖d3-(2,10)x1x2010152025551