基于動態規劃的指派問題網絡方法及其應用

鮑培文

（武警特警學院，北京昌平 102200）

指派問題是運籌學中的規劃問題，主要是運用數學和現代計算機技術等科學技術方法，從數量方面揭示指派問題的模型、方法和應用，為科學地進行指派活動、合理利用資源、提高指派效益提供理論和方法.針對指派問題具有網絡特征，設計基于動態規劃的指派問題網絡方法，有利于綜合運用網絡模型，解決指派問題.

1 指派問題及其網絡方法

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

1.1 標準指派問題的網絡化模型

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

任務分配與工作指派問題簡稱為分配問題或指派問題（Assignment Problem）.指派問題的條件是：每項工作只能分配給一個單位（人）去完成；每個單位（人）只能接受其中一項任務.其中，工作數和單位數一致時，稱為標準指派問題.非標準指派問題可以轉變為標準指派問題[1]303-305.

標準指派問題的數學模型：（xij為第i項工作派第j個單位完成，f為總費用）

標準指派問題有很多種解法.筆者在《指派問題的等價問題研究》[2]中，介紹了指派問題的各種解法.隨著網絡方法的普及，可建立基于動態規劃的指派問題網絡化模型.即指派問題按任務劃分為n個階段，每一階段初始狀態xij，代表Ai到Bj保障小組的起始狀態，規定x11=0，x（n+1）1=1，

1.2 基于動態規劃的指派問題網絡方法

指派問題屬于動態規劃問題的特例.基于動態規劃的指派問題，通過動態規劃的建模方法，借用標號法求解最短路線思路，結合網絡方法進行實例分析，進一步拓展指派問題解法[3].

網絡方法可以從廣義上和狹義上區分.廣義上的網絡方法，是把現代科學思想中網絡的觀點運用到指派問題中，不局限于內容.而狹義的網絡方法，是指依托計算機網絡和網絡技術進行網絡化計算.指派問題網絡方法基于動態規劃問題建立多階段動態規劃模型，采用標號法等方法，共同完成指派任務準備、任務實施和任務總結的完整過程.

1.3 標準指派問題網絡方法流程圖及算法

標準指派問題網絡方法流程圖（圖1）從分析實際問題、列出時間矩陣開始，給出符合要求的可能分配方案，按照動態規劃模型，使用網絡方法計算每一分配方案的費用總值，尋找費用最小值.

圖1 指派問題網絡方法流程圖

指派問題網絡方法lindo算法

model：

!n個工人，n個工作的分配問題；

sets：

workers/w1..wn/；

jobs/j1..jn/；

links（workers，jobs）：cost，volume；

endsets

!目標函數；

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

!每個工人只能有一份工作；

@for（workers（I）：

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

）；

!每份工作只能有一個工人；

@for（jobs（J）：

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

）；

data：

cost=a11a12……a1n

a21a22……a2n

………………

an1an2…… ann；

enddata

end

2 基于動態規劃指派問題網絡方法的應用

基于動態規劃指派問題網絡方法，應用廣泛而靈活.

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

表1 修理組分配問題

這是線性規劃的指派問題，建立指派問題模型：按任務劃分為四個階段，xij代表Ai到Bj保障小組的狀態，規定xij=0，1狀態為1表示派去，為0表示不派去，f為總的時間.

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

下面按任務劃分為四個階段，每一階段初始狀態xij，代表 Ai到 Bj保障小組的起始狀態，規定 x11=0，x51=1，

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

運行 lindo，分配方案，A1到 B1，A2到 B3，A3到B4，A4到 B2.

調用Python，結果如下：

#-*-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“license（）”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 基于動態規劃指派問題網絡方法應把握的問題

基于動態規劃指派問題網絡方法應注重理論聯系實際，進行網絡化分析，把握三對關系，提高決策優化能力.

3.1 整體與部分相統一.整體的各個部分是有機地、有組織地相互聯系、相互作用著的，這種組織性使得各個部分所不具有的新特征和屬性涌現出來；同時，部分在成為整體的成員后，作為部分所獨有的特征和屬性也會受到整體的限制和束縛.這就要求指派問題運用網絡方法時，既為整體形成網絡留出鏈路接口，提供參考，又使部分和整體內容相統一.

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

3.3 趣味性和互動性相統一.指派問題網絡方法是模型的另一種形式，既拓寬了鏈路，又增強了互動性.在此網絡方法中，看似無序，通過建模逐漸自組織為有序，形成網絡結構實現多個屬性、功能、行為，且具有相對的穩定性；條件變化又會影響和破壞網絡的有序，就會進入下一個無序自組織、自學習，進而又成為有序.指派問題網絡方法呈現網絡模型的適應性、學習和自組織等特性，可以提高學習的興趣，增強互動性.