文/李 敏
標(biāo)準(zhǔn)指派問題只要求使得總時(shí)間最少。但實(shí)際很多指派問題既要求總時(shí)間最少,還要求在最短時(shí)間內(nèi)完成。 這類問題被稱為最短時(shí)限指派問題,如搶險(xiǎn)(搶修)任務(wù)的指派問題等。目前,對它的研究較少且主要是研究單目標(biāo)問題,常用算法有簡算法[1]、最短時(shí)限逼近法[2]等。本文研究的是多目標(biāo)問題,給出了在簡算法的基礎(chǔ)上通過對匈牙利算法中尋找獨(dú)立零元素的次序進(jìn)行改進(jìn)的新算法。
多目標(biāo)最短時(shí)限指派問題:設(shè)有n項(xiàng)工作指派給n個(gè)人去做,要求一人一事且一事一個(gè)。已知第i人做第j項(xiàng)工作的時(shí)間為cij,如何分配工作,才能使在最短時(shí)間內(nèi)完成任務(wù)的前提下使總時(shí)間最少。令決策變量xij=1,第i人去做工作j;否則xij=0。則其數(shù)學(xué)模型為:
首先考慮目標(biāo)函數(shù)(1),再考慮目標(biāo)函數(shù)(2)。假設(shè)(1)的最優(yōu)解為F,則多目標(biāo)規(guī)劃模型(1)~(3)可以轉(zhuǎn)化為如下的單目標(biāo)模型:
簡算法是求解單目標(biāo)最短時(shí)限的算法,它可求出完成任務(wù)的最短時(shí)限,但卻不一定使時(shí)間總和達(dá)到最優(yōu)。本算法的思想為:首先找到指派的最短時(shí)限,即目標(biāo)(1)的最優(yōu)解F1,則C中一定存在n個(gè)獨(dú)立且不大于F1的元素,故只要它們的和最小即可。步驟如下:
Step2 將時(shí)間矩陣C中不大于F1的元素全部變?yōu)?,并記為矩陣C(F1)。
Step3 若矩陣C(F1)中某行(列)中的零元素既行獨(dú)立,又列獨(dú)立,則選中它,并劃掉它所在的行和列。若C(F1)中某列(行)存在多個(gè)獨(dú)立零,則在它們的行(列)中找出各自的次小元素,選中次小值最大的行(列)中的獨(dú)立零,劃掉它所在的行和列。若上述情況不止一種,則優(yōu)先分配次小元素最大的行或列中的獨(dú)立零。若C(F1)中所有的行(列)都無獨(dú)立零元素,則任意選出零元素最少的行(列)中的一個(gè)零(多數(shù)禮讓少數(shù))。
Step4 如選中n個(gè)獨(dú)立零元素,則令它們對應(yīng)的變量為1,其它變量為0,即得最優(yōu)指派解;否則,轉(zhuǎn)Step5。
Step5 取 F2=min{cij|cij>F1, i, j=1,2,…, n},用F2代替F1,轉(zhuǎn)Step2。
例 已知某多目標(biāo)最短時(shí)限指派問題的時(shí)間矩陣為:
解由Step1 得,F(xiàn)1=18。將C中不大于F1的元素全部變?yōu)?,得矩陣
可見只選中了3個(gè)獨(dú)立零元素,故轉(zhuǎn)Step5。計(jì)算得F2=19,同理得矩陣
顯然,已找到該指派問題的最優(yōu)解,相應(yīng)的F=19,Z=70。通過比較發(fā)現(xiàn),本算法所用總時(shí)間比文獻(xiàn)[1]要少個(gè)單位,本算法的計(jì)算結(jié)果與文獻(xiàn)[3]一致,且計(jì)算要簡單得多。
通過比較可知該算法操作簡單,對于小規(guī)模指派問題可以手工操作,對于大規(guī)模指派問題可編程實(shí)現(xiàn),因此具有較強(qiáng)的可操作性和適用性。
[1]白國仲.線性不可微規(guī)劃—基于可持續(xù)發(fā)展的決策技術(shù)[M].北京:中國社會科學(xué)出版社,2007.
[2]夏少剛,費(fèi)威.基于最小調(diào)整法求解最短時(shí)限指派問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2009,39(17):179-187.
[3]韓艷娜,郭東威.多目標(biāo)線性不可微指派問題的優(yōu)化算法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(xué)漢文版),2017,46(3):325-328,333.