第五章整数规划.ppt

1、整数规划,1.整数规划的数学模型及解的特点 2.分支定界法、割平面法 3.0-1整数规划 4.指派问题,1.整数规划的数学模型及解的特点,整数规划数学模型的一般形式 一部分或全部决策变量取整数值的规划问题 整数规划 整数规划中不考虑整数条件是对应的规划问题 该整数规划的松弛问题 松弛问题为线性规划的整数规划问题 整数线性规划,整数线性规划一般形式：,中部分或全部取整数,整数线性规划的几种类型,纯整数线性规划 混合整数线性规划 0-1型整数线性规划 例如选择投资项目问题（0-1规划问题）,整数规划的例子 例1：生产计划问题。 例2：某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规

2、定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。,解：设在第j时段开始上班的人数为 ，则,且为整数,解的特点 整数线性规划及其松弛问题比较，前者的最优解的目标函数值不会优于后者的。,例：考虑下面的整数规划问题,且取整数,从图上分析：,整数规划最优解,2.分支定界法,分支定界法是枚举法基础上的改进。 分支定界法的关键是分支和定界。 思路：利用其松弛问题的最优解（值）来分支定界。,例：求解整数规划问题A,且为整数,松弛问题B,设问题A的最优目标函数值为 。,整数规划问题A,初始上界,图解法分析：,、 、 、 、 、 、 、 、 、 、 、 0 1 2 3 4 5

3、 6 7 8 9 10,8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 -,B,不是问题A解 但,图解法分析：,0 1 2 3 4 5 6 7,4 3 2 1,图解法分析：,0 1 2 3 4 5 6 7,4 3 2 1,图解法分析：,4 3 2 1,0 1 2 3 4 5 6 7,是问题A解 但,不是问题A解 而 剪枝,图解法分析：,分支定界的全过程：,分支定界的全过程：,步骤：,步骤1、整数规划问题为A，其松弛问题为B， 设 为问题A的初始下界（min问题为上界） 步骤2、求解问题B，有三种情况： （a）B无可行解，此时问题A也无可行解，停止。 （b）B有可行解且为整数，则问题

4、B的最优解即是问题A的最优解，停止。 （c） B有可行解但不是整数，设目标函数值为 它是问题A的上（下）界，转入步骤3。,步骤3、分支、定界。 步骤4、比较、剪枝。,3.0-1整数规划,标准型 解法,01整数规划的标准型和解法,必须,必须大于 等于0,解法 全枚举法（不展开论述） 隐枚举法（重点讲述）,标准型,隐枚举法求解步骤（一）,（1）令全部都是自由变量且取0值，检验解是否可行。若可行，已得最优解；若不可行，进行步骤（2）。 （2）将某一变量转为固定变量，令其取值为1或0，使问题分成两个子域。令一个子域中的自由变量都取0值，加上固定变量取值，组成此子域的解。 （3）计算此解的目标函数值，与

5、已求出的可行解最小目标函数值比较。如果前者大，则不必检验其是否可行而停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝即使得到可行解，其目标函数值也较大，不会是最优解；如前者小，进行步骤（4）。对第一次算出的目标函数值，不必进行比较，直接转到步骤（4）。 （4）检验解是否可行。如可行，已得一个可行解，计算并记下它的z值，并停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝，即使得到可行解，目标函数值也比记下的z值大，不会是最优解；如不可行，进行步骤（5）。,隐枚举法求解步骤（二）,（5）将子域固定变量的值代入第一个不等式约束条件方程，并令不等式左端的自由变量

6、当系数为负时取值为1，系数为正时取值为0，这就是左端所能取得最小值。若此最小值大于右端值，则称此子域为不可行子域，不再往下分枝，若子域都检验过，转步骤（7），否则，转步骤（6）；若此最小值小于右端值，则依次检验下一个不等式约束方程，直至所有的不等式约束方程都通过，若子域都检验过，转步骤（7），否则，转步骤（6）。 （6）定出尚未检验过的另一个子域的解，执行步骤（3）（5），若所有子域都停止分枝，计算停止，目标函数值最小的可行解就是最优解；否则，转（7）。 （7）检查有无自由变量。若有，转（2）；如没有，计算停止。目标函数值最小的可行解就是最优解。,隐枚举法举例,(0,0,0,0,0),(0,1

7、,0,0,0),(0,1,0,1,0),(0,1,0,0,0),(0,1,1,0,0),(0,0,0,0,0),(0,1,0,0,0),(0,0,0,0,0),(1,0,0,0,0),说明： 彩色字体为固定变量。,Z1=8，可行，停止分支。,Z2=0 Z1 ，不可行；可行子域，分支。,Z3=2 Z1 ，不可行，可行子域，分支。,Z4=0 Z1 ，不可行，不可行子域，停止分支。,Z5=6 Z1 ，可行，停止分支。,Z6=2 Z5，不可行，可行子域，分支。,Z7=9 Z5 ，停止分支。,Z8=2 Z5 ，不可行，不可行子域，停止分支。,令所有变量都为0，不可行，分支。,4. 指派问题(assign

8、ment problem),4.1指派问题的标准形式及其数学模型 4.2匈牙利解法 4.3一般的指派问题,指派问题的标准形式的提出？,在我们现实生活中，常有各种性质的指派问题。例如：应如何分配若干项工作给若干个人（或部门）来完成，以达到总体的最佳效果等等。由于指派问题的多样性，我们有必要定义指派问题的标准形式。,4.1指派问题的标准形式及其数学模型,指派问题的标准形式（以人和事为例） n个人做n件事，并且要求每人必须而且只做一件事。设第i人做第j件事的费用为 Cij（i,j1，2，n)，使总费用最少。,因此，我们可得指派问题的系数矩阵,4.1指派问题的标准形式及其 数学模型,为了建立标准指派问题的数学模型，我们引入nxn个 01变量。并且得到该问题的数学模型。,来表示。指派问题有n! 个可行解。,对于问题的每个可行解，可用解矩阵,例（12） 课本145页,建立数学模型,这是一个标准的指派问题。若设01变量,指派问题的求解,表上作业法 匈牙利法,4.3一般的指派问题,在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将他们化为标准形式，然后再用匈牙利解法解之 1、最大化指派问题 设最大化指派问题系数矩阵C=(Cij)nn,其中最大元素为m,令矩阵B=(bij)nn=(m-cij)nn,则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化