指派问题——航班安排问题的R实现-526互联

在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)，这类问题称为指派问题或分派问题。

一、指派问题的数学模型

最优指派问题也称为最优匹配问题，它是运输问题的特殊情况。
例:有一份中文说明书，需译成英、日、德、俄5种文字。分别记作A、B、C、D、E。现有甲、乙、丙、丁、戊5人。他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，使所需总时间最少?

对应每个指派问题，需有类似上表那样的数表，称为效率矩阵或系数矩阵，其元素$c_{ij}＞0(i,j = 1,2,…,?)$表示指派第$i$人去完成第$j$项任务时的效率(或时间、成本等)。

一般指派问题描述如下：
设有$n$个人，计划做$n$项工作，其中$ c_{ij}$ 表示第$i$ 个人做第$j$项工作的收益，现求一种指派方式，使得每个人完成一项工作，总收益最大。
设决策变量为$x_{ij}$，当第$i$个人做第$j$项工作时，决策变量$x_{ij}=1$；否则，决策变量$x_{ij}=0$，因此最优指派问题可以写成0-1规划模型：

\[\max z =\sum^n_{i=1}\sum^n_{j=1}c_{ij}x_{ij}\\ s.t.\quad \sum^n_{j=1}x_{ij}=1,\quad i=1,2,3,\cdots,n\\\ \sum^n_{i=1}x_{ij}=1,\quad j=1,2,\cdots,n\\ x_{ij}=1 \quad or\quad 0,\quad i,j=1,2,\cdots,n \]

如果$c_{ij}$表示第$i$个人做第$j$项工作所用的花费，则目标函数为求最小。

二、航班安排问题

某航空公司经营 A、B、C 三个城市的航线，这些航线每天班次起飞与到达时间如下表。设飞机在机场停留的损失费用大致与停留时间的平方成正比。又每架飞机从降落到下班起飞至少需2小时准备时间，航班安排信息见下表，试决定一个使停留费用损失为最小的分配飞行方案。

航班号	101	102	103	104	105	106	107	108	109	110	111	112	113	114
起飞城市	A	A	A	A	A	B	B	B	C	C	B	B	C	C
起飞时间	9:00	10:00	15:00	20:00	22:00	4:00	11:00	15:00	7:00	15:00	13:00	18:00	15:00	7:00
到达城市	B	B	B	C	C	A	A	A	A	A	C	C	B	B
到达时间	12:00	13:00	18:00	24:00:00	2:00 （次日）	7:00	14:00	18:00	11:00	19:00	18:00	23:00	20:00	12:00

【解析】

A城市损失费用：

B城市损失费用：

C城市损失费用：

三、R实现

library(lpSolve)
a1 = c(4, 9, 64, 169,225)
a2 = c(361, 400, 625, 36, 64)
a3 = c(225, 256, 441, 4, 16)
a4=c(484, 529, 16, 81, 121)
a5=c(196, 225, 400, 625, 9)
cost = rbind(a1,a2,a3,a4,a5)
colnames(cost)=c("101","102","103","104","105")
rownames(cost)=c("106","107","108","109","110")

assign.sol<-lp.assign(cost.mat=cost,direction="min")
assign.sol$solution
colnames(assign.sol$solution)=c("101","102","103","104","105")
rownames(assign.sol$solution)=c("106","107","108","109","110")
assign.sol$solution
assign.sol$objval

assign.sol$solution    #最优指派方案
   101 102 103 104 105
106   0   1   0   0   0
107   0   0   0   1   0
108   0   0   0   0   1
109   0   0   1   0   0
110   1   0   0   0   0
assign.sol$objval     #最优值
273

library(lpSolve)
a1 = c(256, 529, 9, 625, 36)
a2 = c(225, 484, 4, 576, 25)
a3 = c(100, 289, 441, 361, 576)
a4=c(64, 225, 361, 289, 484)
a5=c(256, 529, 9, 625, 36)
cost = rbind(a1,a2,a3,a4,a5)
colnames(cost)=c("106","107","108","111","112")
rownames(cost)=c("101","102","103","113","114")

assign.sol<-lp.assign(cost.mat=cost,direction="min")
colnames(assign.sol$solution)=c("106","107","108","111","112")
rownames(assign.sol$solution)=c("101","102","103","113","114")
assign.sol$solution
assign.sol$objval

assign.sol$solution
    106 107 108 111 112
101   0   0   0   0   1
102   1   0   0   0   0
103   0   1   0   0   0
113   0   0   0   1   0
114   0   0   1   0   0
assign.sol$objval
  848

library(lpSolve)
a1 = c(49, 225, 225, 49)
a2 = c(25, 169, 169, 25)
a3 = c(169, 441, 441, 169)
a4=c(64, 256, 256, 64)
cost = rbind(a1,a2,a3,a4)
colnames(cost)=c("109","110","113","114")
rownames(cost)=c("104","105","111","112")

assign.sol<-lp.assign(cost.mat=cost,direction="min")
colnames(assign.sol$solution)=c("109","110","113","114")
rownames(assign.sol$solution)=c("104","105","111","112")
assign.sol$solution
assign.sol$objval

assign.sol$solution
    109 110 113 114
104   0   1   0   0
105   0   0   1   0
111   1   0   0   0
112   0   0   0   1
assign.sol$objval
  627

所以使停留费用损失最小的方案为：
101(A)→110(C) →104(A) →107(B) →103(A) →109(C) →112(B) →101(A)
102(A) →106(B) →102(A)
105(A) →108(B) →114(C) →111(B) →113(C) →105(A)
损失费：273K+848K+627K=1748K

参考文献