软件对偶理论课件.ppt

《软件对偶理论课件.ppt》由会员分享，可在线阅读，更多相关《软件对偶理论课件.ppt（34页珍藏版）》请在三一办公上搜索。

1、例1有两个煤厂A、B，每月分别进煤不少于60吨、100吨，它们担负供应三个居民区用煤任务，这三个居民区每月需用煤分别为45吨、75吨和40吨，A厂离这三个居民区分别是10公里、5公里、6公里，B厂离这三居民区分别为4公里、8公里、15公里。问这两煤厂如何分配供煤，才使运量最小？,Matlab:,c=10 5 6 4 8 15;A=-1-1-1 0 0 0;0 0 0-1-1-1;b=-60;-100;Aeq=1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1;beq=45;75;40;lb=zeros(6,1);x,fval=linprog(c,A,b,Aeq,beq,lb

2、),例2：一家石油公司的炼油厂提供两种无铅汽油燃料：无铅高级汽油和无铅普通汽油。炼油厂购买四种不同的石油原料，每种石油原料的化学成份分析、价格及购买上限见下表：无铅高级汽油的售价是每加仑1.00美元，它应至少含有60%的A成份，20%的B成份，而不能超过10%的C成份。无铅普通汽油的售价是每加仑0.90美元，它应至少50%的A成份，15%的B成份，而不能超过15%的C成份。公司预测：无铅高级汽油的销售量为6000加仑，无铅普通汽油的销售量为9000加仑。试确定每种汽油中各种原料的用量，使得公司获得最大的利润。,model:max=6000*1+9000*0.9-(0.7*x1+0.5*x2+0

3、.65*x3+0.85*x4+0.7*y1+0.5*y2+0.65*y3+0.85*y4);0.9*x1+0.7*x2+0.1*x3+0.6*x4=0.6*6000;0.07*x1+0.2*x2+0.7*x3+0.3*x4=0.2*6000;0.03*x1+0.1*x2+0.2*x3+0.1*x4=0.1*6000;,0.07*y1+0.2*y2+0.7*y3+0.3*y4=0.15*9000;0.9*y1+0.7*y2+0.1*y3+0.6*y4=0.5*9000;0.03*y1+0.1*y2+0.2*y3+0.1*y4=0.15*9000;,x1+y1=4000;x2+y2=6000;x3

4、+y3=5000;x4+y4=5000;,End,Lingo:,3.4 对偶理论,换个角度审视生产计划问题,如何安排生产计划，使得获利最多？,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,现从另一个角度提出问题。假定另有个工厂想利用该工厂的资源来生产产品。就要事先考虑至少付出多大代价才能使该工厂放弃生产自己的产品A、B，将现有的资源转而接受外来加工？,y1为每个劳动力的工时价格，y2为使用每台机器的价格，y3为消耗每单位原材料的价格。,它的对偶问题就是一个价格系统，使在平衡了劳动力、设备和原材料的直接成本后，所确定的价格系统最具有竞争力（总价格最

5、低）：,（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）,对偶变量的经济意义可以解释为对资源的单位定价；,（P）,（D）,c bb cA ATmax min,二、原问题和对偶问题的关系1、对称形式的对偶关系,（1）定义：若原问题是,（L）,（D）,则定义其对偶问题为,价值系数 右端项右端项 价值系数约束矩阵 约束矩 阵的转置max min,例：找出下面LP的对偶问题:,相同,相反,例 写出下列线性规划的对偶规划,（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）,原问题 对偶问题,原-对偶问题关系,对偶定理 对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的 一系

6、列定理。,定理1.弱对偶定理若一对对称形式的对偶线性规划,均有可行解，分别为 和，则恒有,证明思路：,由（L）,由（D）,该结论对任意形式的对偶问题同样成立。（证明:先转化为对称形式下的对偶问题，然后利用上面的定理）,由该定理可以得到什么附带结果？关于“界”的结果；,问：,min问题有下界推论1 max问题的任意一个可行解所对应的目标函数值是其对偶min问题最优目标函数值的一个下界。,max问题有上界推论2 min问题的任意一个可行解所对应的目标函数值是其对偶问题max最优目标函数值的一个上界。,Lemma 1.如果原问题无界，则对偶问题不可行。Lemma 2.如果对偶问题无界，则原问题不可行

7、。,推论1.最优性准则定理 若、分别为对称形式对偶线性规划的可行解，且,则，分别为原始问题和对偶问题的最优解。,证明思路,定理2.强对偶定理 若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相等。,对偶问题的解,利用原问题的最优单纯形表求解对偶问题的最优解。,如何求y*？,Lemma 3 对于对称形式的原问题（min）,若有最优解，则在其最优单纯形表中，剩余变量的检验数的负值即为对偶问题（max）的一个最优解。,原问题与对偶问题的关系；,综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：.都有最优解，分别设为x*和 y*，则必有cTx*=bTy*；.一个问题无界，则另

8、一个问题无可行解；.两个都无可行解。,一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。,原问题 对偶问题,原问题和它的对偶问题之间存在着一种松紧关系：一个问题中某个约束是“紧”的，另一个问题中对应的约束就是“松”的。,最终的平衡表达式，就是x和y分别是原始和对偶最优解的充要条件，即互补松紧性条件。,定理3（互补松弛定理）：原问题及其对偶问题的可行解 和 是最优解的充要条件是,证明思路,定义,推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束(严格不等式约束)，则它的对偶约束一定是其对偶问题最优解的紧

9、约束(严格等式约束)。,例5、已知,试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,用图解法求出：y*=（1,3），w=11。将y*1=1，y*2=3 代入对偶约束条件，（1）（2）（5）式为紧约束(=)，（3）（4）为松约束。令原问题的最优解为x*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0.,(1.3),（1）,（2）,（3）,（4）,（5）,又由于y*10，y*2 0，原问题的约束必为等式，即,化简为,此方程组为无穷多解,令x5=0,得到x1=1，x2=2 即x*1=（1,2,0,0,0）为原问题的一个最优解，z=11。再令 x5=2/3，得到x1=5/3，x2=0 即x*2（5/3,0,0,0,2/3）也是原问题的一个最优解，z=11。,作业,