錢麗麗

(無錫機(jī)電高等職業(yè)技術(shù)學(xué)校，江蘇 無錫 214000)

引言

在日常生活安排和企業(yè)生產(chǎn)管理工作中，經(jīng)常會(huì)遇到給人分派工作或給機(jī)器指派任務(wù)等一般指派問題。一般指派問題是最優(yōu)化問題的一種，它的問題模型是給n個(gè)人(本文中的人泛指可以執(zhí)行任務(wù)的一切物體)指派完成m項(xiàng)任務(wù)，根據(jù)每個(gè)人完成每項(xiàng)任務(wù)的工作效率來研究如何分配任務(wù)，使完成任務(wù)所消耗的總資源最少或總收益最大。指派問題是0-1型整數(shù)規(guī)劃問題中比較常見的一種，它的特點(diǎn)是決策變量只有0和1兩種取值，在問題討論時(shí)，通常把某個(gè)人是否執(zhí)行某項(xiàng)任務(wù)取值為1和0，建立一般指派問題與0-1規(guī)劃對(duì)應(yīng)關(guān)系。當(dāng)指派人數(shù)和任務(wù)數(shù)都比較大或數(shù)量關(guān)系不對(duì)等時(shí)，問題的模型就會(huì)變得復(fù)雜，求解也更加困難。因此，本文引入了LINGO這款軟件，LINGO是美國(guó)LINDO系統(tǒng)公司專門開發(fā)用于求解優(yōu)化模型的數(shù)學(xué)軟件，主要用于求解線性、非線性和整數(shù)優(yōu)化模型，它內(nèi)置了一種建立最優(yōu)化模型的語言，可以簡(jiǎn)便地表達(dá)大規(guī)模問題，利用LINGO高效的求解器可以快速求解并分析結(jié)果[1]。本文通過對(duì)一般指派問題建立0-1規(guī)劃模型，分析模型，并借助LINGO求解法實(shí)現(xiàn)對(duì)此類問題的討論。

目前，一般指派問題根據(jù)人數(shù)和任務(wù)數(shù)的數(shù)量關(guān)系大致有以下三種情況：(1)人數(shù)和任務(wù)數(shù)相等，即每個(gè)人必須只完成一項(xiàng)任務(wù)；(2)人數(shù)小于任務(wù)數(shù)，一個(gè)人可以完成幾項(xiàng)任務(wù)；(3)人數(shù)大于任務(wù)數(shù)，一項(xiàng)任務(wù)可由幾個(gè)人來完成。其中，第一種指派為標(biāo)準(zhǔn)指派，它是一種最基礎(chǔ)的指派，人與任務(wù)一一對(duì)應(yīng)；第二、第三種指派屬于非標(biāo)準(zhǔn)指派。本文通過具體的案例，給出這三種情況的LINGO解法[2]。

一、標(biāo)準(zhǔn)指派問題

例1：有4個(gè)工人，要指派他們完成4項(xiàng)任務(wù)， 規(guī)定每人只能做1項(xiàng)任務(wù), 每項(xiàng)任務(wù)只能1個(gè)人做，每人做各項(xiàng)任務(wù)所消耗的時(shí)間如表1所示，如何分派任務(wù)，可使總的消耗時(shí)間最少[3]？

表1 任務(wù)分配問題

問題分析：這是典型的指派問題，每個(gè)工人必須做且只能做1項(xiàng)工作，第i個(gè)工人是否做第j個(gè)工作可以用0-1型變量表示。所以這類問題的數(shù)學(xué)模型是0-1型整數(shù)規(guī)劃。

(一)模型建立

1.決策變量

2.目標(biāo)函數(shù)

3.約束條件

set:

Worker/1..4/;

Job /1..4/;

Assign(work,job):c,x;

endsets

data:

enddata

min=@sum(Assign:c*x);

@for(worker(i):@sum(job(j):x(i,j))=1);

@for(job(j):@sum(worker(i):x(i,j))=1);

@for(Assign:@bin(x));

(二)模型結(jié)果分析

運(yùn)行結(jié)果中的x(i，j)=1表示第i個(gè)工人執(zhí)行第j項(xiàng)任務(wù)，x(i，j)=0則表示不執(zhí)行，故當(dāng)工人1→任務(wù)2，工人2→任務(wù)1，工人3→任務(wù)3，工人4→任務(wù)4，所用的總時(shí)間最省，共70小時(shí)。

用LINGO求解標(biāo)準(zhǔn)指派問題程序語言比較簡(jiǎn)單，它的語句順序可以交換，字母可以不區(qū)分大小寫，但必須是輸入能被軟件識(shí)別的符號(hào)或語言，否則哪怕是一個(gè)微小的錯(cuò)誤也會(huì)導(dǎo)致程序無法運(yùn)行，所以在編程時(shí)除了要按照正常的要求編寫外，還應(yīng)注意一些細(xì)節(jié)：如變量名只能由字母和數(shù)字組成，變量不能出現(xiàn)在約束條件的右端，調(diào)用函數(shù)必須以符號(hào)@開頭，函數(shù)后面的變量必須加括號(hào)等[4]。

二、非標(biāo)準(zhǔn)指派問題

例2：某公司計(jì)劃開5家新店，并決定由該公司下面的3家建筑公司來負(fù)責(zé)完成。3家建筑公司Ai(i=1,2,3)對(duì)5家新店Bj(j=1,2,3,4,5)的建筑費(fèi)Cij(i=1,2,3,j=1,2,3,4,5)如表2所示，且允許每家建筑公司承建1家或2家商店，但每家商店只能由1家公司承擔(dān)，問如何對(duì)5家新店分配建造任務(wù)，可以使建造費(fèi)用最小。

表2 公司承建商店問題 單位：萬元

(一)問題分析

由于公司少商店多，且每家公司最多可以承擔(dān)2家新店，因此，可以把每家公司化作相同的2家公司，然后再添加虛擬的一列B6，各公司承建商店B6的費(fèi)用均為0，用系數(shù)矩陣來表示出這種變化：

B1B2B3B4B5 B1B2B3B4B5B6

用LINGO軟件求解

sets:

company/1..6/;

shop /1..6/;

Assign(company,shop):c,x;

endsets

data:

enddata

min=@sum(Assign:c*x);

@for(shop(j):@sum(company(i):x(i,j))=1);

@ for(company(i):@sum(shop(j):x(i,j))=1);

@for(Assign:@bin(x));

運(yùn)行結(jié)果顯示出有效數(shù)據(jù)：x(1,1)，x(2,3)，x(3,6)，x(4,2)，x(5,5)，x(6,4)為可行方案，且最小值為35。為了問題研究的方便，把原來的3家公司假設(shè)成了相同的6家，因此，i取1和2、3和4、5和6分別表示公司A1，公司A2，公司 A3，j取1—5表示商店1—商店5，j取6表示沒有商店。故當(dāng)公司A1承建商店B1和B3，公司A2承建商店B2，公司A3承建商店B4和B5時(shí)，所消耗的總建筑費(fèi)用最省，共需35萬元。

例3：有6個(gè)人甲、乙、丙、丁、戊、戌要翻譯日文、韓文、英文和俄文4本書，他們每個(gè)人都精通這4種語言，各自翻譯1本書所需的時(shí)間如表3所示，每個(gè)人只能翻譯1本書，1本書可以由1個(gè)人或2個(gè)人來翻譯，問如何分配任務(wù)，可以使他們總共花的時(shí)間最少？

表3 翻譯問題

問題分析：1本語言書可以由2個(gè)人翻譯，可以把每1本書變成2本相同的書，問題可看成6個(gè)人翻譯8本語言書，缺少的2個(gè)人數(shù)用虛擬的2個(gè)人補(bǔ)足，虛擬的2個(gè)人翻譯每本書所用的時(shí)間為0，用系數(shù)矩陣表示出這種變化：

(二)編寫LINGO程序

sets:

person /1..8/;

language /1..8/;

Assign(person,language):c,x;

endsets

data:

enddata

min=@sum(Assign:c*x);

@for(language(j):@sum(person(i):x(i,j))

=1);

@for(person(i):@sum(language(j):x(i,j))=1);

@for(Assign:@bin(x));

運(yùn)行程序結(jié)果顯示，甲和丙翻譯日文書，乙和戌翻譯英文書，丁翻譯俄文書，戊翻譯韓文書，6個(gè)人翻譯8本書的總共時(shí)間最少為24小時(shí)，由于8本書是原來4本書的疊加，所以6個(gè)人翻譯8本書所花的時(shí)間應(yīng)該是6個(gè)人翻譯4本書的兩倍，故實(shí)際最少時(shí)間應(yīng)該是12小時(shí)。

在解決以上兩種非標(biāo)準(zhǔn)指派問題時(shí)可以通過增加虛擬的“人”或虛擬的“事”來轉(zhuǎn)化為標(biāo)準(zhǔn)指派問題。其中，增設(shè)的虛擬人做各種事的費(fèi)用或產(chǎn)生的效益均為0，同樣，增加的虛擬的事被人完成所需的費(fèi)用或能產(chǎn)生的效益也是0。當(dāng)然，還要注意的是，幾個(gè)人完成同一件事的時(shí)間并不是他們獨(dú)立完成這件事時(shí)間的簡(jiǎn)單疊加，所以應(yīng)根據(jù)實(shí)際情況對(duì)計(jì)算結(jié)果進(jìn)行一定分析和處理。

結(jié)束語

一般指派問題是生產(chǎn)管理者在日常工作中經(jīng)常會(huì)遇到的一類問題。用LINGO軟件求解標(biāo)準(zhǔn)指派問題能更高效地表達(dá)目標(biāo)函數(shù)與約束條件，所編的程序語言幾乎是對(duì)數(shù)學(xué)模型的翻譯，不需要太多的轉(zhuǎn)換,程序結(jié)果簡(jiǎn)潔易懂，即使初學(xué)者也能快速掌握。而本文中討論的兩種非標(biāo)準(zhǔn)指派問題最終都能通過一定的條件假設(shè)轉(zhuǎn)化為標(biāo)準(zhǔn)指派問題來求解。當(dāng)然，還有一些其他的非標(biāo)準(zhǔn)指派，如限定某人一定不能做某項(xiàng)工作或者必須做某項(xiàng)工作的情況更為復(fù)雜，不屬于一般的范疇，這里就不作深入討論了。