Investigação Operacional

INSTITUTO POLITÉCNICO DE SETÚBAL
ESCOLA SUPERIOR DE CIÊNCIAS EMPRESARIAIS

DEPARTAMENTO DE ECONOMIA E GESTÃO

INVESTIGAÇÃO OPERACIONAL

CASOS PARTICULARES DA PROGRAMAÇÃO LINEAR

Aníbal Areia

4. CASOS PARTICULARES DA PROGRAMAÇÃO LINEAR
4.1 Problema de Transporte
O problema de transporte consiste em determinar o menor custo de transporte possível para enviar um determinado artigo disponível em quantidades limitadas, em determinados locais, para outros locais onde é necessário.
A formulação do problema de transporte: cij - custo de enviar uma unidade de i para j;

xij  quantidade a enviar de i para j; n m

i 1

Min Z=

j 1

¦ ¦c

x

ij ij

n

¦x

ij

a j , j=1,2,…,m

ij

bi , i=1,…,n

i 1 m ¦x j 1

xij t 0, i=1,…,n; j=1,2,…,m

Exemplo 4.1 Uma empresa tem três armazéns (A1, A2 e A3) onde dispõe de 20, 30 e 10

toneladas de um determinado produto. Pretende-se abastecer três clientes, (C1,C2, e C3) cujas necessidades são 25, 15 e 20 toneladas, respectivamente. Os custos unitários de transporte por tonelada são:

A1
A2
A3

C1
1
3
8

C2
7
8
3

C3
4
2
5

Pretende-se minimizar o custo total do transporte dos produtos.
A formulação do problema:

xij - Quantidade a enviar do armazém i para o cliente j.

1

Min Z= x11  7 x12  4 x13  3x21  8 x22  2 x23  8 x31  3 x32  5 x33
Sujeito a

x11  x12  x13

20

x21  x22  x23

30

x31  x32  x33 10

x11

+ x21

x12

+ x31
+ x22

x13

=25
+ x32

+ x23

=15

+ x33 =20

xij t 0; i 1,2,3; j 1,2,3
4.1.1 Determinar uma solução básica admissível

Para determinar uma solução básica admissível, utilizamos o método do canto do noroeste, o método da matriz de custos e o método de Vogel.
4.1.1.1 Método do canto do noroeste

A variável básica escolhida em cada célula é a que se encontra no canto superior esquerdo. Este método permite afectar a maior quantidade possível a x11 sem violar as restrições. A