第七讲整数规划.ppt

湖州师范学院 五、指派问题与匈牙利法 第七讲 整数规划 例题 某公司有5项任务需要5个人来完成，要求完成任务的时间越短越好。每个人完成每项任务的时间如下表所示。问应如何安排5个人的任务，使完成5项工作的总时间最短。 6 8 8 5 7 E 8 4 13 5 6 D 6 4 9 5 7 C 7 12 14 8 6 B 3 13 6 7 10 A 戊 丁 丙 乙 甲 任务 人员 五、指派问题与匈牙利法 第七讲 整数规划 例题 解：需引入变量xij；其取值只能是1或0。并令 ： 则，数学模型为： 五、指派问题与匈牙利法 第七讲 整数规划 指派问题的提出 指派问题是0-1规划的特例，另外，指派问题也是运输问题的特例；即n=m,ai=bj=1。 这样，指派问题当然可用整数线性规划，0-1规划或运输问题的解法去求解，这就如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。 五、指派问题与匈牙利法 第七讲 整数规划 匈牙利法 定理1：若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。 定理2：若矩阵A的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素（独立0元素）的最大个数。 五、指派问题与匈牙利法 第七讲 整数规划 匈牙利法 利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到z=0，它一定是最小。 这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。 湖州师范学院商学院 运筹学（operations research, OR） 第七讲 整数规划 商学院电子商务系 第七讲 整数规划 一. 整数规划问题的提出 二. 分枝定界法 三. 割平面法 四. 0-1型整数规划 五. 指派问题与匈牙利法 第七讲 整数规划 一、整数规划问题的提出 整数规划数学模型及其分类 在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。 为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。 因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming)，简称ILP。 一、整数规划问题的提出 第七讲 整数规划 如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming) 整数规划数学模型及其分类 如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programming)。 整数线性规划的一种特殊情形是0-1规划，即变量的取值仅限于0或1。 一、整数规划问题的提出 第七讲 整数规划 现举例说明用单纯形法求得的解不能保证是整数最优解。 整数规划数学模型及其分类 例题：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱，可使获得利润为最大? 10 20 利润 13 5 2 重量 24 4 5 体积 托运限制 乙 甲 货物 一、整数规划问题的提出 第七讲 整数规划 例题 解：设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)，这就是一个(纯)整数线性规划问题，用数学模型可表示为： 一、整数规划问题的提出 第七讲 整数规划 容易求得相应的线性规划问题的最优解为：