基于多目标规划的比赛项目排序模型

基于多目标规划的比赛项目排序模型庄浩（中国矿业大学理学院,江苏徐州221008）摘要：在各种运动比赛中，一个合理的赛程安排有着十分重要的意义，它不但可以减少比赛时间、空间复杂度，节约财力、物力，还可以提高比赛的公平性。本文主要讨论了在尽量避免运动员连续参加两个比赛的原则下，来设计赛程以提高比赛的公平性。通过对问题的多次转化找到了建立了多目标动态规划模型，解决了问题。关键词：动态规划；分层序列法；赛程排序1.引言近年来,随着全民健身计划的提出和推广,以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平.现在各级、各类、各种运动比赛比比皆是，在各种运动比赛中，为了使比赛公平、公正、合理的举行，科学地安排比赛项目是必不可少的.衡量赛程安排的优劣有很多指标,而一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。本文将在满足此要求的前提下建立简单明了,易于操作的比赛项目排序模型。2.模型的建立2.1模型的假设为了讨论问题和建模的方便,对原问题提出如下的假设条件:1、无任何参赛队员在赛程间中途弃权。2、整个赛程是持续的,且赛程时间足够长。3、假设每个运动员的恢复体力的能力相同。4、比赛项目时间不冲突，即任两场比赛的时间不相同。5、假设每场比赛的进行、每个运动员的球场发挥都不受天气的影响。6、不考虑因某些特殊因素而使得运动员不能按时参加某一运动项目的比赛。可以看出,对于一般的比赛来说,上述的假设是合理的.2.2符号的说明为了叙述的方便,将下文中常用的一些符号作一些说明:1、——第i个队员的参赛情况，当第个队员参加了第ijaij项比赛时，否则1ija=-1-=。2、jb——第j项比赛项目，1,2,jm=。3、——将两个比赛项目、ijbibjb放在一起所引起的连续参加两项比赛的运动员人次。4、——合理安排比赛项目顺序后第i个队员的参赛情况。ijc5、C——比赛项目的一个组合。12,,,mbbb6、——第i个队员的第ijdj场与第1j+场比赛的间隔场次数。2.3问题的分析及建立模型2.3.1问题的分析寻找排序问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的最优解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。但是当比赛项目很多是，这种方法是不能使用的，因为此时候选解的数量是大数阶乘，即便采用最快的计算机也只能解决规模很小的排序问题,而且也不是很方便。为了可以方便的解决此问题,我们可以用下面的方法来考虑。比赛项目的安排要从总体上考虑，第一个比赛项目不仅对其后的第二个项目有影响，而且对以后的每一个比赛项目的安排都会产生影响。对于如何确定第一个比赛项目，我们有下面的定理：定理1对某个比赛项目，如果将其放在第一位，那么对它的约束是最少的。证明：反证法在确定第j个比赛项目时，假设1j≠，那么我们必须考虑它得与第个比赛项目相匹配，即使得连续参加第(1j−)j和第(1j)−个项目的运动员人数最少。这样的话第j个比赛项目的确定将受到第个项目的约束。故第一个比赛项目的确定所受到的约束最少。(1j−)基于定理1，我们认为应尽量将有可能产生多个连续参赛人数的比赛项目排在前面。如果某个比赛项目的参赛人数很多，或者对某项比赛来说，参加它的运动员同时又参加了其他多项比赛，那么此比赛项目受到的约束就会很多，故考虑先对此比赛做出安排。在确定了第一个比赛项目以后，问题将转化为动态规划决策问题：在知道当前状态的情况下，在满足约束条件时，如何做出决策以确定下一个状态，从而得到最佳结果。2.3.2建立动态模型[1,2,3]设共有个运动员，个比赛项目，令nm111212122212,,,,(),,mmijnmnnnmaaaaaaaaaa×⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦####-2-其中表示第个队员的参赛情况，如果第i个队员参加了第ijaij场比赛，则，否则。即：1ija=0ija=1,0ijija⎧⎪=⎨⎪⎩当第个运动员参加第个运动项目时，其他情况如果第i个运动员连续参加两个项目的比赛，则很显然有：(1)1ijijaa+×=；对于其他情况则有：。(1)0ijijaa+×=将拆分成个n阶列向量，记为，其中：()ijnma×m12,,,mbbb[]11121311,,,,Tnbaaaa=[]21222322,,,,Tnbaaaa=#[]123,,,,Tmmmmnmbaaaa=则问题又转化为如何将重新组合，使得连续参加两项比赛的运动员人次最少。12,,,mbbb令C为的一个组合，由排列组合知识我们可得，这样的共有种.对确定的一组组合，令矩阵内的某一个元素为,由于的值非1及0，则要使连续参加两项比赛的运动员人次最少，即为求最小值：12,,,mbbbC!mnmC×ijcijc（1）(1)11min..0,1,2,,;1,2,,nmijijijijccstcinjm+==⎧×⎪⎨⎪≥==⎩∑∑这就是我们要求的目标函数。为了更好的叙述，有下列的定义：定义1如果将、ibjb两组放在一起所引起的连续参加两项比赛的运动员人次为，定义为的策略结果。ijbijbibb→j则问题转化为如何在状态为时，做出选择状态ibjb的决策,使得策略结果最小。可见这是一个多阶段决策过程，可以用动态规划（）来求解。所谓动态规划是把比较复杂的问题划分成若干阶段，通过逐段求解，最终求得全局最优解。由于它具有“分而治之，逐步改善”的优点，在解决一些较难的问题，尤其是离散性问题，用动态规划的方法去处理，比用线性规划或非线性规划更有效。本题就是一个较复杂的离散性问题，用动态规划处理的过程如下：ijbDynamicPrgramming1.1:step构造阶段变量首先由某个依据选定作为初始状态，我们称为第一个阶段,只要ibibb→jjb使得连续-3-参加、ibjb两项比赛运动员的人次最小；称ijbjkbb→为第二个阶段，只要jb使得连续参加jb、两项比赛运动员的人次kbjkb最小。依次关系可构造出整个过程中的所有阶段变量。1.2:step:确定状态变量某阶段的状态即为它的始点。由于有些状态的始点不止一个，故常用kx表示第阶段的某个状态，用kkX表示第k阶段的状态集合，则{}kkXx=就是第k阶段所有始点的集合。1.3:step选取决策变量所谓决策是指一个阶段的状态确定以后，从该状态变到下一个阶段的某个状态的一种选择。用来描述这种选择的变量称为决策变量。每一个阶段的决策都依赖于该阶段的状态，假设用来表示第阶段的决策变量，则kuk()kkkuux=。决策变量允许选择的范围，称为允许决策集合，记为，。显然，每个决策变量都应在允许决策集合中选择，即。()kkUx1,2,k=()()kkkkuxUx∈1.4:step形成全过程策略由各个阶段的决策，()kkux1,2,k=，组成的决策序列，成为一个全过程策略。可以表示为，即：，其中11()nPx111122(){(),(),,()}nnnPxuxuxux=()()kkkkuxUx∈。一般可供选择的策略有一定的范围，我们称之为允许策略集合。1.5:step求出最优解要想求出最优解f，只需找到策略，使得****111122(){(),(),,()}nnPxuxuxux=nminijfb=∑（2）1.6:step初始状态的确定ib在本题中，对于每一个都有一个最优的策略。而我们最终的目的是找到最佳调和解ib*f，在i很少的情况下，可以用穷举法得到。但当i变大时穷举法是很麻烦的，即使借助大型计算机也不能很快解决。在这里我们需要解决的问题是如何安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少。这是一个实际问题，现实生活中我们在安排赛程时，一般只要求在基本满足约束条件的前提下，使得算法的可操作性、简洁性尽可能的好。为此，我们考虑用下面两种既简洁方便又基本可以求出最佳调和解*f的方法来确定初始状态。ib①参加人数最多法：一般情况而言，如果一个项目的参赛人员js越多，即有maxjs，那么它和其他项目发生冲突（这里的“冲突”指使运动员连续参加两项比赛）的概率就越大。据此，我们可以将参赛队员最多的比赛项目作为动态规划的初始状态。②发生冲突最多法：对第j个比赛项目，如果第i个运动员在参加比赛项目j的同时又参加了l项其他的比-4-赛项目，则为了说明l对j的影响，我们有下面的定义j个比赛项目的冲突权重。定义2定义ijλ为第个运动员所参加的比赛项目的总合对第i这里(1)ijlλ=+，ijλ越大对于运动队员来说比赛项目ij越容易发生冲突。显然对于确定的j，如果1maxnijiλ=∑最大，则比赛项目j与其他项目发生冲突（使运动员连续参加两项比赛）的概率比较大。在实际操作时可以将这两种方法结合起来用，效果会更好！在处理动态规划问题时，一般来说，第阶段的决策变量不仅对此次的决策有影响，而且对第阶段以后的各个阶段都会产生影响。这时，我们在做第阶段的决策变量时就不仅要考虑kkukkminijfb=∑，同时考虑还要maxjs和1maxnijiλ=∑。根据上述分析，我们可将原问题转化为下面的多目标动态规划问题：1231minmaxmax..0,0;1,2,,;1,2,1ijjnijiijijfbfsfstbinjmλλ=⎧=⎪=⎪⎪⎨=⎪⎪⎪≥≥==−⎩∑∑（3）（3）式中的第一个式子表示在此次决策中要尽可能的使连续参加两次比赛的运动员的人数最少；第二个式子表示参加第j个比赛项目的人数，参加人数越多的比赛项目越要先安排；第三个式子表示由于第j个比赛项，第个运动员会连续参加两次比赛的概率，即冲突概率越大的比赛项目越要先安排。i3.模型的求解[4,5]：通常处理多目标规划问题的方法主要有约束法、评价函数法、分层序列法等，根据本问题的特点，我们选用分层序列法对上述多目标动态规划问题进行求解。分层序列法是把多目标规划问题中的多个目标按其重要程度排一个次序，通过对题目的分析，我们不难得出:1f最重要，2f次之，3f再次之。于是我们可以先算出1f的最优值*1f及最优解，再求出*b2f的最优值*2f及最优解，最后解出*s3f的最优值*3f及最优解*λ。这样我们就得到了（*）在分层序列意义下的最优值：（4）****123((),(),())TFfbfsfλ=文献[1]中证明了、、*b*s*λ是多目标问题（4）的可行解。-5-通过对附录表的处理，可以得到比赛项目报名统计图和运动员报名统计图（图1、图2）。比赛项目报名人数统计6869787106106108100246810121234567891011121314比赛项目报名人数图1比赛项目报名统计图要想彻底解决上述问题，我们得用到动态规划的理论基础：最优化原理，其内容如下运动员报名统计01234513579111315171921232527293133353739运动员报名项目数图2运动员报名统计图最优化原理[1]作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。对最优化原理作进一步的分析，我们不难得到如下的结论推论若允许策略是最优策略，则对任意的k*1nP(1)kn，它的子策略对于以为起点的*knP**1(,)kkksTsx+=*k1k+到子过程来说，必是最优策略。n求解的步骤如下：-6-用“参加人数最多法”找出初始状态结合图1我们得到在用“参加人数最多法”时，初始状态可为、、、；8b10b12b14b2.2:step用“发生冲突最多法”找出初始状态当用“