ERP高级计划书的解读―APS算法分析之单一内点方

1、1.单一方法(1),单一算法最初的单一方法的案例目标函数Z = 500 x X + 300 XY => max!约束X £6丫 £82 XX+ 3 X Y £ 24X,Y 3 0Z-500 X X-300 X Y = 0X+ V1=6Y+V2 =82 XX +3 X Y+ V3 =24X, Y ,V1,V2,V330开始表根本XYV1V2V3力杀V1101006V2010108V32300124Z-500-3000000-最大目标函数的算法约束被转换成增加松散变量V1,V2,V3的限制一单一方法的意思：V1,V2,V3在方法里,用一个非根本变量改变一个根本变

2、量-目标值增加 -根本变量的值和剩余非-负值-根本改变的优选：在目标函数行里,非根本变量和负系数-如果目标函数的所有系数是非负的,最正确方案就找到了.算法：非根本变量的选择是在根本里：1 .重要列的决定：在目标函数行的最低负系数的变量被选择,由于目标值增加大局部是这个 变量这里：X和 500.在这个顺序,重要栏目是q 这里：q = 1重点要素：A11根本XYV1V2V3力杀印V11010066V2010108-V3230012412Z-500-3000000重要步骤根本XYV1V2V3力杀X101006V2010108V303-20112Z0-3005000030002 .重要行的决定：目标函

3、数增加的值是随着新的根本变量的值.如这个值应该尽可能的大.一般来说,新的根本变量的增加会导致其它一变量的减少,由于,否那么约束就会冲突.如人力约束.因此,新根本变量增加是有条件限制的,其条件是其它根本变量剩余非-负的值.新的根本变量唯一被增加,直到其它变量之一的值等于0.这个变量将是根本.决定这个瓶颈的所有系数 aiq > 0 重要列q的商计算如下：对所有行i和aiq > 0bi是在方案列里行的系数值.那么在行P的变量必须被根本的在最低的非-负的值的商如：印的值是6.重要因素：all 行p=1,列q=13 .重要步骤：在重要行里用'1'创立一单位向量,如 a*pq

4、=14 .优化条件:,如果目标函数的行的所有系数是非负的,就找到最正确方案.否那么就回到第一步选择总要列这里：优化条件是不能完成的.=> 回到第一步.待续本文由作者向AMT提供作者联系方式：ycaifs 蔡颖专栏重要要素：a32根本XYV1V2V3方案0X101006-V20101088V303-201124Z0-300500003000重要步骤:根本XYV1V2V3方案X101006V2002/31-1/34Y01-2/301/34Z0030001004200第二重要步骤之后：最正确方案是 X=6和Y=4,目标值是Z = 4200.根本XYV1V2V3方案X101006V2002/31

5、-1/34Y01-2/301/34Z0030001004200故每天生产数量：标准沙发：X = 6特别沙发：Y = 4每天利润：4200 RMB(2)最初的和二元单一的关系Min u >b1:1u >A > c案例:Max 500 X1 +300 X X2Min 6 U1 + 8 U2 + 24 X U3X1 £ 6U1 + 0 XU2 + 2 X U3 > 500X2 £ 80 >U1 + U2 + 3 U3 > 3002 )X1 + 3 >X2 £ 24U1, U2, U3 > 0X1, X2 3 0开始表：根本

6、XTVT方案VA_bZ-cT0T0最后表：根本XTVT方案XBB-1 A_B-1B-1 b_ZcBTJ-l A二空cBTB-1cBTB-1 b_二元变量：U = cBT B-1减少本钱： W = cBT B-1 A -cT注意：T匹配列的发散向量=> 行向量X 决策/问题变量向量V 松散变量的向量=初始化表格里的根本变量A 约束矩阵L 单元矩阵b -右方面向量c“价格向量对决策变量的目标函数系数的向量0包含只有0的向量B-1 -根本矩阵逆转它可以在列下松散变量找到cB =根本变量的目标函数系数的向量就像在列里的“根本根本变量的顺序待续本文由作者向AMT提供作者联系方式：ycaifs 蔡颖

7、专栏« ERP高级方案?书的解读 一APS算法分析之单一：内点方法 三蔡颖文档号:00.050.714 时间：10-11-20042,内部点法开始方案单一算法单一：算法是从多面的顶点到一新的顶点,用一次沿着一边推进的移动.内部点法IPM:算法是通过多面的内部的移动.比拟：1. LP的优化问题总是落在顶点.如一可行区域分解线的极点.2. 通过内部区域的移动算法必须注意一个事实,它就是不要离开可行区域.到达可行区域的分解线要被惩罚的.这个惩罚是动态的减少,以至于找到在分解线的一个方案.3. 内部点法包含复杂的数学和使用高等数学的概念.内部点法IPMs的大量变量已经完成开发.在线性规划,内

8、部点发较好是适用,特别是巨大,稀罕的问题.这里,要考虑计算的时间.优化方案的解释根本XYV1V2V3方案X101006V2002/31-1/34Y01-2/301/34Z0030001004200利润=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 减少本钱-> 决策变量:如果一个变量在优化方案里取一正值,它就表现

9、为它可以对最大化问题有有用的奉献.如果变量的值是0,它的减少本钱告诉我们多少目标函数系数必须增加,为了到达非-零值.或者,减少本钱也许告诉我们有多少变量比起其它变量是“低于价格在最大化问题里o对于根本变量减少本钱总是等于0. 影子价格-> 约束：约束的二元值是可以在约束的右面里用一个单位增加,得到增加的对最大化问题.如人工约束的一个单位的增加将对目标函数产生100RMB o这个二元值还可以作为在目标函数里的单位增加是由约束的右面的单位增加引起的.如果一限制没有约束力或没有活动,那么,二元变量就是0,就有一些松散变量可用.-注意减少本钱和影子价格是边际概念是一样的LP的案例2Max 2A - B+ C 目标函数3A + B + C £60约束-资源110约束-资源2A + B - C£20约束-资源3A,B,C30非-负-约束优化方案:根本ABCV1V2V3方案V10011-1-210A100.500.50.515B01-1.50-0.50.55利润001.501.50.525决策变量：A = 15, B = 10, C = 0 => 利润=25松散变量：V1 = 10, V2 = 0, V3 = 0影子价格:U1 = 0, U2 = 1.5, U3 = 0.5减少本钱=相对利润：W1 = 0, W2 =