4.整数规划与分配问题

第四章 整数规划与分配问题

对于线性规划问题，最优解可能是分数或小数。 但是对于某些问题，会要求解答必须是整数 (称为整数解 整数解)。 整数解对于所求解是机器的台数、完成工作的人数、 对于所求解是机器的台数、完成工作的人数、装货 的车数、集装箱数量等； 的车数、集装箱数量等； 对于一些决策变量必须取Boolean值时 值时， 对于一些决策变量必须取Boolean值时，如要不要 在某地建工厂，可选用一个逻辑变量x, 在某地建工厂，可选用一个逻辑变量 ，令x=0表示 表示 不在该地建厂， 表示在该地建厂。 不在该地建厂，x=1表示在该地建厂。 表示在该地建厂

这时，分数或小数的解就不合要求， 这时，分数或小数的解就不合要求，我们称这 样的问题为整数规划 整数规划。 样的问题为整数规划。

例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、 某厂拟用集装箱托运甲乙两种货物，每箱的体积、 重量、可获利润以及托运所受限制如下表： 重量、可获利润以及托运所受限制如下表： 问两种货物各托运多少箱，可使获得的利润为最大？ 问两种货物各托运多少箱，可使获得的利润为最大？货物 甲 乙 托运 限制 体积 米3/箱 箱 重量 利润 百斤/箱 百元/箱 百斤 箱 百元 箱

MaxZ = 20 x1 + 10 x 2 ST : 5 x1 + 4 x 2 ≤ 24 2 x1 + 5 x 2 ≤ 13 x ,x ≥ 0,且为整数 1 2

5 4 24

2 5 13

20 10

能否先不考虑对变量的整数约束， 能否先不考虑对变量的整数约束，作为一般线性 规划来求解，当解为非整数的时候可以用“ 规划来求解，当解为非整数的时候可以用“四舍 五入” 凑整”方法寻找最优解？ 五入”或“凑整”方法寻找最优解？

对于变量取值很大时，用上述方法得到的解 对于变量取值很大时， 与最优解差别不大；但当变量取值较小时， 与最优解差别不大；但当变量取值较小时，得 到的解就可能与实际整数最优解差别很大。 到的解就可能与实际整数最优解差别很大。 当问题规模较大(决策变量较多) 当问题规模较大(决策变量较多)时，用 凑整”方法来算工作量很大。 “凑整”方法来算工作量很大。 例：某线性规划问题最优解为(x1, x2) = (4.6, 某线性规划问题最优解为 5.5),用凑整法需要比较与上述数据最接近的 ， 几种组合： 6), 几种组合：(4, 5), (4, 6), (5, 5), (5, 6), 共四种组合。若问题中有10个整数变量， 10个整数变量 共四种组合。若问题中有10个整数变量，则解 组合达到2 1024个整数组合 个整数组合。 组合达到210 = 1024个整数组合。且最优解未 必在这些组合中。 必在这些组合中。

例：求整数规划问题的最优解 max z =

3 x1 + 2 x2 2 x1 + 3 x2 ≤ 14 x1 + 0.5 x2 ≤ 4.5 x , x ≥ 0, 且均取整数值 1 2解：用图解法得最优解为(3.25 , 2.5) 如果不考虑整数约束( 如果不考虑整数约束(称为整数规划 问题的松弛问题 松弛问题) 问题的松弛问题) (4,1) 凑整法求解：比较四个点( 凑整法求解：比较四个点(4 , 3), ) ),前三个 (4 , 2),(3 , 3),(3 , 2),前三个 )( )( ), 都不是可行解，第四个虽然是可行 都不是可行解， 不是最优解。 解，但 z=13 不是最优解。

最优解为( 最优解为(4 , 1), z*= 14。 ), 。

主要内容一、整数规划的特点及作用 二、分配问题与匈牙利法 三、分枝定界法 四、应用举例

第四章 整数规划及分配问题

第一节 整数规划的特点及作用

一、整数规划的特点及作用

1.1 整数规划的概念整数规划(Integer Programming) :决策变 整数规划 量要求取整数的线性规划。如果所有的决策变量、技术系数和右端项都 是非负整数，就称为纯整数规划。 纯整数规划。 纯整数规划 如果所有的决策变量都是非负整数，技术系 数和右端项为有理数，称为全整数规划。 全整数规划。 全整数规划 如果仅一部分决策变量为整数，则称为混合 混合 整数规划。 整数规划。 如果变量取值仅限于0或1,称为0-1整数规划 0 整数规划。

一、整数规划的特点及作用

1.2 0-1整数规划某公司拟在市东、西、南三区建立门市部。拟 议中有7个位置(点)Ai供选择。规定在东区，由A1,A2,A3三个点中至多选两个； 在西区，由A4,A5两个点中至少选一个； 在南区，由A6,A7两个点中至少选一个。

如选用Ai点，设备投资估计为bi元，每年可获利 润估计为ci元，但投资总额不能超过B元。 问：应如何选址 选址，可使年利润为最大？ 选址

一、整数规划的特点及作用

1.2 0-1整数规划 1 解：设x j = 0 选Ai 不选Ai

MaxZ = c1 x1 + c 2 x 2 + + c7 x7 b1 x1 + b2 x 2 + + b7 x7 ≤ B x + x + x ≤ 2 2 3 1 ST : x 4 + x5 ≥ 1 x + x ≥ 1 7 6 x j = 1或0, ( j = 1, ,7)

0-1整数规划的一般形式 整数规划的一般形式: 整数规划的一般形式

MaxZ = C T X Ax = b ST : x j = 1或0, ( j = 1, , n)

0-1整数规划一般都 整数规划一般都 是纯整数规划。 是纯整数规划。

一、整数规划的特点及作用

1.3 整数规划的作用0-1整数规划在管理领域具有重要作用 整数规划在管理领域具有重要作用1. m个约束条件中只有 个起作用； 个约束条件中只有k个起作用 个约束条件中只有 个起作用； 2. 约束条件的右端项可能是r个值 1, b2, … br) 个值(b 约束条件的右端项可能是 个值 中的某一个； 中的某一个；

3. 两组条件中满足一组； 两组条件中满足一组； 4. 用以表示含固定费用的函数。 用以表示含固定费用的函数。

第四章 整数规划及分配问题

第二节 分配问题与匈牙利法

二、分配问题与匈牙利法

2.1 分配问题(1) 分配问题(1)指派n个人去完成 项任务 指派 个人去完成n项任务，使完成 n项任 个人去完成 项任务， 项任 务的总效率最高(或所需总时间最少 或所需总时间最少), 务的总效率最高 或所需总时间最少 ，这 类问题称为指派问题或分配问题 指派问题或分配问题。 类问题称为指派问题或分配问题。安排工作(派工):有 项加工任务 项加工任务， 安排工作(派工):有n项加工任务，怎样 ): 指派到n台机床上完成 台机床上完成； 指派到 台机床上完成； 条航线， 艘船去航行的； 有n条航线，怎样指定 艘船去航行的； 条航线 怎样指定n艘船去航行的 ……

二、分配问题与匈牙利法

2.1 分配问题(2) 分配问题(2)如果完成任务的效率表现为资源消耗， 如果完成任务的效率表现为资源消耗，考 资源消耗 极小化； 虑的是如何分配任务使得目标函数极小化 虑的是如何分配任务使得目标函数极小化； 如果完成任务的效率表现为生产效率的高 如果完成任务的效率表现为生产效率的高 则考虑的是如何分配使得目标函数最 低，则考虑的是如何分配使得目标函数最 大化。 大化。 在分配问题中， 在分配问题中，利用不同资源完成不同计 划活动的效率，通常用表格形式表示为效 划活动的效率，通常用表格形式表示为效 效率矩阵。 率表，表格中数字组成效率矩阵 率表，表格中数字组成效率矩阵。

二、分配问题与匈牙利法

2.2 分配问题实例(1) 分配问题实例(1)例：有一份中文说明书，需要译成英、日、德、 俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间 如下，问应指派何人去完成工作，使所需总时 间最少? 人员任务 译成英文 译成日文 译成德文 译成俄文 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9

二、分配问题与匈牙利法