Formulation of LPP
OR by Soumitra Chakraborty
Steps in Developing a Linear
Programming (LP) Model
1) Formulation
2) Solution
3) Interpretation and Sensitivity Analysis
Properties of LP Models
1) Seek to minimize or maximize
2) Include “constraints” or limitations
3) There must be alternatives available
4) All equations are linear
Diet problem
• Vitamin-A and Vitamin B are found in food-1 and food-2.
• One unit of food-1 contains 5 unit of Vitamin A and 2 units
of Vitamin B.
• One unit of food-2 contains 6 unit of Vitamin A and 3 units
of Vitamin B.
• The minimum daily requirement of a person is 60 units of
Vitamin A and 80 units of Vitamin B.
• The cost per unit of food-1 is Rs. 5/- and one unit of food-2
is Rs. 6/-.
• Find the minimum cost of the mixture(food-1 & food-2)
which meets the daily minimum requirements of vitamns.
OR by Soumitra Chakraborty
Decision Variables:
X1 = Units of food-1
X2 = Units of food-2
Objective Function: Maximize Profit
Minimize Z=5X1 + 6X2
Constraints:
• Vitamin A constraint
5X1 + 6 X2 < 60 (units)
• Vitamin B Constraint
2X1 + 3X2 < 80 (units)
Nonnegativity:
Cannot make a negative number of chairs or tables
X1 > 0
X1 > 0
Model Summary
Min Z=5 X1 + 6 X2 (cost)
Subject to the constraints:
5 X1 + 6 X2 < 60 (Vitamin A constraint)
3 X1 + 2 X2 < 12 (Vitamin B constraint)
X1 , X2 > 0 (non negativity constraint)
PROBLEM DEFINITION:
BEAVER CREEK MAXIMIZATION PROBLEM
• Product mix problem - Beaver Creek Pottery Company
• How many bowls and mugs should be produced to
maximize profits given labor and materials constraints?
• Product resource requirements and unit profit:
PROBLEM DEFINITION:
BEAVER CREEK MAXIMIZATION
PROBLEM
• Product mix problem - Beaver Creek Pottery Company
• How many bowls and mugs should be produced to
maximize profits given labor and materials constraints?
• Product resource requirements and unit profit:
PROBLEM DEFINITION:
BEAVER CREEK MAXIMIZATION PROBLEM
Resource 40 hrs of labor per day
Availability: 120 lbs of clay
Decision Variables x1 = number of bowls to produce per day
x2 = number of mugs to produce per day
Objective Maximize Z = $40x1 + $50x2
Function: Where Z = profit per day
Resource 1x1 + 2x2 40 hours of labor
Constraints: 4x1 + 3x2 120 pounds of clay
Non-Negativity x1 0; x2 0
Constraints:
PROBLEM DEFINITION:
BEAVER CREEK MAXIMIZATION PROBLEM
Complete Linear Programming Model:
Maximize Z = $40x1 + $50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
PROBLEM DEFINITION:
BEAVER CREEK MAXIMIZATION PROBLEM
A feasible solution does not violate any of the
constraints:
Example x1 = 5 bowls
x2 = 10 mugs
Z = $40x1 + $50x2 = $700
Labor constraint check:
1(5) + 2(10) = 25 < 40 hours, within constraint
Clay constraint check:
4(5) + 3(10) = 50 < 120 pounds, within constraint
INFEASIBLE SOLUTIONS:
BEAVER CREEK EXAMPLE
An infeasible solution violates at least one of the
constraints:
Example x1 = 10 bowls
x2 = 20 mugs
Z = $1400
Labor constraint check:
1(10) + 2(20) = 50 > 40 hours, violates the constraint
The set of all points that satisfy all the constraints
of the model is called
a
FEASIBLE REGION
Production Problem
• A manufacturing company is engaged in producing three
types of products: A,B,C. The production department
produces, each day, component sufficient to make 50
units of A,25 units of B and 30 units of C. The
management confronted with the problem of optimizing
the daily production of the products in the assembly
department, where only 100 man-hours are available.
The following information is available:
Type of Product Profit per unit Assembly time per product per unit
A 12 0.8 hrs
B 20 1.7 hrs
C 45 2.5 hrs
• The daily order commitments are 20 units for A and total
of 15 units of product BOR& C. Formulate the problem.
by Soumitra Chakraborty
Production Problem
• A firm produces three products A,B & C .It uses two types
of raw materials I & II of which 5000 & 7000 units
respectively is available. The raw material requirement are
given below. A B C
I 3 4 5
II 5 3 5
• The labour time of each unit of A is twice that of B and
three times that of C. The entire labour force of the firm
can produce the equivalent of 3000 units . The minimum
demand of the product is 600,650 & 500 respectively.
• Profit per unit of A,B & C are 50,50 & 80 respectively.
• Formulate the LPP problem
OR by Soumitra Chakraborty
Production Problem
• A pharmaceutical company has 100 kgs of A,180 Kgs of B
and120 kgs of C available per month. They can use these
materials to make three products namely 5-10-5,5-5-10
and 20-5-10 where the no. in each case represents the
percentage by weight of A,B and C respectively in each of
the products.
• Cost of raw materials are
Ingredients Cost per kg(Rs.)
A 80
B 20
C 50
Inert ingredients 20
• Selling price of the products are Rs. 40.50,Rs.43 and Rs.45
per Kg. Capacity restriction for product 5-10-5 is 30 kgs.
• Formulate the problem,
OR by Soumitra Chakraborty
Decision Variables:
X1 = Units of food-1
X2 = Units of food-2
Objective Function: Maximize Profit
Minimize Z=5X1 + 6X2
Constraints:
• Vitamin A constraint
5X1 + 6 X2 < 60 (units)
• Vitamin B Constraint
2X1 + 3X2 < 80 (units)
Nonnegativity:
Cannot make a negative number of chairs or tables
X1 > 0
X1 > 0
Model Summary
Min Z=5 X1 + 6 X2 (cost)
Subject to the constraints:
5 X1 + 6 X2 < 60 (Vitamin A constraint)
3 X1 + 2 X2 < 12 (Vitamin B constraint)
X1 , X2 > 0 (non negativity constraint)
