解決不同類型指派問題的EXCEL模型

劉靜, 劉昌海

(1. 九江學院圖書館, 江西 九江 332005; 2. 九江學院商學院, 江西 九江 332005)

解決不同類型指派問題的EXCEL模型

劉靜1, 劉昌海2

(1. 九江學院圖書館, 江西 九江 332005; 2. 九江學院商學院, 江西 九江 332005)

指派問題, 運籌學分支整數規劃的一種應用, 主要用于解決資源配置方面的問題. 通過EXCEL建立了不同類型指派問題的模型, 旨在得到最優化的方案, 并可將該模型應用于組織的管理活動, 提高經濟效益.

指派問題; EXCEL; 整數規劃; 標準指派; 模糊指派; 廣義指派

引言

組織的管理者經常要制定一些有關于資源配置的決策, 以便更好地實現組織目標. 許多情況下, 不同的資源需要在同一時間內、不同的經營活動、經營部門或個人之間進行分配, 然而資源是有限的. 為了使有限的資源能夠最大限度地發揮作用, 需要將資源與需求者進行優化配置, 這就要應用到線性規劃中的整數規劃.

1 指派問題簡介

指派問題是運籌學數學規劃中整數規劃的一種應用.

運籌學是應用分析、試驗、量化的方法, 對經濟管理系統中人力、物力、財力等資源進行統籌安排, 為決策者提供有依據的最優方案, 以實現最有效的管理[1].

整數規劃是從1958年由R.E.戈莫里提出割平面法之后形成獨立分支的[2], 整數規劃是指部分或全部變量限定取整數值的一種線性規劃[3]. 整數規劃問題在經濟與管理中的應用比較廣泛, 如可應用在指派、產品設計、市場份額、投資場所的選擇和固定成本分布系統設計等方面.

指派問題 (Assignment Problem), 也稱分配或配置問題, 是資源合理配置或最優匹配問題[4]. 如把M個任務分配個N個人, 由于每個人的能力與特點不同, 完成每項任務的所產生的效益或需要的時間也不相同, 指派問題所要解決的就是在人與任務之間如何指派, 才能使總體效益最大或總用時最少[5]. 指派問題屬于整數規劃中的純整數規劃,

2 指派問題的類型

根據人數與任務數的關系, 指派問題可以分為二類:

1)標準型（平衡型）指派問題. 即人數M與任務數N相等, 每個人只能分配一項任務[6].

2)非標準型指派（又稱廣義指派、模糊型指派、競爭型指派、非平衡性指派）問題, 即人數M與任務數N不等, 這又可以分為以下二種情況:

①M>N, 即任務數M多于人數N, 這時, 需要一人兼多項任務才能完成全部任務的分配;

《綱要》中指出：幼兒園教育應為幼兒提供自由活動的機會，支持幼兒自主地選擇計劃活動，為每個幼兒提供表現自己長處和獲得成功的機會，增強其自信心。經常性的為幼兒提供作品展示平臺，源源不斷的激發幼兒創作興趣。

②M

3 利用EXCLE進行指派問題的建模

EXCEL作為一種辦公軟件, 具有強大的計算功能, 完全可以EXCEL建模來實現不同類型的指派問題.

3.1 標準型（平衡型）指派問題（M＝N）

如某雜志社同時有3項任務需要分配給3位主編, 且每人必須分配一項任務. 由于這3位主編的背景及能力不同, 因此完成任務所需的時間也不相同, 如表1所示, 請問如何進行任務分配使完成全部任務所用時間最少？

表1 標準型（平衡型）指派問題Form 1 The standard type (balance) assignment problem

用EXCEL建模, 步驟如下:

3.1.1 設計基本矩陣

圖1基本矩陣Figure 1 Basic matrix

3.1.2 設計變量矩陣

圖2 基本矩陣與變量矩陣的設置Figure 2 Basic matrix and matrix of variables set

1)設置C11: E13九個單元格中數字格式為“0”（單元格格式/數字/自定義/0）;

2)設置C14單元格值為C11、C12與C13三個單元格之和, 即在C14單元格輸入“=SUM（C11: C13）”（輸入時不包括引號, 下同）. 同理設置D14與E14單元格分別為D11: D13、E11: E13之和, 可分別單獨設置, 亦可使用格式拖動方式, 即選中C14單元格, 鼠標指向左下角, 會出現個十字形的圖標, 然后向右拖動二格;

3)設置F11單元格值為C11、D11與E11三個單元格之和, 同理設置F12與F13單元格分別為C12: E12、C13: E13單元格之和;

4)應用函數設置G11單元格, SUMPRODUCT函數不但可以計算數據區域中滿足條件的數據累加和, 還可以計算數組乘積的累加和[7], 即在G11單元格內輸入“=SUMPRODUCT(C3: E3, C11: E11)”, 即該二行對應的單元格值先相乘再加總; 設置G11單元格: 設置單元格格式/“數字”標簽/分類: 數值-小數位數: 0. 同理, 分別設置G12及G13;

5)設置G14單元格值為G11: G13三個單元格值之和.

3.1.3 利用EXCEL工具欄中的“工具/規劃求解”進行以下設置, 最后點擊“求解”[8]

1)設置規劃求解參數（工具/規劃求解/選項/）, 在“假定非負”前打勾;

2)設置目標單元格, 即G14單元格;

3)設置可變單元格: 即C11: E13區域共九個單元格;

4)添加約束條件, 如圖3:

①設置C11: E13九個單元格中的數值為二進制（約束-添加-單元格引用位置: $C$11:$E$13-邏輯關系: bin-約束值: 二進制）, 即只能取值0或1, 即如某位主編被分配到某項任務, 則對應的單元格值為1, 否則為0;

②設置C14: E14三個單元格中的數值＝1,即每項任務都應當被分配出去, 且只能被分配一次;

③設置F11: F13三個單元格中的數值＝1,即每人都應當被分配到任務, 且只能被分配一項任務.

圖3 M=N時約束條件的設置Figure 3 When M=N set constraints

5)點擊“求解/保存規劃求解結果”, 如圖, 即分別將任務1分配給B, 任務2分配A, 任務3分配給C, 完成全部任務需要的最少時間為66, 如圖4.

圖4 M＝N時指派任務分配結果Figure 4 When M =N assigned task allocation results

3.2 非標準型指派（廣義指派、模糊型指派、競爭型指派）問題（M

非標準型指派問題必須轉化為標準型指派問題[6]. 假設任務數不變, 人數增加1人, 即同時有3項任務需要分配給4位主編, 且每人最多只能分配其中1項任務.此時, 可通過增加虛擬任務數的方法使人數與任務數相等[9],然后再應用M＝N時所采用的方法與步驟.

因第4個任務為虛擬任務, 因此F3: F6單元格值應為0; 由于4位主編只需要承擔3項任務, 且每人至多只能承擔1項, 這就意味著將有一位主編無法被分配到任務, 因此每個主編承擔的任務數為1或0. 更改相關約束條件, 點擊求解, 得到的結果是: C沒有被分配到任務, 完成全部任務需要的最少時間為60, 如圖5、圖6.

圖5 M

圖6 M

3.3 非標準型指派（廣義指派、模糊型指派、競爭型指派）問題（M>N）

假設人數不變, 增加一項任務, 即同時有4項任務需要分配給3位主編, 每位主編至少應承擔一項, 且最多不超過二項任務. 此時, 因人數與任務數不對稱, 因此通過增加虛擬人數的方法使人數與任務數相等; 然后再應用M=N時所采用的方法與步驟, 只需更改相關約束條件即可, 如圖7:

圖7 M>N時約束條件的設置Figure 7 When M>N set constraints

因D為虛擬人, 因此C6: F6單元格值應為0; 由于3位主編需要承擔4項任務, 且每人至少應承擔一項, 最多只能承擔兩項任務, 因此每個主編承擔的任務數為1或2. 更改相關約束條件, 點擊求解, 得到的結果是: A需同時承擔任務2及任務4,完成全部任務需要的最少時間為87. 如圖8.

圖8 M>N時指派任務分配結果Figure 8 When M >N assigned task allocation results

4 結論

綜上所述, 本文根據實例, 通過利用EXCEL對指派問題進行建模, 使用者只需在基本矩陣中輸入相應數值即可輕松完成求解, 簡化了計算步驟, 縮短了決策時間, 提高了工作效率, 并使利用現代計算機技術解決優化類問題更具有普遍性與現實意義.

[1] 韓伯棠. 管理運籌學[M]. 高等教育出版社, 2005: 1.

[2] 達林. 切平面在混合整數非線性規劃中的應用[D]. 北京: 北京交通大學, 2009:11.

[3] 賀德化. 管理決策中常見數學模型[M]. 蘭州: 蘭州大學出版社, 1988: 291.

[4] 熊偉. 運籌學[M]. 北京: 機械工業出版社, 2009: 123.

[5] 鄭鴻鈞. 指派問題的EXCEL求解模板[J]. 辦公自動化, 2012(16): 20-27.

[6] 杜金玲, 周杰. 關于幾種不平衡指派問題的修正匈牙利解法[J]. 價值工程, 2010(13): 120-123.

[7] 寧桂霞, 劉光鳳. 淺談Excel函數在高校教務管理中的應用[J]. 福建電腦, 2013(09): 160-165.

[8] 王貴強. 運籌學上機指南與案例導航[M]. 蘭州: 蘭州大學出版社, 2009: 47.

[9] 陳海偉, 王潔. 一類非平衡指派問題的求解[J]. 河南教育學院學報: 自然科學版, 2011(03): 16-21.

EXCEL model for solving different types of assignment problem

LIU Jing1, LIU Chang-hai2

(1. Jiujiang University Library, Jiujiang 332005, P.R.C.; 2. Business School, Jiujiang University, Jiujiang 332005, P.R.C.)

Assignment problem is an application of operations research branch of integer programming, mainly used to solve the problem of resource allocation. This paper establishes the different types of assignment problem model by EXCEL, aims to get the optimal solution, and applies the model to the organization's management activities to enhance economic efficiency.

assignment problem; EXCEL; integer programming; standard assignment; fuzzy assignment; generalized assignment

TP317.3

: A

: 1003-4271(2014)03-0456-05

10.3969/j.issn.1003-4271.2014.03.24

2014-03-06

劉靜(1978-), 女, 漢族, 內蒙古人, 講師.