版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
./理工学院数学建模大型作业2011—2012学年第1学期目录一.摘要二.旅行问题问题描述符号说明模型设计建模求解模型分析三.建模过程及心得体会四.参考文件一.摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题,问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。关键词:HAMILTON回路LINGO最优旅行路线0-1模型二.旅行问题问题描述某人要在假期从城市A出发,乘火车或飞机到城市B,C,D,E,F旅游购物。他计划走遍这些城市各一次且仅一次,最后返回城市A。已知城市间的路费数据见附表1,请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市,该怎样修订旅行路线?在城市间旅游时他计划购买照相机,衣服,书籍,摄像机,渔具,白酒,食品,而受航空行重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2.请你为他决策买哪些物品,使所买物品价值最大。附表1:ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相机衣服书籍摄像机渔具白酒食品香烟重量〔kg12434221价格<元>1300275032043501400300120600模型设计首先给出一个定义:设v1,v2,,vn是图G中的n个顶点,若有一条从某一顶点v1出发,经过各节点一次且仅一次,最后返回出发点v1的回路,则称此回路为HAMILTON回路。问题1.分析:这个优化问题的目标是使旅行的总费用最少,要做的决策是如何设定旅行路线,决策受的约束条件:每个城市都必须去,但仅能去一次。按题目所给,将决定变量,目标函数和约束条件用数学符号及式子表示出来,就可得一下模型。模型建立:对于6个城市的旅行问题设A,B,C,D,E,F六个城市分别对应v1,v2,v3,v4,v5,v6。假设表示从城市i到城市j的费用。定义0-1整数型变量=1表示从城市i旅行到城市j,否则=0。则旅行问题的数学模型可表示为一个整数规划问题。minz=<ij>s.t.=1〔ij;j=1,2,……,6=1<ij;i=1,2,……,6><ij;i=2,3,……,6;j=2,3,……6>其中辅助变量〔i=2,3,……,6可以是连续变化的,虽然这些变量在最优解中取普通的整数值〔从而在约束条件中,可以限定这些变量为整数。事实上,在最优解中,=访问城市的顺序数。模型求解运用LINGO,输入程序:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..6/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=0120250330210150120098350225300250980520430280330350520027018521022543027004201503002801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用为1163路线:A-B-C-F-D-E-A问题2.临时因故只能去4个城市,那么应该怎样安排旅行路线。分析:在B,C,D,E,F五个城市中选4个城市,显然有5种可能,按照问题一中的模型,将费用矩阵稍作修改,运用LINGO分别解除5种可能的费用,进行比较,即得结果。〔1选取B,D,E,F,计算旅行费用:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=01203302101501200350225300330350027018521022527004201503001854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用:950路线:A-B-E-D-F-A<2>选取B,C,E,F,计算旅行费用:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025021015012009822530025098043028021022543004201503002804200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用:963路线:A-E-B-C-F-A<3>选取B,C,D,F,计算旅行费用:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033015012009835030025098052028033035052001851503002801850;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用:1013路线:A-B-C-F-D-A<4>选取路线:B,C,D,E,计算旅行费用:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033021012009835022525098052043033035052002702102254302700;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用:1173路线:A-C-B-E-D-A<5>选取C,D,E,F,计算旅行费用:MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=02503302101502500520430280330520027018521043027004201502801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果:总费用:1195路线:A-C-F-D-E-A因此,总结以上〔1,〔2,〔3,〔4,〔5五种情况可得:应该选用路线:A-B-E-D-F-A。总费用花费最少,为950.问题3.在城市间旅游时他计划购买照相机、衣服、书籍、摄像机、渔具、白酒、食品、香烟等物品,而受航空行重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2。请你为他决策买哪些物品,使所买物品总价值最大?分析:解读题意,实际上此题涉及背包问题,题目转化为一个限重15公斤的背包,要求在8件可带可不带的物品中做出合理的方法。模型建立:将照相机,衣服,书籍,摄像机,渔具,酒,食品和香烟编号为1,2,3,4,5,6,7,8。设总容量为b,为每个物品的重量,为每个物品各自的价格。定义一个变量,当=1是,表示装第i件物品,当=0时,则不装〔i=1,2,……,8.则约束条件为:maxz==0或1,〔i=1,2,……,8模型求解:利用LINGO软件求解,在LINGO中输入以下程序:model:sets:M/1..8/:W;price/1..8/:p;number/1..8/:x;endsetsda
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024订购酒的购销合同范本范文
- 专题6 课内阅读 (一)(知识盘点+试题)-2022-2023学年五年级语文下册期末复习
- 城区生活垃圾焚烧发电工程PPP项目招投标书范本
- 2024路沿石购销合同
- 2024商铺租赁标准合同范本
- 2024电子产品购销合同格式模板
- 2024物业保洁劳务合同
- 2024股权转让委托合同标准范本
- 规划课题申报范例:《习近平新时代中国特色社会主义思想学生读本》教学研究(附可修改技术路线图)
- 茶水赠送合同(2篇)
- 电梯使用现场类隐患专项排查清单
- 一例下肢静脉溃疡患者的个案护理论文
- 危岩稳定性计算表格-滑移式-倾倒式-坠落式-完整版
- 直播运营团队组织架构及岗位职责解析
- 肝胆外科运用PDCA循环缩短三四类手术患者术后留置导尿的时间
- JCT640-2010 顶进施工法用钢筋混凝土排水管
- 注塑车间平面规划图OK
- 商户洽谈记录表
- 镇卫生院绩效考核方案
- 9.2+积极投身创新实践(高效教案)-【中职专用】中职思想政治《哲学与人生》(高教版2023基础模块)
- 【高中语文】《逻辑的力量》课件+统编版++选择性必修上册
评论
0/150
提交评论