Dr. Saul I. Gass - An Illustrated Guide to Linear Programming

AN ILLUSTRATED GUIDE
TO LINEAR PROGRAMMING

by Saul I. Gass

College of Business and Management
University of Maryland

Illustrated by W F. McWilliam

DOVER PUBLICATIONS, INC., New York

Copyright 1970 by Saul I. Gass.

All rights reserved.

This Dover edition, first published in 1990, is an unabridged, slightly corrected republication of the work first published by the McGraw-Hill Book Company, New York, 1970.

Library of Congress Cataloging-in-Publication Data

Gass, Saul I.

An illustrated guide to linear programming / by Saul I. Gass ; illustrated by W. F. Mc William.

p. cm.

Reprint. Originally published: New York : McGraw-Hill, 1970.

Includes bibliographical references.

ISBN 0-486-26258-8

1. Linear programming. I. Title.

T57.74.G28 1990 89-25752

519.72dc20 CIP

Manufactured in the United States by Courier Corporation
26258807
www.doverpublications.com

Do not try to satisfy your vanity by teaching a
great many things. Awake their curiosity. It is
enough to open their minds, do not overload them.
Put there just a spark. If there is some good
inflammable stuff, it will catch fire.

ANATOLE FRANCE

To Ron and Joyce,
who have the spark.

PREFACE

The beginnings of all things are small.
CICERO

I NTEREST IN SCIENTIFIC MANAGEMENT and the related arsenal of technical weaponry encompasses a rather wide and ever-increasing audience. Since the field of linear programming has been a key element in the burgeoning power of scientific management, I felt it appropriate to prepare an elementary book which would serve this audience in a multipurpose sense. For some, it is hoped that the Guide will act as a catalyst and send them off to deeper presentations and related areas. For others, this Guide should be adequate for their needs. For all readers, it is hoped that an hour or two with the Guidewith some or little thought about the limited mathematical discussionswill enable them to garner the essentials of linear programming. Thus, An Illustrated Guide to Linear Programming is designed to present the rudiments of a complex topic in an elementary, but informative and entertaining fashion.

As I have been actively involved in the field of linear programming since 1952, it is rather difficult to discriminate and delineate the numerous influences which have shaped the presentation of the Guide. Its origins can be traced to a nontechnical presentation I authored in 1954 while a member of the Directorate of Management Analysis, U.S. Air Force. But through the years, I have gained in knowledge and concepts via readings, lectures, meetings, bull-sessions, and, of course, many stimulating discussions with friends and associates. Their subliminal contributions are gratefully acknowledged.

I want to express my deep appreciation to my wife, Trudy, for her continuing encouragement and patience, to Bill McWilliam for capturing the essence of the subject matter in his excellent illustrations, and to Joanne Wagner for her accomplishing the most difficult task of reading my pen scratches and translating them to typed copy.

Saul I. Gass

CONTENTS

AN ILLUSTRATED GUIDE
TO LINEAR PROGRAMMING

INTRODUCTION

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

T HE SEARCH for the best solutionthe maximum, the minimum, or in general, the optimum solutionto 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 countrys 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 booklinear programming.

To define linear programming in nontechnical terms we can take two approachesdescribe 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 problemslinear or otherwiseare 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 individuals encounter with his days 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 societysocks 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 selectionthe optimum decisionmade? The dressing problem, like all those to be considered, has some measure of effectivenesssome basic objectivewhich 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 effectivenessthe 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 solutionit minimizes the time to get dressed within the fashion constraints of society. Someone else with a different objective functionminimize the opening and closing of drawers, i.e., minimize the early morning noisemight select a different optimum solution.