2016年华中科技大学自动化学院828运筹学考研冲刺密押卷及答案
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 什么是可行流?
【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记
（2）平衡条件 对于中间点，流出量=流入量，即对每个
按如下规则:
式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。
3． 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。
【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。 （2）设备充分利用、总加工时间最短等某一或某几种目标函数最优。
（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。
（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不同施 使整个施工按照最短施工时间保持一定施工节拍进行流工工序如何搭接排序组成一定施工工艺，水作业，同时消耗人、机、材等资源也合理。
二、证明题
4． 设线性规划问题解。
【答案】其对偶问题为
有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优
1
设是原问题的最优解，则其对应的基矩阵B 必存在
，由此得
，即可得，
这时Y 是对偶问题的可行解，它使由于原问题的最优解
，使目标函数取值
，即是对偶
问题的最优解，因此单纯形乘子证明:（l ）若（2）若
，是对偶问题的最优解。
（称
条边的圈。
，假设
为G 的最小次）。
5． 设G=（V ，E ）是一个简单圈，令
，则G 必有圈； ，则G 必有包含至少
（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点，即
相矛盾。故假设不成立， 所以，G 必有圈。
（2）若的次至少为
，设与，也至少与
对应的点为v k ，则v k
必与个端点相连。如果v k 与v i
这
个端点相连。由（l ）的结论知，G
个端点不构成圈，那么在端
条边的圈。
v k 至少与这中必有圈（由于对圈中的连通图而言，点处必向外延伸（因为最小次为另一端点，对该圈而言，边数大于
个端点构成圈）。
， 不与其中某点相连，必与其外某点相连）经连通链而到
条，故G 必定 是包含不少于占
（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。 6． 证明下列定理: （1）设有两个矩阵对策，
，L 为任一常数，则有
（2）设有两个矩阵对策
，
，
（3）设
（定理8） 为矩阵对策，且
了为斜对称矩阵（亦称这种对策为对称对策）。
，其中
，
。（定理7）
，其中a>0
为任一常数。则