一、 填空题（每小题4分，共20分）
minZ=5x1-2x2⎧⎪s.t-x1+2x2=-2⎪⎪1、设原LP问题为-x1+3x2≤4⎨⎪2x1-x2≥2⎪⎪x1无约束，x2≤0⎩
则它的标准形和对偶规划问题分别为：
和
________________________
。
________________________
minZ=-x1-5x2
⎧ x1- x2≥-2
⎪
2、用分枝定界法求整数规划⎪5x1+6x2 ≤30的解时，求得放松问题的解为x1＝
⎨
⎪ x1 ≤4⎪⎩x1,x2≥0且x2为整数18/11, x2 =40/11，则可将原问题分成如下两个子问题
与 求解。
3、右边的图的最小支撑树是
v11v3 23
3
5
v2
v5
4、下图是某网络图中的关于一可行流的增广路，其中每条弧上的数表示其容量和流量。
在其上可增的最大流量为 ；
①
在其上增流的方法可用图示为： 。
5
则其最优解为：Zmax=。
二、单项选择题（每小题2分，共10分） 1、线性规划的可行域的顶点是（ ）
A、可行解 B、正则解 C、 基本可行解 D、最优解
2、在保持最优解不变的前提下，基变量的系数ci的改变量∆ci可由不等式（ ）解得。 A、B-1b≥0 B、ξN-CBB-1N≤0 C、CN-CBB-1N≤0 D、CN-(CB-∆CB)B-1N≤0
3、在运输问题中如果总需求量小于总供应量，则求解时应（ ） A.虚设一些供应量； B.虚设一个供应点； C.根据需求短缺量，虚设多个需求点； D.虚设一个需求点。
4、下列规划问题用动态规划方法求解简便的是（ ）
maxZ=c1x1+c2x2+c3x3
A、
⎧x1+4x2+3x3=10⎪
s.t.⎨2x1-x2+5x3=6⎪⎩x≥0,y≥0
minf(x,y)=(x+2)2+3(y-1)2
B、
⎧x+4y=6
s.t.⎨
⎩x≥0,y≥0
minf(x,y)=4x+3(y-1)2
⎧2x-y≤3⎪
s.t.⎨x+4y=6⎪x≥0,y≥0⎩
5、下列关于树的论述错误地是（ ） A、任何一个图，都有支撑树；
B、图G是树的充分必要条件是其任意两点之间恰有一条链； C、连通图G是树的充分必要条件是G的边数=G的顶点数-1； D、若连通图G是的是无圈的，则连通图G是一个树图。
C、
⎧minf(x,y)=(x+2)2+3(y-1)2
D、⎪ s.. txy+4y
⎪x≥0,y≥0⎩
三、判断题（每小题2分，共10分）
（ ）1、对偶单纯形法与一般单纯形法的解题思路的区别是：它是从基本正则解出
发通过逐步迭代寻找既是基本正则解又是基本可行解的解=最优解；而单纯形法是从基
本可行解出发通过逐步迭代寻找既是基本可行解又是基本正则解的解=最优解 。 （ ）2、对LP
⎧minZ=CTX
问题的标准形⎪
AX=b⎨⎪X≥O⎩
用两阶段法求解时，若其的辅助LP问题
若其的辅助LP问题目标函数最优值等于零，则原问题无可行解，停止计算。
（ ）3、分枝定界法中的分枝起到有效缩减求最优解的范围作用；而定界则起到“巧妙”地删去不必要的一些点的分枝，使计算量大大减少作用。
（ ）4、一个可行流必需满足平衡条件，即所有的结点处流出量与流入量相等。
②5(4) ④
（ ）5、左图中可行流是最大流。
minZ=3x1-x3
①
⑥
③
8(6) ⑤
⎧ x1+x2+x3≤4四、求解线性规划：⎪（方法不限）（15分）
s.t.⎨2x1-x2+x3≤2⎪x,x,x≥0⎩123
求：(1)用最小元素法建立用最小元素法求一个初始可行调运方案；
(2)用位势法检验该初始调运方案是否是总运输费最少的最优方案；若是求最少总运输费，若不是，求一次调整新方案。（15分）
六、用Dijkstra法求右图V1 到 V8 点的最短路
线及最短路程。（10分）
8 V
七、某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。该厂在制定生产计划时有以下各级目标： p1：每周必须用足80小时的生产时间； p2：每周加班时数不超过10小时；
p3：每周销售窗帘布70000米，衣料布45000米；
p4：每周利润不低于是190000元
试建立这个问题的目标规划模型。
（10分）
一、 填空题（每小题4分，共20分）
minZ=5x1-2x2⎧⎪s.t-x1+2x2=-2⎪⎪1、设原LP问题为-x1+3x2≤4⎨⎪2x1-x2≥2⎪⎪x1无约束，x2≤0⎩
则它的标准形和对偶规划问题分别为：
和
________________________
。
________________________
minZ=-x1-5x2
⎧ x1- x2≥-2
⎪
2、用分枝定界法求整数规划⎪5x1+6x2 ≤30的解时，求得放松问题的解为x1＝
⎨
⎪ x1 ≤4⎪⎩x1,x2≥0且x2为整数18/11, x2 =40/11，则可将原问题分成如下两个子问题
与 求解。
3、右边的图的最小支撑树是
v11v3 23
3
5
v2
v5
4、下图是某网络图中的关于一可行流的增广路，其中每条弧上的数表示其容量和流量。
在其上可增的最大流量为 ；
①
在其上增流的方法可用图示为： 。
5
则其最优解为：Zmax=。
二、单项选择题（每小题2分，共10分） 1、线性规划的可行域的顶点是（ ）
A、可行解 B、正则解 C、 基本可行解 D、最优解
2、在保持最优解不变的前提下，基变量的系数ci的改变量∆ci可由不等式（ ）解得。 A、B-1b≥0 B、ξN-CBB-1N≤0 C、CN-CBB-1N≤0 D、CN-(CB-∆CB)B-1N≤0
3、在运输问题中如果总需求量小于总供应量，则求解时应（ ） A.虚设一些供应量； B.虚设一个供应点； C.根据需求短缺量，虚设多个需求点； D.虚设一个需求点。
4、下列规划问题用动态规划方法求解简便的是（ ）
maxZ=c1x1+c2x2+c3x3
A、
⎧x1+4x2+3x3=10⎪
s.t.⎨2x1-x2+5x3=6⎪⎩x≥0,y≥0
minf(x,y)=(x+2)2+3(y-1)2
B、
⎧x+4y=6
s.t.⎨
⎩x≥0,y≥0
minf(x,y)=4x+3(y-1)2
⎧2x-y≤3⎪
s.t.⎨x+4y=6⎪x≥0,y≥0⎩
5、下列关于树的论述错误地是（ ） A、任何一个图，都有支撑树；
B、图G是树的充分必要条件是其任意两点之间恰有一条链； C、连通图G是树的充分必要条件是G的边数=G的顶点数-1； D、若连通图G是的是无圈的，则连通图G是一个树图。
C、
⎧minf(x,y)=(x+2)2+3(y-1)2
D、⎪ s.. txy+4y
⎪x≥0,y≥0⎩
三、判断题（每小题2分，共10分）
（ ）1、对偶单纯形法与一般单纯形法的解题思路的区别是：它是从基本正则解出
发通过逐步迭代寻找既是基本正则解又是基本可行解的解=最优解；而单纯形法是从基
本可行解出发通过逐步迭代寻找既是基本可行解又是基本正则解的解=最优解 。 （ ）2、对LP
⎧minZ=CTX
问题的标准形⎪
AX=b⎨⎪X≥O⎩
用两阶段法求解时，若其的辅助LP问题
若其的辅助LP问题目标函数最优值等于零，则原问题无可行解，停止计算。
（ ）3、分枝定界法中的分枝起到有效缩减求最优解的范围作用；而定界则起到“巧妙”地删去不必要的一些点的分枝，使计算量大大减少作用。
（ ）4、一个可行流必需满足平衡条件，即所有的结点处流出量与流入量相等。
②5(4) ④
（ ）5、左图中可行流是最大流。
minZ=3x1-x3
①
⑥
③
8(6) ⑤
⎧ x1+x2+x3≤4四、求解线性规划：⎪（方法不限）（15分）
s.t.⎨2x1-x2+x3≤2⎪x,x,x≥0⎩123
求：(1)用最小元素法建立用最小元素法求一个初始可行调运方案；
(2)用位势法检验该初始调运方案是否是总运输费最少的最优方案；若是求最少总运输费，若不是，求一次调整新方案。（15分）
六、用Dijkstra法求右图V1 到 V8 点的最短路
线及最短路程。（10分）
8 V
七、某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。该厂在制定生产计划时有以下各级目标： p1：每周必须用足80小时的生产时间； p2：每周加班时数不超过10小时；
p3：每周销售窗帘布70000米，衣料布45000米；
p4：每周利润不低于是190000元
试建立这个问题的目标规划模型。
（10分）