2012--2013运筹学期末考试试题及答案

楚大

2012---2013上学期

经济信息管理及计算机应用系

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

学号

一、单项选择题：

1、在下面的数学模型中，属于线性规划模型的为（ A ）。

22maxS4XYmaxSXYminS2XYminS3XYXY2D.s.t.XY3 XY3C.s.t.B.s.t.2XY1A.s.t.

X,Y0X,Y0X,Y0X,Y0

2、线性规划问题若有最优解，则一定可以在可行域的 （ A ）上

达到。

A．顶点 B．内点 C．外点 D．几何点

3、在线性规划模型中，没有非负约束的变量称为 （ C ）

A．多余变量 B．松弛变量 C.自由变量 D．人工变量

4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那

么该线性规划问题最优解为（ C ）。

A.两个 B.零个 C.无穷多个 D.有限多个

5、线性规划具有唯一最优解是指（ B ）

A．最优表中存在常数项为零B．最优表中非基变量检验数全部非零

C．最优表中存在非基变量的检验数为零D．可行解集合有界

6、设线性规划的约束条件为

x1x2x332x12x2x44 x,,x041

则基本可行解为（ C ）。

A．(0, 0, 4, 3) B． (3, 4, 0, 0)

C．(2, 0, 1, 0) D． (3, 0, 4, 0)

7、若运输问题已求得最优解，此时所求出的检验数一定是全部

（ D ）

A、小于或等于零 B．大于零 C．小于零 D．大

于或等于零

8、对于m个发点、n个收点的运输问题，叙述错误的是( D )

A．该问题的系数矩阵有m×n列

阵有m+n行

C．该问题的系数矩阵的秩必为m+n-1

必唯一

9、关于动态规划问题的下列命题中错误的是（ A ）

A、动态规划分阶段顺序不同，则结果不同

B、状态对决策有影响

C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独

立性

D、动态规划的求解过程都可以用列表形式实现

10、若P为网络G的一条流量增广链，则P中所有正向弧都为G的

（ D ） D．该问题的最优解 B．该问题的系数矩

A．对边 B．饱和边 C．邻边 D．不饱

和边

一、 判断题。

1、图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者

是一致的。（ T ）

2、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大

的另一个可行解。（ F ）

3、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的

数字可以从单纯形表中删除，而不影响计算结果。（ T ）

4、若线性规划问题中的bi,cj值同时发生改变，反映到最终单纯形表

中，不会出现原问题与对偶问题均为非可行基的情况。（ F ）

5、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有

无穷多最优解。（ T ）

6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。

（ T ）

7、对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优

解。（ F ）

8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具

有递推关系的单阶段的决策问题。（T ）

9、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的

写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要

严格注意。（F ）

10、网络最短路线问题和最短树问题实质上是一个问题。（F ）

二、 填空题。

1、线性规划中，满足非负条件的基本解称为__基本可行解______，

对应的基称为___可行基_____。

2、线性规划的目标函数的系数是其对偶问题的___右端常数_____；而若线性规划为最大化问题，则对偶问题为__最小化问题______。

3、在运输问题模型中，mn1个变量构成基变量的充要条件是___

不含闭回路_____。 4、动态规划方法的步骤可以总结为：逆序求解__最优目标函数

______，顺序求_最优策略_______、__最优路线______和__最优

目标函数值______。

5、工程路线问题也称为最短路问题，根据问题的不同分为定步数问

题和不定步数问题；对不定步数问题，用迭代法求解，有___函数_____

迭代法和__策略______迭代法两种方法。

6、在图论方法中，通常用____点____表示人们研究的对象，用__边

______表示对象之间的联系。

7、线性规划maxZx1x2,2x1x26,4x1x28,x1,x20的最优解是(0，

6),它的第1、2个约束中松驰变量（S1,S2）= （ (0,2) ）

8、运输问题的检验数λij的经济含义是（ xij增加一个单位总运费增

加λij ）

四、计算题。

1、考虑线性规划问题：

maxz2x14x23x3

3x14x22x3602xx2x40 123s.t.x13x22x380

x1,x2,x30

（a）、写出其对偶问题；

（b）、用单纯形方法求解原问题；

（c）、用对偶单纯形方法求解其对偶问题；

（d）、比较（b）（c）计算结果。

1：解 a）、其对偶问题为

minz60y140y280y3

3y12y2y324yyy4123s.t.2y12y22y33

y1,y2,y30

b）、用单纯形方法求解原问题时每步迭代结果：

c）、用对偶单纯形方法求解对偶问题时每步迭代结果：

d）、对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问

题的对偶即原问题，因此（b）、（c）的计算结果完全相同。

五、证明题：

1、对问题minf（x1,x2）=x1^2+25x2^2中的变量x=(x1,x2)T作线性变

换：y1=x1,y2=5x2,则原来的无约束优化问题变为：

minF(y1,y2)=y1^2+y2^2

证明：从任意初始点y0出发，用最速下降法问题（* *）迭代一轮

即可求得最优化解，从中你可以得到什么启示？

证：

从任意初始点为y0=（y1^0,y2^0）T，令P0=-f(y0),则代入

f(y)=(1+2t)^2[(y10)^2+(y20)^2],令

df/dt=0

得t0=-1/2,故y1=y0+tp0=(0,0)T

为原问题的最优解，可知，若（UMP）具有

Minf(x)= Xi^2

形式，用最速下降法迭代一次即可求得最优解。

楚大

2012---2013上学期

经济信息管理及计算机应用系

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

学号

一、单项选择题：

1、在下面的数学模型中，属于线性规划模型的为（ A ）。

22maxS4XYmaxSXYminS2XYminS3XYXY2D.s.t.XY3 XY3C.s.t.B.s.t.2XY1A.s.t.

X,Y0X,Y0X,Y0X,Y0

2、线性规划问题若有最优解，则一定可以在可行域的 （ A ）上

达到。

A．顶点 B．内点 C．外点 D．几何点

3、在线性规划模型中，没有非负约束的变量称为 （ C ）

A．多余变量 B．松弛变量 C.自由变量 D．人工变量

4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那

么该线性规划问题最优解为（ C ）。

A.两个 B.零个 C.无穷多个 D.有限多个

5、线性规划具有唯一最优解是指（ B ）

A．最优表中存在常数项为零B．最优表中非基变量检验数全部非零

C．最优表中存在非基变量的检验数为零D．可行解集合有界

6、设线性规划的约束条件为

x1x2x332x12x2x44 x,,x041

则基本可行解为（ C ）。

A．(0, 0, 4, 3) B． (3, 4, 0, 0)

C．(2, 0, 1, 0) D． (3, 0, 4, 0)

7、若运输问题已求得最优解，此时所求出的检验数一定是全部

（ D ）

A、小于或等于零 B．大于零 C．小于零 D．大

于或等于零

8、对于m个发点、n个收点的运输问题，叙述错误的是( D )

A．该问题的系数矩阵有m×n列

阵有m+n行

C．该问题的系数矩阵的秩必为m+n-1

必唯一

9、关于动态规划问题的下列命题中错误的是（ A ）

A、动态规划分阶段顺序不同，则结果不同

B、状态对决策有影响

C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独

立性

D、动态规划的求解过程都可以用列表形式实现

10、若P为网络G的一条流量增广链，则P中所有正向弧都为G的

（ D ） D．该问题的最优解 B．该问题的系数矩

A．对边 B．饱和边 C．邻边 D．不饱

和边

一、 判断题。

1、图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者

是一致的。（ T ）

2、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大

的另一个可行解。（ F ）

3、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的

数字可以从单纯形表中删除，而不影响计算结果。（ T ）

4、若线性规划问题中的bi,cj值同时发生改变，反映到最终单纯形表

中，不会出现原问题与对偶问题均为非可行基的情况。（ F ）

5、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有

无穷多最优解。（ T ）

6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。

（ T ）

7、对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优

解。（ F ）

8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具

有递推关系的单阶段的决策问题。（T ）

9、图论中的图不仅反映了研究对象之间的关系，而且是真实图形的

写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要

严格注意。（F ）

10、网络最短路线问题和最短树问题实质上是一个问题。（F ）

二、 填空题。

1、线性规划中，满足非负条件的基本解称为__基本可行解______，

对应的基称为___可行基_____。

2、线性规划的目标函数的系数是其对偶问题的___右端常数_____；而若线性规划为最大化问题，则对偶问题为__最小化问题______。

3、在运输问题模型中，mn1个变量构成基变量的充要条件是___

不含闭回路_____。 4、动态规划方法的步骤可以总结为：逆序求解__最优目标函数

______，顺序求_最优策略_______、__最优路线______和__最优

目标函数值______。

5、工程路线问题也称为最短路问题，根据问题的不同分为定步数问

题和不定步数问题；对不定步数问题，用迭代法求解，有___函数_____

迭代法和__策略______迭代法两种方法。

6、在图论方法中，通常用____点____表示人们研究的对象，用__边

______表示对象之间的联系。

7、线性规划maxZx1x2,2x1x26,4x1x28,x1,x20的最优解是(0，

6),它的第1、2个约束中松驰变量（S1,S2）= （ (0,2) ）

8、运输问题的检验数λij的经济含义是（ xij增加一个单位总运费增

加λij ）

四、计算题。

1、考虑线性规划问题：

maxz2x14x23x3

3x14x22x3602xx2x40 123s.t.x13x22x380

x1,x2,x30

（a）、写出其对偶问题；

（b）、用单纯形方法求解原问题；

（c）、用对偶单纯形方法求解其对偶问题；

（d）、比较（b）（c）计算结果。

1：解 a）、其对偶问题为

minz60y140y280y3

3y12y2y324yyy4123s.t.2y12y22y33

y1,y2,y30

b）、用单纯形方法求解原问题时每步迭代结果：

c）、用对偶单纯形方法求解对偶问题时每步迭代结果：

d）、对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问

题的对偶即原问题，因此（b）、（c）的计算结果完全相同。

五、证明题：

1、对问题minf（x1,x2）=x1^2+25x2^2中的变量x=(x1,x2)T作线性变

换：y1=x1,y2=5x2,则原来的无约束优化问题变为：

minF(y1,y2)=y1^2+y2^2

证明：从任意初始点y0出发，用最速下降法问题（* *）迭代一轮

即可求得最优化解，从中你可以得到什么启示？

证：

从任意初始点为y0=（y1^0,y2^0）T，令P0=-f(y0),则代入

f(y)=(1+2t)^2[(y10)^2+(y20)^2],令

df/dt=0

得t0=-1/2,故y1=y0+tp0=(0,0)T

为原问题的最优解，可知，若（UMP）具有

Minf(x)= Xi^2

形式，用最速下降法迭代一次即可求得最优解。