线性规划方法(张军).pptVIP

线性规划方法建模 张 军 对运筹学的一个概述 第十一章 线性规划方法 本章主要内容 线性规划模型的引例 线性规划模型的一般形式 线性方程组知识点回顾 线性规划的概念和一般理论 对偶问题和灵敏度分析简介 实例分析——南水北调指标的分配问题 Matlab程序实现和相应程序设计 引例一 线性方程组知识点回顾 设B是秩为m的约束矩阵A中的一个m阶满秩子方阵，则称B为一个“基”（或基阵）。B中的m个线性无关的列向量称为基向量，变量x中与之对应的m个分量成为基变量，其余的称为非基变量。 重点内容回顾 线性规划的含义 线性规划的概念 线性规划的表达方式及 非标准形到标准形的转换方法 线性规划所能解决的问题种类 线性规划的解法——单纯形法 （Matlab或Lingo实现） 南水北调指标的分配问题 实例分析 问题重述 南水北调中线工程建成后，预计2010年的调水量为110亿立方米，主要用来改善经过京、津、冀、豫四省市沿线20个大中城市的用水。用水指标的分配原则是：改善城市环境、促进经济发展、提高用水效益和人民生活水平。生活用水、工业用水和综合服务业用水的分配比例分别为40％、38％和22％。下表是2000年各城市基本状况的统计数据，可以看出，各城市的人口数量差异很大，各城市的生活、工业和综合服务业的用水情况不同，相同的供水量所产生的经济效益也不同。 研究问题：（1）请你综合考虑各种情况，给出2010年每个城市调水分配指标，使得城市的总水量尽量均衡（2）由于各城市的基本状况和自然条件不同，对相同的供水量所产生的经济效益不同，请从经济效益的角度，给出调水指标的分配方案。应注意到，每个城市的工业和综合服务业的发展受产业规模的限制，不可能在10年内无限增长，要适当照顾各城市经济发展的均衡 模型假设 1) 原有供水量保持不变； 2) 人口增长率、工业增加值年增长率和综合服务业人均产值年增长率保持不变 ； 3) 所给工业增加值年增长率、综合服务业人均产值年增长率是在现有的供水条件下的值，即投入的水量按当年的万元用水量产生经济效益。 模型建立(1) 对于问题（1），要求各城市的总用水量尽量“均衡”，我们把“均衡”理解为：各城市新增水量与原供水量的比例相等。 则得到如下的方城： 表示第i个城市2000年的人均用水量， 表示第i个城市的人口总数。 需注意单位！！！ 模型建立(1) 模型建立(1) 于是有： 问题（2）的分析 2010年的工业万元工业增加值用水量为： 即2010年的工业万元增加值用水量等于2000年的工业万元增加值用水量除以2010年的预计工业增加值。（不考虑调水的情况下） 那么调水后的经济效应为工业调水总量除以万元增加值用水量。 问题（2）的分析 同理有综合服务业的结果： 问题（2）的模型 目标为总的经济效益最大： 问题（2）的求解 Matlab里有求解此规划的函数：linprog() LINPROG Linear programming. X=LINPROG(f,A,b) solves the linear programming problem: min f*x subject to: A*x = b x X=LINPROG(f,A,b,Aeq,beq) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq. X=LINPROG(f,A,b,Aeq,beq,LB,UB) defines a set of lower and upper bounds on the design variables, X, so that the solution is in the range LB = X = UB. Use empty matrices for LB and UB if no bounds exist. Set LB(i) = -Inf if X(i) is unbounded below; set UB(i) = Inf if X(i) is unbounded above. X=LINPROG(f,A,b,Aeq,beq,LB,UB,X0) sets the starting point to X0. This option is only available with the active-set algorithm.