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

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

－开始表: 

－最大目标函数的算法

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

－ 单一方法的意思：

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

       - 目标值增加

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

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

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

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

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

重点要素: A11

重要步骤:

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

                     qi= bi/ aiq  对所有行 i 和 aiq > 0
 
bi 是在方案列里行的系数值。那么在行P的变量必须被基本的在最低的非－负的值的商 qi (如: q1的值 是 6).    

重要因素: a11 (行p=1, 列 q=1)

3. 重要步骤:在重要行里用 `1`创建一单位向量，如 a*pq =1

4. 优化条件:,如果目标函数的行的所有系数是非负的，就找到最佳方案。否则就回到第一步（选择总要列）

这里: 优化条件是不能完成的。 => 回到第一步.

（待续）

相关链接：

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

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