已阅读5页,还剩39页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
初等数学模型,1. 商人安全过河模型 2. 人、狼、羊、菜渡河模型,商人安全过河模型,问题的提出,三名商人各带一个随从乘船渡河,一只小船只能容纳两人,由他们自己划行。 随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货。 如何乘船渡河的大权掌握在商人们手中, 商人们怎样才能安全渡河呢?,数模求解的意义,对于这类智力游戏,经过一番逻辑思索是可以找出解决办法的。 这里用数学模型求解, 一是为了给出建模的示例, 二是因为这类模型可以解决相当广泛的一类问题,比逻辑思索的结果容易推广。,问题分析:,由于这个虚拟的问题己经理想化了,所以不必再作假设。 安全渡河问题可以视为多步决策过程。每一步,即船由此岸驶向彼岸或从彼岸驶回此岸,都要对船上的人员(商人、随从各几人)作出决策 在保证安全的前提下(两岸的商人数都不比随从数少),在有限步内使人员全部过河。,变量的确定,用状态(变量)表示某一岸的人员状况,决策(变量)表示船上的人员状况,可以找出状态随决策变化的规律。 问题转化为在状态的允许变化范围内(即安全渡河条件),确定每一步决策,达到渡河目标。,模型构成,记第k次渡河前此岸的商人数为xk,随从数为yk,k=l,2,xk,yk=0,1,2,3。 将二维向量sk=(xk,yk)定义为状态 安全渡河条件下的状态集合称为允许状态集合,记作S。不难写出 S=(x,y)|x=0, y= 0,1,2,3; x=3, y=0,1,2,3; x=y=1,2 (1),状态sk随决策d k变化的规律,记第k次渡船上商人数为u k,随从数为v k 将二维向量dk=(uk,vk)定义为决策.允许决策集合记作D,由小船的容量可知 D=(u,u)|u+v=l,2 (2) 因为k为奇数时船从此岸驶向彼岸,k为偶数时船由彼岸驶回此岸,所以状态sk随决策d k变化的规律是 s k+1= s k +(-1)kd k (3) (3)式称状态转移律。,商人安全过河的数学模型 (多步决策模型):,求决策d kD(k=1,2,,n), 使状态s k S按照转移律(3): s k+1= s k +(-1)kd k 由初始状态s 1=(3,3)经有限步n到达 状态s n+1=(0,0)。,由状态(3,3)经n(奇数)步决策 转移到(0,0)的转移过程,具体转移步骤如下: (0,1) (3,2) (0,2) (3,1) (3,3) + (-1)1 (1,1) (2,2) (1,0) (2,3) (2,0) (1,3) 再将(3,2),(3,1),(2,2)分别与决策向量进行运算。如此下去,不难验证,经过11次决策可取运算后即可完成。 当k为奇数时,dk表示从此岸到彼岸,当k为偶数时,表示从彼岸回到此岸。,模型求解,根据(1)-(3)式编一段程序,用计算机求解上述多步决策问题是可行的。 对于商人和随从人数不大的简单状况,用图解法解这个模型更为方便。,y(随从数) 3 (3,3) o x (商人数) 1 2 3,图1-3 安全渡河问题的图解法(共四种),图解法决策的步骤,在xoy平面坐标系上画出图1-3那样的方格,方格点表示状态s=(x,y)。 允许状态集合S是圆点标出的10个格子点。 允许决策d是沿方格线移动1或2格,k为奇数时向左、下方移动,k为偶数时向右、上方移动。 要确定一系列的d k使由s 1=(3,3)经过那些圆点最终移至原点(0,0)。,课堂(后)数模练习,试在图1-3中给出一种移动方案,即经过决策 d 1,d 2,d n,最终有s n+1=(0,0)。 将该结果翻译成渡河的方案。,评 注,这里介绍的模型是一种规格化的方法,使我们可以用计算机求解,从而具有推广的意义。 譬如当商人和随从人数增加或小船的容量加大时,靠逻辑思考就困难了,而用这种模型则仍可方便地求解。 另外,适当地设置状态和决策,并确定状态转移律,是有效地解决很广泛的一类问题的建模方法,在以后还可能要用到。,人、狼、羊、菜渡河模型,问题的提出,一摆渡人F希望用一条小船把一只狼W,一头羊G和一篮白菜C从一条河的左岸渡到右岸去,而船小只能容纳F、W、G、C中的两个,决不能在无人看守的情况下,留下狼和羊在一起,羊和白菜在一起, 应怎样渡河才能将狼、羊、白菜都运过去? 这是一个有趣的智力游戏问题,显然可用递推方法解决,但我们把此问题化为状态转移问题来解决。,状态向量的表示,将人、狼、羊、菜依次用一个四维向量表示,当一物在左岸时,记相应的分量为1,否则记为0,如A(1,0,1,0)表示人和羊在左岸,并称为一个状态 由问题中的限制条件,有些状态是允许的,有的是不允许的。,凡系统可以允许存在的状态称为可取状态,如A1(1,0,1,0)是可取状态,但A2(0,0,1,1)是一个不可取状态, 此外,把每运载一次也用一个四维向量来表示,如B1(1,1,0,0)表示人和狼在船上,而羊和白菜不在船上,这是可取的运载,因为船可载两物,而B2(1,0,1,1)则是不可取运载 利用穷举法可得到问题的解,穷举法求解,(1)可取(允许)状态A共有10个 (1,1,1,1) (0,0,0,0) (1,1, 1,0) (0,0,0,1) (1,1,0,1) (0,0,1,0) (1,0,1,1) (0,1,0,0) (1,0,1,0) (0,1,0,1) 右边5个正好是左边5个的相反状态 。,可取运载与可取运算,(2)可取运载 B 共有4个 (1,1,0,0) (1,0,1,0) (1,0,0,1) (1,0,0,0) (3)可取运算 :规定A与B相加时对每一分量按二进制法则进行: 0十0= 0,1十 0=1, 0十 1=1,1十 1= 0。 这样 ,一次渡河就是一个可取状态向量与一个可取运载向量相加,可取状态经过加法运算后仍是可取状态 ,这种运算称为可取运算 。,穷举法的数学模型,在上述规定下,问题转化为: 从初始状态 (1,1,1,1)经过多少次(奇数次)可取运算才能转化为状态(0,0,0,0)。 如果一个状态是可取的就打,否则就打,虽然可取但已重复就打,于是问题可用穷举法解答如下:,(1,0,1,0) (0,1,0,1) 1) (1,1,1,1) 十 (1,1,0,0) (0,0,1,1) (1,0,0,1) (0,1,1,0) (1,0,0,0) (0,1,1,1) (1,0,1,0) (1,1,1,1) 2) (0,1,0,1) 十 (1,1,0,0) (1,0,0,1) (1,0,0,1) (1,1,0,0) (1,0,0,0) (1,1,0,1) (1,0,1,0) (0,1,1,1) 3) (1,1,0,1) 十 (1,1,0,0) (0,0,0,1) (1,0,0,1) (0,1,0,1) (1,0,0,0) (0,1,0,1) (1,0,1,0) (1,0,1,1) 4)1 (0,0,0,1) 十 (1,1,0,0) (1,1,0,1) (1,0,0,1) (1,0,0,0) (1,0,0,0) (1,0,0,1) ,(1,0,1,0) (1,1,1,0) 4)2 (0,1,0,0) 十 (1,1,0,0) (1,0,0,0) (1,0,0,1) (1,1,0,1) (1,0,0,0) (1,1,0,0) (1,0,1,0) (0,0,0,1) 5)1 (1,0,1,1) 十 (1,1,0,0) (0,1,1,1) (1,0,0,1) (0,0,1,0) (1,0,0,0) (0,0,1,1) (1,0,1,0) (0,1,0,0) 5)2 (1,1,1,0) 十 (1,1,0,0) (0,0,1,0) (1,0,0,1) (0,1,1,1) (1,0,0,0) (0,1,1,0) (1,0,1,0) (1,0,0,0) 6) (0,0,1,0) 十 (1,1,0,0) (1,1,1,0) (1,0,0,1) (1,0,1,1) (1,0,0,0) (1,0,1,0) ,(1,0,1,0) (0,0,0,0) 7) (1,0,1,0) 十 (1,1,0,0) (0,1,1,0) (1,0,0,1) (0,0,1,1) (1,0,0,0) (0,0,1,0) 第7步 已经出现(0,0,0,0)状态,说明经过7次运载即可,其过程为: 去(人,羊)回(人) 去(人,狼(或菜) 回 (人,羊)去(人,菜(或狼) 回(人) 去(人,羊),评 注,用这种方法的优点易于在计算机上实现。由此可把一个数学游戏问题转化成为一个在计算机上计算的数学问题(即建模)。 可以看出,当状态向量维数增加,约束条件复杂时,这种方法更能方便求解,当所有的转移过程出现循环时,则问题无解。,图论法求解,在研究状态域位置发生变更的问题中,常常构造有向图来解决。 首先对两岸上允许的组合加以分类,比如用(FWG|C)表示F、W和G在左岸上,而C在右岸上,“O“意味着在相应的岸上均无。 将每一状态(允许出现情况)用一个点表示,若某次船从左岸划往右岸时,使状态u变为v,就作一条从u到v的弧(有向边),由此构造了一个有向图(图5-12)。得到该问题的数学模型。,有向图的图数学模型,(FWGC|O) (FWG|C) (FWC|G) (FGC|W) (FG|WC) (WC|FG) (W|FGC) (G|FWC) (C|FWG) (O|FWGC) 图1 注意到船是在两岸间往返的;该问题数学模型: 在图1中找一个从初始状态(FWGC|O)到(O|FWGC)的弧的序列。,无向图的模拟求解法,仍将每一允许状态用一个点表示,两种状态的两顶点有边相连当且仅当两种状态可用载人(或加一物)的渡船互相转变,当且仅当可取状态经过系统的运算向量而仍为可取状态。 由此可以得到图2,无向图的图示数学模型,(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,1,0,1) 图2 于是问题转化为: 求一条从(1,1,1,1)顶点到(0,0,0,0)顶点的路.若各边赋权为l,即化为求一条这样的最短路。,两种等优(最短路)方案,(1,1,1,1) (0,0,0,1) (1,0,1,1) (0,0,1,0) (1,0,1,0) (0,1,0,1) (1,1,0,1) (0,1,0,0) (1,1,1,0) (0,0,0,0) 图3,公平的席位分配模型,席位分配问题,某学校有3个系共200名学生,其中甲系100名,乙系60名,丙系40名,若学生代表会议设20个席位,公平而又简单的席位分配办法是按学生人数的比例分配,显然甲乙丙三系分别应占有10、6、4个席位。,问题提出,现在丙系有6名学生转人甲乙两系,各系人数如表2-1第2列所示。仍按比例(表中第3列)分配席位时出现了小数(表中第4列),在将取得整数的19席分配完毕后,三系同意剩下的1席参照所谓惯例分给比例中小数最大的丙系,于是三系仍分别占有10、6、4席(表中第5列)。,表2-1 按照比例并参照惯例的席位分配,因为有20个席位的代表会议在表决提案时可能出现10:10的局面,会议决定下一届增加l席。他们按照上述方法重新分配席位,计算结果见表6、7列。显然这个结果对丙系太不公平了,因为总席位增加1席,而丙系却由4席减为3席 参照惯例的结果要解决这个问题必须舍弃所谓惯例,找到衡量公平分配席位的指标,并由此建立新的分配方法。,建立数量指标,讨论A、B两方公平分配席位的情况。 设两方人数分别p1、p2,占有席位分别是n1和n2,则两方每个席位代表的人数分别为p1/n1和p2/n2 显然仅当p1/n1=p2/n2时,席位分配才是公平的。 但是因为人数和席位都是整数,所以通常p1/n1p2/n2,这时席位分配不公平,并且pi/ni(i=l,2)数值较大的一方吃亏,或者说对这一方不公平。,不公平程度的数值衡量,不妨假设p1/n1p2/n2,不公平程度可用数值p1/n1-p2/n2衡量。 如设p1=120,p2=100,n1=n2=10, p1/n1-p2/n2=12-10=2, 它衡量的是不公平的绝对程度,常常无法区分两种程度明显不同的不公平情况, 例如上述双方人数增加为p1=1020和p2=1000而席位n1、n2不变时,p1/n1-p2/n2=102-100=2,即绝对不公平程度不变。 但是常识告诉我们,后面这种情况的不公平程度比起前面来已经大为改善了。,相对不公平值的定义,为了改进上述绝对标准,自然想到用相对标准。 仍记p1、p2为A、B两方的固定人数,n1、n2为两方分配的席位(可变), 若p1/n1p2/n2,则定义 rA(n1,n2)=(p1/n1-p2/n2)/(p2/n2) (1) 为对A的相对不公平值.((1)式右端的分母可以易为p1/n1,对下面的结果没有影响) 若p2/n2p1/n1,则定义 rB(n1,n2)=(p2/n2-p1/n1)/(p1/n1) (2) 为对B的相对不公平值。 建立了衡量分配不公平程度的数量指标rA、rB后,制定席位分配方案的原则是使其尽可能小。,确定分配方案,假设A、B两方已分别占有n1和n2席,利用相对不公平值rA和rB讨论,当总席位增加1席时,应该分配给A还是B。 不失一般性可设p1/n1p2/n2,即对A不公平。当再分配1个席位时,关于pi/ni(i=1,2)的不等式可能有以下3种情况: l. p1/(n1+1)p2/n2,这说明即使A方增加1席,仍然对A不公平,所以这一席显然应分给A方。,2. p1/(n1+1)p2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《老年人能力综合评估规范》标准修订编制说明
- DB11T 1031-2013 低层蒸压加气混凝土承重建筑技术规程
- 农业机械采购招投标文件范本
- 智慧城市解决方案研发外包制度
- 活动策划师聘用合同模板
- 汽车维修招投标操作规程
- 医药电商子公司用户体验改进
- 教育机构硬化地面施工合同
- 城镇医疗救助管理办法综合
- 教育公司消防管道安装合同
- 完整2024年国有企业管理人员处分条例专题课件
- 2024-2025一年级上册科学教科版2.5《通过感官来发现》课件
- 中华民族共同体概论课件专家版8第八讲 共奉中国与中华民族聚力发展
- GB/T 32066-2024煤基费托合成液体石蜡
- 术中获得性压力损伤预防
- 国开电大本科工程数学(本)在线形考(形成性考核作业4)试题及答案
- 机器视觉课件
- 六年级上册美术课件-第1课 建筑艺术的美 ▏人美版 (共20张PPT)
- 公路顶管穿越施工方案(中文)
- 桩基溶洞处理施工方案(注浆法
- 第12讲-1602液晶显示及其应用ppt课件
评论
0/150
提交评论