【公式求解】线性规划之整数规划(2)

许多实际应用问题可以归结为这样的形式:将不同的任务分派给若干人去完成,由于任务的难易程度以及人员的素质高低不尽相同,因此每个人完成不同任务的效率存在差异。于是需要考虑应该分派何人去完成哪种任务能够使得总效率最高。这一类问题通常称为指派问题。
指派问题是运筹学中的经典问题,其中的”任务”可以是任何类型的活动,而”人”则可以是任何类型的资源。所以,基于指派问题的科学决策方法在资源优化、项目选址、生产调度、物流管理、决策支持系统以及军事作战方面有着广泛的应用。

1、标准指派模型

标准指派问题的数学模型为
$ min \quad z = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_{ij}x_{ij} $
$ s.t. \begin{cases}
\sum\limits_{j=1}^{n}x_{ij} = 1 \\
\sum\limits_{i=1}^{n}x_{ij} = 1 \\
x_{ij} = 0或1
\end{cases}
$
这是一个纯0-1整数规划模型。当然可以通过分支定界法或隐枚举法来求最优解。但标准指派问题的数学模型由于具有独特的结构,可以采用匈牙利算法——这是一个求解标准指派问题的有效算法。

例:某商业公司计划开办5家新商店,决定由5家建筑公司分别承建。已知建筑公司Ai(i=1,2,3,4,5)对新商店Bj(j=1,2,3,4,5)的建造费用报价(万元)为cij(i,j=1,2,3,4,5)。为节省费用,商业公司应当对5家建筑公司怎样分配建造任务,才能使总的建造费用最少?

B1 B2 B3 B4 B5
A1 4 8 7 15 12
A2 7 9 17 14 10
A3 6 9 12 8 7
A4 6 7 14 6 10
A5 6 9 12 10 6

解:这是一个标准的指派问题。引进0-1变量
$$x_{ij}=\begin{cases}
1 \quad A_{i}承建B_{j}\\
0 \quad A_{i}不承建B_{j}
\end{cases}
$$
则问题的数学模型为
$ min \quad z = \sum\limits_{i=1}^{5}\sum\limits_{j=1}^{5}c_{ij}x_{ij} $
$ s.t. \begin{cases}
\sum\limits_{j=1}^{5}x_{ij} = 1 \\
\sum\limits_{i=1}^{5}x_{ij} = 1 \\
x_{ij} = 0或1
\end{cases}
$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import numpy as np
import cvxpy as cp

c = np.array([[4,8,7,15,12],
[7,9,17,14,10],
[6,9,12,8,7],
[6,7,14,6,10],
[6,9,12,10,6]])

x = cp.Variable((5,5),integer=True)

obj = cp.Minimize(cp.sum(cp.multiply(c,x))) # 构造目标函数

con = [0<=x, x<=1, cp.sum(x,axis=0,keepdims=True)==1, cp.sum(x,axis=1,keepdims=True)==1] # 构造约束条件

prob = cp.Problem(obj, con) # 构建问题模型

prob.solve(solver='GLPK_MI') # 求解问题

print('最优解为:', x.value)
print('最优值为:', prob.value)

得出让A1承建B3,A2承建B2,A3承建B1,A4承建B4,A5承建B5。这样的安排能使总的建造费用最少,最小费用为34万元。

2、广义指派模型

在实际应用中,常会遇到各种非标准形式的指派问题——广义指派问题。通常的处理方法是先将它们转化为标准形式,然后用匈牙利算法求解。
(1)最大化指派问题
一些指派问题中,每人完成各项工作的效率可能是诸如利润、业绩等效益型指标,此时则以总的工作效率最大为目标函数。即
$ max \quad z = \sum\limits_{i=1}^{5}\sum\limits_{j=1}^{5}c_{ij}x_{ij} $
对于最大化指派问题,若令$ M = \mathop{\max}\limits_{1 \leq i,j \leq n} {c_{ij}} $,再考虑约束条件$ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_{ij}x_{ij} = n $,则有
$ nM - max \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}c_{ij}x_{ij} = min \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(M-c_{ij})x_{ij} $
这是一个以$ (M - c_{ij})_{n \times n} $为效率矩阵的标准指派问题。
(2)人数和任务数不等的指派问题
一些指派问题中,可能出现人数和任务数不相等的情况。对于这样的指派问题,通常的处理方式为: 若人数少于任务数,则可添加一些虚拟的”人”。这些虚拟的人完成各项任务的效率取0,理解为这些效率值实际上不会发生。若人数多于任务数,则可添加一些虚拟的”任务”。这些虚拟的任务被每个人完成的效率同样也取0。
(3)一个人可完成多项任务的指派问题
一些指派问题中,可能出现要求某人完成几项任务的情形。对于这样的指派问题,可将该人看作相同的几个人来接受指派,只需令其完成同一项任务的效率都一样即可。
(4)某项任务一定不能由某人完成的指派问题
一些指派问题中,可能出现某人不能完成某项任务的情形。对于这样的指派问题,只需将相应的效率值(成本型)取成足够大的数即可。

0%