《钢管下料问题.doc》由会员分享，可在线阅读，更多相关《钢管下料问题.doc（4页珍藏版）》请在三一文库上搜索。
1、人、猫、鸡、米安全过河问题一：摘要人、猫、鸡、米安全过河问题二：关键词 人、猫、鸡、米 安全过河 次数少三：问题的重述人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个安全过河方案，并使渡河次数尽量地少。四：基本假设与符号说明由于这个虚拟的问题已经理想化了，所以不必作假设。符号说明：1,2,3,4分别表示人、猫、鸡、米 0表示没有 =1 表示i在此岸=0 表示i在对岸 表示在此岸的状态 表示在对岸的状态 表示第K次渡河前此岸的状态C= 表示船上的状态 表示i在船上 表示i不在船上 表示第K次船上的状态五：问题的分析安全过河问题可以看
2、着是一个多部决策的过程。每作出一步决策，都必须保证船、人、猫、鸡、米能满足题设条件。否则，不仅难以实现过河的最优化，而且还容易出现事物的不安全性。因此，在保证安全的前提下，即猫、鸡在一起时，人要在场，鸡、米在一起时，人也要在场，用状态变量s表示某一岸的状况，决策变量C示是乘船方案 ，我们容易得到S和C的关系，其中问题的转化要在允许变化范围内，确定每一步的决策关系，从而达到渡河的最优目标。六：模型的建立 人、猫、鸡、米分别记为，引入01变量（），=1 表示i在此岸，=0 表示i在对岸，则此岸的状态可用表示，对岸的状态可用表示。S的允许状态有：决策为乘船方案，记作，当在船上时记，否则记，C的允许状
3、态有：记第次渡河前此岸的状态为，第次船上的状态为 ，则状态转移律为设计安全过河方案可变为求决策序列，使状态，使状态转移律由初始状态经步达到。七：模型的求解S（1,1,1,1）C（1,0,1,0） S C S C S C S C S C S C S 因此，该问题的最优方案是：1、人先带鸡过河，然后人再回来，把米带过河，然后把米留在对岸并把鸡运回河岸，人再把猫带过河，最后人回来把鸡带过去。八：模型的评价与推广（）优点：1、模型简单，与实际相结合，更益理解；2、结合实际情况对问题进行求解，使得模型具有很好的通用性和推广性；（）缺点：由于问题的求解没有使用LINGO或MATLAB软件，当状态和决策过多
4、时，采用上述方法求解显得繁琐，容易出错。（）推广：正如课本上的商人们安全过河问题，当商人和随从人数增加或小船的容量加大时，靠逻辑思考就有些困难了，而设置适当地状态和决策变量，确定状态转移率，建立多步决策模型，并可通过适当的图表，形象的表达各个变量间的关系，方便有效地求解此类型问题。九：参考文献【1】 杨启帆，边馥萍. 数学建模. 浙江大学出版社，1990【2】 姜启源，谢金星，叶俊. 数学建模. 第三版.北京：高等教育出版社，2003【3】 百度文摘Global optimal solution found. Objective value: 820.0000 Extended solver
5、steps: 0 Total solver iterations: 22 Variable Value Reduced Cost X 7.000000 100.0000 Y1 0.000000 40.00000 Y2 0.000000 40.00000 Y3 0.000000 40.00000 Y4 2.000000 40.00000 Y5 1.000000 40.00000 Y6 0.000000 40.00000 Y7 0.000000 40.00000 Y8 0.000000 40.00000 X4 5.000000 0.000000 X5 2.000000 0.000000 Row S
6、lack or Surplus Dual Price 1 820.0000 -1.000000 2 3.000000 0.000000 3 4.000000 0.000000 4 3.000000 0.000000 5 1.000000 0.000000 6 0.000000 0.000000 7 4.000000 0.000000 8 2.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000min=100*x+40*y1+40*y2+40*y3+40*y4+40*y5+40*y6+40*y7+40*y8;x+y1=4;x+y1+y2=3;x+y1+y2+y3=4;x4+y1+y2+y3+y4=6;x5+y2+y3+y4+y5=5;x+y3+y4+y5+y6=6;x+y4+y5+y6+y7=8;x+y5+y6+y7+y8=8;y1+y2+y3+y4+y5+y6+y7+y8=3;x4+x5=x;gin (x);gin (x4);gin (x5);gin (y1);gin (y2);gin (y3);gin (y4);gin (y5);gin (y6);gin (y7);gin (y8);