(That may sound strange. Bear with me.)
Every once in a while, I pick up and play with linear programming. This post will show you a couple of elementary ways to set up and solve a small linear programming problem….
But that is not the main purpose of this post.
For the record, Mathematica® has some special–purpose commands for solving large linear programming problems. I believe it handles them as data sets in a standardized format. I also believe its smallest example has more than 30 variables. So, if you need to do linear programming professionally, you should look at Mathematica’s linear programming command.
But if, like me, you pick up linear programming as a student who wants to work his way through a textbook, then you need something else.
Working through a textbook will almost certainly involve tabular displays of the initial problem, a sequence of tabular displays of intermediate non-optimal solutions, and a display of the final optimal solution. Each of these tables is typically called by the French “tableau”, plural tableaux.
You need to know how to get the final tableau, given Mathematica’s solution and the initial tableau (i.e. the initial data).
It is, of course, possible to write your own functions which will permit you to move from tableau to tableau. The process involves row operations on an array. This can be instructive if you are trying to understand the simplex method or its variants.
I wrote such functions back in Mathematica version 5… they ceased to work in version 6… faced with the prospect of rewriting them, I chased down a half-remembered idea… and discovered that there is indeed a way to get from the initial tableau – and a solution – to the tableau which represents that solution. Nevermind the row operations… we have the answer… and I want the final tableau.
There were 2 ideas going on. Mathematica itself can find the solution of a linear programming problem… so getting the solution in the textbook is trivial, and does not require stepping through the sequence of tableaux generated by the row operations.
But the bare answer provided by Mathematica lacks an awful lot of information: we want the final tableau. We don’t need it – but we really, really want it. So let me set up a small linear programming problem, and show you what I’m talking about.
A Small Linear Programming Problem
This problem comes from Loomba and Turban “Applied Programming for Management”; Holt, Rinehart, Winston, 1974, 003 078240 6. I bought the book because I thought its purpose was to explain linear programming to management – and I needed help doing that – but the book should have said “for managing”, instead.
We have three products (call them frozen beef, cubed beef, and corned beef if you want). We have three inputs (three grades of beef).
The following array says, for example, that our first output (column 1, frozen beef) requires 7.5 kilogram of grade 1, 2.5 kg of grade 2, and none of grade 3.
(Of course, we must be doing our computations for one average cow.)
Our profit – I know, it’s named c, for cost! – for each kilogram of output is ($):
subject to the constraints that we use no more inputs than we have – and our outputs are non-negative:
(You see that I used a Thread command. Go ahead, try it without!) Here’s how we ask Mathematica to solve that. I have chosen separate names for the maximum value and the of the solution:
And that’s it. We produce outputs 1 and 3 (10 and 1.8 respectively), but none of 2. Our profit is $25.9 per cow. If the answer is all we need, then there we are, done.
We could now check a couple of things. We can confirm the profit:
We can check the constraints. We consume Ax… and we have available b… so unused is b – Ax
We have 7.56 kg of grade 3 left over; we used all we had of grades 1 and 2.
After all that discussion, let me summarize the mathematics. We wish to maximize
when the take on the following values:
We’re done. We got the answer.
The Associated “Final Tableau” and the Augmented Problem
But let’s look at the final tableau presented in the book. Our solution is presented as the column headed “Quantity”…
(Ignore “Step 8” etc. It’s part of the image.)
For my purposes, the tableau has some duplicate information on the left: columns headed “program, profit” correspond to columns to the right of “quantity” (x1 and 2.5, x3 and 0.5, s3 and 0).
The column “quantity” shows more than just the values of x1 and x3 for the optimal solution. It also shows the unused amount of grade 3 (7.56). Note that the values of the relevant variables x1, x3, and s3 are “1” in the heart of the table. In fact, the columns of x1, x3, and s3 form an identity matrix. That’s not an accident.
And what are the variables ? We’ll see shortly what they are.
But if you ever seen a linear programming problem, you might recall that the number +.42 at the bottom of the column headed “x2” is a very significant number. It says that if the profit on x2 rises, but by less than $0.42, then the solution doesn’t change; you continue to not produce any of x2. (Assuming that nothing else changes.)
Let me put that another way. Your chief operating officer comes in and tells you that he can increase the profit on x2 by 15 cents per kilogram. You smile at him ruefully, shake your head, and say, “It’s got to be (a little over) 42 cents in order to change our optimal production schedule. get me 43 cents and I’ll start producing x2.”
Alternatively, if this were a cost minimization problem, and it were the costs of inputs that you were monitoring… you would know from the number at the bottom, how much a cost would have to drop, before you switched to that input.
That number tells us – every thing else being the same – that this solution remains optimal until a change in c2 is at least that large.
(For the record, we will see that the number is slightly larger than 42 cents.)
There are two other useful numbers at the bottom of that table: the +.31 and +.06 tell us how much we should be willing to pay for additional supplies of grades 1 and 2 – the two grades of which we’re using everying we’ve got. They are called the “shadow prices” of the supplies that constrain our production.
So let’s see how to get these numbers… this is why I want the final tableau. We could – and I once did – write routines that would follow the book’s row operations and work through the tableaux.
But we have the answer, and all the information contained in the initial tableau. Is there some way to use the solution to construct the final tableau?
Of course … or I wouldn’ t be posting this.
First, let’ s just introduce the s1, s2, and s3. They are called slack variables. They let us replace the inequality constraints by equalities.
I append 3 variables named to my x’s; this is just a list of names – which defines the variables to be solved for.
I now include the in the equations. Let me just add them to the A matrix – naming it As, s for slick – and also add costs to the cost vector, now called cs – I always call them costs and use c for them, but they are profits for this problem.
Now me show you the book’s initial tableau. They have begun the task of finding the second tableau, but I’m not interested in anything but the first and last.
I can have Mathematica assemble As and b…
and I can add -cs to the bottom… (the negative sign because he has one):
And I can even add some lines… this is not my favorite hobby, but they help. I’m going to do this slowly so you can see what did what. “a1” will insert the vertical line… and the additional vector of True/False in the following Grid command inserts the horizontal line…
Now I add headings…
And, having taken that long to construct the display, let me repeat the book’s initial tableau:
All I’ve done is create a nice pictorial match to the book’s initial tableau. What matter are just the numbers in As, b, and cs.
Now let’s get the solution of the new problem. We wish to maximize cs.xs
You see that s1 has been added to the first equation, converting it to an equality. We know the answer: we will use all of b1, so s1 will be zero.
Similarly for s2: we consume all of b2, so we know s2 = 0.
But for b3, where we learned that we had 7.56 kg left over, we expect that the solution will say s3 -> 7.56 .
Here’s what we tell Mathematica. As before, it is my choice to name the maximum value (vps) and the solution for and (sps):
OK, that explicitly gets me the 7.56, something I had to compute separately before. We did, of course, get the same answer: max is 25.9 when x1 = 10, x2 = 0, and x3 = 1.8.
Getting the Final Tableau, having found the optimal answer
Looking at the optimal solution, we see that answers are columns 1, 3, 6… so we extract them from the matrix As… and compute the inverse….
We’re getting a transition matrix for a change of basis. No matter what else you see me do here, this is the absolutely crucial step – the construction of is the whole point of this post.
BTW, I transposed As in order to select rows 1,3,6… then transposed back… and inverted that.
That, named Ti, is the appropriate transition matrix for getting from the initial basis to the final basis. If you don’t understand why, look at this post. In a nutshell, the extracted columns are the old components of the solution… the new components are, as I said, an identity matrix… a transition matrix maps new components to old – but I have the old components and want the new ones, so I need to use the inverse transition matrix.
We also need to extract the profits associated with each of those columns:
Then… round the numbers for printing, but not for subsequent calculations. We apply to each column of As, and call the result Af (f for final):
and also apply Ti to the column of constraints, b, getting bf.
Recall the final tableau:
We see that we have obtained the heart of all six columns under x1… s3 and the column headed “quantity”. What we don’t have yet is the bottom row.
Here’s the part I don’t understand. I’ve even seen a derivation (Strang, Linear Algebra and Its Applications, on the bibliographies page), and I’ll go take another look at it, but right now I just don’t get this – but it’s too useful not to use.
We will take that extracted vector of profits…
We post-multiply by Af – note that it’s Af not As. That we post-multiply actually seems plausible, because the profits are a row vector – a dual vector – instead of a column vector. But we’re multiplying by Af, rather than by alone – and that’s what confuses me. (Recall that . To put it in other terms, we have post-multiplied by , and then post-multiplied by As. Damned if I know why.)
Anyway, that gets us a new profit line:
That list, in fact, contains the numbers I really want: the profit on x2 must rise to 2.671111 before x2 will be in the optimal solution, i.e. will be produced. But the bottom row of the tableau shows a difference (2.67 – 2.25 = .42), so subtract cf from cs… and throw a negative sign in front of it all, as we did for the initial tableau:
The combined calculation, then, was
Incidentally, we see that the textbook was way too careless in its arithmetic: to 2 places, the shadow price (that’s what it’s called) on b2 is 0.07, not 0.06; to three places, it’s 0.067 .
Let me repeat some hard-won magic to get a nice display again.
Now I add headings…
Let’s take yet another look at the final tableau:
An almost perfect match, except for their round-off error getting .06 instead of .067 .
This summary says we would bring x2 into the solution if c2 rises .42; we know from the more detailed number that we need it to go up .421111… so to the nearest penny, we need a 43 cent rise. (All those numbers are dollars.)
We would pay approximately .31 for an additional kilo of b1, and an additional .07 for an additional kilo of b2. (We know that second number is off quite a bit: 6.7 cents is much closer.)
Now I think it’s worthwhile to review the calculations that gave us the final tableau.
We constructed a transition matrix T, by extracting 3 columns from A… namely the 3 columns holding x1, x3, and s3, which were in the optimal solution. Then we computed the inverse transition matrix, .
Those are easy, and they’re really just a change of basis. (I may change my tune when I understand what we did to the cost vector….)
Then we extract the 3 profits associated with the optimal solution. Call them css. We compute
and if we want the deltas for the final tableau, we subtract from the initial profit vector cs, and change the sign:
dcf = – (cs – cf).
From the initial numbers and the optimal solution, we constructed the final tableau, which had useful additional numbers in it.
So that’s how to get the final tableau… without doing any row-operations on the initial tableau. All we need is the optimal solution – which your textbook is finding by computing the tableaux, but Mathematica already gave us the optimal answer.
A compact version of the calculations
Now let me re-assemble all those pieces. All three calculations (for A, b, and c) could have been done with one suitably-constructed matrix. I am going to augment T:
(The column is just a “1” at the bottom; the row is the extracted profits.) Then get the inverse of that augmented matrix:
I also need to augment A, from
Now compute Thi Ahat, the inverse augmented T applied to the augmented A:
and that just did all the calculations all at once. It even gave me the optimal value down in the southest corner. Round it all… and compare it to the alternative calculation, saved as t2:
That’s the way to go. Not really the way to understand, but the way to assemble the computations. That is, instead of applying
to A and b separately, accompanied by a longer computation of cf, I augment T and A, and do one computation, applying the inverse
and I get the final tableau in one fell swoop.
Whew! That was a lot to do – so what’s new? – and if I provide another example – as I probably should – it will be in another post.