【整数规划基础】聂义勇.pdf

中国科学院先进制造研究与发展创新基金支持项目整数规划基础聂义勇贵刚宋翔编著

目录 1整数规划实例 1整数规划的概念 1单次装载问题 1产销平衡的运输问题 1工厂选址问题 1背包问题 1旅行售货员问题 1套裁下料问题习题 2单纯形法 2线性规划基本概念 2单纯形方法 2改进单纯形方法 2允许解的一般表:达式 2 对偶理论 2 变量带上界限制的线性规划问题 2几何意义 2 字典序单纯形方法 2列生成方法 2等高面法与拟单纯形法习题 3割平面法 3线性整数规划基本概念和性质 3割平面算法 3线性混合整数规划的割平面方法习题 4分支定界和隐式枚举 4分支定界法介绍 4.

1整数规划实例 1整数规划的概念任何具有极大和极小目标的决策问题都可以归结为一个整数最优化问题,其中(可量化)决策变量必须假定为非分数或离散值。一般地说,整数问题可以有约束或无约束,表示目标和约束的函数可以是线性或非线性。在严格意义下,每个整数问题都应当被看作非线性的,因为它的函数仅仅被定义为变量的离散值。然而,从研究整数问题解法的观点看,更有意义的分类是忽略这种技术细节。亦即,一个整数问题被归类为线性的,在放松变量的整数限制后函数是严格线性的。否则,问题是非线性的。以后将看出这种分类是研究整数问题解法的重要基础。