Pesquisa Operacional (Solver)

PROBLEMAS DE TRANSPORTE

CARACTERIZAÇÃO GERAL DO PROBLEMA

DADOS:

estrutura de fontes de produção ou origens de um produto
rede de caminhos possíveis de transporte
destinos ou mercados para os produtos

OBJETIVO:
DETERMINAR O CARREGAMENTO DA REDE DE

TRANSPORTE QUE MINIMIZA O CUSTO TOTAL
DO TRANSPORTE.

EXEMPLO DE UMA REDE DE TRANSPORTE
ROTAS POSSÍVEIS

FÁBRICA 1

DEPÓSITO 1

FÁBRICA 2

DEPÓSITO 2

FÁBRICA 3

DEPÓSITO 3

EXEMPLO
CUSTOS UNITÁRIOS
DE TRANSPORTE
CAPACIDADE DE
FORNECIMENTO

FONTE 1

DESTINO 1

20

DESTINO 2

15

10

CAPACIDADE DE
RECEBIMENTO

10

DESTINO 3

10

3
5

17
7
25

FONTE 2

9

MODELO DE PROGRAMAÇÃO
LINEAR

Minimizar Z = 10 . x11 + 3 . x12 + 5 . x13 + 12 . x21 + 7 . x22 + 9 . x23
Sujeito às restrições:
• De capacidade das fontes:

x11 + x12 + x13 = 15 x21 + x22 + x23 = 25

• De absorção pelos destinos: x11 + x21 = 20 x12 + x22 = 10

x13 + x23 = 10
Com x11 , x12 , x13 , x21 , x22 e x23  0

Matriz para solução do modelo:

Características:
1. Modelo de programação linear, com (m+n) equações e (m+n)

incógnitas,
2. Todos os coeficientes das variáveis são iguais a 0 e 1;
3. A matriz formada pelas restrições de absorção pelos destinos é a transposta da matriz formada pelas restrições das fontes;
4. O modelo exige o equilíbrio entre fontes e destinos ( ai =  bj), temos uma equação dependente, que pode ser obtida em função das demais.
5. Assim, o modelo é formado por um sistema de (m+n-1) equações independentes.

Procedimento de solução:
Procedimento de solução é exatamente o mesmo do método
Simplex, com algumas simplificações oriundas das características acima.

Passo 1: Determinação da solução básica inicial;

Passo 2: Determinação da variável não-básica que deve entrar na base, se a condição de otimalidade não estiver cumprida; Passo 3: Determinação da variável básica que deve sair da base, utilizando a condição de