基本信息

---

下载

文档摘要

---

线性规划的对偶理论

?1947年提出；

?支持对偶理论的思想是：每一个线性

规划问题都存在一个与其对偶的问题。

2

问题提出

某公司制造两种家电产品。假定：已知各制造一件

时分别占用的设备A、设备B的台时、调试时间以及

设备A、设备B和调试工序每天的可用能力、产品的

单件利润，如表所示，要确定A、B两种家电各生产

多少件，获利最大。

产品产品1产品2每天可用能力

设备A(h)0515

设备B(h)6224

调试工序115

单件利润21

3

这是一个典型的最优生产计划制定问题。制

定获得最大利润生产计划的线性规划问题为：

4

再从另一个角度看问题。假定：有另一个公司

想把该公司的资源收买下来，它至少应付多大的代

价才能让原公司愿意放弃生产活动出让资源。显然，

原公司出让自己资源的条件是：出让价不低于同等

资源由自己组织生产时获取的盈利。

设y,y,y分别代表单位时间(h)设备A、B及调试

123

工序的出让代价，则y,y,y应满足

123

5

又另外一个公司希望用个最小代价把该公司的

资源收买过来，有

综上，有

minw15y?24y?5y

123

6y?y?2

?23

?LP2??

s.t.?5y?2y?y?1

123

?

y?0,i1,2,3

?i

6

(LP1)与(LP2)两个线性规划问题的表现

形式和系数之间存在许多对应关系，并且

maxzminw

前者为原问题，后者是前者的对偶问题。

7

1.对称形式的对偶

minf15y?24y?5y