1、习题参考答案第二章 习 题1.线性规划模型为: 0,18234.5max13132xtsx2. 标准形式为: 0,12385.min87654236432xxts3.(1)最优解为(2,2) ,最优值为 8.(2)根据等式约束得: 213-6x代入规划等价于: 0,3-.ma2121xts先用图解法求线性规划 0,3-6.a2121xts得最优解为(0,6)代入原规划可得最优解为(0,6,0)最优值为 18.4.(1)以 为基变量可得基可行解(3,1,0) ,对应的基阵为:21,x10以 为基变量可得基可行解(2,0,1) ,对应的基阵为:31,x 21(2)规划转化为标准形式: 0,563.
2、4min432121xts以 为基变量可得基可行解(0,1,4,0) ,对应的基阵为:32,x 055. 以 为基变量可得基可行解(0,2,3,9) ,对应的典式为:432,x 321942x非基变量 的检验数为 。1x-6. (1) a=0,b=3,c=1,d=0;(2) 基可行解为(0,0,1,6,2)(3)最优值为 3.7.(1)最优解为(1.6,0,1.2) ,最优值为-4.4;(2)令 ,则 , ,在规划中用 替代 ,并化标准形式。1xy0y1yx1yx最优解为(1,0,1) ,最优值为 3;(3)无最优解(4)最优解为(0,3,1)最优值为 7.8.(1)最优解为(2,0,0) ,
3、最优值为 4;(2)无最优解(3)最优解为(0,0,4) ,最优值为 4;(4)没可行解。9.(1)最优解为(3,0,0) ,最优值为-15;(2)允许增加值是 2,允许减少值是 6,在区间(0,8)内取值最优基不变。(3)最优解变为(2,0,0) ,最优值变为-10;(4)最优解为(0,0,2) ,最优值为-16;(5)最优解为(2,0,0) ,最优值变为-10。10.模型输入如下:model:min=-5*x1+8*x2+4*x3+6*x4+2*x5;x1+2*x2+2*x3+x4-x5=4;-x1+2*x2-2*x3+x42;free(x1);bnd(-2,x5,8);end第三章 习
4、题1. 为 整 数0,18215240.3max433321xtsx2. 1,0,11. 7895a3424234213214312 342423xxxxts xxx3. 为 整 数0,68.ma21xts4.(1)最优解为(8,0) ,最优值为-16;(2)最优解为(2,2) ,最优值为 12;(3)最优解为(6,0,0) ,最优值为 12;(4) 最优解为(2,2.5) ,最优值为-16.5 ;5. model:min=3*x1+2*x2+4*x3+6*x4+2*x5;2*x1+x2+2*x3+x4-x5=4;-2*x1+x2-2*x3+x42;GIN(x1);GIN(x2);bin(x5
5、);end第四章 习 题1. 阶段数:4状态变量:每个季度开始时的存储量 , 最大值为 1600;ix决策变量:每个季度的生产量 ;iy状态转移关系:用 表示第 个季度的销售量,则该季度末的库存量为idiiidyx显然第 季度初的存储量等于前一季度末的存储量,有:1i iiii1根据库存限制 6001iiii dyx可以得出决策变量的取值范围,即: 1max(0,)iiidy获得函数:当季成本=生产成本+存储成本= iiiix5.设 表示第 季初库存为 时,经过第 季度及以后各季度的最优成本,则显然有:)(xfiixi)(05.mn1),ax( iiiiiiiidyi dyxfdyii 最后一
6、季度的函数为: 20.i)( 44),0max(444xfdy2. 表示第 i 个点到点 A 的最短路程,则i3B1f5)(2f)B(3f4)(7,4,in)( 321fC562fff )(),(i1 CD6m)( 21fff 97,5in315)(1),()(031 DfffEf ,8i)( 212 63EffFf最短路长度为 26,最短路为:A-B 1-C1-D2-E2-F3最优方案是物品 1 装 5 个,物品 2 装 0 个,物品 3 装 0 个,最大价值为 60.4求最小旅行费用周游线路,表 4-14 是 5 个城市中从城市 i 到城市 j 的费用。注意其中两个城市之间往返的费用是不相
7、等的。表 4-5 5 个城市间的费用表ji1 2 3 4 51 9 11 7 82 13 6 12 43 10 8 5 94 7 12 6 25 12 9 4 3 第五章 多目标规划1 设 表示第 i 个项目是否投资,如果投资为 1,否则取值为 0,则对应的多目标规划为:ix1,0, 15.05323.0 60.327.61.54.826.min .4ax876541 87643 871 6532xxxts xx该问题要求建立多目标规划模型,不要求求解。2. 求解以下多目标规划的有效解和弱有效解。第一个目标的最优解在点 A 处为两条直线的交点,解方程组:6238.1x得最优解为 .第二个目标的
8、最优解为 x 轴上点 B(2,0)和点 C(4,0)的一部分。),( 71所以有效解的集合为 ,弱有效解除了有效解外还包括集合472,8)S1121 x.(AB C,即弱有效解集合为 。42,0)S1212 x.x( 21S3第一个目标的最优值为 13,第二个目标在第一个目标最优的基础上的最优解为(0,2.5,5.5) ,最优值为-5.4设两种产品正常生产的产量分别为 ,加班生产的产量为 ,问题的硬约束为有效工21,x21,y时限制和加班工时限制,即:0,65.2311yx目标函数为 。由于加班生产的利润低于正常生产的利润,所以最优解自2178.yx然满足当正常生产的工时有剩余时加班生产的工时
9、为 0.对应的规划为:0,65.231.8max121yts利润最大为 576.同时软约束为:利润大于等于 576,加班时间不超过 50 小时,产品 A 的产量不低于产品 B 产量的 2/3,即: 0235. 768101yxy根据题意第一个软约束的目标优先级要大于等于后两个,对应的目的规划为: 0,125.360. 5768510. )(min13121132yxdyyxxtsPd5.计算下列判别矩阵的权重、并做一致性检验权重为(0.324259,0.116036,0.103216,0.456489)一致性检验系数为 0.96093,通过检验。第六章 图与网络优化1.最小支撑树如下图加粗线所
10、示:43 51 26 7687662332341最小树权重为 23.2 (1)最短路如下图加粗线所示:7522 67 213642345671图 6-40 网络图最短路长度为 10.(2)最短路如下图加粗线所示:45231 32 175362345671最短路长度为 8.3找增广路标号如下:6,6 5,43,25,44,43,2 3,27,61,02,212 34 56-4,1+1,1+2,1+3,1-新可行流为:6,6 5,53,35,54,43,1 3,27,61,02,212 34 56-该可行流没有增广路,就是最大流,最大流流量为 11。4最大流如下图所示:4,46,47,513 1,
11、12,1 225,54,45,42345671图 6-43 网络图5顶点标号为:5,3 3,42,43,43,32,66,41,32,512 34 5603477最小费用流为:5,2 3,22,23,33,326,312,12 34 56对应的费用为 56。第七章 网络计划技术111.网络计划图为:024 89ACDGEFB 92. 诊断下列网络计划图是否正确G100642ABCD8EF12IH1614 JK18节点 12 和节点 18 都没有没有后续节点,出现两个结束时刻,所以是错误的。3 根据下列网络计划图,写出工程工作的紧前关系。02 64 89ABCDEF图 7-27 网络计划图紧前关
12、系如下:工作 A B C D E F作业时间 2 10 22 10 20 3紧前工作 无 无 A B B C D4.该工程的关键线路为 A-C-E-G-H-I,最短工期为 60.5.网络计划图为:0 2 64 89A B CDEF9G 9H 9 9J KI关键线路为:A-B-C-D-G-H-J-K.最短工期为:50试计算出该工程的最短工期。6 由于工作 C 的紧前工作为 A 和 B,该工程的紧前关系等价于:表 7-9 工程的紧前关系工作 A B C D E F G H作业时间 12 15 22 10 20 13 24 15紧前工作 无 无 A B C C E D C D G网络计划图为:1 742 35ABC DEFH6G设每个节点出现时间分别为 ,则有规划:7,.21,ix7,.20153024152.min674536423ixxxtsi其最短工期为:76.设每个工作的赶工时间为 ,为了便于管理要求赶工时间为整数。8,.21,jy则赶工的规划模型为: 8,.10,7.2,0 201320693154,2,6,4,0241052.min87541 8738675473655432317 jyix yyyyxyxyxtsji 为 整 数计算可得工期可以缩短到 62 天,其中工作 B 赶工 3 天,工作 C 赶工 6 天,工作 G 赶工 1 天,工作 H 赶工 4 天。