《第四版运筹学部分课后习题解答[汇编]》由会员分享，可在线阅读，更多相关《第四版运筹学部分课后习题解答[汇编]（23页珍藏版）》请在金锄头文库上搜索。
1、运筹学部分课后习题解答 P47 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 .424 ,0 xx xx stxx x x 解：由图 1 可知，该问题的可行域为凸集MABCN，且可知线段 BA上的点都 为最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 P47 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10 x5x 349 .528 ,0 xx stxx x x 解：由图 1 可知，该问题的可行域为凸集OABCO ，且可知 B点为最优值点， 即 1 12 122 1 349 3 528 2 x
2、xx xxx ，即最优解为 *3 1, 2 T x 这时的最优值为 max 335 z=10 15 22 单纯形法： 原问题化成标准型为 12 123 124 1234 max z=10 x5x 349 .528 ,0 xxx stxxx x xx x j c 10500 BCB Xb1x2x3x4x 0 3 x 93410 0 4 x 85201 jj CZ 10500 0 3 x 21/5014/51-3 /5 10 1 x 8/512/501 /5 jj CZ 010-2 5 2 x 3 /2015/14-3 /14 10 1 x 110-1/72 /7 jj CZ 00-5/14-25
3、 /14 所以有 * max 3335 1,10 1 5 222 T xz P78 已知线性规划问题： 1234 124 12 234 123 1234 max24 38 26 6 9 ,0 zxxxx xxx xx xxx xxx x xxx 求: (1) 写出其对偶问题；（2）已知原问题最优解为)0 ,4,2 ,2( * X，试根据对偶 理论，直接求出对偶问题的最优解。 解： （1）该线性规划问题的对偶问题为： 1234 124 1234 34 13 1234 min8669 22 34 1 1 ,0 wyyyy yyy yyyy yy yy yyyy （2）由原问题最优解为)0, 4,2
4、, 2( * X，根据互补松弛性得： 124 1234 34 22 34 1 yyy yyyy yy 把)0 ,4, 2,2( * X代入原线性规划问题的约束中得第四个约束取严格不等号， 即 4 224890y 从而有 12 123 3 22 34 1 yy yyy y 得 1234 43 ,1,0 55 yyyy 所以对偶问题的最优解为 * 4 3 (,1,0) 5 5 T y，最优值为 min 16w P79 考虑如下线性规划问题： 123 123 123 123 123 min604080 322 434 2223 ,0 zxxx xxx xxx xxx x x x （1）写出其对偶问题
5、；（2）用对偶单纯形法求解原问题； 解： （1）该线性规划问题的对偶问题为： 123 123 123 123 123 max243 34260 2240 3280 ,0 wyyy yyy yyy yyy y yy （2）在原问题加入三个松弛变量 456 ,xxx把该线性规划问题化为标准型： 123 1234 1235 1236 max604080 322 434 2223 0,1,6 j zxxx xxxx xxxx xxxx xjL j c -60-40-80000 BCB Xb1x2x3x4x5x6x 0 4 x -2-3-2-1100 0 5x -4-4-1-3010 0 6 x -3-
6、2-2-2001 jj CZ -60-40-80000 0 4 x 10-5/45 /41-1/120 80 1 x 111/43 /40-1/40 0 6 x -10-3/2-1/20-1/21 jjCZ 0-25-350-150 0 4 x 11/6005 /311/3-5/6 80 1x 5/6102 /30-1/31/6 40 2 x 2/3011 /301/3-2/3 jj CZ 00-80/30-20/3-50/3 * max 5 252230 (,0) ,6040800 6 3633 T xz P81 某厂生产 A、B、C三种产品，其所需劳动力、 材料等有关数据见下表。 要求：
7、（a）确定获利最大的产品生产计划； （b）产品 A 的利润在什么范围内变动 时，上述最优计划不变；（c）如果设计一种新产品D，单件劳动力消耗为 8 单位， 材料消耗为 2 单位，每件可获利3 元，问该种产品是否值得生产（d） 如果劳 动力数量不增，材料不足时可从市场购买，每单位元。问该厂要不要购进原材 料扩大生产，以购多少为宜。 ABC可用量（单位） 劳动力 材料 635 3 45 45 30 产品利润（元 /件）3 1 4 解：由已知可得，设 j x表示第 j 种产品，从而模型为： 123 123 123 123 max34 63545 .34530 ,0 zxxx xxx stxxx x
8、xx a) 用单纯形法求解上述模型为： 产品 资源 消耗 定额 j c 31400 B CB X b1 x 2 x 3 x 4 x 5 x 0 4 x 4563510 0 5x 3034501 jj CZ 31400 0 4x 153-101-1 4 3 x 63/54/5101/5 jj CZ 3/5-11 /500-4 /5 3 1 x 51-1/301/3-1 /3 4 3 x 3011-1/52 /5 jj CZ 0-20-1/5-3 /5 得到最优解为 * (5,0,3) T x；最优值为 max 354 327z b）设产品 A 的利润为 3，则上述模型中目标函数1 x的系数用 3
9、替代并求 解得： j c 3 1400 B CBXb1x2x3x4x5x 3 1 x 51-1/301/3-1/3 4 3 x 3011-1/52/5 jj CZ -20-1/5-3/5 jj CZ 0-2+/30-1/5-/3-3/5+/3 要最优计划不变，要求有如下的不等式方程组成立 20 3 1 0 53 3 0 53 解得： 39 55 从而产品 A 的利润变化范围为： 39 3,3 55 ,即 24 2, 4 55 C）设产品 D用 6 x表示，从已知可得 1 666 1/ 5 B cc BP 1 66 11 2 8 33 4 122 5 55 PB P 把 6 x加入上述模型中求解
10、得： j c 314003 B CBXb1x2x3x4x5x6x 3 1x 51-1/301/3-1/32 4 3 x 3011-1/52/5-4/5 jj CZ 0-20-1/5-3/51/5 3 6 x 5/21/2-1/601/6-1/61 4 3 x 52/513/151-1/154/150 jj CZ -1/10-59/300-7 /30-17/300 从而得最优解 * (0,0,5,0,0,5 /2) T x；最优值为 max 5 45327.527 2 z 所以产品 D 值得生产。 P101 已知运输问题的产销量与单位运价如下表所示，用表上作业法求各题的最 优解及最小运费。 表
11、3-35 B1B2B3B4产量 A1 A2 A3 10 12 2 2 7 14 20 9 16 11 20 18 15 25 5 销量5151510 产地销地 解：因为 4 1 3 1j j i i ba ，即产销平衡.所以由已知和最小元素法可得初始方案为 B1B2B3B4产量 A1 A2 A35 15 015 0 10 15 25 5 销量5151510 检验： 由于有两个检验数小于零，所以需调整，调整一： B1B2B3B4产量 A1 A2 A35 15 01510 0 15 25 5 销量5151510 检验： 由于还有检验数小于零，所以需调整，调整二： 产地销地 产地销地 B1B2B3B
12、4产量 A1 A2 A35 5 1015 10 0 15 25 5 销量5151510 检验： 从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为： min 2 5257 109 1511 10180335z 表 3-36 B1B2B3B4产量 A1 A2 A3 8 6 5 4 9 3 1 4 4 2 7 3 7 25 26 销量10102015 解：因为 34 11 5855 ij ij ab，即产大于销，所以需添加一个假想的销地，销 量为 3，构成产销平衡问题，其对应各销地的单位运费都为0。 B1B2B3B4B5产量 A1 A2 A3 8 6 5 4 9 3 1 4 4 2 7
13、3 0 0 0 7 25 26 销量101020153 由上表和最小元素法可得初始方案为 产地销地 产地销地 产地销地 B1B2B3B4B5产量 A1 A2 A3 9 110 7 13 15 3 7 25 26 销量101020153 检验： 从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为： min 6 95 13 101 74 133 1503193z 表 3-37 B1B2B3B4B5产量 A1 A2 A3 8 5 6 6 M 3 3 8 9 7 4 6 5 7 8 20 30 30 销量2525201020 解：因为 35 11 80100 ij ij ab，即销大于产，所
14、以需添加一个假想的产地，产 量为 20，构成产销平衡问题，其对应各销地的单位运费都为0。 B1B2B3B4B5产量 A1 A2 A3 A4 8 5 6 0 6 M 3 0 3 8 9 0 7 4 6 0 5 7 8 0 20 30 30 20 销量2525201020 产地销地 产地销地 产地销地 由上表和最小元素法可得初始方案为 B1B2B3B4B5产量 A1 A2 A3 A4 5 20 25 20 0 1015 5 20 30 30 20 销量2525201020 检验： 由于有两个检验数小于零，所以需调整，调整一： B1B2B3B4B5产量 A1 A2 A3 A4 20 5 25 20
15、0 10 5 15 20 30 30 20 销量2525201020 检验： 产地销地 产地销地 由于还有检验数小于零，所以需调整，调整二： B1B2B3B4B5产量 A1 A2 A3 A4 20 525 20 0 10 0 20 20 30 30 20 销量2525201020 检验： 从上表可以看出所有的检验数都大于零，即为最优方案 最小运费为： min 3205204 106 53258002000305z P127 用割平面法求解整数规划问题。 a） 12 12 12 12 max79 36 735 ,0, zxx xx xx x x且为整数 解：该问题的松弛问题为： 12 12 12
16、 12 max79 36 735 ,0 zxx xx xx x x 则单纯形法求解该松弛问题得最后一单纯形表为： 产地销地 j c 7900 B CB X b1 x 2 x 3 x 4 x 9 2 x 7/2017/221/22 7 1x 9/210-1/223/22 jj CZ 00-28/11-15/11 割平面 1 为： 234 (31/ 2)(07/ 22)(01/ 22)xxx 342 171 30 22222 xxx 345 711 22222 xxx 从而有 j c 79000 B CBXb1x2x3x4x5x 9 2 x 7/2017 /221/220 7 1x 9/210-1/223/220 0 5 x -1/200-7/22-1/221 jj CZ 00-28/11-15/110 9 2 x 301001 7 1 x 32/71001/7-1/7 0 3 x 11/70011/7-22/7 jj CZ 000-1-8 割平面 2 为： 145 (44 /7)(01/ 7)( 16/7)xxx 4515
