《运筹学习题答案注释(第3章).doc》由会员分享，可在线阅读，更多相关《运筹学习题答案注释(第3章).doc（11页珍藏版）》请在金锄头文库上搜索。
1、第3章 运输问题注意：本章习题解法不唯一，有的题目，最优解也可能不唯一。3.8 表3-32和表3-33分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。表3-32销地产地B1B2B3B4产量A141468A212508A337514销量656320解：由最小元素法求得上述运输问题的初始基可行解，其过程如下：表3.8-1销地产地B1B2B3B4产量A141468A212508A337514销量656320由于0为最小，所以，取3与8的最小值放在x24位置上，划去B4列，得表3.8-2表3.8-2销地产地B1B2B3B4产量A141468A2125053A
2、337514销量6560在没画线的表格中，由于1最小，所以取6与5的最小值放在x21位置上，划去A2行，得表3.8-3在表3.8-3中的没画线的表格中，由于1最小，所以取8与5的最小值放在x12位置上，划去B2列，得表3.8-4在表3.8-4中没画线的表格中，由于3最小，所以取4与1的最小值放在x31位置上，划去B1列，得表3.8-5表3.8-3销地产地B1B2B3B4产量A141468A21250053A337514销量1560表3.8-4销地产地B1B2B3B4产量A1414635A21250053A337514销量1060表3.8-5销地产地B1B2B3B4产量A1414635A2125
3、0053A3375131销量0060在表3.8-5中没画线的表格中，由于4最小，所以取3与6的最小值放在x13位置上，划去A1行，得表3.8-6在表3.8-6中没画线的表格中，由于5最小，所以取3与3的最小值放在x33位置上，划去A3行和B3列，得表3.8-7，这样就得到了一个初始基可行解，如表3.8-8所示。在表3.8-8中，使用闭回路法计算非基变量的检验数（括弧内的数），得表3.8-9：11 = c11- c13 + c33 - c31 = 4-4+5-3 = 2 14 = c14- c13 + c33 - c31 + c21 - c24 = 6-4+5-3+1-0 = 5得表3.8-6销
4、地产地B1B2B3B4产量A14146353A21250053A3375131销量0030表3.8-7销地产地B1B2B3B4产量A14146053A21250053A33751013销量0000表3.8-8销地产地B1B2B3B4产量A14146853A21250853A33751413销量65632022 = c22 - c12 + c13 - c33 + c31 - c21 = 2-1+4-5+3-1 = 223 = c23 - c33 + c31 - c21 = 5-5+3-1 = 232 = c32 - c33 + c13 c12 = 7-5+4-1 = 534 = c34 - c2
5、4 + c21 c13 = 1-0+1-3 = -1在表3.8-9中，由于检验数34 = -10 ，所以表3.8-9中的解不是最优解。选x34为换入变量，找到闭回路为：x34 x24 x21 x31 ，由于3与1的最小数为1，故调整量为1，选x31为换出变量，调整后的解如表3.8-10所示表3.8-9销地产地B1B2B3B4产量A141468(2)53(5)A2125085(2)(2)3A3375141(5)3(-1)销量656320表3.8-10销地产地B1B2B3B4产量A14146853A21250862A33751431销量656320在表3.8-10中，使用闭回路法计算各非基变量的检
6、验数，得表3.8-11：表3.8-11销地产地B1B2B3B4产量A141468(3)53(6)A2125086(1)(1)2A337514(1)(5)31销量656320在表3.8-11中，由于所有检验数均大于等于 0 ，所以表3.8-11中的解就是最优解，其最小运价为39 。解：由最小元素法求得上述运输问题的初始基可行解，如下表3.8-21：在表3.8-21中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.8-22：在表3.8-22中，由于所有检验数均大于等于 0 ，所以表3.8-22中的解就是最优解，其最小运价为 31 。表3-33销地产地B1B2B3B4产量A193873A2
7、49453A357625销量132511表3.8-21销地产地B1B2B3B4产量A1938733A24945312A357625005销量132511表3.8-22销地产地B1B2B3B4产量A193873(8)3(7)(2)A2494531(3)2(4)A35762500(1)5销量1325113.9 试求表3-34给出的产销不平衡运输问题的最优解。表3-34销地产地B1B2B3B4产量A137645A224322A343856销量3322解：由于该运输问题的产量大于销量，产销不平衡，可增加一个假想的销地B5，其销量为:(5+2+6)-(3+3+2+2)=3,运费为0 ，使之变为产销平衡问
8、题，如表3.9-1所示：表3.9-1销地产地B1B2B3B4B5产量A1376405A2243202A3438506销量3322313由最小元素法求得上述运输问题的初始基可行解，如下表3.9-2 。表3.9-2销地产地B1B2B3B4B5产量A1376405302A224320202A343850633销量3322313表3.9-3销地产地B1B2B3B4B5产量A1376405302（1）（-4）A22432020（-2）（-2）2（-3）A3438506（5）3（6）（6）3销量3322313在表3.9-2中，使用闭回路法计算非基变量的检验数（括号内的数），得表3.9-3 。在表3.9-3中，由于有多个检验数均小于 0 ，选最小的检验数15 = -4 ，其位置上的变量x15为换入变量，找到闭回路为：x15 x35 x32 x12 ，由于3与0的最小数为0，故调整量为0，选x12为换出变量，调整后的解如表3.9-4所示 。在表3.9-4中，使用闭回路法计算各非基变量的检验数（括号内的数）。在表
