2017年沈阳理工大学理学院827运筹学三考研强化模拟题
● 摘要
一、计算题
1． 在图中，（l ）用Dijkstra 方法求从v l 到各点的最短路; （2）指出对v l 来说，哪些顶点是不可到达的。
图
【答案】（1）
①v1已经获得P 标号，
计算从v l 到各点的最短路的步骤如下:
，修改v2，v5，v7的T 标号
因为
②v5已经获得P 标号，
，改写v6的T 标号为
，所以有
。
于是，有v 1到各点v 2，v 5，v 7，v 6，v 8的最短路为
（2）v 1不能到达v 3及v 4。
2． 某电话亭有一部电话，来打电话的顾客数服从泊松分布，相继两个人到达间隔的平均时间为10分钟，通 话时间服从负指数分布，平均数为3分钟。
求:
（l ）顾客到达电话厅要等待的概率。 （2）等待打电话的平均顾客数。
（3）当一个顾客至少要3分钟才能打电话时，电信局打算增设一台电话机，问到达速度增加
第 2 页，共 55 页
，
因为
到多少时，装第二台电话机才合理的?
（4）打一次电话要逗留10分钟以上的概率是多少? （可用指数式表示） （5）目前情况下，安装第二台电话机后，顾客的平均等待时间是多少? 【答案】（1
）
顾客到达电话厅要等待的概率为：
（3）由题意，令到达速度为λ人/小时，
解得
所以，当到达速度增加到10人/小时时，装第二台电话机才合理。 （4）顾客在系统中的逗留时间W ，服从参数为W ，服从参数为
的负指数分布。在本题中，逗留时间
的负指数分布。分布函数为
所以打一次电话要逗留10分钟以上的概率为:（5）安装两部电话机后，系统变为M/M/2模型
3． 试用可行方向法求解
【答案】原非线性规划问题可改写为:
第 3 页，共 55 页
取精度气，初始可行点。则
因为而取搜索方向则得又令
，即
，解得
; 令
，
，将其代入约束条件，并令，得
。
， ，因此
则构成下述线性规划问题:
，
，所以
为空集。
不是近似极小点。
为便于用单纯形法求解，令
从而得到
，得线性规划问题:
引入剩余变量y 4，松弛变量y 5，y 6，y 7及人工变量y 8。
第 4 页，共 55 页