环境系统分析：第六章 线性规划基础

1、第六章第六章 线性规划基础线性规划基础-环境系统污染控制规划的数学基础6.1 6.1 线性规划概述线性规划概述 线性规划是数学规划与运筹学的一个分支，线性规划是数学规划与运筹学的一个分支，是运筹学中最重要的一种数学方法。主要研是运筹学中最重要的一种数学方法。主要研究解决有限资源的最佳分配问题，即如何对究解决有限资源的最佳分配问题，即如何对有限的资源作出最佳方式的调配和最有利的有限的资源作出最佳方式的调配和最有利的使用，以便最充分地发挥资源的效能去获取使用，以便最充分地发挥资源的效能去获取最佳经济效益。最佳经济效益。 这种数学规划的方法，如果用数学语言表达，这种数学规划的方法，如果用数学语言表达

2、，就是在一定的约束条件下，寻找目标函数的就是在一定的约束条件下，寻找目标函数的极值问题。所谓线性规划，是指约束条件为极值问题。所谓线性规划，是指约束条件为线性等式或不等式，且目标函数也是线性函线性等式或不等式，且目标函数也是线性函数数。 生产调度问题生产调度问题1. 线性规划问题的提出线性规划问题的提出一、线性规划及其数学模型一、线性规划及其数学模型 某企业生产甲、乙两种产品，分别用某企业生产甲、乙两种产品，分别用A A、B B、C 3C 3种不同的原料，每生产种不同的原料，每生产1 1个单位的甲，需用个单位的甲，需用1 1个单位的个单位的A A、1 1个单位的个单位的B B、0 0个单位的个

3、单位的C C，利润为，利润为3 3千元；每生产千元；每生产1 1个单位的乙，需用个单位的乙，需用1 1个单位的个单位的A A、2 2个单位的个单位的B B、1 1个单位的个单位的C C，利润为，利润为4 4千元；现有千元；现有6 6个单位的个单位的A A、8 8个单位的个单位的B B、3 3个单位的个单位的C C，问企业，问企业如何安排生产，可使利润最大。如何安排生产，可使利润最大。产品产品 甲甲乙乙x1x2原料原料ABC利润利润11031214原料原料限制限制6832. 建模的步骤建模的步骤(1)明确问题的经济背景明确问题的经济背景(2)设定决策变量设定决策变量(3)明确目标明确目标-给出目

4、标函数给出目标函数(4)明确问题的所有限制明确问题的所有限制-给出约束条件给出约束条件Z = 3x1 + 4x2x1 + x2 6x1 + 2x2 8x2 3x10, x2 0 每天总利润：每天总利润：Z = 3xZ = 3x1 1 + 4x+ 4x2 2 变量变量 x x1 1 和和x x2 2 必须满足三个条件：必须满足三个条件： x x1 1 + x + x2 2 6 6 x x1 1 + 2x + 2x2 2 8 8 x x2 2 3 3 非负性约束：非负性约束：x x1 10, 0, x x2 2 00目标函数目标函数决策变量决策变量函函数数约约束束约束条件约束条件Max Z = 3

5、xMax Z = 3x1 1 + 4x+ 4x2 2 x x1 1 +x +x2 2 6 6 x1 +2x x1 +2x2 2 8 8 x x2 2 3 3 x x1 10, 0, x x2 2 00数学模型数学模型s.t.线性规划的数学表达线性规划的数学表达即求一组变量即求一组变量x x1 1 , x, x2 2 , x, xn n , ,在满足约束条件：在满足约束条件： a11x1 + a12x2 + +a1nxnb1 a21x1 + a22x2 + +a2nxnb2 am1x1 + am2x2 + +amnxnbm x1 , x2 , , xn 0 的情况下，使目标函数：的情况下，使目标

6、函数：f=cf=c1 1x x1 1+c+c2 2x x2 2+ +c+ +cn nx xn n 达到最大值或最小值。达到最大值或最小值。 Max / Min F=CX AXB 或或 AXB X0 或或 X0 或或 X自由自由其中：其中：C=(c1,c2,cn) B=(b1,b2,bm) X=(x1,x2, ,xn) A=aij（i=1,2, ,m；j=1,2, ,n ） 一般来说，满足约束条件的变量一般来说，满足约束条件的变量X=(x1,x2,xn)T有无穷多个解，求解有无穷多个解，求解LPLP问问题的目的就是从中找出一个能满足目标题的目的就是从中找出一个能满足目标函数最大或最小的解，作为该

7、函数最大或最小的解，作为该LPLP问题的问题的最终决策。最终决策。 决策变量、目标函数、约束条件是决策变量、目标函数、约束条件是LPLP模模型的三要素，其中后两者都是关于前者型的三要素，其中后两者都是关于前者的线性表达式；而的线性表达式；而LPLP模型就是由最优化模型就是由最优化的目标函数和约束条件这两部分构成的。的目标函数和约束条件这两部分构成的。二、线性规划的图解法 线性规划的图解法，就是借助几何图形来线性规划的图解法，就是借助几何图形来求解线性规划问题的一种方法。求解线性规划问题的一种方法。 图解法的基本步骤：图解法的基本步骤：1.1.可行域的确定可行域的确定 LPLP模型所有约束条件共

8、同构成的图形，称模型所有约束条件共同构成的图形，称为可行域图形。为可行域图形。2.2.目标函数的等值线和最优点的确定目标函数的等值线和最优点的确定F(0,6)x1+x2=6X1X2OB(4,2)C(2,3)E(8,0)G(0,6)Z=20Z=3x1+4x2A(6,0)x1+2x2=8x2=3D(0,3) 可以看到：当沿法线方向平行移动直线可以看到：当沿法线方向平行移动直线Z=Z=3x1+4x2至至B点时，点时，Z Z值在可行域值在可行域R R上就达到上就达到了最大值，从而确定了最大值，从而确定B点即为该点即为该LPLP问题的问题的最最优点。优点。 最优点的坐标值为最优点的坐标值为最优解最优解。

9、记为。记为X*=(x1*,x2*)T,X* *对应的目标函数值称为对应的目标函数值称为最优最优值，记为值，记为Z Z* *。 该实例的最优解：该实例的最优解：X X* *=(4,2)=(4,2)T T,Z,Z* *=20 =20 说明说明最优生产方案是：生产甲产品最优生产方案是：生产甲产品4 4件，乙产品件，乙产品2 2件，可获得最大利润件，可获得最大利润2020千元。千元。 LP问题几种可能的结果：问题几种可能的结果：唯一解；唯一解；多多重解；重解；无界解；无界解；无可行解。无可行解。 唯一解：只有一个最优点唯一解：只有一个最优点 多重解：有些多重解：有些LP问题最优解可能不唯一，问题最优解

10、可能不唯一，如如:前例中目标函数改为：前例中目标函数改为：max Z=x1+2x2 则目标函数等值线与约束条件则目标函数等值线与约束条件x1+2x28的的边界线平行。当将等值线沿法线方向平移边界线平行。当将等值线沿法线方向平移到到B点时，就与点时，就与R的边界线的边界线BC段重合。这表段重合。这表明明BC上的每一点都使目标函数值取得同样上的每一点都使目标函数值取得同样的最大值。这时出现多重解的情形。的最大值。这时出现多重解的情形。 无界解：无界解：Max Z = 3xMax Z = 3x1 1 + 2x+ 2x2 2 -2x -2x1 1 + x + x2 2 2 2 x x1 1 - 3x-

11、 3x2 2 3 3 x x1 10, 0, x x2 2 00s.t.x1x2 无可行解：有些无可行解：有些LP问题可能不存在可行点，问题可能不存在可行点，也就是说由约束条件得到的可行域也就是说由约束条件得到的可行域R为空集，为空集，即即R=。这时问题无可行解，也就无最优。这时问题无可行解，也就无最优解了，简称无解。解了，简称无解。 LP问题的可行域一般是凸多边形，而且若问题的可行域一般是凸多边形，而且若最优解存在，则一定在可行域的某个顶点最优解存在，则一定在可行域的某个顶点上得到；若在两个顶点同时得到最优解，上得到；若在两个顶点同时得到最优解，则这两个顶点连线上的每一点都是最优解，则这两个

12、顶点连线上的每一点都是最优解，且最优值相等；若可行域无界，则可能发且最优值相等；若可行域无界，则可能发生最优解无界的情况，此时无最优解。若生最优解无界的情况，此时无最优解。若可行域为空集，则问题无可行解。可行域为空集，则问题无可行解。三、线性规划的标准形式 LP问题的各种不问题的各种不同形式可以相互同形式可以相互转化，只需给出转化，只需给出其中一种形式的其中一种形式的解法，就可以普解法，就可以普遍适用于一切形遍适用于一切形式的式的LP问题，而问题，而单纯形法所基于单纯形法所基于的的LP问题的形式，问题的形式，称为标准形式。称为标准形式。1.1.线性规划问题的标准形式线性规划问题的标准形式mib

13、nixbxaxaxabxaxaxabxaxaxatsxcxcxcziimnmnmmnnnnnn, 2 , 10, 2 , 10. .max221122222121112121112211A=（aij）mn为约束方程组的系数阵。R(A)=mn,即A为满秩阵，称m为LP问题的阶数，n为维数njxmibxatsxczjnjijijnjjj, 2 , 1, 0, 2 , 1,. .max11mnmnmmnnnTTbbbbxxxXaaaaaaaaaAcccCXbAXtsXCZ212121222211121121,0. .max其中： 目标函数目标函数 min Z=CTX 函数约束函数约束b bi i0

14、0 两端乘以两端乘以-1-1约束为约束为“”“”的情况，增加非负变量的情况，增加非负变量 松弛变量松弛变量约束为约束为“”“”的情况，减去非负变量的情况，减去非负变量剩余变量剩余变量 决策变量决策变量对不满足非负性要求的变量，采用对不满足非负性要求的变量，采用“变量代换变量代换法法”2.2.非标准形非标准形LPLP问题的标准化问题的标准化举例：1221 xx1221xx0,36431228. .00053max521521423154321xxxxxxxxxxtsxxxxxz0036431228. .53max21212121xxxxxxtsxxz0, 01361532324312. .23m

15、in212121212121xxxxxxxxxxtsxxz0,151532324312. .23max543212152142132121xxxxxxxxxxxxxxxxtsxxz 如果xk0,可令xk=- xk ， xk 0。 如果xk为自由变量，可令xk=xk_xk，且xk0，xk0。 如果方程中有多个xk为自由变量，按照上述方法会使变量的个数扩大一倍，从而增加问题求解时的计算量，为了尽量少地增加变量的个数，可以令xk=xk-x“，其中x“对每个xk的表达式都是同一个数。变量代换法四、四、 线性规划的解及其性质线性规划的解及其性质 可行解：满足可行解：满足LP问题所有约束条件的向量问题所有

16、约束条件的向量X 可行域可行域所有可行解构成的集合所有可行解构成的集合 最优解：满足目标要求的可行解，记为最优解：满足目标要求的可行解，记为X*，其所对应的目标函数值称为最优值，记为其所对应的目标函数值称为最优值，记为z*。 基本解：基本解的概念只适用于标准型基本解：基本解的概念只适用于标准型LP问题。问题。 基向量和非基向量：基向量和非基向量：A=(aij)mn=(P1 P2 Pn)为线性规划问题为线性规划问题LP的约束条件系数矩阵，其秩为的约束条件系数矩阵，其秩为m。则。则A中任中任一组一组m个线性无关的列向量构成的矩阵个线性无关的列向量构成的矩阵B=(Pji pj2 Pjm)非奇异，称此

17、非奇异，称此m个线性个线性无关的列向量为线性规划问题的一个无关的列向量为线性规划问题的一个基基。如果约束矩阵如果约束矩阵A中某一列向量中某一列向量Pj包含于基包含于基B中，中，则称则称Pj为为基向量基向量，否则称为，否则称为非基向量非基向量。对于给定的一个基，整个矩阵对于给定的一个基，整个矩阵A可以分为两可以分为两部分，即可表示为部分，即可表示为A=(B N) 基变量与非基变量：基变量与非基变量：与基向量与基向量Pjt(t=1,2,m)相对应的变量相对应的变量xjt称为称为基变量，否则称为非基变量。基变量，否则称为非基变量。LP问题的变量问题的变量也自然被相应地分成了两部分也自然被相应地分成了

18、两部分X=(xB xN)T 基本解：基本解：在在LP问题中，满足条件问题中，满足条件AX=b且非且非基变量全部为零的基变量全部为零的X成为基本解。成为基本解。 X=(xB xN)T=(xB 0)T AX=(B N) (xB xN)T=BxB+NxN=b 即基本解即基本解X可以用基变量部分来表示成可以用基变量部分来表示成xB=B-1b 基本可行解：基本可行解：满足非负条件的基本解，或者满足非负条件的基本解，或者说说xB=B-1b00就称其为基本可行解。就称其为基本可行解。基本解基本解可行解可行解基本可行解基本可行解约束矩阵约束矩阵A中中基的数目最多基的数目最多为为Cnm，因而，因而基本解的个数基

19、本解的个数最多也只能有最多也只能有Cnm个，所以个，所以基本可行解的基本可行解的个数也不会超个数也不会超过过Cnm 退化基本解：如果基本解中有一个或者多退化基本解：如果基本解中有一个或者多个基变量为零，则称为退化基本解个基变量为零，则称为退化基本解 可行基：基本可行解对应的基可行基：基本可行解对应的基 最优基：最优基本解对应的基最优基：最优基本解对应的基 标准形标准形LP问题的任一基本可行解，其所含问题的任一基本可行解，其所含正分量的个数比不超过问题的阶数正分量的个数比不超过问题的阶数m，而，而一个非退化的基本可行解必恰有一个非退化的基本可行解必恰有m个正分个正分量，其余分量均为量，其余分量均

20、为0。标准形LP问题解的概念与关系解解满足条件满足条件适用适用对象对象备注备注可行解可行解XAX=bX0各种形各种形式的式的LP问题问题最优解最优解X*AX*=b X*0CTX*=optCTX基本解基本解X=(xB xN)TAX=b|B|0,XN=0标准形标准形LP问题问题XB所含所含分量个分量个数恰为数恰为阶数阶数m，XN含含n-m个个0分分量量基本可行解基本可行解X=(xB xN)TAX=bXB0|B|0,XN=0线性规划解的性质线性规划解的性质 性质性质1：LP问题的可行域问题的可行域R为一凸集为一凸集 性质性质2：LP问题的一个基本可行解与可行域问题的一个基本可行解与可行域R的一的一个

21、极点互相对应个极点互相对应 性质性质3：线性规划的基本定理：对于任何一个给定：线性规划的基本定理：对于任何一个给定的标准形的标准形LP问题问题M来说，若来说，若M有可行解，则必有有可行解，则必有基本可行解；如基本可行解；如M有最优解，则必有最优基本可行有最优解，则必有最优基本可行解。解。 性质性质4：若：若LP问题的可行域问题的可行域R，则，则R至少有一极至少有一极点点 性质性质5：LP问题可行域问题可行域R的极点数量必为有限多个的极点数量必为有限多个五、线性规划的单纯形法五、线性规划的单纯形法 单纯形法的基本思想单纯形法的基本思想 单纯形法有三种形式：单纯形法有三种形式：方程组形式方程组形式

22、 表格形式表格形式 矩阵形式矩阵形式 单纯形法的计算过程单纯形法的计算过程 单纯形表单纯形表单纯形法的基本思想单纯形法的基本思路：单纯形法的基本思路： 求出可行域求出可行域S S的一个基本可行解的一个基本可行解 判别这个基本可行解是否为最有解判别这个基本可行解是否为最有解 在使得目标函数值有所改进的前提下进在使得目标函数值有所改进的前提下进行顶点的转换行顶点的转换 重复上述过程，通过有限步来求解重复上述过程，通过有限步来求解LPLP问题。问题。范例说明范例说明Max Z z 3x1 5x2 =0 x1 + x 3 =8 2x2 + x4 =12 3x1 +4x2 +x5 =36 x1, x2

23、, x3 , x4 ,x5 00 约束方程系数阵：约束方程系数阵：54321,100430102000101aaaaaA有一个基有一个基的非退化的基本可行解为: X0=(0,0,8,12,36)T543100010001aaaB 条典：条典： 基本可行解对应的可行基是一个基本可行解对应的可行基是一个m阶单阶单位阵（排列阵）位阵（排列阵） 目标方程中所有基变量的系数全为目标方程中所有基变量的系数全为0 典式：典式：满足条典的线性方程组满足条典的线性方程组 检验数：检验数：当目标方程中基变量的系数全为当目标方程中基变量的系数全为0时，非基变量的系数可以作为判断当前基时，非基变量的系数可以作为判断当

24、前基本可行解是否最优的一个标志，称检验数本可行解是否最优的一个标志，称检验数 只要目标方程中存在负检验数，就意味着只要目标方程中存在负检验数，就意味着目标值还能增加，就需要把它对应的非基目标值还能增加，就需要把它对应的非基变量变换为基变量。变量变换为基变量。 进基变量选择的规则进基变量选择的规则最小检验数规则最小检验数规则 在负检验数中选择数值最小者，让它对应在负检验数中选择数值最小者，让它对应的非基变量进基。即：的非基变量进基。即： 如果记检验数为如果记检验数为j j（j=1,2, nj=1,2, n）包括基）包括基变量的检验数（全为变量的检验数（全为0 0）那么可用数学表达）那么可用数学表

25、达式表示：式表示： minminj j| | j j0= 0= bl/alk 确定主元确定主元alk，同时也确定，同时也确定l行的基变量离基。行的基变量离基。 基本可行解的变换基本可行解的变换矩阵初等变换矩阵初等变换68X1X2OABCDE(12,0)G(0,9)F(8,6)Z=42单纯形法的单纯形法的几何意义几何意义单纯形法的计算过程单纯形法的计算过程单纯形表单纯形表CjCjC1 C2 Cm Cm+1 Cn比值比值基基解解x1 x2 xm xm+1 xnC1C2Cmx1x2xmb1b2bm1 0 0 a1,m+1 a1n0 1 0 a2,m+1 a2n. 0 0 1 am,m+1 amn检验

26、行检验行z00 0 0 m+1m+1 mnmn单纯形法的计算步骤单纯形法的计算步骤1.把把LP问题化成标准型问题化成标准型2.在系数阵中找出或构造出一个在系数阵中找出或构造出一个m阶排列矩阵作为初始阶排列矩阵作为初始可行基，建立初始单纯形表可行基，建立初始单纯形表3.若所有检验数若所有检验数j0，得到一个最优基本解，停止运算，得到一个最优基本解，停止运算，否则转否则转44.在所有在所有j0中，只要有一个中，只要有一个r0所对应的系数列向量所对应的系数列向量ar0,即一切即一切air0,则该问题无最优解，停止运算，否则该问题无最优解，停止运算，否则转则转55.按最小检验数规则按最小检验数规则mi

27、nminj j| | j j0= 0= K K确定进基变确定进基变量量x xk k和主列和主列a ak k，再按最小比值规则，再按最小比值规则min bi/aik | aik0= bl/alk 确定主元确定主元alk，同时也确定，同时也确定l行的基变量离基。行的基变量离基。6.以以ak为主元对当前表格进行一次换基运算，得到一个为主元对当前表格进行一次换基运算，得到一个新的单纯形表的形式。新的单纯形表的形式。CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5000 x3x4x5812 361 0 1 0 00 2 0 1 03 4 0 0 1-12/236/4检验行检验行

28、0-3 -5 0 0 0CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5050 x3x2x586121 0 1 0 00 1 0 1/2 03 0 0 -2 18-4检验行检验行 30 -3 0 0 5/2 0CjCj3 5 0 0 0 比值比值基基解解x1 x2 x3 x4 x5053x3x2x146 40 0 1 2/3 -1/30 1 0 1/2 01 0 0 -2/3 1/3检验行检验行 42 0 0 0 1/2 1人工变量法人工变量法 单纯形法要求先从系数阵中找出一个m阶排列阵，这往往不容易做到，特别对于系数阵A为降秩阵的LP问题，根本就找不出；还有些LP问题

29、本身并没有可行解，当然也就找不出基本可行解。但由于问题的形式比较复杂，往往不易判断。 采用人工变量法可以解决上述问题。mibnixbxaxaxabxaxaxabxaxaxatsxcxcxcziimnmnmmnnnnnn, 2 , 10, 2 , 10. .max221122222121112121112211A分别给每个约束方程硬行加入一个非负变量分别给每个约束方程硬行加入一个非负变量xn+1，xn+2，xn+m，得到，得到mibmnixbxxaxaxabxxaxaxabxxaxaxatsxcxcxcziimmnnmnmmnnnnnnnn, 2 , 10, 2 , 10. .max221122

30、22221211112121112211B这样，以这样，以xn+1，xn+2，xn+m为基变量，可以得到为基变量，可以得到如下的一个初始基本可行解：如下的一个初始基本可行解：X0=(0,0,0,b1,b2,bm)T这个解这个解X0完全是人为地加入完全是人为地加入m个变量而得到的，因此个变量而得到的，因此称为人造基本解，而把变量称为人造基本解，而把变量xn+1，xn+2，xn+m称称为人工变量。为人工变量。人造解人造解X0显然不是原显然不是原LP问题问题A的基本可行解，但是若的基本可行解，但是若能通过单纯形法的迭代步骤将虚拟的人工变量全部从能通过单纯形法的迭代步骤将虚拟的人工变量全部从基中替换出去，这时可以得到一个基本解基中替换出去，这时可以得到一个基本解Xk，不仅满，不仅满足式足式B,而且由于人工变量而且由于人工变量xn+1=xn+2=xn+m=0，因，因此此Xk的前的前n个分量就构成了原个分量就构成了原LP问题的一个基本可行问题的一个基本可行解。如果经过迭代不能将人工变量变为非基变量，则解。如果经过迭代不能将人工变量变为非基变量，则