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

劉靜, 劉昌海

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

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

劉靜1, 劉昌海2

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

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

指派問題; EXCEL; 整數(shù)規(guī)劃; 標(biāo)準指派; 模糊指派; 廣義指派

引言

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

1 指派問題簡介

指派問題是運籌學(xué)數(shù)學(xué)規(guī)劃中整數(shù)規(guī)劃的一種應(yīng)用.

運籌學(xué)是應(yīng)用分析、試驗、量化的方法, 對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排, 為決策者提供有依據(jù)的最優(yōu)方案, 以實現(xiàn)最有效的管理[1].

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

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

2 指派問題的類型

根據(jù)人數(shù)與任務(wù)數(shù)的關(guān)系, 指派問題可以分為二類:

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

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

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

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

②M

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

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

3.1 標(biāo)準型（平衡型）指派問題（M＝N）

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

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

用EXCEL建模, 步驟如下:

3.1.1 設(shè)計基本矩陣

圖1基本矩陣Figure 1 Basic matrix

3.1.2 設(shè)計變量矩陣

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

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

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

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

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

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

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

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

2)設(shè)置目標(biāo)單元格, 即G14單元格;

3)設(shè)置可變單元格: 即C11: E13區(qū)域共九個單元格;

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

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

②設(shè)置C14: E14三個單元格中的數(shù)值＝1,即每項任務(wù)都應(yīng)當(dāng)被分配出去, 且只能被分配一次;

③設(shè)置F11: F13三個單元格中的數(shù)值＝1,即每人都應(yīng)當(dāng)被分配到任務(wù), 且只能被分配一項任務(wù).

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

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

圖4 M＝N時指派任務(wù)分配結(jié)果Figure 4 When M =N assigned task allocation results

3.2 非標(biāo)準型指派（廣義指派、模糊型指派、競爭型指派）問題（M

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

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

圖5 M

圖6 M

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

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

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

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

圖8 M>N時指派任務(wù)分配結(jié)果Figure 8 When M >N assigned task allocation results

4 結(jié)論

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

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

[2] 達林. 切平面在混合整數(shù)非線性規(guī)劃中的應(yīng)用[D]. 北京: 北京交通大學(xué), 2009:11.

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

[4] 熊偉. 運籌學(xué)[M]. 北京: 機械工業(yè)出版社, 2009: 123.

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

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

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

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

[9] 陳海偉, 王潔. 一類非平衡指派問題的求解[J]. 河南教育學(xué)院學(xué)報: 自然科學(xué)版, 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-), 女, 漢族, 內(nèi)蒙古人, 講師.