对偶问题与灵敏度分析.

第三章对偶问题与灵敏度分析第一讲对偶理论第二讲灵敏度分析第一讲对偶理论•例1中该厂的产品销售，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对是否出租做出抉择。一、对偶问题产品车间工时单耗甲乙生产能力ABC10023481236单位产品获利35第一讲对偶理论•对原企业而言，它用于出租或转让的资源收益不应低于自行生产产品所获得的利润，才肯出租或转让。•在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：①如何合理安排生产，取得最大利润?②为保持利润水平不降低，资源转让的最低价格是多少？•问题①的最优解：x1=4，x2=6，Z*=42。一、对偶问题第一讲对偶理论第二个问题：出让定价•假设出让设备A、B、C所得利润分别为y1、y2、y3•原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有对甲产品y1+0y2+3y3≥3•同理，对乙产品而言，则有0y1+2y2+4y3≥5•设备台时出让的收益（租用企业希望出让的收益最少值）MinW=8y1+12y2+36y3•显然还有y1，y2，y3≥0第一讲对偶理论•称后一个线性规划问题为前一个线性规划问题的对偶问题。•对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=42•两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。•对偶问题的最优解对应于原问题最优单纯型法表中“初始基变量的检验数的负值”。例1的对偶问题的数学模型MinW=8y1+12y2+36y3y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.MaxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.第一讲对偶理论原问题最优单纯型法表•对偶问题的最优解：y1=0，y2=1/2，y3=1对应于原问题最优单纯型法表中，初始基变量x3,x4,x5的检验数的负值。Cj35000x1x2x3x4x50x340012/3-1/35x260101/203x14100-2/31/3检验数j-42000-1/2-1CBXBbMaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2……………am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0线性规划原问题（P）对偶问题（D）MinZ=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2……………a1ny1+a2ny2+…+amnym≥cmy1,y2,…,ym≥0对称形式下对偶问题的一般形式对称形式：变量均为非负，其约束条件当目标函数求极大时均取“≤”，当目标函数取极小时均取“≥”。第一讲对偶理论•若原问题为极大，则对偶问题为极小；•对极大的原问题，其约束条件为≤，而极小化的对偶问题的约束为≥；•原问题的变量个数即为对偶问题的约束条件的个数，而原问题的约束条件的个数，即为对偶问题的变量的个数；•原问题的约束条件的右端常数项即为对偶问题的目标函数中变量的系数，而原问题的目标函数中变量的系数即为对偶问题的约束条件的右端常数项。对称形式下对偶模型的特点第一讲对偶理论对称形式下原问题与对偶问题的对应关系MaxZMinWx1x2x3x3≥0y1y2y3y4a11a12a13≤≤≤≤b1b2b3b4a21a22a23a31a32a33a41a42a43yi≥0c1c2c3一般形式下对偶关系对应表原问题(或对偶问题)对偶问题(或原问题)目标函数类型MaxMin目标函数系数与右边项的对应关系目标函数系数右边项系数右边项系数目标函数系数变量数与约束数的对应关系变量数n约束数m约束数n变量数m原问题变量类型与对偶问题约束条件的对应关系≥0变量≤0无限制≥约束≤=原问题约束类型与对偶问题变量类型的对应关系≤约束≥=≥0变量≤0无限制第一讲对偶理论例:写出对偶模型MaxW=5y1+10y2+4y3y1+4y2+1y3≤5-y1+y2+y3≥32y1-y2-y3=-1y1≥0,y2≤0,y3无限制S.t.MinZ=5x1+3x2-x3x1-x2+2x3≥54x1+x2-x3≤10x1+x2-x3=4x1≥0,x2≤0,x3无限制S.t.第一讲对偶理论练习:求对偶模型MaxZ=x1+2x2-3x3+4x4-x1+x2-x3-3x4=56x1+7x2-x3+5x4≥812x1-9x2+7x3+6x4≤10x1≥0,x3≥0,x2,x4无限制S.t.第一讲对偶理论二、对偶问题的基本性质•对称性：对偶问题的对偶是原问题。•弱对偶性：若X0为原问题(P)的可行解，Y0是对偶问题(D)的可行解，则CX0≤Y0b。•最优解：若X*为(P)的可行解，Y*是(D)的可行解，且CX*=Y*b，则X*，Y*分别为最优解。•强对偶性若(P)有最优解，则(D)也有最优解；反之亦然，且两者目标函数相等。第一讲对偶理论证明：此问题的对偶问题为：例题:已知线性规划问题MinZ=x1-x2+x3x1-x3≥4x1-x2+2x3≥3x1,x2,x3≥0S.t.试用对偶理论证明此线性规划问题有无界解(即有可行解，但无最优解)。MaxW=4y1+3y2y1+y2≤1-y2≤-1-y1+2y2≤1y1,y2≥0S.t.第一讲对偶理论•说明yi是右端项bi每增加一个单位的第i种资源对目标函数Z的贡献。•对偶变量yi在经济上表示原问题第i种资源的边际价值。•对偶变量的值yi*所表示的第i种资源的边际价值，称为影子价值。若原问题的价值系数Cj表示单位价格，则yi*称为影子价格。若原问题的价值系数Cj表示单位利润，则yi*称为影子利润。三、对偶问题的经济解释——影子价格njmiiijjWybxcZ11******iiybZ此时，同时达到最优解bi为第i种资源的拥有量第一讲对偶理论•影子价格不是资源的实际价格(市场价格)，而是资源配置结构的反映，是在其它数据相对稳定的条件下对现有资源实现最大效益时的一种估价；它表明资源增加对总效益产生的影响。•对资源i总存量的评估：购进or出让•对资源i当前分配量的评估：增加or减少①它表明了当前的资源配置状况，告诉经营者应当优先增加何种资源，才能获利更多。②告诉经营者以怎样的代价去取得紧缺资源。③提示设备出租或原材料转让的基价。④告诉经营者补给紧缺资源的数量，不要盲目大量补给。⑤借助影子价格进行内部核算。•特别注意第一讲对偶理论•对偶问题的最优解：y1*=0，y2*=1/2，y3*=1，W*=42•y2*=1/2表示设备B的影子价格为1/2元/台时，说明该厂在当前的生产和利润情况下，每增加设备B一台，利润会增加1/2元。•影子价格不是固定不变的，它因企业生产资源与利润的不同而不同，而市场价格是已知且相对稳定的。一般地，当某种资源(设备)的市场价格高于影子价格时，可将资源出租或转让。反之，应该从市场买进该种资源，以获得更大的利润。解释例1的对偶问题的数学模型MinW=8y1+12y2+36y3y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.MaxZ=3x1+5x2x1≤82x2≤123x1+4x2≤36x1,x2≥0S.t.第一讲对偶理论•从原规划的一个对偶可行解(≤0)出发，(从原规划的一个基解出发，此基解不一定可行，但它对应者一个对偶可行解即检验数非正)，且保持其对偶变量的解为可行解。•检验原规划的一个基解是否为基可行解，即是否有负的分量。若是基可行解，即b′=B-1b≥0，则为最优解，•否则进行基变换，得另一个基解，此基解对应着另一个对偶可行解。重复(2)。单纯形法的思路对偶单纯形法的思路•确定初始可行基，初始基可行解(每个分量非负)。•判断是否最优，是否有所有(非基变量)检验数≤0(Max)。•基变换。第一讲对偶理论•适用于：•对偶单纯形图表计算步骤：(1)列出初始单纯形表，得初始基解，要求所有的检验数≤0.(2)检验b列，若所有的b′=B-1b≥0,则得到最优解。若bi′0且bi′所在行的各系数aij≥0,则原规划无可行解；否则取Min{bi′|bi′0}=bl,则相应的xl为离基变量。(3)按照θ=Min{j/alj|alj0}=k/alk确定xk进基变量。(4)以alk为主元素，按单纯形法的方法进行迭代，得到新的表重复(2).对偶单纯形法——应用于对称形式MinZ=CXAX≥bC≥0化标准形时对约束条件两边乘以X≥0-1，且目标函数的系数皆为≤0.S.t.第一讲对偶理论•Cj-8-12-3600CBXBbx1x2x3x4x50x4-3-10-3100x5-50-2-401检验数j0-8-12-3600比值例题：使用对偶单纯形法MinW=8y1+12y2+36y3y1+0y2+3y3≥30y1+2y2+4y3≥5y1，y2，y3≥0S.t.MaxW′=-8x1-12x2-36x3+0x4+0x5-x1-0x2-3x3+x4=-30x1-2x2-4x3+x5=-5x1,x2,x3,x4,x5≥0S.t.-69--主元列初始单纯形表-5-2•x5为出基变量，x2为进基变量第一讲对偶理论•对偶单纯形法(续)Cj-8-12-3600CBXBbx1x2x3x4x50x4-3-10-310-12x25/20120-1/2检验数j30-80-120-6比值8-4---36x311/301-1/30-12x21/2-2/3102/3-1/2检验数j42-400-4-6比值主元•此时b列皆非负且所有的非基变量检验数j≤0，得最优解Y*=(0,1/2,1,0,0)T,最优目标函数值W′=-42,W=42..第一讲对偶理论•习题：用对偶单纯形法求解：MaxZ=-x1-2x2-3x32x1-x2+x3≥4x1+x2+2x3≤8x2–x3≤2x1，x2，x3≥0S.t.MaxZ=-x1-2x2-3x3-2x1+x2-x3+x4=-4x1+x2+2x3+x5=8x2–x3+x6=2x1,x2,x3,x4,x5,x6≥0S.t.Cj-1-2-3000CBXBbx1x2x3x4x5x60x4-4-21-11000x581120100x6201-1001检验数j0-1-2-3000比值-41/2-3----2第一讲对偶理论•最优解为X*=(2,0,0,0,6,2)T,最优值Z*=-2.Cj-1-2-3000CBXBbx1x2x3x4x5x60x4-4-21-11000x581120100x6201-1001检验数j0-1-2-3000比值-41/2-3----2-1x121-1/21/2-1/2000x5603/23/21/2100x6201-1001检验数j20-5/2-5/2-1/200比值第二讲灵敏度分析•线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据(Ci,bj,aij)发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。•灵敏度分析的意义第二讲灵敏度分析•灵敏度分析又称敏感性分析或优化后分析，它研究基础数据发生波动后对最优解的影响，以及在多大的范围内波动才不影响最优基。灵敏度分析就是研究最优解对数据变化的敏感程度。感性太强，则说明最优解的稳定性程度较低。•灵敏度分析解决的问题：参数(基础数据)在什么范围变化而最优基不