Computer-assisted Formulation of 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 lgebraic 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 program (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 linear programming problem 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 analyse some properties of the linear program prior to actually generating a matrix.