2016年武汉工程大学管理学院855运筹学考研内部复习题及答案
● 摘要
一、证明题
1． 假设线性规划问题为:
其中
，秩
运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。 【答案】一般情况下，经过迭代后解变为
再将上式代入目标函数式，整理后得到
令于是
再令则
时，此时的解就为最优解。
为G 的解的充要条件是:存在数。（本章定理4）
，使得
和
分别
这样当所有非基变量的检验数即2． 证明:设
，则
是不等式组（I ）和（II ）的解，且
【答案】（l ）先证充分性。由于x*是不等式组（I ）的解，
且
又由于
是不等式组
的解，且
②
由式①和式②，可知
**
故由教材第390页的定理3可知，（X ，Y ）为G 的解。
则
，
*
*
（2）再证必要性，由于（X ，Y ）为G 的解，所以有
，因此X 和Y 分别是不等式组（I ）和 （）
*
*
的解，且v=VG 。
二、计算题
3． 有一种设备最长使用3年时间，现考虑它在3年内的更新问题。在每年年初要作出决策，是继续使用还 是更新。如果继续使用，己知每年需要支付的维修费用如下表所示（单位:百元）:
表
如果更新设备，已知在各年年初购置该种设备的价格如表所示（残值忽略不计）（单位:百元）:
表
己知开始时该设备已经使用了l 年，问每年年初应怎样作出决策，才能使3年内该项设备的购置和维修总费 用最少? （用动态规划方法求解）
【答案】由更新设备与维修设备费用表可知，三年时间仅需选购一次设备。s k 表示k 年购进设备，可知s k 为0.1; xk 为设备在第k 年的使用年限; 设c k （x k ）为设备在第k 年的维修费用; P k 为设备在k 年购进时价格; f k （s k ）为 k 年购进设备总费用。
知第二年购进设备费用最小。