《（交通运输）运筹学(胡运权版)第三章运输问题课后习题答案》由会员分享，可在线阅读，更多相关《（交通运输）运筹学(胡运权版)第三章运输问题课后习题答案（26页珍藏版）》请在金锄头文库上搜索。
1、P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1， A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？表销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.二、给出运输问题的初始可行解（初始调运方案）1. 最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地B1B2B3B4产量A1412
2、41116A28210392810A38511622销量814121448销地产地B1B2B3B4产量A141241116A28210239810A38511622销量814101448销地产地B1B2B3B4产量A14121041011 16 6A28210239810A38511622销量814101448销地产地B1B2B3B4产量A14121041011 16 6A28210239810A3814511146 22 8销量814101448销地产地B1B2B3B4产量A14121041011 16 6A28210239810A38145118146 22 0销量81410 14 648
3、销地产地B1B2B3B4产量A141210461011 16 0A282102398 10 0A38145118146 22 0销量81410 14 048此时得到一个初始调运方案（初始可行解）：其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).总运费为（目标函数值）2. 伏格尔（Vogel)法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。销地产地B1B2B3B4产量行差额A141241116
4、0A221039101A385116221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210398101A38145111462212销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210390101A38145118146221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A282103890 10 21A38145118146221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412124121116 47A28210
5、32890 10 06A38145118146221销量814121448列差额2513销地产地B1B2B3B4产量行差额A14121244121116 07A2821032890 10 06A38145118146221销量8141214 048列差额2513此时得到一个初始调运方案（初始可行解）：x13 = 12, x14 = 4, x21 = 8, x24 = 2, x32 = 14, x34 = 8其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6)。总运费为（目标函数值）：三、解的最优性检验 闭回路法（以下的闭回路都是顺时针
6、方向）看非基变量的检验数是否满足：（1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：x11，x12，x22，x24，x31，x33。销地产地B1B2B3B4产量A1X1141210461116A2821023910A38145118622销量81412144811 = C11 + C23 - (C13 + C21) = 4 + 3 ( 4 + 2 ) =1销地产地B1B2B3B4产量A14X121210461116A2821023910A38145118622销量81412144812 = C12 + C34 - (C14 + C32) = 12
7、+ 6 ( 11 + 5 ) =2销地产地B1B2B3B4产量A141210461116A282X221023910A38145118622销量81412144822= C22 + C13 + C34 - (C23 + C14 + C32) = 10 + 4 + 6 ( 3 + 11 + 5 ) = 20 19 =1销地产地B1B2B3B4产量A1X1141210461116A2821023X24910A38145118622销量81412144824 = C24 + C13 - (C14 + C23) = 9 + 4 ( 11 + 3 ) = -1销地产地B1B2B3B4产量A141210461116A2821023910A3X318145118622销量81412144831= C31 + C14 + C23 - (C34 + C13 + C21) = 8 + 11 + 3 ( 6 + 4 + 2 ) = 22 12 = 10销地产地B1B2B3B4产量A141210461116A2821023910A38145X33118
