运筹及优化课程论文

1、运筹与优化我的认知黄德志（上海大学 文学院“运筹与优化”第三组 11123850）摘要：运筹学是一门现代科学，作为一门用来解决实际问题的学科，发展至今天已经有诸多的分支。其中，网络规划是其重要的一支分支，确立目标，制定方案，建立模型，制定解法一般是处理网络规划问题的四部曲，模型、案例、解法是迈进网络规划知识殿堂的三个重要关口。下面，我将选取运筹学中的重要分支之一网络规划为例来带领大家进入运筹学的丰富世界，并通过模型、案例和求解三方面展开分析网络规划包含的最短路、最小费用流和最大流等问题，并列举几种相关的求解方法加以分析。网络规划无论是在市场销售、生产计划、库存管理还是在运输问题、设备维修更新、

2、工程的最佳化设计等方面都有广泛的应用，其在政治、经济、社会、民生等方面发挥的作用越来越大。关键词：网络规划、模型、案例、求解1引言在展开分析网络规划包含的最短路、最小费用流和最大流等具体问题前，我们先得理解网络规划的一些基本概念和特征。（1）网络规划含有七个最基本概念，它们分别是：1）图：由点和边组成的集合。 常记为：G=(V,E)；其中：V=v1,v2,vn表示点的集合,E=e1,e2,em表示边的集合。如下图2.1-1为无向图，图2.1-2为有向图。 图2.11 无向图 图2.1-2 有向图 2）网络:带有某种数量指标的图(即:赋权图)称为网络如下图2.1-3为无向网络，图2.1-4为有向

3、网络。 图2.1-3 无向网络 图2.1-4 有向网络 3) 链:无向图G=(V,E)中与边依次交替出现的序列vi0,ei1,vi1,ei2,vi2,vik-1,eik,vik, 且eit=(vit-1,vit),t=1,k，则称这个点边序列为连接vi0到vik的一条链，链长为k。 4）圈:链vi0,ei1,vi1,ei2,vi2,vik-1,eik,vik中当vi0=vik时, 该链称为圈。如下图2.1-7中v1,e1,v2,e3,v3,e2,v1为圈 图2.1-7 链 图2.1-8 路5）路:有向图中当链(圈)上的边方向相同时,称为路(回路)。如图2.1-8中v1,e3,v4,e4,v2,

4、e7,v5为路； v3,e5,v4,e6,v5,e8,v3为回路。 6）连通图:图中任意两点间至少有一条链相连，称此图为连通图。如图2.1-7、图2.1-8。 7）网络模型:对所关心的问题确定研究对象以及这些对象之间某种性质的联系，并用网络图及其图解的形式表示出来，这就是对问题建立网络模型。（2）网络基本特征：1）三要素点、边、权。2）一般将研究“对象”作为“点”，“对象”之间关系作为“边”，“对象”之间关系程度作为“权” 2 我的认知2.1 认知一网络规划模型 网络规划包括最短路、最小费用流和最大流等经典模型。下面，我们分别来认识这些模型。 1、最短路最短路问题，就是从给定的网络图中找出一点

5、到各点或任意两点之间距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。我们以下面这个问题为例来说明:某企业拟铺设一条从A地到F地的输油管道，可供选择路线及各点间的距离如下图2.3-1 ；试问：应如何选择路线使总距离最短？ 图2.3-1 A地到F地可供选择路线从上面的网状图中可以看出来，该问题的求解就是对最短路问题的求解，以获得A地到F地的最短总距离。再来看下面的一个设备更新问题，这是一个由矩阵图呈现出来的最短路问题。某公司拟对一台设备制定5年期的设备更新计划使总的支付费用最少。相

6、关信息如下表2.3-1 ： 表2.3-1 设备更新相关信息下面这个问题也是最短路问题：要求设计一个能够计算图1 中任意两个院校间最短路距的查询器。要求系统应具备较好的纠错与自动计算等功能。 图1 院校距离图该问题可简化为如图2 所示的有向图。节点：表示知行学院；节点：表示政法学院；节点：表示师范大学；节点：表示交通大学；、为计算需要所附加的节点；节点：表示城市学院；节点：表示农业大学。 图2 院校距离有向图3、最小费用流最小费用流问题应满足如下条件: 至少有一个节点是供应点； 至少有一个节点是需求点； 所有剩下的点都是转运点； 网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到

7、达需求点;；通过每一条弧的流的成本与流量成正比。下面就以一个资金运作管理中最小费用流问题为例：例：美国某资金运作公司现储备日元12 亿，卢比105 亿，林吉特280 万。由于日本的经济危机波及东亚其他国家金融市场，导致上述三种货币的贬值，公司决定将上述三种货币全部兑换成美元。下面分别给出货币实时汇率、交易成本及交易限制的三份表格。问：如何交易可使交易后美元数额最大？ 再来看下面这个问题：一物流公司有大宗的业务是向安徽淮南矿业集团的各个矿运送井下物资和原材料(主要是井下支护用的锚杆和锚固剂)。淮南市里有三家合成材料厂(国营原隶属淮南矿业集团的一家, 另外两家比较小, 是跳槽私人单干的)生产同一种

8、锚固剂, 日产量分别为800 t、220 t、380 ;t 有六个矿(谢一、张集、潘一、潘二、潘三、顾桥)是公司的长期客户。他们的日需求量分别为200 t、350 t、100 t、150 t、200 t、400 t。把这三家企业设为A1、A2、A3 , 把六个矿设为B 1、B 2、B3、B4、B5、B 6 。每个工厂到各矿的单位运费(元/ t)如表1所示。 表1 工厂到各矿的每吨单位运费 我们现在来对这个问题展开分析，这个问题的特点如下:目标明确。作为物流企业, 经营总目标是明确的, 即寻求某个整体目标最优运费最低;多种方案。可以从多种供选择的运输方案中选取最佳方案;资源有限。运输决策必须受到

9、限制, 如锚固剂的调运既要满足各个矿的井下生产需要量, 又不能超过各合成材料厂所能提供的锚固剂的生产量。线性关系。约束条件及目标函数均保持线性关系。正是因为具有以上特点, 公司的锚固剂运输问题, 可以归为线性规划问题。从数学模型上概括起来, 可以认为, 是求一组非负的变量即运费, X 1、X 2、X 3、X 4、X 5、X 18 , 在一组线性等式或线性不等式的约束条件下, 使得目标总运费最小。解决这样一个线性规划问题的数学模型有以下共同特征:存在一组变量X 1、X 2、X 3、X 18 , 成为决策变量, 表示某一运输决策。这些变量的取值是非负的;存在两个约束条件, 3 个工厂的实际生产能力

10、和6个矿的实际需要量。可以用两组线性不等式来描述;存在一个线性目标函数， 实际总运费最小。 4、最大流网络最大流问题是网络问题中的一类经典问题，对于这类问题，可以根据题意建立线性规划模型，运用运筹学软件求解，也可以用网络图论法求解。我们通过下列例子来认识最大流模型:例题:某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点。这个网络的一部分如图1 所示，由于管道的直径的变化，它的各段管道（Vi,Vj）的流量（容量）Cij 也是不一样的，这在图中已标出。Cij 的单位为万加仑小时。如果使用这个网络系统从采地V1 向销地V7 运送石油，问每小时能运送多少加仑石油？ 图1 管道网

11、络解这类题目的根本方法是线性规划法，即根据已知条件列出目标函数与约束方程求解。根据题意可知：设弧（Vi,Vj）上的流量为fij,网络上的总的流量为F ，则有Max F=f12+f14;约束条件：f12=f23+f25,f14=f43+f46+f47, f23+f43=f35+f36,f25+f35=f57,f36+f46=f67,f57+f67+f47=f12+f14,fij<=cij，fij>=0 (i=1,2,6；j=2,7). 由此可得，f12=5,f14=5,f23=25,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3.最优值

12、（最大流）为10。由图可知，此系统的最大流量值为10 。此时，V25=3，V35=2，V36=2，V46=1，V47=2，与线性规划方法所的解相同。此例题中，各节点的级别可按方便情况划分，尽量使水流从低级流向高级。但是不排除另外一种情况的存在，即出现级间“逆流”，例如我们把V 4 、V 3 级位颠倒，就出现水流从第三级流到第二级的情况，我们来推导更一般的方法，如图3 。由于我们求的是最大流问题，所以不用考虑逆流情况，可视其为0，所得结果与前面所解一致。综上，我们可以得到这种解法的一般步骤：1 、按照流量从低级流向高级的原则将不同节点划分为不同等级，不宜划分者，可以按标号由小到大的顺序排列成由低

13、到高。2 、按原题意标画出各个支路及流量，逆流可忽略。3、每两个相邻级之间画一道竖线，将与竖线交叉的支路上所有正流量相加，标记于竖线下方。比较各竖线下方标值，则其中最小值即为该网络最大流量。 图32.2 认知二网络规划案例1、最短路案例例1：给定一个运输网络（如图1所示），两点之间连线上的数字表示两点间的距离，求从A到E 的运输线路，使总距离最短。 图1 点与点距离图例2：电信公司准备在甲、乙两地沿路架设一条光缆线，如何架设使其光缆线路最短？（甲、乙两地间的交通图如图2所示）图2 甲乙两地间交通图3、最小费用流南方陶瓷公司销售陶瓷用品。有五个陶瓷供应地: A 1,A 2,A 3,A 4,A 5

14、。拟建立三个销售点: B 1,B 2,B 3。各供应地的陶瓷日可供量及单位商品供应价(即单位进价成本) 如表1。各销售点的陶瓷日最高需求量及销售单位商品三项费用(经营费用、管理费用、财务费用) 如表2。有关交通道路网如图2, 其弧旁数字为(bij ,Cij ) , 即(单位商品运输途中经营费用, 路段流通能力)。问:1、 公司应如何组织采购、运输、销售, 在满足供应地可供量, 道路流通能力及销售点需求量的前提下,使公司的购运销总费用最低?2、 若销售点B 2, 因市场情况变化, 引起该处单位商品销售三项费用从110 提高到115。公司的购运销方案有否变动? 如何变动? 表1 和 表2 图2 有

15、关交通道路网4、最大流图1为某交通管理部门所管制的路网，s为所管制的路网的起点，t为所管制的路网的终点，一般情形下，交通管理部门会按最大流原则分配流量。然而在现实情况下，交通管理部门事前无法知道哪一条路段会由于交通事故（或其他突发事件）而突然堵塞（或中断），而一旦出现堵塞，车辆就需要绕路。假如在某一时间段内只发生一次突然堵塞，那么该如何确定关键路段，加强管制，以使道路突然中断时最大可能减少路网效率损失？ 图1 路网图2.3 认知三网络规划求解1、最短路问题求解（1）穷举法：1）适用于路不多的简单问题；2）求出每条路长，比较各条路长求一路长最短的路。 例2.3-3:求如下网络图2.3-2中点1到

16、点6最短路。 图 2.3-2 网络图解题步骤如下图2.3-3： 图 2.3-3 解题步骤图序号 路 路长 最短路1 1-2-4-6 162 1-2-4-5-6 23 3 1-3-5-6 174 1-3-2-4-5-6 225 1-3-2-4-6 15 1-3-2-4-6 （2）标号法：例2.3-4：以例2.3-1为例，解题步骤如下图2.3-4 图 2.3-4 解题步骤根据解题步骤图可知最短路为：AB1C2D2E2F；路长为：173、最小费用流问题求解对于最小费用流的求解，我们以案例中的南方陶瓷公司的这个问题的第一问来说明：求解步骤：(一) 设S 点为总源, T 点为总汇, 根据所给资料建立相应

17、的网络如图3。 图3(二) 从零流f0始寻求最大流f3可先后取增广链L1= (S ,A 1,B 1, T ) L2= (S ,A 2, C1,B 1, T ) L3= (S ,A 2,B 2, T )L4= (S ,A 3,B 2, T ) L5= (S ,A 3, C3, C2,B 1, T )L6= (S ,A 4, C3, C2,B 1, T )L7= (S ,A 5,B 3, T ) L8= (S ,A 5, C2,B 1, T ) 分别对应得行流f 1, f 2, , f 8, 网络流流量不断增加: V (f 0) = 0,V (f 1) = 4, V (f 2) = 7,V (f

18、3) = 9, V (f 4) = 12, V (f 5)= 15, V (f 6) = 16, V (f 7) = 20, V (f 8) = 21, 对于可行流f 8 已不存在从S 到T 的增广链。因此, 已得网络最大流, 其流量分配图如图4 所示。弧旁数字为(bij ,f ij , C ij )。 图4(三) 从最大流f3，求最小费用最大流f3 3 1、在图4 中对於圈L 1= (C1, B 1, T ,B 2, C1) 上的所有弧按顺、逆时方向剖分为两弧组:L e = (C1,B 1, (B 1, T ) L s = (C1,B 2) , (B 2, T ) 其中L e 的费用大(W

19、e= 19+ 110= 129) , L s 的费用小(W s= 16+ 110= 126) 且弧组L e 均为非零弧, 弧组L s均为非饱和弧, 从而圈L 1 为可降圈。取H= m in f3C1,B 1 , f3B 1, T , CC1,B 2 f3C1,B 2 , CB 2, T f3B 2, T = m in 3, 12, 6 - 0, 9 - 5 = 3令f3C1,1B 1 = f3C1,B 1 - = 0 f3C1,1T = f3C1,T -= 9 f3C1,1B 2 = f3C1,B 2 += 3 f3C1,1T = f3C1,T -= 9于是得到总费用较f3少(129- 126

20、) ×3= 9 的最大流f31 , 其对应的流量分配图如图5 所示。 图5南方陶瓷公司按最佳方案组织采购、运输、销售陶瓷, 总费用可达最低。其值为:151 × 4 + 188 × 2 + 167 × 3 + 152 × 3 + 222 × 3 + 226 × 1 + 204 × 1 + 156 × 4 = 36574、最大流问题求解计算网络最大流所采用的算法分为3种: Ford2Fulkerson标号法、辅助图最短路算法和割集矩阵算法。前两种是传统算法， Ford2Fulkerson算法通过节点标号法寻找增广路,确定增加的流量。此算法计算过程繁琐,不适合大规模编程。辅助图最短路算法利用最短路与最小割集具有对偶性的特性,通过计算最短路得到最小割,但是求解最短路的过程较复杂。割集矩阵算法不仅能快速求解复杂网络最大流,而且能方便地找出网络的关键路段,在运输网络分析方面比前两种算法更实用。对于此三种算法，第一种Ford2Fulkerson标号法是最为常见的对最大流问题的求解方法，具体求解案例这里就不做详细展示了。3 结论 运筹与优化是紧密而又不可分的，运筹学的世界是宏大而丰富的，网络规划只是其分支之一。从现在到未来，运筹学都有着广阔的应用领域，它已渗透到诸如服务、经济、库存、搜索、人口、