软件对偶理论课件.ppt

1、例例1有两个煤厂A、B，每月分别进煤不少于60吨、100吨，它们担负供应三个居民区用煤任务，这三个居民区每月需用煤分别为45吨、75吨和40吨，A厂离这三个居民区分别是10公里、5公里、6公里，B厂离这三居民区分别为4公里、8公里、15公里。问这两煤厂如何分配供煤，才使运量最小？040754510060.231322122111232221131211xxxxxxxxxxxxxijtsMatlab: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=4

2、5;75;40;lb=zeros(6,1);x,fval=linprog(c,A,b,Aeq,beq,lb)原料原料种类种类含化学成份的百分比含化学成份的百分比价格价格(美元美元/加仑加仑)购买上限购买上限(加仑加仑)ABC10.900.070.030.70400020.700.200.100.50600030.100.700.200.65500040.600.300.100.855000例2：一家石油公司的炼油厂提供两种无铅汽油燃料：无铅高级汽油和无铅普通汽油。炼油厂购买四种不同的石油原料，每种石油原料的化学成份分析、价格及购买上限见下表：无铅高级汽油的售价是每加仑1.00美元，它应至少含有

3、60%的A成份，20%的B成份，而不能超过10%的C成份。无铅普通汽油的售价是每加仑0.90美元，它应至少50%的A成份，15%的B成份，而不能超过15%的C成份。公司预测：无铅高级汽油的销售量为6000加仑，无铅普通汽油的销售量为9000加仑。试确定每种汽油中各种原料的用量，使得公司获得最大的利润。12341234max6000 19000 0.9(0.70.50.650.850.70.50.650.85)zxxxxyyyy 60006.06.01.07.09.04321xxxx60002.03.07.02.007.04321xxxx60001.01.02.01.003.04321xxxx9

4、0005.06.01.07.09.04321yyyy900015.03.07.02.007.04321yyyy900015.01.02.01.003.04321yyyy400011 yx600022 yx500033 yx500044 yx0ix model:max=6000*1+9000*0.9-(0.7*x1+0.5*x2+0.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*x

5、2+0.2*x3+0.1*x4=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+y3=5000;x4+y4=5000;EndLingo:3.4 对偶理论产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg701202112070maxxxf0,03001032005436049.21212121xxxxxxxxts产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/k

6、g70120321300200360yyyminw70349321yyy1201054321yyy0,321yyy 它的它的就是一个就是一个，使使在平衡了劳动力、设备和原材料的直在平衡了劳动力、设备和原材料的直接成本接成本后，所确定的后，所确定的总价格最低）总价格最低）（用于生产第（用于生产第i种产品的资源转让收益不小于种产品的资源转让收益不小于生产该种产品时获得的利润）生产该种产品时获得的利润）321300200360yyyminw70349321yyy1201054321yyy0,321yyy2112070maxxxf0,03001032005436049.21212121xxxxxxxx

7、tsmin321300200360yyyw70349321yyy1201054321yyy0,321yyys.t.（1）定义：若原问题是）定义：若原问题是 0.maxxbAxtsxczT（L）0.minycyAtsybwTT（D）例：找出下面例：找出下面LP的对偶问题的对偶问题:0,10251543.2max21212121xxxxxxtsxxz0,124253.1015min21212121yyyyyyt syyw0.minycyAtsybwTT（D）0.maxxbAxtsxczT（P）原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标目标函数函数 max目

8、标目标函数函数 min约束约束条件数：条件数：m个个第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“=”对偶对偶变量变量数：数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量决策决策变量变量数：数：n个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量约束约束条件数：条件数：n第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“=”相同相同相反相反无限制32132132132132

9、1,0,032221.3225minxxxxxxxxxxxxtsxxxzmax约束约束条件数：条件数：n第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“=”决策决策变量变量数：数：n个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量对偶对偶变量变量数：数：m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量约束约束条件数：条件数：m个个第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为“”第第i个约束条件类型为个约束条件类型为

10、“=”目标目标函数函数 min目标目标函数函数 max对偶问题（或原问题）对偶问题（或原问题）原问题（或对偶问题）原问题（或对偶问题）321321yyyw32253212yyy3212yyy321yyy01y02y无限制3ys.t.jTjjjTjjiiTiiiTiTTcypnqjxcypqjxympibxaypibxatstsybwxcz,10,100,10,1.maxminmTnTTpppaaaA21210.maxxbAxtsxczT（L）0.minycyAtsybwTT （D）均有可行解，分别为均有可行解，分别为 和和 ，则恒有，则恒有xy证明思路：证明思路：由（由（L）bxA 由（由（D

11、）cyATybxcTT左乘byxAyTT左乘cxyAxTTTTyTx。（证明（证明:先先）由该定理可以得到什么附带结果？由该定理可以得到什么附带结果？问：问：min问题有问题有下界下界 maxmax问题有问题有上界上界 Lemma 1.如果原问题无界，则对偶问题不可行。如果原问题无界，则对偶问题不可行。Lemma 2.如果对偶问题无界，则原问题不可行。如果对偶问题无界，则原问题不可行。xybxcTTyxy结论结论xx yy 特别取特别取ybxcTT弱对偶弱对偶定定 理理ybxcTTybxcTT已已 知知ybxcTTybybTTxcxcTT对偶问题的解对偶问题的解利用原问题的最优单纯利用原问题的

12、最优单纯形表求解对偶问题的最形表求解对偶问题的最优解。优解。如何求如何求y*？Lemma3对于对称形式的原问题（对于对称形式的原问题（min）,若有最若有最优解，则在其最优单纯形表中，剩余变量的检验数的优解，则在其最优单纯形表中，剩余变量的检验数的负值即为对偶问题（负值即为对偶问题（max）的一个最优解。）的一个最优解。综上所述，一对对偶问题的关系，只能有下面三种情综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：况之一出现：.都有最优解都有最优解，分别设为，分别设为x*和和 y*，则必有，则必有cTx*=bTy*；.一个问题一个问题无界无界，则另一个问题，则另一个问题无可行解无可行解

13、；.两个两个都无可行解都无可行解。jTjjjTjjiiTiiiTiTTcypnqjxcypqjxympibxaypibxatstsybwxcz,10,100,10,1.maxmin0)(ibxTiayi0)(jxyTjpjcxynjjxyTjpjcvmiibxTiaiyuji,10)(,10)(证明思路证明思路00jivunjjmiivvuu1100uui00vvjybxcTTyx0vunjmiiijjjminjijijiyacxbxayvu1111)()(xcybTT例例5、已知、已知032 235 95243min5154321543254321xxxxxxxxxxxxxxxz试通过求对偶

14、问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为0,)5(923 )4(5 5)3(2 )2(4 )1(3 32max2121212121221yyyyyyyyyyyyyw用图解法求出：用图解法求出：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.

15、3)（1）（2）（3）（4）（5）又由于又由于y*10，y*2 0，原问题的约束必为等式，即，原问题的约束必为等式，即 322352152xxxxx 5251321xxxx化简为化简为此方程组为无穷多解此方程组为无穷多解 令令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。2355432xxxx32 54321xxxxx12121212121 11Example

16、 2.(,).7 7max(+2)s.t.32,-23,31,0.Txxxxxxxxxx x如果已用作图法求出下列问题的最优解为求其对偶问题的最优解。123123123123121231233541277min(2+3+)s.t.3-+1,+2-32,0.,0,3-+=1,+2-3=2.3=0.=.yyyy yyyyyy y yxxy yyyyyxyyy对偶问题为因为由互补松弛性条件，则有又将 代入原问题约束条件中，第 个是不等式，故有代入上式可得，故对偶问5477237(,0).Ty题的最优解为最优值123123123123123min 438.12 52420 2312 0,0,.(1)(2)(3)xxxs txxxxxxxxxxxxR考考虑虑线线性性规规划划问问题题：写写出出该该线线性性规规划划问问题题的的对对偶偶形形式式；求求出出对对偶偶形形式式的的最最优优解解和和最最优优值值；利利用用互互补补松松弛弛条条件件求求出出原原问问题题的的最最优优解解。