运筹学线性规划论文-用Flexsim求解整数线性规划问题

摘 要:为了进一步开拓思路,探索物流仿真软件Flexsim在更深层次和更广范围的应用,基于一个简单的整数线性规划例题建立了相应的仿真模型,通过修改代码使该模型能够模拟例题中阐述的问题,最终利用实验器实现了对枚举法的模拟。仿真结果得出的最优方案与传统方法计算的结果一致。由此可知,当整数线性规划问题比较简单时,应用Flexsim建立对应的模型,利用实验器可以实现对该问题的求解。

关键词:Flexsim;实验器;整数线性规划

中图分类号:F253 文献标识码:A

Abstract: To further explore new ideas and explore the applications of Flexsim that is a logistics simulation software in deeper levels and wider dimensions, the author of this article has established a corresponding simulation model, based on a simple integer linear programming example. The model can simulate the problem set forth in the example by modifying the code. Using the experimental device, it has eventually realized the simulation of enumeration method. The optimal solution obtained by the simulation model is consistent with the result calculated by the traditional method. It can be seen that, when the integer linear programming problem is relatively simple, a corresponding simulation model set up by Flexsim can solve the problem with the help of the experimental device.

Key words: Flexsim; the Experimenter; ILP

0 引 言

Flexsim是一款优秀的离散事件仿真软件,一个优秀的分析工具。其研究的对象多是复杂的多目标系统,它可以将不同参数组合的运行结果输出后供分析者比较,从而选取较优的参数组合。由于Flexsim提供了实验器可以一次性将不同参数组合记录到模型中,并能经过快速后台运算后直接输出仿真结果报告,因此分析者可以在较短的时间内对各种方案进行比较。

目前,Flexsim已经在物流领域成功地进行了多类系统的建模与仿真分析,在制造业、服务业、交通运输业、军事等诸多方面得到了广泛应用,涉及整体规划、瓶颈分析、成本分析、流程优化、派车、派工等众多方向。利用Flexsim提供的有力工具建立模型,可以解决简单的整数线性规划问题,这在以往的文献中未见涉及。本文无意于寻找求解整数线性规划问题的新方法,只想借此问题开拓思路,探索Flexsim在更深层次和更广范围的应用。

1 整数线性规划

在线性规划问题中,有些最优解可能是分数或小数,但对于某些具体问题,常要求某些变量的解必须是整数。这种变量限制为整数的线性规划,称为整数线性规划。在整数规划中,如果所有变量都限制为整数,则称为纯整数规划;如果仅一部分变量限制为整数,则称为混合整数规划,本文探讨的案例为纯整数规划。

目前常见的整数线性规划算法有枚举法、割平面法、分枝定界法等[1]。能够对整数线性规划问题进行求解的软件有MATLAB、LINGO、LINDO等[2],也有学者用编程方式实现了对整数线性规划的不同算法。

2 问题描述

对一个简单的线性规划例题进行求解,例题描述如下:某物流企业要将货物包装成I、II两种规格,需要A、B两种原材料的数量、获利情况及两种材料数量限制见表1。问两种规格各包装多少件可获利最多?

3 求解思路

根据题意分析得,例题中的20单位A原料和8单位B原料应该由发生器一次性产生;而按两种规格包装的货物件数同样也要由发生器产生;不同规格与不同原料通过合成器进行匹配;最终获利需要根据题意修改相应代码来得到;而枚举法所列举的各种可能,可以录入到实验器中。

4 问题求解

根据上述思路建立如图1所示的模型。

其中,原料A、原料B分别表示A、B两种原材料的限制数量;货物1、货物2分别表示Ⅰ、Ⅱ两种规格产品的包装件数。到达方式均为“到达时间表”,并选择合适的临时实体种类。相关参数设置如表2所示。

由于受原料限制货物1、货物2的数量存在此消彼长的关系,因此,可将货物2的到达时间和数量设置为较大值,此时只需要调整货物1的数量即可实现对两个变量的同时调整。为了对临时实体加以区别,可以给各个发生器添加colorarray(item, value)的创建触发,即根据临时实体类型设置临时实体颜色。相关参数设置如表3所示。

开始实验并查看结果,如图2。此时,方案重复运行了5次,但由于模型中不含随机变量,因此各次的运行结果均相同,所以方案重复运行次数完全可以设为1,对于枚举数量较多的情况,这样设置可以大大节省运算时间。

从实验结果可知,方案5可使获利最多,可获利48元。至此可知最优方案为规格Ⅰ包装4件,规格Ⅱ包装0件。对于更复杂的情况,上述方法在一定范围内同样有效,在此不多赘述。

参考文献:

[1] 黄振侃,唐薇. 整数线性规划算法的计算机实现[J]. 北京工业大学学报,1994(1):80-85.

[2] 雍龙泉. 求解线性规划的几种方法[J]. 江西科学,2007,25(2):202-205,212.


 

更多