2016年中国民航大学航空安全研究所安全人机工程及运筹学之运筹学(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、计算题
1． 写出下列问题的动态规划的基本方程。
【答案】（l ）设状态转移方程为状态s k 到第n 阶段使
，最优值函数
最大的值，则动态规划的基本方程为:
，或
（2）设状态变量为表示
在s k 状态下从第k 阶段到第n 阶段使
最小的值，则动态规划的基本方程为:
2． 对下列整数规划问题，问用先解相应的线性规划然后凑整的办法能否得到最优整数解? （1）
，状态转移方程为
，最优值函数
表示从第k 阶段
（2）
【答案】 （1）在该线性规划问题的约束条件中分别加入松弛变量
，化为标准型
先不考虑上述模型中的整数约束，利用单纯形法进行求解，如表所示。
表
此时的最优解为
对该最优解进行凑整，当凑整为用分支定界法进一步求解此整数规划. 记
，因为
，最优目标值时均为非可行解。 为可行解，所以
。
时，为可行解，z=13; 当凑整为
。将原问题分解为两个子问题：
求得B 1的最优解
，
。
求得B 2的最优解为于是得到
。
，再将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，并化为标准型