《运筹学第11讲：整数规划(二)》由会员分享，可在线阅读，更多相关《运筹学第11讲：整数规划(二)（12页珍藏版）》请在金锄头文库上搜索。
1、第11讲 整数规划(二)指派问题浙江工业大学经贸管理学院 曹柬一、指派问题的概念一、指派问题的概念运筹学 第11讲：整数规划(二)例例1 1( (习题习题5-2)5-2)甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？ 工件 工人ABCD甲14111317乙9729丙491015丁1510513指派问题的标准形式(以人和事为例)是：有n 个人和n 件事，已知第i 人做第j 事的付出为cij (i,j =1,2,n )，要求确定人与事之间的一一对应的指派方案，使完成这n 件事的总付出最小。 一般称C=(cij )nn为指派问题的系数矩阵
2、。在实际问题中，cij 可表示费用、时间、距离等。 为建立标准指派问题的数学模型，引入n2 个0-1变量： 指派问题有 个可行解n!二、指派问题的标准形式二、指派问题的标准形式运筹学 第11讲：整数规划(二)指派问题标准形式的特点指派问题标准形式的特点M 模型为min型M 系数矩阵C 为方阵M 系数cij0运筹学 第11讲：整数规划(二)三、匈牙利法三、匈牙利法( (以习题以习题5-25-2为例为例) )甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？ 工件 工人ABCD甲14111317乙9729丙491015丁1510513运筹学
3、 第11讲：整数规划(二)某商业公司计划开办5家新商店，为尽快建成营业，公司决定由5家建筑公司分别承建。已知建筑公司Ai 对新商店Bj 的建造费用报价如下表所示。问商业公司应对5家建筑公司如何分配建造任务，使得总建造费用最小？ BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例例2 2运筹学 第11讲：整数规划(二)四、非标准形式指派问题的求解四、非标准形式指派问题的求解h 若为max型，可用C中最大元素分别减去C中每一元素h 若人数和任务数不同，即C非方阵，可添加虚拟的人或任务 ，取系数为0h 一个人做几项任务，可将该人化
4、为几个人；反之亦然h 某任务不能由某人做，取系数为M运筹学 第11讲：整数规划(二)某商业公司计划开办5家新商店，公司决定由3家建筑公司分别承建，允许每家建筑公司承建一家或二家商店。已知建筑公司Ai 对新商店Bj 的建造费用报价如下表所示。求使总费用最小的指派方案。 BjAiB1B2B3B4B5A14871512A279171410A3691287例例3 3运筹学 第11讲：整数规划(二)采用匈牙利法求得：A1承建B1和B3，A2承建B2，A3承建B4和B5，总造价为35万元。作业：习题作业：习题5-35-3，习题，习题5-45-4，5.85.8思考：案例思考：案例7 7例4甲乙丙丁A32-2
5、1B2-20/C/-110表中的元素表示4人完成3项任务的利润，“/”表示不胜任 。由于精力所限，每人只能承担一项任务，求使总利润最 大的指派方案。运筹学 第11讲：整数规划(二)u 便民超市准备在城市西北郊新建的居民小区中开设若干连锁店。为方便购物，规划任一居民小区至其中一个连锁店的距离不超过800m。下表给出了新建的居民小区及离该居民小区半径800m内的各个小区，问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内。例例5 5 ( (习题习题5-7)5-7)小区代号该该小区800m半径内的各小区 AA C E G H IBB H ICA C G H IDD JEA E GFF J KGA C E GHA B C H IIA B C H IJD F J K LKF J K LLJ K Lmin xa+xb+xc+xd+xe+xf+xg+xh+xi+xj+xk+xl st xa+xc+xe+xg+xh+xi=1 xb+xg+xi=1 xa+xc+xg+xh+xi=1 xd+xj=1 xa+xe+xg=1 xf+xg+xk=1 xa+xc+xe+xg=1 xa+xb+xc+xh+xi=1 xd+xf+xj+xk+xl=1 xf+xj+xk+xl=1 xj+xk+xl=1 end int 12附：Lindo语句求得：xGxHxJ1， 其余xj0
