水资源系统分析第三讲.pptVIP

第三讲 水资源系统优化问题（线性规划） 课程内容 回顾线性规划的基本概念 水资源规划中的几个优化应用实例 线性规划问题的求解介绍 1、线性规划的基本形式 线性规划广泛用于水资源的开发利用规划，工程的设计和施工，水资源系统的管理。 线性规划模型的特点是在满足一组已知约束条件下，使决策目标达到最优。 1、线性规划的基本形式 线性规划模型的基本数学形式为： 其它形式： 1）求和形式 2）矩阵形式 3）集合形式 4）标准形式 一般形式与标准形式之间的转化 1、线性规划的基本形式 线性规划模型的基本数学形式为： 式中xj为决策变量，cj、aij、bi-为已知常数。 cj为目标函数的系数，又称价值系数； bi为资源约束常数； aij为技术系数。 括号中表示取三种约束不等式中一种，对一个具体问题来说它将是唯一的。 1、线性规划的基本形式 线性规划模型的基本结构包括有： ①决策变量xi，它反映了所研究问题需要控制的因素。 ②目标函数，它反映了决策者对所研究问题的追求。 ③约束条件，它是实现追求目标的限制条件。 1、线性规划的基本形式 线性规划模型具有哪些特点？ ①线性规划的目标函数和约束方程必须是线性函数。 ②决策变数是连续分布的，它的解xI可以是整数、分数或小数。 ③目标函数的单一性。 ④线性规划模型是确定型的，即模型的参数和系数cj、aij、bi都是已知的，确定的。 建立优化模型的步骤为： 1）根据研究问题的性质决定决策变量； 2）根据问题的目标，列出与决策变量有关的目标函数； 3）根据问题的限制条件，列出与决策变量有关的约束条件。 几个概念 1）可行解与可行域：在标准lps中，满足约束条件和非负条件的解称为可行解，可行解的集合 称为可行域。 2）基.基变量与基解：对于LPS的约束方程AX=b的秩r（A）=m，B是A的m阶可逆子阵，则称B是LP的一个基。其中B的任一列向量Pj称为向量机，对应的决策变量xj称为变量基，变量基之外的决策变量称为非变量基。 3)基可行解与可行基：满足非负条件的基解称为基可行解；基可行解对应的基B即为可行基。 4)最优解 简单线性规划的求解—图解法 求解模型： 8、简单线性规划的求解—图解法 图解法基本原理介绍 （1）求满足约束条件的可行解区。以变量x1，x2为坐标轴，作2x1+3x2=100和4x1+2x2=120的直线，找出满足约束条件的可行解域，如图中的阴影区域即为解的可行域。 （2）令目标函数 ，显然目标函数z是随着d值而变化的一组平行线。变量d值，使z在可行域内平行移动求出z的最大值，即可行域的凸点C，z=200，x1=20，x2=20。C点即为最优解。 8、简单线性规划的求解—图解法 图解法基本原理介绍 8、简单线性规划的求解—图解法 从上述求解过程，可得到以下几点： （1）线性规划所有可行解组成的集合的凸集，没有凹入和孔洞部分，是一个实心域，如图的阴影部分。 （2）如果线性规划问题有最优解存在，它只能在可行域的凸点上找到，如图中的A、B、C、D点。每一个凸点都对应一组解，称之为基础可行解。使目标函数值最大（或最小）的基础可行解称为线性规划问题的最优解。 （3）若可行域为有界，则线性规划问题一定有最优解，且必定在某顶点处得到；若可行域为无界，则不一定有最优解存在。当目标函数可能在多于一个顶点处达到最大值时，则该线性规划问题有无穷多个最优解。 几个概念 1）可行解与可行域：在标准lps中，满足约束条件和非负条件的解称为可行解，可行解的集合 称为可行域。 2）基.基变量与基解：对于LPS的约束方程AX=b的秩r（A）=m，B是A的m阶可逆子阵，则称B是LP的一个基。其中B的任一列向量Pj称为向量机，对应的决策变量xj称为变量基，变量基之外的决策变量称为非变量基。 3)基可行解与可行基：满足非负条件的基解称为基可行解；基可行解对应的基B即为可行基。 4)最优解 2、应用一：供水合理分配问题 设有甲、乙两个水厂同时向某城市A、B、C三区供水。 2、应用一：供水的合理分配问题 甲水厂的日供水量为28万立方米/日，乙水厂的日供水量为35万立方米/日； 三个区的日需水量分别为A≥10万立方米/日，B≥15万立方米/日，C≥20万立方米/日。 各输水单位水费分别为c11=1.2，c12=1.5，c13=1.1，c21=1.1，c22=1.3，c23=1.4。试作出在满足对三个区供水的情况下，输水费用最小的方案。 2、应用一：供水的合理分配问题 建立的数学模型如下： 设甲水厂向三个区日供