对偶理论及灵敏度分析1

《对偶理论及灵敏度分析1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章对偶理论及灵敏度分析3.1.1线性规划对偶问题3.1.2对偶问题的基本性质3.1.3影子价格3.1.4对偶单纯形法3.2.1灵敏度问题及其图解法3.2.2灵敏度分析3.2.3参数线性规划返回继续3.1.1线性规划的对偶问题一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––设：设备A——元／时设备B––––元／时调试工序–––

2、–元／时收购付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备A设备B调试工序利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：收购方的意愿：单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。厂家对偶问题原问题收购厂家一对对偶问题3个约束2个变量2个约束3个变量原问题对偶问题一般规律特点：1．2．限定向量b价值向量C（资源向量）3．一个约束一个变量。4．的LP约束“”的LP是“”的约束。5．变量都是非负限制。其它形式的对偶?二、原问题与对偶问题的数学模型1．对称形式的对

3、偶当原问题对偶问题只含有不等式约束时，称为对称形式的对偶。原问题对偶问题情形一：原问题对偶问题化为标准对称型情形二：证明对偶2、非对称形式的对偶若原问题的约束条件是等式，则原问题对偶问题推导:原问题根据对称形式的对偶模型,可直接写出上述问题的对偶问题:令，得对偶问题为：证毕。三、原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）例:对偶问题为返回结束线性规划的对偶问题返回继续3.1.2对偶问题的基本性质引例对称性弱对偶性最优性对偶性（强对偶性）互补松弛性对偶问题原问题收购厂家引例（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问

4、题化为极小问题，最终单纯形表：原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量对偶问题用两阶段法求解的最终的单纯形表（）原问题的变量原问题松弛变量对偶问题剩余变量对偶问题的变量化为极小问题原问题最优解对偶问题最优解原问题化为极小问题，最终单纯形表：两个问题作一比较:1.两者的最优值相同2.变量的解在两个单纯形表中互相包含原问题最优解（决策变量）对偶问题最优解（决策变量）对偶问题的松弛变量原问题的松弛变量从引例中可见：原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。理论证明：原问题与对偶问题解的关系对偶问题的基本性

5、质一、对称定理：定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2）二、弱对偶性定理：——若和分别是原问题（1）及对偶问题（2）的可行解，则有证明：对偶问题的基本性质从弱对偶性可得到以下重要结论：（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。（6）对偶

6、问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。原问题对偶问题三、最优性定理：——若和分别是（1）和（2）的可行解，且有则分别是（1）和（2）的最优解。则为（1）的最优解，反过来可知：也是（2）的最优解。证明：因为（1）的任一可行解均满足对偶问题的基本性质证明：原问题与对偶问题的解一般有三种情况：一个有有限最优解另一个有有限最优解。一个有无界解另一个无可行解。两个均无可行解。四、对偶定理（强对偶性）：——若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。对偶问题的基本性质五、互补松弛性：——若分别是原问题（1）与对偶问题（2

7、）的可行解，分别为（1）、（2）的松弛变量，则：即：为最优解原问题第i条约束A的第i行说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件去严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。另一方面：对偶问题的第j条约束互补松弛定理应用：（1）从已知的最优对偶解，求原问题最优解，反之亦然。（2）证实原问题可行解是否为最优解。（3）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。（4）非线性的方面的应用。以上性质同样适用于非对称形式。返回结束对偶问题的基本性质返回继续3.1.3