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

2， 内部点法

－单一: 算法是从多面的顶点到一新的顶点，用一次沿着一边推进的移动。

－内部点法 (IPM): 算法是通过多面的内部的移动。

－比较:

1.       LP的优化问题总是落在顶点。如一可行区域分解线的极点。

2.      通过内部区域的移动算法必须注意一个事实，它就是不要离开可行区域 。达到可行区域的分解线要被惩罚的。这个惩罚是动态的减少，以至于找到在分解线的一个方案。  

3.      内部点法包含复杂的数学和使用高等数学的概念。内部点法IPMs的大量变量已经完成开发。在线性规划，内部点发较好是适用，特别是巨大，稀罕的问题。这里，要考虑计算的时间。

优化方案的解释

－利润 = 4200

－决策变量: X = 6, Y = 4

－闲散变量: V1 = 0, V2 = 4, V3 = 0

－影子价格 : U1 = 300, U2 = 0, U3 = 100

－减少成本 (= 相关利润): W1= 0, W2 =0.

－人工能力是充分利用。因此一约束力的约束 (V3=0). 标准沙发的是 (V1=0) 那里对特别沙发就没有约束力的约束 (V2>0)

－减少成本 (-> 决策变量):

如果一个变量在优化方案里取一正值，它就表现为它可以对最大化问题有有用的贡献。 如果变量的值是0，它的减少成本告诉我们多少目标函数系数必须增加，为了达到非－零值 。或者，减少成本也许告诉我们有多少变量比起其它变量是“低于价格”   (在最大化问题里)。

对于基本变量减少成本总是等于0。

－影子价格 (-> 约束):

?         约束的二元值是可以在约束的右面里用一个单位增加， 得到增加的(对最大化问题)。如 人工约束的一个单位的增加将对目标函数产生100RMB 。这个二元值还可以作为在目标函数里的单位增加是由约束的右面的单位增加引起的。

?         如果一限制没有约束力或没有活动，那么，二元变量就是0，就有一些松散变量可用。

－注意减少成本和影子价格是边际概念是一样的。

LP的案例2 

Max   2A  -  B    +  C  (目标函数) 

       3A  + B  + C  ￡  60   (约束 – 资源 1) 

       A  - B  + C     ￡   10  (约束 –资源 2) 

       A  + B  - C      ￡   20  (约束 – 资源 3) 

        A,B,C          3     0  (非-负-约束)     

优化方案： 

－决策变量: A = 15, B = 10, C = 0 => 利润 = 25

－松散变量: V1 = 10, V2 = 0, V3 = 0

－影子价格: U1 = 0, U2 = 1.5, U3 = 0.5

－减少成本 (= 相对利润):

                  W1 = 0, W2 = 0, W3 = 1.5

如果目标函数C的系数增加1.5，如它等于2.5, 那么这个决策变量会是一个正值, 如. 它会考虑基本。

总结：

方案技术方法:1，原始单一  2，二元单一  3，内部点方法

每一个方法找到最佳的方案, 但是计算时间可能有很大不同。 没有同一的选择，性能依赖具体数据的问题。APS优化时，二元单一法比较流行。 (完)

本文由作者向AMT提供

蔡颖 专栏

微信扫一扫实时了解行业动态

微信扫一扫分享本文给好友