Text preview for : E20-8171_An_Introduction_to_Linear_Programming_1964.pdf part of IBM E20-8171 An Introduction to Linear Programming 1964 IBM generalInfo E20-8171_An_Introduction_to_Linear_Programming_1964.pdf
Back to : E20-8171_An_Introduction_ | Home
Data Processing Application
An Introduction to Linear Programming
Data Processing Application
PREFACE
The purpose of this manual is to describe linear
programming, to show what can be accomplished
with it, and to prepare the reader to make intelli-
gent use of a linear programming system on a com-
puter. The presentation covers the entire scope of
a linear programming application: problem formu-
lation, computer operations, interpretation of
results, and additional information that can be ob-
tained through the use of a complete linear pro-
gramming system for a computer. There is no
attempt at mathematical rigor. Some of the mathe-
matical techniques are presented briefly to indicate
what is involved in the computer solution of a
problem, but no mathematical background beyond
high school algebra is assumed.
The glossary, however, is intended as a
comprehensive list of technical terms associated
with the solving of linear programming problems,
rather than as a list of only those terms used in
this manual. Furthermore, the definitions are
written in a technical manner for the benefit of
those readers who are studying linear programming
on a deeper level than that of this introductory manual.
Copies of this and other mM publications can be obtained through mM Branch
Offices. Address comments concerning the contents of this publication
mM, Teclmical Publications Department, 112 East Post Road, White Plains, N. Y. 10601
@ International Business Machines Corporation, 1964
CONTENTS
Chapter 1: Concepts and Examples . 1 Distillate (heating oil) Blending. 26
Fuel Blending . 27
1.1: Example of Production Capacity 3.3: The Objective Function
Allocation . 2 and Constraints 27
1. 2: Example of Feed Blending 7 Objective Function . 27
1. 3: Example of Investment Policy 9 Material-Balance Constraints 27
1. 4: Characteristics of a Linear Pipe-Still Constraints. 27
Programming Application. 13 Cat-Cracker Constraint 27
1. 5: Typical Linear Programming Fuel Oil-Blending Constraint. 27
Applications . 13 Heating Oil-Blending Constraints. 27
Refinery Scheduling . 13 Gasoline-Blending Constraints . 28
Paper Trimming. 14 3.4: Computer Input 29
Production Allocation. 14 3.5: The Solution. 29
The Optimum Policy 31
Chapter 2: Deriving Additional Information Changes in Allocation. 31
About a Solution . 15 Marginal Values. 31
Reduced Costs. 31
2.1: The Fundamental "Answer". 15 Sensitivity of Profit to
2.2: Changing Limits: Right-Hand Side Constraint Coefficients 33
Ranges and Marginal Values 16 Ranges of Optimum-Policy
2.3: Changing Objective Function Variables 33
Coefficients: Profit Ranges 18 Marginal Value Ranges 34
2.4: Tradeoffs: Rates of Substitution 19 3.6: Parametric Programming 34
2.5: Sensitivity to Technology . 20
2.6: Changing Several Things at Once: Chapter 4: The Simplex Method. 37
Parametric Programming 21
4.1: Geometrical Background 37
Chapter 3: A Larger Example - Oil Refinery 4.2: Algebraic Demonstration . 38
Scheduling 23 4.3: Summary. 40
3.1: The Physical Situation 23 Glossary. 41
3.2: The Operating Data . 25
Crude Supply 25 Bibliography. 63
Pipe-Still Operations . 25
Catalytic-Cracker Operation . 25 Index 64
Gasoline Blending. 26
CHAPTER 1: CONCEPTS AND EXAMPLES
Linear programming is a mathematical technique These examples emphasize the importance of
for determining the optimum allocation of resources linear programming. When a large number of in-
(such as capital, raw materials, manpower, plant terrelated choices exist, the best choice may be far
or other facilities) to obtain a particular objective from obvious. An intuitive solution may never un-
(such as minimum cost or maximum profit) when cover the best approach, and there is seldom any
there are alternative uses for the resources. Linear guarantee that what appears to be a fairly good pol-
programming can also be used to analyze the eco- icy is really the best.
nomics of alternate availability of resources, alter- Such problems often involve large amounts of
nate objectives, and so on. money. A rational approach to the problems re-
A few brief examples may serve to indicate more quires:
concretely what can be achieved with linear pro-