基于分支定界法的整数规划问题研究与应用

2019-09-10张晗陈晓晓魏禧辰

赤峰学院学报·自然科学版 2019年4期

张晗陈晓晓魏禧辰

摘要：整数规划是日常生活中较为常见的一种特殊的规划问题，需要使用特殊的方式来进行求解.分支定界法作为一种枚举型的求解思想，通过分割解空间来限定最优解的上下界，从而较为高效地获得整数规划问题的最优解.本文对分支定界法进行了建模分析，给出了分支定界法求解最优解的一般思路和求解方法，同时使用分支定界法进行了实证分析，利用分支定界法对飞机排班问题和生产用料最优化问题进行了实际的模拟求解，并分析了分支定界法的优点和不足.

关键词：整数规划;分支定界法;实证分析;Mathematica

中图分类号：O221.4;F201 文献标识码：A 文章编号：1673-260X（2019）04-0020-04

1 研究背景

整数规划是一种情况较为特殊的规划问题，其所含的变量的取值均为整数，这就为求解问题设置了障碍：一般情况下，最优解并不一定是整数解.

在日常生活中，整数规划的实例很多，例如装载问题、固定费用问题、探险队问题等等.整数规划是NP困难的，存在某个多项式算法来进行求解和检验的，有很高的计算复杂性，我们可以先从求解整数规划中的线性问题，再从线性形式逼近最接近的整数.分支定界法就是解决一般的整数规划的一个很有效的方法.

本文将通过分支定界法来对整数规划问题进行理论模型的建立、推导以及求解，并进行了实际应用.本文研究了组合优化的工厂下料问题，以及航空公司航班安排问题，从理论分析入手，经过模型建立，理论求解，利用数学软件进行实际模拟，并最终得到问题的结果.

2 相关理论

2.1 整数规划

在线性规划问题求解中，最优解可能是小数或分数，但在实际生活中，常会限制某些变量的解必须是整数，那么全部或者个别变量是整数的线性规划就被称作整数规划.由于问题中对求解变量的要求不同，又分为纯整数规划和混合整数规划.

2.2 分支定界法的发展

分支定界法是由学者理查德·卡普在二十世纪60年代发明，他成功求解了旅行商问题.Kolen等利用此方法求解时间窗约束的车辆巡回问题，取得良好效果，其对于时间的计算也体现很强的优势.分支定界发被广泛而普遍地应用于工业化生产之中，对于生产物料消耗的最优化组合问题具有很好的解决能力.李播等利用分支定界法进行了手术计划的调度研究，用以在择期病人的安排最大化和预留应急手术室以应对急诊病人之间达到利用最大化的手术时间安排.李秋阳采用分支定界法，研究了电能表计量电路容差的设计方法;王建辉利用分支定界方法对不平衡的气象数据进行了气象的预测和晴雨的分析.可以看出，分支定界的思想在规划和优化组合的问题上有着至关重要的地位.

2.3 分支定界法的基本思想

分支定界法的最基本思想就是对规划问题的所有可行解空间进行查找，通过将解空间进行分割成小的分支，为每一个分支的解计算一个下界，从而寻找到最终的最优解.这也是分支定界法的三个步骤：分支、松弛和下界.

2.4 分支

对于整数规划问题M，设F（M）为问题M的允许解集，对于子问题M1，M2，…，Mn，若有

2.5 松弛

在放弃M的某些条件后，得到的问题都是M的松弛问题，显然M的松弛问题的约束条件要弱于M，则M的松弛问题有以下特点：

（1）若松弛问题无解，则原问题无解;

（2）原问题的最优解不优于松弛问题的最优解;

（3）若松弛问题的最优解是原问题的允许解，那么这个解也是原问题的最优解.

通常来说，我们在实际求解过程中，最经常放弃的条件就是变量的整数性要求.

2.6 定界

假设问题M已经分解为M1，M2，…，Mn的和，并且各个子问题都已经有了对应的松弛问题，那么如果某个松弛问题无解，那么该松弛问题对应的子问题就没有允许解，那么就将该子问题从M的分解表上删去;

如果已经可以求得M的某一个允许解X，若某松弛问题的最优解不好于该允许解，那么说明其对应的子问题中没有比X更好的允许解，因此可以将对应的子问题从M的分解表中去掉;

如果某个松弛问题的最优解是其对应子问题的允许解，则我们就已知了该子问题的一个最优解，则我们也无需考虑该子问题了，就可以将其从分解表上去掉，如果这个时候子问题的最优解比X要好，那么就将X替换掉.

如果分解表上的松弛问题的最优解都不比原允许解要好，那么原允许解就是M的一个最优解.

从算法的角度看，分支定界法形为在一棵深度为n的树上进行寻找，通过对树上每个节点进行线性规划求解，来寻找每个节点的下界，以此确定下界的最小节点，并把该节点作为下一个分支的节点，最终找到可行解，并且将目前寻找到的最好的可行解和下一个分支寻找到的可行解进行比较，留下更优的解.通过一层一层的筛选和比较，最终找到最优解.分支定界的方法，通過分支大大减少了枚举法带来的运算复杂度，在变量较多的规划问题中，可以凸显其运算精简的优势.

3 理论推导

3.1 模型的基本形式

对于整数规划问题，基本的形式为

3.2 模型求解

首先我们求解整数规划问题的松弛问题，即

如果该松弛问题的最优解x0为整数解，那么此最优解也是原整数规划问题的最优解.

如果该松弛问题的最优解不是整数解，那么该最优解就是原整数规划问题最优解的一个下界，我们就可以把原整数规划问题分为两个子问题

对这两个子问题继续进行松弛问题的求解，也会得到两个不同的最优解，通过比较进行筛选，确定新的下界.通过重复该过程，若在某一个子问题中扎到了整数解xm，则该解为原整数规划问题的一个上界.此时，对于子问题k，若该问题的下界xk>xm，那么该分支就可以直接删去，否则就将分支过程继续下去，直到找到最优解为止.

4 实际应用

4.1 飞机航班问题

航空运输业在运营过程中，由于飞机不论是长时间处于空闲状态或者是满负荷状态都会增加航空公司的运营成本和飞机的维修成本，因此航空公司需要在能够满足航班需求的基础上使每一架飞机的飞行时间和负荷能够达到均衡的水平.同时，也要求航空公司的维护成本、机队均衡都能够满足需求.简而言之，就是航空公司要根据航班计划和飞机的维护状态来对每一架飞机的执飞进行航班安排，以达到飞机使用的平均化.

4.1.1 模型建立

根据问题的求解，我们可以知道，所需求解的问题为整数规划问题，则可以以此建立模型：

令F=航班集合;

R为可航行的航班环集合

M为维护场地集合

J表示可行航班组，也就是能够理论上可以安排飞行的方法安排

I表示航班

aij=1，航班i在可行航班j中0，航班i不在可行航班j中

N为飞机总数

Tj为可航行航班组j的飞行时间

Q为所有航班的飞行总时间

xij=1，若可行航班组j被选上，否则取值为0

模型表达为：

其中cj=|Tj-Q/N|，表示该模型利用每个可行航班环的飞行时间和当天的每架飞机的平均飞行时间的差值来确定均衡性.该模型的限制条件对飞机的数量，即飞机总数不能多于公司拥有的飞机数;飞机飞行的现实条件，即每一个航班只能由一架飞机执飞都进行了限定.

由于分支定界法是对可行情况进行一定程度的枚举，因此变量的复杂程度直接影响了分支定界法的计算复杂度.由于分支定界法的算法复杂度依赖于需要进行排班的航班数，因此如果能尽可能将可以排班的航班范围缩小，就而可以更加便于得到结果.由于我国的有关规定，飞机必须能够在规定时间飞到正确的维修场地过夜和维护，因此，通过筛选我们可以从所有航班中筛选出满足要求的可排班航班组组成集合R，该集合相比集合F能够更加简化运算的复杂度.

4.1.2 模型求解

在本问题中，为了快速得到整数解，我们按照最小下界优先原则进行分支求解，具体步骤如下：

首先令该问题为M，该问题的松弛问题为放弃xj的0-1取值后的问题;

求解松弛问题，记录松弛问题的最优解和求得的最小值，如果此时该最优解满足原问题的要求，则该解为原问题M的最优解，算法结束;若该最优解不能满足原问题的要求，则令该松弛问题的最小值为原问题目标函数值的下界.

选择M的子问题，对其松弛问题进行求解，如果松弛问题无允许解或者其最小值大于原问题的松弛问题的最小值，那么将其删去，若求得子问题的松弛问题的最優解也是原子问题的允许解，那么看求得的最小值与原问题松弛问题的最小值孰小;将较小值保存为原目标函数值的新的下界;若求得子问题的松弛问题的最优解不是子问题的允许解，则选取系数最大的证书变量进行分支，按照0和1分成两个子问题，并重复进行松弛和定界的过程.

循环往复此过程，直到找到原目标问题的最优解结束.

4.1.3 实际模拟

我们收集了国内某家航空公司的飞行数据进行了实际模拟.首先该公司需要执飞68个航班，飞机的维修场地一共有3个，飞机12架，同时根据我国航空运输的相关规定，在这68个航班中，可以组成233个可行航班环，同时每个可行航班环的飞行时间也是已知的，其中航班集合F中含有68个元素，可行航班环集合R中有233个元素，设定目标函数cj=|Tj-Q/N|，Tj为航班环的飞行时间，一共有233个决策变量，除了整数约束外，共有69个约束条件.利用Mathematica软件进行处理，用分支定界法一共进行了38次循环处理，得到了12架飞机的执飞安排图，同时可以利用分支定界法进行轮班，一次可以得到长期的飞机执飞安排.

4.2 物料最优解问题

在工业生产中，经常遇到同一种生产原料生产几种不同的产品，这时候如何最大化利用固有的原料，使产能达到最大化，材料的利用率达到最大就变得至关重要.可以通过利用分支定界法，在有限的时间、空间以及其他原料条件下得到最优的解，从而对客观实际产生帮助.

4.2.1 问题提出

现要利用某种布匹生产不同种类的服装，根据便于生产和节约布料的原则，现在可以有n中不同的制作分配方式.假设第j种生产方式种可以得到第i种服装aij件，同时第i种服装的需求量为bi个，那么究竟该如何分配原料布匹，才能够既满足需求，又能使所使用的原料布匹最少？

4.2.2 模型建立

上述问题可以用表格表示

令xj表示第Bj种分配方式所消耗的布料数量，则该问题可以归纳为整数规划问题

4.2.3 模型求解

运用分支定界法进行求解，首先我们求原整数规划的松弛问题

若得到的最优解是整数，则最优解是原线性整数规划的最优解，求解过程结束.若非整数，则得到的最优解是原线性整数规划最优解的一个下界，这样我们就将原问题分成两个子问题，对子问题松弛问题分别求解;若在某个求解过程中得到了一个整数解，这个整数解就是原线性整数规划的一个上界，此时，若从子问题k开始进行分支，但是该问题的下界要大于原整数规划的解的上界，那么该子问题中找不到小于原线性整数规划的上界的解，则该问题可以直接舍去;若子问题k的下界小于原整数规划的上界，那么分支定界的过程仍继续，直到找出最优解.

4.2.4 实际模拟

假设某服装厂有一批长为180米的布料用来制造服装，其中由三种服装，第一种服装消耗布料70米，第二种服装消耗布料52米，第三种布料消耗布料35米，三种服装的需求量分别为100件，150件和100件，先要计算如何裁制服装才能使消耗的布料最少.

像这样的问题我们可以通过优化组合的方法来给出最合理的资源分配方式，设x1，x2，x3分别表示制造三种服装的数量，那么就有70x1+50x2+35x3≤180，其中x1，x2，x3均为整数，并且x1≤2.

则使用数学表达式则为

利用Mathematica进行编程模拟，可以得到结果：X=[28，42，1，1，1，30，1，1]，也即是，在生產过程中，如果按照B1的裁制方式裁制28套布料，按照B2的裁制方式裁制42套布料，按照B3的裁制方式裁制1套布料，按照B4的裁制方式裁制1套布料，按照B5的裁制方式裁制1套布料，按照B6的裁制方式裁制30套布料，按照B7的裁制方式裁制1套布料，按照B8的裁制方式裁制1套布料，那么此时布料的利用效率是最高的，可达到96.5%，同时满足对每一种服装的生产需求，此时就是最优解.

5 结论

本文不仅从理论上对分支定界法进行了建模和求解分析，还从实际出发，从不同的案例着手对分支定界法进行了实际层面的建模和求解.对飞机排班问题，首先筛选可行航班环来减少运算量，再使用分支定界法对飞机排班进行最优化求解，选择总体最优化的排班方案.利用了分支定界法，对服装厂利用长度一定的整卷布料生产不同耗用布料数量的三种服装，使其在充分满足每种服装的需求的基础上，原料的利用率达到最大，并且根据实际情况，利用数学软件进行了编程运算，从而得到了最优化的解法.

参考文献：

〔1〕范永俊，吴东华.基于分支定界法的飞机均衡排班计划求解[J].统计与决策，2017（20）：60-63.

〔2〕李平风，刘海峰.线性整数规划分支定界法并行化研究[J].电脑知识与技术，2016，12（24）：28-30.

〔3〕刘霞，高岳林.整数二次规划问题的一种新型分支定界算法[J].中北大学学报（自然科学版），2015，36（04）：412-417.

〔4〕马艳利.混合整数非线性规划问题的分支定界算法研究[D].宁夏大学，2014.

〔5〕李红霞，张琛.基于整数规划的模糊关系方程极小解的求解算法[J].佳木斯大学学报（自然科学版），2012，30（05）：788-790.

〔6〕艾杰.基于分支定界算法的护士排班模型研究[J].科学技术与工程，2012，12（13）：3074-3077.

〔7〕秦平平.分支定界算法在运筹学模型中的应用[D].燕山大学，2009.

〔8〕郭志军.Mathematica求解整数规划研究[J].黑龙江科技信息，2007（24）：35+178.

〔9〕管琳，白艳萍.用分支定界算法求解旅行商问题[J].中北大学学报（自然科学版），2007（02）：104-107.

〔10〕刘寿春，胡雁玲，洪文.整数规划模型研究[J].皖西学院学报，2004（02）：6-8.

〔11〕倪明放，徐南荣.混合整数两层线性规划的一个代理约束方法[J].东南大学学报，1994（01）：77-82.