资源描述：
《运筹学考点ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性规划第二章线性规划本章考点建立线性规划问题的数学模型图解法及灵敏度分析将一般形式的线性规划问题转换成标准形式计算机输出结果的解释一般形式:目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn≤(=,≥)b1a21x1+a22x2+…+a2nxn≤(=,≥)b2……am1x1+am2x2+…+amnxn≤(=,≥)bmx1，x2，…，xn≥01.线性规划问题及其数学模型一般形式:简化：nMax(Min)z=∑cjxjj=1约束条件：n∑aijxj≤(=,≥)biJ=1xj≥0(j=
2、1,2,…,n)1.线性规划问题及其数学模型一般形式:向量式：Max(Min)z=CX约束条件：n∑Pjxj≤(=,≥)bJ=1X≥01.线性规划问题及其数学模型一般形式:矩阵和向量形式：Max(Min)z=CX约束条件：AX≤(=,≥)bX≥0A称为系数矩阵1.线性规划问题及其数学模型标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2……am1x1+am2x2+…+amnxn=bmx1，x2，…，xn≥01.线性规划问题及其数学模型可以看
3、出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+…+cnxn则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-…-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf＝-Maxz1.线性规划问题及其数学模型２、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2
4、+…+ainxn≤bi可以引进一个新的变量xs，使它等于约束右边与左边之差xs=bi–(ai1x1+ai2x2+…+ainxn)显然，xs也具有非负约束，即xs≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn+xs=biXs称为松弛变量。１.线性规划问题及其数学模型当约束条件为ai1x1+ai2x2+…+ainxn≥bi时，类似地令xs=(ai1x1+ai2x2+…+ainxn)-bi显然，xs也具有非负约束，即xs≥0，这时新的约束条件成为ai1x1+ai2x2+…+ainxn-xs=bixs称为剩余变量。如果原问题中有若干个非
5、等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量（剩余变量）。在实际问题中,松弛变量表示未被充分利用的资源数、剩余变量表示超出的资源数,均未转化为价值或利润,所以引进模型后,它们在目标函数中的系数均为0。１.线性规划问题及其数学模型３.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj’-xj”其中xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，４．右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<
6、0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi。１.线性规划问题及其数学模型例2.3：将以下线性规划问题转化为标准形式Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58x1,x3,x4≥01.线性规划问题及其数学模型Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-
7、2x3-3x4-x7=58x1,x2’,x2”,x3,x4,x5,x6,x7≥0１.线性规划问题及其数学模型２．线性规划的图解法线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：(1)分别取决策变量x1,x2为坐标向量建立直角坐标系。２．线性规划的图解法（2）图示约束条件，得到可行域。对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域(存在或不存在），若存在，其中的点表
8、示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。然后进行（3）否则该线性规划问题无可行解。２．线性规划的图解
