Or Lecture Notes
Or Lecture Notes
Or Lecture Notes
ON
MECHANICS OF
OPERATIONS SOLIDS
RESEARCH
Mrs. T. VANAJA
Associate PROFESSOR
ASSISTANT Professor
Mr. A. SOMAIAH
ASSISTANT PROFESSOR
1
UNIT-1: BASICS OF OR AND LINEAR PROGRAMMING
1. INTRODUCTION TO OR
TERMINOLOGY
The British/Europeans refer to "operational research", the Americans to "operations
research" - but both are often shortened to just "OR" (which is the term we will use).
Another term which is used for this field is "management science" ("MS"). The Americans
sometimes combine the terms OR and MS together and say "OR/MS" or "ORMS".
Yet other terms sometimes used are "industrial engineering" ("IE"), "decision science"
("DS"), and “problem solving”.
In recent years there has been a move towards a standardization upon a single term for the
field, namely the term "OR".
“Operations Research (Management Science) is a scientific approach to decision making that
seeks to best design and operate a system, usually under conditions requiring the allocation of
scarce resources.”
A system is an organization of interdependent components that work together to accomplish
the goal of the system.
THE METHODOLOGY OF OR
When OR is used to solve a problem of an organization, the following seven step procedure
should be followed:
Step 1. Formulate the Problem
OR analyst first defines the organization's problem. Defining the problem includes specifying
the organization's objectives and the parts of the organization (or system) that must be studied
before the problem can be solved.
Step 2. Observe the System
Next, the analyst collects data to estimate the values of parameters that affect the
organization's problem. These estimates are used to develop (in Step 3) and evaluate (in Step
4) a mathematical model of the organization's problem.
1
Step 3. Formulate a Mathematical Model of the Problem
The analyst, then, develops a mathematical model (in other words an idealized representation)
of the problem. In this class, we describe many mathematical techniques that can be used to
model systems.
Step 4. Verify the Model and Use the Model for Prediction
The analyst now tries to determine if the mathematical model developed in Step 3 is an
accurate representation of reality. To determine how well the model fits reality, one
determines how valid the model is for the current situation.
Step 5. Select a Suitable Alternative
Given a model and a set of alternatives, the analyst chooses the alternative (if there is one)
that best meets the organization's objectives.
Sometimes the set of alternatives is subject to certain restrictions and constraints. In many
situations, the best alternative may be impossible or too costly to determine.
Step 6. Present the Results and Conclusions of the Study
In this step, the analyst presents the model and the recommendations from Step 5 to the
decision making individual or group. In some situations, one might present several
alternatives and let the organization choose the decision maker(s) choose the one that best
meets her/his/their needs.
After presenting the results of the OR study to the decision maker(s), the analyst may find that
s/he does not (or they do not) approve of the recommendations. This may result from
incorrect definition of the problem on hand or from failure to involve decision maker(s) from
the start of the project. In this case, the analyst should return to Step 1, 2, or 3.
Step 7. Implement and Evaluate Recommendation
If the decision maker(s) has accepted the study, the analyst aids in implementing the
recommendations. The system must be constantly monitored (and updated dynamically as the
environment changes) to ensure that the recommendations are enabling decision maker(s) to
meet her/his/their objectives.
HISTORY OF OR
(Prof. Beasley’s lecture notes)
OR is a relatively new discipline. Whereas 70 years ago it would have been possible to study
mathematics, physics or engineering (for example) at university it would not have been
possible to study OR, indeed the term OR did not exist then. It was only
2
really in the late 1930's that operational research began in a systematic fashion, and it started
in the UK.
Early in 1936 the British Air Ministry established Bawdsey Research Station, on the east
coast, near Felixstowe, Suffolk, as the centre where all pre-war radar experiments for both the
Air Force and the Army would be carried out. Experimental radar equipment was brought up
to a high state of reliability and ranges of over 100 miles on aircraft were obtained.
It was also in 1936 that Royal Air Force (RAF) Fighter Command, charged specifically with
the air defense of Britain, was first created. It lacked however any effective fighter aircraft -
no Hurricanes or Spitfires had come into service - and no radar data was yet fed into its very
elementary warning and control system.
It had become clear that radar would create a whole new series of problems in fighter
direction and control so in late 1936 some experiments started at Biggin Hill in Kent into the
effective use of such data. This early work, attempting to integrate radar data with ground
based observer data for fighter interception, was the start of OR.
The first of three major pre-war air-defense exercises was carried out in the summer of 1937.
The experimental radar station at Bawdsey Research Station was brought into operation and
the information derived from it was fed into the general air-defense warning and control
system. From the early warning point of view this exercise was encouraging, but the tracking
information obtained from radar, after filtering and transmission through the control and
display network, was not very satisfactory.
In July 1938 a second major air-defense exercise was carried out. Four additional radar
stations had been installed along the coast and it was hoped that Britain now had an aircraft
location and control system greatly improved both in coverage and effectiveness. Not so! The
exercise revealed, rather, that a new and serious problem had arisen. This was the need to
coordinate and correlate the additional, and often conflicting, information received from the
additional radar stations. With the out-break of war apparently imminent, it was obvious that
something new - drastic if necessary had to be attempted. Some new approach was needed.
3
aspects of the system should begin immediately. The term "operational research"
[RESEARCH into (military) OPERATIONS] was coined as a suitable description of this new
branch of applied science. The first team was selected from amongst the scientists of the radar
research group the same day.
In the summer of 1939 Britain held what was to be its last pre-war air defense exercise. It
involved some 33,000 men, 1,300 aircraft, 110 antiaircraft guns, 700 searchlights, and 100
barrage balloons. This exercise showed a great improvement in the operation of the air
defense warning and control system. The contribution made by the OR teams was so apparent
that the Air Officer Commander-in-Chief RAF Fighter Command (Air Chief Marshal Sir
Hugh Dowding) requested that, on the outbreak of war, they should be attached to his
headquarters at Stanmore.
On May 15th 1940, with German forces advancing rapidly in France, Stanmore Research
Section was asked to analyze a French request for ten additional fighter squadrons (12 aircraft
a squadron) when losses were running at some three squadrons every two days. They
prepared graphs for Winston Churchill (the British Prime Minister of the time), based upon a
study of current daily losses and replacement rates, indicating how rapidly such a move would
deplete fighter strength. No aircraft were sent and most of those currently in France were
recalled.
This is held by some to be the most strategic contribution to the course of the war made by
OR (as the aircraft and pilots saved were consequently available for the successful air defense
of Britain, the Battle of Britain).
In 1941 an Operational Research Section (ORS) was established in Coastal Command which
was to carry out some of the most well-known OR work in World War II.
Although scientists had (plainly) been involved in the hardware side of warfare (designing
better planes, bombs, tanks, etc) scientific analysis of the operational use of military resources
had never taken place in a systematic fashion before the Second World War. Military
personnel, often by no means stupid, were simply not trained to undertake such analysis.
These early OR workers came from many different disciplines, one group consisted of a
physicist, two physiologists, two mathematical physicists and a surveyor. What such people
brought to their work were "scientifically trained" minds, used to querying assumptions, logic,
exploring hypotheses, devising experiments, collecting data, analyzing numbers, etc. Many
too were of high intellectual caliber (at least four
4
wartime OR personnel were later to win Nobel prizes when they returned to their peacetime
disciplines). By the end of the war OR was well established in the armed services both in the
UK and in the USA. OR started just before World War II in Britain with the establishment of
teams of scientists to study the strategic and tactical problems involved in military operations.
The objective was to find the most effective utilization of limited military resources by the
use of quantitative techniques. Following the end of the war OR spread, although it spread in
different ways in the UK and USA. You should be clear that the growth of OR since it began
(and especially in the last 30 years) is, to a large extent, the result of the increasing power and
widespread availability of computers. Most (though not all) OR involves carrying out a large
number of numeric calculations. Without computers this would simply not be possible.
5
2. BASIC OR CONCEPTS
"OR is the representation of real-world systems by mathematical models together with the use
of quantitative methods (algorithms) for solving such models, with a view to optimizing."
We can also define a mathematical model as consisting of:
Decision variables, which are the unknowns to be determined by the solution to the
model.
Constraints to represent the physical limitations of the system
An objective function
An optimal solution to the model is the identification of a set of variable values which are
feasible (satisfy all the constraints) and which lead to the optimal value of the objective
function.
An optimization model seeks to find values of the decision variables that optimize (maximize
or minimize) an objective function among the set of all values for the decision variables that
satisfy the given constraints.
6
Guessing
To explore the Two Mines problem further we might simply guess (i.e. use our judgment)
how many days per week to work and see how they turn out.
work one day a week on X, one day a week on Y
This does not seem like a good guess as it results in only 7 tones a day of high- grade,
insufficient to meet the contract requirement for 12 tones of high-grade a day. We say that
such a solution is infeasible.
work 4 days a week on X, 3 days a week on Y
This seems like a better guess as it results in sufficient ore to meet the contract. We say that
such a solution is feasible. However it is quite expensive (costly).
We would like a solution which supplies what is necessary under the contract at minimum
cost. Logically such a minimum cost solution to this decision problem must exist. However
even if we keep guessing we can never be sure whether we have found this minimum cost
solution or not. Fortunately our structured approach will enable us to find the minimum cost
solution.
Solution
What we have is a verbal description of the Two Mines problem. What we need to do is to
translate that verbal description into an equivalent mathematical description.
In dealing with problems of this kind we often do best to consider them in the order:
Variables
Constraints
Objective
This process is often called formulating the problem (or more strictly formulating a
mathematical representation of the problem).
Variables
These represent the "decisions that have to be made" or the "unknowns". We have
two decision variables in this problem:
x = number of days per week mine X is operated
y = number of days per week mine Y is operated Note
here that x ≥ 0 and y ≥ 0.
7
Constraints
It is best to first put each constraint into words and then express it in a mathematical form.
ore production constraints - balance the amount produced with the
quantity required under the smelting plant contract
Ore
High 6x + 1y ≥ 12
Medium 3x + 1y ≥ 8
Low 4x + 6y ≥ 24
days per week constraint - we cannot work more than a certain maximum
number of days a week e.g. for a 5 day week we have
x≤5
y≤5
Inequality constraints
Note we have an inequality here rather than an equality. This implies that we may produce
more of some grade of ore than we need. In fact we have the general rule: given a choice
between an equality and an inequality choose the inequality
For example - if we choose an equality for the ore production constraints we have the three
equations 6x+y=12, 3x+y=8 and 4x+6y=24 and there are no values of x and y which satisfy all
three equations (the problem is therefore said to be "over- constrained"). For example the
values of x and y which satisfy 6x+y=12 and 3x+y=8 are x=4/3 and y=4, but these values do
not satisfy 4x+6y=24.
The reason for this general rule is that choosing an inequality rather than an equality gives us
more flexibility in optimizing (maximizing or minimizing) the objective (deciding values for
the decision variables that optimize the objective).
Implicit constraints
Constraints such as days per week constraint are often called implicit constraints because they
are implicit in the definition of the variables.
Objective
Again in words our objective is (presumably) to minimize cost which is given by 180x +
160y
8
Hence we have the complete mathematical representation of the problem:
minimize
180x + 160y
subject to
6x + y ≥ 12
3x + y ≥ 8 4x
+ 6y ≥ 24 x ≤
5
y≤5
x, y ≥ 0
Some notes
The mathematical problem given above has the form
all variables continuous (i.e. can take fractional values)
a single objective (maximize or minimize)
the objective and constraints are linear i.e. any term is either a constant or a constant
multiplied by an unknown (e.g. 24, 4x, 6y are linear terms but xy or x2 is a non-linear
term)
Any formulation which satisfies these three conditions is called a linear program (LP). We
have (implicitly) assumed that it is permissible to work in fractions of days - problems where
this is not permissible and variables must take integer values will be dealt with under Integer
Programming (IP).
Discussion
This problem was a decision problem.
We have taken a real-world situation and constructed an equivalent mathematical
representation - such a representation is often called a mathematical model of the real-world
situation (and the process by which the model is obtained is called formulating the model).
Just to confuse things the mathematical model of the problem is sometimes called the
formulation of the problem.
Having obtained our mathematical model we (hopefully) have some quantitative method
which will enable us to numerically solve the model (i.e. obtain a numerical solution) - such a
quantitative method is often called an algorithm for solving the model.
Essentially an algorithm (for a particular model) is a set of instructions which, when followed
in a step-by-step fashion, will produce a numerical solution to that model.
9
Our model has an objective, that is something which we are trying to optimize.
Having obtained the numerical solution of our model we have to translate that
solution back into the real-world situation.
"OR is the representation of real-world systems by mathematical models together with the
use of quantitative methods (algorithms) for solving such models, with a view to
optimizing."
10
3. LINEAR PROGRAMMING
It can be recalled from the Two Mines example that the conditions for a mathematical model
to be a linear program (LP) were:
all variables continuous (i.e. can take fractional values)
a single objective (minimize or maximize)
the objective and constraints are linear i.e. any term is either a constant or a
constant multiplied by an unknown.
LP's are important - this is because:
many practical problems can be formulated as LP's
there exists an algorithm (called the simplex algorithm) which enables us to solve
LP's numerically relatively easily
We will return later to the simplex algorithm for solving LP's but for the moment we will
concentrate upon formulating LP's.
Some of the major application areas to which LP can be applied are:
Work scheduling
Production planning & Production process
Capital budgeting
Financial planning
Blending (e.g. Oil refinery management)
Farm planning
Distribution
Multi-period decision problems
o Inventory model
o Financial models
o Work scheduling
Note that the key to formulating LP's is practice. However a useful hint is that common
objectives for LP's are maximize profit/minimize cost.
11
There are four basic assumptions in LP:
Proportionality
o The contribution to the objective function from each decision variable is
proportional to the value of the decision variable (The contribution to the
objective function from making four soldiers (4 $3=$12) is exactly four times
the contribution to the objective function from making one soldier ($3))
o The contribution of each decision variable to the LHS of each constraint is
proportional to the value of the decision variable (It takes exactly three times
as many finishing hours (2hrs 3=6hrs) to manufacture three soldiers as it
takes to manufacture one soldier (2 hrs))
Additivity
o The contribution to the objective function for any decision variable is
independent of the values of the other decision variables (No matter what the
value of train (x2), the manufacture of soldier (x1) will always contribute 3x1
dollars to the objective function)
o The contribution of a decision variable to LHS of each constraint is
independent of the values of other decision variables (No matter what the value
of x1, the manufacture of x2 uses x2 finishing hours and x2 carpentry hours)
1st implication: The value of objective function is the sum of the
contributions from each decision variables.
2nd implication: LHS of each constraint is the sum of the
contributions from each decision variables.
Divisibility
o Each decision variable is allowed to assume fractional values. If we actually
can not produce a fractional number of decision variables, we use IP (It is
acceptable to produce 1.69 trains)
Certainty
o Each parameter is known with certainty
12
FORMULATING LP
Giapetto Example
(Winston 3.1, p. 49)
Giapetto's wooden soldiers and trains. Each soldier sells for $27, uses $10 of raw materials
and takes $14 of labor & overhead costs. Each train sells for $21, uses $9 of raw materials,
and takes $10 of overhead costs. Each soldier needs 2 hours finishing and 1 hour carpentry;
each train needs 1 hour finishing and 1 hour carpentry. Raw materials are unlimited, but only
100 hours of finishing and 80 hours of carpentry are available each week. Demand for trains
is unlimited; but at most 40 soldiers can be sold each week. How many of each toy should be
made each week to maximize profits?
Answer
Decision variables completely describe the decisions to be made (in this case, by Giapetto).
Giapetto must decide how many soldiers and trains should be manufactured each week. With
this in mind, we define:
x1 = the number of soldiers produced per week
x2 = the number of trains produced per week
Objective function is the function of the decision variables that the decision maker wants to
maximize (revenue or profit) or minimize (costs). Giapetto can concentrate on maximizing
the total weekly profit (z).
Here profit equals to (weekly revenues) – (raw material purchase cost) – (other variable
costs). Hence Giapetto’s objective function is:
Maximize z = 3x1 + 2x2
Constraints show the restrictions on the values of the decision variables. Without constraints
Giapetto could make a large profit by choosing decision variables to be very large. Here there
are three constraints:
Finishing time per week
Carpentry time per week
Weekly demand for soldiers
Sign restrictions are added if the decision variables can only assume nonnegative values
(Giapetto can not manufacture negative number of soldiers or trains!)
13
All these characteristics explored above give the following Linear Programming
(LP) model
max z = 3x1 + 2x2 (The Objective function)
s.t. 2x1 + x2 100 (Finishing constraint)
x1 + x2 80 (Carpentry constraint)
x1 40 (Constraint on demand for soldiers)
x1, x2 > 0 (Sign restrictions)
A value of (x1, x2) is in the feasible region if it satisfies all the constraints and sign
restrictions.
Graphically and computationally we see the solution is (x1, x2) = (20, 60) at which z =
180. (Optimal solution)
Report
The maximum profit is $180 by making 20 soldiers and 60 trains each week. Profit is limited
by the carpentry and finishing labor available. Profit could be increased by buying more
labor.
Advertisement Example
(Winston 3.2, p.61)
Dorian makes luxury cars and jeeps for high-income men and women. It wishes to advertise
with 1 minute spots in comedy shows and football games. Each comedy spot costs $50K and
is seen by 7M high-income women and 2M high-income men. Each football spot costs $100K
and is seen by 2M high-income women and 12M high-income men. How can Dorian reach
28M high-income women and 24M high- income men at the least cost?
Answer
The decision variables are
x1 = the number of comedy spots
x2 = the number of football spots The
model of the problem:
min z = 50x1 + 100x2
st 7x1 + 2x2 28
2x1 + 12x2
24
x1, x2 0
14
The graphical solution is z = 320 when (x1, x2) = (3.6, 1.4). From the graph, in this problem
rounding up to (x1, x2) = (4, 2) gives the best integer solution.
Report
The minimum cost of reaching the target audience is $400K, with 4 comedy spots and 2
football slots. The model is dubious as it does not allow for saturation after repeated viewings.
Diet Example
(Winston 3.4., p. 70)
Ms. Fidan’s diet requires that all the food she eats come from one of the four “basic food
groups“. At present, the following four foods are available for consumption: brownies,
chocolate ice cream, cola, and pineapple cheesecake. Each brownie costs 0.5$, each scoop of
chocolate ice cream costs 0.2$, each bottle of cola costs 0.3$, and each pineapple cheesecake
costs 0.8$. Each day, she must ingest at least 500 calories, 6 oz of chocolate, 10 oz of sugar,
and 8 oz of fat. The nutritional content per unit of each food is shown in Table. Formulate an
LP model that can be used to satisfy her daily nutritional requirements at minimum cost.
Answer
The decision variables:
x1: number of brownies eaten daily
x2: number of scoops of chocolate ice cream eaten daily
x3: bottles of cola drunk daily
x4: pieces of pineapple cheesecake eaten daily The
objective function (the total cost of the diet in cents):
min w = 50x1 + 20x2 + 30x3 + 80x4
Constraints:
400x1 + 200x2 + 150x3 + 500x4 > 500 (daily calorie intake)
3x1 + 2x2 > 6 (daily chocolate intake)
2x1 + 2x2 + 4x3 + 4x4 > 10 (daily sugar intake)
15
2x1 + 4x2 + x3 + 5x4 > 8 (daily fat intake)
xi ≥ 0, i = 1, 2, 3, 4 (Sign restrictions!)
Report
The minimum cost diet incurs a daily cost of 90 cents by eating 3 scoops of chocolate and
drinking 1 bottle of cola (w = 90, x2 = 3, x3 = 1)
Answer
The decision variables are xi (# of employees starting on day i)
Mathematically we must
min z = x1 + x2 + x3 + x4 + x5 + x6 + x7
s.t. x1 + x4 + x5 + x6 + x7 ≥ 17
x1 + x2 + x5 + x6 + x7 ≥ 13
x1 + x2 + x3 + x6 + x7 ≥ 15
x1 + x2 + x3 + x4 + x7 ≥ 19
x1 + x2 + x3 + x4 + x5 ≥ 14
+ x2 + x3 + x4 + x5 + x6 ≥ 16
+ x3 + x4 + x5 + x6 + x7 ≥ 11
xt ≥ 0, t
The solution is (xi) = (4/3, 10/3, 2, 22/3, 0, 10/3, 5) giving z = 67/3.
We could round this up to (xi) = (2, 4, 2, 8, 0, 4, 5) giving z = 25 (may be wrong!).
However restricting the decision var.s to be integers and using Lindo again gives (xi) =
(4, 4, 2, 6, 0, 4, 3) giving z = 23.
Sailco Example
(Winston 3.10, p. 99)
Sailco must determine how many sailboats to produce in the next 4 quarters. The demand is
known to be 40, 60, 75, and 25 boats. Sailco must meet its demands. At the beginning of the
1st quarter Sailco starts with 10 boats in inventory. Sailco can produce up to 40 boats with
regular time labor at $400 per boat, or additional boats at
16
$450 with overtime labor. Boats made in a quarter can be used to meet that quarter's demand
or held in inventory for the next quarter at an extra cost of $20.00 per boat. Answer
The decision variables are for t = 1,2,3,4
xt = # of boats in quarter t built in regular time
yt = # of boats in quarter t built in overtime For
convenience, introduce variables:
it = # of boats in inventory at the end quarter t
dt = demand in quarter t
We are given that d1 = 40, d2 = 60, d3 = 75, d4 = 25, i0 =10
xt ≤ 40, t
By logic it = it-1+ xt + yt - dt, t.
Demand is met iff it ≥ 0, t
(Sign restrictions xt, yt ≥ 0, t)
We need to minimize total cost z subject to these three sets of conditions where
z = 400 (x1 + x2 + x3 + x4) + 450 (y1 + y2 + y3 + y4) + 20 (i1 + i2 + i3 + i4)
Report:
Lindo reveals the solution to be (x1, x2, x3, x4) = (40, 40, 40, 25) and (y1, y2, y3, y4) = (0, 10,
35, 0) and the minimum cost of $78450.00 is achieved by the schedule
Q1 Q2 Q3 Q4
Regular time (xt) 40 40 40 25
Overtime (yt) 0 10 35 0
Inventory (it) 10 10 0 0 0
Demand (dt) 40 60 75 25
Example 1. Giapetto
(Winston 3.1, p. 49)
Since the Giapetto LP has two variables, it may be solved graphically.
Answer
The feasible region is the set of all points satisfying the constraints. max z
= 3x1 + 2x2
s.t. 2x1 + x2 ≤ 100 (Finishing constraint)
x1 + x2 ≤ 80 (Carpentry constraint)
x1 ≤ 40 (Demand constraint)
x1, x2 ≥ 0 (Sign restrictions)
The set of points satisfying the LP is bounded by the five sided polygon DGFEH. Any point
on or in the interior of this polygon (the shade area) is in the feasible region. Having identified
the feasible region for the LP, a search can begin for the optimal solution which will be the
point in the feasible region with the largest z-value (maximization problem).
To find the optimal solution, a line on which the points have the same z-value is graphed. In a
max problem, such a line is called an isoprofit line while in a min problem, this is called the
isocost line. (The figure shows the isoprofit lines for z = 60, z = 100, and z = 180).
X2
B
100
finishing Feasible
D constraint Region
demand
G constraint
z=
80
100 carpentry
constraint
F z=
z= 180A
E C
60
60
40
20
H
10 20 40 50 60 80 X1
In the unique optimal solution case, isoprofit line last hits a point (vertex - corner) before
leaving the feasible region.
The optimal solution of this LP is point G where (x1, x2) = (20, 60) giving z = 180.
A constraint is binding (active, tight) if the left-hand and right-hand side of the constraint are
equal when the optimal values of the decision variables are substituted into the constraint.
A constraint is nonbinding (inactive) if the left-hand side and the right-hand side of the
constraint are unequal when the optimal values of the decision variables are substituted into
the constraint.
In Giapetto LP, the finishing and carpentry constraints are binding. On the other hand the
demand constraint for wooden soldiers is nonbinding since at the optimal solution x1 < 40 (x1
= 20).
Example 2. Advertisement
(Winston 3.2, p. 61)
Since the Advertisement LP has two variables, it may be solved graphically.
Answer
The feasible region is the set of all points satisfying the constraints. min z
= 50x1 + 100x2
s.t. 7x1 + 2x2 ≥ 28 (high income women)
2x1 + 12x2 ≥ 24 (high income men) x1,
x2 ≥ 0
X2
X2
14
14 B
B
14
High-income women
High-income women constraint
constraint
12
12
12
10
10
10
Feasible
Feasible
Region
Region
8
8
6
6
zz==600
600
600
4
4 zz =
= 320
320
320
High-income men
High-income men constraint
constraint
2
2 E
E
D
D
A
A C
C
2
2 4 6 8 10
10 12
12 14
14 X1
X1
4 6 8 10 12 14
Since Dorian wants to minimize total advertising costs, the optimal solution to the problem
is the point in the feasible region with the smallest z value.
An isocost line with the smallest z value passes through point E and is the optimal solution
at x1 = 3.6 and x2 = 1.4 giving z = 320.
Both the high-income women and high-income men constraints are satisfied, both
constraints are binding.
Example 3. Two Mines
min 180x + 160y
st 6x + y ≥ 12
3x + y ≥ 8 4x
+ 6y ≥ 24 x ≤
5
y≤5
x, y ≥ 0
Answer
Optimal sol’n is 765.71. 1.71 days mine X and 2.86 days mine Y are operated.
100 B
80 D
E A C
x1
H 40 50 80
Steps
1. Convert the LP to standard form
2. Obtain a basic feasible solution (bfs) from the standard form
3. Determine whether the current bfs is optimal. If it is optimal, stop.
4. If the current bfs is not optimal, determine which nonbasic variable should become a
basic variable and which basic variable should become a nonbasic variable to find a
new bfs with a better objective function value
5. Go back to Step 3.
Related concepts:
Standard form: all constraints are equations and all variables are nonnegative
bfs: any basic solution where all variables are nonnegative
Nonbasic variable: a chosen set of variables where variables equal to 0
Basic variable: the remaining variables that satisfy the system of equations at the
standard form
Example 1. Dakota Furniture
(Winston 4.3, p. 134)
Dakota Furniture makes desks, tables, and chairs. Each product needs the limited resources of
lumber, carpentry and finishing; as described in the table. At most 5 tables can be sold per
week. Maximize weekly revenue.
LP Model:
Let x1, x2, x3 be the number of desks, tables and chairs produced.
Let the weekly profit be $z. Then, we must
max z = 60x1 + 30x2 + 20x3
s.t. 8x1 + 6x2 + x3 ≤ 48
4x1 + 2x2 + 1.5 x3 ≤ 20
2x1 + 1.5x2 + .5 x3 ≤ 8
x2 ≤ 5
x1, x2, x3 ≥ 0
Check optimality of current bfs. Repeat steps until an optimal solution is reached
We increase z fastest by making x3 non-zero (i.e. x3 enters).
x3 can be increased to at most x3 = 8, when s2 = 0 ( i.e. s2 leaves.)
Report: Dakota furniture’s optimum weekly profit would be 280$ if they produce 2 desks
and 8 chairs.
Initial tableau:
z x1 x2 x3 s1 s2 s3 s4 RHS BV Ratio
1 -60 -30 -20 0 0 0 0 0 z=0
0 8 6 1 1 0 0 0 48 s1 = 48 6
0 4 2 1.5 0 1 0 0 20 s2 = 20 5
0 2 1.5 0.5 0 0 1 0 8 s3 = 8 4
0 0 1 0 0 0 0 1 5 s4 = 5 -
First tableau:
z x1 x2 x3 s1 s2 s3 s4 RHS BV Ratio
1 0 15 -5 0 0 30 0 240 z = 240
0 0 0 -1 1 0 -4 0 16 s1 = 16 -
0 0 -1 0.5 0 1 -2 0 4 s2 = 4 8
0 1 0.75 0.25 0 0 0.5 0 4 x1 = 4 16
0 0 1 0 0 0 0 1 5 s4 = 5 -
z x1 x2 x3 s1 s2 s3 s4 RHS BV Ratio
1 0 0 0 0 10 10 0 280 z=280
0 0 -2 0 1 2 -8 0 24 s1=24 -
0 0 -2 1 0 2 -4 0 8 x3=8 -
0 1 1.25 0 0 -0.5 1.5 0 2 x1=2 2/1.25
0 0 1 0 0 0 0 1 5 s4=5 5/1
x1 2 0 2c
x2 =c 0 + (1 – c) 1.6 = 1.6 – 1.6c
x3 8 11.2 11.2 – 3.2c
z x1 x2 x3 s1 s2 z RHS BV Ratio
1 0 2 -9 0 12 4 100 z=100
0 0 1 -6 1 6 -1 20 x4=20 None
0 1 1 -1 0 1 0 5 x1=5 None
Steps
1. Modify the constraints so that the RHS of each constraint is nonnegative (This requires
that each constraint with a negative RHS be multiplied by -1. Remember that if you
multiply an inequality by any negative number, the direction of the inequality is
reversed!). After modification, identify each constraint as a ≤, ≥ or = constraint.
2. Convert each inequality constraint to standard form (If constraint i is a ≤ constraint, we
add a slack variable si; and if constraint i is a ≥ constraint, we subtract an excess variable
ei).
3. Add an artificial variable ai to the constraints identified as ≥ or = constraints at the end of
Step 1. Also add the sign restriction ai ≥ 0.
4. Let M denote a very large positive number. If the LP is a min problem, add (for each
artificial variable) Mai to the objective function. If the LP is a max problem, add (for each
artificial variable) -Mai to the objective function.
5. Since each artificial variable will be in the starting basis, all artificial variables must be
eliminated from row 0 before beginning the simplex. Now solve the transformed problem
by the simplex (In choosing the entering variable, remember that M is a very large
positive number!).
If all artificial variables are equal to zero in the optimal solution, we have found the
optimal solution to the original problem.
If any artificial variables are positive in the optimal solution, the original problem is
infeasible!!!
Example 1. Oranj Juice
(Winston 4.10, p. 164)
Bevco manufactures an orange flavored soft drink called Oranj by combining orange soda
and orange juice. Each ounce of orange soda contains 0.5 oz of sugar and 1 mg of vitamin C.
Each ounce of orange juice contains 0.25 oz of sugar and 3 mg of vitamin C. It costs Bevco
2¢ to produce an ounce of orange soda and 3¢ to produce an ounce of orange juice.
Marketing department has decided that each 10 oz bottle of Oranj must contain at least 20 mg
of vitamin C and at most 4 oz of sugar. Use LP to determine how Bevco can meet marketing
dept.’s requirements at minimum cost. LP Model:
Let x1 and x2 be the quantity of ounces of orange soda and orange juice (respectively) in a
bottle of Oranj.
min z = 2x1 + 3x2
s.t. 0.5 x1 + 0.25 x2 ≤ 4 (sugar const.)
x1+ 3 x2 ≥ 20 (vit. C const.)
x1+ x2 = 10 (10 oz in bottle)
x1, x2 ≥ 0
Initial tableau:
z x1 x2 s1 e2 a2 a3 RHS BV Ratio
1 2M-2 4M-3 0 -M 0 0 30M z=30M
0 0.5 0.25 1 0 0 0 4 s1=4 16
0 1 3 0 -1 1 0 20 a2=20 20/3*
0 1 1 0 0 0 1 10 a3=10 10
In a min problem, entering variable is the variable that has the “most positive” coefficient
in row 0!
First tableau:
z x1 x2 s1 e2 a2 a3 RHS BV Ratio
1 (2M-3)/3 0 0 (M-3)/3 (3-4M)/3 0 20+3.3M z
0 5/12 0 1 1/12 -1/12 0 7/3 s1 28/5
0 1/3 1 0 -1/3 1/3 0 20/3 x2 20
0 2/3 0 0 1/3 -1/3 1 10/3 a3 5*
Optimal tableau:
z x1 x2 s1 e2 a2 a3 RHS BV
1 0 0 0 -1/2 (1-2M)/2 (3-2M)/2 25 z=25
0 0 0 1 -1/8 1/8 -5/8 1/4 s1=1/4
0 0 1 0 -1/2 1/2 -1/2 5 x2=5
0 1 0 0 1/2 -1/2 3/2 5 x1=5
Report:
In a bottle of Oranj, there should be 5 oz orange soda and 5 oz orange juice. In this
case the cost would be 25¢.
Example 2. Modified Oranj Juice
Consider Bevco’s problem. It is modified so that 36 mg of vitamin C are required. Related
LP model is given as follows:
Let x1 and x2 be the quantity of ounces of orange soda and orange juice (respectively) in a
bottle of Oranj.
min z = 2x1 + 3x2
s.t. 0.5 x1 + 0.25 x2 ≤ 4 (sugar const.)
x1+ 3 x2 ≥ 36 (vit. C const.)
x1+ x2 = 10 (10 oz in bottle)
x1, x2 ≥ 0
Solving with Big M method:
Initial tableau:
z x1 x2 s1 e2 a2 a3 RHS BV Ratio
1 2M-2 4M-3 0 -M 0 0 46M z=46M
0 0.5 0.25 1 0 0 0 4 s1=4 16
0 1 3 0 -1 1 0 36 a2=36 36/3
0 1 1 0 0 0 1 10 a3=10 10
Optimal tableau:
z x1 x2 s1 e2 a2 a3 RHS BV
1 1-2M 0 0 -M 0 3-4M 30+6M z=30+6M
0 1/4 0 1 0 0 -1/4 3/2 s1=3/2
0 -2 0 0 -1 1 -3 6 a2=6
0 1 1 0 0 0 1 10 x2=10
An artificial variable (a2) is BV so the original LP has no feasible solution
Report:
It is impossible to produce Oranj under these conditions.
DUALITY
Primal – Dual
Associated with any LP is another LP called the dual. Knowledge of the dual provides
interesting economic and sensitivity analysis insights. When taking the dual of any LP, the
given LP is referred to as the primal. If the primal is a max problem, the dual will be a min
problem and vice versa.
Finding the Dual of an LP
The dual of a normal max problem is a normal min problem.
Normal max problem is a problem in which all the variables are required to be
nonnegative and all the constraints are ≤ constraints.
Normal min problem is a problem in which all the variables are required to be
nonnegative and all the constraints are ≥ constraints.
Similarly, the dual of a normal min problem is a normal max problem.
Economic Interpretation
When the primal is a normal max problem, the dual variables are related to the value of
resources available to the decision maker. For this reason, dual variables are often referred to
as resource shadow prices.
Example
PRIMAL
Let x1, x2, x3 be the number of desks, tables and chairs produced. Let the weekly profit be $z.
Then, we must
SENSITIVITY ANALYSIS
Reduced Cost
For any nonbasic variable, the reduced cost for the variable is the amount by which the
nonbasic variable's objective function coefficient must be improved before that variable will
become a basic variable in some optimal solution to the LP.
If the objective function coefficient of a nonbasic variable xk is improved by its reduced cost,
then the LP will have alternative optimal solutions at least one in which xk is a basic variable,
and at least one in which xkis not a basic variable.
If the objective function coefficient of a nonbasic variable xk is improved by more than its
reduced cost, then any optimal solution to the LP will have xk as a basic variable and xk > 0.
Reduced cost of a basic variable is zero (see definition)!
Shadow Price
We define the shadow price for the ith constraint of an LP to be the amount by which the
optimal z value is "improved" (increased in a max problem and decreased in a min problem)
if the RHS of the ith constraint is increased by 1.
This definition applies only if the change in the RHS of the constraint leaves the current basis
optimal!
A ≥ constraint will always have a nonpositive shadow price; a ≤ constraint will always have a
nonnegative shadow price.
Conceptualization
max z = 5 x1 + x2 + 10x3
x1 + x3 ≤ 100
x2 ≤ 1
All variables ≥ 0
This is a very easy LP model and can be solved manually without utilizing Simplex.
x2 = 1 (This variable does not exist in the first constraint. In this case, as the problem is a
maximization problem, the optimum value of the variable equals the RHS value of the second
constraint).
x1 = 0, x3 = 100 (These two variables do exist only in the first constraint and as the objective
function coefficient of x3 is greater than that of x1, the optimum value of x3 equals the RHS
value of the first constraint).
Hence, the optimal solution is as follows:
z = 1001, [x1, x2, x3] = [0, 1, 100]
MAX 5 X1 + X2 + 10 X3
SUBJECT TO
2) X1 + X3 <= 100
3) X2 <= 1
END
Lindo output reveals the reduced costs of x1, x2, and x3 as 5, 0, and 0 respectively.
In the maximization problems, the reduced cost of a non-basic variable can also be read from
the allowable increase value of that variable at obj. coefficient ranges. Here, the
corresponding value of x1 is 5.
In the minimization problems, the reduced cost of a non-basic variable can also be read from
the allowable decrease value of that variable at obj. coefficient ranges.
The same Lindo output reveals the shadow prices of the constraints in the "dual price"
section:
Here, the shadow price of the first constraint (Row 2) equals 10. The
shadow price of the second constraint (Row 3) equals 1.
max z = 60 x1 30 x2 20x3
8 x1 + 6 x2 + x3 + s1 = 48 Lumber
4 x1 + 2 x2 +1.5 x3 + s2 = 20 Finishing
2 x1 +1.5 x2 + .5 x3 + s3 = 8 Carpentry
x2 + s4 = 5 Demand
The optimal solution was:
Analysis 1
Suppose available finishing time changes from 20 20+ , then we have the system:
Substituting in:
Analysis 2
What happens if revenue from desks changes to $60+ ? For small revenue increases by
2 (as we are making 2 desks currently). But how large an increase is possible?
The new revenue is:
z' = (60+ )x1+30x2+20x3 = z+ x1
= (280 - 5x2 - 10s2 - 10s3) + (2 - 1.25x2 + .5s2 - 1.5s3)
= 280 + 2 - (5 + 1.25 )x2 - (10-.5 )s2 - (10 + 1.5 )s3
So the top line in the final system would be:
z' + (5 + 1.25 )x2 + (10 - .5 )s2 + (10 + 1.5 )s3 = 280 + 2
Provided all terms in this row are we are still optimal.
For -4 20, the current production schedule is still optimal.
Analysis 3
If revenue from a non-basic variable changes, the revenue is
z’ = 60x1 + (30 + )x2 + 20x3 = z + x2
= 280 - 5x2 - 10s2 - 10s3 + x2
= 280 - (5 - )x2 - 10s2 - 10s3
The current solution is optimal for 5. But when 5 or the revenue per table is
increased past $35, it becomes better to produce tables. We say the reduced cost of tables is
$5.00.
If total supply equals total demand then the problem is said to be a balanced
transportation problem.
Let xij = number of units shipped from supply point i to demand point j
Decision variable xij: number of units shipped from supply point i to
demand point j
then the general LP representation of a transportation problem is
Answer
Representation of the problem as a LP model
xij: number of (million) kwh produced at plant i and sent to city j.
min z = 8 x11 + 6 x12 + 10 x13 + 9 x14 + 9 x21 + 12 x22 + 13 x23 + 7 x24 + 14 x31 + 9
x32 + 16 x33 + 5 x34
s.t. x11 + x12 + x13 + x14 < 35 (supply constraints)
x21 + x22 + x23 + x24 < 50
x31 + x32 + x33 + x34 < 40
x11 + x21 + x31 > 45 (demand constraints)
x12 + x22 + x32 > 20
x13 + x23 + x33 > 30
x14 + x24 + x34 > 30
xij > 0 (i = 1, 2, 3; j = 1, 2, 3, 4)
Formulation of the transportation problem
City 1 City 2 City 3 City 4 SUPPLY
8 6 10 9
Plant 1 35
9 12 13 7
Plant 2 50
14 9 16 5
Plant 3 40
DEMAND 45 20 30 30 125
Total supply & total demand both equal 125: “balanced transport’n problem”.
DEMAND 40 20 30 30 5 125
For a balanced transportation problem, general LP representation may be written as: min i
j cij xij
xij > 0
To find a bfs to a balanced transportation problem, we need to make the following important
observation:
If a set of values for the xij’s satisfies all but one of the constraints of a balanced
transportation problem, the values for the xij’s will automatically satisfy the other constraint.
This observation shows that when we solve a balanced transportation, we may omit from
consideration any one of the problem’s constraints and solve an LP having m+n- 1 constraints.
We arbitrarily assume that the first supply constraint is omitted from consideration. In trying
to find a bfs to the remaining m+n-1 constraints, you might think that any collection of m+n-1
variables would yield a basic solution. But this is not the case: If the m+n-1 variables yield a
basic solution, the cells corresponding to this set contain no loop.
An ordered sequence of at least four different cells is called a loop if
Any two consecutives cells lie in either the same row or same column
No three consecutive cells lie in the same row or column
The last cell in the sequence has a row or column in common with the first cell in the
sequence
There are three methods that can be used to find a bfs for a balanced transportation problem:
1. Northwest Corner method
2. Minimum cost method
3. Vogel’s method
Example 1.
For example consider a balanced transportation problem given below (We omit the costs
because they are not needed to find a bfs!).
2 4 2 1
Total demand equals total supply (9): this is a balanced transport’n problem.
2 3
X 4 2 1
2 3 X
X 1 2 1
2 3 X
X 0 2 1
2 3 X
0 2 1 X
X 0 2 1
NWC method assigned values to m+n-1 (3+4-1 = 6) variables. The variables chosen by NWC
method can not form a loop, so a bfs is obtained.
Example 2.
2 3 5 6
5
2 1 3 5
10
3 8 4 6
15
12 8 4 6
2 3 5 6
2 1 3 5
8
3 8 4 6
2 3 5 6
5
2 1 3 5
X
2 8
3 8 4 6
15
10 X 4 6
2 3 5 6
X
5
2 1 3 5
X
2 8
3 8 4 6 15
5 X 4 6
2 3 5 6
X
5
2 1 3 5
X
2 8
3 8 4 6 10
5 4 6
5 X 4 6
Vogel’s Method
Begin by computing for each row and column a penalty equal to the difference between the
two smallest costs in the row and column. Next find the row or column with the largest
penalty. Choose as the first basic variable the variable in this row or column that has the
smallest cost. As described in the NWC method, make this variable as large as possible, cross
out row or column, and change the supply or demand associated with the basic variable (See
Northwest Corner Method for the details!). Now recomputed new penalties (using only cells
that do not lie in a crossed out row or column), and repeat the procedure until only one
uncrossed cell remains. Set this variable equal to the supply or demand associated with the
variable, and cross out the variable’s row and column.
Example 3.
Row
Supply penalty
6 7 8 10 7-6=1
15 80 78 15 78-15=63
Demand 15 5 5
Column
15-6=9 80-7=73 78-8=70
penalty
Row
Supply penalty
6 7 8 5 8-6=2
5
15 80 78 15 78-15=63
Demand 15 X 5
Column
15-6=9 --------------------- 78-8=70
penalty
Row
Supply penalty
6 7 8 X -
5 5
15 80 78 15 -
Demand 15 X 0
Column
15-6=9 - -
penalty
6 7 8
X
5 5
15 80 78
15 0
15
Demand 15 X 0
THE TRANSPORTATION SIMPLEX METHOD
For a maximization problem, proceed as stated, but replace Step 4 by the following step:
If ui + vj – cij ≥ 0 for all nonbasic variables, then the current bfs is optimal. Otherwise, enter
the variable with the most negative ui + vj – cij into the basis using the pivoting procedure.
This yields a new bfs. Return to Step 3.
Pivoting procedure
1. Find the loop (there is only one possible loop!) involving the entering variable
(determined at step 4 of the transport’n simplex method) and some or all of the basic
variables.
2. Counting only cells in the loop, label those that are an even number (0, 2, 4, and so on) of
cells away from the entering variable as even cells. Also label those that are an odd
number of cells away from the entering variable as odd cells.
3. Find the odd cell whose variable assumes the smallest value. Call this value . The
variable corresponding to this odd cell will leave the basis. To perform the pivot, decrease
the value of each odd cell by and increase the value of each even cell by . The values
of variables not in the loop remain unchanged. The pivot is now complete. If = 0, the
entering variable will equal 0, and odd variable that has a current value of 0 will leave the
basis.
Example 1. Powerco
The problem is balanced (total supply equals total demand).
When the NWC method is applied to the Powerco example, the bfs in the following table is
obtained (check: there exist m+n–1=6 basic variables).
City 1 City 2 City 3 City 4 SUPPLY
8 6 10 9
Plant 1 35
35
9 12 13 7
Plant 2 50
10 20 20
14 9 16 5
Plant 3 40
10 30
DEMAND 45 20 30 30 125
u1 = 0
u1 + v1 = 8 yields v1 = 8
u2 + v1 = 9 yields u2 = 1
u2 + v2 = 12 yields v2 = 11
u2 + v3 = 13 yields v3 = 12
u3 + v3 = 16 yields u3 = 4 u3
+ v4 = 5 yields v4 = 1
For each nonbasic variable, we now compute ĉij = ui + vj – cij ĉ12 =
0 + 11 – 6 = 5
ĉ13 = 0 + 12 – 10 = 2
ĉ14 = 0 + 1 – 9 = -8
ĉ24 = 1 + 1 – 7 = -5
ĉ31 = 4 + 8 – 14 = -2
ĉ32 = 4 + 11 – 9 = 6
Since ĉ32 is the most positive one, we would next enter x32 into the basis: Each unit of
x32 that is entered into the basis will decrease Powerco’s cost by $6. The loop
involving x32 is (3,2)-(3,3)-(2,3)-(2,2). = 10 (see table)
City 1 City 2 City 3 City 4 SUPPLY
Plant 1 8 6 10 9 35
35
9 12 13 7
Plant 2 10 20– 20+ 50
14 9 16 5
Plant 3 10– 30 40
DEMAND 45 20 30 30 125
x33 would leave the basis. New bfs is shown at the following table:
ui/vj 8 11 12 7 SUPPLY
8 6 10 9
0 35
35
9 12 13 7
1 50
10 10 30
14 9 16
-2 40
5
10 30
DEMAND 45 20 30 30 125
DEMAND 45 20 30 30 125
x22 would leave the basis. New bfs is shown at the following table:
ui/vj 8 6 12 2 SUPPLY
8 6 10 9
0 35
25 10
9 12 13
1 50
20 7
30
3 40
14 9 16
5
DEMAND 45 20 30 30 125
10 30
ĉ13 = 2, ĉ14 = -7, ĉ22 = -5, ĉ24 = -4, ĉ31 = -3, ĉ33 = -1
Since ĉ13 is the most positive one, we would next enter x13 into the basis. The
loop involving x13 is (1,3)-(2,3)-(2,1)-(1,1). = 25 (see table)
City 1 City 2 City 3 City 4 SUPPLY
8 6 10 9
Plant 1 35
25– 10 13
9 12 7
Plant 2 50
20+ 30–
14 9 16 5
Plant 3 40
10 30
DEMAND 45 20 30 30 125
x11 would leave the basis. New bfs is shown at the following table:
ui/vj 6 6 10 2 SUPPLY
8 6 10 9
0 35
10 1 25
9 2 13
3 50
7
45 5
3 40
14 9 16
5
DEMAND 45 20 30 30 125
10 30
ĉ11 = -2, ĉ14 = -7, ĉ22 = -3, ĉ24 = -2, ĉ31 = -5, ĉ33 = -3
Since all ĉij’s are negative, an optimal solution has been obtained.
Report
45 million kwh of electricity would be sent from plant 2 to city 1.
10 million kwh of electricity would be sent from plant 1 to city 2. Similarly, 10 million kwh
of electricity would be sent from plant 3 to city 2.
25 million kwh of electricity would be sent from plant 1 to city 3. 5 million kwh of
electricity would be sent from plant 2 to city 3.
30 million kwh of electricity would be sent from plant 3 to city 4 and
Total shipping cost is:
z = .9 (45) + 6 (10) + 9 (10) + 10 (25) + 13 (5) + 5 (30) = $ 1020
TRANSSHIPMENT PROBLEMS
Sometimes a point in the shipment process can both receive goods from other points and send
goods to other points. This point is called as transshipment point through which goods can
be transshipped on their journey from a supply point to demand point.
Shipping problem with this characteristic is a transshipment problem.
The optimal solution to a transshipment problem can be found by converting this
transshipment problem to a transportation problem and then solving this transportation
problem.
Remark
As stated in “Formulating Transportation Problems”, we define a supply point to be a point
that can send goods to another point but cannot receive goods from any other point.
Similarly, a demand point is a point that can receive goods from other points but cannot
send goods to any other point.
Steps
1. If the problem is unbalanced, balance it
Let s = total available supply (or demand) for balanced problem
2. Construct a transportation tableau as follows
A row in the tableau will be needed for each supply point and transshipment point A
column will be needed for each demand point and transshipment point
Each supply point will have a supply equal to its original supply Each
demand point will have a demand equal to its original demand
Each transshipment point will have a supply equal to “that point’s original supply +
s”
Each transshipment point will have a demand equal to “that point’s original demand + s”
3. Solve the transportation problem
Example 1. Bosphorus
(Based on Winston 7.6.)
Bosphorus manufactures LCD TVs at two factories, one in Istanbul and one in Bruges. The
Istanbul factory can produce up to 150 TVs per day, and the Bruges factory can produce up to
200 TVs per day. TVs are shipped by air to customers in London and Paris. The customers in
each city require 130 TVs per day. Because of the deregulation of air fares, Bosphorus
believes that it may be cheaper to first fly some TVs to Amsterdam or Munchen and then fly
them to their final destinations.
The costs of flying a TV are shown at the table below. Bosphorus wants to minimize the total
cost of shipping the required TVs to its customers.
€ To
From Istanbul Bruges Amsterdam Munchen London Paris
Istanbul 0 - 8 13 25 28
Bruges - 0 15 12 26 25
Amsterdam - - 0 6 16 17
Munchen - - 6 0 14 16
London - - - - 0 -
Paris - - - - - 0
Answer:
In this problem Amsterdam and Munchen are transshipment points.
Step 1. Balancing the problem Total
supply = 150 + 200 = 350
Total demand = 130 + 130 = 260
Dummy’s demand = 350 – 260 = 90
s = 350 (total available supply or demand for balanced problem)
Step 2. Constructing a transportation tableau
Transshipment point’s demand = Its original demand + s = 0 + 350 = 350 Transshipment
point’s supply = Its original supply + s = 0 + 350 = 350
Amsterdam Munchen London Paris Dummy Supply
8 13 25 28 0
Istanbul 150
15 12 26 25 0
Bruges 200
Amsterdam 0 6 16 17 0
350
Munchen 6 0 14 16 0
350
Demand 350 350 130 130 90
Step 3. Solving the transportation problem
Amsterdam Munchen London Paris Dummy Supply
Istanbul 8 13 25 28 0
130 20
150
15 12 26 25
Bruges
0
200
Amsterdam 130
70 350
Munchen
0 06 16 17 350
Demand 350 350 130 90 1050
220 130130
6 0 14 16
0
350
Report:
Bosphorus should produce 130 TVs at Istanbul, ship them to Amsterdam, and transship them
from Amsterdam to London.
The 130 TVs produced at Bruges should be shipped directly to Paris. The total
shipment is 6370 Euros.
ASSIGNMENT PROBLEMS
There is a special case of transportation problems where each supply point should be assigned
to a demand point and each demand should be met. This certain class of problems is called as
“assignment problems”. For example determining which employee or machine should be
assigned to which job is an assignment problem.
LP Representation
An assignment problem is characterized by knowledge of the cost of assigning each supply
point to each demand point: cij
On the other hand, a 0-1 integer variable xij is defined as follows
xij = 1 if supply point i is assigned to meet the demands of demand point j xij = 0
if supply point i is not assigned to meet the demands of point j
cij xij
xij = 0 or xij = 1
Hungarian Method
Since all the supplies and demands for any assignment problem are integers, all variables in
optimal solution of the problem must be integers. Since the RHS of each constraint is equal to
1, each xij must be a nonnegative integer that is no larger than 1, so each xij must equal 0 or 1.
Ignoring the xij = 0 or xij = 1 restrictions at the LP representation of the assignment problem,
we see that we confront with a balanced transportation problem in which each supply point
has a supply of 1 and each demand point has a demand of 1.
However, the high degree of degeneracy in an assignment problem may cause the Transportation Simplex
to be an inefficient way of solving assignment problems.
For this reason and the fact that the algorithm is even simpler than the Transportation Simplex,
the Hungarian method is usually used to solve assignment problems.
Remarks
1. To solve an assignment problem in which the goal is to maximize the objective function,
multiply the profits matrix through by –1 and solve the problem as a minimization
problem.
2. If the number of rows and columns in the cost matrix are unequal, the assignment problem
is unbalanced. Any assignment problem should be balanced by the addition of one or
more dummy points before it is solved by the Hungarian method.
Steps
1. Find the minimum cost each row of the m*m cost matrix.
2. Construct a new matrix by subtracting from each cost the minimum cost in its row
3. For this new matrix, find the minimum cost in each column
4. Construct a new matrix (reduced cost matrix) by subtracting from each cost the minimum
cost in its column
5. Draw the minimum number of lines (horizontal and/or vertical) that are needed to cover
all the zeros in the reduced cost matrix. If m lines are required, an optimal solution is
available among the covered zeros in the matrix. If fewer than m lines are needed, proceed
to next step
6. Find the smallest cost (k) in the reduced cost matrix that is uncovered by the lines drawn
in Step 5
7. Subtract k from each uncovered element of the reduced cost matrix and add k to each
element that is covered by two lines. Return to Step 5
Answer:
Step 1. For each row in the table we find the minimum cost: 2, 2, 3, and 5 respectively
Step 2 & 3. We subtract the row minimum from each cost in the row. For this new matrix,
we find the minimum cost in each column
0 2 4 8
0 10 4 3
4 5 0 6
9 0 3 2
Column minimum 0 0 0 2
Step 4. We now subtract the column minimum from each cost in the column
obtaining reduced cost matrix.
0 2 4 6
0 10 4 1
4 5 0 4
9 0 3 0
Step 5. As shown, lines through row 3, row 4, and column 1 cover all the zeros in the reduced
cost matrix. The minimum number of lines for this operation is 3. Since fewer than four lines
are required to cover all the zeros, solution is not optimal: we proceed to next step.
0 2 4 6
0 10 4 1
4 5 0 4
Step 6 & 7. The smallest uncovered
9 cost 0equals 1. We
3 now subtract
0 1 from each uncovered
cost, add 1 to each twice-covered cost, and obtain
0 1 3 5
0 9 3 0
5 5 0 4
10 0 3 0
Four lines are now required to cover all the zeros: An optimal s9olution is available. Observe
that the only covered 0 in column 3 is x33, and in column 2 is x42. As row 5 can not be used
again, for column 4 the remaining zero is x24. Finally we choose x11.
Report:
CP1 should fly with FO1; CP2 should fly with FO4; CP3 should fly with FO3; and CP4
should fly with FO4.
When formulating LP’s we often found that, strictly, certain variables should have been
regarded as taking integer values but, for the sake of convenience, we let them take fractional
values reasoning that the variables were likely to be so large that any fractional part could be
neglected.
While this is acceptable in some situations, in many cases it is not, and in such cases we must
find a numeric solution in which the variables take integer values.
Problems in which this is the case are called integer programs (IP's) and the subject of
solving such programs is called integer programming (also referred to by the initials IP).
IP's occur frequently because many decisions are essentially discrete (such as yes/no, do/do
not) in that one or more options must be chosen from a finite set of alternatives.
An IP in which all variables are required to be integers is called a pure IP problem.
If some variables are restricted to be integer and some are not then the problem is a
mixed IP problem.
The case where the integer variables are restricted to be 0 or 1 comes up surprising often.
Such problems are called pure (mixed) 0-1 programming problems or pure (mixed) binary
IP problems.
For any IP we can generate an LP by taking the same objective function and same constraints
but with the requirement that variables are integer replaced by appropriate continuous
constraints:
“xi ≥ 0 and integer” can be replaced by xi ≥ 0
“xi = 0 or 1” can be replaced by xi ≥ 0 and xi ≤ 1
The LP obtained by omitting all integer or 0-1 constraints on variables is called LP
Relaxation of the IP (LR).
FORMULATING IP
Practical problems can be formulated as IPs. For instance budgeting problems, knapsack
problems, fixed charge production and location problems, set covering problems, etc.
Capital Budgeting
(Winston 9.2, p. 478 – modified)
Stock is considering four investments
Each investment yields a determined NPV ($8,000, $11,000, $6,000, $4,000) Each
investment requires at certain cash flow at the present time ($5,000, $7,000,
$4,000, $3,000)
Currently Stock has $14,000 available for investment.
Formulate an IP whose solution will tell Stock how to maximize the NPV obtained from the
four investments.
Answer
Begin by defining a variable for each decision that Stockco must make. In this
case, we will use a 0-1 variable xj for each investment:
If xj is 1 then Stock will make investment j. If it
is 0, Stock will not make the investment. This
leads to the 0-1 programming problem:
max z = 8x1 + 11x2 + 6x3 + 4x4
s.t. 5x1 + 7x2 + 4x3 + 3x4 ≤ 14
xj = 0 or 1 (j = 1,2,3,4)
Comment
Now, a straightforward “bang for buck” (taking ratios of objective coefficient over
constraint coefficient) suggests that investment 1 is the best choice.
Ignoring integrality constraints, the optimal linear programming solution is:
x1 = x2 = 1, x3 = 0.5, and x4 = 0 for a value of $22K Unfortunately,
this solution is not integral. Rounding x3 down to 0:
x1 = x2 = 1, x3 = x4 = 0 for a value of $19K
There is a better integer solution (optimal solution):
x1 = 0, x2 = x3 = x4 = 1 for a value of $21K
This example shows that rounding does not necessarily give an optimal value.
Capital requirements
Project Return Year1 Year2 Year3
1 0.2 0.5 0.3 0.2
2 0.3 1 0.5 0.2
3 0.5 1.5 1.5 0.3
4 0.1 0.1 0.4 0.1
Available capital 3.1 2.5 0.4
Answer
We will use a 0-1 variable xj for each project:
xj is 1 if we decide to do project j;
xj is 0 otherwise (i.e. not do project j).
This leads to the 0-1 programming problem:
max 0.2 x1 + 0.3 x2 + 0.5 x3 + 0.1 x4
s.t. 0.5 x1 + 1 x2 + 1.5 x3 + 0.1 x4 ≤ 3.1
0.3 x1 + 0.5 x2 + 1.5 x3 + 0.4 x4 ≤ 2.5
0.2 x1 + 0.2 x2 + 0.3 x3 + 0.1 x4 ≤ 0.4
xj = 0 or 1 j = 1, … 4
Knapsack Problems
Any IP that has only one constraint is referred to as a knapsack problem. Furthermore, the
coefficients of this constraint and the objective are all non-negative. The traditional story is
that: There is a knapsack. There are a number of items, each with a size and a value. The
objective is to maximize the total value of the items in the knapsack.
Knapsack problems are nice because they are (usually) easy to solve.
Example 2. Knapsack
For instance, the following is a knapsack problem:
Maximize 8 x1 + 11 x2 + 6 x3 + 4 x4
Subject to 5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
xj = 0 or 1 j = 1, … 4
There is a cost associated with performing an activity at a nonzero level that does not depend
on the level of the activity.
An important trick can be used to formulate many production and location problems
involving the idea of a fixed charge as IP.
Example 3.a. Gandhi
(Winston 9.2, p. 480)
Gandhi Co makes shirts, shorts, and pants using the limited labor and cloth described below.
In addition, the machinery to make each product must be rented.
Shirts Shorts Pants Total Avail.
Labor (hrs/wk) 3 2 6 150
Cloth (m2/wk) 4 3 4 160
Rent for machine ($/wk) 200 150 100
Variable unit cost 6 4 8
Sale Price 12 8 15
Answer
Let xj be number of clothing produced.
Let yj be 1 if any clothing j is manufactured and 0 otherwise.
Profit = Sales revenue – Variable Cost – Costs of renting machinery For
example the profit from shirts is
z1 = ( 12 – 6 ) x1 – 200 y1
Since supply of labor and cloth is limited, Gandhi faces two constraints.
To ensure xj > 0 forces yj = 1, we include the additional constraints
xj ≤ Mj yj
From the cloth constraint at most 40 shirts can be produced (M1=40), so the additional
constraint for shirts is not an additional limit on x1 (If M1 were not chosen large (say M1=10),
then the additional constraint for shirts would unnecessarily restrict the value of x1).
From the cloth constraint at most 53 shorts can be produced (M2=53) From
the labor constraint at most 25 pants can be produced (M3=25) We thus get
the mixed (binary) integer problem:
max 6 x1 + 4 x2 + 7 x3 – 200 y1 – 150 y2 – 100 y3
s.t. 3 x1 + 2 x2 + 6 x3 ≤ 150 (Labor constraint)
4 x1 + 3 x2 + 4 x3 ≤ 160 (Cloth constraint)
x1 ≤ 40 y1 (Shirt production constraint)
x2 ≤ 53 y2 (Short production constraint)
x3 ≤ 25 y3 (Pant production constraint)
x1, x2, x3 ≥ 0 and integer
y1, y2, y3 = 0 or 1
Example 3.b. Lockbox
(Winston 9.2, p. 483)
Consider a national firm that receives checks from all over the United States.
There is a variable delay from when the check is postmarked (and hence the customer has met
her obligation) and when the check clears (the firm can use the money).
It is in the firm's interest to have the check clear as quickly as possible since then the firm can
use the money.
To speed up this clearing, firms open offices (lockboxes) in different cities to handle the
checks.
Suppose firm receives payments from four regions (West, Midwest, East, and South). The
average daily value from each region is as follows: $70,000 from the West,
$50,000 from the Midwest, $60,000 from the East, and $40,000 from the South. Firm is
considering opening lockboxes in L.A., Chicago, New York, and/or Atlanta. Operating a
lockbox costs $50,000 per year.
Assume that each region must send all its money to a single city. Also
assume that investment rate is 20%.
The average days from mailing to clearing is given in the table:
LA Chicago NY Atlanta
West 2 6 8 8
Midwest 6 2 5 5
East 8 5 2 5
South 8 5 5 2
Which lockboxes should firm open? (Formulate an IP that firm can use to minimize the sum
of costs due to lost interest and lockbox operations.)
Answer
First we must calculate the losses due to lost interest for each possible assignment. For
instance, if the West sends to New York, then on average there will be $560,000 (=8×$70.000)
in process on any given day. Assuming an investment rate of 20%, this corresponds to a yearly
loss of $112,000.
We can calculate the losses for the other possibilities in a similar fashion to get the
following table:
LA Chicago NY Atlanta
West 28 84 112 112
Midwest 60 20 50 50
East 96 60 24 60
South 64 40 40 16
Let yj be a 0-1 variable that is 1 if lockbox j is opened and 0 if it is not. Let xij
be 1 if region i sends to lockbox j; and 0 otherwise.
Our objective is to minimize our total yearly costs. This is: 28
x11 + 84 x12 + … + 50 y1 + 50 y2 + 50 y3 + 50 y4
One set of constraint is that each region must be assigned to one lockbox:
∑j xij = 1 for all i
(∑j should be read as "sum over all integer values of j from 1 to n inclusive")
A region can only be assigned to an open lockbox:
x1j + x2j + x3j + x4j ≤ M yj
M is any number that should be at least 4 as there are four regions.
(Suppose we do not open LA lockbox; then y1 is 0, so all of x11, x21, x31, and x41 must also be 0.
If y1 is 1, then there is no restriction on the x values.)
min 28 x11 + 84 x12 + 112 x13 + 112 x14
+ 60 x21 + 20 x22 + 50 x23 + 50 x24
+ 96 x31 + 60 x32 + 24 x33 + 60 x34
+ 64 x41 + 40 x42 + 40 x43 + 16 x44
+ 50 y1 + 50 y2 + 50 y3 + 50 y4
s.t. x11 + x12 + x13 + x14 = 1 x21 +
x22 + x23 + x24 = 1 x31 +
x32 + x33 + x34 = 1 x41 +
x42 + x43 + x44 = 1
x11 + x21 + x31 + x41 ≤ 4y1 x12
+ x22 + x32 + x42 ≤ 4y2 x13 +
x23 + x33 + x43 ≤ 4y3 x14 + x24
+ x34 + x44 ≤ 4y4
All xij and yj = 0 or 1
Membership in Specified Subsets
Using decision variables that equal 1 if an object is part of a solution and 0 otherwise, set
covering, set packing, and set partitioning models formulate problems where the core issue is
membership in specifed subsets.
Many applications in areas such as location problems (fire/police station, warehouse, facility),
scheduling (crew, airline, truck, bus), political districting
Set covering constraints
Require that at least one member of subcollection J belongs to a solution:
∑j J xj ≥ 1
Set packing constraints
Require that at most one member of subcollection J belongs to a solution:
∑j J xj ≤ 1
Set partitioning constraints
Require that exactly one member of subcollection J belongs to a solution:
∑j J xj = 1
Either-Or Constraints
If-Then Constraints
“Given a number of cities and the costs of traveling from any city to any other city, what is
the cheapest round-trip route (tour) that visits each city once and then returns to the starting
city?”
This problem is called the traveling salesperson problem (TSP), not surprisingly.
An itinerary that begins and ends at the same city and visits each city once is called a
tour.
Suppose there are N cities.
Let cij = Distance from city i to city j (for i j) and
Let cii = M (a very large number relative to actual distances) Also
define xij as a 0-1 variable as follows:
xij = 1 if s/he goes from city i to city j;
xij = 0 otherwise
The formulation of the TSP is:
min ∑İ ∑j cij xij
s.t. ∑İ xij = 1 for all j
SOLVING IP
Purpose)
General purpose methods will solve any IP but potentially computationally
ineffective (will only solve relatively small problems); or
Special purpose methods are designed for one particular type of IP problem but
potentially computationally more effective.
Why Heuristics?
Because the size of problem that we want to solve is beyond the computational limit of
known optimal algorithms within the computer time we have available.
We could solve optimally but feel that this is not worth the effort (time, money, etc) we
would expend in finding the optimal solution.
In fact it is often the case that a well-designed heuristic algorithm can give good quality
(near-optimal) results.
LP Relaxation
For any IP we can generate an LP by taking the same objective function and same constraints
but with the requirement that variables are integer replaced by appropriate continuous
constraints:
“xi = 0 or 1” xi ≥ 0 and xi ≤ 1
“xi ≥ 0 and integer” xi ≥ 0
The LP obtained by omitting all integer and 0-1 constraints on variables is called the
LP Relaxation of the IP (LR). We can then solve this LR of the original IP.
Naturally Integer LP
If LR is optimized by integer variables then that solution is feasible and optimal for IP. In
other words, if the solution is turned out to have all variables taking integer values at the
optimal solution, it is also optimal solution for IP:
LR – IP Relation
Since LR is less constrained than IP:
If IP is a maximization problem, the optimal objective value for LR is greater than or
equal to that of IP.
If IP is a minimization problem, the optimal objective value for LR is less than or
equal to that of IP.
If LR is infeasible, then so is IP.
So solving LR does give some information. It gives a bound on the optimal value, and, if we
are lucky, may give the optimal solution to IP.
Enumeration
Unlike LP (where variables took continuous values) in IP's (where all variables are integers)
each variable can only take a finite number of discrete (integer) values. Hence the obvious
solution approach is simply to enumerate all these possibilities - calculating the value of the
objective function at each one and choosing the (feasible) one with the optimal value.
Possible Solutions
There are 24=16 possible solutions:
0 0 0 0 do no projects 1 1 1 0 do three projects 1
0 0 0 1 do one project 101
0 0 1 0 1 0 1 1
0 1 0 0 0 1 1 1
1 0 0 0 1 1 1 1 do four projects
0 0 1 1 do two projects
0 1 0 1
1 0 0 1
0 1 1 0
1 0 1 0
1 1 0 0
Review
Hence for our example, we merely have to examine 16 possibilities before we know precisely
what the best possible solution is. This example illustrates a general truth about integer
programming.
What makes solving the problem easy when it is small is precisely what makes it hard very
quickly as the problem size increases.
This is simply illustrated: suppose we have 100 integer variables each with two possible
integer values then there are 2x2x2x ... x2 = 2100 (approximately 1030) possibilities which we
have to enumerate (obviously many of these possibilities will be infeasible, but until we
generate one we cannot check it against the constraints to see if it is feasible).
For 100 integer variable - conceptually there is not a problem - simply enumerate all
possibilities and choose the best one. But computationally (numerically) this is just
impossible.
The most effective general purpose optimal algorithm is an LP-based tree search approach
called as branch and bound (B&B).
The method was first put forward in the early 1960's by Land and Doig.
This is a way of systematically (implicitly) enumerating feasible solutions such that the
optimal integer solution is found.
Where this method differs from the enumeration method is that not all the feasible solutions
are enumerated but only a part (hopefully a small part) of them. However we can still
guarantee that we will find the optimal integer solution.
By solving a single sub-problem, many possible solutions may be eliminated from
consideration.
Sub-problems are generated by branching on an appropriately chosen fractional- valued
variable.
Suppose that in a given sub-problem (call it subp.1), assumes a fractional value between the
integers i and i+1. Then the two newly generated sub-problems:
Subp.2 = Subp.1 + Constraint “xi ≥ i+1” Subp.3
= Subp.1 + Constraint “xi ≤ I”
If all variables have integer values in the optimal solution to the sub-problem then the solution
is a feasible solution for the original IP.
If the current feasible solution for the IP has a better z-value than any previously obtained
feasible solution, then it becomes a candidate solution, and its z-value becomes the current
Lower Bound (LB) on the optimal z-value (for a max problem). If it is unnecessary to branch
on a sub-problem, we say that it is fathomed (inactive):
The sub-problem is infeasible
The sub-problem yields an optimal solution in which all variables have
integer values
The optimal z-value for the sub-problem does not exceed the current LB, so it cannot
yield the optimal solution of the IP
Two general approaches are used to determine which sub-problem should be solved next:
Backtracking (LIFO)
Leads us down one side of the B&B tree and finds a candidate solution. Then we backtrack
our way up to the top of the other side of the tree.
Jumptracking
Solves all the problems created by branching. Then it branches again on the node with the
best z-value. Often jumps from one side of the tree to the other.
A display of the sub-problems that have been created is called a tree. Each sub-
problem is referred to as a node of the tree.
Each additional constraint is referred to as a line (arc) connecting two nodes (old sub-problem
and one of the new sub-problems) of the tree.
Optimal Sol’n
Thus, the optimal solution to the IP
z = 40, x1 = 5, x2 = 0
Example 3. Mixed IP
(Winston 9.4., p. 523)
max z = 2 x1 + x2
s.t. 5 x1 + 2 x2 ≤ 8
x1 + x2 ≤ 3
x1, x2 ≥ 0; x1 integer
Answer
We solve the LR (subp.1) of the problem [replace
“x1≥ 0 and integer” by “x1 ≥ 0”]
Then using any LP package or utilizing simplex or graphical solution method we get
z = 11/3, x1 = 2/3, x2=7/3
Because x2 is allowed to be fractional, we do not branch on x2. We
branch on x1 and create two new sub-problems:
Subp.2: LR + x1 ≥ 1
Subp.3: LR + x1 ≤ 0
We see that the optimal solution to subp.2 is
z = 7/2, x1 = 1, x2 = 3/2
As only x1 assume integer value, this solution is feasible for the original MIP
Candidate solution; LB = 7/2 The
optimal solution to subp.3 is
z = 3, x1 = 0, x2 = 3
Subp.3 cannot yield a z-value exceeding the current LB, so it cannot yield the optimal solution
to the MIP.
Optimal Sol’n
Thus, the optimal solution to the MIP
z = 7/2, x1 = 1, x2 = 3/2
Example 5. Knapsack
max z = 8 x1 + 11 x2 + 6 x3 + 4 x4
s.t. 5 x1 + 7 x2 + 4 x3 + 3 x4 ≤ 14
xj = 0 or 1 j = 1, … 4
Answer
We compute the ratios:
r1 = 8 / 5 = 1.6
r2 = 11 / 7 = 1.57
r3 = 6 / 4 = 1.5
r4 = 4 / 3 = 1.33
Using the ratios, LR solution is
x1 = 1, x2 = 1, x3 = 0.5, x4 = 0, z = 22
We branch on x3 and get
P1 (LR + x3=0) sol’n: x3=0, x1=x2=1, x4=2/3, z=21.67 P2
(LR + x3=1) sol’n: x3=x1=1, x2=5/7, x4=0, z=21.85
Choosing sub-problem P2 (the best z–value), we branch on x2 and get P3 (P2
+ x2=0) sol’n: x3=1, x2=0, x1=1, x4=1, z=18
P4 (P2 + x2=1) sol’n: x3=x2=1, x1=3/5, x4=0, z=21.8
P3 solution is feasible for the original knapsack problem Candidate solution; LB = 18
Choosing sub-problem P4, we branch on x1 and get P5 (P4
+ x1=0) sol’n: x3=x2=1, x1=0, x4=1, z=21
P6 (P4 + x1=1) sol’n: Infeasible (x3=x2=x1=1: LHS=16)
P5 solution is feasible for the original knapsack problem New candidate solution;
updated LB = 21
The only remaining sub-problem is P1 with solution value 21.67
There is no better solution for this sub-problem than 21. But we already have a solution with
value 21.
It is not useful to search for another such solution. We can fathom P1 based on this
bounding argument and mark P1 as inactive.
Optimal sol’n and Report
Thus, the optimal solution is
z=21, x1=0, x2=1, x3=1, x4=1
Items 2, 3, and 4 should be put in the knapsack. In this
case, the total value would be 21.
B&B for Solving Combinatorial Optimization Problems
A combinatorial (discrete) optimization problem is any optimization problem that has a finite
number of feasible solutions.
A B&B approach is often an efficient way to solve them.
TSP
Please recall that
We define xij as a 0-1 variable:
xij = 1 if TS goes from city i to city j;
xij = 0 otherwise
cij = distance form city i to city j (for i j)
cii = M (a very large number relative to actual distances)
An itinerary that begins and ends at the same city and visits each city once is called a
tour.
It seems reasonable that we might be able to find the answer to TSP by solving an
assignment problem having a cost matrix whose ijth is cij.
If the optimal solution to the assignment problem yields a tour, it is the optimal solution to
the TSP.
Unfortunately, the optimal solution to the assignment problem need not be a tour (may yield
subtours).
If we could exclude all feasible solutions that contain subtours and then solve the
assignment problem, we would obtain the optimal solution to TSP Not easy to do...
Several B&B approaches have been developed for solving TSPs.
One approach start with solving the preceding assignment problem (sub-problem 1). Because
this sub-problem contains no provisions to prevent subtours, it is a relaxation of the original
TSP.
Thus, if the optimal solution to the subp.1 is feasible for the TSP (no subtours), then it is also
optimal for the TSP.
If it is infeasible (contain subtours), we branch on the subp.1 in a way that will prevent one of
subp.1’s subtours from recurring in solutions to subsequent sub- problems.
Example 7: TSP
(Winston 9.6., p. 530)
Joe State lives in Gary, Indiana and owns insurance agencies in Gary, Fort Wayne,
Evansville, Terre Haute, and South Bend.
Each December, he visits each of his insurance agencies. The
distance between each agency:
miles G FW E TH SB
G 0 132 217 164 58
FW 132 0 290 201 79
E 217 290 0 113 303
TH 164 201 113 0 196
SB 58 79 303 196 0
What order of visiting his agencies will minimize the total distance traveled?
Answer
We first solve the assignment problem (subp.1) applying the Hungarian method to the cost
matrix shown:
COSTS G FW E TH SB
G 1000 132 217 164 58
FW 132 1000 290 201 79
E 217 290 1000 113 303
TH 164 201 113 1000 196
SB 58 79 303 196 1000
The optimal solution will be:
x15=x21=x34=x43=x52=1, z=495
The optimal solution to subp.1 contains two subtours:
recommends going from Gary (1) to South Bend (5), then to Fort Wayne (2), and then
back to Gary (1–5–2–1).
also suggests that if Joe is in Evansville (3), he should go to Terre Haute (4) and then to
Evansville (3–4–3).
Thus, the optimal solution can not be the optimal solution to Joe’s problem. We
arbitrarily choose to exclude the subtour 3-4-3.
Observe that the optimal solution to Joe’s problem must have either x34=0 or x43=0. Thus,
we can branch on subp.1 by creating two new sub-problems.
Subp.2: Subp.1 + (x34=0, or c34=M)
Subp.3: Subp.1 + (x43=0, or c43=M)
Now arbitrarily choose subp.2 to solve.
COSTS G FW E TH SB
G 1000 132 217 164 58
FW 132 1000 290 201 79
E 217 290 1000 1000 303
TH 164 201 113 1000 196
SB 58 79 303 196 1000
Evaluation of Heuristics
Performance guarantees
Gives a worse-case bound on how far away from optimality a tour constructed by the
heuristic can be
Probabilistic analysis
A heuristic is evaluated by assuming that the location of cities follows some known
probability distribution
Empirical analysis
Heuristics are compared to the optimal solution for a number of problems for which the
optimal tour is known
A linear inequality is a valid inequality for a given IP problem if it holds for all integer
feasible solutions to the model. Relaxations can often be strengthened dramatically by
including valid inequalities that are not needed by a correct discrete model. To strengthen a
relaxation, a valid inequality must cut off (render infeasible) some feasible solutions to
current LR that are not feasible in the IP model.
Optimum
(integer)
solution
P Optimum
fractional
solution
x
Example:
Example: min.
min. x +s.t.
x + 10y 10y
s.t. x, yx,are
x, y are in P y in P
x, y integer
integer
Idea: add
Idea: add
constraints that
y constraints that
eliminate fractional
eliminate fractional
solutions to the LP
solutions to the LP
without eliminating
without eliminating
any integer
any integer
solutions.
solutions.
add “y 1”
add “y 1”
add “y x –1”
P add “y x –1”
These constraints
These constraints
were obtained by
x
Example: min. x + 10y were obtained
inspection. We by
will
Example: m
s.tin
. . xx,+y1a0ry inspection. We will
e in P develop techniques
s.t. x,, y ianrteeginerP develop techniques
later.
x, y integer later.
If we add exactly
the
If weright
add exactly
inequalities,
the right then
y every corner point
inequalities, then
of the corner
every LP will point
be
integer,
of the LPand
willthe
be IP
can be solved
integer, and thebyIP
solving the LP by
can be solved
solving the LP
Optimum We call this minimal
minimal
(integer) LP, the
the convex hull
hull
solution of the IP solutions.
P For large problems,
these constraints are
hard to find.
Cut Classification
General purpose
A fractional extreme point can always be separated (LP-based approach, that works for
IP)
o Disjunctive cuts
o Gomory cutting planes
Problem specific
Derived from problem structure, generally facets. (Capital Budgeting (Knapsack), Set
Packing... )
The dual simplex ratio test indicates that s1 should enter the basis instead of s3. The
optimal solution is an IP solution:
z = 40, x1 = 5, x2 = 0
Answer
Optimal tableau for LR
z x1 x2 e1 e2 RHS
1 0 0 -0.80 -3.60 17.60
0 1 0 -0.40 0.20 0.80
0 0 1 0.20 -0.60 1.60
Choose the second constraint
x2 + 0.2 e1 – 0.6 e2 = 1.6
Manipulate this:
x2 – e2 – 1 = 0.6 – 0.2 e1 – 0.4 e2
Cut:
0.6 – 0.2 e1 – 0.4 e2 ≤ 0
New LP tableau
z x1 x2 e1 e2 s3 RHS
1 0 0 -0.8 -3.6 0 17.6
0 1 0 -0.4 0.2 0 0.8
0 0 1 0.2 -0.6 0 1.6
0 0 0 -0.2 -0.4 1 -0.6
The dual simplex ratio test indicates that e1 should enter the basis instead of s3. The
optimal solution is an IP solution:
z = 20, x1 = 2, x2 = 1
Unit-V: Queuing
Outline
– For each repetition I, generate a value for each input, evaluate the function, and
calculate the value of the response YI.
• In a single-channel queue:
– Arrivals for service occur one at a time in a random fashion. Once they join the
waiting line they are eventually served.
• Arrivals and services are defined by the distribution of the time between arrivals and
service times.
• Key concepts:
– The system state is the number of units in the system and the status of the server
(busy or idle).
– Assume that the times between arrivals were generated by rolling a die 5 times
and recording the up face, then input generated is:
• Assume the only possible service times are 1, 2, 3 and 4 time units and they are equally
likely to occur, with input generated as:
– Customers arrive at random times from 1 to 8 minutes apart, with equal probability of occurrence: