商人与萝卜问题

商人与萝卜问题本文简介：一道智力测试题的线性规划解法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根胡萝卜。