A-level 数学/Edexcel/决策2/分配问题

分配问题 (AP)（也称为分配问题，虽然在本文中将被称为前者）是一种常见的形式。 AP 的一个显著特征是，一个代理人被分配到一个且仅一个任务。现实生活中的例子可能是

分配合同
分配任务给机器
分配代理人到任务
分配销售人员到区域

此类问题的一个例子是三辆卡车 A、B 和 C，以及需要运输的三种货物 1、2 和 3。一个示例安排是 A → 1、B → 2 和 C → 3。这意味着卡车 A 运输货物 1，卡车 B 运输货物 2，卡车 C 运输货物 3。

平衡问题

一个平衡的 AP 是指

(代理人数量) = (任务数量)

表 1
	1	2	3
A	15	10	12
B	10	7	11
C	15	6	9

再考虑我们卡车和货物的例子。在这个例子中，代理人（卡车）的数量是 3，任务（需要运输的货物）的数量也等于 3。因此，这是一个平衡问题。最初，人们只会考虑平衡问题以及如何解决它们。

在扩展之前的问题后，发现每辆卡车运输每种货物的成本都不同。这些成本在表 1 中表示。

卡车车队的经理希望将完成所有三项工作的总成本降至最低。人们将如何分配卡车到货物上？给定的数字表称为问题的成本矩阵。

线性规划问题的公式

对于 AP，可以很容易地开发线性规划问题。人们将定义 $x$ _ij（其中代理人i被分配到任务j），其中

x

_ij=1，当代理人i完成任务j时

x

_ij=0，当代理人i没有完成任务j时

因此，人们可以通过依次考虑每个代理人/任务来获得线性规划问题的约束条件

由于每个代理人被分配到一个且仅一个工作，我们可以推断

对于代理人 A

x

_A1 +

x

_A2 +

x

_A3 = 1

对于代理人 B

x

_B1 +

x

_B2 +

x

_B3 = 1

对于代理人 C

x

_C1 +

x

_C2 +

x

_C3 = 1

类似地，由于每个工作被分配到一个且仅一个代理人，人们可以推断

对于工作 1

x

_A1 +

x

_B1 +

x

_C1 = 1

对于工作 2

x

_A2 +

x

_B2 +

x

_C2 = 1

对于工作 3

x

_A3 +

x

_B3 +

x

_C3 = 1

如果我们将此应用于前面提到的示例，可以发现对于卡车 A，它只能运输货物 1、2 或 3 中的一种。所以， $x$ _A1 可以 = 1，同时 $x$ _A2 和 $x$ _A3 为零，或者 $x$ _A2 = 1，同时 $x$ _A1 和 $x$ _A3 为零，等等。

为了获得此示例的目标函数，我们必须考虑总成本。

对于卡车 A，成本将是：15

x

_A1

+

10

x

_A2

+

12

x

_A3

对于卡车 B，成本将是：10

x

_B1

+

7

x

_B2

+

11

x

_B3

对于卡车 C，成本将是：15

x

_C1

+

6

x

_C2

+

9

x

_C3

因此，这意味着此示例的目标函数Z是将 Z 降至最低，其中

Z = 15

x

_A1

+

10

x

_A2

+

12

x

_A3

+

10

x

_B1

+

7

x

_B2

+

11

x

_B3

+

15

x

_C1

+

6

x

_C2

+

9

x

_C3

最后，这意味着人们可以得出 LPP 为

将 Z 降至最低，其中 Z = 15 $x$ _A1 $+$ 10 $x$ _A2 $+$ 12 $x$ _A3 $+$ 10 $x$ _B1 $+$ 7 $x$ _B2 $+$ 11 $x$ _B3 $+$ 15 $x$ _C1 $+$ 6 $x$ _C2 $+$ 9 $x$ _C3，受以下约束
$x$ _A1 + $x$ _A2 + $x$ _A3 = 1

$x$ _B1 + $x$ _B2 + $x$ _B3 = 1

$x$ _C1 + $x$ _C2 + $x$ _C3 = 1

$x$ _A1 + $x$ _B1 + $x$ _C1 = 1

$x$ _A2 + $x$ _B2 + $x$ _C2 = 1

$x$ _A3 + $x$ _B3 + $x$ _C3 = 1

平衡分配问题的解决

哈罗德·库恩在 1950 年代开发了一种算法，并将其命名为匈牙利算法。它的名字是对 Dénes Kőnig 和 Jenő Egerváry 的一种引用，他们是一对著名的匈牙利数学家，他们的技术应用于这种算法中。

匈牙利算法

为了使匈牙利算法起作用，分配问题必须满足以下条件

正如我们之前看到的，每个工人必须被分配到一个且仅一个工作。
每个工作必须被分配到一个且仅一个工人。
在成本矩阵中，可以从任何行或列的所有成本值中添加或减去一个常数，而不会对最优分配产生任何影响。

匈牙利算法的实施分为三个阶段

寻找机会成本矩阵
测试最优分配。如果可以进行最优分配，请使用它并停止。
如果无法进行最优分配，请修改机会成本矩阵并返回到上一步。

为了演示这三个步骤，让我们再次考虑卡车示例。

寻找机会成本矩阵

机会成本矩阵（OCM）本质上是我们最初成本矩阵的修改版本。为了将成本矩阵更改为 OCM，必须执行两个阶段。

执行 **行减少**
执行 **列减少**

行减少是在每行中从每个数字中减去最小数字的操作。以我们之前的示例为例

成本矩阵
	1	2	3
A	15	10	12
B	10	7	11
C	15	6	9

带有行最小值的成本矩阵
	1	2	3	行最小值
A	15	10	12	10
B	10	7	11	7
C	15	6	9	6

行减少后的成本矩阵
	1	3
A	5	2
B	3	4
C	9	3

接下来，完成列减少。这与行减少相同，只是从每个列中的最小数字中减去该列中的每个值。因此

行减少后的成本矩阵
	1	3
A	5	2
B	3	4
C	9	3

带有列最小值的成本矩阵
	1	3
A	5	2
B	3	4
C	9	3
列最小值	3	2

列减少后的成本矩阵
	1	3
A	2	0
B	0	2
C	6	1

因此，完成的机会成本矩阵为

机会成本矩阵
	1	3
A	2	0
B	0	2
C	6	1

解释机会成本矩阵

由于分配问题的目标是将一个代理分配给一个任务，因此必须将每个代理分配给最能最小化总成本的任务。完成行减少和列减少后，可以合理地假设表中剩余的值是可能的最小值。同样，由于表中的值是成本值，因此表中最小的值无疑是最低成本的值。为了找到解决方案，必须从每行中选择一个零，并从每列中选择一个零。但是，不能从任何行或列中选择多个值，因为这会导致一个代理/任务被分配两次，这在分配问题中是不可能发生的。

同样，让我们考虑前面的示例。如果要从每个列/行中选择一个零，并且没有出现重复，则唯一可能的解决方案是（选择成本标记为星号）

机会成本矩阵
	1	2	3
A	2	0	0*
B	0*	0	2
C	6	0*	1

如果然后将此解决方案分配给我们的原始成本矩阵，则可以看到以下内容

成本矩阵
	1	2	3
A	15	10	12*
B	10*	7	11
C	15	6*	9

因此，最终分配为

A → 3（成本 12）

B → 1（成本 10）

C → 2（成本 6）

Z = 12 + 10 + 6 = 28

有趣的是，尽管这是最便宜的解决方案，但它实际上并没有利用表中所有最低的值。

解决方案的最优性

AP 中的一个重要问题是解决方案的最优性 - 当获得解决方案时，如何确保它确实是最佳的解决方案？使用匈牙利算法，有一个关于在机会成本矩阵中绘制通过零的线的相当简单的最优性测试。如果线的数量（仅水平和垂直）等于行/列的数量，则获得的解决方案是最优的。但是，如果需要的线数不等于行/列数，则该解决方案不是最优的，可以改进。这是一种有些令人费解的技术，但它易于实施且易于解释。

考虑以下 OCM

机会成本矩阵
	1	2	3
A	1	0	2
B	5	0	0
C	6	3	1

可以很容易地看到，只需要两条线就可以穿过所有零 - 例如，可以使用一条穿过行 B 的水平线和一条穿过列 2 的垂直线。2≠3（行/列数），因此无法获得最优解。

另一方面，考虑我们的卡车示例。我们获得的解决方案是最优的吗？

机会成本矩阵
	1	3
A	2	0
B	0	2
C	6	1

可以看出，为了划掉每个零，需要三条线（例如，一条穿过列 2，一条穿过行 B，一条穿过行 A）。3 = 3，因此我们有一个无法改进的最优解。

机会成本矩阵的修订

在获得非最优分配的情况下，必须修改 OCM。此过程有几个步骤

检查被绘制线遮盖的成本
确定最小的未遮盖值
从所有未遮盖的成本中减去该值
将该值添加到任何位于两条绘制线的交点处的成本

从我们之前的非最优解中，最小的未遮盖值为 1。从每个未遮盖的值中减去 1，得到

机会成本矩阵
	1	2	3
A	0	0	1
B	5	0	0
C	5	3	0

将 1 添加到两条线的交点（在本例中，可以将它们绘制在行 B 和列 2 中，因此交点是单元格 B2）得到

机会成本矩阵
	1	2	3
A	0	0	1
B	5	1	0
C	5	3	0

同样，只需要两条线（这一次，它们必须穿过行 A 和列 3）。它们在单元格 A3 相交。最小的未遮盖值为 1。因此，从每个未遮盖的单元格中减去 1 并将 1 添加到单元格 A3 得到

机会成本矩阵
	1	2	3
A	0	0	2
B	4	0	0
C	4	2	0

最后，需要绘制穿过所有零的最小线数为 3，这等于行/列数。这意味着任何分配都是最优的。

不平衡分配问题的解决方案

平衡 AP 的定义是代理数量与任务数量相同的 AP。在现实中，这不太可能发生 - 也就是说，出租车司机数量与客户数量相同的情况不太可能发生。在不平衡问题的情况下，必须添加一个 **虚拟的**，它是一个空白行，添加到成本矩阵中，以为了算法的需要而“平衡”行。例如，如果有三个代理和四个任务，则会添加一个 **虚拟行**。另一方面，如果拥有四个代理和三个任务，则会添加一个 **虚拟任务**。这很有帮助，因为它意味着一个代理或任务将没有“实际”分配，因为使用它们将增加分配的总成本。

考虑以下示例

一家出租车公司有四名司机（A、B、C、D），目前都在不同的地点。三个客户（1、2、3）已经致电出租车公司，需要被送往目的地。司机行驶的总距离在下面的成本矩阵中表示

成本矩阵
	1	2	3
A	11	19	17
B	21	15	13
C	15	18	21
D	18	15	17

出租车公司希望最大限度地减少司机行驶的总距离。为这个分配问题找到一个最优解。

解决方案
首先，必须添加一个虚拟列，以便将此问题变为“平衡”问题。将此列称为“行 4”。由于实际上没有第四位客户，因此该矩阵中的所有成本都将为零。这意味着矩阵中原本最昂贵的出租车将被分配给虚拟的 - 换句话说，它不会在问题中使用。
首先，让我们执行行和列减少

带有行最小值的成本矩阵
1 2 3 4 行最小值

A 11 19 17 0 0

C 15 18 21 0 0

D 18 15 17 0 0

... 带有列最小值
1 2 3 4

A 11 19 17 0

B 21 15 13 0

C 15 18 21 0

D 18 15 17 0

列最小值 11 15 13 0

机会成本矩阵
1 2 3 4

A 0 4 4 0

B 10 0 0 0

C 4 3 8 0

D 7 4 0 0

可以看出，机会成本矩阵中的所有零都只能使用 4 条线划掉（例如，1 条垂直穿过列 4 的线，3 条水平穿过行 A、B 和 D 的线）。因此，我们已经获得了最优解，因为可以使用 4 条线标记整个矩阵。唯一可能的解决方案是

A → 1

B → 3

C → 2

D → 4*

Z = 11 + 13 + 18 = 42

当然，客户 4 实际上是一个“虚拟的” - 也就是说，D 实际上没有运输任何客户。因此，只需要 A、B 和 C 三名司机。司机 A 将运输乘客 1，司机 B 将运输乘客 3，司机 C 将运输乘客 2。

最大化问题

到目前为止，所有考虑过的例子都是最小化问题 - 换句话说，它们的目标是最小化成本。但是，分配问题可以用于相反的目的 - 最大化收益或利润。考虑冰淇淋销售商的例子。他们知道，在某些城镇，他们将比其他城镇卖出更多冰淇淋。同样，一天中也会改变他/她出售的冰淇淋数量 - 他们只在周一、周三和周六（分别为 M、W 和 S）驾驶货车。考虑到冰淇淋货车一次只能访问一个城镇，冰淇淋货车应该在哪一天访问哪个城镇，才能最大化他/她的利润。

以下成本矩阵表示每个城镇（A、B、C）在每一天（M、W、S）的收益（以 100 英镑计）

成本矩阵
	M	W	S
A	10	7	11
B	10	12	12
C	9	13	11

如果按照常规进行行和列的约减，然后得到一个解，那么这个解将给出冰淇淋车能获得的**最小**利润。为了找到**最大**利润，我们首先要找出矩阵中最大的值。在本例中，该值为 13。然后，我们从 13 中减去每个数字，并将新数字分配到原始数字所在的单元格中。换句话说，单元格 A1（当前值为 10）变为 $13-10=3$ .

对整个矩阵完成此过程后，我们将获得以下结果

成本矩阵
	M	W	S
A	3	6	2
B	3	1	1
C	4	0	2

现在我们可以像往常一样进行行和列的约减。最终，这将得到以下机会成本矩阵

机会成本矩阵
	M	W	S
A	0	6	1
B	0	1	0
C	1	0	1

由于可以使用最少 3 条线来划掉矩阵中所有的零（这等于行/列的数量），因此可以进行**最优分配**。唯一可能的分配是

A → M

B → S

C → W

在成本矩阵上，这将给我们

成本矩阵
	M	W	S
A	10*	7	11
B	10	12	12*
C	9	13*	11

这意味着

星期一，货车将访问城镇 A。

星期三，货车将访问城镇 B。

星期六，货车将访问城镇 C。

总利润为

Z=10+12+13=35

因此，冰淇淋车的最大总利润为 3500 英镑。