2017年河南大学运筹学与控制论综合(运筹学、常微分方程、概率论与数理统计)之运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大
; 。分支定界法就是将B 的可行域分成
:， 最终求到z*。
二、计算题
3． 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。
（1）
（2）
【答案】 （1）在第二个约束条件两边同时乘以-1，得到该线性规划问题的系数矩阵
因为P 1、P 2线性无关，故有
1T
令非基变量x 3=x4=0，解得x 1=1，x 2=2，故有基可行解x （）=（1, 2, 0, 0），z 1=8。
因为P 1、P 3线性无关，故有
令非基变量x 2=x4=0，解得因为P 1、P 4线性无关，故有
令非基变量x 2=x3=0，解得因为P 2、P 3线性无关，故有
令非基变量x 1=x4=0，解得因为P 2、P 4线性无关，故有
令非基变量x 1=x3=0，解得因为P 3、P 4线性无关，故有
令非基变量x 1=x2=0，解得
在z 1，z 2，z 3中，z 3为最大值，所以最优解（2）其系数矩阵为
因为P 1、P 2线性无关，故有
不是可行解。
不是可行解。 故有基可行解
故有基可行解
。
故
不是可行解。
令非基变量x 3=x4=0，解得因为P 1、P 3线性无关，故有
令非基变量x 2=x4=0，解得因为P 1、P 4线性无关，故有
令非基变量x 2=x3=0，解得因为P 1、P 4线性无关，故有
令非基变量x 1=x4=0，解得因为P 3、P 4线性无关，故有
令非基变量x 1=x2=0，解得
不是可行解。
为基可行解，
不是可行解。
为基可行解，。
为基可行解，。
因为P 2、P 4线性相，故x 2 , x 4 不能构成基变量。 在z 2，z 4，z 5中，z 2为最大值，所以最优解
4． 已知A 、B 两人对策时对A 的赢得矩阵如下，求双方各自的最优策略及对策值。
【答案】该对策为混合对策。利用优超原则，由于第三行优超第一行和第四行，故可划去第1、4行，得到新的赢得矩阵
由A l 可知，第2列优超第1列，第4列优超第3列，故可划去第1、3列，得到新的赢得矩阵
由A 2可知，第2列优超第1列，故可划去第l 列，得到新的赢得矩阵
相关内容
相关标签