1、返回返回返回返回继续继续继续继续第一节第一节第一节第一节 线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题n一、一、对偶偶问题的提出的提出n二、原二、原问题与与对偶偶问题的数学模型的数学模型n三、原三、原问题与与对偶偶问题的的对应关系关系实例：美佳公司利用现有资源生产两种实例：美佳公司利用现有资源生产两种 产品，产品，有关数据如下表：有关数据如下表：设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时产品产品产品产品D一、一、对偶偶问题的提出的提出如何安排生产，如何安排生产，使获利最多使获利最多？厂厂家家设设 产量产量 产量
2、产量 设：设备设：设备A A 元时元时 设备设备B B 元时元时 调试工序调试工序 元时元时收收购购 付出的代价最小，付出的代价最小，且对方能接受。且对方能接受。出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。设备设备A 设备设备B调试工序调试工序利润（元）利润（元）0612521115时时24时时 5时时Dn厂家能接受的条件：厂家能接受的条件：n收收购方的意愿：方的意愿：单位产品单位产品出租出租收入不低于收入不低于2 2元元单位产品单位产品出租出租收入不低于收入不低于1 1元元出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己
3、生产的利润。自己生产的利润。厂厂家家对对偶偶问问题题原原问问题题收收购购厂厂家家一对对偶问题一对对偶问题3 3个约束个约束2 2个变量个变量2 2个约束个约束 3 3个变量个变量原问题原问题对偶问题对偶问题一般规律 特点：特点：1 2限定向量限定向量b 价值向量价值向量C （资源向量）资源向量）3一个约束一个约束 一个变量。一个变量。4 的的LP约束约束“”的的 LP是是“”的约束。的约束。5变量都是非负限制。变量都是非负限制。其它形式其它形式的对偶的对偶?二、原二、原问题与与对偶偶问题的数学模型的数学模型n1对称形式的称形式的对偶偶 当原问题对偶问题只含有不等式约束时，称当原问题对偶问题只含
4、有不等式约束时，称为对称形式的对偶。为对称形式的对偶。原问题原问题对偶问题对偶问题情形一：情形一：原问题原问题对偶问题对偶问题化为标准对称型化为标准对称型情形二：情形二：证明证明对偶对偶n2、非非对称形式的称形式的对偶偶 若原问题的约束条件是等式，则若原问题的约束条件是等式，则原问题原问题对偶问题对偶问题推导推导:原问题原问题 根据对称形式的对偶模型根据对称形式的对偶模型,可直接可直接写出上述问题的对偶问题写出上述问题的对偶问题:令令 ，得对偶问题为：，得对偶问题为：证毕。证毕。三、原三、原问题与与对偶偶问题的的对应关系关系 原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）n例例:对偶问题为对偶问题为返回返回返回返回线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题线性规划的对偶问题
