整数规划的特点及应用 Page 11 每项工作只能安排一人，约束条件为： xm+x21+x31+x41=1 X12+x2+X32+x2=1 X13+X23+X33+x43=1 X14+x24+X34+x44=1 变量约束： x,=0或1，ij=1,2,3,4
整数规划的特点及应用 Page 11 每项工作只能安排一人，约束条件为： + + + = + + + = + + + = + + + = 1 1 1 1 1 4 2 4 3 4 4 4 1 3 2 3 3 3 4 3 1 2 2 2 3 2 4 2 1 1 2 1 3 1 4 1 x x x x x x x x x x x x x x x x 变量约束： xij = 0或1，i、j = 1,2,3,4
整数规划的特点及应用 Page 12 整数规划问题解的特征： 。整数规划问题的可行解集合是它松弛问题可行解集合的一 个子集，任意两个可行解的凸组合不一定满足整数约束条件， 因而不一定仍为可行解。 ·整数规划问题的可行解一定是它的松弛问题的可行解（反 之不一定)，但其最优解的目标函数值不会优于后者最优解 的目标函数值
整数规划的特点及应用 Page 12 整数规划问题解的特征： 整数规划问题的可行解集合是它松弛问题可行解集合的一 个子集，任意两个可行解的凸组合不一定满足整数约束条件， 因而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解（反 之不一定），但其最优解的目标函数值不会优于后者最优解 的目标函数值
整数规划的特点及应用 Page 13 例4.3设整数规划问题如下 maxZ=x+x 14x,+9x2≤51 6x1+3x2≤1 x,x2≥0且为整数 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题)。 max Z=x+x 14x1+9x2≤51 -6x1+3x2≤1 x1,x2≥0
整数规划的特点及应用 Page 13 例4.3 设整数规划问题如下 − + + = + , 0且为整数 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。 − + + = + , 0 6 3 1 14 9 51 max 1 2 1 2 1 2 1 2 x x x x x x Z x x
整数规划的特点及应用 Page 14 用图解法求出最优解为：x1=3/2,x2=10/3,且有Z=29/6 现求整数解（最优解）：如用舍 入取整法可得到4个点即(1， X2 (1) (2) 3),(2,3),1,4),(2,4)。显然， 3/2,10/3) 它们都不可能是整数规划的最优 3 解。 按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(2,2)，(3,1)点的目 标函数值最大，即为Z-4
整数规划的特点及应用 Page 14 用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6 现求整数解(最优解):如用舍 入取整法可得到4个点即(1， 3),(2，3),(1，4),(2，4)。显然， 它们都不可能是整数规划的最优 解。 x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) 按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(2,2),(3,1)点的目 标函数值最大，即为Z=4
整数规划的特点及应用 Page 15 整数规划问题的求解方法： 。分支定界法和割平面法 。匈牙利法（指派问题）
整数规划的特点及应用 Page 15 整数规划问题的求解方法： 分支定界法和割平面法 匈牙利法（指派问题）