第二章线性规划的对偶理论与灵敏度分析教材课件.ppt

运筹学,赵明霞山西大学经济与管理学院,2023/4/3,2,第二章 线性规划的对偶理论与灵敏度分析,线性规划的对偶问题影子价格对偶单纯形法灵敏度分析,2023/4/3,3,例1,美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造、两种家电备多少件使获取的利润为最大。,第一节 线性规划的对偶问题,2023/4/3,4,标准化,最终单纯形表,2 1 0 0 0,最优解,X*=(7/2,3/2,15/2,0,0),Z*=17/2,2023/4/3,5,把解X=(7/2,3/2)代入原问题(因为x3、x4、x5为附加变量),分析,53215/2,A有空闲B设备已经饱和调试工序也已经满负荷,2023/4/3,6,6y2+y3,分析,设：y1 设备A值的价值 y2 设备B值的价值 y3 调试工序值的价值,2,5y1+2y2+y3,1,z=15 y1+24y2+5y3,总价值,min,2023/4/3,7,6y2+y3,2,5y1+2y2+y3,1,z=15 y1+24y2+5y3,min,z=-15 y1-24y2-5y3,max,6y2+y3 y4,=,2,5y1+2y2+y3 y5,1,=,y1,y2,y3,y4,y5,0,问题求解,2023/4/3,8,Y=(0,0,0),z=-17/2,z=17/2,2023/4/3,9,Y=(0,0,0),问题分析,问题的解,问题：,？,原问题：,问题的解,X*=(7/2,3/2,15/2,0,0),Z*=17/2,Z*=17/2,5*3/2=15/2,15,结论,两个问题的最优解的值一致最大值问题可行解的目标值必定不大于最小值问题可行解的目标值一个问题的剩余变量（松弛变量）不为0（即有资源剩余），则对应问题的解为0一个决策变量不为0，则对应的问题的约束条件的剩余变量(松弛变量)为0(即资源彻底用完),估价影子价格（即增加单位资源所得到的贡献）,Z=CX=Yb Z/b=(Yb)=Y,2023/4/3,10,Y=(0,0,0),X*=(7/2,3/2,15/2,0,0),解的关系,2023/4/3,11,一、对偶问题,对称形式,X 0,st.,AX b,max z=,CX,其中：C=（c1，c2,cn)b=（b1，b2,bm)T X=（x1，x2,xn)T Y=（y1，y2,ym)T,A=,a11 a12 a1na11 a12 a1n am1 am2 anm,Y 0,st.,ATY CT,min w=,YTb,2023/4/3,12,非对称形式,x1 0,x2 0,x3无约束,st.,a11x1+a12x2+a13x3 b1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3 b3,max z=c1x1+c2x2+c3x3,x1,x2,x3，x3 0,st.,a11x1-a12x2+a13x3-a13x3 b1a21x1-a22x2+a23x3-a23x3 b2-a21x1+a22x2 _ a23x3+a23x3-b2-a31x1+a32x2-a33x3+a33x3-b3,max z=c1x1-c2x2+c3x3-c3x3,y1,y2,y2，y30,st.,a11y1+a21y2 a21y2-a31y3 c1-a12y1-a22y2+a22y2-a32y3-c2a13y1+a23y2 a23y2-a33y3 c3-a13y1-a23y2+a23y2+a33y3-c3,min w=b1y1+b2y2-b2y2-b3y3,min w=b1y1+b2y2+b3y3,a11y1+a21y2+a31y3 c1a12y1+a22y2+a32y3 c2a13y1+a23y2+a33y3=c3,st.,y10,y2无约束，y3 0,2023/4/3,13,二、对偶规则,原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的系数矩阵转置后为对偶问题系数矩阵,变量、约束与系数,2023/4/3,14,变量与约束对应关系,2023/4/3,15,三、对偶问题的基本性质（对称形）,对称性：对偶问题的对偶问题是原问题弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1无界性：原问题无界，对偶问题无可行解,需要说明的是：这些性质同样适用于非对称形问题,2023/4/3,16,X 0,st.,AX b,max z=CX,X,Xs 0,st.,AX+IXs=b,max z=CX+0Xs,2023/4/3,17,B与B-1,2023/4/3,18,第二节 影子价格,bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而做的估价，为区别起见，称为影子价格(shadow price)。,2023/4/3,19,1、资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。2、影子价格是一种边际价格，若对式中目标函数z求bi的偏导数可得。这说明yi*的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数z的增量。,2023/4/3,20,3、资源的影子价格实际上又是一种机会成本。在完全市场经济条件下，当第2种资源的市场价格低于影子价格时，可以买进这种资源；相反，当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平，才处于平衡状态。4、在上一节对偶问题的互补松弛性质中有 时，yi=0；当yi0时，有，这表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。5、当产品产值大于隐含成本时，表明生产该产品有利，可在计划中安排，否则用这些资源来生产别的产品更为有利，就不在生产计划中安排。这就是单纯形表中各个检验数的经济意义。,2023/4/3,21,6、一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。如在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如在社会上可对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上缴的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。,2023/4/3,22,第三节 对偶单纯形法,对于单纯形法叠代过程本质：确保1）z变大；2）B-1b 0,由对偶理论知道，当原问题为最优解时，-0且为对偶问题的最优解，因此人们提出对偶单纯形法。叠代过程本质：1）0；2）逐步使B-1b 0,与,2023/4/3,23,6y2+y3,2,5y1+2y2+y3,1,z=15 y1+24y2+5y3,min,问题求解,2023/4/3,24,1.确定出基变量。在常数列中找一个最小的负常量，把这个常量所在行作为出基变量,2.确定入基变量。在系数列中找负数，把这个常量所在行作为入基变量。,2023/4/3,25,2023/4/3,26,第四节 灵敏度分析,灵敏度分析是指系统或事物对周围环境变化显示出来的敏感程度。,在LP问题中，aij、cj、bi都有可能发生变化，分析这些变化对最优解或目标值的影响程度就是灵敏度分析。,2023/4/3,27,cj通常表示一些估计或预测的数据，随市场而变化；aij通常随工艺技术条件的改变而改变；bi则反映了企业资源状况。,Z0=CBB-1b XB=B-1b,A=C-CBB-1 A N=CN-CBB-1 N j=Cj-CBB-1 Pj,2023/4/3,28,b*=B-1 b,最优解的增量b*与初始b的增量b 成B-1 倍变化,Pj*=B-1 Pj,最优解时的系数增量Pj*与初始的系数增量Pj也成B-1 倍变化,最优性条件可表达为：,2023/4/3,29,通常需要分析的项目：,(1)参数a，b，C在什么范围内变动，对当前方案无影响？,(2)参数b，b，c中的一个(几个)变动，对当前方案影响程度？,(3)如果最优方案改变，如何用简便方法求新方案？,2023/4/3,30,灵敏度分析的步骤：,1、将参数的改变通过计算反映到最终单纯形表上来。具体计算方法是，按下列公式计算出由参数aij，bi，cj的变化而引起的最终单纯形表上有关数字的变化。2、检查原问题是否仍为可行解。3、检查对偶问题是否仍为可行解。4、按下表所列情况得出结论或决定继续计算的步骤。,2023/4/3,31,一、分析cj的变化,线性规划目标函数中变量系数cj的变化仅仅影响到检验数(cj-zj)的变化。所以将cj的变化直接反映到最终单纯形表中，只可能出现上页表中前两种情况。,2023/4/3,32,例1-1：在美佳公司例子中，(1)若家电I的利润降至1.5元/件，而家电II的利润增至2元/件时，美佳公司最优生产计划有何变化；(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，该公司的最优生产计划将不发生变化？,2023/4/3,33,解(1)：将家电I、II的利润变化直接反映到最终单纯形表中得到表如下：,因变量x4的检验数大于零，故需继续用单纯形法迭代计算，得表如下：,即美佳公司随家电I、II的利润变化应调整为生产2件I，生产3件II。,2023/4/3,34,(2)：设家电II的利润为(1+m)元，反映到最终单纯形表中，得表如下：,为使上表中的解仍为最优解，应有：,解得：,即家电II的利润c2的变化范围应满足：,2023/4/3,35,二、分析bi的变化,右端项bi的变化在实际问题中反映为可用资源数量的变化。bi变化反映到最终单纯形表上将引起b列数字的变化，在表中可能出现第一或第三的两种情况。出现第一种情况时，问题的最优基不变，变化后的b列值为最优解。出现第三种情况时，用对偶单纯形法迭代继续找出最优解。,2023/4/3,36,例1-2：在上述美佳公司例子中，(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化；(2)若设备A和设备B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变。,2023/4/3,37,解(1)：因有，则：,将其反映到最终单纯形表中得表如下。由于该表中原问题为非可行解，故用对偶单纯形法继续计算，其结果如下量表所示：,2023/4/3,38,对偶单纯形法处理后结果：,由此美佳公司的最优计划改变为只生产5件家电I。,2023/4/3,39,(2)：设调式工序每天可用能力为(5+m)h，因有,将其反映到最终单纯形表中，其b列数字为：,当b=0时问题的最优基不变，解得-1=m=1。由此调试工序的能力应在4h-6h之间。,2023/4/3,40,三、增加一个变量xj的分析,增加一个变量在实际问题中反映为增加一种新的产品。其分析步骤为：1、计算 2、计算 3、若，原最优解不变，只需将计算得到的 和 直接写入最终单纯形表中；若，则按单纯形法继续迭代计算找出最优。例1-3：在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3h、4h、2h，该产品的预期盈利为3元/件，试分析该种产品是否值得投产；若投产，该公司的最优生产计划有何变化。,2023/4/3,41,解 设该公司生产x6件家电III，有c6=3，P6=(3,4,2)T,将其反映到最终单纯形表中得表如下:,2023/4/3,42,因，故用单纯形法继续迭代计算结果为：,由上表可知，美佳公司新的最优生产计划应该为每天生产7/2件家电I，51/4件家电III。,2023/4/3,43,四、分析参数aij的变化,aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为基变量，则aij的变化分析步骤可参照本节之三；若变量xj在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的情况。出现这种情况时，需引进人工变量先将原问题的解转化为可行解，再用单纯形法求解。例1-4：在美佳公司的例子中，若家电II每件需设备A、B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，试重新确定该公司最优生产计划。,2023/4/3,44,解 先将生产工时变化后的新家电II看作是一种新产品，生产量x2，仿上一节的步骤直接计算 和 并反映到最终单纯形表中。其中：,将其反映到最终单纯形表中得表如下。,2023/4/3,45,因x2已变换为x2，故用单纯形算法将x2替换出基变量中的x2，并在下一个表中不再保留x2，得表如下：,2023/4/3,46,上表中，原问题与对偶问题均非可行解，故先设法使原问题变为可行解。上表中第1行的约束可以写为：x3+4x4-24x5=-9两边同乘以(-1)，再加上人工变量x6得-x3-4x4+24x5+x6=9将上式替换上表第一行，得：,因对偶问题为非可行解，用单纯形法计算可得表如下：,2023/4/3,47,由上表可知，美佳公司的最优生产计划为每天生产11/4件家电I，15/8件新家电II。,2023/4/3,48,五、增加一个约束条件的分析,增加一个约束条件在实际问题中相当于增添一道工序。分析的方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。例1-5：仍以美佳公司为例，设家电I、II经调试后，还需经过一道环境实验工序。家电I每件需环境试验3h，家电II每件需2h，又环境实验工序每天生产能力为12h。试分析增加该工序后的美佳公司最优生产计划。,2023/4/3,49,解 先将原问题的最优解x1=7/2,x2=3/2代入环境实验工序的约束条件3x1+2x212，故原问题最优解不是本例的最优解。在实验工序的约束条件中加松弛变量得：3x1+2x2+x6=12 以x6为基变量，将上式反映到最终单纯形表中可得：,上表中x1、x2列不是单位向量，故需进行变换，得下表，下表中第行同原表第行，表中第行由以下初等变换得到：=-3*-2*。,2023/4/3,50,因上表中对偶问题为可行解，原问题为非可行解，故用对偶单纯形法迭代计算得下表。,由上表可知，添加环境试验工序后，美佳公司的最优生产计划为只生产4件家电I。,2023/4/3,51,作 业,2.1（1）2.11（1）2.16,