第6章 单纯形法的灵敏度分析与对偶2008.ppt

1、第六章单纯形法的灵敏度分析和对偶，线性规划的单纯形表对偶单纯形法的灵敏度分析，第六章单纯形法的灵敏度分析和对偶，如何利用最优单纯形表进行灵敏度分析。单纯形表-求解结果：第1节单纯形表的灵敏度分析.目标函数中变系数Ck的灵敏度分析现在，Ck的灵敏度分析应采用单纯形表法。由于目标函数变量分为基本变量和非基本变量，因此将其分为两类进行讨论。1.xK不是最终单纯形表中的基本变量。2.xK不是最终单纯形表中的基本变量。第一节单形表的灵敏度分析。1.xK不是最终单纯形表中的基本变量。约束(方程)系数的增广矩阵只是其自身行在迭代中的初等变换，与CK无关，所以当CK变成CKCK时，其系数的增广矩阵在最终的单纯

2、形表中不变，并且由于xK是非基本变量，所以基本变量的目标函数的系数不变，即CB不变，所以可以看出ZK不变，而CK变成了CKCK。这时，CKZK变成了ckckckzk=CKK。使原来的最优解仍然是最优解，只是ck0，也就是CK K。第一节单形表的灵敏度分析。在最终的单纯形表中，xK是基本变量。约束(方程)系数的增广矩阵与CK无关，因此当CK变成CKCK时，其系数的增广矩阵在最终的单纯形表中不变，但基本变量在目标函数的系数CB中变化，Zj也是如此。变化规律是：目标函数：maxz=50x1100x2，x1 x2300，2x1x2400，x10，x20，S.T，x2250，maxz=50x1100x2

3、，x1x2s1=300，2x1x2s2=400，x10，x20 X2 s3=250，首先，线性规划问题的基本概念、基础和基本解是：maxz=50x 100 x20s 10s 20s 3，1x 1x 1x 21s 10s 20 ()首先分析非基本变量s1: c3 3，因为它是非基本变量，所以应用公式(1)，当C3 -3时，最优解保持不变； 众所周知，3=-50和C3(50)=50；C=c C=0 50=50最佳解不变。(2)基本变量系数分析的重新分析：A11=1，A12=0，A13=1，A14=0，A15=-1从表中得到。例如，对基本变量X1的C1系数进行灵敏度分析：单纯形表灵敏度分析，所以ma

4、x-50C1 min50，左右半径保证区间。也就是说，当x1的目标函数系数C为：50-50=c1 L C=C1 C1 c1 R=50 50，0C100时，最优解保持不变。* * * * * * * * * * * * * * * * * * * *最佳解决方案如下* * * * * * * * * * * * * * * * * * * * * * * * 目标函数的最优值为3360 27500变量最优解差值-剩余变量的双重价格1 0 50 2 50 0 3 0 50目标函数系数范围：变量下限电流值上限常数范围：约束下限电流值上限1 250 300 325 2 350 400无上限3 200

5、250 300， 在步骤2中发现的线性规划最佳值目标函数值1) 27500.00可变值降低成本X1 50.0000000 0.000000 X2 250.000000.0000000行松弛或盈余双重价格2)0.0000000 50.000000003)50.0000000000.0000000000000000000000000000000000000000000000000000000000000000000000 基于单纯形法的约束方程右常数灵敏度分析，2。约束方程右常数的灵敏度分析，从上一页的表格，知道右系数bj的灵敏度，常数对偶价格和bj的可变范围，我们需要从单形表的数据分析：Zj的值

6、就是对偶价格。然后，当bj变成bj b时，非基本变量的测试次数不会改变，但是基本变量的测试次数会改变。bk的允许范围是：2.约束方程右侧常数的灵敏度分析。然后，当br更改为br br时，非基本变量的检查号将会改变。br的允许范围是：初始单纯形表。现在，应该进行b1的敏感性分析。首先，找出b1的列元素：它是S1。因为可逆矩阵b的第一列是S1=(1，0)t max-50/1=-50b1min-50/-2=25-50b125，那么，300-50b=b b1 300 25 250b=b b1 325练习：分析B3，3。约束方程系数矩阵a的灵敏度分析技术系数aij对线性规划最优解结构的影响是复杂的。从下

7、面的公式可以看出，非基本变量的检验数和基本变量XB的值与技术系数有关。一般来说，联合开展活动的技术系数的敏感性分析分为以下三类：(1) AIJ对应基本变量，所有的商业智能资源已经用完；(2) AIJ对应基本变量，但商务智能资源没有用完；(3) AIJ对应非基本变量，且所有商业智能资源均已用完或未用完；3.约束方程系数矩阵A的灵敏度分析，线性规划最优解的结构不变的条件是(1)联合执行活动对应基本变量，且资源毕已全部用完，则技术系数在联合执行活动=0的范围内变化；(2)共同执行活动对应于基本变量，但资源bi没有用完，则技术系数变化范围为：aijXn i/xj (3)共同执行活动对应于非基本变量，资

8、源bi用完或没有用完。我们将在以下两种情况下讨论它：(A)aij0，它不会破坏最优解。(二)aij0，使原线性规划的最优解不变：必须保证非基本变量的检验次数仍小于0，即cj-Zj0，线性规划的对偶问题在第二节，一个工厂正计划安排I和II产品，I可以得到50元，II可以得到100元。如何安排生产和获得最大化？模型，目标：max z=50 x1 100 x2 S.t. x1 x2=0，假设有一个公司想租工厂设备，工厂有两种方式来赚取利润，一种是自己生产，另一种是租用设备资源。做你自己的模型。所以，如果你租了它，如何建立模型？设备价格为ay1、by2和cy3然后，目标：分钟f=300 y1 400y

9、 2250y 3s . t . Y12 Y2=50 y1 y3100 y 1，Y2，Y3=0，目标：分钟f=300 y1 400y 2250y 3s . t . Y12 Y2=50 y1 y3100 y 1，Y2，Y3目标：max z=50 x1 100 x2 S.t. x1 x2=0，原始问题，双重问题，1。目标函数最大化问题有n个变量和m个约束，所有约束都是小于或等于的不等式；对偶性是m个变量，n个约束和不等式。2。原问题的目标函数系数c是约束B ci=bi 3。原始问题的右系数b成为对偶问题的目标系数c，bi=ci 4。对偶问题的约束系数矩阵a位于、变换示例：最大f=3x 14 x26

10、x34 x22 x3-3x 4353 x1x 25 x36 x445 x1，x2，x3，x40，最小g(y)=35 y1 45 Y2 1 3 Y2 34 y1 42 y15 Y2 6-3y 1 6 Y2 4 y1，y2 0，目标：min f=300 y1400 Y2 2250 y3 s . t . y1 2250 y1 2311 S2=0，a1=0，f的最大值为-27500，即目标f的最小值为：27500 A，设备租金为50元，设备租金为0元，设备租金为50元。2。任何形式的双重问题Max Z=3 x1 4x 2 6x 3s . t . 2x 1 3 x2 6x 3440 6x 1-4x 2-

11、x3 100 5x 1-3 x2 x3=200 x 1，x2，x3 0，2。任何形式的双重问题Max Z=3 x1 4x 2 6x 3s . t . 2x 1 3 x2 6x 3440-6x 1 4x 2 x3-100 5x 1-3 x2 x3 200 5x 1-3 x2 x3 200 x1，x2，x3 0，5x1-3x2 x3=200，Max Z=3 x1 4x 2 6x 3s . t . 2x 1 3 x2 6x 3440-6x 1 4x 2 x3 3-100 5x 1-3 x2 x3 200-5x 1 3x 2-x3 3-200 x1任何形式的对偶问题，原问题的对偶问题是min F=440 y1-100 y2200 y3-200 y4 S . t . 2 y1-6y 25 y3-5y 43 y3-3y 46 y3-y46 y1，Y2，Y40练习：最大f(x)=4x 15 x2 s . t . 3 x1 2x 220 4x 1-3 x2 10 x1x 2=5x 20，x1为正或负。练习转换：最大f(x)=4x 11-4x 12 5x 2s . t . 3x 11-3x 12 2x 220 4x 11-4x 12-3 x2 10x 11-x12x 2=5x 11，x12，x20，练习转换：最大f(x)=4x 11-4x