《《运筹学》胡运权清华版-2-01对偶问题.ppt》由会员分享，可在线阅读，更多相关《《运筹学》胡运权清华版-2-01对偶问题.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、返回返回返回返回继续继续继续继续第一节第一节第一节第一节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题n一、对偶问题的提出一、对偶问题的提出n二、原问题与对偶问题的数学模型二、原问题与对偶问题的数学模型n三、原问题与对偶问题的对应关系三、原问题与对偶问题的对应关系返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题实例：某家电厂家利用现有资源生产两种实例：某家电厂家利用现有资源生产两种 产品，产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时产品产品产品
2、产品D一、对偶问题的提出一、对偶问题的提出返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量产量返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 设：设备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时收收购购 付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。厂家觉得比厂家觉得比自己生产有利。自己生产有利。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 设备设备A y1 设备设备B
3、 y2调试工序调试工序y3利润（元）利润（元）0612521115时时24时时 5时时Dn厂家能接受的条件：厂家能接受的条件：n收购方的意愿：收购方的意愿：单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题厂厂家家对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问题一对对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题ma
4、xmin对对偶偶问问题题原问题原问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一般规律返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题.maxmin对对偶偶问问题题原问题原问题二、对称形式的对偶问题二、对称形式的对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题原问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题对偶问题返回返回返回返回上页
5、上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题可写成可写成YY返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 n n用矩阵表示用矩阵表示原问题原问题对偶问题对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题 特点：特点：1 2限定向量限定向量b 价值向量价值向量C （资源向量）资源向量）3一个约束一个约束 一个变量。一个变量。4 的的LP约束约束“”的的 LP是是“”的约束。的约束。5变量都是非负限制。变量都是非负限制。其它形式其它形式的对偶的对偶?n对偶问题的对偶是原问题对偶问题的对偶是原问题 返回返回返回
6、返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题三、非对称形式的对偶三、非对称形式的对偶 1 若原问题的约束条件中有等式若原问题的约束条件中有等式 例：求例：求LP问题的对偶问题问题的对偶问题第二个约束第二个约束是等式是等式返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题原问题原问题解：解：返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题对偶问题返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶
7、问问问问题题题题=maxmin对对偶偶问问题题原问题原问题无约束无约束结论：结论：等式等式约束约束 对偶对偶变量无约束变量无约束返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题？原问题（？原问题（max）的约束条件是的约束条件是例：例：(y2=-y2)返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题四、原问题与对偶问题的对应关系四、原问题与对偶问题的对应关系原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题n例例:返回返回返回返回上页上页上页上页下页下页下页下页对对对对偶偶偶偶问问问问题题题题对偶问题为对偶问题为返回返回返回返回第一节第一节第一节第一节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题