《运筹学》胡运权清华版-2-01对偶问题.pptx

返回继续第一节线性规划的对偶问题一、对偶问题的提出二、原问题与对偶问题的数学模型三、原问题与对偶问题的对应关系

实例：某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD一、对偶问题的提出

如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––

设：设备A——元／时设备B––––元／时调试工序––––元／时收购付出的代价最小，且对方能接受。厂家觉得比自己生产有利。

设备Ay1设备By2调试工序y3利润（元）0612521115时24时5时ⅠⅡD厂家能接受的条件：收购方的意愿：单位产品Ⅰ出租收入不低于2元单位产品Ⅱ出租收入不低于1元出让代价应不低于用同等数量的资源自己生产的利润。

厂家对偶问题原问题收购厂家一对对偶问题

≤≤≤maxmin≥≥对偶问题原问题

3个约束2个变量2个约束3个变量原问题对偶问题一般规律

≤≤...≤maxmin≥对偶问题原问题≥≥二、对称形式的对偶问题

原问题

对偶问题

YAYB可写成

用矩阵表示原问题对偶问题

特点：1．2．限定向量b价值向量C（资源向量）3．一个约束一个变量。4．的LP约束“”的LP是“”的约束。5．变量都是非负限制。其它形式的对偶?对偶问题的对偶是原问题

非对称形式的对偶若原问题的约束条件中有等式例：求LP问题的对偶问题1第二个约束是等式2

P1原问题P2解：

对偶问题

对偶问题

结论：等式约束对偶变量无约束≤=≤maxmin≥≥对偶问题原问题无约束

例：01(y2’=-y2)02？原问题（max）的约束条件是≥

四、原问题与对偶问题的对应关系对偶问题（或原问题）原问题（或对偶问题）

例:

对偶问题为

返回结束第一节线性规划的对偶问题