基于單純形法的ＬＩＮＧＯ求解一般指派問題的探討

［摘 要］本文首先介紹一般指派問題的數學模型和求解方法，然后詳細給出利用單純形法求解一般指派問題的步驟，并設計了基于單純形法的指派問題算法流程，最后通過LINGO對指派問題的應用實例進行了求解。運行結果表明：LINGO軟件程序設計靈活，能快速準確求解指派問題。

［關鍵詞］ 指派問題；單純形法；LINGO

［中圖分類號］F270.7；F224.0［文獻標識碼］A［文章編號］1673-0194（2008）06-0086-02

1 引 言

在日常生活和企業生產經營管理工作中，經常面臨著給人分派工作、給機床指派加工任務等一般指派問題。指派問題的主要研究方法是定量化、系統化和模型化方法，特別是運用各種數學模型和技術來解決這類問題。在實際中遇到的問題一般規模比較大，即使建立了模型，找到了求解的方法，對于龐大的計算量也是望而卻步。“工欲善其事，必先利其器”，有一個方便的求解最優化問題的工具極為重要。LINGO是一個利用線性規劃和非線性規劃來簡潔地闡述、解決和分析復雜問題的簡便工具，其特點是程序執行速度快，易于輸入、修改、求解和分析數學規劃問題，對于線性規劃（LP）、二次規劃（QP）、非線性規劃（NLP）問題，LINGO工具可以給出解決相應問題的方案。本文力圖利用LINGO工具，探討求解一般指派問題。

2 一般指派問題的數學模型

一般指派問題（Assignment Problem）是指有m項任務，需要有n個人來承擔，由于各人的專長不同，各人完成的任務不同，導致其效率也各不相同。因此，需要科學地指派任務，使完成m項任務所消耗的總資源最少（或總體效益最優）。根據m、n之間的數量關系，指派問題可分為3種情況進行論述。

第一，當m= n時，即為每個人都被指派一項任務；

第二，當m >n時，即任務的數量大于人的數量。這時可虛設（m-n）個人構成一個m×m的效率矩陣，并且這（m-n）個人在執行m 項任務時的成本最高；

第三，當m

通過虛設任務或人，指派問題要求最小化（時間、成本、所消耗的資源）時的數學模型為［1］：

求解一般指派問題的算法很多，包括匈牙利解法、窮舉法、割平面法、單純形法等。其中單純形法方法靈活方便且便于計算機求解，在LINGO中容易實現。

3 單純形法原理及一般步驟

單純形法是美國數學家George Dantzig于1947年首先提出的，其理論根據是：線性規劃問題的可行域是n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到，該頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別；若仍不是，則再轉換，按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。

單純形法的一般解題步驟可歸納如下［1］：

Step 1找出初始可行基，確定初始基可行解，建立初始單純形表。

4 LINGO程序實現

例4個工人被分派做4 項工作，規定每人只能做一項工作，每項工作只能一個人做，現設每個工人做每項工作所消耗的時間如表1，求總耗時最少的分派方案。

表1工作效率表

LINGO程序求解過程如下：

Step 1構造兩個集合。

sets：

！4個工人，4個工作的分配問題;

Person /1..4/;

Job/1..4/;

Assign（Person，Job） ：c，x;

endsets

Step 2構造目標函數。

min = @sum（Assign：c * x）;

Step 3構造約束條件。

@for（Person（i）：@sum（Job（j）：x（i，j）） = 1）;

@for（Job（j）：@sum（Person（i）：x（i，j）） = 1）;

Step 4求解結果。

LINGO采用單純形方法，經過7次迭代，得出全局最優解70，指派矩陣為： ，指派安排如下：工作1→工人1，工作2→工人4，工作3→工人3，工作4→工人2，總耗時為70。

5 結 語

通過本實例可以看出，LINGO是一個利用線性規劃和非線性規劃來簡潔地闡述、解決和分析復雜問題的簡便工具。其特點是程序執行速度快，易于輸入、修改、求解和分析數學規劃問題。另外，用單純形法求解線性規劃問題所需的迭代次數主要取決于約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解。

主要參考文獻

［1］ 甘應愛，田豐等. 運籌學［M］. 北京：清華大學出版社，1990.

［2］ 黃雍檢. Matlab在經濟管理中的應用［J］. 湖南大學學報：自然科學版，2005，32（2）：121-124.

［3］ 白國仲，陳雯，蘇芳荔等. 基于特殊需要的指派問題［J］. 華中師范大學學報：自然科學版，2006，40（3）：305-309.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”