《水资源系统分析学习ppt课件.ppt》由会员分享，可在线阅读，更多相关《水资源系统分析学习ppt课件.ppt（123页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲第三讲 水资源系统优化问题水资源系统优化问题（线性规划）（线性规划）1/19/20231 课程内容课程内容n n回顾线性规划的基本概念n n水资源规划中的几个优化应用实例n n线性规划问题的求解介绍1/19/202321、线性规划的基本形式、线性规划的基本形式n n线性规划广泛用于水资源的开发利用规划，工程的设计和施工，水资源系统的管理。n n线性规划模型的特点是在满足一组已知约束条件下，使决策目标达到最优。1/19/202331、线性规划的基本形式、线性规划的基本形式n n线性规划模型的基本数学形式为：1/19/20234n n其它形式：n n1）求和形式n n2）矩阵形式n n3）集
2、合形式n n4）标准形式n n一般形式与标准形式之间的转化1/19/202351、线性规划的基本形式、线性规划的基本形式n n线性规划模型的基本数学形式为：n n式中式中x xj j为为决策变量决策变量，c cj j、a aijij、b bi i 为已知常数。为已知常数。n nc cj j为目标函数的系数，又称为目标函数的系数，又称价值系数价值系数；n nb bi i为为资源约束常数资源约束常数；n na aijij为为技术系数技术系数。n n括号中表示取三种约束不等式中一种，对一括号中表示取三种约束不等式中一种，对一个具体问题来说它将是唯一的。个具体问题来说它将是唯一的。1/19/20236
3、1、线性规划的基本形式、线性规划的基本形式n n线性规划模型的基本结构包括有：n n决策决策变变量量x xi i，它反映了所研究它反映了所研究问题问题需要控需要控制的因素。制的因素。n n目目标标函数，它反映了决策者函数，它反映了决策者对对所研究所研究问题问题的追求。的追求。n n约约束条件，它是束条件，它是实现实现追求目追求目标标的限制条件。的限制条件。1/19/202371、线性规划的基本形式、线性规划的基本形式n n线性规划模型具有哪些特点？线性规划模型具有哪些特点？n n线性规划的目标函数和约束方程必须是线性线性规划的目标函数和约束方程必须是线性函数。函数。n n决策变数是连续分布的，
4、它的解决策变数是连续分布的，它的解x xI I可以是整可以是整数、分数或小数。数、分数或小数。n n目标函数的单一性。目标函数的单一性。n n线性规划模型是确定型的，即模型的参数和线性规划模型是确定型的，即模型的参数和系数系数c cj j、a aijij、b bi i都是已知的，确定的。都是已知的，确定的。1/19/20238n n建立优化模型的步骤为：n n1）根据研究问题的性质决定决策变量；n n2）根据问题的目标，列出与决策变量有关的目标函数；n n3）根据问题的限制条件，列出与决策变量有关的约束条件。1/19/20239几个概念几个概念n n1 1）可行解与可行域：在标准）可行解与可行
5、域：在标准lpslps中，满足约束中，满足约束条件和非负条件的解称为可行解，可行解的集条件和非负条件的解称为可行解，可行解的集合合 称为可行域。称为可行域。n n2 2）基）基.基变量与基解：对于基变量与基解：对于LPSLPS的约束方程的约束方程AX=bAX=b的秩的秩r r（A A）=m=m，B B是是A A的的mm阶可逆子阵，阶可逆子阵，则称则称B B是是LPLP的一个基。其中的一个基。其中B B的任一列向量的任一列向量PjPj称称为向量机，对应的决策变量为向量机，对应的决策变量xj xj称为变量基，变称为变量基，变量基之外的决策变量称为非变量基。量基之外的决策变量称为非变量基。1/19/
6、202310n n3)基可行解与可行基：满足非负条件的基解称为基可行解；基可行解对应的基B即为可行基。n n4)最优解1/19/202311简单线性规划的求解简单线性规划的求解图解法图解法n n求解模型：1/19/2023128、简单线性规划的求解、简单线性规划的求解图图解法解法n n图解法基本原理介绍图解法基本原理介绍n n（1 1）求满足约束条件的可行解区。求满足约束条件的可行解区。以变量以变量x1x1，x2x2为坐标为坐标轴，作轴，作2x2x1 1+3x+3x2 2=100=100和和4x4x1 1+2x+2x2 2=120=120的直线，找出满足约束的直线，找出满足约束条件的可行解域，
7、如图中的阴影区域即为解的可行域。条件的可行解域，如图中的阴影区域即为解的可行域。n n（2 2）令目标函数）令目标函数 ，显然，显然目标函数目标函数z z是随着是随着d d值而变化的一组平行线值而变化的一组平行线。变量。变量d d值，值，使使z z在可行域内平行移在可行域内平行移动求出动求出z z的最大值，即可行域的凸点的最大值，即可行域的凸点C C，z=200z=200，x1=20 x1=20，x2=20 x2=20。C C点即为最优解。点即为最优解。1/19/2023138、简单线性规划的求解、简单线性规划的求解图图解法解法n n图解法基本原理介绍E=6x1+4x2=2004x1+2x2=
8、120E=2x1+3x2=1001/19/2023148、简单线性规划的求解、简单线性规划的求解图图解法解法n n从上述求解过程，可得到以下几点：从上述求解过程，可得到以下几点：n n（1 1）线性规划所有可行解组成的集合的凸集，没有凹）线性规划所有可行解组成的集合的凸集，没有凹入和孔洞部分，是一个实心域，如图的阴影部分。入和孔洞部分，是一个实心域，如图的阴影部分。n n（2 2）如果线性规划问题有最优解存在，它只能在可行）如果线性规划问题有最优解存在，它只能在可行域的凸点上找到，如图中的域的凸点上找到，如图中的A A、B B、C C、DD点。每一个凸点。每一个凸点都对应一组解，称之为基础可行
9、解。使目标函数值点都对应一组解，称之为基础可行解。使目标函数值最大（或最小）的基础可行解称为线性规划问题的最最大（或最小）的基础可行解称为线性规划问题的最优解。优解。n n（3 3）若可行域为有界，则线性规划问题一定有最优解，）若可行域为有界，则线性规划问题一定有最优解，且必定在某顶点处得到；若可行域为无界，则不一定且必定在某顶点处得到；若可行域为无界，则不一定有最优解存在。当目标函数可能在多于一个顶点处达有最优解存在。当目标函数可能在多于一个顶点处达到最大值时，则该线性规划问题有无穷多个最优解。到最大值时，则该线性规划问题有无穷多个最优解。1/19/202315几个概念几个概念n n1 1）
10、可行解与可行域：在标准）可行解与可行域：在标准lpslps中，满足约束中，满足约束条件和非负条件的解称为可行解，可行解的集条件和非负条件的解称为可行解，可行解的集合合 称为可行域。称为可行域。n n2 2）基）基.基变量与基解：对于基变量与基解：对于LPSLPS的约束方程的约束方程AX=bAX=b的秩的秩r r（A A）=m=m，B B是是A A的的mm阶可逆子阵，阶可逆子阵，则称则称B B是是LPLP的一个基。其中的一个基。其中B B的任一列向量的任一列向量PjPj称称为向量机，对应的决策变量为向量机，对应的决策变量xj xj称为变量基，变称为变量基，变量基之外的决策变量称为非变量基。量基之
11、外的决策变量称为非变量基。1/19/202316n n3)基可行解与可行基：满足非负条件的基解称为基可行解；基可行解对应的基B即为可行基。n n4)最优解1/19/2023172、应用一：供水合理分配问题、应用一：供水合理分配问题n n设有甲、乙两个水厂同时向某城市A、B、C三区供水。1/19/2023182、应用一：供水的合理分配问、应用一：供水的合理分配问题题n n甲水厂的日供水量为甲水厂的日供水量为2828万立方米万立方米/日，乙水厂的日日，乙水厂的日供水量为供水量为3535万立方米万立方米/日；日；n n三个区的日需水量分别为三个区的日需水量分别为A A1010万立方米万立方米/日，日
12、，B B1515万立方米万立方米/日，日，C C2020万立方米万立方米/日。日。n n各输水单位水费分别为各输水单位水费分别为c c1111=1.2=1.2，c c1212=1.5=1.5，c c1313=1.1=1.1，c c2121=1.1=1.1，c c2222=1.3=1.3，c c2323=1.4=1.4。试作出在满足对三个区试作出在满足对三个区供水的情况下，输水费用最小的方案。供水的情况下，输水费用最小的方案。1/19/2023192、应用一：供水的合理分配问、应用一：供水的合理分配问题题n n建立的数学模型如下：n n设甲水厂向三个区日供水量为设甲水厂向三个区日供水量为x x1
13、111、x x1212、x x1313，乙水厂向乙水厂向三个区日供水量为三个区日供水量为x x2121、x x2222、x x2323。求供水量佳方案应选求供水量佳方案应选输水费用最小为目标函数，即输水费用最小为目标函数，即1/19/2023202、应用一：供水合理分配问题、应用一：供水合理分配问题n n建立的数学模型如下：n n需水约束需水约束n n供水约束供水约束1/19/2023212、应用一：供水合理分配问题、应用一：供水合理分配问题n n标准数学表达为：n n目标函数：目标函数：n n约束方程：约束方程：n n式中：式中：q qj jjj用户的需水量；用户的需水量；c cij ij由
14、由i i水厂向水厂向j j用户的用户的单位输水费用；单位输水费用；QQj jii水厂的供水能力水厂的供水能力1/19/2023223、应用二：水库调度问题、应用二：水库调度问题n n设某市有二个年调节水库，求二库联合供水的最佳调度方案。1/19/2023233、应用二：水库调度问题、应用二：水库调度问题n n在水库优化调度中，其目标函数可选用效益最大或水资源利用程度最高等目标。本例选用水资源利用程度最高为目标，即要求联合调度方案以供水量最大，弃水量最小为目标函数。1/19/2023243、应用二：水库调度问题、应用二：水库调度问题n n约束条件：n n（1 1）满足水量平衡约束）满足水量平衡约
15、束n n（2 2）设水库的蒸发渗漏损失与水库蓄水量满足某一线性关系，则有）设水库的蒸发渗漏损失与水库蓄水量满足某一线性关系，则有n n（3 3）水库的供水量应满足用户需水量要求，即）水库的供水量应满足用户需水量要求，即1/19/2023253、应用二：水库调度问题、应用二：水库调度问题n n约束条件：n n（4 4）满足水量平衡约束）满足水量平衡约束n n（5 5）决策变量非负：）决策变量非负：n n（6 6）起始水位：起始水位：1/19/2023263、应用二：水库调度问题、应用二：水库调度问题n n变量说明：t t时时段水段水库库蓄水量；蓄水量；已知起已知起调调水位的相水位的相应应蓄水量；
16、蓄水量；t t时时段水段水库库蒸蒸发发渗漏渗漏损损失量；失量；t t时时段水段水库库弃水量；弃水量；t t时时段水段水库库供水量；供水量；t t时时段水段水库库蓄水量下限和上限蓄水量下限和上限约约束；束；t t时时段用段用户户需水量下限需水量下限约约束；束；t t时时段用段用户户需水量上限需水量上限约约束；束；蒸蒸发发渗漏渗漏损损失的关系系数；失的关系系数；目目标标函数的函数的奖罚奖罚系数；系数；T T联合调度的时段总数。联合调度的时段总数。T1/19/2023274、应用三：、应用三：城市需水预测城市需水预测问题问题n n城市水资源规划中应和城市中的经济发展计划联系起来，建立受供水约束的投入
17、产出的线性规划模型，以预测各经济部门的需水量。1/19/2023284、应用三：、应用三：城市需水预测城市需水预测问题问题n n模型的目标函数是以城市总产值增加极大为目标，即1/19/2023294、应用三：、应用三：城市需水预测城市需水预测问题问题n n模型的约束条件有：n n（1 1）设在期间）设在期间t t，LYLY（t t）为最终需求的下限向量；为最终需求的下限向量；UYUY（t t）为最终需求的上限向量，则为最终需求的上限向量，则n n（2 2）城市供水能力的约束）城市供水能力的约束1/19/2023304、应用三：、应用三：城市需水预测城市需水预测问题问题n n变量说明：变量说明：
18、n n 为为n n部门的产出；部门的产出；n n 为投入产出的技术系数矩阵；为投入产出的技术系数矩阵；n n 为部门为部门i i的净产值系数；的净产值系数；n n 为各部门最终需求上限向量；为各部门最终需求上限向量；n n 为各部门最终需求下限向量；为各部门最终需求下限向量；n n 为各部门用水系数向量；为各部门用水系数向量；n n q(t)q(t)为为t t时期城市可供水总量；时期城市可供水总量；n n n n为城市经济部门总数；为城市经济部门总数；n n T T为规划年限，现年为规划年限，现年t=Ot=O，末年末年t=Tt=T；n n r r为贴现率；为贴现率；n n I I为单位矩阵。为
19、单位矩阵。1/19/2023315、实例四：流域规划问题实例四：流域规划问题水水电电站站 水水库库（点（点5）城市城市A（点点6）城市城市B（点点8）洪水堤防洪水堤防水库（点水库（点2）水文站（点水文站（点1）灌区（点灌区（点4）水文站（点水文站（点9）水库（点水库（点7）引水（点引水（点3）1/19/202332如图所示的流域中，有两个水文站（点1和点9），两个城市（点6和点8），三个蓄水水库（点2,5和点7），一个自流灌区（点4），和一个水电站（点5）。试建立考虑城市和农业供水，以及下游防洪条件的河流流域规划模型。5、实例四：流域规划问题实例四：流域规划问题1/19/202333n n1、
20、目标函数：各用水部门的净效益之和最大；n n净效益可以认为是总效益减去损失和费用。损失可能是由于实际供水小于规定指标供水量产生的，费用包括投资回收，工程维护和管理等项费用。净效益表达如下：5、实例四：流域规划问题实例四：流域规划问题1/19/202334n n 部部门门I I在在点点s s处处每每年年的的指指标标配配水水量量T Ts s的净效益；的净效益；n n 部部门门I I在在点点s s处处，在在时时段段t t内内指指标标配配水水量亏缺的损失；量亏缺的损失；n n 部部门门I I在在点点s s处处，在在时时段段t t内内超超过过指指标标配水量的效益；配水量的效益；n n 部部门门I I在在
21、点点s s处处的的水水资资源源工工程程容容量量的的年年费用。费用。5、实例四：流域规划问题实例四：流域规划问题1/19/202335n n2、约束条件：按照各点的工程和用水约束，逐点进行描述n n点点22水库与引水，对于时段水库与引水，对于时段t:t:5、实例四：流域规划问题实例四：流域规划问题1/19/202336n n点点33引水，对于时段引水，对于时段t:t:n n点点44灌区配水，对于时段灌区配水，对于时段t:t:5、实例四：流域规划问题实例四：流域规划问题1/19/202337n n点点55水库和发电，对于时段水库和发电，对于时段t:t:5、实例四：流域规划问题实例四：流域规划问题1
22、/19/202338n n点点66城市城市A A供水，对于时段供水，对于时段t:t:5、实例四：流域规划问题实例四：流域规划问题1/19/202339n n点点77水库，对于时水库，对于时段段t:t:5、实例四：流域规划问题实例四：流域规划问题1/19/202340n n点点88城市城市B B，对于时段对于时段t:t:5、实例四：流域规划问题实例四：流域规划问题1/19/202341n n3、模型的解n n上述模型为非线性；上述模型为非线性；n n首先进行线性化（分段线性近似）；首先进行线性化（分段线性近似）；n n计算机求解；计算机求解；5、实例四：流域规划问题实例四：流域规划问题1/19/
23、202342第三章第三章 整数规划整数规划n n在第在第2 2章所研究的线性规划问题巾，一般规定决策章所研究的线性规划问题巾，一般规定决策变量为非负实数。在实际工作中会遇到一些问题，变量为非负实数。在实际工作中会遇到一些问题，涉及到人员和设备的调配、投资项日的选择、工涉及到人员和设备的调配、投资项日的选择、工程的开发次序等，要求全部或部分决策变量为非程的开发次序等，要求全部或部分决策变量为非负整数。如果日标函数和约束条件都是线性的，负整数。如果日标函数和约束条件都是线性的，求其最优整数解的方法称为整数线性规划求其最优整数解的方法称为整数线性规划(integer linear programmi
24、ng(integer linear programming，ILP)ILP)，简称为整数，简称为整数规划规划(IP)(IP)。整数规划是数学规划的一个分枝。整数规划是数学规划的一个分枝。1/19/202343n n 根据决策变量是否全部要求为整数，可将整数规划分为如下两类。(1)混合整数规划(mixed，MIP)：部分决策变量要求为整数；(2)纯整数规划(pure IP，PIP)或完全整数规划(all IP,AIP)：所有决策变量均要求为整数。在整数规划中，有些问题要求变量只能取0或1，称之为01规划；而后边要介绍的指派问题则是01规划的特例。1/19/202344n n 例1 一运输公司利用
25、卡车运输甲、乙两种货物，卡车的运输能力为体积12m3，重量9t，每箱货物的体积、重量、利润列于表31。如何安排运输方案，使利润最大?1/19/202345n n例2 1程选址问题。在一流域规划中，初步确定的水库坝址有5个(D1，D2，D5)。根据流域发展规划，在干流3个坝址(D1，D2，D3)中最多选择两个，枝流两个坝3xh(D4，D5)中最少选择1个。水库Dj(j1，2，5)的投资为Cj，净效益为Bj。在工程投资总额不超过C的情况下，如何选择坝址使流域水库工程的净效益最大?解 一个坝址有被选用和不选用两种情况，可以用01变量来表示，1/19/2023461/19/202347例例3、在水资源
26、系统扩展规划中在水资源系统扩展规划中的应用的应用n n动态扩展模型常用于两类问题：n n工程建设问题工程建设问题n n容量扩大问题容量扩大问题 1/19/2023486、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）n n1、工程建设问题n n工工程程建建设设问问题题主主要要回回答答如如何何安安排排流流域域工工程程建建设的顺序。设的顺序。n n常采用整数规划的方法。常采用整数规划的方法。1/19/202349n n1、工程建设问题n n参数设定参数设定 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规
27、划）1/19/202350n n1、工程建设问题n n决策变量决策变量n n目标函数目标函数 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202351n n1、工程建设问题n n资金约束资金约束n n建造次数约束建造次数约束 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202352n n1、工程建设问题n n连续性约束连续性约束 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202353n n1、工程建设问
28、题n n库容约束库容约束 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202354n n2 2、容量扩大问题、容量扩大问题n n水水资资源源工工程程一一般般需需要要分分期期建建设设，规规模模和和容容量量需要逐步扩大。需要逐步扩大。n n在在扩扩容容问问题题中中，成成本本和和容容量量是是变变量量。目目标标函函数也是总的净效益最大。数也是总的净效益最大。n n一般设定成本和容量为线性关系一般设定成本和容量为线性关系 6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202355
29、n n2 2、容量扩大问题、容量扩大问题n n预算约束为：预算约束为：6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划中的应用（整数规划）1/19/202356n n2 2、容量扩大问题、容量扩大问题n n库容约束为：库容约束为：6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划中的应用（整数规划）1/19/202357整数规划的求解问题整数规划的求解问题n n从可行域来看，LP可行域为一凸集，可行解一般有无穷多个且连续分布；而IP可行域是LP可行域的子集，其中AIP的可行域是LP可行域内的整数点，可行解一般为有限个且离散分布。而对于IP来
30、说，最优解不一定在其松弛LP可行域的边界上取得，求解比IP要复杂。对IP的求解可以考虑以下几种方法。1/19/202358n n(1)图解法 n n 对于二维IP模型可采用图解法求解，模型(31)的图解法求解如图31所示。可以看出，模型(31)的松弛LP模型的可行域为OABC，LP在可行域顶点B(225，375)处取得最大值ZLP825；IP在A(0，5)处取得最大值ZIP800。LP与IP模型的最大值之差Z25，这一利润的减少是由于增加整数约束所产生的。1/19/202359n n(2)枚举法 由于AIP的可行解为有限个，如果能计算并比较所有可行解的目标函数，则可以确定最优解（3）圆整法 将
31、IP去掉整数约束而松弛为LP，求出lp的最优解，然后在lp的最优解附件选择一个整数解作为ip的最优解。1/19/202360n n（4）分枝定界法n n 如果lp的最优解为整数，则该最优解也是Ip 的最优解，否则lp的最优解是ip最优解的上限。取Lp中不满足整数约束的一个变量，以其邻近的整数为界，讲lp可行域分为包含整数点的两部分分别求解，进一步确定Ip目标函数的上限和下限。主要步骤包括：1）松弛；2）分枝；3）定界；4）比较与剪枝1/19/2023610-1规划规划n n1.过滤隐枚举法n n2.分枝隐枚举法1/19/202362n n3、模型求解：n n非线性关系的分段线性近似。非线性关系
32、的分段线性近似。n n求解整数规划可以采用分枝定界法。求解整数规划可以采用分枝定界法。6、实例实例3：在水资源系统扩展规划：在水资源系统扩展规划中的应用（整数规划）中的应用（整数规划）1/19/202363n n目标规划是多目标问题的一种解决方法。目标规划是多目标问题的一种解决方法。n n问题：问题：7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202364n n需水量和供水费用如下：需水量和供水费用如下：7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202365n n变量：变量：7、实例六：在供水规划中的
33、应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202366n n约束条件：约束条件：n n（1 1）供水约束）供水约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划（目标规划）1/19/202367n n约束条件：约束条件：n n（2 2）需水量约束）需水量约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202368n n约束条件：约束条件：n n（3 3）水源）水源2 2向城镇向城镇1 1供水约束供水约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/20236
34、9n n约束条件：约束条件：n n（4 4）城镇最低供水量约束）城镇最低供水量约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202370n n约束条件：约束条件：n n（5 5）输入可靠性约束）输入可靠性约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划（目标规划）1/19/202371n n约束条件：约束条件：n n（6 6）协调供水平衡条件约束）协调供水平衡条件约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202372n n约束条件：约束条件：n n（7 7）输水费用最
35、小条件约束）输水费用最小条件约束 7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202373n n目标函数：n n根根据据目目标标的的重重要要性性，设设定定P P1 1,P P2 2,P P3 3,P P4 4,P P5 5,P P6 6,六六 个个 等等 级级，各各 目目 标标 之之 间间 的的 关关 系系 是是 P P1 1 PP2 2 P P6 6,即即只只有有满满足足前前一一个个目目标之后，才能考虑满足后一个目标。标之后，才能考虑满足后一个目标。7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/2023
36、74n n目标函数：7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/202375n n目标函数：n n综上所述，目标函数为综上所述，目标函数为：7、实例六：在供水规划中的应用实例六：在供水规划中的应用（目标规划）（目标规划）1/19/2023768、简单线性规划的求解、简单线性规划的求解图图解法解法n n线性规划问题求解的基本数学方法是什么？线性规划问题求解的基本数学方法是什么？n n线性规划的基本解法有图解法和单纯形法两种。线性规划的基本解法有图解法和单纯形法两种。n n图解法一般只适用于解图解法一般只适用于解2323个变量的问题，实用价个变量的问题
37、，实用价值不大。值不大。n n单纯形法是一种解变量较多的常用解法，变量较单纯形法是一种解变量较多的常用解法，变量较少时可用手解，但在解决实际问题时，一般都可少时可用手解，但在解决实际问题时，一般都可以借助于已有的程序用计算机求解。以借助于已有的程序用计算机求解。1/19/202377几个概念几个概念n n1 1）可行解与可行域：在标准）可行解与可行域：在标准lpslps中，满足约束中，满足约束条件和非负条件的解称为可行解，可行解的集条件和非负条件的解称为可行解，可行解的集合合 称为可行域。称为可行域。n n2 2）基）基.基变量与基解：对于基变量与基解：对于LPSLPS的约束方程的约束方程AX
38、=bAX=b的秩的秩r r（A A）=m=m，B B是是A A的的mm阶可逆子阵，阶可逆子阵，则称则称B B是是LPLP的一个基。其中的一个基。其中B B的任一列向量的任一列向量PjPj称称为向量机，对应的决策变量为向量机，对应的决策变量xj xj称为变量基，变称为变量基，变量基之外的决策变量称为非变量基。量基之外的决策变量称为非变量基。1/19/202378n n3)基可行解与可行基：满足非负条件的基解称为基可行解；基可行解对应的基B即为可行基。n n4）凸集.定点：设K是n维欧式空间的一个点集，若k中任意2点P1，P2连线上的一切点可以表示成P=AP1+（1-a)P2(0a1),则称K为凸
39、集。凸集K中一点P不能由任意两点表示时，则称p点为k的一个顶点。1/19/202379（图解法）线性规划的基本定理（图解法）线性规划的基本定理n n5 5）凸集及顶点）凸集及顶点3 3个基本定理个基本定理n n6 6）非基变量检验数（教材）非基变量检验数（教材P32P32）：是）：是LPLP最优判断的主要依据。最优判断的主要依据。1/19/2023808、简单线性规划的求解、简单线性规划的求解图图解法解法n n从上述求解过程，可得到以下几点：从上述求解过程，可得到以下几点：n n（1 1）线性规划所有可行解组成的集合的凸集，没有凹）线性规划所有可行解组成的集合的凸集，没有凹入和孔洞部分，是一个
40、实心域，如图的阴影部分。入和孔洞部分，是一个实心域，如图的阴影部分。n n（2 2）如果线性规划问题有最优解存在，它只能在可行）如果线性规划问题有最优解存在，它只能在可行域的凸点上找到，如图中的域的凸点上找到，如图中的A A、B B、C C、DD点。每一个凸点。每一个凸点都对应一组解，称之为基础可行解。使目标函数值点都对应一组解，称之为基础可行解。使目标函数值最大（或最小）的基础可行解称为线性规划问题的最最大（或最小）的基础可行解称为线性规划问题的最优解。优解。n n（3 3）若可行域为有界，则线性规划问题一定有最优解，）若可行域为有界，则线性规划问题一定有最优解，且必定在某顶点处得到；若可行
41、域为无界，则不一定且必定在某顶点处得到；若可行域为无界，则不一定有最优解存在。当目标函数可能在多于一个顶点处达有最优解存在。当目标函数可能在多于一个顶点处达到最大值时，则该线性规划问题有无穷多个最优解。到最大值时，则该线性规划问题有无穷多个最优解。1/19/2023818、简单线性规划的求解、简单线性规划的求解图图解法解法n n灵敏度分析n n模型参数cj、aij、bi的变化对最优解的影响分析称之为灵敏度分析。1/19/2023828、简单线性规划的求解、简单线性规划的求解图图解法解法n n从图可以看出，目标函数的斜率从图可以看出，目标函数的斜率mm介于直线介于直线EDED与与BFBF的斜率之
42、间，即的斜率之间，即mmEDEDmmmmBFBF，当目标函数的系当目标函数的系数数c cj j发生变化时，其斜率发生变化时，其斜率mm也将发生变化。若也将发生变化。若mmmmmBFBF，则则最优解是不变的，仍是最优解是不变的，仍是C C点。点。1/19/202383价值系数价值系数C的变化对的变化对LP的影响的影响n n当当C C有一变化量有一变化量C C时：时：n n1 1）非基变量检验数将）非基变量检验数将发生变化，即影响最发生变化，即影响最有条件；有条件；n n2 2）对基解没有影响）对基解没有影响1/19/202384n n目标函数系数变化后会引起检验数的变化，一种目标函数系数变化后会
43、引起检验数的变化，一种目标函数系数变化后会引起检验数的变化，一种目标函数系数变化后会引起检验数的变化，一种情况是变化的系数对应基基变量，另一种情况是情况是变化的系数对应基基变量，另一种情况是情况是变化的系数对应基基变量，另一种情况是情况是变化的系数对应基基变量，另一种情况是变化的系数对应的非基变量，下面分别说明这两变化的系数对应的非基变量，下面分别说明这两变化的系数对应的非基变量，下面分别说明这两变化的系数对应的非基变量，下面分别说明这两种情况。种情况。种情况。种情况。n n情况情况情况情况1 1：非基变量所对应目标函数系数变化：非基变量所对应目标函数系数变化：非基变量所对应目标函数系数变化：
44、非基变量所对应目标函数系数变化n n 设设设设cj cj为非基变量所对应的目标函数系数，它对为非基变量所对应的目标函数系数，它对为非基变量所对应的目标函数系数，它对为非基变量所对应的目标函数系数，它对应的检验数为：应的检验数为：应的检验数为：应的检验数为：n n j j=(=(cj+cj+cj cj)CBB-1Pj0CBB-1Pj0n n由上式即可确定系数变化范围。由上式即可确定系数变化范围。由上式即可确定系数变化范围。由上式即可确定系数变化范围。n n情况情况情况情况2 2：基变量所对应目标函数系数变化：基变量所对应目标函数系数变化：基变量所对应目标函数系数变化：基变量所对应目标函数系数变化
45、1/19/2023858、简单线性规划的求解、简单线性规划的求解图图解法解法n n系数系数a aij ij和约束方程常数项和约束方程常数项b bi i值的变化，将引起可行域范围的变化，如值的变化，将引起可行域范围的变化，如图。此时可能产生两种变化：一是最优解的凸点不变，仍为图。此时可能产生两种变化：一是最优解的凸点不变，仍为C C点，但点，但最优解值发生了变化；另一是最优解的凸点也发生了变化。最优解值发生了变化；另一是最优解的凸点也发生了变化。1/19/202386约束矩阵约束矩阵A的变化对的变化对LP的影响的影响n n当当A A有一变化量有一变化量A A时：时：n n1 1）非基变量检验数将
46、发生变化，即影响）非基变量检验数将发生变化，即影响最有条件；最有条件；n n2 2）对基解有影响）对基解有影响1/19/202387资源向量资源向量b的变化对的变化对lp的影响的影响n n当b有一变化量b时：n n1）非基变量检验数将不发生变化，即不影响最有条件；n n2）对基解有影响，影响了解的可行性。1/19/202388n n设：设：b=(b1,b2,，bm)Tn n现其中某元素现其中某元素br变化为变化为br+b：n n则：则：n n X=B-1b=B-1b+B-1bn nn n如果：如果：n nB-1b+B-1b0n n则所得到的最优解仍是问题的最优解。则所得到的最优解仍是问题的最优
47、解。1/19/202389增加决策变量对增加决策变量对LP解的影响解的影响n n 增加变量相当于同时改变该非基变量的价值系数和约束系数。增加变量只影响lp的最优性，一般最优解不变。1/19/202390增加约束条件对增加约束条件对lp的影响的影响n n 增加约束条件一般会增加基变量的个数，能影响原最优解的可行性。如果原最优解能满足新的约束条件，则新的约束条件是多余的，最优解不变；如果不能满足，则需要加入新的约束条件，继续求解。1/19/202391二二.单纯形法单纯形法n n单纯形法的基本思路：对给定的LP模型，从某个基可行解开始，按照一定的规则转换到另一个可行基解（顶点），使新顶点的目标函数
48、值优于原目标函数值，经过有限次迭代直至目标函数达到最优。1/19/202392n n应用单纯形法需要解决3个关键问题：n n1）初始基可行解（顶点）的确定；n n2）基可行解的转换规则；n n3）最优性判断条件1/19/202393n n单纯形法求解模型的过程如下：n n1）讲lp模型转化为标准型n n2）确定初始可行基n n3）求得初始基可行解后进入迭代过程；1/19/2023949、对偶模型与影子价格、对偶模型与影子价格每一个线性规划模型都有一个对偶模型原模型为：则对偶模型为1/19/2023959、对偶模型与影子价格、对偶模型与影子价格对偶模型的意义：原模型的解可以通过求解对偶模型得到。
49、对偶变量反映了原模型变量的影子价格。1/19/20239610、线性规划问题的计算机求解、线性规划问题的计算机求解求解复杂的线性规划问题，由于变量数目较多，一般多采用数学规划程序包求解。适用于微机上线性规划计算软件有GAMS、LINDO等。GAMS软件（General Algebraic Modeling System）是由世界银行组织开发的数学规划软件，它既可以用于数学规划问题，也可以用于求解数学模拟问题；既可以用于线性规划也可用于非线性规划和混合规划是应用较广的一个软件。1/19/20239710、线性规划问题的计算机求解、线性规划问题的计算机求解GAMS软件求解界面（早期的dos版本）：
50、1/19/20239811、课堂小结、课堂小结线性规划的基本形式几个应用实例线性规划问题的求解1/19/202399第四章第四章 非线性规划及其应用非线性规划及其应用n n 在线性规划的数学模型中，当目标函数或约束条件不完全是线性方程时，其最优化问题称为非线性最优化问题(NLP)。尤其当目标函数是二次型函数（凸函数），特别地称为二次规划。1/19/2023100n 一般来说，非线性关系是普遍存在的，线性关系是非线性关系的一种特殊情况或在一定条件下的近似。因此用NLP模型来描述一些实际问题能更准确地反映变量间的关系。近几十年来，NLP发展迅速，目前已成为一种重要的优化方法，在生产实践中得到了广泛