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

第六章单纯形法的灵敏度分析与对偶§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法1§1单纯形表的灵敏度分析一、目标函数中变量Ck系数灵敏度分析1.在最终的单纯形表里，X

k是非基变量

由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。2.在最终的单纯形表中，X

k是基变量

当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则ZJ(J=1,2,…..,N)一般也变了，不妨设CB=(CB1,

CB2。。。,Ck,…，CBm),当CB变成=(CB1,

CB2。。。,Ck+Ck,…,CBm),则：

ZJ=(CB1,

CB2。。。,Ck,…，CBm)(a’1j,a’2j,…,a’Kj

,…,a’mj)Z’J=(CB1,

CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj

,…,a’mj)=ZJ+

Cka’Kj

2§1单纯形表的灵敏度分析根据上式可知检验数J(J=1,2,…..,M)变成了’J,有

’

J=CJ-Z’J=J+CKa’Kj

。要使最优解不变，只要当JK时，’J<=0

3§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2

约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-504§1单纯形表的灵敏度分析

我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和

a13’大于0，a15’小于0，可知，有。同样有。这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。在最终的单纯形表中，用C’1代替原来的C1=50,计算得表5§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3b501000002X1C’11010-150

S2000-21150

X210001001250

ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-100

从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。6§1单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析

从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中S2=50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的，

A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-507§1单纯形表的灵敏度分析

可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取值的相反数-。

对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的值。

8下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。

从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。

下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。由此可见当bj变化时，要使原来的基不变得到的基本可行解仍然是可行解，也就是所求的基变量的值一定要大于0。所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量不变，且所得的最优解仍然是可行的bj的变化范围。约束条件影子价格的取值

≤等于这个约束条件对应的松弛变量的值,即为的相反数

≥等于这个约束条件对应的剩余变量的值,即为的相反数

=等于这个约束条件对应的人工变量的值,即为的相反数

§1单纯形表的灵敏度分析9§1单纯形表的灵敏度分析

当bj中的第k项bK

变成

时，也就是原来的初始单纯形表中的b向量变成了b’向量10§1单纯形表的灵敏度分析这样在最终单纯形表中基变量XB的解就变成了如要使XB成为可行解，只要使上述等式的右边>0，就可求出的取值范围，也就是使得第K个约束条件的对偶价格不变的bk的变化范围。，11§1单纯形表的灵敏度分析下面我们仍以第二章例1在最终单纯形表上对bj

进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-5012§1单纯形表的灵敏度分析我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,

实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。13§1单纯形表的灵敏度分析三、约束方程系数矩阵A灵敏度分析下面分两种情况讨论

1.在初始单纯形表上的变量Xk的系数列Pk改变为P’k经过迭代后，在最终单纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk’仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj’,而Zk就变成CBB-1Pk’，新的检验数k=Ck-CBB-1Pk’。若k≤0，则原最优解仍然为最优解。若k〉0，则继续进行迭代以求出最优。例以第二章例1为基础，设该厂除了生产Ι，Ⅱ种产品外，现在试制成一个新产品Ⅲ，已知生产产品Ⅲ,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，14§1单纯形表的灵敏度分析接上页迭代次数基变量CBX1X2S1S2S3X3b50100000150X1501010-10.550

S2000-211-250

X2100010011.5250

ZJ501005005017527500CJ-ZJ00-500-50-2515§1单纯形表的灵敏度分析例假设上例题中产品Ш的工艺结构有了改进，这时生产1件Ш产品需要使用1.5台设备，消耗原料A为2千克，原料B为1千克，每件Ш产品的利润为160元，问该厂的生产计划是否要修改。解：首先求出X3在最终表上的系数列

迭代次数基变量CBX1X2S1S2S3X3b501000001502X1501010-10.55050/0.5

S2000-211050

X2100010011250250/1

ZJ501005005012527500CJ-ZJ00-500-503516§1单纯形表的灵敏度分析接下来又可以有新的迭代S3进基，迭代次数基变量CBX1X2S1S2S3X3b501000001503X31602020-21100---

S2000-21105050/1

X2100-201-2030150250/3

ZJ1201001200-2016031000CJ-ZJ-700-120020017§1单纯形表的灵敏度分析接上页可知此规模的最优解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产Ι、П产品，生产Ш产品200件,可获得最大利润32000元。迭代次数基变量CBX1X2S1S2S3X3b501000001504X31602020-21200---

S3000-21105050/1

X2100-214-3000250/3

ZJ1201008020016032000CJ-ZJ-700-80-200018§1单纯形表的灵敏度分析

2.在初始表上的变量XK的系数PK改变为P’K，经过迭代后，在最终表上XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。19§1单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析

在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。下面仍以第三章例1为例来加以说明。例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个Ⅰ产品需要用电10度，而生产一个Ⅱ产品需要用电30度。试分析此时该厂获得最大利润的生产计划？20§1单纯形表的灵敏度分析

解：先将原问题的最优解=50，=250代入用电量的约束条件得：10×50+30×250=500+7500>5000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量S4后得：把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：迭代次数基变量b比值501000000501010-1050000-2110501000100102500103000015000501005005002750000-500-50021§1单纯形表的灵敏度分析

在上表中的X1，X2不是单位向量，故进行行的线性变换，得迭代次数基变量CBx1x2s1s2s3s4b比值501000000x1501010-1050s2000-211050x2100010010250s4000-100-201-3000zj501005005002750000-500-500把上表中的S4行的约束可以写为：上式两边乘以（-1），再加上人工变量a1得：用上式替换上表中的S4行，得下表：22§1单纯形表的灵敏度分析迭代次数基变量x1x2s1s2s3s4a1b比值501000000-Mx1501010-10050s2000-21(1)0050x21000100100250s4-M00-100-20113000zj5010050-10M050-20M0-M0010M-50020M-5000

x15010-11000100

s3000-2110050

x2100012-1000200

s4-M0050-200-112000

zj50100150-50M20M-500M-M

050M-15050-20M0-M0

x1501003/50-1/501/50140

s300001/51-2/502/50130

x2100010-1/502/50-2/50120

s40001-2/50-1/501/5040

zj5010001003-3

00-100-3-M+3

23§1单纯形表的灵敏度分析

由上表可知，最优解为：

即该工厂在添加了用电限量以后的最优生产计划为Ⅰ产品生产140件，Ⅱ产品生产120件。24每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。例题1

某工厂在计划期内安排Ⅰ、Ⅱ两种产品，生产单位产品所需设备A、B、C台时如表所示

该工厂每生产一单位产品可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少产品和Ⅱ产品，才能使工厂获利最多？解：设为产品的计划产量，为产品Ⅱ的计划产量，则有目标函数：Maxz=50+100约束条件：

，§2线性规划的对偶问题25现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？设分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位产品所需各设备的台时各总租金不应低于原利润50元，即，否则就不出租还是用于生产产品以获利50元；同样把生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即，否则这些设备台时就不出租，还是用于生产产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min，这样我们得到了该问题的数学模型：

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

1求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。

2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。

3原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。

4对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。

设

A=则

§2线性规划的对偶问题27如果我们用矩阵形式来表示，则有原问题：

其中A是矩阵m*n，该问题有m个约束条件n个变量，x=,b=,c=

对偶问题：

其中是A的转置，是b的转置,是c的转置,y=现在我们用单纯形法求对偶问题的解。§2线性规划的对偶问题28

加上剩余变量和人工变量，把此问题化成标准型如下：把上述数据填入单纯形表计算。§2线性规划的对偶问题29迭代变量基变量b-300-400-25000-M

1-M1②

0-1015050/2-2501110-10100100/1-M-250-2M-250-250M250-M-50M-25000M-2502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50§2线性规划的对偶问题30

由上表，最优解：=50，

-f的最大值为-27500，即目标函数f的最大值为f=27500元。从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目标函数的最小值。通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通。对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。

§2线性规划的对偶问题31

下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。

S.T.

§2线性规划的对偶问题32

这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得

这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有

显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（-1），得

§2线性规划的对偶问题33

通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：

s.t.

§2线性规划的对偶问题34

这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：

s.t.§2线性规划的对偶问题35

这里和一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为。因为在该对偶问题中和的系数只相差一个符号，我们可以把上面的对偶问题化为：

s.t.§2线性规划的对偶问题36进一步，我们可以令，这时当时，

，当时，。这也就是说，尽管但的取值可以为正，可以为0，可以为负，即没有非负限制。这样我们把原规划的对偶问题化为

s.t.

没有限制。对照原线性规划问题，我们可以知道：当原线性规划问题的第i个约束条件取等号时，则其对偶问题的i个决策变量没有非负限制。如果当原线性规划问题中的第i个决策变量没有非负限制时，我们也可以用进行替换，这里，，用类似的方法知道其对偶问题中第i个约束条件取等号。§2线性规划的对偶问题37

另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。原线性规划问题为：

s.t.

无非负限制。§2线性规划的对偶问题38§3对偶规划的基本性质对偶规划的基本性质1．对称性。即对偶问题的对偶是原问题。2．弱对偶性。即对于原问题（Ⅰ）和对偶问题（Ⅱ）的可行解都有C≤bT

。

由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可