运筹学第三章运输问题课后习题答案

P66： 8.某部门有 3 个生产同类产品的工厂〔产地〕，生产的产品由 4 个销售点出售，各工厂 A1， A2，A3的生产量、各销售点 B1，B2，B3，B4的销售量〔假定单位为 t〕以及各工厂到销售点的单位运价〔元/t〕示于下表中，问如何调运才能使总运费最小？表销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为：min z=∑i=13∑j=14cij xij=4 x11+12 x12+4 x13+11 x14+2 x21+10 x22+3x23+9 x24+8 x31+5 x32+11 x33+6 x34{x11+x12+x13+x14¿16x21+x22+x23+x24¿10x31+x32+x33+x34¿22x11+x21+x31¿8x12+x22+x32¿14x13+ x23+x33¿12x14+x24+ x34¿14xij¿0,i=1,2,3;j=1,2,3,4可以证明：约束矩阵的秩为 r (A) = 6. 从而基变量的个数为 6.二、给出运输问题的初始可行解〔初始调运方案〕1. 最小元素法思想：优先满足运价〔或运距〕最小的供销业务。销地产地B1B2B3B4产量A141241116A282103910A38511622销量814121448销地产地B1B2B3B4产量A141241116A282103910A38511622销量814101448销地产地B1B2B3B4产量A141210411 16 6A282103910A38511622销量81410144882①82②①82②①10③销地产地B1B2B3B4产量A141210411 16 6A282103910A38145116 22 8销量814101448销地产地B1B2B3B4产量A141210411 16 6A282103910A381451186 22 0销量81410 14 648销地产地B1B2B3B4产量A1412104611 16 0A2821039 10 0A381451186 22 0销量81410 14 048此时得到一个初始调运方案〔初始可行解〕：其余〔非基〕变量全等于零。此解满足所有约束条件，且基变量〔非零变量〕的个数为6〔等于 m+n-1=3+4-1=6).82②①10③14④82②①10③14④⑤82②①10③14④⑤⑥⑥x34=8 ,x32=14,x23=2,x21=8,x14=6 ,x13=10,总运费为〔目标函数值〕2. 伏格尔〔Vogel)法伏格尔法的根本思想：运输表中各行各列的最小运价与次小运价之差值〔罚数〕应尽可能地小。或者说：优先供应罚数最大行〔或列〕中最小运费的方格，以防止将运量分配到该行〔或该列〕次小运距的方格中。销地产地B1B2B3B4产量行差额A1412411160A221039101A385116221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A221039101A38145116221→2销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A221039101A381451186221销量814121448列差额251314①814①0②Z=∑i=13∑j=14cij xij=10×4+6×11+8×2+2×3+14×5+8×6=246销...