最低運輸費用 - 拼圖

Table of Contents

  最低運輸費用 
┌─────────────────────────────────────┐
◎Question                                │
│ 「易上路」是一家全國性的汽車租借公司,在各地主要有七個租借中心。以下是 │
│ 七處目前所有的車輛過剩或不足情形:      ┌─┬─┬─┬─┬─┐  │
│ A過剩9輛、B過剩6輛、C過剩8輛;       │ │P│Q│R│S│  │
│ P不足5輛、Q不足7輛、R不足3輛、S不足8輛。 ├─┼─┼─┼─┼─┤  │
│                        │A│60│20│50│40│  │
│ 為了達成供需平衡,現在公司決定重新布局,以過 ├─┼─┼─┼─┼─┤  │
│ 剩的車輛填補不足的部分。而各地之間一輛車的運 │B│40│50│30│80│  │
│ 輸了費用如右表所列,如A→P需要60英鎊。   ├─┼─┼─┼─┼─┤  │
│ 欲使運費最低,公司應如何安排?此時運費為何? │C│30│40│70│50│  │
│                        └─┴─┴─┴─┴─┘  │
◎Answer                       (單位:英鎊)   │
│ 答案請開燈:790元                            │
└─────────────────────────────────────┘
 ※題目出處:《數學遊樂園之妙想天開》(牛頓,2002)第64、65、135、136頁。



--

All Comments

Connor avatarConnor2012-07-13
這題我自己看解答都不太懂……Orz
Ursula avatarUrsula2012-07-14
C2→P
Jacky avatarJacky2012-07-16
可以用 max flow 或匈牙利演算法
Jacky avatarJacky2012-07-20
我是先挑最便宜的20和兩個30塞滿,剩下的就統統去S
William avatarWilliam2012-07-23
然後從B到S的3輛要80很貴,所以找A或C交換來取代
Lydia avatarLydia2012-07-23
結果是用C取代會比較省一點,就這樣
James avatarJames2012-07-23
剩下最貴的是50,可是找不到用20或30或40取代的方法了