运筹学整数规划和分配问题新.pptx

作业：作业：P125 4.1 4.2 4.3(a)4.4第四章第四章 整数规划与分配问题整数规划与分配问题第一节第一节 整数规划的特点及应用整数规划的特点及应用一、整数规划的一般形式一、整数规划的一般形式定义：一部分或全部决策变量必须取整数定义：一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题。的规划问题称为该整数规划的松弛问题。若松弛问题是线性规划，则该整数规划称若松弛问题是线性规划，则该整数规划称为整数线性规划。为整数线性规划。整数线性规划的一般形式:不考虑整数要求时，不考虑整数要求时，最优解为：最优解为：X=(3.25,2.5)X=(3.25,2.5)T T Z=13 Z=13 （见下页图解法）（见下页图解法）考虑整数要求时，最优解为：考虑整数要求时，最优解为：X=(4 X=(4,1),1)T T Z=14Z=14凑整凑整 （3 3，2 2）可行，非最优，）可行，非最优，Z=13Z=13。（4 4，3 3），（），（4 4，2 2），（），（3 3，3 3）不可行不可行二、整数规划的分类二、整数规划的分类1.1.全整数线性规划全整数线性规划 决策变量全部取整数，约束系数和约束常数项决策变量全部取整数，约束系数和约束常数项也取整数的整数线性规划。也取整数的整数线性规划。2.2.纯整数线性规划纯整数线性规划 决策变量全部取整数，约束系数和约束常数项决策变量全部取整数，约束系数和约束常数项可取非整数的整数线性规划。可取非整数的整数线性规划。纯整数线性规划可化为全整数线性规划。纯整数线性规划可化为全整数线性规划。3.3.混合整数线性规划混合整数线性规划 决策变量中有一部分取整数值，另一部分可取决策变量中有一部分取整数值，另一部分可取非整数值的整数线性规划。非整数值的整数线性规划。4.0-14.0-1整数线性规划整数线性规划 决策变量只能取决策变量只能取0 0或或1 1的整数线性规划。的整数线性规划。三、三、0-1变量（或称逻辑变量）在模型中变量（或称逻辑变量）在模型中的应用的应用 整数规划模型对研究管理问题有重要整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模意义。很多不能归结为线性规划数学模型的管理问题，却可以通过设置逻辑变型的管理问题，却可以通过设置逻辑变量建立起整数规划数学模型。量建立起整数规划数学模型。第二节第二节 分配问题分配问题(指派问题）与匈牙利法指派问题）与匈牙利法 2-1 2-1 问题的提出及数学模型问题的提出及数学模型 假设有假设有m m项任务分配给项任务分配给m m个人去完成，并个人去完成，并指定每个人完成其中一项，每项任务也只由指定每个人完成其中一项，每项任务也只由一个人完成，问应如何分配任务，才能使总一个人完成，问应如何分配任务，才能使总效率最高？（或总费用最少，花费的总时间效率最高？（或总费用最少，花费的总时间最少等等。）最少等等。）设每个人完成不同任务的耗费见下面的设每个人完成不同任务的耗费见下面的效率矩阵，通常要求效率矩阵，通常要求a aijij00。则分配问题的数学模型为则分配问题的数学模型为2-2 2-2 匈牙利法匈牙利法定理定理1.1.如果从分配问题效率矩阵如果从分配问题效率矩阵(a(aijij)的每一的每一行元素中分别减去（或加上）一个常数行元素中分别减去（或加上）一个常数u ui i （称为该行的位势）；从每一列中分别减去（称为该行的位势）；从每一列中分别减去（或加上）一个常数（或加上）一个常数 v vj j （称为该列的位势）（称为该列的位势）；得到一个新的效率矩阵；得到一个新的效率矩阵b bijij，其中，其中b bijij=a=aijij-u ui i-v-vj j ，则，则a aijij的最优解等价于的最优解等价于b bijij的最优解。的最优解。定理定理2.2.若效率矩阵若效率矩阵A A的元素可分成的元素可分成0 0与非与非0 0两两部分，则覆盖所有部分，则覆盖所有0 0元素的最少直线数等于位元素的最少直线数等于位于于不同行不同列不同行不同列的的0 0元素的最大个数。元素的最大个数。匈牙利法的步骤：匈牙利法的步骤：第一步第一步 效率矩阵每行都减去该行的最小元素；效率矩阵每行都减去该行的最小元素；第二步第二步 效率矩阵每列都减去该列的最小元素；效率矩阵每列都减去该列的最小元素；此时，效率矩阵的此时，效率矩阵的每行每列每行每列都有都有0 0元素。元素。第三步第三步 寻找位于寻找位于不同行不同列不同行不同列的的0 0元素，也就是元素，也就是寻找能覆盖所有寻找能覆盖所有0 0元素的最少直线数。元素的最少直线数。方法：方法：1.1.从从只有一个只有一个0 0元素元素的行开始，对的行开始，对0 0元素打上（元素打上（）号，然后对打（）号，然后对打（）的）的0 0元素所在元素所在列列画一条直线，画一条直线，依次进行到最后一行；依次进行到最后一行；2.2.从只有一个从只有一个0 0元素的列开始，对元素的列开始，对0 0元素打上（元素打上（）号，）号，然后对打（然后对打（）的）的0 0元素所在元素所在行行画一条直线，画一条直线，依次进行到最后一列；依次进行到最后一列；3.3.重复重复1.1.、2.2.两个步骤，可能出现三种情况：两个步骤，可能出现三种情况：（1 1）若能找到）若能找到m m个位于不同行不同列的个位于不同行不同列的0 0元素（即元素（即带（带（）的）的0 0元素），则令（元素），则令（0 0）处的）处的x xijij=1,=1,求解结求解结束；束；（2 2）若有形成闭回路的）若有形成闭回路的0 0元素，则任选一个打（元素，则任选一个打（），然后对每个间隔的），然后对每个间隔的0 0元素打（元素打（），同时对打），同时对打（）的）的0 0元素所在行（或列）画一条直线。元素所在行（或列）画一条直线。（3 3）若位于不同行不同列的）若位于不同行不同列的0 0元素元素 即带（即带（）的）的0 0元素元素 少于少于m m，转第四步。，转第四步。第四步第四步 为产生为产生m m个位于不同行不同列的个位于不同行不同列的0 0元素，元素，用定理一对效率矩阵进行调整，使之生成新的用定理一对效率矩阵进行调整，使之生成新的0 0元素。方法：元素。方法：1.1.在效率矩阵未被直线覆盖的元素中找出最小在效率矩阵未被直线覆盖的元素中找出最小元素元素k k；2.2.效率矩阵未被直线覆盖的行都减效率矩阵未被直线覆盖的行都减k;k;3.3.效率矩阵被直线覆盖的列都加效率矩阵被直线覆盖的列都加k;k;4.4.转回第三步。转回第三步。2-3 特殊情况的处理特殊情况的处理1.人数多于任务数，加虚拟任务。人数多于任务数，加虚拟任务。设有设有n人，人，m项任务，项任务，nm,则增加则增加n-m项任务。项任务。2.人数少于任务数，加虚拟人员。人数少于任务数，加虚拟人员。设有设有n人，人，m项任务，项任务，nm,则增加则增加m-n项任务。项任务。此时，效率矩阵的元素全成为负值，不符合要此时，效率矩阵的元素全成为负值，不符合要求，根据定理求，根据定理1 1，令，令变换后的效率矩阵每行都加变换后的效率矩阵每行都加M M即可。即可。3.对求最大值问题的处理对求最大值问题的处理设目标函数为设目标函数为可将其变换为可将其变换为作业：作业：P126 4.7P126 4.7（a)4.8(a)a)4.8(a)第三节第三节 分枝定界法分枝定界法一、分枝定界法的基本思想一、分枝定界法的基本思想 先不考虑整数解的限制，用单纯形法求先不考虑整数解的限制，用单纯形法求解其松弛问题，如果求得的解恰好是整数解，解其松弛问题，如果求得的解恰好是整数解，则得整数规划最优解，停止计算。否则，将则得整数规划最优解，停止计算。否则，将松弛问题分解为两个子问题（也称后继问题）松弛问题分解为两个子问题（也称后继问题），每个子问题都是在原松弛问题的基础上增，每个子问题都是在原松弛问题的基础上增加一个变量取整数的约束条件，这样就缩小加一个变量取整数的约束条件，这样就缩小了原来的可行域，然后用单纯形法求解，直了原来的可行域，然后用单纯形法求解，直至得到最终结果。至得到最终结果。二、分枝定界法的步骤（最大值问题）二、分枝定界法的步骤（最大值问题）第一步第一步 寻找替代问题并求解寻找替代问题并求解 设原整数规划问题为设原整数规划问题为IPIP，其松弛问题为，其松弛问题为L L0 0。用单纯形法求。用单纯形法求L L0 0，若若L L0 0无可行解，则无可行解，则IPIP也无也无可行解，计算停止。可行解，计算停止。若求得若求得L L0 0为整数解，则得为整数解，则得IPIP的最优解，停止。否则，转下一步；的最优解，停止。否则，转下一步；第二步第二步 分枝与定界分枝与定界 在在L L0 0的解中，任选一个不满足整数条件的的解中，任选一个不满足整数条件的变量变量x xi i，设，设x xi i=b=bi i ，则做两个子问题，则做两个子问题 不考虑整数条件，用单纯形法求解两个不考虑整数条件，用单纯形法求解两个子问题，子问题，若得整数解或子问题的最优值小于若得整数解或子问题的最优值小于前面分支中已计算得到的所有整数解的目标前面分支中已计算得到的所有整数解的目标函数最大值，则停止分枝；函数最大值，则停止分枝；否则，选取所有否则，选取所有子问题中目标函数值最大的问题作为子问题中目标函数值最大的问题作为L L0 0继续继续分枝，直至得到整数规划的最优解。分枝，直至得到整数规划的最优解。第三步第三步 剪枝剪枝 在所有整数解中选取获得最大值的解为在所有整数解中选取获得最大值的解为最优解。最优解。第四节第四节 割平面法割平面法一、割平面法的基本思想一、割平面法的基本思想 先不考虑整数条件，用单纯形法求解其先不考虑整数条件，用单纯形法求解其松弛问题，若得整数解，即得整数规划最优松弛问题，若得整数解，即得整数规划最优解。否则，增加线性约束条件（称为割平面解。否则，增加线性约束条件（称为割平面方程），将原问题的可行域切割掉一部分，方程），将原问题的可行域切割掉一部分，被切割掉的都是非整数解，再用单纯形法求被切割掉的都是非整数解，再用单纯形法求解新的线性规划问题，依次进行下去，直到解新的线性规划问题，依次进行下去，直到使问题的最优解恰好在可行域的某个具有整使问题的最优解恰好在可行域的某个具有整数坐标的顶点上得到。数坐标的顶点上得到。二、割平面法的步骤二、割平面法的步骤第一步第一步 将问题化为全整数规划问题；将问题化为全整数规划问题；第二步第二步 加非负松弛变量，将约束条件化为等加非负松弛变量，将约束条件化为等式约束；式约束；第三步第三步 解相应的线性规划问题解相应的线性规划问题1.1.若线性规划的最优解是整数解，则得整数若线性规划的最优解是整数解，则得整数规划的最优解，停止计算，否则转规划的最优解，停止计算，否则转2;2;2.2.求解割平面方程作为附加约束条件，构成求解割平面方程作为附加约束条件，构成新的线性规划问题，继续第三步。新的线性规划问题，继续第三步。三、割平面方程的求法三、割平面方程的求法 1.1.求解线性方程组法求解线性方程组法 设设x xi i=b=bi i 是整数规划的松弛问题（是整数规划的松弛问题（LPLP问题）问题）最优解中取分数值（分数部分最大）的基变量，最优解中取分数值（分数部分最大）的基变量，将将x xi i=b=bi i用非基变量表示用非基变量表示 将将b bi i，a aikik分解成整数部分和非负真分数部分之分解成整数部分和非负真分数部分之和：和：要使所有变量都取非负整数值，上式左要使所有变量都取非负整数值，上式左端必为整数，从而右端也必为整数，由于端必为整数，从而右端也必为整数，由于f fi i 0 0，f fikik 0 0，故应有，故应有 这就是所求的割平面方程（这就是所求的割平面方程（GomoryGomory方程）方程）。例例 设某整数规划的松弛问题最优解中有设某整数规划的松弛问题最优解中有x x1 1=3.5 3.5，x x1 1的非基变量表达式为的非基变量表达式为x x1 1=3.5+2.4 x=3.5+2.4 x4 4 3.6 x 3.6 x5 5+4 x+4 x6 6 =3+0.5+2 x =3+0.5+2 x4 4+0.4 x+0.4 x4 4-4 x-4 x5 5+0.4 x+0.4 x5 5+4 x+4 x6 6或或:x x1 1-3-2x-3-2x4 4+4x+4x5 5-4 x-4 x6 6=0.5+0.4x=0.5+0.4x4 4+0.4x+0.4x5 5 由此可得割平面方程为由此可得割平面方程为 0.5+0.4 x0.5+0.4 x4 4+0.4 x+0.4 x5 5 1 1 2.2.借助单纯形表法借助单纯形表法 对求解整数规划问题的松弛问题（对求解整数规划问题的松弛问题（LPLP问题）得到问题）得到最优单纯形表，设最优单纯形表，设x xi i=b=bi i 是最优解中取分数值（分数是最优解中取分数值（分数部分最大）的基变量，则有部分最大）的基变量，则有 上式中，要使等式左端为整数，则右端也必为上式中，要使等式左端为整数，则右端也必为整数，由整数，由0 0f fi i1,1,故应有故应有 这就是所求的割平面方程（这就是所求的割平面方程（GomoryGomory方程）。方程）。例例 设某整数规划的松弛问题最优解中有设某整数规划的松弛问题最优解中有x x1 1=3.5=3.5，x x1 1在单纯形表中的约束条件为：在单纯形表中的约束条件为：x x1 1-2.4x-2.4x4 4+3.6x+3.6x5 5-4x-4x6 6=3.5=3.5 x x1 1-3x-3x4 4+0.6x+0.6x4 4+3x+3x5 5+0.6x+0.6x5 5-4 x-4 x6 6=3+0.5 =3+0.5 或或:x:x1 1-3-3x-3-3x4 4+3x+3x5 5-4x-4x6 6=0.5-0.6x=0.5-0.6x4 4-0.6x-0.6x5 5 由此可得割平面方程为由此可得割平面方程为 0.5-0.6x0.5-0.6x4 4-0.6x-0.6x5 500 解：解：1.1.将问题化为全整数规划问题；去掉变量的将问题化为全整数规划问题；去掉变量的整数要求，可得其松弛问题整数要求，可得其松弛问题G G0 02.2.加松弛变量，将约束化为等式约束；并用加松弛变量，将约束化为等式约束；并用单纯形法求解得到最优表；（表单纯形法求解得到最优表；（表4-44-4）3.找出非整数解变量中非整数部分最大的找出非整数解变量中非整数部分最大的一个基变量（这里是一个基变量（这里是x2），并写出这一行），并写出这一行的约束；的约束；4.4.由于表中还有非整数解，找出非整数解变量由于表中还有非整数解，找出非整数解变量中非整数部分最大的一个基变量（这里是中非整数部分最大的一个基变量（这里是x x1 1），），并写出这一行的约束；并写出这一行的约束；该表已得到整数解，故原整数规划问题的最优解为该表已得到整数解，故原整数规划问题的最优解为:x:x1 1=4=4，x x2 2=1=1，最优值为最优值为max z=14max z=14作业：作业：P127129 4.13 4.14 4.16 4.18 P127129 4.13 4.14 4.16 4.18 第五节第五节 解解0-10-1规划问题的隐枚举法规划问题的隐枚举法一、隐枚举法的基本思想一、隐枚举法的基本思想 首先令所有整数变量都取首先令所有整数变量都取0 0值，然后使某些变量值，然后使某些变量取值为取值为1 1，直到获得一个可行解，将第一个可行解作，直到获得一个可行解，将第一个可行解作为临时最优解（称为过滤条件），再继续试探某些为临时最优解（称为过滤条件），再继续试探某些变量的取值，若可找到另一个可行解优于临时最优变量的取值，若可找到另一个可行解优于临时最优解，则将新的可行解作为临时最优解（新的过滤条解，则将新的可行解作为临时最优解（新的过滤条件），依此类推，检查整数变量等于件），依此类推，检查整数变量等于0 0或或1 1的各种组的各种组合，不断寻求新的临时最优解，直到获得问题的最合，不断寻求新的临时最优解，直到获得问题的最优解为止。优解为止。由于只计算部分可行解的组合（优于临时最优由于只计算部分可行解的组合（优于临时最优解的组合），故称为隐枚举法。解的组合），故称为隐枚举法。二、举例二、举例例例3.3.求解求解0-10-1规划规划解解 ：求解过程可以列表如下：求解过程可以列表如下第五节第五节 应用举例应用举例例例3 东方大学计算机实验室聘用东方大学计算机实验室聘用4名大学生名大学生(代号代号1、2、3、4)和和2名研究生名研究生(代号代号5、6)值班答疑。已值班答疑。已知每人从周一至周五每天最多可安排的值班时间及知每人从周一至周五每天最多可安排的值班时间及每人每小时值班的报酬如下表每人每小时值班的报酬如下表47所示：所示：该实验室开放时间为上午该实验室开放时间为上午8:00至晚上至晚上10:00，开，开放时间内须有且仅须一名学生值班。规定大学生放时间内须有且仅须一名学生值班。规定大学生每周值班不少于每周值班不少于8h，研究生每周不少于，研究生每周不少于7h，每名，每名学生每周值班不超过学生每周值班不超过3次，每次值班不少于次，每次值班不少于2h，每天安排值班的学生不超过每天安排值班的学生不超过3人，且其中必须有人，且其中必须有一名研究生试为该实验室安排一张人员的值班一名研究生试为该实验室安排一张人员的值班表，使总支付的报酬为最少表，使总支付的报酬为最少 解：解：设设xij为学生为学生i在周在周j的值班时间，用的值班时间，用aij代表代表学生学生i在周在周j最多可安排的值班时间，最多可安排的值班时间，ci为学生为学生i的的每小时的报酬，则数学模型见下页。每小时的报酬，则数学模型见下页。例例6 清源市下设八个区，表清源市下设八个区，表411给出救护车从给出救护车从一个区至另一个区的车程时间一个区至另一个区的车程时间(min)。该市拟建救。该市拟建救护中心，要求各区离救护中心的车程时间必须在护中心，要求各区离救护中心的车程时间必须在8 min之内试为该市提供决策建议：至少建多少个之内试为该市提供决策建议：至少建多少个救护中心，建于何处救护中心，建于何处?求解结果为求解结果为x1=1，x6=1，即至少在，即至少在1、6两个区两个区各建一个救护中心。各建一个救护中心。