HUNAN UNIVERSITY运筹学课程设计报告课程题目整数线性规划及应用学生姓名学生学号专业班级指导老师目录摘要-------------------------------------------------------------1一、整数规划概述 ---------------------------------------------------21分支定界法----------------------------------------------------- 32 割平面法-------------------------------------------------------43 0-1整数规划的数学模型------------------------------------------43.1 0-1规划隐枚举法---------------------------------------------53.2指派问题的匈牙利方法-----------------------------------------6二、整数规划问题的LINGO求解----------------------------------------71般整数规划的解法-----------------------------------------------72一般0-1规划的解法----------------------------------------------8三、整数规划应用----------------------------------------------------91一般整数规划问题实例分析（人力资源分配问题）--------------------92 0-1整数规划的实例分析（消防站问题、背包问题）--------------------11四、总结-----------------------------------------------------------20参考文献-----------------------------------------------------------21摘要运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。

它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。

对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。

运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。

其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、规划及其相关决策等问题作出综合最有的合理安排，以使有限的资源发挥更大的效益或作用。

LINGO可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解优化模型的最佳选择。

其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数（即整数规划，包括0-1 整数规划），方便灵活，而且执行速度非常快。

在运筹学的研究中，LINGO如见扮演着重要的角色。

一般地，使用LINGO 求解运筹学问题可以分为以下两个步骤来完成：1）根据实际问题，建立数学模型，即使用数学建模的方法建立优化模型；2）根据优化模型，利用LINGO 来求解模型。

主要是根据LINGO 软件，把数学模型转译成计算机语言，借助于计算机来求解。

本文主要研究整数规划，建立整数规划数学模型，运用LINGO软件求解整数规划的最优解，从而获得最优方案。

因此，整数规划的模型对研究运筹学问题有重要的意义。

关键词：运筹学整数规划LINGO 最优解0-1整数规划一、 整数规划概述整数规划是指一类要求问题中的全部或一部分变量为整数的数学规划。

是近三十年来发展起来的、规划论的一个分支.。

整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。

一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。

在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。

例如，所求解是机器的台数，工作的人数或装货的车数等。

为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。

实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。

整数规划是从1958年由R.E.戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。

解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。

对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。

通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。

随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。

目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。

整数线性规划中如果所有的变量都限制为非负整数，就称为纯整数线性规划或全整数线性规划；如果仅一部分变量限制为整数，则称为混合整数规划。

整数规划的一种特殊情形是0-1规划，它的变量的取值仅限于0和1。

整数规划的一个著名问题---指派问题就是0-1规划问题。

目前所流行的求解整数规划的方法，往往只适用于整数线性规划.本文我们主要讨论整数线性规划问题. 整数线性规划一般模型：x c i ni i Z Z ∑==1)min (max 或s.t b x a i j nj ij =∑=1)...2,1(m i =且部分或全部为整数)...2,1(0n j xj=≥它的求解往往较为复杂，现在公认的几种解法有分支定界法、割平面法和完全枚举法。

但随着计算机技术的发展，求解整数规划问题已经不是难事，如Lingo 和Lindo 等软件都可以十分轻松的进行求解。

下面对部分解法进行介绍和探讨。

1.分支定解法对有约束条件的最优化问题（其可行解为有限数）的可行解空间恰当地进行系统搜索，这就是分枝与定界内容.通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界.在每次分枝后，凡是界限不优于已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。

这就是分枝定界法的主要思路.。

分枝定界法可用于解纯整数或混合的整数规划问题。

在二十世纪六十年代初由Land Doig 和Dakin 等人提出.由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。

目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等.设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z *的上界，记作z -；而A 的任意可行解的目标函数值将是z *的一个下界z -.分枝定界法就是将B 的可行域分成子区域再求其最大值的方法.逐步减小z -和和增大z -，最终求到z *。

用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题A ，将与它相应的线性规划问题称为问题 B 。

A 、解问题B 可能得到以下情况之一：(a).B 没有可行解，这时A 也没有可行解，则停止。

(b).B 有最优解，并符合问题A 的整数条件，B 的最优解即为A 的最优解，则停止。

(c).B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为z 0-.。

B 、用观察法找问题A 的一个整数可行解，一般可取)...2,1(0n j x j ==试探，求得其目标函数值，并记作z -.以z *表示问题A 的最优目标函数值；这时有z z z --≤≤*C 、进行迭代第一步：分枝，在B 的最优解中任选一个不符合整数条件的变量x j ，其值为b j ，以[]b j 示小于b j 的最大整数.构造两个约束条件1][][j +≥≤b x b xj j j和将这两个约束条件，分别加入问题B ，求两个后继规划问题B B 21和.不考虑整数条件求解这两个后继问题.。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z -.从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z -，若无可行解，z -=0。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于z -者，则剪掉这枝，即以后不再考虑了.若大于z -，且不符合整数条件，则重复第一步骤.一直到最后得到z z -=*为止。

得最优整数解.,...,1,*n j x j=2.割平面法用割平面法求解整数规划的基本思路是：先不考虑整数约束条求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止。

如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解。

这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)，而把所有的整数解都保留下来，故称新增加的约束条件为割平面。

当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解。

即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。

割平面法的基本步骤：A 、先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。

在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。

这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。

第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。

B 、求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。

3.0-1整数规划的数学模型如果整数规划中的所有决策变量),...,1(n i x i =仅限于取0或1两个值，则称此问题为0-1整数规划，简称0-1规划。

其变量x i 称为0-1变量，或二进制变量。

相应的决策变量的取值约束变为0=x i 或1，等价于1≤≥x x i i 和，且为整数。

0-1线性规划的一般模型为：x c i ni i Z Z ∑==1)min (max 或s.t. b x a i j nj ij =∑=1)...2,1(m i =),...,1(10n j x j ==或3.1 0-1规划隐枚举法0-1整数规划模型的解法一般为显枚举法（穷举法）或隐枚举法。