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

1、1 整数规划的 MATLAB求解方法（一）用 MATLAB求解一般混合整数规划问题由于 MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题。这里我们给出开罗大学的Sherif和 Tawfik 在 MATLABCentral上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog函数的调用格式如下：x,fval,exitf

2、lag=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)该函数解决的整数规划问题为：在上述标准问题中， 假设 x 为 n 维设计变量， 且问题具有不等式约束m1 个，等式约束m 个，那么：、 均为n维列向量， b 为 m 维列向量，beq为 m 维列向量， A 为 m n2cx121维矩阵， Aeq 为 m2n 维矩阵。在该函数中，输入参数有c,A,b,Aeqeq和TolXInteger。其中c为目标,b,lb,ub,M函数所对应设计变量的系数，A 为不等式约束条件方程组构成的系数矩阵，b 为不等式约束条件方程组右边的值构成的向量。 Aeq 为等式约束方程组

3、构成的系数矩阵，eq 为b等式约束条件方程组右边的值构成的向量。lb 和 ub 为设计变量对应的上界和下界。 M为具有整数约束条件限制的设计变量的序号，例如问题中设计变量为x1, x2 , x6 ，要求 x2 , x3 和 x6为整数，则 M=2;3;6 ；若要求全为整数，则 M=1:6，或者 M=1;2;3;4;5;6 。TolXInteger为判定整数的误差限，即若某数x 和最邻近整数相差小于该误差限，则认为 x 即为该整数。在该函数中，输出参数有 x, fval 和 exitflag。其中 x 为整数规划问题的最优解向量，fval 为整数规划问题的目标函数在最优解向量x 处的函数值， e

4、xitflag为函数计算终止时的状态指示变量。例 1 求解整数规划问题：算法：c=-1;-1;A=-4 2;4 2;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优化工具箱

5、中，提供了专门用于求解 0-1 规划问题的函数 bintprog ，其算法基础即为分枝界定法，在 MATLAB中调用 bintprog 函数求解 0-1 规划时，需要遵循 MATLAB中对 0-1 规划标准性的要求。0-1规划问题的 MATLAB标准型在上述模型中，目标函数 f 需要极小化，以及需要满足的约束条件，不等式约束一定要化为形式为“ ”。假设 x 为 n 维设计变量，且问题具有不等式约束 m1 个，等式约束 m2 个，那么： c 、 x 均为 n 维列向量， b 为 m1 维列向量， beq 为 m2 维列向量， A 为 m1 n 维矩阵， Aeq 为m2n 维矩阵。如果不满足标准型

6、的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似。0-1 规划问题的 MATLAB求解函数MATLAB优化工具箱中求解0-1 规划问题的命令为bintprogbintprog的调用格式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,

7、exitflag,output = bintprog(.)命令详解1）x = bintprog(f)该函数调用格式求解如下形式的0-1 规划问题2）x = bintprog(c,A,b)该函数调用格式求解如下形式的0-1 规划问题3）x = bintprog (c,A,b,Aeq,beq)该函数调用格式求解如下形式的0-1 规划问题：4）x = bintprog (c,A,b,Aeq,beq,x0)该函数调用格式求解如下形式的0-1 规划问题在前一个调用格式的基础上同时设置求解算法的初始解为x0，如果初始解x0 不在 0-1 规划问题的可行域中，算法将采用默认的初始解5）x = bintpro

8、g (c,A,b,Aeq,beq,x0,options)用 options 指定的优化参数进行最小化。可以使用 optimset 来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出参数，则可以参照下面的调用格式：x,fval = bintprog(.)在优化计算结束之时返回整数规划问题在解x 处的目标函数值fvalx,fval,exitflag = bintprog(.)在优化计算结束之时返回exitflag值，描述函数计算的退出条件。x,fval,exitflag,output = bintprog(.)在优化计算结束之时返回结构变量output例 2：求解0-1

9、规划问题为了程序的可读性，我们用一维下标来表示设计变量，即用x1 x4 表示x11 x14 ，用x5 x8 表示x21 x24 ，用 x9 x12 表示x31 x34 ，用x13 x16 表示 x41 x44 ，于是约束条件和目标函数分别为：算法：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;0000000011110000;0000000000001111;beq=ones(1,8);x,fval=bintprog(c,Aeq,beq);B=reshape(x,4,4

10、); %由于 x 是一列元素，为了使结果更加直观，故排成与效率矩阵 E 相对应的形式Bfval结果：Optimization terminated.ans =0100001010000001fval =85整数规划的应用组件配套问题某机械产品需要由三个工厂开工一起生产后组装完成。每件机械需要4 个组件1和 3个组件2。生产这两种组件需要消耗两种原材料A 和 B。已知这两种原材料的供应量分别为400kg 和 600kg。由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量的组件1 和组件 2，其具体的数据如表所示。表

11、 11-2 各工厂生产能力和消耗原材料的数据表每个工厂消耗原材料的数量每个工厂各组件的生产能力（公斤）（件数）A 材料B 材料组件 1组件 2工厂9786工厂61079工厂4995现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配套数达到最大？（）组件配套问题的建模设 x1、x2 和 x3 是三个工厂分别开工的次数，将其作为该问题的设计变量。由于每个工厂开工一次都是配套生产，故每次开工消耗的原材料一定，且生产的组件数也是一定的。在这个假设的前提之下，我们可以得出该问题的目标函数和约束条件。因为原材料的总量是有限的， 根据工厂的开工次数， 可得工厂将消耗A 材料 9x1 ，工 厂

12、将 消 耗 A 材 料 6x2 ， 工 厂 将 消 耗 A 材 料 4x3 ， 故 有 约 束 条 件 ：9x16x24x3400同理，对于材料 B 的总量约束条件可以表达为：7 x1 10x29x3 600然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1 的数量分别为8x1、7x2 和 9x3 ，故组件 1 的总数为： Q1 8x17x29x3同理，组件 2 的总数为： Q 26 x 19 x 25 x 3下一步是分析目标函数，该问题要求的不是生产的各种组件总数最多，而是要求产品的配套数量最大，即能组成的机械数目最多。问题中已经给出了该种机械中两种Q18x17 x2 9 x3组件的配

13、比为 4:3 ，故组件 1 所能成套的数目 T1 满足约束条件： T144同理，组件 2 所能成套的数目 T2Q2 6x19 x25x3满足约束条件： T233因而，所能组成的成品机械的数目f 应该为 T1 和 T2 中的较小值，即：fmin( T1 ,T2 )那么，我们求解的目标即是使得f 能够尽可能大，可以看出，这种形式并不是有关设计变量的线性函数，我们需要对其进行转化，此时我们可以令一个人工设计变量等于目标函数值，则有： x4 min( T1, T2 )在该假设下，一定满足关系式： T1x4 且 T2x4结合约束关系，对 T1 的约束可以表示为： x4T1Q18x17x29 x344同理

14、，对 T2 的约束可以表示为： x4Q26x1 9x2 5x3T233对 T1 的上述关系进行整理，可以得到关系：8x17x29x34x40同理对 T2 也可以得到不等式关系为：6x1 9x25x33x40上面两个式子即为由组件的配比数得到的关于组件数目的约束条件，此时问题的目标就是如何使得 x4 取到最大值，由于开工的次数一定是一个非负整数，故也是一个约束条件，决定了该问题是一个纯整数规划问题。结合前面给出的原材料约束，可以得到如下的数学模型：（）组件配套问题的求解利用 8. 节中给出的函数对此问题求解，代码和运行结果如下：算法：%目标函数所对应的设计变量的系数，为转化为极小，故取原目标函数

15、的相反数f=0;0;0;-1;%不等式约束A=9 6 40;710 90;-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;%所有变量均为整数变量，故将所有序号组成向量MM=1;2;3;4;%判定为整数的误差限Tol=1e-8;%求最优解 x 和目标函数值fval ，并返回状态指示x,fval,exitflag=intprog(f,A,b,lb,ub,M,Tol)结果：x =最优解向量 x181536141fval =在最优解向量x 处，原目标函

16、数值的相反数-141.000exitflag=算法终止指示变量，说明问题收敛到了最优解 x1由运行结果可知，工厂、和需要分别开工18、 15 和 36 次，这样所能生产出来的成套的机械为141 件。2 多目标规划的 MATLAB求解方法（一） 多目标规划的 MATLAB求解由于多目标规划中的求解涉及到的方法非常多，故在 MATLAB中可以利用不同的函数进行求解，例如在评价函数法中我们所得最后的评价函数为一线性函数，且约束条件也为线性函数，则我们可以利用 MATLAB优化工具箱中提供的linprog函数进行求解，如果我们得到的评价函数为非线性函数，则可以利用MATLAB优化工具箱中提供的fmin

17、con 函数进行求解，如果我们采用最大最小法进行求解，则可以利用MATLAB优化工具箱中提供的fminimax 函数进行求解。 下面我们就结合理论求解的几种方法，讲解一下典型多目标规划问题的MATLAB求解方法。例 1 利用理想点法求解我们首先根据评价函数法中的理想点法的理论基础，按照理想点法的求解思路分别对两个单目标规划问题P1 , P2 进行求解：求解 P 的 MATLAB的代码和相应的运行结果为：1算法：c=2;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)结果：x =0.00006.0000fval =-18.0000于是可知。当

18、x10,6 T 时，单目标线性规划P1 的最优函数值为f1*18 。求解 P2 的 MATLAB的代码和相应的运行结果为：算法：c=-5;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)结果：Optimization terminated.x =4.00000.0000fval =-20.0000于是可知，当 x24,0 T 时，单目标线性规划P2 的最优函数值为 f 2*20 。由上述两个单目标线性规划的求解结果可知x2 x2 ，因而 f1* , f 2*18, 20 是一个不可能达到的理想点，因而我们构造如下评价函数：构造描述该评价函数的

19、M-函数文件 objfun.m如下：function f=objfun(x)f=sqrt(2*x(1)-3*x(2)+18)2+(5*x(1)+3*x(2)-20)2);然后用非线性规划的方式求解上述问题：算法：A=3 2;1 1;b=12;8;lb=0;0;x0=0;0;x,fval,exitflag=fmincon(objfun,x0,A,b,lb,)结果：Active inequalities (to within options.TolCon = 1e-006):lowerupperineqlinineqnonlin1x =0.02355.9647fval =1.9941exitfla

20、g =5由运行结果可知在该评价函数标准之下，问题的最优解为： x*0.0235,5.9647 T 此时 ， 各 目 标 函 数 的 取 值 为 ：f1*17.8471, f 2*18.0118 。 它 与 理 想 点f1* , f 2*18, 20 在评价函数标准下的最小距离为1.9941 。例 2利用评价函数中的线性加权和法求解如下多目标规划问题：其中权系数为10.8,20.2 。建立线性加权和法的评价函数为：将相应的权系数代入上式即整理出目标函数f ( x) 为： f (x)x121.2x221.4x32于是建立目标函数的M-函数文件 objfun.m ：function f=objfun

21、(x)f=x(1)2+1.2*x(2)2+1.4*x(3)2;由于目标函数非线性函数且具有线性等式约束和边界约束，因而我们调用MATLAB中求解非线性规划的fmincon 函数对此问题进行求解，同时注意如果只考虑第一个目标函数，由这种特殊形式，即在设计变量的和为一定值，需要求其平方和的最小值时，最优解必然是当这几个设计变量的值相等时取得，于是我们可以将这个解设为问题的初始点，开始迭代。算法：Aeq=1 1 1;beq=3;lb=0;0;0;x0=1;1;1;x,fval=fmincon(objfun,x0,Aeq,beq,lb,)结果：No active inequalities.x =1.1

22、7760.98120.8412fval =3.5327x1*1.1776结果说明，问题的最优解为：x*x2*0.9812 , f ( x* )3.5327x3*0.8412我们在求解多目标规划问题时，可以采用评价函数法中的最大最小法，而MATLAB也为这种方法提供了专门的求解函数fminimax ，在讲解这方面的例题之前，我们首先介绍一下 MATLAB优化工具箱中所提供的最大最小法的求解函数fminimax 。最大最小法问题的MATLAB标准形式为：函数 fminimax 的调用方式和其他的最优化函数类似， 其中所涉及的输入参数和输出参数的含义与非线性规划的求解函数 fmincon 类似，使用

23、方法也基本相同，细节问题读者可以参考 MATLAB的帮助文件。例 3 求解最大最小问题：首先建立描述目标函数的M-函数文件 objfun.m ，注意到一共有五个目标函数，所求目标为这五个函数最大值中的最小值，代码如下：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;然后设置求解的初始点为x0=0;0，调用 fminimax 求解该问题。算法：x0

24、= 0; 0;x,fval,maxfval = fminimax(objfun,x0)结果：Local minimum possible. Constraints satisfied.fminimaxstoppedbecausethepredictedchangeintheobjectivefunctionislessthanthedefaultvalueofthefunctiontoleranceandconstraintsweresatisfiedtowithinthedefaultvalueoftheconstrainttolerance.Active inequalities (to

25、within options.TolCon = 1e-006):lowerupperineqlinineqnonlin15x =4.00004.0000fval =0.0000-64.0006 -1.9999 -8.0000 -0.0000maxfval =2.6897e-008上述结果说明当 x1 4, x24 时，目标函数 fi (x) i1,2, ,5 的最大值达到最小，这一组的函数值为0.0000 ，-64.0006 ，-1.9999 ，-8.0000，-0.0000 ，于是最大值为 0。多目标规划的应用投资问题（全国大学生数学建模竞赛试题）假设市场上有 n 种资产，比如股票、债券等可

26、以供投资者选择， 某公司有数额为M的一笔相当大的资金可用作一个时间的投资。通过财务人员对Si 种资产进行评估，大概可以估算出在这一时期内购买资产Si 的平均收益率为ri ，并预测出购买Si 的损失率为 qi 。考虑到投资越分散，总的风险越小，公司决定当用这笔资金购买若干种资产时，总体风险可用所投资的 Si 中的最大一个风险来度量。购买 Si 要付交易费，费率为 pi ，并且当购买额不超过给定值 ui 时，交易费按购买ui 计算（不买当然无须付费） 。另外，假定同期银行存款利率是r0 ，且既无交易费又无风险 ( r0 5) 。已知 n4 时的相关数据如下表所示：表 1投资各种资产的参数值ui （

27、元）282.51103211.52198235.54.552252.66.540试给该公司设计一种投资组合方案，即用给定的资金M ，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小。（）投资问题的建模为了建立数学模型，首先对模型进行一些必要的假设及符号说明：(1) 模型的假设 在一个时期内所给出的 ri ， qi ， pi 保持不变。在一个时间内所购买的各种资产( 如股票、证券等 ) 不进行买卖交易， 即在买入后不再卖出。 每种投资是否收益是相互独立的。 在投资过程中，无论盈利与否必须先付交易费。(2) 符号说明M ( 元 ) ：公司现有投资总金额；Si , i0,1,

28、 n：欲购买的第 i 种资产种类（其中 i 0 表示存入银行）：xi , i0,1, n：公司购买 Si 的金额；ri , i0,1, n：公司购买 Si 的平均收益率；qi , i0,1, n：公司购买 Si 的平均损失率；pi , i0,1, n：公司购买 Si 超过 ui 时所付交易费率。下面来建立模型。设购买Si 的金额为 xi ，所付的交易费 ci (xi ) ，则由于投资额 M 相当大，所以总可以假定对每个Si 的投资 xiui 。这时上面的大括号公式可简化为： ci( xi) pixi(i1,2, n)对 Si 投资的净收益为： Ri( xi)ri xici ( xi )ri p

29、i xi对 Si 的风险为： Qi (xi )qi xi对 Si 投资所需资金为投资金额xi 与所需的手续费 ci ( xi ) 之和，即：当购买 Si 的金额为 xi (i0,1,2, n) ，投资组合 x ( x0 , x1 , xn ) 的净收益总额为：整体风险为：( )max(xi) maxqi(xi)Q x1 inQi1i nn资金约束为：f i ( xi )Mi0根据题目要求，以净收益总额R( x) 最大，而整体风险 Q( x) 最小为目标建立模型如下：很显然，这是一个多目标规划问题。（）投资问题的求解在此我们采用主要目标法对该问题进行求解，即根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。在上述例子中如果以收益为主要目标，则可以固定风险水平，给定风险一个界限a ，讲问题转化称为求最大风险不超过a 时的最大收益，即下面的线性规划模型：nmaxripixii0s.t.qixiMai1,2, , nn1pi xiMi 0xi0,i1,2, n（ 1）若投资者希望总盈利至少达到水平K 以上，则可以在风险最小的情况下寻找相应的投资组合，从而将原模型转化成为下列的线性规划模型进行求解：minmax qi