intlinprog 函數(shù)和bintprog 函數(shù)在0-1 規(guī)劃中的應(yīng)用

李 淵，郭興明，魏 磊

（1.山西大同大學(xué)機(jī)電工程學(xué)院，山西大同 037003；2.山西大同大學(xué)建筑與測(cè)繪工程學(xué)院，山西大同 037003）

0 引言

0-1 規(guī)劃是決策變量?jī)H取值0 或1 的一類特殊整數(shù)規(guī)劃。0-1 變量可以數(shù)量化地描述諸如有與無(wú)、取與棄、開(kāi)與關(guān)等現(xiàn)象所反映的離散變量間的邏輯關(guān)系、順序關(guān)系以及相互排斥的約束條件。因此，0-1 規(guī)劃非常適合描述及解決諸如線路設(shè)計(jì)、生產(chǎn)計(jì)劃安排、人員安排、工廠選址、旅行購(gòu)物等人們所關(guān)心的很多問(wèn)題。彭慧杰基于0-1 規(guī)劃數(shù)學(xué)模型，分別采用第Ⅰ類和第Ⅱ類裝配線平衡方法，基于LINGO 軟件求解，給出了最優(yōu)作業(yè)元素分配方案，從而提高了裝配線平衡率[1]。蘇志雄借助工序網(wǎng)絡(luò)，運(yùn)用簡(jiǎn)單的時(shí)間參數(shù)，量化了平行工序順序化對(duì)項(xiàng)目工期的影響，建立了純0-1 規(guī)劃模型，從實(shí)驗(yàn)上驗(yàn)證了該模型的求解效率[2]。彭瑤瑤基于零件序列和原材料序列，計(jì)算了原材料的利用率，以最大利用率為目標(biāo)建立了0-1 規(guī)劃模型，并基于遺傳算法進(jìn)行求解[3]。王邦彥針對(duì)海上風(fēng)電場(chǎng)集電系統(tǒng)的開(kāi)關(guān)如何配置才能最優(yōu)的問(wèn)題，建立了0-1 規(guī)劃模型，利用求解器對(duì)算例進(jìn)行了分析，并對(duì)最終設(shè)計(jì)方案基于解析法評(píng)估了其可靠性[4]。董驍翀對(duì)可再生能源場(chǎng)景問(wèn)題如何精確模擬，提出一種基于Wasserstein 概率距離的場(chǎng)景約簡(jiǎn)0-1 規(guī)劃模型。和傳統(tǒng)場(chǎng)景約簡(jiǎn)方法對(duì)比，本模型有著更好的適用性與精準(zhǔn)性[5]。陳傳軍針對(duì)贊比西河卡里巴大壩存在的問(wèn)題，以高安全系數(shù)、低成本為目標(biāo)，建立多目標(biāo)0-1 整數(shù)規(guī)劃模型，基于lingo 軟件求解出在該流域建立水壩的具體數(shù)量及其位置[6]。秦書(shū)婷針對(duì)配送路線規(guī)劃問(wèn)題，結(jié)合配送點(diǎn)之間是否可直接通行等實(shí)際因素，以配送路程為性能指標(biāo)建立了0-1 規(guī)劃模型，利用改進(jìn)型果蠅優(yōu)化算法進(jìn)行了求解[7]。葛召浩針對(duì)無(wú)人機(jī)組網(wǎng)雷達(dá)和編隊(duì)之間的欺騙干擾的問(wèn)題，基于分層規(guī)劃法建立了無(wú)人機(jī)編隊(duì)的協(xié)同規(guī)劃、航跡搜尋、安全約束模型，利用0-1 規(guī)劃的方法對(duì)勻速直線等約束下無(wú)人機(jī)編制定了協(xié)同策略[8]。方舒對(duì)某部隊(duì)執(zhí)行作戰(zhàn)任務(wù)的24 臺(tái)三類車載發(fā)射裝置，根據(jù)其任務(wù)區(qū)域和機(jī)動(dòng)路線，優(yōu)化目標(biāo)設(shè)定為兩波次導(dǎo)彈發(fā)射時(shí)整體暴露時(shí)間最短，基于Dijkstra算法進(jìn)行了合理簡(jiǎn)化，得出了最優(yōu)路徑。并考慮道路節(jié)點(diǎn)沖突等因素，建立0-1 規(guī)劃模型，求出了兩波次發(fā)射時(shí)整體最短暴露時(shí)間[9]。李建平對(duì)一類特殊的傳感器資源調(diào)度問(wèn)題進(jìn)行了研究，主要對(duì)傳感器資源、跟蹤目標(biāo)的探測(cè)次數(shù)和時(shí)間間隔等約束條件進(jìn)行了分析，目標(biāo)函數(shù)設(shè)定為跟蹤目標(biāo)的重要程度之和，建立了一個(gè)0-1 規(guī)劃線性模型[10]?；诟钇矫娣ǖ玫搅俗顑?yōu)調(diào)度策略。本文以人員安排問(wèn)題為例，建立了0-1 規(guī)劃數(shù)學(xué)模型，并基于Matlab 軟件中的bintprog 和intlinprog 函數(shù)編程求解。

1 人員安排問(wèn)題及其數(shù)學(xué)模型

人事部門(mén)欲安排4 人到4 個(gè)不同崗位工作，每個(gè)崗位1 人。經(jīng)考核，4 人在不同崗位的成績(jī)（百分制）見(jiàn)表1。問(wèn)題：4 人的崗位工作怎么安排，使得總成績(jī)最好。

表1 成績(jī)單

2 基于Matlab 軟件進(jìn)行求解

2.1 基于bintprog 函數(shù)的編程求解

2.2 基于intlinprog 函數(shù)的求解

2.3 結(jié)果對(duì)比分析

從上述bintprog 函數(shù)和intlinprog 函數(shù)的求解結(jié)果看，兩者結(jié)果相同，整理見(jiàn)表2，即安排甲從事C 工作，乙從事A 工作，丙從事D 工作，丁從事C 工作。從兩者程序來(lái)看，intlinprog 函數(shù)的程序比bintprog 函數(shù)的程序更復(fù)雜一些，不止要限定變量是整數(shù)型，還要給出其上下界。而bintprog 函數(shù)的程序比較簡(jiǎn)單，甚至可以說(shuō)bintprog 函數(shù)是針對(duì)0-1 規(guī)劃而設(shè)立的函數(shù)。而intlinprog 函數(shù)不止可以求解0-1 規(guī)劃問(wèn)題，還可以求解混合整數(shù)型的線性規(guī)劃問(wèn)題。但bintprog 函數(shù)從2014b 版本后被刪除了，官方建議用intlinprog 代替。

表2 求解結(jié)果

3 結(jié)論

本文以人員安排問(wèn)題為例，建立了0-1 規(guī)劃數(shù)學(xué)模型，分別運(yùn)用Matlab 軟件中的bintprog 和intlinprog 函數(shù)進(jìn)行編程求解，并對(duì)兩者程序等進(jìn)行了對(duì)比分析。結(jié)果表明，bintprog 函數(shù)的程序比較簡(jiǎn)單，intlinprog 函數(shù)應(yīng)用范圍更為廣泛。

項(xiàng)目：山西大同大學(xué)博士科研啟動(dòng)項(xiàng)目：2016B17，柔順并聯(lián)機(jī)器人動(dòng)力學(xué)研究，負(fù)責(zé)人：李淵。山西省重點(diǎn)學(xué)科項(xiàng)目（20131014）。