《初等数学模型》PPT课件.ppt

《《初等数学模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《初等数学模型》PPT课件.ppt（44页珍藏版）》请在三一办公上搜索。

1、初等数学模型,1.商人安全过河模型2.人、狼、羊、菜渡河模型,商人安全过河模型,问题的提出,三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢?,数模求解的意义,对于这类智力游戏，经过一番逻辑思索是可以找出解决办法的。这里用数学模型求解，一是为了给出建模的示例，二是因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推广。,问题分析：,由于这个虚拟的问题己经理想化了，所以不必再作假设。安全渡河问题可以视为多步决策过程。每一步，即船由此岸驶向彼岸或从

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;

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)。

4、,由状态(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

5、安全渡河问题的图解法（共四种）,图解法决策的步骤,在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)。将该结果翻译成渡河的方案。,评 注,这里介绍的模型是一种规格化的方法，使我们可以用计算机求解，从而具有推广的意义。譬如当商人和随从人数增加或小船的容量加

6、大时，靠逻辑思考就困难了，而用这种模型则仍可方便地求解。另外，适当地设置状态和决策，并确定状态转移律，是有效地解决很广泛的一类问题的建模方法，在以后还可能要用到。,人、狼、羊、菜渡河模型,问题的提出,一摆渡人F希望用一条小船把一只狼W，一头羊G和一篮白菜C从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C中的两个，决不能在无人看守的情况下，留下狼和羊在一起，羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过去?这是一个有趣的智力游戏问题，显然可用递推方法解决，但我们把此问题化为状态转移问题来解决。,状态向量的表示,将人、狼、羊、菜依次用一个四维向量表示，当一物在左岸时，记相应的分量为1，否

7、则记为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，

8、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)。如果一个状态是可

9、取的就打，否则就打，虽然可取但已重复就打，于是问题可用穷举法解答如下：,(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，

10、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，

11、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次运载即可，其过程为：去(人，羊)回(人)去(人，狼(或菜)回(人，羊)去(人，菜(或狼)回(人)去(人，羊),评 注,用这种方法的优点易于在计算机上实现

12、。由此可把一个数学游戏问题转化成为一个在计算机上计算的数学问题(即建模)。可以看出，当状态向量维数增加，约束条件复杂时，这种方法更能方便求解，当所有的转移过程出现循环时，则问题无解。,图论法求解,在研究状态域位置发生变更的问题中，常常构造有向图来解决。首先对两岸上允许的组合加以分类，比如用(FWG|C)表示F、W和G在左岸上，而C在右岸上，“O意味着在相应的岸上均无。将每一状态(允许出现情况)用一个点表示，若某次船从左岸划往右岸时，使状态u变为v,就作一条从u到v的弧(有向边)，由此构造了一个有向图(图5-12)。得到该问题的数学模型。,有向图的图数学模型,(FWGC|O)(FWG|C)(FW

13、C|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,

14、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个席位。,问题提出,现

15、在丙系有6名学生转人甲乙两系，各系人数如表2-1第2列所示。仍按比例(表中第3列)分配席位时出现了小数(表中第4列)，在将取得整数的19席分配完毕后，三系同意剩下的1席参照所谓惯例分给比例中小数最大的丙系，于是三系仍分别占有10、6、4席(表中第5列)。,表2-1 按照比例并参照惯例的席位分配,因为有20个席位的代表会议在表决提案时可能出现10:10的局面，会议决定下一届增加l席。他们按照上述方法重新分配席位，计算结果见表6、7列。显然这个结果对丙系太不公平了，因为总席位增加1席，而丙系却由4席减为3席 参照惯例的结果要解决这个问题必须舍弃所谓惯例，找到衡量公平分配席位的指标，并由此建立新的分

16、配方法。,建立数量指标,讨论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，它衡量的是不公平的绝对程度，常常无法区分两种程

17、度明显不同的不公平情况，例如上述双方人数增加为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,

18、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/(n2+1)，即当B方增加1席时将对A不公平，参照(1

19、)式可计算出对A的相对不公平值为 rA(n1,n2+1)=p1(n2+1)/p2n1(4)(不可能出现p1/n1p2/(n2+1)的情况。为什么?),公平分配席位的Q值法,公平分配席位的原则是：使得相对不公平值尽可能地小，所以如果 rB(n1+1,n2)p2/n2也与(6)式等价。于是我们的结论是，当(6)式成立时增加的1席应分给A方，反之则分给B方。若记 Qi=pi2/ni(ni+1),i=l,2，则增加的1席应分给Q值较大的一方。上述方法可以推广到有m方分配席位的情况。,用Q值法讨论三系分配21个席位问题。,先按照比例计算结果将整数部分的19席分配完毕，有n1=10，n2=6，n3=3，然后再用Q值方法分配第20席和第21席。第20席:计算Q1=96.4，Q2=94.5，Q3=96.3 Q1最大，于是这一席应分给甲系第21席:计算Q1=804，Q2=94.5，Q3=96.3 Q3最大，于是这一席应分给丙系。这样，21个席位的分配结果是三系分别占有11、6、4席，丙系保住了险些丧失的1席。你觉得这种分配方法公平吗?,模型评注,席位分配应该对各方公平是人人同意的，问题的关键在于建立衡量公平程度的既合理又简明的数量指标。这个模型提出的指标是相对不公平值rA、rB，它是确定分配方案的前提。在这个前提下导出的分配方案分给Q值最大的一方无疑是公平的。,