整数规划 发表评论(0) 编辑词条

整数规划(integer programming)

　　整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支. 整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。

　　一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。

　　整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。

　　0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。

　　整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、送货问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

　　整数规划又分为：

　　1、纯整数规划：所有决策变量均要求为整数的整数规划

　　2、混合整数规划：部分决策变量均要求为整数的整数规划

　　3、纯0－1整数规划：所有决策变量均要求为0－1的整数规划

　　4、混合0－1规划：部分决策变量均要求为0－1的整数规划

　　整数规划与线性规划不同这处只在于增加了整数约束。不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型。

　　在现实生活中，决策变量代表产品的件数、个数、台数、箱数、艘数、辆数等等，则变量就只能取整数值. 如截料模型实际上就是一个整数规划模型，该例的决策变量代表所截钢管的根数，显然只能取整数值。因而整数规划模型也有着广泛的应用领域，从 以下的几个例子中更可以窥其一斑。

　　[例1]　　某厂在一计划期内拟生产甲、乙两种大型设备. 该厂有充分的生产能力来加工制造这两种设备的全部零件，所需原材料和能源也可满足供应，但A、B两种紧缺物资的供应受到严格限制，每台设备所需原材料如下 表所示. 问该厂在本计划期内应安排生产甲、乙设备多少台，才能使利润达到最大？

原料设备	甲	乙	可供资源数量
A（吨）	1	1	6
B（千克）	5	9	45
每台单位利润（万元）	5	6

　　解： 设x₁,x₂分别为该计划期内生产甲、乙设备的台数，Z为生产这两种设备可获得的总利润.显然x₁,x₂都须是非负整数，因此它是一个(纯)整数规划问题，其数学模型为：

　　max　　 Z = 5x₁ + 8x₂

　　s.t.　　x₁ + x₂6

　　　　　　5x₁ + 9x₂45

　　　　　　x₁,x₂ 0

　　　　　　x₁,x₂为整数

　　[例2]　　(投资决策模型)设有n个投资项目，其中第j个项目需要资金aj万元，将来可获利润cj万元。若现有资金总额为b万元，则应选择那些投资项目，才能获利最大？ 　　解： 设：

　　这里j＝1，2，…n设Z为可获得的总利润(万元)，则该问题的数学模型为：

　　max　

　　s.t.　

　　　　　x_j=0　or　1(j = 1,2,Λ,n)

　　[例3]　　(物资调拨模型)某厂拟用a元资金生产m种设备其中设备Ai单位成本为p_i (i＝1，2，…，m)。预计将一台设备A_i在B_j处销售可获利x_ij元，则应如何调拨这些设备，才能使预计总利润为最大？

　　解 设y_i为生产设备A_i的台数，x_ij为将设备A_i调拨到B_j处销售的台数，Z为预计总利润(元). 则该问题的数学模型为：

　　max　

　　s.t.　　　(i = 1,2,Λ,m)

　　　　　　　(j = 1,2,Λ,n)

　　　　　x_ij,y_i均为整数

　　[例4]　　(选址问题)某种商品有n个销地，各销地每月的需求量分别为bj吨(j＝1，2，…，n).。现拟在m个地点中选址建厂，来生产这种产品以满足供应，且规 定一个地址最多只能建一个工厂。若选址i建厂，将来生产能力每月为ai吨，生产成本每月为di元(i＝1，2，…，m). 已知从i至销地j的运价为cij元/吨. 应如何选择厂址和安排调运，能使总的最少？

　　解 设每月从厂址i至销地j的运量为x_{ij}吨，z为每月的总费用(元)，

　　则该问题的数学模型为：

　　min　　

　　s.t.　　　　(i = 1,2,Λ,m)

　　　　　　　　 (j = 1,2,Λ,m)

　　　　　　0　or　1

　　求解整数规划的一种自然的想法是，能否用整数规划的线性松弛模型的最优解经过四舍五入得到整数规划的最优解呢？回答是否定的，因为这样四舍五入的结果甚至不是可行解。

　　整数规划比通常的线性规划更加难以求解，迄今求解整数规划其基本求解思路都是按一定的搜索规则，在整数规划的线性松弛模型的可行域内寻找出整数最优解（或确认无整数最优解），因此求整数规划的解需要更多的时间，现通用的解法，主要有分支定界法、割平面法和穷举法等。