对偶问题

某工厂用三台设备生产两种产品 已知的条件如表所示 试制订总利润最大的生产计划 引例1生产计划问题 换一角度 将设备卖出 售价定为多少适宜 原问题 对偶问题 两个互为对偶规划问题之间的关系 对称形式 1 目标函数的目标互为相反 max min 2 目标函数的系数是另一个约束条件右端的向量3 约束系数矩阵是另一个的约束系数矩阵的转置4 约束方程的个数与另一个的变量的个数相等 max限定向量b价值向量Cm个约束 n个变量约束条件 变量 原问题 对偶问题 min价值向量限定向量n个约束 m个变量变量 约束条件 对称式对偶 max限定向量b价值向量Cm个约束 n个变量约束条件 原问题 对偶问题 min价值向量限定向量n个约束 m个变量变量自由变量 非对称式对偶 目标函数max 原问题 对偶问题 对偶问题 原问题 目标函数min 目标函数中变量的系数 约束条件右端项 约束条件右端项 目标函数中变量的系数 例2 给出下列线性规划的对偶问题 minZ 2X1 8X2 4X3X1 3X2 3X3 30 X1 5X2 4X3 80st 4X1 2X2 4X3 0 X3无约束其对偶问题为 MAXw 30y1 80y2 50y3y1 y2 4y3 2st 3y1 5y2 2y3 0 y2无约束 y3 0 一 对称性定理对偶问题的对偶是原问题 2 3对偶问题基本性质 二 弱对偶定理 原问题 对偶问题 如果分别是 1 和 2 的可行解 则有 三 最优性定理 如果分别是 1 和 2 的可行解 且有 则分别是 1 和 2 的最优解 四 强对偶定理 原问题 对偶问题 五 无界性定理 对于一对对偶问题 其中一个有有限最优解 则另一个也有最优解 且两个目标函数值相等 对于一对对偶问题 若一个有无界解 则另一个无可行解 例3已知原问题 其对偶问题为 试估计它们的目标函数值的界 并验证弱对偶定理的正确性 且原问题的目标函数值 对偶问题的目标函数值 并且我们知对偶问题的目标函数值 原问题的目标函数值 六 互补松弛性定理 利用互补松弛定理 在已知一个问题的最优解的情况下 可以不要列单纯形表求出另一个的最优解 例4 已知线性规划问题 要求 1 写出对偶问题 2 已知原问题的最优解为x1 5 x2 0 x3 1 试根据对偶理论直接求出对偶问题最优解 解 1 对偶问题 2 由互补松弛定理 因原问题最优解中x1 5 0 必使对偶问题第一个约束条件为等式 于是有 例5 已知下列线性规划问题的对偶问题的最优解为 6 5 1 5 求该线性规划问题的最优解 其对偶问题为 原问题的松弛变量为 X5 X6 对偶问题的剩余变量为 Y3 Y4 Y5 Y6 将 6 5 1 5 代入1 和2 知 Y3 Y4 均不为0 于是由松弛互补定理知 X1 X2 0又由Y1 0 Y2 0和松弛互补定理知 X5 X6 0从而 原问题的约束变为 2X3 3X4 203X3 2X4 20解此方程得 X3 X4 4于是原问题的最优解为 0 0 4 4 七 单纯形表的双重含义例6 用单纯形法 解线性规划 LP1 maxZ 2X1 X25X2 0 X2 0对偶问题为 LP2 minW 15Y1 24Y2 5Y36Y2 Y3 2ST 5Y1 2Y2 Y3 1Y1 0 Y2 0 检验数全部 0 于是得到最优解为 X 7 2 3 2 15 2 0 0 最优值为 Z 17 2 把松弛变量的检验数的相反数 0 1 4 1 2 带入对偶问题中 看有什么规律 1 松弛变量与对偶变量的乘积有什么关系 松弛变量与对偶变量的乘积 02 对偶问题的最优解与什么对应 对偶问题的最优解是原问题松弛变量检验数的相反数 结论 将原始单纯形表中松弛变量的检验数反号恰好得对应对偶问题的一个解 事实上 我们把原始问题写成 1 其对偶问题写成 其中 其中 所对应的检验数分别为 令 这时两组检验数分别为 和 再根据问题 2 这两组检验数可分别记为 上述对应关系如表 2 在获得最优解之前 及的各分量中至少有一大于零 即 即 重要结论 1 原始问题的单纯形表中 原始问题的松弛变量的检验数对应于对偶问题的决策变量 而原始问题的决策变量的检验数对应于对偶问题的松弛变量 只是符号相反 此时对偶问题也同时获得最优解 和 当原始问题获得最优解时 表明 2 4影子价格 一 影子价格的含义根据资源在生产中作出的贡献而作的估价 是对第i种资源实现最大利润的一种估计 是对偶问题的最优解 二 影子价格的特点 1 区别于市场价格 市场价格相对稳定 而影子价格不稳定 依赖于资源的利用 2 影子价格是一种边际价格 3 影子价格是一种机会成本 4 互补松弛定理指出 当某种资源未被充分利用 则该种资源的影子价格为0 而当资源的影子价格不为0时 表明该种资源已耗尽 5 检验数的经济学含义 第j种产品的单位产值 是生产该产品所耗用的各种资源的影子价格 即隐含成本 对偶问题的经济意义 1 影子价格 b代表资源的拥有量 Y代表在资源最优利用条件下对单位资源的估价 但不是市场价 而是对资源在生产中做出的贡献的估价 即企业的生产效率 一般称为影子价格 市场价格是已知的 而影子价格则与资源的利用情况有关 利用的高 影子价格就高 反之亦然 2 影子价格是一种边际价格 或者边际贡献 即每增加一个单位的资源时在最优利用的条件下 目标函数的增量 在最优条件下 Z Y b 目标函数是资源量的函数 3 影子价格又是一种机会成本 减少一件产品 可以节省的资源 Z cx y b 在Y确定后 当X变化时 b也跟着变化 4 当市场价大于影子价格 卖出资源 当市场价小于影子价格 买入资源 组织生产 5 如果Y中有分量 0 即松弛变量 0 则表示对应的资源没有得到充分利用 所有分量都 0 即松弛变量 0 表示资源已消耗尽 6 利用影子价格可以有效控制和使用资源 例如对紧缺资源的控制 择优分配 作为同类企业经济效益的评估标准 通过帮助企业提高工艺和管理水平 降低资源的耗费来提高资源的影子价格 2 5对偶单纯形法 小结 在单纯形表格中1 得到原问题的基本可行解的同时 其检验数的相反数就构成了对偶问题的一个基本解 2 原对松弛变量 决策变量决策变量 剩余变量基变量 非基变量非基变量 基变量 是 否 换基 再确定入基变量 先确定出基变量 bl min bi bi 0 则对应xl出基 则对应xk入基 对偶单纯形法步骤 00 15 24 500 基 15 24 500 0 5 6 2 1 1 10 01 2 1 240 150 1 40 24 5 15 200 7 2 3 2 Min问题 Max问题 单纯形法 1 保持原问题的可行性 即 2 最优性 即使对偶问题达到可行 3 同时得到原问题与对偶问题最优解 对偶单纯形法 1 保持对偶问题的可行性 即 2 最优性 即使原问题达到可行 3 同时得到原问题与对偶问题最优解 从以上求解过程可以看到对偶单纯形法有以下优点 1 初始解可以是非可行解 当检验数都为负数时就可以进行基的变换 这时不需要加入人工变量 因此可以简化计算 2 当变量多于约束条件 对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量 因此对变量较少 而约束条件很多的线性规划问题 可先将它变换成对偶问题 然后用对偶单纯形法求解 3 在灵敏度分析及求解整数规划的割平面法中 有时需要用对偶单纯形法 这样可使问题的处理简化 对偶单纯形法的局限性主要是 对大多数线性规划问题 很难找到一个初始可行基 因而这种方法在求解线性规划问题时很少单独应用 引例 某厂生产A B两种产品 其所需劳动力 材料 设备等有关数据见表 要求确定获利最大的生产计划 建立数学模型 设x1 x2为A B产品的产量 则 1 A B两种产品利润改变 2 增加了材料 3 开发新项目 增加一新产品C 4 技术革新 改变B产品的工艺 5 对两种产品增加一道新工序 是否影响原最优解呢 如发生变化 2 6灵敏度分析 灵敏度分析 指对系统或事物因周围条件变化显示出来的敏感程度分析 所研究的问题 参数A b C一个或几个发生变化 最优解如何 以及在多大范围内变化 最优解不变 1 目标函数系数变为 2 第二个约束条件右端项变为32 3 增加一个新的变量 4 5 增加一个约束条件 作如下灵敏度分析 基 21000 010 001 100 5 41 4 1 4 15 2 1 23 2 15 27 23 2 021 000 1 4 1 2 最终表 1 52 1 52 0001 8 9 4 01 52 00 1 100 3 2 方法 1 将Cj的变化体现在最终表上 2 用变化后的数据重新计算检验数 3 若所有检验数 0 原最优解不变 否则用单纯形法继续迭代 基 21000 010 001 100 5 41 4 1 4 15 2 1 23 2 15 27 23 2 021 000 1 4 1 2 最终表 35 211 2 1 2 020 0 100 2 方法 1 找出原问题的最优基的逆B 1 2 求出X B B 1b 3 若X B 0 原最优基不变 最优解变为X B 否则将变化后的X B反映在最终表的b列 用对偶单纯形法继续迭代 基 21000 010 001 100 5 41 4 1 4 15 2 1 23 2 15 27 23 2 021 000 1 4 1 2 最终表 023 0 1 20 1 8 5 40 3 702 1 方法 1 找出原问题的最优基的逆B 1 2 求出 计算检验数3 若 原最优解不变 否则将用单纯形法继续迭代 基 21000 010 001 100 5 41 4 1 4 15 2 1 23 2 15 27 23 2 021 000 1 4 1 2 最终表 11 21 21 2 023 0001 2 5 3 3 100 900 1 424 00 M 4M 1 224M 50 基 21000 010 001 100 5 41 4 1 4 15 2 1 23 2 15 27 23 2 021 000 1 4 1 2 最终表 0 x61232000 0 x600010 000 1 4 1 20 0 x6 3 2000 1 4 3 21 灵敏度分析的步骤 1 将参数的改变计算反映到最终单纯形表中 2 检查原问题是否可行 即bi 0 3 检查对偶问题是否可行 即 j 0 4 按表所列决定继续迭代的步骤 原问题对偶问题步骤可行解可行解仍为问题最优解可行解非可行解用单纯形法迭代非可行解可行解用对偶单纯形法迭代非可行解非可行解引入人工变量构造可行基 1 目标函数系数变为 2 第一个约束条件右端项变为3 3 增加一个约束条件 引例 某厂生产A B C三种产品 其所需劳动力 材料等有关数据见表 要求 1 确定获利最大的生产计划 2 产品A的利润在什么范围内变