Simplex

The Simplex Algorithm

Overview

The Simplex method was developed in 1947² by George Dantzig when programs referred to (military) strategies. It is a method for finding an optimal solution to a certain problem type called a Linear Program (LP). An optimal solution to an LP does not always exists, but when it does the Simplex method can find it³. This little scrap of a paper introduces an implementation of the Simplex algorithm using Perl. We will use an example to drive the plot.

Motivation

Why should you care about the Simplex method?

• You dig optimality.
• You like to know you’ve got the best possible.
• You want to flex your finite muscles.
• You want to make or save bank.

Silly Example

A programmer named Dubd has found that she obtains maximum programming output when she consumes at least 100mg of caffeine and 80 grams of sugar every three hours. Dubd has not hit the big-time traveling circuit yet and must really pinch pennies. She must decide how she can meet her consumer needs while dolling out the least amount of dinero possible. She has scoured the eco-groovie food lots and come across two powder mixes of her liking that contain both caffeine and sugar.

Kaffinator powder mix has 50 milligrams of caffeine and 20 grams of sugar for each scoop, while BuzzBuilder powder weighs in with 30 milligrams of caffeine and 40 grams of sugar per scoop. In addition, Kaffinator and BuzzBuilder cost 30 and 20 pesos per scoop respectively. How much of each powder must she combine to get her desired caffeine-sugar fix while spending the least amout of money?

Formulation of LP

This type of mumbo jumbo (or story problem to algebraists) can be expressed via a set of linear inequalities and an objective function.

Variables

• k - number of scoops of Kaffinator powder.
• b - number of scoops of BuzzBuilder powder.

Objective

Minimize the amount of money spent on the two powders:

Minimize: 30k + 20b

Constraints

Make sure caffeine and sugar requirements are met:

5k + 3b >= 10
2k + 4b >= 8

Initial Tableau

While we are concerning ourselves with a minimization LP, every LP has both a maximization and minimization problem associated with it. This relates to the dual nature of Linear Programs. The Tucker Tableau approach represents this dual nature in the form a tableau that contains both a minimization LP (written vertically) and a maximization LP (written horizontally).

Therefore, the above LP is be expressed as the following Tucker Tableau:

	x1	x2	-1
Scoops of Kaffinator (k)	5 2 30 3 4 20 10 8 0			= -y1
Scoops of BuzzBuilder (b)				= -y2
-1				= f
	= Caffeine (u1)	= Sugar (u2)	= g

Solve The Problem

In the near future, Dubd knows that the hierarchical order will undulate for cold cash saved. In the near present, she knows that if she can save even just $1, she can permit herself a cold PBR at the Cowboy bar this coming weekend while undergoing a musical experiment by the Bare Metal Monkies w/ special guest Long Division.

Therefore she decides to take a hold of her finances and get analytical with her budget situation. She needs to optimize her caffeine/sugar buying power to afford Friday’s carbonated carbs. Being a CPAN junkie, she searches CPAN⁴ like any good Perl module afficionado would, and comes across Algorithm::Simplex. She notices it hasn’t yet been reviewed, but it does pass tests. More importantly perhaps, the Synposis shows a dead simple example of how to solve an LP given an initial tableau:

use Algorithm::Simplex::Rational;
my $matrix = [
    [ 5,  2,  30],
    [ 3,  4,  20],
    [10,  8,   0],
];
my $tableau = Algorithm::Simplex::Rational->new( tableau => $matrix );
$tableau->solve;

Optimal Tableau

Once the LP has been solved using the solve() method of Algorithm::Simplex, the optimal tableau can be displayed in a basic format via:

print Dumper $tableau->display_tableau;

While an HTML view of the optimal tableau is:

	y2	y1	-1
Caffeine (u1)	2/7 -1/7 40/7 -3/14 5/14 5/7 -8/7 -10/7 -440/7			= -y1
Sugar (u2)				= -y2
-1				= f
	= Scoops of Kaffinator (k)	= Scoops of BuzzBuilder (b)	= g

Interpretation of Results

The optimal tableau is read as follows. The optimal mix of the two powders is 8/7 scoops of Kaffinator combined with 10/7 scoops of BuzzBuilder. This will provide 100 mg of caffeine and 80 grams of sugar for the cost of 440/7 pesos.

Foot Notes

¹ “Linear Programs and Related Problems” Nering, Tucker 1993.

² Preface¹

³ An optimal solution could be one or infinitely many.

⁴ For an article on searching CPAN, see phaylon’s catalyzed.org article

My tags:

 

Popular tags: