整数线性规划极其应用.2.doc.deflate.doc

整数线性规划及其应用目 录引言5第一节 整数线性规划模型611 整数线性规划问题举例612 整数线性规划模型6第二节 解整数规划问题的常用方法821 可用线性规划822 Gomory割平面法82.2.1 松弛问题的关系82.2.2 割平面法的基本思想82.2.3 Gomory割平面法的割平面条件92.2.4 Gomory割平面法计算步骤1023 求解整数线性规划问题的分枝定界方法102.3.1 分枝定界方法的基本思想102.3.2 分枝定界法计算步骤11第三节 01规划问题及其求解方法1331 01规划问题举例1332 建立数学模型1333 01规划问题的解法133.3.1 DFS搜索法133.3.2 隐枚举法15第四节 整数线性规划问题的应用164.1 分配问题164.2 旅行售货员问题174.3 最短路问题174.4 一维背包问题18第五节 怎样求解整数线性规划问题195.1 用LINGO求解线性规划问题195.1.1 模型的输入195.1.2 执行19文献综述22参考文献.22致谢.22- -2020-1-19整数线性规划及其应用李茂数学学院07级4班 指导老师：张森【摘 要】整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整数线性规划问题、求解整数线性规划问题的Gomory割平面法、求解整数线性规划问题的分枝定界方法、01规划问题举例、01规划问题的解法、整数线性规划问题的一些例子、用LINGO软件包求解整数线性规划问题。整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。其中变量只取0或1的整数线性规划问题称为01规划。只要求部分变量取整数值的线性规划称为混合整数线性规划。整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应的线性规划的最优解为出发点的。但是变量取整数值的要求本质上是一种非线性约束，因此解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规划问题。本文主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。【关键词】整数线性规划模型 Gomory割平面法 分枝定界方法 01规划问题Integer linear programming04 Grade, Mathematics institute, instructor:zhang sen【Abstract】The example Of Integer linear programming problem、integer linear programming model and the difficulty of it、the integer linear programming available solving linear programming problem、the integer linear programming problem solving gomory cut plane method、integer linear programming problem solving bound method of branches、the 0-1 programming problem with example、the 0-1 programming problem solution 、integer linear programming problem with some examples、 solving integer linear programming packages LINGO. When the Ilp research are variables integer value, in a group of linear constraints a linear functions optimal problem, it is very extensive an important branch of the operational research. In which the variable take 0 or 1 integer linear programming problem is called the 0-1 programming. Only require partial variable integer linear programming called numerical mixed integer linear programming.Integer linear programming and linear programming closely related, with some of its basic algorithm design are based on the corresponding linear programming for the starting point of the optimal solution. But variable requirements of integer value is essentially a nonlinear constraints, therefore solution integer linear programming difficulty considerably more than the linear programming, some of the famous difficulties problems are integer linear programming problem.This paper mainly introduces some integer linear programming basic concept, the basic theory and practical background and algorithms.【 keywords 】 integer linear programming model Gomory cut plane method bound method branching 0-1 programming problem引言 整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。2020-1-19第一章 整数线性规划模型11 整数线性规划问题举例 材料截取 工地上需要长度为的钢材数分别为根，取长为的原材料进行截取。已知有种截取方案：，其中，表示一根原料用第种方案可截得长为的钢材的根数（，），因此，下料问题就是在满足要求：截取长度为的钢材数分别为根时，用的原料材根数最少的方案。假定表示按方案截取用的原钢材数目，于是问题表示为： (1.1)在许多实际问题中，我们所研究的量具有不可分割的性质，如人数、机器数、项目数等；而开与关、取与舍、真与假等逻辑现象都需要用取值仅为0或1的变量来进行数量化的描述。涉及这些量的线性规划问题，非整数的解答显然不合乎要求。12 整数线性规划模型考虑如下形式的整数线性规划问题ILP (1.2)其中，以及，中的元素皆为整数。在(1.2)中除去为整数向量这一约束后，就得到对应的标准线性规划问题 (1.3)称(1.3)是(1.2)的松弛问题。如果(1.2)对应的标准线性规划问题(1.3)的最优解是整数，则它也是(1.2)的最优解。对于标准线性规划问题，已有有效的算法。那么能不能通过求解对应的线性规划问题，然后将其解舍入到最靠近的整数解呢？考察图1.1所示的情况，可以看出舍入方法是不可取的。图 1.1oooooooooooooooooooooooooooooooooooooooooooooooo既然ILP的可行域是一些离散的整数点（图1.1），如果其可行域有界，那么所包含的整数点的数目就是有限的，可否用枚举法来解ILP问题呢？对一般ILP问题，枚举法是无能为力的。如50个城市的旅行售货员问题（见例4.4），所有可能的旅行路线个数为，这是一个天文数字。由上可见，求解整数线性规划问题ILP比求解对应的线性规划问题LP要困难得多。事实上，整数线性规划模型并不是线性模型。仅以01规划而言，决策变量取值为0或1这个约束是可以用一个等价的非线性约束 (1.4)来代替的。因而变量限制为整数本质上是一个非线性约束。第二章 解整数规划问题的常用方法从1959年R.E.Gomory提出解整数线性规划的割平面算法至今，经过几十年的努力，已经发展起来了一些常用算法，如各种类型的割平面算法、分枝定界算法、解01规划的隐枚举法、分解方法、群论方法、动态规划方法等等，本章主要介绍求解整数线性规划问题的几个常用算法。21 可用线性规划可用线性规划问题求解的整数线性规划问题，实际上是这样的一类问题，它的解就是线性规划解，即可以通过单纯形法来求整数规划的解。因此，对于规划问题(1.2)，若系数矩阵为幺模矩阵，且右端项是整数，则可以用单纯形方法直接求解对应的标准线性规划问题(1.3)，就可以得到它本身的最优整数解。22 Gomory割平面法2.2.1 松弛问题的关系解整数线性规划问题的割平面法有多种类型，但它们的基本思想是相同的。以下我们介绍Gomory割平面法。它在理论上是重要的，被认为是整数线性规划的核心部分。设(1.2)的可行域为D，对应的松弛问题(1.3)的可行域为（多面凸集），当时它是由有限个或可数的整数点构成的集合。问题(1.2)和问题(1.3)之间具有如下明显的关系：；若问题(1.3)无可行解，则问题(1.2)无可行解；问题(1.3)的最优值是问题(1.2)的最优值的一个下界；若问题(1.3)的最优解是整数向量，则是问题(1.2)的最优解。2.2.2 割平面法的基本思想用单纯形法先解松弛问题(1.3)，若问题(1.3)的最优解是整数向量，则是ILP问题(1.2)的最优解；若问题(1.3)的最优解的分量不全是整数，设法构造一个线性约束条件（称它为割平面条件），新增加的这个割平面条件将问题(1.3)的可行区域割掉一块，且这个非整数解恰好在被割掉的区域内，而原ILP问题(1.2)的任何一个可行解（整数点）都没有被割去。给问题(1.3)增加这个约束条件，用得到的问题替换问题(1.3)，继续以上过程。 2.2.3 Gomory割平面法的割平面条件用单纯形方法求解问题(1.2)的松弛问题(1.3)，得到最优基本可行解，设它对应的基为，为基变量，基变量的下标集合为，非基变量的下标集合为。最优解所对应的问题(1.3)是 (2.1)为使符号简便计，令，。如果，全是整数，已经得到了问题(1.2)的最优解；否则至少有一个不是整数，设所对应的约束方程是 (2.2)我们用表示不超过的最大整数，则有 (2.3)其中（）是的分数部分；（）是的分数部分。由于方程(2.2)中的变量是非负的，因此有 (2.4)从而方程(2.2)变为 (2.5)因为为整数向量，故(2.5)式左端为整数，所以右端用的整数部分去代替后，(2.5)式的不等式关系仍成立，即有 (2.6)(2.2)减去(2.6)，得 (2.7)注意到(2.3)关系式，我们得到线性约束 (2.8)称它为对应于生成行的Gomory割平面条件。将(2.8)改写为（引进松弛变量）超平面方程(2.9) (2.9)称它为割平面。将割平面(2.9)加到问题(2.1)，就得到了一个新的线性规划问题，且已经具有满足最优性条件的基本不可行解。如果把割平面(2.9)加到问题(2.1)中，那么没有割掉问题(1.2)的任何整数可行点，当不是整数时，新问题是一个满足最优性条件的不可行基本解。 2.2.4 Gomory割平面法计算步骤第1步 求解问题(1.3)。若问题(1.3)没有最优解（包括无可行解和无有限最优解），则问题(1.2)也没有最优解；若问题(1.3)有最优解，且是整数向量，则是问题(1.2)的最优解，输出；否则转第2步。第2步 任选的一个非整数分量，按关系式(2.2)和(2.3)得到割平面方程 (2.10)第3步 将(2.10)加到第1步所得的问题(1.3)的最优形式(2.1)中，用对偶单纯形法求解这个问题。若其最优解为整数解，则它是问题的最优解，输出这个最优解；否则将这个最优解重新记为，返回第2步。若对偶单纯形算法发现了对偶问题是无界的，此时原ILP问题是不可行的。23 求解整数线性规划问题的分枝定界方法分枝定界法可用于解纯整数线性规划和混合整数线性规划，它是目前求解整数线性规划的成功方法之一。本章介绍该方法的基本思想和计算步骤。2.3.1 分枝定界方法的基本思想分枝定界法是以“巧妙”的枚举问题(1.2)的可行解的思想为依据设计的。与割平面方法类似，求解不是直接针对问题(1.2)，而是求解它的松弛问题(1.3)。设问题(1.3)的最优解为，则是问题(1.2)的最优值的一个下界。若的某个分量不是整数，由于问题(1.2)的整数最优解的第个分量必定落在区域或中，因此可将原问题(1.2)分为两个子问题来求解。这两个子问题是： (2.11)和 (2.12)这两个子问题将问题(1.2)的可行域分成两部分，且把不满足整数要求的问题(1.3)的最优解排斥在外。这一步称为分枝。分别用(2.11)和(2.12)代替原问题(1.2)，则分枝过程一直可以进行下去。每得到松弛问题的一个解，都会修正原问题目标函数最优值的下界。假设在某一时刻，到当时为止所得到的最好的满足整数要求解的目标函数值是（目标函数最优值的一个上界），而且我们正打算由某一点分枝，该点所对应的ILP的下界为，若，这意味着点的所有后代得到的各个解的目标函数值均有因此无须由继续分枝。在这种情况下，我们说已被剪枝。这个过程可以“巧妙”地减少一些不必要的分枝。总之，分枝定界方法的思想是按照下面三步进行的：第一步，通过求解松弛问题对原问题进行分枝；第二步，通过每个松弛问题的最优目标函数值对原问题的目标函数值定界；第三步，一旦某个松弛问题的最优解是整数，就得到原问题最优解的一个近似，其目标函数值就是原问题目标函数值的一个近似值（上界）。如果以后某个松弛问题的最优目标函数值比这个近似值大，那么这个松弛问题及它的所有子问题都不用求解了。之所以说分枝定界方法是“巧妙”的枚举方法，主要是因为“剪枝”步骤，通过“剪枝”步骤就不用枚举问题的所有可行解。2.3.2 分枝定界法计算步骤第1步 求解问题(1.3)。若问题(1.3)没有最优解（包括无可行解和无有限最优解），则问题(1.2)也没有最优解；若问题(1.3)有最优解，且是整数向量，则是问题(1.2)的最优解，输出；否则，令，转第2步。第2步 若，则转第7步，否则，选择一个分枝点，；第3步 解对应的松弛问题，若此问题无解，转第2步；第4步 若对应的松弛问题的最优值，则点被剪枝，转第2步；第5步 若对应的松弛问题的最优解为整数，则，转第2步；第6步 若对应的松弛问题的最优解不是整数，按某个非整数分量生成的两个分枝点和，令，转第2步；第7步 若，则原ILP问题无解；否则，为原ILP问题的最优解，是最优值，计算停止。分枝定界法的思想不仅适用于解ILP问题，也适用于任何组合最优化问题。第三章 01规划问题及其求解方法01规划是整数规划中的特殊情况，它的变量仅取值0或1。31 01规划问题举例某部门在今后五年中可用于投资的资金总额为万元，有个可以考虑的投资项目，假定每个项目最多投资一次，第个项目所需的资金为万元，将会获得的利润为万元。问应如何选择投资项目，才能使获得的总利润最大。3.2 建立数学模型设投资决策变量为设获得的总利润为，则上述问题的数学模型为 (3.1)显然，问题(3.1)是一个01规划。33 01规划问题的解法由于01规划问题的特殊性，虽然上面介绍过的割平面方法和分枝定界方法都可以用来求解，但是正是由于它的特殊性，这里介绍专门用来求解01规划问题的一些方法。3.3.1 DFS搜索法 用DFS搜索法求解整数规划问题（DFS是Depth First Search的缩写，即深度优先搜索的意思。典型的思想可以从下面例子看出）。 (3.2)首先确定搜索树，假定自上而下的搜索顺序为，引进栈用以记录搜索过程，栈是按后进先出的顺序来建立数据结构。属于栈的变量定义为固定变量。，属于的变量定义为自由变量。，作为约定栈顶元素为，中间为，栈底为。若从中取走栈顶元素，则取出的是，取走之后的为，栈顶元素则为。图1.1搜索空间即搜索树（如图3.1所示）。1) ，由于，和不论为0或1均不能满足。故应放弃。2) ，前进一步，再前进一步，。3) 从栈顶元素后退，改为，。4) 不满足约束，应放弃。5) ，前进一步为，应放弃。6) 进入，不满足约束，应放弃，故后退。直到，停止。故得最优解。3.3.2 隐枚举法用隐枚举法求解整数规划问题（隐枚举法是通过建立过滤条件而使计算工作量大为减少的穷举法，用下面的例题加以说明）。 (3.3)解题时，先通过试探的方法找一个可行解，容易看出就是合于条件的，算出相应的目标函数值。我们求最优解，对于极大化问题，当然希望，于是增加一个约束条件： (3.4)后加的条件称为过滤的条件。这样，原问题的线性约束条件就变成5个。用全部枚举的方法，3个变量共有个解，原来四个约束条件，共需32次运算。现在增加了过滤条件(3.4)，如按下述方法进行，就可减少运算次数，将5个约束条件按顺序排好（表3.1），对每个解，依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件就不必再检查，因而减少了运算次数。本例计算过程如表3.1，实际只作24次运算。表3.1点条 件满足条件？是（）否（）值（0）（1）（2）（3）（4）（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）05-233816-1110215126011101538于是求得最优解，。在计算过程中，若遇到值已超过条件(3.4)右边的值，应改变条件(3.4)，使右边为迄今为止最大者，然后继续作。例如，当检查点（0，0，1）时因，所以应将条件(3.4)换成 (3.5)这种对过滤条件的改进，更可以减少计算量。注：一般重新排列的顺序使目标函数中的系数是递增（递减）的。在上例中，改写，因为，3，5是递增的。变量也按下述顺序取值：（0，0，0），（0，0，1），（0，1，0），（0，1，1），这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化。第四章 整数线性规划问题的应用4.1 分配问题设有个人被分配去做件工作，规定每个人只做一件工作，每件工作只能由一个人去做。已知第个人去做第件工作的效率（时间或费用）为（；），并假设。问应如何分配才能使总效率（总时间或总费用）最高（最少）？设决策变量 那么第个人去做第件工作的效率为，从而即为总效率，（）表示每件工作都有人去做，（）表示每个人都有工作做；于是分配问题的数学模型为4.2 旅行售货员问题有一推销员，从城市出发，要遍访城市各一次，最后返回，已知从到的旅费为，问他应该按怎样的次序访问这些城市，使得总旅费最少？（设，为充分大的正数，）。对每一对城市和，我们指定一个变量，令该问题的数学模型为 (1.3)4.3 最短路问题设给定了一个有个章点，条弧的网络，每条弧的长度为。对给定的两个章点，设为和，找出从到的总长度最短的路。若用表示弧是否在这条路上，因此显然有或1，则问题的数学模型是4.4 一维背包问题有一个人带一个背包上山，其可携带物品重量的限度为。设有种不同的物品可供他选择装入背包中，已知第种物品的重量为，单位价值为（）。问此人应如何选择携带物品的方案，使总价值最大？设为第种物品的装入件数，则问题的数学模型是第五章 怎样求解整数线性规划问题5.1 用LINGO求解线性规划问题5.1.1 模型的输入使用LINGO求解上述整数规划模型，LINGO程序如下：MODEL:max=3*x1+4*x2+8*x3-100*y1-150*y2-200*y3;2*x1+4*x2+8*x3=500;2*x1+3*x2+4*x3=300;x1+2*x2+3*x3=100;3*x1+5*x2+7*x3=700;x1=200*y1;x2=150*y2;x3=300*y3;GIN(x1);GIN(x2);GIN(x3); BIN(y1);BIN(y2);BIN(y3);END 5.1.2 执行点击LINGO菜单下的SOLVE键，或按CTRL+S键，即可求得问题的解。此问题的解为：，最优值为：200。当运用LINGO求解此问题后，系统会弹出一个名为Solution Report的文本框，其文本框中包含了求解的详细信息，如下：Rows= 8 Vars= 6 No. integer vars= 6 ( all are linear)Nonzeros= 28 Constraint nonz= 18( 4 are +- 1) Density=0.500Smallest and largest elements in abs value= 1.00000 700.000No. : 0, Obj=MAX, GUBs = 3Single cols= 0Global optimal solution found at step: 4Objective value: 200.0000Branch count: 0 Variable Value Reduced Cost X1 100.0000 -3.000000 X2 0.0000000 -4.000000 X3 0.0000000 -8.000000 Y1 1.000000 100.0000 Y2 0.0000000 150.0000 Y3 0.0000000 200.0000 Row Slack or Surplus Dual Price