运筹学——.整数规划与分配问题

《运筹学——.整数规划与分配问题》由会员分享，可在线阅读，更多相关《运筹学——.整数规划与分配问题（43页珍藏版）》请在金锄头文库上搜索。

1、第四章 整数规划与分配问题 对于线性规划问题，最优解可能是分数或小数 。但是对于某些问题，会要求解答必须是整数 （称为整数解）。 对于所求解是机器的台数、完成工作的人数、装货 的车数、集装箱数量等； 对于一些决策变量必须取Boolean值时，如要不要在 某地建工厂，可选用一个逻辑变量x，令x=0表示不 在该地建厂，x=1表示在该地建厂。 这时，分数或小数的解就不合要求，我们称这 样的问题为整数规划。例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、 重量、可获利润以及托运所受限制如下表：货货物体积积 米3/箱重量 百斤/箱 利润润 百元/箱甲乙5 4 2 520 10托运 限制2413问两种货物

2、各托运多少箱，可使获得的利润为最大？能否先不考虑对变量的整数约束，作为一般线性 规划来求解，当解为非整数的时候可以用“四舍 五入”或“凑整”方法寻找最优解？ 对于变量取值很大时，用上述方法得到的解与对于变量取值很大时，用上述方法得到的解与 最优解差别不大；但当变量取值较小时，得到最优解差别不大；但当变量取值较小时，得到 的解就可能与实际整数最优解差别很大。的解就可能与实际整数最优解差别很大。 当问题规模较大（决策变量较多）时，用当问题规模较大（决策变量较多）时，用“凑凑 整整”方法来算工作量很大。方法来算工作量很大。 例：某线性规划问题最优解为(x1, x2) = (4.6, 5.5) ，用凑

3、整法需要比较与上述数据最接近的几种 组合：(4, 5), (4, 6), (5, 5), (5, 6)，共 四种组合。若问题中有10个整数变量，则解组 合达到210 = 1024个整数组合。且最优解未必 在这些组合中。例：求整数规划问题的最优解解：用图解法得最优解为（3.25 , 2.5）如果不考虑整数约束（称为整数规划 问题的松弛问题）最优解为（4 , 1）， z*= 14。凑整法求解：比较四个点（4 , 3）,（ 4 , 2）,（3 , 3）,（3 , 2），前三个都 不是可行解，第四个虽然是可行解， 但 z=13 不是最优解。(4,1)主要内容一、整数规划的特点及作用一、整数规划的特点及

4、作用 二、分配问题与匈牙利法二、分配问题与匈牙利法 三、分枝定界法三、分枝定界法 四、应用举例四、应用举例第一节第一节 整数规划的特点及作用整数规划的特点及作用第四章 整数规划及分配问题一、整数规划的特点及作用一、整数规划的特点及作用 1.11.1 整数规划的概念整数规划的概念 整数规划(Integer Programming) ：决策变 量要求取整数的线性规划。 如果所有的决策变量、技术系数和右端项都 是非负整数，就称为纯整数规划。 如果所有的决策变量都是非负整数，技术系 数和右端项为有理数，称为全整数规划。 如果仅一部分决策变量为整数，则称为混合 整数规划。 如果变量取值仅限于0或1，称为

5、0-1整数规划 。一、整数规划的特点及作用一、整数规划的特点及作用 1.21.2 0-10-1整数规划整数规划 某公司拟在市东、西、南三区建立门市部。拟 议中有7个位置（点）Ai供选择。规定 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利 润估计为ci元，但投资总额不能超过B元。 问：应如何选址，可使年利润为最大？一、整数规划的特点及作用一、整数规划的特点及作用 1.21.2 0-10-1整数规划整数规划0-1整数规划的一般形式:0-1整数规划一般都 是纯整数规划

6、。一、整数规划的特点及作用一、整数规划的特点及作用 1.31.3 整数规划的作用整数规划的作用 0-1整数规划在管理领域具有重要作用 1. m个约束条件中只有k个起作用； 2. 约束条件的右端项可能是r个值(b1, b2, br) 中的某一个； 3. 两组条件中满足一组； 4. 用以表示含固定费用的函数。第二节第二节 分配问题与匈牙利法分配问题与匈牙利法第四章 整数规划及分配问题二、分配问题与匈牙利法二、分配问题与匈牙利法 2.12.1 分配问题分配问题(1)(1) 指派n个人去完成n项任务，使完成 n项任 务的总效率最高(或所需总时间最少)，这 类问题称为指派问题或分配问题。 安排工作（派工

7、）：有n项加工任务，怎样 指派到n台机床上完成； 有n条航线，怎样指定n艘船去航行的； 二、分配问题与匈牙利法二、分配问题与匈牙利法 2.12.1 分配问题分配问题(2)(2) 如果完成任务的效率表现为资源消耗，考 虑的是如何分配任务使得目标函数极小化 ； 如果完成任务的效率表现为生产效率的高 低，则考虑的是如何分配使得目标函数最 大化。 在分配问题中，利用不同资源完成不同计 划活动的效率，通常用表格形式表示为效 率表，表格中数字组成效率矩阵。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.22.2 分配问题实例分配问题实例(1)(1) 例：有一份中文说明书，需要译成英、日、德 、俄四种文字

8、。现有甲、乙、丙、丁四人，他 们将中文说明书译成不同语种的说明书所需时 间如下，问应指派何人去完成工作，使所需总 时间最少? 人员员任务务甲乙丙丁译译成英文 译译成日文 译译成德文 译译成俄文2 15 13 410 4 14 159 14 16 137 8 11 9二、分配问题与匈牙利法二、分配问题与匈牙利法 2.22.2 分配问题实例分配问题实例(2)(2) 效率矩阵用aij表示。aij 0 ( i,j = 1,2,n )表示 指派第j人去完成第i项任务时的效率(时间、成 本等)。人员员 任务务甲乙丙丁译译成英文 译译成日文 译译成德文 译译成俄文2 15 13 410 4 14 159 1

9、4 16 137 8 11 9二、分配问题与匈牙利法二、分配问题与匈牙利法 2.22.2 分配问题实例分配问题实例(3)(3) 某项任务只能由1人完成； 某人只能完成1项任务。建立整数规划模型分配问题是0-1整数规划的 特例，也是运输问题的特 例； n = m, aj = bj = 1。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.32.3 匈牙利法匈牙利法 分配问题可以用单纯形法或运输表求解。 库恩(W.W.Kuhn)于1955年提出了指派问题的解 法，他引用了匈牙利数学家康尼格(D.Knig)一 个关于矩阵中零元素的定理：系数矩阵中独立0 元素的最多个数等于能覆盖所有0元素的最少直 线

10、数。这个解法称为匈牙利法。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.32.3 匈牙利法的基本思想匈牙利法的基本思想 如果效率矩阵的所有元素aij0, 而其中存在一组位于不 同行不同列的零元素，则只要令对应于这些零元素位 置的xij = 1，其余的xij= 0，则所得到的可行解就是问 题的最优解。显然令 x11=1, x23=1, x32=1, x44=1，即 将第一项工作分配给甲，第二项给丙 ，第三项给乙，第四项给丁。这时完 成总工作的时间为最少。如何寻找这组位于不同行不同列的零 元素？二、分配问题与匈牙利法二、分配问题与匈牙利法 2.32.3 匈牙利法的基本定理匈牙利法的基本定理 定

11、理1 如果从分配问题效率矩阵aij的每一行 元素中分别减去(或加上)一个常数ui(被称为该 行的位势)，从每一列分别减去(或加上)一个常 数vj(被称为该列的位势)，得到一个新的效率矩 阵bij，若其中bij = aij uivj，则bij的最 优解等价于aij的最优解。 定理2 若矩阵A的元素可分为“0”和非“0”两 部分，则覆盖“0”元素的最少直线数等于位于 不同行不同列的“0”元素的最大个数。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(1)(1)人 员员 任务务甲乙丙丁译译成英文 译译成日文 译译成德文 译译成俄文2 15 13 410 4 14

12、 159 14 16 137 8 11 9第一步：找出每 行的最小元素， 每行对应减去这 个元素。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(2)(2)第二步：找出矩阵每列的最小元素，再分别从各列中减去 。必定满足：bij = aijuivj二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(3)(3)第三步：从第一行开始，若该行只有一个零元素，对零元 素打上()括号，表示行所代表的任务已指派。用直线划去 其所在列；若该行没有零元素或有两个以上零元素(已划 去的不计在内)，则转下一行，依次进行到最后一行为止 。二、分配

13、问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(4)(4)第三步：从第一列开始，若该列只有一个零元素，对零元 素打上()括号(同样不考虑已划去的零元素)，再用直线划 去其所在行；若该列没有零元素或有两个零元素，则转下 一列，依次进行到最后一列为止。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(5)(5) 1.效率矩阵每行都有一个打() 的零元素， 这些零元素都位于不同行不同列，令对 应打() 零元素的 xij=1 就得到最优解；2.矩阵中所有零元素或被划去，或被打上 () ，但打() 的零元素少于m个，这时转 第四步。 3.

14、打()的零元素小于m，但未被划去的零元 素之间存在闭回路。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(6)(6)顺着闭回路的走向，对每个间隔的零元素打 ()，然后对 所有打()的零元素或所在行或所在列画一条直线，同样得 到最优解。二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(7)(7)第四步：继续按照定理1，对矩阵进行变换。从矩阵未被直线覆盖的数字中找出一个最小的数k；对矩 阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的 ，令ui=k；对矩阵中有直线覆盖的列，令vj= -k，对无直线 覆盖的列，令vj=0

15、。只有一条直线 覆盖的元素保 持不变二、分配问题与匈牙利法二、分配问题与匈牙利法 2.42.4 匈牙利法实例匈牙利法实例(8)(8)第五步：回到第三步，迭代运算，直到矩阵的每一行都有 一个打() 的零元素为止。最优分配方案为：甲译俄文，乙译日文，丙译英文，丁译 德文。所需时间为：4 + 4 + 9 + 11 = 28h二、分配问题与匈牙利法二、分配问题与匈牙利法 2.52.5 人数和任务数不相等的分配问题人数和任务数不相等的分配问题 有四项工作分配给六个人去完成，每个人分别完成各 项工作的时间如下，依然规定每个人完成一项工作。 每项工作只交给一个人去完成。即六个人中挑选哪四 个人去完成，花费时

16、间最少。工作 人IIIIIIIV1 2 3 4 5 63 7 3 6 5 56 1 6 4 2 72 4 5 3 4 66 4 8 7 3 2工作 人IIIIIIIVVVI1 2 3 4 5 63 7 3 6 5 56 1 6 4 2 72 4 5 3 4 66 4 8 7 3 20 0 0 0 0 00 0 0 0 0 0二、分配问题与匈牙利法二、分配问题与匈牙利法 2.62.6 目标函数最大化的分配问题目标函数最大化的分配问题令 bij = M - aij标准化M为充分大的常数，可以得到bij0。根据定理1，这种转 换是等价的。 bij = aij uivj = aij + M若aij0，转换后的效率矩阵不符合匈牙利法的条件。第四章第四章 整数规划及分配问题整数规划及分配问题 作作 业业 一一 求下面指派问题的最优解第三节