北京网站优化seo,品牌企业建站,常用的软件开发平台,仿站前几章讨论过的线性规划问题的一个共同特点是#xff1a;最优解的取值可以是分数或者小数。然而#xff0c;在许多实际问题中#xff0c;决策者要求最优解必须是整数#xff0c;例如公交车的车辆数、员工的人数、机器的台数、产品的件数等。那么#xff0c;我们能否将得到…前几章讨论过的线性规划问题的一个共同特点是最优解的取值可以是分数或者小数。然而在许多实际问题中决策者要求最优解必须是整数例如公交车的车辆数、员工的人数、机器的台数、产品的件数等。那么我们能否将得到的非整数最优解“舍入化整”呢答案是否定的原因在于1非整数最优解化为整数后可能不再是可行解2即使是可行解也有可能不再是其整数可行解范围内的最优解。因此我们有必要单独研究那些最优解必须是整数的线性规划问题即整数线性规划问题。
1958年R. E. Gomory 在《Outline of an algorithm for integer solutions to linear programs》一文中提出了求解整数规划问题割平面法此后整数规划作为一个独立的研究分支受到人们的广泛关注。1960年A. H. Land 和A. G. Doig 在《An automatic method for solving discrete programming problems》中提出了分支定界法Branch and Bound Method大幅度提高了整数规划的求解效率。目前整数规划仍然是运筹学研究的热点研究者们提出了许多高效的求解方法来解决各种问题已经在交通运输、物流供应链、生产制造和金融等领域取得了巨大的成功。
通过对整数规划问题基础知识的梳理和总结小编绘制了《整数规划思维导图》如下图所示。整数规划问题章节一共有5个知识点和12个子知识点。
第一个知识点是整数规划的数学模型该部分包括整数规划数学模型的一般形式和数学模型的类型两个子知识点。
第二个知识点是解整数规划的割平面法该部分主要讲解了两个子知识点分别是割平面法的基本思路和求解步骤。
第三个知识点是解整数规划的分支定界法它为整数规划模型的求解提高了效率该部分将会对分支定界法的核心思想和求解步骤2个子知识点进行具体介绍。
第四个知识点是0-1型整数规划这部分主要包括0-1型整数规划的定义、应用和隐枚举法3个子知识点。
第五个知识点是指派问题包括3个子知识点介绍了指派问题的数学模型和指派问题的独特算法——匈牙利解法对于非标准形式的指派问题及其求解方式也进行了介绍。
今天小编先带大家学习整数规划的数学模型和割平面法。
一、整数规划的数学模型
1、一般形式 2、问题分类 3、例题展示 二、割平面法
1、解题思路 2、解题步骤 3、例题 4、注意事项
