2016年北京林业大学信息学院管理科学与工程运筹学考研复试题库
● 摘要
一、计算题
1． 利用库恩一塔克条件求解以下问题:
（l ）试写出库恩一塔克条件。
（2）a 满足什么条件以上问题有最优解? （3）分别求出相应的最优解和最优值。 【答案】（l ）所求问题变形为
故库恩一塔克条件为
（2）由约束条件可知，（3）
时，存在最优解
时，时，解得
由且
目标函数值
目标函数值为
，故
其余情况均不符合 故当当
时，最优解为
时，最优解为
2． 下表给出了12种工件在设备A 和B 上的加工时间，试求:
（l ）若所有工件都先在设备A 上加工，再在设备B 上加工，试确定使总加工时间最短的工件加工顺序，并计算总加工时间;
（2）若工件8~12先在设备B 上加工，再在设备A 上加工，其他条件同上，试设计一启发式算法，以计算最小总加工时间和安排相应的工件最优加工顺序。
表
【答案】（l ）采用启发式算法进行计算，计算过程如下表所示。
由上表可以看出，总加工时间最短的工件加工顺序为 4→8→0→5→1→2→7→6→9→1→12→3 总加工时间为（2+3+3+4+6+8+12+7+9+5+10+11）+4=84。 （2）可设计如下启发式算法: ①②③
④将A j ，B j 删去，即不再考虑己排好加工顺序的工件j ； ⑤转入步骤②，直至步骤②中的工件加工时间表变成空集。 故设备A 最优加工顺序为7→2→5→6→l →3→4→12→9→1→10→8 设备B 最优加工顺序为12→9→11→10→8→7→2→5→6→1→3→4
总加工时间为（12+8+4+7+5+11+2）+（10+9+6+3+3）=49+31=80。
3． 试用乘子法求解非线性规划问题（取c=2）:
【答案】设定义拉格朗日函数
于是得到
解得，
4． 用图解法求解下列线性规划问题，并指出问题是具有惟一最优解、无穷多最优解、无界解还是无可行解? （1）
（2）
（3）
（4）
【答案】（1）如图所示，该问题的可行域为有界域。目标函数之=x1+3x2在点A 3处取得最大值，
相关内容
相关标签