运筹学第2章整数规划

《运筹学第2章整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、x2+x3+x4+x5≥14x2+x3+x4+x5+x6≥16x3+x4+x5+x6+x7≥11xi≥0（i=1,2,…,7）X=(1.3,3.3,2,7.3,0,3.3,5)T,z=22.3X*=(7,5,1,8,0,2,0)T,z=23(纯整数规划问题)背包问题目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大。例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。数据物品项目食品氧气冰镐绳索帐篷照相器材通信设备重量(千克)55261224重要系数201518148410背包问题的数学模型：0－1规划解：

5、设01变量表示携带物品i，表示不携带物品i，则问题可写为可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。布点问题共同目标：满足公共要求，布点最少，节约投资费用。学校、医院、商业区、消防队等公共设施的布点问题。例：某市6个区，希望设置最少消防站以便节省费用。条件：必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。请确定设站方案。地点一区二区三区四区五区六区一区01016282720二区10024321710三区16240122721四区28321201525五区27172715014六区20102125140布点问题的数学

6、模型：0－1规划设01为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型游泳运动员的选拔例：甲乙丙丁是4名游泳运动员，他们各种姿势的100m游泳成绩见下表。为组成一个4×100m混合泳接力队，怎样选派运动员，方能使接力队的游泳成绩最好？运动员仰泳蛙泳蝶泳自由泳甲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

7、参加j据题意，此题的数学模型为：指派问题及其数学模型(AssignmentProblem)假定有n项任务分配给n个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总效率为最高。指派问题的数学模型：设xij=1分配第i人去完成第j项任务，xij=0不分配第i人去完成第j项任务。MinZ=cijxijxij=1(j=1,2……n)①xij=1(i=1,2……n)②xij=0或1(i=1,2…..n;j=1,2……n)约束条件①说明第j项任