1、整 数 规 划(Integer Programming)整数规划的模型分支定界法割平面法指派问题（一）、整数规划与线性规划的关系从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。举例说明。一、整数规划的模型例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用 解法求出最优解x1 3/2, x2 = 10/3且有 Z = 29/6x1x2 33(3/2,10/3)现求整数解（最优解）：
2、如用 “舍入取整法 ”可得到 4个点即 (1， 3) (2，3)(1， 4)(2， 4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。图因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中 （ 2， 2）（ 3， 1） 点为最大值， Z=4。目前，常用的求解整数规划的方法有：分支定界法和割平面法；对于特别的 0 1规划问题采用隐枚举法和匈牙利法。（ 二）、整数规划的数学模型一般形式依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、
3、混合整数规划、 0 1整数规划。纯整数规划： 所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。 全整数规划： 除了所有决策变量要求取非负整数外，系数 aij和常数 bi也要求取整数（这时引进的松弛变量和剩余变量也必须是 整数）。混合整数规划： 只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。0 1整数规划： 所有决策变量只能取 0 或 1 两个整数 。在实际中经常会遇到这样的问题，有 n 项不同的任务，需要 n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指
4、派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。（一）、指派问题的数学模型设 n 个人被分配去做 n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第 I 个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2 n;j=1.2 n)并假设 Cij 0。 问应如何分配才能使总效率（ 时间或费用）最高？二、指派问题设决策变量 1 分配第 i 个人去做第 j 件工作xij =0 相反 ( I,j=1.2. n )其数学模型为：（二）、解题步骤：指派问题是 0-1 规划的特例，也是运输问题的特例，当然可用整数规划， 0-1 规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即 系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第一步：变换指派问题的系数矩阵（ cij）为 (bij)， 使在 (bij)的各行各列中都出现 0元素，即(1) 从（ cij） 的每行元素都减去该行的最小元素；(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。
