SUSS Application of Linear Programming Worksheet

BUS107v QuantitativeMethods
Online Unit 1A –
Linear
Programming by
Solver
19:15
1
Agenda for Unit 1: LP (Solver)
COVERED TONIGHT
•
•
CONTENT: the foundations of LP; maths; no graphical works yet
APPROACH: practical with some theory explained; pitstops every 5 minutes to take questions;
case study (Toy Gun production maximisation LP), one Breakout Room exercise (Car Seat
minimisation LP), and occasional poll(s) to practice
•
Preparation stage of LP:
• ACTIVITY 1 – identification of the 3 LP parameters applied to the Toy Gun case:
• Decision variables, objective function, and constraints
• ACTIVITY 2 – Poll on LP constraint linearity
• ACTIVITY 3 – LP formulation and matrix table for the Toy Gun case:
• Problem definition, description, and matrix table of LHS/RHS constraints
•
Execution stage of LP:
• ACTIVITY 4 – Excel Solver implementation on the Toy Gun maximisation problem
• Solver tab and run; interpretation of results and answer report
• ACTIVITY 5 – Group break out exercise: the Car Seat case study on minimisation problem
•
Analysis stage of LP:
• ACTIVITY 6 – Sensitivity on objective coefficients (range of optimality) for the Toy Gun case
• ACTIVITY 7 – Sensitivity on feasibility constraints (range of feasibility) and shadow price
•
COVERED IN THE FIRST 90 MINUTES OF NEXT WEEK
Graphical stage of LP:
• ACTIVITY 8 – 2-D graphical plot and solution for LP by hand drawing and excel for Toy Gun
• Production of 2-D LP, constraint lines, feasible region (FR), objective line, solution
• ACTIVITY 9 – LP solving by observation of 2-D graphical plot on a minimisation problem
• ACTIVITY 10– 2-D graphical plot and solution for LP by excel (Extra case for practice)
2
19:18
Introduction to LP
and identification of
LP
parameters
19:18
3
Introduction to LP
Most business enterprises have two primary objectives in their
operations, viz:
1)
2)
To maximize profits for the business
To minimize costs of operations
Profits or costs should not be taken in their restricted $
definition. Think out of the box!
Maximisation can also cover revenues, benefits, returns, health
and anything positive like happiness etc.
Minimisation can cover time, resources (raw materials or work
required by employees), wastage, defects, risks etc.
Linear Programming (LP) is used at solving maximisation /
minimisation problem when things are complex (programming
one objective with multiple constraints) but relationships are
straight-forward (linear).
LP can be applies to a wide spectrum of industries.
19:21
4
Any business activity to optimise can be
represented as a funnel and formalised as a LP
Inputs (PROBLEM)
• What are they? Example: milk and cocoa
• What do we need to produce, deliver, service? Example: 1 kg
unit of milk and 1 kg unit of cocoa to produce 1 unit (tablet) of
ChocoStorm A
Limitations (CONSTRAINTS)
• How do the various inputs relate to each other? Example:
the mix of milk and cocoa to produce 1 tablet of
ChocoStorm A is 1:1 .
• Any physical limits on these inputs or their combinations?
Example: The maximum quantity of daily milk consumption
is 2 kgs; the maximum daily limit for cocoa is 3 kgs
Outputs (DECISION VARIABLES)
• What are the outputs of the activity? Example: Two products:
ChocoStorm A tablet sold at $6 and ChocoStorm B tablet sold at $8
• What quantities of inputs must be used to achieve: maximum
revenue/profit? Or minimum cost? Example: how much milk and cocoa
are consumed for each tablet of ChocoStorm tablets A and B
A purpose (OBJECTIVE)
• Why are we in this business? Example: maximise revenue
from combined sale of ChocoStorm tablets A and B
• What is the context / challenge / opportunity? Example:
maximise sale knowing constraints on quantities
19:23
5
Characteristics of LP
• The Linear Programming (LP)
Model consists of the 3 following
components (the holy trinity):
A set of decision variables (Outputs)
E.g., quantity of ChocoStorm A and B sold => floating numbers
(unlike constraints and price/cost/profit that are fixed); driven by
the other factors (objective and constraints); their adjustment
will eventually resolve the LP problem
An objective function (on profit or cost)
E.g., quantity * price of ChocoStorm A and B => a mathematical
function or statement combining the variables and
price/cost/profit; will eventually give you the total sales or profits
that you seek to maximise or the total costs that you want to
minimise
A set of constraints (on resources)
E.g., the maximum daily quantity of milk and cocoa, given how
much is necessary to produce ChocoStorm A and B =>
physical constraints on required resources; expressed as a
maximum limits or minimum requirements, like space,
available labour hours or raw materials
19:26
6
BUS107e Classroom Session 1
Activity 1
Identifying the Decision
Variables, Objective
Function and Constraints
for Toy Gun Production
Time Given: 5 minutes
19:26
7
Toy Gun Case Study
A Maximization Problem
During the second world war, USIM Manufacturing
produced only 2 types of toy guns – Space Ray and
Zapper. USIM wanted to keep profits but the war effort
put some constraints on the use of resources necessary
to produce the toy guns. Kids were also less into space
toy guns, so demand was somehow lower.
In production, Space Ray and Zapper each required 2 kg
and 3 kg of plastic respectively. Each needed 1 manhour per unit.
The demand for Space Ray was not more than 6 units a
day. Due to war time constraints, there were only 8 manhours per day available of civil production activities and
our supplier provides only 19 kilogram of plastic daily.
Profit was good – $5 for Space Ray and $7 for Zapper.
19:28
8
Instructions:
Read the Toy Gun production case study in
the previous slide for this Activity.
19:30
9
Debrief for Activity 1
19:35
10
Decision Variables
•
•
•
Number of Space Ray guns to be produced
Number of Zapper guns to be produced
(there is one unique combination or mix which maximises the profit)
The ratio of Space to Zapper guns is called the product mix ratio
Objective Function
•
To maximise the combined profit from selling the optimal number of each
gun as determined by the LP solution, picking up the optimal mix
Space Ray
Zapper
$5
$7
Profit per gun
Constraints
•
•
•
Demand for Space Ray guns (maximum 6 units) – a market demand factor
Labour hours (maximum of 8 hours) – a supply factor on labour
Plastic materials available (maximum is 19 kg) – a supply factor on raw material
Resources required per
unit of gun per day
Space
Zapper
Ray
Maximum
Available per
day
Labour hours
1 hour
1 hour
8 hours
Plastic materials
2 kg
3 kg
19 kg
19:39
11
Formulation of
Linear Programming
19:40
12
LP Model
Now, let’s formulate mathematically the LP
model , so we can solve the problem:
1) Decision variables = how many guns of
each type to produce (known as the Product
Mix)
2) Objective function = Algebraic equation
linking the Decision variables
3) Constraints = physical resources and
market demand
19:42
13
Decision Variables
As we do not know their quantities at the start, we can label
them as X1 and X2, as shown below:
Let X1 = quantity of Space Ray Guns to be produced
Let X2 = quantity of Zapper Guns to be produced
Objective Function
The factory Manager needs to determine the quantity of X1 and
X2 to maximize the company’s profit (Z). A Space Ray gun (X1)
and a Zapper gun (X2) can be sold at a unit profit of $5 (C1) and
$7 (C2) per gun respectively.
Max(Z)
= C1*X1 + C2*X2
= 5X1 + 7X2
19:45
14
Constraints (on resources)
Constraints are a set of mathematical statements that are related to physical resources such
as time, workers, raw materials, labour capacity, etc.
1)
2)
3)
4)
5)
X1 ≤ 6
X1 + X2 ≤ 8
2X` + 3X2 ≤ 19
X1, X2 ≥ 0
X1, X2 INT
(market demand)
(labour hours per day)
(plastic materials)
(both decision variables are non-negative, cannot be less)
(both decision variables must be integers; cannot be parts)
GENERAL STRUCTURE: The mathematical statements has two sides and a sign, dividing the
two sides. The sign divides the statement into a Left-Hand Side (LHS) and a Right-Hand Side
(RHS) as explained below.
LHS RHS
SIDES: LHS includes the decision variables (e.g., a * X1 and b* X2) and a constant, which
indicates the physical need required for each variable, e.g., 2 kgs of plastic for X1 . RHS is just
a NUMBER. This number is usually a maximum limit or minimum requirement on the
resource concerned. It is always given in the LP question.
SIGNAGE: Each statement uses one of the following signs: ≤, (less than or equal to), =
(equal), ≥. (more than or equal to). The inequality signs have different meanings depending
on whether we read the constraint from left to right (→) or from right to left ()
19:50
15
Mandatory in GBA
Steps to Formulating an LP Model:
Step
1
2
3
4
5
6
Critical Tasks
Identify the
Decision variables
Define the Decision
variables
algebraically)
Formulate the
Objective function
into an algebraic
equation
Identify all the
Constraints
Define the
constraints in
algebraic format
Indicate the nonnegative constraint
Outcome
Spare Ray guns
Zapper Guns (for example)
X1 = No. of Space Rays
X2 = No. of Zappers
Maximise Z = 5X1 + 7X2
Market Demand
Labour hours
Plastic materials
`X1 ≤ 6
X1 + X2 ≤ 8
3X` + 1 X2 ≤ 19
X1, X2 ≥ 0
19:52
16
Algebraic Model of the Toy Gun LP Model
(Algebraic Model)
Max Z = 5X1 + 7X2
Subject to:
(the non-negative
constraint is
mandatory in most
LP model; integers
are optional, but I
strongly
recommend you
mention if relevant
in the case)
X1 ≤ 6 (Market Demand)
X1 + X2 ≤ 8 (Labour hours)
2X1 + 3X2 ≤ 19 (Plastic Materials)
X1 , X2 ≥ 0
(Non-negativity)
X1 , X2 INT (Integers)
19:54
Good to give a description for each constraint
17
Activity 2 (Polling)
(about 2 minutes)
Which of the following algebraic expression is
acceptable as a constraint for Linear
Programming?
1)
4 X 2 − 7Y  25
2)
3)
5 XY + 4Y  15
4)
5)
1.2 X − Y  32
X
+Y = 3
Y
− 2 X + 3Y  50
19:55
Please Indicate the correct answer in your Zoom Polling screen
18
Activity 2 (Polling)
Debrief
19:56
19
1)
4 X − 7Y  25
3)
5 XY + 4Y  15
5)
1.2 X − Y  32
2
X
2)
+Y = 3
Y
4 ) − 2 X + 3Y  50
In simple terms, a linear function such as
Z = C1X1 + C2X2 has decision variables
that do not multiply between themselves
and which are not non-linear (i.e.. with an
exponent not equal to 1). Examples of
non-linear decision variables are X1*X2,
SQRT (X) (or X1/2) and X2.
Based on the above definition, only the
function in Statement #4 is the only
linear relationship.
19:58
20
BUS107e Classroom Session 1
Activity 3
Use a LP Matrix to prepare
the Solver calculation
Time Given: 10 minutes
19:58
21
Refresh the Case
Toy Gun Case Study
During the second world war, USIM Manufacturing
produced only 2 types of toy guns – Space Ray and
Zapper.
In production, Space Ray and Zapper each required 2 kg
and 3 kg of plastic respectively. Each needed 1 manhour per unit.
The demand for Space Ray was not more than 6 units a
day. Due to war time constraints, there were only 8 manhours per day available of civil production activities and
our supplier provides only 19 kilogram of plastic daily.
Profit was good – $5 for Space Ray and $7 for Zapper.
19:58
22
Instructions:
Refer to the Toy Gun production case and complete the LP matrix below for the following:
1)
Define the Decision Variables identified earlier by using some algebraic symbols such as X1
and X2
2)
Express the Objective Function as an algebraic equation involving the Decision Variables
defined above.
3)
Formulate the Constraints as inequalities
Matrix for pre-LP formulation:
Decision Variables
Constraints
Demand
SR (X1)
Sign
1
≤
Labour
Plastic
Profit
1
2
7
Max (RHS)
6
≤
≤
19
—
—
19:59
All signs are read from left to right
23
Debrief for Activity 3
20:08
+7’
demo
24
The Toy Gun LP Model
(Algebraic Model)
Max Z = 5X1 + 7X2
Subject to:
X1 ≤ 6
(Market Demand)
2X1 + 3X2 ≤ 19 (Plastic materials)
X1 + X2 ≤ 8 (Labour hours)
X1 , X2 ≥ 0
20:09
25
Instructions:
Matrix for pre-LP formulation:
Constraints
Decision Variables
SR (X1)
ZP (X2)
Sign
Max
(RHS)
Demand
1
0
≤
6
Labour
1
1
8
Plastic
2
3
≤
≤
19
Profit
5
7
—
—
20:15
All signs are read from left to right
26
BUS107e Classroom Session 1
Group Activity 4
Use of Excel Solver to
determine the LP solution
for Toy Gun case study
Time Given: 20 minutes
20:15
27
How to get the Add -in functions:
Analysis ToolPak (Data Analysis) and Solver
For PC
For Mac
1.Click the File tab, click
1. On the Tools menu,
Options, and then click
select Add-Ins.
the Add-Ins category.
2. In the Add-Ins
2.In the Manage box,
available box, select
click Excel Add-ins, and
the add-in you want,
then click Go. The Addand then click OK.
Ins dialog box appears.
3.In the Add-Ins available
box, select the check box
next to the add-in that
you want to activate, and
20:18
then click OK.
28
Instructions:
3) Complete the accompanying Excel spreadsheet .
(some information have already been entered for
you)
4) Under the Data tab of Excel, click Solver located
at the far right of the top menu of Excel.
5) Enter the required information into the Solver
App by clicking the appropriate cells in the Excel
spreadsheet.
6) Check that your formulas and entries are correct
before clicking for Solver completion
7) Generate the Answer and the Sensitivity Reports
using the Solver App.
20:19
29
Debrief for Activity 4
20:20
+ 15’
demo
30
• The LP solver interface
1. The LP matrix
3. The Solver results tab
2. The Solver parameters tab
20:25
31
• Excel Solver Optimal Solution (Answer Report)
Mandatory in GBA
Objective Cell (Max)
Cell
$G$8 Max RHS
Name
Original Value Final Value
$
46.00 $
46.00
Z maximum
Space Ray profit per unit = $5, Zapper = $7
$5(5) + $7(3) = $46
Variable Cells
Cell
Name
$C$4 Adjustment Variable SR – X1
$D$4 Adjustment Variable ZP – X2
Original Value
5.00
3.00
What is provided
by Solver
Final Value
Integer
5.00 Contin
3.00 Contin
Space Ray
Zapper
Binding → see next slide
Constraints
Cell
Name
Cell Value
Formula
Status
Slack
RHS
$E$5:$E$7