烤箱烘烤面包建模问题

1、烤箱烘烤面包摘要本文解决的是烤箱烘烤面包所用时间要尽可能短的问题。现面包所需烘烤时间长短不一、烤箱容量又有限，而需在保证面包质量的情况下使烘烤完所有面包用的时间最短。为解决此问题，我们运用了模糊数学聚类分析法和贪心算法的思想，并建立了0-1整数规划模型与非线性规划模型。针对问题一，我们先对所给数据进行初步分析，确定运用模糊数学的聚类分析法，根据面包烘烤时间的不同把面包大致分成4组，然后通过建立0-1整数规划模型，使用Lingo软件，设计出一个最优烘烤方案，并得出了烤箱工作的时间为259分钟。评价方案性能的优劣指标为数据的波动情况。针对问题二，要使得三台烤箱的工作时间尽可能短，即求三台烤箱中工作

2、时间最长的烤箱的工作时间尽可能的小，我们运用目标规划模型，建立目标函数和求出约束条件，利用lingo编程，最后得出三台烤箱的工作时间分别为85,87,87分钟。评价方案性能的优劣指标为数据相对于平均值的波动情况，得出方案为较优。针对问题三，由于各个面包在烘烤前还需要一定的准备时间，且还需要考虑“烘烤所需时间”、“所占烤箱容量”等因素。考虑因素多重性和交互性，我们运用贪心算法的思想，建立0-1整数规划模型，利用lingo编程，求得烤箱所需的工作时间为274分钟。关键字：工作时间 0-1整数规划和非线性规划模型 贪心算法 lingo软件一、 问题重述一个面包房现有一些面包需要放入烤箱烘烤，烤箱的容

3、量为40个单位，每个面包烘烤所需要的时间（分钟）和所占用的烤箱容量（单位）如下表所示：烘烤所需时间（分钟）101692116148101210911148131717所占烤箱容量（单位）129151020161012172414691071921烘烤所需时间（分钟）910131481720151612810918101311所占烤箱容量（单位）12916851716891214111924141216烘烤所需时间（分钟）211615172422261218111516914121913所占烤箱容量（单位）96211510149221681415169142316面包的烘烤规则如下：大小不同，烘

4、烤时间不同的面包可以同时烘烤，但是不能和比自己的烘烤时间大于5分钟的放在一起烘烤，以免烤坏。一旦烤箱开始工作，中间不能打断，也不允许移走正在烘烤的面包。（一）请为面包房设计一个烘烤方案，使得烤箱的工作时间尽可能短；并且评价该方案的性能优劣。（二）假设现有另外两台烤箱可供同时使用，请另外为面包房设计一个烘烤方案，使得三台烤箱的工作时间尽可能短；并且评价该方案的性能优劣。（三）假设各个面包在烘烤前还需要一定的准备时间（制作，发酵），各个面包的准备好的时刻列表如下（对应于上表的面包顺序），只有在准备时间之后面包才可以开始烘烤。现只有一台烤箱可供使用，请为面包房设计一个烘烤方案。面包准备好的时刻（分钟

5、）61619314212281319263921343831727面包准备好的时刻（分钟）9271630294322263311451724823332面包准备好的时刻（分钟）825282336193512362739111723132431二、问题的假设1.表中的数据真实可靠；2.在烘烤过程中烤箱都能正常工作；3.三台烤箱的性能，规格，及功率都是一样的；4.每次面包装箱，出箱的时间都很短；5.每个面包在烤箱中受热都是均匀的；三、符号说明：每组烘烤面包的最大时间；：烤箱工作的总时间；：第i次烘烤的第j块面包；：为0-1变量，取0时表示第i次不烘烤第j块面包，取1时第i次烘烤第j块面包；：为每组

6、面包烘烤时间的波动程度；：每次烘烤时面包所占烤箱的容积；：为第i次烘烤时第j块面包所用的时间；：为18组面包烘烤时间的波动程度的均值；：为第i次烘烤时的平均时间；：第一台烤箱工作的总时间；第二台烤箱工作的总时间；第二台烤箱工作的总时间；第一台烤箱工作在第组数据最大时间；第二台烤箱工作在第组数据最大时间；第三台烤箱工作在第组数据最大时间；为0-1变量，为1时第组数据最大时间在第一台烤箱进行烘烤，为0时则不在；为0-1变量，为1时第组数据最大时间在第二台烤箱进行烘烤，为0时则不在；为0-1变量，为1时第组数据最大时间在第三台烤箱进行烘烤，为0时则不在；第台烤箱工作的总时间；平均时间；四、问题的分析

7、2.1 问题一的分析通过对表中数据整理，我们以任一个面包不能和比自己的烘烤时间大于5分钟的放在一起烘烤的情况，为首要条件。为此我们以最大烘烤时间26分钟为起点，以极差5为间隔，分别在区间2621,2016,1511,106,大致把数据分成4类。然后再利用0-1规划模型，综合考虑所有面包烘烤所需时间，以及面包烘烤时所占的烤箱的容积这两个目标，最终把51个面包对应的数据分成了18组，用标准差对18组进行了检验，按此方案，烘烤面包组成一组性能优的占83%，中等的占6%，一般的占11%。2.2 问题二的分析其他都不变的条件下，现有另外两台烤箱加入，即有三台烤箱可供同时使用，使三台烤箱的工作时间尽可能短

8、，为了使烤箱烘烤安排更加合理，我们只需使三台烤箱中工作时间最长的烤箱的工作时间尽可能的小，为此我们建立目标规划模型，建立目标函数和求出约束条件，目标函数即为的最大值尽可能最小，约束条件为每组数据只能其中一台烤箱。在运用lingo进行编程，最终解出三台烤箱的工作时间分别为85,87,87分钟。2.3 问题三的分析问题三由于各个面包在烘烤前还需要一定的准备时间（制作，发酵），且只有在准备时间之后面包才可以开始烘烤，则对于该问题我们需要考虑三方面的因素即：烘烤所需时间，所占烤箱的容量，面包准备好的时间。由于因素多重性和交互性，我们只能根据贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就

9、是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。再根据数据不断对所得的解进行优化。建立0-1整数规划模型，目标函数工作时间最短，需考虑不能和比自己的烘烤时间大于5分钟的放在一起烘烤和各面包的容量之和的最大需小于烤箱的容量即小于40个单位等约束。利用lingo编程，求得烤箱所需的工作时间为274分钟。五，模型的建立与求解51问题一的解答针对问题一我们建立了模型一。51、1模型一的建立51、2确定目标函数本文研究的是面包烘烤时间与面包所占烤箱容积的分配问题，对此我们

10、不能主观的人为进行分配，所以我们建立了0-1规划模型对问题进行优化求解。；通过线性约束条件及目标函数的取值我们把51个不同面包的数据分成了18组如下表1.表1面包烘烤时间的分组统计表组号123456烘烤所需时间（分钟）2624222121201917181817161616131313所占烤箱容量（单位）9101410916231716241569916167组号789101112烘烤所需时间（分钟）1616151414141212121111141312151511所占烤箱容量（单位）620148991422176161612122188组号131415161718烘烤所需时间（分钟）109

11、9101091010910917178888所占烤箱容量（单位）12121514121491119241621195101014每组取其最大值作为烘烤面包时所需时间，然后对每组最大时间加和就是烤箱所工作的时间，对第10组数据和第13组数据做适当的调整可以做到进一步优化，调整方法：把第13组的所需时间10，以及所占烤箱容量12调到第10组可使烤箱所工作的时间更小。表2每组面包烘烤的实际时间组号123456789所需最长时间262119181713161412组号101112131415161718所需最长时间1114159101010178根据上述计算公式，最终得出烤箱工作的时间为260分钟.5

12、1、2对方案的评价按照实际生活中面包烘烤的时间不能小于所需时间，同时在满足所需时间时的同时也不能过大，对此我们以每组面包实际烘烤时间的波动程度进行评价评价的标准综合评价标准为了反映面包被烘烤后的质量好坏，我们找到了体现面包程度的波动程度的取值范围如下表表3波动程度取值范围表等级优中等一般取值范围对18组数据进行波动程度运算，我们最终得出了每组烘烤时间的波动值表4 18组烘烤时间波动范围表组号123456789标准差组号101112131415161718标准差综合评价标准，面包的质量优的占73%，中等占16%，一般占11%从上述数据可以看出，通过该方案烘烤出来的面包波动范围小于1，面包的质量优

13、的与中等之和占到了总数的89%.故此方案在一定程度使得面包被烘烤时间，以及面包所占烤箱容量达到了一定程度的上的合理优化。5.2问题二的解答针对问题二我们建立了模型二。5.2、1模型二的建立5.2、2确定目标函数该模型是为了解决烤箱烘烤安排问题，由于有三台烤箱可供同时使用，且使三台烤箱的工作时间尽可能短，为了使烤箱烘烤安排更加合理，我们只需使三台烤箱中工作时间最长的烤箱的工作时间尽可能的小。所以我们建立了如下的目标函数：其中：，。当工作时间最长的烤箱的工作时间都是很小的时候，那问题也得以解答。5.2、3确定约束条件（I）由于烤箱的容量为40个单位，则每次烤箱烘烤面包时最大单位不要大于40个单位。

14、对于问题一解出一个烤箱在工作时间尽可能短的烘烤方案，最终得出18组数据，我们分别取出18组数据最长的时间，标记为。表5每组烤箱的工作时间262119181713161412111415991010178表：每次烘烤面包的最长时间（分钟）则 ，其中：， 分别为18组数据某组数据是在三台烤箱的某台烤箱中。（II）由于18组数据的某组数据只能在其中一台烤箱内进行烘烤。即： 5.2、4综上所述，得到问题二的目标最优化模型目标函数： 根据约束条件和lingo得出问题结果（程序见附录）。三台烤箱的工作时间分别为87分钟,88分钟,88分钟。安排方法为：时间为分钟，容量为单位。第一台烤箱的安排方法：表6第一

15、台烤箱的安排方案组号一、二、三、四、五、烘烤所需（分）26242221212013131317178888所占容量91014109161616721191451010第二台烤箱的安排方法：表7第二台烤箱的安排方案组号一、二、三、四、五、六、烘烤所需（分）18171818141414121212131214101010所占容量23171624989142217121216141212第三台烤箱的安排方法：表8第三台烤箱的安排方案组号一、二、三、四、五、六、七、烘烤所需（分）17161616161615111111101515109999109所占容量15699620146168921811121

16、5191524165.2、6方案的评价根据上述可以得出三台烤箱得出工作时间分别为85,87,87分钟，由于我们的目标是使三台烤箱中工作时间最长的烤箱的工作时间尽可能的小，而对于一个确定的数（三台烤箱的总的工作时间为259分钟），把它分成三份，要使它最大的数尽可能的小，则这三个数相等即可。但考虑实际情况三台烤箱的工作时间不可能相等，所以给出方案评价准则：三个数相对于平均值波动大小。根据计算可得，而对于，即三个数相对于平均值波动大小较小，所以这种方案可以使得三台烤箱工作时间尽可能短，该方案性能为较优。5.3问题三的解答针对问题三我们建立了模型三。5.31模型三的建立对于问题三由于各个面包在烘烤前还

17、需要一定的准备时间（制作，发酵），且只有在准备时间之后面包才可以开始烘烤，则对于该问题我们需要考虑三方面的因素即：烘烤所需时间，所占烤箱的容量，面包准备好的时间。由于因素多重性和交互性，我们只能根据贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。再根据数据不断对所得的解进行优化。步骤一：而由于只有在准备时间之后面包才可以开始烘烤，根据贪心算法所以我们首先考虑面包准备好的时间，根据题目给出的数据面包准备

18、时间最短为3分钟，给出时间较短数据：表9面包准备好的较短时间烘烤所需时间10139181321所占烤箱容量1271224129准备好的时间639838要使烘烤时间最短，即步骤中烘烤所需时间最长的尽可能的小。所以我们建立了如下的目标函数：而需考虑不能和比自己的烘烤时间大于5分钟的放在一起烘烤。即： 且各面包的容量之和的最大需小于烤箱的容量即小于40个单位。即： 根据计算得出最先开始烘烤的面包为：烘烤所需时间分别为10,13,13;所占烤箱的容量分别为12,7,12.步骤二：由于步骤一准备时间花费6分钟，烘烤所需时间为13分钟，即一共花费19分钟。所以准备时间小于或等于19分钟，在这时都可以放入烤

19、箱内进行烘烤。我们将其整理可得：时间为分钟，容量为单位。表10三值对应表烘烤所需时间（分）18219121612141012131691017912所占烤箱容量249121215221612141691611191517准备好的时间88911111212131316161717171919根据要使烘烤时间最短，即步骤中烘烤所需时间最长的尽可能的小。所以我们建立了如下的目标函数：约束条件：各面包的容量之和的最大需小于烤箱的容量即小于40个单位。需考虑不能和比自己的烘烤时间大于5分钟的放在一起烘烤。综上所述，得到该问题的目标最优化模型目标函数： 根据约束条件和lingo得出问题结果（程序见附录），

20、烘烤所需时间分别为：9,9,10；所占烤箱的容量分别为：12,16,12；面包准备好的时间分别：9,17,13.步骤三：由于步骤一花费19分钟，步骤二烘烤所需时间为10分钟，即一共花费29分钟。所以准备时间小于或等于29分钟，在这时都可以放入烤箱内进行烘烤。类似步骤二，将小于或等于29分钟的整理出来（见附录）。与步骤二的约束条件与目标函数相同，根据lingo得出实验结果，烘烤所需时间分别为：10,10,8,8；所占烤箱的容量分别为：11,14,10,5；面包准备好的时间分别：17,23,28,29.步骤四：由于步骤一、二花费29分钟，步骤三烘烤所需时间为10分钟，即一共花费39分钟。所以准备时

21、间小于或等于39分钟，在这时都可以放入烤箱内进行烘烤。类似步骤二，将小于或等于39分钟的整理出来（见附录）。与步骤二的约束条件与目标函数相同，根据lingo得出实验结果，烘烤所需时间分别为：11,8,9；所占烤箱的容量分别为：16,10,14；面包准备好的时间分别：32,38,26.由于步骤三烘烤所需时间11分钟，即一共花费50分钟。而最大准备时间为45分钟，即从步骤四开始，由于烘烤时间以大于面包最大准备好时间（），除步骤一、二、三、四的数据，所有数据都可以进行运算。根据问题一的解法，得出烘烤方案。表11烘烤方案表步骤一、二、三、四、五、烘烤所需时间（分钟）131310910910108811

22、8914141412所占烤箱容量（单位）71212121216111410516101498914面包准好的时刻（分钟）336913171723282932382634302313步骤六、七、八、九、十十一、十二、烘烤所需时间（分钟）101082624221917171718182121201616所占烤箱容量（单位）2491491014231721192416910162015面包准好的时刻（分钟）26274535361924432717836831224211步骤十三、十四、十五、十六、十七 十八、烘烤所需时间（分钟）17161616119912111215131512131514所占烤箱

23、容量（单位1599661519128178161422162116面包准好的时刻（分钟）2333162521192411271926313912162812【注】：由于考虑到各个面包在烘烤前还需要一定的准备时间（制作，发酵），从步骤一开始到步骤四是必须按照此顺序才能使方案最优，从步骤四开始，由于烘烤时间以大于面包最大准备好时间（），步骤可以不按照上表顺序。六，模型的评价，推广与改进6,1对模型的评价模型的优点（1）通过0-1规划模型，我们很好的把数据分成了18组，再通过进一步的优化，求出了所需时间的最小值。（2）增加台数的情况下，合理运用动态规划，使三台烤箱工作时间接近均衡，最终求得分别工作时

24、间最优解为85,87，87分钟。（3）在考虑增加面包准备时间的情况下，我们采用了贪心算法，此方法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。模型的缺点（1）虽然0-1规划模型贯穿论文的三个问题，但在问题一，对数据进行分组时，不能很好的分配，部分数据还是人为的进行了组合。（2）在采用贪心算法时只能使局部达到最优，不能是全局达到最优解，在求解烤箱工作最短时间上造成了一定的困难。6.2模型的推广与改进0-1规划模型不仅适合面包烘烤时间的最优化问题，也非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码

25、选取、可靠性等人们所关心的多种问题。七，参考文献1,2韩中庚 数学建模方法及其应用第2版 高等教育出版社 2009赵静 但琦 数学建模与数学实验第2版 高等教育出版社 20033谢金星 薛毅 优化建模与LINDO/LINGO软件第2版 清华大学出版社 2011贪心算法，浏览时间2012年7月27日。七，附录编写的程序及运行产生的数据model:sets:row/1.3/;col/1.18/;matrix(row,col):x;ENDSETSmin=smax(w,y,z);W=t1*x(1,1)+t2*x(1,2)+t3*x(1,3)+t4*x(1,4)+t5*x(1,5)+t6*x(1,6)+

26、t7*x(1,7)+t8*x(1,8)+t9*x(1,9)+t10*x(1,10)+t11*x(1,11)+t12*x(1,12)+t13*x(1,13)+t14*x(1,14)+t15*x(1,15)+t16*x(1,16)+t17*x(1,17)+t18*x(1,18);y=t1*x(2,1)+t2*x(2,2)+t3*x(2,3)+t4*x(2,4)+t5*x(2,5)+t6*x(2,6)+t7*x(2,7)+t8*x(2,8)+t9*x(2,9)+t10*x(2,10)+t11*x(2,11)+t12*x(2,12)+t13*x(2,13)+t14*x(2,14)+t15*x(2,15

27、)+t16*x(2,16)+t17*x(2,17)+t18*x(2,18);z=t1*x(3,1)+t2*x(3,2)+t3*x(3,3)+t4*x(3,4)+t5*x(3,5)+t6*x(3,6)+t7*x(3,7)+t8*x(3,8)+t9*x(3,9)+t10*x(3,10)+t11*x(3,11)+t12*x(3,12)+t13*x(3,13)+t14*x(3,14)+t15*x(3,15)+t16*x(3,16)+t17*x(3,17)+t18*x(3,18);X(1,1)+X(2,1)+X(3,1)=1;X(1,10)+X(2,10)+X(3,10)=1;X(1,2)+X(2,2)

28、+X(3,2)=1;X(1,3)+X(2,3)+X(3,3)=1;X(1,4)+X(2,4)+X(3,4)=1;X(1,5)+X(2,5)+X(3,5)=1;X(1,6)+X(2,6)+X(3,6)=1;X(1,7)+X(2,7)+X(3,7)=1;X(1,8)+X(2,8)+X(3,8)=1;X(1,9)+X(2,9)+X(3,9)=1;X(1,11)+X(2,11)+X(3,11)=1;X(1,12)+X(2,12)+X(3,12)=1;X(1,13)+X(2,13)+X(3,13)=1;X(1,14)+X(2,14)+X(3,14)=1;X(1,15)+X(2,15)+X(3,15)=1

29、;X(1,16)+X(2,16)+X(3,16)=1;X(1,17)+X(2,17)+X(3,17)=1;X(1,18)+X(2,18)+X(3,18)=1;gin(x(1,1);gin(x(1,2);gin(x(1,3);gin(x(1,4);gin(x(1,5);gin(x(1,6);gin(x(1,7);gin(x(1,8);gin(x(1,9);gin(x(1,10);gin(x(1,11);gin(x(1,12);gin(x(2,1);gin(x(2,2);gin(x(2,3);gin(x(2,4);gin(x(2,5);gin(x(2,6);gin(x(2,8);gin(x(2,9

30、);gin(x(2,10);gin(x(2,11);gin(x(2,12);gin(x(3,1);gin(x(3,2);gin(x(3,3);gin(x(3,4);gin(x(3,5);gin(x(1,13);gin(x(1,14);gin(x(1,15);gin(x(1,16);gin(x(1,17);gin(x(1,18);gin(x(3,6);gin(x(3,7);gin(x(3,8);gin(x(3,9);gin(x(3,10);gin(x(3,11);gin(x(3,12);gin(x(2,13);gin(x(2,14);gin(x(2,15);gin(x(2,16);gin(x(2

31、,17);gin(x(2,18);gin(x(3,13);gin(x(3,14);gin(x(3,15);gin(x(3,16);gin(x(3,17);gin(x(3,18);data:t1=26;t2=21;t3=19;t4=18;t5=17;t6=13;t7=16;t8=14;t9=12;t10=11;t11=14;t12=15;t13=9;t14=9;t15=10;t16=10;t17=17;t18=8;enddataendLocal optimal solution found. Objective value: 87.00000 Objective bound: 87.00000

32、Infeasibilities: 0.000000 Extended solver steps: 16817 Total solver iterations: 897411 Variable Value W 85.00000 Y 87.00000 Z 87.00000 T1 26.00000 T2 21.00000 T3 19.00000 T4 18.00000 T5 17.00000 T6 13.00000 T7 16.00000 T8 14.00000 T9 12.00000 T10 11.00000 T11 14.00000 T12 15.00000 T13 9.000000 T14 9

33、.000000 T15 10.00000 T16 10.00000 T17 17.00000 T18 8.000000 X( 1, 1) 1.000000 X( 1, 2) 1.000000 X( 1, 3) 0.000000 X( 1, 4) 0.000000 X( 1, 5) 0.000000 X( 1, 6) 1.000000 X( 1, 7) 0.000000 X( 1, 8) 0.000000 X( 1, 9) 0.000000 X( 1, 10) 0.000000 X( 1, 11) 0.000000 X( 1, 12) 0.000000 X( 1, 13) 0.000000 X(

34、 1, 14) 0.000000 X( 1, 15) 0.000000 X( 1, 16) 0.000000 X( 1, 17) 1.000000 X( 1, 18) 1.000000 X( 2, 1) 0.000000 X( 2, 2) 0.000000 X( 2, 3) 1.000000 X( 2, 4) 1.000000 X( 2, 5) 0.000000 X( 2, 6) 0.000000 X( 2, 7) 0.000000 X( 2, 8) 1.000000 X( 2, 9) 1.000000 X( 2, 10) 0.000000 X( 2, 11) 1.000000 X( 2, 1

35、2) 0.000000 X( 2, 13) 0.000000 X( 2, 14) 0.000000 X( 2, 15) 1.000000 X( 2, 16) 0.000000 X( 2, 17) 0.000000 X( 2, 18) 0.000000 X( 3, 1) 0.000000 X( 3, 2) 0.000000 X( 3, 3) 0.000000 X( 3, 4) 0.000000 X( 3, 5) 1.000000 X( 3, 6) 0.000000 X( 3, 7) 1.000000 X( 3, 8) 0.000000 X( 3, 9) 0.000000 X( 3, 10) 1.000000 X( 3, 11) 0.000000 X( 3, 12) 1.000000 X( 3, 13) 1.000000 X( 3, 14) 1.000000 X( 3, 15) 0.000000 X( 3, 16) 1.000000 X( 3, 17) 0.000000 X( 3, 18) 0.000000 Row Slack or Surplus 1 87.00000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8