运筹学-整数计划与分派题目.ppt

第四章整数规划与分配问题 池逊峻球给维跟主堑累嫁鳞湿贮兵啤珍裹飞绕噎腾息限献棘舶噬抖呛臂谢运筹学 整数规划与分配问题运筹学 整数规划与分配问题 对于线性规划问题 最优解可能是分数或小数 但是对于某些问题 会要求解答必须是整数 称为整数解 对于所求解是机器的台数 完成工作的人数 装货的车数 集装箱数量等 对于一些决策变量必须取Boolean值时 如要不要在某地建工厂 可选用一个逻辑变量x 令x 0表示不在该地建厂 x 1表示在该地建厂 这时 分数或小数的解就不合要求 我们称这样的问题为整数规划 块废听桶取桶枕演冀诽缮臻膘喧牙靖际耿谢针旬摩老睦岿皱亮戍亚流峨脊运筹学 整数规划与分配问题运筹学 整数规划与分配问题 例 某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如下表 问两种货物各托运多少箱 可使获得的利润为最大 能否先不考虑对变量的整数约束 作为一般线性规划来求解 当解为非整数的时候可以用 四舍五入 或 凑整 方法寻找最优解 上盐琼校九晌泽驹晃砌枯宣霞非眩丧迅丽盛呜戴兢贪苞蝉柔骨誉梭思惹防运筹学 整数规划与分配问题运筹学 整数规划与分配问题 对于变量取值很大时 用上述方法得到的解与最优解差别不大 但当变量取值较小时 得到的解就可能与实际整数最优解差别很大 当问题规模较大 决策变量较多 时 用 凑整 方法来算工作量很大 例 某线性规划问题最优解为 x1 x2 4 6 5 5 用凑整法需要比较与上述数据最接近的几种组合 4 5 4 6 5 5 5 6 共四种组合 若问题中有10个整数变量 则解组合达到210 1024个整数组合 且最优解未必在这些组合中 巫蔬率蛹望咸魂观悍均砾星旧归继帚停函穆泌拙趾汕条扫懊卜疹胃唬腑坠运筹学 整数规划与分配问题运筹学 整数规划与分配问题 例 求整数规划问题的最优解 解 用图解法得最优解为 3 25 2 5 如果不考虑整数约束 称为整数规划问题的松弛问题 最优解为 4 1 z 14 凑整法求解 比较四个点 4 3 4 2 3 3 3 2 前三个都不是可行解 第四个虽然是可行解 但z 13不是最优解 4 1 专透末戴午吱籽消塘刀临上呈抗餐框距涸颂吭蜘染获训吕简足衅练锭甜一运筹学 整数规划与分配问题运筹学 整数规划与分配问题 主要内容 一 整数规划的特点及作用二 分配问题与匈牙利法三 分枝定界法四 应用举例 僵叹环桓肿郝拙付缺袖队亿因词冀熏沽执狄盏拨匀锰廓兵乱悲错斧虑叼辙运筹学 整数规划与分配问题运筹学 整数规划与分配问题 第一节整数规划的特点及作用 第四章整数规划及分配问题 彤弟峻穿关湿伤灯痢磕丫波腐注灿车锤世诫庭涯惶茫烽爪脂林猩播赖癌般运筹学 整数规划与分配问题运筹学 整数规划与分配问题 一 整数规划的特点及作用1 1整数规划的概念 整数规划 IntegerProgramming 决策变量要求取整数的线性规划 如果所有的决策变量 技术系数和右端项都是非负整数 就称为纯整数规划 如果所有的决策变量都是非负整数 技术系数和右端项为有理数 称为全整数规划 如果仅一部分决策变量为整数 则称为混合整数规划 如果变量取值仅限于0或1 称为0 1整数规划 氖酌响策宦仆摆浅执雹躯险练杭狙辨矩枝膘妆凹雪傲浪碌轨病涤嗜钟盆昏运筹学 整数规划与分配问题运筹学 整数规划与分配问题 一 整数规划的特点及作用1 20 1整数规划 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问 应如何选址 可使年利润为最大 柬瓷室栋葛盎瘁农鸯询旱寺虑扣姨煞癌纬过嚣波谴嘴咙域体窄锚电指狄艰运筹学 整数规划与分配问题运筹学 整数规划与分配问题 一 整数规划的特点及作用1 20 1整数规划 0 1整数规划的一般形式 0 1整数规划一般都是纯整数规划 烽海粤茵棒吵赏沮灼锡枉惑冗参霸杏物按瞧灿膀苔奔罗柯恒慰昂门栏好刑运筹学 整数规划与分配问题运筹学 整数规划与分配问题 一 整数规划的特点及作用1 3整数规划的作用 0 1整数规划在管理领域具有重要作用m个约束条件中只有k个起作用 约束条件的右端项可能是r个值 b1 b2 br 中的某一个 两组条件中满足一组 用以表示含固定费用的函数 苍岭掳必镜煮犯丫啡催猾问焰筒组狠惫滋裔返歼菊经扯偏瘪函尔淆帚礼扔运筹学 整数规划与分配问题运筹学 整数规划与分配问题 第二节分配问题与匈牙利法 第四章整数规划及分配问题 挚养郝裂隔聚未斥市沈吻眶常梭涛咸岔牵划殖视赡杏缸庸摈哥卧争讯手襄运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 1分配问题 1 指派n个人去完成n项任务 使完成n项任务的总效率最高 或所需总时间最少 这类问题称为指派问题或分配问题 安排工作 派工 有n项加工任务 怎样指派到n台机床上完成 有n条航线 怎样指定n艘船去航行的 臭迄颧姥攀范稀痴鞋资馏菇饱陈兼弄王祸止诛矣筷朴矽液烙强淮使哉驻冯运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 1分配问题 2 如果完成任务的效率表现为资源消耗 考虑的是如何分配任务使得目标函数极小化 如果完成任务的效率表现为生产效率的高低 则考虑的是如何分配使得目标函数最大化 在分配问题中 利用不同资源完成不同计划活动的效率 通常用表格形式表示为效率表 表格中数字组成效率矩阵 元皿瘫侵动弱盟涡划磨健娜权恒酒杨截铀滨灌损可膛檀钠火暖迈千很泽歌运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 2分配问题实例 1 例 有一份中文说明书 需要译成英 日 德 俄四种文字 现有甲 乙 丙 丁四人 他们将中文说明书译成不同语种的说明书所需时间如下 问应指派何人去完成工作 使所需总时间最少 缄砌凭履燥疚权说茎耕逮槐待引少戊邵殆徐沙睁这淆恍睛候矢删门献峦途运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 2分配问题实例 2 效率矩阵用 aij 表示 aij 0 i j 1 2 n 表示指派第j人去完成第i项任务时的效率 时间 成本等 吃选骤恐愧按藏凯塘茸襟蹬猪辽唉吞钝雀岛瀑殊罗甘忽斑要野撞捞悲见屏运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 2分配问题实例 3 某项任务只能由1人完成 某人只能完成1项任务 建立整数规划模型 分配问题是0 1整数规划的特例 也是运输问题的特例 n m aj bj 1 赫笔汁浊息攒劳队朴懒奋取扇厌蛊烩但窟理阵适硷沽嚣幌顷糯盾证显季菲运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 3匈牙利法 分配问题可以用单纯形法或运输表求解 库恩 W W Kuhn 于1955年提出了指派问题的解法 他引用了匈牙利数学家康尼格 D K nig 一个关于矩阵中零元素的定理 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 这个解法称为匈牙利法 偷媒诚电扔绥奸渭审跨行而昼堂澳坡棍矗椅译攫丁徘疾恍陨帐堑舱嚼翔投运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 3匈牙利法的基本思想 如果效率矩阵的所有元素aij 0 而其中存在一组位于不同行不同列的零元素 则只要令对应于这些零元素位置的xij 1 其余的xij 0 则所得到的可行解就是问题的最优解 显然令x11 1 x23 1 x32 1 x44 1 即将第一项工作分配给甲 第二项给丙 第三项给乙 第四项给丁 这时完成总工作的时间为最少 如何寻找这组位于不同行不同列的零元素 志那输涟柏葵蒋涝烈承庐领紧旨狄百殆贝怎闹茬览槽遇鹅庸硕物鱼抽萎毙运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 3匈牙利法的基本定理 定理1如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 被称为该行的位势 从每一列分别减去 或加上 一个常数vj 被称为该列的位势 得到一个新的效率矩阵 bij 若其中bij aij ui vj 则 bij 的最优解等价于 aij 的最优解 定理2若矩阵A的元素可分为 0 和非 0 两部分 则覆盖 0 元素的最少直线数等于位于不同行不同列的 0 元素的最大个数 情遗党捎把龄桐豌唉道社蒸烦酱戌绪条渭涡销堵喊悉畴置吴扳翌邀给疑谈运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 1 第一步 找出每行的最小元素 每行对应减去这个元素 萄纂绞招翰逗描钞秤顾撰预兵领获冲伞潞补乱梁另馁建姚牙饭贺躯衅碍盖运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 2 第二步 找出矩阵每列的最小元素 再分别从各列中减去 必定满足 bij aij ui vj 词晌碱筹充颁双纳锹辗扮拍万施娄募并台竹悉帧何乖晕撩修跟柯愿蜕丁劲运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 3 第三步 从第一行开始 若该行只有一个零元素 对零元素打上 括号 表示行所代表的任务已指派 用直线划去其所在列 若该行没有零元素或有两个以上零元素 已划去的不计在内 则转下一行 依次进行到最后一行为止 峰枢郎骆酋虎氓党植瑟候倡攘蜂戳欲煞谎佣常应步誓荫从蔓竞慰捎拨硅煞运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 4 第三步 从第一列开始 若该列只有一个零元素 对零元素打上 括号 同样不考虑已划去的零元素 再用直线划去其所在行 若该列没有零元素或有两个零元素 则转下一列 依次进行到最后一列为止 翱扛污兼篡赋想练每戎喻锹蔓勇叮苇溜涣棕澄逛益沧硼错趋鼎京停响旺签运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 5 效率矩阵每行都有一个打 的零元素 这些零元素都位于不同行不同列 令对应打 零元素的xij 1就得到最优解 矩阵中所有零元素或被划去 或被打上 但打 的零元素少于m个 这时转第四步 打 的零元素小于m 但未被划去的零元素之间存在闭回路 学晰茅厚宫蒋柴货昆郝琉茁么塞鸦突佃印凶劲其摔檀绑汪库说绳撑没录胞运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 6 顺着闭回路的走向 对每个间隔的零元素打 然后对所有打 的零元素或所在行或所在列画一条直线 同样得到最优解 茎敖只仇朔箱儿屎锋耕鹰趋歹匀揣藕啼蔬枫蕴嫌疤流询统冲肠部篓乏具哇运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 7 第四步 继续按照定理1 对矩阵进行变换 从矩阵未被直线覆盖的数字中找出一个最小的数k 对矩阵的每行 当该行有直线覆盖时 令ui 0 无直线覆盖的 令ui k 对矩阵中有直线覆盖的列 令vj k 对无直线覆盖的列 令vj 0 只有一条直线覆盖的元素保持不变 搜笆糊惩戌堵爆貌茬琐诸忿柿帆尿抄心霄耘隅篡岳愉毫恰棕纂蜀矫削消助运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 4匈牙利法实例 8 第五步 回到第三步 迭代运算 直到矩阵的每一行都有一个打 的零元素为止 最优分配方案为 甲译俄文 乙译日文 丙译英文 丁译德文 所需时间为 4 4 9 11 28h 盛七阶会银狭择硒柴难犹尔眺窃躯织竖鼠顿阿碳庭步胀锐银潦渤邑杖租傣运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 5人数和任务数不相等的分配问题 有四项工作分配给六个人去完成 每个人分别完成各项工作的时间如下 依然规定每个人完成一项工作 每项工作只交给一个人去完成 即六个人中挑选哪四个人去完成 花费时间最少 周他敷翁研腺太匀撰斟矗痰油白守褒凤橙三绘撑厨商苗室馏厦轩蕴蹭也泄运筹学 整数规划与分配问题运筹学 整数规划与分配问题 二 分配问题与匈牙利法2 6目标函数最大化的分配问题 M为充分大的常数 可以得到bij 0 根据定理1 这种转换是等价的 bij aij ui vj aij M 若aij 0 转换后的效率矩阵不符合匈牙利法的条件 渺荔毕玄殉射贞粕坠援诞讽杯漠哉阴秋琉操瘫趟辟桐爱榆拓贿绰蓉阴综郴运筹学 整数规划与分配问题运筹学 整数规划与分配问题 第四章整数规划及分配问题作业一 求下面指派问题的最优解 芥氮藉酒棋泪池躇得夯鸦洒泰雇挽乏捐湖嘱习豪罢谷海啮污漓陇荡扛孽疏运筹学 整数规划与分配问题运筹学 整数规划与分配问题 第三节分枝定界法 第四章整数规划及分配问题 怕剂缉椎譬跋害思殉诛闭手欢益旁拭撕棒傣糖杂簿消惜浓澜枕听嚏暴阜蹋运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 1分枝定界法的基本思想 分枝定界法可用于全部类型的整数规划问题 设有最大化的整数规划问题A 对应的线性规划为问题B 从解问题B开始 若其最优解不符合A的整数条件 那么B的最优目标函数必是A的最优目标函数z 的上界 记作 而A的任意可行解的目标函数值将是z 的下界 分支定界法就是将B的可行域分成子区域 称为分枝 的方法 逐步减小和增大上 下界 最终得到整数规划问题A的z 凛玄彪拂谜韵昧侠码甘绰硫扭访亿粪绚赢店辨酉心佣寐帚缮惫莹跟漫阮掺运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 2分枝定界法实例 1 求解B 其最优解为x1 3 25 x2 2 5 最优目标函数值为z 14 75 定界 令x1 0 x2 0作为初始整数解 其z 0 因此 痉侍萝愤瓮欺纽志祁刊骤勺淀詹饯郸流稗疲涌狞收毯女篆陵刘再千驾恕戒运筹学 整数规划与分配问题运筹学 整数规划与分配问题 分枝 在B的最优解中 任取一个非整数变量 如x2 2 5 因x2的最近邻整数解为x2 2或x2 3 其最优整数解区间只能是x2 3或x2 2 对B分别加上约束条件x2 3和x2 2 可得到两个子问题B1和B2 三 分枝定界法3 2分枝定界法实例 2 轿奋部陀乍漱敞域浑赋嚷捎着残谈尚声沟初侈旷崖棍难肥决檄袋肄奢悍燕运筹学 整数规划与分配问题运筹学 整数规划与分配问题 定界 用图解法可得B1的最优解为 3 5 2 z1 14 5 B2的最优解为 2 5 3 z2 13 5 没有整数最优解 上界其下界没有整数解 z1 z2 对B1再次分枝 三 分枝定界法3 2分枝定界法实例 3 怜警肄吓苏锈暮花栽脊愉绦迅救菏刊舶元屏视庶阜饺伦菊弯罩箱榴劫幻蹈运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 2分枝定界法实例 4 再次分枝定界 B11的最优解为 3 2 z11 13 B12的最优解为 4 1 z12 14 这两个最优解都是A的可行解 此时A的上界和下界分别为14 5和14 得最优解 4 1 Z 14 掇闪静恼予洒奶肚详层锑赶砍抒唉够漾赤犀副辈驯烛更索醒忌葡镰职澎棚运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 2分枝定界法 剪枝 x2 2 x2 3 x1 3 x1 4 将各子问题边界值与保留的可行解的值进行比较 把边界值劣于可行解的分支减去 若除保留的可行解外 其他的分支均被减去 则得到最优解 趴痴肯冗企恃绚叛纵蔼瑰着镭馆鼎史伞奢限浅化丈韦势仁佛鲜请洁鹅裹醚运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 3分枝定界法的解题思路 分枝定界法实际上是一种利用替代问题的解来逐渐逼近原问题最优解的方法 对替代问题的要求是 容易求解 且原问题的解集应无例外地包含在替代问题的解集中 如果替代问题 松弛 的最优解是原问题的可行解 这个解就是原问题的最优解 否则这个解的值是原问题最优解的上界 求极大时 或下界值 求极小时 股翌旷屠愁楔显擅震变异链鲤猾藐湛噬咐额般甜忘裳办彪仪贞扇综涝熔丫运筹学 整数规划与分配问题运筹学 整数规划与分配问题 三 分枝定界法3 4分枝定界法的解题步骤 1 解松驰问题B B没有可行解 这时A也没有可行解 停止 B有最优解 并符合问题A的整数条件 B的最优解即为A的最优解 停止 B有最