【数学建模】第02章 整数规划

建模算法（⼆）——整数规划⼀、概述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);%如果不是要求整数规划的就可以返回了。

整数规划模型实际问题中x x x x f z Max Min Tn "),(),()(1==或的优化模型mi x g t s i ",2,1,0)(..=≤x ~决策变量f (x )~目标函数g i (x )≤0~约束条件多元函数决策变量个数n 和数线性规划条件极值约束条件个数m 较大最优解在可行域学规非线性规划解的边界上取得划整数规划Programming+Integer所有变量都取整数，称为纯整数规划；有一部分取整数，称为混合整数规划；限制取0，1称为0‐1型整数规划。

型整数规划+整数线性规划max(min) nz c x =1j jj n=∑1s.t. (,) 1,2,,ij j i j a x b i m=≤=≥=∑"12 ,,,0 ()n x x x ≥"且为整数或部分为整数+例：假设有m 种不同的物品要装入航天飞机，它们的重量和体积分别为价值为w j 和v j ，价值为c j ，航天飞机的载重量和体积限制分别为W 和V ，如何装载使价值最大化？m1⎧1max j jj c y =∑ 1 0j j y =⎨被装载 s.t. mj j v y V≤∑0j ⎩没被装载1j m=1j j j w y W=≤∑ 0 or 1 1,2,,j y j m=="(Chicago)大学的Linus Schrage教授于1980年美国芝加哥(Chi)Li S h前后开发, 后来成立LINDO系统公司（LINDO Systems Inc.），网址：I）网址htt//li dLINDO: Interactive and Discrete Optimizer (V6.1) Linear(V61) LINGO: Linear Interactive General Optimizer (V8.0) LINDO——解决线性规划LP—Linear Programming，整数规划IP—Integer Programming问题。

整数规划前面介绍的线性规划问题中，只要求决策变量非负，也就是说决策变量可以取小数，然而在许多经济管理的实际问题中，决策变量只有取非负的整数才有实际意义。

如果一个线性规划问题要求全部的决策变量都取整数，那么这样的线性规划问题称为全整数规划或纯整数规划问题。

如果只要求一部分决策变量取整数，那么这样的线性规划问题称为混合整数规划问题。

如果决策变量只能取0或者1，那么就称为0-1规划问题 整数规划在实际中的应用: 1. 指派问题：某公司人事部门欲安排四个人去做四项不同的工作，每个人只能完成一项工作，一项工作只能由一个人完成。

每个人完成各项工作所消耗的时间（单位：分钟）如下表所示，（2） 如果把（1）中的消耗时间数据看成创造效益的数据，那么应该如何指派，可以使得总的效益最大？（3） 如果在（1）中再增加一项工作E ，甲 、乙、丙、丁四人完成工作E 的时间分别为17，20，15，16分钟，那么应该指派这四个人干哪四项工作，可使得这四个总的消耗时间为最少？解：（1） 引入0-1变量ij x ，并令⎩⎨⎧=项工作时个人不做第当第项工作时个人去做第当第j i j i x ij 01，于是这个分派问题的数学模型为：⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧====+++=+++=+++=+++=+++=+++=+++=++++++++++++++++++=4,3,2,1,4,3,2,1101111111119242017181516262027241828201920min 443424144333231342322212413121114443424134333231242322211413121144434241343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x Z ij ，或 用管理运筹学2.0软件求解结果如下：**********************最优解如下*************************目标函数最优值为 : 71变量 最优解 ------- --------x1 0 x2 1 x3 0 x4 0 x5 1 x6 0 x7 0 x8 0 x9 0 x10 0 x11 1 x12 0 x13 0 x14 0 x15 0 x16 1 约束 松弛/剩余 ------- ---------1 02 03 04 05 06 07 08 0 这就说明112=x ，121=x ，133=x ，144=x所以应该让甲去做B 工作，让乙去做A 工作，让丙去做C 工作，让丁去做D 工作，这时总的消耗时间为71分钟。

整数规划的数学模型及解的特点整数规划IP (integer programming ）:在许多规划问题中,如果要求一部分或全部决策变量必须取整数。

例如,所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。

一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划（pure integer linear programming ）:指全部决策变量都必须取整数值的整数线性规划。

有时,也称为全整数规划.2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划（zero —one integer liner programming ）：指决策变量只能取值0或1的整数线性规划。

1 解整数规划问题0—1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi 称为0-1变量，或称为二进制变量.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z0—1型整数规划中0—1变量作为逻辑变量(logical variable ），常被用来表示系统是否处于某一特定状态,或者决策时是否取某个方案。

整数规划建模方法及应用什么是整数规划？整数规划（Integer Programming，简称IP）是在满足一定的约束条件下，求解使目标函数达到最优的一组整数决策变量的数学规划问题。

与线性规划（Linear Programming，简称LP）不同的是，LP中的决策变量可以取任意实数值，而IP中的决策变量只能取整数值。

因此，整数规划问题通常更为复杂，求解难度更大。

整数规划广泛应用于各种实际问题中，例如制造业生产计划、物流配送优化、网络优化、人员调度等。

整数规划建模方法线性整数规划线性整数规划（Integer Linear Programming，简称ILP）是指目标函数和约束条件都是线性的整数规划问题。

一个典型的线性整数规划问题可以表示为：$max\\{cx|Ax\\le b,x\\in Z^n\\}$其中，$A\\in R^{m*n}$，$b\\in R^m$，$c\\in R^n$，$x\\inZ^n$表示整数决策变量。

指派问题是一个经典的线性整数规划问题。

它是一个求解如下二元匹配问题的整数规划模型：$min\\{cx|cx\\ge\\{1,...,1\\},x_{ij}\\in\\{0,1\\},i=1,...,n,j=1,...,m\\}$其中，c是n∗m维的代价系数向量，x ij表示第i个任务分配给第j个工人的决策变量，x ij=1表示第i个任务分配给第j个工人，x ij=0表示不分配。

非线性整数规划非线性整数规划（Nonlinear Integer Programming，简称NLIP）是指目标函数或/和约束条件中存在非线性项的整数规划问题。

一个典型的非线性整数规划问题可以表示为：$max\\{f(x)|g(x)\\le0,x\\in Z\\}$其中，f(x)是目标函数，g(x)代表约束条件，x是整数决策变量。

整数规划求解方法前向分支定界法前向分支定界法（Branch and Bound，简称B&B）是一种广泛应用于整数规划求解的算法。

整数规划引言：整数规划是一类特殊的数学优化问题，其中一部份或者全部变量被限制为整数。

整数规划问题在许多领域都有广泛的应用，如物流、生产计划、金融投资等。

随着科技的不断发展，整数规划的应用场景和求解方法也在不断扩展和深化。

一、整数规划的定义与分类定义：整数规划是一种特殊的数学优化问题，其目标是最小化或者最大化一个数学表达式（目标函数），同时满足一系列约束条件，且一部份或者全部决策变量被限制为整数。

分类：根据问题的特性，整数规划可以分为以下几种类型：0-1背包问题：决策变量只能取0或者1。

彻底背包问题：决策变量可以取任意非负整数。

整数线性规划：线性规划的变种，要求部份或者全部决策变量为整数。

二次整数规划：目标函数或者约束条件包含二次项。

二、整数规划的应用场景生产计划：在创造业中，整数规划可以用于优化生产流程、物料需求计划等。

物流优化：通过整数规划可以解决货物配送路线、车辆调度等问题。

金融投资：整数规划在投资组合优化、风险管理等领域有广泛应用。

资源分配：整数规划可用于解决资源分配问题，如人员调度、设备配置等。

组合优化：如旅行商问题（TSP）、装箱问题等，都是整数规划的典型应用场景。

三、整数规划的求解算法穷举法：通过逐个测试所有可能的解来找到最优解，但只适合于小规模问题。

分支定界法：一种基于树结构的搜索算法，能够处理较大规模的问题。

遗传算法：摹拟生物进化过程的优化算法，适合处理大规模问题。

摹拟退火算法：借鉴物理中退火过程的优化算法，具有避免陷入局部最优解的能力。

蚁群算法：摹拟蚂蚁觅食行为的优化算法，适合于求解具有离散变量的优化问题。

元胞遗传算法：将遗传算法和元胞自动机结合，能够处理更复杂的问题。

粒子群算法：摹拟鸟群觅食行为的优化算法，具有简单易实现的特点。

深度学习算法：利用神经网络进行求解，特别在处理大规模、高维度的问题时表现出色。

四、整数规划软件介绍CPLEX：由IBM开辟的商业优化软件，支持整数规划、线性规划、混合整数规划等多种优化问题。

XX大学毕业论文数学建模中的整数规划问题研究院系名称：专业：学生姓名：学号：指导老师：XX大学制二〇一年月日1.引言应用数学学科的一项重要任务是从自然科学、社会科学、工程技术以及现代化管理中提出问题和解决问题。

这就要求我们学会如何将实际问题经过分析、简化，转化为一个数学问题，然后用适当的数学方法解决，即建立数学模型。

随着科学技术的发展，特别是计算机技术的发展，数学的应用领域已由传统的物理领域迅速的扩展到非物理领域。

数学在发展高科技、提高生产力水平和实现现代化管理等方面的作用越来越明显。

正是这样的背景下，数学模型这个词汇越来越多的出现在现代化生产、工作和社会生活中。

数学模型的分类方法有很多种，例如按照建模所用的数学方法的不同，可分为：初等模型、运筹学模型、微分方程模型、概率统计模型、控制论模型等。

而运筹学模型中的规划模型又可分为非线性规划模型和线性规划模型，本文通过实例剖析线性规划中整数规划方法在数学模型种的应用2.主要结果2.1数学建模中的整数规划问题在研究线性规划的问题中，一般问题的最优解都是非整数，即为分数或小数，但对于实际中的具体问题的解常常要求必须取整数.例如问题的解表示是人数、机器设备的台数、机械车辆数等都是整数.为了求整数解，我们设想把所求得的非整数解采用“舍人取整”的方法处理，似乎是变成了整数解，但事实上这样得到的结果未必可行.因为取整以后就不一定是原问题的可行解了，或者虽然是可行解，但也不一定是最优解.因此，对于要求最优整数解的问题，需要寻求直接的求解方法，这就是整数规划方法.2.2整数规划的基本概念]1[整数规划的一般模型为：()()()⎪⎩⎪⎨⎧=≥=≥=≤=∑∑==,,,2,1,0,,,2,1),(..,minmax11njxxmibxat sxcjjnjijijnjjjz为整数（2.1）整数规划求解方法总的基本思想是：松弛问题（2.1）中的约束条件（譬如去掉整数约束条件），使构成易于求解的新问题——松弛问题（A），如果这个问题（A）的最优解是元问题（2.1）的可行解，则就是原问题（2.1）的最优解；否则，在保证不改变松弛问题（A）的可行性的条件下，修正松弛问题（A）的可行域（增加新的约束），变成新的问题（B），再求问题（B）的解，重复这一过程直到修正问题的最优解在原问题（2.1）的可行域内为止，即得到了原问题的最优解.2.3整数规划的解法2.3.1整数规划的分枝定界法分枝定界法的基本思想：将原问题（2.1）中的整数约束去掉变为问题（A），求出问题（A）的最优解，如果它不是原问题的可行解，则通过附加线性不等式约束，将问题（A）分枝变为若干子问题（iB）（i=1，2，…，I），即对每一个非整数变量附加两个互相排斥（不交叉）的整型约束，即可得到两个子问题，继续求解定界，重复这一过程，知道得到最优解为止。

XX大学毕业论文数学建模中的整数规划问题研究院系名称：专业：学生姓名：学号：指导老师：XX大学制二〇一年月日1.引言应用数学学科的一项重要任务是从自然科学、社会科学、工程技术以及现代化管理中提出问题和解决问题。

这就要求我们学会如何将实际问题经过分析、简化，转化为一个数学问题，然后用适当的数学方法解决，即建立数学模型。

随着科学技术的发展，特别是计算机技术的发展，数学的应用领域已由传统的物理领域迅速的扩展到非物理领域。

数学在发展高科技、提高生产力水平和实现现代化管理等方面的作用越来越明显。

正是这样的背景下，数学模型这个词汇越来越多的出现在现代化生产、工作和社会生活中。

数学模型的分类方法有很多种，例如按照建模所用的数学方法的不同，可分为：初等模型、运筹学模型、微分方程模型、概率统计模型、控制论模型等。

而运筹学模型中的规划模型又可分为非线性规划模型和线性规划模型，本文通过实例剖析线性规划中整数规划方法在数学模型种的应用2.主要结果2.1数学建模中的整数规划问题在研究线性规划的问题中，一般问题的最优解都是非整数，即为分数或小数，但对于实际中的具体问题的解常常要求必须取整数.例如问题的解表示是人数、机器设备的台数、机械车辆数等都是整数.为了求整数解，我们设想把所求得的非整数解采用“舍人取整”的方法处理，似乎是变成了整数解，但事实上这样得到的结果未必可行.因为取整以后就不一定是原问题的可行解了，或者虽然是可行解，但也不一定是最优解.因此，对于要求最优整数解的问题，需要寻求直接的求解方法，这就是整数规划方法.2.2整数规划的基本概念]1[整数规划的一般模型为：()()()⎪⎩⎪⎨⎧=≥=≥=≤=∑∑==,,,2,1,0,,,2,1),(..,minmax11njxxmibxat sxcjjnjijijnjjjz为整数（2.1）整数规划求解方法总的基本思想是：松弛问题（2.1）中的约束条件（譬如去掉整数约束条件），使构成易于求解的新问题——松弛问题（A），如果这个问题（A）的最优解是元问题（2.1）的可行解，则就是原问题（2.1）的最优解；否则，在保证不改变松弛问题（A）的可行性的条件下，修正松弛问题（A）的可行域（增加新的约束），变成新的问题（B），再求问题（B）的解，重复这一过程直到修正问题的最优解在原问题（2.1）的可行域内为止，即得到了原问题的最优解.2.3整数规划的解法2.3.1整数规划的分枝定界法分枝定界法的基本思想：将原问题（2.1）中的整数约束去掉变为问题（A），求出问题（A）的最优解，如果它不是原问题的可行解，则通过附加线性不等式约束，将问题（A）分枝变为若干子问题（iB）（i=1，2，…，I），即对每一个非整数变量附加两个互相排斥（不交叉）的整型约束，即可得到两个子问题，继续求解定界，重复这一过程，知道得到最优解为止。