Bcon 141 – Introduction to
Business Economics
Module 3: Business Optimization using
Linear Programming
Ian Dave B. Custodio
Instructor
Bcon 141
Lesson 6: Linear Programming
Learning objectives:
- Define Linear Programming
- Differentiate the different assumptions of Linear Programming
- Solve Linear Programming Problems
Bcon 141
Outline
6.1 Linear Programming: Definition and Properties
6.2 LP Model Components
6.3 Steps of Model Formulation
6.4 Finding Solution
6.4.1 Graphical Solution
6.4.2 Mathematical Solution
6.4.3 Computer Solution using Excel Add-ins: Solver and OM/QM
6.5 Special Cases of LPP
Bcon 141
6.1 Linear Programming:
Definition and Properties
Bcon 141
Linear Programming
- a tool in Mathematics for solving optimization problems.
optimization (mathematical optimization): is one in which some function (objective) is
either maximized or minimized relative to a given set of constraints.
- in business and economics, it is a model that consists of linear relationships
representing a firm’s decision(s), given an objective and resource constraints.
Bcon 141
Properties (or assumptions):
1. Proportionality
2. Additivity
3. Divisibility
4. Certainty
Bcon 141
1. Proportionality
- implies that the marginal rate of contribution to the objective for each variable is
assumed to remain constant throughout the entire range of activity levels in the
problem.
This means, if the product contributes P20 towards the profit, then the total
contribution would be equal to 20x1, where x1 is the number of units of the product.
For example:
5 units of the product = P100
10 units of the product = P200
Bcon 141
2. Additivity
- implies that the contribution of the variables to the objective is assumed to be the
sum of their individual weighted contributions.
The total value of the objective function is equal to the sum of the
contributions of each variable to the objective function.
TPr = 𝑃1 𝑋1 + 𝑃2 𝑋2+ 𝑃3 𝑋3
where: TPr = Total Profit, P are profit for each product X
Bcon 141
3. Divisibility
- means that the variables can take on any non-negative value including fractional
values (the variables are said to be continuous or divisible, as opposed to integer or
discrete values).
For example:
10 1/4 maple tables
5.5 cherry tables
Bcon 141
4. Certainty
- means that the problem is assumed to have no probabilistic elements (such as
changes on input prices for labor, raw materials, etc.).
For example,
The net profit per cherry table is 2,000, but this value depends upon the tables’
cost, the cost of materials, and the sale price wherein all of which could be random
variables.
Bcon 141
6.2 LP Model Components
Bcon 141
LP Model components
1. Decision variables
2. Objective function
3. Constraints
4. Parameters
Bcon 141
1. Decision variables (unknowns)
- mathematical symbols (e.g. characters, letters) representing the decisions to be
made.
Examples: 𝑋1 = number of cherry tables to be made
𝑋2 = number of pine tables to be made
Bcon 141
2. Objective function
- a linear mathematical relationship describing an objective of the firm, in terms of
decision variables - this function is to be maximized or minimized.
Examples: Maximize Profit
Minimize Costs
Bcon 141
3. Constraints
– requirements or restrictions placed on the firm by the operating environment, stated
in linear relationships of the decision variables.
Examples: 𝑋1 + 𝑋2 >= 1,000 hectares
𝑋1 <= 500 hectares
Bcon 141
4. Parameters
- numerical coefficients and constants used in the objective function and constraints.
Examples: Pr = 10𝑋1 + 5𝑋2
𝑋1 + 𝑋2 >= 1,000
Bcon 141
6.3 Steps of Model
Formulation
Bcon 141
Steps of Model Formulation
Step 1 : Define the decision variables
(What do you want to know or to determine?)
Step 2 : Define the objective function
(Maximize? or Minimize?)
Step 3 : Define the constraints
(What are the limitations on resources?)
Bcon 141
Example Problem:
Philippine Pottery Company is a small crafts operation run by a Native Filipino Tribal
Council. The company employs skilled artisans to produce clay bowls and mugs with
authentic native Filipino designs and colors. The two primary resources used by the
company are special pottery clay and skilled labor. The bowl needs 1hr of labor and needs
4kls of clay while the mug needs 2hrs of labor and 3kls of clay. Bowl yields a profit of P40
while mug yields P50. There are 40 hours of labor and 120 kls of clay available each day
for production.
Given those limited resources, the company desires to know how many bowls and mugs
to produce each day in order to maximize profit.
Bcon 141
Resource Requirements
Labor Clay Profit
Product
(Hr/Unit) (Kls/Unit) (P/Unit)
Bowl 1 4 40
Mug 2 3 50
Figure 1 The Philippine Pottery Company
Bcon 141
Step 1 : Define the decision variables
What is/are the decision variables of the problem?
Step 2 : Define the objective function
What is the objective function?
Step 3 : Define the constraints
What is/are the constraints?
Bcon 141
Resource Availability: 40 hrs of labor per day
120 kls of clay
Decision Variables: x1 = number of bowls to produce per day
x2 = number of mugs to produce per day
Objective Function: Maximize Z = P40x1 + P50x2
Where Z = profit per day
Resource Constraints: 1x1 + 2x2 ≤ 40 hours of labor
4x1 + 3x2 ≤ 120 pounds of clay
Non-Negativity Constraints: x ≥ 10; x2 ≥ 0
Bcon 141
Complete Linear Programming Model of the problem:
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 ≤ 40
4x1 + 3x2 ≤ 120
x ≥ 10; x2 ≥ 0
Bcon 141
6.4 Finding Solution
Bcon 141
1. Graphical Solution
2. Mathematical Approaches:
1.1 Substitution
- Substitute one variable in terms of the other equation.
1.2 Elimination (via Addition or Subtraction)
- Eliminate one of the variables by adding/subtracting the equations
then find the value of the remaining variable.
Bcon 141
3. Computer Solutions (using MS Excel/ Excel Add-in):
2.1 Graphical
2.2 Solver
2.2 OM/QM
Bcon 141
6.4.1 Graphical Solution
Bcon 141
Graphical Solution
- one of the most used solution for solving Linear Programming problems which only
involves two decision variables.
- it solves the problem by plotting the functions and constraints in a graph and
determine the most feasible solution.
- “geometric approach”
Bcon 141
Feasible vs. Infeasible Solution
Feasible Solution
- Solution does not violate any of the constraints
Infeasible Solution
- Solution violates at least one of the constraints
Bcon 141
Complete Linear Programming Model of the previous problem:
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 ≤ 40
4x1 + 3x2 ≤ 120
x ≥ 10; x2 ≥ 0
Bcon 141
Feasible Solution
Example: x1 = 5 bowls
x2 = 10 mugs
Z = P40x1 + P50x2 = P700
Labor constraint check: 1x1 + 2x2 40
1(5) + 2(10) = 25 ≤ 40 hours
Clay constraint check: 4x1 + 3x2 120
4(5) + 3(10) = 50 ≤ 120 kls
Bcon 141
Infeasible Solution
Example: x1 = 10 bowls
x2 = 20 mugs
Z = P40x1 + P50x2 = P1400
Labor constraint check: 1x1 + 2x2 40
1(10) + 2(20) = 50 > 40 hours
Bcon 141
X2 are mugs
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
X1 are bowls
Figure 2 Coordinates for Graphical Analysis
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 3 Graph of the labor constraint
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 4 Labor constraint area
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 5 The constraint area for clay
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 6 Graph of both constraints
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Feasible region
-the set of all points that
satisfy all the constraints of
the model(s).
Figure 7 The feasible solution area on the
constraints
Bcon 141
Finding the optimal solution:
Isoprofit Approach
-“iso” means equal/same
-the profit anywhere on the
line is the same.
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 8 Objective function line for Z = $800
Bcon 141
Finding the optimal solution:
Isoprofit Approach
-“iso” means equal/same
-the profit anywhere on the
line is the same.
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 9 Alternative objective function lines
for profits, Z, of P800, P1,200, and P1,600
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 10 Identification of the optimal solution
point
Bcon 141
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Point B coordinates:
x1 = 24
x2 = 8
Figure 11 Optimal solution coordinates
Bcon 141
Finding the optimal solution:
Corner Point Solution
-the optimal solution to a
LPP, if it exists, occurs at the
corners (vertex) of the
feasible region.
Maximize Z = P40x1 + P50x2
subject to: 1x1 + 2x2 40
4x1 + 3x2 120
x1, x2 0
Figure 12 Solutions at each corner points
Bcon 141
6.4.2 Mathematical Solution
Bcon 141
Mathematical Solutions
Substitution
- Substitute one variable in terms of the other equation.
Elimination (via Addition or Subtraction)
- Eliminate one of the variables by adding/subtracting the equations
then find the value of the remaining variable.
Bcon 141
6.4.3 Computer Solution using Excel
Add-ins: Solver and OM/QM
Bcon 141
2.1 Graphical Solution (using Excel 2013)
Plug in the data (derived coordinates)
Bcon 141
1. Highlight the
2.1 Graphical Solution (using Excel 2013)
coordinates of the
first constraint.
2 4 2. Go to “Insert” Tab
5
3 3. Select
“Recommended
Charts”
4. Select “All Charts”
and click “X Y
Scatter”
1 5. Select “Scatter
with Straight Lines”
6. Select the second
image showing a
single a straight line
and click “OK”
Bcon 141
2.1 Graphical Solution (using Excel 2013)
Right click on the Letter “B” at the top of the graph and click “Delete”.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Click anywhere on
the graph.
2. Select the funnel
like icon.
3. Click on the
“Select Data…”
menu on the bottom
1 2 part of the window
that popped up.
3
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Select “B” and
click “Edit”
1
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Delete all the
contents on the
“Series Name”
2. Click the encircled
icon.
1 2
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Then click on the
cell that contains the
word “Labor
Constraint”
2. Click back the
encircled icon.
1 2
3. Empty the “Series
3 X values:”
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Click the encircled
icon.
2. Our X-axis values
are the x1 values for
both points, so
highlight the x1
values on Point A
2 and B. (0, 40)
3. Click back on the
1 encircled icon.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Empty the “Series
Y values:” then click
the encircled icon.
2. Our Y-axis values
are the x2 values for
both points, so
highlight the x2
values on Point A
and B. (20, 0)
2
1 3. Click back on the
encircled icon and
click OK on the
bottom part of the
window.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. So we’re done
with the first
constraint and now
we will incorporate
the second
constraint (Point C
and Point D) on the
graph. Start by
clicking “Add”
1
2. Just follow the
same steps (from
the previous four
slides) on
constructing the
graph of the first
constraint.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
Once done, you should have the same graph as shown below. Just click “OK” to finish
setting up the graph of both constraints.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
We need to reduce the intervals of the data points in each axis in order to determine the
coordinates of the optimal point (point of intersection).
1. Start on the x-
axis. Right Click on
any of the values (0
– 45) on the x-axis
and select “Format
Axis” on the menu.
1
Bcon 141
2.1 Graphical Solution (using Excel 2013)
1. Change the
value of the “Major”
submenu under the
“Units” menu from
“5.0” to “1.0” and
press enter on the
keyboard in order
to have a detailed
scaling on the x-
axis.
2. Repeat the same
1 step for the y-axis.
Bcon 141
2.1 Graphical Solution (using Excel 2013)
Enlarge the graph and we can now determine the coordinates of the optimal point (24,8).
x1 (x-axis): 24
x2 (y-axis): 8
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Load first the Solver Add-in by following the instructions (for Windows OS) below from the
official Microsoft Support ([Link]
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Plug in the data (based on the given of the problem) with the following format.
Non-negativity Constraint
Objective Function
Constraints
Results area. Cells highlighted
in yellow will reveal the
solution.
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Highlight the
resulting cells of
the objective and
the constraints
(B11, B12, B13)
and insert the
formula shown in
the picture. After
the MMULT,
highlight the given
of the objective and
the constraint
(B2:C7) and after
the TRANPOSE
highlight the
resulting values of
x1 and x2
(B15:C15).
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Once done typing the formula, press “Ctrl + Shift + Enter” on the keyboard to have the
following output.
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Go to “Data” tab and on the rightmost menu, click on “Solver” and the Solver window will
pop-up.
1
2
Bcon 141
2.2 Solver Add-in (using Excel 2013)
If all are set, then
you can now solve
the problem by
clicking the “Solve”
Choose according to the objective button at the
Title of the problem bottom of the
Solver widow.
Make sure to tick the checkbox
Choose “Simplex LP”
Bcon 141
2.2 Solver Add-in (using Excel 2013)
Click “OK” on the window that will pop-up and you now have the answer.
Max Profit =
1,360
Optimal Combination: x1=24, x2=8
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
Install first the OM/QM (Weiss or Taylor’s version) add-in by downloading from this link:
[Link]/EXCELOMQM-WEISSv4
Once finished downloading, double click the file and follow the installation process.
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
1. After double clicking the file, a window will pop-up, Just click “Next”
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
2. Click “Next”
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
3. Choose 32 bit, if there’s an error that will pop-up saying that it is not compatible, then
choose 64 bit and then click “Next”
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
4. Click “Next”
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
5. And lastly, click “Next”. After clicking the Next button, the installation window will
disappear and Excel OM/QM is already installed. You can now enable the add-in by
following the same steps of the Solver Add-in.
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
Open a new excel workbook, go to File > Options > Add-ins > Select “Excel Add-ins” on
the Manage Menu and click “Go…”. This window will pop-up. Make sure to check both
Excel OM/QM and Solver Add-in and click “OK”.
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
Once already enabled, a new tab named “Excel QM” will appear.
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
To use the add-in, go to Excel QM tab and click “By Chapter”, then click “Chapters 2,3,4;
Linear Programming” menu.
1
2
3
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
A window will pop-up. Fill in the needed information and once done, click “OK”.
Title of the problem
Enter the number of constraints
(in our example, we have two
constraints, labor and clay)
Enter the number of decision
Choose according to
the objective of the variables (in our example, we
problem have two decision variables, x1
and x2)
Those are just the important parameters/menus needed to be adjusted
according to the problem. Just leave the other menus “as is”.
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
Input the given of the problem on the orange highlighted areas. Leave the other items “as
is”.
Constraint 1 is the Labor Constraint Total Available
Resources
Constraint 2 is the Clay Constraint
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
In order to solve the problem, OM/QM also utilizes the Solver Add-in. To solve, go to
“Data” tab, click “Solver” and directly click the “Solve” button.
1 2
3
Bcon 141
2.3 OM/QM Add-in (using Excel 2013)
Another solver window again will pop-up, just click “OK” and you now have the answer.
Optimal Combination: x1=24, x2=8
Profit = 1, 360
Bcon 141
6.5 Special Cases of Linear
Programming Problems
Bcon 141
Special types of problems include those with:
1. Multiple optimal solutions
2. Infeasible solutions
3. Unbounded solutions
Bcon 141
1. Multiple optimal solutions
The objective function is
parallel to a constraint line.
Maximize Z=40x1 + 30x2
subject to: 1x1 + 2x2 40
4x2 + 3x2 120
x1, x2 0
Where:
x1 = number of bowls
x2 = number of mugs
Graph of an example with multiple optimal solutions
Bcon 141
2. Infeasible solutions
Every possible solution
violates at least one constraint:
Maximize Z = 5x1 + 3x2
subject to: 4x1 + 2x2 8
x1 4
x2 6
x1, x2 0
Graph of an infeasible problem
Bcon 141
3. Unbounded solutions
Value of the objective
function increases indefinitely:
Maximize Z = 4x1 + 2x2
subject to: x1 4
x2 2
x1, x2 0
Graph of an unbounded problem
THANK YOU!
