整數(shù)規(guī)劃與多目標(biāo)規(guī)劃模型

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！1整數(shù)規(guī)劃的MATLAB求解方法（一）用MATLAB求解一般混合整數(shù)規(guī)劃問題由于MATLAB優(yōu)化工具箱中并未提供求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃的函數(shù)，因而需要自行根據(jù)需要和設(shè)定相關(guān)的算法來實現(xiàn)?，F(xiàn)在有許多用戶發(fā)布的工具箱可以解決該類問題。這里我們給出開羅大學(xué)的Sherif和Tawfik在MATLABCentral上發(fā)布的一個用于求解一般混合整數(shù)規(guī)劃的程序，在此命名為，在原程序的基礎(chǔ)上做了簡單的修改，將其選擇分枝變量的算法由自然序改造成分枝變量選擇原則中的一種，即：選擇與整數(shù)值相差最大的非整數(shù)變量首先進(jìn)行分枝。intprog函數(shù)的調(diào)用格式如下：[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)該函數(shù)解決的整數(shù)規(guī)劃問題為：fcxminTt.AxbAxbeqeqlbxubx0i,n)x取整數(shù)（j）ij在上述標(biāo)準(zhǔn)問題中，假設(shè)為維設(shè)計變量，且問題具有不等式約束m個，xn1等式約束m個，那么：、均為維列向量，b為m維列向量，b為m維列cxn21eq2向量，A為mn維矩陣，A為mn維矩陣。1eq2在該函數(shù)中，輸入?yún)?shù)有c,A,b,A,beq,lb,ub,M和。其中c為目標(biāo)函數(shù)所對應(yīng)設(shè)計變量的系數(shù)，A為不等式約束條件方程組構(gòu)成的系數(shù)矩陣，b為不等式約束條件方程組右邊的值構(gòu)成的向量。Aeq為等式約束方程組構(gòu)成的系數(shù)矩陣，beq為等式約束條件方程組右邊的值構(gòu)成的向量。lb和ub為設(shè)計變量對應(yīng)的上界和下界。M為具有整數(shù)約束條件限制的設(shè)計變量的序號，例如問題中設(shè)計變量為x,x,,x，要求x,x和x為整數(shù)，則；若要求全126236為整數(shù)，則，或者M(jìn)=[1;2;3;4;5;6]。TolXInteger為判定整數(shù)的誤差限，即若某數(shù)x和最鄰近整數(shù)相差小于該誤差限，則認(rèn)為x即為該整數(shù)。在該函數(shù)中，輸出參數(shù)有x,fval和exitflag。其中x為整數(shù)規(guī)劃問題的最優(yōu)解向量，fval為整數(shù)規(guī)劃問題的目標(biāo)函數(shù)在最優(yōu)解向量x處的函數(shù)值，exitflag為函數(shù)計算終止時的狀態(tài)指示變量。例1求解整數(shù)規(guī)劃問題：fxx12t.4x2x1124x2x122x12,xx12算法：c=[-1;-1];A=[-42;42;0-2];b=[-1;11;-1];lb=[0;0];M=[1;2];%均要求為整數(shù)變量Tol=1e-8;%判斷是否整數(shù)的誤差限[x,fval]=linprog(c,A,b,[],[],lb,[])[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol)%求最優(yōu)解整數(shù)解結(jié)果：%求解原問題松弛線性規(guī)劃x=%松弛線性規(guī)劃問題的最優(yōu)解1.50002.5000fval=-4.0000x1=%整數(shù)規(guī)劃的最優(yōu)解21fval2=-3.0000（二）用MATLAB求解0-1規(guī)劃問題在MATLAB優(yōu)化工具箱中，提供了專門用于求解0-1規(guī)劃問題的函數(shù)，其算法基礎(chǔ)即為分枝界定法，在MATLAB中調(diào)用bintprog函數(shù)求解0-1規(guī)劃時，需要遵循MATLAB中對0-1規(guī)劃標(biāo)準(zhǔn)性的要求。0-1規(guī)劃問題的MATLAB標(biāo)準(zhǔn)型minfcxTbt.AxAxbeqxeq在上述模型中，目標(biāo)函數(shù)f需要極小化，以及需要滿足的約束條件，不等式約束一定要化為形式為“”。假設(shè)為mmxn12、均為維列向量，b為m維列向量，b為m維列向量，A為mn維矩陣，cxn1eq21A為mn維矩陣。eq2使用相關(guān)函數(shù)，標(biāo)準(zhǔn)化的方法和線性規(guī)劃中的類似。0-1規(guī)劃問題的MATLAB求解函數(shù)MATLAB優(yōu)化工具箱中求解0-1規(guī)劃問題的命令為bintprogbintprog的調(diào)用格式x=x=x=x=x====命令詳解1）x=bintprog(f)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題fcTxt.x2）x=bintprog(c,A,b)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題fcTxbt.x03）x=bintprog(c,A,b,Aeq,beq)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題：minfcxTbt.AxAxbeqx0eq4）x=bintprog(c,A,b,Aeq,beq,x0)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題minfcxTbt.AxAxbeqx0eq在前一個調(diào)用格式的基礎(chǔ)上同時設(shè)置求解算法的初始解為，如果初始解x0不在0-1規(guī)劃問題的可行域中，算法將采用默認(rèn)的初始解5）x=bintprog(c,A,b,Aeq,beq,x0,options)用options指定的優(yōu)化參數(shù)進(jìn)行最小化。可以使用optimset來設(shè)置這些參數(shù)上面的函數(shù)調(diào)用格式僅設(shè)置了最優(yōu)解這一輸出參數(shù)，如果需要更多的輸出參數(shù)，則可以參照下面的調(diào)用格式：[x,fval]=bintprog(...)在優(yōu)化計算結(jié)束之時返回整數(shù)規(guī)劃問題在解x處的目標(biāo)函數(shù)值fval[x,fval,exitflag]=bintprog(...)在優(yōu)化計算結(jié)束之時返回exitflag值，描述函數(shù)計算的退出條件。[x,fval,exitflag,output]=bintprog(...)在優(yōu)化計算結(jié)束之時返回結(jié)構(gòu)變量output例2：求解0-1規(guī)劃問題Exnnmaxfijiji1j120123326nt.x1i2,,n221529Eij21133124221632j1nx1j,,n12iji1x4）i2;j2,nijx~x表示x~x，141114用x~x表示x~x，用x~x表示x~x，用x~x表示x~x，于582124912313413164144是約束條件和目標(biāo)函數(shù)分別為：1xxxx1234xxxx15678xxxx19101112xxxx113141516xxx1x15913xxxx1261014xxxx1371115xxxx1481216(ixifExExExExExExEx111122133144215226441611100000000000000011110000000000000001111000000000000000111100010001000100010001000100010001000100010001000100010001000xE相=0010100001000001=整數(shù)規(guī)劃的應(yīng)用——組件配套問題某機(jī)械產(chǎn)品需要由三個工廠開工一起生產(chǎn)后組裝完成。每件機(jī)械需要4個組件1和3個組件A和原材料的供應(yīng)量分別為400kg和600kg。由于三個工廠的生產(chǎn)條件和擁有設(shè)備工藝條件不同，每個工廠生產(chǎn)組件的能力和原材料的消耗也不盡相同，且每個工廠開工一次都是配套生產(chǎn)一定數(shù)量的組件1和組件，其具體的數(shù)據(jù)如表所示。表1296478796959現(xiàn)在的最優(yōu)化問題是，這三個工廠應(yīng)當(dāng)如何安排生產(chǎn)，才能使該產(chǎn)品的配套數(shù)達(dá)到最大？（Ⅰ）組件配套問題的建模設(shè)x、x和x123于每個工廠開工一次都是配套生產(chǎn)，故每次開工消耗的原材料一定，且生產(chǎn)的組件數(shù)也是一定的。在這個假設(shè)的前提之下，我們可以得出該問題的目標(biāo)函數(shù)和約束條件。A材料9x，工廠２將消耗A材料6x，工廠３將消耗A材料4x，故有約束條件：1239x6x4x400123同理，對于材料B的總量約束條件可以表達(dá)為：7x10x9x600123然后再來分析三個工廠零件生產(chǎn)的情況，三個工廠生產(chǎn)的組件1的數(shù)量分別為8x7x和9x，故組件1的總數(shù)為：Q8x7x9x12311236x9x5x同理，組件2的總數(shù)為：Q2123下一步是分析目標(biāo)函數(shù)，該問題要求的不是生產(chǎn)的各種組件總數(shù)最多，而是要求產(chǎn)品的配套數(shù)量最大，即能組成的機(jī)械數(shù)目最多。問題中已經(jīng)給出了該種機(jī)械中兩種組件的配比為4:3，故組件1所能成套的數(shù)目T滿足約束條件：1Q8x7x9xT1112344Q6x9x5x同理，組件2所能成套的數(shù)目T滿足約束條件：T21233322因而，所能組成的成品機(jī)械的數(shù)目f應(yīng)該為T和T中的較小值，即：12fT,T)12那么，我們求解的目標(biāo)即是使得f能夠盡可能大，可以看出，這種形式并不是有關(guān)設(shè)計變量的線性函數(shù)，我們需要對其進(jìn)行轉(zhuǎn)化，此時我們可以令一個人工設(shè)計變量等于目標(biāo)函數(shù)值，則有：xT,T)412在該假設(shè)下，一定滿足關(guān)系式：Tx且Tx14248x7x9xQ結(jié)合約束關(guān)系，對T的約束可以表示為：xT1123441416x9x5xQ同理，對T的約束可以表示為：xT212333242對T的上述關(guān)系進(jìn)行整理，可以得到關(guān)系：8x7x9x4x011234同理對T也可以得到不等式關(guān)系為：6x9x5x3x021234上面兩個式子即為由組件的配比數(shù)得到的關(guān)于組件數(shù)目的約束條件，此時問題的目標(biāo)就是如何使得x取到最大值，由于開工的次數(shù)一定是一個非負(fù)整數(shù)，故4也是一個約束條件，決定了該問題是一個純整數(shù)規(guī)劃問題。結(jié)合前面給出的原材料約束，可以得到如下的數(shù)學(xué)模型：maxfx4s.t.9x6x4x4001237x10xx60091238x7x9x4x012346x9x5x3x01234i且取整數(shù)值xi（Ⅱ）組件配套問題的求解利用§8.１節(jié)中給出的ＭＡＴＬＡＢ函數(shù)對此問題求解，代碼和運行結(jié)果如下：96479Mxx=x=1xx由運行結(jié)果可知，工廠１、２和３需要分別開工18、15和36次，這樣所能生產(chǎn)出來的成套的機(jī)械為141件。2多目標(biāo)規(guī)劃的MATLAB求解方法（一）多目標(biāo)規(guī)劃的MATLAB求解MATLAB中可以利用不同的函數(shù)進(jìn)行求解，例如在評價函數(shù)法中我們所得最后的評價函數(shù)為一線性MATLAB優(yōu)化工具箱中提供的linprog函數(shù)進(jìn)行求解，如果我們得到的評價函數(shù)為非線性函數(shù)，則可以利用MATLAB優(yōu)化工具箱中提供的fmincon函數(shù)進(jìn)行求解，如果我們采用最大最小法進(jìn)行求解，則可以利用MATLAB優(yōu)化工具箱中提供的fminimax函數(shù)進(jìn)行求解。下面我們就結(jié)合理論求解的幾種方法，講解一下典型多目標(biāo)規(guī)劃問題的MATLAB求解方法。例1利用理想點法求解minf(x)2x3x112minf(x)5x3x2123x2x12s.t.12xx812,0xx12我們首先根據(jù)評價函數(shù)法中的理想點法的理論基礎(chǔ)，按照理想點法的求解思路分別對兩個單目標(biāo)規(guī)劃問題P,P進(jìn)行求解：12f(x)2x3xf(x)5x3x112212s.t.3x2xs.t.3x2xP12,P12x8xx81x21212x,x0x,x01212求解P的MATLAB的代碼和相應(yīng)的運行結(jié)果為：1x==于是可知。當(dāng)時，單目標(biāo)線性規(guī)劃P的最優(yōu)函數(shù)值為。18xfT*111求解P的MATLAB的代碼和相應(yīng)的運行結(jié)果為：2x==于是可知，當(dāng)時，單目標(biāo)線性規(guī)劃P的最優(yōu)函數(shù)值為f20。xT*222由上述兩個單目標(biāo)線性規(guī)劃的求解結(jié)果可知xx，因而22f,f20是一個不可能達(dá)到的理想點，因而我們構(gòu)造如下評價函數(shù)：**122minhf(x)f(x)18f(x)202x3x185x3x2022212121R構(gòu)造描述該評價函數(shù)的函數(shù)文件objfun.m如下：functionf=objfun(x)f=sqrt((2*x(1)-3*x(2)+18)^2+(5*x(1)+3*x(2)-20)^2);然后用非線性規(guī)劃的方式求解上述問題：=1x===5由運行結(jié)果可知在該評價函數(shù)標(biāo)準(zhǔn)之下，問題的最優(yōu)解為：Tx*ff18.0118。*1*2它與理想點f,f20在評價函數(shù)標(biāo)準(zhǔn)下的最小距離為1.9941。**12例2利用評價函數(shù)中的線性加權(quán)和法求解如下多目標(biāo)規(guī)劃問題：min()fxx121x22x23minf(x)x2x3x2122232xx3s.t.x123x,x,x01230.2其中權(quán)系數(shù)為。12建立線性加權(quán)和法的評價函數(shù)為：hf(x)xxxx2x3x21222321222312將相應(yīng)的權(quán)系數(shù)代入上式即整理出目標(biāo)函數(shù)f(x)為：f(x)xxx212223于是建立目標(biāo)函數(shù)的M-函數(shù)文件由于目標(biāo)函數(shù)非線性函數(shù)且具有線性等式約束和邊界約束，因而我們調(diào)用MATLAB中求解非線性規(guī)劃的fmincon函數(shù)對此問題進(jìn)行求解，同時注意如果只考慮第一個目標(biāo)函數(shù)，由這種特殊形式，即在設(shè)計變量的和為一定值，需要求其平方和的最小值時，最優(yōu)解必然是當(dāng)這幾個設(shè)計變量的值相等時取得，于是我們可以將這個解設(shè)為問題的初始點，開始迭代。1x==x*1結(jié)果說明，問題的最優(yōu)解為：xx,)**2*x*3我們在求解多目標(biāo)規(guī)劃問題時，可以采用評價函數(shù)法中的最大最小法，而MATLAB也為這種方法提供了專門的求解函數(shù)fminimaxMATLAB優(yōu)化工具箱中所提供的最大最小法的求解函數(shù)fminimax。最大最小法問題的MATLAB標(biāo)準(zhǔn)形式為：minmaxf(x)ixi0s.t.c(x)c(x)0eqbAxAxbeqeqlbxub函數(shù)fminimax的調(diào)用方式和其他的最優(yōu)化函數(shù)類似，其中所涉及的輸入?yún)?shù)和輸出參數(shù)的含義與非線性規(guī)劃的求解函數(shù)fmincon類似，使用方法也基本相同，細(xì)節(jié)問題讀者可以參考MATLAB的幫助文件。例3求解最大最小問題：minmaxf(x)ixis.t.fx1()24840304x21x22x1x2()3xfxx21222f(x)x3x18312f(x)xx412f(x)xx8512首先建立描述目標(biāo)函數(shù)的函數(shù)文件數(shù)，所求目標(biāo)為這五個函數(shù)最大值中的最小值，代碼如下：f=-++-然后設(shè)置求解的初始點為x0=[0;0]，調(diào)用fminimax求解該問題。===15x===上述結(jié)果說明當(dāng)xx4時，目標(biāo)函數(shù)f(x)i的最大值達(dá)到12i最小，這一組的函數(shù)值為0.0000-64.0006-8.0000，于是最大值為0。多目標(biāo)規(guī)劃的應(yīng)用——投資問題（全國大學(xué)生數(shù)學(xué)建模競賽試題）假設(shè)市場上有種資產(chǎn)，比如股票、債券等可以供投資者選擇，某公司有數(shù)n額為M的一筆相當(dāng)大的資金可用作一個時間的投資。通過財務(wù)人員對S種資產(chǎn)iS的平均收益率為rii出購買S的損失率為q?？紤]到投資越分散，總的風(fēng)險越小，公司決定當(dāng)用這ii筆資金購買若干種資產(chǎn)時，總體風(fēng)險可用所投資的S中的最大一個風(fēng)險來度量。i購買S要付交易費，費率為p，并且當(dāng)購買額不超過給定值u時，交易費iii按購買ur，且既i0無交易費又無風(fēng)險(r＝5％。已知n4時的相關(guān)數(shù)據(jù)如下表所示：0表1SSuii121S234SS試給該公司設(shè)計一種投資組合方案，即用給定的資金M，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總體風(fēng)險盡可能小。（Ⅰ）投資問題的建模為了建立數(shù)學(xué)模型，首先對模型進(jìn)行一些必要的假設(shè)及符號說明：(1)模型的假設(shè)①在一個時期內(nèi)所給出的r，q，p保持不變。iii②在一個時間內(nèi)所購買的各種資產(chǎn)不進(jìn)行買賣交易，即在買入后不再賣出。③每種投資是否收益是相互獨立的。④在投資過程中，無論盈利與否必須先付交易費。符號說明M元：公司現(xiàn)有投資總金額；S,i,n：欲購買的第i種資產(chǎn)種類（其中i0ix,i,n：公司購買S的金額；iir,i,n：公司購買S的平均收益率；iiq,i,n：公司購買S的平均損失率；iip,i,n：公司購買S超過u時所付交易費率。iii下面來建立模型。設(shè)購買S的金額為x，所付的交易費c(x)，則iiii0x0ipu0xui,n)c(x)iiiiipxxuiiiiic(x)000由于投資額相當(dāng)大，所以總可以假定對每個S的投資xu。這時上面Miii的大括號公式可簡化為：c(x)pxi,n)iiii對S投資的凈收益為：R(x)rxc(x)rpxiiiiiiiiii對S的風(fēng)險為：Q(x)qxiiiii對S投資所需資金為投資金額x與所需的手續(xù)費c(x)之和，即：iiiif(x)xc(x)1pxiiiiiii當(dāng)購買S的金額為xi,n)x(x,x,,x)的凈收益總ii01n額為：nR(x)R(x)iii0整體風(fēng)險為：Q(x)maxQ(x)maxq(x)iiiiininn資金約束為：f(x)Miii0根據(jù)題目要求，以凈收益總額R(x)最大，而整體風(fēng)險Q(x)最小為目標(biāo)建立模型如下：nminrpxmaxqxiiiiii0ns.t.1pxMiii0xi,ni很顯然，這是一個多目標(biāo)規(guī)劃問題。（Ⅱ）投資問題的求解在此我們采用主要目標(biāo)法對該問題進(jìn)行求解，即根據(jù)問題的實際情況，確定一個目標(biāo)為主要目標(biāo)，而把其余目標(biāo)作為次要目標(biāo)，并且根據(jù)經(jīng)驗，選取一定的界限值。這樣就可以把次要目標(biāo)作為約束來處理，于是就將原來的多目標(biāo)問題轉(zhuǎn)化為一個在新的約束下的單目標(biāo)最優(yōu)化問題。在上述例子中如果以收益為主要目標(biāo)，則可以固定風(fēng)險水平，給定風(fēng)險一個界限a，講問題轉(zhuǎn)化稱為求最大風(fēng)險不超過a時的最大收益，即下面的線性規(guī)劃模型：rp