搭配问的题目地数学模型初探

《搭配问的题目地数学模型初探》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用标准文案搭配问题的数学模型初探叶旭刚(中科院科技政策与管理科学研究所，北京100080)摘要：给出几种最基本的飞行员搭配问题的数学模壅。基于该模壅提出问题转换思路，即将所讨论问题转化为已知的已解决问题或易解决问题。关薯词：搭配；二部图；匹配；单元；广义匹配1、引言飞行员搭配问题是飞行员派遣中的一类特殊问题，它主要针对的是如何在保证飞行技术安全标准得到满足的情况下．最大化航班的生产。具体地说，如何将一定的飞行员按照一定的飞行任务要求分组，使每组的成员之问具有可搭配性，成员总体的技术水平满足飞行任务的技术标准，同时使可执行任务的分组数最多，从

2、而最大限度地满足航班生产。可见。飞行员搭配问题是一类特殊的优化问题，本文将从最简单情况人手，提炼数学模型，并从多个角度对模型及其进行分析，探讨及论证。飞行员搭配问题的良好解决，对于合理使用飞行员资源，保证安全，提高效益具有重要意义．当今的发达国家如美国、德国、加拿大、日本、荷兰等国早已将其纳入了飞行员管理的综合框架。值得一提的是飞行员搭配问题就其数学本质来说可以出现在各个领域，所以它的意义并不局限于航空管理。任何存在人员组合或某些对象组合的地方都会出现类似的问题。2飞行员搭配问题的数学描述实际的飞行员搭配问题主要是按照技术等级的搭配来考虑的。

3、比如说现在有一批飞行员，包括正驾驶(机长)，第一副驾驶．第二副驾驶三个技术等级若干名。与此同时考虑一个航班任务，它需要配备一名正驾驶，两名副驾驶。考虑到执行这个航班任务的技术力量不能太弱，故两名副驾驶只可能是两个第一副驾驶．或者一个第一副驾驶，一个第二副驾驶。若要执行这个任务，必须从所给飞行员中挑出一名正驾驶。两名副驾驶。他们能否配组还要考虑他们之间的可搭配性．比如说不能出现人际障碍．或者性格内向的飞行员碰到一起。单个任务是微观上的考虑，在有多个任务时，要从宏观上考虑，要做到统筹兼顾．要做到优化组合。一句话，要从数学规划的角度上来考虑如何产生

4、尽可能多的，基于一定飞行任务需要的，符合一定技术标准又具有可搭配性的飞行组。搭配问题的最简情形是所谓的“二人组问题”。也即．从飞行员的角度来讲，飞行员只有正驾驶和副驾驶两类。从航班任务的角度来讲．每个航班需且仅需配备一名正驾驶和一名副驾驶。可见“二人组问题”具有问题属性的唯一性特点，而且它是搭配问题的最简情形，上文提到的情形属于一类特殊的“三人组问题”，也属于比较简单的情形，本文的内容将围绕这两类最基本的f可题展开。先来看“二人组问题”的进一步描述。假设有精彩文档实用标准文案m个正驾驶、一个副驾驶，用平面上含有m个点的点集S表示这m个驾驶，用

5、含有个点的点集T表示这个副驾驶，如果某一正驾驶和某一副驾驶具有可搭配性，就在两个相应的点问连上一条弧，将所有可能存在的弧记作集合A。于是，一个无权，无向图G=(s．T．A)就产生了。需要注意的是：这个图中只存在连接s中点和T中点的派，即机长与机长不搭配，副驾驶与副驾驶不搭配。于是图G是一个简单的无权、无向．二部图。相应的优化问题为：定义A的子集M为G的一个匹配，如果M中任两条弧无公共端点，求G的弧数最大的匹配(即最大匹配)。再来看先前提到的“三人组问题”。假设有m个正加强，个副驾驶，令rt=rtl+2，其中1为第一副驾驶的个数．rt2为第二副

6、驾驶的个数。用平面上含有m个点的点集s表示这m个正驾驶，甩含有个点的点集Tl表示这rt1个第一副驾驶，甩含有n2个点的点集Tz表示这rtz个第二副驾驶。如果某一正驾驶可以和某一第一副驾驶搭配，就在两个相应的点间连上一条弧，并赋权1；如果某一正驾驶可和某一第--N驾驶搭配，就在两个相应的点间连上一条弧，并赋权0：如果某一第一副驾驶可以和某一第二副驾驶搭配，就在两个相应的点间连上一条弧，并赋权0；将所有可能存在的弧记作集合A。于是，一个赋权，无向图G=(s，T=丁1UT2，A)就产生了。图G已经是非二部图。构造出图后．我们来进一步阐述“三人组问题

7、”：定义子图I为单元，如果这个子图I是含S中一个点，T中的两个点的完全三角形，且总权和>／1。设B为G的所有单元的集合。定义B的子集M为G的广义匹配，如果M中无两个单元有公共端点。求G的单元数最大的广义匹配。现在，我们已将两种最简单的搭配情形描述清楚了，本文下面将具体对之展开讨论，并对可能的推广做出适度探讨。3对模型的研究3．1二人组问题容易知道．我们这里的“二人组问题”是一个经典的匹配问题，也即二部图的基数匹配问题。文献…指出，二部图的基数匹配问题可以转化为求一种增广路(AugmentPath)的问题，转化为一种特殊的最大流(Maximum

8、flow)问题，转化为一种特殊的指派(WeighedAssignment)问题。实际上这些方法的共同本质特征为：寻求原始问题的数学转化，使其转化为已知可求解或已知易