运筹与优化
——我的认知
黄德志
（上海大学文学院“运筹与优化”第三组11123850）
摘要：运筹学是一门现代科学，作为一门用来解决实际问题的学科，发展至今天已经有诸多的分支。其中，网络规划是其重要的一支分支，确立目标，制定方案，建立模型，制定解法一般是处理网络规划问题的四部曲，模型、案例、解法是迈进网络规划知识殿堂的三个重要关口。下面，我将选取运筹学中的重要分支之一——网络规划为例来带领大家进入运筹学的丰富世界，并通过模型、案例和求解三方面展开分析网络规划包含的最短路、最小费用流和最大流等问题，并列举几种相关的求解方法加以分析。网络规划无论是在市场销售、生产计划、库存管理还是在运输问题、设备维修更新、工程的最佳化设计等方面都有广泛的应用，其在政治、经济、社会、民生等方面发挥的作用越来越大。
关键词：网络规划、模型、案例、求解
1引言
在展开分析网络规划包含的最短路、最小费用流和最大流等具体问题前，我们先得理解网络规划的一些基本概念和特征。
（1）网络规划含有七个最基本概念，它们分别是：
1）图：由点和边组成的集合。常记为：G=(V,E)；其中：V={v1,v2,…,vn}表示点的集合,E={e1,e2,…,em}表示边的集合。如下图2.1-1为无向图，图2.1-2为有向图。
图2.1—1 无向图图2.1-2 有向图
2）网络:带有某种数量指标的图(即:赋权图)称为网络如下图2.1-3为无向网络，图2.1-4为有向网络。
图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,e7,v5}为路；{v3,e5,v4,e6,v5,e8,v3}为回路。
6）连通图:图中任意两点间至少有一条链相连，称此图为连通图。如图2.1-7、图2.1-8。 7）网络模型:对所关心的问题确定研究对象以及这些对象之间某种性质的联系，并用网络图及其图解的形式表示出来，这就是对问题建立网络模型。
（2）网络基本特征：
1）三要素——点、边、权。
2）一般将研究“对象”作为“点”，“对象”之间关系作为“边”，“对象”之间关系程度作为“权”
2 我的认知
2.1 认知一——网络规划模型
网络规划包括最短路、最小费用流和最大流等经典模型。下面，我们分别来认识这些模型。
1、最短路
最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。我们以下面这个问题为例来说明:
某企业拟铺设一条从A地到F地的输油管道，可供选择路线及各点间的距离如下图2.3-1 ；试问：应如何选择路线使总距离最短？
图2.3-1 A地到F地可供选择路线
从上面的网状图中可以看出来，该问题的求解就是对最短路问题的求解，以获得A地到
F地的最短总距离。
再来看下面的一个设备更新问题，这是一个由矩阵图呈现出来的最短路问题。
某公司拟对一台设备制定5年期的设备更新计划使总的支付费用最少。相关信息如下表2.3-1 ：
表2.3-1 设备更新相关信息
下面这个问题也是最短路问题：①
要求设计一个能够计算图1 中任意两个院校间最短路距的查询器。要求系统应具备较好的纠错与自动计算等功能。
图1 院校距离图
该问题可简化为如图2 所示的有向图。
节点①：表示知行学院；
节点②：表示政法学院；
节点③：表示师范大学；
节点④：表示交通大学；
⑤、⑹、⑦为计算需要所附加的节点；
节点⑧：表示城市学院；
节点⑨：表示农业大学。
图2 院校距离有向图
3、最小费用流
最小费用流问题应满足如下条件: 至少有一个节点是供应点；至少有一个节点是需求点；所有剩下的点都是转运点；网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到达需求点;；通过每一条弧的流的成本与流量成正比。下面就以一个资金运作管理中最小费用流问题为例：②
例：美国某资金运作公司现储备日元12 亿，卢比105 亿，林吉特280 万。由于日本的经济危机波及东亚其他国家金融市场，导致上述三种货币的贬值，公司决定将上述三种货币全部兑换成美元。下面分别给出货币实时汇率、交易成本及交易限制的三份表格。问：如何交易可使交易后美元数额最大？
再来看下面这个问题：
一物流公司有大宗的业务是向安徽淮南矿业集团的各个矿运送井下物资和原材料(主要是井下支护用的锚杆和锚固剂)。淮南市里有三家合成材料厂(国营原隶属淮南矿业集团的一家, 另外两家比较小, 是跳槽私人单干的)生产同一种锚固剂, 日产量分别为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 工厂到各矿的每吨单位运费
我们现在来对这个问题展开分析，这个问题的特点如下:
目标明确。作为物流企业, 经营总目标是明确的, 即寻求某个整体目标最优——运费最低;
多种方案。可以从多种供选择的运输方案中选取最佳方案;
资源有限。运输决策必须受到限制, 如锚固剂的调运既要满足各个矿的井下生产需要量, 又不能超过各合成材料厂所能提供的锚固剂的生产量。
线性关系。约束条件及目标函数均保持线性关系。
正是因为具有以上特点, 公司的锚固剂运输问题, 可以归为线性规划问题。从数学模型上概括起来, 可以认为, 是求一组非负的变量即运费, X 1、X 2、X 3、X 4、X 5、∀、X 18 , 在一组线性等式或线性不等式的约束条件下, 使得目标总运费最小。解决这样一个线性规划问题的数学模型有以下共同特征:
存在一组变量X 1、X 2、X 3、∀、X 18 , 成为决策变量, 表示某一运输决策。这些变量的取值是非负的;
存在两个约束条件, 3 个工厂的实际生产能力和6个矿的实际需要量。可以用两组线性不等式来描述;
存在一个线性目标函数，实际总运费最小。③
4、最大流
网络最大流问题是网络问题中的一类经典问题，对于这类问题，可以根据题意建立线性规划模型，运用运筹学软件求解，也可以用网络图论法求解。我们通过下列例子来认识最大流模型:④
例题:某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点。这个网络的一部分如图1 所示，由于管道的直径的变化，它的各段管道（Vi,Vj）的流量（容量）Cij 也是不一样的，这在图中已标出。Cij 的单位为万加仑小时。如果使用这个网络系统从采地V1 向销地V7 运送石油，问每小时能运送多少加仑石油？
