灵敏度分析与线性规划的对偶理论.ppt

1,运筹学,灵敏度分析与 线性规划的对偶理论,2,灵敏度分析,图解法下的灵敏度分析 定义：研究LP问题中目标函数系数C与约束条件中系数矩阵A与常数向量b的变化（局部或全部变动）对LP的最优解 与最优值 的影响程度分析的问题称为LP的灵敏度分析。 由于C，b，A通常表述产品需求，原材料价格，未来的商品售价及企业的加工能力、资源消耗，故在数学建模时的估计有可能出现误差，且未来的环境亦是不确定的，有可能出现变化，因此有必要对应用问题的解作灵敏度分析。,3,图解法下的灵敏度分析 灵敏度分析通常讨论如下内容： C，b，A变动（局部或全部）后LP最优解是否仍存在？若存在的话，最优解有多大程度的变化？ C，b，A在什么范围内变动时能保证LP的原最优解不变？ 若C，b，A的变动超出上述范围后，如何利用LP的原最优解 来求解变动后的 最优解。 这些C，b，A的变动，在出现情况下对决策者有利？在什么情况下对决策者不利？此称为对偶价格研究对象（C的变动对目标最优解的影响）。,4,各种问题求解 问题建模 求解算法（理论、算法步骤、计算复杂性） 解的存在性、唯一性、可靠性（误差分析、灵敏度分析）,5,估计有误差 未来环境变动,数值解,精确解,灵敏度分析,误差分析,数值解,估计正确,6,LPa（LP原规划）,max z=50x1+100x2,7,LPb（C的变动对LP最优解的影响）,max z=60x1+50x2,8,LPc（b1的变动对LP最优解的影响）,max z=50x1+100x2,9,LPd（b2的变动对LP最优解的影响）,max z=50x1+100x2,10,命题：在例1 的优化模型中，A，b不变，讨论C变动的如下问题： 欲使LP的最优解不变，仍为 ，C1与C2应满足什么条件？ 当C2=100 不变，欲使LP 的最优解不变，仍为 ，C1应满足什么条件？ 当C1=50 不变，欲使LP 的最优解仍为 ,C2应满足什么条件？ 当C1，C2均变动，例如C1=60，C2=50时，最优解是否变动？ 欲使最优解变动为 ，求C1，C2应满足的条件？,11,解： 由图(a)，原最优解 对应B点，设LE，LF，LG直线之斜率分别为kE，kF，kG，则由对应直线方程可得kE= -1，kF=0，kG= -2，kz= - G1/G2，此中kz为等值线z=50x1+100x2之斜率。由图(a)中知，欲使最优点仍为B，则应有 当C2=100时，由*式知，需要 方使最优点不变。 当C1=50时，由*式知，需要 方使最优点不变。,12,解： 当C1=60，C2=50时，由图(b)知最优点为C (100，200）,故最优解 且由*式知：此时显然不满足条件 欲使最优解变动为 即最优点为C时，由图(b)知应有 此时有最优值 z(100,200)=100C1+200C2。,13,14,问题：在例1的优化模型中，C不变，讨论b与A分别变动时的如下问题： b1=300310，b2，b3，A不变时，求设备(台时）的对偶价格Pb1。 b2=400410，b1，b3，A不变时，求原料(克）的对偶价格Pb2。,15,解： 。 。,16,计算机解法下的灵敏度分析(P102P112),17,LP：,LP ,18,（见上表）LP,19,20,注1,21,注2,LP最终单纯形表,22,注3,设G为R3中的凸集，它有8个顶点,每一个顶点对应一个基本可行解，当采用单纯形表迭代时，其基本原则是以一个初始顶点开始，然后沿相邻顶点行进(迭代)，直到终点(最优解)为止。 注意到在R3中的凸集D的每一个顶点的相邻顶点有三个（也可有五个如（b)等）凸集D中，每一顶点或基本可行解对应一个基矩阵，则相邻顶点对应的基矩阵只有一列不同），因此从一个起点B0(对应一个初始基本可行解或初始基)开始，沿相邻顶点行进（迭代），直到终点（对应最优解）B2的迭代或运行路径可以有多条，如B0B1B2，B0B5B4B3B2等，这多条路径尽管有相同的起点（初始可行解），相同的终点（最优解），但迭代步数可以不等。,23,(a),(b),24,25,LP： L 次 迭 代,LP r 次 迭 代,26,27,28,例9,对上述LP的C1(又称价值系数)作灵敏度分析,29,解1,30,解2,31,对上述LP的b1作灵敏度分析 解,32,33,34,35,36,结论：当 时，不仅LP与LP有相同最优解，见迭代过程亦相同。一般迭代过程可不同，但最终单纯形表结果相同，由于迭代过程为初等行变换，故变换后之方程与原方程同解，故不影响最终结果，此二数应在0点的两侧。,37,0,38,39,40,LP：,LP ,证： 1,41,42,若在LP最终单纯形表中，xk为基变量，此时原最优解的可行性与最优性都可能遭到破坏，故需修改初始单纯形表并重新计算。,43,例9,在原例1中，该厂除生产，产品外，现又试制成一种新产品，并知生产单位产品需设备2台时，消耗原料A需0.5Kg，原料B需1.5Kg，此时可获利150元，试问该厂是否应该生产产品，或此时保持原方案是否合适？ 若该厂对产品的工艺结构又有了改进，此时生产单位产品需使用1.5设备台时，消耗原料A需2Kg，消耗原料B需1Kg，而同时经计算每件产品的利润为160元，问此时该厂对原生产计划是否要改变？如何改变？,44,解 设xj生产j产品的数量，j=1，2，3，则上述问题可看作原LP1的扩充或修改。,max z=50x1+100x2+150x3 LP2: s.t x1+x2+2x3+s1=300 2x1+x2+0.5x3+s2=400 x2+1.5x3+s3=250 xj, sj0, j=1,2,3,45,46,故该厂仍应保持原生产方案，即生产产品50件，产品250件，不生产产品可得最大利润2.75万元。,47,解 当该厂对产品工艺结构改进后，该生产计划问题可看作原问题LP1LP3 (本例得到退化的最优解),max z=50x1+100x2+160x3 LP2: s.t x1+x2+1.5x3+s1=300 2x1+x2+2x3+s2=400 x2+x3+s3=250 xj, sj0, j=1,2,3,48,49,即此时该厂不生产产品与，单独生产产品200件可获得最大利润32000元=3.2万元,50,51,52,上述命题4中的有关概念定义于下： Cj的允许增加值=Cj上界Cj当前值 Cj的允许减少值=Cj当前值 Cj下界 bi的允许增加值=bi上界bi当前值 bi的允许减少值=bi当前值 bi下界 Cj允许增加百分比= Cj实际增加值/ Cj允许增加值(%) Cj允许减少百分比= Cj实际减少值/ Cj允许减少值(%) bi允许增加百分比= bi实际增加值/ bi允许增加值(%) bi允许减少百分比= bi实际减少值/ bi允许减少值(%),53,54,55,解：,56,例11：在例10中 对于CC，LP与LP是否有相同最优解？ 对于bb， LP与LP是否有相同的关于bi 的对偶价格？ 解,57,注 若允许增加量（减少量）为（）时，允许增加（减少）百分比= 命题4（百分之百法则）仅适用于C或b中仅有一个变动时之判断，当C，b同时变化时应另行寻找求解方法。,58,对偶规划,定义与问题 问题：某甲厂在计划期内安排、两种产品。已知生产一个产品（或）所需的设备A、B、C的台时和相应利润如下表。 试问该厂拟生产多少产品和，方可使其获利最大（产品和为市场紧俏产品，均可卖出）？,59,解：设x1和x2为生产产品和的计划数量（件），则有,60,问题（新的资本运作思想）：某厂（乙厂）根据市场需要与资金状况决定停止生产原产品和，而将设备A、B、C出租已获利，目前已有某工厂与甲厂洽谈，拟租用甲厂设备A、B、C生产产品和。 考虑到租赁市场上还有多家企业可供设备A、B、C出租，为使在此租赁市场的价格竞争中处于有利地位，试问甲厂应如何确定其设备A、B、C的合理租金？（资源供应量，设备台时消耗与单位产品利润仍然同上表）,61,解：设y1、y2、y3为设备A、B、C的每台时租金（元），为使市场竞争有利，应使总设备台时租金尽可能少，为使有利可图，该厂获得的租金应不低于原生产利润。,min f=300y1+400y2+250y3 s.t y1+2y250 y1+y2+y3100 y1,y2,y30,62,63,Def19：设C=(C1,C2,C3)，x=(x1,x2,xn)T，b=(b1,b2,bm)T，y=(y1,y2,ym)T，则称LP1： 为原规划，LP2： 为LP1的 对偶规划。 由上定义容易推得若原规划LP1： 则 LP1有对偶规划LP2：,64,这是由于,y=(y1,y2)T,对偶,Y=y1-y2,65,66,基本理论,Th10：若LP1的对偶规划是LP2，则LP2的对偶规划为LP1，即原规划与对偶规划互为对偶。 Th11：若LP1与LP2互为对偶，且两个线性规划且可行（均有可行解或可行域非空），则LP1与LP2均有最优解（分别为 与 ），且有相同的最优值，即有 Th12：（最优性原理）若LP1与LP2互为对偶，x*与y*分别为LP1与LP2的可行解，且对应的目标函数值相等Cx*=bTy*，则x*与y*亦分别为LP1与LP2的最优解。,67,Th13：设LP1与LP互为对偶，B是LP1的最优可行基，CB为LP1目标函数中基变量对应的价值系数，取 则 为LP2的最优解。 Th14：设LP1与LP2互为对偶，若LP1有最优解，则LP2亦存在最优解，且两最优值相等，反之亦然，即LP2有最优解，则LP1亦有最优解，且两最优值相等。,基本理论,68,例12（P115）求解例1之LP1其对偶规划LP2之最优解。 解1：,min f=300y1+400y2+250y3 s.t y1+2y250 2y1+y2+y3100 y1,y2,y30,max z=50x1+100x2 s.t x1+x2300 2x1+x2400 x2250 x1,x20,LP1:,LP2:,互为对偶,69,解2：对LP2运用单纯形法求解，为此需将LP2化成标准形LP2，并采用大M法求解。,70,71,对偶单纯形法,对偶单纯形法是利用对偶原理而设计的一种单纯形法变种算法，与单纯形法一样，它是通过对原规划问题直接求解的一种方法，而并非是通过对对偶规划求解来获得原规划最优解。,72,算法原理,73,74,75,单纯形法思想： 保持x(i)基本可行性直到 可行 （ 可行 满足最优性条件）,对偶单纯形法思想：* 直到 基本可行保持Yi可行 i=1 ，保持x(i)最优性条件,对称思想,76,Th15：采用下述如图的算法可以实现如*所示的LP求解思路，并可求得LP最优解或无可行解。 上述思路与算法由PaPadimitriou C. H& Steiglitz . K在下述专著证明。Combinational Optimization Algorithms and Complexity，NewJersey PrenticeHall，1982,77,建立初始单纯形表，以使其具有原规划(LP1)的一个基本解和对偶规划(LP2)的一个可行解（即原问题 ），r=0,b(r)0,r=r+1,END,LP1(原)无 可行解,N,N,Y,Y,78,例13：,min z=12x1+8x2+16x3+12x4 LP1: s.t 2x1+x2+4x32 2x1+2x2+4x43 x1,x2,x3,x40,max z=-z=-12x1-8x2-16x3-12x4 LP1: s.t 2x1+x2+4x3s1=2 2x1+2x2+4x4 s2=3 xj0, j=14，s1,s20,max z=-12x1-8x2-16x3-12x4 LP“1: s.t -2x1-x2-4x3+s1=2 -2x1-2x2-4x4 + s2=3 xj0, j=14，s1,s20,不用大M法，用对偶单纯形法，约束方程也不用初等变换法（两边同乘 1/4）,79,80,bT=(2,3),81,注意到对偶单纯形法与单纯形法之区别仅在于进出基规则不同，而其它均相同，故单纯形法的以下性质，对偶单纯形法中仍保持 1 1 1,max f=2y1+3y2 s.t 2y1+2y212 y1+2y218 4y116 4y216 yj0，j=14,LP1 LP2,对偶,82,对偶单纯形法在迭代过程中始终保持了Yi的可行性，直到x(i)基本可行。这只以从上表计算所得的Yi(i=0,1,2,3)代入上述对偶规划LP2的约束方程验证满足即可。也可从对偶单纯形表中各次迭代后始终保持了最优性条件可知。即(i)0，i=0,1,2,3。 验证LP2目标函数可知f(yi)逐步递增到最大值 而由上对偶单纯形表知有f(Yi)= - z(x(i)，i=0,1,2,3=z(xi)， z(x0)=0 z(x1)= 9 z(x2)=13 z(x3)=14=f(Y3) 但需注意此中的xi(i=0,1,2,3)并非基本可行解（容易验证不满足LP1约束方程）,83,算法比较,例14：在例1中若A、C，bj(j1)不变，b1=300b1=350(b1=50)，交替运用单纯形法与对偶单纯形法，求设备台时的对偶价格Pb1。,形是 法使 的用 基对 本偶 条单 件纯,84,由前知当-50b125或250b1325时LP与LP有相同最优解，现b1=350，故LP有新最优解。 解：为交替使用对偶单纯形法求LP最优解，注意到由单纯形表中有 ，故可由此开始以下采用对偶单纯形表，为此需先求出 ，且A(2)不变。,LP,LP,85,86,87,由前知有P300(10)=50，由此可知关于b1的对偶价格P300(10)=50 ，P300(50)=25。,88,影子价格,由Th14，当对偶规划有最优解时，原规划亦有最优解且最优值相等，即有 ，称对偶价格最优解的第i分量yi为资源i的影子价格，它表示资源bi的每一个单位对目标的贡献，或相当于一个单位资源i在实现最大利润时的一种价格估计（这种估计是针对具体企业，具体产品而存在的一种特殊价格，故称影子价格），从经济上考虑，当i资源市场价yi 时，企业可买进i资源j否则可卖出i资源。,89,LP求解步骤及软件包操作与说明,LP求解步骤 软件包操作与说明,90,LP求解步骤,91,说明 根据实际需要，确定决策变量与目标函数。 约束条件通常为资源约束（广义）一般有时间，费用（效益）、人力、设备资源、技术性能要求等要素，详见下表。约束方程（或不等式）应是决策变量的函数。,92,说明 NLP有简约剃度法、投影剃度法、惩罚函数法、近似线性化法、共轭方向法、随机逼迫法等。 依据LP的具体建立形式确定采用何种算法（如单纯形法、修正单纯形法，大M法等） 解的合理性主要指经济合理性、工程技术合理性，而灵敏度分析是指LP的可靠性。,93,软件包操作与说明（P28P34，P406） 该软件包可在Windows及UCDOS中文平台下运行,* * * * * 主 菜 单* * * * * 1.线性规划 7.最小费用最大流 2.运输问题 8.关键路线 3.整数规划 9.存贮论 4.最短路法 10.排队论 5.最小生成树 11.决策分析 6.最大流量 12.预测问题 请输入你的选择(112)：1,94,输入注意要点：P29 输入注意要点：P29P34,* * *问题选择菜单 * * * 1.建立一个新问题 2.恢复已解决的问题 3.继续现在的问题 4.删除已解决的问题 5.返回主菜单 请输入你的选择(15)：1,目标函数：max50x1+100x2 变量个数：2 输入第一个约束：x1+x2300 输入第二个约束：2x1+x2400 输入第三个约束：x2250 输入第四个约束：END,*问题处理菜单* 1.解决这个问题 2.保存这个问题 3.显示编辑这个问题 4.返回上级菜单 输入选择(1,2,3,4)：1,95,模型的建立与标准化,模型的建立 例15（生产计划问题P44） 例16（投资问题P54） 模型的标准化与初始基构造,2019/11/16,96,生产计划的问题,例15：明兴公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。有关生产工时及其约束、成本、价格情况见表41；公司中可利用的总工时为：铸造8000小时，机加工12000小时和装配10000小时。公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造应多少由公司铸造？应多少由外包协作？,2019/11/16,97,产品单位利润=单位产品售价 (自行铸造、外包铸造成本+机加工成本+装配成本） x1三道工序均由本公司生产的甲产品数量（件） x2三道工序均由本公司生产的乙产品数量（件） x3三道工序均由本公司生产的丙产品数量（件） x4铸造外包，机加工，装配本公司生产的甲产品数量 x5铸造外包，机加工，装配本公司生产的乙产品数量,2019/11/16,98,表4-1,99,解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，设x4，x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。 计算每件产品的利润分别如下： 产品甲全部自制的利润=23(3+2+3)=15(元) 产品甲铸造外协，其余自制的利润=23(5+2+3)=13(元) 产品乙全部自制的利润=18(5+1+2)=10(元) 产品乙铸造外协，其余自制的利润=18(6+1+2)=9(元) 产品丙的利润=16(4+3+2)=7(元),100,并由上表可计算甲、乙、丙产品利润如下表 我们建立数学模型如下： 目标函数：max z=15x1+10x2+7x3+13x4+9x5 约束条件： 5x1+10x2+7x38000(铸造) 6x1+4x2+8x3+6x4+4x512000(机加工) 6(x1+x4)+4(x2+x5)+8x312000 3x1+2x2+2x3+3x4+2x510000(装配) 3(x1+x4) +2(x2+x5) +2x310000 x1，x2，x3，x4，x50,101,用管理运筹学软件进行计算，计算机计算结果显示在图4-1 中。 目标函数最优值为：29400 变量 最优解 相差值 x1 1600 0 ，故相差值为0 x2 0 2 欲使 ，在C2=10元基础上还应增加2元利润 x3 0 13.1 欲使 ，在C3=7元基础上还应增加13.1元利润 x4 0 0.5 欲使 ，在C4=13元基础上还应增加0.5元利润 x5 600 0 ，故相差值为0 约束 松弛/剩 对偶价格 余变量 1 0 0.3 铸造能力每增加一工时，可增加利润0.3元 2 0 2.25 机加工能力每增加一工时，可增加利润2.25元 3 4000 0 由于装配能力未完成，故再增加亦无作用,最优方案下，铸造能力全用完,机加工能力全用完,装配能力尚有4000小时未用完,铸造能力,机加工能力,装配能力,102,目标函数系数范围 变量(价值系数) 下限 当前值 上限 x1 (C1) 14 15 无上限 x2 (C2) 无下限 10 12 x3 (C3) 无下限 7 20.1 x4 (C4) 无下限 13 13.5 x5 (C5) 8.667 9 10 常数项范围： 约束 下限 当前值 上限 1 (b1) 0 8000 10000 2 (b2) 9600 12000 20000 3 (b3) 6000 10000 (无上界),为使最优解 不变时C1C5系数允许变动的上下界,为使对偶价格(Pb1,Pb2,Pb3)=(0.3,2.25,0)不变时，b1,b2,b3允许变动的上下界,103,投资问题,例16：某部门现有资金200万元，今后五年内考虑给以下的项目投资，已知 项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%。 项目B：从第一年到第四年每年年初都可以投资，次年末收回本利125%，但规定每年最大投资额不能超过30万元。 项目C：第三年初需要投资，到第五年末能回收本利140%，但规定最大投资额不能超过80万元。 项目D：第二年初需要投资，到第五年末能回收本利155%，但规定最大投资额不能超过100万元。,104,据测定每万元每次投资的风险指数如下所示： 问： 在不考虑风险前提下，应如何确定这些项目的每年投资额，使得第五年末拥有资金的本利金额为最大？ 应如何确定这些项目的每年投资额，使得第五年末拥有资金的本利在330万的基础上使得其投资总的风险系数为最小？,105,解： 确定变量a。这是一个连续投资的问题，我们设xij=第i年初投资于j项目的金额(单位万元)，根据给定条件，将变量列于表4-8。 约束条件 因为项目A每年可以投资，并且当年末都能收回本息，所以该部门每年都应把资金都投出去，手中不应当有 剩余的呆滞资金，因此,表4-8,106,第一年：该部门年初有资金200万元，故有x1A+x1B=200 第二年：因第一年给项目B的投资要到第二年末才能回收，所以该部门在第二年初拥有资金仅为项目A在第一年投资额所回收的本息110%x1A，故有x2A+x2B+x2D=1.1x1A 第三年：第三年初的资金额是从项目A第二年投资和项目B第一年投资所回收的本息总和1.1x2A+1.25x1B 故有x3A+x3B+x3C=1.1x2A+1.25x1B 第四年：同以上分析，可得x4A+x4B=1.1x3A+1.25x2B 第五年：x5A=1.1x4A+1.25x3B 另外，对项目B，C，D的投资额的限制有 xib30 (i=1，2，3，4) x3C80 x2D100,107,目标函数 该问题要求在第五年末该部门所拥有的资金额达到最大，这个目标函数可以表示为 max z=1.1x5A+1.25x4B+1.40x3C+1.55x2D 这样可以得到如下数学模型 max z=1.1x5A+1.25x4B+1.40x3C+1.55x2D s.t x1A+x1B=200 x2A+x2B+x2D=1.1x1A x3A+x3B+x3C=1.1x2A+1.25x1B x4A+x4B=1.1x3A+1.25x2B x5A=1.1x4A+1.25x3B xiB30 (i=1，2，3，4) x3C80 x2D100 xij0,108,解 投资风险指数 ，S=A,B,C,D 其中项目j的风险权重Wj表每投资项目j一万元可能的损失数（单位：万元），亦可理解为投资同样数额于项目A,B,C,D所冒的风险程度比例，WA:WB:WC:WD=1:3:4:5.5 。 项目j的投资总额为fj（单位：万元），,x1A x1