Linear Programming
LINEAR PROGRAMMING: Graphical Method
LEARNING OBJECTIVES_
After completing this lesson, you should be able to:
• Explain what Linear Programming is.
• Determine the restrictions on Linear Programming: Graphical Method.
• Formulate Linear Programming models.
• Define and explain terms such as optimal solution, feasible solution, extreme point and redundant
constraint.
• Recognize problems that have multiple solutions, infeasibility, and unbounded.
• Solve Linear Programming problems graphically and interpret the solutions.
• Describe different problem types that lead to a solution using Linear Programming models.
BASIC CONCEPTS
LINEAR PROGRAMMING is a method of dealing with decisions problems that can be
expressed as controlled or constrained linear problems. The primary objectives of all linear
programming models are certainty of the parameters and linearity of the objective function and all
constraints. Linear programming is a mathematical technique for finding the best uses of an
organization’s resources.
Linear programming was developed by George Dantzig in the 1940s, as a result of Air Force
research project concerned with computing the most efficient and economical way to distribute
men, weapons and supply from different fronts during World War II.
The word “programming” means producing a plan or procedure that determines the solution
to a problem. The GRAPHICAL SOLUTION METHOD is a two-dimensional geometric analysis of
Linear Programming problems with two decision variables.
RESTRICTIONS
Linear programming graphical solution is limited in a two-dimensional set of axes; meaning if
there are more than two variables, we cannot graph the constraints on a two-dimensional set of axes.
But with an appropriate tolls or graphing software applications, the method can be used in three
variables corresponds to planes in a coordinate space.
SOLVING
A. Linear Programming Problems
A linear programming problem in two unknowns X and Y is one in which we are to
determine the maximum and minimum value of a linear expression.
𝑃 = 𝑎1 𝑥 + 𝑏1 𝑦 (for maximization) 𝐶 = 𝑎1 𝑥 + 𝑏1 𝑦 (for minimization)
are called the OBJECTIVE FUNCTION, subject to a number of linear constraints of the form
𝑎2 𝑥 + 𝑏2 𝑦 ≤ 𝑐 or 𝑎2 𝑥 + 𝑏2 𝑦 ≥ 𝑐 or 𝑎2 𝑥 + 𝑏2 𝑦 = 𝑐
1
Linear Programming
An objective function is an expression, which shows the relationship between the
variables in the problem and the firm’s goals. There are two types of constraints: structural
and non-negativity. The structural constraint is a limit on the availability of resources; it is
also referred as explicit constraint. Non-negativity constraint is the constraint that
restricts all the variables to zero and positive solutions; it is also referred as implicit
constraint.
EXAMPLE Linear Programming Model (x and y as decision variables)
Maximize: 𝑃 = 1,200𝑥 + 1,600𝑦 Objective Function
Subject to: 3𝑥 + 2𝑦 ≤ 18 Structural Constraint 1
2𝑥 + 4𝑦 ≤ 20 Structural Constraint 2
𝑥≤5 Structural Constraint 3
𝑥 ≥ 0, 𝑦 ≥ 0 Non-negativity Constraints
The highest (for maximization problem) or lowest value (for minimization problem) of the
objective function is referred to as the OPTIMAL VALUE. The optimal solution is a combination of
decision variable amounts that yields the best possible value of the objective function and satisfies
all the constraints. There may be multiple combinations of decision variables that yield the same best
value of the objective function.
The feasible region is the set of combination values for the decision variables that satisfy
the non-negativity conditions and all the constraints simultaneously; that is, the allowable decisions.
Extreme point is the corner of the feasible region; it is the location of the maximum and minimum
point of the feasible region.
B. The Extreme Point Theorem
The linear objective function will have its optimal solutions at the extreme points
(corner points) of the feasible region whenever the feasible region is bounded. If the feasible
region is unbounded, there is no optimal solution. In cases wherein there is an optimal
solution even though the feasible region is unbounded, it lies at the extreme (or corner) of
the feasible region.
C. Fundamental Theorem of Linear Programming Problem
There are two things we need to consider in solving linear programming problem such
as:
• If a linear programming problem has optimal solution, there is always at least one
extreme point (corner point) solution of the feasible region.
• A linear programming problem with bounded, nonempty feasible regions always
contain optimal solutions.
D. Solving Linear Programming: Maximization Problem
This section will present the solution in maximizing a Linear Programming model
using graphical method. It will be easier to establish the solution of an LP model if we follow
the procedure presented.
2
Linear Programming
Steps in Linear Programming Graphical Method
1. Graph the linear inequalities (structural constraints) and determine the feasible
region.
2. Determine the coordinates of the extreme points (corner points).
3. Substitute the coordinates of the extreme points to the objective function and identify
the highest (for maximization problem) or lowest (for minimization problem) result.
4. The highest or lowest result obtained in Step 3 serves as the optimal solution to the
LP problem.
A local boutique produced two designs of gowns A and B, and has the following
EXAMPLE materials available: 18 yards of cotton, 20 yards of silk and 5 yards of wool. Design
A requires the following: 3 yards of cotton, 2 yards of silk and 1 yard of wool. Design B requires the
following: 2 yards of cotton and 4 yards of silk. If Design A sells for P1,200 and Design B for P1,600,
how many of each garment should the boutique produce to obtain the maximum amount of money?
Solution:
In order to solve a linear programming using graphical method, it is necessary to follow the
following steps:
STEP i: Represent the unknown in the problem.
Let 𝑥 be the number of Design A gowns; and
𝑦 be the number of Design B gowns.
STEP ii: Tabulate the data about the facts (if necessary).
Materials Design A (𝒙) Design B (𝒚) Available
Cotton 3 2 18
Silk 2 4 20
Wool 1 0 5
Revenue/gown P1,200 P1,600
STEP iii: Formulate the objective function and constraints by restating the information in an LP
model.
OBJECTIVE FUNCTION:
Maximize: P = 1,200x + 1,600y
Subject to: 3x + 2y ≤ 18
2x + 4y ≤ 20
x ≤ 5
x ≥ 0,y ≥ 0
STEP iv: Graph each of the constraints, identify the feasible region and determine the coordinates
of the corner/extreme points.
3
Linear Programming
STEP v: Substitute the coordinates of the extreme points (corner points) on the feasible region
to the objective function.
P = 1,200x + 1,600y
Extreme/ Corner Points Values of the Objective Function
(0, 5) 1,200(0) + 1,600(5) = 0 + 8,000 = 𝟖, 𝟎𝟎𝟎
(5, 0) 1,200(5) + 1,600(0) = 6,000 + 0 = 𝟔, 𝟎𝟎𝟎
(4, 3) 1,200(4) + 1,600(3) = 4,800 + 4,800 = 𝟗, 𝟔𝟎𝟎
(5, 1.5) 1,200(5) + 1,600(1.5) = 6,000 + 2,400 = 𝟖, 𝟒𝟎𝟎
(0, 0) 1200(0) + 1600(0) = 0
STEP vi: Formulate the decision.
Decision: x = 4 Design A gowns y = 3 Design B gowns
Max P = P 9,600
Since the coordinate (4, 3) will give the highest value of P9,600, the decision is to
create 4 Design A gowns and 3 Design B gowns in order to maximize the sales.
E. Solving Linear Programming: MINIMIZATION PROBLEM
This section presents the solution in minimizing an LP graphically. Practically, we will
apply the same procedure in establishing the solution of an LP with maximization problem;
the only difference is we will select the lowest linear combination in the objective function in
contrast with the maximization problem. Let us consider the example below.
A pharmacist produces a drug from two ingredients. Each ingredient contains the
EXAMPLE 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:
Resource Requirement Minimum
Antibiotic
INGREDIENT A INGREDIENT B Requirement
Antibiotic 1 3 units 1 unit 6
Antibiotic 2 1 unit 1 unit 4
Antibiotic 3 2 units 6 units 12
The company wants to determine the quantity of ingredient A and B that must go in to the
drug in order to meet the antibiotics minimum requirements at the minimum cost.
Solution:
STEP i: Represent the unknown in the problem.
Let 𝑥 be the quantity of Ingredient A and
𝑦 be the quantity of Ingredient B.
4
Linear Programming
STEP ii: Tabulate the data about the facts (if necessary).
Resource Requirement Minimum
Materials
INGREDIENT A (𝒙) INGREDIENT B (𝒚) Requirement
Antibiotic 1 3 units 1 unit 6
Antibiotic 2 1 unit 1 unit 4
Antibiotic 3 2 units 6 units 12
COST P80 P50
STEP iii: Formulate the objective function and constraints by restating the information in an LP
model.
OBJECTIVE FUNCTION:
Minimize: C = 80x + 50y
Subject to: 3x + y ≥ 6
x + y ≥ 4
2x + 6y ≥ 12
x ≥ 0,y ≥ 0
STEP iv: Graph each of the constraints, identify the feasible region and determine the coordinates
of the corner/extreme points.
STEP v: Substitute the coordinates at the extreme points of the feasible region in the objective
function.
C = 80x + 60y
Corner/ Extreme Points Values of the Objective Function
(0, 6) 80(0) + 50(6) = 0 + 300 = 𝟑𝟎𝟎
(6, 0) 80(6) + 50(0) = 400 + 0 = 𝟒𝟎𝟎
(1, 3) 80(1) + 50(3) = 80 + 150 = 𝟐𝟑𝟎
(3, 1) 80(3) + 50(1) = 240 + 50 = 𝟐𝟗𝟎
STEP vi: Formulate the decision. Since the coordinate (1, 3) will give the lowest value of P230,
the decision is to mix 1 unit of Ingredient A and 3 units of Ingredient B in order to
minimize the cost.
Decision: x = 1 unit Ingredient A y = 3 units Ingredient B
C = P 230
5
Linear Programming
Exercises: Establish and solve the linear programming model of the following:
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 onstage 1 and 6 minutes on stage 2.
A mode B souvenir requires 5 minutes on stage 1 and 4 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?
2. A table manufacturer produces tables in two types, regular and deluxe. It costs P300 to make
each regular table, which sells for P550. It costs P480 to make each deluxe table and each
sells for P750. The daily production capacity is 125 tables and the daily cost cannot exceed
P60,000. How many tables of each type should be made per day to maximize profit?
3. An appliance repair shop has 5 DVD players, 12 LCD TV sets and 18 air conditioning units
to be repaired. The store employs two part-time repairmen. Repairman A can repair 3 DVD
players, 1 LCD TV set and 4 air conditioning units in a week, while Repairman B can repair
1 DVD player, 3 LCD TV sets and 6 air conditioning units in a week. Repairman A is paid
P5000 a week and Repairman B is paid P4200 a week. To minimize cost, how many weeks
should each of the two repairmen be employed?
4. Sofia needs at least 50 units of fat, 48 units of protein and 60 units of carbohydrates each
month. From each kilogram of Food A, she receives 5 units of fat, 2 of protein and 4 of
carbohydrates. Food B contains 2 units of fat, 3 of protein and 3 of carbohydrates per
kilogram. If Food A costs P110 and Food B costs P90 per kilogram, how many kilograms of
each food should Sofia buy each month to keep costs at a minimum?