LINEAR PROGRAMMING
MANAGEMENT SCIENCE
LINEAR PROGRAMMING
❑ is a model that consists of linear relationships
representing a firm’s decision(s), given an objective and
resource constraint
❑ is a tool of management science for solving optimization
problems.
THREE STEPS IN APPLYING THE LINEAR
PROGRAMMING TECHNIQUE.
1. Problem must be identified as being solvable by linear programming.
2. The unstructured problem must be formulated as a mathematical model
3. The model must be solved by using established mathematical techniques.
The linear programming technique derives its name
from the fact that the functional relationships in the
mathematical model are linear, and the solution
technique consists of predetermined mathematical
steps—that is, a program.
MODEL FORMULATION
includes decision variables, an objective
function, and model constraints
DECISION VARIABLES
❑ are mathematical symbols that represent levels of activity
For example, an electrical manufacturing firm desires to produce radios, toasters,
and clocks
Let
X= radios
Y= toasters
Z= clocks
The final values of x ,y and z, as determined by the firm, constitute a decision
OBJECTIVE FUNCTION
❑ is a linear relationship that reflects the objective of an operation.
❑ always consists of either maximizing or minimizing some value
.
❑ Example: maximize the profit or minimize the cost
MODEL CONSTRAINTS
❑ is a linear relationship that represents a restriction on decision making.
❑ they represent the restrictions placed on the firm by the operating environment.
❑ The restrictions can be in the form of limited resources or restrictive guidelines.
❑ For example, only 40 hours of labor may be available to produce radios during
production. The actual numeric values in the objective function and the
constraints, such as the 40 hours of available labor, are parameters
PARAMETERS
❑ numerical values that are included in the objective functions and
constraints.
MAXIMIZATION MODEL EXAMPLE
Midoriya Company wants to maximize the profit of his business. The two primary resources
used by the company are special pottery clay and skilled labor. Given these limited resources,
the company desires to know how many bowls and mugs to produce each day
DECISION VARIABLES
◼ The quantities to be produced can be represented symbolically as
X = number of bowls to produce
Y = number of mugs to produce
THE OBJECTIVE FUNCTION
◼ The company’s profit is the sum of the individual profits gained from each bowl and
mug.
Max Z = P40x + P50y
Where
Z = total profit for day
P40x = profit from bowls
P50y = profit from mugs
MODEL CONSTRAINTS
◼ For each bowl produced, 1 hour of labor is required. Similarly, each mug
requires 2 hours of labor.
1x + 2y
However, the amount of labor is limited to 40 hours per day; thus, the complete
labor constraint is
1x + 2y ≤ 40 hr
▪ the amount of clay used daily for the production of bowls is 4 pounds; and
because each mug requires 3 pounds of clay,
4x + 3y ≤ 120lb
NONNEGATIVITY CONSTRAINTS
◼ restrict the decision variables to zero or positive values
x ≥ 0, y ≥ 0
THE COMPLETE LINEAR PROGRAMMING MODEL FOR THIS
PROBLEM CAN NOW BE SUMMARIZED AS FOLLOWS:
Max Z = P40x + 50y
Subject to
1x + 2y ≤ 40 hr
4x + 3y ≤ 120lb
x,y≥0
Max Z = P40x + 50y
Subject to
1x + 2y ≤ 40 hr
4x + 3y ≤ 120lb
x,y≥0
Solution:
Eliminate the x and solve for y Solve for y
4[1x + 2y ≤ 40] 4 x + 2y ≤ 40
4x + 8y ≤ 160 x + 2(8) ≤ 40
- (4x + 3y ≤ 120) x + 16 ≤ 40
5y ≤ 40 x ≤ 40-16
y≤8 x ≤ 24
USE THE VALUE OF X AND Y TO THE OBJECTIVE FUNCTION
Max Z = P40x + 50y
Z = P40 (24) + 50(8)
Z = 960 + 400
Z = P 1,360
SEATWORK
Jabing Co. wants to determine the number of products to be produced in order to
maximize the profits. Currently, they are producing toy A and toy B. Each toy A yields a
profit of $2 while toy B yields $3. Jabing estimates that no more than 2000 toys will be
sold for the month of September and does not plan to invest more than $20,000 in the
inventory of these toys. He pays $8 and $14 for each of the unit toy.
