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

練習(xí)題一

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

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

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

min/（x）

答:針對(duì)一般優(yōu)化模型g,.（尤）20,i=l,2,相，討論解的可行域。，若存在一點(diǎn)

hj（x）=0,j=1,,p

X*w對(duì)于VXGZ）均有f（X"）＜/（X）則稱X*為優(yōu)化模型最優(yōu)解,最優(yōu)解存在;迭代算

法的收斂性就是指迭代所得到的序列X?X⑵，,X（K）法足f（X（K+D）W/（X（K））,則

迭代法收斂;收斂的停止準(zhǔn)則有

X伏+1)＜邛產(chǎn)）-/（叫

|可（尤叫＜￡等等。

練習(xí)題二

1、某公司瞧中了例2、1中廠家所擁有的3種資源Ri、R2、與R3,欲出價(jià)收購(gòu)（可能

用于生產(chǎn)附加值更高的產(chǎn)品）。如果您就是該公司的決策者，對(duì)這3種資源的收購(gòu)報(bào)價(jià)就

是多少？（該問(wèn)題稱為例2、1的對(duì)偶問(wèn)題）。

解:確定決策變量對(duì)3種資源報(bào)價(jià)九%，%作為本問(wèn)題的決策變量。

確定目標(biāo)函數(shù)問(wèn)題的目標(biāo)很清楚一一“收購(gòu)價(jià)最小二

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

因此有如下線性規(guī)劃問(wèn)題:minw=170y+100%+150%

5%+2%+為N10

s.J2y+3y2+5%N18

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

形法）。

答:略。

3、用單純形法求解下列線性規(guī)劃問(wèn)題:

minz=X]-x2+與minz=4-%2+町

X]+冗2—2巧W2X]—2工2+無(wú)3=2

2勺+工2+工3—3.%2―213+工4=2

⑴s，⑵."

X|+工3?4X2+町+彳5=5

可，工2，工320Xj>0(z=1,2,…,5)

解：(1)引入松弛變量尢42,X6

minz=x]-x2+七+0*%+0*/+0*x6

4-

x}+x2-2X3x4=2

2x,+x,+&+x5=3

s.t.<

-xl+x3+x6=4

xl,x2,x3,x4,x5,x6>0

1-11000

CB基bXIX2X3X4X5X6

0X421[1]-2100

0X53211010

0X64-101001

Cj-Zj1-11000

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

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

CjT1-110oo

CB基bXlX4X3X4X5X6

-1X2211-2100

0X5110[3]-110

0入64-101001

Cj-Zj20-1100

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

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

1-11000

CB基bX]X2X5X4X5X6

-1X28/35/3101/32/30

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

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

Cj-Zj7/3032/31/30

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

原問(wèn)題的最優(yōu)解為:X*=(0,8/3,1/3)。

(2)根據(jù)題意選取XI,A4,X5,為基變量:

minz=4-+與

X]—2%2+工3=2

X?-2%3+=2

+工3+工5=5

Xi>0(i=1,2,…,5)

CL0-1100

CB基bXIX2X3X4X5

0xi21-2100

0[1]-210

0x42

0X5501101

q-40-110o

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

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

CL0-1100

a基bXIX2X3X4X5

0X]610-320

-iX2201-210

0X5300[3]-11

Cj-Zj00-110

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

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

CL0-1100

CB基bXIX2X3X4X5

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)o

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

minZ=4Xj+工2max:z=10%)+15%2+12%3

3xj+冗2=35x\+3%2+工349

9%|+3x2>6.

⑴/5⑵S.A—5x]+6%2+15%3—15

X\+2x2-32~+%2+25

X],%2-0%],&，4-0

解:(1)大M法

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

minz=4x(+x2+Mx3+0*x4

3工]+x2+x3=3

s.t.<xt+2X2+*4=3

%,x4>0

CL41M0

CB基bXIX2X3X4

MX33[3]110

0X431201

Cj-Zj4-3M1-M00

4XI111/31/30

0X420[5/3]-1/31

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

4X\3/5102/5-1/5

1X26/501-1/53/5

Cj-Zj00M-7/51/5

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

Matlab調(diào)用代碼：

閆4;1];

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

b=[-6;3];

Aeq=[3,l];

beq=3;

lb=fO;O];

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

輸出結(jié)果：

Optimizationterminated>

X=

0、6000

1、2000

fval=

3、6000

⑵大M法

引入松弛變量X4/546M構(gòu)造新問(wèn)題o

maxz=IO%,+15x2+12%+0x4+0x5+0x6-Mx1

5%+3X2+X3+X4=9

-5%+6x2+15X3+x5=15

2X]+x2+x3-x6+x7=5

%,，龍7NO

單純形表計(jì)算略;當(dāng)所有非基變量為負(fù)數(shù)，人工變量今=0、5,所以原問(wèn)題無(wú)可行解。

請(qǐng)同學(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é)果：

原題無(wú)可行解。

5、用內(nèi)點(diǎn)法與Matlab軟件求解下列線性規(guī)劃問(wèn)題:

minz=2犬]+冷+%3

X]+2^2+2犬3=6

2修+%2=5

X],，叼20

解:用內(nèi)點(diǎn)法的過(guò)程自己書(shū)寫(xiě)，參考答案:最優(yōu)解X=[4/37/30];最優(yōu)值5

Matlab調(diào)用代碼：

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

beq=[6;5];

lb=[O;O;O];

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

輸出結(jié)果：

Optimizationterminated、

1、3333

2、3333

0、0000

fval=

5、0000

6、用分支定界法求解下列問(wèn)題:

maxz=5%|+maxZ=7X[+9X2

X]+46—X]+3x2—6

⑴s.t.<5x]+9》2-45，⑵s/r1x\+x2-35

和.20且均為整數(shù)X|,x2NO且X]為整數(shù)

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

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

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

33

y=

-39

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

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

f=[-7;-9];G=[-l3;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軟件求解下列問(wèn)題:

z=4x\+3^2+213z—3xj+2%2—5與—214+3和

2尤]—5工2+3工3—4X]+工2++2工4+15<4

4-Xj+X2+3工3—37%|+3工3—414+3%5<8

；(2)s.”

了2+町之111XJ—6%2+3工4—3X5—1

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

解：隱枚舉法：

(1)將(0,0,0)(0,0』)(0』,0)(1,0,0)(0,1,1)(1,0,1)(1,1,0)(L1,1)分別帶入至I」約束條件中，可以

得到:原問(wèn)題的最優(yōu)解就是(0,0,1),目標(biāo)函數(shù)最優(yōu)值2、

(2)W(o,0,0,0,0)(0,0,0,0,1)(0,0,0,1,0)(0,0,1,0,0)…、(1,1,1,1,1)分別帶入到約束條件中,

可以得至I」:原問(wèn)題的最優(yōu)解就是(1,1,0,0,0),目標(biāo)函數(shù)最優(yōu)值-5。

Matlab軟件求解：

(1)

調(diào)用代碼:

f=[4;3;2];%價(jià)值向量/

A=[2,-5,3；-4,-l,-3;0,-I,-l];%不等式約束系數(shù)矩陣A,口中的分號(hào)“：％為行分隔符

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

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

輸出結(jié)果

0

0

調(diào)用代碼:

f=[-3;-2;5;2;3];%價(jià)值向量/

A=[l,l,l,2,l;7,0,3,-4,3;-ll,6,0,-3,3]；%不等式約束系數(shù)矩陣A,國(guó)中的分號(hào)";"％為行分隔符

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

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

輸出結(jié)果

0

0

最優(yōu)值5。

8、某地區(qū)有A、B、C三個(gè)化肥廠,供應(yīng)本地甲、乙、丙、丁四個(gè)產(chǎn)糧區(qū)。已知各

化肥廠可供應(yīng)化肥的數(shù)量與各產(chǎn)糧區(qū)對(duì)化肥的需要量，以及各廠到各區(qū)每噸化肥的運(yùn)價(jià)

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

表2-1

運(yùn)價(jià)/7糧

甲乙丙T各廠供應(yīng)量/萬(wàn)噸

化肥廠

Ai58737

A2491078

A384293

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

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

B3、B4；Q為由Ai運(yùn)化肥至B.i的運(yùn)價(jià)，單位就是元/噸;刈為由Ai運(yùn)往B.i的化肥數(shù)量

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

34

minz=￡Zc匹

/=17=1

孫+徹+工31=6

4-x+X32=

x12226

石3+%+尤33=3

s.t.<34+工24+玉4=3

xu+x12+xl3+x14=7

X2I+X22+X23+X24=8

產(chǎn)31+“32+工33+“34=7

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

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

一列數(shù)為各發(fā)點(diǎn)的供應(yīng)量&，框底下一行數(shù)就是各收點(diǎn)的需求量%):

(1)5I17—lo要求收點(diǎn)3的需求必須正好滿足。

64680

32515

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

解答略。

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

驗(yàn)與能力，因而她們?cè)诓煌貐^(qū)能獲得的利潤(rùn)不同，其獲利估計(jì)值如表2-29所示。公司經(jīng)

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

表2-2

區(qū)

推就、1234

135272837

228342940

335243233

424322528

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

效率矩陣表示為：

「35272837'r513123、

M-Cii行約簡(jiǎn)

28342940126110,______F\

1>1>

3524323351687

M=40

<24322528,(1681512,

(

2106(0)

(21090、

12680*

126110列約簡(jiǎn)

1>/所畫(huà)00元素少于n(n=

01132(0)110*2

標(biāo)號(hào)

<8074,I8(0)44J

4),未得到最優(yōu)解,需要繼續(xù)變換矩陣(求能覆蓋所有0元素的最少數(shù)直線集合):

???使總利潤(rùn)為最大的分配任務(wù)方案為：

If1,2f4,3f3,4f2

此時(shí)總利潤(rùn)W=35+40+32+32=139

練習(xí)題三

1、用0、618法求解問(wèn)題

min0⑺=F+1

?>0

的近似最優(yōu)解，已知8⑺的單谷區(qū)間為［0,31，要求最后區(qū)間精度￡=05。

答:t=0、8115;最小值-0、0886、(調(diào)用golds、m函數(shù))

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

2

min/(xl,x2,x3)=x1++x；-2%

的最優(yōu)解

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

里=2%—2,@=8為,且=2七,則由0(x)=()得玉=1,%=0,七=。

陰dx2dx3

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

2222

d\f9a/8a/9dfdfd\f

端困dx^dx{dx23%竭dx2dx3

’200、

即守/=o80為正定矩陣得極小點(diǎn)為戶=(1,0,0)\最優(yōu)值為-1。

、。02,

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

2

min/(xl,x2,x3)=(x1-1)++x；—1

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

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

min/(X)=%,-x2+++xj

其中X=(%,々尸，給定初始點(diǎn)X。=(0,0)，o

幽)1+4x,+2X

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

彌x)—1+2玉+2,x2

a?)

YAX(s)=1令搜索方向d⑴=-W(X<°))=一再?gòu)腦(°)出發(fā)，沿d⑴方向作一維尋優(yōu),

—11

-0]「一1]P-2-

令步長(zhǎng)變量為X,最優(yōu)步長(zhǎng)為4,則有X(°)+/Wa)=+2=

01A

故/(x)=/(X<0)+AJ(1))=(-2)-^+2(-2)2+2(-/)2+Z2=22-22=(2)

O「一11「一「

令例(乃=2/1-2=0可得4=1X⑴=X(°)+4d⑴=0+]=]求出X⑴點(diǎn)之后，與

上類似地，進(jìn)行第二次迭代:W(X(D)=「I]令〃⑵=-V/(X⑴)=1

令步長(zhǎng)變量為4,最優(yōu)步長(zhǎng)為4,則有

2-1

X⑴+幾/2)=-+

1J|_1A+1

故

f(x)=/(X⑴+⑵)=(2-1)-(2+1)+2(2-1)2+2(2-1)(2+1)+(2+1)2=522-22-1=/(4)

i「一11i「f]「一o」

令仍(㈤=l(U-2=0可得=-X*21=X0為d"]+(]=]]

~A9-

Vf(x(2>)=旬2此時(shí)所達(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(l)*x(l)+2*x(l)*x(2)+x(2)*x(2);

functiong=gfun(x)

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

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

x0=[0,0];

(x,val,k]=grad('fun','gfun',xO)

結(jié)果

x=[-l>0000,K5000]

val=-k2500

k=33

即迭代33次的到最優(yōu)解x=[-l、0000,E5000];最優(yōu)值val=-l、2500。

4、試用Nev"。"法求解第3題。

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

4(x)

。(西)1+4芯+2X

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

歹(X)—1+2Xj+2%2

改無(wú)2)

~42~

22=G,其逆矩陣為G

X⑴=X@—G”(X(s)=[0,0]，—二[1,一

計(jì)算|W（X（D）|=O。

本題最優(yōu)解X*=15,/(%,)=-1,25

解二:除了第3題建立兩個(gè)M文件外，還需建立Hesse矩陣的M文件

利用matlab程序求解

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

functionf=fun(x)

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

functiong=gfun(x)

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

functionh=hess(x)

g=[42;22];

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

xo=ro,o]；

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

結(jié)果

x=[-l>0000,K5000]

val=-1>2500

k=l

5、用FiefMe，—Reeves法求解問(wèn)題

minf(X)=x；+25x；

其中X=(X,，W)T,要求選取初始點(diǎn)乂°=(2,2)。￡=10"。

解一：

1「20]「xJ「20]1

r

/(x)=-(^,x2)/，G=,r=V/(x)=(2x,,50x2).

21050J[X2J1050

第一次迭代:令%=-2=(-4,-100)7,

4

(4,100)

r1001

_A2L_=________

Po'GPo_-oo)2OlP-450

(4)1050j[-100

即,X⑴=X(°)+4Po=(1.92,0尸

第二次迭代:

6=(3.84,())7,4=薯43

，A=—4+￡oPo=(-3.846,—O.15)T

IIroII-2000

T(3.84,0)

4r\0

a.=-?、!一=-----------j=-0.4802

p：Gp、/0-3.846

*H(-3.846,-0.15)(

50-0.15

X(2)=X⑴+?PL(0.0732,-0.072)r

第三次迭代：

^=(0.1464,-3.6/……(建議同學(xué)們自己做下去，注意判別限歸￡)

解二:利用matlab程序求解

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

functionf=fun(x)

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

functiong=gfun(x)

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

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

x0=[2,2]';epsilon=1e-6;

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

結(jié)果

x=l、0e-006*[0>2651,0、0088]

val=7>2182e-014

k=61

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

min/(X)=(X—2)2

<

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

其中X=(X”X2)GR2

解:設(shè)計(jì)罰函數(shù)P(X,/(為M*[g(X

采用Matlab編程計(jì)算，結(jié)果x=[l0];最優(yōu)結(jié)果為10（調(diào)用waidianfa、m）

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

r3

min(X[+l)'+12

<s.t.Xj-1>0

x2>0

解:容易瞧出此問(wèn)題最優(yōu)解為x=[l0];最優(yōu)值為8、

3

給出罰函數(shù)為P(x,^1>2X+r(1M+1)

令也±2=3(%+1)2-——=0;皿2=1_4=0

X]/x2

從而當(dāng)…0+時(shí).)=代歷)

(占j⑼

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

Jminf(X)=x；+6

8/2j(X)=xt+x2-2=0

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

y/(x,AfO")=X]~+一%(芭+%2―2)+—(X)+々-2)八2

令:MX'"Q)=2xi+b(z+x,-2)=0

兩

5^(x,2,cr)】，/,、八

---------=2x-Z+<T(X+x,-2)=0

dX[9'-

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

2。+2

—2b+2

x=

2。+4

_2。+2_

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

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

練習(xí)題四

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

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

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

解：

第五階段: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、用動(dòng)態(tài)規(guī)劃方法求解非線性規(guī)劃

maxf(x)=?+后+&

玉+%2+*3=

<一27

xl,x2,x3>0

解:玉=9,工2=9,當(dāng)=9,最優(yōu)值為9o

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

maxz=+6玉+5x1

s.t.+2X2<10

X

x1-32<9

X),x2>0

解:用順序算法

階段:分成兩個(gè)階段，且階段1、2分別對(duì)應(yīng)和當(dāng)。

決策變量：%,當(dāng)

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

/*(9,")=max{7x；+6玉}=min{7片+6片,7卬；+6%}

0<X|<H'|

x：=min{V[,小}

力*(%,w,)=max{5x1+f*(v2-2x2,w2+3x9)}

0<.r2<5

22

=max{5x;+min{7(v0-2x2)+6(v2-2x2),7(vv2+3x2)+6(%+3%)}}

0<X2<5

由于

2=1o,卬2=9,￡(彩,嗎)=4*(1o,9)=max{min{33x；-292%+760,68x；+396%+621}

0“2《5

可解的3=9.6,%=02,最優(yōu)值為702、92o

4,設(shè)四個(gè)城市之間的公路網(wǎng)如圖4-7。兩點(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個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場(chǎng)部門估計(jì)，在不同地區(qū)

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

點(diǎn)可使每月總利潤(rùn)最大。

表4-1

地俏售點(diǎn)

區(qū)01234

1016253032

2012172122

3010141617

解：

將問(wèn)題分為3個(gè)階段，由1,2,3;

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

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

狀態(tài)轉(zhuǎn)移方程：4+]=.%—1上,其中$]=4;

允許決策集合:。人%）={聞04聲S/}

階段指標(biāo)函數(shù):g%（q）表示xk個(gè)銷售點(diǎn)分配給第k個(gè)地區(qū)所獲得的利潤(rùn)；

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

利潤(rùn)，動(dòng)態(tài)規(guī)劃基本方程為：

'f1M=網(wǎng)lgk（須）+fk+l（般一項(xiàng)）]%=3,2,1

/（戛）=0

k=3時(shí)，力（S3）=max[g3（x3）]

X3F3

g3（巧）

力（$3）/*

01234

0000

110101

214142

316163

417174

仁2時(shí)“)=max[g2(%)+力(§2—巧)]

04“2W$2

g2（%2）切（$2一%2）

啟§2）%2*

01234

0000

10+1012+0121

20+1412+1017+0221

30+1612+1417+1021+0272

40+1712+1617+1421+1022+0312,3

后1時(shí)，工(S1)=max[g](a)+&6—%)],工(4)=1110\[&(/)+&(4—石)]

0<X|0<X|<4

4（%1）乜&一巧）*

工區(qū)）當(dāng)

01234

40+3116+2725+2230+1232+0472

最優(yōu)解為：丐*=2也*=1/3*=1/1（4）=47,即在第1個(gè)地區(qū)設(shè)置2個(gè)銷售點(diǎn)，第2個(gè)地區(qū)設(shè)置

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

6、設(shè)某廠計(jì)劃全年生產(chǎn)某種產(chǎn)品Ao其四個(gè)季度的訂貨量分別為600公斤,700公

斤,500公斤與1200公斤。已知生產(chǎn)產(chǎn)品A的生產(chǎn)費(fèi)用與產(chǎn)品的平方成正比,系數(shù)為0、

005o廠內(nèi)有倉(cāng)庫(kù)可存放產(chǎn)品，存儲(chǔ)費(fèi)為每公斤每季度1元。求最佳的生產(chǎn)安排使年總成

本最小。

解：四個(gè)季度為四個(gè)階段,采用階段編號(hào)與季度順序一致。

設(shè)Sk為第4季初的庫(kù)存量，則邊界條件為$1=8=0

設(shè)xk為第4季的生產(chǎn)量，設(shè)yk為第4季的訂貨量叫xk,yk都取實(shí)數(shù)，狀態(tài)轉(zhuǎn)移方

程為Sk+i=Sk+xk-”仍采用反向遞推,但注意階段編號(hào)就是正向的目標(biāo)函數(shù)為：

4

工（x）=miny（0.005x,2+5,.）

-2*3兇片

第一步:（第四季度）總效果分（$4^4）=°、005母2+$4

由邊界條件有:$5=$4+和->4=°，解得：*4*=1200-.以

將工4*代入為（54，工4）得：

2

必*（$4）=0、005（1200-$4）2+%=7200-1154+。、00554

第二步:（第三、四季度）總效果4（$3>*3）=°、005%32+53+a*（54）

將$4=$3+”3一500代入為G3K3）得:

f3（S3,￡）=0.005Xj+.8+7200-1l（x3+1v3-500）

+0.005（%3+邑-500）2

=0.0lx；+0.01X3S3-16X3+0.005S；-15%+13950

-，與）=+o.OLv,-16=0

c00.52xJ

dx3

解得x；=800-0.5*,代入力63,九3）得

力"（S3）=7550-7邑+0.0025s；

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

—（$2X2）=。、005-2+設(shè)+-*（$3）

將$3=s2+x2-700代入力（$2/2）得：

f2（s2,x2）=0.005%2+邑+7550-7（%+與一700）

2

+0.0025（X2+S2-700）

%色i）=0.0159+0.005（“-700）-7=0

dx2

解得X；=700-（1/3）52,代入以S2,々）得

于；G）=10000-6S2+（0.005/3）$

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

力（.”,町）=0、005xj+s[+力*（$2）

將s2=51+X1_600=xj-600代入力（5]5%1）得：

于、（S[,%）=0.005X：+S]+10000一6（玉一600）

+（0.005/3）（玉—600）2

或結(jié)拈=（0.04/3）%-8=0

dx]

解得x；=600,代入力G，X）得

<*5）=11800

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

》]*=600,$2*=0；*2*=700,S3*=0；彳3*=800,$4*=300;*4*=900。

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

函數(shù)為g=8〃i,其中“I為投入生產(chǎn)的機(jī)器數(shù)量，年完好率。=0、7;在低負(fù)荷下生產(chǎn)的產(chǎn)量函

數(shù)為/『5y,其中y為投入生產(chǎn)的機(jī)器數(shù)量,年完好率為從0、9o假定開(kāi)始生產(chǎn)時(shí)完好機(jī)器

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

總產(chǎn)量最高。

解：

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

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

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