运筹学期末考试试题及答案

2011年运筹学期末考试试题及答案

（用于09级本科）

一、单项选择题（每题3分，共27分）

1. 使用人工变量法求解极大化的线性规划问题时，当所有的检验数 j 0,但在基变量中仍含有非零的人工变量，表明该线性规划问题( D ) A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解

2.对于线性规划

maxz 2x1 4x2

s..t

x1 3x2 x3 4 x 1 5x2 x4 1 x1,x2,x3,x4

0如果取基B 11

10

，则对于基B的基解为（ B ）

A.X (0,0,4,1)T B.X (1,0,3,0)T C.X (4,0,0, 3)T D.X (23/8, 3/8,0,0)T

3.对偶单纯形法解最小化线性规划问题时，每次迭代要求单纯形表中（ C A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零4. 在n个产地、m个销地的产销平衡运输问题中，( D )是错误的。

A．运输问题是线性规划问题 B．基变量的个数是数字格的个数 C．非基变量的个数有mn n m 1个 D．每一格在运输图中均有一闭合回路 5. 关于线性规划的原问题和对偶问题，下列说法正确的是（ B ）

）

A．若原问题为无界解，则对偶问题也为无界解

B．若原问题无可行解，其对偶问题具有无界解或无可行解 C．若原问题存在可行解，其对偶问题必存在可行解 D．若原问题存在可行解，其对偶问题无可行解

6．已知规范形式原问题（max问题）的最优表中的检验数为( 1, 2,..., n)，松弛

变量的检验数为( n 1, n 2,..., n m)，则对偶问题的最优解为（ C ） A. ( 1, 2,..., n) B. ( 1, 2,..., n) C．( n 1, n 2,..., n m) D. ( n 1, n 2,..., n m) 7.当线性规划的可行解集合非空时一定（ D ）

A.包含原点 B.有界 C．无界 D.是凸集

8.线性规划具有多重最优解是指（ B ）

A.目标函数系数与某约束系数对应成比例。 B．最优表中存在非基变量的检验数为零。 C．可行解集合无界。 D．存在基变量等于零。

x1 x2 x3 2

9．线性规划的约束条件为 2x1 2x2 x4 4，则基可行解是（ D ）

x,x,x,x 0 1234

A.(2,0,0,1) B.(-1,1,2,4) C.(2,2,-2,-4) D.(0,0,2,4)

二、填空题(每题3分，共15分)

1．线性规划问题中，如果在约束条件中没有单位矩阵作为初始可行基，我们通常用增加

人工变量

的方法来产生初始可行基。

2.当原问题可行，对偶问题不可行时，常用的求解线性规划问题的方法是 单纯形

法。

3.原问题的第1个约束方程是“=”型，则对偶问题相应的变量是 无约束 变量。

4.运输问题中，当总供应量大于总需求量时，求解时需虚设一个_销__地，此地的需求量为总供应量减去总需求量。

4x1 6x2 1及2x1 4x2 20中至少有一个起作用，引入5. 约束x1 2x2 6,

x1 2x2 6 My14x1 6x2 1 My2

0-1变量，把它表示成一般线性约束条件为2x1 4x2 20 My3。

y1 y2 y3 2y1,y2,y3 0或1

三.考虑线性规划问题

minZ x1 3x2 4x3 13 3x1 2x2

x2 3x3 17

2x1 x2 x3 13 x1,x3 0,x2无约束

（1）把上面最小化的线性规划问题化为求最大化的标准型；（5分） （2）写出上面问题的对偶问题。（5分） 解：

''

3x2max Z x1 3x2 4x3''

2x2 3x1 2x2 x4 13

''

x2x2 3x3 x5 17

''

2x x x x3 13122

'' ,x2x1,x2,x3,x4,x5 0

四. 用图解法求解下面的线性规划问题（8分）

maxZ 2x1 x2

x1 x2 1

x 3x 1 12

x,x 0 12

解：最优解为：（0.5 ,0.5 ）

生产问题五. 某厂准备生产A、B、C三种产品，它们都消耗劳动力和材料，如下表：

试建立能获得最大利润的产品生产计划的线性规划模型，并利用单纯形法求解问题的最优解。（20分）

解：模型为：

标准化为：

maxZ 3x1 1x2 4x3 6x1 3x2 5x3 x4 45

3x1 4x2 5x3 x5 30 x,x,x 0 123

单纯形为：

六、已经线性规划

maxZ x1 2x2 3x3 4x4

x1 2x2 2x3 3x4 20

2x x 3x 2x 20 1234

x,x,x 0,x无约束

4 123

的对偶问题的最优解为Y (1.2,0.2)，利用对偶性质求原问题的最优解。（10

分）

解；其对偶问题为：

……………………… 5分

由y1,y2 0得

x1 2x2 2x3 3x4 20

2x1 x2 3x3 2x4 20 7分

把Y值代入原问题，知第一、二个约束为严格不等式， 故有x1 x2 0 9分 解得X* (0,0,4,4)T 10分

解：