运筹学第2章整数规划.ppt

1、第四章 整数规划,整数规划问题的提出,依照决策变量取整要求的不同，整数规划可分为纯整数规划、 01整数规划、混合整数规划。,整数规划模型与一般的线性规划模型的区别仅在于：整数规划的变量要求部分的或全部的为整数。例如：,纯整数规划：如果所有决策变量都要求取整数，则称为“纯整数规划”,混合整数规划：如果仅有一部分的决策变量要求取整数，则称为“混合型整数规划”。,01整数规划：所有决策变量仅限于取 0 或 1 两个整数，这种规划问题称为“0-1规划”,求解思路：既然整数规划是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整求解即可。？,但实际上，两者却有很大的不同，通过舍入得到的整数

2、解也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。举例说明。,例：设整数规划问题如下,首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。,用图解法求出最优解 x13/2, x2 = 10/3 且有Z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3) (2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点 ，如图所示。,2,1,2,1,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如此例中

3、（2，2）（3，1）点为最大值，Z=4。,整数规划问题的求解方法,目前，常用的求解整数规划的方法有： 分枝定界法、割平面法； 隐枚举法、匈牙利法。,整数规划模型应用举例,排班问题（人力资源配置问题）,例：邮局每天需要的职工数因业务忙闲而异，据统计邮局一周内每天需要的人数如下表。排班要符合每周连续工作5天，休息2天的规定。问如何排班可使用人最少。,(纯整数规划问题),解：设xi为第i天开始上班的人数： Min：z=x1+x2+x3+x4+x5+x6+x7 s.t. x1 +x4+x5+x6+x717 x1+x2 +x5+x6+x713 x1+x2+x3 +x6+x715 x1+x2+x3+x4+

4、 +x719 x1+x2+x3+x4+x5 14 x2+x3+x4+x5+x6 16 x3+x4+x5+x6+x711 xi0 （ i=1,2,7） X=(1.3, 3.3, 2, 7.3, 0, 3.3, 5)T , z=22.3,X*=( 7, 5, 1, 8, 0, 2, 0)T , z=23,(纯整数规划问题),背包问题,目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大 。 例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。,背包问题的数学模型： 01规划,解：设01变量表示携带物品i，表示不携带物品i，则

5、问题可写为 可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。,布点问题,共同目标：满足公共要求，布点最少，节约投资费用。 学校、医院、商业区、消防队等公共设施的布点问题。 例：某市6个区，希望设置最少消防站以便节省费用。条件： 必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。 请确定设站方案。,布点问题的数学模型： 01规划,设01为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型,游泳运动员的选拔,例：甲乙丙丁是4名游泳运动员，他们各种姿势的100m游泳成绩见下表。为组成一个410

6、0m混合泳接力队，怎样选派运动员，方能使接力队的游泳成绩最好？,解： 设i=1，2，3，4分别表示甲、乙、丙、丁；j=1，2，3，4分别表示仰泳、蛙泳、蝶泳、自由泳。并设 xij= 0，表示 i 不参加 j 1，表示 i 参加 j 据题意，此题的数学模型为：,指派问题及其数学模型(Assignment Problem) 假定有n项任务分配给n个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总效率为最高。,指派问题的数学模型： 设xij=1分配第i人去完成第j 项任务， xij=0不分配第i人去完成第j 项任务。 Min Z= cijxij xij =1 (j=1,2

7、n) xij =1 (i=1,2n) xij = 0或1 (i=1,2.n; j=1,2n) 约束条件说明第j项任务只能由1人去完成； 约束条件说明第i人只能完成1项任务。,指派问题与匈牙利法,例1 四人承担四项任务，各人完成各项任务所需的时间如下表，试确定最优的任务分配方案，使四人完成四项任务的总时间最少。,解： 设i=1，2，3，4分别表示甲、乙、丙、丁； j=1，2，3，4分别表示A、B、C、D四项任务； 并设 xij= 0，表示 i 不承担 j任务 1，表示 i 承担 j任务 据题意，此题的数学模型为：,匈牙利法求解,可行解xij的表现形式？,可行解xij写成矩阵形式，称为解矩阵。,指

8、派问题的最优解具有这样的性质： 若从系数矩阵(cij)的一行（列）各元素中分别减去一个常数 ，得到新矩阵(cij)，那么以(cij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。,指派问题求解的思想,指派问题求解的思想,利用上面这个性质 可使原系数矩阵变换为非负但含有很多0元素的新系数矩阵，而最优解保持不变。,在系数矩阵(cij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩(cij)中找出n个独立的0元素。 则令解矩阵(xij)中对应这n个独立的0元素的元素（位置）取值为1，其它元素取值为0，将其代入目标函数中得到z，它一定是最小值。这就是以(cij)为

9、系数矩阵的指派问题的最优解。,匈牙利算法的步骤,第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 （1）从系数矩阵的每行元素减去该行的最小元素； （2）再从所得系数矩阵的每列元素中减去该列的最小元素。 若某行（列）已有0元素，那就不必再减,例1的计算为,min 4 2,第二步：进行试指派，以寻求最优解。 经第一步变换后，系数矩阵中每行每列都已有了0元素，但需找出n个独立的0元素。 若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找。,第二步 试指派,寻找独

10、立0元素的步骤： 对每一行检查，若该行只有一个0元素，就给这个0元素加圈。同时把该元素所在列的其他0元素划去。 再对每一列检查，若该列只有一个0元素，就给这个0元素加圈，同时把该元素所在行的其他0元素划去。 反复进行上述两步，直到所有行、列的零元素被处理完毕。 若独立0元素的数目正好等于矩阵阶数n，那么这分配问题的最优解已得到。,0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0,例1：,0 13 7 0 6 (0) 6 9 0 5 3 2 0 1 0 0, 13 7 0 6 (0) 6 9 (0) 5 3 2 1 0 0, 13 7 0 6 (0) 6 9 (0) 5 3 2

11、1 (0) , 13 7 (0) 6 (0) 6 9 (0) 5 3 2 1 (0) ,0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0,可见有4个独立0元素,得到最优解。,即甲完成D、乙完成B、丙完成A、丁完成C，所需总时间最少。Z=28小时,练习：用匈牙利法求解如下效率矩阵的指派问题,先行后列,先列后行,指派问题求解步骤,1、使系数矩阵C各行各列都出现0元素； 2、试指派，寻找独立0元素；,例2：找独立0元素。,独立0元素有7个,独立0元素有8个,矩阵中0元素覆盖的定理： 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。,例,(0 ) 8 2 5 11 (0)

12、 5 4 2 3 (0) 0 0 11 4 5,只有3个独立零元素，覆盖所有零元素的最少直线数也是3条。,第三步：作最少的能覆盖所有0元素的直线。 对没有(0)的行，打； 在打的行中找被划去0元素，对应其所在的列打； 在打的列中找加圈的0元素，对应其所在的行打； 重复上述两步，直到得打不出为止。 对没有打行画横线，有打列画纵线，就得到覆盖所有0元素的最少直线数。,先行后列,练习：,(0) 8 2 5 11 (0) 5 4 2 3 (0) 0 0 11 4 5,上述练习（先行后列）中的覆盖所有0元素的最少直线:,例2：找独立0元素，并作能覆盖所有0元素的最少直线。,7个独立0元素,若发现所作直线

13、数不等于加圈0元素个数，则需要重新试分配，重新寻找独立0元素。,重新寻找独立0元素：,第四步：若直线数与加圈0元素个数相等，且小于n, 则需对系数矩阵进行调整，得到新的系数矩阵，方法如下： 在没有被直线覆盖的部分中找出最小元素，然后在打行各元素都减去这最小元素，而在打列中各元素都加上这最小元素，原来的0元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。转第二步 试指派 重复进行。,(0) 8 2 5 11 (0) 5 4 2 3 (0) 0 0 11 4 5,上述练习（先行后列）中的覆盖所有0元素的最少直线:,复习：指派问题求解步骤,1、使系数矩阵C各行各列都出现0元素； 2、试指派，寻找独立0元素，以寻求最优解； 3、作最少的能覆盖所有0元素的直线； 4、对系数矩阵进行调整，得到新的系数矩阵，回到第2步反复