管理运筹学教学课件PPT对偶问题.ppt

对偶问题,一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系四、对偶问题的性质五、对偶问题的经济意义六、对偶单纯形法,例：某家电厂家利用现有资源生产两种产品，有关数据如下表：,一、对偶问题的提出,如何安排生产，使获利最多？,厂家,设 产量 产量,设：设备A 元时 设备B 元时 调试工序 元时,收购,付出的代价最小，且对方能接受。,出让代价应不低于用同等数量的资源自己生产的利润。,厂家能接受的条件：收购方的意愿：,出让代价应不低于用同等数量的资源自己生产的利润。,厂家,对偶问题,原问题,收购,3个约束2个变量,2个约束 3个变量,一般规律,特点：1 2限定向量b 价值向量C（资源向量）3一个约束 一个变量。4 的LP约束“”的 LP是“”的约束。5变量都是非负限制。,其它形式的对偶?,例:,对偶问题为,12,解：对偶规划：,写出下列线性规划的对偶问题,13,写出下列线性规划的对偶问题,解：上述问题的对偶规划：,性质1 对称性定理：对偶问题的对偶是原问题,性质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P)和(D)的可行解，则必有,推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,16,原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。,