Pesquisa Operacional Aplicada à Logística
Prof. Fernando Augusto Silva Marins
[email protected]
www.feg.unesp.br/~fmarins
Sumário
 Introdução à Pesquisa Operacional (P.O.)
 Impacto da P.O. na Logística
 Modelagem e Softwares
Exemplos
Cases em Logística
Pesquisa Operacional (P.O.)
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-2007
Ano
1996
1996
1996
1996
1996
1996
1996
1995
1995
1995
1995
1995
1995
1994
1994
1994
1994
1994
1994
1993
1993
1993
1993
1993
1993
Empresa
South African National Defense Force*
Título do Trabalho
"Guns or Butter: Decision Support for Determining the Size and Shape of the
South African National Defense Force (SANDF)"
The Finance Ministry of Kuwait
"The Use of Linear Programming in Disentangling the Bankruptcies of al-Manakh
Stock Market Crash
AT&T Capital
"Credit and Collections Decision Automation in AT&T Capital's Small-Ticket
Business"
British National Health Service
"A New Formula for Distributing Hospital Funds in England"
National Car Rental System, Inc.
"Revenue Management Program"
Procter and Gamble
"North American Product Supply Restructuring at Procter & Gamble"
Federal Highway Administration/California Department "PONTIS: A System for Maintenance Optimization and Improvement of U.S.
of Transportation
Bridge Networks "
Harris Corporation/Semiconductor Sector*
"IMPReSS: An Automated Production-Planning and Delivery-Quotation System at
Harris Corporation - Semiconductor Sector"
Israeli Air Force
"Air Power Multiplier Through Management Excellence"
KeyCorp
"The Teller Productivity System and Customer Wait Time Model"
NYNEX
"The Arachne Network Planning System"
Sainsbury's
"An Information Systems Strategy for Sainsbury’s"
SADIA
"Integrated Planning for Poultry Production"
Tata Iron & Steel Company, Ltd.*
"Strategic and Operational Management with Optimization at Tata Steel"
Bellcore
"SONET Toolkit: A Decision Support System for the Design of Robust and CostEffective Fiber-Optic Networks"
Chinese State Planning Commission and the World
"Investment Planning for China’s Coal and Electricity Delivery System"
Digital Equipment Corp.
"Global Supply Chain Management at Digital Equipment Corp."
Hanshin Expressway Public Corporation
"Traffic Control System on the Hanshin Expressway"
U.S. Army
"An Analytical Approach to Reshaping the Army"
AT&T*
"AT&T's Call Processing Simulator (CAPS) Operational Design for Inbound Call
Centers"
Frank Russell Company & The Yasuda Fire and Marine "An Asset/Liability Model for a Japanese Insurance Company Using Multistage
Insurance Co. Ltd.
Stochastic Programming"
North Carolina Department of Public Instruction
"Data Envelopment Analysis of Nonhomogeneous Units: Improving Pupil
Transportation in North Carolina"
National Aeronautic and Space Administration (NASA) "Management of the Heat Shield of the Space Shuttle Orbiter: Priorities and
Recommendations Based on Risk Analysis"
Delta Airlines
"COLDSTART: Daily Fleet Assignment Model"
Bellcore
"An Optimization Approach to Analyzing Price Quotations Under Business Volume
Discounts"
FINALISTAS EDELMAN 1984-2007
Ano Empresa
1985 Weyerhaeuser Company*
1985 Canadian National Railways
1985
1985
1985
1985
1984
1984
1984
1984
1984
1984
Pacific Gas and Electric Company
New York, NY, Department of Sanitation
Eletrobras and CEPEL, Brazil
United Airlines
Blue Bell, Inc.*
The Netherlands Rijkswaterstaat and the Rand
Austin, Texas, Emergency Medical Services
Pfizer, Inc.
Monsanto Corporation
U.S. Air Force
Título do Trabalho
Weyerhaeuser Decision Simulator Improves Timber Profits
"Cost Effective Strategies for Expanding Rail-Line Capacity Using Simulation and
Parametric Analysis"
"PG&E's State-of-the-Art Scheduling Tool for Hydro Systems"
"Polishing the Big Apple"
Coordinating the Energy Generation of the Brazilian System
United Airlines Station Manpower Planning System
Blue Bell Trims Its Inventory
Planning the Netherlands' Water Resources
Determining Emergency Medical Service Vehicle Deployment
"Inventory Management at Pfizer Pharmaceuticals"
"Chemical Production Optimization"
"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
Profit
Raw Steel Used
Desks
$50
7 pounds (2.61 kg.)
Chairs
$30
3 pounds (1.12 kg.)
Molded Steel
$6 / pound
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 Function
The 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
Profit
Desks
$50
Chairs
$30
Molded Steel
$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
D: amount of desks (number)
C: amount of chairs (number)
M: amount of molded steel (pound)

2000
Products
Raw Steel Used
Desks
7 pounds (2.61 kg.)
Chairs
3 pounds (1.12 kg.)
Molded Steel 1.5 pounds (0.56 kg.)
Writing Constraints

Special constraints or Variable Constraint
Variable Constraint
Mathematical Expression
Non negativity constraint
Lower bound constraint
Upper bound constraint
Integer constraint
Binary constraint
X 0
X  L (number  0)
X  U (number  0)
X = integer  {0, 1, 2, 3, 4 ,…}
X = 0 or 1
New Office Furniture Example

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
Example Mathematical Model
MAXIMIZE
Z = 50 D + 30 C + 6 M
SUBJECT TO: 7 D + 3 C + 1.5 M  2000
D
 100
C
 500
D  0, C  0, M  0
D and C
(Total Profit)
(Raw Steel)
(Contract)
(Cushions)
(Nonnegativity)
are integers
Best or Optimal Solution:
100 Desks, 433 Chairs,
0.67 pounds Molded Steel
Total Profit: $17,994
Ver Modelo no Lindo
Delta Hardware Stores
Problem Statement
Delta Hardware Stores is a
regional retailer with
warehouses in three cities in
California
San Jose
Fresno
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
Phoenix
Azusa
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.
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.
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?”
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
Network Model and Decision
Variables
San Jose
National
Subcontractor
Fresno
Azusa
Phoenix
Model Structure
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.
Costs
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)
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
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)
Constraints (Cont.)
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
Data Collection and Model Selection
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
Data Collection and Model Selection
(Cont.)
Transportation costs per 1000 gallons
Subcontractor: S1 = $1200; S2 = $1400; S3 = $1100
Phoenix Plant: T1 = $1050; T2 = $750;
T3 = $650
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:
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 Stores
Solutions
X1 = 1,000 gallons
X2 = 2,000 gallons
X3 = 5,000 gallons
X4 = 3,000 gallons
X5 = 0
X6 = 0
Cost = $48,400
Ver Modelo no Excel
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.
CARLTON PHARMACEUTICALS

Data
–
Unit shipping cost, supply, and demand
To
From
Cleveland
Detroit
Greensboro
Demand

Boston
$35
37
40
1100
Richmond
30
40
15
400
Atlanta
40
42
20
750
St. Louis
32
25
28
750
Supply
1200
1000
800
Assumptions
– Unit shipping costs are constant.
– All the shipping occurs simultaneously.
– The only transportation considered is between sources and destinations.
– Total supply equals total demand.
CARLTON PHARMACEUTICALS
Network presentation
Sources
Cleveland
S1=1200
Destinations
D1=1100
Boston
Richmond
D2=400
Detroit
S2=1000
Atlanta
D3=750
Greensboro
S3= 800
St.Louis
D4=750
CARLTON PHARMACEUTICALS –
Linear Programming Model
–
The structure of the model is:
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)
Minimize Total Shipping Cost
ST
[Amount shipped from a source]  [Supply at that source]
[Amount received at a destination] = [Demand at that destination]
Supply from Cleveland X11+X12+X13+X14  1200
Supply constraints
Supply from Detroit X21+X22+X23+X24  1000
Supply from Greensboro X31+X32+X33+X34  800
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
D3=750
X34
D4=750
CARLTON PHARMACEUTICAL –
The complete mathematical model
Min 35X11+30X12+40X13+ 32X14 +37X21+40X22+42X23+25X24+ 40X31+15X32+20X33+38X34
ST
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+
X32
X23+
X14+
All Xij are nonnegative
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:E9)
Drag to cells C11:E11
CARLTON PHARMACEUTICALS
Spreadsheet
MINIMIZE Total Cost
SHIPMENTS
Demands are met
Supplies are not
exceeded
CARLTON PHARMACEUTICALS
Spreadsheet - solution
CARLTON PHARMACEUTICALS
SOLUTION
MINIMUM COST
CLEVELAND
DETROIT
GREENSBORO
RECEIVED
INPUT
CLEVELAND
DETROIT
GREENSBORO
DEMAND
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
CARLTON PHARMACEUTICALS - Sensitivity Report
Adjustable Cells
– 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.
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
–
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
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
• 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.
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
– 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 - shipments along certain routes are prohibited.
Remedies:
–
Assign a large objective coefficient to the route (Cij = 1,000,000)
Modifications to the transportation problem
–
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 blocked route
(like as Cij = 1,000,000)
– Add a constraint to Excel solver of the form Xij = 0
Shipments on a
Blocked Route
=0
Only Feasible Routes
Included in Changing Cells
Cell C9 is NOT Included
Modifications to the transportation problem
–
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 (Cij = 1,000,000)
– Add a constraint to Excel solver of the form Xij = 0
– Do not include the cell representing the rout in the Changing cells
Shipments from Greensboro
to Cleveland are prohibited
Modifications to the transportation problem
– 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.
The Capacitated Transshipment Model


Sometimes shipments to destination nodes are made
through transshipment nodes.
Transshipment nodes may be
–
–

Independent intermediate nodes with no supply or demand
Supply or destination points themselves.
Transportation on arcs may be bounded by given
bounds
The Capacitated Transshipment Model

The Linear Programming Model of this problem consists
of:
–
–
–
Flow on arcs decision variables
Cost minimization objective function
Balance constraints on each node as follows:



–
Supply node – net flow out does not exceed the supply
Intermediate node – flow into the node is equal to the flow out
Demand node – net flow into the node is equal to the demand
Bound constraints on each arc. Flow cannot exceed the
capacity on the arc
DEPOT MAX
A General Network Problem

Depot Max has six stores located in the Washington
D.C. area.
DEPOT MAX
• The stores in Falls Church (FC) and Bethesda (BA)
are running low on the model 5A Arcadia workstation.
• DATA:
5
-12
FC
-13
6
BA
DEPOT MAX
• The stores in Alexandria (AA) and Chevy Chase (CC)
have an access of 25 units.
• DATA:
+10
AA
+17
CC
1
5
-12
FC
-13
2
6
BA
DEPOT MAX
• The stores in Fairfax and Georgetown are transshipment
nodes with no access supply or demand of their own.
• DATA:
+10
AA
FX
1
3
0
5
-12
FC
• Depot Max wishes to transport the available
workstations to FC and BA at minimum total cost.
GN
+17
CC
2
4
0
6
-13
BA
DEPOT MAX

Data
–
–
There is a maximum limit for quantities shipped on various
routes.
There are different unit transportation costs for different
routes.
DEPOT MAX
• The possible routes and the maximum flow limits are shown.
• DATA:
+10
AA
6
10
1
7
3
FX
3
8
8
FC
5
7
GN
+17
CC
2
10
4
17
-12
FC
BA
-13
BA
DEPOT MAX
• The possible routes and the shipping unit costs are shown.
• DATA:
+10
AA
20
10
1
6
5
FX
3
7
12
FC
11
7
GN
+17
CC
2
15
4
15
-12
FC
BA
-13
BA
DEPOT MAX – Types of constraints
–Supply nodes:
Net flow out of the node]  [Supply at the node]
–Intermediate transshipment nodes:
[Total flow out of the node] = [Total flow into the node]
X12 + X13 + X15 - X21  10
(Node 1)
X21 + X24 - X12
 17 (Node 2)
X34+X35 = X13
X46 = X24 + X34
(Node3)
(Node 4)
20
+10
10
1
5
3
6
+17
2
7
12
15
-12
5
7
7
11
15
4
–Demand nodes: [Net flow into the node] = [Demand for the node]
X15 + X35 +X65 - X56 = 12
(Node 5)
X46 +X56 - X65 = 13 (Node 6)
6
-13
DEPOT MAX

The Complete mathematical model
Min 5X12 + 10X13 + 20X15 + 6X21
S.T.
10
X12 +
- X12 +
–
12
5
X13 +
X15 –
+ 15X24 + 12X34 + 7X35 + 15X46 + 11X56 + 7X65
X21
X21 +
X13 +
– X15
–
–

X24
X34 +
X24 –
 17
X35
X34 +
=0
=0
X46
X35 +
X56 -
X65
=-
-X46 –
X56 + X65 = -13
X12  3; X15  6; X21  7; X24  10; X34  8; X35  8; X46  17; X56  7; X65 
All variables are non-negative
Usando o Template Network
DEPOT MAX - spreadsheet
NODE INPUT
NODE NAME
SLACK
ARC INPUT
NODE # SUPPLY DEMAND
100
2
FROM
TO
COST CAPACITY
SOLUTION
TOTAL
COST=
645
FROM
TO
FLOW
Alexandria
1
10
1
2
5
3
1
2
Chevy Chase
2
17
1
3
10
12
1
3
9
Fairfax
3
1
5
20
6
1
5
6
Georgetown
4
2
1
6
7
2
1
5
Falls Church
5
12
2
4
15
10
2
4
10
Betheda
6
13
3
4
12
8
3
4
1
3
5
7
8
3
5
8
4
6
15
17
4
6
11
5
6
11
7
5
6
2
6
5
7
5
6
5
Case em Logística
Modelo de Pesquisa Operacional
Expansão de Centros de Distribuição - CD
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 do slide seguinte.
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.
Figura 1
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
C33=13
A3=200
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 =
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
Ver Modelo no Lindo
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
Solução do Case em Logística
OBJECTIVE FUNCTION VALUE = 4815.0
VARIABLE VALUE
L1
0.0
L2
1.0
L3
1.0
X11
0.0
X12
0.0
X14
0.0
X21
50.0
X22
0.0
X23
50.0
X24
200.0
X32
100.0
X33
100.0
X34
0.0
REDUCED COST
50.0
75.0
90.0
18.0
14.0
17.0
13.0
10.0
14.0
7.0
4.0
15.0
9.0