四级考试评分标准-工作失误检讨书

大连大学20102011学年第一学期期中考试卷

姓 名

学 号

学 院

专 业

班 级
题号
1
得分
2

1

2

3

4

考试科目： 运 筹 学
(考试时间
页）

一 二
90分钟
)
（共4
总得分
密
一、用图解法求解（10分）
给定下述线性规划问题：

maxzx
1
2x
2


4x
1< br>3x
2
3


x
1
x
23


x,x0

12
画出其可行域并找出其最优解。
解:可行域:



适用专业

工程管理
适用年级
封
08
考试形式
闭卷
送卷单位

任课教师

总印数

教研室主任


最优解为(3,0),
z3


二、模型转换（10分）
写出下列线性规划问题的对偶问题

minz

c
ij
x
ij

i1j 1
23
线


x
11
x
12x
13
x
14
a
1

xxxx a
2

21222324

x
11
x
2 1
b
1

x
12
x
22
b
2




x
13
x
23
b
3

x
14
x
24
b
4


一切x
ij
0

解：
max wa
1
u
1
a
2
u
2
b
1
v
1
b
2
v
2
b
3
v
3
b
4
v
4

u
1
v
1< br>c
11


u
1
v
2
c12


u
1
v
3
c
13

u
1
v
4
0


u
2< br>v
1
c
21




u
2
v
2
c
22

u
2
v
3
c
23


u
2
v
40



u
1
,u
2
,v
1
,v
2
,v
3
,v
4
无符号限制
三、计 算题（每小题20分，共80分）
1. 用单纯形法求解下列线性规划问题(列出计算过程)。

minz3x
1
5x
2

x
1
8

2x12

2


3x4x36
2

1


x
1
,x
2
0

5x
2

0x3
0x
4
0x
5
MaxW3x
1
< br>x
3
8x
1



x
4< br>12
解：
标准化：

2x
2


4x
2

x
5
36

3x
1< br>

,x
2

,x
3
,x
4
,x
5
0

x
1
变量变量，第二步标准化)

列单纯形表计算：
基 C
B

-3 -5 0 0 0 b
(标准化可分两段，第一步把决策

X
1

X
3

X
4

X
5

0
0
0
c
j
z
j

X
2

0
[-2]
-4
-5
X
3

1
0
0
0
X
4

0
1
0
0
X
5

0
0
1
0
8
12
36

-1
0
-3
-3
最优解X
*
=（3，5，0，0,0）
T
，最优值W
*
=3 4,故Z=-34

2. 用单纯形法中两阶 段法求解下述线性规划问题(列出计算过程)。(注意步骤，
区分人工变量与松驰变量)
minz4x
1
x
2


3x
1< br>x
2
3

4x3xx6

23


1


x
1
2x
2
x4
4


x
i
0,i1,2,3,4
解 ：1)标准化；
maxz
'
4x
1
x
2


3x
1
x
2
3

4x3xx 6

123


x
1
2x
2
 x
4
4


x
i
0,i1,2,3,4(1)
(2)

２）在上约束方程组(1)、（2）中加入人工变量，列出第一阶段线性规划问题
将正文中的问题化成标准型：
minwx
5
x
6
< br>
3x
1
x
2
x
5
3
4x3xxx6

1236


x2xx424

1


x
i
0,i1,2,3,4 ,5,6
3)列出上述线性规划问题的初始单纯形表，并求解

基 C
B

0
X
1

0
X
2

1
3
2
4
13
[53]
0
X
3

0
-1
0
-1
0
-1
0
X
4

0
0
1
0
0
0
-1
X
5

1
0
0
0
13
-43
-1
X
6

0
1
0
0
0
1
b
X
5

X
6

X
4

-1
-1
0
c
j
z
j

[3]
4
1
7
1
0
3
6
4

1
2
X
1

X
6

0
-1

X
4
0
c
j
z
j

0
0
1
0
0
0
53
53
0
1
0
0
0
1
15
-35
1
0
1
0
0
0
1
0
-13
-73
0
0
3

X
1

X
2

X
4

0
0
0
c
j
z
j

35 -15 35
-45 35 65
1
-1
-1
-1
1

4)因为第一阶段目标函数值为0，做去掉人工变量，写出第二阶段目标函数为
maxz4x
1
x
2
0x
3
0x
4< br>，继续用单纯形法求解
基 C
B

-4
X
1

-1
X
2

0
1
0
0
0
1
0
0

0
X
3

15
-35
[1]
15
0
0
1
0
17

5
0
X
4

0
0
1
0
-15
35
1
-15
b
X
1

X
2

X
4

-4
-1
0
c
j
z
j

1
0
0
0
1
0
0
0
29
55
35
65
1

25
95
1

X
1

X
2

X
3

-4
-1
0
c
j
z
j


故有唯一最优解
X(,,1,0,0,0),Z


3. 用对偶单纯形法求解下述线性规划问题(列出计算过程)。(此问题不是加人工
变量，而 是根据对偶理论，在保持对偶问题为可行解的基础上，通过迭代，使原
问题也达到可行解，即得到了目标 函数的最优解。)


minz4x
1
12x
2
18x
3


x
1
3x
3
3



2x
2
2x
3
5


x,x,x0

123
解：先将问题改写为：
max w4x
1
12x
2
18x
3
0x
40x
5


x
1
3x
3
x4
3


2x
2
2x
3
x5
5


x0,i1,2,3,4,5

i约束条件两端乘“-1”得：
maxw4x
1
12x
2
18x
3
0x
4
0x
5


x< br>1
3x
3
x
4
3


2 x
2
2x
3
x
5
5


x0,i1,2,3,4,5

i
c
j


基
-4 -12 -18 0 0
C
B
0
0

0
b

-3
-5

-3
52

1
32

x
1

x
2
0

x
3

x
4
1
0
0
1
0
0

x
5
0
1
0
0

x
4
x
5



-1
0
-4
-1
0
-4
13
-3
-2
-18
[-3]
1
-6
1
0
0
[-2]
-12
0
1
0
0
c
j
z
j
x
4
x
2



-12

-18
-12

-12
-6
0
-12
-6
c
j
z
j
x
3
x
2



-13
13
-2
-13 1
-2 0
c
j
z
j
X=(0 32 1 0 0), minz=36

4. 已知某运输问题的产销数量表与单位运价表如表4-1，用表上作业法求最优
解(列出计算过程)。
表4-1
销地

产地
B
1

B
2

B
3

销量

解：1.|最小元素法的初始方案
A
1
A
2
A
3
A
4
产量
2 9 10 7
1 3 4 2
8 4 2 5
3 8 4 6
9
5
7

销地

产地
B
1

B
2

B
3

销量

位势法检验：
A
1
A
2
A
3
A
4
产量
5 4
3 2
3 4
3 8 4 6
9
5
7

产
销地
A1
A2
A3

地 B1 B2 B3 B4

（-4） 9
1
（7）
1
3 7 5
0 （-1） （2） 2
4
4
2
2
（3） 0
2

（注：括弧中的数位检验数，下同）

闭回路法调整（调整结果与Vogel法的初始方案一致）：
产地 销地
A1
A2
A3
销量


2. Vogel法的初始方案：
B1
3


3
B2
5

3
8
B3


4
4
B4
1
5

6
产量
9
5
7

产地 销地
A1
A2
A3
销量

位势法检验：
B1
3


3
B2
5

3
8
B3


4
4
B4
1
5

6
产量
9
5
7

产
销地
A1
A2
A3


闭回路法调整：
地 B1 B2 B3 B4

2
（4）
9 （0） 7 1
-4 （-1） （2） 2
2
6
（11） 4
1 8
（3） -4
6

产地 销地 B1 B2 B3 B4 产量

A1
A2
A3
销量

位势法检验：
产
销地
A1
A2
A3


2
（4）
地 B1
3


3

5
3
8


4
4
6
0

6
9
5
7

B2 B3 B4

（1） （4） 7
3 （3） 2
2
5
1
-4
（10） 4
1 7
（2） -3
6

所有检验数都大于0，所以此时为最优解。


最终方案（最优调拨方案）为：

销地

产地
B
1

B
2

B
3

销量
3 6
5 0
3 4
3 8 4 6

x
11
3
，
x
14< br>6
，
x
22
5
，
x
24
0
（或
x
12
0
），
x
32
3
，
x
33
4
，
z83
。
A
1
A
2
A
3
A
4
产量
9
5
7

大连大学20102011学年第一学期期中考试卷

姓 名

学 号

学 院

专 业

班 级
题号
1
得分
2

1

2

3

4

考试科目： 运 筹 学
(考试时间
页）

一 二
90分钟
)
（共4
总得分
密
一、用图解法求解（10分）
给定下述线性规划问题：

maxzx
1
2x
2


4x
1< br>3x
2
3


x
1
x
23


x,x0

12
画出其可行域并找出其最优解。
解:可行域:



适用专业

工程管理
适用年级
封
08
考试形式
闭卷
送卷单位

任课教师

总印数

教研室主任


最优解为(3,0),
z3


二、模型转换（10分）
写出下列线性规划问题的对偶问题

minz

c
ij
x
ij

i1j 1
23
线


x
11
x
12x
13
x
14
a
1

xxxx a
2

21222324

x
11
x
2 1
b
1

x
12
x
22
b
2




x
13
x
23
b
3

x
14
x
24
b
4


一切x
ij
0

解：
max wa
1
u
1
a
2
u
2
b
1
v
1
b
2
v
2
b
3
v
3
b
4
v
4

u
1
v
1< br>c
11


u
1
v
2
c12


u
1
v
3
c
13

u
1
v
4
0


u
2< br>v
1
c
21




u
2
v
2
c
22

u
2
v
3
c
23


u
2
v
40



u
1
,u
2
,v
1
,v
2
,v
3
,v
4
无符号限制
三、计 算题（每小题20分，共80分）
1. 用单纯形法求解下列线性规划问题(列出计算过程)。

minz3x
1
5x
2

x
1
8

2x12

2


3x4x36
2

1


x
1
,x
2
0

5x
2

0x3
0x
4
0x
5
MaxW3x
1
< br>x
3
8x
1



x
4< br>12
解：
标准化：

2x
2


4x
2

x
5
36

3x
1< br>

,x
2

,x
3
,x
4
,x
5
0

x
1
变量变量，第二步标准化)

列单纯形表计算：
基 C
B

-3 -5 0 0 0 b
(标准化可分两段，第一步把决策

X
1

X
3

X
4

X
5

0
0
0
c
j
z
j

X
2

0
[-2]
-4
-5
X
3

1
0
0
0
X
4

0
1
0
0
X
5

0
0
1
0
8
12
36

-1
0
-3
-3
最优解X
*
=（3，5，0，0,0）
T
，最优值W
*
=3 4,故Z=-34

2. 用单纯形法中两阶 段法求解下述线性规划问题(列出计算过程)。(注意步骤，
区分人工变量与松驰变量)
minz4x
1
x
2


3x
1< br>x
2
3

4x3xx6

23


1


x
1
2x
2
x4
4


x
i
0,i1,2,3,4
解 ：1)标准化；
maxz
'
4x
1
x
2


3x
1
x
2
3

4x3xx 6

123


x
1
2x
2
 x
4
4


x
i
0,i1,2,3,4(1)
(2)

２）在上约束方程组(1)、（2）中加入人工变量，列出第一阶段线性规划问题
将正文中的问题化成标准型：
minwx
5
x
6
< br>
3x
1
x
2
x
5
3
4x3xxx6

1236


x2xx424

1


x
i
0,i1,2,3,4 ,5,6
3)列出上述线性规划问题的初始单纯形表，并求解

基 C
B

0
X
1

0
X
2

1
3
2
4
13
[53]
0
X
3

0
-1
0
-1
0
-1
0
X
4

0
0
1
0
0
0
-1
X
5

1
0
0
0
13
-43
-1
X
6

0
1
0
0
0
1
b
X
5

X
6

X
4

-1
-1
0
c
j
z
j

[3]
4
1
7
1
0
3
6
4

1
2
X
1

X
6

0
-1

X
4
0
c
j
z
j

0
0
1
0
0
0
53
53
0
1
0
0
0
1
15
-35
1
0
1
0
0
0
1
0
-13
-73
0
0
3

X
1

X
2

X
4

0
0
0
c
j
z
j

35 -15 35
-45 35 65
1
-1
-1
-1
1

4)因为第一阶段目标函数值为0，做去掉人工变量，写出第二阶段目标函数为
maxz4x
1
x
2
0x
3
0x
4< br>，继续用单纯形法求解
基 C
B

-4
X
1

-1
X
2

0
1
0
0
0
1
0
0

0
X
3

15
-35
[1]
15
0
0
1
0
17

5
0
X
4

0
0
1
0
-15
35
1
-15
b
X
1

X
2

X
4

-4
-1
0
c
j
z
j

1
0
0
0
1
0
0
0
29
55
35
65
1

25
95
1

X
1

X
2

X
3

-4
-1
0
c
j
z
j


故有唯一最优解
X(,,1,0,0,0),Z


3. 用对偶单纯形法求解下述线性规划问题(列出计算过程)。(此问题不是加人工
变量，而 是根据对偶理论，在保持对偶问题为可行解的基础上，通过迭代，使原
问题也达到可行解，即得到了目标 函数的最优解。)


minz4x
1
12x
2
18x
3


x
1
3x
3
3



2x
2
2x
3
5


x,x,x0

123
解：先将问题改写为：
max w4x
1
12x
2
18x
3
0x
40x
5


x
1
3x
3
x4
3


2x
2
2x
3
x5
5


x0,i1,2,3,4,5

i约束条件两端乘“-1”得：
maxw4x
1
12x
2
18x
3
0x
4
0x
5


x< br>1
3x
3
x
4
3


2 x
2
2x
3
x
5
5


x0,i1,2,3,4,5

i
c
j


基
-4 -12 -18 0 0
C
B
0
0

0
b

-3
-5

-3
52

1
32

x
1

x
2
0

x
3

x
4
1
0
0
1
0
0

x
5
0
1
0
0

x
4
x
5



-1
0
-4
-1
0
-4
13
-3
-2
-18
[-3]
1
-6
1
0
0
[-2]
-12
0
1
0
0
c
j
z
j
x
4
x
2



-12

-18
-12

-12
-6
0
-12
-6
c
j
z
j
x
3
x
2



-13
13
-2
-13 1
-2 0
c
j
z
j
X=(0 32 1 0 0), minz=36

4. 已知某运输问题的产销数量表与单位运价表如表4-1，用表上作业法求最优
解(列出计算过程)。
表4-1
销地

产地
B
1

B
2

B
3

销量

解：1.|最小元素法的初始方案
A
1
A
2
A
3
A
4
产量
2 9 10 7
1 3 4 2
8 4 2 5
3 8 4 6
9
5
7

销地

产地
B
1

B
2

B
3

销量

位势法检验：
A
1
A
2
A
3
A
4
产量
5 4
3 2
3 4
3 8 4 6
9
5
7

产
销地
A1
A2
A3

地 B1 B2 B3 B4

（-4） 9
1
（7）
1
3 7 5
0 （-1） （2） 2
4
4
2
2
（3） 0
2

（注：括弧中的数位检验数，下同）

闭回路法调整（调整结果与Vogel法的初始方案一致）：
产地 销地
A1
A2
A3
销量


2. Vogel法的初始方案：
B1
3


3
B2
5

3
8
B3


4
4
B4
1
5

6
产量
9
5
7

产地 销地
A1
A2
A3
销量

位势法检验：
B1
3


3
B2
5

3
8
B3


4
4
B4
1
5

6
产量
9
5
7

产
销地
A1
A2
A3


闭回路法调整：
地 B1 B2 B3 B4

2
（4）
9 （0） 7 1
-4 （-1） （2） 2
2
6
（11） 4
1 8
（3） -4
6

产地 销地 B1 B2 B3 B4 产量

A1
A2
A3
销量

位势法检验：
产
销地
A1
A2
A3


2
（4）
地 B1
3


3

5
3
8


4
4
6
0

6
9
5
7

B2 B3 B4

（1） （4） 7
3 （3） 2
2
5
1
-4
（10） 4
1 7
（2） -3
6

所有检验数都大于0，所以此时为最优解。


最终方案（最优调拨方案）为：

销地

产地
B
1

B
2

B
3

销量
3 6
5 0
3 4
3 8 4 6

x
11
3
，
x
14< br>6
，
x
22
5
，
x
24
0
（或
x
12
0
），
x
32
3
，
x
33
4
，
z83
。
A
1
A
2
A
3
A
4
产量
9
5
7