Lp Simplex

So this is the simplex algorithm that Dantzig developed for the USAF. :sigh: here we go. As with the rest of the LP notes, pretty much taking a lot of this right from U. Wash. Math 407.

Before simplex must solve with Gaussian elimination? Use slack variables to assign the system of equations to. Basically if we have a system:

$$x_2 + x_3 + x_4 \le 5$$
We give it a slack variable of, say, x_5 and then we assign it as follows: $$x_5 = x_2 + x_3 + x_4 - 5 \le 0$$

You also give a slack variable to the objective function (what you’re minimizing/maximizing).

Once you’ve assigned all your slack variables, this is called your dictionary.

There was supposed to be a funny comic here. But you have a weird browser so you get nothing.

Now throw your stuff back into a form where all the $x_s$ are on one side and they equal your $b_s$ (like 5 in the above). See slide 17 of the simplex1 notes in the link at the top if you don’t get it. Now you have what’s called an augmented matrix or simplex tableau.

The slack (decision variables) that we added before? The ones on the left hand side of the simplex tableau/dictionary. Yeah, well those are now called the basic variables (i.e. $x_5$ in the second eq. above) and the ones in the center (i.e. $x_2, x_3, x_4$ of the first equation I just threw out there) are called the nonbasic variables.

So to get the basic solution, we basically just set the basic variables to 0 and solve the system of equations. These solutions are actually called the basic feasible solutions. The associated dictionary is said to be the feasible dictionary and the LP is said to have feasible origin.

The Grand Strategy

Really? Pivoting?

So the grand strategy is literally to take one nonbasic variable at a time and increase it as much as possible while keeping all other variables non-negative. I’m not gonna write out the example because it’s long. Check out Slide #41 on the simplex1 slides of the UWash course. If the link gets taken down for some reason and you actually are reading these notes for whatever reason, post a comment and I’ll either type up the example or just send you the slides. Basically you’re trying to make it so that the basic variables have to have a negative coefficient and then you move them to the RHS, and then move the currently pivoting variable to the LHS. Until all the variables in the z equation have negative coefficients? At which point the BFS is optimal? And the optimal value is the number next to the coefficients. For example, in the following:

$$z = 13 - x_4 - 3x_2 - x_6$$

The optimal value is $z=16$ and now you also have another feasible dictionary. The process of moving from one feasible dictionary to another is called simplex pivoting. The pivoting process above is called simplex pivoting. “A pivot corresponds to doing Gauss-Jordan elimination on the column in the simplex tableau (augmented matrix) corresponding to the incoming variable.” You can actually then apply simplex pivoting right on the simplex tableau. The UW slides have a really good example of this starting on slide 96. It’s very very clear. Thank you James V. Burke!!

Written on October 4, 2014