2017年天津职业技术师范大学运筹学(同等学力加试)复试仿真模拟三套题
● 摘要
一、简答题
1． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?
【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
二、计算题
3． 对下列整数规划问题，问用先解相应的线性规划然后凑整的办法能否得到最优整数解?
（1）
（2）
【答案】 （1）在该线性规划问题的约束条件中分别加入松弛变量
，化为标准型
先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。
表
此时的最优解为
用分支定界法进一步求解此整数规划. 记题：
求得B 1的最优解
求得B 2的最优解为于是得到
，因为
，最优目标值。
时，为可行解，z=13; 当凑整
为
对该最优解进行凑整，当凑整
为
时均为非可行解。
为可行解，所以
。将原问题分解为两个子问
，。
。
，再将B 1 分解为两个子问题：
求得B 3 的最优解为
求得B 4 的最优解为B 3已求得整数解，则可取为
故
义，可舍去。继续将B 4分解为两个子问题：
。
，对于B 2 而言，继续分解已无意
B 5无可行解，舍去。
求得B 6 的最优解
划然后凑整的办法能得到最优整数解。
。
所以，得到最优解x l =3，x 2=2，与用舍去法得到的最优解一致。所以，用先解相应的线性规（2）在该线性规划问题的约束条件中分别加入松弛变量x 3，x 4，并化为标准型
先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。
表
相关内容
相关标签