线性规划及在水资源中的应用.ppt

4/7/2019,线性规划及在水资源 中的应用,1 线性规划问题： 一般地，如果问题的目标函数和约束条件关于决策变量都是线性的，则称该问题为线性规划问题，其模型称为线性规划模型。,一、线性规划问题,2 线性规划方法,实际中所研究的优化问题，一般都是要求使问题的某一项指标“最优”的方案，这里的“最优”包括“最好”、“最大”、“最小”、“最高”、“最低”、“最多”、“最少”等等，这类问题统称为最优化问题，解决这类问题的最常用方法就是线性规划方法。 目前，因为线性规划有着非常完备的理论基础和有效的求解方法，所以线性规划在实际中应用是十分广泛的，譬如像合理地分配、使用有限的资源（经济、人力、物资等），使能够获得“最优效益”等问题。,设某企业现有m种资ai(i=1,2,.,m)用于生产n种产品bj(j=1,2,.,n)，每种资源的拥有量和每种产品所消耗的资源量以及单位产品的利润如下表，试问如何安排生产计划使得该企业获利最大?,建立数学模型,设产品bj产量为xj(j=1 , 2 , . , n)，称之为决策变量，所得的利润为z，则要解决的问题的目标是使 得（总利润）函数 有最大值。决策 变量所受的约束条件为：,于是问题可归结为求目标函数在约束条件下的最大值问题。显然目标函数和约束条件都是决策变量的线性函数，即有下面的线性规划模型：,目标函数：,约束条件：,二、线性规划模型的基本形式,1、一般数学形式为：,其中xi为决策变量，cj、aij、bi为己知常数其中cj为目标函数的系数，又称价值系数；bi为资源约束常数：aij为技术系数。,2、线性规划模型的标准型规定为：,标准型主要是针对线性规划的约束条件而言的，约束条件满足以下两个条件的称为标准型： （1） 约束方程均为等式方程 （2） 所有变量均为非负变量,对于非标准形的线性规划模型都可以化为标准形，其方法如下： （1）目标函数为最小化的问题：令z= - z，则 max z=- min z = - cx （2）约束条件为不等式：对于不等号“（）”的约束条件，则可在“（）”的左端加上（或减去）一个非负变量（称为松弛变量）使其变为等式； （3）对于无约束的决策变量：譬如x（- ，+），则令x= x- x，使得 x，x0，带入模型即可。,线性规划模型最重要的特点就是目标函数和约束条件的方程必须是线性的，如果其中任何一个方程不是线性的，则该模型就不是线性规划模型，而属于运筹学的另一分支，即非线性规划。,三、线性规划模型的特点,四、线性规划解的概念及求解方法,1、线性规划解的概念,（1）解 称满足约束条件的解x=(x1 , x2 , , xm)t 为线性规划问题的可行解；可行解的全体构成的集合称为可行域；使目标函数达到最大的可行解称为最优解。,（2）基 设系数矩阵a=（aij）mxn的秩为m，则称a 的某个mm 阶非奇异子矩阵b（detb0）为线性规划问题的一个基，不妨设b=( aij)mm =(p1 , p2 , pm)，则称向量pj=(a1j , a2j , , amj)t（j=1 , 2 , , m）为基向量。其他的称为非基向量；与基向量对应的决策变量xj(j=1 , 2 , , m)称为基变量，其他的变量称为非基变量。,（3）基解 设问题的基为b=(aij)mm=(p1 , p2 , pm)，将约束方程组变为 （1） 在方程组（1）的解中令xj=0(j=m+1 , , n)，则称解向量x=(x1 , x2 , , xm , 0 , , 0 ,)t 为线性规划问题的基解； （4）基可行性解 满足非负约束条件的基解称为基可行性解； （5）可行基 对应于基可行解的基称为可行基。,2、线性规划的求解方法,线性规划的基本解法有图解法和单纯形法两种，图解法一般只适用于2-3个变量的问题，实用价值不大。单纯形法是一种解变量较多的常用解法，运用此方法时，常借助于已有的程序用计算机求解。,图解法：略 单纯形法： （1）解题思路：求出一个基可行解，检查该基可行解是否为最优解，如果不是，则设法再求出另一个没有检查过的基可行解，如此进行下去，直到得到某一个基可行解的最优解为止。,4/7/2019,（2）求解步骤： a. 初始基可行解的确定 如果线性规划问题为标准型，则从系数矩阵a=(aij)mn观察总可以得到一个m阶单位矩阵im。如果问题不是标准型，则先化为标准型，亦能得到一个m阶单位阵im。取如上m阶单位矩阵im 为初始可行基，即b=im ，将相应的约束方程组变为 xi=bi - aim+1 - - a in x n，(i=1 , 2 , , m) 令xj=0(j=m+1 , , n)，则可得到一个初始基可行解 x(0） = (x1(0), x2(0), , xm(0) , 0 , 0 )t = (b1 , b2 , , bm , 0 , , 0),4/7/2019,b.寻找另一个基可行解 当一个基可行解不是最优解或不能判断时，需要过渡到另一个基可行解，即从基可行解x(0）=(x1(0) , x2(0) , , xm(0) , 0 , 0 )t对应的b=（p1 , p2 , , pm）中替换一个列向量，并与原向量组线性无关。譬如用非基向量pm+1（1t n-m）替换基变量pt （1l m） ，就可以得到一个新的可行基b=（p1 , p2 , , pl-1 ，pm+t ,pl+1 , , pm）,从而可以求出一个新的基可行解x(1）=(x1(1), x2(1) , , xm(1) , 0 , , 0 )t，其方法称为基变换法。 如果x(1）=(x1(1) , x2(1) , , xm(1 ), 0 , , 0 )t仍不是最优解，则可以重复利用这种方法，直到最优解为止。,4/7/2019,c . 最优性检验的方法 假设要检验基可行解x(1) =(x1(1) , x2(1) , , xm(1) , 0 , 0)t =(b1 , b2 , bm , 0 , , 0) t的最优性。由约束方程组对任意的x=(x1 , x2 , , xm )t有 将基可行解x(1)和任意的x=(x1 , x2 , , xm )t分别带入目标函数得,4/7/2019,其中 （j=m+1 , , n）,记 dj = cj- zj （j=m+1 , , n）,则 （2） 注：当dj0时就有z(1) z(0) ; 当dj 0时就有z(1) z(0) . 为此， dj = cj- zj的符号是判断x(1)是否有最优解的关键所在，故称之为检验数。于是由上述（2）式可以有以下结论：,4/7/2019,（1）如果dj0（j=m+1 , , n）,则x(1)是问题的最优解，最优值为z(0); （2）如果dj0（j=m+1 , , n）且至少存在一个 dm+k=0(1 k n-m),则问题有无穷个最优解， x(1)是其中之一，最优值为z(0); （3）如果dj0（j=m+1 , , n）,则x(1)是问题唯一的最优解，最优值为z(0); （4）如果存在某个检验数dm+k(j=m+1 , ,n),且对应的洗系数向量pm+k的各分量ai,m+k0 (i=1 , 2 , ，m)， 则问题具有无界解（即无最优解）,4/7/2019,水资源的合理分配： 设有甲、乙两个水厂同时向某城市a、b、c三区供水。甲水厂的日供水量为28万m3d，乙水厂的口供水量为35万m3 d，三个区的日需水量分别为a10万m3 d，b15万m3 d，c20万m3d由于水厂与各供水区的距离不等，输水条件不同，其单位输水费用也不同。设各输水单位水费分别为c11=1.2,c12=1.5,c13=1.1，c21=1.1，c22=1.3，c23=1.41。试作出在满足对三个区供水的情况下，输水费用最小的方案。,4/7/2019,水厂甲 （28万m3/d）,水厂乙 （35万m3/d）,a(10万m3/d),b(15万m3/d),c(20万m3/d),x11,c11,x12,c12,x13,c13,x21,c21,x22,c22,x23,c23,4/7/2019,解：设甲水厂向三个区日供水量为x11 、x12 、x13，乙水厂向三个区日供水量为x21 、x22 、x23。求供水最佳方案应选输水费用晕小为目标函数，即 minz= c11x11+ c12x12+ c13x13+ c21x21+ c22x22+ c23 x23 = 1.2c11+1.5c12+1.1c13+1.1c21+1.3c22+1.41c23 并满足各区的需水量要求，即 x11+ x21l0 x12+ x2215 x13+ x2320 且各水厂的供水量应小于或