Operationalizing Linear Models Excel Task

Problem #1  Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and safety. The K250 model has a new engine and a low profile that make it easy to balance. The QX-500 model is slightly larger, uses a more traditional engine, and is specifically designed to appeal to women riders. Embassy produces the engines for both models at its Jeddah plant. Each K250 engine requires 6 hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing time. The Jeddah plant has 2100 hours of engine manufacturing time available for the next production period. Embassy’s motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500 frame is more complex and the supplier can only provide up to 280 QX-500 frames for the next production period. Final assembly and testing requires 2 hours for each K250 model and 2.5 hours for each QX-500 model. A maximum of 1000 hours of assembly and testing time are available for the next production period. The company’s accounting department projects a profit contribution of $2400 for each K250 produced and $1800 for each QX-500 produced.   Formulate a linear programming model that can be used to determine the number of units of each model that should be produced in order to maximize the total contribution to profit.

In-class Practice Exercises: Formulating a Linear Programming Model
Problem #1
Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and
safety. The K250 model has a new engine and a low profile that make it easy to balance. The QX-500
model is slightly larger, uses a more traditional engine, and is specifically designed to appeal to women
riders. Embassy produces the engines for both models at its Jeddah plant. Each K250 engine requires 6
hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing time. The
Jeddah plant has 2100 hours of engine manufacturing time available for the next production period.
Embassy’s motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500
frame is more complex and the supplier can only provide up to 280 QX-500 frames for the next
production period. Final assembly and testing requires 2 hours for each K250 model and 2.5 hours for
each QX-500 model. A maximum of 1000 hours of assembly and testing time are available for the next
production period. The company’s accounting department projects a profit contribution of $2400 for
each K250 produced and $1800 for each QX-500 produced.
Formulate a linear programming model that can be used to determine the number of units of each
model that should be produced in order to maximize the total contribution to profit.
Problem #2
Mohammed recently inherited a large sum of money; he wants to use a portion of this money to set up
a trust fund for his two children. The trust fund has two investment options: (1) a bond fund and (2) a
stock fund. The projected returns over the life of the investments are 6% for the bond fund and 10% for
the stock fund. Whatever portion of the inheritance Mohammed finally decides to commit to the trust
fund, he wants to invest at least 30% of that amount in the bond fund. In addition, he wants to select a
mix that will enable him to obtain a total return of at least 7.5%.
Formulate a linear programming model that can be used to determine the percentage that should be
allocated to each of the possible investment alternatives.
Problem #3
Blue Ocean Restaurant would like to determine the best way to allocate a monthly advertising budget of
SAR 4,000 between poster advertising and online advertising. Management decided that at least 25% of
the budget must be spent on each type of media, and that the amount of money spent on local poster
advertising must be at least twice the amount spent on online advertising. A marketing consultant
developed an index that measures audience exposure per dollar of advertising on a scale from 0 to 100,
with higher values implying greater audience exposure. If the value of the index for local poster
advertising is 50 and the value of the index for online advertising is 80, how should the restaurant
allocate its advertising budget in order to maximize the value of total audience exposure?
Formulate a linear programming model that can be used to determine how the restaurant should
allocate its advertising budget in order to maximize the value of total audience exposure.
Linear Programming
DR JOEL M. EVANS
Housekeeping
• Midterm #1
• Remaining Deliverables
2
Review: Tools of Analysis
Analysis
Purpose
Descriptive statistics
•
What do the data look like?
•
What is the central tendency of the data?
•
How spread out are the data?
•
What is the relationship between two
variables?
•
What value of an input do we need to
achieve a specified value of an output?
•
E.g., break-even point; profit goal
1-way data table
•
How does the value of an outcome change
in response to a range of different values of
an input?
2-way data table
•
How does the value of an outcome change
in response to a range of respective values
for two separate inputs?
Goal seek
3
Review: Tools of Analysis
Analysis
Purpose
Moving averages &
exponential smoothing
•
How might we predict the value of a
variable based on its past values?
Multiple regression
•
How might we predict the value of a
variable based on a set of other variables?
•
Which input variables are significant
predictors of an outcome variable?
•
How does the predictive ability of an input
variable change once we control for other
input variables?
•
What is the equation for modeling these
predictive relationships?
•
Value optimization: What combination of
input values do we need to maximize or
minimize a certain output value, accounting
for certain constraints?
Linear Programming
4
The Textbook
.
.
.
.
.
.
.
.
.
.
.
.
SLIDES BY
John Loucks
St. Edward’s Univ.
Chapter 7
5
Ch 7: Introduction to Linear Programming
•
•
•
•
•
•
•
•
Linear Programming Problem
Problem Formulation
A Simple Maximization Problem
Graphical Solution Procedure
Extreme Points and the Optimal Solution
Computer Solutions
A Simple Minimization Problem
Special Cases
6
Linear Programming
• Linear programming has nothing to do with
computer programming.
• The use of the word “programming” here means
“choosing a course of action.”
7
Mathematical Programming
• Mathematical programming is the development of
modeling and solution procedures which employ
mathematical techniques to optimize the goals and
objectives of the decision-maker.
• Programming problems determine the optimal
allocation of scarce resources to meet certain
objectives.
8
Components of an LP Formation
1)
Decision Variables
–
2)
The things we can control
Objective Function
–
3)
The goal
Constraints
–
4)
Limitations that we cannot control
Non-negativity Conditions
–
Often a natural constraint that is mathematically necessary
9
Decision Variables
• Decision variables represent unknown quantities.
The solution for these terms are what we would
like to optimize.
10
Objective Function
• The objective function states the goal of the decisionmaker. There are two types of objectives:
– Maximization, or
– Minimization
11
Constraints
• Constraints put limitations on the possible solutions of the
problem. The availability of scarce resources may be
expressed as equations or inequalities which rule out
certain combinations of variable values as feasible
solutions.
12
Non-negativity Conditions
• Non-negativity constraints are special constraints which
require all variables to be either zero or positive.
13
Linear Programming (LP) Problem
• A feasible solution satisfies all the problem’s constraints.
• An optimal solution is a feasible solution that results in the
largest possible objective function value when maximizing
(or smallest when minimizing).
• A graphical solution method can be used to solve a linear
program with two variables.
14
Linear Programming (LP) Problem
• If both the objective function and the constraints are linear,
the problem is referred to as a linear programming
problem.
• Linear functions are functions in which each variable
appears in a separate term raised to the first power and is
multiplied by a constant (which could be 0).
• Linear constraints are linear functions that are restricted to
be “less than or equal to”, “equal to”, or “greater than or
equal to” a constant.
15
Problem Formulation
• Problem formulation or modeling is the process of
translating a verbal statement of a problem into a
mathematical statement.
• Formulating models is an art that can only be mastered
with practice and experience.
• Every LP problems has some unique features, but most
problems also have common features.
• General guidelines for LP model formulation are illustrated
on the slides that follow.
16
Guidelines for Model Formulation
•
•
•
•
•
•
Understand the problem thoroughly.
Describe the objective.
Describe each constraint.
Define the decision variables.
Write the objective in terms of the decision variables.
Write the constraints in terms of the decision variables.
17
Redwood Furniture Company
Resource
Wood
Labor
Unit Profit
Unit Requirements
Table
Chair
30
5
6
20
10
8
Amount
Available
300
110
18
Redwood Problem Formulation
Let:
XT = number of tables produced
XC = number of chairs produced
Z = profit
MAX Z = 6 XT + 8 XC
s.t.
(subject to)
where:
30 XT + 20 XC < 300 5 XT + 10 XC < 110 XT, XC > 0
19
Cabinets Problem Formulation
• You need to buy some filing cabinets. You know that:
• -Cabinet X costs $10 per unit, requires six square feet
of floor space, and holds eight cubic feet of files.
• -Cabinet Y costs $20 per unit, requires eight square feet
of floor space, and holds twelve cubic feet of files.
• You have been given $140 for this purchase, though
you don’t have to spend that much. The office has room
for no more than 72 square feet of cabinets. How many
of which model should you buy, in order to maximize
storage volume?
20
Cabinets Problem Formulation
• Maximise z = 8x + 12y
• s.t.
10x + 20y < 140 6x + 8y < 72 (cost) (space) • Non-negativity x>0
y>0
21
Practice Exercises
1)
2)
3)
Go to the Content tab in Blackboard, and navigate to the
Practice Exercises folder.
Find the file called, “Practice exercises: Formulating
linear models”
Work through the problems as a group, and be prepared
to present your problem formulation.
22
Graphical LP Solution Procedure
1)
2)
3)
4)
5)
6)
7)
8)
Formulate the LP problem
Plot the constraints on a graph
Identify the feasible solution region
Plot two objective function lines
Determine the direction of improvement
Find the most attractive corner
Determine the coordinates of the corner
Find the value of the objective function
23
Example 1: A Simple Maximization Problem
• LP Formulation
Max
s.t.
5×1 + 7×2
x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0
Objective
Function
“Regular”
Constraints
Non-negativity
Constraints
24
Example 1: Graphical Solution
• First Constraint Graphed
x2
8
x1 = 6
7
6
5
4
3
Shaded region
contains all
feasible points
for this constraint
2
(6, 0)
1
1
2
3
4
5
6
7
8
9
10
x1
25
Example 1: Graphical Solution
• Second Constraint Graphed
x2
8
(0, 6.33)
7
6
2×1 + 3×2 = 19
5
4
3
2
1
Shaded
region contains
all feasible points
for this constraint
1
2
3
4
5
6
(9.5, 0)
7
8
9
10
x1
26
Example 1: Graphical Solution
• Third Constraint Graphed
x2
(0, 8)
8
7
x1 + x2 = 8
6
5
4
3
2
1
Shaded
region contains
all feasible points
for this constraint
1
2
3
4
5
(8, 0)
6
7
8
9
10
x1
27
Example 1: Graphical Solution
• Combined-Constraint Graph Showing Feasible Region
x2
x1 + x2 = 8
8
7
x1 = 6
6
5
4
3
2×1 + 3×2 = 19
Feasible
Region
2
1
1
2
3
4
5
6
7
8
9
10
x1
28
Example 1: Graphical Solution
• Objective Function Line
x2
8
7
(0, 5)
6
Objective Function
5×1 + 7×2 = 35
5
4
3
2
(7, 0)
1
1
2
3
4
5
6
7
8
9
10
x1
29
Example 1: Graphical Solution
Selected Objective Function Lines
x2
8
7
5×1 + 7×2 = 35
6
5×1 + 7×2 = 39
5
4
5×1 + 7×2 = 42
3
2
1
1
2
3
4
5
6
7
8
9
10
x1
30
Example 1: Graphical Solution
Optimal Solution
x2
Maximum
Objective Function Line
5×1 + 7×2 = 46
8
7
Optimal Solution
(x1 = 5, x2 = 3)
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
x1
31
Summary: Graphical Solution for Maximization
• Prepare a graph of the feasible solutions for each of the
constraints.
• Determine the feasible region that satisfies all the
constraints simultaneously.
• Draw an objective function line.
• Move parallel objective function lines toward larger
objective function values without entirely leaving the
feasible region.
• Any feasible solution on the objective function line with the
largest value is an optimal solution.
32
Slack and Surplus Variables
• A linear program in which all variables are non-negative
and all constraints are expressed as equalities is said to
be in standard form.
• Standard form is attained by adding slack variables to
“less than or equal to” constraints (and by subtracting
surplus variables from “greater than or equal to”
constraints).
• Slack (and surplus) variables represent the difference
between the left and right sides of the constraints.
• Slack (and surplus) variables have objective function
coefficients equal to 0.
33
Example 1: A Simple Maximization Problem
• LP Formulation
Max
s.t.
5×1 + 7×2
x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0
Objective
Function
“Regular”
Constraints
Non-negativity
Constraints
34
Slack Variables (for < constraints) Example 1 in Standard Form Max s.t. 5x1 + 7x2 + 0s1 + 0s2 + 0s3 x1 + s1 = 6 2x1 + 3x2 + s2 = 19 x1 + x2 + s3 = 8 x1, x2 , s1 , s2 , s3 > 0
s1 , s2 , and s3
are slack variables
35
Slack Variables
Optimal Solution
x2
Third
Constraint:
x1 + x2 = 8
8
7
First
Constraint:
x1 = 6
s3 = 0
s1 = 1
6
5
Second
Constraint:
2×1 + 3×2 = 19
4
3
2
1
Optimal
Solution
(x1 = 5, x2 = 3)
1
2
3
4
5
s2 = 0
6
7
8
9
10
x1
36
Extreme Points and the Optimal Solution
• The corners or vertices of the feasible region are referred
to as the extreme points.
• An optimal solution to an LP problem can be found at an
extreme point of the feasible region.
• When looking for the optimal solution, you do not have to
evaluate all feasible solution points.
• You have to consider only the extreme points of the
feasible region.
37
Example 1: Extreme Points
x2
8
7
5 (0, 6.33)
6
5
4
4 (5, 3)
3
Feasible
Region
2
1
3 (6, 2)
2 (6, 0)
1 (0, 0)
1
2
3
4
5
6
7
8
9
10
x1
38
Computer Solutions
• LP problems involving 1000s of variables and 1000s of
constraints are now routinely solved with computer
packages.
• Linear programming solvers are now part of many
spreadsheet packages, such as Microsoft Excel.
• Leading commercial packages include CPLEX, LINGO,
MOSEK, Xpress-MP, and Premium Solver for Excel.
39
Interpretation of Computer Output
• We will discuss the following output:
– Objective function value
– Values of the decision variables
– Reduced costs
– Slack and surplus
• An optimal solution is affected by a change in:
– A coefficient of the objective function
– The right-hand side value of a constraint
40
Example 1: Spreadsheet Solution
Partial Spreadsheet Showing Solution
A
8
9
10
11
12
13
14
15
16
17
B
C
Optimal Decision Variable Values
X1
X2
5.0
3.0
Maximized Objective Function
Constraints
#1
#2
#3
Amount Used
5
19
8
D
46.0
4
x1, x2 > 0
44
Example 2: Graphical Solution
• Graph the Constraints:
– Constraint 1
• When x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5.
Connect (5,0) and (0,2). The “>” side is above this line.
– Constraint 2
• When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2
= -12, which is not on the graph. Thus, to get a second point
on this line, set x1 to any number larger than 3 and solve for
x2: when x1 = 5, then x2 = 8. Connect (3,0) and (5,8). The
“>“ side is to the right.
45
Example 2: Graphical Solution
• Graph the Constraints (continued)
– Constraint 3
• When x1 = 0, then x2 = 4
• When x2 = 0, then x1 = 4.
• Connect (4,0) and (0,4). The “>” side is above this line.
46
Example 2: Graphical Solution
Constraints Graphed
x2
6
Feasible Region
5
4×1 – x2 > 12
4
x1 + x2 > 4
3
2×1 + 5×2 > 10
2
1
x1
1
2
3
4
5
6
47
Example 2: Graphical Solution
• Graph the Objective Function
– Set the objective function equal to an arbitrary constant
(say 20) and graph it. For 5×1 + 2×2 = 20, when x1 = 0,
then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0)
and (0,10).
• Move the Objective Function Line Toward
Optimality
–
Move it in the direction which lowers its value (down),
since we are minimizing, until it touches the last point of
the feasible region, determined by the last two
constraints.
48
Example 2: Graphical Solution
Objective Function Graphed
x2
Min 5×1 + 2×2
6
5
4×1 – x2 > 12
4
x1 + x2 > 4
3
2×1 + 5×2 > 10
2
1
1
2
3
4
5
6
x1
49
Example 2: Graphical Solution
Solve for the Extreme Point at the Intersection of the
Two Binding Constraints
4×1 – x2 = 12
x1+ x2 = 4
Adding these two equations gives:
5×1 = 16 or
x1 = 3.2
Substituting this into x1 + x2 = 4 gives: x2 = 0.8
Solve for the Optimal Value of the Objective
Function
5×1 + 2×2 = 5(3.2) + 2(0.8) = 17.6
50
Example 2: Graphical Solution
Optimal Solution
x2
6
4×1 – x2 > 12
5
x1 + x2 > 4
4
Optimal Solution:
x1 = 3.2, x2 = 0.8,
3
5×1 + 2×2 = 17.6
2
2×1 + 5×2 > 10
1
1
2
3
4
5
6
x1
51
Summary: Graphical Solution for Minimization
• Prepare a graph of the feasible solutions for each of the
constraints.
• Determine the feasible region that satisfies all the
constraints simultaneously.
• Draw an objective function line.
• Move parallel objective function lines toward smaller
objective function values without entirely leaving the
feasible region.
• Any feasible solution on the objective function line with the
smallest value is an optimal solution.
52
Surplus Variables
Example 2 in Standard Form
Min
5×1 + 2×2 + 0s1 + 0s2 + 0s3
s.t.
2×1 + 5×2 – s1 = 10
4×1 – x2 – s2 = 12
x1 + x2 – s3 = 4
s1 , s2 , and s3
> 0
are surplus
variables
x1, x2, s1, s2, s3
53
Example 2: Spreadsheet Solution
Partial Spreadsheet Showing Solution
A
B
C
Decision Variables
X1
X2
3.20
0.800
9
10
11 Dec.Var.Values
12
13
Minimized Objective Function
14
15
Constraints
Amount Used
16
#1
10.4
17
#2
12
18
#3
4
D
17.600
>=
>=
>=
Amount Avail.
10
12
4
54
Example 2: Spreadsheet Solution
Interpretation of Computer Output
We see from the previous slide that:
Objective Function Value = 17.6
Decision Variable #1 (x1) = 3.2
Decision Variable #2 (x2) = 0.8
Surplus in Constraint #1 = 10.4 – 10 = 0.4
Surplus in Constraint #2 = 12.0 – 12 = 0.0
Surplus in Constraint #3 = 4.0 – 4 = 0.0
55
Feasible Region
• The feasible region for a two-variable LP problem can be
nonexistent, a single point, a line, a polygon, or an
unbounded area.
• Any linear program falls into one of four categories:
– Is infeasible
– Has a unique optimal solution
– Has alternative optimal solutions
– Has an objective function that can be increased without bound
• A feasible region may be unbounded and yet there may be
optimal solutions. This is common in minimization
problems and is possible in maximization problems.
56
Special Cases
Alternative Optimal Solutions
In the graphical method, if the objective function line is
parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions, with all
points on this line segment being optimal.
57
Example: Alternative Optimal Solutions
Consider the following LP problem.
Max 4×1 + 6×2
s.t.
x1 < 6 2x1 + 3x2 < 18 x1 + x2 < 7 x1 > 0 and x2 > 0
58
Example: Alternative Optimal Solutions
Boundary constraint 2×1 + 3×2 < 18 and objective function Max 4x1 + 6x2 are parallel. All points on the line segment A – B are optimal solutions. 7 6 5 x2 x1 + x2 < 7 A B 4 x1 < 6 2x1 + 3x2 < 18 3 2 1 1 2 3 4 5 6 7 x1 8 9 10 59 Special Cases • Infeasibility – No solution to the LP problem satisfies all the constraints, including the non-negativity conditions. – Graphically, this means a feasible region does not exist. – Causes include: • A formulation error has been made. • Management’s expectations are too high. • Too many restrictions have been placed on the problem (i.e., the problem is over-constrained). 60 Example: Infeasible Problem Consider the following LP problem: Max 2x1 + 6x2 s.t. 4x1 + 3x2 < 12 2x1 + x2 > 8
x1, x2 >
0
61
Example: Infeasible Problem
There are no points that satisfy both constraints, so there
is no feasible region (and no feasible solution).
x2
10
2×1 + x2 > 8
8
6
4×1 + 3×2 < 12 4 2 2 4 6 8 10 x1 62 Special Cases • Unbounded – The solution to a maximization LP problem is unbounded if the value of the solution may be made indefinitely large without violating any of the constraints. – For real problems, this is the result of improper formulation. (Quite likely, a constraint has been inadvertently omitted.) 63 Example: Unbounded Solution Consider the following LP problem. Max 4x1 + 5x2 s.t. x1 + 3x1 + x2 > 5
x2 > 8
x1, x2 > 0
64
Example: Unbounded Solution
The feasible region is unbounded and the objective
function line can be moved outward from the origin
without bound, infinitely increasing the objective function.
x2
10
3×1 + x2 > 8
8
6
4
x1 + x2 > 5
2
2
4
6
8
10
x1
65
Practice Exercises: Operationalizing the LP
1)
2)
3)
4)
First, an instructor demo of Excel Solver
Second, download the Excel file entitled, “Practice
exercises: Operationalizing linear models”.
Revisit your answers to our earlier exercises (“Practice
exercises: Formulating linear models”) and
operationalize these models in Excel.
Work through the problems as a group and be prepared
to present your problem operationalization.
66
End of Chapter 7
67
Linear Programming
DR JOEL M. EVANS
Housekeeping
• Midterm #1
• Remaining Deliverables
2
Review: Tools of Analysis
Analysis
Purpose
Descriptive statistics
•
What do the data look like?
•
What is the central tendency of the data?
•
How spread out are the data?
•
What is the relationship between two
variables?
•
What value of an input do we need to
achieve a specified value of an output?
•
E.g., break-even point; profit goal
1-way data table
•
How does the value of an outcome change
in response to a range of different values of
an input?
2-way data table
•
How does the value of an outcome change
in response to a range of respective values
for two separate inputs?
Goal seek
3
Review: Tools of Analysis
Analysis
Purpose
Moving averages &
exponential smoothing
•
How might we predict the value of a
variable based on its past values?
Multiple regression
•
How might we predict the value of a
variable based on a set of other variables?
•
Which input variables are significant
predictors of an outcome variable?
•
How does the predictive ability of an input
variable change once we control for other
input variables?
•
What is the equation for modeling these
predictive relationships?
•
Value optimization: What combination of
input values do we need to maximize or
minimize a certain output value, accounting
for certain constraints?
Linear Programming
4
The Textbook
.
.
.
.
.
.
.
.
.
.
.
.
SLIDES BY
John Loucks
St. Edward’s Univ.
Chapter 7
5
Ch 7: Introduction to Linear Programming
•
•
•
•
•
•
•
•
Linear Programming Problem
Problem Formulation
A Simple Maximization Problem
Graphical Solution Procedure
Extreme Points and the Optimal Solution
Computer Solutions
A Simple Minimization Problem
Special Cases
6
Linear Programming
• Linear programming has nothing to do with
computer programming.
• The use of the word “programming” here means
“choosing a course of action.”
7
Mathematical Programming
• Mathematical programming is the development of
modeling and solution procedures which employ
mathematical techniques to optimize the goals and
objectives of the decision-maker.
• Programming problems determine the optimal
allocation of scarce resources to meet certain
objectives.
8
Components of an LP Formation
1)
Decision Variables
–
2)
The things we can control
Objective Function
–
3)
The goal
Constraints
–
4)
Limitations that we cannot control
Non-negativity Conditions
–
Often a natural constraint that is mathematically necessary
9
Decision Variables
• Decision variables represent unknown quantities.
The solution for these terms are what we would
like to optimize.
10
Objective Function
• The objective function states the goal of the decisionmaker. There are two types of objectives:
– Maximization, or
– Minimization
11
Constraints
• Constraints put limitations on the possible solutions of the
problem. The availability of scarce resources may be
expressed as equations or inequalities which rule out
certain combinations of variable values as feasible
solutions.
12
Non-negativity Conditions
• Non-negativity constraints are special constraints which
require all variables to be either zero or positive.
13
Linear Programming (LP) Problem
• A feasible solution satisfies all the problem’s constraints.
• An optimal solution is a feasible solution that results in the
largest possible objective function value when maximizing
(or smallest when minimizing).
• A graphical solution method can be used to solve a linear
program with two variables.
14
Linear Programming (LP) Problem
• If both the objective function and the constraints are linear,
the problem is referred to as a linear programming
problem.
• Linear functions are functions in which each variable
appears in a separate term raised to the first power and is
multiplied by a constant (which could be 0).
• Linear constraints are linear functions that are restricted to
be “less than or equal to”, “equal to”, or “greater than or
equal to” a constant.
15
Problem Formulation
• Problem formulation or modeling is the process of
translating a verbal statement of a problem into a
mathematical statement.
• Formulating models is an art that can only be mastered
with practice and experience.
• Every LP problems has some unique features, but most
problems also have common features.
• General guidelines for LP model formulation are illustrated
on the slides that follow.
16
Guidelines for Model Formulation
•
•
•
•
•
•
Understand the problem thoroughly.
Describe the objective.
Describe each constraint.
Define the decision variables.
Write the objective in terms of the decision variables.
Write the constraints in terms of the decision variables.
17
Redwood Furniture Company
Resource
Wood
Labor
Unit Profit
Unit Requirements
Table
Chair
30
5
6
20
10
8
Amount
Available
300
110
18
Redwood Problem Formulation
Let:
XT = number of tables produced
XC = number of chairs produced
Z = profit
MAX Z = 6 XT + 8 XC
s.t.
(subject to)
where:
30 XT + 20 XC < 300 5 XT + 10 XC < 110 XT, XC > 0
19
Cabinets Problem Formulation
• You need to buy some filing cabinets. You know that:
• -Cabinet X costs $10 per unit, requires six square feet
of floor space, and holds eight cubic feet of files.
• -Cabinet Y costs $20 per unit, requires eight square feet
of floor space, and holds twelve cubic feet of files.
• You have been given $140 for this purchase, though
you don’t have to spend that much. The office has room
for no more than 72 square feet of cabinets. How many
of which model should you buy, in order to maximize
storage volume?
20
Cabinets Problem Formulation
• Maximise z = 8x + 12y
• s.t.
10x + 20y < 140 6x + 8y < 72 (cost) (space) • Non-negativity x>0
y>0
21
Practice Exercises
1)
2)
3)
Go to the Content tab in Blackboard, and navigate to the
Practice Exercises folder.
Find the file called, “Practice exercises: Formulating
linear models”
Work through the problems as a group, and be prepared
to present your problem formulation.
22
Graphical LP Solution Procedure
1)
2)
3)
4)
5)
6)
7)
8)
Formulate the LP problem
Plot the constraints on a graph
Identify the feasible solution region
Plot two objective function lines
Determine the direction of improvement
Find the most attractive corner
Determine the coordinates of the corner
Find the value of the objective function
23
Example 1: A Simple Maximization Problem
• LP Formulation
Max
s.t.
5×1 + 7×2
x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0
Objective
Function
“Regular”
Constraints
Non-negativity
Constraints
24
Example 1: Graphical Solution
• First Constraint Graphed
x2
8
x1 = 6
7
6
5
4
3
Shaded region
contains all
feasible points
for this constraint
2
(6, 0)
1
1
2
3
4
5
6
7
8
9
10
x1
25
Example 1: Graphical Solution
• Second Constraint Graphed
x2
8
(0, 6.33)
7
6
2×1 + 3×2 = 19
5
4
3
2
1
Shaded
region contains
all feasible points
for this constraint
1
2
3
4
5
6
(9.5, 0)
7
8
9
10
x1
26
Example 1: Graphical Solution
• Third Constraint Graphed
x2
(0, 8)
8
7
x1 + x2 = 8
6
5
4
3
2
1
Shaded
region contains
all feasible points
for this constraint
1
2
3
4
5
(8, 0)
6
7
8
9
10
x1
27
Example 1: Graphical Solution
• Combined-Constraint Graph Showing Feasible Region
x2
x1 + x2 = 8
8
7
x1 = 6
6
5
4
3
2×1 + 3×2 = 19
Feasible
Region
2
1
1
2
3
4
5
6
7
8
9
10
x1
28
Example 1: Graphical Solution
• Objective Function Line
x2
8
7
(0, 5)
6
Objective Function
5×1 + 7×2 = 35
5
4
3
2
(7, 0)
1
1
2
3
4
5
6
7
8
9
10
x1
29
Example 1: Graphical Solution
Selected Objective Function Lines
x2
8
7
5×1 + 7×2 = 35
6
5×1 + 7×2 = 39
5
4
5×1 + 7×2 = 42
3
2
1
1
2
3
4
5
6
7
8
9
10
x1
30
Example 1: Graphical Solution
Optimal Solution
x2
Maximum
Objective Function Line
5×1 + 7×2 = 46
8
7
Optimal Solution
(x1 = 5, x2 = 3)
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
x1
31
Summary: Graphical Solution for Maximization
• Prepare a graph of the feasible solutions for each of the
constraints.
• Determine the feasible region that satisfies all the
constraints simultaneously.
• Draw an objective function line.
• Move parallel objective function lines toward larger
objective function values without entirely leaving the
feasible region.
• Any feasible solution on the objective function line with the
largest value is an optimal solution.
32
Slack and Surplus Variables
• A linear program in which all variables are non-negative
and all constraints are expressed as equalities is said to
be in standard form.
• Standard form is attained by adding slack variables to
“less than or equal to” constraints (and by subtracting
surplus variables from “greater than or equal to”
constraints).
• Slack (and surplus) variables represent the difference
between the left and right sides of the constraints.
• Slack (and surplus) variables have objective function
coefficients equal to 0.
33
Example 1: A Simple Maximization Problem
• LP Formulation
Max
s.t.
5×1 + 7×2
x1 < 6 2x1 + 3x2 < 19 x1 + x2 < 8 x1 > 0 and x2 > 0
Objective
Function
“Regular”
Constraints
Non-negativity
Constraints
34
Slack Variables (for < constraints) Example 1 in Standard Form Max s.t. 5x1 + 7x2 + 0s1 + 0s2 + 0s3 x1 + s1 = 6 2x1 + 3x2 + s2 = 19 x1 + x2 + s3 = 8 x1, x2 , s1 , s2 , s3 > 0
s1 , s2 , and s3
are slack variables
35
Slack Variables
Optimal Solution
x2
Third
Constraint:
x1 + x2 = 8
8
7
First
Constraint:
x1 = 6
s3 = 0
s1 = 1
6
5
Second
Constraint:
2×1 + 3×2 = 19
4
3
2
1
Optimal
Solution
(x1 = 5, x2 = 3)
1
2
3
4
5
s2 = 0
6
7
8
9
10
x1
36
Extreme Points and the Optimal Solution
• The corners or vertices of the feasible region are referred
to as the extreme points.
• An optimal solution to an LP problem can be found at an
extreme point of the feasible region.
• When looking for the optimal solution, you do not have to
evaluate all feasible solution points.
• You have to consider only the extreme points of the
feasible region.
37
Example 1: Extreme Points
x2
8
7
5 (0, 6.33)
6
5
4
4 (5, 3)
3
Feasible
Region
2
1
3 (6, 2)
2 (6, 0)
1 (0, 0)
1
2
3
4
5
6
7
8
9
10
x1
38
Computer Solutions
• LP problems involving 1000s of variables and 1000s of
constraints are now routinely solved with computer
packages.
• Linear programming solvers are now part of many
spreadsheet packages, such as Microsoft Excel.
• Leading commercial packages include CPLEX, LINGO,
MOSEK, Xpress-MP, and Premium Solver for Excel.
39
Interpretation of Computer Output
• We will discuss the following output:
– Objective function value
– Values of the decision variables
– Reduced costs
– Slack and surplus
• An optimal solution is affected by a change in:
– A coefficient of the objective function
– The right-hand side value of a constraint
40
Example 1: Spreadsheet Solution
Partial Spreadsheet Showing Solution
A
8
9
10
11
12
13
14
15
16
17
B
C
Optimal Decision Variable Values
X1
X2
5.0
3.0
Maximized Objective Function
Constraints
#1
#2
#3
Amount Used
5
19
8
D
46.0
4
x1, x2 > 0
44
Example 2: Graphical Solution
• Graph the Constraints:
– Constraint 1
• When x1 = 0, then x2 = 2; when x2 = 0, then x1 = 5.
Connect (5,0) and (0,2). The “>” side is above this line.
– Constraint 2
• When x2 = 0, then x1 = 3. But setting x1 to 0 will yield x2
= -12, which is not on the graph. Thus, to get a second point
on this line, set x1 to any number larger than 3 and solve for
x2: when x1 = 5, then x2 = 8. Connect (3,0) and (5,8). The
“>“ side is to the right.
45
Example 2: Graphical Solution
• Graph the Constraints (continued)
– Constraint 3
• When x1 = 0, then x2 = 4
• When x2 = 0, then x1 = 4.
• Connect (4,0) and (0,4). The “>” side is above this line.
46
Example 2: Graphical Solution
Constraints Graphed
x2
6
Feasible Region
5
4×1 – x2 > 12
4
x1 + x2 > 4
3
2×1 + 5×2 > 10
2
1
x1
1
2
3
4
5
6
47
Example 2: Graphical Solution
• Graph the Objective Function
– Set the objective function equal to an arbitrary constant
(say 20) and graph it. For 5×1 + 2×2 = 20, when x1 = 0,
then x2 = 10; when x2= 0, then x1 = 4. Connect (4,0)
and (0,10).
• Move the Objective Function Line Toward
Optimality
–
Move it in the direction which lowers its value (down),
since we are minimizing, until it touches the last point of
the feasible region, determined by the last two
constraints.
48
Example 2: Graphical Solution
Objective Function Graphed
x2
Min 5×1 + 2×2
6
5
4×1 – x2 > 12
4
x1 + x2 > 4
3
2×1 + 5×2 > 10
2
1
1
2
3
4
5
6
x1
49
Example 2: Graphical Solution
Solve for the Extreme Point at the Intersection of the
Two Binding Constraints
4×1 – x2 = 12
x1+ x2 = 4
Adding these two equations gives:
5×1 = 16 or
x1 = 3.2
Substituting this into x1 + x2 = 4 gives: x2 = 0.8
Solve for the Optimal Value of the Objective
Function
5×1 + 2×2 = 5(3.2) + 2(0.8) = 17.6
50
Example 2: Graphical Solution
Optimal Solution
x2
6
4×1 – x2 > 12
5
x1 + x2 > 4
4
Optimal Solution:
x1 = 3.2, x2 = 0.8,
3
5×1 + 2×2 = 17.6
2
2×1 + 5×2 > 10
1
1
2
3
4
5
6
x1
51
Summary: Graphical Solution for Minimization
• Prepare a graph of the feasible solutions for each of the
constraints.
• Determine the feasible region that satisfies all the
constraints simultaneously.
• Draw an objective function line.
• Move parallel objective function lines toward smaller
objective function values without entirely leaving the
feasible region.
• Any feasible solution on the objective function line with the
smallest value is an optimal solution.
52
Surplus Variables
Example 2 in Standard Form
Min
5×1 + 2×2 + 0s1 + 0s2 + 0s3
s.t.
2×1 + 5×2 – s1 = 10
4×1 – x2 – s2 = 12
x1 + x2 – s3 = 4
s1 , s2 , and s3
> 0
are surplus
variables
x1, x2, s1, s2, s3
53
Example 2: Spreadsheet Solution
Partial Spreadsheet Showing Solution
A
B
C
Decision Variables
X1
X2
3.20
0.800
9
10
11 Dec.Var.Values
12
13
Minimized Objective Function
14
15
Constraints
Amount Used
16
#1
10.4
17
#2
12
18
#3
4
D
17.600
>=
>=
>=
Amount Avail.
10
12
4
54
Example 2: Spreadsheet Solution
Interpretation of Computer Output
We see from the previous slide that:
Objective Function Value = 17.6
Decision Variable #1 (x1) = 3.2
Decision Variable #2 (x2) = 0.8
Surplus in Constraint #1 = 10.4 – 10 = 0.4
Surplus in Constraint #2 = 12.0 – 12 = 0.0
Surplus in Constraint #3 = 4.0 – 4 = 0.0
55
Feasible Region
• The feasible region for a two-variable LP problem can be
nonexistent, a single point, a line, a polygon, or an
unbounded area.
• Any linear program falls into one of four categories:
– Is infeasible
– Has a unique optimal solution
– Has alternative optimal solutions
– Has an objective function that can be increased without bound
• A feasible region may be unbounded and yet there may be
optimal solutions. This is common in minimization
problems and is possible in maximization problems.
56
Special Cases
Alternative Optimal Solutions
In the graphical method, if the objective function line is
parallel to a boundary constraint in the direction of
optimization, there are alternate optimal solutions, with all
points on this line segment being optimal.
57
Example: Alternative Optimal Solutions
Consider the following LP problem.
Max 4×1 + 6×2
s.t.
x1 < 6 2x1 + 3x2 < 18 x1 + x2 < 7 x1 > 0 and x2 > 0
58
Example: Alternative Optimal Solutions
Boundary constraint 2×1 + 3×2 < 18 and objective function Max 4x1 + 6x2 are parallel. All points on the line segment A – B are optimal solutions. 7 6 5 x2 x1 + x2 < 7 A B 4 x1 < 6 2x1 + 3x2 < 18 3 2 1 1 2 3 4 5 6 7 x1 8 9 10 59 Special Cases • Infeasibility – No solution to the LP problem satisfies all the constraints, including the non-negativity conditions. – Graphically, this means a feasible region does not exist. – Causes include: • A formulation error has been made. • Management’s expectations are too high. • Too many restrictions have been placed on the problem (i.e., the problem is over-constrained). 60 Example: Infeasible Problem Consider the following LP problem: Max 2x1 + 6x2 s.t. 4x1 + 3x2 < 12 2x1 + x2 > 8
x1, x2 >
0
61
Example: Infeasible Problem
There are no points that satisfy both constraints, so there
is no feasible region (and no feasible solution).
x2
10
2×1 + x2 > 8
8
6
4×1 + 3×2 < 12 4 2 2 4 6 8 10 x1 62 Special Cases • Unbounded – The solution to a maximization LP problem is unbounded if the value of the solution may be made indefinitely large without violating any of the constraints. – For real problems, this is the result of improper formulation. (Quite likely, a constraint has been inadvertently omitted.) 63 Example: Unbounded Solution Consider the following LP problem. Max 4x1 + 5x2 s.t. x1 + 3x1 + x2 > 5
x2 > 8
x1, x2 > 0
64
Example: Unbounded Solution
The feasible region is unbounded and the objective
function line can be moved outward from the origin
without bound, infinitely increasing the objective function.
x2
10
3×1 + x2 > 8
8
6
4
x1 + x2 > 5
2
2
4
6
8
10
x1
65
Practice Exercises: Operationalizing the LP
1)
2)
3)
4)
First, an instructor demo of Excel Solver
Second, download the Excel file entitled, “Practice
exercises: Operationalizing linear models”.
Revisit your answers to our earlier exercises (“Practice
exercises: Formulating linear models”) and
operationalize these models in Excel.
Work through the problems as a group and be prepared
to present your problem operationalization.
66
End of Chapter 7
67
In-class Practice Exercises: Formulating a Linear Programming Model
Problem #1
Embassy Motorcycles (EM) manufacturers two lightweight motorcycles designed for easy handling and safety. The K250 model
has a new engine and a low profile that make it easy to balance. The QX-500 model is slightly larger, uses a more traditional
engine, and is specifically designed to appeal to women riders. Embassy produces the engines for both models at its Jeddah
plant. Each K250 engine requires 6 hours of manufacturing time and each QX-500 engine requires 3 hours of manufacturing
time. The Jeddah plant has 2100 hours of engine manufacturing time available for the next production period. Embassy’s
motorcycle frame supplier can supply as many K250 frames as needed. However, the QX-500 frame is more complex and the
supplier can only provide up to 280 QX-500 frames for the next production period. Final assembly and testing requires 2 hours
for each K250 model and 2.5 hours for each QX-500 model. A maximum of 1000 hours of assembly and testing time are
available for the next production period. The company’s accounting department projects a profit contribution of $2400 for each
K250 produced and $1800 for each QX-500 produced.
Formulate a linear programming model that can be used to determine the number of units of each model that should be
produced in order to maximize the total contribution to profit.
Embassy Motorcycles (EM) Manufacturers Data:
Model
Manufacturing time
Production quantity
Assembly & testing time
Profit
Embassy Motorcycles
K250
QX-500
6 hours
3 hours
?
280
2 hours
2.5 hours
$2400
$1800
X = K250
Y = QX 500
How much to produce to Maximizing the profit
Max z = 2400 X + 1800 Y
Subjective too (constraints)
St = 6 X + 3 Y ≤ 2100 Manufactures
St = 2 X + 2.5 Y ≤ 1000 Testing
St = Y ≥ 280 Frames
Non negativity
X≥0
Y≥0
Amount
2100 hours
?
1000 hours
X&Y
Problem #2
Mohammed recently inherited a large sum of money; he wants to use a portion of this money to set up
a trust fund for his two children. The trust fund has two investment options: (1) a bond fund and (2) a
stock fund. The projected returns over the life of the investments are 6% for the bond fund and 10% for
the stock fund. Whatever portion of the inheritance Mohammed finally decides to commit to the trust
fund, he wants to invest at least 30% of that amount in the bond fund. In addition, he wants to select a
mix that will enable him to obtain a total return of at least 7.5%.
Formulate a linear programming model that can be used to determine the percentage that should be
allocated to each of the possible investment alternatives.
Problem #3
Blue Ocean Restaurant would like to determine the best way to allocate a monthly advertising budget of
SAR 4,000 between poster advertising and online advertising. Management decided that at least 25% of
the budget must be spent on each type of media, and that the amount of money spent on local poster
advertising must be at least twice the amount spent on online advertising. A marketing consultant
developed an index that measures audience exposure per dollar of advertising on a scale from 0 to 100,
with higher values implying greater audience exposure. If the value of the index for local poster
advertising is 50 and the value of the index for online advertising is 80, how should the restaurant
allocate its advertising budget in order to maximize the value of total audience exposure?
Formulate a linear programming model that can be used to determine how the restaurant should
allocate its advertising budget in order to maximize the value of total audience exposure.