整数线性规划问题解法探究

引言

何谓“整数规划”？它的英文名称就是“Integer Programming”,就是研究在物流管理与运输问题、生产计划与管理、指派问题这些经营管理活动中,如何活动,如何用尽可能小的代价,去获得尽可能最好的结果,即为“最优化”问题。

物流管理与运输问题上,如何最优化地使用道路、车辆、人员、运输时间就是一个经典的整数规划问题。如果管理者能够最优化地使用这些条件,那么将会节省大量的人力物力财力,将会有更大的利润,而城市的道路也会变得宽松流畅,避开人流高峰期,减少车祸概率。

在社会发展中,线性规划影响着人们的生活,如工厂生产问题,工人的劳动时间,设备利用率都影响着该工厂的利润,合理地安排人员将会最大限度地增加利润;物流管理中,物流中心的定点决策。

T。C。Koopmans在1975年由于他们在线性规划中的工作也获得诺贝尔经济学奖,从此之后有更多优秀的学者去研究线性规划问题。 刁在筠 [1]等人全面的介绍了整数线性规划,以及整数线性规划的各种解法,胡清淮等学者[2]建立了目标规划模型根据对方案有相对的喜好的多属性决策问题,陈景艳等[3]根据新定义的贴近度等概念去计算所需的量进而可以排序选择各个方案．其中包括基于分枝定界法、匈牙利法、隐枚举法、割平面法等的多种解决整数线性规划问题的解法。对不确定性的概念,用混合线性规划表示更符合人类直觉与思维。将复杂的经济管理问题变的更加合理科学。但由于整数线性规划问题提出的时间较短,使得利用整数线性规划问题的文献还不是太多。因而基于整数线性规划问题解法探究的研究有着十分重要的意义。在文献[4]中,作者针对各类型的经济管理问题给出了具体的解决方法以及比较,具有非常重要的意义。论文网

本文的结构为:第一部分给出了线性规划的基本概念及理论知识。第二部分比较了分枝定界法、隐枚举法、割平面法、匈牙利法的思想方法及计算步骤。第三部分给出具体的实例,如:汽车厂生产问题、指派问题、投资问题分别来验证这几种解法的可行性、有效性、限制性。 最后是结论与展望。

1线性规划的理论知识                                                                                                                     

1。1线性规划的简介

随着经济的发展,如何利用有限的资源（财力、物力、人力等）获得最大的经济效果,达到最佳的组织目标是每一个管理者需要面临的问题,从中引出线性规划问题。从这些问题可以看出它们具有共同的特征[5]:

（1）有一组决策者可以控制的变量,;

（2）有一个目标函数,该目标函数是由决策变量组成的线性等式或不等式。

1。2线性规划的模型

或1。3线性规划的求解

一般在求解这种问题时,通常把该模型化为标准线性规划模型:

则标准典则形式的线性规划问题:

求解该问题的基本解法为正则形法、单纯形法、图解法,使得式取得最大可行解的为最优解。

2整数线性规划的简介及其解法

2。1整数线性规划的简介

整数线性规划（简记为ILP）即要求变量取整数值的线性问题。整数线性规划的模型:

其中为矩阵,

若上式为0-1规划问题;若则上式是纯整数线性规划问题。规范式和一般形式的ILP也可以类似定义。