整数规划

进行规划求解前，确定变量，上边例子中变量就是B1:B10，而且数字只能是0或1的整数在D1写入公式=SUMPRODUCT(A1:A10,B1:B10)点击“数据”选项卡，“规划求解”；目标单元格“D1”，目标值“15”，通过可改变单元格“B1:B10"（光标放在框中，拖动选择即可，实际出现结果是“$B$1:$B$10”），然后“添加”约束条件；按照要求，B1:B10的数字只能是0或者1两个整数，点击“添加”，一次添加“整数”约束、>=0与<=1的约束，注意“单元格引用”的引用范围就是变量区域B1:B10；上图为整数约束，点击“添加”上图为>=0的约束，点击“添加”上图为<=1的约束，最后一个约束条件添加完成，点击“确定”，如果误点了“添加”，再点击下“取消”即可；条件添加完成后，即返回了“规划求解”对话框，点击“求解”；得到求解结果，B列数字1对应的A列数字就是满足要求的数据，本例比较简单，满足条件的数据不只一组，但规划求解只会给出一组数据。

整数规划法是限制变数的全部或一部分取整数值的线性规划问题称为整数规划。求解整数规划的方法称为整数规划法。戈莫里(R.Gomory)在1960年提出了几种解整数规划的方法。主要想法是在无视整数限制条件下求得的解为非整数时，再导出整数解应满足的较强的不等式条件。依靠添加这样的约束条件删去前面已求得的解。再解一个新的子问题，直至求得最优解。几乎解整数规划的所有方法都是把原问题分解成一系列较为易解的子问题，而这些子问题中至少有一个问题，其最优解同原问题的最优解相同。 最常用的解法有枚举法，割平面法，分支定界法，图论法，二元开发法等。总之求解整数规划的方法比解线性规划的方法复杂得多。通常没有固定的方法。有些问题需根据问题的性质设计独特的运算方法。整数规划的套用极为广泛。如生产序列，工序调度，车间布局，设备计画，资金预算等都涉及到整数规划法的套用。对整数规划目前已得到的能够满足实用的计算方法将会开辟出更广泛的套用领域。

用ms求得：x1=4x2=0o.f.=20

组合最优化通常都可表述为整数规划问题。两者都是在有限个可供选择的方案中，寻找满足一定约束的最好方案。有许多典型的问题反映整数规划的广泛背景。例如，背袋（或装载）问题、固定费用问题、和睦探险队问题（组合学的对集问题）、有效探险队问题（组合学的覆盖问题）、旅行推销员问题, 车辆路径问题等。因此整数规划的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

下列哪些问题属于整数规划问题（） A.纯整数规划 B.混合整数规划 C.0-1规划 D.线性规划 正确答案：ABC

如果整数规划是求最小问题,那么对应的线性规划的最优值比原问题的最优值要小；如果整数规划是求最大问题,那么对应的线性规划的最优值比原问题的最优值要大.但从目标值上,松弛线性规划的更优,但它不是整数规划问题的可行解.

规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划。