《运筹学第17讲复习分配问题与匈牙利法.ppt》由会员分享，可在线阅读，更多相关《运筹学第17讲复习分配问题与匈牙利法.ppt（39页珍藏版）》请在金锄头文库上搜索。
1、第第1页页第四章第四章整数规划与分配问题整数规划与分配问题整数规划的特点及作用整数规划的特点及作用分枝定界法分枝定界法割平面法割平面法分配问题与匈牙利法分配问题与匈牙利法应用举例应用举例 IntegerProgramming,简称简称IP第第2页页有有纯纯整整数数规规划划、混混合合整整数数规规划划与与0-1整整数数规规划划等等类类型型。我我们只研究们只研究线性整数规划线性整数规划。整数规划是研究整数规划是研究决策变量只能取正整数决策变量只能取正整数的一类规划问题。的一类规划问题。整数规划的特点整数规划的特点（1 1）可行解域为离散点集）可行解域为离散点集（2 2）不能用舍入取整法）不能用舍入取
2、整法（3 3）目标函数值的最优值）目标函数值的最优值 不会优于其不会优于其松弛问题松弛问题 的最优值的最优值整数规划的特点整数规划的特点第第3页页整数规划的求解整数规划的求解1.1.分枝定界法分枝定界法2.2.割平面法割平面法共共同同点点：通通过过增增加加附附加加约约束束，使使整整数数最最优优解解最最终终成成为为线线性性规规划划可可行行域域的的一一个个顶顶点点，从从而而使使问问题题可可利利用用单单纯纯形法求出这个整数最优解；形法求出这个整数最优解；不同点：不同点：附加约束条件的选取原则及方法不同。附加约束条件的选取原则及方法不同。第第4页页实实质质：在在保保留留原原问问题题全全部部整整数数可可
3、行行解解的的前前提提下下，将将原原问问题题分分枝枝为为若若干干容容易易求求解解的的子子问问题题，并并利利用用子子问问题题的的整数解的目标值来判定分枝的界限整数解的目标值来判定分枝的界限。分枝定界法分枝定界法分分 枝枝边边 界界第第5页页解：设应购进甲、乙机床台数分别为解：设应购进甲、乙机床台数分别为x1和和x2，数学模型为：，数学模型为：1 1、去去掉掉变变量量为为整整数数约约束束，可可用图解法求得最优解；用图解法求得最优解；x1x201 2 3 4 5 6 7 8 9654321x1=3.25非整数，进行分枝非整数，进行分枝(2) 4x1+2x2=18(1) 2x1+3x2=14(3.25,
4、2.5)TX(0)=(x1,x2)T=(3.25,2.5)TZ(0)=14.75【例例】某某厂厂拟拟购购进进甲甲、乙乙两两类类机机床床生生产产新新产产品品。已已知知两两类类机机床床进进价价分分别别为为2万万元元和和3万万元元，安安装装占占地地面面积积分分别别为为4m2和和2m2，投投产产后后的的收收益益分分别别为为3百百元元/日日和和2百百元元/日日。厂厂方方仅仅有有资资金金14万万元元，安安装装面面积积18m2，为使收益最大，厂方应购进甲、乙机床各多少台？为使收益最大，厂方应购进甲、乙机床各多少台？第第6页页x1=3.25非整数，进行分枝非整数，进行分枝2 2、得两个子问题的数学模型、得两个
5、子问题的数学模型: : 子问题子问题(1) (1) 子问题子问题(2)(2) 分别用图解法求得最优解分别用图解法求得最优解 X(1)=(3,2.67)T,Z(1)=14.33X(2)=(4,1)T,Z(2)=14子问题子问题1x1x201 2 3 4 5 6 7 8 9654321(2)(1)子问题子问题2(4,1)Z(1)Z(2)=14子问题子问题2 2停止分枝，其整数解作为停止分枝，其整数解作为界界；子问题子问题1 1对对x2=2.67进行分枝进行分枝第第7页页 子问题子问题(3) (3) 子问题子问题(4)(4)x1x201 2 3 4 5 6 7 8 9654321(3)(0)子问题子
6、问题3子问题子问题4(1)(2)(4)子问题子问题(1)(1)Z(1)Z(2)=14子问题子问题2 2停止分枝，其整数解作为停止分枝，其整数解作为界界；子问题子问题1 1对对x2=2.67进行分枝进行分枝 分别用图解法求得最优解分别用图解法求得最优解 X(3)=(3,2)T,Z(3)=13X(4)=(2.5,3)T,Z(4)=13.5Z(3)Z(2);Z(4)Z(2)第第8页页 子问题子问题(3) (3) 子问题子问题(4)(4)子问题子问题(1)(1)Z(1)Z(2)=14子问题子问题2 2停止分枝，其整数解作为停止分枝，其整数解作为界界；子问题子问题1 1对对x2=2.67进行分枝进行分枝
7、 分别用图解法求得最优解分别用图解法求得最优解 X(3)=(3,2)T,Z(3)=13X(4)=(2.5,3)T,Z(4)=13.5Z(3)Z(2);Z(4)Z(2)最优解：最优解：X*=X(2)=(4,1)T最优值：最优值：Z*=14第第9页页问题(0)x1=3.25,x2=2.5Z(0)=14.75问题(4)x1=2.5,x2=3Z(4)=13.5问题(3)x1=3,x2=2Z(3)=13问题(1)x1=3,x2=8/3Z(1)=14.33问题(2)x1=4,x2=1Z(2)=14添加x23添加x13添加x22添加x14第第10页页分枝问题解可能出现的情况表分枝问题解可能出现的情况表情况情
8、况2,4,5找到最优解找到最优解情况情况3在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情情况况6中中问问题题1的的整整数数解解作作为为界界被被保保留留，用用于于以以后后与与问问题题2的后续分的后续分枝枝所得到的解进行比较所得到的解进行比较，结论如情况，结论如情况4或或5第第11页页割平面法割平面法 割割平平面面法法的的基基础础仍仍然然是是用用解解线线性性规规划划的的方方法法去去解解整整数数规规划划问问题题：首首先先不不考考虑虑变变量量为为整整数数这这一一条条件件，但但增增加加线线性性约约束束条条件件（Gomory约约束束，称称为为割割平平面面），使使得得原原可可行行解解域域中中切切掉掉
9、一一部部分分，这这部部分分只只包包含含非非整整数数解解，但但没没切切割割掉掉任任何何整整数数可可行行解解，切除的结果使整数解可能成为顶点切除的结果使整数解可能成为顶点。 分分枝枝定定解解法法是是对对原原问问题题可可行行解解域域进进行行了了切切割割，切切割割方方法法是是对对取取非非整整数数解解相相邻邻的的整整数数作作附附加加约约束束，约约束束方方程程简简单单，但但子子问题由于分枝的增多而成指数增长。问题由于分枝的增多而成指数增长。第第12页页割平面法割平面法 割割平平面面法法的的基基础础仍仍然然是是用用解解线线性性规规划划的的方方法法去去解解整整数数规规划划问问题题：首首先先不不考考虑虑变变量量
10、为为整整数数这这一一条条件件，但但增增加加线线性性约约束束条条件件（Gomory约约束束，称称为为割割平平面面），使使得得原原可可行行解解域域中中切切掉掉一一部部分分，这这部部分分只只包包含含非非整整数数解解，但但没没切切割割掉掉任任何何整整数数可可行行解解，切除的结果使整数解可能成为顶点切除的结果使整数解可能成为顶点。 关关键键：如如何何找找到到割割平平面面约约束束方方程程，使使切切割割后后最最终终得得到到这这样样的的可行域可行域它的一个整数坐标的顶点恰好是问题的最优解。它的一个整数坐标的顶点恰好是问题的最优解。第第13页页割平面法的步骤割平面法的步骤求求松弛问题松弛问题的的最优基可行解最优
11、基可行解判断是否判断是否为整数解为整数解否否在单纯形表中在单纯形表中加入加入一行一行利用利用对偶单纯对偶单纯形形算法求最优解算法求最优解是是停止停止得到最优解得到最优解附加约束附加约束利用具有利用具有最大最大分数部分分数部分的非整基变量的非整基变量第第14页页例题：用割平面法求解下列整数规划例题：用割平面法求解下列整数规划max z =3x1+2x2s.t. x1+0.5x2 4.52x1+3x214x1,x20,且均取整数值且均取整数值第第1 1步步. .去去掉掉整整数数约约束束找找出出松松弛弛问问题题，若若约约束束条条件件系系数数和和右右边边常常数数不不是是整数，则必须化为整数整数，则必须
12、化为整数（保证所添加的松弛变量均为整数）；（保证所添加的松弛变量均为整数）；max z =3x1+2x2s.t.2x1+x2 92x1+3x214x1,x20G0单纯形法求解松弛问题单纯形法求解松弛问题G0，得到最终单纯形表：得到最终单纯形表：因最优解不是整数解因最优解不是整数解需引入附加约束条件需引入附加约束条件第第15页页找找出出非非整整数数解解变变量量中中分分数数部部分分最最大大的的一一个个基基变变量，并写出该行在最终表中的约束方程量，并写出该行在最终表中的约束方程将上式所有常数分写成将上式所有常数分写成整数与正分数整数与正分数之和：之和：分数移项到右端，整数项到左端：分数移项到右端，整
13、数项到左端：根据右端为整数且变量非负的要求，得到：根据右端为整数且变量非负的要求，得到：即：即：加上松弛变量之后得到加上松弛变量之后得到Gomory约束约束第第2 2步步. .寻找割平面方程寻找割平面方程；第第16页页第第3 3步步. .在最优单纯形表中求解增加约束条件后的在最优单纯形表中求解增加约束条件后的LPLP问题的最优解问题的最优解；应用应用对偶单纯形对偶单纯形法法迭代计算最优迭代计算最优解解出基出基入基入基第第17页页第第3 3步步. .在最优单纯形表中求解增加约束条件后的在最优单纯形表中求解增加约束条件后的LPLP问题的最优解问题的最优解；最优解仍为非整数解最优解仍为非整数解继续寻
14、找继续寻找GomoryGomory约束约束第第18页页写出该行在最终表中的约束方程写出该行在最终表中的约束方程将上式所有常数分写成将上式所有常数分写成整数与正分数整数与正分数之和：之和：分数移项到右端，整数项到左端：分数移项到右端，整数项到左端：根据右端为整数且变量非负的要求，得到：根据右端为整数且变量非负的要求，得到：加上松弛变量之后得到加上松弛变量之后得到反映到最终单纯形表求最优解反映到最终单纯形表求最优解直到求出整数最优解直到求出整数最优解最优解仍为非整数解最优解仍为非整数解继续寻找继续寻找GomoryGomory约束约束第第19页页上述过程找到的上述过程找到的两个割平面方程两个割平面方
15、程用用决策变量决策变量表示分别为：表示分别为：切割过程如图。切割过程如图。x1x201 2 3 4 5 6 7 8 96543212x1+x2=92x1+3x2=14(3.25,2.5) 2x1+2x2=11(3.5,2)(4,1)x1+x2=5使切割后的可行域的一个使切割后的可行域的一个整数坐整数坐标的顶点标的顶点恰好是问题的最优解。恰好是问题的最优解。第第20页页确定割平面方程的练习确定割平面方程的练习:第第21页页第四章第四章整数规划与分配问题整数规划与分配问题整数规划的特点及作用整数规划的特点及作用分枝定界法分枝定界法割平面法割平面法分配问题与匈牙利法分配问题与匈牙利法应用举例应用举例
16、 IntegerProgramming,简称简称IP第第22页页分配问题的提出分配问题的提出【指派问题指派问题】若若干干项项工工作作或或任任务务需需要要若若干干个个人人去去完完成成。由由于于每每人人的的知知识识、能能力力、经经验验的的不不同同，故故各各人人完完成成不不同同任务所需要的时间不同（或其他资源）。任务所需要的时间不同（或其他资源）。问问应应指指派派哪哪个个人人完完成成何何项项工工作作，可可使使完完成成所所有有工作所工作所消耗的总资源最少消耗的总资源最少？设设某某公公司司准准备备派派n个个工工人人x1,x2,xn,去去作作n件件工工作作y1,y2,yn. 已已知知工工人人xi完完成成工
17、工作作yj所所需需时时间间为为cij (i,j=1,2,n).现现问问：如如何何确确定定一一个个分分派派工工人人去去工工作作的的方方案案，使使得得工人们完成工作的工人们完成工作的总时间为最少总时间为最少？第第23页页标准形式的分配问题标准形式的分配问题分派方案满足下述两个条件：分派方案满足下述两个条件：1.任一个工人都不能去做两件或两件以上的工作任一个工人都不能去做两件或两件以上的工作2.任一件工作都不能同时接受两个及以上的工人去做任一件工作都不能同时接受两个及以上的工人去做设设某某公公司司准准备备派派n个个工工人人x1,x2,xn,去去作作n件件工工作作y1,y2,yn. 已已知知工工人人x
18、i完完成成工工作作yj所所需需时时间间为为cij (i,j=1,2,n).现现问问：如如何何确确定定一一个个分分派派工工人人去去工工作作的的方方案案，使使得得工人们完成工作的工人们完成工作的总时间为最少总时间为最少？第第24页页标准形式的分配问题标准形式的分配问题n个人个人 n件事件事每件每件事事必有且只有一个人去做必有且只有一个人去做每个每个人人必做且只做一件事必做且只做一件事第第25页页数学模型数学模型n个人个人 n件事件事cij：第第i人做第人做第j事的费用事的费用xij1若指派第若指派第i人做第人做第j事事0若指派第若指派第i人不做第人不做第j事事总费用总费用：i，j1,.,nj1,.
19、,ni1,.,n每件每件事事必有且只有一个人去做必有且只有一个人去做每个每个人人必做且只做一件事必做且只做一件事时间、原料、时间、原料、金钱等资源金钱等资源第第26页页数学模型数学模型j1,.,ni1,.,ns.t.线性规划问题线性规划问题运输问题运输问题0-1型整数规划问题型整数规划问题第第27页页匈牙利匈牙利法法 19551955年年由由美美国国数数学学家家W.W.kuhnW.W.kuhn( (库库恩恩) )提提出出，利利用用了了匈牙利数学家匈牙利数学家D.KonigD.Konig( (康尼格康尼格) )证明的证明的2 2个定理。个定理。系数矩阵系数矩阵(效率矩阵效率矩阵)解矩阵解矩阵(决
20、策变量矩决策变量矩阵阵)n个人个人个人个人 n件事件事件事件事第第28页页定定义义：在在系系数数矩矩阵阵C中中，处处在在不不同同行行不不同同列列的的一一组组零零元元素素，称称为为独独立立零零元元素素组组，其其中中每每个个元元素素称称为为独立零元素独立零元素。最优解最优解第第29页页014丙丙085乙乙210甲甲CBA时时工工作作间间人员人员004丙丙075乙乙200甲甲CBA时时工工作作间间人员人员458丙丙4129乙乙987甲甲CBA时时工工作作间间人员人员定定理理：若若将将分分配配问问题题系系数数矩矩阵阵的的每每一一行行及及每每一一列列分分别别减减去去各各行行及及各各列列的的最最小小元元素
21、素，则则新新分分配配问问题题与与原原分分配配问题有问题有相同的最优解相同的最优解，只有最优值差一常数。，只有最优值差一常数。相关定理相关定理使每行每列使每行每列都出现零元素都出现零元素步骤步骤1：变换系数矩阵，使其每行每列都出现变换系数矩阵，使其每行每列都出现0元素元素把把各各行行元元素素分分别别减减去去本本行行元元素素的的最最小小值值，然然后后在在此此基基础础上上再把每再把每列列元素减去本列中的最小值。元素减去本列中的最小值。此时每行及每列中肯定都有此时每行及每列中肯定都有0元素元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试
22、对所有零元素做标记标记，确定确定独立零元素独立零元素。（1）逐）逐行行检验检验对对只只有有一一个个未未未未标标标标记记记记的的零零元元素素的的行行，用用记记号号O将将该该零零元元素素圈圈起起，然然后后将将被圈起的零元素所在列被圈起的零元素所在列的其他的其他未标记的零元素未标记的零元素用用记号记号/划去。划去。重重复复行行检检验验，直直到到每每一一行行都都没没有有未未被被标标记记的的零零元元素素或或至至少少有有两两个个未未被标记被标记的零元素为止。的零元素为止。表示此人只能做该表示此人只能做该事事（此事只能由该人（此事只能由该人做做）表示此事已不能由表示此事已不能由其他人来做其他人来做（此人已不
23、能做其他（此人已不能做其他事事）第第32页页步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记，确定确定独立零元素独立零元素。（1）逐）逐行行检验检验对对只只有有一一个个未未未未标标标标记记记记的的零零元元素素的的行行，用用记记号号O将将该该零零元元素素圈圈起起，然然后后将将被圈起的零元素所在列被圈起的零元素所在列的其他的其他未标记的零元素未标记的零元素用用记号记号/划去。划去。重重复复行行检检验验，直直到到每每一一行行都都没没有有未未被被标标记记的的零零元元素素或或至至少少有有两两个个未未被标记被标记的零元素为
24、止。的零元素为止。（2）逐）逐列列检验检验与与行行检检验验类类似似：对对只只有有一一个个未未标标记记的的零零元元素素的的列列，用用记记号号O将将该该零零元元素素圈圈起起，然然后后将将被被圈圈起起的的零零元元素素所所在在行行的的其其他他未未标标记记的的零零元元素素用用记号记号/划去。划去。重重复复列列检检验验，直直到到没没有有未未被被标标记记的的零零元元素素或或至至少少有有两两个个未未被被标标记记的的零元素为止。零元素为止。第第33页页圈圈0即独立零元素即独立零元素步骤步骤2：进行试分配，判断是否存在进行试分配，判断是否存在n个独立零元素个独立零元素 尝试对所有零元素做尝试对所有零元素做标记标记
25、，确定确定独立零元素独立零元素。可能出现三种情况可能出现三种情况1.每一行均有圈每一行均有圈0出现，圈出现，圈0的个数恰好等于的个数恰好等于n2.存存在在未未标标记记过过的的零零元元素素，但但它它们们所所在在的的行行和和列列中中，未未被被标标记过的零元素的个数均至少有两个。记过的零元素的个数均至少有两个。3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n可进行分配：令可进行分配：令圈圈0位置的决策变量取值位置的决策变量取值为为1，其他为，其他为0（3）判断）判断独立零元素独立零元素的个数的个数第第35页页可能出现三种情况可能出现三种情况2.存存在在未未标标记记过过
26、的的零零元元素素，但但它它们们所所在在的的行行和和列列中中，未未被被标标记过的零元素的个数均至少有两个。记过的零元素的个数均至少有两个。3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n从从某某行行（列列）的的两两个个未未被被标标记记过过的的零零元元素素中中任任选选一一个个加加上上圈圈，然然后后给给同同列列、同同行行的的其其他他未未被被标标记记的的零零元元素素都都加加/，然然后后再再进行行、列检验，可能出现情况进行行、列检验，可能出现情况1或或3。（3）判断）判断独立零元素独立零元素的个数的个数圈圈0个数个数等于等于n=5多重最优解多重最优解第第36页页可能出现三
27、种情况可能出现三种情况3.不存在未被标记过的零元素，但圈不存在未被标记过的零元素，但圈0的个数的个数n（3）判断）判断独立零元素独立零元素的个数的个数圈圈0个数个数4n=5作作最最少少直直线线覆覆盖盖当当前前所所有有零零元元素素，便便于下步增加独立零元素的个数。于下步增加独立零元素的个数。定定理理：系系数数矩矩阵阵C中中独独立立零零元元素素的的最最多多个个数数等等于于能能覆覆盖所有零元素的盖所有零元素的最少线数最少线数。由匈牙利数学家由匈牙利数学家D.Konig(康尼格康尼格)所证明所证明例例：分别求下列矩阵中的独立零元素的最多个数。：分别求下列矩阵中的独立零元素的最多个数。44独立零元素独立
28、零元素的个数最多：的个数最多：对对不含圈不含圈0的行打的行打；在打在打的行中，对所有零元素所在的行中，对所有零元素所在列列打打；在所有打在所有打的列中，对圈的列中，对圈0所在所在行行打打；重复重复2,3步，直到不能步，直到不能打打为止。为止。对对未未打打的的每每一一行行画画一一横横线线，对对已已打打的的每每一一列列画画一纵线，即得到覆盖当前一纵线，即得到覆盖当前0元素的元素的最少直线最少直线集。集。第第39页页对对不含圈不含圈0的行打的行打；在打在打的行中，对所有零元素所在的行中，对所有零元素所在列列打打；在所有打在所有打的列中，对圈的列中，对圈0所在所在行行打打；重复重复2,3步，直到不能步，直到不能打打为止。为止。对对未未打打的的每每一一行行画画一一横横线线，对对已已打打的的每每一一列列画画一纵线，即得到覆盖当前一纵线，即得到覆盖当前0元素的元素的最少直线最少直线集。集。圈圈0个数个数4n=5
