运筹学《第五章 整数规划》

第五章整数规划整数规划的数学模型及其解的特点割平面法分支定界法0-1型整数规划指派问题1运筹学-整数规划第一节整数规划的数学模型及其解的特点1.1整数规划数学模型的一般形式要求一部分或全部决策变量必须取整数值的规划问题称为整数规划.不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数问题的松弛问题。特别的:由目标函数(1)和约束条件(2),(3),(4)构成的模型称为整数线性规划;由目标函数(1)和约束条件(2),(3)构成的模型称为该整数线性规划问题的松弛问题.松弛问题2运筹学-整数规划第一节整数规划的数学模型及其解的特点1.2整数线性规划问题的类型纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划.混合整数线性规划:指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划.0-1型整数线性规划:指决策变量只能取值0或1整数线性规划.3运筹学-整数规划第一节整数规划的数学模型及其解的特点1.2整数线性规划问题的类型纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划.混合整数线性规划:指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划.0-1型整数线性规划:指决策变量只能取值0或1整数线性规划.4运筹学-整数规划第一节整数规划的数学模型及其解的特点1.2整数线性规划问题的类型纯整数线性规划:指全部决策变量都必须取整数值的整数线性规划.混合整数线性规划:指决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划.0-1型整数线性规划:指决策变量只能取值0或1整数线性规划.5运筹学-整数规划第一节整数规划的数学模型及其解的特点1.3整数规划的例子例1某厂生产A、B两种产品，这两种产品的单位利润分别为25元和40元。生产每种产品都需要三道工序，其各种产品的工时(h)，每一工序每周可供使用的时间如下表，问工厂如何安排生产，使其获利最大？解：假设工厂每周应生产A种产品x1件，B种产品x2件，得到下面的数学模型纯整数规划问题6运筹学-整数规划第一节整数规划的数学模型及其解的特点1.3整数规划的例子例2某服务部门各时段(2小时一个时段)需要的服务人员见下表，按规定服务员连续工作8小时为一班,问在满足工作需要的条件下，如何安排使总服务员最少？解：假设xj表示j时段开始工作的服务员数,则有如下模型时段12345678最少人数10891113853纯整数规划问题7运筹学-整数规划第一节整数规划的数学模型及其解的特点1.3整数规划的例子例3现有资金总额为B,可供选择的投资项目有n个,项目j所需投资额和预期收益分别为aj和cj.此外,由于种种原因，有三个附加条件:1)若选择项目1,就必须同时选择项目2,反之不一定;2)项目3和4至少选择1个;3)项目5,6,7中恰好选择两个.应当怎样选择投资项目,才能使总预期收益最大？解:假设xj={1表示投资j项目;0表示不投资j项目}8运筹学-整数规划X1=1,x2=1X1=0,x2=1X1=0,x2=0第一节整数规划的数学模型及其解的特点1.3整数规划的例子例3现有资金总额为B,可供选择的投资项目有n个,项目j所需投资额和预期收益分别为aj和cj.此外,由于种种原因，有三个附加条件:1若选择项目1,就必须同时选择项目2,反之不一定;2项目3和4至少选择1个;3项目5,6,7中恰好选择两个.应当怎样选择投资项目,才能使总预期收益最大？解:假设xj={1表示投资j项目;0表示不投资j项目}9运筹学-整数规划第一节整数规划的数学模型及其解的特点1.3整数规划的例子例3现有资金总额为B,可供选择的投资项目有n个,项目j所需投资额和预期收益分别为aj和cj.此外,由于种种原因，有三个附加条件:1若选择项目1,就必须同时选择项目2,反之不一定;2项目3和4至少选择1个;3项目5,6,7中恰好选择两个.应当怎样选择投资项目,才能使总预期收益最大？解:假设xj={1表示投资j项目;0表示不投资j项目}X3=1,x4=1X3=1,x4=0X3=0,x4=110运筹学-整数规划X5=0,x6=1,x7=1X5=1,x6=1,x7=0X5=1,x6=0,x7=1第一节整数规划的数学模型及其解的特点1.3整数规划的例子例3现有资金总额为B,可供选择的投资项目有n个,项目j所需投资额和预期收益分别为aj和cj.此外,由于种种原因，有三个附加条件:1若选择项目1,就必须同时选择项目2,反之不一定;2项目3和4至少选择1个;3项目5,6,7中恰好选择两个.应当怎样选择投资项目,才能使总预期收益最大？解:假设xj={1表示投资j项目;0表示不投资j项目}0-1整数规划问题11运筹学-整数规划第一节整数规划的数学模型及其解的特点1.3整数规划的例子例4工厂A1和A2生产某种物资.由于该物资供不应求,需要再建一家工厂,相应的建厂方案有A3和A4.该物资需求地有B1,B2,B3,B4.各厂年生产能力,各地需求量及各厂到各地的单位运费如下表,另外,工厂A3或A4开工后,每年的生产费用估计为1200万或1500万,问建工厂A3还是A4所需的年总费用最少？B1B2B3B4产能A12934400A28357600A37612200A44525200需求量350400300150或12运筹学-整数规划B1B2B3B4产能A12x119x123

x134

x14400A28x213x225

x237

x24600A37

x316

x321x332x34200A44

x415

x422x435x44200需求量350400300150解:设xij表示从Ai运到Bj的物资量若用A3方案,则模型为或13运筹学-整数规划B1B2B3B4产能A12x119x123

x134

x14400A28x213x225

x237

x24600A37

x316

x321x332x34200A44

x415

x422x435x44200需求量350400300150解:设xij表示从Ai运到Bj的物资量若用A3方案,则模型为若用A4方案,则模型为或14运筹学-整数规划第一节整数规划的数学模型及其解的特点解:将两模型合并为一个模型,设y={1表示建A3;0表示建A4}当y=1时0+0+0+0=200*0000011000015运筹学-整数规划第一节整数规划的数学模型及其解的特点解:将两模型合并为一个模型,设y={1表示建A3;0表示建A4}混和整数规划问题当y=0时0+0+0+0=200*0000011000016运筹学-整数规划第一节整数规划的数学模型及其解的特点1.4整数规划解的特点能否对松弛问题最优解取整得到其对应的整数规划问题的最优解？例5考虑下面的整数规划：用图解法得松弛问题最优解为P(18/7,19/7)，取整有A1，A2，A3，A4四种结果。显然A1，A2非可行解，而A3，A4经计算不是最优解，事实上最优解是A*（4，2）。A*17运筹学-整数规划第一节目标规划问题及其数学模型能否用枚举法求整数规划最优解？0123456784567891010111218运筹学-整数规划第一节目标规划问题及其数学模型比如对于有n项任务的指派问题，不同得指派方案为n!种。n=10,有3628800种方案。n=20,有2×1018种方案。用每秒百万次的计算机，需要上万年时间计算出结果。能否用枚举法求整数规划最优解？目前采用的思路：将完全枚举法变成部分枚举法。分枝定界法------混合整数规划割平面法------纯整数规划隐枚举法------0-1规划匈牙利法------0-1规划19运筹学-整数规划第二节割平面法思路：针对整数规划问题的松弛问题，增加线性约束条件（割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解，该方法的核心在于如何找到合适的割平面（并非一次就能找到），使切割后最终得到这样的可行域：它的一个有整数坐标的顶点恰好就是问题的最优解。20运筹学-整数规划第二节割平面法思路：针对整数规划问题的松弛问题，增加线性约束条件（割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解，该方法的核心在于如何找到合适的割平面（并非一次就能找到），使切割后最终得到这样的可行域：它的一个有整数坐标的顶点恰好就是问题的最优解。割平面21运筹学-整数规划第二节割平面法割平面构造方法：对于纯整数规划问题设aij,bi均为整数,用单纯形法求其松弛问题的最优解,得到最终单纯形表,记Q为基变量下标的集合，K为非基变量下标集合,最终单纯形表中的约束可以表示为：22运筹学-整数规划cj21000θ0x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/223运筹学-整数规划第二节割平面法割平面构造方法：分解ai0j,bi为两部分.一部分为不超过该数的最大整数，另一部分为余下的小数：若b不为整数，其方程如下:代入上式移项得:24运筹学-整数规划第二节割平面法割平面构造方法：对于由于左边是整数,右边必然也是整数.而若必为小数,故必然有即割平面方程1958R.E.Gomory25运筹学-整数规划26运筹学-整数规划第二节割平面法例6用割平面法求解纯整数规划解：引入松弛变量x3,x4,x5,用单纯形法解其松弛问题，得最优单纯形表27运筹学-整数规划cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7构造割平面约束：引入松弛变量x6,得割平面方程：将该式代入上表为：28运筹学-整数规划cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7构造割平面约束：引入松弛变量x6,得割平面方程：将该式代入上表为：29运筹学-整数规划cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7构造割平面约束：引入松弛变量x6,得割平面方程：将该式代入上表为：30运筹学-整数规划cj3-10000θCBXBbx1x2x3x4x5x63x113/7101/702/70-1X29/701-2/703/700X431/700-3/7122/700x6-6/700-1/70-2/71cj-zj00-5/70-3/70用对偶单纯形法求解得：31运筹学-整数规划cj3-10000θCBXBbx1x2x3x4x5x63x11100001-1X25/4010-1/40-5/40X35/2001-1/20-11/20x57/40001/41-3/4cj-zj000-1/40-17/4构造割平面约束：引入松弛变量x7,得割平面方程：将该式代入上表为：32运筹学-整数规划cj3-10000θCBXBbx1x2x3x4x5x63x11100001-1X25/4010-1/40-5/40X35/2001-1/20-11/20x57/40001/41-3/4cj-zj000-1/40-17/4构造割平面约束：引入松弛变量x7,得割平面方程：将该式代入上表为：33运筹学-整数规划cj3-100000θCBXBbx1x2x3x4x5x6x73x111000010-1X25/4010-1/40-5/400X35/2001-1/20-11/200x57/40001/41-3/400x7-3/4000-1/40-1/41cj-zj000-1/40-17/40用对偶单纯形法求解得：34运筹学-整数规划cj3-100000θCBXBbx1x2x3x4x5x6x73x111000010-1X2201000-100X3400100-5-20X5100001-110X43000101-4cj-zj00000-4-1得最优解x=(1,2,4,3,1,0,0)T,最优值为3-2=135运筹学-整数规划36运筹学-整数规划37运筹学-整数规划x1=1,x2=238运筹学-整数规划第三节分支定界法思路：设有最大化的整数规划问题I，与它相应的线性规划问题为S。从解问题S开始，若其最优解不符合I的整数条件，那么S的最优目标函数是I的最优目标函数的上界，而I的任意可行解的目标函数值是I最优值得下界，通过将S的可行域分成子区域的方法，逐步增加下界值，减小上界值，从而求出最优值。39运筹学-整数规划第三节分支定界法································松弛问题S0整数规划问题I0若S0最优解为整数,则该解也是I0的最优解.否则S0最优解为I0的最优解的上界.可以进行分支.40运筹学-整数规划第三节分支定界法································S1I1S2I2若S1的最优解不是整数,对S1进行分支,否则可以把该最优解作为I0的一个下界.z0z141运筹学-整数规划第三节分支定界法································S1I1S2I2z0z1若S2的最优解不是整数,对S2进行分支,否则可以把该最优解作为I0的一个下界.42运筹学-整数规划例7求解第三节分支定界法(I)(S)43运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s44运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s245运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S146运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3C47运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3CS248运筹学-整数规划第三节分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9B49运筹学-整数规划Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S2150运筹学-整数规划Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S21x1=33/14x2=2z=61/1451运筹学-整数规划Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S21x1=33/14x2=2z=61/14S22无解52运筹学-整数规划Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21CS2x1=2x2=23/9z=41/9Bx2≦2S21x1=33/14x2=2z=61/14S1x1=1x2=7/3z=10/353运筹学-整数规划As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S21154运筹学-整数规划As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4D55运筹学-整数规划As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4Dx1≧3S21256运筹学-整数规划As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4Dx1≧3S212x1=3x2=1z=4s212E求最小化的例子s1的松弛问题最优解小于整数问题解得下限457运筹学-整数规划解：首先不考虑整数约束，相应的问题称为原问题的松驰问题松驰问题（0）用单纯形法求得其最优解为x1=2.5，x2=2.5，z=87.5其求解框图如下：例58运筹学-整数规划问题（0）x1=2.5，x2=2.5z=87.5问题（1）x1=2，x2=2.67z=83.3问题（2）x1=3，x2=1.75z=80问题（3）x1=2，x2=2z=70问题（4）x1=1，x2=3z=75问题（5）x1=3.5，x2=1z=72.5问题（6）无可行解59运筹学-整数规划分支定界法的步骤将要求解的整数规划问题称为A问题，将与它相应的线性规划问题称为B问题60运筹学-整数规划分支定界法的步骤将要求解的整数规划问题称为A问题，将与它相应的线性规划问题称为B问题61运筹学-整数规划例8厂址选择问题

。在5个地点中选3处建生产同一产品的工厂，在这5个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表所示，现在有总投资800万元，占用农田指标60亩，应如何选择厂址，使建成后总生产能力最大。第四节0-1型整数规划一、0-1变量及其应用地点12345所需投资（万元）320280240210180占用农田（亩）201815118生产能力（万吨）7055422811解：设五个0—1变量x1，x2，x3，x4，x5，其中i=1,2,3,4,562运筹学-整数规划第四节0-1型整数规划地点12345所需投资（万元）320280240210180占用农田（亩）201815118生产能力（万吨）70554228118006063运筹学-整数规划例9含有相互排斥的约束条件的问题

。某厂生产A1，A2两种产品，需要经过B1，B2，B3三道工序加工。单件工时和利润以及各个工序每周工时限额见下表，问工厂应如何安排生产，才能使总利润最大？第四节0-1型整数规划一、0-1变量及其应用B1B2B31B32利润A10.30.20.30.225A20.70.10.50.440工时限额(h/周)250100150120

解：设该工厂分别生产A1,A2产品x1,x2件，当分别采用工序B31,B32时，所得线性规划模型为：64运筹学-整数规划B1B2B31B32利润A10.30.20.30.225A20.70.10.50.440工时限额(h/周)250100150120

x1x2B31B3265运筹学-整数规划B31B3266运筹学-整数规划若y1=067运筹学-整数规划若y1=068运筹学-整数规划若y2=069运筹学-整数规划若y2=070运筹学-整数规划例10固定费用问题有三种资源被用于生产三种产品，资源量、产品单价可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表,要求制定一个生产计划使总收益最大.第四节0-1型整数规划一、0-1变量及其应用IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价8101271运筹学-整数规划IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012若设生产产品I,II,III分别x1,x2,x3件72运筹学-整数规划IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012若x1>0,x2>0,x3>0设生产产品I,II,III分别x1,x2,x3件若x1=0,x2>0,x3>073运筹学-整数规划IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价81012若x1>0,x2=0,x3>0设生产产品I,II,III分别x1,x2,x3件若x1>0,x2>0,x3=074运筹学-整数规划设生产产品I,II,III分别x1,x2,x3件75运筹学-整数规划例11变量之间需要满足一定的逻辑关系的问题

一个工厂用三种设备生产5种产品，三种设备的总能力（小时），生产每种产品需要占用的各种设备的能力（小时/件）以及三种产品的利润（元/件）如下表所示第四节0-1型整数规划一、0-1变量及其应用产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722求使利润最大的生产方案(产品为整数)76运筹学-整数规划产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722解:设生产产品1-5分别为xi(i=1-5)件.77运筹学-整数规划产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722五种产品中，安排生产的产品不能超过三种78运筹学-整数规划产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722每一种产品如果生产，最小批量为50件

79运筹学-整数规划产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722如果产品1安排生产，产品2就不能生产

80运筹学-整数规划产品1产品2产品3产品4产品5设备能力（小时）设备A513241,800设备B－34152,500设备C321322,200利润（元/件）2418211722如果产品4安排生产，产品5必须生产，而且至少生产50件81运筹学-整数规划练习：说明如何用0-1整数变量将下列条件表示为线性约束1）或者x1+x2≤2或者2x1+3x2≥8x1+x2-2≤My8-2x1-3x2≤M(1-y)y=0,1M为充分大的正数2）变量x3只能取0，5，9，12x3=5y1+9y2+12y3y1+y2+y3≤1yi=0,182运筹学-整数规划练习：说明如何用0-1整数变量将下列条件表示为线性约束3）若x4≤4,则x5≥6，否则x5≤3本题相当于x4≤4,x5≥6

或x4>4,则x5≤3x4-4≤My6-x5≤My4-x4<M(1-y)x5-3≤M(1-y)4）下列四个约束至少必须满足两个x6+x7≤2,x6≤1,x7≤5,x6+x7≥3x6+x7-2≤My1x6-1≤My2x7-5≤My33-x6-x7≤My4y1+y2+y3+y4≤2yi=0表示满足该约束83运筹学-整数规划例12求解0-1整数规划

第四节0-1型整数规划二、0-1整数规划的解法隐枚举法84运筹学-整数规划(x1,x2,x3)Z约束条件1234过滤条件0,0,00,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一组可行解(x1,x2,x3)=(0,0,1),Z=5,将z≥5作为过滤条件z≥585运筹学-整数规划(x1,x2,x3)Z约束条件1234过滤条件0,0,000,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一组可行解(x1,x2,x3)=(0,0,1),Z=5,将z≥5作为过滤条件z≥55√√√√-2338√√√√z≥816最优解为(x1,x2,x3)=(1,0,1),最优值z=886运筹学-整数规划例

求解0-1整数规划

87运筹学-整数规划(x2,x1,x4,x3)Z约束条件123过滤条件0,0,0,000,0,0,1-10,0,1,010,0,1,100,1,0,030,1,0,120,1,1,040,1,1,131,0,0,071,0,0,161,0,1,081,0,1,171,1,0,0101,1,0,191,1,1,0111,1,1,110(1)(2)(3)任意取一组可行解(x1,x2,x3,x4)=(1,0,1,1),Z=3,将z≤3作为过滤条件z≤

3×√√√√×××√×√×88运筹学-整数规划(x2,x1,x3)Z约束条件1234过滤条件0,0,000,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一组可行解(x1,x2,x3)=(0,0,1),Z=5,将z≥5作为过滤条件z≥55√√√√38-23√√√√z≥816最优解为(x1,x2,x3)=(1,0,1),最优值z=889运筹学-整数规划第五节指派问题一、指派问题的标准形式及其数学模型指派问题的定义:n个人来完成n件事,每个人必须完成一件事情,每件事情必须有一个人来完成.已知第i人做第j事的费用为cij(i,j=1,2,…n),要求确定人和事之间的一一对应的指派方案，使完成这n件事情的总费用最少.称C为指派问题的效率(价值)系数矩阵.90运筹学-整数规划第五节指派问题指派问题的模型指派问题解矩阵每行有且只有一个1每列有且只有一个191运筹学-整数规划第五节指派问题例13某商业公司计划开办5家商店.为了尽早建成营业,商业公司决定由5家建筑公司分别承建.已知建筑公司Ai(i=1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价为cij(i,j=1,2,…,5),问商业公司应当对5家建筑公司怎样分配建造任务才能使总的建造费用最少.B1B2B3B4B5A14871512A279171410A3691287A46714610A5691210692运筹学-整数规划第五节指派问题例13某商业公司计划开办5家商店.为了尽早建成营业,商业公司决定由5家建筑公司分别承建.已知建筑公司Ai(i=1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价为cij(i,j=1,2,…,5),问商业公司应当对5家建筑公司怎样分配建造任务才能使总的建造费用最少.该问题模型为:93运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤1

变换系数矩阵.先对各行元素分别减去本行中的最小元素,再对各列元素减去本列中的最小元素。-4-7-6-6-694运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤1

变换系数矩阵.先对各行元素分别减去本行中的最小元素,再对各列元素减去本列中的最小元素。-1-395运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤1

变换系数矩阵.先对各行元素分别减去本行中的最小元素,再对各列元素减去本列中的最小元素。96运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤2

在变换后的系数矩阵中确定独立零元素。若独立零元素有n个,则已得出最优解;若少于n个,则作能覆盖所有零元素的最少直线数目的直线集合.定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。97运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.作能覆盖所有零元素的最少直线数目的直线集合.1对没有的行打√√2在已打√的行中对所在列打√.0√3在已打√的列中对所在行打√.重复2和3直到再也找不到可以打√的行或列.√4对没有打√的行画一横线,对打√的列画一竖线,得到覆盖所有零元素的最少直线数目。98运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤3

继续变换系数矩阵.在未被直线覆盖的元素中找出一个最小元素,对未被直线覆盖的行均减去该元素,被直线覆盖的列均加上该元素。(未被直线覆盖的数字减去最小值，交叉数字加最小值)√√√066212101001199运筹学-整数规划第五节指派问题二、匈牙利解法

1955年,库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Konig)的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，习惯上称之为匈牙利算法.步骤3

继续变换系数矩阵.在未被直线覆盖的元素中找出一个最小元素,对未被直线覆盖的行均减去该元素,被直线覆盖的列均加上该元素。返回步骤2100运筹学-整数