《第11讲：整数规划(二).pptVIP

第11讲 整数规划(二) ——指派问题 浙江工业大学经贸管理学院 曹柬 一、指派问题的概念 三、匈牙利法 * * * * * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 运筹学 第11讲：整数规划(二) 例1(习题5-2) 甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？ 工件 工人 甲 乙 丙 丁 A 14 9 4 15 B 11 7 9 10 C 13 2 10 5 D 17 9 15 13 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 指派问题的标准形式(以人和事为例)是：有n 个人和n 件事，已知第i 人做第j 事的付出为cij (i,j =1,2,…,n )，要求确定人与事之间的一一对应的指派方案，使完成这n 件事的总付出最小。 一般称C=(cij )n×n为指派问题的系数矩阵。在实际问题中，cij 可表示费用、时间、距离等。 为建立标准指派问题的数学模型，引入n2 个0-1变量： 指派问题有 个可行解 n! 二、指派问题的标准形式 运筹学 第11讲：整数规划(二) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 指派问题标准形式的特点 模型为min型 系数矩阵C 为方阵 系数cij≥0 运筹学 第11讲：整数规划(二) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 运筹学 第11讲：整数规划(二) (以习题5-2为例) 甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间如表所示。问应指派何人加工何种工件，使总的加工时间最少？ 工件 工人 甲 乙 丙 丁 A 14 9 4 15 B 11 7 9 10 C 13 2 10 5 D 17 9 15 13 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 运筹学 第11讲：整数规划(二) 某商业公司计划开办5家新商店，为尽快建成营业，公司决定由5家建筑公司分别承建。已知建筑公司Ai 对新商店Bj 的建造费用报价如下表所示。问商业公司应对5家建筑公司如何分配建造任务，使得总建造费用最小？ Bj Ai A1 A2 A3 A4 A5 B1 4 7 6 6 6 B2 8 9 9 7 9 B3 7 17 12 14 12 B4 15 14 8 6 10 B5 12 10 7 10 6 例2 (P143-例12) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 四、非标准形式指派问题的求解 若为max型，可用C中最大元素分别减去C中每一元素 若人数和任务数不同，即C非方阵，可添加虚拟的人或任务，取系数为0 一个人做几项任务，可将该人化为几个人；反之亦然 某任务不能由某人做，取系数为M 运筹学 第11讲：整数规划(二) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 运筹学 第11讲：整数规划(二) 某商业公司计划开办5家新商店，公司决定由