College Mathematics: Learning Worksheets Chapter 6
165
Name ________________________________ Date ______________ Class ____________
Goal: To solve problems using the simplex method
1. Consider the following linear programming problem:
Maximize: 12
12 10Px x
subject to:
12
12
12
53 15
4
0, 0
xx
xx
xx
+≤
+≤
≥≥
a) Is the linear programming problem in standard form?
b) Find the feasible region by graphing.
The feasible region is shaded above.
Section 6-1 The Table Method:
An Introduction to the Simplex Method
Procedure: Simplex method to solve linear programming problems
Step 1: Find the feasible region by graphing.
Step 2: Find all intersection points, whether the points are in the feasible region or not.
Step 3: Using slack variables, convert the system into a system of equations.
Step 4: Fill in a table giving the basic solutions and intersection points (from step 2) and
College Mathematics: Learning Worksheets Chapter 6
166
c) Find all intersection points of lines in the graph, and state whether the points are in
the feasible region.
22
22
d) Using slack variables, convert the system of inequalities into a system of
equations.
53 15
xxs
++ =
⎧
e) Fill in the following table:
Intersection Is point in
Basic Solutions Point Feasible
(from part c) Region?
1
x
2
x
1
s 2
s
0 0 15 4 (0, 0) Yes
3 0 0 1 (3, 0) Yes
2 5
2 0 0
22
f) Find the maximum value of P (evaluate P only at points that are in the feasible
region).
Point of Intersection 12
12 10Px x
(0, 0) 12(0) 10(0) 0P
22
22
22
167
2. Consider the following linear programming problem:
Maximize: 12
80 30Px x
subject to:
12
12
12
6
39
0, 0
xx
xx
xx
a) Is the linear programming problem in standard form?
b) Find the feasible region by graphing.
c) Find all intersection points of lines in the graph, and state whether the points are in
the feasible region.
22
22
d) Using slack variables, convert the system of inequalities into a system of
equations.
6
xx s
College Mathematics: Learning Worksheets Chapter 6
168
e) Fill in the following table:
Intersection Is point in
Basic Solutions Point Feasible
(from part c) Region?
1
x
2
x
1
s 2
s
0 9 –3 0 (0, 9) No
3 0 3 0 (3, 0) Yes
2 9
2 0 0
22
f) Find the maximum value of P (evaluate P only at points that are in the feasible
region).
Point of Intersection 12
80 30Px x
39
22
(, ) 39
22
80( ) 30( ) 255P
College Mathematics: Learning Worksheets Chapter 6
169
Name ________________________________ Date ______________ Class ____________
Goal: To solve maximum problems using the simplex method
1. Consider the following linear programming problem:
Maximize: 12
12 10Px x
subject to:
12
12
12
53 15
4
0, 0
xx
xx
xx
+≤
+≤
≥≥
a) Using slack variables, convert the system of inequalities into a system
of equations.
b) Write the initial simplex tableau for the linear programming problem.
Section 6-2 The Simplex Method: Maximization
with Problem Constraints of the Form ≤
Procedure: Selecting the Pivot Element
Step 1 Locate the most negative indicator in the bottom row of the tableau to the left
of the P column (the negative number with the largest absolute value). The column
containing this element is the pivot column.
Step 2 Divide each positive element in the pivot column above the line into the
corresponding element in the last column. The pivot row is the row corresponding to
Procedure: Performing a Pivot Operation
A pivot operation, or pivoting, consists of performing row operations as follows:
Step 1 Multiply the pivot row by the reciprocal of the pivot element to transform the
pivot element into a 1.
College Mathematics: Learning Worksheets Chapter 6
170
c) Choose the first pivot element and “clear” the pivot column using this
pivot element.
d) Is there another pivot element? If so, continue until there are no more
pivot elements.
e) State the solution to the linear programming problem in sentence form.
a)
12 2
53 15
4
xxs
xx s
b)–d)
5310015
110104
–12 –10 0 0 1 0
31
–12 –10 0 0 1 0
31
1003
31
55
1003
55 2
10 0
22
171
2. Consider the following linear programming problem:
Maximize: 12
80 30Px x
subject to: 12
12
12
6
39
0, 0
xx
xx
xx
a) Using slack variables, convert the system of inequalities into a system of equations.
b) Write the initial simplex tableau for the linear programming problem.
c) Choose the first pivot element and “clear” the pivot column using this
pivot element.
d) Is there another pivot element? If so, continue until there are no more
pivot elements.
e) State the solution to the linear programming problem in sentence form.
Solution:
a)
12 2
6
39
xx s
xx s
b)–d)
310109
–80 –30 0 0 1 0
111006
College Mathematics: Learning Worksheets Chapter 6
172
21
33
0 – 0 1 240
39
1
01 0
22 2
01 0
0 0 5 25 1 255
22
3. A dietician needs to plan a diet for a patient using two different food combinations to meet
the patient’s needs. Each container of Food A contains 1 units of Additive #1 and 1 units of
Additive #2. Each container of Food B contains 1 units of Additive #1 and 2 units of
Additive #2. The patient needs at most 5 units of Additive #1 and at most 6 units of
Additive #2. If each container of Food A has 12 units of calcium and Food B has 8 units of
calcium, how many containers of each food should be used to maximize the amount of
calcium?
Let
1
x
represent Food A and 2
x
represent Food B. Based on the above information,
12
12
12
5
,0
xx
xx
+≤
⎧
⎪+≤
⎪≥
⎩
Adding the slack variables, we will have the following equations:
121
12 2
12
5
0, 0
xx s
xx
++ =
⎧
⎪++=
⎪≥≥
⎩
College Mathematics: Learning Worksheets Chapter 6
173
12
12 8 0xxP
Solving the initial simplex tableau:
111005
⎡⎤
⎣⎦
11 100 5
⎡⎤
4. Farmer Phil has 640 acres to plant in corn and soybeans. Each acre of corn requires 45
labor-hours and each acre costs $100 in seed and fertilizer. Each acre of soybeans requires
60 labor hours and each acre costs $80 in seed and fertilizer. Phil estimates that he has
36,000 hours of labor and $60,000 capital to spend. Phil estimates that each acre planted in
corn will yield a profit of $120 and each acre planted in soybeans will yield a profit of $100.
Under these conditions, how many acres of corn and how many acres of soybeans should
Phil plant to maximize his profit?
Let 1
x
represent acres of corn and 2
x
represent acres of soybeans. Based on the above
12
12
640
45 60 36,000 .
xx
xx
College Mathematics: Learning Worksheets Chapter 6
174
Adding the slack variables, we will have the following equations:
121
640
xx s
Solving the initial simplex tableau:
⎢
1 1 1 0 0 0 640
1 11000 640
⎢
⎢
⎢
⎡
⎤
⎡⎤
⎢
⎥
⎢⎥
⎣
11
6
0 4 0 0 1 72,000
⎢⎥
−
41
5 100
0 0 0 0 600
⎢⎥
⎢⎥
3
4
0 0 120 1 0 4200
⎢⎥
⎢⎥
−
College Mathematics: Learning Worksheets Chapter 6
175
Name ________________________________ Date ______________ Class ____________
Goal: To solve minimization problems that are in the form of a dual problem
In Problems 1–6, find the transpose of each matrix.
6
9
⎡⎤
⎢⎥
⎢⎥
⎣⎦
T
⎢
3
1
6
2
T
⎡
⎤
⎢
⎥
⎢
⎥
⎢
⎢
⎢
⎥
⎣
⎦
Section 6-3 The Dual Problems: Minimization
with Problem Constraints of the Form ≥
Formation of the Dual Problem:
Given a minimization problem with > problem constraints,
Step 1: Use the coefficients and constants in the problem constraints and the
objective function to form a matrix A with coefficients of the objective
function in the last row.
College Mathematics: Learning Worksheets Chapter 6
176
3.
17
⎢⎥
51 4
T
A⎡⎤
=⎢⎥
35
T
12
78
910
6.
246810
13 23 14 12 3
7614
9812
T
A
College Mathematics: Learning Worksheets Chapter 6
177
In Problems 7–10: a) Form the matrix A, using the coefficients and constants in the
7. Minimize: 12
56Cx x
subject to: 12
1
42 8
0
0
xx
x
x
+≥
≥
≥
⎡
⎢
subject to
1
1
45
26
0
y
y
y
≤
≤
≥
⎡
⎢
⎢
–8 0 0 1 0
⎢
⎣⎦
–8 0 0 1 0
⎢
⎥
⎣
⎦
5
1
100
⎡⎤
College Mathematics: Learning Worksheets Chapter 6
178
8. Minimize: 12
10 20Cx x=+
subject to: 12
12
12
25
7
,0
xx
xx
xx
a)
11 7
A
⎢⎥
=⎢⎥
c)
1120
T
A
⎢⎥
=−
d) Based on the above matrix, we want to maximize 12
57Py y
12
12
12
20
,0
yy
yy
−+ ≤
≥
e)
1101020
⎢⎥
−
⎢⎥
21 10010
⎡⎤
⎣⎦
f) The function has a minimum value of 70 at the point (7, 0).
College Mathematics: Learning Worksheets Chapter 6
179
9. Minimize: 12
13 12Cx x=+
subject to: 12
12
12
12
2
7
,0
xx
xx
xx
a)
⎡
11 7
A
⎢
⎥
=
⎢
⎥
⎢
⎢
⎣
c)
1112
T
A
⎢⎥
=−
⎢⎥
d) Based on the above matrix, we want to maximize 12
27Py y
2
12
12
12
,0
yy
yy
−+ ≤
≥
⎢
1
2110013
⎢
⎡⎤
⎢⎥
⎢⎥
⎣⎦
3
201 10 1
⎡
⎤
−
⎢
⎥
⎢
⎥
⎣
⎦
⎢
⎢
⎢
⎡
⎢
22 2
33 3
f) The function has a minimum value of 90 at the point (6, 1).
College Mathematics: Learning Worksheets Chapter 6
180
10. A dietician needs to plan a diet for a patient using two different food combinations to
meet the patient’s needs. Each container of Food A contains 4 units of Additive #1 and 2
units of Additive #2. Each container of Food B contains 2 units of Additive #1 and 4 units of
Additive #2. The patient needs at least 10 units of Additive #1 and at least 12 units of
Additive #2. How many containers of each food should the dietician use to meet the patients
needs and minimize the cost if one container of Food A costs $6 and each container of Food
B costs $10.
Let
1
x
represent Food A and 2
x
represent Food B. Based on the above information,
12
42 10
xx
42 10
6101
426
10 12 1
subject to:
12
12
12
42 6
24 10
,0
yy
yy
yy
⎢
421006
–10 –12 0 0 1 0
⎡⎤
⎢⎥
⎢
⎣⎦
1
2
5
11
301 0 1
400 3130
⎡
⎤
−
⎢
⎥
−
⎢
⎥
⎣
⎦
11 1
10 0
⎡⎤
−
⎣⎦
Therefore, to have a minimum cost of $31.33, you should use 1
3
1 containers of Food
College Mathematics: Learning Worksheets Chapter 6
181
Name ________________________________ Date ______________ Class ____________
Goal: To solve maximum and minimum problems with mixed problem constraints
Section 6-4 Maximization and Minimization with
Mixed Problem Constraints
To Form the Modified Problem:
Step 1: If any problem constraints have negative constants on the right side, multiply
both sides by –1 to obtain a constraint with a nonnegative constant. (If the
constraint is an inequality, this will reverse the direction of the inequality.)
Step 2: Introduce a slack variable in each < constraint.
Solving the problem using the Big M method:
Step 1: Form the preliminary simplex tableau for the modified problem (see above).
Step 2: Use row operations to eliminate the M’s in the bottom row of the preliminary
simplex tableau in the columns corresponding to the artificial variables. The
resulting tableau is the initial simplex tableau.
Step 3: Solve the modified problem by applying the simplex method to the initial
simplex tableau found in step 2.
Step 4: Relate the optimal solution of the modified problem to the original problem.
a) If the modified problem has no optimal solution, the original
College Mathematics: Learning Worksheets Chapter 6
182
For the following linear programming problems:
a) Form the modified problem.
b) Write the preliminary simplex tableau for the modified problem.
1. Maximize: 12
75Px x
subject to: 12
12
12
64 12
2
,0
xx
xx
xx
+≤
+≥
≥
a) Maximize: 12 1
75Px xMa
12 21
12121
2
,,,, 0
xx sa
xx ss a
+−+=
≥
12112
64100012
xx sas P
⎡⎤
c) 64100012
⎡⎤
⎣⎦
d) 11
24
01100
⎡⎤
−
⎢⎥
183
2. Minimize: 12
4Cx x
subject to: 12
12
12
6
2
,0
xx
xx
xx
a) Maximize: 12 1
4PC x xMa
12 21
12121
2
,,,, 0
xx sa
xx ss a
b)
12112
11 10 006
xx sas P
c) 1110006
d) 20 1 1 10 4
College Mathematics: Learning Worksheets Chapter 6
184