MATH 1003 Calculus and Linear Algebra (Lecture 8)

Albert Ku
HKUST Mathematics Department
Albert Ku (HKUST) MATH 1003 1 / 22
Outline
1
Applications of Gauss-Jordan Elimination
2
Tank Car Leases
3
Trac Flow
4
Boat Production
Albert Ku (HKUST) MATH 1003 2 / 22
Applications of Gauss-Jordan Elimination
Applications of Gauss-Jordan Elimination
A lot of problems in real life can be modelled by systems of linear
equations. In this lecture, we will study three dierent application
problems which can be solved by applying Gauss-Jordan elimination on the
systems of linear equations that formulate the problems.
Albert Ku (HKUST) MATH 1003 3 / 22
Tank Car Leases
Tank Car Leases
Example
A chemical manufacturer wants to lease a eet of 24 railroad tank cars
with a combined carrying capacity of 520,000 gallons. Tank cars with three
dierent carrying capacities are available: 8,000 gallons, 16,000 gallons,
and 24,000 gallons. How many of each type of tank car should be leased?
Albert Ku (HKUST) MATH 1003 4 / 22
Tank Car Leases
Solution
To formulate the problem, we rst need to dene relevant quantities as
variables:
Let x
1
be the number of tank cars with a capacity of 8,000 gallons
Let x
2
be the number of tank cars with a capacity of 16,000 gallons
Let x
3
be the number of tank cars with a capacity of 24,000 gallons
Given the criteria stated in the problem, we can obtain the following linear
system:
_
x
1
+ x
2
+ x
3
= 24
8000x
1
+ 16000x
2
+ 24000x
3
= 520000
The corresponding augmented matrix is
_
1 1 1 24
8000 16000 24000 520000
_
Albert Ku (HKUST) MATH 1003 5 / 22
Tank Car Leases
_
1 1 1 24
8000 16000 24000 520000
_
1
8000
R
2
R
2

_
1 1 1 24
1 2 3 65
_
R
2
+(1)R
1
R
2

_
1 1 1 24
0 1 2 41
_
R
1
+(1)R
2
R
1

_
1 0 1 17
0 1 2 41
_
The linear system corresponding to the reduced form is
_
x
1
x
3
= 17
x
2
+ 2x
3
= 41
Albert Ku (HKUST) MATH 1003 6 / 22
Tank Car Leases
Since x
3
is the free variable, we let x
3
= t, where t is any real number.
Then the general solution can be written as follows:
_

_
x
1
= 17 + t
x
2
= 41 2t
x
3
= t
where t is any real number.
However, the denitions of x
1
, x
2
and x
3
imply that the solutions must be
non-negative integers. Therefore, we need to derive the possible range of
values of t such that the general solution make sense for this problem:
_

_
17 + t 0
41 2t 0
t 0
and t must be an integer.
Albert Ku (HKUST) MATH 1003 7 / 22
Tank Car Leases
Solving the inequalities, we nally obtain all the relevant solutions to the
linear system:
_

_
x
1
= 17 + t
x
2
= 41 2t
x
3
= t
where t is any integer such that 17 t 20.
Albert Ku (HKUST) MATH 1003 8 / 22
Trac Flow
Trac Flow
Example
The rush-hour trac ow for a network of for one-way streets in a city is
shown in the gure. The numbers next to each street indicate the number
of vehicles per hour that enter and leave the network on that street. The
variable x
1
, x
2
, x
3
and x
4
represent the ow of trac between the four
intersections in the network.
Albert Ku (HKUST) MATH 1003 9 / 22
Trac Flow
(a) For a smooth trac ow, the number of vehicles entering each
intersection should always equal the number leaving. For example,
since 1000 vehicles enter the intersection of 1st Street and 3rd Street
each hour and x
1
+ x
3
vehicles leave this intersection, we see that
x
1
+ x
3
= 1000. Find the equations determined by the trac ow at
each of the other three intersections.
(b) Find the solution to the system in (a).
(c) What is the maximum number of vehicles that can travel from 3rd
Street to 4th Street on 1st Street? What is the minimum number?
(d) If trac lights are adjusted so that 700 vehicles per hour travel from
3rd Street to 4th Street on 1st Street, determine the ow around the
rest of the network.
Albert Ku (HKUST) MATH 1003 10 / 22
Trac Flow
Solution for (a)
For each of the four intersections, the number of vehicles entering the
intersection equals the number leaving. Therefore, we have
_

_
x
1
+ x
4
= 1100
x
1
+ x
3
= 1000
x
2
+ x
3
= 1100
x
2
+ x
4
= 1200
Albert Ku (HKUST) MATH 1003 11 / 22
Trac Flow
Solution for (b)
We use Gauss-Jordan elimination to solve the linear system in (a):
_
_
_
_
1 0 0 1 1100
1 0 1 0 1000
0 1 1 0 1100
0 1 0 1 1200
_
_
_
_

_
_
_
_
1 0 0 1 1100
0 0 1 1 100
0 1 1 0 1100
0 1 0 1 1200
_
_
_
_

_
_
_
_
1 0 0 1 1100
0 1 1 0 1100
0 0 1 1 100
0 1 0 1 1200
_
_
_
_

_
_
_
_
1 0 0 1 1100
0 1 1 0 1100
0 0 1 1 100
0 0 1 1 100
_
_
_
_

_
_
_
_
1 0 0 1 1100
0 1 0 1 1200
0 0 1 1 100
0 0 0 0 0
_
_
_
_
Albert Ku (HKUST) MATH 1003 12 / 22
Trac Flow
The linear system corresponding to the reduced form is
_
_
_
x
1
+ x
4
= 1100
x
2
+ x
4
= 1200
x
3
x
4
= 100
x
4
is the free variable. Hence let x
4
= t and we have the following general
solution:
_

_
x
1
= 1100 t
x
2
= 1200 t
x
3
= 100 + t
x
4
= t
where t is any real number.
Albert Ku (HKUST) MATH 1003 13 / 22
Trac Flow
Similar to the previous example, the solution makes sense only when
x
1
, x
2
, x
3
and x
4
are non-negative integers. Therefore, we have
_

_
1100 t 0
1200 t 0
100 + t 0
t 0
and t is an integer. Solving the inequalities, we obtain the all the relevent
solutions:
_

_
x
1
= 1100 t
x
2
= 1200 t
x
3
= 100 + t
x
4
= t
where t is any integer such that 100 t 1100.
Albert Ku (HKUST) MATH 1003 14 / 22
Trac Flow
Solution for (c) and (d)
(c) By the result from (b), we know that x
1
= 1100 t and t is any
integer such that 100 t 1100. Therefore, the maximum value of
x
1
is 1000 and the minimum value of x
1
is 0.
(d) Set x
1
= 700. By the result from (b), 700 = x
1
= 1100 t. Hence
t = 400 and we have
_

_
x
1
= 700
x
2
= 1200 400 = 800
x
3
= 100 + 400 = 300
x
4
= 400
Albert Ku (HKUST) MATH 1003 15 / 22
Boat Production
Boat Production
Example
A small manufacturing plant makes three types of inatable boats:
one-person, two-person, and four-person models. Each boat requires the
services of three departments, as listed in the table. The cutting, assembly
and packaging departments have available a maximum of 380, 330 and
120 labor-hours per week, respectively.
Department One-Person Two-Person Four-Person
Boat Boat Boat
Cutting 0.5hr 1.0hr 1.5hr
Assembly 0.6hr 0.9hr 1.2hr
Packaging 0.2hr 0.3hr 0.5hr
Albert Ku (HKUST) MATH 1003 16 / 22
Boat Production
(a) How many boats of each type must be produced each week for the
plant to operate at full capacity?
(b) How is the production schedule in part (a) aected if the packaging
department is no longer used?
(c) How is the production schedule in part (a) aected if the four-person
boat is no longer produced?
Albert Ku (HKUST) MATH 1003 17 / 22
Boat Production
Solution for (a)
Let x
1
, x
2
and x
3
be the number of one-person boats, two-person boats
and four-person boats produced each week respectively.
According to the given table, we have the following linear system:
_

_
0.5x
1
+ x
2
+ 1.5x
3
= 380
0.6x
1
+ 0.9x
2
+ 1.2x
3
= 330
0.2x
1
+ 0.3x
2
+ 0.5x
3
= 120
Albert Ku (HKUST) MATH 1003 18 / 22
Boat Production
_
_
0.5 1 1.5 380
0.6 0.9 1.2 330
0.2 0.3 0.5 120
_
_

_
_
1 2 3 760
2 3 4 1100
2 3 5 1200
_
_

_
_
1 2 3 760
0 1 2 420
0 1 1 320
_
_

_
_
1 2 3 760
0 1 2 420
0 0 1 100
_
_

_
_
1 0 1 80
0 1 2 420
0 0 1 100
_
_

_
_
1 0 0 20
0 1 0 220
0 0 1 100
_
_
Therefore, the solution is x
1
= 20, x
2
= 220 and x
3
= 100.
Albert Ku (HKUST) MATH 1003 19 / 22
Boat Production
Solution for (b)
If the packaging department is no longer used, we should drop the last
equation in the linear system i.e. the corresponding augmented matrix
should be
_
0.5 1 1.5 380
0.6 0.9 1.2 330
_
Using the steps of Gauss-Jordan elimination in (a), we obtain
_
1 0 1 80
0 1 2 420
_
Albert Ku (HKUST) MATH 1003 20 / 22
Boat Production
Since x
3
is the free variable, Let x
3
= t and hence the general solution is
_

_
x
1
= 80 + t
x
2
= 420 2t
x
3
= t
where t is any integer such that 80 t 210.
Albert Ku (HKUST) MATH 1003 21 / 22
Boat Production
Solution for (c)
If the four-person boat is no longer produced, we should drop the variable
x
3
in the linear system i.e. the corresponding augmented matrix should be
_
_
0.5 1 380
0.6 0.9 330
0.2 0.3 120
_
_
Using the steps of Gauss-Jordan elimination in (a), we obtain
_
_
1 2 760
0 1 420
0 0 100
_
_
Therefore, the linear system has no solution.
Albert Ku (HKUST) MATH 1003 22 / 22