文档介绍：运输问题的表上作业法
一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案,如图3-1所示。
表上作业法和单纯形法的求解思想完全一致,但是具体作法更加简捷。
确定初始方案
( 初始
基本可行解)
改进调整
(换基迭代)
否
判定是否
最优?
是
结束
最优方案
图3-1 运输问题求解思路图
二、初始方案的确定
1、作业表(产销平衡表)
初始方案就是初始基本可行解。
将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”(产销平衡表)。
表3-3是两个产地、三个销地的运输问题作业表。
调销地
运
量
产地
B1
B2
B3
产量
A1
c11
X11
c12
X12
c13
X13
a1
A2
c21
X21
c22
X22
c23
X23
a2
销量
b1
b2
b3
表3-3 运输问题作业表(产销平衡表)
其中xij是决策变量,表示待确定的从第i个产地到第j个销地的调运量,cij为从第i个产地到第j个销地的单位运价或运距。
2、确定初始方案的步骤:
(1)选择一个xij,令xij= min{ai,bj}=
将具体数值填入xij在表中的位置;
(2)调整产销剩余数量:从ai和bj中分别减去xij的值,若ai-xij=0,则划去产地Ai所在的行,即该产地产量已全部运出无剩余,而销地Bj尚有需求缺口bj-ai;若bj-xij =0,则划去销地Bj所在的列,说明该销地需求已得到满足,而产地Ai尚有存余量ai-bj;
(3)当作业表中所有的行或列均被划去,说明所有的产量均已运到各个销地,需求全部满足,xij的取值构成初始方案。否则,在作业表剩余的格子中选择下一个决策变量,返回步骤(2)。
按照上述步骤产生的一组变量必定不构成闭回路,其取值非负,且总数是m+n-1个,因此构成运输问题的基本可行解。
对xij的选择采用不同的规则就形成各种不同的方法,比如每次总是在作业表剩余的格子中选择运价(或运距)最小者对应的xij,则构成最小元素法,若每次都选择左上角格子对应的xij就形成西北角法(也称左上角法)。
3、举例
例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤,各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4,求使总运输量最少的调运方案。
表3-4 例3-2有关信息表
450
200
150
100
日销量
(需求量)
250
75
65
80
乙
200
100
70
90
甲
日产量
(供应量)
C
B
A
运距城市
煤矿
例3-2 的数学模型