PHPSimplex

«Consider the problem of assigning 70 men to 70 jobs. An 'activity' consists of assigning the i-th man to the j-th job. The restrictions are (a) that there are 70 men, each of whom must be assigned, and (b) that all of the jobs, also 70, must be filled. The level of an activity is either 1, meaning it will be used, or 0, meaning it willnot. Thus there are 2 x 70, or 140, restrictions and 70 x 70, or 4900, activities with 4900 corresponding zero-one decision variables. Unfortunately there are also 70 factorial permutations, or ways to make the assignments. The problem is to compare 70 factorial ways and to select the one which is optimal, or 'best' by some criterion.»

«Now in this example 70 factorial is a very big number. To get some idea of how big, suppose we had had an IBM main-frame computer available at the time of the Big Bang fifteen million years ago. Would itbetween then and now have been able to examine all the possible solutions? No! But suppose that an even more powerful computer had been available, one that could have examined one billion assignments per second. The answer would still be no. Even if the Earth were filled with nanosecond speed computers,all working in parallel, the answer would still be no. If,however, there were ten Earths, all filled with nanosecond speed computers, all programmed in parallel from the time of the Big Bang until the sun grows cold, then perhaps the answer would be yes. The remarkable thing is that the simplex method with the aid of a modern computer can solve this problem in a split second.»

«When the planning problem was first formulated for the Air Force, the very notion of an objective function, the idea of a sharply defined goal, was nonexistent. Of course we paid lip service to the concept of a goal. In the military setting I often heard it said, 'Our goal is to win the war'. In a business setting one would hear, 'Our goal is to make a profit'. But you could never find any direct relationship between the stated goal and the actions to achieve the goal.»

«If you looked closely at the next step, you would find that some leader in his conceit had promulgated a bunch of ground rules to guide the way to the goal. This is a far cry from honestly looking at all alternative combinations of actions across the board and picking the best combination. Those in charge often do a hand-wave and say, 'I've considered all the alternatives', but this is so much garbage. They couldn't possibly look at all possible combinations. Before 1947 the possibility that there could be a tool like linear programming that would enable one to examine millions of combinations was inconceivable. There was no algorithm or computational tool for doing so.»

«I didn't discover the linear programming model all in a flash. It evolved. About a whole year was spent deciding whether my model could be used to formulate practical scheduling problems. Planning and scheduling, as you know, were carried out on a vast scale during the war. Running the Air Force was the equivalent of running the economy of a whole nation. Hundreds of thousands of people were involved in the process. The logistics were on a scale that is impossible to convey to an outsider. My colleague Marshall Wood and I reviewed thousands of situations drawn from our wartime experience.»

«The ground rules used in planning were expressed in a completely different format from the way we now formulate a linear program. What we did was review these rules one by one and demonstrate that almost all could be reformulated acceptably in linear programming format. Not all. In some cases discreteness and nonconvexity also had to be taken into account.»

«When I first formulated my linear programming model, I did so without an objective function or goal. I struggled for a while with adding ground rules for selecting from the feasible solutions one that was in some sense 'optimal'. But I soon abandoned this approach and replaced it with an objective function to be maximized. The model I formulated was not specialized to the military. It could be applied to all kinds of planning problems-all one had to do was change the names of the columns and the rows, and it was applicable to an economic planning problem or to an industrial planning problem.»