运筹学第17讲复习分配问题与匈牙利法.ppt

1、第四章整数规划与分配问题,整数规划的特点及作用 分枝定界法 割平面法 分配问题与匈牙利法 应用举例,Integer Programming,简称IP,有纯整数规划、混合整数规划与0-1整数规划等类型。我们只研究线性整数规划。,整数规划是研究决策变量只能取正整数的一类规划问题。,整数规划的特点 （1）可行解域为离散点集 （2）不能用舍入取整法 （3）目标函数值的最优值 不会优于其松弛问题 的最优值,整数规划的特点,整数规划的求解,分枝定界法 割平面法,共同点：通过增加附加约束，使整数最优解最终成为线性规划可行域的一个顶点，从而使问题可利用单纯形法求出这个整数最优解； 不同点：附加约束条件的选取原

2、则及方法不同。,实质：在保留原问题全部整数可行解的前提下，将原问题分枝为若干容易求解的子问题，并利用子问题的整数解的目标值来判定分枝的界限。,分枝定界法,解：设应购进甲、乙机床台数分别为x1和x2，数学模型为：,1、去掉变量为整数约束，可用图解法求得最优解；,x1=3.25非整数，进行分枝,(3.25,2.5)T,X(0)=(x1,x2)T=(3.25,2.5)T Z(0)=14.75,【例】某厂拟购进甲、乙两类机床生产新产品。已知两类机床进价分别为2万元和3万元，安装占地面积分别为4m2和2m2，投产后的收益分别为3百元/日和2百元/日。厂方仅有资金14万元，安装面积18m2，为使收益最大，

3、厂方应购进甲、乙机床各多少台？,x1=3.25非整数，进行分枝,2、得两个子问题的数学模型: 子问题(1) 子问题(2),分别用图解法求得最优解 X(1)=(3,2.67)T, Z(1)=14.33 X(2)=(4,1)T, Z(2)=14,Z(1) Z(2) =14,子问题2停止分枝，其整数解作为界； 子问题1对x2=2.67进行分枝,子问题(3) 子问题(4),子问题(1),Z(1) Z(2) =14,子问题2停止分枝，其整数解作为界； 子问题1对x2=2.67进行分枝,分别用图解法求得最优解 X(3)=(3,2)T, Z(3)=13 X(4)=(2.5,3)T, Z(4)=13.5,Z(

4、3) Z(2) ; Z(4) Z(2),子问题(3) 子问题(4),子问题(1),Z(1) Z(2) =14,子问题2停止分枝，其整数解作为界； 子问题1对x2=2.67进行分枝,分别用图解法求得最优解 X(3)=(3,2)T, Z(3)=13 X(4)=(2.5,3)T, Z(4)=13.5,Z(3) Z(2) ; Z(4) Z(2),最优解：X*=X(2) =(4,1)T 最优值：Z*=14,添加x23,添加x13,添加x22,添加x14,分枝问题解可能出现的情况表,情况 2, 4, 5 找到最优解 情况 3 在缩减的域上继续分枝定界法 情况 6 中问题 1 的整数解作为界被保留，用于以后

5、与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5,割平面法,割平面法的基础仍然是用解线性规划的方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件（Gomory约束，称为割平面），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解，切除的结果使整数解可能成为顶点。,分枝定解法是对原问题可行解域进行了切割，切割方法是对取非整数解相邻的整数作附加约束，约束方程简单，但子问题由于分枝的增多而成指数增长。,割平面法,割平面法的基础仍然是用解线性规划的方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件（Gomory约束，称为割平面

6、），使得原可行解域中切掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解，切除的结果使整数解可能成为顶点。,关键：如何找到割平面约束方程，使切割后最终得到这样的可行域它的一个整数坐标的顶点恰好是问题的最优解。,割平面法的步骤,求松弛问题的 最优基可行解,例题：用割平面法求解下列整数规划,x1 +0.5 x2 4.5,2x1 + 3 x2 14,x1, x20,且均取整数值,第1步.去掉整数约束找出松弛问题，若约束条件系数和右边常数不是整数，则必须化为整数（保证所添加的松弛变量均为整数）；,2x1 + x2 9,2x1 + 3 x2 14,x1, x20,G0,单纯形法求解松弛问题G0，

7、得到最终单纯形表：,因最优解不是整数解 需引入附加约束条件,找出非整数解变量中分数部分最大的一个基变量，并写出该行在最终表中的约束方程,将上式所有常数分写成整数与正分数之和：,分数移项到右端，整数项到左端：,根据右端为整数且变量非负的要求，得到：,即：,加上松弛变量之后得到,第2步.寻找割平面方程；,第3步.在最优单纯形表中求解增加约束条件后的LP问题的最优解；,应用对偶单纯形法迭代计算最优解,出基,入基,第3步.在最优单纯形表中求解增加约束条件后的LP问题的最优解；,最优解仍为非整数解 继续寻找Gomory约束,写出该行在最终表中的约束方程,将上式所有常数分写成整数与正分数之和：,分数移项到

8、右端，整数项到左端：,根据右端为整数且变量非负的要求，得到：,加上松弛变量之后得到,最优解仍为非整数解 继续寻找Gomory约束,上述过程找到的两个割平面方程用决策变量表示分别为：,切割过程如图。,使切割后的可行域的一个整数坐标的顶点恰好是问题的最优解。,确定割平面方程的练习:,第四章整数规划与分配问题,整数规划的特点及作用 分枝定界法 割平面法 分配问题与匈牙利法 应用举例,Integer Programming,简称IP,分配问题的提出【指派问题】,若干项工作或任务需要若干个人去完成。由于每人的知识、能力、经验的不同，故各人完成不同任务所需要的时间不同（或其他资源）。 问应指派哪个人完成何

9、项工作，可使完成所有工作所消耗的总资源最少？,设某公司准备派n个工人x1, x2, xn,去作n件工作y1, y2, , yn. 已知工人xi完成工作yj所需时间为cij (i,j=1,2,n). 现问：如何确定一个分派工人去工作的方案，使得工人们完成工作的总时间为最少？,标准形式的分配问题,分派方案满足下述两个条件：,任一个工人都不能去做两件或两件以上的工作 任一件工作都不能同时接受两个及以上的工人去做,设某公司准备派n个工人x1, x2, xn,去作n件工作y1, y2, , yn. 已知工人xi完成工作yj所需时间为cij (i,j=1,2,n). 现问：如何确定一个分派工人去工作的方案

10、，使得工人们完成工作的总时间为最少？,标准形式的分配问题,n个人 n件事,每件事必有且只有一个人去做,每个人必做且只做一件事,数学模型,n个人 n件事,cij：第i人做第j事的费用,总费用：,i，j1, ., n,j1,.,n,i1,.,n,每件事必有且只有一个人去做,每个人必做且只做一件事,时间、原料、金钱等资源,数学模型,线性规划问题,运输问题,0-1型整数规划问题,匈牙利法,1955年由美国数学家W.W.kuhn(库恩)提出，利用了匈牙利数学家D.Konig(康尼格)证明的2个定理。,系数矩阵 (效率矩阵),解矩阵 (决策变量矩阵),n个人 n件事,定义：在系数矩阵C中，处在不同行不同列

11、的一组零元素，称为独立零元素组，其中每个元素称为独立零元素。,最优解,定理：若将分配问题系数矩阵的每一行及每一列分别减去各行及各列的最小元素，则新分配问题与原分配问题有相同的最优解，只有最优值差一常数。,相关定理,使每行每列 都出现零元素,步骤1：变换系数矩阵，使其每行每列都出现0元素 把各行元素分别减去本行元素的最小值，然后在此基础上再把每列元素减去本列中的最小值。,此时每行及每列中肯定都有0元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（1）逐行检验,对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标

12、记的零元素用记号/划去。,重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。,表示此人只能做该事 （此事只能由该人做）,表示此事已不能由 其他人来做 （此人已不能做其他事）,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,（1）逐行检验,对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号/划去。,重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。,（2）逐列检验,与行检验类似：对只有一个未标记的零元素的列，用记号O将该零元素圈起，然后将被圈起

13、的零元素所在行的其他未标记的零元素用记号/划去。,重复列检验，直到没有未被标记的零元素或至少有两个未被标记的零元素为止。,圈0即独立零元素,步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。,可能出现三种情况,1.每一行均有圈0出现，圈0的个数恰好等于n 2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,可能出现三种情况,2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,圈0个数等于n=5,多重最优解,可能出现三种情况,3.不存在未被标记过的零元素，但圈0的个数n,（3）判断独立零元素的个数,圈0个数4 n=5,定理：系数矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少线数。,例：分别求下列矩阵中的独立零元素的最多个数。,独立零元素 的个数最多：,对不含