教案五线性规划的对偶问题

教案五线性规划的对偶问题教学内容第四节线性规划的对偶问题2.对偶单纯形法教学学时7学时教学目标1.理解对偶问题的基本概念教学过程一、复习巩固1.单纯形法的基本原理(见课件)2.单纯形解法(见课件)3.大M法(见课件)(1)对偶问题的基本概念(见课件)对偶现象每一个线性规划都伴随着另一个线性规划，两者有密切关系，互为对偶.其中一个问题称为原问题，另一个问题称为其对偶问题.两者间只要得到其中一个问题的解，那么也就得到了另一个问题的解.下面通过一个实例来解释对偶线性规划的概念.例2-12以例2-1为例，我们讨论了一个制药厂的生产计划的数学模型及其解法.现在假定该制药厂决定在计划期内不生产药品I、Ⅱ,而将生产设备的有效台时全部租给某公司，那么该公司应对设备A、B、C、D每小时付多少租金，才能使成本最小，而又能为制药厂所接受?从租用设备的公司的角度考虑，一是所付的租金越低越好；二是所付的租金总额能使制药厂接受，即租金应不低于制药厂自己生产该两种药品所得利润，否则，制药厂宁可自己生产，而不租给公司.设公司租用该制药厂A、B、C、D四种设备的租金(元/小时)分别为y,、y₂、y,和y₄.在考虑租用设备的定价时，能使该制药厂接受的条件是：公司租用该制药厂用以生产每千克药品I所需A、B、C、D四种设备的台时的租金不应少于200元，即2y₁+y₂+4y₃+0y₄≥200同样，公司租用该制药厂用以生产每千克药品Ⅱ所需A、B、C、D四种设备的台时的租金不应少于300元，即2y₁+2y₂+0y₃+4y₄≥300公司在考虑自身利益时，其目标是使付出的租金总额为最小，即MinW=12y₁+8y₂+16y₃+12y.于是，上面的问题可以用下列线性规划的数学模型表示：MinW=12y₁+8y₂+16y₃+12y₄s.t.若把制药厂利润最大的线性规划问题称为原问题，则想租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题的对偶问题(dualproblem);反之，若把租用A、B、C、D四种设备的公司的租金最小的线性规划问题称为原问题，则制药厂利润最大的线性规划问题称为原问题的对偶问题.影子价格一般地，我们称对偶问题的最优解为原问题约束条件的影子价格，即对偶问题的解y,称为第i种资源的影子价格.它并不是某种资源在市场上的价格，而是代表单位资源在最优利用的条件下所产生的经济效果.为了和市场价格相区别，我们才称它为影子价格.它在经济上是一个很有意义的数据，通过它我们可以知道，当增加某种资源时，可以使利润增长的大小.另外，影子价格还给出了是否应当购进某种资源以增加生产量，而获得更多利润的价格标准.(2)对称的对偶线性规划(见课件)如果一个线性规划具备下面两个条件，则称它具有对称形式：①所有的变量都是非负的；②所有的约束条件都是不等式，而且在目标函数是求极大值的情况，不等式具有小于和等于(≤)的符号，在目标函数是求极小值的情况，不等式具有大于和等于(≥)的符号.对称形式的原问题和对偶问题叫做对称的对偶线性规划.原问题和对偶问题在形式上的对比如果我们把线性规划称为原问题，则必同时存在另一线性规划问题，我们称为对偶问题：用简缩形式表示：原问题为对偶问题为原问题为MaxZ=CX对偶问题为MinW=Ybs.t.原问题与对偶问题之间的关系1)原问题是求目标函数的最大值，对偶问题是求目标函数的最小值.2)原问题约束条件的右端项变成对偶问题目标函数的系数.原问题目标函4)原问题约束条件的每一行正好对应于对偶问题的每一列，所以原问题中5)原问题中约束条件的每一列正好对应于对偶问题的每一行，所以原问题6)对偶问题的对偶规划正是原问题.例2-13设原问题为：MiW=2x,+5x试写出它的对偶问题.(3)非对称的对偶线性规划(见课件)对于我们经常遇到的非对称形式的线性规划，我们可首先将其化为等价的的对应关系，将其化为对偶问题.实际上，我们在考虑对称的对偶线性对称的对偶线性规划(dualofanonnormalLP)时，也可以按表2-13原问题与对偶问题之间的对应关系，直接进行变换，得到原问题表2-13原问题与对偶问题间的转换原问题(或对偶问题)对偶问题(或原问题)目标函数MinW约束条件数：m个第i个约束条件为“≤”对偶变量数：m个对偶变量y,≥0第i个约束条件为“≥”第i个约束条件为“=”第j个约束条件为“≥”第j个约束条件为“≤”第j个约束条件为“=”限定向量b限定向量b系数矩阵A?例2-14可按表2-13的原则，将原问题直接转化成对偶问题：MinW=20y₁+10y₂+5y₃(4)对偶问题的基本性质(见课件)1)对偶问题的对偶是原问题(对称性质).2)若x和γ分别是原问题和对偶问题的可行解，则CX≤γb(弱对偶性质).3)设x和γ分别是原问题和对偶问题的可行解，当两者目标函数值相等，即CX=γb时，X,γ分别是原问题和对偶问题的最优解(可行解是最优解的性质).4)若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等(对偶性质).5)若x和γ分别是原问题和对偶问题的可行解，则x和γ为原问题及对偶VX=0和γ=0其中，u=(ui,u₂,…,um)”,ui,u₂,…,un是原问题的松弛变量，γ=(v₁,Vz,…,Vn),vi,vz,…,V,是对偶问题的剩余变量(松弛互补性质).此性质在线性规划中有广泛应用.如从已知的原问题最优解(或对偶问题最优解)求取对偶问题最优解(或原问题最优解);验证原问题的可行解是否最优解等等.6)原问题的检验数对应于对偶问题的一个基本解.由对偶性质可知，在求解原问题的过程中，利用单纯形表每一次迭代所得例2-15设原问题为：已知其对偶问题的最优解为y=1.2,y,=0.2,=28,试利用对偶性质求该问题的最优解相应的目标函数最小值W由松弛互补性质可知，在最优条件下，vX=0u₁^y₁^=0,u₃`y,^=0,v,x₁¹=0,v,^x?⁴=0,v₃*x;¹=0,v₄*x₄'=0;这解方程得x;=x₄=4综上所得，原问题的最优解为x*=(0为z*=28.1)若原问题可行，但有无界解(或称无有限最优解),则对偶问题不可行；若对偶问题可行，但有无界解(或称无有限最优解),则原问题不可行；2)若原问题可行，而对偶问题不可行，则原问题有无界解(或称无有限最优解);若对偶问题可行，而原问题不可行，则对偶问题有无界解(或称无有限最优解).2.对偶单纯形法那么根据对偶问题的对称性，我们也可以这样来处理：保持对偶问题的解基本可行解.这样，也使原问题和对偶问题都达到了最优解.事实上，对偶单纯形法(dualsimplexmethod)并不是解对偶问题的单纯形法，而是应用对偶原理来求解原问题的最优解的一种方法.(1)对偶单纯形法的要点(见课件)例2-16用对偶单纯形法求解下列线性规划问题s.t.解此问题可用大M法去解，但用大M法求解很麻烦，现在用对偶单纯形法求解.先将原问题化为标准形式，为此引入剩余变量x,xs,令z=-W,得.t.然后将约束条件等式的两边都乘以(-1),得到MaxZ=-1600x₁-2500x₂-400x建立这个问题的初始单纯形表，见表2-14:表2-14对偶单纯形法求解例2-16(1)b00解为x=(000-4-3)’,它是一个不可行解.而全部检验数c,-z,≤0,的迭代是在保持检验数小于等于零的条件下，逐步使x,≥0,j=1,2,…,5.为了1)首先确定换出变量：选择具有负数的基本变量中绝对值最大的基本变量为换出变量.2)确定换入变量：用换出变量那一行具有负值的系数分别去除同列的检验则原问题无可行解.3)把换出变量的那一行除以枢元位置的系数，使枢元位置变为1.(2)表解形式的对偶单纯形法(见课件)按上述迭代的要点，对表2-14继续运算，见表2-15.表2-15对偶单纯形法求解例2-16(2)-1600-2500-40000b00θ-40040θ-400-2500X₂θ-16001-2500X₂2-5若对应两个约束条件的对偶变量分别为y,和y,,则对偶问题的最优解为y*=(20060000200),最优值=2600.(3)对偶单纯形法的优点及用途(见课件)1)初始解可以是非可行解，当检验数都是小于等于零时，就可以进行基变换，这样就避免了增加人工变量，使运算简化.再用对偶单纯形法求解，简化计算.在上述讨论线性规划问题时，假定a。,b,,c,都是精确的数据，然而在大多数实际问题中，这些系数往往是估计值和预测值，而且它们也随着某些条件的变化而变化.因此很自然会想到，当这些系数中的一个或几个发生变化时，已求得的规划问题的最优解会发生什么变化?如果最优解发生了变化，又怎样用最简单的方法找到新的最优解?这就是线性规划灵敏度分析(sensitivityanalysisofLP)的任务.(1)单纯形法的矩阵表达式(见课件)设有一线性规划问题，用矩阵表示为MaxZ=CX列向量，0为n×1列向量.现引入松弛变量化为标准型MaxZ=CX+0Xs,0有m+n个元素.如果我们把系数矩阵A分为两块，A=(B,N),B也称基矩阵(即原始系数于是线性规划问题可以写成MaxZ=CnX+CxXx+0X;在单纯形法的每次迭代中，是用行变换的方法将基矩阵变成单位矩阵.用矩阵方法，则将上述约束方程的两边乘以基矩阵B的逆矩阵B-',于是可得X=B~¹b-B-'NXx-B-'Xs将式(2-11)代入目标函数可得Z=C₄B-b-C₀B-'NXv-C₀或者z+(C₈B-¹N-Cx)Xx+C₄B¹Xs=C₈B-¹b(2-13)从式(2-9)可知，在单纯形表每次迭代后，每个变量的系数列向量是B的逆阵B'乘以该变量的原始列向量而得到的，右端常数的列向量是B的逆阵B-¹乘以右端常数的原始列向量而得到的.从式(2-10)可见，其松弛变量的系数矩阵正好是基矩阵的逆阵B-'.更一般地理解，在任一单纯形表中相应于初始基本例如第二章第三节的例2-8中，表2-4、表2-5、表2-6和表2-7给出了单纯形法的计算过程，其中表2-7为最优解单纯形表，其基本变量是x,x,,x。和x,.对应于表2-7的基矩阵对应于表2-7的b列向量是对应于表2-7的非基本变量的检验数是C、-C。B-'n,松弛变量的检验数(2)系数变化的灵敏度分析(见课件)系数变化的灵敏度分析是在决策变量和约束条件数目不变时，研究各种系化时，已得到的最优解保持不变，或者最优解的基本变量保持不变(但数值有所改变);二是如果某些系数的变化引起最优解的变化，如何用最简便的方法求出因为C,=c;-Z,(j=1,2,…,n)(式中c,是基本变量的成本或利润系数)新的检验数C':C'=c,+△c,-Z,=C,+△c 例2-17以例2-8的最终计算表(表2-7)为例.设基本变量x,在目标函b0X₃00040x₆14300+△c,x₂020+2△c;b′=B-(b+△b)=B~`b+B⁻¹△b=b'+B~¹△b≥0所以△b,在[-8,0]之间变动时(即b,的变化范围在[8,16]时),原来最优解,最优值z=1375,表2-17右端常数变化后的最优解见表2-17.bθ0x₃007-20x₆13X₂09-40如果△b,的变化超出了[-8,0]的范围，这时最优解的基本变量就发生变化.在这种情况下要用对偶单纯形法继续求出新的最优解则最终单纯形表变为表2-18.表2-18右端常数变化后的对偶单纯形法求解C₈bX₈0000X₆15X₂00Z=1425θ0240X₆4X₂122新的最优解x*=(420024)',最优值Z=1400.矩阵A中的系数改变对最优解的影响当对应于P,的变量x,为非基本变量的系数时，它的变化不会改变基矩阵B和它的逆阵B-',所以只需修改单纯形表中所对应x,的列就可以了.P;=B~¹P若极大化问题C;≤0,则得到的还是新问题的最优单纯形表，最优解和最优值不变，否则可用单纯形法求解.当对应于p,的变量x,为基本变量的系数时，它的变化会改变基矩阵B和它的逆阵B-¹,所以会影响到最终单纯形表的右端向量和非基本变量对应的列.下例2-19以例2-1为例，若计划生产的药品I的工艺结构有了改进，相应地生产单位药品I所需设备4、B、C、D的台时改为(3,2,5,2),它的利润也提高到每千克400元.试分析已求得的最优计划有何变化?解当x,的系数列向量变化后，原最终单纯形表(表2-7)中x,的系数列向原最终单纯形表变成表2-19:表2-19决策变量系数改变对最优解的影响(1)C₈bX₈0x₃00040x₆14X₂3-802由x,的系数列向量可知，到此尚未完成行变换，所以需继续使x,的系数列向量变成单位列向量，于是得到表2-20.表2-20决策变量系数改变对最优解的影响(2)bX0X₃000x₆1x₂0 =1520元.4.线性规划在卫生管理中的应用(1)放射科的业务安排(见课件)A医院估计今后放射科如果开展此3项业务，在现有放射科医务人员力量和病人需求的情况下，每月此3项业务的最多提供量为1800人次.平均每人次检查时间、每月机器实际可使用时间、平均每人次检查利润如下表2-2