运筹学-整数规划指派问题.ppt

《运筹学-整数规划指派问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0－1变量：在整数规划问题中，有一类特殊的整数规划，不仅要求解为整数，而且要求只能取得0和1两个整数值，这类整数规划称之为0－1型整数规划，该类解称为0－1变量。第三节0－1型整数规划一指派问题由n项不同的工作或任务，需要n个人去完成（每人只能完成一项工作）。由于每人的知识、能力、经验等不同，故各人完成不同任务所需的时间（或其它资源）不同。问应指派哪个人完成何项工作所消耗的总资源最少？指派问题的数学模型引进0-1变量表示安排第i个人完成第j项工作表示不安排第i个人完成第j项工作决策变量矩阵可表示为：用表示第i个人完成第j项工作所需的资源数，称之为效率系数（或价值系数

2、）。表示为则指派问题的数学模型为或1注：指派问题是一种特殊的LP问题，是一种特殊的运输问题。目前认为最简洁的方法—匈牙利法。例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造报价（万元）为，商业公司应当对5家建筑公司怎样分配建筑任务，才能使总的建筑费用最少？这是一个标准的指派问题。若设0-1变量当承建时当不承建时则问题的数学模型为或1如何分派工作?-4-6-7-6-7从而导出匈牙利解法的思想：1955年,由库恩（W.W.Kuhn）根据匈牙利数学家狄·考尼格（d.konig)关于矩阵中独立零元素的定理发明的

3、。匈牙利法的基本原理：定理1将效率矩阵的某一行（或某一列）的各个元素都减去同一个常数t(t可正可负），得到新的矩阵，则以新矩阵为效率矩阵的指派问题与原指派问题的最优解相同。但其最优值比原最优值减少t。解：设效率矩阵C为二匈牙利解法记新指派问题的目标函数为，注意到所以原式因此有推论若将指派问题的效率矩阵每一行及每一列分别减去各行各列的最小元素，则得到的新的指派问题与原指派问题有相同的最优解。注：当cij=0时，从第i行看，它表示第i人去干第j项工作效率（相对）最好，而从第j列来看，它表示第j项工作让第i人来干效率（相对）最高。问题是：能否找到位于不同行、不同列的n个0

4、元素？定义在效率矩阵C中，有一组处于不同行、不同列的零元素，称为独立零元素组，此时其中每个元素称为独立零元素。例已知则是一个独立零元素组，分别称为独立零元素。也是一个独立零元素组。不是一个独立零元素组。定理效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。本定理由匈牙利数学家狄·考尼格证明的。例已知矩阵例现有一个4×4的指派问题，其效率矩阵为：求解该指派问题。步骤1：变换系数矩阵，使得每行及每列至少产生一个零元素。-2-4-9-7-4-2步骤2：用圈0法确定中的独立0元素。若独立零元素个素有n个，则已得最优解。若独立零元素的个数

5、余全为0。在只有一个0元素的行（或列）加圈，表示此人只能做该事（或此事只能由该人来做），每圈一个“0”，同时把位于同列同行的其他零元素划去。表示此时已不能再由他人来做（或此人已不能做其它事）。如此反复，直到矩阵中所有零元素都被圈去或划去为至。在遇到所有行和列中，零元素都不止一个时，可任选其中一个加圈，然后划去同行、同列其他未被标记的零元素。例步骤3：若矩阵所有零元素都被标记的，但圈零的个数m

6、4<5.⑴对没有圈0的行打“✓”。⑵在已打“✓”的行中，对零元素所在的列打“✓”。✓✓⑶在已打“✓”的列中，对圈0元素所在的行打“✓”。✓✓✓✓⑷重复⑵和⑶，直到再也找不到可以打“✓”的行或列为止⑸对没有打“✓”的行画一横线，对已打“✓”的列画一纵线，即得覆盖当前0元素的最少直线数目的集合。✓✓✓⒋继续变换系数矩阵，以增加0元素。在未被直线覆盖的元素中找出一个最小的元素。对未被直✓✓✓✓✓✓线覆盖的元素所在的行（或列）中各元素都减去这一元素。这样，在未被直线覆盖的元素中势必会出现0元素，但同时却又使已覆盖的元素中出现负元素。为了消除负元素，只要对它们所在的列（或行）

7、中各元素都加上这一最小元素。返回⑵。-1-1+1中已有5个独立0元素，故可确定指派问题的最优方案。其余全为0。也就是说，最优指派方案是：让A1承建B3,A2承建B2,让A3承建B1,让A4承建B4,让A5承建B5.这样安排能使总的建造费用最少，总的建造费用为7+9+6+6+6=34（万元）。三非标准形式的指派问题处理方法：化成标准形式，再按匈牙利方法求解。⒈目标函数最大化指派问题例有4名工人A1,A2,A3,A4分别操作4台机床B1,B2,B3,B4。每人操作每台机床的单位产量见下表。求产值最大的指派方案。机床工人B1B2B3B4A1A2A3A410987345