整数规划的分类？

一、整数规划的分类？

整数规划英文（integerprogramming）定义：在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。

例如，当变量代表的是机器的台数，工作的人数或装货的车数等。

为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。

在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。不同于线性规划问题，整数和01规划问题至今尚未找到一般的多项式解法。

组合最优化组合最优化通常都可表述为整数规划问题。

两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题,车辆路径问题等。

因此整数规划的应用范围也是极其广泛的。

它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

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

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

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

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

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

现今比较成功又流行的方法是分支定界法和割平面法，它们都是在上述框架下形成的。0—1规划0—1规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0—1规划等价，用0—1规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解0—1规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便。

二、凸规划问题的判定例题？

若最优化问题的目标函数为凸函数，不等式约束函数也为凸函数，等式约束函数是仿射的，则称该最优化问题为凸规划。凸规划的可行域为凸集，因而凸规划的局部最优解就是它的全局最优解。

当凸规划的目标函数为严格凸函数时，若存在最优解，则这个最优解一定是唯一的最优解。

三、0-1规划和整数规划的区别？

0-1规划是单统数规划。而整数规划是双统数规划。

四、怎么用lingo求解整数规划？

目前大学生接触较多的数学软件是matlab，其自带的linprog函数能够解决大量的线性规划问题，但是却没有用于解决整数规划的工具箱。事实上，还有一款专门适用于运筹学的软件lingo【他还有个同胞兄弟叫lindo，两者差不多】，由于功能单一，这个软件很小，很好用。

1，打开lingo。

2,输入程序框架。

3，输入问题，只需要按照图中的格式去写。可以看到，lingo的编程语言与我们所学到的运筹学公式基本一致。

4，添加整数约束,希望哪一个变量是整数，就在末尾加一行“@gin(变量);”就可以了。

5,得出结果,点击图中的“solve”按钮，即可。

6,查看结果,解决后，会弹出一个窗口，向你显示目标函数值和每个变量的取值。问题解决。

五、万加特纳整数规划法原理？

万加特纳整数规划法（Branch and Bound Method）是一种求解整数规划问题的常用方法，其原理是将整数规划问题分解成多个线性规划子问题，并利用分支和限界剪枝技术来减少搜索空间，最终找到最优解。

具体地，万加特纳整数规划法的主要步骤如下：

1. 初始化：将整数规划问题转化为一个线性规划求解问题，并确定最小目标函数值 $z^*$ 的上限和下限。

2. 分支：选择一个决策变量进行分支，将问题分解为两个线性规划子问题。每个子问题中仅有一个决策变量取整。

3. 限界剪枝：对于每个子问题，计算其上界和下界。如果一个子问题的上界小于当前已知最小目标函数值，则该子问题可被丢弃；如果一个子问题的下界大于当前已知最小目标函数值，则该子问题无需再继续拓展。

4. 选择：从所有未搜索的子问题中选择一个进入下一轮循环。

5. 结束条件：当所有未搜索的子问题都无法再被削减或者所有可行解均被评价后，算法结束，并返回发现的最优解。

万加特纳整数规划法通过构建一颗搜索树，对整数规划问题进行求解。其通过将问题分解为多个子问题，减小搜索空间大小，并通过限界剪枝技术加速求解过程。在实践中，万加特纳整数规划法是一种常用的高效求解整数规划问题的方法。

六、纯整数线性规划定义？

纯整数线性规划(Pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。整数线性规划是指要求一部分或全部决策变量必须取整数值的线性规划问题。典型的整数线性规划有纯整数线性规划、混合整数线性规划和0-1型整数线性规划。

七、0-1型整数规划的解法？

解0-1 型整数规划最容易想到的方法，和一般整数规划的情形一样。

就是穷举法，即检查变量取值为0 或1 的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的2的n次方个组合。

对于变量个数n 较大（例如n>100），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration ），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

八、整数规划分支定界法maxZ＝x₁＋x₂？

将(√x₁-√x₂)分子分母同乘以(√x₁+√x₂）,分子就是(x₁-x₂)分母就是(√x₁+√x₂）,所以等号后面是(x₁-x₂)/(√x₁-√x₂)

九、excel线性规划如何让结果为整数？

Excel 中的线性规划求解模型一般使用 Excel 的内置函数 Solver。要让线性规划的结果为整数，可以采取以下两种方法:

方法一：使用整数规划

整数规划是线性规划的一种特殊形式，它限制了决策变量必须是整数，而不是实数。所以，如果希望线性规划的结果为整数，可以将求解模型转换为整数规划问题。在 Excel 中，启用整数规划功能只需要勾选 Solver 参数设置“整数规划”选项即可。这种方法的缺点是，求解整数规划问题的时间复杂度一般比线性规划高得多，因此适用于决策变量数量较少的情况。

方法二：使用 Excel 的约束形式

可以针对每个决策变量给出一个整数约束条件，强制 Excel 求解模型只能使用整数。可以采用以下步骤实现：

1. 打开“名字管理器”，选中您的目标单元格，并创建一个名字。

2. 打开“数据验证”菜单，选中单元格，勾选“整数”选项。

3. 启用 Excel 的 Solver 功能，设置“假定值”并设置目标函数和约束条件。

4. 解决线性规划问题，获得求解结果。

此方法的缺点是每个决策变量需要另一个经过数据验证的单元格并重新设置诸如“期望值”之类的参数，这可能会变得很繁琐。

十、线性规划最优解不是整数怎么办？

1.

利用约束条件画出图形,如果得出的是非整数解,进行适当的调整,可以找与所求出的最优解(非整数解)接近的整数解进行验证;

2.

在直线的附近找出与此直线距离最近的整点,根据求出的结果给出最优解的整数解.