游泳運(yùn)動(dòng)員選拔問題的求解

隋 英 暢春玲 韓孺眉

(沈陽建筑大學(xué) 理學(xué)院 遼寧 沈陽：110168)

游泳運(yùn)動(dòng)員選拔問題的求解

隋 英 暢春玲 韓孺眉

(沈陽建筑大學(xué) 理學(xué)院 遼寧 沈陽：110168)

游泳運(yùn)動(dòng)員的選拔是一個(gè)值得研究的典型指派問題，將該問題轉(zhuǎn)化成一般的線性規(guī)劃問題，然后采用數(shù)學(xué)計(jì)算軟件Mathemaica進(jìn)行求解，獲得良好的效果。

指派問題；線性規(guī)劃；數(shù)學(xué)軟件

游泳運(yùn)動(dòng)員的選拔是一個(gè)值得研究的典型指派問題，即：整數(shù)規(guī)劃問題中的0-1規(guī)劃問題。該問題可以通過常用的數(shù)學(xué)軟件Mathemaica、Matlab、Lindo、Lingo等進(jìn)行求解。本文嘗試用Mathemaica進(jìn)行求解。

1 問題的提出

某班準(zhǔn)備從5名游泳隊(duì)員中選擇4人組成接力隊(duì)，參加學(xué)校的4×100米混合泳接力賽。5名隊(duì)員4種泳姿的百米平均成績(jī)?nèi)绫?所示，問應(yīng)如何選拔隊(duì)員組成接力隊(duì)？

表1 隊(duì)員4種泳姿的百米平均成績(jī)(單位：秒)

2 問題分析

問題是要從5名隊(duì)員中選出4人組成接力隊(duì)，每人一種泳姿，并且4人的泳姿各不相同，使接力隊(duì)的成績(jī)最好。容易想到的一個(gè)辦法是窮舉法，組成接力隊(duì)的方案共有5﹗=120種，逐一計(jì)算后做比較，即可找出最優(yōu)方案。顯然這樣做的計(jì)算量很大，不是解決這類問題的最好辦法，尤其是隨著問題規(guī)模的變大，窮舉法的計(jì)算量將是無法接受的。于是，我們考慮用0-1變量來表示一個(gè)隊(duì)員是否入選接力隊(duì)，從而建立該問題的0-1規(guī)劃模型。

3 模型建立及求解

記甲、乙、丙、丁、戊分別為隊(duì)員i=1,2,3,4,5；記蝶泳、仰泳、蛙泳、自由泳分別為泳姿j=1,2,3,4。記隊(duì)員i的第j種泳姿的百米平均成績(jī)?yōu)閏ij(單位：秒)。

決策變量：引入0-1變量xij，若選擇隊(duì)員i參加第j種泳姿的比賽，記xij=1，否則記xij=0。

約束條件：根據(jù)組成接力隊(duì)的要求，xij應(yīng)該滿足下面兩個(gè)約束條件：

(1)每人最多只能入選1種泳姿，即：

綜上可得該問題的整數(shù)規(guī)劃模型：

利用Mathematica 8求解模型

In[1]:=Minimize [ {66.8x11+ 75.6x12 +87x13+58.6x14+ 57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54

x11+x12+x13+x14 <= 1,

x21+x22+x23+x24<= 1,

x31+x32+x33+x34<= 1,

x41+x42+x43+x44<= 1,

x51+x52+x53+x54<= 1,

x11+x21+x31+x41+x51==1,

x12+x22+x32+x42+x52==1,

x13+x23+x33+x43+x53==1,

x14+x24+x34+x44+x54==1,

x11==1‖x11==0,x12==1‖x12==0,

x13==1‖x13==0,x14==1‖x14==0,

x21==1‖x21==0,x22==1‖x22==0,

x23==1‖x23==0,x24==1‖x24==0,

x31==1‖x31==0,x32==1‖x32==0,

x33==1‖x33==0,x34==1‖x34==0,

x41==1‖x41==0,x42==1‖x42==0,

x43==1‖x43==0,x44==1‖x44==0,

x51==1‖x51==0,x52==1‖x52==0,

x53==1‖x53==0,x54==1‖x54==0},

{x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,x41,x42,x43,x44,x51,x52,x53,x54} ]

Out[1]=No more memory available.

Mathematica kernel has shut down.

Try quitting other applications and then retry.

即：按照0-1規(guī)劃的命令來做這個(gè)問題，沒有找到答案。于是將該問題轉(zhuǎn)化成一般的線性規(guī)劃問題來求解。

該問題的決策變量和目標(biāo)函數(shù)保持不變，約束條件進(jìn)行適當(dāng)?shù)恼{(diào)整，把0-1規(guī)劃問題轉(zhuǎn)化為一般的線性規(guī)劃問題來求解

約束條件：根據(jù)組成接力隊(duì)的要求，xij應(yīng)該滿足下面三個(gè)約束條件：

(2)每種泳姿必須有1人且只能有1人參賽

(3)非負(fù)性要求：xij≥0 ，i=1,2,3,4,5，j=1,2,3,4。

綜上可得該問題的線性規(guī)劃模型：

利用Mathematica求解模型

In[1]:=Minimize [ {66.8x11+ 75.6x12 + 87x13+58.6x14+ 57.2x21+66x22+66.4x23+53x24+78x31+67.8x32+84.6x33+59.4x34+70x41+74.2x42+69.6x43+57.2x44+67.4x51+71x52+83.8x53+62.4x54

x11+x12+x13+x14 <= 1,

x21+x22+x23+x24<= 1,

x31+x32+x33+x34<= 1,

x41+x42+x43+x44<= 1,

x51+x52+x53+x54<= 1,

x11+x12+x13+x14 >= 0,

x21+x22+x23+x24>= 0,

x31+x32+x33+x34>= 0,

x41+x42+x43+x44>= 0,

x51+x52+x53+x54>= 0,

x11+x21+x31+x41+x51= =1,

x12+x22+x32+x42+x52= =1,

x13+x23+x33+x43+x53= =1,

x14+x24+x34+x44+x54= =1,

x11>= 0,x12>= 0,x13>= 0,x14>= 0,

x21>= 0,x22>= 0,x23>= 0,x24>= 0,

x31>= 0,x32>= 0,x33>= 0,x34>= 0,

x41>= 0,x42>= 0,x43>= 0,x44>= 0,

x51>= 0,x52>= 0,x53>= 0,x54>= 0},

{x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,x41,x42,x43,x44,x51,x52,x53,x54} ]

Out[1]={253.2,{x11->0.,x12->0.,x13->0.,x14->1.,x21->1.,x22->0.,x23->0.,x24->0.,x31->0.,x32->1.,x33->0.,x34->0.,x41->0.,x42->0.,x43->1.,x44->0.,x51->0.,x52->0.,x53->0.,x54->0.}}

4 結(jié)論

本文嘗試用數(shù)學(xué)計(jì)算軟件Mathemaica進(jìn)行求解游泳運(yùn)動(dòng)員選拔問題，但在求解的過程中發(fā)現(xiàn)，使用Mathemaica求解簡(jiǎn)單的0-1規(guī)劃問題尚可，但當(dāng)決策變量的個(gè)數(shù)增加后，Mathemaica求解0-1規(guī)劃問題問題就變得困難了，這是因?yàn)槎鄠€(gè)決策變量的0-1規(guī)劃問題可能會(huì)導(dǎo)致一個(gè)冗長(zhǎng)的分支定界計(jì)算。當(dāng)分支定界計(jì)算時(shí)間很長(zhǎng)仍得不到最優(yōu)解時(shí)，適當(dāng)?shù)貙?duì)輸入模型進(jìn)行一些等價(jià)變換，可能對(duì)問題的求解會(huì)有所幫助。因此，本文將游泳運(yùn)動(dòng)員的選拔問題由整數(shù)規(guī)劃的0-1規(guī)劃問題轉(zhuǎn)化成一般的線性規(guī)劃問題，然后通過Mathemaica軟件進(jìn)行求解，從而得出了問題的最佳求解方案。

[1] 姜啟源，謝金星，葉俊.數(shù)學(xué)模型(第3版)[M].北京：高等教育出版社，2003．

[2] 謝金星，薛毅.優(yōu)化模型與LINDO/LINGO軟件[M]．北京：清華大學(xué)出版社，2005．

[3] 萬中，曾金平.數(shù)學(xué)實(shí)驗(yàn)[M]．北京：科學(xué)出版社，2002．

[4] 李漢龍，繆淑賢，韓婷．Mathematica基礎(chǔ)及其在數(shù)學(xué)建模中的應(yīng)用[M]．北京：國(guó)防工業(yè)出版社，2013．

(責(zé)任編輯：李文英)

Seeking Solutions to Selection of Swimming Athletes

SUI Ying CHANG Chunling HAN Rumei

(Science School of Shenyang Jianzhu University, Shenyang 110168, Liaoning)

Selection of swimming athletes is a typical assignment problem worthy of studying. In this paper, the problem is turned into a general linear programming problem and solved by mathematical software, achieving a good effect.

assignment; linear programming; mathematical software

2014-10-24

2014-11-10

隋 英(1974～)，女，副教授.E-mail:2008suiying@163.com

O173

A

1671-3524(2015)02-0083-03