F( 4, 3) 0.000000 10.00000 F( 4, T) 9.000000 0.000000
最大流的费用为205，而原最大流的费用为v（f）=7*2+7*8+5*2+2*5+9*3+9*7+5*6=210，故原方案不是最优的。 三、实验任务
问题2-1：求下图所示的最大流问题，弧上数字为容量和初始可行流量：
v1 （7，4） v3
（8，8） （3，1） （8，6）
vs （3，3） （3，0） vt
（9，4） （2，2） （9，6）
v2 （5，5） v4
问题2-2： 如下图，从三口油井1、2、3经管道将油输至脱水处理厂7和8，中间经4、5、6三个泵站。已知图中弧旁数字为各管道通过的最大能力（吨/小时），求从油井每小时能输送到处理厂的最大流量。
1 7
20 4 10 2 10 50 20 10 6 50 30 20 20 3 15 5 30 8
问题2-3： 下表给出某运输问题的产销平衡表与单位运价表。将此问题转化为最小费用
最大流问题，画出网络图并求数值解。
产地 销地 1 2 3 产 量
A 20 24 5 8 B 30 22 20 7 销 量 4 5 6
问题2-4 求下图所示网络的最大流，每弧旁的数字是（容量，流量）.
(4,3)(3,2)v1(3,2(1,1)v534,(5vs(10,4)))(2,2)(7(,0)(3,2)v3(4,2),3)(8,vt3)v2V4四、实验报告要求
实验报告包含下列几个部分：
(1) 目的；(2) 软件；(3) 问题；(4) 数学模型；
(5) 计算程序；(6) 计算结果;(7) 分析、检验和结论;(8) 心得体会;
15
实验三、利用LINGO求解排队与存贮模型 一、实验目的
通过此实验， 了解Lingo软件求解排队论与存贮论中的常用命令，能利用排队与存贮理论的基本知识，建立实际问题的数学模型，并利用LINGO求解。 二、实验原理及方法
（一）、熟悉与排队论有关的Lingo软件中的常用命令[8]： （1）P=@peb(load,s)
其中p表示系统到达负荷时，服务系统中有s个服务台且允许排队时系统繁忙的概率，即顾客等待的概率，Load=λ/μ。 (2)p=@pel(Load,S)
其中p表示系统到达负荷时，服务系统中有s个服务台且不允许排队时系统损失的概率，即顾客得不到服务离开的概率，Load=λ/μ。 (3)@pfs(load,s,k)
该函数的返回值是当系统到达负荷为load时，顾客数为k，平行服务台数量为s时，有限源的Poisson服务系统等待或返修顾客数的期望值。
(二)等待制排队模型(见[1]第324页4节 标准的M/M/C模型)或文献[8]
下面介绍用Lingo软件求解最常见的等待制排队模型M/M/S/?，即顾客到达系统的相继到达时间间隔独立且服从参数为?的负指数分布(即输入过程为Poisson过程)，服务台的服务时间也相互独立，且服从参数为?的负指数分布（分布函数为F(x)=1-exp(-?x),x>0;F(x)=0,x<=0），系统空间无限，允许永远排队。
注：?为单位时间来到系统的人数，1/?为平均每个顾客的服务时间,即?为单位时间服务的人数.
等待制排队系统的基本参数： (1)顾客的平均等待概率为： Pwait=@peb(load,s)
其中s 是服务台的个数，load是系统到达负荷，即load=?=λ/μ（下面编程中，用load=?，lamba表示λ，mu表示μ）则有 (2)顾客的平均等待时间为：
Wq?Pwait?（S?load）（公式推导见文[8],[1]）
（3）顾客的平均逗留时间Ws，队长Ls（在系统中的平均顾客数）和等待队长Lq（系统中排队等待的顾客的平均数），由Little公式：
16
Ws?Wq?Ls??WsLq??Wq1?
例题3-1 某中心 在周末只安排一名员工为顾客服务。新来到的顾客到达后，若已有顾客正在接受服务，则需要排队。假设来维修的顾客到达过程为poisson流，平均每小时4人，维修时间服从负指数分布，平均需要6min。试求该系统的主要数量指标。 解：
（1）顾客的平均等待概率为： Pwait=@peb(load,s)
其中s 是服务台的个数，load是系统到达负荷，load=λ/μ， (2)顾客的平均等待时间为：
Wq?Pwait?（S?load）（3）顾客的平均逗留时间Ws，队长Ls（在系统中的平均顾客数）和
等待队长Lq（系统中排队等待的顾客的平均数），由Little公式：
Ws?Wq?Ls??WsLq??Wq1?
本例中， S=1; ?=4; 1/?=6/60; load=?/? 利用上述公式，编写Lingo程序为：
S=1; lamda=4; mu=10; load=lamda/mu; Pwait=@peb(load,S);
W_q=Pwait/mu/(S-load); L_q=lamda*W_q; W_s=W_q+1/mu; L_s=lamda*W_s;
计算结果为：
Variable Value
S 1.000000 LAMDA 4.000000 MU 10.00000 LOAD 0.4000000 PWAIT 0.4000000 W_Q 0.6666667E-01 L_Q 0.2666667 W_S 0.1666667 L_S 0.6666667
由此得到：
（1）系统的平均队长为Ls=0.666666（人） （2） 系统的等待队长Lq=0.266667（人）
17
（3） 顾客平均逗留时间为Ws=0.166667（h）=10（min） （4） 顾客平均等待时间Wq=0.066667（h）=4（min） （5） 系统繁忙概率Pwait=0.4。
例题3-2[3] 一个大型露天矿山，正考虑修建矿石些卸位的个数。估计运矿石的车将按Poisson流到达，平均每小时15辆。卸矿石时间服从负指数分布，平均3min卸一辆。又知每辆运送矿石的卡车售价是8万元，修建一个卸位的投资是14万元。问应建多少矿山卸位最为适宜？
解：用等待制排队系统M/M/S/?进行分析，其费用包括两个方面：一个是建造卸位的费用，另一个是卡车处于排队状态不能工作的费用，因此目标函数为
f?14S?8Ls(此处用Lq也可，见文[1]P336)
在上述条件下求目标函数的最小值。 本例中，?=15，1/?=3/60,load=?/?=3/4 相应的Lingo程序为：
lamda=15; mu=20; load=lamda/mu; Pwait=@peb(load,S); W_q=Pwait/mu/(S-load); W_s=W_q+1/mu; L_s=lamda*W_s; min=8*L_s+14*S; @gin(S); @bnd(1,S,5);
计算结果为：Local optimal solution found at iteration: 184
Objective value: 34.00000
Variable Value Reduced Cost LAMDA 15.00000 0.000000 MU 20.00000 0.000000 LOAD 0.7500000 0.000000 PWAIT 0.6312547 0.000000 S 2.000000 10.95338 W_Q 0.000000 0.000000 W_S 0.5000000E-01 0.000000 L_S 0.7500000 0.000000 即建造两个卸位，总成本为34.98万元。
(三)损失制排队模型
(见[1]第327页4.3节 系统容量有限制的情形M/M/C/N模型)或文献[8]) 损失制排队模型通常记为M/M/S/S,当S个服务器配占用后,顾客自动离开. 等待制排队系统的基本参数：
(1)系统损失的Plost概率.在Lingo中用函数@pel(load,s)表示: Plost=@pel(load,s)
其中s 是服务台的个数，load是系统到达负荷，即load=?=λ/μ（下面编程中，用load=?，lamba表示λ，mu表示μ）,上式中Plost就是文[1] p328中式(12-33)的Pc,即系统中有S
18
个顾客的概率.则有
(2)单位时间平均进入系统的顾客数?e: ?e??(1?Plos)t
?e称为有效到达率.
(3)系统的相对通过能力Q Q=1- Plost
(4)系统在单位时间内占用服务台的均值L (即平均队长Ls):
L??e?(平均排队长Lq?0)
Ls(5)系统服务台的效率: ??
（6）顾客的平均逗留时间Ws，队长Ls（在系统中的平均顾客数）和等待队长Lq（系统中排队等待的顾客的平均数），由Little公式：
Ws?Wq?1?1??
例题3_3
某单位电话交换台有一台200条内线的总机,已知上班8小时的时间内，有20%的内线分机平均每40分钟要一次外线电话，80%的分机平均每隔120分钟要一次外线。又知外线打入内线的电话为平均每分钟一次。假设与外线通话的时间为平均3分钟，并且上述时间均服从负指数分布，如果要求外线电话的通话率为95%，问该交换台应设置多少条外线？
解：(1)电话交换台的服务分为两类，第1类为内线打外线，其强度（单位时间（h）打出去的条数）为：
?1???60?40?0.2???0.8??200?140120?60
第2 类为外线打内线，单位时间(h)打进来的次数?2?1?60?60 从而总强度???1??2?140?60?200
（2）该系统为损失制，系统损失的概率不超过5%。即 Plost?5%
(3)系统的服务率(单位时间服务人数)?=60/3。 要求在满足条件下，外线数越少越好。Lingo程序为
lamda=200; mu=20; load=lamda/mu; Plost=@pel(load,s); Q=1-plost;lamda_e=lamda*Q; L=lamda_e/mu;eta=L/s; plost<0.05;
19