整數(shù)規(guī)劃和多目標規(guī)劃模型Word版

1、1 整數(shù)規(guī)劃的MATLAB求解方法（一） 用MATLAB求解一般混合整數(shù)規(guī)劃問題由于MATLAB優(yōu)化工具箱中并未提供求解純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃的函數(shù)，因而需要自行根據(jù)需要和設定相關(guān)的算法來實現(xiàn)。現(xiàn)在有許多用戶發(fā)布的工具箱可以解決該類問題。這里我們給出開羅大學的Sherif和Tawfik在MATLAB Central上發(fā)布的一個用于求解一般混合整數(shù)規(guī)劃的程序，在此命名為intprog，在原程序的基礎(chǔ)上做了簡單的修改，將其選擇分枝變量的算法由自然序改造成分枝變量選擇原則中的一種，即：選擇與整數(shù)值相差最大的非整數(shù)變量首先進行分枝。intprog函數(shù)的調(diào)用格式如下： x,fval,exitflag=

2、intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 該函數(shù)解決的整數(shù)規(guī)劃問題為：在上述標準問題中，假設為維設計變量，且問題具有不等式約束個，等式約束個，那么：、均為維列向量，為維列向量，為維列向量，為維矩陣，為維矩陣。在該函數(shù)中，輸入?yún)?shù)有c,A,b,Aeq,beq,lb,ub,M和TolXInteger。其中c為目標函數(shù)所對應設計變量的系數(shù)，A為不等式約束條件方程組構(gòu)成的系數(shù)矩陣，b為不等式約束條件方程組右邊的值構(gòu)成的向量。Aeq為等式約束方程組構(gòu)成的系數(shù)矩陣，beq為等式約束條件方程組右邊的值構(gòu)成的向量。lb和ub為設計變量對應的上界和下界。M為具有整數(shù)約

3、束條件限制的設計變量的序號，例如問題中設計變量為，要求和為整數(shù)，則M=2;3;6；若要求全為整數(shù)，則M=1:6，或者M=1;2;3;4;5;6。TolXInteger為判定整數(shù)的誤差限，即若某數(shù)x和最鄰近整數(shù)相差小于該誤差限，則認為整理為word格式x即為該整數(shù)。在該函數(shù)中，輸出參數(shù)有x, fval和exitflag。其中x為整數(shù)規(guī)劃問題的最優(yōu)解向量，fval為整數(shù)規(guī)劃問題的目標函數(shù)在最優(yōu)解向量x處的函數(shù)值，exitflag為函數(shù)計算終止時的狀態(tài)指示變量。例1 求解整數(shù)規(guī)劃問題：算法：c=-1;-1;A=-4 2;4 2;0 -2;b=-1;11;-1;lb=0;0;M=1;2; %均要求為整

4、數(shù)變量Tol=1e-8; %判斷是否整數(shù)的誤差限x,fval=linprog(c,A,b,lb,) %求解原問題松弛線性規(guī)劃x1,fval1=intprog(c,A,b,lb,M,Tol) %求最優(yōu)解整數(shù)解結(jié)果：x =%松弛線性規(guī)劃問題的最優(yōu)解 1.5000 2.5000fval = -4.0000x1 =%整數(shù)規(guī)劃的最優(yōu)解 2 1fval2 =整理為word格式 -3.0000（二） 用MATLAB求解0-1規(guī)劃問題在MATLAB優(yōu)化工具箱中，提供了專門用于求解0-1規(guī)劃問題的函數(shù)bintprog，其算法基礎(chǔ)即為分枝界定法，在MATLAB中調(diào)用bintprog函數(shù)求解0-1規(guī)劃時，需要遵循M

5、ATLAB中對0-1規(guī)劃標準性的要求。 0-1規(guī)劃問題的MATLAB標準型在上述模型中，目標函數(shù)f 需要極小化，以及需要滿足的約束條件，不等式約束一定要化為形式為“”。假設為維設計變量，且問題具有不等式約束個，等式約束個，那么：、均為維列向量，為維列向量，為維列向量，為維矩陣，為維矩陣。如果不滿足標準型的要求，則需要對原問題進行轉(zhuǎn)化，化為標準型之后才能使用相關(guān)函數(shù)，標準化的方法和線性規(guī)劃中的類似。0-1規(guī)劃問題的MATLAB求解函數(shù) MATLAB優(yōu)化工具箱中求解0-1規(guī)劃問題的命令為bintprog bintprog的調(diào)用格式x = bintprog(f)x = bintprog(f,A,b)

6、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(.)整理為word格式命令詳解1）x = bintprog(f) 該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題 2）x = bintprog(c,A,b) 該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題 3）x = bintprog (c,A,b,A

7、eq,beq)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題：4）x = bintprog (c,A,b,Aeq,beq,x0) 該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題在前一個調(diào)用格式的基礎(chǔ)上同時設置求解算法的初始解為x0，如果初始解x0不在0-1規(guī)劃問題的可行域中，算法將采用默認的初始解5）x = bintprog (c,A,b,Aeq,beq,x0,options)用options指定的優(yōu)化參數(shù)進行最小化。可以使用optimset來設置這些參數(shù) 上面的函數(shù)調(diào)用格式僅設置了最優(yōu)解這一輸出參數(shù)，如果需要更多的輸出參數(shù)，則可以參照下面的調(diào)用格式：x,fval = bintprog(.) 在優(yōu)化計

8、算結(jié)束之時返回整數(shù)規(guī)劃問題在解x處的目標函數(shù)值fval 整理為word格式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ī)劃問題為了程序的可讀性，我們用一維下標來表示設計變量，即用表示，用表示，用表示，用表示，于是約束條件和目標函數(shù)分別為： 算法：c=20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23;Aeq=1 1 1 1 0 0 0 0

9、 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1;整理為word格式 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0; 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0; 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1; ;beq=ones(1,8);x,fval=bintprog(c,Aeq,beq);

10、B=reshape(x,4,4); %由于x是一列元素，為了使結(jié)果更加直觀，故排成與效率矩陣E相對應的形式Bfval結(jié)果：Optimization terminated.ans = 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1fval = 85整數(shù)規(guī)劃的應用組件配套問題某機械產(chǎn)品需要由三個工廠開工一起生產(chǎn)后組裝完成。每件機械需要4個組件1和3個組件2。生產(chǎn)這兩種組件需要消耗兩種原材料A和B。已知這兩種原材料的供應量分別為400kg和600kg。由于三個工廠的生產(chǎn)條件和擁有設備工藝條件不同，每個工廠生產(chǎn)組件的能力和原材料的消耗也不盡相同，且每個工廠開工一次都是配套生產(chǎn)一定數(shù)量的

11、組件1和組件2，其具體的數(shù)據(jù)如表所示。表11-2 各工廠生產(chǎn)能力和消耗原材料的數(shù)據(jù)表整理為word格式每個工廠消耗原材料的數(shù)量（公斤）每個工廠各組件的生產(chǎn)能力（件數(shù)）A材料 B材料組件1組件2工廠工廠工廠9647109879695現(xiàn)在的最優(yōu)化問題是，這三個工廠應當如何安排生產(chǎn)，才能使該產(chǎn)品的配套數(shù)達到最大？（）組件配套問題的建模設和是三個工廠分別開工的次數(shù)，將其作為該問題的設計變量。由于每個工廠開工一次都是配套生產(chǎn)，故每次開工消耗的原材料一定，且生產(chǎn)的組件數(shù)也是一定的。在這個假設的前提之下，我們可以得出該問題的目標函數(shù)和約束條件。因為原材料的總量是有限的，根據(jù)工廠的開工次數(shù)，可得工廠將消耗材料

12、，工廠將消耗材料，工廠將消耗材料，故有約束條件：同理，對于材料的總量約束條件可以表達為：然后再來分析三個工廠零件生產(chǎn)的情況，三個工廠生產(chǎn)的組件1的數(shù)量分別為和，故組件1的總數(shù)為：同理，組件2的總數(shù)為：下一步是分析目標函數(shù)，該問題要求的不是生產(chǎn)的各種組件總數(shù)最多，而是要求產(chǎn)品的配套數(shù)量最大，即能組成的機械數(shù)目最多。問題中已經(jīng)給出了該種機械中兩種組件的配比為4:3，故組件1所能成套的數(shù)目滿足約束條件：同理，組件2所能成套的數(shù)目滿足約束條件：整理為word格式因而，所能組成的成品機械的數(shù)目應該為和中的較小值，即：那么，我們求解的目標即是使得能夠盡可能大，可以看出，這種形式并不是有關(guān)設計變量的線性函數(shù)

13、，我們需要對其進行轉(zhuǎn)化，此時我們可以令一個人工設計變量等于目標函數(shù)值，則有：在該假設下，一定滿足關(guān)系式：且結(jié)合約束關(guān)系，對的約束可以表示為：同理，對的約束可以表示為：對的上述關(guān)系進行整理，可以得到關(guān)系：同理對也可以得到不等式關(guān)系為：上面兩個式子即為由組件的配比數(shù)得到的關(guān)于組件數(shù)目的約束條件，此時問題的目標就是如何使得取到最大值，由于開工的次數(shù)一定是一個非負整數(shù)，故也是一個約束條件，決定了該問題是一個純整數(shù)規(guī)劃問題。結(jié)合前面給出的原材料約束，可以得到如下的數(shù)學模型：（）組件配套問題的求解利用8.節(jié)中給出的函數(shù)對此問題求解，代碼和運行結(jié)果如下：算法：%目標函數(shù)所對應的設計變量的系數(shù)，為轉(zhuǎn)化為極小，

14、故取原目標函數(shù)的相反數(shù)f=0;0;0;-1;整理為word格式%不等式約束A= 9 6 4 0; 7 10 9 0; -8 -7 -9 4; -6 -9 -5 3;b=400;600;0;0;%邊界約束，由于無上界，故設置ub=Inf;Inf;Inf;Inf;lb=0;0;0;0;ub=Inf;Inf;Inf;Inf;%所有變量均為整數(shù)變量，故將所有序號組成向量MM=1;2;3;4;%判定為整數(shù)的誤差限Tol=1e-8;%求最優(yōu)解x和目標函數(shù)值fval，并返回狀態(tài)指示x,fval,exitflag=intprog(f,A,b,lb,ub,M,Tol)結(jié)果：x =最優(yōu)解向量x 18 15 36

15、141fval = 在最優(yōu)解向量x處，原目標函數(shù)值的相反數(shù) -141.000exitflag= 算法終止指示變量，說明問題收斂到了最優(yōu)解x 1由運行結(jié)果可知，工廠、和需要分別開工18、15和36次，這樣所能生產(chǎn)出來的成套的機械為141件。2 多目標規(guī)劃的MATLAB求解方法整理為word格式（一） 多目標規(guī)劃的MATLAB求解由于多目標規(guī)劃中的求解涉及到的方法非常多，故在MATLAB中可以利用不同的函數(shù)進行求解，例如在評價函數(shù)法中我們所得最后的評價函數(shù)為一線性函數(shù)，且約束條件也為線性函數(shù)，則我們可以利用MATLAB優(yōu)化工具箱中提供的linprog函數(shù)進行求解，如果我們得到的評價函數(shù)為非線性函數(shù)

16、，則可以利用MATLAB優(yōu)化工具箱中提供的fmincon函數(shù)進行求解，如果我們采用最大最小法進行求解，則可以利用MATLAB優(yōu)化工具箱中提供的fminimax函數(shù)進行求解。下面我們就結(jié)合理論求解的幾種方法，講解一下典型多目標規(guī)劃問題的MATLAB求解方法。例1 利用理想點法求解我們首先根據(jù)評價函數(shù)法中的理想點法的理論基礎(chǔ)，按照理想點法的求解思路分別對兩個單目標規(guī)劃問題進行求解：求解的MATLAB的代碼和相應的運行結(jié)果為：算法：c=2;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)結(jié)果：x =整理為word格式 0.0000 6.0000fv

17、al = -18.0000于是可知。當時，單目標線性規(guī)劃的最優(yōu)函數(shù)值為。求解的MATLAB的代碼和相應的運行結(jié)果為：算法：c=-5;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)結(jié)果：Optimization terminated.x = 4.0000 0.0000fval =-20.0000于是可知，當時，單目標線性規(guī)劃的最優(yōu)函數(shù)值為。由上述兩個單目標線性規(guī)劃的求解結(jié)果可知，因而是一個不可能達到的理想點，因而我們構(gòu)造如下評價函數(shù)：構(gòu)造描述該評價函數(shù)的M-函數(shù)文件objfun.m如下：function f=objfun(x)整理為word格

18、式f=sqrt(2*x(1)-3*x(2)+18)2+(5*x(1)+3*x(2)-20)2);然后用非線性規(guī)劃的方式求解上述問題：算法：A=3 2;1 1;b=12;8;lb=0;0;x0=0;0;x,fval,exitflag=fmincon(objfun,x0,A,b,lb,)結(jié)果： Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 1 x = 0.0235 5.9647fval = 1.9941exitflag = 5由運行結(jié)果可知在該評價函數(shù)標準之下，問題的最

19、優(yōu)解為：此時，各目標函數(shù)的取值為：。它與理想點在評價函數(shù)標準下的最小距離為1.9941。例2 利用評價函數(shù)中的線性加權(quán)和法求解如下多目標規(guī)劃問題：其中權(quán)系數(shù)為。整理為word格式建立線性加權(quán)和法的評價函數(shù)為：將相應的權(quán)系數(shù)代入上式即整理出目標函數(shù)為：于是建立目標函數(shù)的M-函數(shù)文件objfun.m：function f=objfun(x)f=x(1)2+1.2*x(2)2+1.4*x(3)2;由于目標函數(shù)非線性函數(shù)且具有線性等式約束和邊界約束，因而我們調(diào)用MATLAB中求解非線性規(guī)劃的fmincon函數(shù)對此問題進行求解，同時注意如果只考慮第一個目標函數(shù)，由這種特殊形式，即在設計變量的和為一定值，

20、需要求其平方和的最小值時，最優(yōu)解必然是當這幾個設計變量的值相等時取得，于是我們可以將這個解設為問題的初始點，開始迭代。算法：Aeq=1 1 1;beq=3;lb=0;0;0;x0=1;1;1;x,fval=fmincon(objfun,x0,Aeq,beq,lb,)結(jié)果：No active inequalities.x = 1.1776 0.9812 0.8412fval = 3.5327結(jié)果說明，問題的最優(yōu)解為：整理為word格式我們在求解多目標規(guī)劃問題時，可以采用評價函數(shù)法中的最大最小法，而MATLAB也為這種方法提供了專門的求解函數(shù)fminimax，在講解這方面的例題之前，我們首先介紹一

21、下MATLAB優(yōu)化工具箱中所提供的最大最小法的求解函數(shù)fminimax。最大最小法問題的MATLAB標準形式為：函數(shù)fminimax的調(diào)用方式和其他的最優(yōu)化函數(shù)類似，其中所涉及的輸入?yún)?shù)和輸出參數(shù)的含義與非線性規(guī)劃的求解函數(shù)fmincon類似，使用方法也基本相同，細節(jié)問題讀者可以參考MATLAB的幫助文件。例3 求解最大最小問題：首先建立描述目標函數(shù)的M-函數(shù)文件objfun.m，注意到一共有五個目標函數(shù)，所求目標為這五個函數(shù)最大值中的最小值，代碼如下：function f = objfun(x)f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x

22、(1)2 - 3*x(2)2;f(3)= x(1) + 3*x(2) -18;f(4)= -x(1)- x(2);f(5)= x(1) + x(2) - 8;然后設置求解的初始點為x0=0;0，調(diào)用fminimax求解該問題。算法：整理為word格式x0 = 0; 0;x,fval,maxfval = fminimax(objfun,x0)結(jié)果：Local minimum possible. Constraints satisfied.fminimax stopped because the predicted change in the objective functionis less t

23、han the default value of the function tolerance and constraints were satisfied to within the default value of the constraint tolerance.Active inequalities (to within options.TolCon = 1e-006): lower upper ineqlin ineqnonlin 1 5x = 4.0000 4.0000fval = 0.0000 -64.0006 -1.9999 -8.0000 -0.0000maxfval = 2

24、.6897e-008上述結(jié)果說明當時，目標函數(shù)的最大值達到最小，這一組的函數(shù)值為0.0000，-64.0006，-1.9999，-8.0000，-0.0000，于是最大值為0。多目標規(guī)劃的應用投資問題（全國大學生數(shù)學建模競賽試題）假設市場上有種資產(chǎn)，比如股票、債券等可以供投資者選擇，某公司有數(shù)額為的一筆相當大的資金可用作一個時間的投資。通過財務人員對種資產(chǎn)進行評估，大概可以估算出在這一時期內(nèi)購買資產(chǎn)的平均收益率為，并預測出購買的損失率為?？紤]到投資越分散，總的風險越小，公司決定當用這筆資金購買若干種資產(chǎn)時，總體風險可用所投資的整理為word格式中的最大一個風險來度量。購買要付交易費，費率為，并

25、且當購買額不超過給定值時，交易費按購買計算（不買當然無須付費）。另外，假定同期銀行存款利率是，且既無交易費又無風險(5)。已知時的相關(guān)數(shù)據(jù)如下表所示：表1 投資各種資產(chǎn)的參數(shù)值（元）282.51103211.52198235.54.552252.66.540試給該公司設計一種投資組合方案，即用給定的資金，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總體風險盡可能小。（）投資問題的建模 為了建立數(shù)學模型，首先對模型進行一些必要的假設及符號說明：(1) 模型的假設 在一個時期內(nèi)所給出的，保持不變。在一個時間內(nèi)所購買的各種資產(chǎn)(如股票、證券等)不進行買賣交易，即在買入后不再賣出。 每種投

26、資是否收益是相互獨立的。 在投資過程中，無論盈利與否必須先付交易費。(2)符號說明 (元)：公司現(xiàn)有投資總金額；：欲購買的第種資產(chǎn)種類（其中表示存入銀行）：整理為word格式：公司購買的金額；：公司購買的平均收益率；：公司購買的平均損失率；：公司購買超過時所付交易費率。下面來建立模型。設購買的金額為，所付的交易費，則由于投資額相當大，所以總可以假定對每個的投資。這時上面的大括號公式可簡化為：對投資的凈收益為：對的風險為：對投資所需資金為投資金額與所需的手續(xù)費之和，即：當購買的金額為，投資組合的凈收益總額為：整體風險為：資金約束為：根據(jù)題目要求，以凈收益總額最大，而整體風險最小為目標建立模型如下

27、：整理為word格式很顯然，這是一個多目標規(guī)劃問題。（）投資問題的求解在此我們采用主要目標法對該問題進行求解，即根據(jù)問題的實際情況，確定一個目標為主要目標，而把其余目標作為次要目標，并且根據(jù)經(jīng)驗，選取一定的界限值。這樣就可以把次要目標作為約束來處理，于是就將原來的多目標問題轉(zhuǎn)化為一個在新的約束下的單目標最優(yōu)化問題。在上述例子中如果以收益為主要目標，則可以固定風險水平，給定風險一個界限，講問題轉(zhuǎn)化稱為求最大風險不超過時的最大收益，即下面的線性規(guī)劃模型： （1）若投資者希望總盈利至少達到水平以上，則可以在風險最小的情況下尋找相應的投資組合，從而將原模型轉(zhuǎn)化成為下列的線性規(guī)劃模型進行求解： （2）根據(jù)上面的分析，我們利用主要目標法建立了該問題的多目標規(guī)劃模型，進而轉(zhuǎn)化成為了線性規(guī)劃模型，下面我們利用MATLAB對