资源描述
第11讲 整数规划(二) 指派问题,浙江工业大学经贸管理学院 曹柬,一、指派问题的概念,运筹学 第11讲:整数规划(二),例1(习题5-2),甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件,使总的加工时间最少?,指派问题的标准形式(以人和事为例)是:有n 个人和n 件事,已知第i 人做第j 事的付出为cij (i,j =1,2,n ),要求确定人与事之间的一一对应的指派方案,使完成这n 件事的总付出最小。,一般称C=(cij )nn为指派问题的系数矩阵。在实际问题中,cij 可表示费用、时间、距离等。,为建立标准指派问题的数学模型,引入n2 个0-1变量:,指派问题有 个可行解,n!,二、指派问题的标准形式,运筹学 第11讲:整数规划(二),指派问题标准形式的特点,模型为min型 系数矩阵C 为方阵 系数cij0,运筹学 第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),min 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,
展开阅读全文