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

P66：8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1，A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？表销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为：可以 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ：约束矩阵的秩为r(A)=6.从而基变量的个数为6.二、给出运输问题的初始可行解（初始调运 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ）1.最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地B1B2B3B4产量A141241116A28210392810A38511622销量814121448①销地产地B1B2B3B4产量A141241116A28210239②810A38511622销量①814101448销地产地B1B2B3B4产量A14121041011166A28210239②810A38511622销量①814③101448销地产地B1B2B3B4产量A14121041011166A28210239②810A3814511146228销量①8④14③101448销地产地B1B2B3B4产量A14121041011166A28210239②810A38145118146⑤220销量①8④14③1014648销地产地B1B2B3B4产量A141210461011⑥160A28210239②8100A38145118146⑤220销量①8④14③10⑥14048此时得到一个初始调运方案（初始可行解）：其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6).总运费为（目标函数值）2.伏格尔（Vogel)法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。销地产地B1B2B3B4产量行差额A1412411160A221039101A385116221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210398101A3814511146221→2销量814121448列差额2①513销地产地B1B2B3B4产量行差额A1412411160A221039010②1A38145118146221销量814121448列差额2①513销地产地B1B2B3B4产量行差额A1412411160A282103890102②1A38145118146221销量814121448列差额③2①513销地产地B1B2B3B4产量行差额A14121241211164⑤7A2821032890100②6A38145118146221销量814121448列差额③2①5④13销地产地B1B2B3B4产量行差额A141212441211160⑤7A2821032890100②6A38145118146221销量8141214048列差额③2①5④1⑥3此时得到一个初始调运方案（初始可行解）：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销量814121448σ11=C11+C23-(C13+C21)=4+3–(4+2)=1销地产地B1B2B3B4产量A14X121210461116A2821023910A38145118622销量814121448σ12=C12+C34-(C14+C32)=12+6–(11+5)=2销地产地B1B2B3B4产量A141210461116A282X221023910A38145118622销量814121448σ22=C22+C13+C34-(C23+C14+C32)=10+4+6–(3+11+5)=20–19=1销地产地B1B2B3B4产量A1X1141210461116A2821023X24910A38145118622销量814121448σ24=C24+C13-(C14+C23)=9+4–(11+3)=-1销地产地B1B2B3B4产量A141210461116A2821023910A3X318145118622销量814121448σ31=C31+C14+C23-(C34+C13+C21)=8+11+3–(6+4+2)=22–12=10销地产地B1B2B3B4产量A141210461116A2821023910A38145X33118622销量814121448σ33=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销量814121448σ11=C11+C24-(C14+C21)=4+9–(11+2)=0销地产地B1B2B3B4产量A14X121212441116A2821032910A38145118622销量814121448σ12=C12+C34-(C14+C31)=12+6–(11+5)=2销地产地B1B2B3B4产量A141212441116A282X221032910A38145118622销量814121448σ22=C22+C34-(C24+C32)=10+6–(9+5)=16–14=2销地产地B1B2B3B4产量A141212441116A28210X2332910A38145118622销量814121448σ23=C23+C14-(C13+C24)=3+11–(4+9)=14-13=1销地产地B1B2B3B4产量A141212441116A2821032910A3X318145118622销量814121448σ31=C31+C24-(C21+C34)=8+9–(2+6)=17-8=9销地产地B1B2B3B4产量A141212441116A2821032910A38145X33118622销量814121448σ33=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)=1σ12=C12-(u1+v2)=12–(0+10)=2σ22=C22-(u2+v2)=10–(-1+10)=1σ24=C24-(u2+v4)=9–(-1+11)=-1σ31=C31-(u3+v1)=8–(-5+3)=10σ33=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)=0σ12=C12-(u1+v2)=12–(0+10)=2σ22=C22-(u2+v2)=10–(-2+10)=2σ23=C23-(u2+v3)=3–(-2+4)=-1σ31=C31-(u3+v1)=8–(-5+4)=9σ33=C33-(u3+v3)=11–(-5+4)=12与闭回路法计算的结果相同。四、解的改进（用闭回路法调整）在使用最小元素法求得的初始方案中，由于σ24<0，说明当前方案不是最优，需要改进或调整。见表1中非基变量x24所在的闭回路，调整量为ε=min{2,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产量A1A2A333171194321010857419销量3656①表3销地产地B1B2B3B4产量A1A2A333171194321010857419销量3656第2步，在表3未划去的元素中再找出最小运价为2，确定A2多余的1t物资供应B3。得表4。将表4的A2行运价划去，得表5表4销地产地B1B2B3B4产量A1A2A333171194321010857419①销量3656表5销地产地B1B2B3B4产量A1A2A333171194312101085②74109①销量36546第3步，在表5未划去的元素中再找出最小运价为3，确定A1的4t物资供应B3。得表6。将表6的B3列运价划去，得表7。表6销地产地B1B2B3B4产量A1A2A3331711944312101085②734109①销量36546表7销地产地B1B2B3B4产量A1A2A3331711944312101085②734109①销量3③65406第4步，在表7未划去的元素中再找出最小运价为4，确定A3的6t物资供应B2。得表8。将表8的B2列运价划去，得表9。表8销地产地B1B2B3B4产量A1A2A33317119644312101085②7341093①销量360③5406表9销地产地B1B2B3B4产量A1A2A333171196443121010835②7341093①销量3④60③5406第5步，在表9未划去的元素中再找出最小运价为5，确定A3的3t物资供应B4。得表10。将表10的A3行运价划去，得表11。表10销地产地B1B2B3B4产量A1A2A333171196443121010835②73410⑤93①销量3④60③54063表11销地产地B1B2B3B4产量A1A2A333171196443121010835②73410⑤93①销量3④60③54063第6步，在表11未划去的元素中再找出最小运价为10，确定A1的3t物资供应B4。得表12。将表12的A3行运价划去，得表13。表12销地产地B1B2B3B4产量A1A2A3331711964431210310835②730410⑤93①销量3④60③54063表13销地产地B1B2B3B4产量A1A2A3331711964431210310835②730410⑤93①销量3④60③540⑥63在表13中，所有元素都被划去，说明在产销平衡表上已得到一个调运方案，即初始基可行解，x13=4,x14=3,x21=3,x23=1,x32=6,x34=5。（基变量个数：3+4―1=6）基变量对应的运输量为零，非基变量对应的运输量为零。运输费用为：Z=3×4+10×3+1×3+2×1+4×6+5×3=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产量行差额A1A2A331711964321010857493011销量36056列差额2513表4销地产地B1B2B3B4产量行差额A1A2A331711964321010857493011销量36056列差额2513表5销地产地B1B3B4产量行差额A1A2A3317321010857493012销量356列差额213第3步：根据表4中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表5。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表5中，可确定A3的产品应首先供应B4，得表6。将单位运价表中相应的行划去，得表7。表6销地产地B1B3B4产量行差额A1A2A331732101083574930012销量3563列差额213表7销地产地B1B3B4产量行差额A1A2A331732101083574930012销量3563列差额213第4步：根据表7中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表8。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表8中，可确定A2的产品应首先供应B1或B4，选择B1得表9。将单位运价表中相应的列划去，得表10。（之所以选择B1，是因为对应的运距小）表8销地产地B1B3B4产量行差额A1A231321087401销量3563列差额212表9销地产地B1B3B4产量行差额A1A2331321087401销量30563列差额212表10销地产地B1B3B4产量行差额A1A2331321087401销量30563列差额212第5步：根据表10中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表11。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表11中，可确定A1的产品应首先供应B3，得表12。将单位运价表中相应的列和行划去，得表13。表11销地产地B3B4产量行差额A1A23210874176销量563列差额12表12销地产地B3B4产量行差额A1A2532108724176销量5063列差额12表13销地产地B3B4产量行差额A1A2532108724176销量5063列差额12第6步：根据表13中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表14。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表14中，可确定A1的产品应首先供应B4，得表15。将单位运价表中相应的行划去，得表16。表14销地产地B4产量行差额A1A21087241108销量63列差额2表15销地产地B4产量行差额A1A2210872041108销量63列差额2表16销地产地B4产量行差额A1A2210872041108销量631列差额2第7步：根据表16中余下的元素，再分别计算出各行、各列的最小运费和次最小运费的差额，得表17。从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表17中，可确定A2的产品应供应B4，得表18。表17销地产地B4产量行差额A28418销量631列差额表18销地产地B4产量行差额A2184108销量6310列差额初始基可行解列于表19中，可知：X13=5,X14=2,X21=3,X23=1,X32=6,X34=3。Z=3×5+10×2+1×3+8×1+4×6+5×3=15+20+3+8+24+15=85表19销地产地B1B2B3B4产量A1A2A33164532101835749销量3656可见，伏格尔法给出的初始基可行解更接近最优解。三、解的最优性检验⒈闭回路法（以下的闭回路都是顺时针方向）看非基变量的检验数是否满足：（1）首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：x11，x12，x22，x24，x31，x33，见表1，检验过程如表2-7所示：表1销地产地B1B2B3B4A131143310A2319128A37641035表2销地产地B1B2B3B4A1X1131143310A2319128A37641035σ11=C11+C23-(C13+C21)=3+2–(1+3)=5-4=1表3销地产地B1B2B3B4A13X121143310A2319128A37641035σ12=C12+C34-(C14+C32)=11+5–(10+4)=16-14=2表4销地产地B1B2B3B4A131143310A231X229128A37641035σ22=C22+C13+C34-(C23+C14+C32)=9+3+5–(2+10+4)=17-16=1表5销地产地B1B2B3B4A131143310A231912X248A37641035σ24=C24+C13-(C23+C14)=8+3–(2+10)=11-12=-1表6销地产地B1B2B3B4A131143310A2319128A3X317641035σ31=C31+C23+C14-(C21+C13+C34)=7+2+10–(1+3+5)=19-9=10表7销地产地B1B2B3B4A131143310A2319128A3764X331035σ33=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销地产地B1B2B3B4A1X1131153210A2319218A37641035σ11=C11+C24-(C14+C21)=3+8–(10+1)=11-11=0表3销地产地B1B2B3B4A13X121153210A2319218A37641035σ12=C12+C34-(C14+C32)=11+5–(10+4)=16-14=2表4销地产地B1B2B3B4A131153210A231X229218A37641035σ22=C22+C34-(C24+C32)=9+5–(8+4)=14-12=2表5销地产地B1B2B3B4A131153210A2319X23218A37641035σ23=C23+C14-(C13+C24)=2+10–(3+8)=12-11=1表6销地产地B1B2B3B4A131153210A2319218A3X317641035σ31=C31+C24-(C21+C34)=7+8–(1+5)=15-6=9表7销地产地B1B2B3B4A131153210A2319218A3764X331035σ33=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)=1σ12=C12-(u1+v2)=11–(0+9)=2σ22=C22-(u2+v2)=9–(-1+9)=1σ24=C24-(u2+v4)=8–(-1+10)=-1σ31=C31-(u3+v1)=7–(-5+2)=10σ33=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)=0σ12=C12-(u1+v2)=11–(0+9)=2σ22=C22-(u2+v2)=9–(-2+9)=2σ23=C23-(u2+v3)=2–(-2+3)=-1σ31=C31-(u3+v1)=7–(-5+3)=9σ33=C33-(u3+v3)=10–(-5+3)=12与闭回路法计算的结果相同。四、解的改进（用闭回路法调整）在使用最小元素法求得的初始方案中，由于σ24<0，说明当前方案不是最优，需要改进或调整。见表1中非基变量x24所在的闭回路，调整量为ε=min{3,1}=1。调整过程见表2：表1销地产地B1B2B3B4A131143310A2319128A37641035表2销地产地B1B2B3B4A13114+133-110A23191-120+18A37641035表3销地产地B1B2B3B4A131153210A2319218A37641035调整后的结果如表3所示，此结果正好与使用伏格尔法求得的结果相同，因此最优性检验过程同前，由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为：x13=5，x14=2，x21=3，x24=1，x32=6，x34=3，将最优解代入到目标函数中，得总运费为（目标函数值）：20