第四章目標(biāo)規(guī)劃及圖解法運(yùn)籌學(xué)

第四章目標(biāo)規(guī)劃及圖解法運(yùn)籌學(xué)第一頁，共二十九頁，編輯于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年，星期五目標(biāo)的含義本題三個(gè)目標(biāo)依次表示為：

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中還提出一些的希望達(dá)到的目標(biāo)。這些要求實(shí)際上也是約束條件，當(dāng)然這些目標(biāo)能到達(dá)最好，實(shí)在無法達(dá)到也是可以接受的，我們稱之為目標(biāo)約束如：1、B產(chǎn)品不超過10單位

2、利潤不低于1600元

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

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

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

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）目標(biāo)的重要程度不同，因此目標(biāo)的滿足有先有后，即有優(yōu)先級別。設(shè)最重要的為P1級，次之者為P2級——優(yōu)先因子

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

。6)x1+2x2

≤

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

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

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

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

d3-

和d3+越小越好7）目標(biāo)規(guī)劃的目標(biāo)第十二頁，共二十九頁，編輯于2023年，星期五問題分析7）目標(biāo)規(guī)劃的目標(biāo)函數(shù)：目標(biāo)規(guī)劃有多個(gè)目標(biāo)，我們已經(jīng)把它轉(zhuǎn)化為目標(biāo)約束，整個(gè)問題的目標(biāo)就是使得實(shí)施結(jié)果與目標(biāo)期望值的偏差最小于是本題目標(biāo)函數(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ù)學(xué)模型為：目標(biāo)函數(shù)：minZ={P1d1+,P2d2-

,P3(d3-+d3+)}約束條件第十四頁，共二十九頁，編輯于2023年，星期五目標(biāo)規(guī)劃的概念及數(shù)學(xué)模型數(shù)學(xué)模型為：目標(biāo)函數(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目標(biāo)約束系統(tǒng)約束第十五頁，共二十九頁，編輯于2023年，星期五目標(biāo)規(guī)劃的圖解法例22x1+1.5x2≤50x2+d1--d1+=1080x1+100x2+d2--d2+=1600x1+2x2+d3--d3+=40x1

，x2

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

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

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

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

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

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.

該目標(biāo)規(guī)劃和下面線性規(guī)劃問題等價(jià)第二十一頁，共二十九頁，編輯于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