[整数线性规划.ppt

整数规划(Integer Programming) 分枝定界法的理论基础： 对于求最大的整数规划，上界是通过松弛方法得到，作用是判断最优，下界找可行解得到，作用是剪枝。上界定不好难以得到最优解，下界定不好难以剪枝，仅仅是多计算几步。 对于不满足整数约束的变量就行分枝； 如何分枝和定界 上下界的作用 1、概述 匈牙利法是用来解决人员分配问题的一个解法。1955年，库恩（W.W.Kuhn)利用匈牙利数学家康尼格（D.Kǒnig)的一个定理构造了这个解法，故称为匈牙利法。 人员分配问题：设某单位现有n个人员A1,A2…An来完成n项工作B1,B2,……Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。 四、指派问题及匈牙利法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 令xij表示对人员Ai完成工作Bj的决策变量 表示分配Ai干工作Bj 表示不分配Ai干工作Bj 按问题要求，建立该问题的数学模型为： 这就是一般分配问题的数学模型. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 此模型也可以看成一个特殊的运输问题，如果用表上作业法得出的一个最优解又满足“xij =0,1”的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。 注：人员分配问题有各种提法。 如果完成任务的效率表现为资源的消耗，则所谓的效率最好是指消耗的资源最少，分配问题就是一个最小化问题； 如果完成任务的效率表现为生产效率的高底，则分配问题就是一个最大化问题。 所有分配问题可以建立相同的数学模型. 2、相关概念 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. a、0-1变量及其应用 如前所述,若变量只能取值0或l，则称其为0-1变量. 0-1变量作为逻辑变量，常被用来表示系统是否处于某个待定状态．或者决策时是否取某个待定方案.例如 当决策取方案 P 时 当决策不取方案 P 时 五、0-1型整数规划 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述。 一般地，设问题有有限项要素 El,E2,…En。其中每项 Ej 有两种选择 ， ,( j＝1,2,…n )，则可令 那么,向量 (x1 , x2 , … , xn)T 就描述了问题的特定状态或方案，即 若 Ej 选择 若 Ej 选择 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profi