《运筹学(胡运权版)第三章运输问题课后习题答案》由会员分享，可在线阅读，更多相关《运筹学(胡运权版)第三章运输问题课后习题答案（26页珍藏版）》请在金锄头文库上搜索。
1、精品资料推荐P66:8.某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点出售，各工厂Ai,A2,A3的生产量、各销售点Bl,B2,B3,B4的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表中，问如何调运才能使总运费最小？表产士人B1B2B3B4A141241116A22103910A38511622销量814121448解：一、该运输问题的数学模型为:34min zCjxj 4i1 j 110X223x239x24X11X12X13X21X22X23X31X32X33X11X21X31X12X22X32X13X23X33X14X24X34Xij0,i 1,x
2、11 x12 x13 x14 x211111 111111可以证明：约束矩阵的秩为11 12x124x13 11x8X31 5x3211x33X1416X2410X342281412142,3; j 1,2,3,4X22 X23x24 X3114(X216x34X32X33X341 1 111111r (A) = 6.从而基变量1111 7 12一数为 6.二、给出运输问题的初始可行解（初始调运方案）1.最小元素法思想：优先满足运价（或运距）最小的供销业务。销地产地BiB2B3B4A141241116A28210391082A3I8511622销量8;141214487销地产地11b1iB2B
3、3B4A11；4124111611A2A381+2-1-02399911111H822iii815116ili销量8!14101448销地产地一1B111B21B3B4A14:12104111661011I1A28-J-2-F*0-2一，F一一9-一i1118I11111A38141|5111622814111ii销量81114；1014482aI销地产地B11ii1c1B2I11B3B4A141210411116610111111-?1_i21-Jd-n_9-10A2812j102,8111IA3814i|5118622011Jij14销量8ii14i101464825aIX232,X321
4、4,x348,Xi310,Xi46,X218,其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=6）.总运费为（目标函数值）34ZCjXiji1j11046118223145862462.伏格尔（Vogel）法伏格尔法的基本思想：运输表中各行各列的最小运价与次小运价之差值（罚数）应尽可能地小。或者说：优先供应罚数最大行（或列）中最小运费的方格，以避免将运量分配到该行（或该列）次小运距的方格中。销地产地B1B2B3B4行差额A1412411160A221039101A385116221销量814121448列差额2513_销地产地B111
5、B2|1B3B4行差额A1412411160111A221039101111A38141I5116228141一2111销量8141121448列差额25!113口地产地B1b21!B3B4行差额A141211411160A221011139101A38141!511V.1一丁_6_i22141销量814i121448列差额25;1132产地销地B1B2B3B4行差额A14112411160A28210391021118A3814-5_11_-8一22一140_1111销量814121448列差额2513(D产地一一，销地B1B2!111B3jiipiB4行差额A141212141116412
6、7111A2一8一_2_103Z91006一I118A31一8_5i1.-8r6011411r2214销量814;j12r1448列差额25I13cD(D产地-销地B1B2111B3B4行差额A1412124411160127I1I101006A2一82.329一1118A385;1L162zz-14-0_141111L81销量81411214(D48列差额25113cD(D厂此时得到一个初始调运方案（初始可行解）X13=12,X14=4,X21=8,X24=2,X32=14,X34=8其余（非基）变量全等于零。此解满足所有约束条件，且基变量（非零变量）的个数为6（等于m+n-1=3+4-1=
7、6）。总运费为（目标函数值）：34Zcjxj124411822914586244三、解的最优性检验L闭回路法(以下的闭回路都是顺时针方向)看非基变量的检验数是否满足：j0.(1)首先对用最小元素法所确定的初始基本可行解进行检验。参见前面的计算结果，可知非基变量分别为：Xll,X12,X22,X24,X31,X33。7销地产地B1B2B3B4A1X1141210461116rA218IL21011_.23910A38145118622销量81412144861=C11+C23-(C13+C21)=4+3-(4+2)=1销地产地B1B2B3B4A14X1212-4-461116L1IiA28211023IlI910A381,4-511-一.J8622销量81412144832=C12+C34-(C14+C32)=12+6-(11+5)=2销地产地B1B2B3B4A1412104n1116A282X2211_10_231
