Optimization

Optimization
Session 1: Introduction to Optimization and LP

April 13, 2024

Optimization

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization

Learning objectives

1. To recognize an optimization problem and identify the key

issues.
2. To model a business problem using mathematical
modelling techniques.
3. Formulate business decision (optimization) problems using
Excel Spreadsheet.
4. Evaluate and analyse the solution; and answer the“what if”
questions.
5. Compare various optimization problem types (Linear
versus Integer).
Optimization
Introduction

Introduction

I We face numerous decisions in life and business.

I We can use computers to analyze the potential outcomes
of decision alternatives.
I Spreadsheets are the tool of choice for today’s managers.
Optimization
Introduction

Business Analytics

I A field of study that uses computers, statistics, and

mathematics to solve business problems1 . Also known as:
I Management Science
I Operations research
I Decision science
I Each year, the Institute For Operations Research and
Management Science (INFORMS) sponsors the Franz
Edelman Awards competition to recognize some of the
most outstanding OR/MS ( Business Analytics) projects in
the past year.

1
as defined in CTR
Optimization
Introduction

Types of Business Analytics

Descriptive Diagnostic Predictive Prescriptive

Analytics Analytics Analytics Analytics

Identifies reasons Forecasts future Recommends actions

Summarizes historical
for past outcomes outcomes based on to achieve desired
data to answer
to answer "why historical data and outcomes based on
"what happened?"
did it happen?" current trends analysis results
Optimization
Introduction
Applications

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Introduction
Applications

Fedex Story-Logistical Planning of Shipments

I Logistical Challenge2 : Millions of daily shipments must be

individually sorted and routed to the correct general
location(usually by aircraft) and then delivered to the exact
location(usually by motorized vehicle)in an amazingly short
period of time.

2
R.O. Mason, J.L. McKenney, W. Carlson, and D. Copeland, “Absolutely,
Positively Operations Research: The Federal Express Story,” Interfaces 27,
no. 2 (March-April 1997), pp. 17-36.
Optimization
Introduction
Applications

Swift & Company

I Swift & Company3 , a beef meat packing plant.
I Three challenges:
I Enable CSR’s to talk to more than 8000 customers with
accurate information.
I Produce an efficient shift-level schedule for each plant over
a 28- day horizon.
I To determine whether a plant can ship a requested order
quantity on the requested date and time given the
availability of cattle and constraints on plant’s capacity.
I Developed an integrated system of 45 linear programming
models to schedule operations.
I Audited benefits reported: Annual Savings of $12.74
million in the first year of operation.
3
A. Bixby, B. Downs, and M. Self, “A Scheduling and Capable to-Promise
Application for Swift & Company”, Interfaces 36, no. 1 (January-February
2006), pp. 69-86.
Optimization
Introduction
Applications

Xerox

I Xerox 4 developed “Lean Document Production” solutions

for the printing industry.
I Provides productivity and cost improvements for print
shops.
I Benefits:
I $200 million in incremental profit for customers
I 20% - 40% productivity increase

4
Sudhendu Rai, Charles B. Duke, Vaughn Lowe, Cyndi Quan-Trotter and
Thomas Scheermesser; “ LDP Lean Document Production-O.R.-Enhanced
Productivity Improvements for the Printing Industry” Interfaces, Vol. 39, No. 1,
2008.
Optimization
Introduction
Applications

StatOilHydro
I The network for transport of natural gas on the Norwegian
Continental Shelf, with 7,800 km of subsea pipelines, is the
world’s largest offshore pipeline network
I StatOilHydro5 Primary supplier of natural gas in Norway
I Developed GassOpt tool for optimizing operation of world’s
largest offshore pipeline
I GassOpt allows users to graphically model their network
and run optimizations to find the best solutions quickly.
I Benefits:
I Accumulated savings of US $2 billion through 2008

5
Romo, Frode, Asgeir Tomasgard, Lars Hellemo, Marte Fodstad, Bjorgulf
Haukelidsater Eidesen, and Birger Pedersen. “Optimizing the Norwegian
natural gas production and transport.” Interfaces 39, no. 1 (2009)
Optimization
Introduction
Applications

US Federal Aviation Administration(FAA)

I Responsible for air traffic management 6

I Large-scale weather systems reduce available air space
I Developed Airspace Flow Programs to optimize ground
delays for each individual flight when weather
compromises flight routes
I Benefits:
I Saved airlines $190 million in first 2-years of use

6
Ved P. Sud, Midori Tanino, James Wetherly, Michael Brennan, Miro
Lehky, Ken Howard and Rick Oiesen; “Reducing Flight Delays through Better
Traffic Management” Interfaces, Vol. 39, No. 1, 2008.
Optimization
Introduction
Applications

Netherland Railways
I In December 2006, Netherlands Railways7 introduced a
completely new timetable. Its objective was to facilitate the
growth of passenger and freight transport on a highly
utilized railway network and improve the robustness of the
timetable, thus resulting in fewer operational train delays
I Developed system to optimize 5,500 daily trains routes
I Creates efficient crew & rolling stock schedules
I Benefits:
I Increased profit by 40 million Euros
I Improved on-time arrivals

7
Leo Kroon, Dennis Huisman, Erwin Abbink, Pieter-Jan Fioole, Matteo
Fischetti, Gábor Maróti, Alexander Schrijver, Adri Steenbeek, and Roelof
Ybema; “The New Dutch Timetable: The OR Revolution” Interfaces Vol. 39:1
, 2009
Optimization
Introduction
Modeling approach

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Introduction
Modeling approach

What is a “Computer model”?

I A set of mathematical relationships and logical

assumptions implemented in a computer as an abstract
representation of a real-world object of phenomenon.
I Spreadsheets provide the most convenient way for
business people to build computer models.
Optimization
Introduction
Modeling approach

Mathematical model
I Mathematical models usually describe functional
relationships. For example,
I Consider
Profit = Revenue − Expenses
Optimization
Introduction
Modeling approach

Mathematical model
I Mathematical models usually describe functional
relationships. For example,
I Consider
Profit = Revenue − Expenses

I Using symbols of mathematics, this can be described as a

functional relationship between revenue, expenses and
profit.
Profit = f (Revenue, Expenses)
Optimization
Introduction
Modeling approach

Mathematical model
I Mathematical models usually describe functional
relationships. For example,
I Consider
Profit = Revenue − Expenses

I Using symbols of mathematics, this can be described as a

functional relationship between revenue, expenses and
profit.
Profit = f (Revenue, Expenses)

I Profit is dependent variable represented by Y ; Revenue

and Expenses are independent variables represented by
X1 and X2 . Mathematical form of representation
Y = f (X1 , X2 )
Optimization
Linear Programming

Introduction to Mathematical Programming

We all face decision about how to use limited resources such

as:
I Oil in the earth
I Land for dumps
I Time
I Money
I Workers
Optimization
Linear Programming

Introduction to Mathematical Programming

We all face decision about how to use limited resources such

as:
I Oil in the earth
I Land for dumps
I Time
I Money
I Workers
Mathematical Programming is a field of management science
that finds the optimal, or most efficient, way of using limited
resources to achieve the objectives of an individual of a
business. a.k.a Optimization
Optimization
Linear Programming

Applications of optimization

I Resource- Allocation Problems.

I Cost-Benefit Trade-Off problems.
I Make vs Buy Decisions
I Investment Problem
I Transportation and Assignment problems
I Production Planning problem
I Multiperiod- cash flow problem
Optimization
Linear Programming

Characteristics of optimization problems

Optimization
Linear Programming

Characteristics of optimization problems

I Decisions: The decisions in an optimization problem are

represented by X1 , X2 , . . . , Xn . They might represent
production quantities, amount to invest, etc.
Optimization
Linear Programming

Characteristics of optimization problems

I Decisions: The decisions in an optimization problem are

represented by X1 , X2 , . . . , Xn . They might represent
production quantities, amount to invest, etc.
I Objective: The objective function identifies some function
of the decision variables that the decision maker wants to
either maximize or minimize.
Optimization
Linear Programming

Characteristics of optimization problems

I Decisions: The decisions in an optimization problem are

represented by X1 , X2 , . . . , Xn . They might represent
production quantities, amount to invest, etc.
I Objective: The objective function identifies some function
of the decision variables that the decision maker wants to
either maximize or minimize.
I Constraints: Three general ways to represent a constraint
relationship:
Optimization
Linear Programming

Characteristics of optimization problems

I Decisions: The decisions in an optimization problem are

represented by X1 , X2 , . . . , Xn . They might represent
production quantities, amount to invest, etc.
I Objective: The objective function identifies some function
of the decision variables that the decision maker wants to
either maximize or minimize.
I Constraints: Three general ways to represent a constraint
relationship:
I A less than or equal to constraint - captures “at most”
I A greater than or equal to constraint- captures “ at least ”
I An equal to constraint.
Optimization
Linear Programming
Formulating linear programming models

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Linear Programming
Formulating linear programming models

Example: Blue Ridge Hot Tubs

I Blue Ridge Hot Tubs8 produces two types of hot tubs:

Aqua-Spas & Hydro-Luxes
Aqua-Spa Hydro-Lux
Pumps 1 1
Labor 9 hours 6 hours
Tubing 12 feet 16 feet
Unit Profit $350 $300

8
Reference: CTR Chapter 2
Optimization
Linear Programming
Formulating linear programming models

Example: Blue Ridge Hot Tubs

I Blue Ridge Hot Tubs8 produces two types of hot tubs:

Aqua-Spas & Hydro-Luxes
Aqua-Spa Hydro-Lux
Pumps 1 1
Labor 9 hours 6 hours
Tubing 12 feet 16 feet
Unit Profit $350 $300
I There are 200 pumps, 1566 hours of labor, and 2880 feet
of tubing available.

8
Reference: CTR Chapter 2
Optimization
Linear Programming
Formulating linear programming models

Steps in formulating an LP Model

1. Understand the problem.

2. Identify the decision variables.
3. State the objective function as a function of the decision
variables.
4. State the constraints as a function of the decision
variables.
5. Identify any upper or lower bounds on the decision
variables.
Optimization
Linear Programming
Formulating linear programming models

1. Understand the problem.

2. Identify the decision variables.
I X1 : number of Aqua-Spas to produce
I X2 : number of Hydro-Luxes to produce
3. State the objective function as a linear combination of the
decision variables.
I Maximize 350X1 + 300X2
4. State the constraints as linear combinations of the decision
variables.
I Pumps constraint: X1 + X2 ≤ 200
I Labor constraint : 9X1 + 6X2 ≤ 1566
I Tubing constraint: 12X1 + 16X2 ≤ 2880
5. Identify any upper or lower bounds on the decision
variables.
I X1 , X2 ≥ 0 (Impossible to produce a negative number of hot
tubs)
Optimization
Linear Programming
Formulating linear programming models

Basic assumptions of linear programming

1. Proportionality
2. Additivity
3. Continuity
4. Certainty
Optimization
Linear Programming
Formulating linear programming models

Assumptions of linear programming

I Proportionality:
The basic assumption underlying the linear programming
is that any change in the constraint inequalities will have
the proportional change in the objective function. This
means, if product contributes Rs 20 towards the profit, then
the total contribution would be equal to 20 × x1 , where x1 is
the number of units of the product
Optimization
Linear Programming
Formulating linear programming models

Assumptions of linear programming

I Additivity:
I The assumption of additivity asserts that the total profit of
the objective function is determined by the sum of profit
contributed by each product separately. Similarly, the total
amount of resources used is determined by the sum of
resources used by each product separately.
I This implies, there is no interaction between the decision
variables.
Optimization
Linear Programming
Formulating linear programming models

Assumptions of linear programming

I Continuity:
I The decision variables are continuous.
I This means a combination of outputs can be used with the
fractional values along with the integer values.
Optimization
Linear Programming
Formulating linear programming models

Assumptions of linear programming

I Certainty:
I The parameters of objective function coefficients and the
coefficients of constraint inequalities is known with certainty.
Optimization
Linear Programming
Formulating linear programming models

LP model

Maximize 350X1 + 300X2

Subject to X1 + X2 ≤ 200
9X1 + 6X2 ≤ 1566
12X1 + 16X2 ≤ 2880
X1 , X2 ≥ 0
Optimization
Linear Programming
Formulating linear programming models

LP model

Maximize 350X1 + 300X2

Subject to X1 + X2 ≤ 200
9X1 + 6X2 ≤ 1566
12X1 + 16X2 ≤ 2880
X1 , X2 ≥ 0

Goal: To determine the values for X1 and X2 that maximize the

objective 350X1 + 300X2 while simultaneously satisfying all
constraints.
Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
I How many would that be?
I Let X2 = 0
Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
I How many would that be?
I Let X2 = 0

X1 ≤ 200
 9X1 ≤ 1566
12X1 ≤ 2880
Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
I How many would that be?
I Let X2 = 0
 
X1 ≤ 200 
 9X1 ≤ 1566 =⇒ X1 ≤ 174
12X1 ≤ 2880

Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
I How many would that be?
I Let X2 = 0
 
X1 ≤ 200 
 9X1 ≤ 1566 =⇒ X1 ≤ 174
12X1 ≤ 2880

I If X2 = 0, the maximum value of X1 is 174 and the total
profit is $350 × 174 + $300 × 0 = $60, 900.
Optimization
Solving LP problems

Solving LP Problems: An intuitive approach

I Idea: Each Aqua-Spa (X1 ) generates the highest unit profit

($350), so let’s make as many of them as possible.
I How many would that be?
I Let X2 = 0
 
X1 ≤ 200 
 9X1 ≤ 1566 =⇒ X1 ≤ 174
12X1 ≤ 2880

I If X2 = 0, the maximum value of X1 is 174 and the total
profit is $350 × 174 + $300 × 0 = $60, 900.
I This solution is feasible, but is it optimal?
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Solving LP problems: A graphical approach

I The constraints of an LP problem defines its feasible

region.
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Solving LP problems: A graphical approach

I The constraints of an LP problem defines its feasible

region.
I The best point in the feasible region is the optimal solution
to the problem.
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Solving LP problems: A graphical approach

I The constraints of an LP problem defines its feasible

region.
I The best point in the feasible region is the optimal solution
to the problem.
I For LP problems with 2 variables, it is easy to plot the
feasible region and find the optimal solution.
Implementing the Model- File: Blue Ridge_1.xlsm
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Feasible Region
x2

x1
x1 + x2 = 200
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Calculating the optimal solution

I The optimal solution occurs where the “pumps” and “labor”

constraints intersect.
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Calculating the optimal solution

I The optimal solution occurs where the “pumps” and “labor”

constraints intersect.
I This occurs where:
 
X1 + X2 = 200
=⇒ X1 = 122, X2 = 78
9X1 + 6X2 = 1566
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Calculating the optimal solution

I The optimal solution occurs where the “pumps” and “labor”

constraints intersect.
I This occurs where:
 
X1 + X2 = 200
=⇒ X1 = 122, X2 = 78
9X1 + 6X2 = 1566
I So the optimal solution is,X1 = 122, X2 = 78 realizing a
profit of 350 × 122 + 300 × 78 = 66, 100.
Optimization
Solving LP problems
Solving LP problems: A graphical approach

Enumerating The corner points

Optimization
Solving LP problems
Solving LP problems: A graphical approach

Enumerating The corner points

Note: This technique will not work if the solution is unbounded.

Optimization
Solving LP problems
Solving LP problems: A graphical approach

Summary of graphical solution to LP problems

1. Plot the boundary line of each constraint

2. Identify the feasible region
3. Locate the optimal solution by either:
a. Plotting level curves
b. Enumerating the extreme points
Optimization
Solving LP problems
Simplex method

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Solving LP problems
Simplex method

Simplex method

I To use the simplex method, we first convert all inequalities

to equalities by adding slack variables to ≤ constraints and
subtracting surplus variables from ≥ constraints.

For example ai1 X1 + ai2 X2 + . . . + ain Xn ≤ bi

converts to ai1 X1 + ai2 X2 + . . . + ain Xn + si = bi

And ai1 X1 + ai2 X2 + . . . + ain Xn ≥ bi

converts to ai1 X1 + ai2 X2 + . . . + ain Xn − si = bi
Optimization
Solving LP problems
Simplex method

For Blue Ridge Hot Tubs Example

I Standard form of LP
0
Maximize c x
Subject to Ax = b
x ≥0
I Example
Maximize 350X1 + 300X2
Subject to X1 + X2 + s1 = 200
9X1 + 6X2 + s2 = 1566
12X1 + 16X2 + s3 = 2880
X1 , X2 , s1 , s2 , s3 ≥ 0
Optimization
Solving LP problems
Simplex method

Basic feasible solutions

I If there are n variables in a system of m equations (where

n > m) we can select any m variables and solve the
equations (setting the remaining n − m variables to zero.)
Optimization
Solving LP problems
Simplex method

Basic feasible solutions

I If there are n variables in a system of m equations (where

n > m) we can select any m variables and solve the
equations (setting the remaining n − m variables to zero.)
I The solution XB = B −1 b, XN = 0 is a basic feasible solution
to the system of equations.
Optimization
Solving LP problems
Simplex method

Basic feasible solutions

I If there are n variables in a system of m equations (where

n > m) we can select any m variables and solve the
equations (setting the remaining n − m variables to zero.)
I The solution XB = B −1 b, XN = 0 is a basic feasible solution
to the system of equations.
I { Basic Feasible Solutions} ⇐⇒ {Extreme points}
Optimization
Solving LP problems
Simplex method

Possible Basic feasible solutions

Optimization
Solving LP problems
Simplex method

Basic Feasible Solutions & Extreme Points

Optimization
Solving LP problems
Simplex method

Simplex method

I Identify any basic feasible solution (or extreme point) for an

LP problem, then moving to an adjacent extreme point if
such a move improves the value of the objective function.
Optimization
Solving LP problems
Simplex method

Simplex method

I Identify any basic feasible solution (or extreme point) for an

LP problem, then moving to an adjacent extreme point if
such a move improves the value of the objective function.
I Moving from one extreme point to an adjacent one occurs
by switching one of the basic variables with one of the
nonbasic variables to create a new basic feasible solution
(for an adjacent extreme point).
Optimization
Solving LP problems
Simplex method

Simplex method

I Identify any basic feasible solution (or extreme point) for an

LP problem, then moving to an adjacent extreme point if
such a move improves the value of the objective function.
I Moving from one extreme point to an adjacent one occurs
by switching one of the basic variables with one of the
nonbasic variables to create a new basic feasible solution
(for an adjacent extreme point).
I When no adjacent extreme point has a better objective
function value, stop – the current extreme point is optimal.
Optimization
Solving LP problems
Special conditions in LP models

Outline
Introduction
Applications
Modeling approach
Linear Programming
Formulating linear programming models
Basic assumptions of linear programming

Solving LP problems
Solving LP problems: A graphical approach
Simplex method
Special conditions in LP models
Solving LP problems in a spreadsheet
Understanding LP and how things change
Optimization
Solving LP problems
Special conditions in LP models

Special conditions in LP models

A number of anomalies can occur in LP problems:

I Alternate Optimal Solutions
I Redundant Constraints
I Unbounded Solutions
I Infeasibility
Optimization
Solving LP problems
Special conditions in LP models

Alternate optimal solutions

Optimization
Solving LP problems
Special conditions in LP models

Redundant constraints
Optimization
Solving LP problems
Special conditions in LP models

Unbounded solutions
Optimization
Solving LP problems
Special conditions in LP models

Infeasibility
Optimization
Solving LP problems
Special conditions in LP models

Properties of Linear Programming solutions

I An optimal solution must lie on the boundary of the feasible
region.
I There are exactly four possible outcomes of linear
programming:
I A unique optimal solution is found.
I An infinite number of optimal solutions exist.(Alternate
Optima)
I The objective function is unbounded (there is no optimal
solution).
I No feasible solutions exist.(Infeasibility)
I If an LP model has one optimal solution, it must be at a
corner point.
I If an LP model has many optimal solutions, at least two of
these optimal solutions are at corner points.
Optimization
Solving LP problems in a spreadsheet

The steps in implementing an LP Model in a

spreadsheet

1. Organize the data for the model on the spreadsheet.

2. Reserve separate cells in the spreadsheet for each
decision variable in the model.
3. Create a formula in a cell in the spreadsheet that
corresponds to the objective function.
4. For each constraint, create a formula in a separate cell in
the spreadsheet that corresponds to the left-hand side
(LHS) of the constraint.
Implementing the Model- File: Blue Ridge_2.xlsm
Optimization
Solving LP problems in a spreadsheet

How Solver views the model

I Objective cell - the cell in the spreadsheet that represents

the objective function
I Variable cells - the cells in the spreadsheet representing
the decision variables
I Constraint cells - the cells in the spreadsheet representing
the LHS formulas on the constraints
Optimization
Understanding LP and how things change

Understanding how things change

I It is important to realize that if changes occur in any of the

coefficients in the objective function or constraints of the
problem, then the level curve, the feasible region, and the
optimal solution to the problem might also change.
Implementing the Model- File: Blue Ridge_1.xlsm
Optimization
Understanding LP and how things change

A few questions

1. In the optimal solution to this problem, how many pumps,

hours of labor, and feet of tubing are being used?
Optimization
Understanding LP and how things change

A few questions

1. In the optimal solution to this problem, how many pumps,

hours of labor, and feet of tubing are being used?
I 200 pumps, 1566 labor hours, 2712 feet of tubing.
Optimization
Understanding LP and how things change

A few questions

1. In the optimal solution to this problem, how many pumps,

hours of labor, and feet of tubing are being used?
I 200 pumps, 1566 labor hours, 2712 feet of tubing.
2. If possible, should the company increase the number of
pumps available? Why or why not? And if so, what is the
maximum number of additional pumps the company should
consider acquiring and by how much would this increase
profit?
Optimization
Understanding LP and how things change

A few questions

1. In the optimal solution to this problem, how many pumps,

hours of labor, and feet of tubing are being used?
I 200 pumps, 1566 labor hours, 2712 feet of tubing.
2. If possible, should the company increase the number of
pumps available? Why or why not? And if so, what is the
maximum number of additional pumps the company should
consider acquiring and by how much would this increase
profit?
I Pumps are a binding constraint and should be increased to
207, if possible. This would increase profits by $1,400 to
$67,500.
Optimization
Understanding LP and how things change

A few questions- Continued

3. If possible, should the company acquire more labor hours?

Why or why not? If so, how much additional labor should
the company consider acquiring and by how much would
this increase profit?
Optimization
Understanding LP and how things change

A few questions- Continued

3. If possible, should the company acquire more labor hours?

Why or why not? If so, how much additional labor should
the company consider acquiring and by how much would
this increase profit?
I Labor is a binding constraint and should be increased to
1800, if possible. This would increase profits by $3900 to
$70000.
Optimization
Understanding LP and how things change

A few questions- Continued

3. If possible, should the company acquire more labor hours?

Why or why not? If so, how much additional labor should
the company consider acquiring and by how much would
this increase profit?
I Labor is a binding constraint and should be increased to
1800, if possible. This would increase profits by $3900 to
$70000.
4. If possible, should the company acquire more tubing? Why
or why not? If so, how much additional tubing should the
company consider acquiring and by how much would this
increase profit?
Optimization
Understanding LP and how things change

A few questions- Continued

3. If possible, should the company acquire more labor hours?

Why or why not? If so, how much additional labor should
the company consider acquiring and by how much would
this increase profit?
I Labor is a binding constraint and should be increased to
1800, if possible. This would increase profits by $3900 to
$70000.
4. If possible, should the company acquire more tubing? Why
or why not? If so, how much additional tubing should the
company consider acquiring and by how much would this
increase profit?
I Tubing is a non-binding constraint. They have already got
more than they can use and do not need any more.
Optimization
Understanding LP and how things change

A few questions- Continued

5. By how much would profit increase if the company could

reduce the labor required to produce Aqua-spas from 9 to
8 hours? From 8 to 7 hours? From 7 to 6 Hours?
Optimization
Understanding LP and how things change

A few questions- Continued

5. By how much would profit increase if the company could

reduce the labor required to produce Aqua-spas from 9 to
8 hours? From 8 to 7 hours? From 7 to 6 Hours?
I 9 to 8: profit increases by $3,050
I 8 to 7: profit increases by $850
I 7 to 6: profit increases by $0
Optimization
Understanding LP and how things change

A few questions- Continued

5. By how much would profit increase if the company could

reduce the labor required to produce Aqua-spas from 9 to
8 hours? From 8 to 7 hours? From 7 to 6 Hours?
I 9 to 8: profit increases by $3,050
I 8 to 7: profit increases by $850
I 7 to 6: profit increases by $0
6. By how much would profit increase if the company could
reduce the labor required to produce Hydro-Luxes from 6
to 5 hours? From 5 to 4 hours? From 4 to 3 Hours?
Optimization
Understanding LP and how things change

A few questions- Continued

5. By how much would profit increase if the company could

reduce the labor required to produce Aqua-spas from 9 to
8 hours? From 8 to 7 hours? From 7 to 6 Hours?
I 9 to 8: profit increases by $3,050
I 8 to 7: profit increases by $850
I 7 to 6: profit increases by $0
6. By how much would profit increase if the company could
reduce the labor required to produce Hydro-Luxes from 6
to 5 hours? From 5 to 4 hours? From 4 to 3 Hours?
I 6 to 5: profit increases by $975
I 5 to 4: profit increases by $585
I 4 to 3: profit increases by $390
Optimization
Understanding LP and how things change

A few questions- Continued

7. By how much would profit increase if the company could
reduce the amount of tubing required to produce
Aqua-spas from 12 to 11 feet? From 11 to 10 feet? From
10 to 9 Feet?
Optimization
Understanding LP and how things change

A few questions- Continued

7. By how much would profit increase if the company could
reduce the amount of tubing required to produce
Aqua-spas from 12 to 11 feet? From 11 to 10 feet? From
10 to 9 Feet?
I 12 to 11: profit increases by $0
I 11 to 10: profit increases by $0
I 10 to 9: profit increases by $0
8. By how much would profit increase if the company could
reduce the amount of tubing required to produce
Hydro-Luxes from 16 to 15 feet? From 15 to 14 feet? From
14 to 13 feet?
Optimization
Understanding LP and how things change

A few questions- Continued

7. By how much would profit increase if the company could
reduce the amount of tubing required to produce
Aqua-spas from 12 to 11 feet? From 11 to 10 feet? From
10 to 9 Feet?
I 12 to 11: profit increases by $0
I 11 to 10: profit increases by $0
I 10 to 9: profit increases by $0
8. By how much would profit increase if the company could
reduce the amount of tubing required to produce
Hydro-Luxes from 16 to 15 feet? From 15 to 14 feet? From
14 to 13 feet?
I 16 to 15: profit increases by $0
I 15 to 14: profit increases by $0
I 14 to 13: profit increases by $0
Optimization
Understanding LP and how things change

A few questions- Continued

9. By how much would the unit profit on Aqua-Spas have to

change before the optimal product mix changes?
I The profit on Aqua-Spas can vary between $300 and $450
without changing the optimal solution.
10. By how much would the unit profit on Hydro-Luxes have to
change before the optimal product mix changes?
I The profit on Hydro-Luxes can vary between $233.33 and
$350 without changing the optimal solution.
Optimization

Session summary

I How to formulate decision problems mathematically

I Linear programming formulation
I Decision variables, Constraints, Objective function
I Graphical Method to solve LP
I Special Conditions in LP Models
I Solving LP in a Spreadsheet
I Understanding how things change
Optimization

Next Session- Formulating problems as LP

1. Resource- Allocation Problems.

2. Cost-Benefit Trade-Off problems.
3. Make vs Buy Decisions
4. Investment Problem
5. Transportation and Assignment problems
6. Blending Problem
7. Production Planning problem
8. Multiperiod- cash flow problem