楚雄师范学院
2013年数学建模培训第一次预赛论文
题 目 田径赛安排优化模型
姓 名 马杰
系（院） 数学系
专 业 信息与计算科学
年 月 日
田径赛安排优化模型
摘要：本文通过对某校田径选拔赛比赛日程安排表进行分析规划，并针对参赛项目即跳高、跳远、标枪、铅球、100米和200米短跑，在规定每个选手至多参加三个项目的比赛，有七名选手报名的情况下，设计比赛日程安排表，使得在尽可能短的时间内完成比赛，找出最小目标函数和各项约束条件的数学表达式，建立数学规划模型。模型的求解过程中，采用数据结构图解法及数学软件LINGO等编写相应的程序，对建立的模型进行求解，得出最优结果。
关键字：LINGO数学软件 离散数学 0-1变量 线性规划 数据结构
- 1 -
一、问题重述
假设某校的田径选拔赛共设六个项目的比赛，即跳高、跳远、标枪、铅球、100米和200米短跑，规定每个选手至多参加三个项目的比赛，现有七名选手报名，选手所选项目如表所示。现在要求设计一个比赛日程安排表，使得在尽可能短的时间内完成比赛。 姓名 项目1 项目2 项目3 赵宁 跳高 跳远 铅球 钱虎 跳远 100米 孙正 跳高 200米 铅球 李江 200米 标枪 铅球 杨众 跳远 铅球 跳高 刘平 铅球 跳高 200米 王跃 标枪 跳远 100米 二、问题分析
根据条件分析：七名选手参加的比赛项目都没超过三个，说明他们所报的
项目都可以比赛。
对于这七个同学参加六项田径选拔比赛，要使比赛时间在短时间内尽可能完成比赛，主要考虑每个项目尽能在同时间内可以同时进行几个足够多项目的比赛，并且保证每个选手都有时间参加每个项目。我们最容易想到的一个办法就是穷举法，这种赛日安排方法共有6!=720种,显然不能用这种方法解决这类题。
根据条件，我们可以重新把上表重新排列出每个项目分有哪些项参加（如下表），通过下表我们就可以准确的找出相关的限制条件：每个时间段只能参加一项目，不能同时参加几个项目（例赵宁在同一时刻参加了跳高，就不能参加跳远和铅球）。我们可以用0?1变量表示每个项目是否在同一段时间是否进行，从而建立这个问题的0?1规划模型，借助现成的数学软件 求解。 项目(xj) 跳高 跳远 铅球 100米 200米 标枪 比 赛 选 手 赵宁 赵宁 钱虎 赵宁 孙正 李江 杨众 刘平 钱虎 王跃 孙正 李江 刘平 李江 王跃 孙正 杨众 杨众 刘平 王跃
- 2 -
三、模型假设
1.假设每个同学都会按时参加每个项目，有足够多老师或教练组织每一项比赛，保证同一时间段可以同时进行几个项目的比赛。
2.假设每个同学在同一时间段只能参加一个项目，即：参加一个项目后没有时间在去参加其他项目。
- 3 -
四、模型建立
引入0?1变量xj（j=1,2,3,4,5,6）表示项目（跳高，跳远，铅球，100米，200米，标枪）。若xj（项目）进行，记xj?1，否则记xj?0。根据参赛成员在同一时间段只能参加一个项目条件限制，xj应该满足以下约束条件：
Min Z= x1+x2+x3+x4+x5+x6
对于赵宁限制：x1+x2+x3=1;
对于钱虎限制： x2+x4=1; 对于孙正限制： x1+x3 +x5=1; 对于李江限制： x3 +x5+x6=1; 对于杨众限制： x1+x2+x3=1; 对于刘平限制： x1+x3 +x5=1; 对于王跃限制： x2 +x4+x6=1。
从而我们可以得到线性规划模型：
Min Z= x1+x2+x3+x4+x5+x6
s.t.
x1+x2+x3=1 x2+x4=1 x1+x3 +x5=1 x3 +x5+x6=1 x2 +x4+x6=1
五、模型求解
下面介绍两种解法 第一种解法（图表法）：
为了能较好地解决这个模型，可以根据该问题的数据结构模型图如下图（竞赛项目在所有的两个不能同时进行比赛的项目之间连上一条边仙），表示出同一
- 4 -
个选手选择的几个项目是不能在同一时间内比赛的，因此该选手选择的项目中没有两两相连的线，可以同时进行并且是所用的时间也是最短的。
由此可得：只要安排3个不同的时间竞赛即可。时间1内可以比赛跳高（X1）和标枪（X6），时间2内可以比赛跳远（X2）和200米（X5），时间3可以进行比赛铅球（X3）和100米（X4）。（但这种方法主观性太强，依据不强）
X1 X3 X2 X4 X5 X6 第二种解法：用LINGO直接求解，输入文件： model:
min=x1+x2+x3+x4+x5+x6; x1+x2+x3=1; x2+x4=1;
x1+x3 +x5=1; x3+x5+x6=1; x2+x4+x6=1; end int 6
求解可以得到最优解如下：
Global optimal solution found.
Objective value: 2.000000 Total solver iterations: 0
Variable Value Reduced Cost X1 0.000000 0.000000 X2 0.000000 0.000000 X3 1.000000 0.000000 X4 1.000000 0.000000 X5 0.000000 0.000000 X6 0.000000 0.000000 Row Slack or Surplus Dual Price 1 2.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 -1.000000
- 5 -
5 0.000000 0.000000 6 0.000000 -1.000000
根据LINGO所求得的解可以知道： X3=X4=1 ，可知：铅球（X3）和100米（X4）可以同时进行比赛，然后在由影子条件知：跳高（X1）和标枪（X6）也可同时进比赛，最后只剩下跳远（X2）和200米（X5），而他们的成员没有相同的，这两项也可同时进行比赛。从而要使赛程的时间最短，我们只要安排3个不同的时间竞赛分别安排能同时进行两个比赛项目即可。（由此我们也可以判定解法一也是正确的，并为一提供科学依据）
- 6 -
六、模型检验
根据上面解：我们把能同时进行的比赛项目排在同一时间进行比赛排表，由此可以简单的排出如下赛程表： 时间 1 2 3 项目 铅球 100米 跳高 标枪 跳远 200米 参 赵宁 钱虎 赵宁 李江 赵宁 孙正 赛 孙正 王跃 孙正 王跃 钱虎 李江 选 李江 杨众 杨众 刘平 手 杨众 刘平 王跃 刘平 由表可以看出：每个时间段安排两个比赛安排都是合理的，从而说明这个线性规划模型是正确的，确立这个模型也是一种解决该类问题的方法，。
- 7 -
七、模型评价
1.模型优点：
（1）该模型引用0-1变量是根据现有的数据资料假条件和假设建立数学规划模型，该模型都简单明确，容易接受。
（2）模型由于简单，容易接受，很多人在学这种方法可以掌握、推广解决到生活中去 。
（3）模型体现了应用数学软件的优异性。
（4）图论法也是解决这类问题的较好的方法，对数学软件不熟悉的人可以是一种首选方法。
2.模型不足：
本模型有较多的优点，但仍存在着一些缺陷，要求对对数学软件有一定的分析能力。比如：运用LINGO的数学软件不能得出一个该赛程的完整的方案，只能得出：可以同时进行的两项（X3=X4），其他药根据影子条件分析得出。
- 8 -
八、模型改进
如果你不具有很好的数学软件分析问题的能力，不会用影子条件来分析问题，我们可以在第一次模型求的解，根据先摆出第一时间段的的项目，然后再次建立下一时间段阶的模型。如下： model:
min=x1+x2+x5+x6; x1+x2=1; x1+x5=1; x5+x6=1; x2+x6=1; end int 6
Global optimal solution found. Objective value: 2.000000 Total solver iterations: 0
Variable Value Reduced Cost
X1 0.000000 0.000000
X2 1.000000 0.000000 X5 1.000000 0.000000 X6 0.000000 0.000000 Row Slack or Surplus Dual Price 1 2.000000 -1.000000 2 0.000000 0.000000 3 0.000000 -1.000000 4 0.000000 0.000000 5 0.000000 -1.000000
从这个模型我们可以得出：X2=X4=1，即：跳远（X2）和200米（X5）在这一时间段也可以同时进行，最后两个项目跳高（X1）和标枪（X6）成员没有相同的，它们不受限制，这两项也可同时进行比赛。
- 9 -
九、模型推广
在日常生活中，我们经常碰到工作日程表、课程表等规划问题，我们可以结合实际条件建立这种采用0-1变量问题建立简单的数学规划模型，然后采用常用的数学软件中求解的最优解，得出最后合理的方案，如果只要求最优结果，图论法也是解决这类问题的较好的方法，对数学软件不熟悉的人可以是一种首选方法。
10 - -
附录 参考文献
【1】中国大学生数学建模竞赛，李大潜主编，高等教育出版社(1998)．
【2】 大学生数学建模竞赛辅导教材，(一)(二)(三)，叶其孝主编，湖南教育 出版社(1993，1997，1998)．
【3】 数学建模教育与国际数学建模竞赛 《工科数学》专辑。
【4】数学模型，姜启源编，高等教育出版社(1987年第一版，1993年第二版，2003年第三版；第一版在 1992年国家教委举办的第二届全国优秀教材评选中获\全国优秀教材奖\． 【5】数学模型与计算机模拟，江裕钊、辛培情编，电子科技大学出版社，(1989)．数学模型选谈(走向数学从书)，华罗庚，王元著，王克译，湖南教育出版社；(1991)． 【6】数学建模--方法与范例，寿纪麟等编，西安交通大学出版社(1993)． 【7】数学模型，濮定国、 田蔚文主编，东南大学出版社(1994)． 【8】数学模型，朱思铭、李尚廉编，中山大学出版社，(1995) 【9】、数学模型，陈义华编著，重庆大学出版社，(1995)
11 - -