powerpoint presentation - 河南大学化学化工学院.ppt

文档介绍：线性规划LinearProgramming河南大学化学化工学院2011年6月本章目录线性规划问题的描述线性模型的建立线性规划解法图解法单纯形法使用Excel求解线性规划问题大规模线性规划问题举例1线性规划问题的描述1线性规划问题与标准型例题:(略)如何安排生产,可使利润最大?P1P2资源限制M131030TM24920TM39436T利润712千元/吨原料产品线性模型将上面的具体问题,转化为数学模型,设生产P1为x1吨,生产P2为x2吨,则有:目标函数:maxJ=7x1+12x2约束方程:3x1+10x2≤304x1+5x2≤209x1+4x2≤36x1≥0,x2≥0上述模型就是线性优化模型,求解这个优化模型就是线性规划要解决的问题。线性规划的标准型一般形式向标准型的转化1将最大转化为最小2将不等式约束化为等式约束:引入变量。对小于等于型,引入松弛变量yi,对大于等于型,引入剩余变量yi。3将自由变量转化为非负变量。4若bj≤0则化为:将上例问题转化为标准型:目标函数:maxJ=7x1+12x2约束方程:3x1+10x2≤304x1+5x2≤209x1+4x2≤36x1≥0,x2≥0目标函数:minJ=-7x1-12x2约束方程:3x1+10x2+x3=304x1+5x2+x4=209x1+4x2+x5=36x1≥0,x2≥0,x3≥0x4≥0,x5≥0例2:把线性规划模型化成标准型maxf=x1--x2≥-2x1-3x2≤2x1+x2≤4x1≥0,x2无限制解:对照标准型,对上面的线性规划模型进行第一轮初步转化:minf‘=-x1+-x2-x3=-2x1-3x2+x4=2x1+x2+x5=4x1≥0,x2=x6-x7最终标准化:minf‘=-x1+x6-.-2x1+x3+x6-x7=2x1+x4-3x6+3x7=2x1+x5+x6-x7=4xi≥0,i=1-7i≠2