1. 整数规划怎么求解

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

1，打开lingo。

2,输入程序框架。

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

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

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

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

2. 求解整数规划的方法

1,这两种也只能精确求解线形规划问题

2, 要看问题特性, 有些可以按照线性规划方法解最优解

3, 大规模问题,一般要用到分解算法.

3. 整数规划的解法

1.在工具菜单的 加载宏 加载此功能 2. Microsoft Excel 在 Office\Samples 文件夹下有一个工作簿 (Solvsamp.xls)，其中给出了可以解决的问题类型的示例。您可以借助 Solvsamp.xls 中的示例工作表来解决一些实际问题。一共有六张工作表可用：“产品组合”、“货物传送”、“排班组合”、“最大收益”、“投资方案”和“电路设计”。若要使用某个示例工作表，请打开工作簿，切换到相应工作表，再单击“工具”菜单中的“规划求解”。示例工作表中的目标单元格、可变单元格和约束条件已经被指定了。

4. 一般整数规划的求解方法

1、先选择数据列，然后ctrl+H替换，把所有0替换删除掉，替换内容不用写，注意单元格格匹配点上，不然会把10变成1之类的。

2、保持选择区域不变（不要乱点鼠标），按ctrl+G定位，定位条件选“空值“

3、定位选择后在有选区内点鼠标右键选删除，选下方单元格上移。完成。

5. 规划求解 整数

你所说是（1）交点不满足最优解，可适当放大横或纵坐标，寻求最接近交点的最优解，此时的最优解横或纵坐标一般都是整数（2）某一处边界上的所有点都是最优解

6. 求解纯整数规划的方法

化简小数的方法：去掉小数末尾的0，把小数写成简单的形式。例如：0.460=0.46，0.050=0.05。小数，是实数的一种特殊的表现形式。所有分数都可以表示成小数，小数中的圆点叫做小数点，它是一个小数的整数部分和小数部分的分界号。其中整数部分是零的小数叫做纯小数，整数部分不是零的小数叫做带小数。

7. 整数规划如何求解

分枝界限法是由三栖学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，成功求解含有65个城市的旅行商问题，创当时的记录。“分枝界限法”把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。

简介

分枝界限法也能够使用在混合整数规划问题上，其为一种系统化的解法，以一般线性规划之单形法解得最佳解后，将非整数值之决策变量分割成为最接近的两个整数，分列条件，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数值的上限（上界）或下限（下界），从其中寻得最佳解。

基本思想

1、基本思想

分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。

将问题分枝为子问题并对这些子问题定界的步骤称为分枝定界法。

2、分枝节点的选择

对搜索树上的某些点必须作出分枝决策，即凡是界限小于迄今为止所有可行解最小下界的任何子集（节点），都有可能作为分枝的选择对象（对求最小值问题而言）。怎样选择搜索树上的节点作为下次分枝的节点呢？有两个原则：

1）从最小下界分枝（队列式FIFO分枝限界法）：每次算完界限后，把搜索树上当前所有叶节点的界限进行比较。找出限界最小的节点，此结点即为下次分枝的结点。

• 优点：检查子问题较少，能较快地求得最佳解；

• 缺点：要存储很多叶节点的界限及对应的耗费矩阵，花费很多内存空间。

2）从最新产生的最小下界分枝（优先队列式分枝限界法）：从最新产生的各子集中选择具有最小的下界的结点进行分枝。

优点：节省了空间； 缺点：需要较多的分枝运算，耗费的时间较多。这两个原则更进一步说明了，在算法设计中的时空转换概念。分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题。对于不同的问题，分枝与界限的步骤和内容可能不同，但基本原理是一样的。

步骤

分枝界限法是组合优化问题的有效求解方法，其步骤如下所述：

步骤一：如果问题的目标为最小化，则设定目前最优解的值Z=∞。

步骤二：根据分枝法则（Branching rule），从尚未被洞悉（Fathomed）节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的节点。

步骤三：计算每一个新分枝出来的节点的下限值（Lower bound，LB）。

步骤四：对每一节点进行洞悉条件测试，若节点满足以下任意一个条件，则此节点可洞悉而不再被考虑：

• 此节点的下限值大于等于Z值。

• 已找到在此节点中，具最小下限值的可行解；若此条件成立，则需比较此可行解与Z值，若前者较小，则需更新Z值，以此为可行解的值。

• 此节点不可能包含可行解。

步骤五：判断是否仍有尚未被洞悉的节点，如果有，则进行步骤二，如果已无尚未被洞悉的节点，则演算停止，并得到最优解。

Kolen等曾利用此方法求解含时间窗约束的车辆巡回问题，其实验的节点数范围为6-15。当节点数为6时，计算机演算所花费的时间大约1分钟（计算机型为VAZ11/785），当节点数扩大至12时，计算机有内存不足的现象产生，所以分枝定界法比较适用于求解小型问题。Held和Karp指出分枝定界法的求解效率，与其界限设定的宽紧有极大的关系。