第五章第五章 整整 数数 规规 划划1整数规划的基本概念整数规划的基本概念2分枝定界法解整数规划分枝定界法解整数规划3规划规划4. 4. 指派问题及其解法指派问题及其解法1运筹学01规划指派问题1. 1. 整数规划的基本概念整数规划的基本概念2. 2. 分枝定界法解整数规划分枝定界法解整数规划纯整数规划、混整数规划纯整数规划、混整数规划分枝定界法分三步：分枝定界法分三步：第一步第一步第一步第一步 放宽放宽放宽放宽第二步第二步第二步第二步 分枝分枝分枝分枝第三步第三步第三步第三步 定界定界定界定界2运筹学01规划指派问题 具具具具体体体体作作作作法法法法是是是是：首首先先，删删去去整整整整数数数数条条条条件件件件，把把原原整整数数规规划划化化化化成成成成相相相相应应应应线线线线性性性性规规规规划划划划。其其次次，求求求求解解解解相相相相应应应应线线线线性性性性规规规规划划划划。最最后后，如如果果相相应应线线性性规规划划的的最最优优解解也也是是原原整整数数规规划划的的最最优优解解，那那么么整整个个计计算算过过程程即告结束；否则，便转入第二步。即告结束；否则，便转入第二步。第一步第一步放宽放宽3运筹学01规划指派问题 具具具具体体体体作作作作法法法法是是是是：从从相相应应线线性性规规划划的的最最优优解解中中，任任意意选选择择一一个个不不满满足足原原整整数数规规划划整整数数条条件件的的决决策策变变量量xj=bj。以以使使相相应应线线性性规规划划增增加加一一个个约约束束条条件件；x xj j小小小小于于于于b bj j的的的的最最最最大大大大整整整整数数数数（或或x xj j大大大大于于于于b bj j的的的的最最最最小小小小整整整整数数数数），因因而而得得到到两两枝枝新新的的线线性性规划，然后计算每枝的最优解和最优值。规划，然后计算每枝的最优解和最优值。第二步第二步 分枝分枝4运筹学01规划指派问题 具体做法为具体做法为具体做法为具体做法为：进行定界（由各枝的最：进行定界（由各枝的最优值中选最大值），找出界枝。若界枝的优值中选最大值），找出界枝。若界枝的最优解就是原整数规划的最优解，则计算最优解就是原整数规划的最优解，则计算过程便告结束；否则，回到第二步。过程便告结束；否则，回到第二步。第三步第三步 定界定界返回返回5运筹学01规划指派问题第四节第四节 0-1 0-1 规规 划划一、一、0- -1规划的概念规划的概念二、二、隐枚举法隐枚举法6运筹学01规划指派问题 例例9在在暑暑假假期期间间，某某同同学学准准备备徒徒步步回回家家探探亲亲。他他把把要要带带的的物物品品装装进进包包后后，觉觉得得还还能能多多放放5个个单单位位重重量量的的东东西西。为为此此，他他列列出出了了拟拟放放物物品品的的清清单单，见见表表2-11。他他认认为为：应应使使所所增增加加的的物物品品总总价价值值为为最最大大。基基于于以以上上的的考考虑虑，他他到到底底还要带哪些东西呢？还要带哪些东西呢？一、一、0- -1规划的概念规划的概念7运筹学01规划指派问题y为增加的物品总价值为增加的物品总价值编号编号名称名称重量重量价值价值1书籍书籍562诱饵诱饵233电筒电筒114食物食物35表表2-112-11解：解：设设例例9的数模为：的数模为：8运筹学01规划指派问题 只取只取0或或1的变量的变量,称为称为0- -1变量变量。若纯整。若纯整数规划的决策变量都是数规划的决策变量都是0- -1变量，则称为变量，则称为0- -1规划规划。 在讨论线性规划时，如果研究对象可以在讨论线性规划时，如果研究对象可以归结为互相对立的两种可能情况，那么依靠归结为互相对立的两种可能情况，那么依靠引入引入0- -1变量，就能够将它进一步化成变量，就能够将它进一步化成0- -1规规划。划。9运筹学01规划指派问题如如果果0-1规规划划模模型型不不是是标标准准型型，总总可可以以通通过过适适当的变换，使其化为标准型当的变换，使其化为标准型.称下面形式的数学模型为称下面形式的数学模型为0-10-1规划的标准型：规划的标准型：返回返回10运筹学01规划指派问题二、隐枚举法二、隐枚举法n从从理理论论上上讲讲，求求解解01规规划划，可可用用枚枚举举法法。 这这时时，一一旦旦有有n个个决决策策变变量量x1，x2，xn，就就必必须须逐逐一一地地检检查查（x1，x2，xn）的的2n种种取取值值（不不仅仅仅仅指指可可行行解解）。但但是是，当当 n10时时，即即使使经经历历漫漫长长的的计计算算过过程程找找到到了了最最优优解解，也会由于时过境迁而失去实用价值。也会由于时过境迁而失去实用价值。n隐隐枚枚举举法法是是0- -1规规划划的的常常用用解解法法，它它只只须须检检查查（x1，x2，xn）取取值值的的一一部部分分，即即可可找找到到最优解。最优解。11运筹学01规划指派问题例例例例10101010 利用隐枚举法求解例利用隐枚举法求解例9。试探的方法试探的方法这是一个求这是一个求y 的的最大值问题，当最大值问题，当然可以认为然可以认为ymax6这这个个新新的的约约束束条条件件具具有有滤滤掉掉非非最最优优解解的的功功能能，称称为为过滤条件过滤条件。解：解：解：解：（1 1 1 1）找出一个可行解并计算出相应的目标函数值：找出一个可行解并计算出相应的目标函数值： （x1，x2，x3，x4）=（1，0，0，0），），y =6；（2 2）将不等式）将不等式6x1+3x2+x3+5x46加到约束条件中；加到约束条件中；（3 3）把）把 6x1+3x2+x3+5x46和和 5x1+2x2+x3+3x45依次记作（依次记作（0）和（）和（1），把它们的左边分别），把它们的左边分别 写成（写成（0） 和（和（1） 。12运筹学01规划指派问题 本本0-10-1规规划划包包含含4 4 个个决决策策变变量量。所所以以（x1，x2，x3，x4）共共有有24种种不不同同的的取取值值。见见表表2-12。其其中中：（x1，x2，x3，x4）是是24种种取取值值；（0） 和和（1） 是是将将（x1，x2，x3，x4）取取值值代代入入后后的的计计算算结结果果。考考查查它它们们是是否否满满足足（0）和和（1）：当当不不满满足足某某个个约约束束条条件件时时，同同行行以以下下的的各各项项就就不不再再考考虑虑，这这表表明明（x1，x2，x3，x4）不不是是可可行行解解；当当满满足足全全部部约约束束条条件件时时，这这表表明明（x1，x2，x3，x4）是可行解。）是可行解。13运筹学01规划指派问题（x1，x2，x3，x4）(0)(1)是是()否否()y（0,0,0,0）0(0,0,0,1)5(0,0,1,0)1(0,0,1,1)646(0,1,0,0)3(0,1,0,1)858(0,1,1,0)4(0,1,1,1)96(1,0,0,0)6(5)6(1,0,0,1)118(1,0,1,0)76(1,0,1,1)129(1,1,0,0)97(1,1,0,1)1410(1,1,1,0)108(1,1,1,1)1511小于上面的目小于上面的目标值标值8，所以所以此解此解非最优。非最优。最最优优解解14运筹学01规划指派问题求出这些可行解对应的目标函数的最大值：求出这些可行解对应的目标函数的最大值：Max6,8=8。于是，本于是，本0-10-1规划的规划的 最优值最优值y ymaxmax= 8= 8 最优解（最优解（x1，x2，x3，x4）=（0，1，0，1）。这表明，该同学还要带诱饵和食物。这表明，该同学还要带诱饵和食物。15运筹学01规划指派问题 从提高隐枚举法的效率着想，当求解最从提高隐枚举法的效率着想，当求解最大（小）化大（小）化0- -1规划时，若遇到规划时，若遇到y 值大（小）于值大（小）于（0）的右边，应随即让（）的右边，应随即让（0）的右边改取这个）的右边改取这个y 值。求解值。求解0- -1规划，不要墨守成规，应视具体规划，不要墨守成规，应视具体情况选择适当的解法，以期收到事半功倍的效情况选择适当的解法，以期收到事半功倍的效果。果。16运筹学01规划指派问题例例例例3-33-33-33-3求下面求下面0-10-1规划的解规划的解. . 它它满满足足约约束束条条件件（1）到到（4），且且对对应应的的目目标标函函数数值值y =3于是过滤条件为：于是过滤条件为：解解解解首先用试探的方法找一个可行解首先用试探的方法找一个可行解:17运筹学01规划指派问题表表3-13隐枚举法计算表隐枚举法计算表(0)（1）（2）（3）（4）满足满足否则否则y(0,0,0)0(0,0,1)5-11015(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)802118(1,1,0)1(1,1,1)618运筹学01规划指派问题用用全全部部枚枚举举法法，3个个变变量量共共有有23=8个个解解，原原来来4个个约约束束条条件件共共需需32次次运运算算，现现在在用用隐隐枚枚举举法法，将将5个个约约束束条条件件按按（0）（4）顺顺序序排排好好（见见表表3-13），对对每每个个解解依依次次代代入入约约束束条条件件左左侧侧，求求出出数数值值，看看是是否否适适合合不不等等式式条条件件，如如某某一一条条件件不不适适合合，同同行行以以下下各各条条件件可可不不必必再再检检查查，因因而而就就减减少少了了运运算算次次数数.本例实际只作本例实际只作18次运算最优解次运算最优解:返回返回19运筹学01规划指派问题第五节第五节指派问题指派问题一、一、指派问题的概念指派问题的概念二、二、最小化指派问题最小化指派问题三、三、最大化指派问题最大化指派问题20运筹学01规划指派问题 指派问题就是人员和设备的任务安排问题。指派问题就是人员和设备的任务安排问题。但是，运筹学当前所涉及的指派问题，并不是泛但是，运筹学当前所涉及的指派问题，并不是泛指一切指派问题，而是把它局限于某种特殊情况。指一切指派问题，而是把它局限于某种特殊情况。这种特殊情况的一个典型事例是：这种特殊情况的一个典型事例是：有有n个人分别个人分别完成完成n项任务中的项任务中的其中一项其中一项。因工作性质和个人。因工作性质和个人专长的差异，每个人完成各项工作的时间也就有专长的差异，每个人完成各项工作的时间也就有所不同。于是便提出这样的问题：所不同。于是便提出这样的问题：指派哪个人完指派哪个人完成哪项工作，可使他们总的工作时间最短成哪项工作，可使他们总的工作时间最短？ 指派问题有指派问题有最小化最小化最小化最小化和和最大化最大化最大化最大化之分，二者的解之分，二者的解法大同小异。法大同小异。一、指派问题的概念一、指派问题的概念返回返回21运筹学01规划指派问题 例例例例1111某某医医院院的的四四名名化化验验员员（甲甲、乙乙、丙丙、丁丁）完完成成四四项项化化验验工工作作（A、B、C、D）所所消消耗耗的的时时间间见见表表2- -13。哪哪个个化化验验员员担担当当哪哪项项化化验验工工作作，可可使使他他们们总总的的消消耗耗时时间间最最短？短？二、二、最小化指派问题最小化指派问题22运筹学01规划指派问题表表表表1-131-13 A B C D 消耗时间（分） 甲 37.7 43.4 33.3 29.2 乙 32.9 33.1 28.5 26.4 丙 33.8 42.2 38.9 29.6 丁 37.0 34.7 30.4 28.5建立其数学模型。设：建立其数学模型。设：i=1, ,2, ,3, ,4分别表示甲，乙，丙，丁；分别表示甲，乙，丙，丁； j =1,2,3,4分别表示分别表示A，B，C，D；bij表示表示 i 完成完成 j 的消耗时间；的消耗时间；23运筹学01规划指派问题y 表示四名化验员总的消耗时间，于是表示四名化验员总的消耗时间，于是数学模型数学模型为：为：例例1111称为称为最小化指派问题最小化指派问题。24运筹学01规划指派问题一般地，最小化指派问题的一般地，最小化指派问题的数学模型数学模型是：是：其中其中 bij 称为称为效率矩阵效率矩阵。25运筹学01规划指派问题定定定定理理理理2.12.1若若效效率率矩矩阵阵bij第第i 行行元元素素的的最最小小值值为为bi,则则效效率率矩矩阵阵分分别别为为bij和和bij-bi的的最最小小化化指指派派问问题题具具有有相相同同的的最最优优解解。把把“第第i行行”换换成成“第第j列列”，“bi”换成换成 “ “bj”后，依然成立。后，依然成立。最小化指派问题的求解步骤如下：最小化指派问题的求解步骤如下：最小化指派问题的求解步骤如下：最小化指派问题的求解步骤如下：第一步：第一步：第一步：第一步：在效率矩阵在效率矩阵bij中，让每行（列）元素减去该中，让每行（列）元素减去该行（列）元素的行（列）元素的最小值最小值最小值最小值，从而得到矩阵，从而得到矩阵 C Cij ij 。26运筹学01规划指派问题每行减去该行每行减去该行的最小元素的最小元素每列减去该列每列减去该列的最小元素的最小元素每行每每行每列都有列都有零零27运筹学01规划指派问题第二步：第二步：第二步：第二步：在矩阵在矩阵Cij中，首先找出含中，首先找出含0最少的行，并且最少的行，并且把其中的一个把其中的一个0括起来，即括起来，即（0）；然后划掉与；然后划掉与前提下，相继完成其它各行。前提下，相继完成其它各行。 （0）同行或同列的）同行或同列的0，即，即 。在不得再括。在不得再括 的的( )( )( )28运筹学01规划指派问题第第第第三三三三步步步步：在在矩矩阵阵Cij中中，若若不不能能得得到到m个个（0），则则进进行行第第四四步步；若若能能得得到到m个个（0），则则令令Cij中中与与（0）相相对对应应的的xij=1，其其余余的的决决策策变变量量等等于于0。这这时时，xij便便是是最最优优解解。将将最最优优解解代代入入目目标标函函数数 y 的的表表达达式式，即即得得最最优优值。值。( )( )( )没有得到没有得到4个个(0)转入第四步转入第四步29运筹学01规划指派问题第四步：第四步：第四步：第四步：遵循下列程序，在遵循下列程序，在Cij中画出直线：中画出直线：（一）在没有（一）在没有（0）的行，标上）的行，标上“”“”；（三）在标上（三）在标上“”“”的列中（的列中（0）所在的行，标上）所在的行，标上“”“”；（四四）在在没没有有标标上上 “”“”的的行行或或已已经经标标上上“”“”的的列，列， 都画上一条直线；都画上一条直线；（二）在标上（二）在标上“”“”的行中的行中 所在的列，标上所在的列，标上“”“”；（五）去掉（五）去掉“”“”，而且将（，而且将（0）和）和 重新写成重新写成 0 0。( )( )( )( )( )( )30运筹学01规划指派问题第五步：第五步：从从Cij未画上直线的元素中未画上直线的元素中找出最找出最找出最找出最 小值小值小值小值。让画上直线的列中元素都。让画上直线的列中元素都加上该最加上该最加上该最加上该最 小值小值小值小值，未画上直线的行中元素都，未画上直线的行中元素都减去该最减去该最减去该最减去该最 小值小值小值小值，随即去掉各行各列上的直线，并转，随即去掉各行各列上的直线，并转 入第二步。入第二步。31运筹学01规划指派问题最小元素最小元素0.2新产生新产生的的0元素元素32运筹学01规划指派问题( )( )( )( ) 已得到已得到4个个（0），则令，则令Cij中中与与（0）相对应的相对应的xij=1，其余的决策变量等于其余的决策变量等于0。这时，。这时，xij便是最优解。将最优解代便是最优解。将最优解代入目标函数入目标函数 y 的表达式，即得最优值的表达式，即得最优值 ymin =126.2(分分)。转入第二步转入第二步, ,重新括重新括0 0元素元素: :返回返回 这这表表明明，让让化化验验员员甲甲、乙乙、丙丙、丁丁分分别别担担当当化化验验工工作作D、C、A、B，可可使使他他们们总总的的消消耗耗时时间间最最短短，只只消消126.2分分，就能完成四项化验工作。就能完成四项化验工作。33运筹学01规划指派问题三、三、最大化指派问题最大化指派问题 例例12某某卫卫生生防防疫疫站站准准备备选选拔拔防防疫疫科科、食食品品科科、总总务务科科的的三三名名科科长长。几几经经筛筛选选，仅仅剩剩下下赵赵、钱钱、孙孙三三名候选人。根据民主评议的统计结果名候选人。根据民主评议的统计结果, ,他们主持各个他们主持各个 科的工作能力（以科的工作能力（以 得分多少来衡量）得分多少来衡量） 如表如表2-14所示。试所示。试 从工作能力出发，从工作能力出发， 确定最优选择科长确定最优选择科长 方案。方案。防疫防疫食品食品总务总务工作能力（分）工作能力（分）赵赵353027钱钱373529孙孙382832表表 2 2141434运筹学01规划指派问题 建立数学模型建立数学模型建立数学模型建立数学模型设：设：i=1,2,3分别表示赵，钱，孙；分别表示赵，钱，孙； j=1,2,3分别表示防疫科，食品科，总务科；分别表示防疫科，食品科，总务科；aij表示表示 i担任担任 j科长的工作能力；科长的工作能力； y 表示三名科长总的工作能力。表示三名科长总的工作能力。于是所求于是所求数学模型数学模型是：是：35运筹学01规划指派问题例例12称为最大化指派问题。称为最大化指派问题。36运筹学01规划指派问题一般地，最大化指派问题的数学模型是：一般地，最大化指派问题的数学模型是：其中其中aij称为称为效率矩阵效率矩阵。37运筹学01规划指派问题最大化指派问题的求解步骤如下最大化指派问题的求解步骤如下最大化指派问题的求解步骤如下最大化指派问题的求解步骤如下：第一步：第一步：第一步：第一步：将最大化指派问题的效率矩阵将最大化指派问题的效率矩阵aij化成化成aaij，a=maxaij i,j=1,2,m第第第第二二二二步步步步：求求出出效效率率矩矩阵阵为为aaij的的最最小小化化指指派派问问题题的的最最优优解解，以以其其作作为为最最大大化化指指派派问问题题的的最最优优解。解。第第第第三三三三步步步步：把把最最优优解解代代入入最最大大化化指指派派问问题题的的目目标标函函数数的表达式，求出最优解。的表达式，求出最优解。 定理定理定理定理2.22.2若效率矩阵若效率矩阵aij各元素的最大值是各元素的最大值是 a,则效率矩阵为则效率矩阵为 a aij ij 的最大化的最大化的最大化的最大化指派问题与效率矩阵为指派问题与效率矩阵为 a aa aij ij 的最小化的最小化的最小化的最小化指派问题具有指派问题具有相同的最优解相同的最优解相同的最优解相同的最优解。38运筹学01规划指派问题 确定例确定例12的最优选拔科长方案的最优选拔科长方案a = maxaiji,j=1,2, 3= 38 得：第一步：第一步：第一步：第一步：由由39运筹学01规划指派问题 第二步：第二步：因为 3 8 11 -3aaij= 1 3 9 -1 0 10 6 -0 0 5 8 （0） 3 2 0 2 8 （0） 2 0 10 6 8 （0） -0 -2 -640运筹学01规划指派问题所以，例所以，例12的最优解是：的最优解是：第第第第三三三三步步步步：将将最最优优解解代代入入目目标标函函数数y的的表表达达式式，求求得得最最优值为：优值为： ymax= = a11 11 + + a22 22 + + a33 33 = 35 + 35 + 32 = 102 (= 35 + 35 + 32 = 102 (分分) ) 于是，最优选拔科长方案是：于是，最优选拔科长方案是：赵、钱、孙分别担任防疫科、食赵、钱、孙分别担任防疫科、食品科、总务科的科长。这时，三品科、总务科的科长。这时，三名科长的总工作能力达到最大值，名科长的总工作能力达到最大值，即为即为102102分。分。返回返回返回返回41运筹学01规划指派问题小小结结1.1.最小化指派问题及其求解步骤最小化指派问题及其求解步骤第一步：第一步：第一步：第一步：使使使使效率矩阵的每行每列都有效率矩阵的每行每列都有0 0元素元素第二步：第二步：第二步：第二步：括括0元素元素第三步：第三步：第三步：第三步：判断是否已得到最优解判断是否已得到最优解判断是否已得到最优解判断是否已得到最优解第四步：第四步：第四步：第四步：画直线覆盖画直线覆盖0 0元素元素第五步：第五步：第五步：第五步：未被直线覆盖的元素中未被直线覆盖的元素中找出最小值找出最小值找出最小值找出最小值, , , , 产生新的产生新的产生新的产生新的0 0 0 0元素元素, ,返回第二步返回第二步. .42运筹学01规划指派问题小小结结2.2.最大化指派问题及其求解步骤最大化指派问题及其求解步骤第一步：第一步：第一步：第一步：将最大化指派问题的效率矩阵将最大化指派问题的效率矩阵aij化成化成aaij，a=maxaij i,j=1,2,m 第二步：第二步：第二步：第二步：求出效率矩阵为求出效率矩阵为aaij的最小化指派问的最小化指派问 题最优解，以其作为最大化指派问题最题最优解，以其作为最大化指派问题最 优解。优解。第三步：第三步：第三步：第三步：把最优解代入最大化指派问题的目标函把最优解代入最大化指派问题的目标函 数的表达式，求出最优值。数的表达式，求出最优值。43运筹学01规划指派问题作作业业P534P775（1）,9,10P53444运筹学01规划指派问题