第四章多目標(biāo)規(guī)劃(運(yùn)籌學(xué)上海電力學(xué)院)

第四章多目的規(guī)劃同時(shí)思索多個(gè)決策目的時(shí)，稱(chēng)為多目的規(guī)劃問(wèn)題。4-0引言從線性規(guī)劃問(wèn)題可看出：線性規(guī)劃只研討在滿足一定條件下，單一目的函數(shù)獲得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目的決策問(wèn)題，如擬訂消費(fèi)方案時(shí)，不僅思索總產(chǎn)值，同時(shí)要思索利潤(rùn)，產(chǎn)質(zhì)量量和設(shè)備利用率等。這些目的之間的重要程度〔即優(yōu)先順序〕也不一樣，有些目的之間往往相互發(fā)生矛盾。線性規(guī)劃努力于某個(gè)目的函數(shù)的最優(yōu)解，這個(gè)最優(yōu)解假設(shè)是超越了實(shí)踐的需求，很能夠是以過(guò)分地耗費(fèi)了約束條件中的某些資源作為代價(jià)。線性規(guī)劃把各個(gè)約束條件的重要性都不分主次地等同對(duì)待，這也不符合實(shí)踐情況。求解線性規(guī)劃問(wèn)題，首先要求約束條件必需相容，假設(shè)約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問(wèn)題的可行解，但消費(fèi)還得繼續(xù)進(jìn)展，這將給人們進(jìn)一步運(yùn)用線性規(guī)劃方法帶來(lái)困難。為了彌補(bǔ)線性規(guī)劃問(wèn)題的局限性，處理有限資源和方案目的之間的矛盾，在線性規(guī)劃根底上，建立目的規(guī)劃方法，從而使一些線性規(guī)劃無(wú)法處理的問(wèn)題得到稱(chēng)心的解答。4-1多目的規(guī)劃問(wèn)題多目的規(guī)劃問(wèn)題的提出在實(shí)踐問(wèn)題中，能夠會(huì)同時(shí)思索幾個(gè)方面都到達(dá)最優(yōu)：產(chǎn)量最高，本錢(qián)最低，質(zhì)量最好，利潤(rùn)最大，環(huán)境達(dá)標(biāo)，運(yùn)輸滿足等。多目的規(guī)劃能更好地兼顧統(tǒng)籌處置多種目的的關(guān)系，求得更切合實(shí)踐要求的解。目的規(guī)劃可根據(jù)實(shí)踐情況，分主次地、輕重緩急地思索問(wèn)題。例4-1：一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤(rùn)也不一樣〔如下表〕。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤(rùn)到達(dá)最大？如何安排消費(fèi)，使利潤(rùn)到達(dá)最大。用單純形法求得最優(yōu)解=〔20，20〕最優(yōu)值=200〔百元〕問(wèn)題：該廠提出如下目的〔1〕利潤(rùn)到達(dá)280百元；〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；如何安排消費(fèi)？例4-2：某車(chē)間有A、B兩條設(shè)備一樣的消費(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)量的比例確定重要性。例4-3：某電器公司運(yùn)營(yíng)的唱機(jī)和錄音機(jī)均有車(chē)間A、B流水作業(yè)組裝。數(shù)據(jù)見(jiàn)下表。要求按以下目的制定月消費(fèi)方案：〔1〕庫(kù)存費(fèi)用不超越4600元；〔2〕每月銷(xiāo)售唱機(jī)不少于80臺(tái)；〔3〕不使A、B車(chē)間停工〔權(quán)數(shù)由消費(fèi)費(fèi)用確定〕；〔4〕A車(chē)間加班時(shí)間限制在20小時(shí)內(nèi)；〔5〕每月銷(xiāo)售錄音機(jī)為100臺(tái)；〔6〕兩車(chē)間加班時(shí)數(shù)總和要盡能夠小〔權(quán)數(shù)由消費(fèi)費(fèi)用確定〕；多目的優(yōu)先級(jí)先將目的等級(jí)化：將目的按重要性的程度不同依次分成一級(jí)目的、二級(jí)目的…..。最次要的目的放在次要的等級(jí)中。目的優(yōu)先級(jí)作如下商定：對(duì)同一個(gè)目的而言，假設(shè)有幾個(gè)決策方案都能使其到達(dá)，可以為這些方案就這個(gè)目的而言都是最優(yōu)方案；假設(shè)達(dá)不到，那么與目的差距越小的越好。目的優(yōu)先級(jí)作如下商定：不同級(jí)別的目的的重要性是不可比的。即較高級(jí)別的目的沒(méi)有到達(dá)的損失，任何較低級(jí)別的目的上的收獲都不可彌補(bǔ)。所以在判別最優(yōu)方案時(shí)，首先從較高級(jí)別的目的到達(dá)的程度來(lái)決策，然后再其次級(jí)目的的判別。目的優(yōu)先級(jí)作如下商定：同一級(jí)別的目的可以是多個(gè)。各自之間的重要程度可用數(shù)量〔權(quán)數(shù)〕來(lái)描畫(huà)。因此，同一級(jí)別的目的的其中一個(gè)的損失，可有其他目的的適當(dāng)收獲來(lái)彌補(bǔ)。多目的規(guī)劃解的概念：假設(shè)多目的規(guī)劃問(wèn)題的解能使一切的目的都到達(dá)，就稱(chēng)該解為多目的規(guī)劃的最優(yōu)解；多目的規(guī)劃解的概念：假設(shè)多目的規(guī)劃問(wèn)題的解能使一切的目的都到達(dá)，就稱(chēng)該解為多目的規(guī)劃的最優(yōu)解；假設(shè)解只能滿足部分目的，就稱(chēng)該解為多目的規(guī)劃的次優(yōu)解；多目的規(guī)劃解的概念：假設(shè)多目的規(guī)劃問(wèn)題的解能使一切的目的都到達(dá)，就稱(chēng)該解為多目的規(guī)劃的最優(yōu)解；假設(shè)解只能滿足部分目的，就稱(chēng)該解為多目的規(guī)劃的次優(yōu)解；假設(shè)找不到滿足任何一個(gè)目的的解，就稱(chēng)該問(wèn)題為無(wú)解。例4-4：〔例4-1〕一個(gè)企業(yè)需求同一種原資料消費(fèi)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需求的原資料的數(shù)量及所耗費(fèi)的加工時(shí)間各不一樣，從而獲得的利潤(rùn)也不一樣〔如下表〕。那么，該企業(yè)應(yīng)如何安排消費(fèi)方案，才干使獲得的利潤(rùn)到達(dá)最大？如何安排消費(fèi)，使利潤(rùn)到達(dá)最大。前面曾經(jīng)求得最優(yōu)解=〔20，20〕最優(yōu)值=200〔百元〕問(wèn)題：該廠提出如下目的〔1〕利潤(rùn)到達(dá)280百元；〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；如何安排消費(fèi)？對(duì)例4-1的問(wèn)題，設(shè)超越一噸鋼材與超越5個(gè)工時(shí)的損失一樣?，F(xiàn)有四個(gè)方案進(jìn)展比較優(yōu)劣？目的：〔1〕利潤(rùn)到達(dá)280百元；〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；對(duì)于〔1〕，只需方案4沒(méi)有完成。排除方案4。對(duì)于〔2〕，只需方案2到達(dá)了，因此方案2是最優(yōu)。目的：〔1〕利潤(rùn)到達(dá)280百元；〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；方案1與方案3都到達(dá)了〔1〕，又沒(méi)到達(dá)〔2〕方案1與〔2〕的差距：工時(shí)損失=〔110-100〕*5+〔130-120〕*1=60方案3與〔2〕的差距：工時(shí)損失=0*5+〔190-120〕*1=70方案1優(yōu)于方案3。方案2優(yōu)于方案1優(yōu)于方案3優(yōu)于方案4例4-4：繼續(xù)上例目的：〔1〕利潤(rùn)到達(dá)280百元；〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；對(duì)于〔1〕，三個(gè)方案都沒(méi)有完成。但方案3離目的最遠(yuǎn)，方案3最差。方案1與〔2〕的差距：工時(shí)損失=〔108-100〕*5+〔130-120〕*1=50方案2與〔2〕的差距：工時(shí)損失=0*5+〔160-120〕*1=40方案2優(yōu)于方案1方案2優(yōu)于方案1優(yōu)于方案34-2多目的規(guī)劃問(wèn)題的數(shù)學(xué)模型多目的的處置為了將不同級(jí)別的目的的重要性用數(shù)量表示，引進(jìn)P1，P2，….,用它表示一級(jí)目的，二級(jí)目的，….，的重要程度，規(guī)定P1>P2>P3>….。稱(chēng)P1，P2，….,為級(jí)別系數(shù)。約束方程的處置差別變量：決策變量x超越目的值b的部分記d+決策變量x缺乏目的值b的部分記d-d+0,d-0且x-d++d-=b多目的的綜合假設(shè)決策目的中規(guī)定xb,當(dāng)d+=0時(shí)目的才算到達(dá)。多目的的綜合假設(shè)決策目的中規(guī)定xb,當(dāng)y+=0時(shí)目的才算到達(dá)。假設(shè)決策目的中規(guī)定xb,當(dāng)d-=0時(shí)目的才算到達(dá)。多目的的綜合假設(shè)決策目的中規(guī)定xb,當(dāng)y+=0時(shí)目的才算到達(dá)。假設(shè)決策目的中規(guī)定xb,當(dāng)y-=0時(shí)目的才算到達(dá)。假設(shè)決策目的中規(guī)定x=b,當(dāng)d+=d-=0時(shí)目的才算到達(dá)。例4-5〔例4-4)解：引進(jìn)級(jí)別系數(shù)P1：〔1〕利潤(rùn)到達(dá)280百元；P2：〔2〕鋼材不超越100噸，工時(shí)不超越120小時(shí)；〔權(quán)數(shù)之比5：1〕數(shù)學(xué)模型：目的函數(shù)：MinS=P1d1-+P2(5d2++d3+)約束方程：6X1+4X2+d1--d1+=2802X1+3X2+d2--d2+=1004X1+2X2+d3--d3+=120X1,X2,di-,di+0(i=1,2,3)例4-6〔例4-2)某車(chē)間有A、B兩條設(shè)備一樣的消費(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ù)：MinS=P1d1-+P2d2++4P3d3-+3P3d4-約束方程：2X1+1.5X2+d1--d1+=210〔消費(fèi)量到達(dá)210件/周〕X1+d2--d2+=60〔A消費(fèi)線加班時(shí)間限制在15小時(shí)內(nèi)〕

X1+d3--d3+=45〔充分利用A的工時(shí)目的〕X2+d4--d4+=45〔充分利用B的工時(shí)目的〕X1,X2,di-,di+0(i=1,2,3,4)A，B的產(chǎn)量比例2：1.5=4:3目的函數(shù)：MinS=P1d1-+P2d2++4P3d3-+3P3d4-約束方程：2X1+1.5X2+d1--d1+=210X1+d2--d2+=60X1+d3--d3+=45X2+d4--d4+=45X1,X2,di-,di+0(i=1,2,3,4)例4-7(例4-3)：(1)庫(kù)存費(fèi)用不超越4600元；(2)每月銷(xiāo)售唱機(jī)不少于80臺(tái)；(3)不使A、B車(chē)間停工〔權(quán)數(shù)由消費(fèi)費(fèi)用確定〕；(4)A車(chē)間加班時(shí)間限制在20小時(shí)內(nèi)；〔5〕每月銷(xiāo)售錄音機(jī)為100臺(tái)；〔6〕兩車(chē)間加班時(shí)數(shù)總和要盡能夠小〔權(quán)數(shù)由消費(fèi)費(fèi)用確定〕；解：設(shè)每月消費(fèi)唱機(jī)、錄音機(jī)X1，X2臺(tái)。且A、B的消費(fèi)費(fèi)用之比為100：50=2：1目的函數(shù)：MinS=P1d1++P2d2-+2P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+約束方程：50X1+30X2+d1--d1+=4600〔庫(kù)存費(fèi)用不超越4600元〕X1+d2--d2+=80〔每月銷(xiāo)售唱機(jī)不少于80臺(tái)〕X2+d3--d3+=100〔每月銷(xiāo)售錄音機(jī)為100臺(tái)〕2X1+X2+d4--d4+=180〔不使A車(chē)間停工〕X1+3X2+d5--d5+=200〔不使B車(chē)間停工〕d4++d41--d41+=20〔A車(chē)間加班時(shí)間限制在20小時(shí)內(nèi)〕X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)目的函數(shù)：MinS=P1d1++P2d2-+2P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+約束方程：50X1+30X2+d1--d1+=4600X1+d2--d2+=80X2+d3--d3+=1002X1+X2+d4--d4+=180X1+3X2+d5--d5+=200d4++d41--d41+=20X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)4-3多目的規(guī)劃問(wèn)題的求解多目的規(guī)劃問(wèn)題的圖解法例4-8MinS=d1+X1+2X2+d1--d1+=10X1+2X26X1+X24X1,X2,d1-,d1+0x1x204681021342X1+2X26x1x204681021342X1+X24x1x204681021342x1x204681021342x1x204681021342x1+2x2=105d1+d1-AB(2,2)x1x204681021342x1+2x2=105d1+d1-AB(2,2)當(dāng)MinS=d1+到達(dá)時(shí)d1+=0x1x204681021342x1+2x2=105d1-AB(2,2)當(dāng)MinS=d1+到達(dá)時(shí)d1+=0x1x204681021342x1+2x2+d1-=10d1-=25d1-AB(2,2)當(dāng)MinS=d1+到達(dá)時(shí)d1+=0x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有無(wú)窮多解：點(diǎn)〔0，3〕和點(diǎn)〔2，2〕連線上的點(diǎn)都是最優(yōu)解。(0,3)x1x204681021342x1+2x2+d1-=10d1-=65d1-AB(2,2)有無(wú)窮多解：點(diǎn)〔4，0〕和點(diǎn)〔0，2〕連線上的點(diǎn)都是最優(yōu)解。(0,3)(4,0)(0,2)x1x204681021342x1+2x2+d1-=10d1-=75d1-AB(2,2)有無(wú)窮多解：點(diǎn)〔1，1〕和點(diǎn)〔0，3/2〕〔3，0〕連線上的點(diǎn)都是最優(yōu)解。(0,3)(4,0)(1,1)例4-9MinS=P1d1-+P2d2++5P3d3-+P3d1+X1+X2+d1--d1+=40X1+X2+d2--d2+=50X1+d3-=30X2+d4-=30X1,X2,dI-,dI+0(I=1,2,3,4)x1x2020304050101030402050d1-d1+X1+X2=40x1x2020304050101030402050d1-d1+d2+d2-X1+X2=50x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30x1x2020304050101030402050d1+d2+d2-d3-d4-Mind1-=0可行域如圖x1x2020304050101030402050d1+d2-d3-d4-Mind2+=0可行域如圖x1x2020304050101030402050d1+d2-d4-Mind3-=0線段AB是可行域ABx1x2020304050101030402050d2-d4-Mind1+=0P=(30,10)獨(dú)一最優(yōu)解。d2-=10d4-=20P例4-10MinS=P1d1-+P2d2++P3d3-+P3d4-5X1+10X2+d1--d1+=1002X1+X2+d2--d2+=14X1+d3--d3+=6X2+d4--d4+=10X1,X2,di-,di+0(i=1,2,3,4)x1x20101520255515201025d1+d1-5X1+10X2=100x1x20101520255515201025d1+d1-d2+d2-2X1+X2=14x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1=6x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Mind1-=0x1x20101520255515201025d1+d2-d3+d3-d4+d4-Mind2+=0可行域如圖x1x20101520255515201025d1+d2-d3+d4+d4-Mind3-=0可行域?yàn)榭杖鐖Dx1x20101520255515201025d1+d2-d3+d4+Mind3-0Mind4-=0可行域如圖d3-(2,10)x1x20101520255515201025d1+d2-d3+d4+