WHAT SHOULD I DO?

Some Thoughts on Linear Programming

Michael Round

May 13, 2009

Let's suppose you're in charge of purchasing for Alpha-Omega Bookstores.  Your boss has given you $1,400 to spend on bookshelves, and tasked you with the responsibility of furnishing the modest room.

You head off to Office Depot.  You find two bookshelves you really like, and are given the following "spec sheet" by the willing worker:

You had not thought of "square footage" when you left, but of course it's important,  There's a limited amount of space on the floor, after all!  Also, does the boss want tall-and-skinny shelves, or short-and-wide ones?

You hesitantly reach the boss on your cell phone, who tells you the store has room for about 72 square feet of bookshelves.

What to do?

You can afford 14 "# 1s" - costing $1,400 - but that would be 84 square feet.  You can afford 7 "# 2s" - again, costing $1,400 - but that only gives 56 square feet.  Show up with the former, and you're in trouble for buying too much square footage shelving - show up with the latter, and you're in trouble for buying too little!

What to do?

Likely you're suppose to buy a combination of the two, but what combination?  You run back to the office, careful to avoid your boss (who's expecting shelves and not questions), and decide to run a quick check of all possible combinations!  You decide, based on cost, to run every combination from 0 to 14 "# 1s" and 0 to 7 "# 2s":

Of course, many of these do not meet the criteria - the combination is either too expensive, or it takes up too much space, or both.

Additionally, many of the combinations - while meeting both cost and space constraints - clearly are not "plausible" answers.  No shelves, for example, meets the criteria, but will certainly get me fired!

You decide to sort the combinations meeting both criteria in descending order, using "capacity" as the sorting criteria.  You see "8 of Type 1, 3 of Type 2" is the "optimal" answer:

You rush back to the store, purchasing 11 bookshelves (8 of #1, 3 of #2), confident in your purchase, and ready to defend it - analytically - to your boss, who likely will say "why did you do that"?

Why did you do that?

Does it really take such a procedure to find solutions to systems where "there's a lot going on"?  Is there something more simple than sheer brute computing power to provide the answer?

One man asked the same question, following World War II.

Charged with solving systems like this, only infinitely harder, this man developed a geometric and analytic method for interpreting "systems with constraints".

His name was George Dantzig.

Dantzig realized, in graphing the constraints, one could immediately eliminate two types of obviously wrong answers visually:

1. those meeting one criteria - but not another;

2. those meeting both criteria, but usually arriving at a "trivial" answer (like our purchasing no shelves above).

But more than this, the "feasible region of possible answers", it turns out, provides a means of directly arriving at an answer, as the edge points of the feasible region afford an optimal answer!

But more than this!  He found an analytic means to program all of this - called the Simplex Method!

Many More Questions To Ask

Having done this geometrically and analytically is one thing.  To implement it intuitively is quite another.  The focus on the constraint is essential to practically solving and implementing business solutions, but which constraint?  Are they all equal in nature, or are some constraints more important than others?

In The Goal, for example, during the Boy Scout trail walk, surely we could arrive at a number of constraints - conditions - governing the walk:  we must cover at least 10 miles a day.  We must stop and rest 10 minutes every hour.  We must allow 1 hour for lunch.  We cannot go faster than 3 miles per hour.  etc. 

But in the case of the trail walk, we realized simple things like offloading Herbie's backpack, and making sure Herbie was not stopping improved the performance of the system.

Yes - many constraints, but one more important than all others!  Few constraints governing the performance of the system.

How does this systems' paradigm relate to the Simplex Method of George Dantzig and linear programming?

Additionally, our answer above - 8 of one, 3 of another - was pretty precise.  What happens if I go back to the store and they only have 2 of the "short-and-fat" shelves?  Or the price has slightly changed?  Is the Simplex Method "8 and 3" output set in stone, or are there answers "good enough"?

Many more questions - and answers to research.

Why have I gone to such detail to describe mathematical and systems' perspectives on this topic?

Rest in Peace, Father of the Simplex Method

Today is the fourth anniversary of the death of the great George Dantzig, who passed away May 13, 2005.