Faculdade de Engenharia - Campus de Guaratinguetá
Pesquisa Operacional
Livro: Introdução à Pesquisa Operacional
Capítulo 4 – Modelo de Transporte Simples
Fernando Marins – [email protected]
Departamento de Produção
1
Sumário
Modelo de Transporte Simples
Histórico e Características
Modelo Matemático
Modelo em Grafos
“Stepping Stone Algorithm”
Casos Especiais
2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Histórico
• Kantorovich (1939) - problema da distribuição
• Koopman (1941) - problema de transporte
Observação: dividiram o Prêmio Nobel de Economia em 1975.
• Dantzig (1947) - algoritmo eficiente
Características
• Transporte de um produto a partir de várias origens para diversos
destinos.
• Produção ai em cada origem Oi, i = 1, m.
• Demanda bj em cada destino Dj, j = 1, n.
• Custos unitários de transporte cij em cada trajeto Oi - Dj.
3
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Variáveis de decisão:
Xij = quantidade a ser transportada da origem Oi ao destino Dj.
Função objetivo: minimização do custo total transporte
Min C =   Cij Xij
i
Restrições:
j
 Xij = ai, i = 1, m - balanço nas origens
 j

 Xij = bj, j = 1, n - balanço nos destinos
i
Xij  0.

Observação importante:  ai
i
=
 bj
(modelo balanceado)
j
4
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Exemplo: considere situação onde há 3 fábricas produzindo o mesmo
produto e 4 depósitos onde estes produtos são estocados para posterior
venda. As produções nas fábricas são: a1 = 40, a2 = 80, a3 = 110. nos
depósitos devem ser atendidas as seguintes demandas: b1 = 20, b2 = 30,
b3 = 100, b4 = 80. Os custos unitários de transporte do produto são
dados por:
D1
D2
D3
D4
O1
10
5
12
4
O2
2
0
1
9
O3
13
11
14
6
Achar um modelo de PL para determinar o programa de entregas do
produto com mínimo custo de transporte.
5
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Formulação do modelo
Variáveis de decisão: Xij = quantidade de produto enviado de Oi para Dj
Min C = 10X11 + 5X12 + 12X13 + 4X14 + 2X21 + 0X22 + 1X23 + 9X24 + 13X31 +
+ 11X32 + + 14X33 + 6X34
= 40
 X 11 + X12 + X13 + X14

X21 + X22 + X23 + X24
= 80


X31 + X32 + X33 + X34 = 110

Sujeito a: X11
+ X21
+ X31
= 20

X12
+ X22
+ X32
= 30


X13
+ X23
+ X33
= 100

X14
+ X24
+ X34 = 80

Xij  0, i = 1, 3 e j = 1, 4.

6
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Representação matricial das restrições
(excluindo os zeros na matriz de coeficientes das variáveis)
1 1 1 1



1
1
1
1



1 1 1 1


1
1
1


 1

1
1


1
1
1



1
1
1

X=
 40 
 80 
 
110
 
 20 
 30 
 
100
 80 
 
Qualquer equação do sistema de restrições é combinação linear
das demais  no. de equações Linearmente Independentes = (m
+ n -1).
7
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelos em Grafos
(a1= 40) O1
Cij
10
5
12
4
2
(a2=80)
O2
Rede de transporte
D1
(b1=20)
D2 (b2=30)
0
1
9
D3
(b3=100)
D4
(b4=80)
13 11
14
(a3=110) O3
6
8
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Solução Básica Viável = Árvore
Solução Básica Viável equivale a uma Árvore na rede de transporte
com (m + n - 1) = 3 + 4 -1 = 6 variáveis básicas.
Exemplo: x11, x12, x22, x23, x33, x34 são as variáveis básicas.
40
X11= 20
20
X12 = 20
80
X22 = 10
30
X23 = 70
110
X33 = 30
100
X34 = 80
80
Observação: as demais variáveis são não-básicas e nulas.
9
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Algoritmos e Equivalência de Conceitos
entre PL e Grafos
- Método Simplex
- Algoritmo especializado: “Stepping Stone Algorithm”
Toma vantagem da estrutura especial da matriz de restrições de modelos de
transporte formada por “0” e “1”.
Equivalência de Conceitos
Programação Linear
Teoria dos Grafos
Valor da Variável de Decisão
Valor do Fluxo no Arco
Solução Básica Viável
Árvore Viável
Solução Inicial
Árvore Inicial
Coeficiente de Custo Relativo
Coeficiente de Custo Marginal
Variável (Não) Básica
Arco (Não) Básico
Pivoteamento
Balanceamento de Fluxo no Ciclo de compensação
10
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Etapas de aplicação do “Stepping
Stone Algorithm”
Passo 1: Inicialização*
Achar árvore inicial. Ir ao passo 2.
Passo 2: Teste de Otimalidade
Achar os coeficientes de custos (lucros) marginais dos fluxos não-básicos.
Se for árvore ótima  Parar.
Caso contrário escolher arco para entrar na próxima árvore básica. Ir ao passo 3.
Passo 3: Melhoria da solução atual
Achar ciclo de compensação formado pelo arco que entra e a árvore básica atual.
Determinar no ciclo qual arco básico será substituído.
Efetuar o balanceamento de fluxo no ciclo. Voltar ao passo 2.
*Métodos de inicialização do “Stepping Stone Algorithm”:
Regra do canto esquerdo (ou regra do canto noroeste).
Regra do custo mínimo (lucro máximo para problemas de Maximização).
11
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Métodos de inicialização do “Stepping Stone Algorithm”
Regra do canto esquerdo:
Consiste em, iniciando pelo arco (1, 1) ou trajeto O1D1 associado ao
canto superior esquerdo da tabela usada pelo algoritmo, e através de
deslocamentos sucessivos para a direita e para baixo, atingir o canto
inferior direito da tabela, distribuindo a produção disponível nas origens
pelos arcos (chamados arcos básicos) de forma a atender as demandas
nos destinos.
Uma linha (ou coluna) é explorada até que a produção (ou
demanda) desta linha (ou coluna) seja esgotada (ou atendida). Em
cada arco deve-se alocar a maior quantidade de produto possível.
12
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Regra do custo mínimo (ou lucro máximo):
Consiste em atribuir o máximo valor transportável aos trajetos
associados aos menores (ou maiores) custos (ou lucros) unitários de
transporte.
Escolhe-se primeiro o trajeto associado com o menor (ou maior)
custo (ou lucro) unitário, depois o trajeto associado ao próximo
menor (ou maior) custo (ou lucro), e assim por diante até se
esgotar toda a produção disponível e atender toda a demanda
existente.
13
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Aplicação do “Stepping Stone Algorithm”
Tabela inicial com os dados do problema:
D1
O1
O2
O3
Demanda
D2
10
2
13
20
D3
5
0
11
30
D4
12
1
14
100
Produção
40
80
110
230
4
9
6
80
Árvore inicial obtida pela regra do canto esquerdo:
D1
O1
20
D2
10
O2
2
O3
13
Demanda
20
20
10
D3
5
D4
12
4
Produção
40
9
80
6
110
0
70
1
11
30
14
30
100
80
80
230
Número de arcos básicos:(m + n - 1) = 3 + 4 -1 = 6.
Custo da solução: 20.10 + 20.5 + 10.0 + 70.1 + 30.14 + 80.6 = 1270.
14
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Árvore inicial obtida pela regra do custo mínimo
D1
D2
O1
10
O2
2
O3
20
Demanda
20
D3
5
30
13
D4
12
0
50
1
11
50
14
30
100
40
40
80
4
Produção
40
9
80
6
110
230
Número de arcos básicos: (m + n - 1) = 3 + 4 -1 = 6.
Custo da solução: 40.4 + 50.1 + 30.0 + 20.13 + 50.14 + 40.6 = 1410.
15
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo de Compensação
X11= 20 -1 (C11 =10)
40
20
X12 = 20 +1 (C12 =5)
X21 =0 +1(C21 =2)
X22 = 10 -1 (C22 =0)
80
30
X23 = 70
X33 = 30
110
100
X34 = 80
80
C21 =2.(+1) +10.(-1) +5.(+1) +0.(-1) = -3/unidade.
X21 (É candidato a entrar)
16
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo de compensação do arco não-básico (2, 1) .
Ciclo de compensação formado pela árvore básica, obtida pela Regra do
Canto esquerdo, e pelo arco não-básico (2, 1).
D1
O1
O2
20
(-1) 10 20
(+1) 2 10
O3
Demanda
D2
(+1) 5
(-1) 0
11
13
20
D3
30
12
4
Produção
40
70
1
9
80
30
14
6
110
100
D4
80
80
230
Custo marginal do arco (2, 1):
C21 = 2.(+1) + 10.(-1) + 5.(+1) + 0.(-1) = -3/unidade.
(É candidato a entrar)
17
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo de Compensação
X11= 20
40
X12 = 20-1 (C12 =5)
X14 =0 +1(C14=4)
X22 = 10 +1(C22 =0)
80
20
30
X23 = 70 -1 (C23 =1)
X33 = 30 +1 (C33 =14)
110
100
X34 = 80 -1 (C34 =6)
80
C14 =4.(+1) +6.(-1) +14.(+1) +1.(-1) +0.(+1) +5.(-1) = 6/unidade.
X14 (Não é candidato a entrar)
18
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo de compensação do
arco não-básico (1, 4).
O1
D1
20
D2
D3
10 20
(-1) 5
O2
2 10
(+1) 0
O3
13
Demanda
20
D4
12
70
(-1) 1
11 30 (+1) 14 80
30
100
(+1) 4
9
Produção
40
80
(-1) 6
110
80
230
Custo marginal do arco (1, 4):
C14 = 4.(+1) + 6.(-1) + 14.(+1) + 1.(-1) + 0.(+1) + 5.(-1) = +6/unidade.
(Não é candidato a entrar)
19
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Ciclo de Compensação
X11= 20 -1 (C11 =10)
40
X12 = 20 +1 (C12 =5)
X22 = 10 -1 (C22 =0)
80
20
30
X23 = 70 +1(C23 =1)
X31 =0 +1(C31 =13)
X33 = 30 -1 (C33 =14)
110
100
X34 = 80
80
C31 =13.(+1) +10.(-1) +5.(+1) +0.(-1) +1.(+1) +14.(-1) = -5/unidade.
X31 (É candidato a entrar)
20
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Determinação dos coeficientes de custos marginais de
alguns arcos não-básicos
Ciclo de compensação formado pela árvore básica, obtida pela Regra do
Canto esquerdo, e pelo arco não-básico (3, 1).
D1
D2
D3
O1
20 (-1) 10 20 (+1) 5
12
O2
2 10 (-1) 0 70 (+1) 1
(+1) 13
O3
11 30 (-1) 14
Demanda
20
30
100
D4
80
80
4
9
6
Produção
40
80
110
230
Custo marginal do arco (3, 1):
C31 = 13.(+1) +10.(-1) + 5.(+1) + 0.(-1) + 1.(+1) + 14.(-1) = -5/unidade.
(É candidato a entrar)
21
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Balanceamento de Fluxo no Ciclo de
Compensação
X11= 20 -1 .(10)
40
20
X12 = 20 +1 .(10)
X22 = 10 -1 .(10)
Possui o menor
valor de fluxo dos
valores com (-1)
dentro do ciclo de
compensação.
30
Sairá o arco básico
X23 = 70 +1 .(10)
do ciclo que se
anular primeiro ao
X31 =0 +1 .(10)
X33 = 30 -1 .(10)
se aumentar o valor
100
110
do fluxo no arco
X34 = 80
não-básico (3, 1)
escolhido para
entrar: neste caso
80
X31 (É que Entrar) = X22 (É que sai)=10
será o arco (2, 2) =>
Xij  0 (satisfazer
O arco (2,2) é substituído pelo Arco (3,1)
a condição de nãonegatividade)
Novo valor da função objetivo = valor anterior + c31.X31= 1270 + (-5).10 = 1220.
80
22
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Balanceamento de Fluxo no Ciclo de
Compensação
X11= 10
40
20
X12 = 30
X31 = 10
80
Nova solução básica
com arco (3, 1) no
lugar do arco (2, 2)
30
X23 = 80
X33 = 20
110
100
X34 = 80
X31 (É que Entrar) = X22 (É que sai)=10
80
Novo valor da função objetivo = valor anterior + c31.X31= 1270 + (-5).10 = 1220.
23
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Melhoria da solução básica
Escolhendo o arco não-básico (3, 1) para entrar na próxima árvore básica deve-se
determinar o arco básico do ciclo de compensação que será substituído.
Sairá o arco básico do ciclo que se anular primeiro ao se aumentar o valor do fluxo no
arco não-básico (3, 1) escolhido para entrar: neste caso será o arco (2, 2).
O novo fluxo no arco (3, 1) será exatamente o valor do fluxo que passava pelo arco
substituído (2, 2): assim x31 = 10 na nova árvore básica.
Deve-se fazer o balanceamento dos fluxos nos arcos do ciclo a partir do novo valor de
fluxo no arco (3, 1)= x31 = 10: assim
X11 = 20 - 10 = 10
X12 = 20 + 10 = 30
X23 = 70 + 10 = 80
X33 = 30 - 10 = 20
X34 = 80 (não se altera pois não é do ciclo)
Novo valor da função objetivo = valor anterior + c31.X31= 1270 + (-5).10 = 1220.
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Nova solução básica com arco (3, 1) no lugar
do arco (2, 2)
Aplicando-se o Passo 2 tem-se:
O1
D1
10
O2
O3
Demanda
10
D2
30
5
C21 = +2
2
C22 = +5
0
80
10
13
C32 = +3
11
20
20
30
D3
D4
C13 = +1 12 C14 = +1
4
Produção
40
1
C24= +16
9
80
14
80
6
110
100
80
230
Não há cij < 0: Árvore atual é ótima.
X11 = 10  Remeter 10 unidades do produto da fábrica 1 ao depósito 1
X12 = 30  Remeter 30 unidades do produto da fábrica 1 ao depósito 2
X23 = 80  Remeter 80 unidades do produto da fábrica 2 ao depósito 3
X31 = 10  Remeter 10 unidades do produto da fábrica 3 ao depósito 1
X33 = 20  Remeter 20 unidades do produto da fábrica 3 ao depósito 3
X34 = 80  Remeter 80 unidades do produto da fábrica 3 ao depósito 4
Custo Ótimo mínimo de transporte = 1220.
25
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Método alternativo para cálculo dos coeficientes de
custos marginais dos arcos não-básicos
Método Modificado (Modi):
Inspirado nas condições de folgas complementares
da teoria da dualidade da Programação Linear.
Maneira mais simples de se calcular os
coeficientes de custo marginais.
26
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Método Modificado (Modi):
Procedimento:
Considere uma dada solução básica para o modelo
Definir:
custo marginal Li com i = 1, m para cada linha i da tabela,
custo marginal Kj, com j = 1, n para cada coluna j da tabela,
de forma que, para cada trajeto (ou arco) básico (i, j) da solução
dada tem-se: Li + Kj = cij
27
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modi
O sistema de equações resultante tem solução indeterminada:
(m + n) variáveis Li, Kj
(m + n - 1) equações, uma para cada um dos arcos básicos
da árvore associada a solução em estudo.
Para levantar a indeterminação do sistema basta fazer, por exemplo,
L1 = 0 e calcular por inspeção os demais valores de Li e Kj.
Para o cálculo do valor do coeficiente de custo marginal de cada arco
não-básico (i, j) usar a expressão: Cij = cij - (Li + Kj)
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo do MODI
Considere no exemplo anterior a tabela associada à solução inicial,
obtida pela regra do custo mínimo, onde deseja-se calcular todos os
coeficientes de custo marginal dos arcos não-básicos.
D1
D2
O1
10
O2
2
O3
Demanda
20
20
D3
5
30
13
30
D4
12
0
50
1
11
50
14
100
40
40
80
4
Produção
40
9
80
6
110
230
Número de arcos básicos: (m + n - 1) = 3 + 4 -1 = 6.
29
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Modelo de Transporte Simples
Aplicando-se o método Modi tem-se as variáveis L1, L2, L3, K1, K2, K3, K4, e o
sistema de equações:
L1+ K4 = 4
L2 + K2= 0
L2 + K3 = 1
L3 + K1 = 13
L3 + K3 = 14
L3 + K4 = 6
Fazendo-se L1= 0 tem-se: K4 = 4 L3 = 2, K3 = 12, K1 = 11, L2 = -11, K2 = 11.
Cálculo dos Coeficientes de Custo Marginal:
C11 = C11 - (L1 + K1 ) = 10 - (0 + 11) = -1
Candidatos
C12 = C12 - (L1 + K2 ) = 5 - (0 + 11) = -6
C13 = C13 - (L1 + K3 ) = 12 - (0 + 12) = 0 Mantém o valor da FO
C21 = C21 - (L2 + K1 ) = 2 - ( -11 + 11) = 2
C24 = C24 - (L2 + K4 ) = 9 - (-11 + 4) = 16
Candidato
C32 = C32 - (L3 + K2 ) = 11 - (2 + 11) = -2
30
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
“Stepping Stone Algorithm”
Para um Modelo de Minimização
Passo 1: Inicialização
Determinar uma árvore básica inicial com (m + n - 1) arcos básicos. Ir ao
Passo 2.
Passo 2: Teste de Otimalidade
Calcular os coeficientes de custos marginais dos arcos não-básicos.
Se coeficiente de custo marginal > 0  solução atual é ótima. Parar.
Se há coeficiente de custo marginal cij < 0  solução atual não é ótima.
O arco (i, j) deve se tornar arco básico na próxima árvore básica. assim o
arco (i, j) é escolhido para entrar. Ir ao Passo 3.
31
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
“Stepping Stone Algorithm”
Passo 3. Melhoria da Solução
Achar ciclo de compensação formado pelo arco não-básico (i, j)
escolhido para entrar e a árvore básica atual.
No ciclo achar o arco básico (k, l) que se anula primeiro ao se
aumentar o valor do fluxo no arco (i, j) que entra.
O arco básico (k, l) sai e será substituído pelo arco (i, j).
Efetuar o balanceamento de fluxo no ciclo, com todo o fluxo do arco
(k, l) indo para o arco (i, j). Voltar ao Passo 2.
32
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
“Stepping Stone Algorithm”
Passo 2: Teste de Otimalidade - Modelos de Maximização
Calcular os coeficientes de lucro marginal.
Se coeficiente de lucro marginal < 0  Solução Atual é
Ótima. Parar.
Se há coeficiente de lucro marginal lij > 0  solução atual não
é ótima.
O arco (i, j) deve se tornar arco básico na próxima árvore básica.
Assim o arco (i, j) é escolhido para entrar
Todo o restante do algoritmo é igual ao caso de mimimização
33
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Casos especiais
(1) ofertas e demandas desbalanceadas
 ai
>
i
Podem ocorrer duas situações
 bj  excesso de oferta  criar destino fictício.
j
a b
i 
i
j
 excesso de demanda  criar origem fictícia.
j
Custos de transporte nos trajetos fictícios são nulos.
Aplica-se o “Stepping Stone Algorithm” para o modelo ampliado e
balanceado.
34
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Casos especiais - (2) Condições proibidas de
embarque e recepção – Trajetos proibidos
Quando há restrições adicionais, como a existência de trajetos
proibidos entre determinadas origens e destinos do modelo:
Basta bloqueá-los na tabela de aplicação do algoritmo, de forma a
desconsiderá-los da solução.
Ou seja, associar a cada um destes trajetos proibidos um custo
de transporte muito alto na função objetivo
35
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Casos Especiais - (3) Soluções degeneradas
Podem ocorrer a partir de duas situações:
(I) Na inicialização do algoritmo se o nº. de arcos básicos for menor que
(m + n - 1), ou seja, a regra de inicialização não fornece uma árvore:
Acrescentar convenientemente arcos com fluxo nulo até que se obtenha uma
árvore (= grafo com m + n - 1 arcos e sem ciclos).
(II) No Passo 3 do algoritmo durante a determinação do arco básico a ser
substituído pelo arco não-básico escolhido para entrar pode se verificar
um “empate na saída”, ou seja, mais de um arco básico do ciclo de
compensação encontrado se anula para um dado valor de fluxo no arco
que entra:
Escolher qualquer um destes arcos básicos para sair e manter os demais, com
fluxo nulo na próxima árvore básica (degenerada).
Efetuar o balanceamento de fluxo para os demais arcos.
36
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo com degeneração e
desbalanceamento
D1
D2
D3
D4
Produção
O1
10
5
12
4
40
O2
2
0
1
9
80
O3
13
11
14
6
100
Demanda
20
30
80
70
200\220
Há um excesso de produção no valor de 220 - 200 = 20 unidades  criar um
destino fictício DF com demanda associada de 20 unidades.
Solução inicial para o novo modelo (balanceado)
D1
O1
20
10
D2
20
O2
C21= -3
2
10
0
70
1
C24= +16
9
C2F= +13
0
80
O3
C31= -5 13 C32= -2 11
10
14
70
6
20
0
100
Demanda
20
D3
5 C13= +6 12
D4
C14= +6
30
80
Custo da solução inicial: 930
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
70
4
DF
C1F= +8
Produção
0
40
20
220
37
Exemplo com degeneração e
desbalanceamento
Escolhendo para entrar o arco (3, 1) obtém-se o ciclo de compensação :
O1
D1
D2
20 (-1)
10 20 (+1)
5
2
0
11
O2
O3
Demanda
(+1)
20
10 (-1)
13
30
D3
D4
DF
Produção
12
4
0
40
70 (+1)
1
9
0
80
10 (-1)
14
0
100
80
70
70
6
20
20
220
Percebe-se que quando o fluxo no arco que entra (3, 1) é aumentado
até o valor 10  os fluxos nos arcos básicos (2, 2) e (3, 3) se anulam
configurando-se um “empate na saída”.
38
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exemplo com degeneração e
desbalanceamento
Escolhendo, por exemplo, o arco (2, 2) para sair e ser substituído
pelo arco (3, 1):
Arco (3, 3) fica na árvore básica (degenerada) com fluxo nulo
D1
D2
D3
O1
10
10
30
5
O2
C21= +2
2
 C22= +5
0
O3
10
13
 C32= 3
11
Demanda
20
30
D4
C13= +1 12 C14= +1
DF
4  C1F= +3
Produção
0
40
80
1  C24= +16 9  C2F= +13 0
80
0
14
100
80
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
70
70
6
20
20
0
220
Exemplo com degeneração e
desbalanceamento
D1
O1
10
10
O2
 C21= +2 2
O3
10
13
Demanda
20
D2
D3
D4
DF
30
5 C13= +1 12 C14= +1 4 C1F= +3 0
 C22= +5 0
80
1  C24= +16 9  C2F= +13 0
 C32= +3 11
0
14
70
6
20
0
30
80
70
20
Produção
40
80
100
220
Esta tabela corresponde a solução ótima (degenerada) com
custo ótimo = custo anterior + C31.X31 = 930 + (-5).10 = 880.
Valores ótimos de fluxo para os arcos básicos:
X11 = 10, X12 = 30, X23 = 80, X31 = 10, X33 = 0, X34 = 70, X3F = 20.
Observe que o valor de fluxo igual a 20 no arco fictício (O3, DF)
significa que 20 unidades do produto ficarão estocadas na origem 3.
Os arcos não-básicos tem fluxo nulo.
40
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
1. Uma empresa tem 3 fábricas e 4 clientes, com as seguintes
capacidades de produção e demandas relativas a um produto de
interesse:
Fábrica
Capacidade
Cliente
Demanda
F1
200
C1
140
F2
100
C2
120
F3
80
C3
90
C4
30
Total
380
Total
380
41
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
Os custos de transporte ($/por unidade) são os seguintes:
Clientes
Fábricas
C1
C2
C3
C4
F1
5
4
6
14
F2
2
9
8
10
F3
6
11
7
12
Com o objetivo de minimizar os custos de transportes, determinar o
programa de embarque do produto de cada fábrica a cada cliente.
Formule os modelos em Redes e de PL e aplique o Stepping Stone
Algorithm. Inicialize o algoritmo com a Regra do Canto Esquerdo.
42
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
2. Uma companhia tem 3 depósitos e 4 clientes, com as seguintes
capacidades mensais de estocagem e demanda para um dado
produto:
Depósito
Capacidade
Cliente
Demanda
D1
30
C1
10
D2
90
C2
100
D3
70
C3
70
C4
30
Total
210
Total
190
43
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
No contrato com os Clientes foram incluídas multas ($/unidade de
produto faltante) associadas a eventuais faltas dadas por: $1 se faltar
para o Cliente 1, $3 se faltar para o Cliente 3 e $2 se faltar para o
Cliente 4. Os custos de embarque ($/por unidade) são os seguintes:
Sabendo-se que obrigatoriamente o
cliente C2 deve ser atendido
completamente,
encontrar
o
programa de embarque de mínimo
custo. Formule um modelo de PL e
aplique o Stepping Stone Algorithm.
Inicialize o algoritmo com a Regra
do Custo Mínimo.
44
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
3.
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)
45
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Exercícios
Conhecem-se os custos de se manter o produto em estoque
($/unidade estocada) em cada Fábrica: $1 para estocagem na Fábrica
1, $2 para estocagem na Fábrica 2 e $3 para estocagem na Fábrica 3.
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 Stepping Stone
Algorithm. Inicialize o algoritmo pela Regra do canto Esquerdo.
46
Pesquisa Operacional - UNESP / Campus de Guaratinguetá