matlab在運(yùn)籌學(xué)中的應(yīng)用.ppt

MATLAB 在運(yùn)籌學(xué)中的應(yīng)用,緒 論,優(yōu)化求解工作中常用的軟件： 1、Matlab 2、Mathematica 3、Maple 4、SAS 5、SPSS 6、Lindo/Lingo 7、GAMS 8、WinQSB 9、Excel 10、其他，如SQP、DPS、ORS、Visual Decision、Decision Explore、AIMMS、Crystal Ball、TreeAge等。,Matlab （Matrix Laboratory ） 專業(yè)級的數(shù)值計算和符號計算、 強(qiáng)大的繪圖功能、 可視化建模仿真和實時控制,從事理論研究的數(shù)學(xué)工作者和其他科學(xué)工作者 強(qiáng)大的符號計算能力 輸入格式有嚴(yán)格的規(guī)定,SAS（Statistical Analysis System) 譽(yù)為統(tǒng)計分析的標(biāo)準(zhǔn)軟件，統(tǒng)計方法齊、全、新 集數(shù)據(jù)存取、管理、分析和展現(xiàn)于一體 政府行政管理、科研、教育、生產(chǎn)和金融等領(lǐng)域,SPSS（Statistical Package for the Social Sciences) 2000 （Statistical Product and Service Solutions) 最早的統(tǒng)計分析軟件 類似Execl表格的方式輸入和管理數(shù)據(jù) 應(yīng)用最廣泛的專業(yè)統(tǒng)計軟件,Lindo/Lingo 求解最優(yōu)化問題的軟件包 線性規(guī)劃、二次規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃 解算器尋最佳模型進(jìn)行求解，公式表示 Lingo優(yōu)化問題的建模語言，可與文本、Excel、數(shù)據(jù)庫對接,GAMS（General Algebraic Modeling System） 針對大型、復(fù)雜系統(tǒng)的建模 建模迅速、易修改，豐富的模型求解引擎,WinQSB（Quantitative Systems for Business） 基于模塊化設(shè)計的專業(yè)運(yùn)籌規(guī)劃和決策輔助軟件 規(guī)劃問題、計劃編制、抽樣分析、MRP、質(zhì)量控制、馬爾可夫過程、決策分析等,通過加載宏功能 擴(kuò)展為一個優(yōu)化求解的工具,Matlab簡介,概述 Matlab是矩陣實驗室（Matrix Laboratory）的簡稱，是美國MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，和Mathematica、Maple并稱為三大數(shù)學(xué)軟件。 用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算的高級技術(shù)計算語言和交互式環(huán)境，主要包括Matlab和Simulink兩大部分。 主要應(yīng)用于工程計算、控制設(shè)計、信號處理與通訊、圖像處理、信號檢測、金融建模設(shè)計與分析等領(lǐng)域。 具有廣泛應(yīng)用前景的全新的計算機(jī)高級編程語言 產(chǎn)生與發(fā)展 70年代后期，基于特征計算的程序庫EISPACK和線性代數(shù)程序庫LINPACK （FORTRAN語言） 1984年，MathWorks公司正式推出的商業(yè)化版本，C語言； 1992年，基于Windows平臺的Matlab4.0，6.5 2004年，7.x 2006a，2006b，2011a，2011b。,優(yōu)勢 強(qiáng)大易用的科學(xué)計算語言 全面的圖形功能 獨(dú)立開放的平臺 實用的程序接口 Simulink動態(tài)仿真功能 Matlab是一個交互式開發(fā)系統(tǒng)，其基本數(shù)據(jù)單元是矩陣。 MathWorks公司的描述：計算、可視化及編程一體 常用網(wǎng)址： ,MATLAB 產(chǎn)品族可以用來進(jìn)行以下各種工作： 數(shù)值分析 數(shù)值和符號計算 工程與科學(xué)繪圖 控制系統(tǒng)的設(shè)計與仿真 數(shù)字圖像處理 技術(shù) 數(shù)字信號處理 技術(shù) 通訊系統(tǒng)設(shè)計與仿真 財務(wù)與金融工程 MATLAB 的應(yīng)用范圍非常廣，包括信號和圖像處理、通訊、控制系統(tǒng)設(shè)計、測試和測量、財務(wù)建模和分析以及計算生物學(xué)等眾多應(yīng)用領(lǐng)域。附加的工具箱（單獨(dú)提供的專用MATLAB 函數(shù)集）擴(kuò)展了MATLAB 環(huán)境，以解決這些應(yīng)用領(lǐng)域內(nèi)特定類型的問題。,Matlab Main Toolboxmatlab主工具箱 Control System Toolbox控制系統(tǒng)工具箱 Communication Toolbox通訊工具箱 Financial Toolbox財政金融工具箱 System Identification Toolbox系統(tǒng)辨識工具箱 Fuzzy Logic Toolbox模糊邏輯工具箱 Higher-Order Spectral Analysis Toolbox高階譜分析工具箱 Image Processing Toolbox圖象處理工具箱 computer vision system toolbox-計算機(jī)視覺工具箱 LMI Control Toolbox線性矩陣不等式工具箱 Model predictive Control Toolbox模型預(yù)測控制工具箱 -Analysis and Synthesis Toolbox分析工具箱 Neural Network Toolbox神經(jīng)網(wǎng)絡(luò)工具箱 Optimization Toolbox優(yōu)化工具箱 Partial Differential Toolbox偏微分方程工具箱 Robust Control Toolbox魯棒控制工具箱 Signal Processing Toolbox信號處理工具箱 Spline Toolbox樣條工具箱 Statistics Toolbox統(tǒng)計工具箱 Symbolic Math Toolbox符號數(shù)學(xué)工具箱 Simulink Toolbox動態(tài)仿真工具箱 Wavele Toolbox小波工具箱 DSP system toolbox-DSP處理工具箱,Matlab界面窗口,MATLAB界面窗口,MATLAB中變量區(qū)別于其他編程語言的特點(diǎn) MATLAB表達(dá)式中可以使用矩陣形式； MATLAB中不需要預(yù)先聲明變量的類型和維數(shù)，MATLAB會根據(jù)對新變量的操作創(chuàng)建該變量，確定其類型并為其分配存儲空間； 對已經(jīng)存在的變量的賦值操作，MATLAB會以新值代替舊值。如果需要的話，MATLAB可以改變該變量的類型或者為其分配新的存儲空間; MATLAB中的變量名是大小寫敏感的，即A和a代表不同的變量；,矩陣特征值參數(shù)運(yùn)算,一、矩陣的行列式 函數(shù)：det(A) 二、矩陣的跡 函數(shù)：trace(A) 三、矩陣的秩 函數(shù)：rank(A) 四、矩陣的范數(shù) 函數(shù)：norm（A，選項） 五、矩陣的特征值 函數(shù)：eig(A) 六、矩陣的分解-三角形分解（LU或LR分解）函數(shù)：L, U=lu(A) 七、矩陣的分解-正交分解（QR分解） 函數(shù)：Q, R=qr(A),MATLAB中的控制結(jié)構(gòu),循環(huán)結(jié)構(gòu) for循環(huán) while循環(huán) 選擇結(jié)構(gòu) if結(jié)構(gòu) switch結(jié)構(gòu) try/catch結(jié)構(gòu) 其他流程控制 break語句 continue語句 return語句,try 語句組1 catch 語句組2 end,【例】解Lorenz方程-大氣對流模型,function xdot=lorenzeq(t,x) xdot=-8/3*x(1)+x(2)*x(3); -10*x(2)+10*x(3); -x(1)*x(2)+28*x(2)-x(3);,線性規(guī)劃問題的數(shù)學(xué)模型,線性規(guī)劃問題的數(shù)學(xué)描述 或 其中 C 為n維行向量 A 為mn維矩陣 b 為m維列向量 X 為n維列向量,線性規(guī)劃問題的MATLAB求解,MATLAB中求解 線性規(guī)劃問題的 標(biāo)準(zhǔn)形式 MATLAB標(biāo)準(zhǔn)型和教科書中講解有所不同， 極小化的目標(biāo)函數(shù)z 線性規(guī)劃問題具有不等式約束m1個，等式約束m2個 f、x、lb 和ub 均為n維列向量，b為m1維列向量，beq為m2維列向量，A為m1n維矩陣，Aeq為m2n維矩陣,注意事項 MATLAB標(biāo)準(zhǔn)型是對目標(biāo)函數(shù)求極小，如果遇到是對目標(biāo)函數(shù)求極大的問題，在使用MATLAB求解時，需要在函數(shù)前面加一個負(fù)號轉(zhuǎn)化為對目標(biāo)函數(shù)求極小的問題； MATLAB標(biāo)準(zhǔn)型中的不等式約束形式為“”，如果在線性規(guī)劃問題中出現(xiàn)“”形式的不等式約束，則我們需要在兩邊乘以(-1)使其轉(zhuǎn)化為MATLAB中的“”形式。如果在線性規(guī)劃問題中出現(xiàn)了“”的約束形式，則我們需要通過添加松弛變量使得不等式約束變?yōu)榈仁郊s束,將問題轉(zhuǎn)化為MATLAB標(biāo)準(zhǔn)型 原問題是對目標(biāo)函數(shù)求極大，故添加負(fù)號使目標(biāo)變?yōu)椋簃in z=-4x1+2x2-x3 原問題中存在“”的約束條件，故添加負(fù)號使其變?yōu)?: 8x1-2x2+2x3 -8 將約束整理為矩陣形式 用MATLAB表達(dá)則為,f=-4; 2; -1; %將目標(biāo)函數(shù)轉(zhuǎn)化為求極小 A=2 -1 1; 8 -2 2; b=12; -8; %不等式約束系數(shù)矩陣 Aeq=-2 0 1; 1 1 0;beq=3; 7; %等式約束系數(shù)矩陣 lb=0; 0; 0;ub=Inf; Inf; Inf %邊界約束,函數(shù)調(diào)用格式 MATLAB優(yōu)化工具箱中求解線性規(guī)劃問題的函數(shù)為 linprog() x = linprog(f, A, b) x = linprog(f, A, b, Aeq, beq) x = linprog(f, A, b, Aeq, beq, lb, ub) x = linprog(f, A, b, Aeq, beq, lb, ub, x0) x = linprog(f, A, b, Aeq, beq, lb, ub, x0, options) x = linprog(problem) x, fval = linprog(.) x, fval, exitflag = linprog(.) x, fval, exitflag, output = linprog(.) x, fval, exitflag, output, lambda = linprog(.),輸入?yún)?shù) MATLAB工具箱中的linprog函數(shù)在求解線性規(guī)劃問題時，提供的參數(shù)為：模型參數(shù)、初始解參數(shù)和算法控制參數(shù)。 模型參數(shù)x、c、lb、ub、b、beq、A和Aeq在MATLAB標(biāo)準(zhǔn)型中已經(jīng)介紹了其具體物理意義和獲得方法 x0為線性規(guī)劃問題的初始解，該設(shè)置僅在中型規(guī)模算法中有效，而在默認(rèn)的大型規(guī)模算法和單純形算法中，MATLAB將忽略一切初始解。 options為包含算法控制參數(shù)的結(jié)構(gòu)變量，我們可以通過optimset命令對這些具體的控制參數(shù)進(jìn)行設(shè)置，例如下述格式 options = optimset(param1,value1,param2,value2,.) 該命令格式創(chuàng)建一組控制參數(shù)結(jié)構(gòu)變量options，將參數(shù)的具體值賦給單引號之間的參數(shù)，任何未被指定的參數(shù)將被賦值為，參數(shù)值為的具體的含義是將該組控制參數(shù)傳遞給優(yōu)化函數(shù)時將使用MATLAB提供的默認(rèn)值 在線性規(guī)劃問題中可以用到的設(shè)置參數(shù)如下一頁的表所示,輸出參數(shù) linprog函數(shù)返回的輸出參數(shù)有x、fval、exitflag、lambda和output。 輸出參數(shù)x為線性規(guī)劃問題的最優(yōu)解 輸出參數(shù)fval為線性規(guī)劃問題在最優(yōu)解x處的函數(shù)值 輸出參數(shù)exitflag返回的是優(yōu)化函數(shù)計算終止時的狀態(tài)指示，說明算法終止的原因，其取值和其代表的具體原因如表所示,輸出參數(shù) 輸出參數(shù)output是一個返回優(yōu)化過程中相關(guān)信息的結(jié)構(gòu)變量，其屬性如表所示 輸出參數(shù)lambda是返回線性規(guī)劃問題最優(yōu)解x處的拉格朗日乘子的一個結(jié)構(gòu)變量,其總維數(shù)等于約束條件的個數(shù)，其非零分量對應(yīng)于起作用的約束條件，其屬性如表所示。,函數(shù)命令詳解 x = linprog(f, A, b) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 x = linprog(f, A, b, Aeq, beq) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 即該函數(shù)調(diào)用格式解決的是既含有線性等式約束，又含有線性不等式約束的線性規(guī)劃問題，如果在線性規(guī)劃問題中無線性不等式約束，則可以設(shè)A=以及b=,函數(shù)命令詳解 x = linprog(f, A, b, Aeq, beq, lb, ub) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 即在線性規(guī)劃問題的求解過程中進(jìn)一步考慮了對決策變量的約束，其中l(wèi)b和ub均是和決策變量維數(shù)相同的列向量，如果對決策變量沒有上界約束，可以設(shè)置ub(i) = Inf，如果沒有下界約束則可以設(shè)置lb(i) = -Inf，和(2)類似，如果問題中沒有等式約束，則可以設(shè)Aeq=以及beq=,命令詳解 x = linprog(c,A,b,Aeq,beq,lb,ub,x0) 在前面調(diào)用方法的基礎(chǔ)上設(shè)置線性規(guī)劃問題求解的初始解為x0，該參數(shù)僅在使用有效集算法時生效，否則當(dāng)使用默認(rèn)的內(nèi)點(diǎn)算法時，將忽略任何初始點(diǎn)，即參數(shù)無效。 x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) 用options指定的優(yōu)化參數(shù)進(jìn)行最小化?？梢允褂胦ptimset來設(shè)置這些參數(shù) x,fval = linprog(.) 在優(yōu)化計算結(jié)束之時返回線性規(guī)劃問題在解x處的目標(biāo)函數(shù)值fval。 x,fval,exitflag = linprog(.) 在優(yōu)化計算結(jié)束之時返回exitflag值，描述函數(shù)計算的退出條件。 x,fval,exitflag,output = linprog(.) 在優(yōu)化計算結(jié)束之時返回返回結(jié)構(gòu)變量output x,fval,exitflag,output,lambda = linprog(.) 在優(yōu)化計算結(jié)束之時返回線性規(guī)劃問題最優(yōu)解x處的拉格朗日乘子lambda,例題1,用MATLAB求解線性規(guī)劃問題,f=-1; -1; %目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) A=1 -2; 1 2; %線性不等式約束 b=4; 8; lb=0; 0; %邊界約束，由于無上界，故設(shè)置ub=Inf;Inf; ub=Inf; Inf; x, fval=linprog(f, A, b, , , lb, ub) Optimization terminated. x = 6.0000 1.0000 fval = -7.0000,例題2,用MATLAB求解線性規(guī)劃問題,f=-1; -3; 1; %目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) Aeq=1 1 2; -1 2 1; %線性等式約束 beq=4; 4; lb=0; 0; 0; %設(shè)計變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf;Inf ub=Inf; Inf; Inf; x, fval, exitflag=linprog(f, , , Aeq, beq, lb, ub) Optimization terminated. x = 1.3333 2.6667 0.0000 fval = -9.3333 exitflag = 1,例題3,用MATLAB求解線性規(guī)劃問題,f=-3; 1; 1; A=1 -2 1; 4 -1 -2; %線性不等式約束 b=11; -3; Aeq=-2 0 1; %線性等式約束 beq=1; lb=0; 0; 0; %變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf;Inf ub=Inf; Inf; Inf; x, fval, exitflag, output, lambda=linprog(f, A, b, Aeq, beq, lb, ub) Optimization terminated. x = 4.0000 1.0000 9.0000 fval = -2.0000output = exitflag = 1,output = iterations: 6 algorithm: large-scale: interior point cgiterations: 0 message: Optimization terminated. lambda = ineqlin: 2x1 double eqlin: -0.6667 upper: 3x1 double lower: 3x1 double,0-1規(guī)劃問題,MATLAB中求解 0-1規(guī)劃問題的 標(biāo)準(zhǔn)形式 bintprog的調(diào)用格式 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, exitflag = bintprog(.) x, fval, exitflag, output = bintprog(.),線性二次規(guī)劃問題,MATLAB中求解 線性二次規(guī)劃問 題的標(biāo)準(zhǔn)形式 函數(shù)調(diào)用格式： x = quadprog(H, f, A, b) x = quadprog(H, f, A, b, Aeq, beq) x = quadprog(H, f, A, b, Aeq, beq, lb, ub) x = quadprog(H, f, A, b, Aeq, beq, lb, ub, x0) x = quadprog(H, f, A, b, Aeq, beq, lb, ub, x0, options) x, fval = quadprog(.) x, fval, exitflag = quadprog(.) x, fval, exitflag, output = quadprog(.) x, fval, exitflag, output, lambda = quadprog(.),線性目標(biāo)規(guī)劃問題,線性目標(biāo)規(guī)劃的MATLAB求解,輸入輸出參數(shù),輸入?yún)?shù)中，fun為目標(biāo)函數(shù)，x0是求解的初始值，goal是目標(biāo)函數(shù)的期 望值，nonlcon是非線性約束函數(shù)，weight是目標(biāo)權(quán)重。 fun：最小化的目標(biāo)函數(shù)，fun可以是一個在M函數(shù)中定義的函數(shù)句柄； Weight：可以控制低于或超過fgoalattain函數(shù)指定目標(biāo)的相對程度。需要注意的是，如果將weight向量中的任一元素設(shè)置為0時，則算法將把對應(yīng)的目標(biāo)約束當(dāng)做是硬約束來處理；當(dāng)設(shè)置weight為不同的數(shù)值時，fgoalattain將對目標(biāo)函數(shù)采取不同的處理方式： (1) 當(dāng)權(quán)重weight設(shè)置為正時，fgoalattain函數(shù)則試圖使目標(biāo)函數(shù)值小于期望值； (2) 當(dāng)權(quán)重weight設(shè)置為負(fù)時；fgoalattain函數(shù)則試圖使目標(biāo)函數(shù)值大于期望值； (3) 當(dāng)需要目標(biāo)函數(shù)值盡可能等于期望值時，則應(yīng)設(shè)置控制參數(shù)GoalsExactAc