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

调运问题-表上作业法 基本思路：1.建立供需平衡运价表2.用最小元素法求出初始调运方案3.用位势法检验初始调运方案4.用闭合回路法调整初始调运方案5.重复步骤34，直到出现最优调运方案6.计算最少总运费在供销不平衡的情况下，可用以下办法进行解决：1供大于求-引入虚拟需求点，其需求量等于实际供应量与需求量之差，该点运价为零。2供小于求-引入虚拟供应点，其供应量等于实际需求量与供应量之差，该点运价为零。例题：设有5个产地a1、a2、a3、a4、a5和4个销地b1、b2、b3、b4的运输问题，他们的供应量和需求量及单位运费如下表，试计算其最小运输成本。b1b2b3b4供应量a110205710a213912820a34157930a41471040a531251950需求量60602010150解：1该案例属于供需平衡，下面直接用最小元素法求出初始调运方案。在所有运价中，找出最小运价为0，该运价对应的需求量为10，供应量为40，即需求量可以得到全部满足。将调运数量和a4、b4的剩余供需数量在表上做出记号，同时由于b4的需求已经满足，可以划去该列其他的各个运价。结果如下：b1b2b3b4供应量a110205710a213912820a34157930a414710/1040/30a531251950需求量60602010/0150在剩下的运价中，最小运价为1，调运结果如下：b1b2b3b4供应量a110205710a213912820a34157930a41471/200/1040/30/10a531251950需求量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供应量a110205710a213912820a34/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/0a34/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/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，如果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调整为205/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=1v4=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/20128u2=-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对该方案进行检验，结果如下：第三次调整后检验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=12v