运筹学-第五章整数规划

1、薛威 2015年4月,运筹学 第五章整数规划,Textmasterformate durch Klicken bearbeiten Zweite Ebene Dritte Ebene Vierte Ebene Fnfte Ebene,【教学目的】 通过本单元的学习，使学生掌握整数问题的概念，类型和模型的建立，能够运用分支界定法求解一般整数问题，并掌握0-1整数规划和指派问题的基本求解方法。,Lets go,第五章整数规划,整数规划问题介绍 整数规划算法分枝定界法 整数规划算法割平面法 0-1整数规划 指派问题(分派问题),线性规划模型：,实际问题要求xi为整数！,如机器的台数，人数等,线性整数

2、规划,非线性整数规划,简称整数规划,整数线性规划问题,纯整数规划的数学模型：,0-1规划的数学模型：,纯整数规划,01规划,混合型整数规划,例1.胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,纯整数规划,例2.某服务部门各时段（每2小时为一时段）需要的服务员人数见下表。按规定，服务员连续工作8小时（即4个时段）为一班。现要求安排服务员的工作

3、时间，使服务部门服务员总数最少。,解 设在第j时段开始时上班的服务员人数是xj。由于第j时段开始时上班的服务员将在第（j+1）时段结束时下班，所以决策变量只需考虑x1，x2 ，x3 ，x4 ，x5。该问题的数学模型是,解：,混合型整数规划,数学模型：,总结 整数规划的可行域包含在其对应的一般线性规划可行域之内； 整数规划的最优解可能不是其对应的一般线性规划的顶点； 整数规划的最优解不会优于其对应的线性规划的最优解。,分支定界法,1、基本思路,考虑纯整数问题：,整数问题的松弛问题：,（1）先不考虑整数约束，解( IP )的松弛问题( LP )，可能得到以下情况之一： 若( LP )没有可行解，则

4、( IP )也没有可行解，停止计算。 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。 为讨论方便，设( LP )的最优解为：,（2）分支：,在( LP )的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr= br （不为整数），以br表示不超过br的最大整数。构造两个约束条件 xr br 和 xr br1,将这两个约束条件分别加入问题( IP ) ，形成两个子问题( IP1)和( IP2 ) ，再解这两个子问题的松弛问题( LP1)和( LP2) 。

5、,（3）定界：,记( IP )的目标函数最优值为 ,以 作为 的下界，记为 。令 ，则有,（4）修改上、下界：按照以下两点规则进行。 在各分枝问题中，找出目标函数值最小者作为新的下界； 从已符合整数条件的分枝中，找出目标函数值最小者作为新的上界。,（5）比较与剪枝 ： 各分枝的目标函数值中，若有大于 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。,如此反复进行，直到得到 为止， 即得最优解 X* 。,2、例题,max Z=40X1 + 90X2,解：先解该整数规划对应的松弛问题,选X1分枝,问题2,问题3,选(2)继续分枝,分支定界过程,x1x*01,x1x*01+1,总结

6、,割平面法,割平面法的基本思想：,若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.,.,原最优解要被割去,可行域中割去一部分，割去部分不含整数解，,割平面法原理：,计算步骤： （1）用单纯形法求解( IP )对应的松弛问题( LP )： 若( LP )没有可行解，则( IP

7、)也没有可行解，停止计算。 若( LP )有最优解，并符合( IP )的整数条件，则( LP )的最优解即为( IP )的最优解，停止计算。 若( LP )有最优解，但不符合( IP )的整数条件，转入下一步。,（2）从(LP)的最优解中，任选一个不为整数的分量xr,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：,的小数部分,的小数部分,（3）将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用单纯形法求出新的最优解，返回1。,例：用割平面法求解整数规划问题,解：增加松弛变量x3和x4 ，得到(LP)的初始单

8、纯形表和最优单纯形表：,此题的最优解为：X= (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面。,此题的最优解为：X= (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 生成割平面的条件为:,0-1整数规划,枚举法：,检验可行解： 32次运算,计算目标 函数值：8次,（0 0 0）,（0 0 1）,（0 1 0）,（1 0 0）,（1 0 1）,（1 1 0）,（1 1 1）,0,-2,5,3,1,8,3,6, , , ,Z0,Z5,运算次数：21,（0 1 1

9、）,01 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1，一般的解法为隐枚举法。 是否能对上述方法进行优化，使得运算量进一步减少呢？根据上述算法的特点，可以按目标函数中各变量系数的大小顺序重新排列各变量，以使最优解尽可能早出现。,试用改进的算法求解下题：,在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。,指派问题,

10、设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( i, j=1.2. n ),其数学模型为：,指派问题的性质,定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解,解题步骤：,指派问题是0-1 规划的特例，当然可用整数规划，0-1 规划的解法去求解，但运算繁琐。利用指派问题的特点可有更简便的解法，这就是匈牙利法(匈牙利数学家D.Konig提出) ，即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。,第一步：变换指派问题的系数(也称效率)矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素

11、，即 (1) 从（cij）的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。,第二步：进行试指派，以寻求最优解。 在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为： (1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作 。然后划去 所在列(行)的其它0元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了。 (2)给只有一个0元素的列(行)中的0元素加圈，记作；然后划去 所在行的0元素，记作 (3)反复进行(1)，(2

12、)两步，直到尽可能多的0元素都被圈出和划掉为止。,(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若 元素的数目m 等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。 第三步：作最少的直线覆盖所有0元素。 (1)对没有的行打号； (2)对已打号的行中所有含元素的列打号； (3)再对打有号的列中含 元素的行打号；,(4)重复(2)，

13、(3)直到得不出新的打号的行、列为止； (5)对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 lm n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。 第四步：变换矩阵(bij)以增加0元素。 在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。,例：求费用矩阵为右表的 指派问题的最优解,费用,工作,人,甲 乙 丙 丁 戊,A B C D E,12

14、7 9 7 9,8 9 6 6 6,7 17 12 14 12,15 14 6 6 10,4 10 7 10 6,第一步：每行减去最小元素，每列减掉最小元素; 第二步：对零元素画圈打; 第三步: 划线覆盖零元素;,-7,-6,-7,-6,-4,得4个，且不存在没打的0,第四步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。,匈牙利法的具体步骤：,第一步：变换指派问题的费用矩阵，使其在各行各列都出现0元素；方法：首先每行元素减去该行的最小元素，然后每列减去该列的最小元素,第二步：进行试指派（画）,方法：从含0元素最少的行或列开始，圈出一个0元素，用 表示，然

15、后划去该所在的行和列中的其余0元素，用表示，依次类推。,若矩阵中的的个数等于n，则得最优解,若矩阵中的的个数n，则进行第三步,第三步：做能复盖所有0元素的最小直线集合：,1）对没有的行打号,2）对打号的行上所有0元素的列打号,3）再对打号的列上所有的行打号,4）重复以上步骤直到得不出新的打号为止,5）对没有打号的行画横线，所有打号的列画纵线，所得到的直线既是复盖所有0元素的最小直线集合,第四步：在没有被直线复盖的元素中找出最小元素，让打号的列加上这个元素，打号的行减去这个元素。,混合型,x13,x14,L0的最优单纯型表：,随堂练习,x13,x14,x22,x23,x12,x13,用隐枚举法求解下题,匈牙利法求解下题,有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不同文字所需的时间(h)如表所示。问：如何分配任务使效率最高？,本章小结,某地准备投资D元建民用住宅。可以建住宅的地点有 处： 。在 处每幢住宅的造价为 ，最多限造 幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。,一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为a，携带物品总重量不超过b。现有物品m件，第i件物品体积为 ，重量为 ，i=1,2,.,m。为了比较物品的有用程