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

《第二章对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《第二章对偶理论与灵敏度分析（85页珍藏版）》请在金锄头文库上搜索。

1、第二章第二章LP的对偶理论与灵敏度分析的对偶理论与灵敏度分析1 1 线性规划的对偶问题线性规划的对偶问题2 2 对偶规划的基本性质对偶规划的基本性质 3 3 影子价格影子价格 4 4 对偶单纯形法对偶单纯形法 5 5 灵敏度分析灵敏度分析对偶问题概念： 任何一个线性规划问题都有一个伴生的线性规划问题，称为其“对偶”问题。 对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。 对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。 第一节第一节 线性规划的对偶问题线性规划的对偶问

2、题例例1 穗羊公司的例子III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32一、对偶问题的提出一、对偶问题的提出问问问问公司应每天制造两种产品各多少件，使获取的利公司应每天制造两种产品各多少件，使获取的利公司应每天制造两种产品各多少件，使获取的利公司应每天制造两种产品各多少件，使获取的利润最大？润最大？润最大？润最大？生产计划问题（LP1）现在我们从另一个角度来考虑这个问题。假如有另现在我们从另一个角度来考虑这个问题。假如有另外一个新公司要求租用穗羊公司的资源，那么外一个新公司要求租用穗羊公司的资源，那么新公新公新公新公司愿意以多大的代价才能使穗羊出让自己

3、所拥有的司愿意以多大的代价才能使穗羊出让自己所拥有的司愿意以多大的代价才能使穗羊出让自己所拥有的司愿意以多大的代价才能使穗羊出让自己所拥有的生产资源？生产资源？生产资源？生产资源？资源定价问题（LP2）设设y1,y2和和y3分别表示出让资源分别表示出让资源A，B和调试和调试工序的单价，则该公司同意出让的条件将工序的单价，则该公司同意出让的条件将是是同意出让生产产品同意出让生产产品I I的资源的资源同意出让生产产品同意出让生产产品IIII的资源的资源购买者希望用最少的代价获得这些资源购买者希望用最少的代价获得这些资源，因此因此这样得到一个新的线性规划问题这样得到一个新的线性规划问题这样从两个不同

4、的角度来考虑同一种资源的最大这样从两个不同的角度来考虑同一种资源的最大利润（最小租金）的问题，所建立起来的两个线利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。而另外一个叫对偶问题。 如果我们把求目标函数最大值的线性规划问题看成如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。偶问题。下面来研究这两个问题在数学模型上的关系。 1. 求求目标函数最大值的线性规划

5、问题中有目标函数最大值的线性规划问题中有n 个变个变量量 m个约束条件，它的约束条件都是小于等于不等式。个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，而其对偶则是求目标函数为最小值的线性规划问题，有有m个变量个变量n个约束条件，其约束条件都为大于等于个约束条件，其约束条件都为大于等于不等式。不等式。 2. 原问题的目标函数中的变量系数为对偶问题中原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的约束条件的右边常数项，并且原问题的目标函数中的第的第i个变量的系数就等于对偶问题中的第个变量的系数就等于对偶问题中的第i

6、个约束条个约束条件的右边常数项。件的右边常数项。 3. 原原问题的约束条件的右边常数项为对偶问题的目问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第标函数中的变量的系数。并且原问题的第i个约束条件个约束条件的右边常数项就等于零对偶问题的目标函数中的第的右边常数项就等于零对偶问题的目标函数中的第i个个变量的系数。变量的系数。 4. 对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A是原是原问题约束问题约束矩阵的转置。矩阵的转置。 设设 则则 二、二、对称形式的对称形式的LP问题与对偶问题的一般形式问题与对偶问题的一般形式定义：定义：满足下列条件的满足下列条件的

7、LP问题称为具有对称形式：问题称为具有对称形式：变量变量：所有变量均具有非负约束：所有变量均具有非负约束约束条件约束条件： 最大化问题最大化问题 所有约束条件都是所有约束条件都是“”型的型的 最小化问题最小化问题 所有约束条件都是所有约束条件都是“”型的型的对称形式的对称形式的LP问题与对偶问题的一般形式为问题与对偶问题的一般形式为对称形式的原问题对偶问题的矩阵形式对称形式的原问题的矩阵形式对称形式的对偶问题的矩阵形式对称形式下的对偶关系对称形式下的对偶关系 项目项目 原问题原问题 对偶问题对偶问题 A b C目标函数目标函数约束条件约束条件决策变量决策变量约束条件系数矩阵约束条件系数矩阵约束

8、条件右端项向量约束条件右端项向量目标函数系数向量目标函数系数向量max z=CX AXb X0约束条件系数矩阵转置约束条件系数矩阵转置目标函数的系数向量目标函数的系数向量约束条件的右端项向量约束条件的右端项向量min w=Y bAY CY 0原问题原问题max z对偶问题对偶问题min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“”型型决策变量决策变量0决策变量决策变量0约束条件约束条件“”型型对称形式的对应关系对偶问题的对偶是原问题，即对偶关系是对偶问题的对偶是原问题，即对偶关系是相互对称的关系相互对称的关系对偶问题的特点对偶问

9、题的特点若原问题目标是求极大化，则对偶问题的目若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然标是极小化，反之亦然原问题的约束系数矩阵与对偶问题的约束系原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵数矩阵互为转置矩阵极大化问题的每个约束对应于极小化问题的极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个一个变量，其每个变量对应于对偶问题的一个约束。约束。 一般线性规划问题的对偶问题2 2、非对称形式下的原问题与对偶问题、非对称形式下的原问题与对偶问题(x(x变变) )2 2、非对称形式下的原问题与对偶问题、非对称形式下的原问题与对偶问题( (方程

10、变方程变) )2、max z = 2 x1 + x2 + 3 x3 + x4 x1 + x2 + x3 + x4 5 s.t. 2x1 - x2 + 3 x3 = - 4 x1 + 2 x3 + x4 1 x1 , x3 0 , x2 , x4无约束无约束练习题：练习题： 1 1、min z = 3 x1 + 2 x2 - 3 x3 + 4 x4 x1 - 2 x2 + 3 x3 + 4 x4 3 s.t. x2 + 3 x3 + 4 x4 - 5 2 x1 - 3 x2 - 7 x3 - 4 x4 = 2 x10 , x2 0 , x3 , x4无约束无约束2 2、非对称形式下的原问题与对偶

11、问题、非对称形式下的原问题与对偶问题( (方程变方程变) )结论：结论：方程对变量方程对变量变量对方程变量对方程正常对正常正常对正常不正常对不正常不正常对不正常变量正常是非负变量正常是非负方程正常看目标方程正常看目标(max =)(max =)对称、非对称形式下的对偶关系原问题原问题（对偶问题）（对偶问题）max z对偶问题对偶问题（原问题）（原问题）min wn个决策变量个决策变量m个约束条件个约束条件n个约束条件个约束条件m个决策变量个决策变量约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型决策变量决策变量0决策变量决策变量0决策变量无约束决策变量无约束决策变量决

12、策变量0决策变量决策变量0决策变量无约束决策变量无约束约束条件约束条件“”型型约束条件约束条件“”型型约束条件约束条件“=”型型原问题对偶问题第二节第二节 对偶问题的基本性质对偶问题的基本性质1 1、对偶问题的对偶问题是原问题、对偶问题的对偶问题是原问题对偶的定义对偶的定义对偶的定义对偶的定义max z=CXs.t. AXb X 0min w=bYs.t. AYCY 0min z = - CXs.t. -AX -bX 0max w = -bYs.t. -AY-CY 0一、单纯形法的矩阵表示一、单纯形法的矩阵表示添加松弛变量XS将XB的系数矩阵化为单位矩阵CB CN 0XB XN XS0 XS

13、bB N I cj-zjCB CN 0CB CN 0XB XN XSCB XB B-1bI B-1N B-1 cj-zj0 CN CBB-1N CBB-1 初始单纯形表迭代后的单纯形表在初始单纯形表中单位矩阵经过迭代后变为基矩阵B的逆在初始单纯形表给出的解中基变量Xs=b,而在迭代后的表给出的解中基变量 XB=B-1b系数矩阵的变化: A, IB-1A, I在初始单纯形表中变量xj的系数为Pj经过迭代后变为Pj,并且Pj=B-1 Pj当B为最优基时，由上表有 CN-CBB-1N0， -CBB-1 0 （1） 因而xB的检验数应写为 CB-CBI=0 （2） 所以（1）、（2）可以改写为 C-C

14、BB-1A0， -CBB-1 0 （3）CBB-1称为单纯形乘子，若令Y=CBB-1， （3）改写为 看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。将此解代入对偶问题，有 w=Yb= CBB-1 b=z若原问题有最优解，这是对偶问题为可行解且有相同的目标值。 迭代后的单纯形表为最终表则该表也同时给出对偶问题的最优解 min w = 5y1+4y2+9y3 6 y2 + y32st. 5 y1 + 2 y2 + y31 y1 , y2 , y3 0 5x 5x2 2 1515 6x 6x1 1+2x+2x2 2 2424 x x1 1+ x+ x2 2 55 x x1 1 ,x,x

15、2 2 0 0max z=3xmax z=3x1 1+2x+2x2 2stst. .对偶变量对偶变量y1y2y3变量变量x1x2 x x1 1 + 2x + 2x2 2 + x+ x3 3 = 5= 5 2x 2x1 1 +x+x2 2 + x+ x4 4 = 4= 4 4x 4x1 1+ 3x+ 3x2 2 + x+ x5 5 = 9= 9 x x1 1 ,x,x2 2 ,x ,x3 3 ,x,x4 4 , x, x5 500 y1 +2 y2 +4 y3 y4 = 32 y1 + y2 +3 y3 y5 = 2 y1 , y2 , y3 , y4 , y5 0原本在对偶关系中，原问题的变量

16、对应着对偶问题原本在对偶关系中，原问题的变量对应着对偶问题的约束条件，原问题的约束条件对应着对偶变量。的约束条件，原问题的约束条件对应着对偶变量。但但在分别添加了松弛变量和剩余变量后，也可以建在分别添加了松弛变量和剩余变量后，也可以建立原问题变量与对偶问题变量之间的对应关系立原问题变量与对偶问题变量之间的对应关系原问题原问题对偶问题对偶问题第第i个约束条件中个约束条件中添加的松弛变量添加的松弛变量第第i个对偶变量个对偶变量第第j个变量个变量第第j个约束条件中个约束条件中添加的松弛变量添加的松弛变量注 上表中我们将松弛变量与剩余变量统称为松弛变量推论推论1 1：原问题任一可行解的目标函数值是其对

17、偶原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。解的目标函数值是起原问题目标函数值的上界。推论推论2 2： 原问题原问题 对偶问题对偶问题 无界解无界解 无可行解无可行解 无可行解无可行解 无界解无界解2 2、弱对偶性、弱对偶性如果如果 是原问题的可行解，是原问题的可行解， 是其对偶问题的是其对偶问题的可行解，则：可行解，则：推论推论3 3：原问题原问题 对偶问题对偶问题 无可行解无可行解 + + 可行解可行解 对偶问题有无界解对偶问题有无界解 可行解可行解 + + 无可行解无可

18、行解 原问题有无界解原问题有无界解3 3、最优性、最优性如果如果 是原问题的可行解，是原问题的可行解， 是其对偶问题的可是其对偶问题的可行解，且有行解，且有 则：则： 是原问题和对是原问题和对偶问题的最优解。偶问题的最优解。4 4、强对偶性强对偶性X X* *、Y Y* * 分别是原问题和对偶问题的最优解，则：分别是原问题和对偶问题的最优解，则：5 5、互补松弛性、互补松弛性 max z = CX s.t. AX + XS = b X, XS0min w = bYs.t. AY - YS = C Y, YS0max z = CXs.t. AX b X 0min w = bYs.t. AY C

19、Y0对偶对偶引进松弛变量引进松弛变量引进松弛变量引进松弛变量X YS = 0 , Y XS = 0互补松弛关系互补松弛关系X , XsY , Ys互补松弛性的另一种表述互补松弛性的另一种表述在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则该约束条件中松弛变量等于零;反之若一个约束条件中松弛变量非零,则其对应的对偶变量为零。互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值非零,则其对应的约束条件取等式;反之若一个约束条件为严格的不等式,则其对应的对偶变量为零例原原原原问题问题问题问题对偶问题对偶问题对偶问题对偶问题将原将原将原将原问题最优解问题最优解问题最优

20、解问题最优解X*=(2,2,4,0)X*=(2,2,4,0)代入原问题约束条件中得代入原问题约束条件中得代入原问题约束条件中得代入原问题约束条件中得第一个约束条件：第一个约束条件：第一个约束条件：第一个约束条件：2+6=82+6=8，为等式，为等式，为等式，为等式第二个约束条件：第二个约束条件：第二个约束条件：第二个约束条件：4+2=64+2=6，为等式，为等式，为等式，为等式第三个约束条件：第三个约束条件：第三个约束条件：第三个约束条件：2+4=62+4=6，为等式，为等式，为等式，为等式第四个约束条件：第四个约束条件：第四个约束条件：第四个约束条件：2+2+492+2+40, 得而由x2=

21、20, 得而由x3=40, 得于是得到方程组得对偶问题最优解为注：原问题与对偶问题最优目标函数值都是 z*=4+8+4=16 三、对偶问题的经济解释三、对偶问题的经济解释1 1、原问题是利润最大化的生产计划问题、原问题是利润最大化的生产计划问题单位产品的利润（单位产品的利润（元元/ /件）件）产品产量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/ /件）件）剩余的资源（剩余的资源（吨）吨）消耗的资源（吨）消耗的资源（吨）2 2、对偶问题、对偶问题资源限量（吨）资源限量（吨）资源价格（元资源价格（元/ /吨）吨）总利润（元）总

22、利润（元） 对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格（种资源的影子价格（Shadow Price）原、对偶问题都取得最优解时原、对偶问题都取得最优解时, ,最大利润最大利润max z=min wmax z=min w3 3、资源影子价格的性质、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子 价格一

23、定等于价格一定等于0 0n市场价格市场价格 影子价格：影子价格： 卖出此项资源卖出此项资源y1y2ym4 4、产品的机会成本、产品的机会成本增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源机会成本机会成本利润利润差额成本差额成本5 5、产品的差额成本（、产品的差额成本（Reduced CostReduced Cost）差额成本差额成本 = = 机会成本机会成本 - - 利润利润0yyyyyycyyayayacyyayayacyyayaya. t . sybybybwminnm2m1mm21nnmmmn2n21n122mm2m2221121

24、1mm1m221111mm2211 = =- -+ + += =- -+ + += =- -+ + + + += =+ + + + + + +LLLLLLLLLLLL5 5、互补松弛关系的经济解释、互补松弛关系的经济解释在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产影子价格影子价格 是一个向量，它的分量表示最优目标值随相应资是一个向量，

25、它的分量表示最优目标值随相应资源数量变化的变化率。源数量变化的变化率。 若若x x* *, ,y y* * 分别为（分别为（LPLP）和（和（DPDP）的最优解，的最优解， 那么，那么， c cT Tx x* * = = b bT Ty y* * 。 根据根据 f f = =b bT Ty y* *= =b b1 1y y1 1* *+ +b b2 2y y2 2* *+ + +b bm my ym m* * 可知可知 f f/ / b bi i = =y yi i* * y yi i* * 表示表示 b bi i 变化变化1 1个单位对目标个单位对目标 f f 产生的影响，称产生的影响，称

26、y yi i* * 为为 b bi i的的影子价格。影子价格。 注意：注意：若若 B B 是最优基，是最优基， y y* * = ( = (B BT T) )-1-1 c cB B 为影子价格向量。为影子价格向量。第三节 影子价格影子价格的经济含义影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价. 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。 （2 2）影影子子价

27、价格格表表明明资资源源增增加加对对总总效效益益产产生生的的影影响响。根根据据推推论论“设设x x0 0和和y y0 0分分别别为为原原规规划划（P P）和和对对偶偶规规划划（D D）的的可可行行解解，当当cxcx0 0= =b bT Ty y0 0时时，x x0 0、y y0 0分分别别是是两两个个问题的最优解问题的最优解”可知，在最优解的情况下，有关系可知，在最优解的情况下，有关系 因因此此，可可以以将将z z* *看看作作是是b bi i, ,i i=1,2=1,2， , ,m m的的函函数数，对对b bi i求偏导数可得到求偏导数可得到 这这说说明明，如如果果右右端端常常数数增增加加一一

28、个个单单位位，则则目目标标函数值的增量将是函数值的增量将是 影影子子价价格格反反映映了了不不同同的的局局部部或或个个体体的的增增量量可可以以获获得得不不同同的的整整体体经经济济效效益益。如如果果为为了了扩扩大大生生产产能能力力，考考虑虑增增加加设设备备，就就应应该该从从影影子子价价格格高高的的设设备备入入手手。这这样样可可以以用用较较少的局部努力，获得较大的整体效益。少的局部努力，获得较大的整体效益。式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi的意义代表在资源最优利用的条件下对第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的

29、估价，为区别起见，称为影子价格影子价格。设 和 分别是原问题和对偶问题的最优解，则由对偶性质，有第四节第四节 对偶单纯形法对偶单纯形法按按对偶问题与原问题之间的关系，对最大对偶问题与原问题之间的关系，对最大化问题，在用单纯形法求解原问题时，最化问题，在用单纯形法求解原问题时，最终表不但给出了原问题的最优解，而且其终表不但给出了原问题的最优解，而且其检验数的相反数就是对偶问题的最优解。检验数的相反数就是对偶问题的最优解。单纯形法求解的基本思路单纯形法求解的基本思路基基可行解可行解检验数非正检验数非正保持解的可行性保持解的可行性对偶单纯形法的基本思路对偶单纯形法的基本思路对偶问题基可行解对偶问题基

30、可行解（检验数非正）（检验数非正）原原问题基可行问题基可行解解保持对偶问题解的保持对偶问题解的可行性（检验数非可行性（检验数非正正（对偶问题可行解）（对偶问题可行解） 对偶单纯形法的基本思想对偶单纯形法的基本思想 对对偶偶单单纯纯形形法法的的基基本本思思想想是是：从从原原规规划划的的一一个个基基本本解解出出发发，此此基基本本解解不不一一定定可可行行，但但它它对对应应着着一一个个对对偶偶可可行行解解（检检验验数数非非正正），所所以以也也可可以以说说是是从从一一个个对对偶偶可可行行解解出出发发；然然后后检检验验原原规规划划的的基基本本解解是是否否可可行行，即即是是否否有有负负的的分分量量，如如果果

31、有有小小于于零零的的分分量量，则则进进行行迭迭代代，求求另另一一个个基基本本解解，此此基基本本解解对对应应着着另另一个对偶可行解（检验数非正）。一个对偶可行解（检验数非正）。 如果得到的基本解的分量皆非负则该基如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。的可行解时，便得到

32、原规划的最优解。对偶单纯形法在什么情况下使用：对偶单纯形法在什么情况下使用： 应用前提：应用前提：有一个基，其对应的基有一个基，其对应的基满足满足: : 单纯形表的检验数行全部非正（对偶单纯形表的检验数行全部非正（对偶可行）；可行）； 变量取值可有负数（非可行解）。变量取值可有负数（非可行解）。 注：注：通过矩阵行变换运算，使所有相应变通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。量取值均为非负数即得到最优单纯性表。对偶单纯形法计算步骤对偶单纯形法计算步骤适应于求解这样的适应于求解这样的LP问题：问题：标准化后不标准化后不含初始基变量，但将某些约束条件两端含初始基变量，但

33、将某些约束条件两端乘以乘以“-1”后，即可找出初始基变量。后，即可找出初始基变量。要求：要求：初始单纯形表中的检验数满足最初始单纯形表中的检验数满足最优性条件优性条件对满足上述条件的对满足上述条件的LP问题，对偶单纯形法的问题，对偶单纯形法的步骤是：步骤是：旋转运算。然后回到第旋转运算。然后回到第2步。步。作出初始单纯形表（注意要求）作出初始单纯形表（注意要求）检查检查b列的数据是否非负，若是，表中已经列的数据是否非负，若是，表中已经给出最优解给出最优解；否则转下一步；否则转下一步确定换出变量确定换出变量：取：取b列最小的数对应的变量列最小的数对应的变量为换出变量为换出变量确定换入变量确定换入

34、变量：用检验数去除以换出变量行：用检验数去除以换出变量行的那些对应的负系数，在除得的商中选取其的那些对应的负系数，在除得的商中选取其中最小者对应的变量为换入变量中最小者对应的变量为换入变量例例 用对偶单纯形法求解如下的用对偶单纯形法求解如下的LP问题问题化成标准形式将各约束条件两端同乘“-1”得用对偶单纯形法求解得最优解：最优解：最优解：最优解：x x1 1=0, x=0, x2 2=1/4, x=1/4, x3 3=1/2, x=1/2, x4 4=0, x=0, x5 5=0=0最优目标函数值：最优目标函数值：最优目标函数值：最优目标函数值：w*=-8.5w*=-8.5（z*=8.5z*=

35、8.5）注：通常很少直接使用对偶单纯形法求解线性规划问题。单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法对偶单纯形法的适用范围对偶单纯形法的适用范围 对对偶偶单单纯纯形形法法适适合合于于解解如如下下形形式式的的线线性性规规划划问题问题 在在引引入入松松弛弛变变量量化化为为标标准准型型之之后后，约约束束等等式式两两侧侧同同乘乘-1-1，能能够够立立即即得得到到检检验验数数全全部部非非正正的的原原规规划划基基本本解解，可

36、可以以直直接接建建立立初初始始对对偶偶单单纯纯形形表表进进行求解，非常方便。行求解，非常方便。 对对于于有有些些线线性性规规划划模模型型，如如果果在在开开始始求求解解时时不不能能很很快快使使所所有有检检验验数数非非正正，最最好好还还是是采采用用单单纯纯形形法法求求解解。因因为为，这这样样可可以以免免去去为为使使检检验验数数全全部部非非正正而而作作的的许许多多工工作作。从从这这个个意意义义上上看看，可可以以说说，对对偶偶单单纯纯形形法法是是单单纯纯形形法法的的一一个个补补充充。除除此此之之外外，在在对对线线性性规规划划进进行行灵灵敏敏度度分分析析中中有有时时也也要要用用到到对对偶单纯形方法，可以

37、简化计算。偶单纯形方法，可以简化计算。第五节第五节 灵敏度分析灵敏度分析 将讨论将讨论LP问题中的参数问题中的参数 中有中有一个或几个发生改变时问题的最优解会有什么一个或几个发生改变时问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变时，问题的最优解不变 在在生生产产计计划划问问题题的的一一般般形形式式中中，A代代表表企企业业的的技技术术状状况况，b代代表表企企业业的的资资源源状状况况，而而C代代表表企企业业产产品品的的市市场场状状况况，在在这这些些因因素素不不变变的的情情况况下下企企业业的的最最优优生生产产计计划和最大利润

38、由线性规划的最优解和最优值决定。划和最大利润由线性规划的最优解和最优值决定。 在在实实际际生生产产过过程程中中，上上述述三三类类因因素素均均是是在在不不断断变变化化的的，如如果果按按照照初初始始的的状状况况制制订订了了最最佳佳的的生生产产计计划划，而而在在计计划划实实施施前前或或实实施施中中上上述述状状况况发发生生了了改改变变，则则决决策策者者所所关关心心的的是是目目前前所所执执行行的的计计划划还还是是不不是是最最优优，如如果果不不是是应应该该如如何何修修订订原原来来的的最最优优计计划划。更更进进一一步步，为为了了防防止止在在各各类类状状况况发发生生时时，来来不不及及随随时时对对其其变变化化作

39、作出出反反应应，即即所所谓谓“计计划划不不如如变变化化快快”，企企业业应应当当预预先先了了解，当各项因素变化时，应当作出什么样的反应。解，当各项因素变化时，应当作出什么样的反应。 当系数A，b，C发生改变时，目前最优基是否还最优？ 为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化目标系数C变化 基变量系数发生变化； 非基变量系数发生变化；右端常数b变化增加一个变量增加一个约束技术系数A发生变化 CB XB cjCBCN xj b XBTXNTCBTXBB-1b B-1BB-1N- CB B-1b CB- CB B-1BCN- CB B-1N若B是最优基，则

40、最优表形式如下灵敏度分析总是在最优表上进行 研究的思路将将个别参数的变化直接在计算得到的最个别参数的变化直接在计算得到的最终单纯形表中反映出来，这样就不需要终单纯形表中反映出来，这样就不需要从头计算，而从头计算，而直接检查在参数改变后最直接检查在参数改变后最终表有什么改变终表有什么改变，若仍满足最终表的条，若仍满足最终表的条件，则表中仍给出最优解，否则从这个件，则表中仍给出最优解，否则从这个表开始进行迭代求改变以后的最优解。表开始进行迭代求改变以后的最优解。灵敏度分析的步骤灵敏度分析的步骤将将参数的改变计算反映到最终表上来。具体计参数的改变计算反映到最终表上来。具体计算公式可以使用算公式可以使

41、用检查原问题是否仍为可行解检查原问题是否仍为可行解检查对偶问题是否仍为可行解检查对偶问题是否仍为可行解对检查情况按下表进行处理对检查情况按下表进行处理原原问题问题对偶问题对偶问题结论或继续计算步骤结论或继续计算步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优基不变可行解可行解非非可行解可行解用用单纯形法继续迭代求最优单纯形法继续迭代求最优解解非非可行解可行解可行解可行解用用对偶单纯形法继续迭代求对偶单纯形法继续迭代求最优解最优解非非可行解可行解非非可行解可行解引进人工变量，编制新的单引进人工变量，编制新的单纯形表重新计算纯形表重新计算1.价值系数Cj变化的灵敏度分析目标函

42、数系数目标函数系数cj的变化，仅仅带来检验数的变化，仅仅带来检验数 的变的变化，对最优单纯形表右边向量化，对最优单纯形表右边向量B-1b和系数矩阵和系数矩阵B-1N没有影响。没有影响。 首先计算变化后的首先计算变化后的 ，基变量检验数，基变量检验数 。如果所有检验数仍然满足非正数，则最优解不变，。如果所有检验数仍然满足非正数，则最优解不变，否则继续进行迭代。否则继续进行迭代。例：穗羊公司根据市场调查，例：穗羊公司根据市场调查，（1）发现产品）发现产品II的市场价需要下调的市场价需要下调1万，万，产品产品I、II的单位利润变为（的单位利润变为（3，1），该），该公司的最优生产计划有何改变；公司的

43、最优生产计划有何改变；（2）若产品）若产品II的利润不变，则产品的利润不变，则产品I的利润的利润在什么范围变化时，该公司的最优生产在什么范围变化时，该公司的最优生产计划不发生变化计划不发生变化原原最终单纯形表最终单纯形表（1）改变后）改变后新的最优解为：最优目标函数值为：（2）改变后）改变后为使表为使表中的解仍为最优解必须中的解仍为最优解必须因此产品因此产品II的利润变化范围为的利润变化范围为2. 资源常数bj变化的灵敏度分析当当b发生改变时，对检验数、系数矩阵没有影发生改变时，对检验数、系数矩阵没有影响，但对基变量的取值有影响。响，但对基变量的取值有影响。 计算计算 ，如果，如果 保持非保持

44、非负，则原最优解不改变，；否则进行对偶单负，则原最优解不改变，；否则进行对偶单纯形迭代。纯形迭代。例：在第一章的例例：在第一章的例1中中 资源资源B的使用量可以增加到的使用量可以增加到5，分析公司最，分析公司最优计划的变化；优计划的变化；（1）b由由(5，4，9)T 变为变为(5，5，9)T 后，相应地最终表后，相应地最终表中中b列的数据变为列的数据变为3.3.增加一变量增加一变量x xj j ：设新产品设新产品的产量为的产量为x x6 6件件例例 该公司研发了新产品该公司研发了新产品IIIIII，单位产品对资单位产品对资源的消耗为（源的消耗为（3 3，0 0，2 2），该产品的利润为，该产品

45、的利润为2 2万元，原生产计划是否改变？万元，原生产计划是否改变？假设该产品的消耗系数为假设该产品的消耗系数为P Pj j，单位利润为单位利润为c cj j计算该产品的机会成本计算该产品的机会成本YYPj。 如果机会成本小于单位利润，则不生产；否则，如果机会成本小于单位利润，则不生产；否则，在原终表里增加新列在原终表里增加新列B-1 Pj，并进行迭代。并进行迭代。产品产品III的机会成本的机会成本=YPj=（0，1/2,1/2）(3,0,2)=1最优解：最优解：X = ( 2 , 0 , 3/2 , 0 , 0 ，1/2 ) z = 7利用Excle求解LP问题，以P45.7(2)为例变量，已经赋了初值目标函数值约束条件右端值其他专业软件：Lindo与Lingo，WinQSB例如Lingo，启动Lingo后，按图中的方式输入模型，然后点击求解的图标 。就可得到所需的最优解。