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