Analyzing Decomposition Procedures in LP and Unraveling for the Two Person Zero Sum Game and Transportation Problems

2. Literature Review

Over recent decades, LPs are one of the greatest successes to emerge from operations research and management science. It is well developed and widely used. The LP problem consists of a linear objective function that is to be maximized or minimized while subject to a finite number of linear constraints. The coordinating program generates at each cycle a new objective form for each part, and each part generates in turn (from its optimal basic feasible solutions) new activities (columns) for the interconnecting program. LP arose as a mathematical model developed during World War II to analyze expenditures and returns such that it reduces costs to the army and increases losses to the enemy. It was kept secret until 1947. After World War II, George Dantzig, a member of the US Air force, developed the simplex method of optimization in 1947, a procedure used in many mathematical and economical fields. John von Neumann, who developed the theory of the duality in the same year, and Leonid Kantorovich, a Russian mathematician who used similar techniques in economics before Dantzig and won the Nobel Prize in 1975 in economics (Dantzig & Wolfe 1961). This leads to a generalization of the Simplex Algorithm, for which the decomposition procedure becomes a special case. Postwar, many industries used this model in their daily planning.