2017年河南农业大学运筹学考研复试核心题库
● 摘要
一、简答题
1． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
2． 试写出M/M/1排队系统的Little 公式。
【答案】M/M/1排队系统的Little 公式为
二、计算题
3． 用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、无界解还是无可行解?
（1）
（2）
（3）
（4）
【答案】（1）如图所示，该问题的可行域为有界域。目标函数之=x1+3x2在点A 3处取得最大值，求解方程组
规划问题具有惟一最优解。
可得A 4的坐标为（2，4），所以x*=（2，4），z*=14，该线性
T
图
（2）如图所示，该线性规划问题的可行域无界。目标函数
值，求解方程组
，得A 点的坐标为（3/2, 1/2），
所以
在点A 处取得最小
该问题具有惟一最优解。
图
（3）如图所示，该问题的可行域无界。目标函数可以增加到无穷大，因此该问题无最优解或称为无界解。
图
（4）如图所示，该问题的可行域为空集，因此该线性规划无可行解。
图
4． 国内某电缆公司利用包括5个分销中心、8个客户区域的分销系统来销售其产品。配给每个客户区域一个专门的资源供应商，且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需求和雇员的工作量， 公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。如下表就是从5个分销中心到8个客户区域的供给成本（单位:1000美元）。求:
（1）使总成本最小的分销中心—客户区域的组合方式; （2）如果有，哪一分销中心没有任务分派;
（3）若进一步规定每个分销中心最多只能负责2个区域，那么新的分配方案又是什么? 【答案】 （1）由题意知该题为指派问题，添加虚拟的人，用匈牙利解法，具体过程如下：
相关内容
相关标签