第六章_整数规划 (1)

整数规划的数学模型及解的特点

整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。

一、整数线性规划数学模型的一般形式

整数线性规划问题可以分为以下几种类型

1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划(zero—one integer liner programming)：指决策变量只能取值0或1的整数线性规划。

1 解整数规划问题

0—1型整数规划

0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi称为0—1变量，或称为二进制变量。

0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。

一、0—1型整数规划的典型应用问题

例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

序号 1 2 3 4 5 6 7

物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备

第二章 整数规划

§1 概论

定义

规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类

如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：

1o 变量全限制为整数时，称纯（完全）整数规划。

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

1.2 整数规划特点

（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：

①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例1 原线性规划为

其最优实数解为：45min,45,021zxx。

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

例2 原线性规划为

其最优实数解为：23min,23,021zxx。

若限制整数得：2min,1,121zxx。

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

求解方法分类：

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

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

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

②分枝隐枚举法。

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

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

下面将简要介绍常用的几种求解整数规划的方法。

§2 分枝定界法

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

第六章 整数规划

6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。

1、 max z=3x1+2x2

S.T. 2x1+3x2≤12

2x1+x2≤9

x1、x2≥0

解：

2、 min f=10x1+9x2

S.T. 5x1+3x2≥45

x1 ≥8

x2 ≤10

x1、x2≥0

6.2 求解下列整数规划问题

1、 min f=4x1+3x2+2x3

S.T. 2x1-5x2+3x3≤4

4x1+x2+3x3≥3

x2+x3≥1

x1、x2、x3=0或1

解：最优解（0，0，1），最优值：2

2、 min f=2x1+5x2+3x3+4x3

S.T. -4x1+x2+x3+x4≥2

-2x1+4x2+2x2+4x2≥4

x1+x2-x2+x2≥3

x1、x2、x3、x3=0或1

解： 此模型没有可行解。

3、max Z=2x1+3x2+5x3+6x4

S.T. 5x1+3x2+3x3+x4≤30

2x1+5x2-x2+3x2≤20

-x1+3x2+5x2+3x2≤40

3x1-x2+3x2+5x2≤25

x1、x2、x3、x3=正整数

解：最优解（0，3，4，3），最优值：47

4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+

5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19

约束条件 x1 + x2+x3≤30

x4+ x5＋ x6-10 x16≤0

x7+ x8＋ x9-20 x17≤0

x10+ x11＋ x12-30 x18≤0

实用标准文案

精彩文档 第五章 整数规划

主要内容：1、分枝定界法；

2、割平面法；

3、0－1型整数规划；

4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出

要求变量取为整数的线性规划问题，称为整数规则问题（简称IP）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题

211020maxxxz

为整数21212121,0,13522445xxxxxxxx

如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96max,0,8.421zxx。

实用标准文案

精彩文档 用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421xx）时得最优解为1,421xx，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。

§2 分枝定界法

分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A，与之相应的线性规划问题B，从解B开始，若其最优解不符合A的整数条件，那么B的最优值必是A的最优值*z的上界，记为z；而A的任意可行解的目标函数值是*z的一个下界z，采取将B的可行域分枝的方法，逐步减少z和增大z，最终求得*z。现举例说明：

例2 求解A

219040maxxxz