运筹学习题2-单纯形法

《运筹学》习题（二）

班级 姓名

一、 判断题

1、 无约束的变量xj，通常令

，其中

，在用单纯形法求得的最优解中有可能同时出现

。

2、用单纯形法求解标准形的线性规划问题时，与

对应的变量都可以被选作换入变量。

3、单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负。

4、单纯形法计算中，选取最大正检验数

对应的变量xk作为换入变量，将使目标函数值得到最快的增长。

答：

二、 单纯形法迭代中，任何从基变量中替换出来的变量，在紧接着的下一次迭代中，会不会再进入基变量中？为什么？

答：

三、 下表为用单纯形法计算时某一步的表格，已知该线性规划问题中目标函数为

，约束条件均用“≤”关系连接，

,

为松弛变量，该表中解代入目标函数可得z =10。求a---g的值；问此表所给的解是否为最优解。 cj?-?zj 答：

四、 用单纯形法求解下述问题： max S=x1+x2

2x1+x2≤8

2x1+5x2≤20

x1+x2≤5

x1, x2≥0

解：加入松弛变量，用单纯形法解得如下： Cj→ CB 0 0 0 XB X3 X4 X5 b 8 20 5 1 X1 2* 2 1 1 X2 1 5 1 0 X3 1 0 0 0 X4 0 1 0 0 θi X5 0 0 1 2 a c d b 0 e -1 1 0 f 0.2 1 g

-S 1 0 0 -S 1 0 1 -S X1 X4 X2 X1 X4 X5 0 4 12 1 -4 3 4 2 -5 1 1 0 0 0 1 0 0 0 1 1/2 4 1/2* 1/2 0 0 1 0 0 1/2 -1 -1/2 -1/2 1 3 -1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 -1 -8 2 -1 ←λj ←λj ←λj 五、 试利用两阶段法第一阶段的求解，找出下述方程组的一个可行解，并利用计算得到的最终单纯形表说明该方程组有多余方程。

解：

附《运筹学》习题（二）答案

一、1、对（因为

的系数列向量只差一个符号，所以它们线性相关，不可能是某个可行基中的两列，因此在同一个基可行解中不可能出现

）；2、对；3、对；4、错。