Read an Excerpt

An Illustrated Guide To Linear Programming

Dover Publications, Inc.

INTRODUCTION

{On how to get dressed, about straight lines, and the beginning of a trip through the land of Linear Programsville.}

The search for the best solution—the maximum, the minimum, or in general, the optimum solution—to a wide range of problems has entertained and intrigued man throughout the ages. Euclid described ways to find the greatest and least straight lines that can be drawn from a point to the circumference of a circle, and how to determine the parallelogram of maximum area with given perimeter. The great mathematicians of the seventeenth and eighteenth centuries developed new optimization procedures that solve complex geometric, dynamical, and physical problems, such as finding the minimum curves of revolution or the curve of quickest descent.

Recently, a new class of optimization problems has originated out of the convoluted organizational structures that permeate modern society. Our natural inclination to attack and solve such problems is manifested by such phrases as "'cost-effective," "mostest for the leastest," and "more bang for the buck." Here we are concerned with such matters as the most efficient manner in which to run an economy or a factory, the optimum deployment of aircraft that maximizes a country's chances for winning a war, or with such mundane tasks as mixing cattle feed to meet diet specifications at minimum cost. Research on how to formulate and solve such problems has led to the development of new and important optimization techniques. Among these we find the subject of this book—linear programming.

To define linear programming in nontechnical terms we can take two approaches—describe the literal meaning of the phrase linear programming or simply describe typical problems which can be formulated as linear programs. As it is quite instructional to interweave both descriptive paths, we shall do so.

In a most general sense, programming problems—linear or otherwise—are concerned with the efficient use or allocation of limited resources to meet desired objectives. Such allocation problems are central to the field of economics. However, they not only are found within industrial and corporate entities, but also arise in many guises during an individual's encounter with his day's activities.

ON GETTING DRESSED

Diddle, diddle, dumpling, my son John,
He went to bed with his stockings on;
One shoe off, one shoe on;
Diddle, diddle, dumpling, my son John.
ANONYMOUS

The first thing each morning you and I face the programming problem of getting dressed. We must select a program of action which enables us to become dressed in a manner which meets the constraints or accepted fashion rules of society—socks are not worn over shoes, but socks are worn. Our basic resource is time, and the selected program must be best in terms of how each individual interprets his expenditure of early morning time.

From a personal point of view, ignoring the "bare" essentials, my program of action involves the putting on of six items of clothes: shoes, socks, trousers, shirt, tie, and jacket. A program of action is any order in which the clothes can be put on. There are 6 × 5 × 4 × 3 × 2 × l = 720 different orderings. Many of these are not feasible programs as they do not meet the constraints of society (socks over shoes) or are impractical (tie on before shirt). Even after eliminating these infeasible solutions from consideration, I still have a number of feasible programs to contend with.

How is the final selection—the optimum decision—made? The dressing problem, like all those to be considered, has some measure of effectiveness—some basic objective—which enables me to compare the efficacy of the available feasible programs. If, in some fashion, I can compare the measures for each program, I can select the optimum one. For the dressing problem, I am concerned with minimizing the time it takes to get dressed. This is my measure of effectiveness—the objective function in programming terminology— with which I can compare the various feasible orderings of clothes. Admittedly, I have not solved this problem with stopwatch accuracy, but over the years, my optimum solution has been the following ordering: socks, shirt, trousers, tie, shoes, jacket. This is my optimum solution—it minimizes the time to get dressed within the fashion constraints of society. Someone else with a different objective function—minimize the opening and closing of drawers, i.e., minimize the early morning noise—might select a different optimum solution.

The dressing problem, although not a linear-programming problem, typifies programming problems in that it has many possible solutions. If there were only one feasible solution, there would really not be any problem or any fun in solving it. There is also some objective to be optimized which enables us to select at least one of the feasible solutions to be the optimum. The finding of the feasible solutions and the determination of an optimal one represents the computational aspects of programming problems which are discussed in later sections.

As we shall concern ourselves only with linear-programming problems, it should be stressed that linear programs are a special subset of general programming problems (usually called mathematical programming) in that the mathematical description of linear programs can be written in terms of linear or straight-line relationships. For example, if one pound of coffee costs $1.00, and the seller offers no quantity discount, the total cost is directly proportional to the amount purchased; i.e., it is a straight-line relationship, as shown in Figure 1. On the other hand, if the seller allowed 10 cents off for the second pound purchased, 20 for the third, etc., up to the fifth pound, and 50 cents per pound afterwards, the cost curve would be nonlinear, as shown in Figure 2. In sum, linear-programming problems are those programming problems whose relationships—the constraints of the problem and the objective function—can be represented mathematically as linear relationships. Although this appears to be quite restrictive, many important problems have this simplifying feature.

Programming problems, especially linear-programming problems, arise in a wide variety of settings. There are standard applications of programming techniques found in the areas of agriculture, petrochemicals, paper manufacturing, transportation, production scheduling and inventory control, military and defense, engineering, economics, to cite just a few. A bibliography of applications is given in the Appendix. We shall deal with a few such applications in order to develop the fundamentals of linear programming. But first—as a slight digression—we must discuss the place of linear programming within the scheme of modern-day scientific decision-making, i.e., operations research or management science.

OPERATIONS RESEARCH AND MODELS

When we mean to build,
We first survey the plot, then draw the model;
And when we see the figure of the house,
Then must we rate the cost of the erection.
SHAKESPEARE

Definitions of operations research (OR), like advice to the lovelorn, have always been in demand and are plentiful. They range from the detailed one of "operations research is the application of scientific techniques, tools, and methodology to problems involving the operations of a system so as to provide those in control of the system with optimum solutions to the problems," to the succinct ones of "operations research is quantitative common sense" or "research into operations." For our needs, we consider OR to be the application of scientific techniques to decision problems. What interests us most, however, is not what OR claims to be, but its methodology.

The phases of an OR project can be delineated into six overlapping and somewhat ill-defined stages. For most purposes they are:

* Formulating the problem

* Developing a mathematical model to represent the system under study

* Deriving a solution from the model

* Testing the model and solution

* Establishing controls over the solution

* Putting the solution to work

Here we have introduced the concept of a mathematical model, which we shall see is central to the methodology of OR. These phases of an OR project can be viewed as accomplishing the following: For any problem we need to define the broad objectives and goals of the system—examine the environment we are working in—become familiar with the jargon, the people and things associated with the problem—determine the alternative courses of action available to the decision-maker—develop some statement, verbal or otherwise, of the problem to be investigated; translate the problem into a suitable logical or mathematical model which relates the variables of the problem by realistic constraints and a measure of effectiveness; find a solution which optimizes the measure of effectiveness, i.e., a feasible and optimum solution; compare the model's solution against reality to determine if we have actually formulated and solved the real-world problem we started with; determine when the real-world situation changes and the reflection of such changes into the mathematical model; and most important, implementation—putting the solution into operation (not just filing a report) and observing the behavior of the solution in a realistic setting. As our ability to develop precise mathematical models of operational problems is not a highly developed science—most people believe it to be an art—we must be sensitive to discrepancies in the solution and feed back to the model refinements that will cause future solutions to be more realistic and accurate.

Models have been classified into three basic types. The iconic model looks like what it is supposed to represent. It could be an architectural model of an apartment complex, a planetarium representing the celestial sphere, or the idealization of the typical housewife as demonstrated by the designer's fashion model. The analogue model relates the properties of the entity being modeled with other properties that are both descriptive and meaningful. For example, the concept of temperature is described by a graph in which a degree is equivalent to a specified unit of distance. Finally, the symbolic model or the mathematical/logical model represents a symbolic description of the process or problem under investigation. Einstein's famous equation e = mc2 states, in symbols, that the energy e contained in a mass m is equal to the product of the mass and c2, the square of the velocity of light. The mathematical model represents the translation of the statement of the problem into quantitative terms. As we shall see, the model of a linear program is a mathematical one. In programming terms, the mathematical model represents a set of relationships among the variables, resources, constraints, and objective function (measure of effectiveness). The mathematical model is central to the methodology of OR; it offers understanding of the process and problem under investigation; it provides a vehicle for the evaluation and comparison of alternative solutions; it enables us to evaluate the effects of a change of one variable on all the other variables; and finally, and somewhat mystically, it provides us with a quantitative basis to sharpen and evaluate our intuition of the process under investigation.

It should be stressed that the mathematical model is the prime distinguishing feature of OR, mathematical decision-making, or management science. Mathematical models enable us to bring some semblance of scientific methodology to areas of decision-making heretofore characterized by intuition and experience. Mathematical models abound in the areas of inventory control, allocation of resources, queuing, competitive situations, transportation, industrial processes, and many more.

The role of the mathematical model in OR and decision-making can be summed diagrammatically, as in Figure 3. After the statement of the problem, which includes the choice of the all-important measure of effectiveness, the functional form of the mathematical model is determined. As this requires specifying how the variables are related with associated data, certain experiments designed to aid the structuring of the correct form must be carried out. In some instances, this experimentation could be just the opening of the accounting ledger to gather the needed information; in others, it might call for complex and expensive efforts. In any event, the results are fed back into the structure of the model as shown in Figure 3.

It is by means of the mathematical model that the problem is connected with its proposed solution. The major activity here is the devising of alternative ways of solving the problem, using the mathematical model to evaluate a proposed solution and the measure of effectiveness to choose a solution to implement. For some problems the development of a set of feasible alternative solutions is automatically accomplished by computation involving the related mathematical model. This is the case in linear programming. For others, ingenuity and innovation are a must in proposing alternatives. As the implementation of a solution can affect the structure of the mathematical model, we have a feedback loop from the solution side to the problem side, and the process continues. We illustrate the above by describing a particular problem and developing its mathematical model, which in this case is a linear-programming model.

THE TRANSPORTATION PROBLEM

For my part, I travel not to go anywhere,
but to go. I travel for travel's sake.
The great affair is to move.
ROBERT LOUIS STEVENSON

A refrigerator manufacturer has two factories which supply his three retail stores. At the beginning of each month, the manufacturer receives from each store manager a list of unfilled sales which must be filled in the coming month by new production. This set of requirements represents the total number of new refrigerators that must be produced by the two factories. To simplify the discussion, we assume the manufacturer has enough resources—manpower, raw material, etc.—to fulfill the requirements, and in this instance, he does not have any over production; i.e., there is no facility for storage. The production process itself could possibly be treated via a mathematical model, but here our interests are in a different area. The manufacturer's store one, denoted by S1, requires 10 refrigerators, S2 requires 8, and S3 requires 7, for a total of 25 refrigerators. He has decided to produce 11 at factory one, F1, and the remaining 14 at F2. The problem we wish to consider is how many refrigerators should be shipped from each factory to each store so as to minimize the total cost of transporting the refrigerators from the factories to the stores. The basic form of this problem, termed the transportation problem, is one of the earliest and most widely used formulations of linear programming.

We need additional information concerning transportation restrictions and costs. It is assumed that it is possible to ship any specified number of refrigerators from each factory to any store; i.e., a transportation link—rail, truck, or other mode—connects any factory to all stores. We also assume knowledge of the costs of shipping one refrigerator from a factory to a store. Here we must make a linearity assumption about these costs which is quite critical—and in some instances quite debatable. This linearity or proportionality assumption requires that if the cost of shipping one refrigerator from F1 to S1is $10, then the cost of shipping two refrigerators is $20, for three the cost is $30, and so on. We can argue about this assumption based on real-world experience. If it costs $100 to hire a truck to deliver one refrigerator, the unit cost for two refrigerators (excluding handling costs) would be $50, for three it would be $33 1/3—a nonlinear cost relationship. As another example, we note that parcel post rates (including insurance) for a $3.80 gift from Atlantic City have the following table:

[TABLE OMITTED]

The graph of these rates versus mileage illustrates the nonlinearity of the postal rates, Figure 4. We see that the graph is not continuous in that it is made up of vertical and disconnected segments. If the government allowed the postal rate to vary by the exact mileage, the nonlinear, but connected, cost graph would be the dotted line. In most transportation situations, if the cost is not linear, a good approximation can be obtained by averaging costs used by previous solutions.

---

Excerpted from An Illustrated Guide To Linear Programming by Saul I. Gass, W F. McWilliam. Copyright © 1970 Saul I. Gass. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---