第8章_线性规划和网络流

第8章线性规划与网络流8.1运筹学概论8.2线性规划基础8.3线性规划求解的单纯形算法8.4网络流算法设计与分析线性规划四川师范大学计算机科学学院刘芳28.1运筹学概论运筹学的思想在古代就已经产生了敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法。运筹帷幄之中，决胜千里之外。8.1.1运筹学的历史8.1.2运筹学的应用8.1.3运筹学的研究分支8.1.4运筹学与线性规划算法设计与分析线性规划四川师范大学计算机科学学院刘芳38.1.1运筹学的历史运筹学的诞生20世纪整个世界参与规模最大的事件是什么？第二次世界大战！整个世界的资源都投入到了第二次世界大战中。如何才能更好地利用资源，分配有限的资源，这是一个值得研究的问题。当时在英国军队中率先成立了研究小组来研究这些问题，这就是著名的OR（OperationalResearchGroup）小组，很快美军中也相继成立了OR小组。战争——运筹学诞生的温床。算法设计与分析线性规划四川师范大学计算机科学学院刘芳48.1.1运筹学的历史二战中成功的运筹学案例：英国防空部门如何布置防空雷达，建立最有效的防空警报系统。英，美空军如何提高对地面目标轰炸的命中率。如何安排反潜飞机的巡逻飞行线路，深水炸弹的合理爆炸深度，摧毁德军潜艇数增加400%。商船如何编队，遭潜艇攻击时如何减少损失，使船只受敌机攻击时，中弹数由47%降到29%。这些研究大大提高了盟军的作战能力，为反法西斯战争的最后胜利作出了巨大的贡献！算法设计与分析线性规划四川师范大学计算机科学学院刘芳58.1.2运筹学的应用战争结束了！整个世界投入到了战后的重建国家的经济之中。运筹学的应用迅速转向了民用，相继在工业，农业，经济，社会问题等各个领域中展开了应用。如：算法设计与分析线性规划四川师范大学计算机科学学院刘芳68.1.2运筹学的应用运筹学的应用1.市场销售2.生产计划3.运输问题4.人事管理5.设备维修，更新和可靠性等。6.计算机和信息系统7.城市管理8.对策研究………………算法设计与分析线性规划四川师范大学计算机科学学院刘芳78.1.3运筹学的研究分支研究分支规划论排队论对策论（博弈论）图与网络分析统筹方法存储论决策论、多目标决策等。算法设计与分析线性规划四川师范大学计算机科学学院刘芳88.1.4线性规划的发展规划论规划论是目前运筹学中发展较快、应用较广的一个分支。主要包括：线性规划,非线性规划,整数规划,目标规划,动态规划。规划论所研究的问题主要有两类：给定了一定数量的人力、物力，如何合理调配这些资源，去完成最多的任务；确定了一项任务，如何精打细算，使用最少的人力、物力，去完成这项任务．对于上述问题的一般数学模型的建立、探讨和求解的理论，称为数学规划。其中重要而常用的一种是线性规划。算法设计与分析线性规划四川师范大学计算机科学学院刘芳98.1.4线性规划的发展发展历史法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年旦茨基（G.B.Dantzig）提出了一般线性规划问题求解的方法——单纯形法（simplexmethod），为这门学科奠定了基础。自此线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。算法设计与分析线性规划四川师范大学计算机科学学院刘芳108.1.4线性规划的发展1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。如：1954年C.莱姆基提出对偶单纯形法1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题1956年A.塔克提出互补松弛定理1960年G.B.丹齐克和P.沃尔夫提出分解算法等。算法设计与分析线性规划四川师范大学计算机科学学院刘芳118.1.4线性规划的发展线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。算法设计与分析线性规划四川师范大学计算机科学学院刘芳128.1.4线性规划的发展调查表明：在世界500家最大的企业中，有85%的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。8.2线性规划基础8.2.1什么是线性规划8.2.2线性规划的数学模型8.2.3二维线性规划的图解法8.2.4用excel求解线性规划算法设计与分析线性规划四川师范大学计算机科学学院刘芳148.2.1什么是线性规划线性规划问题是什么样的一类问题呢？请看案例------算法设计与分析线性规划四川师范大学计算机科学学院刘芳158.2.1什么是线性规划例1：生产安排问题问题描述：产品Ⅰ产品Ⅱ设备可用时间设备A2212设备B128设备C4016设备D0412单位利润23问：如何安排生产计划，才能获利最多？算法设计与分析线性规划四川师范大学计算机科学学院刘芳168.2.1什么是线性规划分析：假设x1,x2分别表示在计划期内生产Ⅰ、Ⅱ型产品的件数。产品Ⅰ产品Ⅱ设备所用时间设备可用时间设备A222x1＋2x2≤12设备B12x1＋2x2≤8设备C404x1≤16设备D044x2≤12单位利润23目标：maxZ＝2x1＋3x2生产件数x1x2产品Ⅰ产品Ⅱ设备所用时间设备可用时间设备A2212设备B128设备C4016设备D0412单位利润23生产件数x1x2算法设计与分析线性规划四川师范大学计算机科学学院刘芳178.2.1什么是线性规划于是得到该问题的数学模型：1212121212max23221228s.t.4164120,0Zxxxxxxxxxx目标：算法设计与分析线性规划四川师范大学计算机科学学院刘芳188.2.1什么是线性规划例2：下料问题某车间有长为180cm的钢管（数量足够多），今要将其截为不同长度的管料，长度分别为70cm,52cm,35cm。生产任务规定：70cm需要100根，52cm和35cm的管料分别不少于150根，120根。问：应该如何截取，才能完成任务，同时使余料最少？算法设计与分析线性规划四川师范大学计算机科学学院刘芳198.2.1什么是线性规划解：所有可能的截法有8种：截法长度余料7052351201521206311123410355030246022670132380055算法设计与分析线性规划四川师范大学计算机科学学院刘芳208.2.1什么是线性规划设xj:第j种截法的使用次数。（j=1,2,…,8）则上述问题的数学模型为：12345678123423567134678min562352462352100232150..32351200(18)jzxxxxxxxxxxxxxxxxxstxxxxxxxjL算法设计与分析线性规划四川师范大学计算机科学学院刘芳218.2.1什么是线性规划例3：人力资源分配的问题某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：班次i时间至少所需人数xi16:00～10:0060x1210:00～14:0070x2314:00～18:0060x3418:00～22:0050x4522:00～2:0030x562:00～6:0030x6算法设计与分析线性规划四川师范大学计算机科学学院刘芳228.2.1什么是线性规划设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时。问:该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务员？算法设计与分析线性规划四川师范大学计算机科学学院刘芳238.2.1什么是线性规划解：设xi表示第i班次时开始上班的司机和乘务人员数，这样可以知道:在第i班工作的人数＝第i－1班次时开始上班的人员数＋第i班次时开始上班的人员数;又要求这六个班次时开始上班的所有人员最少，即：要求x1+x2+x3+x4+x5+x6最小。这样建立如下的数学模型：算法设计与分析线性规划四川师范大学计算机科学学院刘芳248.2.1什么是线性规划目标函数：minz=x1+x2+x3+x4+x5+x6约束条件：6~1,0303050607060655443322161jxxxxxxxxxxxxxj算法设计与分析线性规划四川师范大学计算机科学学院刘芳258.2.1什么是线性规划从上面的例子可以看出：虽然各个例子的具体内容各不相同，但归结出的数学模型却属于同一类问题，即在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值的问题。我们将这类问题称为线性规划问题（LinearProgramming）算法设计与分析线性规划四川师范大学计算机科学学院刘芳268.2.1什么是线性规划线性规划（LP）的要素：一组有待决策的变量xj（决策变量）一个线性的目标函数和优化准则z称为目标函数max或min成为优化准则一组线性的约束条件（s.t：subject约束条件）线性规划的应用线性规划是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。算法设计与分析线性规划四川师范大学计算机科学学院刘芳278.2.2线性规划的数学模型线性规划（LP）的定义：若目标函数z为决策变量xj的线性函数，约束条件亦为决策变量xj的线性不等式（或等式），则该数学表达式（模型）称为线性规划模型（LinearProgrammingModel）。注：若目标与约束中至少有一为非线性时，则该模型称为非线性模型（NLP）。算法设计与分析线性规划四川师范大学计算机科学学院刘芳288.2.2线性规划的数学模型线性规划模型的特征：每个问题都追求一个目标，这个目标可以表示为一组变量（决策变量）的线性函数（线性函数就是一次多项式形式的函数）。问题中的若干个约束条件，可用线性等式或线性不等式表示。求解过程就是在若干个可行方案中选择一组或多组方案使目标函数值达到最大或最小。算法设计与分析线性规划四川师范大学计算机科学学院刘芳298.2.2线性规划的数学模型建立线性规划问题数学模型的一般步骤：1.确定决策变量确定合适的决策变量是能否成功的建立数学模型的关键。2.确定目标函数将题目要追求目标列成函数形式（一般用Z作函数中的因变量，决策变量为自变量）。3.确定约束条件方程将题目中与决策变量有关的限制条件列成代数方程。算法设计与分析线性规划四川师范大学计算机科学学院刘芳30一、线性规划的一般形式1.展开式11221111221121122222112212max(min)(,)(,)..(,),,,0nnnnnnmmmnnmnZcxcxcxaxaxaxba