PROBLEMAS DE TRANSPORTE E DA DESIGNAÇÃO E USO DE PACOTES COMPUTACIONAIS NA PROGRAMAÇÃO LINEAR

SUMÁRIO

1.1. PROBLEMAS DE TRANSPORTE E DA DESIGNAÇÃO...............................04

1.2. O Problema de Transporte............................................................................04

1.3. Algoritmo para o Problema de Transporte: Método do Canto Noroeste........06

1.3.1. Uma aplicação do método do Canto Noroeste.....................................07

1.4. Algoritmo para o problema de Transporte: Método de Vogel........................07

1.4.1. Uma aplicação do método do Método de Vogel...................................08

1.5. O problema da designação............................................................................09

1.5.1. Uma aplicação do Método da Designação...........................................10

2. DESIGNAÇÃOUSO DE PACOTES COMPUTACIONAIS NA PROGRAMAÇÃO LINEAR................................................................................................................15

2.1. Programação Linear utilizando o software LINDO........................................15

2.2. Programação Linear utilizando a ferramenta Solver do Microsoft Excel........16

2.2.1. Resolução de problema prático de programação linear, utilizando a ferramenta Solver do Microsoft Excel......................................................16

REFERÊNCIAS..........................................................................................................20

1. Problemas de Transporte e da Designação

1.2. O Problema de Transporte

Classe denominada para ser utilizada na Pesquisa Operacional, e também para encontrar o menor custo de transporte na distribuição de cargas entre centros produtores e consumidores.

Podemos descrever detalhadamente um problema de transporte da seguinte forma:

1. Um conjunto de m pontos de fornecimento a partir dos quais um insumo é embarcado ou remetido. O ponto de fornecimento i pode fornecer no máximo si unidades.

2. Um conjunto de n pontos de demanda para os quais o insumo é remetido. O ponto de demanda j deve receber pelo menos dj unidades do insumo.

3. Cada unidade produzida no ponto de fornecimento i e remetida ao ponto de demanda j incorre num custo de cij.

Seja xij = nº de unidades despachadas do ponto de fornecimento i para

o ponto de demanda j.

A formulação genérica do problema do transporte será:

Figura 1 – Formulação do Problema de Transporte

Note que X ij pode ter valores zero ou um.

O cálculo da solução ótima é tão simples que será mostrado com exemplos.

O problema de transporte pode ser balanceado quando a capacidade de fornecimento excede a demanda. Pode ser se seguido os seguintes passos:

Cria-se um ponto fictício de demanda. A demanda nesse ponto será igual ao excedente da capacidade.

Como balancear o problema quando a demanda é maior que a capacidade de fornecimento? Neste caso, o problema não possui soluções viáveis. Como alternativa, pode-se adicionar um ponto fictício de fornecimento.

Exemplo:

O custo de fornecimento daquele ponto será igual à penalização incorrida pelo não fornecimento do insumo.

Dois reservatórios de água abastecem três cidades. Cada reservatório pode abastecer até 50 milhões de litros de água por dia. Cada cidade necessita receber 40 milhões de litros de água por dia. Associado a cada milhão de litros de água não fornecido por dia existe uma multa. A multa na cidade 1 é de $20; na cidade 2 é de $18; na cidade 3 é de $23.

Os custos do transporte entre reservatórios e cidades seguem conforme tabela abaixo:

Figura 2 – Custos do Transporte

Tabela 3 – Resolução do Problema de Transporte

1.3. Algoritmo para o Problema de Transporte: Método do Canto Noroeste.

A partir da célula superior esquerda transportamos o máximo possíveI da origem ao destino correspondente. Esse procedimento zera a disponibilidade da linha ou da coluna da célula. O próximo transporte será feito na célula contigua (à direita ou abaixo) que tenha disponibilidade de linha e coluna correspondente.

O método do canto noroeste garante a não-formação de circuitos entre as variáveis básicas, além de satisfazer as condições de contorno (restrições de origem e destino).

Inicie o método considerando a célula (1,1) do tableau. Faça com que x11 seja o maior valor possível.

Obviamente, x11 = Min (d1, s1).

Se x11 = s1, desconsidere as demais células na primeira linha do tableau, já que nenhuma outra variável básica virá desta linha. Atualize o valor de d1 para d1 -s1.

Se x11 = d1, desconsidere as demais células na primeira coluna do tableau, já que nenhuma outra variável básica virá desta coluna. Atualize o valor de s1 para s1 - d1.

Se x11 =s1=d1, desconsidere as demais células na primeira linha ou na primeira coluna do tableau (mas não ambas). Se você escolher desconsiderar a linha 1, mude d1 para 0. Se escolher desconsiderar a coluna 1, mude s1 para 0.

Repita o procedimento, sempre escolhendo a célula posicionada no extremo noroeste do tableau (desde que ela não esteja em uma linha ou coluna eliminada anteriormente).

Ao cabo de (m+ n - 1) iterações chega-se a uma base viável inicial para o problema.

1.3.1. Uma aplicação do método do Canto Noroeste

Figura 4 – Aplicação do Método Noroeste