卫星开关.ppt

2004年浙江大学数学建模竞赛
(B题)通讯卫星上的开关设置

地面上存在着n个接收站与n个发送站,而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示,若卫星可接收发送站i发射的信息并将信息传送回地面的接收站j时,矩阵中的元素pij =1,否则pij =0。通讯卫星上的接收发送任务也可以用一个矩阵T=(tij)来表示,其元素tij为需经通讯卫星传递的由i发点发送到j接收点的信息量的传送时间长度。由于技术上的原因,当发送站i在发送给接收站j信息时,它不能同时发送给别的接收站信息;同样,当接收站j在接收发送站i的信息时,也不能同时接收其他发送站发送的信息。你的任务是:
设计一组开关模式,k=1, …,r(注:r应当尽可能小),使得对任意给定的任务矩阵T,卫星开关设置均能完成要求的发接收任务。
设计一个算法,在发接收任务T给出后,可根据你设计的开关模式(k=1,…,r)求出各开关的使用时间λk,使得在完成预定传送任务的前提下使用各开关模式的总时间最短。
同样由于技术上的原因,开关模式的总数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),矩阵
均具有某些特殊的性质,例如其行和(及列和)均为同一常数。这样的矩阵构成一个线性空间(参见逻辑模型第一节 Dürer魔方),为减少开关模式的种类,可取此空间的一组基底作为开关模式。在使用这种开关模式时,无论T的元素tij怎么取,通讯卫星对每一发(收)点的开通时间总和是恒定的。在这种开关模式下,可按如下方式指派各开关模式的使用时间:
步1 先将T改变为, 满足:
(1) ≥T
(2)记,
步2 用Pk表示,即将分解为
(r为空间的维数)
将T化为的方法一般有无穷多种,如可如下化法:
令
事实上, ,(即通讯卫星传送总时间的下界)。
令
其中
用这种方法化例中的T,得到
的任一行(或列)中元素之和均为7。
定义1
称行和、列%%和均相等的矩阵为双随机矩阵(Doubly stochastic matrix)
定理1 (Birkhoff定理,1944)任一n阶双随机矩阵均可写成至多
(n-1)2+1个置换矩阵的非线性组合。
的分解可如下进行:
步1 选取由Pij>0可推出>0的置换矩阵P
步2 确定
步3 取,用- 代替
步4 若=0,停;否则,返回步1。
例2. 为方便起见,我们来分解一个元素均为非负整数的3阶双随机矩阵,
(由Birkhoff定理,r≤5)
解:取,λ=min {1, 3, 3 } =1
分解成
,再取
因min{ 5, 5, 3} = 3,又有
,取
于是又有
易得分解结果为:
尚需解决的问题是如何求P,使得Pij>0必有。读者不难发现,此问题可以通过求解一个两分图上的最大流(或最大匹配)来实现,计算量为O(n4),是多项式时间可解的。具体方法为:作一两分图,若,则作边(i, j),令边容量为1