解：建立乘子法的增广目标函数：
2?(x,?,?)?x12?x2??(x1?x2?2)??2(x1?x2?2)^2
令：
??(x,?,?)?2x1????(x1?x2?2)?0 ?x1??(x,?,?)?2x2????(x1?x2?2)?0 ?x1解上述关于x的二元一次方程组得到稳定点
?2?????2??2?x???
2???????2??2???1?当乘子?取2时，或发参数?趋于无穷时，得到x????x*即最优解。
?1?（建议同学自己编程序计算）
练习题四
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
由于v2?10,w2?9，
22f2*(v2,w2)?f2*(10,9)?max{min{33x2?292x2?760,68x2?396x2?621}
0?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销售点00001161210225171433021164322217 解：
将问题分为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）000?x2?s2110234f3(s3) x3* 0141617001234 k=2时，f2(s2)?max[g2(x2)?1f3(s2?x2)]
234 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) 得：