文档介绍：运筹帷幄之中
决胜千里之外
对偶理论
运筹学课件
对偶理论
对偶问题
对偶理论
对偶单纯形算法
对偶问题的提出
例:设某企业有m种资源,用于生产n种不同的产品,各种资源的拥有量为bi(i=1,2,…m),又知生产单位第j种产品(j=1,2,…n)消费第i种资源aij单位,产值为cj元。若用xj表示第j种产品的生产量,求产值最大,LP模型为:
任意线性规划问题都存在一个与之伴随的对偶问题
现从另一角度提出问题:假设此企业拥有资源但未生产,而另一企业预将上述企业拥有的资源买过来,至少应付出多少代价,才能使前一企业愿意放弃生产活动,出让资源。
若设yi表示收买该企业一单位i种资源时付出的代价。则另一线性规划问题为:
收买的企业付出的代价是该商品的价格吗?若不是,它和原本的价格是什么关系?
收购资源的企业能赚钱吗?怎么赚?
原问题与对偶问题对应关系
原问题(L)
一
一
对
应
对偶问题(D)
max问题
min问题
有m个约束条件
有m个变量
第j个约束条件为≤关系
第j个变量≥0
第j个约束条件为≥关系
第j个变量≤0
第j个约束条件为等式关系
第j个变量无非负约束,自由变量
第j个变量≥0
第j个约束条件为≥关系
第j个变量≤0
第j个约束条件为≤关系
第j个变量无非负约束,自由变量
第j个约束条件为=关系
资源向量
价值向量
价值向量
资源向量
实例
对偶问题的基本性质
以下各性质基于如下假设
原问题
对偶问题
若
是原问题的可行解,
是其对偶问题的可行解,则恒有
证明
性质1(弱对偶性)
若
是原问题的可行解,
是其对偶问题的可行解,且有
则
是原问题的最优解,
是其对偶问题的最优解。
性质2(最优性)
性质 2 证明
又因为
则