指派問題的特殊解法

一、匈牙利法

範例：

有四位教授被分派開設四門課程，如何指派使所需的總準備時間為最小。已知個人對各課程之準備時間如下表所示：

	課程1	課程2	課程3	課程4
教授A	2	10	9	7
教授B	15	4	14	8
教授C	13	14	16	11
教授D	4	15	13	9

解法：

Step 1. 在各列中找最小值，將該列中各元素檢去此值，對各行重複一次。

0	8	7	5	本列各減2
11	0	10	4	本列各減4
2	3	5	0	本列各減11
0	11	9	5	本列各減4

0	8	2	5
11	0	5	4
2	3	0	0
0	11	4	5
本欄各減0	本欄各減0	本欄各減5	本欄各減0

Step 2. 檢驗各列，對碰上之第一個零，做記號，同列或同欄的其他零則畫X (由零較少的列先做，可不依順序)

0	8	2	5
11	0	5	4
2	3	0	0
0	11	4	5

Step 3. 檢驗可否完成僅含零的完全指派，若不能，則畫出最少數目的垂直與水平的刪除線來包含所有的零至少一次。

0	8	2	5
11	0	5	4
2	3	0	0
0	11	4	5

Step 4. 找出未被畫線的元素中之最小值 K，將含有此些未被畫線的元素的各列所有元素減去K (Step 4.1)，若造成負值，則將該欄加上K (Step 4.2)。形成新矩陣後回到Step 2.

Step 4.1

-2	6	0	3
11	0	5	4
2	3	0	0
-2	9	2	3

Step 4.2

0	6	0	3
13	0	5	4
4	3	0	0
0	9	2	3

形成新矩陣

Step 2.

0	6	0	3
13	0	5	4
4	3	0	0
0	9	2	3

由上表知，指派順序為 (2,2), (4,1), (1,3), (3,4)，可得到完全指派。

	課程1	課程2	課程3	課程4
教授A			9
教授B		4
教授C				11
教授D	4

總準備時間為 9+4+11+4 = 28 為最佳解。

二、分支定界法 (Branch and Bound Technique)

分支定界法是在有限個可行解中作有系統的搜尋以求得最佳解的一種技術，做法是將所有可行解分成小的部分集合(分支)，解每個部分集合求得之最小值為所有可行解之界 (Bound)，每個分支可再進一步做分支。

指派問題之分支定界法：

	工作1	工作2	工作3	工作4
人員A	2	10	9	7
人員B	15	4	14	8
人員C	13	14	16	11
人員D	4	15	13	9

上題中的可行解個數有4！=24個。

在指派問題中每人只能指派一項工作，暫時不考慮此限制。

做法：

step 1: 求各行做計算求最小總時間與指派方法

Node 1	工作1	工作2	工作3	工作4	總計時間
最小時間	2	4	9	7	22
指派人員	A	B	A	A	Not yet

在此，22為所有可行解的下限。

Step 2: 檢驗是否已得完全指派，若可得完全指派，則其值為可行解的一個上限。若否 (如上表右下角標註Not yet)，固定一個指派，刪除該指派所對應的時間表，回step 1，計算完後找出總計時間為最小者。

在指定A做工作1之後，表中第一列的數據在後續即不考慮。

Node 2	工作1	工作2	工作3	工作4	總計時間
	2	4	13	8	27
指派人員	指定A	B	D	B	Not yet

在指定B做工作1之後，表中第二列的數據在後續即不考慮。

Node 3	工作1	工作2	工作3	工作4	總計時間
	15	10	9	7	41
指派人員	指定B	A	A	A	Not yet

在指定C做工作1之後，表中第三列的數據在後續即不考慮。

Node 4	工作1	工作2	工作3	工作4	總計時間
	13	4	9	7	33
指派人員	指定C	B	A	A	Not yet

在指定D做工作1之後，表中第四列的數據在後續即不考慮。

Node 5	工作1	工作2	工作3	工作4	總計時間
	4	4	9	7	24
指派人員	指定D	B	A	A	Not yet

Node 2 至 Node 5 中以Node 5 為最小，在此，24為新的下限。由此處繼續。

Step 3: 固定下一個指派，刪除該指派所對應的時間表，回step 1，計算完後找出總計時間為最小者。

Node 6	工作1	工作2	工作3	工作4	總計時間
	4	10	14	8	36
指派人員	指定D	指定A	B	B	Not yet

Node 7	工作1	工作2	工作3	工作4	總計時間
	4	4	9	7	24
指派人員	指定D	指定B	A	A	Not yet

Node 8	工作1	工作2	工作3	工作4	總計時間
	4	14	9	7	34
指派人員	指定D	指定C	A	A	Not yet

Node 6 至 Node 8 中以Node 7 為最小，在此，24為新的下限。由此處繼續。

Step 4:

Node 9	工作1	工作2	工作3	工作4	總計時間
	4	4	9	11	28
指派人員	指定D	指定B	指定A	C	Yes

Node 10	工作1	工作2	工作3	工作4	總計時間
	4	4	16	7	31
指派人員	指定D	指定B	指定C	A	Yes

Node 9與10均符合完全指派，較小值28為所有可行解的上界 (Upper Bound)。任何Node 之值大於28者均可忽略。

Step 5: 不考慮自身之所出，由其他分支之Node檢驗是否有低於28之值，Node 2,3,4,6,8,10中只有Node 2 低於28，予以進一步分支。

Node 11	工作1	工作2	工作3	工作4	總計時間
	2	4	13	9	28
指派人員	指定A	指定B	D	D	Not yet

Node 12	工作1	工作2	工作3	工作4	總計時間
	2	14	13	8	37
指派人員	指定A	指定C	D	B	Yes

Node 13	工作1	工作2	工作3	工作4	總計時間
	2	15	14	8	39
指派人員	指定A	指定D	B	B	Not yet

Node 12 為可行解，但其值仍大於Node 9之值，Node 11雖可得值=28，但由此分支下去的也一定>=28，並不會優於Node 9。所以可得知Node 9 為最佳解。

三、結合匈牙利法與分支定界法

求解旅行推銷員問題Traveling Salesman Problem

五個城市間的距離如下表所示，由任一城市出發，要走遍所有城市並回到起始城市，請找出有最短總距離的路線，最短總距離為多少？

	City 1	City 2	City 3	City 4	City 5
City 1	X	1	7	4	3
City 2	2	X	6	3	4
City 3	1	6	X	2	1
City 4	1	5	4	X	6
City 5	7	5	4	5	X

求解：

匈牙利法

各列扣除最小數

X	0	6	3	2
0	X	4	1	2
0	5	X	1	0
0	4	3	X	5
3	1	0	1	X

各行扣除最小數

X	0	6	2	2
0	X	4	0	2
0	5	X	0	0
0	4	3	X	5
3	1	0	0	X

指派零值

X	0	6	2	2
0	X	4	0	2
0	5	X	0	0
0	4	3	X	5
3	1	0	0	X

相對應的路線為 1-2-4-1與 3-5-3，由於指派中的旅行有兩段所以並非最佳解。總距離為10，此值為所有可行解的下限。

分支定界法

由於上述兩段路線中以3-5-3為較短，選取該路線，將原題分支為兩各部分問題，分別強制使 3-5 與 5-3 的值為無限大，繼續以匈牙利法求解。

子題1

X	1	7	4	3
2	X	6	3	4
1	6	X	2	X
1	5	4	X	6
7	5	4	5	X

可求出

X	0	6	2	0
0	X	4	0	0
0	5	X	0	X
0	4	3	X	3
3	1	0	0	X

路線：1-2-5-3-4-1，總距離為12。

子題2

X	1	7	4	3
2	X	6	3	4
1	6	X	2	1
1	5	4	X	6
7	5	X	5	X

可求出

X	0	3	3	2
0	X	1	1	2
0	5	X	1	0
0	4	0	X	5
2	0	X	0	X

路線：1-2-1, 3-5-4-3，總距離為13。

由於子題1的可行解的值比子題2的解還小，所以已有最佳解，不需在由子題2重新分支做下去。若子題2的解小於12，則應強制使 1-2 與 2-1 的值為無限大，繼續以匈牙利法求解。

四、新經驗法則 (New Heuristic Method)

旅行推銷員問題Traveling Salesman Problem

五個城市間的距離如下表所示，由任一城市出發，要走遍所有城市並回到起始城市，請找出有最短總距離的路線，最短總距離為多少？

	City 1	City 2	City 3	City 4	City 5
City 1		42	30	30	25
City 2	42		30	30	18
City 3	30	30		42	25
City 4	30	30	42		18
City 5	25	18	25	18

此題可看成如下問題：

Task 1

Task 2

Task 3

Task 4

Task 5

Assignee 1

Assignee 2

Assignee 3

Assignee 4

Assignee 5

其中Assignee n 不能執行 task n.

使用新經驗法則(New Heuristic Method)求解：

(1,,,,)
X	42	30	30	25
42	X	30	30	18
30	30	X	42	25
30	30	42	X	18
25	18	25	18	X
TermA=0, TermB=580 Expect-cost=580/4+0=145

	(1,2,,,*)						(1,3,,,*)						(1,4,,,*)						(1,5,,,*)
X		42	X	X	X	X		X	30	X	X	X		X	X	30	X	X		X	X	X	25
X		X	30	30	18	42		X	X	30	18	42		X	30	X	18	42		X	30	30	X
30		X	X	42	25	X		30	X	42	25	30		30	X	X	25	30		30	X	42	X
30		X	42	X	18	30		30	X	X	18	X		30	42	X	18	30		30	42	X	X
25		X	25	18	X	25		18	X	18	X	25		18	25	X	X	X		18	25	18	X
	TermA=42,TermB=333 Expect-cost=333/3+42=153						TermA=30,TermB=326 Expect-cost=326/3+30=138.6						TermA=30,TermB=333 Expect-cost=333/3+30=141						TermA=25,TermB=367 Expect-cost=367/3+25=147.3

(1,3,2,*,*)

(1,3,4,*,*)

(1,3,5,*,*)

TermA=60,TermB=139

Expect-cost=139/2+60=129.5

TermA=72,TermB=151

Expect-cost=151/2+72=147.5

TermA=55,TermB=168

Expect-cost=168/2+55=139

(1,3,2,4,*)

(1,3,2,5,*)

TermA=90,TermB=43

Expect-cost=43/1+90=133

TermA=78,TermB=48

Expect-cost=48/1+78=126

Solution: <1,3,2,5,4,1> is optimal, expected cost is 126