數(shù)據(jù)、模型與決策

Data,ModelandDecisions

數(shù)據(jù)、模型與決策

趙明霞山西大學(xué)經(jīng)濟(jì)與管理學(xué)院2

其它規(guī)劃問(wèn)題規(guī)劃的組成：目標(biāo)函數(shù)opt（optimize）maxz(f)或minz(f)約束條件s.t.(subjectto)滿足于決策變量用符號(hào)來(lái)表示可控制的因素2023/2/422.1

整數(shù)規(guī)劃2.2

目標(biāo)規(guī)劃2.3

動(dòng)態(tài)規(guī)劃42.1整數(shù)規(guī)劃

§1整數(shù)規(guī)劃的圖解法

§2整數(shù)規(guī)劃的計(jì)算機(jī)求解

§3整數(shù)規(guī)劃的應(yīng)用5求整數(shù)解的線性規(guī)劃問(wèn)題，不是用四舍五入法或去尾法對(duì)線性規(guī)劃的非整數(shù)解加以處理都能解決的，而要用整數(shù)規(guī)劃的方法加以解決。在整數(shù)規(guī)劃中:如果所有的變量都為非負(fù)整數(shù)，則稱為純整數(shù)規(guī)劃問(wèn)題；如果只有一部分變量為非負(fù)整數(shù)，則稱之為混合整數(shù)規(guī)劃問(wèn)題。如果所有的變量都為0-1變量，則稱之為0-1規(guī)劃。6§1整數(shù)規(guī)劃的圖解法例8-1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。甲種貨物至多托運(yùn)4件，問(wèn)兩種貨物各托運(yùn)多少件，可使獲得利潤(rùn)最大?貨物每件體積（立方英尺）每件重量（百千克）每件利潤(rùn)（百元）甲乙19527344023托運(yùn)限制1365140

7解：設(shè)x1、

x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型目標(biāo)函數(shù)：Maxz=2x1+3x2

約束條件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0為整數(shù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問(wèn)題。利用圖解法，8得到線性規(guī)劃的最優(yōu)解為x1=2.44,x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4,x2=2,目標(biāo)函數(shù)值為14。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=69性質(zhì)1：任何求最大目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最大目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最大目標(biāo)函數(shù)值；任何求最小目標(biāo)函數(shù)值的純整數(shù)規(guī)劃或混合整數(shù)規(guī)劃的最小目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最小目標(biāo)函數(shù)值。10例8-2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0為整數(shù)例8-3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3

為整數(shù)

x3

為0-1變量用《管理運(yùn)籌學(xué)》軟件求解得：

x1=5x2=2x3=2用《管理運(yùn)籌學(xué)》軟件求解得：

x1=4x2=1.25x3=1z=16.25§2整數(shù)規(guī)劃的計(jì)算機(jī)求解11§3整數(shù)規(guī)劃的應(yīng)用

一、投資場(chǎng)所的選擇

例8-4:京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個(gè)位置Aj(j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度，規(guī)定：在東區(qū)由A1

，A2

，A3三個(gè)點(diǎn)至多選擇兩個(gè)；在西區(qū)由A4

，A5兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)由A6

，A7兩個(gè)點(diǎn)中至少選一個(gè)；在北區(qū)由A8

，A9

，A10

三個(gè)點(diǎn)中至少選兩個(gè)。

Aj

各點(diǎn)的設(shè)備投資及每年可獲利潤(rùn)由于地點(diǎn)不同都是不一樣的，預(yù)測(cè)情況見(jiàn)表所示(單位：萬(wàn)元)。但投資總額不能超過(guò)720萬(wàn)元，問(wèn)應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤(rùn)為最大?12解：設(shè)：0--1變量xi=1(Ai點(diǎn)被選用）或0(Ai點(diǎn)沒(méi)被選用）。這樣我們可建立如下的數(shù)學(xué)模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2xj≥0

且xj

為0--1變量，i=1,2,3,……,1013二、固定成本問(wèn)題

例8-5:高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元。現(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。14解：這是一個(gè)整數(shù)規(guī)劃的問(wèn)題。設(shè)x1，x2，x3分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說(shuō)明固定費(fèi)用的這種性質(zhì)，設(shè)yi=1(當(dāng)生產(chǎn)第i種容器,即xi＞0時(shí))或0（當(dāng)不生產(chǎn)第i種容器即xi=0時(shí)）。引入約束xi≤Myi

，i=1，2，3，M充分大，以保證當(dāng)yi=0時(shí)，xi=0。

yi=0xi=0

這樣我們可建立如下的數(shù)學(xué)模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj

為0--1變量，i=1,2,315三、指派問(wèn)題有n項(xiàng)不同的任務(wù)，恰好n個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長(zhǎng)不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把n項(xiàng)任務(wù)指派給n個(gè)人，使得完成n項(xiàng)任務(wù)的總的效率最高，這就是指派問(wèn)題。例8-6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問(wèn)應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。16解：引入0—1變量xij，并令

xij=1(當(dāng)指派第i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí))．這可以表示為一個(gè)0--1整數(shù)規(guī)劃問(wèn)題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一項(xiàng)工作)

x21+x22+x23+x24=1(乙只能干一項(xiàng)工作)

x31+x32+x33+x34=1(丙只能干一項(xiàng)工作)

x41+x42+x43+x44=1(丁只能干一項(xiàng)工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

為0--1變量，i,j=1,2,3,417四、分布系統(tǒng)設(shè)計(jì)例8-7．某企業(yè)在A1地已有一個(gè)工廠，其產(chǎn)品的生產(chǎn)能力為30千箱，為了擴(kuò)大生產(chǎn)，打算在A2，A3，A4，A5地中再選擇幾個(gè)地方建廠。已知在A2，A3，A4，A5地建廠的固定成本分別為175千元、300千元、375千元、500千元，另外，A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)(每千箱運(yùn)費(fèi):千元)如下表所示。

a)問(wèn)應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小?

b)如果由于政策要求必須在A2，A3地建一個(gè)廠，應(yīng)在哪幾個(gè)地方建廠?18解：a)設(shè)xij為從Ai運(yùn)往Bj的運(yùn)輸量(單位千箱)，

yk=1(當(dāng)Ak被選中時(shí))或0（當(dāng)Ak沒(méi)被選中時(shí)),k=2,3,4,5．這可以表示為一個(gè)整數(shù)規(guī)劃問(wèn)題：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。s.t.x11+x12+x13≤30(A1

廠的產(chǎn)量限制)

x21+x22+x23≤10y2(A2

廠的產(chǎn)量限制)

x31+x32+x33≤20y3(A3

廠的產(chǎn)量限制)

x41+x42+x43≤30y4(A4

廠的產(chǎn)量限制)

x51+x52+x53≤40y5(A5

廠的產(chǎn)量限制)

x11+x21+x31+x41+x51=30(B1

銷地的限制)

x12+x22+x32+x42+x52=20(B2

銷地的限制)

x13+x23+x33+x43+x53=20(B3

銷地的限制)

xij≥0，i=1,2,3,4,5；j=1,2,3，yk為0--1變量，k=2,3,4,5。19五、投資問(wèn)題(第4章）

例8-8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額為4萬(wàn)元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年末能回收本利128％，但規(guī)定最低投資金額為3萬(wàn)元，最高金額為5萬(wàn)元；

項(xiàng)目C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元或?yàn)?萬(wàn)元。

項(xiàng)目D：五年內(nèi)每年初可購(gòu)買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。該部門現(xiàn)有資金10萬(wàn)元，問(wèn)它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額為最大?20解：1)設(shè)xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分別表示第i年年初給項(xiàng)目A，B，C，D的投資額(元)；設(shè)yiA，yiB，是0—1變量，并規(guī)定取1時(shí)分別表示第i年給A、B投資，否則取0（i=1,3）。設(shè)yiC是非負(fù)整數(shù)變量，并規(guī)定：第2年投資C項(xiàng)目8萬(wàn)元時(shí)，取值為4；第2年投資C項(xiàng)目6萬(wàn)元時(shí)，取值3；第2年投資C項(xiàng)目4萬(wàn)元時(shí)，取值2；第2年投資C項(xiàng)目2萬(wàn)元時(shí)，取值1；第2年不投資C項(xiàng)目時(shí)，取值0；

這樣我們建立如下的決策變量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C=20000y2C

D

x1D

x2D

x3D

x4D

x5D

212）約束條件：第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是x1A+x1D=100000；第二年：A的投資第二年末才可收回，故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的資金為1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的資金為1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的資金為1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。關(guān)于項(xiàng)目A的投資額規(guī)定:x1A≥40000y1A

，x1A≤200000y1A

，200000是足夠大的數(shù)；保證當(dāng)

y1A=0時(shí)，x1A=0；當(dāng)y1A=1時(shí)，x1A≥40000。關(guān)于項(xiàng)目B的投資額規(guī)定:x3B≥30000y3B

，x3B≤50000y3B

；保證當(dāng)

y3B=0時(shí)，x3B=0；當(dāng)y3B=1時(shí)，50000≥

x3B≥30000。關(guān)于項(xiàng)目C的投資額規(guī)定:x2C=20000y2C

，y2C=0，1，2，3，4。223）目標(biāo)函數(shù)及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=10；

x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；

x4A+x4D=1.15x2A+1.06x3D；

x5D=1.15x3A+1.06x4D；

x1A≥4y1A

，

x1A≤10y1A

，

x3B≥3y3B

，

x3B≤5y3B

；

x2C=2y2C

，y2C≤4xiA

，xiB

，xiC

，xiD≥0(i=1、2、3、4、5）,y1A，y3B

為0-1變量,y2C整數(shù)

案例分析教材P199案例分析9-122023/2/42324練習(xí)教材P195習(xí)題2-1125

2.2目標(biāo)規(guī)劃§1目標(biāo)規(guī)劃問(wèn)題舉例§2目標(biāo)規(guī)劃問(wèn)題求解§3復(fù)雜情況下的目標(biāo)規(guī)劃§4加權(quán)目標(biāo)規(guī)劃26§1目標(biāo)規(guī)劃問(wèn)題舉例多目標(biāo)問(wèn)題例1．企業(yè)生產(chǎn)例2．商務(wù)活動(dòng)例3．投資例4．裁員例5．營(yíng)銷27§2目標(biāo)規(guī)劃問(wèn)題求解

例9-6．一位投資商有一筆資金準(zhǔn)備購(gòu)買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時(shí)投資于兩種股票）。其價(jià)格以及年收益率和風(fēng)險(xiǎn)系數(shù)如表1：股票價(jià)格（元）年收益（元）／年風(fēng)險(xiǎn)系數(shù)A2030.5B5040.2從上表可知，A股票的收益率為（3／20）×100％＝15％，股票B的收益率為4／50×100％＝8％，A的收益率比B大，但同時(shí)A的風(fēng)險(xiǎn)也比B大。這也符合高風(fēng)險(xiǎn)高收益的規(guī)律。試求一種投資方案，使得一年的總投資風(fēng)險(xiǎn)不高于700，且投資收益不低于10000元。28

顯然，此問(wèn)題屬于目標(biāo)規(guī)劃問(wèn)題。它有兩個(gè)目標(biāo)變量：一是限制風(fēng)險(xiǎn)，一是確保收益。在求解之前，應(yīng)首先考慮兩個(gè)目標(biāo)的優(yōu)先權(quán)。假設(shè)第一個(gè)目標(biāo)（即限制風(fēng)險(xiǎn)）的優(yōu)先權(quán)比第二個(gè)目標(biāo)（確保收益）大，這意味著求解過(guò)程中必須首先滿足第一個(gè)目標(biāo)，然后在此基礎(chǔ)上再盡量滿足第二個(gè)目標(biāo)。建立模型：設(shè)x1、x2分別表示投資商所購(gòu)買的A股票和B股票的數(shù)量。首先考慮資金總額的約束：總投資額不能高于90000元。即20x1＋50x2≤90000。29一、約束條件再來(lái)考慮風(fēng)險(xiǎn)約束：總風(fēng)險(xiǎn)不能超過(guò)700。投資的總風(fēng)險(xiǎn)為0.5x1＋0.2x2。引入兩個(gè)變量d1+和d1-,建立等式如下：

0.5x1+0.2x2=700+d1+-d1-

其中，d1+表示總風(fēng)險(xiǎn)高于700的部分，d1-表示總風(fēng)險(xiǎn)少于700的部分，d1+,d1-≥0。目標(biāo)規(guī)劃中把d1+、d1-這樣的變量稱為偏差變量。偏差變量的作用是允許約束條件不被精確滿足。30

把等式轉(zhuǎn)換，可得到

0.5x1+0.2x2-d1++d1-=700

再來(lái)考慮年收入:

年收入=3x1+4x2

引入變量d2+和d2-，分別表示年收入超過(guò)與低于10000的數(shù)量。于是，第2個(gè)目標(biāo)可以表示為

3x1+4x2-d2++d2-=1000031二、有優(yōu)先權(quán)的目標(biāo)函數(shù)本問(wèn)題中第一個(gè)目標(biāo)的優(yōu)先權(quán)比第二個(gè)目標(biāo)大。即最重要的目標(biāo)是滿足風(fēng)險(xiǎn)不超過(guò)700。分配給第一個(gè)目標(biāo)較高的優(yōu)先權(quán)P1分配給第二個(gè)目標(biāo)較低的優(yōu)先權(quán)P232針對(duì)每一個(gè)優(yōu)先權(quán)，應(yīng)當(dāng)建立一個(gè)單一目標(biāo)的線性規(guī)劃模型：首先建立具有最高優(yōu)先權(quán)的目標(biāo)的線性規(guī)劃模型，求解；然后再按照優(yōu)先權(quán)逐漸降低的順序分別建立單一目標(biāo)的線性規(guī)劃模型，方法是在原來(lái)模型的基礎(chǔ)上修改目標(biāo)函數(shù)，并把原來(lái)模型求解所得的目標(biāo)最優(yōu)值作為一個(gè)新的約束條件加入到當(dāng)前模型中，并求解。33三、建模1．針對(duì)優(yōu)先權(quán)最高的目標(biāo)建立線性規(guī)劃建立線性規(guī)劃模型如下：

Mind1+s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥0342．針對(duì)優(yōu)先權(quán)次高的目標(biāo)建立線性規(guī)劃優(yōu)先權(quán)次高（P2）的目標(biāo)是總收益超過(guò)10000。建立線性規(guī)劃如下：

Mind2-s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000

d1+＝0x1,x2,d1+,d1-,d2+,d2-≥035目標(biāo)規(guī)劃的這種求解方法可以表述如下：

1．確定解的可行區(qū)域。

2．對(duì)優(yōu)先權(quán)最高的目標(biāo)求解，如果找不到能滿足該目標(biāo)的解，則尋找最接近該目標(biāo)的解。

3．對(duì)優(yōu)先權(quán)次之的目標(biāo)進(jìn)行求解。注意：必須保證優(yōu)先權(quán)高的目標(biāo)不變。

4.重復(fù)第3步，直至所有優(yōu)先權(quán)的目標(biāo)求解完。

36四、目標(biāo)規(guī)劃模型的標(biāo)準(zhǔn)化例6中對(duì)兩個(gè)不同優(yōu)先權(quán)的目標(biāo)單獨(dú)建立線性規(guī)劃進(jìn)行求解。為簡(jiǎn)便，把它們用一個(gè)模型來(lái)表達(dá)，如下：

minP1（d1+）+P2（d2-）

s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥037管理運(yùn)籌學(xué)軟件運(yùn)用注意事項(xiàng)決策變量個(gè)數(shù)：不包括偏差變量（2）優(yōu)先級(jí)數(shù)：目標(biāo)優(yōu)先等級(jí)（2）目標(biāo)約束個(gè)數(shù)：含偏差變量約束條件個(gè)數(shù)（2）絕對(duì)約束個(gè)數(shù)：不含偏差變量約束條件個(gè)數(shù)（1）38§3復(fù)雜情況下的目標(biāo)規(guī)劃例9-7．一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費(fèi)人力2工時(shí)，生產(chǎn)一件產(chǎn)品B需要耗費(fèi)人力3工時(shí)。A、B產(chǎn)品的單位利潤(rùn)分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費(fèi)人力資源不能低于600工時(shí)，但也不能超過(guò)680工時(shí)的極限；次要任務(wù)是要求每周的利潤(rùn)超過(guò)70000元；在前兩個(gè)任務(wù)的前提下，為了保證庫(kù)存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因?yàn)锽產(chǎn)品比A產(chǎn)品更重要，不妨假設(shè)B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的2倍。試求如何安排生產(chǎn)？39解：本問(wèn)題中有3個(gè)不同優(yōu)先權(quán)的目標(biāo)，不妨用P1、P2、P3表示從高至低的優(yōu)先權(quán)。對(duì)應(yīng)P1有兩個(gè)目標(biāo)：每周總耗費(fèi)人力資源不能低于600工時(shí),也不能超過(guò)680工時(shí)；對(duì)應(yīng)P2有一個(gè)目標(biāo)：每周的利潤(rùn)超過(guò)70000元；對(duì)應(yīng)P3有兩個(gè)目標(biāo)：每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件。40采用簡(jiǎn)化模式，最終得到目標(biāo)線性規(guī)劃如下：

MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.

2x1+3x2-d1++d1-=680對(duì)應(yīng)第1個(gè)目標(biāo)

2x1+3x2-d2++d2-=600對(duì)應(yīng)第2個(gè)目標(biāo)

250x1+125x2-d3++d3-＝70000對(duì)應(yīng)第3個(gè)目標(biāo)

x1-d4++d4-=200對(duì)應(yīng)第4個(gè)目標(biāo)

x2-d5++d5-=120對(duì)應(yīng)第5個(gè)目標(biāo)

x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0罰數(shù)權(quán)重41

使用運(yùn)籌學(xué)軟件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目標(biāo)函數(shù)120。可見(jiàn)，目標(biāo)1、目標(biāo)2、目標(biāo)3和目標(biāo)4達(dá)到了，但目標(biāo)5有一些偏差。

42§4加權(quán)目標(biāo)規(guī)劃加權(quán)目標(biāo)規(guī)劃是另一種解決多目標(biāo)決策問(wèn)題的方法，其基本方法是:通過(guò)量化的方法分配給每個(gè)目標(biāo)的偏離的嚴(yán)重程度一個(gè)罰數(shù)權(quán)重，然后建立總的目標(biāo)函數(shù)，該目標(biāo)函數(shù)表示的目標(biāo)是要使每個(gè)目標(biāo)函數(shù)與各自目標(biāo)的加權(quán)偏差之和最小，假設(shè)所有單個(gè)的目標(biāo)函數(shù)及約束條件都符合線性規(guī)劃的要求，那么，整個(gè)問(wèn)題都可以描述為一個(gè)線性規(guī)劃的問(wèn)題。43在例7中我們對(duì)每周總耗費(fèi)的人力資源超過(guò)680工時(shí)或低于600工時(shí)的每工時(shí)罰數(shù)權(quán)重定為7；每周利潤(rùn)低于70000元時(shí)，每元的罰數(shù)權(quán)重為5；每周產(chǎn)品A產(chǎn)量低于200件時(shí)每件罰數(shù)權(quán)重為2，每周產(chǎn)品B產(chǎn)量低于120件時(shí)每件罰數(shù)權(quán)重為4。44則其目標(biāo)函數(shù)化為：

min7d1++7d2-+5d3-+2d4-+4d5-

這就變成了一個(gè)普通的單一目標(biāo)的線性規(guī)劃問(wèn)題

min7d1++7d2-+5d3-+2d4-+4d5-s.t.2x1+3x2-d1++d1-=6802x1+3x2-d2++d2-=680250x1+125x2-d3++d3-=70000x1-d4++d4-=200x2-d5++d5-=120x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-≥0。練習(xí)教材P212習(xí)題1-1045462.3動(dòng)態(tài)規(guī)劃§1多階段決策過(guò)程最優(yōu)化問(wèn)題舉例§2基本概念、基本方程與最優(yōu)化原理§3動(dòng)態(tài)規(guī)劃的應(yīng)用47§1多階段決策過(guò)程最優(yōu)化問(wèn)題舉例例10-1最短路徑問(wèn)題下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最短路徑。BACBDBCDEC41231231232216472483867561106375148用窮舉法的計(jì)算量:如果從A到E的站點(diǎn)有k個(gè)，除A、E之外每站有3個(gè)位置則總共有3k-1×2條路徑；計(jì)算各路徑長(zhǎng)度總共要進(jìn)行(k+1)3k-1×2次加法以及3k-1×2-1次比較。隨著k的值增加時(shí)，需要進(jìn)行的加法和比較的次數(shù)將迅速增加；例如當(dāng)k=20時(shí)，加法次數(shù)為4.2550833966227×1015

次，比較1.3726075472977×1014

次。若用1億次/秒的計(jì)算機(jī)計(jì)算需要約508天。49討論：

1、以上求從A到E的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從Di

、Ci、Bi、A到E的最短路徑問(wèn)題。第四階段：兩個(gè)始點(diǎn)D1和D2，終點(diǎn)只有一個(gè)；表10-1分析得知：從D1和D2到E的最短路徑唯一。

階段4本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)ED1D210*6106EE50

第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2

的最短路徑問(wèn)題：表10-2分析得知：如果經(jīng)過(guò)C1，則最短路為C1-D2-E；如果經(jīng)過(guò)C2，則最短路為C2-D2-E；如果經(jīng)過(guò)C3，則最短路為C3-D1-E。

階段3本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D151第二階段：有4個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3

的最短路徑問(wèn)題：

表10-3

分析得知：如果經(jīng)過(guò)B1，則走B1-C2-D2-E；如果經(jīng)過(guò)B2，則走B2-C3-D1-E；如果經(jīng)過(guò)B3，則走B3-C3-D1-E；如果經(jīng)過(guò)B4，則走B4-C3-D1-E。

階段2本階段始點(diǎn)（狀態(tài)）

本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C352第一階段：只有1個(gè)始點(diǎn)A，終點(diǎn)有B1,B2,B3,B4

。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問(wèn)題：

表10-4最后，可以得到：從A到E的最短路徑為AB4C3D1E

階段1本階段始點(diǎn)(狀態(tài))

本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B453

以上計(jì)算過(guò)程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到E的最短路徑。以上過(guò)程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法。BACBDBCDEC4123123123321647248386751610601061211111213141412751254一、基本概念：

1、階段k：表示決策順序的離散的量，階段可以按時(shí)間或空間劃分。

2、狀態(tài)sk：每個(gè)階段開(kāi)始時(shí)所處的自然狀態(tài)或客觀條件。狀態(tài)可以是數(shù)量，也可以是字符，數(shù)量狀態(tài)可以是連續(xù)的，也可以是離散的。

3、決策xk：從某一狀態(tài)向下一狀態(tài)過(guò)渡時(shí)所做的選擇。決策是所在狀態(tài)的函數(shù)，記為xk(sk)。

4、策略Pk,n(sk)：從第k階段開(kāi)始到最后第n階段的決策序列，稱k子策略。P1,n(s1)即為全過(guò)程策略。

5、指標(biāo)函數(shù)rk(sk,xk)：衡量策略優(yōu)劣的數(shù)量指標(biāo)；最優(yōu)指標(biāo)函數(shù)fk(sk)，f1(s1)。

6、狀態(tài)轉(zhuǎn)移方程sk+1=Tk(sk,xk)：某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系。§2基本概念、基本方程與最優(yōu)化原理55二、基本方程

最優(yōu)指標(biāo)函數(shù)fk(sk)：從狀態(tài)sk出發(fā)，對(duì)所有的策略Pk,n，過(guò)程指標(biāo)rk,n的最優(yōu)值，即56

對(duì)于可加性指標(biāo)函數(shù)，上式可以寫為

上式中“opt”表示“max”或“min”。對(duì)于可乘性指標(biāo)函數(shù)，上式可以寫為

以上式子稱為動(dòng)態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動(dòng)態(tài)規(guī)劃的基本方程。

終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，一般最后一個(gè)狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)=0。57三、最優(yōu)化原理作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)來(lái)說(shuō)，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說(shuō)，最優(yōu)策略的任意子策略都是最優(yōu)的。58一、資源分配問(wèn)題

例10-2.某公司擬將某種設(shè)備5臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠。各工廠獲得此設(shè)備后，預(yù)測(cè)可創(chuàng)造的利潤(rùn)如表10-5所示，問(wèn)這5臺(tái)設(shè)備應(yīng)如何分配給這3個(gè)工廠，使得所創(chuàng)造的總利潤(rùn)為最大？表10-5

工廠盈利設(shè)備臺(tái)數(shù)

甲廠

乙廠

丙廠000013542710639111141211125131112§3動(dòng)態(tài)規(guī)劃的應(yīng)用59解：將問(wèn)題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號(hào)為1、2、3廠。設(shè)

sk=分配給第k個(gè)廠至第3個(gè)廠的設(shè)備臺(tái)數(shù)（k=1、2、3）。

xk=分配給第k個(gè)廠設(shè)備臺(tái)數(shù)。已知s1=5,

并有

從sk

與xk

的定義，可知

以下我們從第三階段開(kāi)始計(jì)算。60

第三階段:

顯然將s3(s3=0,1,2,3,4,5)臺(tái)設(shè)備都分配給第3工廠時(shí)，也就是s3=x3時(shí)，第3階段的指標(biāo)值（即第3廠的盈利）為最大，即

由于第3階段是最后的階段，故有其中x3可取值為0,1,2,3,4,5。其數(shù)值計(jì)算見(jiàn)表10－6。61表10－6

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－1212562

其中x*3表示取3子過(guò)程上最優(yōu)指標(biāo)值f3(s3)時(shí)的x3決策，例如在表10-6中可知當(dāng)s3=4時(shí)，有r3(4,4)=12,有f3(4)=12此時(shí)x*3=4，即當(dāng)s3=4時(shí)，此時(shí)取x3=4

（把4臺(tái)設(shè)備分配給第3廠）是最優(yōu)決策，此時(shí)階段指標(biāo)值（盈利）為12，最優(yōu)3子過(guò)程最優(yōu)指標(biāo)值也為12。63第二階段：當(dāng)把s2=0,1,2,3,4,5臺(tái)設(shè)備分配給第2工廠和第3工廠時(shí)，則對(duì)每個(gè)s2值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過(guò)程最優(yōu)指標(biāo)函數(shù)值為因?yàn)閟3=s2-x2上式也可寫成64其數(shù)值計(jì)算如表10－7所示。

表10－7

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

21265第一階段：把臺(tái)設(shè)備分配給第1，第2，第3廠時(shí)，最大盈利為其中可取值0,1,2,3,4,5。數(shù)值計(jì)算見(jiàn)表10－8

0

1

2

3

4

5

5

3＋169+1012+513+0210,266然后按計(jì)算表格的順序推算，可知最優(yōu)分配方案有兩個(gè)：

1.由于x*1=0，根據(jù)s2=s1-x*1=5，查表10－7可知x*2=2，再由s3=s2-x*2=3，求得x*3=s3=3。即分配給甲廠0臺(tái)，乙廠2臺(tái)，丙廠3臺(tái)。

2.由于x*1=2，根據(jù)s2=s1-x*1=3，查表10－7可知x*2=2，再由s3=s2-x*2=1,求得x*3=s3=1，即分配給甲廠2臺(tái)，乙廠2臺(tái)，丙廠1臺(tái)。這兩種分配方案都能得到最高的總盈利21萬(wàn)元。67二、背包問(wèn)題設(shè)有n種物品，每一種物品數(shù)量無(wú)限。第i種物品每件重量為wi公斤，每件價(jià)值ci元?，F(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。這個(gè)問(wèn)題可以用整數(shù)規(guī)劃模型來(lái)描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i=1,2,…,n），背包中物品的總價(jià)值為z，則

maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且為整數(shù)。68

下面用動(dòng)態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量sk：第k次裝載時(shí)背包還可以裝載的重量；決策變量xk：第k次裝載第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=skwkxk；階段指標(biāo)：rk=ckxk；最優(yōu)過(guò)程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價(jià)值；遞推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(skwkxk)}；

xDk(sk)終端條件：fn+1(sn+1)=0。69

例10-3.某咨詢公司有10個(gè)工作日可以去處理四種類型的咨詢項(xiàng)目，每種類型的咨詢項(xiàng)目中待處理的客戶數(shù)量、處理每個(gè)客戶所需工作日數(shù)以及所獲得的利潤(rùn)如表10－9所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請(qǐng)其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個(gè)工作日中獲利最大？表10－9咨詢項(xiàng)目類型待處理客戶數(shù)處理每個(gè)客戶所需工作日數(shù)處理每個(gè)客戶所獲利潤(rùn)

1

2

3

4

4

3

2

2

1

3

4

7

2

8

11

2070

解：用動(dòng)態(tài)規(guī)劃來(lái)求解此題。我們把此問(wèn)題分成四個(gè)階段：第一階段我們決策將處理多少個(gè)第一種咨詢項(xiàng)目類型中的客戶，第二階段決策將處理多少個(gè)第二種咨詢項(xiàng)目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們?cè)O(shè)

sk＝分配給第k種咨詢項(xiàng)目到第四種咨詢項(xiàng)目的所有客戶的總工作日（第k階段的狀態(tài)變量）。

xk=在第k種咨詢項(xiàng)目中處理客戶的數(shù)量（第k階段的決策變量）。已知s1＝10并有71從第四階段開(kāi)始計(jì)算：顯然將s4個(gè)工作日s4=(0,1,2……,10)盡可能分配給第四類咨詢項(xiàng)目，即x4=[s4/7]時(shí)，第四階段的指標(biāo)值為最大，其中[s4/7]表示取不大于[s4/7]的最大整數(shù)，符號(hào)[]為取整符號(hào)，故有由于第四階段是最后的階段，故有72因?yàn)閟4至多為10，其數(shù)值計(jì)算見(jiàn)表10－10。

表10－10

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

20

173第三階段：當(dāng)把s3=(0,1,2……,10)個(gè)工作日分配給第四類和第三類咨詢項(xiàng)目時(shí)，則對(duì)每個(gè)s3值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過(guò)程最優(yōu)指標(biāo)函數(shù)值為

因?yàn)橐驗(yàn)閟3

至多為10，所以x3的取值可為0,1,2。其數(shù)值計(jì)算見(jiàn)表10－11。74

表10－11

012

0－－

0

01

－－

0

02－－

0

03－－

0

04

0＋0－

1115

0＋0－

1116

0＋0－

1117

11+0－2008

0＋20

11+0

2229

0＋20

11+0

22210

0＋20

11+0

22275第二階段：同樣以每個(gè)s2值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過(guò)程最優(yōu)指標(biāo)函數(shù)值為：因?yàn)?，故有因?yàn)閟2至多為10，所以x2的取值為0,1,2,3。其數(shù)值計(jì)算見(jiàn)表10－12。76表10-1277

第一階段：我們已知，又因?yàn)?，同樣?/p>

因?yàn)?故可取值為0,1,2,…,10。其數(shù)值計(jì)算見(jiàn)表10－13。表10－1378從表10－13可知f1(10)=28，x*1=0從而得s2=s1-x*1＝10－0＝10表10－12的s2=10的這一行可知x*2=1，由s3=s2-3x*1＝7查表10－11的s3=7的這一行可知x*3=0，最后由s4=s3-x*3＝7查表10-10的s4=7這一行得x*4=1綜上所述得最優(yōu)解為：x*1=0,x*2=1，x*3=0，x*4=1,最大盈利為28。現(xiàn)在我們不妨假設(shè)該咨詢公司的工作計(jì)劃有所改變，只有8個(gè)工作日來(lái)處理這四類咨詢項(xiàng)目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開(kāi)始重做這個(gè)問(wèn)題，而只要在第一階段上把s1改成8，重新計(jì)算就可得到結(jié)果，如表10－14所示，這是動(dòng)態(tài)規(guī)劃的一個(gè)好處。79

表10－14

如上一樣可從表10－14,10－12,10－11,10－10得到兩組最優(yōu)解如下：

它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計(jì)算第一階段，而且要在第二、第三、第四階段的計(jì)算表上補(bǔ)上增加的工作日的新的信息，也可得到新的結(jié)果。80三、生產(chǎn)與存貯問(wèn)題

例10-4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購(gòu)買，所以該公司可以預(yù)測(cè)未來(lái)幾個(gè)月的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)生產(chǎn)計(jì)劃，這四個(gè)月的需求如表10－15所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費(fèi)為4，除了調(diào)度費(fèi)