02-线性规划3__灵敏度分析

第五节灵敏度分析,大连海事大学交通运输管理学院,2.5.1单纯形法的矩阵描述2.5.2图解法灵敏度分析2.5.3单纯形法灵敏度分析,第五节灵敏度分析,灵敏度分析就是分析研究模型参数的取值变化对最优解或最优基的影响。模型参数在什么范围内变化将不致影响最优基？(参数规划)若最优解随参数的变化而变，则应如何用最简方法找到新最优解？,在单纯形法的迭代中，我们注意到，迭代过程中主要应用了矩阵的行变换，如在某一行上乘以一个不等于0的乘数k,或在某一行上乘以常数k加到另一行上。这种迭代过程相当于左乘一个相应的初等阵，而初等阵及其乘积为可逆矩阵。因此，约束方程系数矩阵的迭代实际上相当于左乘相应的可逆矩阵。,2.5.1单纯形法的矩阵描述,1.约束方程系数矩阵的变化约束方程系数矩阵，进行初等行变换，相当于左乘一个相应的初等阵。即，在A中所包含的矩阵B，左乘后，则得到。2.约束方程右端项的变化3.目标函数系数的变化由，得，两边左乘基变量的目标函数系数，得到与得到,2.5.1单纯形法的矩阵描述,例子,化为标准形，并用单纯形法求解如下：,Cj,x1,x2,x3,x4,XB,b,CB,11101201,2300,34,x3x4,00,cj-zj,2,3,0,0,3/1=3,4/2=2,1/201-1/21/2101/2,x3x2,12,cj-zj,1/200-3/2,03,24,102-101-11,x1x2,21,cj-zj,00-1-1,23,i,B-1,MaxZ=2X1+3X2,4,4,0,4,以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析。,2.5.2图解法灵敏度分析,例子,用图解法求得的最优解为Q（4，2）点。即生产甲产品4件，乙产品2件。,考虑目标函数系数变化对例题中最优产量解有什么影响。甲产品的利润为2元，乙产品的利润为3元，如果其中一种产品的利润增加，公司就会增加该产品的产量，如果其中一种产品的利润减少，公司就会减少该产品的产量。但问题是，利润变化多少时，管理者才应该决定改变产量呢？每个目标函数都有一个最优范围，目标函数系数在此范围内变化，模型最优解保持不变。下面用图解法求解这个最优范围。,1.目标函数系数的变化,只要目标函数直线的斜率处于直线x1+2x2=8与直线4x1=16的斜率之间，Q2点就仍然是最优解的点。目标函数直线的斜率z=c1x1+c2x2的斜率-c1/c2小于等于-0.5如果甲产品的单位利润不变，乙产品的单位利润改变，可得甲产品的利润范围c11.5.同理，乙产品的利润最优范围0C24。当两个系数C1、C2都改变时，我们仍然可以用目标函数斜率的变化范围来确定最优解是否改变。由于系数的改变，最优值z可能发生变化而不再是原值了。,2、约束条件右端值的变化,约束条件右端值每增加一个单位引起的最优值的改进量称为对偶价格。对偶价格只适用于在右端值仅发生了很小变动的情况,在其他系数不变的情况下，一些参数在一定范围内变化最优解不变。但是如果一些参数的变化较大，最优解就可能发生变化。这样就要问：这些参数在什么范围内变化时，问题的最优基（或最优解）不变，或者当这些参数中的一个或几个发生变化时，问题的最优解会有何变化。这就是灵敏度分析要研究解决的问题。,2.5.3单纯形法灵敏度分析,当某一个参数发生变化后，引起最优解如何改变的分析。可以改变的参数有：bi约束右端项的变化，通常称资源的改变；cj目标函数系数的变化，通常称市场条件的变化；pj约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。,1.灵敏度分析的概念：,（1）借助最终单纯形表将变化后的结果按下述基本原则反映到最终表里去。bi变化：（b+b）=B-1（b+b）=B-1b+B-1b=b+B-1bpj变化：（pj+pj）=B-1（pj+pj）=B-1pj+B-1pj=pj+B-1pjcj变化：直接反映到最终表中，计算检验数。增加一个约束方程：直接反映到最终表中。增加新产品：仿照pj变化。,2分析原理及步骤：,（2）检查改变后的最终表是否符合单纯形表的结构要求（基变量的值中无负数，基变量的系数向量构成单位矩阵，基变量的检验数全为0），或是否符合对偶单纯形表的结构要求（检验数中无正数，基变量的检验数全为0，基变量的系数向量构成单位矩阵）;（3）检查原问题是否仍为可行解;（4）检查对偶问题是否仍为可行解;,2分析原理及步骤：,（5）按照下表所列情况得出结论或继续计算的步骤。,2分析原理及步骤：,2.1资源数量变化的分析,资源数量变化是指资源中某系数br发生变化，即br=br+br。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为XB=B-1(b+b)这里b=(0,，br,0,，0)T。只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。新的最优解的值可允许变化范围用以下方法确定。,B-1是最终计算表中的最优基的逆,b列的元素变化,例对线性规划问题,分别分析1、2、3在什么范围内变化，问题的最优基不变.,先分析1的变化.,解：,方法一：,最终表:,使问题最优基不变的条件是,由此推得612.,方法二：,由此推得420,13/21,4.3灵敏度分析的程序,1-1/42,3/4,3,2,x1x2x6,3.553,4001/21/2-1/41,4101/2-1/21/40,601-3/81/83/160,5600-11/8-3/8-17/160,X*=(4,6,0,0,0,4)T,z*=56,x6,例10分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响?,2,5,2X1+,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章对偶问题-,-53-,表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。,-第2章对偶问题-,-54-,例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为换出变量。经基