商人与萝卜问题
商人与萝卜问题本文简介:一道智力测试题的线性规划解法1、问题描述网上流传一道被称为小学6年级奥数竞赛的智力测试趣题:一个商人骑一头驴,穿越1000公里长的沙漠,去卖3000根胡萝卜。已知:驴一次性可驮1000根胡萝卜,但每走一公里又要吃掉一根胡萝卜,而空载时不需吃胡萝卜。问:商人最多可卖出多少根胡萝卜?不考虑实际情况中可能
商人与萝卜问题本文内容:
一道智力测试题的线性规划解法
1、问题描述
网上流传一道被称为小学6年级奥数竞赛的智力测试趣题:
一个商人骑一头驴,穿越1000公里长的沙漠,去卖3000根胡萝卜。已知:驴一次性可驮1000根胡萝卜,但每走一公里又要吃掉一根胡萝卜,而空载时不需吃胡萝卜。问:商人最多可卖出多少根胡萝卜?
不考虑实际情况中可能会出现的各种问题,仅在理想的环境下,网友给出了以下三种版本的回答:
版本一:最多能卖出500根,具体方案——分三趟运输,第一趟驮1000根,行至500公里处放下500根,空载回起点,再驮1000根胡萝卜至500公里处,带上第一趟留下的500根,一直走到终点,剩500根出售,再回去驮1000根,剩0根出售(也可不回去驮第三趟),总共最多可出售500根。
版本二:最多能卖出750根,具体方案——分三趟运输,第一趟驮1000根,行至500公里处放下500根,空载回起点,再驮1000根胡萝卜至500公里处,带上第一趟留下的500根,行至750公里处,此时驴背上还剩下750根,全部放下,空载回到起点,驮上最后剩下的1000根,行至750公里处带上第二趟留下的750根,一直行至终点,带到终点的胡萝卜数是750根。
版本三:最多能卖出833根,具体方案——分三趟运输,第一趟驮1000根,行至333公里处放下6***根,空载回起点,再驮1000根胡萝卜至333公里处,带上第一趟留下的333根(还剩334根),行至833公里处,此时驴背上还剩下500根,全部放下,空载回去,驮上最后剩下的1000根,行至333公里处带上第一趟留下的333根(还有一根浪费),行至833公里处,带上第二趟留下的500根,一直行至终点,带到终点的胡萝卜数是833根。
多数人认为833根应该是商人能卖出的最大数量(如果可以有小数,应该为833.33),从优化理论的角度来讲,833被认为是该问题的最优解,现在的问题是:833真的是该问题的最优解吗?如果是,如何证明?
2、问题分析
由已知条件,我们可以知道:
(1)由于驴每次只能驮1000根胡萝卜,3000根胡萝卜至少要分成三趟运输,而且只能分成三趟运输(即每次从起点出发均驮上1000根),才能保证商人尽量多卖出胡萝卜。
(2)前面两趟运输时,必定要在途中卸载部分胡萝卜,然后空载返回,否则胡萝卜将全部被驴吃掉,商人一根也卖不了。
A
B
S
T
图1
(3)第一趟运输时,其卸载点可以只有一个。为什么?假设有两个卸载点A、B(如图1),由于以后各趟都是满载从起点S出发,到达A点时,驴只吃掉了根胡萝卜,此时最多只能再加上根胡萝卜,到B点后最多能再加根,实际上这与在B点直接加根是等效的,即第一趟中只需设B点为卸载点。
(4)同理,第二趟在中途也只需设一个卸载点,无防假设第二趟的卸载点在第一趟卸载点的右边。
(5)第三趟运输时,在经过前两趟的卸载点时尽量带上留下的胡萝卜,一直行至终点。
综合以上分析,可以知道最优运输模式如下:
分三趟运输:
第一趟:如图1,驮上1000根从S点出发,到达A点时返回,留下剩下的根胡萝卜;
第二趟:驮上1000根从S点出发,途经A点时加上根(且),再行走至B点处返回,留下剩下的()根胡萝卜;
第三趟:驮上1000根从S点出发,途经A点时加上根(且),再行走至B点处加上根(且),一直行至终点T。
最终能够驮到终点T的胡萝卜数是()根,这也是商人最多能卖出的胡萝卜数。
3、建立模型
由以上分析,可得该问题的线性规划模型为:
4、模型求解
使用Lingo软件求解该线性规划问题,在Lingo中输入模型:
Model:
max=x4+x5;
x1<1000;
x2<1000;
x3<1000-x1;
x3 x4<1000-x1-x3; x4 x5<1000-x2+x3; x5 @gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5); end 运行结果如下: Global optimal solution found. Objective value: 833.0000 Extended solver steps: 0 Total solver iterations: 5 Variable Value Reduced Cost X4 333.0000 -1.000000 X5 500.0000 -1.000000 X1 333.0000 0.000000 X2 833.0000 0.000000 X3 333.0000 0.000000 Row Slack or Surplus Dual Price 1 833.0000 1.000000 2 667.0000 0.000000 3 167.0000 0.000000 4 334.0000 0.000000 5 0.000000 0.000000 6 1.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 通过对模型的求解,我们可以知道最优运输模式为: 分三趟运输: 第一趟:驮上1000根从起点出发,到达333公里处返回,留下剩下的667根胡萝卜; 第二趟:驮上1000根从起点出发,到达333公里处加上333根,再行走至833公里处返回,留下剩下的500根胡萝卜; 第三趟:驮上1000根从起点出发,到达333公里处加上333根(还剩1根浪费),再行走至833公里处加上500根,一直行至终点。 最终能够驮到终点T的胡萝卜数是833根,这也是商人最多能卖出的胡萝卜数。 至此我们已经证明了833是该问题的最优解,即在已知条件下,商人最多能卖出833根胡萝卜。 5、问题拓展 如果将问题稍作修改:将“空载时不需吃胡萝卜”改为“空载时也需吃胡萝卜”。问:商人最多可卖出多少根胡萝卜? 类似前面的分析,我们可以知道此时的最优运输模式为: 分三趟运输: 第一趟:如图1,驮上1000根从S点出发,到达A点时带上根胡萝卜返回,留下剩下的根; 第二趟:驮上1000根从S点出发,途经A点时加上根(且),再行至B点时返回,留下根,返回S点的途中经过A点时带上根(,,,); 第三趟:驮上1000根从S点出发,途经A点时加上根(且),再行走至B点处加上根(且),一直行至终点T。 最终能够驮到终点T的胡萝卜数是()根,这也是商人最多能卖出的胡萝卜数。 由以上分析,可得此种情况下的线性规划模型为: 使用Lingo软件求解该线性规划问题,在Lingo中输入模型: Model: max=x4+x5; x1<1000; x2<1000; x3<1000-2*x1; x3 x6<1000-2*x2+x3+x7; x6 <1000+x3-x2-(x2-x1); x7<1000-2*x1-x3; x7<2*x2-x1-x3+x6; x4<1000-2*x1-x3-x7; x4 x5 x5 @gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7); end 运行结果为: Global optimal solution found. Objective value: 533.0000 Extended solver steps: 0 Total solver iterations: 26 Variable Value Reduced Cost X4 200.0000 -1.000000 X5 333.0000 -1.000000 X1 200.0000 0.000000 X2 533.0000 0.000000 X3 200.0000 0.000000 X6 333.0000 0.000000 X7 200.0000 0.000000 Row Slack or Surplus Dual Price 1 533.0000 1.000000 2 800.0000 0.000000 3 467.0000 0.000000 4 400.0000 0.000000 5 0.000000 0.000000 6 1.000000 0.000000 7 1.000000 0.000000 8 200.0000 0.000000 9 799.0000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 0.000000 0.000000 13 0.000000 0.000000 由模型结果可知道此时的最优运输模式为: 分三趟运输: 第一趟:驮上1000根从起点出发,到达200公里处带上200根胡萝卜返回,留下剩下的600根; 第二趟:驮上1000根从起点出发,途经200公里处加上200根,再行至533公里处时带上333根胡萝卜返回,留下334根,返回到起点的途中经过200公里处时带上200根返回到起点; 第三趟:驮上1000根从S点出发,途经200公里处加上200根,再行走至533公里处加上333根(剩余1根浪费),一直行至终点。 最终能够驮到终点T的胡萝卜数是533根,这也是商人最多能卖出的胡萝卜数。 至此我们也证明了:当空载时也要吃胡萝卜时,533是该问题的最优解,即在此条件下,商人最多能卖出533根胡萝卜。