第二章线性规划灵敏度分析

Chapter 2线性规划灵敏度分析上海工程技术大学 管理学院Chapter 2 灵敏度分析本章提要 Content 单纯形法的矩阵描述 改进单纯形法 对偶问题提出 线性规划对偶理论 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析 案例分析及 Matlab求解 习题Chapter 2 灵敏度分析单纯形法的矩阵描述 ？单纯形法矩阵的描述标准型 maxZ=CXAX=bX 0已知： A、 b、 cA=(NB)B=EChapter 2 灵敏度分析用非基变量表示基变量Z= CBB-1b + (CN - CBB-1 N)XNXB =B-1 b-B-1 NXNCBB-1b CN - CBB-1 N O B-1 b B-1 N ECBB-1b C - CBB-1 A B-1 b B-1 AChapter 2 灵敏度分析C - CBB-1A= (CN CB )- CBB-1 (NB )= (CN - CBB-1N, CB -CBB-1B)B-1A= B-1(NB )= (B-1N, B-1B)单个检验数： j = Cj - CBB-1 Pj 某列 Pj = B-1 Pj Chapter 2 灵敏度分析改进单纯形法对 maxZ=CX AX bX0 A=(P1 P2 Pn)(1)、已有初始可行基 B，求 B-1 ， XB = B-1 b(2)、计算 j = Cj -CB B-1Pj 若全部 j 0， 则计算Z0 = CB B-1 b, 停；否则，取 m+k =maxj ， Xm+k换入。 j0Chapter 2 灵敏度分析(3)、计算 Pm+k = B-1Pm+k ，若 Pm+k 0， 则无有限最优解 , 停；否则 =min biAim+karm+k 0 = brarm+kXr 换出(4)、最小 比值法 ：(5)、新基 B。 转 (1)。Chapter 2 灵敏度分析对偶问题提出问题 一：某公司在计划期内要安排生产 I II两种产品已知生产单位产品所需的设备台时及 A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利 2元，每生产一件产品 II可获利 3元，问应该如何安排计划使该工厂获利最多？如何安排方案？举例有哪些方面可以考虑呢？Chapter 2 灵敏度分析 先根据图表来列出模型Max Z= 2X1+3X2 X1+2X2 84X1 164X2 12X1, X2 0我们从另一个角度来讨论这个问题 .假如该工厂的决策者决定不生产产品 I II，而将其所有资源出租或外售 .这时工厂的决策者就要考虑给每种资源如何定价的问题 .设用 ,分别表示出租单位设备台时的租金和出让单位原材料 A,B的附加额 .他在做定价决策时 ,作如下比较 :若用一个单位设备台时和 4个单位原材料 A可以生产一件产品 I,可获利 2元 ,那么生产每件产品 I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品 I的利润 ,这就有 Y1+4Y2 2举例Chapter 2 灵敏度分析同理将生产每件产品 II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品 II的利润 ,这就有2Y1+4Y3 3把工厂所有设备台时和资源都出租和出让 ,其收入为f= 8Y1+16Y2+12Y3从工厂决策者的角度来看 W当然是越大越好 ,但从接受者眼光来说 W是越少越好 ,所以工厂决策者只可以在满足 所有产品的利润条件下 ,使其总收入尽可能的小 .因此可以列出如下线性规划问题f= 8Y1+16Y2+12Y3Y1+4Y2 22Y1+4Y3 3Yi 0, i = 1,2,3 Chapter 2 灵敏度分析v 各模型中有关数据的 “位置 ”示意图如下。 Chapter 2 灵敏度分析问题二 :考虑：资源拥有者为了实现一定的收入目标，将其 所拥有的资源出售，给每一种资源如何定价？Chapter 2 灵敏度分析Yi表示出售单位数量的第 i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有： 如果资源拥有者将所有资源出售，则他得到的总收入Chapter 2 灵敏度分析资源拥有者出售每一种资源的最低估价，可通过求 解线性规划问题 而得到。对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。 线性规划的对偶理论对偶定义对称形式： 互为对偶(LP) Max z = cT x (DP) Min f = bT ys.t. Ax b s.t. AT y cx 0 y 0 “Max - ” “Min- ”Chapter 2 灵敏度分析Chapter 2 灵敏度分析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 灵敏度分析Chapter 2 灵敏度分析综上所述其变换形式如下：原问题（或对偶问题） 对偶问题（或原问题）目标函数 max 目标函数 min约束条件m个 m个变量 0 0= 无约束变量n个 n个 约束条件 0 0 无约束 =约束条件右端项 目标函数变量的系数目标函数变量的系数 约束条件右端项Chapter 2 灵敏度分析小 练习 写出下列问题的对偶问题Chapter 2 灵敏度分析Chapter 2 灵敏度分析对偶问题的基本性质 性质 1:对称性规范原始，对偶问题的对偶是原问题。Max z = CX Min f = Ybs.t. AX b s.t. YA CX 0 Y 0 “Max - ” “Min- ” Chapter 2 灵敏度分析性质 2:弱对偶原理 （弱对偶性）：设 和 分别是 问题（ P） 和（ D） 的可行解，则必有性质 3:最优性判别定理若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b，则 X*. Y*分别是问题 P和 D 的最优解 。Chapter 2 灵敏度分析性质 4:线性规划的对偶原理（ 1）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（强对偶性）（ 2）若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性） 性质 5:互补松弛定理设 X*和 Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是Chapter 2 灵敏度分析同时成立一般而言，我们把某一可行点（如 X*和 Y* ）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。Chapter 2 灵敏度分析例题 判断下例说法是否正确，为社么？A 如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解B 如果线性规划的对偶问题无可行解，则原问题也