2016年山东大学管理学院运筹学(线性规划部分)之运筹学基础及应用(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 用改进单纯形法求解以下线性规划问题。 （1）
（2）
-x
【答案】 （1）在上述线性规划的约束条件中分别引入松弛变量x 4，x 5，并化为标准型:
，初始基变
量
，对应的系数
x 1 为换入变量。
由此得到新的基B 1、基变量X BI 及系数C B1、非基变量X N1及系数C N1分别为:
计算换入变量x l 的系数向量P 1及B 1为:
计算非基变量的检验数为:
第 2 页，共 57 页
-1
得到初始
基，对应的系
数
。非基变量的检验数
；非基变
量
，则
由可确定x 2 为换入变量，再由
知x 5 为换出变量。
得到新的基B 2 、基变量X B2 及系数C B2 、非基变量X N2 及系数C N2 分别为:
计算换入变量x 2 的系数向量P 2 及B 2为：
非基变量的检验数向量为
此时，非基变量的检验数均为负，最优解为
，即
最优目标函数值为
。
。
-1
（2）在第二个约束条件中减去剩余变量x 3，再分别在第一、二个约束条件中加入人工变量x 4，x 5，在第三个约束条件中加入松弛变量x 6，得该线性规划的标准型:
得到初始基，
初始基变量，对应的系数
，
对应的系数
。非基变量的检验数
，则x 1 为换入变量。
，所以对应的换出变量为x 4 。
；
非基变量
由此得到新的基B1、基变量X B1及系数C B1、非基变量X N1 及C N1 分别为
，
计算换入变量x 1 的系数变量
，及B 1为
-1
， ，
计算非基变量的检验数为：
第 3 页，共 57 页
由
可确定x 2为换入变量，再由
知x 5为换出变量。
得到新的基B 2 、基变量XB 2 及系数C B2 、非基变量X N2及系数C N2分别为：
，
，
-1
，
计算换入变量x 2 的系数向量P 2 及B 2为
非基变量的检验数向量为
因为非基变量的检验数均大于0，故问题的最优解为：
最优目标值为
2． 一家公司要生产一个新产品（称之为产品3）。一单位产品3需要1单位的产品1和1单位的产品2才能 生产出来。在产品1和产品2开始生产之前，需要购买原材料，以及对工人的培训。此外，产品2还需要检验。 各项活动及其前导工作、相应的持续时间如表所示。
表
第 4 页，共 57 页