Complete the Multiple Choice
1. Consider a minimal spanning tree problem in which pipe must be laid to connect sprinklers on a golf course. When represented with a network,
a. the pipes are the arcs and the sprinklers are the nodes.
b. the pipes are the nodes and the sprinklers are the arcs.
c. the pipes and the sprinklers are the tree.
d. each sprinkler must be connected to every other sprinkler.
2. Which would be the correct transformation for the constraints defined as:
ax1+bx2 ≥c; x1≥-d; x2≥0.
a. a(x1+d)+bx2-x3+ x4=c; xj≥0 (j=1,..,4)
b. ax1+bx2-x3+x4=c; -x1+x5 =d; xj≥0 (j=1,..,5)
c. ax1+bx2-x3+x4=c; x1-x5+x6=-d; xj≥0 (j=1,..,6)
d. ax1+bx2+x3-x4=c; -x1+x5=-d; xj≥0 (j=1,..,5)
3. The shortest-route algorithm has assigned the following permanent labels to six nodes, where the label [a, b] indicates the minimum distance a up to the node k from node b.
Node Label
1 [0,S]
2 [15,1]
3 [12,1]
4 [20,3]
5 [8,1]
6 [32,4]
What is the shortest path from the source to node 6?
a. 1, 3, 4, 6
b. 1, 6
c. 1, 2, 5, 6
d. 1, 5, 6
4. The basic solution to a problem with four equations and five variables would assign a value of 0 to
a. 4 variables.
b. 0 variables.
c. 1 variable.
d. 7 variables.
5. Given a maximization problem with the following intermediate simplex tableau:
Which statement is true?
|
Basic
Variable
|
Eq.
|
Coefficient of
|
RHS
|
|
z
|
x1
|
x2
|
x3
|
x4
|
x5
|
|
z
|
0
|
1
|
0
|
0
|
-4
|
-3
|
0
|
20
|
|
x1
|
1
|
0
|
1
|
0
|
-1
|
3
|
0
|
4
|
|
x5
|
2
|
0
|
0
|
0
|
-5
|
1
|
1
|
14
|
|
x2
|
3
|
0
|
0
|
1
|
0
|
7
|
0
|
2
|
a. The problem may have an unbounded feasible region.
b. x3 enters to the basis and x5 leaves the basis.
c. x4 enters to the basis and x2 leaves the basis.
d. It cannot be determined since there is missed information