运筹学第二章线性规划的对偶理论和灵敏度分析

1、窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.1 单纯形法的矩阵描述 上一章我们讨论了如何运用单纯形表，通过迭代调整变量，求出线性规划模型的最优解。这一节我们运用矩阵、向量的形式来揭示这种迭代运算的本质，以利于讨论线性规划的对偶理论与灵敏度分析。 假如有一个求最大值的线性规划标准形式，其初始基变量为xi，迭代如干次后，其基变量为xb，先不妨假设xi与xb中无相同的变量。,将模型填入单纯形表2.1中：,第二章 线性规划的对偶理论和灵敏度分析,约束条件：,表2.1,第二章 线性规划的对偶理论和灵敏度分析,经过

2、若干次迭代后，基变量变为xb，则在表2.1中，基一列的xi应改为xb，为计算出xb的取值，xb一列中，约束条件行的b应变为i，则当非基变量xn，xi变为零时，在解的一列中直接可得xb的取值，故可在上表中的约束条件行两边同左乘b-1，得表2.2：,表2.2,在这里不妨假设b-1是存在的，因为如果b不可逆，说明约束条件中含有多余的约束方程，或含相关变量，可采取适当方法处理之，以保证b的可逆性。 为判断当前的基本可行解是否最优，必须将表2.2中的基变量xb从目前函数行中消去，可通过以下运算来实现，将约束条件行左乘cb后，加到目标函数行得：,第二章 线性规划的对偶理论和灵敏度分析,这样就得到了：当xb

3、为基变量时，解为b-1b，目标函数值为cbb-1b，非基变量xn，xi的检验数分别为cbb-1n-cn和cbb-1-ci 。当cbb-1n-cn和cbb-1-ci都满足最优条件时，已得最优解，否则，当前的基本解还不是最优的，还需进一步迭代，考虑新的xb（基变量）。,第二章 线性规划的对偶理论和灵敏度分析,表2.3,通过以上对单纯形表矩阵形式的分析可以看出：当单纯形表迭代到某一步时，表格中的所有数据均由基变量xb决定，即我们取xb在约束条件中的系数矩阵为b，求出它的逆矩阵b-1，再取xb在目标函数中的系数cb，则利用表2.3可将整个单纯形表计算出来。只是我们在计算时，我们要注意以下三点： 1.在

4、表2.1到表2.3中，我们将所有的变量分为xb，xn和xi，它们在目标函数中的系数分别记,第二章 线性规划的对偶理论和灵敏度分析,为b，n，和i。这种记法主要方便表示和运算。就其本质而言，在迭代计算中，它们运算的实质是完全一样的。即都是对约束方程乘以b-1，而且目标函数行的运算是利用约束方程消去目标函数行基变量的系数。这些运算都是按列运算的，各列之间并没有任何运算。例如对任意一个变量xj（不论它属于xb，xn还是xi），记其在目标函数中的系数为cj，在约束条件中的系数为pj，则迭代后的xj在目标函数的系数都为cbb-1pj-cj，约,第二章 线性规划的对偶理论和灵敏度分析,束条件中的系数都为b

5、-1pj。只是由于pj的初始状态不同，在迭代后的表才会有不同的形式。 2.可能有一个或几个变量同时出现在xb与xi中，也就是说，有一个或几个变量既是迭代若干次后的基变量，也是初始基变量。虽然它们每个变量在单纯形表中占一列，但是我们在讨论xi时要把它考虑进去，在讨论xb时也要把它考虑进去，即一列扮演了两个角色。 3.由于单纯形表中个变量的位置一般按x1， x2，xn等事先确定，而未必会正好按基变,第二章 线性规划的对偶理论和灵敏度分析,量xb，非基变量xn等排好，好在线性规划约束条件、目标函数中，交换变量的先后位置是不要紧的，我们可以通过交换变量的位置来实现xb，xn，xi的排列，或更常用的是，

6、就用原有的次序，按列来进行计算，选取有关的数据。,第二章 线性规划的对偶理论和灵敏度分析,2.2 改进单纯性法 我们在第一章已经熟悉了单纯形法的表格计算。用这种方法求解线性规划问题时，发现每一步迭代过程中不必要地计算了很多与下一步迭代无关的数据，严重影响了计算效率。在单纯性法的迭代过程中，基矩阵的逆阵b-1求出后，调出行表中的其他行和列的数据随之可以确定。这就是单纯形法的出发点。,第二章 线性规划的对偶理论和灵敏度分析,2.2.1 用改进单纯形法求解线性规划的计算步骤 (1)根据给出的线性规划问题，在加入松弛变量后，得到初始基变量。求解初始基变量b的逆阵b-1，求出初始解 ，然后计算单纯性乘子

7、y=cbb-1。 (2)计算非基变量xn的检验书n，n=cn-cbb-1n。若n0，已经得到最优解，停止计算。否则转下一步。 (3)根据max(j| j0)= k所对应的非基变量xk为调入变量计算b-1n，若b-1n 0则问题无解，停止计算，否则转下一步。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,(4)求出 它对应的基变量xl跳出变量。可以得出一组新的基变量和基矩阵b。 (5) 计算基矩阵的逆阵b-1，求出b-1b和y=cbb-1。重复（2）（5）。 如果我们细心的话，只要注意单纯形法的计算步骤就可以看出上一步的基b与下一步的基b之间只差了一个变量。如果

8、只根据b-1和调入变量xk,的系数变量来计算出b1-1，而不是直接求b1-1，计算过程为： (a)把mm的单位阵表示为：im=(e1,e2,em) (b)设xk为调入变量，xl为调出变量，则有,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第l行,第二章 线性规划的对偶理论和灵敏度分析,2.2.2例子 例2.1用改进单纯形法求解,解：,第二章 线性规划的对偶理论和灵敏度分析,x1 x2 x3 x4 x5,计算非基变量检验数 2=31=1，因此，选x2作为调入变量，则：,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性

9、规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第三步迭代略，最后得最优解,第二章 线性规划的对偶理论和灵敏度分析,2.3对偶问题的提出 例2.2 某公司在计划期内安排生产i、ii两种产品。已知生产单位产品所需的设备台时及a、b两种原材料的消耗如下表所示，该工厂每生产一件产品i可获取2元，每生产一件产品ii可获利3元，问如何安排计划使该工厂获利最多。,第二章 线性规划的对偶理论和灵敏度分析,解 设x1，x2分别表示产品i和ii的产量，则可建立如下线性规划模型： max z=2x1+3x2 x1+2x28 4x116 4x212 x1，x20 我们从另一个角度考虑这个问题。假

10、如该工厂的决策者决定不生产产品i、ii，而将其所有资源出售或出租。这时工厂的决策者就要考虑给每个资,第二章 线性规划的对偶理论和灵敏度分析,s.t.,源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料a、b的附加额。它们在定价决策时，作如下比较：若用一个单位设备台时和4个单位原材料a可以生产一件产品i，可获利2元，那么生产每件产品i的设备台时和原材料出租和出让的所有收入应不低于生产一件产品i的利润，这就有： y1+4y22 同理，将生产每件产品ii的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品ii的利润，这就有：,第二章 线性规划的对偶理论和灵敏

11、度分析,2y1+4y33 把所有的设备台时和资源出租和出让，其收入为： f=8y1+16y2+12y3 从工厂的角度看，f当然是越大越好，但从接受者眼光看，f是越小越好，所以工厂决策者只可以在满足所有产品利润条件下，使其总收入尽可能的小。因此可以列出如下线性规划问题：,第二章 线性规划的对偶理论和灵敏度分析,我们称这个问题为原问题的对偶问题。各模型中有关数据的“位置”示意图如下图所示。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.3.2 用矩阵形式表示线性规划的对偶问题 从上一节得到的检验数的表达式是 cn-cbb-1n与-cbb-1 另外我们知道，当检

12、验数 cn-cbb-1n0(2-9) 这表示线性规划问题已得到最优解，可见上面两式是得到最优解条件。 由上一节我们知道： y=cbb-10称为单纯形子，,第二章 线性规划的对偶理论和灵敏度分析,由于，cb-cbb-1b=0 所以 (cb,cn)-(cbb-1b，cbb-1n)=c-cbb-1(b,n)0 包括基变量在内的所有检验数可以用c-cbb-1a0表示，因此可知：c-ya0 移项后得到：yac 由于 y=cbb-1 同乘于b得：yb=cbb-1b=z,第二章 线性规划的对偶理论和灵敏度分析,由于y的上界为无穷大，所以只存在最小值。 从而可以得到另一个线性规划问题： min f=yb ya

13、c y0 我们称它为原线性规划问题的对偶问题。 从这里两个线性规划问题的表达式可以看出：根据原线性规划问题的系数矩阵a、c、b就可以写出它的对偶问题。以例2.2为例原线性规划问题各系数矩阵是：,第二章 线性规划的对偶理论和灵敏度分析,s.t.,第二章 线性规划的对偶理论和灵敏度分析,2.3.3 线性规划问题的对偶问题举例 例2.3 某工厂拥有a、b、c三种类型的设备，生产甲、乙两种产品。每件产品在生产中占用的设备机时数、每件产品可以获得的利润以及三种设备可利用的时数如下表。求最大利润的方案。,第二章 线性规划的对偶理论和灵敏度分析,根据例2.2的分析思路不难得出下面一对对偶问题。,第二章 线性

14、规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,例2.4 资源利用问题 考虑，资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每个资源如何定价？,第二章 线性规划的对偶理论和灵敏度分析,解 yi(i=1,2,m)表示出售单位数量的第i种资源的价值。资源拥有者在作出出售资源的决策时，考虑出售资源的收入不应低于生产所获得的收入，则有： 如果资源所有者将资源出售，则他得到的总收入 ，资源买方希望越小越好，所以资源拥,第二章 线性规划的对偶理论和灵敏度分析,有者出售每一种资源的合理估价，可以通过求解线性规划问题而得到。 对于同一个资源利用问题，从不同的角度考虑，将可以得到

15、两个相互关联的线性规划模型，这就是线性规划的对偶问题。,第二章 线性规划的对偶理论和灵敏度分析,2.3.4 原问题与对偶问题的关系 1. 线性规划问题是对称形式 以上是一对对偶问题，它们之间的关系可以用下表表示。,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,如上例所示，对偶规划之间具有下面的关系： “max，”“min，” “a”“at” “c，b” “b，c” 变量均非负 2.线性规划问题是非对称形式 非对称形式的规划可以按照下面的对应关系直接给出其对偶规划： 将模型统一为“max，”或“min，”。,第二章 线性规

16、划的对偶理论和灵敏度分析,若原规划的某个约束条件为等式，则对偶问题中与此约束对应的那个变量取值没有非负约束。 若原规划的某个约束没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 证明：,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,2.4 对偶问题的基本性质 性质1 对称性 对偶问题的对偶问题是原问题 性质2 弱对偶性 若x*是原问题的可行解，y*是对偶问题的可行解，则存在cx*y*b 性质3 可行解是最优解的情况 设x*是原问题的

17、可行解，y*是对偶问题的可行解，则当cx*=y*b时，x*、y*分别是最优解。,第二章 线性规划的对偶理论和灵敏度分析,性质4 线性规划的对偶原理 （1）若原问题有最优解，那么对偶问题也有最优解，且二者最优值相等（强对偶性质）。 （2）若原问题（对偶问题）的解为无界，则其对偶问题（原问题）无可行解（无界性）。 性质 互补松弛性 若x*，y*分别是原问题和对偶问题的可行解，那么y*xs=0和ysx*=0当且仅当x*、y*为最优解。,第二章 线性规划的对偶理论和灵敏度分析,性质6 假设原问题是：maz z=cx；ax+xs=b；x，xs0；它的对偶问题是：min f=yb；ya-ys=c；y，ys

18、0 则原问题的单纯形表的检验数对应其对偶问题的一个基解。其对应关系如下表所示。 这里ys1是对应原问题中基变量的剩余变量，ys2是对应原问题中非基变量xn的剩余变量。,第二章 线性规划的对偶理论和灵敏度分析,例2.7 判断下面的说法是否正确，为什么？ a. 如果线性规划的原问题存在可行解，则器对偶问题一定存在可行解。 b. 如果线性规划的对偶问题无可行解，则原问题一定无可行解。 c. 在互为对偶的一对线性规划中，不管原问题是极大或极小，原问题的目标函数值一定不超过对偶问题可行解的目标函数值。,第二章 线性规划的对偶理论和灵敏度分析,例2.8 已知线性规划问题 max z=x1+x2 -x1+x

19、2+3x32 -2x1+x2-x31 x1，x2，x30 试用对偶理论证明上述问题有无界解。,第二章 线性规划的对偶理论和灵敏度分析,s.t.,例2.8 已知线性规划问题 min f=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 x1，x2，x3，x4，x50 已知其对偶问题的最优解为y1*=4/5，y2*=3/5，z=5。试利用对偶理论找出原问题的最优解。,第二章 线性规划的对偶理论和灵敏度分析,s.t.,例2.8 已知线性规划问题 max z=2x1+x2+5x3+6x4 2x1+x3+x48 2x1+2x2+x3+2x41

20、2 x1，x2，x3，x40 已知其对偶问题的最优解为y1*=4，y2*=1，试利用对偶理论找出原问题的最优解。,第二章 线性规划的对偶理论和灵敏度分析,2.5 对偶问题的经济学解释影子价格 从对偶定理我们知道，原问题的和对偶问题的最优目标值相等，因此有： z=f=b1y1*+b2y2*+bnym* 其中，y1*，y2*，ym*为其对偶问题的最优解。 从上式我们知道， ，其中z为利润，bi为 企业第i种资源的拥有量。因此，yi*就是每增加一个单位的第i种资源所产生的利润的增加量，我们称为第i种资源的影子价格。它不是市场价格，而,第二章 线性规划的对偶理论和灵敏度分析,是第i种资源在生产中对利润

21、所做的贡献而作的估计。 不同的线性规划模型有不同的影子价格，因此影子价格因企业资源和生产利润状况不同而不同，而市场价格是已知的且相对稳定。 资源的影子价格实际上又是一种机会成本， 在纯市场经济条件下，企业对其拥有的资源的使用可以根据资源的市场价格和影子价格的不同情况而做出不同的考虑： 当某种资源的市场价格高于其影子价格时，可将资源出租或转让。相反当某种资源的市场价格低于其影子价格时，则不宜出租或转让，反而应该从市场上买进该资源，以获得更大的收益。,第二章 线性规划的对偶理论和灵敏度分析,2.6 对偶单纯形法 2.6.1对偶单纯形法的基本思想 在第1章中我们用单纯形法求解时，我们先找到一个初始基

22、本可行解，然后用检验数判别其是否为最优解。若不是，则通过迭代(基变换)找一个新的基本可行解，在迭代的过程保持基本解为基本可行解，再进行判别、迭代，最后使所有的检验数0，使其为最优，也就足说使对偶变量的解为可行解（y*ac，y*）时，得到最优解。 而对偶单纯形法的思路则是保持其对偶变量的解为可行解，即，也就说原问题的解满足最优条件。然后从原问题的一个基本解(此时基本解不一定为基本可行解)出发，检验其是否是可行解的，若是基本可行解，则得最优解，否则进行迭代(基变换)，迭代过程中保持其对偶变量的解为可行解（0），得到一个新的基本解，再判断、迭代，直到求得最优解。,第二章 线性规划的对偶理论和灵敏度分

23、析,对偶单纯形法的应用前提是线性规划问题有一个基，且该基满足： （1）单纯形表的检验行数全部非正（对偶可行）。 （2）变量取值可有负数。 注：通过矩阵行变换运算，使其所有变量均取非负值即得到最优单纯形表。 对于原问题： 令基b=(p1,p2,pm)t，对应的基变量为xb=(x1,x2,xm)。当非基变量都为零时，xb=b-1b。若b-1b中至少有一个负分量，设(b-1b)i0，并且单纯形表的检验数行中的检验,第二章 线性规划的对偶理论和灵敏度分析,数都非正，即对偶问题保持可行解，它的各分量是： （1）对应基变量x1,x2,xm的检验数 i=ci-zi=ci-cbb-1pi=0,i=1,2,m

24、（2）对应非基变量xm+1,xm+2,xn的检验数 i=ci-zi=ci-cbb-1pi=0,i=m+1,m+2,n 每次迭代将基变量中的负分量xl取出，替换非基变量中的xk，基变换保持所有的检验数非正。 2.6.2对偶单纯形法求解线性规划的步骤 （1）建立初始单纯形表，使得所有检验数j0。 （2）检查b列元素，如果所有bi0，则已得到最优解。否则，转入下一步。,第二章 线性规划的对偶理论和灵敏度分析,（3）确定调出变量：设minbi|bi0=bl，第l方程原基变量为调出变量，第l行为主元行。 （4）确定调入变量： ，xk为调入变量，第k列为主元列。 （5）以alk为主元作基迭代运算，方法与单

25、纯形法完全相同，得到单纯形表，返回步骤（2）。 例2.10 求下列线性规划,第二章 线性规划的对偶理论和灵敏度分析,化为标准型： 列初始单纯形表：,第二章 线性规划的对偶理论和灵敏度分析,从上表可以看出：所有的检验数0，因此对应的对偶问题的解是可行的，但b列数字（-3，-5）为负，因此当前解不是最优解。 确定调出变量：min-3，-5=-5，因此x5为调出变量。 确定调入变量： ，因此x2为调入变量。,第二章 线性规划的对偶理论和灵敏度分析,继续上述步骤： 确定调出变量：min-3=-3，因此x为调出变量。 确定调入变量： ，因此x为调入变量。 此时b列全为非负，所有的非基变量检验数0，得最优

26、解x*=(0,3,1,0,0)，最优值z=36。,第二章 线性规划的对偶理论和灵敏度分析,2.11 求线性规划问题,第二章 线性规划的对偶理论和灵敏度分析,对偶单纯形法适合下列线性规划问题： 其中，c0，这样在化为标准型后对约束条件两边同乘以-1，而且目标函数皆0，马上就能得到符合对偶单纯形法条件的初始单纯形表。 从以上求解过程中我们可以看出对偶单纯形法有以下优点： （1）初始解可以是非可行解，当检验数为负时，就可以进行基变换，这时就不用加入人工变量，因此可以简化计算。,第二章 线性规划的对偶理论和灵敏度分析,（2）当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作

27、量，因此对于变量较少而约束条件很多的线性规划问题，可以先将它转化为对偶问题，然后用对偶单纯形法进行求解。 （3）在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。对偶单纯形法的局限性在于：对大多数的线性规划问题，很难找到一个初始可行基，因此这个方法在求解线性规划问题时很少单独使用。,第二章 线性规划的对偶理论和灵敏度分析,2.7 灵敏度分析 线性规划的灵敏度是在求出最优解之后，研究线性规划模型中各相关参数的变化对最优解的影响，它在应用线性规划解决实际问题的过程中起着非常重要的作用。 在建立线性规划数学模型的过程中，我们对实际问题进行了归纳、分析和假设，忽略了某些次要因素，而选取

28、了一组确定的参数来建立模型，并求出最优解。实际上这些参数往往可以在一定的范围内发生变化，因此必须研究和讨论这些变化对最优解带来的影响。 另一方面，人们可能对已经解出的目标函数值并不满意，想通过修改模型的某些参数使目标函数值进一步优化，这也需要用到灵敏度分析。,第二章 线性规划的对偶理论和灵敏度分析,灵敏度分析主要是应用单纯形表格的特殊结构，也就是我们在前面已经讨论过的单纯形表的矩阵形式。,第二章 线性规划的对偶理论和灵敏度分析,下面我们通过一个具体的例子来讨论线性规划的灵敏度分析。 例2.12 设某工厂甲、乙两种原料生产a、b、c三种产品，每种产品的单位利润及原料消耗定额等如下表。 试问如何安

29、排生产可使总利润最大？,第二章 线性规划的对偶理论和灵敏度分析,解：设a、b、c三种产品的产量为x1、x2、x3吨，则线性规划模型为： 初始单纯形表如下：,第二章 线性规划的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,最优解为：a产品生产30吨，b产品生产10吨，最大利润为150万元。,一、约束条件右边常数b的变化 在单纯形表的矩阵形式最优表中，可以看到，约束条件右边常数b的变化仅影响到最优表中解所在的列。我们可以通过重新计算b-1b和cbb-1b得到新的表。这种影响可分为两种情况。 1.当新的解b-1b0时，它仅改变最优解的值，而不改变最优解的基变量，即不影响到新解的可行性

30、。 2.当新的解b-1b0时，此解已不满足变量的非负约束，变为不可行解，此时影响到解的可行性，我们需采用对偶单纯形法求出新的最优解。,第二章 线性规划的对偶理论和灵敏度分析,在上例中，如果甲原料的供应量增加，乙原料的供应量增加（、可正可负），则原最优表中解的列将发生变化，可重新计算如下： 我们先讨论甲原料供应量的变化，即=0，则为使可行解仍为可行，则必须有：,第二章 线性规划的对偶理论和灵敏度分析,当甲原料供应量的变化10吨时，当前的解就不可行了，我们需用对偶单纯形法求出新的最优解。例如，=20，则： 将原问题最优表中解所在的列用上述数据代替，得如下单纯形表：,第二章 线性规划的对偶理论和灵敏

31、度分析,上表的可行条件不满足，但是满足最优条件，故可用对偶单纯形法求出新的最优解，调出x2，调入x3，计算后得：,第二章 线性规划的对偶理论和灵敏度分析,从上表可得最优解：x1=30，x2=0，x3=20，max z=160。此时还可以发现有可选择的最优解，调入s1，调出x3，计算后得下表： 得到可选择的最优基本可行解：x1=40，x2=0，x3=0，max z=160。 类似地，可对乙原料的供应量进行分析，亦可同时对甲、乙两种原料的供应量进行分析。,第二章 线性规划的对偶理论和灵敏度分析,二、目标函数中决策变量cb、cn、ci的变化 在单纯形表的矩阵形式最优表中，可以看到目标函数中变量系数c

32、b、cn、ci的变化，仅影响到最优表目标方程行。我们可通过重新计算cbb-1n-cn，cbb-1-ci，得到新的表。这种变化可分为两种情况： 1.当计算出的cbb-1n-cn，cbb-1-ci仍满足最优条件时，原来的最优解不变，最优的目标函数值做相应的调整。 2.当计算出的cbb-1n-cn，cbb-1-ci不满足最优条件，则可利用单纯形法进一步迭代，求出新的最优解与最优值。 如果仅有cn、ci发生变化改变，则对最优表的影响就更小了。而且计算cbb-1n-cn，cbb-1-ci也变得十分容易，即只要减去cn、ci的变化量即可。,第二章 线性规划的对偶理论和灵敏度分析,原问题中，a、b、c三种产

33、品的单位利润分别为4、3、2，而最优解为x1=30，x2=10，x3=0，最大利润为150万元。c产品之所以不生产，是因为相对其原料消耗，它的单位利润太低。它在最优表中的检验数为： cbb-1n-cn=cbb-1n-2=1/2 若c产品的单位利润增加,它在最优表中的检验数变为： cbb-1n-2-=1/2- 当=1/2时，检验数为0，此时，虽不能增加目标函数利润的值，但x3已可作为可选择的最优解，调入基，也就是说，我们可以得到生产产品c的可选择的最优解。此时最优表如下：,第二章 线性规划的对偶理论和灵敏度分析,在上表中调入x3，调出x1，计算后得下表： 得到可选择的最优解：x1=0，x2=25

34、，x3=30，最大利润仍为150万元。,第二章 线性规划的对偶理论和灵敏度分析,当=1时，即c产品的单位利润由2万元增加到3万元时，其检验数为-1/2，则原来的解已经不是最优解了，此时的最优表如下： 在上表中调入x3，调出x1，计算后的下表：,第二章 线性规划的对偶理论和灵敏度分析,得到最优解x1=0，x2=25，x3=30，最大利润达到165万元，超过原解中的150万元。 对cb的变化可以做类似的讨论。 三、约束条件左边变量系数n的变化 在单纯形表矩阵形式最优表中可以看到，约束条件左边变量系数有b与n两部分，而b的变化将引起b-1的变化，从而影响到整个最优表的变化。因为最优表中各部分的计算几

35、乎都要用到b-1，如此复杂的变化已使灵敏度分析失去意义，不如重新计算新的问题。因此这里只讨论n的变化，n的变化只影响到xn所在的列，影响到b-1n与cbb-1n-cn。,第二章 线性规划的对偶理论和灵敏度分析,1.当cbb-1n-cn仍满足最优条件时，则这种变化不影响已求出的最优解。 2.当cbb-1n-cn不满足最优性条件时，则需要进一步进行单纯形法迭代，以求出新的最优解。 仍以例2.12为例，其n的变化，相当于改变c产品对原料消耗的定额。设每生产1吨产品c需消耗原料甲、乙从（1，1）t吨，改变为（1+，1+）t吨，则最优表中x3所在的列中，b-1n，cbb-1n-cn为：,第二章 线性规划

36、的对偶理论和灵敏度分析,第二章 线性规划的对偶理论和灵敏度分析,为简单起见，不妨设原料乙的消耗定额不变，即=0，由上式可以看出，当=-1/2时，cbb-1n-cn，这说明当原料甲的消耗减少1/2时，产品c可作为作为可选择的最优解而进行生产，此时的最优利润保持150万元不变。将上述数据代替最优表中x3所在的列，得到如下单纯形表。,在上表中调入x3，调出x1，计算后得到下表。 可选择的解是：x1=0，x2=10，x3=60，最大利润仍为150万元。 当=-3/4时，即产品c的甲原料消耗定额减少3/4时，cbb-1n-cn=-1/4，已不满足最优性条件，原解已经不是最优解，需将x3调入，进一步进行迭

37、代。,第二章 线性规划的对偶理论和灵敏度分析,在上表中调入x3，调出x2，计算后的下表： 在上表中最优解是：x1=20，x2=0，x3=40，最大利润为160万元。此时显然还有可选择的最优解，将s1调入，,第二章 线性规划的对偶理论和灵敏度分析,x1调出，即得到可选择的最优解为：x1=0，x2=0，x3=80，最大利润仍为160万元。此时对偶问题的最优解为（0，2），即原料甲的影子价格为0，说明原料甲可能有剩余。 有关的变化以及、同时变化，均可类似地讨论。 四、加入新的决策变量 在原线性规划模型中增加新的变量可以看成是同时改变一个非基变量在目标函数和约束条件中的系数，看成是改变一个开始时全为零

38、的非基变量的系数。所以，这种情况类似于前面讨论的的二、三部分。它只能影响到问题的最优性条件。增加新的决策变量只有在它能改进目标函数被调入基时才有实现的意义，否则，新增的变量也就成为取值为零的非基变量，而无太多的实际意义。,第二章 线性规划的对偶理论和灵敏度分析,在例2.12中若开发出第四种产品d，它的单位利润是5万元，对原料甲与乙的单位消耗分别为2吨和3吨。试问是否应生产d，以取得更大的利润？ 设生产d的产量为x4，则原最优表中，x4的系数应为cbb-1n-cn和b-1n，即： 由于x4的检验数cbb-1n-cn=3/20，仍满足最有条件，故x4只能为非基变量等于零，即不生产d，原最优解不变。,第二章 线性规划的对偶理论和灵敏度分析,如想要生产d，则必须提高它的单位利润或降低他的原料消耗。 如果d的单位利润提高到6.5万元，则相应地： cbb-1n-cn=0 此时x4可作为可选择的调入变量，但它不会增加总的利润。在原最优表中增加一列x4，并将上面计算的数据列入，得如下的淡出形表：,第二章 线性规划的对偶理论和灵敏度分析,在上表中调入x4，调出x1，计算后得到下表： 可选择的最优解：x1=0，x2=35/2，x3=0，x4=15，最大利润仍为150万元。 如果产品d的单位利润提高到8.5万元，则： cbb-1n-cn=-2 这时必须将x4调入，以获得更大的利润。