《运筹学：第二章线性规划的对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《运筹学：第二章线性规划的对偶理论与灵敏度分析（95页珍藏版）》请在金锄头文库上搜索。
1、内容回顾与思考内容回顾与思考 基可行解的概念和几何意义基可行解的概念和几何意义 单纯形法的原理步骤单纯形法的原理步骤 单纯形表的原理和结构单纯形表的原理和结构 大大M法的原理和步骤法的原理和步骤 Min型单纯形表计算方法型单纯形表计算方法对偶理论是对偶理论是LP的重要基础理论，它揭示了：每一个的重要基础理论，它揭示了：每一个LP都存在与它对偶的一个都存在与它对偶的一个LP，二者之间有密切的联系，以，二者之间有密切的联系，以至于把二者放在一起研究往往比单独研究一个问题更有至于把二者放在一起研究往往比单独研究一个问题更有意义意义Chapter2 对偶理论对偶理论 ( Duality Theory
2、)( Duality Theory ) 线性规划的对偶模型线性规划的对偶模型 对偶性质对偶性质 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析本章主要内容：本章主要内容：本章主要内容：本章主要内容：1线性规划的对偶问题线性规划的对偶问题设某工厂生某工厂生产两种两种产品甲和乙，生品甲和乙，生产中需中需4种种设备按按A，B，C，D顺序加工，每件序加工，每件产品加工所需的机品加工所需的机时数、每件数、每件产品的利品的利润值及每种及每种设备的可利用机的可利用机时数列于下表数列于下表 ：产品数据表产品数据表 设备设备产品产品ABCD产品利润产品利润（
3、元件）（元件） 甲甲 21402乙乙 22043设备可利用设备可利用机时数（时）机时数（时） 1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？获得最大利润？1. 对偶问题的提出对偶问题的提出对偶问题的提出对偶问题的提出对偶问题的提出对偶问题的提出解：解：设甲、乙型甲、乙型产品各生品各生产x1及及x2件，件，则数学模型数学模型为： 若厂长决定不生产甲和乙型产品，决定出租机器用于接受外若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳加工，只收加工费，那么
4、种机器的机时如何定价才是最佳决策？决策？对偶问题的提出对偶问题的提出在市在市场竞争的争的时代，厂代，厂长的最佳决策的最佳决策显然然应符合两条：符合两条：（1）不吃）不吃亏原原则。即机。即机时定价所定价所赚利利润不能低于加工甲、乙不能低于加工甲、乙型型产品所品所获利利润。由此原。由此原则，便构成了新，便构成了新规划的不等式划的不等式约束条件。束条件。 （2）竞争性原争性原则。即在上述不吃。即在上述不吃亏原原则下，尽量降低机下，尽量降低机时总收收费，以便争取更多用，以便争取更多用户。设设A、B、C、D设备的机时价分别为设备的机时价分别为y1、y2、y3、y4，则新的线性，则新的线性规划数学模型为：
5、规划数学模型为：对偶问题的提出对偶问题的提出把同种把同种问题的两种提法所的两种提法所获得的数学模型用表得的数学模型用表2表示，将会表示，将会发现一个有趣的一个有趣的现象。象。原问题与对偶问题对比表原问题与对偶问题对比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612min max z 对偶性是线性规划问题的最重要的内容之一。每一个线性规划（对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求）必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的的LP都
6、有一个求都有一个求 minZ 的的LP。其中的一个问题叫。其中的一个问题叫“原问题原问题”，记为，记为“P”，另一，另一个称为个称为“对偶问题对偶问题”，记为，记为“D”。对偶问题的提出对偶问题的提出2. 原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题原问题-P对偶问题对偶问题-D（4）目标的系数）目标的系数C 约束的常数项约束的常数项 约束的约束的A （4）约束条件的常数项）约束条件的常数项 目标的系数目标的系数 约束的约束的A对偶问题的提出对偶问题的提出2. 原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题与对偶问题
7、的对应关系原问题与对偶问题的对应关系原问题原问题-P对偶问题对偶问题-D（1）max（2）2个变量，对应两个产品个变量，对应两个产品（3）4个约束，对应四种资源个约束，对应四种资源 （1）min（2）2个约束，基于两个产品列出的个约束，基于两个产品列出的 （3）4个变量，对应每个资源的出让个变量，对应每个资源的出让价格价格对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式（1）对称形式）对称形式特点：目标函数求极大值时，所有约束条件为特点：目标函数求极大值时，所有约束条件为号，变号，变量非负量非负;目标函数求极小值时，所有约束条件为目标函数求极小值时，所有约束条件为号，变量非号，变量非负
8、负.原问题原问题对偶问题对偶问题目标函数目标函数maxmin约束条件约束条件变量数量变量数量约束条件个数约束条件个数约束条件个数约束条件个数变量数量变量数量对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式（P）（D）这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系：应关系： 原问题（原问题（P P） 对偶问题对偶问题 （D D） 目标目标max型型 目标目标min型型 有有n个变量（非负）个变量（非负） 有有n个约束（大于等于）个约束（大于等于） 有有m个约束个约束 （小于等于）（小于等于）
9、有有m个变量（非负）个变量（非负） 价格系数价格系数 资源向量资源向量 资源向量资源向量 价格系数价格系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转技术系数矩阵的转置置对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式例例 写出写出线性性规划划问题的的对偶偶问题解：首先将原问题变形为对称形式解：首先将原问题变形为对称形式 注意：以后不强调等式注意：以后不强调等式右段项右段项 b b00，原因在对偶，原因在对偶单纯型表中只保证单纯型表中只保证 而不保证而不保证 ，故，故 b b可以是负数。可以是负数。非对称形式的原非对称形式的原-对偶关系对偶关系(2) 非对称型对偶问题非对称型对偶问题若
10、给出的线性规划不是对称形式，可以先化成对称形式若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。再写对偶问题。例例 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.非对称形式的原非对称形式的原-对偶关系对偶关系例例 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.解：先将原问题化为对称形式解：先将原问题化为对称形式非对称形式的原非对称形式的原-对偶关系对偶关系例例 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.对偶问题对偶问题.非对称形式的原非对称形式的原-对偶关系对偶关系非对称形式的原非对称形式的原-对偶关系对偶关系原问题原问题.对偶问
11、题对偶问题 原问题（原问题（P P） 对偶问题对偶问题 （D D） 目标目标max型型 目标目标min型型 有有n个变量个变量 有有n个约束个约束 有有m个约束个约束 有有m个变量个变量 价格系数价格系数 资源向量资源向量 资源向量资源向量 价格系数价格系数 技术系数矩阵技术系数矩阵 技术系数矩阵的转技术系数矩阵的转置置非对称形式的原非对称形式的原-对偶关系对偶关系原问题原问题（或对偶问题）（或对偶问题）对偶问题对偶问题（或原问题）（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n个个约约束束条条件件000
12、0无约束无约束= =b b约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数C C目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项非对称形式的原非对称形式的原-对偶关系对偶关系例例 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题.解：原问题的对偶问题为解：原问题的对偶问题为无约束无约束非对称形式的原非对称形式的原-对偶关系对偶关系例例 写出下列写出下列线性性规划划问题的的对偶偶问题.解：原问题的对偶问题为解：原问题的对偶问题为非对称形式的原非对称形式的原-对偶关系对偶关系例例非对称形式的原非对称形式的原-对偶关系对偶关系2对偶问题的基本性质对偶问题的
13、基本性质性质性质1 1 对称性定理对称性定理：对偶问题的对偶是原问题：对偶问题的对偶是原问题min Z= - CXs.t. - AX - b X 0 min W= Y Tbs.t. ATY CT Y 0max Z=C Xs.t. AX b X 0对偶的定义对偶的定义对偶的定义对偶的定义max W = -YTbs.t. -ATY - CT Y 0对偶性质对偶性质性质性质2 2 弱对偶原理弱对偶原理( (弱对偶性弱对偶性) )：设设 和和 分别是问分别是问题题(P)(P)和和(D)(D)的可行解，则必有的可行解，则必有图示：图示：（P）（D）对偶性质对偶性质推论推论1: 原问题任一可行解的目标函数
14、值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。推论推论2: 在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中一个问题可行但）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；目标函数无界，则另一个问题无可行解；反之不成立反之不成立。这也是对这也是对偶问题的无界性。偶问题的无界性。图示：图示：对偶性质对偶性质推推论3 3：在一在一对对偶偶问题（P）和（）和（D）中，若一个可行（如）中，若一个可行（如P），
15、而另一个不可行（如），而另一个不可行（如D），），则该可行的可行的问题目目标函数函数值无界。无界。试估计它们目标函数的界，并验证弱对偶性原理。试估计它们目标函数的界，并验证弱对偶性原理。（P）例例对偶性质对偶性质解：解：（D） 由观察可知：由观察可知： =(1 1 1 1)T， =(1 1) T ，分别是，分别是（P）和（）和（D）的可行解。）的可行解。Z=10 ，W=40，故有，故有 ,弱对弱对偶定理成立。由推论偶定理成立。由推论可知，可知，W 的最小值不能小于的最小值不能小于10，Z 的最大值不能超过的最大值不能超过40。（P）（D）图示：图示：对偶性质对偶性质性性质4 强对偶性偶性：若原
16、若原问题及其及其对偶偶问题均具有可行解，均具有可行解，则两者均具有最两者均具有最优解，且它解，且它们最最优解的目解的目标函数函数值相等。相等。还可推出另一结论：若（还可推出另一结论：若（P）与（）与（D）都有可行解，则两者都）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。有最优解，若一个问题无最优解，则另一问题也无最优解。（P）（D）证：对（证：对（P）增加松弛变量）增加松弛变量 ， 化为：化为：设其最优基为设其最优基为B，终表为，终表为其检验数为其检验数为性质性质4 强对偶性强对偶性：若原问题及其对偶问题均具有可行解，则若原问题及其对偶问题均具有可行解，则两者均具有
17、最优解，且它们最优解的目标函数值相等。两者均具有最优解，且它们最优解的目标函数值相等。初始单纯形表和初始单纯形表和B为基的单纯形表为基的单纯形表问题：问题：问题：问题：(1) (1) 由对偶定理可知，对偶问题最优解的表达式由对偶定理可知，对偶问题最优解的表达式由对偶定理可知，对偶问题最优解的表达式由对偶定理可知，对偶问题最优解的表达式 Y*Y*T T = =？ (2) 求求Y*是否有必要重新求解（是否有必要重新求解（ D）？）？ CBB-1 不必。由对偶定理的证明过程可知，原问题不必。由对偶定理的证明过程可知，原问题（P）的）的单纯形终表单纯形终表可同时得到（可同时得到（P）和对偶问题）和对偶
18、问题（D）的最优解）的最优解。（P）的最优解）的最优解中基变量的解中基变量的解（D）的最优解）的最优解（P）和（）和（D）的）的最优值相等最优值相等例如，已知例如，已知 的终表为的终表为请指出其对偶问题的最优解和最优值。请指出其对偶问题的最优解和最优值。对偶性质对偶性质对偶性质对偶性质对偶性质对偶性质y1 yi ym ym+1 ym+j ym+n x1 xj xn xn+1xn+ixn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一
19、对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0直观上直观上对偶性质对偶性质性性质5的的应用：用：该性性质给出了已知一个出了已知一个问题最最优解求另一个解求另一个问题最最优解解的方法，即已知的方法，即已知Y求求X 或已知或已知X 求求Y 互补松弛条件互补松弛条件由于松弛变量都非负，要使求和式等于零，则必定每一分量为由于松弛变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：零，因而有下列关系：若若Y 0，则，则Xs必为必为0；若；若X 0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或
20、原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。对偶性质对偶性质例例 已知已知线性性规划划的最优解是的最优解是X=(6,2,0)T,求其对偶问题的最优解求其对偶问题的最优解Y。解：写出原问题的对偶问题，即解：写出原问题的对偶问题，即对偶性质对偶性质设对偶偶问题最最优解解为Y(y1，y2),由互由互补松弛性定理可知，松弛性定理可知，X和和 Y满足：足：即：即：因为因为X1=60，X2=20，所以对偶问题的第一、二个约束的，所以对偶问题的第一、二个约束的松弛变量等于零，即松弛变量等于零，即y30，y40，带入方程中：，带入方程中：解此线性方程组得解此线性方程组得y1=1,y2
21、=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y=(1,1)，最优值，最优值w=26。对偶性质对偶性质例例 已知已知线性性规划划 的对偶问题的最优解为的对偶问题的最优解为Y=(4/5,3/5)，求原问题的最优解。，求原问题的最优解。解解: 对偶问题是对偶问题是对偶性质对偶性质设对偶偶问题最最优解解为X(x1，x2 ，x3，x4，x5)T ,由互由互补松松弛性定理可知，弛性定理可知，X和和 Y满足：足：将将Y =(4/5,3/5)带入由方程可知第二带入由方程可知第二-四约束为等式，从而四约束为等式，从而x2x3=x40。 y1=4/50, y2=3/50 x6 x7= 0解方程组得：解方
22、程组得：x1=5,x5=1, 所以原问题的最优解为所以原问题的最优解为X=(1,0,0,0,1)T，最优值，最优值z=5定定义义：在在一一对对 P 和和 D 中中，若若 P 的的某某个个约约束束条条件件的的右右端端项项常常数数bi 增增加加一一个个单单位位时时，所所引引起起的的目目标标函函数数最最优优值值Z* 的的改改变变量量y*i称称为第为第i个约束条件的影子价格，又称为边际价格。个约束条件的影子价格，又称为边际价格。 3影子价格影子价格设：设：B是问题是问题 （ P ）的最优基，则）的最优基，则 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 当当b
23、i 变为变为bi+1 时（其余右端项不变，也不影响时（其余右端项不变，也不影响B） 目标函数最优值变为：目标函数最优值变为： Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以写成：也可以写成： 即即y*i 表示表示Z*对对 bi的变化的变化率。率。其其经经济济意意义义是是：在在其其它它条条件件不不变变的的情情况况下下，单单位位资资源源变变化化所所引引起起的的目目标标函函数数的的最最优优值值的的变变化化。即即对对偶偶变变量量yi 就就是是第第 i 个约束条件的影子价格。个约束条件的影子价格。也也可可以以理理解解为为目目标标函函数数最最
24、优优值值对对资资源源的的一一阶阶偏偏导导数数（但但问题中所有其它数据都保持不变）。问题中所有其它数据都保持不变）。若若第第 i 种种资资源源的的单单位位市市场场价价格格为为mi ，当当yi mi 时时，企企业业愿愿意意购购进进这这种种资资源源，单单位位纯纯利利为为yimi ，则则有有利利可可图图；如如果果yi mi ，则则企企业业有有偿偿转转让让这这种种资资源源，可可获获单单位位纯纯利利为为miyi ，否则企业无利可图，甚至亏损。，否则企业无利可图，甚至亏损。影子价格影子价格对偶问题的经济解释对偶问题的经济解释例（原问题）例（原问题） 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关
25、单耗某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源，有关单耗 数据如表，试拟定使总收入最大的生产计划。数据如表，试拟定使总收入最大的生产计划。127单价单价300103油油20054电电36049煤煤资源限制资源限制乙乙甲甲产品产品资源资源例（对偶问题）例（对偶问题）这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽这时有另一家厂商提出要购买其煤、电、油全部资源，并希望花费尽量少。试建立购买者的线性规划模型。量少。试建立购买者的线性规划模型。对偶问题的经济解释对偶问题的经济解释 对偶问题的最优解对偶问题的最优解 买主的最低出价；买主的最低出价； 原问题原问题资源的影子价格资源的
26、影子价格 当该资源增加当该资源增加1单单 位时引起的总收入的增量位时引起的总收入的增量卖主的内控价格。卖主的内控价格。 （1 1）对偶）对偶）对偶）对偶最优解的最优解的最优解的最优解的经济解释经济解释经济解释经济解释资源的影子价格资源的影子价格资源的影子价格资源的影子价格（Shadow PriceShadow Price）对偶问题的经济解释对偶问题的经济解释 对偶问题的最优解对偶问题的最优解 买主的最低出价；买主的最低出价； 原问题原问题资源的影子价格资源的影子价格 当该资源增加当该资源增加1单单 位时引起的总收入的增量位时引起的总收入的增量卖主的内控价格。卖主的内控价格。 （1 1）对偶）对
27、偶）对偶）对偶最优解的最优解的最优解的最优解的经济解释经济解释经济解释经济解释资源的影子价格资源的影子价格资源的影子价格资源的影子价格（Shadow PriceShadow Price）设：设：B是问题是问题 （ P ）的最优基，则）的最优基，则 Z*=CB B-1b = Y*Tb =y*1b1+ y*2b2+y*ibi+y*mbm 当当bi 变为变为bi+1 时（其余右端项不变，也不影响时（其余右端项不变，也不影响B） 目标函数最优值变为：目标函数最优值变为： Z*= y*1b1+ y*2b2+y*i （ bi+1 ）+y*mbm Z*= Z* Z* = y*i 也可以写成：也可以写成： 即
28、即y*i 表示表示Z*对对 bi的变化率。的变化率。对偶问题的经济解释对偶问题的经济解释例（煤电油例）的单纯形终表如下：例（煤电油例）的单纯形终表如下：（1）请指出资源煤电油的影子价格，并解释其经济意义。）请指出资源煤电油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？）由单纯形终表还可得到哪些有用的信息？例例（煤电油例）的单纯形终表如下：（煤电油例）的单纯形终表如下：（1）请指出资源煤、电、油的影子价格，并解释其经济意义。）请指出资源煤、电、油的影子价格，并解释其经济意义。（2）由单纯形终表还可得到哪些有用的信息？）由单纯形终表还可得到哪些有用的信息？解：（解：（1）
29、煤、电、油的影子价格分别是）煤、电、油的影子价格分别是0、1.36、0.52； 其经济意义是当煤、电、油分别增加其经济意义是当煤、电、油分别增加1单位时可使总单位时可使总 收入分别增加收入分别增加0 、1.36、0.52。（2）由单纯形终表还可得到：原问题的最优生产计划、）由单纯形终表还可得到：原问题的最优生产计划、资源剩余，对偶问题的最低购买价格等。资源剩余，对偶问题的最低购买价格等。 y1y2ym（2）对偶对偶约束的约束的经济解释经济解释产品的机会成本产品的机会成本 (Opportunity Cost)机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可
30、以增加的利润增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源对偶问题的经济解释对偶问题的经济解释机会成本机会成本利润利润差额成本差额成本（3）对偶对偶松弛变量的松弛变量的经济解释经济解释产品的差额成本（产品的差额成本（Reduced Cost）差额成本差额成本=机会成本机会成本 利润利润对偶问题的经济解释对偶问题的经济解释 在利润最大化的生产计划中在利润最大化的生产计划中 （1）影子价格大于）影子价格大于0的资源没有剩余；的资源没有剩余； （2）有剩余的资源影子价格等于）有剩余的资源影子价格等于0； （3）安排生产的产品机会成本等于利润；
31、）安排生产的产品机会成本等于利润； （4）机会成本大于利润的产品不安排生产。）机会成本大于利润的产品不安排生产。（4）互补松弛关系的经济解释）互补松弛关系的经济解释对偶问题的经济解释影子价格对偶问题的经济解释影子价格练习：填空练习：填空1 .根据根据LP的互补松弛定理，影子价格大于的互补松弛定理，影子价格大于0的资源一定的资源一定 剩余；剩余；安排生产的产品机会成本一定安排生产的产品机会成本一定 利润。利润。 A.没有，小于没有，小于 B .没有，大于没有，大于 C .没有，等于没有，等于 D .有，等于有，等于2.若若LP的原始问题增加一个变量，则其对偶问题就增加一个的原始问题增加一个变量，
32、则其对偶问题就增加一个 ；因而对偶的最优目标值可能变因而对偶的最优目标值可能变 。 A.约束，好约束，好 B .约束，坏约束，坏 C .变量，好变量，好 D .变量，坏变量，坏 对偶问题的经济解释影子价格对偶问题的经济解释影子价格4对偶单纯形法对偶单纯形法 对偶单纯形法是求解线性规划的另一个基本方法。对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称它是根据对偶原理和单纯形法原理而设计出来的，因此称为为对偶单纯形法对偶单纯形法。不要简单理解为是求解对偶问题的单纯。不要简单理解为是求解对偶问题的单纯形法。形法。对偶单纯形法原理对偶单纯形法原理对偶单纯形
33、法原理对偶单纯形法原理对偶单纯形法的基本思路对偶单纯形法的基本思路回顾单纯形法原理回顾单纯形法原理回顾单纯形法原理回顾单纯形法原理 能否尝试对称的思路，在保持能否尝试对称的思路，在保持0（对偶问题有可行解）（对偶问题有可行解）下改善可行性下改善可行性B-1b0？ 单纯形法是在保持可行性单纯形法是在保持可行性B-1b0下改善最优性下改善最优性0。基本思想基本思想 若保持若保持对偶偶问题的解是基可行解，而原的解是基可行解，而原问题在非在非可行解的基可行解的基础上，通上，通过逐步迭代达到基可行解，逐步迭代达到基可行解，这样也就得到了最也就得到了最优解。解。这种方法的种方法的优点是原点是原问题的初始的
34、初始解不一定是基可行解，可从非基可行解开始迭代。解不一定是基可行解，可从非基可行解开始迭代。 基本原理基本原理 对于原于原问题 对偶单纯形法的基本思路对偶单纯形法的基本思路设B是一个基，不失一般性是一个基，不失一般性,令令 ，它，它对应的基的基变量量为 。当当非非基基变量量都都为零零时，可可以以得得到到 。若若在在 中中至至少少有有一一个个负分分量量，设 ，并并且且在在单纯形形表表的的检验数行中的数行中的检验数都非正，即数都非正，即对偶偶问题保持可行解，它的各分量是保持可行解，它的各分量是: 对应基基变量的量的检验数是数是 对应非基非基变量的量的检验数是数是对偶单纯形法的基本思路对偶单纯形法的
35、基本思路 每每次次迭迭代代是是将将基基变变量量中中的的负负分分量量取取出出，去去替替换换非非基基变变量量中中的的，经经过过基基变变换换，所所有有检检验验数数仍仍保保持持非非正正。从从原原问问题题来来看看，经经过过每每次次迭迭代代，原原问问题题由由非非可可行行解解往往可可行行解解靠靠近近，当当原原问问题题得得到到可可行行解解时时，便便得到了最优解。得到了最优解。对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路：对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断条件下，判断XB是否可行（是否可行（XB
36、=b为非负），有最优解。否则，为非负），有最优解。否则，通过变换基解，直到找到原问题基可行解（即通过变换基解，直到找到原问题基可行解（即XB为非负），为非负），这时原问题与对偶问题同时达到可行解，由定理这时原问题与对偶问题同时达到可行解，由定理4可得。可得。对偶单纯形法的基本思路对偶单纯形法的基本思路找出一个找出一个D的可行基的可行基P是否可行是否可行（XB 0）保持保持D为可行解情况下转移到为可行解情况下转移到P的的另一个基本解另一个基本解最优解最优解是是否否循循环环结束结束对偶单纯形法的计算步骤对偶单纯形法的计算步骤列出初始单纯形表，检查b列中的各分量，若都为非负，且检验数都为非正，则已得
37、到最优解。若b列中至少有一个负分量，检验数保持非正，进行以下计算。确定换出变量。按照法则确定对应的基变量为换出变量。 对偶单纯形法的计算步骤对偶单纯形法的计算步骤 确定换入变量。 若xj所在行有负系数，计算 所对应的非基变量xk为换入变量。 以 为主元素，按原单纯形法迭代运算，得新单纯形表。 重复 的步骤，直至求得最优解。 例例 用对偶单纯形法求解：用对偶单纯形法求解：解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行（求出一组基本解，因为对偶问题可行（求max问题）。问题）。对偶单纯形法的计算步骤对偶单纯形法的计
38、算步骤对偶单纯形法的计算步骤对偶单纯形法的计算步骤cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001j-9-12-15000对偶单纯形法的计算步骤对偶单纯形法的计算步骤cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9,-45/-14,-15/-1)-6-9000-3cj-9-12-15000cBxBbx1x2x3x4x5x60x4-9
39、/7-9/14001-9/14-1/14-12x223/79/14100-5/141/14(-3/-9,-45/-9,-33/-1)-15x315/71/140101/14-3/14-3/14000-45/14-33/14对偶单纯形法的计算步骤对偶单纯形法的计算步骤cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9000-1/3-3-7/3原问题的最优解为：原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 由定理由定理4，其对偶问题的最优解为：，其对偶
40、问题的最优解为：Y*= （1/3 , 3 , 7/3），），W*= 72对偶单纯形法的计算步骤对偶单纯形法的计算步骤 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用用对对偶偶单单纯纯形形法法求求解解线线性性规规划划是是一一种种求求解解方方法法，而而不不是是去去求求对对偶问题的最优解偶问题的最优解 初初始始表表中中一一定定要要满满足足对对偶偶问问题题可可行行，也也就就是是说说检检验验数数满满足足最最优优判别准则判别准则 对对偶偶单单纯纯形形法法与与普普通通单单纯纯形形法法的的换换基基顺顺序序不不一一样样，普普通通单单纯纯形形法法是是先先确确定定进进基基变变量量后后确确定定出出基基变变量
41、量，对对偶偶单单纯纯形形法法是是先先确确定定出出基基变变量后确定进基变量；量后确定进基变量；对偶单纯形法对偶单纯形法 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是值是其目的是保证下一个对偶问题的基本解可行。其目的是保证下一个对偶问题的基本解可行。 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规规则则，任任选选一一个个小小于于零零的的b bi i对对应应的的基基变变量量出出基基，不不影影响响计计算算结结果果，只是迭代次数可能不一样。只是迭
42、代次数可能不一样。灵敏度分析又称灵敏度分析又称“后验分析后验分析”，它是对已经得到的最优方案改，它是对已经得到的最优方案改变某些条件来检验最优解的变某些条件来检验最优解的“稳定性稳定性”以及目标函数最优值以及目标函数最优值随各种条件变化的随各种条件变化的“敏感性敏感性”。讨论模型的系数或变量发生小的变化时对解的影响讨论模型的系数或变量发生小的变化时对解的影响（如，当模型的一个参数或多个参数发生变化时，问题的最（如，当模型的一个参数或多个参数发生变化时，问题的最优解会有什么变化？或，它们在何范围内变化时可使原最优优解会有什么变化？或，它们在何范围内变化时可使原最优解或最优基不变？）解或最优基不变
43、？）5灵敏度分析灵敏度分析换言之，假定对于已知线性规划问题已求得的最优解是获得换言之，假定对于已知线性规划问题已求得的最优解是获得的最大利润的生产计划安排，现在如果在生产过程中成本系的最大利润的生产计划安排，现在如果在生产过程中成本系数向量数向量C，约束常数向量，约束常数向量b，约束系数，约束系数A以及其他条件发生变以及其他条件发生变化或波动，这些变化限制在什么范围内，在原来得到的最优化或波动，这些变化限制在什么范围内，在原来得到的最优安排仍为最优，而不需要改变工作计划？安排仍为最优，而不需要改变工作计划？灵敏度越小，解的稳定性越好灵敏度越小，解的稳定性越好67灵敏度分析包括以下几个方面的内容
44、灵敏度分析包括以下几个方面的内容灵敏度分析包括以下几个方面的内容灵敏度分析包括以下几个方面的内容分析成本系数向量分析成本系数向量C C的变化对解和目标函数值的影响的变化对解和目标函数值的影响分析约束常数向量分析约束常数向量b b的变化对解的影响，以及通过对偶最的变化对解的影响，以及通过对偶最优解研究优解研究b b的变化对目标函数值的影响的变化对目标函数值的影响分析系数矩阵分析系数矩阵A A中元素变化对解和目标值的影响中元素变化对解和目标值的影响增加新变化量时最优解和最优值的变化增加新变化量时最优解和最优值的变化增加新的约束条件后对最优解和最优值的影响增加新的约束条件后对最优解和最优值的影响灵敏
45、度分析灵敏度分析主要讨论主要讨论C、b和变量结构和变量结构变化时对解的影响。变化时对解的影响。对解怎样影响？对解怎样影响？ 影响解的影响解的 - 最优性最优性 - 可行性可行性灵敏度分析的步骤灵敏度分析的步骤分析分析cj的变化的变化分析分析cj的变化的变化设设变化为变化为只要只要即即 则最优解不变（则最优解不变（此表仍为最优，此时最优解不变但最优值改此表仍为最优，此时最优解不变但最优值改变变）；否则（）；否则（此表不是最优单纯形表此表不是最优单纯形表），将最优单纯形表的），将最优单纯形表的检验数检验数 k k 用用 取代，继续单纯形法的表格计算取代，继续单纯形法的表格计算。 分析分析cj的变化
46、的变化例例：某某企企业业利利用用三三种种资资源源生生产产两两种种产产品品的的最最优优计计划划问问题题归归结结为下列线性规划为下列线性规划问题：问题：（1 1）确确定定x x2 2的的系系数数c c2 2的的变变化化范围，使原最优解保持最优；范围，使原最优解保持最优；（2 2）若若c c2 2=6=6，求求新新的的最最优优计划。计划。 分析分析cj的变化的变化cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14 x2 10 010-12j000-1-3最最 优优 单单纯纯 性性 表表如下：如下：分析分析cj的变化的变化4 = - 1 05 = -3 2 0
47、-3/2 1，即，即c2的变化范围应满足的变化范围应满足5/2 c2 5cj54+000CBXBbx1x2x3x4x50x3250012-55x1351001-14+x2 10 010-12j000 - 1-3 - 2最优解最优解X*=（35，10，25，0，0）保持不变。保持不变。（1）分析分析cj的变化的变化（2）Cj56000CBXBbx1x2x3x4x50x3250012-55x1351001-16 x2 10 010-12j 0001-70x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2用单纯形法求得：
48、用单纯形法求得：x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2分析分析cj的变化的变化分析分析bi的变化的变化例：对于上例中的线性规划作下列分析：例：对于上例中的线性规划作下列分析：（1 1）b b3 3在什么范围内变化，原最优基不变？在什么范围内变化，原最优基不变？（2 2）若）若b b3 3=55=55，求出新的最优解。，求出新的最优解。 分析分析bi的变化的变化cj54000CBXBbx1x2x3x4x50x3250012-55x1351001-14 x2 10 010-12000-1-3最优基：最优基：B=I=（P3，P1，P2）最优解：最
49、优解：X*=（35，10，25，0，0）分析分析bi的变化的变化（1）XB=B1b=0 B1解得解得40b350，即当，即当b340，50 时，最优基时，最优基B 不变不变z*=5（80b3）+4（80+2b3） =80+3b3=分析分析bi的的变化变化（2）当当 b3= 55 时时 =x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -101030 x2 4 100125x152100-25x30x4x3x2x1bXBCB0045Cj最优解：最优解：X*=（30，20，0，0，5）分析分
50、析bi的的变化变化用对偶单纯用对偶单纯形法求得：形法求得：增加一个变量增加一个变量xj 的分析的分析增加一个新变量在实际问题中反映为增加一种新的产品。增加一个新变量在实际问题中反映为增加一种新的产品。主要讨论增加新变量主要讨论增加新变量xn+1是否有利。经济意义是第是否有利。经济意义是第n+1种新产品种新产品是否应当投产，数学意义是是否应当投产，数学意义是xn+1是否是否应进基。应进基。经济意义：经济意义：市场价市场价影子价影子价例：（续前例）设企业研制了一种新产品，对三种资源的消耗例：（续前例）设企业研制了一种新产品，对三种资源的消耗系数列向量以系数列向量以P6表示表示 。问它的价值系数。问
51、它的价值系数c c6 6符合什么条件符合什么条件才必须安排它的生产？设才必须安排它的生产？设c c6 6=3=3，新的最优生产计划是什么？，新的最优生产计划是什么？=B1P6 =增加一个变量增加一个变量xj 的分析的分析Cj540003CBXBbx1x2x3x4x5x60x3250012-515x1351001-11/24 x2 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/20增加一个变量增加一个变量xj 的分析的分析分析参数分析参数a aijij的变化的变化例例: :在前例中，第
52、一种产品的消耗系数改变为在前例中，第一种产品的消耗系数改变为 , ,价值系数不变，求新的最优解。价值系数不变，求新的最优解。 B1=灵敏度分析灵敏度分析Cj54000CBXBbx1x2x3x4x50x3252012-55x1351001-14 x2 10 -1/210-12j 000-1-3Cj54000CBXBbx1x2x3x4x50x3252012-55x1351001-14 x2 10 -1/210-12j 000-1-30x3-450010-35x1351001-14 x2 27.5 010-1/23/2j000-3-10x51500-1/3015x15010-1/3104 x2 5
53、011/2-1/20j 00-1/3-30增加增加新的约束条件的分析新的约束条件的分析1 1、将最优解代入新的约束条件，若满足，则最优解不变、将最优解代入新的约束条件，若满足，则最优解不变2 2、若不满足，则当前最优解要发生变化；将新增约束条件、若不满足，则当前最优解要发生变化；将新增约束条件加入最优单纯形表，并变换为标准型加入最优单纯形表，并变换为标准型3 3、利用单纯形法或对偶单纯形法继续迭代、利用单纯形法或对偶单纯形法继续迭代 为什么可以利用对偶单纯形法？为什么可以利用对偶单纯形法？为什么可以利用对偶单纯形法？为什么可以利用对偶单纯形法？例例: : 假设在前例中，还要考虑一个新的资源约束
54、：假设在前例中，还要考虑一个新的资源约束： 4x4x1 1+2x+2x2 2150150标准化标准化增加增加新的约束条件的分析新的约束条件的分析原最优解原最优解X*=（35，10）不满足新约束）不满足新约束。cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104 x2 10 010-1200x6150420001000-1-30增加增加新的约束条件的分析新的约束条件的分析Cj540000CBXBbx1x2x3x4x5x60x3250012-505x1351001-104x210010-1200 x6 150 420001j 000-1-300x32
55、50012-505x1351001-104x210010-1200 x6 -10 000-201j000-3-300x3150010-515x1301000-11/24x21501002-1/20 x4 5 00010-1/2j0000-3-1/2思考题思考题判断下列判断下列结论是否正确，如果不正确，是否正确，如果不正确，应该怎怎样改正？改正？1 1）任何线性规划都存在一个对应的对偶线性规划）任何线性规划都存在一个对应的对偶线性规划. .2 2）原问题第）原问题第i i个约束是个约束是“”约束，则对偶变量约束，则对偶变量y yi i0.0.3 3）互为对偶问题，或者同时都有最优解，或者同时都无
56、最优解）互为对偶问题，或者同时都有最优解，或者同时都无最优解. .4 4）对偶问题有可行解，则原问题也有可行解）对偶问题有可行解，则原问题也有可行解. .5 5）原问题有多重解，对偶问题也有多重解）原问题有多重解，对偶问题也有多重解. .6 6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解. .7 7）原问题无最优解，则对偶问题无可行解）原问题无最优解，则对偶问题无可行解. .8 8）对偶问题不可行，原问题可能无界解）对偶问题不可行，原问题可能无界解. .9 9）原问题与对偶问题都可行，则都有最优解）原问题与对偶问题都可行，则都
57、有最优解. .1010）原问题具有无界解，则对偶问题不可行）原问题具有无界解，则对偶问题不可行. .1111）对偶问题具有无界解，则原问题无最优解）对偶问题具有无界解，则原问题无最优解. .1212）若）若X X* *、Y Y* *是原问题与对偶问题的最优解，则是原问题与对偶问题的最优解，则X X*=*=Y Y*.*.本章小结本章小结学习要点：学习要点：1. 熟练掌握对偶问题的转换熟练掌握对偶问题的转换 2. 掌握对偶问题的掌握对偶问题的5个性质个性质 3. 熟练掌握对偶单纯形法的解题思路及求解步骤熟练掌握对偶单纯形法的解题思路及求解步骤求解线性规划的计算机软件举例求解线性规划的计算机软件举例
58、求解线性规划的计算机软件举例求解线性规划的计算机软件举例LINDOLINDO、EXCELEXCELLINDO可以从下面的网址下载：可以从下面的网址下载：WWW.L LINDOLINDO由美国芝加哥大学开发，可求解线性规划和线性由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。整数规划等。其可按自然格式输入模型，使用方便。输入例输入例 ：MAX 2X+3Y ？ST ？4X+9Y9 ？7X+6Y13 ？END ：GO DO RANGE (SENSITIVITY) ANALYSIS? ？Y 可用可用HELP命命令令得到帮助。得到帮助。计算结果说明：计算结果说明：
59、REDUCED COST 为使该变量进基，其价格系数至少应为使该变量进基，其价格系数至少应 增加的数值；增加的数值；SLACK OR SUPLUS 松弛或剩余变量；松弛或剩余变量；DUAL PRICES 影子价格影子价格;ALLOWABLE INCREASE 灵敏度分析中可使最优基不灵敏度分析中可使最优基不 变的系数可增量之上界；变的系数可增量之上界；ALLOWABLE DECREASE 灵敏度分析中可使最优基不灵敏度分析中可使最优基不 变的系数可减量之上界；变的系数可减量之上界；使用使用EXCEL求解线性规划求解线性规划- -进入进入EXCELEXCEL后先在表格的第一列输入变量、约束和目标的名后先在表格的第一列输入变量、约束和目标的名 称，在后面某一列对应位置输入约束和目标的表达式称，在后面某一列对应位置输入约束和目标的表达式( (前加前加 等号提示符等号提示符) )；- -然后在工具中调用规划求解，按提示操作。然后在工具中调用规划求解，按提示操作。（可参看关于使用（可参看关于使用EXCELEXCEL的书，如谢国锋等，的书，如谢国锋等，EXCEL2000EXCEL2000中中文版入门与提高文版入门与提高，清华大学出版社，清华大学出版社，19991999）
