1、 实用运筹学课程设计 整数规划问题及其应用 院（系）名称 信息工程学院 专 业 班 级 10 普本信计一班 学 号 学 生 姓 名 指 导 教 师 2013 年 06 月 16 日 课程设计任务书 20122013 学年第二学期 课程设计名称： 实用运筹学 设计题目： 整数规划问题及其应用 完成期限：自 2013 年 06 月 10 日至 2013 年 06 月 16 日共 7 天 设计依据、要求及主要内容： 一、设计目的 熟练掌握整数规划问题的基本原理以及整数规划的求解方法、0-1整数规划 的求解方法， 以及关于这些方法的分析和综合应用， 并应用LINGO软件得到了结 果，并对结果进行分析.
2、以学习更多的运筹学知识. 二、设计内容 （1）详细介绍整数规划问题产生的背景及求解方法 （2）运用运筹学知识， 编写整数规划数学模型.（3）运用LINGO软件，对模型进行求解，并对结果进行 分析. 三、设计要求 1介绍整数规划问题产生的背景及求解整数规划问题的各种算法 2学会使用LINGO软件，求解实际的运筹学问题. 3熟练掌握运筹学求解实际问题的步骤，并进行结果分析. 计划答辩时间：2013 年 06 月 16 日 工作任务与工作量要求： 查阅文献资料不少于 3 篇，课程设计报告 1 篇不少于 3000 字 指导教师（签字） ： 教研室主任（签字） ： 批准日期： 2013 年 06 月 0
3、9 日 整数规划问题及其应用 摘 要 运筹学是运用代数学、统计学等现代应用数学的方法和技术，通过建立 数学模型分析研究各种资源的运用、 筹划及相关决策等问题的一门新兴学科。 其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、 规划及其相关决策等问题作出综合最有的合理安排，以使有限的资源发挥更 大的效益或作用。LINGO 是一款解决线性规划、整数规划、二次规划的强大 工具软件，它的使用减少了大量的人工计算。在运筹学的研究中，LINGO 如 见扮演着重要的角色。 本文主要研究整数规划，建立整数规划数学模型，运用 LINGO 软件求解 整数规划的最优解，从而获得最优方案。很多实际问题
4、中，变量的取值必须 是整数。因此，整数规划的模型对研究运筹学问题有重要的意义。 关键词：运筹学，整数规划，LINGO，最优解. 目 录 1 前言 1 2 整数规划问题的理论基础 1 2.1 分支定界法 2 2.2 割平面法 . 3 2.3 0-1 整数规划的数学模型 4 3 整数规划问题的 LINGO 求解方法 6 3.1 一般整数规划的解法 6 3.2 一般 0-1 规划的解法 7 4 实例应用 8 4.1 一般整数规划问题实例分析 . 8 4.2 0-1 整数规划的实例分析 12 总 结 18 参考文献 18 1 前言 整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。 是近三
5、十年 来发展起来的、 规划论的一个分支. 整数规划问题是要求决策变量取整数值的线性规划 或非线性规划问题。 一般认为非线性的整数规划可分成线性部分和整数部分， 因此常常把整数规划作为 线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些 具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的 车数等。 为了满足整数的要求， 初看起来似乎只要把已得的非整数解舍入化整就可以了。 实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。 在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限 制为整数，则称为混合整数规划。整数规划的一种特殊情形是 01 规划，它的变数仅限 于 0 或 1。 整数规划是从 1958 年由 R.E.戈莫里提出割平面法之后形成独立分支的 ，30 多年 来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问 题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题 （衍生问题称为松弛问题的源问题） 。通过松弛问题的解来确定它的源问题的归宿，即 源问题应被舍弃，还是
