yalmip + lpsolve + matlab 求解混合整数线性规划问题（MIP/MILP） - balabala已被注册 - 博客园
随笔 - 30, 文章 - 0, 评论 - 95, 引用 - 0
　　最近建立了一个网络流模型，是一个混合整数线性规划问题（模型中既有连续变量，又有整型变量）。当要求解此模型的时候，发现matlab优化工具箱竟没有自带的可以求解这类问题的算法（只有bintprog求解器，但是只能求解不含连续变量的二值线性规划问题）。于是在网上找了一些解决问题的途径，下面说说我试过的几种可能的解决方案，包括cplex、GLPK、lpsolve 和 yalmip。
　　首先想到的是IBM公司大名鼎鼎的cplex。cplex是IBM公司一款高性能的数学规划问题求解器，可以快速、稳定地求解线性规划、混合整数规划、二次规划等一系列规划问题。CPLEX 的速度非常快，可以解决现实世界中许多大规模的问题，它能够处理有数百万个约束 (constraint) 和变量&(variable) 的问题，而且一直刷新数学规划的最高性能记录。他的标准版本是一个windows下的IDE应用软件，但是开发人员能通过组件库从其他程序语言调用 CPLEX 算法。随标准版本一起发布的文件中包含一个名为matlab文件夹，将此文件夹添加到matlab的搜索路径下就可以在matlab下调用cplex高效地求解数学规划问题。
　　CPLEX Optimizer中文介绍：
　　官方网址：
　　遗憾的是，cplex是一款商业软件，可以从以上官方网址上下载免费试用版，使用时限是90天，而且试用版对问题规模有限制（我的问题有300个变量，370个约束，结果因为问题规模限制无法用试用版求解）。如果你要用cplex解决问题的话，可能还需要学习特定于cplex的建模语言。
　　值得一提的是，IBM公司一直对学术界有或多或少的支持，要想使用完整版的cplex，你可以参与IBM的学院计划，前提条件是你是大学/研究机构的老师/研究员，或者IBM公式的职员，通过这个网址：&，填写一个申请表格，通过审核之后你就有权限使用cplex的完整版，没有任何限制，和商业版完全一样的功能。
　　由于没钱买软件，试用版有规模限制，又是个学生不能参与学院计划，只好放弃这一途径==。
　　在放弃了cplex之后搜寻其他解决方案的时候，我想起了GLPK。GLPK (GNU Linear Programming Kit，GNU线性编程工具)是GNU下的一个项目，用于建立大规模线性规划LP和混合型整数规划MIP问题，并对模型进行最优化求解。由于是GNU下的项目，因此没有商业非商业的版本限制，可以自由使用。
　　GLPK实现了对windows的支持，但是为此，你同样需要学习它的建模语言，并且所有的操作都在 glpsol.exe 提共的命令行下完成，比较不方便，且耗时长。如果要在matlab下使用，还需要下载额外的驱动文件。
　　GLPK英文介绍：
　　GLPK for windows：
lpsolve（详细介绍，最好结合后面介绍的&yalmip&工具箱一起看）
　　在弄了一阵GLPK无果之后，我又转投lpsolve了。lpsolve是sourceforge下的一个开源项目，它的介绍如下：
　　Mixed Integer Linear Programming (MILP) solver lp_solve solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models.lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and WINDOWS
　　它是一个混合整数线性规划求解器，可以求解纯线性、（混合）整数/二值、半连续和特殊有序集模型。并且经过实际验证，有极高的求解效率。
　　sourceforge主页：
　　从以上主页上可以下载lpsolve的IDE版本，界面比较简陋，类似于如下的样子：
　　以上是用IDE工具建模求解，如果要在matlab下使用lpsolve，需要在网址&提供的文件列表中下载类似lp_solve_5.5.2.0_MATLAB_exe_win32（只针对windows 32位操作系统，其他操作系统请选择对应版本下载）的zip文件。
　　由于我的问题就是用的lpsolve解决的，在这里详细介绍一下，以lp_solve_5.5.2.0_MATLAB_exe_win32为例，过程如下：
　　　　1. 下载。将下载的zip解压后，得到以下文件结构：
　　　　　　
　　　　　　bin目录下有matlab插件所必须的.mexw32文件和函数库API（.dll）。ex开头的一系列文件是自带的一些demo，教你如何在matlab下建模和求解。mxlpsove.m 是建模的核心函数，一个线性规划模型的所有配置和求解都是通过这个函数完成的。lp_maker.m 和 lp_solve.m 是对mxlpsolve.m的高层包装，简化了模型建立和求解的过程（后面会详细介绍）。
　　　　2. 准备驱动文件。在解压的bin目录下找到mxlpsolve.mexw32和mxlpsolve.dll两个文件，拷贝到解压根目录下（这两个文件就是matlab调用lpsolve的驱动文件），然后将此根目录添加到matlab搜索路径下（试试 pathtool 命令）。
　　　　3. 准备dll库文件。到这里不够，还需要lpsolve55.dll文件，真正求解问题的算法在这个函数库中。在lpsolve项目sourceforge首页下载安装一个IDE版本的程序，在安装目录下可以找到此dll文件，然后将此文件放到系统文件夹C:\Windows\System32下。也可以从我分享的这个链接下载到：/s/z4URgeDRTzBPd
　　　　4. 代码、求解。至此就可以在matlab下进尽情使用lpsolve了。以一个具体的例子说明用lpsolve求解数学规划问题的方法。
　　　　　假设我们要用matlab解决如下线性规划问题：
max 4x1 + 2x2 + x3s. t. 2x1 + x2 &= 1x1 + 2x3 &= 2x1 + x2 + x3 = 1x1 &= 0x1 &= 1x2 &= 0x2 &= 1x3 &= 0x3 &= 2
　　　　　　matlab语句如下：
　　　　　　&& f = [4 2 1];
　　　　　　&& A = [2 1 0; 1 0 2; 1 1 1];
　　　　　　&& b = [1; 2; 1];
　　　　　　&& l = [ 0 0 0];
　　　　　　&& u = [ 1 1 2];
　　　　　　&& lp=mxlpsolve('make_lp', 1, 3);
　　　　　　&& mxlpsolve('set_verbose', lp, 3);
　　　　　　&& mxlpsolve('set_obj_fn', lp, f);
　　　　　　&& mxlpsolve('add_constraint', lp, A(1, :), 1, b(1));
　　　　　　&& mxlpsolve('add_constraint', lp, A(2, :), 1, b(2));
　　　　　　&& mxlpsolve('add_constraint', lp, A(3, :), 0, b(3);
　　　　　　&& mxlpsolve('set_lowbo', lp, l);
　　　　　　&& mxlpsolve('set_upbo', lp, u);
　　　　　　&& mxlpsolve('write_lp', lp, 'a.lp');
　　　　　　&& mxlpsolve('get_mat', lp, 1, 2)
　　　　　　&& mxlpsolve('solve', lp)
　　　　　　&& mxlpsolve('get_objective', lp)
　　　　　　&& mxlpsolve('get_variables', lp)
　　　　　　&& mxlpsolve('get_constraints', lp)　　　　最后不要忘了用
　　　　　　&& mxlpsolve('delete_lp', lp)　　　　释放模型占用的内存。
　　　　如果需还要其他功能，请参考包含完整API文档的网址（重要，推荐看!!!）：&　　从以上的过程我们看到用 lpsolve 建立一个规划问题的代码还是够麻烦的，想必你刚开始看到上面那些语句的时候，也是一头雾水。不要着急，对于这类简单的问题，还有更简便的方法。好在 lpsolve 为我们提供了一种简化的途径，我们注意到以上文件列表中有一个lp_maker.m和lp_solve.m文件。lp_maker.m文件的功能是创建一个（混合整数）线性规划问题，调用格式类似于其他matlab自带的优化工具箱，你只需要为它提供f、A、b、l、u几个矩阵，它会自动为你实现创建模型、设置目标函数、添加约束的过程。help一下可以看到如下帮助：　
　　&& help lp_maker &% 嫌麻烦可以跳过此段帮助信息 　　LP_MAKER
Makes mixed integer linear programming problems.
　　SYNOPSIS: lp_handle = lp_maker(f,a,b,e,vlb,vub,xint,scalemode,setminim)
　　　　make the MILP problem
　　　　　　max v = f'*x
　　　　　　　　a*x && b
　　　　　　　　　　vlb &= x &= vub
　　　　　　　　　　x(int) are integer
　　ARGUMENTS: The first four arguments are required:
　　　　f: n vector of coefficients for a linear objective function.
　　　　a: m by n matrix representing linear constraints.
　　　　b: m vector of right sides for the inequality constraints.
　　　　e: m vector that determines the sense of the inequalities:
　　　　　　e(i) & 0
==& Less Than
　　　　　　e(i) = 0
==& Equals
　　　　　　e(i) & 0
==& Greater Than
　　　　vlb: n vector of non-negative lower bounds. If empty or omitted,
　　　　　　then the lower bounds are set to zero.
　　　　vub: n vector of upper bounds. May be omitted or empty.
　　　　xint: vector of integer variables. May be omitted or empty.
　　　　scalemode: Autoscale flag. Off when 0 or omitted.
　　　　setminim: Set maximum lp when this flag equals 0 or omitted.
　　OUTPUT: lp_handle is an integer handle to the lp created.
　　而 lp_solve.m 的调用格式与lp_maker.m类似，唯一的不同是，lp_solve.m 在创建模型的同时还求解模型，求解结果直接返回给输出参数。help一下帮助文档如下：
　　&& help lp_solve & &% 嫌麻烦可以跳过此段帮助信息
　　LP_SOLVE Solves mixed integer linear programming problems.
　　SYNOPSIS: [obj,x,duals,stat] = lp_solve(f,a,b,e,vlb,vub,xint,scalemode,keep)
　　　　solves the MILP problem
　　　　　　max v = f'*x
　　　　　　　　a*x && b
　　　　　　　　vlb &= x &= vub
　　　　　　　　x(int) are integer
　　ARGUMENTS: The first four arguments are required:
　　　　f: n vector of coefficients for a linear objective function.
　　　　a: m by n matrix representing linear constraints.
　　　　b: m vector of right sides for the inequality constraints.
　　　　e: m vector that determines the sense of the inequalities:
　　　　　　e(i) = -1
==& Less Than
　　　　　　e(i) =
==& Equals
　　　　　　e(i) =
==& Greater Than
　　　　vlb: n vector of lower bounds. If empty or omitted,
　　　　　　then the lower bounds are set to zero.
　　　　vub: n vector of upper bounds. May be omitted or empty.
　　　　xint: vector of integer variables. May be omitted or empty.
　　　　scalemode: scale flag. Off when 0 or omitted.
　　　　keep: Flag for keeping the lp problem after it's been solved.
　　　　　　If omitted, the lp will be deleted when solved
　　OUTPUT: A nonempty output is returned if a solution is found:
　　　　　obj: Optimal value of the objective function.
　　　　　x: Optimal value of the decision variables.
　　　　　duals: solution of the dual problem.
　　例如，同样解决以上线性规划问题，可以用如下语句简化过程(lp_maker版)：
　　&& f = [4 2 1];
　　&& A = [2 1 0; 1 0 2; 1 1 1];
　　&& b = [1; 2; 1];
　　&& l = [ 0 0 0];
　　&& u = [ 1 1 2];
　　&& lp = lp_maker(f, A, b, [-1; -1; 0], l, u, [], 1, 0);
　　&& solvestat = mxlpsolve('solve', lp)
　　solvestat =
　　&& obj = mxlpsolve('get_objective', lp)
　　&& x = mxlpsolve('get_variables', lp)
　　0.5000
　　0.5000
　　&& mxlpsolve('delete_lp', lp)或者只需要一句（lp_solve版）：　　&& [obj,x,duals,stat] = lp_solve(f, A, b, [-1; -1; 0], l, u, [], 1, 0);　　高层次的包装带来简便的同时也会让我们失去对问题更精细化的控制。例如，要使用 lp_solve.m 和 lp_maker.m，你必须事先知道约束系数矩阵A，然而对于很多实际问题，由于问题规模太大或者其他限制，你不能事先知道A矩阵，而是要用嵌套的for循环一步步建立起约束条件的时候，这两个高层包装就显得力不从心了。
yalmip（重点推荐！！）
　　最后登场的是yalmip，本来问题到 lpsolve 似乎就已经解决了，为什么还要介绍yalmip呢？因为我在解决这个问题的时候，其实是先遇到 yalmip，之后才遇到 lpsolve 的；再者，对于我的问题，lp_maker.m和lp_solve.m两个封装也无能为力；而且yalmip有它独特的优点，在这里不得不介绍。
　　此网址有它的详细介绍和下载链接：&（我猜测yalmip是耶鲁大学出品的，但是竟然找不到支持的证据。）
　　可以说，yalmip是一位&集大成者&，它不仅自己包含基本的线性规划求解算法，比如linprog（线性规划）、bintprog（二值线性规划）、bnb（分支界定算法）等，他还提供了对cplex、GLPK、lpsolve等求解工具包更高层次的包装。更为可贵的是，yalmip真正实现了建模和算法二者的分离，它提供了一种统一的、简单的建模语言，针对所有的规划问题，都可以用这种统一的方式建模；至于用哪种求解算法，你只需要通过一次简单的参数配置指定就可以了，甚至不用你指定，yalmip会自动为你选择最适合的算法。
　　总而言之，你只需要知道在matlab下如何用yalmip的方式建模，而不需要单独针对每一种工具包学习新的建模语法；而且yalmip 的建模语法非常简单，简单到你只需要记住四个命令就可以了：
1. 创建决策变量：
　　&& x = sdpvar(m, n [, option])：创建m*n的连续型决策变量矩阵，option是对矩阵的一些参数指定。
　　相应的，如果要创建整型或二值型决策变量，matlab语句分别为：　　
　　&& x = intvar(m, n, [option])
　　&& x = binvar(m, n, [option])
2. 添加约束：
　　&& F = set(constraint [, tag])：创建一个以constraint指定的约束，可选参数tag可以给该约束指定一个字符串标记。重要的是constraint的表达也非常简单，例如如果有 x1 + x2 + x3 &= 3 的约束，直接写：
　　&& x = sdpvar(3, 1);
　　&&&F = set(x(1) + x(2) + x(3) &= 3, 'cost bound1');
　　如果要继续添加约束也非常简单，支持用+直接相连：
　　&& F = F + set(constraint1 [, tag1]);
　　&& F = F + set(constraint2 [, tag2]);&&
　　例如，如果继续限制 x 只能取[0, 1]之间的值，则：
　　&& F = F + set(0 &= x &= 1, &upper and lower bound&);
　　一句话就搞定了，是不是非常简单。！
3. 参数配置
　　这个比较简单，语句如下：
　　&&&ops = sdpsettings(option1, value1, option2, value2, &&)
　　例如语句
　　&&&ops = sdpsettings('solver', 'lpsolve', 'verbose', 2);
　　'solver' 参数指定程序用lpsolve求解器（如果已经安装，否则会报错），如果不指定 &solver& 参数，他会根据决策变量类型自动挑选已安装的、最适合的求解器；'verbose' 指定显示冗余度（冗余度越大，你就可以看到越详细的求解过程信息）。
　　这个也只有一句话：
　　&&&result = solvesdp(F, f, ops) 求解一个数学规划（最小化）问题，该问题的目标函数由 f 指定，约束由 F 指定，ops指定求解参数，最后的结果存储在result结构体中。
还是以前面那个问题作为例子，如果用yalmip的话，只需要如下简单几句：
　　&&&x = sdpvar(3, 1);　　&&&f = [4 2 1] *　　&&&F = set(2*x(1) + x(2) &= 1);　　&&&F = F + set(x(1) + 2 * x(3) &= 2);　　&&&F = F + set(x(1) + x(2) + x(3) == 1);　　&&&F = F + set(0 &= x(1) &= 1) + set(0 &= x(2) &= 1) + set(0 &= x(3) &= 2);　　&&&ops = sdpsettings('solver', 'lpsolve', 'verbose', 2);　　&&&result = solvesdp(F, -f, ops);
　　如果你想用 cplex 求解器求解，只需要将以上的&solver&参数的&lpsolve&改成&cplex&，其他任何地方都不需要做改动。
　　除此以外，yalmip还支持几乎所有其他的求解算法，在matlab下输入yalmiptest命令可以得到所有支持的算法以及它们的安装状态（其中cplex和lpsolve是我安装的，其他status为found的表示默认支持，not found表示支持但matlab中还未安装）：
&& yalmiptest+++++++++++++++++++++++++++++++++++++++++++++++|
Searching for installed solvers
|+++++++++++++++++++++++++++++++++++++++++++++++|
Version/module|
Status|+++++++++++++++++++++++++++++++++++++++++++++++|
MXLPSOLVE|
geometric|
FMINSEARCH|
not found||
not found||
GLPKMEX-CC|
not found||
not found||
not found||
not found||
not found||
CLPMEX-LP|
not found||
MEXPRESS 1.1|
not found||
MEXPRESS 1.0|
not found||
not found||
not found||
not found||
not found||
not found||
not found||
GEOMETRIC|
not found||
not found||
not found||
CLPMEX-QP|
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
LOGDETPPA|
not found||
SPARSECOLO|
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
not found||
geometric|
not found||
not found||
not found||
not found||
geometric|
not found||
not found||
SPARSEPOP|
not found||
POWERSOLVER|
not found|+++++++++++++++++++++++++++++++++++++++++++++++
　　有了yalmip，你不再需要针对每一种工具包去学习特定的建模语言（比如用cplex要专门学习cplex的建模语言，用lingo要专门学习lingo的建模语言，还有GLPK、lpsolve、Matlab自带的求解器等等，如果每一种求解器都要学习新的建模语言的话，这个工作量是可想而知的）。相反，如果你选择使用yalmip，那么你只需要学习yalmip一种建模语法，因为yalmip真正实现了建模和算法的分离，所有的问题都可以用统一的方法建模，如果需要使用不同的求解器，只需要一句简单的配置即可。因此，yalmip不仅仅是一个线性规划求解器，更强大的地方在于，它提供了一个统一的建模平台，支持现有的几乎所有的求解算法。有了yalmip，一切都变得简单起来。
　　我的问题总共有300个变量，其中120个连续变量，120个0-1变量，60个整型变量；另外还有370个约束（不包括变量本身的上下限、整型约束）。由于yalmip自带的bnb算法求解出了错误的结果（这是个已经reported的bug，在最近的release版本中修复了），而且效率极差，一次求解要花费大概5分钟的时间，最后我在matlab下，用 yalmip 建模，求解器采用 lpsolve 把问题解决了，而且由于用了lpsolve，效率得到极大的提升，每一次求解只花费不到5秒钟中的时间。
　　将以上四个工具总结如下：
高效，快速，稳定，功能全面，适合大型商业化解决方案；可以通过学院计划免费获取。
付费，试用版有规模限制，需要学习特定建模语言。
开源，免费；适合linux用户。
windows下繁琐，需要学习特定建模语言。
sourceforge
开源，免费。
需要学习特定建模语言；建模语言较繁琐。
网络开放获取，建模语言简单、统一，自带基本求解算法，并支持集成几乎所有其他求解器。推荐使用。??2010年10月??????????????；??第31卷第5期???????????????；Matlab求解整数规划问题；陈福来,夏双喜,凌??双；(湘南学院数学系,湖南郴州??423000)；摘??要:克服Matlab不能直接求解整数规划问；关键词:整数规划;M遍历法;资源分配；中图分类号:O221.4????????????；1??前
??2010年10月????????????????????????????????????湘南学院学报??
??第31卷第5期??????????????????????????????JournalofXiangnanUniversity??Oct.,2010Vol.31No.5
Matlab求解整数规划问题
陈福来,夏双喜,凌??双
(湘南学院数学系,湖南郴州??423000)
摘??要:克服Matlab不能直接求解整数规划问题的不足,给出了Matlab求解整数规划问题的一般程序,并通过资源分配和会议筹备这两个问题说明了程序的可行性.
关键词:整数规划;M遍历法;资源分配;会议筹备
中图分类号:O221.4????????????文献标识码:A??????????????文章编号:10)05-0024-04
整数规划(IntegerProgramming)作为运筹学的一个重要内容,是近40年来发展起来的规划论中的一个分支,在生产管理、工程技术、军事作战、科学实验、财政经济以及社会科学中都有广泛的应用.数学建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,当决策变量为整数时,所建立的数学模型是一个整数规划问题,或者0-1整数规划问题,如全国大学生数学建模竞赛的2003年B题!露天矿生产的车辆安排?、2004年D题!公务员招聘问题?、2005年B题!DVD在线租赁问题?和2009年D题!会议
筹备问题?等.整数规划问题可以使用Lindo、Lingo等专用软件来求解,但这些软件都是付费软件,价格高且使用范围窄.对于整数规划规划问题,无法直接调用Matlab的内部函数,只能自己编程实现,一般是使用求解整数规划的分支定界法和割平面法进行Matlab编程实现.然而,无论是分支定界法还是割平面法,当决策变量较多时,成指数形式增加的编程工作量使得这些的方法变得不可行.这里我们介绍一种简单易行的方法###使用遍历法编写Matlab程序来求解整数规划问题,探讨如何使用遍历法编写Matlab程序求解整数规划问题,
并通过资源分配问题和会议筹备问题来说明方法的可行性.
2??遍历法求解整数规划问题
一般地,整数规划模型可表示为
??????????????????
??bi,i=1,2,%,m1,=bi,i=m1+1,%,m
xj&{0,1,%,kj},j=1,2,%,n.
由于xj为整数且取值范围有限,从而可行解的个数是有限的,又由于计算机硬件的飞速发展,世界上最快的计
基金项目:湖南省教育厅优秀青年科研项目(09B096),湖南省普通高校教学改革研究项目(湘教通??号),湖南教育
厅重点建设学科和湖南省高校科技创新团队项目,湘南学院教改项目(09Y001)
作者简介:陈福来(1971-),男,湖南郴州人,副教授,博士,研究方向:数学建模与数值模拟.
算机的技术速度已达每秒千兆次,普通的计算机的计算能力也大为加强,我们有可能在很短的时间内就遍历所有的可行解.遍历法求解整数规划问题,主要是通过循环控制语句和条件控制语句来实现的,使用for循环来遍历所有可行解,使用if语句来判断约束条件是否满足以及目标函数是否达到,使用变量替换来实现最优解的输出,具体如下:首先使用matlab的importData窗口导入矩阵A=(aij)、b=(bi)和c=(cj)的数据,按.mat的格式保存,然后编写M文件model.m,
Clear,loadA,loadb,loadcmin=e+10;
fory1=1:k1+1,%,foryn=1:kn+1x1=y1-1;%;xn=yn-1;
ifa(1,1)*x1+%+a(1,n)*xn&=b(1)
ifa(m,1)*x1+%+a(m,n)*xn=b(m)total=c(1)*x1+%+c(n)*iftotal&=min
min=z1=x1;%;zn=end,%,endmin,z1,%,zn
这里x1,%,xn分别表示x1,%,xn,k1,%,kn分别表示k1,%,kn,min表示目标函数取最优解,z1,%,zn表示获得最优解时xj的取值.
使用上述程序遍历规划问题所有的整数可行解,就能获得符合要求的最优整数解.这样在Matlab中,也能轻松地求解整数规划问题了.下面通过资源分配问题和会议筹备问题来说明程序的可行性.
3??资源分配问题
某中型的百货商场对售货人员的需求经过统计分析,一周中星期日、一、二、三、四、五和六每天所需的售货人数依次为12、18、15、12、16、19、14人(每天售货员工资200元).为保证销售人员充分休息,售货人员每周工作五天,休息两天,并要求休息的两天是连续的,问应该如何安排售货人员的作息,既满足了工作需要,又使所配备的售货人员总费用最少?
此问题是一个整数规划问题,目标是要求售货人员总数最少.因为每个售货员都工作5天,休息2天,所以只要计算出连续休息两天的售货员人数,也就计算出了售货员的总数.以每天开始休息的人数为决策变量x,即星期一开始休息的人数为x1,星期二开始休息的人数为x2,依次类推.建立如下的数学模型:
目标函数:min200(x1+x2+x3+x4+x5+x6+x7),
x1+x2+x3+x4+x5??12,x2+x3+x4+x5+x6??18,x3+x4+x5+x6+x7??15,
约束条件:????????????????
x4+x5+x6+x7+x1??12,x5+x6+x7+x1+x2??16,x6+x7+x1+x2+x3??19,x7+x1+x2+x3+x4??14,xi,i=1,%,7为正整数.
相应地,使用遍历法编写Matlab程序,有:%资源分配问题min=1000;
fory1=1:10,fory2=1:10,fory3=1:10,fory4=1:10,fory5=1:10,fory6=1:10,fory7=1:10
x1=y1-1;x2=y2-1;x3=y3-1;x4=y4-1;x5=y5-1;x6=y6-1;x7=y7-1;
ifx1+x2+x3+x4+x5&=12
ifx2+x3+x4+x5+x6&=18ifx3+x4+x5+x6+x7&=15ifx1+x4+x5+x6+x7&=12ifx1+x2+x5+x6+x7&=16ifx1+x2+x3+x6+x7&=19ifx1+x2+x3+x4+x7&=14
????total=x1+x2+x3+x4+x5+x6+x7;iftotal&=min
z1=x1;z2=x2;z3=x3;z4=x4;z5=x5;z6=x6;z7=x7;
end,end,end,end,end,end,end,end,end,end,end,end,end,end,end
min=min*200,z1,z2,z3,z4,z5,z6,z7
程序中min表示目标函数最优解,z1,z2,%,z7表示目标函数取最优解时决策变量的取值.运行程序得:星期一开始休息3人,星期二开始休息4人,星期三开始休息6人,星期四开始休息0人,星期五开始休息3人,星期六开始休息5人,星期天开始休息1人,整个支付费用为4400元??每周.
4??会议筹备问题
某市的一家会议服务公司负责承办某专业领域的一届全国性会议,会议筹备组要为与会代表预订宾馆客房.筹备组经过实地考察,筛选出10家宾馆作为备选,它们的名称用代号(至)表示,有关客房及会议室的规格、间数、价格等数据见表1,本届会议代表有关住房要求的信息见表2(单位:间).表头第一行中的数字1、2、3分别指每天每间120元~160元、161元~200元、201元~300元三种不同价格的房间,合住指要求两人合住一间,独住是指可安排单人间,或一人单独住一个双人间,下同.
表1??10家备选宾馆的有关数据
宾馆2宾馆3宾馆4宾馆5宾馆6宾馆7宾馆8宾馆9宾馆10
合住004000
合住060100
表2??本届会议代表的住房要求
????由于预计会议规模庞大,而适于接待这次会议的几家宾馆的客房数量有限,所以只能让与会代表分散到若干家宾馆住宿.为了便于管理,除了尽量满足代表在价位等方面的需求之外,所选择的宾馆数量应该尽可能少.
如果把这个问题看着是一个0-1整数规划问题,则决策变量xi(i=1,%10)表示是否入住第i家宾馆,即xi=
0,不入住家i家宾馆,1,入住第i家宾馆.
则目标函数是使入住的宾馆数最少,即:minz=
相应的约束条件:
85x2+50x3+50x4+70x5+50x7+40x8??98,50x1+30x2+24x3+45x4+40x5+40x6+40x8??x2+30x6+30x7+60x9+100x10??21,85x2+77x3+50x4+70x5+40x6+90x7+40x8??238,80x1+30x2+24x3+45x4+40x5+70x6+85x8??145,50x1+35x2+30x6+30x7+120x9+100x10??72,xi=0,1,i=1,%10.
约束条件中,前3个式中表示满足合住的要求,第4~6式表示满足独住的要求,最后的式子表示是否入住该宾馆.
编写Matlab程序如下:
%会议筹备问题min=10;
fory1=1:2,fory2=1:2,fory3=1:2,fory4=1:2,fory5=1:2,fory6=1:2,fory7=1:2,fory8=1:2,
fory9=1:2,fory10=1:2
??x1=y1-1;x2=y2-1;x3=y3-1;x4=y4-1;x5=y5-1;x6=y6-1;x7=y7-1;x8=y8-1;x9=y9-1;x10=y10-1;
if85*x2+50*x3+50*x4+70*x5+50*x7+40*x8&=98
if50*x1+30*x2+24*x3+45*x4+40*x5+40*x6+40*x8&=64
if30*x1+35*x2+30*x6+30*x7+60*x9+100*x10&=21
if85*x2+77*x3+50*x4+70*x5+40*x6+90*x7+40*x8&=238
if80*x1+30*x2+24*x3+45*x4+40*x5+70*x6+85*x8&=145
if50*x1+35*x2+30*x6+30*x7+120*x9+100*x10&=72
????total=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10;
iftotal&=min????min=
????z1=x1;z2=x2;z3=x3;z4=x4;z5=x5;z6=x6;z7=x7;z8=x8;z9=x9;z10=x10;
end,end,end,end,end,end,end,end,end,end,end,end,end,end,end,end,end
min,z1,z2,z3,z4,z5,z6,z7,z8,z9,z10
程序中min表示目标函数最优解,z1,z2,%,z10表示目标函数取最优解时决策变量的取值.运行程序,可得最少需要4个宾馆,即需要1、2、5、7这4个宾馆.
本文运用遍历法求解整数规划问题,所编写的程序简单易行,克服了Matlab不能直接求解这类问题的不足.通过资源分配和会议筹备这两个问题演示了如何建立整数规划模型和编写相应的Matlab程序,运行结果表明了程序的易编写性和可行性,易于用于其它整数规划问题的求解.参考文献:
[1]胡运权.运筹学(修订版)[M].北京:清华大学出版社,1990.
[2]董乘宇.数学建模竞赛中应当掌握的十类算法[J].数模,):12-14.
[3]谢金星,薛??毅.优化模型与Lindo??Lingo软件(第一版)[M].北京:清华大学出版社,2005.[4]张圣勤.数学实验与数学建模(第1版)[M].上海:复旦大学出版社,2008.
SolvingIntegerProgrammingProblemsUsingMatlab
CHENFu lai,XIAShuang xi,LINGShuang
(DepartmentofMathematics,XiangnanUniversity,Chenzhou423000,China)
Abstract:Inthisarticle,generalprogramtosolveintegerprogrammingproblems,whichovercomesthedrawback
thatMatlabcan?tdirectlybeusedtosolveintegerprogrammingproblems,isgivenbyusingMatlab,anditsfeasi bilityisverifiedthroughtwointegerprogrammingproblems,includingtheresourceallocationandmeetingarrang ing.
Keywords:Marrangingthemeeting
包含各类专业文献、中学教育、专业论文、幼儿教育、小学教育、生活休闲娱乐、文学作品欣赏、行业资料、应用写作文书、15Matlab求解整数规划问题等内容。
　用matlab求解整数规划的例子_数学_自然科学_专业资料。有四个人,要指派他们分别...Matlab求解整数规划问题 4页 2下载券
matlab解整数规划程序 2页 免费
matlab... 　3、Lindo 、Lingo 、Matlab 都可以求规划问题, 由于各种软件设计思想不同, 求出的最优解值相同,方案也不一定相同,例如案例 2 用 Lingo 和 Matlab 求得的 ... 　整数规划和多目标规划模型_理学_高等教育_教育专区。1 整数规划的 MATLAB 求解方法(一) 用 MATLAB 求解一般混合整数规划问题 由于 MATLAB 优化工具箱中并未提供求解... 　matlab中利用yalmip求解整数规划_城乡/园林规划_工程科技_专业资料。具体问题如下式: 目标函数:max z=4x1+6x2+2x3 s.t. -x1+3x2&=8 -x2+3x3&=10 5x1... 　第 13 章 整数规划本章通过分析应用问题建立数学模型并求解, 学习掌握整数规划及其求 解的分枝定界算法以及应用 MATLAB 求解。加强从“模型的建立到求解” 的数学... 　穷举法求解 0-1 整数规划的 matlab 程序 (原创) 0-1 整数规划有很广泛的应用背景,比如指派问题,背包问题等等,实际上 TSP 问题也是一个 0-1 问题,当然这些... 　解整数规划最典型的做法是逐步 生成一个相关的问题, 称它是原问题的衍生问题。...[2]刘卫国,MATLAB 程序设计与应用(第二版) ,北京:高等教育出版社; [3]薛毅... 　理解指派问题这一特殊整数线性规划问题的特点,体会指派问题求解的匈牙利方法; 2 掌握用 Matlab 或 LINDO 求解指派问题的方法和步骤,学会利用 Matlab 或 LINDO 求解... 　MATLAB分支定界法求解例... 3页 免费 整数规划_分支定界法_MA... 6页 1下载券m​a​t​l​a​b​解​整​数​规​划​程​序 ...}