第五讲 线性规划的灵敏度分析线性规划的灵敏度分析在线性规划问题中,都假定A,b,C中的元素aij,bi,cj是已知常数. 但实际上这些数往往是一些估计或预测的数字,如市场条件一 变,cj值就会变化. aij是随工艺技术条件的改变而改变,而bi值 是根据资源投入后能产生多大经济效益来决定的一种决策选择因此,当这些参数中的一个或几个发生变化时，线性规划问题的最优解会有什么变化，或者这些参数一个或多个在什么范围内 变化时,问题的最优解是不变的。这就是灵敏度分析当然,当线性规划问题中的一个或几个参数发生变化时, 可用单纯 形 法从头计算,看一看最优解有无变化,但这样做既麻烦又没必要 . 因为单纯形法的迭代是从一个基到另一个基去寻找最优解的,因 此当一个或几个参数发生变化时,我们从最优单纯形表去分析,去 寻找即可.一.非基变量系数Cj的灵敏度分析设线性规划的标准形式:设B是(LP)的最优基，对应的单纯形表为C-CBB-1A=(b01,b02,.,b0n)b0j=Cj-CBB-1Pj 当xj的价值系数Cj有改变量 Cj即Cj变成C*=Cj+ Cj一.非基变量系数Cj的灵敏度分析设xj的价值系数Cj有改变量 Cj此时Xj 的检验数其它检验数没改变由Cj-CBB-1Pj(Cj+Cj) -CBB-1Pj =b0j+Cj(1)当Cj +b0j 0时,则基B仍是(LP)的最优基,最优值 和最优解都不变此时原单纯形表中的检验数b0j 用Cj+b0j代替利用单 纯形法迭代,得新问题的最优解(2)当Cj+b0j0时,则基B仍是(LP)的可行基,但不是最优基某厂利用三种资源B1、B2、B3生产三种产品A1、A2、A3;其中 B1为劳动力(单位:人),B2为流动资金(单位:元),B3为主要设备(单位 :台时)。在一个生产周期内,各资源的 供应数量,单位产品对各资源 的消耗数及单位产品的销售价格如下表所示:如何组织该周期内各种产品的生产,使总产值最大?已知该问题的线性规划模型为如下:(其中X1,X2,X3分别为 产品A1,A2,A3的产量,X4,X5,X6为引入的松驰变量)非基变量系数Cj的灵敏度分析(例1)例12的最优单纯形表为如下:(1)若产品A3的销售价格 C3发生变化时, C3在什么 范围内变化时,原来最优 解保持不变?(2)若产品A3的销售价格 C3变为10时的最优解?解：(1)因C3变为非基变量x3的系数例13 其检验数b03=-4，设C3的改变量为C3要使原最优解不变,则必须b03+C3 0即4+C3 0C3 4C3 3+4=7因此当C3 7 (价格小于等于7时,原最优解不变(2)当C3变为10时则C3=7b03+C332.基变量的价值系数Cj的灵敏度分析此时Cj 的在CB中,故Cj的变化引起所有检验数都有可能变化设Xj 的系数Cj的改变量为Cj则检验数由C-CBB-1A(1)当 有大于0时则基B仍是(LP)的最优基,但最优 值变成而最优解不变(2)当 我们可从不等式组得到Cj的变化范围此时可利用单纯形法迭代,得新问题的最优解2.基变量的价值 系数Cj的灵敏度分析在解具体问题时,解不等式组不等式组可通过如下方式得到:先在原最优单纯形表中将xj的检验数替换为Cj然后,将Cj化为0,可得到不等式组,再求解.某厂利用三种资源B1、B2、B3生产三种产品A1、A2、A3;其中 B1为劳动力(单位:人),B2为流动资金(单位:元),B3为主要设备(单 位:台时)。在一个生产周期内,各资源的 供应数量,单位产品对各 资源的消耗数及单位产品的销售价格如下表所示:如何组织该周期内各种产品的生产,使总产值最大?价值 系数Cj的灵敏度分析(例2)已知该问题的线性规划模型为如下:(其中X1,X2,X3分别 为产品A1,A2,A3的产量,X4,X5,X6为引松入的驰变量)例22的最优单纯形表为如下:(1)若产品A1的销售价格C1发生 变化时, C1在什么范围内变化时 ,原来最优解保持不变?(2)产品A1的销售价格C1=10时 的最优解?解： (1)因C1为基变量x1的系数例23解： (1)因C1为基变量x1的系数设其改变量为C1例24-4+C10 - 3+C10 -1- C10故 4C18C14C1 3C1 -1C1=5则基B仍是(LP)的最优基,但最优值变成(2)因C1=10-1C13例25最优解 x1=40, x2=0, x3=0, x4=5, x6=50则最优值z=400 二.约束条件右端常数项bi的灵敏度分析设B是(LP)的最优基设bi变为b*i =bi +bi 则变化后的线性规划为因为常数项b的变动,不影响单纯形表中的检验数故原问题(Lp)的最优基是改 变后问题的对偶可行基 二.约束条件右端常数项bi的灵敏度分析(2)故原问题的最优基是改变后问题的对偶可行基基B是否为(LP2)的最优基, 取决于 是否成立? 只要 则原问题的最优基B是新问题的最优基二.约束条件右端常数项bI的灵敏度分析(3)我们可通过解不等式组即 求出bi允许变化的范围当超出允许值之外,B不再是最优基,可用对偶单纯形法继续求最优解注: 当B仍是最优基时,但最优解却不同右端常数项bI的灵敏度分析(例子)某厂利用三种资源B1、B2、B3生产三种产品A1、A2、A3;其 中B1为劳动力(单位:人),B2为流动资金(单位:元),B3为主要设备 (单位:台时)。在一个生产周期内,各资源的 供应数量,单位产品 对各资源的消耗数及单位产品的销售价格如下表所示:如何组织该周期内各种产品的生产,使总产值最大?已知该问题的线性规划模型为如下:(其中X1,X2,X3分别为产品 A1,A2,A3的产量,X4,X5,X6为引松入的驰变量)例子(2)的最优单纯形表为如下:(1)根据上述表格试对资金b2进行灵敏度分析;若资金限量改为100元,求最优生产方案。(2)若劳务市场每个劳动力在一个生产周期内的工资为2元,问从劳务市场 雇用工人参加生产是否值得?若值得,最多可增加多少工人?此时总产 值增加多少?例子(2-1)解：（1）b2=80, b2=20,由最优单纯形表知则原最优基B是新问题的对偶可行基，新单纯形表如下例子(2-2)则原最优基B是新问题的对偶可行基，新单纯形表如下换基迭代得下列单纯形表：则得到新的最优解（45,0,0,0,10,45)和最优值225三.增加一个新决策变量时的灵敏度分析若在(LP)中增加一个决策变量xn+1其系数列向量为pn+1xn+1的价值系数为cn+1则(LP)变成设B是(LP)的最优基则B也是(LP3)的一个基,并且与其对应 的单纯形表如下三.增加一个新决策变量时的灵敏度分析(2)显然,B是(LP3)的可行基(1)若Cn+1 CBB-1Pn+1 0则B是(LP3)的最优基(2)若Cn+1 CBB-1Pn+1 0则B是(LP3)的可行基,而非最优基此时又有两种情形 (I)若B-1Pn+10则(LP3)无最优解 (ii)若B-1Pn+1中至少有一个正数则利用单纯形法继续迭代求出最优解三.增加一个新决策变量时的灵敏度分析(例子)某厂利用三种资源B1、B2、B3生产三种产品A1、A2、A3;其 中B1为劳动力(单位:人),B2为流动资金(单位:元),B3为主要设备 (单位:台时)。在一个生产周期内,各资源的 供应数量,单位产品 对各资源的消耗数及单位产品的销售价格如下表所示:如何组织该周期内各种产品的生产,使总产值最大?已知该问题的线性规划模型为如下:(其中X1,X2,X3分别为产品 A1,A2,A3的产量,X4,X5,X6为引松入的驰变量)(1)设工厂计划生产新产品A4,生产一个A4单位所消耗 的人力、资金、设备时数分别为1，2，3。问在怎样的销售价格下，投产产品A4,才有利？如投产产品A4, 怎样安排新的最优生产 计划？例31的最优单纯形表为如下:解：设产品A4的产量为x7其销售价格为C7例32C7CBB-1P7= C75CB=(4,5,0) 则在原最优单纯形表中加上X7这一列X7B-1P7C7CBB-1P7X7 0 1 2 C75因此，当A4产品的价格大于5时，投产产品A4才有利例33 X7 0 1 2 C7-5X7 0 0 1 0四.添加一个新约束条件时的灵敏度分析在(LP)中添加一个新约束条件Am+1Xbm+1其中Am+1=(am+1,1 am+1,2 am+1,n) 则(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*不是新问题(LP4)的可行解 则可按如下进行分析引进松驰未知量Xn+1化新约束条件为等式，即 am+1,1x1+ am+1,2x2+ +am+1,nxnxn+1=bm+1 设B是（LP)的一个最优基 记 四.添加一个新约束条件时的灵敏度分析（3）显然 故 是(LP4) 的一个基新问题(LP4)对应基 的单纯形表 可由 (LP)对应的基B的单纯形表T(B)来推得 上表不是(LP4)对应基 的单纯形表 因为 基变量对应的列不是单位向量 但可通过初等变换得到对应基 的单纯形表四.添加一个新约束条件时的灵敏度分析（4）而形成 过程中.检验数仍然不变（即小于或等于0）因此,基 是问题的对偶可行基, 例41某厂利用三种资源B1、B2、B3生产三种产品A1、A2、A3;其 中B1为劳动力(单位:人),B2为流动资金(单位:元),B3为主要设备 (单位:台时)。在一个生产周期内,各资源的 供应数量,单位产品 对各资源的消耗数及单位产品的销售价格如下表所示:如何组织该周期内各种产品的生产,使总产值最大?已知该问题的线性规划模型为如下:(其中X1,X2,X3分别为产品 A1,A2,A3的产量,X4,X5,X6为引松入的驰变量)例42的最优单纯形表为如下:设增加一个用电限制条件,生产产品,A1 ,A2,A3 的一个单位的耗 电量分别为1，2，2(度)。而一个生产周期内总耗电量不超过43 度,问此时应如何安排生产,使总产值最大？例43解:新增的约束条件为x1+ 2x2+2x3 43 原问题(LP)的最优解：X=(35,10, 0,0,0,25 )代入新增的约束条件中 x1+ 2x2+ 2x3+ x7=43 则X*不是新问题(LP4)的可行解 x1+ 2x2+2x3=55 43 从而引入松驰未知量X7,化新约束条件为等式 原最优单纯形表上添加一行和一列得 例45x1+ 2x2+ 2x3+ x7=43 例46例47最优解 x1=39, x2=2, x3=0,则最优值 z=203