Optimization Modeling with Spreadsheets, 3rd Edition

3 LINEAR PROGRAMMING: NETWORK MODELS

In the previous chapter, we examined allocation, covering, and blending models—three basic structures frequently encountered in linear programming applications. A fourth common structure is the network model, and we devote a separate chapter to it because of its distinctive nature. The network model describes configurations of flow in a connected system, where the flow might involve material, or people, or funds, etc. These configurations are conveniently described with flow diagrams, which help in the development of valid spreadsheet models. The possibility of doing some of the model building with a diagram makes network models a special category of linear programs.

The flow diagram is a modeling tool in its own right, and we can use it as a visual aid or an auditing device. Used as a visual aid, the flow diagram is an accessory, providing a picture of the problem structure to assist us in our main task, which is developing the spreadsheet representation of the linear program. In this role, the flow diagram is a preliminary step; it helps us build the spreadsheet model, and once we’ve done that, we may no longer need the diagram. Alternatively, used as an auditing device, the flow diagram allows us to translate a network picture directly into an algebraic formulation and vice versa. This approach integrates the flow diagram with the spreadsheet model. In this role, the diagram allows us to develop a model on two fronts simultaneously, ...