第四章目標規(guī)劃及圖解法運籌學第一頁，共二十九頁，編輯于2023年，星期五例1

產(chǎn)品資源AB限量1車間2車間21.5125040單位利潤80100求利潤最大的生產(chǎn)方案利潤maxz=80x1+100x2約束條件2x1+1.5x2

≤

50x1+2x2

≤

40x1，x2

≥0第二頁，共二十九頁，編輯于2023年，星期五例2由于各種原因，對例1的提出一些要求：

1、B產(chǎn)品不超過10單位

2、利潤不低于1600元

3、充分利用2車間的生產(chǎn)能力，盡量不加班。第三頁，共二十九頁，編輯于2023年，星期五目標的含義本題三個目標依次表示為：

1、B產(chǎn)品不超過10單位

x2<=102、利潤不低于1600元

80x1+100x2>=16003、充分利用2車間的生產(chǎn)能力，盡量不加班。

x1+2x2=40?第四頁，共二十九頁，編輯于2023年，星期五問題分析1）問題中有些限制是必須滿足的，不能有絲毫妥協(xié)余地的，如對資源的約束：

2x1+1.5x2≤50(1)x1+2x2≤40(2)

這些約束條件是一種剛性約束，稱之為

系統(tǒng)約束or絕對約束第五頁，共二十九頁，編輯于2023年，星期五問題分析2）除了前面提到的剛性約束外，例2中還提出一些的希望達到的目標。這些要求實際上也是約束條件，當然這些目標能到達最好，實在無法達到也是可以接受的，我們稱之為目標約束如：1、B產(chǎn)品不超過10單位

2、利潤不低于1600元

3、充分利用2車間的生產(chǎn)能力，盡量不加班。第六頁，共二十九頁，編輯于2023年，星期五問題分析3）目標約束的目標一定要明確，給出確切的量值，即目標期望值B產(chǎn)品不超過10單位利潤不低于1600元

充分利用2車間的生產(chǎn)能力，盡量不加班如：第七頁，共二十九頁，編輯于2023年，星期五問題分析4）目標約束不是剛性的，而是彈性的，允許在一定范圍內(nèi)有偏差，這更接近于實際。為表達這種靈活性，便引入了偏差變量的概念，偏差變量有正負之分，表示為：d+和d-，d+表示超過目標值的部分；

d-表示不足目標值的部分.顯然有d-·d+=0第八頁，共二十九頁，編輯于2023年，星期五問題分析本題三個目標約束依次表示為：

1、B產(chǎn)品不超過10單位

x2+d1-

-d1+=102、利潤不低于1600元

80x1+100x2+d2--d2+

=16003、充分利用2車間的生產(chǎn)能力，盡量不加班。

x1+2x2+d3--d3+=40第九頁，共二十九頁，編輯于2023年，星期五問題分析4）目標的重要程度不同，因此目標的滿足有先有后，即有優(yōu)先級別。設最重要的為P1級，次之者為P2級——優(yōu)先因子

P看成實數(shù)P1>>P2第十頁，共二十九頁，編輯于2023年，星期五問題分析5）有時同級別的目標中，其重要程度又有差別，則設置不同的權(quán)重（系數(shù)W）

。6)x1+2x2

≤

40(系統(tǒng)約束)x1+2x2+d3--d3+=40(目標約束)

當對某個資源約束既是系統(tǒng)約束，又是目標約束時，則不再表示為系統(tǒng)約束第十一頁，共二十九頁，編輯于2023年，星期五問題分析1、B產(chǎn)品不超過10單位d1+越小越好

0最佳2、利潤不低于1600元 d2-越小越好0最好

3、充分利用2車間的生產(chǎn)能力，盡量不加班

d3-

和d3+越小越好7）目標規(guī)劃的目標第十二頁，共二十九頁，編輯于2023年，星期五問題分析7）目標規(guī)劃的目標函數(shù)：目標規(guī)劃有多個目標，我們已經(jīng)把它轉(zhuǎn)化為目標約束，整個問題的目標就是使得實施結(jié)果與目標期望值的偏差最小于是本題目標函數(shù)表示為：

minZ={P1d1+,P2d2-

,P3(d3-+d3+)}第十三頁，共二十九頁，編輯于2023年，星期五問題分析2x1+1.5x2≤50x2+d1--d1+=1080x1+100x2+d2--d2+=1600x1+2x2+d3--d3+=40x1

，x2

，di-，di+≥0,i=1,2,3綜上所述，本題的數(shù)學模型為：目標函數(shù)：minZ={P1d1+,P2d2-

,P3(d3-+d3+)}約束條件第十四頁，共二十九頁，編輯于2023年，星期五目標規(guī)劃的概念及數(shù)學模型數(shù)學模型為：目標函數(shù)minZ={Pl(∑k(Wlk-?dk-+Wlk+

?

dk+))，

l=1,2,…,L}約束條件∑jckjxj+dk--dk+

=bk,k=1,2,…,K∑jaijxj≤(=≥)bi,

i=1,2,…,mxj

，dk-，dk+

≥0,j=1,…n;k=1,2,…,K目標約束系統(tǒng)約束第十五頁，共二十九頁，編輯于2023年，星期五目標規(guī)劃的圖解法例22x1+1.5x2≤50x2+d1--d1+=1080x1+100x2+d2--d2+=1600x1+2x2+d3--d3+=40x1

，x2

，di-，di+≥0,i=1,2,3目標函數(shù)minZ={P1d1+,P2d2-,

P3(d3-+d3+)約束條件3010203040102040Ox1x2d1-d1+圖解法d2+d2-d3+d3-第十六頁，共二十九頁，編輯于2023年，星期五§4.3解目標規(guī)劃的單純形法第十七頁，共二十九頁，編輯于2023年，星期五§4.3解目標規(guī)劃的單純形法

目標規(guī)劃的數(shù)學模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學模型結(jié)構(gòu)沒有本質(zhì)的區(qū)別，所以可用單純形法進行求解。但要考慮目標規(guī)劃數(shù)學模型的一些特點：(1)因目標規(guī)劃問題的目標函數(shù)都是求最小化，所以檢驗數(shù)的最優(yōu)準則與我們前面講到的線性規(guī)劃檢驗準則是相反的，即以所有的σj≥0為最優(yōu)準則；(2)因為非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，且Pi>>Pi+1，i=1,2,,L-1.所以在判斷各檢驗數(shù)大小時得小心；第十八頁，共二十九頁，編輯于2023年，星期五解目標規(guī)劃的單純形法計算步驟

(1)建立初始單純形表，在表中將檢驗數(shù)行按優(yōu)先因子個數(shù)分別列成L行，置k=1。(2)檢查該行中是否存在負數(shù)，且對應的前k-1行的系數(shù)是0。若有，則取其中最小者對應的變量為換入變量，轉(zhuǎn)(3)；否則，轉(zhuǎn)(5)。(3)按最小比值規(guī)則確定換出變量，當存在兩個或兩個以上相同的最小比值時，選取具有較高優(yōu)先級別的變量為換出變量。(4)按單純形法進行基變換運算，建立新的單純形表。(5)當k=L時，計算結(jié)束，表中解即為滿意解。否則置k=k+1，返回(2)。第十九頁，共二十九頁，編輯于2023年，星期五例5用單純形法來解例2

引入松弛變量x3，將例2的目標規(guī)劃中約束條件轉(zhuǎn)換成線性規(guī)劃標準形式，如下：

Min{P1d1-，P2d2+，P3d3-}

s.t.5x1

+10x2+

x3

=60

x1

-2x2

+d1--d1+=0

4x1

+4x2+d2--d2+=36

6x1+8x2

+d3--d3+=48

x1,x2,x3

,di-,di+0,i=1,2,3.

第二十頁，共二十九頁，編輯于2023年，星期五

Minz=P1d1-+P2d2++P3d3-

s.t.5x1

+10x2+

x3

=60

x1

-2x2

+d1--d1+=0

4x1

+4x2+d2--d2+=36

6x1+8x2

+d3--d3+=48

x1,x2,x3

,di-,di+0,i=1,2,3.

該目標規(guī)劃和下面線性規(guī)劃問題等價第二十一頁，共二十九頁，編輯于2023年，星期五C

00

0

P1

0

0

P2

P3

0CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0P10

P3x3d1－d2－d3－60036485101000000

[

1]－201－10000440001－10068000001－1σP1P2P3

－120010000000000100－6－80000001建立初始單純形表第二十二頁，共二十九頁，編輯于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000x3x1d2－x21224/536/512/50011－100－111002/5－2/5001/10－1/10000－2/52/51－1－3/53/5010－3/103/10001/20－1/20σP1P2P3000100000000000100000000010最終單純形表最優(yōu)解X1=（24/5，12/5）第二十三頁，共二十九頁，編輯于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000x3x1d2－d1+20848010/310000－5/65/614/3000001/6－1/60－4/30001－1－2/32/3010/30－11001/6－1/6σP1P2P3000100000000000100000000010

C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000d3+x1d2－x2126030011－100－11101/101/2－1/2000000－3/5－111－100011/20－1/41/40000σP1P2P3000100000000000100000000010

第二十四頁，共二十九頁，編輯于2023年，星期五C000P100P2P30CBXBbx1x2x3d1－

d1+d2－d2+d3－d3+0000d3+x1d1+x3699150－20003/2－3/2－11110001/4－1/400030－111/4－1/40005100－5/45/400σP1P2P30001000000000001