最優(yōu)化方法練習(xí)題答案

練習(xí)題一

1、建立優(yōu)化模型應(yīng)考慮哪些要素？

答：決策變量、目標(biāo)函數(shù)和約束條件。

2、討論優(yōu)化模型最優(yōu)解的存在性、迭代算法的收斂性及停止準(zhǔn)那么。

min/(x)

答：針對一般優(yōu)化模型g,(x)>0,z=l,2,m,討論解的可行域。，假設(shè)存在一點(diǎn)

(x)=0,j=1,,p

X*eD,對于VXw。均有/(X*)</(X)那么稱X*為優(yōu)化模型最優(yōu)解，最優(yōu)解存在；迭代

算法的收斂性是指迭代所得到的序列X?X⑵，,X(K),滿足/(X(KM))</(X(K)),那么

1111(M)W

迭代法收斂;收斂的停止準(zhǔn)那么有卜--叫<￡,..(n||<g,|/(X)-/(X)|<￡，

練習(xí)題二

1、某公司看中了例2.1中廠家所擁有的3種資源Ri、R2、和R3,欲出價收購(可能

用于生產(chǎn)附加值更高的產(chǎn)品)。如果你是該公司的決策者，對這3種資源的收購報價是多

少？(該問題稱為例2.1的對偶問題)。

解：確定決策變量對3種資源報價冷火，%作為本問題的決策變量。

確定目標(biāo)函數(shù)問題的目標(biāo)很清楚一一“收購價最小”。

確定約束條件資源的報價至少應(yīng)該高于原生產(chǎn)產(chǎn)品的利潤，這樣原廠家才可能賣。

因此有如下線性規(guī)劃問題：min攻=170%+100%+150%

*2、研究線性規(guī)劃的對偶理論和方法(包括對偶規(guī)劃模型形式、對偶理論和對偶單純

形法)。

答：略。

3、用單純形法求解以下線性規(guī)劃問題：

minZ—Xy—%2+%3z—4-+%3

+%2-2叼〈2%]—2%2+%3=2

2%i+%2+%3<3；〔2〕—2%3+=2

s.t.<

-%]+叼<4+%3+%5=5

,%2，%3-0X/>00=1,2,…,5)

解：(1)引入松弛變量X4,X5,X6

CL1-11000

CB基5XIX2X3X4X5X6

QX421EH-2100

0X53211010

0X64-101001

Cj-Zj1-11000

因檢驗(yàn)數(shù)。2<0,故確定X2為換入非基變量,以XI的系數(shù)列的正分量對應(yīng)去除常數(shù)列,

最小比值所在行對應(yīng)的基變量X4作為換出的基變量。

CL1-11000

CB基bX1尤4X3X4X5X6

-1xi211-2100

0X5110[3]-110

QX64-101001

Cj-Zj20-1100

因檢驗(yàn)數(shù)O3<0,故確定X3為換入非基變量,以X3的系數(shù)列的正分量對應(yīng)去除常數(shù)列,

最小比值所在行對應(yīng)的基變量X5作為換出的基變量。

5-1-11000

CB基bXIX2X5X4X5X6

0

-1x28/35/311/32/30

1X31/31/301-1/31/30

0X611/3-4/3001/3-1/31

Cj-Zj7/3032/31/30

因檢驗(yàn)數(shù)5>。，說明已求得最優(yōu)解：X*=(0,8/3,1/3,0,0,11/3),去除添加的松弛變量,

原問題的最優(yōu)解為：X*=(0,8/3,1/3)o

[2)根據(jù)題意選取XI,%4,%5,為基變量：

C.L0-1100

CB基bXIX2X3X4X5

0XI21-2100

0X420[1]-210

0X5501101

Cj-Zj0-1100

因檢驗(yàn)數(shù)s<0最小，故確定X2為換入非基變量，以及的系數(shù)列的正分量對應(yīng)去除常數(shù)

列，最小比值所在行對應(yīng)的基變量X4作為換出的基變量。

CL0-1100

CB基bXIX2%3X4X5

0xi610-320

-1X22Ol-2io

0xs300[3]-11

Cj-Zj00-110

因檢驗(yàn)數(shù)O3<0最小，故確定X3為換入非基變量，以XI的系數(shù)列的正分量對應(yīng)去除常數(shù)

列，最小比值所在行對應(yīng)的基變量X5作為換出的基變量。

CL0-1100

CB基匕XIX2X3X4X5

0xi910011

-1X240101/32/3

1X31001-1/31/3

Cj-Zj0002/31/3

因檢驗(yàn)數(shù)5>0,說明已求得最優(yōu)解：X*=(9,4,1,0,0)。

4、分別用大”法、兩階段法和Matlab軟件求解以下線性規(guī)劃問題:

minZ=4XI+%2maxz=10巧+15%2+12叼

3司+%2=3f5a+3叼+叼49

⑴s.t.<9X1+3%2-6；⑵“l(fā)5X1+6%2+15叼415

X]+2%2—32xj+%2+叼―5

X],%22°[巧,，町20

解：（1）大M法

根據(jù)題意約束條件1和2可以合并為1,引入松弛變量X3,X4,構(gòu)造新問題。

CL41M0

CB基匕X\X2X3X4

MX33[3]110

0%431201

CrZj4-3M1-M00

4xi111/31/30

0X420[5/3]-1/31

Cj-Zj0-1/3M-4/30

4xi3/5102/5-1/5

1X26/501-1/53/5

Cj-Zj00M-7/51/5

因檢驗(yàn)數(shù)5>0,說明已求得最優(yōu)解：X*=(3/5,6/5)o

Matlab調(diào)用代碼：

f=[4；l]；

A=[-9,-3;l,2];

b=[-6;3];

Aeq=[3,l];

beq=3;

lb=[O;O];

[x,fval]=linprog(f,A,b,Aeq,beq,lb)

輸出結(jié)果：

Optimizationterminated.

x=

0.6000

1.2000

fval=

3.6000

(2〕大M法

引入松弛變量X4,X5,X6,X7構(gòu)造新問題。

單純形表計(jì)算略；當(dāng)所有非基變量為負(fù)數(shù)，人工變量匕=0.5,所以原問題無可行解。

請同學(xué)們自己求解。

Matlab調(diào)用代碼：

f=[-10;-15;-12];

A=[5,3,l;-5,6,15;-2,-l,-l];

b=[9;15;-5];

lb=[0;0;0];

x=linprog(f,A,b,[],[],lb)

輸出結(jié)果：

原題無可行解。

5、用內(nèi)點(diǎn)法和Matlab軟件求解以下線性規(guī)劃問題：

解：用內(nèi)點(diǎn)法的過程自己書寫，參考答案：最優(yōu)解X=[4/37/30]；最優(yōu)值5

Matlab調(diào)用代碼：

f=[2；l；l]；

Aeq=[l,2,2;2,l,0];

beq=[6;5];

lb=[O;O;O];

[x,fval]=linprog(f,[],[],Aeq,beq,lb)

輸出結(jié)果：

Optimizationterminated.

x=

1.3333

2.3333

0.0000

fval=

5.0000

6、用分支定界法求解以下問題：

maxz=5x]+8x2m(z=7xj+9%2

Xj+%2-6—X]+3%2—6

(1)s.t.<5刈+9x2<45；⑵s」

7芍+x2-35

X1，X2NO且均為整數(shù)xr,x220且刈為整數(shù)

解：(1)調(diào)用matlab編譯程序bbmethod

f=[-5;-8];G=[11;59];h=[6;45]

[x,y]=bbmethod(f,G,h,[],[],[0;0],[],[l;l],l)

x=

33

y=

-39

最優(yōu)解[33]；最優(yōu)值39

⑵調(diào)用matlab編譯程序bbmethod

f=[-7;-9];G=[-13;7l];h=[6;35]

[x,y]=bbmethod(f,G,h,[],[],[0;0],[],[l;0],l)

x=

50

y=

-35

最優(yōu)解［50］；最優(yōu)值35

7、用隱枚舉法和Matlab軟件求解以下問題:

maxz=3%i+2x-5%3-2x+3%5

minz=4司+3x2+2x324

2%]—5犬2+3%3W4Xy+%2+冗3+2%4+%5V4

4%]+%2+3町237%]+3%3—4%4+3%5?8

(2〕s.t.<

%2+%3-111%]—6%2+3%4—3九5—1

Xj=0或1(/=1,2,3)弓=0或1()=1,2,…,5)

解：隱枚舉法:

⑴將(0,0,0)[0,0,1〕(0,1,0〕(1,0,0)(0,1,1)[1,0,1)[1,1,

0)(1,1,1)分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是(0,0,1),目標(biāo)函

數(shù)最優(yōu)值2.

(2)將(0,0,0,0,0〕(0,0,0,0,1)(0,0,0,1,0〕(0,0,1,0,Oj....

(1,1,1,1,1〕分別帶入到約束條件中，可以得到：原問題的最優(yōu)解是(1,1,0,0,

0),目標(biāo)函數(shù)最優(yōu)值-5。

Matlab軟件求解：

⑴

調(diào)用代碼:

f=[4;3;2];%價值向量/

A=[2,-5,3；%不等式約束系數(shù)矩陣A,□中的分號“；”％為行分隔符

b=[4;-3;-l];%不等式約束右端常數(shù)向量b

[x,fval]=bintprog(f,A,b,[],[]);%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。

輸出結(jié)果

X二

0

0

1

fval=

2

⑵

調(diào)用代碼:

f=[-3;-2;5;2;3];%價值向量/

A=[l,l,1,2,1;7,0,3,-4,3；-11,6,0,-3,3];%不等式約束系數(shù)矩陣A,□中的分號“；”％為行分隔符

b=[4;8;-1];%不等式約束右端常數(shù)向量b

[x,fval]=bintprog(f,A,b,[],[]);%調(diào)用函數(shù)bintprog。注意兩個空數(shù)組的占位作用。

輸出結(jié)果

x=

1

0

0

0

fval=

最優(yōu)值5。

8、某地區(qū)有A、B、C三個化肥廠，供給本地甲、乙、丙、丁四個產(chǎn)糧區(qū)。各化肥廠

可供給化肥的數(shù)量和各產(chǎn)糧區(qū)對化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價如表2-28

所示。試制定一個使總運(yùn)費(fèi)最少的化肥調(diào)撥方案。

表2-1

運(yùn)價/7糧

甲乙丙T各廠供給量/萬噸

化肥廠

Ai58737

A2491078

A384293

各區(qū)需要量/萬噸6633

解：設(shè)A、B、C三個化肥廠為Ai、A2、A3,甲、乙、丙、丁四個產(chǎn)糧區(qū)為Bi、B2、

B3、B4;Q為由Ai運(yùn)化肥至Bj的運(yùn)價，單位是元/噸；瓶為由Ai運(yùn)往Bj的化肥數(shù)量

（i=l,2,3;j=l,2,3,4〕單位是噸；z表示總運(yùn)費(fèi)，單位為元，依題意問題的數(shù)學(xué)模型為：

該題可以用單純形法或matlab自帶工具箱命令［linprog）求解。

*9、求解以下不平衡運(yùn)輸問題（各數(shù)據(jù)表中，方框內(nèi)的數(shù)字為單位價格回，框外右側(cè)

的一列數(shù)為各發(fā)點(diǎn)的供給量%,框底下一行數(shù)是各收點(diǎn)的需求量%）：

要求收點(diǎn)3的需求必須正好滿足。

要求收點(diǎn)1的需求必須由發(fā)點(diǎn)4供給。

解答略。

10、一公司經(jīng)理要分派4位推銷員去4個地區(qū)推銷某種商品。推銷員各有不同的經(jīng)驗(yàn)

和能力，因而他們在不同地區(qū)能獲得的利潤不同，其獲利估計(jì)值如表2-29所示。公司經(jīng)理

應(yīng)怎樣分派才使總利潤最大？

表2-2

1234

推

135272837

228342940

335243233

424322528

解：用求極大值的“匈牙利法”求解。

效率矩陣表示為：

勺5272837)(r?123、

行約簡

28342940i.M-9110

1

35243233f87

28)1.M=40

、2432251512,

(2106（。）、

〈21090）

!列約簡80*_

12611

2所畫。元素少于n（n=4）,未得到

(^>0*

01132

1r標(biāo)號

18074

最優(yōu)解，需要繼續(xù)變換矩陣（求能覆蓋所有0元素的最少數(shù)直線集合）：

p106(|叫

1268()*

(0)1102

1aQ⑼/n\4/I

未被直線覆蓋的最小元素為叼=2,在未被直線覆蓋處減去2,在直線交叉處加上2。

"1000

00

J得最優(yōu)解:0標(biāo)號

0Upj------IX.

、010

??.使總利潤為最大的分配任務(wù)方案為:

1-1,2—4,3-3,4—2

此時總利潤W=35+40+32+32=139

練習(xí)題三

1、用0.618法求解問題

的近似最優(yōu)解，。⑺的單谷區(qū)間為[0,3],要求最后區(qū)間精度￡=0.5。

答：t=0.8U5；最小值-0.0886.(調(diào)用golds.m函數(shù))

2、求無約束非線性規(guī)劃問題

minf(xl,x2,x3)=xf+4x；+-2xx

的最優(yōu)解

解一：由極值存在的必要條件求出穩(wěn)定點(diǎn)：

—2,'=8%,』~=2X3,那么由W(x)=0得X]=1,x2—0>X3=。

dxxdx2dx3一

再用充分條件進(jìn)行檢驗(yàn)：

2222

d~f.dfodf,dfnd2fndf?

亞dr,dx30再去2亞&3dx2dx?

’200、

即y2/=080為正定矩陣得極小點(diǎn)為x*=(l,0,0)T,最優(yōu)值為-1。

1002)

解二：目標(biāo)函數(shù)改寫成

min-(一，龍2，%3)=(七一I)2+-1

易知最優(yōu)解為[1,0,0),最優(yōu)值為-1。

3、用最速下降法求解無約束非線性規(guī)劃問題。

其中X=(再,無2尸，給定初始點(diǎn)X°=(0,01。

?'(X)

。(七)1+4%+2X

解一:目標(biāo)函數(shù)/(X)的梯度W(x)=2

旗X)—1+2再+2%2

。(％2)

1-1

V/,(X(0))=令搜索方向d(i)=-W(X(°))=再從X(°)出發(fā)，沿d⑴方向作一維尋優(yōu),

—11

令步長變量為2,最優(yōu)步長為4,那么有X⑼+4/)=0+2

0

故/(X)=/(X⑼+2J(1))=(-2)-2+2(—4)2+2(-2)2+22=22-22^^(2)

0-1-1

令9；U）=2X—2=0可得4=1X。）=X（°）+4/1）=0+]=]求出X⑴點(diǎn)之后，與上

類似地，進(jìn)行第二次迭代：vf（x（1））=令F=-vf（x（D）=

一1

令步長變量為2,最優(yōu)步長為4,那么有

故

/(%)=f(Xm+4d⑵)=()_1)-Q+1)+2(4-1)2+2(2-1)(2+1)+(A+l)a=522-2A-1=%(A)

1-1i1

令夕2（力）=10力一2=0可得/X⑵=X（i）+//）=]+玄]-0.8

1.2

“(X(2))=02此時所到達(dá)的精度||W(X⑵)卜0.2828

此題最優(yōu)解X*=:;,/(X*)=-1,25

解二：利用matlab程序求解

首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件

functionf=fun(x)

f=x(l)-x(2)+2*x(1)*x(1)+2*x(l)*x(2)+x(2)*x(2);

functiong=gfun(x)

g=[l+4*x(l)+2*x(2),-l+2*x(l)+2*x(2)];

調(diào)用grad.m文件

x0=[0,0];

[x,val,k]=grad('fun7gfun',x0)

結(jié)果

x=[-1.0000,1.5000]

val=-1.2500

k=33

即迭代33次的到最優(yōu)解x=[-1.0000,1.5000]；最優(yōu)值val=-1.2500。

4、試用Newton法求解第3題。

解一：計(jì)算目標(biāo)函數(shù)的梯度和Hesse陣

第(x)

。(西)1+4%+2X

目標(biāo)函數(shù)/Xx)的梯度Vf(x)=2

討(X)—1+2玉+2%2

。(%2)

420.5-0.5

V2/(X)=22=G，其逆矩陣為G-I

-0.51

計(jì)算|W(x(叫=0。

此題最優(yōu)解X*=:[,/(X*)=-1,25

解二：除了第3題建立兩個M文件外，還需建立Hesse矩陣的M文件

利用matlab程序求解

首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件

functionf=fun(x)

f=x(l)-x(2)+2*x(1)*x(1)+2*x(l)*x(2)+x(2)*x(2);

functiong=gfun(x)

g=[l+4*x(l)+2*x(2),-l+2*x(l)+2*x(2)];

functionh=hess(x)

g=[42;22];

調(diào)用newton.m文件

x0=[0,0];

[x,val,k]=newton('fun,,,gfun,,'hess,,xO)

結(jié)果

x=[-1.0000,1.5000]

val=-1.2500

k=l

5、用Fletcher一Reeves法求解問題

其中X=&,々尸，要求選取初始點(diǎn)X°=(2,2廠,￡=10-6。

解一：

1「2OlFxl「20]1

/(尤)=彳(尻，々)八，G=cs，r=Vf(x)=(2x1,50x2).

21050J|_x2J|_050

第一次迭代:令Po=-4=(-4,-100)，,

即，X。)=X(°)+%0=(1.92,0尸

第二次迭代：

^=(3.84,0/,4=邛=焉，+&%=(—3.846,—0.15)T

第三次迭代：

々=(0.1464,-3.6尸……(建議同學(xué)們自己做下去，注意判別㈤歸力

解二：利用matlab程序求解

首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件

functionf=fun(x)

f=x(l)人2+25*x(2)*x(2);

functiong=gfun(x)

g=[2*x(l),50*x(2)];

調(diào)用frcg.m文件

x0=[2,2],;epsilon=le-6;

[x,val,k]=frcg(,fun,,'gfun',xO,epsilon)

結(jié)果

x=1.0e-006*[0.2651,0.0088]

val=7.2182e-014

k=61

6、試用外點(diǎn)法[二次罰函數(shù)方法〕求解非線性規(guī)劃問題

min/(X)=(%1-2)2+

s.t.g(X)=x2-1>0

2

其中X=(x15x2)eR

解：設(shè)計(jì)罰函數(shù)P(x,M)=/(X)+M*[g(X)]人2

采用Matlab編程計(jì)算，結(jié)果x=[l0]；最優(yōu)結(jié)果為1。(調(diào)用waidianfa.m)

7、用內(nèi)點(diǎn)法〔內(nèi)點(diǎn)障礙罰函數(shù)法)求解非線性規(guī)劃問題：

解：容易看出此問題最優(yōu)解為x=[l0]；最優(yōu)值為8.

給出罰函數(shù)為尸(x,r)=(為+1尸+々+r(l/(為-1)+1/9)

令^2=3?+1>-一^=o；^)=i-4-o

玉(七一1)x2%；

從而當(dāng)廠―0時，x(r)=f=x

7rJ⑼

1建議同學(xué)自己編程序計(jì)算)

8、用乘子法求解以下問題渴X)3+z-2=。

解：建立乘子法的增廣目標(biāo)函數(shù)：

令："o~)=2石-%+b(再+%—2)=0

陰

解上述關(guān)于x的二元一次方程組得到穩(wěn)定點(diǎn)

當(dāng)乘子2取2時，或發(fā)參數(shù)〃趨于無窮時，得到元=；=x*即最優(yōu)解。

1建議同學(xué)自己編程序計(jì)算)

練習(xí)題四

1、石油輸送管道鋪設(shè)最優(yōu)方案的選擇問題：考察網(wǎng)絡(luò)圖4-6,設(shè)A為出發(fā)地，F(xiàn)為目

的地，B,C,D,E分別為四個必須建立油泵加壓站的地區(qū)。圖中的線段表示管道可鋪設(shè)

的位置，線段旁的數(shù)字表示鋪設(shè)這些管線所需的費(fèi)用。問如何鋪設(shè)管道才能使總費(fèi)用最??？

圖4-1

解：

第五階段：El—F4；E2—F3；

第四階段：DI—El—F7；D2—E2—F5；D3—El—F5；

第三階段：Cl—DI—El—F12；C2—D2—E2—F10；C3—D2—E2—F8；C4—D3—El—F9；

第二階段：Bl—C2—D2—E2—F13；B2—C3—D2—E2—F15；

第一階段：A—Bl—C2—D2—E2—F17；

最優(yōu)解：A—Bl—C2—D2—E2—F最優(yōu)值：17

2、用動態(tài)規(guī)劃方法求解非線性規(guī)劃

解：xi—9,x2—9,xi—9,最優(yōu)值為9。

3、用動態(tài)規(guī)劃方法求解非線性規(guī)劃

解：用順序算法

階段：分成兩個階段，且階段1、2分別對應(yīng)辦,%。

決策變量：石,々

狀態(tài)變量：+叫分別為第/階段第一、第二約束條件可供分配的右段數(shù)值。

由于%=10,叫=9，方(%,墳2)二方(1。,9)=max{min{33xf一292%+760,68%；+396x+621}

0<^2<52

可解的％=9.6,々=0.2,最優(yōu)值為702.92。

4、設(shè)四個城市之間的公路網(wǎng)如圖4-7o兩點(diǎn)連線旁的數(shù)字表示兩地間的距離。使用迭

代法求各地到城市4的最短路線及相應(yīng)的最短距離。

圖4-2城市公路網(wǎng)

解：城市1到城市4路線一一1-3-4距離10；

城市2到城市4路線一一2-4距離8；城市3到城市4路線一一3-4距離4。

5、某公司打算在3個不同的地區(qū)設(shè)置4個銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)

設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表4-19所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可

使每月總利潤最大。

表4-1

解：

將問題分為3個階段，k=l,2,3；

決策變量也表示分配給第k個地區(qū)的銷售點(diǎn)數(shù)；

狀態(tài)變量為s左表示分配給第左個至第3個地區(qū)的銷售點(diǎn)總數(shù)；

狀態(tài)轉(zhuǎn)移方程：S左+]=s左一X左，其中S]=4；

允許決策集合：D,[sA=

AV/vAV/V/v

階段指標(biāo)函數(shù)：g左表示々個銷售點(diǎn)分配給第左個地區(qū)所獲得的利潤；

最優(yōu)指標(biāo)函數(shù)〃(6攵)表示將數(shù)量為V的銷售點(diǎn)分配給第k個至第3個地區(qū)所得到的最大

利潤，動態(tài)規(guī)劃根本方程為：

上3時，力。3)=max[g3(&)]

巧=$3

左=2時，力(%)=max[g,(x,)+力(s,-%,)]

0<^2<52

左=1時，工(。)=max[&(%)+力(?！?],X(Si)=max[gi(%)+/,(4-xJ]

0<x(<s10<看<4

最優(yōu)解為：町*=2,x2*=l,X3*=L4(4)=47,即在第1個地區(qū)設(shè)置2個銷售點(diǎn)，第2個地

區(qū)設(shè)置1個銷售點(diǎn)，第3個地區(qū)設(shè)置1個銷售點(diǎn)，每月可獲利潤47。

6、設(shè)某廠方案全年生產(chǎn)某種產(chǎn)品A。其四個季度的訂貨量分別為600公斤，700公斤,

500公斤和1200公斤。生產(chǎn)產(chǎn)品A的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比，系數(shù)為0.005。廠內(nèi)

有倉庫可存放產(chǎn)品，存儲費(fèi)為每公斤每季度1元。求最正確的生產(chǎn)安排使年總本錢最小。

解：四個季度為四個階段，采用階段編號與季度順序一致。

設(shè)必為第左季初的庫存量，那么邊界條件為si=S5=0

設(shè)乙為第左季的生產(chǎn)量，設(shè)株為第左季的訂貨量；s左，"都取實(shí)數(shù)，狀態(tài)轉(zhuǎn)移方程

為我+l=sk+%-株仍采用反向遞推，但注意階段編號是正向的目標(biāo)函數(shù)為：

第一步：（第四季度）總效果a（§4，和）=°，0°5X/+S4

由邊界條件有：巧=$4+和->4=3解得：^4*=1200-54

將％*代入必（§4，》4）得：

2

必*（§4）=0.005（1200—§4）2+64=7200-1154+0.00554

第二步：（第三、四季度）總效果8（53，叼）=0。05叼2+53+a*（54）

將§4=§3+%3-500代入力（S3,叼）得：

第三步：（第二、三、四季度）總效果

力（52，%2）=0-0。5X22+s2+f3*（S3）

將§3=§2+%2-700代入力（$2，%2）得：

第四步：（第一、二、三、四季度）總效果

1^1）=0.005xj+s]+力*（肛）

將§2=$1+町一600=町—600代入力（5口1）得：

由此回溯：得最優(yōu)生產(chǎn)-庫存方案

jq*=600,$2*=0;》2*=700，§3*=。；叼*=800，54*=300;x^*=900o

7、某種機(jī)器可在上下兩種不同的負(fù)荷下進(jìn)行生產(chǎn)。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)

為g=8Mi,其中Ml為投入生產(chǎn)的機(jī)器數(shù)量，年完好率。=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為

h=5y,其中y為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為6=0.9。假定開始生產(chǎn)時完好機(jī)器的數(shù)量

51=1000。試問每年如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，使在5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最

高。

解：

構(gòu)造這個問題的動態(tài)規(guī)劃模型：

設(shè)階段序數(shù)k表示年度。

狀態(tài)變量sk為第k年度初擁有的完好機(jī)器數(shù)量，同時也是第k-1年度末時的完好機(jī)器數(shù)量。

決策變量uk為第k年度中分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是sk-uk為該年度中分配在低

負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。

這里Sk和心均取連續(xù)變量，它們的非整數(shù)值可以這樣理解，如Sk=0.6,就表示一臺機(jī)器

在k年度中正常工作時間只占6/10；uk=0.3,就表示一臺機(jī)器在該年度只有3/10的時間能

在高負(fù)荷下工作。

狀態(tài)轉(zhuǎn)移方程為：%]=a”*+b（s*-以）=0.7a*+0.9（必-〃*）,k=1,2,.--,5

k段允許決策集合為:Dk（sJ={uk\0<uk<sk}

設(shè)％區(qū),以）為第k年度的產(chǎn)量，那么.=8。+5（s?-uk）

5

故指標(biāo)函數(shù)為：L=??幾,以）

k=i

令最優(yōu)值函數(shù)fk（Sk）表示由資源量Sk出發(fā)，從第k年開始到第5年結(jié)束時所生產(chǎn)的產(chǎn)品

的總產(chǎn)量最大值。因而有逆推關(guān)系式：

從第5年度開始，向前逆推計(jì)算。

當(dāng)k=5時，有：

因f5是噸的線性單調(diào)增函數(shù)，故得最大解噸*，相應(yīng)的有：

當(dāng)k=4時，有：

故得最大解，U4*=S4，相應(yīng)的有

依此類推，可求得

因si=1000,故：/3）=23700

計(jì)算結(jié)果說明：最優(yōu)策略為

即前兩年應(yīng)把年初全部完好機(jī)器投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好機(jī)器投入高負(fù)

荷生產(chǎn)。這樣所得的產(chǎn)量最高，其最高產(chǎn)量為23700臺。

在得到整個問題的最優(yōu)指標(biāo)函數(shù)值和最優(yōu)策略后，還需反過來確定每年年初的狀態(tài)，即從

始端向終端遞推計(jì)算出每年年初完好機(jī)器數(shù)。si=1000臺，于是可得：

8、有一輛最大貨運(yùn)量為10t的卡車，用以裝載3種貨物，每種貨物的單位重量及相應(yīng)

單位價值如表4-20所示。應(yīng)如何裝載可使總價值最大？

表4-2

貨物編號i123

單位重量⑴345

單位價值ci456

解：建模設(shè)三種物品各裝為々,退件

利用動態(tài)規(guī)劃的逆序解法求此問題。

狀態(tài)轉(zhuǎn)移方程為：sk+l=Tk(sk,xk)=sk-xk,k=3,2,1

該題是三階段決策過程，故可假想存在第四個階段，而％=0,于是動態(tài)規(guī)劃的根本方程為:

計(jì)算最終結(jié)果為x；=2,x；=1,芯=0,最大價值為13o

9、設(shè)有A,B,C三部機(jī)器串聯(lián)生產(chǎn)某種產(chǎn)品，由于工藝技術(shù)問題，產(chǎn)品常出現(xiàn)次品。

統(tǒng)計(jì)結(jié)果說明，機(jī)器A,B,C產(chǎn)生次品的概率分別為PA=30%,PB=40%,Pc=20%,而產(chǎn)品

必須經(jīng)過三部機(jī)器順序加工才能完成。為了降低產(chǎn)品的次品率，決定撥款5萬元進(jìn)行技術(shù)

改造，以便最大限度地提高產(chǎn)品的成品率指標(biāo)?，F(xiàn)提出如下四種改良方案：

方案1：不撥款，機(jī)器保持原狀；

方案2：加裝監(jiān)視設(shè)備，每部機(jī)器需款1萬元；

方案3：加裝設(shè)備，每部機(jī)器需款2萬元；

方案4：同時加裝監(jiān)視及控制設(shè)備，每部機(jī)器需款3萬元；

采用各方案后，各部機(jī)器的次品率如表4-21。

表4-3

ABC

不撥款30%40%20%

撥款1萬元20%30%10%

撥款2萬元10%20%10%

撥款3萬元5%10%6%

問如何配置撥款才能使串聯(lián)系統(tǒng)的可靠性最大？

解：為三臺機(jī)器分配改造撥款，設(shè)撥款順序?yàn)锳,B,C,階段序號反向編號為k,即第一階

段計(jì)算給機(jī)器C撥款的效果。

設(shè)弘為第左階段剩余款，那么邊界條件為S3=5；

設(shè)必為第左階段的撥款額；

狀態(tài)轉(zhuǎn)移方程為Shl=Sk-覘；

目標(biāo)函數(shù)為max7?=(l-PA)(l-PB)(l-Pc)

仍采用反向遞推

第一階段：對機(jī)器C撥款的效果

勺電內(nèi)尸苗⑻內(nèi)“%0。，和尸"1(包,無1)

0123XI*Ri

SiGl,X1*）

00.800.8

10.80.910.9

20.80.90.91,20.9

30.80.90.90.9430.94

40.80.90.90.9430.94

50.80.90.90.9430.94

第二階段：對機(jī)器B,C撥款的效果

由于機(jī)器A最多只需3萬元，故s法2

遞推公式：

7?2(52，%2)=12(52，%2)*勺G1，勺*)

例：氏2(3,2)=12(3,2*勺(1,1)=(1-0.2)x0.9=0.72

得第二階段最優(yōu)決策表

Xi*Ri

Si（Sl,Xi*）

000.8

110.9

21,20.9

330.94

430.94

530.94

0123X2*Ri

S2(S2,必*)

20.540.630.6420.64

30.5640.630.720.722,30.72

40.5640.6580.720.8130.81

50.5640.6580.7520.8130.81

第三階段：對機(jī)器A,B,C撥款的效果

邊界條件：§3=5

遞推公式：

氏3（5343）="3（5353叢夫2（52/2*）

例：7?3(5,3)=13(5,3*氏2(2,2)=(1005)x0.64=0.608

S2

I：尤3=1，％2=3,%1=1,尺3=0.8x0.9x0,9=0.648

II：叼=2,硒=2,町=1,7?3=0.9X0,8X0.9=0.648

III：叼=2,%2=3,町=0,尺3=0.9x0.9x0.8=0.648

練習(xí)題五

1、考察多目標(biāo)規(guī)劃問題

—X+2,—

其中工(x)=x\/(x)=<1,1<X<2,試畫出個目標(biāo)函數(shù)的圖形，并求出

x-1,x>2

居,4M，尺“這里凡是要2力(了)的最優(yōu)解集。

解：

2、用線性加權(quán)法中的a-法求解下述多目標(biāo)規(guī)劃問題

min(x)=4玉+6x2

maxf2(x)=3玉+3x2。

2x1+4X2<14

s.t.<6xx+3X2<24

XVX2>Q

解：min力(%)=4玉+6々最優(yōu)解為X(D=[O0]T；

T

maxf2(x)=3%+3x2最優(yōu)解為乂⑵=[32]；

利用。法得線性方程組：

解得唯一加權(quán)系數(shù)2=O3846,0.61541T

原多目標(biāo)規(guī)劃加權(quán)后

解得加權(quán)后的最優(yōu)解為：x*=[40]T,最優(yōu)值為-1.2312

3、用線性加權(quán)求和法求解下述多目標(biāo)規(guī)劃問題，取4=064=0.4。

解：將問題轉(zhuǎn)化為一個新的單目標(biāo)規(guī)劃問題。

約束條件同上，該問題轉(zhuǎn)化為線性規(guī)劃問題，可用單純形法求解，也可用Matlab命令

求解〔求解過程略)。

解得加權(quán)后的最優(yōu)解為：x*=[01『，最優(yōu)值為-1.4。

4、用平方和加權(quán)法求解多目標(biāo)規(guī)劃問題：

xy-x2<4

[2

其中/j(x)=X],￡(x)=%，D;<xx+x2<8,4=§，4=§。

,x2>0

解：不難看出兩個目標(biāo)函數(shù)下界均為0,得平方和加權(quán)法后的新目標(biāo)規(guī)劃問題：

利用matlab程序求解

首先建立目標(biāo)函數(shù)及其梯度函數(shù)的M文件

functionf=fun(x)

f=l/3*x(l)人2+2/3*x(2)*x(2);

4

[x,fval]=fmincon(f\[00],[l-1;11],[4;8],[],[],[00])

解得最優(yōu)解為：x*=[00]T,最優(yōu)值為0。

5、用極小極大法和Matlab軟件求解下述多目標(biāo)規(guī)劃問題

227

v-minF(x)=((Xj-3)+(x2-2))

o

S.t.玉+%2<2

解：取評價函數(shù)為v(b(%))=max[(%]-3)2+￥，%；+(%-2)2],再求

i

Matlab軟件求解：

編制M文件

functionf=mnmax(x)

f(l)=(x(l)-3)A2+x(2)A2;

f(2)=x(l)A2+(x(2)-2)A2

設(shè)初值

x0=[