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

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

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

3、束條件限制的設(shè)計(jì)變量的序號，例如問題中設(shè)計(jì)變量為，要求和為整數(shù)，則M=2;3;6；若要求全為整數(shù)，則M=1:6，或者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ù)計(jì)算終止時的狀態(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; %均要求為整數(shù)變量Tol=1e

4、-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 = -3.0000（二） 用MATLAB求解0-1規(guī)劃問題在MATLAB優(yōu)化工具箱中，提供了專門用于求解0-1規(guī)劃問題的函數(shù)bintprog，其算法基礎(chǔ)即為分枝界定法，在MATLAB中調(diào)用bintprog函數(shù)求解0-1規(guī)劃時，需要遵循MATLAB中對0-1規(guī)劃標(biāo)準(zhǔn)性的要求

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

6、,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(.)命令詳解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,Aeq,beq)該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問

7、題：4）x = bintprog (c,A,b,Aeq,beq,x0) 該函數(shù)調(diào)用格式求解如下形式的0-1規(guī)劃問題在前一個調(diào)用格式的基礎(chǔ)上同時設(shè)置求解算法的初始解為x0，如果初始解x0不在0-1規(guī)劃問題的可行域中，算法將采用默認(rèn)的初始解5）x = bintprog (c,A,b,Aeq,beq,x0,options)用options指定的優(yōu)化參數(shù)進(jìn)行最小化?？梢允褂胦ptimset來設(shè)置這些參數(shù) 上面的函數(shù)調(diào)用格式僅設(shè)置了最優(yōu)解這一輸出參數(shù)，如果需要更多的輸出參數(shù)，則可以參照下面的調(diào)用格式：x,fval = bintprog(.) 在優(yōu)化計(jì)算結(jié)束之時返回整數(shù)規(guī)劃問題在解x處的目標(biāo)函數(shù)值fval

8、 x,fval,exitflag = bintprog(.) 在優(yōu)化計(jì)算結(jié)束之時返回exitflag值，描述函數(shù)計(jì)算的退出條件。 x,fval,exitflag,output = bintprog(.)在優(yōu)化計(jì)算結(jié)束之時返回結(jié)構(gòu)變量output 例2：求解0-1規(guī)劃問題為了程序的可讀性，我們用一維下標(biāo)來表示設(shè)計(jì)變量，即用表示，用表示，用表示，用表示，于是約束條件和目標(biāo)函數(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 0 0 0 0 0 0 0 0; 0 0 0 0 1 1 1 1 0

9、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; 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);B=reshape(x,4,4); %由于x是一列元素，為了使結(jié)果更加直觀，故排成與效率矩

10、陣E相對應(yīng)的形式B'fval結(jié)果：Optimization terminated.ans = 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1fval = 85整數(shù)規(guī)劃的應(yīng)用組件配套問題某機(jī)械產(chǎn)品需要由三個工廠開工一起生產(chǎn)后組裝完成。每件機(jī)械需要4個組件1和3個組件2。生產(chǎn)這兩種組件需要消耗兩種原材料A和B。已知這兩種原材料的供應(yīng)量分別為400kg和600kg。由于三個工廠的生產(chǎn)條件和擁有設(shè)備工藝條件不同，每個工廠生產(chǎn)組件的能力和原材料的消耗也不盡相同，且每個工廠開工一次都是配套生產(chǎn)一定數(shù)量的組件1和組件2，其具體的數(shù)據(jù)如表所示。表11-2 各工廠生產(chǎn)能力和消耗原材料的數(shù)

11、據(jù)表每個工廠消耗原材料的數(shù)量（公斤）每個工廠各組件的生產(chǎn)能力（件數(shù)）A材料 B材料組件1組件2工廠工廠工廠9647109879695現(xiàn)在的最優(yōu)化問題是，這三個工廠應(yīng)當(dāng)如何安排生產(chǎn)，才能使該產(chǎn)品的配套數(shù)達(dá)到最大？（）組件配套問題的建模設(shè)和是三個工廠分別開工的次數(shù)，將其作為該問題的設(shè)計(jì)變量。由于每個工廠開工一次都是配套生產(chǎn)，故每次開工消耗的原材料一定，且生產(chǎn)的組件數(shù)也是一定的。在這個假設(shè)的前提之下，我們可以得出該問題的目標(biāo)函數(shù)和約束條件。因?yàn)樵牧系目偭渴怯邢薜?，根?jù)工廠的開工次數(shù)，可得工廠將消耗材料，工廠將消耗材料，工廠將消耗材料，故有約束條件：同理，對于材料的總量約束條件可以表達(dá)為：然后再來分

12、析三個工廠零件生產(chǎn)的情況，三個工廠生產(chǎn)的組件1的數(shù)量分別為和，故組件1的總數(shù)為：同理，組件2的總數(shù)為：下一步是分析目標(biāo)函數(shù)，該問題要求的不是生產(chǎn)的各種組件總數(shù)最多，而是要求產(chǎn)品的配套數(shù)量最大，即能組成的機(jī)械數(shù)目最多。問題中已經(jīng)給出了該種機(jī)械中兩種組件的配比為4:3，故組件1所能成套的數(shù)目滿足約束條件：同理，組件2所能成套的數(shù)目滿足約束條件：因而，所能組成的成品機(jī)械的數(shù)目應(yīng)該為和中的較小值，即：那么，我們求解的目標(biāo)即是使得能夠盡可能大，可以看出，這種形式并不是有關(guān)設(shè)計(jì)變量的線性函數(shù)，我們需要對其進(jìn)行轉(zhuǎn)化，此時我們可以令一個人工設(shè)計(jì)變量等于目標(biāo)函數(shù)值，則有：在該假設(shè)下，一定滿足關(guān)系式：且結(jié)合約束關(guān)

13、系，對的約束可以表示為：同理，對的約束可以表示為：對的上述關(guān)系進(jìn)行整理，可以得到關(guān)系：同理對也可以得到不等式關(guān)系為：上面兩個式子即為由組件的配比數(shù)得到的關(guān)于組件數(shù)目的約束條件，此時問題的目標(biāo)就是如何使得取到最大值，由于開工的次數(shù)一定是一個非負(fù)整數(shù)，故也是一個約束條件，決定了該問題是一個純整數(shù)規(guī)劃問題。結(jié)合前面給出的原材料約束，可以得到如下的數(shù)學(xué)模型：（）組件配套問題的求解利用§8.節(jié)中給出的函數(shù)對此問題求解，代碼和運(yùn)行結(jié)果如下：算法：%目標(biāo)函數(shù)所對應(yīng)的設(shè)計(jì)變量的系數(shù)，為轉(zhuǎn)化為極小，故取原目標(biāo)函數(shù)的相反數(shù)f=0;0;0;-1;%不等式約束A= 9 6 4 0; 7 10 9 0; -8

14、 -7 -9 4; -6 -9 -5 3;b=400;600;0;0;%邊界約束，由于無上界，故設(shè)置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和目標(biāo)函數(shù)值fval，并返回狀態(tài)指示x,fval,exitflag=intprog(f,A,b,lb,ub,M,Tol)結(jié)果：x =最優(yōu)解向量x 18 15 36 141fval = 在最優(yōu)解向量x處，原目標(biāo)函數(shù)值的相反數(shù) -141.000exitflag= 算法終止指示變量，說明問題

15、收斂到了最優(yōu)解x 1由運(yùn)行結(jié)果可知，工廠、和需要分別開工18、15和36次，這樣所能生產(chǎn)出來的成套的機(jī)械為141件。2 多目標(biāo)規(guī)劃的MATLAB求解方法（一） 多目標(biāo)規(guī)劃的MATLAB求解由于多目標(biāo)規(guī)劃中的求解涉及到的方法非常多，故在MATLAB中可以利用不同的函數(shù)進(jìn)行求解，例如在評價函數(shù)法中我們所得最后的評價函數(shù)為一線性函數(shù)，且約束條件也為線性函數(shù)，則我們可以利用MATLAB優(yōu)化工具箱中提供的linprog函數(shù)進(jìn)行求解，如果我們得到的評價函數(shù)為非線性函數(shù)，則可以利用MATLAB優(yōu)化工具箱中提供的fmincon函數(shù)進(jìn)行求解，如果我們采用最大最小法進(jìn)行求解，則可以利用MATLAB優(yōu)化工具箱中提供

16、的fminimax函數(shù)進(jìn)行求解。下面我們就結(jié)合理論求解的幾種方法，講解一下典型多目標(biāo)規(guī)劃問題的MATLAB求解方法。例1 利用理想點(diǎn)法求解我們首先根據(jù)評價函數(shù)法中的理想點(diǎn)法的理論基礎(chǔ)，按照理想點(diǎn)法的求解思路分別對兩個單目標(biāo)規(guī)劃問題進(jìn)行求解：求解的MATLAB的代碼和相應(yīng)的運(yùn)行結(jié)果為：算法：c=2;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)結(jié)果：x = 0.0000 6.0000fval = -18.0000于是可知。當(dāng)時，單目標(biāo)線性規(guī)劃的最優(yōu)函數(shù)值為。求解的MATLAB的代碼和相應(yīng)的運(yùn)行結(jié)果為：算法：c=-5;-3;A=3 2;1 1;

17、b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)結(jié)果：Optimization terminated.x = 4.0000 0.0000fval =-20.0000于是可知，當(dāng)時，單目標(biāo)線性規(guī)劃的最優(yōu)函數(shù)值為。由上述兩個單目標(biāo)線性規(guī)劃的求解結(jié)果可知，因而是一個不可能達(dá)到的理想點(diǎn)，因而我們構(gòu)造如下評價函數(shù)：構(gòu)造描述該評價函數(shù)的M-函數(shù)文件objfun.m如下：function f=objfun(x)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

18、=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由運(yùn)行結(jié)果可知在該評價函數(shù)標(biāo)準(zhǔn)之下，問題的最優(yōu)解為：此時，各目標(biāo)函數(shù)的取值為：。它與理想點(diǎn)在評價函數(shù)標(biāo)準(zhǔn)下的最小距離為1.9941。例2 利用評價函數(shù)中的線性加權(quán)和法求解如下多目標(biāo)規(guī)劃問題：其中權(quán)系數(shù)為。建立線性加權(quán)和法

19、的評價函數(shù)為：將相應(yīng)的權(quán)系數(shù)代入上式即整理出目標(biāo)函數(shù)為：于是建立目標(biāo)函數(shù)的M-函數(shù)文件objfun.m：function f=objfun(x)f=x(1)2+1.2*x(2)2+1.4*x(3)2;由于目標(biāo)函數(shù)非線性函數(shù)且具有線性等式約束和邊界約束，因而我們調(diào)用MATLAB中求解非線性規(guī)劃的fmincon函數(shù)對此問題進(jìn)行求解，同時注意如果只考慮第一個目標(biāo)函數(shù)，由這種特殊形式，即在設(shè)計(jì)變量的和為一定值，需要求其平方和的最小值時，最優(yōu)解必然是當(dāng)這幾個設(shè)計(jì)變量的值相等時取得，于是我們可以將這個解設(shè)為問題的初始點(diǎn)，開始迭代。算法：Aeq=1 1 1;beq=3;lb=0;0;0;x0=1;1;1;x

20、,fval=fmincon(objfun,x0,Aeq,beq,lb,)結(jié)果：No active inequalities.x = 1.1776 0.9812 0.8412fval = 3.5327結(jié)果說明，問題的最優(yōu)解為：我們在求解多目標(biāo)規(guī)劃問題時，可以采用評價函數(shù)法中的最大最小法，而MATLAB也為這種方法提供了專門的求解函數(shù)fminimax，在講解這方面的例題之前，我們首先介紹一下MATLAB優(yōu)化工具箱中所提供的最大最小法的求解函數(shù)fminimax。最大最小法問題的MATLAB標(biāo)準(zhǔn)形式為：函數(shù)fminimax的調(diào)用方式和其他的最優(yōu)化函數(shù)類似，其中所涉及的輸入?yún)?shù)和輸出參數(shù)的含義與非線性規(guī)

21、劃的求解函數(shù)fmincon類似，使用方法也基本相同，細(xì)節(jié)問題讀者可以參考MATLAB的幫助文件。例3 求解最大最小問題：首先建立描述目標(biāo)函數(shù)的M-函數(shù)文件objfun.m，注意到一共有五個目標(biāo)函數(shù)，所求目標(biāo)為這五個函數(shù)最大值中的最小值，代碼如下：function f = objfun(x)f(1)= 2*x(1)2+x(2)2-48*x(1)-40*x(2)+304; f(2)= -x(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;然后設(shè)置求解的初始點(diǎn)為x0=0;0，調(diào)用fminima

22、x求解該問題。算法：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 than the default value of the function tolerance and constraints were satisfied to within the default value of the c

23、onstraint tolerance.<stopping criteria details>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.6897e-008上述結(jié)果說明當(dāng)時，目標(biāo)函數(shù)的最大值達(dá)到最小，這一組的函數(shù)值為0.0000，-64.0006，-1.9999，-8.0000，-0.0000，于是

24、最大值為0。多目標(biāo)規(guī)劃的應(yīng)用投資問題（全國大學(xué)生數(shù)學(xué)建模競賽試題）假設(shè)市場上有種資產(chǎn)，比如股票、債券等可以供投資者選擇，某公司有數(shù)額為的一筆相當(dāng)大的資金可用作一個時間的投資。通過財(cái)務(wù)人員對種資產(chǎn)進(jìn)行評估，大概可以估算出在這一時期內(nèi)購買資產(chǎn)的平均收益率為，并預(yù)測出購買的損失率為。考慮到投資越分散，總的風(fēng)險越小，公司決定當(dāng)用這筆資金購買若干種資產(chǎn)時，總體風(fēng)險可用所投資的中的最大一個風(fēng)險來度量。購買要付交易費(fèi)，費(fèi)率為，并且當(dāng)購買額不超過給定值時，交易費(fèi)按購買計(jì)算（不買當(dāng)然無須付費(fèi)）。另外，假定同期銀行存款利率是，且既無交易費(fèi)又無風(fēng)險(5)。已知時的相關(guān)數(shù)據(jù)如下表所示：表1 投資各種資產(chǎn)的參數(shù)值（元）

25、282.51103211.52198235.54.552252.66.540試給該公司設(shè)計(jì)一種投資組合方案，即用給定的資金，有選擇地購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總體風(fēng)險盡可能小。（）投資問題的建模 為了建立數(shù)學(xué)模型，首先對模型進(jìn)行一些必要的假設(shè)及符號說明：(1) 模型的假設(shè) 在一個時期內(nèi)所給出的，保持不變。在一個時間內(nèi)所購買的各種資產(chǎn)(如股票、證券等)不進(jìn)行買賣交易，即在買入后不再賣出。 每種投資是否收益是相互獨(dú)立的。 在投資過程中，無論盈利與否必須先付交易費(fèi)。(2)符號說明 (元)：公司現(xiàn)有投資總金額；：欲購買的第種資產(chǎn)種類（其中表示存入銀行）：公司購買的金額；：公司購買

26、的平均收益率；：公司購買的平均損失率；：公司購買超過時所付交易費(fèi)率。下面來建立模型。設(shè)購買的金額為，所付的交易費(fèi)，則由于投資額相當(dāng)大，所以總可以假定對每個的投資。這時上面的大括號公式可簡化為：對投資的凈收益為：對的風(fēng)險為：對投資所需資金為投資金額與所需的手續(xù)費(fèi)之和，即：當(dāng)購買的金額為，投資組合的凈收益總額為：整體風(fēng)險為：資金約束為：根據(jù)題目要求，以凈收益總額最大，而整體風(fēng)險最小為目標(biāo)建立模型如下：很顯然，這是一個多目標(biāo)規(guī)劃問題。（）投資問題的求解在此我們采用主要目標(biāo)法對該問題進(jìn)行求解，即根據(jù)問題的實(shí)際情況，確定一個目標(biāo)為主要目標(biāo)，而把其余目標(biāo)作為次要目標(biāo)，并且根據(jù)經(jīng)驗(yàn)，選取一定的界限值。這樣就可以把次要目標(biāo)作為約束來處理，于是就將原來的多目標(biāo)問題轉(zhuǎn)化為一個在新的約束下的單目標(biāo)最優(yōu)化問題。在上述例子中如果以收益為主要目標(biāo)，則可以固定風(fēng)險水平，給定風(fēng)險一個界限，講問題轉(zhuǎn)化稱為求最大風(fēng)險不超過時的最大收益，即下面的線性規(guī)劃模型： （1）若投資者希望總盈利至少達(dá)到水平以上，則可以在風(fēng)險最小的情況下尋找相應(yīng)的投資組合，從而將原模型轉(zhuǎn)化成為下列的線性規(guī)劃模型進(jìn)行求解： （2）根據(jù)上面的分析，我們利用主要目標(biāo)法建立了該問題的多目標(biāo)規(guī)劃模型，進(jìn)而轉(zhuǎn)化成為了