商人与萝卜问题

中年使者 范文 工作总结范文
精选回答

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

笑我一世沉沦 2022-07-08 19:18:52

相关推荐

zinc (electro)plating

zinc(electro)plating汉语翻译:【化】电镀锌...
展开详情

benzo brilliant orange gr

benzobrilliantorangegr汉语翻译:【建】苯并亮橙GR...
展开详情

kleene hierarchy

kleenehierarchy汉语翻译:【计】克林分层...
展开详情

cosmos

cosmos汉语翻译:n.宇宙,秩序,和谐,*斯菊【医】*斯菊词意辨析:space,universe,cosmos这些名词均含“宇宙,太空”之意。space:指大气层或太阳系之外的极高的天空,即太空之意。uni...
展开详情

air fuel ratio

airfuelratio汉语翻译:【机】混合比...
展开详情

精选推荐更多>

最早提出科学家一词的人是

最早提出“科学家”一词的人是费米尔,1840年,费米尔在一次演讲时说:“在科学领域里孜孜不倦的耕耘者,我们需要给他们一个适当的名称,我想称呼他们为科学家。”科学家这个词在拉丁文中是scien,即了解的意思。
科学家精神是胸怀祖国、服务人民的爱国精神,敢为人先的创新精神,严谨治学的求实精神,淡泊名利、潜心研究的奉献精神,集智攻关、团结协作的协同精神,甘为人梯、奖掖后学的育人精神。新中国成立以来,广大科技工作者在祖国大地上树立起一座座科技创新的丰碑,也铸就了独特的精神气质。

语文120分多少分及格

120分的卷子72分及格,不及格为72分以下,优秀为108~120分。卷子是一些纸张或电子版的答题卷或问题卷,在纸张或电子版上印有考试组织者为检测接受考试者学习情况而设定的并规定在一定时间内必须完成的试题。
考试萌发于南北朝时期,随着士族门阀的衰落和庶族地主的兴起,魏晋以来选官注重门第的九品中正制已无法继续下去。隋文帝即位以后,废除九品中正制。据史载,开皇三年正月,隋文帝曾下诏举“贤良”。应为开皇七年,又令京官五品以上,总管、刺史,以“志行修谨”“清平干济”二科举人。隋炀帝大业三年四月,诏令文武官员有职事者,可以“孝悌有闻”“德行敦厚”“结义可称”“操履清洁”“强毅正直”“执宪不饶”“学业优敏”“文才秀美”“才堪将略”“膂力骄壮”等10科举人。进士二科,并以“试策”取士。

刮的部首是立刀还是舌

“刮”的部首是立刀。立刀,读音为lì dāo,是汉语词语,意思是汉字楷书偏旁“刂”的称呼。立刀旁又称为利刀旁。
立刀旁的书写是竖、竖勾,行书写法是落笔斜写左短竖,再折笔向右上勾挑,然后顺势写右竖勾。立刀旁,右边不是竖,是竖勾。
刮,汉语常用字,读作guā,最早见于说文小篆,即《说文解字》:“掊把也。从刀聲。古八切”。从刀、从舌。本义为用刀刃去掉物体表面的东西,引申指“掠夺财物”,“在物体表面上涂抹”,用作姓。

鸟表达了作者的什么思想

《鸟》表达了作者爱鸟、鸟的喜、鸟的悲、鸟的生、鸟的死,无不牵动着作者的情思。作者这种对鸟的生存和命运的情思,寄托着作者对无拘无束生活的向往和对囚笼般的现实的不满。
《鸟》是中国近代著名文学家、散文家、学者、文学批评家、翻译家梁实秋的散文,文章以典雅生动的语言描写了鸟的美,也记述了各种不同的鸟给自己带来的感受,字里行间蕴含着作者对自然、对人生的体味与理解。
梁实秋(1903年1月6日—1987年11月3日),浙江省杭县(今杭州)人,出生于北京,原名梁治华,字实秋,笔名子佳、秋郎、程淑等。中国现当代散文家、学者、文学批评家、翻译家。1923年8月赴美留学,并取得哈佛大学文学硕士学位。1926年回国后,先后任教于国立东南大学(1928年更名为国立中央大学,1949年更名为南京大学)、国立青岛大学(今中国海洋大学、山东大学共同前身)并任外文系主任。1949年到台湾,任台湾师范大学英语系主任、所长、文学院院长。1987年11月3日,梁实秋病逝于台北,享年84岁。