for
Background for Linear
Programming
Linear
programming is an area of linear algebra in which the goal
is to maximize or minimize a linear function of variables
on a region whose
boundary is defined by linear inequalities and
equations. In this context, when we speak of a "linear
function of
variables" we mean that has
the form
.
The region is
a convex polytope. If all the vertices
of are
known, then the maximum of
will occur at one of these vertices.
The solution can be constructed using the
simplex method and is attributed to George
Dantzig (1914  ) who was born in Portland,
Oregon. The simplex method starts at the origin and
follows a path along the edges of the polytope to the vertex where
the maximum occurs. The history of the development of the
simplex method has been summarized in the article: An
Interview with George B. Dantzig: The Father of Linear
Programming by Donald J. Albers; Constance
Reid; in The College Mathematics Journal, Vol. 17, No. 4. (Sep.,
1986), pp. 292314, Jstor.
Definition (Convex Polytope). In two dimensions a convex polytope is a region that is the intersection of a finite set of halfplanes (the general idea of a convex polygon). In three dimensions a convex polytope is solid region that is the intersection of a finite set of halfspaces (the generalized idea of a convex polyhedron). The generalization in n dimensions is called a polytope.
Example 1. Two
students Ann and Carl work x and
y hours per week,
respectively. Together they can work at most 40 hours per
week. According to the rules for part timers Ann can work
at most 8 hours more that Carl. But Carl can work at most
6 hours more than Ann. There is an extra
constraint . Determine
the region for
these constraints.
1 (a). If Ann and Carl
earn $15 and $17 per hour, respectively, then find their maximum
combined income per week.
1 (b). If Ann and Carl
earn $17 and $15 per hour, respectively, then find their maximum
combined income per week.
1 (c). If Ann and Carl
both earn $16 per hour, respectively, then find their maximum
combined income per week.
Standard Form of
the Linear Programming Problem
The standard form of the linear programming
problem is to maximize of variables
.
(1) Maximize
where for .
(2) Subject
to the m constraints
where for .
(3) With
the primary constraints
for .
The coefficients and can
be any real number. It is often the case
that , but
the cases or can
occur.
Setting up the
Extended Simplex Tableau
For computational purposes, we construct a
tableau. The first
rows consist of the coefficients matrix
,
the identity matrix
and the column vector .
In the row
of the tableau the first
elements are the coefficients , which
are called the coefficients of the augmented
objective equation. The remainder of the bottom row
is filled in with zeros. An extra column on the right will
be used in the decision process in solving for the variables.

The
nonnegative variable
is called a slack variable and is the amount that the linear
combination falls
short of the bound . It's
purpose is to change an inequality to an equation, i.e. we have
(4) for
rows
in the
tableau.
The goal of the simplex method is to exchange some of the columns of 1's and 0's of the slack variables into columns of 1's and 0's of the decision variables.
A explanation of this tableau is given in the link below.
Algorithm (Simplex Method). To find the minimum of over the convex polytope .
(i) Use nonnegative slack variables and form a system of equations and the initial tableau.
(ii) Determine
the exchange variable, the pivot row and pivotal
element.
The exchange variable
is chosen in the pivot column
where is
the smallest negative coefficient.
The
pivot row is
chosen where the minimum ratio occurs
for all rows with .
The pivot element is
.
(iii) Perform row operations to zero out elements in the pivotal column above and below the pivot row .
(iv) Repeat steps (ii) and (iii) until there are no negative coefficients in the bottom row.
Computer Programs Linear Programming
Mathematica Subroutines (Simplex
Method). To
find the minimum of over
the convex polytope .
Activate the following four cells.
Warning. The above subroutines are for pedagogical purposes to illustrate the simplex method. They will not work for certain cases when , and in cases where more than one coefficient is set equal to zero in one step of the iteration. For complicated problems one of the Mathematica subroutines: ConstrainedMin, ConstrainedMax, or LinearProgramming should be used.
Example 2. Consider
the region
in the plane defined by the inequalities:
2 (a). Find the
maximum of over
the region .
2 (b). Find the
maximum of over
the region .
Example 3. Consider
the region
in the plane defined by the inequalities:
3 (a). Find the
maximum of over
the region .
3 (b). Find the
maximum of over
the region .
Example
4. Find the
maximum of subject
to the constraints:
Example
5. Find the
maximum of subject
to the constraints:
Example
6. Find the
maximum of subject
to the constraints:
Research Experience for Undergraduates
Linear Programming Internet hyperlinks to web sites and a bibliography of articles.
Download this Mathematica Notebook Linear ProgrammingSimplex Method
(c) John H. Mathews 2005