整数规划范文(6篇)

整数规划篇1

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

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

Solving0-1IntegerProgrammingProblembyHybridParticleSwarmOptimizationAlgorithm

XUEFeng，CHENGang,GAOShang

(SchoolofComputerScienceandEngineering,JiangsuUniversityofScienceandTechnology,Zhenjiang212003,China)

Abstract:Theclassicalparticleswarmoptimizationisapowerfulmethodtofindtheminimumofanumericalfunction,onacontinuousdefinitiondomain.Theparticleswarmoptimizationalgorithmcombinetheidealofthegeneticalgorithmisrecommendedtosolve0-1integerprogrammingproblem.Allthe6hybridparticleswarmoptimizationalgorithmsareprovedeffective.EspeciallythehybridparticleswarmoptimizationalgorithmwithacrossstrategyAandmutationstrategyCisasimpleandeffectivebetteralgorithmthanothers.Itcaneasilybemodifiedforanycombinatorialproblemforwhichwehavenogoodspecializedalgorithm.

Keywords:particleswarmalgorithm;0-1integerprogrammingproblem；knapsackproblem;geneticalgorithm;mutation

1引言

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

20-1整数规划问题数学模型

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

minf(x1,x2,…,xn),

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

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

粒子群优化(PSO,particleswarmoptimization)算法是一种进化计算技术，最早是由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

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

minT=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=100101111001，

old2=011010101100。

交叉区域为01011，交叉后为

new1=100100101101。

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

如原来解为100101111001，随机产生区域为1100，则变异操作后的解为

100101100111。

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

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

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

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

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

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

4)forj=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=269g，{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］EberhartRC，KennedyJ.Anewoptimizerusingparticlesswarmtheory［A］.ProcSixthInternationalSymposiumonMicroMachineandHumanScience［C］.Nagoya,Japan,1995.30~43

［7］ShiYH,EberhartRC.Amodifiedparticleswarmoptimizer［A］.IEEEInternationalConferenceonEvolutionaryComputation［C］.Anchorage,Alaska,1998：69-73

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

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

整数规划篇2

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

中图分类号：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.

整数规划

关键词：仓库；选址；混合整数规划法

伴随着经济的发展，我国零售业诞生了许多不同形式的连锁零售业态，同时，也将零售业市场推到白热化竞争状态。如今，连锁零售业的竞争已由店前发展到店后，变成物流配送体系的竞争。而在物流体系中，仓库作为衔接供应链上下游的环节，起到了至关重要的作用，所有的物流活动几乎都是围绕它来进行。合理的仓库选址可以有效地节省企业经营的各项费用，保证物流系统的高效运作。因此，通过合理的优化算法来选择仓库地址具有十分重要的意义和应用价值。

一、广西南宁市A便利店有限公司仓库选址现状

1.公司现状简介

广西南宁市A便利店有限公司是一家从事商业贸易、连锁管理、信息咨询及相关培训业务的连锁企业，公司以特许加盟连锁方式发展分店，至今旗下拥有二十多家便利门店，其中公司直营12家。公司各门店分布如图1：

2.公司仓库现状分析

便利店在选址时，一般选择在居民区和办公区的要道，以为居民提供便利为宗旨。所以，公司能否保证店面的持续供货是发展的关键因素。为了满足各门店商品需求，企业仓库选址一般优先选择在可以辐射到各个门店的地方。

广西南宁市A便利店有限公司目前在南宁市建政路租有一个仓库（如图1绿色标注所示），仓库为企业老板之前租住的公寓套房改用而成，供旗下12家门店的货物配送。仓库地处一个居民小区内，面积为70平米的一房一厅套房，仓库内布局混乱，没有作业功能区域划分，仓库的设备设施相对落后，仓库货物不分区存储，储存物品品种繁多，单品种货量存储少，货物堆放凌乱。

公司目前配送分为单双期配送，将12家门店按所在区域不同划分为两条路线配送，其操作流程为：首先，各门店店长依据销售情况按公司要求在规定的配送日前一天通过系统向仓库发送商品需求信息；其次，仓库接到信息，整理信息，汇总各门店订货数量，再根据仓库库存量分拣各门店的商品数量；最后，次日下午联系司机安排货物配送。若门店错过发送商品信息时间，便只能等待下一个配送日配送，或者商品量很大的情况下单独配送，或者门店自行到仓库提货。部分门店经常出现缺货现象。

3.公司仓库选址存在的问题

（1）随意性较强

在仓库选址前，公司没有综合的考虑门店的日均货物需求量、门店的分布情况等因素，选择较为轻率，仅凭公司领导的感觉，将仓库设立在自身周围闲余的空间内，将其仅仅当作一个单纯的收发货地，尚未认识到其真正的存在价值。

（2）租金成本较高

仓库建设费用为仓库选址主要考虑的因素之一，在满足仓库需求的情况下应该尽量选择建设费用低的地段。A公司将仓库选择在居民住宅小区内，租金成本偏高。

（3）交通便捷性较差

在连锁企业的物流体系中，每天具有出入库、交货等交通的压力，交通条件对物流的配送效率具有重要的影响，交通的不便将直接影响车辆配送的效率，从而导致门店的缺货。A公司仓库所在路段来往车辆频繁，路况严重拥堵，货车只能在规定的时间段通行，对门店需求的及时配送以及供应商对其的货物配送具有一定的影响。

（4）作业便捷性较差

仓库作为企业物流运作体系中的枢纽，每天都得处理大批量的货物，因此，需要给货物的存储、装卸搬运以及配送车辆停靠留有空余的空间。仓库地处居民小区内，货车的经常出入o周边居民带来诸多不便。

（5）扩展性差

连锁便利店仓库不仅要满足当下各门店供货需求，还应满足连锁店扩张的需要，即要求仓库要有好的扩展性。A便利店有限公司仓库处于居民小区楼内，面积小，仅为70平米，储存物品品种繁多，单品种货量存储少，难以满足各门店的供货需求，周边没有空置房源，仓库没有扩展空间，不能满足门店供货扩张的需求。这些都制约着A公司的经济效益的提升，长远来看，将成为阻碍公司发展的重要因素之一。

公司现有的仓储设施的不足将影响其为各门店提供优质的服务，重新规划企业仓库的选址变得尤为重要，合理的仓库选址对于提高门店服务水平和经济增长有着重要的意义。

二、混合整数规划法选址模型建立

通过对连锁便利店仓库的业务和数据分析可知，其物流配送一般具有以下特点：商品品种繁多、单店商品需求量小、物流配送频率高、配送点多且散、配送时间快等。鉴于以上特点，连锁便利店企业仓库辐射范围小，其通常和需求点的距离较近，其服务主要是能及时满足各个便利门店的供货需求。因此，这类仓库在选址时，不仅仅只考虑物流成本的降低，还得考虑是否能及时为其服务的各个门店提供服务。本文只针对考虑企业仓库到需求点的单因素配送情况进行分析，这过程涉及的影响因素主要考虑从仓库到门店的运输费用和仓库固定建设费用两个部分以及配送时间的长短。

为了寻求合适A便利店有限公司仓库的地址，笔者通过调查分析，综合考虑了四个层面：（1）门店的分布状况，门店的分布区域是选址的重要因素之一，选址应尽量靠近门店一些，特别是在门店比较集中的地方设置仓库；（2）配送服务条件及成本，依据门店供货时间要求，计算从仓库到门店的距离和时间，保证配送及时，满足门店货源需求，为顾客提供及时便捷的服务，同时保证配送成本的控制；（3）仓库租金费用，同一地区不同地段房源各不相同，租金也不一样，此外，还得考虑周边是否留有未来发展的空间；（4）交通条件，一方面在选址时要充分考虑周边的交通运输条件的便利性，以提高配送效率，缩短配送运输时间，另一方面还要考虑仓库与周边交通条件的协调性，因为连锁便利店仓库每天输送货物的频率较大，对周边的交通道路会有一定的影响。最终选取了3个备选地址，为了在这3个备选地中选出最合适的地址作为公司的仓库地址，收集了一些相关的数据，对3个备选地和目前仓库做一个定量比较分析，希望从中选出一个合适的地址。

1.问题描述

广西南宁市A便利店有限公司，旗下设有12个连锁门店（如图1红色标注所示），用j1-j12表示，其坐标及门店日需求量（将各种不同的商品均转化为重量来记）如下表1所示。1个现有仓库（如图1绿色标注所示）、3个仓库备选点（如图1蓝色标注所示），分别用i1-i4表示，其坐标及现有仓库和备选仓库的固定投资费用如下表2所示。单位产品从仓库到门店的运价因为都在市内，单位运价均为1，各门店到仓库备选点的距离（根据谷歌地图驾车路线实际距离为准）如表3，各门店到仓库备选点的配送时间如表4（配送时间=距离/速度，假设车辆行驶速度为35km/h）。要求在备选仓库中选择一个仓库，在能够及时满足所有门店需求的前提下，使得总费用最小以及所用时间最小。

（3）符号说明

与上一模型相同的字母表示相同的意义

L――供应商的数量；

Wki――从供应商k到仓库i的运输量；

Ak――供应商k的供应量；

Cki――单位产品从供应商k到仓库i的配送费用；

gi――仓库i单位流转量的管理费用；

Tki――供应商k到仓库i的配送时间；

Tij――仓库i到门店j的配送时间。

（4）模型解释

式（1）表示供应商到仓库到门店的运输成本和固定建设成本之和最小；

式（2）表示供应商到仓库到各门店配送的时间之和最小；

式（3）表示从供应商k向仓库提供的产品量不能超过其自身的供应能力；

式（4）表示仓库配送出的产品量与其从供应商的进货量相等；

式（5）表示所有需求点的需求都能得到满足；

式（6）表示仓库i向外配送的物资总量不能超过其自身容量；

式（7）规定了仓库建设数量的上限。

3.计算求解

将企业数据代入上式通过计算可知，选择目前的仓库i1的总成本为10722.86元，配送所需时间之和为1.36h；备选地i2的总成本为14498.33元，配送所需时间之和为1.84h；备选地i3的总成本为9546.40元，配送所需时间之和为1.20h；备选地i4的总成本为10228.33元，配送所需时间之和为1.32h。

4.广西南宁市A便利店有限公司仓库选址方案

根据计算比较分析，选择备选地i3作为公司仓库的情况下总成本最小，为9546.40元，配送花费时间也是最少，为1.2h。所以理论上i3为几个选择点中的最佳点。公司可以考虑将仓库搬到i3点处。

三、优化方案评价

现有仓库i1与三个备选地i2、i3、i4几个方面比较分析如下：

1.交通便利方面：i1处于路段拥堵地段；i2较为偏远，路况不算拥挤；i3、i4均处于大道附近，路况车辆不算拥挤，四周交通网较好。

2.仓库容量方面：i1面积太小，货物容纳量小，商品周转速度快，供应商配送次数频繁，配送成本较高；i2、i3、i4面积较大，货物容量较多，可满足门店货物的需求量。

3.与门店网络的距离情况：i1与各门店的距离较为集中，i2、i3、i4与各门店的距离较为分散。

4.成本方面：i1处于较中心地段，仓库租金成本偏高，i2、i3、i4处于较偏地段，租金成本相对较低。

连锁便利店的物流配送具有商品品种多、批量小、配送频率高、配送网点分散、适时快速配送等特点，这些特点要求企业必须有一个合理的仓库作为后盾。综合以上各方面因素分析，i3是A公司仓库最佳的选址点。

四、结论

仓库是连接连锁企业总部和各个门店的商品业务纽带，在连锁企业中起着承上启下的作用。所以在企业物流系统分析中，仓库选址是核心内容，仓库合理的选址能够减少运输成本，降低营运成本，从而提高利润。同时，合理的配送仓库可以使企业物流系统有效运转，为企业提供优质服务。

参考文献：

[1]皱德玲，倪晓峰。连锁零售企业配送中心选址研究[J].2010.

[2]蒋利军，蒋明，赵正佳。配送中心选址问题研究文献综述[J].物流科技期刊，2011.

整数规划篇4

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

一、引言

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

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

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

二、问题的阐述及假设

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

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

三、整数规划模型

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

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

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

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

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

2.约束条件

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

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

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

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

四、结论与展望

整数规划篇5

Abstract：Thispaperintroducestheloadingandhandlingequipmentinlogisticscentre.Ittakestheoperationalcostandoperationcapabilityasthegoaltoconsidertheactualfactorsofutilizationrateloadratio，configurationcoefficient，alternateoperation，establishanoptimizationmodelforallocatedquantityofhandlingequipmentbasedonintegerprogramming.Atlast，anumericalexampleispresentedbysteellogisticscentre，whichshowsthatthemethodputforwardinthepaperisfeasibleandeffective.

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

Keywords：logisticscenter；handlingequipment；optimizationofallocatedquantity；integerprogramming

中图分类号：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

整数规划篇6

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

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

Abstact：Variables（allorpart）islimitedtoaninteger，calledintegerprogramming.Ifthelinearmodel，limitedtoanintegervariable，iscalledlinearintegerprogramming.Branchandboundalgorithmisanimportantmethodtosolveintegerprogramming.However，theefficiencyofthealgorithmneedstobeimproved.Thepaperelaboratesthestepsofsolvinglinearintegerprogrammingproblembythemethodofbranchandbound，thenthroughthenachievebranchandboundmethodforparallelizationofalgorithmsintheuseofparallelismsupportedbymatlab.Analysistherunningtimeofbothbeforeandafterparalleltostudytheparallelizationalgorithmsforefficiency.

Keywords：linearintegerprogramming；branchandbound；matlab；algorithmefficiency；parallelprocessing

1分支定界法简介

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

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

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

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

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

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

2在matlab中并行化的实现

2.1Matlab并行计算的基本概念

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.2Matlab中的并行计算支持

为了支持并行计算，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]JackDongarra.并行计算综论[M].北京：电子工业出版社，2005

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

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

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

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

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