第4章整数规划课件.ppt

整数规划问题的提出 整数规划模型应用举例 排班问题（人力资源配置问题） 例：邮局每天需要的职工数因业务忙闲而异，据统计邮局一周内每天需要的人数如下表。排班要符合每周连续工作5天，休息2天的规定。问如何排班可使用人最少。 解：设xi为第i天开始上班的人数： Min：z=x1+x2+x3+x4+x5+x6+x7 s.t. x1 +x4+x5+x6+x7≥17 x1+x2 +x5+x6+x7≥13 x1+x2+x3 +x6+x7≥15 x1+x2+x3+x4+ +x7≥19 x1+x2+x3+x4+x5 ≥14 x2+x3+x4+x5+x6 ≥16 x3+x4+x5+x6+x7≥11 xi≥0 （ i=1,2,…,7） X=(1.3, 3.3, 2, 7.3, 0, 3.3, 5)T , z=22.3 投资问题 5个投资项目；600万元资金，投资受到约束： (1) 项目1、2和3至少一项被选中； (2) 项目3和4只能选一项； (3) 项目5选中的前提是1必须被选中。 问如何投资才能使收益最大？ 投资问题的数学模型：0－1规划 设0?1变量为决策变量，即xi=1表示项目i被选中，xi=0表示项目i被淘汰，则模型可表示为 背包问题 目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大 。 例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。 背包问题的数学模型： 0－1规划 解：设0?1变量表示携带物品i，表示不携带物品i，则问题可写为 可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。 布点问题 共同目标：满足公共要求，布点最少，节约投资费用。 学校、医院、商业区、消防队等公共设施的布点问题。 例：某市6个区，希望设置最少消防站以便节省费用。条件： 必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。各区之间消防车行驶的时间见右表。 请确定设站方案。 布点问题的数学模型： 0－1规划 设0?1为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型 游泳运动员的选拔 例：甲乙丙丁是4名游泳运动员，他们各种姿势的100m游泳成绩见下表。为组成一个4×100m混合泳接力队，怎样选派运动员，方能使接力队的游泳成绩最好？ 解： 设i=1，2，3，4分别表示甲、乙、丙、丁；j=1，2，3，4分别表示仰泳、蛙泳、蝶泳、自由泳。并设 xij= 0，表示 i 不参加 j 1，表示 i 参加 j 据题意，此题的数学模型为： 整数规划问题的求解方法 求解整数规划的分枝定界法 思路：分枝和定界两部分： 分枝：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解；（由于非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不妨碍整数规划问题的优化） 定界：松弛问题最优解——上界；IP问题的任意可行解——下界，不断减小上界和增加上界，最终的最优解。（IP问题的最优解不优于LP问题的最优解） 求解0-1整数规划的隐枚举法 隐枚举法步骤： 指派问题与匈牙利法 解： 设i=1，2，3，4分别表示甲、乙、丙、丁； j=1，2，3，4分别表示英语、日语、德语、俄语； 并设 xij= 0，表示 i 不翻译 j 1，表示 i 翻译 j 据题意，此题的数学模型为： 解矩阵(xij)中各行各列的元素之和都是1。但是，这不是最优。 指派问题求解的思想 利用上面这个性质 可使原系数矩阵变换为非负但含有很多0元素的新系数矩阵，而最优解保持不变。 在系数矩阵(cij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩(cij)中找出n个独立的0元素。 则令解矩阵(xij)中对应这n个独立的0元素的元素（位置）取值为1，其它元素取值为0，将其代入目标函数中得到z，它一定是最小值。这就是以(cij)为系数矩阵的指派问题的最优解。也就是原问题的最优解。 匈牙利算法的步骤 第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 （1）从系数矩阵的每行元素减去该行的最小元素； （2）再从所得系数矩阵的每列元素中减去该列