电力-授课顾问博学院

引例：某厂利用集装箱托运甲、乙两种货物，每箱体积、重量、可获利润及托运限制如下：体积重量利润甲213乙30.52托运限制144.5两种货物各托运多少箱使利润最大？MaxZ=3x1+2x22x1+3x2≤14x1+0.5x2≤4.5x1,x2≥0x1,x2

为整数解:设能托运甲、乙两种集装箱分别为

箱,则

运筹帷幄之中决胜千里之外运筹学课件第四章整数规划

在许多线性规划问题中,要求最优解必须取整数.例如所求的解是机器的台数、人数车辆船只数等,这类问题即整数规划问题.

整数规划(integerprogramming)简称为IP问题.本章主要讨论的是整数线性规划问题,简称为ILP问题.

讨论整数规划对研究管理问题有重要意义，比如项目投资问题、人员分配问题等都可以化为一个整数规划问题。整数规划是近二、三十年来发展起来的数学规划的一个重要分支，可分为：

1)纯整数规划（所有变量都限制为整数）

2)混合整数规划（一部分变量限制为整数）注意:0—1规划（所有变量都限制取0或1）。整数规划问题的主要算法

1)割平面法

2)分枝定界法分配问题的匈牙利算法。

一.整数规划的数学模型所谓整数规划是指具有下列模型的规划问题：其中A,b,C中所有的数都是整数或有理数。例1红星日用化工厂为发运产品,下一年度需6种不同包箱。每种包箱的需求量及生产一个的可变费用如下表，每种包装的不变费用为1200，大可替代小.试设计使总费用最小的生产方案。包箱代号123456容积（m3）需求量（个）可变费用（元/个）0.080.10.120.150.200.255005507009004504005.08.010.012.116.318.2解设xj(j=1,2,…,6)为代号j包装箱的订做数量.则数学模型为:包箱代号123456容积（m3）需求量（个）可变费用（元/个）0.080.10.120.150.200.255005507009004504005.08.010.012.116.318.2例2人员分配问题

设某单位现有n个人员A1,A2……An来完成n项工作B1,B2,……Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。按问题要求，建立该问题的数学模型为分析:设例3求下列整数规划的最优解：二.整数规划问题与其松弛问题之间关系求解过程1解：先不考虑“x1,x2是整数”的条件，则相应的线性规划的最优解易由图解法得出是：X=（3.25,2.5）通过凑整法，可以的出4种组合因此，直接利用图解法或单纯形法都无法找出整数规划的最优解。（4，3）（4，2）（3，3）（3，2）。（4，2）（3，3）（4，3）都不是可行解；（3，2）虽是可行解，但不是最优解。问题的最优解是（4，1），最优值是14。而最优解（4，1）并不是相应线性规划的可行域的顶点。X=（3.25,2.5）

线性规划（LP）的任一整数可行解都是整数规划（IP）的一个可行解，并且（IP）的所有解（可行解）对应于（LP）的一个整数可行解。进一步地，如果（LP）的最优解是一个整数解，那么，这个解也一定是（IP）问题的最优解。

当（LP）的最优解不是一个整数解时，一般不可以通过对非整数解“四舍五入”得出（IP）问题的最优解。二.整数规划问题与其松弛问题之间关系例2人员分配问题

有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。第二节分配问题与匈牙利法

例1有一份资料，要分别译成四种文字，现有甲、乙、丙、丁四人可以承担这项工作。因为各人专长不同，他们翻译成不同文字所需要的时间用效率矩阵C表示。应如何分配工作，使他们完成任务的总时间最短？解:效率矩阵为ⅠⅡ

ⅢⅣ解：引入0—1变量xij，并令

xij=1(当指派第i人去完成第j项工作时)或0（当不指派第i人去完成第j项工作时)．这可以表示为一个0--1整数规划问题：Minz=2x11+10x12+9x13+7x14+15x21+4x22+14x23+8x24+13x31+14x32+16x33+11x34+4x41+15x42+13x43+9x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)

x21+x22+x23+x24=1(乙只能干一项工作)

x31+x32+x33+x34=1(丙只能干一项工作)

x41+x42+x43+x44=1(丁只能干一项工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

为0--1变量，i,j=1,2,3,4

n项不同的任务，恰好n个人可分别承担这些任务.称矩阵C为分配问题的效率矩阵：令xij表示人员Ai完成工作Bj的决策变量

表示分配Ai干工作Bj

表示不分配Ai干工作Bj一.分配问题的模型决策变量矩阵

分配问题的决策变量，可以写成一个矩阵形式，称为分配问题的决策变量矩阵。按问题要求，建立该问题的数学模型为可行解矩阵可行解矩阵X中各行或各列的元素之和都是1；并且X中只有n个元素是1，且位于不同行和不同列中。位于不同行和不同列的元素，称之为线性独立的。此模型也可以看成一个特殊的运输问题(各产地产量为1,各销地销量为1)，如果用表上作业法得出的一个最优解又满足“xij

=0,1”的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况，并不简单。二.匈牙利法1.方法的由来库恩研究发现,但方法的核心地方用了匈牙利人Konig的定理,故依此命名.2.基本思想

例如()()()()令关键是:找出位于不同行和不同列的0元素3.理论依据

Konig的两个定理

定理1

如果从分配问题效率矩阵[aij]的每一行元素中分别减去（或加上）一个常数ui(被称为该行的位势)，从每一列分别减去（或加上）一个常数vj（被称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=aij-ui-vj，则[bij]的最优解等价于[aij]的最优解。证明:

定理2

若矩阵A

的元素可分成“

0”与非“

0”两部分，则覆盖“

0”元素的最少直线数等于位于不同行不同列的“

0”元素的最大个数。例2.6个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使收益最大的分派方案？解：此问题是一个非平衡的指派问题，通过虚设两项任务Ⅴ，Ⅵ，设任务的收益为零，化为平衡指派问题。ⅠⅡⅢⅣ123456354567688981010109111211101213121113平衡指派问题的收益矩阵(cij)为:目标函数为将其转化为极小问题：用匈牙利法求解，将矩阵(cij’)变换为：由此可知空格的个数为6，已求得最优解。其余为0，即第3人做第Ⅳ项工作，第4人做第Ⅲ项工作，第5人做第Ⅱ项工作，第6人做第Ⅰ项工作.例3分配甲、乙、丙、丁去完成A、B、C、D、E五项任务，每人完成任务的时间如表，由于任务多于人数，故考虑：（1）任务E必须完成，其它四项可任选三项完成。（2）其中有一人完成两项任务任务，其他每人完成一项。ABCDE甲乙丙丁2529314237393826203334272840322442362345ABCDE甲乙丙丁戊25293142373938262033342728403224423623450000MABCDE甲乙丙丁戊25293142373938262033342728403224423623452427262032最少时间：105最少时间：131注：人员分配问题有各种提法。如果完成任务的效率表现为资源的消耗，则所谓的效率最好是指消耗的资源最少，分配问题就是一个