运筹学习题2-单纯形法.pdfVIP

《运筹学》习题（二）

班级姓名

一、判断题

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

，其中

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

。

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

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

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

少有一个基变量的值为负。

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

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

答：

二、单纯形法迭代中，任何从基变量中替换出来的变量，在紧接着的下一

次迭代中，会不会再进入基变量中？为什么？

答：

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

数为

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

,

为松弛变量，该表中解代入目标函数可得z=10。求ag的值；问此表所给的解

是否为最优解。

2c010.2

ade01

cj?-?zjb-1fg

答：

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

2x1+x2≤8

2x1+5x2≤20

x1+x2≤5

x1,x2≥0

解：加入松弛变量，用单纯形法解得如下：

Cj→11000

θi

CBXBbX1X2X3X4X5

0X382*1100

0X42025010

0X5511001

-S011000←λj

1X1411/21/200

0X41204-110

0X5101/2*-1/201

-S-401/2-1/200←λj

1X131010-1

0X440031-8

1X2201-102

-S-50000-1←λj

五、试利用两阶段法第一阶段的求解，找出下述方程组的一个可行解，并

利用计算得到的最终单纯形表说明该方程组有多余方程。

解：

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

一、1、对（因为

的系数列向量只差一个符号，所以它们线性相关