第8章代数模型.ppt

科学出版社普通高等教育 十二五 规划教材 数学实验与数学建模 组编江苏省十所地方高校主编林道荣 南通大学 秦志林 淮阴师范学院 周伟光 南京晓庄学院 副主编李苏北 徐州工程学院 陈荣军 常州工学院 张立 常熟理工学院 伍鸣 金陵科技学院 钱黎明 南通纺织职业技术学院 田瀚 淮安信息职业技术学院 周小建 南通大学 夏海峰 淮阴师范学院 田蓓艺 南京晓庄学院 钱峰 南通大学 缪雪晴 南通大学 刘晓惠 南通大学 主审刘东生 南京理工大学 陆国平 江苏信息职业技术学院 第二篇 数学建模 南通大学理学院信息科学与统计学系 科学出版社 2020 1 27 2 第6章数学建模绪论第7章初等模型第8章代数模型第9章微分方程模型第10章差分方程模型 南通大学理学院信息科学与统计学系 科学出版社 2020 1 27 3 第11章静态优化模型第12章动态优化模型第13章随机模型第14章离散数学模型 南通大学理学院信息科学与统计学系 科学出版社 2020 1 27 4 现实世界中有些对象本身是离散的 也有些对象本身是连续的 但从建模目的来考虑 把连续变量离散化更好 处理离散变量一种比较简单的方法是利用代数学工具 即建立代数模型来研究某些现实对象 第8章代数模型 南通大学理学院信息科学与统计学系 科学出版社 2020 1 27 5 本章首先介绍用初等代数方法解决住房贷款利率与还本付息方案问题 其次利用矩阵给出单循环比赛的赛程安排 第三 对植物基因的分布问题 用代数方程表达上一代的基因型分布产生的下一代的基因型分布的递推公式 再用矩阵对角化方法得到任一基因型分布由最初一代的基因型分布的表达式 最后 用代数方程组描述交通网络中各路口等候车辆长度的状态转移规律 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 6 8 1住房贷款利率与还本付息方案8 2体育竞赛赛程安排8 3植物基因的分布8 4城市交通流量 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 7 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 8 8 1住房贷款利率与还本付息方案 一 背景材料 1998年12月30日 金陵晚报 报道 一笔总额为13 5万元的个人住房组合贷款 在两家银行算出了两种还款结果 而差额高达万元以上 这让首次向银行借款的江苏某进出口公司程姓夫妇伤透了脑筋 据介绍 小程打算贷8万元公积金贷款和5 5万元商业性贷款 他分别前往省建行直属支行和市建行房地产信贷部咨询 其结果是 这13 5万元贷款 分15年还清 在利率相同的情况下省建行每月要求还本付息1175 46元 其中公积金贷款660 88元 商业性贷款514 58元 而市建行每月要求还1116 415元 其中公积金634 56元 商业性贷款481 855元 按贷款180个月一算 省建行的贷款比在市建行贷款要多10628 1元 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 9 有关行家解释说 省建行虽然也是等额还款 但实行的是先还息后还本原则 每月还本还息不等 但每月总额一样 举个简单的例子 若每月等额还款1 000元 第一个月还本息分别为100元 900元 而第二个月还本息分别变为200元 800元 依此类推 而市建行实行的是较便于市民理解的等本 等息 等额还款法 为不让市民首期还款时面对巨额利息为难 该行取了一个利息平均值 平摊到每个月中 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 10 值得一提的是 小程夫妇的麻烦已引起了央行的重视 为规范个人住房贷款计息办法 央行重新明确了个人住房贷款的利息计算方法 从1999年1月1日起 除保留每月等额本息偿还法外 又推出了利随本清的等本不等息递减还款法 公式是 每月还款额 贷款本金 贷款期月数 本金 已还本金累计额 月利率 同一笔贷款按这两种方法计算还款 偿还总金额相同 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 11 2020 1 27 南通大学理学院计算科学与统计学系 12 二 问题的提出 请解决下面的问题 1 省建行的 每月等额本息偿还法 先还息后还本原则 中每月还款额是怎样算出来的 2 央行推出的 利随本清等本不等息偿还法 的每月还款额是怎样算出来的 并用市建行的结果进行计算 3 市建行的 等本 等息 等额还款法 是怎样得到的 4 试分析这三种算法的不同之处及利弊 科学出版社 三 问题分析 现有问题 某企业向银行贷款a元人民币 贷期n年 如果年利率为r 问到期贷款本息为多少 答案也是a 1 r n元 在中学中解决问题 某人有a元人民币存入银行 存期n年 如果年利率为r 问到期存款本息为多少 答案是a 1 r n元 由此可见 计算贷款本息和计算存款本息是一样的 分月还贷 换算成月利率 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 13 每月等额本息偿还法 先还息后还本原则 科学出版社 第一月还款额必须超过总贷款一月产生的利息 否则无法还本 每月等额还款额大于总贷款一月产生的利息 在每月等额本息偿还的前提下 计算贷款减去还本后产生的利息 以此确定各月还本额 南通大学理学院计算科学与统计学系 2020 1 27 14 每月等额本息偿还法 先还本后还息原则 第一月还款额必须超过总贷款除以还款月数的分额 否则无法还息 每月等额还款额大于总贷款除以还款月数的分额 在每月等额本息偿还的前提下 计算贷款减去还本后产生的利息 以此确定各月还本额 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 15 等本 等息 等额还款法 由于逐月等额还本 各月贷款利息逐渐减少 以各月未还贷款乘以月利率计算各月产生的利息 取平均值为每月平均还息 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 16 利随本清的等本不等息递减还款法 计算公式 每月还款额 贷款本金 贷款期月数 本金 已还本金累计额 月利率 只要知道月利率 就可计算每月还款额 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 17 四 假设 1 假设小程向银行贷8万元公积金贷款和5 5万元商业性贷款 分15年还清 2 公积金贷款年利率为8 1 相应地月利率为0 675 3 商业性贷款年利率为7 56 相应地月利率为0 63 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 18 五 每月等额本息偿还法 1 先还息后还本原则2 先还本后还息原则3 等本 等息原则 让我们从这三个原则来建立模型吧 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 19 1 先还息后还本原则 设有元贷款 月利率为 每月等额还款分别为元 第月还本元 元贷款第一月产生利息 于是为了能分月还清贷款 必须 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 20 第一月还本a1 x Dr元 第一月末剩余贷款为 科学出版社 第一月末剩余贷款D 1 r x在第二月产生利息Dr 1 r rx 则第二月还本 第二月末剩余贷款为 2020 1 27 南通大学理学院计算科学与统计学系 21 一般地 第月末剩余贷款在第月产生利息 则第月还本 8 1 1 第月末剩余贷款为 8 1 2 即 8 1 3 科学出版社 22 南通大学理学院计算科学与统计学系 2020 1 27 2020 1 27 南通大学理学院计算科学与统计学系 23 科学出版社 取D 80000 r 0 00675 由式 8 1 3 得x 769 147元 与660 88元差距较大 由于公积金贷款是政策性贷款 公积金贷款利率应当低于商业性贷款利率 取x 660 88 代入 8 1 3 得 r 0 004725与0 00675比较发现公积金贷款利率按七折计算 现取r 0 004725 代入 8 1 3 得x 660 906 与660 88元基本吻合 取D 55000 r 0 0063 由式 8 1 3 得x 511 734 与514 58元基本吻合 2 先还本后还息原则 设有D元贷款 月利率为r 每月等额还款分别为y元 而贷款每月等额还款后第i月剩余本息为bi元 i 1 2 180 由于贷款产生利息 于是为了能分月还清贷款 必须y D 180 D元贷款第一月产生利息Dr 则等额还款y元后 第一月末剩余贷款本息为 科学出版社 2020 1 27 南通大学理学院计算科学与统计学系 24 第一月末剩余贷款本息到第二月末产生利息为b1r D 1 r r yr 则等额还款y元后第二月末剩余贷款本息为 科学出版社 一般地 第i 1月末剩余贷款本息 在第i月产生利息 则第i月等额还款y元后第i月末剩余贷款本息为 25 南通大学理学院计算科学与统计学系 2020 1 27 由于第180月等额还款y元后第180月末剩余贷款本息为0元 即 科学出版社 所以 8 1 6 比较式 8 1 6 和式 8 1 3 后发现 等额本息偿还法无论是采用先还息后还本原则还是采用先还本后还息原则 每月等额还款数额一致 2020 1 27 南通大学理学院计算科学与统计学系 26 2020 1 27 南通大学理学院计算科学与统计学系 27 3 等本 等息原则 设有D元贷款 月利率为r 每月等额还本D 180元 等额还本后 设第i月剩余贷款产生利息为ci元 则 贷款每月等额还本后从第一月到第180个月产生的利息C为 8 1 7 科学出版社 科学出版社 180个月产生的平均利息c为 8 1 8 设每月等额还款z元 则由式 8 1 8 有 8 1 9 28 南通大学理学院计算科学与统计学系 2020 1 27 2020 1 27 南通大学理学院计算科学与统计学系 29 科学出版社 分别取D 80000 r 0 004725和D 55000 r 0 0063 由式 8 1 9 得公积金贷款和商业性贷款每月等额还款分别为634 494和479 768 结果与市建行的 等本 等息 等额还款法 的公积金贷款每月等额还款634 56元 商业性贷款每月等额还款481 855元基本吻合 2020 1 27 南通大学理学院计算科学与统计学系 30 六 每月不等额本息偿还法 设有D元贷款 月利率为r 第i月利随本清的等本不等息递减还款额为ui元 则 8 1 10 取D 80000 r 0 004725 公积金贷款第一月还款822 444元 按每月减少还款2 100元 到第180月还款446 544元 取D 55000 r 0 0063 商业贷款第一月还款652 056元 按每月减少还款1 925元 到第180月还款307 481元 科学出版社 七 三种还款法比较 等本 等息 等额还款法VS先还息后还本的等额还款法等本 等息 等额还款法VS利随本清的等本不等息递减还款法先还息后还本的等额还款法VS利随本清的等本不等息递减还款法 科学出版社 2020 1 27 南通大学理学院计算科学与统计学系 31 2020 1 27 南通大学理学院计算科学与统计学系 32 等本 等息 等额还款法VS先还息后还本的等额还款法 对于D元月利率为r的15年期贷款 由式 8 1 9 知等本 等息 等额还款法每月等额还款 而由式 8 1 3 知先还息后还本的等额偿还法每月等额还款 显然r 0时 有 科学出版社 结论 采用等本 等息 等额还款法对于贷款人而言明显好于先还息后还本的等额偿还法 其原因是前90个月的部分利息推迟到后90个月偿还 并且推迟偿还的部分利息没有计算另外计算利息 科学出版社 33 南通大学理学院计算科学与统计学系 2020 1 27 2020 1 27 南通大学理学院计算科学与统计学系 34 等本 等息 等额还款法VS利随本清的等本不等息递减还款法 对于D元月利率为r的15年期贷款 由式 8 1 9 知等本 等息 等额还款法每月等额还款 而由式 8 1 10 知第i月利随本清的等本不等息递减还款额为 当i 91时 z ui 而这两种还款法180个月总还款额都为 科学出版社 2020 1 27 南通大学理学院计算科学与统计学系 35 似乎不能比较这两种还款法优劣 把贷款人的还款反过来看作存款 计算产生的本息 有180笔 元的存款 以月利率r分别存0 1 179个月 则到期本息为 元的存款 以月利率r分别存180 i个月 i 1 2 180 这180笔存款到期本息为 科学出版社 2020 1 27 南通大学理学院计算科学与统计学系 36 显然 结论 采用等本 等息 等额还款法对于贷款人而言明显好于利随本清的等本不等息递减还款法 科学出版社 2020 1 27 南通大学理学院计算科学与统计学系 37 科学出版社 先还息后还本的等额还款法VS利随本清的等本不等息递减还款法 对于D元月利率为r的15年期贷款 由式 8 1 3 知先还息后还本的等额还款法每月等额还款 180个月总还款额为 明显大于 2020 1 27 南通大学理学院计算科学与统计学系 38 科学出版社 下面从存款的角度来分析 有180笔元的存款 以月利率r 分别存0 1 179个月 则到期本息为 明显小于 2020 1 27 南通大学理学院计算科学与统计学系 39 科学出版社 结论 采用先还息后还本的等额还款法对于贷款人而言明显好于利随本清的等本不等息递减还款法 由此可见 市建行的 等本 等息 等额还款法 对贷款人最有利 而对贷款人最不利的是利随本清的等本不等息递减还款法 问题总结 科学出版社 南通大学理学院计算科学与统计学系 2020 1 27 40 2020 1 27 南通大学理学院计算科学与统计学系 41 科学出版社 8 2体育竞赛赛程安排 一 背景材料 许多体育比赛都要安排比赛日程 抛开宣传 商业等方面的考虑 对各参赛队的公平性应该成为赛程安排是否妥当最重要的标准之一 例如 一个随意安排的由5个队 A B C D E 参加的单循环赛的一种赛程表如下 见表8 1 2020 1 27 南通大学理学院计算科学与统计学系 42 科学出版社 表8 15队单循环赛程表一 易见这个赛程安排的公平性得不到保证 对A E有利 而对D不公平 2020 1 27 南通大学理学院计算科学与统计学系 43 科学出版社 表8 25队单循环赛程表二 精心安排的5个队 A B C D E 参加的单循环赛的一种赛程表 易见这个赛程安排的公平性得到提高 2020 1 27 南通大学理学院计算科学与统计学系 44 科学出版社 二 问题的提出 探讨n n 5 支球队在同一块场地上进行单循环比赛的公平性 探讨如何安排赛程 2020 1 27 南通大学理学院计算科学与统计学系 45 科学出版社 三 模型的假设 1 每个参赛队伍按赛程准时参加比赛 无中途调整情况 2 赛程不考虑种子队因素 3 在比赛过程中不会出现意外的停赛等事故 4 给每支球队都编上队号 依次为1 2 3 n 2020 1 27 南通大学理学院计算科学与统计学系 46 科学出版社 四 问题分析 注意到衡量公平的标准为各队每两场比赛中间相隔场次应尽量相等 由此应对各队每两场比赛的最小间隔场次r进行讨论 设赛程中某场比赛是i j两队 i队参加的下一场比赛将是i k两队 k j 要使各队每两场比赛最小相隔场次为r 则上述两场比赛之间必须有除i j k以外的2r支球队参加比赛 于是n 2r 3 注意到r是整数 则r n 3 2 x 表示不超过x的最大整数 即r的上界是 n 3 2 2020 1 27 南通大学理学院计算科学与统计学系 47 科学出版社 为了问题研究具有意义 必须要求 n 3 2 0 即考虑至少5个队的公平赛程安排 当某个赛程的各队每两场比赛的最小间隔场次能达到上界即 n 3 2 时 则是一个公平的赛程安排 2020 1 27 南通大学理学院计算科学与统计学系 48 科学出版社 五 模型的建立和求解 设参赛队数为n n 5 则整个赛程的比赛场次数为 记顶点集 其中的顶点vi表示第i个球队 记权集为 记边集 边 上的权数w表示第i队和第j队在总赛程中的第w场相遇 w W 2020 1 27 南通大学理学院计算科学与统计学系 49 科学出版社 这样 由n个球队参赛的单循环赛赛程安排的问题可以转化为顶点数为n的完全图Kn上赋权的问题 即把权集W中不同的数赋给E中不同的边 就是赛程的一种安排 显然 总共有 种不同的赛程安排 而一个公平的赛程安排必须各队每两场比赛的最小间隔场次能达到上界 n 3 2 2020 1 27 南通大学理学院计算科学与统计学系 50 科学出版社 求解思路 基于抽屉原理利用构造法说明存在一种安排法使得r达到其上界 n 3 2 利用构造法编制赛程表 抽屉原理在2k个抽屉中 放2k 1个球 则必有一个抽屉内放2个以上球 2020 1 27 南通大学理学院计算科学与统计学系 51 科学出版社 存在一种安排法使得达到其上界 当n 2k时 用如下方法制定赛程 设以k场比赛为1轮 总比赛场数为 因此共有n 1 2k 1轮比赛 记第1轮赛程表为 其中 矩阵中每列的两个元素表示该轮中比赛的两支队伍的队号 第i 1轮是在第i轮的基础上 左下角元素2k始终不动 事实上可固定矩阵中的任一元素 其余2k 1个元素按逆时针方向旋转 每个元素移动1位 i 1 2 2k 1 2020 1 27 南通大学理学院计算科学与统计学系 52 科学出版社 当n 2k 1时 用如下方法制定赛程 总比赛场数为 可以分为k轮 每一轮有2k 1场比赛 每个队出场两次 记第1轮赛程表为 其中 矩阵分为左右两部分 左侧k 1列是左部分 右侧k列是右部分 2020 1 27 南通大学理学院计算科学与统计学系 53 科学出版社 第i 1轮是在第i轮的基础上 左部分的左上角和右下角的元素1始终不动 其余元素按顺时针方向旋转 每个元素移动1位 右部分的元素按逆时针方向旋转 i 1 2 k 1 可以验证用上述方法安排的赛程 任意两队之间有比赛 并且无重复 且各队每两场比赛的最小间隔场次能达到上界即 n 3 2 2020 1 27 南通大学理学院计算科学与统计学系 54 科学出版社 构造法编制赛程表 表8 38个参赛队的赛程表 可以看到n 8时每两场比赛相隔场次数只有2 3 4 2020 1 27 南通大学理学院计算科学与统计学系 55 科学出版社 表8 49个参赛队的赛程表 n 9时每两场比赛相隔场次数只有3 4 2020 1 27 南通大学理学院计算科学与统计学系 56 科学出版社 推广 n为偶数时 每两场比赛相隔场次数只有n 2 2 n 2 1和n 2 n为奇数时 每两场比赛相隔场次数只有 n 3 2和 n 1 2 2020 1 27 南通大学理学院计算科学与统计学系 57 科学出版社 六 评注 除了用各队每两场比赛最小相隔场次的上界作为公平性指标外 还可以用其它一些指标来衡量赛程的优劣 如平均相隔场次及平均相隔场次的上界 相隔场次的最大偏差等等 2020 1 27 南通大学理学院计算科学与统计学系 58 科学出版社 七 进一步的问题 对于单循环赛 如果有多块比赛场地 或同时可举行多场比赛 如何安排公平赛程 而对于双循环赛 即两队主客场各赛一次 安排赛程时除间隔场次外 要考虑主客场因素 如何安排公平赛程 另外像桥牌双人比赛那样 不仅对手要轮换 牌局也要轮换 赛程安排就更复杂一些 如何安排公平赛程 2020 1 27 南通大学理学院计算科学与统计学系 59 科学出版社 8 3植物基因的分布 一 问题的提出 假定一个农场有数亩作物 它由三种可能基因型AA Aa及aa的某种分布所组成 农场育种技术人员要采用的育种方案是 作物总体中的每种作物都总是用基因型AA的作物来授粉 要解决的问题为导出在任何一个后代总体中三种可能基因型的分布表达式 2020 1 27 南通大学理学院计算科学与统计学系 60 科学出版社 二 假设 假定所考虑的遗传特性由两个基因A和a来支配 例如人类的眼睛染色体是通过常染色体遗传来控制 AA及Aa型产生棕色眼睛 aa型的是蓝色眼睛 2020 1 27 南通大学理学院计算科学与统计学系 61 科学出版社 三 问题分析 在常染色体遗传中 一个个体从它的亲本的每一基因对中遗传一个基因 以形成它自己特殊的基因对 AA Aa aa 亲本的两个基因中的哪一个传给后代纯属机会问题 如果一个亲本是Aa型 后代从这个亲本遗传获得A基因或a基因的机会是等可能的 对于各种亲本基因型 后代的可能基因型的概率可列入表8 5中 2020 1 27 南通大学理学院计算科学与统计学系 62 科学出版社 表8 5对于各种亲本基因型 后代的可能基因型的概率 2020 1 27 南通大学理学院计算科学与统计学系 63 科学出版社 四 建立模型 记an n 0 1 为在第n代中AA基因型作物所占的分数 记bn n 0 1 为在第n代中Aa基因型作物所占的分数 记cn n 0 1 为在第n代中aa基因型作物所占的分数 a0 b0 c0表示基因型的原始分布 且 2020 1 27 南通大学理学院计算科学与统计学系 64 科学出版社 由于用基因型AA的作物来授粉 由分析表8 5 前三列数据 可知 从上一代的基因型分布产生的下一代的基因型分布可用下列递推公式求出 8 3 1 其中 式 8 3 1 中第一式表明 基因型AA的所有后代都是AA型基因 基因型Aa的后代 有一半是AA型 2020 1 27 南通大学理学院计算科学与统计学系 65 科学出版社 递推公式的矩阵表示为 8 3 2 其中 2020 1 27 南通大学理学院计算科学与统计学系 66 科学出版社 记 由递推公式 8 3 2 可得 于是有模型 8 3 3 其中 2020 1 27 南通大学理学院计算科学与统计学系 67 科学出版社 五 模型求解 求解模型 8 3 3 有两种方法 一是直接计算Mn 二是将矩阵M对角化后计算Mn 2020 1 27 南通大学理学院计算科学与统计学系 68 科学出版社 对角化方法 将矩阵M对角化 需要找出一个可逆矩阵P和一个对角矩阵 使得M P P 1 于是 其中 而 1 2 3是的M特征值 故只需求得M的特征值和对应的特征向量 就可使M对角化 2020 1 27 南通大学理学院计算科学与统计学系 69 科学出版社 在MATLAB软件中输入命令M 1 0 5 0 0 0 5 1 0 0 0 p d eig M 得M的三个特征值为 1 1 2 0 5 3 0及对应的特征向量分别为 2020 1 27 南通大学理学院计算科学与统计学系 70 科学出版社 于是对角矩阵 和可逆矩阵P分别为 为了求逆矩阵 使用命令P 1 1 1 0 1 2 0 0 1 inv P 得 2020 1 27 南通大学理学院计算科学与统计学系 71 科学出版社 由 8 3 3 得 所以 这是用原始基因分数表示第n代作物总体中三种基因分数 显然 当n 时 有 这说明在极限情况下总体中所有作物都将是基因AA型 2020 1 27 南通大学理学院计算科学与统计学系 72 科学出版社 六 评注 式 8 3 3 反映了第n 1代作物总体中三种基因分布向第n代作物总体中三种基因分布的转移规律 2020 1 27 南通大学理学院计算科学与统计学系 73 科学出版社 七 进一步的问题 某农场饲养的某种动物所能达到的最大年龄为15岁 将其分为三个年龄组 第一组0 5岁 第二组6 10岁 第三组11 15岁 动物从第二个年龄组开始繁殖后代 第二个年龄组的动物在其年龄段平均繁殖4个后代 第三年龄组的动物在其年龄段平均繁殖3个后代 第一年龄组和第二年龄组的动物能顺利进入下一个年龄组的存活率分别为0 5和0 25 假设农场现有三个年龄段的动物各1000头 计算5年后 10年后 15年后各年龄段动物数量 20年后农场三个年龄段的动物的情况会怎样 2020 1 27 南通大学理学院计算科学与统计学系 74 科学出版社 根据有关生物学研究结果 对于足够大的时间值k 有 1是莱斯利矩阵L的惟一正特征值值 请检验这一结果是否正确 如果正确 请给出适当的k的值 如果每五年平均向市场供应各年龄动物数都为s 在20年后农场动物不至灭绝的前提下 s应取多少为好 2020 1 27 南通大学理学院计算科学与统计学系 75 科学出版社 8 4城市交通流量 随着经济的发展 人民收入的增加 汽车等机动车辆快速增加 城市交通日益繁忙 在一些没有立交桥的交叉路口 机动车辆排长队等候绿灯的情况经常发生 目前大多数城市交叉路口红绿灯时间是固定的 这是机动车辆排长队等候绿灯的原因之一 了解机动车辆在交叉路口等候的车队长度 从而依据候车长度来调节红绿灯时间是解决机动车辆排长队等候绿灯的有效方法 一 问题的提出 2020 1 27 南通大学理学院计算科学与统计学系 76 科学出版社 城市交通网络通常由一些互相连接的路段和交叉路口组成 为简单和确定起见 本节讨论右图所示的交通网络 此交通网络由两条横向公路 两条纵向公路和四个交叉路口A B C D组成 公路都是单行线 方向如图所示 而且不考虑转弯 由A到B C的距离为1个单位 D到B C的距离为2个单位 2020 1 27 南通大学理学院计算科学与统计学系 77 科学出版社 二 问题分析 研究城市交通流量的目的是度量等候绿灯的机动车辆排队长度 从而通过调节红绿灯时间减少机动车辆等候时间 为了解决问题 各路口绿灯持续时间是控制变量 作为研究对象的每次绿灯开始时刻等候在各路口的机动车辆队伍长度则是状态变量 红绿灯是周期变化的 以这个周期为时间单位将时间离散化 通过代数方法 寻找机动车辆排队长度的状态转移规律 是解决问题的关键 2020 1 27 南通大学理学院计算科学与统计学系 78 科学出版社 三 模型假设 1 交通网络饱和 即各路口等候的车队足够长 以至在绿灯持续时间内有源源不断的机动车辆通过 2 4个交叉路口的红绿灯周期相同 绿灯开始时刻也相同 将每次绿灯开始时刻记作t 0 1 3 不计黄灯时间 横向 纵向 路口的绿灯时间等于纵向 横向 路口的红灯时间 4 绿灯持续时间内通过单向路口的车队长度与绿灯持续时间成正比 5 车队在交叉路口之间行驶1个单位距离所需时间为1个单位时间 即为1个红绿灯周期 2020 1 27 南通大学理学院计算科学与统计学系 79 科学出版社 四 建立模型 记时刻t等候在8个单行线路口的车队长度为xi t i 1 2 8 记时刻t开始的绿灯持续时间内通过单向路口i的车队长度为zi t i 1 2 8 记时刻t开始的红绿灯周期内到达单向路口i的车队长度为yi t i 1 2 8 由假设1可知 在任何时刻t t 0 1 2 xi t yi t z