ITPub博客

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

原创 Linux操作系统 作者:urinator 时间:2007-08-04 00:00:00 0 删除 编辑

《 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).

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

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

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

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

重要要素: a32

基本

X

Y

V1

V2

V3

方案

qi

X

1

0

1

0

0

6

-

V2

0

1

0

1

0

8

8

V3

0

3

-2

0

1

12

4

Z

0

-300

500

0

0

3000

重要步骤:

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7942439/viewspace-20262/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2007-12-06

  • 博文量
    3875
  • 访问量
    1801239