3对偶问题.pptVIP

对偶问题 1 对偶规划 对偶问题的提出 例2 原问题（P） 资源分配问题：3种有限的资源生产2种产品，决策变量为2种产品的产量，目标函数决策变量系数为2种产品获得的单位利润，目标为利润最大化。 对偶问题（D） 对偶问题实际意义 假定管理决策者从另一个角度来讨论这个问题，不考虑自己生产甲、乙两种产品去盈利，而是将现有资源标价出售，试问：决策者应该怎样给资源定一个合理的价格？ 设 分别表示三种资源的单位售价 决策者应该考虑卖掉资源的收入不能低于用资源安排生产的获利 表示将用于生产单位第一种产品的资源卖出去后，所获利不能少于其用于生产的获利（第一种产品的单位利润）。 一般化 表示用于生产单位第j种产品的资源卖出去后，所获利不能少于其用于生产的获利（第j 种产品的单位利润）。 矩阵形式 原问题LP 对偶问题DP 原问题 对偶问题 决策变量个数为原问题方程个数 目标函数max min 约束方程组右端常数为原问题目标函数中决策变量的系数：C bT 约束方程组系数为原问题约束方程系数矩阵的转置：A AT 约束方程组符号 目标函数中决策变量的系数为原问题约束方程组右端常数：b CT 练习1 : 写出对偶问题 练习1答案 对偶关系对应表 LP DP 目标 max min 变量 n个 约束 n个 ≥ 0 ≥ ≤ ≤ 无约束 = 约束 m个 变量 m个 ≥ ≤ 0 ≤ ≥ 0 = 无约束 例2 例2答案 练习2 练习2答案 2 对偶理论 定理1 对偶问题的对偶问题是原问题。 定理2 （弱对偶性） 设X，Y分别是（P）、（D）的任一可行解，则 引申：若（P）有可行解，但无最优解，则对偶问题（D）无可行解。 有用的结论 设X，W分别是原始及其对偶问题的可行解，则X，W分别是原始和对偶问题最优解的充分必要条件是 若P有最优解，则D也有最优解，且其最优值相等。D的最优解是P最终单纯形表中松弛变量对应的检验数的相反数CBB-1。 例6 求解下列线性规划问题 求解该问题： 标准化后还需添加人工变量，用两阶段法来求解，麻烦！ 其对偶问题DP： 求解对偶问题 加入3个松弛变量 以 为初始基可行 解求解。 最终单纯形表： 结论 例7（互补松弛性） LP如下 解 写出其对偶问题为 解 根据互补松弛性 得 将 带入上式得 对应的 请同学们根据此定理求解一题 3 对偶问题的解 4 影子价格 三种情况 当市场价格小于影子价格时，购入原料。 例8 求解LP，最终单纯形表如下 影子价格为： 实际上 影子价格为最终单纯形表松弛变量的检验数的相反数，也是原问题的对偶问题的解。 图解： 5对偶单纯形法 基本思想 原始单纯形法是从满足可行性条件的基（可行基）出发直到满足最优性条件，从而找到最优解。 对偶单纯形法是从满足最优性条件的基（正则基）出发直到满足可行性条件，从而找到最优解。 对偶单纯形法的步骤 （1）可行性标准。所有 ,停止，已经得到最优解，否则转步骤（2）。 （2）选出基变量， 确定 为出基变量，转步骤（3）。 （3）选进基变量。为保证迭代后的解仍是正则解，即所有检验数非正，类似于单纯形法的最小比值法则，计算 对偶单纯形法例 例： 标准化 列初始表如下： 优点 （1）初始解可以是非可行解，只要检验数都为负数，就可进行基变换，无须加入人工变量； （2）当变量多于约束条件，可以减少计算工作量。 （3）在灵敏度分析中也会有所应用。 DP 实际意义 6 1 -5 2