LINEAR PROGRAMMING
(Graphical Method)
Terminologies
Objective function: an expression which shows the relationship
between the variables in the problem
P = ax + by (for maximization) C = ax + by (for minimization)
wherein:
a and b are coefficients
Example 1:
A souvenir store wishes to produce two models of souvenirs: model
A and model B. Every model-A souvenir will result to P14 profit, and
every model-B souvenir will result to P23 profit. To manufacture a
model-A souvenir requires 3 minutes on stage 1 and 6 minutes on
stage 2. There are 270 minutes on stage 1 and 360 minutes on stage 2
for processing order. How many souvenirs of each model should the
store make in order to maximize profit?
Objective function:
P = ax + by (for maximization) C = ax + by (for minimization)
Example 1:
A souvenir store wishes to produce two models of souvenirs: model
A and model B. Every model-A souvenir will result to P14 profit, and
every model-B souvenir will result to P23 profit. To manufacture a
model-A souvenir requires 3 minutes on stage 1 and 6 minutes on
stage 2. There are 270 minutes on stage 1 and 360 minutes on stage 2
for processing order. How many souvenirs of each model should the
store make in order to maximize profit?
Objective function:
P = ax + by (for maximization) C = ax + by (for minimization)
Example 1:
A souvenir store wishes to produce two models of souvenirs: model
A and model B. Every model-A souvenir will result to P14 profit, and
every model-B souvenir will result to P23 profit. To manufacture a
model-A souvenir requires 3 minutes on stage 1 and 6 minutes on
stage 2. There are 270 minutes on stage 1 and 360 minutes on stage 2
for processing order. How many souvenirs of each model should the
store make in order to maximize profit?
Objective function:
P = ax + by (for maximization)
Example 1:
A souvenir store wishes to produce two models of souvenirs: model
A and model B. Every model-A souvenir will result to P14 profit, and
every model-B souvenir will result to P23 profit. To manufacture a
model-A souvenir requires 3 minutes on stage 1 and 6 minutes on
stage 2. There are 270 minutes on stage 1 and 360 minutes on stage 2
for processing order. How many souvenirs of each model should the
store make in order to maximize profit?
Objective function:
P = 14x + 23y (for maximization)
Terminologies
Structural Constraint: shows the limit on the availability of
resources; also referred to as explicit
constraint
Terminologies
Structural Constraint: shows the limit on the availability of
resources; also referred to as explicit
constraint
STAGE Model-A Model-B Available
(x) (y) Minutes
1 3 minutes 5 minutes 270 minutes
2 6 minutes 4 minutes 360 minutes
Profit P14 P23
Structural Constraints:
Model-A Model-B Available
STAGE
(x) (y) Minutes
1 3 minutes 5 minutes 270 minutes
2 6 minutes 4 minutes 360 minutes
Profit P14 P23
3x + 5y ≤ 270
6x + 4y ≤ 360
Structural Constraints:
Model-A Model-B Available
STAGE
(x) (y) Minutes
1 3 minutes 5 minutes 270 minutes
2 6 minutes 4 minutes 360 minutes
Profit P14 P23
3x + 5y ≤ 270
6x + 4y ≤ 360
*if the problem indicates that resources must be
maximized then use the ≤ symbol otherwise, ≥
Terminologies
Non-negativity Constraint: restricts all the variables to zero
and positive solution; also
referred to as implicit constraint
Non-negativity Constraint:
STAGE Model-A Model-B Available
(x) (y) Minutes
1 3 minutes 5 minutes 270 minutes
2 6 minutes 4 minutes 360 minutes
Profit P14 P23
x ≥0, y≥0
*the assumption that the values of x and y are always
equal to 0 or a positive number
Terminologies
Optimal Value: the best possible value of the objective
function and satisfy all the constraints
Feasible Region: set of combinations of values for the
decision variables (x and y) that satisfy the
non negativity constraints and all the
constraints simultanously.
Terminologies
Extreme Point: the corner of the feasible region; it is the
location of the maximum and minimum
point of the feasible region
STEPS IN GRAPHICAL METHOD
Step 1: Represent the unknown in the problem
Model-A (x) and Model-B (y)
Step 2: Tabulate the data about the facts
Model-A Model-B Available
STAGE
(x) (y) Minutes
1 3 minutes 5 minutes 270 minutes
2 6 minutes 4 minutes 360 minutes
Profit P14 P23
Step 3: Formulate the objective function and cnstraints by restating
the information in mathematical form.
P = 14x + 23y Objective Function
3x + 5y ≤ 270
6x + 4y ≤ 360 } Structural Constraints
x ≥0, y≥0 Non-Negativity Constraint
Step 4: Plot the constraints of theproblem on a graph. Use the
intercept rule to get the coordinates.
3x + 5y ≤ 270 6x + 4y ≤ 360
3x + 5y =270 6x + 4y = 360
a
Let x=0 Let y=0 Let x=0 Let y=0
3(0) + 5y=270 3x +5(0)=270 6(0) + 4y=360 6x +4(0)=360
5y=270 3x=270 4y=360 6x=360
y=270/5 x=270/3 y=360/4 x=360/6
y=54 x=90 y=90 x=60
Step 4: Plot the constraints of theproblem on a graph. Use the
intercept rule to get the coordinates.
(0,90)
6x + 4y = 360
(0,54)
3x + 5y = 270
(60,0) (90,0)
Step 4: Plot the constraints of theproblem on a graph. Use the
intercept rule to get the coordinates.
(0,90)
(0,54)
FEASIBLE REGION
(60,0) (90,0)
Step 5: Trace the extreme points and solve for the unknown
coordinates
(0,90)
(0,54)
Unknown coordinate
FEASIBLE REGION
(60,0) (90,0)
Step 5a: Identify the equations of the intersecting lines and apply the
Least Common Multiple (LCM) on one decision variable to
eliminate it.
2(3x + 5y = 270) 6x + 10y = 540
For example we
want to elimate 1(6x + 4y = 360) (-)6x + 4y = 360
both x's of the 6y = 180
two equations. y = 30
Step 5b: Substitute the value of y to either of the equations involved
in the intersection to obtain the value of x.
y = 30
3x + 5(30) = 270
3x + 150 = 270
3x = 270-150
3x =120
x =120/3
x = 40
(0,90)
(0,54)
(40,30)
FEASIBLE REGION
(60,0) (90,0)
Step 6: substitute the coordinates at the extreme points on the
feasible region to the objective function
Objective function: P= 14x + 23y
Extreme Points Values of the objective function
(0,54) 14(0) + 23(54) = 1,242
(40, 30) 14(40) + 23(30) = 1,250
(60, 0) 14(60) + 23(0) = 840
Step 7: Formulate the decision.
Since coordinate (40, 30) will give the highest value of P 1,250.
The decision is to create 40 model-A souvenirs and 30 model-B
souvenirs in order to maximize the profit.
Example 2:
A local boutique produced two designs of gowns A and B and has the
following materials available: 18 sq. meters of cotton, 20 sq. meters of
silk and 5 sq. meters of wool. Design A requires the following: 3 sq.
meters of cotton, 3 sq. meters of silk and 1 sq. meter of wool. Design
B requires the following: 2 sq. meters of cotton and 4 sq. meters of
silk. If Design A sells for P 1,200 and Design B sells for 1,600, how
many of each garment should the boutique produce to obtain the
maximum amount of money?
Seatwork 1:
A pharmcist produces a drug from two ingredients. Each ingredient
contains the same three antibiotics in different proportions. Each
ingredient A produced results P80 in cost; each ingredient B results
P50 in cost. The production of the antibiotics is dependent on the
availability of limited resources. The resource requirements for the
production are as follows.
Minimun
Antibiotic Ingredient A Ingredient B
Requirement
1 3 units 1 unit 6
2 1 unit 1 unit 4
3 2 units 6 units 12
Seatwork 1:
The company wants to determine the quantity of ingredient A and B
that must go in to drug in order to meet the antibiotics minimum
requirements at the minimum cost.
