运筹学模型

第5章 运筹学模型

5.2 图论模型

图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。

5.2.1 图的基本概念

城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。

1.图

图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接

起来。

图5-1

由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且

使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1也可以画成图5-2的形式。 图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作

) , (E V G =。这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序

的。如果边e 连接顶点u 和v ，则记作e = {v u ,}。u 和v 称作e 的端点，e 称作u 和v 的关联边。如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之间可以有不止一条

边，端点相同的两条边称作平行边，如果一条边的两个端点重合，则称作环。不含环和平行边的图称作简单图。如图5-3中

)

, (E V G =,

V

={

6

i 1 | ≤≤i v },

E ={9j 1 | ≤≤j e }, 1e ={21,v v },

}, {322v v e =, 21 v v 和相邻，31 v v 和不相邻。

21 e e 和相邻。6v 是孤立点。7e 和8e 是平行边，9e 是环。

设P 是图) , (E V G =中以顶点u 和v 为首尾、点边交替的序列。如果序列中每一条边的

端点恰好是与它前后相邻的两个顶点，则称这 个序列p 是从u 到v 的一条链。当链的首尾相

连时，它称作圈。如果链上所有顶点都不相同， 图5-3 则称这条链是初级链。如果圈上除首尾两个定点之外所有顶点都不相同，则称这个圈是初级圈。

例如，在图5-3中，},,,,,,,,,,{452232211911v e v e v e v e v e v p =是一条从41 v v 到的链，但不是初级链。},,,,,,,,,,{112658475412v e v e v e v e v e v p =是一个圈，但不是初级圈。 在简单图中，可以用顶点序列表示链和圈。任意两个顶点间都有一条链的图称作连通图。图5-3不是连通图。

设有两个图) , (E V G =和),(111E V G =。如果E E V V ??11,则称1G 是G 的子图，如果),(111E V G =是) , (E V G =的子图，并且V V =1，则称1G 是G 的生成子图。如果V V ?1， 1E 是E 中所有端点属于1V 的边组成的集合，

则称1G 是G 的关于1V 的导出子图，图5-4中的3个图均是图5-3的子图，其中（b ）是生成子图，（c ）是关于},,{5211v v v V =的导出子图。

图 5-4

我们常常可以利用图比较简便的解决某些实际问题，下面是一个例子。

例 1 有5位运动员参加游泳比赛，表5-1给出每位运动员参加的比赛项目。问如何安排比赛，才能是每位运动都不连续的参加比赛？

表 5-1

赛没有同一运动员参加，则可以把这两项紧排在一起，用一条边把代表这两个项目的顶点连起来。这样得到 图5-5，不难看出，为了解决这个问题，只需找到一条包含所有顶点的初级链。如P= {B,C,D,A,E}是一条初级链，其对应的比赛安排是：50m 蛙泳，100m 蝶泳，100m 自由泳，50m 仰泳，200m 自由泳。

图 5-5

2.有向图

在图) , (E V G =中，边是没有方向的，即},{},{u v v u =，这种图称作无向图。但是，有些关系不是对称的，用图表示这样的关系时，边是有方向的，用箭头表示，称作弧。从顶点u 指向v 的弧a 记作),(v u a =。u 称作a 的始点，v 称作a 的终点。这样的图称作有向图。

设顶点集合V ={n v v v ,...,, 21}，弧集合A ={m a a a , ... ,,21}，有向图记作) , (A V D =，和无向图类似，在有向图中也有环、平行弧、子图等概念。当然，在有向图中必须注意到弧是有方向的。例如，平行弧不仅要求两条弧的端

点相同而且要求它们的始点和始点相同，终点和终点相同。

设P 是有向图) , (A V D =中从顶点u 到v 的点弧交替的序列。

如果序列中每一条弧的始点和终点恰好分别是与它前后相邻的顶点，则

P 称D 是中的一条路。当路的首尾相连时，称

作一条回路。和无向图一样，顶点全不相同的路称作初级回路。例如，图5-6给出一个有向

图) , (A V D =，其中V ={4321,,, v v v v }，}, 81|{≤≤=i a A i ),(),,(232211v v a v v a ==， 图 5-6

},,,,,,{1435461v a v a v a v p =是一初级回路。

3. 树

无圈的连通图称作树(tree)。设) , (E V G =为一个连通图，如果树) , (E V T =是

) , (E V G =的生成子图，则T 称作G 生成树。图5-7给出3棵树，其中（b ）和（c ）都是图

5-1的生成树。

图 5-7

不难证明树有下列性质：

性质1 树的边数等于顶点数减1。

性质2 树的任意两个顶点之间有且只有一条初级链。 性质3 在树中任意去掉一条边，就得到一个非连通图。

性质4 在树中任意两个顶点之间添加一条边，恰好产生一个初级圈。

5.2.2 最小生成树

设图) , (E V G =，对每一条边E e ∈， 指定一个实数)(e ω，我们称这样的图为赋权图，记作) ,, (ωE V G =，其中ω是边集合E 到实数集的映射，实数)(e ω称作边的权。当

},{j i v v e =时，常把)(e ω记作j i ω。类似地，对有向图) , (A V D =的每一条弧A a ∈指定

一个实数)(a ω，得到赋权有向图，记作) ,, (ωA V D =，)(a ω称作弧a 的权，当)

,(j i v v a =时，常把)(a ω记作j i ω。

在实际应用中，权可以有各种各样的含义，如距离、时间、费用、运输量、流量等。

1．最小生成树的概念

设) ,, (ωE V G =是一个连通的赋权图，),(S V T =是G 的生成树，把T 中所有边的权之和称作树T 的权，记作)(T ω，即∑∈=s

e e T )()(ωω，G 中权和最小的生成树*

T

称作最小

生成树。

2．最小生成树的算法

Kruskal 于1956年给出一个求最小生成树的算法：避圈法。其基本方法如下：

(1) 画出图) ,, (ωE V G =中的全部顶点。

(2) 按边权的大小从小到大选边（n 个顶点需n-1步），并且每一步都不能构成

圈。

例 2 现有5个城市，打算用铁路把它们连接起来。这5个城市之间哪两个可以修建铁路以及铁路的长度如图5-8所示（每一条边旁边有一个数字，即表示这段铁路的长度）。试给出修建铁路的方案，使铁路总长度最短。

图 5-8

解 此题提出的问题是求给定赋权图的最小生成树。做题步骤如图5-9所示：

图 5-9

注意，在第四步,可以不取},{42v v ，而取},{53v v ，得到另一棵最小生成树，其权和为

12。如图5-10所示。可见最小生成树不唯一。

计算在每一步都要判断添加的边是否构成圈。这在图不很复杂时，直接观察并不困难。但在使用

计算机时，则必须进一步给出形式化的方法，计算的具体步骤如下：

Kruskal 算法

1. 按权从小到大排列边

)()()(21m e e e ωωω≤≤≤

令 n i i v l i ≤≤←1 ,)( 图 5-10 2. 令S ←φ,K ←1(φ表示空集)。

3. 设)()( },,{v l u l v u e k ==若，则转6；否则令}{k e s s ←，执行4。

4. 对所有i i v v l u l v l 的顶 )}(),(max{)(=

令 )}(),(min{)(v l u l v l i ←。

5. 若|S|= n-1,则 是S 最小生成树的边集合，计算结束；否则执行6。（|S|表示S 中元素的个数）

6. 若k=m ，则说明图是非连通的，停止计算；否则令k ←k+1，转3。

5.2.3最短路问题

1. 最短路的概念

设 (,)G V E =为连通图，图中各边 (,)i j v v 有权 i j ω（其中i j ω=+∞ 表示 ,i j v v

之间没有边），,s t v v 为图中任意两点，所谓最短路问题就是求一条路μ，使它为从s v 到t v 的所有路中总权最小的路。即：(,)()i j i j

v v L μμω

∈

=

∑ 最小。

2. 图的矩阵表示

对于赋权图( , )G V E =，由其边(,)i j v v 的权i j w ，构造矩阵()i j n n A a ?= ，其中：

(,)inf() (,)0 i j i j i j i j i j

w v v E

a v v E v v ?∈?

=∞???

=?

称矩阵A 为赋权图G 的权矩阵。

例如图5-11的权矩阵为：

图5-11

3．最短路的算法

（1）由图写出其权矩阵。

（2）由Matlab 软件求最短路。 （3）软件计算程序为：

function[D,R]=floyd(a) n=size(a,1); D=a

for i=1:n for j=1:n R(i,j)=j; end

end R

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

End

例 3求下图5-12从1v 到6v 的最短路。（无向图）

图 5-12 解 首先由图写出其权矩阵：

035inf inf inf 30122inf 510inf 4inf a inf 2inf 024inf 24202inf inf

inf

4

2

????????=?

?????????

再给出指令 [D ，R]=floyd(a) 最后由Matlab 软件得出结论：

最短距离（下列数据可揭示图中任意两点的最短距离）

D =

0 3 4 5 5 7 3 0 1 2 2 4 4 1 0 3 3 5 5 2 3 0 2 4 5 2 3 2 0 2 7 4 5 4 2 0

最短路径（下列数据可揭示图中任意两点的最短路径）

R =

1 2 2 2 2 2 1 2 3 4 5 5 2 2 3 2 2 2 2 2 2 4 5 6 2 2 2 4 5 6 5 5 5 4 5 6

则1v 到6v 的最短路为：

1256v v v v →→→

例 4 有一批货要从1运到8，运输路线如图5-13所示，弧旁的数字是这段路的单位运费。试给出总运费最小的运输路线。（有向图）

图5-13

解首先由图写出其权矩阵：

02inf1inf3inf inf

inf06inf5inf inf inf

inf inf0inf inf inf inf6

inf10inf0inf inf2inf

a

inf inf9inf0inf inf4

inf inf inf5inf04inf

inf7inf inf3inf08

inf inf inf inf inf inf inf0

再给出指令 [D，R]=floyd(a)

最后由Matlab软件得出结论：

最短距离

D =

0 2 8 1 6 3 3 10

Inf 0 6 Inf 5 Inf Inf 9

Inf Inf 0 Inf Inf Inf Inf 6

Inf 9 14 0 5 Inf 2 9

Inf Inf 9 Inf 0 Inf Inf 4

Inf 11 16 5 7 0 4 11

Inf 7 12 Inf 3 Inf 0 7

Inf Inf Inf Inf Inf Inf Inf 0

最短路径

R =

1 2 2 4 4 6 4 4

1 2 3 4 5 6 7 5

1 2 3 4 5 6 7 8 1 7 7 4 7 6 7 7 1 2 3 4 5 6 7 8 1 7 7 4 7 6 7 7 1 2 5 4 5 6 7 5 1 2 3 4 5 6 7 8

则从1到8的最短路径为

14758→→→→，最小运费为10。

例 5 求图5-14从1v 到4v 的最短路。 （有负权）

图 5-14 解 由图写出其权矩阵：

023inf inf 0inf 2a inf 403inf inf inf 0

=

- 给出指令 [D ，R]=floyd(a)

由Matlab 软件得出结论：

D = 0 -1 3 1

Inf 0 Inf 2 Inf -4 0 -2 Inf Inf Inf 0

R = 1 3 3 3

1 2 3 4 1 2 3 2 1 2 3 4 则1v 到4v 的最短路为

1324v v v v →→→ ,其权为1。

例 6 （设备更新问题）一台机器在新的时候，故障少，维修费用小。使用一段时间之后，故障增多，维修费用增加。而更换一台新的，则需要一笔购置费，因此，企业应该制定一个较长时间内的设备更新计划，使得在这时期内设备购置费和维修费的总和最小。现在正

好是年末，计划在明年初购置一台新机器，并且要做出今后5年的设备更新计划。预测该机器在今后5年的价格（以万元为单位）如下表所示：

表 5-2

不同使用年限的维修费用（以万元为单位）如下表所示：

解 这是一个实际应用问题，首先将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。

用 i v （51≤≤i ）表示第i 年初购置新设备，增加一个 6v 表示机器用到第5年底。弧

),(j i v v 的权j i ω为第i 年初购买的设备使用到第j 年初（或第1-j 年底）所需的购置费与

维修费之和（61≤<≤j i ）。例如13ω= 22 + 10 + 12 = 44。这样就得到一个赋权有向图

D ，如图5-15所示。

图 5-15

在D 中从 1v 到 6v 的一条路表示一个设备更新计划，于是我们的问题变成求D 中从 1v 到

6v 的最短路。

图的权矩阵为：

a=[0 32 44 60 82 118

inf 0 32 44 60 82 inf inf 0 34 46 62 inf inf inf 0 34 46 inf inf inf inf 0 36 inf inf inf inf inf 0];

[D,R]=floyd(a)

D = 0 32 44 60 82 106 Inf 0 32 44 60 82 Inf Inf 0 34 46 62 Inf Inf Inf 0 34 46 Inf Inf Inf Inf 0 36 Inf Inf Inf Inf Inf 0

R =1 2 3 4 5 3 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

更新计划为136v v v →→，即在第一年和第三年初各购一台新设备，总费用是106万元。

例 7 银行计划用6千元来发展某种产品的生产。现有三个投资对象，预测对它们的投资额与5年的利润关系如下：

对一个单位的最大投资额是3千元。试制定这项投资计划，使总利润最大。

解 首先考虑对A 投资。设i A 为 对A 投资后剩余i （千万元）。应有6A ，5A ，4A ，

3A 。再接着考虑对B 投资。设j B 为 对B （实际上是对A 和B ）投资后剩余j （千万元）。

应有0123 , , ,B B B B 。最后的余款全部投资给C,记作0C 。而开始时记作6S ，表示总投资额有6（千万元）从6S 到5A 的弧表示对A 投资1千万元，可收益2千万元，故弧（6S ，5A ）的权为2，其它的依此类推。如图5-16所示。显然，现在的问题是要求从6s 到0C 的最长路。

我们只需将每一个权变号，就可以把最长路问题变成最短路问题。

图 5-16

由Matlab 软件可得： 6S 到0C 的最长路是6S →3A →2B →0C 。即对A 投资3千万元，对B 投资1千万元，对C 投资2千万元，五年可获利润7.7千万元。（读者自已利用软件求解验证）

5.2.4最大流问题

1. 网络和可行流

设),(A V D =是一个有向图，指定两个顶点s v 和t v ，s v 称作发点(source)，t v 称作收点(sink)，其余的点称作中间点。每一条弧a 有个数0)(≥a c ，称作弧a 的容量，我们把这样的有向图叫做网络(network)，记作),,,,(t s v v c A V D =，其中c 是容量函数。例如图5-17给出一个网络。

图 5-17

交通图、流体的管道输送系统、电力输送系统都可以用网络表示。

一般地，对网络D 中的每一条弧A a ∈指定一个实数)(a f ，如果满足下述条件： （1） 容量约束。对所有的弧A a ∈，有

)()(0a c a f ≤≤

（2） 守恒条件。对所有的中间点},{t s v v V v -∈，

)()(v f v f -+=

则称f 是D 上的一个可行流(feasible flow)。)(a f 称作弧a 上的流量， ∑∈'+'=A

v v v v f v f ),(),( )(

称作顶点v 的流出量,∑∈'-'=

A

v v v v f v f ),(),()(, 称作顶点v 的流入量，)

()()(s s v f v f

f v -+

-=或)()()(t t v f v f f v +--=称作可行流f 的流量。

可行流总是存在的。例如，令所有的)(a f =0，这是一个流量为0的可行流，称作零

流，记作f =0。例如图5-18给出一个可行流，弧),(j i v v 旁边标的数字是),(ij ij f c 其流量

10)(=f v 。

图 5-18

网络D 上的流量最大的可行流称作D 的最大流。所谓最大流问题(maximal flow problem)就是求给定网络的最大流。

2. 常见弧的分类

（1） 饱和弧：)()(a c a f =，如图5-18中，),(1v v s 是饱和弧。 （2） 非饱和弧：)()(a c a f <，如图5-18中，),(2t v v 是非饱和弧。 （3） 零流弧：0)(=a f ，如图5-18中，),(2v v s 是零流弧。 （4） 非零流弧： 0)(>a f ，如图5-18中，),(3v v s 非零流弧。 例8 下图5-19给出一个可行流（注意容量约束、守恒条件）

图 5-19

图中 36( , )v v 为零流弧，其余为非饱和弧、非零流弧。其流量v (f ) =8

3. 最大流与最大流的算法

（1）最大流的定义

网络上的流量最大的可行流称作的最大流，所谓最大流问题就是求给定网络的最大

流。

（3） 最大流的算法

1） 由图编写程序。

2） 由lingo8.0软件求最大流。

例9 现需要将城市s 的石油通过管道运送到城市t ,中间有4个中转站v 1,v 2,v 3 和v 4，城市与中转站的连接以及管道的容量如下图5-20所示，求从城市s 到城市t 的最大流。

图 5-20 解 由lingo8.0软件求解的程序如下：

sets:

nodes/s,1,2,3,4,t/; arcs(nodes,nodes)/

s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,f; endsets data:

c= 8 7 5 9 9 2 5 6 10;

enddata

max = flow;

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);

@sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow;

@for(arcs:@bnd(0,f,c));

END

注程序由以下三部分构成：

1、集合定义部分（sets到endsets) 。

2、数据输入部分（data到enddata)。

3、其他部分为优化目标和约束条件。

lingo8.0运行结果如下：

Global optimal solution found at iteration: 6

Objective value: 14.00000 Variable Value Reduced Cost

FLOW 14.00000 0.000000

C( S, 1) 8.000000 0.000000 C( S, 2) 7.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, 3) 9.000000 0.000000 C( 2, 4) 9.000000 0.000000 C( 3, 2) 2.000000 0.000000 C( 3, T) 5.000000 0.000000 C( 4, 3) 6.000000 0.000000 C( 4, T) 10.00000 0.000000 F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000

F( 3, 2) 0.000000 0.000000

F( 3, T) 5.000000 -1.000000

F( 4, 3) 0.000000 1.000000

F( 4, T) 9.000000 0.000000 求解结果标在图5-21上，从城市s 到城市t 的最大流为v(f ) =14。

图5-21

例10 求下图5-22中网络D的最大流。

图5-22

解lingo8.0软件求解的程序如下：

sets:

nodes/s,1,2,3,t/;

arcs(nodes,nodes)/

s,1 s,2 s,3 1,2 1,t 2,3 2,t 3,t/:c,f;

endsets

data:

c= 5 7 8 5 7 4 6 7;

enddata

max = flow;

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):

@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);

@sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow;

@for(arcs:@bnd(0,f,c));

END

运行结果如下：

Global optimal solution found at iteration: 5

Objective value: 18.00000

Variable Value Reduced Cost FLOW 18.00000 0.000000 C( S, 1) 5.000000 0.000000 C( S, 2) 7.000000 0.000000 C( S, 3) 8.000000 0.000000 C( 1, 2) 5.000000 0.000000 C( 1, T) 7.000000 0.000000 C( 2, 3) 4.000000 0.000000 C( 2, T) 6.000000 0.000000 C( 3, T) 7.000000 0.000000 F( S, 1) 5.000000 -1.000000 F( S, 2) 6.000000 0.000000 F( S, 3) 7.000000 0.000000 F( 1, 2) 0.000000 1.000000 F( 1, T) 5.000000 0.000000 F( 2, 3) 0.000000 0.000000 F( 2, T) 6.000000 -1.000000 F( 3, T) 7.000000 -1.000000

求解结果标在图5-23上，网络D 的最大流为v (f ) =18。

图 5-23

例 11 （多发点多收点网络的最大流问题）某种物资有两个产地1s 和2s ，三个销地1t ，

2t 和3t 。运输系统如图5-24所示，其中1v 和2v 是两个中转站。所标数字是线路的最大运输

能力。求从产地到销地的最大运输量。

解 这是一个多发点多收点的网络。为了能够用前面介绍的算法求它的最大流,需要把它化成只有一个发点和一个收点的网络。

这并不困难.在网络中添一个发点s v 和一个收点t v 以及s v 到1s ,2s 的弧, 1t ,2t ,3

t

到t v 弧．弧),(1s v s 的容量取作所有以1s 为 图 5-24

始点的弧的容量之和（或者任何大于这个数的数），这里应等于1051227++=。同样，

),(2s v s 的容量可取作151227+=．而弧),(1t v t 的容量取作所有以1t 为终点的弧的容量之

和（或者任何大于这个数的数），弧),(1t v t 和),(3t v t 的容量类同．这样就得到一个只有一个发点和一个收点的网络D ，对于D 上的任何一个可行流，删去多余的弧之后，就得到D 上的任何一个可行流．总可以把它扩张到D 上，成为D 上的一个可行流．这样一来，就把求原最大流化成求D 的最大流．

只有一个发点和一个收点的网络如下图5-25 。

图 5-25 其lingo8.0软件求解的程序如下： sets:

nodes/vs,s1,s2,v1,v2,t1,t2,t3,vt/; arcs(nodes,nodes)/

vs,s1 vs,s2 s1,t1 s1,v1 s1,v2 s2,v2 s2,t3 v1,t1 v1,t2 v2,v1 v2,t2 v2,t3 t1,vt t2,vt t3,vt/:c,f; endsets data:

c= 27 27 10 5 12 15 12 8 6 3 6 10 18 12 22 ; enddata

max = flow;

@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes): @sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0); @sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow; @for(arcs:@bnd(0,f,c)); END

运行结果如下：

Global optimal solution found at iteration: 10 Objective value: 46.00000

Variable Value Reduced Cost FLOW 46.00000 0.000000 F( VS, S1) 19.00000 0.000000 F( VS, S2) 27.00000 0.000000 F( S1, T1) 10.00000 -1.000000 F( S1, V1) 5.000000 -1.000000 F( S1, V2) 4.000000 0.000000 F( S2, V2) 15.00000 0.000000 F( S2, T3) 12.00000 0.000000 F( V1, T1) 8.000000 0.000000 F( V1, T2) 0.000000 0.000000 F( V2, V1) 3.000000 -1.000000 F( V2, T2) 6.000000 -1.000000 F( V2, T3) 10.00000 0.000000 F( T1, VT) 18.00000 0.000000 F( T2, VT) 6.000000 0.000000 F( T3, VT) 22.00000 -1.000000 求解的结果标在图5-26上，这个运输系统的最大运量为46。

图 5-26

5.2.5 最小费用最大流问题

在考虑一个运输系统中的运输量的同时，往往还要考虑运输费用，希望给出从发货站到收货站的运输量最大、费用最小的运输方案。这就是最小费用最大流问题。

1．最小费用最大流的基本概念

设D 是一个网络，对于每一条弧A a ∈，除容量)(a c 外，还给定一个数0)(≥a b ，称

第七章运筹学运输问题案例

第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果： 得种植计划方案如下表： 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的大型客车。该厂在这四年内生产大型客车的能力及每辆客车的成本情况如下表： 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维

护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：得运价表（产大于销的运输模型）如下： 第一季度正常上班生产20台，加班27台，拿出正常生产18台和加班2台，加上年前储存的20台，满足本季度的40台； 第二季度正常生产38台，不安排加班。加上第一季度储存的2台，满足本季度的40台； 第三季度正常生产15台，不安排加班。加上第一季度储存的25台，满足本季度的40台； 第四季度正常生产42台。加班生产23台。拿出正常生产的17台的加班生产的23台满足本季度的40台。剩余25台以后务用。 7.3 某企业生产有甲、乙、丙、丁四个分厂生产同一种产品，这四个分厂的产量分别为：200吨、300吨、400吨和100吨，这些产品供应给A、B、C、D、E、F六个地区，六个地区的需求量分别为：200吨、150吨、350吨、100吨、120吨、120吨。由于工艺、技术的差别，各分厂运往各销售地区的单位运价（万元/吨）、各厂单位产品成本（万元/吨）和各销地的销售价格（万元/吨）如下表：

补充：运筹学经典案例

运筹学经典案例 一、鲍德西（B a w d s e y）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。1935年，英国科学家沃森—瓦特：（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的P.M.S.Blachett为首，组织了一个小组，代号为“Blachett马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。 “Blackett马戏团”是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了“Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。

运筹学 参考书

参考书 1.《运筹学》（科学版精品课程立体化教材·管理学系列）(第2版)，张伯生等编著，科学出版社，2012年； 2.《数据、模型与决策》(第13版)，戴维·R·安德森/丹尼斯·J·斯威尼编著，于淼译，机械出版社，2012年； 3、《运筹学》（新体系经济管理系列教材），李成标，刘新卫主编，清华大学出版社，2012年； 4．《运筹学——优化模型与算法》，（美）拉丁（Rardin，R.L.) 著，电子工业出版社，2007年 5.《Introduction to Operations Research》（第6 版）（外原版经典教材）， F. S. Hillier and G. J. Lieberman 著，McGraw-Hill 出版社； 6. 《运筹学》，党耀国，李帮义等编著，科学出版社，2009年； 7. 《物流运筹学》，刘蓉主编，电子工业出版社，2012年； 8. 《运筹学导论》（第9版）（美国麦格劳-希尔教育出版公司工商管理最新教材（英文版）），（美）希利尔，（美）利伯曼著，清华大学出版社，2010年； 9. 《运筹学》（第4版）（面向21世纪课程教材（信息管理与信息系统专业教材系列），《运筹学》教材编写组编，清华大学出版社，2012年； 10.《运筹学：应用与解决方法》（第4版）（美国商学院原版教材精选系列），（美）温斯顿著，清华大学出版社，2011年； 11.《管理运筹学》（高等学校经济与工商管理系列教材），茹少峰，申卯兴编著，清华大学出版社，2008年； 12.《运筹学》（第3版），刁在筠等编，高等教育出版社，2007年；

13.《实用运筹学：模型、方法与计算》，韩中庚主编，清华大学出版社，2007年； 14.《运筹学》（现代信息管理与信息系统系列教材），李红艳，范君晖主编，清华大学出版社，2012 年； 15.《管理运筹学：管理科学方法》（21世纪管理科学与工程系列教材），谢家平著，中国人民大学出版社，2010年； 16.《运筹学与实验》，薛毅，耿美英编著，电子工业出版社，2008年； 17.《实用运筹学——上机实验指导及习题解答》，叶向编，中国人民大学出版社，2007年； 18.《应用运筹学》（第二版），曹勇，周晓光，李宗元编著，经济管理出版社，2008年； 19.《运筹学导论》（第8版），（美）希利尔（Hillier,F.S.），（美）利伯曼（Lieberman,G.J.）著，胡运权等译，清华大学出版社，2007年； 20.《经济管理运筹学习题集》，王玉梅，孙在东，张志耀编著，中国标准出版社，2012年； 21.《运筹学习题集》(第4版),胡运权主编，清华大学出版社，2010年； 22.《运筹学解题指导》，周华任主编，清华大学出版社，2006年； 23.《运筹学概率模型应用范例与解法》（第4版），（美）温斯顿（Winston，W.L.）著，李乃文等译，清华大学出版社，2006年； 24.《运筹学学习辅导与习题解析》(第3版)，戎晓霞，宿洁，刘桂真编，高等教育出版社，2009年； 25.《管理运筹学习题集》(普通高等学校管理科学与工程类学科核心课程教材辅

运筹学---案例分析

管理运筹学案例分析 产品产量预测 一、问题的提出 2007年，山西潞安矿业集团与哈密煤业集团进行重组，成立了潞安新疆煤化工（集团）有限公司。潞安新疆公司成立后，大力加快新项目建设。通过技术改造和加强管理，使煤炭产量、销售收入、利润、职工收入等得到了大幅提高，2007年生产煤炭506万吨，2008年煤炭产量726万吨，2009年煤炭产量956万吨。三年每月产量见下表，请预测2010年每月产量。 表1 2007—2009年每月产量表单位：万吨 二、分析与建立模型 1、根据2007—2009年的煤炭产量数据，可做出下图：

表2 2007—2009年每月产量折线图 由上图可看出，2007—2009年的煤炭产量数据具有明显的季节性因素和总体上升趋势。因此，我们采取用体现时间序列的趋势和季节因素的预测方法。 （一）、用移动平均法来消除季节因素和不规则因素影响 1、取n=12； 2、将12个月的平均值作为消除季节和不规则因素影响后受趋势因素影响的数值； 3、计算“中心移动平均值”； 4、计算每月与不规则因素的指标值。 表3 平均值表

5、计算月份指数； 6、调整月份指数。 表4 调整（后）的月份指数 （二）、去掉时间序列中的月份因素 将原来的时间序列的每一个数据值除以相应的月份指数。表5 消除月份因素后的时间序列表

三、计算结果及分析 确定消除季节因素后的时间序列的趋势。 求解趋势直线方程。设直线方程为： T t =b0+b1 t T t为求每t 时期煤炭产量；b0为趋势直线纵轴上的截距；b1为趋势直线的斜率。 求得： 四、一点思考 新疆的煤矿生产企业产能只是企业要考虑的部分因素，因国家产业政策以及新疆距离内地需经河西走廊，因此，企业不仅要考虑产能，更多的要考虑运输问题，从某种意义上来说，东疆地区煤炭生产企业不是“以销定产”，而是“以运定产”，也就是说，物流运输方案是企业管理人员要认真思考的问题。本案例可以结合物流运输远近及运输工具的选择作进一步的

运筹学答案_第_11_章__图与网络模型

第11章图与网络模型 习题1 配送的最短距离。用解：这是一个最短路问题，要求我们求出从v1到v 7 Dijkstra算法求解可得到这问题的解为27。我们也可以用此书附带的管理运筹学软件进行计算而得出最终结果为： 从节点1到节点7的最短路 ************************* 起点终点距离 ------------ 124 2312 356 575 此问题的解为:27 → 12357 习题2 解：这是一个最短路的问题，用Dijkstra算法求解可得到这问题的解为4.8，即在4年内购买、更换及运行维修最小的总费用为：4.8万元。 最优更新策略为：第一年末不更新 第二年末更新 第三年末不更新 第四年末处理机器 我们也可以用此书附带的管理运筹学软件进行求解，结果也可以得出此问题的解为4.8。 习题3 解：此题是一个求解最小生成树的问题，根据题意可知它要求出连接v1到v8的最小生成树。解此题可以得出结果为18。也可以使用管理运筹学软件，得出如下结果： 此问题的最小生成树如下： ************************* 起点终点距离 ------------ 132 342 124 252 573

习题4 782 763此问题的解为:18 解：此题是一个求解最大流的问题，根据题意可知它要求出连接v1到 v6 的最 大流量。解此题可以得出最大流量为 出结果为： 22。使用管理运筹学软件，我们也可以得v1从节点1到节点6的最大流 ************************* 起点终点距离 ------------ 126 146 1310 240 256 345 365 455 466 5611 此问题的解为:22 即从v1到v6的最大流量为：22 习题5 解：此题是一个求解最小费用最大流的问题，根据题意可知它要求出连接v1到v6的最小费用最大流量。解此问题可以得出最大流为5，最小费用为39。使用管理运筹学软件，我们也可以得出结果如下： 从节点1到节点6的最大流 ************************* 起点终点流量费用 ---------------- 1213 1341 2424 3211 3533 4624

简单的运筹学实际应用案例

运筹学的实际应用 学生会晨读考勤巡视人员分配建模 晨读考勤制度是我校对大学一年级及二年级学生的特殊制度，针对上午第一节有课的班级——周一至周五上午第一节课有课（包括任何课程）的班级需7:30到教室组织英语晨读，未按时到达学生录入考勤系统，按迟到处理。 晨读考勤状况的盘点与巡视工作由校学生会负责。因为每天上晨读的班级数目都不一样，所以每天需要的巡查人员数目也并不同，根据每天晨读班级数目制定的每日所需巡查人数如下表所示。巡视工作枯燥繁重，所以成员在连续参与巡视工作3天后，可以连休两天。（周二至周四巡视过得人员可以在周五和下周一休息）。 学生会人数有限，所以请设计一套方案，需满足每天所需的巡查人数，又使 项目解决： 一，项目内容要求提取 （1）忽略星期六和星期日 （2）巡视人员连续工作3天后连续休息2天，忽略请假情况 （3）分配休息两天后周一至周五每天开始工作的人员，使总工作人数最少。 二，分析建模 此问题是一个典型并且简单的线性规划问题，所以接下来是建立目标函数以及对应的约束条件，并设法求解。 建立模型： Z为所需巡视人员总的人数。 设：x i（i=1,2,3,4,5）为休息两天后，周一至周五每天开始工作的学生会成员。 minZ=x1+x2+x3+x4+x5 x1+x4+x5≥40 x1+x2+x5≥55

x1+x2+x3≥30 x2+x3+x4≥48 x3+x4+x5≥30 x i≥0，i=1,2,3,4,5 三，求解 运用Matlab的linprog函数求解 编写命令： c=[1,1,1,1,1] A=[-1 0 0 -1 -1; -1 -1 0 0 -1; -1 -1 -1 0 0; 0 -1 -1 -1 0; 0 0 -1 -1 -1;] b=[-40;-55;-30;-49;-30]; Aeq=[];beq=[]; vlb=[0;0;0;0;0];vub=[] [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) 求解得出： x = 4.3625 32.0000 0.0000 17.0000 18.6375 fval = 72.0000

数学建模 运筹学模型(一)

运筹学模型（一） 本章重点： 线性规划基础模型、目标规划模型、运输模型及其应用、图论模型、最小树问题、最短路问题 复习要求： 1.进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵. 2.进一步理解数学模型的作用与特点. 本章复习重点是线性规划基础模型、运输问题模型和目标规划模型.具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单.运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单.你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求.目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型.另外，关于图论模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型.这之前恐怕要善于将一个实际问题转化为图论模型.还有一个最小数的问题，该如何把一个网络中的最小数找到.另外在个别场合可能会涉及一笔划问题. 1.营养配餐问题的数学模型 n n x C x C x C Z ++=211m i n ????? ?? ??=≥≥+++≥+++≥+++??) ,,2,1(0, ,, 22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 ∑== n j j j x C Z 1 m i n ??? ??? ?==≥≥??∑=),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 2.合理配料问题的数学模型 有m 种资源B 1，B 2，…，B m ，可用于生产n 种代号为A 1，A 2，…，A n 的产品.单位产品A j 需用资源B i 的数量为a ij ，获利为C j 单位，第i 种资源可供给总量为b i 个单位.问如何安排生产，使总利润达到最大？ 设生产第j 种产品x j 个单位（j =1，2，…，n ），则有 n n x C x C x C Z +++= 2211m a x

运筹学经典案例

运筹学经典案例 案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的P.M.S.Blachett为首，组织了一个小组，代号为“Blachett 马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团”是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。

管理运筹学lindo案例分析报告

管理运筹学lindo案例分析 ⑻Lindo的数据分析及习题 用该命令产生当前模型的灵敏性分析报告：研究当目标函数的费用系数和约束右端项在什么围（此时假定其它系数不变）时，最优基保持不变。灵敏性分析是在求解模型时作出的，因此在求解模型时灵敏性分析是激活状态，但是默认是不激活的。为了激活灵敏性分析，运行LINGO|Options…，选择General Solver Tab , 在Dual Computations 列表框中，选择Prices and Ranges 选项。灵敏性分析耗费相当多的求解时间，因此当速度很关键时，就没有必要激活它。 下面我们看一个简单的具体例子。 例5.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示： 用DESKS TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型。 max=60*desks+30*tables+20*chairs; 8*desks+6*tables+chairs<=48; 4*desks+2*tables+1.5*chairs<=20; 2*desks+1.5*tables+.5*chairs<=8; tables<=5; 求解这个模型，并激活灵敏性分析。这时，查看报告窗口（Reports Window）,可以看到如下结果。Global optimal solution found at iteration:3 Objective value:280.0000 Variable Value Reduced Cost DESKS 2.0000000.000000 TABLES0.000000 5.000000 CHAIRS8.0000000.000000 Row Slack or Surplus Dual Price 1280.0000 1.000000 224.000000.000000 30.00000010.00000 40.00000010.00000 5 5.0000000.000000 “ Global optimal solution found at iteration: 3 ”表示 3 次迭代后得到全局最优解。 a Objective value:280.0000 ”表示最优目标值为280。“Value”给出最优解中各变量的值：造2个书桌（desks）, 0 个餐桌（tables ）, 8 个椅子（chairs ）。所以desks、chairs 是基变量（非0）, tables 是非基变量（0 ）。 “ Slack or Surplus ”给出松驰变量的值： 第1行松驰变量=280 （模型第一行表示目标函数，所以第二行对应第一个约束） 第2行松驰变量=24 第3行松驰变量=0 第4行松驰变量=0 第5行松驰变量=5 “ Reduced Cost ”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目 标函数的变化率。其中基变量的reduced cost 值应为0, 对于非基变量X j,相应的reduced cost 值 表示当某个变量X j 增加一个单位时目标函数减少的量（ max 型问题）。本例中：变量tables 对应的

《运筹学》期末复习题

《运筹学》期末复习题 第一讲运筹学概念 一、填空题 1.运筹学的主要研究对象就是各种有组织系统的管理问题,经营活动。 2.运筹学的核心主要就是运用数学方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。 3.模型就是一件实际事物或现实情况的代表或抽象。 4通常对问题中变量值的限制称为约束条件,它可以表示成一个等式或不等式的集合。5.运筹学研究与解决问题的基础就是最优化技术,并强调系统整体优化功能。运筹学研究与解决问题的效果具有连续性。 6.运筹学用系统的观点研究功能之间的关系。 7.运筹学研究与解决问题的优势就是应用各学科交叉的方法,具有典型综合应用特性。 8.运筹学的发展趋势就是进一步依赖于_计算机的应用与发展。 9.运筹学解决问题时首先要观察待决策问题所处的环境。 10.用运筹学分析与解决问题,就是一个科学决策的过程。 11、运筹学的主要目的在于求得一个合理运用人力、物力与财力的最佳方案。 12.运筹学中所使用的模型就是数学模型。用运筹学解决问题的核心就是建立数学模型,并对模型求解。 13用运筹学解决问题时,要分析,定议待决策的问题。 14.运筹学的系统特征之一就是用系统的观点研究功能关系。 15、数学模型中,“s·t”表示约束。 16.建立数学模型时,需要回答的问题有性能的客观量度,可控制因素,不可控因素。 17.运筹学的主要研究对象就是各种有组织系统的管理问题及经营活动。 18、1940年8月,英国管理部门成立了一个跨学科的11人的运筹学小组,该小组简称为OR。 二、单选题 1．建立数学模型时,考虑可以由决策者控制的因素就是( A ) A.销售数量 B.销售价格 C.顾客的需求 D.竞争价格 2.我们可以通过( C )来验证模型最优解。 A.观察 B.应用 C.实验 D.调查 3.建立运筹学模型的过程不包括( A )阶段。 A.观察环境 B.数据分析 C.模型设计 D.模型实施 4、建立模型的一个基本理由就是去揭晓那些重要的或有关的( B ) A数量B变量 C 约束条件 D 目标函数 5、模型中要求变量取值( D ) A可正B可负C非正D非负 6、运筹学研究与解决问题的效果具有( A ) A 连续性 B 整体性 C 阶段性 D 再生性 7、运筹学运用数学方法分析与解决问题,以达到系统的最优目标。可以说这个过程就是一个(C) A解决问题过程B分析问题过程C科学决策过程D前期预策过程8、从趋势上瞧,运筹学的进一步发展依赖于一些外部条件及手段,其中最主要的就是 ( C )

运筹学经典案例

案例一：鲍德西（（B AWDSEY）雷达站的研究 20世纪30年代，德国内部民族沙文主义及纳粹主义日渐抬头。以希特勒为首的纳粹势力夺取了政权开始为以战争扩充版图，以武力称霸世界的构想作战争准备。欧洲上空战云密布。英国海军大臣丘吉尔反对主政者的“绥靖”政策，认为英德之战不可避免，而且已日益临近。他在自己的权力范围内作着迎战德国的准备，其中最重要、最有成效之一者是英国本土防空准备。 1935年，英国科学家沃森—瓦特（R．Watson-Wart）发明了雷达。丘吉尔敏锐地认识到它的重要意义，并下令在英国东海岸的Bawdsey建立了一个秘密的雷达站。 当时，德国已拥有一支强大的空军，起飞17分钟即可到达英国。在如此短的时间内，如何预警及做好拦截，甚至在本土之外或海上拦截德机，就成为一大难题。雷达技术帮助了英国，即使在当时的演习中已经可以探测到160公里之外的飞机，但空防中仍有许多漏洞，1939年，由曼彻斯特大学物理学家、英国战斗机司令部科学顾问、战后获诺贝尔奖金的为首，组织了一个小组，代号为“Blachett马戏团”，专门就改进空防系统进行研究。 这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官及一名测量人员。研究的问题是：设计将雷达信息传送给指挥系统及武器系统的最佳方式；雷达与防空武器的最佳配置；对探测、信息传递、作战指挥、战斗机与防空火力的协调，作了系统的研究，并获得了成功，从而大大提高了英国本土防空能力，在以后不久对抗德国对英伦三岛的狂轰滥炸中，发挥了极大的作用。二战史专家评论说，如果没有这项技术及研究，英国就不可能赢得这场战争，甚至在一开始就被击败。“Blackett马戏团” 是世界上第一个运筹学小组。在他们就此项研究所写的秘密报告中，使用了 “Operational Research”一词，意指作战研究”或“运用研究”。就是我们所说的运筹学。Bawdseg雷达站的研究是运筹学的发祥与典范。项目的巨大实际价值、明确的目标、整体化的思想、数量化的分析、多学科的协同、最优化的结果，以及简明朴素的表述，都展示了运筹学的本色与特色，使人难以忘怀。

__运筹学概述

第一讲运筹学概述 一、运筹学是什么 ----------------------晕愁学 其实，这绝对一种误解，事实上运筹学方法及应用早在中小学就比较系统地学过，并且在我们每时每刻的生活过程中都在利用。 北师大版小学语文第六册教材中就有一篇课文《田忌赛马》，在座的各位应该都不陌生。这是战国时期运筹学思想成功应用的典型实例。孙膑同志合理地利用当时的现有资源、条件和比赛规则，只建议田忌调换了赛马的出场顺序，就使得原来屡战屡败的战局得到了彻底的扭转，以获胜而告终。形成了本文主题中“初战失败”、“孙膑献计”、“再赛获胜”的三部分内容。 运筹学思想体现的是，将现有资源的作用得到充分发挥，以获得最优的结果。运筹让生活得更有条理的艺术。 谈起运筹学，是否会想到很通俗的例子——沏茶水。沏茶，看起来是一件日常生活中再小不过的事情，却包含着运筹学的道理。让我们来看一看，沏茶的过程可以分为烧开水、洗茶壶、放茶叶多道“工序”。其中，烧开水所需的时间最长，洗茶壶、放茶叶的时间则较短。善于运筹的人，应该是先将水烧上，在烧水的过程中，从从容容地把茶壶洗净，把茶叶放好。而不善运筹的人，可能会先把茶壶洗净，把茶叶放好，才想起来水还没有烧；或者先把水烧开了，才急急忙忙去洗茶壶、放茶叶，搞得手忙脚乱。 另外还有一个例子我们外地生到上海的路线选择，虽然条条大路都能通到上海，但我们都有一个明确的目标，有些人的目标是准备用最短的时间到达，有些人的目标是用最少费用到达，这样基于不同的目标，就会选择不同的最佳路线。 这两个生活中的运筹学实例说明了运筹学应用的思想并不神秘，而现实的生活中，从沏茶、选择路线这样一件小事，到规模宏大的建设项目，都能运用运筹学的原理。在人生大事的安排上，也同样需要下功夫好好运筹一番。 从技术是，也就是运筹学解决决策问题的工具方面，在初中的数学教材中有一个重要的内容是《线性规划》，其中比较详细地讲述了线性规划的数学表述形式和求解方法。只不过没有详细介绍在实际决策过程中的应用。而线性规划是运筹学的主要决策工具，并且我们

中国古代的运筹学案例

中国古代优秀的运筹案例 1. 孙武与《孙子兵法》 孙武，字长卿，后人尊称其为孙武子、孙子，中国历史上著名军事家.公元前535年左右出生于齐国乐安（今山东惠民）. 后来到了吴国，因为献上兵法十三篇，被吴王阖闾重用，拜为大将，和伍子胥共事，辅佐吴王，领兵攻破楚国都城郢（今湖北江陵县纪南城）. 孙武在春秋末期（公元前476年前后）所著《孙子兵法》，是世界上现存最古老的兵书.其中的《始计第一》论述怎样在开战之前和战争中实行谋划的问题，以及谋划在战争中的重要意义；《作战第二》论述速战速胜的重要性；《谋攻第三》论述用计谋征服敌人的问题；《军形第四》论述用兵作战要先为自己创造不被敌人战胜的条件，以等待敌人可以被我战胜的时机，使自己“立于不败之地”；《兵势第五》论述用兵作战要造成一种可以压倒敌人的迅猛之势，并要善于利用这种迅猛之势；《虚实第六》论述用兵作战须采用“避实而击虚”的方针；《军争第七》论述如何争夺制胜的有利条件，使自己掌握作战主动权的问题；《九变第八》论述将帅指挥作战应根据各种具体情况灵活机动地处置问题，不要机械死板而招致失败，并对将帅提出了要求；《行军第九》论述行军作战中怎

样安置军队和判断敌情问题；《地形第十》论述用兵作战怎样利用地形的问题，并着重论述深入敌国作战的好处；《九地第十一》进一步论述用兵作战怎样利用地形及统兵之道的问题；《火攻第十二》论述在战争中使用火攻的办法、条件和原则等问题；《用间第十三》论述使用间谍侦察敌情在作战中的重要意义，以及间谍的种类和使用间谍的方法. 《孙子兵法》是体现我国古代军事运筹思想的最早的典籍.它考察了战争中各种依存、制约关系，总结了战争的规律，并依此来研究如何筹划兵力以争取全局的胜利. 书中的语言叙述简洁，内容也很有哲理性，后来的很多将领用兵都受到了该书的影响.《孙子兵法》对中国的文化发展有深远的影响. 2. 孙膑与齐王赛马 孙膑（约公元前380－公元前432），孙武的后世子孙，战国中期的著名军事家. 少时孤苦，年长后从师鬼谷子（著名隐士，精通兵学和纵横学）学习《孙子兵法》十三篇等兵书战策. 庞涓妒孙膑之才而将其骗至魏,施以膑刑(割去膝盖骨).后来乘齐国使团来魏之机，孙膑被齐使秘密接到齐国,并被大将田忌所赏识，留在府中做幕僚，奉为上宾. 孙膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例（记载于《史记·孙子吴起列传》），成为军事上一条重要的用兵规律，即要善于用局部的牺牲去换取全局的

运筹学课后习题答案

第一章 线性规划 1、 由图可得：最优解为 2、用图解法求解线性规划： Min z=2x 1+x 2 ????? ??≥≤≤≥+≤+-01058 2442 12121x x x x x x 解： 由图可得：最优解x=1.6,y=6.4

Max z=5x 1+6x 2 ? ?? ??≥≤+-≥-0 ,23222212 121x x x x x x 解： 由图可得：最优解Max z=5x 1+6x 2, Max z= +∞

Maxz = 2x 1 +x 2 ????? ? ?≥≤+≤+≤0,5242261552121211x x x x x x x 由图可得：最大值?????==+35121x x x ， 所以?????==2 3 21x x max Z = 8.

12 12125.max 2328416412 0,1,2maxZ .j Z x x x x x x x j =+?+≤? ≤?? ≤??≥=?如图所示，在（4，2）这一点达到最大值为2 6将线性规划模型化成标准形式： Min z=x 1-2x 2+3x 3 ????? ??≥≥-=++-≥+-≤++无约束 321 321321321,0,05232 7x x x x x x x x x x x x 解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中 x 3’≥0,x 3’’≥0 Max z ’=-x 1+2x 2-3x 3’+3x 3’’ ????? ? ?≥≥≥≥≥≥-=++-=--+-=+-++0 ,0,0'',0',0,05 232 '''7'''543321 3215332143321x x x x x x x x x x x x x x x x x x x

运筹学 数据模型与决策教材习题答案

教材习题答案 工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示． 表1－ 试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－23所示： 表1－23 【解】 设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 用单纯形法求解得到两个基本最优解 X (1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X (2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为 用单纯形法求解得到两个基本最优解 X (1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X (2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。 图解下列线性规划并指出解的形式： (1) 12 121212 max 2131,0Z x x x x x x x x =-++≥?? -≥-??≥? 【解】最优解X ＝（1/2，1/2）；最优值Z=－1/2

(2) 12 12121 2min 32223120,0 Z x x x x x x x x =---≥-?? +≤??≥≥? 【解】最优解X ＝（3/4，7/2）；最优值Z=－45/4 (3)121212 1212 12min 32211 410 2731 ,0 Z x x x x x x x x x x x x =-++≤??-+≤?? -≤??-≤??≥? 【解】最优解X ＝（4，1）；最优值Z=－10 (4) 12 1212112max 3812223,0 Z x x x x x x x x x =++≤??+≤?? ≤??≥? 【解】最优解X ＝（3/2，1/4）；最优值Z=7/4 (5) ?????? ?≥≤≥≥-+=0 ,6322min 2121212 1x x x x x x x x Z 【解】最优解X ＝（3，0）；最优值Z=3 (6) ?????? ?≥≤≥≥-+=0 ,6322max 21212121x x x x x x x x Z 【解】无界解。 (7)12 121212 min 25262,0Z x x x x x x x x =-+≥?? +≤??≥? 【解】无可行解。 (8) 12 1211212max 2.52280.5 1.5210,0 Z x x x x x x x x x =++≤??≤?? +≤??≥? 【解】最优解X ＝（2，4）；最优值Z=13

运筹学案例分析

. 案例描述西兰物业公司承担了正大食品在全市92 个零售店的肉类、蛋品和蔬菜的运送业务，运送业务要求每天4 点钟开始从总部发货，必须在 7:30 前送完货（不考虑空车返回时间）。这92 个零售点每天需要运送货物0.5 吨，其分布情况为：5 千米以内为A区，有36个点，从总部到该区的时间为20分钟；10千米以内5千米以上的为B区，有26个点，从总部到该区的时间为40分钟；10千米以上的为C区，有30个点，从总部到该区的时间为60 分钟；A 区各点间的运送的时间为5分钟，B区各点间的运送时间为10分钟，C区各点间的运送时间为20 分钟，A 区到B 区的运送时间为20 分钟，B 区到C区的运送时间为20分钟，A区到C区的运送时间为40 分钟。每点卸货、验收时间为30 分钟。该公司准备购买规格为2 吨的运送车辆，每车购价5 万元。请确定每天的运送方案，使投入的购买车辆总费用为最少。 二.案例中关键因素及其关系分析 关键因素： 1. 首先针对一辆车的运送情况作具体分析，进而推广到多辆车的运送情况；

2. 根据案例中的关键点“零售点每天需要运送货物0.5吨” 及“规格为2吨的运送车辆”可知就一辆车运送而言，可承 担4个零售点的货物量； 3. 根据案例中的“运送业务要求每天4点钟开始从总部发货，必须在7:30前送完货(不考虑空车返回时间)”可知每天货物运送的总时间为210分钟，超过该时间的运送方案即为不合理； 4. 如下表以套裁下料的方法列出所有可能的下料防案，再逐 个分析。 三、模型构建 1、决策变量设置 设已穷举的12个方案中方案i所需的车辆数为决策变量Xi (i=1 , 2- 12)，即： 方案1的运送车台数为X1； 方案2的运送车台数为X2； 方案3的运送车台数为沁;

动态规划经典案例详解(背包问题)

动态规划经典案例详解之背包问题 【摘要】本文主要从动态规划经典案例——背包问题的动态规划设计思路出发，结合具体实例，对动态规划在程序设计中的典型应用以及衍生拓展进行详细分析。 【关键字】动态规划信息学奥赛0/1背包问题 动态规划并非一个算法，而是一种解题的思路，其核心思想是通过使用大量的存储空间把中间结果记录下来，大大减少重复计算的时间，从而提高的程序的执行效率，因为信息学奥林匹克复赛题目的解决程序一般是有时间限制的，对于某些用搜索必然耗费大量时间的题目，动态规划几乎是唯一的选择。但是动态规划并没有一个简单的模型可以套用，对于每个不同的题目都有对应的不同规划思路，我们只能通过对一些动态规划经典案例的学习来训练自己的动态规划思维能力，从而以不变应万变，应付各种复杂的程序设计，本文通过对动态规划经典案例之一的背包问题进行详细阐述，旨在让学生了解动态规划和搜索的不同设计思路以及动态规划的优越性。 【原型例题】 从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。求使物品价值最高的选取方法。 【输入文件】 第一行一个数c，为背包容量。 第二行一个数n，为物品数量 第三行n个数，以空格间隔，为n个物品的重量 第四行n个数，以空格间隔，为n个物品的价值 【输出文件】 能取得的最大价值。 【分析】 初看这类问题，第一个想到的会是贪心，但是贪心法却无法保证一定能得到最优解，看以下实例： 贪心准则1：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。而最优解为[0,1,1]，其总价值为30。 贪心准则2：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=[10,20], p=[5,100],c=25。当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。

运筹学模型

第四章 运筹学模型 本章教学重点是： 线性规划模型 目标规划模型 运输模型及其应用 图论模型 最小树问题 最短路问题 最大流问题与最小割 复习要求 1．进一步理解基本建模过程，掌握类比法、图示法以及问题分析、合理假设的内涵。 2．进一步理解数学模型的作用与特点。 本章复习重点是线性规划模型、运输问题模型和目标规划模型。具体说来，要求大家会建立简单的线性规划模型，把实际问题转化为线性规划模型的方法要掌握，当然比较简单。运输问题模型主要要求善于将非线性规划模型转化为运输规化模型，这种转化后求解相当简单。你至少把一个很实际的问题转化为用表格形式写出的模型，至于求解是另外一回事，一般不要求。目标模型一般是比较简单的线性规模模型在提出新的要求之后转化为目标规划模型。这是主要的考虑方向。另外，关于图模型的问题涉及到最短路问题，具体说来用双标号法来求解一个最短路模型。这之前恐怕要善于将一个实际问题转化为图模型。还有一个最小数的问题，该如何把一个网络中的最小数找到。另外在个别场合可能会涉及一笔划问题。 1．营养配餐问题的数学模型为 n n x C x C x C Z 211m in ) ,,2,1(0, ,,22112222212111212111n j x b x a x a x a b x a x a x a b x a x a x a t s j m n mn m m n n n n 或更简洁地表为 n j j j x C Z 1 min ),,2,1,,2,1(01 n j m i x b x a t s j n j i j ij 其中的常数C j 表示第j 种食品的市场价格，a ij 表示第j 种食品含第i 种营养的数量，b i 表示人或动物对第i 种营养的最低需求量. 例1 医院为病人配制营养餐，要求每餐中含有铁不低于50单位，蛋白质不低于40单位，钙不低于42单位．假设仅有两种食品A 和B 可供配餐，相关数据见下表．试问，如何购买两种食品进行搭配，才能即使病人所需营养达到需求，又使总花费最低？

运筹学案例分析

皮革厂租用厂库安排 刘梦瑶 12２11２22 一、研究目的及问题表述 （一）研究目的：在生活中，厂商通常面临货物存储问题，有时便需要租借仓库进行货物存储，而租金也会随着租借时间的长短而有所改变。这时我们就可以运用运筹学算出最优的租借方案，使租金最小，减少存储成本。 （二）1、问题表述:广东黄埔区的某皮革代理商需要寻租可存储采购到的皮革的仓库，并在广州5８同城网上找到了位于黄埔区中心地带的具有６000平方米的高标准仓库。出租商原定价1.2元／平方米/天，后经协商,双方同意如下：租期为两个月可打九折,３个月打八折,4个月打七折，5个月打6.5折。 ２、皮革代理商根据经验预测租赁期间所需仓库大小，其预测结果如下: 第一个月20００平方米；第二个月300０平方米 第三个月2500平方米；第四个月3500平方米 第五个月1600平方米 将租赁合同设为每月初办理,每月签订合同份数不限,每份所选租期不限。求租金最小。 3、将各方条件汇表如下 （三）数据来源：在58同城网上找到相关的仓库租赁信息,其中发现位于黄埔区中心地带,107国道旁有高标准仓库招租,并标明其有600０平方米的仓库可供出租，1.２元/平方米/天。经过在网上联系该出租商，了解到其出租价格为按天数算的短期出租,若存储时间长，可另外折扣。于是我便假定租期为两个月可打九折，3个月打八折，4个月打七折，５个月打6．５折。而由于能力有限,尚未查出有公司或厂商具体需要租借仓库并有具体租借时长与租借大小的数据资料，于是按照课本题目例子,假定了如上的皮革代理商与其的租借要求。 二、方法选择及结果分析 （一）方法选择:该问题的目标能为求租金最小,可用线性函数描述该目标的要求，且有多个方案可选。达到目标具有一定的约束条件，且这些条件可用