厦门大学运筹学2

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

在这一章中，我们将通过举例来说明线性规划对偶问题的提出并说明它的经济意义；由此来阐述它们两者之间的关系。进一步来探讨如何求一个线性规划问题的对偶问题、以及线性规划与它的对偶问题之间的关系、对偶单纯形算法以及对线性规划问题解的变化的进一步讨论（即灵敏度分析和参数规划等等）。第一节对偶问题的提出在第一章第一节的例1中，我们讨论了工厂生产计划模型及其解法，现从另一个角度来讨论这个问题。假设该工厂的决策者决定不生产产品I、II，而将其所有资源出租或出售。这时，工厂的决策者就要考虑给每种资源进行定价的问题。设用

y1、y2、y3

分别表示出租单位设备台时的租金和出让单位原材料A、B

的附加费。作决策时，需要如下的比较：若一个单位设备台时和四个单位原材料A可以生产一件产品I，可获利2元，那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润。这就有：

y1+4y2

2；对于产品II同理有：2y2+4y3

3；把工厂所有设备台时和资源都出租和出让，其收入应为：w=8y1+16y2+12y3。从工厂的决策者来看，当然希望w

的值越大越好；但从接受者的角度来看，他支付的越少越好。所以工厂决策者只能在满足所有产品的单位利润条件下，使其总收入尽可能地小，才能实现工厂决策者的意愿。为此需要解如下的线性规划问题：我们称这个线性规划问题为例1线性规划问题（我们称为原问题）的对偶问题。根据上述例题可见，对于形如如下形式的线性规划问题：我们可以马上得出它的对偶问题：其中：AT、bT

分别是原线性规划问题中的约束条件矩阵A的转置矩阵与约束条件中右边列向量的转置(即为行向量)。从以上的线性规划问题和其对偶问题中，我们可以得出：原问题的约束条件的个数m

就是对偶问题的变量的个数；原问题的变量的个数n

就是对偶问题的约束条件的个数；若原问题的目标函数是Max型，则对偶问题的目标函数必是Min型。它们二者的最优目标函数值相等。二、对偶问题的经济解释——影子价格设B

是线性规划问题{MaxZ=CTX|AX

b，X0}的最优基，则该线性规划问题的最优解为(B-1b，0)T，其对应的目标函数最优值则为：Z*=CTB-1b=(Y*)b，其中：Y*=CTB-1(我们称为单纯形乘子)由此可得：所以变量的经济义是在其它条件不变的情况下，第i种资源的变化所引起的目标函数最优值的变化。由第一章的例1的最终计算表表1—7可见：这说明，在其它条件不变的情况下，机器台时增加一台时，该厂按最优计划安排生产可多获利1.5元，原材料A

每增加一公斤，可多获利0.125元，原材料B每增加一公斤，对获利没有影响。从上图我们可以看到：设备每增加一台时，代表约束条件的直线就由移至

，相应地最优解由点A=(4，2)移到点B=(4，2.5)，目标函数值Z=24+32.5=15.5，即比原来的增大1.5。又若原材料A

增加一公斤，代表约束条件的直线就由

移至'，相应地最优解由点A=(4，2)移到点B=(4.25，1.875)，目标函数值Z=24.25+31.875=14.125，即比原来的增大0.125。原材料B

增加一公斤时，该约束条件的直线由

移至

‘，这时的最优解不变。

yi

的值代表对第i

种资源的估价。这种估价是针对具体产品而存在的一种特殊价格，我们称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时出租费为1.5元，一公斤原材料A

的出让费为除成本外再附加0.125元，一公斤原材料B

可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异。在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进该资源用于扩大再生产；而当某种资源的市场价格高于影子价格时，则企业的决策者应把已有的资源卖出，这时企业的获利比由自己生产的还高。可见，影子价格对市场有调节作用。下面再从另一个角度来讨论该问题：从第一章第三节得到的检验数的表达式是CNT-CBTB-1N

与0–CBTB-1（松弛变量对应的检验数）。当满足条件：CNT-CBTB-1N

0，–CBTB-1

0(2.1)这表示线性规划问题已得到最优解。可见(2.1)式是作为得到最优解的条件。引进记号YT=CBTB-1，称为单纯形乘子。由(2.1)式，可知对于最优解所对应的单纯形表有Y0。对应于基变量XB

的检验数是0，它是CBT-CBTB-1B=0。包括基变量在内的所有检验数可用CT-CBTB-1A

0表示。由此可以得到CT-YTA

0即ATY

C。由于-YT=-CBTB-1，将此式两边同时右乘于b

得到：-YTb=-CBTB-1b即：YTb=CBTB-1b=Z综合1、2、3的讨论，我们可以得到另一个线性规划问题：(2.2)称此线性规划问题为原线性规划问题{MaxZ=CTX|AX

b，X0}的对偶线性规划问题。从这两个规划问题的表达式可以看出，只要根据原线性规划问题的系数矩阵A、C、b，就可以写出它的对偶问题。

第二节线性规划问题的对偶理论以上讨论可以直观地了解到原线性规划问题与对偶问题之间的关系，这一节将从理论上进一步讨论线性规划问题的对偶问题。2.1原问题与对偶问题的关系

由第一节的讨论，如下形式的线性规划问题的对偶问题是(2.2)(2.3)我们称(2.3)与(2.2)是原问题与对偶问题的标准形式。对其他形式的原问题的对偶问题，我们可进行如下分析：首先我们可以总结得出：

1.线性规划原问题的约束条件的个数m，就是其对偶问题的变量的个数；原问题的变量个数n，就是其对偶问题的约束条件的个数。

在原问题目标函数为极大化（Max）的条件下有：

2.若原问题的第i个约束条件是“”，则对偶问题的第i个变量yi

0；原问题的第i个约束条件是“”，则对偶问题的第i个变量yi

0（0

i

m）。

证明：对于“”约束条件，由标准型(2.3)与(2.2)可知：

yi

0，0

i

m；对于“”约束条件，设：

ai1x1+ai2x2+···+ainxn

bi

将上式两边同乘以（-1）得：

（-ai1x1）+（-ai2x2）+···+（-ainxn）

-bi

利用标准型对偶关系可知原问题的对偶问题是：另–yi/=yi，则yi

0，上述问题变成：

3.若原问题的第i个约束条件是“=”，则对偶问题的第i个变量yi

无约束。

证明：对于“=”约束条件，设：ai1x1+ai2x2+···+ainxn

=bi

则此式等价于ai1x1+ai2x2+···+ainxn

bi

-ai1x1

-

ai2x2

-

···-

ainxn

-bi

利用标准型对偶关系可知原问题的对偶问题是：令yi=yi/-yi//

，则显然yi

无非负限制，上述问题变成如下形式：

4.若原问题的第j

个变量xj

0，则对偶问题的第j

个约束条件为“”型；若原问题的第j

个变量xj

0，则对偶问题的第j

个约束条件为“”型。

证明：对于xj

0，则由标准型(2.3)与(2.2)可知对偶问题的第j

个约束条件为“”型；对于xj

0，问题，令：

xj/=-xj，则xj/

0，原问题变成：其对偶问题变为：即为：

5.若原问题的第j

个变量xj

无约束，则其对偶问题的第j

个约束条件为“=”号。

证明：假设xj

无约束，令xj=xj/-xj//

，则原问题和对偶问题分别为如下形式：原问题：对偶问题：即：综合1、2、3、4、5点，线性规划问题与其对偶问题的关系其变换形式可归结为如下表2—1：

表2—1原问题对偶问题目标函数（maxZ）目标函数（minW）约束条件个数m

个对偶变量个数m

个约束条件为“”型对偶变量为“0”约束条件为“”型对偶变量为“

0”约束条件为“=”型对偶变量为无约束变量个数为n

个约束条件个数为n

个变量为“0”约束条件为“”型变量为“

0”约束条件为“”型变量为无约束约束条件为“=”型下面举一例说明如何利用以上规则来求一个线性规划问题的对偶问题。

例1试求如下线性规划问题的对偶问题

解：设对应于约束条件(1)，(2)，(3)的对偶变量分别为y1y2，y3，则由表2—1中原问题与对偶问题的对应关系，可以直接写出上面问题的对偶问题，它是：

2.2对偶问题的基本定理

1.对称性：线性规划问题的对偶问题的对偶是原问题。

证明：设原问题是：maxZ=CTX；AX

b；X0。它的对偶问题是：minW=bTY；ATY

C；Y0。将此对偶问题作形式上的变换，等价于：

max(-W)=-bTY；-ATY

-C；Y0；这个问题的对偶问题是：

minZ/=-CTX；-AX

-b；X0；即：max(-Z/)=CTX；AX

b；X0;也就是原问题。

2.弱对偶性：假如X*与Y*分别是原问题与对偶问题的可行解。则必有：CTX*

bTY

*。

证明：假设原问题与对偶问题分别是(2.3)与(2.2)形式，因为X*

是原问题的可行解，所以满足约束条件，即：

AX*

b；X*0由因为Y*0，所以有：(Y*)TAX*

(Y*)Tb

=

bTY

*；又Y*是对偶问题的可行解，所以满足约束条件，即：ATY

*

C；Y*0由因为X*0，所以有：(X*)TATY

*

(X*)TC=CTX

*

又因为：(Y*)TAX*=(X*)TATY

*

所以有：CTX

*

bTY

*。3.无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。

证明：由弱对偶性显然便可得到。应当指出的是本性质不存在逆，即当原问题（对偶问题）无可行解时，并不能断言对偶问题（原问题）必定具有无界解。如下问题便可说明：

例2：原问题对偶问题显然在例2中，原问题与对偶问题都没有可行界。

4.可行解是最优解时的性质：设X*与Y*分别是原问题与对偶问题的可行解，当CTX

*=

bTY

*

时，

X*与Y*分别是原问题与对偶问题的最优解解。

证明：当CTX

*=

bTY

*

时，根据弱对偶性可知，对于对偶问题的任何一个可行解Y，都有bTY

CTX

*=

bTY

*，可见Y

*

是对偶问题的最优解。同理可证明：对于原问题的任何一个可行解X，比有CTX

*=

bTY

*

CTX，所以X

*必然是原问题的最优解。

5.对偶定理：若原问题有最优解，则其对偶问题也有最优解，且它们的目标函数值相等。

证明：设X*是原问题最优的基可行解，它对应的基矩阵为B必使得CT-CBTB-1A

0，即得到(Y*)TA

CT

也就是

ATY

*

C，其中：(Y*)T=CBTB-10这时Y*

是对偶问题的可行解，它使得：(Y*)Tb=CBTB-1b=CTX

*

由性质4可知，Y*

是对偶问题的可行解。

6.互补松弛性：若X*与Y*分别是原问题与对偶问题的可行解，那么(Y*)TXs=0和YsTX=0的充分必要条件是X*与Y*分别是原问题与对偶问题的最优解解。这里Xs

和Ys

分别为原问题与对偶问题的松弛向量和剩余向量。

证明：设原问题和对偶问题的标准型是：原问题对偶问题将原问题目标函数中的系数向量C

用C=ATY–Ys

代替，得到：Z=(ATY–Ys)TX=YTAX–YsTX(2.4)将对偶问题目标函数中的系数向量b

用b=AX+Xs代替，得到：W=YT(AX+Xs)=YTAX+YTXs(2.5)

若(Y*)TXs=0和YsTX*=0，则

CTX

*=

bTY

*=(Y*)TAX*

由性质4可知X*与Y*分别是原问题与对偶问题的最优解。由若X*与Y*分别是原问题与对偶问题的最优解，由性质2可知CTX

*=(Y*)TAX*

=

bTY

*

再由(2.4)、(2.5)式知道，这时必有(Y*)TXs=0和YsTX*=0

7.设原问题是：maxZ=CTX；AX+Xs=b；X，Xs

0对偶问题是：minW=YTb；ATY–Ys=C；Y，Ys

0则原问题单纯形表的检验数行对应其对偶问题的一个基解

，其对应关系见表2—2。

表2—2XBXNXs0CNT–CBTB-1N-CBTB-1Ys1-Ys2T-Y

这里Ys1是对应原问题中基变量XB

的剩余变量，Ys2是对应原问题中非基变量XN

的剩余变量。

证明：设B

是原问题的一个可行基，于是A=(B,N)；原问题可改写为：相应地对偶问题可表示为：这里：，当求得原问题的一个可行解XB=B-1b时，其相应的非基变量XN、Xs

检验数为：CNT–CBTB-1N-CBTB-1。现分析这些检验数与对偶问题的解之间的关系：令YT=CBTB-1，将它代入(2.6)、(2.7)式得到Ys1=0，

-Ys2T=CNT–CBTB-1N。

现举两个例子说明这些性质的应用。

例3：对于如下线性规划问题，试利用对偶理论证明该线性规划问题无最优解。

证明：首先我们可以知道该线性规划问题存在可行解X=(0，0，0)；而上述问题的对偶问题是：由第一约束条件可知对偶问题无可行解，因此无最优解。再由对偶定理可知原问题必无最优解。

例4已知线性规划问题：的对偶问题的最优解为y1*=4/5，y2*=3/5，目标函数值为Z*=5，试用对偶理论找出原问题的最优解。

解：首先写出该线性规划问题的对偶问题：将y1*、y2*

的值代入约束条件，得(2)、(3)、(4)为严格不等式；由互补松弛性（性质6）可得：x2*=x3*=x4*=0，同样由互补松弛性，因为y1*、y2*>0，所以原问题的两个约束条件应该取等式，故有：求解此方程组便可得到：x1*=1，x5*=1；所以原问题的最优解为：X*=(x1*,x2*,x3*,x4*,x5*)=(1,0,0,0,1)。

最优目标函数值为：W

*=5。

第三节对偶单纯形算法

本章第二节讲到原问题与对偶问题的解之间的对应关系（性质7）时指出：在单纯形表进行迭代计算时，在列中得到的是原问题的基可行解，而在检验数行中得到的是对偶问题的基解。通过逐步迭代计算，当在检验数行得到对偶问题的解也是可行解时，根据性质2、4便可知道，已得到最优解。此时原问题与对偶问题都是最优解。根据对偶问题的对称性，也可以这样考虑问题：若保持对偶问题的解是基可行解，即检验数：

σj=cj–CBTB-1Pj

0

而原问题在非可行解的基础上，通过逐步迭代计算达到可行，即：0，这样也可以得到原问题的最优解。其优点是原问题的初始解不一定要求是基可行解，可从非基可行解开始迭代计算。这个方法可具体表述如下：设原问题是：又设B

是一个基（不一定是可行基），不失一般性，令

B=(P1,P2,···,Pm)

它对应的基变量为XB=(x1,x2,···,xm)T

。当非基变量都为0时可以得到XB=B-1b。若在B-1b

中至少有一个负分量，设(B-1b)i<0，并且在单纯形表检验数行中的检验数都0，即对偶问题保持可行，它的各分量是：对应于基变量x1,x2,···,xm

的检验数是σj=cj–CBTB-1Pj

=0，j=1,2,···,m

对应于非基变量

xm+1,xm+2,···,xn的检验数是σj=cj–CBTB-1Pj

0，j=

m+1,···,n

每次迭代是将基变量中的负分量xl

取出，去替换非基变量中的xk

，并使所有检验数继续保持0。在列中小于的元素个数要减少。即从原问题来看，经过每次迭代，原问题由非可行解向可行解靠近，而当原问题得到可行解时，便得到了原问题的最优解。

对偶单纯形算法的计算步骤如下：（1）首先根据线性规划问题，列出初始单纯形表。（所给出的基要使得非基变量检验数全都0，也就是所给出的解是一个对偶可行解，这时也称所给出的基为对偶可行基），检查列的数字，若都为非负，则已得到原问题的最优解，停止计算。（2）若列中存在某个，且所对应的该行的系数矩阵元素，则原问题无可行解，停止计算。我们对第（2）项内容说明如下：取，这时可知

Y

T是对偶问题的可行解，对应于这个可行解的对偶问题的目标函数值是：即对偶问题的可行解使得对偶问题目标函数值无界，则由性质3（无界性）可知原问题没有可行解。(3)若非（1）、（2）情形，则进行基变换，具体如下：首先确定换出变量：由

对应的基变量xl

为换出变量。其次确定换入变量：由

对应的非基变量xk

为换入变量（只有这样，才能保持得到的对偶问题的解仍为可行解）。（4）以ylk

为主元素，按原单纯形算法在表中进行迭代运算（即进行基变换），得到新的计算表。

重复（1）~（4）的步骤，直到的所有分量全都0。

下面举例说明具体算法。

例5用对偶单纯形算法求解如下线性规划问题

解：先将该问题化成下面形式，以便得到原问题的一个对偶初始可行解，进而得到一个初始对偶可行基。以x4,x5

为初始基变量，建立这个问题的初始单纯形表，见表2—3；然后，利用对偶单纯形算法进行计算得到表2—4、表2—5，具体如下：表2—3Cj

-2-3-400CBXBx1x2x3x4x50x4-3-1-2-1100x5-4[-2]1-301

j0-2-3-400

表2—4Cj

-2-3-400CBXBx1x2x3x4x50x4-10[-5/2]1/21-1/2-2x121-1/23/20-1/2

j40-4-10-1

表2—5Cj

-2-3-400CBXBx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5

j28/500-3/5-8/5-1/5在表2—5中，，检验数全都0，所以原问题的最优解为X

*=(x1*,x2*,x3*,x4*,x5*)=(11/5,2/5,0,0,0)。

原问题对应于两个约束条件的对偶变量分别为y1,y2,则由表2—5的检验数行便可得出原问题的对偶问题的最优解是Y*=(y1*,y2*)=(8/5,1/5)即对应于原问题的两个松弛变量x4

和x5

的检验数的反号。从以上求解过程可以看到，对偶单纯形算法有以下优点：(1)初始解可以是非可行解，当检验数都0，就可以进行基变换，这时无需加人工变量，因此，可以简化计算。(2)当变量多于约束条件时，对于这样的线性规划问题，用对偶单纯形算法计算可以减少计算工作量。因此，对变量较少而约束条件较多的线性规划问题，可先将它变换成对偶问题，然后利用对偶单纯形算法求解。（3）在灵敏度分析中，有时需要利用对偶单纯形算法，这样可使问题的处理简化。

当然，对偶单纯形算法也有它的不足之处，其极限性主要是，对大多数线性规划问题，很难找到一个初始对偶可行解（基），因此，这种方法在求解线性规划问题时很少单独使用。

第四节灵敏度分析在以前讨论线性规划问题时，都假定aij,bi

,cj

都是常数。但实际上这些系数往往是估计值或预测值。如果市场条件发生变化，cj

值就会发生变化；aij

往往是因为工艺条件的改变而改变；

bi

是根据资源投入后的经济效果决定的一种决策选择。因此，我们会提出这样的问题（1）当这些系数有一个或若干个发生变化时，原先已求得的线性规划问题的最优解会有什么变化；（2）或者这些系数在什么范围变化时，线性规划问题的最优解或最优基不变。前一个问题我们称为参数规划，将在第五节中讨论；而后一个问题我们称为灵敏度分析，将在本节中进行讨论。显然，当线性规划问题中这些系数有一个或若干个发生变化时，原先已求得的线性规划问题的最优解一般是会发生变化的。当然可以用单纯形算法从头开始计算，以便得到新的最优解。但是，这样做很麻烦，而且也没有必要。由于在单纯形法迭代计算时，每次计算都和基变量所对应的系数矩阵B

有关，因此，可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2—6中的几种情况进行处理。下面就各种情况分别进行讨论。

表2—6原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍为最优解可行解非可行解用单纯形法继续计算求最优解非可行解可行解用对偶单纯形法继续计算求最优解非可行解非可行解引进人工变量，编制新的单纯形表求最优解

4.1资源数量变化的分析资源数量变化是指系数br

发生变化，即br/=

br+Δbr

。并假定规划问题其他系数都保持不变；这样使最终表中原问题的解相应地变化为：XB/=B-1(b+Δb)

这里Δb=(0,···,Δbr,···,0)T

，只要XB/

0，最终表中检验数不变，则最优基不变。但最优解的值发生了变化，所以XB/

为新的最优解。新最优解的值可允许变化范围用以下方法确定。这时在最终表中求得的列的所有元素：由此可得：即当约束条件中的第r

种资源变化范围的改变量在上述范围变化时，原问题的最优基不发生变化。例如我们求第一章例1中第二个约束条件b2

的变化范围Δb2

时，可计算：因此，b2

的变化范围是：b2+Δb2=[8，32]。

例6我们知道第一章例1中，每设备台时的影子价格为1.5元，若该厂又从别处抽出4个台时用于生产产品I、II，求这时该厂生产产品I、II的最优方案。

解：首先计算将上述结果反映到最终计算表中，得表2—7，并利用对偶单纯形算法求得表2—8如下：

表2—7Cj

23000CBXBx1x2x3x4x52x14+01000.2500x54-800[-2]0.513x22+2010.5-0.1250

j00-1.5-0.1250表2—8Cj

23000CBXBx1x2x3x4x52x141000.2500x32001-0.25-0.53x2301000.25

j000-0.5-0.75即该厂最优生产方案应改为生产产品I4件，生产产品II3件，最大获利Z*=42+33=17（元）。从表2—8中可看出x3=2，即设备有2台时未利用。

4.2目标函数中价值系数cj

的变化分析

可以分别就cj

对应的变量是非基变量和基变量两种情形加以讨论：（1）若cj

对应的变量xj

是非基变量，这时它在计算表中所对应的检验数是：σj=cj–CBTB-1Pj

当cj

变化Δcj

后，为了保证最终表中这个检验数仍然小于0，即：σj/=cj

+Δcj

–CBTB-1Pj

0

cj

+Δcj

YTPj(YT=CBTB-1)

Δcj

YTPj

-cj=-σj

即Δcj

的值必须小于等于YTPj

-cj

，也就是-σj

，才可以满足原解仍然是最优解的这一结果，这样我们就确定了

Δcj

的取值范围。即当Δcj(-,-σj

]时，原问题的最优解不变。

（2）若cr对应的变量xr

是基变量，因为cr

CB，当cr

变化时，就会引起

CB

的变化，这时：(CBT+ΔCBT)B-1A=CBTB-1A+(0,···,Δcr,···,0)B-1A

=CBTB-1A+Δcr(ar1,ar2,···,arn)

其中：(ar1,ar2,···,arn)

表示B-1A矩阵的第r

行。可见，当

cr

变化Δcr

后，最终表中的检验数是：σj/=cj–CBTB-1Pj

–Δcjarj

=σj–Δcjarj

(j

IN

)若要求原最优解不变，即必须满足σj/

0,j

IN

，于是得到：例7：试以第一章例1的最终表为例。若基变量x2

的系数

c2

变化Δc2，在原最优解不变的条件下，确定Δc2

的变化范围。

解：这时由表1—7表1—7cj23000CBXBx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-Z-1400-1.5-1/80经修改后可得表2—9

表2—9cj23+Δc2

000CBXBx1x2x3x4x52x141001/400x5400-21/213+Δc2

x22011/2-1/80-Z-1400-1.5-Δc2/2-1/8+Δc2/80从表2—9可看出，为使表中解仍然为最优解，就必须有：

-1.5-Δc2/20，

-1/8+Δc2/80联立以上两个不等式求解变得：-3Δc21即当x2

的价值系数c2

在[0，4]区间变化时，原问题的最优解不变。

4.3技术系数aij

的变化对最优解的影响

下面分两种情况讨论技术系数

aij

的变化，并以具体例子加以说明。

例8分析在原计划中是否应该安排一种新产品。以第一章例1为例，设该厂除了生产产品I、II外，还有一种新产品III。已知生产产品III，每件需消耗原材料A、B各为6kg、3kg，使用设备2台时；每件可获利5元，问该厂是否应生产该产品和生产多少？

解：分析此问题的步骤是：（1）设生产产品IIIx3/

件，其技术系数向量P3/=(2,6,3)T

，然后计算表中对应于x3/

的检验数：

3/=c3/

-CBTB-1P3/

=5–(1.5,0.125,0)(2,6,3)T=1.25>0

说明安排生产产品III是有利的。（2）计算产品III在最终表中对应

x3/

的列向量：并将（1）、（2）中的计算结果填入最终表中可得表2—10

表2—10cj230005CBXBx1x2x3x4x5x3/2x141001/403/20x5400-21/21[2]3x22011/2-1/801/4-Z-1400-1.5-1/805/4

由于列的数字没有变化，原问题的解是可行解，但检验数中还有正检验数，说明目标函数值还可以改善。（3）将x3/

作为换入变量，x5

作为换出变量，进行基变换，求出新的最优解。这时得出新的最优解为：x1=1，

x2=1.5，x3/=2，总利润为16.5元，比原计划增加了2.5元，具体见下表2—11

表2—11cj230005CBXBx1x2x3x4x5x3/2x11101.5-0.125-0.7505x3/200-10.250.513x21.5010.75-0.1875-0.1250-Z-16.500-0.25-0.4375-0.6250

例9分析原计划生产产品的工艺结构发生变化。仍以第一章例1为例加以说明，若原来计划生产产品I的工艺结构有了改进，这时有关它的技术向量变为P1/=(2,5,2)T

，每件利润为4元，试分析对原最优计划有什么影响？解：把改进工艺结构的产品I看作新产品I/，设x1/

为其产量，于是计算在最终表中对应x1/

的列向量：同时计算出x1/

的检验数为：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(2,5,2)T=0.375>0将以上结果填入最终表附加的x1/

列向量位置得表2—12cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.510.53x22010.5-0.12500.375-Z-1400-1.5-0.12500.375显然在表2—12中，x1/

正好替换x1，经基变换运算之后将x1

列去掉，以x1/

代替x1

列可得表2—13如下：

表2—13cj43000CBXBx1/x2x3x4x54x1/3.21000.200x52.400-20.413x20.8010.5-0.20-Z-15.200-1.5-0.20即这时应当生产产品I/3.2件，产品II0.8件，可获利15.2元

例10：假设上例的产品I/

的技术向量变为P1/=(4,5,2)T

，而每件产品获利仍为4元。试问该厂如何安排最优生产方案？

解：方法与上例相同，以x1/

代替x1，计算：同时计算出x1/

的检验数为：

1/=c1/

-CBTB-1P1/

=4–(1.5,0.125,0)(4,5,2)T=-2.625<0将以上结果填入最终表附加的x1/

列向量位置得表2—14表2—14cj230004CBXBx1x2x3x4x5x1/2x141000.250[1.25]0x5400-20.51-3.53x22010.5-0.12501.375-Z-1400-1.5-0.1250-2.625由单纯形法的计算规则可知，这时原解仍为最优解。但我们仍以x1/

强行替换x1，将运算后的x1/

列填入x1

列位置，去掉x1

列可得表2—15如下：

表2—15

cj43000CBXBx1/x2x3x4x54x1/3.21000.200x515.200-21.213x2-2.4010.5-0.40-Z-5.600-1.50.40从该表可见原问题和对偶问题都是非可行解，于是引入人工变量x6(放入出现负的那一行)，用方程表示即为0x1/+x2+0.5x3

–0.4x4+0x5=-2.4

引入人工变量x6，上式就变为：