曹迎槐

摘要：該文以混合泳接力項(xiàng)目這種特殊的類指派問題為例，一改傳統(tǒng)的0-1規(guī)劃解法，不僅提出了基于GA和偶圖的求解思路，更提出了一種基于各泳姿成績(jī)表差值的表上求解算法，并對(duì)各算法做了匯總分析。

關(guān)鍵詞：混合泳接力；指派；績(jī)差求解；GA；偶圖

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）17-0220-02

1背景

生活中的指派問題很常見，但運(yùn)動(dòng)會(huì)上的類指派接力項(xiàng)目卻有些特殊。接力項(xiàng)目既可出現(xiàn)在田徑場(chǎng)上，也可出現(xiàn)在游泳池里，既可設(shè)男子項(xiàng)目，亦可設(shè)女子項(xiàng)目，甚至還有男女混合接力，觀賞性非常強(qiáng)。田徑場(chǎng)上的接力比賽之接棒技術(shù)很有講究，但游泳池里的混合接力雖省去了接棒壓力，但增加了泳姿要求，需考慮的因素反而更多。

例如：4×100m混合泳接力項(xiàng)目全程400米，規(guī)定每個(gè)隊(duì)由4人組成，必須按仰泳、蛙泳、蝶泳、自由泳的順序進(jìn)行，每人只能用一種泳姿游完100m，每種泳姿的技術(shù)要求依據(jù)本泳姿之相關(guān)規(guī)則。不難理解，當(dāng)備選人數(shù)較多時(shí)，如何確定組隊(duì)人選就頗費(fèi)腦筋。較傳統(tǒng)意義上的指派問題而言，此類問題存在淘汰機(jī)制，不可隨意指派，且同時(shí)存在著人員選擇與泳姿分配等縱、橫雙向?qū)Ρ确治?，相?duì)復(fù)雜，其特殊性一目了然。為便于說明問題，設(shè)現(xiàn)有8名備選隊(duì)員，其平時(shí)成績(jī)?nèi)绫?，試分析如何組隊(duì)，可使全隊(duì)的總成績(jī)最好。

此類問題的常見解法多用0-1規(guī)劃，屬LP范疇。其實(shí)，還有多種求解思路。

2基于GA的求解分析

作為指派問題，因其非線性特征十分明顯，且不連續(xù)，在數(shù)據(jù)規(guī)模較大時(shí)解空間相對(duì)可觀，所以基于GA求解也是個(gè)不錯(cuò)的選擇。仍以上述想定案例為基礎(chǔ)，因備選人數(shù)有8人，故可用3位二進(jìn)制0-1編碼來精確描述每個(gè)選手，如表2所示。

于是，GA的個(gè)體即可用人選的4位選手之0-1編碼（長(zhǎng)為固定的12位）來表示。例如：個(gè)體‘101 000 100 010，即表示‘己、甲、戊、丙四位選手，按照仰泳、蛙泳、蝶泳、自由泳的規(guī)定順序組隊(duì)參賽。

至于GA之操作算子設(shè)計(jì)，倒也沒有太多的特殊性，無非是交叉、突變，甚至選擇等。但在GA的求解過程中，每迭代生成一個(gè)新個(gè)體，都必須檢測(cè)其規(guī)范性，即必須保證四位選手不重，以規(guī)避一人游多個(gè)泳姿的情形。而適應(yīng)度函數(shù)十分簡(jiǎn)單，只需計(jì)算四名選手的總成績(jī)并求最小即可。在本案例中，種群規(guī)?？稍O(shè)置為80，大約相當(dāng)于解空間的二十分之一左右。而交叉、遺傳和突變等概率，則按常規(guī)處之就好，無須做額外設(shè)計(jì)。

經(jīng)MATLAB軟件實(shí)際運(yùn)行可知，用GA求解確無把握得到最優(yōu)解，所以，用GA求解本案例之指派問題，旨在對(duì)比分析幾種不同求解方法之異同和特點(diǎn)，從而強(qiáng)化學(xué)生的運(yùn)籌優(yōu)化意識(shí)和對(duì)現(xiàn)實(shí)問題的分析思路或角度。

3基于成績(jī)差的表上求解算法嘲

首先，先將表1中的成績(jī)統(tǒng)一為以秒為單位，稱‘歸秒處理。結(jié)果如表3。

接著，再求成績(jī)差，稱‘績(jī)差。即找到各泳姿的最優(yōu)成績(jī)，然后求出該泳姿的其他各選手之成績(jī)與該最優(yōu)成績(jī)之差，結(jié)果當(dāng)然均非負(fù)。其中，最優(yōu)成績(jī)不變。如表4。

雖然最小績(jī)差是0.3，但因選手戊已確定自由泳，且選手戊沒有其他任務(wù)，所以可不考慮該績(jī)差。次小績(jī)差是1.5，有兩個(gè)點(diǎn)，即‘丁的蛙泳、‘辛的蝶泳。不妨先考慮點(diǎn)‘丁的蛙泳，即調(diào)整蛙泳的人選，用選手丁取代選手乙，游蛙泳。如表5。

再考慮另外一個(gè)次小績(jī)差1.5的對(duì)應(yīng)點(diǎn)‘辛的蝶泳的情形，可調(diào)整蝶泳的人選，用選手辛取代選手乙，游蝶泳。如表6。

此刻，泳隊(duì)人選已確定完成。即：乙游仰泳、丁游蛙泳、戊游自由泳、辛游蝶泳，總成績(jī)251.7秒。

4基于LP之0-1規(guī)劃求解分析

5基于偶圖之交替鏈求解分析

此類指派問題實(shí)質(zhì)上可直接描述為一個(gè)二部圖，即偶圖K_2.4，如圖2所示。對(duì)應(yīng)于前面幾種解法得出的最優(yōu)解便是圖中粗線組成的邊集。該邊集顯然是交替鏈：‘自由泳—戊，戊、蛙泳，蛙泳—丁，丁—蝶泳，蝶泳—辛，辛—仰泳，仰泳—乙中的一部分。換言之，在偶圖K_2.4中求解，即找出圖中所有這些長(zhǎng)度為7的交替鏈，該鏈從泳姿點(diǎn)集出發(fā)，到選手點(diǎn)集結(jié)束，點(diǎn)不重，邊不重，從中找出交替鏈總權(quán)值最小的那條，取相間的4條邊即為最優(yōu)解。容易理解，這種方法的運(yùn)行效率不會(huì)很高，其復(fù)雜度與窮舉法幾乎無異。

6諸算法之對(duì)比分析

匯總上述幾種求解思路得表7。不難看出，不論是從求解工具、可操作性、分析思路，還是求解前的數(shù)據(jù)準(zhǔn)備，甚至復(fù)雜度等諸多方面來看，基于成績(jī)差的表上求解算法都處于十分突出的位置。

鑒于水平所限，不妥或錯(cuò)誤難免，敬請(qǐng)大家批評(píng)指正！