第4章 整数规划与分配问题 管理运筹学 重庆三峡学院

1、第,4,章,整数规划与分配问题,目录,4,整数规划,1,2,3,0-1,规划,分配问题,本章小结与作业,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,4.1,整数规划,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,导入案例,整数规划的基本概念,图解法,分枝定界法的基本思路,4.1.1,导入案例集装箱托运计划,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,货物,每箱体积,m,3,每箱质量,50kg,每箱利润,百元,甲,乙,3,8,4,3,5,6,托运,限制,40,24,某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利

2、,润以及托运所受到的限制如表所示。问怎样安排托运计划，可使利润最,大,1,2,1,2,1,2,1,2,1,2,max z,5,6,3,8,4,3,0,x,x,x,x,x,x,x,x,x,x,40,24,取整数,设,x1,x2,表示两种货物装载数量,整,数,依题意有如下数学模型,在实际中，许多要求变量取整,的数学模型，称为整数规划,4.1.2,整数规划的基本概念,整数规划,integer programming,IP,是指一类要求问,题中的全部或一部分变量为整数的数学规划。在整数规划,中，依决策变量的取值不同，又可进一步划分,如果所有变量都限制为整数，则称为纯整数规划,Pure,Integer

3、Programming,PIP,如果仅一部分变量限制为整数，则称为混合整数规划,Mixed Integer Programming,MIP,变量取二进制的整数规划则称为,0-1,规划,Binary Integer,Programming,BIP,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,4.1.3,图解法,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,例,4.1,用图解法求解整数规划,1,2,1,2,1,2,1,2,1,2,max,5,6,3,8,40,1,4,3,24,2,0,z,x,x,x,x,x,x,x,x,x,x,取整数,1,建立直角坐标

4、系,图示约束条件，确定,可行域,2,图示目标函数一,根基线，按目标要求,平行移动，直到与可,行域相交,3,求出交点坐标与,目标值,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,x1,0,1,2,3,4,5,6,7,8,x,2,X,2,4),z=34,4.1.4,分枝定界法的基本思路,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,例,4.1,分枝定界法求解,1,2,1,2,1,2,1,2,1,2,max,5,6,3,8,40,1,4,3,24,2,0,z,x,x,x,x,x,x,x,x,x,x,取整数,分枝定界法,Branch and Bound,M

5、ethod,用于求解整数规划问题,是在,20,世纪,60,年代初，由,Land,Doig,和,Dakin,等人提出的,解,1,承例,4.1,由图解法知，一般线性规划解的坐标为,72/23,88/23,不在,网格线的交叉点上，非整数解（非可行解,2,对“解,1,分枝定界：选取,x1,进行分枝定界：在原模型的基础上，分别添,加,x13,x14,优化结果,解,2,X=(3,31/8,解,3,X=(4,8/3,均为非,整数（非可行解,3,先对“解,2,2,的坐标为,3,31/8,分别添加,x23,x24,优化结果,解,4,X=(3,3,z=33,为可行解；“解,5,X=(8/3,4,z=37.33,为

6、非可行解，由于其目标值大于解,4,的目标值，先保留，待进一步分枝定界,4,再对“解,3,分枝定界：“解,3,的,x2,坐标,为非整数，添加,x22,x2 3,为非,可行域），优化结果为“解,6,X=(9/2,2,z=34.5,再添加,x1 =4,x1 5,解得,整数解,X=(4,2,z=32,和非整数解,X=(5,4/3,目标值,z=33,这两个整数解和非,整数解的目标值均不大于整数解,解,4,不再保留,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,x1,0,1,2,3,4,5,6,7,8,x,2,解,6,9/2,2),z=34.5,解,3,4,8/3,解,1,72/2

7、3,88/23,解,2,3,31/8,解,4,3,3),z=33,解,5,8/3,4),z=37.33,5,对“解,5,分枝定界：“解,5,的坐标,8/3,4,为非整数，添加,x12,x13,为非可行域），优化结果为,X=(2,17/4,再添加,x2=4,和,x2=5,求得整数解,2,4,目标值,34,整数解,0,5,目标值,30,取,2,4,如图“解,7,解,7,2,4),z=34,6,剪枝：将“解,4,X=(3,3,z=33,与,解,7,X=(2,4,z=34,相比较，“解,7,目标值为,34,对应的最优方案,4.2 0-1,规划,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配

8、,问,题,0-1,规划的概念与隐枚举法简介,0-1,变量在数学建模中的应用,案例,1,球队队员筛选,案例,2,选址问题,案例,3,集合覆盖问题,4.2.1 0-1,规划的概念,0-1,规划是一种特殊类型的整数规划，即决策变量只取,0,或,1,0-1,规划在整数规划中占有重要地位，许多实际问,题，例如指派问题、选址问题、送货问题都可归结为此,类规划。求解,0-1,规划的常用方法是隐枚举法，对各种,特殊问题还有一些特殊方法，例如求解指派问题的匈牙,利方法,0-1,规划的数学模型为,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,0,1,max(min,z,CX,AX,b,s,t

9、,X,取,或,4.2.2,隐枚举法简介,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,1,2,3,1,2,3,1,2,3,1,2,1,2,3,max,3,2,2,1,4,4,2,s.t,3,3,0,1,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,例,求最优解,或,1,2,3,1,2,3,1,2,3,1,2,1,2,3,min,min,3,2,2,4,4,s.t,3,0,1,j,c,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,改变,符号,变为,或,1,1,2,2,3,3,1,1,1,x,x,x,x,x,x,令,1,2,3,1,2,3,1,2,

10、3,1,2,1,2,3,min,3,5,2,0,4,2,s.t,1,0,1,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,或,2,3,1,2,3,1,2,3,1,2,1,1,2,3,min,3,5,2,0,4,2,s.t,1,0,1,w,x,x,x,x,x,x,x,x,x,x,x,x,x,x,目标系数升序排序,或,1,化成标准形式,1,目标函数,min ,cj0,目标若,max,目标系数改变符号,变为,min,2,若,cj0,令,yj=1-xj,使其变正,3,目标函数中,变量按目标系数,从小到大排列,约束条件中也跟,着相应改变,2,令标准化后的,0-1,问题所有变,量为,0,若满

11、足约束,即为最优,否,则转下步,3,按目标函数中排列顺序依次,令各变量分别取,1,或,0,进行枚举,1,2,3,0,1,0,x,x,x,解得,1,2,3,1,0,1,x,x,x,max,4,z,4.2.4 0-1,变量在数学建模中的应用,1) n,中（至少、最多）选,k,个,2,选甲必选乙，选乙不一定选,3,选了甲或乙，丙就不能入选，选了丙，甲、乙都不能入选,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,1,1,0,1,x,x,x,x,x,x,x,甲,丙,乙,丙,甲,乙,丙,或,1,0,1,n,j,j,j,x,k,x,或,0,1,j,x,x,x,乙,甲,或,4,变量以离散

12、数值,c1,c2,cn,1,1,1,0,1,1,n,j,j,j,n,j,j,j,y,c,x,x,x,j,n,或,解,该问题可表示成如下约束,1,2,3,4,1,2,3,4,3,5,7,9,1,0,1,1,4,j,y,x,x,x,x,x,x,x,x,x,j,或,4.2.4 0-1,变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,例,4.3,用,0-1,变量表示约束,变量,y,取,3,5,7,9,中的一个,例,4.4,用,0-1,变量表示约束,只需满足一个,5,两个约束满足一个,1,1,2,2,1,0,1,f,X,g,My,f,X,g,M,y,y,或,1

13、,2,1,1,2,2,1,2,1,2,1,2,1,2,2,3,2,10,1,0,1,2,1,3,2,10,0,1,x,x,y,M,x,x,y,M,y,y,y,y,x,x,y,M,x,x,yM,y,解,该问题可表示成,或,或,或,1,2,1,2,2,3,2,10,x,x,x,x,和,4.2.4 0-1,变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,6) n,个约束（至少、最多,满足,k,个,1,1,1,0,1,1,2,n,n,n,j,j,f,X,g,My,f,X,g,My,y,n,k,y,j,n,M,或,1,2,1,3,3,4,5,2,2,6,x,x

14、,x,x,x,x,1,2,1,1,2,3,3,3,4,4,1,2,3,4,14,5,2,2,6,2,0,1,x,x,y,M,x,y,M,x,y,M,x,x,y,M,y,y,y,y,y,或,例,4.5,以下四个约束中至少,满足两个,解,该问题可表示成,4.2.4 0-1,变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,7,两组约束满足一组,2,1,5,1,2,2,5,2,1,2,1,2,4,0,4,3,1,0,1,x,y,M,x,y,M,x,y,M,x,y,M,y,y,y,或,2,5,2,5,4,0,4,1,3,1,0,1,x,yM,x,yM,x,y,

15、M,x,y,M,y,或,或,2,5,2,5,4,0,4,3,x,x,x,x,则,否则,例,4.6,用,0-1,表示：若,解,该问题可表示成,1,1,2,2,3,3,4,4,1,1,0,1,f,X,g,My,f,X,g,My,f,X,g,M,y,f,X,g,M,y,y,或,4.2.4 0-1,变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,8,分段函数的,0-1,表述,0,0,0,0,1,x,f,x,k,cx,x,f,x,yk,cx,y,Mx,x,My,y,当,当,对,可表示为,或,生产过程的种类,固定投资,元,生产成本,元,千克,最大日产量,千克,甲

16、,乙,丙,1,000,2,000,3,000,5,4,3,2,000,3,000,4,000,例,P76,第,6,题,某企业接受某项产品订货,需求量为每日,3,500,千克，现有,3,种生产,过程供选择，各生产过程所需固定投资,成本,生产成本，最大日产量如表,所示。问,企业需要决定采用哪种,一种,或多种,生产过程和日产量多少千克,才能既保证按合同交货又使总成本最小,试列出该问题的整数规划数学模型,4.2.4 0-1,变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,1,0,1,2,3,i,i,i,i,y,x,i,i,采用第,种生产过程,不采用第,种生产

17、过程,采用第,种生产过程生产的数量,1,2,3,1,2,3,1,2,3,1,1,2,2,3,3,1,1,2,2,3,3,13,13,min,1000,2000,3000,5,4,3,3000,4000,0,1,z,y,y,y,x,x,x,x,x,x,x,y,x,y,x,y,s,t,y,x,M,y,x,M,y,x,M,y,x,3500,2000,或,0,解,设,采用生产过程丙生产,3500kg,总成本,13500,元,生产,过程,固定投资,元,生产成本,元,千克,最大日产量,千克,甲,乙,丙,1,000,2,000,3,000,5,4,3,2,000,3,000,4,000,4.2.4 0-1,

18、变量在数学建模中的应用,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,某校篮球队准备从以下,6,名预备队员中选,拔,3,名为正式队员，并使平均的身高尽可,能高。这六名预备队员情况如表所示,队员的挑选要满足下列条件,1) 6,位预备队员选,3,名,2,至少补充,1,名后卫人员,3) B,或,E,中间最多入选,1,名,4,最多补充,1,名中锋,5,无论,B,或,D,入选,F,都不能入选,案例,4-1,球队队员筛选,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,预备队员,身高,cm,位置,A,B,C,D,E,F,193,191,187,186,180,18

19、5,中锋,中锋,前锋,前锋,后卫,后卫,s.t,1,2,3,4,5,6,max,193,191,187,186,180,185,z,x,x,x,x,x,x,0,1,i,i,x,i,第,名未进入正式队,设,第,名进入正式队,5,6,1,2,x,x,1,2,3,4,5,6,3,1,x,x,x,x,x,x,2,5,1,3,x,x,1,2,1,4,x,x,2,6,4,6,1,5,1,x,x,x,x,16,0,1,x,或,案例,4-2,选址问题,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,地点,A,1,A,2,A,3,A,4,A,5,A,6,A,7,建点成本,20,20,25,2

20、4,22,24,23,估计利润,30,30,35,34,38,40,45,某公司在城市东、西、南,三区拟建立门市部。计划,有,7,个位置,点,A,j,j=1,7,可供选择。规定,在东区，由,A,1,A,2,A,3,三个,点至多选两个；在西区,由,A,4,A,5,两个点至少选一,个；在南区，由,A,6,A,7,两,个点至少选一个。设各位,置建点的成本与预计利润,见表，若建点总成本控制,在,100,万元以内，试问应,该选取哪几个点可使年利,润为最大,1,1,2,7,0,i,i,i,A,x,i,A,L,当,被选中,设,当,未被选中,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,

21、4,5,6,7,max,30,30,35,34,38,40,45,20,20,25,24,22,24,23,100,2,s.t,1,1,0,1,i,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,东区,西区,南区,或,数学模型为,某区有,6,个街道。这个区必须确定在什,么地方修建消防站。在保证至少有一,个消防站在每个街道的,15min,行驶时,间内的情况下，这个区希望修建的消,防站最少。各街道间行驶时间如表,案例,4-3,集合覆盖问题,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,街道,1,街道,2,街道,3,街道,4,街道,5

22、,街道,6,街道,1,0,10,20,30,30,20,街道,2,10,0,25,35,20,10,街道,3,20,25,0,15,30,20,街道,4,30,35,15,0,15,25,街道,5,30,20,30,15,0,14,街道,6,20,10,20,25,14,0,1,2,1,2,6,3,4,3,4,5,4,5,6,2,5,6,16,1,1,1,1,1,1,0,1,x,x,x,x,x,x,x,s,t,x,x,x,x,x,x,x,x,x,x,或,1,0,1,6,i,i,i,i,x,L,第,街道设消防站,第,街道不设消防站,设,1,2,3,4,5,6,min,z,x,x,x,x,x,x,

23、目标,消防站数目最少,4.3,分配问题,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,分配问题数学模型,匈牙利法,案例,任务分派,4.3.1,分配问题数学模型,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,项目,张,王,李,赵,仰泳,蛙泳,蝶泳,自由泳,37,43,33,30,33,33,29,26,38,42,39,29,37,34,30,29,导入案例,任务分配,某游泳队有四名运动员，其平,时训练成绩,s/50m,如表所示,问如何安排可使总成绩最好,人员,任务,效率矩阵,cij,1,0,ij,i,j,i,j,x,第,分配给第,人,第,不分给第,人

24、,设,11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44,min,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,z,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,11,12,13,14,21,22,23,24,31,32,33,34,41,42,43,44,1,1,1,1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,每项任务,交给一人,0,1,1,4,1,4,ij,x,i,j,或,11,21,31,41,12,22,32,42,13,23,33,34,14,24,

25、34,44,1,1,1,1,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,每人分给,一项任务,s,t,在管理活动中，人们会经常遇到这样的问题，某单位有,n(n1,项工作任务,需要,m(n1,个人去完成，并且每个人只干一件工作，每项工作都必须有人,干，通过权衡，合理分派任务，使总的消耗,或收益,达到最小,或最大,的,0,1,规划问题，称为分配问题,Assignment Problem,AP,当,n=m,时为人员与任务平衡,nm,为人多任务少,nm,为人少任务多，其,数学模型如下,人少任务多,nM,人多任务少,nm,人员与任务平衡,n=m,1,1,1,1,min,max,1,1,

26、s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,或,4.3.1,分配问题数学模型,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,1,1,1,1,min,max,1,1,s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,或,1,1,1,1,min,max,1,1,s.t,0,1,1,2,1,2,m,n,ij,ij,i,j,n,ij,j,m,ij,i,ij,z,z,c,x,x,x,x,i,m,j,n,

27、或,匈牙利法是,1955,年库恩,W.W.Kuhu,引用匈牙利数学家考尼格,D.Konig,关于“一个矩阵中独立,0,元素最多个数等于能够覆盖所有,0,元,素的最少直线数”的定理而提出的分配问题的解题方法。虽然在此以,后方法不断改进，但仍沿用这个名称,匈牙利法解题首先要将模型标准化（人员任务平衡、目标极小,1,若人员数,n,任务数,m,则添加,n-m=k,个虚拟任务，效率矩阵,中对应的元素为,0,2,若人员数,n,任务数,m,则添加,m-n=s,个虚拟人员，效率矩阵,中对应的元素为,0,3,若目标函数为极大，则令,构造新的效率矩阵,将目标函数转化为最小,4.3.2,匈牙利法,管,理,运,筹,学

28、,第,4,章,整,数,规,划,与,分,配,问,题,ij,M,ij,b,c,c,max,M,ij,n,n,c,c,4.3.2,匈牙利法,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,ij,M,ij,b,c,c,max,M,ij,n,n,c,c,1,1,n,n,ij,ij,i,j,z,c,x,1,1,1,1,max,min,n,n,n,n,ij,ij,ij,ij,i,j,i,j,c,x,b,x,等价于,1,1,n,n,M,ij,ij,i,j,nc,b,x,1,1,n,n,M,ij,ij,i,j,c,b,x,1,1,1,1,n,n,n,n,M,ij,ij,ij,i,j,i,j,

29、c,x,b,x,证,匈牙利法迭代步骤,每行减去该行最小数,每列减去该列最小数,先看行，只有,1,个,0,标记为,划去所在列，转下行，直到最后行,再看列，只有,1,个,0,标记为,划去所在行，转下列，直到最后列,重复上述过程,三种结局,处取,1,其余取,0,得最优解,从未被划去的数找,最小数,k,末被划,去的数字减,k,覆,盖直线交叉处加,k,个数,n,个数,n,从闭回路任一,0,出发,在转弯处按顺序编,号，取单号,或双号,标记,存在,0,的闭回路,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,例,4.7,用匈牙利,法求解引例中最小化,分配问题,匈牙利法迭代例题,管,理,运

30、,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,X,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,C,min,33,33,29,26,4,0,5,4,10,0,9,1,4,0,10,1,4,0,3,3,min,4,0,3,1,0,0,2,4,6,0,6,0,0,0,7,0,0,0,0,2,1,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,X,129,z,最优值,37,33,38,37,43,33,42,34,33,29,39,30,30,26,29,29,C

31、,例,4.8,用匈牙,利法求解最小化分,配问题,12,7,9,9,9,8,9,7,7,7,7,11,12,12,9,15,14,14,7,10,4,10,10,7,9,C,min,12,7,9,9,9,7,8,9,7,7,7,7,7,11,12,12,9,7,15,14,14,7,10,7,4,10,10,7,9,4,C,解,5,0,0,2,0,3,4,0,2,0,0,4,3,5,0,8,7,5,0,1,0,6,4,3,3,5,0,2,2,2,1,2,0,0,0,0,4,5,5,2,8,7,7,0,3,0,6,6,3,5,k=2,最优方案,x11=x23=x35=x44,x51=1,其余,0,

32、最优值,34,匈牙利法迭代例题,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,分配甲、乙、丙、丁四个人去完成,A,B,C,D,E,五项任务，每个人,完成各项任务的时间如表所示,由于任务数多于人数，故考虑,1,任务,E,必须完成，其他,4,项中可任选,3,项完成,2,其中有一个人完成两项，其他每人完成一项,3,任务,A,由甲或丙完成，任务,C,由丙或丁完成，任务,E,由甲、乙或丁,完成，且规定,4,人中丙或丁完成两项任务，其他每人完成一项,试分别确定最优分配方案，使完成任务的总时间为最小,任务,人员,A,B,C,D,E,甲,乙,丙,丁,25,39,34,24,29,38,2

33、7,42,31,26,28,36,42,20,40,23,37,33,32,45,案例,4-4,任务分派,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,4,5,1,1,5,1,4,1,4,5,1,min,1,1,2,3,4,s.t,1,1,2,3,4,1,0,1,ij,ij,i,j,ij,j,ij,i,i,ij,i,z,c,x,x,i,x,j,x,x,数学模型,或,1,任务,E,必须完成，其他,4,项中可任选,3,项完成,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,25,29,31,42,37,39,38,26,20,33,34,27,28,40,

34、32,24,42,36,23,45,ij,A,B,C,D,E,c,甲,乙,丙,丁,该问题为人少任务多，应添加,假想人员，但任务,E,必须完成,故,c,55,应为,M,25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,0,0,0,ij,c,M,25,29,31,42,37,39,38,26,20,33,34,27,28,40,32,24,42,36,23,45,0,0,0,0,ij,c,M,匈牙利法求解,管,理,运,筹,学,第,4,章,整,数,规,划,与,分,配,问,题,0,4,6,17,12,19,18,6,0,13,7

35、,0,1,13,5,1,19,13,0,22,0,0,0,0,M,min,25,20,27,23,0,0,4,6,17,7,19,18,6,0,8,7,0,1,13,0,1,19,13,0,17,0,0,0,0,5,M,min,0,0,0,0,5,k=4,0,0,2,17,3,19,14,2,0,4,11,0,1,17,0,1,15,9,0,13,4,0,0,4,5,M,k=1,0,0,2,18,3,18,13,1,0,3,11,0,1,18,0,0,14,8,0,12,4,0,0,5,5,M,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,X,29,20,32,24,105,z,1,2,3,25,29,31,42,37,25,29,31,42,37,0,0,0,39