基于Matlab的混合泳隊接力賽選拔方案優(yōu)化探究

李麗容

（武漢學院信息工程學院，湖北 武漢 430212）

0 引言

文獻[1]中例題：混合泳隊接力賽選拔方案采用Lingo軟件求解，下面筆者采用Matlab優(yōu)化工具箱中的intlinprog函數(shù)求解，并將其同Lingo軟件求解結果進行比較，分析這兩種目前學生最常用的軟件求解方案各自的特點及實用性，便于學生在求解過程中進行合適的選擇。

題目：某泳隊要從5個人中選4人參加4100米混合泳接力賽，5名候選人百米成績見表1：

表1 5名候選人的百米成績

請根據(jù)以上表格給出的數(shù)據(jù)，建立數(shù)學模型，解決下面問題：

（1）怎樣選拔組成4100米混合泳接力隊？

（2）甲的仰泳成績進步到1'05''4，丁的蛙泳成績退步到1'15''2，戊的自由泳成績進步到54''5，組成接力隊的方案需要調整嗎？應該怎樣調整？

1 問題分析及模型的建立

1.1 問題分析

該問題是比較常見的0-1型整數(shù)規(guī)劃問題，在日常生活安排和企業(yè)生產管理工作中，常常要給人分派工作或給機器指派任務等，我們一般把這類問題也叫指派問題。它是最優(yōu)化問題的一種，它的問題模型是給個人（人泛指可以執(zhí)行任務的一切物體）指派完成項任務，并通過每個人完成每件任務的工作效率來研究如何分配任務資源，使完成任務所消耗的總資源最少或總利潤最大。因決策變量只有0和1兩種取值，在問題討論時，通常把某個人是否執(zhí)行某項任務取值為1和0，從而建立一般指派問題的0-1規(guī)劃模型。

1.2 模型的建立

2 用Matlab優(yōu)化工具箱中函數(shù)求解整數(shù)規(guī)劃模型

Matlab作為一款非常強大的科學計算軟件，在能夠自己編寫程序的同時，也可以利用其工具箱中已有的函數(shù)進行求解，比如Matlab優(yōu)化工具箱中提供了各種優(yōu)化問題的求解函數(shù)，線性規(guī)劃linprog函數(shù)，二次規(guī)劃quadprog函數(shù)等等。

但對于整數(shù)規(guī)劃,并不能簡單地把已得的非整數(shù)解舍入化整就可以了，因為化整后的數(shù)不一定是可行解和最優(yōu)解，應該用特殊的方法來求解整數(shù)規(guī)劃，因此就有很多學者探尋出各種不同的方法，以前Matlab是不能直接求解這類規(guī)劃的，bintprog函數(shù)只可以用來求0-1整數(shù)規(guī)劃，求解過程比較麻煩，而且bintprog在2014b中就取消了，官方建議用intlinprog代替，intlinprog是2014a引入的函數(shù)，是一個比較新的、專用于求解各類整數(shù)線性規(guī)劃包括0-1整數(shù)規(guī)劃，也可用于求解混合整數(shù)線性規(guī)劃問題。其標準模型為：

綠色建筑工程造價成本的預估是在項目建設前期進行招投標環(huán)節(jié)進行的，主要是預測在項目建成所需要花費的費用，這是建筑項目能夠保質保量順利建成的重要參考標準。綠色建筑工程的造價成本需要考慮一定的精確性，與此同時，還需要兼顧成本造價的速度。對于招投標環(huán)節(jié)來說，造價成本的預估速度和精確度直接影響了投標單位能否順利中標。工程造價估算成本的重要意義體現(xiàn)在以下幾個方面：

該函數(shù)的使用僅僅是在linprog函數(shù)的基礎上多加了一個參數(shù)──intcon，用來約束整數(shù)變量的位置，和線性規(guī)劃函數(shù)linprog函數(shù)的使用很相似。例如：

改寫模型成標準形式如下：

于是，調用Matlab優(yōu)化工具箱中intlinprog函數(shù)，其代碼可寫為：

Matlab優(yōu)化工具箱中的優(yōu)化函數(shù)都要求目標函數(shù)值最小，如果優(yōu)化問題要求目標函數(shù)值最大，可使該目標函數(shù)的負值最小化來達到目的；缺省的條件用[]來替代。

下面調用Matlab優(yōu)化工具箱中intlinprog函數(shù)求解文獻[1]中混合泳接力選拔問題：

為了計算方便，先將所有隊員各種泳姿的百米成績進行換算，以秒為單位，有下面表2：

表2 cij(秒)隊員i第j種泳姿的百米成績

為了將模型改寫成標準形式，將20個0-1決策變量按表2中從上至下，從左至右順序改成于是用intlinprog函數(shù)求解混合泳接力選拔的，須先將模型改寫成標準形式：

由于維數(shù)比較大，這里采用kron函數(shù)將矩陣A寫成：A=kron(eye(5),ones(1,4))，b是由5個1構成的列向量。

于是，混合泳接力選拔模型的代碼可寫為：

從結果可以看到x4,x5,x10,x15=1，即被選。

表3 5名候選人被選中的4人及相應泳姿

3 模型結果分析及比較

比較Matlab優(yōu)化工具箱中intlinprog函數(shù)相較Matlab2014a版之前的bintprog函數(shù)只能求解0-1整數(shù)規(guī)劃類問題，它實用性更廣，它可以求解一般整數(shù)規(guī)劃問題，還可以解決0-1整數(shù)規(guī)劃問題，只要在求解整數(shù)規(guī)劃的基礎上加上一個對變量最大值約束為1就行了；還可以求解混合整數(shù)規(guī)劃類問題，只需用參數(shù)intcon說明整數(shù)約束變量的位置即可。另外，該函數(shù)有非常固定的標準模型，學生只需要將一般模型轉化成標準模型，然后編寫成代碼即可求解，且結果還比較可靠，計算的精度也很高，避免了應用其他語言程序過于復雜、調試困難等這樣的缺點,提高了計算效果，學起來也比較容易，操作也很方便，比較適合初學的同學。

4 結語

針對混合泳隊接力賽選拔方案這一類0-1整數(shù)規(guī)劃問題，也叫做指派問題，就是很多項任務指派給一些候選人來完成，每人的專長不同，完成每項任務取得的效益或需要的資源也不同，怎樣分派任務使獲得的總效益最大，或付出的總資源最少；或者很多種策略可以供選擇，各種不同策略得到的收益或付出的成本不同，每個策略之間有相互制約關系，怎樣在滿足一定條件下作出抉擇，使得收益最大或成本最小。這些都可以建立相同的數(shù)學模型，根據(jù)具體要求對約束條件作簡單變化，即得相應模型，由此都能采用Matlab中intlinprog函數(shù)來求解。筆者在講解這一類型時，引導學生進行歸納總結，反復練習，對該函數(shù)的固定的模型熟練轉化為標準模型，然后編寫成代碼進行求解。通過同類型題目練習，結果表明：intlinprog函數(shù)求解這一類問題簡單易學，易于理解掌握，優(yōu)于其他函數(shù)。