2017年西安石油大学946运筹学之运筹学教程复试实战预测五套卷
● 摘要
一、简答题
1． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
二、计算题
3． 现有线性规划问题
先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化? （1）约束条件式②的右端常数由20变为30; （2）约束条件式②的右端常数由90变为70; （3）目标函数中x 3的系数由13变为8; （4）x 1的系数向量由
、变成
;
; 。
第 2 页，共 58 页
（5）增加一个约束条件式③:
（6）将原约束条件②改变为
【答案】在上述线性规划问题的第①，②个约束条件中分别引入松弛变量x 4，x 5，得
建立初始单纯形表，并利用单纯形法进行迭代计算，如表所示。
表
所以，原问题得到最优解为
（l ）约束条件式①的右端常数由20变为
30
，最优目标函数值为z*=100。
列出单纯形表，并利用对偶单纯形法求解，求解过程如表所示。
表
所以，线性规划为题的最优解变为
第 3 页，共 58 页
，最优目标函数值为。
（2） 约束条件②的右端常数由90变为
70
列出初始单纯形表，并利用对偶单纯形法进行迭代计算，求解过程如表所示。
所以，线性规划的最优解变为
（3）目标函数中x 3的系数由13变为8
，最优目标函数值为。
，
因为在最终单纯形表中x3是非基变量，其目标函数的系数变化后，对应的检验数仍小于0。所以，此时线性规划问题的最优解不发生变化。
（4）x 1的系数列向量由（l ，一2）变为（o ，5） x 在最终单纯形表中的系数列向量变为
其对应的检验数变为
所以线性规划问题的最优解不变。 （5）增加一个约束条件③：
在约束条件式③中加入松弛变量x 6，得纯形表，并进行 进一步迭代，求解过程如表所示。
表
l
T
T
。将此约束条件加入原单
第 4 页，共 58 页