[对偶单纯形法.docx

1.对偶问题模型 2.对偶例子，总结特点 3.对偶的相关性质定理 4.对偶单纯形法 对偶问题模型例：某化工厂利用R1、R2、R3 三种原料，生产Q1、Q2两种产品，生产每公斤产品所需的各单位原料、工厂所拥有的个资源最大量及每公斤产品销售利润如下表所示，问每天应生产多少公斤Q1、Q2才能使利润最大。原料-产品-利润表产品资源生产每公斤产品Q1生产每公斤产品Q2每天原料的最大用量（公斤）R1原料（公斤）3.010.0300R2原料（公斤）4.05.0200R3原料（公斤）9.04.0360利润（万元/公斤）0.71.2设每天生产Q1、Q2的产品量为x1，x2，可得到约束方程Max s=0.7 x1 +1.2 x23x1 + 10x23004x1 + 5x22009x1 + 4x2360x10, x20现在的问题是，如果另一个化工厂想全部购买该厂R1、R2、R3 三种原料，那么该厂在什么条件下出售这三种原料，才能使该厂在经济收入上不低于用等量的三种原料生产Q1、Q2产品获得的最大利润。设三种原料出售单价分别为u1, u2, u3, 可得到约束方程Min W= 300 u1 +200 u2 +360 u33 u1 +4 u2 +9 u3 0.710 u1 +5 u2 +9u3 1.2u10, u20, u30一半钱这问题成为L，后者为其对偶问题成为D比较两个线性规划模型，其特征有目标函数的要求上两者相反，s求max，w求min右端向量和目标函数的价值系数两者对调约束方程两者符号相反，s是“”，w是“”由s的约束方程书引入了同等数量的另一组非负变量u=( u1, u2, u3)T,且作为w的决策变量，约束方程数由m个变为n个对偶问题及其转化方对偶问题在理论和实践方面有着广泛的应用在某些情况下线性规划的对偶问题比原解问题更容易对偶变量对原问题的解提供了重要的经济意义在处理一般型初始模型时可以不引入人工变量而采用对偶单纯形法直接处理，减少计算量推证出若干重要性质和定理作为线性规划灵敏度分析的重要工具例：求下列线性规划的对偶问题： Max s= x1 +2 x2s.t.x1 -2x22x1 9-x1 + x25x10, x20解：其对偶问题为：min w=2y1+9y2+5y3 s.t. y1+y2-y31 -2y2+y32 y10, y20, y30需要注意的是，如果原问题的目标函数为求极小，其目标函数的系数需要乘-1变成求极大，如果某些约束为“”，则这些约束需乘-1，变成“”，才能产生相应的对偶问题。例：求下列线性规划的对偶问题： Min s= -4x1 +18 x2-10x3s.t. x1 +x2-x32-2x1+ x31x10, x20, x30解：化为标准问题： Max s= 4x1 -18 x2+10x3s.t.-x1 -x2+x3-2-2x1+ x31x10, x20, x30对偶问题为：Min w=-2y1+y2 s.t. -y1-2y24 -y1-18 -y1+y210 y10, y20若原问题的约束条件中含有等式约束条件，它的对偶问题的求法是将登时约束条件分解为两个不等式约束条件，然后按照上述标准求其对偶问题。例如：3 x1 +18 x2-10x3=6可转化为3 x1 +18 x2-10x36和-3 x1 -18 x2+10x3-6综上，原问题产生对偶问题特点如下：对于含n个变量的和m个约束的原问题，对偶问题将有m个变量和n个约束原问题中小于等于约束，在对偶问题中变为大于等于约束求极大化的原问题变成了求极小的对偶问题原问题中目标函数的系数为c1,c2,…,cn, 对偶问题中则为b1,b2,…,bm。原问题中的约束条件的右边项为b1,b2,…,bm，对偶问题中则为c1,c2,…,cn。原问题与对偶问题的变量均为非负。对偶问题的相关性质定理对偶定理M个不等式约束和n个变量约束的原问题：Max s=c1x1+c2x2+…+cnxns.t. a11x1+a12x2+…+a1nxnb1a21x1+a22x2+…+a2nxnb2…am1x1+am2x2+…+amnxnbmxj0,j=1,2,…,m引入m个松弛变量xn+1, xn+2, …, xn+mMax s=c1x1+c2x2+…+cnxns.t. a11x1+a12x2+…+a1nxn +xn+1=b1a21x1+a22x2+…+a2nxn+xn+2=b2…am1x1+am2x2+…+amnxn+xn+m=bmxj0,j=1,2,…,n+m同理，对偶问题n个剩余变量ym+1, ym+2, …, ym+n得对偶问题：Min w=b1y1+b2y2+…+bnyns.t. a11y1+a21y2+…+am1ym -ym+1=c1a12y1+a2