李麗容

（武漢學(xué)院信息工程學(xué)院，湖北 武漢 430212）

0 引言

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

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

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

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

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

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

1 問題分析及模型的建立

1.1 問題分析

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

1.2 模型的建立

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

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

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

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

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

改寫模型成標(biāo)準(zhǔn)形式如下：

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

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

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

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

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

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

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

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

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

表3 5名候選人被選中的4人及相應(yīng)泳姿

3 模型結(jié)果分析及比較

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

4 結(jié)語

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