《数学电工数模》PPT课件.ppt

电工数学建模竞赛 一总则 n全国大学生电工数学建模竞赛（以下简称 竞赛）是中国电机工程学会电工数学专委 会主办的面向全国大学生的科技活动，目 的是提高学生的综合素质、增强创新意识 、培养学生应用数学知识解决实际工程问 题的能力，激发学生学习数学的积极性， 同时也将推动高校的教学改革与教育创新 的进程 。 二竞赛内容 n竞赛题 目一般来源于电工、近代数学及 经济 管理等方面，经过 适当的简化、加 工的实际问题 ，主要包括： 1信息处理问题 ； 2控制理论及应用问题 ； 3运筹与决策问题 ； 4电路与电磁场理论相关问题 。 二竞赛内容 n参赛学生应学过普通高校的工科数学课程及相 关专业的专业基础知识，不要求参赛者预先掌 握深入的专门知识。竞赛题 目比较灵活，能够 使参赛学生充分发挥其创造能力。参赛者要根 据题目要求，完成一篇包括模型的假设、建立 和求解、算法的设计和计算机实现、结果的分 析和检验、模型的改进等方面的论文（即答卷 ）。答卷的评定以假设的合理性、建模的创造 性、结果的可行性和文字的清晰度为主要标准 。 三竞赛形式、规则和纪律 n1全国统一竞赛题目，采取网上竞赛方式，以 学校为单位进行。 2竞赛一般在每年11月末的三天内举行。 3本科生以队为单位参赛，每队3人，专业不 限。每队可设一名指导教师（或教师组），对 参赛学生进行赛前的辅导及赛前准备工作。竞 赛期间指导教师要回避参赛队员，禁止进行指 导或参与讨论。 三竞赛形式、规则和纪律 n4竞赛期间参赛学生可以使用各种图书资料、 计算机和软件以及在网上浏览，不能与队外任 何人讨论。 5竞赛题目将按照规定时间准时在指定的网站 公布，参赛队员在规定的时间内完成答卷，并 准时在网上交卷。 6各参赛院校应责成有关职能部门负责竞赛的 组织和纪律监督工作，保证竞赛的规范性和公 正性。 数学建模 数学模型（Mathematical Model） 是用数学符号、数学式子、程序、图形等对实际 课题本质属性的抽象而又简洁的刻划，它或解释 某些客观现象，或能预测未来的发展规律，或能 为控制某一现象的发展提供某种意义下的最优策 略或较好策略。 数学建模（Mathematical Modeling） 应用知识从实际课题中抽象、提炼出数学模型的 过程。 1.1 数学模型与数学建模数学模型与数学建模 1.了解问题的实际背景，明确建模目的，收集掌握 必要的数据资料。 2. 通过对资料的分析计 算， 找出起主要作用的因素 ，经必要的精炼、简化，提出若干符合客观实际的假 设。 3.在所作假设的基础上，利用适当的数学工具去刻 划各变量之间的关系，建立相应的数学结构 即 建立数学模型。 4.模型求解。 5.模型的分析与检验。 在难以得出解析解时，也 应当借助 计算机 求出数值 解。 1.21.2 数学建模的一般步骤数学建模的一般步骤 实体信 息(数据) 假设建模求解验证应用 1.31.3 数学模型的分类数学模型的分类 分类标准分类标准具体类别具体类别 对某个实际问题 了解的深入程度 白箱模型、灰箱模型、黑箱模型 模型中变量的特 征 连续连续 型模型、离散型模型或确定性 模型、随机型模型等 建模中所用的数 学方法 初等模型、微分方程模型、差分方 程模型、优优化模型等 研究课题的实际 范畴 人口模型、生态态系统统模型 、交通 流模型、经济经济 模型、 基因模型等 数学建模实践的 每一步中都 蕴含着能力上的 锻炼，在 调查研究阶段，需 要用到观察能力、分析能力和数据处理 能力等。在提出假设 时，又需要用到 想象力和归纳 简化 能力。 在真正开始自己的研究之前，还应当尽可能先了解一下 前人或别人的工作，使自己的工 作成为别人研究工作 的 继续而不是别人工作的重复，你可以把某些已知的研究结 果用作你的假设，去探索新的奥秘。因此我们还应当学会 在尽可能短的时间 内查到并学会我想应用的知识的本领。 还需要你多少要有点 创新的能力。这种能力不是生来就 有的，建模实践就为你提供了一个培养创新能力的机会。 1.41.4 数学建模与能力的培养数学建模与能力的培养 开设数学建模课的主要目的为了提高学 生的综合素质，增强 应用数学知识 解决实际问 题的本领。 例1 某人平时下班总是按预定时间到达某处，然 然后他妻子开车接他回家。有一天，他比平时提早 了三十分钟到达该处，于是此人就沿着妻子来接他 的方向步行回去并在途中遇到了妻子，这一天，他 比平时提前了十分钟到家，问此人共步行了多长时 间？ 1.5 1.5 一些简单实例一些简单实例 似乎条件不够哦 。 换一种想法，问题就迎刃而 解了。假如他的妻子遇到他后仍 载着他开往会合地点，那么这一 天他就不会提前回家了。提前的 十分钟时间从何而来？ 显然是由于节省了从相遇点到 会合点，又从会合点返回相遇点这一 段路的缘故，故由相遇点到会合点需 开5分钟。而此人提前了三十分钟到 达会合点，故相遇时他已步行了二十 五分钟。 请思考一下，本题解答中隐含了哪些假设请思考一下，本题解答中隐含了哪些假设 ？ 例2 交通灯在绿灯转换成红灯时，有一 个过渡状态亮一段时间的黄灯。请分 析黄灯应当亮多久。 设想一下黄灯的作用是什么，不难看 出，黄灯起的是警告的作用，意思是 马上要转红灯了，假如你能停住，请 立即停车。停车是需要时间的，在这 段时间内，车辆仍将向前行驶一段距 离 L。这就是说，在离街口距离为 L处 存在着一条停车线（尽管它没被画在 地上），见图。对于那些黄灯亮时已 过线的车辆，则应当保证它们仍能穿 过马路。 马路的宽度 D是容易测得 的，问题的关键在 于L 的确定。为确定 L，还应当将 L划分为两段：L1 和L2，其中 L1是司机在发现黄灯亮及判断应当刹 车的反应时间内驶过的路程 ，L2为刹车制动后 车辆驶过的路程。L1较容易计算，交通部门对司 机的平均反应时间 t1早有测算，反应时间过长 将考不出驾照），而此街道的行驶速度 v 也是 交管部门早已定好的，目的是使交通流量最大， 可另建模型研究，从而 L1=v*t1。刹车距离 L2 既可用曲线拟合方法得出，也可利用牛顿第二定 律计算出来 。 黄灯究竟应当亮多久现在已经变得清楚多了。第 一步，先计算出 L应多大才能使看见黄灯的司机 停得住车。第二步，黄灯亮的时间应当让已过线 的车顺利穿过马路，即T 至少应当达到 （L+D） /v。 D L 初等模型 某航空母舰派其护卫舰去搜寻其跳伞的飞行 员，护卫舰找到飞行员后，航母通知它尽快 返回与其汇合并通报了航母当前的航速与方 向，问护卫舰应怎样航行，才能与航母汇合。 2.1 舰艇 的会合 令：则上式可简记成 ： A(0,b ) X Y B(0,-b) P(x,y) O 航母 护卫舰 1 2 即： 可化为： 记v2/ v1=a通常a1 则 汇合点 p必位于此圆上。 （护卫舰的路线方程） （航母的路线方程 ） 即可求出P点的坐标和 2 的值。 本模型虽简单，但分析 极清晰且易于实际应用 2.2 双层玻璃的功效 在寒冷的北方， 许多住房的玻璃窗都是双层 玻璃的，现在我们来建立一个简单 的数学模 型，研究一下双层玻璃到底有多大的功效。 比较两座其他条件完全相同的房屋，它们的 差异仅仅在窗户不同。 不妨可以提出以下 假设： 1、设室内热量的流失是热传导 引起的，不存在户内外的空气对 流。 2、室内温 度T1与户外温 度T2均 为常数。 3、玻璃是均匀的，热传导系数 为常数。 设玻璃的热传导系数 为k1，空气的 热传导系数 为k2，单位时间通过单 位面积由温度高的一侧流向温度低 的一侧的热量为 d dl 室 外 T2 室 内 T1 Ta Tb 由热传导公式 =kT/d 解得： 此函数的图形为 d d 室 外 T2 室 内 T1 类似有 一般故 记h=l/d并令f(h)= 0 12345678910 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 h f(h) 考虑到美观和使用上 的方便，h不必取得过大，例如，可 取h=3，即l=3d，此时房屋热量的损失不超过单层玻璃窗 时的 3% 。 2.3 崖高的估算 假如你站在崖顶且身上带着一只具有跑表功 能的计算器，你也许会出于好奇心想用扔下 一块石头听回声的方法来估计山崖的高度， 假定你能准确地测定时间，你又怎样来推算 山崖的高度呢，请你分析一下这一问题。 我有一只具有跑 表功能的计算器。 方法一 假定空气阻力不计，可以直接利用自由落体运动的公式 来计算。例如， 设t=4秒，g=9.81米/秒2，则可求得h78.5 米。 我学过微积分，我可以做 得更好，呵呵。 除去地球吸引力外，对石块下落影响最大的当 属空气阻力 。根据流体力学知识，此时可设空气阻力正比于石块下落 的速度，阻力系 数K为常数，因而，由牛顿第二定律可得 ： 令k=K/m，解得 代入初始条件 v(0)=0，得c=g/k，故有 再积分一次，得： 若设k=0.05并仍设 t=4秒，则可求 得h73.6米。 听到回声再按跑表，计算得到的时间中包含了 反应时间 进一步深入考虑进一步深入考虑 不妨设平均反应时间 为0.1秒 ，假如仍 设t=4秒，扣除反 应时间后应 为3.9秒，代入 式，求得h69.9米。 多测几次，取平均值 再一步深入考虑再一步深入考虑 代入初始条 件h(0)=0，得到计算山崖高度的公式： 将e-kt用泰勒公式展开并 令k 0+ ，即可 得出前面不考虑空气阻力时的结果。 还应考虑回声传回来所需要的时间。为此，令石块下落 的真正时间 为t1，声音传回来的时间记 为t2，还得解一个 方程组： 这一方程组是 非线性的，求 解不太容易， 为了估算崖高 竟要去解一个 非线性主程组 似乎不合情理 相对于石块速度，声音速度要快得多，我们可 用方法二先求一次 h，令t2=h/340，校正t，求石 块下落时间 t1t-t2将t1代入式再算一次，得出 崖高的近似值。例如， 若h=69.9米，则 t20.21 秒，故 t13.69秒，求得 h62.3米。 最小二乘法 插值方法 当问题的机理非常不清楚难以直接利用其他知 识来建模时，一个较为自然的方法是利用数据 进行曲线拟合，找出变量之间的近似依赖关系 即函数关系。 2.4 经验模型 最小二乘法最小二乘法 设经实际测量已得 到n组数据（xi , yi），i=1, n。将数据 画在平面直角坐标系中，见 图。如果建模者判断 这n个点很 象是分布在某条直线附近，令 该直线方程 为y=ax+b，进而 利用数据来求参 数a和b。由于该直线只是数据近似满足的 关系式，故 yi-(axi+b)=0一般不成立，但我们希望 最小 此式对a和b的偏导数均 为0， 解相应方程组，求得： y=ax+b y O (xi ,yi) x 其中 和 分别为xi和yi 的平均值 如果建模者判断变量间的关系并非线性关系而是其他类型的函数 ，则可作 变量替换使之转化为线性关系或用类似方法拟合。 显然，运动员体重越大，他能举起的重量也越大，但举重 成绩和运动员体重到底是怎样关系的，不同量级运动员的 成绩又如何比较优劣呢？运动成绩是包括生理条件、心理 因素等等众多相关因素共同作用的结果，要建立精确的模 型至少现在还无法办到。但我们拥有大量的比赛成绩纪录 ，根据这些数据不妨可以建立一些经验模型。为简单起见 ，我们不妨取表中的数据为例。 例1（举重成绩的比较） 举重是一种一般人都能看懂的运动，它共分 九个重量级，有两种主要的比赛方法：抓举 和挺举。 表中给出了到1977年底为止九个 重量级的世界纪录。 255200110以上 237.5185110 22118090 207.517082.5 195157.575 180141.567.5 161.513060 151120.556 14110952 挺举举（公斤）抓举举（公斤） 成绩绩 重量级级（上限体 重） 模型1（线性模型） 将数据画在直角坐标系中可以发现，运动成绩与体 量近似满足线性关系，只有110公斤级有点例外，两 项成绩都显得较低。应用前面叙述的方法可求出近 似关 系式L=kB+C，其中B为体重，L为举重成绩。 你在作图 时L轴可以放 在50公斤或52公斤处，因为 没有更轻级别的比赛，具体计算留给同学自己去完 成。 模型2（幂函数模型） 线性模型并未得到广泛的接受，要改进结果，能够 想到的自然首先是幂函数模型，即令L=kBa，对此式 取对数，得 到lnL=lnk+a lnB。将原始数据也取对数 ，问题即转化了线性模型，可用最小二乘法求出参 数。几十年前英国和爱尔兰采用的比较举重成绩优 劣 的Austin公式：L=L/B3/4就是用这一方法求得的 。 模型3（经典模型） 经典模型是根据生理学中的已知结果和比例关系推导出来的 公式，应当说，它并不属于经验公式。为建立数学模型，先 提出如下一些假设： (1)举重成绩正比于选手肌肉的平均横截 面积A，即L=k1A (2)A正比于身高 L的平方，即 A=k2L2 (3)体重正比于身高 L的三次方， 即B=k3L3 根据上述假设，可得 显然，K越大则成绩越好，故可用 来比较选手 比赛成绩的优劣。 模型4（O Carroll公式） 经验公式的主要依据是比例关系，其假设条件非常粗糙，可 信度不大，因而大多数人认为它不能令人信服。1967年，O Carroll基于动物学和统计分析得出了一个现在被广泛使用的 公式。O Carroll模型的假设条件是： (1) L=k1Aa, am）。由 于公式量纲齐次当且仅当它可用无量纲的量表示，故方 程当且仅当可写 成f(1，, m)=0时才是量纲齐次的， 定理证毕。 证 设x1,xk为方程中出现的变量与常数, ,对这些变量与 常数的任一乘积 ,令 函数g建立了xi(i=1,k)的乘积所组成的空间 与k维欧氏 空间之间的一个一一对应。现设涉及到的基本量纲有n个, 它们 为y1,yn.用这些基本量纲来表达 该xi的乘幂,设此乘 幂的量纲为 令 易见dg-1是k维欧氏空间 到n维欧氏空间的一个变换，这里 的g-1为g的逆变换。 例4（理想单摆的摆动周期） 考察质量集中于距支点为 l 的质点上的无阻 尼 单摆，（如图），其运动为某周 期 t 的 左右摆动，现希望得到周期 t 与其他量之间 的 关系。 l mg 考 察 ， 的 量 纲 为 M a L b + d T c- 2 b 若 无 量 纲 ， 则 有 量纲分析法虽然简单，但使用时在技巧方面的要求较高，稍 一疏忽就会导出荒谬的结果或根本得不出任何有用的结果。 首先，它要求建模者对研究的问题有正确而充分的了解，能 正确列出与该问题相关的量及相关的基本量纲，容易看出， 其后的分析正是通过对这些量的量纲研究而得出的，列多或 列少均不可能得出有用的结果。其次，在为寻找无量纲量而 求解齐次线性方程组时，基向量组有无穷多种取法，如何选 取也很重要，此时需依靠经验，并非任取一组基都能得出有 用的结果。此外，建模者在使用量纲分析法时对结果也不应 抱有不切实际的过高要求，量纲分析法的基础是公式的量纲 齐次性，仅凭这一点又怎么可能得出十分深刻的结果，例如 ，公式可能包含某些无量纲常数或无量纲变量，对它们之间 的关系，量纲分析法根本无法加以研究。 2.7 赛艇成绩的比较(比例模型) 八人赛艇比赛和举重比赛一样，分成86公斤 的重量级和 73公斤的轻量级。1971年， T.A.McMahon比较了1964-1970年期间两次 奥运会和两次世锦赛成绩，发现 86公斤级比 73公斤级的成绩大约好5%，产生这一差异的 原因何在呢？ 我们将以L表示轻量级、以H表示重 量级，用S表示赛艇的浸水面积，v 表示赛艇速度，W表示选手体重，P 表示选手的输出功率，I表示赛程， T表示比赛成绩（时间）。 考察优秀赛艇选手在比赛中的实际表现可以发现，整个赛程大 致可以分三个阶段， 即初始时刻的加速阶段、中途的匀速阶 段和到达终点的冲刺阶段 。由于赛程较长，可以略去前后两 段而只考虑中间一段 ，为此，提出以下建模假设。 （1）设赛艇浸水部分的摩擦力是唯一阻力，摩擦力f正比 于 Sv2,（见流体力学），空气阻力等其他因素不计。 （2）同一量级的选手有相同的体重W，选手的输出功 率P 正比于W，且效率大体相同。 由假设1，故 竞赛成绩 记比例系数 为k，则有： 故 由假设2， 故 令WH=86,WL=73,则有 由于SL略小于SH，故轻量级所化时间比重量级所化时间 约 多5%左右。 2.8 方桌问题 将一张四条腿的方桌放在不平的地面上，不 允许将桌子移到别处，但允许其绕中心旋转 ，是否总能设法使其四条腿同时落地？ 不附加任何条件，答案 显然 是否定的， 因此我们假设 （1）地面为连续曲面 （2 ）方桌的四条腿长度相同 （3）相对于地面的弯曲程 度而言，方桌的腿是足够长 的 （4 ）方桌的腿只要有一点接触 地面就算着地。 总可以使三条腿 同时着地。 现在，我们来证明：如果上述假设条件成立，那么答案是肯定 的。以方桌的中心为坐标原点作直角坐标系如 图所示，方桌 的四条腿分别在A、B、C、D处，A、C的初始位置在x轴上， 而B、D则在y轴上，当方桌绕中 心0旋转时，对角线 AC与x轴 的夹角记为。 容易看出，当四条腿尚未全部着地时，腿到地面的距离是不确 定的。为消除这一不确定性，令 f()为A、C离地距离之和， g()为B、D离地距离之和，它们的值 由唯一确定。由假设（1 ），f()、g()均为的连续函数。又 由假设（3），三条腿总能 同时着地， 故f()g()=0必成立（ ）。不妨设 f(0)=0,g(0)0（若g(0)也为0，则初始时刻已四条腿着地，不必 再旋转），于是问题归结为： y x C D A B o 已知f()、g()均为的连续函数，f(0)=0,g(0)0且对任意有 f()g()=0，求证存在某一0，使f(0)=g(0)=0。 （证法一）当=/2时，AC与BD互换位置，故f(/2)0 , g(/2)=0。作h()=f()-g()，显然，h()也是的连续函数， h(0)=f(0)-g(0)0，由连续函数的取 零值定理，存在 o，00,g(/2)=0。令o =sup |f ()=0，00，总有0且0 。因为f(0+)g (o+)=0，故必有g (0+)=0，由可任意小 且g连续，可知必 有 g (0)=0，证毕。证法二除用 到f 、g的连续性外，还用到了上确界的性质。 在解决实际问题时，注意观察和善于想象是十分重要的， 观察与想象不仅能发现问题隐含的某些属性，有时还能顺 理成章地找到解决实际问题的钥匙。本节的几个例子说明 ，猜测也是一种想象力。没有合理而又大胆的猜测，很难 做出具有创新性的结果。开普勒的三大定律（尤其是后两 条）并非一眼就能看出的，它们隐含在行星运动的轨迹之 中，隐含在第谷记录下来的一大堆数据之中。历史上这样 的例子实在太多了。在获得了一定数量的资料数据后，人 们常常会先去猜测某些结果，然后试图去证明它。猜测一 经证明就成了定理，而定理一旦插上想象的翅膀，又常常 会被推广出许多更为广泛的结果。即使猜测被证明是错误 的，结果也决不是一无所获的失败而常常是对问题的更为 深入的了解。 2.9最短路径与最速方案问题 例5（最短路径问题） 设有一个半径为 r 的圆形湖，圆心为 O。A、 B 位于湖的两侧，AB连线过O，见图。 现拟从A点步行到B点，在不得进入湖中的限 制下，问怎样的路径最近。 A B O r 将湖想象成凸出地面的木桩， 在AB间拉一根软线，当 线被拉紧时将得到最短路径。根据这样的想象，猜测 可以如下得到最短路径： 过A作圆的切线切圆于E，过 B作圆的切线切圆 于F。最短路径为由线 段AE、弧EF 和线段FB连接而成的连续曲线（根据对称性，AE，弧 EF，FB连接而成的连续曲线也是）。 EF E F 以上只是一种猜测，现在来证明这一猜测是正确的。为此， 先介绍一下凸集与凸集的性质。 定义2.1（凸集）称集合 R为凸集，若x1、x2R及0 ，1，总有x1+（1-）x2R。即若x1、x2R，则x1、x2 的连线必整个地落 在R中。 定理2.2（分离定理）对平面中的凸 集R与R外的一点K， 存在直线 l , l 分离R与K，即R与K分别位于 l 的两侧（注： 对一般的凸 集R与R外的一点K，则存在超平面分 离R与K ），见图。 k l R 下面证明猜想 猜测证明如下： （方法一）显然， 由AE、EF、FB及AE，EF，FB围成 的区域 R是一凸集。利用分离定理易证最短径不可能经过R 外的点，若不然，设 为最短路径，过R外的一点M，则 必存在直 线l分离M与R，由于路径是连续曲线，由A沿 到M，必交l于M1，由M沿到B又必交l于M2。这样，直线 段M1M2的长度必小于路 径M1MM2的长度，与是A到B的 最短路径矛盾，至此，我们已证明最短路径必在凸集R内。 不妨设路径经湖的上方到达B点，则弧EF必在路径F上，又 直线段AE是由A至E的最短路径，直线FB是由F到B的最短 路径，猜测得证。 A B O r EF E F M1 M2 M l 还可用微积分方法求弧长，根据计算证 明满足限止条件的其他连续曲线必具有 更大的长度；此外，本猜测也可用平面 几何知识加以证明等。 根据猜测不难看出， 例5中的条件可以大大放 松，可以不必 设AB过圆心，甚至可不必设湖 是圆形的。例如对 下图，我们可断定由A至B 的最短路径必 为l1与l2之一，其证明也不难类 似给出。 A B l1 l2 D 到此为止，我们的研讨还只局限于平面之中 ，其实上述猜测可十分自然地推广到一般空 间中去。1973年，J.W.Craggs证明了以上结 果： 若可行区域的边界是光滑曲面。则最短路径必由下列弧组 成，它们或者是空间中的自然最短曲线，或者是可行区域 的边界弧。而且，组成最短路径的各段弧在连接点处必定 相切。 例6 一辆汽车停于 A处并垂直于AB方向，此 汽车可转的最小圆半径为 R，求不倒车而由 A到B的最短路径。 解（情况1）若|AB|2R，最短路径由 弧AC与切线BC组 成（见图 ）。 （情况2）若|AB|0为推力，fS，故由连续函数的性质存在 某Tb4，可再和b6比（若a80，对任 意正整数N，总可找到一个大于N的正整数n及D的一个规模为n的实例，对 这一实例有fB(D,n)=O (2kn)，则称B为求解问题D的一个指数算法。 多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认 为是“坏”算法，因为它只能求解规模极小的实例。 下面的表1列出了在规模大约为n时各类算法的计算量，而表2 则反映了当计算机速度提高10倍、100倍时，各类算法在1小时 内可求解的问题的模型的增长情况，（前三个是多项式时间的 ，后两个是指数时间的） 表1 几个多项式和指数时间复杂性函数增长情况 算法要求的计计算量 规规模n的近似值值 101001000 n101001000 nlogn336649966 n3103106109 2n10241.2710301.0510301 n!3628800101584102567 表2 1小时内可解的问题实例的规模 算法要求的计计算 量 用现现在计计算机用快10倍计计算机用快100倍计计算机 nN110N1100N1 nlognN28.2N267N2 n3N32.15N34.64N3 2n N4N4+3.32N4+6.64 n! N5N5+2N5+3 由定义1知4n2与2n2都是O(n2)，nlogn+3n是O(nlogn)，我们在以后分析时 间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通 过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率 的关键因素。 2004年浙江大学数学建模竞赛 （B题）通讯卫星上的开关设置 地面上存在着n个接收站与n个发送站，而在通讯卫星上则 设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示 ，若卫星可接收发送站i发射的信息并将信息传送回地面的 接收站j时，矩阵中的元素pij =1，否则pij =0。通讯卫星上 的接收发送任务也可以用一个矩阵T=（tij）来表示，其元 素tij为需经通讯卫星传递的由i发点发送到j接收点的信息量 的传送时间长度。由于技术上的原因，当发送站i在发送给 接收站j信息时，它不能同时发送给别的接收站信息；同样 ，当接收站j在接收发送站i的信息时，也不能同时接收其 他发送站发送的信息。你的任务是： n设计一组开关模式，k=1, ,r（注：r应当尽可能小），使 得对任意给定的任务矩阵T，卫星开关设置均能完成要求 的发接收任务。 n设计一个算法，在发接收任务T给出后，可根据你设计的 开关模式（k=1,r）求出各开关的使用时间k，使得在 完成预定传送任务的前提下使用各开关模式的总时间最短 。 n同样由于技术上的原因，开关模式的总数r有一个上限。当 需要传送的任务数数量较大时，仍无法分派任务。请你想 一些办法来解决这一困难，（当然，这时你可能要作出一 些牺牲，即传送时间可能会增加一些）。 问题及模型 问题的标准形式为：在地面上存在着n个收站与n个发战，而在通讯卫星上 则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示，若卫星可接收 发射站i发射的信息并将信息传送回地面的接收站j时，矩阵元素pij =1，否则 pij =0。通讯卫星的接发任务也可用一矩阵T=（tij）来表示，其元素tij为需经 通讯卫星传递的由i发点发送到j接受点的信息量的传送时间长度。问题要求 求r并设计一组开关模式Pk，k=1, ,r及模式Pk的使用时间k，使得在完成 预定传送任务的前提下各开关模式使用的总时间最短，即要求求解下面的 问题： 例1 设 这是一个有3个发送站与3个接收站的实例，tij在矩阵中已给出，例如 由发站1传送到收站1的通讯量为3单位时间等。 分析 容易看出，三个发站需传送的时间分别为6、5、5；而三个收站需接 收的时间分别为6、3、7。为完成全部传送任务，通讯卫星总传送时间至少 应为7单位时间，即的下界为7。 由于技术上的原因，当发站i在发送给收站j信息时，它不能同时发送给别的 收站信息；同样，当收站j在接收发站i的信息时，也不能同时接收其他发站 发送的信息。这一要求说明，任一开关模式Pk应具有以下性质：（1）Pk的 每一行中有且只有一个1，每一列中也有且只有一个1；（2）所有的1均位 于不同的行列中。 满足（1）、（2）的矩阵 被称为置换矩阵，n阶置换矩阵Pk共有n!个，当n 较大时，我们不可能在通讯卫星上设置这么多种不同的开关模式。因而，为 了设计出切实可行的开关模式，我们还得另想办法。 （设计方法1） 注意到Pk每行（或列）元素之和均为1，故不管如何指派开关的使用时间（ 即不论如何取k），矩阵 均具有某些特殊的性质，例如其行和（及列和）均为同一常数。这样的矩 阵构成一个线性空间（参见逻辑模型第一节 Drer魔方），为减少开关模 式的种类，可取此空间的一组基底作为开关模式。在使用这种开关模式时 ，无论T的元素tij怎么取，通讯卫星对每一发（收）点的开通时间总和是恒 定的。在这种开关模式下，可按如下方式指派各开关模式的使用时间： 步1 先将T改变为 ， 满足： （1） T （2）记 ， 步2 用Pk表示 ，即将 分解为 （r为空间的维数） 将T化为 的方法一般有无穷多种，如可如下化法： 令 事实上， ，（即通讯卫星传送总时间的下界）。 令 其中 用这种方法化例中的T，得到 的任一行（或列）中元素之和均为7。 定义1 称行和、列%和均相等的矩阵为双随机矩阵（Doubly stochastic matrix） 定理1 （Birkhoff定理，1944）任一n阶双随机矩阵均可写成至多 （n1）2+1个置换矩阵的非线性组合。 的分解可如下进行： 步1 选取由Pij0可推出 0的置换矩阵P 步2 确定 步3 取 ，用 代替 步4 若 =0，停；否则，返回步1。 例2. 为方便起见，我们来分解一个元素均为非负整数的3阶双随机矩阵， （由Birkhoff定理，r5） 解：取 ，=min 1, 3, 3 =1 分解成 ，再取 因min 5, 5, 3 = 3，又有 ，取 于是又有 易得分解结果为： 尚需解决的问题是如何求P，使得Pij0必有 。读者不难发现，此问 题可以通过求解一个两分图上的最大流（或最大匹配）来实现，计算量 为O(n4)，是多项式时间可解的。具体方法为：作一两分图，若 ， 则作边（i, j），令边容量为1，这样，可作出P的充要条件是该最大流问 题的最大流量为n。对例9.33，n=3。由于所有 ，先取 ， P1为 相应的两分图为： 于是又可求得 ，相应的两分图为： 又可得 ，如此下去，直到作不出P为至， 由于 的特殊性质及Birkhoff定理，上述分解必能在不超过r= (n1)2 + 1步内终止。 上述开关设计方法要求在通讯卫星上设置(n1)2 + 1种不同的开关模式 （即Pk），当n稍大时，(n1)2 + 1仍显得太大而使得使用时不便。例如 ，当n=41时，(n1)2 + 1=| 60 |。为实用方便，人们研究了限止开关模式 个数的相应问题。 若要求rn，即要求通讯卫星上至多设置n种开关模式，则问题化为令rn ，求不超过n个置换矩阵Pk及k，使之满足： min S.t 为了使任意一对发射法与接收站之间的传送均为可能实现的，自然应要求 Pk满足 （5.1） （5.2） （右面的矩阵有n2个值为1的分量，每一Pk 恰有n个1分量）故r=n。 容易看出，（5.1）隐含着T的每一元素只能被唯一的P复盖，即T的元素在 分解中是不可分割的，这当然是一个好性质，使实际操作时较为方便，但 可惜的是对一般的双随机矩阵，分解很可能无解。 例3 若取 ， ， （注意：T已是双随机矩阵，行和列和均为10） 则min S.t 的解为1=3，2=4，3=5。 （大于10）而 但等号经常