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 英鎊。