整数规划范文优秀6篇

2023-11-03 11:47:19

《整数规划范文优秀6篇》由壶知道为您提供，希望可以在【整数规划】写作方面，给予您一定的参考价值。

整数规划篇一

关键词：粒子群算法；0-1整数规划问题；背包问题；遗传算法；变异

中图分类号：TP301.6文献标识码：A

Solving 0-1 Integer Programming Problem by Hybrid Particle Swarm Optimization Algorithm

XUE Feng，CHEN Gang, GAO Shang

(School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003,China)

Abstract:The classical particle swarm optimization is a powerful method to find the minimum of a numerical function, on a continuous definition domain. The particle swarm optimization algorithm combine the ideal of the genetic algorithm is recommended to solve 0-1 integer programming problem. All the 6 hybrid particle swarm optimization algorithms are proved effective. Especially the hybrid particle swarm optimization algorithm with across strategy A and mutation strategy C is a simple and effective better algorithm than others. It can easily be modified for any combinatorial problem for which we have no good specialized algorithm.

Key words:particle swarm algorithm; 0-1 integer programming problem；knapsack problem; genetic algorithm; mutation

1 引言

0-1整数规划问题是运筹学中一个典型的组合优化难题，有着广泛的应用背景，如货物装载问题，选址问题等。由于此问题比较简单典型，因此评价算法优劣常常以此问题作为的测试对象进行研究。0-1整数规划问题属于NP问题，目前求解的方法有精确方法（如动态规划、递归法、回溯法、分支限界法等［1］），近似算法（如贪心法［1］，Lagrange法等）以及智能优化算法（如模拟退火算法［2］、遗传算法［2］、遗传退火进化算法［3］、蚁群算法［4, 5］）。精确方法虽然可以得到准确解，但时间复杂性与物品数目成指数关系。近似算法和智能优化算法虽然不一定得到准确解，但可得到比较有效解，并且时间复杂性比较低。笔者尝试采用粒子群优化算法解决此问题。

2 0-1整数规划问题数学模型

0-1整数规划问题的数学模型为

min f(x1,x2,…,xn),

s.t.gi(x1,x2,…,xn)≥0(i=1,2,…,m)(1)

xi = 0, 1(i = 0, 1, …, n)3 基本粒子群优化算法

粒子群优化 (PSO, particle swarm optimization) 算法是一种进化计算技术，最早是由Kennedy与Eberhart于1995年提出的［6］。源于对鸟群捕食的行为研究的PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。目前已提出了多种PSO改进算法［6~9］，如自适应PSO算法、杂交PSO算法、协同PSO算法。笔者提出基于遗传算法思想的一种新的PSO算法来解决0-1整数规划问题。PSO是模拟鸟群的捕食行为，设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟，称为“粒子”。所有的例子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。一个是粒子本身所找到的最优解，称为个体极值pbest；另一个极值是整个种群目前找到的最优解，称为全局极值gbest，另外也可以不用整个种群而只是用其中一部分为粒子的邻居，那么在所有邻居中的极值就是局部值。

在找到这2个最优值时，每个粒子根据如下的公式来更新自己的速度和新的位置：

xk+1= xk + vk+1(3)

其中：vk是粒子的速度向量；xk是当前粒子的位置；pbestk粒子本身所找到的最优解的位置；gbestk整个种群目前找到的最优解的位置；c0, c1, c2表示群体认知系数，c0一般取介于（0, 1）之间的随机数，c1, c2取（0, 2）之间的随机数。vk+1是vk，pbest

首先把原约束方程作为罚函数项加入到原目标中，变成无约束的优化问题，即

min T=f(x1,x2,…,xn)+

M∑mi=1min (0,gi(x1,x2,…,xn)2 (4)

其中M为一充分大的正数。

计算技术与自动化2011年3月

第30卷第1期薛峰等：求解0-1整数规划的混合粒子群优化算法

0-1整数规划问题的解用向量X = (x1, x2, …, xn)T表示，粒子群算法的本质是利用个体极值信息和全局极值两个信息，来指导粒子下一步迭代位置。对于0-1整数规划问题，若按基本粒子群算法，其速度难于表达，故采用遗传算法［2］交叉操作的思想：式（1）中的c0vk项可以看作遗传算法的变异操作，式（1）中的c1(pbestk

项可以看作遗传算法的交叉操作，让当前解与个体极值和全局极值分别作交叉操作，产生的解为新的位置。交叉方法可以采用以下两种方法

1）交叉策略A：

（1）两串old1和old2交叉，在第二个串old2中随机选择一个交叉区域；

（2）将old1的相应的交叉区域由old2交叉区域代替。

例如两父串为

old1=1 0 0 1 0 1 1 1 1 0 0 1，

old2=0 1 1 0 1 0 1 0 1 1 0 0。

交叉区域为0 1 0 1 1，交叉后为

new1=1 0 0 1 0 0 1 0 1 1 0 1。

2）交叉策略B：

（1）随机产生k个1到n的整数j1, j2, …, jk；

（2）将old1的j1, j2, …, jk的位置数值由old2相应的部分代替。

具体变异操作可以采用下面三种

1）变异策略A：

（1）在解空间(x1, x2, …, xn)T中随机选择一块区域，如(xi, xi+1, …, xj)T；

（2） (xi, xi+1, …, xj)T

如原来解为1 0 0 1 0 1 1 11 0 01 ，随机产生区域为1 1 0 0，则变异操作后的解为

1 0 0 1 0 1 1 0 0 1 1 1。

2）变异策略B：

（1）在解空间(x1, x2, …, xn)T中随机选择一块区域，如(xi, xi+1, …, xj)T；

（2）. (xi, xi+1, …, xj)T取随机值。

3）变异策略C：

（1）在解空间(x1, x2, …, xn)T中随机选择一个1到n的整数j；

（2） xj

如原来解为1 0 0 1 0 1 1 1 1 0 0 1，随机产生整数为4，则变异操作后的解为1 0 0 0 0 1 1 1 1 0 0 1。

解0-1整数规划问题的混合粒子群算法hybrid _PSO如下：

1) 设定粒子数np，规定迭代次数nmax，随机产生np个初始解X0；

2) 根据当前位置根据式（4）计算适应值l0，设置当前适应值为个体极值plbest，当前位置为个体极值位置pxbest，根据各个粒子的个体极值plbest，找出全局极值glbest和全局极值位置gxbest；

3) While (迭代次数＜规定迭代次数n┆max) do

4) for j =1: np

5) 第j个粒子位置X0(j)与gxbest交叉得到X1

7) 对X1(j)进行变异操作；

8) 根据当前位置计算适应值l1；

9) 如果l1(j)＜ plbest (j)，则pxbest (j) = X1(j)，plbest (j) = l1(j)；

10) End

11) 根据各个粒子的个体极值plbest，找出全局极值glbest和全局极值位置gxbest；

12) X0

13) End

14) 输出全局极值glbest和全局极值位置xbest。

该粒子群算法的时间复杂性估算如下：以交叉时间和变异操作花费最多，变异操作的时间与交叉操作时间相近，里面循环需要作O(3np)交叉（或变异）操作，外循环执行n┆max次，所以时间复杂性大约为O(3npn┆max)。

5 数值仿真与分析

5.1 各种策略比较

背包问题是一个典型的0-1整数规划问题。采用文献［4］的一个典型的背包问题数据，n = 10，C = 269 g，{p1, p2, …, p10}={55，10，47，5，4，50，8，61，85，87}元，{c1, c2, …, c10}={95，4，60，32，23，72，80，62，65，46} g。混合粒子群算法分别2种交叉策略和3种变异策略，组合起来6种方法进行比较，各种算法各测试100次，最优目标值为295元，最优解为：X*= {0, 1, 1, 1, 0, 0, 0, 1, 1, 1}。参数粒子数np = 10，最大迭代次数nmax = 10的结果如表1所示；若粒子数np = 20，最大迭代次数n┆max = 30。蚁群算法参数如下：蚂蚁数20，信息素强度重要性

从表1和表2可以看出，只进行交叉操作的2个算法，效果比较差。效果最好的是交叉策略A和变异策略C的组合算法最好。并且交叉策略A比交叉策略B简单，变异策略C也比变异策略A和变异策略B简单。变异策略A和变异策略B，由于变异的位数多，增加了部分差的解，因此效果不如变异方法C。随着粒子数和最大迭代次数增加，计算效果变好，但其运算量也将增大。另外这里的交叉操作与遗传算法的交叉操作不同，遗传算法随机选择2个解进行交叉，而粒子群交叉操作是对每个粒子进行交叉操作，并且与个体极值和全局极值进行交叉，考虑了优生的思想，因此效果比传统的遗传效果好。

5.2 与其他算法比较

针对背包问题，对递归算法、回溯方法和蚁群算法进行了比较，采用文献［5］的测试方法，数据随机产生，各ci和pi在1~100随机生成，物品种类取值为5~20，背包的质量容量C为总质量的80 %。每个算法运行100次，统计出平均运行时间，结果如表3所示。从表3可以看出交叉策略A和变异策略C的粒子群算法运行的效率较高，尽管比文献［5］蚁群算法运行稍长点，但得到精确解的次数较高（表2）。

6 结论

本文作者创新点：提出的粒子群优化算法不仅可以解决0-1整数规划问题，对于整数规划问题，对该算法作适当修改，也可适用。粒子群优化算法(PSO)是起源对简单社会系统的模拟，擅长连续问题的优化，笔者尝试采用粒子群算法解决离散优化问题。PSO研究处于初期，还有许多问题值得研究，如算法的收敛性、理论依据等。但从当前的粒子群算法的应用效果［8, 9］来看，这种模仿自然生物的新型系统的寻优思想无疑具有十分光明的前景，更深入的工作还有待于进一步展开。

参考文献

［1］王晓东。计算机算法设计与分析［M］. 北京：电子工业出版社， 2001：92-168

［2］王凌。智能优化算法及其应用［M］. 北京：清华大学出版社， 2001：17-59

［3］金慧敏，马良。遗传退火进化算法在背包问题中的应用［J］. 上海理工大学学报，2004，26(6)： 561-564

［4］马良，王龙德。背包问题的蚂蚁优化算法［J］. 计算机应用， 2001, 21(8): 4-5

［5］于永新，张新荣。基于蚁群系统的多选择背包问题优化算法［J］. 计算机工程， 2003, 29(20)：75-76

［6］Eberhart R C，Kennedy J. A new optimizer using particles swarm theory ［A］. Proc Sixth International Symposium on Micro Machine and Human Science ［C］. Nagoya, Japan, 1995. 30~43

［7］ Shi Y H, Eberhart R C. A modified particle swarm optimizer ［A］. IEEE International Conference on Evolutionary Computation ［C］. Anchorage, Alaska, 1998：69-73

［8］李爱国，覃征，鲍复民，等。粒子群优化算法［J］.计算机工程与应用， 2002, 38(21)：1-3

［9］杨维，李歧强。粒子群优化算法综述［J］. 中国工程科学， 2004, 6(5)：87-94.

整数规划篇二

整数规划是一类要求问题中的全部或一部分变量为整数的数学规划。如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。在数学规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求结果必须是整数。本文采用整数规划的方法建立排课问题的数学模型，优化高等院校的排课。

1.排课问题描述

1.1 排课问题要素

从本校的实际情况来看，排课主要考虑时间、班级、课程、教室和教师这五个要素。对这些要素进行透彻的分析以及适当的预处理，是建立排课模型的基础。

（1）时间：排课问题中涉及的时间概念有学年、学期、周、天、时间段等。结合本校上课时间安排，只考虑按周来组织课表。每周5天教学日，每天10节课，分5个时间段，每2节课为一个时间段，每学期每周课表固定。

（2）课程：每门课程都有自己的编号、名称、学时和学分等要求，每门课程每周需要安排的学时体现为课程的学分，1学分的概念就是在每个教学周安排1个学时；周学时为奇数的课程，排课时的实际周学时，取为比该课程周学时数大的最小偶数。

（3）教室：每个教室要有自己的编号和类别名称（如普通教室、多媒体教室、微机室等）等，每个教室在同一时间只能上一门课，且满足教室的类型和教室的容量等要求。

（4）班级：每个班级要有自己的编号和名称，在同一时间一个班级只能上一门课程。

（5）教师：每个教师要有自己的工号和名称，在同一时间一个教师只能上一门课程。

1.2 排课问题约束条件

因为排课问题要满足多种约束条件，为了降低问题复杂度，可将排课的约束条件按照程度分为两大类：硬性约束和软性约束。前者是排课问题中必须遵循的原则，是衡量排课方案是否切实可行的标准，后者是排课过程中应当予以考虑，不一定必须满足，但如果满足可使排课结果更加合理，是衡量排课方案优劣的标准。

2.排课数学模型的建立

基于排课问题涉及的要素和约束条件建立如下排课问题的数学模型，主要对排课问题进行严格的数量关系描述。

2.1 模型参数

3.结论

虽然我们给出了排课问题的目标方程。但是，在不同的教学环境和不同的评价人的主观因素下，很难确定各个目标方程的权重。所以，对于课表优劣的衡量仍然是一个模糊的概念。基于以上的情况，我们不需要寻找问题的最优解，而应该寻找满足约束条件（F，C，L，R，T）的较优组合，从中选择一个作为较优课表。后续我们将进一步研究求解整数规划问题的算法，使排课达到最优组合。

参考文献

[1]鄂强金。基于混沌遗传算法的排课问题研究[硕士学位论文].哈尔滨工程大学，2009.

[2]A.S.Asratian.Investigation of some mathematical model of scheduling theory[D].Moscow University，1980.

[3]于艳东。基于遗传模拟退火算法的智能组卷系统研究[硕士学位论文].内蒙古大学，2011.

[4]C c Gotlieb.The Construction of Class-Teacher Time-Tables.1963.

整数规划篇三

关键词：线性整数规划；分支定界；matlab；算法效率；并行化处理

中图分类号：O246 文献标识码：A 文章编号：1009-3044（2016）24-0028-03

Abstact： Variables （all or part） is limited to an integer， called integer programming. If the linear model， limited to an integer variable， is called linear integer programming. Branch and bound algorithm is an important method to solve integer programming. However， the efficiency of the algorithm needs to be improved. The paper elaborates the steps of solving linear integer programming problem by the method of branch and bound， then through then achieve branch and bound method for parallelization of algorithms in the use of parallelism supported by matlab. Analysis the running time of both before and after parallel to study the parallelization algorithms for efficiency.

Key words： linear integer programming； branch and bound； matlab； algorithm efficiency； parallel processing

1 分支定界法简介

在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常常会遇到一些变量的解必须是整数。例如，变化量表示的是机器的台数，工作的人数或装货的车数等。为了满足整数解的需求，一般来说只要化整已经得到了的非整数解。但是事实上化整也不一定能得到可行解和最优解，因此需要有特定的方法来求解整数规划[1]。

上个世纪60年代LandDoig和Dakin等人提出了可以求解整数或者是混合整数线性规划问题的分支定界算法。

该算法的思想是把有约束条件的最优化问题所拥有的所有可行的解空间进行搜索。具体执行算法时，会不断地分割所有可行的解空间成为越来越小的子集，然后将每个分割出的子集里面的目标函数值计算一个下界或上界。在每次分支之后，对所有界限超过了已知的可行解的值的那些子集不再分支。这样就可以去掉许多的子集，因此缩小了搜索的范围。重复这一过程一直到找出可行解的值不大于任何子集界限的可行解的位置。所以这个算法一般可以求得最优解[1]。

要将分支定界算法由串行计算转换为并行计算，难点在于要解决对二叉树的每个左右分支都实施并行计算所面临的计算数据组织、通信处理问题[2]。

接下来以下例来阐述分支定界法解线性整数规划的步骤。

由此可知，分支定界就是根据现有解不断将问题化为子问题，并更新上下界，直到求得我们需要的答案的过程。

2 在matlab中并行化的实现

2.1 Matlab并行计算的基本概念

Matlab依赖以下两个工具来实现并行计算架构：Matlab并行计算工具箱和分布式程序。用户使用Matlab提供的并行计算工具可以更加专注于并行计算算法的设计，很大程度上减少了用户用于解决网络通信等问题上投入的工作和精力[3]。

Matlab并行计算可以分为两类问题：第一类是distributed任务，各个作业之间完全独立，不需要进行数据通信，各个作业可以异步执行；第二类是parallel任务，任务的各个作业之间需要进行数据通信，必须同步执行[4]。

进行并行计算时，工作单元有job、task、client、worker。其中client相当于计算机的界面，负责完成几乎所有的用户交互操作；job负责管理worker和分配task，每一个job包含多个task，每个task都要通过job分配给worker执行，并将执行结果返回[5]。client、job、worker运行在同一台或者是多台网络上的计算机上。

程序执行时，task是Matlab处理待完成的并行计算的基本单元，每个任务都是由一个或者是多个task组成的。由用户编写并行程序来创建和划分job和task来完成待解决的并行计算任务。

开发Matlab并行程序首先要采用串行方法运行程序；然后选择合适的并行方法，采用Matlab并行结构或者创建通用的并行计算程序；之后再控制数据和任务分配；然后采用pmode调试并行功能；配置local，在本地多核计算机执行并行任务[6]。

2.2 Matlab中的并行计算支持

为了支持并行计算，Matlab为开发者提供了许多的并行结构，这些结构中包括了Parfor循环结构，SPMD并行结构，分布式阵列，分布式数值处理算法和消息传递函数等。本文采用的是Parfor循环结构来实现分支定界法解线性规划问题的并行化。

由for关键字表示的循环可以通过使用parfor关键字代替进行并行。Matlab执行代码过程中，如果循环体使用的是for关键字，则采用串行方式执行；如果循环体使用的是parfor关键字，则采用并行方式执行。

在使用parfor关键字代替for关键字并行执行循环时，会将循环分为很多部分，每个部分交给不同的worker执行。因此对于执行效率来说，假设使用的worker的数量为n，循环次数为m，则m如果能被n整除的话，则将循环均匀划分；如果不能被整除的话，则将循环非均匀划分，其中某些worker会执行较多的循环次数。

默认情况matlab启动时只有一个进程，因此默认情况下执行parfor关键字标志的循环时是串行执行的。因此在执行前必须先打开Matlab并行计算池。

Matlab并行计算池管理很多个worker，每个worker都可以执行分配的并行计算任务，其对应的物理单元即处理器或处理器核。

Parfor循环将for循环分解为子循环，分解后得到的子循环由不同的处理单元处理，用此来减少整个循环执行所需要的时间，提高计算效率。而在使用Parfor循环代替for循环之前一定要先使用matlabpool命令启动所需要的处理单元，然后将循环体中的for关键字修改为parfor关键字，通过Matlab的程序解释器将此循环交由matlabpool启动的多个处理单元完成[7]。

3 用matlab实现分支定界法解线性规划并行化

解决线性规划问题时，分支定界法是一项相当重要的方法。因此，研究该算法的并行化对于提高解决线性规划问题而言是特别有意义的。

在使用分支定界法时，最重要的就是分支和剪枝。并且耗时最长循环最多的地方也是这里，因此我们选择将这一部分并行处理。

我们仍然用开头所用的例子来进行测试，比较使用了并行和未并行的情况下计算出结果分别所使用的时间。

因为使用了matlab所提供的计算线性规划的函数linprog，因此我们需要将求解最大值问题转换为求解最小值问题。只需要将函数加负号就能解决，而且这并不影响我们的测试[8]。

用matlab提供的时间函数来记录程序运行的时间，分别记录开启并行时和未开启时分别的运行速度来进行比较。

测试使用的是一台四核计算机，理论来说的话上可以将计算速度提高四倍，然而实际效果却达不到这个效果。这是由于该算法对二叉树的每个左右分支实施并行计算及并行计算数据组织、通信与处理时对算法运行效率影响较高，因此达不到理想效果。但是从测试结果来看，并行化后的程序的确大大提升了运行效率。

参考文献：

[1] 孙小玲，李端。整数规划新进展[J]. 运筹学学报， 2014， 18（1）： 40-65.

[2] Jack Dongarra.并行计算综论[M]. 北京：电子工业出版社， 2005

[3] 胡良剑，孙晓君。 Matlab 数学实验[M]. 北京：高等教育出版社， 2006.

[4] 陈国良。并行算法实践[M]. 北京：高等教育出版社， 2004.

[5] 楼顺天。 Matlab程序设计语言[M]. 西安：西安电子科技大学出版社， 1997.

[6] 陈国良。并行算法实践[M]. 北京：高等教育出版社， 2004.

[7] 刘维。实战Matlab并行程序设计[M]. 北京：北京航空航天大学出版社， 2012.

整数规划篇四

Abstract： This paper introduces the loading and handling equipment in logistics centre. It takes the operational cost and operation capability as the goal to consider the actual factors of utilization rate load ratio， configuration coefficient， alternate operation， establish an optimization model for allocated quantity of handling equipment based on integer programming. At last， a numerical example is presented by steel logistics centre， which shows that the method put forward in the paper is feasible and effective.

关键词：物流中心；装卸搬运设备；配置数量优化；整数规划

Key words： logistics center；handling equipment；optimization of allocated quantity；integer programming

中图分类号：F253.9 文献标识码：A 文章编号：1006-4311（2016）03-0222-02

0 引言

在物流中心内，物料装卸搬运设备的合理配置是极为重要的关键。配置良好的搬运设备可有效满足物流中心内各项作业活动的需求，在成本方面，物料搬运成本约占作业总成本的50%以上，而通过良好的搬运设备配置，可有效降低营运成本约20%左右，由此可见搬运设备配置对于配送中心的重要性。

装卸搬运作业贯穿于整个物流中心作业的始终，它是最能体现物流作业效率的部分，在整个物流系统中具有重要地位。因此对装卸搬运进行优化和计划，将能在很大程度上降低作业量，减少设备的使用量，提高作业精度，加快对客户的反映速度，提高整个物流系统的效率。为了保证装卸搬运工作的顺利进行，必须统筹安排作业流程规划和设备合理拥有量，才能取得良好的效果。本文以运营成本、作业能力为目标，建立了基于多目标规划的装卸搬运设备配置数量优化模型。

1 装卸搬运设备配置数量优化模型

1.1 问题描述

装卸搬运设备作为物流中心数量最多，使用最频繁的物流设备，很大程度上决定了物流中心的作业效率和服务水平的高低，同时也会给物流中心带来运营成本的压力。配置数量的增加，直接提高了作业能力与效率，但同时也带来了作业成本的增加，因此成本目标和作业能力目标成了两个相互矛盾的因素。控制成本可以减少投资，增加资金利用率，而保证作业能力则可以提高效率，增强对突发状况的响应能力，提升客户服务水平。本文以运营成本、作业效率为目标，建立基于整数规划的物流中心装卸搬运设备配置数量优化模型。

1.2 模型假设

①物流中心在规划过程中已对未来的经营状况进行了合理准确的预测，货物种类和周转量相对稳定，不会出现极大与极少的极端情况，且每种货物的所占比例也是已知的。

②物流中心经营状况良好，各种装卸搬运设备使用良好，设备管理水平较高，装卸搬运工艺与操作技术成熟。

③所有装卸搬运设备的成本采用全寿命周期成本计算。

④从提高设备利用率和保证作业便利性的角度出发，只允许同种类别相邻吨位的装卸设备才能替代作业，即大吨位装卸设备可以替代相邻小吨位装卸设备进行作业；每台搬运设备的单次作业量以不超过额定作业能力为限，可以进行充分配载，即大吨位搬运设备可以替代任何小吨位搬运设备进行作业。

1.3 模型建立

本模型中共有i种类型的装卸搬运设备，每种类型设备又分为j种型号，因此所需配置的设备数量为Xij，设备全寿命周期成本为Cij，包括第i类设备第j种型号的固定成本与变动成本。其他符号定义如下：

Q：物流中心货物搬运量（万t/年）；

λ：物流中心装卸搬运设备配置系数；

Qij：第i种类型第j种型号设备所分配的作业量（万t/年）；

Fij：第i种类型第j种型号设备所承担的实际作业量（万t/年）；

Pij：第i种类型第j种型号设备作业效率（万t/台时）；

Gij：第i种类型第j种型号设备额定载重量；

Hij：第i种类型第j种型号设备平均装卸搬运一次货物重量与额定载重量之比；

γij：第i种类型第j种型号设备每小时完成的作业次数；

t：设备年日历工作时间（h/小时）；

K：设备使用系数。

其中，设备作业效率Pij=GijHijγij

设备承担实际作业量Fij=XijPijtK

整数规划篇五

关键词：答辩排班整数规划排班模型

中图分类号：G4 文献标识码：A 文章编号：1673-9795（2014）05（a）-0111-02

答辩在现实生活中越来越多，尤其是在高校里，例如毕业论文答辩、优秀生答辩等等。答辩排班就是将评审人与答辩人分组并安排好参与评审和答辩的时间。以往这些工作是由工作人员手工完成，但随着答辩人数的增加，排班就变得十分复杂，往往会花费工作人员大量时间。

在排班问题的研究中，谢屹红等对护士排班的问题进行了早期的研究，沈吟东等则在模型和算法上对护士排班的问题进行了深入探讨。孙宏等建立的规划模型并利用分阶段指派算法研究了航空公司飞机排班问题。梁建波等建立了公交智能排班方法，并对其应用进行了研究。马荣昌、谢传柳等在对呼叫中心话务量预测的基础上设计了呼叫中心排班模型和算法。魏红翠针对图书馆人员排班问题建立了优化模型。前人对排班问题已经有了较为深入的研究，但答辩排班的问题有自身的独特性，在约束条件方面与其他排班问题有很大不同之处，而在这一方面尚未有人涉足。

本文即针对答辩排班问题，根据此类问题的特性，建立整数规划模型，并对一高校毕业论文答辩进行分析和求解。

1 答辩排班问题

在答辩中，每个答辩人的研究方向会有所不同，每个评审人对各个方向的擅长程度也不同；答辩一般持续1～3天，有些甚至更长，每天的答辩分为上午、下午两班，各评审人在此期间是否能参加评审也存在差异；答辩中，评审人可能与答辩人存在利害关系而影响答辩的公平性：以上这些都是答辩排班问题的特性。

答辩排班问题是一种在满足时间、研究方向等约束条件下，实现将答辩人和评审人最优分组的问题。在答辩排班问题中，约束条件主要包括评审人时间偏好要求、评审人熟悉答辩人所研究问题的要求、评审人与答辩人无利害关系的要求（简称背对背要求）、答辩时间场地的要求等。具体约束如下。

约束1：评审人有时间参加答辩评审。

约束2：评审人熟悉答辩人所研究的问题。

约束3：每个答辩小组的评审人数为固定值。

约束4：评审人与所评审的答辩人无利害关系（即背对背）。

约束5：每个答辩小组答辩人数不低于下限，也不超过上限。

约束：6：每个评审人评审组数不能超过上限。

约束7：任何班次答辩组数不能超过场地上限。

约束8：每个答辩人都要分入答辩小组，每一答辩小组都要安排时间答辩。

2 答辩排班模型

答辩排班模型的目标是在满足各种约束条件下，使此次答辩能够得到最好的评审，即让更多擅长的评审人进行评审。

用表示评审人的集合，用表示答辩人的集合，用表示答辩所涉及方向的集合，表示答辩期间所有班次的集合，用表示答辩小组的集合。

如果评审人l有时间参加第i班次的评审，则，否则。表示评审人l对答辩方向j的擅长度，记为

。如果答辩人s涉及的方向为j，记，否则记。如果答辩人s与评审人l有利害关系，则，否则。表示答辩人s被分配到第k答辩小组，表示评审人l评审第k答辩小组，表示第k答辩小组在第i班次进行答辩。表示每个答辩小组的评审人数，分别表示每个答辩小组答辩人数的下限和上限，表示每个评审人评审组数的上限，表示答辩场地的上限。

其中为待求量，均为0-1变量，其余均为已知量。基于上述定义的参数，可建立如下答辩排班模型：

（1）

约束1：

≤（2）

约束2：≤

（3）

约束3：（4）

约束4：

（5）

约束5：≤≤ （6）

约束6：≤ （7）

约束7：≤ （8）

约束8：

（9）

公式（1）为此模型的目标函数，即让更多更擅长的评审人来评审答辩；公式（2）～（9）分别表示上文所述的约束条件1～8。

3 算例实验

本文利用某大学工程硕士答辩排班作为算例进行实验。此算例即对该校工程硕士论文答辩进行排班。

3.1 数据假设

（1）此例中评审人有22位，答辩人有40位，答辩所涉及的方向有3个，答辩要在两天内完成，所以答辩期间班次有4班。要求每个答辩小组的评审人数为5人，每个答辩小组答辩人数的下限为8人、上限为10人，每个评审人最多评审两个答辩小组，答辩场地有5个。

（2）评审人答辩期间时间安排如表1所示。

表1中数字“1”表示评审人可以评审该班次答辩，“0”表示评审人没有时间参加该班次的评审。

（3）评审人对答辩方向擅长程度如表2所示。

（4）答辩人s1～s13的答辩方向为j1，s14～s26的答辩方向为j2，s27～s40的答辩方向为j3。

4 结论

本文研究了答辩排班这一问题，在对问题进行综合分析的基础上建立了答辩排班模型，并通过一个实际算例证明了本模型的可靠性。此模型可以解决手工排班速度慢、准确性低的问题，并且兼顾评审准确性方面，大大提高了答辩排班的效率。但利用lingo中的分支定界算法求解大规模的答辩排班问题时效率还有待提高，答辩排班的智能算法会是以后的研究方向。

参考文献

[1] 谢屹红。护士排班方式与护理人力资源的合理利用[J].中国实用护理杂志，2004（7）：65.

[2] 彭刚艺，李亚洁，李茶香。连续排班模式对护士工作压力影响的评价[J].中华护理杂志，2009（5）：407-409.

[3] 张莉，彭刚艺，刘雪琴，苏敏谊，程云，袁卫红，张秀平，严素芬。连续性排班模式有助于推动护士分层级管理[J].中华护理杂志，2009（2）：99-103，111.

[4] 沈吟东，苏光辉。带约束的护士排班模型和基于变换规则的优化算法[J].计算机工程与科学，2010（7）.

[5] 王昌毓，沈吟东，陈凯。带个人偏好的多级别护士排班问题研究[C]//第三十一届中国控制会议论文集B卷，2012.

[6] 孙宏，杜文。航空公司飞机排班问题的排序模型及算法[J].系统工程理论方法应用，2002（3）：244-247.

[7] 孙宏，杜文。航空公司飞机排班问题的分阶段指派算法[J].系统工程学报，2003（2）：168-172.

整数规划篇六

[关键词] 主生产计划路径整数规划半导体制造

一、引言

本文主要致力于解决半导体后道封装测试厂的生产计划问题。基于客户确定的订单及销售预测的需求，我们来研究如何计算一个合适的数量的芯片在一个给定的周期内完成加工。工厂可以是自有工厂也可以考虑外发加工。订单完成率及产能约束会加入到约束条件之中。计算结果可以用于决策每个工厂的投料的数量，品种及时间点。这个计算结果就是主生产计划(MPS). 主生产计划在一个较长的时间段内，通常是半年，根据产品系列整合总体的生产，销售，及运作计划并最终产生针对各个产品以周为单位的总体生产计划。一个主生产计划是下一层各工厂或代工厂的生产计划及库存控制的重要依据。本文中所提及的主生产计划在一定程度上可以被称为供应链计划。

在诸多研究中，半导体行业的主生产计划很少被提及。有些著作会研究晶圆厂的产能规划问题。然而这种产能规划的时间段通常是1至2年，大大长过主生产计划。并且一般只是基于一个半导体晶圆厂针对不同产品系列展开的综合分析。在有的著作中曾提及基于整数规划来探讨集团范围内的生产策略及资源规划。一个总体模式被用来产生基于产品系列层级的计算结果。这样的模型和本文的模型有点类似在于它着重考虑了半导体制造中各前道晶圆厂及后道封装测试厂间的网络关系。也有基于一个前道晶圆厂的比较详细的模型。其中一个线形规划模型及相应的离散时件模拟被用于对不同产品投产比例的研究。基于对以往研究的探讨，可以发现主生产计划问题并不仅仅局限于半导体制造的供应链网络。在其它不同类型的行业中也有关于主生产计划方面的研究。本文主要就后道封装测试的自有工厂及外包厂的主生产计划建模并进行模拟计算。

在本文的第一段，我们会描述目前的问题。第二段，我们会建议一个整数规划模型。在最后，一些下一步的研究方向会加以阐述。

二、问题的阐述及假设

在本小节中，我们会针对所研究的问题加以描述，在第2小节中一个数学模型将会引入以优化本文的问题。我们主要致力于确定在不同的时间段不同的工厂投产的芯片数量。半导体制造包括前道及后道生产线。前道生产主要在半导体晶圆厂，而后道生产主要在封装测试厂。

本文只考虑封装测试厂。通常，生产可以外包也可以在自有工厂生产。自有工厂的模型会比外包工厂的来得复杂。我们假设需求的时间单位是周。需求包括确定的订单以及基于预测的产量。确定的订单的投产优先级要高于基于预测的产量。我们考虑上一个时间周期未达成的确定订单。基于预测的产量也被称为追加的需求。只有当产能充足的时候，我们才考虑基于预测的产量。假设我们会为了以后的订单储存一定量的成品库存。基于确定订单的销量不会超过客户订单的数量。基于预测的销量小于基于预测的产量。产能约束对于主生产计划问题很关键。在我们的模型中，我们假设每个产品的平均生产周期固定。给定的产品的完成时间。,我们能计算出它到达生产瓶颈的时间。我们在每个时间周期都会计算单位产品在生产瓶颈上消耗的时间。这个举措可以将那些工艺流程中要重复进入某一生产瓶颈的情况得到计算。由于我们无从获知代工厂的生产瓶颈，故而这种方法不适用于代工厂。因此对于代工厂，我们只是简单的计算单位时间的出货量。在这里我们规定代工厂的加工数量不能超过一个确定的界线。我们主要的工作是确定一定数量的芯片产品 p 能够在某个工厂m 内在时间周期 t 的结束前完成。我们使用周作为一个时间周期的长度，主生产计划包含6个月的时间跨度。

三、整数规划模型

在本小节中，我们基于上文中的主生产计划问题引入了一个整数规划模型

1. 决策变量，参数及目标函数

首先，我们先设定一些重要的模型纬度。以下模型纬度被加以考虑：

在这里我们用公式kmax = CTmax -1 来定义变量 kmax, 假设，我们能将所有产品的最长生产周期缩小到一个时间周期。我们可以引入以下决策变量：

目标函数是由于追加的销售预测而获得的营业额与成本之间的差值(制造，库存，未完成的订单以及选择不同生产工厂的成本)。

2. 约束条件

以下一些条件约束被考虑到我们的主生产计划模型。

首先，我们加入库存平衡：

这个约束能够确保只有在需要的情况下一批产品才会在一个以上的工厂生产。

将非负约束及布尔约束加入模型，我们得到：

四、结论与展望