基于單純形法的最優(yōu)化方法的畢業(yè)設(shè)計(jì)論文

1、 摘 要： 最優(yōu)化方法普遍的應(yīng)用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸、國防、通信、建設(shè)、等各個(gè)方面與我們的生活息息相關(guān)；最優(yōu)化方法主要用來解決最優(yōu)計(jì)劃、最優(yōu)決策、最優(yōu)設(shè)計(jì)、最優(yōu)分配等最優(yōu)化問題。本文主要研究的內(nèi)容是通過單純形方法對最優(yōu)化問題的解決進(jìn)行歸納總結(jié)，分析最優(yōu)化問題所涉及的原理和方法，使用軟件對最優(yōu)化問題進(jìn)行實(shí)踐仿真測試，并將最優(yōu)化問題推廣應(yīng)用到生活當(dāng)中去。 關(guān)鍵詞: 最優(yōu)化 單純形方法 仿真 AbstractOptimization method is widely used in industry, agriculture, commerce, transportation, defens

2、e, communications, construction, and other aspects of our lives; the optimization method is used to solve the optimal planning, optimal decision-making, optimal design, optimal allocation optimization problem. The main research content of this paper is summarized by the simplex method to solve the o

3、ptimization problem, the principle and method of optimization analysis of the problems involved in the use of software simulation test of practical optimization problems, and promote the use of the optimization problem to life.Keywords : optimization Simplex method Simulation 目目 錄錄第一章 緒論11.1最優(yōu)化問題簡述1

4、1.2 單純形方法的簡述2第二章 最優(yōu)化問題研究32.1 最優(yōu)化問題簡介32.1.1 最優(yōu)化問題的發(fā)展32.2 最優(yōu)化問題的常見方法42.3 最優(yōu)化的工作步驟52.3.1 模型的基本要素52.3.2 最優(yōu)解的概念72.4 最優(yōu)化方法的應(yīng)用7第三章 基于單純形法的最優(yōu)化方法103.1 單純形法方法及其特點(diǎn)103.2 單純形方法的基本思想103.2.1 單純形法的迭代原理113.3 基于單純形法的最優(yōu)化設(shè)計(jì)133.3.1 單純形法處理最優(yōu)化的一般解題設(shè)計(jì)步驟可歸納如下133.3.2 最優(yōu)解可能出現(xiàn)下列的情況14第四章 軟件仿真實(shí)驗(yàn)154.1 軟件簡介154.2 實(shí)驗(yàn)仿真16第五章 結(jié)論19致謝20

5、參考文獻(xiàn)21第 1 頁 共 21 頁第一章緒論最優(yōu)化問題的解決方法是在最近幾十年漸漸形成的。那么可想而知，就要提到最優(yōu)化問題的主要研究對象：是各種有組織系統(tǒng)的管理問題和一些生產(chǎn)經(jīng)營活動(dòng)。最優(yōu)化方法產(chǎn)生的目的是在于對所研究問題的整體，能有一個(gè)合理運(yùn)用物質(zhì)、財(cái)產(chǎn)和人力的最優(yōu)方案，并且讓整體的效能達(dá)到一個(gè)增漲和提高，以最終達(dá)到最優(yōu)化解決問題的目標(biāo)。實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)，實(shí)踐證明，由于人們掌握的科學(xué)技術(shù)的不斷更新和進(jìn)步，人類的發(fā)展生產(chǎn)經(jīng)營規(guī)模的不斷擴(kuò)大，最優(yōu)化方法已經(jīng)漸漸深入人心，成為了一個(gè)重要的理論依據(jù)在指導(dǎo)現(xiàn)代科學(xué)管理中起到重要的作用?？傊?，現(xiàn)在最優(yōu)化方法已經(jīng)變得越來越重要了，被普遍的應(yīng)用到經(jīng)

6、濟(jì)、管理、工程、國防等各個(gè)領(lǐng)域。1.1最優(yōu)化問題簡述最優(yōu)化問題簡單的可以說是一種數(shù)學(xué)問題，它的理論和算法是一個(gè)非常重要的數(shù)學(xué)分支，又被人們叫做數(shù)學(xué)規(guī)劃。所針對解決的問題就是在很多的計(jì)劃方案里確定什么計(jì)劃方案最好，并且找出最優(yōu)計(jì)劃方案進(jìn)行具體實(shí)施。下面我們就針對工程類問題的最優(yōu)化處理進(jìn)行一下簡單的介紹，讓大家了解最優(yōu)化方法大概應(yīng)該怎么去應(yīng)用。首先，我們要進(jìn)行問題的轉(zhuǎn)化，即把工程問題轉(zhuǎn)化成數(shù)學(xué)問題，建立數(shù)學(xué)模型，也就是說使用數(shù)學(xué)表達(dá)式來更具體的描述工程上的問題。然后，在建好數(shù)學(xué)模型的基礎(chǔ)上，根據(jù)數(shù)學(xué)模型里的特點(diǎn)來選擇用那種最優(yōu)化的設(shè)計(jì)方法，要求出問題的解還需要借助計(jì)算機(jī)這一現(xiàn)代科技必不可少的工具，

7、通過計(jì)算機(jī)上的軟件編寫程序來求出最優(yōu)解，也就是所要求得最優(yōu)化的結(jié)果。所以，在這就可以總結(jié)一下工程上的最優(yōu)化問題無非就是數(shù)學(xué)建模和最優(yōu)化方法的選擇以及計(jì)算機(jī)軟件編程方面的應(yīng)用等一些內(nèi)容。其中，工程優(yōu)化設(shè)計(jì)成敗的關(guān)鍵是從工程實(shí)際命題中抽象出的正確的數(shù)學(xué)模型。 這也是工程設(shè)計(jì)工作者進(jìn)行優(yōu)化設(shè)計(jì)時(shí)所要完成的主要任務(wù)。 我們已經(jīng)了解到工程類問題第 2 頁 共 21 頁的最優(yōu)化設(shè)計(jì)可以先建立數(shù)學(xué)模型?，F(xiàn)在就針對數(shù)學(xué)模型來進(jìn)行近一步的分析，最優(yōu)化問題設(shè)計(jì)時(shí)的數(shù)學(xué)模型一般包括一些設(shè)計(jì)的變量、目標(biāo)函數(shù)和約束條件。其中這三個(gè)基本要素：設(shè)計(jì)變量里的個(gè)數(shù)決定了應(yīng)該設(shè)計(jì)空間的維數(shù)；還有設(shè)計(jì)變量的要求那就是，在滿足設(shè)計(jì)基

8、本要求的前提下，把那些對設(shè)計(jì)目標(biāo)影響比較大的參數(shù)選為設(shè)計(jì)的變量，并根據(jù)具體問題具體分析的原則，給變量賦值來簡化設(shè)計(jì)變量的數(shù)量等?？偠爬ǎ鉀Q這一類最優(yōu)化問題我們至少要注意兩點(diǎn)：（1）要有明確的問題方向，也即是說通過實(shí)際面臨的問題的概況，進(jìn)行簡單的描述進(jìn)而轉(zhuǎn)化成純粹的數(shù)學(xué)問題，然后建立成一個(gè)數(shù)學(xué)建模的過程；（2）既然建好了數(shù)學(xué)模型接下來就是求解過程，也就是說用已經(jīng)掌握的最優(yōu)化的相關(guān)知識(shí)來求解出最優(yōu)的處理方案 。數(shù)學(xué)問題來源于生活，然后又可以用數(shù)學(xué)知識(shí)來反作用于生活，在掌握一定的數(shù)學(xué)基礎(chǔ)的前提下，結(jié)合日常生活當(dāng)中可能出現(xiàn)的數(shù)學(xué)問題， 通過適當(dāng)?shù)囊?guī)劃安排，運(yùn)用數(shù)學(xué)原理求解出行之有效的最優(yōu)化方案。在

9、最優(yōu)化介紹的末尾，我們不僅要了解最優(yōu)化的一些簡單常識(shí)，而且要更進(jìn)一步懂得研究最優(yōu)化問題的意義所在，最優(yōu)化方法致力于解決日常生活中的一些常見規(guī)劃安排問題，例如，如果要完成一件事情怎樣能資源最省，時(shí)間最省，并且效率高，產(chǎn)值高等常見的生活中的問題，這就需要你運(yùn)用最優(yōu)化的知識(shí)來進(jìn)行解決，用最優(yōu)化方法來尋找一種更科學(xué)合理的方案來解決這些問題。1.2 單純形方法的簡述數(shù)學(xué)最優(yōu)化中，由喬治伯納德丹齊格（George Dantzig）發(fā)明的單純形法（simplex algorithm）是線性規(guī)劃問題的數(shù)值求解的流行技術(shù)。這二者都使用了單純形的概念，它是 N 維中的 N + 1 個(gè)頂點(diǎn)的凸包，是一個(gè)多胞體：直線

10、上的一個(gè)線段，平面上的一個(gè)三角形，三維空間中的一個(gè)四面體，等等。單純行法問題的理論依據(jù)為：在可行域?yàn)?n 維向量空間 Rn 中的多面凸集的線性規(guī)劃問題中，如果其最優(yōu)值存在則必在這個(gè)凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對應(yīng)的可行解稱為基本可行解。第 3 頁 共 21 頁第二章最優(yōu)化問題研究2.1 最優(yōu)化問題簡介最優(yōu)化問題，主要是指以下形式的問題：給出一個(gè)函數(shù)，查找一個(gè)元素使所有 A 的元素，取得最小化；或者最大化。這種類型有時(shí)也被稱為“數(shù)學(xué)規(guī)劃”（例如，線性規(guī)劃） 。許多理論和實(shí)際問題可被建模為這樣的一般性框架。最優(yōu)化，是應(yīng)用數(shù)學(xué)的一個(gè)分支。既然提到最優(yōu)化問題是應(yīng)用數(shù)學(xué)的一個(gè)分支，再此我就簡略闡述一下最優(yōu)

11、化問題的一些數(shù)學(xué)意義：人們?yōu)榱私鉀Q最優(yōu)化問題從而提出很多種求解的方法。然而從數(shù)學(xué)意義上來說，其實(shí)求最優(yōu)化問題就是一種求極值的問題，也就是說在給定的一組條件約束的條件下，可以讓系統(tǒng)的里的目標(biāo)函數(shù)達(dá)到極大值或極小值。然而，如果你從經(jīng)濟(jì)上來看，那就可以看成是在一定物質(zhì)，人力的條件下，通過最優(yōu)化方法可以讓系統(tǒng)的經(jīng)濟(jì)效益達(dá)到極值；或者也可以說是在效益相等的前提下，讓投入的人力、資源等物質(zhì)越少越好。2.1.1 最優(yōu)化問題的發(fā)展最優(yōu)化問題離不開人類的發(fā)展，人類的不斷發(fā)展也讓最優(yōu)化問題變得越來越完善，早在公元前五百年的古希臘人就從建筑美學(xué)中懂得了黃金分割比，因?yàn)橹挥邪茨莻€(gè)黃金分割比來建設(shè)建筑才可以讓建筑更美達(dá)

12、到建筑里的最優(yōu)化。到目前為止，在生活等各個(gè)方面中的黃金分割比仍然被廣泛使用。隨著人們知識(shí)的增長，見識(shí)的開闊，很多有學(xué)識(shí)的人開始研究用具體的數(shù)學(xué)方法來打開最優(yōu)化方法研究的瓶頸。歷史會(huì)證明一切，在最優(yōu)化問題發(fā)展的過程中，不斷被科學(xué)家給以證明并不斷完善最優(yōu)化方法。為什么古代歐洲的城堡幾乎都是圓形的呢？那是因?yàn)榻o定的周邊圓行區(qū)域所包含的面積是最大的，這是阿基米德所證明的，也是前期人們對最優(yōu)化問題的一種研究與追求。但是，直到 17 世紀(jì)以后，使用科學(xué)的方法來解決最優(yōu)化問題才算真正形成。在 17 世紀(jì)，牛頓和萊布尼茨在其創(chuàng)作的微積分中，他們就發(fā)現(xiàn)了求解含有多個(gè)自變量的實(shí)值函數(shù)的最第 4 頁 共 21 頁大

13、值和最小值得方法。時(shí)間在推移，人類在進(jìn)步，直到第二次世界大戰(zhàn)，不僅是人類的大決戰(zhàn)，更是科學(xué)技術(shù)進(jìn)步的大熔爐。戰(zhàn)時(shí)軍事的需要從而使科學(xué)技術(shù)和生產(chǎn)以高速發(fā)展，最優(yōu)化問題的解決方法也已經(jīng)無法被以往的方法所解決，這也就導(dǎo)致了現(xiàn)代最優(yōu)化方法的形成與出現(xiàn)。近現(xiàn)代最優(yōu)化問題的出現(xiàn)其中的一些標(biāo)志性事件有：以蘇聯(lián) .康托羅維奇和美國 G.B.丹齊克為代表的線性規(guī)劃；以美國庫恩和塔克爾為代表的非線性規(guī)劃；以美國 R.貝爾曼為代表的動(dòng)態(tài)規(guī)劃；以蘇聯(lián)龐特里亞金為代表的極大值原理等。 ”這些人的研究很好的推進(jìn)了最優(yōu)化問題研究的進(jìn)步，這些近現(xiàn)代的方法慢慢的都形成了它們各自的體系，這很好的對促進(jìn)我們當(dāng)代的運(yùn)籌學(xué)，最優(yōu)化問題

14、，控制論和系統(tǒng)工程等的發(fā)展起到了很重要的作用。2.2 最優(yōu)化問題的常見方法任何事情都會(huì)有它的研究方法，當(dāng)然最優(yōu)化問題也不例外。要解決一個(gè)問題就要有一個(gè)切實(shí)可行的方法，針對不同類型的最優(yōu)化問題我們可以有不同的處理方法，即使是遇到相同的最優(yōu)化問題我們也可以用各種不同的方法來處理這一個(gè)問題。我們從另一個(gè)方面來講，不同類型的模型也要用不同的最優(yōu)化方法來處理。就目前來看，解決最優(yōu)化的方法大體上可以分為解析法、直接法、數(shù)值計(jì)算法等。（1） 解析法：這種方法只適應(yīng)于那些目標(biāo)函數(shù)與約束條件是很明顯的解析式表達(dá)式的情況。解決這種問題的方法是：先要求出最優(yōu)的必要條件，從而得到一組方程或不等式，接下來，就要進(jìn)行求解

15、這組方程和不等式，一般可以用求導(dǎo)數(shù)的方法或者變分法來求出必要的條件，然后再用必要條件來簡化所求的問題。（2） 直接法：當(dāng)遇到目標(biāo)函數(shù)是那些較為復(fù)雜或者不是很確定的可變函數(shù)時(shí)，沒有辦法用解析法求解出必要條件的時(shí)候。我們這時(shí)可以用直接查找的辦法通過若干次的迭代從而得到最優(yōu)值。往往這種方法得到的結(jié)果是根據(jù)經(jīng)驗(yàn)和試驗(yàn)來實(shí)現(xiàn)的。還有當(dāng)我們遇到一維（即單變量極值）的查找時(shí)，我們主要使用消去法或者多項(xiàng)式插值法；而當(dāng)遇到多維（即多變量極值）查找的問題時(shí)，第 5 頁 共 21 頁我們主要是應(yīng)用的爬山法。 （3） 數(shù)值計(jì)算法：我們來說一下這個(gè)方法，這個(gè)方法也是一種直接的方法。它往往是以梯度法為基礎(chǔ)的一種解決最優(yōu)化

16、的方法，所以我們大家可以理解為是一種解析與數(shù)值計(jì)算相組合的方法。（4） 本次畢業(yè)設(shè)計(jì)研究的主要內(nèi)容是基于單純形法的最優(yōu)化方法：單純形法的方法的優(yōu)點(diǎn):單純形法它嘗試從空間的一個(gè)頂點(diǎn)移動(dòng)到另一個(gè)頂點(diǎn)，直到人們找到最優(yōu)點(diǎn)為止。單純形法可以解決多維問題，那是因?yàn)樗鼘D形法轉(zhuǎn)化成了代數(shù)法，從而避免掉了多維空間的不可描述性。2.3 最優(yōu)化的工作步驟我們?nèi)祟愄岢鲆粋€(gè)問題發(fā)現(xiàn)一種方法，都有它的用途。都有它的工作方法。再此，我們就來進(jìn)行工作步驟的具體討論。在我們使用最優(yōu)化方法解決現(xiàn)實(shí)中我們自己遇到的實(shí)際問題時(shí)，我們通?？梢杂靡韵鹿ぷ鞣椒ú襟E：（1）首先，我們要針對最優(yōu)化提出關(guān)于他的問題，然后分工去進(jìn)行一些關(guān)于這

17、個(gè)問題的一些數(shù)據(jù)和相應(yīng)資料的收集采樣；（2）這是在第二點(diǎn)也是很重要的一環(huán)，那就是要建立數(shù)學(xué)模型關(guān)于你所要解決的最優(yōu)化問題，并且還要確定最優(yōu)化問題里面包含的一些變量，確定變量之后，我們還要列出關(guān)于這個(gè)問題的目標(biāo)函數(shù)和與它對應(yīng)的約束條件；（3）在上一步建立好模型之后，我們就要對問題的模型進(jìn)行更進(jìn)一步的模型分析，分析后，我們來選擇應(yīng)該采用哪種最優(yōu)化方法來解決問題；（4）以上都齊全了以后我們就要開始進(jìn)行求解了，對于求解現(xiàn)在我們一般都是借助計(jì)算機(jī)軟件程序，在計(jì)算機(jī)上進(jìn)行操作求得結(jié)果；（5）最后，在上一步我們求好解以后，我們還要對所遇到的問題進(jìn)行一些常規(guī)的測試并根據(jù)問題的具體情況進(jìn)行完善和實(shí)地驗(yàn)證。從上述

18、五個(gè)工作方法步驟中我們可以看出，他們之間一環(huán)扣一環(huán)，環(huán)環(huán)相連，相互照應(yīng)并且相互制約互相有影響，牽一發(fā)而動(dòng)全身。所以，在以后我們的具體實(shí)踐工作里我們要反復(fù)的進(jìn)行這幾個(gè)步驟，來確保我們所遇到的問題能最優(yōu)化的完善解決。2.3.1 模型的基本要素第 6 頁 共 21 頁在此，我專門分了一個(gè)小節(jié)來進(jìn)一步介紹最優(yōu)化工作步驟里的模型這一個(gè)方面。將生活中實(shí)際的問題轉(zhuǎn)化為我們所要的數(shù)學(xué)模型，它的重要性就好比，建筑里的地基這一項(xiàng)，提出問題，就好比選好地址，而數(shù)學(xué)建模就好比是地基的構(gòu)建，萬丈高樓平地起，孰不知只有地基打的深他才敢蓋起那萬丈的高樓??！我們這里主要來說一下最優(yōu)化模型，他主要包含了一些變量、約束條件和目標(biāo)

19、函數(shù)三個(gè)基本的的要素。下面我們來在具體分析一下：（1）變量：大多數(shù)情況下都是指在最優(yōu)化問題中一些未確定的某些量，通常我們可以用x=(x1，x2,xn)T 來進(jìn)行表示；（2）約束條件：通常是指我們在求解最優(yōu)解的過程中對我們問題中的變量的一些包括時(shí)間上、技術(shù)上、和原料的限制等，形象生動(dòng)的說，就好比有人給你布置一道任務(wù)，要求你在一天之內(nèi)就要完成，其中這個(gè)一天之內(nèi)就是一種約束條件。針對約束條件我們的原則是越接近實(shí)際情況越好，因?yàn)橹挥羞@樣才能讓我們得出最貼近實(shí)際的最優(yōu)解。約束條件在這我們可以用 gi(x)0 表示 i=（1,2，m） ，m 表示約束條件數(shù)；或 xR(R表示可行集合)。 （3）目標(biāo)函數(shù)：所

20、謂目標(biāo)函數(shù)就是我們針對這個(gè)最優(yōu)化問題到底要達(dá)到一種什么樣的程度達(dá)到一種什么樣的標(biāo)準(zhǔn)，而目標(biāo)函數(shù)就是把實(shí)際問題數(shù)學(xué)化了在計(jì)算式更加符合數(shù)學(xué)的描述方式，一般我們可以用 f(x)來表示，即 f(x)=f(x1，x2,xn)。目標(biāo)函數(shù)總歸還是目標(biāo)函數(shù)，它還是必須要在規(guī)定的約束條件的前提下，達(dá)到系統(tǒng)功能的最大值或者最小值。針對最優(yōu)化問題我們還可以有一些的分類 ：可以 根據(jù)其最優(yōu)化問題中的變量、約束條件、目標(biāo)函數(shù)、問題的性質(zhì)、時(shí)間的因素和函數(shù)關(guān)系等不同的情況，又可以將最優(yōu)化問題分成許多種不同的類型。 根據(jù)我們知道的一些函數(shù)功能的解析性質(zhì)，我們還可以進(jìn)一步對各種方法進(jìn)行一些分類。例如，若目標(biāo)函數(shù)和約束條件都

21、是線性的，那么也就是說形成了線性規(guī)劃。針對線性規(guī)劃，我們有專門的解法：例如單純形法、橢球法、解乘數(shù)法等。如果當(dāng)目標(biāo)函數(shù)或約束條件中有一為非線性函數(shù)時(shí),那么，這個(gè)時(shí)候就形成非線性規(guī)劃。而當(dāng)目標(biāo)函數(shù)是二次的時(shí)候,而約束條件是線性的時(shí)候，那么這個(gè)時(shí)候，則稱為二次規(guī)劃?，F(xiàn)在來說二次規(guī)劃的理論和方法都已經(jīng)比較成熟。當(dāng)我們遇到目標(biāo)函數(shù)具有某些函數(shù)的平方和的形式，則那時(shí)就又有專門用于求解平方和問題的優(yōu)化方法了。第 7 頁 共 21 頁而當(dāng)我們碰到目標(biāo)函數(shù)具有多項(xiàng)式的形式時(shí)，又可以形成一類幾何規(guī)劃了。 2.3.2 最優(yōu)解的概念 當(dāng)我們遇到一個(gè)問題，我們就會(huì)想到要想辦法去解決他，也就是說要求出它的答案求出它的解

22、。同樣的最優(yōu)化問題也是要求得解的，它的解我們通常叫做最優(yōu)解。在這我們就來說一下最優(yōu)解的問題。最優(yōu)解也分很多情況，當(dāng)我們只考慮約束集合中的一些局部范圍內(nèi)的情況時(shí)，這時(shí)候的最優(yōu)解我們就稱為局部最優(yōu)解；然而相反的當(dāng)我們以考察整個(gè)約束集合為對象時(shí)，這時(shí)候的解我們叫做總體最優(yōu)解。當(dāng)我們針對各種不同的最優(yōu)化問題時(shí)，這時(shí)最優(yōu)解也會(huì)被賦予各種不同的含義，并且還會(huì)使用專用的名詞來進(jìn)行闡述。下面舉個(gè)例子，就像在對策論和數(shù)理經(jīng)濟(jì)模型里的解我們又稱為平衡解；而當(dāng)我們在控制類的問題里我們又稱為最優(yōu)控制；還有當(dāng)我們在多目標(biāo)的決策問題里我們稱為非劣解。理想很豐滿，但是現(xiàn)實(shí)很骨感！當(dāng)在我們解決現(xiàn)實(shí)中的實(shí)際問題時(shí)，并不會(huì)像理想

23、里的那樣標(biāo)準(zhǔn)，往往現(xiàn)實(shí)中遇到的實(shí)際問題都是非常的錯(cuò)綜復(fù)雜，而那種我們理想狀態(tài)的最優(yōu)解一般都不是那么容易去求得，即使是可以求解到也是要付出非常高的代價(jià)的，所以在我們求解現(xiàn)實(shí)中問題最優(yōu)解時(shí)往往要根據(jù)具體問題具體分析的方法，只要求的解在一定可以承受的范圍內(nèi)條件下，也不一定非要過分的來強(qiáng)調(diào)一定要最優(yōu)，只要是能最接近最優(yōu)就可以了，因?yàn)槟Ｐ褪抢硐氲模乾F(xiàn)實(shí)的實(shí)際是有誤差的，所以無法確定一定最優(yōu)。相應(yīng)的針對這種情況的存在，在最優(yōu)化問題研究的早期，大約五十年代初，就有人先見的提到了次優(yōu)化這一概念和他相對應(yīng)的次優(yōu)解的概念。以上關(guān)于解的這些發(fā)現(xiàn)與討論都引出一個(gè)問題，那就是我們在提出這些概念時(shí)關(guān)于最優(yōu)化所創(chuàng)建的模

24、型只是一種近似的模型，再另外加上在現(xiàn)實(shí)的實(shí)際問題里又有很多不確定的因素，尤其是當(dāng)含有非定量因素時(shí)很難在一個(gè)模型里都全部的考慮進(jìn)去。從方法層面來說，在處理這些問題上，目前我們還沒有一些很有效的辦法用來解決這些復(fù)雜的模第 8 頁 共 21 頁型。2.4 最優(yōu)化方法的應(yīng)用有的人會(huì)問，我們?yōu)槭裁匆獙W(xué)習(xí)知識(shí)，我們?yōu)槭裁匆芯恳粋€(gè)問題，我想那是因?yàn)閷W(xué)以致用的原因，應(yīng)為我們要使用它所以我們?nèi)W(xué)習(xí)去研究。當(dāng)然話說回來了，我們研究最優(yōu)化問題不也是為了應(yīng)用嗎？所以在這一段我們就來探討一下最優(yōu)化問題的應(yīng)用。通常我們針對最優(yōu)化先進(jìn)行一些大概總體方面的分析，我們現(xiàn)在可以從最優(yōu)的控制、最優(yōu)的設(shè)計(jì)、最優(yōu)的管理、最優(yōu)的規(guī)劃這

25、些大的方面來一點(diǎn)點(diǎn)的著手分析他的應(yīng)用。 （1）我們先來說一下最優(yōu)控制的應(yīng)用有哪些，一般主要我想應(yīng)該集中在對各種人類構(gòu)建的控制系統(tǒng)的優(yōu)化。可以舉一些常見例子，像馬上就要進(jìn)行的俄羅斯的衛(wèi)國戰(zhàn)爭的閱兵式上我們從彩排中可以看到很多型號的導(dǎo)彈，在軍事上用到的優(yōu)化設(shè)計(jì)就是導(dǎo)彈系統(tǒng)的最優(yōu)化設(shè)計(jì)，也就是說在保證完成任務(wù)的前提下，我們可以用最優(yōu)控制使用盡可能少的燃料來完成相同的任務(wù)。還有我們國家的航天，航空母艦，飛機(jī)等系統(tǒng)也都是需要用到最優(yōu)化控制來掌控整個(gè)系統(tǒng)的調(diào)配；即便是民用的一些行業(yè)，像工廠，電力調(diào)度等也是需要合理地運(yùn)用最有設(shè)計(jì)來解決問題的；（2）第二個(gè)我們來說一下最優(yōu)設(shè)計(jì)的一些應(yīng)用，目前世界上很多國家在工

26、程制造領(lǐng)域都將最優(yōu)設(shè)計(jì)用在其中，像在飛機(jī)，輪船，汽車的外觀設(shè)計(jì)上都追求在外形上怎么減少他們在運(yùn)動(dòng)中所遇到的阻力，怎么設(shè)計(jì)能讓他的能耗最低，能節(jié)能減排，促進(jìn)環(huán)保，美化自然。還有在我們學(xué)的電子電路這一塊，電子原件怎么最優(yōu)設(shè)計(jì)，才能制作出即功能全面又?jǐn)y帶方便，怎么能更符合人體工學(xué)讓我們?nèi)祟惛械礁鼭M意都等待著最優(yōu)設(shè)計(jì)來解決這一問題。還有在一些工業(yè)生產(chǎn)方面，我們可以用最優(yōu)設(shè)計(jì)來設(shè)計(jì)出最優(yōu)的原料配比，來讓產(chǎn)品最優(yōu)的服務(wù)于大眾，更好的促進(jìn)我們?nèi)祟愇拿饔趾糜挚斓倪M(jìn)步；（3）最優(yōu)管理這個(gè)也是很好理解的，我們無論是個(gè)人還是一個(gè)企業(yè)都要學(xué)會(huì)管理自己的一些東西，個(gè)人來說，你要自己來管理你的時(shí)間、工作、生活等各個(gè)方面，

27、然而只有你運(yùn)用了最優(yōu)化管理才能使自己的生活得到一個(gè)提升，自己只是一個(gè)小的方面，我們來看看企業(yè)上，一個(gè)企業(yè)的管理層如果懂得了使用最優(yōu)管理的方法來管理企業(yè)員工，那他們的企業(yè)一定會(huì)第 9 頁 共 21 頁非常的高效率，在日常公司管理中制定詳細(xì)科學(xué)的計(jì)劃，合理調(diào)度，合理管理運(yùn)營，還有隨著現(xiàn)在計(jì)算機(jī)信息技術(shù)在管理中的運(yùn)用，更讓最優(yōu)管理如虎添翼，插上了騰飛的翅膀；（4）這一點(diǎn)我們說一下最優(yōu)規(guī)劃，并不是因?yàn)樘诤竺嫣岬剿筒恢匾?，恰恰相反我感覺規(guī)劃還是挺重要的，正如俗話說的凡是預(yù)則立，不預(yù)則廢；這就說明了規(guī)劃還是挺重要的。我們應(yīng)該宜未雨而綢繆，勿臨渴而掘井。同樣告誡我們規(guī)劃的重要性。規(guī)劃在我們國家可以說非

28、常常見，大家耳熟能詳?shù)木陀惺晃逡?guī)劃，十二五規(guī)劃等，這就說明最優(yōu)規(guī)劃在我們的現(xiàn)代國家部門有著舉足輕重的地位，在實(shí)際的現(xiàn)實(shí)生活里，無論是國家部門還是農(nóng)業(yè)，工業(yè)，能源資源等的方面都需要一個(gè)長遠(yuǎn)而合理的最優(yōu)規(guī)劃。因?yàn)橐粋€(gè)重要的最優(yōu)規(guī)劃決定了整個(gè)社會(huì)的發(fā)展方向！所以我們不容忽視最優(yōu)化問題在我們生活里的一些應(yīng)用，因?yàn)樗臀覀兊纳钕⑾⑾嚓P(guān)！第 10 頁 共 21 頁第三章基于單純形法的最優(yōu)化方法3.1 單純形法方法及其特點(diǎn)現(xiàn)在，本章我們是基于單純形法的方面來解析一下最優(yōu)化方法。首先我們既然提到單純行法，就要大概知道它是什么，雖然在前面的段落也有提到，但在這里我們可以簡單的說，單純形法就是求解線性規(guī)劃問題

29、的一般方法。關(guān)于單純形法的理論依據(jù)是這樣定義的：也就是說，在給定的線性規(guī)劃問題里，當(dāng)可行域是 n 維向量空間 Rn 中的多面凸集，它的最優(yōu)值假如存在則必在該凸集的某頂點(diǎn)處達(dá)到。而這個(gè)頂點(diǎn)它所對應(yīng)的解決方法的可行解我們就稱它為基本可行解。并且在這還要提一下，單純形法，它是一種直接、快速搜索求得最小值的方法，它最大的優(yōu)點(diǎn)就是在于對目標(biāo)函數(shù)的解析性沒有太多的要求，并且收斂速度快，還有就是應(yīng)用范圍較廣。3.2 單純形方法的基本思想人是一棵會(huì)思考的蘆葦，人和動(dòng)物的區(qū)別就在于人是有思想的動(dòng)物?，F(xiàn)在我們就針對我們的研究對象單純形法來說一下它在解決問題的時(shí)候的主要基本的思想。首先，要知道單純行法是一種多變量函

30、數(shù)來尋找最優(yōu)化的方法，它的基本主要思想是這樣的：第一步，我們要找到一個(gè)基本的可行解，然后要對這個(gè)解進(jìn)行判定，看看它是否是最優(yōu)解；如果是那就好解決了，但是當(dāng)如果不是的時(shí)候，我們就要遵循一定的規(guī)則轉(zhuǎn)換到另一個(gè)改善的基本可行解，然后再接第 11 頁 共 21 頁著對它進(jìn)行判定，如果是最優(yōu)解就可以了，如果還是不是最優(yōu)解，那就再進(jìn)行轉(zhuǎn)換判斷，不斷重復(fù)的遵循這個(gè)方法進(jìn)行判定，直到得到最優(yōu)解再結(jié)束。由于存在的基本可行解的個(gè)數(shù)是有限的，所以我們通過有限次數(shù)的轉(zhuǎn)換肯定可以得出問題所要求的最優(yōu)解。反正只要遵循這個(gè)方法就可以求出最優(yōu)解。就算當(dāng)出現(xiàn)問題沒有最優(yōu)解的那種情況也能使用這種方法來進(jìn)行判斷。因?yàn)槲覀兛梢愿鶕?jù)最

31、優(yōu)化理論及時(shí)的發(fā)現(xiàn)，并且停止計(jì)算，來避免錯(cuò)誤及無效運(yùn)算。3.2.1 單純形法的迭代原理枚舉法：如果線性規(guī)劃問題存在最優(yōu)解，則肯定可以在某個(gè)頂點(diǎn)上達(dá)到，即在某個(gè)基本可行解上可以取得最優(yōu)解。因此，針對線性規(guī)劃問題，就是把所有基本可行解都找出來，然后逐一進(jìn)行比較，從而可以求出最優(yōu)解。逐步改善法：針于線性規(guī)劃的問題，我們第一步要找出一個(gè)基本的可行解，再判斷其對應(yīng)的是否為最優(yōu)解，如果求得的不是最優(yōu)解，則就應(yīng)該再去尋求一個(gè)更好的基本可行解，直到我們找到最優(yōu)解為止，但是當(dāng)我們使用這種逐步改善的求解方法時(shí)，我們就需要解決以下三個(gè)問題： （1）我們怎么來判斷當(dāng)前的基本可行解是否已經(jīng)達(dá)到了最優(yōu)解 （2）如果當(dāng)前解

32、不是最優(yōu)解，以及我們?nèi)绾稳ふ乙粋€(gè)比當(dāng)前解更好的基本可行解 （3）還有在開始的時(shí)候，我們?nèi)绾蔚玫揭粋€(gè)初始的基本可行解。下面具體舉一個(gè)關(guān)于單純形法的線性規(guī)劃的例子：例題 求解下列線性規(guī)劃問題的最優(yōu)解 004155160203025max211212121xxxxxxxxxz解：把上面的式子化成為標(biāo)準(zhǔn)形式第 12 頁 共 21 頁04155160203000025max515142132154321xxxxxxxxxxxxxxz第一步：首先要確定一個(gè)初始基本可行解；基本可行解就是滿足非負(fù)條件的基本解，因此要在約束矩陣 A 中找出一個(gè)可逆的基矩陣。 10001010150012030A這里 m=3，

33、3 階可逆方陣，可以看出 x3,x4,x5 的系數(shù)列向量是線性獨(dú)立的，這些向量構(gòu)成一個(gè)基 ，對應(yīng)的基變量為 x3,x4,x5，x1,x2 為非基),(100010001543)0(pppB變量。將基變量用非基變量表示，由(2)得：將(3)代入目標(biāo)函數(shù)得 Z=5x1+2x2+0令非基變量 x1=x2=0,代入(3),得到一個(gè)基可行解 X(0)X(0)=(0,0,160,15,4)第二步：從當(dāng)前基可行解轉(zhuǎn)換為更好的基可行解；從數(shù)學(xué)角度看，x1,x2 的增加將會(huì)增加目標(biāo)函數(shù)值，從目標(biāo)函數(shù)值中 x1,x2前的系數(shù)看，x1 前的系數(shù)大于 x2 前的系數(shù)，所以讓 x1 從非基變量轉(zhuǎn)為基變量，稱為進(jìn)基變量，

34、怎樣確定離基變量：因?yàn)?x2 仍為非基變量，故 x2=0第 13 頁 共 21 頁則(3)式變?yōu)閙in=3，所以當(dāng) x1=3 時(shí)，x4 第一個(gè)減少到 0，所以 x4 出基則 此時(shí)非基變量為 x2,x4,用非基變量表示基變量，代入(3) 將(4)代入目標(biāo)函數(shù)得 Z=15+x2-x4第三步：繼續(xù)迭代x2 進(jìn)基，x4 仍為非基變量，令 x4=0，則(4)式表示為 min=5，所以當(dāng) x2=5 時(shí)，x3 首先減少到 0，所以 x3 出基則 此時(shí)非基變量為 x3,x4,用非基變量表示基變量，代入(4) 第 14 頁 共 21 頁將(5)代入目標(biāo)函數(shù)得 此時(shí)若非基變量 x3,x4 的值增加，只能使 Z 值

35、下降所以 X(2)為最優(yōu)解，Z*=20, X*=(2,5, 0,0,2)3.3 基于單純形法的最優(yōu)化設(shè)計(jì) 3.3.1 單純形法處理最優(yōu)化的一般解題設(shè)計(jì)步驟可歸納如下：（1）.把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。（2）.如果基本可行解不存在，即約束條件有矛盾，則這個(gè)問題無解。（3）.如果基本可行解存在，從初始基本可行解作為出發(fā)點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基本變量取代某一基本變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。(4).按照步驟 3 進(jìn)行迭代,直到找到對應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善） ，即解得問題的最優(yōu)解。(5).如果迭

36、代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界，則終止迭代。計(jì)算步驟流程圖可以簡單表述如下（如圖 3-1）第 15 頁 共 21 頁圖 3-1 算法流程圖3.3.2最優(yōu)解可能出現(xiàn)下列的情況：運(yùn)用單純形法可以很好的解決好最優(yōu)化問題，在解決問題求得結(jié)果后，它的解可能出現(xiàn)的情況一般有這幾種情況：（1）存在著一個(gè)最優(yōu)解；（2）無窮多個(gè)最優(yōu)解存在著；（3）不存在最優(yōu)解，這只在三種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不限制目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大） 。第 16 頁 共 21 頁第四章軟件仿真實(shí)驗(yàn)4.1 軟件簡介mldemos 是一個(gè)開源的可視化工具 ，用機(jī)器算法來幫助人們學(xué)習(xí)和了解幾種算法的功能，軟

37、件可以解決在 分類，回歸，聚類等方面的問題，mldemos 是開源和免費(fèi)的，用于個(gè)人和學(xué)術(shù)用途。軟件圖形如下（圖 4-1）圖 4-1 mldemos 軟件圖標(biāo)本次實(shí)驗(yàn)仿真圖就是根據(jù)這個(gè)軟件對單純行法的方法進(jìn)行更真實(shí)的軟件仿真，讓大家能更生動(dòng)的看到單純形法求最優(yōu)化的圖形過程。4.2 實(shí)驗(yàn)仿真（1）首先，打開軟件就就會(huì)進(jìn)入如下開始界面（如圖 4-2）：第 17 頁 共 21 頁圖 4-2 開始界面（2）下面開始畫圖，具體做法：用鼠標(biāo)左鍵單擊會(huì)形成深淺不同的層次，表示目標(biāo)函數(shù)的等高圖，然后畫成如下所示圖形（如圖 4-3）圖 4-3 軟件畫圖（3）畫好圖形以后打開本次所要仿真的選項(xiàng)：在最優(yōu)化選項(xiàng)里的單

38、純形法選項(xiàng)，打開仿真選項(xiàng)然后，再進(jìn)行仿真（如圖 44）和仿真軟件選項(xiàng)放大圖（如圖 4-5）第 18 頁 共 21 頁圖 4-4 打開仿真選項(xiàng)圖 4-5 仿真軟件選項(xiàng)放大圖（4）在打開仿真選項(xiàng)后，用鼠標(biāo)選好初始點(diǎn)，然后就確定仿真，軟件會(huì)自動(dòng)生成仿真的結(jié)果。 （如圖 4-6）第 19 頁 共 21 頁 圖 4-6 仿真結(jié)果圖形分析：我們通過圖形可以看到圖形從開始選定的初始點(diǎn)，由單純形法依次迭代慢慢的沿著等高線逐漸爬升知道找到最優(yōu)點(diǎn)為止。仿真實(shí)驗(yàn)總結(jié)：理論是實(shí)踐的基礎(chǔ)，但是只有實(shí)踐才能更好的對理論進(jìn)行深入的表達(dá)。所以我們這次仿真實(shí)驗(yàn)就是對理論單純形法方法下的最優(yōu)化的最好的展現(xiàn)。第五章結(jié)論通過近三個(gè)多月的努力工作，基于單純行法的最優(yōu)化問題的畢業(yè)設(shè)計(jì)論文終于在我的不懈努力下圓滿的完成了。在這次畢業(yè)設(shè)計(jì)論文的寫作過程中，遇到了很多的問題，也有很多的困惑，但是，都在老師和同學(xué)的悉心幫助下，以及我本人的努力下一一順利解決了，并且在學(xué)習(xí)過程，我收獲到了很多，也有了一些親身的感悟：首先，論文寫作的過程我認(rèn)為是一個(gè)不斷進(jìn)步不斷學(xué)習(xí)的過程，從剛一開始，論文寫作時(shí)對最優(yōu)化問題的認(rèn)識(shí)不是很清楚到漸漸的了解，以及到最后對第 20 頁 共 21 頁該問題