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

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

2、lag=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXlnteger)该函数解决的整数规划问题为：min f 二 cT xs.t.Ax 三 blb 辽 x < ubxi _ 0 (i = 1,2, ,n)xj取整数(j M)在上述标准问题中，假设x为n维设计变量，且问题具有不等式约束 m个,等式约束m2个，那么：c、x均为n维列向量，b为m维列向量，beq为m?维列 向量，A为mi n维矩阵，Aeq为m? n维矩阵。在该函数中，输入参数有 c,A,b,Aeqbeqlb,ub,M和TolXInteger。其中c为 目标函数所对应设计变量的系数，A为不等式约束条件方程组

3、构成的系数矩阵，b为不等式约束条件方程组右边的值构成的向量。Aeq为等式约束方程组构成的系数矩阵，beq为等式约束条件方程组右边的值构成的向量。lb和ub为设计变 量对应的上界和下界。M为具有整数约束条件限制的设计变量的序号，例如问 题中设计变量为xX2,，冷，要求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为整数规划问题的目

4、标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量。例1求解整数规划问题：max f = x1x2s.t.4x - 2x2 - 1|4x十 2x2 兰 112x2 z 1、x1,x 0，且取整数值算法：C=-1;-1;A=-4 2;4 2;0 -2;b=-1;11;-1;lb=O；O；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.50

5、00fval =-4.0000x1 =%整数规划的最优解21fval2 =-3.0000(二)用MATLAB求解0-1规划问题在MATLAB优化工具箱中，提供了专门用于求解0-1规划问题的函数bintprog,其算法基础即为分枝界定法，在 MATLAB中调用bintprog函数求解 0-1规划时，需要遵循 MATLAB中对0-1规划标准性的要求。0-1规划问题的MATLAB标准型min f =cTxst.Ax 兰 b*Aeqx = beq、x = 0,1在上述模型中，目标函数f需要极小化，以及需要满足的约束条件，不等式 约束一定要化为形式为假设x为n维设计变量，且问题具有不等式约束 m个，等式

6、约束m2个，那么: c、x均为n维列向量，b为mi维列向量，beq为m?维列向量，A为m n维矩阵, 代q为m2 n维矩阵。如果不满足标准型的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似。0-1规划问题的MATLAB求解函数MATLAB优化工具箱中求解0-1规划问题的命令为bintprog bintprog的调用格式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

7、,x0,options)x,fval = bintprog()x,fval,exitflag = bintprog()x,fval,exitflag,output = bintprog()命令详解1) x = bintprog(f)该函数调用格式求解如下形式的0-1规划问题2)x = bintprog(c,A,b)f .mins.t.f 二 CT Xx = 0,1该函数调用格式求解如下形式的0-1规划问题min« s.t.f = cT xAx < bx =0,13)x = bintprog (c,A,b,Aeq,beq)该函数调用格式求解如下形式的0-1规划问题:mins.t.

8、f 二 CTXAx _ bAeq x = beqx =0,14)x = bintprog (c,A,b,Aeq,beq,x0)该函数调用格式求解如下形式的0-1规划问题minst.Tf c xAx汕Aeq X = beqx0,如果初始解x=0,1在前一个调用格式的基础上同时设置求解算法的初始解为x0不在0-1规划问题的可行域中，算法将采用默认的初始解5)x = bintprog (c,A,b,Aeq,beq,x0,options)用options指定的优化参数进行最小化。可以使用optimset来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出 参数，则可以参照下面

9、的调用格式：x,fval = bintprog()在优化计算结束之时返回整数规划问题在解x处的目标函数值fvalx,fval,exitflag = bintprog()在优化计算结束之时返回exitflag值，描述函数计算的退出条件x,fval,exitflag,output = bintprog()在优化计算结束之时返回结构变量output例2：求解0-1规划问题maxs.t.n_20123326Z Xij =1 (i =1,2，n)22152923j生E =n21133124Z Xij =1 (j =1,2，n).22163223(1,2,3,4) i=1,2,，n;j=12, ,nn n

10、f EijXji 4 j 4i 4xij = 0或1为了程序的可读性,我们用一维下标来表示设计变量,即用X1 X4表示X11用 X5X8表示X21X24，用 X9 X12表示X31 X34，X13 X16 表:示 X41 X44，于是约束条件和目标函数分别为:X<| + x2 + x3 + x4 = 1X5 *X6 *X7 +X8X9 *X1o +X11 +X12 二1X13 *X14*x15+x16X1 + X5 + X9 + X13 = 1X2 f +X10 +X14 =1X3 +X7 +X11 +X15 =1X4 +X8 +X12 +为6 =1Xi =0,1 (i =1,2/ ,1

11、6)f 二E11X1-E12X2-E13X3-E14X4- E21X5 E22X6 E44X!6算法:c=20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23;Aeq=1 1 11 0 00 000 00 0 00 0;0 0 00 1 11 100 00 0 00 0;0 0 00 0 00 011 11 0 00 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

12、 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是一列元素，为了使结果更加直观，故排成与效率矩阵E相对应的形式B'fval结果：Optimization terminated.ans =0100001010000001fval85整数规划的应用一一组件配套问题某机械产品需要由三个工厂开工一起生产后组装完成。每件机械需要4个组件1和3个组件2。生产这两种组件需要消耗两种原材料 A和B。已知这两种 原材料的供应量分别为400

13、kg和600kg。由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的 能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量 的组件1和组件2,其具体的数据如表所示。表11-2各工厂生产能力和消耗原材料的数据表每个工厂消耗原材料的数量（公斤）每个工厂各组件的生产能力 （件数）A材料B材料组件1组件2工厂19786工厂261079工厂34995现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配 套数达到最大？(I)组件配套问题的建模设Xi、X2和X3是三个工厂分别开工的次数，将其作为该问题的设计变量。由 于每个工厂开工一次都是配套生产，故每次开工消耗的原

14、材料一定，且生产的 组件数也是一定的。在这个假设的前提之下，我们可以得出该问题的目标函数 和约束条件。因为原材料的总量是有限的，根据工厂的开工次数，可得工厂1将消耗A材 料9xi，工厂2将消耗A材料6X2，工厂3将消耗A材料4x3，故有约束条件：9x1 6x2 4x3 _ 400同理，对于材料B的总量约束条件可以表达为：7x1 10x2 - 9x3 一 600 然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1的数量分别为8x7x2和9x3，故组件1的总数为：Q8x1 7x2 9x3同理，组件2的总数为：Q 6 x19 x2 5x3下一步是分析目标函数，该问题要求的不是生产的各种组件总数

15、最多，而 是要求产品的配套数量最大，即能组成的机械数目最多。问题中已经给出了该 种机械中两种组件的配比为 4:3,故组件1所能成套的数目Ti满足约束条件：丁 w Qi8x1+7x2+9x34同理,因而,4组件2所能成套的数目T2满足约束条件：T2乞°2 = 6x1 9x2 5x333所能组成的成品机械的数目f应该为£和T2中的较小值，即：f =mi n( T1 ,T?)那么，我们求解的目标即是使得f能够尽可能大，可以看出，这种形式并不是有关设计变量的线性函数，我们需要对其进行转化，此时我们可以令一个人工设计变量等于目标函数值，则有：X4二min(T|,T2)在该假设下，一定

16、满足关系式：_X4且T2 -X4结合约束关系，对T,的约束可以表示为：xTQ8Xi 7X2 9X344同理，对T2的约束可以表示为：x4岂T2岂°2 = 6X1 饥 5X333对的上述关系进行整理，可以得到关系：-8洛-7x2 -9x3 - 4x4 _ 0同理对T2也可以得到不等式关系为：- 6xi - 9X2 - 5X3 3X4岂0上面两个式子即为由组件的配比数得到的关于组件数目的约束条件，此时问题 的目标就是如何使得X4取到最大值，由于开工的次数一定是一个非负整数，故 也是一个约束条件，决定了该问题是一个纯整数规划问题。结合前面给出的原 材料约束，可以得到如下的数学模型：max

17、f =x4s.t. 9为 +6x2 +4x3 兰 4007% +10x2 +9x3 兰 600一8为7x2 9x3 +4x4 兰 0一6为9x2 5x3 +3x4 兰 0、xi > 0且取整数值(i= 1,2,3,4)(U)组件配套问题的求解利用§. 1节中给出的MATLAE函数对此问题求解，代码和运行结果如下：算法：%目标函数所对应的设计变量的系数，为转化为极小，故取原目标函数的相反数f=0;0;0;-1;%不等式约束A= 96 4 0;7 10 9 0;-8 -7 -9 4;-6 -9 -5 3;b=400;600;0;0;% 边界约束，由于无上界，故设置 ub=Inf;I

18、nf;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 处，原目标函数值的相反数-141.000exitflag= 算法终止指示变量，说明问题收敛到了最优解 x1由运行结果可知，工厂1、2和3需要分别开工18、15和36次，这样所能生产出来的

19、成套的机械为 141 件。2 多目标规划的 MATLAB 求解方法(一) 多目标规划的MATLA求解由于多目标规划中的求解涉及到的方法非常多， 故在 MATLAB 中可以利用不同的函数进行求解，例如在评价函数法中我们所得最后的评价函数为一线性 函数，且约束条件也为线性函数，则我们可以利用MATLAB优化工具箱中提供 的linprog函数进行求解，如果我们得到的评价函数为非线性函数，贝冋以利用 MATLAB优化工具箱中提供的fmincon函数进行求解，如果我们采用最大最小 法进行求解，则可以利用 MATLAB优化工具箱中提供的fminimax函数进行求 解。下面我们就结合理论求解的几种方法，讲解

20、一下典型多目标规划问题的 MATLAB求解方法。例1利用理想点法求解"min J (x) = 2x - 3x2minf 2 (x) = -5 - 3x2* s.t.3x + 2x2 兰 12+ x2 兰 8Xi, X2 z 0我们首先根据评价函数法中的理想点法的理论基础，按照理想点法的求解思路分别对两个单目标规划问题 Ri , R2进行求解：fi(x) =2xr _3x2 min3x1 2x2 乞 12x-i x2 空 8为，x2 _ 0nR,P2s.t.f2(x) - -5xj - 3x23x1 2x2 乞 12x-i x2 乞 8为，x2 _ 0求解(R的MATLAB的代码和相应

21、的运行结果为: 算法：c=2;-3;A=3 2;1 1;b=12;8lb=O;Ox,fval=linprog(c,A,b,lb,)结果：6.00000.0000fval =-18.0000于是可知。当为=(0,6时，单目标线性规划(R )的最优函数值为f； = 18 求解F2的MATLAB的代码和相应的运行结果为：算法：c=-5;-3;A=3 2;1 1;b=12;8lb=0;0x,fval=linprog(c,A,b,lb,)结果：Optimization terminated.4.00000.0000fval =-20.0000于是可知，当X2二4,0 T时，单目标线性规划 F2的最优函数

22、值为f2 = -20 o由上述两个单目标线性规划的求解结果可知x2 = x2 ,因而fl, f2* 4：-18,-20是一个不可能达到的理想点，因而我们构造如下评价函数：氏 h(f (x)= Jifi(x) +18$ +(f2(x) + 20f = J(2xi 3X2 +18丫 +(5xi +3x 20)2构造描述该评价函数的 M-函数文件objfun.m如下：function f=objfun(x)仁 sqrt(2*x(1)-3*x(2)+18)A2+(5*x(1)+3*x(2)-20)A2);然后用非线性规划的方式求解上述问题：算法：b=12;8;lb=O；O；xO=O;O;x,fval,

23、exitflag=fmincon(objfun,xO,A,b,lb,)结果：Active inequalities (to within options.TolCon = 1e-006):lowerupper ineqlin ineqnonlin1x =0.02355.9647fval =1.9941exitflag =5由运行结果可知在该评价函数标准之下，问题的最优解为： 只=(0.0235,5.9647 T 此时，各目标函数的取值为：f； = -17.8471, f； = -18.0118 它与理想点f1*, f； 1=：-18,-20在评价函数标准下的最小距离为 1.9941。例2禾I用

24、评价函数中的线性加权和法求解如下多目标规划问题：min fjx) = X： +x； + X：2 2 2min f2(x x1 +2x2+3x3s.t. % + X2 + X3 = 3_为，X2, X3 3 0其中权系数为'0.8, 2 =0.2。建立线性加权和法的评价函数为：min h f (x) = ' 1 x； x；x； I 2 x：2x| 3xf将相应的权系数代入上式即整理出目标函数f (x)为：f(x)=x：1.2x|1.4x3于是建立目标函数的 M-函数文件objfun.m：function f=objfun(x)f=x(1)A2+1.2*x(2)A2+1.4*x(3

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

26、7结果说明，问题的最优解为:*X21.17760.98120.8412 一f(x*) = 3.5327我们在求解多目标规划问题时，可以采用评价函数法中的最大最小法，而MATLAB也为这种方法提供了专门的求解函数 fminimax，在讲解这方面的例题 之前，我们首先介绍一下MATLAB优化工具箱中所提供的最大最小法的求解函 数 fminimax。最大最小法问题的MATLAB标准形式为:'min max f, (x)xis.t. c(x)兰 0ceq(x)= 0Ax兰bAeqX = beqlb乞x乞ub函数fminimax的调用方式和其他的最优化函数类似，其中所涉及的输入参数和输出参数的含

27、义与非线性规划的求解函数fmincon类似，使用方法也基本相同，细节问题读者可以参考MATLAB的帮助文件。例3求解最大最小问题：min max f, (x)xi2 2s.t. fj(x) =2为 +x2 48xj 40x2 +3042 2 f2(x) = X1 3x2f3(x) = Xj +3x2 18f 4(X)= Xi - X2 f5(x) =X1 + X2 8首先建立描述目标函数的M-函数文件objfun.m,注意到一共有五个目标函数，所求目标为这五个函数最大值中的最小值，代码如下：function f = objfun(x)f(1)= 2*x(1)A2+x(2)A2-48*x(1)-

28、40*x(2)+304;f(2)= -x(1)A2 - 3*x(2)A2;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 = 0; 0;x,fval,maxfval = fminimax(objfun,x0)结果：Local minimum possible. Constraints satisfied.fminimax stopped because the predicted change in the objective func

29、tionis less than the default value of the function tolerance and constraintswere satisfied to within the default value of the constraint tolerance.vstopping criteria details>Active inequalities （to within options.TolCon = 1e-006）:lowerupper ineqlin ineqnonlin15x =4.00004.0000fval =0.0000-64.0006-

30、1.9999-8.0000-0.0000maxfval =2.6897e-008上述结果说明当Xj = 4, X2 = 4时，目标函数fi （x） i = 1,2/ ,5的最大值达到 最小，这一组的函数值为 0.0000, -64.0006, -1.9999, -8.0000, -0.0000,于是最 大值为0。多目标规划的应用一一投资问题（全国大学生数学建模竞赛试题）假设市场上有n种资产，比如股票、债券等可以供投资者选择，某公司有数额为M的一笔相当大的资金可用作一个时间的投资。通过财务人员对Si种资产进行评估，大概可以估算出在这一时期内购买资产Si的平均收益率为ri，并预测出购买Si的损失率

31、为qi。考虑到投资越分散，总的风险越小，公司决定当用这 笔资金购买若干种资产时，总体风险可用所投资的Si中的最大一个风险来度量。购买Si要付交易费，费率为Pi，并且当购买额不超过给定值Ui时，交易费 按购买Ui计算（不买当然无须付费）。另外，假定同期银行存款利率是ro，且既 无交易费又无风险（r0 = 5%）。已知n = 4时的相关数据如下表所示：表1投资各种资产的参数值Sri(%)qi (%)Pi (%)Ui (元)S282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使

32、净收益尽可能大，而总体风险尽可能小。(I) 投资问题的建模为了建立数学模型，首先对模型进行一些必要的假设及符号说明：(1) 模型的假设 在一个时期内所给出的ri， qi， Pi保持不变。 在一个时间内所购买的各种资产(如股票、证券等)不进行买卖交易，即 在买入后不再卖出。 每种投资是否收益是相互独立的。 在投资过程中，无论盈利与否必须先付交易费。(2) 符号说明M (元)：公司现有投资总金额；S, i =0,1,，n :欲购买的第i种资产种类(其中i = 0表示存入银行)：人,(i =0,1,n ):公司购买S的金额；r,(i =0,1，n ):公司购买S的平均收益率；qi,(i =0,1，,

33、n ):公司购买S的平均损失率；Pi, i =0,1/ ,n ：公司购买S超过Ui时所付交易费率。F面来建立模型。设购买Si的金额为Xi，所付的交易费g (xj，则0Xj = 0PiUj0 <Xi <Uj(i =1,2,，n)Ci(X=<PiXjXi XUig(Xo) =0由于投资额M相当大，所以总可以假定对每个Si的投资Xj 7。这时上面的大括号公式可简化为：q(Xi) = PM (i =1,2,n)对S投资的净收益为：Ri (xj = AXi -G(Xi) =5 - Pi X对S的风险为：Qi (xj =qiXi对S投资所需资金为投资金额Xi与所需的手续费g (xj之和，

34、即：fi (XXi Ci (Xi) = 1 Pi Xi当购买S的金额为Xi (i =0,1,2，,n)，投资组合x = (Xo,Xi，x)的净收益总额为：nR(x)八 Ri(Xi)i=0整体风险为：Q(x)二 maxQdxJ 二 maxq'xj1n资金约束为：7 fi(Xi)二Mi -0根据题目要求，以净收益总额 R(x)最大，而整体风险Q(x)最小为目标建立模型如下：(n、min(n 一 Pi X maXqixi )J i=0丿n< s.t. Z (1 十 Pi k = Mi =0Xi »0,i =1,2广,n很显然，这是一个多目标规划问题(U)投资问题的求解在此我们

35、采用主要目标法对该问题进行求解，即根据问题的实际情况，确 定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一 定的界限值。这样就可以把次要目标作为约束来处理，于是就将原来的多目标 问题转化为一个在新的约束下的单目标最优化问题。在上述例子中如果以收益为主要目标，则可以固定风险水平，给定风险一 个界限a ,讲问题转化称为求最大风险不超过 a时的最大收益，即下面的线性规 划模型："nmax Z （仃-Pi Xis.t.qjXj 兰 Ma （i =1,2；八,n ）nX （1 + Pi Xi = Mi =0、Xi KO,i =1,2,n（1）若投资者希望总盈利至少达到水平K以上，则可以在风险最小的情况下寻找相应的投资组合，从而将原模型转化成为下列的线性规划模型进行求解：'min （max（qXj ）xins.t. Z （n p Ri 启 K* znZ （1 + Pi ）Xi = Mi=0IXi zo,i =1,2,n（2）根据上面的分析，我们利用主要目标法建立了该问题的多目标规划模型，进而转化成为了线性规划模型