第2章对偶理论和灵敏度分析(精品).ppt

（本科版（本科版）运筹学运筹学运筹学教材编写组编清华大学出版社第2章对偶理论和灵敏度分析第1节单纯形法的矩阵描述第2节 改进单纯形法第3节 对偶问题的提出第4节 线性规划的对偶理论第5节 对偶问题的经济解释影子价格第6节 对偶单纯形法第7节 灵敏度分析第8节*参数线性规划单纯形原理的矩阵描述单纯形原理的矩阵描述 设标准的线性规划问题为设标准的线性规划问题为minz=CTXs.t.AX=bX 0矩阵矩阵A可以分块记为可以分块记为A=B，N 相应地，向量相应地，向量X和和C可以记为可以记为AX=b可以写成BXB+NXN=b即XB=B-1b-B-1NXN对于一个确定的基B，目标函数z可以写成目标函数z用非基变量表出的形式单纯形表的结构小结1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。第2章对偶理论和灵敏度分析第2节改进单纯形法改进单纯形主要用于计算机求解时,节省计算量和节约内存占用,一般不在手工计算时采用。由于在单纯形迭代时只有一个变量换入和换出，在相关计算时也设法只计算一列。求解线性规划问题的关键是计算以下介绍一种比较简便的计算方法第2章对偶理论和灵敏度分析第3节对偶问题的提出第3节对偶问题的提出对偶是什么：对同一事物（或问题），从不同的角度（或立场）提出对立的两种不同的表述。例如在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。（1）周长一定，面积最大的矩形是正方形。（2）面积一定，周长最短的矩形是正方形。这是互为对偶关系的表述。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。第1章例1的不同表述现从另一角度来讨论这个问题。假设该工厂的决策者决定不生产产品、，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品，可获利2元，那么生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润，这就有y1+4y22同理将生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润，这就有2y1+4y33把工厂所有设备台时和资源都出租或出让，其收入为 =8y1+16y2+12y3从工厂的决策者来看当然愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题称这个线性规划问题为例1线性规划问题(这里称原问题)的对偶问题。min=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0，i=1,2,3 (2-8)这就是从另一角度提出的线性规划问题。进一步讨论它们之间的关系从第1节得到检验数的表达式是CN-CBBN-1与-CBB-1在第1章已提到，当检验数CN-CBBN-10(2-9)-CBB-10(2-10)这表示线性规划问题已得到最优解。也是作为得到最优解的判断条件。现在讨论这两个条件。(1)(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘子，用符号Y=CBB-1表示。由(2-10)式，可得到Y0(2)对应基变量XB的检验数是0。它是CB-CBB-1B=0。包括基变量在内的所有检验数可用C-CBB-1A0表示。从此可得C-CBB-1A=C-YA0移项后，得到YAC(3)Y由(2-10)式，得到-Y=-CBB-(2-11)将(2-11)式两边右乘b，得到-Yb=-CBB-1b(2-12)Yb=CBB-1b=z因Y的上界为无限大，所以只存在最小值(4)从这里可以得到另一个线性规划问题min=YbYACY0称它为原线性规划问题maxz=CXAXb，X0的对偶规划问题对偶规划问题例生产计划问题某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。产品产品车间车间工时单耗工时单耗甲甲乙乙生产能力生产能力ABC10023481236单位产品获利单位产品获利35(1)(1)决决策策变变量量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。(2)(2)约约束束条条件件。生产这两种产品受到现有生产能力的制约，用量不能突破。生产单位甲产品的零部件需耗用A车间的生产能力1工时，生产单位乙产品不需耗用A车间的生产能力，A车间的能力总量为8工时，则A车间能力约束条件表述为 x18同理，B和C车间能力约束条件为2x212 3x1+4x236建立模型建立模型(3)(3)目标函数目标函数。目标是利润最大化，用Z表示利润，则 maxZ=3x1+5x2(4)(4)非非负负约约束束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0，x2 0综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 maxZ=3x1+5x2 x182x212 3x1+4x236 x1 0,x2 0若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？问题的最优解：x1=4，x2=6，Z*=42。一、对偶问题一、对偶问题第二个问题：出让定价第二个问题：出让定价假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有y1+0y2+3y33同理，对乙产品而言，则有 0y1+2y2+4y35设备台时出让的收益（希望出让的收益最少值）min=8y1+12y2+36y3显然还有 y1，y2，y30对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=42两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。例例1的对偶问题的数学模型的对偶问题的数学模型min=8y1+12y2+36y3 y1+0y2+3y33 0y1+2y2+4y35 y1，y2，y30 S.t.maxZ=3x1+5x2 x182x212 3x1+4x236 x1,x2 0对偶的定义对偶的定义 定义定义设以下线性规划问题设以下线性规划问题Maxz=CTXs.t.AXb(P)X0为原始问题，则称以下问题为原始问题，则称以下问题Minz=bTWs.t.ATWC(D)W0为原始问题的对偶问题。为原始问题的对偶问题。例例max Z=4x1+7x2s.t.3x1+5x26x1+2x28x1,x20(P)minW=6w1+8w2s.t.3w1+w245w1+2w27w1,w20(D)第2章对偶理论和灵敏度分析第4节线性规划的对偶理论从理论上讨论线性规划的对偶问题原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2min=360y1+200y2+300y39X1+4X23609y1+4y2+3y3704X1+5X22004y1+5y2+10y31203X1+10X2300y10,y20,y30X10X20对偶规则原问题一般模型：对偶问题一般模型：maxZ=CXmin=YbAXbYACX0Y0对偶规则原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反对偶规则.原问题对偶问题目标函数maxmin目标函数约束条件=变量无约束变量符号无约束约束条件=对偶规则简捷记法原问题标准则对偶问题标准原问题不标准则对偶问题不标准例max=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y332x1+x2-4x3+x4+3x57y1+3y32x1+2x3-x44-4y1+2y2-6-x1+3x2-x4+x5=-2y1-y2-y30 x1，x2，x30;3y1+y3=1x40;x5无限制y10y20y3无约束例例maxz=8x1+5x2s.t.-x1+2x243x1-x2=72x1+4x28x10,x20minw=4y1+7y2+8y3s.t.-y1+3y2+2y382y1-y2+4y35y10,y2:unry304.1原问题与对偶理论原问题（LP）：对偶问题(DP)标准型原问题与对偶问题的关系例2根据表2-3写出原问题与对偶问题的表达式。表2-3 x y x1x2x2y1111y2222y3888c444标准形式的变换关系为对称形式原问题（LP）对偶问题(DP)非对称形式的变换关系原问题的约束条件中含有等式约束条件时，按以下步骤处理。设等式约束条件的线性规划问题第一步：先将等式约束条件分解为两个不等式约束条件。第二步：按对称形式变换关系可写出它的对偶问题设yi是对应(2-13)式的对偶变量 yi是对应(2-14)式的对偶变量。这里i=1,2,，m将上述规划问题的各式整理后得到综合上述，线性规划的原问题与对偶问题的关系，其变换形式归纳为表2-4中所示的对应关系。例3 试求下述线性规划原问题的对偶问题则由表2-4中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题，4.2 对偶问题的基本性质(1)对称性对偶问题的对偶是原问题;(2)弱对偶性 若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb;(3)无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解;(4)可行解是最优解时的性质;(5)对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等;(6)互补松弛性;(7)原问题检验数与对偶问题解的关系.(1)对称性对偶问题的对偶是原问题证设原问题是maxz=CX;AXb；X0根据对偶问题的对称变换关系，可以找到它的对偶问题是min=Yb;YAC；Y0若将上式两边取负号，又因min=max(-)可得到max(-)=-Yb;-YA-C；Y0根据对称变换关系，得到上式的对偶问题是min(-)=-CX；-AX-b;X0又因min(-)=max可得max=maxz=CX；AXb;X0这就是原问题。证毕。(2)弱对偶性 证明：(3)无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解 证：由性质（2）可知，例：从两图对比可明显看到原问题无界，其对偶问题无可行解y1y2(4)可行解是最优解时的性质 设是原问题的可行解，是对偶问题的可行解，当时，是最优解。证明：(5)对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。互补松弛定理互补松弛定理若若原问题原问题LPLP与对偶问题与对偶问题DPDP的可行解的可行解 与与 分分别最优解的充分必要条件为：别最优解的充分必要条件为：其中其中X XS S和和Y YS S分别为原问题分别为原问题LPLP和对偶问题和对偶问题DPDP的的松弛向量。松弛向量。(6)互补松弛性将原问题目标函数中的系数向量C用C=YA-YS代替后，得到z=(YA-YS)X=YAX-YSX (2-15)将对偶问题的目标函数中系数列向量b，用b=AX+XS代 替 后，得 到 =Y(AX+XS)=YAX+YXS (2-16)(7)原问题检验数与对偶问题解的关系设原问题是maxz=CX;AX+XS=b;X,XS0它的对偶问题是min=Yb;YA-YS=C;Y,YS0则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表2-5。表2-5对应关系YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。证:设B是原问题的一个可行基，于是A=(B,N)；原问题可以改写为maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS0相应地对偶问题可表示为min=YbYB-YS1=CB(2-17)YN-YS2=CN(2-18)Y，YS1,YS20这里YS=(YS1，YS2)。当求得原问题的一个解：XB=B-1b其相应的检验数为CN-CBB-1N与-CBB-1现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1，将它代入(2-17)式，(2-18)式得YS1=0,-YS2=CN-CBB-1N证毕例4 已知线性规划问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。先将其变换为对偶问题。上述问题的对偶问题为min=2y1+y2-y1-2y21y1+y21y1-y20y1，y20由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但最优解。例5 已知线性规划问题min=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20将y1*=4/5,y2*=3/5的值代入约束条件，得=1/53，=17/55，=7/50得到x4=0由y40得到x2=0由y50得到x3=0因此原始问题的约束条件x1+x2-x4=1x1+2x2+x3-x5=-1成为x1=1x1-x5=-1由此得到由此得到x1=1，x5=2即原始问题的最优解为即原始问题的最优解为X=(x1，x2，x3，x4，x5)T=(1，0，0，0，2)Tz=6以上是理解对偶单纯形法的理论基础第2章对偶理论和灵敏度分析第5节对偶问题的经济解释影子价格在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN-CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?设B是maxz=CXAXb，X0的最优基，由-Yb=-CBB-1b(2-12)式可知z*=CBB-1b=Y*b。对z求偏导数，得由上式可知，变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。cj23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由移至，相应的最优解由(4，2)变为(4，2.5)，目标函数z=24+32.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由移至，相应的最优解从(4，2)变 为(4.25，1.875)，目 标 函 数 z=4.25+31.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由移至，这时的最优解不变。图2-1yi*的值代表对第i种资源的估价-影子价格。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。对偶变量yi在经济上表示原问题第i种资源的边际价值边际价值。对偶变量的值yi*所表示的第i种资源的边际价值，称为影子价值影子价值。若原问题的价值系数Cj表示单位产值，则yi 称为影子价格影子价格。若原问题的价值系数Cj表示单位利润，则yi 称为影子利润影子利润。对偶问题的经济解释对偶问题的经济解释影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。对资源i总存量的评估：购进购进 or出让出让对资源i当前分配量的评估：增加增加 or减少减少它表明了当前的资源配置状况，告诉经营者应当优先增加何种资源，才能获利更多。告诉经营者以怎样的代价去取得紧缺资源。提示设备出租或原材料转让的基价。告诉经营者补给紧缺资源的数量，不要盲目大量补给。借助影子价格进行内部核算。特别注意特别注意对偶最优解的经济解释影子价格结合影子价格：y1=0，y2=1/2，y3=1，y1=0:第一种资源过剩，y3=1最紧张。影子价格所含的信息：1、资源紧缺状况2、确定资源转让基价3、取得紧缺资源的代价利润最大化问题影子价格的经济解释利润最大化问题影子价格的经济解释每一种资源的影子价格每一种资源的影子价格=当该资源当该资源增加一个单位时，总利润增加一个单位时，总利润Z的增加的增加量量每一种需求的影子价格每一种需求的影子价格=当该需求当该需求增加一个单位时，总成本增加一个单位时，总成本Z的增加的增加量量问题：问题：每种资源的价值如何？每种资源的价值如何？应如何定价？应如何定价？与市场采购价关系如何？与市场采购价关系如何？影子价格的引入影子价格的引入第6节偶单纯形法前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。LP可行解可行解DP可行解可行解当当LP与与DP均为可行时，均为可行时，LP与与DP均得到最优解均得到最优解单纯形方法：单纯形方法：保持保持LP可行的同时，可行的同时，逐步将逐步将DP变可行变可行对偶单纯形方法：对偶单纯形方法：保持保持DP可行的同时，可行的同时，逐步将逐步将LP变可行变可行根据对偶问题的对称性可以这样考虑：若保持对偶问题的解是基可行解，即cj-CBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。方法如下：设原问题maxz=CXAX=bX0又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为XB=(x1，x2，,xm)当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是(1)对应基变量x1，x2，,xm的检验数是i=ci-zi=ci-CBB-1Pj=0，i=1,2,m(2)对应非基变量xm+1，xn的检验数是j=cj-zj=cj-CBB-1Pj0，j=m+1,n每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。对偶单纯形法的计算步骤如下：(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量(3)确定换入变量在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止计算。若存在lj0(j=1,2,，n),计算按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4)以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。例6用对偶单纯形法求解min=2x1+3x2+4x3x1+2x2+x332x1-x2+3x34x1，x2，x30解解先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3-x1-2x2-x3+x4 =-3-2x1+x2-3x3 +x5=-4xj0，j=1,2,5例6的初始单纯形表，见表2-6。从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。换出变量的确定：按上述对偶单纯形法计算步骤(2)，即按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算min(-3,-4)=-4故x5为换出变量。换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止计算。计算故x1为换入变量。换入、换出变量的所在列、行的交叉处“-2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。表2-7表2-8表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第7节灵敏度分析以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。灵敏度分析的意义灵敏度分析的意义灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。灵敏度分析就是研究最优解对数据变化的敏感程度。感性太强，则说明最优解的稳定性程度较低。灵敏度分析解决的问题：参数在什么范围变化而最优基不变。已知参数的变化范围，考察最优解(最优基)是否改变。灵敏度分析的概念灵敏度分析的概念灵敏度分析目的灵敏度分析目的灵敏度分析所要解决的问题：灵敏度分析所要解决的问题：系系数数在在什什么么范范围围内内变变化化，不不会会影影响响已已获得的最优基获得的最优基。如如果果系系数数的的变变化化超超过过以以上上范范围围，如如何何在原来最优解的基础上求得新的最优解在原来最优解的基础上求得新的最优解当当线线性性规规划划问问题题增增加加一一个个新新的的变变量量或或新新的的约约束束，如如何何在在原原来来最最优优解解的的基基础础上上获得新的最优解。获得新的最优解。基本方法(1)对照原来问题的单纯形表和最终单纯形表,求基变换矩阵;(2)根据需要做灵敏度分析的的要求,刷新初始单纯形表;(3)根据基变换矩阵对原来的最终单纯形表进行刷新;(4)根据最优性条件,检验原来最优解的性质(是否最优?是否可行?),决定是否继续计算,若继续计算,用单纯形法或对偶单纯形法?可行和最优判定主要检查检验数行和b列(对偶问题检验数)线性规划问题中某一个或几个系数发生变化显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况进行处理。原问题对偶问题结论和进一步计算步骤可行可行最优解不变可行非可行单纯形继续迭代非可行可行对偶继续迭代非可行非可行引进人工变量,继续迭代表2-97.1 资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这里b=(0,，br,0,，0)T。只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定。B-1是最终计算表中的最优基的逆b列的元素变化例如求第1章例1中第二个约束条件b2的变化范围。解：可以利用第1章例1的最终计算表中的数据：可计算b2：由上式，可得b2-4/0.25=-16，b2-4/0.5=-8，b22/0.125=16。所以b2的变化范围是-8，16；显然原b2=16，加它的变化范围后，b2的变化范围是8，32。例7 从表1-5得知第1章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品，。求这时该厂生产产品，的最优方案。解先计算B-1b,将结果反映到最终表1-5中，得 表2-10。由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。表2-11即该厂最优生产方案应改为生产4件产品，生产3件产品，获利z*=42+33=17(元)从表2.11看出x3=2，即设备还有2小时未被利用7.2目标函数中价值系数cj的变化分析可以分别就cj是对应的非基变量和基变量两种情况来讨论。(1)若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是j=cj-CBB-1Pj或当cj变化cj后，要保证最终表中这个检验数仍小于或等于零，即j=cj-CBB-1Pj0那么cj+cjYPj，即cj的值必须小于或等于YPj-cj，才可以满足原最优解条件。这就可以确定cj的范围了。cr可变化的范围例8 试以第1章例1的最终表表1-5为例。设基变量x2的系数c2变化c2，在原最优解不变条件下，确定c2的变化范围。解解 这时表1-5最终计算表便成为表2-12所示。若保持原最优解，从表2-12的检验数行可见应有由此可得c2-3 和c21。c2的变化范围为-3c21即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。7.3技术系数ij的变化分两种情况来讨论技术系数ij的变化，下面以具体例子来说明。例9分析在原计划中是否应该安排一种新产品。以第1章例1为例。设该厂除了生产产品，外，现有一种新产品III。已知生产产品III，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。问该厂是否应生产该产品和生产多少?解解分析该问题的步骤是：(1)设 生 产 产 品 II为 x3台，其 技 术 系 数 向 量P3=(2,6,3)T，然后计算最终表中对应x3的检验数3=c3-CB-13=5-(1.5,0.125,0)(2,6,3)T=1.250说明安排生产产品III是有利的。分析该问题的步骤(2)是：表2-13(a)由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。分析该问题的步骤(3)是：(3)将x3作为换入变量，x5作为换出变量，进行迭代，求出最优解。计算结果见表2-13(b)，这时得最优解：x1=1,x2=1.5，x3=2。总的利润为16.5元。比原计划增加了2.5元。表2-13(b)例10分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?解 把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。同时计算出x1的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1的列向量位置.得表2-14。表2-14可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15表2-15表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。例11 假设例10的产品的技术系数向量变为P1=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案?解解方法与例10相同，以x1代替x1，并计算列向量x1的检验数为c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T=-2.625。将这些数字填入最终表1-15的x1列的位置，得到表2-16。表2-16将表2-16的x1变换为基变量，替换x1，得表2-17。表2-17从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行，用方程表示时为0 x1+x2+0.5x3-0.4x4+0 x5=-2.4引入人工变量x6后，便为-x2-0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表2-17，得到表2-18。表2-18这时可按单纯形法求解。X4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品，0.667单位；产品，2.667单位，可得最大利润10.67元。表2-19除以上介绍的几项分析以外，还可以作增减约束条件等分析。留给读者自己考虑。第第8 8节节*参数线性规划参数线性规划灵敏度分析时，主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。而参数线性规划是研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：(1)对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解；(2)用灵敏度分析法，将参变量t直接反映到最终表中；(3)当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若在b列首先出现某负值时，则以它对应的变量为换出变量；于是用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代一步；(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。8.1 8.1 参数参数c c的变化的变化例12 试分析以下参数线性规划问题。当参数t0时的最优解变化。解 将此模型化为标准型令t=0，用单纯形法求解的结果，见表2-20。将c的变化直接反映到最终表2-20中，得表2-21。计算t的变化范围当 t值变化，在40，即0t9/7时，为最优解(2,6,2,0,0)T；当 t值增大，t(3/2)/(7/6)=9/7时，在检验数行首先出现40；表示还可以继续改进。t=9/7为第一临界点。当t9/7时，40，这时x4作为换入变量。用单纯形法迭代一步，得表2-22。当t继续增大t(5/2)/(1/2)=5时，在检验数行首先出现50，在50，即9/7t5时，得最优解(4,3,0,6,0)T。t=5为第二临界点。当t5时，50，这时x5作为换入变量，用单纯形法迭代一步，得表2-23。t 继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。8.2 8.2 参数参数b b的变化分析的变化分析例13分析以下线性规划问题，当t0时，其最优解的变化范围。解解 将上述模型化为标准型令t=0，用单纯形法迭代两次，求解的结果，见表2-24。将此计算结果反映到最终表2-24，得表2-25。在表2-25中进行分析，当t增大至t2时，则b0；即0t2时，最优解为(2-t.4,0,0)T。当t2时，则b10；故将x1作为换出变量，用对偶单纯形法迭代一步，得表2-26结论从表2-26可见，当t6时，问题无可行解；当2t6时，问题的最优解为(0，6-t，0，-6+3t)T。