第3章整数线性规划解读

数学中的线性规划与整数规划线性规划和整数规划是数学中两个重要的优化问题。

它们在实际生活和工业生产中有着广泛的应用。

本文将简要介绍线性规划和整数规划的概念、应用以及解决方法。

一、线性规划线性规划是一种优化问题，其目标是在给定的约束条件下，找到一个线性函数的最大值或最小值。

线性规划可以用来解决诸如资源优化分配、生产计划、物流运输等问题。

首先，我们来定义线性规划的标准形式：```最大化： c^Tx约束条件：Ax ≤ bx ≥ 0```其中，`c`是一个n维列向量，`x`是一个n维列向量表示决策变量，`A`是一个m×n维矩阵，`b`是一个m维列向量。

上述的不等式约束可以包括等式约束。

通过线性规划，我们希望找到一个满足所有约束的向量`x`，使得目标函数`c^Tx`达到最大或最小值。

解决线性规划问题的方法有多种，例如单纯形法、内点法等。

其中，单纯形法是应用广泛的一种方法。

它通过不断地移动顶点来搜索可行解的集合，直到找到最优解为止。

二、整数规划整数规划是线性规划的一种扩展形式，它要求决策变量`x`必须取整数值。

整数规划可以更准确地描述实际问题，并且在某些情况下具有更好的可解性。

例如，在生产计划问题中，决策变量可以表示生产的数量，由于生产数量必须为整数，因此整数规划更适用于此类问题。

整数规划的求解相对于线性规划更加困难。

由于整数规划问题是NP困难问题，没有多项式时间内的高效算法可以解决一般情况下的整数规划问题。

因此，为了获得近似最优解，通常需要使用一些启发式算法，如分支定界法、割平面法等。

三、线性规划与整数规划的应用线性规划和整数规划在实际生活和工业生产中有着广泛的应用。

以下列举几个常见的应用领域：1. 生产计划：通过线性规划和整数规划，可以确定产品的生产量、原材料的采购量以及生产时间表，以实现最佳的生产效益。

2. 物流运输：线性规划和整数规划可以用来优化货物的配送路线和运输方案，减少物流成本，提高配送效率。

整数线性规划现在有⼀个⼚家打算⽤集装箱托运甲⼄两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所⽰：其中，货物甲每箱 5 ⽴⽅⽶，重 200 ⽄，托运⼀箱可获利 2 千元，也就是 20 个百元；货物⼄每箱 4 ⽴⽅⽶，重 500 ⽄，托运⼀箱可获利 1 千元，也就是 10 个百元；由于集装箱的⼤⼩及承载量有限，只能托运不⼤于 24 ⽴⽅⽶且重量不超过 13 个百⽄的货物。

问两种货物各托运多少箱，可使获得利润为最⼤？显然这是⼀个最优化问题，⽬的是获取最⼤利润。

决策变量是托运甲、⼄两种货物的箱数，为此，我们设甲⼄两种货物分别托运x1箱和x2箱，于是⽬标就是求 1和 2，使得20x1 + 10x2最⼤。

注意到托运限制体积是 24 ⽴⽅⽶，因此5x1 + 4x2 ≤ 24；托运限制重量是 13，所以2x1 + 5x2 ≤ 13此外，我们还需要注意到托运的箱数必须⾮负；不仅如此，由于本题托运货物按箱计算，所以x1和x2还必须为整数。

因此本题的数学模型是：⽬标函数20 1 + 10 2取最⼤值，并且它受到 4 个约束条件的限制max\quad z=20x_1+10x_2\\ s.t. \begin{cases} 5x_1+4x_2\le 24\\ 2x_1+5x_2\le 13\\ x_1,x_2\ge 0,x_1,x_2\in Z \end{cases}这个模型和的线性规划⾮常像，唯⼀的区别是增加了对⾃变量是整数的限制，这类规划问题属于整数规划。

决策变量（全部或部分）限制为整数的规划称为整数规划。

整数规划的英⽂翻译是 integer program, 简称 IP。

若在线性模型中，变量限制为整数，则称为整数线性规划，即 ILP。

⽬前所流⾏的求解整数规划的⽅法往往只适⽤于整数线性规划。

整数规划⼜分以下四类：1. 纯整数规划：所有决策变量均要求为整数2. 混合整数规划：部分决策变量要求为整数3. 纯 0－1 规划：所有决策变量均要求为 0 或者 14. 混合 0－1 规划：部分决策变量要求为 0 或者 1整数规划与线性规划不同这处在于增加了整数约束。

第三章 整数线性规划【教学内容】整数线性规划问题举例、整数线性规划模型及其求解的困难性、可用线性规划求解的整数线性规划问题、求解整数线性规划问题的Gomory 割平面法、求解整数线性规划问题的分枝定界方法、0－1规划问题举例、0－1规划问题的解法、整数线性规划问题的一些例子、用LINGO 软件包求解整数线性规划问题。

【教学要求】要求学生熟悉整数线性规划模型，能熟练地掌握求解整数线性规划问题的Gomory 割平面法和分枝定界方法；熟悉并会求解0－1规划问题，能够建立整数线性规划模型并用软件求解整数线性规划问题。

【教学重点】整数线性规划模型，Gomory 割平面法，分枝定界方法，0－1规划问题。

【教学难点】Gomory 割平面法，分枝定界方法，0－1规划问题的求解。

【教材内容及教学过程】整数线性规划(Integer Linear Programming ，简记为ILP )问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。

其中变量只取0或1的整数线性规划问题称为0－1规划。

只要求部分变量取整数值的线性规划称为混合整数线性规划。

整数线性规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应的线性规划的最优解为出发点的。

但是变量取整数值的要求本质上是一种非线性约束，因此解整数线性规划的“困难度”大大超过线性规划，一些著名的“困难”问题都是整数线性规划问题。

本章主要介绍整数线性规划一些基本概念、基本理论、实际背景及常用算法。

第一节 整数线性规划模型§1．1 整数线性规划问题举例例3.1.1[2] 工地上需要长度为m l l l ,,,21 的钢材数分别为m b b b ,,,21 根，取长为l 的原材料进行截取。

已知有n 种截取方案：()12i iimi A a a a =，1,2,,i n =其中，ji a 表示一根原料用第i 种方案可截得长为j l 的钢材的根数（1,2,,i n =，1,2,,j m =），因此 1122i i m mi l a l a l a l +++≤，1,2,,i n =下料问题就是在满足要求：截取长度为m l l l ,,,21 的钢材数分别为m b b b ,,,21 根时，用的原料材根数最少的方案。

最新文件---------------- 仅供参考--------------------已改成-----------word 文本 --------------------- 方便更改 赠人玫瑰，手留余香。

整数线性规划理论§1 概论1.1 定义规划中的变量（部分或全部）限制为整数时，称为整数规划。

若在线性规划模型中，变量限制为整数，则称为整数线性规划。

目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类如不加特殊说明，一般指整数线性规划。

对于整数线性规划模型大致可分为两类：1o 变量全限制为整数时，称纯（完全）整数规划。

2o 变量部分限制为整数的，称混合整数规划。

1.3 整数规划特点（i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例1 原线性规划为 21m inx x z +=0,0,5422121≥≥=+x x x x其最优实数解为：45min ,45,021===z x x 。

LINGO1.lg4 LINGO11.lg4③有可行解（当然就存在最优解），但最优解值变差。

例2 原线性规划为 21m inx x z +=0,0,6422121≥≥=+x x x x 其最优实数解为：23min ,23,021===z x x 。

若限制整数得：2m in ,1,121===z x x 。

LINGO2.lg4 LINGO21.lg4（ii ） 整数规划最优解不能按照实数最优解简单取整而获得。

1.4 求解方法分类：（i ）分枝定界法—可求纯或混合整数线性规划。

（ii ）割平面法—可求纯或混合整数线性规划。

（iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。

（iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。

（v ）蒙特卡洛法—求解各种类型规划。