Ot Lecture Notes 0 PDF
Ot Lecture Notes 0 PDF
Ot Lecture Notes 0 PDF
ON
OPTIMIZATION TECHNIQUES
V Semester
R M Noorullah
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:
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.
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.
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.
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.
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.
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.
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
In 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 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 Z 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 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.
Accordingly, on the termination of the exercise, the Superintendent of Bawdsey Research Station, A.P. Rowe,
announced that although the exercise had again demonstrated the technical feasibility of the radar system for
detecting aircraft, its operational achievements still fell far short of requirements. He therefore proposed that a
crash program of research into the operational - as opposed to the technical -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
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 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.
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."
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.
The Two Mines Company own two different mines that produce an ore which, after being crushed, is graded
into three classes: high, medium and low-grade. The company has contracted to provide a smelting plant with 12
tons of high-grade, 8 tons of medium-grade and 24 tons of low-grade ore per week. The two mines have
different operating characteristics as detailed below.
X 180 6 3 4
Y 160 1 1 6
Consider that mines cannot be operated in the weekend. How many days per week should each mine be
operated to fulfill the smelting plant contract?
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.
This does not seem like a good guess as it results in only 7 tons 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.
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).
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
x = number of days per week mine X is operated y = number of days per week mine Y is operated
Constraints
It is best to first put each constraint into words and then express it in 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
Note we have an inequality here rather than 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
Minimize
180x + 160y
Subject to
6x + y ≥ 12
3x + y ≥ 8
4x + 6y ≥ 24
x≤5
y≤5
x, y ≥ 0
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
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.
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."
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) 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.
We will return later to the simplex algorithm for solving LP's but for the moment we will concentrate upon
formulating LP's.
Work scheduling
Financial planning
o Distribution
Inventory model
Financial models
Work scheduling
Note that the key to formulating LP's is practice. However a useful hint is that common objectives for LP's are
maximized profit/minimize cost.
Proportionality
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)
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
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
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
FORMULATING LP
Giapetto Example
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?
Solution:
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:
Here profit equals to (weekly revenues) – (raw material purchase cost) – (other variable costs). Hence Giapetto’s
objective function is:
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:
Sign restrictions are added if the decision variables can only assume nonnegative values (Giapetto can not
manufacture negative number of soldiers or trains!)
All these characteristics explored above give the following Linear Programming (LP) model
x1 + x2 80 (Carpentry constraint)
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
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
Solution:
x1, x2 >= 0
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
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 invest 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.
Brownie 400 3 2 2
Solution:
Constraints:
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
A PO requires different numbers of employees on different days of the week. Union rules state each employee
must work 5 consecutive days and then receive two days off. Find the minimum number of employees needed.
Staff Needed 17 13 15 19 14 16 11
Solution:
We could round this up to (xi) = (2, 4, 2, 8, 0, 4, 5) giving z = 25 (may be wrong!). However restricting the
decision ver. to be integers and using Linda again gives (xi) = (4, 4, 2, 6, 0, 4, 3) giving z = 23.
Sailco Example
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 $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.
Solution:
xt ≤ 40, t
Demand is met if it ≥ 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:
Linda 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
Overtime (yt) 0 10 35 0
Inventory (it) 10 10 0 0 0
Demand (dt) 40 60 75 25
CSL services computers. Its demand (hours) for the time of skilled technicians in the next 5 months is
It starts with 50 skilled technicians at the beginning of January. Each technician can work 160 hrs/month. To
train a new technician they must be supervised for 50 hrs by an experienced technician for a period of one
month time. Each experienced
technician is paid $2K/mth and a trainee is paid $1K/mth. Each month 5% of the skilled technicians leave. CSL
needs to meet demand and minimize costs.
xt = # to be trained in month t
Then we must
Subject to
xt, yt ≥0
SOLVING LP
LP Solutions: Four Cases
2. The LP has alternative (multiple) optimal solutions. It has more than one (actually an infinite number
of) optimal solutions
3. The LP is infeasible. It has no feasible solutions (The feasible region contains no points).
4. The LP is unbounded. In the feasible region there are points with arbitrarily large (in a max problem)
objective function values.
The Graphical Solution
Example 1. Giapetto
Solution:
The feasible region is the set of all points satisfying the constraints.
x1 + x2 ≤ 80 (Carpentry constraint)
x1 ≤ 40 (Demand constraint)
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).
z = 180
z = 60
E A C
X
10 20 40 50 60 80 1
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 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
Solution:
The feasible region is the set of all points satisfying the constraints.
x1, x2 ≥ 0
z=
600
4 z = 320
A C
2 4 6 8 10 12 14 X1
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
st 6x + y ≥ 12
3x + y ≥ 8
4x + 6y ≥ 24
x≤5
y≤5
x, y ≥ 0
Solution:
x1 + x2 ≤ 80 (Carpentry constraint)
x1 ≤ 40 (Demand constraint)
Solution:
Points on the line between points G (20, 60) and F (40, 20) are the alternative
Thus, for 0 ≤ c ≤ 1,
100 B
80 D
E A C
x1
H 40 50 80
Solution:
Solution:
Isoprofit line never lose contact with the feasible region: Unbounded LP
Note that in the examples considered at the graphical solution, the unique optimal solution to the LP occurred at
a vertex (corner) of the feasible region. In fact it is true that for any LP the optimal solution occurs at a vertex of
the feasible region. This fact is the key to the simplex algorithm for solving LP's.
Essentially the simplex algorithm starts at one vertex of the feasible region and moves (at each iteration) to
another (adjacent) vertex, improving (or leaving unchanged) the objective function as it does so, until it reaches
the vertex corresponding to the optimal LP solution.
The simplex algorithm for solving linear programs (LP's) was developed by Dantzig in the late 1940's and since
then a number of different versions of the algorithm have been developed. One of these later versions, called the
revised simplex algorithm (sometimes known as the "product form of the inverse" simplex algorithm) forms the
basis of most modern computer packages for solving LP's.
Steps
3. 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
4. Go back to Step 3.
Related concepts:
Standard form: all constraints are equations and all variables are nonnegative
Basic variable: the remaining variables that satisfy the system of equations at the standard form
Example 1. Dakota Furniture
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.
Price ($) 60 30 20
LP Model:
Let x1, x2, x3 be the number of desks, tables and chairs produced.
2x1 + 1.5x2 + .5 x3 ≤ 8
x2 ≤5
x1, x2, x3 ≥ 0
First introduce slack variables and convert the LP to the standard form and write a canonical for
R1 8x1 + 6x2 + x3 + s1 = 48
R4 x2 + s4 =5
As (x1, x2, x3) = 0 is feasible for the original problem, the below given point where three of the variables equal
0 (the non-basic variables) and the four other variables (the basic variables) are determined by the four
equalities is an obvious bfs:
x1 = x2 = x3 = 0, s1 = 48, s2 = 20, s3 = 8, s4 = 5.
Determine whether there is any way that z can be increased by increasing some nonbasic variable.
If each nonbasic variable has a nonnegative coefficient in the objective function row (row 0), current bfs is
optimal.
However, here all nonbasic variables have negative coefficients: It is not optimal.
Increases most rapidly when x1 is made non-zero; i.e. x1 is the entering variable.
Now we must rewrite the system so the values of the basic variables can be
read off.
R1’ - x3 + s1 - 4s3 = 16 s1 = 16
R4’ x2 + s4 = 5 s4 = 5
Check optimality of current bfs. Repeat steps until an optimal solution is reached
Each non basic variable has a nonnegative coefficient in row 0 (5x2, 10s2, 10s3).
Report: Dakota furniture’s optimum weekly profit would be 280$ if they produce 2 desks and 8 chairs.
x2 ≤5
Initial tableau:
x x x s s s s
z 1 2 3 1 2 3 4 RHS BV Ratio
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 x x x s s s s RHS BV Ratio
1 2 3 1 2 3 4
1 0 15 -5 0 0 30 0 240 z = 240
0 0 0 -1 1 0 -4 0 16 s = 16 -
0 0 -1 0.5 0 1 -2 0 4 s =4 8
0 0 1 0 0 0 0 1 5 s =5 -
4
Second and optimal tableau:
1 2 3 1 2 3 4
1 0 5 0 0 10 10 0 280 z = 280
0 0 -2 0 1 2 -8 0 24 s = 24
0 0 -2 1 0 2 -4 0 8 x =8
1
0 0 1 0 0 0 0 1 5 s =5
new z = 60 x1 + 35 x2 + 20 x3
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 0 1 0 0 0 0 1 5 s4=5 5/1
z x1 x2 x3 s1 s2 s3 s4 RHS BV
x1 2 0 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
The Big M method is a version of the Simplex Algorithm that first finds a bfs by adding "artificial" variables to
the problem. The objective function of the original LP must, of course, be modified to ensure that the artificial
variables are all equal to 0 at the conclusion of the simplex algorithm.
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!!!
Bevco manufactures an orange flavored soft drink called Orange 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 Orange 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.
Let x1 and x2 be the quantity of ounces of orange soda and orange juice (respectively) in a bottle of Oranj.
x1, x2 ≥ 0
z – 2x1 – 3x2 = 0
0.5x1 + 0.25x2 + s1 = 4
x1 + 3x2 - e2 = 20
x1 + x2 = 10
x1 + 3x2 - e2 + a2 = 20 Row 2
x1 + x2 + a3 = 10 Row 3
5. Since each artificial variable are in our starting bfs, they must be eliminated from row 0
Initial tableau:
z x1 x2 s1 e2 a2 a3 RHS BV Ratio
0 1 3 0 -1 1 0 20 a2=20 20/3*
0 1 1 0 0 0 1 10 a3=10 10
In main 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
Optimal table:
z x1 x2 s1 e2 a2 a3 RHS BV
Report:
Let x1 and x2 be the quantity of ounces of orange soda and orange juice (respectively) in a bottle of Oranj.
x1, x2 ≥ 0
Initial tableau:
z x1 x2 s1 e2 a2 a3 RHS BV Ratio
0 1 3 0 -1 1 0 36 a2=36 36/3
0 1 1 0 0 0 1 10 a3=10 10
z x1 x2 s1 e2 a2 a3 RHS BV
0 -2 0 0 -1 1 -3 6 a2=6
0 1 1 0 0 0 1 10 x2=10
Report:
INTRODUCTION:
(a) Certainty
The resources available and the requirement of resources by competing candidates, the profit
Coefficients of each variable are assumed to remain unchanged and they are certain in nature.
(b) Linearity
The objective function and structural constraints are assumed to be linear.
(c) Divisibility
All variables are assumed to be continuous; hence they can assume integer or fractional values.
(d) Single stage
The model is static and constrained to one decision only. And planning period is assumed to be
fixed.
(e) Non-negativity
A non-negativity constraint exists in the problem, so that the values of all variables are to be 0,
i.e. the lower limit is zero and the upper limit may be any positive number.
(f) Fixed technology
Production requirements are assumed to be fixed during the planning period.
The transportation model deals with a special class of linear programming problem in which the objective is to
transport a homogeneous commodity from various origins or factories to different destinations or markets at
a total minimum cost.
Similarities
The steps used in getting a solution to a transportation problem are given below:
The allocation made must satisfy the rim requirements, i.e., it must satisfy availability constraints and
requirement constraints.
A 4 3 2 10
B 5 6 1 8
C 6 4 3 5
D 3 5 4 6
Requirement in 7 12 4
tons. 23
Here ab is greater than ad hence we have to open a dummy column whose requirement constraint is 6, so that total
of availability will be equal to the total demand. Now let get the basic feasible solution by three different methods
and see the advantages and disadvantages of these methods. After this let us give optimality test for the obtained
basic feasible solutions.
North- west corner method:
Balance the problem. That is see whether abi = ad j . If not open a dummy column or dummy row as the
case may be and balance the problem.
Start from the left hand side top corner or cell and make allocations depending on the availability and
requirement constraint. If the availability constraint is less than the requirement constraint, then for that cell
make allocation in units which is equal to the availability constraint. In general, verify which is the smallest
among the availability and requirement and allocate the smallest one to the cell under question. Then proceed
allocating either sidewise or down- ward to satisfy the rim requirement. Continue this until all the allocations
are over.
Once all the allocations are over, i.e., both rim requirement (column and row i.e., availability and requirement
constraints) are satisfied, write allocations and calculate the cost of transportation
For cell AX the availability constraint is 10 and the requirement constraint is 7. Hence 7 is smaller than 10,
allocate 7 to cell AX. Next 10 – 7 = 3, this is allocated to cell AY to satisfy availability requirement. Proceed in
the same way to complete the allocations. Then count the allocations, if it is equals to m + n – 1, then the
solution is basic feasible solution. The solution, we got have 7 allocations which is = 4 + 4 – 1 = 7. Hence the
solution is basic feasible solution.
Solution by Least cost cell (or inspection) Method: (Matrix Minimum method):
Allocations are:
Write row opportunity costs and column opportunity costs as described above.
Identify the highest opportunity cost among all the opportunity costs and write a tick mark at that element.
If there are two or more of the opportunity costs which of same magnitude, then select any one of them, to
break the tie. While doing so, see that both availability constraint and requirement constraint are
simultaneously satisfied. If this happens, we may not get basic feasible solution i.e solution with m + n – 1
allocations. As far as possible see that both are not satisfied simultaneously. In case if inevitable, proceed
with allocations. We may not get a solution with, m + n – 1 allocations. For this we can allocate a small
element epsilon to any one of the empty cells. This situation in transportation problem is known as
degeneracy. (This will be discussed once again when we discuss about optimal solution).
In transportation matrix, all the cells, which have allocation, are known as loaded cells and those, which have
no allocation, are known as empty cells.
(Note: All the allocations shown in matrix 1 to 6 are tabulated in the matrix given below:)
A Y 7 7 × 3 = 21
B X 3 3 × 5 = 15
B Z 5 5 × 1 = 05
C Y 5 5 × 4 = 20
D X 1 1 × 3 = 03
D DUMM 5 5 × 0 = 00
Y
Total 76
Rs.
Now let us compare the three methods of getting basic feasible solution:
In the problem given, the total cost of transportation for Northwest corner method is Rs. 101/-. The total cost of
transportation for Inspection method is Rs. 71/- and that of VAM is Rs. 76/-. The total cost got by inspection
method appears to be less. That of Northwest coroner method is highest. The cost got by VAM is in between
Let us take the basic feasible solution we got by Vogel's Approximation method and give optimality test to it
by stepping stone method.
Basic Feasible Solution obtained by VAM:
Table showing the cost change and opportunity costs of empty cells:
Table I.
In the table 1 cells A DUMMY, B DUMMY, C DUMMY are the cells which are having positive opportunity
cost. Between these two cells B DUMMY and C DUMMY are the cells, which are having higher opportunity
cost i.e Rs. 2/ - each. Let us select any one of them to include in the improvement of the present programme. Let
us select C DUMMY.
Table II.
Cells A DUMMY and B DUMMY are having positive opportunity costs. The cell B DUMMY is having higher
opportunity cost. Hence let us include this cell in the next programme to improve the solution.
Table III.
All the empty cells have negative opportunity cost hence the solution is optimal. The allocations are:
Basically, the transportation problem is a minimization problem, as the objective function is to minimize the
total cost of transportation. Hence, when we would like to maximize the objective function. There are two
methods.
The given matrix is to be multiplied by –1, so that the problem becomes maximization problem.
Subtract all the elements in the matrix from the highest element in the matrix. Then the problem becomes
maximization problem. Then onwards follow all the steps of maximization problem to get the solution. Let
us consider the same problem solved above.
Problem 2.
Four factories, A, B, C and D produce sugar and the capacity of each factory is given below: Factory A produces
10 tons of sugar and B produces 8 tons of sugar, C produces 5 tons of sugar and that of D is 6 tons of sugar. The
sugar has demand in three markets X, Y and Z. The demand of market X is 7 tons, that of market Y is 12 tons and
the demand of market Z is 4 tons. The following matrix gives the returns the factory can get, by selling the sugar in
each market. Formulate a transportation problem and solve for maximizing the returns.
In the given problem as the opportunity costs of all empty cells are positive, the solution is optimal. And the
optimal return to the company is Rs. 125/-.
Allocations:
Degeneracy in transportation problem can develop in two ways. First, the problem becomes degenerate when the
initial programme is designed by northwest corner or inspection or VAM, i.e. at the stage of initial allocation
only.
To solve degeneracy at this stage, we can allocate extremely small amount of goods (very close to zero) to one
or more of the empty cells depending on the shortage, so that the total occupied cells becomes m + n – 1. The
cell to which small element (load) is allocated is considered to be an occupied cell. In transportation problems,
epsilon is added to such an empty cell, which will enable us to write row number ‘ui’ and column number ‘vj’
without any difficulty while giving optimality test to the basic feasible solution by MODI method. That is care
must be taken to see that the epsilon is added to such a cell, which will not make a closed loop, when we move
horizontally and vertically from loaded cell to loaded cell.
(Note: Epsilon is so small so that if it is added or subtracted from any number, it does not change the numerical
value of the number for which it added or from which it is subtracted.).
Secondly, the transportation problem may become degenerate during the solution stages. This happens when the
inclusion of a most favorable empty cell i.e. cell having highest opportunity cost results in simultaneous
vacating of two or more of the currently occupied cells. Here also, to solve degeneracy, add epsilon to one or
more of the empty cells to make the number of occupied cells equals to (m + n – 1
Initial allocation show that the solution is not having (m+n–1) allocations. Hence degeneracy occurs.
Row numbers ui s and column numbers vj s are written in the matrix and opportunity cost of empty cells are
evaluated. As the opportunity cost of all empty cells is negative, the solution is optimal. The allocations and the
total cost of transportation is:
It is well known fact that the transportation problem is cost minimization model, i.e we have to find the least cost
transportation schedule for the given problem. Some times the cost will become secondary factor when the time
required for transportation is considered. This type of situation we see in military operation. When the army
want to send weapons or food packets or medicine to the war front, then the time is important than the money.
They have to think of what is the least time required to transport the goods than the least cost of transportation.
Here the given matrix gives the time elements, i.e. time required to reach from one origin to a destination than
the cost of transportation of one unit from one origin to a destination. A usual, we can get the basic feasible
solution by Northwest corner method or by least time method or by VAM. To optimize the basic feasible solution,
we have to identify the highest time element in the allocated cells, and try to eliminate it from the schedule by
drawing loops and encouraging to take the cell, which is having the time element less than the highest one. Let
us take a problem and work out the solution. Many a time, when we use VAM for basic feasible solution, the
chance of getting an optimal solution is more. Hence, the basic feasible solution is obtained by Northwest corner
method.
Problem 4: The matrix given below shows the time required to shift a load from origins to destinations. Formulate a
least time schedule. Time given in hours.
Roc: Row opportunity cost, Coc: Column opportunity cost, Avail: Availability, Req: Requirement.
Initial assignment by Northwest corner method: The Maximum time of allocated cell is 17 hours. Any cell
having time element greater than 17 hours is cancelled, so that it will not in the programme.
In this allocation highest time element is 11 hours. Let us try to reduce the same.
No more reduction of time is possible. Hence the solution is optimal and the time required for completing the
transportation is 10 Hours. Tmax = 10 hours.
PURCHASE AND SELL PROBLEM: (TRADER PROBLEM):
Problem. 5:
M/S Epsilon traders purchase a certain type of product from three manufacturing units in different places and
sell the same to five market segments. The cost of purchasing and the cost of transport from the traders place to
market centers in Rs. per 100 units is given below:
Market Segments.
(Transportation cost in Rs.per 100
Place of Availability Manufacturing units).
Manufacture In units x cost in Rs. per
. 10000. unit 1 2 3 4 5
Bangalore 10 40 40 30 20 25 35
(B)
Chennai (C) 15 50 30 50 70 25 40
Hyderabad 5 30 50 30 60 55 40
(H)
Requirement in units × 6 6 8 8 4
10000
The trader wants to decide which manufacturer should be asked to supply how many to which market segment
so that the total cost of transportation and purchase is minimized.
Solution:
Here availability is 300000 units and the total requirement is 320000 units. Hence a dummy row (D) is to be
opened. The following matrix shows the cost of transportation and purchase per unit in Rs. from manufacturer to
the market centers directly.
1 2 3 4 5 Availability
Let us multiply the matrix by 100 to avoid decimal numbers and get the basic feasible solution by VAM. Table. Avail:
Availability. Req: Requirement, Roc: Row opportunity cost, Coc: Column opportunity cost.
Allocation:
From To Load Cost in Rs.
Bangalore 2 10,000 4,03,000
Bangalore 3 80,000 32, 16,000
Bangalore 5 10,000 4, 03,000
This type of problems will arise when a company having many units manufacturing the same product and wants
to satisfy the needs of various market centers. The production manager has to work out for transport of goods
to various market centers to cater the needs. Depending on the production schedules and transportation costs, he
can arrange for transport of goods from manufacturing units to the market centers, so that his costs will be kept at
minimum. At the same time, this problem also helps him to prepare schedules to aim at maximizing his returns.
Problem 6:
A company has three manufacturing units at X, Y and Z which are manufacturing certain product and the
company supplies warehouses at A, B, C, D, and E. Monthly regular capacities for regular production are 300,
400 and 600 units respectively for X, Y and Z units. The cost of production per unit being Rs.40, Rs.30 and Rs.
40 respectively at units X, Y and Z. By working overtime it is possible to have additional production of 100, 150
and 200 units, with incremental cost of Rs.5, Rs.9 and Rs.8 respectively. If the cost of transportation per unit in
rupees as given in table below, find the allocation for the total minimum production cum transportation cost.
Under what circumstances one factory may have to work overtime while another may work at under capacity?
To
If the sales price per unit at all warehouses is Rs. 70/- what would be the allocation for maximum profit?
Is it necessary to obtain a new solution or the solution obtained above holds valid?
If the sales prices are Rs.70/-, Rs. 80/-, Rs. 72/-, Rs. 68/- and Rs. 65/- at A, B, C, D and E respectively
what should be the allocation for maximum profit?
Solution: Total production including the overtime production is 1750 units and the total requirement by
warehouses is 1500 units. Hence the problem is unbalanced. This can be balance by opening a Dummy Row
(DR), with cost coefficients equal to zero and the requirement of units is 250. The cost coefficients of all other
cells are got by adding production and transportation costs. The production cum transportation matrix is given
below:
As we have m +n – 1 (= 11) allocations, the solution is feasible and all the opportunity costs of empty cells are
negative, the solution is optimal.
Allocations:
Cell Load Cost in Rs.
XA 300 300 × 52 = 15,600
YD 100 100 × 41 = 4,100
YE 300 300 × 40 = 12,000
ZB 400 400 × 54 = 21,000
ZC 100 100 × 59 = 5,900
ZD 100 100 × 56 = 5,600
XOT A 50 50 × 57 = 2,850
XOT DR 50 50 × 0 = 0
YOT A 50 50 × 50 = 5,500
YOT C 100 100 × 54 = 5,400
Allocation by VAM:
1.
A B C D E DC AVAIL ROC
X 52 54 58 53 56 0 300 52
Y 41 46 45 41 42 0 400 41
Z 56 57 59 56 54 0 600 54
XOT 57 59 63 58 61 0 100 50
YOT 50 55 54 50 51 0 150 50
ZOT 64 65 67 64 62 0 (200) 2 00 62
REQ 400 400 2 00 2 00 300 2 50 1750
COC 9 8 9 9 9 0
As for one allocation a row and column are getting eliminated. Hence, the degeneracy occurs
2.
A B C D E DC AVAIL ROC
X 52 54 58 53 56 0 300 52
Y 41 46 45 41 42 0 400 41
Z 56 57 59 56 54 0 600 54
XOT 57 59 63 58 61 0 (50) 100 57
YOT 50 55 54 50 51 0 150 50
REQ 400 400 2 00 2 00 300 2 50 15 50
COC 9 8 9 9 9 0
3.
A B C D E AVAIL RO
C
X 52 54 58 53 56 300 1
Y 41 46 45 41 42 (300) 400 0
Z 56 57 59 56 54 600 2
XOT 57 59 63 58 61 50 2
YOT 50 55 54 50 51 150 0
REQ 400 400 2 00 2 00 300 1500
COC 9 8 9 9 9
4.
A B C D AVAIL ROC
X 52 54 58 53 300 1
Y 41 46 45 41 (100) 100 0
Z 56 57 59 56 600 0
XOT 57 59 63 58 50 1
YOT 50 55 54 50 150 0
REQ 40 400 2 00 2 00 1200
0
COC 9 8 9 9
5.
A B C D Avail Ro
c
X 52 54 58 53 300 1
Z 56 57 59 56 600 0
XOT 57 59 63 58 50 1
YOT 50 55 54 (150) 50 150 0
Req 400 400 200 100 110
0
Coc 2 1 4 3
6.
A B C D Avail Roc
X 52 (30 54 58 53 300 1
0)
Z 56 57 59 56 600 0
XOT 57 59 63 58 50 1
Req 400 400 50 100 950
Coc 4 3 1 3
7.
A B C D Avail Roc
Z 56 57 59 (5) 56 550 0
XOT 57 59 63 58 50 1
Req 100 400 50 100 600
Coc 1 2 4 2
A B D Avail Roc
9.
A Avai
l
Z 56 (50) 50
XO 57 (50) 50
T
100
In the table showing optimal solution, we can understand that the company X has to work 50% of its over time
capacity, and company Y has to work 100% of its overtime capacity and company Z will not utilize its overtime
capacity.
Here the total profit or return that the trading company gets is equals to Sales revenue – total expenses, which
include manufacturing cost and transportation cost. Hence,
Profit = (Total Sales Revenue) – (Manufacturing cost + transportation cost).
In the question given the sales price is same in all market segments, hence, the profit calculated is independent of
sales price. Hence the programme, which minimizes the total cost will, maximizes the total profit. Hence the
same solution will hold good. We need not work a separate schedule for maximization of profit.
Here sales price in market segments will differ. Hence we have to calculate the total profit by the formula given
above for all the markets and work for solution to maximize the profit.
The matrix showing the total profit earned by the company:
A B C D E DC Avail Coc
X 18 26 14 15 9 0 300 8
Y 29 34 27 27 25 0 400 5
400
Z 14 23 13 12 11 0 600 9
XOT 13 21 9 10 4 0 100 8
YOT 20 25 18 18 14 0 150 5
ZOT 6 15 5 4 3 0 200 9
Req 400 400 200 200 300 250 1750
Coc 11 8 9 9 9 0
B C D E DC Avail Coc
X 26 14 15 9 0 300 11
300
Z 23 13 12 11 0 600 10
XOT 21 9 10 4 0 100 11
YOT 25 18 18 14 0 150 7
ZOT 15 5 4 3 0 200 10
Req 400 200 200 300 250 1350
Coc 1 4 3 5 0
B C D E DC Avail Coc
Z 23 13 12 11 0 600 10
XOT 21 9 10 4 0 100 11
100
YOT 25 18 18 14 0 150 7
ZOT 15 5 4 3 0 200 10
Req 100 200 200 300 250 1050
Coc 2 5 6 3 0
Here also for one allocation, a row and a column are getting eliminated. Degeneracy will occur. In all we may
have to allocate two s to two empty cells.
C D E DC Avail Coc
Z 13 12 11 0 600 1
YOT 18 18 14 0 150 0
150
ZOT C5 D 4 E
3 DC0 Avail
200 Coc
1
Z
Req 13
200 12200 11
300 0 250 600
950 1
Coc 200
5 6 3 0
ZOT 5 4 3 0 200 1
Req 200 50 300 250 800
Coc 8 8 8 0
D E DC Avai Coc
Problem:
A company has booked the orders for its consignment for the months of April, May, June and July as given
below:
April: 900 units, May: 800 units, June: 900 units and July: 600 units. The company can produce 750 units per
month in regular shift, at a cost of Rs. 80/- per unit and can produce 300 units per month by overtime production
at a cost of Rs. 100/- per unit. Decide how much the company has to produce in which shift for minimizing the
cost of production. It is given that there is no holding cost of inventory.
Solution: Remember here the production of April is available to meet the orders of April and subsequent months.
But the production of May cannot be available to meet the demand of April. Similarly, the production of June is
not available to meet the demand of April, May, but it can meet the demand of June and subsequent months and
so on. Hence very high cost of production is allocated to the cells (Infinity or any highest number greater than
the costs given in the problem), which cannot meet the demands of previous months (i.e. back ordering is not
allowed). Here total availability is 4200 units and the total demand is for 3200 units. Hence we have to open a
dummy column (DC), with cost coefficients equal to zero. The balanced matrix is shown below. Let us find the
initial basic feasible solution by Northwest corner method and apply optimality test by MODI method.
A: April, M: May, J: June, Jl: July, AT: April Over time, MT: May overtime, JT: June overtime, JLT: July over time.
DC : Dummy column.
Here the cell JT DC is having highest opportunity cost. Hence let us include the cell in the revised programme.
To find the opportunity costs of empty cells, the row number ui and column number vj are shown. The cells
marked with (X) are avoided from the programme. We can also allocate very high cost for these cells, so that
they will not enter into the programme.
As the opportunity costs of all empty cells are either zeros or negative elements, the solution is optimal. As
many empty cells are having zero as the opportunity cost, they can be included in the solution and get alternate
solution.
Allocations:
When a company stocks its goods in warehouse and then sends the goods from warehouse to the market, the
problem is known as Transshipment problem.
SENSITIVITY ANALYSIS:
While discussing MODI method for getting optimal solution, we have discussed significance of implied cost,
which fixes the upper limit of cost of the empty cell to entertain the cell in the next programme. Now let us
discuss the influence of variations in present parameters on the optimum solution i.e sensitivity of optimal
solution for the variations in the costs of empty cells and loaded cells. If unit cost of transportation of a
particular non-basic variable changes, at what value of the cost of present optimum will no longer remain
optimum? To answer this question, in the first instance, it is obvious that as the empty cell is not in the solution,
any increase in its unit transportation cost will to qualify it for entering variable. But if the unit cost of empty
cells is reduced the chances of changing the optimum value may be examined. Let us take an optimum solution
and examine the above statement.
In the solution shown above as all the opportunity costs of empty cells are negative. Consider empty cell XA. Its
opportunity cost is Rs. -3/- This means to say that the units cost of transportation of cell XA decreases by Rs.3/-
or more i.e Rs.10/- the unit cost of transportation of the empty cell XA minus 3 = 7, or less than 7 the optimal
Cells XA and XB is positive when XA is > than 19. Cell XC is positive when XA is > 17 and cell XD is positive
when XA is
If unit cost of transportation increase and becomes 17, the present optimum may change. In case the unit cost of
transportation of the cell XA is reduced, the solution will still remain optimum, as our objective is to minimize
the total transportation cost.
A point to note here is we have used Northwest corner method and Vogel’s approximation method to get basic
feasible solution. Also we have discussed the least cost method and there are some methods such as row
minimum and column minimum methods. These methods attempt to optimize the sub- system and do not
consider marginal trade-offs. Therefore, such methods have no merit to serve useful purpose.
INTRODUCTION:
A sequence is the order in which the jobs are processed. Sequence problems arise when we are concerned with
situations where there is a choice in which a number of tasks can be performed. A sequencing problem could
involve:
Terms used:
Job : The jobs or items or customers or orders are the primary stimulus for sequencing. There should be a
certain number of jobs say ‘n’ to be processed or sequenced.
Number of Machines : A machine is characterized by a certain processing capability or facilities through which
a job must pass before it is completed in the shop. It may not be necessarily a mechanical device. Even human
being assigned jobs may be taken as machines. There must be certain number of machines say ‘k’ to be used for
processing the jobs.
Processing Time : Every operation requires certain time at each of machine. If the time is certain then the
determination of schedule is easy. When the processing times are uncertain then the schedule is complex.
Total Elapsed Time : It is the time between starting the first job and completing the last one.
Idle time : It is the time the machine remains idle during the total elapsed time.
Technological order : Different jobs may have different technological order. It refers to the order in which
various machines are required for completing the jobs.
Basic assumptions:
Flow-Shop Sequencing:
Job shop scheduling is basically an optimization process in which ideal jobs are assigned to resource at
particular times.
Let there be ‘n’ jobs J1, J2, J3…..Jn. Let there be ‘m’ machines M1, M2, M3…..Mn. .. If below conditions are
met, then it is said to be a flow shop sequencing problem.
The very purpose of flow shop sequencing is to assign jobs to each assigned machines in a manner that the every
machines are engaged all the time without being left ideal.
Let there be ‘n’ jobs each of which is to be processed through two machines say A & B, in the order
AB. That is each job will go to machine A first and then to B in other words passing off is not allowed.
All ‘n’ jobs are to be processed on A without any idle time. On the other hand the machine B is subject
to its remaining idle at various stages.
Let A1 A2………….An & B1 B2……..Bn be the expected processing time of n jobs on these two
machines.
Step 1: Select the smallest processing time occurring in list Ai or Bi, if there is a tie select either of the smallest
processing time.
Step 2: If the smallest time is on machine A, then place it at first place if it is for the B machine place the
corresponding job at last. Cross off that job.
Step 3: If there is a tie for minimum time on both the machines then select machine A first & machine B last
and if there is tie for minimum on machine A (same machine) then select any one of these jobs first and if there
is tie for minimum on machine B among and select any of these job in the last.
Step 4: Repeat step 2 & 3 to the reduced set of processing times obtained by deleting the processing time for
both the machines corresponding to the jobs already assigned
Step 5: Continue the process placing the job next to the last and so on till all jobs have been placed and it is
called optimum sequence.
Step 6: after finding the optimum sequence we can find the followings
Total elapsed time = Total time between starting the first job of the optimum sequence on machine A
and completing the last job on machine B.
Idle time in machine A = Time when the last job in the optimum sequence is completed on Machine B –
Time when the last job in the optimum sequence is completed on Machine A.
Problem:
In a factory, there are six jobs to process, each of which should go to machines A & B in the order AB. The
processing timings in minutes are given, determine the optimal sequencing & total elapsed time.
Jobs 1 2 3 4 5 6
Machine A 7 4 2 5 9 8
Machine B 3 8 6 6 4 1
Solution:
Step 1: the least of all the times given in for job 6 in machine B. so perform job 6 in the end. It is last in the
sequences. Now delete this job from the given data.
Example 2:
Suppose we have five jobs, each of which has to be processed on two machines A & B in the order AB.
Processing times are given in the following table:
1 6 3
2 2 7
3 10 8
4 4 9
5 11 5
Determine an order in which these jobs should be processed so as to minimize the total processing time.
Solution:
The minimum time in the above table is 2, which corresponds to job 2 on machine A.
2
Now we eliminate job 2 from further consideration. The reduced set of processing times are as follows:
1 6 3
3 10 8
4 4 9
5 11 5
The minimum time is 3 for job 1 on machine B. Therefore, this job would be done in last. The allocation of jobs
till this stage would be
2 1
After deletion of job 1, the reduced set of processing times are as follows:
3 10 8
4 4 9
5 11 5
2 4 3 5 1
Once the optimal sequence is obtained, the minimum elapsed time may be calculated as follows:
2 0 2 2 9
4 2 6 9 18
3 6 16 18 26
5 16 27 27 32
1 27 33 33 36
Idle time for machine A = total elapsed time - time when the last job is out of machine A
36-33=3hours.
Idle time for machine B = 2 + (9 - 9) + (18 - 18) + (27 - 26) + (33 - 32) = 4 hours.
Example3
:Strong Book Binder has one printing machine, one binding machine, and the manuscripts of a number of
different books. Processing times are given in the following table:
Book Time In Hours
Printing Binding
A 5 2
B 1 6
C 9 7
D 3 8
E 10 4
Solution:
The minimum time in the above table is 1, which corresponds to the book B on printing machine.
Printing Binding
A 5 2
C 9 7
D 3 8
E 10 4
The minimum time is 2 for book A on binding machine. Therefore, this job should be done in last. The
allocation of jobs till this stage is:
B A
Printing Binding
C 9 7
D 3 8
E 10 4
B D C E A
Once the optimal sequence is obtained, the minimum elapsed time may be calculated as follows:
B 0 1 1 7
D 1 4 7 15
C 4 13 15 22
E 13 23 23 27
A 23 28 28 30
Idle time for printing process = total elapsed time - time when the last job is out of machine A
30-28=2hours.
Idle time for binding process = 1 + (7 - 7) + (15 - 15) + (23 - 22) + (28 - 27) = 3 hours.
There is no solution available for the general sequencing problems of n jobs through 3 machines.However we do
have a method under the circumstance that no passingof jobs is permissible and if either or both the following
conditions are satisfied.
1)The minimum time on machine A is greater than or equal to the maximum time on machine B.
2)The minimum time on machine C is greater than or equal to the maximum time on machine B
Method of Procedure:
Step1: First of all, the given problem is replaced with an equivalent problem involving n jobs and 2 fictitious
machines G and H .define the corresponding processing times Gi and Hi by
Gi=AI+BI
Hi=Bi+Ci
Step2: to the problem obtained step1 above ,the method for processing n jobs through 2 machines is applied
.The optimal sequence resulting this shall also be optimal for the given problem.
Example 1:
There are five jobs which must go through these machines A,B and C n th order ABC .Processing times of the
jobs on different machines given below.
Jobs A B C
1 7 5 6
2 8 5 8
3 6 4 7
4 5 2 4
5 6 1 3
Min.Ai=5
Max.Bi=5
Min.Ci=3
We shall now determines Gi and Hi and from them find the optimal sequence.
In accordance with the rules for determining optimal sequence in respect of n jobs processi ng on 2 machines ,
the sequence for above shall be:
3 2 1 4 5
Example 2:
The MDH Masala company has to process five items on three machines: - A, B & C. Processing times are given
in the following table:
Item Ai Bi Ci
1 4 4 6
2 9 5 9
3 8 3 11
4 6 2 8
5 3 6 7
Solution:
Item Gi = Ai + Bi Hi = Bi + Ci
1 8 10
2 14 14
3 11 14
4 8 10
5 9 13
1 4 5 3 2
Example 3:
Shahi Export House has to process five items through three stages of production, viz, cutting, sewing &
pressing. Processing times are given in the following table:
2 8 4 8
3 7 2 10
4 5 1 7
5 2 5 6
Determing an order in which these items should be processed so as to minimize the total processing time.
Solution:
The processing times for the new problem are given below.
Item Gi = Ai + Bi Hi = Bi + Ci
1 6 8
2 12 12
3 9 12
4 6 8
5 7 11
Thus, the optimal sequence may be formed in any of the two ways.
1 4 5 3 2
4 1 5 3 2
This section focuses on the sequencing problem of processing two jobs through m machines. Problems under
this category can be solved with the help of graphical method. The graphical method below is explained with the
help of the following example.
Two jobs are to be performed on five machines A, B, C, D, and E. Processing times are given in the following
table.
Machine
Sequence : A B C D E
Job 1
Time : 3 4 2 6 2
Sequence : B C A D E
Job 2
Time : 5 4 3 2 6
Solution:
Steps
Mark the processing times of job 1 & job 2 on X-axis & Y-axis respectively.
Draw the rectangular blocks by pairing the same machines as shown in the following figure.
Example 2:There are 4 job ABCD are required to be processed on four machine M1, M2,M3, M4 in that order.
Determine optimal sequence and total elapsed time.
Job M1 M2 M3 M4
A 13 8 7 14
B 12 6 8 19
C 9 7 5 15
D 8 5 6 15
Given
Job M1 M2 M3 M4
A 13 8 7 14
B 12 6 8 19
C 9 7 5 15
D 8 5 6 15
Step 1- 1st we have to convert this problem into two machine problem. For
that we have to check following condition:
Job A B C D
New M/c 5 28 26 21 19
New M/c 6 29 33 27 26
Sequencing According to consolidation Table:
Consolidated table:
Job A B C D
New M/c 5 28 26 21 19
New M/c 6 29 33 27 26
Job sequence:
JOB D B A C
Idle Time for M/c 1=Total Elapsed Time- Total time of M/c 1
=82-42= 40hrs.
Idle Time for M/c 2=Total Elapsed Time- Total time of M/c 2
=82-26= 56hrs.
Idle Time for M/c 3=Total Elapsed Time- Total time of M/c 3
= 82-26= 56hrs.
Idle Time for M/c 4=Total Elapsed Time- Total time of M/c 4
=82-63=19hrs.
Game theory is a kind of decision theory in which one's alternative action is determined after taking into
consideration all possible alternatives available to an opponent playing the similar game, rather than just by the
possibilities of various outcome results. Game theory does not insist on how a game must be played but tells the
process and principles by which a particular action should be chosen. Therefore it is a decision theory helpful in
competitive conditions.
Properties of a Game
1. Competitive game:
A competitive situation is known as competitive game if it has the four properties
1. There are limited number of competitors such that n ≥ 2. In the case of n = 2, it is known as two-person
game and in case of n > 2, it is known as n-person game.
2. Each player has a record of finite number of possible actions.
3. A play is said to takes place when each player selects one of his activities. The choices are supposed to
be made simultaneously i.e. no player knows the selection of the other until he has chosen on his own.
4. Every combination of activities finds out an outcome which results in a gain of payments to every player,
provided each player is playing openly to get as much as possible. Negative gain means the loss of same
amount.
2. Strategy
The strategy of a player is the determined rule by which player chooses his strategy from his own list during the
game. The two types of strategy are
1. Pure strategy
2. Mixed strategy
Pure Strategy
If a player knows precisely what another player is going to do, a deterministic condition is achieved and
objective function is to maximize the profit. Thus, the pure strategy is a decision rule always to choose a
particular strategy.
Mixed Strategy
If a player is guessing as to which action is to be chosen by the other on any particular instance, a probabilistic
condition is achieved and objective function is to maximize the expected profit. Hence the mixed strategy is a
choice among pure strategies with fixed probabilities.
In repeated games, the chronological nature of the relationship permits for the acceptance of strategies
that are dependent on the actions chosen in previous plays of the game.
Most contingent strategies are of the kind called as "trigger" strategies.
In the investment game, if you are sender: At start play Send. Play Send providing the receiver plays Return. If
the receiver plays keep, then never go for Send again. This is called as the "grim trigger" strategy.
3. Number of persons
When the number of persons playing is 'n' then the game is known as 'n' person game. The person here
means an individual or a group aims at a particular objective.
3. Number of activities
The activities can be finite or infinite.
4. Payoff
Payoff is referred to as the quantitative measure of satisfaction a person obtains at the end of each play
6. Payoff matrix
Assume the player A has 'm' activities and the player B has 'n' activities. Then a payoff matrix can be made by
accepting the following rules
Row designations for every matrix are the activities or actions available to player A
Column designations for every matrix are the activities or actions available to player B
Cell entry Vij is the payment to player A in A's payoff matrix when A selects the activity i and B selects
the activity j.
In a zero-sum, two-person game, the cell entry in the player B's payoff matrix will be negative of the
related cell entry Vij in the player A's payoff matrix in order that total sum of payoff matrices for player
A and player B is finally zero.
Value of the game is the maximum guaranteed game to player A (maximizing player) when both the players
utilizes their best strategies. It is usually signifies with 'V' and it is unique.
Classification of Games:
Games where players select activities simultaneously are simultaneous move games.
- Examples: Sealed-Bid Auctions, Prisoners' Dilemma.
- Must forecast what your opponent will do at this point, finding that your opponent is also doing
the same.
Games where players select activities in a particular series or sequence are sequential move games.
Advise: If you plan to follow an aggressive strategy, ask yourself whether you are in a one-shot game or
in repeated game. If a repeated game then think again.
The technique for solving these two types changes. By solving a game, we require to determine best strategies
for both the players and also to get the value of the game. Saddle point method can be used to solve pure
strategy games.
The diverse methods for solving a mixed strategy game are
Dominance rule
Analytical method
Graphical method
Simplex method
Classification of Games:
Simultaneous vs. Sequential Move Games
Games where players select activities simultaneously are simultaneous move games.
- Examples: Sealed-Bid Auctions, Prisoners' Dilemma.
Games where players select activities in a particular series or sequence are sequential move games.
- Examples: Bargaining/Negotiations, Chess.
- Must look forward so as to know what action to select now.
- Many sequential move games have deadlines on moves.
Advise: If you plan to follow an aggressive strategy, ask yourself whether you are in a one-shot game or
in repeated game. If a repeated game then think again.
The technique for solving these two types changes. By solving a game, we require to determine best strategies
for both the players and also to get the value of the game.Saddle point method can be used to solve pure
strategy games.
The diverse methods for solving a mixed strategy game are
Dominance rule
Analytical method
Graphical method
Simplex method
In a zero-sum game, the pure strategies of two players constitute a saddle point if the corresponding
entry of the payoff matrix is simultaneously a maximum of row minima and a minimum of column
maxima. This decision-making is referred to as the minimax-maximin principle to obtain the best
possible selection of a strategy for the players.
In a pay-off matrix, the minimum value in each row represents the minimum gain for player A. Player A
will select the strategy that gives him the maximum gain among the row minimum values. The selection
of strategy by player A is based on maximin principle. Similarly, the same pay-off is a loss for player B.
The maximum value in each column represents the maximum loss for Player B. Player B will select the
strategy that gives him the minimum loss among the column maximum values.
The selection of strategy by player B is based on minimax principle. If the maximin value is equal to
minimax value, the game has a saddle point (i.e., equilibrium point). Thus the strategy selected by player
A and player B are optimal
Example 1: Consider the example to solve the game whose pay-off matrix is given in the following table as
follows:
Game Problem
The game is worked out using minimax procedure. Find the smallest value in each row and select the largest
value of these values. Next, find the largest value in each column and select the smallest of these numbers. The
procedure is shown in the following table.
Minimax Procedure
Example 2: Check whether the following game is given in Table, determinable and fair.
Game Problem
Example 3: Identify the optimal strategies for player A and player B for the game, given below in Table.
The game is strictly determinable and fair. The saddle point exists and the game has a pure strategy. The optimal
strategies are given in the following table.
Optimal Strategies
A 2 x2 payoff matrix where there is no saddle point can be solved by analytical method.
Given the matrix
Example 1:
Solution:
It is a 2 x 2 matrix and no saddle point exists. We can solve by analytical method
Example 2:
Solution:
Example 1: Solve the game with the pay-off matrix for player A as given in table.
Game Problem
Minimax Procedure
Select the largest element in row and smallest element in column. Check for the minimax criterion,
1=1
Optimum Strategy:
Player A A2 Strategy
Player B B1 Strategy
Example 2: Solve the game with the payoff matrix given in table and determine the best strategies for the
companies A and B and find the value of the game for them.
Game Problem
Maximin Procedure
Example 1:
A and B play a game in which each has three coins, a 5 paise, 10 paise and 20 paise coins. Each player selects a
coin without the knowledge of the other’s choice. If the sum of the coins is an odd amount, A wins B’s coins. If
the sum is even, B wins A’s coins. Find the optimal strategies for the players and the value of the game.
Solution:
The pay of matrix for the given game is: Assume 5 paise as the I strategy, 10 paise as the II strategy and the 20
paise as the III strategy.
5 10 20
I II III
5 I –10 15 25
A 10 II 15 –20 –30
20 III 25 –30 –40
5 10 20
I II III Row
minimum
5 I –5 10 20 –5
A 10 II 5 –10 –10 –10
20 III 5 –20 –20 –20
Column 5 10 20
maximum.
The problem has no saddle point. Column I and II are dominating the column III. Hence it is removed from the
game. The reduced matrix is:
5 10
I II Row
minimum
5 I –5 10 –5
A 10 II 5 –10 –10
20 III 5 –20 –20
Column 5 10
maximum.
The problem has no saddle point. Considering A, row III is dominated by row II, hence row III is eliminated
from the matrix. The reduced matrix is:
I II Row minimum
I –5 10 –5
A
II 5 –10 –10
Colum 5 10
maximum.
y2 = 0
Problem 1:
Solve the game whose payoff matrix is:
I II III
I –4 3 –1
A
II 6 –4 –2
Column maximum.
No saddle point.
Sub game I:
No saddle point. First let us find the value of the sub games by applying the formula. Then compare the values
of the sub games; which ever is favorable for the candidate, that sub game is to be
selected.NowhereasAhasonlytwostrategiesandBhasthreestrategies,thegame,whichisfavorable to B, is to be
selected.
Problem 1:
I II
I 1 8
A II 3 5
III 11 2
Solution:
I II Row minimum
I 1 8 1
A
III 11 2 2
Column 11 8
maximum.
No saddle point. Hence the value of the game v2 = (a11 a22 – a12 a21) / (a11 + a22) – (a12 + a21)
= [(1) × (2) – (8) × (11)] / (3) – (19) = (3 – 88) / (– 16) = (85 / 16)
A’s Sub game No. 3:
I II Row minimum
II 3 5 3
A III 11 2 2
Column 11 5
maximum.
No saddle point. Hence the value of the game v3 =(a11 a22 – a12 a21) / (a11 + a22) – (a12 + a21)
x2 = 1 – (9 / 16) = (7/16)
y1 = (a22 – a12) / (a11 + a22) – (a12 + a21) or = 1 – y2 = (2 – 8) / (– 16) = (6 / 16)
y2 = 1 – (6 / 16) = ( 10 / 16) .
A (9 / 16, 0, 7 / 16), B (6 / 16, 10 / 16) and value of the game v = (85 / 16) = 5.31
Graphical method:
The graphical method is used to solve the games whose payoff matrix has
Draw two vertical axes 1 unit apart. The two lines are x1= 0, x1= 1
Take the points of the first row in the payoff matrix on the vertical line x1= 1 and the points of the
second row in the payoff matrix on the vertical line x1= 0.
The point a1jon axis x1= 1 is then joined to the point a2jon the axis x1= 0 to give a straight line. Draw
‘n’ straight lines for j=1, 2... n and determine the highest point of the lower envelope obtained. This will
be the maximin point.
The two or more lines passing through the maximin point determines the required 2 x 2 payoff matrix.
This in turn gives the optimum solution by making use of analytical method.
Example 1:
Solution:
Solution:
V = 8/7
SA= (3/7, 4 /7)
SB= (2/7, 0, 5 /7)
3 –1 1
A
–4 –2
II 4
Column Maximum. 3 1
The game has saddle point (1,3), the element is (–1). Hence the value of the game v3 =-1.
Comparing the two values v1 and v2, v2, and v3, both v2 and v3 have negative values, which are favorable to
player B. But v2 is more preferred by B as it gives him good returns. Hence B prefers to play strategies I and III.
Hence sub game II is selected. For this game we have to find the probabilities of strategies. For sub game II the
probabilities of strategies are:
x1= (a22 – a21) / (a11 + a22) – (a12 + a21) or = 1 – x2 = [(–2) – 6] / (– 11) = ( 8 / 11), hence
x2= 1 – (8 / 11) = 3 / 11
y1 = (a22 – a12) / (a11 + a22) – (a12 + a21) or = 1 – y2 = [(–2) – (–1)] / –11 = (1 / 11), Hence
Draw two vertical axes 1 unit apart. The two lines are x1=0, x1= 14
Take the points of the first row in the payoff matrix on the vertical line x1= 1 and the points of the second
row in the payoff matrix on the vertical line x1= 0.
The point a1jon axis x1= 1 is then joined to the point a2jon the axis x1= 0 to give a Straight line. Draw
‘n’ straight lines for j=1, 2... n and determine the lowest point of the upper envelope obtained. This will
be the minimax point.
The two or more lines passing through the minimax point determines the required 2 x 2 payoff matrix.
This in turn gives the optimum solution by making use of analytical method.
Example 1:
Solution:
Example 2
Solution:
INTRODUCTION:
In previous chapters, we have seen how to solve the problems, where decision is made in single stage, one time
period. But we may come across situations, where we may have to make decision in multistage, i.e. optimization
of multistage decision problems. Dynamic programming is a technique for getting solutions for multistage
decision problems. A problem, in which the decision has to be made at successive stages, is called a multistage
decision problem. In this case, the problem solver will take decision at every stage, so that the total effectiveness
defined over all the stages is optimal. Here the original problem is broken down or decomposed into small
problems, which are known as sub problems or stages which is much convenient to handle and to find the
optimal stage. For example, consider the problem of a sales manager, who wants to start from his head office
and tour various branches of the company and reach the last branch. He has to plan his tour in such a way that he
has to visit number of branches and cover less distance as far as possible. He has to divide the network of the
route connecting all the branches into various stages and workout, which is the best route, which will help him
to cover more branches and less distance. We can give plenty of business examples, which are multistage
decision problems. The technique of Dynamic programming was developed by Richard Bellman in the early
1950.
Discrete or Continuous systems: There are two ways of solving (computational procedure) recursive equations
depending on the type of the system. If the system is continuous one the procedure is different and if the system
is discrete, we use a different method of computation. If the system is discrete, a tabular computational scheme
is followed at each stage. The number of rows in each table is equal to the number of corresponding feasible
state values and the number of columns is equal to the number of possible decisions. In case of continuous
system, the optimal decision at each stage is obtained by using the usual classical technique such as
differentiation etc.
Forward and Backward Equations: If there are ‘n’ stages, and recursive equations for each stage is f1, f2
……fn and if they are solved in the order f1 to fn and optimal return for f1 is r1 and that of f2 is r2 and so
on, then the method of calculation is known as forward computational procedure.
On the other hand, if they are solved in the order from fn, fn-1, ….. f1, then the method is termed as
backward computational procedure. (e.g. Solution to L.P.P. by dynamic programming).
The Algorithm
Identify the decision variables and specify objective function to be optimized under certain limitations, if
any.
Decompose or divide the given problem into a number of smaller sub-problems or stages. Identify the state
variables at each stage and write down the transformation function as a function of the state variable and
decision variables at the next stage.
Write down the general recursive relationship for computing the optimal policy. Decide whether forward or
backward method is to follow to solve the problem.
Construct appropriate stage to show the required values of the return function at each stage.
Determine the overall optimal policy or decisions and its value at each stage. There may be more than one
such optimal policy.
CHARACTERISTICS OF DYNAMIC PROGRAMMING:
The basic features, which characterize the dynamic programming problem, are as follows:
PROBLEMS
A company has 8 salesmen, who have to be allocated to four marketing zones. The return of profit from each
zone depends upon the number of salesmen working that zone. The expected returns for different number of
salesmen in different zones, as estimated from the past records, are given below. Determine the optimal allocation
policy.
Solution:
4 4
Zone 1
0 1 2 3 4 5 6 7 8
Salesmen
Return 45 58 70 82 93 101 108 113 118
Zone 2
Salesmen Return
Number of salesmen. 0 1 2 3 4 5 6 7 8
Zone 1 0 0 0 1 2 3 4 4 4 3
Zone 2 0 1 2 2 2 2 2` 3 4 5
Outcome in Rs. × 1000 75 90 105 118 130 142 15 162 172 172
3
Now in the second stage, let us combine zone 3 and zone 4 and get the total market returns.
Combination of zone 3 and zone 4.
Zone 3
Salesmen 0 1 2 3 4 5 6 7 8
Return. 35 45 52 64 72 82 93 98 100
Zone 4
Salesmen Return.
Now the table below shows the allocation and the outcomes for zone 3 and zone 4.
Number of Salesmen 0 1 2 3 4 5 6 7 8
Zone 3 0 1 1 2 3 5 1 1 2 3
Zone 4 0 0 1 1 1 0 5 6 5 5
Return in Rs. × 1000 77 97 99 106 118 130 140 147 147 159
In third stage we combine both zones 1 & 2 outcomes and zones 3 and 4 outcomes.
Zones 1 and 2 and zones 3 and 4 combined.
Zones 1& 2 (0, 0) (0, 1) (0, 2) (1, 2) (2, 2) (3, 2) (4, 2) (4, (4, 4)(3,
Salesmen 0 1 2 3 4 5 6 3) 5)
7 8
Return. 75 90 105 118 130 142 153 163 172
Zones 3 &
4
Salesmen Retur
n.
0(0,0) 77 152 187 182 195 207 219 230 240 247
1(1,0) 97 172 187 202 215 302 239 243 260
2(1,1) 99 174 189 204 217 229 241 252
3(2,1) 106 181 196 211 224 236 248
4 (3,1) 118 193 208 223 236 248
5(5,0) 130 205 220 235 248
6(1,5) 140 215 230 245
7(1,6)
( 2,5) 147 222 237
8( 3,5) 159 234
Salesmen 0 1 2 3 4 5 6 7 8
Zone 1 0 0 1 0 1 2 3 4 4
Zone 2 0 0 0 2 2 2 2 2 3
Zone 3 0 1 1 1 1 1 1 1 1
Zone 4 0 0 0 0 0 0 0 0 0
Total return in Rs. × 152 187 187 202 215 302 239 243 26
The above table shows that how salesmen are allocated to various zones and the optimal outcome for the
allocation. Maximum outcome is Rs. 260 × 1000.
Problem 2.
The owner of a chain of four grocery stores has purchased six crates of fresh strawberries. The estimated
probability distribution of potential sales of the strawberries before spoilage differs among the four stores. The
following table gives the estimated total expected profit at each store, when it is allocated various numbers of
crates:
Number of Crates 1 2 3 4
0 0 0 0 0
1 4 2 6 2
2 6 4 8 3
3 7 6 8 4
4 7 8 8 4
5 7 9 8 4
6 1 10 8 4
For administrative reasons, the owner does not wish to split crates between stores. However he is willing to
distribute zero crates to any of his stores.
Solution
Let the four stores be considered as four stages in dynamic programming formulation. The decision variables xi
(i = 1, 2, 3 and 4) denote the number of crates allocated to the i th stage. Let f (x i) be the expected profit from
allocation of xi crates to the store ‘i’, then the problem is:
Maximize Z = f1 (x1) + f2 (x2) + f3 (x3) + f4 (x4) subject to x1 + x2 + x3 + x4 = 6 and all xi = 0
No. of 0 1 2 3 4 5 6
crates
Profit. 0 6 8 8 8 8 8
No. of Profit.
crates
0 0 0 6 8 8 8 8 8
1 2 2 3 10 10 10 10
2 3 3 9 11 11 11
3 4 4 10 12 12
4 4 4 10 12
5 4 4 10
No. of 0 1 2 3 4 5 6
crates
Store 3 0 1 2 2 2 2 3 2
Store 4 0 0 0 1 2 3 3 4
Profit 0 6 8 10 11 12 12
No. of 0 1 2 3 4 5 6
crates
Profit 0 4 6 7 7 7 7
No. of Profi
crates t
0 0 0 4 6 7 7 7 7
1 2 2 6 8 9 9 9
2 4 4 8 10 11 11
3 6 6 10 12 12
4 8 8 12 14
5 9 9 13
6 10 10
No. of 0 1 2 3 4 5 6
crates
Store 1 0 1 2 1 2 1 2 1 2 1 2
Store 2 0 0 0 1 1 2 2 3 3 4 4
Profit. 0 4 6 6 8 8 10 10 12 12 14
No. of crates 0 1 2 3 4 5 6
0, 0 1, 0 2, 0 2, 1 2,2 2, 3 2
3
Profit 0 6 8 10 11 12 12
No. of crates Profi
t
0 (0, 0) 0 0 6 8 10 11 12 12
1 (1, 0) 4 4 10 12 14 15 16
2 (2, 0), (1, 1) 6 6 12 14 16 17
3 (2, 1), (1, 2) 8 8 14 16 18
4 (2,2), (1, 3) 10 10 16 18
5(2, 3), (1, 4) 12 12 18
No. of 0 1 2 3 4 5 6
crates
Store 1 2 1 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1
Store 2 0 1 0 1 2 0 1 0 2 3 1 2 0 1 3 4 2 3 1 2
Store 3 1 1 2 1 1 2 2 2 1 1 2 2 2 2 1 1 2 2 2 2
Store 4 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1
Profit. 0 6 10 12 14 16 18
A vessel is to be loaded with stocks of 3 items. Each item ‘i’ has a weight of wi and a value of vi. The maximum
cargo weight the vessel can take is 5 and the details of the three items arte as follows:
j wj vj
1 1 30
2 3 80
3 2 65
Develop the recursive equation for the above case and find the most valuable cargo load without exceeding the
maximum cargo weight by using dynamic programming.
Solution:
Let us represent the three items as xj ( j = 1, 2, 3) and we have to take decision how much of each item is to be
loaded into the vessel to fulfil the objective. Let fj (xj) is the value of optimal allocation for the three items, and
if f (s, x ) is the value associated with the optimum solution f * (s) for (j = 1, 2
Now as the weight value of item number 1 is 1 (= w1) only and the maximum load (W) that can be loaded is 5
the largest value of item number one that can be loaded is = W/w1 = 5/1 = 5. The tabular computation for stage 1
is:
x1 0 1 2 3 4 5 f * (s) x*1
1
s - - - - - - - -
0 0 0 0
1 0 30 30 1
2 0 30 60 60 2
3 0 30 60 90 90 3
4 0 30 60 90 120 120 4
5 0 30 60 90 120 15 150 5
The entries in the above table are obtained as follows: As the five items can be loaded as W/w1 = 5, when
load is zero the value is 30 × 0 = 0, when load is 1, value 30 × 1 = 30 and so on. The maximum in the row is
written in 8th column, i.e. 0, 30, 60, ….., 150. And the load for that weight is written in the last column.
Similarly we can write for item number 2.
Specimen calculations:
For zero load: [80 × 0 + f1 (0 + 3 × 0) = 0.
For load 1: [80 + 0] = 80.
The load of item 2 that can be loaded is W/w2 = 5/3 = 1. Hence in the table for x2 only 0 and 1 are shown.
Value of 80 x2 +f * (s – 3x2).
x2 0 1 f * (s) x
2 *
2
s - - - - - - - -
0 0+0=0 0 0
1 0 + 30 = 30 30 0
2 0 + 60 = 60 60 0
3 0 + 90 = 90 80 + 0 = 80 90 0
4 0 + 120 = 80 + 30 = 120 0
120 110
5 0 = 150 = 80 + 60 = 150 0
150 140
As all the maximum values are due to item number 1, the item number 2 is not loaded into the cargo. Hence here
x2 = 0.
For stage 3, the items that can be loaded into cargo is S/w3 = 5/2 = 2. Hence 0, 1, 2 are shown in the table.
x3 0f 1 2 f * (s) x*3
3
s - - - - - - - -
0 0+0=0 0 0
1 0 + 30 = 30 30 0
2 0 + 60 = 60 65 + 0 = 65 65 1
3 0 + 90 = 90 65 + 35 = 95 1
95
4 0 + 120 = 65 + 60 = 130 + 0 = 130 2
120 125 130
5 0 + 150 = 65 + 90 = 130 + 30 = 160 2
150 155 160
In the above table, x1 = 1, x2 = 0 and x3 = 2 and the maximum value is 160, therefore answer is:
x*1 = 1, x*3 = 2 and f*3 = 160.
Maximize Z = a1 x1 + a2 x2 + a2 x3 + a4 x4 s.t.
For item number 1f1 (x1) = Max [a1 v1] where the value of a1 may be anything between maximum weight (W)
allowed divided by item weight (w). Here W/w = 17/1 = 17.
For item number 2, f2 (x2) = Max [a2 v2 + f1 (x2 – a2 w2)] For item number 3, f3 (x3) = Max [a3 v 3 + f2 ( x3
– a3 w3)] For item number 4, f4 (x4) = Max [ a4 v4 + f3 ( x4 – a4 w4)]
In general, for item ‘i’ fi (xi) = Max. [av + fi – 1 (xi – ai wi) is the recursive equation.
In the given problem the recursive equations are:
1. x 1 v1
Substituting the value stage by stage, the values are tabulated in the table given below: (Remember as there are 4
items, this is a 4-stage problem.
Answer: To maximize the value of the cargo load 1 unit of item 1, 1 unit of item 3 and 2 units of item 4. The
maximum value of the cargo is 30.
Problem 5:
In a cargo-loading problem, there are four items of different unit weight and value. The maximum cargo load is 6
units. How many units of each item are loaded to maximize the value?
Solution:
W 0 4 8 12 16
C 0 1 2 3 4
W d Z Z 0 5 10 15 20
0 0 0 0 0, 5 8,
10
4 1 4 4, 4, 5
4
8 2 8 8,
8
Here for c = 1 and d = 1 the element (4, 5) has selected instead of (8, 8) and (8, 10) because it is within the given
limit of maximum load 6 units.
C 0 1 1
D 0 0 1
W 0 4 4
Z 0 5 5
W 0 1 2 3 4 5 6
a 0 1 2 3 4 5 6
W b Z Z 0 1 2 3 4 5 6
0 0 0 0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6
3 1 3 3, 3 3, 3
6 2 6 6, 6
A 0 0 1 0 6
B 0 1 0 2 0
W 0 3 3 6 6
Z 0 3 3 6 6
Now combining, a and b with c and d we get.
W 0 4 4
c 0 1 1
d 0 0 1
W a b Z Z 0 5 5
0 0 0 0 0 4, 5(0,0,1,0) 4, 5(0, 0, 1,
1)
Determine the value of u1 , u2, and u3 so as to Maximize u1. u2. u3 subject to u1 + u2 + u3 = 10 and u1, u2 and
u3 all = 0.
Solution
This can be treated as a 3-stage problem, with the state variable xi and the return fi (xi), such that
At stage 3,x3 = u1 + u2 + u3 = 10,
at stage 2,x2 = x3 – u3 = u1 + u2,
at stage 1x1 = x2 – u2 = u1.
and the returns are:
f3 (x3) = max [u3 f2 (x2)]
f2 (x2) = max [ u2 f1(x1)]
Since u1 = (x2 – u2)
f1 (x1) = u1
f2 (x2) = max [ u2 ( x2 – u2)] = max [ u2 x2 – u22]
Differentiating [u2 x2 – u22] w.r.t. u2 and equating to zero (to find the maximum value)
u2 – 2 u2 = 0 or u2 = (x2/2), therefore,
f2 (x2) = (x2/2) . x2 – (x2/2)2 = (x22/4)
Differentiating [u3 . (x3 – u3)2 / 4] w.r.t. u3 and equating to zero, (1/4) [u3 . 2 (x3 – u2) (–1) + (x3 – u3)2] = 0 or
(x3 – u3) (– 2 u3 + x3 – u3) = 0 or (x3 – u3) (x3 – 3u3) = 0.
Now, either u3 = x3, which is trivial as u1 + u2 + u3 = x3 or u3 = (x3/3) = (10/3) Therefore, u2 (x2/2) = (x3 –
u3)/2 = (1/2) [10 – (10/3)] = (10/3)u1 = x2 – u2 = (20/3) – (10/3) = (10/3)
Therefore, u1 = u2 = u3 = (10/3) and maximum (u1 . u2. u3) = (1000/27).
Quadratic approximation is an extension of linear approximation, where we are adding one more term, which is
related to the second derivative. The formula fo r the quadratic approximation of a function f(x) for values of x
near x"0" is :
We got from the linear approximation to the quadratic one by adding one more term that is related to the second
derivatives:
These are more complicated and so are only used when higher accuracy is needed.
The quadratic approximation also uses the point x=a to approximate nearby values, but uses a parabola instead
of just a tangent line to do so.
This gives a closer approximation because the parabola stays closer to the actual function.
Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’
→ S.
Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed earlier)
Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed earlier)
Step 4 − Remove all direct and indirect left-recursion.
Step 5 − Do proper substitutions of productions to convert it into the proper form of GNF.
Example: Convert the following grammar G into Greibach Normal Form (GNF).
S→ X A|BB
B → b|SB
X→b
A→a
To write the above grammar G into GNF, we shall follow the following steps:
1. Rewrite G in Chomsky Normal Form (CNF) It is already in CNF.
2. Re-label the variables
S with A1
X with A2
A with A3
B with A4
After re-labeling the grammar looks like:
A1 → A2 A3|A4A4
A4 → b|A1 A4
A2 → b
A3 → a
Identify all productions which do not conform to any of the types listed below:
Ai → Aj xk such that j > I
Zi → Aj xk such that j ≤ n
Ai → axk such that xk ∈ V ∗ and a ∈ T
A4 → A1 A4 ................ identified
A4 → A1 A4 |b.
To eliminate A1 we will use the substitution rule A1 → A2 A3|A4A4 .
Therefore, we have A4 → A2 A3A4 |A4A4 A4|b
The above two productions still do not conform to any of the types in step 3.
Thus, much of the discussion of the previous chapters does point to the considerable algorithmic potential of
using higher order, specifically quadratic, approximating functions for solving constrained problems. In this
chapter we examine in some detail various strategies for using quadratic approximations. We begin by briefly
considering the consequence of direct quadratic approximation, the analog of the successive LP strategy.
Then we investigate the use of the second derivatives and Legrangian constructions to formulate quadratic
programming (QP) sub problems, the analog to Newton’s method. Finally, we discuss the application of quasi-
Newton formulas to generate updates of quadratic terms.
We will find that the general NLP problem can be solved very efficiently via a series of sub problems consisting
of a quadratic objective function and linear constraints, provided a suitable line search is carried out from the
solution of each such subproblem. The resulting class of exterior point algorithms can be viewed as a natural
extension of quasi-Newton methods to constrained problems.
Direct Quadratic Approximation:-
The solution of the general NLP problem is by simply replacing each nonlinear function by its local quadratic
approximation at the solution estimate x0 and solving the resulting series of approximating subproblems. If each
function ƒ(x) is replaced by its quadratic approximation
then the subproblem becomes one of minimizing a quadratic function subject to quadratic equality and
inequality constraints. While it seems that this subproblem structure ought to be amendable to efficient solution,
in fact, it is
not. To be sure, the previously discussed strategies for constrained problems can solve this subproblem but at no
real gain over direct solution of the original problem. For a sequential strategy using subproblem solutions to be
effective, the subproblem solutions must be substantially easier to obtain than the solution of the original
problem. Recall from the discussion in Section 9.2.3 that problems with a quadratic positive-definite objective
function and linear constraints can be solved in a finite number of reduced gradient iterations provided that
quasi-Newton or conjugate gradient enhancement of the reduced gradient direction vector is used. Of course,
while the number of iterations is finite, each iteration requires a line search, which strictly speaking is itself not a
finite procedure. However, as we will discover in Chapter 11, there are specialized methods for these so-called
QP problems that will obtain a solution in a finite number of iterations without line searching, using instead
simplex like pivot operations. Given that QP problems can be solved efficiently with truly finite procedures, it
appears to be desirable to formulate our approximating sub problems as quadratic programs. Thus, assuming that
from the initial feasible estimate x 0 = (2, 1) using the direct successive QP strategy.
At x0, ƒ(x 0) = 12.25, h(x0) = 0, and g(x 0) = 2 > 0. The derivatives required to construct the QP subproblem are
Since the first constraint can be used to eliminate one of the variables, that is,
d1 = - 2d2
the resulting single-variable problem can be solved easily analytically to give
at which point
Note that the objective function value has improved substantially but that the equality constraint is violated.
Suppose we continue with the solution procedure. The next subproblem is
Note that both the objective function value and the equality constraint violation are reduced. The next two
iterations produce the results
x(3) = (1.00108, 1.99313) ƒ(x(3)) = 5.00457 h(x(3)) = - 4.7 * 10-3
x(4) = (1.00014, 1.99971) ƒ(x(4)) = 5.00003 h(x(4)) = -6.2 * 10-6
The exact optimum is x* (1, 2) with ƒ(x*) 5.0; a very accurate solution has been obtained in four iterations. As
is evident from Figure 10.1, the constraint linearization’s help to define the search directions, while the quadratic
objective function approximation effectively fixes the step length along that direction. Thus, the use of a
nonlinear objective function approximation does lead to non-vertex solutions. However, as shown in the next
example, the self-bounding feature of the quadratic approximation does not always hold.
The optimal solution to this problem is identical to that of Example 10.1. With the starting point x0 = (2, 1) the
first subproblem becomes
The solution to this subproblem is d0 = (1.7571, 0.24286), at which both constraints are tight. Thus, a
subproblem corner point is reached. The resulting intermediate solution is
x1 = x0 + d0 = (0.24286, 0.75714)
with
ƒ(x(1)) = 0.18388 h(x(1)) = 9.7619 g(x(1)) = 0
Although the objective function value decreases, the equality constraint vio- lation is worse. The next
subproblem becomes
Again, g(x) is tight. The next few points obtained in this fashion are
These and all subsequent iterates all lie on the constraint g(x) = 0. Since the objective function decreases
toward the origin, all iterates will be given by the intersection of the local linearization with g(x) = 0. Since the
slope of the linearization becomes larger or smaller than -1 depending upon which side of the constraint
‘‘elbow’’ the linearization point lies, the successive iterates simply follow an oscillatory path up and down the
surface g(x)=0.
Evidently the problem arises because the linearization cannot take into account the sharp curvature of the
constraint h(x) = 0 in the vicinity of the optimum. Since both the constraint and the objective function shapes
serve to define the location of the optimum, both really ought to be taking into ac-count.
Minimize ƒ(x)
Subject to h(x) = 0
Sufficient conditions for x* to be a local minimum (see Theorem 5.7 of Chapter 5) are that conditions (10.1)
hold and that the Hessian of the La- grangian function,
satisfies
Given some point , we construct the following subproblem expressed in terms of the variables d:
We now observe that if d* = 0 is the solution to the problem consisting of (10.3) and (10.4), then x must satisfy
the necessary conditions for a local minimum of the original problem. First note that if d* = 0 solves the sub-
problem, then form (10.4) it follows that h(x) = 0; in other words, x is a feasible point. Next, there must exist
some v* such that the subproblem functions satisfy the Legrangian necessary conditions at d* = 0. Thus, since
the gradient of the objective function (10.3) with respect to d at d* = 0 is Qƒ(x) and that of (10.4) is Qh(x), it
follows that
Note that the second derivative with respect to d of (10.4) is zero, since it is a linear function in d. Consequently,
the above inequality implies that d T Qx2L( , v*)d is positive also. Therefore, the pair ( , v*) satisfies the
sufficient conditions for a local minimum of the original problem. This demonstration indicates that the
subproblem consisting of (10.3) and (10.4) has the following very interesting features:
1. If no further corrections can be found, that is, d = 0, then the local minimum of the original problem will
have been obtained.
By making use of the sufficient conditions stated for both equality and in- equality constraints, it is easy to arrive
at a QP subproblem formulation for the general case involving K equality and J inequality constraints. If we let
0
The algorithm retains the basic steps outlined for the direct QP case. Namely, given an initial estimate x as
0 0
well as u and v (the latter could be set equal to zero, we formulate the subproblem [Eqs. (10.7), (10.8a), and
(10.8b)]; solve it; set x(t+1) = x(t) + d; check for convergence; and repeat, using as next estimates of u and v
the corresponding multipliers obtained at the solution of the subproblem.
This is exactly the same as the fist subproblem of Example 10.1, because with the initial zero estimates of the
multipliers of the constraint terms of the Legrangian will vanish. The subproblem solution is thus, as before,
d0 = (—0.92079, 0.4604)T
Since the inequality constraint is loose at this solution, u(1) must equal zero. The equality constraint multiplier
can be found from the solution of the Legrangian necessity conditions for the subproblem. Namely,
The solution is d(1) = (0.00614, 0.38450). Again, since g˜(d(1); x(1) )> 0, u(2) = 0, and the remaining equality
constraint multiplier can be obtained from
or
with
Continuing the calculations for a few more iterations, the results obtained are
and
It is interesting to note that these results are essentially comparable to those obtained in Example 10.1 without
the inclusion of the constraint second derivative terms. This might well be expected, because at the optimal
solution
(1, 2) the constraint contribution to the second derivative of the Legrangian is small:
The basic algorithm illustrated in the preceding example can be viewed as an extension of Newton’s method to
accommodate constraints. Specifically, if no constraints are present, the subproblem reduces to
(1)
The subproblem solution is d = (+0.10434,-0.10434)T, and the multipliers are v(2) = -0.02497, u(2) = 0.38822.
At the new point x(2) = (0.40183,0.59817)T, the objective function value is 0.24036 and the constraint value is
2.7352.
The results of the next iteration,
x(3) = (0.74969, 0.25031)T ƒ(x(3)) = 0.18766 h(x(3)) = 13.416
Indicate that the constraint violation has increased considerably while the objective function value has decreased
somewhat. Comparing the status at x(1) and x(3), it is evident that the iterations show no real improvement. In
fact, both the objective function value and the equality constraint violation have increased in proceeding from
x(1) to x(3).
The solution to the problem of unsatisfactory convergence is, as in the unconstrained case, to perform a line
search from the previous solution estimate in the direction obtained from the current QP subproblem solution.
However, since in the constrained case both objective function improvement and reduction of the constraint
could be used along with some strategy for adjusting the penalty parameter R. This approach is illustrated in the
next example.
Example 5
Consider the application of the penalty function line search to the problem of Example 10.4 beginning with the
point x(2) and the direction vector d(2) = (0.34786, -0.34786)T which was previously used to compute the point
x(3) directly.
Suppose we use the penalty function
P(x, R) = ƒ(x) + 10{h(x)2 + [min(0, g(x)]2 }
and minimize it along the line
Note that at P 75.05, while at 1, P 1800.0. Therefore, a minimum ought to be found in the range 0 1.
Using any convenient line search method, the approximate minimum value P 68.11 can be found with 0.1. The
resulting point will be
x(3) = (0.43662, 0.56338)T
with ƒ(x(3)) = 0.24682 and h(x(3)) = 2.6053.
To continue the iterations, updated estimates of the multipliers are required. Since is no longer
the optimum solution of the previous subproblem, this value of d cannot be used to estimate the multipliers. The
only available updated multiplier values are those associated with d (2), namely v(3) = 0.005382 and u(3)= 0.37291.
The results of the next four iterations obtained using line searches of the penalty function after each subproblem
solution are shown in Table 10.1. As is evident from the table, the use of the line search is successful in forcing
convergence to the optimum from poor initial estimates. The use of the quadratic approximation to the
Legrangian was proposed by Wilson. Although the idea was pursued by Beale and by Bard and Greestadt, it has
not been widely adopted in its direct form.
As with Newton’s method, the barriers to the adoption of this approach in engineering applications have been
two fold: first the need to provide second derivative values for all model functions and, second, the sensitivity
relevance to defining a good search direction. (For instance, Table 10.1, v(3) = -5.38 x 10-3, while v* = -2.) Thus,
during the initial block of iterations, the considerable computational burden of evaluating all second derivatives
may be entirely wasted. A further untidy feature of the above algorithm involves the strategies required to adjust
the penalty parameter of the line search penalty function. First, a good initial estimate of the parameter must
somehow be supplied; second, to guarantee convergence, the penalty parameter must in principle be increased to
large values.
Step 2. Select the step size along d(t) and set x(t +1) = x(t) + d (t).
Step 3. Check for convergence.
Step 4. Update H(t) using the gradient difference
or line search by setting = 1. However, to assure convergence from arbitrary points, a line search is required.
Specifically, Han recommends the use of the penalty function
and
Then define
and calculate
The line search could be carried out by selecting the largest value of , 0 <= <=1, such that
However, Powell prefers the use of quadratic interpolation to generate a sequence of values of k until the more
conservative condition
is met. It is interesting to note, however, that examples have been found for which the use of Powell’s heuristics
can lead to failure to converge. Further refinements of the step-size procedure have been reported, but these
details are beyond the scope of the present treatment. We illustrate the use of a variant of the constrained
variable metric (CVM) method using update (10.11), penalty function (10.12), and a simple quadratic
interpolation-based step-size procedure.
It is easy to show that the problem solution lies at the intersection of the two constraints. Thus, d0 = (-4, 2)T, and
the multipliers at this point are solutions of the system
or
Clearly, the minimum on the line has been bounded. Using quadratic interpolation on the three trial points of
= 0, 0.1, 0.3, we obtain dash = 0.1348 with P( ) = 9.1702. Since this is a reasonable improvement
over P(0), the search is terminated with this value of . The new point is
(1) T
X = (2, 1) + (0.1348)(-4, 2) = (1.46051, 1.26974)
We now must proceed to update the matrix H. Following Powell, we calculate
z = x(1) – x0 (-0.53949, 0.26974)T
Then
where
The iterations continue with an update of H(1) .The details will not be elaborated since they are repetitious. The
results of the next four iterations are summarized below.
Recall that in Example 10.3, in which analytical second derivatives were used to formulate the QP subproblem,
comparable solution accuracy was attained in four iterations. Thus, the quasi-Newton result obtained using only
first derivatives is quite satisfactory, especially in view of the fact that the line searches were all carried out only
approximately.
It should be reemphasized that the available convergence results (superlinear rate) [6, 11] assume that the
penalty function parameters remain unchanged and that exact line searches are used. Powell’s modifications
(10.13) and (10.14) and the use of approximate searches thus amount to useful heuristics justified solely by
numerical experimentation.