Algorithm Animation: Two Phase Simplex Method
If the Java applet fails to start due to Java Security issues,
click
here.
Introduction
Since most people benefit greatly from geometric intuition,
it is natural to try to represent a algorithms graphically. The
obvious/textbook graphical representation of algorithms for linear
programming involve restricting ones attention to situations with at most
3 variables.
However,
real-world linear programming problems involve thousands of variables and
constraints.
It would be nice to have graphical representations for these problems too.
If one is willing to restrict ones attention to a specific application area,
then it is often easy to come up with a nice representation of the problem.
Minimum-Weight Structural Design
Here we consider the minimum-weight structural design problem.
A simple version of this problem is defined as follows.
One starts with a graph (i.e., list of
nodes and connecting arcs) that represents places in 2 or 3 dimensional
space where structural beams could be placed. The problem is to design
a structure that is anchored at certain specified nodes
and that can support a specified load (i.e., force vector) at certain other
specific nodes. We assume that each beam must have a cross sectional area that
is proportional to the tension/compression that that beam must carry in order
to have force balance at every node in the structure. Of course, the objective
is to minimize weight, which is
assumed to be proportional to the sum of the volumes of the beams.
Without going into the details
(see
Chapter 15 of Linear Programming: Foundations and Extensions),
the problem can be easily formulated as a linear programming problem.
Two Phase Simplex Algorithm
The applet below animates the two phase simplex algorithm for solving
linear programming problems.
There are several data sets one can choose from.
After selecting a problem and clicking on the Solve button, you will see
a graphical animation of the algorithm. Nodes are shown
in blue except for anchor nodes which are magenta and load nodes which
are yellow. The load vectors themselves aren't shown;
they are in all cases vectors pointing vertically
downward.
Details of the two phase simplex
method can be found in
Chapter 6 of
Linear Programming: Foundations and Extensions).
Running the Animation
In the optimal structure, beams with zero cross-sectional area are, of course,
simply not built. Of the beams that remain, some are under compression and
others are under tension. The compressed beams are shown in red while the
beams under tension are shown in green. As the algorithm progresses from
an initial solution to the optimal solution, there are times when beams one
or both of the tension/compression components of the force are
given negative values. These ``negative'' beams are shown in
magenta and teal.
There are a few parameters that you can play with.
You can select whether you want to see an update of the animation on
every simplex pivot or just once every 200 pivots. Usually, the
animation looks best if updated with every pivot.
The second parameter is the strength of the beam material.
A larger value
gives smaller cross sections. You should simply adjust this parameter as
appropriate to get a nice visual representation for each specific problem.