第四章目標規(guī)劃

第四章目標規(guī)劃第一頁，共七十六頁，編輯于2023年，星期五第二頁，共七十六頁，編輯于2023年，星期五第三頁，共七十六頁，編輯于2023年，星期五第四頁，共七十六頁，編輯于2023年，星期五第五頁，共七十六頁，編輯于2023年，星期五線性規(guī)劃把各個約束條件的重要性都不分主次地等同看待，這也不符合實際情況。求解線性規(guī)劃問題，首先要求約束條件必須相容，如果約束條件中，由于人力，設(shè)備等資源條件的限制，使約束條件之間出現(xiàn)了矛盾，就得不到問題的可行解，但生產(chǎn)還得繼續(xù)進行，這將給人們進一步應(yīng)用線性規(guī)劃方法帶來困難。為了彌補線性規(guī)劃問題的局限性，解決有限資源和計劃指標之間的矛盾，在線性規(guī)劃基礎(chǔ)上，建立目標規(guī)劃方法，從而使一些線性規(guī)劃無法解決的問題得到滿意的解答。第六頁，共七十六頁，編輯于2023年，星期五第一節(jié)目標規(guī)劃問題一、目標規(guī)劃問題的提出

在實際問題中，可能會同時考慮幾個方面都達到最優(yōu)：產(chǎn)量最高，成本最低，質(zhì)量最好，利潤最大，環(huán)境達標，運輸滿足等。多目標規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標的關(guān)系，求得更切合實際要求的解。目標規(guī)劃可根據(jù)實際情況，分主次地、輕重緩急地考慮問題。第七頁，共七十六頁，編輯于2023年，星期五例1

某公司分廠用一條生產(chǎn)線生產(chǎn)兩種產(chǎn)品A和B，每周生產(chǎn)線運行時間為60小時，生產(chǎn)一臺A產(chǎn)品需要4小時，生產(chǎn)一臺B產(chǎn)品需要6小時．根據(jù)市場預(yù)測，A、B產(chǎn)品平均銷售量分別為每周9、8臺，它們銷售利潤分別為12、18萬元。在制定生產(chǎn)計劃時，經(jīng)理考慮下述4項目標：

(1)產(chǎn)量不能超過市場預(yù)測的銷售量；

(2)工人加班時間最少；

(3)希望總利潤最大；

(4)要盡可能滿足市場需求,當不能滿足時,市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍。試建立這個問題的數(shù)學(xué)模型．第八頁，共七十六頁，編輯于2023年，星期五若把總利潤最大看作目標，而把產(chǎn)量不能超過市場預(yù)測的銷售量、工人加班時間最少和要盡可能滿足市場需求的目標看作約束，則可建立一個單目標線性規(guī)劃模型：

設(shè)決策變量

x1，x2分別為產(chǎn)品A,B的產(chǎn)量，

MaxZ=12x1+18x2

第九頁，共七十六頁，編輯于2023年，星期五容易求得上述線性規(guī)劃的最優(yōu)解為(9,4)T

到(3,8)T

所在線段上的點，最優(yōu)目標值為Z*=180，即可選方案有多種。在實際上，這個結(jié)果并非完全符合決策者的要求，它只實現(xiàn)了經(jīng)理的第一、二、三條目標，而沒有達到最后的一個目標。進一步分析可知，要實現(xiàn)全體目標是不可能的。第十頁，共七十六頁，編輯于2023年，星期五

例2

一家具制造企業(yè)，主要生產(chǎn)桌子、椅子兩種家具，其經(jīng)營環(huán)境主要受到兩種資源——木工和油漆工每天的有效工作時間的限制。企業(yè)過去的經(jīng)營環(huán)境條件如下：(1)每天木工和油漆工的總有效工作時間分別為11小時和10小時。(2)每生產(chǎn)一把椅子需要2小時的木工、1小時的油漆工。(3)每生產(chǎn)一張桌子需要1小時的木工、2小時的油漆工。第十一頁，共七十六頁，編輯于2023年，星期五(4)每生產(chǎn)一把椅子和一張桌子分別可獲利潤8元、10元。求解此線性規(guī)劃問題可以得到最優(yōu)方案：每天生產(chǎn)椅子4把，桌子3張，獲最大利潤62元。企業(yè)過去一直以如何計劃兩種家具的生產(chǎn)量才能獲得最大總利潤為其生產(chǎn)、經(jīng)營的唯一目標。然而，市場經(jīng)濟環(huán)境下新的問題出現(xiàn)了，它迫使企業(yè)不得不考慮…...第十二頁，共七十六頁，編輯于2023年，星期五（1）首先，根據(jù)市場信息，椅子的銷售量已有下降的趨勢，故應(yīng)果斷決策減少椅子的產(chǎn)量，其產(chǎn)量最好不大于桌子的產(chǎn)量。（2）其次，市場上找不到符合生產(chǎn)質(zhì)量要求的木工了，因此決不可能考慮增加木工這種資源來增加產(chǎn)量，并且由于某種原因木工決不可能加班。（3）再其次，應(yīng)盡可能充分利用油漆工的有效工作時間，但油漆工希望最好不加班。（4）最后，企業(yè)考慮最好達到并超過預(yù)計利潤指標56元。第十三頁，共七十六頁，編輯于2023年，星期五

二、目標規(guī)劃模型的基本概念把例1的4個目標表示為不等式，仍設(shè)決策變量x1，x2

分別為產(chǎn)品A，B的產(chǎn)量。那么，第一個目標為:x1

≤9，x2

≤

8；第二個目標為:4x1+6x2

≤

60；第三個目標為:希望總利潤最大，要表示成不等式需要找到一個目標上界，這里可以估計為252（=129+188），于是有

12x1

+18x2≥252；第四個目標為:x1≥9，x2≥8；第十四頁，共七十六頁，編輯于2023年，星期五下面引入與建立目標規(guī)劃數(shù)學(xué)模型有關(guān)的概念1．正、負偏差變量d

+，d-

我們用正偏差變量d

+

表示決策值超過目標值的部分；負偏差變量d-

表示決策值不足目標值的部分。因決策值不可能既超過目標值同時又末達到目標值，故恒有d

+

d-

＝0。2．絕對約束和目標約束我們把所有等式、不等式約束分為兩部分：絕對約束和目標約束。絕對約束是指必須嚴格滿足的等式約束和不等式約束；如在線性規(guī)劃問題中考慮的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。如例1中生產(chǎn)A，B產(chǎn)品所需原材料數(shù)量有限制，并且無法從其它渠道予以補充，則構(gòu)成絕對約束。第十五頁，共七十六頁，編輯于2023年，星期五目標約束是目標規(guī)劃特有的，目標約束具有更大的彈性，我們可以把約束右端項看作要努力追求的目標值，但允許結(jié)果與所制定的目標值存在正或負的偏差，用在約束中加入正、負偏差變量來表示，于是稱它們是軟約束。對于例1，我們有如下目標約束

x1

+d1--d1+=9(4.1)

x2+d2--d2+=8(4.2)4x1+6x2+d3--d3+=60(4.3)12x1+18x2+d4--d4+=252(4.4)第十六頁，共七十六頁，編輯于2023年，星期五3．優(yōu)先因子與權(quán)系數(shù)．對于多目標問題，決策者在要求達到這些目標是，是有主次或輕重緩急的不同。多個目標之間有相互沖突時，決策者首先必須對目標排序。設(shè)置各目標的優(yōu)先因子，依據(jù)優(yōu)先因子的大小確定目標順序。要求第一位達到的目標賦予優(yōu)先因子P1，次位的目標賦予優(yōu)先因子P2，…，并規(guī)定Pk>>Pk+1，k=1,2,…，K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。即首先保證P1級目標的實現(xiàn)，這時可不考慮次級目標；而P2級目標是在實現(xiàn)P1級目標的基礎(chǔ)上考慮的；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個目標的差別，這時可分別賦予它們不同的權(quán)系數(shù)ωj，這些都由決策者按具體情況而定。第十七頁，共七十六頁，編輯于2023年，星期五4．目標規(guī)劃的目標函數(shù)．目標規(guī)劃的目標函數(shù)是通過各目標約束的正、負偏差變量和賦于相應(yīng)的優(yōu)先等級來構(gòu)造的。當每一目標值確定后，決策者的要求是盡可能從某個方向縮小偏離目標的數(shù)值。于是，目標規(guī)劃的目標函數(shù)應(yīng)該是求極?。簃inf＝f（d

+，d-)。其基本形式有三種：（1）要求恰好達到目標值，即使相應(yīng)目標約束的正、負偏差變量都要盡可能地小。這時取min（d

++d-)；（2）要求不超過目標值，即使相應(yīng)目標約束的正偏差變量要盡可能地小。這時取min（d

+)；（3）要求不低于目標值，即使相應(yīng)目標約束的負偏差變量要盡可能地小。這時取min（d

-)；第十八頁，共七十六頁，編輯于2023年，星期五目標規(guī)劃的目標函數(shù)中包含了多個目標，決策者對于具有相同重要性的目標可以合并為一個目標，如果同一目標中還想分出先后次序，可以賦予不同的權(quán)系數(shù)，按系數(shù)大小再排序。對于例1,我們根據(jù)決策者的考慮知第一優(yōu)先級要求min（d1++d2+)；第二優(yōu)先級要求min（d3+)；第三優(yōu)先級要求min（d4-

）；第四優(yōu)先級要求min（d1-+2d2-

），這里，當不能滿足市場需求時，市場認為B產(chǎn)品的重要性是A產(chǎn)品的2倍．即減少B產(chǎn)品的影響是A產(chǎn)品的2倍，因此我們引入了2:1的權(quán)系數(shù)。第十九頁，共七十六頁，編輯于2023年，星期五綜合上述分析，我們可得到下列目標規(guī)劃模型:

Minf=P1（d1++d2+)+P2

d3++P3

d4-+P4（d1-+2d2-)

(4.5)第二十頁，共七十六頁，編輯于2023年，星期五三、目標規(guī)劃模型的一般形式根據(jù)上面討論,我們可以得到目標規(guī)劃的一般形式如下第二十一頁，共七十六頁，編輯于2023年，星期五例3：某車間有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)量的比例確定重要性。建立目標規(guī)劃的數(shù)學(xué)模型時，需要確定目標值、優(yōu)先等級、權(quán)系數(shù)等，它都具有一定的主觀性和模糊性，可以用專家評定法給以量化。第二十二頁，共七十六頁，編輯于2023年，星期五解：設(shè)A，B生產(chǎn)線每周工作時間為X1，X2。A，B的產(chǎn)量比例2：1.5=4:3目標函數(shù)：MinS=P1d1-+P2d2++4

P3d3-+3P3d4-約束方程：2X1+1.5X2+d1--d1+=210

（生產(chǎn)量達到210件/周）

X1+d2--d2+=60（A生產(chǎn)線加班時間限制在15小時內(nèi)）

第二十三頁，共七十六頁，編輯于2023年，星期五

X1+d3--d3+=45

（充分利用A的工時指標）

X2+d4--d4+=45

（充分利用B的工時指標）

X1,X2,di-,di+0(i=1,2,3,4)第二十四頁，共七十六頁，編輯于2023年，星期五A，B的產(chǎn)量比例2：1.5=4:3目標函數(shù)：

MinS=P1d1-+P2d2++4

P3d3-+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)第二十五頁，共七十六頁，編輯于2023年，星期五例4：某電器公司經(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)費用確定）；第二十六頁，共七十六頁，編輯于2023年，星期五第二十七頁，共七十六頁，編輯于2023年，星期五解：設(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臺）第二十八頁，共七十六頁，編輯于2023年，星期五

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)第二十九頁，共七十六頁，編輯于2023年，星期五目標函數(shù)：MinS=P1d1++P2d2-+2

P3d4-+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)第三十頁，共七十六頁，編輯于2023年，星期五例5．某單位領(lǐng)導(dǎo)在考慮本單位職工的升級調(diào)資方案時，依次遵守以下規(guī)定：(1)不超過年工資總額60000元；(2)每級的人數(shù)不超過定編規(guī)定的人數(shù)；(3)Ⅱ，Ⅲ級的升級面盡可能達到現(xiàn)有人數(shù)的20%，且無越級提升；(4)Ⅲ級不足編制的人數(shù)可錄用新職工，又Ⅰ級的職工中有10%要退休。有關(guān)資料匯總于表4.1中，問該領(lǐng)導(dǎo)應(yīng)如何擬訂一個滿意的方案。第三十一頁，共七十六頁，編輯于2023年，星期五表4.1等級工資額(元/年)現(xiàn)有人數(shù)編制人數(shù)ⅠⅡⅢ200015001000101215121515合計3742解：設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級和錄用到Ⅲ級的新職工人數(shù)。對各目標確定的優(yōu)先因子為：P1——不超過年工資總額60000元；P2——每級的人數(shù)不超過定編規(guī)定的人數(shù)；P3——Ⅱ、Ⅲ級的升級面盡可能達到現(xiàn)有人數(shù)的20%。第三十二頁，共七十六頁，編輯于2023年，星期五先分別建立各目標約束。

年工資總額不超過60000元：2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1--d1+

=60000每級的人數(shù)不超過定編規(guī)定的人數(shù)：對Ⅰ級有10(1-0.1)+x1+

d2--d2+

=12對Ⅱ級有12-x1+x2+

d3--d3+=15對Ⅲ級有15-x2+x3+

d4--d4+=15Ⅱ，Ⅲ級的升級面不大于現(xiàn)有人數(shù)的20%，但盡可能多提；對Ⅱ級有x1+

d5-

-d5+

=12×0.2對Ⅲ級有x2+

d6-

-

d6+

=15×0.2目標函數(shù)：minz=P1

d1+

+P2(d2+

+

d3++

d4+)+P3(d5-+

d6-)第三十三頁，共七十六頁，編輯于2023年，星期五第二節(jié)目標規(guī)劃的圖解法對只具有兩個決策變量的目標規(guī)劃的數(shù)學(xué)模型，我們可以用圖解法來分析求解。通過圖解示例，可以看到目標規(guī)劃中優(yōu)先因子，正、負偏差變量及權(quán)系數(shù)等的幾何意義。例6MinS=d1+X1+2X2+d1--d1+=10X1+2X26X1+X24X1,X2,d1-,d1+0第三十四頁，共七十六頁，編輯于2023年，星期五x1x204681021342X1+2X26第三十五頁，共七十六頁，編輯于2023年，星期五x1x204681021342X1+X24第三十六頁，共七十六頁，編輯于2023年，星期五x1x204681021342第三十七頁，共七十六頁，編輯于2023年，星期五x1x204681021342第三十八頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2=105d1+d1-AB(2,2)第三十九頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2=105d1+d1-AB(2,2)當MinS=d1+達到時d1+=0第四十頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2=105d1-AB(2,2)當MinS=d1+達到時d1+=0第四十一頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2+d1-=10d1-=25d1-AB(2,2)當MinS=d1+達到時d1+=0第四十二頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有無窮多解：點（0，3）和點（2，2）連線上的點都是最優(yōu)解。(0,3)第四十三頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2+d1-=10d1-=65d1-AB(2,2)有無窮多解：點（4，0）和點（0，2）連線上的點都是最優(yōu)解。(0,3)(4,0)(0,2)第四十四頁，共七十六頁，編輯于2023年，星期五x1x204681021342x1+2x2+d1-=10d1-=75d1-AB(2,2)有無窮多解：點（1，1）和點（0，3/2）（3，0）連線上的點都是最優(yōu)解。(0,3)(4,0)(1,1)第四十五頁，共七十六頁，編輯于2023年，星期五例4-9

MinS=P1d1-+P2d2++5

P3d3-+P3d1+X1+X2+d1--d1+=40X1+X2+d2--d2+=50X1+d3-=

30X2+d4-=

30X1,X2,dI-,dI+0(I=1,2,3,4)第四十六頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1-d1+X1+X2=40第四十七頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1-d1+d2+d2-X1+X2=50第四十八頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30第四十九頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30第五十頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d2+d2-d3-d4-Mind1-=0可行域如圖第五十一頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d2-d3-d4-Mind2+=0可行域如圖第五十二頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d2-d4-Mind3-=0線段AB是可行域AB第五十三頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d2-d4-Mind1+=0P=(30,10)唯一最優(yōu)解。

d2-=10

d4-=20P第五十四頁，共七十六頁，編輯于2023年，星期五例4-10

MinS=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)第五十五頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d1-5X1+10X2=100第五十六頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d1-d2+d2-2X1+X2=14第五十七頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1=6第五十八頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10第五十九頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Mind1-=0第六十頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d2-d3+d3-d4+d4-Mind2+=0可行域如圖第六十一頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d2-d3+d4+d4-Mind3-=0可行域為空如圖第六十二頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d2-d3+d4+Mind3-0Mind4-=0可行域如圖d3-(2,10)第六十三頁，共七十六頁，編輯于2023年，星期五x1x20101520255515201025d1+d2-d3+d4+Mind3-=0Mind4-0可行域為空如圖d4-第六十四頁，共七十六頁，編輯于2023年，星期五對于目標P1與目標P2很容易達到。目標P3的兩個指標不能同時滿足，否則無解。又因為P3中的兩個目標同樣重要，要討論（1）Mind3-=0Mind4-0原問題無解。（2）Mind3-0Mind4-=0原問題(2,10)是次優(yōu)解。第六十五頁，共七十六頁，編輯于2023年，星期五例4-11

MinS=P1d1-+P1d2-X1+d1--d1+=154X1+5X2+d2--d2+=2003X1+4X2120X1-2X215X1,X2,di-,di+0(i=1,2)第六十六頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d1-X1=15第六十七頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d1-d2+d2-4X1+5X2=200第六十八頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d1-d2+d2-3X1+4X2120第六十九頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d1-d2+d2-X1-2X2

15第七十頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d1-d2+d2-第七十一頁，共七十六頁，編輯于2023年，星期五x1x2020304050101030402050d1+d2+同時考慮d1-=0,d2-=0

原問題無解。第七十二頁，共七十六頁，編輯于2023年，星期五例6．已知有三個產(chǎn)地給四個銷地供應(yīng)某種產(chǎn)品，產(chǎn)銷地之間的供需量和單位運價見表4.2。有關(guān)部門在研究調(diào)運方案時依次考慮以下七項目標，并規(guī)定其相應(yīng)的優(yōu)先等級：P1—B4是重點保證單位，必須全部滿足其需要；P2—A3向B1提供的產(chǎn)量不少于100；P3—每個銷地的供應(yīng)量不小于其需要量的80%；P4—所定調(diào)運方案的總運費不超過最小運費調(diào)運方案的10%；P5—因路段的問題，盡量避免安排將A2的產(chǎn)品往B4；P6—給B1和B3的供應(yīng)率要相同；P7——力求總運費最省。建立目標規(guī)劃模型。第七十三頁，共七十六頁，編輯于2023年，星期五表4.2銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A353