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

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

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

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

1 引 言

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

2 一般指派問題的數(shù)學模型

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

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

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

第三，當m

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

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

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

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

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

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

4 LINGO程序實現(xiàn)

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

表1工作效率表

LINGO程序求解過程如下：

Step 1構造兩個集合。

sets：

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

Person /1..4/;

Job/1..4/;

Assign（Person，Job） ：c，x;

endsets

Step 2構造目標函數(shù)。

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次迭代，得出全局最優(yōu)解70，指派矩陣為： ，指派安排如下：工作1→工人1，工作2→工人4，工作3→工人3，工作4→工人2，總耗時為70。

5 結 語

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

主要參考文獻

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

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

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

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