运筹学第4章 单纯形法的对偶问题.ppt

1 第4章单纯形法的对偶问题 1线性规划的对偶问题 2对偶规划的基本性质 3对偶单纯形法 2 每一个线性规划问题 都存在每一个与它密切相关的线性规划的问题 我们称其为原问题 另一个为对偶问题 例题1某工厂在计划期内安排 两种产品 生产单位产品所需设备A B c台时如表所示该工厂每生产一单位产品可获利50元 每生产一单位产品 可获利100元 问工厂应分别生产多少产品和 产品 才能使工厂获利最多 解 设为产品的计划产量 为产品 的计划产量 则有目标函数 Maxz 50 100约束条件 1线性规划的对偶问题 3 现在我们从另一个角度来考虑这个问题 假如有另外一个工厂要求租用该厂的设备A B c 那么该厂的厂长应该如何来确定合理的租金呢 设分别为设备A B c的每台时的租金 为了叙述方便 这里把租金定义为扣除成本后的利润 作为出租者来说 生产单位产品所需各设备的台时各总租金不应低于原利润50元 即 否则就不出租还是用于生产产品以获利50元 同样生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元 即 否则这些设备台时就不出租 还是用于生产产品以获利100元 但对于租用者来说 他要求在满足上述要求的前提下 也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好 即min 这样我们得到了该问题的数学模型 目标函数 约束条件 这样从两个不同的角度来考虑同一个工厂的最大利润 最小租金 的问题 所建立起来的两个线性模型就是一对对偶问题 其中一个叫做原问题 而另外一个叫对偶问题 1线性规划的对偶问题 4 如果我们把求目标函数最大值的线性规划问题看成原问题 则把求目标函数最小值的线性规划问题看成对偶问题 下面来研究这两个问题在数学模型上的关系 1求目标函数最大值的线性规划问题中有n个变量m个约束条件 它的约束条件都是小于等于不等式 而其对偶则是求目标函数为最小值的线性规划问题 有m个变量n个约束条件 其约束条件都为大于等于不等式 2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项 并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项 3原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数 并且原问题的第i个约束条件的右边常数项就等于对偶问题的目标函数中的第i个变量的系数 4对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置 设A 则 1线性规划的对偶问题 5 如果我们用矩阵形式来表示 则有原问题 其中A是矩阵m n 该问题有m个约束条件n个变量 对偶问题 其中是A的转置 是b的转置 是c的转置 y 现在我们用单纯形法求对偶问题的解 1线性规划的对偶问题 6 加上剩余变量和人工变量 把此问题化成标准型如下 把上述数据填入单纯形表计算 1线性规划的对偶问题 7 1线性规划的对偶问题 8 由上表 最优解 50 f的最大值为 27500 即目标函数f的最小值为f 27500元 从上面可知租金 A设备为50元 B设备为0元 c设备为50元 这样把工厂的所有设备出租可共得租金27500元 对出租者来说这租金是出租者愿意出租设备的最小费用 因为这是目标函数的最小值 通过比较 我们发现 对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格 这在道理上也能讲得通 对于两个有对偶关系的线性规划的问题 我们只要求得了其中一个最优解 就可以从这个问题的对偶价格而求得其对偶问题的最优解 知道其中一个最优值也就找到了其对偶问题的最优值 因为这两个最优值相等 1线性规划的对偶问题 9 下面来阐述如何写出一个线性规划问题的对偶问题 为了便于阐述 我们不妨以下面的线性规划为例 写出它的对偶问题 s t 1线性规划的对偶问题 10 这是一个求最大值的线性规划问题 为了写出它的对偶问题 我们不妨把它的约束条件都变换成取小于等于号的不等式 显然第一个约束条件已符合要求 不要做任何变动 而第二个约束条件 我们只要两边都乘以 1 使不等号方向改变即可 得这样第二个约束条件也就符合要求 对于第三个约束条件 我们可以用小于等于和大于等于两个约束条件来替代它 即有显然 这两个约束条件与原来第三个约束条件是等价的 我们再把其中的两边都乘以 1 得 1线性规划的对偶问题 11 通过上面的一些变换 我们得到了一个和原线性规划等价的线性规划问题 s t 1线性规划的对偶问题 12 这个求最大值的线性规划问题的约束条件都取小于等于号 我们马上可以写出其对偶问题 s t 1线性规划的对偶问题 13 这里和一样都是不同的决策变量 为了表示这两个决策变量都来源于原问题的第三个约束条件 记为 因为在该对偶问题中和的系数只相差一个符号 我们可以把上面的对偶问题化为 s t 1线性规划的对偶问题 14 进一步 我们可以令 这时当时 当时 这也就是说 尽管但的取值可以为正 可以为0 可以为负 即没有非负限制 这样我们把原规划的对偶问题化为s t 没有非负限制 对照原线性规划问题 我们可以知道 当原线性规划问题的第i个约束条件取等号时 则其对偶问题的i个决策变量没有非负限制 如果当原线性规划问题中的第i个决策变量没有非负限制时 我们也可以用进行替换 这里 用类似的方法知道其对偶问题中第i个约束条件取等号 1线性规划的对偶问题 15 另外 用大于等于0的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法 原线性规划问题为 s t 1线性规划的对偶问题 16 首先在写对偶问题之前 我们先把第二个约束条件两边乘以 1得然后按照上面的规则 我们可以得到其对偶问题为s t 1线性规划的对偶问题 17 2对偶规划的基本性质 对偶规划的基本性质1 对称性 即对偶问题的对偶是原问题 2 弱对偶性 即对于原问题和对偶问题的可行解 都有 由弱对偶性 可得出以下推论 1 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界 反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界 2 如原问题有可行解且目标函数值无界 或具有无界解 则其对偶问题无可行解 反之对偶问题有可行解且目标函数值无界 则其原问题无可行解 注意 此性质的逆不成立 当对偶问题无可行解时 其原问题或具有无界解或无可行解 反之亦然 3 若原问题有可行解而其对偶问题无可行解 则原问题目标函数值无界 反之对偶问题有可行解而其原问题无可行解 则对偶问题的目标函数值无界 18 2对偶规划的基本性质 3 最优性 如果是原问题的可行解 是对偶问题的可行解 并且 则和分别为原问题和对偶问题的最优解 4 强对偶性 即若原问题及其对偶问题都有可行解 则两者都有最优解 且它们的最优解的目标函数都相等 5 互补松弛性 在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零 则该约束条件取严格等式 反之 如果约束条件取严格不等式 则其对应的对偶变量一定为零 也即若yi 0 则有若 则有yi 0 19 3对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法 对偶单纯形法是在保持原有问题的所有检验数都小于等于零的情况下 通过迭代使得所有约束条件的常数都大于等于零 最后求得最优解 简化计算是对偶单纯形法的优点 但是它在使用上有很大的局限 这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于等于零 但是在灵敏度分析中 有时需要对偶单纯形法 这样可以简化处理 下面以第二节例一为例 上节分析中已知当250 b 1 325时第一个约束条件的对偶