第八章线性规划与网络流ppt课件.ppt

《第八章线性规划与网络流ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学习要点理解线性规划算法模型掌握解线性规划问题的单纯形算法理解网络与网络流的基本概念掌握网络最大流的增广路算法掌握网络最大流的预流推进算法掌握网络最小费用流的消圈算法掌握网络最小费用流的最小费用路算法掌握网络最小费用流的网络单纯形算法第8章线性规划与网络流1问题与建模模型：对真实系统的结构与行为用图、解析式或方程来描述的合称为模型。数学模型：通过抽象和简化，使用数学语言对实际对象的一个刻画，以便于人们更简明更深刻地认识所研究的对象数学建模：根据要求，针对实际问题，组建数学模型的全过程（包括建立、求解、分析、检验等）2线性规划模型应用最广泛的方法之一。是最基本的方法之一。网络规划，整数规划，目

2、标规划和多目标规划都是以线性规划为基础的。是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大3仓库租赁问题某企业计划为流通的货物租赁一批仓库。必须保证在时间段i=1,2,…,n，有bi的仓库容量可用。现有若干仓库源可供选择。设cij是从时间段i到时间段j租用1个单位仓库容量的价格，1ijn。应如何安排仓库租赁计划才能满足各时间段的仓库需求，且使租赁费用最少。在现实生活中利用现有资源来安排生产以取得最大经济效益的问题，经常表述为线性规划问题。48.1线性规划问题和单纯形算法线性规划问题及其表示线性规划问题可表示为如下形式：s.t.目标函数约束条件目标函数和约束条件都为线性

3、函数，所以称为线性规划问题。线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题5变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。所有可行解构成的集合称为线性规划问题的可行区域。使目标函数取得极值的可行解称为最优解。在最优解处目标函数的值称为最优值。有些情况下可能不存在最优解。通常有两种情况：(1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集；(2)目标函数没有极值，也就是说在n维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。6一个可行解：1,5,1,2这个问题的最优解为(x1,x2,

4、x3,x4)=(0,3.5,4.5,1)；最优值为16。7仓库租赁问题某企业计划为流通的货物租赁一批仓库。必须保证在时间段i=1,2,…,n，有bi的仓库容量可用。现有若干仓库源可供选择。设cij是从时间段i到时间段j租用1个单位仓库容量的价格，1ijn。应如何安排仓库租赁计划才能满足各时间段的仓库需求，且使租赁费用最少。设租用时间段i到时间段j的仓库容量为yij，1ijn。则租用仓库的总费用为：在时间段k可用的仓库容量为：仓库租赁问题可表述为下面的线性规划问题：8线性规划基本定理约束条件(8.2)-(8.5)中n个约束以等号满足的可行解称为线性规划问题的基本可行解。基：矩阵中的

5、最大线性无关组基本解：满足Ax=b，且非基变量为0的解基本可行解：满足非负条件的基本解。线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。Dantzig于1948年提出了线性规划问题的单纯形算法。单纯形法迭代的基本思路是：先找出一个基本可行解，判断其是否为最优解，如为否，则转换到相邻的基本可行解，并使目标函数值不断增大，一直找到最优解为止。（即在凸集的各个顶点进行测试，判断是否为最优）单纯形算法的特点是：（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；（2）一般经过不大于m或n次迭代就可求得最优解。9max(1-17)在约束条件（1-18）式的变量的

6、系数矩阵中总会存在一个单位矩阵，不妨设为(1-20)基本可行解理解例子式中称为基向量,同其对应的决策变量称为基变量,模型中的其它变量称为非基变量。在(1-18)式中令所有非基变量等于零,即可找到一个解X=(，)T=(b1,…,bm,0,…,0)T因有b≥0,故X满足约束(1-19),是一个基本可行解记为又称初始基本可行解。例3求解非齐次线性方程组(5/4,1/4,0,0)是一个基本可行解约束标准型线性规划问题的单纯形算法当线性规划问题中没有不等式约束(8.2)和(8.4)式，而只有等式约束(8.3)和变量非负约束(8.5)时，称该线性规划问题具有标准形式。再考察一类更特殊的标准形式线性规划问

7、题。这一类线性规划问题中，每一个等式约束中，至少有一个变量的系数为正，且这个变量只在该约束中出现。在每一约束方程中选择一个这样的变量，并以它作为变量求解该约束方程。这样选出来的变量称为左端变量或基本变量，其总数为m个。剩下的n-m个变量称为右端变量或非基本变量。这一类特殊的标准形式线性规划问题称为约束标准型线性规划问题。任意一个线性规划问题可以转换为约束标准型线性规划问题。12x2x3x5z0-13-2x17