《整数规划和多目标规划模型》由会员分享，可在线阅读，更多相关《整数规划和多目标规划模型（24页珍藏版）》请在金锄头文库上搜索。
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 =cTxs.t. Ax 兰 bAeq x = beqlb 兰 xEubXi KO(i=1,2,，n) xj取整数(j M)在上述标准问题中，假设x为n维设计变量，且问题具有不等式约束 mh个， 等式约束m2个，那么：c、x均为n维列向量，b为维列向量，beq为m2维列 向量，A为m! n维矩阵，Aeq为m2 n维矩阵。在该函数中，输入参数有 c,A,b,Aeqbeqlb,ub,M和TolXInteger。其中c为 目标函数所对应设计变量的系数，A为不等式约束条件方
3、程组构成的系数矩阵，b为不等式约束条件方程组右边的值构成的向量。Aeq为等式约束方程组构成的系数矩阵，beq为等式约束条件方程组右边的值构成的向量。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为整数规
4、划问题的目标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量。例1求解整数规划问题：max f = x1x2s.t.4x - 2x2 - 1|4% 十 2x2 兰 112X2 z 1x1, 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.50
5、002.5000fval =-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 = beqx = 01在上述模型中，目标函数f需要极小化，以及需要满足的约束条件，不等式 约束一定要化为形式为假设X为n维设计变量，且问题具有不等式约束m
6、i个，等式约束m2个，那么: c、x均为n维列向量，b为mi维列向量，beq为m?维列向量，A为mi n维矩阵, 他为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,Ae
7、q,Beq,x0,options)x,fval = bintprog()x,fval,exitflag = bintprog()x,fval,exitflag,output = bintprog()命令详解1) x = bintprog(f)该函数调用格式求解如下形式的0-1规划问题mins.t.f 二 CT Xx = 0,12)x = bintprog(c,A,b)该函数调用格式求解如下形式的0-1规划问题mins.t.f = cT XAx乞bx 二 0,13)x = bintprog (c,A,b,Aeq,beq)该函数调用格式求解如下形式的0-1规划问题:mins.t.Tf c xAx
8、_ bAeq x = beqX = 0,14)x = bintprog (c,A,b,Aeq,beq,x0)该函数调用格式求解如下形式的0-1规划问题minst.f = cTxAx汕AeqX - beqx0,如果初始解x=0,1在前一个调用格式的基础上同时设置求解算法的初始解为x0不在0-1规划问题的可行域中，算法将采用默认的初始解5)x = bintprog (c,A,b,Aeq,beq,x0,options)用options指定的优化参数进行最小化。可以使用optimset来设置这些参数上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出 参数，则可以参照下面的调用格式：x,f
9、val = 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 =n21133124X Xij =1 (j =1,2，n ).22163223 一n nfEjXji 4Xj =0或 1(12,3,4)i =1,2/
10、 ,n; j =1,2，nX14，于为了程序的可读性，我们用一维下标来表示设计变量，即用X1X4表示X11X13X16表示X41X44用 X5 X8 表示X21X24，用X9X12表示X31X34，用是约束条件和目标函数分别为：X + x2 +x3 + x4 = 1X5 *X6 *X7 +X8X9 *X10 +X11 +X12X13 *X14*x15 +x16 X1 + X5 + X9 + X13 = 1X2 f +X10 +X14 =1X3 +X7 +X11 +X15 =1X4 + X8 + X12 + X16 = 1Xi =0,1 (i =1,2,16)-E11X1 E12X2 E13X3
11、 E14X4 E21X5 E22X6 E44X16算法: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 00 0 00 000 00 1 11 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
12、0 0 1 0 0 0 1； ；beq=ones(1,8);x,fval=bintprog(c,Aeq,beq);B=reshape（x,4,4）; %由于x是一列元素，为了使结果更加直观，故排成与效率矩阵E相对应的形式Bfval结果：Optimization terminated.ans =0100001010000001fval85整数规划的应用一一组件配套问题某机械产品需要由三个工厂开工一起生产后组装完成。每件机械需要4个组件1和3个组件2。生产这两种组件需要消耗两种原材料 A和B。已知这两种 原材料的供应量分别为400kg和600kg。由于三个工厂的生产条件和拥有设备工艺条件不同，每个
13、工厂生产组件的 能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量 的组件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 9x1 600 然后再来分析三个工厂零件生产的情况，三个工厂生产的组件1的数量分别为8x7x2和9x3，故组件1的总数为：Q1 =8治+7x2 +9x3同理，组件2的总数为：Q 6x1 9x2 5x3下一步是分析目标函数，该问题要求的不是生产的各种组件总数最多，而 是要求产品的配套数量最大，即能组成的机械数目最多。问题中已经给出了该 种机械中两种组件的配比为 4:3,故组件1所能成套的数目Ti满足约束条件：Qi 8xi +7X2 +9x3Ti44同理，组件2所能成套的数目T2满足约束条件：丁2乞念二时 9X2 5X3
