最優(yōu)控制設(shè)計

最優(yōu)控制設(shè)計摘要計算機(jī)已經(jīng)成為現(xiàn)代社會開展的不可取代的有利助手，而計算機(jī)控制更是普及各個領(lǐng)域。用盡可能少的指令去控制部件，用盡可能短的指令集合去控制部件將大大的簡化控制過程，大大的方便控制。因而對計算機(jī)指令控制部件并到達(dá)最優(yōu)的研究具有深遠(yuǎn)的意義。針對問題一我們建立了整數(shù)線性規(guī)劃模型。得到了所有部件得到控制的最少指令的集合為13的結(jié)果針對問題二我們建立了整數(shù)線性規(guī)劃模型。得到了所有部件得到控制的總長度最小長度為360的結(jié)果。針對問題三由于此題模型0—1線性規(guī)劃問題，我們采用單純形法對所建立的模型進(jìn)行了求解。針對問題四提出的算法復(fù)雜度，我們根據(jù)現(xiàn)代計算機(jī)軟件相關(guān)理論，從時間復(fù)雜度和空間復(fù)雜度兩個方面逐一論述了單純形法在兩個方面的復(fù)雜度。具體來說時間復(fù)雜度為1575，空間復(fù)雜度由于數(shù)據(jù)量大，導(dǎo)致其空間復(fù)雜度相對較復(fù)雜。一·問題重述在計算機(jī)控制過程中，一條計算機(jī)指令往往可以控制幾個計算機(jī)部件，反過來，一個部件一般由幾條指令控制。一個根本的問題是，在指令集合里尋找最少的指令，使得所有的部件得到控制；另一個問題是，當(dāng)給定每條指令的長度時，在指令集合里，尋求總長度最小的假設(shè)干指令，使得他們可以控制全部部件。對于上面兩個問題，建立如下兩個數(shù)學(xué)模型：1·建立使得所有部件得到控制的最少指令集合；2·建立使得所有部件得到控制的總長度最小的指令集合。再給出指令控制的部件和指令的長度后如表1所示，用所建立的數(shù)學(xué)模型對表1所列的數(shù)據(jù)求出結(jié)果。3·設(shè)計模型的求解算法，用表1-1中所列的數(shù)據(jù)給出求解結(jié)果；4·分析所設(shè)計算法的復(fù)雜性和計算所得到的結(jié)果。二·問題分析由于一條計算機(jī)指令往往可以控制幾個計算機(jī)部件，反過來，一個部件一般有幾條指令控制，這兩都是線性規(guī)劃問題且約束條件相同，只是兩個題的目標(biāo)函數(shù)不同。針對問題一：建立使得所有的部件得到控制的指令集合里的最少的指令模型。我們利用整數(shù)線性規(guī)劃模型，列出所求優(yōu)化問題目標(biāo)函數(shù)和約束條件，并確保一個部件至少有1條指令控制，同時求出所有部件得到控制的最少指令的集合。針對問題二：仍然建立整數(shù)規(guī)劃模型，依然要保證一個部件至少有1條指令控制，再求出所有部件得到控制的總長度的最小長度。針對問題三：因為此題中兩個問題均是線性規(guī)劃問題且約束條件相同，只是目標(biāo)函數(shù)略有不同，對此，我們選取單純形法求解。單純形法是線性規(guī)劃問題的一般解法，其根本思想是尋找一個基的可行解〔極點〕，便可以通過有限步的迭代找到問題的最優(yōu)解。針對問題四：從時間的復(fù)雜性和空間的復(fù)雜性兩個方面進(jìn)行分析。三·模型假設(shè)1·一條計算機(jī)指令往往可以控制幾個計算機(jī)部件，反過來，一個部件一般有幾條指令控制。2·計算機(jī)部件都完好，不會出現(xiàn)因部件不佳而造成指令的無法控制。3·不考慮計算機(jī)指令之間的相互沖突。4·不考慮計算機(jī)發(fā)送指令所用的時間。四·符號使用及說明：第條指令控制第各部件；：是否使用第條指令；：第條指令的長度；：指令的總條數(shù)；：部件的總個數(shù)；：所用指令的總條數(shù)；：所用指令的總長度；五·模型的建立與求解問題一的模型：問題一的目的是為了在指令集合中尋找條數(shù)最少的指令，使得所有的部件得到控制，表示是否使用第條指令，，所使用指令的總條數(shù)可以表示為，因此目標(biāo)函數(shù)為：。約束條件：我們可以用表示第條指令和第個部件的關(guān)系，，易知表示第個部件是否得到指令集合中一條或多條指令控制，當(dāng)時，表示第個部件得到指令集合中至少一條指令的控制。目標(biāo)函數(shù)：約束條件：解得：最小指令集合為：,,,,,,,,,,,,;總共為13條指令。問題二的模型：首先我們引入一組變量其中表示第條指令的長度。問題二的目的是為了在指令集合中尋求總長度最小的假設(shè)干指令，使得所有的部件得到控制，根據(jù)對問題一的分析可知，問題二仍未整數(shù)線性規(guī)劃問題，整數(shù)規(guī)劃模型為：目標(biāo)函數(shù)：約束條件：解得：表2所有部件得到控制的總長度最小的指令集合指令XjX1X3X4X5X6X7X10長度1530127193236所控部件6,11327,24,27,351,12,18,285,7,27,327,10,13,224,6,8,20,28,3410,15,31指令XjX14X17X19X21X22X23X24長度53462626191722所控部件7,3413,24,292,21,24,265,8,112,12,14,346,19,22,317,16,26所以最小長度為：L=15+30+12+7+19+32+36+53+46+26+26+19+17+22=360問題三的求解因為此題中兩個問題均是線性規(guī)劃問題且約束條件相同，只是目標(biāo)函數(shù)略有不同，對此，我們選取單純形法求解。單純形法是線性規(guī)劃問題的一般解法，其根本思想是尋找一個基的可行解〔極點〕，便可以通過有限步的迭代找到問題的最優(yōu)解。求解問題一用單純形的二階段法第一階段：第一步：將數(shù)學(xué)模型的線性規(guī)劃轉(zhuǎn)化為單純形法的標(biāo)準(zhǔn)形式?！灿捎谠紗栴}全部“”約束條件構(gòu)成，因此還需添加人工變量和剩余變量〕本問題約束矩陣M=〔A,-l,K〕,其中A=為階矩陣，l,K為階單位矩陣，Z表示人工變量的和。輔助目標(biāo)函數(shù)：將輔助目標(biāo)函數(shù)化為求最大值的問題：目標(biāo)函數(shù)也化為求最大值的問題：約束條件為:第二步：檢驗各非基變量的檢驗系數(shù)，假設(shè)那么基可行解已是最優(yōu)解，計算結(jié)束；否那么轉(zhuǎn)為下一步。第三步：以輔助目標(biāo)函數(shù)為判斷依據(jù)進(jìn)行迭代，選取輔助目標(biāo)函數(shù)中具有非負(fù)系數(shù)的非基變量(假設(shè)是)，作為進(jìn)入下一個根本可行解的進(jìn)基變量，然后轉(zhuǎn)入下面介紹的第四步。如果此時，所有的系數(shù)均為非負(fù)，就得到輔助目標(biāo)函數(shù)的最優(yōu)解。假設(shè)此時的目標(biāo)函數(shù)值為零，并且所有人工變量均不在基內(nèi)，這就得到了原始問題的一個根本可行解，然后就轉(zhuǎn)入第二階段計算；如果此時輔助目標(biāo)函數(shù)值不為零，那么人工變量至少還有一個留在基內(nèi)取非零的正值，那么，原始問題就沒有可行解，那么停止運(yùn)算，轉(zhuǎn)至第六步。第四步：根據(jù)|>0=,確定為進(jìn)基變量，為出基變量，轉(zhuǎn)入下一步。第五步：以為主元素進(jìn)行迭代〔即高斯消去法〕，把所對應(yīng)的列向量〔1為第個數(shù)〕；目標(biāo)函數(shù)〔輔助目標(biāo)函數(shù)〕中也應(yīng)消去，將基變量中轉(zhuǎn)化為重復(fù)第一至第五步，直到終止。第六步：假設(shè)無可行解，那么依題意定義第二階段：去掉輔助目標(biāo)函數(shù)所在的行和列，然后以原目標(biāo)函數(shù)代替第一階段的輔助目標(biāo)函數(shù)作為判斷依據(jù)，進(jìn)行單純形法迭代。運(yùn)算步驟同第一階段中，第一至第五步相類似〔注意將第二步中的范圍定為〕，知道得到原線性規(guī)劃問題的最優(yōu)解。求解問題二的算法：根據(jù)模型的相似性，只需將求解問題一中的目標(biāo)函數(shù)改為：即可，算法與求解問題一中的相同。問題四的求解復(fù)雜性分析1．對于時間復(fù)雜度，題目要求是使每個部件都受一條或多條指令的控制，所以對于每一個部件都要從1……35遍歷每一個的指令，假設(shè)果遍歷過程中發(fā)現(xiàn)某一條指令控制此部件，那么對加一，表示第i個部件總共接收到的指令條數(shù)。那么時間復(fù)雜度為45*35=1575，而第二問同第一問時間復(fù)雜度為45*35=1575。2．對于空間復(fù)雜度，求解約束方程較少、數(shù)據(jù)量較小時，運(yùn)行較為容易，且數(shù)據(jù)存儲所占內(nèi)存空間較多，運(yùn)行循環(huán)過程過于復(fù)雜?？傮w來說，空間復(fù)雜度所占較大。六·結(jié)果分析問題一：據(jù)題中要求提出相應(yīng)的線性規(guī)劃模型，解得：最小指令集合為：,,,,,,,,,,,,;總共為13條指令。而且從運(yùn)行結(jié)果來看所建立模型是符合實際情況的，問題二中模型跟題一類似；解得最小長度為：L=15+30+12+7+19+32+36+53+46+26+26+19+17+22=360；問題三：我們建立的單純形法對與求解這類模型是可行的，從計算過程來看，迭代次數(shù)不高，求解相對而言具有效率。對于問題四：復(fù)雜性分析1．對于時間復(fù)雜度，題目要求是使每個部件都受一條或多條指令的控制，所以對于每一個部件都要從1……35遍歷每一個的指令，假設(shè)果遍歷過程中發(fā)現(xiàn)某一條指令控制此部件，那么對加一，表示第i個部件總共接收到的指令條數(shù)。那么時間復(fù)雜度為45*35=1575，而第二問同第一問時間復(fù)雜度為45*35=1575。2．對于空間復(fù)雜度，求解約束方程較少、數(shù)據(jù)量較小時，運(yùn)行較為容易，且數(shù)據(jù)存儲所占內(nèi)存空間較多，運(yùn)行循環(huán)過程過于復(fù)雜?？傮w來說，空間復(fù)雜度所占較大。七·模型的評價與推廣本模型對計算機(jī)指令優(yōu)化控制問題做了細(xì)致的分析，提出了模型的算法，并進(jìn)行了計算求解，最后用數(shù)學(xué)軟解檢驗了結(jié)果的正確性。本模型也適用于其他類似問題，且規(guī)劃明確簡單，易于操作，可是由于算法的局限，當(dāng)此類問題有多組最優(yōu)解時，其模型只能求出其中一組，但所得結(jié)果還是令人滿意的。優(yōu)點：模型一為整數(shù)線性規(guī)劃模型，本身較為嚴(yán)密，思路清晰，分步驟逐個擊破，對題目一條計算機(jī)指令往往可以控制幾個計算機(jī)部件，反過來，一個部件一般有幾條指令控制考慮周全，并且可以運(yùn)用于實踐問題，到達(dá)數(shù)學(xué)建模的根本目的，采用MATLAB和LINGO軟件解決復(fù)雜程序，將問題簡單化。缺點：當(dāng)然我們對缺點也不避諱，因為知識面的局限及時間有限我們沒有采用大量的文獻(xiàn)資料來證明，且模型還有一些漏洞，以后我們會改良。八·參考文獻(xiàn)薛毅數(shù)學(xué)建模根底北京：北京工業(yè)大學(xué)出版社2004劉煥彬等數(shù)學(xué)模型與實驗武漢：科學(xué)出版社2008孫祥等MATLAB7.0根底教程北京：清華大學(xué)出版社2005王秋萍整數(shù)規(guī)劃問題舉例課件九·附錄表1指令控制的部件和指令的長度指令指令所控制的部件指令的長度指令指令所控制的部件指令的長度14，8，20，31，44151913,23,26,392628，19,22,29,3780207,12,40,412232,16,34,33,32302112,16,19,28,352647,11,35,3012226,23,27,451955,13,18,2172333,37,40,411761,7,9,23,2519243,17,19,362273,5,6,14,24322516,33,44,451087,20,21,32,35122613,19,24,253099,15,20,4545272,3,5，882106,10,39,42,4336284,7,9,12,4373111,11,21,34,38572916,17,20,3266122,4,18,22,37783028,33,34,3655136,17,25,36653110,23,25,27241422,33,34,3853321,5,44,4546152,10,20,37343311,15,18,4337169,24,29,3948347,14,22,36771715,18,29,3146353,15,25,399184,42,44,4532問題一的LINGO程序：model!定義集;sets:zhiling/1..35/:x;bujian/1..45/:b;shuju(bujian,zhiling):s;endsets!目標(biāo)函數(shù);min=@sum(zhiling:x);@for(bujian(j):@sum(zhiling(i):x(i)*s(j,i))>=1);@for(zhiling:@BIN(x));!導(dǎo)入數(shù)據(jù);data:s=000001000010000000000000000000010000010000000010010000000000010000000000000010000000000000000100100000001100000000001000001000000000100000000000101000000000000000000010000100000000010010010000000010000000000000000101010000000000010000000100000101100000000000000000000000010000000000000100100000010000000000010000000000000000100001000000000000000100000001000000100000000000000000000010000000000000000000001100000010000000000010000000000000100000010000000000000001000000000000000000000000001000000000100000001000000000000000101001000000000000000001000100010000000000000000001000000000010000100000000001000000100001000000000000000100010000000000000000001001010000000001000000110000010000000000000100000000001001001000000000000000000000000010000000001010000000000000000000100000010000000000001001000000001000000000010000000010000000001000000000000001000000100000000000010000100010000000000000000001000000000000000000000000000000000000010000000010000000000000000000000001000000001000000100000000000001100000000000000000000010000000000000000000000000000000100000000000000010000000000000000000010000100000000000000000000100000000100000000001000000001010000100000001000000010010000000000000001000000001000100000000000010000000000000000000000000010000000000100000100010010000000001001000000010000000000000000000000100100000000000000000000000000000010000010010000000000000001000000000000000000010010000000000000000000000000000000100100000000000000000000010000000100000000000000000000000000100000000000000000100001001000000000000000010000001000000100000000000100000000100010010000001000;enddataend運(yùn)行結(jié)果：Globaloptimalsolutionfound.Objectivevalue:13.00000Objectivebound:13.00000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:63VariableValueReducedCostX(1)0.0000001.000000X(2)1.0000001.000000X(3)0.0000001.000000X(4)1.0000001.000000X(5)0.0000001.000000X(6)0.0000001.000000X(7)1.0000001.000000X(8)0.0000001.000000X(9)0.0000001.000000X(10)0.0000001.000000X(11)1.0000001.000000X(12)1.0000001.000000X(13)0.0000001.000000X(14)0.0000001.000000X(15)0.0000001.000000X(16)0.0000001.000000X(17)1.0000001.000000X(18)1.0000001.000000X(19)1.0000001.000000X(20)1.0000001.000000X(21)0.0000001.000000X(22)0.0000001.000000X(23)0.0000001.000000X(24)0.0000001.000000X(25)0.0000001.000000X(26)0.0000001.000000X(27)0.0000001.000000X(28)1.0000001.000000X(29)1.0000001.000000X(30)1.0000001.000000X(31)1.0000001.000000X(32)0.0000001.000000X(33)0.0000001.000000X(34)0.0000001.000000X(35)0.0000001.000000問題二的LINGO程序：model:!定義集;sets:zhiling/1..35/:x,l;bujian/1..45/:b;shuju(bujian,zhiling):s;endsets!目標(biāo)函數(shù);min=@sum(zhiling:x*l);@for(bujian(j):@sum(zhiling(i):x(i)*s(j,i))>=1);@for(zhiling:@BIN(x));@for(zhiling:@GIN(l));!導(dǎo)入數(shù)據(jù);data:s=000001000010000000000000000000010000010000000010010000000000010000000000000010000000000000000100100000001100000000001000001000000000100000000000101000000000000000000010000100000000010010010000000010000000000000000101010000000000010000000100000101100000000000000000000000010000000000000100100000010000000000010000000000000000100001000000000000000100000001000000100000000000000000000000000000000000001100000010000000010000000010000000000000100000010000000000000001000000000000000000000000001000000000100000001000000000000000101001000000000000000001000100010000000000000000001000000000010000100000000001000000100001000000000000000100 010000000000000000001001010000000001000000110000010000000000000100000000001001001000000000000000000000000010000000001010000000000000000000100000010000000000001001000000001000000000010000000010000000001000000000000001000000100000000000010000100010000000000000000001000000000000000000000000000000000000010000000010000000000000000000000001000000001000000100000000000001100000000000000000000010000000000000000000000000000000100000000000000010000000000000000000010000100000000000000000000100000000100000000001000000001010000100000001000000010010000000000000001000000001000100000000000010000000000000000000000000010000000000100000100010010000000001001000000010000000000000000000000100100000000000000000000000000000010000010010000000000000001000000000000000000010010000000000000000000000000000000100100000000000000000000010000000100000000000000000000000000100000000000000000100001001000000000000000010000001000000100000000000100000000100010010000001000;l=15803012719321245365778655334484632262226191722103082736655244637779;enddataend運(yùn)行結(jié)果：Globaloptimalsolutionfound.Objectivevalue:360.0000Objectivebound:360.0000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:28VariableValueReducedCostX(1)1.00000015.00000X(2)0.00000080.00000X(3)1.00000030.00000X(4)1.00000012.00000X(5)1.0000007.000000X(6)1.00000019.00000X(7)1.00000032.00000X(8)0.00000012.00000X(9)0.00000045.00000X(10)1.000000