2017年成都理工大学运筹学(同等学力加试)复试实战预测五套卷
● 摘要
一、简答题
1． 简述求解最小费用最大流的赋权网络设置方法。
【答案】解:对网络G=（ V ，E ，C ，d ），有可行流f ，保持原网络各点， 每条边用两条方向相反的有向边代替，各边的权
②当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
按如下规则:
二、计算题
3． 利用库恩一塔克条件求解以下问题:
（l ）试写出库恩一塔克条件。
（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为
故库恩一塔克条件为
（2）由约束条件可知，（3）
时，存在最优解
时，时，解得
由且
目标函数值
目标函数值为
，故
其余情况均不符合 故当当
时，最优解为
时，最优解为
4． 用递推方法求解下列问题。
（2）
（4）
（5）
（6）
（1）s 0=0，【答案】将问题划分为三个阶段k=1, 2, 3；设状态变量s k 为第k 阶段的结束状态，s 3=10；决策变量为x k ，设最优值函数
由
应用顺推法，
递推公式为
，最优解为x l *=s1
=200，最优解x 3*=10 所以，该问题的最优解为:
决策变量为x k ，设最优值函数
; 其最优值为z*=200。
表示从第1阶段至第k 阶段的最大值。
用顺推法，递推公式为
，最优解为
，最优解为
。
由二次函数的性质，解得: 最优解为解为:
，经比较，在端点
; 其最优值为z*=45/2。
表示从第1阶段至第k 阶段的最大值。于
按顺推法，递推公式为
，最优解为
，有
处能达到最优值，所以该问题的最优
得
（2）将问题划分为三个阶段k=l，2，3; 设状态变量s k 为第k 阶段的结束状态，s 0=0，s 3≤10;
表示从第1阶段至第k 阶段的最大值。 得
，
于是得到
（3）将此问题划分为n 个阶段。阶段变量k=1，2，···，n ; 设状态变量s k 为第k 阶段的结束状态，s 0=0，s n =c: 决策变量为x k ; 设最优值函数是有