基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法及其應(yīng)用

鮑培文

（武警特警學(xué)院，北京昌平 102200）

指派問題是運(yùn)籌學(xué)中的規(guī)劃問題，主要是運(yùn)用數(shù)學(xué)和現(xiàn)代計(jì)算機(jī)技術(shù)等科學(xué)技術(shù)方法，從數(shù)量方面揭示指派問題的模型、方法和應(yīng)用，為科學(xué)地進(jìn)行指派活動(dòng)、合理利用資源、提高指派效益提供理論和方法.針對(duì)指派問題具有網(wǎng)絡(luò)特征，設(shè)計(jì)基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法，有利于綜合運(yùn)用網(wǎng)絡(luò)模型，解決指派問題.

1 指派問題及其網(wǎng)絡(luò)方法

指派問題既屬于資源優(yōu)化的線性規(guī)劃，又屬于多階段決策問題的動(dòng)態(tài)規(guī)劃.這也賦予指派問題的多種模型及求解方法，每一種模型和方法都有利于合理分配資源，提高有限資源的使用效益.

1.1 標(biāo)準(zhǔn)指派問題的網(wǎng)絡(luò)化模型

在日常管理工作中，往往會(huì)碰到這樣的人員分配問題：有 n項(xiàng)任務(wù)（或工作）A1，A2，…，An，需要給 n個(gè)人B1，B2，…，Bn去完成，每人只能執(zhí)行一項(xiàng)任務(wù).由于每個(gè)人完成每一項(xiàng)任務(wù)的時(shí)間（或效率）不盡相同，所以不同的分配方案完成任務(wù)的總時(shí)間（或總效率）也不同，要解決的問題是分配何人去完成何項(xiàng)任務(wù)，才能使完成n項(xiàng)任務(wù)的時(shí)間最少（或總效率最高）.

任務(wù)分配與工作指派問題簡(jiǎn)稱為分配問題或指派問題（Assignment Problem）.指派問題的條件是：每項(xiàng)工作只能分配給一個(gè)單位（人）去完成；每個(gè)單位（人）只能接受其中一項(xiàng)任務(wù).其中，工作數(shù)和單位數(shù)一致時(shí)，稱為標(biāo)準(zhǔn)指派問題.非標(biāo)準(zhǔn)指派問題可以轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)指派問題[1]303-305.

標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型：（xij為第i項(xiàng)工作派第j個(gè)單位完成，f為總費(fèi)用）

標(biāo)準(zhǔn)指派問題有很多種解法.筆者在《指派問題的等價(jià)問題研究》[2]中，介紹了指派問題的各種解法.隨著網(wǎng)絡(luò)方法的普及，可建立基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)化模型.即指派問題按任務(wù)劃分為n個(gè)階段，每一階段初始狀態(tài)xij，代表Ai到Bj保障小組的起始狀態(tài)，規(guī)定x11=0，x（n+1）1=1，

1.2 基于動(dòng)態(tài)規(guī)劃的指派問題網(wǎng)絡(luò)方法

指派問題屬于動(dòng)態(tài)規(guī)劃問題的特例.基于動(dòng)態(tài)規(guī)劃的指派問題，通過動(dòng)態(tài)規(guī)劃的建模方法，借用標(biāo)號(hào)法求解最短路線思路，結(jié)合網(wǎng)絡(luò)方法進(jìn)行實(shí)例分析，進(jìn)一步拓展指派問題解法[3].

網(wǎng)絡(luò)方法可以從廣義上和狹義上區(qū)分.廣義上的網(wǎng)絡(luò)方法，是把現(xiàn)代科學(xué)思想中網(wǎng)絡(luò)的觀點(diǎn)運(yùn)用到指派問題中，不局限于內(nèi)容.而狹義的網(wǎng)絡(luò)方法，是指依托計(jì)算機(jī)網(wǎng)絡(luò)和網(wǎng)絡(luò)技術(shù)進(jìn)行網(wǎng)絡(luò)化計(jì)算.指派問題網(wǎng)絡(luò)方法基于動(dòng)態(tài)規(guī)劃問題建立多階段動(dòng)態(tài)規(guī)劃模型，采用標(biāo)號(hào)法等方法，共同完成指派任務(wù)準(zhǔn)備、任務(wù)實(shí)施和任務(wù)總結(jié)的完整過程.

1.3 標(biāo)準(zhǔn)指派問題網(wǎng)絡(luò)方法流程圖及算法

標(biāo)準(zhǔn)指派問題網(wǎng)絡(luò)方法流程圖（圖1）從分析實(shí)際問題、列出時(shí)間矩陣開始，給出符合要求的可能分配方案，按照動(dòng)態(tài)規(guī)劃模型，使用網(wǎng)絡(luò)方法計(jì)算每一分配方案的費(fèi)用總值，尋找費(fèi)用最小值.

圖1 指派問題網(wǎng)絡(luò)方法流程圖

指派問題網(wǎng)絡(luò)方法lindo算法

model：

!n個(gè)工人，n個(gè)工作的分配問題；

sets：

workers/w1..wn/；

jobs/j1..jn/；

links（workers，jobs）：cost，volume；

endsets

!目標(biāo)函數(shù)；

min=@sum（links：cost*volume）；

!每個(gè)工人只能有一份工作；

@for（workers（I）：

@sum（jobs（J）：volume（I，J））=1；

）；

!每份工作只能有一個(gè)工人；

@for（jobs（J）：

@sum（workers（I）：volume（I，J））=1；

）；

data：

cost=a11a12……a1n

a21a22……a2n

………………

an1an2…… ann；

enddata

end

2 基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法的應(yīng)用

基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法，應(yīng)用廣泛而靈活.

問題 某修理所組成A1，A2，A3，A4四個(gè)修理小組，對(duì)B1，B2，B3，B4四個(gè)單位實(shí)施技術(shù)保障，由于各組的技術(shù)專長和設(shè)備不同，各單位的設(shè)備損壞程度不同，因此各組在各單位完成任務(wù)所需要的時(shí)間也不一樣.假定具體時(shí)間如表1所示.問哪一修理組完成哪一個(gè)單位的技術(shù)保障任務(wù)，才能使總的時(shí)間最少.

表1 修理組分配問題

這是線性規(guī)劃的指派問題，建立指派問題模型：按任務(wù)劃分為四個(gè)階段，xij代表Ai到Bj保障小組的狀態(tài)，規(guī)定xij=0，1狀態(tài)為1表示派去，為0表示不派去，f為總的時(shí)間.

按照匈牙利法可以求出分配方案：A1到B1，A2到B3，A3到 B4，A4 到 B2.

下面按任務(wù)劃分為四個(gè)階段，每一階段初始狀態(tài)xij，代表 Ai到 Bj保障小組的起始狀態(tài)，規(guī)定 x11=0，x51=1，

按照指派問題的模型、流程和算法，輸出符合要求的指派方案，如圖2和圖3.

運(yùn)行 lindo，分配方案，A1到 B1，A2到 B3，A3到B4，A4到 B2.

調(diào)用Python，結(jié)果如下：

#-*-coding：utf-8-*-

import numpyas np

import copy

c=[2，3，5，7，3，5，2，8，9，5，7，8，2，2，3，9

]

c=np.array（c）

c=c.reshape（（4，4））

all_p=[]

class obj：

def_init_（self）：

self.p=[]

self.cost=0

for i in range（4）：

for j in range（4）：

ifj==i：

continue

for u in range（4）：

ifu==i or u==j：

continue

for vin range（4）：

ifv==i or v==j or v==u：

continue

p=np.zeros（（4，4））

p[0，i]=p[1，j]=p[2，u]=p[3，v]=1

ans=obj（）

ans.p=copy.deepcopy（p）

ans.cost=sum（sum（c*ans.p））

all_p.append（ans）

all_p.sort（key=lambda ans：ans.cost，reverse=False）

print（all_p[0].p）

print（all_p[0].cost）

圖2

圖3

Python 3.7.3（v3.7.3：ef4ec6ed12，Mar 25 2019，22：22：05）

[MSCv.1916 64 bit（AMD64）]on win32

Type“help”，“copyright”，“credits”or“l(fā)icense（）”for more

information.

＞＞＞

RESTART：C：/Users/Administrator/AppData/Local/Programs/

Python/Python37/33333333333.py

[[1.0.0.0.]

[0.0.1.0.]

[0.0.0.1.]

[0.1.0.0.]]

14.0

＞＞＞

3 基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法應(yīng)把握的問題

基于動(dòng)態(tài)規(guī)劃指派問題網(wǎng)絡(luò)方法應(yīng)注重理論聯(lián)系實(shí)際，進(jìn)行網(wǎng)絡(luò)化分析，把握三對(duì)關(guān)系，提高決策優(yōu)化能力.

3.1 整體與部分相統(tǒng)一.整體的各個(gè)部分是有機(jī)地、有組織地相互聯(lián)系、相互作用著的，這種組織性使得各個(gè)部分所不具有的新特征和屬性涌現(xiàn)出來；同時(shí)，部分在成為整體的成員后，作為部分所獨(dú)有的特征和屬性也會(huì)受到整體的限制和束縛.這就要求指派問題運(yùn)用網(wǎng)絡(luò)方法時(shí)，既為整體形成網(wǎng)絡(luò)留出鏈路接口，提供參考，又使部分和整體內(nèi)容相統(tǒng)一.

3.2 建模與網(wǎng)絡(luò)方法相統(tǒng)一.指派問題網(wǎng)絡(luò)方法關(guān)鍵步驟是根據(jù)問題建立模型，需要掌握一定的量化分析方法.量化分析方法并非人人都能掌握，給問題求解帶來了難度.運(yùn)用網(wǎng)絡(luò)方法，可以突破難點(diǎn)，化難為易，收到意想不到的效果.如基于動(dòng)態(tài)規(guī)劃指派問題，模型的建立不是很好理解，但效仿最短路線法，用網(wǎng)絡(luò)方法可以克服建模方法的困難，通過圖上求解，還能輔助建模方法的進(jìn)一步理解和掌握.

3.3 趣味性和互動(dòng)性相統(tǒng)一.指派問題網(wǎng)絡(luò)方法是模型的另一種形式，既拓寬了鏈路，又增強(qiáng)了互動(dòng)性.在此網(wǎng)絡(luò)方法中，看似無序，通過建模逐漸自組織為有序，形成網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)多個(gè)屬性、功能、行為，且具有相對(duì)的穩(wěn)定性；條件變化又會(huì)影響和破壞網(wǎng)絡(luò)的有序，就會(huì)進(jìn)入下一個(gè)無序自組織、自學(xué)習(xí)，進(jìn)而又成為有序.指派問題網(wǎng)絡(luò)方法呈現(xiàn)網(wǎng)絡(luò)模型的適應(yīng)性、學(xué)習(xí)和自組織等特性，可以提高學(xué)習(xí)的興趣，增強(qiáng)互動(dòng)性.