对偶线性规划问题.ppt

第二章对偶线性规划问题,2-1线性规划的对偶理论例21生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,数学模型maxg=50 x1+30 x2s.t.4x1+3x2120(2.1)2x1+x250 x1,x20,如果我们换一个角度，考虑另外一种经营问题。假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？,假设y1,y2分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：mins=120y1+50y2目标函数中的系数120，50分别表示可供出租的木工和油漆工工时数。,该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：4y1+2y2503y1+y230y1,y20,得到另外一个数学模型：mins=120y1+50y2s.t.4y1+2y250(2.2)3y1+y230y1,y20,模型(2.1)和模型(2.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。,如果模型(2.1)称为原问题，则模型(2.2)称为对偶问题。任何线性规划问题都有对偶问题，而且都有相应的意义。,例2.2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000 x1+800 x2+900 x3+200 x4300050 x1+60 x2+20 x3+10 x455400 x1+200 x2+300 x3+500 x4800 x1，x2，x3，x40(2.3),该问题的对偶问题：maxg=3000y1+55y2+800y3s.t.1000y1+50y2+400y314800y1+60y2+200y36900y1+20y2+300y33200y1+10y2+500y32y1，y2，y30(2.4),该问题的对偶问题(2.4)经济意义可解释为：市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。,线性规划的对偶关系：（I）MaxS=Cxs.t.Axb（2.3）x0(II)Ming=ybs.t.yAC（2.4）y0（2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。,a11a12.a1nb1A=a21a22.a2nb=b2。am1am2.amnbm,c1x10y1c2x20y2Ct=X=0=yt=.xn0ym,例2-3：写出下列线性规划问题的对偶问题minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x322x1+2x2+4x43x1，x2，x3，x40,minS=12x1+8x2+16x3+12x4s.t.2x1+x2+4x32y12x1+2x2+4x43y2x1，x2，x3，x40,解：该问题的对偶问题：maxg=2y1+3y2s.t.2y1+2y212y1+2y284y1164y212y1，y20,例2-4：写出下列线性规划问题的对偶问题maxS=10 x1+x2+2x3s.t.X1+x2+2x310y14x1+2x2-x320y2x1，x2，x30,解：该问题的对偶问题：ming=10y1+20y2s.t.y1+4y210y1+2y212y1-y22y1，y20,例2-5：写出下列线性规划问题的对偶问题minS=x1+2x2+3x3s.t.2x1+3x2+5x323x1+x2+7x33x1，x2，x30,解：用（-1）乘以第二个约束方程两边minS=x1+2x2+3x3s.t.2x1+3x2+5x32y1-3x1-x2-7x3-3y2x1，x2，x30,该问题的对偶问题：maxg=2y1-3y2s.t.2y1-3y213y1-y225y1-7y23y1，y20,例2-6：写出下列线性规划问题的对偶问题minS=2x1+3x2-5x3s.t.x1+x2-x352x1+x3=4x1，x2，x30,解：将原问题的约束方程写成不等式约束形式：minS=2x1+3x2-5x3x1+x2-x35y12x1+x34y2-2x1-x3-4y2”x1，x2，x30,引入变量y1,y2，y2”写出对偶问题maxg=5y1+4y2-4y2”s.t.y1+2y2-2y2”2y13-y1+y2-y2”-5y1，y2，y2”0,令y2=y2-y2”得到maxg=5y1+4y2s.t.y1+2y22y13-y1+y2-5y10，y2无非负约束此类问题称为非对称型对偶问题。前面的问题称为对称型对偶问题。,若原规划中有等式约束,则与之对应的对偶变量无非负限制.根据对偶规划的对称性,若原规划某个变量无非负限制,则与之对应的对偶约束为等式约束.,例2-7：写出下列线性规划问题的对偶问题minS=3x1-2x2+x3s.t.x1+2x2=1y12x2-x3-2y22x1+x33y3x1-2x2+3x34y4x1，x20，x3无非负限制,minS=3x1-2x2+x3s.t.x1+2x2=1y1-2x2+x32y22x1+x33y3x1-2x2+3x34y4x1，x20，x3无非负限制,解:综合运用对偶原则得到maxg=y1+2y2+3y3+4y4s.t.y1+2y3+y432y1-2y2-2y4-2y2+y3+3y4=1y2,y3,y40，y1无非负约束,对偶问题的基本定理定理2.0:(对称性定理)对偶问题的对偶就是原问题.,对偶问题的基本定理定理2.1:(弱对偶定理)对于互为对偶问题(I)(II)中的任意的可行解x(0),y(0),都有cx(0)y(0)b,用非线性函数马鞍面说明定理的含义（鞍点）。但是线性规划是线性函数。,马鞍面z=x2/4-y2/6,鞍点,Y,Z,X,Z,Y,X,在Y=0的平面上鞍点是z=f(0,y)的极大值点,X,Y,Z,在X=0的平面上鞍点是z=f(0,y)的极小值点,对偶问题的基本定理推理一:对偶问题中,任意一个可行解,都产生了另一个问题的目标函数的界。推理二:若原问题和对偶问题都有可行解,则它们都有最优解。推理三:若互为对偶问题中任意一个有可行解,但无最优解,则另一个就无可行解。,对偶问题的基本定理定理2.2(最优准则)若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解.,对偶问题的基本定理定理2.3(对偶定理)若原问题有最优解,则对偶问题也有最优解,且最优值相等.,对偶问题的基本定理定理2.3(对偶定理)若原问题有最优解,则对偶问题也有最优解,且最优值相等。推理:对偶问题的最优解为原问题最优表中,相应的松驶变量检验数的相反数。,原问题与对偶问题解的对应关系,2-2对偶单纯形法原始单纯形法其基本思路：在换基迭代过程中，始终保持基变量值非负，逐步使检验数变成非正，最后求得最优解或判断无最优解。对偶单纯形法其基本思路：在换基迭代过程中，始终保持检验数非正，逐步使基变量值变成非负，最后求得最优解或判断无最优解。,例2-9：用对偶单纯形法解下列线性规划问题minS=x1+4x2+3x4s.t.x1+2x2-x3+x43-2x1-x2+4x3+x42x1，x2，x3，x40,解：此题可用人工变量方法求，但也可用对偶单纯形法。maxS=-x1-4x2-3x4s.t.-x1-2x2+x3-x4+x5=-32x1+x2-4x3-x4+x6=-2x1，x2，x3，x4，x5，x60,计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。,常数项是负数且最小，确定出基变量x5。,用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交叉元素为主元（-1）,主元运算：第一行乘（-1）,主元运算：第二行加上第一行（-2）,计算检验数,确定出基变量X6,确定进基变量X3，主元（-2）,主元运算：第二行乘（-1/2）,主元运算：第一行加第二行,计算检验数：全为非正。但此时常数b已全大于零，最优解=（7，0，4，0）最优值S=-7S=7,例2-10：用对偶单纯形法解下列线性规划问题minS=x1+2x2s.t.-x1+2x2-x31-x1-2x2+x36x1，x2，x30,解：将原问题化成maxS=-x1-2x2s.t.x1-2x2+x3+x4=-1x1+2x2-x3+x5=-6x1，x2，x3，x4，x50,常数项最小出基变量X5，按比值无法比较。,常数项次小出基变量X4，按比值X2为进基变量。主元（-2）,主元运算：第一行乘（-1/2）,主元运算：第二行加第一行（-2）,计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。,例2-11：某种农作物在生长过程中至少需要氮肥33公斤，磷肥24公斤钾肥42公斤。已知有甲、乙、丙、丁四种复合肥料的每公斤价格和含氮、磷、钾肥数量如下表。问应如何使用这些肥料，既能满足作物生长的需要，又能使施肥成本最低？,原始数据表,解：假设用甲、乙、丙、丁为X1、X2、X3、X4公斤。数学模型为：minS=4x1+15x2+10 x3+13x4s.t.0.03x1+0.3x2+0.15x4330.05x1+0.2x3+0.1x4240.14x1+0.07x424x1，x2，x3，x40,也可将模型化为：maxS=-4x1-15x2-10 x3-13x4-0.03x1-0.3x2-0.15x4+x5=-33-0.05x1-0.2x3-0.1x4+x6=-24-0.1