整数规划与matlab吴颖丹

建模算法（⼆）——整数规划⼀、概述1、定义：规划中变量部分或全部定义成整数是，称为整数规划。

2、分类：纯整数规划和混合整数规划。

3、特点：（1）原线性规划有最优解，当⾃变量限制为整数后：a、原最优解全是整数，那最优解仍成⽴b、整数规划没有可⾏解c、有可⾏解，但是不是原最优解4、求解⽅法分类（1）分⽀定界法（2）割平⾯法（3）隐枚举法（4）匈⽛利法（5）蒙特卡洛法⼆、分⽀定界法1、算法如下（求解整数规划最⼤化问题）MATLAB实现function r=checkint(x)%判断x(i)是不是整数了。

是的话r(i)返回1，不是的话，返回0%输⼊参数：x X向量%输出参数：r R向量for i=1:length(x)if(min(abs(x(i)-floor(x(i))),abs(x(i)-ceil(x(i))))<1e-3)r(i)=1;elser(i)=0;endendfunction val=isrowinmat(arow,mat)%⽤来判断mat中是否包含与arow⼀样的向量%输⼊变量：arow 向量% mat 矩阵%输出变量：val 1表⽰有，0表⽰没有val=0;rows=size(mat,1);for i=1:rowstemp=(mat(i,:)==arow);if length(find(temp==0))==0val=1;return;elseval=0;end;end% [x,fval,exitflag,output,lambda]=lpint(ifint.f,A,b,Aeq,beq)% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb)% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub)% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0)% [x,fval,exitflag,output,lambda]=lpint(ifint,f,A,b,Aeq,beq,lb,ub,x0,options)if nargin<10, options=[]; endif nargin<9, x0=[]; endif nargin<8, ub=inf*ones(size(f)); endif nargin<7, lb=zeros(size(f)); end[x,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,beq,lb,ub,x0,options);if exitflag<=0 %表⽰线性规划没有最优解returnendv1=find(ifint==1); %找到需要整数规划的变量的下标temp=x(v1);%如果不是要求整数规划的就可以返回了。

P120第1（1）题求整数规划问题原问题A松弛问题Ba=[3 4 1 1 0 104 2 3 0 1 80 -4 -3 0 0 0]zuiyoujie =value =最优解不是整数解，对问题B关于x1进行分支B1a=[4 1 1 0 0 102 3 0 1 0 81 0 0 0 1 2-4 -3 0 0 0 0]zuiyoujie =24/32/3value =12B2a=[4 1 1 0 0 102 3 0 1 0 81 0 0 0 -1 3-4 -3 0 0 0 0]无可行解对问题B1关于x2进行分支B11a=[4 1 1 0 0 0 102 3 0 1 0 0 81 0 0 0 1 0 20 1 0 0 0 1 1-4 -3 0 0 0 0 0]zuiyoujie =2111value =11B12a=[4 1 1 0 0 0 102 3 0 1 0 0 81 0 0 0 1 0 20 1 0 0 0 -1 2-4 -3 0 0 0 0 0] zuiyoujie =0 value =10P120第1（3）题求整数规划问题原问题A松弛问题Ba=[3 54 1 0 244 25 0 1 130 -20 -10 0 0 0]zuiyoujie =value =96最优解不是整数解，对问题B关于x1进行分支B1a=[5 4 1 0 0 242 5 0 1 0 131 0 0 0 1 4-20 -10 0 0 0 0]zuiyoujie =41value =90B2a=[5 4 1 0 0 242 5 0 1 0 131 0 0 0 -1 5-20 -10 0 0 0 0]无可行解该整数线性规划问题的最优解就是（4，1），最优值就是90P120第2（1）题求整数规划问题原问题A松弛问题Ba=[3 -3 -1 1 0 0 -24 -1 -4 0 1 0 -55 -3 -2 0 0 1 -70 4 5 0 0 0 0]用对偶单纯形法得到的结果：zuiyoujie =value =最优解不是整数解最后一张单纯形表为根据第三行得到一个新约束条件：00 1 02 0 1 0 01 1 0 0 06 0 0 0 10 0 0 0 0 ]zuiyoujie =value =最优解不是整数解，增加新约束，得到新规划问题a=[3 0 0 1 2/3 0 -11/6 0 17/32 0 1 0 -1/3 0 1/6 0 2/31 1 0 0 1/3 0 -2/3 0 7/35 0 0 0 1/3 1 -5/3 0 4/37 0 0 0 -1 0 -1 1 -10 0 0 0 1/3 0 11/6 0 -38/3]zuiyoujie =21511value =13最优解已经是整数解，这就是整数规划问题的最优解。

名字由和两词的前个字母MATLAB Matrix Laboratory 3组合而成。

起于世纪年代后期，现在研究和设计中，2070被认为是进行高效研究、开发的首选软件工具。

MATLAB 在国际学术界，已经被确认为准确、可靠的科学MATLAB 计算标准软件。

在数学上提供了大量的优化计算命令。

线性规MALAB 划中，提供了相关函数，但是对于变量取整数的MATLAB 线性规划，即线性整数规划，并没有提供相关函MATLAB 数。

线性整数规划是介于计算机算法和最优化方法中的问题，在实际工程中有着广泛的应用。

本文通过计算机算法中分支限界法的思想解决此类方法。

线性整数规划的求解，是离散型优化问题求解，即指在有限多个可行方案中寻找一个符合目标的方案，常用的技术之一是将整个搜索的范围划分为若干个互不重叠并且完备的子范围，试图找到两个明确结论之一：所要找的最优解(1)肯定不在这个子范围内，如已知所要找的最小值不超过而a,在此范围内最小值超过则问题的解不在此范围内；原问a,(2)题的最小值在该子范围内，则找到该最小值，或者继续划分该子范围，直到找到最小值为止，这样原问题的解就自然得到。

解线性整数规划是一类具体的离散优化问题。

离散优化的问题都可以使用穷举法，在线性整数规划上，这个解空间很大。

显然在实际使用中，使用穷举法时间消耗很大。

在计算机的计算过程中，通常使用回朔的方法，然而仍然需要遍历整个树，然后在所有满足条件的值中找到最优的值。

树的遍历是个递归过程，如果使用递归算法，在每次进行递归调用中，需要保存当前的状态和当前的所有变量，仍然需要很大的空间和时间消耗。

本文通过堆栈的方式，改进递归过程，这将改进整个算法的执行效率。

分支限界法的算法思想1 分支限界法是一种在问题的解空间树上搜索问题界的算法，其目的是找出满足约束条件的一个解，或者是在满足约束条件的解中找出使目标函数值达到极大或极小的解，即最优解。

分支限界法以广度优先或者以最小耗费优先的方式搜索解空间树，分支限界法的策略是，在扩展结点处，先生成其所有的儿子结点，以加速搜索进程，在每一活结点处，计算一个函数值，并根据这些已经计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索向着解空间树上最优解的分支推进，以便尽快找出一个最优解。

MATLAB优化算法与工具介绍引言近年来，计算机科学和工程领域取得了快速发展，求解优化问题变得越来越重要。

MATLAB是一种功能强大的高级计算软件，提供了丰富的数学和工程计算工具。

本文将介绍MATLAB中的优化算法和工具，帮助读者对其有更深入的了解和运用。

一、MATLAB优化工具箱MATLAB优化工具箱是MATLAB软件的一个重要组件，它集成了多种优化算法和工具，为用户提供了高效且灵活的求解优化问题的能力。

优化工具箱包括了线性规划、非线性规划、整数规划、二次规划等多种优化算法。

1. 线性规划线性规划是一类特殊的优化问题，其目标函数和约束条件都是线性的。

MATLAB提供了函数linprog来求解线性规划问题。

通过指定目标函数的系数、约束条件的矩阵和边界，linprog可以找到满足约束条件下使目标函数最小或最大化的解。

2. 非线性规划非线性规划是指目标函数和/或约束条件中至少存在一个非线性函数的优化问题。

MATLAB提供了函数fmincon用于求解非线性规划问题。

fmincon可以接受不等式和等式约束条件，并且可以指定变量的边界。

通过调用fmincon，用户可以有效地求解各种非线性规划问题。

3. 整数规划整数规划是一类在决策变量上加上整数约束的优化问题。

MATLAB提供了两种用于求解整数规划的函数，分别是intlinprog和bintprog。

这两个函数使用了不同的求解算法，可以根据问题的特点来选择合适的函数进行求解。

4. 二次规划二次规划是目标函数和约束条件都是二次的优化问题。

MATLAB提供了函数quadprog来求解二次规划问题。

用户需要指定目标函数的二次项系数、线性项系数和约束条件的矩阵。

通过调用quadprog，用户可以高效地求解各类二次规划问题。

二、MATLAB优化算法除了优化工具箱提供的算法，MATLAB还提供了一些其他的优化算法，用于求解特定类型的优化问题。

1. 递归算法递归算法是一种通过将问题拆分为较小的子问题并逐步解决的优化方法。

matlab 最优路径算法
在MATLAB中，可以使用一些优化算法来求解最优路径问题，其中常用的有以下几种：
1. 线性规划（Linear Programming）：可以使用MATLAB中
的`linprog`函数来求解线性规划问题，可以将最优路径问题转
化为线性规划问题进行求解。

2. 整数规划（Integer Programming）：如果最优路径的节点需
要是整数，可以使用MATLAB中的`intlinprog`函数来求解整
数规划问题。

3. 旅行商问题（Traveling Salesman Problem）：旅行商问题是
一个经典的最优路径问题，可以使用MATLAB中的
`travelling_salesman`函数来求解。

4. 模拟退火算法（Simulated Annealing）：模拟退火算法是一
种用于求解组合优化问题的随机搜索算法，可以使用
MATLAB中的`simulannealbnd`函数来求解最优路径问题。

5. 遗传算法（Genetic Algorithm）：遗传算法是一种求解组合
优化问题的启发式算法，可以使用MATLAB中的`ga`函数来
求解最优路径问题。

以上是一些常用的最优路径求解算法，根据具体问题的特点选择合适的算法来求解。

关于MATLAB整数规划分支定界法一、编程利用Matlab的线性规划指令:[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub)编写计算整数规划函数，输入与输出与上述指令相同分枝定界法(递归实现)function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e)%整数规划求解函数 intprog()% 其中 f为目标函数向量% A和B为不等式约束 Aeq与Beq为等式约束 % I为整数约束% lb与ub分别为变量下界与上界% x为最优解，fval为最优值%例子:% maximize 20 x1 + 10 x2 % S.T.% 5 x1 + 4 x2 <=24 % 2 x1 + 5 x2 <=13 % x1, x2 >=0 % x1, x2是整数 % f=[-20, -10];% A=[ 5 4; 2 5];% B=[24; 13];% lb=[0 0];% ub=[inf inf];% I=[1,2];% e=0.000001;% [x v s]= IP(f,A,B,I,[],[],lb,ub,,e) % x = 4 1 v = -90.0000 s = 1% 控制输入参数if nargin < 9, e = 0.00001;if nargin < 8, ub = [];if nargin < 7, lb = [];if nargin < 6, Beq = [];if nargin < 5, Aeq = [];if nargin < 4, I = [1:length(f)];end, end, end, end, end, end%求解整数规划对应的线性规划,判断是否有解 options = optimset('display','off'); [x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options);if exitflag < 0disp('没有合适整数解');x = x0;fval = fval0;status = exitflag;return;else%采用分支定界法求解bound = inf;[x,fval,status] =branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);end子函数function [newx,newfval,status,newbound] =branchbound(f,A,B,I,x,fval,bound,Aeq,Beq,lb,ub,e)% 分支定界法求解整数规划% f,A,B,Aeq,Beq,lb,ub与线性规划相同 % I为整数限制变量的向量% x为初始解，fval为初始值options = optimset('display','off');[x0,fval0,status0]=linprog(f,A,B,Aeq,Beq,lb,ub,[],options);%递归中的最终退出条件%无解或者解比现有上界大则返回原解 if status0 <= 0 || fval0 >= bound newx = x;newfval = fval;newbound = bound;status = status0;return;end%是否为整数解,如果是整数解则返回 intindex = find(abs(x0(I) -round(x0(I))) > e);if isempty(intindex)newx(I) = round(x0(I));newfval = fval0;newbound = fval0;status = 1;return;end%当有非整可行解时，则进行分支求解 %此时必定会有整数解或空解%找到第一个不满足整数要求的变量n = I(intindex(1));addA = zeros(1,length(f));addA(n) = 1;%构造第一个分支 x<=floor(x(n))A = [A;addA];B = [B,floor(x(n))];[x1,fval1,status1,bound1] =branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:) = [];B(:,end) = [];%解得第一个分支，若为更优解则替换，若不是则保持原状status = status1;if status1 > 0 && bound1 < boundnewx = x1;newfval = fval1;bound = fval1;newbound = bound1;elsenewx = x0;newfval = fval0;newbound = bound;end%构造第二分支A = [A;-addA];B = [B,-ceil(x(n))];[x2,fval2,status2,bound2] =branchbound(f,A,B,I,x0,fval0,bound,Aeq,Beq,lb,ub,e);A(end,:) = [];B(:,end) = [];%解得第二分支，并与第一分支做比较，如果更优则替换 if status2 > 0 && bound2 < boundstatus = status2;newx = x2;newfval = fval2;newbound = bound2;end二、求解利用上述指令求解下列问题:汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量小型中型大型现有量钢材(吨) 1 2 5 1000劳动时间(小时) 250 125 150 120000利润(万元) 3 5 121、若每月生产的汽车必须为整车，试制订月生产计划，使工厂的利润最大2、如果生产某一类型汽车，则至少要生产50辆，那么最优的生产计划应作何改变, 解:1f = [-3 -5 -12];A = [1 2 5;250 125 150];B = [1000 120000];I = [1:length(f)];lb = [0 0 0];[x,fval,status] = intprog(f,A,B,I,[],[],lb)答案为 x =307 344 1 fval = -2653 status =12lb = [50 50 50]答案为 x =350 200 50 fval =-2.6500e+003 status =1用分枝定界法求解整数线性规划问题%%问题的标准形式:%% min c'*x%% s.t. A*x<=b%% Aeq*x=beq%% 要求是整数%%function [y,fval]=BranchBound(c,A,b,Aeq,beq)%NL=length(c);UB=inf;LB=-inf;FN=[0];AA(1)={A};BB(1)={b};k=0;flag=0;while flag==0;[x,fval,exitFlag]=linprog(c,A,b,Aeq,beq); if (exitFlag == -2) | (fval >= UB)FN(1)=[];if isempty(FN)==1flag=1;elsek=FN(1);A=AA{k};b=BB{k};endelsefor i=1:NLif abs(x(i)-round(x(i)))>1e-7kk=FN(end);FN=[FN,kk+1,kk+2];temp_A=zeros(1,NL);temp_A(i)=1;temp_A1=[A;temp_A];AA(kk+1)={temp_A1};b1=[b;fix(x(i))];BB(kk+1)={b1};temp_A2=[A;-temp_A];AA(kk+2)={temp_A2};b2=[b;-(fix(x(i))+1)];BB(kk+2)={b2};FN(1)=[];k=FN(1);A=AA{k};b=BB{k};break;endendif (i==NL) & (abs(x(i)-round(x(i)))<=1e-7) UB=fval;y=x;FN(1)=[];if isempty(FN)==1flag=1;elsek=FN(1);A=AA{k};b=BB{k};endendendendy=round(y);fval=c*y;。

高校排课问题的整数规划模型求解摘要课表编排是一个充满冲突的过程，所开课程的上课时间、上课班级、上课地点、任课教师等多方面因素限制教学资源分配。

为了提升高校的办学效率，更好地完成教学任务，本文以教室数目作为目标，建立了以教室数目最少的目标决策模型。

在问题一中，我们以教室数目最少作为目标，对各种情况做了详细定义，巧妙地引入了0-1变量，将问题转换为以教室数目总和最少为目标的整数规划模型：Min Z=∑x i在模型的求解中，我们使用matlab，使用数据库快速插入算法，得到了完整的课程表以及结果：最小教室数目为9个，A类6间，B、C、E类各一间。

在问题二中，我们考虑到必修课的约束条件，增加了对问题一中的约束，利用问题一中类似的方法得出了结果。

对于问题三，为了使教室数目保持不变，我们将问题一、二所使用的目标函数转换为第三问的约束条件，建立了将必修课在4、5时间段出现以及周五4、5时间段出现的课时作为目标函数的模型：MIN Z=∑x s,c,l,r,t+∑x s,c,l,r,tD={5}∩Q={4,5}Q={4，5}∩LB={1}对于问题四，我们从教室（包括机房）的利用率、开课对象的上课强度、问题3的不满足率这三个方面来对问题三的结果进行了评价，并提出了一定的建议。

关键词：整数规划；目标函数；约束条件；Matlab.一、问题重述在国家对高等教育大力发展政策的激励下,高等教育事业得到了迅速发展,由于在校学生人数急剧增加,教学硬件设施增长缓慢、教师资源短缺,如何利用有限的资源,以最优形式满足教学需求成为目前急需解决的问题。

课表编排是一个充满冲突的过程，所开课程的上课时间、上课班级、上课地点、任课教师等多方面因素限制教学资源分配。

为了提升高校的办学效率，更好地完成教学任务，如何应用现代信息化技术在时间上和空间上合理分配教学资源成为亟待解决的问题。

本问题假定在某一学期18教学周内安排教学任务，每个教学周星期一至星期五安排课程，每天分为上午2个时间段（时间段1和时间段2），下午2个时间段（时间段3和时间段4），晚上1个时间段（时间段5），每个时间段2学时安排同一门课程，同一班级的不同课程不考虑课程内容之间的前后逻辑关系。

整数规划模型的Matlab程序实现作者：顾文亚孟祥瑞来源：《科技资讯》2018年第36期摘要：整数规划是线性规划的基础上，对部分或全部决策变量为整数的最优化问题的模型、算法及应用等研究，是运筹学和管理科学中应用最基本的模型之一。

大多数整数规划问题的计算求解存在实际的困难，求解一般线性规划的方法无法求解整数规划。

为加深学生的理解，提高动手能力，本文介绍了一般整数规划和0-1整数规划的Matlab命令，并给出具体的实例。

关键词：整数规划 0-1整数规划割平面法分枝定界法 Matlab中图分类号：O221.4 文献标识码：A 文章编号：1672-3791（2018）12（c）-0009-02整数规划是在线性规划的基础上，给一些或全部决策变量附加取整约束得到的。

在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。

整数规划的一种特殊情形是0-1规划，它的变量仅限于0或1[1-3]。

若按线性规划的方法来求解整数规划问题，最优解如果不是整数，似乎把已得的非整数解舍入化整就可以了。

但实际上化整后的数一般不是最优解，所以整数规划有自身特有的方法来求解。

目前比较成功又流行的方法是分枝定界法和割平面法[4，5]。

求解0-1规划的常用方法是枚举法和隐枚举法[6]，对各种特殊问题还有一些特殊方法，例如求解指派问题的匈牙利法[7，8]。

1 整数规划的Matlab函数3 结语直接调用Matlab R2014a工具箱，只须编写很简单的几行程序代码，即可实现对整数规划，包括对0-1整数规划的求解，且结果可靠，计算精度高，避免了应用其他语言程序过于复杂、调试困难等缺点，提高了计算效果。

参考文献[1] 顾文亚，孟祥瑞，陈允杰.运筹学（上）[M].镇江：江苏大学出版社，2015.[2] Ping-Qi PAN.Linear Programming Computation[M].Berlin Heidlberg：Springer Verlag，2014.[3] Williams，H.Paul.Logic and integer programming[M]. Berlin Heidlberg：Springer Verlag，2009.[4] R.E. Gomory. Outline of an algorithm for integer solutions to linear programs[J]. Bulletin of the American Mathematical Society，1958，64（5）：275-278.[5] A.H. Land， A.G. Doig.An automatic method of solving discrete programmingproblems[J].Econometrica，1960，28（3）：497-520.[6] E Balas，F Glover，S Zionts. An Additive Algorithm for Solving Linear Programs with Zero-One Variable[J]. Operations Research，1965，13（4）：517-549.[7] Harold W. Kuhn. The Hungarian Method for the assignment problem[J].Naval Research Logistics Quarterly，1955（2）：83-97.[8] Harold W. Kuhn. Variants of the Hungarian method for assignment problems[J].Naval Research Logistics Quarterly，1956（3）：253-258.[9] 温正.MATLAB科学计算[M].北京：清华大学出版社， 2017.。

function [x,y]=ILP(f,G,h,Geq,heq,lb,ub,x,id,options)global upper opt c x0 A b Aeq beq ID options;if nargin<10options=optimset({});options.Display='off';rgeScale='off';endif nargin<9,id=ones(size(f));endif nargin<8,x=[];endif nargin<7 ||isempty(ub),ub=inf*ones(size(f));endif nargin<6 ||isempty(lb),lb=zeros(size(f));endif nargin<5,heq=[];endif nargin<4,Geq=[];endupper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;ftemp=ILP(lb(:),ub(:));x=opt;y=upper;%下面是子函数function ftemp=ILP(vlb,vub)warning off all;global upper opt c x0 A b Aeq beq ID options;[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);if how <=0return;end;if ftemp-upper>0.00005 %in order to avoid errorreturn;end;if max(abs(x*ID-round(x*ID)))<0.00005if upper-ftemp>0.00005 %in order to avoid erroropt=x';upper=ftemp;return;elseopt=[opt;x'];return;end;end;notintx=find(abs(x-round(x))>=0.00005); %in order to avoid error intx=fix(x);tempvlb=vlb;tempvub=vub;if vub(notintx(1,1),1)>=intx(notintx(1,1),1)+1;tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;ftemp=ILP(tempvlb,vub);end;if vlb(notintx(1,1),1)<=intx(notintx(1,1),1)tempvub(notintx(1,1),1)=intx(notintx(1,1),1);ftemp=ILP(vlb,tempvub); end;。

作者： 顾文亚[1];孟祥瑞[1]
作者机构： [1]南京信息工程大学滨江学院,江苏南京210044
出版物刊名： 科技资讯
页码： 9-10页
年卷期： 2018年 第36期
主题词： 整数规划;0-1整数规划;割平面法;分枝定界法;Matlab
摘要：整数规划是线性规划的基础上,对部分或全部决策变量为整数的最优化问题的模型、算法及应用等研究,是运筹学和管理科学中应用最基本的模型之一。

大多数整数规划问题的计算求解存在实际的困难,求解一般线性规划的方法无法求解整数规划。

为加深学生的理解,提高动手能力,本文介绍了一般整数规划和0-1整数规划的Matlab命令,并给出具体的实例。

MATLAB中的混合整数线性规划方法在数学和计算机科学领域，混合整数线性规划是一个重要且有挑战性的问题。

它涉及到线性约束和整数变量的优化，常用于解决许多实际问题，如资源分配、生产计划和调度等。

在本文中，我们将讨论MATLAB中的混合整数线性规划方法，介绍一些基本概念和解决技巧。

首先，让我们明确混合整数线性规划的定义。

在一个混合整数线性规划问题中，我们要最小化或最大化一个线性目标函数，同时满足一系列线性约束条件。

这些约束条件可以是等式或不等式。

另外，问题中存在一些整数变量，这些变量只能取整数值。

求解混合整数线性规划的目标是找到使得目标函数取得最优值的整数解。

MATLAB提供了一套强大的工具箱，用于解决混合整数线性规划问题。

其中最常用的工具箱是Optimization Toolbox。

它包含了多种求解算法和函数，可以根据问题的特点选择合适的方法。

在MATLAB中，我们可以使用函数intlinprog来解决混合整数线性规划问题。

该函数的基本语法如下：[x, fval, exitflag] = intlinprog(c, intcon, A, b, Aeq, beq, lb, ub)其中，c是目标函数的系数向量，intcon是整数变量的索引向量，A和b是不等式约束的系数矩阵和右侧项向量，Aeq和beq表示等式约束的系数矩阵和右侧项向量，lb和ub是变量的下界和上界限制。

函数的输出包括最优解x、目标函数的最优值fval和求解器的退出标志exitflag。

在实际应用中，为了提高计算效率和求解精度，我们通常需要根据问题的特点来选择合适的求解算法和设置求解选项。

MATLAB提供了许多选项，如指定求解器、设置迭代次数和容忍度等。

此外，我们还可以通过约束条件的线性化、变量分解和割平面等技巧来改进混合整数线性规划的求解。

除了intlinprog函数，MATLAB还提供了其他与混合整数线性规划相关的函数。

例如，我们可以使用linprog函数来求解线性规划问题；使用quadprog函数来求解二次规划问题；使用bintprog函数来求解纯整数线性规划问题。

Matlab语言在整数规划中的应用林志程【期刊名称】《电脑知识与技术》【年(卷),期】2013(000)009【摘要】该文提出了用枚举法解决线性函数中的整数规划问题.应用Matlab语言的线性规划函数linprog,先取消整数限制求解;因目标函数为线性函数,它具有一致倾斜性,再求出整数规划的最优解.由于文章所提算法可以很便捷算出整数规划的最优解,因而避免了原有算法的一些困境.%This paper puts forwards that enumeration method is a solution to integer programming in linear function. The Matlab language can be used in linear programming function after the cancellation of integer limit. The integer optimization can be solved because objective function is linear function and it has consistent inclining. Some dilemma of the original algorithm can be avoided with the application of Matlab language.【总页数】3页(P2122-2124)【作者】林志程【作者单位】湖南广播电视大学,湖南长沙410004【正文语种】中文【中图分类】TP319【相关文献】1.整数规划法在流域规划项目最优开发次序中的应用 [J], 王宝红;康永辉2.关于超加性函数在整数与混合整数规划中的一些应用 [J], 张子辉3.基于遗传规划的整数线性规划问题求解算法及其在高速公路收费员排班优化中的应用 [J], 张希亮;鞠琳;赵雪平4.居住区规划中的应用数学问题的探讨：一个非线性整数规划应用计算机求解的实[J], 李大戈;许帆5.动态规划和整数规划在应急物流物资配送优化中的应用研究 [J], 英升贺;李毅鑫因版权原因，仅展示原文概要，查看原文内容请购买。

有四个人，要指派他们分别完成四项工作，每人做各项工作所消耗的时间如表所示：有四个人，要指派他们分别完成四项工作，每人做各项工作所消耗的时间如表所示：c=[15,18,21,24,19,23,22,18,26,17,16,19,19,21,23,17];a=[15,18,21,24,zeros(1,12);zeros(1,4),19,23,22,18,zeros(1,8);zeros(1,8),26,17,16,19,zeros(1,4);zeros(1,12),19,21,23,17;15,zeros(1,3),19,zeros(1,3),26,zeros(1,3),19,zeros(1,3);zeros(1,1),18,zeros(1,3),23,zeros(1,3),17,zeros(1,3),21,zeros(1,2);zeros(1,2),21,zeros(1,3),22,zeros(1,3),16,zeros(1,3),23,0;zeros(1,3),24,zeros(1,3),18,zeros(1,3),19,zeros(1,3),17];b=[24;23;26;23;26;23;23;24];A=[ones(1,4),zeros(1,12);zeros(1,4),ones(1,4),zeros(1,8);zeros(1,8),ones(1,4),zeros(1,4);zeros(1,12),ones(1,4);1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,2);0,0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,0;zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];B=ones(1,8);m=zeros(1,16);[Q,W]=bintprog(c,a,b,A,B,m)c=[15,18,21,24,19,23,22,18,26,17,16,19,19,21,23,17];a=[15,18,21,24,zeros(1,12);zeros(1,4),19,23,22,18,zeros(1,8);zeros(1, 8),26,17,16,19,zeros(1,4);zeros(1,12),19,21,23,17;15,zeros(1,3),19,ze ros(1,3),26,zeros(1,3),19,zeros(1,3);zeros(1,1),18,zeros(1,3),23,zero s(1,3),17,zeros(1,3),21,zeros(1,2);zeros(1,2),21,zeros(1,3),22,zeros( 1,3),16,zeros(1,3),23,0;zeros(1,3),24,zeros(1,3),18,zeros(1,3),19,zer os(1,3),17];b=[24;23;26;23;26;23;23;24];A=[ones(1,4),zeros(1,12);zeros(1,4),ones(1,4),zeros(1,8);zeros(1,8),o nes(1,4),zeros(1,4);zeros(1,12),ones(1,4);1,zeros(1,3),1,zeros(1,3),1 ,zeros(1,3),1,zeros(1,3);0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,z eros(1,2);0,0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,0;zeros(1,3),1 ,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];B=ones(1,8);m=zeros(1,16);[Q,W]=bintprog(c,a,b,A,B,m)Warning: The given starting point x0 is not binary integer feasible; it will be ignored.> In bintprog at 291Optimization terminated.Q =(2,1) 1(5,1) 1(11,1) 1(16,1) 1W =70即甲B,乙A,丙C,丁D最小总耗时，w=70。

整数规划_分支定界法_MATLAB程序整数规划分支定界法MATLAB程序 1.这种方法绝对能都解出答案，而且答案正确 function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub)x=zeros(n,1);x1=zeros(n,1);m1=2;m2=1;[x1,val1]=linprog(f,a,b,aeq,beq,lb,ub);if (x1==0)x=x1;val=val1;elseif (round(x1)==x1)x=x1;val=val1;elsee1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1};zl=0;zu=-val1;while (zu~=zl)for c=1:1:m2if (m1~=2)if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0};e(m1,c*2-1)={e1};e(m1,c*2)={e1};continue;end;end;x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1);s=0;s1=1;s2=1;lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7));lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0)s=1;lb1(d)=fix(x1(d))+1;if (a*lb1<=b)s1=0;end;ub2(d)=fix(x1(d));if (a*lb2<=b)s2=0;end;end;end;e1={s1,a,b,aeq,beq,lb1,ub1,[],0}; e2={s2,a,b,aeq,beq,lb2,ub2,[],0}; e(m1,c*2-1)={e1};e(m1,c*2)={e2};end;m1=m1+1;m2=m2*2;for c=1:1:m2if (cell2mat(e{m1-1,c}(1))==0) [x1,val1]=linprog(f,cell2mat(e{m1-1,c}( 2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2 mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)));e1={cell2mat(e{m1-1,c}(1)),cell2mat(e{m1-1,c}(2)),cell2mat(e{m1-1,c}(3)),cell2mat(e{m1-1,c}(4)),cell2mat(e{m1-1,c}(5)),cell2mat(e{m1-1,c}(6)),cell2mat(e{m1-1,c}(7)),x1,val1};e(m1-1,c)={e1};end;z=val1;if ((-z)<(-zl))e1={1,[],[],[],[],[],[],[],0}; e(m1-1,c)={e1};elseif (abs(round(x1)-x1)<=0.0001) zl=z;end;end;for c=1:1:m2if (cell2mat(e{m1-1,c}(1))==0) zu=cell2mat(e{m1-1,c}(9));end;end;for c=1:1:m2if (-cell2mat(e{m1-1,c}(9))>(-zu)) zu=cell2mat(e{m1-1,c}(9));end;end;end;for c=1:1:m2if (cell2mat(e{m1-1,c}(1))==0)&(cell2mat(e{m1-1,c}(9))==zu)x=cell2mat(e{m1-1,c}(8));end;end;val=zu;end;2.这种方法是课本上的程序，但是不能解题，希望高手能将它改进function [x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options) %整数线性规划分支定界法，可求解全整数线性或混合整数线性规划%y=min f'*x subject to:G*x<=h Geq*x=heq x为全整数%数或混合整数列向量%用法% [x,y]=IntLp(f,G,h)% [x,y]=IntLp(f,G,h,Geq,heq)% [x,y]=IntLp(f,G,h,Geq,heq,lb,ub) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options) %参数说明% x:最优解列向量;y:目标函数最小值;f:目标函数系数列向量% G:约束不等式条件系数矩阵;h:约束不等式条件右端列向量% Gep:约束等式条件系数矩阵;heq:约束等式条件右端列向量% lb:解的下界列向量(Default:-inf)% ub:解得上界列向量(Default:inf)% x:迭代初值列向量;% id:整数变量指标列向量，1—整数，0—实数(default:1)% options的设置请参见 optimset或linprog%例 min z=x1+4x2%s.t. 2x1+x2<=8% x1+2x2>=6% x1,x2>=0且为整数%先将 x1+x2>=6 化为 -x1-2x2<=-6%[x,y]=IntLp([1;4],[2 1;-1 -2],[8;-6],[],[],[0;0]) global upper opt c x0 A b Aeq beq ID options; ifnargin<10,options=optimset({});options.Display='off';rgeScale='off';endif nargin<9,id=ones(size(f));endif nargin<8,x=[];endif nargin<7|isempty(ub),ub=inf*ones(size(f));end ifnargin<6|isempty(lb),lb=zeros(size(f));end if nargin<5,heq=[];end if nargin<4,Geq=[];endupper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;ftemp=IntLp(lb(:),ub(:));x=opt;y=upper;%以下为子函数function ftemp=IntLp(vlb,vub)global upper opt c x0 A b Aeq beq ID options;[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);if how<=0return;end;if ftemp-upper>0.00005%in order to avoid errorreturn;end;if max(abs(x.*ID-round(x.*ID)))<0.00005if upper-ftemp>0.00005%in order to avoid erroropt=x';upper=ftemp;return;elseopt=[opt;x'];return;end;end;notintx=find(abs(x-round(x))>0.00005); %in order to avoid error intx=fix(x);tempvlb=vlb;tempvub=vub; ifvub(notintx(1,1),1)>=intx(notintx(1,1),1)+1tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;ftemp=IntLp(tempvlb,vub);end;if vlb(notintx(1,1),1)<=intx(notintx(1,1),1)tempvub(notintx(1,1),1)=intx(notintx(1,1),1);ftemp=IntLp(vlb,tempvub);end;3.这种方法是我网上搜的，也不能解题，希望高手改进function [y,fval]=BranchBound(c,A,b,Aeq,beq) NL=length(c); UB=inf;LB=-inf;FN=[0];AA(1)={A};BB(1)={b};k=0;flag=0;while flag==0;[x,fval,exitFlag]=linprog(c,A,b,Aeq,beq);if (exitFlag == -2) | (fval >= UB) FN(1)=[];if isempty(FN)==1flag=1;elsek=FN(1);A=AA{k};b=BB{k};endelsefor i=1:NLif abs(x(i)-round(x(i)))>1e-7kk=FN(end);FN=[FN,kk+1,kk+2];temp_A=zeros(1,NL);temp_A(i)=1;temp_A1=[A;temp_A];AA(kk+1)={temp_A1};b1=[b;fix(x(i))];BB(kk+1)={b1};temp_A2=[A;-temp_A];AA(kk+2)={temp_A2};b2=[b;-(fix(x(i))+1)];BB(kk+2)={b2};FN(1)=[];k=FN(1);A=AA{k};b=BB{k};break;endendif (i==NL) & (abs(x(i)-round(x(i)))<=1e-7)UB=fval;y=x;FN(1)=[];if isempty(FN)==1flag=1;elsek=FN(1);A=AA{k};b=BB{k};endendendendy=round(y);fval=c*y;以上程序都是我网上搜到的，还有自己从课本上自己敲的，第一个程序能成功解出答案，后两个不能，也许是程序有问题，也许是我不会调用，希望高手指点，帮助更多朋友们能够应用这三个程序～～～。