Exam
Name___________________________________
SHORT ANSWER. Write the word or phrase that best completes each statement or answers the question.
Solve the problem.
1)
Consider the following linear programming problem.
Maximize P = 5x + 6y subject to
2x + 3y 9
x + y 4
x 0, y
0
The associated final simplex tableau is as follows:
x y u v P
0 1 1 –2 0 1
1 0 –1 3 0 3
0 0 1 3 1 21
Find the optimal solution of the minimization problem.
1)
Provide an appropriate response.
2)
For the following initial simplex tableau, identify the basic and nonbasic variables. Find
the pivot element, the entering and exiting variables, and perform one pivot operation.
s1
s2
P
x y s1s2 P
3 5 1 0 0 15
4 1 0 1 0 4
–15 –10 0 0 1 0
2)
3)
State whether the optimal solution has been found, an additional pivot is required, or there
is no solution for the modified problem corresponding to the following simplex tableau:
x1x2x3s1a1s2a2a3P
0 1 0 0 0 2 1 1 0 5
1 0 –1 0 1 –1 0 1 0 2
0 0 –3 1 2 1 –1 0 0 8
0 0 –M + 3 0 0 4 M – 5 M + 2 120
3)
4)
Consider the linear programming problem:
Maximize P =3x1+7x2
subject to
x1+x2
6
2x1+x2
5
x1+3x2
15
x1, x2
0
(A) Introduce slack, surplus, and artificial variables and form the modified problem. (B)
Write the preliminary simplex tableau for the modified problem. (DO NOT SOLVE.)
4)
5)
State whether the optimal solution has been found, an additional pivot is required, or there
is no solution for the problem corresponding to the following simplex tableau:
x1x2x3s1s2s3P
1 0 0 3 1 1 0 8
0 1 0 –2 0 0 0 40
–2 0 1 2 1 0 0 5
1 0 0 4 2 0 1 54
5)
Solve the problem.
6)
Consider the following linear programming problem.
Maximize P = 3x + 2y + 5z subject to
x – 2z
10
x + y + 6z
80
x 0, y 0, z 0.
The associated final simplex tableau is as follows:
x y z u v P
1 0 –2 1 0 0 10
0 1 8 –1 1 0 70
0 0 5 1 2 1 170
Find the optimal solution of the minimization problem .
6)
7)
A stereo manufacturer makes three types of stereo systems, I, II, and III, with profits of $20,
$30, and $40, respectively. No more than 100 type–I systems can be made per day. Type–I
systems require 5 man–hours, and the corresponding numbers of man–hours for types II
and III are 10 and 15, respectively. If the manufacturer has available 2000 man–hours per
day, determine the number of units from each system that must be manufactured in order
to maximize profit. Compute the corresponding profit.
7)
8)
Big Round Cheese Company has on hand 45 pounds of Cheddar and 49 pounds of Brie
each day. It prepares two Christmas packagesthe “Holiday” box, which has 5 pounds of
Cheddar and 2 pounds of Brie, and the “Noel” box, which contains 2 pounds of Cheddar
and 7 pounds of Brie. Profit on each Holiday assortment is $6, profit on each Noel
assortment is $8.
(a) Give the optimal production schedule and the resulting maximum profit.
(b) How much excess Cheddar and excess Brie remain each day if this plan is followed?
8)
MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question.
Provide an appropriate response.
9)
Use the big M method to find the optimal solution to the problem.
Maximize P = 6x1+ 2x2
subject to x1+ 2x2 20
2x1+x2 16
x1+x2
9
x1, x2 0
9)
A)
max P = 46 at x1= 2 , x2= 7
B)
max P = 46 at x1= 7 , x2= 2
C)
max P = – 46 at x1= 2 , x2= 7
D)
max P = 46 at x1 , x2= 2
Convert the given i–system to an e–system using slack variables. Then construct a table of all basic solutions of the
e–system. For each basic solution, indicated whether or not it is feasible.
10)
x1+2x212
3x1+x29
x1, x2
0
10)
A)
x1+2x2+s1=12
3x1+x2+s2=9
x1x2s1s2
(A) 0 0 9 12
(B) 0 6 0 3
(C) 0 9 -6 0
(D) 12 0 0 -27
(E) 3 0 9 0
(F) 27
5
6
50 0
Feasible: (A), (B), (E), (F)
Not feasible: (C), (D)
B)
x1+2x2+s112
3x1+x2+s29
x1x2s1s2
(A) 0 0 12 9
(B) 0 6 0 3
(C) 0 9 -6 0
(D) 12 0 0 -27
(E) 3 0 9 0
(F) – 6
5– 9
50 0
Feasible: (A), (B), (E)
Not feasible: (C), (D), (F)
C)
x1+2x2+s1=12
3x1+x2+s2=9
x1x2s1s2
(A) 0 0 9 12
(B) 0 6 0 -3
(C) 0 9 6 0
(D) 12 0 0 27
(E) 3 0 -9 0
(F) 27
5
6
50 0
Feasible: (A), (C), (D), (F)
Not feasible: (B), (E)
D)
x1+2x2+s1=12
3x1+x2+s2=9
x1x2s1s2
(A) 0 0 12 9
(B) 0 6 0 3
(C) 0 9 -6 0
(D) 12 0 0 -27
(E) 3 0 9 0
(F) 6
5
27
50 0
Feasible: (A), (B), (E), (F)
Not feasible: (C), (D)
5
11)
Find x1 0 and x2
0 such that
2x1+ 5x211
3x1+ 3x215
and z = 4x1+x2 is maximized.
11)
A)
x1x2s1s2 z
2 5 1 0 0 11
3 3 0 1 0 15
4 1 0 0 1 0
B)
x1x2s1s2 z
2 5 1 0 0 15
3 3 0 1 0 11
4 1 0 0 1 0
C)
x1x2s1s2 z
2 5 1 0 0 11
3 3 0 1 0 15
–4–1 0 0 1 0
D)
x1x2s1s2 z
2 5 1 0 0 15
3 3 0 1 0 11
–4–1 0 0 1 0
12)
Write the modified problem for the following linear programming problem (DO NOT SOLVE):
Maximize P =9x1–4x2+x3
subject to
4x1–x2+2x3
3
–x1–7x2+9x3–4
x1–x2+2x3= 8
x1, x2, x3 0
12)
A)
Maximize P =9x1–4x2+x3+Ma1+Ma2
subject to
4x1–x2+2x3+s1= – 3
x1+7x2–9x3–s2+a1= – 4
x1–x2+2x3+a2= – 8
x1, x2, x3, s1, s2, a1, a2
0
B)
Maximize P =9x1–4x2+x3–Ma1–Ma2
subject to
4x1–x2+2x3+s1= – 3
x1+7x2–9x3–s2+a1= – 4
x1–x2+2x3+a2= – 8
x1, x2, x3, s1, s2, a1, a2
0
6
C)
Maximize P =9x1–4x2+x3+Ma1+Ma2
subject to
4x1–x2+2x3+s1= 3
x1+7x2–9x3–s2+a1= 4
x1–x2+2x3+a2= 8
x1, x2, x3, s1, s2, a1, a2
0
D)
Maximize P =9x1–4x2+x3–Ma1–Ma2
subject to
4x1–x2+2x3+s1= 3
x1+7x2–9x3–s2+a1= 4
x1–x2+2x3+a2= 8
x1, x2, x3, s1, s2, a1, a2
0
13)
Write the simplex tableau, label the columns and rows for the linear programming problem:
Maximize P = 4x1+x2 subject to
2x1+ 5x2 9
3x1+ 3x2 2
x1, x2 0
13)
A)
x1x2s1s2 P
2 5 1 0 0 2
3 3 0 1 0 9
4 1 0 0 1 0
B)
x1x2s1s2 P
2 5 1 0 0 9
3 3 0 1 0 2
4 1 0 0 1 0
C)
x1x2s1s2 P
2 5 1 0 0 9
3 3 0 1 0 2
–4–1 0 0 1 0
D)
x1x2s1s2 P
2 5 1 0 0 2
3 3 0 1 0 9
–4–1 0 0 1 0
14)
Write the basic solution for the following simplex tableau:
x1x2s1s2s3P
2 1 1
2 0 0 0 10
3 0 –1
2 1 0 0 40
–2 0 –1 0 1 0 4
14 0 6 0 0 1 120
14)
A)
x1= 0, x2= 10, s1= 1, s2= 40, s3= 4, P = 120
B)
x1= 0, x2= 10, s1= 0, s2= 40, s3= 4, P = – 120
C)
x1= 5, x2= 10, s1= 0, s2= 40, s3= 4, P = 120
D)
x1= 0, x2= 10, s1= 0, s2= 40, s3= 4, P = 120
Graph the system of inequalities.
15)
x1+x2
12
2x1+x2
20
x1, x2
0
15)
A)
B)
C)
D)
9
Write the e–system obtained via slack variables for the linear programming problem.
16)
Maximize P = 3x1+ 5x2
subject to: 4x1+ 3x2 30
x1+ 7x2 40
with: x1
0, x2
0
16)
A)
4x1+ 3x2=s1+ 30
x1+ 7x2=s2+ 40
B)
4x1+ 3x2+s1= 30
x1+ 7x2+s2= 40
C)
4x1+ 3x2+s1 30
x1+ 7x2+s2 40
D)
4x1+ 3x2+s1= 30
x1+ 7x2+s1= 40
Solve the problem.
17)
A linear programming problem has 35 decision variables x1, ..., x35 and50 problem constraints.
How many rows are there in the table of basic solutions of the associated e–system?
17)
A)
8.96 ×1013
B)
2.25 ×1023
C)
8.96 ×1023
D)
8.96 ×1025
18)
Formulate the following problem as a linear programming problem (DO NOT SOLVE):A shoe
company is introducing a new line of running shoes. The marketing division decides to promote
the line in a particular city. The promotion will consist of newspaper, radio, and television ads.
Each newspaper ad will cost $120, each television ad will cost $370, and each radio ad will cost
$210. The company wants to spend at most half their money on newspaper ads. The marketing
division believes that each newspaper ad will reach 4,700 men and 3,700 women, each television ad
will reach 7,600 men and 6,600 women, and each radio ad will reach 4,500 men and 5,500 women.
The promotion will be considered successful if it reaches at least 400,000 men and 200,000 women.
How should the company divide its money between the newspaper, television, and radio ads so as
to insure a successful promotion at a minimum cost? (Let x1 equal the number of newspaper ads,
x2 equal the number of television ads, and x3 equal the number of radio ads purchased in the
promotion.)
18)
A)
Minimize C =120x1+370x2+210x3
subject to
4,700x1+7,600x2+4,500x3 400,000
3,700x1+6,600x2+5,500x3 200,000
120x1–370x2–210x3 0
x1, x2, x3 0
10
B)
Minimize C = – 120x1–370x2+210x3
subject to
4,700x1+7,600x2+4,500x3 400,000
3,700x1+6,600x2+5,500x3 200,000
120x1–370x2–210x3 0
x1, x2, x3 0
C)
Minimize C = – 120x1–370x2+210x3
subject to
4,700x1+7,600x2+4,500x3 400,000
3,700x1+6,600x2+5,500x3 200,000
120x1–370x2–210x3 0
x1, x2, x3 0
D)
Maximize C =120x1+370x2+210x3
subject to
4,700x1+7,600x2+4,500x3 400,000
3,700x1+6,600x2+5,500x3 200,000
120x1–370x2–210x3 0
x1, x2, x3 0
Provide an appropriate response.
19)
Formulate the dual problem for the linear programming problem:
Minimize
C =3x1+x2
subject to
2x1+3x2 60
x1+4x2 40
x1, x2 0
19)
A)
Maximize P =60y1+40y2
subject to
2y1+y2
3
3y1+4y2
1
y1, y2 0
B)
Maximize P =3y1+y2
subject to
2y1+y2
3
3y1+4y2
1
y1, y2
0
C)
Maximize P =60y1+40y2
subject to
2y1+y2
3
3y1+4y2
1
y1, y2
0
D)
Maximize P =3y1+y2
subject to
2y1+y2
3
3y1+4y2
1
y1, y2 0
20)
Solve the linear programming problem by using the simplex method.
Minimize f = 5x+ 3y
subject to: 2x + 3y 9
2x +y 11
x
0, y
0
20)
A)
x =11
2, y = 0, f =55
2
B)
x = 5, y = 0, f = 25
C)
x = 0, y = 11, f = 33
D)
x = 5, y = 1, f = 28
21)
Maximize P=x1+ 2x2+ 3x3
subject to: x1+ 8x2+ 5x3
40
9x1+x2+ 7x3
50
with: x1
0, x2
0, x3 0
How many slack variables must be introduced to form the system of problem constraint equations?
21)
A)
0
B)
3
C)
2
D)
1
Convert the given i–system to an e–system using slack variables. Then construct a table of all basic solutions of the
e–system. For each basic solution, indicated whether or not it is feasible.
22)
9x1+7x263
x1, x2
0
22)
A)
9x1+7x2+s1=63
x1x2s1
(A) 0 0 63
(B) 0 7 0
(C) 9 0 0
Feasible: (A), (B), (C)
Not feasible: none
B)
9x1+7x2+s163
x1x2s1
(A) 0 0 63
(B) 0 9 0
(C) 7 0 0
Feasible: (B), (C)
Not feasible: (A)
C)
9x1+7x2+s1=63
x1x2s1
(A) 0 0 63
(B) 0 9 0
(C) 7 0 0
Feasible: (A), (B), (C)
Not feasible: none
D)
9x1+7x2+s1=63
x1x2s1
(A) 0 0 63
(B) 0-9 0
(C) -7 0 0
Feasible: (A)
Not feasible: (B), (C)
13
23)
Find x1 0 and x2 0 such that
x1+x272
3x1+x2189
and z = 2x1+x2 is maximized.
23)
A)
x1x2s1s2 z
1 1 1 0 0 72
3 1 0 1 0 189
2 1 0 0 1 0
B)
x1x2s1s2 z
1 1 1 0 0 189
3 1 0 1 0 72
2 1 0 0 1 0
C)
x1x2s1s2 z
1 1 1 0 0 189
3 1 0 1 0 72
–2–1 0 0 1 0
D)
x1x2s1s2 z
1 1 1 0 0 72
3 1 0 1 0 189
–2–1 0 0 1 0
Pivot once about the circled element in the simplex tableau, and read the solution from the result.
24)
24)
A)
x1= 48, s2= 16, z = 48; x2, x3, s1= 0
B)
x1= 24, s2= – 16, z = 24; x2, x3, s1= 0
C)
x1= 24, s2= – 16, z = – 24; x2, x3, s2= 0
D)
x1= 48, s2= – 16, z = – 48; x2, x3, s1= 0
25)
A linear programming problem has 4 decision variables, x1 to x4, and 8 problem constraints. How
many rows are there in the table of basic solutions of the associated e–system?
25)
A)
495
B)
11,880
C)
248
D)
24
26)
A catering company makes three kinds of Jello saladorange, strawberry, and lemon. It supplies
two outlet stores, Outlet A and Outlet B. The company can make up to 14 trays of orange, 20 trays
of strawberry, and 24 trays of lemon per day. Outlet A needs at least 20 trays of Jello per day and
Outlet B needs at least 10 trays of Jello per day. The transportation costs for shipping trays from the
company to the outlets are given in the chart below:
Shipping Charges
Type of Jello Outlet A Outlet B
Orange $4 $1
Strawberry $1 $4
Lemon $5 $5
Formulate a linear programming problem that will determine a shipping schedule that will
minimize the cost of transporting the Jello salads to fill the needs of the two outlets. DO NOT
SOLVE.
Let x1= number of trays of orange shipped to Outlet A
x2= number of trays of strawberry shipped to Outlet A
x3= number of trays of lemon shipped to Outlet A
x4= number of trays of orange shipped to Outlet B
x5= number of trays of strawberry shipped to Outlet B
x6= number of trays of lemon shipped to Outlet B
26)
A)
Minimize C = – 4x1–x2–5x3–x4+4x5–5x6
subject to
x1+x4
14
x2+x5
20
x3+x6
24
x1+x2+x3
20
x4+x5+x6
10
x1, x2, x3, x4, x5, x6
0
B)
Minimize C =4x1+x2+5x3+x4+4x5+5x6
subject to
x1+x4
14
x2+x5
20
x3+x6
24
x1+x2+x3
20
x4+x5+x6
10
x1, x2, x3, x4, x5, x6
0
C)
Minimize C = – 4x1–x2+5x3+x4+4x5–5x6
subject to
x1+x4
14
x2+x5
20
x3+x6
24
x1+x2+x3
20
x4+x5+x6
10
x1, x2, x3, x4, x5, x6
0
15
D)
Minimize C = – 4x1–x2+5x3+x4+4x5–5x6
subject to
x1+x4
14
x2+x5
20
x3+x6
24
x1+x2+x3
20
x4+x5+x6
10
x1, x2, x3, x4, x5, x6
0
27)
Solve the following linear programming problem using the simplex method:
Maximize P = 5x1+ 3x2
subject to
2x1+ 4x2 13
x1+ 2x2 6
x1, x2
0
27)
A)
Max P = 32.5 when x1= 6.5, x2= 0
B)
Max P = 18 when x1= 0, x2= 6
C)
Max P = 30 when x1= 6, x2= 0
D)
Maxi P = 9 when x1= 0, x2= 3
Write the e–system obtained via slack variables for the linear programming problem.
28)
Maximize P = 2x1+ 8x2
subject to: x1+ 5x2 15
9x1+ 8x2 25
with: x1
0, x2
0
28)
A)
x1+ 5x2+s1 15
9x1+ 8x2+s2 25
B)
x1+ 5x2+s1= 15
9x1+ 8x2+s2= 25
C)
x1+ 5x2=s1+ 15
9x1+ 8x2=s2+ 25
D)
x1+ 5x2+s1= 15
9x1+ 8x2+s1= 25
16
29)
Formulate the dual problem for the linear programming problem:
Minimize C =6x1+x2+5x3
subject to
8x1+x2 2
8x2+5x3 16
x1, x2, x3 0
29)
A)
Maximize P =2y1+16y2
subject to
8y1
6
y1+8y2
1
5y2
5
y1, y2 0
B)
Maximize P =16y1+2y2
subject to
8y1
6
y1+8y2
1
5y2
5
y1, y2 0
C)
Maximize P =2y1+16y2
subject to
8y1
6
y1+8y2
1
5y2
5
y1, y2
0
D)
Maximize P =2y1+16y2
subject to
8y1 6
y1+8y2 1
5y2
5
y1, y2 0
30)
Formulate the dual problem for the linear programming problem:
Minimize C =3x1+x2
subject to
2x1+3x2
60
x1+4x2
40
x1, x2
0
30)
A)
Maximize P =3y1+y2
subject to
2y1+y2 3
3y1+4y2 1
y1, y2 0
B)
Maximize P =60y1+40y2
subject to
2y1+y2 3
3y1+4y2 1
y1, y2 0
C)
Maximize P =60y1+40y2
subject to
2y1+y2 3
3y1+4y2 1
y1, y2 0
D)
Maximize P =3y1+y2
subject to
2y1+y2 3
3y1+4y2 1
y1, y2 0
Refer to the table of the six basic solutions to the e–system.
31)
The following chart depicts basic solutions to a system of linear inequalities. Which of the solutions
is NOT feasible?
x1x2s1s2
(A) 0 0 11 6
(B) 011
30–4
3
(C) 0 3 2 0
(D) 11
20 0 1
2
(E) 6 0 –1 0
(F) 4 1 0 0
31)
A)
(B)
B)
(A), (D), (E), (F)
C)
(B) and (E)
D)
(A), (B), (C)