Chapter 17 – Linear Programming: Simplex Method
True / False
1. When a system of simultaneous equations has more variables than equations, there is a unique solution.
a.
True
b.
False
2. To determine a basic solution set of n−m, the variables equal to zero and solve the m linear constraint equations for the
remaining m variables.
a.
True
b.
False
3. A basic feasible solution satisfies the nonnegativity restriction.
a.
True
b.
False
4. Every extreme point of the graph of a two variable linear programming problem is a basic feasible solution.
a.
True
b.
False
5. In a simplex tableau, there is a variable associated with each column and both a constraint and a basic variable
associated with each row.
a.
True
b.
False
6. At each iteration of the simplex procedure, a new variable becomes basic and a currently basic variable becomes
nonbasic, preserving the same number of basic variables and improving the value of the objective function.
a.
True
b.
False
7. Coefficients in a nonbasic column in a simplex tableau indicate the amount of decrease in the current basic variables
when the value of the nonbasic variable is increased from 0 to 1.
a.
True
b.
False
8. If a variable is not in the basis, its value is 0.
a.
True
b.
False
9. The purpose of row operations is to create a unit column for the entering variable while maintaining unit columns for
Chapter 17 – Linear Programming: Simplex Method
the remaining basic variables.
a.
True
b.
False
10. We recognize infeasibility when one or more of the artificial variables do not remain in the solution at a positive
value.
a.
True
b.
False
11. Artificial variables are added for the purpose of obtaining an initial basic feasible solution.
a.
True
b.
False
12. A solution is optimal when all values in the cj − zj row of the simplex tableau are either zero or positive.
a.
True
b.
False
13. The variable to enter into the basis is the variable with the largest positive cj − zj value.
a.
True
b.
False
14. The variable to remove from the current basis is the variable with the smallest positive cj − zj value.
a.
True
b.
False
15. The coefficient of an artificial variable in the objective function is zero.
a.
True
b.
False
Multiple Choice
16. Algebraic methods such as the simplex method are used to solve
a.
nonlinear programming problems.
b.
any size linear programming problem.
c.
programming problems under uncertainty.
d.
graphical models.
17. The basic solution to a problem with three equations and four variables would assign a value of 0 to
Chapter 17 – Linear Programming: Simplex Method
a.
0 variables.
b.
1 variable.
c.
3 variables.
d.
7 variables.
18. A basic solution and a basic feasible solution
a.
are the same thing.
b.
differ in the number of variables allowed to be zero.
c.
describe interior points and exterior points, respectively.
d.
differ in their inclusion of nonnegativity restrictions.
19. When a set of simultaneous equations has more variables than constraints,
a.
it is a basic set.
b.
it is a feasible set.
c.
there is a unique solution.
d.
there are many solutions.
20. Which is not required for a problem to be in tableau form?
a.
Each constraint must be written as an equation.
b.
Each of the original decision variables must have a coefficient of 1 in one equation and 0 in every other
equation.
c.
There is exactly one basic variable in each constraint.
d.
The right-hand side of each constraint must be nonnegative.
21. Unit columns are used to identify
a.
the tableau.
b.
the c row.
c.
the b column.
d.
the basic variables.
22. The values in the cj − zj , or net evaluation, row indicate
a.
the value of the objective function.
b.
the decrease in value of the objective function that will result if one unit of the variable corresponding to the
jth column of the A matrix is brought into the basis.
c.
the net change in the value of the objective function that will result if one unit of the variable corresponding to
the jth column of the A matrix is brought into the basis.
d.
the values of the decision variables.
23. The purpose of the tableau form is to provide
Chapter 17 – Linear Programming: Simplex Method
a.
infeasible solution.
b.
optimal infeasible solution.
c.
initial basic feasible solution.
d.
degenerate solution.
24. Which of the following is not a step that is necessary to prepare a linear programming problem for solution using the
simplex method?
a.
formulate the problem.
b.
set up the standard form by adding slack and/or subtracting surplus variables.
c.
perform elementary row and column operations.
d.
set up the tableau form.
25. A minimization problem with four decision variables, two greater-than-or-equal-to constraints, and one equality
constraint will have
a.
2 surplus variables, 3 artificial variables, and 3 variables in the basis.
b.
4 surplus variables, 2 artificial variables, and 4 variables in the basis.
c.
3 surplus variables, 3 artificial variables, and 4 variables in the basis.
d.
2 surplus variables, 2 artificial variables, and 3 variables in the basis.
26. In the simplex method, a tableau is optimal only if all the cj − zj values are
a.
zero or negative.
b.
zero.
c.
negative and nonzero.
d.
positive and nonzero.
27. What coefficient is assigned to an artificial variable in the objective function?
a.
zero.
b.
one.
c.
a very large negative number.
d.
a very large positive number.
28. When there is a tie between two or more variables for removal from the simplex tableau,
a.
post-optimality analysis is required.
b.
their dual prices will be equal.
c.
converting the pivot element will break the tie.
d.
a condition of degeneracy is present.
29. An alternative optimal solution is indicated when in the simplex tableau
a.
a non-basic variable has a value of zero in the cj − zj row.
Chapter 17 – Linear Programming: Simplex Method
b.
a basic variable has a positive value in the cj − zj row.
c.
a basic variable has a value of zero in the cj − zj row.
d.
a non-basic variable has a positive value in the cj − zj row.
30. Infeasibility exists when one or more of the artificial variables
a.
remain in the final solution as a negative value.
b.
remain in the final solution as a positive value.
c.
have been removed from the basis.
d.
remain in the basis.
Subjective Short Answer
31. Write the following problem in tableau form. Which variables would be in the initial basic solution?
Min Z =
3x1 + 8x2
s.t.
x1 + x2 ≤ 200
x1 ≤ 80
x2 ≤ 60
Min Z
= 3x1 + 8x2 + Ma1 + Ma2
s.t.
x1 + x2 + a1 = 200
x2 + s2 + a2 = 60
The initial basis includes a1, a2, and s2.
32. Given the following initial simplex tableau
x1
x2
x3
s1
s2
s3
Basis
cB
5
8
12
0
0
0
s1
0
3
4
5
1
0
0
80
s2
0
9
15
20
0
1
0
250
s3
0
1
−1
2
0
0
0
20
zj
0
0
0
0
0
0
0
cj − zj
5
8
12
0
0
0
a.
What variables form the basis?
b.
What are the current values of the decision variables?
c.
What is the current value of the objective function?
d.
Which variable will be made positive next, and what will its value be?
Which variable that is currently positive will become 0?
f.
What value will the objective function have next?
Chapter 17 – Linear Programming: Simplex Method
33. Given the following simplex tableau
x1
x2
x3
s1
s2
Basis
cB
3
4
5
0
0
1/2
1
0
1/2
−1/2
6
0
0
1
−1/4
1
3
cj
cj − zj
a.
What variables form the basis?
b.
What are the current values of the decision variables?
c.
What is the current value of the objective function?
d.
Which variable will be made positive next, and what will its value be?
e.
Which variable that is currently positive will become 0?
f.
What value will the objective function have next?
c.
39
f.
51
34. A simplex tableau is shown below.
x1
x2
x3
s1
s2
s3
Basis
cB
3
5
8
0
0
0
s1
0
3
6
0
1
0
−9
126
s2
0
−5/2
−1/2
0
0
1
−9/2
45
x3
8
1/2
1/2
1
0
0
1/2
18
zj
4
4
8
0
0
4
144
cj − zj
−1
1
0
0
0
−4
a.
Do one more iteration of the simplex procedure.
b.
What is the current complete solution?
c.
Is this solution optimal? Why or why not?
a.
5
1
0
0
21
0
0
0
1
c.
0
f.
z = 120
Chapter 17 – Linear Programming: Simplex Method
35. A simplex table is shown below.
x1
x2
x3
s1
s2
s3
Basis
cB
5
4
8
0
0
0
s1
0
2/5
−3/5
0
1
−2/5
0
4
x3
8
4/5
4/5
1
0
1/5
0
8
s3
0
4/5
9/5
0
0
1/5
1
10
zj
32/5
32/5
8
0
8/5
0
64
cj − zj
−7/5
−12/5
0
0
−8/5
0
a.
What is the current complete solution?
b.
The 32/5 for z1 is composed of 0 + 8(4/5) + 0. Explain the meaning of this number.
c.
Explain the meaning of the −12/5 value for c 2 − z2.
x1 = 0, x2 = 0, x3 = 8, s1 = 4, s2 = 0, s3 = 10, Z = 64
order to make a unit of x1, profit of 32/5 will be given up.
Therefore it makes no sense to produce x2.
36. Solve the following problem by the simplex method.
Max
14x1 + 14.5x2 + 18x3
s.t.
x1 + 2x2 + 2.5x3 ≤ 50
x1 + x2 + 1.5x3 ≤ 30
x1 , x2 , x3 ≥ 0
30
−3/2
Chapter 17 – Linear Programming: Simplex Method
37. Solve the following problem by the simplex method.
Max
100x1 + 120x2 + 85x3
s.t.
3x1 + 1x2 + 6x3 ≤ 120
5x1 + 8x2 + 2x3 ≤ 160
x1 , x2 , x3 ≥ 0
14.5
Chapter 17 – Linear Programming: Simplex Method
38. Determine from a review of the following tableau whether the linear programming problem has multiple optimal
solutions.
Basis
cB
x1
x2
s1
s2
s3
s3
0
0
0
1
−1/5
8/6
6
x2
2
0
1
0
1/5
−3/5
1
x1
3
1
0
0
1/5
2/5
4
zj
3
2
0
0
0
14
cj −zj
0
0
0
−1
0
39. Write the following problem in tableau form. Which variables would be in the initial basis?
Max
x1 + 2x2
s.t.
3x1 + 4x2 ≤ 100
2x1 + 3.5x2 ≥ 60
2x1 − 1x2 = 4
x1 , x2 ≥ 0
x1 + 2x2 − Ma1 − Ma2
s.t.
3x1 + 4x2 + s1 = 100
2x1 + 3.5x2 − s2 + a1 = 60
2x1 − 1x2 + a2 = 50
x1 , x2 , s1 , s2 , a1 , a2 ≥ 0
The initial basis would include s1, a1, and a2 .
40. Write the following problem in tableau form. Which variables would be in the initial basic solution?
Min Z
= −3x1 + x2 + x3
97.745
124.38
9.3755
Chapter 17 – Linear Programming: Simplex Method
s.t.
x1 − 2x2 + x3 ≤ 11
−4 x1 + x2 + 2x3 ≥ 3
2x1 − x3 ≥ −1
x1 − 2x2 + x3 + s1 = 11
−2x1 + x3 + a2 = 1
41. Comment on the solution shown in this simplex tableau.
x1
x2
x3
s1
s2
Basis
cB
3
5
9
0
0
x3
9
1/3
2/3
1
1/3
0
40
s2
0
5/3
19/3
0
−1/3
1
100
zj
3
6
9
3
0
360
cj − zj
0
−1
0
−3
0
42. Comment on the solution shown in this simplex tableau.
x1
x2
x3
s1
s2
a1
Basis
cB
1
2
5
0
0
−M
a1
−M
−3
−1
0
−1
−2
1
4
x3
5
1
1/2
1
0
1/2
0
4
zj
5+3M
2.5+M
5
M
2.5+2M
−M
−4M+20
cj − zj
−4−3M
−.5−M
0
−M
−2.5−2M
0
43. Comment on the solution shown in this simplex tableau.
x1
x2
x3
s1
s2
Basis
cB
4
6
5
0
0
s1
0
3
0
−1
1
−1
26
x2
6
1
1
1
0
−1
10
zj
6
6
6
0
−6
60
cj − zj
−2
0
−1
0
6
44.
Joe Forrester, an operations analyst for a manufacturing company, developed the following LP formulation and wants to
create an initial simplex tableau.
Chapter 17 – Linear Programming: Simplex Method
Max 40xl + 30x2 + 50x3
s.t. 2xl + 3x2 + 4x3 < 200
x1 + 2x2 + 2x3 < 300
3xl + x2 + 5x3 < 500
s2
45.
Jackie Quinn developed the following LP formulation for a problem she is working on and now needs to create an initial
simplex tableau.
Min 75xl + 45x2
s.t. 3xl + 2x2 > 10
xl + 6x2 > 15
3
2
a2
1
6
46. A student in a Management Science class developed this initial tableau for a maximization problem and
now wants to perform row operations to obtain the next tableau and check for an optimal solution.
x1
x2
s1
s2
s3
Basis
cB
550
350
0
0
0
s1
0
2
2
1
0
0
2000
s2
0
2
1
0
1
0
1500
s3
0
1
2
0
0
1
3000
zj
0
0
0
0
0
0
cj – zj
550
350
0
0
0
Chapter 17 – Linear Programming: Simplex Method
x1
x2
s1
s2
s3
550
350
0
0
0
0
0
1
1
0
500
550
1
1/2
0
1/2
0
750
zj
550
275
0
275
0
412500
0
0
0
47.
A student in a Management Science class wants to perform row operations on this second tableau and complete the third
tableau to see if it is optimal. If it is optimal, what is the optimal answer?
x1
x2
s1
s2
s3
Basis
cB
550
350
0
0
0
s1
0
0
1
1
-1
0
500
x1
550
1
1/2
0
1/2
0
750
s3
0
0
3/2
0
-1/2
1
2250
zj
550
275
0
275
0
412500
cj – zj
0
75
0
–275
0
x1
x2
s1
s2
s3
Basis
cB
550
350
0
0
0
350
0
1
1
-1
0
500
x1
550
1
0
1
0
500
s3
0
0
0
-3/2
1
1
1500
zj
550
350
75
200
0
450000
cj – zj
0
0
0
48.
An operations research analyst for a communications company has the following LP problem and wants to solve it using
the simplex method.
Max 50x1 + 20x2
s.t. 2x1 + x2 < 200
x1 + x2 < 350
xl + 2x2 < 275
Chapter 17 – Linear Programming: Simplex Method
50
20
0
50
20
Basis
cB
0
0
0
x1
50
1
0
0
s2
0
0
1
0
s3
0
0
0
1
zj
0
0
5000
cj – zj
0
-5
0
0
49. The operations research analyst for a big manufacturing firm in Oregon developed the following variable definitions
for a LP maximization problem she was working on. The company was trying to determine how many consoles of each
model to produce next week given each console had to go through three production departments. She obtained the
following optimal simplex tableau for the problem and wanted to interpret its meaning.
Variable definitions:
xl = number of model 1 consoles produced
x2 = number of model 2 consoles produced
s1 = unused personnel hours in department 1
s2 = unused personnel hours in department 2
s3 = unused personnel hours in department 3
objective function = total profit on model 1 and model 2 consoles produced in the coming week
Optimal tableau
x1
x2
s1
s2
s3
Basis
cB
180
350
0
0
0
x1
180
1
0
1
0
-1
15
s2
0
0
0
-1
1
1
10
x2
350
0
1
0
0
1
20
zj
180
350
180
0
170
9700
cj – zj
0
0
–180
0
–170
Chapter 17 – Linear Programming: Simplex Method
50. A manager for a food company is putting together a buffet and she is trying to determine the best mix of
crab and steak to be served. Below are variable definitions she developed including vitamin, mineral and protein
requirements. Also included below is an optimal simplex tableau she obtained from her
computations. She is interested in interpreting what it means.
Variable definitions:
xl = amount of crab (oz) to be served per buffet batch
x2 = amount of steak (oz) to be served per buffet batch
s1 = vitamin A units provided in excess of requirements
s2 = mineral units provided in excess of requirements
s3 = protein units provided in excess of requirements
Optimal tableau
x1
x2
a1
a2
a3
s1
s2
s3
Basis
cB
-7
-4
-M
-M
-M
0
0
0
s2
0
0
0
4
-2
-1
-4
1
2
2500
x2
-4
0
1
1/50
0
-1/100
-1/50
0
1/100
20
x1
-7
1
0
-1/100
0
1/100
1/100
0
-1/100
15
zj
-7
-4
1/100
0
-3/100
1/100
0
170
–185
cj – zj
0
0
-M
-M
-M
-1/100
0
-3/100
Essay
51. What is the criterion for entering a new variable into the basis?
52.
A portion of a simplex tableau is
x1
Basis
cB
20
x2
25
.2
s2
0
3
zj
5
cj − zj
15
Give a complete explanation of the meaning of the z1 = 5 value as it relates to x2 and s2.
53. What is an artificial variable? Why is it necessary?
Chapter 17 – Linear Programming: Simplex Method
54. Describe and illustrate graphically the special cases that can occur in a linear programming solution. What clues for
these cases does the simplex procedure supply?
55. For each of the special cases of infeasibility, unboundedness, and alternate optimal solutions, tell what you would do
next with your linear programming model if the case occurred.
56. List the steps to get a problem formulation to tableau form.
57. What is degeneracy and what can be done in the simplex procedure to overcome the problem?