第五讲 线性规划灵敏度分析演示教案(Max型)

1、第五节第五节线性规划的灵敏度分析线性规划的灵敏度分析线性规划的灵敏度分析线性规划的灵敏度分析在线性规划问题中在线性规划问题中, ,都假定都假定A,b,CA,b,C中的元素中的元素a aijij,b,bi i,c,cj j是已知常数是已知常数. .但实际上这些数往往是一些估计或预测的数字但实际上这些数往往是一些估计或预测的数字, ,如市场条件一如市场条件一变变, ,c cj j值就会变化值就会变化. . a aijij是随工艺技术条件的改变而改变是随工艺技术条件的改变而改变, ,而而b bi i值值是根据资源投入后能产生多大经济效益来决定的一种决策选择是根据资源投入后能产生多大经济效益来决定的一

2、种决策选择因此因此,当这些参数中的一个或几个发生变化时，线性规划问题的当这些参数中的一个或几个发生变化时，线性规划问题的最优解会有什么变化，或者这些参数一个或多个在什么范围内最优解会有什么变化，或者这些参数一个或多个在什么范围内变化时变化时,问题的最优解是不变的。问题的最优解是不变的。这就是这就是灵敏度分析灵敏度分析当然当然,当线性规划问题中的一个或几个参数发生变化时当线性规划问题中的一个或几个参数发生变化时, 可用单纯可用单纯形形 法从头计算法从头计算,看一看最优解有无变化看一看最优解有无变化,但这样但这样做既麻烦又没必要做既麻烦又没必要. 因为单纯形法的迭代是从一个基到另一个基去寻找最优解

3、的因为单纯形法的迭代是从一个基到另一个基去寻找最优解的,因因此此当一个或几个参数发生变化时当一个或几个参数发生变化时,我们从最优单纯形表去分析我们从最优单纯形表去分析,去去寻找即可寻找即可.一一.非基变量系数非基变量系数cj的灵敏度分析的灵敏度分析设线性规划的标准形式设线性规划的标准形式:设设B是是(LP)的最优基，对应的单纯形表为的最优基，对应的单纯形表为(). .0maxzCXLPAXbs tXABCCbBCABbBBB1111当当xj的价值系数的价值系数cj有改变量有改变量cj即即cj变成变成c*=cj+cj1(). .0max zCXLPAXbs tX112,BnCC B A 1jjB

4、jcC B P一一.非基变量系数非基变量系数cj的灵敏度分析的灵敏度分析设非基变量设非基变量xj的价值系数的价值系数cj有改变量有改变量cj此时此时xj 的检验数的检验数其它检验数没改变其它检验数没改变由由cj-CBB-1Pj(cj+cj) -CBB-1Pj = j +cj(1)当当cj +j 0时时,则基则基B仍是仍是(LP)的最优基的最优基, 最优值最优值 和最优解都不变和最优解都不变此时原单纯形表中的检验数此时原单纯形表中的检验数j用用cj+j代替利用单纯形代替利用单纯形法迭代法迭代,得得新问题的最优解新问题的最优解(2)当当cj+j 0时时,则基则基B仍是仍是(LP)的可行基的可行基,

5、 但不是最优基但不是最优基ABCCbBCABbBBB1111某厂利用三种资源某厂利用三种资源B1、B2、B3生产三种产品生产三种产品A1、A2、A3;其中其中B1为为劳动力劳动力(单位单位:人人),B2为流动资金为流动资金(单位单位:元元),B3为主要设备为主要设备(单位单位:台时台时)。在一个生产周期内在一个生产周期内,各资源的供应数量各资源的供应数量,单位产品对各资源的消耗数单位产品对各资源的消耗数及单位产品的利润如下表所示及单位产品的利润如下表所示:如何组织该周期内各种产品的生产如何组织该周期内各种产品的生产,使总利润最大使总利润最大?产品产品资源资源A1A2A3资源资源供给供给B1B2

6、B3112211131458090单位产品利润单位产品利润543已知该问题的线性规划模型为如下已知该问题的线性规划模型为如下:(其中其中x1,x2,x3分别为分别为产品产品A1,A2,A3的产量的产量,x4,x5,x6为引入的松驰变量为引入的松驰变量)非基变量系数非基变量系数cj的灵敏度分析的灵敏度分析(例例1)例例120,903802452.345max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxz的最优单纯形表为如下的最优单纯形表为如下:xBbx1x2x3x4x5x6x2x1x61035250132-1010-1-11000-7-521-z -2

7、15 00-4-3-10(1)若产品若产品A3的单位利润的单位利润c3发生变化时发生变化时, c3在什么在什么范围内变化时范围内变化时,原来最优原来最优解保持不变解保持不变?(2)若产品若产品A3的单位利润的单位利润c3变为变为10时的最优解时的最优解?解：解：(1)因因c3为非基变量为非基变量x3的系数的系数例例13其检验数其检验数3=-4，设设c3的改变量为的改变量为c3要使原最优解不变要使原最优解不变,则必须则必须3 +c3 0即即4+c3 0c3 4c3 3+4=7因此当因此当c3 7 (价格小于等于价格小于等于7时时,原最优解不变原最优解不变)(2)当当c3变为变为10时时,则则c3

8、=7, 3 +c33,需要进行基变换，再做进一步的判断将其反映到原将其反映到原问题终表中得下表问题终表中得下表2.基变量的价值系数基变量的价值系数cj的灵敏度分析的灵敏度分析此时此时cj 的在的在CB中中,故故cj的变化引的变化引起起所有检验数都有可能变化所有检验数都有可能变化设基变量设基变量xj 的系数的系数cj的改变量为的改变量为cj则检验数由则检验数由C-CBB-1A(1)当当 有大于有大于0时时ABCCB101ABCCB则基则基B仍是仍是(LP)的最优基的最优基,但最优但最优值变成值变成而最优解不变而最优解不变bBCB1(2)当当 我们可从不等式组我们可从不等式组得到得到cj的变化范围

9、的变化范围此时可此时可利用单纯形法迭代利用单纯形法迭代,得新问题的最优解得新问题的最优解ABCCbBCABbBBB1111ABCCB101ABCCB2.基变量的价值系数基变量的价值系数cj的灵敏度分析的灵敏度分析在解具体问题时在解具体问题时,解不等式组解不等式组不等式组可通过如下方式得到不等式组可通过如下方式得到:先在原最优单纯形表中将先在原最优单纯形表中将xj的检验数替换为的检验数替换为cj然后然后,将将cj化为化为0,可得到不等式组可得到不等式组,再求解再求解.01ABCCB某厂利用三种资源某厂利用三种资源B1、B2、B3生产三种产品生产三种产品A1、A2、A3;其中其中B1为为劳动力劳动

10、力(单位单位:人人),B2为流动资金为流动资金(单位单位:元元),B3为主要设备为主要设备(单位单位:台时台时)。在一个生产周期内在一个生产周期内,各资源的各资源的 供应数量供应数量,单位产品对各资源的消耗单位产品对各资源的消耗数及单位产品的利润如下表所示数及单位产品的利润如下表所示:如何组织该周期内各种产品的生产如何组织该周期内各种产品的生产,使总利润最大使总利润最大?产品产品资源资源A1A2A3资源资源供给供给B1B2B3112211131458090单位产品利润单位产品利润543已知该问题的线性规划模型为如下已知该问题的线性规划模型为如下:(其中其中x1,x2,x3分别为分别为产品产品A

11、1,A2,A3的产量的产量,x4,x5,x6为引入的松驰变量为引入的松驰变量)基变量系数基变量系数cj的灵敏度分析的灵敏度分析(例例2)例例220,903802452.345max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxz的最优单纯形表为如下的最优单纯形表为如下:(3)若产品若产品A1的单位利润的单位利润c1发生发生变化时变化时, c1在什么范围内变化时在什么范围内变化时,原来最优解保持不变原来最优解保持不变?(4)产品产品A1的单位利润的单位利润c1=10时时的最优解的最优解?xBbx1x2x3x4x5x6x2x1x61035250132-10

12、10-1-11000-7-521-z -215 00-4-3 -10例例23xB b x1 x2 x3 x4 x5 x6x2x1x610 35 25 0 1 3 2 -1 0 1 0 -1 -1 1 0 0 0 -7 -5 2 1 -z -215 C1 0 -4 -3 -1 0解：解： (3)因因c1为基变量为基变量x1的系数的系数设其改变量为设其改变量为c1xB b x1 x2 x3 x4 x5 x6x2x1x6 10 35 25 0 1 3 2 -1 0 1 0 -1 -1 1 0 0 0 -7 -5 2 1-z -215-35C1 0 0 -4+C1 3+C1 1-C1 0借助初等行借助

13、初等行变换将变换将c1化化为零，得下为零，得下表：表：例例24111403010ccc 故故 4c18c1=5，则基则基B仍是仍是(LP)的最优基的最优基,但最优值变成但最优值变成bBCB1(4)因因c1=10， -1c13111431ccc 要使原最优解不变要使原最优解不变,则必须则必须将其反映到原问题的终表中得下将其反映到原问题的终表中得下表：表：例例25新问题的最优解为：新问题的最优解为：X X* *=(40,0=(40,0，0 0，5,0,50)5,0,50)T T新问题最优新问题最优值值z z* *=400 =400 二二.约束条件右端常数项约束条件右端常数项bi的灵敏度分析的灵敏度

14、分析设设B是是(LP)的最优基的最优基().0max zCXLPAXbstXABCCbBCABbBBB11112().0max zCXLPAXbstX设设bi变为变为b*i =bi +bi 则变化后的线性规划为则变化后的线性规划为*111( ,., ,)Tiiimbbbb bb因为常数项因为常数项b的变动的变动,不影响单纯形表中的检验数不影响单纯形表中的检验数故原问题故原问题(Lp)的最优基是改的最优基是改变后问题的对偶可行基变后问题的对偶可行基 二二.约束条件右端常数项约束条件右端常数项bi的灵敏度分析的灵敏度分析(2)故原问题的最优基是改变后问题的对偶可行基故原问题的最优基是改变后问题的对

15、偶可行基基基B是否为是否为(LP2)的最优基的最优基, 取决于取决于 是否成立是否成立? 01bBmiibbbbBbB.111110.0iBbBb(1)若若 01bB则原问题的最优基则原问题的最优基B是新问题的最优基是新问题的最优基二二.约束条件右端常数项约束条件右端常数项bi的灵敏度分析的灵敏度分析(3)即即 00.011ibBbB求出求出bi允许变化的范围允许变化的范围(2) 若若 中出现负分量时中出现负分量时, B不再是最优基不再是最优基,可用对偶单纯形法继续求最优解可用对偶单纯形法继续求最优解注注: 当当B仍是最优基时仍是最优基时,但最优解却不同但最优解却不同1B b某厂利用三种资源某

16、厂利用三种资源B1、B2、B3生产三种产品生产三种产品A1、A2、A3;其中其中B1为为劳动力劳动力(单位单位:人人),B2为流动资金为流动资金(单位单位:元元),B3为主要设备为主要设备(单位单位:台时台时)。在一个生产周期内在一个生产周期内,各资源的各资源的 供应数量供应数量,单位产品对各资源的消耗单位产品对各资源的消耗数及单位产品的利润如下表所示数及单位产品的利润如下表所示:如何组织该周期内各种产品的生产如何组织该周期内各种产品的生产,使总利润最大使总利润最大?产品产品资源资源A1A2A3资源资源供给供给B1B2B3112211131458090单位产品利润单位产品利润543已知该问题的

17、线性规划模型为如下已知该问题的线性规划模型为如下:(其中其中x1,x2,x3分别为分别为产品产品A1,A2,A3的产量的产量,x4,x5,x6为引入的松驰变量为引入的松驰变量)约束条件右端常数项约束条件右端常数项bi的灵敏度分析的灵敏度分析(例例3)例子例子(2)的最优单纯形表为如下的最优单纯形表为如下:(5) 问问b2在什么范围内变化时，最优基不变？在什么范围内变化时，最优基不变？ 0,903802452. .345max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxz(6)若资金限量改为若资金限量改为100元元,求最优生产方案。求最优生产方案。例子

18、例子(2-1)解：（解：（5）设）设b2有增量有增量b2，由最优单纯形表知由最优单纯形表知xB bx1 x2 x3 x4 x5 x6x2x1x6 10 35 25 0 1 3 2 -1 0 1 0 -1 -1 1 0 0 0 -7 -5 2 1-z-215 0 0 -4 -3 -1 0121 01 1 0 ,5 2 1B 200bb bBbBbB1112221035252bbb 2221035252bbb 若想保持最优基不变，则要求：若想保持最优基不变，则要求：222210253510225/ 2bbbb 故：2135902b例子例子(2-2)解：（解：（6）b2=80, b2=20,由最优单

19、纯形表知由最优单纯形表知1250110121B0200bbBbBbB111402020253510655510则原最优基则原最优基B是新问题的对偶可行基，新单纯形表如下是新问题的对偶可行基，新单纯形表如下例子例子(2-3)则原最优基则原最优基B是新问题的对偶可行基，新单纯形表如下是新问题的对偶可行基，新单纯形表如下换基迭代得下列单纯形表：换基迭代得下列单纯形表：则得到新的最优解则得到新的最优解(45,0,0,0,10,45)T和新的最优值和新的最优值225三三.增加一个新决策变量时的灵敏度分析增加一个新决策变量时的灵敏度分析若在若在(LP)中中增加一个决策变量增加一个决策变量xn+1其系数列向

20、量为其系数列向量为Pn+1xn+1的价值系数为的价值系数为cn+1113111max(). .0,0nnnnnzCXcxLPAXPxbstXx().0max zCXLPAXbstX则则(LP)变成变成设设B是是(LP)的最优基的最优基则则B也是也是(LP3)的一个基的一个基,并且与其对应并且与其对应 的单纯形表如下的单纯形表如下ABCCbBCABbBBB1111三三.增加一个新决策变量时的灵敏度分析增加一个新决策变量时的灵敏度分析(2)显然显然,B是是(LP3)的可行基的可行基(1)若若cn+1 CBB-1Pn+1 0则则B是是(LP3)的最优基的最优基(2)若若cn+1 CBB-1Pn+1

21、0则则B是是(LP3)的可行基的可行基, 而非最优基而非最优基此时又有两种情形此时又有两种情形(I)若若B-1Pn+10则则(LP3)无最优解无最优解 (ii)若若B-1Pn+1中至少有一个正数中至少有一个正数则则利用单纯形法继续迭代求出最优解利用单纯形法继续迭代求出最优解某厂利用三种资源某厂利用三种资源B1、B2、B3生产三种产品生产三种产品A1、A2、A3;其中其中B1为为劳动力劳动力(单位单位:人人),B2为流动资金为流动资金(单位单位:元元),B3为主要设备为主要设备(单位单位:台时台时)。在一个生产周期内在一个生产周期内,各资源的各资源的 供应数量供应数量,单位产品对各资源的消耗单位

22、产品对各资源的消耗数及单位产品的利润如下表所示数及单位产品的利润如下表所示:如何组织该周期内各种产品的生产如何组织该周期内各种产品的生产,使总利润最大使总利润最大?产品产品资源资源A1A2A3资源资源供给供给B1B2B3112211131458090单位产品利润单位产品利润543已知该问题的线性规划模型为如下已知该问题的线性规划模型为如下:(其中其中x1,x2,x3分别为分别为产品产品A1,A2,A3的产量的产量,x4,x5,x6为引入的松驰变量为引入的松驰变量)三三.增加一个新决策变量时的灵敏度分析增加一个新决策变量时的灵敏度分析(例例4)(7)设工厂计划生产新产品设工厂计划生产新产品A4,

23、生产一个生产一个A4单位所消耗单位所消耗 的人力、资金、设备时数分别为的人力、资金、设备时数分别为1，2，3。问在怎样。问在怎样的单位利润条件下，投产产品的单位利润条件下，投产产品A4,才有利？才有利？例例31的最优单纯形表为如下的最优单纯形表为如下:0,903802452. .345max654321632153214321321xxxxxxxxxxxxxxxxxxtsxxxzxB bx1 x2 x3 x4 x5 x6x2x1x6 10 35 25 0 1 3 2 -1 0 1 0 -1 -1 1 0 0 0 -7 -5 2 1-z -215 0 0 -4 -3 -1 0解：解： (7)设产

24、品设产品A4的的产量为产量为x7其单位利润为其单位利润为c7例例32c7CBB-1P7= c753217P1250110121BCB=(4,5,0) 则在原最优单纯形表中加上则在原最优单纯形表中加上x7这一列这一列x7B-1P7c7CBB-1P7x7012c75因此，当因此，当A4的单位产品的利润大于的单位产品的利润大于5时，投产产品时，投产产品A4才有利才有利四四.添加一个新约束条件时的灵敏度分析添加一个新约束条件时的灵敏度分析在在(LP)中中添加一个新约束条件添加一个新约束条件Am+1Xbm+1其中其中Am+1=(am+1,1 am+1,2 am+1,n) 411ax(). .0mmmzC

25、XAXbLPs tAXbX(). .0max zCXLPAXbstX则则(LP)变成了变成了设设B是是(LP)的一个最优基的一个最优基,但它不是（但它不是（LP4)的一个基的一个基四四.添加一个新约束条件时的灵敏度分析添加一个新约束条件时的灵敏度分析(2)(1)若原问题若原问题(LP)的最优解：的最优解：X=(x1*, x2*, ,xn* )(2)若若X* 不满足新约束条件，不满足新约束条件，满足新的约束条件：满足新的约束条件：Am+1X=am+1,1x1*+ am+1,2x2*+ +am+1,nxn* bm+1 则则X*是新问题是新问题(LP4)的最优解的最优解 则则X*不是新问题不是新问题

26、(LP4)的可行解的可行解 则可按如下进行分析则可按如下进行分析引进松驰未知量引进松驰未知量Xn+1化新约束条件为等式，即化新约束条件为等式，即 am+1,1x1+ am+1,2x2+ +am+1,nxnxn+1=bm+1 设设B是（是（LP)的一个最优基的一个最优基 101mABB记记 四四.添加一个新约束条件时的灵敏度分析（添加一个新约束条件时的灵敏度分析（3）0| BB显然显然 故故 是是(LP4) 的一个基的一个基B新问题新问题(LP4)对应基对应基 的单纯形表的单纯形表 可由可由(LP)对应的基对应的基B的单纯形表的单纯形表T(B)来推得来推得 B)(BT上表不是上表不是(LP4)对

27、应基对应基 的单纯形表的单纯形表 因为因为基变量对应的列不是单位向量基变量对应的列不是单位向量 B)(BT但可通过初等变换得到对应基但可通过初等变换得到对应基 的单纯形表的单纯形表B)(BT四四.添加一个新约束条件时的灵敏度分析（添加一个新约束条件时的灵敏度分析（4）而形成而形成 过程中过程中.检验数仍然不变（即小于或等于检验数仍然不变（即小于或等于0）)(BT因此因此,基基 是新问题的对偶可行基是新问题的对偶可行基; B某厂利用三种资源某厂利用三种资源B1、B2、B3生产三种产品生产三种产品A1、A2、A3;其中其中B1为为劳动力劳动力(单位单位:人人),B2为流动资金为流动资金(单位单位:

28、元元),B3为主要设备为主要设备(单位单位:台时台时)。在一个生产周期内在一个生产周期内,各资源的各资源的 供应数量供应数量,单位产品对各资源的消耗单位产品对各资源的消耗数及单位产品的利润如下表所示数及单位产品的利润如下表所示:如何组织该周期内各种产品的生产如何组织该周期内各种产品的生产,使总利润最大使总利润最大?产品产品资源资源A1A2A3资源资源供给供给B1B2B3112211131458090单位产品利润单位产品利润543已知该问题的线性规划模型为如下已知该问题的线性规划模型为如下:(其中其中x1,x2,x3分别为分别为产品产品A1,A2,A3的产量的产量,x4,x5,x6为引入的松驰变量为引入的松驰变量)例例41例例42的最优单纯形表为如下的最优单纯形表为如下:(8)设增加一个用电