An Illustrated Guide to Linear Programming

Saul I. Gass

• Publisher: Dover Publications
• Year: 2013
• ISBN:
  9780486319605
• Topic: Informatica
• Subtopic: Informatica generale

"I would not hesitate to recommend the book." — Industrial Engineering
Linear programming is an extremely effective problem-solving tool, with applications in business, agriculture, government, manufacturing, transportation, engineering, and many other areas. This very readable book presents an elementary introduction to linear programming in a refreshing, often humorous style.
Requiring no math beyond high-school algebra, the book shows how linear programming can help anyone reach the optimum solution for a host of diverse problems. Chapter One introduces the basic concepts of linear programming and discusses its relationship to other mathematical models. Chapter Two discusses the formulation of linear-programming problems, including detailed treatment of problems involving diet, catering, assignment, and activity analysis. Chapter Three briefly introduces solution techniques for linear-programming problems, emphasizing the graphical approach. The final chapter describes and formulates a number of important applications, including network problems, traveling-salesman problems and the relationship between linear programming and the theory of games.
Finally, a useful appendix offers precise statements of definitions, theorems and techniques, as well as additional computational procedures. Enlivened with over 70 excellent illustrations, this book represents a very accessible introduction to basic linear programming.

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.

Figure 1

Figure 2

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 cel...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Preface
• Contents
• 1: Introduction
• 2: Formulation of Problems
• 3: Solution of Problems
• 4: Linear Potpourri
• Mathematical Appendix and Summary of Applications
• References
• Bibliography
• Index