课程设计任务书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 前言 (3)2 解题思想和方法 (3)2.1 线性规划解的概念 (3)2.2 线性规划解的基本理论 (4)2.3 线性规划的求解方法 (4)3 问题的提出 (5)4 问题的分析 (6)5 模型假设与符号说明 (6)6 模型的建立与求解 (7)7 模型的评价 (11)总结 (11)参考文献 (12)1 前言运筹学是运用代数学、统计学等现代应用数学的方法和技术，通过建立数学模型分析研究各种（广义）资源的运用、筹划及相关决策等问题的一门新兴学科。
其目的是根据实际问题的具体要求，通过定量的分析与运算，对资源运用、筹划及相关决策等问题做出综合最优的合理安排，以使有限的资源发挥更大的效益或作用。
一般线性规划问题的求解方法—单纯形法，使得线性规划在实际中的应用日益广泛。
特别是随着计算机技术的飞速发展，使得大规模线性规划的求解成为可能，从而使线性规划的应用领域更加广泛。
例如在工业、农业、商业、交通、运输、军事、政治、经济、社会和管理等领域的最优设计和决策问题很多都可归结为线性规划问题。
2 解题思想和方法2.1 线性规划解的概念（1）解 称满足约束条件的解12(,,,)T n x x x x =⋅⋅⋅为线性规划问题的可行解；可行解的全体构成的集合称为可行域，记为D ；使目标函数达到最大的可行解称为最优解。
（2）基 设系数矩阵()ij m n A a ⨯=的秩为m ，称A 的某个m n ⨯非奇异子矩阵B≠（|B|0）为线性规划问题的一个基。
不妨设m 12()ij m m B a ⨯==⋅⋅⋅（p ,p ,,p ），则称向量12(,,,)T j j j mj a a a =⋅⋅⋅p (1,2,,)j m =⋅⋅⋅为基向量，矩阵A 的其他列向量称为非基向量；与基向量对应的决策变量(1,2,,)j x j m =⋅⋅⋅称为基向量，其他的变量称为非基变量。
（3）基解 设问题的基为m 12()ij m m B a ⨯==⋅⋅⋅（p ,p ,,p ），将约束方程组变为11m n jj j j j j m p x b p x ==+=-∑∑在上方程的解中令0(1,2,,)j x j m m n ==++⋅⋅⋅，则称解向量12(,,,,0,,0)T m x x x x =⋅⋅⋅⋅⋅⋅为问题的基解。
（4） 基可行解 满足非负约束条件的基解称为基可行解。
（5） 可行基 对应于基可行解的基称为可行基。
2.2 线性规划解的基本理论在介绍线性规划的几个重要结论之前，先引入凸集和顶点的概念。
假设K 为n 维欧式空间n E 中的点集，如果对于任意两点x x K ∈（1）（2），，其连线上一切点(1)(1)(01)x x xK λλλ=+-∈≤≤（2），则称K 为凸集。
设,,x x x ⋅⋅⋅（1）（2）（k ），是n 维欧式空间n E 中的k 个点，如果存在i λ：()011,2,,i i k λ≤≤=⋅⋅⋅，且11k i i λ==∑，使得(1)12k x x x x λλλ=++⋅⋅⋅+（2）（k ），则称x 为,,x x x ⋅⋅⋅（1）（2）（k ），的凸组合。
对于凸集k 中的点x ，如果x 不能用相异的两点xx K ∈（1）（2），的凸组合表示为(1)(1)(01)x x x K λλλ=+-∈≤≤（2），则称x 为凸集K 的一个顶点（或极点）。
由上述的概念，下面不加证明地给出线性规划的几个重要定理，这是解决线性规划问题的理论基础。
定理 1 如果线性规划问题（2.5），（2.6）存在可行域D ，则其可行域j 1x |b x 0m j j j D p x =⎧⎫==≥⎨⎬⎩⎭∑，一定是凸集。
定理 2 线性规划问题（2.5），（2.6）的任一个基可行解x 必对应于可行域D 的一个顶点。
定理 3 （1）如果线性规划问题（2.5），（2.6）的可行域有界，则问题的最优解一定在可行域的顶点上达到。
(2) 如果线性规划问题（2.5），（2.6）的可行域无界，则问题可能无最优解；若有最优解也一定在可行域的某个顶点上达到。
2.3 线性规划的求解方法根据线性规划的解的概念和基本理论，求解线性规划问题可采用下面的方法：求一个基可行解（即对应可行域的一个顶点）；检查基可行解是否为最优解；如果不是，则设法再求另一个没有检查过的基可行解（可行域的另一个顶点），如此进行下去，直到得到某一个基可行解为最优解为止。
解决此问题的方法称为单纯形法。
（1） 初始基可行解的确定如果线性规划问题为标准型（即约束方程全为等式），则从系数矩阵()ij m n A a ⨯= 中总可以得到一个m 阶单位阵m E 。
如果问题的约束条件的不等号均为“≤”则引入m 个松弛变量，可化为标准型，并将变量重新排序编号，即可得到一个m 阶单位阵m E ；如果问题的约束条件的不等号为“≥”和“=”，则首先引入松弛变量化为标准型，再通过人工变量法（人工加上一个系数为1的变量）总能得到一个m 阶单位阵m E 。
综上所述，取如上m 阶单位阵m E 位初始可行基，即m B E =，将相应的约束方程组变,11(1,2,,)i i i m m in n x b a x a x i m ++=--⋅⋅⋅-=⋅⋅⋅令0(1,,)j x j m n ==+⋅⋅⋅，则可得到一个初始基可行解(0)(0)(0)(0)1212(,,,,0,,0)(,,,,0,,0)T T m m x x x x b b b =⋅⋅⋅⋅⋅⋅=⋅⋅⋅⋅⋅⋅ (2) 寻找另一个基可行解假设要检验基可行解(0)(0)(0)(0)12(,,,,0,,0)T m x x x x =⋅⋅⋅⋅⋅⋅对应的可行基111(,,,,,,)l m t l m B p p p p p -++=⋅⋅⋅⋅⋅⋅，从而可以求出一个新的基可行解(0)(0)(0)(0)12(,,,,0,,0)T m x x x x =⋅⋅⋅⋅⋅⋅。
次方法称为基变换法。
事实上()(0),,(1)1,2,,,,1,1.{i i m t x i l i m i i l l m t n m x θβθ+-≠=⋅⋅⋅=≤≤≤≤-=, 其中(0)(0),,11,,|0,min m i i i m t m t i m t i i m i l m t i m t x x P P θββββ+++≤≤=++⎧⎫⎪⎪==>=⎨⎬⎪⎪⎩⎭∑ 如果(0)(0)(0)(0)12(,,,,0,,0)T m x x x x =⋅⋅⋅⋅⋅⋅仍不是最优解，则可以重复利用这种方法，直到得到最优解为止。
3 问题的提出如何吸引更多的顾客以获取更高的利润是每一位快餐店老板最关心的问题.除了增加花色、提高品味、保证营养、降低成本之外，快餐店应在其基本特点“快”字上下功夫.有人向老板建议，公开向顾客宣布：如果让哪位顾客等待超过一定时间(譬如3分钟)，那么他可以免费享用所订的饭菜，提建议者认为这必将招揽更多的顾客，由此带来的利润一定大于免费奉送造成的损失.但是老板希望对于利弊有一个定量的分析.告诉他在什么条件下作这种承诺才不会亏本，更进一步，他希望知道应该具体地作几分钟的承诺，利润能增加多少。
4 问题的分析本问题是关于快餐店利润的问题。
随着经济水平的提高,外出到快餐店用餐的人越来越多,由于服务生产与消费的同步性、服务的不可储藏性,以及顾客到达的随机性,让顾客进行排队等待是不可避免的。
排队等待通常出现在服务的最开始阶段,它会对顾客如何看待接下来的服务产生“晕轮”的效果我们首先从顾客进入快餐店他在订餐处订餐的起始时刻出发，我们规定顾客定餐后就拿到一张收据，上面标明时间为起始时刻，接着服务在厨房进行，厨房只有一位厨师，按订单到达的顺序配餐，配好一份立即送往取餐处.最后，服务员将饭菜交给顾客，并核对收据，若发现顾客等待时间超过店方的承诺，则将所收款项如数退还。
这个问题建模的关键有二：一是对顾客到达、服务时间、排队规则等作什么样的假设；二是当宣布“服务慢了将免费供餐”以后，承诺的时间与顾客的增多之间的关系应该用什么规律描述.对于前者，M/M/1模型是一个合理的、简化的选择；对于后者，我们将在直观分析的基础上用最简单的定量关系表示出来。
5 模型假设与符号说明1、由于顾客较多，而服务员又相对较少，故我们可认为在各段时间段中顾客源是无限的，且顾客单独到来且相互独立。
2、每个服务员的工作效率是随机的，很难对其进行精确的分析。
所以由一般统计规律，认为其满足指数分布，且服务员之间无差异。
3、顾客在快餐店的服务服从M/M/1模型。
4、店方承诺等待时间超过u的顾客免费享用订餐，u越小则顾客越多，c越小，在一定范围内设c与u成正比，同时又存在u的最大值u0，当u≥u0时快餐店的承诺对顾客无吸引力，相当于不作承诺。
5、顾客在快餐店的服务服从M/M /1模型；顾客平均到达率为λ=1/c,c 为平均到达间隔，在未宣布承诺时c =c 0；6、快餐店平均服务率μ=1/d,d 为平均服务时间；d ＜c 。
6 模型的建立与求解首先，根据本讲对M /M /1模型的分析，顾客等待时间(记作随机变量Y )服从参数μ-λ的指数分布，即t c d t e e t y P )11()()(----==>λμ （6.1）对于等待时间为Y 的顾客设店方获得的利润为Q (Y)，则在宣布承诺时间为u 的情况下有⎩⎨⎧--=,,)(q q p Y Q u Y u Y >≤ （6.2） 利润Q 的期望值为)()()(u Y qP u Y P q p EQ >-≤-= （6.3）用（6.1）式代入得u c d pe q p EQ ⎪⎭⎫ ⎝⎛----=11 （6.4）因为顾客到达的平均间隔为c ，所以单位时间利润的期望值为][11)(11u c d pe q p c EQ c u J ⎪⎭⎫⎝⎛----== （6.5） 建模的目的是确定承诺时间u 使利润J(u)最大.下面我们根据对于c 和u 关系的假设确定函数c(u).因为可以假定c (0)=0(理解为u →０时顾客将无穷多)，当u ≥u 0时c(u)=c 0(因为这时相当于不作承诺)，所以若假设在0≤u ≤u 0时c 与u 成正比，函数c(u)的图形就如图6－5（见下）所示，并且由于d ＜c 的基本要求,必须u>00c du ，于是c(u)可表为⎪⎩⎪⎨⎧≥<<=0000000,,)(u u c u u c du u u c u c （6.6） 将(6.5)式代入(6.6)式得⎪⎪⎩⎪⎪⎨⎧≥---<<--=---0)11(000000]1[),1()()(0u u e q p p c q p u u c du e u c q p u u J u c d d u α (6.7)图5-5其中00c u e qp p --=α (6.8) J (u )中除u 外均为已知常数，问题化为求u 使J (u )最大.对于(6.7)式的J (u )应按u 的不同范围分别求解.当000u u c du <<时，用微分法求出μ的最优值u *应满足)1(**du e d u +=α (6.9) 且算出J 的最大值为)()()(*00*d u c q p u u J +-= （6.10） 当u ≥u 0，显然u →∞时J (μ)最大，且)(c q p J -=∞ (6.11)比较)(*u J 和)(∞J 可知，当且仅当0*u d u <+时)(*u J >)(∞J ，所以J (μ)最大值问题的解应为⎩⎨⎧≥+∞<+=0*0**u d u u d u u u (6.12) 其中*u 由(6.9)式确定.这就是说，对于给定的p 、q 、0c 、0u 和d ，以及按(6.8)、(6.9)式算出的*u ，仅当0*u d u <+时,才可承诺服务慢了免费供餐，并且承诺时间为*u 时利润最大.进一步分析可以作承诺的条件du d u 0*1<+ (6.13) 根据(6.9)式，如果用方程)1(f e f +=α （6.14） 条件(6.13)可以表为)(10αf u d +< (6.15) 因为(6.8)式中的α是q p /、0u 、0c 的函数，即),,/(1//0000c u q p e q p q p c u αα=-= (6.14) 若记 ),,/()(1000c u q pd f u d c c =+=α (6.16) 则当q p /、0u 、0c 给定时快餐店可以作承诺的条件(6.17)，应该表为平均服务时间d 满足),,/(00c u q p d d c < (6.17)在这个条件下最优承诺时间*u 由(6.16)式确定.与不作承诺时的利润J (∞)相比，此时的利润)(*u J 为)()()(*0*∞>∞+=J J du u u J (6.18) 目标函数：min z=16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11）x1+x9+x10+x11>=8x1+x2+x10+x11>=8x1+x2+x3+x11>=7x1+x2+x3+x4>=1x2+x3+x4+x5>=2x3+x4+x5+x6>=1x4+x5+x6+x7>=5x5+x6+x7+x8>=10x6+x7+x8+x9>=10x7+x8+x9+x10>=6x8+x9+x10+x11>=6x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11>=0程序如下：Model:Sets:Row/1…11/:b;Arrange/1…11/:x,c;Link(row,arrange):a;EndsetsData:b=8,8,7,1,2,1,5,10,6,6;c=16,16,16,16,16,16,16,16,16,16,16;a=1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1 ,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1, 1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0 ,0,0,0,0,0,0,0,1,1,1,1;enddata[OBJ]min=@sum(arrange(j):c(j)*x(j));@for(row(i);@sum(arrange(j):a(i,j)x (i,j))>=b(i););@for(arrange(j):x(j)>=0;);End最优解为x=(2,1,0,0,1,0,9,0,1,0,5),最优值为z=304，即临时工班次为11:00~12:00开始上班2人，12:00~13:00开始上班1人，15:00~16:00开始上班1人，17:00~18:00开始上班9人，19：00~20：00开始上班1人，21:00~22:00开始上班5人，雇佣临时工19人，临时工的总工资为304元。