排行榜 -

您的位置:首页 > ppt下载 > PPT课件 > 课件PPT > 最优化问题ppt

最优化问题ppt下载

素材预览

最优化问题ppt

这是最优化问题ppt,包括了网络最优化问题基本概念,最小费用流问题,最大流问题,最短路问题,最小支撑树问题,货郎担问题和中国邮路问题等内容,欢迎点击下载。

最优化问题ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.

第5章 网络最优化问题 本章内容要点 网络最优化问题的基本概念 网络最优化问题的四种主要类型:最小费用流、最大流、最短路、最小支撑树 各种网络最优化问题的建模与应用 本章节内容 5.1 网络最优化问题基本概念 5.2 最小费用流问题 5.3 最大流问题 5.4 最短路问题 5.5 最小支撑树问题 5.6 货郎担问题和中国邮路问题 本章主要内容框架图 5.1 网络最优化问题基本概念 网络在各种实际背景问题中以各种各样的形式存在。交通、电子和通讯网络遍及我们日常生活的各个方面,网络规划也广泛用于解决不同领域中的各种问题,如生产、分配、项目计划、厂址选择、资源管理和财务策划等等。 网络规划为描述系统各组成部分之间的关系提供了非常有效的直观和概念上的帮助,广泛应用于科学、社会和经济活动的各个领域中。 近些年来,运筹学(管理科学)中一个振奋人心的发展是它的网络最优化问题的方法论和应用方面都取得了不同寻常的飞速发展。 5.1 网络最优化问题基本概念 许多研究的对象往往可以用一个图表示,研究的目的归结为图的极值问题。 运筹学中研究的图具有下列特征: (1) 用点表示研究对象,用连线(不带箭头的边或带箭头的弧)表示对象之间某种关系; (2) 强调点与点之间的关联关系,不讲究图的比例大小与形状; (3) 每条边上都赋有一个权,其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义; (4) 建立一个网络模型,求最大值或最小值。 5.1 网络最优化问题基本概念 5.1 网络最优化问题基本概念 (1)将某个点vi的物资或信息送到另一个点vj,使得运送成本最小。这属于最小费用流问题。 (2)将某个点vi的物资或信息送到另一个点vj,使得流量最大。这属于最大流问题。 (3)从某个点vi出发到达另一个点vj,怎样安排路线使得总距离最短或总费用最小。这属于最短路问题。 5.1 网络最优化问题基本概念 (4)点vi表示自来水厂及用户,vi与vj之间的边表示两点间可以铺设管道,权为vi与vj间铺设管道的距离或费用,极值问题是如何铺设管道,将自来水送到其他5个用户并且使总的费用最小。这属于最小支撑树问题。 (5) 售货员从某个点vi出发走过其他所有点后回到原点vi,如何安排路线使总路程最短。这属于货郎担问题或旅行售货员问题。 (6)邮递员从邮局vi出发要经过每一条边将邮件送到用户手中,最后回到邮局vi,如何安排路线使总路程最短。这属于中国邮递员问题。 5.1 网络最优化问题基本概念 网络最优化问题类型主要包括: (1)最小费用流问题; (2)最大流问题; (3)最短路问题; (4)最小支撑树问题; (5)货郎担问题和中国邮路问题,等等 5.2 最小费用流问题 最小费用流问题的模型在网络最优化中扮演着重要的角色,因为它的适用性很广,并且求解方法容易。通常最小费用流问题用于最优化货物从供应点到需求点的网络。目标是在通过网络配送货物时,以最小的成本满足需求,一种典型的应用就是使得配送网络的运营最优。 最小费用流问题的特殊类型包括运输问题和指派问题,以及在下面将要提到的两种重要类型:最大流问题和最短路问题。 5.2 最小费用流问题 例5.1 某公司有两个工厂生产产品,这些产品需要运送到两个仓库中。其配送网络图如图所示。目标是确定一个运输方案(即每条路线运送多少单位的产品),使通过配送网络的运输成本最小。 5.2 最小费用流问题 最小费用流问题的三个基本概念: 1、最小费用流问题的构成(网络表示) (1)节点:包括供应点、需求点和转运点; (2)弧:可行的运输线路(节点i->节点j),经常有最大流量(容量)的限制。 5.2 最小费用流问题 2、最小费用流问题的假设 (1)至少一个供应点; (2)至少一个需求点; (3)剩下都是转运点; (4)通过弧的流只允许沿着箭头方向流动,通过弧的最大流量取决于该弧的容量; (5)网络中有足够的弧提供足够容量,使得所有在供应点中产生的流都能够到达需求点;(有解) (6)在流的单位成本已知前提下,通过每一条弧的流的成本和流量成正比;(目标是线性的) (7)最小费用流问题的目标在满足给定需求条件下,使得通过网络供应的总成本最小(或总利润最大)。 5.2 最小费用流问题 3、最小费用流问题的解的特征 (1)具有可行解的特征:在以上的假设下,当且仅当供应点所提供的流量总和等于需求点所需要的流量总和时(即平衡条件),最小费用流问题有可行解; (2)具有整数解的特征:只要其所有的供应、需求和弧的容量都是整数值,那么任何最小费用流问题的可行解就一定有所有流量都是整数的最优解(与运输问题和指派问题的解一样)。因此,没有必要加上所有决策变量都是整数的约束条件。 5.2 最小费用流问题 最小费用流问题的数学模型为: (1)决策变量:设fij为通过弧(节点i->节点j)的流量。 (2)目标是通过网络供应的总成本最小。 (3)约束条件 ① 所有供应点:净流量(总流出减总流入)为正; ② 所有转运点:净流量为零; ③ 所有需求点:净流量为负; ④ 所有弧的流量fij受到弧的容量限制; ⑤ 所有弧的流量fij非负。 5.2 最小费用流问题 例5.1最小费用流问题的数学模型为: (1)决策变量:设fij为通过弧(节点i->节点j)的流量。 (2)目标函数 本问题的目标是总运输成本最小。 5.2 最小费用流问题 (3)约束条件(节点净流量、弧的容量限制、非负) ① 供应点 F1: 供应点 F2: ② 转运点 DC: ③ 需求点 W1: 需求点 W2: ④ 弧的容量限制: ⑤ 非负: 5.2 最小费用流问题 例5.1的电子表格模型:列出了网络中的弧和各弧所对应的容量、单位成本。决策变量为通过弧的流量。目标是计算流量的总成本。每个节点的净流量为约束条件。供应点的净流量为正,需求点的净流量为负,而转运点的净流量为0。 这里用了一个窍门:用两个SUMIF函数的差来计算每个节点的净流量,这样快捷且不容易犯错。 5.2 最小费用流问题 大规模的最小费用流问题的求解一般采用“网络单纯法(Network Simplex Method)”。现在,许多公司都使用网络单纯法来解决他们的最小费用流问题。有些问题是非常庞大的,有着数万个节点和弧。有时,弧的数量甚至可能会多得多,达到几百万条。但Excel的规划求解中没有网络单纯法,但其他的线性规划的商业软件包通常都有这种方法。 5.2 最小费用流问题 最小费用流问题有五种重要的特殊类型: (1)运输问题:有出发地(供应点-供应量)和目的地(需求点-需求量),没有转运点和弧的容量限制,目标是总运输成本最小(或总利润最大)。 (2)指派类型:出发地(供应点-供应量为1)是人,目的地(需求点-需求量为1)是任务,没有转运点和弧的容量限制,目标是总指派成本最小(或总利润最大)。 (3)转运问题:有出发地(供应点-供应量)和目的地(需求点-需求量),有转运点,但没有弧的容量限制(或有容量限制),目标是总流量费用最小(或总利润最大)。 5.2 最小费用流问题 最小费用流问题有五种重要的特殊类型(续): (4)最大流问题:有供应点、需求点、转运点、弧的容量限制,但没有供应量和需求量的限制,目标是通过网络到目的地的总流量最大。 (5)最短路问题:有供应点(供应量为1) 、需求点(需求量为1) 、转运点、没有弧的容量限制,目标是通过网络到目的地的总距离最短。 5.3 最大流问题 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流,城市给排水系统的水流问题等。而网络系统最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产中的实际问题起着十分重要的作用。 最大流问题也与网络中的流有关,但目标不是使得流的总成本最小,而是寻找一个流的方案,使得通过网络的流量最大。除了目标(流最大化和成本最小化)不一样外,最大流问题的特征和最小费用流问题的特征非常相似。 5.3 最大流问题 例5.2 某公司要从起始点vs(发点)运送货物到目的地vt(收点),其网络图如图所示。图中每条弧(节点i->节点j)旁边的权cij表示这段运输线路的最大通过能力(容量)。要求制定一个运输方案,使得从vs到vt的运货量达到最大,这个问题就是寻求网络系统的最大流问题。 5.3 最大流问题 5.3 最大流问题 例5.2最大流问题的线性规划数学模型: (1)决策变量 设fij为通过弧(节点i->节点j)的流量。 (2)目标函数 本问题的目标是从vs流出的总流量最大。 (3)约束条件(转运点的净流量为0、弧的容量限制、非负) 5.3 最大流问题 例5.2最大流问题电子表格模型 5.3 最大流问题 最大流问题的一些实际应用: (1)通过配送网络的流量最大,如例5.2和例5.3; (2)通过管道运输系统的油的流量最大; (3)通过输水系统的水的流量最大; (4)通过交通网络的车辆的流量最大;等等。 5.3 最大流问题 例5.3 计划编制问题。某市政工程公司在未来5~8月份内需完成4项工程:修建一条地下通道、修建一座人行天桥、新建一条道路及道路维修。工期和所需劳动力见表5-1。该公司共有劳动力120人,任一工程在一个月内的劳动力投入不能超过80人,问公司应如何分配劳动力完成所有工程,是否能按期完成? 5.3 最大流问题 本问题除了可以用第3章介绍的线性规划方法来求解(可设xij为工程i在j月投入的劳动力)外,还可以用最大流的方法来求解。 将工程计划用网络图表示。图中的节点5、6、7、8分别表示5~8月份,Ai、Bi、Ci、Di表示工程在第i个月内完成的部分。用弧表示某月完成某项工程的状态,弧的流量为所投入的劳动力,受到劳动力限制(弧旁边的数字表示弧的容量,从S开始的弧,其容量为该公司共有劳动力120人;从节点5、6、7、8开始的弧以及到节点A、B、C、D的弧,其容量为任一工程在一个月内的劳动力投入不能超过80人;到收点T的弧,其容量为每个工程所需劳动力)。合理安排每个月各工程的劳动力,在不超过现有人力的条件下,尽可能保证工程按期完成,就是求图从发点到收点的最大流问题。 5.3 最大流问题 5.4 最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型,如设备更新、管道铺设、线路安排、厂区布局等 最短路问题的最普遍的应用是在两个点之间寻找最短路,是最小费用流问题的一种特殊类型:源的供应量为1 、目的地(需求点)的需求量为1 、转运点的净流量为0、没有弧的容量限制,目标:通过网络到目的地的总距离最短。 5.4 最短路问题 例5.4 某人每天从住处v1开车到工作地v7上班,图中各弧旁的数字表示道路的长度(公里),试问该人应选择哪条路线,从家出发到工作地,路上行驶的总距离最短。 5.4 最短路问题 解:这是一个最短路问题。其数学模型为: (1)决策变量:设xij为弧(节点i->节点j)是否走(1表示走,0表示不走)。 (2)目标函数 本问题的目标是总距离最短。 (3)约束条件(节点净流量、非负)略。 5.4 最短路问题 例5.6的最短路问题的电子表格模型 5.4 最短路问题 最短路问题的应用很广,如设备更新、管道铺设、线路安排、厂区布局等。 下面举两个例子: (1)设备更新问题; (2)新产品开发时间问题。 5.4 最短路问题 例5.5 设备更新问题。某工厂的某台机器可连续工作4年,决策者每年年初都要决定机器是否需要更新。若购置新机器,就要支付购置费用;若继续使用,则需要支付维修与运行费用,而且随着机器使用的年限费用逐年增多。已知计划期(4年)中每年的购置价格及维修与运行费用。试制定今后4年的机器更新计划,使总的支付费用最少。 5.4 最短路问题 解:把该问题看作最短路问题。 设节点1和节点5表示计划期的始点和终点(节点5可以理解为第4年末)。图中各弧(i,j)表示第i年初购进的机器使用到j年初(即j-1年底),弧旁的数字由表中的数据计算得到。 弧长=购置价格+使用多年的维修与运行总费用 例如,考虑从节点1到节点3的弧,这条弧对应的是在第1年初购进的机器,使用到3年初(即使用了2年),所以 从①到③的弧长=2.5+1+1.5=5(万元) 5.4 最短路问题 例5.5 设备更新问题的网络模型 因此,把求最优的设备更新问题转化为求节点1到节点5的最短路问题 5.4 最短路问题 例5.7的电子表格模型 5.5 最小支撑树问题 许多网络问题可以归结为最小支撑树问题。例如,设计长度最小的公路网把若干城市(乡村)联系起来;设计用料最省的电话线网(光纤)把有关单位联系起来,等等。这种问题的目标是设计网络。虽然节点已经给出,但必须决定在网络中要加入哪些边。特别地,向网络中插入的每一条可能的边都有成本。为了使得每两个节点之间形成路,需要提供足够的边。目标就是以某种方法完成网络设计,使得边的总成本最小。这种问题称为最小支撑树问题。 5.5 最小支撑树问题 例5.9 某公司铺设光导纤维网络问题。 某公司的管理层已经决定铺设最先进的光导纤维网络,为它的主要中心之间提供高速通信(数据、声音和图像)。图5-20(下一张幻灯片)中的节点显示了该公司主要中心(包括公司的总部、巨型计算机、研究区、生产和配送中心等)的分布图。虚线是铺设纤维光缆可能的位置。每条虚线旁边的数字表示了如果选择在这个位置铺设光缆需要花费的成本。 为了充分利用光纤技术在中心之间高速通信的优势,不需要在每两个中心之间都用一条光缆把它们直接连接起来。现在的问题就是要确定需要铺设哪些光缆使得提供给每两个中心之间的高速通信的总成本最低。实际上,这就是一个最小支撑树问题。 5.5 最小支撑树问题 5.5 最小支撑树问题 通过“贪婪算法”来求解。 求解最小支撑树问题的贪婪算法有很多。比如,Kruskal算法,其步骤如下: (1)选择第一条边:选择成本最低的备选边; (2)选择下一条边:从剩下的边中取一条边满足:(a)最小边;(b)不构成圈; (3)重复第(2)步骤,直到选取的边数为节点数-1。此时就得到了最优解(最小支撑树)。 处理成本相同的边:当有几条边同时是成本最低的边时,任意选择一条边不会影响最后的最优解。 5.6 货郎担问题和中国邮路问题 一个推销员从n个城市中的某个城市出发,到其他n-1个城市推销货物,每个城市都必须访问并且只访问一次,最后回到出发地,如何安排他的行走路线使总距离最短,这就是货郎担问题或旅行售货员问题。 5.6 货郎担问题和中国邮路问题 例5.6 某电动汽车公司和学校合作,拟定在校园内开通无污染无噪音的“绿色交通”路线。图5-23是教学楼和学生宿舍楼的分布图,边上的数字为汽车通过两点间的正常时间(分钟)。电动汽车公司应如何设计一条行驶路线,使汽车通过每一处教学楼和宿舍楼一次后总时间最少。 5.6 货郎担问题和中国邮路问题 对于货郎担问题,也是将边看成长度相等方向相反的两条弧,其线性规划模型略。 用Excel求解货郎担问题的想法来源于用Excel求解最短路问题,但要修改。由于在最短路问题中,有些节点可以不经过,但在货郎担问题中要求每个节点都要恰好经过一次,所以约束条件改为将每个节点的总流入和总流出分开。也就是说,每个节点有两个约束(总流入=1和总流出=1),而非最短路问题的一个净流量约束。改进后的Excel方法,有时可以得到只有一个大回路的最优解(此时求解结束),但经常会得到有几个小回路的解,此时就应该再增加去掉小回路的约束。 5.6 货郎担问题和中国邮路问题 解:对于例子5.6,第一步:将每个节点的总流入和总流出分开,电子表格模型如图所示。Excel求解结果为:A<->D、B<->C、E<->F,也就是说,分成3个小的回路。此时的总时间为13.2分钟。 5.6 货郎担问题和中国邮路问题 第二步:去掉第一步的3个小回路。在图的基础上,增加这3对节点(教学楼和学生宿舍楼)不能有回路的约束,电子表格模型如图所示。Excel求解结果为:A->C->B->E->F->D->A,也就是说,求得一个大回路,此时求解结束。如果还存在有3个节点或3个节点以上的小回路,还需增加新的约束,去掉小回路。 5.6 货郎担问题和中国邮路问题 一个邮递员从邮局出发,将邮件投递到他管辖的所有街道,最后回到邮局,如何安排他的行驶路线,使总路长最短。这个问题由我国数学家管梅谷教授于1962年首先提出来的,因此称为“中国邮路问题”。 货郎担问题与中国邮路问题的不同之处是前者要遍历图的所有节点,后者要遍历图的所有边。 5.6 货郎担问题和中国邮路问题 管梅谷教授还给出了求解“中国邮路问题”的“奇偶点图上作业法”。这种解法通过添加重复边(重复边就是邮递员重复经过的街道),将所有奇点变为偶点。但所添加的重复边要满足下列两个条件:(1)每条边最多重复一次;(2)所有回路中重复边长之和不超过回路边长之和的一半。 在用“奇偶点图上作业法”求解“中国邮路问题”时,需检查图中的每一条回路。当图中回路较多时,检查不便且容易出错。对此,受求解最短路问题的Excel解法的启发,作者给出了求解“中国邮路问题”的Excel解法。 5.6 货郎担问题和中国邮路问题 例5.7 在图中,v1是邮局所在地。请帮邮递员设计一条投递线路(从邮局出发,将邮件投递到他管辖的所有街道,最后回到邮局),使总路长最短。 5.6 货郎担问题和中国邮路问题 解:例5.7属于求无向图上的中国邮路问题。在无向图中,把每一条边看成是长度相等、方向互反的两条弧。 例5.7的Excel电子表格模型: 5.6 货郎担问题和中国邮路问题 Excel的求解结果为:添加所需的4条重复弧: 并求解出一条最优邮递路线: 此时的最短总距离为68

最优化理论与算法ppt:这是最优化理论与算法ppt,包括了最优化问题,泰勒级数问题,方向导数与极值问题,凸集、凸函数与凸优化问题,算法概述等内容,欢迎点击下载。

蚁群优化算法ppt:这是蚁群优化算法ppt,包括了基本概念及原理,数学模型与算法流程,研究现状及进展,算法优缺点及应用等内容,欢迎点击下载。

ppt资源优化:这是ppt资源优化,包括了目前ERP系统存在的两大问题,统一的企业模型,新的企业经营管理系统,企业资源优化问题的重要性,企业资源优化要解决的问题,企业资源优化的问题的复杂性,实现企业资源优化的途径,MRP逻辑的主要问题等内容,欢迎点击下载。

推荐PPT

PPT分类Classification

Copyright:2009-2015 rsdown.cn Corporation,All Rights Reserved 红软PPT免费下载网版权所有

粤ICP备14102101号