Introduction To Operations Research (OR) and Linear Programming (LP)

Download as pptx, pdf, or txt
Download as pptx, pdf, or txt
You are on page 1of 18

Introduction to Operations

Research (OR) and Linear


Programming (LP)
Session-1
By Prof. Prashant and Prof. Kushal
Management Science and OR
Broadly, the tasks of the manager are:
Handling Administrative Task
Problem Solving
Strategy and Innovation
Networking and bonding
The aforementioned tasks require
Formalization
Quantification
Constraints handling
Decision making
OR is about formal techniques, quantification, decision
making and constraints and limitation handling.
OR and LP
OR is a field of study where we optimize performance
under given constraints
OR also helps us develop models for decision making
Among the several topics in operations research, LP is
the most important and the most popular one.
LP problems have applications in the various fields.
Some of which include manufacturing systems, public
systems, business supply chain management and
analytics, expert systems and decision support systems
Definition of Linearity
Linearity or Linear functions are those whose graph is
a straight line
y = f(x) = a + bx
In LP, we will be dealing with linearity, i.e., each
variable will be having power one.
In LP we often use inequalities.
An inequality is a relation which makes a non-equal
comparison between two numbers or other
mathematical expressions.
Example, <, >, ≠, ≤, ≥
To begin with LP: Example-1
Formulation-1 Product mix Problem:
A shop can make two types of sweets (A and B). They
use two resources flour and sugar. To make one packet
of A, they need 3Kg. of flour and 3Kg of sugar. To
make one packet of B, they need 3Kg of flour and 4Kg
of sugar. They have 21Kg of flour and 28Kg of sugar.
These sweets are sold at Rs. 1000 and 900 per packet
respectively. Find the best product mix to maximize
the revenue.
What is the objective?
To maximize the revenue
What decisions will influence the objective?
Quantity of Sweet A to be produced
Quantity of Sweet B to be produced
What resources do we have to implement the above
decisions?
Flour
Sugar
Are the resources unlimited?
Let X1 be the number of packets of sweet A made
Decision
Let X2 be the number of packets of sweet B made
Variables
Resources
Ingredients Sweet A Sweet B
Flour Flour 3 Kg 3 Kg
3 X1  3 X 2 
Sugar 3 Kg 4 Kg
21
Suga Constraints
r
3 X1  4 X 2  28

X1, X 2  0

Non-negative
Revenue
restriction
Maximize 1000 X 1  900 X 2

Objective
Function
Characteristics of LP
Proportionality:
If I make 1 packet of sweet A then I get 1000 rupees. If I make
X1 packet of A then I will get 1000X1 rupees.
Additivity:
Additivity property says that profit obtained by selling X1
packet and X2 packet can be added.
Certainty:
We need deterministic values to formulate LP. E.g., 21Kg flour,
28 Kg sugar and so on.
Divisibility:
Since we are using continuous variables, the LP model assumes
that the decision variables can take on fractional values. 
LP Problem formulation: Example-2
The daily requirements of nurses in a private nursing
home is given by the following table:
Time of the day Requirements
8 AM to 12 noon 12
12 noon to 4PM 15
4PM to 8PM 10
8PM to 12 midnight 8
12 midnight to 4 AM 6
4 AM to 8 AM 10

The nurses start work at the beginning of the shift (e.g.


8AM, 12 noon etc.) and work for 8 continuous hours.
What is the minimum number of nurses required to meet
the daily demand?
Let X1 to X6 be the number of nurses who start Time of the day Requirements
work at 8 AM, 12 noon , 4 PM, 8PM, 12 Mid- 8 AM to 12 noon 12
night and 4 AM respectively. 12 noon to 4PM 15
4PM to 8PM 10
Subject to: 8PM to 12 8
midnight
X 1  X 2  15
12 midnight to 4 6
X 2  X 3  10 AM
X3  X4  8 4 AM to 8 AM 10
X4  X5  6
X 5  X 6  10
X 6  X 1  12
X1, X 2 , X 3 , X 4 , X 5 , X 6  0
Objective:
Minimize :

X1  X 2  X 3  X 4  X 5  X 6
LP Problem formulation: Example-3
The demand for the products for two weeks is 800 and 1000.
In a week, company can produce up to 700 units at regular
time at 100 rupees/product. It can employ over time and
produce up to an extra 300 units in a week at rupees
120/product. The cost of carrying the product from one week
to the next is rupees 15/product/week. How that company
should produce in order to meet the demand at minimum
cost.
Number of products made using regular time in week one  - X1
Number of products made using regular time in week two - X2
Number of products made using overtime in week one  - Y1
Number of products made using overtime in week two - Y2
Number of products carried from week1 to week2 - Z1
Subject to:

X 1  700
X 2  700

Y1  300
Y2  300

X 1  Y1  800  Z1
Or
X 1  Y1  Z1  800

X 2  Y2  Z1  1000

X 1 , X 2 , Y1 , Y2 , Z1  0

Objective:
Minimize :100 X 1  100 X 2  120Y1  120Y2  15Z1
Subject to:

X 1  700
X 2  700

Y1  300
Y2  300

X 1  Y1  800

Z1  X 1  Y1  800

X 2  Y2  Z1  1000

X 2  Y2  X 1  Y1  800  1000

X 1  Y1  X 2  Y2  1800

X 1 , X 2 , Y1 , Y2  0

Objective:
Minimize :100 X 1  100 X 2  120Y1  120Y2  15Z1
Minimize :100 X 1  100 X 2  120Y1  120Y2  15  X 1  Y1  800 
LP Problem formulation: Example-4
A company wants to advertise their product in four different
media- TV, newspaper, website and radio. The reach per
advertisement on these four platforms are 8000, 5000, 3000, 2000.
The cost per advertisement is 4 lakhs, 3lakhs, 2 lakhs and 1.5
Lakhs. The maximum number of advertisements the company
wishes to have in each media is 3, 4, 5, 4. The budget of the
company for the advertisement is 32 lakhs. How many
advertisements does the company decide in each media to
maximize the reach?
X1 be the number of advertisement on TV
X2 be the number of advertisement on newspaper
X3 be the number of advertisement on web
X4 be the number of advertisement on radio
LP Problem formulation: Example-4 (Cont.)
Maximize 8000X1+5000X2+3000X3+2000X4
4X1+3X2+2X3+1.5X4 ≤32
X1 ≤3
X2 ≤4
X3 ≤5
X4 ≤4
X1, X2, X3, X4≥0
LP Problem formulation: Example-5
Three friends (A, B and C) start from P towards Q
which is 5KM away. They have one cycle and only
one person rides the cycle at a time. A, b and C walk at
the speed of 4, 5, and 6 KM/hour and can ride the
cycle at 7, 8 and 10 KM/hour. How do they travel such
that all three reach Q at the earliest time?
Let X1 be the distance Cycled by A in KM
Let X2 be the distance Cycled by B in KM
Let X3 be the distance Cycled by C in KM
LP Problem formulation: Example-5 (Cont. )
That means,
(5-X1) be the distance walked by A in KM
(5-X2) be the distance walked by B in KM
(5-X3) be the distance walked by C in KM
Further, X 1 (5  X 1)

Time taken by A = 7 4

X 2 (5  X 2)

Time taken by B = 8 5
X 3 (5  X 3)

Time taken by C= 10 6

X1+X2+X3=5
LP Problem formulation: Example-5 (Cont. )
All person reach to the destination when the last
person reach.
We do not know who is the last person. He can be
either A or B or C. Suppose time taken by the last
person to reach destination is u.
Thus, u ≥X 1  (5  X 1)
7 4
X 2 (5  X 2)
Or u ≥ 
8 5

X 3 (5  X 3)
Or u ≥ 
10 6

You might also like