Logística 06

Prévia do material em texto

ENP119 – Logística
Aula 06 –Gestão de Transportes
FORMULAÇÃO DO PROBLEMA
𝜑 = m𝑖𝑛 𝑓 𝑥 =෍
𝑖=0
𝑚
෍
𝑗=1
𝑛
𝑐𝑖𝑗𝑥𝑖𝑗
𝑠. 𝑡.
෍
𝑗=1
𝑛
𝑥𝑖𝑗 ≤ 𝑠𝑖 ∀𝑖
෍
𝑖=1
𝑚
𝑥𝑖𝑗 ≥ 𝑑𝑗 ∀𝑗
𝑥𝑖𝑗≥ 0
EXEMPLO DE INSTÂNCIA
100
50
30
80
40
5
3
4
2
2
1
TABELA DO PROBLEMA
MÉTODO DO CUSTO MÍNIMO
 O método do custo mínimo é o mais utilizado e
apresenta, quase sempre, uma solução muito próxima
da ótima. O objetivo desse método é procurar por um
solução viável inicial de menor custo total.
MÉTODO DE RESOLUÇÃO
 Atribuir o maior valor possível à variável que tenha o
menor custo de transporte e cortar a linha ou coluna
satisfeita
 No exemplo acima, devemos fazer 𝑥23 = 40, já que
𝑐23 = 1, eliminando-se a terceira coluna da demanda,
que se encontra satisfeita
MÉTODO DE RESOLUÇÃO
 Atribuir o maior valor possível à variável que tenha o
menor custo de transporte e cortar a linha ou coluna
satisfeita
 No exemplo acima, devemos fazer 𝑥23 = 40, já que
𝑐23 = 1, eliminando-se a terceira coluna da demanda,
que se encontra satisfeita
 Repetir o processo para as variáveis que tenham outros
custos, em ordem crescente
QUADRO RESPOSTA
VERIFICAÇÃO DAS RESTRIÇÕES
 Constata-se, no quadro, que as somas dos valores das
variáveis em cada linha (coluna) são iguais ao valor de
oferta (procura). Isto significa que a solução dada neste
quadro satisfaz as relações de igualdade do problema
de transportes
 Além disso, como todos os valores das variáveis são
não negativos, trata-se de uma solução admissível do
problema
VERIFICAÇÃO DE OTIMALIDADE
 Para testar a otimização da solução encontrada e
determinar a variável que deve entrar na base, caso
exista alguma, alguns métodos podem ser aplicados
 Neste caso, será utilizado o método dos
multiplicadores
PASSO 01
 Definir as variáveis 𝑈𝑖 e 𝑉𝑗
 A cada fonte 𝑖 é associada uma variável 𝑈𝑖
 A cada destino 𝑗 é associada uma variável 𝑉𝑗
PASSO 01
 Definir as variáveis 𝑈𝑖 e 𝑉𝑗
 A cada fonte 𝑖 é associada uma variável 𝑈𝑖
 A cada destino 𝑗 é associada uma variável 𝑉𝑗
 Neste caso, teremos:
 𝑢1, 𝑢2, 𝑣1, 𝑣2, 𝑣3
PASSO 02
 A cada variável básica 𝑥𝑖𝑗 da solução inicial, deve-se
associar a seguinte equação: 𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗
PASSO 02
 A cada variável básica 𝑥𝑖𝑗 da solução inicial, deve-se
associar a seguinte equação: 𝑢𝑖 + 𝑣𝑗 = 𝑐𝑖𝑗
 Ou seja:
 𝑥11 → 𝑢1 + 𝑣1 = 𝑐11
 𝑥12 → 𝑢1 + 𝑣2 = 𝑐12
 𝑥22 → 𝑢2 + 𝑣2 = 𝑐22
 𝑥23 → 𝑢2 + 𝑣3 = 𝑐23
PASSO 03
 Resolver o sistema
 Para resolver o sistema, devemos tomar uma variável
qualquer e igualá-la a zero. Por exemplo, fazendo 𝑢1 =
0, encontramos:
PASSO 03
 Resolver o sistema
 Para resolver o sistema, devemos tomar uma variável
qualquer e igualá-la a zero. Por exemplo, fazendo 𝑢1 =
0, encontramos:
𝑢1 = 0, 𝑣1 = 5, 𝑣2 = 3, 𝑢2 = −1, 𝑣3 = 2
PASSO 04
 Encontrar o ganhos ou perdas
 A cada variável não básica deve-se calcular:
 𝑃𝑖𝑗 = 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗
 Se:
 𝑃𝑖𝑗 ≥ 0, 𝑎 𝑠𝑜𝑙𝑢çã𝑜 é ó𝑡𝑖𝑚𝑎
 𝑃𝑖𝑗 < 0, 𝑎 𝑠𝑜𝑙𝑢çã𝑜 𝑛ã𝑜 é ó𝑡𝑖𝑚𝑎, 𝑒 𝑥𝑖𝑗 𝑒𝑛𝑡𝑟𝑎 𝑛𝑎 𝑏𝑎𝑠𝑒
PASSO 04
 Encontrar o ganhos ou perdas
 A cada variável não básica deve-se calcular:
 𝑃𝑖𝑗 = 𝑐𝑖𝑗 − 𝑢𝑖 − 𝑣𝑗
 Se:
 𝑃𝑖𝑗 ≥ 0, 𝑎 𝑠𝑜𝑙𝑢çã𝑜 é ó𝑡𝑖𝑚𝑎
 𝑃𝑖𝑗 < 0, 𝑎 𝑠𝑜𝑙𝑢çã𝑜 𝑛ã𝑜 é ó𝑡𝑖𝑚𝑎, 𝑒 𝑥𝑖𝑗 𝑒𝑛𝑡𝑟𝑎 𝑛𝑎 𝑏𝑎𝑠𝑒
 𝑃21 = 4 + 1 − 5 = 0
 𝑃13 = 2 + 0 − 2 = 0
EXEMPLO