THE SCIENCE AND ART OF FORMULATING LINEAR PROGRAMS

Abstract

This paper describes the philosophy underlying the development of an intelligent system to assist in the formulation of large linear programs. The LPFORM system allows users to state their problem using a graphical rather than an algebraic representation. A major objective of the system is to automate the bookkeeping involved in the development of large systems. It has expertise related to the structure of many of the common forms of linear programs (e.g. transportation, product-mix and blending problems) and of how these prototypes may be combined into more complex systems. Our approach involves characterizing the common forms of LP problems according to whether they are transformations in place, time or form. We show how LPFORM uses knowledge about the structure and meaning of linear programs to construct a correct tableau. Using the symbolic capabilities of artificial intelligence languages, we can manipulate and analyze some properties of the LP prior to actually generating a matrix.