【正文】 2023年 2月 27日星期一 12時 19分 25秒 12:19:2527 February 2023 ? 1一個人即使已登上頂峰，也仍要自強不息。 2023年 2月 27日星期一 下午 12時 19分 25秒 12:19: ? 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。勝人者有力，自勝者強。 :19:2512:19Feb2327Feb23 ? 1越是無能的人，越喜歡挑剔別人的錯兒。 , February 27, 2023 ? 閱讀一切好書如同和過去最杰出的人談話。 2023年 2月 27日星期一 12時 19分 25秒 12:19:2527 February 2023 ? 1空山新雨后，天氣晚來秋。 。 :19:2512:19:25February 27, 2023 ? 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 :19:2512:19Feb2327Feb23 ? 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 , February 27, 2023 ? 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。 2023年 2月 27日星期一 12時 19分 25秒 12:19:2527 February 2023 ? 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 。 :19:2512:19:25February 27, 2023 ? 1他鄉(xiāng)生白發(fā)，舊國見青山。 :19:2512:19Feb2327Feb23 ? 1故人江海別，幾度隔山川。 , February 27, 2023 ? 雨中黃葉樹，燈下白頭人。他們設計了一個求解此問題的 O(n5)算法，有興趣的讀者可直接閱讀他們的論文。 (0, 1) | , i= 1, …, m。 1()n kkk?????由于技術(shù)水平的提高，目前通訊衛(wèi)星傳送信息已允許一個發(fā)射站同時向多個接收站發(fā)送信息，當然，同時發(fā)送的信息條數(shù)具有某一上限，例如上限為 v。首先，要求完成的任務矩陣是 T，在將T轉(zhuǎn)換成時我們可盡量使具有上述的特殊結(jié)構(gòu)（有興趣的讀者可自行研究這一問題），只要能做到這一點，即可給出一個達到下界的開關模式的指派方式。 41()k k k kkPQ?????讀者可將上述討論推廣到 n為一般偶數(shù)的情況，分析方法是完全類似的。例如，若令 4= 3=0，可得 2=1， 1=0，進而可求得 1=2， 4=3， 3=3及 2=4， 已達到下界。 當 n=4時， 11 0 0 00 1 0 00 0 1 00 0 0 1P?????????20 1 0 00 0 1 00 0 0 11 0 0 0P ?30 0 1 00 0 0 11 0 0 00 1 0 0P ?40 0 0 11 0 0 00 1 0 00 0 1 0P?????????10 0 0 10 0 1 00 1 0 01 0 0 0Q ???20 0 1 00 1 0 01 0 0 00 0 0 1Q ?30 1 0 01 0 0 00 0 0 10 0 1 0Q ?41 00 10 0 1 00 1 0 0Q ???1 4 2 3 3 2 4 14 3 1 2 2 1 3 4413 2 4 1 1 4 2 32 1 3 4 4 3 1 2()k k k kKABPQBA? ? ? ? ? ? ? ?? ? ? ? ? ? ? ???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ??? ? ? ?????? ? ? ? ????????????? ? ? ? ??? ? ? ????易見， 具有非常特殊的結(jié)構(gòu)，一般的偶數(shù)階雙隨機矩 陣，即使其元素是非負整數(shù)，也無法用 Pk、 Qk來分解。另一方面空間 的維數(shù)恰為 2 n－ 1，故 之一可任取，而通過方程組解得所有的 ，（只須注意保持其非負性即可） 1()n k k k kkPQ?????,kk??,kk??但當 n為偶數(shù)時，情況就不大相同了。） 現(xiàn)在，我們來分解例 ，令 = ，得方程組 TT31()k k k kkPQ?????1 3 2 2 3 13 2 1 1 2 32 1 3 3 1 21 4 55 3 2433? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ? ?求出各對角線與反對角線上的三個元素之和，并作一些簡單的消去運算； 將矩陣的所有元素相加，可得下面的方程組： 313212131 2 3 1 2 32102( ) ( ) 10????????? ? ? ? ? ????????????? ???? ? ? ? ? ? ??注意到（ ），易證空間 的維數(shù)為 5， 故 之一可任取，（稍加注意即可保持非負性）， 例如，令 μ3=0，求得 ，故有 31()k k k kkPQ?????,kk?? 1 2 1 2 32 , 1 , 2 , 3? ? ? ? ?? ? ? ? ?1 2 3 1 22 3 2 2T P P P Q Q? ? ? ? ?31( ) 10kkk??????讀者不難驗證，上述方法可推廣到 n是奇數(shù)的一般情況。Rendel證明，在給定滿足（ ）的置換矩陣 P1,…, Pn后，求解問題（ ）是 NP難的，從而不可能存在多項式時間算法，除非 P=NP。 3112kk????（大于 10）而 313 4 55 3 44 5 3kkkPT?????????????但等號經(jīng)常并不成立。 容易看出，（ ）隱含著 T的每一元素只能被唯一的 P復蓋，即 T的元素在分解中是不可分割的，這當然是一個好性質(zhì)，使實際操作時較為方便，但可惜的是對一般的雙隨機矩陣，分解很可能無解。為實用方便，人們研究了限止開關模式個數(shù)的相應問題。 30 1 00 0 11 0 0P?????????T上述開關設計方法要求在通訊衛(wèi)星上設置 (n－ 1)2 + 1種不同的開關模式（即 Pk），當 n稍大時， (n－ 1)2 + 1仍顯得太大而使得使用時不便。對例 ， n=3。讀者不難發(fā)現(xiàn)，此問題可以通過求解一個兩分圖上的最大流（或最大匹配）來實現(xiàn)，計算量為 O(n4)，是多項式時間可解的。 的分解可如下進行： T步 1 選取由 Pij0可推出 0的置換矩陣 P ijt步 2 確定 ? ?m in | 1ij ijtp? ??步 3 取 ，用 － 代替 ?TP?T步 4 若 =0，停；否則，返回步 1。 1 , , )nni ij j ijjir t c t i n j n??? ? ? ???用這種方法化例中的 T，得到 16 141557845512 13255T???????????????????的任一行（或列）中元素之和均為 7。 11m a x , 1 , , 。在使用這種開關模式時，無論 T的元素 tij怎么取，通訊衛(wèi)星對每一發(fā)（收）點的開通時間總和是恒定的。這樣的矩陣構(gòu)成一個線性空間（參見邏輯模型第一節(jié) D252。因而，為了設計出切實可行的開關模式，我們還得另想辦法。這一要求說明，任一開關模式 Pk應具有以下性質(zhì)：（ 1） Pk的每一行中有且只有一個 1，每一列中也有且只有一個 1；（ 2）所有的 1均位于不同的行列中。為完成全部傳送任務，通訊衛(wèi)星總傳送時間至少應為 7單位時間，即的下界為 7。問題要求求 r并設計一組開關模式 Pk， k=1, …, r及模式 Pk的使用時間 λk，使得在完成預定傳送任務的前提下各開關模式使用的總時間最短，即要求求解下面的問題： 1min r kk???1. r kkkS t P T???例 1 設 3 2 11042 1 2T???????????這是一個有 3個發(fā)送站與 3個接收站的實例， tij在矩陣中已給出，例如由發(fā)站 1傳送到收站 1的通訊量為 3單位時間等。開關模式可用矩陣 P=(pij)來表示，若衛(wèi)星可接收發(fā)射站 i發(fā)射的信息并將信息傳送回地面的接收站 j時，矩陣元素 pij =1，否則 pij =0。請你想一些辦法來解決這一困難，（當然，這時你可能要作出一些犧牲，即傳送時間可能會增加一些）。 ? 同樣由于技術(shù)上的原因，開關模式的總數(shù) r有一個上限。你的任務是： ? 設計一組開關模式， k=1, …,r （注： r應當盡可能?。?，使得對任意給定的任務矩陣 T，衛(wèi)星開關設置均能完成要求的發(fā)接收任務。通訊衛(wèi)星上的接收發(fā)送任務也可以用一個矩陣 T=（ tij）來表示，其元素 tij為需經(jīng)通訊衛(wèi)星傳遞的由 i發(fā)點發(fā)送到 j接收點的信息量的傳送時間長度。rer鑄造的銅幣 2023年浙江大學數(shù)學建模競賽 （ B題）通訊衛(wèi)星上的開關設置 地面上存在著 n個接收站與 n個發(fā)送站，而在通訊衛(wèi)星上則設置了若干種開關模式。 071???iii Qr 令： ，即 ????????????????????????6542317713526426174534375621rrrrrrrrrrrrrrrrrrrrrrrrrrrr????????????0000