运筹学上机实验指导书.doc

运筹学上机实验指导书

运筹学上机实验指导书

重庆交通大学管理学院

目录
绪论
运筹学上机实验软件简介
第一章 运筹学上机实验指导
§1.1 中小型线性规划模型的计算机求解
§1.2 大型线性规划模型的编程计算机求解
§1.3线性规划的灵敏度分析
§1.4运输问题数学模型的计算机求解
§1.5目标规划数学模型的计算机求解
§1.6整数规划数学模型的计算机求解
§1.7 指派问题的计算机求解
§1.8最短路问题的计算机求解
§1.9最大流问题的计算机求解
第二章LINGO软件基础及应用
§2.1 原始集(primitive set)和派生集(derived set)及集的定义
§2.2 LINGO中的函数及目标函数和约束条件的表示
§2.3 LINGO中的数据
§2.4 LINDO简介
第三章 运筹学上机实验及要求
实验一.中小型线性规划模型的求解及Lingo软件的初步使用
实验二.中小型运输问题数学模型的Lingo软件求解。
实验三.大型线性规划模型的编程求解。
实验四.运输问题数学模型的Lingo编程求解。
实验五.分支定界法上机实验
实验六.整数规划、0-1规划和指派问题的计算机求解
实验七：最短路问题的计算机求解
实验八:最大流问题的计算机求解
实验九:运筹学综合实验

绪论
运筹学是研究资源最优规划和使用的数量化的管理科学，它是广泛利用现有的科学技术和计算机技术，特别是应用数学方法和数学模型，研究和解决生产、经营和经济管理活动中的各种优化决策问题。
运筹学通常是从实际问题出发，根据决策问题的特征，建立适当的数学模型，研究和分析模型的性质和特点，设计解决模型的方法或算法来解决实际问题，是一门应用性很强的科学技术。运筹学的思想、内容和研究方法广泛应用于工程管理、工商企业管理、物流和供应链管理、交通运输规划及管理等各行各业，也是现代管理科学和经济学等许多学科研究的重要基础。
在解决生产、经营和管理活动中的实际决策问题时，一般都是建立变量多、约束多的大型复杂的运筹学模型，通常都只能通过计算机软件才能求解，因此，学习运筹学的计算机求解和进行上机实验，就是运筹学教学的重要组成部分。
现在求解各类运筹学模型的软件多种，主要有Microexcel，Matlab，LINDO，LINGO，WinQSB和英国运筹学软件Dash-Xpress。Microexcel主要利用规划求解来解线性规划模型，WinQSB 功能比较齐全，但是主要适合解决规模较小的运筹学模型，英国运筹学软件Dash-Xpress现在在中国的使用率不高，Matlab是通过矩阵的方法解决线性规划，对非线性规划和其它运筹学模型特别是大规模的模型的输入不太方便，。而LINGO和LINDO是使用最广泛的运筹学专业软件，前者功能强大，能解决几乎所有的运筹学优化模型，后者主要功能是线性规划模型的求解。在LINGO中模型的输入和编程都比较方便，可解决大规模的运筹学模型。因此，本课程的教学就是以LINGO为主，适当补充Excel和LINDO作为运筹学上机软件，后者的优势主要在于能获得最优单纯形表以进行更全面地灵敏度分析。
LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。
LINGO全称是Linear INteractive and General Optimizer的缩写---交互式的线性和通用优化求解器。它是一套设计用来帮助您快速,方便和有效的构建和求解线性,非线性,和整数最优化模型的功能全面的工具.包括功能强大的建模语言,建立和编辑问题的 全功能环境,读取和写入Excel和数据库的功能,和一系列完全内置的求解程序.
运行环境： Win9x/NT/2000/XP/2003/Vista/Win7
软件类别： 国外软件/工具软件/计算工具
软件语言： 英文
LINGO 是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。LINGO 提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。 LINGO具有如下的优势：
1． 简单的模型表示
LINGO 可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。LINGO的建模语言允许您使用汇总和下标变量以一种易懂的直观的方式来表达模型，非常类似您在使用纸和笔。模型更加容易构建，更容易理解，因此也更容易维护。
2．方便的数据输入和输出选择
LINGO 建立的模型可以直接从数据库或工作表获取资料。同样地，LINGO 可以将求解结果直接输出到数据库或工作表。使得您能够在您选择的应用程序中生成报告.
3．强大的求解器
LINGO拥有一整套快速的,内建的求解器用来求解线性的,非线性的(球面&非球面的),二次的,二次约束的,和整数优化问题.您甚至不需要指定或启动特定的求解器,因为LINGO会读取您的方程式并自动选择合适的求解器.
4. 交互式模型或创建Turn-key应用程序
您能够在LINGO内创建和求解模型,或您能够从您自己编写的应用程序中直接调用LINGO.对于开发交互式模型,LINGO提供了一整套建模环境来构建,求解和分析您的模型.对于构建turn-key解决方案,LINGO提供的可调用的DLL和OLE界面能够从用户自己写的程序中被调用.LINGO也能够从Excel宏或数据库应用程序中被直接调用.
5. 广泛的文件和 HELP 功能
安装好了的LINGO，启动后的界面如下图1所示，即可输入求解运筹学模型的程序。

图1

第一章 运筹学上机实验指导
§1.1 中小型线性规划模型的计算机求解
对于小型线性规划模型的求解，LINGO中可以用一种及线性规划的数学模型及其类似的方式直接输入模型来求解，简单方便。
例1.1 求解下面的线性规划
max z=2x1+3x2
x1+2x2≤8
4x1 ≤16
4x2≤16
x1，x2≥0
LINGO中的输入的代码如图2所示，这种输入方式的优势在于适合LINDO系统。

图2

注1：LINGO中输入的代码和线性规划模型的差异如下：
(1) max z→max,min z→min；
(2) 每一行(包括目标函数)用英文的分号结束；
(3) 数及变量的乘积用*表示；
(4) 不等号≤和≥用<=和>=或<和>表示；
(5) LINGO系统默认所有的变量非负，因此非负变量的约束可省略，而非正变量和自由变量要用x1<=0和@free(x2)表示；
(6) LINGO中不能输入下标，x1→x1。

图3

注2：例1.1的模型求解还可以按图4的方式输入代码求解。此时LINGO中输入的代码和线性规划模型的除注1的相关差异外，还有如下不同：
(1) 数及变量的乘积，乘号用空格表示；
(2) 约束条件之前用s.t.或subject to表示后面是约束；
(3) 每行后面不用分号结束；
(4) 这种输入法的好处是和LINDO的输入一致，可以直接在LINDO中求解，做灵敏度分析较方便，也能得到最优单纯形表。

图4

点菜单栏的LINGO→Solver，或直接点工具栏上的 ，可得求解结果即解的状况(Solver Status)和解报告(Solution Report)：

图5

关于图5的Solver Status的注释如下：
(1) Model(模型) LP(线性规划Linear programming，其它模型还有非线性规划NLP(Nonlinear programming )，整数线性规划ILP(Integer)，整数非线性规划 INLP)
(2) State(状态) Global Opt(整体最优解Global optimal solution，线性规划的最优解都是整体最优解，非线性规划有局部最优解(Local Opt)和整体最优解之分，其它状态还有无可行解(Infeasible)图7和无界解(Unbounded) 图8)
(3) Objective，目标函数值为14，由于处于最优解状态，所以这里表示最优值为14。
(4) Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解。
(5) Iteration 1，表示迭代了1步求得最优解。
(6) Extended Solver Status，表示扩展的解的状况，主要用于整数规划和非线性规划。
(7) Variables，表示变量，Total 2，表示总决策变量2个，非线性(Nonlinear)变量和整数(Integer)变量都是0个。
(8) Constraints，表示约束，Total 4，表示包括目标函数一共4个约束，非线性(Nonlinear)约束0个。
(9) Nonzeros，表示非零系数，Total 6，表示包括目标函数和约束条件中变量的非零系数6个，右端常数项不算。

图6

图7

图8

关于图6的Solution Report的注释如下：
(1) Global optimal solution found.整体最优解被找到。
(2) Objective value: 14.00000.最优值为14。
(3) Total solver iterations: 1.求解的总迭代步数为1步。
(4) Variable Value Reduced Cost
X1 4.000000 0.000000
X2 2.000000 0.000000
最优解的变量X1=4.000000，X2 2.000000。
(5) Reduced Cost：表示减少的成本，即最小化问题的最优目标函数中各变量的检验数，即在其它变量不变时，该变量减少一个单位，目标费用减少的数量如图8。对于最大化问题，是最优目标函数中各变量的检验数的相反数，表示当该变量增加一个单位时目标函数减少的数量如图9。这里由于上面X1和X2为取值非零的基变量，所以检验数为零。Reduced Cost为在最优解时，最小化问题中变量的检验数，最大化问题中变量检验数的相反数。
(6) Row Slack or Surplus Dual Price
1 14.00000 1.000000
2 0.000000 1.500000
3 0.000000 0.1250000
4 4.000000 0.000000
Slack or Surplus表示松弛或剩余变量，即将最优解带入各个约束条件后，左边比右边小的或大的数量，表示在最优方案中，剩余或超过的资源数量。注意，这里第一行表示目标函数，其松弛或剩余变量和对偶价格都没有意义。
(7) Dual Price，对偶价格，即最大化问题中对偶变量的最优解的值如图9所示，对于最小化问题，对偶价格为对偶变量的最优解的值的相反数。

图9

图10
例1.2 求解下面线性规划的数学模型
min z=-3x1+4x2-2x3+5x4;
4x1-x2+2x3-x4=-2;
x1+x2+3x3-x4≤14;
-2x1+3x2-x3+2x4≥2;
x1,x2,x3≥0,x4无约束;
LINGO中输入如下的代码：
min =-3*x1+4*x2-2*x3+5*x4;
4*x1-x2+2*x3-x4=-2;
x1+x2+3*x3-x4<=14;
-2*x1+3*x2-x3+2*x4>=2;
@free(x4);
求解可得解报告：
Global optimal solution found.
Objective value: 2.000000
Total solver iterations: 0
Variable Value Reduced Cost
X1 0.000000 15.50000
X2 8.000000 0.000000
X3 0.000000 8.500000
X4 -6.000000 0.000000
Row Slack or Surplus Dual Price
1 2.000000 -1.000000
2 0.000000 4.500000
3 0.000000 0.5000000
4 10.00000 0.000000

§1.2 大型线性规划模型的编程计算机求解
教学过程中所见到的运筹学模型大多是小型的，但是，在解决生产和经营管理活动中的实际时，建立的通常是含有很多和变量和约束条件的模型，用前面的方法，经常要花费大量的时间来输入代码或模型，下面介绍编程的方法，对于解决大型复杂的模型，效果显著。
下面是求解例1的线性规划的LINGO程序。
例2.1 用LINGO编程求解例1.1的线性规划模型
!定义变量及常量，给出了值的为常量;
sets:
is/1..3/:b;
js/1..2/:c,x;
links(is,js):a;
endsets
!目标函数;
max=@sum(js(J):c(J)*x(J));
!约束条件;
@for(is(I): @sum(js(J):a(I,J)*x(J))<=b(I));
!指定常量的值;
data:
!直接输入数据;
c=2 3;
b=8 16 12;
a=1 2
4 0
0 4;
end data
end
求解可得Solution Report
Global optimal solution found.
Objective value: 14.00000
Total solver iterations: 1
Variable Value Reduced Cost
B( 1) 8.000000 0.000000
B( 2) 16.00000 0.000000
B( 3) 12.00000 0.000000
C( 1) 2.000000 0.000000
C( 2) 3.000000 0.000000
X( 1) 4.000000 0.000000
X( 2) 2.000000 0.000000
A( 1, 1) 1.000000 0.000000
A 1, 2) 2.000000 0.000000
A( 2, 1) 4.000000 0.000000
A( 2, 2) 0.000000 0.000000
A( 3, 1) 0.000000 0.000000
A( 3, 2) 4.000000 0.000000

Row Slack or Surplus Dual Price
1 14.00000 1.000000
2 0.000000 1.500000
3 0.000000 0.1250000
4 4.000000 0.000000
这里以!开始和分号结束的语句为注释语句，该程序的求解方法和解报告及小型模型类似，只是编程的解报告会把所有的系数也表述出来而已。
从例3可以看出，一个LINGO的程序由四个部分组成。
1. 以“sets:”开始，以“endsets”结束的语句定义模型中出现的变量集。
2. 以sets中定义的变量和常量来表达目标函数。
3. 以sets中定义的变量和常量来表达全部的约束条件。
4. 以“data:”开始，以“end data”结束的语句给常量指定数值。
第二章详细解释每一部分的含义及如何表达对应的数学模型。
例2.2 求解下面线性规划的数学模型;
min z=-3x1+4x2-2x3+5x4;
4x1-x2+2x3-x4=-2;
x1+x2+3x3-x4≤14;
-2x1+3x2-x3+2x4≥2;
x1,x2,x3≥0,x4无约束;
编程如下：
!定义变量及常量，给出了值的为常量;
sets:
is/1..3/:b;
js/1..4/:c,x;
links(is,js):a;
endsets
!目标函数;
min=@sum(js(J):c(J)*x(J));
!约束条件;
@sum(js(J):a(1,J)*x(J))=b(1);
@sum(js(J):a(2,J )*x(J))<=b(2);
@sum(js(J):a(3,J)*x(J))>= b(3);
!自由变量;
@free(x(4));
!指定常量的值;
data:
c=-3 4 -2 5;
b=-2 14 2;
a=4 -1 2 -1
1 1 3 -1
-2 3 -1 2;
end data
!结束;
end
求解可得解报告：
Global optimal solution found.
Objective value: 2.000000
Total solver iterations: 2
Variable Value Reduced Cost
B( 1) -2.000000 0.000000
B( 2) 14.00000 0.000000
B( 3) 2.000000 0.000000
C( 1) -3.000000 0.000000
C( 2) 4.000000 0.000000
C( 3) -2.000000 0.000000
C( 4) 5.000000 0.000000
X( 1) 0.000000 15.50000
X( 2) 8.000000 0.000000
X( 3) 0.000000 8.500000
X( 4) -6.000000 0.000000
A( 1, 1) 4.000000 0.000000
A( 1, 2) -1.000000 0.000000
A( 1, 3) 2.000000 0.000000
A( 1, 4) -1.000000 0.000000
A( 2, 1) 1.000000 0.000000
A( 2, 2) 1.000000 0.000000
A( 2, 3) 3.000000 0.000000
A( 2, 4) -1.000000 0.000000
A( 3, 1) -2.000000 0.000000
A( 3, 2) 3.000000 0.000000
A( 3, 3) -1.000000 0.000000
A( 3, 4) 2.000000 0.000000
Row Slack or Surplus Dual Price
1 2.000000 -1.000000
2 0.000000 4.500000
3 0.000000 0.5000000
4 10.00000 0.000000

§1.3线性规划的灵敏度分析
在求解了一个线性规划的模型的时候如果是编程输入的模型，还可以通过LINGO中的命令显示线性规划的数学模型。
例3.1 通过图和图的操作，可显示例2.1LINGO程序的数学模型。

图11

图12

图13

MODEL:
[_1] MAX= 2 * X_1 + 3 * X_2 ;
[_2] X_1 + 2 * X_2 <= 8 ;
[_3] 4 * X_1 <= 16 ;
[_4] 4 * X_2 <= 12 ;
END
只是系统默认的非负约束没有显示，下图表明自由变量和非正变量都会显示出来。

图14

下面的图演示了对线性规划的灵敏度分析
首先求解一个线性规划模型，然后选中“prices & Ranges”

图15

然后在菜单LINGO→Ranges

图16

点击Ranges，得到在最优基或最优解不变时，单个价值系数和右端系数变化范围的灵敏度分析结果。

图17

Ranges in which the basis is unchanged:

Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
X( 1) 2.000000 INFINITY 0.5000000
X( 2) 3.000000 1.000000 3.000000

Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 8.000000 2.000000 4.000000
3 16.00000 1600000 8.000000
4 12.00000 INFINITY 4.000000
LINDO中也可以作灵敏度分析，一般在求解了线性规划模型后，自动出现是否进行灵敏度分析的对话框，如图

图18

点击“是”，就可得解和灵敏度分析报告：
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 14.00000
VARIABLE VALUE REDUCED COST
X1 4.000000 0.000000
X2 2.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 1.500000
3) 0.000000 0.125000
4) 4.000000 0.000000
NO. ITERATIONS= 2
RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 2.000000 INFINITY 0500000
X2 3.000000 1.000000 3.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 8.000000 2.000000 4.000000
3 16.000000 16.000000 8.000000
4 12.000000 INFINITY 4.000000
§1.4运输问题数学模型的计算机求解
1. 中小型运输问题的求解
中小型运输问题可以和小型线性规划一样，直接输入运输问题的数学模型代码求解。
例4.1 求解下面运输问题的数学模型
单
位 销地
运
价
产地
B1
B2
B3
B4
产量
A1
3
11
3
10
7
A2
1
9
2
8
4
A3
7
4
10
5
9
销量
3
6
5
6

LINGO中的输入代码为：
min=3*x11+11*x12+3*x13+10*x14+x21+9*x22+2*x23+8*x24+7*x31+4*x32
+10*x33+5*x34;
x11+ x12+ x13+ x14 = 7;
x21+ x22+ x23+ x24 = 4;
x31+ x32+ x33+ x34 = 9;
x11+ x21+ x31= 3;
x12+ x22+ x32 = 6;
x13+ x23+ x33 = 5;
x14+ x24+ x34 = 6;
求解可得:
Global optimal solution found.
Objective value: 83.00000
Total solver iterations: 0
V Variable Value Reduced Cost
X11 0.000000 0.000000
X12 0.000000 2.000000
X13 5.000000 0.000000
X14 2.000000 0.000000
X21 3.000000 0.000000
X22 0000000 2.000000
X23 0.000000 1.000000
X24 1.000000 0.000000
X31 0.000000 9.000000
X32 6.000000 0.000000
X33 0.000000 12.00000
X34 3.000000 0.000000

Row Slack or Surplus Dual Price
1 85.00000 -1.000000