运筹学论文

课程设计任务书2012—2013学年第二学期专业班级：10普本信息与计算科学学号：xxxxxxxx姓名：xxxxxxxx课程设计名称：运筹学设计题目：线性规划的问题及其应用完成期限：自2013年06月10日至2013年06月16日共7天设计依据、要求及主要内容：一、设计目的熟练掌握求解线性规划的方法以及关于这些方法的分析和综合应用，能够较熟练地应用LINGO软件编写求解线性规划的程序。二、设计内容（1）认真挑选有代表性的线性规划问题．（2）根据线性规划的解的概念和基本理论，运用单纯形法来求解线性规划问题。（3）列出目标函数，编程序用LINGO软件来求解。三、设计要求1．掌握线性规划的求解方法和一些基本理论。2．先分析题中的数据，列出目标函数。3．然后使用所用的方法编写LINGO程序求解。计划答辩时间：2013年06月16日工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字．指导教师（签字）：教研室主任（签字）：批准日期：2013年6月9日课程设计说明书（论文）1线性规划的问题及其应用摘要本文考虑的是快餐店如何获得最高利润问题。影响快餐店利润的因素主要有顾客对等待时间的态度；当宣布“服务慢了将免费供餐”以后，承诺的时间与顾客的增多之间的关系等。我们在模型中主要从以上二个因素来考虑对快餐店能获利润进行预测。根据此模型得到了顾客平均到达率，快餐店平均服务率来分析此问题。我们运用运筹学中排队论模型对快餐店排队系统进行优化,在常规优化方案的基础上提出进一步的优化方案。通过优化不仅提高了服务效率,而且增强了顾客满意度,增加了经济效益。关键词：快餐店，排队论，数学模型，运筹学，优化课程设计说明书（论文）2目录1前言.....................................................................................................................................32解题思想和方法.................................................................................................................32.1线性规划解的概念..................................................................................................32.2线性规划解的基本理论............................................................................................42.3线性规划的求解方法................................................................................................43问题的提出.........................................................................................................................54问题的分析.........................................................................................................................65模型假设与符号说明...........................................................................................................66模型的建立与求解.............................................................................................................77模型的评价.........................................................................................................................11总结...................................................................................................................................11参考文献.................................................................................................................................12课程设计说明书（论文）31前言运筹学是运用代数学、统计学等现代应用数学的方法和技术，通过建立数学模型分析研究各种（广义）资源的运用、筹划及相关决策等问题的一门新兴学科。其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、筹划及相关决策等问题做出综合最优的合理安排，以使有限的资源发挥更大的效益或作用。一般线性规划问题的求解方法—单纯形法，使得线性规划在实际中的应用日益广泛。特别是随着计算机技术的飞速发展，使得大规模线性规划的求解成为可能，从而使线性规划的应用领域更加广泛。例如在工业、农业、商业、交通、运输、军事、政治、经济、社会和管理等领域的最优设计和决策问题很多都可归结为线性规划问题。2解题思想和方法2.1线性规划解的概念（1）解称满足约束条件的解12(,,,)Tnxxxx为线性规划问题的可行解；可行解的全体构成的集合称为可行域，记为D；使目标函数达到最大的可行解称为最优解。（2）基设系数矩阵()ijmnAa的秩为m，称A的某个mn非奇异子矩阵B（|B|0）为线性规划问题的一个基。不妨设m12()ijmmBa（p,p,,p），则称向量12(,,,)Tjjjmjaaap(1,2,,)jm为基向量，矩阵A的其他列向量称为非基向量；与基向量对应的决策变量(1,2,,)jxjm称为基向量，其他的变量称为非基变量。（3）基解设问题的基为m12()ijmmBa（p,p,,p），将约束方程组变为11mnjjjjjjmpxbpx在上方程的解中令0(1,2,,)jxjmmn，则称解向量12(,,,,0,,0)Tmxxxx为问题的基解。（4）基可行解满足非负约束条件的基解称为基可行解。（5）可行基对应于基可行解的基称为可行基。课程设计说明书（论文）42.2线性规划解的基本理论在介绍线性规划的几个重要结论之前，先引入凸集和顶点的概念。假设K为n维欧式空间nE中的点集，如果对于任意两点xxK（1）（2），，其连线上一切点(1)(1)(01)xxxK（2），则称K为凸集。设,,xxx（1）（2）（k），是n维欧式空间nE中的k个点，如果存在i：011,2,,iik，且11kii，使得(1)12kxxxx（2）（k），则称x为,,xxx（1）（2）（k），的凸组合。对于凸集k中的点x，如果x不能用相异的两点xxK（1）（2），的凸组合表示为(1)(1)(01)xxxK（2），则称x为凸集K的一个顶点（或极点）。由上述的概念，下面不加证明地给出线性规划的几个重要定理，这是解决线性规划问题的理论基础。定理1如果线性规划问题（2.5），（2.6）存在可行域D，则其可行域j1x|bx0mjjjDpx，一定是凸集。定理2线性规划问题（2.5），（2.6）的任一个基可行解x必对应于可行域D的一个顶点。定理3（1）如果线性规划问题（2.5），（2.6）的可行域有界，则问题的最优解一定在可行域的顶点上达到。(2)如果线性规划问题（2.5），（2.6）的可行域无界，则问题可能无最优解；若有最优解也一定在可行域的某个顶点上达到。2.3线性规划的求解方法根据线性规划的解的概念和基本理论，求解线性规划问题可采用下面的方法：求一个基可行解（即对应可行域的一个顶点）；检查基可行解是否为最优解；如果不是，则设法再求另一个没有检查过的基可行解（可行域的另一个顶点），如此进行下去，直到得到某一个基可行解为最优解为止。解决此问题的方法称为单纯形法。课程设计说明书（论文）5（1）初始基可行解的确定如果线性规划问题为标准型（即约束方程全为等式），则从系数矩阵()ijmnAa中总可以得到一个m阶单位阵mE。如果问题的约束条件的不等号均为“”则引入m个松弛变量，可化为标准型，并将变量重新排序编号，即可得到一个m阶单位阵mE；如果问题的约束条件的不等号为“”和“=”，则首先引入松弛变量化为标准型，再通过人工变量法（人工加上一个系数为1的变量）总能得到一个m阶单位阵mE。综上所述，取如上m阶单位阵mE位初始可行基，即mBE，将相应的约束方程组变,11(1,2,,)iiimminnxbaxaxim令0(1,,)jxjmn，则可得到一个初始基可行解(0)(0)(0)(0)1212(,,,,0,,0)(,,,,0,,0)TTmmxxxxbbb(2)寻找另一个基可行解假设要检验基可行解(0)(0)(0)(0)12(,,,,0,,0)Tmxxxx对应的可行基111(,,,,,,)lmtlmBppppp，从而可以求出一个新的基可行解(0)(0)(0)(0)12(,,,,0,,0)Tmxxxx。次方法称为基变换法。事实上(0),,(1)1,2,,,,1,1.{iimtxilimiillmtnmx,其中(0)(0),,11,,|0,minmiiimtmtimtiimilmtimtxxPP如果(0)(0)(0)(0)12(,,,,0,,0)Tmxxxx仍不是最优解，则可以重复利用这种方法，直到得到最优解为止。3问题的提出如何吸引更多的顾客以获取更高的利润是每一位快餐店老板最关心的问题.除了增加花色、提高品味、保证营养、降低成本之外，快餐店应在其基本特点“快”字上下功夫.有人向老板建议，公开向顾客宣布：如果让哪位顾客等待超过一定时间(譬如3分钟)，课程设计说明书（论文）6那么他可以免费享用所订的饭菜，提建议者认为这必将招揽更多的顾客，由此带来的利润一定大于免费奉送造成的损失.但是老板希望对于利弊有一个定量的分析.告诉他在什么条件下作这种承诺才不会亏本，更进一步，他希望知道应该具体地作几分钟的承诺，利润能增加多少。4问题的分析本问题是关于快餐店利润的问题。随着经济水平的提高,外出到快餐店用餐的人越来越多,由于服务生产与消费的同步性、服务的不可储藏性,以及顾客到达的随机性,让顾客进行排队等待是不可避免的。排队等待通常出现在服务的最开始阶段,它会对顾客如何看待接下来的服务产生“晕轮”的效果我们首先从顾客进入快餐店他在订餐处订餐的起始时刻出发，我们规定顾客定餐后就拿到一张收据，上面标明时间为起始时刻，接着服务在厨房进行，厨房只有一位厨师，按订单到达的顺序配餐，配好一份立即送往取餐处.最后，服务员将饭菜交给顾客，并核对收据，若发现顾客等