文档介绍：------------------------------------------------------------------------------------------------ ——————————————————————————————————————对偶线性规划一般来说, 对于一个线性规划问题, 一定存在与此互为对偶关系的另一个线性规划问题。 对偶问题的引出及定义 引例例 乐山厂计划出产甲、乙两种产品,该厂使用 d1、 d2和 d3 三种生产因素的数量限制、每产品所需各种因素及出厂后可获利润如下表 2-1 所示,求该厂所能得到的最大利润。 max 5Z=x1 +4x2 ?x1+3x2 ≤ 90?2x+x ≤ 80?12 (1) s?t?+ ≤ xx452?1 ??x 1、 x2≥0 解:设 x1 为甲产品的生产数量, x2 为乙产品的生产数量,据已知条件得出线形规划如果我们反面来考虑该问题: 最低应付出多少代价, 放能使乐山厂放弃生产 x1和 x2 的活动而出让 d1, d2和 d3 生产因素。分析: 要使乐山厂放弃生产 C和 x2 出让 d1, d2和 d3 生产因素、也就等于说要乐山厂放弃由生产 x1和 x2 所获得的最大利益,因此, 我们最少应付出相等或大于这个最大收益的数值,才能从乐山厂获得 d1, d2和 d3 生产因素。假设生产因素 d1, d2和 d3 的单位机会成本分别为 W1 , W2 和 W3 。那么,这三种因素的最低价值应该是 minG =90W1 +80W2 ------------------------------------------------------------------------------------------------ ——————————————————————————————————————+45W3 并且有: maxZ ≤ minG 另一方面,生产单位 x1或 x2 所需用的生产因素 d1, d2和d3 的机会价格不能低于 x1或 x2 的单位收益。否则的话, 乐山厂宁愿自己生产而不会出让生产因素,因此我们得到反面问题的约束: ?w1+2w2+w3 ≥ 5? s?t?3w1+w2+w3 ≥4 ?w 、w、w≥0 23?1 归纳起来,得到反面问题的线形规划: minG =90W1 +80W2 + 45W3 ?w1+2w2+w3 ≥ 5? s?t?3w1+w2+w3 ≥4(2) ?w 、w、 w≥0 23?1 我们称规划( 2 )是规划( 1 )的对偶规划。 定义称线形规划?maxZ=CX AX ≤b (L?P)??s?t?????X ≥0 与线形规划?minG=bTW? ------------------------------------------------------------------------------------------------ ——————————————————————————————————————(D?P)??ATw ≥ CT ?s?t?W ≥ 0?? 为互为对偶规划。 对偶问题的性质 对偶关系表利用以上两规划的形式我们可以得出一个对偶关系表,如表 2-2 所示。表 2-2 x1 x2… xm … xn (1) 从行看是原问题(Ⅰ), 从列看是对偶问题(Ⅱ), 两个问题的变量系数矩阵互为转置矩阵。(2 )原问题( Ⅰ)的常数项是对偶问题( Ⅱ)的目标系数,反之,原问题( Ⅰ)的目标系数是对偶问题( Ⅱ)的常数项。(3 )原问题( Ⅰ)有 n 个决策变量,对偶问题( Ⅱ)有 n 个约束方程:原问题有 m 个约束方程,对偶问题就有 m 个决策变量。(4) 原问题的约束是“≤”型, 对偶问题的约束是“≥”型。(5) 原问题的目标函数是求极大, 对偶问题的目标是求极小。例 在例 中引出的两规则: maxZ=5x1+4x2 minG=90w1+80w2+45w3 ?x1+3x2 ≤ 90 ?2x+x ≤ 80?w1+2w2+w3 ≥5 ??12 ------------------------------------------------------------------------------------------------ —————————————————————————————————————— s?t3w+w+w ≥ 4s?t??123 +≤ xx452?w,w,w ≥ 0?1 ?1 23??x1,x2 ≥0 的对偶关系表如表 2-3 。从以上对偶表的关系知, 只要我们得到定义中的原线性规划就可得到对偶规划, 这样不要再像例 1