【正文】 ing Problem)等。至今已出現(xiàn)線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃、幾何規(guī)劃、動態(tài)規(guī)劃、隨機規(guī)劃、網(wǎng)絡流等許多分支。但是，任何科學的進步，都受到歷史條件的限制，直到20世紀三十年代，最優(yōu)化這個古老課題并未形成獨立的有系統(tǒng)的學科。1847年法國數(shù)學家Cauchy研究了函數(shù)值沿什么方向下降最快的問題，提出最速下降法。最優(yōu)化是個古老的課題，長期以來，人們對最優(yōu)化問題進行著探討和研究。而多重組合優(yōu)化，則是在完成一個組合優(yōu)化的基礎上，按照縱向思維，層層推進，繼續(xù)完成下一步組合優(yōu)化問題，最終達到圓滿解決問題的能力。自從擬陣概念進入圖論領(lǐng)域之后，對擬陣中的一些理論問題的研究成為組合規(guī)劃研究的新課題，并得到應用。從最廣泛的意義上說，組合規(guī)劃與整數(shù)規(guī)劃這兩者的領(lǐng)域是一致的，都是指在有限個可供選擇方案的組成集合中，選擇使目標函數(shù)達到極值的最優(yōu)子集。上述決策問題通常稱為優(yōu)化問題。一類多重組合優(yōu)化問題的數(shù)學建模畢業(yè)設計目錄摘 要 1Abstract 2第一章 緒論 4 4 4 5第二章 組合優(yōu)化理論 6 定義 6 6 6 7 7 7 11 12第三章 應用實例——太陽能小屋設計 13 13 13 14 14 鋪設方案分析 15 15 16 小屋各個面光照強度的計算 18 21 24 總發(fā)電量、經(jīng)濟效益等參數(shù)的計算 25 總發(fā)電量 26 總經(jīng)濟效益 26 成本及投資年限的計算 27總結(jié) 28致謝 29參考文獻 30附錄 31第一章 緒論在工程技術(shù)、經(jīng)濟管理、科學研究和日常生活等諸多領(lǐng)域中，人們經(jīng)常遇到各種決策問題,如在一系列客觀或主觀的限制條件下，尋求使所關(guān)注的多個或某個指標達到最大（最?。┑臎Q策。例如，結(jié)構(gòu)設計要在滿足強度要求條件下選擇材料的尺寸，使其總重量最輕；資源分配要在有限資源約束下制定各用戶的分配數(shù)量，使資源產(chǎn)生的總效益最大；運輸方案要在滿足物質(zhì)需求和裝載條件下安排從各供應點到各需求點的運量和路線，使運輸總費用最低；生產(chǎn)計劃要按照產(chǎn)品工藝流程和顧客需求，制定原料、零件、部件等訂購、投產(chǎn)的日程和數(shù)量，盡量降低成本使利潤最高。在給定有限集的所有具備某些條件的子集中，按某種目標找出一個最優(yōu)子集的一類數(shù)學規(guī)劃，又稱組合規(guī)劃。組合最優(yōu)化發(fā)展的初期，研究一些比較實用的基本上屬于網(wǎng)絡極值方面的問題 ，如廣播網(wǎng)的設計 、開關(guān)電路設計、航船運輸路線的計劃、工作指派、貨物裝箱方案等?，F(xiàn)在應用的主要方面仍是網(wǎng)絡上的最優(yōu)化問題，如最短路問題、最大（小）支撐樹問題、最優(yōu)邊無關(guān)集問題、最小截集問題、推銷員問題等。常見的優(yōu)化方法有無約束優(yōu)化問題的解法、約束優(yōu)化問題的解法、線性規(guī)劃的解法、非線性規(guī)劃問題的解法。早在17世紀，英國科學家Newton發(fā)明微積分的時代，就已經(jīng)提出極值問題，后來又出現(xiàn)Lagrange乘數(shù)法。人們關(guān)于最優(yōu)化問題的研究工作，隨著歷史的發(fā)展不斷深入。 20世紀40年代以來，由于生產(chǎn)和科學技術(shù)研究突飛猛進地發(fā)展，特別是電子計算機日益廣泛應用，使最優(yōu)化問題的研究不僅成為一種 迫切需要，而且有了求解的有力工具，因此，最優(yōu)化理論和算法迅速發(fā)展起來，形成一個新的學科。最優(yōu)化理論和算法在實際應用中發(fā)揮越來越大的作用。這些問題描述非常簡單，并且有很強的工程代表性，但最優(yōu)化求解很困難，其主要原因是求解這些問題的算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現(xiàn)有計算機上實現(xiàn)，即所謂的“組合爆炸”。針對上述課題背景中所論述的組合優(yōu)化問題在求解中遇到的難題，本文在求解中將不會采用現(xiàn)有的方法，因為采用這些方法很難再計算上實現(xiàn)。因此，本文另辟蹊徑。對工程問題進行優(yōu)化設計，本質(zhì)上是根據(jù)優(yōu)化設計理論，采用優(yōu)化設計算法，運用計算機高質(zhì)量高速度的完成設計任務。因此，工程優(yōu)化設計包括建立數(shù)學模型和運用優(yōu)化設計方法求解這兩個方面的重要內(nèi)容。這也是本文解決實際問題時所用到的最核心的設計思想，即采用數(shù)學建模的方法將實際的太陽能小屋設計的問題轉(zhuǎn)化為一個多重組合優(yōu)化模型，再利用數(shù)學建模的一般思路，借助于計算機程序設計，獲得太陽能小屋的最佳設計方案。組合優(yōu)化往往涉及排序、分類、篩選等問題，它是運籌學的一個重要分支。一個組合優(yōu)化問題可以用二元組表示，其中表示可行解區(qū)域，中的任何一個元素稱為該問題的可行解，表示目標函數(shù)，滿足的可行解稱為該問題的最優(yōu)解。對于問題規(guī)模較小，枚舉時間是可以接受的；然而，隨著問題規(guī)模的增大，中解的個數(shù)會迅速增大，實際上要想遍歷所有的解，幾乎是不可能的。 多少年來，人們試圖尋找解答各種組合問題的多項式算法，這種研究工作在一些問題上已經(jīng)取得成功，其中包括最短路問題、最小支撐樹問題、網(wǎng)絡最大流問題、最小費用流以及運輸問題等等。⑵一般來說，組合優(yōu)化問題通常帶有大量的局部極值點，往往是不可微的、不連續(xù)的、多維的、有約束條件的、高度非線性的NP完全(難)問題 非線性的NP完全(難)問題；l ⑶由于組合優(yōu)化問題的解空間經(jīng)常是離散的集合，所以組合最優(yōu)化無法利用導數(shù)信息；l ⑶綜合上述特點，可以得出，精確地求解組合優(yōu)化問題的全局最優(yōu)解的“有效”算法一般是不存在的。 在實際的的生產(chǎn)、生活中，組合優(yōu)化問題有很多，也出現(xiàn)了一些經(jīng)典的組合優(yōu)化問題模型:覆蓋問題、裝箱問題、背包問題、指派問題、旅行商問題、影片遞送問題、最小生成樹問題、作業(yè)調(diào)度問題。以下列舉幾種典型的方法：完全枚舉法、準完全枚舉法、降序排列法、貪婪法、隨機法、松弛法、分割法、分支定界法、鄰域搜索法、 多起點鄰域搜索法、人工智能法。下面，本文先介紹目前已經(jīng)發(fā)展出來的比較優(yōu)秀的算法，其中一些算法，本文在求解中將會用到。解決線性規(guī)劃問題常用單純形法，具體如下：1. 單純形表法單純形法求解線性規(guī)劃的思路：一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。這就是迭代，直到目標函數(shù)實現(xiàn)最大值或最小值為止。為了確定初始基可行解，要首先找出初始可行基，其方法如下：對于線性規(guī)劃問題從中一般能直接觀察到存在一個初始可行基 1 對所有約束條件是“”形式的不等式，可以利用化為標準型的方法，在每個約束條件的左端加上一個松弛變量。為了便于迭代運算，可將上述方程組寫成增廣矩陣若將Z看做不參與基變換的基變量，它與的系數(shù)構(gòu)成一個基，這時可采用行初等變換將變換為零，使其對應的系數(shù)矩陣為單位矩陣。重復36，直到終止。與線性規(guī)劃相比決策變量是離散的變量。我們稱這樣的問題為整數(shù)規(guī)劃。步驟如下：將要求解的整數(shù)規(guī)劃問題稱為問題A，將它與相應的線性規(guī)劃問題稱為B。②B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止。用觀察法找問題A的一個整數(shù)可行解，一般可取試探，求得其目標函數(shù)值，并記作。 第一步：分支，在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù)。不考慮整數(shù)條件求解這兩個后繼問題。從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作出新的下界，若無可行解， 。若大于，且不符合整數(shù)條件，則重復第一步驟。這個方法就是指出怎樣找到適當?shù)母钇矫妫骨懈詈笞罱K得到這樣的可行域，它的一個有整數(shù)坐標的極點恰好是問題的最優(yōu)解。步驟如下：①令是相應線性規(guī)劃最優(yōu)解中為分數(shù)值的一個基變量，由單純形表的最終表得到其中（Q是指構(gòu)成基變量號碼的集合），（K指構(gòu)成非基變量號碼的集合）②將都分解成整數(shù)部分N與非負真分數(shù)之和，即而N表示不超過b的最大整數(shù)。在多指標的最優(yōu)化問題背景下所建立起來的數(shù)學規(guī)劃問題即為多目標規(guī)劃問題。多目標規(guī)劃能更好地兼顧統(tǒng)籌處理多種目標的關(guān)系，求得更切合實際要求的解。也可直接用數(shù)學方法求非劣解。步驟：主要目標的最優(yōu)集合為，再在集合內(nèi)求次重要目標的最優(yōu)解，設此時的最優(yōu)解集合為，如此繼續(xù)進行，直到求出最后一個目標函數(shù)的最優(yōu)解。 同樣的組合優(yōu)化問題，采用不同的近似求解方法，所得到的解、以及解的精度是不一樣的。某些算法，只要稍微做些改變，就有可能導致解的精度或搜索效率的大幅度提高。 第三章 應用實例——太陽能小屋設計在設計太陽能小屋時，需在建筑物外表面（屋頂及外墻）鋪設光伏電池，光伏電池組件所產(chǎn)生的直流電需要經(jīng)過逆變器轉(zhuǎn)換成220V交流電才能供家庭使用，并將剩余電量輸入電網(wǎng)。因此，在太陽能小屋的設計中，研究光伏電池在小屋外表面的優(yōu)化鋪設是很重要的問題。請參考附件提供的數(shù)據(jù)，對下列問題，分別給出小屋外表面光伏電池的鋪設方案，使小屋的全年太陽能光伏發(fā)電總量盡可能大，而單位發(fā)電量的費用盡可能小，并計算出小屋光伏電池35年壽命期內(nèi)的發(fā)電總量、經(jīng)濟效益（）及投資的回收年限。 在求解該問題時，都要求配有圖示，給出小屋各外表面電池組件鋪設分組陣列圖形及組件連接方式（串、并聯(lián)）示意圖，也要給出電池組件分組陣列容量及選配逆變器規(guī)格列表。在不同表面上，即使是相同型號的電池也不能進行串、并聯(lián)連接。解決這一問題不僅僅是組合優(yōu)化理論的應用，太陽能小屋的推廣使用對于解決全球的能源危機和環(huán)境污染都有十分重要的意義。如果能行之有效的解決此類問題，對于今后類似的有關(guān)設計類的問題，都可以采用類似的方法。問題要求采用貼附安裝方式對小屋的外表面進行光伏電池的優(yōu)化鋪設。然后比較不同光照條件下不同型號的光伏電池的收益，分析出屋頂?shù)牟煌瑐?cè)面應優(yōu)先選擇的電池類型。然后，對不同側(cè)面電池組件的串并聯(lián)方式進行優(yōu)化設計，盡量減少逆變器成本。該問題可以看做是一個全局優(yōu)化問題。逆變器的選擇取決于光伏組件的串并聯(lián)方式的選擇，從而影響整個系統(tǒng)的成本。對不同型號光伏電池的選擇，覆蓋方案的選取和光伏電池的串并聯(lián)形成了對方案的約束條件，即一個可行域。方案難點是決策變量多，利用軟件無法在較短的時間內(nèi)得到全局的最優(yōu)解。根據(jù)“貪心算法”的思想，分步驟找出每個子問題的最優(yōu)解，將得到的局部最優(yōu)方案作為最終的鋪設方案。⑴ 只有處于同一表面并且型號相同的電池板可以串聯(lián)。 ⑶ 假設大同市在未來35年內(nèi)的氣象條件與典型氣象年相同。 （5）逆變器的體積對于鋪設方案的影響。逆變器的選擇直接取決于光伏組件的串并聯(lián)，從而影響整個系統(tǒng)的成本，每一種光伏組件的串聯(lián)方式都需要一種滿足匹配條件且成本最小的逆變器與其