%This is a Plain-TeX document
\magnification=\magstep1
\centerline{ MATH 360}
\centerline{ SAMPLE PROJECT}
\medskip
\centerline{ Locating a railway supply depot}
\bigskip
Several factors influence the location of factories, power plants,
retail stores, and other commercial buildings. The placement of
machines in a production facility is similarly subject to a number of
considerations. Final decisions are made by balancing the pros and
cons of various options. In this project we will show that in some
circumstances we can find an optimal location easily.
This is the scenario we consider:
\medskip
Because of extreme weather conditions, lots of maintenance and repairs
are needed for the trains which run on the trans-Siberian railway. This
maintenance is carried out at a number of sidings (repair stations)
which are located at various points along the track. Parts are scarce
and it is not economical to stock them at all the repair
facilities. Instead, it is planned to implement a ``just in time"
supply procedure: a Parts Distribution Center is to be built somewhere
along the track. Parts will be shipped from there to the various
repair facilities. The problem is to choose a location which will
minimize the cost of {\it supplying\/} the parts to the sidings.
\medskip
How could we possibly solve this problem? We need to translate it into
mathematical terms. The first step is to decide on a way of representing
the setting for the problem. Since the setting is a single railroad track, it
is essentially one-dimensional, so we will represent the railroad track by
the $x$-axis. (We must select a point to be the origin, and select our
unit of measurement, but those choices won't affect our answers.) Then
the sidings can be represented by points $x_i$ ($i = 1, 2, \ldots, n$) on the
$x$-axis, where $n$ is the number of sidings. We'll likewise let the unknown
$x$ be the position of the parts center. There is a certain cost $C(x)$
associated with siting the parts center at any point $x$; the problem
then becomes:
Find the location $x$ of the parts center so that the cost $C(x)$
of supplying parts to $x_1, \ldots, x_n$ is minimized.
At one level, the problem is of a familiar type. It is a
maximum/minimum problem, and we know that calculus provides a tool for
solving such problems. However, what is the function $C(x)$ to be
minimized? This isn't given directly in the statement of the
problem. We shall have to figure it out.
\smallskip
The cost of supplying parts will depend on the distance through which
they must be moved. This, in turn, will depend on the number of trips
to each siding $x_i$, and the distance from $x$ to $x_i$.
Denote by $N_i$ the number of trips to siding $x_i$ in a year. Then the
total distance involved in all the supply trips to repair station $i$ is
$$ N_i |x - x_i|.$$
Now, how does this determine the cost? The statement of the problem
does not say; what's a reasonable assumption? Costs primarily
associated with transit (say, driver's hourly wage, or fuel cost) are
roughly proportional to the distance traveled, say, $C = k D$. Let us
assume that this is in fact how $C(x)$ is to be computed; that is, we
make explicit the assumption that there is a unit cost $k$ such that
total cost is $k$ times the distance traveled.
Then the cost of maintaining the parts center at $x$ is of the form
$$C(x) = k\{N_1|x-x_1| + \ldots + N_n|x-x_n|\}$$
$$=M_1|x-x_1|+\ldots +M_n|x-x_n|$$
for some constants
$M_1 = k N_1,\ \ldots,\ M_n = k N_n$. Our problem becomes, ``Find the value
of $x$ which minimizes $C(x)$".
Before trying to solve this problem, we note that we have made several
assumptions in setting up the model, and so there are several
questions about the model that we should consider. For example, is the
model a realistic one? The model depends on the distance from $x$ to
each $x_i$, and also on the number $N_i$ of trips from the parts center to
$x_i$. How can we determine $N_i$? We shall return to these questions
later.
\medskip
At first this seems like a simple calculus problem. We know how to
solve those: just take the derivative and set it to zero, right ? The
problems is that the function $C(x)$ doesn't have a derivative
everywhere because of the absolute value bars, so we can't just take
the derivative. However, we can use theorems from calculus to help us
solve the problem. Let's see what see do know about $C(x)$.
1. $C(x)$ is the sum of the functions $C_i(x) = N_i|x-x_i|$ for $i = 1, \ldots
n$. Each of these is a continuous function. Therefore, since the sum
of continuous functions is continuous, $C(x)$ is continuous for all
values of $x$. Since we know that $C(x)$ is continuous, a theorem from
calculus tells us that $C(x)$ {\it has\/} a minimum value on $[A,B]$, so there
really is a solution to the problem.
2. $C_i(x) = N_i|x-x_i|$ is differentiable for all $x$ different from $x_i$.
For example, $y=5|x-2|$ is differentiable for all values of $x$ except
$x=2$. Further, the graph is a straight line, that is, the function is
linear, on the intervals $(-\infty, 2)$ and $(2, \infty)$. Thus, since the
derivative of a sum is the sum of the derivatives provided the
derivative of each summand exists, we see that $C(x)$ is
differentable at every point different from $x_1, \ldots, x_n$.
3. The minimum value of $C(x)$ occurs at one of the following:
--- at one of the ends of the interval;
--- at a point in the interior of the interval where the derivative is zero;
--- at a point in the interior of the interval where the derivative does not exist.
4. Since the sum of linear functions is linear, we know that $C(x)$ is
linear on each of the intervals $[A, x_1],\ [x_1, x_2],\ \ldots,\ [x_n, B]$
and so the minimum value of $C(x)$ on the interval occurs at one of the
end points. This means that the minimum value of $C(x)$ on $[A,B]$ occurs
at one of the points $A, x_1, \ldots, x_n, B$. To find an optimal location
we can calculate the values of $C(x)$ at these $n+2$ points and find those
locations where the value is least.
\medskip
The solution we have given is a qualitative one. It uses qualitative
properties of the model --- continuity, differentiability, etc. --- to
show that the problem has a solution and, in qualitative terms, where
the solution may be found. But how good a solution is this? There are
still questions to be asked.
For example, how many solutions are there? If there are several, how
do we distinguish between them? (Maybe one is better than another for
some purposes.) How efficient is the solution? That is, how much
computational effort is required to find it? If there are only a few
sidings, this isn't really a problem but what if many locations were
involved? The solution we have given doesn't explicitly take into
account the particular locations $x_i$ and costs $N_i$. Can we get a
better solution process if we do take these into account? In other
words, can we {\it refine\/} the solution we have already obtained to find a
better one?
\smallskip
Let's look at an example where there are three sidings located at 2,3, and 5 on the $x$-axis, and where
$$ C(x) = 4|x-2| + |x-3| + 2|x-5|.$$
To see what is going on, we consider the graph of $C(x)$ on the subintervals
$$ (-\infty, 2),\ (2,3),\ (3,5),\ (5, \infty)$$
of the $x$-axis because the absolute values change on these intervals. To
the left of $x=2$, for example, $|x-2| = 2-x, \ |x-3|=3-x$, and $|x-5|=5-x$, so that
$C(x) = 21-7x$, whose graph is a straight line with slope $-7$. Likewise in the
the remaining intervals, we calculate $C(x) = x+5,\ 3x-1,$ and $7x-21$,
respectively.
Looking at the graph then shows there is exactly one location where the minimum
value occurs, namely $x=3$.
To see what is going on in the general situation where there are $n$ locations
we look at the intervals
$$ (-\infty, x_1),\ (x_1, x_2),\ \ldots,\ (x_n, \infty).$$
First consider $(-\infty, x_1)$. Here $|x-x_1| = x_i-x$ for each $i$ so that
$$ C(x) = N_1 |x-x_1| + \ldots + N_n|x-x_n|$$
$$ = N_1 (x_1 - x ) + \ldots + N_n(x_n - x)$$
$$ = (N_1x_1 + \ldots + N_n x_n) - (N_1+\ldots+N_n)x$$
which is the equation of a straight line with negative slope
$$ S_0 = - (N_1+\ldots+N_n).$$
Next consider $(x_n, \infty)$. Here $|x-x_1| = x-x_i$ for each $i$ so that
the situation this time is the opposite of that which we considered before.
We get
$$ C(x) = N_1 |x-x_1| + \ldots + N_n|x-x_n|$$
$$ = N_1 (x - x_1) + \ldots + N_n(x - x_n)$$
$$ = (N_1+\ldots+N_n)x - (N_1x_1 + \ldots + N_n x_n)$$
which is the equation of a straight line with positive slope
$$ S_n = N_1+\ldots+N_n.$$
It follows from these two cases that the minimum value must occur at one of the
points $x_1, \ldots, x_n$, rather than at the endpoints $A$ or $B$.
Finally, consider one of the intervals $ (x_r, x_{r+1})$ where $r = 1, 2, \ldots, n-1.$
For $x$ in this interval, $x-x_i$ is positive for $i \le r$ and negative for
$i > r$, so that
$$C(x) = \{N_1(x-x_1) + \ldots + N_r(x-x_r)\} - \{N_{r+1}(x-x_{r+1}) + \ldots + N_n(x-x_n)\}$$
which is a straight line with slope
$$ S_r = (N_1 + \ldots + N_r) - (N_{r+1}+ \ldots + N_n).$$
Looking at the slopes we see that
$$ S_0 = - (N_1+\ldots+N_n)$$
$$ S_1 = N_1 - (N_2+\ldots+N_n) = 2N_1 + S_0 > S_0$$
$$ S_2 = N_1+N_2 - (N_3+\ldots+N_n) = 2N_2 + S_1 > S_1$$
and in general $S_{r+1} = 2 N_r + S_r > S_r$. This means that the slopes
of the line segments which go to making up $C(x)$ are strictly increasing so there
are just two possibilities:
1. There is exactly one optimal location (this happens if no $S_r = 0$)
2. There are exactly two adjacent $x$'s, say $x_i$ and $x_{i+1}$, where $C(x)$
has the same value. In this case, any location in the closed interval $[x_i, x_{i+1}]$ will give an optimal location.
\smallskip
By doing this further analysis we have got more understanding about what is
going on in the problem. In addition, we have another way of finding the optimal location which uses the additional information. The optimal location
occurs at $x_i$ if $S_{i-1} < 0$ and $ S_i > 0$, (or else anywhere in $ [x_i, x_{i+1}]$ if
$S_i = 0$). How can we test for this?
1. Calculate $N_1 + \ldots + N_n$ and set $T_0 = S_0/2 = (N_1 + \ldots + N_n)/2$;
(this takes $n+2$ arithmetic operations).
2. Repeatedly add $N_i$'s to get $T_1, T_2, \ldots$ until $T_i \ge 0$; this is
at most $2(n-1)$ further operations. (We know $T_n = S_n/2$ is positive so
the change must occur among $T_1, \ldots, T_{n-1}$.)
Therefore, using this method, we can find the optimal location in at most
$3n$ operations. Evaluating $C(x)$ directly at each of $x_1, \ldots, x_n$ and then
finding the smallest value requires approximately $2n^2$ operations. If $n=10$, this
gives approximately 200 operations as opposed to 30 by the other method. When $n=100$, direct calculation requires approximately 20,000 as opposed to 300 !
The second solution is clearly more efficient. Furthermore, we now understand
much more. For example, the optimal solution doesn't depend directly on the
locations $x_i$; it only depends on the values $N_i$ and on the order in which they occur! We wouldn't have guessed that up front. The mathematical analysis has given us
{\it understanding\/} about how the system works and not just numbers.
\vfill\eject\end