运筹与优化课程论文Word下载.docx

运筹与优化课程论文Word下载.docx

《运筹与优化课程论文Word下载.docx》由会员分享，可在线阅读，更多相关《运筹与优化课程论文Word下载.docx（13页珍藏版）》请在冰点文库上搜索。

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-1A地到F地可供选择路线

从上面的网状图中可以看出来，该问题的求解就是对最短路问题的求解，以获得A地到F地的最短总距离。

再来看下面的一个设备更新问题，这是一个由矩阵图呈现出来的最短路问题。

某公司拟对一台设备制定5年期的设备更新计划使总的支付费用最少。

相关信息如下表2.3-1：

表2.3-1设备更新相关信息

下面这个问题也是最短路问题：

①

要求设计一个能够计算图1中任意两个院校间最短路距的查询器。

要求系统应具备较好的纠错与自动计算等功能。

图1院校距离图

该问题可简化为如图2所示的有向图。

节点①：

表示知行学院；

节点②：

表示政法学院；

节点③：

表示师范大学；

节点④：

表示交通大学；

⑤、⑹、⑦为计算需要所附加的节点；

节点⑧：

表示城市学院；

节点⑨：

表示农业大学。

图2院校距离有向图

3、最小费用流

最小费用流问题应满足如下条件:

至少有一个节点是供应点；

至少有一个节点是需求

点；

所有剩下的点都是转运点；

网络中有足够的弧提供足够的容量，使得所有在供应点中产生的流都能够到达需求点;

；

通过每一条弧的流的成本与流量成正比。

下面就以一个资金运作管理中最小费用流问题为例：

②

例：

美国某资金运作公司现储备日元12亿，卢比105亿，林吉特280万。

由于日本的经济危机波及东亚其他国家金融市场，导致上述三种货币的贬值，公司决定将上述三种货币全部兑换成美元。

下面分别给出货币实时汇率、交易成本及交易限制的三份表格。

问：

如何交易可使交易后美元数额最大？

再来看下面这个问题：

一物流公司有大宗的业务是向安徽淮南矿业集团的各个矿运送井下物资和原材料（主要

是井下支护用的锚杆和锚固剂）。

淮南市里有三家合成材料厂（国营原隶属淮南矿业集团的一家,另外两家比较小,是跳槽私人单干的）生产同一种锚固剂,日产量分别为800t、220t、380;

t有六个矿（谢一、张集、潘一、潘二、潘三、顾桥）是公司的长期客户。

他们的日需求量分别为200t、350t、100t、150t、200t、400t。

把这三家企业设为A1、A2、A3,把六个矿设为B1、B2、B3、B4、B5、B6。

每个工厂到各矿的单位运费（元/t）如表1所示。

表1工厂到各矿的每吨单位运费

我们现在来对这个问题展开分析，这个问题的特点如下:

目标明确。

作为物流企业,经营总目标是明确的,即寻求某个整体目标最优——运费最

低;

多种方案。

可以从多种供选择的运输方案中选取最佳方案;

资源有限。

运输决策必须受到限制,如锚固剂的调运既要满足各个矿的井下生产需要量,又不能超过各合成材料厂所能提供的锚固剂的生产量。

线性关系。

约束条件及目标函数均保持线性关系。

正是因为具有以上特点,公司的锚固剂运输问题,可以归为线性规划问题。

从数学模型上概括起来,可以认为,是求一组非负的变量即运费,X1、X2、X3、X4、X5、∀、X18,在一组线性等式或线性不等式的约束条件下,使得目标总运费最小。

解决这样一个线性规划问题的数学模型有以下共同特征:

存在一组变量X1、X2、X3、∀、X18,成为决策变量,表示某一运输决策。

这些变

量的取值是非负的;

存在两个约束条件,3个工厂的实际生产能力和6个矿的实际需要量。

可以用两组线性

不等式来描述;

存在一个线性目标函数，实际总运费最小。

③

4、最大流

网络最大流问题是网络问题中的一类经典问题，对于这类问题，可以根据题意建立线性规划模型，运用运筹学软件求解，也可以用网络图论法求解。

我们通过下列例子来认识最大流模型:

④

例题:

某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点。

这个网络的一部分如图1所示，由于管道的直径的变化，它的各段管道（Vi,Vj）的流量（容量）Cij也是不一样的，这在图中已标出。

Cij的单位为万加仑小时。

如果使用这个网络系统从采地V1向销地V7运送石油，问每小时能运送多少加仑石油？

图1管道网络

解这类题目的根本方法是线性规划法，即根据已知条件列出目标函数与约束方程求解。

根据题意可知：

设弧（Vi,Vj）上的流量为fij,网络上的总的流量为F，则有

MaxF=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.最优值（最大流）为10。

由图可知，此系统的最大流量值为10。

此时，V25=3，V35=2，V36=2，

V46=1，V47=2，与线性规划方法所的解相同。

此例题中，各节点的级别可按方便情况划分，尽量使水流从低级流向高级。

但是不排除另外一种情况的存在，即出现级间“逆流”，例如我们把V4、V3级位颠倒，就出现水流从第三级流到第二级的情况，我们来推导更一般的方法，如图3。

由于我们求的是最大流问题，所以不用考虑逆流情况，可视其为0，所得结果与前面所解一致。

综上，我们可以得到这种解法的一般步骤：

1、按照流量从低级流向高级的原则将不同节点划分为不同等级，不宜划分者，可以按标号由小到大的顺序排列成由低到高。

2、按原题意标画出各个支路及流量，逆流可忽略。

3、每两个相邻级之间画一道竖线，将与竖线交叉的支路上所有正流量相加，标

记于竖线下方。

比较各竖线下方标值，则其中最小值即为该网络最大流量。

图3

2.2认知二——网络规划案例

1、最短路案例

例1：

给定一个运输网络（如图1所示），两点之间连线上的数字表示两点间的距离，求从A到E的运输线路，使总距离最短。

图1点与点距离图

例2：

电信公司准备在甲、乙两地沿路架设一条光缆线，如何架设使其光缆线路最短？

（甲、乙两地间的交通图如图2所示）⑤

图2甲乙两地间交通图

南方陶瓷公司销售陶瓷用品。

有五个陶瓷供应地:

A1,A2,A3,A4,A5。

拟建立三个销售点:

B1,B2,B3。

各供应地的陶瓷日可供量及单位商品供应价（即单位进价成本）如表1。

各销售点的陶瓷日最高需求量及销售单位商品三项费用（经营费用、管理费用、财务费用）如表2。

有关交通道路网如图2,其弧旁数字为（bij,Cij）,即（单位商品运输途中经营费用,路段流通能力）。

问:

1、公司应如何组织采购、运输、销售,在满足供应地可供量,道路流通能力及销售点需求量的前提下,使公司的购运销总费用最低?

2、若销售点B2,因市场情况变化,引起该处单位商品销售三项费用从110提高到115。

公司的购运销方案有否变动?

如何变动?

⑥

表1和表2

图2有关交通道路网

4、最大流

图1为某交通管理部门所管制的路网，s为所管制的路网的起点，t为所管制的路网的终点，一般情形下，交通管理部门会按最大流原则分配流量。

然而在现实情况下，交通管理部门事前无法知道哪一条路段会由于交通事故（或其他突发事件）而突然堵塞（或中断），而一旦出现堵塞，车辆就需要绕路。

假如在某一时间段内只发生一次突然堵塞，那么该如何确定关键路段，加强管制，以使道路突然中断时最大可能减少路网效率损失？

⑦

图1路网图

2.3认知三——网络规划求解

1、最短路问题求解

（1）穷举法：

1）适用于路不多的简单问题；

2）求出每条路长，比较各条路长求一路长最短的路。

例2.3-3:

求如下网络图2.3-2中点1到点6最短路。

图2.3-2网络图

解题步骤如下图2.3-3：

图2.3-3解题步骤图

序号路路长最短路

11-2-4-616

21-2-4-5-623

31-3-5-617

41-3-2-4-5-622

51-3-2-4-6151-3-2-4-6

（2）标号法：

例2.3-4：

以例2.3-1为例，解题步骤如下图2.3-4

图2.3-4解题步骤

根据解题步骤图可知最短路为：

AB1C2D2E2F；

路长为：

17

3、最小费用流问题求解

对于最小费用流的求解，我们以案例中的南方陶瓷公司的这个问题的第一问来说明：

求解步骤：

⑧

（一）设S点为总源,T点为总汇,根据所给资料建立相应的网络如图3。

图3

（二）从零流f0始寻求最大流f3

可先后取增广链

L1=（S,A1,B1,T）　

L2=（S,A2,C1,B1,T）

L3=（S,A2,B2,T）

L4=（S,A3,B2,T）　

L5=（S,A3,C3,C2,B1,T）

L6=（S,A4,C3,C2,B1,T）

L7=（S,A5,B3,T）　

L8=（S,A5,C2,B1,T）　

分别对应得行流f1,f2,⋯,f8,网络流流量不断增加:

V（f0）=0,

V（f1）=4,

V（f2）=7,

V（f3）=9,

V（f4）=12,

V（f5）=15,

V（f6）=16,

V（f7）=20,

V（f8）=21,　

对于可行流f8已不存在从S到T的增广链。

因此,已得网络最大流,其流量分配图如图4所示。

弧旁数字为（bij,fij,Cij）。

图4

（三）从最大流f3，求最小费用最大流f33

1、在图4中对於圈L1=（C1,B1,T,B2,C1）上的所有弧按顺、逆时方向剖分为两弧组:

Le={（C1,B1,（B1,T）}　　Ls={（C1,B2）,（B2,T）}

其中Le的费用大（We=19+110=129）,Ls的费用小（Ws=16+110=126）且弧组Le均为非零弧,弧组Ls均为非饱和弧,从而圈L1为可降圈。

取H=min{f3C1,B1,f3B1,T,CC1,B2–f3C1,B2,CB2,T–f3B2,T}

=min{3,12,6-0,9-5}=3

令f3C1,1B1=f3C1,B1-θ=0　　f3C1,1T=f3C1,T-θ=9

f3C1,1B2=f3C1,B2+θ=3　　　f3C1,1T=f3C1,T-θ=9

于是得到总费用较f3少（129-126）×

3=9的最大流f31,其对应的流量分配图如图5所示。

图5

南方陶瓷公司按最佳方案组织采购、运输、销售陶瓷,总费用可达最低。

其值为:

151×

4+188×

2+167×

3+152×

3+222×

3+226×

1+204×

1+156×

4=3657

4、最大流问题求解

计算网络最大流所采用的算法分为3种:

Ford2Fulkerson标号法、辅助图最短路算法和割集矩阵算法。

前两种是传统算法，Ford2Fulkerson算法通过节点标号法寻找增广路,确定增加的流量。

此算法计算过程繁琐,不适合大规模编程。

辅助图最短路算法利用最短路与最小割集具有对偶性的特性,通过计算最短路得到最小割,但是求解最短路的过程较复杂。

割集矩阵算法不仅能快速求解复杂网络最大流,而且能方便地找出网络的关键路段,在运输网络分析方面比前两种算法更实用。

⑨对于此三种算法，第一种Ford2Fulkerson标号法是最为常见的对最大流问题的求解方法，具体求解案例这里就不做详细展示了。

3结论

运筹与优化是紧密而又不可分的，运筹学的世界是宏大而丰富的，网络规划只是其分支之一。

从现在到未来，运筹学都有着广阔的应用领域，它已渗透到诸如服务、经济、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性等各个方面。

网络规划虽然只有数量可数的几个模型，但其涵括的问题已经涉及到社会生产发展和人类生活的方方面面，其案例在生活中也是可以做到信手拈来，所以重要的是要掌握好对于其所牵涉的问题的解决，以更好的服务于实际情况。

以上就是我作为一名文科生对于运筹与优化的一些认知，我虽然是个门外汉，但运筹学就好比一块大磁铁，吸引着包括我在内的其他学科的学子，其分支之一的网络规划已经如同浩瀚的逻辑海洋，它的重要性和实际作用是不言而喻的。

参考文献：

[1]朱小军、崔剑波.《最短路算法及其应用》[Z].甘肃兰州：

兰州城市学院，2008

[2]卢小青、田如玉《资金运作中最小费用流问题的规划求解》[J].《商场现代化》，2008，8（总第537期）：

171-172

[3]李艳《利用运筹学模型在物流企业中解决实际问题》[J].《淮南职业技术学院学报》，2008,8

（1）：

95-98

[4]李昕伟《关于求网络最大流问题的另一种图解法》[J].《中国科技信息》，2008,1（3）：

97-98

[5]段冰滢《最短路问题的解法探讨》[J].《科协论坛》，2010,11

（1）：

74-75

[6]林景荣《最小费用流在商品购运销中的应用》[J].《系统工程理论与实践》，1994,14（8）：

78-79

[7]石超峰、徐寅峰《交通网络最大流关键边》[J].《系统工程》，2009,27（9）：

57-58

[8]林景荣《最小费用流在商品购运销中的应用》[J].《系统工程理论与实践》，1994,14（8）：

79-81

[9]向红艳、张邻、杨波《基于最大流的路网结构优化》[J].《西南交通大学学报》，2009,44

（2）：

286-287

《运筹与优化》课程结业论文

11123850黄德志

文学院

指导老师：

王冰