MANAGEMENT SCIENCE
Manuel S. Enverga University Foundation
College of Business and Accountancy
Lucena City
LINEAR PROGRAMMING
RALYN E. BERMUDEZ
MANAGEMENT SCIENCE
Definition
Linear Programming
o a tool of management science for solving optimization
problems.
o Mathematical technique for finding the best uses of
organization’s resources
o The word “linear” indicates that all mathematical
relationships in a model are linear.
MANAGEMENT SCIENCE
Maximization: Summary of Steps
1. Set up the objective function and the problem constraints
2. Convert the inequalities by adding slack or artificial variables
3. Enter equalities in the simplex table
4. Calculate the Cj and Zj values for this solution
5. Determine the entering variable
MANAGEMENT SCIENCE
2.1 FORMULATION OF LINEAR
PROGRAMMING MODELS
MANAGEMENT SCIENCE
Word Problem
Toy Story Inc. manufactures 2 types of wooden toys: trucks and trains.
The price of a piece of truck is P550, of a piece of train P700. The wood
cost for the truck is P50, whereas for the train P70. The truck requires 1
hour of carpentry labor and 1 hour of finishing labor (assembling and
painting). The train requires 2 hours of carpentry labor and 1 hour of
finishing labor. Worth of carpentry labor is P30 per hour, worth of finishing
labor is P20 per hour. Each month, Toy Story has 5000 available hours of
carpentry labor and 3000 hours of finishing labor. Demand for trains is
unlimited, but at most 2000 trucks are, at an average, bought each month.
The Toy Story’s management wants to maximize monthly profit (total
revenue - total cost).
MANAGEMENT SCIENCE
Steps in Formulating Linear
Programming Models
Step 1. Define the specific decision variables
o assigning variables to the given products
o the variables should completely describe the decisions to
be made by the management.
The manager must decide how many trucks and how many trains should
be manufactured each month in order to maximize the profit. In this case
the decision variables are:
𝑥1 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑟𝑢𝑐𝑘𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑑 𝑒𝑎𝑐ℎ 𝑦𝑒𝑎𝑟
𝑥2 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑡𝑟𝑎𝑖𝑛𝑠 𝑝𝑟𝑜𝑑𝑢𝑐𝑒𝑑 𝑒𝑎𝑐ℎ 𝑦𝑒𝑎𝑟
MANAGEMENT SCIENCE
Step 2. Identify the objective function
This function represents the management’s criterion that is
to be maximized or minimized.
Maximize: Contribution to profit
Minimize: Cost
MANAGEMENT SCIENCE
In the Toy Story’s situation the management intends to maximize
total monthly profit as the difference between total monthly revenue
and total monthly cost. Both revenue and cost can be expressed as
the function of decision variables 𝑥1 and 𝑥2 .
MANAGEMENT SCIENCE
Objective Function
𝐏𝐫𝐨𝐟𝐢𝐭 = 𝐓𝐑 − 𝐓𝐂
Total Revenue
𝑇𝑅 = 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 𝑓𝑟𝑜𝑚 𝑠𝑜𝑙𝑑 𝑡𝑟𝑢𝑐𝑘𝑠 + 𝑟𝑒𝑣𝑒𝑛𝑢𝑒 𝑓𝑟𝑜𝑚 𝑠𝑜𝑙𝑑 𝑡𝑟𝑎𝑖𝑛𝑠
𝑇𝑅 = 𝟓𝟓𝟎𝒙𝟏 + 𝟕𝟎𝟎 𝒙𝟐
Total Cost
Materials: 50𝑥1 + 70 𝑥2
Carpentry: 30𝑥1 + 60 𝑥2
Finishing: 20𝑥1 + 20 𝑥2
Total Cost 𝟏𝟎𝟎𝒙𝟏 + 𝟏𝟓𝟎 𝒙𝟐
𝐏𝐫𝐨𝐟𝐢𝐭 = 𝟓𝟓𝟎𝒙𝟏 + 𝟕𝟎𝟎 𝒙𝟐 − 𝟏𝟎𝟎𝒙𝟏 + 𝟏𝟓𝟎 𝒙𝟐
Objective: Maximize z: 𝟒𝟓𝟎𝒙𝟏 + 𝟓𝟓𝟎 𝒙𝟐
MANAGEMENT SCIENCE
Step 3. Set up the Constraints
If there are no restrictions, objective function (profit) can
grow to infinity.
From the previous example, there are three restrictions
(called constraints) for the toys production:
1. Each month Toy Story , Inc. has only 5000 available hours of
carpentry labor.
2. Each month no more than 3000 hours of finishing labor may be used.
3. Because of limited demand, at most 2000 trucks should be produced
each month
MANAGEMENT SCIENCE
• The truck requires 1 hour of carpentry labor and 1 hour of finishing labor
(assembling and painting). The train requires 2 hours of carpentry labor
and 1 hour of finishing labor
• Toy Story has 5000 available hours of carpentry labor and 3000 hours
of finishing labor. Demand for trains is unlimited, but at most 2000
trucks are, at an average, bought each month
Products
Department/category Truck (𝒙𝟏 ) Train Allocation
(𝒙𝟐 )
Carpentry
Finishing (assembly & Painting)
demand
MANAGEMENT SCIENCE
Answer
Products Allocation
Department/category Truck (𝒙𝟏 ) Train
(𝒙𝟐 )
Carpentry 1 2 ≤ 5000
Finishing (assembly & Painting) 1 1 ≤ 3000
demand ≤ 2000
Carpentry: 𝑥1 + 2 𝑥2 ≤ 5000
Finishing: 𝑥1 + 𝑥2 ≤ 3000
Demand: 𝑥1 ≤ 2000
Implicit/nonnegativity Constraints: 𝑥1 0, 𝑥2 0
MANAGEMENT SCIENCE
Linear Program
Maximize: 𝒛 = 𝟒𝟓𝟎𝒙𝟏 + 𝟓𝟓𝟎 𝒙𝟐
Subject to: 𝑥1 + 2 𝑥2 ≤ 5000
𝑥1 + 𝑥2 ≤ 3000
𝑥1 ≤ 2000
𝑥1 0, 𝑥2 0
MANAGEMENT SCIENCE
Mind Exercise
Requirements:
1. Define the decision variables
2. Identify the Objective Function
3. Set up the constraints (explicit and implicit/nonnegativity)
4. Prepare the appropriate linear program
MANAGEMENT SCIENCE
Mind Exercise
Problem 1
Zeera-zeera Furnitures manufactures tables and chairs. Each
product is processed in two departments, Department A (carpentry
and assembly) and Department B (varnishing and quality check).
Each unit of table requires 1 hour of processing in Dept. A, and 2
hours in Dept. B, and each unit of chair requires 3 hours on Dept. A.
and 1 hour on Dept. B. The expected profit is P200 per unit on
tables and P300 per unit on chairs. It is then determined that
Department A is available for 200 hours each month and
Department B for 300 hours. How many units of each product can
be manufactured in one month in order to maximize the profits?