Introduction to Operations Research and Applications

Description
A business firm must make decisions on many issues relating to production, distribution, consumers, shareholders, information processing, employees, society, pricing etc.

OPERATIONS RESEARCH METHODS:
RELATED PRODUCTION, DISTRIBUTION, AND
INVENTORY MANAGEMENT APPLICATIONS
B. D. CRAVEN

University of Melbourne
S. M. N. ISLAM
Victoria University
March 2005
ii
iii
PREFACE
Business managements make daily decisions on many issues, such
as how much and where to produce, for which market, what prices to
set, and how much stock to keep. Mathematical models can help to
make the best decisions, among the possible alternatives.
The objective of this book is to present a survey of selected
Operations Research methods, and some of their applications to
managerial decision making, concerning production, inventory,
distribution, and integrated supply chain modelling. Also included are
listing of some computer programs to compute operations research
models.
1
Operations Research (O.R.) has been termed The Science of
Better. A problem in the real world is modelled, usually in mathematical
terms, then mathematical techniques, together with data analysis and
computational algorithms, are applied, in order to find ways to do the
job better. The word Operations derives from the many successful
applications of O.R. to military operations in the 1940s. But, since
then, most O.R. applications have been to peaceful activities, especially
to business management, of which planning industrial production, and
scheduling airlines, and other transportation, have been prominent. The
name Management Science denotes the same discipline, with some
emphasis on business management. Practitioners of Operations
Management will find many of these techniques relevant. The areas of
Logistics, Supply Chain Management, Decision Sciences, and
Manufacturing Management deal with similar applications.
2
This book is concerned with O.R. methods. The commencing chapter
(numbered chapter 0 - computers count up from zero) gives a general
discussion of model building, various examples of their applications, and
some discussion of the limitations of some models. It is suggested that
an O.R. practitioner should understand the models and the techniques,
and, while using computers and computer packages extensively, should
not depend on them to decide a model (possibly inappropriate) to use.
Chapter 1 discusses linear programming . As well as the
mathematics, section 1.16 on cost data discusses when such models
are appropriate, and what sort of data must be sought.
Chapter 2 discusses dynamic programming, and several of its many
applications, to capital budgetting and to a rental problem. The effect
of random elements is also considered.
Chapter 3 discusses the critical path method.
Chapter 4 discusses planning over time. This includes discussion of
interest rates and present value, effect of inflation, risk-averse utility,
decision trees and planning over time, and forecasting. A concise
introduction to the use of spreadsheets for such planning and
calculations is given in chapter 9.
Chapter 5 discusses inventory, presenting various versions of
2
See Ragsdale (2001), and Gass and Harris (2001), for various such applications.
1
Some programs written in FORTRAN AND GAMS are included.
iv
economic order quantity, with applications including seasonal demand,
discounting, and the issues that arise when inventory and production
must be managed together, as especially in supply chain management.
Chapter 6 outlines the topic of networks, which often arise in
planning models.
Chapter 7 discusses various methods for nonlinear optimization ,
and lists some of their applications. Although many models are
described by linear equations, nonlinear models are also often needed.
Chapter 8 discusses simulation techniques, with applications to
queue, inventory and storage models, and also to networks models.
Often simulation can obtain results, when no exact formulas are
possible. The discussion of simulation methods, both those based on
events and those planned on a time scale, should enable a user to
understand what a computer package for simulation should be doing,
and perhaps write his own simulation program.
In chapter 9, a number of related computer programs are listed.
For these various methods and applications, the basic methods and
primary applications are presented, together with some reviews of
recent developments.
In comparison with some other books on the methods of Operations
Research, the present book gives a concise account of the methods and
applications. A moderate mathematical background is assumed (some
calculus and matrix algebra). A reader is assumed to want to
understand the methods, and the modelling assumptions made, rather
than leave it all to a computer package. Some aspects that may be
innovative include the following:
• A detailed discussion (in chapter 0) of O.R. modelling, including the
difficulties involved, and various areas of application to real problems.
• A discussion (section 1.16) of cost data, replacing the common
(inadequate) assumption that everything is linear.
• Various topics (in chapter 4) concerning planning over time, i
including discussion of riak-averse utility, and stability analysis.
• Some critical discussion (sections 5.11 and 5.12) of supply chain
models.
• Some critical discussion (sections 7.19 and 7.20) of multiobjective
optimization, and of optimization when the usual convexity
assumptions fail.

This book presents phases and aspects of applied operations
research studies with the emphasis on business, logistics, and operation
management applications. This book includes many examples of
applications of operations research methods in those areas. It can be
used as a text or a reference for a course on operations management
and logistics/supply chain management at the Masters or Doctoral level
and a text for undergraduate students in operations research. It will also
be of importance to corporate executives, academics, practitioners,
and business consultants.
v
TABLE OF CONTENTS
Chapter 0 Introduction to Operations Research and Applications
0.1 Mathematical models for management 1
0.2 Some reference books 2
0.3 Initial example 3
0.4 Check-list, when setting up an Operations Research model 3
0.5 Some other examples of Operations Research models
in business 6
0.6 Importance of model building, and limitations of computers 11
0.7 Why the name? 12
0.8 The usefulness of spreadsheets 12
0.9 Presentation of conclusions and recommendations 12
Chapter 1 Linear Programming
1.1 Introduction - management models 14
1.2 Standard form for a linear program 16
1.3 Idea of simplex method 16
1.4 Simplex tableaus 17
1.5 Information from tableau 18
1.6 Two-phase method 19
1.7 Unsigned variables 20
1.8 Revised simplex method 20
1.9 Dual linear program 22
1.10 Dual properties 23
1.11 Sensitivity 25
1.12 Dual simplex method 25
1.13 Jumps in shadow costs 26
1.14 Integer linear programming 27
1.15 Transportation problem 29
1.16 Cost data (piecewise linear cost function) 33
1.17 Some exercises on linear programming 36
1.18 Computer input/output for linear programming 40
1.19 A note on interior-point methods 43
Appendix: Some theory of linear programming 44
Chapter 2 Dynamic Programming
2.1 Introduction 46
2.2 A routing problem 46
2.3 Why does this work? 47
2.4 Forward analysis 48
2.5 An investment (or capital budgetting) problem 48
2.6 A model for inventory and production 49
2.7 A rental problem 51
2.8 Stochastic inventory 52
2.9 Some exercises and examples 53
vi
Chapter 3 Critical Path Method
3.1 Introduction 55
3.2 Example of CPM 55
3.3 Method of calculation 56
3.4 Example of computer output 57
3.5 Alternative presentation 58
3.6 Random variation in time durations 59
3.7 Exercises 59
Chapter 4 Planning over Time, Uncertainty and Forecasting
4.1 Present value 61
4.2 Annual cost and rate of return 62
4.3 Allowing for inflation? 62
4.4 Different interest rates 63
4.5 Decision trees 64
4.6 Risk-averse utility 68
4.7 Decision tree examples and exercises 69
4.8 Stability over time 70
4.9 Indifference curves 71
4.10 Forecasting and exponential smoothing 72
Chapter 5 Inventory Management
5.1 What is inventory? 74
5.2 Economic order quantity 74
5.3 Inventory model for constant sales rates 75
5.4 Inventory model for variable demand 76
5.5 Sequencing a number of products 77
5.6 What stock to carry of a critical component? 78
5.7 Managing inventory and production together 78
5.8 Seasonal demand 80
5.9 Discounted and floor prices 80
5.10 The newsboy problem 81
5.11 Supply chain management 81
5.12 Examples of supply chain models 83
5.13 Some exercises 85
Chapter 6 Network Planning
6.1 Why networks? 86
6.2 Idea of out-of-kilter algorithm 87
6.3 Idea of a shortest-path algorithm 88
6.4 Idea of Ford-Fulkerson transportation method 88
6.5 Branch and bound 89
6.6 Remarks on mixed-integer linear programming 92
6.7 Job-shop scheduling 92
6.8 Examples 94
Chapter 7 Nonlinear Optimization Methods
7.1 Introduction 95
vii
7.2 Separable programming 95
7.3 Convergence and convergence rate 96
7.4 Lagrange multipliers 97
7.5 Sensitivity 99
7.6 Computing an iterative algorithm 99
7.7 Descent methods 100
7.8 Fletcher-Reeves algorithm 101
7.9 Davidon-Fletcher-Powell (DFP) algorithm 101
7.10 Example 102
7.11 Linesearch 103
7.12 Descent methods and stability 105
7.13 Constrained minimization 106
7.14 Sequential unconstrained minimization technique (SUMT) 107
7.15 Projected gr5dient 107
7.16 Quadratic programming by Wolfe's method 108
7.17 Further comments on constrained mimimization 109
7.18 Multiobjective optimization 112
7.19 Invexity 113
7.20 Some applications of nonlinear programming 114
Chapter 8 Simulation
8.1 Idea of simulation 115
8.2 Queue and storage models 115
8.3 Examples of simulation 118
8.4 Getting pseudorandom numbers 120
8.5 Some simulation models 122
8.6 Some other methods and models 122

Chapter 9 Some Computer Programs
9.1 Remarks on computer programs for O. R. problems 125
9.2 Using spreadsheets 126
9.3 Using Excel Solver 129
9.4 An example of a GAMS package for capital budgetting 131
9.5 Introduction to the FORTRAN programming language 133
9.6 A linear programming package lpZSq 138
9.7 Documentation for the linear programming package lpZSq 144
9.8 A FORTRAN program for critical path 147
9.9 A program for one application of dynamic programming 151
9.10 FORTRAN programs to illustrate methods for unconstrained
optimization 153
Bibliography 160
1
Chapter 0 INTRODUCTION TO OPERATIONS RESEARCH
AND APPLICATIONS
0.1 Mathematical models for management
A business firm must make decisions on many issues relating to
production, distribution, consumers, shareholders, information
processing, employees, society, pricing etc..These decisions typically
concern production and inventory planning, sales forecasting, capital
budgeting, investment planning, materials requirement planning,
locational decisions, personnel management and planning, pricing,
distribution, management and planning, integrated supply chain or
logistics management and planning, as they affect the several parts of
the firm. These questions are sometimes considered under the heading
of Operations Management.
Business decision making requires the choice of the best decision
among alternatives, or at any rate a decision that gives a substantial
improvement. The objectives may be revenue maximisation, cost
minimisation, satisfactory performance regarding social responsibility,
shareholder value maximisation, etc., or sometimes the survival of the
firm in adverse circumstances. The decisions are constrained by
requirements such as budget and resource constraints. Methods of
Operations Research (O.R.) are well adapted to such decision making in
business. Applications of OR to business management have been
discussed in different disciplines such as Management Science,
Operations Management, Logistics Management, Supply Chain
Management, and Decision Sciences.
In Operations Research, we set up and use mathematical models,
usually related to questions of planning in business, industry, or
management. Any model of a real-life situation must simplify it greatly,
by picking out those factors we think important for our purpose, and
neglecting the rest. Otherwise, we can't calculate, or predict. (Newton
approximated the sun and earth by masses concentrated at points.
This approximation succeeded). We must consider whether we have
we made a right selection. What check or validation is possible?
To put our model in mathematical terms makes us formulate our
ideas precisely - what exactly are we assuming? - and so we are less
likely to make hidden assumptions without knowing it. Moreover, once
we have a model in mathematical terms, we can manipulate it
effectively using concise mathematical language. Also calculations,
using a computer, are more readily set up. The model results provide
useful information for making business decisions.
The factors we recognize, as affecting the situation, consist of (i)
external factors ("exogenous factors"), which we regard as inputs to
the system, and whose effects we shall study, (ii) factors the model
2
tries to explain ("output", "dependent", or "endogenous" factors), and
(iii) factors we shall neglect. For example, if we are hired by a firm to
determine the level of production that will maximize profits, then profit
becomes an "output" for the system, and market factors become the
"inputs". But, for an economist who wants to explain production levels,
profit could be an internal variable (internal to the system being
studied, neither an input nor an output). We should be clear what is the
aim of our investigation. It often falls to the O.R. investigator to clarify
the objective. This involves much discussion with the propounder of the
problem, to find out "where the shoe is really pinching". For example, it
could be irrelevant to optimize a production schedule, if the real
problem is labor relations.
We can fall on our face by neglecting some essential factors. A
century ago, some mathematicians proved that aeroplanes were
impossible; they had neglected the essential "boundary layer", where
viscosity of the air plays an essential role. Likewise, in a business
model, it is possible to omit an essential factor - for example there
may be an upper bound on certain resources, which must not be
forgotten. This course has to present examples from books; however, in
a real-world situation, always go and see for yourself (the factory floor,
or the airport, or whatever) if you possibly can - it is usually different
from what was supposed.
0.2 Some reference books (a few out of the many published.)
The codes etc. are here for cross-referencing.
Note that a book such as , which includes discussion of
building suitable models, is of more value to an O.R. practitioner than a
book that mainly presents the computational algorithms. In practice,
the calculations are done on computers; however, one needs some
understanding of the algorithms, otherwise one never knows whether
the computer is producing sense or nonsense.
H.C. Daellenbach, J.A. George, D.C.. McNickle, 1984 (1st. ed.)
or 1978 (2nd. ed.). Introduction to Operations Research (Allyn &
Bacon).

R. Hesse and E. Woolsey, 1980. Applied Management Science
(a quick and dirty approach), (Science Research Associates).

K.H. Bradshaw and others, 1982. An Operations Research
Casebook (Longman Cheshire).
[TH]
J.C. Ecker and M. Kupferschmid, 1988.Introduction to Operations
Research (Wiley).
M.J.C. Martin and R.A. Denison, 1971. Case Exercises in
Operations Research ,(Wiley-Interscience)
3

E.A. Bender, 1970. An introduction to mathematical modelling
(Wiley/Interscience).
H.A. Taha, 1982. Operations Research (Macmillan).

B. Srinavasan and C.L. Sandblom, 1989, Quantitative Analysis for
Business Decisions (McGraw-Hill).

M. Syslo, N. Deo, J. Kowalik,1983. Discrete Optimization
Algorithms with Pascal Programs, (Prentice-Hall).

R.E.D.Woolsey and H. Swanson, 1969, 1975.Operations
Research for Immediate Application A Quick and Dirty Manual, (Harper &
Row).
S. Makridakis and S. C. Wheelwright, 1989. Forecasting
Methods for Management (Wiley).
This list is not meant to exclude other, and more recent, textbooks.
Reference may be made to Thompson and Thore (1992), Ragsdale
(2001), and Vollman et al. (2005), listed in the bibliography, for more
examples of O. R. models in management. But it is not recommended
to use a text that is mainly a manual for a particular computer package
(see section 0.6).
0.3 Initial example
Think of a factory, whose running cost (which is to be minimized)
is a function of various production variables (how much do we make of
which product on which machine for which market?), subject to
constraints (limits on material resources, labor, time available, market
requirements). This may (but need not always) reduce to a linear
programming model). Note that we must, later, be specific as to what
we mean by cost. The following check-list (in 0.4) applies specifically
to linear programming models, but also gives general guidance in
setting up other kinds of O.R. models.
0.4 Check-list, when setting up an Operations Research model
The stages of an applied operations research study have been listed
as follows (following Taha, 1992):
a. defining the research or the policy problem
b. developing the operations research model for the relevant
system
c. implementing/solving the model numerically by some suitable
algorithms and computer programs
d. undertaking validation tests of the model and its results
e. analysing the implications of the model results for actions or
decisions related to the issues under the study.
4
A more detailed check-list is as follows:
(1). Find out what the problem really is! It won't come to you packages
in mathematical terms. Ask simple, relevant questions. Go and see for
yourself. "Obvious" assumptions can be wrong.
(2) What are the variables of the problem? What, in fact, can you
vary? If you seek to optimize, what is the objective function? Or are
there several ? Check that the variables relate to the decisions that
must be made. Would they give us enough information to act on? Many
variables cannot be negative. What alternatives are possible?
(3) List the constraints. They often include: input constraints
(restrictions or requirements on raw materials), capacity constraints
(e.g. available machine time, pipeline capacity, storage available, rate
at which a product can be made), materials balance ("what goes in
must come out", e.g. old inventory + production - part used to make
new product = new inventory + deliveries to customers), output
constraints (requirements, or limits, on sales, production, or rate of
return). Check that units of measurement are consistent, or make
them so. (A factory once measured its storage tank capacities in cubic
feet, but its flow rates - inconsistently - in gallons per minute. For
mathematical modelling, the flow rates were converted to cubic feet
per hour - to avoid hopeless confusion. Today, SI units (metres,
kilograms,. etc.) would be preferred).
(4) What data are needed? You may need all your tact to get it! Exact
figures may be unobtainable, or make little sense; maybe get upper and
lower estimates instead. Are the cost figures you get relevant ? If you
are planning production schedules, then likely costs of raw materials
and energy enter; wages may or may not, depending on the time scale
of planning.
(5) Check out a simplified example! So, find any blunders in your
model, or your computer program, before you risk your reputation. And
get quickly a "ballpark estimate" to please the boss ! (Don't be
frightened of a rough "back of envelope" calculation for this limited
purpose - if you can do it quickly !) Do the results make practical
sense? Are the computations, perhaps, only telling you what everyone
in tbe industry has known for twenty years ?
(6) Compute the full model. Often it is better to start from present
operating conditions, and try to improve them, rather than start from
scratch. What can be recommended for action (expressed in practical
5
terms, not mathematical symbols) ? Note the importance of writing a
report, intelligible to management. Don't expect managers to cope with
a schedule of how much to make of which product, if it is expressed as:
x? = 17.5
x‹ = 29.7
and so on !
Instead, tell the, in their language ! Something like:
Daily production schedule
Dinguses 17.5 tonnes
Whatsits 29.7 tonnes
and so on.
(7) Model Validation and Verification.
In Gass and Harris (2001, p. 865), model validation is defined as
the process of determining how well the outputs of a mathematical
model of real-world problem conform to reality. Model validation is
often synonymously used with other terms such as model verification
and model testing. Model validation is one of the important steps of an
O.R. study. In an applied O.R. study, the reliability of the O.R. model and
its results need to be tested. For this purpose, the usual model
validation criteria can be adopted. According to Hazell and Norton
(1986, p. 269) model validation and its purposes are as follows
“"Validation of model is a process that leads to (1) a numerical report
of the models fidelity to the historical data, (2) improvements of the
model as a consequence of imperfect validation, (3) a qualitative
judgment on how reliable the model is for its stated purposes, and (4) a
conclusion (preferably explicit) for the kinds of uses it should not be
used for"
Several criteria can be used to test the validation of a model (see
Gass and Harris, 2001; Labys, 1982; Taha, 1992; Hazell and Norton,
1986) at three levels of validation tests: descriptive, analytical and
experimental. Three different types of validation criteria are applied to
these three levels of validation tests (although 2 types of validations
are suggested in Gass and Harris (2001) which are face validity and
predictive validity) (see Kresge 1980 for further details):
(i) Descriptive validation criteria:
The attainment of the objectives of the model.
The appropriateness of the model structure and the plausibility of
results.
(ii) Analytical validation criteria:
The plausibility and characteristics of models and their results.
The robustness of the results.
(iii) Experimental validation criteria:
Methodological tests of model documentation.
Cost and efficiency in model, storage, transfer and extension.
Tests for accuracy and efficiency of implementation as well as cost
of and efficiency in the software transfer, storage and extension.
6
The above is a detailed set of model validation criteria for O.R.
models. In a real life O.R. study often some simple validation tests are
used (Hazell and Norton, 1986): plausibility of results, and comparisons
of model results with actual or historical results, and other model
results. Also, it is important to compare the model predictions with an
independent set of observations. Those may be observations from a
different time period, from the period whose data were used to
estimate the parameters of the model.
(8) What happens if something changes?
Murphy's law makes sure it does ! How sensitive are your
conclusions to small changes in the data ? (The jargon phrases are
"post-optimality analysis" for linear programming, or (more generally)
"sensitivity analysis".) If your recommendation is very sensitive to a
particular item of data, or a particular assumption, find this out before
it finds you out!
If you calculate a linear programming model, it is seldom good
enough to just present an optimum schedule! Consider also what
happens if some likely things change. For example, a sales target for
some product may have been set; but would it be profitable to increase
it by a few percent, even though the distribution costs would then also
increase ? Also, there may (quite often) be several other schedules,
alternative to the calculated optimum schedule, which are nearly as
good; and sometimes these alternatives should be presented to a
management. They may want to take additional factors into account -
such as qualitative factors, that could not be included in the
mathematical model.
(9) Try to persuade the management to put your recommendations into
effect. This can be the hardest part ! If they do, observe carefully
what happens. Get some feedback of information. Should your model
then be altered ?
0.5 Some other examples of Operations Research models in business
There will be many such in later chapters. Chapter 1 discusses
various linear programming examples. For the present, consider -
without going into details - the following additional examples of
Operations Research models in business, including supply chain
questions.
(a ) A management must choose between several plans for future
action. For example, do they start at once to produce their new product
line ? Or do they conduct a market survey first ? That gives them,
hopefully, better information, but runs the risk of letting a competitor
7
get in first. The various possibilities may be shown on a diagram called
a decision tree. In this diagram, a branch divides into two or more
branches whenever the management must take some decision (go
ahead, or not? how much to make?), or whether the external world
decides it for them (the new product sells like hot cakes, or only a few
people want to buy it?) Based on this diagram, some evaluation of
alternative courses of action can be made. Of course, one is
estimating uncertain things (how likely is it that the sales will go up by
50% for the new product?), and such estimates have to be rough. But
one is better off analysing even rough information in a systematic and
quantitative way, than just relying on intuition - or optimism - to put
the picture together. (See Chapter 4)
(b) Planning industrial operations over months or years, as well as
comparing alternatives as in a, needs to be done systematically. A
dollar now is worth more than a dollar at some future date. (Even
without inflation, money can still earn interest.) So one has to discount
future payments or receipts, to an extent depending on the time
interval, to allow for this. One may thus calculate a present value of
operations that will happen gradually over time. A variant of this is to
calculate a (percentage) rate of return - a measuring stick for how
profitable or productive the planned operations will be (see Chapter 4).
Such calculations are often, and usefully, done using a spreadsheet
program on a desktop computer, so that all the relevant figures are
handily displayed, say with years as columns and various kinds of
payments or receipts as rows. This makes it easy to vary some
parameter, such as some interest rate, and see what will happen. Such
a presentation also allows another important aspect, called cash flow,
to be checked. A business must have enough money coming in, from
somewhere, to meet its essential obligations in each year. (A firm may
go bankrupt now, for lack of cash flow this year, even though its
prospects for future years appear bright.)
(c) Network models are often useful. This may describe some actual
network, of pipelines for oil or water, or an electrical or telephone
network, or a network of routes for road transport, whose performance
(and bottlenecks !) must be analysed. However, scheduling problems
can often be described by networks. If a number of tasks have to be
done in a suitable order (you can't put the roof on the building until you
have built some walls !), then a network can describe the scheduling.
Thus, each line (or "pipe", or arc) of the network could represent a
task, and each dot (or "junction", or node) of the network represents a
time of completion. One may then calculate how soon the whole
project could be completed, and which are the "bottlenecks" (see
Chapters 3 and 6).
8
(d) Inventory means things kept in store - whether raw materials, or
products partly made ("in-process inventory"), or completed products.
If the firm has no inventory of raw materials, then an interruption to
supply will stop production - and starting and stopping is expensive
(even, sometimes, disastrous !). If there is no inventory of finished
products, then the customers can't get the products when they need
them (and then do they buy them from another firm ?), or the firm's
production is further disrupted by starting and stopping to match
varying demand for the products. But carrying inventory costs money;
not only do storage facilities, and wages of people to run them, cost
money, but (often, most importantly) the cost of the materials held in
stock has to be borrowed from the bank, and costs bank charges. How
should these conflicting requirements be balanced ? Guesswork usually
gets it wrong ! (Many firms have spent far too much in connection with
inventory, keeping far too much, or far too little.) However,
mathematical models are available, and these things can be calculated
(see Chapter 5).
(e) Rail trucks, carrying raw materials for a factory, come to a goods
yard to be unloaded. Their rate of arrival is somewhat variable; and the
rate at which they can be handled is also somewhat variable. The usual
result is that some queue builds up of trucks, waiting to be unloaded.
That costs money - and the situation is even worse, if the materials are
perishable ! Similar queues arise in many other situations, including
(for example):
Passengers, and baggage, arriving at airline counters;
Telephone calls coming into a telephone exchange;
Waiting to use specialized machines in a factory.
Mathematical models are available for various kinds of queues, if
something is known (or can be measured) about variabilities, as well as
average rates. It is these quantities that make the differences, not
whether the queue is of people or rail trucks or telephone calls. The
mathematics is very close to that for inventories (see Section 8.1).
(f) Many scheduling problems, including some questions of inventory
management, scheduling production and employment, budgetting for
capital expenditure between several projects, have the common (and
awkward) feature that the number of possibilities is very great, far too
many to make a list of them to compare. Suppose that the scheduling
can be put on a time scale (weeks or months, say), or at any rate put in
order (number off the alternative investment projects 1,2,3,...).
Suppose also that the "cost" (maybe actual cost, or some other
quantity such as waste product, to be minimized), adds up over the
different "times". Then a technique called dynamic programming can
9
often be used, to avoid listing an impossible number of possibilities.
Under the "adds up" assumption, one may calculate from each "time"
to the next, instead of listing all possible schedules. Roughly stated, the
production (or whatever) for "today" depends on past history, only to
the extent that it is summed up in the production (or whatever) for
"yesterday" (see Chapter 3).
(g ) The property just stated (not needing to look further back than
"yesterday") may be thought of as a "short memory" property.
(Technically, it is called the Markovian property). This property
happens, quite often, with stochastic systems - those including some
random elements - in particular with many queues, and inventory
systems where (as usual) there is some variability in demand for the
products. Of course, it does not always happen; but, when it does, it
usually makes some calculations possible.
(h) The order of scheduling tasks in a workshop - say, when various
jobs must be scheduled on successive machines - often leads to job
shop scheduling problems, involving integers (in which order should a
list of jobs be done), rather than continuous variables. For some of
these practical problems, there are good techniques; for some others,
there are only rough approximations (see Chapter 6).
(i) Suppose the yield (ratio of useful output to raw material input)
for some industrial process must be maximized, subject to some
constraints (it is no use blowing up the factory, or making the reaction
vessel freeze solid !). Usually, the functions here are nonlinear, so that
linear programming does not apply. Sometimes, such a problem can be
reformulated, using different variables, to allow linear programming to
be used as an approximation. But, quite often, there is too much
nonlinearity in the problem to allow this simplification. There are a
diversity of methods for calculating such nonlinear problems. Questions
of sensitivity to changes in the data are also important (see Chapter 7).
(j) Optimization is not only about maximizing profit or minimizing cost,
but can, and often should, consider environmental variables as well. For
example, a model may include a constraint which sets an upper bound
to air or water pollution. Or an environmental variable may be
assigned a cost, and included in the cost function that is to be
minimized.
(k) A model for optimal waste management was given by Sahoo, Kim,
Kim, Kraas, and Popov (2005). If only vehicle travel time is minimized,
the model is a mixed integer linear program (MILP). Thus (see Chapter
1 and Section 6.6), the model is described by linear equations, but
10
some of them may only take integer values. A more complicated
version of the model also seeks to minimize the number of vehicles, and
balance the workload. Of course, there must be some compromise
between these different objectives. While there are various computer
programs for MILP, they may not be suitable for this specialized
problem. The authors use several heuristic (approximate) methods,
including a clustering algorithm to generate the initial routes, related to
the travelling salesman problem, and also a simulated annealing method
(see Section 8.4) to improve the result.
(l) Various models for supply chain have been given recently. One, by
de Kok, Janssen, van Donemalen, van Wachem, Clerkx and Peeters
(2005) is cited in section 5.12. The variability of demand increases as
one moves back through the stages of the production process. The
authors propose a model, with linear equations describing inventory.
However, their main concern is to reduce time lags in the planning
process.
Another supply chain model, by Troyer, Smith, Marshall, Yaniv,
Tayur, Barkman, Kaya and Liu (2005), seeks to improve the proportion
of deliveries that are on time, over a network of factories and dealers,
while reducing inventories. Here, inventories must be held at various
places in the network, with appropriate levels of safety stock (see
chapter 5 for what this means for a single inventory). But the demands
must be propagated down the network (see Section 5.11.)
(m) Metty, Harlan, Samelson, Moore, Schnweur, Raskina, Schneur,
Kanner, Potts and Robbins (2005) gave a model for a supplier
negotiation process in the telecommunications industry. This led again
to a MILP model.
Hicks, Madrid, Milligan, Pruneau, Kanaley, Dumas, Lacroix,
Desrisoers and Soumis (2005) gave a MILP model for scheduling the use
of aircraft which are shared between several firms. This model
contained many zero-one variables (taking value 1 when the aircraft is
used for a particular journey, and 0 otherwise). The (heavy)
computational requirement was reduced by partitioning the MILP into
smaller subprograms, having only a few variables in common. So the
problem was handled by optimizing the subprograms, then
improving the values of the common variables, then repeating the
process.
Kuchta, Newman and Topal (2005) gave a MILP model for
scheduling production at an iron mine, to meet demands from the mills
that process it. Here, zero-one variables occur, taking value 1 if a
particular block is mined at a particular time, and otherwise zero.
LeBlanc, Hill, Greenwell and Czesnat (2005) developed a
distribution model, involving different warehouses and shipping
distances, to minimize the total shipping, holding and handling costs,
using a linear programming model.
11
0.6 Importance of model building, and limitations of computers
Any course on Operations Research must detail various standard
models, and methods to analyse and calculate with them. But one must
not impose a standard model on a real-world situation, if it does not fit.
It may well happen that no standard model is of any relevance, to a
particular real situation. One must learn, and be prepared, to set up a
model, to fit the real situation. To practice this, one should also
undertake project work on specific problems.
Most Operations Research investigations involve serious
computation, and many computer packages are available, e.g. for linear
programming. But it is important not to allow an available package to
determine the model to be used. The computer output may be very
misleading if you do not know what model, or assumptions, are built
into the package, or if you do not know, even in outline, what
computational method is being used. Indeed, if a very rough, quick,
pencil-and-paper calculation can be done, it may provide a useful check
(are we out by a factor of ten?), as well as giving some answer to an
impatient boss or client.
One instance of misuse of a computer package was cited by
Greenberg (1987). A factory had a two-year supply of unsaleable red
widgets in its warehouse, and more being made, because the
computer-based production and inventory control system said they
should be made. The system was not documented, to they did not
understand it. Eventually, it was found that an order for blue widgets
had been received, but it was entered by mistake as a large order for
red widgets. This caused a special production order to replenish the
stock of red widgets, and a spurious forecast demand for red widgets,
so even more were called for. The mistaken order was corrected, but
the system did not recover from the mistake.
One source of projects (of moderate size) is An Operations
Research Casebook, by K. H. Bradshaw, D. N. Foster, B. R. Smith, and G.
A. Vignaux (Longman Cheshire, Melbourne, 1982). Many actual
applications of operations research may be found in journals, especially
Journal of the Operational Research Society and Interfaces. However
those in Interfaces are often large models, involving large sets of data
and heavy computation. A student is advised to start on some smaller
models, found in the older literature. A few examples are the following:
K. Kolesar, 1975, Determining the relation between fire engine travel times and
travel distances in New York city, Operations Research 23 (4), 614.
W. T. Ziemba, C. Parkan and R. B rooks-Hill, 1974. Calculation of investment
portfolio with risk-free borrowing and lending, Management Science 21, 209-222.
R. Juseret, Long term optimization of electrical system generation by convex
programming, 1978. Mathematical Programming Study 9, 186-195.
A. Prékopa and T. Szántai, Flood control reservoir system design using stochastic
programming, 1978. Mathematical Programming Study 9, 138-151.
B. D. Craven, Mathematical Programming and Control Theory, 1978. Chapman & Hall,
12
London.
S. K. Singh, A function for size distribution of incomes, 1976. Econometrica 44, 963-
970.
R. P. O'Neill, M. Williard, B. Wilkins and R. Pike, 1979. A mathematical
programming model for allocation of natural gas, Operations Research 27, 857.
0.7 Why the name ?
Operations Research takes its name from the application of
scientific methods to the planning of military operations, by Britain and
U.S.A., during the 1939-1945 war. However, the ideas and methods
have long since been applied to the arts of peace.
Other names, such as Management Science and Industrial
Engineering, describe very similar disciplines.
0.8 The usefulness of spreadsheets
A spreadsheet program is often useful for data input (e.g. to a
linear programming package, see section 1.18 for an example), or for
data output for presentation, from the computation of an O. R. model.
The basic principles of a spreadsheet are quite simple (see section 9.2),
and the complications (especially graphical presentations) can be
learned later, as and when required.
However, the computational features of spreadsheet programs have
serious limitations, and often more specialized computer programs are
preferable (e.g. programs for linear programming or nonlinear
optimization.)
Moreover, a model that is easy to set up on a spreadsheet may be an
inadequate model. Nothing substitutes for the pencil-and-paper
modelling, before going near the computer.
0.9 Presentation of conclusions and recommendations
It is the responsibility of an Operations Research consultant
(whatever label he/she wears) to present the results intelligibly to the
client, without assuming the client is already familiar with the
technicalities. (It is always the job of a mathematician to explain
himself/herself to the client, rather than the other way about.)
Usually, both a written report and an oral presentation are required.
The following notes relate to a written report, what it should contain,
and how it should be arranged, so as to be acceptable to a business
management.
The layout of a report should be something like the following:
SUMMARY (or OVERVIEW (on a single page; no math
symbols!)
Introduction and objectives
Summary of findings and conclusions
Summary of recommendations (perhaps cross-referenced to
main report)
13
MAIN REPORT (maximum nine pages)
Problem definition
Method (but relegate math. technicalities to an appendix)
Assumptions made (list assumptions - so that your work is
checkable)
Analysis of data
Findings and conclusions (some graphical, or
spreadsheet, presentation may be useful)
Recommendations (some specific things to do)
APPENDICES (as the problem requires; put here such
things as extensive tables of data, computer output,
mathematical formulation, e.g. of a linear programming
model.)
The stated limitation on the size of the Summary (one page, for
the big boss), and the Main Report (maximum 9 pages), are important.
Do not expect managers to read masses of material! Don't expect them
to read mathematical symbols, when these are not essential! For
example, do not present the results of a linear programming optimization
as x1 = 123.45 , x2 = 17.4 , etc. .
Instead present some table of recommended quantities, with names that
the management will be familiar with, for example:
PRODUCTION SCHEDULE
123.5 tons of Wotsernames,
17.4 tons of Gizmos,
etc (putting in whatever the names of the products really are).
Do not present spurious precision in the conclusions - consider how
accurate the data are! Also, a spreadsheet presentation is often
persuasive.
The names given for headings are not set in concrete; vary them to
suit the topic.
There must be (usually in an appendix) enough relevant mathematical
detail to enable the calculations to be checked, or repeated with some
changes. For example, for a linear programming model, there must be a
list of variables, and the problem description in some form - a data
matrix, maybe on a spreadsheet, can be better than pages of equations.
Note carefully that the data for a real-world problem is often
inadequate (then, often, you must make assumptions, and state clearly
what you have assumed), and may contain items that are irrelevant, or
misleading (you must use some judgement !)
A report must be typed, using any available word processor. You don't
have to use a computer program to do diagrams; graphs can be pasted
in the report. However, spreadsheet programs, such as Excel, have some
useful graphics capability. And the added neatness of graphs done with a
computer program is a selling point, as well as a requirement by journal
editors.
14

Chapter 1 LINEAR PROGRAMMING
1.1 Introduction : management models
To introduce linear programming, consider the following two models.
Model A Allocation of production to machines Six products can be
made on each of two machines.The following tables show, for each
combination of product and machine, the production rate (expressed as
hours per ton) and the cost ($ per ton); also the demand in tons for
each product. Also shown are the variables, x?, x¤, ..., chosen to
denote the amount (tons) of each product to be made on each
machine. The hours available are 780 hours on machine 1, and 3077
hours on machine 2. A schedule is required, by which the requirements
can be met at minimum total cost.
Production rate Cost Demand Variables (hours/ton)
($/ton) (tons)
Mach.1 Mach.2 Mach.1 Mach.2
Product 1 .228 .119 36.0 44.2 2929 x? x‡
Product 2 .228 .119 42.4 36.2 9420 x¤ x°
Product 3 .231 .132 34.5 38.4 1655 x‹ x·
Product 4 .231 .132 41.0 30.2 8978 x› x?‚
Product 5 .182 .112 22.1 21.4 2989 x? x??
Product 6 .182 .112 28.5 13.4 2977 x? x?¤

There is a constraint for each product (x? + x‡ = 2929 for the first
product), and a constraint for each machine
(.228x?+.228x¤+.231x‹+.231x›+.182x?+.182x?ˆ780 for machine 1);
and all the variables x
j
are nonnegative. The constraints need to be laid
out tidily in rows and columns (thus as a matrix) - or there will be
confusion, especially when entering data into a computer program.
The use of dots for zeros is unconventional, but helps the eye
considerably. The objective function to be minimized is
36.0x? + 42.4x¤ + ... + 13.4x?¤ .
15

x? x¤ x‹ x› x? x? x‡ x° x· x?‚ x?? x?¤
1 1 . . . . . 1 . . . . . =2929
2 . 1 . . . . . 1 . . . . =9420
3 . . 1 . . . . . 1 . . . =1655
4 . . . 1 . . . . . 1 . . =8978
5 . . . . 1 . . . . . 1 . =2989
6 . . . . . 1 . . . . . 1 =2977
7 .228 .228 .231 .231 .182 .182 . . . . . . ˆ 780
8 . . . . . . .119 .119.132 .132 .112 .112 ˆ3077
Model B The Novelty Company makes Thingos, Dinguses and Whatsits.
Each Thingo takes 1.5 hours to make, and requires 4.5 kg of raw
material I and 950 g of raw material II. Each Dingus takes 4.6 hours to
make, and requires 2.0 kg of raw material I and 100 g of raw material
II. Each Whatsit takes 2.1 hours to make, and requires 11.0 kg of raw
material I and 240 g of raw material II. The net profit (= sale price
minus costs) for each Thingo is $220, for each Dingus is $150, for
each Whatsit is $270. The Company has available 25 hours, 130 kg of
raw material I, and 26 kg of raw material II. What is the maximum
profit they can make, and how do they do it ?
Suppose they make x? Thingos, x¤ Dinguses, and x‹ Thingos.
Then x? ˜ 0, x¤ ˜ 0 and x‹ ˜ 0, since negative amounts have no meaning
here. The restrictions on time, raw material I, and raw material II,
require the following constraints to be satisfied:
1.5x? + 4.6x¤ + 2.1x‹ ˆ 25,
4.5x? + 2.0x¤ + 11.0x‹ ˆ 130,
950x? +100x¤ +240x‹ ˆ26000.
Subject to these constraints, the objective function
220x? + 150x¤ + 270x‹
is to be maximized. So there is a linear programming problem:
Maximize 220x? + 150x¤ + 270x‹
subject to x? ˜ 0, x¤ ˜ 0, x‹ ˜ 0,
1.5x? + 4.6x¤ + 2.1x‹ ˆ 25 ,
.45x? + .20x¤ + 1.10x‹ ˆ 13.0 ,
.95x? +.10x¤ + .24x‹ ˆ 26.0 .
Observe that, in a linear program, the objective function and the
constraint functions are linear, and the veariables are nonnegative .
The constraints may be equalities, ˆ inequalities, or ˜ inequalities.
[Note also , in Model B, that the second and third constraints have been
scaled (multiplying by 0.1 and 0.001 respectively), so as to make the
largest coefficient in each constraint not too far from 1 is absolute
value; this helps the accuracy of computation.]
Linear programming applies to many other situations; other
examples are given in later sections.
16
1.2 Standard form for a linear program
The inequalities are converted to equalities by putting in extra
variables. Thus, in Model B, the inequality1.5x? + 4.6x¤ + 2.1x‹ ˆ 25
becomes 1.5x? + 4.6x¤ + 2.1x‹ + x› = 25,
where x› is a nonnegative slack variable . Thus Model B becomes:
Minimize 220x? + 150x¤ + 270x‹ + 0x› + 0x? + 0x?
subject to x?, x¤, x‹, x›, x?, x? ˜ 0,
1.5x? + 4.6x¤ + 2.1x‹ + x› = 25.0 ,
.45x?+ .20x¤ + 1.10x‹ + x? = 13.0 ,
.95x? + .10x¤ + .24x‹ + x? = 26.0 .
Note that each constraint now has a variable with coefficient 1, that
occurs nowhere else (thus, x› in the first constraint). Thus there is an
initial feasible solution (feasible means satisfying the constraints) x› =
25.0, x› = 13.0, x? = 26.0, all other x
j
= 0. (Notice that there are here
just as many nonzero x
j
(three) as there are constraints.) If the
coefficients in these constraInts are laid out as a matrix, thus

x? x¤ x‹ x› x? x?
1.5 4.6 2.1 1 . . 25
.45 .20 1.10 . 1 . 13
.95 .10 .24 . . 1 26

then this matrix contains a unit matrix (here, columns 4,5,6). This is
necessary in order to start the simplex method - see Section 1.3).
If a model has a ˜ constraint, for example 3x? + 4x¤ ˜ 12, then a
negative slack variable is introduced, to convert to an equality, thus
3x? + 4x¤ - x
negslack
= 12. But this is not enough, since a term
with coefficient +1 is needed, to provide the unit matrix. So an
artificial variable is added; thus,
3x? + 4x¤ - x
negslack
+ x
artificial
=12.
But x
artificial
is not part of the original problem; so a penalty cost term
+Mx
artificial
must be added to the objective function (to be minimized).
Here, M is a large enough positive number, so that minimizing the
objective function will get rid of the artificial variable. Consider now an
equality constraint, say 3x? + 4x¤ = 12. This still needs an artificial
variable (though not a slack variable), thus 3x?+4x¤ + x
artificial
= 12,
with +Mx
artificial
in the objective function.
This account standardizes on Minimization problems. Maximization
(as in many textbooks) is equally good. Note that MAX 2x? - 3x¤ + 5x‹
is equivalent to MIN -2x? + 2x¤ -+ 5x‹ .Thus, the profit coefficients
-2, 2, -5 are the negatives of the cost coefficients 2, -3, 5 ; and the
z
j
-c
j
(see Section 1.4) have opposite sign; and -Mx
artificial
is added to the
objective being maximized. [Also some books have a different
definition of standard form.]
1.3 Idea of simplex method
The simplex method is the most widely used algorithm for
computing linear programs. (See also Section 1.19.)
17
Consider the linear program:
C: Minimize 3x? + 4x¤ subject to x?˜0, x¤˜0, 2x? + x¤ ˆ 7, x? + x¤ ˜ 5.
Putting this into standard form gives the (initial) tableau :
Cost coeffts 3 4 0 0 10
x? x¤ x‹ x› x? Requirement Multiplier
2 1 . 1 . 7
1 1 -1 . 1 5 -.5
z
j
-c
j
7 6 -10 0 0 50 -3.5
Note that the cost coefficients (c?=3, c¤=4, etc.) are not part of
the tableau; but we need to refer to them. Multiplier and z
j
-c
j
are
explained below. Here, x› is a slack variable, x‹ is a negative slack, and
x? is an artificial variable; M is taken here as 10, for simplicity. (Usually
a much larger number is required, like 10000, to be large enough,
compared to all the other costs in the problem). Columns 4 and 5 give
the required unit matrix.
The constraints solve immediately to give x›=7-2x?-2x¤-0x‹ and
x?=5-x?-x¤+x‹. (The variables x› and x? form the initial basis. Initially
x›=7 and x?=5, so the objective function f = 0(7)+10(5)=50. ) Now
the objective function equals
f = 3x?+4x¤+0x‹+0x›+10x? = 3x?+4x¤+0x‹+10(5-x?-x¤+x‹)
= 50 - [ 10(1) -3]x? - [10(1) - 4]x¤ - [10(-1)-0]x‹
= 50 - 7x? - 6x¤ + 10x‹.
[The numbers 7, 6, -10 are z
j
-c
j
in the tableau.]
Initially x?=x¤=x‹=0 (nonbasic variables). Consider increasing one of
them from zero. The fastest rate of decrease of f is obtained by
increasing x? from zero. How far can x? increase ? From x›=7-2x?
˜0and x?=5-x?˜0, there follows x?ˆ3.5 and x?ˆ5, hence x? is taken as
3.5. The new basis variables are x? (replacing x›) and x?. [The order
of the basis variables matters.] [Here, the pivot is the element in
column 1 (new basis variable) and row 1 (the first constraint here tells
which variable leaves the basis. Row 1 is here the pivot row.]
It is now required to solve for x? and x?. Add 0.5 (equation 1) to
equation 2; add -3,5(equation 1) to the z
j
-c
j
row); divide the pivot row
(here, row 1) by the 2 (the pivot element). This gives
x? +.5x¤ +.5x› = 3.5 and .5x¤-x‹-.5x›+x?=1.5.
Solving for the new basis variables, x?=3.5-.5x¤-.5x› and
x?=1.5-.5x¤+x‹+.5x›. Therefore f = 3x?+4x¤+10x?
=25.5 -[ 3(.5)+10(.5)-4]x¤ -[3(0)+10(-1)-0]x‹ - [3(.5)+10(-.5)-0]x›
=25.5 - 2.5x¤ +10x‹ + 3.5x› ;
so x¤ enters the basis. Then x?=3.5-.5x¤˜0 and x?=1.5-.5x¤˜0, require
that x¤ˆ3.5/.5=7.0 and x¤ˆ1.5/.5=3; so take x¤=3; the pivot is the
second element in column 2. And so on.
1.4 Simplex tableaus
The above calculations are done systematically, using arrays of
numbers, called tableaus. The step from each tableau to the next is
18
called an iteration.

Cost coeffts 3 4 0 0 10
x? x¤ x‹ x› x? Requirement Multiplier
Tabl.1 2 1 . 1 . 7
1 1 -1 . 1 5 -.5
z
j
-c
j
7 6 -10 0 0 50 -3.5

Tabl.2 1 .5 . .5 . 3.5 -1
. .5 -1 -.5 1 1.5
0 2.5 -10 -3.5 0 25.5 -5

Tabl.3 1 . 1 1 -1 2
. 1 -2 -1 2 3
0 0 -5 -1 -5 18 .
In tableau 1, the basis columns are 4 and 5; the cost coefficients are
[c› c?] = [0 10]. Calculate z?-c? =[0 10] ã2õ-3=7;
z¤-c¤=[0 10] ã1õ-4=6;
and so on; note basic z
j
-c
j
=0. Ã1Õ
The largest positive z
j
-c
j
is z?-c?=7; so x? enters the basis. Choose
the smallest nonnegative ratio among 7/2 and 5/1 [look at
requirements column and pivot column; ignore negative ratios, if
present, since they don't stop the variable going positive]. The first
ratio is the smallest, so the first basis variable (x›) is replaced by x?.
The pivot is shown in bold.
For rows other than the pivot row, the
multiplier = - (element in pivot column)/(pivot element).
[Thus the multiplier for second row is -(1)/(2). ]
To update the tableau, for rows other than the pivot row:
new element = old element +(row multiplier)(element in same
column and pivot row)
Thus, for row 2 and column 1, 1 ü 1 + (-.5)(1) = .6. The z
j
-c
j

row is
updated like any other row. Finally, the pivot row is divided by the
pivot.Thus tableau 2 is obtained. The largest positive z
j
-c
j
is z¤-c¤=2.5;
so x¤ enters the basis. The second basis element (x?) leaves the basis
(consider ratios 3.5/.5 and 1.5/.5).
In the third tableau, all z
j
-c
j
are ˆ 0; so an optimum has been
reached. (The numbers z
j
-c
j
are called reduced costs.)
1.5 Information from tableau
The optimal solution is x? = 2, x¤ = 3, other x
j
= 0. Observe that
the unit matrix in the initial tableau consists of columns 4 and 5 (in that
order). The optimal inverse basis matrix then consists of columns 4
and 5 in the optimal tableau. From z›-c›=-1 and z?-c?=-5, with c›=0
and c?=10, obtain z›=-1 and z?=5. In the optimal tableau, columns 1
and 2 form the unit matrix; columns 1 and 2 in the initial tableau from
19
the optimal basis.
Check that: ã 1 -1õã2 1õ
=
ã1 0õ
and
[3 4]ã -1õ
=
[-1 5]
Ã-1 2ÕÃ1 1Õ Ã0 1Õ Ã-1 2Õ
i.b.m. b.m.
Here, [3 4] is the vector of cost coefficients for the optimal basic
variables; and the shadow costs are [z›, z?] = [-1 5] (see below).
What happens if some requirement is perturbed a little? If the
second requirement 5 is changed to 5+h, then (using the inverse basis
matrix)
ãx? õ
=
ã1 -1õã7 õ
=
ã2- h õ
˜
ã0õ
provided
hˆ2
Ãx¤ Õ Ã-1 2ÕÃ5+hÕ Ã3+2hÕ Ã0Õ h˜-1.5
So the basic variables x?, x¤ stay basic when h varies between -1.5 and
2, although the values change. Within that range, the optimal objective
function equals 3(2-h)+4(3+2h)=18+5h. The number 18 is already
given in the optimal tableau; and 5 is the second shadow cost.
1.6 Two-phase method
So far, a numerical value was given for M. If, instead, M is left as a
symbol, then the z
j
-c
j
for the initial tableau for example C (in 1.3) are
M-3, M-4, -M, 0,0, and the initial objective is 5M (instead of 50), with
multiplier -(M-3)/2. The second tableau obtains 0, (M-5)/2,-M, -(M-
3)/2,0; objective =(3M+21)/2, and multiplier = -(M-5). The third
tableau has z
j
-c
j
as 0, 0, -5, -1, -M+5, and objective 18. This is the
big M method, sometimes used for hand calculation.
An alternative, often used in computer programs for LP, is the
two-phase method. In phase I, M is taken as the unit of cost, and other
numbers considered negligible, so that the cost coefficients become 0,
0, 0, 0, 1, and the initial objective value is 5.
Phase I
Cost coeffts 0 0 0 0 1
x? x¤ x‹ x› x? Requirement Multiplier
Tabl.1 2 1 . 1 . 7
1 1 -1 . 1 5 -.5
z
j
-c
j
1 1 -1 0 0 5 -.5

Tabl.2 1 .5 . .5 . 3.5 -1
. .5 -1 -.5 1 1.5
0 .5 -1 - .5 0 1.5 -1

Tabl.3 1 . 1 1 -1 2
. 1 -2 -1 2 3
z
j
- c
j
0 0 0 0 -1 0
New z
j
- c
j
0 0 -5 -1 5
At the end of phase I, the z
j
-c
j
are all zero, except artificial columns.
They must be recalculated, using the original costs, for example
20
z‹-c‹= [3 4] ã 1 õ -0 = -5 (using costs 3, 4 for basic x?,x¤
Ã-2 Õ and zero now instead of M )
Here, by coincidence and unusually, all the (new) z
j
-c
j
happen to be ˆ 0,
so the optimum has been reached. But usually some (new) z
j
-c
j
is > 0,
so a phase II must follow, consisting of one or more simplex iterations.
If the objective function in example C (in 1.3) is changed to x? - x¤,
then the tableaus become
x? x¤ x‹ x› x? Requirement
2 1 . 1 . 7
1 1 -1 . 1 5
1 1 -1 . . 5

1 . 1 1 -1 2
1 1 -1 . 1 5
0 0 0 0 -1 0
-2 . 1 . X -5 öRecalculated
After the end of Phase I, the z
j
- c
j
row and objective value are
recalculated as shown above, for example
z?-c? = [c‹ c¤] [1] - c? = [0 -1 [1] -1 = -3 .
[2] [2]
[Here X is no longer relevant, since the artificial column will ot be put back into the basis.
For comparison, X would be -M-1 for the big M method.] An iteration of Phase II
gives:
1 . 1 1 -1 2
2 1 . 1 . 7
-3 . . -1 X -7
which happens to be optimal, with x?=0, x¤=7, and (slack) x‹=2. (Again,
X is not relevant here - although its matrix column is part if the inverse
basis natrix.)
1.7 Unsigned variables
A variable (z say) that is not required to be nonnegative can occur
in a linear program - usually representing the change (up or down) of
a variable from its usual level. To make the simplex method work, z
must be written as z = z? - z¤ with z?˜0 and z¤˜0. But z? and z¤ must
not both occur in a basis (3 = 3-0 and -3 = 0-3 okay, not 3 = 4-1).
1.8 Revised simplex method
Usually (see model A for an example) the matrix of coefficients in a
linear program is sparse, meaning that there is a high proportion of
zeros. It then becomes computationally useful to not work with the
whole simplex tableau, but only with part of it - the inverse basis
matrix, with an extra row and column. The revised simplex method thus
saves both data storage and computing time (multiplying uselessly by
zero). But it is then necessary to record separately which variables are
21
in the basis; the whole simplex tableau is no longer available to show it.
Req Matrix Col Mult Req Matrix Col Mult Req Matrix .
50 | 0 10 | 7 | -3.5 25.5 | -3.5 10 | 2.5 | -5 18 | -1 5|
7 | 1 . | 2 | 3.5 | 0.5 . | .5 |-1 2 | 1 -1|
5 | . 1 |1 | -.5 1.5 | -.5 1 | .5 | 3 | -1 2|
Basis x›,x? Basis x?,x? Basis x?,x¤
z
j
- c
j
=7,6,-10,0,0 ; col 1 z
j
- c
j
=0,2.5,-10,-3.5,0 ; col 2 z
j
- c
j
=0,0,-5,-1,[-5] ;optimal.
In this calculation, M is taken as 10. The initial objective value,
50, is obtained as in the simplex method; it is convenient here to put
the requirements column at the left. The matrix tabulated is the
inverse basis matrix , so starts with a unit matrix. The top row starts
with the cost coefficients for the initial basis columns.
The revised simplex (unlike the simplex) regularly refers back to
the original data matrix:
x? x¤ x‹ x› x? Requirement
2 1 . 1 . 7
1 1 -1 . 1 5
The cost coefficients are 3,4,0,0,10. To obtain the z
j
-c
j
for the first
revised-simplex tableau, use the top row with the columns of the
data matrix. Thus z?-c? = [0 10] ã2 õ - 3 = 7; others are
Ã1 Õ
similar.This shows that column 1 should enter the basis. To
reconstruct column 1 of the simplex, use the inverse basis matrixwith
column 1 of the data matrix :
ã1 0 õã2õ
=
ã2õ
Ã0 1ÕÃ1Õ Ã1Õ
This column is marked Cols in the above revised-simplex tableau; the 7
at the top is z?-c?. The pivot is chosen, in this column, as for the
simplex; and the update (of the whole matrix) is done, just as for the
simplex (except that it is a smaller matrix). [For example, 0-(3.5)(1)=-3.5]
In the second revised-simplex tableau, z¤-c¤=[-3.5 10]ã1õ-4= 2.5;
others are similar. Thus x¤ enters the basis. Ã1Õ
Column 2 of the simplex is reconstructed as ã.5 0õ ã1õ=ã.5õ;note that
the column is got from the data matrix Ã-.5 1Õ Ã1Õ Ã.5Õ
Considering the ratios 3.5/.5 and 1.5/.5, the first basis variable (x›)
leaves the basis, being replaced by x¤. In the update (for example) the
matrix element 0.5 ü 0.5+(-1)(-.5)=1.
The third tableau is optimal, since all z
j
-c
j
are ˆ 0; z?-c? (for the
artificial column) is put in [ ], to remind that an artificial column is not
considered for putting back in the basis.
Computer programs for linear programming use the revised simplex
(or some development of it that saves space by storing, not the inverse
matrix itself, but other information from which it can be constructed, or
some other form that is more numerically stable for large LPs), not the
simplex, to save both storage space and time. (Only integer
22
programming needs the full simplex tableau).
Normally, one uses decimals, rather than vulgar fractions -
otherwise denominators soon get unmanageably large. Note that the
change from simplex to revised simplex, and the change from big M to
two-phase, are separate things; the revised simplex example here used
big M (with M=10 for convenient presentation), but could have used
two-phase instead. Observe also that the calculations work down
columns rather than across rows. For this reason, some computer
programs for linear programming (e.g. Craven's program - see Section
1.19, and the Minos package) enter the matrix data going down
columns (thus not across rows, like equations), and enter only nonzero
matrix elements (and which row they are in). Alternatively, some
programs accept the data in spreadsheet format (see section 4.10);
here also, only nonzero data need be entered.
1.9 Dual linear program
Consider the following linear programs:
Primal program in matrix language
MIN 3x?+4x¤+Mx? subject to MIN c
T
x = [3 4 0 0 M] x
2x?+x¤+x› = 7, (where x = [x?, x¤, x‹, x›, x?]
T
)
x?+x¤-x‹+x?=5, ü subject to x ˜ 0,
x?,x¤,x‹,x›.x? ˜0 Ax = b,
[Optimum x?=2, x¤=3] where A = ã2 1 . 1 .õ, b=ã7õ .
Ã1 1 -1 . 1Õ Ã5Õ
Dual program ï ï (rearrange the pieces)
MAX 7w? + 5w¤ subject to ö ö MAX b
T
w subject to A
T
w ˆ c
T
,
2w?+w¤ˆ3, w?+w¤ˆ4, thus MAX [7 5]ãw?õ subject to
0w? -1w¤ˆ 0 [so w¤˜0] à w¤Õ
1w?+0w¤ ˆ M, [so w¤ˆM] [w? w¤]ã2 1 . 1 .õ
ˆ
[3 4 0 0 M]
ï ï [Optimum w?=-1,w¤=5 Ã1 1 -1 . 1Õ
set z?=-w?, z¤=w¤ Note that the dual does not
MAX -7z?+5z¤ subject to include a constraint w ˜ 0.
-2z?+z¤ˆ3, -z?+z¤ˆ4, z?˜0, z¤˜0.
Thus, a dual problem can sometimes be usefully rearranged. Note that,
if M is very large, a constraint w¤ ˆ M has no effect.
1.10 Dual properties
I Weak duality If x is feasible for the primal, and w is feasible for the
dual, then c
T
x ˜ b
T
w.
Proof c
T
x - b
T
w = c
T
x - w
T
b = c
T
x - w
T
Ab = (c
T
-w
T
A)x ˜ 0
since each vector has components ˜ 0.
Remark The range of values that the primal objective takes lies
entirely above the range of values that the dual objective takes
(assuming x and w feasible). Suppose that the primal is minimized
as x=x*, and the dual is maximized at w=w*; then c
T
x* ˜ b
T
w*.
23
II Zero Duality Gap (ZDG) c
T
x* = b
T
w* ; and w* is the vector of
shadow costs for the primal.
Proof In the optimal simplex tableau, denote by Q the inverse
basis matrix, u the vector of basic variables, q the vector of cost
coefficients for them. Then u = Qb; the matrix in the optimal tableau
is QA; the vector of the z
j
-c
j
is c
T
QA-c
T
, which is ˆ 0 by the
optimality condition. So the vector q
T
Q of shadow costs is feasible
for the dual. Since (q
T
Q)b = q
T
u = c
T
x*, and no w feasible for the
dual can (by I) have w
T
b>c
T
x*, it follows that w*=q
T
b is optimal for
the dual, and c
T
x* = b
T
w*.
III Karush-Kuhn-Tucker conditions (see chapter 7). Necessary
conditions for x* to minimize the primal are that, for Lagrange
multipliers r* ˜ 0 and w*, there hold c
T
=w*
T
A + r* and r*
T
x* = 0.
Proof In the optimal tableau, x
j
>0 only for basic x
j
, and then r*
j
=c
j
-z
j
=0.
So r*
j
= c
j
-z
j
= 0; so r*
T
x = 0.
1.11 Sensitivity
It is usually not enough to calculate an optimum to a linear
program; it is also necessary to consider how sensitive the optimum is
to small changes of the data. (Requirements are not all "set in
concrete"; and there can be last-minute changes to data.)
•a In 1.5, a small change to one requirement is considered; over a
sufficiently small right hand side range (in the example, if the second
requirement lies between 5-1.5 and 5+2), then optimal objective =
original value+(shadow cost)(change in requirement); and the same
basic variables stay optimal. (If more than one requirement changes,
the shadow costs still apply, but the RHS ranges are reduced.)
•b Consider a change to a cost coefficient.
(a) Change c‹ away from 0. Since x‹ is not in the optimal basis, the
z
j
are unchanged. So all the z
j
-c
j
remain ˆ 0 (still optimal), provided that
z‹-c‹ stays ˆ0. From c‹=0 and z‹-c‹=-5 follows z‹=-5, so now z‹-c‹=-
5-c‹ˆ0 provided c‹˜-5.
(b) Change c? away from 3. Since x? is basic, the z
j
are changed; it
is necessary to check all nonbasic z
j
-c
j
(except artificials). Thus,
z‹-c‹= [c? 4] ã 1 õ-0=c?-8ˆ0 provided c?ˆ8. (Hereã 1õ is column 3 of
Ã-2Õ Ã-2Õ
the optimal tableau in 1.4.) Similarly z›-c›=c?-4ˆ0 provided c?ˆ4. So
the tableau is still optimal when c?ˆ4. (If c? increases above 4, a
further simplex iteration is needed.)
(c) Suppose that both c? and c‹ are both functions of some
parameter r. For a simple example, suppose c?=3+r and c¤=4-2r. Then
z‹-c‹ = [3+r 4-2r]ã 1õ-0 = 5-4r ˆ 0 provided r˜5/4; z›-c› = ... .
Ã-2Õ
Such a situation may arise in a profit-maximizing problem, with profit
24
coefficients p? = 30-20 (thus, revenue - variable cost) and p¤ = 85-45
(representing products manufactured) in the objective being
maximized. Suppose that a unit of the first product requires 0.1 kg of a
certain ingredient, and a unit of the second product requires 0.2 kg,
where this ingredient costs $q per kg (currently q = $50, but may
vary). Then
p? = 30 - [.1q+15] and p¤ = 85 - [.2q + 35].
•c Consider the example of 1.4, with requirements changed to 7 and
3.5. (The latter is on a boundary of its RHS range.). The optimal tableau
now becomes:

Tabl.3 1 . 1 1 -1 3.5
. 1 -2 -1 2 0
0 0 -5 -1 -5 25.5
(Note one basic x
j
is zero.) But there is also another optimal tableau
(got using dual simplex, see 1.12) :
Tabl.3 1 1 -1 . 1 3.5
(new) . -1 2 1 -2 0
0 0 -3 0 -7 25.5
The shadow costs are different: -1 and 5 for the first tableau, 0 and 3
for the second. But also the RHS ranges are different, when the
second requirement (b¤) varies: from 3.5 to 5.0 for the first tableau,
from 0 to 3.5 for the second. If the optimal objective value is
considered as a function of b¤, then this function is piecewise linear
(thus, made up of a finite number of linear pieces), and the slope
changes when b¤=3.5 .
•d Consider adding a new column to the problem . Suppose the
example of 1.3 is modified to:
Minimize 3x?+4x¤ (+10x?)-7x? subject to all x
j
˜0, and
2x?+x¤+x› +x? = 7, x?+x¤-x‹+x? -x? = 5.
(Including slacks x
3
, x
4
and artificial x
5
).
What would z?-c? be for tableau 3 in 1.4 (which was optimal without x?) ?
This is calculated using the shadow costs, as
z?-c?= [-1 5]ã 1õ-(-7) =+1, so no longer optimal. Then the new
Ã-1Õ
column 6 must be calculated, applying the inverse basis matrix,to the
new column, as
ã1 -1õ ã 1õ
=
ã 2õ
.
A simplex iteration would then follow.
Ã-1 2Õ Ã-1Õ Ã-3Õ
•e Consider a change in (one or more) matrix coefficients. The
constraints Ax=b, x˜0 may be written as Bu + Kv = b, where B = matrix
of basic columns, K = matrix of nonbasic columns, u = vector of basic
25
variables, v = vector of nonbasic variables. So the optimum (u*,v*)
satisfies Bu*=b, u*˜0, v*=0. Now perturb B to B+E; this will change u to
u+z, say, satisfying (B + E)(u + z) = b. If the elements of the
matrix E are "small enough", so that z is "small", and the product Ez
can be neglected, then Eu + Bz Ú 0; so z Ú -B
-1
Eu. In the example of
1.4, suppose the coefficient of x? in the first constraint changes from 2
to 2.1 Then

B

=
ã2 1õ
;

E =
ã0.1 0õ
; z
Ú

ã1 -1õã.1 0õã2õ
.
Ã1 1Õ Ã 0 0Õ Ã-1 2Õ Ã 0 0ÕÃ3Õ
1.12 Dual simplex method
In the simplex, requirements must be ˜0; feasibility is kept at all
times, but the optimality conditions are not satisfied until the last
tableau. In the dual simplex, which in fact solves the dual problem,
but using a tableau suitable for the primal, requirements may be
negative; the optimality conditions are satisfied always; but feasibility is
not fulfilled until the last tableau. Consider the example:
D: MIN x?+3x¤ subject to x?,x¤˜0, x?+4x¤˜8, x?+2x¤˜6,2x?+x¤˜6.
Instead of introducing artificial variables then using the simplex method,
the dual simplex may be used, writing the constraints in the form
-x? -4x¤ + x
slack
= -8 (similarly for the others). This gives the first
two tableaus as follows:
-1 -4 1 . . | -8 ö .25 1 -.25 . . | 2
-1 -2 . 1 . | -6 ü ü -.5 . -.5 1 . | -2
-2 -1 . . 1 | -6 -1.75 . -.25 . 1 | -4 ö
-1 -3 0 0 0 | 0 -.25 . -.75 0 0 | 6
In the first tableau, x‹,x›,x? form an infeasible basis. The z
j
-c
j
are
calculated as for the simplex; they are all ˆ0 (optimality conditions satisfied),
so this basis is dual feasible. Choose now the row with most negative
requirement as the pivot row (shown ö). Look at the pivot row and the
z
j
-c
j
row, considering the ratios -1/-1 , -3/-4, 0/1 . The smallest
positive ratio picks out column 2 to enter the basis; the pivot (-4) is
shown bold in the tableau. [In a maximizing problem, choose instead the
negative ratio nearest zero. ] An ordinary simplex iteration, with this
pivot, gives the second tableau shown.
Consider now the parametric programming question from 1.11•c,
where the second requirement (h say) is the parameter, and the
optimum is required, as this parameter varies. The tableau obtained is:
26

Tabl.3 1 . 1 1 -1 | 7-h | (optimal
. 1 -2 -1 2 | -7+2h ö |3.5ˆhˆ7)
0 0 -5 -1 -5 | 21-3h
(Note that -7+2h=0 when h=3.5). If h decreases below 3.5, then x¤
becomes negative. Therefore a dual simplex iteration is done, with the
second row as the pivot row. This leads to the tableau:
1 1 -1 . 1 | h (optimal
. -1 2 1 -2 | 7-2h 0ˆhˆ3.5)
0 0 -3 0 -7 | 3h
(Note that h˜0 and 7-2h˜0 provided that 0ˆhˆ3.5). This parametric
optimization could be continued, for h˜7 or for hˆ0. The dual
simplex is also used in integer linear programming.
1.13 Jumps in shadow costs
Consider the following initial and optimal tableaus for a linear
program. (This example is modified from an example in , page
125, by scaling the rows, so that the largest coefficients in each row
are comparable in size. Such scaling is recommended for
computational accuracy.)
Costs -24 -20 0 0 0 0 100
12 .5 1 1 . . . .
20 1 1 . 1 . . .
24 1.5 1 . . 1 . .
0 1.2 -.8 . . -1 1
0 144 -60 0 0 0 -100 0
6 . 1 1,5 . -.5 . .
2 . . -.5 . -.5 . .
9.6 . . -2.4 . 1.5 1 -1
12 1 . -1 . 1 . .
-408 0 0 -6 0 -14 0 -100
Suppose that the first requirement is perturbed from 12 to 12+h. When
h=-6, the basic x
j
are no longer all ˜ 0; multiplying the optimal inverse
basis matrix by the column vector (12+h, 20, 24, 0) gives
(x¤, x›, x?, x?0 = (-3, 5, 24, 18). The dual simplex can be used here;
two iterations proceed from the tableau on the left to the optimal
tableau on the right, (If the simplex is run again, starting with first
requirement = 6, the same optimum is obtained, but with the rows in a
different order).
27
. 1 1.5 . -.5 . . -3 . -2 -3 . 1 . . 6
. . -.5 1 -.5 . . 5 . -1 -2 1 . . . 8
. . -2.4 . 1.6 1 -1 24 ü ü . 3.2 2.4 . . 1 -1 14.4
1 . -1 . 1 . . 18 1 2 2 . . . . 12
0 0 -6 0 -14 0 -372 0 -28 -48 0 0 0 0 -288
Now consider what happens when the first requirement is
changed to 19. The dual simplex gives an optimum, x
2
=12, x
4
=0, x
3
=3,
x
1
=8; with shadow costs (got from columns 3,4,5,7 ) 0, 0, -18, -2.5.
But now, for comparison, let us solve this problem (with requirements
19,20,24,0) using the simplex. This gives x
2
=12, x
3
=3,x
6
=0,x
1
=8, and
shadow costs 0, -12, -8, 0, thus a different optimum, though with the
same optimal total cost of -432. Why the difference? Observe that
each optimum has some basic x
j
at zero. Using the inverse basis matrix
in each case, a calculation with the optimal inverse basis matrix, and
using here a RHS parameter p, gives:
x
2
. . 1/2 -5/8 19 12+p/2 0
x
4
= . 1 -5/6 5/24 20 = 0-5p/8 ! 0 if -24"p"0
x
3 1 . -2/3 5/12 24+p 3-2p/3 0

x
1
. . 1/3 5/12 0 8+p/3 0
x
2
1 -2 1 . 19 3+p 0
x
3
= . 3 -2 . 20 = 12-2p ! 0 if 0 " p "6
x
6
. -4.8 4 -1 24+p 0+4p
x
1
. -2 2 . 0 8+2p
Thus p=0 is a boundary between the first case (where optimal cost =
-432-18p, -24ˆpˆ0), and the second case (optimal cost = -432-8p,
0ˆp 0, A
T
y + z = c, z > 0, x
i
z
i
= µ (i=1,2,...,n), (PD
µ
)
in which µ is a positive parameter. The system (PD
µ
) can be solved quickly
by Newton's method (see Section 7.3), giving a solution (x*(µ),y*(µ)). The
central path is the graph of x*(µ) against µ. Of course, x*(µ) is only
computes for a chosen set of values of µ = µ
0
> µ
1
> µ
2
> ... tending to 0.
Efficient computation requires a balance between the steps in µ (say, how tg
choose µ
j+1
/µ
j
) and the precision of computing each x*(µ
j
).
Newton's method, to find a zero of a vector function F(w), generates a
sequence w
0
, w
1
, w
2
, ...
F(w
j=1
) Ú F(w
j
) + G(w
j
) (w
j+1
- w
j
) = 0
to determine the step w
j+1
- w
j
. Here G(w
j
) is the gradient of F at w
j
.
44
45

doc_912239524.pdf