2017年昆明理工大学J002运筹学(同等学力加试)复试实战预测五套卷
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
2． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l;
第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。
二、计算题
3． 已知有六台机床x 1，x 2，…，x 6，六个零件y 1，y 2，…，y 6。机床x 1可加工零件y 1; x 2可加工零件y 1，y 2; x3可加工零件y 1，y 2，y 3，x 4可加工零件y 2; x 5可加工零件y 2，y 3，x 4; x 6可加工零件y 2，y 5，y 6。现在要求制订一个加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件加工。试把这个问题化为求网络最大流的问题，求出能满足上述条件的加工方案。
【答案】依题意，画出最大容量的网络图，并令（l ）标号过程。进行标号，并找出增广链:
因v t 已标号，转入调整过程。
，如图所示。
图
（2）调整过程。按点的第一个标号找到一条增广链整:
调整后得如图所示的可行流，对这个可行流进入重新标号，寻找增广链。
。按照
在
上调
图
反复标号过程和调整过程，最后得到如图所示的结果。
图
可知，最优加工方案为:机床x 1加工零件y 1，机床x 2加工零件y 2，机床x 3加工零件y 3，机床x 5加工零件y 4，机床x 6加工零件y 6，机床x 4不加工零件，零件y 5没有机床加工。
最大流量是V （f ）=5。
4． 试用SUMT 外点法求解
并求出当罚因子等于1和10时的近似解。 【答案】构造惩罚函数
令
，得
的解为; 当M=l0时，
。
。
所以，当M=1时，
5． 银行要把总行与支行的计算机直接或间接地连接起来，保持连通，其中任意两银行之间的距离如表所示，而连接线费用为0.2万元/百米，求总费用最小的连接方案及最小总费用。
表
【答案】构建图论模型，如图所示。
图
采用破圈法，如图所示。求得最小支撑树，即为最优连接方案
图