数学建模培训班第一章初等模型

1、数学建模(提高班)总学时 60 考试任课教师 杨尚俊电话 5107817全国数学建模竞赛优秀指导教师(2000年) 省级教学名师(2006年)本课拟讲内容0 引言1 初等模型2 微分方程方法建模3 层次分析方法建模4 矩阵分析方法建模7 充分发挥智力巧妙建模8 大学生数学建模竞赛本课程的特点以讨论具体实际问题为主要线索;以讲授数学建模的思路与方法为主要内容;以培养创新精神为主要目的(培训数模竞赛队员). 强调启发思路和分析、解决问题的技巧. 按求解所讨论的具体数学模型的需要介绍有关数学背景知识和基本方法,即实际问题需要什么介绍什么,不强求数学方面的系统性与完整性. 安徽大学从1993年起,就组

2、队参加全国和国际大学生数学建模竞赛,并取得不错的成绩.2000年在国际大学生数学建模竞赛中安大参赛3个队,其中获一等奖1队,获二等奖2队.2002年在全国大学生数学建模竞赛中安大参赛7个队,其中获国家一等奖2队,国家二等奖1队.2006年在全国大学生数学建模竞赛中安大参赛15个队,其中获国家一等奖1队,国家二等奖5队;赛区一等奖5队.2008年在国际大学生数学建模竞赛中安大参赛3个队,其中获一等奖1队,获二等奖3队.2008年在全国大学生数学建模竞赛中安大参赛15个队,其中获国家一等奖3队,国家二等奖2队;赛区一等奖5队.这些成绩不仅给安大争得荣誉,更为国家培养了一些优秀人才. 引 言0.1

3、数学的重要性0.2 本书主要内容0.3 本课程主要特点数学的重要性新世纪国家间的竞争主要是经济竞争,是人才的竞争;人才培养的关键是素质教育,数学教育在素质教育中占据重要地位.当今社会正日益数学化,数学是高科技的基础.数学在工程技术以及国民生产中发挥愈来愈重要的作用甚至是决定性的作用.素质教育的重要性素质教育既是“科教兴国”战略的必然选择,也是教育自身进一步发展的客观需要,更是高校发展的灵魂和动力.理工科的特征往往体现在严谨,规范的教育体系上,而综合性大学更重要的是强调个性化教育.能充分挖掘每个学生的潜力的个性化教育往往是一所综合性大学的重要特征和体现,而数学建模的教育及实践正符合这方面的要求.

4、 数学是高科技的基础社会进步依赖于科学的创新而数学对于科学的发展则具有根本的意义.在今天,数学已成为高科技的基础,并且在一定意义上,可以说是现代文明的标志 (2002年北京国际数学家大会东道国欢迎词摘录).各行各业日益依赖于数学,可以说,当今社会正日益数学化.数学正在向一切领域渗透,数学正在不停地与别的学科结合产生活跃的新兴学科.”高科技本质上是一种数学技术”的观点正在被越来越多的人接受. 2002年8月在中国首都北京举行国际数学家2002年大会,这是该国际最高级数学学术会议第一次在一个发展中国家举行.我国政府非常重视和支持这次会议,最高领导人出席了会议开幕式,并为得奖者授奖.这是李岚清副总理

5、在致大会欢迎词中的一段话. 数学在生产中起重要作用的例子曾经有一家电器公司生产中出现成品率只有84%,并仅有50%的发货日期可以兑现所造成的严重亏损问题. 他们应用统计质量控制在很短时间就成功地发现和解决了问题,使成品率稳定在95%以上,按期发货率也达到95%,当年就实现扭亏增盈1200万美元.这个故事告诉我们:数学可以在国民生产中发挥重要作用,甚至决定性作用.Mathematical Science,Technology,Economic Compitive- ness,National Academy Press, Washington D.C.1991.该公司最先发现出现电器元件的各种性

6、能波动太大.他们首先用数学技术找出产生元件性能波动的原因是在自动控制的酸洗工序中确定酸洗液PH值的机制有问题,产生校正过度.他们再用数学技术(优选法)重新校正减少了起伏,从而解决了这个大问题. 这份报告提出的如下结论也颇有启发性:“在经济竞争中数学科学是必不可少的.数学科学是一种关键性的,能够实行的(低耗高效的)技术.” 这个例子取自Glimm教授主持编撰的代表美国数学科学委员会给美国政府的公开报告:第1章 初等模型 1.1 例子与定义 1.2 其它初等模型简例航行问题:已知:沿长江在相距750km的两个码头A与B之间,顺水航行时间是 30hr;逆水航行时间是50hr.试分别求出船(在静水中)

7、和水的平均速度.AB解:令船和水的平均速度分别是x和y,由题意得二元线性方程组:求解此方程组得 x=20, y=5.答案:船和水的平均速度分别是20km/hr和5km/hr.2515必要的简化与说明 这里,只考虑平均速度是基本的简化,因为船和水的速度是随时间,地点而变化的.严格讲,已知的顺水,逆水航行时间是船在该河段上常年航行的平均时间;而要求的船和水的平均速度也应是该船和水在该河段上常年航行的平均速度. 若把实际问题看作原型的话,则数学模型是将原型经过简化提炼而构成的替代物.这里值得注意的是:简化是构作数学模型必不可少的一步. 解决本问题也需要速度等相关的物理概念,例如,匀速直线运动,速度合

8、成等的有关知识.s=vt 或 v=s/t : 速度=路程/时间 解决本问题的步骤:按照题意设定未知量并决定未知量满足的数学公式;求出这个方程组的解;并在讨论解的存在性与唯一性之后确定该解就是原问题所需要的解. 别忘了验证解的正确性.什么是数学模型?如果要下一个定义的话,可以说:数学模型是对一个实际问题,按照其内在规律作出一些必要的假设(目的为了简化和去掉不确定的因素使之能归结为一个确定的数学问题)并应用适当数学工具导出的一个数学结构.借助数学的分析与计算全面探讨并求出所得数学模型的解,再利用有关的背景知识可以成功地将所得数学解用来解释和回答原先的实际问题.这一整个过程称为数学建模.可用下面的图

9、表直观地表示数学建模过程的各阶段及其联系.实际问题抽象,简化,假设,确定变量与参数建立数学模型并求解,确定参数的值交付使用从而产生经济,社会效益用实际背景或数据等来检验数学模型若不符合实际若符合实际实际问题与其数学模型之间的关系大家知道原型与模型之间的关系.若把实际问题看作原型的话,则数学模型是将原型经过精致地简化,提炼而构成的替代物.这里必须强调两点:第一,一般来说,原型是复杂和困难的,必须把它归结为数学模型才能解决;第二,数学模型不是原型原封不动的复制品,它只是在突出反映原型某些方面性质的近似物.这里难免会存在数学模型与原型的差异甚至矛盾,冲突.但对我们来讲,原型是根本的,当二者出现无法解

10、释的矛盾时,必须修改相关的数学模型以适应原型.例2 气象预报问题气象观测与气象预报偏微分方程组的初值边值混合问题求出数值解确定有关参数作24hr,48hr和72hr预报简化,归纳使用巨型计算机用数值结果解释气象分析偏差及其产生原因 作为天气现象的数学模型在一百多年前就已经很成功地解决了,它是一个特殊的二阶非线性偏微分方程组的初值,边值混合问题.遗憾的是,这个偏微分方程组的混合问题很难求解,不要说,精确解找不到,就是求很粗糙近似解的计算量也惊人地巨大.在现代巨型电子计算机未出世以前,即使通过求此混合问题很粗糙近似解来作短期天气预报也是不现实的,因为花一个月甚至更多时间也完成不了所需的计算.直到2

11、0世纪80年代出现每秒可完成上亿次运算的巨型计算机以后, 数值天气预报这个多年的梦想才得以实现.目前我国也研制成功每秒千亿次运算水平的巨型机,保证了中央气象台每天及时而准确地发布各种天气预报,为国民生产及人民生活作出巨大贡献.例3 安全过河问题问题: 一位老师带三名小学生:甲,乙和丙过河.假设仅有一条小渡船,最多能容纳二人;并且只有老师能划船.此外,学生乙很顽皮,无老师在场时他肯定要欺负甲和丙. 老师应如何安排过河方案使四人都到达彼岸并且不发生学生乙与学生甲,丙单独相处而发生打架伤人的事故?甲乙丙师 实际问题及其数学模型不仅可以涉及数量关系,也可以涉及方案,规则,措施等方面,过河问题就是一例.

12、 过河问题的解一种安全过河方案是: 师乙过去, 接着师回; 师甲去, 接着师乙回; 师丙过去, 接着师回; 师乙过去. 师甲丙乙师乙丙甲师乙甲丙师甲乙丙师甲乙丙过河问题(1)的答案唯一吗?不允许重复时有几个答案?最少渡河次数是多少?如果每人都能划船结论又是如何?* 若你的解法与参考答案不同,你可把它写下来交给我,便于我下次课作适当总结.思考题1-1例4 安全过河问题问题：三个商人每人带一随从过河.假设仅有一条小渡船,最多能容纳二人;并且因他们正处于偏僻地带,这几个不安分的随从在他们人数超过商人人数时将图谋不轨.商人们应如何安排过河方案使六人到达彼岸之前都不发生随从数超过商人数情况而引发杀人越货

13、的事故?从1商1从2从3商2商3 切莫以为数学建模问题都像例1,例3那么简单.不信的话,请你不要参看下面一张幻灯片,试着对例4中的问题,给出你的安全过河方案.你能较快地写出一个安全过河方案吗? 2从过去 接着1从回来; 2从过去 接着1从回来; 2商过去 接着1商1从回来; 2商过去 接着1从回来; 2从过去 接着1从回来; 2从过去. 过河问题的解两点注记按照题意，重要的是商人和随从间的人数对比，至于，商人，随从的个体差异可以不考虑。故在规划方案时只考虑商人，随从人数而不考虑商人，随从的个体差异。如果经过一次或多次来回渡河后本岸状态回复到前面曾经出现过的状态者，称为产生重复。显然，从一个安全

14、方案可以得到一个无重复的安全方案。故在规划方案时只考虑无重复的安全方案。相关的数学表示与分析河岸的状态可用三维向量(x,y,z)表示,意指在所考虑的时刻,该岸有x商人和y随从;z=0,1分别表示船在此岸,彼岸.x,y的取值范围是0,1,2,3.易见:每岸共有44=16种可能的人员状态;两岸人员状态互相唯一决定,例如,若此岸状态向量为(x,y,0),则彼岸状态向量为(3-x,3-y,1).安全状态向量中的x,y应满足条件:xy或x=0.但当一岸出现 3xy 时,另一岸状态向量(x,y,z)将出现 0 xxy 也认为是不安全的状态.所以,每岸的16种状态中恰有10种是安全的,它们组成的集合是S=(

15、x,y)|x=0 x=3x=y.上述分析也适用于有n个商人及n个随从的情况,其中,n为任意正整数.此时,安全集为 S=(x,y)|x=0 x=nx=y.在直角坐标系下安全集S的点组成字形,详见下图.xy(0,0)(3,3)(2,2)(1,1)(0,1)(0,2)(0,3)(3,0)(3,2)(3,1)此岸状态图图 1-1解决安全过河问题(2)的数学模型 基于前面的分析建立解决n商n从安全过河问题的字形棋盘单人跳棋模型:在此岸安全集S组成的字形棋盘上,经奇数步从起点(n,n)跳到终点(0,0)为成功.跳棋规则是:每步在水平或垂直方向跳1或2格;或在45斜线方向跳1格.奇数步向下向左跳;偶数步向上

16、向右跳.一个成功的跳棋过程将给出n商n从安全过河问题的一个方案.例如,图1-1所示的成功跳棋过程正好对应我们前面提出的那个安全过河方案.关于安全过河问题(2)解的讨论一般来说,该问题只要有一个解就有无穷多个解.因为:在这个解的第1步之前增加两步:“1随从过去,接着再回来”,走完此两步仍回到原状态.显然,把这两步作任意次循环,都将回到原状态.所以,由一个已知解可以构造出无穷多个不同的解.换句话说,此问题解的唯一性一般不成立.我们应把两个这样的解看作同一类:其中一个解除多一个循环之外,与另一个解完全相同,这里,循环指的是一个偶数步的来回过渡,并保持循环前和循环后两岸状态完全一样.今后,同一类的解中

17、恒取那个”不允许重复的解”为代表.注意:即使不区别商人或随从间的置换,对于不允许重复的解,解的唯一性一般地也是不成立的.例如,对于安全过河问题(2),仔细观察图1-1不难发现:从(3,3)出发,经“2从过去,接着1从回来”或“1商1从过去,接着1商回来”都达到同样的状态:”1从在彼岸,其余人员在此岸”.因此,安全过河问题(2)至少有两个不允许重复的解.每个不允许重复的解的渡河次数称为最少渡河次数.例如,对图1-1表示的那个不允许重复解最少渡河次数是11.你能证明:”对任何正整数n,n商n从的安全过河问题,不允许重复的解一定是有限个”吗?你能证明:对3商3从安全过河问题,不允许重复(但不区别商人

18、或随从间的置换)的解个数是4吗?思考题1-2安全过河问题(2)的各种推广1. 渡船容量不变(即至多容2人),仅商人,随从人数有所改变思考题1-3 对任意正整数n2,讨论n商人和n随从能否安全过河,若能,并给出答案.思考题1-4 对任意正整数n2,讨论n+1商人和n随从能否安全过河?若能并给出答案.2. 渡船容量和商从人数都改变思考题1-5 假设渡船至多容3人,5商人和5随从能否安全过河?若能,请给出答案.并考虑怎样作更一般性的推广? 思考题1-6 假设渡船至多容4人,能否证明:对任意正整数n,n商人和n随从都能安全过河?给出你的答案的严格证明. 问题：某家7人 (包括爸,妈,二男孩,二女孩和仆

19、人)带一条狗需要一起过河.当时的状况是:只有一条渡船,最多容二人或一人一狗,仅爸,妈,仆人能划船,并且,仆人不在场狗会咬人,妈不在场爸要打儿子, 爸不在场妈要打女儿.应如何安排过河方案使全家和狗安全(指没有人被咬或被打)过河? 注：仅有两个不同的无重复解.另一个安全过河问题爸妈子子女女仆狗 1.2 其它初等模型小兔繁殖问题汉诺塔问题圆内接三角形计数问题双层玻璃窗保温功效可行性分析代表席位公平分配问题最优价格制定问题小兔繁殖问题假设:一对刚出生的小兔(一公一母)被放到一个水草丰盛的孤岛上;2月龄及以上的每对兔子每一个月恰好繁殖一对新兔(也是一公一母);在观察期间没有任何兔子死去.问题:试计算在观

20、察期间的第n个月岛上兔子总对数.解:记第n个月内兔子总对数为fn.则显然f1=1;因一月龄的兔不能繁殖,故f2=1.123456考察期间月数图 1-2初生兔当n3时,为了计算第n月兔子对数fn,要把前一个月的兔子对数fn-1加上新生兔子对数,而新生兔子对数正好等于fn-2(因每对成兔一月生一对).这就证明数列fn满足初始条件:f1=f2=1和递推关系: fn=fn-1+fn-2,n3.不难依次求得数列fn前若干项(参看图1-2)的值 如上表所示:n12345678fn1123581321Fibonacci数列 数列fn在理论和运用方面都非常有用,被称为Fibonacci数列.可以方便地编程计算

21、数列fn,也可以证明它满足下列封闭公式: fn=(1/5)(un-vn),n=1,2, (2.1) 其中,u=(1+5)/2,v=(1-5)/2.试用Matlab编程求fn,其中n为任意正整数.你能严格证明公式(2.1)吗?思考题 1-7汉诺塔问题:一个著名数学游戏游戏规则:今有安装在一块木板上的3根柱子和若干中心有孔的盘子.这些盘子的直径两两不同.开始时,它们已按大小的次序套在第一根柱子上,使得每个盘子的下面没有比它小的盘子.每一次把1个盘子从一根柱子移动到另一根柱子,但是不允许这个盘子放在任何比它小的盘子上面.游戏的最终目标是把所有的盘子都放到第三根柱子上,并保持按大小次序放置,大盘子在下

22、面.问题:令hn表示解n个盘子汉诺塔问题所需要的最少移动次数.试建立关于hn的递推关系并求出函数hn的公式.111222213333ABCDh2=3111222213333ABCD3次1次3次h3=7111222213333ABCDhn-1次1次hn-1次hn=2hn-1+1汉诺塔问题的解法开始时n个盘子放在柱1.按照游戏规则和归纳法我们可以用hn-1次移动将上边的n-1个盘子移到柱2.在这些移动中保留最大的盘子不动,然后我们用一次移动将最大盘子移动到柱3.我们可以再使用hn-1次移动将柱2上的n-1个盘子移到柱3,把它们放到最大的盘子上面(这个最大的盘子一直放在柱3的底部不会破坏游戏规则).

23、容易看出,使用更少的次数是不可能达到目的的.这就证明了hn=2hn-1+1.初始条件是h1=1,因为依照规则一个盘子可以经1次移动从柱1移到柱3. hn=2hn-1+1 =2(2hn-2+1)+1 =22hn-2+2+1 =22(2hn-3+1)+2+1 =23hn-3+22+2+1 = =2n-1h1+2n-2+2+1 =2n-1+2n-2 +2+1 用了初始条件h1=1 =2n-1 用了等比数列和的公式用迭代方法求解这个递推关系2n-1+2n-2+2+1=2n-1的证明令 x=2n-1+2n-2+2+1则 2n-1=2(2n-1+2n-2+2+1)-(2n-1+2n-2 +2+1) =2x

24、-x =x即 2n-1+2n-2+2+1=2n-1 在汉诺地方有一座塔, 那里的僧侣们严格按照这个游戏规则从一根柱子到另一根柱子移动64个金盘子. 他们一秒钟移动一个盘子. 据说当他们结束游戏时世界就到了末日. 试问: 这个世界在僧侣们开始移动盘子多久以后终结? 答案: 264-1秒 5000亿年一个古老的传说12836547过圆周上等分点的三角形计数问题 假设n(2)为给定的正整数,并已知圆周上的n个等分点.试计算以这些等分点为顶点的一切可能的(计较顶点,如156与267或与154都是不同直角三角形)锐,直,钝角三角形个数.右图显示n=8 的情形.用循环数组(i,j,k)来刻画所讨论三角形的

25、构形,其中i,j,k分别表示该三角形按反时针方向相邻二点间所夹已知等分点的个数.易见,经旋转后能重合的三角形构形相等;所讨论三角形的构形满足下列条件: i,j,k0,i+j+k=n-3. (*)例如,在上面例子中的锐角三角形472,直角三角形156,钝角三角形238可分别刻画为 (2,2,1),(3,0,2)和(0,4,1).建立数学模型构形(0,4,1)与(0,1,4)视为不同,因对应三角形238与235经任何旋转都不会重合.设ABC为有构形(i,j,k)的三角形,显然,ABC为直角三角形 maxi,j,k=n/2-1;ABC为锐角三角形 maxi,j,k n/2-1;ABC为钝角三角形 m

26、axi,j,k n/2-1.注 记 (i,j,k)中的i,j,k两两不同,则(i,k,j)视为与 (i,j,k)构形不同的三角形构形. 在具体计算直,钝角三角形个数时,只要确定一切满足条件(*)的不同(非等边)三角形构形(i,j,k)的个数a,再乘以n即可.计算锐角三角形个数时,还要计算等边三角形(i=j=k)构形的个数b.则锐角三角形个数等于 n(a+b/3).n=8时共计有 锐角构形一个:(1,2,2); 直角构形3个:(1,1,3),(0,2,3),(0,3,2); 钝角构形3个:(0,0,5),(0,1,4),(0,4,1)所以,锐角三角形个数是8;直,钝角三角形个数都是38=24.n

27、=8时三角形计数问题的解 当n=10时分别有多少锐,直,钝角三角形? 当n=9时分别有多少锐,直,钝角三角形?思考题 1-8 在复平面单位圆周上取定的n个等分点为a0,a1,an-1,其中,ak=e2ki/n,k=0,1,n-1,以(0,j,k)表示顶点为a0,aj,ak满足:0j16b/d=16h (令h=b/d).双层玻璃窗保温功效讨论 因函数f(s)=2/(s+2) 的导数 f(s)= -2/(s+2)20,故它是s的严格递减函数,从而s16h 给出 QS/QD2/(16h+2). 在通常情况下有 h=b/d4,于是QS/QD2/(16h+2)2/(64+2)=1/333%. 这就是说,

28、在通常情况下,双层玻璃窗的传热量仅为单层玻璃窗的3%.由此可见,双层玻璃窗的保温效果十分显著.这真是一个又好又省的技术,目前已开始全面推广（我家也用上了）. 一个出乎意外的现象人数分别为103,63和34的三个单位的一个20人的代表会议,上一届按照人数比例分配并参照小数尾数优先的惯例决定三单位按10,6和4分配代表席位.但下一届会议为了避免表决提案时出现10:10的僵持局面,决定增加一席,他们按照上述方法算出的结果是11,7和3的分配方案（有关计算如表4-1所示）.增加一席的分配结果显然对第三个单位不公平,因为他们反而比原来的分配方案减少了一席. 20席21席单位人数比例%理论席位实际席位理论

29、席位实际席位110351.510.31010.8151126331.56.366.6157334173.443.573总和20010020202121表1-1问题:如何解释上述不合理现象并提出更合理的代表名额分配方案?代表席位公平分配问题不合理现象产生原因按人数比例分配应该是公平的,但如何解释上述不合理现象呢?显然,其主要原因是代表席位只取整数值,即必须把公平但不是整数的理论席位值作取整处理,即将小数尾数舍去或增加为1.所以,执行的实际席位并非理论席位,从而难保其公平性.严格讲,不考虑单位人数多少单纯的小数尾数优先原则也不尽合理.不合理现象的数学刻画(量化)建立数学模型之前,必须对此不合理现象

30、进行数学刻画.一般地,考察人数分别为pi,pj的单位i和单位j,设按某种分配方案分配给他们实际席位为ni,nj.让我们来讨论在此分配方案下对他们公平性的衡量.显然,若pi/ni=pj/nj,则此分配(对二者)绝对公平.可惜,因ni,nj经过了取整,上述条件几乎不可能满足,故或者pi/nipj/nj,此时,对单位i不公平;或者 pi/nipj/nj,此时,对单位j不公平(为什么?).引进单位i的不公平值如下:ri(ni,nj)=(pi/ni-pj/nj)/(pj/nj)= pinj/(pjni)-1.现在讨论如何在已有分配方案的基础上修改增加一席的新方案.如把一席加给单位j,则单位i的不公平值变

31、为ri(ni,nj+1)=pi(nj+1)/(pjni)-1；如把一席加给单位i,则单位j的不公平值变为rj(ni+1,nj)=pj(ni+1)/(pinj)-1. 易见 ri(ni,nj+1) rj(ni+1,nj) qi qj 其中 qi=pi2/(ni(ni+1)是增加一个代表席位时衡量对单位i不公平程度的一个只依赖于i的参数.上面的讨论引向下之增加1席的合理分配模型: 把增加的1席分配给使比值qi取最大值的对应单位i(因为,未得到加1席的单位中它的不公平值最大,这个分配模型体现照顾矛盾最大者的政策,符合正确处理人民内部矛盾,建立和谐社会的原则).对所讨论的那个3单位实例,先由表1-1得

32、到20席的实际席位分配后,再按上述加1席合理分配模型得出的分配方案是:加1席给单位1,即分配方案向量为(11,6,4)(见表1-2)增加1席的合理分配模型单位pini pi2/(ni(ni+1)加1席方案11031096.4=MAX10+1=11263694.56334457.84总和2002021表1-2结果的分析与讨论加1席合理分配模型照顾可能最吃亏的单位,不言而喻是公平的.应用于上述3单位实例结果将不再发生增加代表名额后出现某些单位反而减少席位的不合理情况,这也是本模型合理性的一个佐证.表1-1,1-2对本例的计算结果也从一个侧面说明按老办法关于20、21席分配方案不合理.这一点也使我们

33、认识到通常的按比例分配的办法并非绝对可靠,在某些特殊情况下,由于取整的影响也会产生显著的误差.思路:先用常法分配19个代表席位,再用本模型加一席即可.计算结果如表1-3所示.此结果与用常法分配20个代表席位的结果不同,这一事实说明原先的分配方案其实并不合理.有趣的是,用本模型分配21个代表席位时,无论从20个代表席位的原方案或从新方案出发都得出同一正确结果(思考题).如何用本模型合理分配20个代表名额?单位pi理论席位ni pi2/(ni(ni+1)加1席方案11039.7851096.45=MAX10+1=112635.985694.5063343.23396.333总和2001920表1-

34、3单位pini pi2/(ni(ni+1)加1席方案11031180.3711263694.56334396.33=MAX3+1=4总和2002021我们用表1-4给出的5单位的例子说明:上述模型也不是绝对正确.因78席时理论值小数尾数全相等,都等于0.4,故取整时可选任2单位加1,其余全舍去尾数.表1-4的两个计算结果说明,用合理加1席模型也得不出唯一合理的结果.下面将提出一个较为公平,但也较为复杂的模型方差最小模型.合理加1席模型仍非绝对正确单位人数理论值取整1qi加1席取整2qi加1席140440.44099.5414194.841220420.42099.1202190.1213104

35、10.41098.3101098.3114545.4669.46597.255141.4232.72198.01总合7807878797879表1-4代表席位分配的方差最小模型(创新)分析:要从分别有人数 p1,pm 的m个单位中选取n个代表.令 p=p1+pm, 则p/n为每个席位平均代表的人数.先算出每个单位应分配代表数的理论值: b1,bm, bi=pin/p,i=1,m. 照例记不大于x的最大整数为x;不小于x的最小整数为x,则ri=bi-bi为bi的小数尾数.若 k=i=1mri 为0,则对每个i,bi都是整数(此时ni=bi),这是罕见的理想绝对公平情况.一般地,k为某个正整数,从

36、而,总有某些bi不是整数.选定k个bi取整为bi=bi,其余取整为bi=bi. 显然,对k个bi取整时,有至多Cmk种可能性.对第u种可能性算出对应方差:Q(u)=i=1mbi/n(pi/bi-p/n)2方差Q(u)的大小刻画按该可能性取整的情况下每个席位平均代表人数与其理想公平值的方差(偏差程度),其值越小越公平.比较两个取整方案ui,uj,它们仅有i,j两单位取整不同,前者按bi,bj;后者按bi,bj取整.易见 由此可见,让对应于使取最小值的前k个单位按ni取整将给出方差最小的,也就是最优的分配方案.令 F(i)=pi2/ bibi,则让使F(i)取最大值的前k个单位向上(其余单位向下)

37、取整将给出最优分配方案(加一席的改进).注意：(F值)方差模型:在k0的情况下对每个单位计算F(i)=pi2/ bibi,则让使F(i)取最大值的前k个单位向上取整,其余单位向下取整将给出最优分配方案.实例:考虑3单位20席的实例.各单位人数为: p1=103,p2=63,p3=34;ni理论值为:b1=10.3, b2=6.3,b3=3.4.因k=1,用方差最小模型计算出20席和21席的公平分配方案(见下表)分别是: 11:6:3 和 11:6:4,与从前结果相一致.方差最小模型与实例20席21席单位pibiFinibiFini110310.396.4551110.81596.4551126

38、36.394.566.61594.563343.496.33333.57096.3334试用方差最小模型计算表1-4给出的5单位78名代表的合理分配方案.思考题 1-10用加一席模型计算出78席和79席的公平分配方案（表A）分别是 (41,20,10,5,2) 和 (41,21,10,5,2). 用方差模型计算出78席和79席的公平分配方案（表B）分别是 (41,21,10,5,1) 和 (41,21,11,5,1).思考题：二者结果不同,到底谁错了? 你能证明前者错而后者对吗？ 试对人数分别为404,204,104,54,14的七单位决定78席和79席的公平分配方案？单人数77席78席79席

39、位pibiniqiniqini140439.8824099.5224194.78341220420.1382099.0862099.08621310410.2641098.3271098.327104545.3308597.2597.255141.3821232.667232.6672单人数78席79席位pibiFinibiFini140440.499.5224140.91899.52241220420.4103.5222120.662103.52221310410.498.3271010.53398.327114545.497.255.469297.255141.49811.4179981表

40、A表B席位分配的另一种方差最小模型设要从分别有人数p1,pm的m个单位中选取n个代表.令p=p1+pm,则n/p为该m个单位的每个人能成为代表的平均机会.设n1,nm为各单位的实际代表数,则ni/pi为第i单位的每个人能成为代表的平均机会.令第i个单位应分配代表数的理论值为bi=npi/p, i=1,m,则ni=bi或bi.ri=bi-bi为bi的小数尾数.若k=n=1mri为0,则每个bi都是整数,这是绝对公平情况,可惜它几乎不可能出现.实际上,k总是某个正整数,换句话说,总有某些bi不是整数.任何一个可行分配方案都对应于选定k个ni为bi,其余ni为bi.显然,将k个ni取整为bi的所有可

41、能性共有Cmk种.对其中第u种可能性算出对应方差:Q(u)=i=1mpi(ni/pi-n/p)2方差Q(u)的大小刻画按第u种可能性取整的情况下,每个人能成为代表的平均机会与理想平均机会n/p的偏差程度,其值越小公平性越好.对任意的ij比较两个取整方案ui,uj,它们仅有i,j两单位取整不同,前者按bi,bj;后者按bi, bj取整.易见 由此可见,让对应于使取前k个最小值的那k个单位按bi取整将给出方差最小的,也就是最优的分配方案.令 G(i)= (2bj+1)/pi,则让使G(i)前k个最小值的那k个单位按bi取整将给出最优分配方案.因(G值)方差模型模型:定义函数值:则将G(i)的前k个

42、最小值对应的单位的ni取整为bi的方案是最优的席位分配方案.实例:下表对人数为:103,63,34的三单位的实例,用本模型计算出20席和21席的公平分配方案分别是:11:6:3和11:6:4;对人数为:404,204,104,54, 14的五单位的实例,用本模型计算出78席和79席的公平分配方案分别是(与前面结果相同):(41,21,10,5,1)和(41,21,11,5,1).20席21席单位pibiGinibiGini110310.30.203881110.8150.20388112636.30.2063566.6150.2063563343.40.2058833.5700.2058847

43、8席79席单位pibiGinibiGini140440.40.20054140.9180.20050441220420.40.200982120.6620.2074721310410.40.201921010.5330.21218114545.40.203755.46920.2201855141.40.2142911.41790.273991 代表席位问题进一步讨论有人给出下列例子说明G值方差模型失效(这里,失效不等同于错误).15席单位pibiGini17021/23/10?2309/23/10?总和10015(2b1+1)/p1=21/70(2b2+1)/p2=9/30 对于上述例子虽然G值方差模型失效,但F值方差模型仍然有效,下表说明加一席模型和F值方差模型给出同一正确结果:(10,5).14席15席(加1席)15席(F值方差模型)单位pibinipi2/ni(ni+1)nibipi2/bibini1709.81044.5451010.544.545102304.244554.5455总和10014141515