最優(yōu)化實(shí)驗(yàn)報(bào)告-展示頁
2024-08-16 19:26本頁面
【正文】 解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。（3）、單純形法的算法流程如下：①把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基本可行解作為初始基本可行解。③停止法則──在當(dāng)前角點(diǎn)可行解比所有相鄰角點(diǎn)可行解都更好些時(shí)停止。 算法流程圖 （1）、確定初始基可行解①?gòu)木€性規(guī)劃標(biāo)準(zhǔn)形的系數(shù)矩陣中能直接找出m個(gè)線性獨(dú)立的單位向量；②對(duì)約束條件全為“=”連接的LP，化為標(biāo)準(zhǔn)形，左端添加松弛變量后即形成一個(gè)單位子矩陣；③約束條件中含有“=”或“=”連接的方程，在插入剩余變量后找不到單位矩陣，則必須采用“人造基”法，（2）、單純形法的運(yùn)算步驟可歸結(jié)為：①起始步驟──在一個(gè)角點(diǎn)可行解上開始。最后一個(gè)性質(zhì)的重要性在于它為一個(gè)角點(diǎn)可行解是否是最優(yōu)解提供了一種簡(jiǎn)便的檢驗(yàn)標(biāo)準(zhǔn)，因而毋需列舉所有的可行解。②只存在有限個(gè)數(shù)的角點(diǎn)可行解。角點(diǎn)可行解具有下列三個(gè)重要性質(zhì)：①如果存在著一個(gè)最優(yōu)解，那么它必定是角點(diǎn)可行解。一個(gè)可行解，如果不處在由另兩個(gè)可行解連接起來的任何線段上，它就是一個(gè)角點(diǎn)可行解。因此，可行區(qū)域的邊界是由那些滿足一個(gè)或同時(shí)滿足幾個(gè)邊界方程（即處在作為邊界的一個(gè)或幾個(gè)超平面上）的可行解所組成，而且最優(yōu)解必在其中。任何一項(xiàng)約束條件的邊界方程是用“＝”號(hào)來替換該約束條件中的“≤”或“≥”號(hào)而得到的。求解時(shí)可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大）。用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)主要取決于約束條件的個(gè)數(shù)。這樣，一個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。概述：根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，…xn的值稱為一個(gè)解,滿足所有的約束條件的解稱為可行解。如果問題無最優(yōu)解也可用此法判別。單純形法的基本思想是：先找出一個(gè)基本可行解，對(duì)它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。有了MATLAB這個(gè)強(qiáng)大的計(jì)算平臺(tái)，既可以利用MATLAB優(yōu)化工具箱（OptimizationToolbox）中的函數(shù)，又可以通過算法變成實(shí)現(xiàn)相應(yīng)的最優(yōu)化計(jì)算。伴隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，最優(yōu)化理論與方法的迅速進(jìn)步為解決實(shí)際最優(yōu)化問題的軟件也在飛速發(fā)展。收集和統(tǒng)計(jì)上述擬定之模型所需要的各種基礎(chǔ)數(shù)據(jù)，并最終將數(shù)據(jù)整理形成分析和解決問題的具體模型。最優(yōu)化方法課程設(shè)計(jì)報(bào)告 班級(jí)：________________ 姓名： ______ 學(xué)號(hào)： __________ 成績(jī)： 2017年 5月 21 日 目 錄一、摘 要 1二、單純形算法 2 單純形算法的基本思路 2 算法流程圖 3 用matlab編寫源程序 3二、 黃金分割法 7 黃金分割法的基本思路 7 算法流程圖 8 用matlab編寫源程序 9 黃金分割法應(yīng)用舉例 10三、 最速下降法 10 最速下降法的基本思路 10 算法流程圖 12 用matlab編寫源程序 12 最速下降法應(yīng)用舉例 13四、 懲罰函數(shù)法 16 懲罰函數(shù)法的基本思路 16 算法流程圖 17 用matlab編寫源程序 17 懲罰函數(shù)法應(yīng)用舉例 19五、 自我總結(jié) 19六、參考文獻(xiàn) 19一、摘 要運(yùn)籌學(xué)是一門以人機(jī)系統(tǒng)的組織、管理為對(duì)象，應(yīng)用數(shù)學(xué)和計(jì)算機(jī)等工具來研究各類有限資源的合理規(guī)劃使用并提供優(yōu)化決策方案的科學(xué)。通過對(duì)數(shù)據(jù)的調(diào)查、收集和統(tǒng)計(jì)分析，以及具體模型的建立。最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決策等各個(gè)領(lǐng)域，而最優(yōu)化模型與方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、通信、政府機(jī)關(guān)等各個(gè)部門及各個(gè)領(lǐng)域。其中，MATLAB軟件已經(jīng)成為最優(yōu)化領(lǐng)域應(yīng)用最廣的軟件之一。關(guān)鍵詞：優(yōu)化、線性規(guī)劃、黃金分割法、最速下降法、懲罰函數(shù)法 二、單純形算法 單純形算法的基本思路 線性規(guī)劃問題的可行域是頂點(diǎn)所對(duì)應(yīng)的可行解稱為基本可行解。因基本可行解的個(gè)數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。單純形法是從某一基可行解出發(fā)，連續(xù)地尋找相鄰的基可行解，直到達(dá)到最優(yōu)的迭代過程，其實(shí)質(zhì)是解線性方程組。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為最優(yōu)解。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解?，F(xiàn)在一般的線性規(guī)劃問題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對(duì)于具有106個(gè)決策變量和104個(gè)約束條件的線性規(guī)劃問題已能在計(jì)算機(jī)上解得。要縮小對(duì)最優(yōu)解的搜索范圍，就必須認(rèn)識(shí)最優(yōu)解的一般性質(zhì)，最優(yōu)解如果存在的話，則它必然處于可行區(qū)域的邊界上。每一個(gè)邊界方程確定一個(gè)超平面。最優(yōu)解不僅是在可行區(qū)域的邊界上，而且也在這個(gè)區(qū)域的一個(gè)隅角上。如果連接兩個(gè)角點(diǎn)可行解的線段處在可行區(qū)域的邊界上，這兩個(gè)角點(diǎn)可行解就稱為相鄰的角點(diǎn)可行解。如果存在有多個(gè)最優(yōu)解，那么至少有兩個(gè)最優(yōu)解必定是相鄰的角點(diǎn)可行解。③如果一個(gè)角點(diǎn)可行解按目標(biāo)函數(shù)值來衡量時(shí)比其所有的相鄰角點(diǎn)可行解更好一些，那它就比所有其他角點(diǎn)可行解都更好，也就是最優(yōu)解。上述這些性質(zhì)構(gòu)成單純形法的原理基礎(chǔ)。單純形法正是利用了這個(gè)性質(zhì)，只要檢查少數(shù)的角點(diǎn)可行解，并且一旦這個(gè)最優(yōu)性檢驗(yàn)獲得通過就可立即停止運(yùn)算。②迭代步驟──移動(dòng)至一個(gè)更好一些的相鄰角點(diǎn)可行解（根據(jù)需要反復(fù)進(jìn)行這一步驟）。當(dāng)前角點(diǎn)可行解就是一個(gè)最優(yōu)解。單純形法的優(yōu)點(diǎn)及其成功之處在于它只需要較少的有限次數(shù)的迭代，即可找到最優(yōu)解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。④按步驟3進(jìn)行迭代,直到對(duì)應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時(shí)目標(biāo)函數(shù)值不能再改善），即得到問題的最優(yōu)解。化標(biāo)準(zhǔn)形式、松弛變量求初始基本可行解選擇非基本變量Y輸出，終止程序轉(zhuǎn)軸對(duì)換選擇基本變量無解，終止程序NNY 用matlab編寫源程序 Matlab程序源代碼： function simplexTab(mat,numFreeVar)maxRow=length(mat(:,1))。objEntryExcludingMaxPayOff=mat(maxRow,1:maxCol2)。while(objEnt0) lastColExcludingObjEnty=mat(1:(maxRow1),maxCol)。 a=lastColExcludingObjEnty./ithColExcludingObjEnty。 sprintf(39。,bestRowToPivot,bestColToPivot) disp(39。)。0]] disp(39。)。 if(val0) [s indices]=sort(a)。 while(s(count)0) count=count+1。 end end if(length(a)==0) length(a) return end mat=pivot(mat,bestRowToPivot,bestColToPivot)。 [objEnt bestColToPivot]=min(objEntryExcludingMaxPayOff)。the best Picot is %d 行 and %d 列39。單純形表化為：39。[mat,[a。運(yùn)行結(jié)束!39。 interChange .m子函數(shù)function newMat=interChange
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1