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

（用于09级本科）

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

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

2.对于线性规划

maxz??2x1?4x2s..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 ）

第 1 页 共 7 页

）

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?1234A.(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个约束方程是“=”型，则对偶问题相应的变量是 无约束 变量。

第 2 页 共 7 页

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

4x1?6x2?1及2x1?4x2?20中至少有一个起作用，引入5. 约束x1?2x2?6,x1?2x2?6?My14x1?6x2?1?My20-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?

第 3 页 共 7 页

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

maxZ??2x1?x2?x1?x2?1 ?x?3x??1?12?x,x?0?12

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

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

产 品 消 A B C 资源量

耗 资 源

设备（台时/件） 6 3 5 45

材料（kg/件） 3 4 5 30 利润（元/件） 3 1 4 试建立能获得最大利润的产品生产计划的线性规划模型，并利用单纯形法求解问题的最优解。（20分）

解：模型为：

第 4 页 共 7 页

标准化为：

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 页 共 7 页

分）

解；其对偶问题为：

……………………… 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分

七、有某运费最少的运输问题,其运价表如表： 销 地 B2 B4 B1 B3 产 地 产量 8 9 7 A1 A2 6 4 2 8 7 5 9 6 5 10 7 5 8 8 3 5 A3 销量 求此运输问题的最优调运方案。(10分) 第 6 页 共 7 页

解：

第 7 页 共 7 页