EN: All rights pertaining to online course contents available on this platform are

reserved and protected by copyrights of the respective course. Online contents on this
platform cannot be used for any other purposes, unless authorized in writing by the
course instructor(s). The contents may not be copied, altered, distributed, transmitted,
or used for miscellaneous purposes, in any way, in whole or in part.
Linear Programming

More Examples
Optimization Musts

Decision variables: e.g., x and y.

In general, there are quantities you can control to improve your
objective which should completely describe the set of decisions
to be made.

Constraints: e.g., 5x + 8y  24 , x  0 , y  0
Limitations on the values of the decision variables.
Objective Function. e.g., 3x + 4y
Value measure used to rank alternatives
Seek to maximize or minimize this objective
examples: maximize NPV, minimize cost
Chapter Topics

◼ An Aggregate Planning Example

◼ A Blend Example
◼ An Investment Example
◼ A Data Envelopment Analysis Example
An Aggregate planning Example
What is aggregate planning?
Planning Horizons
medium-range capacity planning,
usually covering 2 to 18 months

Short-range plans Responsible:

Job assignments Operations
Ordering managers
Job scheduling Intermediate-range plans
Dispatching Sales planning Responsible: Top
Production planning and executives
Responsible: budgeting
Long-range plans
Operations Setting employment, inventory,
R&D
managers, subcontracting levels
New product plans
supervisors, Analyzing operating plans
Capital expenses
foremen Facility location, expansion

Today 3 Months 1 year 5 years

Planning Horizon
An Aggregate planning Example
Such models, where we determine workforce levels and
production schedules for a multiperiod time horizon, are called
aggregate planning models.

What does “over-time” mean?

What does “holding-cost” mean?
Without solving the problem, can you guess whether
in the optimal solution, no overtime is made?
in the optimal solution, no inventory is held at any periods?
in the optimal solution, it holds that “inventory at the end of
period 4=100”?
An Aggregate planning Example
During the next four months the SureStep Company must meet (on
time) the following demands for pairs of shoes: 3,000 in month 1; 5,000
in month 2; 2,000 in month 3; and 1,000 in month 4.
At the beginning of month 1, 500 pairs of shoes are on hand
SureStep has 100 workers.
A worker is paid $1,500 per month. Each worker can work up to 160
hours a month before he or she receives overtime.
A worker can work up to 20 hours of overtime per month and is paid
$13 per hour for overtime labor.
It takes 4 hrs of labor and $15 of raw material to produce a pair of
shoes.
The workforce level is allowed to change each period through the hiring
and firing of workers.
A hiring costs $1600, firing costs $2000
A holding cost of $3 for each pair at the end of each month
An Aggregate planning Example
Production in a given month can be used to meet that month’s
demand.
SureStep wanst to use LP to determine its optimal production
schedule and labor policy.
Objective is to find minimum-cost solution that meets forecasted
demands on time and stays within limits on overtime and
production capacity.
Optimization Musts: An Aggregate Planning Problem
Objective Function.
Minimize cost
Decision variables:
# of workers hired in each month
# of workers fired in each month
Overtime labor hrs in each month
Production amount in each month
In total ( 4*4=16 DVs)
Constraints:
Demand is satisfied with available inventory
Production does not exceed worker capacity
Max overtime hr not exceeded
 Modeling Tricks
1. Determine decision variables
2. Make a plan for constraints:
1. If constraints require not only direct decision variables, but some
functions of decision variables, called “intermediary variables”, calculate
them
2. If possible first write each of these intermediary variables separately,
then combine them in a cell
3. E.g. total production capacity composed of both regular and overtime
3. Make a plan for the objective function
1. If constraints require not only direct decision variables, but some
functions of decision variables, called “intermediary variables”, calculate
them
2. If possible first write each of these intermediary variables separately,
then combine them in a cell
3. E.g. total cost is composed of hiring, firing, regular, overtime, raw
material, inventory
Sensitivity: Aggregate Planning
1. What happens if the overtime wage rate/hr would be
lower? Or higher?

2. How sensitive is the total cost to hiring cost per/worker and

firing cost/cost? Please use a two-way table and test
sensitivity between 1500-2200 with increments of 100.
The rolling planning horizon approach
In reality, an aggregate planning model is usually implemented
via a rolling planning horizon.
To illustrate, we assume that SureStep works with a 4-month
planning horizon.
To implement the SureStep model in the rolling planning
horizon context, we view the “demands” as forecasts and solve
a 4-month model with these forecasts.
However, we implement only the month 1 production and work
scheduling recommendation.
Model with backlogging allowed
In many situations backlogging is allowed - that is, customer
demand can be met later than it occurs.
We’ll modify this example to include the option of backlogged
demand.
We assume that at the end of each month a cost of $20 is
incurred for each unit of demand that remains unsatisfied at
the end of the month.
This is easily modeled by allowing a month’s ending inventory
to be negative. The last month, month 4, should be
nonnegative.
This also ensures that all demand will eventually be met by
the end of the four-month horizon.
The ball is in your court…
Please work in groups and update the model (completed one)
to allow for backlogging,
For this purpose:
Define backlog cost/unit/month=20$
Add a total backlog cost function per month for each
month. How? Hint: IF…
Is the model still linear?
Now, only for month 4, “inventory after production >=
forecasted demand”
Model with backlogging allowed
When certain functions, including IF, MIN, MAX, and ABS, are
used to relate the objective cell to the changing variable cells,
the resulting model becomes not only nonlinear but
nonsmooth.
Essentially, nonsmooth functions can have sharp edges or
discontinuities.

Solver’s GRG nonlinear algorithm can handle “smooth”

nonlinearities, but it has trouble with nonsmooth functions.

The moral is that you should avoid the nonsmooth functions in

optimization models.
Model with backlogging allowed
If you do use nonsmooth functions, then you must run Solver
several times, stating from different initial solutions.
Alternatively, nonsmooth functions can be handled with a
totally different kind of algorithm called a genetic algorithm.
Alternatively, you can use Frontline System’s Evolutionary
Solver, which became available in Excel’s Solver in Excel 2010.
Blending models
In many situations, various inputs must be blended together
to produce desired outputs.
In many of these situations, linear programming can find the
optimal combination of outputs as well as the mix of inputs
that are used to produce the desired outputs.
Always ensure that blending constraints are expressed linearly.
Some examples of blending problems are given in the table
below.
Blending Example
Chandler Oil has 5000 barrels of crude oil 1 and 10,000 barrels of
crude oil 2 available.
Chandler sells gasoline and heating oil. These products are
produced by blending the two crude oils together.
We assume that demand for heating oil and gasoline is unlimited,
so that all of Chandler’s production can be sold.
If any oil is leftover, they can be sold at a value.
The leftover value and quality levels of inputs (oils) and the price
and min. quality requirements of outputs (gasoline and heating
oil) are Properties of
Properties of outputs Gasoline Heating oil
crude oil Value per Quality Selling price
inputs barrel level per barrel $75 $60
Crude oil 1 $65 10 Required
Crude oil 2 $50 5 quality level 8 6
Blending Example
Chandler wants to maximize its revenue from selling gasoline
and heating oil.
Objective is to develop an LP spreadsheet model for finding the
revenue-maximizing plan that meets quality constraints and
stays within limits on crude oil availabilities
Before spending time on modeling…
Which output is more profitable?
Gasoline ($75)

So, shall they produce only gasoline?

But the gasoline requires a higher quality level,
Which is possible with crude oil 1, which is more expensive

Should they keep any crude oil unused?

We will see..
Optimization Musts: Blending Problem
Objective Function.
Maximize revenue: output revenue+ leftover input revenue
Decision variables:
Amount of crude oil 1 in gasoline
Amount of crude oil 1 in heating oil
Amount of crude oil 2 in gasoline
Amount of crude oil 2 in heating oil
In total (4 DVs)
Constraints:
Availability of each input (crude 1 and crude 2)
Min quality level for each output (gasoline and heating oil)
The ball will be in your court…
We will first model the problem together.
Then, please work in groups and solve the problem using
solver.
Sensitivity Analysis: Blending Problem
1. How does increasing the price of the gasoline above $75
increase the profit and production plan?

2. How does the change in availability of crude oil 1 change

the production plan and the total profit?
Financial models
Optimization and other management science methods have
also been applied successfully in a number of financial areas,
and they deserve recognition.
Several of these applications are discussed throughout this
book.
Next, we discuss a typical applications of LP in finance: pension
fund management.
 Pension Fund Example
James Judson is the financial manager in charge of the company
pension fund at Armco Inc.
James knows that the fund must be sufficient to make payments
listed in the table below.
Each payment must be made on the first day of each year.
It is now Jan 1st of 2022
PAYMENTS
2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036

$11,000 $12,000 $14,000 $15,000 $16,000 $18,000 $20,000 $21,000 $22,000 $24,000 $25,000 $30,000 $31,000 $31,000 $31,000
 Pension Fund Example
James is going to finance these payments by purchasing bonds.
3 bonds are available for immediate purchase. The prices and
coupons for the bonds are given in the following table.
PRICES OF BOND AND EARNINGS BY YEAR
2022
Year (price) 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036

Bond 1 $980 $60 $60 $60 $60 $1,060

Bond 2 $970 $65 $65 $65 $65 $65 $65 $65 $65 $65 $65 $1,065

Bond 3 $1,050 $75 $75 $75 $75 $75 $75 $75 $75 $75 $75 $75 $75 $75 $1,075

James must decide how much cash to allocate to meet the initial
$11 000 payment and buy enough bonds to make future
payments.
He knows that any excess cash on hand can earn an annual rate
of 4% in a fixed-rate account. How should he proceed?
Pension Fund Example
This example illustrates a common situation where fixed
payments are due in the future and current funds must be
allocated and invested so that their returns are sufficient to
make the payments.
We place this in a pension fund context.
Objective is to minimize cash allocated to fund plan.
Cash allocated to fund plan is also a decision variable!
Optimization Musts: Pension Fund Problem
Objective Function.
Minimize the total money to allocate
Decision variables:
The number of Bond 1 to buy SAME
The number of Bond 2 to buy
The number of Bond 3 to buy
The total initial cash to allocate
In total (4 DVs)
Constraints:
In each year, there should be enough cash for pension fund
payments
The ball will be in your court…
We will first model and solve the problem together.
Then, please work in groups and answer the sensitivity
question using SolverTable add-in.
Sensitivity Analysis: Pension Fund
How do the bond allocation decisions and the total cash
needed change with the outside interest rate?
Change this rate between 2%-8%
Take-Aways
Presented more LP spreadsheet models of many diverse
situations.
Discussed their sensitivity analyses using SolverTable add-in.
When integer variables are used, standard sensitivity analysis
of Excel is not available, but SolverTable is available.