1、HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.1 对偶问题的提出例：某工厂有 A、 B两种设备，生产甲、乙两种产品。每件产品在生产中所占用的设备时数，设备 A、 B每天的可用能力及每件产品的利润如表所示，求最大利润方案。甲 乙 每天可用能力A 1 5 15B 6 2 24单件利润 2 1设备产品基本思想：每一个线性规划问题都存在一个与其对偶的问题。在求出其中一个问题的解时，同时给出了另一问题的解。解：设每天生产甲、乙产品分别为 件假设该工厂不生产甲、乙产品，将其所有资源出租或出售。出租条件：出租价格不低于由自己生产时的获利。设 表示单位
2、时间设备 A、 B的租金，则不少于甲产品利润：不少于乙产品利润： 同时租者希望租金越少越好：HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.1 对偶问题的提出则该线性规划问题为：该线性规划问题为原问题的对偶问题，两问题间存在许多联系。2.2 对偶问题与原问题设原问题为（矩阵形式）：检验数设则当 时有最优解即又对偶问题为：对偶问题 原问题HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题原问题为： 对偶问题为：n个变量， m个约束条件 m个变量， n个约束条件1.对称
3、形式的对偶关系当原问题与对偶问题满足以下条件：（ 1）原问题与对偶问题的变量均非负（ 0）（ 2）约束条件个数等于变量数；目标函数的系数是右端常数项。（ 3）目标函数取极大值时，约束条件均取 “”；目标函数取极小值时，约束条件均取 “”；则为对称（标准）形式下的线性规划对偶关系。HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题1.对称形式的对偶关系原问题 对偶问题Ab CC b约束条件系数矩阵b右端常数项C价值系数目标函数约束条件决策变量例：原问题 对偶问题HuBei University of Technology湖
4、北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题2.非对称形式的对偶关系例：写出下列线性规划的对偶问题解：目标函数为 “min”型，约束条件应为 “”，所有变量均 0两端 （ -1）等价为令即令HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题2.非对称形式的对偶关系根据约束条件令对应的对偶变量分别为令HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题2.非对称形式的对偶关系方法：将上述问题先变为 “标准 ”（对称）形式的线性规划原问
5、题，再按照对称形式下线性规划对偶关系写出对偶问题。原问题 对偶问题max min目标函数中变量的系数 约束条件右端常数项约束条件右端常数项 目标函数中变量的系数变量n个00无约束约束条件n个=HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.2 对偶问题与原问题2.非对称形式的对偶关系原问题与对偶问题变换规则： 约束条件为等式，其对偶问题的变量无约束； 符号相同的变量，其对偶问题的约束条件符号相同；符号相同的约束条件，其对偶问题的变量符号相同； 符号相反的变量，其对偶问题的约束条件符号也相反；符号相反的约束条件，其对偶问题的变量符号也相反；
6、例：写出下列线性规划的对偶问题HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.3 对偶问题的基本性质设原问题与对偶问题为 对称（标准）形式 线性规划问题。原问题：对偶问题：HuBei University of Technology湖北工业大学第 2章 线性规划的对偶理论2.3 对偶问题的基本性质2.3.1 基本性质1.对称性：对偶问题的对偶是原问题。2.弱对偶性：若 是原问题的可行解， 是对偶问题的可行解，则存在 证明：设 是原问题的可行解，满足约束条件，即设 是对偶问题的可行解，满足约束条件，即3.最优性：设 是原问题的可行解， 是对偶问题的可行解，当 时，是最优解。
