Linear Programming in Industry

A. Planning Company Operations: The General Problem At more or less regular intervals, the management of an industrial enter­ prise is confronted with the problem of planning operations for a coming period. Within this category of management problems falls not only the overall planning of the company's aggregate production but problems of a more limited nature such as, for example, figuring the least-cost combina­ tion of raw materials for given output or the optimal transportation schedule. Any such problem of production planning is most rationally solved in two stages: (i) The first stage is to determine the feasible alternatives. For example, what alternative production schedules are at all compatible with the given capacity limitations? What combinations of raw materials satisfy the given quality specifications for the products? etc. The data required for solving this part of the problem are largely of a technological nature. (ii) The second is to select from among these alternatives one which is economically optimal: for example, the aggregate production programme which will lead to maximum profit, or the least-cost combination of raw materials. This is where the economist comes in; indeed, any economic problem is concerned with making a choice be. tween alternatives, using some criterion of optimal utilization of resources.

I. Introduction. - A. Planning Company Operations: The General Problem. - B. Linear Planning Models. - C. A Simple Example. - II. Elements of the Mathematical Theory of Linear Programming. - A. The Fundamental Theorem. - B. The Simplex Method and the Simplex Criterion. - III. A Practical Example. - IV. Industrial Applications. - A. Blending Problems. - B. Optimal Utilization of Machine Capacities. - C. Inventory Problems. - D. Transportation Problems. - E. Linear Investment Planning. - V. Computational Procedures for Solving Linear Programming Problems. - A. The Simplex Method. - B. The Simplex Tableau. - C. Alternate Optima and Second-Best Solutions. - D. Computational Short Cuts. - E. The Case of Degeneracy. - F. Procedure for Solving Transportation Problems. - VI. Duality in Linear Programming. - A. The Duality Theorem. - B. Economic Interpretation of the Dual. - C. The Dual Simplex Method. - VII. Sensitivity Analysis and Parametric Programming. - A. Sensitivity Analysis. - B. A Concrete Example of Sensitivity Analysis. - C. Parametric Linear Programming. - VIII. Integer Linear Programming. - A. Integer Programming and Solution by Rounding. - B. Solution by Cuts. Pure Case. - C. Solution by Cuts. Mixed Case. - D. Solution by a Branch-and-Bound Procedure. - E. O 1 Programming. - F. Computer Solution. - IX. Decomposition. - A. Decomposition and Decentralized Planning. - B. Decomposition by Direct Allocation. - C. Decomposition by Shadow Prices. - X. Appendix. - A. Proof of the Fundamental Theorem. - B. The Simplex Criterion. - C. The Simplex Algorithm. - D. Proof of the Duality Theorem. - E. Gomory s Algorithms for Integer Programming. - F. A Decomposition Theorem. - References.