OPERATIONS
rESEARCH
INTRODUCTION
TO
MODEL BUILDING
What is OPERATION RESEARCH ??
OPERATION RESEARCH is simply a scientific
approach to decision making that seeks to best
design and operate a system, usually under
conditions requiring the allocation of scarce
resources
By a system, we mean an organization of
interdependent components that work together to
accomplish the goal of system.
For Example, Ford Motor Company is a system
whose goal consist of maximize profit that can be
earned by producing quality vehicles. 3
PERSPECTIVE OR OPTIMIZATION
MODEL
The components of a perspective model include
Objective function(s)
Decision Variables
Constraints
Objective Function
In most models, there will be a function we wish to
maximize or minimize. This function is called the
models objective function.
In many situations, an organization may have more
than one objective:
Equalize the no. of students at the two high
schools
Minimize the average distance student travel to
school
Have a diverse student body at both high schools
5
The Decision Variables
The Variables whose values are under our control and
influence the performance of the system are called
decision variables.
Constraints
In most situations, only certain values of decision
variables are possible. For example, certain volume,
temperature and pressure combination might be
unsafe. Also A, B, & C must be non-negative numbers
that add to 1. Restrictions on the values of decision
variables are called constraints.
6
Static and Dynamic Models
A STATIC model is one in which decision variables
do not involve the sequences of decisions over
multiples periods.
A DYNAMIC model is model in which the decision
variable do involve sequences of decisions over
multiple periods
Other Models Types
Linear and Nonlinear Models
Integer and Non-integer Models
Deterministic and Stochastic Models
7 Step Model Building Process
Step 1: Formulate the problem
Step 2: Observe the system
Step 3: Formulate a Mathematical model of the
problem
Step 4: Verify the model and Use the model for
prediction
Step 5: Select a suitable Alternative
Step 6: Present the results and Conclusion of the
study to the organization
Step 7: Implement & Evaluate Recommendations
9
INTRODUCTION
TO
LINEAR
PROGRAMMING
10
Example 1 Giapettos
Woodcarviing
11
Solution
Decision Variables
x1 = number of soldiers produced each week
x2 = number of trains produced each week
Objective function
Fixed cost do not depend on x1 and x2. Thus, Giapetto
can concentrate on maximizing
[weekly revenues Raw material purchase cost other
variable cost]
(27x1 + 21x2) (10x1 + 9x2) (14x1 + 10x2) = 3x1 + 2x2
12
Constraints
Constraint1 = Each Week, no more than 100 hours
of finishing time may be used
Constraint2 = Each week, no more than 80 hours of
carpentry time may be used
Constraint3 = Because of limited demand, at most
40 soldiers should be produced each week
Constraint1 Constraint2 Constraint3 -
2x1 + x2 100
x1 + x2 80
x1 40
13
The coefficients of the decision variables in the
constraints are called technological coefficients. This
is because the technological coefficients often reflect
the technology used to produce different products.
For example, the technological coefficient of x2 in
constraint 2 is 1, indicating that a soldier requires 1
carpentry hour.
14
The number on the right-hand side of each constraint
is called the constraints right-hand side (or RHS).
Often the RHS of a constraint represents the quantity
of a resource that is available.
Sign Restrictions: If a decision variable xi can only
assume nonnegative values, then we add the sign
restriction xi 0. If a variable xi can assume both
positive and negative values. Then we say that xi is
unrestricted in sign (often abbreviated as (urs)
15
Optimization
model
Max 3x1 + 2x2
Subject to (s.t.)
2x1 + x2 100 (Fishing Constraint)
x1 + x2 80
(Carpentry Constraint)
x1 40
(Constraint on demand for soldier)
x1 0
(Sign Restriction)
x2 0
(Sign Restriction)
16
Example-2
Ryan corporation manufactures Brute and Chanelle perfumes. The
raw material needed to manufacture each type of perfume can be
purchased for $3 per pound. Processing 1 lb of raw material
requires 1 hour of laboratory time. Each pound of processed raw
material yield 3 oz of Regular Brute Perfume and 4 oz of Regular
Chanelle Perfumes. Regular Brute can be sold for $7/oz and
Regular Chanelle can be sold for $6/oz. Ryan also has the option
for further processing Regular Brute and Regular Chanelle to
produce Luxury Brute, sold at $18/oz, and Luxury Chanelle, sold at
$14/oz . Each ounce of Regular Brute processed further requires an
additional 3 hours of laboratory time and $4 processing cost and
yields 1 oz of Luxury Brute .Each ounce of regular Chenelle
processed further requires an additional 2 hours of laboratory time
and $4 processing cost and yield 1 oz of Luxury Chanelle. Each
year, Ryan has 6000 hours of laboratory time available and can
purchase up to 4000 lb of raw material. Formulate an LP that can be
used to determine how Ryan can maximize profits.17 Assume that the
cost of laboratory hours is fixed cost.
SolutionX1=no. of ounces of regular Brute sold annually
X2=no. of ounces of Luxury Brute sold annually
X3=no of ounces of Regular Chanelle sold annually
X4=no. of ounces of Luxury Chanelle sold annually
X5=no. of pounds of raw material purchased annually
Contribution to profit=revenues from perfumes salesprocessing costs-costs of purchasing raw material
=7X1+18X2+6X3+14X4-(4X2+4X4)-3X5
=7X1+14X2+6X3+10X4-3X5
18
Constraint1 : No more than 4000 lb of raw material can be
purchased annually.
Constraint2 :No more than 6000 hours of laboratory time can
used each year.
Constraint 1 is expressed by
X54000
Constraint 2 becomes
3X2+2X4+X5 6000
X1 oz Reg. Brute sold
3X533
oz
Brute
XXXXXXXXX
5 lb
XXxXXx5X
Raw material
xx
X2 oz Reg. Brute processed
into Lux. Brute
X3 oz Reg. Chanelle sold
4X5 oz
Chanelle
X4 oz Reg. Chanelle into
Lux. Chanelle
19
MAX Z= 7X1+14X2+6X3+10X4-3X5
S.T.
X5 4000
3X2 +2X4 + X5 6000
X1+ X2 -3X5 =0
X3 + X4 - 4X5 =0
Xi0 (i=1,2,3,4,5)
(Ounce of Brute /Pounds of raw material)*(Ounce of Brute)
20
Example 3-Sailco Corporation must determine how many sail boats
should be produced during each of the next 4 quarters(1 Quarter
=3months).The demand during each of the next four quarter is as
follows : first quarter, 40 sailboats; second quarter ,60 sailboats ;third
quarter ,75 sailboats; fourth quarter, 25 sailboats. Sailco must meet
demands on time. At the beginning of the first quarter, Sailco has an
inventory of 10 Sailboats. At the beginning of each quarter , Sailco
must decide how many sailboats should be produced during that
quarter. For simplicity, we assume that sailboat manufactured during a
quarter can be used to meet demand for that quarter. During each
quarter Sailco can produce up to 40 sailboats with regular time labor
with a total time cost $400 per sailboat. By having employee work
overtime during a quarter , sailco can produce additional sailboats with
overtime labor at a total coast of $450 per sailboat.
At the end of each quarter (after production has occurred and the
current quarters demand has been satisfied), a carrying or holding
cost of $20 per sailboat is incurred. Use linear programming to
determine a production schedule to minimize the sum of production
21
and inventory costs during the next four quarter.
Solution-Xt=no. of sailboats produced by regular-time labor (at
$400/boat) during quarter t (t=1,2,3,4)
Yt=no. of sailboats produced by overtime labor (at $450/boat) during
quarter t (t=1,2,3,4)
It=no. of sailboats on hand at end of quarter t (t=1,2,3,4)
Total Cost=cost of producing regular-time boat + cost of producing
overtime boat + inventory costs
=400(X1+X2+X3+X4)+450(Y1+Y2+Y3+Y4)+20(I1+I2+I3+I4)
MIN Z = 400X1+400X2+400X3+400X4+450Y1+450Y2+450Y3+450Y4
+20I1+20I2+20I3+20I4
Inventory at the end of quarter t = inventory at end of quarter (t-1)+
quarter t production quarter t demand
It=It-1+(Xt + Yt)-dt
(t = 1,2,3,4)
22
I1=10+X1+Y1-40
I2=I1+X2+Y2-60
I3=I2+X3+Y3-75
I4=I3+I4+Y4-25
MIN
Z=400X1+400X2+400X3+400X4+450Y1+450Y2+450Y3+450Y4
+20I1+20I2+20I3+20I4
S.T.
X1 40,
X2 40,
I1=10+X1+Y1-40 ,
I3=I2+X3+Y3-75,
Xt0, Yt0,
X3 40,
X4 40
I 2=I1+X2+Y2-60
I 4=I3+I4+Y4-25
It0 (t=1,2,3,4)
23
MIN Z= 400(X2+X3+X4+X5)+ 450(Y2+Y3+Y4+Y5)+ 20(I2+I3+I4+I5)
S.T.
X2 40,
X3 40,
X4 40,
X5 40
I2=15+X2+Y2-60,
I3=I2+X3+Y3-75
I4=I3+X4+Y4-25,
I5=I4+X5+Y5-36
It0,
Yt0 and
Xt0
(t=2,3,4,5)
To make it useful in a rolling horizon it is assumed above that 5 th
quarter demand is 36.
24
Example 4 - Finco Investment Corporation must determine
investment strategy for the firm during the next three years .
Currently (time 0), $100,000 is available for investment . Investment
A, B, C, D and E are available. The cash flow associated with
investing $1 in each investment is given in table .
For example , $1 invested in investment B requires a $1 cash
outflow at time 1 and returns 50c at time 2 and $1 at time 3. To
insure that the companys portfolio is diversified, Finco requires that
at most $75,000 be placed in any single investment. In addition to
investments A-E, Finco can earn interest at 8% per year by keeping
uninvested cash in money market funds. Returns from investment
may be immediately reinvested . For example, the positive cash
flow received from investment C at time 1 may immediately be
reinvested in investment B. Finco cannot borrow funds, so the cash
available for investment at any time is limited to cash on hand.
Formulate LP that will maximize cash on hand at time 3.
25
Cash flow ($)
at Time
0
-1
+0.5
+1
-1
+0.5
+1
-1
+1.2
-1
+1.9
-1
+1.5
NOTE: Time 0 = present;
time 1 = 1 year from now;
time 2 = 2 year from now ; time 3= 3 year from now
26
Solution: A = dollars invested in investment A
B = dollars invested in investment B
C = dollars invested in investment C
D = dollars invested in investment D
E = dollars invested in investment E
St= dollars invested in money market funds at time t
(t=0,1,2)
27
MAX Z = B+1.9D+1.5E+1.08S2
S.T.
A+C+D+S0 = 100,000
0.5A+1.2C+1.08S0 = B+S1
A+0.5B+1.08S1 = E+S2
A 75,000
B 75,000
C 75,000
D 75,000
E 75,000
A,B,C,D,E,S0,S1,S2 0
28
Example 5- CSL is a chain of computer service stores. The no. of
hours of skilled repair time that CSL requires during the next five
months is as follows:
Month 1 (January): 6,000 hours; Month 2 (February): 7,000 hours
Month 3 (March): 8,000 hours;
Month 4 (April): 9,500 hours
Month 5 (May): 11,000 hours
At the beginning of January, 50 skilled technicians work for CSL. Each
skilled technician can work up to 160 hours per month. To meet future
demands, new technicians must be trained. It takes one month to train
a new technician. During the month of training a trainee must be
supervised for 50 hours by an experienced technicians. Each
experienced technicians is paid $2000 in month (even if he or she
doesnt work the full 160 hours). During the month of training, a
trainee is paid $1000 a month. At the end of each month 5% of CSLs
experienced technician quit to join Plum Computers. Formulate a LP
whose solution will enable CSL to minimize the labor cost incurred in
meeting the service requirement for the next fine months.
29
Solution:
Xt= No. of technicians trained during month t (t= 1,2,3,4,5)
Yt= No. of experienced technicians at the beginning of month t
Total labor cost = cost of paying trainees + cost of paying
experienced technicians
MIN Z = 1,000X1 + 1,000X2 + 1,000X3 + 1,000X4 + 1,000X5
+ 2,000Y1 + 2,000Y2 + 2,000Y3 + 2,000Y4 + 2,000Y5
30
MIN Z = 1,000X1+1,000X2+1,000X3+1,000X4+1,000X5
+2,000Y1+2,000Y2+2,000Y3+2,000Y4+2,000Y5
S.T.
160Y1-50X1 6,000
Xt, Yt 0
Y1=50
160Y2-50X2 7,000
0.95Y1 + X1 =Y2
160Y3-50X3 8,000
0.95Y2 + X2 = Y3
160Y4-50X4 9,500
0.95Y3 + X3 = Y4
160Y5-50X5 11,000
0.95Y4 + X4 = Y5
(t= 1, 2, 3, 4, 5)
31
The Proportionality and
Additivity Assumptions
32
33
34
FEASIBLE REGION & OPTIMAL
SOLUTION
The feasible region for an LP is the set of all the points
that satisfies all the LPs constraints and sign
restrictions
For a maximization problem, an optimal solution to
an LP is a point in the feasible region with the largest
objective function value.
Similarly for a minimization problem, an optimal
Solution is a point in the feasible region with the
smallest objective function value.
35
Graphical Solution of Two-Variable
LPP
We illustrate how to solve two variable LPs graphically by
solving the Giapetto problem.
To begin, we graphically determine the feasible region.
Feasible region for the Giapetto Problem is the set of all
the points (x1, x2) satisfying
2x1 + x2 100 (Fishing Constraint)
x1 + x2 80
(Carpentry Constraint)
x1 40
(Constraint on demand for soldier)
x1 0
(Sign Restriction)
x2 0
(Sign Restriction)
36
37
Binding and Nonbinding Constraints
A constraint is Binding when the left-hand side and
the right-hand side of the constraint are equal when
the optimal values of the decision variables are
substituted into the constraint.
A constraint is Nonbinding when 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.
38
Exceptional Cases
Usually a LPP will have a unique optimal solution. But
there are problems where there may be no solution,
may have alternative optimum solutions and
unbounded solutions. We graphically explain these
cases in the following slides. We note that the (unique)
optimum solution occurs at one of the corners of the
set of all feasible points.
39
Alternative Optimal Solutions
Consider the LPP
Maximize
z 10 x1 5 x2
Subject to the constraints
x1
150
x2 200
2 x1 x2 400
x1 , x2 0
40
Graphical Solution
x2
Maximize z=10x1+5x2
Subject to the constraints
2x1+x2 400
(100,200)
(0,200)
z=600 z=1500
z maximum
=2000 at
(150,100)
z=1000
z=400
150
x1
x2 200
x1,x2 0
z=2000
x1
(150,0)
41
Thus we see that the objective function z is maximum at the
corner (150,200) and also has an alternative optimum
solution at the corner (100,200). It may also be noted that z
is maximum at each point of the line segment joining them.
Thus the problem has an infinite number of (finite) optimum
solutions. This happens when the objective function is
parallel to one of the constraint equations.
42
Maximize Z = 5x1 + 7 x2
Subject to
2 x1 -
x2 -1
- x1 + 2 x2 -1
x1, x2 0
No feasible solution
43
Maximize z = x1 + x2
Subject to
- x1 + 3 x2 30
-3
x1 + x2 30
x1, x2 0
unbounded solution
z=70
z=50
z=30
z=20
44
Linear Programming
45
Linear Programming Model
46
Graphical for Solution Linear Programming
47
Optimal Solution of Reddy Mikks model
48
49
50
Graphical Interpretation of Simplex method
51
Continued
52
Continued
53
Continued
54
Artificial Starting Solution
example
55
M- Method
56
Continued
57
L P Model ( M- Method )
58
Continued
59
Replace R1 and R2 in the objective function from
constraint equation:
R1= 3 - 3X1 X2
R2= 6 - 4X1 3X2 + X3
Z= (4-7M) X1 + (1-4M) X2 + MX3 + 9M
Z - (4-7M) X1 - (1-4M) X2 - MX3 = 9M
Take M as 100 to solve LP Model
60
Continued
61
Continued
62
After one more iteration we get:
Z= 17/5
X1 = 2/5
X2 = 9/5
X3 = 1
63
SENSITIVITY
ANALYSIS
64
65
66
67
68
69
70
71
