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