【作者】 张立溥；

【导师】 胡清淮；

【作者基本信息】 湘潭大学 ， 应用数学， 2004， 硕士

【摘要】 文章研究了整数和混合整数规划中有效不等式以及割平面法的问题，共分四章，在第一章讨论了一般的有效不等式产生规则，并对此如何运用这些简单有效不等式给予举例说明，在此基础上得出著名的c—G割平面，Gomory，小数割平面，混合取整割平面以及Gomory混合整数割平面。在第二章运用一个超加性函数，通过参数的变化，取得一系列有效不等式，进而得到上述割平面的联系，同时对其进行有意义的推广。在第三章里，针对整数规划中的KnapsaCk问题的覆盖不等式进行讨论，通过O．1Knapsack问题，延伸到混合0．1问题，进而对整数KnapsaCk问题进行研究，文中还对覆盖不等式的升维伺题进行了探讨。第四章简要介绍了分枝定界法和割平面法的基本原理，并对有效不等式和割平面在分枝割平面法中的应用作了一些解释。说明了有效不等式在整数规划中的作用是巨大的。更多还原

【Abstract】 This thesis is for Master degree of mine, converting an intensivestudy of some theories of valid inequalities and cutting planes forinteger and mixed integer program with four chapters. Firstly itdiscuses some rules in deducing the simple valid inequalities, and theexamples in using these rules. Thus on this basis, we get all thefamous C-G cut, Gomory fractional cut, mixed integer roundingcut and Gomory mixed integer cut as well. Secondly we get a seriesof valid inequalities through changing the parameters in asupperadditive function, and also the relationship between this cutswith those as the valid inequalities which described in the first chapter.Thirdly, putting our focus on the discussion of Knapsack problem, wetalk about the cover inequalities of 0-1 knapsack and mixed 0-1knapsack problems, and also some results for the integer knapsackproblem. The lifting procedure was also discussed in this chapter.Lastly we give some introduction on branch and bounds and cuttingplane methods, and we also explain the usage of valid inequalities andcutting planes in newly branch and cut algorithm.更多还原