Source: https://jj-zhu.github.

io/argmin/

Introduction to Optimization and Linear Programming(LP)

Read along with Chapter 2 of “Spreadsheet Modeling and Decision Analysis: A Practical Introduction to Business
Analytics, 9th Edition, Cliff Ragsdale, Cengage © 2022”

Lecture by: Dr. Jay Annadatha

Professor
Every Business (Decision) Problem is an Optimization Problem

Every business entity has limited resources (but unlimited potential for growth). The challenge is to Maximize the use
of limited resources by optimal allocation and maximize returns.

Real world cases:

• Oil and Gas Industry – resources may get depleted. How to maximize returns?
• Area for waste disposal
• People facing the challenge of handling several tasks with limited time
• Limited funds available for use

Mathematical Programming (MP) is a business analytics area that finds the most efficient (optimal) use of
available resources to accomplish the business goals.

In other words, MP is used to identify the optimal values for the decision parameters in a mathematical model. So, MP
is also called as Optimization and key to Prescriptive Analytics (for data-driven decision making). Prescriptive
Analytics recommends the best course of action for the business to move forward.

“Prescriptive analytics takes things one step further and presents actions you can take to meet organizational goals”.
(https://online.hbs.edu/blog/post/prescriptive-analytics ) [ Beyond descriptive and predictive analytics]
 Every Business (Decision) Problem
is an Optimization Problem

• Every decision problem can be considered as an

Optimization problem (to maximize the limited
resources and maximize profits)

• Don’t we look at options before making any decisions?

Are we not choosing the best, most efficient way
forward?

• Optimization plays a key role in analytics modeling

This Photo by Unknown Author is licensed under CC BY
(whether it is descriptive, predictive or prescriptive
modeling) – involving choice of optimal variables for the
expected outcome.

• So, optimization study is an excellent starter for business

analytics.
 Chapter 2
Introduction to Optimization and
Linear Programming

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a
publicly accessible website, in whole or in part. 5
Icebreaker: Class Scheduling

• Think about registering for classes.

• How do you prioritize your schedule?
• AM vs. PM classes
• Certain days of the week over others?
• Which professor is teaching?
• Mix of easy and hard classes?
• Distance between classes on campus?
• What is the best schedule?

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Chapter Objectives (1 of 2)
By the end of this chapter, you should be able to:
• 02.01 Describe business applications of optimization.
• 02.02 Describe the components of an optimization problem.
• 02.03 Differentiate between LP and MP problems.
• 02.04 Describe the steps involved in formulating an LP problem
• 02.05 Formulate simple, two-variable LP models for business problems.
• 02.06 Draw the feasible region for an LP problem with two variables.
• 02.07 Identify the optimal solution to an LP problem with two variables using
level curves and by enumerating the corner points of the feasible region.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Chapter Objectives (2 of 2)

By the end of this chapter, you should be able to:

• 02.08 Describe how an LP problem’s feasible region and solution might change
as changes are made to the model parameters.
• 02.09 Describe infeasibility in regard to optimization problems.
• 02.09 Describe alternate optimal solutions in regard to optimization problems.
• 02.10 Describe redundant constraints in regard to optimization problems.
• 02.11 Describe unbounded solutions in regard to optimization problems.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Polling Activity

Which business discipline uses optimization problems most?

a) Accounting
b) Finance
c) Information Systems
d) Management
e) Marketing
f) Supply Chain

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Introduction
• Every decision can be considered an optimization problem
• We generally try to make the best decision possible under the
circumstances
• We face decisions about how to use limited resources such as
• Class schedules
• Oil in the earth
• Land for dumps
• Time
• Money
• Workers

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Mathematical Programming…
• MP 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 underpins
• Descriptive analytics
• Predictive analytics
• Prescriptive analytics

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Applications of Optimization
• Determining Product Mix - how many of each product to make
to maximize profits or meet the market demand at minimal cost
• Manufacturing – optimizing manufacturing operations for
improving the productivity
• Routing and Logistics – Walmart, and other retailers – optimizing
their warehouse and retail stores inventory; FEDEX, UPS using
optimal routing.
• Financial Planning – Imagine 401k withdrawals – how to
minimize IRS taxes and get the best outcome and be in compliance.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Characteristics of Optimization Problems

Optimization problems involve three basic elements as follows:

• Decisions – how many of each product to be produced?

• Constraints – restrictions (maybe IRS withdrawal penalties)
• Objectives – goals that decision maker considers while choosing
the best option.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 General Form of an Optimization Problem
Decisions: X1, X2 etc are the decision variables (say, amount of $
MAX (or MIN): f0(X1, X2, …, Xn) from 401k withdrawal)

Subject to: f1(X1, X2, …, Xn)<=b1 Constraints: Represented as < =, >= or = constraints.
Here, the constraint is some function of the decision variables meeting
: the given constraints. Any number of constraints can be used for an
optimization problem.
fk(X1, X2, …, Xn)>=bk
For e.g., the $ amount withdrawn from 401k is at least the
: minimum amount required by the IRS (for compliance)

fm(X1, X2, …, Xn)=bm Objective: MAX (or MIN): f(X1, X2)

Objective function identifies some function of the decision variables
that the decision maker wants (to either Max Profits or Min losses). For
example, Minimize Total Tax liability for the 401-k withdrawal.

Note: If all the functions in an optimization are linear, the problem is a Linear
Programming (LP) problem

Goal of optimization to find the values of the decision variables which would Maximize (or Minimize) the business objective
function considering all the given constraints.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Linear Programming (LP) Problems

Objective function
MAX (or MIN): c1X1 + c2X2 + … + cnXn
Subject to: a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >=bk Constraints

:
am1X1 + am2X2 + … + amnXn = bm
• LP involves creating and solving optimization problems which have linear objective functions as well as linear constraints (linear in
nature – flat or straight line formation). LP is a very powerful business application tool for optimization.
• c1, c2 – objective function coefficients – represent the marginal profits associated with the decision variables X1, X2
• A11, a12 etc – weighted numeric coeeficients of the decision variables for constraints

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
An Example LP Problem

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a
publicly accessible website, in whole or in part. 16
 An Example LP Problem
• Blue Ridge Hot Tubs 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

• There are 200 pumps, 1566 hours of labor, and 2880 feet of tubing available during the next production cycle.
• The owner is confident that he can sell all the hot tubs he can produce

Challenge: Decide on how many of each type of hot tubs to produce during the next production cycle?

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
5 Steps in Formulating LP Models (1 of 2)

1. Understand the problem.

2. Identify the decision variables.
X1=number of Aqua-Spas to produce
X2=number of Hydro-Luxes to produce
3. State the objective function as a linear combination of the
decision variables.
MAX: 350X1 + 300X2

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 5 Steps in Formulating LP Models (2 of 2)
4. State the constraints as linear combinations of the decision variables.
1X1 + 1X2 <= 200 } pumps
9X1 + 6X2 <= 1566 } labor
12X1 + 16X2 <= 2880 } tubing

5. Identify any upper or lower bounds on the decision variables.

X1 >= 0
X2 >= 0

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
LP Model for Blue Ridge Hot Tubs
Objective Function MAX: 350X1 + 300X2

S.T.: 1X1 + 1X2 <= 200

9X1 + 6X2 <= 1566

Constraints (all
linear) 12X1 + 16X2 <= 2880

X1 >= 0

X2 >= 0

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Discussion Activity: Relying on Intuition

• Idea: Each Aqua-Spa (X1) generates the highest unit profit ($350), so let’s
make as many of them as possible!
• How many would that be?
• Let X2 = 0 [ Because X1 nets $350 profit and makes sense to make X1 more]
1X1 + 1X2 <= 200
• 1st constraint: X1 <= ? (200)
• 2nd constraint: X1 <= ? (174) 9X1 + 6X2 <= 1566

• 3rd constraint: X1 <= ? (240) 12X1 + 16X2 <= 2880

• If X2=0, the maximum value of X1 is what (174 as it is the most restrictive of all the 3 constraint and is the largest X1 value to
satisfy all the constraints) , and what would the total profit be? ($350 x 174 = $60,900)

• Is this the best answer? – No. Let us explore. (because there will still be 26 pumps and 792 ft of tubing remaining)
Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Solving LP Problems: A Graphical Approach

• The constraints of an LP problem defines its feasible region.

• The best point in the feasible region is the optimal solution to the
problem.
• For LP problems with 2 variables, it is easy to plot the feasible
region and find the optimal solution.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Plotting the First Constraint
Shaded area is the feasible region. (or
feasible solution)

Also,

X1 >= 0
X2 >= 0

So, we can not have

negative X1, X2)

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Plotting the Second Constraint

The (200,0) while satisfies the 1st constraint

does not meet the second constraint needs.

So, look for the region which would satisfy

both the constraints 1 and 2 – the shaded
region is the feasible solution

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Plotting the Third Constraint
We can have infinite number of feasible
solutions to maximize the objective. Let
us explore how we can easily eliminate
most of the options in an LP Problem by
consideration

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Plotting a Level Curve of the Objective Function

MAX: 350X1 + 300X2 How to narrow down the optimal solution from
the feasible region meeting all the 3 constraints?

• If a LP Problem has an optimal solution with

a finite objective function value, the solution
always occurs at a point in the shaded feasible
region where 2 or more of the boundary lines
of the constraints intersect. (aka corner points
(0,116.67)
or extreme points of the shaded feasible
region)

• Example shows a case where our objective is

$35,000 profit. All points on the green line
will fetch a profit of $35K.
(100,0)

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
A Second Level Curve of the Objective Function

• If we wish a higher level of profit ($52,500), this

plot will answer the question.

• The two lines representing the two objective

functions are called ‘level curves’ – they
represent different levels or values of the desired
objective. We can have similar levels, all parallel
to each other and away from the point (0,0)

• The last level plot will yield the optimal

solution.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Using a level Curve to Locate the Optimal Solution

The optimal solution as shown here is the point

where the largest possible level curve meets
our feasible region at a single point.

The X1, X2 values at this point will fetch the

maximum profit for the company.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Calculating the Optimal Solution
• The optimal solution occurs where the “pumps” and “labor” constraints intersect.
• This occurs where:
X1 + X2 = 200 (1)
and 9X1 + 6X2 = 1566 (2)
• From (1) we have, X2 = 200 −X1 (3)

• Substituting (3) for X2 in (2) we have,

9X1 + 6 (200 −X1) = 1566
which reduces to X1 = 122
• So the optimal solution is,
X1=122, X2=200−X1=78

Total Profit = $350*122 + $300*78 = $66,100

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Enumerating the Corner Points
Note: This technique will not work if the
solution is unbounded.

The solution using intuitive

approach yielded a Profit of
$60,900 while the optimal solution
fetches a Max Profit of $66,100.

This is the optimal solution.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
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 – this is what was demonstrated in this lecture
b. Enumerating the extreme points (we indicated that if a LP problem has a finite optimal
solution, it always occurs at the corner points of the feasible region. So, we can solve a LP
Problem by identifying all the corner points and compute the objective function values at
each of those points. The corner point with the largest objective function value is the
optimal solution)

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Understanding How Things Change

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Special Conditions in LP Models

• A number of anomalies can occur in LP problems:

• Alternate Optimal Solutions These two conditions do not stop us from solving a LP
Problem. Just anomalies
• Redundant Constraints
• Unbounded Solutions
Real problems that prevent us from solving a LP Model
• Infeasibility

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Example of Alternate Optimal Solutions
There can be more than one optimal solution. (more
than one optimal point which maximizes the objective
function value)

In the example discussed, the manufacturer can increase

the price of Aqua-Spas where each sale fetches $450
profit ( not $350)

Revised LP Model objective function is:

MAX: 450 X1 + 300 X2
Constraints would be the same.

Feasible region is the same as constraints are the same.

Only the objective level curves would change as shown.

The final level curve meets the feasible region – not at

one optimal point but along an edge (corner points
from (122,78) to (174,0) produce the same optimal
value of $78,300

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Example of a Redundant Constraint
• Redundant constraint is one which plays
no role in determining the feasible
region of the LP Problem.

• If 225 hot tub pumps are available (not

200 as in the earlier case), constraint 1
would change as: 1X1 + 1X2 < = 225

• We see that the new feasible region is

not influenced by the pump constraint
but the constraints 2 and 3 play a key
role. So, we can remove the pump
constraint from the model (if 2 and 3 are
satisfied, constraint 1 will also be
satisfied). So, this constraint is
redundant. (also being redundant, there
will always be excess pumps available
for any optimal solution)

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Example of an Unbounded Solution
There may be cases where objective
function can be made infinitely large.
For example,
MAX: X1 + X2 (subject to earlier
constraints)

The feasible region and level curves

are shown for this objective function.

While the level curves are moving

away from (0,0) in parallel in one
direction, the feasible region is not
bounded in that direction.

This happens when some constraints

were omitted or < constraint used for >
constraint.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
Example of Infeasibility to a LP Problem

If there is no way to satisfy all the

problem constraints simultaneously, we
say the LP Problem is not feasible.

There are no possible values of X1, X2

that satisfy both the constraints shown
here. So, infeasible LP Problem.

Occurs due to wrong specification of the

constraints (<, >) . So, we have to
formulate the constraints properly
(loosening by increasing upper limits or
lowering the lower limits)

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Self-Assessment

What are some other types of optimization problems

you regularly encounter in your life?

Can you take an example of an optimization problem

and try using the five steps in formulating an LP model?

What does it mean to have alternate optimal solutions?

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Summary (1 of 2)

We learned how to
• Describe business applications of optimization.
• Describe the components of an optimization problem.
• Differentiate between LP and MP problems.
• Describe the steps involved in formulating an LP problem
• Formulate simple, two-variable LP models for business problems.
• Draw the feasible region for an LP problem with two variables.
• Identify the optimal solution to an LP problem with two variables using
level curves and by enumerating the corner points of the feasible region.
Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.
 Summary (2 of 2)

Learned how to
• Describe how an LP problem’s feasible region and solution might
change as changes are made to the model parameters.
• Describe infeasibility in regard to optimization problems.
• Describe alternate optimal solutions in regard to optimization
problems.
• Describe redundant constraints in regard to optimization problems.
• Describe unbounded solutions in regard to optimization problems.

Cliff T. Ragsdale, Spreadsheet Modeling & Decision Analysis, Ninth Edition. © 2022 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly
accessible website, in whole or in part.