OPERATIONS RESEARCH An Intro
By Farizal, PhD
Operations Research, OR What is It?
Operations research (also known as management science, MS) is a collection of techniques based on mathematics and other scientific approaches a problem within a
system to yield the optimal solution.
2
History of O.R.
World War IIresearch on military operation. 1947simplex method by George Dantzig. 1950LP , DP , Queueing Theory , and Inventory Theory. Computer revolution. 1980ssoftware package.
Optimisation = Efficiency + Savings
Kelloggs
The largest cereal producer in the world. LP-based operational planning (production, inventory, distribution) system saved $4.5 million in 1995. A large worldwide consumer goods company. Utilised integer programming and network optimization worked in concert with Geographical Information System (GIS) to re-engineering product sourcing and distribution system for North America. Saved over $200 million in cost per year. Robust supply chain design based on advanced inventory optimization techniques. Realized savings of over $130 million in 2004
Procter and Gamble
Hewlett-Packard
Source: Interfaces
Properties of O.R.
O.R. is concerned with OPTIMAL decision making in, and modeling of, deterministic & probabilistic systems that originate from Real life.
Properties of O.R.
Creative scientific research into the fundamental properties of operations. Search for optimality. Team approach-involving the backgrounds of mathematics, statistics & probability theory, economics, business administration, electronic computing, engineering & physics, and behavior sciences etc.
Distinct Nature of OR
Simultaneously analyzes all variables Seeks global, balanced solutions defined by: Multiple criteria Multiple, conflicting objectives Helps mitigate risk and reduces uncertainty by modeling different scenarios Goes beyond single-issue management
Contribution of O.R.
The structuring of the real life situation into a mathematical model, abstracting the essential elements so that a solution relevant to the decision makers objectives can be sought. This involves looking at the problem in the context of the ENTER SYSTEM. Exploring the STRUCTURE of such solutions & developing systematic procedures for obtaining them. Developing a solution, including the mathematical theory, if necessary that yields an optimal measure of DESIRABILITY.
What in O.R.?
Deterministic LP , DP , NLP , Scheduling, Problem IP ,Inventory , PERT/CPM Network Stochastic D.S. Forecasting , Problem Simulation. Decision Queueing , Analysis, Game Theory Markov Chain
Deterministic versus Stochastic
Two broad categories of optimization models exist deterministic parameters/data known with certainty stochastic parameters/data know with uncertainty Deterministic models are easier to solve. we pretend we know the parameter/input with certainty). Stochastic model are difficult to solve. In reality, we know a distribution about our demand. We get around this in real life by re-optimizing.
Deterministic versus Stochastic
Deterministic optimization ignores risk of being wrong about parameter/data estimates. No commercial software packages are currently available to do generalized, stochastic optimization.
Linear Programs A Major Tool of OR
Linear Programs (LPs) are a special type of mathematical model where all relationships between parts of the system being modeled can be represented linearly (a straight line). Not always realistic, but we know how to solve LPs. May need to approximate a relationship that is slightly non-linear with a linear one. When to use: if a problem has too many dimensions and alternative solutions to evaluate all manually, use an LP to evaluate.
General Optimization Model
Problem(1):
Min f(x) s.t. g(x)0 --------(1) x 0
Linear Programs
LPs can evaluate thousands, millions, etc. of different alternatives to find the one that best meets the objective of the business problem.
Fleet Assignment Model - assign aircraft to flight legs to minimize cost and maximize revenue Revenue Management - set bid prices to maximize revenue and/or minimize spill Crew Scheduling - schedule crew members to minimize number of crew needed and maximize utilization
Other Types of Linear Optimizations
MIP (Mixed Integer Programming)
is similar to LP but at least one decision variable is required to be a integer value violates the LP rule that decision variables be continuous is solved by branch and bound - solving a series of LPs that fix the integer decision variables to various integer values and comparing the resulting objective function values is done in a smart way to avoid enumerating all possibilities is useful, since you can not have .3 of an aircraft
Other Types of Linear Optimization
Network problem
is a special form of LP which turns out to be naturally integer can be solved faster than an LP, using a special network optimization algorithm is very restrictive on types of constraints that can be present in the problem
Shortest Path
finds the shortest path from the source (start) to sink (end) nodes, along connecting arcs, each having a cost associated with them is used in many applications
Other Optimization Models
Quadratic Program
has a quadratic objective function with linear constraints can be applied to revenue management, because it allows fare to rise with demand within a problem
price(OD) = 50 + [5*numpax(OD)] max revenue = price * numpax
Other Optimization Models
Non-linear Program (NLP)
can have either non-linear objective function or non-linear constraints or both feasible region is generally not convex much more difficult to solve but it is worth our time to learn to solve them since world is actually non-linear most of the time some non-linear programs can be solved with LPs or MIPs using piecewise linear functions
Applications of O.R.
Inventory & Production Problem Maximization Problem Minimization Problem Work-Force Planning Problem Waiting Line Problem
Application Details
Accounting:
Cash flow planning Credit policy Strategy planning
Manufacturing
Production scheduling Production-marketing balance
Facilities Planning
Location & size Logistics systems Transportation Planning Hospital planning
Organization Behavior
Employee recruiting Skills balancing Training programs scheduling Manpower justification \ planning
OR/MS Successes
Best cases from the annual INFORMS Edelman Competition
2002: Continental Airlines Survives 9/11 2001: Merrill Lynch Integrated Choice 2001: NBCs Optimization of Ad Sales 2000: Ford Motor Prototype Vehicle Testing 1996: Procter & Gamble Supply Chain 1991: American Airlines Revolutionizes Pricing
Case 4: Ford Motor Prototype Vehicle Testing
Business Problem: Developing prototypes for new cars and modified products is enormously expensive. Ford sought to reduce costs on these unique, first-of-akind creations.
Ford Motor (cont)
Model Structure: Ford and a team from Wayne State University developed a Prototype Optimization Model (POM) to reduce the number of prototype vehicles. The model determines an optimal set of vehicles that can be shared and used to satisfy all testing needs. Project Value: Ford reduced annual prototype costs by $250 million.
Case 5: Procter & Gamble Supply Chain
Business Problem: To ensure smart growth, P&G needed to improve its supply chain, streamline work processes, drive out nonvalue-added costs, and eliminate duplication.
P&G Supply Chain (cont)
Model Structure: The P&G operations research department and the University of Cincinnati created decision-making models and software. They followed a modeling strategy of solving two easierto-handle subproblems:
Distribution/location Product sourcing
Project Value: The overall Strengthening Global Effectiveness (SGE) effort saved $200 million a year before tax and allowed P&G to write off $1 billion of assets and transition costs.
P&G Supply Chain (cont)
Project Value: The overall Strengthening Global Effectiveness (SGE) effort saved $200 million a year before tax and allowed P&G to write off $1 billion of assets and transition costs.
Case 6: American Airlines Revolutionizes Pricing
Business Problem: To compete effectively in a fierce market, the company needed to sell the right seats to the right customers at the right prices.
American Airlines (cont)
Model Structure: The team developed yield management, also known as revenue management and dynamic pricing. The model broke down the problem into three subproblems:
Overbooking Discount allocation Traffic management
The model was adapted to American Airlines computers.
American Airlines (cont)
Project Value: In 1991, American Airlines estimated a benefit of $1.4 billion over the previous three years. Since then, yield management was adopted by other airlines, and spread to hotels, car rentals, and cruises, resulting in added profits going into billions of dollars.
Phases of an OR Project
Define the problem Develop math model to represent the system Solve and derive solution from model Test/validate model and solution Establish controls over the solution Put the solution to work
Mathematics in Operation
Real Practical Problem Mathematical (Optimization) Problem Mathematical Solution Method (Algorithm) x2
Computer Algorithm
Decision Support Software System Human Decision-Maker
Problem Solving Stages
Real Practical Problem Mathematical (Optimization) Problem Mathematical Solution Method (Algorithm) Computer Algorithm
Staff Rostering at Childcare Centre
Mathematical Programming
CPLEX
XpressMP
LINGO
Decision Support Software System Human Decision-Maker
Excel with VBA
Childcare Centre Manager
General Optimization Model
Problem(1):
Min f(x) s.t. g(x)0 --------(1) x 0
The Objective Function is an expression that defines the optimal solution, out of the many feasible solutions. We can either
MAXimize - usually used with revenue or profit or MINimize - usually used with costs
Feasible solutions must satisfy the constraints of the problem. LPs are used to allocate scarce resources in the best possible manner. Constraints define the scarcity. The scarcity in this problem involves a fixed number of seats and scarce high paying customers.
Rules for Constraints
must be a linear expression decision variables can be summed together but not multiplied or divided by each other have relational operators of =, <=, or >= must be continuous
Constraints define the feasible region - all points within the feasible region satisfy the constraints. The feasible region is convex. The optimal solution lies at an extreme point of the feasible region
Example
A company with three plants produces two products. First plant that operates for 4 hours produces only product 1. Second plant operates for 12 hours but produces only product 2. The last plant operates for 18 hours and produces both products. It takes one hour to produce product 1 at plant 1 and 3 hours at plant 3 while product 2 needs 2 hour to be produced at available facilities. If the selling price for product 1 and 2 is $3,000 and $5,000, respectively. Find how many product 1 and product 2 should be made to maximize the profit? How much the profit?
Solution: Problem Articulation
Plant 1 2 3 Profit Product 1 1 0 3 $3,000 2 0 2 2 $5,000 Product time available 4 hours 12 hours 18 hours
Linear Programming Formulation
Define:
xi
: number of batches of product i produce per week : total profit per week form purchasing this two
products Objective function: to maximize Max 3 X1 + 5 X2 Constraints: production time available X1 4
Complete LP Model
Max z = 3x1 5 x2 s.t x1 4
2 x2 12 3 x1 2 x2 18 x1 0, x2 0
Example-Extended
A company with three plants produces two products. First plant that operates for 4 hours produces only product 1. Second plant operates for 12 hours but produces only product 2. The last plant operates for 18 hours and produces both products. It takes one hour to produce product 1 at plant 1 and 3 hours at plant 3 while product 2 needs 2 hour to be produced at available facilities. If the selling price for product 1 and 2 is $3,000 and $5,000, respectively, and if product 1 in order to be economical should be produced at least 3, find how many product 1 and product 2 should be made to maximize the profit? How much the profit?
Complete LP Model
Max z = 3x1 5 x2 s.t x1 4
x1 3 2 x2 12 3 x1 2 x2 18 x1 0, x2 0
Example-Extended
A company with three plants produces two products . First plant that operates for 4 hours produces only product 1. Second plant operates for 12 hours but produces only product 2. The last plant operates for 18 hours and produces both products. It takes one hour to produce product 1 at plant 1 and 3 hours at plant 3 while product 2 needs 2 hour to be produced at available facilities. If the selling price for product 1 and 2 is $3,000 and $5,000, respectively. Find how many product 1 and product 2 should be made to maximize the profit. How much the profit? Determine which plants produce the products?
References
F.S. Hillier, Introduction to Operations Research, McGraw Hill 2009 H.A. Taha, Operations Research an Introduction, Prentice Hall 2008 F.S. Hillier and Lieberman Winston