运筹学实验指导书 - 图文

《运筹学》

实验指导书

（第一版）

李丰兵 编

桂林电子科技大学 数学与计算科学学院 2007年3月20日

运筹学实验指导书

实验一 运输问题算法实现

一、实验目的

1. 熟悉运输问题的表上作业法； 2. 掌握运输问题的WinQSB软件求解； 3. 了解运输问题的Lingo软件求解。

二、实验课时：4个课时 三、实验准备

1、学会建立运输问题的数学模型； 2、熟悉运输问题表上作业法；

3、熟悉WinQSB软件的基本操作。 4、熟悉Lingo软件建模。

四、实验内容

根据下列实际问题，建立运输问题的数学模型，并用WinQSB软件进行求解。

实例1（产销平衡问题）：现有A1,A2,A3三个产粮区，可供应粮食分别为10,8,5（万吨），欲将这些粮食运往B1,B2,B3,B4四个地区，其需求量分别为5,7,8,3（万吨）。产粮地到需求地的运费价钱（元/吨）如下表所示。问如何安排一个运输计划，使得总运费最少（建立模型并求解）。

实例2（产销不平衡问题，求运费最小）（建立模型并求解）

lfb 第 1 页 2014-12-8

运筹学实验指导书

实例3（需求量不确定问题，求运费最小）（建立模型并求解，不写在报告上）

五、实验主要步骤

1、安装WinQSB1.0（或以上版本）及lingo8.0（或以上版本）；

2、用WinQSB软件求解上述运输问题，记录实验结果（实验报告数据）； 3、试用Lingo软件求解上述问题。 4、撰写实验报告。

六、实验报告的撰写要求

1. 实验报告需打印出来；

2. 写出实验课程名称、课号，任课老师； 3. 写出姓名、学号、日期； 4. 写出实验目的、实验内容；

5. 对第一，第二个问题，建立数学模型，写出实验结果（求解结果表单及其网络图形）； 6. 写出上述三个问题的Lingo模型（课堂做，但不写在试验报告上）； 7. 写出心得体会

七、用WinQSB或lingo软件求解实例

实例4：某运输资料如下表所示：

lfb

第 2 页

2014-12-8

运筹学实验指导书

方法一：用WinQSB求解

从开始菜单程序里找到WinQSB程序，然后打开

打开Network Modeling程序后，打开file菜单下的New Problem子菜单，进行如下选择

lfb 第 3 页 2014-12-8

运筹学实验指导书

点击OK,弹出数据输入表单，输入数据，如下所示：

单击菜单：Solve and Analyze的子菜单Solve the Problem，并弹出如下求解结果表单：

关闭该表单后，单击菜单：Results的子菜单Graphic Solution，即弹运输问题最优求解方案的网络图，如下所示：

lfb 第 4 页 2014-12-8

运筹学实验指导书

单击菜单：Solve and Analyze的子菜单Solve the Problem，并弹出如下求解结果表单：

由此表可看到满意解同图解法相同。也可以从菜单Results下的Solution summary子菜单查看简洁的求解报告，如下：

另还可在最后一行看到（Alternate Solution exists!! ），说明还存在其它的满意解。单击菜单Results下子菜单Obtain Alternate Optimal即可得另一满意解。

lfb

第 10 页

2014-12-8

运筹学实验指导书

下面用Lingo软件进行求解

第一步：求第一级目标的最优解，建立如下Lingo模型

model: min=d11;

30*x1+12*x2+d11-d12=2500; 2*x1+x2+d21-d22=140; x1+d31-d32=60; x2+d41-d42=100; end

运行结果如下：

Global optimal solution found at iteration: 0 Objective value: 0.000000

Variable Value D11 0.000000 X1 83.33333 X2 0.000000 D12 0.000000 D21 0.000000 D22 26.66667 D31 0.000000 D32 23.33333 D41 100.0000 D42 0.000000

Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000

lfb 第 11 页 2014-12-8

运筹学实验指导书

4 0.000000 5 0.000000

第二步：求第二级目标的最优解，建立如下Lingo模型

model:

min=2.5*d32+d42;

30*x1+12*x2+d11-d12=2500; 2*x1+x2+d21-d22=140; x1+d31-d32=60; x2+d41-d42=100; d11=0; end

运行结果如下：

Global optimal solution found at iteration: 4 Objective value: 0.000000

Variable Value D32 0.000000 D42 0.000000 X1 60.00000 X2 58.33333 D11 0.000000 D12 0.000000 D21 0.000000 D22 38.33333 D31 0.000000 D41 41.66667

Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000

第三步：求第三级目标的最优解，建立如下Lingo模型

model: min=d22;

30*x1+12*x2+d11-d12=2500; 2*x1+x2+d21-d22=140; x1+d31-d32=60; x2+d41-d42=100;

lfb 第 12 页 2014-12-8

运筹学实验指导书

d11=0;

2.5*d32+d42=0; end

运行结果如下：

Global optimal solution found at iteration: 4 Objective value: 38.33333

Variable Value D22 38.33333 X1 60.00000 X2 58.33333 D11 0.000000 D12 0.000000 D21 0.000000 D31 0.000000 D32 0.000000 D41 41.66667 D42 0.000000

Row Slack or Surplus 1 38.33333 2 0.000000 3 0.000000

4 0.000000 5 0.000000 6 0.000000 7 0.000000 由此可得满意解：

可看出，Lingo软件求解的只是其中一个满意解。

lfb 第 13 页 2014-12-8

运筹学实验指导书

实验三 最大流及最小费用最大流问题算法实现

一、实验目的

1. 掌握最大流及最小费用最大流问题的数学建模；

2. 掌握最大流问题的WinQSB软件求解和Lingo软件求解；

3. 掌握最小费用最大流问题问题的的WinQSB软件求解和Lingo软件求解。

二、实验课时：4个课时 三、实验准备

1、熟悉建立最大流问题的数学模型；

2、熟悉建立最小费用最大流问题的数学模型； 3、熟悉WinQSB软件的基本操作。 4、熟悉Lingo软件建模。

四、实验内容

根据下列实际问题，建立相应的数学模型，并用WinQSB软件或Lingo软件进行求解。

实例1（最大流问题）：下图为一个某产品的运输网络，其中S为某产品的生产基地，T为该产品的销售基地，A,B,C,D为四个不同的中转站，箭头表示运输方向，其旁边的数字表示该路线的最大运输能力。现要求制定一个运输方案，使得尽可能多的产品从产地S运往销售基地T。（建立数学模型，并求解）

实例2（最大流问题）下图同样是某产品的运输网络图，情况和实例相似，只是网络的结构不相同，求S到T的最大流。（建立数学模型，并求解）

lfb

第 14 页

2014-12-8

运筹学实验指导书

实例3（最小费用流问题）为下图从S到T制定一个费用最小的运输方案，其中流量指定为15。（建立数学模型，并求解）

说明：每条弧旁边括号内第一个数为容量，第二个数为单位流量的运费。

实例4（最小费用最大流问题）为下图从S到T制定一个流量最大费用最小的运输方案。（建立数学模型，并求解，该图与实例三相同）

说明：每条弧旁边括号内第一个数为容量，第二个数为单位流量的运费。

五、实验主要步骤

1、安装WinQSB1.0（或以上版本）及lingo8.0（或以上版本）；

2、用WinQSB软件Network Modeling程序求解上述四个实例问题，记录实验结果； 3、建立数学模型，试用Lingo软件求解上述问题。 4、撰写实验报告。

六、实验报告的撰写要求

1. 写出实验课程名称、课号，任课老师； 2. 写出姓名、学号、日期； 3. 写出实验目的、实验内容；

4. 对上述四个实际问题，写出实验结果（求解结果表单及其网络图形）； 5. 写出上述四个问题的Lingo模型（可不做）； 6. 写出心得体会

七、用WinQSB或lingo软件求解实例

实例讲解1（最大流问题）：下图是一石油运输网络，S,A,B,C,D,T为六个城市，现需要

lfb 第 15 页 2014-12-8

运筹学实验指导书

将城市S库存的石油运往城市T的化工厂，箭头符号表示两个城市间存在石油管道，其旁边的数字表示该管道容量，求城市S到城市T的最大流。

方法一：用WinQSB软件求解

第一步：打开Network Modeling程序，选择Maximal Flow Problem选项，其他如下图所表示。点OK进入下一步。

第二步：输入网络模型数据如下表

lfb

第 16 页

2014-12-8

运筹学实验指导书

第三步：运行程序，点Solve and Analyze→Solve the Problem，并选择初始点和结束点， 即得运行结果如下表

由此表可看出各节点之间的流值和从S到T的最大流值。 第四步：（图解法）点Results→Graphic Solution, 即可把求解结果以图形的方式表示出来，如下图所示。

方法二：用Lingo软件求解 由已知建立如下数学模型：

maxfs..t?i,j??Aj?V?fij??j,i??Aj?V??f,i?S?fji???fi?T

?0i?S,T?0?fij?cij,?i,j??ALingo模型:

model: sets:

nodes/S,A,B,C,D,T/; arcs(nodes,nodes)/

S,A S,B A,B,A,C B,D C,B,C,T, D,C D,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;

@sum(arcs(i,j)|j#eq#@size(nodes):f(i,j))=flow; @for(arcs:@bnd(0,f,C)); end

lfb 第 17 页 2014-12-8

运筹学实验指导书

运行结果（部分数据）：

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

Variable Value Reduced Cost

F( S, A) 7.000000 0.000000 F( S, B) 7.000000 0.000000 F( A, B) 2.000000 0.000000 F( A, C) 5.000000 0.000000 F( B, D) 9.000000 -1.000000 F( C, T) 5.000000 -1.000000 F( D, T) 9.000000 0.000000

实例讲解2（最小费用最大流问题）（续上例）若再考虑每条管道的运输费用，如下图所示，括号内第一个数字为管道容量，第二个数字为流的单位运输费用。此时，求该运输网络的最小费用最大流。

由该图建立数学模型

min?i,j??A?eijfij?fmax,i?S?fji???fmaxi?T

?0i?S,T?s..tj?V?i,j??A?fij?j?V?j,i??A?0?fij?cij,?i,j??A其中eij表对应管道的流的单位运费，cij表对应管道的容量，fij（未知）表对应管道的流量，最大流由上例可知fmax?14，由此建立Lingo模型如下：

model: sets:

nodes/S,A,B,C,D,T/; arcs(nodes,nodes)/

S,A S,B A,B,A,C B,D C,B,C,T, D,C D,T/:C,f,e;

lfb 第 18 页 2014-12-8

运筹学实验指导书

endsets data:

C=8 7 5 9 9 2 5 6 10; e=2 8 5 2 3 1 6 4 7; enddata

min=@sum(arcs:e*f);

@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))=14;

@sum(arcs(i,j)|j#eq#@size(nodes):f(i,j))=14; @for(arcs:@bnd(0,f,C)); end

运行结果（部分数据）：

Global optimal solution found at iteration: 0 Objective value: Variable Value Reduced Cost F( S, A) 8.000000 -1.000000 F( S, B) 6.000000 0.000000 F( A, B) 1.000000 0.000000 F( A, C) 7.000000 0.000000 F( B, D) 9.000000 0.000000 F( C, B) 2.000000 -2.000000 F( C, T) 5.000000 -7.000000 F( D, T) 9.000000 0.000000

lfb 第 19 页

2014-12-8

205.0000

运筹学实验指导书

实验四 网络优化算法实现（综合性实验）

一、实验目的

1. 掌握最小树的数学模型创建方法及其软件求解； 2. 掌握最短路问题数学模型创建方法及其软件求解； 3. 掌握TSP问题的软件求解；

4. 掌握动态规划的建模方法及软件实现。

二、实验课时：4个课时 三、实验准备

1、熟悉最小树问题的数学模型创建方法； 2、熟悉最短问题的数学模型创建方法； 3、熟悉动态规划原理及其模型创建； 3、熟悉WinQSB软件的基本操作。 4、熟悉Lingo软件建模。

四、实验内容

根据下列实际问题，建立相应的数学模型，并用WinQSB软件或Lingo软件进行求解。 实例1（最小树问题）下图中S表示一自来水公司，A,B,C,D,E表示5个不同的自来水用户，线段旁边的数字表示距离，请为自来水公司选择一种安装方案，使得安装水管最短。

图4.1

实例2（最短路问题）下图（图4.2）中S,A,B,C,D,E,T表示7不同的城市，现欲在城市S到城市T之间架一条高压线，数字表示两城市间架高压线的费用，请为该项目选择一种方案，使得总的费用最小。

实例3（最小树问题） 下图（图4.3）为某城市各乡镇地理位置分布图。数字1表示市中心，2~10表示各乡镇。现要设计一个供气系统，使得从市中心到各乡镇都有一条管道相通，并且铺设管道要尽可能少。表4.1给出了各点之间的距离。请为该项目设计一套方案。

实例4（TSP问题）（续实例3）若某公司计划在该地区做宣传，宣传员需从市中心出发，经过所有乡镇，再回到市中心。为节约开支，公司希望宣传员走过的总距离最短。请为该公司设计一套路线。

lfb

第 20 页

2014-12-8

运筹学实验指导书

图4.2

图4.3 表4.1

1 2 3 4 5 6 7 8 9 2 8 3 5 9 4 9 15 7 5 12 17 9 3

lfb

第 21 页

2014-12-8

6 14 8 11 17 8 7 12 11 7 10 10 9 8 16 18 12 7 6 14 8 9 17 14 12 15 15 8 6 11 10 22 22 17 18 15 16 11 11 10 运筹学实验指导书

五、实验主要步骤

1、安装WinQSB1.0（或以上版本）及lingo8.0（或以上版本）；

2、用WinQSB软件求解上述运输问题，记录实验结果（实验报告数据）； 3、试用Lingo软件求解上述问题。 4、撰写实验报告。

六、实验报告的撰写要求

1. 写出实验课程名称、课号，任课老师； 2. 写出姓名、学号、日期； 3. 写出实验目的、实验内容；

4. 对上述四个实际问题，写出实验结果（至少选两个）； 5. 写出上述四个问题的Lingo模型（可不做）； 6. 写出心得体会

七、用WinQSB几lingo软件求解实例（略）

lfb 第 22 页 2014-12-8

本文来源：https://www.bwwdw.com/article/ceqo.html