线性规划灵敏度分析.ppt

《线性规划灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《线性规划灵敏度分析.ppt（71页珍藏版）》请在三一办公上搜索。

1、Chapter 2线性规划灵敏度分析,上海工程技术大学管理学院,Chapter 2 灵敏度分析,本章提要 Content单纯形法的矩阵描述改进单纯形法对偶问题提出线性规划对偶理论对偶问题的基本性质影子价格对偶单纯形法灵敏度分析案例分析及Matlab求解 习题,Chapter 2 灵敏度分析,单纯形法的矩阵描述？,单纯形法矩阵的描述,已知：A、b、c A=(NB)B=E,Chapter 2 灵敏度分析,用非基变量表示基变量,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,改进单纯形法,(1)、已有初始可行基B，求B-1，XB=B-1 b,Chapter 2 灵敏度分析,Chapt

2、er 2 灵敏度分析,对偶问题提出问题一：某公司在计划期内要安排生产I II两种产品已知生产单位产品所需的设备台时及A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？如何安排方案？,举例,有哪些 方面可以考虑呢？,Chapter 2 灵敏度分析,先根据图表来列出模型 Max Z=2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1,X2 0 我们从另一个角度来讨论这个问题.假如该工厂的决策者决定不生产产品I II，而将其所有资源出租或外售.这时工厂的决策者就要考虑给每种资源如何定价的问题.设用,分别

3、表示出租单位设备台时的租金和出让单位原材料A,B的附加额.他在做定价决策时,作如下比较:若用一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有 Y1+4Y2 2,举例,Chapter 2 灵敏度分析,同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有 2Y1+4Y3 3 把工厂所有设备台时和资源都出租和出让,其收入为 f=8Y1+16Y2+12Y3 从工厂决策者的角度来看W当然是越大越好,但从接受者眼光来说W是越少越好,所以工厂决策者只可

4、以在满足所有产品的利润条件下,使其总收入尽可能的小.因此可以列出如下线性规划问题 f=8Y1+16Y2+12Y3 Y1+4Y2 2 2Y1+4Y3 3 Yi 0,i=1,2,3,Chapter 2 灵敏度分析,各模型中有关数据的“位置”示意图如下。,Chapter 2 灵敏度分析,问题二:考虑：资源拥有者为了实现一定的收入目标，将其 所拥有的资源出售，给每一种资源如何定价？,Chapter 2 灵敏度分析,Yi表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：如果资源拥有者将所有资源出售，则他得到的总收 入,Chapter

5、2 灵敏度分析,资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。,线性规划的对偶理论对偶定义 对称形式：互为对偶(LP)Max z=cT x(DP)Min f=bT y s.t.Ax b s.t.AT y c x 0 y 0“Max-”“Min-”,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型

6、为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。,Chapter 2 灵敏度分析,然而在一般线性规划问题中遇到非对称形式时我们的处理如下：非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的

7、等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,Chapter 2 灵敏度分析,非对称型对偶问题,Chapter 2 灵敏度分析,举例,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,综上所述其变换形式如下：,Chapter 2 灵敏度分析,小练习,写出下列问题的对偶问题,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,对偶问题的基本性质 性质1:对称性规范原始，对偶问题的对偶是原问题。M

8、ax z=CX Min f=Yb s.t.AX b s.t.YA C X 0 Y 0“Max-”“Min-”,Chapter 2 灵敏度分析,性质2:弱对偶原理（弱对偶性）：设 和 分别是 问题（P）和（D）的可行解，则必有,性质3:最优性判别定理 若 X*和 Y*分别是 P 和 D 的可行解且 CX*=Y*b，则X*.Y*分别是问题 P和D 的最优解。,Chapter 2 灵敏度分析,性质4:线性规划的对偶原理（1）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（强对偶性）（2）若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性）性质5:互补松弛定理设

9、X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是,Chapter 2 灵敏度分析,同时成立,一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。,Chapter 2 灵敏度分析,例题判断下例说法是否正确，为社么？A 如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C 在互为对偶的一对原问题和对偶问

10、题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。,Chapter 2 灵敏度分析,解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。,Chapter 2 灵敏度分析,例题:已知原问题的最优解为X*=（），Z=12 试求对偶问题的最优解。,Chapter 2 灵敏度分析,解:,将X*=（0.0.4）代入原问题中，有下式：,Chapter 2 灵敏度分析,所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=

11、3。因此，对偶问题的最优解为 Y*=（0.0.3），W=12。,Chapter 2 灵敏度分析,影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cT x*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产生的影响，称 yi*为 bi的影子价格。注意：若 B 是最优基，y*=(BT)-1 cB 为影子价格向量。,Chapter 2 灵敏度分析,影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价

12、格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,Chapter 2 灵敏度分析,（2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是,Cha

13、pter 2 灵敏度分析,影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。,Chapter 2 灵敏度分析,需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。,Chapter 2 灵敏度分析,对偶单纯形法,对偶单纯形法的基本思想

14、 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,Chapter 2 灵敏度分析,对偶单纯形法在什么情况下使用：应用前提：有一个基，其

15、对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,Chapter 2 灵敏度分析,对偶单纯形法求解线性规划问题过程：1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有akj0 则选=minj/akjakj0=r/akr那么 xr为进基变量,转4；4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,Ch

16、apter 2 灵敏度分析,例题:用对偶单纯形法求解,Chapter 2 灵敏度分析,解:将上述模型转化为,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,Chapter 2 灵敏度分析,所以，X*=（2.2.2.0.0.0）Z*=72，原问题 Z*=72 其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72,Chapter 2 灵敏度分析,从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：1)初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。2

17、)当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。3)在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。对偶单纯形法的局限在于：对于大多数的线性规划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。,Chapter 2 灵敏度分析,对偶单纯形法与单纯形法的区别,补充,Chapter 2 灵敏度分析,灵敏度分析灵敏度分析的步骤可以归纳如下：1)将参数的改变计算反映到最终单纯形表上来;具体的计算方法是，按照相关公式计算出

18、由参数，的变化而引起的最终单纯形表上有关数字的变化；2)检查原问题是否仍为可行解;3)检查对偶问题是否仍为可行解;4)我们可以按照书中表2.10中罗列的几种情况得出结论和决定继续计算的步骤,Chapter 2 灵敏度分析,1)资源数量发生变化的分析 设分量 br 变化为 br+br，根据讨论，最优解的基变量 xB=B-1b，那么只要保持 B-1(b+b)0，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。对于问题(LP)Max z=cT x s.t.Ax b x 0,Chapter 2 灵敏度分析,最优单纯形表中含有B-1=(aij）i=1,m;j=n+1,n+m

19、 那么新的xi=(B-1b)i+brair i=1,m。由此可得，最优基不变的条件是 Max-bi/airair0brMin-bi/airair0,Chapter 2 灵敏度分析,例题:Max z=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,x3,x4,x5 0,Chapter 2 灵敏度分析,最终单纯形表为:,Chapter 2 灵敏度分析,0 0.25 0 这里 B-1=-2 0.5 1 0.5-0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1,x5,x2分别变

20、为：4+04=4,4+(-2)4=-40,2+0.54=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=17,Chapter 2 灵敏度分析,2)价值系数cj的变化分析 m 考虑检验数 j=cj-cri arij j=1,2,n i=1 若ck是非基变量的系数：设ck变化为 ck+ck k=ck+ck-cri arik=k+ck 只要 k 0,即 ck-k，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。,Chapter 2 灵敏度分析,例题:Max z=-2x1-3x2-4x3 S.t.-x1-2x2-x3+x4=-3-2x

21、1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0,Chapter 2 灵敏度分析,最优单纯形表:,从表中看到3=c3+c3-(c2a13+c1a23)可得到c3 9/5 时，原最优解不变。,Chapter 2 灵敏度分析,若 cs 是基变量的系数：设 cs 变化为 cs+cs，那么 j=cj-cri arij-(cs+cs)asj=j-cs asj，i s 对所有非基变量，只要对所有非基变量 j 0，即 j cs asj，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。Maxj/asjasj0csMinj/asjasj0,Chapter 2

22、 灵敏度分析,例题:Max z=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,x3,x4,x5 0,Chapter 2 灵敏度分析,从表中看到j=cj-(c1a1j+c5 a5j+(c2+c2)a2j)j=3,4可得到-3c21时，原最优解不变。,Chapter 2 灵敏度分析,增加一个变量 增加变量 xn+1 则有相应的pn+1,cn+1。那么 计算出B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表,若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解。,补充,Chapter

23、2 灵敏度分析,增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。,补充,Chapter 2 灵敏度分析,案例分析及Matlab求解 为了能够快速准确的运用对偶单纯形法来计算相关线性规划问题,我们使用MATLAB语言来实现,如书本上面所说的程序相对要复杂了点,所以我们使用MATLAB的优化工具箱里面的Linprog来实现我们的模型,命令：1 x=linprog（c，A，b

24、，Aeq,beq,VLB，VUB）2 x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1 若没有等式约束,则令Aeq=,beq=.2其中X0表示初始点,Chapter 2 灵敏度分析,爱思特公司经营一个营养中心，专门为VIP客户配置人体所需营养的元素摄入量，并且配置相应的服务套餐。现在公司为了能够进一步的拓展中国市场，公司从海外引入了四种营养品“甲”“乙”“丙”“丁”。这四种营养品可以提供人体所需要的营养元素。,案例,Chapter 2 灵敏度分析,根据书本上面的表格我们建立了如下的线性规划模型:f=8x1+6x2+3x3+6x4 x1+2x2+x4 30 3x1+

25、x2+x3+x4 60 x3+x4 20 x1+x3 20 x1,x2,x3,x4 0,Chapter 2 灵敏度分析,根据MATLAB优化工具箱编写：A=1,2,0,1;3,1,1,1;0,0,1,1;1,0,1,0;B=30,60,20,20;C=8,6,3,6;x=linprog(C,-A,-B,zeros(4,1),由于对偶单纯形法开始的变形,所以这里要输入-A,-B,这个表示输出的矩阵格式,Chapter 2 灵敏度分析,运行结果:,这个就是线性规划的最优解从上到下对应X1-4,Chapter 2 灵敏度分析,复习思考题：1、对偶问题和它的经济意义是什么？2、简述对偶单纯形法的计算步

26、骤。它与单纯形法的异同之处是什么？3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6、在线性规划的最优单纯形表中，松弛变量（或剩余变量），其经济意义是什么？7、在线性规划的最优单纯形表中，松弛变量的检验数，其经济意义是什么？8、关于单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？,Shanghai University of Engineering Science,Thank You!,