运筹运输问题

1、 第三章 运输问题 运输问题的数学模型1、运输问题的一般提法 销地产地 B1 B2 B3 B4 B5 产 量 A1 A2 A31.2 1.7 1.6 1.8 2.41.8 1.5 2.2 1.2 1.61.5 1.4 1.2 1.5 1.0 3000 4000 1000 需求量1000 500 3000 1500 2000问：如何合理调运，才能使总运费最少？（产销平衡）2、运输模型的特点不是满秩阵, r(A)=m+n-1 基可行解只有m+n-1个变量3) 对偶问题二、表上作业法1、思路同单纯形法2、初始方案的确定1）西北角法 销地产地B1B2B3B4B5产 量A11.21.71.61.82.4

2、3000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量1000500300015002000100050015001500150010001000(Z=15120)空格：非基变量数字格：基变量2) 最小元素法 销地产地B1B2B3B4B5产 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量1000500300015002000100010001500500200010001000(z=11750)3) 差额法(z=11750) 销地产地B1 B2B3B4B5销量

3、A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 产 量1000 500300015002000差 额差 额0.40.30.2 0.3 0.1 0.40.3 0.610000.40.30.60.20.60.60.8100010000.40.320000.60.20.60.60.20.60.60.10.3150050010004) 补零 销地产地B1B2B3B4产 量A110876 60 A2326150A3452960 销 量503070202030601050补零位置：（1）所在行列上的最小元素；（2）不能形成所有

4、顶点都为数字格的闭回路。0 产地销地123 产 量121012231114344销 量91011Z=49P98/3.2(1)3、检验数的求法极小化问题：所有j0时为最优。1）闭回路法 闭回路从调运方案的某一空格出发，沿水平或垂直的 方向前进，遇到一个适当的数字格便按与前进 方向垂直的路径前进。经过若干次后，再回到 原来出发的那个格，由此形成的封闭折线称为 闭回路。 销地产地B1B2B3B4B5产 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量10005003000150020001000100015005

5、00200010001000（2）闭回路的性质 以空格出发的闭回路存在且唯一； 不存在所有顶点都为数字格的闭回路。2) 用闭回路求检验系数 销地产地B1B2B3B4B5产 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量1000500300015002000100010001500500200010001000+12 = 1.7-1.6+2.2-1.5=0.831 =1.5-1.0+1.6-2.2+1.6-1.2=0.3(1)(2)(3)(4)结论：空格（i,j)的检验系数ij可表示为：由空格所作出的 闭

6、回路中所有奇数格对应的单位运价之和减去所有 偶数格对应的单位运价之和的差。 i j1234510.81.21.42030.30.5-0.40.92) 初等变换法（1）把对应于数字格的运费加上括号 销产B1B2B3B4B5 A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0( )( )( )( )( )( )( ) 销产B1B2B3B4B5 A1(1.2)1.7(1.6)1.82.4 A21.2(0.9)(1.6)(0.6)(1.0) A31.51.41.21.5(1.0) 销产B1B2B3B4B5 A1( 0 )0.8( 0 )1.21.

7、4 A20( 0 )( 0 )( 0 )( 0 ) A30.30.5-0.40.9( 0 )（2）作行的初等变化，使每列中加括号的数都相等-0.6(3)各列分别减去本列中加括号的数3) 位势法对应于基变量存在如下关系： 销产B1B2B3B4B5 ui A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0 vj( )( )( )( )( )( )( ) 01.21.60.60.9 0.6 1.0 0 i j12345123 0.8 1.2 1.4 0 0.3 0.5 -0.4 0.94、方案的调整过格(k,l)作闭回路，在闭回路上作尽可能大的

8、调整，调整量y为偶数格上的最小调运量。(最小规则) 最小元素法 销地产地B1B2B3B4B5产 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量1000500300015002000100010001500500200010001000(z=11750)+_+_调整量 y=1000，x23出基 销地产地B1B2B3B4B5产 量A11.21.71.61.82.43000A21.81.52.21.21.64000A31.51.41.21.51.01000 销 量100050030001500200010001

9、50050020001000 02000 销产B1B2B3B4B5 ui A11.21.71.61.82.4 A21.81.52.21.21.6 A31.51.41.21.51.0 vj( )( )( )( )( )( )( ) 01.21.60.21.3 1.0 1.4- 0.4 i j1234510.40.81.020.40.430.70.50.9 销地产地甲乙丙丁产 量13764 5 224322343853 销 量332221 32 2 0Z1=36uivj0 3 6-1 4 5-2 销地产地甲乙丙丁产 量137645 224322343853 销 量33223 32 0 0Z2=36

10、-4=32uivj203 4-15-2 4 销地产地甲乙丙丁产 量13764 5 224322343853 销 量33223 32 0Z3=32uivj203 4 0-2 6 5-3三、运输问题的进一步讨论（一）产销不平衡的运输问题1、供大于求解决问题的思路：产销不平衡产销平衡 销地产地B1B2B3B4B5产 量A121347A2103595A378127 销 量23460 0 0 4 3 4 2 3 2 1 42 、供不应求（二）无运输通路如：至无运输通路（三）目标函数极大化型1、最大元素法2、最大减次大练习题 销地产地 B1 B2 B3 B4 B5 产 量A1A2A3A4 5 7 3 4

11、4 6 8 6 9 7 3 5 7 2 5 8 4 5 7 3 7005008001000需求量420 490 510 530 550 已知某运输问题的单位收益表如下：1、求出最佳运输方案；2、若A4产地因仓库容量限制，1000单位货物必须全部运出去则应如何确定最佳运输方案。 差额法 销地产地B1 B2B3B4B5B6销量A1573440700A2686970500A3357250800A48457301000 产 量420 490510530550500差 额差 额21 21 2 1 1 2 24901 2 2 1500 3 2 3 1 420 1 2 2 30 1 2 2510290210

12、 50500Z=17510 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A48457301000销 量4204905105305505005004204905103029021050500uivj0 7 4 1-1 6 8 91 1Z=17610 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A48457301000销 量42049051053055050045042049051080290210500uivjZ=1761050 0 7 4 3 1 6 6 1 7-1+-+-+

13、- 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A48457301000销 量420490510530550500240420490510290290210290uivjZ=17820260 0 70 0 8 72 5 0 7 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A48457301000销 量420490510530550500240420490510290290210290uivjZ=17820260-M 0 7 0-M7 + M2-M5 + M8 + M-M7 +

14、 M +-+-+- 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A484573-M1000销 量420490510530550500420250510530290 450 50uivj260 0 7 0-M240 1 67+M 8+M-1 8+-+- 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A484573-M1000销 量420490510530550500420200510530290 500uivj260 0 7 0240 1 650Z=17430-3 11 10-1

15、 8+-+-+- 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A484573-M1000销 量42049051053055050042044051053050 260uivj500 0 7 050Z=17670240-30 7 5 11 10 2+-+-+- 产地销地B1B2B3B4B5B6产 量A1573440700A2686970500A3357250800A484573-M1000销 量42049051053055050042049046053050 210uivj500 0 7 0Z=177202900 7 5 250-2 10 9 销地产地甲乙丙产 量A151822 400 B212516 450 销 量320250350 C 701521M290300甲22M1627080M0丙3、书上P100/（1）； （2）若C22变为2