大鲲逍遥居分享 http://blog.sciencenet.cn/u/sjk

博文

原规划与对偶规划问题的变量及解之间的对应关系

已有 27827 次阅读 2013-4-18 19:59 |系统分类:教学心得| 运筹学, 对偶问题

原规划与对偶规划问题的变量及解之间的对应关系

除了互补松弛定理求解外,还有如下的直观关系:

1)对偶(min)变量的最优解等于原问题松弛变量检验数的绝对值

2)对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值

3)由于原问题和对偶问题是相互对偶的,因此对偶问题的检验数与原问题的解也有类似上述关系。

4)更一般地讲,不管原问题是否标准,在最优解的单纯型表中,都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解,原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此,原问题或对偶问题只需求解其中之一就可以了。

1  两个互为对偶的线性规划问题:

两者分别加上松弛和剩余变量后为:

两个问题的最终单纯形表(注第2张表以最小化为目标)见:

原问题变量

松弛变量

Cjà

2

1

0

0

0

CB

XB

b

x1

x2

x3

x4

x5

0

x3

15/2

0

0

1

5/4

-15/2

2

x1

7/2

1

0

0

1/4

-1/2

1

x2

3/2

0

1

0

-1/4

3/2

Cj-zj

0

0

0

-1/4

-1/2

对偶问题的剩余变量

对偶问题变量

y4

y5

y1

y2

y3

对偶问题变量

对偶问题的剩余变量

Cjà

15

24

5

0

0

CB

XB

b

y1

y2

y3

y4

y5

24

y2

1/4

-5/4

1

0

-1/4

1/4

5

y3

1/2

15/2

0

1

1/2

-3/2

Cj-zj

15/2

0

0

7/2

3/2

原问题的松弛变量

原问题变量

x3

x4

x5

x1

x2

明显可见其中类似(4)的对应关系。



https://blog.sciencenet.cn/blog-71538-681559.html

上一篇:为什么JIT会在日本诞生?
下一篇:项目最终是要顾客满意!
收藏 IP: 222.195.188.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-9-27 11:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部