赵丽颖详细资料大全 整数规划详细资料大全

整数规划详细资料大全  

整数规划是指规划中的变数（全部或部分）限制为整数，若线上性模型中，变数限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划。

一类要求问题的解中的全部或一部分变数为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。

基本介绍

中文名：整数规划外文名：integer programming所属领域：数学、运筹学定义：线性模型中，变数限制为整数套用举例：0-1规划分类举例：二次、非线性、线形 定义,发展历程,分类,常用算法,套用举例,组合最最佳化,0—1规划,

定义

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

发展历程

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

分类

整数规划又分为： 1、纯整数规划：所有决策变数均要求为整数的整数规划 2、混合整数规划：部分决策变数均要求为整数的整数规划 3、纯0－1整数规划：所有决策变数均要求为0－1的整数规划 4、混合0－1规划：部分决策变数均要求为0－1的整数规划 整数规划与线性规划不同这处只在于增加了整数约束。不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型。

常用算法

单纯形算法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函式值更高的另一个顶点，直至到达最优解为止。虽然这个算法在实际上很有效率，在小心处理可能出现的“循环”的情况下，可以保证找到最优解，但它的最坏情况可以很坏：可以构筑一个线性规划问题，单纯形算法需要问题大小的指数倍的运行时间才能将之解出。事实上，有一段时期内人们曾不能确定线性规划问题是NP完全问题还是可以在多项式时间里解出的问题。 第一个在最坏情况具有多项式时间复杂度的线性规划算法在1979年由前苏联数学家Leonid Khachiyan提出。这个算法建基于非线性规划中Naum Shor发明的椭球法（ellip-soid method），该法又是Arkadi Nemirovski（2003年冯‧诺伊曼运筹学理论奖得主）和D. Yudin的凸集最最佳化椭球法的一般化。 理论上，“椭球法”在最恶劣的情况下所需要的计算量要比“单形法”增长的缓慢，有希望用之解决超大型线性规划问题。但在实际套用上，Khachiyan的算法令人失望：一般来说，单纯形算法比它更有效率。它的重要性在于鼓励了对内点算法的研究。内点算法是针对单形法的“边界趋近”观念而改采“内部逼近”的路线，相对于只沿着可行域的边沿进行移动的单纯形算法，内点算法能够在可行域内移动。 1984年，贝尔实验室印度裔数学家卡马卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚少，在实际套用中它却表现出色。 单形法沿着边界由一个顶点移动到“相邻”的顶点，内点算法每一步的移动考量较周详，“跨过可行解集合的内部”去逼近最佳解。当今的观点是：对于线性规划的日常套用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。 线性规划的求解程式在各种各样的工业最最佳化问题里被广泛使用，例如运输网路的流量的最最佳化问题，其中很多都可以不太困难地被转换成线性规划问题。

套用举例

组合最最佳化

组合最最佳化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆蓋问题）、旅行推销员问题, 车辆路径问题等。因此整数规划的套用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多套用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的套用。

0—1规划

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