第二章new 对偶理论与灵敏度分析

Chapter 2 对偶理论与灵敏度分析 上海工程技术大学 管理学院 Chapter 2 灵敏度分析 对偶问题提出 问题一：某公司在计划期内要安排生产 I、 II两种产 品，已知生产单位产品所需的设备台时及 A B两 种原材料的消耗如表所示，该工厂每生产一件产 品 I可获利 2元，每生产一件产品 II可获利 3元，问 应该如何安排计划使该工厂获利最多？ 如何安排方案？ 举例 有哪些 方面可以考虑呢？ Chapter 2 灵敏度分析 先根据图表来列出模型 Max Z= 2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1, X2 0 举例 我们从另一个角度来讨论这个问题 .假如该工 厂的决策者决定不生产产品 I II，而将其所 有资源出租或外售 .这时工厂的决策者就要 考虑给每种资源如何定价的问题 .设用 Y1, Y2, Y3分别表示出租单位设备台时的租金 和出让单位原材料 A,B的附加额 . 从工厂决策者的角度来看 f当然是越大越好 , 但从接受者眼光来说 f是越少越好 ,所以工 厂决策者只可以在满足 所有产品的利 润条件下 ,使其总收入尽可能的小 .因此可 以列出如下线性规划问题 min f= 8Y1+16Y2+12Y3 Y1+4Y2 2 2Y1+4Y3 3 Yi 0, i = 1,2,3 Chapter 2 灵敏度分析 v 各模型中有关数据的 “ 位置 ” 示意图如下。 v由上面的例子我们可以知道原问题与 对偶问题的关系 1线性规划问题是对称形式 Max z = CX Min f = Yb s.t. Ax b s.t. YA c x 0 y 0 “Max - ” “Min- ” Chapter 2 灵敏度分析 v如上面例题所示一对对称形式的对偶规划 之间具有下面的对应关系 (1)若一个模型为目标求 “极大 ”，约束为 “小于 等于 ”的不等式，则它的对偶模型为目标求 “极小 ”，约束是 “大于等于 ”的不等式。即 “max， ”和 “min， ”相对应。 (2)从约束系数矩阵看：一个模型中为 ，则 另一个模型中为 AT。一个模型是 m个约束 ， n个变量，则它的对偶模型为 n个约束， m个变量。 (3)从数据 b、 C的位置看：在两个规划模型中 ， b和 C的位置对换。 (4)两个规划模型中的变量皆非负。 Chapter 2 灵敏度分析 v然而在一般线性规划问题中遇到 非对称形 式 时我们的处理如下： 非对称形式的对偶规划 一般称不具有 对称形式的一对线性规划为非对称形式的 对偶规划。 v对于非对称形式的规划，可以按照下面的 对应关系直接给出其对偶规划。 （ 1）将模型统一为 “max， ”或 “min， ” 的 形式，对于其中的等式约束按下面（ 2）、 （ 3）中的方法处理； （ 2）若原规划的某个约束条件为等式约束， 则在对偶规划中与此约束对应的那个变量 取值没有非负限制； （ 3）若原规划的某个变量的值没有非负限制 ，则在对偶问题中与此变量对应的那个约 束为等式。 Chapter 2 灵敏度分析 v非对称型对偶问题 Chapter 2 灵敏度分析 举例 Chapter 2 灵敏度分析 原问题（或对偶问题） 对偶问题（或原问题） 目标函数 max 目标函数 min 约 束 条 件 m个 m个 变 量 0 0 = 无约束 变 量 n个 n个 约 束 条 件 0 0 无约束 = 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 Chapter 2 灵敏度分析 小练习 写出下列问题的对偶问题 Chapter 2 灵敏度分析 对偶问题的基本性质 性质 1:对称性 规范原始，对偶问题的对偶是原问题。 Max z = CX Min f = Yb s.t. AX b s.t. YA C X 0 Y 0 “Max - ” “Min- ” Chapter 2 灵敏度分析 性质 2:弱对偶原理（弱对偶性）：设 和 分别是 问题（ P）和（ D）的可行解，则必有 性质 3:无界性 若原问题（对偶问题）的解为无界解，则其 对偶问题（原问题）无可行解。（无界性 ） 性质 4:可行解是最优解的性质： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b， 则 X*. Y*分别是问题 P和 D 的最优解。 Chapter 2 灵敏度分析 性质 5:对偶定理 若原问题有最优解，那么对偶问题也有最优 解，而且二者最优值相等。（强对偶性） 性质 6:互补松弛定理 设 X*和 Y*分别是问题 P 和 D 的可行解，则 它们分别是最优解的充要条件是 同时成立 Chapter 2 灵敏度分析 例题判断下例说法是否正确，为什么？ A 如果线性规划的原问题存在可行解，则其对 偶 问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问 题也一定无可行解。 C 在互为对偶的一对原问题和对偶问题中，不 管原问题是求极大或者极小，原问题可行解的目 标函数值都一定不超过其对偶问题可行解的目标 函数值。 Chapter 2 灵敏度分析 v解： A不对。因为原问题为无界解时（它当然有可行解 ），其对偶问题无可行解。 B此句为 A的逆否命题，所以也不对。 C不对。因为哪个问题是原问题，哪个问题是对偶 问题是相对而言的。 Chapter 2 灵敏度分析 例题 :已知原问题的最优解为 X* =（ 0,0,4） ， Z=12,试求对偶问题的最优解。 Chapter 2 灵敏度分析 解 : 将 X* =（ 0 , 0 , 4）代入原问题中，有下式 ： Chapter 2 灵敏度分析 所以，根据互补松弛条件，必有 y*1= y*2=0，代 入对偶问题 （ 3）式， y3 =3。因此，对偶问 题的最优解为 Y*=（ 0 . 0 . 3）， W=12。 第二节 影子价格 Chapter 2 灵敏度分析 第三节 对偶单纯形法 v对偶单纯形法是求解线性规划的另一的基本方法 。它是根据对偶原理和单纯形法的原理而设计出 来的，因此称为对偶单纯形法。 对偶单纯形法并 不是求解对偶问题解的方法，而是利用对偶理论 求解原问题的解的方法。 由单纯形方法，我们可以得到， LP问题的最优解应 该是 可行的； 最优的；由对偶性可知， LP 问题的最优性相当于 DLP的可行性， LP问题的可 行性相当于 DLP的最优性 . (3) 对偶单纯形法 因此单纯形方法可以解释为它是在保持一个原 始问题可行解的前提下，向对偶可行解的方向 迭代 . 原始算法 我们可以从一个对偶可行解开始，保持对偶问 题的可行性，向原始可行解的方向迭代 对偶单纯形法 对偶单纯形法的基本思路对偶单纯形法的基本思路 单纯形法的基本思路：单纯形法的基本思路： 原问题基可行解 最优解判断 对偶问题的可行解对偶问题最优解判断 对偶单纯形法对偶单纯形法 基本思路基本思路 也就是说，求解原问题（ P）时，可以从（ P）的一 个基本解（非基可行解）开始，逐步迭代，使目标函 数值（ Z=Y b= CB B-1b =CX）减少，当迭代到 XB=B-1b0时，即找到了（ P）的最优解，这就是对偶 单纯形法。 同原始单纯形求法一样，求解对偶问题（ D），也可 以从（ D）的一个基本可行解开始，从一个基本可行解 （迭代）到另一个基本可行解，使目标函数值减少。 4 对偶单纯形法 对偶单纯形法的基本思路是： 在迭代过程中，始终保持对偶问题解的可行性， 而原问题的解由不可行逐渐向可行性转化，一旦原 问题的解也满足了可行性条件 ,也就达到了最优解。 也即在保持正则解的正则性不变条件下，在迭代 过程中，使原问题解的不可行性逐步消失，一旦迭 代到可行解时，即达到了最优解。 v这样的优点在于 ， v一是当问题的模型中存在 “=”的约束条件时，不 需要引入人工变量，只要在约束条件方程的两边 乘以 “-1”后加入松弛变量，再按单纯形法求解。 v二是当约束条件方程个数 m大于变量个数 n的时候 ，将原问题变换成对偶问题求解，计算量一般会 小些。 Chapter 2 灵敏度分析 对偶单纯形法求解线性规划问题过程： 1.建立初始对偶单纯形表 ,对应一个基本 解 ,所有检验数均非正 ,转 2； 2.若 b0, 则得到最优解 ,停止 ; 3.若有 bi0 brMin- bi/airair0 csMin j/asjas j0 Chapter 2 灵敏度分析 例题 : Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0 下表为最优单纯形表 ,考虑基变量系数 c2发生变化 Chapter 2 灵敏度分析 从表中可得到 -3 c21 时，原最优解 不变。 例：某企业利用三种资源生产两种产品的最优计划 问题归结为下列线性规划 已知最优表如下。 （ 1）确定 x2的系数 c2的 变化范围，使原最优解 保持最优； （ 2）若 c2=6， 求新的最 优计划。 一、 价 值 系数 cj的 变 化分析 cj 5 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 25 0 0 1 2 -5 5 x1 35 1 0 0 1 -1 4 x2 10 0 1 0 -1 2 0 0 0 -1 -3 4 = c2 5 0 5 = 5 2c2 0 5/2 c2 5 cj 5 c2 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 25 0 0 1 2 -5 5 x1 35 1 0 0 1 -1 c2 x2 10 0 1 0 -1 2 0 0 0 c2 - 5 5 - 2c2最优解 X*=（ 35， 10， 25， 0， 0） 保持不变。 （ 1） Cj 5 6 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 25 0 0 1 2 -5 5 x1 35 1 0 0 1 -1 6 x2 10 0 1 0 -1 2 j 0 0 0 1 -7 0 x4 25/2 0 0 1/2 1 -5/2 5 x1 45/2 1 0 -1/2 0 3/2 6 x2 45/2 0 1 1/2 0 -1/2 j 0 0 -1/2 0 -9/2 x1*=45/2， x2*=45/2， x4*=25/2， x3*= x5*=0， z*=495/2 （ 2） XB= B 1b 例：对于上例中的线性规划作下列分析： （ 1） b3在什么范围内变化，原最优基不变？ （ 2）若 b3=55， 求出新的最优解。 二、右端常数 bi的 变 化分析 cj 5 4 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 25 0 0 1 2 -5 5 x1 35 1 0 0 1 -1 4 x2 10 0 1 0 -1 2 0 0 0 -1 -3 最优基： B=（ P3， P1， P2） B 1= （ 1） B 1 = = 0 解得 40b350， 即当 b3 40， 50 时，最优基 B