线性规划的对偶问题.ppt

第四章线性规划的对偶问题

4.1对称的对偶规划

在线性规划早期发展中,对偶问题是一项重要的

发现。早在1928著名数学家在研究对策理论时

就已经有原始和对偶的思想。

对偶理论有着重要的应用。首先是在原始和对偶两个线性

规划中求解任一规划时，会自动地给出另一个规划的最优

解。当对偶问题比原问题有较少分量时，求解对偶问题比

求解原始问题方便得多。对偶理论另一个应用是Lemke，

1954提出的对偶单纯形法。

对偶理论对影子价值的分析在经济理论上有着

重要作用。

资源甲乙丙丁每台收益

产品

A32112000

B41324000

C22343000

资源总量600400300200

一对偶问题的提出:

例:某厂生产三种畅销产品,每台产品需四种

maxz2000x4000x3000x

123资源,具体数据表：

3x14x22x3600



2x1x22x3400问怎样安排生产,效益最大？



s.t.x3x3x300

123设决策变量得出模型:

x2x4x200

123

xi0.i1,2,3

现在工厂考虑不进行生产而把全部可利用的资源都让给其它企业单位,但

又希望给这些资源订一个合理价格,既使别的单位愿意买,又使工厂能得到生

产这些产品时可以得到的最大效益.

这就需建立另一个线性规划模型,设y1,y2代,y表3y销4售这四种资

源的价格，买方希望总售价尽可能低,即：

minw600y1400y2300y3200y4

原来生产产品A每台需用的资源按现在的单价计算,每台收益为:

3y12y2y3y4

为了使工厂效益不减少,就要求订y1,y2,时y3,,使y这4个效益额不低于原来

生产一台产品A可以得到的效益,因此满足约束:

3y12y2y3y42000

对产品可列出类似约束

B,C.4y1y23y32y44000

2