TOPIC 4: OPTIMIZATION MODELS

LAN JIANG

MIS 665 Prescriptive Analytics and Advanced Topics

Chapter 14 Optimization Models

Business Analytics

Data Analysis and Decision

Making (7e)

S. Christian Albright

Wayne L. Winston

© 2020 Cengage. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part, except for use as permitted in a license distributed with a certain product or service or

otherwise on a password-protected website or school-approved learning management system for classroom use.

Agenda

• More LP Examples

– 14.3 Blending Models

– 14.6 Financial Models

• Fundamentals of Integer Programming

– 14.2 Employee Scheduling Problems

– 14.7 Integer Optimization Models

• Assignment Overview

– P14_89

– P14_80

• Week 4 Assignment Discussion

BLENDING MODELS (EXAMPLE 14.2)

Blending Models

• In many situations, various inputs must be blended to produce

desired outputs.

• In many of these situations, blending models can be used to

find the optimal combination of outputs as well as the mix of

inputs used to produce desired outputs.

• Examples of blending problems:

Example 14.2: Blending Oil Products

• Objective: To develop an optimization model for finding the

revenue-maximizing plan that meets quality constraints and stays

within limits on crude oil availabilities.

• Solution: Chandler Oil has 5000 barrels of crude oil 1 and 10,000

barrels of crude oil 2 available.

– Chandler sells gasoline and heating oil, which are produced by blending the

two crude oils together.

– Each barrel of crude oil 1 has a quality level of 10, and each barrel of crude

oil 2 has a quality level of 5.

– Gasoline must have an average quality level of at least 8, whereas heating

oil must have an average quality level of at least 6.

– Gasoline sells for $75 per barrel, and heating oil sells for $60 per barrel.

– If any barrels of the crude oils are left over, they can be sold for $65 and $50

per barrel, respectively.

Problem Formulation 1

NONLINEAR INEQUALITY

Problem Formulation 2

Excel Demonstration

• Example14_2_lanDemo.xlsx

14.6 FINANCIAL MODELS (EXAMPLE 14.6)

Example 14.6

• Objective: To develop an optimization model that relates investment decisions to total

ending cash, and to use Solver to find the strategy that maximizes ending cash and

invests no more than a given amount in any one investment.

• Solution: At the beginning of year 1, Barney-Jones Investment Corporation has $100,000

to invest for the next four years. It wants to limit the amount put into any investment to

$75,000.

• There are five possible investments, labeled A through E.

– Investment A: Invest at the beginning of year 1, and for every dollar invested, receive

returns of $0.50 and $1.00 at the beginnings of years 2 and 3.

– Investment B: Invest at the beginning of year 2, receive returns of $0.50 and $1.00 at

the beginnings of years 3 and 4.

– Investment C: Invest at the beginning of year 1, receive return of $1.20 at the

beginning of year 2.

– Investment D: Invest at the beginning of year 4, receive return of $1.90 at the

beginning of year 5.

– Investment E: Invest at the beginning of year 3, receive return of $1.50 at the

beginning of year 4.

Problem Formulation

Excel Demonstration

• Example14_6_lanDemo.xlsx

FUNDAMENTALS OF INTEGER PROGRAMMING

Integer Programming

• An integer programming (IP) in which all variables are required

to be integers is called a pure IP problem.

• An integer programming (IP) in which some of variables are

required to be integers is called a mixed IP problem.

• An IP problem in which all the variables must be 0 or 1 is called

a 0-1 IP or binary IP.

• The linear programming (LP) obtained by omitting all integer

or binary constraints on variables is called LP relaxation of the

IP.

Examples

Reference: Yong Wang (2017) Operations Research 09A: Integer Programming vs Linear Programming Relaxation

https://www.binghamton.edu/centers/seorl/

Fundamental Questions

• Q1: feasible region of IP is (<=, =, >=) the feasible region of LP

relaxation?

• Q2: optimal function value of IP is (<=, =, >=) optimal function

value of LP relaxation? (Max obj)

• Q3: Which is more difficult to solve? The IP or the LP

relaxation?

• Can we use the rounding method of LP relaxation to solve the

IP?

Fundamental Questions

• Q1: feasible region of IP is (<=, =, >=) the feasible region of LP relaxation?

Answer: LP relaxation has greater feasible region since in LP relaxation variables

can take both integers and real numbers

• Q2: optimal function value of IP is (<=, =, >=) optimal function value of LP

relaxation? (Max obj)

Answer: In general, LP relaxation will have a greater optimal function value since it

has a greater feasible region

• Q3: Which is more difficult to solve? The IP or the LP relaxation?

Answer LP is easier to solve since we can use the simplex method to only check

for the extreme points and it will lead us to find the optimal solution whereas in IP

theoretically we need to enumerate all possible combinations of x values in the

feasible region and check for the optimal function value.

• Can we use the rounding method of LP relaxation to solve the IP?

Answer: NO! refer to the example in the next slide!

Solution Algorithms

• An LP with several thousand continuous variables can be solved

with a number of commercial linear programming solvers.

However, an all-integer linear programming problem with less

than 100 variables can be extremely difficult to solve.

• Experienced scientists can help identify the types of integer linear

programs that are easy, or at least reasonable, to solve.

• Commercial computer software packages, such as MPSX-MIP ®,

OSL ®, CPLEX ® and LINDO, have extensive integer programming

capability. Spreadsheet packages, such as Excel, have the

capability for solving smaller integer linear programs.

Reference: Yong Wang (2017) Operations Research 09A: Integer Programming vs Linear Programming Relaxation

https://www.binghamton.edu/centers/seorl/

14.2 EMPLOYEE SCHEDULING MODELS

(EXAMPLE 14.1)

Example 14.1: Employee Scheduling

• Objective: To develop an optimization model that relates five-day shift

schedules to daily numbers of employees available, and to use Solver on

this model to find a schedule that uses the fewest number of employees

and meets all daily workforce requirements.

• Solution: The number of full-time employees required each day is given in

the table at the bottom left.

– Union rules state that each full-time employee must work five

consecutive days and then receive two days off.

– The business wants to meet its daily requirements using only full-time

employees, with the objective of minimizing the number of full-time

employees.

Problem Formulation

Excel Demonstration

• Example14_1_lanDemo.xlsx

Modeling Issues

• The employee scheduling example is called a static scheduling

model because we assume that the business faces the same

situation each week.

– In reality, demands change over time. A dynamic scheduling model is

necessary for such problems.

• A scheduling model for a more complex organization has a

larger number of decision variables, and optimization software

such as Solver will have difficulty finding a solution.

– Heuristic methods have been used to find solutions to these

problems.

• The scheduling model can be expanded to handle part-time

employees, the use of overtime, and alternative objectives

such as maximizing the number of weekend days off.

14.7 INTEGER OPTIMIZATION MODELS

(EXAMPLE 14.8)

Example 14.8

• Objective: To use a binary IP model to find the set of investments that stays

within budget and maximizes total NPV.

• Solution: Tatham Company is considering seven investments.

• The cash required for each investment and the net present value (NPV)

each investment adds to the firm are listed in the table below.

• Partial investments are not allowed.

• The cash available for investment is $15,000,000.

Problem Formulation

Excel Demonstration

• Example14_8_lanDemo.xlsx

CENGAGE HOMEWORK REVIEW

Topic 4: Chapter 14

MC 14.038

MC 14-043

Problem 14-50

Useful Tutorial:

https://college.cengage.com/geyser/albright/winston_9780357109953/video/video.html?as

set=chapter_14_problem_14_50

Hint: Mathematical Formulation

Problem 14-50

Note: Cengage Error, the optimal NPV (215757)

solved by your Excel is the correct one however,

please enter 75757 in Cengage to obtain the full

score!!!

P14.80

Hint: Mathematical Formulation

S14_80_lanDemo.xlsx

Problem 14.86

Hint: Mathematical Formulation

Excel Setup

Problem 14.86

Note: Cengage Error, the optimal NPV

(324,000,000) solved by your Excel is the correct

one however, please enter 324,000 in Cengage to

obtain the full score!!!

GIANT MOTOR COMPANY

Week 4 Case Study

Case 14.1

Hints: Thinking about Math Formulation

• Decision Variables: two binary (if retool Lyra and/or Libra), 15

integer (non-negative) variables

• Constraints:

– Number of Vehicles of each model to be produced should be less

than or equal to the actual demand (with consideration of demand

diversion)

– Number of Vehicles of each model to be produced should be less

than or equal to capacity of each plant

• Objective Function: maximize profit

– Update profit margin based on the decision of retooling

– Update fixed cost based on the decision of retooling

Hints: decision variables

• Two major decisions to make:

– If we want to retool Lyra and/or Libra manufacturing plants

– How many vehicles of each model (Lyra, Libra and Hydra) to be

produced by each of the manufacturing plants next year

Hints: decision variables

• Two major decisions to make:

– If we want to retool Lyra and/or Libra manufacturing plants

– How many vehicles of each model (Lyra, Libra and Hydra) to be

produced by each of the manufacturing plants next year

Talking About Constraints

• Demand: take into consideration of Demand Diversion!

• Based on the decision of retooling the following components

need to be updated:

– Production Capacity

– Fix Cost

– Profit Margin

Mathematical Formulation

This is a Linear Integer

Programming problem (LIP). Use

Simplex method in Excel Solver

Excel: Requiremnts

• Download Case14.1_student.xlsx

• Complete the constraint formula (of demand and capacity) and

objective function cells highlighted in Dark Red

• Setup Solver (define objective function, setup decision variables and

constraints)

• Solve the problem and discuss (in the WORD document) if Excel

provides the optimal solution (why and why not?)

• Rename the Excel file with your first name and submit on Halo. I will

grade your work based on if you correctly calculate the constraints

and objective function and setup the solver with all required items!

Further Thoughts

• For some reasons, current Excel Solver fails to find optimal

solution for this LIP?! Why the solution provided by Excel is not

optimal?

• Review my sample R script (case14_1_lanDemo.R) to see how

to solve exactly the same question in R

• Original problem’s optimal solution solved by R is shown below:

Report: Requirements

• Start with MIS-665-RS-CaseStudy.docx (download it

from Halo→ Class Resource)

• Include the following items in your report:

–Background

–Problem Statement

–Questions

–Solution and Recommendation

• Explicitly state the optimal solution found by the Excel solver.

• Is Excel solution optimal? Why and why not?

• Explicitly state the optimal solution found by R (GIVEN to you in the

previous slide!!!) and discuss the solution and recommendation!

–References

Deliverables

• Upload:

–The completed Excel file

–The completed Word file

• Please rename both of your files with

your FirstName before submission!