黄石理工学院
数学建模大型作业2011—2012 学年第1学期
目录
一．摘要
二．旅行问题
1.问题描述
2.符号说明
3.模型设计
4.建模求解
5.模型分析
6.
三．建模过程及心得体会
四．参考文件
一．摘要
本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。
关键词：HAMILTON回路LINGO 最优旅行路线0-1模型
二．旅行问题
问题描述
某人要在假期内从城市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
价格
(元)
模型设计
首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。 问题1.
分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立：
对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。假设ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66
1
ij ij
i j
d
x =∑∑ (i ≠j)
s.t.
6
1ij
i x
=∑=1 （i ≠j ；j=1,2, (6)
6
1
ij
j x
=∑=1 (i ≠j ；i=1,2, (6)
1
i j i j u u n x n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6) 其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，i u =访问城市的顺序数。
模型求解
运用LINGO ，输入程序：
MODEL :
!Traveling Sales Problem for the cities of six city; SETS :
CITY / 1..6/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 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 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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:
!Traveling Sales Problem for the cities of six city;
SETS:
CITY / 1..5/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 0 120 330 210 150
120 0 350 225 300
330 350 0 270 185
210 225 270 0 420
150 300 185 420 0 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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:
!Traveling Sales Problem for the cities of six city; SETS:
CITY / 1..5/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 0 120 250 210 150
120 0 98 225 300
250 98 0 430 280
210 225 430 0 420
150 300 280 420 0 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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:
!Traveling Sales Problem for the cities of six city; SETS:
CITY / 1..5/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 0 120 250 330 150
120 0 98 350 300
250 98 0 520 280
330 350 520 0 185
150 300 280 185 0 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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:
!Traveling Sales Problem for the cities of six city; SETS:
CITY / 1..5/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 0 120 250 330 210
120 0 98 350 225
250 98 0 520 430
330 350 520 0 270
210 225 430 270 0 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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:
!Traveling Sales Problem for the cities of six city;
SETS:
CITY / 1..5/: U; ! U( I) = sequence no. of city;
LINK( CITY, CITY): COST, ! The cost matrix;
X; ! X( I, J) = 1 if we use link I, J;
ENDSETS
DATA: !Cost matrix, it need not be symmetric;
COST= 0 250 330 210 150
250 0 520 430 280
330 520 0 270 185
210 430 270 0 420
150 280 185 420 0 ;
ENDDATA
N= @SIZE( CITY);
MIN= @SUM( LINK: COST * X);
@FOR( CITY( K): !It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
!Weak form of the subtour breaking constrains;
!These are not very powerful for large problems;
@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)); !Make the X's 0/1;
! For the first and last stop we know...;
@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,i b 为每个物品的重量，i c 为每个物品各自的价格。定义一个变量i x ，当i x =1是，表示装第i 件物品，当i x =0时，则不装（i=1,2,……,8）. 则约束条件为： max z=
8
1
i i i c x =∑
8
1
i i
i b x
b =≤∑
i x =0或1，（i=1,2, (8)
模型求解：
利用LINGO 软件求解，在LINGO 中输入以下程序：
model : sets : M/1..8/:W; price/1..8/:p; number/1..8/:x; endsets data :
W=1,2,4,3,4,2,2,1;
P=1300,2750,320,4350,1400,300,120,600; enddata
MAX =@SUM (M:X*P); @SUM (M:X*W)<=15; @FOR (M:@BIN (X)); End
得到结果：
选择照相机，衣服，摄像机，渔具，酒，食品和香烟，最大价值为10820。
三．建模过程及心得体会
数学建模是一个经历观察、思考、归类、抽象与总结的过程，也是一个信息捕捉、筛选、整理的过程，更是一个思想与方法的产生与选择的过程。它给学生再现了一种“微型科研”的过程。数学建模教学有利于激发学生学习数学的兴趣，丰富学生数学探索的情感体验；有利于学生自觉检验、巩固所学的数学知识，促进知识的深化、发展；有利于学生体会和感悟数学思想方法。同时教师自身具备数学模型的构建意识与能力，才能指导和要求学生通过主动思维，自主构建有效的数学模型，从而使数学课堂彰显科学的魅力。
为了使描述更具科学性，逻辑性，客观性和可重复性，人们采用一种普遍认为比较严格的语言来描述各种现象，这种语言就是数学。使用数学语言描述的事物就
称为数学模型。有时候我们需要做一些实验，但这些实验往往用抽象出来了的数学模型作为实际物体的代替而进行相应的实验，实验本身也是实际操作的一种理论替代。
数学建模要有团队精神。数学建模不是一个人的事，是团队的一项活动。三个人要相互支持，相互鼓励。不能只管自己的那一部分。特别是模型的建立，一个人根本不可能想的那么全面，只有大家一起讨论才能把问题搞清楚。
必须合理的安排时间。做任何事情，合理的时间安排非常重要，建模也是一样，事先要做好一个规划，建模一共分十个板块。你每天昨晚哪几个板块事先要确定好，这样做才会使自己游刃有余，保证在规定的时间内完成论文，以避免在时间上的不妥，以至于最后无法完成论文。有些同学经常会借鉴一些别人的论文里的思想，然后变成自己的东西，不过那也是一种能力，不能小瞧。所以也要多看些别人的论文来调高自己。
四．参考文件。
【1】.运筹学，科学出版社，徐玖平，胡知能，2003年11月第一版
【2】.运筹学——数据，模型，决策，科学出版社，徐玖平，胡知能，2006年3月第一版
黄石理工学院 数学建模大型作业2011—2012 学年第1学期
目录 一．摘要 二．旅行问题 1.问题描述 2.符号说明 3.模型设计 4.建模求解 5.模型分析 6. 三．建模过程及心得体会 四．参考文件
一．摘要 本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。 关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型 二．旅行问题 问题描述 某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F 旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？ 在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。
模型设计 首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。 问题1. 分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立： 对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。假设ij d 表示从城市i 到城市j 的费用。定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则 ij x =0。则旅行问题的数学模型可表示为一个整数规划问题。 min z=66 1 ij ij i j d x =∑∑ (i ≠j) s.t. 6 1ij i x =∑=1 （i ≠j ；j=1,2, (6) 6 1 ij j x =∑=1 (i ≠j ；i=1,2, (6) 1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6) 其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，i u =访问城市的顺序数。 模型求解 运用LINGO ，输入程序： MODEL : !Traveling Sales Problem for the cities of six city; SETS :
排队模型之港口系统 本文通过排队论和蒙特卡洛方法解决了生产系统的效率问题，通过对工具到达时间和服务时间的计算机拟合，将基本模型确定在//1 M M排队模型，通过对此基本模型的分析和改进，在概率论相关理论的基础之上使用计算机模拟仿真（蒙特卡洛法）对生产系统的整个运行过程进行模拟，得出最后的结论。好。 关键词：问题提出： 一个带有船只卸货设备的小港口，任何时间仅能为一艘船只卸货。船只进港是为了卸货，响铃两艘船到达的时间间隔在15分钟到145分钟变化。一艘船只卸货的时间有所卸货物的类型决定，在15分钟到90分钟之间变化。 那么，每艘船只在港口的平均时间和最长时间是多少 若一艘船只的等待时间是从到达到开始卸货的时间，每艘船只的平均等待时间和最长等待时间是多少 卸货设备空闲时间的百分比是多少 船只排队最长的长度是多少 问题分析： 排队论：排队论(Queuing Theory) ，是研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支。本题研究的是生产系统的效率问题，可以将磨损的工具认为顾客，将打磨机当做服务系统。【1】 //1 M M：较为经典的一种排队论模式，按照前面的Kendall记号定义，前面的M代表顾客(工具)到达时间服从泊松分布，后面的M则表示服务时间服从负指数分布，1为仅有一个打磨机。 蒙特卡洛方法：蒙特卡洛法蒙特卡洛(Monte Carlo)方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战进研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。（2） 排队论研究的基本问题 1.排队系统的统计推断:即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。 2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。【3】 为了得到一些合理的答案，利用计算器或可编程计算器来模拟港口的活动。 假定相邻两艘船到达的时间间隔和每艘船只卸货的时间区间分布，加入两艘船到达的时间间隔可以是15到145之间的任何数，且这个区间内的任何整数等可能的出现。再给出模拟这个系统的一般算法之间，考虑有5艘传至的假象情况。
黄金周旅游方案设计 摘要 本文主要解决的是去安徽旅游的最佳旅游路线的设计问题。花最少的钱游览尽可能满意度高的景点是我们追求的目标。基于对此的研究，我们建立了三个模型。 针对方案一：建立了单目标最优化模型。选定10个游览景点，在约束条件下，建立0-1规划模型，以总费用最小为目标函数。使用 lingo 编程，最后求得的最小费用是：755元。具体方案为：11→7→ 4→6→3→2→1→10→11 针对方案二：建立了单目标最优化模型。巧妙地将该问题化为TSP，以满意度为目标函数，在时间的约束条件下，运用lingo 编程，最后求得满意度是：0.86。旅游路线为： 11→2→4→7→9→10→11 针对方案三：建立了多目标最优化模型。基于方案一与二，以最小费用和最大满意度为目标函数，在约束条件下，采用分层求解法，运用lingo 编程，最后得出满意度是：0.83，费用为782元。推荐路线：11→2→7→6→3→10→9→11 关键词：多目标最优化模型 0-1规划模型 TSP lingo求解 一、问题重述 1.1问题背景 安徽是全国旅游大省，每年接纳游客上千万人次。现假设黄金周期间，你在外地读书的老同学、好朋友前来看望你，并要在安徽游玩几天，请查阅相关资料，从车费，餐饮，门票，景点满意度等多方面综合考虑，建立相关数学模型，列出一个四天三夜的游玩计划。 1.2需要解决的问题 根据对题目的理解我们可以知道，需要解决的问题是在安徽游玩四天三夜，并且综合考虑车费，餐饮，门票，景点满意度等多方面因素。所以我们的目标就是在满足所有约束条件的情况下，求出最少费用。 二、模型假设 假设1：旅行路线的总路程不包括在某一城市中观光旅游的路程； 假设2：旅行者在某一城市的旅游结束前往下一个目的地时，所乘坐的交通工具都是非常顺利的，不会出现被滞留等意外情况；
有一个推销员，从城市1出发，要遍访城市2，3，…，n 各一次，最后返回城市1。已知从城市i 到j 的旅费为ij c ，问他应按怎样的次序访问这些城市，使得总旅费最少？ 可以用多种方法把TSP 表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。 在下述意义下，引入一些0-1整数变量： ij x ?? ?≠=其它情况，且到巡回路线是从，0,1j i j i 其目标只是使∑=n j i ij ij x c 1 ,为最小。 这里有两个明显的必须满足的条件： 访问城市i 后必须要有一个即将访问的确切城市；访问城市j 前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。 n i x n j ij ,,2,1, 11 ==∑= n j x n i ij ,,2,1, 11 ==∑= 到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP 来说并不充分，仅仅是必要条件。例如： 以上两个条件都满足，但它显然不是TSP 的解，它存在两个子巡回。 这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量 ),,3,2(n i u i =附加到问题中。可把这些变量看作是连续的（最然这些变量在最 优解中取普通的整数值）。现在附加下面形式的约束条件 n j i n x n u u ij j i ≤≠≤-≤+-2, 1。 为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线都不满足该约 束条件；（2）全部巡回都满足该约束条件。 首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为121i i i i k ，则必有(对于所有的i k 都满足大 于2的限制条件) 1 11132121-≤+--≤+--≤+-n n u u n n u u n n u u i i i i i i k 把这k 个式子相加，有 1-≤n n ，矛盾！ 故假设不正确，结论（1）得证。 下面证明（2），采用构造法。对于任意的总巡回1111-n i i ，可取 =i u 访问城市i 的顺序数。 下面来证明总巡回满足该约束条件。 1 2 3 4 5 6
重庆交通大学 学生实验报告 实验课程名称数学建模 ^ 开课实验室数学实验室 学院信息院11 级软件专业班 1 班 学生姓名 学号 ￥ 开课时间2013 至2014 学年第 1 学期
！ 】 )
/ 实验一 钢管下料问题 摘要 ( 生产中常会遇到通过切割、剪裁、冲压等手段,将原材料加工成规定大小的某种,称为原料下料问题.按照进一步的工艺要求,确定下料方案,使用料最省,或利润最大是典型的优化问题.下面我们采用数学规划模型建立线性规划模型并借助LINGO 来解决这类问题. 关键词线性规划最优解钢管下料 一，问题重述 1、问题的提出 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割出售．从钢管厂进货得到的原材料的钢管的长度都是1850mm ，现在一顾客需要15根290 mm，28根315 mm，21根350 mm和30根455 mm的钢管．为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，以此类推，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5根产品），此外为了减少余料浪费，每种切割模式下的余料浪费不能超过100 mm，为了使总费用最小，应该如何下料 ` 2、问题的分析 首先确定合理的切割模式，其次对于不同的分别进行计算得到加工费用，通
过不同的切割模式进行比较，按照一定的排列组合，得最优的切割模式组，进而使工加工的总费用最少. 二，基本假设与符号说明 1、基本假设 假设每根钢管的长度相等且切割模式理想化.不考虑偶然因素导致的整个切割过程无法进行. 2、定义符号说明 （1）设每根钢管的价格为a ，为简化问题先不进行对a 的计算. （2）四种不同的切割模式：1x 、2x 、3x 、4x . 》 （3）其对应的钢管数量分别为：i r 1、i r 2、i r 3、i r 4（非负整数）. 三、模型的建立 由于不同的模式不能超过四种，可以用i x 表示i 按照第种模式（i =1,2,3,4）切割的原料钢管的根数，显然它们应当是非负整数.设所使用的第i 种切割模式下 每根原料钢管生产290mm ，315mm,,350mm 和455mm 的钢管数量分别为i r 1，i r 2，i r 3，i r 4（非负整数）. 决策目标 切割钢管总费用最小，目标为： Min=（1x ?+2x ?+3x ?+4x ?）?a (1) 为简化问题先不带入a 约束条件 为满足客户需求应有 11r ?1x +12r ?2x +13r ?3x +14r ?4x ≧15 (2) ( 21r ?1x +22r ?2x +23r ?3x +24r ?4x ≧28 (3) 31r ?1x +32r ?2x +33r ?3x +34r ?4x ≧21 (4) 41r ?1x +42r ?2x +43r ?3x +44r ?4x ≧15 (5) 每一种切割模式必须可行、合理，所以每根钢管的成品量不能大于1850mm 也不能小于1750mm.于是： 1750≦290?11r +315?21r +350?31r +455?41r ≦1850 （6） 1750≦290?12r +315?22r +350?32r +455?42r ≦1850 （7） 1750≦290?13r +315?23r +350?33r +455?43r ≦1850
1 预测模块：灰色预测、时间序列预测、神经网络预测、曲线拟合（线性回归）； 2 归类判别：欧氏距离判别、fisher判别等； 3 图论：最短路径求法； 4 最优化：列方程组用lindo 或lingo软件解； 5 其他方法：层次分析法马尔可夫链主成分析法等； 6 用到软件：matlab lindo （lingo）excel ； 7 比赛前写几篇数模论文。 这是每年参赛的赛提以及获奖作品的解法，你自己估量着吧…… 赛题解法 93A非线性交调的频率设计拟合、规划 93B足球队排名图论、层次分析、整数规划 94A逢山开路图论、插值、动态规划 94B锁具装箱问题图论、组合数学 95A飞行管理问题非线性规划、线性规划 95B天车与冶炼炉的作业调度动态规划、排队论、图论 96A最优捕鱼策略微分方程、优化 96B节水洗衣机非线性规划 97A零件的参数设计非线性规划 97B截断切割的最优排列随机模拟、图论 98A一类投资组合问题多目标优化、非线性规划 98B灾情巡视的最佳路线图论、组合优化 99A自动化车床管理随机优化、计算机模拟 99B钻井布局0-1规划、图论 00A DNA序列分类模式识别、Fisher判别、人工神经网络 00B钢管订购和运输组合优化、运输问题 01A血管三维重建曲线拟合、曲面重建 01B 工交车调度问题多目标规划 02A车灯线光源的优化非线性规划 02B彩票问题单目标决策 03A SARS的传播微分方程、差分方程 03B 露天矿生产的车辆安排整数规划、运输问题 04A奥运会临时超市网点设计统计分析、数据处理、优化 04B电力市场的输电阻塞管理数据拟合、优化 05A长江水质的评价和预测预测评价、数据处理 05B DVD在线租赁随机规划、整数规划
旅游路线最短问题的优化模型 一、摘要 本题建立了一个关于自驾游的云南旅游路线最短问题的优化模型。最短路问题就是要在所有从s v到t v的路中，求一条权最小的路，首先根据提供的信息，描绘出一个自驾游行车路线的赋权有向图；然后把最短路问题看成是一种特殊的最小费用流问题；建立0—1整数规划模型；再用Dijkstra算法对其进行求解。
二、问题重述 有一个从没有到过云南的人准备在假期带家人到云南旅游，预计从昆明出发，并最终返回昆明。如何以自驾游的旅行方式设计一条在云南旅游的最佳路线。从上面的例子出发，讨论如下问题： （1） 他和他的家人经济是否宽裕 （2） 旅游景点的选择问题 （3） 描绘可能行车路线的过程 （4） 最短路问题转化为0—1整数规划模型 （5） 在赋权有向图中寻求最短路的Dijkstra 算法 三、模型假设 （1） 他和他的家人经济宽裕，随心旅游 （2） 选择的旅游景点都在昆明的附近 （3） 行车路线全程高速，行车速度在80—120km/h 之间 （4） 路况良好，沿途加油方便 （5） 旅途中，无特殊情况发生 （6） 各个景点之间不再有其他旅游景点 四、符号说明 1234567(){,,,,,,}V G V V V V V V V 其中1V 代表昆明，2V 代表玉溪， 3V 代表大理，4V 代表楚雄，5V 代表香格里拉，6V 代表丽江，7V 代表昆明，这些都为可能经过的旅游景点， E(G)=A={84,330,184,100,176,1086,200,400,349,200,533,1000}表示各个旅游景点之间的距离，
((),())G V G E G =表示赋权有向图， S V 表示发点 ， t V 表示收点， i V 表示从起点到该顶点的最短长度的下界， j V 表示从起点到该顶点的最短长度的上界， (,) i j a V V =表示每一条弧， ()ij w a w =表示每一条弧相应的权， ()i p V 表示从发点S V 到 i V 的最短路的距离， ()i V λ表示从发点S V 到 i V 的最短路上i V 前面一个邻点的下标， M 表示任意常数， T( i V ) 表示从S V 到该点的最短路的权的上界， Si 表示第i 步，具有P 标号点的集合。 五、模型建立 在赋权有向图((),())G V G E G =中，寻求从发点 S V 到收点t V 的最短 路问题实际上是一中特殊的最小费用流问题。此时，可将各弧的权解释为其单位流量的费用，从 S V 到t V 的某一条路可以解释为有向图 ((),())G V G E G =的相应路中流量为1的流。所以，使该流的费用 最小就等价于使该路最短。这里，发点S V 的净输出量为1，收点t V 的 净输入量为1，其他中间点的流出量等于流入量。 由此，最短路问题可转化为如下0—1整数规划模型，
以点0表示旅行商的出发城市，称为源点，点1,2, ,l 表示m 个旅行商需访 问的城市。MTSP 问题的数学模型可以表示为： 令10ij x ?=??弧(i,j)在线路上 弧(i,j)不在线路上 模型表示如下： 0000min 10,1,,10,1,,()01,0,1,,R R ij ij i j R ij i R ij j ij ij z d x x j R x i R X x S x i j R ====?=?? ?==????==??=∈??==?∑∑∑∑或 式中：1;ij R m l d =+-为增广费用。若用(,1,,)ij c i j l =表示旅行商经过对应弧度(,)i j 所花的费用，如时间、距离、花费等，那么给ij c 增加(1)m -行和(1)m -列，每一新的行或列是ij c 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用ij d 。 一般MTSP 中，旅行商访问l 个城市必须满足以下2个条件。 条件1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m 条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP ，可通过附加虚拟城市的方法把MTSP 转化为TSP 。将另外(1)m -个旅行商理解为(1)m -个虚拟城市，这(1)m -个虚拟城市标号分别为1,2,,1,l l l m +++-，它们与城市0具有相同的坐标(即相同位置)。在旅行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP 中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(1)m -个虚拟城市到原点的距离为 00(,0,1,,1),ij c M i j l l m M ==++-为一无穷大的正数（即永远不能达到），到其他各点距离与原点一致，这样遗传算法就不会出现0-0-0的途径。将源点0复制(1)m -个，m 个源点编号为0,1,1,l l m ++-每一个同源点0一样与其他
钢管下料问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m 。 (1）现在一客户需要50根4m 、20根6m 和15根8m 的钢管。应如何下料最节省？ (2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5m 的钢管。应如何下料最节省。 问题（1）分析与模型建立 首先分析1根19m 的钢管切割为4m 、6m 、8m 的钢管的模式，所有模式相当于求解不等式方程： 12346819 k k k ++≤ 的整数解。但要求剩余材料12319(468)4r k k k =-++<。 容易得到所有模式见表1。 决策变量 用i x 表示按照第i 种模式(i=1,2,…，7)切割的原料钢管的根数。 以切割原料钢管的总根数最少为目标，则有 1234567min z x x x x x x x =++++++ 约束条件 为满足客户的需求，4米长的钢管至少50根，有
1236743250x x x x x ++++≥ 6米长的钢管至少20根，有 25673220x x x x +++≥ 8米长的钢管至少15根，有 346215x x x ++≥ 因此模型为： 1234567min z x x x x x x x =++++++ 123672567346432503220..215,1,2,,7 i x x x x x x x x x s t x x x x i ++++≥??+++≥??++≥??=? 取整 解得： 12345670,12,0,0,0,15,0x x x x x x x ======= 目标值z=27。 即12根钢管采用切割模式2：3根4m ，1根6m ，余料1m 。 15根钢管采用切割模式6：1根4m ，1根6m ，1根8m ，余料1m 。 切割模式只采用了2种，余料为27m ，使用钢管27根。 LINGO 程序： model: sets: model/1..7/:x; endsets min=x(1)+x(2)+x(3)+x(4)+x(5)+x(6)+x(7); 4*x(1)+3*x(2)+2*x(3)+x(6)+x(7)>=50; x(2)+3*x(5)+x(6)+2*x(7)>=20; x(3)+2*x(4)+x(6)>=15; @for(model(i):@gin(x(i))); end 问题（2）模型建立 首先分析1根19m 的钢管切割为4m 、6m 、8m 、5m 的钢管的模式，所有模式相当
数学建模中竞赛阅读中的问题 摘要 本文主要研究的是数学建模竞赛中试卷的优化配发，评分的标准化处理及对教师的评阅效果定量评价的问题． 问题一：针对试卷的随机分发问题，先利用MATLAB软件自带的randperm 函数产生一个1至500的随机矩阵，再用reshape函数对其进行重新排列成25行20列的矩阵，对矩阵y进行列列交换的变化成两个新矩阵y1与y2，构成75行20列的新矩阵z=[]2 ,1 y y，从而实现对试卷的随机分发；针对均匀性问题， ,y 以交叉数的方差作为评价任务单均匀性的评定指标，从多个随机分配方案中，选取交叉数方差最小的任务单供组委会使用． 问题二：评分的预处理需要对评阅教师的分数进行标准化，评分预处理方法是将不同的评分者变换到同一个尺度下，就是以某一位评分者的均值作为参照点，以其标准差表示距离转化为以零为参照点的标准分；然后采用均值为70标准差为10将标准分转化为百分制的标准，分这样使得标准分与原始分相差不大；最后将同一份试卷的三个标准评分的几何平均值作为该份试卷的最终标准分．将附录中的200份试卷的数据根据用Excel软件的统计与函数功能最终得到各份试卷的标准分值． 问题三：针对教师评阅效果的评价问题，本文给出两个评价标准：分别是评阅的原始成绩的可信度和评阅的原始成绩与成绩标准化合成后的最终成绩的偏差值的稳定性．对于可信度，结合评分分制，对评阅的原始成绩与成绩标准化合成后的最终成绩的差分值做百分化处理，建立可信度数学模型，得出可信度最高的有10，11，15，19，20号教师，高达96%；对于偏差值的稳定性，采用偏差值的方差来反映，得出稳定性最好的是第3号教师，稳定性较好的还有第1，7，10，11，19号教师．最后，综合可信度和偏差值的稳定性两项指标，得出评阅效果较好的教师有第1，3，10，11，15，19，20号教师，在下一次阅卷后合成成绩的时候可以考虑给他们以更大的权重． 关键词：随机数矩阵标准化参照点可信度偏差值
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的 i j=L位置上的数表示（其中∞表示两个客户之间无直接的路线到i j(,1,,10) (,) 达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给 客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能 装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送
数学建模第三次作业 下料问题 摘要 本文是针对如何对钢管进行下料问题，根据题目要求以及下料时有关问题进行建立切割费用最少以及切割总根数最少两个目标函数通过结果分析需要使用何种切割模式。 生产方式所花费的成本价格或多或少有所不同，如何选取合理的生产方式以节约成本成为了很多厂家的急需解决的问题。这不仅仅关系到厂家的利益，也影响到一个国家甚至整个人类星球的可利用资源，人们的生活水平不断提高对物资的需求量也不断上升，制定有效合理的生产方式不仅可以为生产者节约成本也可以为社会节约资源，以达到资源利用最大化。本文以用于切割钢管花费最省及切割总根数最少为优化目标，通过构建多元函数和建立线性整数规划模型，利用数学及相关方面的知识对钢管的切割方式进行优化求解最佳方案。 本文最大的特色在于通过求解出切割钢管花费最省及切割总根数最少时分别得出两种目标函数取最小值时的切割模式。通过结果发现两种目标函数取最小值时所需切割根数都一样。于是选择切割钢管花费最省为目标函数，此时的切割模式达到最少，这样既满足了总根数最小有满足了切割费用最小。 关键词：切割模式LINGO软件线性整数
一、问题的提出 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后出售。从钢管厂进货时得到的原料钢管的长度都是1850mm。现有一客户需要15根290mm、28根315mm、21根350mm和30根455mm的钢管。为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，依次类推，且每种切割模式下的切割次数不能太多（一根钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料不能超过100mm。为了使总费用最小，应如何下料？ 二、基本假设 1、假设所研究的每根钢管的长度均为1850mm的钢管。 2、假设每次切割都准确无误。 3、假设切割费用短时间内不会波动为固定值。 5、假设钢管余料价值为0. 6、假设一切运作基本正常不会产生意外事件。 7、每一根钢管的费用都一样，为一常值。 三、符号说明
最佳旅游路线设计 摘要 本文主要研究最佳旅游路线的设计问题。在满足相关约束条件的情况下，花最少的钱游览尽可能多的景点是我们追求的目标。基于对此的研究，建立数学模型，设计出最佳的旅游路线。 第一问给定时间约束，要求为主办方设计合适的旅游路线。我们建立了一个最优规划模型，在给定游览景点个数的情况下以人均总费用最小为目标。再引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件，使用lingo编程对模型求解。推荐方案：→都江堰→青城山→丹巴→→，人均费用为949元（此处不考虑旅游人数对游览费用的影响）。 第二问放松时间约束，要求代表们游遍所有的景点，该问题也就成了典型的货郎担（TSP）问题。同样使用第一问的模型，改变时间约束，使用lingo编程得到最佳旅游路线为：→→峨眉→海螺沟→→丹巴→四姑娘山→青城山→都江堰→九寨沟→黄龙→，人均费用为3243元。 第三问要求在第一问的基础上充分考虑代表们的旅游意向，建立模型求解。通过对附件一数据的观察，我们使用综合评判的方法，巧妙地将代表们的意愿转化为对相应旅游景点的权重，再对第一问的模型稍加修改，编程求出对应不同景点数的最佳路线。推荐路线：→→都江堰→青城山→丹巴→，人均费用为927元。 对于第四问，由于参观景点的人数越多每人承担的费用越少，因此我们要考虑的是尽量使得两组代表在共同旅游的时间在相同的景点游览。正是基于此，我们建立模型求解。推荐路线：第一组：→→丹巴→都江堰→青城山→第二组：→都江堰→青城山→峨眉→→，两组在都江堰会合并且共同游览了都江堰和青城山，人均费用为971元。 第五问中，首先我们修改了不合理数据，并用SPSS软件对缺省数据进行了时间序列预测。其次我们合理定义了阴雨天气带来的损失，以人均总花费最小和阴雨天气带来的损失最小为目标，建立加权双目标规划模型。推荐路线：→→青城山→都江堰→→，相应人均消费987元，阴雨天气带来的损失为1.6。 本文思路清晰，模型恰当，结果合理.由于附件所给数据的繁杂，给数据的整理带来了很多麻烦，故我们利用Excel排序，SPSS预测，这样给处理数据带来了不少的方便。本文成功地对0—1变量进行了使用和约束，简化了模型建立难度，并且可方便地利用数学软件进行求解。此外，本文建立的模型具有很强普适性，便于推广。 关键词：最佳路线TCP问题综合评判景点个数最小费用 1 问题重述
3.下料问题 班级：计科0901班姓名：徐松林学号：2009115010130 摘要： 本文建立模型，以最少数量的原材料以及最少的余料浪费来满足客户的需求。主要考虑到两方面的问题。钢管零售商是短时间内出售钢管，则应该以最少原材料根数为目标函数来建模模型；钢管零售商是长时间内出售钢管，则应该以最少余料浪费为目标函数。有效地使用背包问题及线性规划、非线性规划等算法，算出最优解。特别是钢管零售商是短时间内出售钢管，需要分析切割模式的种类1到4种的各个情况的整数最优解，再依次比较每个情况的最优解得出总的最优解。 关键词：余料、原材料、加工费、总费用。 一、问题背景 工厂在实际生产中需要对标准尺寸的原材料进行切割，以满足进一步加工的需要，成为下料问题。 相关数据表明，原材料成本占总生产成本的百分比可以高达45%～60%，而下料方案的优劣直接影响原材料的利用率，进而影响原材料成本。因此需要建立优化的下料方案，以最少数量的原材料以及最少的余料浪费，尽可能按时完成需求任务。 二．问题描述及提出 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出.从钢管厂进货时得到的原料钢管长度都是1850mm.现有一客户需要15根290mm、28根315mm、21根350mm 和30根455mm的钢管.为了简化生产过程，规定所使用的切割模式的种类不能超过4种，使用频率最高的一种切割模式按照一根原料钢管价值的1/10增加费用，使用频率次之的切割模式按照一根原料钢管价值的2/10增加费用，依此类推，且每种切割模式下的切割次数不能太多（一根原料钢管最多生产5根产品）。此外，为了减少余料浪费，每种切割模式下的余料浪费不能超过100mm.为了使总费用最小，应如何下料？ 在该目标下要求考虑下面两个问题： 1.若钢管零售商是短时间内出售钢管（即每次将钢管按照顾客的要求切割后售 出，多余的零件不准备下次售出），则每次应该以最少原材料根数为目标函数。
数学建模的十大算法 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理）
令x ij 弧(i,j)在线路上 弧(i,j) 不在线路上 以点0表示旅行商的出发城市，称为源点，点1,2丄，1表示m个旅行商需访 问的城市。MTSP问题的数学模型可以表示为: 模型表示如下: RR min z d ij x ij i0j0 R x ij 1 j 0,1,L ,R i0 R x ij 1 i 0,1,L ,R j0 X (x ij ) S x ij 0或1 i, j 0,1,L ,R 式中：R m l 1;d ij为增广费用。若用C ij (i,j 1,L ,1)表示旅行商经过对应弧度(i, j)所花的费用，如时间、距离、花费等，那么给q增加(m 1)行和(m 1)列，每一新的行或列是c ij 的最后一行或列的复制，增广矩阵的其他元素为无穷大，由此构成了增广费用d ij 。 一般MTSP中，旅行商访问I个城市必须满足以下2个条件。 条件 1：从指定城市出发，对其他所有城市严格访问一次后返回原出发城市。 条件2：一条有效路径严格由m条非平凡子路径(Nontrivial Subtours)组成。所谓非平凡子路径是指该路径中除出发城市外，至少访问一个其他城市。 用遗传算法求解MTSP，可通过附加虚拟城市的方法把 MTSP转化为TSP。 将另外(m 1)个旅行商理解为(m 1)个虚拟城市，这(m 1)个虚拟城市标号分 别为l 1,l 2,L ,l m 1,，它们与城市0具有相同的坐标(即相同位置)。在旅 行商访问路径中出现的每一个虚拟城市均表示旅行商返回出发城市，从而组成一个回路。每个回路表示MTSP中一个旅行商的旅行路径。需注意的是，为了避免出现平凡子路径，必须假设(m 1)个虚拟城市到原点的距离为 c ij M0(i, j 0,l 1,L ,l m 1 ) , M 0为一无穷大的正数(即永远不能达到) ，到其他各点距离与原点一致，这样遗传算法就不会出现 0-0-0 的途径。将源点 0 复制(m 1)个，m个源点编号为0,1 1,L l m 1,每一个同源点0 —样与其他
随机库存的分配 摘要 卖方管理库存（VMI，Vendor-Managed Inventory）是现代物流中一个比较新的管理思想，它是指货物的提供者根据所有客户的当前库存量决定在一定时间内对他们的货物分配量。基于VMI思想，设计出当供货方的供应能力有限、客户需求随机情况下的分配方案，能够应用到实际的物流管理信息系统中，具有实际意义。 针对此问题，在客户需求量服从同一指数分布的前提条件下，首先通过MATLAB软件编写程序，得到50个客户的随机需求量和初始库存量，然后从车辆配载能力出发，以客户的库存费用最小为目标函数，以供货总量和每辆车的承载能力为约束条件，建立非线性随机规划模型，通过lingo软件求解模型，得到所有客户库存费用最小时的分配方案，同时得到最小库存费用为699.5543。 关键词：随即需求库存分配随机规划
一、问题重述 考虑由一个供货方和n个客户组成的配送网络，配送活动的组织基于VMI 思想。假设供货方的供应能力有限(意味着某些客户可能得不到供应)，可供应的货物总量为A；拥有车辆数为K，车辆k的载重量为b k(k∈K)。每个客户的需求量是随机的，但需求的分布函数F i已知(假设F i是严格增函数，并假设不同客户的需求是相互独立的，且服从相同分布)，周期初的初始库存为βi，h+i为单位货物的保管费，h-i为单位货物的缺货损失费。令q i(w i)表示客户i在得到配送量w 时的库存费用函数。令y ik表示车辆k是否服务客户i，是取1，否取0。 i 当y ik(i=1，…，n；k=0，…，K)的取值确定后，也就意味着确定了对所有客户的一个划分，如令Y k表示车辆k服务的客户集合，其应满足Y k={i∶y ik=1}。 请写出库存分配问题的模型，并带入适当规模的数据进行计算，分析其计算结果，得出结论。 二、问题分析 本问题讨论的是当供货方的供应能力不足、客户需求随机情况下的库存分配问题。客户的需求量是随机的，但需求的分布函数F i已知(假设F i是严格增函数，并假设不同客户的需求是相互独立的，且服从相同分布)，在处理问题时，可以将需求量当作服从相同参数的同一指数分布，通过MATLAB软件来产生指数分布的随机数作为客户需求量，要使得所有客户的库存费用最小，需要构造与配送量、库存费、保管费等有关的目标函数，将有限的车辆数和每辆车的承载能力以及供货方的总供应量作为约束条件，建立模型，通过lingo软件求解得到具体的配送方案。 三、模型假设 1.假设客户的随即需求量服从参数为0.5的指数分布； 2.假设每个客户的初始库存量在0.1~1.5吨之间随即取值； 3.假设所有客户的库存保管费和缺货损失费相同； 4.假设供货方的总供应量为所有客户随即需求量之和的0.8倍； 5.假设不考虑运货车辆的运费。 四、符号说明
数学建模问题分析 1、给出一个所感兴趣的建模的实际问题:上班高峰车辆拥堵情况 (1) 写出问题的实际背景:**发展迅速，人们生活水平提高，私家车越来越多。上班高峰期车辆拥堵严重，通过调查统计603路公交车的双程的运行时间，与平常运行时间相对比，了解吴家坟?省体育场交通拥堵状况，合理地配置车辆资源。 (2) 给出解决问题的路径(建模与解答路径): 通过调查统计，绘制相应的统计图。 根据统计图，了解各路段的拥堵状况，对车辆的运行稍作调整。 ,将调查结果提供给市民，是他们可以适当地选择合理的交通工具和上班路线，适当地缓解交通压力。 (3)要解决什么样的问题:了解该路段的拥堵情况，选择合适的交通工具以及交通路线，适当地减轻交通拥堵，减轻交通压力。 2、找一本与数学建模有关的参考书:《数学模型方法》 作者:齐欢出版社:华中科技大学出版社 (1) 为何选择这本书, 数学的产生一直是和数学建模紧密相联的(实际上，一切科学研究都是首先与模型打交道，然后才在实际系统上实现(在本世纪70年代前后，数学建模再次形成热潮，主要是由于计算机的迅猛发展和日益广泛的应用(正如美国科学、工程和公共事务政策委员会在一份报告中指出的“今天，在技术科学中最有用的数学研究领域是数值分析和数学建模”。
何谓模型?简言之，模型是一种结构，它是由对原型的形象化或模拟与抽象而来、对原型的一个不失真的近似反映，例如建筑模型和玩具(数学模型是一种符号模型，在应用数学中，称反映特定的具体实体内在规律性的数学结构为数学模型。 本书的重点在于如何建立数学模型，而对这些数学模型的详细的教学分析，读者不难在有关的数学专业书中找到(建立数学模型的基本方法是机理分析法、数据分析法和计算机仿真。 数学模型方法是近10多年来随着计算机的广泛使用而发展起来的新学科，是利用数学知识解决实际问题的重要方法(这是一本关于数学建模的理论与方法的入门书，内容包括数学建模的方法论基础，以及数学建模的三种主要方法:机理分析法、数据分析法和计算机仿真，本书避免了详细的理论证明和复杂的数学推导，在众多的实例中，介绍了数学建模的大量方法与技巧，着重研究了在不同背景下数学模型的构造，内容生动，富有启发性。 凡具有微积分、线性代数和概率论知识的读者，即可掌握本书的基本内容，本书适于数学、应用数学、工程各专业、经济与管理等专业的本科生。 (2) 对数学建模的思想有何启示, 应用数学去解决各类实际问题时，建立数学模型是十分关键的一步，同时也是十分困难的一步。建立教学模型的过程，是把错综复杂的实际问题简化、抽象为合理的数学结构的过程。要通过调查、收集数据资料，观察和研究实际对象的固有特征和内在规律，抓住问题的主要矛盾，建立起反映实际问题的数量关系，然后利用数学的理论和方法去分析和解决问题。这就需要深厚扎实的数学基础，敏锐的洞察力和想象力，对实际问题的浓厚兴趣和广博的知识面。 本书的重点在于如何建立数学模型，而对这些数学模型的详细的教学分析。本书的目的在于通过多种建模方法的训练和大量实例的分析，提高学生的三个能力，即: