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

《运筹学胡运权版第三章运输问题课后习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、P66：8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂A1，A2，A3的生产量、各销售点B1，B2，B3，B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？表销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为：可以证明：约束矩阵的秩为r(A)=6.从而基变量的个数为6.二、给出运输问题的初始可行解（初始调运方案）1.最小元素

2、法思想：优先满足运价（或运距）最小的供销业务。销地产地B1B2B3B4产量A141241116A28210392810A38511622销量814121448①销地产地B1B2B3B4产量A141241116A28210239②810A38511622销量①814101448销地产地B1B2B3B4产量A14121041011166A28210239②810A38511622销量①814③101448销地产地B1B2B3B4产量A14121041011166A28210239②810A38145

3、11146228销量①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).总

4、运费为（目标函数值）2.伏格尔（Vogel)法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。销地产地B1B2B3B4产量行差额A1412411160A221039101A385116221销量814121448列差额2513销地产地B1B2B3B4产量行差额A1412411160A2210398101A3814511146221→2销量814121448列差

5、额2①513销地产地B1B2B3B4产量行差额A1412411160A221039010②1A38145118146221销量814121448列差额2①513销地产地B1B2B3B4产量行差额A1412411160A282103890102②1A38145118146221销量814121448列差额③2①513销地产地B1B2B3B4产量行差额A14121241211164⑤7A2821032890100②6A38145118146221销量814121448列差额③2①5④13销地产地B1

6、B2B3B4产量行差额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)。总运费为（目标函数值）：三、解的最优性检验⒈闭回路法（以下的闭回路都是顺时针方向）看非基变量的检验数是否满

7、足：（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-(C1

8、4+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销地产地B1B2B3B