运筹学(胡运权版)第三章运输问题课后习题答案

P66： 8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1， A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？表销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.二、给出运输问题的初始可行解（初始调运方案）1. 最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地B1B2B3B4产量A141241116A28210392810A38511622销量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销地产地B1B2B3B4产量A141210461011 16 0A282102398 10 0A38145118146 22 0销量81410 14 048此时得到一个初始调运方案（初始可行解）：其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).总运费为（目标函数值）2. 伏格尔（Vogel)法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。销地产地B1B2B3B4产量行差额A1412411160A221039101A385116221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210398101A38145111462212销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210390101A38145118146221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A282103890 10 21A38145118146221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412124121116 47A2821032890 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)。总运费为（目标函数值）：三、解的最优性检验 闭回路法（以下的闭回路都是顺时针方向）看非基变量的检验数是否满足：（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 + 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产量A141210461116A2821023910A38145X33118622销量81412144833 = C33 + C14 - (C13 + C34) = 11 + 11 ( 4 + 6 ) =12由于24 = C24 + C13 - (C14 + C23) = 9 + 4 ( 11 + 3 ) = -1 0，所以当前方案不是最优方案。（2）然后对用伏格尔法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：x11，x12，x22，x23，x31，x33。（伏格尔法）销地产地B1B2B3B4产量A1X1141212441116A2821032910A38145118622销量81412144811 = C11 + C24 - (C14 + C21) = 4 + 9 ( 11 + 2 ) = 0销地产地B1B2B3B4产量A14X121212441116A2821032910A38145118622销量81412144812 = C12 + C34 - (C14 + C31) = 12 + 6 ( 11 + 5 ) = 2销地产地B1B2B3B4产量A141212441116A282X221032910A38145118622销量81412144822 = C22 + C34 - (C24 + C32) = 10 + 6 ( 9 + 5 ) = 16 14 = 2销地产地B1B2B3B4产量A141212441116A28210X2332910A38145118622销量81412144823 = C23 + C14 - (C13 + C24) = 3 + 11 ( 4 + 9 ) = 14-13=1销地产地B1B2B3B4产量A141212441116A2821032910A3X318145118622销量81412144831 = C31+ C24 - (C21 +C34) = 8 + 9 ( 2 + 6 ) = 17-8 = 9销地产地B1B2B3B4产量A141212441116A2821032910A38145X33118622销量81412144833 = C33 + C14 - (C13 + C34) = 11 + 11 ( 4 + 6 ) = 22-10 = 12由于所有非基变量的检验数都大于零，说明当前方案是最优方案，最优解为：x11=12，x14=4，x21=8，x24=2，x32=14，x34=8。2位势法 （1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x23，x32，x34。销地产地B1B2B3B4产量A141210461116A2821023910A38145118622销量814121448构造方程组：u1 + v3 = c13 = 4u1 + v4 = c14 = 11u2 + v1 = c21 = 2u2 + v3 = c23 = 3u3 + v2 = c32 = 5u3 + v4 = c34 = 6令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -1，v1 = 3，将其代入非基变量检验数：ij=Cij - (ui + vj)，得：11=C11 - (u1 + v1) = 4 ( 0 + 3 ) = 112=C12 - (u1 + v2) = 12 ( 0 + 10 ) = 222=C22 - (u2 + v2) = 10 ( -1 + 10 ) = 124=C24 - (u2 + v4) = 9 ( -1 + 11 ) = -131=C31 - (u3 + v1) = 8 ( -5 + 3 ) = 1033=C33 - (u3 + v3) = 11 ( -5 + 4 ) = 12与闭回路法计算的结果相同。（2）然后对用伏格尔法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x24，x32，x34。销地产地B1B2B3B4产量A141212441116A2821032910A38145118622销量814121448构造方程组：u1 + v3 = c13 = 4u1 + v4 = c14 = 11u2 + v1 = c21 = 2u2 + v4 = c24 = 9u3 + v2 = c32 = 5u3 + v4 = c34 = 6令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 4，v4 = 11，u3 = -5，v2 = 10，u2 = -2，v1 = 4，将其代入非基变量检验数：ij=Cij - (ui + vj)，得：11=C11 - (u1 + v1) = 4 ( 0 + 4 ) = 012=C12 - (u1 + v2) = 12 ( 0 + 10 ) = 222=C22 - (u2 + v2) = 10 ( -2 + 10 ) = 223=C23 - (u2 + v3) = 3 ( -2 + 4 ) = -131=C31 - (u3 + v1) = 8 ( -5 + 4 ) = 933=C33 - (u3 + v3) = 11 ( -5 + 4 ) = 12与闭回路法计算的结果相同。四、解的改进（用闭回路法调整）在使用最小元素法求得的初始方案中，由于240，说明当前方案不是最优，需要改进或调整。见表1中非基变量x24所在的闭回路，调整量为 = min2,6 = 2。调整过程见表2：表1销地产地B1B2B3B4产量A141210461116A2821023910A38145118622表2销地产地B1B2B3B4产量A141210+246-21116A282102-230+2910A38145118622表3销地产地B1B2B3B4产量A141212441116A2821032910A38145118622调整后的结果如表3所示，此结果正好与使用伏格尔法求得的结果相同，因此最优性检验过程同前，由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为：x13=12，x14=4，x21=8，x24=2，x32=14，x34=8。将最优解代入到目标函数中，得总运费为（目标函数值）：P66： 9.解：首先列出这一问题的产销平衡表，见表1。 表1 销地产地B1B2B3B4产量A1A2A3317119432101085749销量3656一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r (A) = 6. 从而基变量的个数为 6.二、给出运输问题的初始可行解（初始调运方案）1. 最小元素法第1步，从表1中找出最小运价为1，表示应先将A2的产品供应B1。在表中A2和B1的交叉格处填上3，得表2。将表2中的B1列运价划去，得表3表2 销地产地B1B2B3B4产量A1A2A333 1711943210108574 19销量3656表3 销地产地B1B2B3B4产量A1A2A333 1711943210108574 19销量3656第2步，在表3未划去的元素中再找出最小运价为2，确定A2多余的1 t物资供应B3 。得表4。将表4的A2行运价划去，得表5表4 销地产地B1B2B3B4产量A1A2A333 1711943210108574 19销量3656表5 销地产地B1B2B3B4产量A1A2A333 17119431 210108574 1 09销量365 46第3步，在表5未划去的元素中再找出最小运价为3，确定A1的4 t物资供应B3 。得表6。将表6的B3列运价划去，得表7。表6 销地产地B1B2B3B4产量A1A2A333 1711944 31 21010857 34 1 09销量365 46表7 销地产地B1B2B3B4产量A1A2A333 1711944 31 21010857 34 1 09销量365 4 06第4步，在表7未划去的元素中再找出最小运价为4，确定A3的6 t物资供应B2 。得表8。将表8的B2列运价划去，得表9。表8 销地产地B1B2B3B4产量A1A2A333 171196 44 31 21010857 34 1 09 3销量36 05 4 06表9 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2101083 57 34 1 09 3销量36 05 4 06第5步，在表9未划去的元素中再找出最小运价为5，确定A3的3 t物资供应B4 。得表10。将表10的A3行运价划去，得表11。表10 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2101083 57 34 1 09 3销量36 05 4 06 3表11 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2101083 57 34 1 09 3销量36 05 4 06 3第6步，在表11未划去的元素中再找出最小运价为10，确定A1的3 t物资供应B4 。得表12。将表12的A3行运价划去，得表13。表12 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2103 1083 57 3 04 1 09 3销量36 05 4 06 3表13 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2103 1083 57 3 04 1 09 3销量36 05 4 06 3在表13中，所有元素都被划去，说明在产销平衡表上已得到一个调运方案，即初始基可行解，x13 = 4, x14 = 3, x21 = 3, x23 = 1, x32 = 6, x34 = 5。（基变量个数：3 + 41 = 6）基变量对应的运输量为零，非基变量对应的运输量为零。运输费用为：Z = 34 + 103 +13 +21 +46 +53 = 12+30+3+2+24+15 = 862. 伏格尔（Vogel)法第1步：在表1中分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表2。表1 销地产地B1B2B3B4产量A1A2A3317119432101085749销量3656表2 销地产地B1B2B3B4产量行差额A1A2A3317119432101085749011销量3656列差额2513第2步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表2中，可确定A3的产品应首先供应B2，得表3。将单位运价表中的列的数字划去，得表4。表3 销地产地B1B2B3B4产量行差额A1A2A33171196 432101085749 3011销量36 056列差额2513表4 销地产地B1B2B3B4产量行差额A1A2A33171196 432101085749 3011销量36 056列差额2513表5 销地产地B1B3B4产量行差额A1A2A331732101085749 3012销量356列差额213第3步：根据表4中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表5。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表5中，可确定A3的产品应首先供应B4，得表6。将单位运价表中相应的行划去，得表7。表6 销地产地B1B3B4产量行差额A1A2A331732101083 5749 3 0012销量356 3列差额213表7 销地产地B1B3B4产量行差额A1A2A331732101083 5749 3 0012销量356 3列差额213第4步：根据表7中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表8。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表8中，可确定A2的产品应首先供应B1或B4，选择B1得表9。将单位运价表中相应的列划去，得表10。（之所以选择B1，是因为对应的运距小）表8 销地产地B1B3B4产量行差额A1A231321087401销量356 3列差额212表9 销地产地B1B3B4产量行差额A1A233 1321087401销量3 056 3列差额212表10 销地产地B1B3B4产量行差额A1A233 1321087401销量3 056 3列差额212第5步：根据表10中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表11。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表11中，可确定A1的产品应首先供应B3，得表12。将单位运价表中相应的列和行划去，得表13。表11 销地产地B3B4产量行差额A1A23210874 176销量56 3列差额12表12 销地产地B3B4产量行差额A1A25 321087 24 176销量5 06 3列差额12表13 销地产地B3B4产量行差额A1A25 321087 24 176销量5 06 3列差额12第6步：根据表13中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表14。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表14中，可确定A1的产品应首先供应B4，得表15。将单位运价表中相应的行划去，得表16。表14 销地产地B4产量行差额A1A21087 24 1108销量6 3列差额2表15 销地产地B4产量行差额A1A22 1087 2 04 1108销量6 3列差额2表16 销地产地B4产量行差额A1A22 1087 2 04 1108销量6 3 1列差额2第7步：根据表16中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表17。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表17中，可确定A2的产品应供应B4，得表18。表17 销地产地B4产量行差额A284 18销量6 3 1列差额表18 销地产地B4产量行差额A21 84 1 08销量6 3 1 0列差额初始基可行解列于表19中，可知：X13 = 5, X14 = 2, X21 = 3, X23 = 1, X32 = 6, X34 = 3。Z = 35 + 102 +13 +81 +46 +53 = 15+20+3+8+24+15 = 85表19 销地产地B1B2B3B4产量A1A2A33 16 45 32 101 83 5749销量3656可见，伏格尔法给出的初始基可行解更接近最优解。三、解的最优性检验 闭回路法（以下的闭回路都是顺时针方向）看非基变量的检验数是否满足：（1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：x11，x12，x22，x24，x31，x33，见表1，检验过程如表2-7所示：表1销地产地B1B2B3B4A131143310A2319128A37641035表2销地产地B1B2B3B4A1X1131143310A2319128A3764103511 = C11+ C23 - (C13 +C21) = 3 + 2 ( 1 + 3 ) = 5 - 4 = 1表3销地产地B1B2B3B4A13X121143310A2319128A3764103512 = C12+ C34 - (C14 +C32) = 11 + 5 ( 10 + 4 ) = 16 - 14 = 2表4销地产地B1B2B3B4A131143310A231X229128A3764103522 = C22+ C13+ C34 - (C23 +C14+ C32) = 9 + 3+ 5 ( 2 + 10+ 4 ) = 17 - 16 = 1表5销地产地B1B2B3B4A131143310A231912X248A3764103524 = C24+ C13 - (C23 +C14) = 8 + 3 ( 2 + 10 ) = 11 - 12 = -1表6销地产地B1B2B3B4A131143310A2319128A3X31764103531 = C31+ C23+ C14 - (C21 +C13+ C34) = 7 + 2+ 10 ( 1 + 3+ 5 ) = 19 - 9 = 10表7销地产地B1B2B3B4A131143310A2319128A3764X33103533 = C33+ C14 - (C13 +C34) = 10 + 10 ( 3 + 5 ) = 20 - 8 = 12由于24 = C24+ C13 - (C23 +C14) = 8 + 3 ( 2 + 10 ) = 11 - 12 = -1 0，所以当前方案不是最优方案。（2）然后对用伏格尔法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：x11，x12，x22，x23，x31，x33，见表1，检验过程如表2-7所示：表1销地产地B1B2B3B4A131153210A2319218A37641035表2销地产地B1B2B3B4A1X1131153210A2319218A3764103511 = C11+ C24 - (C14 +C21) = 3 + 8 ( 10 + 1 ) = 11 - 11 = 0表3销地产地B1B2B3B4A13X121153210A2319218A3764103512 = C12+ C34 - (C14 +C32) = 11 + 5 ( 10 + 4 ) = 16 - 14 = 2表4销地产地B1B2B3B4A131153210A231X229218A3764103522 = C22+ C34 - (C24 +C32) = 9 + 5 ( 8 + 4 ) = 14 - 12 = 2表5销地产地B1B2B3B4A131153210A2319X23218A3764103523 = C23+ C14 - (C13 +C24) = 2 + 10 ( 3 + 8 ) = 12 - 11 = 1表6销地产地B1B2B3B4A131153210A2319218A3X31764103531 = C31+ C24 - (C21 +C34) = 7 + 8 ( 1 + 5 ) = 15 - 6 = 9表7销地产地B1B2B3B4A131153210A2319218A3764X33103533 = C33+ C14 - (C13 +C34) = 10 + 10 ( 3 + 5 ) = 20 - 8 = 122位势法 （1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x23，x32，x34。销地产地B1B2B3B4A131143310A2319128A37641035构造方程组：u1 + v3 = c13 = 3u1 + v4 = c14 = 10u2 + v1 = c21 = 1u2 + v3 = c23 = 2u3 + v2 = c32 = 4u3 + v4 = c34 = 5令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 3，v4 = 10，u3 = -5，v2 = 9，u2 = -1，v1 = 2，将其代入非基变量检验数：ij=Cij - (ui + vj)，得：11=C11 - (u1 + v1) = 3 ( 0 + 2 ) = 112=C12 - (u1 + v2) = 11 ( 0 + 9 ) = 222=C22 - (u2 + v2) = 9 ( -1 + 9 ) = 124=C24 - (u2 + v4) = 8 ( -1 + 10 ) = -131=C31 - (u3 + v1) = 7 ( -5 + 2 ) = 1033=C33 - (u3 + v3) = 10 ( -5 + 3 ) = 12与闭回路法计算的结果相同。（2）然后对用伏格尔法所确定的初始基本可行解进行检验。参见前面的计算结果，可知基变量分别为：x13，x14，x21，x24，x32，x34。销地产地B1B2B3B4A131153210A2319218A37641035构造方程组：u1 + v3 = c13 = 3u1 + v4 = c14 = 10u2 + v1 = c21 = 1u2 + v4 = c24 = 8u3 + v2 = c32 = 4u3 + v4 = c34 = 5令自由变量u1 = 0 ，将其代入方程组，得：u1 = 0，v3 = 3，v4 = 10，u3 = -5，v2 = 9，u2 = -2，v1 = 3，将其代入非基变量检验数：ij=Cij - (ui + vj)，得：11=C11 - (u1 + v1) = 3 ( 0 + 3 ) = 012=C12 - (u1 + v2) = 11 ( 0 + 9 ) = 222=C22 - (u2 + v2) = 9 ( -2 + 9 ) = 223=C23 - (u2 + v3) = 2 ( -2 + 3 ) = -131=C31 - (u3 + v1) = 7 ( -5 + 3 ) = 933=C33 - (u3 + v3) = 10 ( -5 + 3 ) = 12与闭回路法计算的结果相同。四、解的改进（用闭回路法调整）在使用最小元素法求得的初始方案中，由于240，说明当前方案不是最优，需要改进或调整。见表1中非基变量x24所在的闭回路，调整量为 = min3,1 = 1。调整过程见表2：表1销地产地B1B2B3B4A131143310A2319128A37641035表2销地产地B1B2B3B4A13114+133-110A23191-120+18A37641035表3销地产地B1B2B3B4A131153210A