运筹学第5章：整数规划

1、整数规划及其数学模型整数规划及其数学模型分枝定界法分枝定界法割平面法割平面法0-1整数规划整数规划指派问题指派问题WinQSB软件应用软件应用第五章第五章 整数规划整数规划 (Integer Programming) 第一节第一节 整数规划及其数学模型整数规划及其数学模型在很多实际问题中，有些变量的取值必须是整数在很多实际问题中，有些变量的取值必须是整数在一个规划问题中，如果它的在一个规划问题中，如果它的某些变量（或全部某些变量（或全部变量）要求取整数变量）要求取整数，这个规划问题就称为，这个规划问题就称为整数规整数规划问题划问题，其中，其中v如果所有变量都取整数，就称为如果所有变量都取整数，

2、就称为纯整数规划或全整纯整数规划或全整数规划数规划v如果仅有一部分变量取整数，则称为如果仅有一部分变量取整数，则称为混合整数规划混合整数规划v 若变量值仅限于若变量值仅限于0 0或或1 1，则称为，则称为0-10-1规划规划一、问题的提出一、问题的提出在整数规划问题中，不考虑整数要求，由其他在整数规划问题中，不考虑整数要求，由其他约束条件和目标函数构成的规划问题称为该整约束条件和目标函数构成的规划问题称为该整数规划问题的数规划问题的松弛问题松弛问题。若松弛问题是一个线性规划问题，则其对应的若松弛问题是一个线性规划问题，则其对应的整数规划问题称为整数规划问题称为整数线性规划（整数线性规划（ILP

3、）。本章所讨论的整数规划都是指整数线性规划。本章所讨论的整数规划都是指整数线性规划。 （一）下料问题（一）下料问题【例【例5-1】某工地需要长度不同、直径相同的成套】某工地需要长度不同、直径相同的成套钢筋，每套钢筋由两根钢筋，每套钢筋由两根7米长和七根米长和七根2米长的钢筋米长的钢筋组成。现有组成。现有15米的圆钢毛坯米的圆钢毛坯150根，应如何下料根，应如何下料使废料最少？使废料最少？ 下料方式下料方式7 7米长的钢筋（根）米长的钢筋（根）2 2米长的钢筋（根）米长的钢筋（根）废料废料1 12 20 01 12 21 14 40 03 30 07 71 1 (二二)工厂选址问题工厂选址问题【

4、例【例5-35-3】工厂】工厂A1和和A2生产某种物资，由于该种物资供不应求，生产某种物资，由于该种物资供不应求，故需要再建一家工厂，相应的建厂方案有故需要再建一家工厂，相应的建厂方案有A3和和A4两个。这种物两个。这种物资的需求地有资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各地四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费年需求量、各厂至各需求地的单位物资运费cij（j=1,2,3,4）如如下表所示下表所示B1B2B3B4生产能力生产能力（千吨（千吨/年）年）A12934400A28357600A37612200A44525200需求量需求量（千吨（千吨/

5、年）年）350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后，每年的生产费用估计分别为12001200万元或万元或15001500万元。现要决定应该建设万元。现要决定应该建设A3还是还是A4，才能使今后每年的总，才能使今后每年的总费用最少。费用最少。( (三三) )投资问题投资问题【5-2】某投资公司可用于投资的资金是】某投资公司可用于投资的资金是B，可供，可供投资的项目有投资的项目有n个，项目个，项目j所需投资额和预期收益所需投资额和预期收益分别分别aj和和cj。同时，由于种种原因，有三个附加。同时，由于种种原因，有三个附加条件：条件：第一，若选择项目第一，若选

6、择项目1，就必须同时选择项目，就必须同时选择项目2，反，反之则不一定；之则不一定；第二，项目第二，项目3和项目和项目4中至少选择一个；中至少选择一个；第三，项目第三，项目5、项目、项目6和项目和项目7中恰好选择两个。中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？应当怎样选择投资项目，才能使总预期收益最大？整数规划数学模型的一般形式整数规划数学模型的一般形式且部分或全部为整数，或 n)21(j 0)21( )min(max11jnjijijnjjjxmibxaxcZZ 依照决策变量取整要求的不同，整数规划可分为纯依照决策变量取整要求的不同，整数规划可分为纯整数规划整数规划/ /全整

7、数规划、混合整数规划、全整数规划、混合整数规划、0 01 1整数规划整数规划二、整数规划模型的一般形式及解的特点二、整数规划模型的一般形式及解的特点且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ求解整数规划问题求解整数规划问题分析：考虑对应的线性规划问题分析：考虑对应的线性规划问题(LP)0,143292)(23max21212121xxxxxxLPxxZ整数规划解的性质整数规划解的性质3200CB XB b x1x2x3x40 x3921109/20 x414230114/2j32003200CB XB b x1x2x3x43x113/4103/4-1/

8、42x25/201-1/21/2j00-5/4-1/4用单纯形法解（用单纯形法解（如表所示如表所示），获得最优解），获得最优解初始表初始表最终表最终表可见，最优解为可见，最优解为x1=3.25 x2=2.5 z(0) =59/4=14.75变量不为整数，显然（变量不为整数，显然（LP）的最优解不是（）的最优解不是（IP）的最优解）的最优解 凑整凑整：(4, 3), (4, 2), (3, 3), (3, 2) (4, 3), (4, 2), (3, 3)均不可行均不可行 (3, 2)对应的目标函数值对应的目标函数值 z=13 但但(4, 1)对应的目标函数值对应的目标函数值 z=14可见，直接

9、凑整得到的解不见得是可行解；或者虽是可行可见，直接凑整得到的解不见得是可行解；或者虽是可行解，但不一定是最优解解，但不一定是最优解故需要对整数规划问题发展新的解法故需要对整数规划问题发展新的解法 分枝定界法分枝定界法 割平面法割平面法 分配问题的匈牙利法分配问题的匈牙利法 0-1规划的隐枚举法规划的隐枚举法0 x2 x1(a)(b)(5/3,5/2)第二节第二节 整数规划的解法整数规划的解法 分枝定界法分枝定界法且均为整数0,521023max2122121xxxxxxxz【例【例5-75-7】求解整数规划问题求解整数规划问题【思考【思考】（IPIP）的最优解是否会优于（）的最优解是否会优于（

10、LPLP）的最优解？）的最优解？（IPIP）的可行域与（）的可行域与（LPLP）可行域的关系如何？）可行域的关系如何？若（若（LPLP）有最优解，且其最优解为整数，则它是否也）有最优解，且其最优解为整数，则它是否也是（是（IPIP）的最优解？）的最优解？若（若（LPLP）有最优解，但其最优解不是整数，怎么办？）有最优解，但其最优解不是整数，怎么办？假设已知（假设已知（IPIP）的一个整数可行解，则（）的一个整数可行解，则（IPIP）的最优）的最优解与该解有怎样的关系？解与该解有怎样的关系？v 适用范围适用范围 全整数规划问题或混合整数规划问题全整数规划问题或混合整数规划问题v 本世纪本世纪60

11、60年代初由年代初由Land DoigLand Doig和和DakinDakin等人提出等人提出v 基本思路基本思路 设有最大化的整数规划问题设有最大化的整数规划问题(IP)，与它相应的线性规，与它相应的线性规划问题为划问题为(LP)松弛问题。从解松弛问题。从解(LP)开始，若其开始，若其最优解不符合整数条件，那么最优解不符合整数条件，那么(LP)的最优目标函数的最优目标函数必是必是(IP)最优解最优解z*的一个上界，记作的一个上界，记作z ;而而(IP)的任意的任意可行解的目标函数值将是可行解的目标函数值将是z*的一个下界的一个下界z 。分枝定界。分枝定界法就是将法就是将(LP)的可行域分成

12、子区域（分枝），逐步的可行域分成子区域（分枝），逐步减小减小z 和增大和增大z ，最终求得，最终求得z*的方法。的方法。【例【例5-75-7】且为整数且为整数)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考虑全整数规划问题：考虑全整数规划问题：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整数规划的松弛问题：整数规划的松弛问题：步骤：步骤： 1、先不考虑整数约束，解、先不考虑整数约束，解( IP )的松弛问题的松弛问题( LP )，可能，可能得到以下情况之一：得到以下情况之一： ( LP

13、 )没有最优解，则没有最优解，则( IP )也没有最优解，停止计算；也没有最优解，停止计算； 若若( LP )有最优解，并符合有最优解，并符合( IP )的整数条件，则的整数条件，则( LP )的的最优解即为最优解即为( IP )的最优解，停止计算；的最优解，停止计算； 若若( LP )有最优解，但不符合有最优解，但不符合( IP )的整数条件，转入下的整数条件，转入下一步。为讨论方便，设一步。为讨论方便，设( LP )的最优解为：的最优解为： 不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr 2、定

14、界：、定界： 记记( IP )的目标函数最优值为的目标函数最优值为Z* ,以以Z(0) 作为作为Z* 的上界，的上界，记为记为 Z(0) 。再用观察法找到一个整数可行解。再用观察法找到一个整数可行解 X，并，并以其相应的目标函数值以其相应的目标函数值 Z作为作为Z* 的下界，记为的下界，记为Z Z（取（取xj = 0），则有：），则有： Z Z* 。ZZ将这两个约束条件分别加入问题将这两个约束条件分别加入问题(IP) ，形成两个子问题，形成两个子问题(IP1)和和(IP2) ，再解这两个问题的松弛问题，再解这两个问题的松弛问题(LP1)和和(LP2) 。 3、分枝：分枝： 在在( LP )的最

15、优解的最优解X(0)中，任选一个不符合整数条件的中，任选一个不符合整数条件的变量，例如变量，例如xr= （不为整数），以（不为整数），以 表示不超过表示不超过 的的最大整数。构造两个约束条件最大整数。构造两个约束条件 xr 和和xr 1 1rbrbrbrbrb 4、修改上、下界：修改上、下界：( (按照以下两点规则进行按照以下两点规则进行) ) 在各分枝问题中，找出目标函数值最大者作为新在各分枝问题中，找出目标函数值最大者作为新的上界；的上界； 从已符合整数条件的分枝中，找出目标函数值最从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。大者作为新的下界。 5、比较与剪枝比较与剪枝 ：

16、 各分枝的目标函数值中，若有小于各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，者，则剪掉此枝，表明此子问题已经探清，不必再分枝了表明此子问题已经探清，不必再分枝了;否则继续分枝否则继续分枝 。 如此反复进行，直到得到如此反复进行，直到得到ZZ* 为止，即得最优解为止，即得最优解 X* Z3200CB XB b x1x2x3x40 x3921109/20 x414230114/232003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/200-5/4-1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,获得最优

17、解获得最优解初始表初始表最终表最终表可见，最优解为可见，最优解为x1=3.25 x2=2.5 z(0) =59/4=14.75且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ例例1、用分枝定界法求解整数规划问题、用分枝定界法求解整数规划问题选选 x2 进行分枝，即增加两个约束进行分枝，即增加两个约束x22 和和x2 3 ，则，则且且为为整整数数0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且为为整整数数0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分别在分别在(LP1)和和(LP2)中

18、引入松弛变量中引入松弛变量x5和和x6 ，将新加，将新加约束条件加入上表计算，即约束条件加入上表计算，即 x2+ x5= 2 , x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x520100100-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/2100-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝

19、，继续分枝，加入约束加入约束 x1 3, x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) z(3),故故x1=4, x2=1为最优解为最优

20、解 LP4树形图如下：树形图如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14例例2、用分枝定界法求解整数规划问题、用分枝定界法求解整数规划问题（图解法计算）（图解法计算）且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题0

21、,4 30 652 5min211212121xxxxxxxxxZ记为（记为（LP）用图解法求用图解法求（LP）的最优的最优解，如图所示解，如图所示x1x233(18/11,40/11)对于对于x118/111.64， 取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值取值x2 3 ，x2 4先将先将（LP）划分为（）划分为（LP1）和（）和（LP2）, ,取取x1 1, x1 2 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最小值的下限最小值的下限有下式：有下式：且且为为整整数数0,1 4 30 652 )1(5min

22、2111212121xxxxxxxxIPxxZ且且为为整整数数0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ 现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可）的最优解即可同理求同理求（LP2） ,如图所示如图所示在在C 点取得最优解点取得最优解即即x12, x2 =10/3, Z(2) 56/318.7 Z(2) Z(0) 原问题目标函数值的下界为原问题目标函数值的下界为-18.7-18.7x2 不是整数，故利用不是整数，故利用3 10/34 加入条件加入条件x1x233(18/11,40/11) 先求先求（LP1）, ,如图所示。此

23、如图所示。此时，在时，在B 点取得最优解点取得最优解x11, x2 =3, Z(1)16找到整数解，问题已探明，找到整数解，问题已探明，此枝停止计算。且由此可知此枝停止计算。且由此可知目标函数最优值的上界为目标函数最优值的上界为-1611BAC加入条件：加入条件： x23, x24 有下式：有下式：且且为为整整数数0,3 2 4 30 652 )3(5min21211212121xxxxxxxxxIPxxZ且且为为整整数数0,4 2 4 30 652 )4(5min21211212121xxxxxxxxxIPxxZ只要求出（只要求出（LP3）和（）和（LP4）的最优解即可）的最优解即可x1x2

24、33(18/11,40/11)11BAC先求先求（LP3）, ,如图所示。此时如图所示。此时D 在点取得最优解在点取得最优解即即 x112/5=2.4, x2 =3, Z(3)-87/5=-17.4-18.7但但x112/5不是整数，可继续不是整数，可继续分枝。即分枝。即 3x12D求求（LP4），），如图所示如图所示无可行解，不再分枝无可行解，不再分枝 在在（LP3）的基础上继续分枝。加入条件）的基础上继续分枝。加入条件3x12有下式：有下式：且且为为整整数数0,2 3 2 4 30 652 )5(5min211211212121xxxxxxxxxxIPxxZ且且为为整整数数0,3 3 2

25、4 30 652 )6(5min211211212121xxxxxxxxxxIPxxZ只要求出（只要求出（LP5）和（）和（LP6）的最优解即可）的最优解即可x1x233(18/11,40/11)11BACD先求先求（LP5）, ,如图所示。此时如图所示。此时E 在点取得最优解在点取得最优解即即 x12, x2 =3, Z(5)17找到整数解，问题已探明，此找到整数解，问题已探明，此枝停止计算。枝停止计算。E求求（LP6），），如图所示。此时如图所示。此时 F在点取得最优解在点取得最优解x13, x2 =2.5, Z(6)31/2=15.5 Z(5) F 如对如对Z(6) 继续分解，其最小值也

26、不会低于继续分解，其最小值也不会低于15.5，问题探明，问题探明, ,剪枝剪枝至此，原问题至此，原问题( (IP) )的最优解为：的最优解为： x1=2， x2 =3, Z* = Z(5) 17以上的求解过程可以上的求解过程可以用一个树形图表以用一个树形图表示如右：示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP3x1=12/5, x2=3Z(3) 17.4LP4无可无可行解行解LP5x1=2, x2=3Z(5) 17LP6x1=3, x2=5/2Z(6) 15.5x11x12x23

27、x24x12x13 且全为整数且全为整数0,13651914max21212121xxxxxxxxZ练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP3x1=33/14, x2=2Z(3) 61/14LP4无可无可行解行解x22x23LP5x1=2, x2=2Z(7) 4LP6x1=3, x2=1Z(8) 4x12x13一、计算步骤一、计算步骤 1、用单纯形法求解、用单纯形法求解( IP )对应的松弛问题对应的

28、松弛问题( LP ) 若若( LP )没有最优解，则没有最优解，则( IP )也没有最优解，也没有最优解，停止计算；停止计算； 若若( LP )有最优解，并符合有最优解，并符合( IP )的整数条件，的整数条件，则则( LP )的最优解即为的最优解即为( IP )的最优解，停止计算；的最优解，停止计算； 若若( LP )有最优解，但不符合有最优解，但不符合( IP )的整数条件，的整数条件，转入下一步。转入下一步。第三节第三节 整数规划的解法整数规划的解法 割平面法割平面法 2 2、从、从( (LP) )的最优解中，任选不为整数的分量的最优解中，任选不为整数的分量xi ,将最将最优单纯形表中该

29、行的系数优单纯形表中该行的系数 和和 分解为整数部分和小分解为整数部分和小数部分之和，并以该行为源行，作割平面方程数部分之和，并以该行为源行，作割平面方程ikaib由最终单纯形表可以得到：由最终单纯形表可以得到： ikikibxaxikaib将将 和和分成整数部分和非负真分数之和，即分成整数部分和非负真分数之和，即iiifNb10iiifbN的整数部分，为ikikikfNa10ikikikfaN的整数部分，为代入上式得：代入上式得：kkikkiikikixffNxNx 因变量为整数，即上式左边必须是整数，由右边看，因为因变量为整数，即上式左边必须是整数，由右边看，因为00fi 11，所以不能为

30、正，即，所以不能为正，即 0kkikixff割平面方程割平面方程 3 3、将由割平面方程得到的约束条件作为一个新、将由割平面方程得到的约束条件作为一个新的约束条件置于最优单纯形表中，用对偶单纯形法的约束条件置于最优单纯形表中，用对偶单纯形法求出新的最优解，返回求出新的最优解，返回1 1。例例1 、用割平面法求解整数规划问题、用割平面法求解整数规划问题且为整数, 0,14329223max21212121xxxxxxxxZ2123maxxxz0,1432924321421321xxxxxxxxxx 解：增加松弛变量解：增加松弛变量x3和和x4 ，得到，得到(LP)的初始单纯形表的初始单纯形表和最

31、优单纯形表和最优单纯形表：Cj3200CBXBbx1x2x3x40 x31423100 x492101Z00100Cj3200CBXBbx1x2x3x42x25/2011/2-1/23x113/410-1/41/4Z-3/200-1/4-5/4 此题的最优解为：此题的最优解为：X =(13/4 ,5/2) 。但不是整数最优解，但不是整数最优解，引入割平面。可以使用的割平面的条件有引入割平面。可以使用的割平面的条件有: 252121432xxx4134141431xxx41414343xx21212143xx252121432xxx21221214432xxxx43422121212xxxx41

32、34141431xxx41341434331xxxx43314143413xxxx 为加快割平面的速度，一般选择较大的为加快割平面的速度，一般选择较大的 fi 作为割平面作为割平面方程进行计算方程进行计算现将生成的割平面条件加入松弛变量，然后加到表中现将生成的割平面条件加入松弛变量，然后加到表中212121543xxx21212143xx21212143xxCj32000CBXBbx1x2x3x4x52x25/2011/2-1/203x113/410-1/43/400 x5-1/200-1/2-1/2100-1/4-5/402x22010-113x17/21001-1/20 x310011-2

33、000-1-1/221215x割平面方程为割平面方程为: :Cj320000CBXBbx1x2x3x4x5x62x22010-1103x17/21001-1/200 x310011-200 x6-1/20000-1/21000-1-1/202x21010-1023x1410010-10 x3300110-40 x5100001-2000-10-1且均为整数0,521023max2122121xxxxxxxz【例【例5-75-7】求解整数规划问题求解整数规划问题且为整数0,205462max21212121xxxxxxxxz【练习【练习】求解整数规划问题求解整数规划问题 01整数规划是一种特殊形

34、式的整数规划，整数规划是一种特殊形式的整数规划，这时的决策变量这时的决策变量xi 只取两个值只取两个值0或或1，一般的解法为，一般的解法为隐枚举法隐枚举法【例【例5-11】求解下列】求解下列01规划问题规划问题 10,(4) 64 (3) 3 (2) 44(1) 22523max3213221321321321或或xxxxxxxxxxxxxxxxZ第四节第四节 0-1整数规划整数规划x1 , x2 , x3约束条件约束条件满足条件满足条件Z 值值 (1) (2) (3) (4)是是 否否( 0, 0, 0 ) 0 0 0 00( 0, 0, 1 ) 1 1 0 15( 0, 1, 0 ) 2

35、4 1 42( 1, 0, 0 ) 1 1 1 03( 0, 1, 1 ) 1 5( 1, 0, 1 ) 0 2 1 18( 1, 1, 0 ) 3( 1, 1, 1 ) 2 6由上表可知，问题的最优解为由上表可知，问题的最优解为 X*=( x1=1， x2=0， x3=1 )解：对于解：对于01规划问题，由于每个变量只取规划问题，由于每个变量只取0、1两个值，一两个值，一般会用穷举法来求解，即将所有的般会用穷举法来求解，即将所有的0、1组合找出，使目标函组合找出，使目标函数达到极值要求就可求得最优解。数达到极值要求就可求得最优解。 由上表可知：由上表可知： x1 =0，x2=0，x3=1是一

36、个可行解，为尽快找是一个可行解，为尽快找到最优解，可将到最优解，可将3x12x25x35作为一个约束，凡是目标函作为一个约束，凡是目标函数值小于数值小于5的组合不必讨论，如下表。的组合不必讨论，如下表。x1 , x2 , x3约束条件约束条件满足条件满足条件Z 值值(0) (1) (2) (3) (4)是是 否否( 0, 0, 0 ) 0 0 0 0 00( 0, 0, 1 ) 5 1 1 0 15( 0, 1, 0 )-2( 0, 1, 1 ) 3( 1, 0, 0 ) 3( 1, 0, 1 ) 8 0 2 1 18( 1, 1, 0 ) 1( 1, 1, 1 ) 4问题的最优解为问题的最优

37、解为 X*=( x1 =1，x2=0，x3=1 )隐枚举法如果重新排列变量的顺序可使问题更快地求得最优解，如：如果重新排列变量的顺序可使问题更快地求得最优解，如：令令x2=1-x2(0 x21)，将目标函数中变量前的系数均化为正数，将目标函数中变量前的系数均化为正数，则目标函数变为则目标函数变为22355)1(23213321xxxxxxzmax寻找最优目标函数值寻找最优目标函数值x1 ， x2， x3约束条件约束条件满足条件满足条件Z 值值(0) (1) (2) (3) (4)是是 否否( 1, 1, 1 ) 8 0 0 0 08问题的最优解为问题的最优解为 X*=( x1=1，x2=0，x

38、3=1 ) 【例】求解下列【例】求解下列01规划问题规划问题4 , 3 , 2 , 1 1 , 05 35646 1 273max421432143214321jxxxxxxxxxxxxxxxxZj 解：令解：令 x11x1, x2=1- x2, x4=1- x4，则目标函数变，则目标函数变为为1173)1 ()1 (7)1 ( 3max43214321xxxxxxxxZ此时，此时，x*=(1, 0, 1, 0)，z*=-2练习：求解下列练习：求解下列01规划问题规划问题)5 , 4 , 3 , 2 , 1( 1054 24423 248510min543215432154321jxxxxxx

39、xxxxxxxxxxZj或所以，所以， 原问题的最优解为：原问题的最优解为： X*(0, 0, 1, 0, 0)，Z*=8第五节第五节 指派问题指派问题 在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任项不同的任务，务，需要需要n 个人分别完成其中的一项个人分别完成其中的一项，但由于任务的，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生的效率（或花费的时间或费用）也就不同。于是产生了一个问题，指派哪个人去完成哪项任务，可使完成了一个问题，指派哪个人去完成哪项任务

40、，可使完成 n 项任务的总效率最高（或所需时间最少）？这类问项任务的总效率最高（或所需时间最少）？这类问题称为题称为指派问题指派问题或或分配问题分配问题。 每一项工作只能分配给一个人；每一项工作只能分配给一个人； 每一个人只能并且必须接受一项工作每一个人只能并且必须接受一项工作 一、指派问题的一般提法一、指派问题的一般提法【5-135-13】某工厂要生产四种产品，该工厂有四个车间都可以生】某工厂要生产四种产品，该工厂有四个车间都可以生产这四种产品。但由于设备情况与技术情况不同，所以生产成产这四种产品。但由于设备情况与技术情况不同，所以生产成本不同，其单位产品的生产成本如表所示。问应当如何分配这

41、本不同，其单位产品的生产成本如表所示。问应当如何分配这四种产品到各车间，才能使总的生产成本最小？试建立该问题四种产品到各车间，才能使总的生产成本最小？试建立该问题的数学模型。的数学模型。 产品产品车间车间1234145410251453332643446解解 引入引入0-10-1变量变量xij ( (i, j1,2,3,4,5)1,2,3,4,5)，令：令： 时生产产品，当不指派车间时生产产品，当指派车间jijixij01这个问题的约束条件如下：这个问题的约束条件如下：(1)(1)一个车间只生产一种产品，即一个车间只生产一种产品，即1111444342413433323124232221141

42、31211xxxxxxxxxxxxxxxx141jijx简写为：简写为： （i=1,2,3,4） (2)(2)一种产品只由一个车间生产，即一种产品只由一个车间生产，即 111144342414433323134232221241312111xxxxxxxxxxxxxxxx简写为：简写为：141iijx（ j =1,2,3,4） (3)(3)变量工变量工xij 必须等于必须等于0 0或或1 1，即，即xij =0=0或或1 1。 目标函数为：目标函数为：Min 443412116454xxxxz设决策变量设决策变量 1 分配第分配第i 个人去做第个人去做第j 件工作件工作 xij = 0 相反相

43、反 ( i , j =1.2. n )其数学模型为： 设设n个人被分配去做个人被分配去做n件工作，规定每个人只做一件工作件工作，规定每个人只做一件工作,每每件工作只有一个人去做。已知第件工作只有一个人去做。已知第i个人去做第个人去做第j件工作的的效件工作的的效率（率（ 时间或费用）为时间或费用）为cij (i =1, 2, , n; j =1, 2, , n)并假设并假设cij 0。问应如何分配才能使总效率（。问应如何分配才能使总效率（ 时间或费用）最高？时间或费用）最高？ninjijijxcz11min), 2 , 1,( 10), 2 , 1( 1), 2 , 1( 111njixnjxn

44、ixijniijnjij或效率矩阵（成本矩阵）效率矩阵（成本矩阵）:(:(cij ) )nn 二、匈牙利法二、匈牙利法 分配问题是分配问题是0-1规划的特例，也是运输问题的特例，当然可规划的特例，也是运输问题的特例，当然可用整数规划，用整数规划，0-1规划或运输问题的解法去求解，但这些方法却规划或运输问题的解法去求解，但这些方法却没有充分利用指派问题的特点。没有充分利用指派问题的特点。 库恩库恩( (W.W.Kuhn) )于于19551955年提出了指派问题的解法，他引用了年提出了指派问题的解法，他引用了匈牙利数学家康尼格匈牙利数学家康尼格( (D.Konig) )的关于矩阵中独立零元素的定理

45、：的关于矩阵中独立零元素的定理：系数矩阵中独立系数矩阵中独立0 0元素的最多个数等于能覆盖所有零元元素的最多个数等于能覆盖所有零元素的最小直线数，习惯上称之为匈牙利解法。素的最小直线数，习惯上称之为匈牙利解法。 分配问题最优解的以下性质：分配问题最优解的以下性质：若从系数矩阵若从系数矩阵(cij )的某行的某行( (或某列或某列) )各元素分别减去该行（列）的最小元素，得各元素分别减去该行（列）的最小元素，得到新矩阵到新矩阵(cij),那么以那么以(cij)为系数矩阵求得的最优解和为系数矩阵求得的最优解和利用原系数矩阵求得的最优解相同。利用原系数矩阵求得的最优解相同。 证明证明), 2 , 1

46、;, 3 , 2();, 2 , 1(11njniccnjkccijijjj设成本矩阵第一行各元素均减去同一个数设成本矩阵第一行各元素均减去同一个数k，得到的新矩，得到的新矩阵记为阵记为( (cij ) )kzkxcxcxkxcxcxkcxczninjijijninjijijnjjnjjjninjijijnjjjninjijij1121111112111111)( 第一步：变换成本矩阵，使每行每列中至少出现一第一步：变换成本矩阵，使每行每列中至少出现一个个0元素元素 (1) 令令(cij) nn的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； (2) 再从所得新系数矩阵的每列元

47、素中减去该列的再从所得新系数矩阵的每列元素中减去该列的最小元素。最小元素。644362335415104543110401143046010321401101011130430103匈牙利法的步骤（以（以 例例5-135-13为例）为例） 第二步：试求最优解第二步：试求最优解 在新矩阵中找尽可能多的独立在新矩阵中找尽可能多的独立0元素，若能找出元素，若能找出n个个独立独立0元素，就以这元素，就以这n个独立个独立0元素对应解矩阵元素对应解矩阵(xij)中的元中的元素为素为1，其余为，其余为0，这就得到最优解。找独立，这就得到最优解。找独立0元素，常元素，常用的步骤为：用的步骤为： (1) 从只有

48、一个从只有一个0元素的行元素的行(列列)开始，给这个开始，给这个0元素加元素加，记作，记作 。然后划去。然后划去 所在列所在列(行行)的其它的其它0元素，记作元素，记作 ；这表示这列所代表的任务已指派完，不必再考虑别人了；这表示这列所代表的任务已指派完，不必再考虑别人了； (2) 给只有一个给只有一个0元素的列元素的列(行行)中的中的0元素加元素加，记，记作作 ；然后划去；然后划去 所在行的所在行的0元素，记作元素，记作 ； (3) 反复进行反复进行(1)，(2)两步，直到尽可能多的两步，直到尽可能多的0元素都元素都被圈出和划掉为止；被圈出和划掉为止；00000001101011130430101000010000100001 (4) (4) 若仍有没有划若仍有没有划的的0 0元素，且同行元素，且同行( (列列) )的的0 0元素元素至少有两个，则从剩有至少有两个，则从剩有0 0元素最少的行元素最少的行( (列列) )开始，比较开始，比较这行各这行各0 0元素所在列中元素所在列中0 0元素的数目，选择元素的数目，选择0 0元素少的那元素少的那列的这个列的这个0 0元素加元素加( (表示选择性多的要表示选择性多的要“礼让礼让”选择选择性少的性少的) )，然后划掉同行同列的其它，然后划掉同