多目標(biāo)規(guī)劃MATLAB2012年wgx

1、MATLABMATLAB求解多目標(biāo)規(guī)劃求解多目標(biāo)規(guī)劃江西江西師師范大范大學(xué)數(shù)學(xué)數(shù)信信學(xué)學(xué)院院吳吳根秀根秀一、一、0-1規(guī)劃的規(guī)劃的MATLAB求解求解數(shù)學(xué)模型：數(shù)學(xué)模型：MIN fx S.T. Ax=b Aeqx=beq x=0,1命令格式：命令格式：x = bintprog(f)x = bintprog(f, A, b)x = bintprog(f, A, b, Aeq, beq)x = bintprog(f, A, b, Aeq, beq, x0)x = bintprog(f, A, b, Aeq, beq, x0, options)x, fval = bintprog(.)x,fval,

2、 exitflag = bintprog(.)x, fval, exitflag, output = bintprog(.)數(shù)學(xué)模型：數(shù)學(xué)模型：MIN lambda S.T. F(x)-weight* lambda =goal(達(dá)到目標(biāo)）達(dá)到目標(biāo)） Ax=b（線性不等式約束）（線性不等式約束） Aeqx=beq（線性等式約束）（線性等式約束） C(x)=0（非線性不等式約束）（非線性不等式約束） Ceq(x)=0（非線性等式約束）（非線性等式約束） lb=x 1 % Two output arguments G = . % Gradients evaluated at xEndThe grad

3、ient consists of the partial derivative dF/dx of each F at the point x.二二、多目標(biāo)規(guī)劃的多目標(biāo)規(guī)劃的MATLAB求解求解二二、多目標(biāo)規(guī)劃的多目標(biāo)規(guī)劃的MATLAB求解求解v有關(guān)優(yōu)化參數(shù)設(shè)置：有關(guān)優(yōu)化參數(shù)設(shè)置：voptions = optimset(GradConstr,on）約束條件的）約束條件的梯度方向參數(shù)設(shè)置為梯度方向參數(shù)設(shè)置為on時，用下列函數(shù)定義：時，用下列函數(shù)定義：function c,ceq,GC,GCeq = mycon(x)c = . % Nonlinear inequalities at xceq = .

4、 % Nonlinear equalities at xif nargout 2 % Nonlcon called with 4 outputs GC = . % Gradients of the inequalities GCeq = . % Gradients of the equalitiesEnd注意：一般注意：一般 weight=abs(goal)模型：模型：x=(A+BKC)x+Bu，設(shè)計(jì)，設(shè)計(jì)K滿足目標(biāo)：滿足目標(biāo)： Y=Cx1）循環(huán)系統(tǒng)）循環(huán)系統(tǒng)的的特征值（由命令特征值（由命令eig(A+B*K*C)確定）的目標(biāo)為確定）的目標(biāo)為goal = -5,-3,-12）K中元素均在中元素

5、均在-4,4中中; 設(shè)特征值的設(shè)特征值的weight= abs(goal),定義目標(biāo)函數(shù)定義目標(biāo)函數(shù)F如下：如下： function F = eigfun(K,A,B,C)F = sort(eig(A+B*K*C); % Evaluate objectives，由小到大排列，由小到大排列優(yōu)化程序?yàn)椋簝?yōu)化程序?yàn)椋篈 = -0.5 0 0; 0 -2 10; 0 1 -2;B = 1 0; -2 2; 0 1;C = 1 0 0; 0 0 1; K0 = -1 -1; -1 -1; % Initialize controller matrixgoal = -5 -3 -1; % Set goal

6、values for the eigenvaluesweight = abs(goal) % Set weight for same percentagelb = -4*ones(size(K0); % Set lower bounds on the controllerub = 4*ones(size(K0); % Set upper bounds on the controlleroptions = optimset(Display,iter); % Set display parameterK,fval,attainfactor = fgoalattain(K)eigfun(K,A,B,

7、C). goal,weight,lb,ub,options)二二、舉例舉例-有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題v運(yùn)行結(jié)果如下運(yùn)行結(jié)果如下vActive constraints:v 1v 2v 4v 9v 10vK = v -4.0000 -0.2564v -4.0000 -4.0000vfval =v -6.9313v -4.1588v -1.4099vattainfactor = v -0.3863二二、舉例舉例-有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題如果至少保證如果至少保證38.63%的目標(biāo)精確匹配，設(shè)置的目標(biāo)精確匹配，設(shè)置GoalsExactAchieve參數(shù)值為

8、參數(shù)值為3v options = optimset(GoalsExactAchieve,3);v K,fval,attainfactor = fgoalattain(.v (K)eigfun(K,A,B,C),K0,goal,weight,lb,ub,.options)v After about seven iterations, a solution is v K = v -1.5954 1.2040v -0.4201 -2.9046v fval =v -5.0000v -3.0000v -1.0000v attainfactor = v 1.0859e-20表明目標(biāo)已完全匹配表明目標(biāo)已完全

9、匹配二二、舉例舉例-有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題有關(guān)循環(huán)控制系統(tǒng)優(yōu)化問題 初等模型舉例初等模型舉例 常見類型常見類型v定性模型定性模型v經(jīng)驗(yàn)公式（擬合、插值）經(jīng)驗(yàn)公式（擬合、插值）v量綱分析量綱分析v比例模型比例模型 2.1 崖高的崖高的估算估算假如你站在崖頂且身上帶著一只具有跑表功假如你站在崖頂且身上帶著一只具有跑表功 能的計(jì)算器，你也許會出于好奇心想用扔下能的計(jì)算器，你也許會出于好奇心想用扔下 一塊石頭聽回聲的方法來估計(jì)山崖的高度，一塊石頭聽回聲的方法來估計(jì)山崖的高度， 假定你能準(zhǔn)確地測定時間，你又怎樣來推算假定你能準(zhǔn)確地測定時間，你又怎樣來推算 山崖的高度呢，請你分析一下這一問題。山崖的高度

10、呢，請你分析一下這一問題。我有一只具有跑我有一只具有跑 表功能的計(jì)算器。表功能的計(jì)算器。方法一方法一假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動的公式假定空氣阻力不計(jì)，可以直接利用自由落體運(yùn)動的公式來計(jì)算。例如，來計(jì)算。例如， 設(shè)設(shè)t=4秒，秒，g=9.81米米/秒秒2，則可求得，則可求得h78.5米。米。221gth 我學(xué)過微積分，我可以做我學(xué)過微積分，我可以做 得更好，呵呵。得更好，呵呵。 vKmgdtdvmF除去地球吸引力外，對石塊下落影響最大的當(dāng)除去地球吸引力外，對石塊下落影響最大的當(dāng) 屬屬空氣阻空氣阻力力。根據(jù)流體力學(xué)知識，此時可設(shè)空氣阻力正比于石塊下。根據(jù)流體力學(xué)知識，此時可設(shè)空氣阻

11、力正比于石塊下落的速度，阻力系落的速度，阻力系 數(shù)數(shù)K為常數(shù)，因而，由牛頓第二定律可為常數(shù)，因而，由牛頓第二定律可得：得： kgcevkt令令k=K/m，解得解得 代入初始條件代入初始條件 v(0)=0，得，得c=g/k，故有，故有 ktekgkgv再積分一次，得：再積分一次，得： cekgtkghkt2若設(shè)若設(shè)k=0.05并仍設(shè)并仍設(shè) t=4秒，則可求秒，則可求 得得h73.6米。米。 聽到回聲再按跑表，計(jì)算得到的時間中包含了聽到回聲再按跑表，計(jì)算得到的時間中包含了 反應(yīng)時間反應(yīng)時間 不妨設(shè)不妨設(shè)平均反應(yīng)時間平均反應(yīng)時間 為為0.1秒秒 ，假如仍，假如仍 設(shè)設(shè)t=4秒，扣除反秒，扣除反應(yīng)時間

12、后應(yīng)應(yīng)時間后應(yīng) 為為3.9秒，代入秒，代入 式式，求得，求得h69.9米。米。 222)1(kgektkgkgekgtkghktkt多測幾次，取平均多測幾次，取平均值值代入初始條代入初始條 件件h(0)=0，得到計(jì)算山崖高度的公式：，得到計(jì)算山崖高度的公式： 將將e-kt用泰勒公式展開并用泰勒公式展開并 令令k 0+ ，即可，即可得出前面不考慮空氣阻力時的結(jié)果。得出前面不考慮空氣阻力時的結(jié)果。還應(yīng)考慮還應(yīng)考慮回聲回聲傳回來所需要的時間。為此，令石塊下落傳回來所需要的時間。為此，令石塊下落 的真正時間的真正時間 為為t1，聲音傳回來的時間記，聲音傳回來的時間記 為為t2，還得解一個，還得解一個方

13、程組：方程組： 933401212211.ttthkg)ekt (kghkt這一方程組是這一方程組是非線性非線性的，求的，求解不太容易，解不太容易，為了估算崖高為了估算崖高竟要去解一個竟要去解一個非線性主程組非線性主程組似乎不合情理似乎不合情理 相對于石塊速度，聲音速度要快得多，我們可相對于石塊速度，聲音速度要快得多，我們可 用方法二先求一次用方法二先求一次 h，令，令t2=h/340，校正，校正t，求石，求石塊下落時間塊下落時間 t1t-t2將將t1代入式代入式再算一次，得出再算一次，得出崖高的近似值。例如，崖高的近似值。例如， 若若h=69.9米，則米，則 t20.21秒，故秒，故 t13

14、.69秒，求得秒，求得 h62.3米。米。 2.2 錄像帶還能錄多長時間錄像帶還能錄多長時間錄像機(jī)上有一個四位計(jì)數(shù)器，一盤錄像機(jī)上有一個四位計(jì)數(shù)器，一盤 180分鐘分鐘的錄像帶在開始計(jì)數(shù)時為的錄像帶在開始計(jì)數(shù)時為 0000，到結(jié)束時計(jì)，到結(jié)束時計(jì)數(shù)為數(shù)為1849，實(shí)際走時為，實(shí)際走時為185分分20秒。我們從秒。我們從0084觀察到觀察到0147共用時間共用時間3分分21秒。若錄像秒。若錄像機(jī)目前的計(jì)數(shù)為機(jī)目前的計(jì)數(shù)為1428，問是否還能錄下一個，問是否還能錄下一個 60分鐘的節(jié)目？分鐘的節(jié)目？rRl由由W vt)r (R22得到得到212rvtWR又又 因和因和 得得 Rl tvl tRv

15、積分得到積分得到tdt)rWvtv(d02120rrWvtW2rWvtW2t2212021)()(即即從而有從而有rrWvtWn212)(12我們希望建立一個錄像帶已錄像時我們希望建立一個錄像帶已錄像時 間間t與計(jì)數(shù)器計(jì)與計(jì)數(shù)器計(jì) 數(shù)數(shù)n之間的函數(shù)關(guān)系。為建立一個正確的模型，首之間的函數(shù)關(guān)系。為建立一個正確的模型，首 先必先必須搞清哪些量是常量，哪些量是變量。首先，錄像須搞清哪些量是常量，哪些量是變量。首先，錄像 帶帶的厚的厚 度度W是常量，它被繞在一個半徑是常量，它被繞在一個半徑 為為r的園盤上，的園盤上，見圖。磁帶轉(zhuǎn)動中線速見圖。磁帶轉(zhuǎn)動中線速 度度v顯然也是常數(shù)，否則圖象顯然也是常數(shù)，否

16、則圖象聲音必然會失真。此外，計(jì)數(shù)器的讀聲音必然會失真。此外，計(jì)數(shù)器的讀 數(shù)數(shù)n與轉(zhuǎn)過的圈與轉(zhuǎn)過的圈數(shù)有關(guān)，從而與轉(zhuǎn)過的角數(shù)有關(guān)，從而與轉(zhuǎn)過的角 度度成正比。成正比。 rRlrrWvtWn212)(12 此式中的三個參數(shù)此式中的三個參數(shù)W、v和和r均不易精確測得，均不易精確測得，雖然我們可以從上式解出雖然我們可以從上式解出t與與n的函數(shù)關(guān)系，的函數(shù)關(guān)系，但效果不佳，故令但效果不佳，故令 則可將上式簡化為：則可將上式簡化為： Wv vW/r2tn故故nnnt21222令令21a b2上式又可化簡記成上式又可化簡記成 t= an2+bn t= an2+bn rRl上式以上式以a、b為參數(shù)顯然是一個十

17、分明智的為參數(shù)顯然是一個十分明智的做法，它為公式的最終確立即參數(shù)求解提做法，它為公式的最終確立即參數(shù)求解提供了方便。將已知條件代入，得方程組：供了方便。將已知條件代入，得方程組： 3.351471478484185.331849(1849)12122tbatbaba從后兩式中消從后兩式中消 去去t1，解得，解得a=0.0000291, b=0.04646,故故t=0.0000291 n2+0.04646n，令，令n=1428，得到，得到t=125.69（分）由于一盒錄像帶實(shí)際可錄像時間為（分）由于一盒錄像帶實(shí)際可錄像時間為185.33分，分，故尚可錄像時間故尚可錄像時間 為為59.64分，已不

18、能再錄下一個分，已不能再錄下一個60分鐘分鐘的節(jié)目了。的節(jié)目了。 在解決實(shí)際問題時，注意觀察和善于想象是十分重要的，在解決實(shí)際問題時，注意觀察和善于想象是十分重要的，觀察與想象不僅能發(fā)現(xiàn)問題隱含的某些屬性，有時還能順觀察與想象不僅能發(fā)現(xiàn)問題隱含的某些屬性，有時還能順理成章地找到解決實(shí)際問題的鑰匙。本節(jié)的幾個例子說明，理成章地找到解決實(shí)際問題的鑰匙。本節(jié)的幾個例子說明，猜測也是一種想象力。沒有合理而又大膽的猜測，很難做猜測也是一種想象力。沒有合理而又大膽的猜測，很難做出具有創(chuàng)新性的結(jié)果。開普勒的三大定律（尤其是后兩條）出具有創(chuàng)新性的結(jié)果。開普勒的三大定律（尤其是后兩條）并非一眼就能看出的，它們隱

19、含在行星運(yùn)動的軌跡之中，并非一眼就能看出的，它們隱含在行星運(yùn)動的軌跡之中，隱含在第谷記錄下來的一大堆數(shù)據(jù)之中。歷史上這樣的例隱含在第谷記錄下來的一大堆數(shù)據(jù)之中。歷史上這樣的例子實(shí)在太多了。在獲得了一定數(shù)量的資料數(shù)據(jù)后，人們常子實(shí)在太多了。在獲得了一定數(shù)量的資料數(shù)據(jù)后，人們常常會先去猜測某些結(jié)果，然后試圖去證明它。猜測一經(jīng)證常會先去猜測某些結(jié)果，然后試圖去證明它。猜測一經(jīng)證明就成了定理，而定理一旦插上想象的翅膀，又常常會被明就成了定理，而定理一旦插上想象的翅膀，又常常會被推廣出許多更為廣泛的結(jié)果。即使猜測被證明是錯誤的，推廣出許多更為廣泛的結(jié)果。即使猜測被證明是錯誤的，結(jié)果也決不是一無所獲的失敗

20、而常常是對問題的更為深入結(jié)果也決不是一無所獲的失敗而常常是對問題的更為深入的了解。的了解。 2.3最短路徑與最速方案問題最短路徑與最速方案問題 例例5（最短路徑問題）（最短路徑問題） 設(shè)有一個半徑為設(shè)有一個半徑為 r 的圓形湖，圓心為的圓形湖，圓心為 O。A、B 位于湖的兩側(cè)，位于湖的兩側(cè)，AB連線過連線過O，見圖。，見圖?，F(xiàn)擬從現(xiàn)擬從A點(diǎn)步行到點(diǎn)步行到B點(diǎn)，在不得進(jìn)入湖中的限點(diǎn)，在不得進(jìn)入湖中的限 制下，問怎樣的路徑最近。制下，問怎樣的路徑最近。 ABOr將湖想象成凸出地面的木樁，將湖想象成凸出地面的木樁， 在在AB間拉一根軟線，當(dāng)間拉一根軟線，當(dāng)線被拉緊時將得到最短路徑。根據(jù)這樣的想象，猜

21、測線被拉緊時將得到最短路徑。根據(jù)這樣的想象，猜測 可以如下得到最短路徑：可以如下得到最短路徑： 過過A作圓的切線切圓于作圓的切線切圓于E，過，過B作圓的切線切圓作圓的切線切圓 于于F。最短路徑為由線。最短路徑為由線 段段AE、弧、弧EF和線段和線段FB連接而成的連續(xù)曲線（根據(jù)對稱性，連接而成的連續(xù)曲線（根據(jù)對稱性，AE，弧弧EF，F(xiàn)B連接而成的連續(xù)曲線也是）。連接而成的連續(xù)曲線也是）。EFEF以上只是一種猜測，現(xiàn)在來證明這一猜測是正確的。為此，以上只是一種猜測，現(xiàn)在來證明這一猜測是正確的。為此，先介紹一下凸集與凸集的性質(zhì)。先介紹一下凸集與凸集的性質(zhì)。定義定義2.1（凸集凸集）稱集合）稱集合 R

22、為凸集，若為凸集，若x1、x2R及及0，1，總有總有x1+（1+）x2R。即若。即若x1、x2R，則，則x1、x2的連線必整個地落的連線必整個地落 在在R中。中。定理定理2.2（分離定理分離定理）對平面中的凸）對平面中的凸 集集R與與R外的一點(diǎn)外的一點(diǎn)K，存在直線存在直線 l , l 分離分離R與與K，即，即R與與K分別位于分別位于 l 的兩側(cè)（注：的兩側(cè)（注：對一般的凸對一般的凸 集集R與與R外的一點(diǎn)外的一點(diǎn)K，則存在超平面分，則存在超平面分 離離R與與K），見圖。），見圖。klR下面證明猜想下面證明猜想猜測證明如下：猜測證明如下：（方法一）（方法一）顯然，顯然， 由由AE、EF、FB及及A

23、E，EF，F(xiàn)B圍成圍成的區(qū)域的區(qū)域 R是一凸集。利用是一凸集。利用分離定理分離定理易證最短徑不可能經(jīng)過易證最短徑不可能經(jīng)過R外的點(diǎn)，若不然，設(shè)外的點(diǎn)，若不然，設(shè) 為最短路徑，為最短路徑，過過R外的一點(diǎn)外的一點(diǎn)M，則，則必存在直必存在直 線線l分離分離M與與R，由于路徑，由于路徑是連續(xù)曲線，由是連續(xù)曲線，由A沿沿到到M，必交，必交l于于M1，由，由M沿沿到到B又必交又必交l于于M2。這樣，直線。這樣，直線 段段M1M2的長度必小于路的長度必小于路 徑徑M1MM2的長度，與的長度，與是是A到到B的的最短路徑矛盾，至此，我們已證明最短路徑必在凸集最短路徑矛盾，至此，我們已證明最短路徑必在凸集R內(nèi)。內(nèi)

24、。不妨設(shè)路徑經(jīng)湖的上方到達(dá)不妨設(shè)路徑經(jīng)湖的上方到達(dá)B點(diǎn)，則弧點(diǎn)，則弧EF必在路徑必在路徑F上，又上，又直線段直線段AE是由是由A至至E的最短路徑，直線的最短路徑，直線FB是由是由F到到B的最短的最短路徑，猜測得證。路徑，猜測得證。ABOrEFEFM1M2Ml還可用還可用微積分微積分方法求弧長，根據(jù)計(jì)算證方法求弧長，根據(jù)計(jì)算證明滿足限止條件的其他連續(xù)曲線必具有明滿足限止條件的其他連續(xù)曲線必具有更大的長度；此外，本猜測也可用更大的長度；此外，本猜測也可用平面平面幾何幾何知識加以證明等。知識加以證明等。 根據(jù)猜測不難看出，根據(jù)猜測不難看出， 例例5中的條件可以大大放中的條件可以大大放松，可以不必松，

25、可以不必 設(shè)設(shè)AB過圓心，甚至可不必設(shè)湖過圓心，甚至可不必設(shè)湖是圓形的。例如對是圓形的。例如對 下圖，我們可斷定由下圖，我們可斷定由A至至B的最短路徑必的最短路徑必 為為l1與與l2之一，其證明也不難類之一，其證明也不難類似給出。似給出。 ABl1l2D到此為止，我們的研討還只局限于平面之中，到此為止，我們的研討還只局限于平面之中，其實(shí)上述猜測可十分自然地推廣到一般空間其實(shí)上述猜測可十分自然地推廣到一般空間中去。中去。1973年，年，J.W.Craggs證明了以上結(jié)果：證明了以上結(jié)果：若可行區(qū)域的邊界是光滑曲面。則最短路徑必由下列弧組若可行區(qū)域的邊界是光滑曲面。則最短路徑必由下列弧組成，它們或

26、者是空間中的自然最短曲線，或者是可行區(qū)域成，它們或者是空間中的自然最短曲線，或者是可行區(qū)域的邊界弧。而且，組成最短路徑的各段弧在連接點(diǎn)處必定的邊界弧。而且，組成最短路徑的各段弧在連接點(diǎn)處必定相切。相切。例例6 6 一輛汽車停于一輛汽車停于 A A處并垂直于處并垂直于ABAB方向，此方向，此汽車可轉(zhuǎn)的最小圓半徑為汽車可轉(zhuǎn)的最小圓半徑為 R，求不倒車而由，求不倒車而由 A A到到B B的最短路徑。的最短路徑。解解（情況（情況1）若若|AB|2R，最短路徑由，最短路徑由 弧弧AC與切線與切線BC組組成（見成（見圖圖 ）。）。（情況（情況2）若若|AB|0為推力，為推力，fS，故由連續(xù)函數(shù)的性質(zhì)存在，

27、故由連續(xù)函數(shù)的性質(zhì)存在 某某TT，S（T）=S但這一結(jié)但這一結(jié)果與果與=(t)是最優(yōu)方案下的車速的假設(shè)矛盾，因?yàn)橛梦覀儾聹y是最優(yōu)方案下的車速的假設(shè)矛盾，因?yàn)橛梦覀儾聹y的推車方法推車，只的推車方法推車，只 需需T時間即可將車推到修車處，時間即可將車推到修車處， 而而T0可推出可推出 0的置換矩陣的置換矩陣Pijt步步2 確定確定 min|1ijijtp步步3 取取 ，用，用 代替代替PTPT步步4 若若 =0，停；否則，返回步，停；否則，返回步1。T例例2. 2. 為方便起見，我們來分解一個元素均為非負(fù)整數(shù)的為方便起見，我們來分解一個元素均為非負(fù)整數(shù)的3階雙隨機(jī)矩陣，階雙隨機(jī)矩陣，（由（由Bir

28、khoff定理，定理，r5）145532433T解：取解：取 ，=min 1, 3, 3 =11100010001P分解成分解成1045522432TP，再取，再取 2001100010P因因min 5, 5, 3 = 3，又有，又有120423222402TPP，取，取 3010001100P于是又有于是又有 12302232220202TPPP易得分解結(jié)果為：易得分解結(jié)果為：1000010100100010103 1002 0012 1002 010001010100001100T110rkk尚需解決的問題是如何求尚需解決的問題是如何求P，使得，使得Pij0必有必有 。讀者不難發(fā)現(xiàn)，此問。

29、讀者不難發(fā)現(xiàn)，此問題可以通過求解一個兩分圖上的最大流（或最大匹配）來實(shí)現(xiàn)，計(jì)算量題可以通過求解一個兩分圖上的最大流（或最大匹配）來實(shí)現(xiàn)，計(jì)算量為為O(n4)，是多項(xiàng)式時間可解的。具體方法為：作一兩分圖，若，是多項(xiàng)式時間可解的。具體方法為：作一兩分圖，若 ，則作邊（則作邊（i, j），令邊容量為），令邊容量為1，這樣，可作出，這樣，可作出P的充要條件是該最大流問的充要條件是該最大流問題的最大流量為題的最大流量為n。對例。對例9.33，n=3。由于所有。由于所有 ，先取，先取 0ijt 0ijt 0ijt ， P1為為 1100010001PT045522432相應(yīng)的兩分圖為：相應(yīng)的兩分圖為：于是

30、又可求得于是又可求得2001100010P120423222402TPP，相應(yīng)的兩分圖為：，相應(yīng)的兩分圖為： 又可得又可得 ，如此下去，直到作不出，如此下去，直到作不出P為至，為至，由于由于 的特殊性質(zhì)及的特殊性質(zhì)及Birkhoff定理，上述分解必能在不超過定理，上述分解必能在不超過r= (n1)2 + 1步內(nèi)終止。步內(nèi)終止。3010001100PT上述開關(guān)設(shè)計(jì)方法要求在通訊衛(wèi)星上設(shè)置上述開關(guān)設(shè)計(jì)方法要求在通訊衛(wèi)星上設(shè)置(n1)2 + 1種不同的開關(guān)模式種不同的開關(guān)模式（即（即Pk），當(dāng)），當(dāng)n稍大時，稍大時，(n1)2 + 1仍顯得太大而使得使用時不便。例如，仍顯得太大而使得使用時不便。例如

31、，當(dāng)當(dāng)n=41時，時，(n1)2 + 1=| 60 |。為實(shí)用方便，人們研究了限止開關(guān)模式個。為實(shí)用方便，人們研究了限止開關(guān)模式個數(shù)的相應(yīng)問題。數(shù)的相應(yīng)問題。若要求若要求rn，即要求通訊衛(wèi)星上至多設(shè)置，即要求通訊衛(wèi)星上至多設(shè)置n種開關(guān)模式，則問題化為令種開關(guān)模式，則問題化為令rn，求不超過求不超過n個置換矩陣個置換矩陣Pk及及k，使之滿足：，使之滿足： min S.t 1nkk1nkkkPT為了使任意一對發(fā)射法與接收站之間的傳送均為可能實(shí)現(xiàn)的，自然應(yīng)要求為了使任意一對發(fā)射法與接收站之間的傳送均為可能實(shí)現(xiàn)的，自然應(yīng)要求Pk滿足滿足（5.1） 1111111nkkP （5.2） （右面的矩陣有（右

32、面的矩陣有n2個值為個值為1的分量，每一的分量，每一Pk 恰有恰有n個個1分量）故分量）故r=n。容易看出，（容易看出，（5.1）隱含著）隱含著T的每一元素只能被唯一的的每一元素只能被唯一的P復(fù)蓋，即復(fù)蓋，即T的元素在的元素在分解中是不可分割的，這當(dāng)然是一個好性質(zhì)，使實(shí)際操作時較為方便，但分解中是不可分割的，這當(dāng)然是一個好性質(zhì)，使實(shí)際操作時較為方便，但可惜的是對一般的雙隨機(jī)矩陣，分解很可能無解?？上У氖菍σ话愕碾p隨機(jī)矩陣，分解很可能無解。例例3 3 若取若取1100010001P， 2010001100P3001100010P， 145532433T（注意：（注意：T已是雙隨機(jī)矩陣，行和列和均

33、為已是雙隨機(jī)矩陣，行和列和均為10） 則min 31kkS.t 31kkkPT的解為的解為1=3，2=4，3=5。3112kk（大于（大于10）而）而 31345534453kkkPT但等號經(jīng)常并不成立。但等號經(jīng)常并不成立。1985年，年，F(xiàn)Rendel證明，在給定滿足（證明，在給定滿足（5.2）的置）的置換矩陣換矩陣P1,Pn后，求解問題（后，求解問題（5.1）是）是NP難的，從而不可能存在多項(xiàng)式難的，從而不可能存在多項(xiàng)式時間算法，除非時間算法，除非P=NP?，F(xiàn)要求現(xiàn)要求r2n一種自然而方便的開關(guān)設(shè)置為引入兩組各有一種自然而方便的開關(guān)設(shè)置為引入兩組各有n個開關(guān)模式的置換矩陣個開關(guān)模式的置換矩

34、陣P1,Pn，Q1,Qn，滿足下面的（，滿足下面的（5.3)式：式：111111nnkkkkPQ例如，當(dāng)例如，當(dāng)n=3時，可令：時，可令：1100010001P2010001100P3001100010P1001010100Q2010100001Q3100001010Q（注：這種設(shè)置方法保持了其內(nèi)在的對稱性，不失為一種明智的做法。）（注：這種設(shè)置方法保持了其內(nèi)在的對稱性，不失為一種明智的做法。）現(xiàn)在，我們來分解例現(xiàn)在，我們來分解例9.33中的雙隨機(jī)矩陣中的雙隨機(jī)矩陣 ，令，令 =，得方程組，得方程組TT31()kkkkkPQ132231321123213312145532433求出各對角線與反

35、對角線上的三個元素之和，并作一些簡單的消去運(yùn)算；求出各對角線與反對角線上的三個元素之和，并作一些簡單的消去運(yùn)算；將矩陣的所有元素相加，可得下面的方程組：將矩陣的所有元素相加，可得下面的方程組：313212131231232102()()10注意到（注意到（5.3），易證空間），易證空間 的維數(shù)為的維數(shù)為 5，故故 之一可任取，（稍加注意即可保持非負(fù)性），之一可任取，（稍加注意即可保持非負(fù)性），例如，令例如，令3=0，求得，求得 ，故有，故有31()kkkkkPQ,kk 121232,1,2,3123122322TPPPQQ31()10kkk讀者不難驗(yàn)證，上述方法可推廣到讀者不難驗(yàn)證，上述方法可

36、推廣到n是奇數(shù)的一般情況。事實(shí)，由各對角線是奇數(shù)的一般情況。事實(shí)，由各對角線元素之和可導(dǎo)出元素之和可導(dǎo)出n1個方程，由各反對角線元素之和又可導(dǎo)出個方程，由各反對角線元素之和又可導(dǎo)出n1個方程，個方程，加上矩陣所有元素之和導(dǎo)出的等式，共計(jì)可導(dǎo)出加上矩陣所有元素之和導(dǎo)出的等式，共計(jì)可導(dǎo)出2 n1個方程，并易知它個方程，并易知它們是獨(dú)立的。另一方面空間們是獨(dú)立的。另一方面空間 的維數(shù)恰為的維數(shù)恰為2 n1，故，故 之一可任取，而通過方程組解得所有的之一可任取，而通過方程組解得所有的 ，（只須注意保持其非負(fù)性即可）（只須注意保持其非負(fù)性即可）1()nkkkkkPQ,kk ,kk 但當(dāng)?shù)?dāng)n為偶數(shù)時，情

37、況就不大相同了。讓我們先來觀察一下為偶數(shù)時，情況就不大相同了。讓我們先來觀察一下n=4的情況。的情況。當(dāng)當(dāng)n=4時，時，11000010000100001P20100001000011000P30010000110000100P40001100001000010P10001001001001000Q20010010010000001Q30100100000010010Q41000000100100100Q1423324143122134413241142321344312()kkkkKABPQBA 易見，易見， 具有非常特殊的結(jié)構(gòu)，一般的偶數(shù)階雙隨機(jī)矩具有非常特殊的結(jié)構(gòu)，一般的偶數(shù)階雙隨機(jī)矩陣，即使其元素是非負(fù)整數(shù)，也無法用陣，即使其元素是非負(fù)整數(shù)，也無法用Pk、Qk來分解。來分解。41()kkkkkPQ當(dāng)當(dāng) 具有上述結(jié)構(gòu)時，能否用具有上述結(jié)構(gòu)時，能否用Pk和和Qk來分解呢？易見，由各對角線元素來分解呢？易見，由各對角線元素之和可導(dǎo)出：之和可導(dǎo)出：T12441332421342()1042()1242()1442()16另外，由反對角線元素之和又可導(dǎo)出另外，由反對角線元素之和又可導(dǎo)出12441332421342()1442()1042()1442()14上述方程中只有上述方程中只有6個是獨(dú)立的，且已不可能再得出新的獨(dú)立方程，（讀者個是獨(dú)立的，且