整数规划与多目标规划模型

经典word整理文档，仅参考，双击此处可删除页眉页脚。本资料属于网络整理，如有侵权，请联系删除，谢谢！1整数规划的MATLAB求解方法（一）用MATLAB求解一般混合整数规划问题由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif和Tawfik在MATLABCentral上发布的一个用于求解一般混合整数规划的程序，在此命名为，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog函数的调用格式如下：[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)该函数解决的整数规划问题为：fcxminTt.AxbAxbeqeqlbxubx0i,n)x取整数（j）ij在上述标准问题中，假设为维设计变量，且问题具有不等式约束m个，xn1等式约束m个，那么：、均为维列向量，b为m维列向量，b为m维列cxn21eq2向量，A为mn维矩阵，A为mn维矩阵。1eq2在该函数中，输入参数有c,A,b,A,beq,lb,ub,M和。其中c为目标函数所对应设计变量的系数，A为不等式约束条件方程组构成的系数矩阵，b为不等式约束条件方程组右边的值构成的向量。Aeq为等式约束方程组构成的系数矩阵，beq为等式约束条件方程组右边的值构成的向量。lb和ub为设计变量对应的上界和下界。M为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为x,x,,x，要求x,x和x为整数，则；若要求全126236为整数，则，或者M=[1;2;3;4;5;6]。TolXInteger为判定整数的误差限，即若某数x和最邻近整数相差小于该误差限，则认为x即为该整数。在该函数中，输出参数有x,fval和exitflag。其中x为整数规划问题的最优解向量，fval为整数规划问题的目标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量。例1求解整数规划问题：fxx12t.4x2x1124x2x122x12,xx12算法：c=[-1;-1];A=[-42;42;0-2];b=[-1;11;-1];lb=[0;0];M=[1;2];%均要求为整数变量Tol=1e-8;%判断是否整数的误差限[x,fval]=linprog(c,A,b,[],[],lb,[])[x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol)%求最优解整数解结果：%求解原问题松弛线性规划x=%松弛线性规划问题的最优解1.50002.5000fval=-4.0000x1=%整数规划的最优解21fval2=-3.0000（二）用MATLAB求解0-1规划问题在MATLAB优化工具箱中，提供了专门用于求解0-1规划问题的函数，其算法基础即为分枝界定法，在MATLAB中调用bintprog函数求解0-1规划时，需要遵循MATLAB中对0-1规划标准性的要求。0-1规划问题的MATLAB标准型minfcxTbt.AxAxbeqxeq在上述模型中，目标函数f需要极小化，以及需要满足的约束条件，不等式约束一定要化为形式为“”。假设为mmxn12、均为维列向量，b为m维列向量，b为m维列向量，A为mn维矩阵，cxn1eq21A为mn维矩阵。eq2使用相关函数，标准化的方法和线性规划中的类似。0-1规划问题的MATLAB求解函数MATLAB优化工具箱中求解0-1规划问题的命令为bintprogbintprog的调用格式x=x=x=x=x====命令详解1）x=bintprog(f)该函数调用格式求解如下形式的0-1规划问题fcTxt.x2）x=bintprog(c,A,b)该函数调用格式求解如下形式的0-1规划问题fcTxbt.x03）x=bintprog(c,A,b,Aeq,beq)该函数调用格式求解如下形式的0-1规划问题：minfcxTbt.AxAxbeqx0eq4）x=bintprog(c,A,b,Aeq,beq,x0)该函数调用格式求解如下形式的0-1规划问题minfcxTbt.AxAxbeqx0eq在前一个调用格式的基础上同时设置求解算法的初始解为，如果初始解x0不在0-1规划问题的可行域中，算法将采用默认的初始解5）x=bintprog(c,A,b,Aeq,beq,x0,options)用options指定的优化参数进行最小化。可以使用optimset来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出参数，则可以参照下面的调用格式：[x,fval]=bintprog(...)在优化计算结束之时返回整数规划问题在解x处的目标函数值fval[x,fval,exitflag]=bintprog(...)在优化计算结束之时返回exitflag值，描述函数计算的退出条件。[x,fval,exitflag,output]=bintprog(...)在优化计算结束之时返回结构变量output例2：求解0-1规划问题Exnnmaxfijiji1j120123326nt.x1i2,,n221529Eij21133124221632j1nx1j,,n12iji1x4）i2;j2,nijx~x表示x~x，141114用x~x表示x~x，用x~x表示x~x，用x~x表示x~x，于582124912313413164144是约束条件和目标函数分别为：1xxxx1234xxxx15678xxxx19101112xxxx113141516xxx1x15913xxxx1261014xxxx1371115xxxx1481216(ixifExExExExExExEx111122133144215226441611100000000000000011110000000000000001111000000000000000111100010001000100010001000100010001000100010001000100010001000xE相=0010100001000001=整数规划的应用——组件配套问题某机械产品需要由三个工厂开工一起生产后组装完成。每件机械需要4个组件1和3个组件A和原材料的供应量分别为400kg和600kg。由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量的组件1和组件，其具体的数据如表所示。表1296478796959现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配套数达到最大？（Ⅰ）组件配套问题的建模设x、x和x123于每个工厂开工一次都是配套生产，故每次开工消耗的原材料一定，且生产的组件数也是一定的。在这个假设的前提之下，我们可以得出该问题的目标函数和约束条件。A材料9x，工厂２将消耗A材料6x，工厂３将消耗A材料4x，故有约束条件：1239x6x4x400123同理，对于材料B的总量约束条件可以表达为：7x10x9x600123然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1的数量分别为8x7x和9x，故组件1的总数为：Q8x7x9x12311236x9x5x同理，组件2的总数为：Q2123下一步是分析目标函数，该问题要求的不是生产的各种组件总数最多，而是要求产品的配套数量最大，即能组成的机械数目最多。问题中已经给出了该种机械中两种组件的配比为4:3，故组件1所能成套的数目T满足约束条件：1Q8x7x9xT1112344Q6x9x5x同理，组件2所能成套的数目T满足约束条件：T21233322因而，所能组成的成品机械的数目f应该为T和T中的较小值，即：12fT,T)12那么，我们求解的目标即是使得f能够尽可能大，可以看出，这种形式并不是有关设计变量的线性函数，我们需要对其进行转化，此时我们可以令一个人工设计变量等于目标函数值，则有：xT,T)412在该假设下，一定满足关系式：Tx且Tx14248x7x9xQ结合约束关系，对T的约束可以表示为：xT1123441416x9x5xQ同理，对T的约束可以表示为：xT212333242对T的上述关系进行整理，可以得到关系：8x7x9x4x011234同理对T也可以得到不等式关系为：6x9x5x3x021234上面两个式子即为由组件的配比数得到的关于组件数目的约束条件，此时问题的目标就是如何使得x取到最大值，由于开工的次数一定是一个非负整数，故4也是一个约束条件，决定了该问题是一个纯整数规划问题。结合前面给出的原材料约束，可以得到如下的数学模型：maxfx4s.t.9x6x4x4001237x10xx60091238x7x9x4x012346x9x5x3x01234i且取整数值xi（Ⅱ）组件配套问题的求解利用§8.１节中给出的ＭＡＴＬＡＢ函数对此问题求解，代码和运行结果如下：96479Mxx=x=1xx由运行结果可知，工厂１、２和３需要分别开工18、15和36次，这样所能生产出来的成套的机械为141件。2多目标规划的MATLAB求解方法（一）多目标规划的MATLAB求解MATLAB中可以利用不同的函数进行求解，例如在评价函数法中我们所得最后的评价函数为一线性MATLAB优化工具箱中提供的linprog函数进行求解，如果我们得到的评价函数为非线性函数，则可以利用MATLAB优化工具箱中提供的fmincon函数进行求解，如果我们采用最大最小法进行求解，则可以利用MATLAB优化工具箱中提供的fminimax函数进行求解。下面我们就结合理论求解的几种方法，讲解一下典型多目标规划问题的MATLAB求解方法。例1利用理想点法求解minf(x)2x3x112minf(x)5x3x2123x2x12s.t.12xx812,0xx12我们首先根据评价函数法中的理想点法的理论基础，按照理想点法的求解思路分别对两个单目标规划问题P,P进行求解：12f(x)2x3xf(x)5x3x112212s.t.3x2xs.t.3x2xP12,P12x8xx81x21212x,x0x,x01212求解P的MATLAB的代码和相应的运行结果为：1x==于是可知。当时，单目标线性规划P的最优函数值为。18xfT*111求解P的MATLAB的代码和相应的运行结果为：2x==于是可知，当时，单目标线性规划P的最优函数值为f20。xT*222由上述两个单目标线性规划的求解结果可知xx，因而22f,f20是一个不可能达到的理想点，因而我们构造如下评价函数：**122minhf(x)f(x)18f(x)202x3x185x3x2022212121R构造描述该评价函数的函数文件objfun.m如下：functionf=objfun(x)f=sqrt((2*x(1)-3*x(2)+18)^2+(5*x(1)+3*x(2)-20)^2);然后用非线性规划的方式求解上述问题：=1x===5由运行结果可知在该评价函数标准之下，问题的最优解为：Tx*ff18.0118。*1*2它与理想点f,f20在评价函数标准下的最小距离为1.9941。**12例2利用评价函数中的线性加权和法求解如下多目标规划问题：min()fxx121x22x23minf(x)x2x3x2122232xx3s.t.x123x,x,x01230.2其中权系数为。12建立线性加权和法的评价函数为：hf(x)xxxx2x3x21222321222312将相应的权系数代入上式即整理出目标函数f(x)为：f(x)xxx212223于是建立目标函数的M-函数文件由于目标函数非线性函数且具有线性等式约束和边界约束，因而我们调用MATLAB中求解非线性规划的fmincon函数对此问题进行求解，同时注意如果只考虑第一个目标函数，由这种特殊形式，即在设计变量的和为一定值，需要求其平方和的最小值时，最优解必然是当这几个设计变量的值相等时取得，于是我们可以将这个解设为问题的初始点，开始迭代。1x==x*1结果说明，问题的最优解为：xx,)**2*x*3我们在求解多目标规划问题时，可以采用评价函数法中的最大最小法，而MATLAB也为这种方法提供了专门的求解函数fminimaxMATLAB优化工具箱中所提供的最大最小法的求解函数fminimax。最大最小法问题的MATLAB标准形式为：minmaxf(x)ixi0s.t.c(x)c(x)0eqbAxAxbeqeqlbxub函数fminimax的调用方式和其他的最优化函数类似，其中所涉及的输入参数和输出参数的含义与非线性规划的求解函数fmincon类似，使用方法也基本相同，细节问题读者可以参考MATLAB的帮助文件。例3求解最大最小问题：minmaxf(x)ixis.t.fx1()24840304x21x22x1x2()3xfxx21222f(x)x3x18312f(x)xx412f(x)xx8512首先建立描述目标函数的函数文件数，所求目标为这五个函数最大值中的最小值，代码如下：f=-++-然后设置求解的初始点为x0=[0;0]，调用fminimax求解该问题。===15x===上述结果说明当xx4时，目标函数f(x)i的最大值达到12i最小，这一组的函数值为0.0000-64.0006-8.0000，于是最大值为0。多目标规划的应用——投资问题（全国大学生数学建模竞赛试题）假设市场上有种资产，比如股票、债券等可以供投资者选择，某公司有数n额为M的一笔相当大的资金可用作一个时间的投资。通过财务人员对S种资产iS的平均收益率为rii出购买S的损失率为q。考虑到投资越分散，总的风险越小，公司决定当用这ii笔资金购买若干种资产时，总体风险可用所投资的S中的最大一个风险来度量。i购买S要付交易费，费率为p，并且当购买额不超过给定值u时，交易费iii按购买ur，且既i0无交易费又无风险(r＝5％。已知n4时的相关数据如下表所示：0表1SSuii121S234SS试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。（Ⅰ）投资问题的建模为了建立数学模型，首先对模型进行一些必要的假设及符号说明：(1)模型的假设①在一个时期内所给出的r，q，p保持不变。iii②在一个时间内所购买的各种资产不进行买卖交易，即在买入后不再卖出。③每种投资是否收益是相互独立的。④在投资过程中，无论盈利与否必须先付交易费。符号说明M元：公司现有投资总金额；S,i,n：欲购买的第i种资产种类（其中i0ix,i,n：公司购买S的金额；iir,i,n：公司购买S的平均收益率；iiq,i,n：公司购买S的平均损失率；iip,i,n：公司购买S超过u时所付交易费率。iii下面来建立模型。设购买S的金额为x，所付的交易费c(x)，则iiii0x0ipu0xui,n)c(x)iiiiipxxuiiiiic(x)000由于投资额相当大，所以总可以假定对每个S的投资xu。这时上面Miii的大括号公式可简化为：c(x)pxi,n)iiii对S投资的净收益为：R(x)rxc(x)rpxiiiiiiiiii对S的风险为：Q(x)qxiiiii对S投资所需资金为投资金额x与所需的手续费c(x)之和，即：iiiif(x)xc(x)1pxiiiiiii当购买S的金额为xi,n)x(x,x,,x)的净收益总ii01n额为：nR(x)R(x)iii0整体风险为：Q(x)maxQ(x)maxq(x)iiiiininn资金约束为：f(x)Miii0根据题目要求，以净收益总额R(x)最大，而整体风险Q(x)最小为目标建立模型如下：nminrpxmaxqxiiiiii0ns.t.1pxMiii0xi,ni很显然，这是一个多目标规划问题。（Ⅱ）投资问题的求解在此我们采用主要目标法对该问题进行求解，即根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。在上述例子中如果以收益为主要目标，则可以固定风险水平，给定风险一个界限a，讲问题转化称为求最大风险不超过a时的最大收益，即下面的线性规划模型：rp