作者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)