运筹学第四章整数规划与分配问题ppt课件

1、作业：作业：P126 4.1 4.2 4.3(a) 4.4第四章第四章 整数规划与分配问题整数规划与分配问题第一节第一节 整数规划的特点及运用整数规划的特点及运用一、整数规划的普通方式一、整数规划的普通方式定义：一部分或全部决策变量必需取整数定义：一部分或全部决策变量必需取整数值的规划问题称为整数规划。不思索整数值的规划问题称为整数规划。不思索整数条件，由余下的目的函数和约束条件构成条件，由余下的目的函数和约束条件构成的规划问题称为该整数规划的松弛问题。的规划问题称为该整数规划的松弛问题。假设松弛问题是线性规划，那么该整数规假设松弛问题是线性规划，那么该整数规划称为整数线性规划。划称为整数线性

2、规划。且部分或全部取整数）或或),.2 , 1(0),.2 , 1(min)max(11njxmibxaxczjijnjijjnjj且均取整数值最优解求下述整数规划问题的例, 0,5 . 45 . 0143223max. 121212121xxxxxxxxz整数线性规划的普通方式:不思索整数要求时，不思索整数要求时，最优解为：最优解为： X=(3.25 ,2.5)T X=(3.25 ,2.5)T Z=13 Z=13 见下页图解法见下页图解法思索整数要求时，最优解为：思索整数要求时，最优解为：X=(4 ,1)T Z=14X=(4 ,1)T Z=14凑整凑整 3 3，2 2可行，非最优，可行，非最

3、优，Z=13Z=13。 4 4，3 3，4 4，2 2，3 3，3 3 不可行不可行二、整数规划的分类二、整数规划的分类1. 1. 全整数线性规划全整数线性规划 决策变量全部取整数，约束系数和约束常数项决策变量全部取整数，约束系数和约束常数项也取整数的整数线性规划。也取整数的整数线性规划。2. 2. 纯整数线性规划纯整数线性规划 决策变量全部取整数，约束系数和约束常数项决策变量全部取整数，约束系数和约束常数项可取非整数的整数线性规划。可取非整数的整数线性规划。 纯整数线性规划可化为全整数线性规划。纯整数线性规划可化为全整数线性规划。3. 3. 混合整数线性规划混合整数线性规划 决策变量中有一部

4、分取整数值，另一部分可取决策变量中有一部分取整数值，另一部分可取非整数值的整数线性规划。非整数值的整数线性规划。4. 0-14. 0-1整数线性规划整数线性规划 决策变量只能取决策变量只能取0 0或或1 1的整数线性规划。的整数线性规划。三、三、0-1变量或称逻辑变量在模型中变量或称逻辑变量在模型中的运用的运用 整数规划模型对研讨管理问题有重整数规划模型对研讨管理问题有重要意义。很多不能归结为线性规划数学要意义。很多不能归结为线性规划数学模型的管理问题，却可以经过设置逻辑模型的管理问题，却可以经过设置逻辑变量建立起整数规划数学模型。变量建立起整数规划数学模型。第二节第二节 分配问题分配问题(

5、(指派问题与匈牙利法指派问题与匈牙利法 2-1 2-1 问题的提出及数学模型问题的提出及数学模型 假设有假设有m m项义务分配给项义务分配给m m个人去完成，并个人去完成，并指定每个人完成其中一项，每项义务也只由指定每个人完成其中一项，每项义务也只由一个人完成，问应如何分配义务，才干使总一个人完成，问应如何分配义务，才干使总效率最高？或总费用最少，破费的总时间效率最高？或总费用最少，破费的总时间最少等等。最少等等。 设每个人完成不同义务的耗费见下面的设每个人完成不同义务的耗费见下面的效率矩阵，通常要求效率矩阵，通常要求aij0aij0。 mmmmmmmmijaaaaaaaaaaA.212222

6、111211),.,2 , 1,(j0, 1mjiijixij项任务。人去完成第不分配第，项任务；人去完成第分配第又设那么分配问题的数学模型为那么分配问题的数学模型为),.,2 , 1,(10),.,2 , 1( 1),.,2 , 1( 1min1111mjixmjxmixxazijmiijmjijmimjijij，或2-2 2-2 匈牙利法匈牙利法定理定理1.1.假设从分配问题效率矩阵假设从分配问题效率矩阵(aij)(aij)的每一的每一行元素中分别减去或加上一个常数行元素中分别减去或加上一个常数ui ui 称为该行的位势；从每一列中分别减去称为该行的位势；从每一列中分别减去或加上一个常数或

7、加上一个常数 vj vj 称为该列的位称为该列的位势；得到一个新的效率矩阵势；得到一个新的效率矩阵bijbij，其中，其中bij= bij= aij - ui - vj aij - ui - vj ，那么，那么aijaij的最优解等价于的最优解等价于bijbij的最优解。的最优解。定理定理2. 2. 假设效率矩阵假设效率矩阵A A的元素可分成的元素可分成0 0与非与非0 0两部分，那么覆盖一切两部分，那么覆盖一切0 0元素的最少直线数等元素的最少直线数等于位于不同行不同列的于位于不同行不同列的0 0元素的最大个数。元素的最大个数。匈牙利法的步骤：匈牙利法的步骤：第一步第一步 效率矩阵每行都减去

8、该行的最小元素；效率矩阵每行都减去该行的最小元素；第二步第二步 效率矩阵每列都减去该列的最小元素；效率矩阵每列都减去该列的最小元素； 此时，效率矩阵的每行每列都有此时，效率矩阵的每行每列都有0 0元素。元素。第三步第三步 寻觅位于不同行不同列的寻觅位于不同行不同列的0 0元素，也就是元素，也就是寻觅能覆盖一切寻觅能覆盖一切0 0元素的最少直线数。元素的最少直线数。 方法：方法：1. 1. 从只需一个从只需一个0 0元素的行开场，对元素的行开场，对0 0元素打上元素打上 号，然后对打号，然后对打 的的0 0元素所在列画一条直线，元素所在列画一条直线，依次进展到最后一行；依次进展到最后一行；2.

9、2. 从只需一个从只需一个0 0元素的列开场，对元素的列开场，对0 0元素打上元素打上 号，号， 然后对打然后对打 的的0 0元素所在行画一条直线，元素所在行画一条直线，依次进展到最后一列；依次进展到最后一列；3. 3. 反复反复1.1.、2.2.两个步骤，能够出现三种情况：两个步骤，能够出现三种情况： 1 1假设能找到假设能找到m m个位于不同行不同列的个位于不同行不同列的0 0元素元素即带即带 的的0 0元素，那么令元素，那么令0 0处的处的xij=1,xij=1,求解终了；求解终了；2 2假设有构成闭回路的假设有构成闭回路的0 0元素，那么任选一个元素，那么任选一个打打 ，然后对每个间隔

10、的，然后对每个间隔的0 0元素打元素打 ，同，同时对打时对打 的的0 0元素所在行或列画一条直线。元素所在行或列画一条直线。 3 3假设位于不同行不同列的假设位于不同行不同列的0 0元素元素 即带即带 的的0 0元素元素 少于少于m m，转第四步。，转第四步。 第四步第四步 为产生为产生m m个位于不同行不同列的个位于不同行不同列的0 0元素，元素，用定理一对效率矩阵进展调整，使之生成新的用定理一对效率矩阵进展调整，使之生成新的0 0元素。方法：元素。方法：1. 1. 在效率矩阵未被直线覆盖的元素中找出最小在效率矩阵未被直线覆盖的元素中找出最小元素元素k k；2. 2. 效率矩阵未被直线覆盖的

11、行都减效率矩阵未被直线覆盖的行都减k;k;3. 3. 效率矩阵被直线覆盖的列都加效率矩阵被直线覆盖的列都加k;k;4. 4. 转回第三步。转回第三步。2-3 特殊情况的处置特殊情况的处置1. 人数多于义务数，加虚拟义务。人数多于义务数，加虚拟义务。设有设有n人，人，m项义务，项义务，nm,那么添加那么添加n-m项义务。项义务。2. 人数少于义务数，加虚拟人员。人数少于义务数，加虚拟人员。设有设有n人，人，m项义务，项义务，nm,那么添加那么添加m-n项义务。项义务。此时，效率矩阵的元素全成为负值，不符合要此时，效率矩阵的元素全成为负值，不符合要求，根据定理求，根据定理1 1，令，令变换后的效率

12、矩阵每行都加变换后的效率矩阵每行都加M M即可。即可。mimjijijxaz11)(min ijaMmax3. 对求最大值问题的处置对求最大值问题的处置设目的函数为设目的函数为可将其变换为可将其变换为mimjijijxaz11max作业：作业：P127 4.8(a)P127 4.8(a)第三节第三节 分枝定界法分枝定界法一、分枝定界法的根本思想一、分枝定界法的根本思想 先不思索整数解的限制，用单纯形法求先不思索整数解的限制，用单纯形法求解其松弛问题，假设求得的解恰好是整数解，解其松弛问题，假设求得的解恰好是整数解，那么得整数规划最优解，停顿计算。否那么，那么得整数规划最优解，停顿计算。否那么，

13、将松弛问题分解为两个子问题也称后继问将松弛问题分解为两个子问题也称后继问题，每个子问题都是在原松弛问题的根底题，每个子问题都是在原松弛问题的根底上添加一个变量取整数的约束条件，这样就上添加一个变量取整数的约束条件，这样就减少了原来的可行域，然后用单纯形法求解，减少了原来的可行域，然后用单纯形法求解，直至得到最终结果。直至得到最终结果。二、分枝定界法的步骤最大值问题二、分枝定界法的步骤最大值问题第一步第一步 寻觅替代问题并求解寻觅替代问题并求解 设原整数规划问题为设原整数规划问题为IPIP，其松弛问题为，其松弛问题为L0L0。用单纯形法求用单纯形法求L0L0，假设，假设L0L0无可行解，那么无可

14、行解，那么IPIP也也无可行解，计算停顿。假设求得无可行解，计算停顿。假设求得L0L0为整数解，为整数解，那么得那么得IPIP的最优解，停顿。否那么，转下一步；的最优解，停顿。否那么，转下一步；第二步第二步 分枝与定界分枝与定界 在在L0L0的解中，任选一个不满足整数条件的的解中，任选一个不满足整数条件的变量变量xixi，设，设xi = bi xi = bi ，那么做两个子问题，那么做两个子问题 iibxL,1 1,2iibxL 不思索整数条件，用单纯形法求解两个不思索整数条件，用单纯形法求解两个子问题，假设得整数解或子问题的最优值小子问题，假设得整数解或子问题的最优值小于前面分支中已计算得到

15、的一切整数解的目于前面分支中已计算得到的一切整数解的目的函数最大值，那么停顿分枝；否那么，选的函数最大值，那么停顿分枝；否那么，选取一切子问题中目的函数值最大的问题作为取一切子问题中目的函数值最大的问题作为L0L0继续分枝，直至得到整数规划的最优解。继续分枝，直至得到整数规划的最优解。 第三步第三步 剪枝剪枝 在一切整数解中选取获得最大值的解为在一切整数解中选取获得最大值的解为最优解。最优解。且均取整数值数规划问题的最优解用分枝定界法求下述整例, 0,5 . 45 . 0143223max.21212121xxxxxxxxz第四节第四节 割平面法割平面法一、割平面法的根本思想一、割平面法的根本

16、思想 先不思索整数条件，用单纯形法求解其先不思索整数条件，用单纯形法求解其松弛问题，假设得整数解，即得整数规划最松弛问题，假设得整数解，即得整数规划最优解。否那么，添加线性约束条件称为割优解。否那么，添加线性约束条件称为割平面方程，将原问题的可行域切割掉一部平面方程，将原问题的可行域切割掉一部分，被切割掉的都是非整数解，再用单纯形分，被切割掉的都是非整数解，再用单纯形法求解新的线性规划问题，依次进展下去，法求解新的线性规划问题，依次进展下去，直到使问题的最优解恰好在可行域的某个具直到使问题的最优解恰好在可行域的某个具有整数坐标的顶点上得到。有整数坐标的顶点上得到。二、割平面法的步骤二、割平面法

17、的步骤第一步第一步 将问题化为全整数规划问题；将问题化为全整数规划问题； 第二步第二步 加非负松弛变量，将约束条件化为等加非负松弛变量，将约束条件化为等式约束；式约束； 第三步第三步 解相应的线性规划问题解相应的线性规划问题1. 1. 假设线性规划的最优解是整数解，那么得假设线性规划的最优解是整数解，那么得整数规划的最优解，停顿计算，否那么转整数规划的最优解，停顿计算，否那么转2;2;2. 2. 求解割平面方程作为附加约束条件，构成求解割平面方程作为附加约束条件，构成新的线性规划问题，继续第三步。新的线性规划问题，继续第三步。三、割平面方程的求法三、割平面方程的求法 1.1.求解线性方程组法求

18、解线性方程组法 设设xi=bi xi=bi 是整数规划的松弛问题是整数规划的松弛问题LPLP问题问题最优解中取分数值分数部分最大的基变量，最优解中取分数值分数部分最大的基变量，将将xi=bixi=bi用非基变量表示用非基变量表示 将将bibi，aikaik分解成整数部分和非负真分数部分分解成整数部分和非负真分数部分之和：之和：kkikiixabxkkikikkikiikkikikkikikkikikiiiikikikikiiiixffxNNxxffxNNxfNfNxffNaffNb)() 10() 10(得kkikiixabx 要使一切变量都取非负整数值，上式左要使一切变量都取非负整数值，上式

19、左端必为整数，从而右端也必为整数，由于端必为整数，从而右端也必为整数，由于fi fi 0 0 ， fik 0 fik 0 ，故应有，故应有 这就是所求的割平面方程这就是所求的割平面方程GomoryGomory方程方程 。1kkikixff例例 设某整数规划的松弛问题最优解中有设某整数规划的松弛问题最优解中有x1 = x1 = 3.5 3.5 ， x1 x1的非基变量表达式为的非基变量表达式为x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 x1=3.5 + 2.4 x4 3.6 x5 + 4 x6 =3+0.5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 =3+0.

20、5+2 x4 +0.4 x4 - 4 x5 +0.4 x5 +4 x6x6或或: : x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 x1-3- 2x4+4x5-4 x6 = 0.5+0.4x4+0.4x5 由此可得割平面方程为由此可得割平面方程为 0.5 + 0.4 x4 + 0.4 x5 1 0.5 + 0.4 x4 + 0.4 x5 1 2. 2. 借助单纯形表法借助单纯形表法 对求解整数规划问题的松弛问题对求解整数规划问题的松弛问题LPLP问题得到问题得到最优单纯形表，设最优单纯形表，设xi=bi xi=bi 是最优解中取分数值分数是最优解中取分数值分数部分最

21、大的基变量，那么有部分最大的基变量，那么有kkikiikkikiikikikikiikikikikiiiiikiikkikixffNxNxfNxfNxffNaffNbabbxax即得令真分数部分之和，分解成整数部分和非负将)() 10() 10(, 上式中，要使等式左端为整数，那么右上式中，要使等式左端为整数，那么右端也必为整数，由端也必为整数，由0 0fifi1,1,故应有故应有 这就是所求的割平面方程这就是所求的割平面方程GomoryGomory方程。方程。0kkikixff例例 设某整数规划的松弛问题最优解中有设某整数规划的松弛问题最优解中有x1=3.5 x1=3.5 ， x1x1在单纯

22、形表中的约束条件为：在单纯形表中的约束条件为： x1-2.4x4 +3.6x5 -4x6=3.5 x1-2.4x4 +3.6x5 -4x6=3.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 x1-3x4+0.6x4+3x5+0.6x5-4 x6=3+0.5 或或: x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 : x1-3-3x4+3x5-4x6=0.5-0.6x4-0.6x5 由此可得割平面方程为由此可得割平面方程为 0.5 -0.6x4 -0.6x50 0.5 -0.6x4 -0.6x50 且均取整数值规划问题的最优解用割平面法求下述整数例,

23、0,5 . 45 . 0143223max.21212121xxxxxxxxz解：解：1.1.将问题化为全整数规划问题；去掉变量的将问题化为全整数规划问题；去掉变量的整数要求，可得其松弛问题整数要求，可得其松弛问题G0G02. 2. 加松弛变量，将约束化为等式约束；并加松弛变量，将约束化为等式约束；并用单纯形法求解得到最优表；表用单纯形法求解得到最优表；表4-44-40,92143223max21212121xxxxxxxxz0,92143223max432142132121xxxxxxxxxxxxz3. 找出非整数解变量中非整数部分最大的找出非整数解变量中非整数部分最大的一个基变量这里是一个

24、基变量这里是x2，并写出这一行，并写出这一行的约束；的约束；:02121212121212)212()211()210(2122121434342432432加松弛变量化为等式所以，割平面方程为或即xxxxxxxxxxxx。形表，见表的单纯法继续求解得到中，然后用对偶单纯形的单纯形表解，可将该式直接加入求问题的约束中，得一新的将上式加入松弛问题54LP2121211010543GGGGxxx 4.由于表中还有非整数解，找出非整数解变量由于表中还有非整数解，找出非整数解变量中非整数部分最大的一个基变量这里是中非整数部分最大的一个基变量这里是x1，并写出这一行的约束；并写出这一行的约束；:0212

25、1212132132121321555415541541加松弛变量化为等式得割平面方程为或即xxxxxxxxxxxx。单纯形表，见表的续求解得到然后用对偶单纯形法继的单纯形表中，可将该式直接加入求解，问题中得一新的将上式加入到64LP2121212165GGGGxx该表已得到整数解，故原整数规划问题的最优解该表已得到整数解，故原整数规划问题的最优解为为: x1 = 4: x1 = 4， x2 = 1x2 = 1， 最优值为最优值为max z=14max z=14作业：作业：P128130 4.13 4.14 4.16 4.18 P128130 4.13 4.14 4.16 4.18 第五节第五

26、节 解解0-10-1规划问题的隐枚举法规划问题的隐枚举法一、隐枚举法的根本思想一、隐枚举法的根本思想 首先令一切整数变量都取首先令一切整数变量都取0 0值，然后使某值，然后使某些变量取值为些变量取值为1 1，直到获得一个可行解，将第，直到获得一个可行解，将第一个可行解作为暂时最优解称为过滤条一个可行解作为暂时最优解称为过滤条件，再继续试探某些变量的取值，假设可件，再继续试探某些变量的取值，假设可找到另一个可行解优于暂时最优解，那么将找到另一个可行解优于暂时最优解，那么将新的可行解作为暂时最优解新的过滤条新的可行解作为暂时最优解新的过滤条件，依此类推，检查整数变量等于件，依此类推，检查整数变量等于0 0或或1 1的的各种组合，不断寻求新的暂时