作者cj6u40 (阿克 \⊙▽⊙/)
看板puzzle
標題[問題] 最低運輸費用
時間Wed Jul 11 13:14:53 2012
最低運輸費用
┌─────────────────────────────────────┐
│
◎Ｑ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頁。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.139.87
1F：→ cj6u40:這題我自己看解答都不太懂……Orz 07/11 13:17
推 allen65535:我湊出運費可以壓到790不知道對不對 07/11 13:37
→ wxtab019:A7→Q A2→S B3→P B3→R C2→6 C6→S 共790英鎊? 07/11 13:37
2F：→ wxtab019: C2→P 07/11 13:38
竟然把馬上被破解了！究竟是怎麼算的XD
3F：→ stimim:可以用 max flow 或匈牙利演算法 07/11 13:51
願聞其詳(′‧ω‧‵)
4F：推 allen65535:我是先挑最便宜的20和兩個30塞滿，剩下的就統統去S 07/11 14:07
5F：→ allen65535:然後從B到S的3輛要80很貴，所以找A或C交換來取代 07/11 14:08
6F：→ allen65535:結果是用C取代會比較省一點，就這樣 07/11 14:09
7F：→ allen65535:剩下最貴的是50，可是找不到用20或30或40取代的方法了 07/11 14:10
有點理解了……
※ 編輯: cj6u40 來自: 111.254.139.87 (07/11 14:33)