Formulation Lpp

1. LINEAR PROGRAMMING
PROBLEM

2. Linear : form meant a mathematical expression of the type
aa
11xx
1 1 + a+ a
22xx
2 2 + ……….+ a+ ……….+ a
nnxx
nn
where awhere a
11, a, a
22, ….., a, ….., a
nn are constants, are constants,
and xand x
11, x, x
22, ………, x, ………, x
nn are variables. are variables.
Programming : refers to the process of determining
a particular program or plan of action.
Linear Programming Problem(LPP): Technique for
optimizing(maximizing/minimizing) a linear function
of variables called the ‘OBJECTIVE FUNCTION’
subject to a set of linear equations and/or inequalities
called the ‘CONSTRAINTS’ or ‘RESTRICTIONS’.

3. FORMULATION OF
LP PROBLEMS

4. LP Model Formulation
lObjective function
l
a linear relationship reflecting the objective of
an operation
l
most frequent objective is to maximize profit or
to minimize cost.
lDecision variables
l
an unknown quantity representing a decision
that needs to be made. It is the quantity the
model needs to determine
lConstraint
l
a linear relationship representing a restriction on
decision making

5. Steps in Formulating the
LP Problems
1.1. Define the objective. (min or max)Define the objective. (min or max)
2.2. Define the decision variables. Define the decision variables.
3.3. Write the mathematical function for the objective. Write the mathematical function for the objective.
4.4. Write the constraints. Write the constraints.
5.5. Constraints can be in Constraints can be in <<, =, or , =, or >> form. form.

6. Example
Two productsTwo products: Chairs and Tables: Chairs and Tables
DecisionDecision:: How many of each to make this month? How many of each to make this month?
ObjectiveObjective: : Maximize profitMaximize profit

7. Data
10001 hr2 hrsPainting
24004 hrs3 hrscarpentry
$5$7Profit
Contribution
Hours
Available
Chairs
(per chair)
Tables
(per table)
Other Limitations:
• Make no more than 450 chairs
• Make at least 100 tables

8. Decision VariablesDecision Variables::
TT = Num. of tables to make = Num. of tables to make
CC = Num. of chairs to make = Num. of chairs to make
Objective FunctionObjective Function: Maximize Profit: Maximize Profit
MaximizeMaximize $7 $7 TT + $5 + $5 CC
Solution

9. Constraints
l
Have 2400 hours of carpentry time availableHave 2400 hours of carpentry time available
3 3 TT + 4 + 4 CC << 2400 2400 (hours)(hours)
l
Have 1000 hours of painting time availableHave 1000 hours of painting time available
2 2 TT + 1 + 1 CC << 1000 1000 (hours)(hours)

10. More ConstraintsMore Constraints::
l
Make no more than 450 chairsMake no more than 450 chairs
CC << 450 450
l
Make at least 100 tablesMake at least 100 tables
TT >> 100 100
Non negativityNon negativity::
Cannot make a negative number of chairs or tablesCannot make a negative number of chairs or tables
TT >> 0 0
CC >> 0 0

11. Model
MaxMax 7 7TT + 5 + 5CC
Subject to the constraintsSubject to the constraints::
33TT + 4 + 4CC << 2400 2400
22TT + 1 + 1CC << 1000 1000
C C << 450 450
T T >> 100 100
TT,, C C >> 0 0

12. General Formulation of LPP
Max/min Max/min z = cz = c
11xx
11 + c + c
22xx
22 + ... + c + ... + c
nnxx
nn
subject to:subject to:
aa
1111xx
11 + a + a
1212xx
22 + ... + a + ... + a
1n1nxx
nn (≤, =, ≥) b (≤, =, ≥) b
11
aa
2121xx
11 + a + a
2222xx
22 + ... + a + ... + a
2n2nxx
nn (≤, =, ≥) b (≤, =, ≥) b
22
::
aa
m1m1xx
11 + a + a
m2m2xx
22 + ... + a + ... + a
mnmnxx
nn (≤, =, ≥) b (≤, =, ≥) b
m m
xx
1 1 ≥ 0, x≥ 0, x
22 ≥ 0,…….x ≥ 0,…….x
jj ≥ 0,……., x ≥ 0,……., x
nn ≥ 0. ≥ 0.
xx
jj = decision variables = decision variables
bb
ii = constraint levels = constraint levels
cc
jj = objective function coefficients= objective function coefficients
aa
ijij = constraint coefficients = constraint coefficients

13. Example
Cycle Trends is introducing two new lightweight bicycle
frames, the Deluxe and the Professional, to be made from
aluminum and steel alloys. The anticipated unit profits
are $10 for the Deluxe and $15 for the Professional.
The number of pounds of each alloy needed per
frame is summarized on the next slide. A supplier
delivers 100 pounds of the aluminum alloy and 80 pounds
of the steel alloy weekly. How many Deluxe and
Professional frames should Cycle Trends produce each
week?

14. Example
Pounds of each alloy needed per frame
Aluminum AlloyAluminum Alloy Steel AlloySteel Alloy
DeluxeDeluxe 2 3 2 3
Professional Professional 4 4 22

15. Solution
Define the objective
Maximize total weekly profit
Define the decision variables
x
1
= number of Deluxe frames produced weekly
x
2
= number of Professional frames produced
weekly

16. Solution
Max Z = 10x
1
+ 15x
2
Subject To
2x
1
+ 4x
2
< 100
3x
1
+ 2x
2
< 80
x
1
, x
2 >> 0

17. Example
A firm manufactures 3 products A, B and C. The profits are Rs.3, Rs.2, A firm manufactures 3 products A, B and C. The profits are Rs.3, Rs.2,
and Rs.4 respectively. The firm has 2 machines and below is the and Rs.4 respectively. The firm has 2 machines and below is the
required processing time in minutes for each machine on each product.required processing time in minutes for each machine on each product.
422H
534GMachines
CBA
Product
Machine G and H have 2000 and 2500 machine-minutes
respectively. The firm must manufacture 100 A’s, 200 B’s and 50
C’s, but not more than 150 A’s. Set up an LP problem to
maximize profit.

18. Solution
Define the objective
Maximize profit
Define the decision variables
x
1
= number of products of type A
x
2
= number of products of type B
x
3
= number of products of type C

19. Solution
Max Z = 3xMax Z = 3x
1 1 + 2x+ 2x
22 + 4x + 4x
33
Subject ToSubject To
4x4x
11 + 3x + 3x
22 + 5x + 5x
33 ≤ 2000 ≤ 2000
2x2x
11 + 2x + 2x
22 + 4x + 4x
33 ≤ 2500 ≤ 2500
100 ≤100 ≤ xx
11 ≤ 150 ≤ 150
xx
2 2 ≥≥ 200
x
3 ≥≥ 50
xx
11, x, x
22, x, x
33 ≥ ≥ 0

20. Example
The Sureset Concrete Company produces concrete.
Two ingredients in concrete are sand (costs $6 per
ton) and gravel (costs $8 per ton). Sand and gravel
together must make up exactly 75% of the weight of
the concrete. Also, no more than 40% of the
concrete can be sand and at least 30% of the
concrete be gravel. Each day 2000 tons of concrete
are produced. To minimize costs, how many tons of
gravel and sand should be purchased each day?

21. Solution
Define the objective
Minimize daily costs
Define the decision variables
x
1
= tons of sand purchased
x
2
= tons of gravel purchased

22. Cont…
Min Z = 6x
1
+ 8x
2
Subject To
x
1
+ x
2
= 1500
x
1
< 800
x
2
>> 600 600
x
1
, x
2 >> 0