数学模型论文

数学模型论文 数学建模 大型作业 作业名称: 旅 行 问 题 班 级 : 姓 名 : 学 号 : 指导教师: 时 间 : 2011—2012 学年 第1学期 旅行问题 摘要 本问题讨论的是著名的旅行推销商问题和背包问题.旅行推销商问题的一般提法为:求 一个访问n个城市的旅行路线，用1，2，…，n表示，城i, j之间的距离为d，从城1出ij发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短,即最短路～最短路问题是图论理论的一个经典问题，寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量, 如时间、费用、线路容量等。最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。遗憾的是:人们至今未找到有效的解决，只是有一些近似的解决方案。背包问题的一般提法为:某人带背包上山，携带的物品重量的限度为W公斤在人们不断思考和探索的现实问题过程中，找到了几种比较简单的可行方案 一、问题: 某人要在假期内从城市A出发，乘火车或飞机到城市B、C、D、E、F旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行线路使得他的总路费最少,如果临行他因故只能去4个城市，该怎样修订旅行路线, 在城市间旅游时他计划购买照相机、衣服、书籍、摄像机、渔具、白酒、食品、香烟等物品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2。请你为他决策买哪些物品，使所买物品总价值最大, 附表1: A B C D E F A 0 120 250 330 210 150 B 120 0 98 350 225 300 C 250 98 0 520 430 280 D 330 350 520 0 270 185 E 210 225 430 270 0 420 F 150 300 280 185 420 0 附表2 照相机 衣服 书籍 摄像机 渔具 白酒 食品 香烟 重量1 2 4 3 4 2 2 1 (kg) 价格1300 2750 320 4350 1400 300 120 600 (元) 二、符号说明 d表示从i城市到j城市的距离。 ij xxi=1表示旅客从从城市到城市，否则=0; jijij 表示背包不超过的最大重量，在这里=15; ,, ,表示该物品的重量; i 表示该物品的价格; ci 总价格所能达到的最高值定义为; f,，，k ,,,c/定义为商品的性价比; iii min定义为最小值; 定义为最大值; max 定义为求和。 , 三、模型设计 (1)由于旅客需要从A城市出发，到 B、C、D、E、F旅游购物，走遍这些城市各一次且仅 [1]一次，最后返回城市A，这就形成一个不重复的回路，在离散数学中叫做哈密顿回路. 将六个城市记为六个顶点，将来往两城市之间的路费记成两点之间的距离即权值，若求 旅游遍六个城市且不重复的最小路费的路线，相当于求带有权值的最小哈密顿回路。 定义: 经过图(有向图货无向图)中所有顶点一次且仅一次的回路叫做哈密顿回路。若各点 间有权值，所有回路中权值之和最小的一条 f(),)最优值函数是当总重量不超过公斤，背包中可以装入第一种到第k种物品的(2,k 最大使用价值。 即 k fcx()max(),, ,kkii,1,,,因而可以写出动态规划的顺序关系为: iii,x,1i且为整数(…6)fcx()max,,,,01 111ix,…，[,,0,1,/]xi1k fcxfxkn()()}2,,,,，,,, kkkkkk,1 四、建立模型及求解 , 模型建立 假定A、B、C、D、E、F的标号为1、2、3、4、5、6，假定以A、B、C、D、E、F城市之间 dx的往返费用为其距离=1表示某人从城表示从城市i到j的距离，定义0—1整型变量ijij,x市i旅行到城市j，否则=0,则该旅行问题的数子模型课表示为一个整体规划问题. ij 66 min z= (ij,) dx,,ijiji=1ij, 6 xiji,,,1(;1,26),ij,j1uuxijij,,,,,,65(;2,36;2,36) ijij xu,,010或， iji u其中，辅助变量() i,2,36)是可以连续变化的i 模型求解: 本模型的第一个约束是保证每个城市必须到达，第二个约束是保证旅游者必须离开每个 城市，后两个是保证没有子回路的出现。 根据本模型的思路编写C++程序(1)，运行后得到结果为: 其中1,2,3,4,5分别表示城市,,,,,,,,,,,。 因此可以得到旅游者要想路费最小，他的旅游路线应该为: 城市A?城市B?城市C?城市F?城市D?城市E?城市A 最小总路费为:1163元。 而求他只当只经过四个城市时的总路费，处理方法与上面的一致，只是去掉没去的城市 后，再重新按字母顺序编号。由于旅行者要经过的城市的个数不多，只有四个，可以用穷举 法求解。 求解结果为: 当他没有去城市B时: 即要想总路费最小为1195元，路线应为: 城市A?城市C?城市F?城市D?城市E?城市A 当他没有去城市C时: 即要想总路费最小为950元，路线应为: 城市A?城市B?城市D?城市E?城市F?城市A 当他没有去城市D时: 即要想总路费最小为963元，路线应为: 城市A?城市E?城市B?城市C?城市F?城市A 当他没有去城市E时: 即要想总路费最小为1013元，路线应为: 城市A?城市B?城市C?城市F?城市D?城市A 当他没有去城市F时: 即要想总路费最小为1173元，路线应为: 城市A?城市C?城市B?城市E?城市D?城市A 综上所述:当旅客只去四个城市时，路线为: 城市A?城市B?城市E?城市D?城市F?城市A 此时，总路费最小，为950元。 , 模型假设: 假定照相机，衣服，书籍，摄像机，渔具，白酒，食品，香烟编号为:1，2，3，4，5，6， ,cpc,p设定第i种物品每件重量为kg，设每件物品的价格为元，则令=/,则有=1300，iiiii1 ppppppp=1325，=80，=1450，=350，=150，=60，=600.则若想在规定的重量2345678 ppppp下的总价值最大，则诸如=80，=350，=150，=60，=600均可舍弃，而由已35678知可得由编号1的照相机，编号2的衣服，编号4的摄像机组成的新的被选择的物品能满足 要求，故从新编号为:照相机(1)，衣服(2)，摄像机(3),七每件重量分别为1，2，3kg， x设为第i种物品的件数，则其数学模型为: i xxxmax f=1300+2750+4350 123 xxx，，,2315st 123 x,0i=123切为整数，，， i xxx，，,2315 即 123 x,0 1 x,0 2 x,0 3 模型求解 f(15)用动态规划方法求解，即为求 3 而 由此类推得: fxxx(15)max130027504350,，，，， 3123 xxx，，,23151230且为整数，=1,2,3x, ii ,，，max130027504350xxx，， 123 xxx，,,2153123,, 0且为整数，=1,2,3x,ii max4350max13002750xxx,,，，,，， 323,,，，,,xxxxx1502315331233,,且为整数且为整数xxx,,,00,0,312,, ,，,max4350(153)xfx，，323x,0,1,2,3,4,53 ,，，，，max{0(15),4350(12),43502(9)fff， 222 43503(6)43504(3)43505(0)，，，，，，fff，，， 222由此类推得: fffff(15)max[(15),2750(13),5500(11),8250(9),,，，，21111 11000(7),13750(5),16500(3),19250(1)]，，，，ffff1111 fffff(12)max[(12),2750(10),5500(8),8250(6),,，，，21111 11000(4),13750(2),16500(0)]，，，fff 111 ffffff(9)max[(9),2750(7),5500(5),8250(3),11000(1)],，，，，211111 fffff(6)max[(6),2750(4),5500(2),8250(0)],，，， 21111 fff(3)max[(3),2750(1)],， 211 ff(0)(0), 21 而 fx()max1350=4=1300[],,,,，()(超过的最大整数)11x,,1且为整数 x,01 x,,相应的最优决策为:，于是得到: 1fxii(=1300(1,2,3,1415),…，) 1i f (15)max[(15),2750(12),+(1)],，，fff27507从而 2111 ,，，27507(1)f 1 ,，，275071300 ,,,20550(1,7)xx 12 f (15)max[(15),2750(12),+(1)],，，fff27507 2111 ,，，27506(0)f 1 ,，，275060 ,,,16500(0,6)xx 12 f (9)max[(9),2750(7),+(1)],，，fff27504 2111 ,，，27504(1)f 1 ,，，275041300 ,,,12300(1,4)xx 12 f (6)max[(6),2750(10),+(0)],，，fff27503 2111 ,，，27503(0)f 1 ,，，275030 ,,,8250(0,3)xx 12 f(3)max[(3),2750(1)],，ff 211 ,，2750(1)f 1 ,，27501300 ,,,4050(1,1)xx 12 ffxx(0)(0)0(0,0),,,, 2112 故最后得到 ffff(15)max[0(15),4350(12),054(0)],，，，，…435 3222 ,，，43505(0)f 2 ,,,,21750(0,0,5)xxx 123 xxx,,,0,0,5所以最佳装入方案为 123 如利用LINDO运行得到的结果为: LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 21750.0000 FIX ALL VARS.( 2) WITH RC > 0.000000E+00 NEW INTEGER SOLUTION OF 21750.0000 AT BRANCH 0 PIVOT 1 BOUND ON OPTIMUM: 21750.00 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 1 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 21750.00 VARIABLE VALUE REDUCED COST X1 0.000000 -1300.000000 X2 0.000000 -2750.000000 X3 5.000000 -4350.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1 BRANCHES= 0 DETERM.= 1.000E 0 LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 21750.0000 FIX ALL VARS.( 2) WITH RC > 0.000000E+00 NEW INTEGER SOLUTION OF 21750.0000 AT BRANCH 0 PIVOT 1 BOUND ON OPTIMUM: 21750.00 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 1 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 21750.00 VARIABLE VALUE REDUCED COST X1 0.000000 -1300.000000 X2 0.000000 -2750.000000 X3 5.000000 -4350.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 5.000000 0.000000 NO. ITERATIONS= 1 BRANCHES= 0 DETERM.= 1.000E 0 最大的使用价值为21750元。 若考虑八种物品，求其最大总价值，则用LINDO所求的结果为: LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 21750.0000 FIX ALL VARS.( 3) WITH RC > 0.000000E+00 NEW INTEGER SOLUTION OF 21750.0000 AT BRANCH 0 PIVOT 1 BOUND ON OPTIMUM: 21750.00 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 1 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 21750.00 VARIABLE VALUE REDUCED COST X1 0.000000 150.000000 X2 0.000000 150.000000 X3 0.000000 5480.000000 X4 5.000000 0.000000 X5 0.000000 4400.000000 X6 0.000000 2600.000000 X7 0.000000 2780.000000 X8 0.000000 850.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1450.000000 3) 0.000000 0.000000 4) 0.000000 0.000000 5) 0.000000 0.000000 6) 5.000000 0.000000 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 10) 0.000000 0.000000 NO. ITERATIONS= 1 BRANCHES= 0 DETERM.= 1.000E 0 由结果可知其最大的使用价值仍为21750元。 五、讨论(模型分析): (1)旅行问题的模型为:n(n+1)个 变量，n个 变量，(n+1)个第一类约束，(n+1)个第二类约束，n(n—1)个第三类约束。可以知道，为避免子回路而附加的第三类约束条件大大增加实际问题的约束条件的个数，而且当n较大时，该约束的数量是相当大的。 f(),(2)最优值函数是当总重量不超过公斤，背包中可以装入第一种到第k种物品的,k 最大使用价值。 即 k fcx()max(),, ,kkii,1,,,因而可以写出动态规划的顺序关系为: iii,x,1i且为整数(…6),,01ixi fcx()max,, 111x,…，[,,0,1,/]1k fcxfxkn()()}2,,,,，,,, kkkkkk,1 然后，逐步计算出f(),，f(),，…，f(),及其相应的决策函数x(),，x(),…，12n12x(),，最后得出的fa()就是所求的最大值，其相应的最优策略由反推运算即可推出。 nn 在实际问题中，当a不大时，为了计算的简便，可将单位重量的,牌成递减序列，然i x后逐个分析能取值的可能性，并适当加以比较调整，再删掉某些可能性，这样能节省计i cx()都是线性函数cx的情形，可算量。当n很大时，就会产生存储量过大的困难。如果iiii按单位重量的价值,,,c/()由小到大进行排列。设,,,,,,…，则i,2,3…niii12n ,,,对于给定的可供装入重量，如果，背包内当然没办法容纳第n件物品，即最优解,n*x,,,k,中=0，如果(k为正整数)，背包内必然仅含有第n种物品，即最优解为:=k，nnn*xin,,,,,=0，();如果，且不是的整数倍，这时背包容了n种物品，甚至可能不inn,*nx是最优解。但可以找到一个初略的估算公式:当成立时，最优解中一定,,,nn,,,nn,1大于或等于1，即一定要装入第n种物品。 六、参考文献 1、姜启源 谢金星 叶俊 数学模型(第三版) 高等教育出版社 2003.8 2、甘应爱 田丰 李维铮等 运筹学(第三版) 清华大学出版社 2005.6 3、屈婉玲 耿素云 张立昂 离散数学(第一版) 高等教育出版社 2008.3 4、徐玖平 胡知能 运筹学(第二版) 科学出版社 2009.6 5、谭浩强 C程序设计(第三版) 清华大学出版社 2005.7 6、谭浩强 C++面向对象程序设计(第四版) 清华大学出版社 2006.1 七、附录:程序。 (1)//将城市间的路费数据建立一个数组，城市A,B,C,D,E,F分别用1,2,3,4,5,6表 示～ #include #include #include #define MAX 6 using namespace std; int dis[MAX][MAX] = { 0, 120, 250, 330, 210, 150, 120, 0 ,98, 350, 225, 300, 250, 98, 0, 520, 430, 280, 330, 350, 520, 0, 270, 185, 210, 225, 430, 270, 0, 420, 150, 300, 280,185, 420, 0 }; typedef struct { int curcity; //当前所在的城市 vector unvisited; //当前未访问的城市 set type; //由于set自动排序，相同状态的vector可能不同，但set必然相同 int distance; //从当前城市到终点回到起点的距离 } status; void printVec( vector vec ) // 测试用 { vector::iterator iter; vector::iterator it; for( iter = vec.begin( ); iter!=vec.end(); iter++ ) { cout << (*iter).curcity << " <"; for( it = (*iter).unvisited.begin( ); it != (*iter).unvisited.end( ); it++ ) { cout << *it <<" "; } cout << ">" << " distance:" << (*iter).distance << endl; } } bool contain( int i, status &sta ) // 看看当前状态的城市中是否包括城市i { vector::iterator iter; if( i == sta.curcity ) return true; else { for( iter = sta.unvisited.begin( ); iter != sta.unvisited.end( ); iter++ ) if( i == *iter ) return true; } return false; } vector combine(vector vec) // 合并相同状态 { vector new_vec; vector::iterator iter; status temp; while( vec.size( ) > 0 ) { iter = vec.begin(); temp = *iter; vec.erase( iter ); for( ; iter!=vec.end( ); iter++ ) { if( (temp.curcity == (*iter).curcity) && (temp.type == (*iter).type) ) { if( (*iter).distance < temp.distance ) temp=*iter; iter = vec.erase(iter); iter--; } } new_vec.push_back( temp ); } return new_vec; } int main() { vector pre_vector; vector cur_vector; //从后往前推，初始化 for( int i = 1; i < MAX; i++) { status sta; sta.curcity = i; sta.distance = dis[i][0]; cur_vector.push_back( sta ); } //依次递推，递推MAX-2次 for(int j=0;j::iterator iter; for(iter=pre_vector.begin();iter!=pre_vector.end();iter++) { status temp=*iter; if(contain(i,temp)==false)//为确保状态中没有重复路径 { status new_stat=temp; vector::iterator int_iter=new_stat.unvisited.begin(); new_stat.unvisited.insert(int_iter,new_stat.curcity);//加入vector new_stat.type.insert(new_stat.curcity);//加入set new_stat.distance+=dis[i][new_stat.curcity];//计算距离 new_stat.curcity=i; cur_vector.push_back(new_stat); } } } //记录相同状态最短路径，并合并相同状态 cur_vector=combine(cur_vector); }//end for //递推完毕后，最后一步，计算起点到每个状态的距离，找到最短路径 vector::iterator iter=cur_vector.begin(); status shortest=*iter; int min_dis=shortest.distance+dis[0][shortest.curcity]; iter++; for(;iter!=cur_vector.end();iter++) { int temp_dis=dis[0][(*iter).curcity]+(*iter).distance; if(temp_dis::iterator iter_city; cout<<"minimum distance is "< #include #include #define MAX 5 //做修改，将MAX改为5 using namespace std; int dis[MAX][MAX] = { //将数据的输入做修改，当不去B即为2时，将 0, 250, 330, 210, 150, // 原数据的第2行第2列删除即可 250,0, 520, 430, 280, 330, 520, 0, 270, 185, 210, 430, 270, 0, 420, 150, 280,185, 420, 0 }; typedef struct { int curcity; //当前所在的城市 vector unvisited; //当前未访问的城市 set type; //由于set自动排序，相同状态的vector可能不同，但set必然相同 int distance; //从当前城市到终点回到起点的距离 } status; void printVec( vector vec ) // 测试用 { vector::iterator iter; vector::iterator it; for( iter = vec.begin( ); iter!=vec.end(); iter++ ) { cout << (*iter).curcity << " <"; for( it = (*iter).unvisited.begin( ); it != (*iter).unvisited.end( ); it++ ) { cout << *it <<" "; } cout << ">" << " distance:" << (*iter).distance << endl; } } bool contain( int i, status &sta ) // 看看当前状态的城市中是否包括城市i { vector::iterator iter; if( i == sta.curcity ) return true; else { for( iter = sta.unvisited.begin( ); iter != sta.unvisited.end( ); iter++ ) if( i == *iter ) return true; } return false; } vector combine(vector vec) // 合并相同状态 { vector new_vec; vector::iterator iter; status temp; while( vec.size( ) > 0 ) { iter = vec.begin(); temp = *iter; vec.erase( iter ); for( ; iter!=vec.end( ); iter++ ) { if( (temp.curcity == (*iter).curcity) && (temp.type == (*iter).type) ) { if( (*iter).distance < temp.distance ) temp=*iter; iter = vec.erase(iter); iter--; } } new_vec.push_back( temp ); } return new_vec; } int main() { vector pre_vector; vector cur_vector; //从后往前推，初始化 for( int i = 1; i < MAX; i++) { status sta; sta.curcity = i; sta.distance = dis[i][0]; cur_vector.push_back( sta ); } //依次递推，递推MAX-2次 for(int j=0;j::iterator iter; for(iter=pre_vector.begin();iter!=pre_vector.end();iter++) { status temp=*iter; if(contain(i,temp)==false)//为确保状态中没有重复路径 { status new_stat=temp; vector::iterator int_iter=new_stat.unvisited.begin(); new_stat.unvisited.insert(int_iter,new_stat.curcity);//加入vector new_stat.type.insert(new_stat.curcity);//加入set new_stat.distance+=dis[i][new_stat.curcity];//计算距离 new_stat.curcity=i; cur_vector.push_back(new_stat); } } } //记录相同状态最短路径，并合并相同状态 cur_vector=combine(cur_vector); }//end for //printVec(cur_vector); //递推完毕后，最后一步，计算起点到每个状态的距离，找到最短路径 vector::iterator iter=cur_vector.begin(); status shortest=*iter; int min_dis=shortest.distance+dis[0][shortest.curcity]; iter++; for(;iter!=cur_vector.end();iter++) { int temp_dis=dis[0][(*iter).curcity]+(*iter).distance; if(temp_dis::iterator iter_city; cout<<"minimum distance is "<0 x2>0 x3>0 end gin 3 前面选取八种物品的情形LINDO的程序如下 max 1300x1+2750x2+320x3+4350x4+1400x5+300x6+120x7+600x8 st x1+2x2+4x3+3x4+4x5+2x6+2x7+x8<15 x1>0 x2>0 x3>0 x4>0 x5>0 x6>0 x7>0 x8>0 end gin 3