2017年西南交通大学运筹学(同等学力加试)考研复试核心题库
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点，
每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求解k 个线性规划（k 为优先级的个数），即可求出目标规划的满意解。
按如下规则:
二、计算题
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． 利用图解法求解下列矩阵对策，其中A 为
【答案】（l ）在矩阵中，由于第l 行优超于第2行，故可划去第2行，得到新的赢得矩阵为
设局中人‖的混合策略为
标分别是局中人‖采取混合策略
且对策的值显然为AB 。
了，由图可知，直线在任一点上的纵坐时的支付。根据最不利当中选取最有利的原则，局中人‖的最优选择，就是如何确定y ，以使三个纵坐标值中的最大值尽可能地小。由图可知，应选择y=OA，
图
由方程
所以，局中人I ，的最优混合策略为
和x 3可由以下联立方程求解。
*。则，而x 1*
所以，局中人Ⅰ的最优混合策略为。