第四章多目標規(guī)劃,同時考慮多個決策目標時，稱為多目標規(guī)劃問題。,4-0引言從線性規(guī)劃問題可看出：線性規(guī)劃只研究在滿足一定條件下，單一目標函數(shù)取得最優(yōu)解，而在企業(yè)管理中，經(jīng)常遇到多目標決策問題，如擬訂生產(chǎn)計劃時，不僅考慮總產(chǎn)值，同時要考慮利潤，產(chǎn)品質(zhì)量和設(shè)備利用率等。這些指標之間的重要程度（即優(yōu)先順序）也不相同，有些目標之間往往相互發(fā)生矛盾。,線性規(guī)劃致力于某個目標函數(shù)的最優(yōu)解，這個最優(yōu)解若是超過了實際的需要，很可能是以過分地消耗了約束條件中的某些資源作為代價。線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。,求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進行，這將給人們進一步應(yīng)用線性規(guī)劃方法帶來困難。,為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。,4-1多目標規(guī)劃問題多目標規(guī)劃問題的提出在實際問題中，可能會同時考慮幾個方面都達到最優(yōu)：產(chǎn)量最高，成本最低，質(zhì)量最好，利潤最大，環(huán)境達標，運輸滿足等。多目標規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標的關(guān)系，求得更切合實際要求的解。目標規(guī)劃可根據(jù)實際情況，分主次地、輕重緩急地考慮問題。,例4-1：一個企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達到最大？,如何安排生產(chǎn)，使利潤達到最大。用單純形法求得最優(yōu)解=（20，20）最優(yōu)值=200（百元）,問題：該廠提出如下目標（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；如何安排生產(chǎn)？,例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小時，要求制定完成下列目標的生產(chǎn)計劃：,（1）生產(chǎn)量達到210件/周；（2）A生產(chǎn)線加班時間限制在15小時內(nèi)；（3）充分利用工時指標，并依A、B產(chǎn)量的比例確定重要性。,例4-3：某電器公司經(jīng)營的唱機和錄音機均有車間A、B流水作業(yè)組裝。數(shù)據(jù)見下表。要求按以下目標制訂月生產(chǎn)計劃：（1）庫存費用不超過4600元；（2）每月銷售唱機不少于80臺；,（3）不使A、B車間停工（權(quán)數(shù)由生產(chǎn)費用確定）；（4）A車間加班時間限制在20小時內(nèi)；（5）每月銷售錄音機為100臺；（6）兩車間加班時數(shù)總和要盡可能?。?quán)數(shù)由生產(chǎn)費用確定）；,多目標優(yōu)先級先將目標等級化：將目標按重要性的程度不同依次分成一級目標、二級目標.。最次要的目標放在次要的等級中。,目標優(yōu)先級作如下約定：對同一個目標而言，若有幾個決策方案都能使其達到，可認為這些方案就這個目標而言都是最優(yōu)方案；若達不到，則與目標差距越小的越好。,目標優(yōu)先級作如下約定：不同級別的目標的重要性是不可比的。即較高級別的目標沒有達到的損失，任何較低級別的目標上的收獲都不可彌補。所以在判斷最優(yōu)方案時，首先從較高級別的目標達到的程度來決策，然后再其次級目標的判斷。,目標優(yōu)先級作如下約定：同一級別的目標可以是多個。各自之間的重要程度可用數(shù)量（權(quán)數(shù)）來描述。因此，同一級別的目標的其中一個的損失，可有其余目標的適當收獲來彌補。,多目標規(guī)劃解的概念：若多目標規(guī)劃問題的解能使所有的目標都達到，就稱該解為多目標規(guī)劃的最優(yōu)解；若解只能滿足部分目標，就稱該解為多目標規(guī)劃的次優(yōu)解；若找不到滿足任何一個目標的解，就稱該問題為無解。,例4-4：（例4-1）一個企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費的加工時間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計劃，才能使獲得的利潤達到最大？,如何安排生產(chǎn)，使利潤達到最大。前面已經(jīng)求得最優(yōu)解=（20，20）最優(yōu)值=200（百元）,問題：該廠提出如下目標（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；如何安排生產(chǎn)？,對例4-1的問題，設(shè)超過一噸鋼材與超過5個工時的損失相同。現(xiàn)有四個方案進行比較優(yōu)劣？,目標：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；對于（1），只有方案4沒有完成。排除方案4。對于（2），只有方案2達到了，因此方案2是最優(yōu)。,目標：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；方案1與方案3都達到了（1），又沒達到（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)于方案4,例4-4：繼續(xù)上例,目標：（1）利潤達到280百元；（2）鋼材不超過100噸，工時不超過120小時；對于（1），三個方案都沒有完成。但方案3離目標最遠，方案3最差。方案1與（2）的差距：工時損失=（108-100）*5+（130-120）*1=50,方案2與（2）的差距：工時損失=0*5+（160-120）*1=40方案2優(yōu)于方案1方案2優(yōu)于方案1優(yōu)于方案3,4-2多目標規(guī)劃問題的數(shù)學模型多目標的處理為了將不同級別的目標的重要性用數(shù)量表示，引進P1，P2，.,用它表示一級目標，二級目標，.，的重要程度，規(guī)定P1P2P3.。稱P1，P2，.,為級別系數(shù)。,約束方程的處理差異變量：決策變量x超過目標值b的部分記d+決策變量x不足目標值b的部分記d-d+0,d-0且x-d+d-=b,多目標的綜合若決策目標中規(guī)定xb,當d+=0時目標才算達到。,多目標的綜合若決策目標中規(guī)定xb,當y+=0時目標才算達到。若決策目標中規(guī)定xb,當d-=0時目標才算達到。,多目標的綜合若決策目標中規(guī)定xb,當y+=0時目標才算達到。若決策目標中規(guī)定xb,當y-=0時目標才算達到。若決策目標中規(guī)定x=b,當d+=d-=0時目標才算達到。,例4-5（例4-4)解：引進級別系數(shù)P1：（1）利潤達到280百元；P2：（2）鋼材不超過100噸，工時不超過120小時；（權(quán)數(shù)之比5：1）,數(shù)學模型：目標函數(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)某車間有A、B兩條設(shè)備相同的生產(chǎn)線，它們生產(chǎn)同一種產(chǎn)品。A生產(chǎn)線每小時可制造2件產(chǎn)品，B生產(chǎn)線每小時可制造1.5件產(chǎn)品。如果每周正常工作時數(shù)為45小時，要求制定完成下列目標的生產(chǎn)計劃：,（1）生產(chǎn)量達到210件/周；（2）A生產(chǎn)線加班時間限制在15小時內(nèi)；（3）充分利用工時指標，并依A、B產(chǎn)量的比例確定重要性。,解：設(shè)A，B生產(chǎn)線每周工作時間為X1，X2。A，B的產(chǎn)量比例2：1.5=4:3目標函數(shù)：MinS=P1d1-+P2d2+4P3d3-+3P3d4-約束方程：2X1+1.5X2+d1-d1+=210（生產(chǎn)量達到210件/周）X1+d2-d2+=60（A生產(chǎn)線加班時間限制在15小時內(nèi)）,X1+d3-d3+=45（充分利用A的工時指標）X2+d4-d4+=45（充分利用B的工時指標）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)庫存費用不超過4600元；(2)每月銷售唱機不少于80臺；(3)不使A、B車間停工（權(quán)數(shù)由生產(chǎn)費用確定）；(4)A車間加班時間限制在20小時內(nèi)；,（5）每月銷售錄音機為100臺；（6）兩車間加班時數(shù)總和要盡可能?。?quán)數(shù)由生產(chǎn)費用確定）；解：設(shè)每月生產(chǎn)唱機、錄音機X1，X2臺。且A、B的生產(chǎn)費用之比為100：50=2：1,目標函數(shù)：MinS=P1d1+P2d2-+2P3d4-+P3d5-+P4d41+P5d3-+P5d3+2P6d4+P6d5+約束方程：50X1+30X2+d1-d1+=4600（庫存費用不超過4600元）X1+d2-d2+=80（每月銷售唱機不少于80臺）,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,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ī)劃問題的求解多目標規(guī)劃問題的圖解法例4-8MinS=d1+X1+2X2+d1-d1+=10X1+2X26X1+X24X1,X2,d1-,d1+0,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+2X26,x1,x2,0,4,6,8,10,2,1,3,4,2,X1+X24,x1,x2,0,4,6,8,10,2,1,3,4,2,x1,x2,0,4,6,8,10,2,1,3,4,2,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1+,d1-,A,B,(2,2),當MinS=d1+達到時d1+=0,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2=10,5,d1-,A,B,(2,2),當MinS=d1+達到時d1+=0,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1-=10d1-=2,5,d1-,A,B,(2,2),當MinS=d1+達到時d1+=0,x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1-=10d1-=4,5,d1-,A,B,(2,2),有無窮多解：點（0，3）和點（2，2）連線上的點都是最優(yōu)解。,(0,3),x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1-=10d1-=6,5,d1-,A,B,(2,2),有無窮多解：點（4，0）和點（0，2）連線上的點都是最優(yōu)解。,(0,3),(4,0),(0,2),x1,x2,0,4,6,8,10,2,1,3,4,2,x1+2x2+d1-=10d1-=7,5,d1-,A,B,(2,2),有無窮多解：點（1，1）和點（0，3/2）（3，0）連線上的點都是最優(yōu)解。,(0,3),(4,0),(1,1),例4-9MinS=P1d1-+P2d2+5P3d3-+P3d4-X1+X2+d1-d1+=40X1+X2+d2-d2+=50X1+d3-=30X2+d4-=30X1,X2,dI-,dI+0(I=1,2,3,4),x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,X1+X2=40,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,X1+X2=50,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,X1=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1-,d1+,d2+,d2-,d3-,d4-,X2=30,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2+,d2-,d3-,d4-,Mind1-=0可行域如圖,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d3-,d4-,Mind2+=0可行域如圖,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d1+,d2-,d4-,Mind3-=0線段AB是可行域,A,B,x1,x2,0,20,30,40,50,10,10,30,40,20,50,d2-,d4-,Mind4-P=(30,20)唯一最優(yōu)解。d2-=10d4-=10,P,例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),x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,5X1+10X2=100,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,2X1+X2=14,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,X1=6,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,X2=10,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2+,d2-,d3+,d3-,d4+,d4-,Mind1-=0,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d3-,d4+,d4-,Mind2+=0可行域如圖,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,Mind3-=0可行域為空如圖,x1,x2,0,10,15,20,25,5,5,15,20,10,25,d1+,d2-,d3+,d4+,d4-,Mind3-0,如何使P3（d3-+d4-）最小呢？對于2X1+X2=14來說，x1減少1個單位，x2卻增加2個單位，于是P1為最優(yōu)點。,P1(2,10),P2(26/3,8/3),多目標規(guī)劃的單純形算法多目標規(guī)劃問題與線性規(guī)劃問題相似，可用單純形算法求解。注意：在比較檢驗數(shù)大小時，要先比較較高級別的系數(shù)，再比較較低級別的系數(shù)。,例4-11（例4-6）目標函數(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),標準型目標函數(shù)：MaxS=-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),初始單純形表,首先滿足第一目標P1進基變量X1，出基變量y3-主元（4）,主元運算：第三行除以4,主元運算：第一行加上第三行（-6）倍,主元運算：第二行加上第三行（-2）倍,重新計算檢驗數(shù),第二行除以2,第一行加上第二行（-1）,第三行加上第二行（-1/2）,計算檢驗數(shù),計算檢驗數(shù),第一行乘上4/5,第三行加上第一行（3/8）,計算檢驗數(shù),最后變量y1-的檢驗數(shù)為-P1+(4/5)P2由于假定P1P2，所以此檢驗數(shù)也小于零。,該問題的最優(yōu)方案為生產(chǎn)A產(chǎn)品44個單位，B產(chǎn)品4個單位，利潤為280百元。此時，原料正好用了100噸，工時比原計劃超了64小時。,例4-11設(shè)某工廠生產(chǎn)兩種產(chǎn)品，都要經(jīng)過兩道工序，有關(guān)資料如下表。假如工序1，2都允許加班，使得利潤不少于1000元作為目標。又以：第1，2工序的加班工時之和盡可能在160之內(nèi)為第一目標；產(chǎn)品乙必須嚴格控制在70公斤之內(nèi)為第二目標；該廠的利潤越高越好為第三目標；盡量減少工序1，2加班工時為第四目標.試問：在上述條件下，該廠應(yīng)如何生產(chǎn)？,解：設(shè)X1，X2為甲，乙兩種產(chǎn)品的生產(chǎn)公斤數(shù)，d1-，d1+分別為低于或超過利潤1000元的偏差d2-，d2+分別為第1道工序剩余和加班的工時數(shù)d3-，d3+分別為第2道工序剩余和加班的工時數(shù)d4-，d4+為加班工時之和低于或超過160工時數(shù)由于產(chǎn)品X2必須嚴格控制在70公斤之內(nèi)為第一目標，則可取d5-為實際公斤數(shù)不到70的偏差，且d5+=0。,目標函數(shù)：MinZ=P1d4+P2d5-+P3d1-+P4(d2+d3+)約束方程：6X1+4X2+d1-d1+=10002X1+X2+d2-d2+=100X1+X2+d3-d3+=80d2+d3+d4-d4+=160X2+d5=70X1,X2,di-,di+,d50(i=1,2,3,4),目標函數(shù)：Maxs=-P1d4+-P2d5-P3d1-P4(d2+d3+)約束方程：6X1+4X2+d1-d1+=10002X1+X2+d2-d2+=10