摘要:本文首先介绍了整数线性规划的基本概念,以及Gomory割平面法、分枝定界法、隐枚举法以及匈牙利法的基本思想及解题步骤。然后将这几种方法应用于投资问题、汽车厂生产问题、指派问题。割平面法适用于大部分线性规划问题,计算复杂,应用广泛;分枝定界法适用于纯整数规划问题,计算较为复杂。隐枚举法适用于0-1规划问题,思路简单,计算过程较为复杂;匈牙利法适用于指派问题,但其思路简单,计算简便。85001

毕业论文关键词:整数线性规划;隐枚举法;分枝定界法;Gomory割平面法;匈牙利法

The Solution Of Integer Linear Programming Problem

Abstract:This paper first introduces the basic concepts of integer linear programming, and the basic ideas of Gomory cut plane method, branch and bound method, implicit enumeration method, and the method of solving the problem of the Hungarian method。 Then these methods are applied to the investment problem, the automobile factory production problem and the assignment problem, and the difference between the solution of integer linear programming problem is explained by using these four methods。 Cutting plane method is suitable for most linear programming problems; Branch and bound method is applied to the problem of pure integer programming, and the calculation is more complicated;The implicit enumeration method is suitable for the 0-1 programming problem。 The method is simple and the calculation process is more complex; Hungarian method is suitable for assignment problem, but it is simple and easy to calculate。 Hungarian method is suitable for assignment problem, but it is simple and easy to calculate。

Key words:Integer linear programming; Implicit enumeration method; Branch and bound method; Gomory cut plane method; Hungarian method

目  录

摘要 1

引言 2

1线性规划的理论知识 3

1。1线性规划的简介 3

1。2线性规划的模型 3

1。3 线性规划的求解 3

2整数线性规划的简介及其解法 4

2。1整数线性规划的简介 4

2。2 Gomory割平面法 4

2。2。1 Gomory割平面法的基本思想 4

2。2。2 Gomory割平面法的计算步骤 4

2。3分枝定界法 5

2。3。1分枝定界法的基本思想 5

2。3。2 分枝定界法计算步骤 6

2。4隐枚举法 7

2。4。1隐枚举法的基本思想 7

2。4。2隐枚举法的计算步骤 7

2。5匈牙利法 7

2。5。1匈牙利法的基本思想 7

2。5。2匈牙利法的计算步骤 8

3。实例分析 8

3。1汽车生产问题 8

3。2投资项目的选择问题 13

3。3参赛项目的选择问题 15

3。4四种解法的探究 17

4．总结与展望 17

参考文献 19

致谢