对偶理论与灵敏度分析课件

1、运 筹 学“运筹学”课题组本章内容重点 2.1 线性规划的对偶理论2.2对偶单纯形法2.3灵敏度分析第二章 线性规划的对偶理论与灵敏度分析2.1 线性规划的对偶理论一、对偶问题的提出 对偶理论是线性规划问题的最重要的内容之一。每一个线性规划（LP）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ的LP都有一个求minW的LP。其中的一个问题叫“原问题”，记为“LP”，另一个称为“对偶问题”，记为“DP”。第二章 线性规划的对偶理论与灵敏度分析例2.1 资源的合理利用问题 某工厂在计划期内安排生产、两种产品，已知资料如表2.1所示，问应如何安排生产计划使得既能充分利用现有资源有使总利

2、润最大？表2.1 III资源总量原材料2 3 24 工时52 26 利润(元)4 3 假设 x1、x2分别表示在计划期内生产产品I、II的件数，其数学模型为： 现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的工时和购买工厂的材料，为其加工生产别的产品，由客户支付工时费和材料费，此时工厂应考虑如何为每种资源定价，同样使其获得的利润最大？分析问题：1、每种资源定价不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受解: 1)决策变量：设y1，y2分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金。 2）目标函数：此时工厂的总收入为 ，这也是租赁方需要付出的成本。而

3、在这个问题中，是企业不生产，将自己的资源出售或出租，因此，此时起决定作用的是租赁方，所以此时的目标函数为 3)约束条件:工厂决策者考虑： （1）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有： （2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）。租赁者考虑：希望价格越低越好，否则另找他人。 于是，能够使双方共同接受的是： 上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。 模型对比：（原问题） （对偶问

4、题） 一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：原问题（LP） 对偶问题（DP） 相应的矩阵形式为：原问题（LP） 对偶问题（DP） 二、对偶理论1、原问题与对偶问题的关系 对称形式的对偶问题为：原问题（LP） 对偶问题（DP） 由以上两式可知，原问题与对偶问题之间具有如下关系：(1) 原问题中的约束条件个数等于它的对偶问题中的变量数；(2) 原问题中目标函数的系数是其对偶问题中约束条件的右端项；(3) 约束条件在原问题中为“”，则在其对偶问题中为“”；(4) 目标函数在原问题中为求最大值，在其对偶问题中则为求最小值。例2.2 写出下述线性规划问

5、题的对偶问题解：按照上述规则，该问题的对偶线性规划为: 当线性规划的约束条件为等式约束时，原问题与其对偶问题之间的变量关系就是非对称形式的对偶关系。此时，原问题为:对偶问题为:该对偶问题的特点是：对偶变量符号不限，系数矩阵为原问题系数矩阵的转置矩阵。 根据上述实例计算结果，考虑可能出现的各种情况，归纳出原问题与对偶问题之间的关系，可以用表2.2表示。表2.2 原问题与对偶问题的关系原问题Max（对偶问题） 对偶问题Min（原问题） 约束条件数=m 变量个数=m 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=” 第i个变量0第i个变量0第i个变量无限制 变量个数=n 约束条件个数=

6、n 第i个变量0第i个变量0第i个变量无限制 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=” 第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数第i个约束条件的右端项 例2.3 写出下述线性规划问题的对偶问题按照表2.2将线性规划问题化为对偶问题2、对偶问题的基本定理原问题（LP） 对偶问题（DP） （1）（对称性）对偶问题的对偶是原问题。 证：设原问题是 其对偶问题为 若将上式两边取负号，又因为 可得到又因为可得这就是原问题。根据对称变换关系，上式的对偶问题是（2）（弱对偶定理）若X(0)是原问题的可行解，Y(0)是对偶问题的可行解，则有C X(0)Y(0

7、)b。证：设原问题是 因 是原问题的可行解，所以满足约束条件，即 若是给定的一组值，设它是对偶问题的可行解，将 左乘上式，得到原问题的对偶问题是因为是对偶问题的可行解，所以满足将右乘上式，得到（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。证：由弱对偶性显然得。 注意这个问题的性质不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。4）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，且C X(0) = Y(0) b，则X(0)、Y(0)分别是它们的最优解。 证：若 ，根据性质2知 ，对偶问题的所有可行解Y都存在 ，

8、因为 ，所以 ，可见 是使目标函数取值最小的可行解，因而是最优解。同样可以证明：对于原问题的所有可行解X，存在 ，所以 是最优解。（5）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。 从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：原问题与对偶问题都有最优解，且CX=Yb；一个问题具有无界解，则它的对偶问题无可行解；两个问题均无可行解。（6）（互补松驰性）若X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充要条件是： Y*XS=0,YSX*=0(其中XS，YS分别是原问题和对偶问题的松驰变量向量)。证明：设原问题和对偶问

9、题的标准型是 原问题 对偶问题 将原问题目标函数中的系数向量C用 代替后，得到 将对偶问题的目标函数中的系数向量，用 代替后，得到 若 ；则 故 是最优解。 又若 分别是原问题和对偶问题的最优解，则必有 由 ，我们可以得到如下结论：（1） 若对偶变量值不等于零，则其对应的原问题约束方程中的松弛变量必定为0，也即该约束方程取严格等式。（2） 若原问题中某个松弛变量不等于零，则对应的对偶问题中的变量必定为0。 由 ，我们可以得到如下结论：（1） 若对偶问题中某个剩余变量不等于零，则对应的原问题中的变量必定为0。（2） 若原问题的变量值不等于零，则其对偶问题中对应的松弛变量必定为0，也即对偶问题中该

10、约束方程取严格等式。 一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下结论： 设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。例2.5 已知 试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为 用图解法可求得对偶问题的最优解：Y*=（1，3），W=11。 将代入对偶约束条件，（1），（2），（5）式为紧约束，（3），（4）为松约束。 令原问题的最优解为X* = （x1，x2，x3，x4，x5），则根据互补松弛条件，必有x3 = x4 =

11、0化简为又由于，原问题的约束必为等式，即 此方程组为无穷多解 令x5 =0,得到x1=1，x2=2， 即X*1 =（1，2，0，0，0）为原问题的一个最优解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0，即X*2（5/3，0，0，0，2/3）也是原问题的一个最优解，Z=11。三、对偶问题的经济解释影子价格1、影子价格 在一对LP和DP中，若LP的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量称为第i个约束条件的影子价格，又称为边际价格。 设：B是问题LP的最优基，由前式可知， 当bi变为bi+1时（其余右端项不变，也不影响 B），则目标函数最优值

12、变为：所以有也可以写成：即表示Z*对bi的变化率。其经济意义是： 在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对偶变量yi就是第 i 个约束条件的影子价格。 影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。 资源的影子价格定量的反映了单位资源在最优生产方案中为总收益所做出的贡献，因此，资源的影子价格也可称为在最优方案中投入生产的机会成本。 也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。 若第i 种资源的单位市场价格为mi，当yi mi时，企业愿意购进这种资源，单位

13、纯利为yimi，则有利可图； 如果yi 0，说明该资源已耗尽，成为短线资源 影子价格=0，说明该资源有剩余，成为长线资源（3）可以预测产品的价格 产品的机会成本为CBB-1A-C，只有当产品价格定在机会成本之上，企业才有利可图。 （2）对市场资源的最优配置起着推进作用 即在配置资源时，对于影子价格大的企业，资源优先供给（4）可作为同类企业经济效益评估指标之一。 对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。 通过以上讨论可知： 只有某资源对偶解大于0，该资源才有利可图，可增加此种资源量；若某资源对偶解为0，则不增加此种资源量。 直接用影子价格与市场价格相比较，进行决

14、策，是否买入该资源。 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。 不要简单理解为是求解对偶问题的单纯形法。2.2 对偶单纯形法 求解原问题（LP）时，可以从（LP）的一个基本解（非基可行解）开始，逐步迭代，使目标函数值（Z=Y b= CB B-1b =CX）减少，当迭代到XB=B-1b0时，即找到了（LP）的最优解，这就是对偶单纯形法。 因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。1. 单纯形法的重新解释 设X*是最大化LP问题最优解的充要条件是同时满足 根据对偶问题的对称性，也可以在

15、保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是根据这种思想所设计的。 因此对偶单纯形是先保证现行解对对偶问题可行，即 ，然后从 迭代到 。对偶单纯形的计算步骤：（1）根据线性规划问题，列出初始单纯形表。 检查b列的数字，若都为非负，且检验数都为非正，则已得到最优解，停止计算。 若检查b列的数字时，至少还有一个负分量，检验数保持非正，转（2）；（3）确定换入变量 在单纯形表中检查所在的行的系数 ， 若所有的 ，则无可行解，停止计算。 若存在 ，计算（2）确定换出变量 按 对应的基变量为换出变量； 按规则，所对应的列变量的非基变量为换入变量；（4）以 为主元素，按单纯形

16、法进行换基迭代，得到新的单纯形表； 重复（1）（4）的步骤进行计算。例2.7 用对偶单纯形法求解：解：将模型转化为cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-50010-9-12-15000表24 从表24可以看出，检验数行对应的对偶问题的是可行的，因b列数字为负，故需进行迭代运算。 换出变量的确定：按上述对偶单纯形计算步骤（2），计算 故 为换出变量。 故 为换入变量。换入、换出变量所在列、行的交叉处的元素为主元素。 按单纯形法计算步骤进行迭代，得表25换入变量的确定： 按上述对偶单纯形计

17、算步骤（3），计算表25 cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-7.2-1.8-1.8010-0.20 x5-9.2-1.8-2.8001-0.2-15x32.80.20.2100-0.242-6-9000-3重复以上步骤得表26、表27cj-9-12-15000CBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14-15x315/71/140101/14-3/14501/7-3/14000-5/1433/14表26 表27 cj-9-12-15000CBxBbx1x2x3x4x5

18、x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/972000-1/3-3-7/3所以，X*=（2，2，2，0，0，0）， =72 原问题 Z* =72。 通过上面的例子，可以看出对偶单纯形方法与一般单纯形方法的区别：（1）单纯形表。 一般单纯形表始终保持基本可行解，而对偶单纯形表先保持对偶解可行，原问题的解不可行。（2）换基迭代过程。 一般单纯形方法先确定换入基变量，后确定换出基变量。对偶单纯形方法反过来，先确定换出基变量，后确定换入基变量。（3）换出基变量的确定规则。 一般单纯形方法是以最大检验数对应的非基变量作为换出基变量，然后将已得到的基变

19、量的值与换入基变量所在的列的正分量相除，以最小比值对应的基变量作为换出基变量。 在对偶单纯形求解时，以基变量的负值中最小的对应的为换出基变量，将检验数与换出基变量所在行的负分量相除，然后选取最小比值对应的非基变量为换入基变量。（4）最优解的判别标准。 一般单纯形最优解的判别标准为 对偶单纯形最优解的判别标准为对偶单纯形的优点与用途：（1）初始解可以是非可行解，当检验数都是负数时，就可以进行基变换，这样避免了增加人工变量，使运算简便。（2）对变量较少时，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形求解，简化计算。（3）用于后面的灵敏度分析。 最后提醒一下： 对偶单纯形方法不

20、能理解为是求解对偶问题的方法，相反它却是求解原问题最优解的有效工具。2.3 灵敏度分析 在前面的线性规划问题讨论中，都是假定为常数，但实际工作中这些系数往往是估计值和预测值。 如市场条件发生变化，价值系数就会发生变化； 当资源投入量发生改变时，也随着发生变化； 因此当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化？ 或者这些系数在什么范围内变化时，线性规划问题的最优解不发生变化。因此我们在进行灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新的最优解ABC资源量甲11112乙12220利润586问

21、：如何安排产品产量，可获最大利润？表2.12下面分别就各个参数改变后的情形进行讨论。例2.9 已知某企业计划生产3种产品A、B、C，其资源消耗与利润如表2.12所示解：设三种产品的产量分别为x1、x2、x3其数学模型的标准型为该问题的初始单纯形表如表2.14所示58600XBbx1x2x3x4x50 x412111100 x52012201058600表2.14经过计算得最优表如表2.1558600XBbx1x2x3x4x55x141002-18x28011-11Z8400-2-2-3这时最优方案为 X=(4,8,0)T,目标值为84表2.151.目标函数中的价值系数Cj的灵敏度分析（1）非基

22、变量的价值系数的灵敏度分析 由于检验数 j= cj CBB-1 Pj，因此 cj 的改变，只使检验数 j 发生改变，其它不变。 如果 cj的改变，检验数 j仍小于零时，这时对最优解方案没有影响。 在例2.9中，如果改变 c3 ，使 原最优方案不发生改变。若改变为10时， ，这时原方案已不是最优方案。这时单纯形表变为表2.16581000XBbx1x2x3x4x55x141002-18x28011-11Z84002-2-3表2.16581000XBbx1x2x3x4x55x141002-110 x38011-11Z1000-200-5表2.17 单位产品C3的利润为10时，则最优方案调整为 X=

23、(4,0,8)T,目标值为100。（2）基变量的价值系数 Cj 的灵敏度分析如果cj的改变，使全部检验数j仍小于零时，这时对最优解方案没有影响，但对最优值发生改变。在例2.9中，如果c1改变，使即 解得 ， 这时原最优方案不发生改变。即单位产品A的利润在4,8之间变化时,最优方案不变，但最优值为 。若改变为10时， ，这时需要换基迭代。这时原方案已不是最优方案。这时单纯形表变为表2.18108600XBbx1x2x3x4x510 x141002-18x28011-11Z10400-2-122表2.18表2.19108600XBbx1x2x3x4x510 x112111100 x58011-11

24、Z1200-2-4-100单位产品A的利润为10时，则最优方案调整为 X=(12,0,0)T,目标值为120。2、资源约束数量b的灵敏度分析从矩阵形式的单纯形表中可以看出，b的变化只影响最优解的变化和最优值的变化。bXXBB-1bB-1AZ-C BB-1bC-C BB-1A 因此，当 时，最优基不变（即生产产品的品种不变，但数量及最优值会变化）。 是一个不等式组，从中可以解得b的变化范围，若 B-1b中有小于0的分量，则需用对偶单纯形法迭代，以求出新的最优方案。（1） 若 的改变，使 时，最优方案不变。在例2.9中，如果 改变，则 解得 即原料甲的供应量在10，20之间时并不影响最优方案。当

25、时，最优方案调整为 X=(16,2,0)T,目标值为96。（2）若改变为30时表2.2058600XBbx1x2x3x4x55x1401002-18x2-10011-11-Z-12000-2-2-3利用对偶单纯形法可解得58600XBbx1x2x3x4x55x120122010 x4100-1-11-1-Z-1000-2-40-5原料甲的供应为30，则最优方案调整为 X=(20,0,0)T,目标值为100。表2.213、添加新变量的灵敏度分析 在例2.9中，若新开发新产品D，该单位产品需要消耗原材料甲：3个单位，乙：2个单位，可以得利润10。 问：投产产品D是否有利？因此最优方案不变。投产产品

26、D无利。（1）产品D的利润为多少时，投产产品D有利？只有 时， 才能进入基，也就是说产品D才能生产，这时解得 。即当 时，投产产品D才有利。（2）当 时，表2.225860015XBbx1x2x3x4x5x65x141002-148x28011-11-1-Z-8400-2-2-33表2.235860015XBbx1x2x3x4x5x615x611/400-1/2-1/418x291/411-1/23/40-Z-87-3/40-2-7/2-9/40单位产品D的利润为15时，这时生产方案为： 生产 B产 品 9件 ， 生产D产品1件。目标值为87。4、添加新约束的灵敏度分析 在例2.9中，假设电力

27、供应紧张，若电力供应最多为13单位，而生产产品A、 B、C每单位需电力分别为2、1、3个单位问该公司生产方案是否需要改变？解：先将原问题的最优解x14，x28，x30代入电力约束条件2x1+x2+3x313 因为42+8=1613 ，故原问题最优解已经不是新约束条件下的最优解。 在电力约束条件中加入松弛变量得2x1+x2+3x3x613 以x6为基变量，将上式反映到最终单纯形表中得到表2.24表2.24586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x613213001-Z-8400-2-2-30在表2.24中，x1、x2、x6为基变量，因此所对应的列

28、向量应为单位向量，因此经计算得表2.25。586000XBbx1x2x3x4x5x65x141002-108x28011-1100 x6-3002-311-Z-8400-2-2-30表2.25利用对偶单纯形法计算得表2.26586000XBbx1x2x3x4x5x65x12104/30-1/32/38x29011/302/3-1/30 x4100-2/31-1/3-1/3-Z-8200-10/30-11/3-2/3增加电力约束后，这时生产方案为：生产A产品1件，生产 B产 品 9件。目标值为82。表2.265、技术系数改变(计划生产的产品工艺结构发生改变)（1）非基变量的工艺发生改变 当 是非基变量 的系数时，它的变化不会改变 ,它只影响单纯形表 列，只是对检验数有影