《运筹学》上机实验报告
学院机电工程学院
专业工业工程
指导教师吴小东
班级工业10-1班
学生姓名林金铎
学生学号 10024090146 实验时间 2012-2013学年第一学期
实验一 使用LINGO 求解线性规划问题
班级:工业10-1班 姓名:林金铎 学号:10024090146 评阅成绩: 已知如下线性规划模型:
123max 303540z x x x =++
1231231231233251823412229,,0
x x x x x x x x x x x x ++≤??++≤??++≤??≥? 一、利用集的方法编写上述线性规划模型的LINGO 程序。
在LINGO 软件模型中编写本题的程序如下图1-1所示所示。
图1-1 LINGO 模型窗口截图
点击LINGO 菜单下的Solve 选项,LINGO 软件求解所输入的模型,得到LINGO 运行状态窗口如图1-2所示
图1-2 LINGO运行状态窗口截图
运行结束后,关闭LINGO运行状态窗口,获得LINGO软件的结果报告窗口,如图1-3、1-4所示。
图1-3 LINGO结果报告窗口截图(一)
图1-4 LINGO结果报告窗口截图(二)
二、根据编写的程序,回答以下问题:
1、哪些是原始集?
答:var(j), const(i)是原始集
2、哪个是派生集?该派生集是稠密集还是稀疏集?该派生集有多少个成员?
答:A(i,j)是派生集,属于稠密集合,共有9个成员
3、属性值“5”是属于成员(b1,x3)还是(b3,x1)的属性值?
答:属于成员(b1,x3)的属性值
三、根据程序的运行结果,回答以下问题:
1、全局最优值是否已经找到?该值是多少?
答:已经找到,最优值为165
2、该模型求解一共迭代了多少次?
答:共迭代了2次
3、在求解结果的界面中,Variable、Value、Reduced Cost、Row、Slack or Surplus 和Dual Price分别表示什么?
答:Variable表示运算时各定义变量的取值;
Value表示给出最优解中各变量的值;
Reduced Cost表示列出最优单纯形表中判别数所在行的变量的系数,表示当变量有微小变动时, 目标函数的变化率;
Row表示行数;
Slack or Surplus 表示给出松驰变量的值;
Dual Price表示当对应约束有微小变动时, 目标函数的变化率。输出结果中对应于每一个约束有一个对偶价格。若其数值为p,表示对应约束中不等式右端项若增加1 个单位,目标函数将增加p个单位。
4、找出一个基变量,指出其判断系数并说明该判断系数的含义。
答:例如基变量B(1),其判断系数是0,表示当基变量B(1)发生微小变化时最大值Z的变化率为0。
5、指出松弛变量或剩余变量为0和非0的约束各一个,指出相应的对偶价格,并指出对偶价格的含义(如果没有,请说明)。
答:第一行松弛变量=150,对偶价格=1,其含义为当不等式右端增加1个单位时,最大值Z也相应的增加1个单位。
第3行松弛变量=0,对偶价格=5,其含义为当不等式右端增加1个单位时,目标函数Z就会增加5个单位。
6、对偶价格与松弛变量或剩余变量有什么关系规律?
答:假设对偶价格的数值为p,表示对应约束中不等式右端项增加1 个单位,目标函数将增加p个单位,即此时的松弛变量应该在原基础上再加p。
四、实验小结与体会
通过运筹学的实验学习,我对有关运筹学建模问题有了更深刻的认识和把握;对运筹学的有关知识点也有了进一步的学习和掌握。
对于这种比较难偏理的学科来说确实是的,而且往往老师也很难把这么复杂的又与实际生活联系的我们又没亲身经历过的问题分析的比较透彻,所以很多同学从一开始听不懂就放弃了。但对于上课认真听讲,课后认真复习并且做相应习题的同学来说,学好它也不是一件难事,应该比较有把握的,毕竟题目是百变不离其中的,这也是这门课的好处。
在为数不多的实验过程中,不仅对运筹学的有关知识有了进一步的掌握,同时对在自己的计算机操作水准也有了很大的提高。课程的学习很快过去,但它对我们掌握运筹学建模问题的要求却并没有随课程的结束而结束。因此在以后的学习当中我们更应该时刻温习,不时巩固,以达到知新的效果。以上就是我的一些感悟,希望可以对自己有所帮助。
同时,在此感谢吴老师的耐心教导。
实验二使用LINGO求解运输问题
班级:工业10-1 班姓名:林金铎学号: 10024090146 评阅成绩:设有三个产地的产品需要运往四个销地。各产地的产量、各销地的销量及
其各产地到销地的单位运输费用如表所示,问如何调运使得总费用最少?
三个产地四个销地的运输问题
B1B2B3B4产量销地
产地
A1 4 12 4 11 16
A2 2 10 3 9 10
A38 5 11 6 22
销量8 14 12 14 48
一、按照运输问题的数学模型按集的方法编写LINGO程序。
(1)在LINGO软件模型中编写本题的程序如下图2-1所示。
图2-1 LINGO窗口截图
(2)点击LINGO菜单下的Solve选项,LINGO软件求解所输入的模型,得到LINGO运行状态窗口如图2-2所示。
图2-2 LINGO运行状态窗口截图
(3)运行结束后,关闭LINGO运行状态窗口,获得LINGO软件的结果报告窗口,如图2-3,2-4所示。
图2-3 LINGO结果报告窗口截图
图2-4 LINGO结果报告窗口截图
二、根据编写的程序,回答以下问题:
1、集循环函数可以对几个集进行循环操作?
答:1个集
2、哪个语句表示生产地产量约束?
答:@for(from(i):@sum(to(j):x(i,j))<=Capacity(i));
3、哪个语句表示销售地销量约束?
答:@for(to(j):@sum(from(i):x(i,j))>=Demand(j));
4、本模型中的@for循环函数循环操作多少次?
答:7次
5、本模型中的@sum循环函数循环操作多少次?
答:24次
实验三使用LINGO求解整数规划问题
班级:工业10-1 班姓名:林金铎学号: 10024090146 评阅成绩:现有9项工作和4个人,这4个人完成每项工作所需的时间和每个人可提
供的最多工作时间如表所示。问应该如何分配工作,所用时间最少。
4个人做9项工作的收益情况
工作人
A B C D
1 4 3 1
2 7
2 8 10 12 6
3 3 5 2 5
4 10 6 2 4
5 10 3 7 9
6 8 10 9 9
7 7 2 10 12
8 5 9 4 14
9 10 8 15 7
可供时间15 12 20 14
一、先建立该问题的数学模型然后用集的方法编写LINGO程序。
在LINGO软件模型中编写本题的程序如下图3-1所示。
图3-1 LINGO窗口截图
点击LINGO菜单下的Solve选项,LINGO软件求解所输入的模型,得到LINGO运行状态窗口如图3-2所示。
图3-2 LINGO运行状态窗口截图
运行结束后,关闭LINGO运行状态窗口,获得LINGO软件的结果报告窗口,如图3-3,3-4,3-5,3-6,3-7,3-8所示。
图3-3 LINGO结果报告窗口截图
图3-4 LINGO结果报告窗口截图
图3-5 LINGO结果报告窗口截图
图3-6 LINGO结果报告窗口截图
图3-7LINGO结果报告窗口截图
图3-8 LINGO结果报告窗口截图
二、在LINGO中如何限制变量为0、1变量,以本题为例进行说明。
答:通过语句编程来实现,例如本例中的
@for(flight(i):@sum(vcf(j):x(i,j))=1);
@for(vcf(j):@sum(flight(i):x(i,j))=1);
三、所编写的程序能否通过编译?求解结果是否满足题目的实际约束条件?如果不能通过编译或求解结果不满足题目约束条件,请记录并分析原因。
答:可以通过编译,但是所求解的结果不满足题意。原因估计是四个人所有的时间都用上都不能把所有的工作都做完,即工作量太大,而人数太少无论如何都不可能完成所有的工作。
四、根据运行结果,回答以下问题:A、B、C、D各做哪几项工作?一共花费多少时间?
答:根据运行结果无法得出结论,因为该题无解。
五、根据本题目所编写的程序、编译情况和运行结果,对0-1整数规划和指派问题的LINGO求解进行总结。
答:
@for(flight(i):@sum(vcf(j):x(i,j))=1);@for(vcf(j):@sum(flight(
i):x(i,j))=1);此类语句的编程我看不懂。
实验四 使用LINGO 求解动态规划问题
班级:工业10-1 班 姓名:林金铎 学号: 10024090146 评阅成绩: 如下最短路模型:
一、按集的方法编写上述模型的LINGO 模型。
在LINGO 软件模型中编写本题的程序如下图4-1所示。
图4-1 LINGO 窗口截图
A
B 1
B 2
C 1
C2
C 4 C 3
D 1
D
D 3
E 1 E 2
F
3
2
2
3
5
3
7 2
5
6
4
5
3 4
8
2 3
5
6 2 5
3 3
5 E 1
3 3
2
点击LINGO菜单下的Solve选项,LINGO软件求解所输入的模型,得到LINGO运行状态窗口如图4-2所示。
图4-2 LINGO运行状态窗口截图
运行结束后,关闭LINGO运行状态窗口,获得LINGO软件的结果报告窗口,如图4-3,4-5所示。
图4-3 LINGO结果报告窗口截图
图4-4LINGO结果报告窗口截图
二、根据所编写的程序,回答下列问题:
1、在本程序中,派生集有多少个成员?指出其中的一个成员及其属性值。答:两个成员,其中一个是roads(i,j),其属性值有,1,2 1,3 2,4 2,5 2,6 3,5 3,6 3,7 4,8 4,9 5,8 5,9 6,9 6,10 7,9 7,10 8,11 8,13 9,11 9,12 9,13 10,11 10,12 10,13 11,14 12,14 13,14
2、在LINGO程序的数据部分,属性值数量与集成员的数量应该存在什么关系?属性值顺序与集成员的顺序应该存在什么关系?
答:属性值数量与集成员的数量相等,属性值顺序与集成员的顺序是一一对应的顺序。
3、本程序的编写是基于动态规划解法中的逆序法还是顺序法?
答:顺序法
4、在本题的动态规划基本方程中,边界条件是如何表示的(用程序中的语句说明)?
答:边界条件是利用语句f(@size(cities))=0来实现的。
5、集循环函数的语法为
@function(setname[(set_index_list)[|conditional_qualifier]]: expression_list),找出本题所编写程序的一个集循环函数,指出其@function、、setname、set_index_list、conditional_qualifier和expression_list各是什么?
答:语句@for(cities(i)|i#lt#@size(cities):@function是@for,setname 是cities(i),set-index-list在语句中未出现,conditional-qualifier是
i#lt#,expression-list是@size(cities)
三、根据软件求解结果,回答以下问题:
1、根据求解结果,指出各点到点F的最短距离是多少。
答:A点: 11; B1点 13; C1点 11; D1点 6; E1点 3; F点 0; B2点 9; C2点 10; D2点 5; E2点 5;
C3点 8; D3点 5; E3点 2,
C4点 7;
2、根据求解结果,指出模型中的剩余变量、松弛变量有什么特征。
答:松弛变量全部为0,剩余变量没有什么特征。
实验五 使用LINGO 求解网络规划问题
班级:工业10-1 班 姓名:林金铎 学号: 10024090146 评阅成绩: 如下流量网络:
一、 按集的方法编写其LINGO 程序并在LINGO 软件上运行求解。
在LINGO 软件模型中编写本题的程序如下图5-1所示。
图5-1 LINGO 窗口截图
V 1
V 2
V 3
V 5
V 6
3
5
5
2
2
1
1
3
V 4
4
点击LINGO菜单下的Solve选项,LINGO软件求解所输入的模型,得到LINGO运行状态窗口如图5-2所示。
图5-2 LINGO运行状态窗口截图
运行结束后,关闭LINGO运行状态窗口,获得LINGO软件的结果报告窗口,如图1-3所示。
图5-3 LINGO结果报告窗口截图
图5-4 LINGO 结果报告窗口截图
二、根据编写的程序,回答下列问题:
本模型属于单源点和单汇集点的网络最大流问题,其数学规划可以表示为
max f
v
(,)(,),..,0,,f f ij ij i V j V
i j E i j E
i s v s t i t f f v i s t ∈∈∈∈=??
-==∑∑-??≠? 0,(,)ij ij i j E f c ≤≤∈
式中,V 是顶点集,E 边集或弧集,s 是源点,t 是汇点。 指出哪些语句分别表示上述目标函数和两大约束。 答:@for(a(i,j):f(i,j)<=c(i,j));
@for(n(i):@sum(a(i,j):f(i,j))=@sum(a(j,i):f(j,i)));表示上述目标函数。