MANAGEMENT SCIENCE
(LESSON 2)
ENGR. ELMA V. LUZANO
LESSON 2 –LINEAR PROGRAMMING
LEARNING OBJECTIVES:
At the end of the lesson, the students are expected
to:
▪ Formulate the objective function and the explicit
constraints of the problem,
▪ Determine the feasible solution area utilizing the
graphical method of solving linear programming
problems and
▪ Formulate the decisions of linear programming
problem if an optimal solution is reached .
LINEAR PROGRAMMING
- Is used extensively used technique to make decisions
that will maximize or minimize quantity known as the
OBJECTIVE FUNCTION.
- Linear equation made up of decision variables
- The objective of graphical method is to choose values of
the two decision variables x and y that will maximize the
profit or minimize the cost of operation or production of
the company as the case may be depending on the prob.
- Decision variables are subject to various
explicit constraints that impose limits on the
values of the decision variables and often
represent the availability of resources,
FORMULATION OF LINEAR PROGRAM
1. Identify the decision variables.
2. Formulate the objective function and constraints in
logical order.
3. Let the problem guide you in formulating a linear
program
Example:
a. If the statement is “A manager wants to maximize
profits” this would lead to maximize profits
b. If the statement is “A department has 500 kg of raw
materials available to prepare its products” this would
lead to : Raw material ≤ 500 kg
c. If the statement is “A supervisor would like to know
how much each of two products to produce” this would
lead to:
𝒙𝟏 = 𝑸𝒖𝒂𝒏𝒕𝒊𝒕𝒚 𝒐𝒇 𝒕𝒉𝒆 𝒇𝒊𝒓𝒔𝒕 𝒑𝒓𝒐𝒅𝒖𝒄𝒕
𝒙𝟐 = 𝑸𝒖𝒂𝒏𝒕𝒊𝒕𝒚 𝒐𝒇 𝒕𝒉𝒆 𝒔𝒆𝒄𝒐𝒏𝒅 𝒑𝒓𝒐𝒅𝒖𝒄𝒕
STEPS IN SOLVING LINEAR PROGRAMMING
(Graphical Method)
1. Use variables to represent the unknown in the problem
and tabulate.
2. Set up the problem in terms of a series of mathematical
constraints and objective function.
3. Convert the inequality explicit constraints to equation.
4. Graph each of the constraints equation and solve for
the intersection if necessary.
5. Determine the feasible solution region that is, the
region containing all points that satisfy the explicit
constraints simultaneously.
6. Find the vertices of the feasible solution region and
substitute it to the objective function.
7. Choose the vertex with the highest profit in a
maximization problem or lowest cost in a minimization
problem and write the decision.
EXAMPLE: A firm manufactures 2 products, A and B.
Each product is processed by 2 machines, M1 and M2.
Each unit of type A requires 1 hr of processing by M1,
and 2 hrs in M2 and each unit of type B requires 3 hrs. of
processing by M1, and 1 hr on M2. The profit on product
A is P20 per unit and on B is P30 per units. If M1 is
available for 200 hrs each month and M2 for 300 hrs for
300 hrs, how many units of each type can be
manufactured in one month in order to maximize the
profit?
Let x – be the product A
y – be the product B
Step 1:
PRODUCT MACHINE 1 MACHINE 2 PROFIT
X → 1x → 2x 20x
y → 3y → 1y 30y
Availability 200 hours 300 hours
Step 2:
Maximize: P = 20x + 30y --- Objective Function
Subject to: 𝑥 + 3𝑦 ≤ 200 hrs – time in M1– Explicit Constraint
2𝑥 + 𝑦 ≤ 300 hrs – time in M2– Explicit Constraint
𝑥, 𝑦, ≥ 0 - Implicit Constraints
Step 3:
x + 3y = 200
Let x = 0, y = 66.67 ; let y = 0, x = 200
2x + y = 300
Let x = 0, y = 300 ; let y = 0, x = 150
Step 4 and 5 : Graph and determine Feasible Region
Step 6:
Vertices : (0, 66.67), (150, 0), and (140, 20)
Maximize: P20x + P30y
20(0) + 30(66.67) = P2,000.10
20(150) + 30(0) = P3,000.00
20(140) + 30(20) = P3,400.00
PROBLEM:
Solution: Let x = no. of minutes for mixing, bottling, and
packing the product for one case of
men’s shampoo
y = no. of minutes for mixing, bottling, and
packing the product for one case of
women’s shampoo
Maximize: P = 60x + 80y --- Objective Function
Constraints:
Subject to: 5𝑥 + 10𝑦 ≤ 100
7𝑥 + 7𝑦 ≤ 84
9𝑥 + 5𝑦 ≤ 90
𝑥, 𝑦, ≥ 0
For : 5𝑥 + 10𝑦 = 100, the intercepts are (0, 10) & (20, 0)
7𝑥 + 7𝑦 = 84 , the intercepts are (0, 12) & (12, 0)
9𝑥 + 5𝑦 = 90 , the intercepts are (0, 18) & (10, 0)
GRAPH:
Finding the Optimum Solution:
V2 (0, 10) 60(0) + 80(10) = 800
V3 (4, 8) 60(4) + 80(8) = 880
V4 (15/2, 9/2) 60(7.5) + 80(4.5) = 810
V5 (10, 0) 60(10) + 80(0) = 660
Decision Making:
Pantene Shampoo should produce 4 cases of men’s shampoo and 8 cases
of women’s shampoo per day to get a maximum profit of P880 per day.
MINIMIZATION:
Solution:
Let x = gallons of Liberty milk to be purchased per day
y = gallons of Alaska milk to be purchased per day
Objective Function: Minimize: C = 5x + 6y
Subject to:(constraints)
𝟓𝒙 + 𝟏𝟎𝒚 ≥ 𝟏𝟎𝟎
𝟕𝒙 + 𝟖𝒚 ≥ 𝟏𝟏𝟐
9𝒙 + 𝟒𝒚 ≥ 𝟕𝟐
𝒙 ,𝒚 ≥ 𝟎
For : 𝟓𝒙 + 𝟏𝟎𝒚 = 𝟏𝟎𝟎, the intercepts are (0, 10) & (20, 0)
7𝒙 + 𝟖𝒚 = 𝟏𝟏𝟐, the intercepts are (0, 14) & (16, 0)
9𝒙 + 𝟒𝒚 = 𝟕𝟐, the intercepts are (0, 18) & (8, 0)
GRAPH:
Corner B is the intersection of the lines:
𝟕𝒙 + 𝟖𝒚 = 𝟏𝟏𝟐 and 9𝒙 + 𝟒𝒚 = 𝟕𝟐
Solving for x and y coordinates:
𝟑𝟐 𝟏𝟒𝟏
x= 𝒂𝒏𝒅 𝒚=
𝟏𝟏 𝟏𝟏
Corner C is the intersection of the lines:
𝟕𝒙 + 𝟖𝒚 = 𝟏𝟏𝟐 and 𝟓𝒙 + 𝟏𝟎𝒚 = 𝟏𝟎𝟎
Solving for x and y coordinates:
𝟏𝟏𝟗 𝟑𝟏
x= 𝒂𝒏𝒅 𝒚=
𝟑 𝟔
Finding the Optimum Solution:
A (20, 0) 5(20) + 6(0) = 100
𝟑𝟐 𝟏𝟒𝟏 𝟑𝟐 𝟏𝟒𝟏
B( , ) 5( ) + 6( ) = 91.45
𝟏𝟏 𝟏𝟏 𝟏𝟏 𝟏𝟏
𝟏𝟏𝟗 𝟑𝟏 𝟏𝟏𝟗 𝟑𝟏
C ( , ) 5( ) + 6( ) = 229.33
𝟑 𝟔 𝟑 𝟔
D (0, 18) 5(0) + 6(0) = 108
Decision Making:
𝟑𝟐
The purchasing manger should buy or 2.91 gallons of Liberty milk and
𝟏𝟏
𝟏𝟒𝟏
or 12.82 gallons of Alaska milk per day to achieve a MINIMUM total
𝟏𝟏
cost of $91.45.
Linear Programming (LP) Optimization with Excel
Solver - YouTube
SEATWORK1.1:
MINIMIZE:
P = 20x + 40y
Subject to: x + y ≥ 𝟓𝟎
x≤ 30
y≤ 40
x,y ≥ 0
SEATWORK 1.2
ASSIGNMENT:
A. Graph the solution set:
1.
2.
B.
1.
2.
