运筹学第11讲：整数规划.ppt_第1页
运筹学第11讲：整数规划.ppt_第2页
运筹学第11讲：整数规划.ppt_第3页
运筹学第11讲：整数规划.ppt_第4页
运筹学第11讲：整数规划.ppt_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第11讲整数规划 二 指派问题 浙江工业大学经贸管理学院曹柬 一 指派问题的概念 运筹学第11讲 整数规划 二 例1 习题5 2 甲 乙 丙 丁四人加工A B C D四种工件所需时间如表所示 问应指派何人加工何种工件 使总的加工时间最少 指派问题的标准形式 以人和事为例 是 有n个人和n件事 已知第i人做第j事的付出为cij i j 1 2 n 要求确定人与事之间的一一对应的指派方案 使完成这n件事的总付出最小 一般称C cij n n为指派问题的系数矩阵 在实际问题中 cij可表示费用 时间 距离等 为建立标准指派问题的数学模型 引入n2个0 1变量 指派问题有个可行解 n 二 指派问题的标准形式 运筹学第11讲 整数规划 二 指派问题标准形式的特点 模型为min型系数矩阵C为方阵系数cij 0 运筹学第11讲 整数规划 二 三 匈牙利法 以习题5 2为例 甲 乙 丙 丁四人加工A B C D四种工件所需时间如表所示 问应指派何人加工何种工件 使总的加工时间最少 运筹学第11讲 整数规划 二 某商业公司计划开办5家新商店 为尽快建成营业 公司决定由5家建筑公司分别承建 已知建筑公司Ai对新商店Bj的建造费用报价如下表所示 问商业公司应对5家建筑公司如何分配建造任务 使得总建造费用最小 例2 运筹学第11讲 整数规划 二 四 非标准形式指派问题的求解 若为max型 可用C中最大元素分别减去C中每一元素若人数和任务数不同 即C非方阵 可添加虚拟的人或任务 取系数为0一个人做几项任务 可将该人化为几个人 反之亦然某任务不能由某人做 取系数为M 运筹学第11讲 整数规划 二 某商业公司计划开办5家新商店 公司决定由3家建筑公司分别承建 允许每家建筑公司承建一家或二家商店 已知建筑公司Ai对新商店Bj的建造费用报价如下表所示 求使总费用最小的指派方案 例3 运筹学第11讲 整数规划 二 采用匈牙利法求得 A1承建B1和B3 A2承建B2 A3承建B4和B5 总造价为35万元 作业 习题5 3 习题5 4 5 8 思考 案例7 例4 表中的元素表示4人完成3项任务的利润 表示不胜任 由于精力所限 每人只能承担一项任务 求使总利润最大的指派方案 运筹学第11讲 整数规划 二 便民超市准备在城市西北郊新建的居民小区中开设若干连锁店 为方便购物 规划任一居民小区至其中一个连锁店的距离不超过800m 下表给出了新建的居民小区及离该居民小区半径800m内的各个小区 问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内 例5 习题5 7 minxa xb xc xd xe xf xg xh xi xj xk xlstxa xc xe xg xh xi 1xb xg xi 1xa xc xg xh xi 1xd xj 1xa xe xg 1xf xg xk 1xa xc xe xg 1xa xb xc xh xi 1xd xf xj xk xl
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论