《 ERP高级计划》书的解读之二APS算法分析之单一：内点方法（蔡颖）(转)

《 ERP高级计划》书的解读之二APS算法分析之单一：内点方法（蔡颖）

http://www.amteam.org/k/Board/2004-11/0/484323.html

1. 单一方法

（1），单一算法

－最初的单一方法的案例

目标函数

Z = 500×X + 300×Y => max!

约束

X ￡ 6

Y ￡ 8

2 ×X+ 3×Y ￡24

X,Y3 0

Z-500×X-300×Y = 0

X+ V1=6

Y+V2 =8

2 ×X +3×Y+ V3 =24

X, Y ,V1,V2,V3 30

－开始表:

基本	X	Y	V1	V2	V3	方案
V1	1	0	1	0	0	6
V2	0	1	0	1	0	8
V3	2	3	0	0	1	24
Z	-500	-300	0	0	0	0

－最大目标函数的算法

－约束被转换成增加松散变量V1,V2,V3的限制

－单一方法的意思：

在方法里，用一个非基本变量改变一个基本变量 V1,V2,V3

- 目标值增加

- 基本变量的值和剩余非－负值

－基本改变的优选：在目标函数行里，非基本变量和负系数

－如果目标函数的所有系数是非负的，最佳方案就找到了。

算法：非基本变量的选择是在基本里：

1. 重要列的决定: 在目标函数行的最低负系数的变量被选择，因为目标值增加大部分是这个变量（这里: X 和 –500). 在这个顺序，重要栏目是q (这里: q = 1)

重点要素: A11

基本	X	Y	V1	V2	V3	方案	qi
V1	1	0	1	0	0	6	6
V2	0	1	0	1	0	8	-
V3	2	3	0	0	1	24	12
Z	-500	-300	0	0	0	0

重要步骤:

基本	X	Y	V1	V2	V3	方案
X	1	0	1	0	0	6
V2	0	1	0	1	0	8
V3	0	3	-2	0	1	12
Z	0	-300	500	0	0	3000

2. 重要行的决定: 目标函数增加的值是随着新的基本变量的值。如这个值应该尽可能的大。一般来说，新的基本变量的增加会导致其它一变量的减少，因为，否则约束就会冲突。（如:人力约束). 因此，新基本变量增加是有条件限制的，其条件是其它基本变量剩余非－负的值。新的基本变量唯一被增加，直到其它变量之一的值等于0。这个变量将是基本。决定这个瓶颈的所有系数 aiq > 0 重要列q 的商计算如下：

qi= bi/ aiq 对所有行 i 和 aiq > 0

bi 是在方案列里行的系数值。那么在行P的变量必须被基本的在最低的非－负的值的商 qi (如: q1的值是 6).