《运筹学第2章 整数规划》由会员分享，可在线阅读，更多相关《运筹学第2章 整数规划（89页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 整数规划整数规划整数规划问题的提出依照决策变量取整要求的不同，整 数规划可分为纯整数规划、 01整 数规划、混合整数规划。整数规划模型与一般的线性规划模型整数规划模型与一般的线性规划模型 的区别仅在于：整数规划的变量要求的区别仅在于：整数规划的变量要求 部分的或全部的为整数。例如：部分的或全部的为整数。例如：纯整数规划：如果所有决策变量都要求取 整数，则称为“纯整数规划” 混合整数规划：如果仅有一部分的决策变 量要求取整数，则称为“混合型整数规划”。01整数规划：所有决策变量仅限于取 0 或 1 两个整数，这种规划问题称为“0-1规划 ”求解思路：既然整数规划是线性规划的 一种特
2、殊形式，求解只需在线性规划的 基础上，通过舍入取整求解即可。？但实际上，两者却有很大的不同，通过 舍入得到的整数解也不一定就是最优解 ，有时甚至不能保证所得到的解是整数 可行解。举例说明。例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称 为松弛问题）。用图解法求出最优解 x13/2, x2 = 10/3 且有Z = 29/6x1x233(3/2,10/3)现求整数解（最优解） ：如用“舍入取整法”可得 到4个点即(1，3) (2， 3)(1，4)(2，4)。显然， 它们都不可能是整数规划 的最优解。按整数规划约束条件，其可行解肯定在线性规划问题 的可行域内且为整数点 ，如图
3、所示。2121因此，可将集合内的整数点一一找出，其最 大目标函数的值为最优解，此法为完全枚举法 。如此例中（2，2）（3，1）点为最大值，Z=4 。整数规划问题的求解方法目前，常用的求解整数规划的方法有：分枝定界法、割平面法；隐枚举法、匈牙利法。整数规划模型应用举例排班问题（人力资源配置问题）例：邮局每天需要的职工数因业务忙闲而异，据 统计邮局一周内每天需要的人数如下表。排班 要符合每周连续工作5天，休息2天的规定。问 如何排班可使用人最少。一二三四五六日 17131519141611( (纯整数规划问题纯整数规划问题) )解：设xi为第i天开始上班的人数： Min：z=x1+x2+x3+x4
4、+x5+x6+x7 s.t. x1 +x4+x5+x6+x717x1+x2 +x5+x6+x713x1+x2+x3 +x6+x715x1+x2+x3+x4+ +x719x1+x2+x3+x4+x5 14x2+x3+x4+x5+x6 16x3+x4+x5+x6+x711xi0 （ i=1,2,7）X=(1.3, 3.3, 2, 7.3, 0, 3.3, 5)T , z=22.3X X* *=( 7, 5, 1, 8, 0, 2, 0)=( 7, 5, 1, 8, 0, 2, 0)T T, z=23 , z=23( (纯整数规划问题纯整数规划问题) )背包问题n目标：在不超过一定重量的前提下，使所
5、携 带物品的重要性系数之和最大 。n 例：登山队员需携带的物品及每一件物品 的重量和重要性系数见下表。假定允许携带 的最大重量为25千克，试确定一最优方案。数据 物品 项目食品氧气冰镐绳索帐篷照相器材通信设备重量(千克)55261224重要系数201518148410背包问题的数学模型： 01规划n解：设01变量表示携带物品i，表示不携带 物品i，则问题可写为n可通过计算每一物品的重要性系数和重量 的比值ci/ai来解决。布点问题 n共同目标：满足公共要 求，布点最少，节约投 资费用。n学校、医院、商业区、消防 队等公共设施的布点问题。n例：某市6个区，希望设 置最少消防站以便节省 费用。条件
6、：n必须保证在城区任何地方发 生火警时，消防车能在15分 钟之内赶到现场。各区之间 消防车行驶的时间见右表。n请确定设站方案。地 点一 区二 区三 区四 区五 区六 区 一 区01016282720二 区10024321710三 区16240122721四 区28321201525五 区27172715014六 区20102125140布点问题的数学模型： 01规划n设01为决策变量，当表示i地区设站，表示i 地区不设站。这样根据消防车15分钟赶到现 场的限制，可得到如下模型游泳运动员的选拔例：甲乙丙丁是4名游泳运动员，他们各种姿势的 100m游泳成绩见下表。为组成一个4100m混合 泳接力队
7、，怎样选派运动员，方能使接力队的游 泳成绩最好？运动员仰泳蛙泳蝶泳自由泳甲75.586.866.658.4乙65.866.257.052.8丙67.684.377.859.1 丁74.069.460.857.0解： 设i=1，2，3，4分别表示甲、乙、丙、丁；j=1 ，2，3，4分别表示仰泳、蛙泳、蝶泳、自由泳。 并设xij= 0，表示 i 不参加 j1，表示 i 参加 j据题意，此题的数学模型为：指派问题及其数学模型指派问题及其数学模型 ( (Assignment Problem)Assignment Problem)假定有假定有n n项任务分配给项任务分配给n n个人去完个人去完 成，并指
8、定每人完成其中一项，成，并指定每人完成其中一项， 每项只交给其中一个人去完成，每项只交给其中一个人去完成， 应如何分配使总效率为最高。应如何分配使总效率为最高。 指派问题的数学模型：指派问题的数学模型：设设x xijij=1=1分配第分配第i i人去完成第人去完成第j j 项任务，项任务， x xijij=0=0不分配第不分配第i i人去完成第人去完成第j j 项任务。项任务。Min Z=Min Z= c cijijx xijij x xijij =1=1(j=1,2(j=1,2n) n) x xijij =1=1(i=1,2(i=1,2n) n) x xijij = = 00或或1 1(i=
9、1,2n; j=1,2 (i=1,2n; j=1,2n)n)约束条件约束条件说明第说明第j j项任务只能由项任务只能由1 1人去完成；人去完成；约束条件约束条件说明第说明第i i人只能完成人只能完成1 1项任务。项任务。指派问题与匈牙利法例例1 1 四人承担四项任务，各人完四人承担四项任务，各人完 成各项任务所需的时间如下表，成各项任务所需的时间如下表， 试确定最优的任务分配方案，使试确定最优的任务分配方案，使 四人完成四项任务的总时间最少四人完成四项任务的总时间最少 。任务务 人员员ABCD甲215134乙1041415丙9141613丁78119解： 设i=1，2，3，4分别表示甲、乙、丙
10、、丁； j=1 ，2，3，4分别表示A、B、C、D四项任务；并设xij= 0，表示 i 不承担 j任务1，表示 i 承担 j任务据题意，此题的数学模型为：匈牙利法求解任务务 人员员ABCD甲215134乙1041415丙9141613丁78119可行解可行解x xij ij的表现形式？的表现形式？可行解可行解xijxij写成矩阵形式，称为解矩阵。写成矩阵形式，称为解矩阵。指派问题的最优解具有这样的性质：指派问题的最优解具有这样的性质：若从系数矩阵若从系数矩阵(c(cij ij) )的一行（列）各元的一行（列）各元 素中分别减去一个常数素中分别减去一个常数 ，得到新矩，得到新矩 阵阵(c(cij
11、 ij) )，那么以，那么以(c(c ij ij) )为系数矩阵求得为系数矩阵求得 的最优解和用原系数矩阵求得的最优的最优解和用原系数矩阵求得的最优 解相同。解相同。指派问题求解的思想指派问题求解的思想n利用上面这个性质可使原系数矩阵变换为非负但含有很多0元素 的新系数矩阵，而最优解保持不变。n在系数矩阵(cij)中，我们关心位于不同行不同 列的0元素，以下简称为独立的0元素。n若能在系数矩(cij)中找出n个独立的0元素。则令解矩阵(xij)中对应这n个独立的0元素的元 素（位置）取值为1，其它元素取值为0，将 其代入目标函数中得到z，它一定是最小值。 这就是以(cij)为系数矩阵的指派问题
12、的最优解 。匈牙利算法的步骤n第一步：使指派问题的系数矩阵经变换， 在各行各列中都出现0元素。n（1）从系数矩阵的每行元素减去该行的最 小元素；n（2）再从所得系数矩阵的每列元素中减去 该列的最小元素。n若某行（列）已有0元素，那就不必再减例1的计算为min 4 2n第二步：进行试指派，以寻求最优解。经第一步变换后，系数矩阵中每行每列都已有 了0元素，但需找出n个独立的0元素。n若能找出，就以这些独立0元素对应解矩阵(xij) 中的元素为1，其余为0，这就得到最优解。n当n较小时，可用观察法、试探法去找出n个独 立0元素。若n较大时，就必须按一定的步骤去 找。 第二步 试指派寻找独立寻找独立0
13、 0元素的步骤：元素的步骤： 对每一行检查，若该行只有一个对每一行检查，若该行只有一个0 0元素，就给这个元素，就给这个 0 0元素加圈。同时把该元素所在列的其他元素加圈。同时把该元素所在列的其他0 0元素划去元素划去 。 再对每一列检查，若该列只有一个再对每一列检查，若该列只有一个0 0元素，就给这元素，就给这 个个0 0元素加圈，同时元素加圈，同时把该元素所在行的其他把该元素所在行的其他0 0元素划元素划 去。去。反复进行上述两步，直到所有行、列的零元素被处反复进行上述两步，直到所有行、列的零元素被处 理完毕。理完毕。若独立若独立0 0元素的数目正好等于元素的数目正好等于矩阵阶数矩阵阶数n
14、 n，那么这，那么这 分配问题的最优解已得到。分配问题的最优解已得到。0 13 7 00 13 7 06 6 0 0 6 6 9 90 5 3 20 5 3 20 1 0 00 1 0 0例1：0 13 7 00 13 7 06 6 (0)(0) 6 6 9 90 05 5 3 2 3 20 0 1 1 0 0 0 0 13 7 0 13 7 06 6 (0)(0) 6 6 9 9(0)(0) 5 3 2 5 3 2 1 0 0 1 0 0 13 7 0 13 7 06 6 (0)(0) 6 9 6 9(0)(0) 5 3 2 5 3 2 1 1 (0)(0) 13 7 13 7 (0)(0)6 6 (0)(0) 6 9 6 9(0)(0) 5 3 2 5 3 2 1 1 (0)(0) 0
