特殊指派問題之求解算法對比分析

曹迎槐

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）17-0220-02

1背景

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

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

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

2基于GA的求解分析

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

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

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

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

3基于成績差的表上求解算法嘲

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

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

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

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

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

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

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

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

6諸算法之對比分析

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

鑒于水平所限，不妥或錯誤難免，敬請大家批評指正！