第二节
表上作业法 (1) (2)
(3) (4) (5)
2.位势法
用闭回路法求检验数时,需要找出每个空格所在的闭回路,当产销点很多时,计算量非常大。
下面介绍一种求检验数的简便方法——位势法。
设 是运输问题的m+n个约束条件对应的对偶变量,决策变量Xij对应的列向量 ,对于一个基可行解,由单纯形法得知所有基变量Xij(数字格)的检验数等于0,即 ,所以由m+n-1个数字格对应的 及u1=0即可确定所有ui,vj的值。
称 分别为产销平衡表各行与各列的位势。
因为非基变量(空格)检验数 ,所以,只要计算出所有位势值,就能求出各空格的检验数。
这些计算可以直接在表格中进行。以例1的初始方案为例:
初始方案表:
单位运价表
先由m+n-1个数字格对应的 ,确定所有ui,vj的值。
令u1=0,由(1,3)处数字格运价3=u1+vs,可得v3=3,类似可求得其它 的值,见方案表中红色数字。
再按公式 计算空格的检验数,结果见方案表中带括号的红色数字。
可以验证,按位势法与按闭回路法算得的检验数完全一致。
事实上,若设空格(i,j)所在闭回路上数字格依次位 ,则按闭回路可以算得:
|