※ 引述《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 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 60.250.111.124 ※ 编辑: stimim 来自: 60.250.111.124 (07/12 12:26)