水质模型13章

1、shandong jianzhu university水质模型水质模型水质模型水质模型（shandong jianzhu university水质模型水质模型课程内容课程内容: : 以环境（水环境）系统为研究对象以环境（水环境）系统为研究对象, ,通过分综通过分综合合, ,建立数学模型建立数学模型, ,以寻求系统的最优或较满意的规划方案以寻求系统的最优或较满意的规划方案. 环境系统规划：环境系统规划：运用现代科技的最新技术运用现代科技的最新技术系统工程和系统工程和计算机方法来解决环境系统的规划方法。计算机方法来解决环境系统的规划方法。 环境系统特点环境系统特点：v是一个涉及到社会、经济、环境、

2、资源等方面的问题是一个涉及到社会、经济、环境、资源等方面的问题v是一个多变量、多目标、多层次的复杂系统问题是一个多变量、多目标、多层次的复杂系统问题 水环境系统数学模型类型：水环境系统数学模型类型：v各类水体的水质模型、生态模型、污水处理和输送过各类水体的水质模型、生态模型、污水处理和输送过程的模型程的模型v各类工程实施的经济模型、效益费用分析模型各类工程实施的经济模型、效益费用分析模型v水质评价模型、规划模型水质评价模型、规划模型 shandong jianzhu university水质模型水质模型课程内容课程内容shandong jianzhu university水质模型水质模型本课程

3、主要参考书籍本课程主要参考书籍1.环境环境系统工程系统工程. . 韦鹤平韦鹤平. . 同济大学出版社同济大学出版社2.2.水污染控制系统规划水污染控制系统规划. .傅国伟傅国伟, ,程声通程声通. . 清华大学出版社清华大学出版社3 3. .河流水质数学模型及其模拟计算河流水质数学模型及其模拟计算. .傅国伟傅国伟. . 中国环境科中国环境科学出版社学出版社4.4.系统工程系统工程, ,汪应洛汪应洛. . 机械工业出版社机械工业出版社5 5. .系统分析系统分析. .顾培亮顾培亮 . .机械工业出版社机械工业出版社6.6.中国水环境预测与对策概论中国水环境预测与对策概论. . 刘鸿亮刘鸿亮,

4、,韩国钢韩国钢. . 中国环中国环境科学出版社，境科学出版社，198819887.7.最优化技术应用最优化技术应用. . 韦鹤平韦鹤平. .同济大学出版社同济大学出版社. .8.8.优化与决策优化与决策. . 徐裕生徐裕生. .陕西科学技术出版社陕西科学技术出版社.2004.2004shandong jianzhu university水质模型水质模型chapter 1 系统与系统工程系统与系统工程 集合性：集合性：2个要素构成集合体个要素构成集合体 相关性：内在要素的相互作用相互联系相关性：内在要素的相互作用相互联系 目的性：有规定目的、功能目的性：有规定目的、功能 (不可控自然系统除外不可

5、控自然系统除外) 环境适应性：适应系统外部环境的变化环境适应性：适应系统外部环境的变化v基本特征基本特征 ：“极其复杂的研究对象，即由相互作用和相互依赖的若极其复杂的研究对象，即由相互作用和相互依赖的若干干 组成部分组合成具有特定功能的有机整体，它又从组成部分组合成具有特定功能的有机整体，它又从属于一个更大系统的组成部分属于一个更大系统的组成部分”(钱学森钱学森)。v定义定义：shandong jianzhu university水质模型水质模型（1 1）按组成的属性分为）按组成的属性分为v自然系统自然系统：海洋、大气、生态系统等：海洋、大气、生态系统等v人造系统人造系统：工业、给排水、污染监

6、测控制等：工业、给排水、污染监测控制等v复合系统复合系统：利用自然系统为人类服务建造的系统，气象：利用自然系统为人类服务建造的系统，气象预报等预报等（2 2）按形态分）按形态分v实体系统实体系统：物体实体，如管道构件、机械：物体实体，如管道构件、机械v概念系统概念系统：由概念、原理、法规等组成，如法律系统、：由概念、原理、法规等组成，如法律系统、教育系统教育系统v分类分类 ：shandong jianzhu university水质模型水质模型（3 3）按所处的状态分）按所处的状态分v静态系统静态系统：不随时间变化的系统：不随时间变化的系统v动态系统动态系统：随时间变化的系统：随时间变化的系统

7、（4 4）按照规模分）按照规模分v小型系统小型系统v中型系统中型系统v大型系统大型系统v分类分类 ：shandong jianzhu university水质模型水质模型 1.2 1.2 系统工程系统工程(system engineering)(system engineering) 系统工程是一门新兴的高度综合的科学，是一种组织管系统工程是一门新兴的高度综合的科学，是一种组织管理的科学方法。把研究的对象看成一个系统，解决如何对系理的科学方法。把研究的对象看成一个系统，解决如何对系统进行规划、治理、组织和管理，使之获得最佳效益。统进行规划、治理、组织和管理，使之获得最佳效益。40年代正式形成年

8、代正式形成5060年代逐步形成较为完整的体系年代逐步形成较为完整的体系70年代得到广泛应用，进入初步成熟阶段年代得到广泛应用，进入初步成熟阶段 shandong jianzhu university水质模型水质模型 shandong jianzhu university水质模型水质模型1. 整体性原则：全面、整体整体性原则：全面、整体2. 综合性原则：目标多样性，方法、方案多综合性原则：目标多样性，方法、方案多样性样性3. 优化性原则：实现最佳目标体系优化性原则：实现最佳目标体系4. 模型化原则：模拟与仿真模型化原则：模拟与仿真5. 交互性原则：决策者与系统的信息交换交互性原则：决策者与系统的

9、信息交换shandong jianzhu university水质模型水质模型1. 明确和提出问题明确和提出问题2. 建立数学模型建立数学模型3. 求解数学模型求解数学模型4. 模型验证模型验证5. 结果实施结果实施shandong jianzhu university水质模型水质模型shandong jianzhu university水质模型水质模型 物理模型 图形模型 数学模型 宏观模型 微观模型 shandong jianzhu university水质模型水质模型 水质模型 大气模型 生态模型 经济模型 预测模型 决策模型 最优化模型 shandong jianzhu univers

10、ity水质模型水质模型过程过程1. 明确建模目的明确建模目的2. 提出要解决的具体问题提出要解决的具体问题3. 构思构思 (构造构造) 模型系统模型系统4. 收集相关资料收集相关资料5. 设置变量和参数设置变量和参数6. 建模建模7. 模型检验模型检验8. 模型标准化模型标准化 (归一化、通用性归一化、通用性)9. 模型运行模型运行静态静态数值数值解析解析数值数值解析解析动态动态确定确定随机随机数值数值解析解析数值数值解析解析确定确定随机随机数学模型数学模型shandong jianzhu university水质模型水质模型涉及人类活动的各个领域涉及人类活动的各个领域 (p10 (p10 表

11、表1.1)1.1) 自然环境保护(生态保护)古迹保护土壤保护水生保护野生保护草原保护森林保护环境管理固体废物管理城市规划管理土地利用管理工企环境管理水资源管理环境监测食品监测生物监测土壤监测水质监测大气监测污染控制废能控制固体废弃物控系统水体污控系统大气污控系统微波辐射热噪声振动环境保护系统环境系统的构成shandong jianzhu university水质模型水质模型shandong jianzhu university水质模型水质模型shandong jianzhu university水质模型水质模型shandong jianzhu university水质模型水质模型shandon

12、g jianzhu university水质模型水质模型举例：举例： 城市污水再生回用系统城市污水再生回用系统shandong jianzhu university水质模型水质模型城市的gdp、人均收入、污染治理投资状况污水治理、污水回用的政策、水价政策、投资政策、城市发展规划节水技术、污水处理技术、再生水处理技术水资源丰度、开发利用程度、水污染状况生态环境建设、生态农业、生态环境需水经济因素工业经济城市经济水平工业产值、工业结构、工业布局社会因素人 口政 策民众行为观念科技发展水平人口数量、人口素质对再生水的接受程度污水再生回用系统影响因素生态环境环境因素水 环 境地理环境地理位置、区域特点

13、shandong jianzhu university水质模型水质模型二级处理子系统再生水供水子系统再生处理子系统再生水需水子系统城市市政生活用水子系统工业用水子系统城市生态用水子系统城市供需水子系统城市需水子系统城市供水子系统污水再生回用系统shandong jianzhu university水质模型水质模型再生水供水子系统 二级处理子系统二级处理规模二级处理建设投资二级处理率二级处理工艺 再生处理子系统再生处理规模再生处理建设投资污水回用率再生处理工艺shandong jianzhu university水质模型水质模型住宅冲厕用水冷却补水洗涤用水再生水需水子系统城市生态用水子系统生态建

14、设用水生态景观用水生态农业用水城市市政及杂用水子系统园林绿化用水浇洒道路用水公共建筑用水消防用水洗车用水建筑施工用水锅炉用水空调用水其他用水工业再生水替代子系统shandong jianzhu university水质模型水质模型城市供需水子系统城市生活需水工业需水城市需水子系统城市供水子系统自备水源供水自来水供水再生水供水shandong jianzhu university水质模型水质模型自备水源供自备水源供水量水量污水回用量污水回用量供供 水水 量量自来水供给自来水供给量量需需 水水 量量缺缺 水水 量量生态用生态用水水生活用水生活用水工业用水工业用水城市供需水平衡反馈机制图城市供需水平

15、衡反馈机制图shandong jianzhu university水质模型水质模型市政生活用水量城市生态用水量再生水需水量工业再生水替代量用户接受程度再生水需水子系统再生水需水子系统城市需水量人 口缺 水 量城市供水量生活用水量工 业 产 值工业用水量自备井供水量自来水供水量水资源开发程度给水工程建设投资水环境污染程度量城市供需水子系统城市供需水子系统污 水 量gdp污水回用量二级处理率再生水供水子系统再生水供水子系统二级处理量污水处理工程建设投资再生水供需差污染物排放量城市污水再生回用城市污水再生回用sd模型子系统相互关系图模型子系统相互关系图shandong jianzhu univers

16、ity水质模型水质模型shandong jianzhu university水质模型水质模型八大公害事件八大公害事件shandong jianzhu university水质模型水质模型可持续发展概念可持续发展概念 可持续发展的英文翻译：可持续发展的英文翻译：sustainable development 可持续发展的来源可持续发展的来源：最初是从环境保护角度提出来的，：最初是从环境保护角度提出来的， 在在19721972年的斯德哥尔摩人类环境会议上首次提出了年的斯德哥尔摩人类环境会议上首次提出了“可持续发展可持续发展”。定义有很多，经济学家、环境学家及生态学家都给过学科。定义有很多，经济学家

17、、环境学家及生态学家都给过学科性的定义，但是都有一定的局限性。到性的定义，但是都有一定的局限性。到19871987年，在世界环境委年，在世界环境委员会出版的员会出版的我们共同的未来我们共同的未来( (our conmen future) )一书中给一书中给出了一个明确的大家公认的定义。出了一个明确的大家公认的定义。可持续发展的定义：可持续发展的定义：既满足当代人的需求又不对后代人满足既满足当代人的需求又不对后代人满足其需求能力构成危害的发展。其需求能力构成危害的发展。 水资源可持续发展的含义：水资源可持续发展的含义：水资源的可持续利用水资源的可持续利用shandong jianzhu univ

18、ersity水质模型水质模型整体性原则整体性原则shandong jianzhu university水质模型水质模型chapter 2 系统分析系统分析2.1 概述概述2.1.1 2.1.1 系统分析系统分析( (system analysis) ) 基本概念基本概念 对一个系统内的基本问题对一个系统内的基本问题,用系统的观点思维推理用系统的观点思维推理,在确定和不确定条在确定和不确定条件下件下,通过分析对比通过分析对比,对可能采取的方法进行优化对可能采取的方法进行优化, 得最优方案的辅助得最优方案的辅助决策方法。决策方法。2.1.2 2.1.2 环境系统分析环境系统分析 如河流污染如河流污

19、染（多因素决策）（多因素决策）1. 污染源性质污染源性质2. 排放口位置、形式排放口位置、形式3. 污水处理程度污水处理程度4. 环境容量环境容量5. 河流水文情势河流水文情势6. 稀释扩散与转化稀释扩散与转化 其他因素等等其他因素等等 排污决策，实际上就是一个系统优化问题。排污决策，实际上就是一个系统优化问题。shandong jianzhu university水质模型水质模型2.1.3 2.1.3 系统分析的准则系统分析的准则n 外、内条件相结合：周围环境、能源、交通等外、内条件相结合：周围环境、能源、交通等n 当前利益与长远利益相结合：处理程度与投资当前利益与长远利益相结合：处理程度与

20、投资n 局部与整体利益相结合：管网与厂址局部与整体利益相结合：管网与厂址n 定量与定性分析相结合：定性定量与定性分析相结合：定性定量定量定性定性 2.2 系统分析基本要素系统分析基本要素 包括1. 目的2. 可行性方案3. 模型如前所述：多种形式4. 费用5. 效果6. 评价标准shandong jianzhu university水质模型水质模型 2.3 系统分析步骤系统分析步骤 1. 确定目的（目的与目标关系）确定目的（目的与目标关系）2. 收集分析资料收集分析资料3. 系统模型化系统模型化4. 系统的最优化系统的最优化5. 系统的评价系统的评价 2.4 系统分析的方法系统分析的方法 2.

21、4.1 2.4.1 系统最优化系统最优化v 4个特征目标可定量化目标可定量化 关系模型化关系模型化存在不同解存在不同解无明显最优解无明显最优解v 一般形式mibxxxgtsxxxfzinin, 2 , 1),(),(. .),(max(min)2121shandong jianzhu university水质模型水质模型2.4.2 2.4.2 层次分析法（层次分析法（ahp-analytical hierarchy process) )定性与定量相结合、简单易行、行之有效的一种系统分析方法，定性与定量相结合、简单易行、行之有效的一种系统分析方法，70年代美国的萨蒂提出的。年代美国的萨蒂提出的。

22、该法该法1982年引入，能源、环保也得到应用。年引入，能源、环保也得到应用。层次分析法步骤：层次分析法步骤： 1. 1. 明确问题明确问题 2. 2. 建立层次分析模型建立层次分析模型 最高层（目标层）最高层（目标层） 中间层（准则层）中间层（准则层） 最低层（方案层）最低层（方案层）3. 3. 建立判断矩阵，求最大特征根及特征向量建立判断矩阵，求最大特征根及特征向量 判断矩阵构造：判断矩阵构造：逐层逐项两两比较，评出优劣，可从最低层始逐层逐项两两比较，评出优劣，可从最低层始。（最简单可分为3层） 如fig2.4层次图shandong jianzhu university水质模型水质模型层次图

23、层次图 a c1 c2cm p1 p2 pn（准则层）（准则层）（方案层）（方案层）（目标层）（目标层）shandong jianzhu university水质模型水质模型（第（第i个准则）个准则）判断矩阵判断矩阵nnnnnnnnibbbpbbbpbbbppppc2122221211211121nnnnnnbbbbbbbbbb212222111211对准则对准则ci9/197/175/153/131ijjiijijjiijijjiijijjiijjiijbppbbppbbppbbppbppb极优甚优优于稍优于劣则反之优劣同亦可采用亦可采用2 2，4 4，6 6，8 8等，（专家、分析人员、资

24、料）等，（专家、分析人员、资料）对对i=1,2,mi=1,2,m，由上式可得，由上式可得c ci i的判断矩阵，对目标的判断矩阵，对目标a a，也，也要建立要建立m m个准则的判断矩阵，两两比较，得出判断矩阵。个准则的判断矩阵，两两比较，得出判断矩阵。 shandong jianzhu university水质模型水质模型计算判断矩阵的最大特征根及特征向量通常有三种方法计算判断矩阵的最大特征根及特征向量通常有三种方法：niiitnnjjiiniinjijinwbwdwwwwwwwcmwbnnibma1max2111:.,(:.), 1(.最大特征根向量正则化次方根行元素之积方根法方根法niii

25、njnjjiiijinwbwdwwcnjiwwwbwba1max11:.), 1,(.) 1,(.最大特征根正规化后即为特征向量按行相加得向量每列各元素之和为正规化后按列正规化正规化（则）求和正规化（则）求和shandong jianzhu university水质模型水质模型求和法求和法niiinjjiinjijinwbwcvvwvvvbbva1max1211)(:.),(.最大特征根正规化得特征向量向量按行加 4. 4. 层次单排序及判断矩阵一致性检验层次单排序及判断矩阵一致性检验层次单排序：特征向量w为同一层次相应因素对上一层次某一因素相对重要性的权值，称为层次单排序。shandong

26、jianzhu university水质模型水质模型判断矩阵一致性判断矩阵一致性： 判断矩阵b应满足具唯一非“0”最大特征根max：随机一致性比率随机一致性比率crcr : : crcr 0.100.10，具完全一致性，否，具完全一致性，否则需要新调整判断矩阵。则需要新调整判断矩阵。其中，其中，ci ci 为判断矩阵的一致性指标为判断矩阵的一致性指标, , ri ri 为同阶平均随机一致性指标，可从表为同阶平均随机一致性指标，可从表2-12-1中得到中得到ricicr 1maxnnci), 1,(nkjibbbikjkijn123456789ri000.58 0.91.12 1.24 1.32

27、 1.41 1.45shandong jianzhu university水质模型水质模型 5. 5. 层次总排序和一致性检验层次总排序和一致性检验层次总排序，见表层次总排序，见表2.2（以图（以图2.4为例）为例）wn1 , wn2, , wnmp1 , , , w21 , w22, , w2mp2w11 , w12, , w1m p1a1 , a2 , , am,总排序权值c1 , c2 , , cm, 层次c层次p jmjjwa11jmjjwa21ijmjjwa1a1 , a2 , , am c对对a的单排序权值的单排序权值;wij pi对对cj单排序的权值，单排序的权值，shandon

28、g jianzhu university水质模型水质模型层次总排序一致性检验层次总排序一致性检验p层次对层次对cj单排序一致性指标单排序一致性指标cii,平均随机性指标平均随机性指标rij则则cr0.10，满足一致性，否则重新调整判断矩阵。，满足一致性，否则重新调整判断矩阵。举例举例2.1（作业）（作业）（说明应用方法，注意计算结果有误）（说明应用方法，注意计算结果有误）举例举例: (p41)常州市城市污水排江工程排放口选择系统分常州市城市污水排江工程排放口选择系统分析析(p50图图2-11)mjjjmjjjriaciacr11shandong jianzhu university水质模型水质

29、模型2.4.3 2.4.3 环境问题费用环境问题费用效益分析效益分析(cost-benefit analysis)(cost-benefit analysis) 1.基本学理基本学理国外应用较多，国外应用较多，58年应用于环境污染；年应用于环境污染；国内在环境决策方面的应用较晚。国内在环境决策方面的应用较晚。最佳污染点：费用曲线与效益曲线的交点（如图）。最佳污染点：费用曲线与效益曲线的交点（如图）。是准优，而非最优是准优，而非最优 2.费用效益分析在环保中的应用（后述内容自学）shandong jianzhu university水质模型水质模型最佳污染点治理程度环境效益费用或效益xy效益费用

30、（金额）shandong jianzhu university水质模型水质模型城市污水处理层次模型城市污水处理层次模型城市污水处理城市污水处理运行管理方便运行管理方便 费用低费用低处理效果好处理效果好a-b法法 od法法 a/o法法shandong jianzhu university水质模型水质模型chapter 3 最优化技术最优化技术1.1.最优化技术最优化技术 最优化技术最优化技术: 是从所有可能的方案中选择最佳一种以达是从所有可能的方案中选择最佳一种以达到最有目标的科学，它是到最有目标的科学，它是运筹学运筹学的一个分支。的一个分支。 广泛应用于工广泛应用于工业、农业、交通运输、商业、

31、国防等各个部门各个领域业、农业、交通运输、商业、国防等各个部门各个领域.2.2.运筹学的概念运筹学的概念 运筹学（运筹学（operational research,缩写为缩写为o.r ）:是一门是一门应用于管理有组织系统的科学应用于管理有组织系统的科学; 运筹学一词起源于运筹学一词起源于20世纪世纪30年代年代,1940年英国成立了由物理学家布莱克特年英国成立了由物理学家布莱克特(p.m.s.blackett)组成的第一个研究组组成的第一个研究组,shandong jianzhu university水质模型水质模型3.3.运筹学的发展可分为三个阶段运筹学的发展可分为三个阶段(1)1945到到

32、50年代初年代初,称为创建时期称为创建时期. (2)50年代初期到年代初期到50年代末期年代末期,称为成长时期称为成长时期 (3)20世纪世纪60年代年代,迅速发展和普及时期迅速发展和普及时期 在在1956年引入我国的，年引入我国的，80年代后得到广泛的推广。年代后得到广泛的推广。4.4.运筹学基本特征运筹学基本特征n 系统的整体观念系统的整体观念n 多学科的综合多学科的综合n 模型方法的应用模型方法的应用shandong jianzhu university水质模型水质模型1)1) 分析和表述问题：定性、定量分析确定目标分析和表述问题：定性、定量分析确定目标2)2) 建立模型建立模型3)3)

33、 求解模型和优化方案求解模型和优化方案4)4) 对模型和由模型导出的解进行检验对模型和由模型导出的解进行检验5)5) 建立起对解的有效控制：任何模型都有适用范围建立起对解的有效控制：任何模型都有适用范围, ,注意注意模型和它的解是否有效，并及时调整；模型和它的解是否有效，并及时调整；6)6) 方案的实施方案的实施5 5 运筹学研究问题的步骤运筹学研究问题的步骤shandong jianzhu university水质模型水质模型线性规划（线性规划（linear programming）非线性规划（非线性规划（nonlinear programming）动态规划（动态规划（dynamic pro

34、gramming）整数规划（整数规划（integer programming）网络分析（网络分析（graph theory and network analysis)存贮论（存贮论（inventory theory）排队论（排队论（queuing theory ，waiting line）对策论（对策论（game theory）决策论（决策论（decision theory） 6. 6.运筹学的分支运筹学的分支shandong jianzhu university水质模型水质模型最优化方法最优化方法tntnnbbbbxxxxxbaxcccccxz),(0),(),(),(max212121mn

35、mnaaaaa1111矩阵表示njxmibxaxczjijnjijjnjj, 2 , 10, 2 , 1),(max(min)11线性规划的一般线性规划的一般形式可表示为形式可表示为shandong jianzhu university水质模型水质模型 非标准形式化为标准型式，引入非标准形式化为标准型式，引入v 1. 1. 松驰变量松驰变量约束矩阵方程为约束矩阵方程为“”时，不等式左端加上一个非负变量时，不等式左端加上一个非负变量松驰变松驰变量，使不等式约束变为等式约束，目标函数量，使不等式约束变为等式约束，目标函数cn+i(i=1,2,m)=0v 2. 2. 剩余变量剩余变量约束方程约束方程

36、“”时，不等式左端减去一个非负变量时，不等式左端减去一个非负变量剩余变量，变剩余变量，变不等式约束为等式约束，目标函数同上。不等式约束为等式约束，目标函数同上。v 3. 3. 自由变量自由变量变量非负问题变量非负问题目标函数由最大求最小，变量可负目标函数由最大求最小，变量可负 jnjjjnjjxczxcz11minmaxnjxmibxaxczjijnjijjnjj, 2 , 10, 2 , 1),(max(min)11=bi标准形式标准形式: : shandong jianzhu university水质模型水质模型例题例题: : 将下列线性规划化为标准形将下列线性规划化为标准形取值无约束32

37、1321321321321, 0, 063244239232minxxxxxxxxxxxxxxxz解解: 令令z=z， x1=x1，x3=x3x3，其中其中x30 ，x30； 该问题的标准形式为该问题的标准形式为 : : 0,6332442239200332min5433213321533214332154321xxxxxxxxxxxxxxxxxxxxxxxxxxzshandong jianzhu university水质模型水质模型3.1.2 3.1.2 线性规划求解方法线性规划求解方法1.1.图解法（二维平面问题）图解法（二维平面问题）2. 2. 单纯形法（单纯形法（simplex met

38、hod) simplex method) 3.3.人工变量法（人造基）人工变量法（人造基）4.4.改进单纯形法改进单纯形法 5.5.对偶线性规划对偶线性规划shandong jianzhu university水质模型水质模型1.1.图解法（二维平面问题图解法（二维平面问题）shandong jianzhu university水质模型水质模型图解法例题图解法例题1 1 用图解法求解用图解法求解 以上条件在图形中形成的区域以上条件在图形中形成的区域为阴影部分（即为阴影部分（即oabc区域）区域） 构成了构成了凸多边形凸多边形（凸集，满足于（凸集，满足于约束条件的可行域）约束条件的可行域）虚线表

39、示虚线表示z=2 x1+3x2 ，在在可行域中可行域中寻找目标函数的最优解寻找目标函数的最优解，先设，先设z=0z=0，然后平行上移，直到最，然后平行上移，直到最大值，得出在大值，得出在b b点（点（4 4，2 2），计算），计算z=2 x1+3x2 =14 =14约束条件：约束条件： 3 x3 x1 1+6 x+6 x2 22424代表直线代表直线abab左左下方的半平面；下方的半平面； 2 x2 x1 1+ x+ x2 21010代表直线代表直线bcbc左下左下方的半平面；方的半平面； x x1 1，x x2 20 0 是指第一象限；是指第一象限；shandong jianzhu univ

40、ersity水质模型水质模型 用图解法求解用图解法求解 maxz=2x1+x2目标函数变化目标函数变化ocba2x1+x2=10 x1x13x1+6x=242x1+x2=z 有无限多个最优解有无限多个最优解图解法例题图解法例题2 2 shandong jianzhu university水质模型水质模型oba-x1+2x2=0 x1x1x1-x2=12x1+2x2=z maxz=2x1+2x2 x1 x21 s. t. x1+ 2x20 x1，x20 无最优无最优解解图解法例题图解法例题3 3 shandong jianzhu university水质模型水质模型2. 单纯形法（单纯形法（si

41、mplex method)shandong jianzhu university水质模型水质模型 shandong jianzhu university水质模型水质模型单纯形法基本概念单纯形法基本概念 检验数检验数的求法的求法mijiijjjjacczc1tmiitmitmiixx,0,min0minijijiaabshandong jianzhu university水质模型水质模型原方程可改写为：原方程可改写为： 写成增广矩阵的形式写成增广矩阵的形式利用矩阵的初等行变利用矩阵的初等行变换，将换，将c c1 1 c c2 2c cm m消消为为0 0，得单纯形表。，得单纯形表。shandon

42、g jianzhu university水质模型水质模型单纯形法例题单纯形法例题+0 x3+0 x4变标准形变标准形1.1.变标准形变标准形, ,取松弛变量取松弛变量为为x3，x4基变量基变量, , x1，x2为非基变量为非基变量, , 建立初始建立初始单纯形表单纯形表 最优解检验数最优解检验数1=2, 2=3,3= 4 =0令非基变量令非基变量 x1=x2=0, ,得到初得到初始可行解始可行解x=（0，0，24，10）t目标函数值目标函数值z= 0 写成增广矩阵写成增广矩阵 3x1+ 6x2+x3+0 x4=24 2 x1+x2+0 x3+x4=10z+2x1+3x2+0 x3+0 x4=0

43、shandong jianzhu university水质模型水质模型2. 2. 因基变量检验数因基变量检验数 1 1 和和 2 2大于大于0, 0, 取取maxmax1 1, , 2 2=3 ,=3 ,2 2=3 =3 对对应的非基变量为应的非基变量为x x2 2作为换入变量作为换入变量, ,3.3.确定换出变量确定换出变量: : 4.4.1 1=4=4对应于变量对应于变量x x3 3这一行这一行, ,所以所以x3x3为换出变量为换出变量: :x2x2所在列与所在列与x x3 3所在行的交叉点为所在行的交叉点为6,6,作作为主元素为主元素4110,624min0min22iiiaab检验数检

44、验数值值-z-z值值基变量系数基变量系数基变量基变量值值mijiijjacc11 =2-（0 3+ 0 2）=22 =3-（06+ 01）=30min22iiiaab1=24/6=4 2=10/1=10增广矩阵增广矩阵 3x1+ 6x2+x3+0 x4=24 2 x1+x2+0 x3+x4=10z+2x1+3x2+0 x3+0 x4=0shandong jianzhu university水质模型水质模型4.4.以以6 6 为主元素进行变换为主元素进行变换, ,把这一列变成单位向量把这一列变成单位向量将将x x2 2换到原基变量换到原基变量x x3 3的位置的位置, ,得到新的单纯形表得到新的

45、单纯形表令非基变量令非基变量x1=0，x3=0, ,得到新的基本可行解得到新的基本可行解x=（0，4，0，6）t， 目标函数值目标函数值z= 12 shandong jianzhu university水质模型水质模型此时，最后以行的检验数都是负数或零，即此时，最后以行的检验数都是负数或零，即i 00，目标函数已不再，目标函数已不再增大，那么增大，那么最优解最优解x=（4，2，0，0）t， 目标函数值目标函数值z= 14说明说明: 例题以例题以maxz =cx, ax =b, x0为标准型时，以检验数为标准型时，以检验数j0(j=1,n),为最优判别准则为最优判别准则 若以若以minz =cx

46、, ax =b, x0为标准型时以检验数为标准型时以检验数j0(j=1,n),为为最优判别准则选择换入变量时，取最优判别准则选择换入变量时，取j=cjzj0 确定换入变量确定换入变量.5.5.检查所有的检验数检查所有的检验数1 =1/2, 3 = -1/2 ,2= 4 =0, max1, 3=1/2 0,取取x1为换入变量为换入变量, , 计算计算得得x x4 4为换出变量，通过矩阵变换为换出变量，通过矩阵变换, ,得到新的单纯形表得到新的单纯形表shandong jianzhu university水质模型水质模型单纯形法求单纯形法求( (最大值最大值) )步骤框图步骤框图shandong

47、jianzhu university水质模型水质模型3. 3. 人造基人造基 规划中当约束方程中至少有一个为规划中当约束方程中至少有一个为“=”=”或或“”时，时，松驰变量无法给出一个初始基本可行解，需引入人造基变松驰变量无法给出一个初始基本可行解，需引入人造基变量。量。问题化为标准形式问题化为标准形式 “” “”约束方程左边加一个非负变量约束方程左边加一个非负变量 对初始基本解应用人造基变量对初始基本解应用人造基变量 按单纯形法进行求解按单纯形法进行求解shandong jianzhu university水质模型水质模型3.2 3.2 整数规划整数规划integer programming

48、）至少一个变量限定为非负整数整数或混合整数线性规划。shandong jianzhu university水质模型水质模型3.3 3.3 非线性规划非线性规划(nonlinear programming）目标函数或约束条件中有一个或多个为非线性函数时的规划目标函数或约束条件中有一个或多个为非线性函数时的规划问题。问题。科学研究和工程技术中多数是非线性规划问题。科学研究和工程技术中多数是非线性规划问题。 例如例如：类型类型：无约束最优化法：无约束最优化法： 有约束最优化法有约束最优化法shandong jianzhu university水质模型水质模型举例：举例： 某市有某市有n n个工厂排放

49、污水，拟集中于污水处理厂。已知工厂个工厂排放污水，拟集中于污水处理厂。已知工厂j j的污水排的污水排放量为放量为qj j，单方水每公里的费用为，单方水每公里的费用为c cj j，确定污水处理厂的位置，使总输水，确定污水处理厂的位置，使总输水投资最小。投资最小。解：设污水处理厂位置为（解：设污水处理厂位置为（x x，y y），则），则从工厂从工厂j j到污水处理厂的输水费用为到污水处理厂的输水费用为 n n工厂工厂的总的总输水费用输水费用污水厂污水厂工厂工厂工厂工厂shandong jianzhu university水质模型水质模型3.3.2 无约束最优化方法无约束最优化方法 1.1.minf

50、minf（x x）x xeen n 的一个极小点。为其中：为正定阵矩阵为正定阵，即，极值存在的充要条件：)()()(0)()(min*2*xfxxfxhxfrxxfpnhessianshandong jianzhu university水质模型水质模型 1. 1. 最速下降法（梯度法、登山法）最速下降法（梯度法、登山法） （f(x)在在x(h)处一阶逼近）处一阶逼近） 若目标函数写成操作变量的函数若目标函数写成操作变量的函数 p=f(x1，x2，xm )，那么，那么 p 与与 xh 构成构成 m+1 维空间。若以图形表示函数，就为曲面，曲面的最高点（或最低点）即极维空间。若以图形表示函数，就为

51、曲面，曲面的最高点（或最低点）即极值点值点 所谓所谓“登山登山”即从曲面上任意点（初始解）出发向峰点逼近的过程。即从曲面上任意点（初始解）出发向峰点逼近的过程。 设设 minf（x） xrn函数在点处的梯度为：函数在点处的梯度为： 沿着法线方向上升最快（等高线），反之，沿负梯度的方向，即为下降最沿着法线方向上升最快（等高线），反之，沿负梯度的方向，即为下降最快的方向快的方向 s（k）= f（x（k） （负梯度的方向负梯度的方向） nkkkxxfxxfxf)()()()(1)()( dmshandong jianzhu university水质模型水质模型起点、终点起点、终点 dm 必须满足（必

52、须满足（3.31）式，或由该式协调，然而，）式，或由该式协调，然而， 都是未知的，需要有一种方法解决这一问题。都是未知的，需要有一种方法解决这一问题。mkmdx,（2）快速登山法fdm或hkhhmvxfd1单位矢量hv（1）搜索矢量与步长搜索矢量：搜索矢量：表示从出发点前进的矢量，步长则表示求前进步幅大小。表示从出发点前进的矢量，步长则表示求前进步幅大小。若以矢量表示出发点、到达点，则与搜索矢量的关系可表示为若以矢量表示出发点、到达点，则与搜索矢量的关系可表示为mkmmdxx1（3.31）登山方向矢量使符合由出发点以最大梯度前进使符合由出发点以最大梯度前进 符号符号“ ”，求极大用，求极大用“

53、”，求极小用，求极小用“”。步长步长k的求法：确定为一个常数，试算，但需要检验的求法：确定为一个常数，试算，但需要检验 公式计算：公式计算：xm先给定一个初始点先给定一个初始点 x（0）)()()()()()()()()()(kktkktkkxfxhxfxfxfshandong jianzhu university水质模型水质模型并且并且 xh 在方向移动距离为在方向移动距离为hhxfx 为任意常数，相当于步长为任意常数，相当于步长最速下降法步骤最速下降法步骤： a. 选取初值选取初值x（0）及精度及精度 ； b. 令令k=0； c. 计算计算f（x（k），并令），并令 dm= f（x（k）；

54、）； d. 如果如果 f（x（k）2，最优解迭代终止，最优解迭代终止，x*即为所求，否则即为所求，否则进行下一步；进行下一步； e. 用公式求步长用公式求步长k f. 计算计算 ，k=k+1，转向，转向cmkmmdxx1shandong jianzhu university水质模型水质模型几点说明：几点说明：步长很重要，步长很重要，p p 曲面复杂时要选小些，曲面简单时可大些；曲面复杂时要选小些，曲面简单时可大些；当存在两个以上极值时，一旦到达其一就不能前进，为此应选择几个出发点；当存在两个以上极值时，一旦到达其一就不能前进，为此应选择几个出发点；到达是极值点还是鞍点，落入鞍点就无法解脱；到达

55、是极值点还是鞍点，落入鞍点就无法解脱；变步长方法：变步长方法： 一次成功，下次取一次成功，下次取3 3倍步长；倍步长； 一次失败，下次取一次失败，下次取1/21/2步长。步长。为什么搜索失败？为什么搜索失败？ 如从如从1 1点出发，因步长太大，超越极值点点出发，因步长太大，超越极值点步长小些为好，视步长小些为好，视 p p 增加情况而定。增加情况而定。 0 01 1 ，步长太大，步长太大, , 改向，说明步长不当改向，说明步长不当 如极值为极大如极值为极大, , 改向，改向， 即表示有问题即表示有问题 0 01 1，p p 增长不多增长不多, ,要判别平坦或越过。要判别平坦或越过。154320

56、12起止mdmdshandong jianzhu university水质模型水质模型梯度法例题梯度法例题用梯度法求：用梯度法求：f(x)=(x1-1)2+(x2-1)2的极小值，的极小值，取初值：取初值：x（0）=（0，0）t，=0.1解 ： (1)求目标函数的一阶偏导数 f(x)=2(x1-1) ，2(x2-1)t那么 f(x（0）)=（-2，-2）t(2)检验 (3)继续迭代，求步长k先求海森矩阵8)2()2()(22)0(xf2002)(xh21)()()(xxfxxfxf222122212212211*)()(xfxxfxxfxfxfxhshandong jianzhu univer

57、sity水质模型水质模型11222100)()0(0)0()1(xfxx0)11 (2)11 (2()(22)1(xf所以x（1）为极小点因为21168222002)2, 2(22)2, 2()()()()()()0()0()0()0()0(xfxhxfxfxfttk步长k则11)1(xf(x)=2(x1-1) ，2(x2-1)tshandong jianzhu university水质模型水质模型 2. 二阶梯度法（二阶梯度法（ x(h)处的二阶逼近）处的二阶逼近）222212222221221221221222)()(2)()()()()()()()()()()(21)()()()()(n

58、nnnnkktkktkkkxfxxfxxfxxfxfxxfxxfxxfxfxfxhhessianxfxxxfxxxxxfxfxxf矩阵为海森其中，如果将最速下降法的搜索方向可看作对目标函数的一种线性逼近或如果将最速下降法的搜索方向可看作对目标函数的一种线性逼近或一阶逼近，那么，二阶梯度法则可认为是一阶逼近，那么，二阶梯度法则可认为是f(x)在在x(k)点处的二阶逼近。点处的二阶逼近。将f(x)在其某个近似极小点x(k)处进行二阶talor 级数展开，有shandong jianzhu university水质模型水质模型ckkfxxxxesxxfxfxxdsxfxfckbxakkkkkkkkk

59、kkk，转向第三步、令下一步；，迭代终止，否则进行，则求得最优解、如果、计算搜索矢量、计算、令及、选取初值1)()()()(; 0;)1(*)()1()()()(1)(2)()1()()(1)(2)0(为搜索矢量方向，则，引入步长因子为了保证迭代的收敛性)()()()(1)(2)()1()()(kkkkkkkkkkssxxfxfxx：迭代公式上式变形可得多维牛顿求偏导，展开式对对上页即则应满足极小点的下一个近似点对于)()()()(0)(,)()1()()(2)()1()1(kkkkkkxxxxxfxfxxxxxfk)k)talor)()()()()()(1)()(1)(2)()1(kkkkk

60、kkxfxhxxfxfxxshandong jianzhu university水质模型水质模型.3 有约束非线性规划v 1. 线性逼近法非线性目标函数、线性约束：将目标函数在可行域的任一顶点非线性目标函数、线性约束：将目标函数在可行域的任一顶点x(0)处展开变为线性函数求解线性规划问题。处展开变为线性函数求解线性规划问题。设目标函数是非线性的，约束条件为线性的，其数学模型为 0,minxbaxxf或s.t.tmtnmnmnbbbbxxxxaaaaa,21211111（3.39）式中shandong jianzhu university水质模型水质模型约束条件构成的可行域0,xbaxxr或是凸