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

初等数学模型vv1.1.商人安全过河模型商人安全过河模型商人安全过河模型商人安全过河模型vv2.2.人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型商人安全过河模型商人安全过河模型问题的提出问题的提出v三名商人各带一个随从乘船渡河，一只小船只三名商人各带一个随从乘船渡河，一只小船只能容纳两人，由他们自己划行。能容纳两人，由他们自己划行。v随从们密约，在河的任一岸，一旦随从的人数随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。比商人多，就杀人越货。v如何乘船渡河的大权掌握在商人们手中，如何乘船渡河的大权掌握在商人们手中，v商人们怎样才能安全渡河呢商人们怎样才能安全渡河呢?数模求解的意义数模求解的意义v 对于这类智力游戏，经过一番逻辑思索是可以找出对于这类智力游戏，经过一番逻辑思索是可以找出解决办法的。解决办法的。v这里用数学模型求解，这里用数学模型求解，一是为了给出建模的示例，一是为了给出建模的示例，二是因为这类模型可以解决相当广泛的一类问题，比逻二是因为这类模型可以解决相当广泛的一类问题，比逻辑思索的结果容易推广。辑思索的结果容易推广。问题分析：问题分析：v由于这个虚拟的问题己经理想化了，所以不必由于这个虚拟的问题己经理想化了，所以不必再作假设。再作假设。v安全渡河问题可以视为多步决策过程。每一步，安全渡河问题可以视为多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员对船上的人员(商人、随从各几人商人、随从各几人)作出决策作出决策v在保证安全的前提下在保证安全的前提下(两岸的商人数都不比随从两岸的商人数都不比随从数少数少)，在有限步内使人员全部过河。，在有限步内使人员全部过河。变量的确定变量的确定v用状态用状态(变量变量)表示某一岸的人员状况，决策表示某一岸的人员状况，决策(变量变量)表示船上的人员状况，可以找出状态随决策变化的表示船上的人员状况，可以找出状态随决策变化的规律。规律。v问题转化为在状态的允许变化范围内问题转化为在状态的允许变化范围内(即安全渡河即安全渡河条件条件)，确定每一步决策，达到渡河目标。，确定每一步决策，达到渡河目标。模型构成模型构成 v记第记第k次渡河前此岸的商人数为次渡河前此岸的商人数为xk，随从数为，随从数为yk，k=l，2，xk,yk=0，1，2，3。v将二维向量将二维向量sk=(xk,yk)定义为状态定义为状态v安全渡河条件下的状态集合称为允许状态集合，记安全渡河条件下的状态集合称为允许状态集合，记作作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变化的规律变化的规律v记第记第k次渡船上商人数为次渡船上商人数为u k，随从数为，随从数为v kv将二维向量将二维向量dk=(uk,vk)定义为决策定义为决策.允许决策集允许决策集合记作合记作D，由小船的容量可知，由小船的容量可知 D=(u，u)|u+v=l，2 (2)v因为因为k为奇数时船从此岸驶向彼岸，为奇数时船从此岸驶向彼岸，k为偶数时为偶数时船由彼岸驶回此岸，所以状态船由彼岸驶回此岸，所以状态sk随决策随决策d k变化变化的规律是的规律是 s k+1=s k+(-1)kd k (3)(3)式称状态转移律。式称状态转移律。商人安全过河的数学模型商人安全过河的数学模型（多步决策模型）多步决策模型）:v 求决策求决策d k D(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)的转移过程的转移过程v具体转移步骤如下具体转移步骤如下:(0，1)(3，2)(0，2)(3，1)(3，3)+(-1)1 (1，1)(2，2)(1，0)(2，3)(2，0)(1，3)v 再将再将(3，2)，(3，1)，(2，2)分别与决策向量分别与决策向量进行运算。如此下去，不难验证，经过进行运算。如此下去，不难验证，经过11次决次决策可取运算后即可完成。策可取运算后即可完成。v 当当k为奇数时，为奇数时，dk表示从此岸到彼岸，当表示从此岸到彼岸，当k为为偶数时，表示从彼岸回到此岸。偶数时，表示从彼岸回到此岸。模型求解模型求解 v 根据根据(1)-(3)式编一段程序，用计算机求解上述多式编一段程序，用计算机求解上述多步决策问题是可行的。步决策问题是可行的。v对于商人和随从人数不大的简单状况，用图解法解对于商人和随从人数不大的简单状况，用图解法解这个模型更为方便。这个模型更为方便。v y（随从数）（随从数）3 (3,3)o x(商人数商人数)1 2 3 图1-3 安全渡河问题的图解法（共四种）图解法决策的步骤图解法决策的步骤v在在xoy平面坐标系上画出图平面坐标系上画出图1-3那样的方格，方格点那样的方格，方格点表示状态表示状态s=(x,y)。v允许状态集合允许状态集合S是圆点标出的是圆点标出的10个格子点。个格子点。v允许决策允许决策d是沿方格线移动是沿方格线移动1或或2格，格，k为奇数时向左、为奇数时向左、下方移动，下方移动，k为偶数时向右、上方移动。为偶数时向右、上方移动。v要确定一系列的要确定一系列的d k使由使由s 1=(3，3)经过那些圆点最经过那些圆点最终移至原点终移至原点(0，0)。课堂课堂(后后)数模练习数模练习v试在图试在图1-3中给出一种移动方案，即经过决策中给出一种移动方案，即经过决策 d 1,d 2，d n，最终有，最终有s n+1=(0，0)。v将该结果翻译成渡河的方案。将该结果翻译成渡河的方案。评评 注注 v 这里介绍的模型是一种规格化的方法，使我们这里介绍的模型是一种规格化的方法，使我们可以用计算机求解，从而具有推广的意义。可以用计算机求解，从而具有推广的意义。v譬如当商人和随从人数增加或小船的容量加大譬如当商人和随从人数增加或小船的容量加大时，靠逻辑思考就困难了，而用这种模型则仍时，靠逻辑思考就困难了，而用这种模型则仍可方便地求解。可方便地求解。v另外，适当地设置状态和决策，并确定状态转另外，适当地设置状态和决策，并确定状态转移律，是有效地解决很广泛的一类问题的建模移律，是有效地解决很广泛的一类问题的建模方法，在以后还可能要用到。方法，在以后还可能要用到。人、狼、羊、菜渡河模型人、狼、羊、菜渡河模型 问题的提出问题的提出v一摆渡人一摆渡人F希望用一条小船把一只狼希望用一条小船把一只狼W，一头，一头羊羊G和一篮白菜和一篮白菜C从一条河的左岸渡到右岸去，从一条河的左岸渡到右岸去，而船小只能容纳而船小只能容纳F、W、G、C中的两个，决中的两个，决不能在无人看守的情况下，留下狼和羊在一不能在无人看守的情况下，留下狼和羊在一起，羊和白菜在一起，起，羊和白菜在一起，v应怎样渡河才能将狼、羊、白菜都运过去应怎样渡河才能将狼、羊、白菜都运过去?v 这是一个有趣的智力游戏问题，显然可用这是一个有趣的智力游戏问题，显然可用递推方法解决，但我们把此问题化为状态转递推方法解决，但我们把此问题化为状态转移问题来解决。移问题来解决。状态向量的表示状态向量的表示 v将人、狼、羊、菜依次用一个四维向量表示，将人、狼、羊、菜依次用一个四维向量表示，当一物在左岸时，记相应的分量为当一物在左岸时，记相应的分量为1，否则记，否则记为为0，如，如A(1,0,1,0)表示人和羊在左岸，并称表示人和羊在左岸，并称为一个状态为一个状态v由问题中的限制条件，有些状态是允许的，由问题中的限制条件，有些状态是允许的，有的是不允许的。有的是不允许的。v凡系统可以允许存在的状态称为可取状态，如凡系统可以允许存在的状态称为可取状态，如A1(1,0,1,0)是可取状态，但是可取状态，但A2(0,0,1,1)是一个是一个不可取状态，不可取状态，v此外，把每运载一次也用一个四维向量来表示，此外，把每运载一次也用一个四维向量来表示，如如B1(1,1,0,0)表示人和狼在船上，而羊和白菜表示人和狼在船上，而羊和白菜不在船上，这是可取的运载，因为船可载两物，不在船上，这是可取的运载，因为船可载两物，而而B2(1,0,1,1)则是不可取运载则是不可取运载v利用穷举法可得到问题的解利用穷举法可得到问题的解 穷举法求解穷举法求解v(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个的相反状态个的相反状态。可取运载与可取运算可取运载与可取运算 v(2)可取运载可取运载 B 共有共有4个个 (1，1，0，0)(1，0，1，0)(1，0，0，1)(1，0，0，0)v(3)可取运算可取运算:规定规定A与与B相加时对每一分量按二进相加时对每一分量按二进制法则进行制法则进行:0十十0=0，1十十 0=1，0十十 1=1，1十十 1=0。v 这样这样，一次渡河就是一个可取状态向量与一个可，一次渡河就是一个可取状态向量与一个可取运载向量相加，可取状态经过加法运算后仍是可取运载向量相加，可取状态经过加法运算后仍是可取状态取状态，这种运算称为可取运算，这种运算称为可取运算。穷举法的数学模型穷举法的数学模型v 在上述规定下，问题转化为在上述规定下，问题转化为:从初始状态从初始状态 (1，1，1，1)经过多少次经过多少次(奇数次奇数次)可取运算才能转化为状态可取运算才能转化为状态(0，0，0，0)。v 如果一个状态是可取的就打如果一个状态是可取的就打，否则就打，否则就打，虽然，虽然可取但已重复就打可取但已重复就打，于是问题可用穷举法解答如，于是问题可用穷举法解答如下：下：(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)v第第7步步 已经出现已经出现(0，0，0，0)状态，说明经过状态，说明经过7次次运载即可，其过程为：运载即可，其过程为：去去(人，羊人，羊)回回(人人)去去(人，狼人，狼(或菜或菜)回回(人，羊人，羊)去去(人，菜人，菜(或狼或狼)回回(人人)去去(人，羊人，羊)评评 注注v用这种方法的优点易于在计算机上实现。由此可把用这种方法的优点易于在计算机上实现。由此可把一个数学游戏问题转化成为一个在计算机上计算的一个数学游戏问题转化成为一个在计算机上计算的数学问题数学问题(即建模即建模)。v可以看出，当状态向量维数增加，约束条件复杂时，可以看出，当状态向量维数增加，约束条件复杂时，这种方法更能方便求解，当所有的转移过程出现循这种方法更能方便求解，当所有的转移过程出现循环时，则问题无解。环时，则问题无解。图论法求解图论法求解v在研究状态域位置发生变更的问题中，常常在研究状态域位置发生变更的问题中，常常构造有向图来解决。构造有向图来解决。v 首先对两岸上允许的组合加以分类，比如首先对两岸上允许的组合加以分类，比如用用(FWG|C)表示表示F、W和和G在左岸上，而在左岸上，而C在右在右岸上，岸上，“O意味着在相应的岸上均无。意味着在相应的岸上均无。v 将每一状态将每一状态(允许出现情况允许出现情况)用一个点表示，用一个点表示，若某次船从左岸划往右岸时，使状态若某次船从左岸划往右岸时，使状态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)图图1v注意到船是在两岸间往返的注意到船是在两岸间往返的;该问题数学模型：该问题数学模型：在图在图1中找一个从初始状态中找一个从初始状态(FWGC|O)到到(O|FWGC)的弧的序列。的弧的序列。无向图的模拟求解法无向图的模拟求解法v仍将每一允许状态用一个点表示，两种状态的两顶仍将每一允许状态用一个点表示，两种状态的两顶点有边相连当且仅当两种状态可用载人点有边相连当且仅当两种状态可用载人(或加一物或加一物)的渡船互相转变，当且仅当可取状态经过系统的运的渡船互相转变，当且仅当可取状态经过系统的运算向量而仍为可取状态。算向量而仍为可取状态。v由此可以得到图由此可以得到图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)图图2v 于是问题转化为：于是问题转化为：v 求一条从求一条从(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 公平的席位分配模型公平的席位分配模型席位分配问题席位分配问题v 某学校有某学校有3个系共个系共200名学生，其中甲系名学生，其中甲系100名，名，乙系乙系60名，丙系名，丙系40名，若学生代表会议设名，若学生代表会议设20个席位，个席位，公平而又简单的席位分配办法是按学生人数的比例公平而又简单的席位分配办法是按学生人数的比例分配，显然甲乙丙三系分别应占有分配，显然甲乙丙三系分别应占有10、6、4个席位。个席位。问题提出问题提出v现在丙系有现在丙系有6名学生转人甲乙两系，各系人数如表名学生转人甲乙两系，各系人数如表2-1第第2列所示。仍按比例列所示。仍按比例(表中第表中第3列列)分配席位时出分配席位时出现了小数现了小数(表中第表中第4列列)，在将取得整数的，在将取得整数的19席分配席分配完毕后，三系同意剩下的完毕后，三系同意剩下的1席参照所谓惯例分给比席参照所谓惯例分给比例中小数最大的丙系，于是三系仍分别占有例中小数最大的丙系，于是三系仍分别占有10、6、4席席(表中第表中第5列列)。表表2-1 按照比例并参照惯例的席位分配按照比例并参照惯例的席位分配系系 别别学学生生人人数数学学生生人人数数比比例例（%）20个席位的分配个席位的分配21个席位的分配个席位的分配比比例例分分配席位配席位参参照照惯惯例结果例结果比比例例分分配席位配席位参参照照惯惯例结果例结果甲甲10351.510.31010.81511乙乙6331.56.366.6157丙丙34l7.03.443.5703合合计计200100.020.02021.00021v因为有因为有20个席位的代表会议在表决提案时可能出现个席位的代表会议在表决提案时可能出现10:10的局面，会议决定下一届增加的局面，会议决定下一届增加l席。他们按照席。他们按照上述方法重新分配席位，计算结果见表上述方法重新分配席位，计算结果见表6、7列。显列。显然这个结果对丙系太不公平了，因为总席位增加然这个结果对丙系太不公平了，因为总席位增加1席，而丙系却由席，而丙系却由4席减为席减为3席席v 参照惯例的结果要解决这个问题必须舍弃所谓惯例，参照惯例的结果要解决这个问题必须舍弃所谓惯例，找到衡量公平分配席位的指标，并由此建立新的分找到衡量公平分配席位的指标，并由此建立新的分配方法。配方法。建立数量指标建立数量指标 v讨论讨论A、B两方公平分配席位的情况。两方公平分配席位的情况。v设两方人数分别设两方人数分别p1、p2，占有席位分别是，占有席位分别是n1和和n2，则两方每个席位代表的人数分别为，则两方每个席位代表的人数分别为p1/n1和和p2/n2v显然仅当显然仅当p1/n1=p2/n2时，席位分配才是公平时，席位分配才是公平的。的。v但是因为人数和席位都是整数，所以通常但是因为人数和席位都是整数，所以通常p1/n1 p2/n2,这时席位分配不公平，并且这时席位分配不公平，并且pi/ni(i=l，2)数值较大的一方吃亏，或者说对数值较大的一方吃亏，或者说对这一方不公平。这一方不公平。不公平程度的数值衡量不公平程度的数值衡量v 不妨假设不妨假设p1/n1p2/n2,不公平程度可用数值不公平程度可用数值p1/n1-p2/n2衡量。衡量。v如设如设p1=120，p2=100，n1=n2=10,p1/n1-p2/n2=12-10=2，它衡量的是不公平的绝对程度，常常无法区分它衡量的是不公平的绝对程度，常常无法区分两种程度明显不同的不公平情况，两种程度明显不同的不公平情况，v例如上述双方人数增加为例如上述双方人数增加为p1=1020和和p2=1000而席位而席位n1、n2不变时，不变时，p1/n1-p2/n2=102-100=2，即绝对不公平程度不变。，即绝对不公平程度不变。v但是常识告诉我们，后面这种情况的不公平但是常识告诉我们，后面这种情况的不公平程度比起前面来已经大为改善了。程度比起前面来已经大为改善了。相对不公平值的定义相对不公平值的定义v 为了改进上述绝对标准，自然想到用相对标准。为了改进上述绝对标准，自然想到用相对标准。v仍记仍记p1、p2为为A、B两方的固定人数，两方的固定人数，n1、n2为两方分配的席位为两方分配的席位(可变可变)，v 若若p1/n1p2/n2,则定义则定义 rA(n1,n2)=(p1/n1-p2/n2)/(p2/n2)（1）为对为对A的相对不公平值的相对不公平值.（(1)式右端的分母可式右端的分母可以易为以易为p1/n1，对下面的结果没有影响），对下面的结果没有影响）v 若若p2/n2p1/n1，则定义，则定义 rB(n1,n2)=(p2/n2-p1/n1)/(p1/n1)(2)为对为对B的相对不公平值。的相对不公平值。v 建立了衡量分配不公平程度的数量指标建立了衡量分配不公平程度的数量指标rA、rB后，制定席位分配方案的原则是使其尽可能小。后，制定席位分配方案的原则是使其尽可能小。确定分配方案确定分配方案 v 假设假设A、B两方已分别占有两方已分别占有n1和和n2席，利用相对不席，利用相对不公平值公平值rA和和rB讨论，当总席位增加讨论，当总席位增加1席时，应该分配席时，应该分配给给A还是还是B。v不失一般性可设不失一般性可设p1/n1p2/n2,即对即对A不公平。当再不公平。当再分配分配1个席位时，关于个席位时，关于pi/ni(i=1，2)的不等式可能有的不等式可能有以下以下3种情况种情况:v l.p1/(n1+1)p2/n2，这说明即使，这说明即使A方增加方增加1席，席，仍然对仍然对A不公平，所以这一席显然应分给不公平，所以这一席显然应分给A方。方。v 2.p1/(n1+1)p2/(n2+1)，即当，即当B方增加方增加1席时将席时将对对A不公平，参照不公平，参照(1)式可计算出对式可计算出对A的相对不的相对不公平值为公平值为 rA(n1,n2+1)=p1(n2+1)/p2n1 (4)(不可能出现不可能出现p1/n1p2/(n2+1)的情况。为什么的情况。为什么?)公平分配席位的公平分配席位的Q值法值法v 公平分配席位的原则是：使得相对不公平值尽可能公平分配席位的原则是：使得相对不公平值尽可能地小，所以如果地小，所以如果 rB(n1+1,n2)rA(n1,n2+1)(5)则这则这1席应分给席应分给A方方;反之则分给反之则分给B方。方。根据根据(3)、(4)两式，两式，(5)式等价于式等价于 p22/n2(n2+1)p2/n2也也与与(6)式等价。于是我们的结论是，当式等价。于是我们的结论是，当(6)式成立时式成立时增加的增加的1席应分给席应分给A方，反之则分给方，反之则分给B方。若记方。若记 Qi=pi2/ni(ni+1),i=l,2，则增加的则增加的1席应分给席应分给Q值较大的一方。值较大的一方。v 上述方法可以推广到有上述方法可以推广到有m方分配席位的情况。方分配席位的情况。用用Q值法讨论三系分配值法讨论三系分配21个席位问题。个席位问题。v 先按照比例计算结果将整数部分的先按照比例计算结果将整数部分的19席分配席分配完毕，有完毕，有n1=10，n2=6，n3=3，然后再用，然后再用Q值值方法分配第方法分配第20席和第席和第21席。席。第第20席席:计算，计算，Q1最大，于是这一席应分给甲系最大，于是这一席应分给甲系第第21席席:计算计算Q1=804，Q3最大，于是这一席应分给丙系。最大，于是这一席应分给丙系。v 这样，这样，21个席位的分配结果是三系分别占有个席位的分配结果是三系分别占有11、6、4席，丙系保住了险些丧失的席，丙系保住了险些丧失的1席。你席。你觉得这种分配方法公平吗觉得这种分配方法公平吗?模型评注模型评注 v席位分配应该对各方公平是人人同意的，问题的关席位分配应该对各方公平是人人同意的，问题的关键在于建立衡量公平程度的既合理又简明的数量指键在于建立衡量公平程度的既合理又简明的数量指标。标。v这个模型提出的指标是相对不公平值这个模型提出的指标是相对不公平值rA、rB，它是，它是确定分配方案的前提。确定分配方案的前提。v在这个前提下导出的分配方案在这个前提下导出的分配方案分给分给分给分给QQ值最大的值最大的值最大的值最大的一方一方一方一方无疑是公平的。无疑是公平的。