面包店问题数学建模论文.doc

编号:A412013年高校数学建模竞赛参赛队伍选择的题号（从A/B/C/D中选择一项填写）： B题 参赛队员：队员1： 陈钰 ，学院 数理学院 队员2： 朱方超 ，学院 电气学院 队员3： 张梦姣 ，学院 人文学院 题 目 面包店问题一、摘 要 在竞争日益激烈的市场经济环境下，利益最大化无疑是每个市场经济主体最关注的问题。面包自明朝传入中国以来，越来越受到大众的喜爱。如今各地面包店不断增加，面包店面临着如何将其利益最大化的问题。 针对问题一，所需的不同种类的面包数量及样式已经确定，故在考虑面包店收益最大化时，可以将求利润最大值转化为求烘烤面包时间最小值，那么结合题目中有四个批次的面包，我们就可以每个批次分开计算最短时间，从而计算出总的最短时间。题目中有说明在面包烘烤过程中不同种类的面包的烤制时间不一样，但可以在同一个烤箱中烤制，那么此时每批次生产面包就有两种生产方式。方式一是在同一烤箱中只生产同种面包，运用线性规划的知识就可以算出每批次生产面包的所需的最短时间；方式二是在同一烤箱中可以烘烤不同种类的面包，那么就有每一批次中哪种面包是在哪次烘烤的问题。所以我们应用了0-1规划模型来解决这个问题，然后再根据烘烤面包的实际要求两种面包烘烤时间相差不能过大，在建模中我们定义相差时间为t，从而利用非线性规划模型通过MATLAB软件来计算出每批次烘烤面包的最短时间，进而得到总的最短时间。针对问题二，考虑到在一天中对面包的需求是不一样的，故可以将一天中生产出售给大众的面包也分成如问题一中的四个阶段，在每一阶段生产面包中首先满足宾馆所需的面包后再面向大众出售。考虑到面包在每一阶段时间的需求不同，以及面包生产后面临买卖风险，故在每一阶段生产面包时计算出每类面包的预期收益。然后运用动态规划模型计算出在同等时间条件下生产面包的一个最优的生产计划。 最后，对于模型的评价及改进我们提出了自己合理化的建议。关键词：非线性规划模 0-1模型 动态规划模型 MATLAB 二、问题的提出某个面包店有两个烤箱，每个烤箱有数个烤盘。该店可以烤制数十种样式的面包。不同种类的面包的烤制时间不一样，但可以在同一个烤箱中烤制。当天烤制的面包只能当天销售，过期销毁。（1）如果该面包店只为某些宾馆服务，宾馆每天分四批来取货，每次取货的面包样式及数量提前一天告知面包店，则面包店应该如何安排，才能使每天的收益最大？（2）如果面包店同时还面向大众零售服务，则应该如何安排生产计划才能使预、期的收益最大？ 请为面包店建立模型安排每天的生产计划，并自己给出数据检验模型的效果。说明你的数据产生的方式，评价模型的优缺点。三、问题分析面包店生产面包的时候必然追求生产效益最大化，面包销售获利的最大化包括面包的生产、销售的过程中面包的获利最大化，对两个部分影响面包销售获利最大化的情况进行不同的分析。问题一中我们已知宾馆对面包的需求数量和种类，故销售面包获得利润最大化就是对生产面包时间的最小化，我们可以通过用0-1模型对每次烘烤面包的种类进行界定，再通过建立非线性规划模型进行求解，从而得到生产面包的最优组合。问题二中对整个问题进行分解，即把每个时间段里生产的面包分为供应宾馆的面包和出售给大众的面包，首先满足供应宾馆的面包，其是通过问题一求得最优生产组合，可以得到每个阶段烘烤面包所用的时间。然后我们可以用每个时间段减去生产供应宾馆的面包的时间，就得到每个时间段里生产出售给大众的面包的时间，再结合动态规划来进行求解就可以得到最优生产组合，从而得到每天面包店获得大利润的最优生产组合。 四、建模过程、问题一1、模型假设：1、面包烘烤过程中拿出面包与放入面包时间忽略不计。 2、不同种类的面包在烘烤之前的准备工作时间忽略不计（如：烤箱预热以及面团的制作与发酵等）。 3、在烘烤过程不考虑不同种类的面包烘烤所需的温度、湿气不同。 4、在烘烤过程中无其他突发事件发生（如：断电等）。 5、假设所有数据是合理的，可行的。2、符号说明：m : 该店可以烤制的面包样式总数 m=10n : 每个烤箱烤盘数量w ：每个烤盘所能容纳的面包数量j : 烘烤面包的次数 j=1,2,3,hbf: 第一、二、三、四批宾馆所需面包数量 f=1,2,3,4Tf: 每批次的的面包烤制所需的时间 f=1,2,3,4ni: 宾馆每批面包中A1,A2,Am各样式所需的数量 i=1,2,3,mAi: 各种样式的面包 i=1,2,3,m ti: 不同种类的面包烘烤所需的时间 i=1,2,3,mBi: 各种样式的面包各户所需的数量 i=1,2,3,m3、模型建立：针对题中烘烤不同种类的面包可以有两种烘烤方式：3.1（模型一）在同一烤箱内只烘烤同一种面包，此时有面包利润最大化即烘烤时间最小化，可有如下模型: 先讨论第一批次的面包烘烤，可有如下定义Mi， 此时可有模型 同理可有，烘烤第二、三、四批次的面包时间，则为宾馆烘烤面包总时间为3.2 （模型二） 在同一烤箱中可以烘烤不同种类面包，则烘烤时间不同的面包可以同时烘烤，考虑到在烘烤面包的过程中一旦烤箱开始工作就不能打断烤箱工作这一事实客观事实，未免烘烤时间过长考坏面包须满足两种面包烘烤时间不能相差过大，此处相差时间设为t。引入决策0-1变量Mij，则在第一批次烘烤面包中，由题目可有目标函数： （tj表示每次烘烤面包的所需的时间）目标函数满足如下约束条件：（1）每次烘烤的数量不大于烤箱中可以烘烤面包的数量nw（2）两种面包烘烤时间相差不大于t综上各种条件有如下线性模型： 满足的条件为： 那么由以上的模型可以分别得出第二、三、四批次面包烘烤过程中所需的最短时间，故最短总时间为模型比较，比较两种模型的优越性可比较两种模型求解出的时间、的大小即可，时间越小即说明烘烤面包花费成本小，也就是利润越高，此时模型越优越。鉴于此，在通过对面包店调查中我们知道某一面包店的烤箱数量为两个，且每个烤箱的烤盘有两个，每个烤盘可以烘烤十个面包，某社区在其店订购面包数量的数据如下：面包种类ABCDE烘烤时间（分钟）678910第一批次3040503050第二批次6050605080第三批次7060409040第四批次4050403040针对模型一，经matlab分析可有如下烘烤顺序：第一批次的烘烤顺序第二批次的烘烤顺序第三批次的烘烤顺序第四批次的烘烤顺序A (6分钟)A (6分钟)A (6分钟)两次A (6分钟)B（7分钟）B（7分钟）B（7分钟）B（7分钟）C（8分钟）C（8分钟）C（8分钟）C（8分钟）D（9分钟）D（9分钟）D（9分钟）两次D（9分钟）E（10分钟）E（10分钟）两次E（10分钟）E（10分钟）AE（10分钟）AB（7分钟） CD（10分钟）BD（9分钟）B（9分钟）烘烤次数6886烘烤时间5O分钟67分钟64分钟49分钟故可得到第一批次生产面包花费时间为=50，第二批次生产面包花费时间=67，第三批次生产面包花费时间=64，第四批次生产面包花费时间=49 ， 总时间为=230分钟针对模型二，可有如下烘烤顺序及组合：第一批次的烘烤组合及顺序第二批次的烘烤组合及顺序第三批次的烘烤组合及顺序第四批次的烘烤组合及顺序AC(8分钟)A(6分钟)A(6分钟)A(6分钟)B(7分钟）A(6分钟)B(7分钟)B(7分钟)C98分钟）B(7分钟)C(8分钟)C(8分钟)DE(10分钟）C(8分钟)D(9分钟)CD(9分钟)E(10分钟）D(9分钟)D(9分钟)E(10分钟)E(10分钟)E(10分钟)E(10分钟)A(6分钟)BCD(9分钟)BD(9分钟)43分钟65分钟64分钟40分钟 故可得到第一批次生产面包花费时间为=43，第二批次生产面包花费时间=65，第三批次生产面包花费时间=64，第四批次生产面包花费时间=40,总时间为=212分钟 显然通过两种模型的比较可以很清楚的看出模型二比模型一优越。、问题二1、模型假设：1、每种面包在每次烘烤过程中都会成功，没有考坏的面包 2、每天销售的各种面包数量大致符合同一分布函数 3、面包烘烤过程中拿出面包与放入面包时间忽略不计。 4、在烘烤过程中无其他突发事件发生。 5、假设所有数据是合理的，可行的。2、符号说明：m : 该店可以烤制的面包样式总数 m=10n : 每个烤箱烤盘数量w ：每个烤盘所能容纳的面包数量Ai: 各种样式的面包 i=1,2,3,mti: 不同种类的面包烘烤所需的时间 i=1,2,3,mBi: 各种样式的面包各户所需的数量 i=1,2,3,mCi: 各种样式的面包销售后的不同利润 i=1,2,3,m: 一天中每个阶段生产面包的时间 i=1,2,3,4:一天中每个阶段生产面向大众销售的面包的最大收益 i=1,2,3,43、模型建立： 在解决问题一的过程中可以知道，面向大众出售面包时要面临各个时间段各种面包的需求不同的这个客观存在的环境，鉴于此根据调查一天中每种面包的需求量随时间变化的函数大致都满足正态分布函数。在此我们假设该函数的均值为，方差为，其中i=1,2,3,m。 根据正态分布函数我们可以求得每个时间段的的均值为： 这样我们就可以知道每种面包在一天中每个时间段的需求量，分别为、。其中 i=1,2,3,m 我们假设面包作坊每天的工作时间分为四个时间段，时间长度分别为，结合第一题的数据可以知道每个时间段中用来生产面向大众销售的面包的时间分别为 、在上述过程后我们可以得到如下表的数据：面包种类第一段时间面包需求量第二段时间面包需求量第三段时间面包需求量第一段时间面包需求量1234M为了让面包店的收益最大化，在面向大众出售面包的过程中，在第一个时间段面包店在选择生产哪几种面包时可以有如下模型： 目标函数为： 其中要满足 满足如下关系：则可以分别求出面向大众出售面包是每个阶段最大收益为、，从而可以得出总的最大收益。由动态规划可有 a、逆推解法： 可以把问题的变量个数划分阶段，把它看作为一个m阶段决策问题，设状态变量为s1、s2、s3、s4sm,并记s1=c；取问题中的变量x1,x2,x3,x4xm为决策变量；各阶段指标函数按函数乘积方式结合。令最优值函数表示为第k阶段的初始状态为sk，从k阶段到第m阶段所得到的最大值。 从第m阶段开始，则有 其中是有状态sm所确定的第m阶段的允许决策模型集合。借此极致问题，就得到最优解和最优值。在第m-1阶段，有 其中，解此问题可以得到最优解和最优值。 在第k阶段，有 其中，解此问题可以得到最优解和最优值 如此类推，直到第一阶段，有 其中，解此问题可以得到最优解和最优值 由于初始状态s1已知，故x1=x1（s1）和是确定的，从而也就可以确定，于是x2=x2（s2）和也就可以确定。这样，按照上述递推过程相反的顺序推算下去，就可逐步确定出最优的烘烤面包的种类以及每种面包的数量。 b、顺推解法：设已知终止状态，并假定最优值函数表示第k阶段末的结束状态为s，从1阶段到k阶段所得到的最大利益。已知终止状态用顺推解法与已知初始状态用逆推解法在本质上没有区别，它相当于把实际的起点视为终点，实际的终点视为起点，而按逆推解法进行的。换言之，只要把图8-6的箭头倒转过来即可，把输出看作输入，把输入看作输出，这样便得到顺推解法。但应注意，这里是在上述状态变量和决策变量的记法不变的情况下考虑的。因而这时的状态变换是上面状态变换的逆变换，记为；从运算而言，既是由和而去确定的。从第一阶段开始，有 ，其中解得最优解和最优值。若只有一个决策，则就写成。在第二阶段，有 其中，解得最优解和最优值。如此类推，直到第n阶段，有 其中。解到最优解和最优值。由于终止状态是已知的，故和是确定的。再按计算过程的相反顺序推算上去，就可以逐步确定出每阶段的决策及效益。应指出的是，若将状态变量的记法改为，决策变量记法不变，则按顺序解法，此时的最优值函数为。因而，这个符号与逆推解法的符号一样，但含义是不同的，这里的是表示k阶段末的结束状态。 结合问题一的数据我们有：120-43=77120-65=55120-64=56120-40=80根据每种面包的烘烤时间以及每种面包每个利润可以有分别对四个阶段分别求解，如下第一阶段中（每种面包的预计销售量见附录二）通过动态规划进行迭代可以求得每种面包应生产计划：生产x3的数量为140个，生产x5的数量为100个。可以求得以下结果:X1X2X3X4X5第一阶段001400100第二阶段500801000第三阶段4090040120第四阶段60601008050（x1：表示奶油面包，x2：表示法式软面包，x3：巧克力面包，x4：蛋糕卷，x5：表示全麦土司） 计算结果中第一阶段主要销售巧克力蛋糕和全麦蛋糕，第二阶段主要销售奶油面包、巧克力蛋糕以及蛋糕卷，第三阶段主要销售奶油蛋糕、法式软面包以及全麦土司，在第四阶段五种面包均有销售。此结果较为符合一天中从早到晚人们对面包的需求的种类和数量。五、模型的评价与推广 面包店销售面包时为取得最大利润，在卖出面包数量一定时通过对面包烘烤的过程中面包烘烤顺序的合理安排可以减少烘烤时间增加收益；在时间一定时则可以通过对面包烘烤数量、种类与获利的合理考虑得到最优组合。 a、模型的优点： 问题一中我们在已知所要供应的面包数量的条件下，我们运用非线性规划模型对两个面包烘烤箱进行合理安排和使用可以使烘烤时间最短，从而知道面包店生产面包获得最大利润的最优组合。 问题二中通过从销售面包中把对宾馆的面包的供应和对大众销售的面包的供应分离开来，运用动态规划知识求得在一定时间条件下，生产各种面包所能获得的最大利润的最优组合，再结合问题一中生产面包的最优组合从而得到问题二中生产面包的最优组合。 b、模型的缺点： 在整个建模过程中我们忽略了在烘烤面包时可能存在考坏的情况，从而整个烘烤过程是理想化的情况下进行的。 在向大众出售面包时用均值来体现生产面包的风险过于数据化，理想化，与实际销售情况可能出现偏差。 C、模型的推广：本模型有效地解