《北京理工大学运筹学 吴祈宗 第2章》由会员分享，可在线阅读，更多相关《北京理工大学运筹学 吴祈宗 第2章（135页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 线性规划建模及单纯形法,本章内容重点,线性规划模型与解的主要概念 线性规划的单纯形法，线性规划多解分析 线性规划应用建模,2,1.线性规划的概念,例2.1:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,3,问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2
2、 65； 对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 40；,1.线性规划的概念,4,对设备C ：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75 ；另外，产品数不可能为负，即 x1 ,x2 0。 同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润： z = 1500x1 + 2500x2 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,1.线性规划的概念,5,目标函数 Max z =1500x1+2
3、500x2 约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0,1.线性规划的概念,6,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数 z 达到最大的x1 ,x2 的取值。,1.线性规划的概念,7,一般形式 目标函数： Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22
4、x2+a2nxn( =, )b2 . . . am1x1+am2x2 +amnxn( =, )bm x1 ，x2 ， ，xn 0,1.线性规划的概念,8,标准形式 目标函数： Max z = c1x1 + c2x2 + + cnxn,约束条件： A11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,1.线性规划的概念,9,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形
5、式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,1.线性规划的概念,10,1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + + cnxn 则可以令z -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f - Max z,1.线性规划的概念,11,2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的变量s ，使它等于约束右
6、边与左边之差 s =bi(ai1 x1 + ai2 x2 + + ain xn ) 显然，s 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,1.线性规划的概念,12,当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi,1.线性规划的概念,13,为了使约束由不等式成为等式而引进的变量 s 称为“松弛变量”。如果原问题中有若干个非等
7、式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,1.线性规划的概念,14,例2.2：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0,1.线性规划的概念,解：首先,将目标函数转换成极大化： 令 z= -f = -3.6x1+5.2x2-1.8x3,15,其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 0。 于是，我们可以得到以下标准形式的线性
8、规划问题： Max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s.t. 2.3x1+5.2x2-6.1x3+x4= 15.7 4.1x1+3.3x3-x5= 8.9 x1+x2+x3= 38 x1 ,x2 ,x3 ,x4 ,x5 0,1.线性规划的概念,16,3. 变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj- xj” 其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,1.线性规划的概念,17,4.右端项有负值的问题： 在标准形式中，要
9、求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到： -ai1 x1-ai2 x2- -ain xn = -bi,1.线性规划的概念,18,例2.3：将以下线性规划问题转化为标准形式 Min f= -3 x1 + 5 x2 + 8 x3 - 7 x4 s.t. 2 x1 - 3 x2 + 5 x3 + 6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1 , x3 , x4 0,1.线性规划的概念,19,解：首先，将目标函数转换成极大化： 令 z = -f = 3x15
10、x28x3+7x4 ； 其次考虑约束，有3个不等式约束，引进松弛变量x5 ,x6 ,x7 0 ； 由于x2无非负限制，可令x2=x2-x2”,其中 x20，x2”0 ； 由于第3个约束右端项系数为-58，于是把该式两端乘以-1 。 于是，我们可以得到以下标准形式的线性规划问题：,1.线性规划的概念,20,Max z = 3x15x2+5x2”8x3 +7x4 s.t. 2x13x2+3x2”+5x3+6x4+x5= 28 4x1+2x2-2x2”+3x3-9x4-x6= 39 -6x2+6x2”-2x3-3x4-x7 = 58 x1 ,x2,x2”,x3 ,x4 ,x5 ,x6 ,x7 0,1
11、.线性规划的概念,21,2.线性规划的图解法,线性规划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下：,22,2.线性规划的图解法,(1)建立直角坐标系： 分别取决策变量x1 ,x2 为坐标向量。,23,2.线性规划的图解法,（2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。,24,2.
12、线性规划的图解法,（3）绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。,25,2.线性规划的图解法,结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。,26,2.线性规划的图解法,例2.4:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中
13、需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,27,2.线性规划的图解法,问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。 解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据前面分析，可以建立如下的线性规划模型： Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0 (D, E),28,2.线性规划的图解法 例题作图（1）,按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系；,29,2.线性规划的图
14、解法,（2）对每个约束（包括非负约束）条件作出直线（A、B、C、D、E），并通过判断确定不等式所决定的半平面。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示。,30,2.线性规划的图解法 例题作图（2）,第2步图示(1) 分别作出各约束半平面,2x1+ x2 40,3x2 75,x1 0,X2 0,3x1+ 2x2 65,31,2.线性规划的图解法 例题作图（3）,第2步图示(2) 各约束半平面的交可行域,32,2.线性规划的图解法,（3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使
15、其达到既与可行域有交点又不可能使值再增加的位置，得到交点 (5,25)T ，即最优解。此目标函数的值为70000。,2.线性规划的图解法 例题作图（4）,第3步图示 作出目标函数等值线,函数值增大,2.线性规划的图解法 例题作图（5）,第3步图示(2) 求出最优解,35,2.线性规划的图解法,根据上面的过程 我们得到这个线性规划的 最优解 x1=5、x2=25， 最优值 z = 70000 即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。,36,2.线性规划的图解法,线性规划的解有如下几种情况： 1、存在有限最优解： 唯一最优解；无穷多个最优解 2、无有限最优解（无界解） 3、无可行解（可行域空）,37,2.线性规划的图解法,例2.5：在例2.4的线性规划模型中，如果目标函数变为： Max z = 1500 x1 + 1000 x2 那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点 (5,25)T到点 (15,10)T 线段上的所有点，最优值为32500。如下图所示：,38,2.线性规划的图解法,无穷多解的情况,(15, 10)T,39,2.线性规划的图解法,例2.6：在例2.4的线性规划模型中,如果约束条件（A）、（C）变为： 3 x1 + 2 x2 65 (A） 3 x2 75 (
