最低運輸費用 - 拼圖

※ 引述《cj6u40 (阿克 \⊙▽⊙/)》之銘言：
　　最低運輸費用　
┌─────────────────────────────────────┐
│◎Ｑuestion　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 │
│　「易上路」是一家全國性的汽車租借公司，在各地主要有七個租借中心。以下是　│
│　七處目前所有的車輛過剩或不足情形：　　　　　　┌─┬─┬─┬─┬─┐　　│
│　Ａ過剩9輛、Ｂ過剩6輛、Ｃ過剩8輛；　　　　　　 │　│Ｐ│Ｑ│Ｒ│Ｓ│　　│
│　Ｐ不足5輛、Ｑ不足7輛、Ｒ不足3輛、Ｓ不足8輛。　├─┼─┼─┼─┼─┤　　│
│　　　　　　　　　　　　　　　　　　　　　　　　│Ａ│60│20│50│40│　　│
│　為了達成供需平衡，現在公司決定重新布局，以過　├─┼─┼─┼─┼─┤　　│
│　剩的車輛填補不足的部分。而各地之間一輛車的運　│Ｂ│40│50│30│80│　　│
│　輸了費用如右表所列，如Ａ→Ｐ需要60英鎊。　　　├─┼─┼─┼─┼─┤　　│
│　欲使運費最低，公司應如何安排？此時運費為何？　│Ｃ│30│40│70│50│　　│
│　　　　　　　　　　　　　　　　　　　　　　　　└─┴─┴─┴─┴─┘　　│
│◎Ａnswer　　　　　　　　　　　　　　　　　　　　　　　（單位：英鎊）　　 │
│　答案請開燈：790元　　　　　　　　　　　　　　　　　　　　　　　　　　　 │
└─────────────────────────────────────┘
　※題目出處：《數學遊樂園之妙想天開》（牛頓，2002）第64、65、135、136頁。


上一篇說的是原理，現在則是實際的解一次看看，因為 cost 都是 10 的倍數，

所以在下面的過程中，都直接用 cost/10 來算。

和剛剛不一樣的是，X = {A, B, C}, Y = {P, Q, R, S} 的車輛狀況都不是多或少一輛，

理論上我們要把他們變成 23 * 23 的表格來解，可是這裡面有很多重複的東西，

所以，我們只有在必要的時候才把 X 和 Y 更細分。

一開始的表格變這樣

5P(3) 7Q(2) 3R(3) 8S(4)
9A(0) 3 0 2 0
6B(0) 1 3 0 4
8C(0) 0 2 4 1

數字代表的是那一個行或列其實有數台車，

在匹配的時候，比如說，CP 可以產生配對，可是只有 5 對，有 3 個 C 會剩下，

所以我們要把 C 分成 5C 和 3C 兩列。並用 0 代表被匹配的 0

5P(3) 7Q(2) 3R(3) 2S(4) 6S(4)
7A(0) 3 0 2 0 0
2A(0) 3 0 2 0 0
3B(0) 1 3 0 4 4
3B(0) 1 3 0 4 4
5C(0) 0 2 4 1 1
3C(0) 0 2 4 1 1

可以發現並沒有完美匹配 (我們只匹配了 5 + 7 + 3 + 2 = 17 個 0) ，

所以要找出 Z ， (事實上，會有 |Z| = 17 也就是剛剛被匹配的 0 的個數)

結果是：

5P(3) 7Q(2) 3R(3) 2S(4) 6S(4)
7A(0) 3 0 2 0 0
2A(0) 3 0 2 0 0
3B(0) 1 3 0 4 4
3B(0) 1 3 0 4 4
5C(0) 0 2 4 1 1
3C(0) 0 2 4 1 1

Z = {7A(0), 2A(0), 5P(3), 3R(3)} |Z| = 7 + 2 + 5 + 3 = 17

e = 1

現在要更新表格：

5P(3) 7Q(3) 3R(3) 2S(5) 6S(5)
7A(-1) 4 0 3 0 0
2A(-1) 4 0 3 0 0
3B( 0) 1 2 0 3 3
3B( 0) 1 2 0 3 3
5C( 0) 0 1 4 0 0
3C( 0) 0 1 4 0 0

尋找匹配：

5P(3) 7Q(3) 3R(3) 2S(5) 3S(5) 3S(5)
7A(-1) 4 0 3 0 0 0
2A(-1) 4 0 3 0 0 0
3B( 0) 1 2 0 3 3 3
3B( 0) 1 2 0 3 3 3
5C( 0) 0 1 4 0 0 0
3C( 0) 0 1 4 0 0 0

被匹配的 0 有 5 + 7 + 3 + 2 + 3 = 20 個

5P(3) 7Q(3) 3R(3) 2S(5) 3S(5) 3S(5)
7A(-1) 4 0 3 0 0 0
2A(-1) 4 0 3 0 0 0
3B( 0) 1 2 0 3 3 3
3B( 0) 1 2 0 3 3 3
5C( 0) 0 1 4 0 0 0
3C( 0) 0 1 4 0 0 0

Z = {7A, 2A, 3C, 5C, 3R} |Z| = 20

e = 1

更新表格：

3P(4) 2P(4) 7Q(4) 3R(3) 2S(6) 6S(6)
7A(-2) 4 4 0 4 0 0
2A(-2) 4 4 0 4 0 0
3B( 0) 0 0 1 0 2 2
3B( 0) 0 0 1 0 2 2
2C(-1) 0 0 1 5 0 0
6C(-1) 0 0 1 5 0 0

匹配完成， 3 B->P, 2 C->P, 7 A->Q, 3 B->R, 2 A->S, 6 C->S

花費為 (4*5 + 7*4 + 3*3 + 8*6 + 9*(-2) + 6*(0) + 8*(-1)) * 10 = 790



--