\section{Excavating and Leveling a Large Land Tract}\label{S:LandLeveling}

\newpar
An excavation company must prepare a large tract of land for future construction. \footnote{Based upon
Moreb and Bafail,  \cite{Moreb_Landlevelling}, (1994)}
The company recognizes the difficulty and lack of aesthetics associated with leveling the site to form one horizontal plane. Instead, it divides the site into eight rectangles, with each rectangle assigned to fall in one of three possible planes, whose equations are to be determined. Rectangles within a given plane must be pairwise adjacent.

\newpar
Each plane will be expressed as a function of $x$ and $y$, and to keep the planes relatively
``flat,'' we require that the slopes in both the $x$- and $y$-directions that are close to zero. (The actual tolerance will be prescribed as a constraint in the LP.) In addition, adjacent
planes should meet along their edges so as to avoid ``jumps.'' This entire process of plane-fitting and leveling is accomplished through a process of transporting among the various rectangles. The company's goal is to minimize the total costs stemming from the digging of dirt, the filling of dirt, and the transporting of dirt from one rectangle to another.

\newpar
The eight rectangles and their designated planes are shown in Figure \ref{Fi:land_tract}.

\begin{figure}[h]
\centering
\includegraphics[width=.9 \linewidth]{images/p01x01.eps}
\caption{Land tract site consisting of eight rectangles forming three planes.}
\label{Fi:land_tract}
\end{figure}

\newpar
Corresponding to rectangle $i$, $1 \leq i \leq 8$, is its center $(x_i,y_i)$
in $\R^2$, its area, $A_i$, and its average height, $h_i$.
The excavation is comprised of three different types of processes: ``Cutting,'' or digging dirt from a rectangle, which decreases the rectangle's average height, transporting dirt from one rectangle to another, and, finally, ``filling,'' or adding dirt to a rectangle, which increases the rectangle's average height.

\newpar
We define the decision variables for this model using the following notation:
	\bi
	\item $c_i$, where $1 \leq i \leq 8$: amount of ``cut'' from rectangle $i$, measured in feet.
    \item $f_i$, $1 \leq i \leq 8$: amount of ``fill'' for rectangle $i$, measured in feet.
	\item $t_{ij}$, where
	$1 \leq i \leq 8$ and $1 \leq j \leq 8$:
	amount of dirt transported from rectangle $i$ to rectangle $j$, measured in units of cubic feet, where we assume $t_{ii}=0$ for $i=1,2,\ldots,8$.
	\item $a_j$, $1 \leq j \leq 3$: the slope in the $x$-direction of plane $j$.
	\item $b_j$, $1 \leq j \leq 3$: the slope in the $y$-direction of plane $j$.
	\item $d_j$, $1 \leq j \leq 3$: the vertical axis intercept of plane $j$.
	\ei

\newpar
To create an LP with nonnegative decision variables, we rewrite
all slopes and intercepts of the planes as differences of two nonnegative decision variables:
\[ a_j=a_{j1}-a_{j2}\mbox{, } b_j=b_{j1}-b_{j2} \mbox{, and   } d_j=d_{j1}-d_{j2}, \quad 1 \leq j \leq 3,\]
where $a_{jk}$ $b_{jk}$, and $d_{jk}$ is nonnegative for $1 \leq k \leq 2$ and $1 \leq j \leq 3$.

\newpar
Equations for planes can then be created using this notation. For example,
\begin{align*}
T_1(x,y)&= a_1x+b_1 y +d_1 \\
        &= (a_{11}-a_{12})x+(b_{11}-b_{12})y+(d_{11}-d_{12})
\end{align*}
represents the equation of the first plane. For the sake of aesthetics,
we prescribe that each plane has slopes in the $x$- and $y$-directions
falling between -.1 and .1.

\newpar
Costs, in dollars, associated with filling, cutting, and transporting are given as follows:
	\bi
	\item The cost of removing one cubic foot of dirt from
    any rectangle is \$2
    \item The cost of adding one cubic foot of dirt from
    any rectangle is \$1
    \item The cost of transporting one cubic foot from one rectangle to another is
    \$1
    \ei

\be
\item Construct the objective function for this LP, which consists of total costs stemming from three sources: the digging of dirt from the rectangles, the adding of dirt to the rectangles, and the transporting of dirt between pairs of rectangles.
\item Now formulate a set of constraints for the LP. They arise from the following requirements:

	\be
	\item There is a gap between the original height of each rectangle and the height of the new plane
	containing the rectangle. This gap equals the difference between the fill and cut amounts for the rectangle. A total of eight equations arise from this condition.
	\item Each rectangle has an area, $A_i$. The net volume of dirt removed from that rectangle can be
	expressed two ways. The first uses the quantities $A_i$, $c_i$, and $f_i$; the other utilizes the family
    of variables, $\left\{t_{ij}\right\}$. For example, the volume of dirt added to rectangle one, equals
    \begin{equation*}
    (t_{21}-t_{12})+(t_{31}-t_{13})+...+(t_{81}-t_{18}),
    \end{equation*}
    which can also be expressed in terms of $A_1$, $c_1$, and $f_1$. Eight more
    constraints arise from this condition.
    \item Six more constraints stem from the requirements that the slopes $a_j=a_{j1}-a_{j2}$ and $b_j=b_{j1}-b_{j2}$, where $1 \leq j \leq 3$,
	must fall within their prescribed lower and upper limits.
	\item The restriction that no gaps between exist between planes is fulfilled if planes 1 and 3
    intersect at both $(0,40)$ and $(56,40)$, planes 1 and 2 at both $(56,100)$ and $(56,40)$, and
    planes 2 and 3 at $(80,40)$.
	\ee

\newpar
\item Now use Maple to solve the LP that minimizes the objective from (1), subject to the
constraints from (2).

\ee 