Pesquisa Operacional
Aplicada à Logística
Prof. Fernando Augusto Silva Marins
www.feg.unesp.br/~fmarins
[email protected]
1
Pesquisa Operacional faz diferença
no desempenho de organizações?
2
Finalistas do Prêmio Edelman
3
INFORMS 2007
• Questões Logísticas
• (Pesquisa Operacional)
4
Delta Hardware Stores
Problem Statement
San Jose
Fresno
• Delta Hardware Stores
is a regional retailer
with warehouses in
three cities in California
5
Azusa
• 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
Phoenix
Azusa
6
Delta Hardware Stores
Problem Statement
• 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.
7
Delta Hardware Stores
Problem 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.
8
Delta Hardware Stores
Variable Definition
• 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?”
9
Decision/Control Variables:
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
10
Network Model
San Jose
National
Subcontractor
Fresno
Azusa
11
Phoenix
Mathematical Model
•
The objective is to minimize the total overall
monthly costs of manufacturing, transporting and
subcontracting paint,
The constraints are (subject to):
12

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.
Mathematical Model
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)
13
Mathematical Model: Objective Function
Minimize
(M + T1) X1 + (M + T2) X2 + (M + T3) X3 +
(C + S1) X4 + (C + S2) X5 + (C + S3) X6
Where:
Manufacturing cost at the plant in Phoenix: M
Procurement cost from National Subcontractor: C
Truckload 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
14
Mathematical Model: Constraints
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)
15
Mathematical Model: Constraints
• 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
16
Mathematical Model: Data Collection
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
17
Mathematical Model: Data Collection
Transportation costs $ per 1000 gallons
Subcontractor: S1=$1200; S2=$1400;
S3= $1100
Phoenix Plant: T1 = $1050;T2 = $750;
T3 = $650
18
Delta Hardware Stores
Operations Research Model
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:
19
X1 + X2 + X3  8000 (Plant Capacity)
X4 + X5 + X6  5000 (Upper Bound order from subcont.)
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 (nonnegativity)
X1, X2, X3, X4, X5, X6 integer
Delta Hardware Stores
Solutions
X1 = 1,000 gallons
X2 = 2,000 gallons
X3 = 5,000 gallons
X4 = 3,000 gallons
X5 = 0
X6 = 0
Optimum Total Cost = $48,400
20
CARLTON PHARMACEUTICALS
• Carlton Pharmaceuticals supplies drugs and
other medical supplies.
• It has three plants in: Cleveland, Detroit,
Greensboro.
• It has four distribution centers in:
Boston, Richmond, Atlanta, St. Louis.
• Management at Carlton would like to ship cases
of a certain vaccine as economically as
possible.
21
CARLTON PHARMACEUTICALS
• Data
– Unit shipping cost, supply, and demand
To
From
Cleveland
Detroit
Greensboro
Demand
Boston
$35
37
40
1100
• Assumptions
Richmond
30
40
15
400
Atlanta
40
42
20
750
St. Louis
32
25
28
750
Supply
1200
1000
800
– Unit shipping costs are constant.
– All the shipping occurs simultaneously.
– The only transportation considered is between sources and
destinations.
– Total supply equals total demand.
22
CARLTON PHARMACEUTICALS
Network presentation
23
Destinations
Sources
D1=1100
Boston
Cleveland
S1=1200
Richmond
D2=400
Detroit
S2=1000
Atlanta
D3=750
Greensboro
S3= 800
24
St.Louis
D4=750
CARLTON PHARMACEUTICALS –
Linear Programming Model
– The structure of the model is:
Minimize Total Shipping Cost
ST
[Amount shipped from a source]  [Supply at that source]
[Amount received at a destination] = [Demand at that
destination]
– Decision variables
Xij = the number of cases shipped from plant i to warehouse j.
where: i=1 (Cleveland), 2 (Detroit), 3 (Greensboro)
j=1 (Boston), 2 (Richmond), 3 (Atlanta), 4(St.Louis)
25
Supply from Cleveland X11+X12+X13+X14  1200
Supply from Detroit X21+X22+X23+X24  1000
Supply from Greensboro X31+X32+X33+X34  800
The supply constraints
Boston
D1=1100
X11
Cleveland
S1=1200
X12
X13
X21
X31
Richmond
X14
X22
Detroit
S2=1000
D2=400
X32
X23
X24
Atlanta
X33
St.Louis
Greensboro
S3= 800
26
D3=750
X34
D4=750
CARLTON
PHARMACEUTICAL –
The complete mathematical model
Minimize 35X11 + 30X12 + 40X13 + 32X14 + 37X21 + 40X22 + 42X23 + 25X24+ + 40X31+15X32
ST
+ 20X33 + 38X34
Total shipment out of a supply node
cannot exceed the supply at the node.
Supply constraints:
X11+ X12+ X13+ X14
X21+ X22+ X23+ X24
X31+ X32+ X33+ X34
Demand constraints:
X11+
X12+
X13+
X21+
X31
X22+
X23+
X14+
All Xij are nonnegative
27
X32
X33
X24+
X34
Total shipment received at a destination
node, must equal the demand at that node.
 1200
 1000
 800
= 1100
= 400
= 750
= 750
CARLTON PHARMACEUTICALS
Spreadsheet
=SUMPRODUCT(B7:E9,B15:E17)
=SUM(B7:E7)
Drag to cells
G8:G9
=SUM(B7:B9)
Drag to cells C11:E11
28
CARLTON PHARMACEUTICALS
Spreadsheet
MINIMIZE Total Cost
SHIPMENTS
Demands are met
Supplies are not
exceeded
29
CARLTON PHARMACEUTICALS
Spreadsheet - solution
CARLTON PHARMACEUTICALS
SOLUTION
MINIMUM COST
CLEVELAND
DETROIT
GREENSBORO
RECEIVED
INPUT
CLEVELAND
DETROIT
GREENSBORO
DEMAND
30
84000
SHIPMENTS (CASES)
BOSTON RICHMOND ATLANTA ST. LOUIS
850
350
250
750
50
750
1100
400
750
COST (PER CASE)
BOSTON RICHMOND ATLANTA ST.
35
30
40
37
40
42
40
15
20
1100
400
750
SHIPPED
1200
1000
800
750
LOUIS
32
25
28
750
SUPPLY
1200
1000
800
CARLTON PHARMACEUTICALS
Sensitivity Report
– Reduced costs
• The unit shipment cost between Cleveland and Atlanta must be reduced by at
least $5, before it would become economically feasible to utilize it
• If this route is used, the total cost will increase by $5 for each case shipped
between the two cities.
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell
Name
Value
Cost
Coefficient Increase Decrease
$B$7 CLEVELAND BOSTON
850
0
35
2
5
$C$7 CLEVELAND RICHMOND
350
0
30
5
17
$D$7 CLEVELAND ATLANTA
0
5
40
1E+30
5
$E$7 CLEVELAND ST. LOUIS
0
9
32
1E+30
9
$B$8 DETROIT BOSTON
250
0
37
5
2
$C$8 DETROIT RICHMOND
0
8
40
1E+30
8
$D$8 DETROIT ATLANTA
0
5
42
1E+30
5
$E$8 DETROIT ST. LOUIS
750
0
25
9
1E+30
$B$9 GREENSBORO BOSTON
0
20
40
1E+30
20
$C$9 GREENSBORO RICHMOND
50
0
15
17
5
$D$9 GREENSBORO ATLANTA
750
0
20
5
1E+30
$E$9 GREENSBORO ST. LOUIS
0
20
28
1E+30
20
31
CARLTON PHARMACEUTICALS
Sensitivity Report
– Allowable Increase/Decrease
• This is the range of optimality.
• The unit shipment cost between Cleveland and Boston may increase
up to $2 or decrease up to $5 with no change in the current optimal
transportation plan.
Adjustable Cells
Final Reduced Objective Allowable Allowable
Cell
Name
Value
Cost
Coefficient Increase Decrease
$B$7 CLEVELAND BOSTON
850
0
35
2
5
$C$7 CLEVELAND RICHMOND
350
0
30
5
17
$D$7 CLEVELAND ATLANTA
0
5
40
1E+30
5
$E$7 CLEVELAND ST. LOUIS
0
9
32
1E+30
9
$B$8 DETROIT BOSTON
250
0
37
5
2
$C$8 DETROIT RICHMOND
0
8
40
1E+30
8
$D$8 DETROIT ATLANTA
0
5
42
1E+30
5
$E$8 DETROIT ST. LOUIS
750
0
25
9
1E+30
$B$9 GREENSBORO BOSTON
0
20
40
1E+30
20
$C$9 GREENSBORO RICHMOND
50
0
15
17
5
$D$9 GREENSBORO ATLANTA
750
0
20
5
1E+30
$E$9 GREENSBORO ST. LOUIS
0
20
28
1E+30
20
32
CARLTON PHARMACEUTICALS
Sensitivity Report
– Shadow prices
• For the plants, shadow prices convey the cost savings realized
for each extra case of vaccine produced.
For each additional unit available in Cleveland the total cost
reduces by $2.
Constraints
Cell
$G$7
$G$8
$G$9
$B$11
$C$11
$D$11
$E$11
33
Name
CLEVELAND SHIPPED
DETROIT SHIPPED
GREENSBORO SHIPPED
RECEIVED BOSTON
RECEIVED RICHMOND
RECEIVED ATLANTA
RECEIVED ST. LOUIS
Final Shadow Constraint Allowable Allowable
Value
Price
R.H. Side Increase Decrease
1200
-2
1200
250
0
1000
0
1000
1E+30
0
800
-17
800
250
0
1100
37
1100
0
250
400
32
400
0
250
750
37
750
0
250
750
25
750
0
750
CARLTON PHARMACEUTICALS
Sensitivity Report
Constraints
Cell
$G$7
$G$8
$G$9
$B$11
$C$11
$D$11
$E$11
Name
CLEVELAND SHIPPED
DETROIT SHIPPED
GREENSBORO SHIPPED
RECEIVED BOSTON
RECEIVED RICHMOND
RECEIVED ATLANTA
RECEIVED ST. LOUIS
Final Shadow Constraint Allowable Allowable
Value
Price
R.H. Side Increase Decrease
1200
-2
1200
250
0
1000
0
1000
1E+30
0
800
-17
800
250
0
1100
37
1100
0
250
400
32
400
0
250
750
37
750
0
250
750
25
750
0
750
– Shadow prices
34
• For the warehouses demand, shadow
prices represent the cost savings for
less cases being demanded.
For each one unit decrease in
demanded in Richmond, the total cost
decreases by $32.
– Allowable Increase/Decrease
• This is the range of feasibility.
• The total supply in Cleveland may
increase up to $250, but doesn´t may
decrease up, with no change in the
current optimal transportation plan.
Modifications to the
Transportation Problem
Cases may arise that require
modifications to the basic model:
- Blocked Routes
- Minimum shipment
- Maximum shipment
35
Cases may arise that require modifications to the
basic model:
Blocked routes - shipments along certain routes are prohibited
Remedies:
– Assign a large objective coefficient to the route
of the form Cij = 1,000,000
– Add a constraint to Excel solver of the form Xij = 0
Shipments
on a Blocked
Route = 0
36
Cases may arise that require modifications to the
basic model:
Blocked routes - shipments along certain routes are prohibited
Remedy:
- Do not include the cell representing the route in the Changing
cells
Shipments from Greensboro
to Cleveland are prohibited
37
Only Feasible Routes Included in
Changing Cells
Cell C9 is NOT Included
Cases may arise that require modifications to
the basic model:
• Minimum shipment - the amount shipped
along a certain route must not fall below a
pre-specified level.
–Remedy: Add a constraint to Excel of the
form Xij  B
• Maximum shipment - an upper limit is placed
on the amount shipped along a certain route.
–Remedy: Add a constraint to Excel of the
form Xij  B
38
Problema (Desbalanceado) de Max Lucro com
possibilidade de estoque remanescente
Uma empresa tem 3 fábricas e 4 clientes, referentes a um determinado
produto, e conhece-se os dados abaixo:
Fábrica
Capacidade
Custo de
mensal da
produção
Demanda
Cliente
mensal
Preço de
venda
produção
($/unidade)
F1
85
50
C1
100
100
F2
90
30
C2
80
110
F3
75
40
C3
20
105
C4
40
125
Total
240
Total
250
($/unidade)
39
39
Problema (Desbalanceado) de Max de Lucro
com possibilidade de estoque remanescente
Conhecem-se os custos de se manter o produto em estoque
($/unidade estocada) nas Fábricas 1 e 2: $1 para estocagem na
Fábrica 1, $2 para estocagem na Fábrica 2. Sabe-se que a Fábrica 3
não pode ter estoques.
Os custos de transporte ($/unidade) são:
Local de
Locais de Venda
Fabricação
C1
C2
C3
C4
F1
43
57
33
60
F2
30
49
25
47
F3
44
58
33
64
Encontrar o programa de distribuição que proporcione lucro
máximo. Formule o modelo de PL e aplique o Solver do Excel para
40
40 resolvê-lo.
Modelo de PO para a Expansão de Centros
de Distribuição
•
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 (slide 67).
• 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.
41
Rede Logística, com Demandas (Clientes),
Capacidades (Armazéns) e Custos de
•
Transporte (Armazém-Cliente)
A1=350
C2 = 100
C12=9
C11=13
C22=7
C21=10
C14=12
C1 = 50
A2 =300
C32=2
C23=11
C3=150
C24=4
C4=200
C34=7
A3=200
Figura 1
42
C33=13
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
1, se o CD i for instalado
Li =
43
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
44
Restrições: sujeito a
X11 + X12 + X14  350L1
Produção
X21 + X22 + X23 + X24  300L2
X32 + X33 + X34  200L3
L1 + L2 + L3 = 2
Instalar 2 CD’s
X11 + X21 = 50
X12 + X22 + X32 = 100
Demanda
X23 + X33 = 150
X14 + X24 + X34 = 200
Xij  0
Não - Negatividade
Li  {0, 1}
Integralidade
45
Check Point 10
Problema (Desbalanceado) de Maximização
de Lucro com possibilidade de multa devido
a falta de produto
Uma empresa tem fábricas onde fabrica o mesmo produto.
Existem depósitos regionais e os preços pagos pelos
consumidores são diferentes em cada caso.
Tendo em vista os dados das tabelas a seguir, qual o melhor
programa de produção e distribuição?
Sabe-se que o Cliente 3 é preferencial (tem que ser
atendido totalmente).
Além disso, não é economicamente viável entregar o
produto da Fábrica A ao Cliente 4.
46
Problema (Desbalanceado) de Max Lucro com
possibilidade de multa devido a falta de produto
Fábrica
47
Capacidade
Multas por
mensal da
falta
produção
Cliente
Demanda
mensal
($/unidade)
Preço de
venda
($/unidade)
F1
80
C1
4
90
30
F2
200
C2
5
150
32
F3
100
C3
*M
150
36
F4
100
C4
2
100
34
Total
480
Total
490
*M = valor muito grande, pois C3 é preferencial
47
Problema (Desbalanceado) de Max Lucro
com possibilidade de multa devido a falta de
produto
*M = valor muito grande, pois não é viável a entrega
Local de
Fabrica
Locais de Venda
çã o
C
1
C
2
C
3
C
4
F
1
3
9
5
*M
F
2
1
7
4
6
F
3
5
8
3
3
4
F4
7
8
2
Encontrar o programa de distribuição que proporcione lucro
máximo. Formule o modelo de PL e aplique o Solver do Excel para
resolvê-lo.
48