第二章 线性规划及单纯形法PPT课件

1、.,1,运筹学OPERATIONAL RESEARCH,2,.,第一章 线性规划及单纯形法,3,.,第四节 单纯形法计算步骤,第二节 图解法,第三节 单纯形法原理,第一节 线性规划问题及其数学模型,第五节 单纯形法的进一步讨论,第六节 数据包络分析,第七节 其他应用例子,4,.,第一节 线性规划问题及其数学模型,一、问题的提出 二、线性规划问题的与模型 三、线性规划的数学模型 四、线性规划模型的应用 五、线性规划问题的标准形式,5,.,一、问题提出 例1生产计划问题,两种家电各生产多少, 可获最大利润?,6,.,5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2 0,max

2、 Z= 2x1 +x2,解:设两种家电产量分别为变量x1 ， x2,7,.,5x2 15 3、约束条件 6x1 + 2x2 24 x1 + x2 5 x1，x2 0,2、目标函数max Z= 2x1 +x2,LP问题的三要素 1、决策变量x1 ， x2,8,.,例2,9,.,例2,解：设 表示捷运公司在第i (i=1,2,3,4)月初签订的租期为j (j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,.,10,15,10,20,12,.,11,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,12,.,二、线性规划模型特点,决策变量：向量(x1 xn)T 决策人要考虑和控

3、制的因素非负 约束条件：线性等式或不等式 目标函数：Z=(x1 xn) 线性式，求Z极大或极小,13,.,（一）一般式,Max(min)Z=C1X1+ C2X2+CnXn,14,.,15,.,（二）隐含的假设,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值,16,.,线性规划的标准化 一般形式 目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + +

4、 a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 标准形式 目标函数： Max z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0，bi 0,三、线性规划问题的标准形式,17,.,可以看出，线性

5、规划的标准形式有如下四个特 点： 目标最大化； 约束为等式； 决策变量均非负； 右端项非负。 对于各种非标准形式的线性规划问题，我们总可 以通过以下变换，将其转化为标准形式:,三、线性规划问题的标准形式,18,.,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn (可以)令 z -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f - Max z,三、线性规划问题的标准形式,

6、19,.,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右边与左 边之差 s=bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,三、线性规划问题的标准形式,20,.,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约 束条件成为 ai1 x1

7、+ai2 x2+ +ain xn-s = bi,三、线性规划问题的标准形式,21,.,为了使约束由不等式成为等式而引进的变量s,当 不等式为“小于等于”时称为“松弛变量”；当不等式 为“大于等于”时称为“剩余变量”。如果原问题中有 若干个非等式约束，则将其转化为标准形式时，必须 对各个约束引进不同的松弛变量。,3.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2 x2- -ain xn = -bi。,三、线性规划问题的标准形式,22,.,例：将以下线性规划问题转化为标准形式 Mi

8、n f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 6 2 x1 + x3 8 x1 + x2 + x3 = -9 x1 , x2 , x3 0 解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进变量x4，x5 0。 第三个约束条件的右端值为负，在等式两边同时乘-1。,三、线性规划问题的标准形式,23,.,通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8

9、 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 0 * 变量无符号限制的问题*： 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号 取决于xj和xj”的大小。,三、线性规划问题的标准形式,.,24,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,.,25,课堂练习,某蓄场每日要为

10、每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5 x1 +0.1x210 0.2x1 +0.3x2 5 0.3x1 +0.4x2 8 0.2x2 7 x1 , x20,s.t.,Min Z=300 x1 +200 x2,.,26,第二节 图解法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,.,27,第二节 图解法,一、图解法的目的和步骤,.,28,5x2 15 6x1 + 2

11、x2 24 x1 + x2 5 x1，x2 0,max Z= 2x1 +x2,例1模型的图解法,第二节 图解法,.,29,第二节 图解法,例2.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E),.,30,第二节 图解法,.,31,第二节 图解法,目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D

12、，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,.,32,第二节 图解法,例2.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500,.,33,第二节 图解法,最优解： x1 = 0， x2 = 1 最优目标值 z = 3,课堂练习 图解法求解线性规划,.,34,第二节 图解法,注：出现（3）、（4）情况时，建模有问题,二、图解法的求解结果分类,

13、.,35,第二节 图解法,三、图解法的几点启示,从图解法中我们了解到以下事实： 若LP问题的可行域存在，则可行域一定是凸集。 若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。,思路：最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。） 最优解在可行域的极点中找。 极点是有限个，若两个极点都是最优解，则两个极点所连线段上的所有点均是最优解）,定义：LP问题的可行域的极点（顶点）称为基本可行解。,.,36,第三节 单纯形法,凸集,凸集：在点集中任取两点，则其连线仍在其中。,即没有凹入的部分；没有空洞。,在凸集中，点A，B，C，D

14、称为极点（或顶点）。,A,B,C,D,37,.,第四节 单纯形法,38,.,38,第四节 单纯形法,单纯形法的基本思路：根据线性规划问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，线性规划问题就得到了最优解。,(1) 确定初始基可行解,(2) 最优性检验和解的判别,(3) 由一个基可行解另一个基可行解。,39,.,39,第四节 单纯形法,理论基础,40,.,40,第四节 单纯形法,单纯形法的步骤及解法,41,.,(1) 确定初始基可行解,(2) 最优性检验和解的判别,(3) 由一个基可行解另一个基可行解。,一、单纯形法的基本思路,第

15、四节 单纯形法,42,.,第四节 单纯形法,标准化模型， 确定初始基可行解,43,.,43,单纯形表,X1 X2 Xm Xm+1 Xm+k Xn CB XB b C1 C2 Cm Cm+1 Cm+k Cn C1 X1 b1 1 0 0 a1m+1 a1m+k a1n C2 X2 b2 0 1 0 a2m+1 a2m+k a2n Cr Xr br 0 0 0 arm+1 arm+k arn Cm Xm bm 0 0 1 amm+1 amm+k ann,z 0 0 0 m+1 m+k n,44,.,44,例1,第四节 单纯形法,5x2 15 6x1 + 2x2 24 x1 + x2 5 x1，x2

16、 0,max Z= 2x1 +x2,45,.,45,第一步：标准化,第四节 单纯形法,5x2+x3 = 15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 x1，x2 ，x3 ，x4，x5 0,max Z= 2x1 +x2 +0 x3 +0 x4 +0 x5,46,.,46,第二步：根据增广矩阵找一个初始基可行解,第四节 单纯形法,47,.,47,第三步：列出初始单纯形表,第四节 单纯形法,48,.,48,第四步：判断是否最优，否则找出下一个基可行解，并写出新单纯形表,第四节 单纯形法,49,.,49,第四步：判断是否最优，否则找出下一个基可行解，并写出新单纯形表,第四

17、节 单纯形法,50,.,50,第五步：再写出新单纯形表,第四节 单纯形法,51,.,51,习题,第四节 单纯形法,52,.,52,习题,第四节 单纯形法,53,.,53,习题,第四节 单纯形法,54,.,54,习题,第四节 单纯形法,55,.,55,习题,第四节 单纯形法,56,.,56,习题,第四节 单纯形法,57,.,57,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,没有初始基可行解时怎么办？ 借助人工变量求初始的基本可行解,58,.,58,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,59,.,59,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,60,.,

18、60,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,61,.,61,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,62,.,62,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,63,.,63,一、人工变量法（大M法）,第五节 单纯形法的进一步讨论,64,.,64,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,65,.,65,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,66,.,66,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,67,.,67,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,68,.,68,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,69,.,69,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,70,.,70,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,71,.,71,二、两阶段法（大M法）,第五节 单纯形法的进一步讨论,72,.,72,三、关