一、填空题(每小题3分,共15分)1用单纯形法求解线性规划问题时,单纯形表中的每个解对应的是线性规划
问题的一个
,与图解法中其
一一对应。
2在对偶单纯形法中,确定换入变量时采用的是最小比值规则(θ规则),采
用该规则的主要目的是保证对偶问题的解总是
。
3用表上作业法(运输单纯形法)解运输规划模型时,作业表应满足的两个
基本条件是
。
4在动态规划模型中,状态变量表示每个阶段
时所处的自然状况或
客观条件,它要满足
的特性。
5
若解整数规划的单纯形表的最终表中有约束行为:
x1
14
x3
25
x4
83
,
其中x1为基变量,则其对应的割平面方程为
。
二、单项选择题(每题3分,共15分)1、下面哪一个表达式可以作为目标规划的目标函数
A、mi
d
1
d
1
B、max
d
1
d
1
C、mi
d
1
d
1
D、max
d
1
d
1
2、线性规划问题可行域的每一个顶点,对应的是一个
A、基本可行解
B、非可行解
C、最优解
本解
。D、基
3、在整数规划割平面方法最终单纯形表中得到的一个各变量之间关系式为
x1
45
x2
14
x3
85
,则其确定的割平面方程为
。
fA、
15
x2
14
x3
35
15
x2
14
x3
35
B、
15
x2
34
x3
35
C、
15
x2
14
x3
35
D、
4、已知某个含10个节点的树,其中9个节点的次为1,1,3,1,1,1,3,1,
3,另一个节点的次为
。
A、1
B、4
C、3
D、2
5、用标号法寻找网络最大流时,发生标号中断(没有增广链),这时若用V表示已标号的节点的集合,用V表示未标号的节点集合,则在网络中所有V→
V方向上的弧有
。(f为当前流,c为弧的容量)
A、fc
B、fc
C、fc
D、f0
三、已知线性规划问题(第一问8分,第二问7分,共15分)
mi
z2x1x22x3
x1x2x34
x1x2x36
x1
0
x2
0
x
无
3
约
束
(1)写出其对偶问题。
(2)其原问题的最优解为x15x20x31,根据对偶性质直接求解对偶问题的最优解。
四、(共20分,其中第1、3问各7分,第2问6分)某厂用两种原材料生产两种产品,已知数据见表1,根据该表列出的数学模型如下,加松弛变量,
f并用单纯形法求解得最终单纯形表见表2
表1:
产品I产品II
原材料A(kg件)2
3
原材料B(kg件)2
1
收入(元件)
3
2
资源限制149
表2:
CB
XB
b
x1x2x3
x4
2
x2
52011212
3
x1134101434
cjzj
001454
maxz3x12x2
2x13x2142x1x29
x1
0
x2
0
(1)求c1的变化范围以使最优解保持不变。(2)现在市场上原材料B的价格r