管理运筹学6单纯形法的灵敏度分析与对偶1.ppt

1、1、第6章单纯形法的灵敏度分析和对偶、1单纯形表的灵敏度分析2线性计划的对偶问题3对偶计划的基本性质4对偶单纯形法、2、1单纯形表的灵敏度分析、1、目标函数中的变量Ck系数灵敏度分析1 .在最终的单纯形表中X k不是基本变量， 约束方程式的系数放大矩阵在反复中只有本身的行的初等变换与Ck没有关系，所以当Ck变为Ck时，在最终单纯形表中系数的放大矩阵不变，X k不是基变量，所以基变量的目标函数的系数不变，即CB不变，Zk也不变，只有Ck是Ck 此时，K=Ck-Zk成为Ck Ck- Zk=K Ck。 为了使原来的最佳解保持最佳解，仅需要Ckk0，即，ck的增量Ck- K。 在最终的简单表中，当X

2、k的基变量从Ck变到Ck时，在最终的简单表中，约束方程式的放大矩阵不改变，但是当基变量的目标函数的系数CB改变时，ZJ (j=1，2，2，n )也一般地改变，因此假定CB=(CB1，CB2) 的双曲正切值。 的双曲正切值。 其中，Ck、CBm、CB为=(CB1、CBM2)。 的双曲正切值。 的双曲正切值。 Ck Ck、CBm、ZJ=(CB1、CB2)。 的双曲正切值。 的双曲正切值。 Ck、CBm)(a1j、a2j、aKj、amj) ZJ=(CB1、CB2)。 的双曲正切值。 的双曲正切值。 Ck Ck、CBm)(a1j、a2j、aKj、amj)=ZJ Ck aKj、3、1根据单纯形式表的灵敏

3、度分析，检测常数J (J=1,2、2、2、m )为j，可知J=CJ-ZJ=J CK aKj。 为了使最佳解不变，在J K的情况下，j=0，4，1单纯形表的灵敏度解析，例如目标函数： Max z=50X1 100X2制约条件： X1 X2300 2X1 X2400 X2250 X1，X20最佳单纯形表如下所示，5，1单纯形表的灵敏度解析，非基本变量S1的这里，由于3=-50，所以在c3的增量c50中，最佳解不变化。 对基变量x1的目标函数的系数c1进行灵敏度分析。 在a1、a12、a13、a14、a15中，除了知道a11和a13大于0，a15小于0以外一样。 由此可知，当-50c150时，即x1

4、的目标函数c1是0c1100时，最佳解不会改变。 在最终的单纯形表中，使用C1 (而不是原始的C1=50 )计算表、6、1的单纯形表的灵敏度分析，从3.0得到-c10，即c10，并且从5.0得到c1100。 如果c1的值超过该范围，则检测常数必然大于0，可以通过重复获得新的最佳解。7、1增加了单纯形表的灵敏度分析、2、制约条件的灵敏度分析，在原线性规划中增加了制约条件时，首先将原问题的最优解的变量值代入新的制约条件，说明如果满足则新的条件不会成为制约，因此原最优解不变。 否则，将新的制约追加到原来的最终单纯形表中进一步解决。 以下，以第三章例1为例进行说明。 /该工厂位于设备台上时，产品材料a

5、、b除了对该工厂的生产有限制外，对电力供给也有限制。 最高供电量为5000度，生产产品需要1.0电力，生产产品需要3.0电力。 你在这个时候试析这个工厂获得最大利益的生产排程吗？8，1单纯形表的灵敏度分析，解：将原问题的最佳解，=5.0，=250代入电力使用量的制约条件，则为1050 30250=500 75005000，因此原问题的最佳解不是本问题的最佳解。 在电力使用量的限制条件中添加缓和变量S4得到：把这个限制条件添加到原来的最终单纯形表中，S4为基本变量，表如下：9，1单纯形表的灵敏度解析，因为上表中的X1，X2不是单位矢量，进行行的线性变换，将上表中的S4行的限制设置为：在上式的两侧

6、将上表中的S4行替换为上式，由下表：1.0、1单形表的灵敏度分析、1.1、1单形表的灵敏度分析、上表可知，最佳解是，该工厂施加使用电量后的最佳生产排程为产品生产140件、产品生产120件。从1.2、1单纯形表的灵敏度分析、3、约束方程的常数项灵敏度分析上的表可知，各松弛变量的值正好等于相应变量的对偶价格。 最佳解中S2=50为基变量，即原料a 5.0的基计程仪柱也没有用完，再增加a原料利润就没有上升，a的对偶价格是0。 对应于作为基本变量的缓和变量的制约条件的对偶价格是0。1.3，1从单纯形表的灵敏度分析可以看出，对于以上问题，如果设备台时间限制，其缓和变量以目标函数从0变为z3=5.0，即，

7、当前的剩馀台时间设备从盈利性变为5.0源，如有希望在5.0源购买设备的人，我们可以为生产、产品提供所有的等号以上的约束，添加剩余变量作为标准类型。 此时，该制约条件的对偶价格与该剩余变量有关。 这应该是限制条件的对偶价格取值的反对数，因为这不是改善而是特别“恶化”。 在包含等号的制约条件中，该制约条件的对偶价格与该制约方程式的人工变量有关。 其制约条件的对偶价格等于该制约方程式的人工变量的值。 1.4，下表显示了从最终单纯形表中，对于不同的制约类型的对偶价格的值。 从对偶价格的定义可知，对偶价格为正时改善目标函数的值，对偶价格为负时使目标函数向与最优化相反的方向前进。 其次，研究右端的bj变化

8、时，对偶价格在哪个范围内不变化。 由于bj的变化不会影响系数矩阵的反复，所以最终简单的表的系数矩阵不会变化。 由此可知，当bj变化时，用于使原化学基不变化的基本可行解仍为可行解，也就是说，求出的化学基变量的值必须大于0。 所谓不改变对偶价格的bj的变化范围，是指不改变其最佳解的所有基本变量，得到的最佳解仍然可能的bj的变化范围。1单形表的灵敏度解析、1.5、1单形表的灵敏度解析、bj的第k项bK变化时，即原来的最初的单形表的b向量成为b向量、1.6、1单形表的灵敏度解析，在最终单形表中，基变量XB的解成为使XB成为可能的解，仅将上述式的右边设为0即可求出、1.7、1单纯形表的灵敏度分析，在第二

9、章例1中用最终单纯形表对bj进行了灵敏度分析。 最终的单纯形表如下： 1.8、1单纯形表的灵敏度分析，我们对b1进行了灵敏度分析。 由于第一约束方程中包含松弛变量S1，所以实际意义是设备台小时数的对偶价格不变，全部设备台小时数在250和325之间变化，设备台小时数的对偶价格不变，全部设备台小时数可以记述为5.0源。 1.9、1简单形表的灵敏度分析、3、约束方程系数矩阵a的灵敏度分析分为以下两种情况进行讨论。 在第一个单纯形表的变量Xk的系数列Pk变化为Pk并重复之后，在最终的单纯形表Xk中不是基本变量。 由于简单形表的迭代是约束方程的扩大矩阵的行变换，所以Pk变为Pk只影响最终简单形表的第k列

10、的数据，包含Xk的系数列、Zk和k的最终简单形表的Xk的系数列变为B-1Pj，Zk变为CBB-1Pk，新的校验数k=CK-CB-1 如果是k0，则原来的最佳解还是最佳解。 如果是k 0，则连续迭代求最佳。 例以第二章例1为化学基，已知该厂除生产、品种外，目前试制全新产品，生产产品，需要一台设备时，消耗a原料0.5公斤。 b原料是1.5公斤，收益是150元，那个工厂应该生产多少产品？解：这是增加新变量的问题。我们可以认为这是变量X3初始表的系数列改变的问题。 假设在2.0，1的简单表的灵敏度分析，接着是2.1，1的简单表的灵敏度分析，例如例题中产品的流程构造得到了改善，生产1个产品需要1.5台设

11、备，消费原料a为2kg，原料b为1kg，每产品的利润为160元，询问是否修改该工厂的生产排程。 解：首先求出X3最终表中的系数列，进行2.2、1单形表的灵敏度解析，其次有新的反复S3进制化学基，进行2.3、1单形表的灵敏度解析，从下一页可知该规模的最佳解X1=0、X2=0、S1=0、S2=0、S3=50、X3=200，此时也就是说，这个工厂的新生产排程不生产，生产产品，就能生产200个产品，最大收益32000元。2.4、1简单形表的灵敏度分析、2 .初始表中变量XK的系数PK变化为PK，经过反复，最终表中XK为基变量的情况下，原来的最佳解的可行性和最佳解有可能被破坏，问题非常复杂，一般不修正元

12、表而直接计算。 2.5，所有线性规划问题都有与其密切相关的线性规划问题，我们称之为原问题，另一个称为对偶问题。 例题1某工厂在计划期间内安排了两种产品，生产公司产品所需的设备a、b、c台如表所示，该工厂生产的每单位产品得到5.0元，生产的每单位产品得到100元的利润，工厂分别生产几个产品和产品，询问工厂利润最高。 解：作为产品的计划产量，作为产品的计划产量，目标函数： Max z=50 100制约：2线性计划的对偶问题，2.6，现在，从另一个角度考虑这个问题。 如果另一个工厂要求租借那个工厂的设备a、b、c，那个工厂的厂长应该怎样决定合理的租金呢？ 分别作为设备a、b、c每台的租金。 为了便于

13、说明，这里把租金定义为减去成本的利润。 作为一个出租人，生产部门的产品需要各设备的台，各总租金不应低于原来的利润5.0元。 否则，不出租或生产产品应用于获得利润5.0元，同样，生产产品所需各设备台的总租金也不应低于原利润100元。 否则，这些个的设备台不出租，生产产品用于获利100元。 但是，对于出租人来说，在出租人满足上述要求的前提下，即在出租人希望租赁的前提下，要求所有设备台尽可能要求时的总租金越低越好，即要求min， 我们得到了这个问题的数学模型：目标函数：限制条件：这样从两个不同的角度考虑同一工厂的最大利润(最小租金)问题，建立的两个线性模型是一对对偶问题，其中一个是原问题，另一个是对

14、偶问题。 2线性规划的对偶问题、2.7、求目标函数最大值的线性规划问题认为是原来的问题，求目标函数最小值的线性规划问题认为是对偶问题。 让我们探讨一下这两道题在数学模型上的关系。 求1目标函数最大值的线性规划问题有n个变量m个制约条件，其制约条件都在不等式以下。 其对偶是目标函数求最小值的线性规划问题，有m个变量n个约束条件，其约束条件都在不等式以上。 二元问题目标函数中的变量系数是对偶问题中制约条件的右边常数项，元问题目标函数中的第I个变量的系数等于对偶问题中的第I个制约条件的右边常数项。 三元问题的制约条件的右边常数项是对偶问题的目标函数中变量的系数。 另外，元问题的第I个制约条件的右边常

15、数项等于零对偶问题的目标函数中的第I个变量的系数。 4对偶问题的制约条件的系数矩阵a是原问题制约矩阵的转置。假设A=，2线性规划的对偶问题，2.8，如果我们用矩阵形式表现，有原来的问题。 其中，a是矩阵m*n，该问题是m个约束条件n个变量，x=，b=，c=对偶问题：其中，a的转置，b的转置，c的转置，y=当前我们以简单的形式求对偶问题的解。 加上2线性规划的对偶问题、2.9、剩余变量和人工变量，以该问题为标准形，把上述数据记入单纯形表计算中。 2线性规划的对偶问题、3.0、2线性规划的对偶问题、3.1、上表、最佳解：=50，-f的最大值为-27500，即目标函数f的最大值为f=27500元。

16、由此可知，租金方面，a设备为5.0元，b设备为0元，c设备为5.0元。 这样一来，工厂的所有设备可以租金27500元。 对出租人来说，租金是出租人想租设备的最小费用。 因为这是目标函数最小值。 比较发现，作为对偶问题最优解的最优租金与原问题的各种设备的对偶价格正好相等，这也是道理。 对于具有对偶关系的两个线性规划问题，我们只需求其中一个最佳解，就可以从该问题的对偶价格求对偶问题的最佳解，其中一个最佳值也可以找到对偶问题的最佳值。 因为这两个最佳值相等。 2线性规划的对偶问题，3.2，以下叙述如何写线性规划问题的对偶问题。 为了简化说明，以下面的线性计划为例，试着写对偶问题。 S.T .2线性规划的对偶问题，3.3，这是求最大值的线性规划问题，为了写对偶问题，我们可以把它的制约条件全部变换成比符号小的不等式。 很明显，第一约束满足要求，没有任何变更使不得。 第二个限制是，只要将双方乘以(-1 )，改变不等号的方向即可。 这样，第二约束也可以满足要求。 在第三个约束中，可以用两个以上的约束替换。 即，这两个制