现代物流运筹学第2版：表上作业法——最优性检验、调整PPT教学课件.pptx

表上作业法——最优性检验、方案调整

《现代物流运筹学》

1.西北角法

2.最小元素法

3.伏格尔法

1.闭回路法

2.位势法

闭回路法

表上作业法步骤

基可行解的最优性检验

对初始基可行解的最优性检验有闭合回路法和位势法两种基本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。

所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个空格存在唯一的闭回路。

闭合回路法

所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。

最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。

举例

产量

产地

销地

A1A2A3

B1B2B3B4

销量

4

1

3

10

2

5

3656

749

3

11

9

8

7

10

运价

总产=总销

最优性检验——闭回路法

表示什么？

每个空格都能找到闭回路吗？有的话，是否唯一？

每个空格有且只有一条闭回路！

甲

乙

丙

丁

产量（ai）

A

11=1

12=2

4

3

7

B

3

22=1

1

24=-1

4

C

31=10

6

33=12

3

9

销量（bj）

3

6

5

6

表1闭回路法求检验数汇总表

如何判断初始方案是否达到最优？

若存在某些检验数小于0，则说明调整后运价将减少。（不是最优解）

若存在某些检验数等于0，则说明调整后运价将不发生改变。（多个最优解）

若所有检验数大于0，说明调整后运价将增加。（唯一最优解）

最优方案：所有检验数≥0

注意是目标最小化的问题

方案调整

闭回路法

方案调整（闭回路法）

当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。

步骤：1.若检验数σij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量θ

若有多个检验数小于零，则取其中最小的负数

继续上例，因σ24=-1，画出以x24为起始变量的闭回路

计算调整量：θ=Min（3，1）=1

2.按照下面的方法调整调运量：

闭回路上，偶数次顶点的调运量减去θ，奇数次顶点（包括起始顶点）的调运量加上θ；闭回路之外的变量调运量不变。

B1

B2

B3

B4

A1

5

2

A2

3

1

A3

6

3

3.得到调整后的调运方案：

4.计算新方案的检验数，重复上述步骤，直至所有检验数都≥0，即得到最优方案。

最优调运方案

B1

B2

B3

B4

A1

5

2

A2

3

1

A3

6

3

相应的最小总运费为：

感谢观看

《现代物流运筹学》