1、多目的規(guī)劃1概述與圖解法1、線性規(guī)劃的缺乏1、線性規(guī)劃只研討在滿足一定條件下，單一目的函數(shù)獲得最優(yōu)解。但是在企業(yè)管理中，經(jīng)常遇到多目的決策問題，如擬訂消費(fèi)方案時(shí)，不僅思索總產(chǎn)值，同時(shí)要思索利潤，產(chǎn)質(zhì)量量和設(shè)備利用率等。這些目的之間的重要程度即優(yōu)先順序也不一樣，有些目的之間往往相互發(fā)生矛盾。1、線性規(guī)劃的缺乏2、線性規(guī)劃努力于處理某個(gè)目的函數(shù)的最優(yōu)解。 3、線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同對待，不符合實(shí)踐情況。1、線性規(guī)劃的缺乏4、求解線性規(guī)劃問題，首先要求約束條件必需相容，假設(shè)約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解。 但是在消費(fèi)

2、實(shí)踐中即使出現(xiàn)了這樣的情況，消費(fèi)還得繼續(xù)進(jìn)展。這就給人們進(jìn)一步運(yùn)用線性規(guī)劃方法帶來困難。使線性規(guī)劃的運(yùn)用遭到限制。2、目的規(guī)劃的作用在實(shí)踐消費(fèi)管理問題中，能夠會(huì)同時(shí)思索幾個(gè)方面都要求到達(dá)最優(yōu)，如：產(chǎn)量最高，本錢最低，質(zhì)量最好，利潤最大，環(huán)境達(dá)標(biāo)，運(yùn)輸滿足等。同時(shí)思索多個(gè)決策目的時(shí)，稱為多目的規(guī)劃問題。1、為了彌補(bǔ)線性規(guī)劃問題的局限性，處理有限資源和方案目的之間的矛盾，在線性規(guī)劃根底上，運(yùn)用建立目的規(guī)劃方法，從而使一些線性規(guī)劃無法處理的問題得到稱心的解答。2、目的規(guī)劃的作用2、目的規(guī)劃能更好地兼顧統(tǒng)籌處置多種目的的關(guān)系，求得更切合實(shí)踐要求的解。 3、目的規(guī)劃可根據(jù)實(shí)踐情況，分主次地、輕重緩急地思

3、索問題。3、多目的規(guī)劃問題的提出 例1：一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤也不一樣如下表。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤到達(dá)最大？解：設(shè)消費(fèi)甲產(chǎn)品X1件，乙產(chǎn)品X2件，那么運(yùn)用線性規(guī)劃，建立模型如下： MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2120 X1、X2 0初始單純形表C6400CBXBX1X2X3X4b0X32310100500X4420112030 6 40 0 0C6400CBXBX1X2X3X4b0X3021-1/2406X111/201/430010-3

4、/2C6400CBXBX1X2X3X4b4X2011/2-1/4206X110-1/43/82000-1/2-5/4最終單純形表為：C6400CBXBX1X2X3X4b4X2011/2-1/4206X110-1/43/82000-1/2-5/4原問題最優(yōu)解為： X1 =20，X2=20最優(yōu)值 Z=200百元對偶問題最優(yōu)解為：Y1=1/2，Y2=5/4最優(yōu)值 Z=200百元問題提出該廠提出如下目的1利潤到達(dá)280百元；2鋼材不超越100噸，工時(shí)不超越120小時(shí)； 如何安排消費(fèi)？例2某車間有A、B兩條設(shè)備一樣的消費(fèi)線，它們消費(fèi)同一種產(chǎn)品。A消費(fèi)線每小時(shí)可制造2件產(chǎn)品，B消費(fèi)線每小時(shí)可制造1.5件產(chǎn)

5、品。假設(shè)每周正常任務(wù)時(shí)數(shù)為45小時(shí)，要求制定完成以下目的的消費(fèi)方案：1消費(fèi)量到達(dá)210件/周；2 A消費(fèi)線加班時(shí)間限制在15小時(shí)內(nèi)；3充分利用工時(shí)目的，并依A、B產(chǎn)量 的比例確定重要性。例3 某電器公司運(yùn)營的唱機(jī)和錄音機(jī)均有車間A、B流水作業(yè)組裝。數(shù)據(jù)見下表。 公司方案要求按以下目的制定月消費(fèi)方案：1庫存費(fèi)用不超越4600元；2每月銷售唱機(jī)不少于80臺(tái)； 3不使A、B車間停工權(quán)數(shù)由消費(fèi)費(fèi)用確定；4A車間加班時(shí)間限制在20小時(shí)內(nèi)；5每月銷售錄音機(jī)為100臺(tái)；6兩車間加班時(shí)數(shù)總和要盡能夠小權(quán)數(shù)由消費(fèi) 費(fèi)用確定；4、多目的規(guī)劃優(yōu)先級(jí)的概念1、目的等級(jí)化：將目的按重要性的程度不同依次分成一級(jí)目的、二級(jí)

6、目的.。最次要的目的放在次要的等級(jí)中。2、對同一個(gè)目的而言，假設(shè)有幾個(gè)決策方案都能使其到達(dá)，可以為這些方案就這個(gè)目的而言都是最優(yōu)方案；假設(shè)達(dá)不到，那么與目的差距越小的越好。4、多目的規(guī)劃優(yōu)先級(jí)的概念3、不同級(jí)別的目的的重要性是不可比的。即較高級(jí)別的目的沒有到達(dá)的損失，任何較低級(jí)別的目的上的收獲都不可彌補(bǔ)。4、在判別最優(yōu)方案時(shí)，首先從較高級(jí)別的目的到達(dá)的程度來決策，然后再其次級(jí)目的的判別。5、同一級(jí)別的目的可以是多個(gè)。各自之間的重要程度可用數(shù)量權(quán)數(shù)來描畫。因此，同一級(jí)別的目的的其中一個(gè)的損失，可用其他目的的適當(dāng)收獲來彌補(bǔ)。5、多目的規(guī)劃解的概念1、假設(shè)多目的規(guī)劃問題的解能使一切的目的都到達(dá)，就稱

7、該解為多目的規(guī)劃的最優(yōu)解；2、假設(shè)解只能滿足部分目的，就稱該解為多目的規(guī)劃的次優(yōu)解；3、假設(shè)找不到滿足任何一個(gè)目的的解，就稱該問題為無解。5、多目的規(guī)劃解的概念舉例 一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤也不一樣如下表。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤到達(dá)最大？解：設(shè)消費(fèi)甲產(chǎn)品X1件，乙產(chǎn)品X2件，那么運(yùn)用線性規(guī)劃，建立模型如下： MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2 0用單純形法求得最優(yōu)解=20，20；最優(yōu)值=200百元問題提出該廠提出如下目的1利潤到達(dá)280百元；2鋼

8、材不超越100噸，工時(shí)不超越120小時(shí)； 如何安排消費(fèi)？ 注：超越一噸鋼材與超越5個(gè)工時(shí)的損失一樣解：為到達(dá)第一目的，現(xiàn)可以提出4個(gè)方案如下：方案號(hào)甲產(chǎn)品產(chǎn)量乙產(chǎn)品產(chǎn)量鋼材（噸）工時(shí)（時(shí)）利潤（百元)損失量150010020030080207021014028057034441001842806444539918628266經(jīng)過對上述四個(gè)方案比較進(jìn)展求解：目的：1利潤到達(dá)280百元； 2鋼材不超越100噸，工時(shí)不超越120小時(shí)；討論：上述方案都到達(dá)了目的1，但是沒有到達(dá)目的2方案1與目的2的差距：工時(shí)損失=100-100*5+200-120*1=80方案2與目的2的差距：工時(shí)損失=210-10

9、0*5+140-120*1=570方案3與目的2的差距：工時(shí)損失=100-100*5+184-120*1=64方案4與目的2的差距：工時(shí)損失=0*5+186-120*1=66方案排序：方案2 方案1 方案3 方案46、多目的規(guī)劃數(shù)學(xué)模型建立1、多目的的處置 為了將不同級(jí)別目的的重要性用數(shù)量表示，引進(jìn)P1，P2，.,用它表示一級(jí)目的，二級(jí)目的，.，的重要程度。 規(guī)定P1P2 P3 .。 稱P1，P2，.,為級(jí)別系數(shù)。6、多目的規(guī)劃數(shù)學(xué)模型建立2、約束方程的處置 引入差別變量d+ 、d- 并規(guī)定如下： 1決策變量x超越目的值b的部分記d+ 2決策變量x缺乏目的值b的部分記d- 3d+ 0, d-

10、0 且 x- d+ + d- = b6、多目的規(guī)劃數(shù)學(xué)模型建立3、多目的的綜合1假設(shè)決策目的中規(guī)定 x b, 當(dāng) d+ = 0 時(shí)目的才算到達(dá)。2假設(shè)決策目的中規(guī)定 x b, 當(dāng) d- = 0 時(shí)目的才算到達(dá)。3假設(shè)決策目的中規(guī)定 x = b, 當(dāng) d+ = d- = 0 時(shí)目的才算到達(dá)。例如 一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤也不一樣如下表。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤到達(dá)最大？解：設(shè)消費(fèi)甲產(chǎn)品X1件，乙產(chǎn)品X2件，那么運(yùn)用線性規(guī)劃，建立模型如下： MAX Z=6X1+4X2 2X1+3X

11、2100 4X1+2X2 0用單純形法求得最優(yōu)解=20，20；最優(yōu)值=200百元問題提出該廠提出如下目的1利潤到達(dá)280百元；2鋼材不超越100噸，工時(shí)不超越120小時(shí)； 如何安排消費(fèi)？解：引進(jìn)級(jí)別系數(shù)P1：1利潤到達(dá)280百元；P2：2鋼材不超越100噸，工時(shí)不超越120 小時(shí)；權(quán)數(shù)之比5：1建立多目的規(guī)劃數(shù)學(xué)模型：目的函數(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,2,3)練習(xí)1 某車間有A、B兩條設(shè)備一樣的

12、消費(fèi)線，它們消費(fèi)同一種產(chǎn)品。A消費(fèi)線每小時(shí)可制造2件產(chǎn)品，B消費(fèi)線每小時(shí)可制造1.5件產(chǎn)品。假設(shè)每周正常任務(wù)時(shí)數(shù)為45小時(shí)，要求制定完成以下目的的消費(fèi)方案： 1消費(fèi)量到達(dá)210件/周； 2 A消費(fèi)線加班時(shí)間限制在15小時(shí)內(nèi)； 3充分利用工時(shí)目的，并依A、B產(chǎn)量的比例確定重要性。 解：設(shè)A，B消費(fèi)線每周任務(wù)時(shí)間為X1，X2。 A，B的產(chǎn)量比例2 ：1.5 = 4 :3目的函數(shù)： Min S=P1d1-+P2d2+4 P3d3-+3 P3d4-約束方程： 2X1+1.5X2+ d1- d1+=210 消費(fèi)量到達(dá)210件/周 X1 + d2- d2+=60 A消費(fèi)線加班時(shí)間限制在15小時(shí)內(nèi) X1 +

13、 d3- d3+=45 充分利用A的工時(shí)目的 X2+ d4- d4+=45 充分利用B的工時(shí)目的 X1,X2,di-, di+ 0(i=1,2,3,4) 練習(xí)2 某電器公司運(yùn)營的唱機(jī)和錄音機(jī)均有車間A、B流水作業(yè)組裝。數(shù)據(jù)見下表。 公司方案要求按以下目的制定月消費(fèi)方案：1庫存費(fèi)用不超越4600元；2每月銷售唱機(jī)不少于80臺(tái)； 3不使A、B車間停工權(quán)數(shù)由消費(fèi)費(fèi)用確定；4A車間加班時(shí)間限制在20小時(shí)內(nèi)；5每月銷售錄音機(jī)為100臺(tái)；6兩車間加班時(shí)數(shù)總和要盡能夠小權(quán)數(shù)由消費(fèi) 費(fèi)用確定；解：設(shè)每月消費(fèi)唱機(jī)X1， 、錄音機(jī)X2臺(tái)。且A、B的消費(fèi)費(fèi)用之比為 100：50=2：1目的函數(shù)：Min S=P1d1

14、+P2d2-+2P3d4-+ P3d5-+P4d41+ P5d3-+ P5d3+2P6d4+ P6d5+約束方程： 50X1+30X2+ d1- d1+=4600 庫存費(fèi)用不超越4600元 X1 + d2- d2+=80 每月銷售唱機(jī)不少于80臺(tái) X2 + d3- d3+=100 每月銷售錄音機(jī)為100臺(tái) 2X1+ X2+ d4- d4+=180 不使A車間停工 X1+ 3X2+ d5- d5+=200 不使B車間停工 d4+ d41- d41+=20 A車間加班時(shí)間限制在20小時(shí)內(nèi) X1,X2,di-, di+ ,d41-,d41+ 0(i=1,2,3,4,5)目的函數(shù)：Min S=P1d1

15、+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)7、多目的規(guī)劃問題的求解圖解法例1: 一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤也不一樣

16、如下表。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤到達(dá)最大？解：設(shè)消費(fèi)甲產(chǎn)品X1件，乙產(chǎn)品X2件，那么運(yùn)用線性規(guī)劃，建立模型如下： MAX Z=6X1+4X2 2X1+3X2100 4X1+2X2 0用單純形法求得最優(yōu)解=20，20；最優(yōu)值=200百元問題提出該廠提出如下目的1利潤到達(dá)280百元；2鋼材不超越100噸，工時(shí)不超越120小時(shí)； 如何安排消費(fèi)？解：引進(jìn)級(jí)別系數(shù)P1：1利潤到達(dá)280百元；P2：2鋼材不超越100噸，工時(shí)不超越120 小時(shí)；權(quán)數(shù)之比5：1建立多目的規(guī)劃數(shù)學(xué)模型：目的函數(shù)：Min S=P1d1-+P2(5d2+d3+)約束方程： 6X1+4X2+ d1- d1+=

17、280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+=120 X1,X2,di-, di+ 0(i=1,2,3)1020304050605040302010706X1+4X2280 2X1+3X21004X1+2X2120討論：對于目的P1與目的P2中第一個(gè)子目的很容易到達(dá)。但目的P2的兩個(gè)目的不能同時(shí)滿足，否那么無解。討論如下： 1Min d3- =0；原問題無解。2Min d3- 0 ； (44,4)是原問題的次優(yōu)解。但需求添加工時(shí)量。計(jì)算需求添加的工時(shí)量的數(shù)量：由 6X1+4X2=280和 2X1+3X2=100解得交點(diǎn)為44,4)；那么把方程4x1+2x2

18、=120平移到點(diǎn)44，4后得到：4x1+2x2=4*44+2*4=184因此添加工時(shí)量為184-120=64個(gè)工時(shí)。例2 Min S = d1+ X1+2X2+ d1- d1+ = 10 X1+2X2 6 X1+X2 4 X1,X2,d1-, d1+ 0 x1x204681021342X1+2X2 6x1x204681021342X1+X2 4x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1+d1-AB(2,2)當(dāng) Min S = d1+ 到達(dá)時(shí) d1+

19、 = 0 x1x204681021342x1+2x2=105d1-AB(2,2)當(dāng) Min S = d1+ 到達(dá)時(shí) d1+ = 0 x1x204681021342x1+2x2+d1- = 10 d1- = 25d1-AB(2,2)當(dāng) Min S = d1+ 到達(dá)時(shí) d1+ = 0 x1x204681021342x1+2x2+d1- = 10 d1- = 45d1-AB(2,2)有無窮多解：點(diǎn)0，3和點(diǎn)2，2連線上的點(diǎn)都是最優(yōu)解。(0,3)x1x204681021342x1+2x2+d1- = 10 d1- = 65d1-AB(2,2)有無窮多解：點(diǎn)4，0和點(diǎn)0，2連線上的點(diǎn)都是最優(yōu)解。(0,3

20、)(4,0)(0,2)x1x204681021342x1+2x2+d1- = 10 d1- = 75d1-AB(2,2)有無窮多解：點(diǎn)1，1和點(diǎn)0，3/2 3，0連線上的點(diǎn)都是最優(yōu)解。(0,3)(4,0)(1,1)例3 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)x1x2020304050101030402050d1-d1+X1+X2=40 x1x2020304050101030402050d1

21、-d1+d2+d2-X1+X2=50 x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30 x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30 x1x2020304050101030402050d1+d2+d2-d3-d4-Min d1- = 0可行域如圖x1x2020304050101030402050d1+d2-d3-d4-Min d2+ =0可行域如圖x1x2020304050101030402050d1+d2-d4-Min d3- = 0 線段AB是可行域ABx1x2020304050101030402

22、050d2-d4-Min d1+ = 0P=(30,10)獨(dú)一最優(yōu)解。 d2- =10 d4- = 20P例4 Min S=P1d1-+P2d2+ P3d3-+ P3d4- 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)x1x20101520255515201025d1+d1-5X1+10X2=100 x1x20101520255515201025d1+d1-d2+d2-2X1 +X2 =14x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1 =6x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10 x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Min d1- = 0 x1x20101520255