运筹学第11讲：整数规划.ppt

《运筹学第11讲：整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11讲整数规划(二)——指派问题浙江工业大学经贸管理学院曹柬一、指派问题的概念运筹学第11讲：整数规划(二)例1(习题5-2)甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？工件工人ABCD甲14111317乙9729丙491015丁1510513指派问题的标准形式(以人和事为例)是：有n个人和n件事，已知第i人做第j事的付出为cij(i,j=1,2,…,n)，要求确定人与事之间的一一对应的指派方案，使完成这n件事的总付出最小。一般称C=(cij)n×n为指派问题的系数矩阵

2、。在实际问题中，cij可表示费用、时间、距离等。为建立标准指派问题的数学模型，引入n2个0-1变量：指派问题有个可行解n!二、指派问题的标准形式运筹学第11讲：整数规划(二)指派问题标准形式的特点模型为min型系数矩阵C为方阵系数cij≥0运筹学第11讲：整数规划(二)三、匈牙利法(以习题5-2为例)甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？工件工人ABCD甲14111317乙9729丙491015丁1510513运筹学第11讲：整数规划(二)某商业公司计划开办5家新商

3、店，为尽快建成营业，公司决定由5家建筑公司分别承建。已知建筑公司Ai对新商店Bj的建造费用报价如下表所示。问商业公司应对5家建筑公司如何分配建造任务，使得总建造费用最小？BjAiB1B2B3B4B5A14871512A279171410A3691287A46714610A56912106例2运筹学第11讲：整数规划(二)四、非标准形式指派问题的求解若为max型，可用C中最大元素分别减去C中每一元素若人数和任务数不同，即C非方阵，可添加虚拟的人或任务，取系数为0一个人做几项任务，可将该人化为几个人；反之亦然某任务不能由某人做，取系数为M

4、运筹学第11讲：整数规划(二)某商业公司计划开办5家新商店，公司决定由3家建筑公司分别承建，允许每家建筑公司承建一家或二家商店。已知建筑公司Ai对新商店Bj的建造费用报价如下表所示。求使总费用最小的指派方案。BjAiB1B2B3B4B5A14871512A279171410A3691287例3运筹学第11讲：整数规划(二)采用匈牙利法求得：A1承建B1和B3，A2承建B2，A3承建B4和B5，总造价为35万元。作业：习题5-3，习题5-4，5.8思考：案例7例4甲乙丙丁A32-21B2-20/C/-110表中的元素表示4人完成3项任务

5、的利润，“/”表示不胜任。由于精力所限，每人只能承担一项任务，求使总利润最大的指派方案。运筹学第11讲：整数规划(二)便民超市准备在城市西北郊新建的居民小区中开设若干连锁店。为方便购物，规划任一居民小区至其中一个连锁店的距离不超过800m。下表给出了新建的居民小区及离该居民小区半径800m内的各个小区，问该超市最少应在上述小区中建多少个连锁店及建于哪些小区内。例5(习题5-7)小区代号该小区800m半径内的各小区AACEGHIBBHICACGHIDDJEAEGFFJKGACEGHABCHIIABCHIJDFJKLKFJKLLJKLmi

6、nxa+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>=1xf+xj+xk+xl>=1xj+xk+xl>=1endint12附：Lindo语句求得：xG＝xH＝xJ＝1，其余xj＝0