环境系统分析PPT第9讲

1、主讲主讲: 李明俊李明俊 教授教授2006.5.8南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.第五章第五章 环境系统的最优化环境系统的最优化 在对环境问题系统化后，对其中各子系在对环境问题系统化后，对其中各子系统，各因素之间关系建立数学模型，有了系统，各因素之间关系建立数学模型，有了系统化和模型化，便可对适合于不同经济和水统化和模型化，便可对适合于不同经济和水质目标的种种可供选择的方案，定量的进行质目标的种种可供选择的方案，定量的进行费用效益分析，在综合评价（优化）的基础费用效益分析，在综合评价（优化）的基础上确定近远期的经济和水质目标，最后制定上确定近

2、远期的经济和水质目标，最后制定出可供实施的控制规划方案等内容，因此最出可供实施的控制规划方案等内容，因此最优化是综合评价的关键手段。优化是综合评价的关键手段。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n最优化方法是指系统对某一具体的目标最优化方法是指系统对某一具体的目标函数在满足给定的约束条件下取最优值函数在满足给定的约束条件下取最优值的分析求解方法的分析求解方法n目前应用较多的是线性规划和动态规划目前应用较多的是线性规划和动态规划方法方法 n用线性规划或动态规划方法求解最优方用线性规划或动态规划方法求解最优方案虽能解决许多问题，但仍有许多问题案虽能

3、解决许多问题，但仍有许多问题它不能解决，而运用系统化却可以容纳它不能解决，而运用系统化却可以容纳人类过去有的大多数知识与经验，解决人类过去有的大多数知识与经验，解决更多的问题，然而，能够采用最优化方更多的问题，然而，能够采用最优化方法的情况，应该尽量采用。法的情况，应该尽量采用。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.一、线性规划的方法与一、线性规划的方法与0-1型整数规划型整数规划 1、什么是线性规划问题、什么是线性规划问题 线性规划问题就是求一些非负的变线性规划问题就是求一些非负的变量，它们应满足一组表述为线性等式或量，它们应满足一组表述为线性

4、等式或线性不等式的约束条件，并使线性的目线性不等式的约束条件，并使线性的目标函数取极值（最大或最小）标函数取极值（最大或最小） 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.（1）把一个实际问题抽象为一个线性规划的）把一个实际问题抽象为一个线性规划的问题：问题：a问题：（绪论中曾提及过）问题：（绪论中曾提及过） 有一条下水干管把城市污水和一个有一条下水干管把城市污水和一个大型制糖厂的废水合并排入一条河中，大型制糖厂的废水合并排入一条河中，见下图：见下图： 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18. 在系统综合阶段提

5、出的可考虑的治在系统综合阶段提出的可考虑的治理方法，是对城市污水进行一级处理或理方法，是对城市污水进行一级处理或二级处理，也可通过对制糖厂的综合治二级处理，也可通过对制糖厂的综合治理减少该排放口的排污量，每类治理方理减少该排放口的排污量，每类治理方法可能削减的最大法可能削减的最大BOD5/日量及其相应的日量及其相应的费用列于下表中：费用列于下表中： 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18. 需决定的问题是：采取什么治理措需决定的问题是：采取什么治理措施才能既使排放总量削减到允许排放量施才能既使排放总量削减到允许排放量以下，又使总的治理费用最小。以下，

6、又使总的治理费用最小。 b把问题抽象为线性规划数学模型把问题抽象为线性规划数学模型 把一个实际问题抽象为一个线性规把一个实际问题抽象为一个线性规划数学模型，一般包括确定划数学模型，一般包括确定评价指标评价指标，明确明确决定变量决定变量，建立，建立目标函数目标函数和建立和建立约约束条件束条件四个步骤。四个步骤。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n确定评价指标确定评价指标 前述问题要求我们找到一个最省钱前述问题要求我们找到一个最省钱的治理方案，因此对于此问题的评价指的治理方案，因此对于此问题的评价指标就是费用，设所需的总费用为标就是费用，设所需的

7、总费用为Z，则则Z最小的方案就是理想的方案。最小的方案就是理想的方案。 n明确决定变量明确决定变量 对于该例子，应决定的事是选择治对于该例子，应决定的事是选择治理方案，决定每种治理方案所应削减的理方案，决定每种治理方案所应削减的BOD5量，也即每种方法所应承担任务的量，也即每种方法所应承担任务的大小。大小。南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18. 为此定义一个决定变量为此定义一个决定变量Xi,j，为第为第i个个污染源采用它所能采用的第污染源采用它所能采用的第j种治理方法种治理方法所承担的所承担的BOD5削减量与该方法的最大可削减量与该方法的最大可能削

8、减量之比，即能削减量之比，即 可知：可知：0 xi,j1 Xi,j=0时表示不采用第时表示不采用第i个源的第个源的第j种方法。种方法。 Xi,j=1时表示要求第时表示要求第i个源用第个源用第j种方法治理种方法治理达到最大能力达到最大能力 。南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.对于前述问题，可以写出：对于前述问题，可以写出： 所以：所以：南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n建立目标函数建立目标函数 为了把决定变量与评价指标联系起来，为了把决定变量与评价指标联系起来，则需建立则需建立Xi,j与与Z之间

9、的函数关系，即建之间的函数关系，即建立目标函数。立目标函数。 对本例，各方案已知费用与对本例，各方案已知费用与BOD5的的削减量成正比（并假设为线关系），因削减量成正比（并假设为线关系），因此可以写出对第此可以写出对第i个污染源使用第个污染源使用第j种治理种治理方法的费用方法的费用Ci,j，即有：即有： Ci,j=Ci,jmaxXi,j (5-2) 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.对于各种治理方法，有：对于各种治理方法，有：C1,1=36500X1,1 (5-2 a)C1,2=9000X1,2 (5-2 b)C2,1=3000X2,1 (5-

10、2 c)从而总费用为：从而总费用为： Z=36500X1,1+9000X1,2+3300X2,1 (5-3)此即为本例的目标函数。此即为本例的目标函数。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n建立约束条件：建立约束条件： 在解决水环境系统问题时除了要节省在解决水环境系统问题时除了要节省费用外，还必须使采取的方案能实现预费用外，还必须使采取的方案能实现预期的治理目标（使排放量减到允许排放期的治理目标（使排放量减到允许排放量或使水质达到期望指标等等），以及量或使水质达到期望指标等等），以及考虑技术上的可行性等。这类在作出决考虑技术上的可行性等。这类在

11、作出决定时需要考虑的因素在抽象为线性规划定时需要考虑的因素在抽象为线性规划数学模型时就成为约束条件。数学模型时就成为约束条件。 对于本例问题作决定时有两个必须考对于本例问题作决定时有两个必须考虑的因素：虑的因素： 已给定的最大允许排放强度已给定的最大允许排放强度（91.3吨吨BOD5/日）和每种治理方法所能日）和每种治理方法所能达到的最大能力。达到的最大能力。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.可抽象为：可抽象为：a最大允许排放强度约束最大允许排放强度约束106+60M1,1M1,2M2,191.3 (5-4)代入式（代入式（5-1，d）、（）

12、、（5-1，e）和（和（5-1，f）并整理得：并整理得： 84.8X1,1+31.8X1,2+48X2,174.7 (5-4 a) 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.b.治理能力约束治理能力约束 M1,1M1,1max M1,2M1,2max M2,1M2,1max即即 X1,11 （5-5 a） X1,21 （5-5 b） X2,11 （5-5 c） 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.c非负变量约束非负变量约束 按关于线性规划问题的定义，所求的按关于线性规划问题的定义，所求的变量应是非负的，故

13、要求：变量应是非负的，故要求： X1,10 （5-6 a） X1,20 （5-6 b） X2,10 （5-6 c） 从式（从式（5-4）到（）到（5-6）都是约束条件，）都是约束条件，可以看出约束条件的作用是规定了决定可以看出约束条件的作用是规定了决定变量可以取值的范围。变量可以取值的范围。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n线性规划模型线性规划模型 综合上述四个步骤，我们已把原始问题综合上述四个步骤，我们已把原始问题抽象为如下一个线性规划数字模型，即：抽象为如下一个线性规划数字模型，即： 求一组非负变量求一组非负变量 Xi,j (i=1，j

14、=1、2，i=2, j=1)使目标函数使目标函数 Z=36500X1,1+9000X1,2+3300X2,1 最小最小 并满足：并满足：84.8X1,1+31.8X1,2+48X2,174.7 X1,11 ； X1,21 ； X2,11 ； Xi,j0 ；南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.c线性规划数学模型的一般形式：线性规划数学模型的一般形式：求一组变量求一组变量Xi (i=1,2n)使目标函数使目标函数Z=C1X1+ C2X2 +CnXn 取极值（最大或最小）取极值（最大或最小）, 同时满足：同时满足： a11x1+ a12x2+ +a1n

15、xn （）b1 a21x1+ a22x2+ +a2nxn （）b2 am1x1+ am2x2+ +amnxn （）bm 和和Xi0 （i=1,，n） 式中的式中的 （）表示三种符号中取一个。）表示三种符号中取一个。南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.2、线性规划问题的解法简介、线性规划问题的解法简介 线性规划问题有一种很有效的解法线性规划问题有一种很有效的解法单纯形法，此法仅用到加、减、乘、除，单纯形法，此法仅用到加、减、乘、除，故易于推广应用。故易于推广应用。 下面介绍单纯形法基本出发点和一般下面介绍单纯形法基本出发点和一般解算过程，为了便于理

16、解，先介绍一个解算过程，为了便于理解，先介绍一个只有二个决定变量的线性规划问题的图只有二个决定变量的线性规划问题的图解方法。解方法。南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.（1）线性规划问题的图解法。）线性规划问题的图解法。设有以下线性规划问题：设有以下线性规划问题： 求非负变量求非负变量x和和y，使目标函数使目标函数Z=5xy 最最大，大，并满足：并满足： 3xy9 （5-9 a） 0.45x+0.85y2.25 （5-9 b） 3x+y0 （5-9 c） x0 （5-9 d） y0 （5-9 e）南昌航空工业学院环境系统分析课件南昌航空工业学院环

17、境系统分析课件2006.4.18.a约束条件的图表表达形式：约束条件的图表表达形式： 先在先在x-y坐标平面上画出各约束条件坐标平面上画出各约束条件取等于符号时的直线（见下图），并按取等于符号时的直线（见下图），并按不等号方向找出可行域。不等号方向找出可行域。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.b目标函数的图形表达方式：目标函数的图形表达方式： 在约束条件图上可作出一系列目标在约束条件图上可作出一系列目标函数的等值线（见下图），如设函数的等值线（见下图），如设Z=0，则则相应的等值线为相应的等值线为y=5x，Z=6则则y=5x6南昌航空工业学院

18、环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n等值线穿过可行域的线段（如等值线穿过可行域的线段（如EFEF）上的上的各点既满足约束条件，又有相同的各点既满足约束条件，又有相同的Z值。值。n越靠近右边的等值线越靠近右边的等值线Z值越大。值越大。 c确定最优解确定最优解 与可行域相切的最右边的一条等值线与可行域相切的最右边的一条等值线的的Z值为最大值，切点即为决定变量的最值为最大值，切点即为决定变量的最优解，相反最左边的一条为最小值。优解，相反最左边的一条为最小值。 本例为本例为 x*=3.3 y*=0.9 z=15.6 南昌航空工业学院环境系统分析课件南昌航空工业学院环境

19、系统分析课件2006.4.18.（2）单线形法的基本出发点和一般算法）单线形法的基本出发点和一般算法 事实上对于多个变量的线性规划问事实上对于多个变量的线性规划问题，最优解也一定是可行域的一角点，题，最优解也一定是可行域的一角点，如果能设法通过一些代数运算，从某一如果能设法通过一些代数运算，从某一角点开始，找出另一个使目标函数值上角点开始，找出另一个使目标函数值上升（求最大值问题）或下降（求最小值升（求最大值问题）或下降（求最小值问题）的角点，依次逐点寻找，最后必问题）的角点，依次逐点寻找，最后必可找到使目标函数取极值（最大或最小）可找到使目标函数取极值（最大或最小）的角点，从而比较快地找到最

20、优解。这的角点，从而比较快地找到最优解。这就是就是1947年美国数学家年美国数学家Geoge B.Dantzig 提出的单纯形法的提出的单纯形法的基本出发点基本出发点。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.线性规划问题有标准型和非标准型两种：线性规划问题有标准型和非标准型两种： 标准型是指求一组非负变量标准型是指求一组非负变量x1，xn ，使目标函数使目标函数Z值取最大值，并满足值取最大值，并满足只含只含“”“”号的一系列约束条件的线性号的一系列约束条件的线性规划问题。规划问题。 不符合上述定义的即为非标准型不符合上述定义的即为非标准型（如求最小

21、值等）（如求最小值等） 标准型线性规划问题的单纯形法已标准型线性规划问题的单纯形法已有非常成熟的解法和计算机程序软件有非常成熟的解法和计算机程序软件 。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.几几个解的概念个解的概念n可行解：满足约束条件及非负条件的解可行解：满足约束条件及非负条件的解n最优解：使目标函数达到极值的可行解。最优解：使目标函数达到极值的可行解。n基本解：约束方程为基本解：约束方程为m个，而变量为个，而变量为n，且且nm，则可行解有无穷多个。选出则可行解有无穷多个。选出m个个变量构成变量构成m个方程，并令其余（个方程，并令其余（nm）个

22、个变量取零值，若此时约束方程组有唯一解，变量取零值，若此时约束方程组有唯一解，则该解称为基本解，被求解的则该解称为基本解，被求解的m个变量为个变量为基变量，其余为非基变量。基变量，其余为非基变量。n基本可行解：若基本解满足非负条件则称基本可行解：若基本解满足非负条件则称为基本可行解。为基本可行解。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n非标准线性规划问题的解法非标准线性规划问题的解法 对非标问题，一般分两步求解，即先将对非标问题，一般分两步求解，即先将问题转化为标准型，然后前述方法解标准问问题转化为标准型，然后前述方法解标准问题。题。下面着重论述

23、转化方法：下面着重论述转化方法： 把原目标函数把原目标函数Z等式两边同乘（等式两边同乘（-1），），令令 Z = - Z ， 则则 Z m i n 变 为变 为 Z m a x , 系数系数 Cj=（-1）Cj，j=1,n 定义一个新函数定义一个新函数SZ，其对应于非基变其对应于非基变量的系数量的系数C“j等于该变量所在的大于等于约等于该变量所在的大于等于约束中和等于约束中该变量的系数的总和束中和等于约束中该变量的系数的总和 。南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18.n实际问题中，变量实际问题中，变量X k可能有正有负，即可能有正有负，即不满足非负变

24、量要求，此时可令：不满足非负变量要求，此时可令： X k= XkXk 其中其中 Xk0 Xk0 则满足非负要求。则满足非负要求。 即做这种变量代换后，同样可作标即做这种变量代换后，同样可作标准问题求解，问题得以解决。准问题求解，问题得以解决。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统分析课件2006.4.18. 前面已举过的例题（河流、城市污水、前面已举过的例题（河流、城市污水、制糖厂污水）制糖厂污水） 的解为：的解为： z*= 10855万元万元 X*1，1=0 X*2，1=1 X*1，2=0.84 故故 M*1,1=0 即对于该城市污水不需即对于该城市污水不需要二级处理。要二级处理。M*1,2=31.80.84=26.71吨吨BOD5/日日 （84%）M*2,1=48X*2,1=481=48吨吨BOD5/日日 =M2,1max 即制糖厂污水按最大能削减量处理，即制糖厂污水按最大能削减量处理，如此可达最低费用如此可达最低费用10885万元，且达标。万元，且达标。 南昌航空工业学院环境系统分析课件南昌航空工业学院环境系统