第四章第四章 整数规划与分配问题整数规划与分配问题对于线性规划问题，最优解可能是分数或小数。但是对于某些问题，会要求解答必须是整数（称为整数解整数解）。对于所求解是机器的台数、完成工作的人数、装货对于所求解是机器的台数、完成工作的人数、装货的车数、集装箱数量等；的车数、集装箱数量等；对于一些决策变量必须取对于一些决策变量必须取Boolean值时，如要不要在值时，如要不要在某地建工厂，可选用一个逻辑变量某地建工厂，可选用一个逻辑变量x，令，令x=0表示不表示不在该地建厂，在该地建厂，x=1表示在该地建厂。表示在该地建厂。 这时，分数或小数的解就不合要求，我们称这这时，分数或小数的解就不合要求，我们称这样的问题为样的问题为整数规划。整数规划。例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表：量、可获利润以及托运所受限制如下表：货物货物体积体积米米3/箱箱重量重量百斤百斤/箱箱 利润利润百元百元/箱箱 甲甲 乙乙54 252010托运托运限制限制2413问两种货物各托运多少箱，可使获得的利润为最大？问两种货物各托运多少箱，可使获得的利润为最大？能否先不考虑对变量的整数约束，作为一般线性能否先不考虑对变量的整数约束，作为一般线性规划来求解，当解为非整数的时候可以用规划来求解，当解为非整数的时候可以用“四舍四舍五入五入”或或“凑整凑整”方法寻找最优解？方法寻找最优解？对于变量取值很大时，用上述方法得到的解对于变量取值很大时，用上述方法得到的解与最优解差别不大；但当变量取值较小时，得与最优解差别不大；但当变量取值较小时，得到的解就可能与实际整数最优解差别很大。到的解就可能与实际整数最优解差别很大。当问题规模较大（决策变量较多）时，用当问题规模较大（决策变量较多）时，用“凑整凑整”方法来算工作量很大。方法来算工作量很大。 例：某线性规划问题最优解为例：某线性规划问题最优解为(x1, x2) = (4.6, 5.5)，用凑整法需要比较与上述数据最接近的几种，用凑整法需要比较与上述数据最接近的几种组合：组合：(4, 5), (4, 6), (5, 5), (5, 6)(4, 5), (4, 6), (5, 5), (5, 6)，共，共四种组合。若问题中有四种组合。若问题中有1010个整数变量，则解组个整数变量，则解组合达到合达到2 21010 = 1024 = 1024个整数组合。个整数组合。且最优解未必且最优解未必在这些组合中。在这些组合中。例：求整数规划问题的最优解例：求整数规划问题的最优解解：解：用图解法得最优解为（3.25 , 2.5）如果不考虑整数约束（称为整数规划如果不考虑整数约束（称为整数规划问题的问题的松弛问题松弛问题）最优解为（最优解为（4 , 1），）， z*= 14。凑整法求解：比较四个点（凑整法求解：比较四个点（4 , 3）,（4 , 2）,（3 , 3）,（3 , 2），前），前三个都不是可行解，第四个虽然是可三个都不是可行解，第四个虽然是可行解，但行解，但 z=13 不是最优解。不是最优解。(4,1)主要内容主要内容一、整数规划的特点及作用二、分配问题与匈牙利法三、分枝定界法四、应用举例第一节第一节 整数规划的特点及作用整数规划的特点及作用第四章第四章 整数规划及分配问题整数规划及分配问题一、整数规划的特点及作用一、整数规划的特点及作用1.1 整数规划的概念整数规划的概念整数规划整数规划(Integer Programming) ：决策变量要求取整数的线性规划。如果所有的决策变量、技术系数和右端项都是非负整数，就称为纯整数规划。纯整数规划。如果所有的决策变量都是非负整数，技术系数和右端项为有理数，称为全整数规划。全整数规划。如果仅一部分决策变量为整数，则称为混合混合整数规划。整数规划。如果变量取值仅限于0或1，称为0-10-1整数规划整数规划。一、整数规划的特点及作用一、整数规划的特点及作用1.2 0-1整数规划整数规划某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai供选择。规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问：应如何选址选址，可使年利润为最大？一、整数规划的特点及作用一、整数规划的特点及作用1.2 0-1整数规划整数规划0-1整数规划的一般形式整数规划的一般形式:0-1整数规划一般都整数规划一般都是纯整数规划。是纯整数规划。一、整数规划的特点及作用一、整数规划的特点及作用1.3 整数规划的作用整数规划的作用0-1整数规划在管理领域具有重要作用整数规划在管理领域具有重要作用1.m个约束条件中只有个约束条件中只有k个起作用；个起作用；2.2.约束条件的右端项可能是约束条件的右端项可能是r个值个值(b1, b2, br)中的某一个；中的某一个；3.3.两组条件中满足一组；两组条件中满足一组；4.4.用以表示含固定费用的函数。用以表示含固定费用的函数。第二节第二节 分配问题与匈牙利法分配问题与匈牙利法第四章第四章 整数规划及分配问题整数规划及分配问题二、分配问题与匈牙利法二、分配问题与匈牙利法2.1 分配问题分配问题(1)指派指派n个人去完成个人去完成n项任务，使完成项任务，使完成 n项任项任务的总效率最高务的总效率最高(或所需总时间最少或所需总时间最少)，这，这类问题称为类问题称为指派问题或分配问题指派问题或分配问题。安排工作（安排工作（派工派工）：有）：有n项加工任务，怎样项加工任务，怎样指派到指派到n台机床上完成；台机床上完成；有有n条航线，怎样指定条航线，怎样指定n艘船去航行的；艘船去航行的； 二、分配问题与匈牙利法二、分配问题与匈牙利法2.1 分配问题分配问题(2)如果完成任务的效率表现为如果完成任务的效率表现为资源消耗资源消耗，考，考虑的是如何分配任务使得目标函数虑的是如何分配任务使得目标函数极小化极小化；如果完成任务的效率表现为如果完成任务的效率表现为生产效率的高生产效率的高低低，则考虑的是如何分配使得目标函数，则考虑的是如何分配使得目标函数最最大化大化。在分配问题中，利用不同资源完成不同计在分配问题中，利用不同资源完成不同计划活动的效率，通常用表格形式表示为划活动的效率，通常用表格形式表示为效效率表率表，表格中数字组成，表格中数字组成效率矩阵效率矩阵。二、分配问题与匈牙利法二、分配问题与匈牙利法2.2 分配问题实例分配问题实例(1)例：有一份中文说明书，需要译成英、日、德、俄四种文字。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下，问应指派何人去完成工作，使所需总时间最少? 人员人员任务任务甲甲乙乙丙丙丁丁译成英文译成英文译成日文译成日文译成德文译成德文译成俄文译成俄文2151341041415914161378119二、分配问题与匈牙利法二、分配问题与匈牙利法2.2 分配问题实例分配问题实例(2)效率矩阵效率矩阵用aij表示。aij 0 ( i,j = 1,2,n )表示指派第j人去完成第i项任务时的效率(时间、成本等)。 人员人员任务任务甲甲乙乙丙丙丁丁译成英文译成英文译成日文译成日文译成德文译成德文译成俄文译成俄文2151341041415914161378119二、分配问题与匈牙利法二、分配问题与匈牙利法2.2 分配问题实例分配问题实例(3)某项任务只能由某项任务只能由1人完成；人完成；某人只能完成某人只能完成1项任务。项任务。 建立整数规划模型建立整数规划模型 分配问题是分配问题是0-10-1整数规划整数规划的特例，也是运输问题的的特例，也是运输问题的特例；特例； n = m, aj = bj = 1。二、分配问题与匈牙利法二、分配问题与匈牙利法2.3 匈牙利法匈牙利法分配问题可以用单纯形法或运输表求解。库恩(W.W.Kuhn)于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格(D.Knig)一个关于矩阵中零元素的定理：系数矩阵中独立系数矩阵中独立0元素的最多个数等于能覆盖所有元素的最多个数等于能覆盖所有0元素的最少直元素的最少直线数线数。这个解法称为匈牙利法匈牙利法。二、分配问题与匈牙利法二、分配问题与匈牙利法2.3 匈牙利法的基本思想匈牙利法的基本思想如果效率矩阵的所有元素aij0, 而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的xij = 1，其余的xij= 0，则所得到的可行解就是问题的最优解。显然令显然令 x11=1, x23=1, x32=1, x44=1，即，即将第一项工作分配给甲，第二项给丙，将第一项工作分配给甲，第二项给丙，第三项给乙，第四项给丁。这时完成第三项给乙，第四项给丁。这时完成总工作的时间为最少。总工作的时间为最少。如何寻找这组位于不同行不同列的零如何寻找这组位于不同行不同列的零元素？元素？二、分配问题与匈牙利法二、分配问题与匈牙利法2.3 匈牙利法的基本定理匈牙利法的基本定理定理1 如果从分配问题效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势)，从每一列分别减去(或加上)一个常数vj(被称为该列的位势)，得到一个新的效率矩阵bij，若其中bij = aij uivj，则bij的最优解等价于aij的最优解。定理2 若矩阵A的元素可分为“0”和非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(1) 人员人员任务任务甲甲乙乙丙丙丁丁译成英文译成英文译成日文译成日文译成德文译成德文译成俄文译成俄文2151341041415914161378119第一步：第一步：找出每找出每行的最小元素，行的最小元素，每行对应减去这每行对应减去这个元素。个元素。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(2)第二步：第二步：找出矩阵每列的最小元素，再分别从各列中减去。找出矩阵每列的最小元素，再分别从各列中减去。必定满足：必定满足：bij = = aijuivj二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(3)第三步：第三步：从第一行开始，若该行只有一个零元素，对零元从第一行开始，若该行只有一个零元素，对零元素打上素打上()()括号，表示行所代表的任务已指派。用直线划去括号，表示行所代表的任务已指派。用直线划去其所在列；若该行没有零元素或有两个以上零元素其所在列；若该行没有零元素或有两个以上零元素( (已划已划去的不计在内去的不计在内) )，则转下一行，依次进行到最后一行为止。，则转下一行，依次进行到最后一行为止。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(4)第三步：第三步：从第一列开始，若该列只有一个零元素，对零元从第一列开始，若该列只有一个零元素，对零元素打上素打上()()括号括号( (同样不考虑已划去的零元素同样不考虑已划去的零元素) )，再用直线划，再用直线划去其所在行；若该列没有零元素或有两个零元素，则转下去其所在行；若该列没有零元素或有两个零元素，则转下一列，依次进行到最后一列为止。一列，依次进行到最后一列为止。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(5)1.效率矩阵每行都有一个打每行都有一个打() 的零元素的零元素，这些零元素都位于不同行不同列，令对应打() 零元素的 xij=1 就得到最优解；2.矩阵中所有零元素或被划去，或被打上() ，但打() 的零元素少于少于m个个，这时转转第四步第四步。3.打()的零元素小于m，但未被划去的零元素之间存在闭回路闭回路。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(6)顺着闭回路的走向，对每个间隔的零元素打顺着闭回路的走向，对每个间隔的零元素打 ()()，然后对，然后对所有打所有打()()的零元素或所在行或所在列画一条直线，同样得的零元素或所在行或所在列画一条直线，同样得到最优解。到最优解。二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(7)第四步：第四步：继续按照定理继续按照定理1 1，对矩阵进行变换。，对矩阵进行变换。从矩阵未被直线覆盖的数字中找出一个最小的数从矩阵未被直线覆盖的数字中找出一个最小的数k；对矩；对矩阵的每行，当该行有直线覆盖时，令阵的每行，当该行有直线覆盖时，令ui=0=0，无直线覆盖的，无直线覆盖的，令令ui= =k；对矩阵中有直线覆盖的列，令；对矩阵中有直线覆盖的列，令vj= -k，对无直线覆，对无直线覆盖的列，令盖的列，令vj=0。只有一条直线只有一条直线覆盖的元素保覆盖的元素保持不变持不变二、分配问题与匈牙利法二、分配问题与匈牙利法2.4 匈牙利法实例匈牙利法实例(8)第五步：第五步：回到第三步，迭代运算，直到矩阵的每一行都有回到第三步，迭代运算，直到矩阵的每一行都有一个打一个打()() 的零元素为止。的零元素为止。最优分配方案为：甲译俄文，乙译日文，丙译英文，丁译最优分配方案为：甲译俄文，乙译日文，丙译英文，丁译德文。所需时间为：德文。所需时间为：4 4 + + 4 4 + + 9 9 + + 11 = 28h11 = 28h二、分配问题与匈牙利法二、分配问题与匈牙利法2.5 人数和任务数不相等的分配问题人数和任务数不相等的分配问题有四项工作分配给六个人去完成，每个人分别完成各项工作的时间如下，依然规定每个人完成一项工作。每项工作只交给一个人去完成。即六个人中挑选哪四个人去完成，花费时间最少。 工作工作人人IIIIIIIV123456373655616427245346648732 工作工作人人IIIIIIIVVVI123456373655616427245346648732000000000000二、分配问题与匈牙利法二、分配问题与匈牙利法2.6 目标函数最大化的分配问题目标函数最大化的分配问题令令 bij = M - aij标准化标准化 M为充分大的常数，可以得到bij0。根据定理1，这种转换是等价的。 bij = aij uivj = aij + M若若aij0，转换后的效率矩阵不符合匈牙利法的条件。，转换后的效率矩阵不符合匈牙利法的条件。第四章第四章 整数规划及分配问题整数规划及分配问题作作 业业 一一求下面指派问题的最优解第三节第三节 分枝定界法分枝定界法第四章第四章 整数规划及分配问题整数规划及分配问题三、分枝定界法三、分枝定界法3.1 分枝定界法的基本思想分枝定界法的基本思想分枝定界法分枝定界法可用于全部类型全部类型的整数规划问题。设有最大化的整数规划问题A，对应的线性规划线性规划为问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界上界，记作 ；而A的任意可行解的目标函数值将是z*的下界下界 。分支定界法就是将B的可行域分成子区域(称为分枝分枝)的方法，逐步减小和增大上、下界，最终得到整数规划问题A的z*。三、分枝定界法三、分枝定界法3.2 分枝定界法实例分枝定界法实例(1)1.1.求解求解B B：其最优解为x1 = 3.25，x2 = 2.5，最优目标函数值为z* = 14.75松弛问题松弛问题2.2.定界：定界：令x1 = 0，x2 = 0 作为初始整数解，其 z = 0，因此 。3.3.分枝：分枝：在B的最优解中，任取一个非整数变量，如 x2 = 2.5；因 x2 的最近邻整数解为 x2 = 2或 x2 = 3，其最优整数解区间只能是 x2 3或 x2 2。对B分别加上约束条件 x2 3和 x2 2，可得到两个子问题B1和B2。三、分枝定界法三、分枝定界法3.2 分枝定界法实例分枝定界法实例(2)4.4.定界：定界： 用图解法可得B1的最优解为(3.5, 2), z1 = 14.5； B2的最优解为(2.5, 3), z2 =13.5。没有整数最优解，上界5.其下界没有整数解，6. 7.z1 z2，对B1再次分枝。 三、分枝定界法三、分枝定界法3.2 分枝定界法实例分枝定界法实例(3)三、分枝定界法三、分枝定界法3.2 分枝定界法实例分枝定界法实例(4)5.5.再次分枝定界：再次分枝定界： B11的最优解为(3, 2), z11 = 13;B12的最优解为(4, 1), z12 = 14。这两个最优解都是A的可行解，此时A的上界和下界分别为14.5和 14。得最优解： (4, 1)，Z* = 14。三、分枝定界法三、分枝定界法3.2 分枝定界法分枝定界法 剪枝剪枝Bx1=3.25 x2=2.5Z =14.75B1x1=3.5 x2=2Z = 14.5B2x1=2.5 x2=3Z =13.5B11x1=3 x2=2Z =13B12x1=4 x2=1Z =14x2 2x2 3x1 3x1 4将各子问题边界值与保留将各子问题边界值与保留的可行解的值进行比较。的可行解的值进行比较。把边界值劣于可行解的分把边界值劣于可行解的分支减去。若除保留的可行支减去。若除保留的可行解外，其他的分支均被减解外，其他的分支均被减去，则得到最优解。去，则得到最优解。三、分枝定界法三、分枝定界法3.3 分枝定界法的解题思路分枝定界法的解题思路分枝定界法实际上是一种利用替代问题的解来逐渐逼近原问题最优解的方法；对替代问题的要求是：容易求解，且原问题的解集应无例外地包含在替代问题的解集中；如果替代问题(松弛)的最优解是原问题的可行解，这个解就是原问题的最优解；否则这个解的值是原问题最优解的上界(求极大时)或下界值(求极小时)。三、分枝定界法三、分枝定界法3.4 分枝定界法的解题步骤分枝定界法的解题步骤(1)1.1.解松驰问题解松驰问题B B：B没有可行解，这时A也没有可行解，停止。B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，停止。B有最优解，但不符合问题A的整数条件，将B的目标函数值为问题A的上界。2.用观察法找问题A的一个整数可行解，一般可取 xj = 0，j=1,n，求得其目标函数值，作为A的下界，开始迭代运算。三、分枝定界法三、分枝定界法3.4 分枝定界法的解题步骤分枝定界法的解题步骤(2)3.3.分枝与定界：分枝与定界：分枝：分枝：在B的最优解中任选一个不符合整数条件的变量xj。其值为bj，以bj表示小于bj的最大整数。构造两个约束条件xj bj和xj bj + 1，将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。求解这两个后继松弛问题。定界：定界：比较所有后继问题的最优解，最大的为A的新上界，从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，令下界 = 0。三、分枝定界法三、分枝定界法3.4 分枝定界法的解题步骤分枝定界法的解题步骤(3)4.4.比较与剪枝：比较与剪枝：各分支的最优目标函数若小于第三步得到的第三步得到的下界下界，则剪掉此分枝(用打表示)，以后不再考虑。若大于下界，且不符合整数条件，则重复第三步，选取所有边界值最优的分枝边界值最优的分枝进行分枝与定界，一直到最后得到z* = A的下界为止，此时得到最优解。第四章第四章 整数规划及分配问题整数规划及分配问题本章小结本章小结什么是整数规划？什么是整数规划？什么是什么是0-1整数规划？整数规划？整数规划的作用整数规划的作用什么是分配问题什么是分配问题(指派问题指派问题)匈牙利法匈牙利法求解一般整数规划的方法求解一般整数规划的方法分枝定界法分枝定界法