最优化方法课件：2-4 对偶规划与灵敏度分析

1、14 对偶规划与灵敏度分析 对偶线性规划 对偶定理 对偶单纯形法 灵敏度分析2 对偶理论是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划问题。 原问题和对偶问题紧密关联，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。 由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。 3对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时

2、数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。对偶线性规划设备每吨产品的加工台时 可供台时数 甲 乙 ABC 359 448 364076 利润（元/吨） 32 30 4 假设计划期内甲乙两种产品各生产 吨，设备每吨产品的加工台时 可供台时数 甲 乙 ABC 359 448 364076 利润（元/吨） 32 30 用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产 吨，乙产品生产8吨，可以使总利润达到最大，为 元。5 现在从另一个角度来考虑该工厂的生产问题:假设该厂打算不再自己生产甲,乙产品，而是把各种设备租让给其他工厂，这时工厂的决

3、策者应该如何确定各种设备的租价。设 分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少设备每吨产品的加工台时 可供台时数 甲 乙 ABC 359 448 364076 利润（元/吨） 32 30 6由此可得两个对称的线性规划：7矩阵形式：8可以得到另一个线性规划：称之为原线性规划问题的对偶问题， 对偶线性规划考虑如下具有不等式约束的线性规划问题9101112若令线性规划标准型的对偶规划为： 线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题 由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标

4、准形线性规划问题可等价表示为：它的对偶规划为：13对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始对偶表： 目标函数变量系数约束条件右端项 约束条件右端项目标函数变量系数 约束条件个数：n个 变量个数：n个 变量个数：m个 约束条件个数：m个 目标函数minW 目标函数maxZ 对偶问题（或原问题） 原问题（或对偶问题） 14解：对偶规划：例2 写出下列线性规划的对偶问题15例3 写出下列线性规划的对偶问题解：上述问题的对偶规划：16本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和

5、对偶问题的解之间的基本关系。定理1：（对合性）对偶问题的对偶是原问题。证明：设原问题为对偶问题为改写对偶问题为对偶问题的对偶为对偶定理17 定理2：弱对偶定理 若是原（极小化）问题的可行解，是对偶（极大化）问题的可行解，那么 证明：因为是对偶问题的可行解，所以满足约束条件 又因为是原问题的可行解，可得，,所以 。注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。 对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。推论1：如果原问题没有下界（即minZ），则对偶问题不可行。 如果对偶问题没有上界（即maxW），则原问题不可行。 若原问题与对偶问题之

6、一无界，则另一个无可行解。18证明：由弱对偶定理，对于原始问题的所有可行解，都有 因此是原问题的最优解。同理，对于对偶问题的所有可行解 ，都有 所以 是对偶问题的最优解。 推论2：最优性定理若是原问题的可行解，是对偶问题的可行解，而且两者的目标函数值相等，即，则和分别是原问题和对偶问题的最优解。19证明：设是原问题(min)的最优解，则对应的基必有。若定义，则 ，因此为对偶问题的可行解，而且 ，由最优性定理，是对偶问题的最优解。 定理3: 强对偶定理 如果原问题（min)与对偶问题(max)之一有最优解，那么另一个也有最优解，而且目标函数值相等。20证明：设满足原问题(min)的最优性条件，则

7、对应的基必有。若定义 ，则 ，因此为对偶问题的基本可行解。 定理4：设满足原问题(min)的最优性条件的一个基本解，则其对应的线性规划问题(min)的检验数对应对偶问题的一个基本可行解。21原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。22定理5：互补松弛定理如果 分别是原问题(min)和对偶问题（max)的可行解，那么 和 为最优解的充要条件是 通常称之为互补松弛条件。证明：充分性必要性23例5、已知线性规划问题:其对偶问题的最优解。试用互补松弛定理找出原问题的最优解。解：原问题的对偶问题为：由对偶问题最

8、优解可知，由互补松弛定理， 解方程组 所以原问题最优解24 假设计划期内甲乙两种产品各生产 吨，设备每吨产品的加工台时 可供台时数 甲 乙 ABC 359 448 364076 利润（元/吨） 32 30 用图解法或单纯形法可求得最优解 (元) 即在计划期内甲产品生产 吨，乙产品生产8吨，可以使总利润达到最大，为 元。例：对偶最优解的经济解释影子价格 2526由强对偶定理可知，如果原问题有最优解，那么对偶问题也有最优解，而且它们的目标函数值相等，即有：其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不

9、是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadow price)。27影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量，由互补松弛定理，在对偶最优解中，第i种资源的影子价格。反之如果第i种资源的影子价格，那么由互补松弛定理，原问题的第i个约束为严格等式，即，这表明第i种资源已经用完，成为稀缺资源。 资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价

10、格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。28设备每吨产品的加工台时 可供台时数 甲 乙 ABC 359 448 364076 利润（元/吨） 32 30 例：对偶最优解其中为设备A的影子价格，在资源最优利用的条件下，设备A每增加一个单位台时，可以使总利润增加元。若设备可供台时数，则29对偶单纯形法单纯形法是以保持原问题可行为条件，即不论进行怎样的基变换，常数列必须保持非负。利用对偶问题的对称性，我们从另一个角度来考虑求解原问题最优解的方法，这种方法以保持对偶问题可行为条件，即不论进行何

11、种基变换，必须保持所有的检验数非负，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上逐步转换成基本可行解，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法的基本思想。单纯形法： 可行性最优性对偶单纯形法：最优性可行性30例6 求解下列线性规划 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 min z=5x1+2x2+6x32x1 +4x2+8x3 - x4 =244x1 + x2 +4x3 -x5 =8x1、x2，x3，x4，x50 min z=5x1+2x2

12、+6x32x1 4x2 8x3 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x5031Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80032对偶单纯形法基变换的次序和一般单纯形法不同：一般单纯形法首先由最大减少原则确定换入变量，然而用最小比值原则确定换出变量 。对偶单纯形法则是先将具有负分量的基变量 取出，作为换出变量，然后确定某个非基变量作为换入变量。其变换目的是在保持对偶问题可行性的前提下，使原问题的基本解向可行解靠拢。33对偶单纯形法的计算步骤如下：（4）以 为主元进

13、行旋转变换，得新的单纯形表，返回（2）。 （2）确定换出变量 根据 ，确定基变量 作为换出变量。检验所在行各元素若所有,则无可行解，停止计算。否则转入().（3）确定换入变量按最大比值原则，若确定非基变量 为换入变量。（1）根据原始线性规划，列出初始单纯形表，检查b列数字，若b列数字全部非负，则已经求得最优解，停止计算。若b列中至少有一个负分量，则转入（2）.34例6 用对偶单纯形法求解下列线性规划 min z=5x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解 将问题改写成如下形式 min z=5x1+2x2+6x32x1 4x2 8x3

14、 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正则基。35 7/4 0 1 1/8 -1/21x36 -3 1 0 -1/2 14x22-2/7 0 -2 -1/4 1-2x501 /2 1 2 -1/4 06x22-4 -1 -4 0 1-8x50-2 -4 -8 1 0-24x40 1/2 0 0 1/4 0 4/(-7/2) 2/-2 (1/2)/(-1/4) 4 0 2 1/2 0 5/-2 2 /-4 6/-8 5 2 6 0 0 x1 x2

15、 x3 x4 x5bXBCB 5 2 6 0 0C36最后一个单纯形表中，已得到一个可行的正则解，因而得到问题的最优解为 X*=（0，4，1）T最优值为z*=14（1）对于形如min z=CX，AXb，X0，且C0的线性规划问题。因为将其改写为max (z) =CX，AX+XS=b，X0，则立即可以得到初始正则解； （2）在灵敏度分析中，有时需要用对偶单纯形法，可使问题的处理简化。对偶单纯形法在以下情况下较为方便。37例7 用对偶单纯形法求解解：先化为标准型 对偶单纯形允许约束方程右端为负，因此可将方程2，3两端同乘-1，可得含单位矩阵的标准型：38据此列出初始单纯形表，并施行对偶单纯形法迭代

16、步骤如下： 5/4 7/4 000-1/4 1/4 0102x2 2 -1/4 -3/4 0014x1 3 5/4 3/4 1004x3 0 2/3 0007/3 -1/3 0011/3 10/3 x2 21/3 100-4/3-16/3 x4 0101018 x3 000023100-3-1 -10 x5 00101-1 -2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 0002 3 C可得最优解 39例8 用对偶单纯形法求解下列线性规划 min z=x1+2x2x1 +x2 42x1 +3 x218x1、x20解 将问题改写成如下形式 min z=x1+

17、2x2x1 +x2 + x3 =42x13x2 + x4 =18x1、x2，x3，x40显然，p3、p4可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p3、p4构成的就是初始z正则基。1 0 3 1 -6x11 0 1 -2 -1 10 x221 3/2 0 -1/2 9x110 -1/2 1 1/2 -5x30-2 -3 0 1-15x401 1 1 04x300 0 1 10 1/2 0 1/2 1/-2 2/-3 1 2 0 0 x1 x2 x3 x4 bXBCB 1 2 0 0C41灵敏度分析 线性规划问题所对应的数据集合，b，常常是通过预测或估计所得到的统计数据

18、，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。 因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。 42灵敏度分析主要讨论如下二类问题：数据集合在什么范围内波动将不影响最优解或最优基？若最优解发生变化，应如何找到新的最优解。CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn) CB2 XB2 : : CBm XBm C-CBTB-1A 列出标准型线性规划问题最优单纯形表：43价值向量C的改变当价值向量由 时，

19、检验行应修改为：目标函数值应为 。 只要非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于分别就价值系数对应非基变量或基变量加以讨论：44若是非基变量的价值系数，为其改变量，在最优表中检验数 发生变化。若超出范围，那么 ，当前解已不是最优解。此时以修改后的最优单纯形表出发，进行单纯形迭代，直至求出新的最优解。 由 只要 即就可以保持现行最优解仍为最优。 45若是某基变量的价值系数，为改变量，在最优表中所有的非基变量检验数均发生了变化.由上式可得到一个不等式组，求解该不等式组就可得到价值系数 的可变动范围。由，只要检验数： 或则最优解仍然保持为最优.46例7、某工厂用甲乙两种原

20、料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：原料（公斤）产品（万件）供应量A B C D甲乙3 2 10 40 0 2 1/2183利润（万元/万件）9 8 50 19问应该怎样组织生产，才能使总利润最大，若产品或的利润产生波动，波动范围多大时，原最优解保持不变？解：设生产，四种产品各万件，则此问题的线性规划模型为：47标准化，引入松弛变量x5,x6， 利用单纯形表求解： 4 2/3 0 0 13/3 10/3 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/321x4x3-19-50 0 -2 0 -2 3 102

21、6 1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/2x1x3-9-50 -9 -8 0 -13/2 0 251- 3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2x5x30-50 -9 -8 -50 -19 0 09/53/2 3 2 10 4 1 0 0 0 2 1/2 0 1183x5x600 x1 x2 x3 x4 x5 x6bXBCB -9 -8 -50 -19 0 0C即最优生产方案是生产产品1万件，产品2万件，不生产,两种产品。可得最大利润为88万元。 48C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x

22、5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表：原最优解不变，最优利润值（万元）也不变。(1)若 有改变量。因为为非基变量，由推得即 或时49C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表：()若 有改变量。因为为基变量，由推得即当或时原最优解不变，最优利润值 万元50右端

23、项向量b的改变当右端项向量时，改变的是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。若，可用对偶单纯形法再次进行迭代，直到求得新最优解。为了使B可行，只要或51例8、在例7中，若想增加甲种原料，问增加多少时原最优基不变？ 解：设甲种原料的改变量为 ,则由 即 最优目标函数值 (万元)由此可以推得， 即当 时，原最优基不变。此时最优解 或52约束矩阵A的改变 假设原线性规划问题有一个最优解其中为最优基，约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形：增加一个变量，增加一个约束条件。53 增加一个变量增加一个新变量，对应的价值系数为，对应的系数列向量

24、为，可得新的线性规划问题：设，则 为新问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果 ，则， 是新问题的最优解。否则以为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。54增加一个约束如果加入一个新的约束条件，不妨假设此约束条件为不等式形式，即在附加不等式约束左端加上一个松弛变量 ,新的线性规划变成 55由此可以在原来最优基的基础上定义一个新的基, 是非奇异矩阵，得到新问题的一个基本解 在原最优解基础上对新问题作初等行变换，使基变量对应的系数列向量为单位矩阵，该基本解不一定是可行解，但是由于是原线性规划问题的最优基，所以能保证该线性规划的对偶规划是可行的。56结论：如果由新基定义的基本解是非负的。那么该基本解就是有附加约束条件的新线性规划问题的最优解。不满足非负条件。那么至少有一个基变量小于零，此时可用对偶单纯形法求出新问题的最优解。57解：（1）设生产产品x7万件，1万件E产品的利润为c7万元，则数学模型变为：例9、在例7中，若考虑生产另一种产品，已知每生产1万件产品要消耗甲原料3公斤，乙原料1公斤，那么，产品的每万件利润为多少时才有利于该种产品投产？若假设该工厂又增加了用电量不超过9千瓦的限制，已知生产，四种产品各1万件分别耗电4，3，5，2千瓦，问此约束是否改变了原最优决策方案？58已知 是原问题的最优解，若令，则是现问题的一