- 相關(guān)推薦
研究通訊衛(wèi)星上的開(kāi)關(guān)設(shè)置問(wèn)題(一)
摘 要
本文研究通訊衛(wèi)星上的開(kāi)關(guān)設(shè)置問(wèn)題，具體的討論了開(kāi)關(guān)模式的優(yōu)化設(shè)計(jì)方法。
在發(fā)送接收任務(wù)矩陣給出后，我們證明了在完成預(yù)定任務(wù)的前提下，開(kāi)關(guān)模式使用總時(shí)間的下界是的最大行列和，并利用雙隨機(jī)矩陣的特殊性質(zhì)，證明了總存在一組開(kāi)關(guān)模式使得使用總時(shí)間等于的最大行列和，同時(shí)給出了相應(yīng)的算法，對(duì)任意給定的任務(wù)，設(shè)計(jì)出相應(yīng)的開(kāi)關(guān)模式組及對(duì)應(yīng)的使用時(shí)間，使得使用總時(shí)間達(dá)到最�。粚�(duì)于最少開(kāi)關(guān)模式數(shù)，本文得出如下結(jié)論：當(dāng)中零元素個(gè)數(shù)小于時(shí)，；對(duì)一般的任務(wù)矩陣，，此時(shí)只要求出完全覆蓋中非零元素的一組開(kāi)關(guān)模式，，使得盡量小即可，最后我們分析給出了最小值的一個(gè)上界。
針對(duì)任務(wù)三中給出的四個(gè)任務(wù)矩陣，模型求解結(jié)果如下：
T1：最少模式數(shù)3，最短時(shí)間18（兩者可同時(shí)達(dá)到）
T2：最少模式數(shù)3，最短時(shí)間3（兩者可同時(shí)達(dá)到）
T3：最少模式數(shù)3，最短時(shí)間13（兩者不能同時(shí)達(dá)到[9，13]或[3，14]）
T4：最少模式數(shù)8，最短時(shí)間509（兩者不能同時(shí)達(dá)到，[8，671]或[50，509]）
問(wèn)題重述
早期的通訊衛(wèi)星只允許單向發(fā)送信息，且一個(gè)接收站同一時(shí)刻只能接收一個(gè)發(fā)送站的信息。問(wèn)題的數(shù)學(xué)模型可以描述為：
在地面上存在著n個(gè)接收站與n個(gè)發(fā)送站，而在通訊衛(wèi)星上則設(shè)置了若干種開(kāi)關(guān)模式。開(kāi)關(guān)模式可用矩陣來(lái)表示，若衛(wèi)星可接收發(fā)射站發(fā)射的信息并將信息傳送回地面的接收站時(shí)，矩陣元素，否則。通訊衛(wèi)星的接發(fā)任務(wù)也可用一矩陣來(lái)表示，其元素為需經(jīng)通訊衛(wèi)星傳遞的由發(fā)點(diǎn)發(fā)送到接受點(diǎn)的信息量的傳送時(shí)間長(zhǎng)度。問(wèn)題要求在發(fā)送接受任務(wù)給出后設(shè)計(jì)一組開(kāi)關(guān)模式，及模式的使用時(shí)間， 完成以下任務(wù)：
任務(wù)一：
在發(fā)送接受任務(wù)給出后,設(shè)計(jì)一組開(kāi)關(guān)模式，,使得在完成預(yù)定任務(wù)前提下各開(kāi)關(guān)模式使用時(shí)間的總時(shí)間最短,即求解下列優(yōu)化問(wèn)題:
任務(wù)二：
在發(fā)送接受任務(wù)給出后, 設(shè)計(jì)一組開(kāi)關(guān)模式，,使得在完成預(yù)定任務(wù)前提下盡可能小, 即求解下列優(yōu)化問(wèn)題:
任務(wù)三:
就以下給出的四組任務(wù)矩陣，分別求一，二問(wèn)，給出相應(yīng)的開(kāi)關(guān)模式組及每個(gè)模式對(duì)應(yīng)的傳送時(shí)間。
假設(shè)
開(kāi)關(guān)模式之間切換時(shí)間為零
發(fā)送站和接收站一直處于正常工作狀態(tài)
符號(hào)說(shuō)明
開(kāi)關(guān)模式數(shù)
， 由個(gè)開(kāi)關(guān)模式組成的一個(gè)開(kāi)關(guān)模式組
通訊衛(wèi)星上的發(fā)送接收任務(wù)矩陣
對(duì)應(yīng)的雙隨機(jī)矩陣
第個(gè)開(kāi)關(guān)模式的使用時(shí)間
任務(wù)矩陣的最大行列和
問(wèn)題分析
問(wèn)題要求設(shè)計(jì)一組開(kāi)關(guān)模式，及模式的使用時(shí)間，使其滿(mǎn)足相應(yīng)的條件。對(duì)給定的任務(wù)，首先必須滿(mǎn)足。我們很自然的想到模式數(shù)和使用總時(shí)間之間存在相互制約的關(guān)系，即限制開(kāi)關(guān)模式數(shù)量會(huì)導(dǎo)致 增大。
在本題的求解中，對(duì)任務(wù)一，為了獲得最短使用時(shí)間我們不考慮開(kāi)關(guān)模式數(shù)量；同樣對(duì)任務(wù)二，為了使盡量小，模型不對(duì)各個(gè)開(kāi)關(guān)模式的使用時(shí)間做限制。
因?yàn)殚_(kāi)關(guān)模式具有的特殊性質(zhì)，無(wú)論怎樣選取，矩陣的每一行列和將為，這樣的矩陣稱(chēng)為雙隨機(jī)矩陣。因此當(dāng)任務(wù)不是雙隨機(jī)矩陣時(shí)條件中的等號(hào)是不會(huì)成立的。我們考慮對(duì)做適當(dāng)?shù)霓D(zhuǎn)化以利用雙隨機(jī)矩陣的性質(zhì)解決問(wèn)題。
模型建立與求解
由于技術(shù)上的原因，當(dāng)發(fā)送站在發(fā)送給接收站信息時(shí)，它不能同時(shí)發(fā)送給別的接收站信息；同樣，當(dāng)接收站在接收發(fā)送站的信息時(shí)，也不能同時(shí)接收其他發(fā)送站發(fā)送的信息。這一要求說(shuō)明，任一開(kāi)關(guān)模式應(yīng)具有以下性質(zhì)：
的每一行中有且只有一個(gè)1，每一列中也有且只有一個(gè)1；
所有的1均位于不同的行列中。
定義1 稱(chēng)滿(mǎn)足性質(zhì)（1），（2）的矩陣為置換矩陣。
任務(wù)一
求
定理1.1 對(duì)給定的任務(wù)矩陣，滿(mǎn)足條件的開(kāi)關(guān)使用總時(shí)間的下界為的最大行列和。
上述定理顯然是成立的，對(duì)任務(wù)矩陣，發(fā)送站需要使用衛(wèi)星傳送信息的時(shí)間為，同樣接收站需要使用衛(wèi)星接收信息的時(shí)間為，為了完成全部傳送任務(wù)，通訊衛(wèi)星要傳送完所有信息至少需要時(shí)間為，
定理1.2 總存在一組開(kāi)關(guān)模式，，滿(mǎn)足條件且。
為了證明定理1.2，下面引入雙隨機(jī)矩陣的概念。
定義1.1 稱(chēng)行列和均為同一個(gè)數(shù)的矩陣為雙隨機(jī)矩陣。
由置換矩陣的特殊性質(zhì)，無(wú)論怎樣選取，總是一個(gè)雙隨機(jī)矩陣，其行列和恒為。
對(duì)于雙隨機(jī)矩陣還有如下定理：
定理1.3 （Birkhoff定理，1944）任一階雙隨機(jī)矩陣均可寫(xiě)成至個(gè)置換矩陣的線(xiàn)性組合。（證明見(jiàn)參考文獻(xiàn)[1]）
這樣如果任務(wù)矩陣是一個(gè)雙隨機(jī)矩陣我們就可以將其分解為若干置換矩陣的線(xiàn)性組合，即，且此時(shí)等于的行列和。但是一般的任務(wù)矩陣是無(wú)法進(jìn)行以上分解的，因此先將轉(zhuǎn)化為雙隨機(jī)矩陣，滿(mǎn)足條件：
；
=（），==，為的最大行列和
這樣我們總能將分解為，且滿(mǎn)足=，而由定理1.1, 已經(jīng)是的下界。
由以上分析，只要設(shè)計(jì)出將轉(zhuǎn)化為和將分解為的方法就可以很好的解決任務(wù)一。
下面給出算法1和算法2，算法1將轉(zhuǎn)化為，算法2將雙隨機(jī)矩陣分解成的線(xiàn)形組合。
算法1：
令
，，
按如上方式求得=，滿(mǎn)足，且。
算法2：
Step1 選取有可推出的置換矩陣
Step2 令
Step3 取，
Step4 若，中止；否則，返回Step1
至此，定理1.2得到證明。
對(duì)任務(wù)一，當(dāng)發(fā)送接收任務(wù)給出后，先利用算法1將轉(zhuǎn)化為雙隨機(jī)矩陣，再利用算法2將分解為，這樣我們得到一組開(kāi)關(guān)模式，及模式的使用時(shí)間，滿(mǎn)足條件，以上分析已經(jīng)證明，這樣得到的是最小的。
任務(wù)二
求
若T中任意元素都大于零
此時(shí)只要找到一組，，且盡可能小即可，因?yàn)榇藭r(shí)只要令=就能滿(mǎn)足，而由置換矩陣的特點(diǎn)總可以找到n個(gè)置換矩陣，那么要滿(mǎn)足條件（2 .1），.
若中含有零元素，則可能減小，對(duì)一般的，要滿(mǎn)足， 顯然有.
令，，由以上分析問(wèn)題轉(zhuǎn)化為
若滿(mǎn)足條件（2.2），同1）只要令=就能滿(mǎn)足，
階置換矩陣共有個(gè)，當(dāng)較小時(shí)直接搜索容易求得結(jié)果，例如任務(wù)三中的，。
事實(shí)上直接求解問(wèn)題（2.2）是NP難的，當(dāng)太大時(shí)問(wèn)題無(wú)法直接求解。
我們考慮怎樣使r盡可能的小。因?yàn)楫?dāng)T中所有元素都非零時(shí)，，隨著零元素個(gè)數(shù)的增加將引起的減小。顯然當(dāng)零元素個(gè)數(shù)小于時(shí)仍然有成立。
定義2.1 對(duì)置換矩陣，若任意可推出，則稱(chēng)被零覆蓋。
容易理解，隨著中零元素個(gè)數(shù)的增加，當(dāng)正好有個(gè)互不重疊（任兩個(gè)沒(méi)有位置重合的1）的置換矩陣，被T零覆蓋，則。
與算法2類(lèi)似，可按如下方式求得：
算法3：
Step1 ，選取有可推出的置換矩陣，若不存在，終止，返回；否則，執(zhí)行Step2
Step2 ，， ，返回Step1
例如對(duì)任務(wù)三中的的求解結(jié)果滿(mǎn)足。
任務(wù)三
對(duì)題中給出的任務(wù)矩陣，，，分別求解第一問(wèn)和第二問(wèn)。
由任務(wù)一和任務(wù)二中得出的結(jié)論，解答如下：
:
求最小
利用算法1和算法2將T轉(zhuǎn)化為再分解如下：
, 對(duì)應(yīng)的.
求最小
不含零元素，取一組滿(mǎn)足條件（2.1）的開(kāi)關(guān)模式
min ，對(duì)應(yīng)的, .
:
求最小:
同:
min, 對(duì)應(yīng)的.
求最小:
取一組滿(mǎn)足條件（2.2）的開(kāi)關(guān)模式如下：
，對(duì)應(yīng)的.
:
求最小
同以上兩問(wèn)：
, 對(duì)應(yīng)的.
求最小:
取一組滿(mǎn)足條件（2.2）的開(kāi)關(guān)模式如下：
，對(duì)應(yīng)的 .
:
,對(duì)應(yīng)的模式數(shù)。
不含零元素，只需滿(mǎn)足條件（2.1）即可。
任選一組滿(mǎn)足條件的開(kāi)關(guān)模式，得到,對(duì)應(yīng)的總使用時(shí) 間 。
（對(duì)應(yīng)的開(kāi)關(guān)模式組及相應(yīng)的使用時(shí)間見(jiàn)附錄）
模型檢驗(yàn)與結(jié)果分析
通過(guò)對(duì)任務(wù)三中四個(gè)給定任務(wù)的求解已經(jīng)很好的檢驗(yàn)了我們建立的模型。
第一問(wèn)求最短使用總時(shí)間，四個(gè)任務(wù)矩陣的結(jié)果都已經(jīng)達(dá)到總使用時(shí)間的下界，并給出了相應(yīng)的開(kāi)關(guān)模式組，及對(duì)應(yīng)的使用時(shí)間，這已經(jīng)
是最優(yōu)的結(jié)果。求解過(guò)程中使用的算法都是多項(xiàng)式時(shí)間內(nèi)可解的，具有實(shí)際可行性。
模型對(duì)問(wèn)題的求解 最短時(shí)間 18 3 13 509
最少模式數(shù) 3 3 3 8
參考答案 最短時(shí)間 18 3 13 509
最少模式數(shù) 7 3 5 58
第二問(wèn)求最少開(kāi)關(guān)模式數(shù)，我們解出的結(jié)果較參考答案更優(yōu)。
模型對(duì)問(wèn)題的求解結(jié)果與參考答案比較如下：
求解結(jié)果很好的驗(yàn)證了我們所得結(jié)論的合理性和可操作性。
模型的進(jìn)一步討論
對(duì)于問(wèn)題第二問(wèn)求最少開(kāi)關(guān)模式數(shù)，我們分別對(duì)任務(wù)矩陣是否含有非零元素的情況做了討論，得出了一些相應(yīng)的結(jié)論。當(dāng)任務(wù)矩陣所含零元素個(gè)數(shù)小于時(shí)，能夠很好的得出最優(yōu)的結(jié)果。當(dāng)零元素較多且較大時(shí)，直接求解難度太大，近似結(jié)論并不能滿(mǎn)足結(jié)果最優(yōu)。設(shè)計(jì)復(fù)雜度較低的算法或者研究更高精度的近似解法是有待進(jìn)一步改進(jìn)的關(guān)鍵之處。
實(shí)際問(wèn)題中衛(wèi)星上不便設(shè)置太多的開(kāi)關(guān)模式。我們求得的最短使用總時(shí)間對(duì)應(yīng)的開(kāi)關(guān)模式數(shù)可達(dá)到，當(dāng)較大時(shí)將對(duì)實(shí)際使用造成困難。同樣當(dāng)達(dá)到最小時(shí)使用總時(shí)間將會(huì)變得較大，嚴(yán)重降低了衛(wèi)星的工作效率。我們可以考慮對(duì)模型進(jìn)行適當(dāng)?shù)母倪M(jìn)，在開(kāi)關(guān)模式數(shù)和使用總時(shí)間之間取得一個(gè)平衡，使得衛(wèi)星上設(shè)置的開(kāi)關(guān)模式數(shù)不太多又具有較高的工作效率。
現(xiàn)代通訊衛(wèi)星已經(jīng)允許一個(gè)發(fā)射站同時(shí)向多個(gè)接收站發(fā)送信息，有興趣的讀者可做相應(yīng)的改進(jìn)。1987年J.L.Lewandowski和C.L.Liu對(duì)此問(wèn)題進(jìn)行了較深入的研究，讀者可參考相關(guān)論文。
模型優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
方法簡(jiǎn)潔，可操作性強(qiáng)，對(duì)題中所給任務(wù)均能取得較好的結(jié)果。
缺點(diǎn)：
對(duì)于最小的求解，沒(méi)有給出對(duì)所有任務(wù)都適用的方法，只能得到其范圍，當(dāng)較大時(shí)不能保證能求得最優(yōu)解。
參考文獻(xiàn)
[1]Roger A.Horn,Charles R.Johnson著,楊奇譯,矩陣分析, 機(jī)械工業(yè)出版社, 2005
[2]姜啟源，數(shù)學(xué)建模，高等教育出版社，1998
附錄
解答:
求最小:
利用算法1和算法2將T轉(zhuǎn)化為再分解如下
, 對(duì)應(yīng)的.
求最小:
因?yàn)椴缓阍�，只需滿(mǎn)足條件（2.1）即可，任選一組滿(mǎn)足條件的開(kāi)關(guān)模式
對(duì)應(yīng)的, .
【研究通訊衛(wèi)星上的開(kāi)關(guān)設(shè)置問(wèn)題(一)】相關(guān)文章：
支票在ATM上的應(yīng)用問(wèn)題研究03-23
試論普通高校崗位設(shè)置與崗位聘用的問(wèn)題與對(duì)策研究03-20
高校專(zhuān)業(yè)設(shè)置與適應(yīng)區(qū)域經(jīng)濟(jì)發(fā)展問(wèn)題研究03-23
傳統(tǒng)知識(shí)保護(hù)的法律問(wèn)題研究(上)03-18
關(guān)于目前中國(guó)商法研究的幾個(gè)問(wèn)題（上）03-20
并聯(lián)均流高頻開(kāi)關(guān)電源的研究03-18
鈮酸鋰光開(kāi)關(guān)的驅(qū)動(dòng)電路的研究03-07
計(jì)算機(jī)開(kāi)關(guān)電源技術(shù)研究03-28
公務(wù)法人問(wèn)題研究12-06