1、练习题一 1、建立优化模型应考虑哪些要素 ? 答：决策变量、目标函数和约束条件。 2、讨论优化模型最优解的存在性、迭代算法的收敛性及停止准则。 答： 针对一般优化模型 m in ( ). . 0 , 1 , 2 ,0 , 1 , ,ijfxs t g x i mh x j p，讨论解的可行域 D ，若存在一点 *XD ，对于 XD 均有 *( ) ( )f X f X 则称 *X 为优化模型最优解，最优解存在； 迭代算法的收敛性是指迭代所得到的序列 (1 ) ( 2 ) ( ), , , KX X X ，满足 ( 1) ( )( ) ( )KKf X f X ，则迭代法收敛；收敛的停止准则有(
2、 1) ( )kkxx ， ( 1) ( )()kkkxxx ， ( 1 ) ( )kkf x f x ， ( 1 ) ( )()kkkf x f xfx ， ()kfx 等等。 练习题二 1、 某公司看中了例 2.1 中厂家所拥有的 3 种资源 R1、 R2、和 R3，欲出价收购（可能用于生产附加值更高的产品）。如果你是该公司的决策者，对这 3 种资源的收购报价是多少？（该问题称为例 2.1的对偶问题）。 解： 确定决策变量 对 3 种资源报价 1 2 3,y y y 作为本问题的决策变量。 确定目标函数 问题的目标很清楚 “收购价最小”。 确定约束条件 资源的报价至少应该高于原生产产品的利
3、润，这样原厂家才可能卖。 因此有如下线性规划问题： 1 2 3m i n 1 7 0 1 0 0 1 5 0w y y y 1 2 31 2 31 2 35 2 1 0. . 2 3 5 1 8, , 0y y ys t y y yy y y *2、研究线性规划的对偶理论和方法（包括对偶规划模型形式、对偶理论和对偶单纯形法）。 答：略。 3、用单纯形法求解下列线性规划问题： （ 1） 0,43222.min32131321321321xxxxxxxxxxxtsxxxz； （ 2） )5,2,1(052222.4m in53243232132ixxxxxxxxxxtsxxzi 解：（ 1） 引入
4、松弛变量 x4， x5， x6 1 2 3 4 5 6m i n 0 * 0 * 0 *z x x x x x x 1 2 3 41 2 32 = 22 5 = 3.1 3 6 = 41 , 2 , 3 , 4 , 5 , 6 0x x x xx x x xstx x xx x x x x x cj 1 -1 1 0 0 0 CB 基 b x1 x2 x3 x4 x5 x6 0 x4 2 1 1 -2 1 0 0 0 x5 3 2 1 1 0 1 0 0 x6 4 -1 0 1 0 0 1 cj-zj 1 -1 1 0 0 0 因检验数 20，表明已求得最优 解： * ( 0 , 8 / 3
5、, 1 / 3 , 0 , 0 , 1 1 / 3 )X ，去除添加的松弛变量，原问题的最优解为： * (0,8 / 3,1 / 3)X 。 （ 2） 根据题意选取 x1， x4， x5， 为基变量： )5,2,1(052222.4m in53243232132ixxxxxxxxxxtsxxzicj 0 -1 1 0 0 CB 基 b x1 x2 x3 x4 x5 0 x1 2 1 -2 1 0 0 0 x4 2 0 1 -2 1 0 0 x5 5 0 1 1 0 1 cj-zj 0 -1 1 0 0 因检验数 20，表明已求得最优解： * (9, 4,1, 0, 0)X 。 8、某地区有 A
6、、 B、 C 三个化肥厂，供应本地甲、乙、丙、丁四个产粮区。已知各化肥厂可供应化肥的数量和各产粮区对化肥的需要量，以及各厂到各区每吨化肥的运价如表 2-28 所示。试制定一个使总运费最少的化肥调拨方案。 表 2- 1 运价 / 产粮 ( 元 / 吨 ) 区 化肥厂 甲 乙 丙 丁 各厂供应量 /万吨 A1 5 8 7 3 7 A2 4 9 10 7 8 A3 8 4 2 9 3 各区需要量 /万吨 6 6 3 3 解： 设 A、 B、 C 三个化肥厂为 A1、 A2、 A3，甲、乙、丙、丁四个产粮区为 B1、 B2、 B3、 B4；cij 为由 Ai 运化肥至 Bj 的运价，单位是元 /吨；
7、xij 为由 Ai 运往 Bj 的化肥数量（ i=1,2,3;j=1,2,3,4）单位是吨； z表示总运费，单位为元，依题意问题的数学模型为： 3411m in ij ijijz c x1 1 2 1 3 11 2 2 2 3 21 3 2 3 3 31 4 2 4 3 41 1 1 2 1 3 1 42 1 2 2 2 3 2 43 1 3 2 3 3 3 4663. . 3787x x xx x xx x xs t x x xx x x xx x x xx x x x 该题可以用单纯形法或 matlab 自带工具箱命令（ linprog）求解。 *9、 求解下列不平衡运输问题（各数据表中，
8、方框内的数字为单位价格 ijc，框外右侧的一列数为各发点的供应量 ia，框底下一行数是各收点的需求量 jb）： （ 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 法求解问题 12)(m in 30 tttt 的 近似最优解，已知 )(t 的单谷区 间为 3,0 ， 要求最 后区间精度 0.5 。 答： t=0.8115；最小值 -0.0886.（调
9、用 golds.m函数） 2、求无约束非线性规划问题 min ),( 321 xxxf = 1232221 24 xxxx 的最优解 解 一 ： 由极值存在的必要条件求出稳定点： 11 22f xx ，22 8f xx ，33 2f xx ， 则由 0fx得 1 1x ， 2 0x ， 3 0x 再用充分条件进行检验： 221 2fx ， 222 8fx ， 223 2fx ， 2120fxx ， 2130fxx ， 2230fxx 即 2 2 0 00 8 00 0 2f为正定矩阵得极小点为 T* (1,0,0)x ， 最优值为 -1。 解二： 目标函数改写成 min ),( 321 xxx
10、f = 2 2 21 2 3( 1) 4 1x x x 易知最优解为（ 1,0,0） ，最优值为 -1。 3、用 最速下降法求解无约束非线性规划问题 。 22212121 22)(m in xxxxxxXf 其中 TxxX ),( 21 ，给定初始点 TX )0,0(0 。 解一： 目标函数 ()fx的梯度 1 12122()() 1 4 2()1 2 2()()fxx xxfxxxfxx (0) 1() 1fX 令搜索方向 (1 ) ( 0 ) 1() 1d f X 再从 (0)X 出发，沿 (1)d 方向作一维寻优，令步长变量为 ，最优步长为 1 ，则有 ( 0 ) ( 1 ) 01Xd
11、故 ( 0 ) ( 1 ) 2 2 2 1( ) ( ) ( ) 2 ( ) 2 ( ) 2 ( )f x f X d 令 1 ( ) 2 2 0 可得 1 1 ( 1 ) ( 0 ) ( 1 )1 0 1 10 1 1X X d 求出 (1)X 点之后，与上类似地，进行第二次迭代： (1) 1()1fX 令 ( 2 ) (1 ) 1()1d f X 令步长变量为 ，最优步长为 2 ，则有 ( 1 ) ( 2 ) 1 1 11 1 1Xd 故 ( 1 ) ( 2 ) 2 2 2 2( ) ( ) ( 1 ) ( 1 ) 2 ( 1 ) 2 ( 1 ) ( 1 ) ( 1 ) 5 2 1 ( )
12、f x f X d 令2 ( ) 10 2 0 可得 2 15 ( 2 ) ( 1 ) ( 2 )2 1 1 0 .811 1 1 .25X X d ( 2 ) 0.2() 0.2fX 此时所达到的精度 ( 2 )( ) 0. 28 28fX 本题最优解 11.5X ， ( ) 1, 25fX 练习题四 1、石油输送管道铺设最优方案的选择问题：考察网络图 4-6，设 A 为出发地， F 为目的地， B，C， D， E 分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？ 图 4- 1 解： 第 五 阶段 ：
13、 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、 用动态规划方法求解非线 性规划 1 2 31 2 31 2 3m a x ( )27, , 0f x x x xx x xx x x 解： 1 2 39, 9,
14、 9x x x ，最优值为 9。 3、 用动态规划方法求解非线性规划 221 1 2121212m a x 7 6 5. . 2 1 039,0z x x xs t x xxxxx 解： 用顺序算法 阶段 ： 分成两个阶段 ， 且阶段 1 、 2 分别对应 12,xx。 决策变量： 12,xx 状态变量 ： ,iivw分别为第 j 阶段第一、第二约束 条件 可供分配的右段数值。 11* 2 2 21 1 1 1 1 1 1 1 100( , ) m a x 7 6 m in 7 6 , 7 6 xvxwf v w x x v v w w *1 1 1min , x v w 22* 2 *2 2
15、 2 2 1 2 2 2 2052 2 22 2 2 2 2 2 2 2 205( , ) m a x 5 ( 2 , 3 ) m a x 5 m in 7 ( 2 ) 6 ( 2 ) , 7 ( 3 ) 6 ( 3 ) xxf v w x f v x w xx v x v x w x w x 由于 2210, 9vw，2* * 2 22 2 2 2 2 2 2 205( , ) ( 1 0 , 9 ) m a x m i n 3 3 2 9 2 7 6 0 , 6 8 3 9 6 6 2 1 xf v w f x x x x 可解的 129.6, 0.2xx，最优值为 702.92。 4、
16、设四个城市之间的公路网如图 4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市 4 的最短路线及相应的最短距离。 2 14358674图 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 地区销售点0 1 2 3 41230001612102517143
17、02116322217地区地区销售点销售点解： 将问题分为 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 个地区所得到的最大利润，动态规划基本方程为： 1044( ) m a x ( ) ( ) 3 ,
18、 2 , 1( ) 0 kkk k k k k k kxsf s g x f s x kfs k=3 时，333 3 3 3( ) m ax ( )xsf s g x4 1 7 174 316163214142110101000043210x3*f3( s3) g3（ x3）（ ）k=2 时，222 2 2 2 3 2 20( ) m a x ( ) ( ) xsf s g x f s x 2 , 3 3 1 2 2 + 0 2 1 + 1 0 1 7 + 1 4 1 2 + 1 6 0 + 1 7 4 2272 1 + 01 7 + 1 01 2 + 1 40 + 1 631221 7 +
19、01 2 + 1 00 + 1 421121 2 + 00 + 1 01000043210x2*f2( s2) g2( x2)+ f3( s2 x2) k=1 时，111 1 1 1 2 1 10( ) m a x ( ) ( ) xsf s g x f s x ，11 1 1 1 2 104( ) m a x ( ) ( 4 ) xf s g x f x 最优解为： x1*=2， x2*=1， x3*=1， f1(4)=47，即在第 1 个地区设置 2 个销售点，第 2 个地区设置 1个销售点，第 3 个地区设置 1 个销售点，每月可获利润 47。 6、 设某厂计划全年生产某种产品 A。其四
20、个季度的订货量分别为 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 仍采用反向递推，但注意阶段编号是正向的目标函数为 ： 1 2 3 44 21 , , ,
21、 1( ) m in ( 0 .0 0 5 )iix x x x if x x s 第一步： (第四季度 ) 总效果 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) 得： 23 3 3 3 3 3 3233223 3 3
22、 3 3 33 3 33333 3 3 3 323 3 3 3( , ) 0 .0 0 5 7 2 0 0 1 1 ( 5 0 0 )0 .0 0 5 ( 5 0 0 )0 .0 1 0 .0 1 1 6 0 .0 0 5 1 5 1 3 9 5 0( , )0 .0 2 0 .0 1 1 6 08 0 0 0 .5 , ( , )( ) 7 5 5 0 7 0 .0 0 2 5f s x x s x sxsx x s x s sf s xxsxx s f s xf s s s 解 得 代 入 得第三步： (第二、三、四季度 ) 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(
23、s3) 将 s3= s2 + x2 700 代入 f2(s2,x2) 得： 22 2 2 2 2 2 22222 2 22222 2 2 2 222 2 2 2( , ) 0 .0 0 5 7 5 5 0 7 ( 7 0 0 )0 .0 0 2 5 ( 7 0 0 )( , )0 .0 1 5 0 .0 0 5 ( 7 0 0 ) 7 07 0 0 ( 1 3 ) , ( , )( ) 1 0 0 0 0 6 ( 0 .0 0 5 3 )f s x x s x sxsf s xxsxx s f s xf s s s 解 得 代 入 得第四步： (第一、二、三、四季度 ) 总效果 f1(s1,x
24、1)=0.005 x12+s1+ f2*(s2) 将 s2= s1 + x1 600= x1 600 代入 f1(s1,x1) 得： 21 1 1 1 1 1211 1 1111 1 1 112( , 0 .0 0 5 1 0 0 0 0 6 ( 6 0 0 )( 0 .0 0 5 3 ) ( 6 0 0 )( , )( 0 .0 4 3 ) 8 06 0 0 , ( , )( ) 1 1 8 0 0f s x x s xxf s xxxx f s xfs 解 得 代 入 得 由此回溯 ：得最优生产 库存方案 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。试问每年如何安排机
