第3章 节 线性规划 筹学与最优化方法－课件.pptVIP

第 三 章;3.1 线性规划模型; 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 ≤ 40；; 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 ≤75 ；另外，产品数不可能为负，即 x1 ,x2 ≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：;目标函数 Max z =1500x1+2500x2? 约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0? ;标准形式 目标函数： Max z = c1x1 + c2x2 + … + cnxn ; 可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式: ; 1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn 则可以令z ＝ -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z; 2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi; 当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时，类似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi ; 为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。 ?; 例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? ;其次考虑约束，有2个不等式约束，引进松弛变量x4，x5 ≥0。 于是，我们可以得到以下标准形式的线性规划问题： 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; 3. 变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令 xj = xj’- xj” 其中 xj’≥0，xj”≥0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。; 4.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得到： -ai1 x1-ai2 x2- … -ain