最优化方法练习题答案修改建议版本--删减版

1、建立优化模型应考虑哪些要素? 答：决策变量、目标函数和约束条件。

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

minf(x)tgix0,i1,2,m，讨论解的可行域D，若存在一点X*D，对答：针对一般优化模型s.. hjx0,j1,,p于XD 均有f(X*)f(X)则称X*为优化模型最优解，最优解存在；迭代算法的收敛性是指迭代所得到的序列X(1),X(2),,X(K) ，满足f(X(K1))f(X(K))，则迭代法收敛；收敛的停止准则有

x(k1)x(k)，

x(k1)x(k)x(k)，fx(k1)fx(k)，

fx(k1)fx(k)fx(k)，fx(k)等

等。

练习题二

1、某公司看中了例2.1中厂家所拥有的3种资源R1、R2、和R3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这3种资源的收购报价是多少？（该问题称为例2.1的对偶问题）。

解：确定决策变量 对3种资源报价y1,y2,y3作为本问题的决策变量。

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

确定约束条件 资源的报价至少应该高于原生产产品的利润，这样原厂家才可能卖。 因此有如下线性规划问题：min w170y1100y2150y3

5y12y2y310s..t2y13y25y318 y,y,y0123*2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。

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

z4x2x32x12x2x3x1x22x32x2xx2xxx3223423 （1）s.t.1； （2）s.t.x2x3x55xx431xi0(i1,2,,5) x1,x2,x30minzx1x2x3min解：（1）引入松弛变量x4，x5，x6

min zx1x2x30*x40*x50*x6

x1x22x3x4 =22xxx x5 =3s..t123

x1x3 x6=4x1,x2,x3,x4,x5,x60cj→ CB 0 0 0 基 x4 x5 x6 cj-zj b 2 3 4 1 x1 1 2 -1 1 -1 x2 [1] 1 0 -1 1 x3 -2 1 1 1 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 因检验数σ2<0，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。

cj→ CB -1 0 0 基 x2 x5 x6 cj-zj b 2 1 4 1 x1 1 1 -1 2 -1 x4 1 0 0 0 1 x3 -2 [3] 1 -1 0 x4 1 -1 0 1 0 x5 0 1 0 0 0 x6 0 0 1 0 因检验数σ3<0，故确定x3为换入非基变量，以x3的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x5作为换出的基变量。

cj→ CB -1 1 0 基 x2 x3 x6 cj-zj b 8/3 1/3 11/3 1 x1 5/3 1/3 -4/3 7/3 -1 x2 1 0 0 0 1 x5 0 1 0 3 0 x4 1/3 -1/3 1/3 2/3 0 x5 2/3 1/3 -1/3 1/3 0 x6 0 0 1 0 因检验数σj>0，表明已求得最优解：X*(0,8/3,1/3,0,0,11/3)，去除添加的松弛变量，原问题的最优解为：X*(0,8/3,1/3)。

（2）根据题意选取x1，x4，x5，为基变量：

minz4x2x32x12x2x3x2xx2234 s.t.x2x3x55xi0(i1,2,,5)cj→ 0 -1 1 0 0 CB 0 0 0 基 x1 x4 x5 cj-zj b 2 2 5 x1 1 0 0 0 x2 -2 [1] 1 -1 x3 1 -2 1 1 x4 0 1 0 0 x5 0 0 1 0 因检验数σ2<0最小，故确定x2为换入非基变量，以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x4作为换出的基变量。

cj→ CB 0 -1 0 基 x1 x2 x5 cj-zj b 6 2 3 0 x1 1 0 0 0 -1 x2 0 1 0 0 1 x3 -3 -2 [3] -1 0 x4 2 1 -1 1 0 x5 0 0 1 0 因检验数σ3<0最小，故确定x3为换入非基变量，以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量x5作为换出的基变量。

cj→ CB 0 -1 1 基 x1 x2 x3 cj-zj b 9 4 1 0 x1 1 0 0 0 -1 x2 0 1 0 0 1 x3 0 0 1 0 0 x4 1 1/3 -1/3 2/3 0 x5 1 2/3 1/3 1/3 因检验数σj>0，表明已求得最优解：X*(9,4,1,0,0)。

8、某地区有A、B、C三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表2-28所示。试制定一个使总运费最少的化肥调拨方案。

表2- 1

运价/ 产粮 (元/吨) 区 化肥厂 A1 A2 A3 各区需要量/万吨 5 4 8 6 8 9 4 6 7 10 2 3 3 7 9 3 7 8 3 甲 乙 丙 丁 各厂供应量/万吨 解：设A、B、C三个化肥厂为A1、A2、A3，甲、乙、丙、丁四个产粮区为B1、B2、B3、B4；cij为由Ai运化肥至Bj的运价，单位是元/吨；xij为由Ai运往Bj的化肥数量（i=1,2,3;j=1,2,3,4）单位

是吨；z表示总运费，单位为元，依题意问题的数学模型为：

minzcijxij

i1j134x11x21x316xxx6122232x13x23x333 s..tx14x24x343xxxx711121314x21x22x23x248x31x32x33x347该题可以用单纯形法或matlab自带工具箱命令（linprog）求解。

*9、求解下列不平衡运输问题（各数据表中，方框内的数字为单位价格cij，框外右侧的一列数为各发点的供应量ai，框底下一行数是各收点的需求量bj）：

（1） 5 1 7 10 要求收点3的需求必须正好满足。 6 4 6 80 3 2 5 15

75 20 50

（2） 5 1 0 20 要求收点1的需求必须由发点4供应。 3 2 4 10 7 5 2 15 9 6 0 15

5 10 15 解答略。

练习题三

1、用0.618法求解问题

min(t)t32t1

t0的近似最优解，已知(t)的单谷区间为[0,3]，要求最后区间精度0.5。 答：t=0.8115；最小值-0.0886.（调用golds.m函数） 2、求无约束非线性规划问题

22min f(x1,x2,x3)=x124x2x32x1

的最优解

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

fff2x12，8x2，2x3，则由fx0得x11，x20，x30 x1x2x3再用充分条件进行检验：

2f2f2f2f2f2f0，0 2，28，22，0，2x1x3x2x3x1x2x3x1x2200即2f080为正定矩阵得极小点为x*(1,0,0)T，最优值为-1。

002解二：目标函数改写成

22 min f(x1,x2,x3)=(x11)24x2x31

易知最优解为（1,0,0），最优值为-1。

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

2 minf(X)x1x22x122x1x2x2其中X(x1,x2)T，给定初始点X0(0,0)T。

f(x)(x)14x2x112解一：目标函数f(x)的梯度f(x) f(x)12x12x2(x)211f(X(0))令搜索方向d(1)f(X(0))再从X(0)出发，沿d(1)方向作一维寻优，令步长变

11量为，最优步长为1，则有X(0)d(1)01 01故f(x)f(X(0)d(1))()2()22()2221()

011令1'()220可得11 X(1)X(0)1d(1) 求出X(1)点之后，与上类似地，

01111(2)(1)进行第二次迭代：f(X) 令df(X)

11(1)令步长变量为，最优步长为2，则有

111 X(1)d(2)111故

f(x)f(X(1)d(2))(1)(1)2(1)22(1)(1)(1)252212()1令

1)2)' 2d(2()1020可得 2 X(2)X(511.5121110.80.2(2)f(X)0.2828 此时所达到的精度f(X(2))0.21本题最优解X，f(X)1,25

1.5练习题四

1、石油输送管道铺设最优方案的选择问题：考察网络图4-6，设A为出发地，F为目的地，B，C，D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？

图4- 1

解：

第五阶段：E1—F 4；E2—F 3；

第四阶段：D1—E1 —F 7；D2—E2—F 5；D3—E1—F 5；

第三阶段：C1—D1—E1 —F 12；C2—D2—E2—F 10；C3—D2—E2—F 8；C4—D3—E1—F 9； 第二阶段：B1—C2—D2—E2—F 13； B2—C3—D2—E2—F 15； 第一阶段：A—B1—C2—D2—E2—F 17； 最优解：A—B1—C2—D2—E2—F 最优值：17

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

maxf(x)x1x2x3x1x2x327x1,x2,x30

解：x19,x29,x39，最优值为9。 3、用动态规划方法求解非线性规划

2maxz7x126x15x2tx12x210s.. x3x912x1,x20解：用顺序算法

阶段：分成两个阶段，且阶段1 、2 分别对应x1,x2。 决策变量：x1,x2

状态变量：vi,wi分别为第j 阶段第一、第二约束条件可供分配的右段数值。

f1*(v1,w1)max{7x126x1}min{7v126v1,7w126w1}

0x1v10x1w1*x1min{v1,w1}

2f2*(v2,w2)max{5x2f1*(v22x2,w23x2)}0x25 max{5xmin{7(v22x2)6(v22x2),7(w23x2)6(w23x2)}}0x252222

22292x2760,68x2396x2621} 由于v210,w29，f2*(v2,w2)f2*(10,9)max{min{33x20x25可解的x19.6,x20.2，最优值为702.92。

4、设四个城市之间的公路网如图4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。

275861344

图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

地区123销售点000011612102251714330211322217 解：

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

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

状态变量为sk表示分配给第k个至第3个地区的销售点总数； 状态转移方程：sk+1=sk－xk，其中s1=4； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝

阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；

最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：

[gk(xk)fk1(skxk)] k3,2,1fk(sk)0maxxksk f4(s4)0k=3时，f3(s3)max[g3(x3)]

x3s3g3（x3）0k=2时，f2(s2)max[g2(x2)f3(s2x2)]

0x2s2110234f3(s3) x3* 00141617001234 1234 10141617 g2(x2)+f3(s2－x2) 01234000k=1时，f1(s1)max[g1(x1)f2(s1x1)]，f1(s1)max[g1(x1)f2(4x1)]

s0x410x0+1012+012111f2(s2) x2* 0112234 0+1412+1017+00+1612+1417+1021+00+17 12+16 17+14 21+10 22+0 222731 2,3

最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1个地区设置2个销售点，第2个地区设置1个销售点，第3个地区设置1个销售点，每月可获利润47。

6、设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。 解：四个季度为四个阶段，采用阶段编号与季度顺序一致。 设 sk 为第k季初的库存量，则边界条件为 s1=s5=0

设 xk 为第k季的生产量，设 yk 为第k季的订货量；sk ，xk ，yk 都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的目标函数为：

f1(x)minx1,x2,x3,x4(0.005xi142isi)

第一步：(第四季度) 总效果 f4(s4,x4)=0.005 x42+s4

由边界条件有： s5= s4 + x4 – y4=0，解得：x4*=1200 – s4 将x4*代入 f4(s4,x4)得：

f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42

第二步：(第三、四季度) 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4) 将 s4= s3 + x3 – 500 代入 f3(s3,x3) 得：

2f3(s3,x3)0.005x3s3720011(x3s3500)0.005(x3s3500)2220.01x30.01x3s316x30.005s315s313950f3(s3,x3)0.02x30.01s3160x3解得x38000.5s3,

代入f3(s3,x3)得2f3(s3)75507s30.0025s3第三步：(第二、三、四季度) 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 700 代入 f2(s2,x2) 得：

2f2(s2,x2)0.005x2s275507(x2s2700)0.0025(x2s2700)2f2(s2,x2)0.015x20.005(s2700)70 x2解得x2700(13)s2,代入f2(s2,x2)得2f2(s2)100006s2(0.0053)s2第四步：(第一、二、三、四季度) 总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2)

将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得：

f1(s1,x1)0.005x12s1100006(x1600)(0.0053)(x1600)2f1(s1,x1)(0.043)x180x1解得x1600,代入f1(s1,x1)得f1(s2)11800由此回溯：得最优生产–库存方案

x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。

7、某种机器可在高低两种不同的负荷下进行生产。设机器在高负荷下生产的产量函数为g=8u1，其中u1为投入生产的机器数量，年完好率a=0.7；在低负荷下生产的产量函数为h=5y，其中y为投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量s1=1000。试问每年如何安排机

器在高、低负荷下的生产，使在5年内生产的产品总产量最高。 解：

构造这个问题的动态规划模型： 设阶段序数k表示年度。

状态变量sk为第k年度初拥有的完好机器数量，同时也是第k−1年度末时的完好机器数量。 决策变量uk为第k年度中分配高负荷下生产的机器数量，于是sk−uk为该年度中分配在低负荷下生产的机器数量。

这里sk和uk均取连续变量，它们的非整数值可以这样理解，如sk=0.6，就表示一台机器在k年度中正常工作时间只占6/10；uk=0.3，就表示一台机器在该年度只有3/10的时间能在高负荷下工作。 状态转移方程为：sk1aukb(skuk)0.7uk0.9(skuk), k1,2,,5 k段允许决策集合为：Dk(sk)uk0uksk 设vk(sk,uk)为第k年度的产量，则vk8uk5(skuk) 故指标函数为：V1,5vk(sk,uk)

k15令最优值函数fk(sk)表示由资源量sk出发，从第k年开始到第5年结束时所生产的产品的总产量最大值。因而有逆推关系式：

f6(s6)08uk5(skuk)fk10.7uk0.9(skuk) fk(sk)umaxkDk(sk) k1,2,3,4,5从第5年度开始，向前逆推计算。 当k=5时，有：

f5(s5)max8u55(s5u5)f60.7u50.9(s5u5)0u5s50u5s50u5s5max8u55(s5u55)max3u55s5

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

f5(s5)8s5

当k=4时，有：

f4(s4)max8u45(s4u4)f50.7u40.9(s4u4)0u4s40u4s40u4s40u4s4max8u45(s4u4)80.7u40.9(s4u4)max13.6u412.2(s4u4)max1.4u412.2s4故得最大解，u4*=s4，相应的有

f4(s4)13.6s4

依此类推，可求得

*u3s3, 相应的 f3(s3)17.5s3*u20, 相应的 f2(s2)20.8s2 *u10, 相应的 f1(s1)23.7s1因s1=1000，故：f1(s1)23700 计算结果表明：最优策略为

*****u10,u20,u3s3,u4s4,u5s5

即前两年应把年初全部完好机器投入低负荷生产，后三年应把年初全部完好机器投入高负荷生产。这样所得的产量最高，其最高产量为23700台。

在得到整个问题的最优指标函数值和最优策略后，还需反过来确定每年年初的状态，即从始端向终端递推计算出每年年初完好机器数。已知s1=1000台，于是可得：

**s20.7u10.9(s1u1)0.9s1900(台)**s30.7u20.2(s2u2)0.9s2810(台)**s40.7u30.9(s3u3)0.7s3567(台) **s50.7u40.9(s4u4)0.7s4397(台)**s60.7u50.9(s5u5)0.7s5278(台)

8、有一辆最大货运量为10t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4-20所示。应如何装载可使总价值最大？

表4- 2

货物编号i 单位重量（t） 单位价值 ci 1 3 4 2 4 5 3 5 6 解：建模设三种物品各装x1,x2,x3件

max(4x15x26x3)3x14x25x310 xj0,xjI,j1,2,3利用动态规划的逆序解法求此问题。

s1c,D1(s1){x1|0x1s1} s2s1x1,D2(s2){x2|0x2s2} s3s2x2,D3(s3){x3|0x3s3}

状态转移方程为： sk1Tk(sk,xk)skx,kk3, 2,1该题是三阶段决策过程，故可假想存在第四个阶段，而x40，于是动态规划的基本方程为：

[xk,fk1(sk1)],k3,2,1fk(sk)xkmaxDK(sk) f4(s4)0k3,

f3(s3)k2,

x30,1,,[s3/5]max6x3

f2(s2) k1,

max[5x2f3(s3)]x20,1,,[s2]4max[5x2f3(s24x2)]x20,1,,[s2]4

f1(s1)max[4x1f2(s2)]x10,1,2,3 max[4x1f2(s13x1)]x10,1,2,3

计算最终结果为x12,x21,x30，最大价值为13 。

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

不拨款 拨款 1 万元 拨款 2 万元 拨款 3 万元 A 30% 20% 10% 5% B 40% 30% 20% 10% C 20% 10% 10% 6% 问如何配置拨款才能使串联系统的可靠性最大？

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

设 sk 为第 k 阶段剩余款，则边界条件为 s3=5； 设 xk 为第 k 阶段的拨款额； 状态转移方程为 sk-1=sk-xk；

目标函数为 max R=(1-PA)(1-PB)(1-PC) 仍采用反向递推 第一阶段 ：对机器 C 拨款的效果

R1(s1,x1)=d1(s1,x1) R0(s0,x0)= d1(s1,x1)

x1 0 1 2 3 x1* R1 s1 (s1, x1*) 0 0.8 0 0.8 1 0.8 0.9 1 0.9 2 0.8 0.9 0.9 1, 2 0.9 3 0.8 0.9 0.9 0.94 3 0.94 4 0.8 0.9 0.9 0.94 3 0.94 5 0.8 0.9 0.9 0.94 3 0.94 第二阶段 ：对机器 B, C 拨款的效果 由于机器 A 最多只需 3 万元，故 s2  2 递推公式：

R2(s2,x2)=d2(s2,x2) R1(s1,x1*)

例：R2(3,2)=d2(3,2) R1(1,1)=(1-0.2) 0.9=0.72

得第二阶段最优决策表

x1 x1* s1 0 1 2 3 4 5 0 1 1, 2 3 3 3 R1 (s1, x1*) 0.8 0.9 0.9 0.94 0.94 0.94

x2 s2 2 3 4 5 0. 0.5 0.5 0.5 0.63 0.63 0.658 0.658 0. 0.72 0.72 0.752 0.72 0.81 0.81 2 2,3 3 3 0 1 2 3 x2* R2 (s2, x2*) 0. 0.72 0.81 0.81 第三阶段 ：对机器 A, B, C 拨款的效果 边界条件：s3 = 5 递推公式：

R3(s3,x3)=d3(s3,x3) R2(s2,x2*)

例：R3(5,3)=d3(5,3) R2(2,2)=(1-0.05) 0.=0.608 得第三阶段最优决策表

x2 x2* s2 2 3 4 5 2 2,3 3 3 R2 (s2, x2*) 0. 0.72 0.81 0.81

s3 x3 0 1 2 3 x3* R3(s3, x3*) 5 0.567 0.8 0.8 0.608 1,2 0.8 回溯 ：有多组最优解。

I：x3=1, x2=3, x1=1, R3=0.8 0.9 0.9=0.8 II：x3=2, x2=2, x1=1, R3= 0.90.80.9=0.8 III： x3=2, x2=3, x1=0, R3= 0.90.90.8=0.8 练习题五

1、考察多目标规划问题

x2,2x11,1x2，试画出个目标函数的图形，并求出R1,R2,Rab,Rpa,Rwp，这其中f1(x)x2,f2(x)x1,x2里Ri是minfi(x)的最优解集。

2x4解：