Introduction To Operations Research (OR) and Linear Programming (LP)
Introduction To Operations Research (OR) and Linear Programming (LP)
Introduction To Operations Research (OR) and Linear Programming (LP)
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
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