Embed Size (px)
Citation preview
Pesquisa Operacional Aplicada à Logística
Prof. Fernando Augusto Silva Marins
www.feg.unesp.br/~fmarins
Sumário Introdução à Pesquisa Operacional (P.O.)
Impacto da P.O. na Logística
Modelagem e SoftwaresExemplosCases em Logística
Pesquisa Operacional
Operations Research
Operational Research
Management Sciences
A P.O. e o Processo de Tomada de Decisão
Tomar decisões é uma tarefa básica da gestão.
Decidir: optar entre alternativas viáveis.
Papel do Decisor:
Identificar e Definir o Problema
Formular objetivo (s)
Analisar Limitações
Avaliar Alternativas Escolher a “melhor”
PROCESSO DE DECISÃO
Abordagem Qualitativa: Problemas simples e experiência do decisor
Abordagem Quantitativa: Problemas complexos, ótica
científica e uso de métodos quantitativos.
Pesquisa Operacional faz diferença no desempenho de
organizações?
Resultados - finalistas do Prêmio Edelman
INFORMS 2007
FINALISTAS EDELMAN 1984-2007Ano Empresa Título do Trabalho1996 South African National Defense Force* "Guns or Butter: Decision Support for Determining the Size and Shape of the
South African National Defense Force (SANDF)"1996 The Finance Ministry of Kuwait "The Use of Linear Programming in Disentangling the Bankruptcies of al-Manakh
Stock Market Crash1996 AT&T Capital "Credit and Collections Decision Automation in AT&T Capital's Small-Ticket
Business"1996 British National Health Service "A New Formula for Distributing Hospital Funds in England"1996 National Car Rental System, Inc. "Revenue Management Program"1996 Procter and Gamble "North American Product Supply Restructuring at Procter & Gamble"1996 Federal Highway Administration/California Department
of Transportation"PONTIS: A System for Maintenance Optimization and Improvement of U.S. Bridge Networks "
1995 Harris Corporation/Semiconductor Sector* "IMPReSS: An Automated Production-Planning and Delivery-Quotation System at Harris Corporation - Semiconductor Sector"
1995 Israeli Air Force "Air Power Multiplier Through Management Excellence"1995 KeyCorp "The Teller Productivity System and Customer Wait Time Model"1995 NYNEX "The Arachne Network Planning System"1995 Sainsbury's "An Information Systems Strategy for Sainsbury’s"1995 SADIA "Integrated Planning for Poultry Production"1994 Tata Iron & Steel Company, Ltd.* "Strategic and Operational Management with Optimization at Tata Steel"1994 Bellcore "SONET Toolkit: A Decision Support System for the Design of Robust and Cost-
Effective Fiber-Optic Networks"1994 Chinese State Planning Commission and the World "Investment Planning for China’s Coal and Electricity Delivery System"1994 Digital Equipment Corp. "Global Supply Chain Management at Digital Equipment Corp."1994 Hanshin Expressway Public Corporation "Traffic Control System on the Hanshin Expressway"1994 U.S. Army "An Analytical Approach to Reshaping the Army"1993 AT&T* "AT&T's Call Processing Simulator (CAPS) Operational Design for Inbound Call
Centers"1993 Frank Russell Company & The Yasuda Fire and Marine
Insurance Co. Ltd."An Asset/Liability Model for a Japanese Insurance Company Using Multistage Stochastic Programming"
1993 North Carolina Department of Public Instruction "Data Envelopment Analysis of Nonhomogeneous Units: Improving Pupil Transportation in North Carolina"
1993 National Aeronautic and Space Administration (NASA) "Management of the Heat Shield of the Space Shuttle Orbiter: Priorities and Recommendations Based on Risk Analysis"
1993 Delta Airlines "COLDSTART: Daily Fleet Assignment Model"1993 Bellcore "An Optimization Approach to Analyzing Price Quotations Under Business Volume
Discounts"
FINALISTAS EDELMAN 1984-2007Ano Empresa Título do Trabalho1985 Weyerhaeuser Company* Weyerhaeuser Decision Simulator Improves Timber Profits1985 Canadian National Railways "Cost Effective Strategies for Expanding Rail-Line Capacity Using Simulation and
Parametric Analysis"1985 Pacific Gas and Electric Company "PG&E's State-of-the-Art Scheduling Tool for Hydro Systems"1985 New York, NY, Department of Sanitation "Polishing the Big Apple"1985 Eletrobras and CEPEL, Brazil Coordinating the Energy Generation of the Brazilian System1985 United Airlines United Airlines Station Manpower Planning System1984 Blue Bell, Inc.* Blue Bell Trims Its Inventory1984 The Netherlands Rijkswaterstaat and the Rand Planning the Netherlands' Water Resources1984 Austin, Texas, Emergency Medical Services Determining Emergency Medical Service Vehicle Deployment 1984 Pfizer, Inc. "Inventory Management at Pfizer Pharmaceuticals"1984 Monsanto Corporation "Chemical Production Optimization"1984 U.S. Air Force "Improving Utilization of Air Force Cargo Aircraft"
Como construir Modelos Matemáticos?
Classification of Mathematical Models
Classification by the model purpose– Optimization models– Prediction models
Classification by the degree of certainty of the data in the model
– Deterministic models– Probabilistic (stochastic) models
Mathematical Modeling
A constrained mathematical model consists of
– An objective: Function to be optimised with one or more Control /Decision Variables
Example: Max 2x – 3y; Min x + y
– One or more constraints: Functions (“”, “”, “=”) with one or more Control /Decision Variables
Examples: 3x + y 100; x - 4y 100; x + y 10;
New Office Furniture Example
Products
Desks
Chairs
Molded Steel
Profit
$50
$30
$6 / pound
Raw Steel Used
7 pounds (2.61 kg.)
3 pounds (1.12 kg.)
1.5 pounds (0.56 kg.)
1 pound (troy) = 0.373242 kg.
Defining Control/Decision Variables
Ask, “Does the decision maker have the authority to decide the numerical value (amount) of the item?”
If the answer “yes” it is a control/decision variable.
By very precise in the units (and if appropriate, the time frame) of each decision variable.
D: amount of desks (number)C: amount of chairs (number)M: amount of molded steel (pound)
Objective FunctionThe objective of all optimization models, is to
figure out how to do the best you can with what you’ve got.
“The best you can” implies maximizing something (profit, efficiency...) or minimizing something (cost, time...).
Total Profit = 50 D + 30 C + 6 M
Products
Desks
Chairs
Molded Steel
Profit
$50
$30
$6 / pound
D: amount of desks (number)C: amount of chairs (number)M: amount of molded steel (pound)
Writing Constraints Create a limiting condition for each scarce resource :
(amount of a resource required) (“”, “”, “=”) (resource availability)
Make sure the units on the left side of the relation are the same as those on the right side.
Use mathematical notation with known or estimated values for the parameters and the previously defined symbols for the decision/control variables.
Rewrite the constraint, if necessary, so that all terms involving the decision variables are on the left side of the relationship, with only a constant value on the right side
New Office Furniture Example
If New Office has only 2000 pounds (746.5 kg) of raw steel available for production.
7 D + 3 C + 1.5 M 2000
Products
Desks
Chairs
Molded Steel
Raw Steel Used
7 pounds (2.61 kg.)
3 pounds (1.12 kg.)
1.5 pounds (0.56 kg.)
D: amount of desks (number)C: amount of chairs (number)M: amount of molded steel (pound)
Special constraints or Variable Constraint
Variable Constraint
Non negativity constraintLower bound constraintUpper bound constraintInteger constraintBinary constraint
Mathematical Expression
X0X L (a number other than 0)X UX = integerX = 0 or 1
Writing Constraints
No production can be negative;D 0, C 0, M 0
To satisfy contract commitments; • at least 100 desks, and • due to the availability of seat cushions, no more than 500 chairs must be produced.
D 100, C 500
Quantities of desks and chairs produced during the production must be integer valued.
D, C integers
New Office Furniture Example
Example Mathematical ModelMAXIMIZE Z = 50 D + 30 C + 6 M (Total Profit)
SUBJECT TO: 7 D + 3 C + 1.5 M 2000 (Raw Steel) D 100 (Contract) C 500 (Cushions) D 0, C 0, M 0 (Nonnegativity) D and C are integers
Best or Optimal Solution:100 Desks, 433 Chairs,
0.67 pounds Molded SteelTotal Profit: $17,994
Example - Delta Hardware Stores
Problem Statement
Delta Hardware Stores is aregional retailer withwarehouses in three cities in California
San JoseFresno
Azusa
Delta Hardware Stores
Problem Statement
Each month, Delta restocks its warehouses with its own brand of paint.
Delta has its own paint manufacturing plant in Phoenix, Arizona.
San Jose
Fresno
Azusa
Phoenix
Although the plant’s production capacity is sometime inefficient to meet monthly demand, a recent feasibility study commissioned by Delta found that it was not cost effective to expand production capacity at this time.
To meet demand, Delta subcontracts with a national paint manufacturer to produce paint under the Delta label and deliver it (at a higher cost) to any of its three California warehouses.
Delta Hardware StoresProblem Statement
Given that there is to be no expansion of plant capacity, the problem is to determine a least cost distribution scheme of paint produced at its manufacturing plant and shipments from the subcontractor to meet the demands of its California warehouses.
Delta Hardware StoresProblem Statement
Decision maker has no control over demand, production capacities, or unit costs.
The decision maker is simply being asked, “How much paint should be shipped this month (note the time frame) from
the plant in Phoenix to San Jose, Fresno, and Asuza”
and
“How much extra should be purchased from the subcontractor and sent to each of the three cities to satisfy their orders?”
Delta Hardware StoresVariable Definition
X1 : amount of paint shipped this month from Phoenix to San Jose
X2 : amount of paint shipped this month from Phoenix to Fresno
X3 : amount of paint shipped this month from Phoenix to Azusa
X4 : amount of paint subcontracted this month for San Jose
X5 : amount of paint subcontracted this month for Fresno
X6 : amount of paint subcontracted this month for Azusa
Delta Hardware Stores: Decision/Control Variables
NationalSubcontractorX4
X 5
X 6
X1
X2
X3
San Jose
Fresno
Azusa Phoenix
Network Model
The objective is to minimize the total overall monthly costs of manufacturing, transporting and subcontracting paint,
The constraints are (subject to):
The Phoenix plant cannot operate beyond its capacity;
The amount ordered from subcontractor cannot exceed a maximum limit;
The orders for paint at each warehouse will be fulfilled.
Delta Hardware Stores
To determine the overall costs: The manufacturing cost per 1000 gallons of paint at the plant in
Phoenix - (M) The procurement cost per 1000 gallons of paint from National
Subcontractor- (C)
The respective truckload shipping costs form Phoenix to San Jose, Fresno, and Azusa- (T1, T2, T3)
The fixed purchase cost per 1000 gallons from the subcontractor to San Jose, Fresno, and Azusa(S1, S2, S3)
Delta Hardware Stores
MINIMIZE (M + T1) X1 + (M + T2) X2 + (M + T3) X3 +
(C + S1) X4 + (C + S2) X5 + (C + S3) X6
Delta Hardware Stores: Objective Function
Where:Manufacturing cost at the plant in Phoenix: MProcurement cost from National Subcontractor: CTruckload shipping costs from Phoenix to San Jose, Fresno, and Azusa: T1, T2, T3
Fixed purchase cost from the subcontractor to San Jose, Fresno, and Azusa: S1, S2, S3
X1 : amount of paint shipped this month from Phoenix to San Jose
X2 : amount of paint shipped this month from Phoenix to Fresno
X3 : amount of paint shipped this month from Phoenix to Azusa
X4 : amount of paint subcontracted this month for San Jose
X5 : amount of paint subcontracted this month for Fresno
X6 : amount of paint subcontracted this month for Azusa
To write to constraints, we need to know:
The capacity of the Phoenix plant(Q1)
The maximum number of gallons available from the subcontractor(Q2)
The respective orders for paint at the warehouses in San Jose, Fresno, and Azusa(R1, R2, R3)
Delta Hardware StoresConstraints
The number of truckloads shipped out from Phoenix cannot exceed the plant capacity: X1 + X2 + X3 Q1
The number of thousands of gallons ordered from the subcontrator cannot exceed the order limit:X4 + X5 + X6 Q2
The number of thousands of gallons received at each warehouse equals the total orders of the warehouse: X1 + X4 = R1 X2 + X5 = R2 X3 + X6 = R3
All shipments must be nonnegative and integer: X1, X2, X3, X4, X5, X6 0 X1, X2, X3, X4, X5, X6 integer
Delta Hardware StoresConstraints
Respective Orders: R1 = 4000, R2 = 2000, R3 = 5000 (gallons)
Capacity: Q1 = 8000, Q2 = 5000 (gallons)
Subcontractor price per 1000 gallons: C = $5000
Cost of production per 1000 gallons: M = $3000
Delta Hardware StoresData Collection and Model Selection
Transportation costs per 1000 gallons
Subcontractor: S1 = $1200; S2 = $1400; S3 = $1100
Phoenix Plant: T1 = $1050; T2 = $750; T3 = $650
Delta Hardware StoresData Collection and Model Selection
Min (3000+1050)X1+(3000+750)X2+(3000+650)X3+(5000+1200)X4+(5000+1400)X5+(5000+1100)X6
Ou
MIN 4050 X1 + 3750 X2 + 3650 X3 + 6200 X4 + 6400 X5 + 6100 X6
SUBJECT TO: X1 + X2 + X3 8000 (Plant Capacity)X4 + X5 + X6 5000 (Upper Bound - order from
subcontracted)X1 + X4 = 4000 (Demand in San Jose)X2 + X5 = 2000 (Demand in Fresno)X3 + X6 = 5000 (Demand in Azusa)X1, X2, X3, X4, X5, X6 0 (non negativity)X1, X2, X3, X4, X5, X6 integer
Delta Hardware StoresOperations Research Model
X1 = 1,000 gallons
X2 = 2,000 gallons
X3 = 5,000 gallons
X4 = 3,000 gallons
X5 = 0
X6 = 0
Cost = $48,400
Delta Hardware StoresSolutions
Uma empresa está planejando expandir suas atividades abrindo dois novos CD’s, sendo que há três Locais sob estudo para a instalação destes CD’s (Figura 1 adiante). Quatro Clientes devem ter atendidas suas Demandas (Ci): 50, 100, 150 e 200.
As Capacidades de Armazenagem (Aj) em cada local são: 350, 300 e 200. Os Investimentos Iniciais em cada CD são: $50, $75 e $90. Os Custos Unitários de Operação em cada CD são: $5, $3 e $2.
Admita que quaisquer dois locais são suficientes para atender toda a demanda existente, mas o Local 1 só pode atender Clientes 1, 2 e 4; o Local 3 pode atender Clientes 2, 3 e 4; enquanto o Local 2 pode atender todos os Clientes. Os Custos Unitários de Transporte do CD que pode ser construído no Local i ao Cliente j (Cij) estão dados na Figura 1.
Deseja-se selecionar os locais apropriados para a instalação dos CD’s de forma a minimizar o custo total de investimento, operação e distribuição.
Case em Logística – Encontrar um Modelo de Pesquisa Operacional para a Expansão de Centros de Distribuição - CD
Rede Logística, com Demandas (Clientes), Capacidades (Armazéns) e Custos de Transporte (Armazém-Cliente)
A1=350 C2 = 100
C1 = 50A2 =300
C3=150
A3=200C4=200
C12=9
C14=12
C24=4
C34=7
C23=11
C33=13
C32=2
C22=7
C21=10
C11=13
Figura 1
Variáveis de Decisão/Controle:
Xij = Quantidade enviada do CD i ao Cliente j
Li é variável binária, i {1, 2, 3} sendo
Li =
1, se o CD i for instalado
0, caso contrário
Modelagem
Função Objetivo: Minimizar CT = Custo Total de Investimento + Operação + Distribuição
CT = 50L1 + 5(X11 + X12 + X14) + 13X11 + 9X12 + 12X14 +
+ 75L2 + 3(X21+X22+X23+X24) + 10X21+7X22+11X23+4X24 +
+ 90L3 + 2(X32 + X33 + X34) + 2X32 + 13X33 + 7X34
Cancelando os termos semelhantes, tem-se
CT = 50L1 + 75L2 + 90L3 + 18X11 + 14X12 + 17X14 + 13X21+
+ 10X22+14X23+7X24 + 4X32 + 15X33 + 9X34
Restrições: sujeito a
X11 + X12 + X14 350L1
X21 + X22 + X23 + X24 300L2
X32 + X33 + X34 200L3
L1 + L2 + L3 = 2 Instalar 2 CD’s
X11 + X21 = 50
X12 + X22 + X32 = 100
X23 + X33 = 150
X14 + X24 + X34 = 200
Xij 0
Li {0, 1}
Produção
Demanda
Não - Negatividade
Integralidade
