《运筹学B》实验指导书
(第二版)
南昌航空大学数信学院应用数学系
邱根胜编
2011年09月
目录
实验１、用Lingo求解最短路、最小树问题 (4)
实验2、用Lingo求解最大流、最小费用流问题 (11)
实验3、利用Lingo求解排队与存贮模型 (16)
实验4、利用数学软件求解对策论问题 (30)
实验5、运筹学综合应用 (37)
一、授课对象
四年制本科数学与应用数学、信息与计算科学专业。
二、课程类型
专业选修课
三、实验的性质、目的与任务
1、实验性质
《运筹学B》实验是一门重要的专业课实验。要求通过上机实验，使学生了解运筹学中的网络优化、排队论、对策论等在实际中的应用，了解运筹学解决实际问题的基本方法，培养建模能力和计算机应用能力。
2、实验的目的
培养与提高学生分析问题和解决问题的能力、自学能力，利用运筹学和数学软件求解实际问题的能力，以及程序设计能力。
3、实验的任务
应用Matlab、lindo/lingo求解网络优化模型、排队与存储模型、对策论模型等，加深对运筹学方法的理解，并初步具有利用运筹学和计算机软件解决实际问题的能力。
五、实验内容与实验要求
实验一、用Lingo求解最短路、最小树问题
实验要求：
1、了解Lingo软件求解一般数学规划的方法；
2、理解最短路问题和最小树的数学规划模型。
实验二、用Lingo求解最大流、最小费用流问题
实验要求：
1、熟悉Lingo软件求解一般数学规划的方法；
2、熟悉最大流、最小费用流问题的数学规划模型；
3、掌握利用Lingo求解最大流、最小费用流问题的数学模型的用法。
实验三、利用Lingo求解排队与存贮模型
实验要求：
1、理解排队论与存贮论中的几个基本模型；
2、利用Lingo求解排队与存贮模型。
实验四、利用数学软件求解对策论问题
实验要求：
1、了解将对策论模型转化为数学规划模型的方法；
2、利用Lingo求解对策论模型。
实验四、运筹学综合应用
本实验为综合性实验，主要内容为对一个实际问题，能利用运筹学建立模型，并利用计算机编程求解，培养学生数学建模的能力和计算机应用能力。
实验要求：
1、根据要求选取一个实际问题，利用运筹学知识，建立实际问题的数学模型；
2、利用数学软件求解模型，并对结果进行分析、讨论，最后给出问题的解决方案；
3、写出实验报告。
注：从12学时的实验内容中选择8学时的实验内容，其中有一个综合性实验。
六、主要参考书
[1] 谢金星，薛毅编著，《优化建模与LINDO/LINGO》，清华大学出版社,2005年7月。
[2]《运筹学》教材编写组编，《运筹学》（第三版），清华大学出版社，2005年6月，
[3] 姜启源,邢文训,谢金星等，《大学数学实验》，清华大学出版社，2005年。
[4] 胡运权主编，《运筹学教程》（第三版），清华大学出版社，2007年。
实验一：用Lingo 求解最短路、最小树问题及旅行商问题 一、实验目的
通过本实验熟悉Lingo 软件中的集合、运算、编辑等命令,了解最短路、最小生成树和旅行商问题的数学规划模型；能利用最短路和最小生成树建立实际问题的数学模型，并利用Lingo 求解。 二、例题
(1)最短路问题 假设有向图有n 个顶点。现需要求从顶点V 1到顶点V n 的最短路。设决策变量为ij x ，当1=ij x ，说明弧(V i ,V j )位于顶点V 1到顶点V n 的最短路上;否则0=ij x ，则求V1到V n 的最短路的数学模型为：
(P1) E
V V x n
i n
i i x x t s x w
j i ij n
E V V j ji n
E V V j ij E
V V ij
ij
i j j i j i ∈≥⎪⎩⎪
⎨⎧≠=-==-∑∑∑∈=∈=∈),(,0,1,0,11
,1..min
),(1),(1),(
其中E 为有向图的所有弧的集合,ij w 为弧(Vi,Vj)的权.
例题1-1 在下图中,用点表示城市,现有A ，B1，B2，C1，C2，C3，D 共7个城市，点与
点之间的连线表示城市间有道路相连，连线旁的数字表示道路的长度。现计划从城市A
到称市D 铺设一条天然气管道，请设计出最小价格管道铺设方案。
解：
Lingo 求解程序为：
! We have a network of 7 cities. We want to find
the length of the shortest route from city 1 to city 7; sets :
C1
! Here is our primitive set of seven cities; cities/A, B1, B2, C1, C2, C3, D/;
! The Derived set "roads" lists the roads that exist between the cities; roads(cities, cities)/
A,B1 A,B2 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3 C1,D C2,D C3,D/: w, x; endsets data :
! Here are the distances that correspond to above links; w = 2 4 3 3 1 2 3 1 1 3 4; enddata
n=@size (cities); ! The number of cities; min =@sum (roads: w*x);
@for (cities(i) | i #ne# 1 #and# i #ne# n:
@sum (roads(i,j): x(i,j)) = @sum (roads(j,i): x(j,i))); @sum (roads(i,j)|i #eq# 1 : x(i,j))=1;
运行得到非零解为：
X( A, B1) 1.000000 0.000000 X( B1, C1) 1.000000 0.000000 X( C1, D) 1.000000 0.000000 即最短路为：A-B1-C1-D ，最短路长为6
(2)最小生成树问题
设无向图是连通的，且互不包有圈，则称该图为树。如果有向图中任何一点都可由某一个顶点V 1到达，则称1V 为图G 的根。如果有向图G 有根。且关于它的基础图是树，则称G 为有向树。 若'
G 是包含G 的全部顶点的子图，它又是树，则称'
G 的生成树。若图(,)G V E 是一个连通赋权图，T 是G 的一颗生成树，T 的每条边所赋权的和称为树T 的权，称具有最小权的生成树为G 的最小生成树。
例1-2 假设某电力公司在7个村庄之间架设电线，各村庄之间的距离如下图所示，试求出使电线
总长度最小的架线方案。
