最优化方法练习题答案

练习题一

1、建立优化模型应考虑哪些要素？

答：决策变量、目标函数和约束条件。

2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准那么。

min/(x)

答：针对一般优化模型g,(x)>0,z=l,2,m,讨论解的可行域。，假设存在一点

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

X*eD,对于VXw。均有/(X*)</(X)那么称X*为优化模型最优解，最优解存在；迭代

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

1111(M)W

迭代法收敛;收敛的停止准那么有卜--叫<£,..(n||<g,|/(X)-/(X)|<£，

练习题二

1、某公司看中了例2.1中厂家所拥有的3种资源Ri、R2、和R3,欲出价收购(可能

用于生产附加值更高的产品)。如果你是该公司的决策者，对这3种资源的收购报价是多

少？(该问题称为例2.1的对偶问题)。

解：确定决策变量对3种资源报价冷火，%作为本问题的决策变量。

确定目标函数问题的目标很清楚一一“收购价最小”。

确定约束条件资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。

因此有如下线性规划问题：min攻=170%+100%+150%

*2、研究线性规划的对偶理论和方法(包括对偶规划模型形式、对偶理论和对偶单纯

形法)。

答：略。

3、用单纯形法求解以下线性规划问题：

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

因检验数。2<0,故确定X2为换入非基变量,以XI的系数列的正分量对应去除常数列,

最小比值所在行对应的基变量X4作为换出的基变量。

CL1-11000

CB基bX1尤4X3X4X5X6

-1xi211-2100

0X5110[3]-110

QX64-101001

Cj-Zj20-1100

因检验数O3<0,故确定X3为换入非基变量,以X3的系数列的正分量对应去除常数列,

最小比值所在行对应的基变量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

因检验数5>。，说明已求得最优解：X*=(0,8/3,1/3,0,0,11/3),去除添加的松弛变量,

原问题的最优解为：X*=(0,8/3,1/3)o

[2)根据题意选取XI,%4,%5,为基变量：

C.L0-1100

CB基bXIX2X3X4X5

0XI21-2100

0X420[1]-210

0X5501101

Cj-Zj0-1100

因检验数s<0最小，故确定X2为换入非基变量，以及的系数列的正分量对应去除常数

列，最小比值所在行对应的基变量X4作为换出的基变量。

CL0-1100

CB基bXIX2%3X4X5

0xi610-320

-1X22Ol-2io

0xs300[3]-11

Cj-Zj00-110

因检验数O3<0最小，故确定X3为换入非基变量，以XI的系数列的正分量对应去除常数

列，最小比值所在行对应的基变量X5作为换出的基变量。

CL0-1100

CB基匕XIX2X3X4X5

0xi910011

-1X240101/32/3

1X31001-1/31/3

Cj-Zj0002/31/3

因检验数5>0,说明已求得最优解：X*=(9,4,1,0,0)。

4、分别用大”法、两阶段法和Matlab软件求解以下线性规划问题:

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

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

⑴s.t.<9X1+3%2-6；⑵“l5X1+6%2+15叼415

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

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

解：（1）大M法

根据题意约束条件1和2可以合并为1,引入松弛变量X3,X4,构造新问题。

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

因检验数5>0,说明已求得最优解：X*=(3/5,6/5)o

Matlab调用代码：

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)

输出结果：

Optimizationterminated.

x=

0.6000

1.2000

fval=

3.6000

(2〕大M法

引入松弛变量X4,X5,X6,X7构造新问题。

单纯形表计算略；当所有非基变量为负数，人工变量匕=0.5,所以原问题无可行解。

请同学们自己求解。

Matlab调用代码：

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)

输出结果：

原题无可行解。

5、用内点法和Matlab软件求解以下线性规划问题：

解：用内点法的过程自己书写，参考答案：最优解X=[4/37/30]；最优值5

Matlab调用代码：

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)

输出结果：

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且均为整数xr,x220且刈为整数

解：(1)调用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

最优解[33]；最优值39

⑵调用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

最优解［50］；最优值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)分别带入到约束条件中，可以得到：原问题的最优解是(0,0,1),目标函

数最优值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〕分别带入到约束条件中，可以得到：原问题的最优解是(1,1,0,0,

0),目标函数最优值-5。

Matlab软件求解：

⑴

调用代码:

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

A=[2,-5,3；%不等式约束系数矩阵A,□中的分号“；”％为行分隔符

b=[4;-3;-l];%不等式约束右端常数向量b

[x,fval]=bintprog(f,A,b,[],[]);%调用函数bintprog。注意两个空数组的占位作用。

输出结果

X二

0

0

1

fval=

2

⑵

调用代码:

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

A=[l,l,1,2,1;7,0,3,-4,3；-11,6,0,-3,3];%不等式约束系数矩阵A,□中的分号“；”％为行分隔符

b=[4;8;-1];%不等式约束右端常数向量b

[x,fval]=bintprog(f,A,b,[],[]);%调用函数bintprog。注意两个空数组的占位作用。

输出结果

x=

1

0

0

0

fval=

最优值5。

8、某地区有A、B、C三个化肥厂，供给本地甲、乙、丙、丁四个产粮区。各化肥厂

可供给化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28

所示。试制定一个使总运费最少的化肥调拨方案。

表2-1

运价/7粮

甲乙丙T各厂供给量/万吨

化肥厂

Ai58737

A2491078

A384293

各区需要量/万吨6633

解：设A、B、C三个化肥厂为Ai、A2、A3,甲、乙、丙、丁四个产粮区为Bi、B2、

B3、B4;Q为由Ai运化肥至Bj的运价，单位是元/吨；瓶为由Ai运往Bj的化肥数量

（i=l,2,3;j=l,2,3,4〕单位是吨；z表示总运费，单位为元，依题意问题的数学模型为：

该题可以用单纯形法或matlab自带工具箱命令［linprog）求解。

*9、求解以下不平衡运输问题（各数据表中，方框内的数字为单位价格回，框外右侧

的一列数为各发点的供给量%,框底下一行数是各收点的需求量%）：

要求收点3的需求必须正好满足。

要求收点1的需求必须由发点4供给。

解答略。

10、一公司经理要分派4位推销员去4个地区推销某种商品。推销员各有不同的经验

和能力，因而他们在不同地区能获得的利润不同，其获利估计值如表2-29所示。公司经理

应怎样分派才使总利润最大？

表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标号

18074

最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：

p106(|叫

1268()*

(0)1102

1aQ⑼/n\4/I

未被直线覆盖的最小元素为叼=2,在未被直线覆盖处减去2,在直线交叉处加上2。

"1000

00

J得最优解:0标号

0Upj------IX.

、010

・•.使总利润为最大的分配任务方案为:

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

此时总利润W=35+40+32+32=139

练习题三

1、用0.618法求解问题

的近似最优解，。⑺的单谷区间为[0,3],要求最后区间精度£=0.5。

答：t=0.8U5；最小值-0.0886.(调用golds.m函数)

2、求无约束非线性规划问题

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

的最优解

解一：由极值存在的必要条件求出稳定点：

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

dxxdx2dx3一

再用充分条件进行检验：

2222

d~f.dfodf,dfnd2fndf„

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

’200、

即y2/=080为正定矩阵得极小点为x*=(l,0,0)T,最优值为-1。

1002)

解二：目标函数改写成

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

易知最优解为[1,0,0),最优值为-1。

3、用最速下降法求解无约束非线性规划问题。

其中X=(再,无2尸，给定初始点X°=(0,01。

⑪'(X)

。(七)1+4%+2X

解一:目标函数/(X)的梯度W(x)=2

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

。(％2)

1-1

V/,(X(0))=令搜索方向d(i)=-W(X(°))=再从X(°)出发，沿d⑴方向作一维寻优,

—11

令步长变量为2,最优步长为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⑴点之后，与上

类似地，进行第二次迭代：vf（x（1））=令F=-vf（x（D）=

一1

令步长变量为2,最优步长为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此时所到达的精度||W(X⑵)卜0.2828

此题最优解X*=:;,/(X*)=-1,25

解二：利用matlab程序求解

首先建立目标函数及其梯度函数的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)];

调用grad.m文件

x0=[0,0];

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

结果

x=[-1.0000,1.5000]

val=-1.2500

k=33

即迭代33次的到最优解x=[-1.0000,1.5000]；最优值val=-1.2500。

4、试用Newton法求解第3题。

解一：计算目标函数的梯度和Hesse阵

第(x)

。(西)1+4%+2X

目标函数/Xx)的梯度Vf(x)=2

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

。(%2)

420.5-0.5

V2/(X)=22=G，其逆矩阵为G-I

-0.51

计算|W(x(叫=0。

此题最优解X*=:[,/(X*)=-1,25

解二：除了第3题建立两个M文件外，还需建立Hesse矩阵的M文件

利用matlab程序求解

首先建立目标函数及其梯度函数的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];

调用newton.m文件

x0=[0,0];

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

结果

x=[-1.0000,1.5000]

val=-1.2500

k=l

5、用Fletcher一Reeves法求解问题

其中X=&,々尸，要求选取初始点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尸……(建议同学们自己做下去，注意判别㈤归力

解二：利用matlab程序求解

首先建立目标函数及其梯度函数的M文件

functionf=fun(x)

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

functiong=gfun(x)

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

调用frcg.m文件

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

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

结果

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

val=7.2182e-014

k=61

6、试用外点法[二次罚函数方法〕求解非线性规划问题

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

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

2

其中X=(x15x2)eR

解：设计罚函数P(x,M)=/(X)+M*[g(X)]人2

采用Matlab编程计算，结果x=[l0]；最优结果为1。(调用waidianfa.m)

7、用内点法〔内点障碍罚函数法)求解非线性规划问题：

解：容易看出此问题最优解为x=[l0]；最优值为8.

给出罚函数为尸(x,r)=(为+1尸+々+r(l/(为-1)+1/9)

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

玉(七一1)x2%；

从而当厂―0时，x(r)=f=x

7rJ⑼

1建议同学自己编程序计算)

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

解：建立乘子法的增广目标函数：

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

阴

解上述关于x的二元一次方程组得到稳定点

当乘子2取2时，或发参数〃趋于无穷时，得到元=；=x*即最优解。

1建议同学自己编程序计算)

练习题四

1、石油输送管道铺设最优方案的选择问题：考察网络图4-6,设A为出发地，F为目

的地，B,C,D,E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设

的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？

图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；

最优解：A—Bl—C2—D2—E2—F最优值：17

2、用动态规划方法求解非线性规划

解：xi—9,x2—9,xi—9,最优值为9。

3、用动态规划方法求解非线性规划

解：用顺序算法

阶段：分成两个阶段，且阶段1、2分别对应办,%。

决策变量：石,々

状态变量：+叫分别为第/阶段第一、第二约束条件可供分配的右段数值。

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

0<^2<52

可解的％=9.6,々=0.2,最优值为702.92。

4、设四个城市之间的公路网如图4-7o两点连线旁的数字表示两地间的距离。使用迭

代法求各地到城市4的最短路线及相应的最短距离。

图4-2城市公路网

解：城市1到城市4路线一一1-3-4距离10；

城市2到城市4路线一一2-4距离8；城市3到城市4路线一一3-4距离4。

5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区

设置不同数量的销售点每月可得到的利润如表4-19所示。试问在各地区如何设置销售点可

使每月总利润最大。

表4-1

解：

将问题分为3个阶段，k=l,2,3；

决策变量也表示分配给第k个地区的销售点数；

状态变量为s左表示分配给第左个至第3个地区的销售点总数；

状态转移方程：S左+]=s左一X左，其中S]=4；

允许决策集合：D,[sA=

AV/vAV/V/v

阶段指标函数：g左表示々个销售点分配给第左个地区所获得的利润；

最优指标函数〃(6攵)表示将数量为V的销售点分配给第k个至第3个地区所得到的最大

利润，动态规划根本方程为：

上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

最优解为：町*=2,x2*=l,X3*=L4(4)=47,即在第1个地区设置2个销售点，第2个地

区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。

6、设某厂方案全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤,

500公斤和1200公斤。生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内

有仓库可存放产品，存储费为每公斤每季度1元。求最正确的生产安排使年总本钱最小。

解：四个季度为四个阶段，采用阶段编号与季度顺序一致。

设必为第左季初的库存量，那么边界条件为si=S5=0

设乙为第左季的生产量，设株为第左季的订货量；s左，"都取实数，状态转移方程

为我+l=sk+%-株仍采用反向递推，但注意阶段编号是正向的目标函数为：

第一步：（第四季度）总效果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）得：

由此回溯：得最优生产-库存方案

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

7、某种机器可在上下两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数

为g=8Mi,其中Ml为投入生产的机器数量，年完好率。=0.7；在低负荷下生产的产量函数为

h=5y,其中y为投入生产的机器数量，年完好率为6=0.9。假定开始生产时完好机器的数量

51=1000。试问每年如何安排机器在高、低负荷下的生产，使在5年内生产的产品总产量最

高。

解：

构造这个问题的动态规划模型：

设阶段序数k表示年度。

状态变量sk为第k年度初拥有的完好机器数量，同时也是第k-1年度末时的完好机器数量。

决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk-uk为该年度中分配在低

负荷下生产的机器数量。

这里Sk和心均取连续变量，它们的非整数值可以这样理解，如Sk=0.6,就表示一台机器

在k年度中正常工作时间只占6/10；uk=0.3,就表示一台机器在该年度只有3/10的时间能

在高负荷下工作。

状态转移方程为：%]=a”*+b（s*-以）=0.7a*+0.9（必-〃*）,k=1,2,.--,5

k段允许决策集合为:Dk（sJ={uk\0<uk<sk}

设％区,以）为第k年度的产量，那么.=8。+5（s«-uk）

5

故指标函数为：L=»?几,以）

k=i

令最优值函数fk（Sk）表示由资源量Sk出发，从第k年开始到第5年结束时所生产的产品

的总产量最大值。因而有逆推关系式：

从第5年度开始，向前逆推计算。

当k=5时，有：

因f5是吨的线性单调增函数，故得最大解吨*，相应的有：

当k=4时，有：

故得最大解，U4*=S4，相应的有

依此类推，可求得

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

计算结果说明：最优策略为

即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负

荷生产。这样所得的产量最高，其最高产量为23700台。

在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从

始端向终端递推计算出每年年初完好机器数。si=1000台，于是可得：

8、有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的单位重量及相应

单位价值如表4-20所示。应如何装载可使总价值最大？

表4-2

货物编号i123

单位重量⑴345

单位价值ci456

解：建模设三种物品各装为々,退件

利用动态规划的逆序解法求此问题。

状态转移方程为：sk+l=Tk(sk,xk)=sk-xk,k=3,2,1

该题是三阶段决策过程，故可假想存在第四个阶段，而％=0,于是动态规划的根本方程为:

计算最终结果为x；=2,x；=1,芯=0,最大价值为13o

9、设有A,B,C三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。

统计结果说明，机器A,B,C产生次品的概率分别为PA=30%,PB=40%,Pc=20%,而产品

必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款5万元进行技术

改造，以便最大限度地提高产品的成品率指标。现提出如下四种改良方案：

方案1：不拨款，机器保持原状；

方案2：加装监视设备，每部机器需款1万元；

方案3：加装设备，每部机器需款2万元；

方案4：同时加装监视及控制设备，每部机器需款3万元；

采用各方案后，各部机器的次品率如表4-21。

表4-3

ABC

不拨款30%40%20%

拨款1万元20%30%10%

拨款2万元10%20%10%

拨款3万元5%10%6%

问如何配置拨款才能使串联系统的可靠性最大？

解：为三台机器分配改造拨款，设拨款顺序为A,B,C,阶段序号反向编号为k,即第一阶

段计算给机器C拨款的效果。

设弘为第左阶段剩余款，那么边界条件为S3=5；

设必为第左阶段的拨款额；

状态转移方程为Shl=Sk-觇；

目标函数为max7?=(l-PA)(l-PB)(l-Pc)

仍采用反向递推

第一阶段：对机器C拨款的效果

勺电内尸苗⑻内“%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

第二阶段：对机器B,C拨款的效果

由于机器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

得第二阶段最优决策表

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

第三阶段：对机器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

练习题五

1、考察多目标规划问题

—X+2,—

其中工(x)=x\/(x)=<1,1<X<2,试画出个目标函数的图形，并求出

x-1,x>2

居,4M，尺“这里凡是要2力(了)的最优解集。

解：

2、用线性加权法中的a-法求解下述多目标规划问题

min(x)=4玉+6x2

maxf2(x)=3玉+3x2。

2x1+4X2<14

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

XVX2>Q

解：min力(%)=4玉+6々最优解为X(D=[O0]T；

T

maxf2(x)=3%+3x2最优解为乂⑵=[32]；

利用。法得线性方程组：

解得唯一加权系数2=O3846,0.61541T

原多目标规划加权后

解得加权后的最优解为：x*=[40]T,最优值为-1.2312

3、用线性加权求和法求解下述多目标规划问题，取4=064=0.4。

解：将问题转化为一个新的单目标规划问题。

约束条件同上，该问题转化为线性规划问题，可用单纯形法求解，也可用Matlab命令

求解〔求解过程略)。

解得加权后的最优解为：x*=[01『，最优值为-1.4。

4、用平方和加权法求解多目标规划问题：

xy-x2<4

[2

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

,x2>0

解：不难看出两个目标函数下界均为0,得平方和加权法后的新目标规划问题：

利用matlab程序求解

首先建立目标函数及其梯度函数的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])

解得最优解为：x*=[00]T,最优值为0。

5、用极小极大法和Matlab软件求解下述多目标规划问题

227

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

o

S.t.玉+%2<2

解：取评价函数为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

设初值

x0=[