运筹学 第四章 整数规划与分配问题.

1、第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学 例例1、合理下料问题、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A1, A2,Am 的的毛坯。毛坯。在一根圆钢上下料的方式有在一根圆钢上下料的方式有B1,B2, Bn 种，每种，每种下料方式可以得到各种零件的毛坯数以及每种种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？使得即满足需要，所用的原材料又最少？第四章 整数规划与分配问题 冯大光制作沈阳农业大学零 件毛坯

2、数零件 方 个数 式零件nBB 1mAA 1mbb 1mnmnaaaa 1111 设：设：xj 表示用表示用Bj (j=1.2n) 种方式下料根数模型：种方式下料根数模型：且且为为整整数数n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZx1xn第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学1211112111221222221212 nnmmmm nmmnBBB nAcccafAcccafAcccafbbb第四章 整数规划与分配问题 冯大光制作沈阳农业大学n)1.2jm1.2(i 1 0, 0n)1.2(j

3、)2 . 1( min111、或或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学njijjmixa1)2 . 1( miijmix1)2 . 1( 1第四章 整数规划与分配问题 冯大光制作沈阳农业大学 因此，求因此，求xij ，使得使得n)1.2jm,1.2(i 1 0n)1.2(j 1),max(min111121或ijmiijnjnjnjmjjjjjjxxxaxaxaZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大

4、学第四章 整数规划与分配问题 冯大光制作沈阳农业大学且为整数0,13651914max21212121xxxxxxxxZ0,13651914max21212121xxxxxxxxZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学134142122211211yyMyxMyxMyxMyx41x32x

5、41x12x)2 , 1(, 0, 1iiiyi组条件起作用第组条件不起作用第第四章 整数规划与分配问题 冯大光制作沈阳农业大学(4)第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学 ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxaZijniijnjijninjijij或第四章 整数规划与分配问题 冯大光制作沈阳农业大学0ija0ijx1ijxninjijijxaz11第四章 整数规划与分配问题 冯大光制作沈阳农业大学014120830232302093

6、9140111x123x132x144x第四章 整数规划与分配问题 冯大光制作沈阳农业大学ninjijijXbZ11ninjijjiijXdta11)(ninjninjniijjnjijiijijXdXtXa111111)()()(11ninjjidtZninjjidt11第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学 任务任务人员人员ABCD甲甲67112乙乙4598丙丙31104丁丁598

7、2第四章 整数规划与分配问题 冯大光制作沈阳农业大学2142 289541013895421176)(ija 0673390245100954 01733402401004540173340240100454第四章 整数规划与分配问题 冯大光制作沈阳农业大四章 整数规划与分配问题 冯大光制作沈阳农业大学6244251343000 0 00 010000100001100006244251343150062440250100343第四章 整数规划与分配问题 冯大光制作沈阳农业大学 任务任务人员人员ABCD甲甲21097乙乙154148丙丙131

8、41611丁丁415139第四章 整数规划与分配问题 冯大光制作沈阳农业大学21097154148131416114151390875110104235001195082511054230001145082511054230001145第四章 整数规划与分配问题 冯大光制作沈阳农业大学08251105423000114506031105423000923060311054230009230010010000011000第四章 整数规划与分配问题 冯大光制作沈阳农业大学115764戊戊69637丁丁96458丙丙9117129乙乙118957甲甲EDCBA费费 工作工作 用用人员人员第四章 整数

9、规划与分配问题 冯大光制作沈阳农业大学11576469637964589117129118957造造“零零”第四章 整数规划与分配问题 冯大光制作沈阳农业大学5032015304310140305242402第四章 整数规划与分配问题 冯大光制作沈阳农业大学50320153043101403052424025032015304310140305242402第四章 整数规划与分配问题 冯大光制作沈阳农业大学50330042033102 40306231301第四章 整数规划与分配问题 冯大光制作沈阳农业大学50330042033102 40306231301第四章 整数规划与分配问题 冯大光制作

10、沈阳农业大学50330042033102 403062313010-120215-12-12-113-10604300631-1023024023第四章 整数规划与分配问题 冯大光制作沈阳农业大学60440032023002302061303000100000010001001000000001第四章 整数规划与分配问题 冯大光制作沈阳农业大学79 10 1213 12 16 1715 16 14 1511 12 15 163821038729764275842359106910第四章 整数规划与分配问题 冯大光制作沈阳农业大学最大化指派问题最大化指派问题人数和工作数不等的指派问题人数和工作数

11、不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题第四章 整数规划与分配问题 冯大光制作沈阳农业大学610129610617711781296101429121215784最大化指派问题最大化指派问题最大值最大值617101712179176171017617171771711177178171217917617101714172179171217121715177178174171175811711010610958117315855210913第四章 整数规划与分配问题 冯大光制作沈阳农业大学10129

12、66177118129614291215784101296617711812961429121578400000第四章 整数规划与分配问题 冯大光制作沈阳农业大学10129661771181296142912157840000004102200150702102208028095100410220015070210220802809510 0410220015070210220802809510第四章 整数规划与分配问题 冯大光制作沈阳农业大学0210002017070010002802829710041022001507021022080280951002100020170700100028

13、02829710第四章 整数规划与分配问题 冯大光制作沈阳农业大学78329824763195232154321BBBBBAAA 31952319527832982476319525432111321BBBBBAAAAAA1可同时做三可同时做三项工作项工作第四章 整数规划与分配问题 冯大光制作沈阳农业大学列减列减第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学452782946178298247639525432154321BBBBBAAAAA4 5 2 782 9 4 6178298247639525432154321MMAAAAABBBB

14、BA1不能做不能做B4;A3不能做不能做B3第四章 整数规划与分配问题 冯大光制作沈阳农业大学（一）、基本思路（一）、基本思路 且为整数且为整数)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考虑整数问题：考虑整数问题：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整数问题的松弛问题：整数问题的松弛问题：第四章 整数规划与分配问题 冯大光制作沈阳农业大学 1、先不考虑整数约束，解、先不考虑整数约束，解( IP )的松弛问题的松弛问题( LP )，可能得到以下情况之一：可能得到以下情况之一：

15、若若(LP)没有可行解没有可行解,则则(IP)也没有可行解也没有可行解,停止计算。停止计算。若若( LP )有最优解有最优解,并符合并符合( IP )的整数条件的整数条件,则则( LP )的的最优解即为最优解即为( IP )的最优解的最优解,停止计算。停止计算。若若( LP )有最优解有最优解,但不符合但不符合( IP )的整数条件的整数条件,转入下转入下一步。为讨论方便，设一步。为讨论方便，设( LP )的的最优解为：最优解为：不不全全为为整整数数其其中中目目标标函函数数最最优优值值为为), 2 , 1(.Z)0 , 0 ,( (0)21)0(mibbbbbXiTmr第四章 整数规划与分配问

16、题 冯大光制作沈阳农业大学 记记( IP )的目标函数最优值为的目标函数最优值为Z* ,以以Z(0) 作为作为Z* 的的上界，上界，记为记为 Z(0) 。再用观察法找的一个整数可行解再用观察法找的一个整数可行解 X，并以其相应的目标函数值并以其相应的目标函数值 Z作为作为Z* 的的下界，记为下界，记为Z Z，也可以令也可以令Z，则有：则有： Z Z* ZZ 在在( LP )的最优解的最优解 X(0)中，任选一个不符合整数条件的中，任选一个不符合整数条件的变量，例如变量，例如xr= （不为整数），以（不为整数），以 表示不超过表示不超过 的最大整数。构造两个约束条件的最大整数。构造两个约束条件

17、xr 和和xr 1rbrbrbrbrb第四章 整数规划与分配问题 冯大光制作沈阳农业大学如此反复进行，直到得到如此反复进行，直到得到ZZ* 为止，即得最优解为止，即得最优解X* 。 将这两个约束条件分别加入问题将这两个约束条件分别加入问题( IP ) ，形成两个子形成两个子问题问题( IP1)和和( IP2 ) ，再解这两个问题的松弛问题再解这两个问题的松弛问题( LP1)和和( LP2) 。 4、修改上、下界：按照以下两点规则进行。、修改上、下界：按照以下两点规则进行。在各分枝问题中在各分枝问题中,找出目标函数值最大者作为新的上界找出目标函数值最大者作为新的上界;.从已符合整数条件的分枝中，

18、找出目标函数值最大者从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。作为新的下界。 5、比较与剪枝、比较与剪枝 ：各分枝的目标函数值中各分枝的目标函数值中,若有小于若有小于Z 者者,则剪掉此枝，表则剪掉此枝，表明此子问题已经探清，不必再分枝了明此子问题已经探清，不必再分枝了;否则继续分枝。否则继续分枝。 Z第四章 整数规划与分配问题 冯大光制作沈阳农业大学且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x4

19、3x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4第四章 整数规划与分配问题 冯大光制作沈阳农业大学x1=13/4 x2=5/2 Z(0) =59/414.75, 选选 x2 进行分枝，即进行分枝，即增加两个约束，增加两个约束，2 x2 ，x2 3 有下式：有下式：且为整数0,2 14329 2) 1(23max212212121xxxxxxxLPxxZ且为整数0,3 14329 2)2(23max212212121xxxxxxxLPxxZ 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将，将新加新加约束条件加入上

20、表计算。即约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得得下表下表:第四章 整数规划与分配问题 冯大光制作沈阳农业大学且为整数0,2 14329 2) 1(23max212212121xxxxxxxLPxxZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学且为整数0,3 14329 2)2(23max212212121xxxxxxxLPxxZ3200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4第四章 整数规划与分配问题 冯大光制作沈阳农业

21、大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学且为整数0,3 2 14329 2)3(23max2112212121xxxxxxxxLPxxZ且为整数0,4 2 14329 2)4(23max2112212121xxxxxxxxLPxxZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学且为整数0,3 2 14329 2) 3(23max2112212121xxxxxxxxLPxxZ第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学LPx1=13/4, x2=5/2Z(0) 59/4=1

22、4.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14LP1x1=7/2, x2=2Z(1)29/2=14.5第四章 整数规划与分配问题 冯大光制作沈阳农业大学例例2.用分枝定界法求解整数规划问题（用图解法计算）用分枝定界法求解整数规划问题（用图解法计算）且且全全为为整整数数0,4 30 652 5min211212121xxxxxxxxxZ记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题0,4 30 652 5min211212121xxxxxxxx

23、xZ记为（记为（LP）第四章 整数规划与分配问题 冯大光制作沈阳农业大学用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x233(18/11,40/11)对于对于x118/111.64，取值取值x1 1， x1 2，先将先将（LP）划分为（划分为（LP1）和和（LP2）, ,取取x1 1, x1 2。 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是( () )最小值的下限。最小值的下限。第四章 整数规划与分配问题 冯大光制作沈阳农业大学且且为为整整数数0,1 4 30 652 )1(5min2111212121xxxxxxxx

24、IPxxZ且且为为整整数数0,2 4 30 652 )2(5min2111212121xxxxxxxxIPxxZ现在只要求出现在只要求出( (LP1) )和和( (LP2) )的最优解即可。的最优解即可。第四章 整数规划与分配问题 冯大光制作沈阳农业大学x1x233 先求先求（LP1）, ,如图所示。如图所示。此时此时B 在点取得最优解。在点取得最优解。x11, x2 =3, Z(1)=-16找到整数解，问题已探找到整数解，问题已探明，此枝停止计算。明，此枝停止计算。11同理求同理求（LP2） ,如图所示。如图所示。在在C 点取得最优解。即点取得最优解。即x12, x2 =10/3, Z(2)

25、=-56/3-18.7 Z2 =10;);tsum(num_j(j):x(5,j)=8;tsum(num_j(j):x(6,j)=8;tfor(num_i(i):sum(num_j(j):y(i,j)=4;);tfor(num_j(j):sum(num_i(i):y(i,j)=1;);tfor(link(i,j):2*y(i,j)=x(i,j)=0;);tfor(link(i,j):gin(x(i,j);x(i,j)=0;);第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学)5,.,1(1461jxiij)4,.,1(851ixjij)6,5

26、(751jxjij)6,.,1(351iyjij) 5,.,1; 6,.,1(2jiyaxyijijijij)5,.,1( 361jyiij)5,.,1( 165jyyjj第四章 整数规划与分配问题 冯大光制作沈阳农业大学)5,.,1(1461jxiij)4,.,1(851ixjij)6 , 5(751jxjij)6,.,1(351iyjij) 5,.,1; 6,.,1(2jiyaxyijijijij)5,.,1( 361jyiij) 5,.,1( 165jyyjj6151miniijjixczLingo 求解求解第四章 整数规划与分配问题 冯大光制作沈阳农业大学第四章 整数规划与分配问题 冯大光制作沈阳农业大学12345123451233451max15021060801802103001001302606001. .1 0 11,