[問題] 最低運輸費用

[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頁。



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.254.139.87
→ cj6u40:這題我自己看解答都不太懂……Orz
推 allen65535:我湊出運費可以壓到790不知道對不對                    07/11 13:37
→ wxtab019:A7→Q A2→S B3→P B3→R C2→6 C6→S 共790英鎊?         07/11 13:37
→ wxtab019:                     C2→P
竟然把馬上被破解了！究竟是怎麼算的XD
→ stimim:可以用 max flow 或匈牙利演算法
願聞其詳(′‧ω‧‵)
推 allen65535:我是先挑最便宜的20和兩個30塞滿，剩下的就統統去S
→ allen65535:然後從B到S的3輛要80很貴，所以找A或C交換來取代
→ allen65535:結果是用C取代會比較省一點，就這樣
→ allen65535:剩下最貴的是50，可是找不到用20或30或40取代的方法了
有點理解了……

※ 編輯: cj6u40          來自: 111.254.139.87       (07/11 14:33)