第四章 对偶单纯形法和对偶问题ppt课件.ppt

第四章对偶问题及对偶单纯形法 4 1对偶问题的提出 一 问题的提出 例1现有工厂生产A B C三种产品 单位产品所需要消耗的工时 材料及拥有量如下表 已知每单位A B C产品的利润分别为2 3 3 如何分配资源可以使得利润最大 建立模型如下 假设有客户提出要求 购买工厂所拥有的工时和材料 为客户加工别的产品 由客户支付工时费和材料费 那么工厂给每单位工时和材料制订的最低价格应是多少 才值得出卖工时和材料 同样是这个问题 现在我们来换一个角度思考 在考虑这个问题时我们应做到 1 价格应该尽量低 这样 才能有竞争力 2 出卖资源获利应不少于生产产品的获利 3 价格应该是非负的 目标 约束条件 非负约束 现在我们用数学语言描述 设y1和y2分别表示单位工时和材料的出售价格 总价格最小minW 3y1 9y2保证获利大于A产品利润y1 y2 2保证获利大于B产品利润y1 4y2 3保证获利大于C产品利润y1 7y2 3售价非负y1 0y2 0 二 对偶问题概念 任何一个线性规划问题都有一个与之相对应的线性规划问题 如果前者称为原始问题 后者就称为 对偶 问题 对偶问题是对原问题从另一角度进行的描述 其最优解与原问题的最优解有着密切的联系 在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解 反之亦然 对偶理论就是研究线性规划及其对偶问题的理论 是线性规划理论的重要内容之一 第四章对偶问题及对偶单纯形法 4 2建立对偶问题的规则 一 建立对偶问题的规则 可以用如下形式表示原问题与对偶问题之间的关系 原问题maxz CXAX bX 0 对偶问题minw bTYATY CTY 0 其中Y y1 y2 ym 二 对偶问题的特点 1 目标函数在一个问题中是求最大值在另一问题中则为求最小值 2 一个问题中目标函数的系数是另一个问题中约束条件的右端项 3 一个问题中的约束条件个数等于另一个问题中的变量数 4 原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵 对偶问题对应表 三 例题 原问题 对偶问题 maxZ 70X1 120X2min 360y1 200y2 300y39X1 4X2 3609y1 4y2 3y3 704X1 5X2 2004y1 5y2 10y3 1203X1 10X2 300y1 0 y2 0 y3 0X1 0X2 0 习题 课本P51例2 练习写出如下LP问题的对偶问题 第四章对偶问题及对偶单纯形法 4 3对偶问题的基本性质 选学 一 对称性 定理1 对偶问题的对偶就是原始问题 定理2 可行解的目标函数值之间的关系 设X Y分别是原始问题和对偶问题的可行解 则CX YTb 二 弱对偶性 1 如果原问题 对偶问题 具有无界解 则其对偶问题 原问题 无可行解 2 若原问题可行 而对偶问题不可行 则原问题的目标函数值无界3 若对偶问题可行 而原问题不可行 则对偶问题的目标函数值无界 推论 例如 试用对偶理论证明原问题无界 解 0 0 0 是原问题的一个可行解 而对偶的第一个约束条件不能成立 因为y1 y2 0 因此 原问题无界 习题P603 定理3 三 可行解是最优解的性质 四 对偶定理 定理4如果原问题有最优解 则其对偶问题也一定有最优解 且两者的目标函数值相等 定理5若X为原问题的满足最优检验的基本解 则Y CBb 1为对偶问题的可行解 原问题在得到基本可行解的同时 其检验数的相反数就构成对偶问题的一个基本解 且各自目标函数值恒相等 补充 对比原问题和对偶问题的最优单纯形表P54表4 2 4 3 原问题 对偶问题 第四章对偶问题及对偶单纯形法 4 4对偶单纯形法 当一个线性规划问题是求目标函数值最小 约束方程是 时 求解时用大M法或两阶段法比较麻烦 此时较有效的算法是将要介绍的对偶单纯形法对偶单纯形法并不是求解对偶问题解的方法 而是利用对偶理论求解原问题的解的方法 一 原理 第一步找出一个初始正则解B0 要求对应的单纯形表中的全部检验数 0 但右边项中允许有负数第二步若右边项中各数均非负 则B0已是最优基 即已求得最优解 计算终止 否则转为下一步第三步取右边项中取值最小 即负的最多 的数所对应的变量为换出变量 二 对偶单纯形法的计算步骤 第四步按公式其中 j cj zj计算最小比值 则该列所对应的变量即为换入变量第五步以换出变量的行和换入变量列交点处的元素为主元进行单纯形迭代 再转入第二步 用对偶单纯形法求解线性规划问题 minw 15y1 24y2 5y36y2 y3 25y1 2y2 y3 1yj 0 对一切j解 先将问题改写为maxw 15y1 24y2 5y3maxw 15y1 24y2 5y36y2 y3 y4 2 6y2 y3 y4 25y1 2y2 y3 y5 1 5y1 2y2 y3 y5 1yj 0 对一切jyj 0 对一切j 三 例题 第一步建立一个初始单纯形表 使表中检验行的值全部 0即对其对偶问题而言是一基本可行解 第二步检验当前可行解是否可行 若可行 已得最优解 否则转入下一步 检验数均为非正数 但右边项仍有负数 并非最优解 继续迭代 第三步选择b列中取值最小 即负的最多 的数所对应的变量为出基变量 第四步按公式计算最小比值 则该列所对应的变量即为入基变量 其中 j cj zj 第五步用换入变量替换对偶问题中的换出变量得到一个新的单纯形表 表中数字计算同用单纯形法时完全一样 新表中对偶问题仍保持基本可行解 第六步 重复第二 四步 一直到找出最优解为止 此时右边项全为非负值 达到最优 Y1 0 Y2 1 4 Y3 1 2 W最优为17 2 四 练习 课本60页2 第四章对偶问题及对偶单纯形法 4 5对偶问题的经济意义 影子价格 定义 约束条件方程右端的bi增加一单位时 最优目标函数z的变化量称为资源i的影子价格 影子价格越大 说明这种资源越是相对紧缺影子价格越小 说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余 这种资源的影子价格一定等于0 第四章对偶问题及对偶单纯形法 4 6对偶单纯形法的一个应用 增加约束条件 在求出线性规划问题的最优解后 又增加一个约束条件 此时可以利用对偶单纯形法求解 不必对原问题从头做起 其步骤如下 1 将最优解代入新的约束条件 若满足 则最优解不变2 若不满足 则当前最优解要发生变化 将新增约束条件加入松弛变量或剩余变量后加入到原来的最优单纯形表 令原来的基变量和新增加的变量组成新的基 进行初等变换将基变量对应的系数矩阵变为单位矩阵 3 利用对偶单纯形法继续迭代 一 原理及步骤 二 例题 转化为标准型 以达到最优 此时X1 0 X2 100 X3 0 X4 200 X5 100 X6 0 X7 0 Z 1300若此时增加约束条件X1 2X2 3X3 3X4 650 代入当前的最优解检验不符合条件 应继续迭代加入新条件 将原问题变为 利用单纯形法迭代 求得 转化为标准型 2x1 3x2 x3 2x4 x5 8005x1 4x2 3x3 4x4