第四章整数规划讲稿11

理解：几何级数的惊人增长：复式利率
2）解IP，首先想到解其松弛问题。似乎只要把 已求得的解经过四舍五入或截去小数来简单取整数 就可以，但这常常是不可行的。 （看书上的例子了 解凑整的意思）
因为化整后不见得是可行解，或虽然是可行解， 但不一定是最优解；当变量较多时，凑整工作量也 很大。这种方法，只有在变量的取值很大时，才有 成功的可能性，而当变量的取值较小时，特别是0-1 规划时，往往不能成功。
约束条件：s.t.
x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0
3.设备购置问题 某厂拟用Ｍ元资金购买m种设备Ａ 1 ,Ａ 2 , … , Ａ m， 其 中 设 备 Ａ i 单 价 为 pi(i=1,2,…,m)，现有n个地点Ｂ 1 ,Ｂ 2 ,…, Ｂn可装置这些设备，其中Ｂj处最多可装置 bj(j=1,2,…,n)台．预计将一台设备Ａ i 装 置Ｂ j 处可获利cij 元．问应如何购置这些设 备，才能使预计总利润为最大？ 设：yi为购买设备Ai的数量,xij为将设备Ai 装置在Bj处的台数；总利润为Ｚ，则该问题 的数学模型为：
（Min z = ijxij ）
令位于不同行不同列的那组m个零元素所对应的xij =1, 其余xij =0。因此寻找独立的零元素是解题的中心。
定理1（指派问题最优解的性质）：设 (ij)是指派问题的 系数矩阵， ij 0，i , j = 1 , 2, ··, m。若从(ij)的某一行 ·· ·· （列）各元素中分别减去（或加上）一个常数而得到新矩 阵 (bij) ，那么以新矩阵 (bij) 为系数矩阵的指派问题求解 的最优解与用原系数矩阵求解的最优解相同。
2、混合整数规划(Mixed Integer Programming )：要求 部分决策变量取整数的LP。
3、0-1型整数规划：决策变量只取 0、1 的整数规划。
三、求解
1、整数规划是数学规划中一个较弱的分支，它的求解要 比一般的线性规划困难得多，到目前为止还没有一个十 分有效的解法，只能对一些特定的问题提出求解的方法。 而且目前只能解中等规模的线性整数规划问题，而非线 性整数规划问题，还没有好的办法。专门方法：分枝定 界法、割平面法、隐枚举法、匈牙利法。 2、但在实践中，许多问题可以归结为IP。由于决策问题 中经常有整数要求，如人数、件数、机器台数、货物箱 数……如何解决？因此，对求最优整数解的问题，有必 要另行研究。它作为数学规划论的一个重要分支，近二 十多年发展起来了。
• 某集装箱运输公司，箱型标准体积24m ，重量13T,现有两种货物可以装运，甲 3 货物体积5m 、重量2T、每件利润2000 3 元；乙货物体积4m 、重量5T、每件利 润1000元，如何装运获利最多？ • maxZ=2000x1+1000x2 5x1+4x2≤24 2x1+5x2 ≤13 x1 ， x2 ≥0且为整数 • 解此IP的松弛问题，得： x1 =4.8， x2 =0 • 显然不是可行解
第四章 整数规划(Integer Programming ，简称为IP） 本章要求 • 理解整数规划的含义； • 掌握分配问题的匈牙利算法； • 掌握割平面法； • 掌握分枝定界法的思想和方法； • 掌握0-1变量的含义和用法。
§1
整数规划问题的提出
在线性规划问题中，所有的解都假设为具 有连续型的数值，即解可以是整数、分数或 小数。但对于某些具体的问题，常要求最优 解是整数的情形。例如，所求的解是机器台 数，完成工作的人数或装货的车数等，还有 逻辑变量，只允许取整数值的一类变量，比 如x=1或0。这时，分数或小数的解就不符合 要求。
•
m n
• •
•
Max z = n
cij xij
i=1j=1
•
•
•
•
s.t. xij – yi = 0 , i = 1,2,…,m
j=1
m
• •
xij ≤ bj , j = 1,2,…,n
i=1 pi yi ≤ M
• •
xij ,yi ≥ 0 且均为整数 这是一个纯整数规划问题。
4、背包问题( Knapsack Problem)
设司机和乘务人员分别在各时间段一开始时上班，并连 续工作8h，问该公交线路怎样安排机和乘务人员，既能 满足工作需要，又配备最少司机和乘务人员?
解：设 xi 表示第i班次时开始上班的司机和乘 务人员数,这样我们建立如下的数学模型。
目标函数：minZ= x1 + x2 + x3 + x4 + x5 + x6
8
16
11
13
9
类似的有：m项加工任务，怎样指派到 m 台机床上分 别完成的问题；m条航线，怎样指定 m 艘船去航行的问 题，m若干项合同需要选择若干个承包者··等等。它们 ·· ·· 的基本要求是满足特定的指派条件下，指派方案的总体效 果最佳（时间最少、效率最高、成本最低等）。这类问题 性质相同，称为指派问题或分配问题。 对应每个指派问题, 都有类似上表那样的表格，我们 称之为效率矩阵或系数矩阵（coefficient matrix），其元 素 ij ( i , j = 1,2, ··, m) 表示指派第 i 个人去完成第 j ·· ·· 项任务时的效率(或时间、成本等)。
s.t. Σajxj b xj=0 或1
例：一登山队员做登山准备，他需要携带 的物品有：食品，氧气，冰镐，绳索，帐 篷，照相机和通讯设备，每种物品的重要 性系数和重量如下：假定登山队员可携带 最大重量为25公斤。
序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 相机 设备 重量 重要 系数 5 20 5 15 2 18 6 14 12 8 2 4 4 10
一个旅行者,为了准备旅行的必须用品,要在背包内装一 些最有用的东西,但有个限制,最多只能装b公斤的物品,而 每件物品只能整个携带,这样旅行者给每件物品规定了一 个“价值”以表示其有用的程度,如果共有n件物品,第j件 物品aj公斤,其价值为cj。问题变成:在携带的物品总重量不 超过b公斤条件下,携带哪些物品,可使总价值最大? 解：如果令xj=1表示携带物品j，xj=0表示不携带物品j， 则问题表示成0-1规划: Max Z = Σcjxj
3
整数规划图解法
x2
3 2
1
1 2 3
示
A（4.8，0）点是LP问题的可行解，不是IP问题的 可行解，B（4，1）才是IP的最优解 纯整数规划的可行解就是可行域中的整数点 非整数点不是可行解，对于求解没有意义，故切割 掉可行域中的非可行解，不妨碍整数规划问题的优 化 IP问题的最优解不优于其松弛问题的最优解


i=1 j=1
m s.t. xij = 1 j=1 m i = 1,2,…,m


xij = 1
i=1
j = 1,2,…,m (i=1,2,…,m;j=1,2,…,m)
xij = 0 或1
对每一问题的可行解，可以用解矩阵表示。 指派问题的解矩阵应当是每行或每列只能有一 个元素为1，其余均为 0 的m 阶方阵。如下就是 例子的一个解矩阵：
除上述四类问题外，典型整数规划问 题还有下料问题、产品配套问题、工厂 选址问题、任务分配问题等等。关于分 配问题后面要专门介绍。
§2分配问题（Assignment Problem）
一、分配问题的标准形式及数学模型
在生活中经常会遇到这样的问题，某单位需 要指派m个人去完成m项任务，每个人只做一项 工作，同时，每项工作只由一个人完成。由于各 人的专长不同，每个人完成各项任务的效率也不 同。于是产生了应指派哪一个人去完成哪一项任 务，使完成m项任务的总效率最高（如所用的时 间为最少）。我们把这类问题称之为指派问题或 分配问题(Assignment Problem)。
四、整数规划的性质（一般指纯IP)
1、可行域为点集。
2、整数规划的解是可数个的，最优解不 一定发生在顶点。 3、整数规划的最优解的目标值不会优于 其松弛问题的最优解的目标值。(max不大 于，min不小于)
五、整数规划的典型问题
在现实生活的许多领域中 都有整数规划实例，这里仅 介绍其中的几个典型问题。
二、匈牙利解法
库恩（W.W.Kuhn）于1955年提出了指派问题的解法，他 引用了匈牙利数学家（D.Kö nig)的两个定理，因此称为 匈牙利法。以后方法虽然不断改进，仍沿用这个名称。 基本思路是：此解法从一个明显的事实出发，若效率矩 阵（所有元素≥0）中存在 m 个位于不同行不同列的零 （以下简称独立的零元素），就找到了最优解。
指派问题是 0—1规划的特例，也是运输 问题的特例，即 m = n ，ai = bj = 1。 运输问题是任务分配问题的松弛问题;任务 分配问题不但是整数规划，而且是01规划; 任务分配问题有m2个变量，2m个约束条件， 但有且只有m个非零解，是自然高度退化的。 可以用解整数规划、0-1规划或运输问题的方 法求解，但这样做太麻烦了，不合理。我们 利用指派问题的特点可以有更为简便的求解 方法。
例 :有一份中文说明书,需要译成英、日、德、俄四 种文字，分别记作 E、J、G、R 。现有 甲、乙、丙
丁四人，他们将中文说明书翻译成不同文字说明 书所需要的时间如下表所示。问应指派何人去完 成哪一项工作，使所需的总时间最少？
工作
人员
E 2 10
J 15 4
G 13 14
R 4 15
甲 乙
丙
丁
9
7
14
一、整数规划的定义：决策变量要求取整数的LP。
IP的松驰问题：任何IP，放弃整数要求后，所得到的 问题称为原IP的松驰问题（Slack Problem）或称作和原 IP相应的LP问题。 二、分类