《运筹》教学课件-线性规划的模型

2006/08,-第1章线性规划-,-1-,线性规划的模型LinearProgramming,2006/08,-第1章线性规划-,-2-,1.1.2线性规划问题的一般数学模型,1.相关概念（1）决策变量：指模型中要求解的未知量，简称变量。,（2）目标函数：指模型中要达到的目标的数学表达式。,（3）约束条件：指模型中的变量取值所需要满足的一切限制条件。,此三项内容称为模型结构的三要素。,2006/08,-第1章线性规划-,-3-,2.线性规划模型的一般要求,（1）变量：取值为连续的、可控的量；（2）目标函数：线性表达式；（3）约束条件：线性的等式或者不等式。,2006/08,-第1章线性规划-,-4-,线性规划问题的一般形式,maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1,x2,xn0s.t.-subjectto,2006/08,-第1章线性规划-,-5-,2006/08,-第1章线性规划-,-6-,2006/08,-第1章线性规划-,-7-,2006/08,-第1章线性规划-,-8-,2006/08,-第1章线性规划-,-9-,线性规划问题的标准形式,2006/08,-第1章线性规划-,-10-,4.线性规划模型的标准形式,（1）变量：所有变量均xj0（2）目标函数：为取“max”形式（3）约束条件：全部约束方程均为“=”连接（4）约束右端项：bi0非标准形式情况有变量：xj0,或xj无约束目标函数：min约束条件：“”或“”约束右端项：bi0,2006/08,-第1章线性规划-,-11-,LP的标准化：,（1）变量：若xj0，令xj=-xj，xj0若xj无约束，则令xj=xjxj，xj0，xj0,x,z,z,zmin,z=-z,zmax,（3）约束方程：当“”时，引进松弛（slack）变量+xs；如x1+x23x1+x2+x3=3当“”时，引进剩余（surplus）变量-xs；如x1+2x24x1+2x2x4=4,（2）目标函数：若求minz，则令z=-z，等价于求max（z）即有minz=-max（-z）,（4）约束右端项：当bi0，则不等式两端同乘（-1）,2006/08,-第1章线性规划-,-12-,例：将下述LP模型标准化：,obj.Minz=2x1-x2+3x3st.x1+2x2+4x363x1-2x2+x3=42x1-x2-3x35x10,x2无符号限制,x30,解：设z=-z,x2=x2-x2,x20,x20,x3=-x3,x30，x40,x50,则有obj.Maxz=-2x1+(x2-x2)+3x3st.x1+2(x2-x2)-4x3+x4=63x1-2(x2-x2)-x3=42x1-(x2-x2)+3x3-x5=5x10,x20,x20,x30,x40,x50,2006/08,-第1章线性规划-,-13-,复习思考题：,1.什么是模型结构的三要素？2.什么是线性规划模型？能举出线性规划模型的例子吗？3.LP模型中目标函数系数、约束条件系数、约束右端项的含义指的是什么？通常以什么符号表示？4.LP模型的一般表