整数规划问题--毕业论文.doc

--------------------------校验:_____________-----------------------日期:_____________整数规划问题--毕业论文目录摘要 IAbstract II引言 11整数规划问题 1概念 1分类 1整数规划的一般形式 22整数规划问题的计算方法 2分支定界法 2割平面法 23整数规划问题的应用 3在经济管理问题中的应用 3投资问题 3生产安排问题 4下料问题 7在指派问题中的应用 8平衡指派问题 9不平衡指派问题 10非确定型指派问题 12在组合优化方面的应用 14一维背包问题 14选址问题 15在集合划分问题中的应用 16中心覆盖问题 17旅行商问题(TSP) 18结论 19致谢 20参考文献 20整数规划问题的应用摘要:整数规划(IntegerProgramming,IP)是带整数变量的最优化问题。即最大化或最小化全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。整数规划的历史可以追溯到20世纪50年代,主要是由于经济管理中的大量问题抽象为模型时,人们发现许多量具有不可分割性,因此当它们被作为变量引入到规划中时,常要求满足取整条件。而今,许多经济、管理、通信和工程中的最优化问题都可以用整数规划来建模。本文主要阐述了整数规划的理论基础,给出了整数规划的基本模型以及计算方法,在此基础上对一些整数规划问题及其解答方法进行归纳总结,最后列举了若干整数规划在现实中的应用实例,将数学知识应用到实际生活中来解决实际问题,从而使得该问题形象化、简单化,同时进一步完善和丰富整数规划理论。关键词:整数规划问题;实际应用;0-1整数规划;数学模型ApplicationofintegerprogrammingproblemsAbstract:Integerprogrammingisanoptimizationproblemwithintegervariables,whichmaximizeorminimizethemultiplefunctionsoffullorpartialvariablesforinteger,,mainlyduetoalargenumberofproblemsineconomicmanagementbeabstractedasamodel,itisfoundthatmanyareinseparable,optimizationproblemswithintegerofeconomic,,,,:IntegerProgramming;Practicalapplication;0-1integerlinearprogramming;Mathematicalmodel引言整数规划(IntegerProgramming,IP)是规划论中近30年才发展起来一个重要分支。整数规划与组合最优化从广泛的意义上说,两者的领域是一致的,都是在有限个可供选择的方案中,寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。例如,背包(或装载)问题、固定费用问题、有效探险队问题(组合学的覆盖问题)、送货问题等。因此整数规划的应用范围是极其广泛的。它不仅在工业、工程设计和科学研究方面有许多应用,而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。此外,整数规划还可以描述和处理互斥决策问题。如运作管理中的决策问题:工厂选址、超市选址、人员的工作指派、设备购置和配置、系统可靠性设计、机床加工任务的均衡分派、线路设计中的接点串联设计等;物流管理中,物流中心的定点决策;以及金融和项目投资中的组合投资和项目选择