intlinprog 函數和bintprog 函數在0-1 規劃中的應用

李 淵，郭興明，魏 磊

（1.山西大同大學機電工程學院，山西大同 037003；2.山西大同大學建筑與測繪工程學院，山西大同 037003）

0 引言

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

1 人員安排問題及其數學模型

人事部門欲安排4 人到4 個不同崗位工作，每個崗位1 人。經考核，4 人在不同崗位的成績（百分制）見表1。問題：4 人的崗位工作怎么安排，使得總成績最好。

表1 成績單

2 基于Matlab 軟件進行求解

2.1 基于bintprog 函數的編程求解

2.2 基于intlinprog 函數的求解

2.3 結果對比分析

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

表2 求解結果

3 結論

本文以人員安排問題為例，建立了0-1 規劃數學模型，分別運用Matlab 軟件中的bintprog 和intlinprog 函數進行編程求解，并對兩者程序等進行了對比分析。結果表明，bintprog 函數的程序比較簡單，intlinprog 函數應用范圍更為廣泛。

項目：山西大同大學博士科研啟動項目：2016B17，柔順并聯機器人動力學研究，負責人：李淵。山西省重點學科項目（20131014）。