《线性规划问题 基础与提高讲解》由会员分享，可在线阅读，更多相关《线性规划问题 基础与提高讲解（93页珍藏版）》请在金锄头文库上搜索。
1、第 三 章,线 性 规 划,3.1 线性规划模型,例:某工厂拥有A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1 + 2 x2 65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1 + x2 40；,3.1 线性规划模
2、型,对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 75 ；另外，产品数不可能为负，即 x1 ,x2 0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：,3.1 线性规划模型,目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1+2x2 652x1+x2 403x2 75x1 ,x2 0,3.1 线性规划模型,这是一个典型的利润最大化
3、的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。,3.1 线性规划模型,一般形式 目标函数： Max(Min)z = c1x1 + c2x2 + + cnxn,约束条件： a11x1+a12x2+a1nxn( =, )b1 a21x1+a22x2+a2nxn( =, )b2 . am1x1+am2x2 +amnxn( =, )bmx1 ，x2 ， ，xn 0,3.1 线性规划模型,标准形式 目标函数： Ma
4、x z = c1x1 + c2x2 + + cnxn,约束条件： a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . am1x1 + am2x2 + + amnxn = bmx1 ，x2 ， ，xn 0,3.1 线性规划模型,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,3.1 线性规划模型,1.极小化目标函数的问题：设目标函数为Min f = c1x1 + c2x2 + + cnxn 则可以令z
5、-f ，该极小化问 题与下面的极大化问题有相同的最优 解，即Max z = -c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Min f - Max z,3.1 线性规划模型,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,3.1 线性规划模型,当
6、约束条件为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,3.1 线性规划模型,为了使约束由不等式成为等式而引进的变量s称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。,3.1 线性规划模型,例2.2：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3s. t. 2.3 x1 + 5.2 x2 -
7、6.1 x3 15.74.1 x1 + 3.3 x3 8.9x1 + x2 + x3 = 38x1 , x2 , x3 0,3.1 线性规划模型,解：首先,将目标函数转换成极大化： 令 z= -f = -3.6x1+5.2x2-1.8x3,其次考虑约束，有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.74.1x1+3.3x3-x5= 8.9x1+x2+x3= 38x1 ,x2 ,x3 ,x4 ,x5 0,3.1 线性规
8、划模型,3. 变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj = xj- xj” 其中xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。,3.1 线性规划模型,4.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 bi 0, 且 B-1pj0, 则 (LP) 无有界解 .,3.2 线性规划的单纯形法,表格单纯形法 1、原理及算法过程Max cTx (LP) s.t. Ax = bx0 其中,c , x Rnb RmA mn 矩阵，秩
9、（A）= m,3.2 线性规划的单纯形法 单纯形法原理及算法过程,算法过程 (考虑一般步, k = 0,1,2, ) 设 x(k) 为极点, 对应分解 A = B , N ，使xT = xBT, xNT , 这里 xB = B-1b0, xN =0，相应 cT = cBT, cNT 。那么，1）若 cNT- cBT B-1N0, 则 x(k) opt，停；2）否则，存在 cj- cBT B-1pj 0, a）若 B-1pj0, 则 (LP) 无有界解，停；b）若存在 (B-1pj)i 0, 取 = min(B-1b)i / (B-1pj)i | (B-1pj)i 0= (B-1b)r /(B-
10、1pj)r 0,3.2 线性规划的单纯形法 单纯形法原理及算法过程,(续)得到 x(k+1) = x(k) + d 是极点 其中, dT = dBT, dNT , 这里 jdB = -B-1pj , dN = (0, . , 1, ,0)T 有, cTx(k+1) = cTx(k) + cTd = cTx(k) + (cj - cBTB-1pj) cTx(k)所以，x(k+1) 比 x(k) 好重复这个过程，直到停机。,3.2 线性规划的单纯形法 表格单纯形法,2、单纯形表：设 x 为初始极点, 相应分解 A = B , N ,作变换，使前m+1列对应的m+1阶矩阵变为单位矩阵。相当于该表左乘
11、1 cBT -1 1 - cBT B-1 0 B 0 B-1,=,3.2 线性规划的单纯形法 表格单纯形法,得到： 检验数,为了计算方便，我们对规范形式建立如下单纯形表： （注：引入了m个松弛变量）,3.2 线性规划的单纯形法,表格单纯形法 考虑： bi 0 i = 1 , , mMax z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1a21 x1 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bmx1 ，x2 ， ，xn 0,3.2 线性规划的单纯形法,加入松弛变量：Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bmx1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0,
