ch2-1对偶问题.ppt

Chapter2对偶问题DualProblem 1 线性规划的对偶模型DualModelofLP2 对偶性质Dualproperty3 对偶单纯形法DualSimplexMethod4 灵敏度分析SensitivityAnalysis 运筹学 OperationsResearch 在线性规划问题中 存在一个有趣的问题 即每一个线性规划问题都伴随有另一个线性规划问题 称它为对偶线性规划问题 例2 1 某企业用四种资源生产三种产品 工艺系数 资源限量及价值系数如下表 建立总收益最大的数学模型 解 设x1 x2 x3分别为产品A B C的产量 则线性规划数学模型为 现在从另一个角度来考虑企业的决策问题 假如企业自己不生产产品 而将现有的资源转让或出租给其它企业 那么资源的转让价格是多少才合理 价格太高对方不愿意接受 价格太低本单位收益又太少 合理的价格应是对方用最少的资金购买本企业的全部资源 而本企业所获得的利润不应低于自己用于生产时所获得的利润 这一决策问题可用下列线性规划数学模型来表示 设y1 y2 y3及y4分别表示四种资源的单位增殖价格 售价 成本 增殖 总增殖最低可用 minw 500y1 450y2 300y3 550y4 表示 企业生产一件产品A用了四种资源的数量分别是9 5 8和7个单位 利润是100 企业出售这些数量的资源所得的利润不能少于100 即 同理 对产品B和C有 价格不可能小于零 即有yi 0 i 1 4 从而企业的资源价格模型为 这是一个线性规划数学模型 称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题 生产计划的线性规划问题称为原始线性规划问题或原问题 例2 2 某人根据医嘱 每天需补充A B C三种营养 A不少于80单位 B不少于150单位 C不少于180单位 此人准备每天从六种食物中摄取这三种营养成分 已知六种食物每百克的营养成分含量及食物价格如下表 试建立此人在满足健康需要的基础上花费最少的数学模型 含量食物 解 设xj为每天第j种食物的用量 数学模型为 现有一制药厂要生产一种包含A B C三种营养成分的合成药 如何制定价格 使得此药既要畅销又要产值最大 设yi i 1 2 3 为第i种营养成分的单价 则 影子价格 Shadowprice 上面两个线性规划有着重要的经济含义 原始线性规划问题考虑的是充分利用现有资源 以产品的数量和单位产品的收益来决定企业的总收益 没有考虑到资源的价格 但实际在构成产品的收益中 不同的资源对收益的贡献也不同 它是企业生产过程中一种隐含的潜在价值 经济学中称为影子价格 即对偶问题中的决策变量yi的值 由后面的对偶性质可知 原问题和对偶问题的最优值相等 故有 即yi是第i种资源的变化率 说明当其它资源供应量bk k i 不变时 bi增加一个单位时目标值Z增加yi个单位 例如 第一种资源的影子价格为y1 2 第二种资源的影子价格为y2 2 即当第一种资源增加一个单位时 Z增加2个单位 当第二种资源增加一个单位时 Z增加2个单位 企业可利用影子价格调节生产规模 例如 目标函数Z表示利润 或产值 当第i种资源的影子价格大于零 或高于市场价格 时 表示有利可图 企业应购进该资源扩大生产规模 当影子价格等于零 或低于市场价格 企业不能增加收益 这时应将资源卖掉或出让 缩小生产规模 应当注意 是在最优基B不变的条件下有上述经济含义 当某种资源增加或减少后 最优基B可能发生了变化 这时yi的值也随之变化 在例2 1中 原问题的最优解X 24 24 0 46 96 对偶问题的最优解Y 10 6 0 91 0 0 最优值z w 5712 12 分析 1 y1 10 6说明在现有的资源限量的条件下 增加一个单位第一种资源可以给企业带来10 6元的利润 如果要出售该资源 其价格至少在成本价上加10 6元 2 y3 0说明增加第三种资源不会增加利润 因为第三种资源还有没有用完 问题 1 第三 四种资源的售价是多少 是否不值钱 2 如果要增加利润 企业应增加哪几种资源 各增加多少后再进行调整 上面两种形式的线性规划称为对称形式 原问题和对偶问题是互为对偶的两个线性规划问题 已知一个问题就可写出另一个问题 对称形式的定义是 目标函数求极大值时 所有约束条件为 号 变量非负 目标函数求极小值时 所有约束条件为 号 变量非负 对称形式的线性规划的对偶问题亦是对称形式 以上是依据经济问题推导出对偶问题 还可以用代数方法推导出对偶问题 例2 3 写出下列线性规划的对偶问题 解 这是一个对称形式的线性规划 设Y y1 y2 则有 从而对偶问题为 对偶变量yi也可写成xi的形式 例2 4 写出下列线性规划的对偶问题 解 这是一个对称形式的线性规划 它的对偶问题求最小值 有三个变量且非负 有两个 约束 即 若给出的线性规划不是对称形式 可以先化成对称形式再写对偶问题 也可直接按表2 1中的对应关系写出非对称形式的对偶问题 将上述原问题与对偶问题的对应关系列于表2 1 例如 原问题是求最小值 按表2 1有下列关系 1 第i个约束是 约束时 第i个对偶变量yj 0 2 第i个约束是 约束时 第i个对偶变量yi无约束 3 当xj 0时 第j个对偶约束为 约束 当xj无约束时 第j个对偶约束为 约束 表2 1 例2 5 写出下列线性规划的对偶问题 解 目标函数求最小值 应将表2 1的右边看作原问题 左边是对偶问题 原问题有3个约束4个变量 则对偶问题有3个变量4个约束 对照表2 1的对应关系 对偶问题为 本节以实例引出对偶