2. Introduction Linear programming problems.ppt

Liner Problems

1. Introduction
to
Linear Programming
Problem

2. Amity School of Engineering & Technology
2
Introduction to Linear Programming
Linear Programming is a special and versatile
technique which can be applied to a variety of
management problems viz. Advertising, Distribution,
Investment, Production, Refinery Operations, and
Transportation analysis. The linear programming is
useful not only in industry and business but also in
non-profit sectors such as Education, Government,
Hospital, and Libraries. The linear programming
method is applicable in problems characterized by
the presence of decision variables.

3. Amity School of Engineering & Technology
3
The objective function and the constraints can be
expressed as linear functions of the decision
variables. The decision variables represent
quantities that are, in some sense, controllable
inputs to the system being modeled. An objective
function represents some principal objective
criterion or goal that measures the effectiveness of
the system such as maximizing profits or
productivity, or minimizing cost or consumption.
There is always some practical limitation on the
availability of resources viz. man, material,
machine, or time for the system.

4. Amity School of Engineering & Technology
4
These constraints are expressed as linear
equations involving the decision variables.
Solving a linear programming problem means
determining actual values of the decision variables
that optimize the objective function subject to the
limitation imposed by the constraints.
The main important feature of linear
programming model is the presence of linearity
in the problem. Some model may not be strictly
linear, but can be made linear by applying
appropriate mathematical transformations.

5. Amity School of Engineering & Technology
5
Still some applications are not at all linear, but can
be effectively approximated by linear models. The
ease with which linear programming models can
usually be solved makes an attractive means of
dealing with otherwise intractable nonlinear
models.

6. Amity School of Engineering & Technology
6
Linear Programming Problem Formulation
Three components are:
1. The decision variable
2. The environment (uncontrollable) parameters
3. The result (dependent) variable

7. Amity School of Engineering & Technology
7
TERMINOLOGY USED IN LPP
1. Components of LP Problem: Every LPP is
composed of a. Decision Variable, b. Objective
Function, c. Constraints.
2. Optimization: Linear Programming attempts to
either maximize or minimize the values of the
objective function.
3. Profit or Cost Coefficient: The coefficient of
the variable in the objective function express the
rate at which the value of the objective function
increases or decreases by including in the solution
one unit of each of the decision variable.

8. Amity School of Engineering & Technology
8
4. Constraints: The maximization (or minimization)
is performed subject to a set of constraints. They
reflect the limitations of the resources.
5. Input-Output coefficients: The coefficient of
constraint variables are called the Input-Output
Coefficients. They indicate the rate at which a
given resource is unitized or depleted. They appear
on the left side of the constraints.
6. Capacities: The capacities or availability of the
various resources are given on the right hand side
of the constraints.

9. Amity School of Engineering & Technology
9
MATHEMATICAL EXPRESSION OF THE LPP
The general LPP Model can be expressed in
mathematical terms as shown below:
Let
a
ij = Input-Output Coefficient
C
j
= Cost (Profit) Coefficient
b
i
= Capacities (Right Hand Side)
X
j
= Decision Variables
Find a vector (x
1, x
2, x
3 .......... x
n) that minimize or
maximize a linear objective function F(x) where

10. Amity School of Engineering & Technology
10
F(x) = c
1
x
1
+ c
2
x
2
+ ................+ c
n
x
n

subject to constraints
a
11
x
1
+ a
12
x
2
+ ................+ a
1n
x
n
≤ b
1

a
21
x
1
+ a
22
x
2
+ ................+ a
2n
x
n
≤ b
2

.......................................................
.......................................................
.......................................................
.......................................................
a
m1x
1 + a
m2x
2 + ................+ a
mnx
n ≤ b
m
and non-negativity constraints
x
1
≥ 0, x
2
≥ 0, .................., x
n
≥ 0

11. Amity School of Engineering & Technology
11
Examples of LPP Formulation
The linear programming problem formulation is
illustrated through a product mix problem. The
product mix problem occurs in an industry where it
is possible to manufacture a variety of products. A
product has a certain margin of profit per unit, and
uses a common pool of limited resources. In this
case the linear programming technique identifies
the products combination which will maximize the
profit subject to the availability of limited resource
constraints.

12. Amity School of Engineering & Technology
12
Example 1:
Suppose an industry is manufacturing two types of
products P1 and P2. The profits per Kg of the two
products are Rs.30 and Rs.40 respectively. These
two products require processing in three types of
machines. The following table shows the available
machine hours per day and the time required on
each machine to produce one Kg of P1 and P2.
Formulate the problem in the form of linear
programming model.

13. Amity School of Engineering & Technology
13
Products
   P1P2 
Profit/Kg  Rs.30Rs.40
Total available
Machine
hours/day
Processing
Times in hrs
Machine-132 600
Machine-235 800
Machine-356 1100

14. Amity School of Engineering & Technology
14
Solution:
The procedure for linear programming problem
formulation is as follows:
Let, the decision variable be as follows:
x
1
= amount of P1
x
2
= amount of P2
In order to maximize profits, we establish the
objective function as
30x
1
+ 40x
2

15. Amity School of Engineering & Technology
15
Since one Kg of P1 requires 3 hours of processing
time in machine-1 and the corresponding
requirement of P2 is 2 hours.
So, the first constraint can be expressed as
3x
1
+ 2x
2
≤ 600
Similarly, corresponding to machine-2 and 3 the
constraints are
3x
1 + 5x
2 ≤ 800
5x
1
+ 6x
2
≤ 1100

16. Amity School of Engineering & Technology
16
In addition to the above there is no negative
production, which may be represented algebraically
as
x
1 ≥ 0 ; x
2 ≥ 0

17. Amity School of Engineering & Technology
17
Maximize
Z =30x
1
+ 40x
2
Subject to:
3x
1 + 2x
2 ≤ 600
3x
1
+ 5x
2
≤ 800
5x
1
+ 6x
2
≤ 1100
x
1≥ 0, x
2 ≥ 0

18. Amity School of Engineering & Technology
18
Example 2:
A company owns two flour mills viz. A and B,
which have different production capacities for
high, medium and low quality flour. The company
has entered a contract to supply flour to a firm
every month with at least 8, 12 and 24 quintals of
high, medium and low quality respectively. It
costs the company Rs.2000 and Rs.1500 per day
to run mill A and B respectively.

19. Amity School of Engineering & Technology
19
On a day, Mill A produces 6, 2 and 4 quintals of
high, medium and low quality flour, Mill B
produces 2, 4 and 12 quintals of high, medium
and low quality flour respectively. How many days
per month should each mill be operated in order
to meet the contract order most economically.

20. Amity School of Engineering & Technology
20
Production/Day
  HighMediumLow
Running Cost
(Rs.)
Mill
A 6 2 4 2000
B 2 4 12 1500
Supply/Month   8 1224
 

21. Amity School of Engineering & Technology
21
Let us define x
1
and x
2
are the number of days
that mills A and B are running.
Here the objective is to minimize the cost of the
machine runs and to satisfy the contract order.
The linear programming problem is given by
Minimize
2000 x
1 + 1500 x
2
Subject to: 6 x
1 + 2 x
2 ≥ 8
2 x
1 + 4 x
2 ≥ 12
4 x
1 + 12 x
2 ≥ 24
x
1
≥ 0, x
2
≥ 0

22. Amity School of Engineering & Technology
22
Example 3:
A firm produces three products. These products
are processed on three different machines. The
time required to manufacture one unit of each of
the three products and the daily capacity of the
three machines are given in the table below:

23. Amity School of Engineering & Technology
23
It is required to determine the daily number of
units to be manufactured for each product. The
profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3
and Rs.6 respectively. It is assumed that all the
amounts produced are consumed in the market.
Formulate the mathematical (L.P.) model that will
maximize the daily profit.

24. Amity School of Engineering & Technology
24
Solution:
Let the variables are x
1, x
2 and x
3 which represent
the per day production of the three products.
So, objective is to maximize the profit.
i.e., Z = 4x
1+ 3x
2 + 6x
3
Here, constraints are on the machine capacities
and can be mathematically expressed as
2x
1+ 3x
2 + 2x
3 ≤ 440
4x
1+ 0x
2 + 3x
3 ≤ 470
2x
1+ 5x
2 + 0x
3 ≤ 430
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0

25. Amity School of Engineering & Technology
25
Example 4:
A factory manufactures two products A and B. To
manufacture one unit of A, 1.5 machine hours
and 2.5 labour hours are required. To
manufacture product B, 2.5 machine hours and
1.5 labour hours are required. In a month, 300
machine hours and 240 labour hours are
available. Profit per unit for A is Rs. 50 and for B
is Rs. 40. Formulate as LPP.

26. Amity School of Engineering & Technology
26
Solution:
There will be two constraints. One for machine
hours availability and for labour hours availability.
Decision variables X
1
= Number of units of A
manufactured per month. X
2 = Number of units of
B manufactured per month.

27. Amity School of Engineering & Technology
27
The objective function:
Max Z = 50x
1+ 40x
2
Subjective Constraints
For machine hours
1.5x
1
+ 2.5x
2
≤ 300
For labour hours
2.5x
1+ 1.5x
2 ≤ 240
Non negativity
x
1, x
2 ≥0

28. Amity School of Engineering & Technology
28
Example 5: PORTFOLIO SELECTION
An investor is considering investing in two securities
'A' and 'B'. The risk and return associated with
these securities is different. Security 'A' gives a
return of 9% and has a risk factor of 5 on a scale of
zero to 10. Security 'B' gives return of 15% but has
risk factor of 8. Total amount to be invested is Rs.
5, 00, 000.Total minimum returns on the investment
should be 12%. Maximum combined risk should not
be more than 6. Formulate as LPP.

29. Amity School of Engineering & Technology
29
Solution:
Decision Variables:
X
1
= Amount invested in Security A
X
2 = Amount invested in Security B
Objective Function:
The objective is to maximize the return on total
investment.
Max Z = 0.09 X
1 + 0.15 X
2
Note: Here, 9% = 0.09 and15% = 0.15.

30. Amity School of Engineering & Technology
30
Constraints:
1. Related to Total Investment:
X
1
+ X
2
= 5, 00, 000
2. Related to Risk:
5 X
1 + 8 X
2 = (6 X 5, 00, 000)
or5 X
1
+ 8 X
2
= 30, 00, 000
3. Related to Returns:
0.09 X
1
+ 0.15 X
2
= (0.12 X 5, 00, 000)

⸫
0.09 X
1 + 0.15 X
2 = 60, 000
4. Non-negativity
X
1
, X
2
≥ 0

31. Amity School of Engineering & Technology
31
Example 6: MEDIA SELECTION
An advertising agency is planning to launch an ad
campaign. Media under consideration are T.V.,
Radio & Newspaper. Each medium has different
reach potential and different cost. Minimum 10, 000,
000 households are to be reached through T.V.
Expenditure on newspapers should not be more
than Rs. 10, 00, 000. Total advertising budget is Rs.
20 million. Following data is available:

32. Amity School of Engineering & Technology
32
Medium
Cost per Unit
(Rs.)
Reach per unit
(No. of households)
Television2, 00, 000 20, 00, 000
Radio 80,000 10,00,000
Newspaper 40,000 2,00,000

33. Amity School of Engineering & Technology
33
Solution:
Let decision Variables are
x
1 = Number of units of T.V. ads,
x
2 = Number of units of Radio ads,
x
3 = Number of units of Newspaper ads.
Objective function: (Maximize reach)
Max.
Z = 20, 00, 000 x
1
+ 10, 00, 000 x
2
+ 2, 00, 000 x
3

34. Amity School of Engineering & Technology
34
Subject to constraints:
For T.V.
20, 00, 000 x
1 ≥ 10, 000, 000
For Newspaper
40, 000 x
3 ≤ 10, 00, 000
For Ad. budget
2, 00, 000 x
1 + 80, 000 x
2 + 40, 000 x
3 ≤ 20, 000,
000
x
1, x
2, x
3 ≥ 0

35. Amity School of Engineering & Technology
35
Max.
Z = 20, 00, 000 x
1 + 10, 00, 000 x
2 + 2, 00, 000 x
3
Subject to constraints:
For T.V. x
1 ≥ 5
For Newspaper x
3 ≤ 25
For Ad. budget
5x
1
+ 2x
2
+ x
3
≤ 500
x
1
, x
2
, x
3
≥ 0

36. Amity School of Engineering & Technology
36
Example 7: Diet Problem
Vitamins B
1 and B
2 are found in two foods F
1 and
F
2. 1 unit of F
1 contains 3 units of B
1 and 5 units of
B
2. 1 unit of F
2 contains 5 units of B
1 and 7 units of
B
2
respectively.
Minimum daily prescribed consumption of B
1
& B
2
is
30 and 40 units respectively. Cost per unit of F
1 &
F
2
is Rs. 100 & Rs. 150 respectively. Formulate as
LPP.

37. Amity School of Engineering & Technology
37
Let decision variables are:
x
1 = No. of units of F
1 per day.
x
2 = No. of units of F
2 per day.

38. Amity School of Engineering & Technology
38
Objective function:
Min. Z = 100 x
1
+ 150 x
2

Subject to constraints:
3 x
1
+ 5 x
2
≥ 30 (for B
1
)
5 x
1
+ 7 x
2
≥ 40 (for B
2
)
x
1, x
2 ≥ 0