4线性规划对偶问题(清华4)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 对偶线性规划问题,2-1,线性规划的对偶理论,例,2,1,生产计划问题（资源利用问题）,胜利家具厂生产桌子和椅子两种家具。桌子售价,50,元,/,个，椅子销售价格,30/,个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工,4,小时，油漆工,2,小时。生产一个椅子需要木工,3,小时，油漆工,1,小时。该厂每个月可用木工工时为,120,小时，油漆工工时为,50,小时。问该厂如何组织生产才能使每月的销售收入最大？,数学模型,max,g= 50x,1,+ 30x,2,s.t,.,4x,1,+ 3x,2,120 (2.1),2x,1,+,x,2,50,x,1,x,2,0,如果我们换一个角度，考虑另外一种经营问题。 假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？,假设,y,1, y,2,分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为：,min,s = 120 y,1,+ 50 y,2,目标函数中的系数,120,，,50,分别表示可供出租的木工和油漆工工时数。,该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益：,4,y,1,+ 2y,2,50,3,y,1,+ y,2,30,y,1, y,2,0,得到另外一个数学模型：,min,s = 120 y,1,+ 50 y,2,s.t,. 4 y,1,+ 2y,2,50 (2.2),3,y,1,+ y,2,30,y,1, y,2,0,模型,(2.1),和模型,(2.2),既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型,(2.1),是站在家具厂经营者立场追求销售收入最大，模型,(2.2),是,则站在家具厂对手的立场追求所付的租金最少。,如果模型,(2.1),称为原问题，,则模型,(2.2),称为,对偶问题。,任何线性规划问题都有对偶问题，,而且都有相应的意义。,例,2 .2,营养配餐问题,假定一个成年人每天需要从食物中获得,3000,千卡的热量、,55,克蛋白质和,800,毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,解：,设,x,j,为第,j,种食品每天的购入量，则配餐问题的线性规划模型为：,min S=14x,1,+6x,2,+3x,3,+2x,4,s.t. 1000x,1,+800x,2,+900x,3,+200x,4,3000,50x,1,+,60x,2,+,20x,3,+ 10x,4,55,400x,1,+200x,2,+300x,3,+500x,4,800,x,1,，,x,2,，,x,3,，,x,4,0 (2.3,),该问题的对偶问题：,max g = 3000 y,1,+55y,2,+800y,3,s.t. 1000 y,1,+50y,2,+400y,3,14,800,y,1,+60y,2,+200y,3,6,900,y,1,+20y,2,+300y,3,3,200,y,1,+10y,2,+500y,3,2,y,1,，,y,2,，,y,3,0,(,2.4),该问题的对偶问题,(2.4),经济意义可解释为：市场上有一厂商生产三种可代替食品中的热量、蛋白质和钙的营养素，该厂商希望它的产品既有市场竞争力，又能带来最大利润，因此需要构造一个模型来研究定价问题。以上模型的变量为各营养素单位营养量的价格，目标函数反映厂商利润最大的目标，约束条件反映市场的竞争条件，即：用于购买与某种食品营养价值相同的营养素的价格应小于该食品的市场价格。,线性规划的对偶关系：,（,I,）,MaxS,=,C,x,s.t,.,Ax,b,(2.3,）,x,0,(II),Min,g = y b,s.t,.,y,A,C,(2.4,）,y,0,（,2.3)(2.4),称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。,a,11,a,12,. a,1n,b,1,A=,a,21,a,22,. a,2n,b,=,b,2,。 。,a,m1,a,m2,.,a,mn,b,m,c,1,x,1,0 y,1,c,2,x,2,0 y,2,C,t,= X= 0=,y,t,=, . .,c,n,x,n,0,y,m,例,2-3,：写出下列线性规划问题的对偶问题,min S=12x,1,+8x,2,+16x,3,+12x,4,s.t. 2x,1,+ x,2,+4x,3,2,2x,1,+2x,2,+,4x,4,3,x,1,，,x,2,，,x,3,，,x,4,0,min S=12x,1,+8x,2,+16x,3,+12x,4,s.t. 2x,1,+ x,2,+4x,3,2,y,1,2x,1,+2x,2,+ 4x,4,3,y,2,x,1,，,x,2,，,x,3,，,x,4,0,解：,该问题的对偶问题：,max,g = 2y,1,+,3y,2,s.t,.,2y,1,+ 2y,2,12,y,1,+ 2y,2,8,4,y,1,16,4y,2,12,y,1,，,y,2,0,例,2-4,：,写出下列线性规划问题的对偶问题,max S = 10x,1,+ x,2,+ 2x,3,s.t.,X,1,+ x,2,+ 2x,3,10,y,1,4x,1,+2x,2,- x,3,20,y,2,x,1,，,x,2,，,x,3,0,解：,该问题的对偶问题：,min,g = 10 y,1,+ 20 y,2,s.t,.,y,1,+ 4y,2,10,y,1,+ 2y,2,1,2,y,1,-,y,2,2,y,1,，,y,2,0,例,2-5,：,写出下列线性规划问题的对偶问题,min,S = x,1,+ 2x,2,+ 3x,3,s.t.,2x,1,+3x,2,+ 5x,3,2,3x,1,+ x,2,+ 7x,3,3,x,1,，,x,2,，,x,3,0,解：,用（,-1,）乘以第二个约束方程两边,min,S=x,1,+2x,2,+3x,3,s.t.,2x,1,+3x,2,+ 5x,3,2,y,1,-,3x,1,- x,2,- 7x,3,-3,y,2,x,1,，,x,2,，,x,3,0,该问题的对偶问题：,max,g = 2 y,1,- 3y,2,s.t,.,2y,1,-,3y,2,1,3y,1,-,y,2,2,5y,1,-,7y,2,3,y,1,，,y,2,0,例,2-6,：,写出下列线性规划问题的对偶问题,min,S = 2x,1,+ 3x,2,- 5x,3,s.t.,x,1,+ x,2,-,x,3,5,2x,1,+,x,3,=,4,x,1,，,x,2,，,x,3,0,解：,将原问题的约束方程写成不等式约束形式：,min,S = 2x,1,+ 3x,2,- 5x,3,x,1,+ x,2,-,x,3,5,y,1,2x,1,+,x,3,4,y,2,-,2x,1,-,x,3,-4,y,2,”,x,1,，,x,2,，,x,3,0,引入变量,y,1,y,2,，,y,2,”,写出对偶问题,max,g = 5 y,1,+ 4y,2,- 4y,2,”,s.t,.,y,1,+2y,2,- 2y,2,”,2,y,1,3,-,y,1,+,y,2,-,y,2,”,-5,y,1,，,y,2,，,y,2,”,0,令,y,2,= y,2,- y,2,”,得到,max,g = 5 y,1,+ 4y,2,s.t,.,y,1,+ 2y,2,2,y,1,3,-,y,1,+,y,2,-5,y,1,0,，,y,2,无非负约束,此类问题称为非对称型对偶问题。,前面的问题称为对称型对偶问题。,若原规划中有等式约束,则与之对应的对偶变量无非负限制,.,根据对偶规划的对称性,若原规划某个变量无非负限制,则与之对应的对偶约束为等式约束,.,例,2-7,：,写出下列线性规划问题的对偶问题,min,S = 3x,1,- 2x,2,+ x,3,s.t.,x,1,+2x,2,=,1,y,1,2x,2,- x,3,-2,y,2,2x,1,+,x,3,3,y,3,x,1,-,2x,2,+ 3x,3,4,y,4,x,1,，,x,2,0,，,x,3,无非负限制,min,S = 3x,1,- 2x,2,+ x,3,s.t.,x,1,+2x,2,=,1,y,1,-2x,2,+ x,3,2,y,2,2x,1,+ x,3,3,y,3,x,1,-,2x,2,+ 3x,3,4,y,4,x,1,，,x,2,0,，,x,3,无非负限制,解,:,综合运用对偶原则得到,max g = y,1,+2y,2,+3y,3,+4y,4,s.t,. y,1,+,2y,3,+ y,4,3,2y,1,-2y,2,-,2y,4,-2,y,2,+ y,3,+3y,4,=,1,y,2,y,3,y,4,0,，,y,1,无非负约束,对偶问题的基本定理,定理,2.0:(,对称性定理,),对偶问题的对偶就是原问题,.,对偶问题的基本定理,定理,2.1,:(,弱对偶定理,),对于互为对偶问题,(I)(II),中的任意的可行解,x,(0),y,(0),都有,c x,(0),=,y,(0),b,用非线性函数马鞍面说明定理的含义（鞍点）。但是线性规划是线性函数。,马鞍面,z=x,2,/4-y,2,/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,：,用对偶单纯形法解下列线性规划问题,min S = x,1,+ 4x,2,+ 3x,4,s.t. x,1,+2x,2,- x,3,+x,4,3,-2x,1,- x,2,+4x,3,+x,4,2,x,1,，,x,2,，,x,3,，,x,4,0,解：,此题可用人工变量方法求，但也可用,对偶单纯形法。,max,S = -x,1,- 4x,2,- 3x,4,s.t.,-,x,1,-2x,2,+ x,3,-x,4,+x,5,=,-3,2x,1,+ x,2,-4x,3,-x,4,+,x,6,= -2,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,0,计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。,常数项是负数且最小，确定出基变量,x,5,。,用出基变量,x,5,行的所有负数分别去除对应的检验数，最小值对应的为进基变量,x,1,，,交叉元素为主元,（,-1,）,主元运算：第一行乘（,-1,）,主元运算：第二行加上第一行（,-2,）,计算检验数,确定出基变量,X6,确定进基变量,X,3,，,主元,（,-2,）,主元运算：第二行乘（,-1/2,）,主元运算：第一行加第二行,计算检验数：全为非正。但此时常数,b,已全大于零，最优解,=,（,7,，,0,，,4,，,0,）,最优值,S = - 7 S=7,例,2-10,：,用对偶单纯形法解下列线性规划问题,min S = x,1,+ 2x,2,s.t. -x,1,+2x,2,- x,3,1,-x,1,-2x,2,+ x,3,6,x,1,，,x,2,，,x,3,0,解：,将原问题化成,max,S = -x,1,- 2x,2,s.t.,x,1,- 2x,2,+ x,3,+ x,4,=,-,1,x,1,+ 2x,2,-,x,3,+,x,5,=,-,6,x,1,，,x,2,，,x,3,，,x,4,，,x,5,0,常数项最小出基变量,X,5,，,按比值无法比较。,常数项次小出基变量,X,4,，,按比值,X,2,为进基变量。主元,（,-2,）,主元运算：第一行乘（,-1/2,）,主元运算：第二行加第一行（,-2,）,计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。,例,2-11,：,某种农作物在生长过程中至少需要氮肥,33,公斤，磷肥,24,公斤钾肥,42,公斤。已知有甲、乙、丙、丁四种复合肥料的每公斤价格和含氮、磷、钾肥数量如下表。问应如何使用这些肥料，既能满足作物生长的需要，又能使施肥成本最低？,原始数据表,解：,假设用甲、乙、丙、丁为,X,1,、,X,2,、,X,3,、,X,4,公斤。,数学模型为：,min S=4x,1,+15x,2,+ 10x,3,+13x,4,s.t.,0.03x,1,+0.3x,2,+,0.15x,4,33,0.05x,1,+,0.2x,3,+0.1x,4,24,0.14x,1,+,0.07x,4,24,x,1,，,x,2,，,x,3,，,x,4,0,也可将模型化为：,max S= - 4x,1,- 15x,2,- 10x,3,-13x,4,- 0.03x,1,-0.3x,2,-,0.15x,4,+x,5,=,-33,- 0.05x,1,-,0.2x,3,-0.1x,4,+,x,6,=,-24,- 0.14x,1,-,0.07x,4,+,x,7,= -24,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,，,x,7,0,初始可行基,B,1,=,（,P,5,，,P,6,，,P,7,）,第三行乘以,1/,（,-0.14,）,第一行加上第三行乘（,0.03,）,第二行加上第三行乘（,0.05,）,第一行除（,-0.3,） 计算检验数,第二行除以（,-0.2),最优解（,300,，,80,，,45,）,最优值,S=-2850 S=2850,最优解：甲肥,300,公斤，乙肥,80,公斤，丙肥,45,公斤，最少费用为,2850,元。,另外一个最优解：甲肥,480,公斤，乙肥,62,公斤，最少费用为,2850,元。,习题,P74,2.3,（,1,）（,2,）,2.4,2.6,2.7,