面包店问题课件

数学建模论文答辩题B：面包店问题单位：环工111李功松环工111方爱冬信息121陈玲玲摘要

本文解决的是烤箱烘烤面包问题。通过分析我们建立了相应的数学模型，并通过对问题进行求解与分析。

首先就问题一，我们将烘烤方案设计为三种。生产模型一：同一烤箱烘烤同种面包。生产模型二和生产模型三：混合烘烤。由于我们对模型一和生产模型二进行了一些条件上的假设与限制，所以较为简单，我们并未进行深入探讨。之后，我们紧密联系了烤箱烘烤面包的实际情况，对模型而进行了较为严谨、科学的分析。诸如：烤箱的容积，各种类面包的体积，以及烘烤的时间差等限制性因素。我们先对一台烤箱进行分析。确定运用模糊数学的聚类分析法，然后通过建立0-1整数规划模型，使用Lingo软件设计出一个最优烘烤方案。对两台烤箱的工作时间尽可能短，即求两台烤箱的工作时间最长的烤箱的工作时间尽可能的小。我们运用非线性规划模型，建立目标函数和求出约束条件，再次利用Lingo软件编程解决问题。针对问题一，为了使模型更加形象化，易于理解。我们通过收集到的数据对所建立的模型进行检验。而且，为了评价出方案的优劣，我们将以数据的波动程度而定。

然后就问题二，根据市场分析进行生产条件的假设，建立目标函数，线性与非线性规划模型，确定约束条件，然后运用Lingo软件编写程序对数据进行处理从而得出面包店的生产计划，以获得最大的利润。

关键字：面包烘烤时间函数

0-1整数规划模型和非线性规划模型

Lingo软件市场分析调查

面包最大利润函数

线性规划模型一、问题分析1.1

这个优化问题的目标就是要使面包店的收益最大，要做的决策就是生产计划，而宾馆所需的面包的样式和总数已经提前知道了，所以只需考虑面包烘烤的时间。显而易见，问题就转化到了如何安排烤箱的烘烤计划，才能使其在最短时间的时间内完成既定的烘烤任务。通过建立模型从而求出的时间的最小值，即为利润最高的最优解。1.2

此问题应该结合市场来分析，目前消费市场竞争日趋激烈，面包店的整体布局也应该随着由于每一天是的不稳定性以及一些问题的不确定性，所以为了问题处理的方便，我们对求解的模型做了一些合理化的假设：1.不考虑产品需求预测估计值的误差，也不考虑产品各项成本费用在此阶段时间的变化。

2、为了方便起见，时间和产量都作为离散量处理。固定的认为该天产品的数量。

3、面包的种类要配合地点和顾客阶层，才会有理想的销售量。代替点心的甜面包、填饱肚子的调理面包、土司之类的主食面包等等，会因位于商业区、办公区或住宅区而有不同的销路。另外，供应薪水阶级、职业妇女或学生的面包种类也有不同。二、问题的假设1、每次烘烤拿出、放入面包的时间忽略不计2、烤箱预热时间忽略不计3、面包准备好以后，停放时间不影响其烘烤时间4、烤箱的烘烤效率不随时间变化5、烤箱的烘烤效率与面包所占烤箱容量无关6、两台烤箱的性能、规格，及功率是一样的7、在烤箱中面包之间相互独立，互不影响8、每个烤盘的容积是一样的三、符号说明：烤箱烘烤的总时间（某一个批次）：宾馆烤制完成四个批次的面包所花费的总时间：第i台烤箱工作总时间：第一台烤箱工作总时间：第二台烤箱工作总时间D:每个烤盘的容积：第i种面包的体积：第j组第i种面包的体积：为同一烤箱中第i次烘烤时第j块面包所用的时间：同一个烤箱中的第i种面包烘烤所需的时间：第一、二、三、四批中烤制时间最长的i=1,2,3,4：宾馆每批面包中各种样式所需的数量n：每个烤箱烤盘的数量：第一、二、三、四批宾馆所需面包的数量f=1,2,3,4：宾馆每批面包烘烤总工作时间f=1,2,3,4：同一个烤箱中第i组烘烤面包的最长时间：同一个烤箱中第i组烘烤面包的最短时间：第一台烤箱中第i组烘烤面包的最长时间：第二台烤箱中第i组烘烤面包的最短时间d：混合烘烤的面包所能承受的最大时间间隔z：某一个烤箱工作的总时间：第i组中地j种面包的系数（0或1）等于0表示该面包不烘烤等于1表示该面包烘烤：第i组中第j种面包所对应的最大时间系数：第i组中第j种面包所对应的最小时间系数：为0-1变量，为1是第i组数据最大时间在第一台烤箱进行烘烤，为0时则不在：为0-1变量，为1是第i组数据最大时间在第二台烤箱进行烘烤，为0时则不在:每个烤箱的平均工作时间：为每组面包烘烤时间的波动程度：为m组面包烘烤时间的波动程度的均值（m为面包的组数）（注：部分符号的说明在模型建立的过程中讲解）四、模型的建立与求解问题一的解答

针对问题一我们建立了模型一和模型二以及模型三。

模型一的建立

确定目标函数（同一烤箱烘烤同种面包）

此种条件下，我们并未严格考虑同一个烤箱中各个烤盘间的关系，为了处理的方便，人为地认为同一个烤箱中的各个烤盘是一个整体，而不是相互独立的（指的是烤盘的容积与面包的体积之间的关系）。我们假设总利润最大，然后对第一批面包生产所需时间（当烘烤时间最小时，收益最大）建立模型。

同理：第二、三、四批时间计算一样。时间分别为，因此烘烤花费的总时间为

对方案的评价首先此种方案未考虑现实中各个烤盘间的相互关系，而是将其作为一个整体来看。这样在有些情况下，就扩大化了烤箱的实际容量，因为烤盘与烤盘之间不可能拼凑起来，显然这是不切合实际的。所以此种情况下，得到的利益是偏大的。即

模型二的建立

确定目标函数

（混合烘烤，即同一烤箱中同时烘烤多种面包，则烘烤时间以最后烘烤完成的面包时间计算）

为了数据处理的方便，我们假设此种情况下烤箱的容积足够大。即一次性可以完成每个批次的烘烤任务。同时也认为各种类的面包的烤制时间相近。当需要较短时间烤熟面包再次放进去烤的面包的烤制时间不能比之前所需烤制时间最大的大，并且一次可以全部烤完每一批所需的该种类面包。则有：

因此烘烤完成四批面包所花费的总时间

对方案的评价此方案虽然进行了混合烘烤，但是实际生产中，烤箱几乎是不可能一次就将所有的生产任务完成，还有将不同种类的面包放在一起烘烤，这会影响面包的质量，显然这是不切合实际的。此种情况下，得到的利益是偏大的。即模型三的建立确定目标函数

对模型三进行了一些合理化的假设：

1）考虑烤盘的容积与面包体积之间的关系，以及同一个烤箱中烤盘与烤盘之间的关系（即将每个烤盘在其容积上单独考虑）。

2）通过查阅资料我们得知在实际烘烤面包的过程中：大小不同的面包可以同时烘烤，但是不能比自己的烘烤时间大于一定时间的面包放在一起烤，以免烤坏。一旦烤箱开始工作，中间不能打断，也不允许移走正在烘烤的面包。（我们设最大时间间隔为d）。

分析：本问题中各类面包必须取整数，不能将其分散处理，此符合整数规划的先决条件；又有面包只有可以被烘烤和不可以被烘烤两种情况，此符合0-1规划的变量取值条件，故从整体方面来看，本问题采用0-1整数规划最为适宜。设问题的决策变量为是0-1变量，即

题中所设的容量约束条件是：（对某一个烤盘而言）

题中所假设的时间约束条件是：（对某一个烤箱而言）

同理我们可以得到同一个烤箱的其他烤盘的时间与容量的约束条件，从而可以确定目标函数烘烤总时间为：

，由上述分析可得出该问题0-1规划模型为：为了使烤箱烘烤安排更加合理，我们只需使两台烤箱中工作时间最长的工作时间尽可能的小。所以我们建立了如下的目标函数：其中：

，

。当工作时间最长的烤箱的工作时间都是很小时候，那问题就得以解决了。确定约束条件（I），其中：，分别为m组数据某组数据是在两台烤箱的某台烤箱中进行的。（m为组数）（II）由于m组数据的某组数据只能在其中一台烤箱内进行烘烤。即：

，i=1,2,3,...,m综上所述，得到问题一的目标最优化模型。目标函数：

同理我们也可以得出其他批次的数学模型。最后再根据提供的数据，利用Lingo软件得出问题的结果。对方案的评价按照实际生活中面包烘烤的时间不能小于所需时间，同时满足所需时间的同时也不能过大，对此我们以每组面包实际烘烤时间的波动程度进行评价

评价的标准

综合评价标准

为了反映面包被烘烤后的质量的好坏，我们找到了体现面包烘烤时间的波动程度的取值范围如下表

波动程度取值范围表由于我们的目标是使两台烤箱中工作时间最长的烤箱的工作时间尽可能的小，而对于一个确定的数（两台烤箱总的工作时间）把它分成两份，要是它最大的数尽可能的小，则两个数相等即可。但考虑到实际情况两台烤箱的工作时间可能不相等，所以给出方案评价准则：两个数相对于平均值波动大小。

i=1,2通过以上分析，可以得出：波动程度越小，所求得的方案就越好。等级优中等一般取值范围0-11-22-5对模型的检验为了使我们见了的模型更具有说服力，使结果更加形象化。我们通过查阅资料得到了一组数据如下表：

面包烘烤所需时间与所占容量表并且我们假设最大时间间隔d=5min，D=40（单位）。同时为了数据处理的方便，我们小组假设了每个烤箱仅有一个烤盘，且对某个批次数据处理（如第一批）。注：这种加假设是合理的，我们只是将问题简化了而已。这是不影响对模型效果的判定的。对模型一的检验

通过对上述数据的分析，我们可以观察到同种类的面包很少，所以所求的时间会很大，因此没有必要对此模型进行数据检验。（没有意义）

对模型二的检验

此假设条件下，该模型的诸多假设显然都是不合理的。如烤箱的容积，面包烘烤的时间间隔等。因此没有必要对此模型进行数据检验。（没有意义）对模型三的检验通过之前的线性约束条件及目标函数的取值我们把51个不同面包的数据分成了18组如下。（见程序一）每组取其最大值作为烘烤面包时所需时间，然后对每组最大时间之和就是烤箱所工作的时间；

对第10组数据和第13组数据做适当的调整可以做到进一步优化，调整方法：把第13组的所需时间10，以及所占烤箱容量12调到第10组可使烤箱所工作的时间更小。

每组面包烘烤的实际时间组号 1 2 3 4 5 6 7 8 9所需最长时间 26 21 19 18 17 13 16 14 12组号 10 11 12 13 14 15 16 17 18所需最长时间 11 14 15 9 10 10 10 17 8根据上述计算公式，最终得出烤箱工作的时间为260分钟。

对18组数据进行波动程度运算，我们最终得出了每组烘烤时间的波动值

18组烘烤时间波动范围表组号 1 2 3 4 5 6 7 8 9标准差 2.83 0.82 1.4 0 0.87 0 0.82 1.73 0组号 10 11 12 13 14 15 16 17 18标准差 0 1.4 3.27 0.82 0.87 0.87 0.71 0 0综合评价标准，面包优的占73%，中等占16%，一般占11%。从上述数据可以看出，通过该方案烘烤出来的面包波动范围小于1，面包的质量优的与中等的之和占到了总数的89%。故此方案在一定程度上是的面包被烘烤时间，以及面包所占容量达到了一定程度上的合理化。对两台烤箱同时工作进行考虑。根据之前的约束条件和Lingo得出问题结果（见程序二）.由于该组数据较为特殊安排生产计划有多种，我们也不便一一列举。下面只给出一种生产计划。第一台烤箱的安排方法：

第二台烤箱的安排方法：根据上述可以得出两台烤箱的工作时间分别为130,130分钟。显然可以求得s=0，即两个数相对于平均值没有波动，所以这种方案可以使得两台烤箱工作时间最短，该方案性能为最优。当然这组数据具有特殊性。对模型的比较理论上讲，三种模型的原材料生产成本是一样的，只需比较各种模型工作总时间的长短即可，时间长的生产模型消耗的成本更高，故时间较短的为较优模型。但考虑到实际情况，三种模型在绝大多数情况下是不具备可比性的，只有在一些特殊条件下，三种模型之间才有可比性。问题二的解答

模型四的建立

确定目标函数

面向大众零售服务与固定宾馆批量销售，我们在考虑面包烘烤时间的同时，也要考虑面包销售的利润。也就是说我们为了使所建立的模型满足效益最大化，既要在最短的时间内完成生产任务，又要使所获得利润最大化。对于时间最优化的问题，我们前面已经通过0-1整数规划模型做了较好的解决，在这里我们就不在做过多的说明了。所以，对该模型的建立我们将着重从面包销售的利润方面进行分析建立模型。为了使模型建立起来的方便，我们做出了如下表：

面包店日生产情况表样式日生产量日销售量单价（元）成本（个/元）利润（个/元）日定向销售量A1S1H1Y1Q1C1B1A2S2H2Y2Q2C2B2A3S3H3Y3Q3C3B3.....................AmSmHmYmQmCmBm1.每种样式利润2.由此我们可以求得面包的总利润确定约束条件在确定这个目标函数的约束条件之前，我们有必要了解一下市场分析中面包的销量在一天中随时间变化的关系，如下图：通过图示，我们不难得出这样的结论：1）面包的销量在一天的开始的一段时间以及一天结束的一段时间销量是极小的，几乎可以忽略不计。2）面包在某段时间内的需求量达到最大值，紧接着随着时间的推移面包的销量呈下降趋势。很显然，这是与绝大多数的人的作息习惯相互吻合的。

对某段（如一个月）时间内相同时间段进行比较。不难得出，各个时间段内的日销售量总是有一个极值。所以，根据以上分析，我们将一天划分为四个时间段（对应各个批次）来进行分析，如下表：

面包日销售能力与生产能力和时间的关系表批次

日时间段 日销售能力（个） 日生产能力（个）第一批次 6:00-10:00

y1

x1第二批次 10:00-14:00

y2

x2第三批次 14:00-18:00

y3

x3第四批次 18:00-22:00

y4

x4为了更能反映日销售能力的具体情况，我们具体到了对每一种面包的市场调查分析，如下表：

各种样式的面包的日销售能力样式A1A2A3...Am日销售能力（个）H1H2H3...Hm因此，该模型的约束条件为：且有：由此我们就可以运用Lingo软件得出该模型的求解结果。对方案的评价该模型的创新之处就在于在考虑面包销量时结合了市场分析与调查，很大程度上联系到了实际生活，具有较为普遍的应用价值。但是也有不妥之处，就是在市场调查时，对于调查方案的设定要求很高，否则便不能准确地反映面包需求量与时间的关系。对模型的检验我们通过对我们学校周围的一家面包店进行了市场调查分析（主要是对宾馆服务）。该家面包店一共生产十种面包。具体调查得到的数据，我们在下面以表格的形式展现出来。样式

日生产量

日销售量

单价（元）成本（个/元）利润（个/元）

日定向销售量A1 S1 H1 2

1

C1

20A2 S2 H2 2

1

C2

10A3 S3 H3 2.5

1.5

C3

40A4 S4 H4 2.5

1.5

C4

50A5 S5 H5 2.5

2

C5

100A6 S6 H6 3 2

C6

60A7 S7 H7 3

2.5

C7

40A8 S8 H8 3.5

2.5

C8

30A9 S9 H9 3.5

3

C9

30A10 S10 H10 4

3

C10

20

该面包点各种样式的面包的日零售能力（面向大众销售）样式

A1

A2

A3

A4

A5

A6

A7

A8

A9

A10日销售能力

20

20

15

20

50

30

20

10

10

5

该面包店的日生产能力（各个批次）

批次

一

二

三 四日生产能力（个） 300 200 100 50然后我们将表中的数据依次带入到之前已经建立好的模型当中去，再利用Lingo软件编写程序对其求解（见程序三）。具体得到的结果如下：且有：S1+S2+S3+S4+S5+S6+S7+S8+S9+S10<=650H1+H2+H3+H4+H5+H6+H7+H8+H9+H10<=200求目标函数：五、模型的评价对模型的评价1模型的优点（1）通过对模型一与模型二分析，联系到了实际的生产情况我们之后建立了模型三。其主要是0-1整数规划模型，我们很好的把数据分成了若干组，再通过进一步的优化，求出了所需时间的最小值。（2）增加台数的情况下，合理运用动态规划，使两台烤箱工作时间接近均衡，最终求出其最优解。（3）对问题二，我们运用市场调查分析将面包店生产过程中不确定的因素大体上明确了，在生产过程中有了一个生产方向。从而较好地运用Lingo求解出线性与非线性模型方程。2模型的缺点（1）对问题一，虽然0-1规划模型较模型一与模型二有了很大的改善，但在具体处理某些比较特殊的数据时，不能很好地分配，部分数据还是人为的进行了组合。（问题中假设的数据就属于这种情况）（2）对问题二，虽然市场调查给面包店生产提供了方向，但这种方向很大程度上是不够精确的，无法使面包店的效益得到最大化。（3）零售和批发的利润不一样，但烘烤时间一样，我们的模型则把零售与批发的利润等同考虑了。（4）面包在烘烤过程中，我们认为的忽略了一些限制因素。如烘烤过程中面包的准备时间，以及影响面包质量的温度、时间等因素。六、模型的推广与改进

（1）0-1整数规划模型不仅适合面包烘烤时间的最优化问题，也非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们关心的多种问题。

（2）市场调查在实际生活与生产中的运用也极其广泛，在市场投资，广告投入等很多问题上都有极为广泛的应用。

七、参考文献韩中庚《数学建模方法及其应用》第2版高等教育出版社2009赵静但琦《数学建模与数学实验》第2版高等教育出版社2003谭永基蔡志杰《数学模型》第二版复旦大学出版社2011谢金星薛毅《优化建模与LINDO/LINGO软件》第2版清华大学出版社侯文华梁冯珍《数学模型方法预算法》高等教育出版社2005/view/f1fd4e93dd88d0d233d46a18.html面包店问题浏览时间2013年5月5日/view/6677be7f31b765ce05081469###烤箱烘烤面包浏览时间2013年5月3日/p-468932684.html烤箱烘烤面包问题的数学模型浏览时间2013年5月3日程序一model:sets:m/1..18/:c,d;n/1..51/:a,b;link(m,n):x,t,s;endsetsdata:a=9,10,14,10,9,16,23,24,16,19,21,17,15,9,20,9,6,15,8,21,14,16,9,8,9,7,16,12,16,17,12,22,14,6,16,8,12,12,24,9,11,14,15,14,12,19,16,10,10,5,14;b=26,24,22,21,21,20,19,18,18,17,17,17,17,16,16,16,16,16,15,15,15,14,14,14,14,13,13,13,13,12,12,12,12,11,11,11,10,10,10,10,10,10,9,9,9,9,9,8,8,8,8;enddata@for(m(i)):@sum(n(j):a(j)*x(i,j))<=40;);@for(n(j):@sum(m(i):x(i,j))=1;);@for(m(i):@for(n(j):s(i,j)=@if(x(i,j)#eq#1,b(j),0);T(i,j)=@if(x(i,j)#eq#1,b(j),0);););@for(m(i):@for(n(i):c(i)=@max(n(j):t(i,j));d(i)=@min(n(j):s(i,j)););c(i)-d(i)<5;);@for(m(i):@for(n(j):@bin(x(i,j));););min=(@sum(m(i):c(i)));end.程序二model：sets:row/1,2/；col/1,2..18/;matrix(row,col):x;endsetsmin=@smax(w,y,);W=t1*x(1,1)+t2*x(1,2)+t3*x(1,3)+t4*x(1.4)+t5*x(1,18)+t6*x(1,6)+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,18)+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)+t16*x(2,1