第五讲线性规划灵敏度分析

第五讲线性规划灵敏度分析2023/4/151第1页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析一.目标函数系数的变化二.约束右端常数项的变化三.系数矩阵A的变化四.用Excel进行灵敏度分析2023/4/152第2页，共30页，2023年，2月20日，星期一一、目标函数系数的变化第五讲线性规划灵敏度分析价值系数c发生变化：考虑检验数j=cj–CBB-1Pj，

j=1,2,……,n1.若cj是非基变量的系数：设cj变化为cj

+

cj

：则j’=cj

+cj–CBB-1Pj=j+cj若使当前最优解不变，则j’≤0即：cj

+cj≤CBB-1Pj=YPj2023/4/153第3页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析一、目标函数系数的变化1.若cj是非基变量的系数：例题Maxz=-2x1-3x2-4x3S.t.-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4

x1,x2,x3,x4,x5≥02023/4/154第4页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析1.若cj是非基变量的系数：

从表中看到σ3=c3+Δc3-(c2×a13+c1×a23)可得到Δc3≤9/5时，原最优解不变。2023/4/155第5页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析一、目标函数系数的变化2.若cr是基变量的系数：因cr∈CB，当cr变化Δcr时，就引起CB的变化，这时

(CB+ΔCB)B-1A=CBB-1A+(0，…，Δcr，…，0)B-1A=CBB-1A+Δcr(αr1,αr2,…，αrn)

可见，当cr变化Δcr后，最终表中的检验数是

σj′=cj−CBB-1Pj−Δcr

a’rj，j=1,2,…，n

若要求原最优解不变，即必须满足σj′≤0。于是得到:2023/4/156第6页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析一、目标函数系数的变化2.若cr是基变量的系数：Δcr可变化的范围是:2023/4/157第7页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析一、目标函数系数的变化例试以例1的最终表为例。

设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。

解：这时最终计算表便成为下表所示。2023/4/158第8页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析若保持原最优解，从上表的检验数行可见应有

由此可得Δc2≥−4和Δc2≤2。

Δc2的变化范围为−4≤Δc2≤2

即x2的价值系数c2可以在［0，6］之间变化，而不影响原最优解。一、目标函数系数的变化2023/4/159第9页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为：XB′=B-1(b+Δb)

这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。2023/4/1510第10页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。2023/4/1511第11页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化新的最优解的值可允许变化范围用以下方法确定。在最终表中求得的经过变化后的b列的所有元素，要求：于是得到：2023/4/1512第12页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化例如求例1中第二个约束条件b2的变化范围。解：可以利用例1的最终计算表中的数据：00-21/2141001/404011/2-1/802x1x5x2304B－1bXBCBx1x2x3x4x5θcj→2023/4/1513第13页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化可计算Δb2：由上式，可得Δb2≥−4/0.25=−16，Δb2≥−4/0.5=−8，b2≤2/0.125=16。所以Δb2的变化范围是［−8，16］；显然原b2=16，加它的变化范围后，b2的变化范围是［8，32］。2023/4/1514第14页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析二、约束右端常数项的变化练习题：从例1中，若该厂又从其他处抽调4个单位的原材料用于生产产品甲，乙。求这时该厂生产产品甲，乙的最优方案。2023/4/1515第15页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析三、系数矩阵A的变化1.A中某个元素的变化：若系数矩阵中aij变化了△aij

，且它是非基变量的系数列向量的分量。而在单纯形最终计算表中，非基变量xj的检验数为：则：故：2023/4/1516第16页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析三、系数矩阵A的变化2.A中某列向量的变化：若系数矩阵A中某一列向量Pj发生了变化，且其对应的变量xj为非基变量，那么Pj的变化仅影响起自身的检验数。如果，则说明变化后并不影响当前解；如果，则说明变化后影响当前解，需重新迭代；若系数矩阵A中某一列向量Pj发生了变化，且其对应的变量xj为基变量，则需恢复该列向量为单位列向量后，再处理。2023/4/1517第17页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析例：分析原计划生产产品的工艺结构发生变化。仍以例1为例，若原计划生产产品甲的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(1,2,0)T，试分析对原最优计划有什么影响?同时计算出变化后的检验数为：c1−CBB-1P1′=0.5将以上计算结果填入最终表x1的列向量位置，得下表。三、系数矩阵A的变化2.A中某列向量的变化：解：变化后的系数列向量记为P1′，则其在最终表的列向量数字为：2023/4/1518第18页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析0-1/4-201/2cj-zj

0101/41/2-1/80-21/20011/2-11/4442x1x5x2304x5x4x3x2x1B－1bXBCB00043cj→0-1/2-200

cj-zj

0101/21-1/40-21/20011008120x1x5x2304x5x4x3x2x1B－1bXBCB00043cj→由上表可得：原问题和对偶问题都得到了最优解。2023/4/1519第19页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析三、系数矩阵A的变化2.A中某列向量的变化：例：仍以例1为例，若原计划生产产品甲的工艺结构有了改进，这时有关它的技术系数向量变为P1′=(4,4,2)T，试分析对原最优计划有什么影响?解：变化后的系数列向量记为P1′，则其在最终表的列向量数字为：将以上计算结果填入最终表x1的列向量位置，得下表。2023/4/1520第20页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析0-1/4-200.5cj-zj

0101/41/2-1/80-21/20011-43/2442x1x5x2304x5x4x3x2x1B－1bXBCB00043cj→恢复P1为单位列向量，得到下表：05/4-200cj-zj

0101/43/2-1/20-21/2001100420-4x1x5x2304x5x4x3x2x1B－1bXBCB00043cj→2023/4/1521第21页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析05/4-200cj-zj

0101/43/2-1/20-21/2001100420-4x1x5x2304x5x4x3x2x1B－1bXBCB00043cj→分析知：应在第三个约束条件中加入人工变量，即：

001/2M-3/4-1/2M-M+40cj-zj

0010101/43/21/20-2-1/200-11004204x1x5x630-M

x6x5x4x3x2x1B－1bXBCB

-M00043cj→2023/4/1522第22页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析由上表可得：原问题得到了最优解。

-M+3/200-3/45/20cj-zj

-1/2-320100011/4-1/2-11/23-2100288x1x5x4300

x6x5x4x3x2x1B－1bXBCB

-M00043cj→

-M+4-5/60-7/300cj-zj

0-10-1/61/32/30011/3-1/6-4/30101002/38/340/3x1x2x4340

x6x5x4x3x2x1B－1bXBCB

-M00043cj→2023/4/1523第23页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析三、系数矩阵A的变化3.A中增加一列或一行的变化：例以例1为例。设该厂除了生产产品甲，乙外，现有一种新产品丙。已知生产产品丙，每件需消耗原材料及设备A，B的数量分别为2个单位，4h，2h；每件可获利6元。问该厂是否应生产该产品和生产多少?解：分析该问题的步骤是：

(1)设生产产品丙为x6台，其技术系数向量P6=(2,4,2)T，然后计算最终表中对应x6的检验数为：说明安排生产产品丙是有利的。2023/4/1524第24页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析

(2)设分析应安排生产的方案：填入到最终单纯形表中可得：

10-1/4-200cj-zj

101/20101/41/2-1/80-21/2001100442x1x5x2304

x6x5x4x3x2x1B－1bXBCB

600043cj→2023/4/1525第25页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析

10-1/4-200cj-zj

101/20101/41/2-1/80-21/2001100442x1x5x2304

x6x5x4x3x2x1B－1bXBCB

600043cj→

00-1/2-20-1cj-zj

1000101/41/2-1/40-21/200110-1/2440x6x5x2604

x6x5x4x3x2x1B－1bXBCB

600043cj→由上表可得：原问题得到了最优解。2023/4/1526第26页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析例仍以例1为例。若企业为了提高产品质量，考虑给产品甲、乙增加一道精加工工序，并在设备C上进行加工。甲、乙两种产品在C上的单位加工台时分别为（2，4）。已知设备C的可用工作时间为12个台时，试问增加这道精加工工序以后，对原最优计划方案有何影响?三、系数矩阵A的变化3.A中增加一列或一行的变化：解：增加一道工序等于增加一个约束条件，表达式为：即：则以该松弛变量为基变量，得到新单纯形表为：2023/4/1527第27页，共30页，2023年，2月20日，星期一第五讲线性规划灵敏度分析

10-1/4-200cj-zj

101/2101001/41/2-1/800-21/200014100244212x1x5x2x63040

x6x5x4x3x2x1B－1bXBCB

600043cj→

00-1/4-200cj-zj

000101001/41/2-1/800-21/2-200101000442-4x1x5x2x63040

x6x5x