《运筹学对偶问题学习资料》由会员分享，可在线阅读，更多相关《运筹学对偶问题学习资料（62页珍藏版）》请在金锄头文库上搜索。
1、第四章对偶问题 对偶问题的一般形式对偶问题的经济意义对偶性质对偶单纯形法对偶单纯形法的解题原理 一 对偶问题的一般形式 若设一线性规划问题如下 A 如果采用向量 矩阵来表示 A B 其中 可以将以上关系列成以下对偶表 例 写出下列线性规划问题的对偶问题 解 可以将原问题的有关参数列成下表 对偶规划问题为 比较 以上我们介绍的对偶问题是严格定义的对偶问题 也成为对称对偶问题 它满足两个条件 两个条件 1 所有变量非负 即X 0 Y 02 约束条件均为同向不等式 若原问题约束条件均为 则它的对偶问题的约束条件都是 当原问题的约束条件的符号不完全相同时 也存在对偶问题 这种对偶问题称为非对称对偶问题
2、 例 分析 为求对偶问题 可先做过渡 将问题对称化 对称化 则 原问题变为 A A 则 A 的对偶问题如下 B A 对比结果 以上对偶问题 B 并非原问题 A 的对偶问题 它是线性规划问题 A 的对偶问题 A B 调整 对照问题B 目标函数系数的符号与原问题A中约束条件右端常数项的符号 可做以下调整 令y1 y1 y2 y2 y3 y4 y3 令y1 y1 y2 y2 y3 y4 y3 则得到以下对偶问题 B B 合并 B 比较 对于任何一个线性规划问题 我们都可以求出它的对偶问题 A B 原问题与对偶问题的相应关系 例 写出下列问题的对偶形式 解 例 写出下列问题的对偶问题 解 二 对偶问题
3、的经济意义 若原规划问题是 在一定条件下 使工作或成果 产品产量 利润等 尽可能的大 那么它的对偶问题就是 在另外一些条件下 使工作的消耗 浪费 成本等 尽可能的小 实际上是一个问题的两个方面 例 某产品计划问题的线性规划数学模型为 假设生产部门根据市场变化 决定停止生产甲 乙产品 而将原有的原料 设备专用于接受外来订货以生产市场急需的紧俏商品 则需要考虑决策的问题就是 在什么样的价格条件下 才能接受外来订货 问题的实质就是如何确定原料 设备的收费标准 分析 若设y1为单位原材料的价格 y2为设备单位台时价格 由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位 现在不
4、生产甲产品 转而接受外来订货加工 则收取的费用不能低于2个单位 否则自己生产甲产品更有利 因此 可以得到下面的条件 分析 同理 将生产乙产品的原料和设备工时用于接受外来加工订货 收取的费用不能低于乙产品的单位利润1个单位 分析 另外 为了争取外来加工订货 在满足上述要求的基础上 收费标准应尽可能低从而具有竞争力 因此总的收费w 15y1 10y2应极小化 这样 就得到一个目标函数 这样 就得到另一个线性规划模型 比较 生产问题 要利用资源 资源利用问题 会影响生产 第二节对偶理论 定理1 对称性定理 对偶问题 B 的对偶规划为线性规划 A 对称性定理是很重要的 它表明原规划问题 A 和对偶规划
5、问题 B 是互为对偶的 也就是说 如果 B 是 A 的对偶 那么 A 也是 B 的对偶 这就为以后的讨论带来方便 不难理解 如果当A具有某种性质时可以推出B的某些性质 于是可以无需另加证明地得到 当B具有某种性质时 问题A也具有那些性质 定理2 弱对偶定理 当原问题A是求最大值max 而对偶问题是求最小值时 如果X0是原问题的任意可行解 Y0是对偶问题的任意可行解 则有以下关系式成立 定理3 最优性定理 设和分别是问题A和B的可行解 若相应于和 A和B的目标函数值相等 即 则和分别是A和B的最优解 定理4 无界性定理 如果原问题A的目标函数值无界 则对偶问题B无可行解 如果对偶问题B的目标函数
6、值无界 则原问题A无可行解 以上三个定理可以这样记忆 原问题A和对偶问题B如果有可行解 则它们的可行解区域只可能相接 不可能相交 两个区域的交界线即是它们的最优解 如果原问题A的目标函数无界 意味着可行解区域无界 向外扩张 挤占了对偶问题B的可行解区域 则对偶问题无可行解 反之同理可说明 对偶问题 B minW 原问题 A maxZ y0b cx0 定理5 强对偶定理 若线性规划A存在最优解 则对偶规划B也存在最优解 并且它们的最优值相等 相反地 若规划B存在最优解 则规划A也存在最优解 并且它们的最优值相等 定理6 存在性定理 若线性规划A和B都存在可行解 则A和B都存在最优解 第三节对偶单
7、纯形法 条件 b列中至少有一个bi 0 原问题A的检验数满足符号条件 例 解 minmax 解 引入松弛变量 化为标准形式 观察A矩阵 解 以上标准形式中没有完全单位向量组 我们将约束条件进行变换 两边同乘 1 A矩阵中存在完全单位向量组 但bi 0 考虑求解 用单纯形法求解 步骤1 判断对偶单纯形法的条件是否满足 步骤2 在对偶单纯形表中 检验数是b列 当b 0时 得到最优解 否则 进行换基迭代 步骤3 换基迭代 1 找主元行 找到b列中绝对值最大者所在行为主元行 记为Pi 主元行对应的变量Xi 为调出变量 2 计算 j 找出主元行Pj 中所有负分量 计算注 若主元行中没有负分量 则问题无解
8、 3 找主元列 j中绝对值最小者所在的列为主元列 记为Pj 主元列所对应的变量xj 为调入变量 4 找主元素 主元行与主元列相交处的元素即主元素 记为Pi j 5 迭代 用高斯消去法 使原主元列中除了原主元素为1外 其余元素均为0 计算结果 找主元行 确定调出变量 计算zj cj 计算 j 确定调入变量 继续换基迭代 继续换基迭代 继续换基迭代 得到最优解 计算到第三段时 b 0且Cj Zj 0 得到原问题的最优解 五 对偶单纯形法的求解思路 一般单纯形法的思路 在使用表格单纯形法求解线性规划标准型的最优解时 是从一个初始基本可行解 可行域的一个顶点 开始 按照一定的规则进行迭代 求出第二个基
9、本可行解 另一个可行域的顶点 同时 逐步使检验数都变成正值 目标函数的当前值则逐步变优 直至所有检验数全部变成非负值 对应的基本可行解就成为最优解 由于迭代过程中出现的基本可行解既是满足约束条件的基本解 又是保持取非负值的可行解 即使解答列中基变量的取值 b列 始终保持非负 通过迭代逐步消除检验数行中的不满足符号条件的检验数 检验数也可以用向量形式写出 这里只写出非基变量的检验数向量 从可以很容易得推出 这说明原问题的最优基正是对偶问题的可行基 换言之 当原问题的基B即是原问题的可行基又是对偶问题的可行基时 B就是最优基 因此 单纯性法求解过程正是在保持原始可行 解答列基变量取值均非负 的条件下 通过迭代逐步实现对偶可行性 在对偶关系中 由于价值系数C和约束条件右端常数系数b互换位置 因此可以设想 能否在保持检验数Cj Zj非正的条件下 逐步消除基本解中的负分量 使之成为可行解 这样 该基本解就是基本最优解 对偶单纯形法正是基于这种思想而产生的 其基本思想就是在保持对偶可行性的条件下 通过逐步迭代实现原始可行性 所以 对偶单纯形法的使用条件是 b列中至少有一个bi 0 原问题A的检验数Cj Zj 0
