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