商人与萝卜问题.doc

一道智力测试题的线性规划解法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公里处放下664根，空载回起点，再驮1000根胡萝卜至333公里处，带上第一趟留下的333根（还剩334根），行至833公里处，此时驴背上还剩下500根,全部放下，空载回去，驮上最后剩下的1000根，行至333公里处带上第一趟留下的333根（还有一根浪费），行至833公里处，带上第二趟留下的500根，一直行至终点，带到终点的胡萝卜数是833根。多数人认为833根应该是商人能卖出的最大数量（如果可以有小数，应该为833.33），从优化理论的角度来讲，833被认为是该问题的最优解，现在的问题是：833真的是该问题的最优解吗？如果是，如何证明？2、问题分析由已知条件，我们可以知道：（1）由于驴每次只能驮1000根胡萝卜，3000根胡萝卜至少要分成三趟运输，而且只能分成三趟运输（即每次从起点出发均驮上1000根），才能保证商人尽量多卖出胡萝卜。（2）前面两趟运输时，必定要在途中卸载部分胡萝卜，然后空载返回，否则胡萝卜将全部被驴吃掉，商人一根也卖不了。ABST图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;x11000;x21000;x31000-x1;x3x1;x41000-x1-x3;x4x1;x51000-x2+x3;x5x2-x4;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;x11000;x21000;x31000-2*x1;x3x1;x61000-2*x2+x3+x7;x6 1000+x3-x2-(x2-x1);x71000-2*x1-x3;x72*x2-x1-x3+x6;x41000-2*x1-x3-x7;x4x1;x5x6;x5x2-x4;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根胡萝卜返回，留下3