陈基政运筹学课程设计报告2.docx
- 文档编号:3900452
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:24
- 大小:123.51KB
陈基政运筹学课程设计报告2.docx
《陈基政运筹学课程设计报告2.docx》由会员分享,可在线阅读,更多相关《陈基政运筹学课程设计报告2.docx(24页珍藏版)》请在冰点文库上搜索。
陈基政运筹学课程设计报告2
成绩评定表
学生姓名
陈基政
班级学号
1009010217
专业
信息与计算科学
课程设计题目
某城市自来水供水运输最优问题及分配问题
评
语
组长签字:
成绩
日期
20年月日
课程设计任务书
学院
理学院
专业
信息与计算科学
学生姓名
陈基政
班级学号
1009010217
课程设计题目
某城市自来水供水运输最优问题及分配问题
实践教学要求与任务:
设计要求(技术参数):
1、熟练掌握Lindo软件,了解Lingo软件。
2、根据所选题目及调研所得数据,运用运筹学知识,抽象出线性规划的数学模型。
3、运用Lindo软件,对模型进行求解,对结果进行分析并得出结论。
4、掌握利用运筹学理论知识解决实际问题的一般步骤。
5、利用Lingo软件求解运输问题或分配问题。
设计任务:
1、运用运筹学有关知识及Lindo软件,对三个水库在四个区供水量进行分配,根据公司对于各区的引水管理费及各区最高(低)需求,对公司供水量最优运输进行分析,并建立线性规划模型求解,得出最优运输方案和总最低的饮水管理费。
2、利用Lingo软件编程求解分配问题。
工作计划与进度安排:
第一天——第二天学习使用Lindo、Lingo软件并选题
第三天——第四天查阅资料
第五天——第六天建立数学模型
第七天——第九天上机求解并完成论文
第十天答辩
指导教师:
201年月日
专业负责人:
201年月日
学院教学副院长:
201年月日
摘要
运筹学是一门以人机系统的组织、管理为对象,应用数学和计算机等工具来研究各类有限资源的合理规划使用并提供优化决策方案的科学。
随着科学技术和生产的发展,运筹学已渗入很多领域里,发挥了越来越重要的作用。
此题研究的主要内容是根据保证居民生活用水和某些重要机关、企业、事业单位用水的基本需求进行合理规划。
目的是依据各区的引水管理费,最高(低)需求规划各区自来水的使用情况,考虑各水库如何分配供水量达到最低需求,如何分配才能使公司获利最多,当各水库运输各区供水量一定时,又如何使各区的引水管理费最低,公司获利最多,这完全符合运筹学线性规划的理论。
按照线性规划求解模式计算出既科学又合理的最优搭配方案:
在使居民生活用水和某些重要机关、企业、事业单位用水的基本需求的情况下,用(单价-其他管理费)*总供水量-最低总的饮水管理费,计算出最大获利。
根据各种限定性因素得出目标函数和各个约束条件,运用运筹学计算软件(主要是指Lindo软件)求解所建立的运筹学模型。
所以对基本情况的分析,经过抽象和延伸,建立起了水库供水运输的线性规划模型。
结合模型的特点,对模型的求解进行了讨论和数据分析,将模型应用于案例的背景问题,得出相应的最优解决方案,就可以对问题一一进行解答。
同时还可以用Lingo软件进行分配问题进行求解最优分配方案。
关键词:
线性规划;Lindo软件;最优运输;数据分析
目录
1某城市自来水供水运输最优问题1
1.1问题的提出1
1.2问题分析2
1.3模型建立及求解2
1.3.1设定变量2
1.3.2建立模型3
1.3.3Lindo数据输入与输出4
1.4结果分析8
2分配问题案例9
2.1问题的提出10
2.2问题的分析及求解10
2.2.1问题分析10
2.2.2问题求解10
2.3结果分析15
总结16
参考文献17
1某城市自来水供水运输最优问题
某城市自来水的水源地为A、B、C三个水库,分别由地下管道把水送往该市所辖甲、乙、丙、丁四个区。
唯一的例外是C水库与丁区没有地下管道。
由于地理位置的差别,各水库通往各区的输水管道经过的涵洞、桥梁、加压站和净水站等设备各不相同,因此该公司对各区的引水管理费(元/千吨)各不相同(见下表)。
但是对各区自来水的其他管理费均为45元/千吨,而且对各区用户都按统一标准计费,单价为90元/千吨。
目前水库将临枯水期,该公司决策机构正考虑如何分配现有供水量的问题。
首先,必须保证居民生活用水和某些重要机关、企业、事业单位用水的基本需求,各区的这部分用水量由下表的“最低需求”行表示,但是拥有一个独立水源的丙区这部分水量可自给自足,无须公司供给。
其次,除乙区外,其他三个区都已向公司申请额外再分给如下水量(千吨/天):
甲区:
20;丙区:
30;丁区要求越多越好,无上限。
这部分水量包含于“最高需求”行中。
引水管理费
(千/吨)
甲
乙
丙
丁
供水量(元/千吨)
A
16
13
22
17
50
B
14
13
19
15
60
C
19
20
23
—
50
最低需求(千吨/天)
30
70
0
10
最高需求(千吨/天)
50
70
30
不限
1.1问题的提出
该公司应如何分配供水量,才能在保障各区最低需求的基础上获利最多?
并按要求分别完成下列分析:
(1)水库B供应甲区的引水管理费(元/千吨)在何范围内变化时最优运输方案不变?
(2)水库A的供水量在何范围内变化时最优基不变?
(3)乙区的日供水量为80千吨时的最优运输方案。
1.2问题分析
通过对题目的正确理解和分析,依据题意可以得到在保证各区最低供水量的基础上运费最低,也就是获利最大的模型,以这个模型为基础用Lindo6.1进行求解,可以得到公司分配供水量的最优决策方案即A、B、C三个水库分别给甲、乙、丙、丁四个区的供水量和公司最小总的引水管理费用,则最大获利为:
(用户单价-其他管理费)*总供水量-公司最小总的引水管理费用。
然后通过灵敏度分析解决以下三个问题。
(1)水库B供应甲区的引水管理费(元/千吨)在何范围内变化时最优运输方案不变,即当目标函数的系数C在[初始目标函数的系数-允许变量系数减少的范围,初始目函数的系数+允许变量系数增加的范围]内变化时,最优基不变,最优解也不变,由于目标函数的系数发生改变了,所以最优值有可能改变。
(2)水库A的供水量在何范围内变化时最优基不变,当约束条件右端项的值在[初始约束条件右端项的值-允许b值减少的范围,初始约束条件右端项的值+允许b值增加的范围]内变化时最优基不变,最优解不变。
(3)乙区的日供水量为80千吨时的最优运输方案。
乙区的日供水量是第5个约束条件的右端项,将b5改为等于80然后用Lindo6.1进行求最优方案。
1.3模型建立及求解
1.3.1设定变量
设
表示从第i个水库输水到第j个区的供水量,其中i=1、2、3(1、2、3分别代表A、B、C三个水库);j=1、2、3、4(1、2、3、4分别表示甲、乙、丙、丁四个区)
设Z为总的引水管理费;设Y表示公司的获利。
根据题意推理:
A水库到甲区的引水管理费为:
A水库到乙区的引水管理费为:
A水库到丙区的引水管理费为:
A水库到丁区的引水管理费为:
B水库到甲区的引水管理费为:
B水库到乙区的引水管理费为:
B水库到丙区的引水管理费为:
B水库到丁区的引水管理费为:
C水库到甲区的引水管理费为:
C水库到乙区的引水管理费为:
C水库到丙区的引水管理费为:
A水库的供水量为:
B水库的供水量为:
C水库的供水量为:
甲区的最低需求为:
乙区的最低需求为:
丙区的最低需求为:
无
丁区的最低需求为:
甲区的最高需求为:
乙区的最高需求为:
丙区的最高需求为:
丁区的最高需求为:
无
1.3.2建立模型
则得该问题的LP问题为:
将原问题第一、二、三、四、六、七、八个约束条件添加松弛变量
、
、
、
、
、
、
;
将原问题第四、五、六个约束条件添加人工变量
、
、
;
将LP问题化为标准形式:
1.3.3Lindo数据输入与输出
在模型编译框内输入语句如下:
Min16X11+13X12+22X13+17X14+14X21+13X22+19X23+15X24+19X31+20X32+23X33
ST
X11+X12+X13+X14<50
X21+X22+X23+X24<60
X31+X32+X33<50
X11+X21+X31>30
X12+X22+X32>70
X14+X24>10
X11+X21+X31<50
X13+X23+X33<30
END
选择"是(Y)"表示同意做敏感性分析运行结果如下图所示:
LPOPTIMUMFOUNDATSTEP4
OBJECTIVEFUNCTIONVALUE
1)1480.000
VARIABLEVALUEREDUCEDCOST
X110.0000002.000000
X1250.0000000.000000
X130.00000022.000000
X140.0000002.000000
X2130.0000000.000000
X2220.0000000.000000
X230.00000019.000000
X2410.0000000.000000
X310.0000005.000000
X320.0000007.000000
X330.00000023.000000
ROWSLACKORSURPLUSDUALPRICES
2)0.0000000.000000
3)0.0000000.000000
4)50.0000000.000000
5)0.000000-14.000000
6)0.000000-13.000000
7)0.000000-15.000000
8)20.0000000.000000
9)30.0000000.000000
NO.ITERATIONS=4
RANGESINWHICHTHEBASISISUNCHANGED:
OBJCOEFFICIENTRANGES
VARIABLECURRENTALLOWABLEALLOWABLE
COEFINCREASEDECREASE
X1116.000000INFINITY2.000000
X1213.0000000.000000INFINITY
X1322.000000INFINITY22.000000
X1417.000000INFINITY2.000000
X2114.0000002.00000014.000000
X2213.0000007.0000000.000000
X2319.000000INFINITY19.000000
X2415.0000002.00000015.000000
X3119.000000INFINITY5.000000
X3220.000000INFINITY7.000000
X3323.000000INFINITY23.000000
RIGHTHANDSIDERANGES
ROWCURRENTALLOWABLEALLOWABLE
RHSINCREASEDECREASE
250.00000020.0000000.000000
360.000000INFINITY0.000000
450.000000INFINITY50.000000
530.0000000.00000030.000000
670.0000000.00000020.000000
710.0000000.00000010.000000
850.000000INFINITY20.000000
930.000000INFINITY30.000000
b5改为“
”然后用Lindo6.1运行结果如下图所示:
LPOPTIMUMFOUNDATSTEP5
OBJECTIVEFUNCTIONVALUE
1)1660.000
VARIABLEVALUEREDUCEDCOST
X110.0000002.000000
X1250.0000000.000000
X130.00000027.000000
X140.0000002.000000
X2120.0000000.000000
X2230.0000000.000000
X230.00000024.000000
X2410.0000000.000000
X3110.0000000.000000
X320.0000002.000000
X330.00000023.000000
ROWSLACKORSURPLUSDUALPRICES
2)0.0000005.000000
3)0.0000005.000000
4)40.0000000.000000
5)0.000000-19.000000
6)0.000000-18.000000
7)0.000000-20.000000
8)20.0000000.000000
9)30.0000000.000000
1.4结果分析
由输出结果可知:
“LPOPTIMUMFOUNDATSTEP4”表示LINDO在(用单纯形法)四次迭代或旋转后得到最优解。
“OBJECTIVEFUNCTIONVALUE1480.000”表示最优目标值为1480。
“VALUE”给出最优解中各变量的值即最优分配供水量方案为:
,
,
,
,其余变量的值为0;即A水库输水到乙区50千吨,B水库输入到甲区30千吨,到乙区20千吨,到丁区10千吨。
此时
,即最低总的引水管理费为1480元,则最大获利为:
。
“REDUCEDCOST”给出最优单纯形表中第0行中变量的系数(Max型问题).其中基变量的“REDUCEDCOST”值应为0,对于非基变量,相应的“REDUCEDCOST”值表示当该非基变量增加一个单位时目标函数增加的量。
如本例题中第一行表示“A水库输水到甲区每增加1千吨则公司的引水管理费增加2元”。
“SLACKORSURPLUS”给出松驰变量的值:
第2、3、5、6、7行松驰变量均为0,说明对于最优解来讲,五个约束(第2、3、5、6、7行)均取等号。
“DUALPRICES”给出对偶价格的值:
第2、3、5、6、7行对偶价格分别为0,0,-14.000000,-13.000000,-15.000000。
“DUALPRICES”值表示当该松驰变量增加一个单位时目标函数增加的量。
如本例题中第5行松驰变量增加一个单位时即B水库运输到甲区每增加1千吨则公司的引水管理费减少14元。
灵敏度分析:
CURRENTCOEF:
初始目标函数系数;ALLOWABLEINCREASE:
允许变量系数增加的范围;ALLOWABLEDECREASE:
允许变量系数减少的范围;CURRENTRHS:
初始约束条件右端项的值;ALLOWABLEINCREASE:
允许b值增加的范围;ALLOWABLEDECREASE:
允许b值减少的范围。
当目标函数的系数在[初始目标函数的系数-允许变量系数减少的范围,初始目函数的系数+允许变量系数增加的范围]内变化时,最优基不变,最优解也不变。
当约束条件右端项的值在[初始约束条件右端项的值-允许b值减少的范围,初始约束条件右端项的值+允许b值增加的范围]内变化时最优基不变,最优解不变。
由输出结果可知:
(1)水库B供应甲区的引水管理费为
,由上列计算结果可得初始目标函数系数为14,允许变量系数增加的范围为:
,允许变量系数减少的范围:
,所以水库B供应甲区的引水管理费在
范围内变化时最优基不变,最优解也不变即最优方案不变。
(2)水库A的供水量年是第1个约束条件的右端项,即该问题求的是b1的变化范围,由上列计算结果可得初始约束条件右端项的值为50,允许b值增加的范围为:
,允许b值减少的范围为:
0,所以水库A的供水量在
范围内变化时最优基不变。
由输出结果可知:
“OBJECTIVEFUNCTIONVALUE1660.000”表示最优目标值为1660即公司最小总的引水管理费用minZ=1660.000。
“VALUE”给出最优解中各变量的值即最优分配供水量方案为:
,
,
,
,
,其余变量的值为0即A水库输水到乙区50千吨,B水库输入到甲区30千吨,到乙区20千吨,到丁区10千吨,C水库输水到甲区10千吨。
2分配问题案例
某大学图书馆聘用四名大学生A,B,C,D值班。
大学生值班报酬为10元/小时。
该图书馆开放时间为上午9:
00至晚上8:
00,开放时间内须有且仅须一名学生值班,每名学生每周值班不超过5次,每次值班不少于2小时,每天安排值班的学生不超过3人。
已知每人每天最多可安排的值班时间见下表。
每天最多可安排的值班时间(h)
学生代号
学生代号
值班时间
周一
周二
周三
周四
周五
周六
周日
A
5
8
6
0
7
4
8
B
5
6
0
6
0
8
5
C
4
4
3
8
5
8
0
D
5
3
6
2
4
2
8
2.1问题的提出
该图书馆如何安排人员值班表,使得支付的报酬最少?
2.2问题的分析及求解
2.2.1问题分析
通过对题目的正确理解和分析,依据题意可以得到在保证图书馆的规定要求和学生值班时间最少,也就是图书馆支付报酬最少的模型,以这个模型为基础用Lingo进行求解,可以得到学生值班最优分配方案和图书馆支付最少报酬。
2.2.2问题求解
用LINGO解决分配问题,在LINGO中输入程序如下:
model:
sets:
xuesheng/1..4/:
;
week/1..7/:
;
worktime(xuesheng,week):
wtime,x,y;
endsets
data:
wtime=5860748
5606085
4438580
5362428;
enddata
min=10*@sum(worktime(i,j):
x(i,j));
@for(worktime:
x>=y*2);
@for(xuesheng(i):
@sum(week(j):
y(i,j))<=5);
@for(week(j):
@sum(xuesheng(i):
y(i,j))<=3);
@for(week(j):
@sum(xuesheng(i):
x(i,j))>=11);
@for(worktime:
x<=wtime);
@for(worktime:
@gin(x));
end
运行后得到输出结果如下:
Globaloptimalsolutionfound.
Objectivevalue:
770.0000
Objectivebound:
770.0000
Infeasibilities:
0.000000
Extendedsolversteps:
0
Totalsolveriterations:
0
VariableValueReducedCost
WTIME(1,1)5.0000000.000000
WTIME(1,2)8.0000000.000000
WTIME(1,3)6.0000000.000000
WTIME(1,4)0.0000000.000000
WTIME(1,5)7.0000000.000000
WTIME(1,6)4.0000000.000000
WTIME(1,7)8.0000000.000000
WTIME(2,1)5.0000000.000000
WTIME(2,2)6.0000000.000000
WTIME(2,3)0.0000000.000000
WTIME(2,4)6.0000000.000000
WTIME(2,5)0.0000000.000000
WTIME(2,6)8.0000000.000000
WTIME(2,7)5.0000000.000000
WTIME(3,1)4.0000000.000000
WTIME(3,2)4.0000000.000000
WTIME(3,3)3.0000000.000000
WTIME(3,4)8.0000000.000000
WTIME(3,5)5.0000000.000000
WTIME(3,6)8.0000000.000000
WTIME(3,7)0.0000000.000000
WTIME(4,1)5.0000000.000000
WTIME(4,2)3.0000000.000000
WTIME(4,3)6.0000000.000000
WTIME(4,4)2.0000000.000000
WTIME(4,5)4.0000000.000000
WTIME(4,6)2.0000000.000000
WTIME(4,7)8.0000000.000000
X(1,1)5.00000010.00000
X(1,2)8.00000010.00000
X(1,3)6.00000010.00000
X(1,4)0.00000010.00000
X(1,5)7.00000010.00000
X(1,6)4.00000010.00000
X(1,7)8.00000010.00000
X(2,1)5.00000010.00000
X(2,2)3.00000010.00000
X(2,3)0.00000010.00000
X(2,4)6.00000010.00000
X(2,5)0.00000010.00000
X(2,6)7.00000010.00000
X(2,7)3.00000010.00000
X(3,1)0.00000010.00000
X(3,2)0.00000010.00000
X(3,3)3.00000010.00000
X(3,4)5.00000010.00000
X(3,5)4.00000010.00000
X(3,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 陈基政 运筹学 课程设计 报告