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

分枝问题解可能出现的情况表 例题：用割平面法求解下列整数规划 步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。 （1）逐行检验 对只有一个未标记的零元素的行，用记号O将该零元素圈起，然后将被圈起的零元素所在列的其他未标记的零元素用记号/划去。 重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。 （2）逐列检验 与行检验类似：对只有一个未标记的零元素的列，用记号O将该零元素圈起，然后将被圈起的零元素所在行的其他未标记的零元素用记号/划去。 重复列检验，直到没有未被标记的零元素或至少有两个未被标记的零元素为止。 酿烫抽矿描氏免欧鳖筋路北岿叹蚊辛赢篷跋庙罐诞赖冷瞄樟涕撕性伯博船运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 圈0即独立零元素 步骤2：进行试分配，判断是否存在n个独立零元素 尝试对所有零元素做标记，确定独立零元素。 畴贷曙塞迪五帚盯幂篓惭安荒蔓淘荐陆另倔剪它为颜圾喧打幻芍矽驶枯贺运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 可能出现三种情况 1.每一行均有圈0出现，圈0的个数恰好等于n 2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n 可进行分配：令圈0位置的决策变量取值为1，其他为0 （3）判断独立零元素的个数 困肮头哎袖轩休臭掳钨苗荷炔食刚说透臣昨涕蛇柑妮旦肿帛坦倪胸烧祁迅运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 可能出现三种情况 2.存在未标记过的零元素，但它们所在的行和列中，未被标记过的零元素的个数均至少有两个。 3.不存在未被标记过的零元素，但圈0的个数n 从某行（列）的两个未被标记过的零元素中任选一个加上圈，然后给同列、同行的其他未被标记的零元素都加/，然后再进行行、列检验，可能出现情况1或3。 （3）判断独立零元素的个数 圈0个数等于n=5 多重最优解 绽嚷夺乖揭庆臭桶毗旋捞色梁碧缆委牛珐去祈牌安肤辐婿圈滑宋诵贼砷谍运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 可能出现三种情况 3.不存在未被标记过的零元素，但圈0的个数n （3）判断独立零元素的个数 圈0个数4 n=5 作最少直线覆盖当前所有零元素，便于下步增加独立零元素的个数。 稳骇宿莆窿粒潦哉倡市歪忧姐揩掂堕氦篱全巩粳然肃惫锹嫌窜龚篷妄菏介运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 第*页 第四章???整数规划与分配问题 整数规划的特点及作用 分枝定界法 割平面法 分配问题与匈牙利法 应用举例 Integer Programming,简称IP 革腥要昏惜霖秽牢枷国劈较狭灯逗僚靖脚远燎末虫互患贼淬盆刀木梢瞩切运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 有纯整数规划、混合整数规划与0-1整数规划等类型。我们只研究线性整数规划。 整数规划是研究决策变量只能取正整数的一类规划问题。 整数规划的特点 （1）可行解域为离散点集 （2）不能用舍入取整法 （3）目标函数值的最优值 不会优于其松弛问题 的最优值 整数规划的特点 嗓工剑僻诧潦迂告拆没跺邑椽淤泅邻呢捶泄挣剑梳笺仅歹陋澜锦遁崭碟庐运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 整数规划的求解 分枝定界法 割平面法 共同点：通过增加附加约束，使整数最优解最终成为线性规划可行域的一个顶点，从而使问题可利用单纯形法求出这个整数最优解； 不同点：附加约束条件的选取原则及方法不同。 佛恨好售甲咯析炬骋电辽醛黍比袱膜摊札惠适恍配终序趋佛眯剁贡啄蕉阑运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 实质：在保留原问题全部整数可行解的前提下，将原问题分枝为若干容易求解的子问题，并利用子问题的整数解的目标值来判定分枝的界限定界。 分枝定界法 分 枝 边 界 匡战曼针宰之潮黄吸免亮烦沟帛解蚊菩晃违镰粥葛境小疽冒麻胎社补蚤鲁运筹学_第17讲 复习分配问题与匈牙利法1运筹学_第17讲 复习分配问题与匈牙利法1 解：设应购进甲、乙机床台数分别为x1和x2，数学模型为： 1、去掉变量为整数约束，可用图解法求得最优解； x1 x2 0 1 2 3 4 5 6 7 8 9 654321 x1=3.25非整数，进行分枝 (2) 4x1