數學建模教學中順序調度問題的研究

陳允峰

[摘 ? ? ? ? ? 要] ?在參考資料《數學建模算法與應用》一書消防車調度的基礎上通過進一步完善，提出解決順序指派問題的一個通用數學模型，并通過搶險車順序調度這一具體問題，編制lingo程序，程序運算結果驗證本方法的有效性。

[關 ? ?鍵 ? 詞] ?數學建模;順序調度;lingo

[中圖分類號] ?G712 ? ? ? ? ? ? ? ? ? [文獻標志碼] ?A ? ? ? ? ? ? ? ? ? ?[文章編號] ?2096-0603（2018）26-0139-01

某防汛中心下有5輛搶險車，分屬于3個不同的搶險站。某市洪災，有三處搶險點分別需要2輛、1輛、2輛搶險車，洪災損失程度與搶險車到達的及時程度有關。記第j輛車到達第i個地點的時間為tij，這三處搶險點的損失分別為5t11+3t12，3t21，6t31+4t32，假設搶險車從3個搶險站到3個搶險點的時間如表1所示，假設3個搶險站恰好分別有2，1，2輛車，該防汛中心該如何調度搶險車輛。

問題分析：

參考文獻[1]，該問題可以看作是指派問題的一個變種，我們可以通過構造相應的損失矩陣，再添加合適的決策變量，把這個問題轉化為0-1規劃模型。我們把每一個搶險點需要的一輛車看成是1個需求，這樣從搶險點1到搶險點3共有5個需求點，這樣我們可以得到從3個搶險站到5個需求點的損失表（見表2），記從第i個搶險站到第j個需求點派車，損失為Sij（i=1，2，3，j=1，2，3，4，5）。

同樣的方法我們可以整理出從3個搶險站到5個需求點的時間表（見表3），并記從第i個搶險站到第j個需求點的時間為Tij（i=1，2，3，j=1，2，3，4，5）。

設第i個搶險站向第j個需求點派車為Xij（i=1，2，3，j=1，2，3， 4，5），Xij=1，表示第i個搶險站向第j個需求點派車，Xij=0，表示不派車。

模型建立及求解：

則此順序調配問題可以表示為如下線性規劃模型：

min=■■SijXij

s.t.■X1j=2■X2j=1■X3j=2■Xi2Ti2<■Xi1Ti1■Xi5Ti5<■Xi4Ti4■Xij=1，（j=1，2，3，4，5）Xi，j為0-1變量

編制lingo程序，并運算得全局最優解：X1，3=1，X1，5=1，X2，2=1，X3，1=1，X3，4=1，其余決策變量為零。即得搶險車的調度方案為：從搶險站1往搶險點2發一輛車，從搶險站1往搶險點3發第二輛車，從搶險站2往搶險點1發第二輛車，從搶險站3往搶險點1發第一輛車，從搶險站3往搶險點3發第一輛車，經驗證，此解為合理的。

參考文獻：

[1]謝金星，薛毅.優化建模與LINDO/LINGO軟件[M].北京：清華大學出版社，2006.

[2]司守奎，孫璽菁.LIINGO軟件及應用[M].北京：國防工業出版社，2017.