线性规划灵敏度分析.ppt

Chapter 2线性规划灵敏度分析线性规划灵敏度分析上海工程技术大学上海工程技术大学管理学院管理学院Chapter 2 灵敏度分析灵敏度分析本章提要本章提要 Content单纯形法的矩阵描述改进单纯形法对偶问题提出线性规划对偶理论对偶问题的基本性质影子价格对偶单纯形法灵敏度分析案例分析及Matlab求解 习题Chapter 2 灵敏度分析灵敏度分析 单纯形法的矩阵描述？单纯形法矩阵的描述标准型标准型maxZ=CX AX=b X 0已知：已知：A、b、c A=(NB)B=EChapter 2 灵敏度分析灵敏度分析用非基变量表示基变量用非基变量表示基变量Z=CBB-1b+(CN-CBB-1 N)XNXB=B-1 b-B-1 NXNCBB-1b CN-CBB-1 N O B-1 b B-1 N ECBB-1b C-CBB-1 A B-1 b B-1 AChapter 2 灵敏度分析灵敏度分析C-CBB-1A=(CN CB)-CBB-1(NB)=(CN-CBB-1N,CB-CBB-1B)B-1A=B-1(NB)=(B-1N,B-1B)单个检验数：单个检验数：j=Cj -CBB-1 Pj 某列某列Pj =B-1 Pj Chapter 2 灵敏度分析灵敏度分析改进单纯形法改进单纯形法对对maxZ=CX AX bX 0A=(P1 P2 Pn)(1)、已有初始可行基、已有初始可行基B，求，求B-1，XB=B-1 b(2)、计算、计算j=Cj-CB B-1Pj 若全部若全部 j 0 0，则计算则计算Z0=CB B-1 b,停；否则，取停；否则，取m+k=maxj，Xm+k换入。换入。j0Chapter 2 灵敏度分析灵敏度分析(3)、计算、计算Pm+k=B-1Pm+k，若，若Pm+k 0 0，则无有限则无有限最优解最优解,停；否则停；否则=minbiAim+karm+k 0=brarm+kXr 换出换出(4)、最小、最小比值法比值法：(5)、新基、新基B。转。转(1)。Chapter 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，而将其所有资源出租或外售.这时工厂的决策者就要考虑给每种资源如何定价的问题.设用,分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.他在做定价决策时,作如下比较:若用一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有 Y1+4Y2 2举例Chapter 2 灵敏度分析灵敏度分析 同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有 2Y1+4Y3 3 把工厂所有设备台时和资源都出租和出让,其收入为 f=8Y1+16Y2+12Y3 从工厂决策者的角度来看W当然是越大越好,但从接受者眼光来说W是越少越好,所以工厂决策者只可以在满足所有产品的利润条件下,使其总收入尽可能的小.因此可以列出如下线性规划问题 f=8Y1+16Y2+12Y3 Y1+4Y2 2 2Y1+4Y3 3 Yi 0,i=1,2,3 Chapter 2 灵敏度分析灵敏度分析v各模型中有关数据的“位置”示意图如下。Chapter 2 灵敏度分析灵敏度分析问题二问题二:考虑：资源拥有者为了实现一定的收入目标，将其 所拥有的资源出售，给每一种资源如何定价？Chapter 2 灵敏度分析灵敏度分析Yi表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：如果资源拥有者将所有资源出售，则他得到的总收 入Chapter 2 灵敏度分析灵敏度分析 资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。线性规划的对偶理论线性规划的对偶理论对偶定义 对称形式：互为对偶 (LP)Max z z=c cT x x (DP)Min f f=b bT y y .AxAx b b .A AT y y c c x x 0 y y 0 “Max-”“Min-”Chapter 2 灵敏度分析灵敏度分析Chapter 2 灵敏度分析灵敏度分析Chapter 2 灵敏度分析灵敏度分析v如上面例题所示一对对称形式的对偶规划对称形式的对偶规划之间具有下面的对应关系(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。Chapter 2 灵敏度分析灵敏度分析v然而在一般线性规划问题中遇到非对称形式时我们的处理如下：非对称形式的对偶规划非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。v对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。Chapter 2 灵敏度分析灵敏度分析v非对称型对偶问题非对称型对偶问题Chapter 2 灵敏度分析灵敏度分析举例Chapter 2 灵敏度分析灵敏度分析Chapter 2 灵敏度分析灵敏度分析综上所述其变换形式如下：综上所述其变换形式如下：原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0 00 0=无约束无约束变变量量n个个n个个约约束束条条件件0 00 0无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项Chapter 2 灵敏度分析灵敏度分析 小练习写出下列问题的对偶问题Chapter 2 灵敏度分析灵敏度分析Chapter 2 灵敏度分析灵敏度分析对偶问题的基本性质对偶问题的基本性质 性质性质1:1:对称性对称性规范原始，对偶问题的对偶是原问题。Max z=CX Min f=Yb s.t.AX b s.t.YA C X 0 Y 0 “Max-”“Min-”Chapter 2 灵敏度分析灵敏度分析性质性质2 2:弱对偶原理弱对偶原理（弱对偶性）：设 和 分别是 问题（P）和（D）的可行解，则必有性质性质3:3:最优性判别定理最优性判别定理 若 X*和 Y*分别是 P 和 D 的可行解且 CX*=Y*b，则X*.Y*分别是问题 P和D 的最优解。Chapter 2 灵敏度分析灵敏度分析性质性质4:4:线性规划的对偶原理线性规划的对偶原理（1）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（强对偶性）（2）若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性）性质性质5:5:互补松弛定理互补松弛定理设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是Chapter 2 灵敏度分析灵敏度分析同时成立 一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。Chapter 2 灵敏度分析灵敏度分析例题例题判断下例说法是否正确，为社么？A 如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。Chapter 2 灵敏度分析灵敏度分析v解：解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。Chapter 2 灵敏度分析灵敏度分析例题:已知原问题的最优解为X*=（），Z=12 试求对偶问题的最优解。Chapter 2 灵敏度分析灵敏度分析解解:将将X X*=（0.0.40.0.4）代入原问题中，有下式：）代入原问题中，有下式：Chapter 2 灵敏度分析灵敏度分析所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3 =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)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。Chapter 2 灵敏度分析灵敏度分析（2）影子价格表明资源增加对总效益产生的影响。根据推推论论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是Chapter 2 灵敏度分析灵敏度分析 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。Chapter 2 灵敏度分析灵敏度分析 需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。Chapter 2 灵敏度分析灵敏度分析对偶单纯形法对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应着一个对偶可行解对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。Chapter 2 灵敏度分析灵敏度分析对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。Chapter 2 灵敏度分析灵敏度分析对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程：1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有akj0 则选 =minj/akjakj0brMin-bi/airair0Chapter 2 灵敏度分析灵敏度分析例题:Max z=2x1+3x2+0 x3+0 x4+0 x5 .x1+2x2+x3 =8 4x1+x4 =16 4x2+x5=12 x1,x2,x3,x4,x5 0Chapter 2 灵敏度分析灵敏度分析最终单纯形表为:Chapter 2 灵敏度分析灵敏度分析 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1,x5,x2分别变为：4+04=4,4+(-2)4=-40csMinj/asjasj0 Chapter 2 灵敏度分析灵敏度分析例题:Max z=2x1+3x2+0 x3+0 x4+0 x5 .x1+2x2+x3 =8 4x1+x4 =16 4x2+x5=12 x1,x2,x3,x4,x5 0Chapter 2 灵敏度分析灵敏度分析从表中看到j=cj-(c1a1j+c5 a5j+(c2+c2)a2j)j=3,4可得到-3c21时，原最优解不变。Chapter 2 灵敏度分析灵敏度分析 增加一个变量 增加变量 xn+1 则有相应的pn+1,cn+1。那么 计算出B B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表,若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解。补充Chapter 2 灵敏度分析灵敏度分析 增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。补充Chapter 2 灵敏度分析灵敏度分析案例分析及案例分析及Matlab求解求解 为了能够快速准确的运用对偶单纯形法来计算相关线性规划问题,我们使用MATLAB语言来实现,如书本上面所说的程序相对要复杂了点,所以我们使用MATLAB的优化工具箱里面的Linprog来实现我们的模型命令：1 x=linprog（c，A，b，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+x2+x3+x4 60 x3+x4 20 x1+x3 20 x1,x2,x3,x4 0Chapter 2 灵敏度分析灵敏度分析v根据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-4Chapter 2 灵敏度分析灵敏度分析v复习思考题：1、对偶问题和它的经济意义是什么？2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6、在线性规划的最优单纯形表中，松弛变量（或剩余变量），其经济意义是什么？7、在线性规划的最优单纯形表中，松弛变量的检验数，其经济意义是什么？8、关于单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？Shanghai University of Engineering Science