1、第 3章 对偶线性规划线性规划的对偶问题对偶问题的基本性质对偶的经济解释灵敏度分析 *DUAL主讲人 ： 晋琳琳项 目 产品 产品 每天可利用能力原材料 A（ 千克） 1 2 5原材料 B（ 吨） 2 1 4设备 C（ 百工时）4 3 9利 润（万元） 3 2一、线性规划的对偶问题如何将生产能力出让出去 ?设 y1,y2和 y3分别表示出让资源 A， B和 C的单价，则穗羊公司同意出让的条件将是同意出让生产产品 I的资源同意出让生产产品 II的资源购买者希望用最少的代价获得这些资源 ，因此这样得到一个新的线性规划问题称这一问题是原来的 LP问题的 对偶线性规划问题 或 对偶问题 。原问题 对偶
2、问题原问题max z=C Xs.t. AX bX 0对偶问题min w=bYs.t. AY CY 0 CAbminmnmaxbACmn1、规范形式下的原问题与对偶问题LP问题的规范形式问题的规范形式 变量变量 ：所有变量均具有非负约束：所有变量均具有非负约束 约束条件约束条件 ：最大化问题最大化问题 所有约束条件都是所有约束条件都是 “”型型最小化问题最小化问题 所有约束条件都是所有约束条件都是 “”型型原问题（对偶） 对偶问题（原）系数矩阵约束条件右端向量目标函数系数向量目标函数系数向量max z = C X min w = Y bAX b AY CX 0 Y 0bc 约束条件右端向量目标函数约束条件决策变量原问题变量个数 =对偶问题约束条件方程个数原问题约束条件方程个数 =对偶问题变量个数2、非规范形式下的原问题与对偶问题 (x变 )2、非规范形式下的原问题与对偶问题 (方程变 )
