第四章整数规划与分配问题 本章主要内容： 整数规划的特点及作用 ·分配问题与匈牙利法 兼分支定界法 兼割平面法（自学） 豢 0-1型整数规划应用举例 2014-12-15 1
2014-12-15 1 第四章 整数规划与分配问题 整数规划的特点及作用 分配问题与匈牙利法 分支定界法 割平面法（自学） 0-1型整数规划应用举例 本章主要内容：
§1整数规划的特点及作用 整数规划（简称：IP) 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。（线性整数规划、非线性整数规划等） 整数规划问题的种类： ·纯整数规划：指全部决策变量都必须取整数值的整数规划。 ·混合整数规划：决策变量中有一部分必须取整数值，另一 部分可以不取整数值的整数规划。 ·0-1型整数规划：决策变量只能取值0或1的整数规划。 2014-12-15
2014-12-15 2 §1 整数规划的特点及作用 整数规划（简称：IP） 要求一部分或全部决策变量取整数值的规划问题称为整 数规划。（线性整数规划、非线性整数规划等） 纯整数规划：指全部决策变量都必须取整数值的整数规划。 混合整数规划：决策变量中有一部分必须取整数值，另一 部分可以不取整数值的整数规划。 0-1型整数规划：决策变量只能取值0或1的整数规划。 整数规划问题的种类：
§1整数规划的特点及作用 例1设整数规划问题如下 max Z=3x+2x2 2x1+3x2≤14 s.tx1+0.5x2≤4.5 x1,x2≥0且为整数 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题) 0 max Z=3x+2x2 2x1+3x2≤14 s.t. x1+0.5x2≤4.5 x1,x2≥0 2014-12-15 3
2014-12-15 3 §1 整数规划的特点及作用 例1 设整数规划问题如下 , 0且为整数 0.5 4.5 2 3 14 . . max 3 2 1 2 1 2 1 2 1 2 x x x x x x st Z x x 首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。 , 0 0.5 4.5 2 3 14 s.t. max 3 2 1 2 1 2 1 2 1 2 x x x x x x Z x x
§1整数规划的特点及作用 用图解法求出最优解为：X,=3.252=2.5,且有7=14.75 现求整数解（最优解）：如用舍 入取整法可得到4个点即(4， 3),(4,2),3,3),3,2)。显然， 它们都不可能是整数规划的最优 解。 按整数规划约束条件，其可行 3.25,2.5) 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(4,1)点的目标函 数值最大，即为Z=14。 2014-12-15
2014-12-15 4 §1 整数规划的特点及作用 用图解法求出最优解为：x 1＝3.25, x 2 = 2.5，且有Z = 14.75 现求整数解(最优解):如用舍 入取整法可得到4个点即(4， 3),(4，2),(3，3),(3，2)。显然， 它们都不可能是整数规划的最优 解。 x1 x2 ⑴ ⑵ 4 4 (3.25,2.5) 按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(4,1)点的目标函 数值最大，即为Z=14
§1整数规划的特点及作用 整数规划问题的求解方法： 。匈牙利法（指派问题） ·分支定界法和割平面法 2014-12-15 5
2014-12-15 5 §1 整数规划的特点及作用 整数规划问题的求解方法： 匈牙利法（指派问题） 分支定界法和割平面法
§2分配问题与匈牙利法 指派问题的数学模型的标准形式： 设n个人被分配去做件工作，规定每个人只做一件工作， 每件工作只有一个人去做。已知第个人去做第j件工作的效率 （时间或费用)为C=1.2.nj=1.2.n)并假设Ci≥0。问应 如何分配才能使总效率（时间或费用)最高？ 设决策变量 1 指派第个人做第件事 0 不指派第个人做第件事 (i,j=1,2,.,n) 2014-12-15 6
2014-12-15 6 §2 分配问题与匈牙利法 指派问题的数学模型的标准形式： 设n 个人被分配去做n 件工作，规定每个人只做一件工作， 每件工作只有一个人去做。已知第i个人去做第j 件工作的效率 （ 时间或费用）为Cij(i=1.2.n;j=1.2.n)并假设Cij ≥0。问应 如何分配才能使总效率（ 时间或费用）最高？ 设决策变量 ( , 1,2,., ) 0 i j 1 i j xi j i j n 不指派第个人做第件 事 指派第 个人做第件 事
§2分配问题与匈牙利法 指派问题的数学模型为： minZ=会2cx, 2=1=12.n 2,=10=12.m x取0或1(i,i=1.2.n) 2014-12-15
2014-12-15 7 §2 分配问题与匈牙利法 指派问题的数学模型为： 0 1( , 1.2. . ) 1 ( 1.2. . ) 1 ( 1.2. . ) min 1 1 1 1 x i j n x j n x i n Z c x i j n i i j n j i j n i n j i j i j 取 或
§2分配问题与匈牙利法 匈牙利解法： 标准的指派问题是一类特殊的0-1整数规划问题，可以用 多种相应的解法来求解。但是，这些方法都没有充分利用指 派问题的特殊性质来有效减少计算量。1955年，库恩 (W.W.Kuhn)利用匈牙利数学家克尼格(D.Konig)的关于 矩阵中独立零元素的定理，提出了指派问题的一种解法，由 此，习惯上称之为匈牙利解法。 2014-12-15 8
2014-12-15 8 §2 分配问题与匈牙利法 匈牙利解法： 标准的指派问题是一类特殊的 0-1 整数规划问题，可以用 多种相应的解法来求解。但是，这些方法都没有充分利用指 派问题的特殊性质来有效减少计算量。1955年，库恩 （W.W.Kuhn）利用匈牙利数学家克尼格（D.König）的关于 矩阵中独立零元素的定理，提出了指派问题的一种解法，由 此，习惯上称之为匈牙利解法
§2分配问题与匈牙利法 克尼格定理： 定理1：如果从分配问题效率矩阵[Q]的每一行元素中分别 减去（或加上）一个常数U,从每一列中分别减去（或加上）一 个常数y,得到一个新的效率矩阵bJ,则以[b]为效率矩 阵的分配问题与以[Q]为效率矩阵的分配问题具有相同的 最优解。 定理2：若矩阵A的元素可分为“0”元和“非0”元，则覆盖 “0”元的最少直线数等于位于不同行、不同列的“0”元的最 大个数。 2014-12-15
2014-12-15 9 §2 分配问题与匈牙利法 克尼格定理 : 定理1：如果从分配问题效率矩阵[aij]的每一行元素中分别 减去(或加上)一个常数ui，从每一列中分别减去(或加上)一 个常数vj，得到一个新的效率矩阵[bij]，则以[bij]为效率矩 阵的分配问题与以[aij]为效率矩阵的分配问题具有相同的 最优解。 定理2：若矩阵A的元素可分为“0”元和“非0”元，则覆盖 “0”元的最少直线数等于位于不同行、不同列的“0”元的最 大个数
§2分配问题与匈牙利法 匈牙利法求解步骤如图： 每行减去该行最小数 每列减夫该列最小数 五 先看行，只有1个0，标记为()划去所在列，转下行，直到最后行 再看列，只有1个0，标记为()划去所在行， 转下列，直到最后列 重发上述过程 ()个数<马不存在闭回路 三种结局 ()个数<n,存在0的闭回路 从未被划去的数找最小 ()个数=n 从闭回路任一0出发，在 数k,末被划去的数字减 转弯处按顺序编号，取单 k, 履盖直线交叉处加k ()处取1，其余取0， 号（或双号）标记() 得最优解 图4.7匈牙利法流程图 ∠U14-1∠-13 LU
2014-12-15 10 §2 分配问题与匈牙利法 ( ) ( ) ( ) ( ) ( ) ( ) ，不存在闭回路 （）个数<n