调运问题---表上作业法

1、调运问题-表上作业法                                       基本思路：1.建立供需平衡运价表2.用最小元素法求出初始调运方案3.用位势法检验初始调运方案4.用闭合回路法调整初始调运方

2、案5.重复步骤34，直到出现最优调运方案6.计算最少总运费在供销不平衡的情况下，可用以下办法进行解决：1供大于求-引入虚拟需求点，其需求量等于实际供应量与需求量之差，该点运价为零。2供小于求-引入虚拟供应点，其供应量等于实际需求量与供应量之差，该点运价为零。例题： 设有5个产地A1、A2、A3、A4、A5和4个销地B1、B2、B3、B4的运输问题，他们的供应量和需求量及单位运费如下表，试计算其最小运输成本。B1B2B3B4供应量A110205710A213912820A34157930A41471040A531251950需求量60602010150解：1该案例属于供需平衡，下面直接

3、用最小元素法求出初始调运方案。在所有运价中，找出最小运价为0，该运价对应的需求量为10，供应量为40，即需求量可以得到全部满足。将调运数量和A4、B4的剩余供需数量在表上做出记号，同时由于B4的需求已经满足，可以划去该列其他的各个运价。结果如下：B1B2B3B4供应量A110205710A213912820A34157930A414710/1040/30A531251950需求量60602010/0150在剩下的运价中，最小运价为1，调运结果如下：B1B2B3B4供应量A110205710A213912820A34157930A41471/200/1040/30/10A531251950需求量

4、606020/010/0150在剩下的运价中，最小运价为3，调运结果如下：B1B2B3B4供应量A110205710A213912820A34157930A41471/200/1040/30/10A53/501251950/0需求量60/106020/010/0150在剩下的运价中，最小运价为4，调运结果如下：B1B2B3B4供应量A110205710A213912820A34/10157930/20A41471/200/1040/30/10A53/501251950/0需求量60/10/06020/010/0150在剩下的运价中，最小运价为7，调运结果如下：B1B2B3B4供应量A11020

5、5710A213912820A34/10157930/20A4147/101/200/1040/30/10/0A53/501251950/0需求量60/10/060/5020/010/0150在剩下的运价中，最小运价为9，调运结果如下：B1B2B3B4供应量A110205710A2139/2012820/0A34/10157930/20A4147/101/200/1040/30/10/0A53/501251950/0需求量60/10/060/50/3020/010/0150在剩下的运价中，最小运价为15，调运结果如下：B1B2B3B4供应量A110205710A2139/2012820/0A3

6、4/1015/207930/20/0A4147/101/200/1040/30/10/0A53/501251950/0需求量60/10/060/50/30/1020/010/0150在剩下的运价中，最小运价为20，调运结果如下：B1B2B3B4供应量A11020/105710/0A2139/2012820/0A34/1015/207930/20/0A4147/101/200/1040/30/10/0A53/501251950/0需求量60/10/060/50/30/10/020/010/0150至此，求得初始调运方案如下表所示：B1B2B3B4A11020/1057A2139/20128A34

7、/1015/2079A4147/101/200/10A53/50125192用位势法检验初始方案是否为最优。设有调运数量的运价Dij=Ui+Vj，i为行数，j为列数。可以列出如下方程组：20=U1+V29=U2+V24=U3+V115=U3+V27=U4+V21=U4+V30=U4+V43=U5+V1设U4=0，分别求出U1U5和V1V4，如下表所示B1B2B3B4A11020/1057U1=13A2139/20128U2=2A34/1015/2079U3=8A4147/101/200/10U4=0A53/5012519U5=7V1=-4V2=7V3=1V4=0设没有调运量的运价为Cij，如果

8、Cij不小于Ui+Vj，检验通过；否则在该运价上做记号，等待下一步调整。最终检验结果如下：初始方案B1B2B3B4A11020/1057U1=13A2139/20128U2=2A34/1015/2079U3=8A4147/101/200/10U4=0A53/5012519U5=7V1=-4V2=7V3=1V4=0第一次调整。对C13调整。为其寻找另外三个有调运量的价格元素，使这四个元素在表中形成矩形，即闭合回路。然后按照“最小运量，加减加减”的原则进行调整，过程如下：20/10  57/10   1/20调整为20    &

9、#160;  5/107/20   1/10第一次调整后的调运方案和新的U、V如下：第一次调整后B1B2B3B4A110205/107U1=4A2139/20128U2=2A34/1015/2079U3=8A4147/201/100/10U4=0A53/5012519U5=7V1=-4V2=7V3=1V4=0对该方案进行检验，结果如下：第一次调整后检验B1B2B3B4A110205/107U1=4A2139/20128U2=2A34/1015/2079U3=8A4147/201/100/10U4=0A53/5012519U5=7V1=-4V2=7V3=1

10、V4=0第二次调整。对C33调整。过程如下：15/20  77/20    1/10调整为15/10  7/107/30    1第二次调整后的调运方案和新的U、V如下：第二次调整后B1B2B3B4A110205/107U1=-2A2139/20128U2=-6A34/1015/107/109U3=0A4147/3010/10U4=-8A53/5012519U5=-1V1=4V2=15V3=7V4=0对该方案进行检验，结果如下：第二次调整后检验B1B2B3B4A110205/107U1=-2A2139/20128U

11、2=-6A34/1015/107/109U3=0A4147/3010/10U4=-8A53/5012519U5=-1V1=4V2=15V3=7V4=0第三次调整。对C52调整。过程如下：4/10  15/103/50  12调整为4/20  153/40  12/10第三次调整后的调运方案和新的U、V如下：第三次调整后B1B2B3B4A110205/107U1=11A2139/20128U2=9A34/20157/109U3=13A4147/3010/10U4=7A53/4012/10519U5=12V1=-9V2=0V3=-6V4=-7对该方案进行检验

12、，结果如下：第三次调整后检验B1B2B3B4A110205/107U1=11A2139/20128U2=9A34/20157/109U3=13A4147/3010/10U4=7A53/4012/10519U5=12V1=-9V2=0V3=-6V4=-7第四次调整。对C53调整。过程如下：4/20   7/103/40   5调整为4/30   73/30   5/10第四次调整后的调运方案和新的U、V如下：第四次调整后B1B2B3B4A110205/107U1=12A2139/20128U2=9A34/301579U3=13A4147/3010/10U4=7A53/3012/105/1019U5=12V1=-9V2=0V3=-7V4=-7经过检验，所