运筹学 试题.doc

运筹学试题
一、 填空题
1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加_人工变量__的方法来产生初始可行基。
2．在图论方法中，树具有_____的特点，树中的连线数必定等于__ ___。
3．线性规划数学模型三要素： 、 、
4．在多目标决策问题中，当目标中规定了x=b为达到了目标，则必须同时满足 才算达到了目标。
7．动态规划是解决 决策过程最优化问题的一种方法。
1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解 。
2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。
3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。
4、在图论中，称 无圈的 连通图为树。
5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。
3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是_无约束__变量。
4．求最小生成树问题，常用的方法有：避圈法和 _破圈法__。
二、单项选择题
1．设P是线性规划问题，D是其对偶问题，则( )不正确。
A． P有最优解，D不一定有最优解
B．若P和D都有最优解，则二者最优值肯定相等
C．若P无可行解，则D无有界最优解
D.D的对偶问题为P
2．在求minz的线性规划问题中，则( )不正确。
A． 最优解只能在可行基解中才有
B． 最优解只能在基解中才有
C． 基变量的检验数只能为零
D． 有可行解必有最优解
3．用图解法求解下列问题：max S=2x-3y
s.t.-x+2y<=2
x+2y<=6
x-y<=3
x+3y>=3
x,y>=0
其最优解为（ ）
A．(2，2) B．(4，1) C．(3，0) D．(2，5)
4．若运输问题在总供应量大于总需要量时，( )。
A． 必须用线性规划单纯形法求最优解
B． 不存在可行解
C． 虚设一个需求点
D． 虚设一个供应点
3、对于线性规划问题，下列说法正确的是（ D ）
A 线性规划问题可能没有可行解
B 在图解法上，线性规划问题的可行解区域都是“凸”区域
C 线性规划问题如果有最优解，则最优解可以在可行解区域的顶点上到达
D 上述说法都正确
4、下面哪些不是线性规划问题的标准形式所具备的（ C ）
A 所有的变量必须是非负的
B 所有的约束条件（变量的非负约束除外）必须是等式
C 添加新变量时，可以不考虑变量的正负性
D 求目标函数的最小值
6、在用单纯形法求解线性规划问题时，下列说法错误的是（ D ）
A 如果在单纯形表中，所有检验数都非正，则对应的基本可行解就是最优解
B 如果在单纯形表中，某一检验数大于零，而且对应变量所在列中没有正数，则线性规划问题没有最优解
C 利用单纯形表进行迭代，我们一定可以求出线性规划问题的最优解或是判断线性规划问题无最优解
D 如果在单纯形表中，某一检验数大于零，则线性规划问题没有最优解
1．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题 【 】
A．有唯一的最优解 B．有无穷多最优解
C．为无界解 D．无可行解
2．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中 【 】
A．b列元素不小于零 B．检验数都大于零
C．检验数都不小于零 D．检验数都不大于零
3．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为 【 】
A．3 B．2
C．1 D．以上三种情况均有可能
4．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【 B 】

5．在运输方案中出现退化现象，是指数字格的数目 【 】
A．等于 m+n B．等于m+n-1
C．小于m+n-1 D．大于m+n-1
6．关于线性规划的原问题和对偶问题，下列说法正确的是 【 】
A．若原问题为元界解，则对偶问题也为无界解
B．若原问题无可行解，其对偶问题具有无界解或无可行解
c．若原问题存在可行解，其对偶问题必存在可行解
D．若原问题存在可行解，其对偶问题无可行解
7．下列说法正确的是 【 】
A．线性规划问题的基本解对应可行域的顶点
也必是该问题的可行解

D．单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解
三、判断
3、如果在单纯形表中，所有的检验数都为正，则对应的基本可行解就是最优解（×）
4、如果单纯形表中，某一检验数大于0，而且对应变量所在列中没有正数，则线性规划问题无最优解（√）
6、在线性规划的模型中全部变量要求是整数（×）
增加约束条件时, 线性规划模型的可行域不扩大。( )
(1) 线性规划问题的对偶问题的对偶问题是原问题。 ( )
(2) 动态规划的逆推与顺推解法得到相同的最优解。( )
(3) 若某种资源的影子价格等于,在其他条件不变的情况下,当该种资源增加5时，相应的目标函数值将增大5。( )
(4) 加非负权无向连通图中任两点间必存在最短路径。 ( )

四、名词解释
线性规划：一般地，如果我们要求出一组变量的值，使之满足一组约束条件，这组约束条件只含有线性不等式或线性方程，同时这组变量的值使某个线性的目标函数取得最优值（最大值或最小值）。这样的数学问题就是线性规划问题
可行解：在线性规划问题的一般模型中，满足约束条件的一组值称为此线性规划问题的可行解，
最优解：在线性规划问题的一般模型中，使目标函数达到最优值的可行解称为线性规划问题的最优解。
运输问题：将一批物资从若干仓库（简称为发点）运往若干目的地（简称为收点），通过组织运输，使花费的费用最少，这类问题就是运输问题
闭回路：如果在某一平衡表上已求得一个调运方案，从一个空格出发，沿水平方向或垂直方向前进，遇到某个适当的填有调运量的格子就转向前进。如此继续下去，经过若干次，就一定能回到原来出发的空格。这样就形成了一个由水平线段和垂直线段所组成的封闭折线，我们称之为闭回路
四、问答
1、 用图解法求解两个变量线性规划问题的解的一般步骤
答： (1)在平面直角坐标系中，求出可行解区域，可行解区域是各约束条件所表示的半平面的公共部分。
(2)求最优解：将坐标函数中的f看作参数，作出等值线。选取一条等值线，使它与可行解区域有公共点，并取得最大值或是最小值

3、简要描述求解线性规划问题两阶段
答：第一阶段，如果线性规划问题已经具有典则形式，并且约束方程右端常数非负，则可以直接写出对应的单纯形表，进入第二阶段，否则，在第一阶段应引入辅助问题，求出辅助问题的最优解，再得到原问题的基本可行解对应的单纯形表或判定原问题无可行解，在两个阶段的计算过程中，都可以利用单纯形法。

4、解“运输问题”的一般步骤
答：(1)编制初始调运方案：我们可以利用“西北角法”来编制初始调运方案。
(2)检验：为了判定某一调运方案是否最优，我们可以利用“位势法”来求出检验数。
(3)调运方案调整。
五、解答题
1．某机械部件每件进厂价为500元，年需求总额为60万元，求得最佳订货批量为 300件，年保管费用率为12％。求按经济订货批量进货时，年订货多少次，每次订货费用、年保管费用和年总存货费用各是多少。
2．用单纯形法求解某线性规划问题得到最终单纯形表：
Cj
基变量
50
40
10
60
S
X1
X2
X3
X4
a
c
0
1
1/2
1
6
b
d
1
0
1/4
2
4

Cj-Zj
0
0
e
f
G
（1） 给出a,b,c,d,e,f,g的值或表达式；
（2） 指出原问题是求目标函数的最大值还是最小值；
（3） 用a+Da，b+Db分别代替a和b ，仍然保持上表是最优单纯形表，求Da，Db满足的范围。
四、(每小题10分，共20分)
1． 求总运费最小的运输问题，某步运输图如下：

B1
B2
B3
供应量
A1
3（3）
（5）
（7）
3
A2
2（4）
4（2）
（4）
6
A3
（5）
1（6）
5（3）
d
需要量
a
b
c
e

(1)写出a,b,c,d,e的值，并求出最优运输方案；
（2)A3到B1的单位运费满足什么条件时，表中运输方案为最优方案。
2． 如图所示的运输网络上，求最大流，边上括号内为（cij）

v1 (3) v3

(4) (5)

vs (1) (1) (3) vt

(5) (2)

v2 (2) v4

五、(本题8分)
某风景区有6个海岛，相互间的距离如下表所示(哩)。现欲架设海上浮桥，使各岛相连且与陆地相连，已知第1个海岛离海岸最近，为0．3哩，求使架设浮桥长度最短的方案。

2
3
4
5
6
1
1．0
3．0
2．5
5．0
4．0
2

2．6
1．7
4．2
3．2
3

1．0
2．5
1．3
4

2．6
1．8
5

1．3
三、多项选择题
19．线性规划问题的标准型最本质的特点是 【 】
A．目标要求是极小化 B．变量可以取任意值
C．变量和右端常数要求非负 D．约束条件一定是等式形式
22．关于运输问题，下列说法正确的是 【 】
A．在其数学模型中，有m+n—1个约束方程
B．用最小费用法求得的初始解比用西北角法得到的初始解在一般情况下更靠近最优解
C．对任何一个运输问题，一定存在最优解
D．对于产销不平衡的运输问题。同样也可以用表上作业法求解