glicksman notes linear programming

Linear Programming and the Theory of Games by Abraham Glicksman PhL 11.26.04 This is a 1963 blue paperback book that has been quietly sitting on my shelf probably since about 1963. I cannot recall in what context I bought the book. Maybe just "for fun". Today I am interested in the Simplex Method because Scheid has failed in his explanation of it, at least to me. // This book did indeed explain the method, and it is a good book. Nothing about dimensions above 2D, however. Preface: Author claims this is the simplest book on this subject that has any meat to it. He is a high-school teacher in the Bronx, and claims to have talked to Dantzig to get reprints. Most references are to this book, which is the same year as Glickman's book. Dantzig (born 1914 so today he is age ~ 90, below are comments at his 80th birthday party: http://www.stanford.edu/group/SOL/dantzig.html And here are some early references: Dantzig, G. B. Linear Programming and Extensions. Princeton, New Jersey: Princeton University Press, 1963  Dantzig, G.B., "Programming interdependent activities, II, mathematical model," Econometrica, vol. 17, pp. 200-211, 1949. Original paper of the general statement of the linear programming model. Shows connection with Koopmans' transportation model, Stigler's diet model and Leontief's I/O model.  Dantzig, G.B., "Maximization of linear function of variables subject to linear inequalities," in Activity Analysis of Production and Allocation (T.C. Koopmans ed.), Wiley, NY 1951. The original paper. It includes a time model that is a military manpower scheduling model.  Dantzig, G.B., "Application of the simplex method to a transportation problem," (pp. 359-373) in Activity Analysis of Production and Allocation (T.C. Koopmans ed.), Wiley, NY, 1951.  Dantzig, G.B., "A Comment on Edie's 'Traffic Delays at Toll Booths,'" Operations Research, vol. 2, no. 3, 1954. Develops the personnel scheduling LP using the set covering model.  Dantzig, G.B., "Linear programming under uncertainty," Management Science, vol. 1, 1955, pp. 197-206. Two stage stochastic programming. Uses expected value in the objective function. Part I: Elementary Aspects of Linear Programming Comment that Dantzig did it in 1947, but Russian Kantorovich did it in 1939. This chapter talks about the general idea of graphing the inequalities in 2D. The TV problem on page 18 is interesting. It shows that you might have conflicting things to maximize, but if there is a full edge solution to one problem, then you should take the vertex that mimimizes the miss of the other goal. Part II: Convex Sets and the Fundamental Extreme Point Theorem Examples of convex and non-convex in 2D page 29. Lots of simple line math for those high schoolers. It is proved that the intersection of a set of half planes creates a convex set (at least it is proved in 2D, see page 40 for the quote). The thing you maximize ax + by is called a linear form. The theorem of the title is stated and proven on page 52, in 2D, picture on page 53. Idea is that as you move your max line, the best situation is just grazing the convex volume. Part III: The Simplex Method in Linear Programming I have a lot of notes in this section because I was learning it here for the first time. 1. Preliminaries. A guy named George Dantzig discovered this method in 1947 and it is a big deal. 2. The Gauss-Jordan Complete Elimination Procedure. In Scheid we took a square problem and cleared out the lower triangle and called that Gauss elimination. Here we something a little strange. We have a 3x3 system with variables u,v,w called the basic variables, then we have two more variables x,y which are really "parameters". We could think of this as a 3x3 system and we could incorporate the x,y stuff off on the right side with the rest of the "constant" stuff. Now in Scheid page 338 top we got the system into upper triangular form doing Gauss elimination. that was good enough to let us quickly solve the problem. But I now see that we could have kept going. For example, we could subtract the 3rd equation from the second so the new second would be x2 = -36. Basically with a few more fiddlings, we could have made the system completely diagonal, and in that case the right column becomes the solution. Why did he not do that I wonder. So now in this book, this is done, and we get things diagonal, and this is called Gauss-Jordan elimination. I have confirmed this name looking on the web. The Jordan part is this extra set of steps to get it into diagonal form. Also, things are scaled so those diagonal elements are all 1's. So, this section shows how you do the Gauss-Jordan, but it has an extra twist. In addition to the rightmost "constant" column, we separate out the x and y contributions into their own columns. Right now, I just think of these as other constants we are tracking along. Fine. So we arrive at the diagonal form on page 63 and we know that if x = y = 0, the rightmost column gives the solution to the problem for the basic variables u,v,w. This is called the basic solution. So far so good. The u,v,w variables are called the basic variables, while x,y are the non-basic variables. 3. The Extended Simplex Tableau. Here we are given a nice sample problem from the real world, and we summarize it on the top of page 64. There are n = 3 variables and m = 3 inequalities. We add three slack variables and restate the problem. Now comes something new! We take the thing to be maximized and add it to our matrix as shown. We now have a 4th new variable M, and we seek a solution with max M. So our problem is now cleanly restated on the lower half of page 64. Feasible solutions are that that lie inside the inequality boundary AND which solve the equations. The optimal of these feasible solutions is the one that maximizes M. Now we write out our very first table on page 65 and we put columns for the original problem variables x,y,z and the slack variables u,v,w and the extra variable M. We observe that we have a 4x4 identity matrix sitting there, and this tells us that we have a basic solution! Think now of x,y,z as parameters, and think of u,v,w,M as the basic variables. The basic solution occurs when x=y=z=0 and we get u=100 v=210 w=150 and M=0. We know this is not optimal because any different x,y,z will give a larger M! Suppose we try then to increase z but keep solving the equations. This reduces u,v and w as shown. So let's increase z (Scheid's p I assume) until one of these hits 0. That means z = 52.5. We have now reached another solution to our equations! It is a better solution because M is larger now! I am starting to see the light, this guy has done his job. Look again at the table on page 65. We look in that last row for the largest negative number which is -6 and that is our column of interest. We want to increase z for the most "profit". If we increase z by one unit, it does us more good than increasing x or y by one unit. As we increase z, we have said that u,v and w get reduced. Which of these will hit the value 0 first? It is the one with the smallest ratio of a positive number in the z column divided by the rightmost column. Zeros and negative numbers don't cause such a boundary hit anywhere. That is why we select the 4 in the z column as our pivot, the ratio 52.5 is smaller than the ratio 100. Now, we are going to do Gauss-Jordan with this pivot. This means we add multiples of this row to other rows to clear out the z column. When we do this, we see that we are going to "mess up" the v column because it is the one that has a 1 in the pivot row!! So after doing the G-J, we end up with the picture on page 67 top. Yes, we have messed up the v column, but we have made the z column a new unit vector. We have exchanged one unit vector for another, as Scheid was saying. We now change the labels over in the stub section. Those numbers are interpreted as applying to the variables that have unit vectors in the row shown. The constant column gives the values of these variables in a basic solution. We switch the v label to a z label. We see our z = 52.5, we see that M has boosted up to M=315 from 0, a vast improvement. Now we look in the bottom row for the largest negative number. The -1 says we should now try to increase variable y. The same ratio analysis now shows that we want our pivot to be the 2 in the y column. We do it, and now we have exchanged w and y. M is now up to 390. Since the bottom row no longer has negative numbers, we are done! The optimal solution has z = 15, y = 75 and we still have x = 0 because we never moved x at all from the previous solutions. I now have a better feel for what Scheid is trying to do, maybe I can decode it now with this extra boost from Gliscksman. Scheid page 364. The matrix he shows mid page is like Glicksman page 65. We have unit vectors on the right for all the slack variables. The M column is not shown. Scheid does not yet show the bottom M row. Review Question #1: After we decide that we could go 52.5 units in the z direction, why do we want to make the z column be a unit vector? Answer: We started off with this BFS: x=0 y=0 z=0 u=100 v=215 w=150 M=0. We had unit vectors on the last 4, so we could just read these values off from the stub column. We are now going to a new solution which is x=0 y=0 z=52.5 u=xxx v=xxx w=xxx M=xxx. We know manually how to deduce the xxx values shown here by writing out the equations. But the Simplex table will also keep track of this for us, at least for some of these values. If we make z be a unit vector (4 components, we include the last row), we will then get the values of z, M, and two of the three slack variables. If we know everything except one variable, we can always compute that one variable. So the answer is that we want to get the table into a form that shows z = 52.5 clearly, and we are willing to sacrifice one of the slack variable unit vectors to this end. This of course puts a 0 in the bottom row in the z column, and I think I can show that this will never change. Since the M column never changes, we know that it will always be the last unit vector, and it never gets swapped with anything. Review Question #2: When we do our pivot thing for z to get z be a unit vector, why do we act on the last row as well as the other rows? Answer: The last row is on an equal footing as the other rows in the enlarged space (enlarged by the 3 slack variables and the M variable) if we think of it in this manner: -5x -4y -6z + cuu + cvv + cww +M = 0. where these new cu type things are all 0's at first. These are just all the numbers from the bottom row. Now I see why Scheid introduces cj beyond the first three original coordinates. So, in our enlarged space of 4 equations and 7 variables, if we act on the last row the same as the others, we don't change our system at all! More Clarity is Needed Let's write out our system in full, instead of doing the shortcut, because I cannot think about something I can only see a shortcut for. Here we go: For our starting position, we specified x = 0, y = 0, z = 0. This means that, when you do the matrix product above, none of the numbers in the leftmost three columns matter. They will only be multiplied against x,y,z all zero. This being the case, we see at once that we can interpret the RHS as the solution value for u,v,w and M. (this is a basic solution, and x,y,z are the NON-basic variables) In general, when you have four unit vectors corresponding to 4 of the 7 variables, you must make sure that the other three variables are set to 0, only then can you interpret the RHS as the solution values of those four variables, and the other three are 0. The above picture shows our starting position. The three slack variables have max values equal to the constants of the inequalities since x=y=z=0 for the opening solution. Now, when we do our pivot on the 4, we will make the z column be a unit vector and we know this will mess up the v column. Therefore, in our new solution, we require that v = 0. So we swap z=0 with v=0. Here is the new situation, We are now assuming that x=0 and y=0 still, and we have now added v = 0. This ensures the solution values shown, and all not shown are 0. Since we arrived at this new unit vector situation by legal row transformations, our system of equations is still satisfied by this solution. The last equation reads M = 315 for example. In the next step, we are going to run y out from 0 to 75. Our new equation will then have y = 75 and we will swap with unit vector for w, so we will have w=0. So the solution on bottom of page 67 has x=0, v=0 and w=0. We then see the values for u,z,y,M. I wonder if this is true: as we decide to shoot y out from 0 to 75, we are also running w from 150 as shown above down to 0. I have the feeling we are running along a boundary of our hypervolume when we do this. We are running from one "vertex" to a different "vertex". As we do this run, z and u change as well, so we are surely on some surface in the hypervolume. How do we know that we are at a new "vertex"? Because we have x = 0, y=0 and v=0. In this problem, a vertex is a 3D thing. Question: We seem to be in a 7-dimensional space, but we also seem to have only 4 basis vectors that are independent. So what space are we really in here? What is the vector space interpretation of what we are doing here? { There are really two spaces E3 and E4 that you can think about, see notes elsewhere.} Answer: Suppose we forget the last row and we have three equations. If we choose as our basis the set of axes (u,v,w), we can pick a point in our E3 space by selecting a coordinate (u,v,w). We can then solve the three equations to get (x,y,z). Therefore, these last variables are not "independent". They are really all determined by (u,v,w). So I would say we have a space E3 where 3 is the number of constraint inequalities that we have, and this was called m in Scheid. So our real space is Em . We could in theory have lots of constraints, perhaps 9 constraints. We then have 9 equations and 9 slack variables and our space is then E9 . We can start with 9 unit vectors along the slack variable axes. But we now have 9 equations containing x,y and z, so it is not true that we can "solve" for x,y,z. Any 3 of the equations might give a different solution. { It is true that the mapping backwards from E9 to E3 is many to one, see notes elsewhere! } A comment before I continued on. So I am back at square zero. I have a very dim idea of what is happening here, but I can in no way say that I "understand" the simplex method. It is too hard for me right now. I am a mere beginner and this was day 1. I don't really need to know this subject. I would have learned it if it took < 1 day, but that was not the case. So we can just put it on the rainy day list and continue on with Scheid. After all, this is not really related to problems I intend to be working on. 4. The use of artificial variables. When you have or = boundaries, you need to add variables in addition to the slack variables. The reason is that the usual starting point (x,y) = (0,0) is not a vertex. The method described here is called the Big-M method in a paper I downloaded on this subject, and this involves adding the new variables and modifying the "objective" by adding a huge offset to it to force your answer to have all the artificial variables zero. I think that paper is a better place than this to study this subject. You start off with your unit vectors in the columns of these artificial variables, then you do swaps to move these out of "the basis" and that will get you to a starting point for normal simplex iterations, ie, it will get you do a vertex of the polygon. 5. The condensed simplex tableau. I did not bother with this, but you remove some info. 6. Degeneracy. This is some kind of problem you can encounter doing simplex, don't care. Part IV: Elementary Aspects of the Theory of Games 1. Discussion of two players flipping coins and having a payoff matrix. The idea here is not clearly stated in Scheid. You have two smart players that can set theory own strategies for doing heads or tales, ie, each can work with some (a,b) like (1/3, 2/3). Suppose each player adopts a strategy and they play for a while. If player A sees he is losing, he will change his strategy because he is smart, same for B. The question is: what is in fact the best strategy for each to pursue so each does as best he can? Depending on the numbers in the matrix, it may be possible for one player to win, this is then not a fair game. All he can do is optimize to minimize his loss. Part V: Matrix Games and Linear Programming. 1. Each player sees a linear programming problem and can solve it using the simplex method. In A's problem, he has to assume the worst case for what B will do, because eventually B will find and stabilize on his best strategy. So in the equations for A, he will take the worst case of several equations to make his inequalities. Player A works with a maximize winnings strategy (if game favors him), and player B works with a minimize loss strategy. These appear to be two completely unrelated problems, but the famous Minimax Theorem ( von Neumann 1928, life 1903-1957) says that the optimal solution to both problems is the same! 2. Here author shows the Duality Theorem ( perhaps Lemke 1954) and the fact that the two games above are dual to each other. In general, a problem and its dual have the same solution. So the Matrix Game problem's Minimax theorem is just a special case of the Fundamental Duality Theorem of Linear Programming. References. Dantzig's 1963 book is missing because it had not come out yet! Index Garbage duplicate pages. For some reason, the end of the book from page 119 forward is duplicated. I leave them in and tape them off, don't want to risk wrecking the binding.