II. Programação Linear (PL)
Capítulo 7.1:
O problema de transporte (PT).
 Definição e apresentação sobre forma de rede.
 Formulação do caso equilibrado e não equilibrado.
Exemplos
 Propriedades fundamentais.
   
©2000-2001 Prof.ª Gladys Castillo
1
Problema de Transporte. Exemplo Protótipo
Um dos principais produtos da firma Lactosal é o leite.
Os pacotes de leites são empacotados
em 3 fábricas
e depois são distribuídos de camião
para quatro armazéns
Conhecendo os custos de transporte, a procura prevista
para cada armazém e as capacidades de produção de
cada fábrica, pretende-se:
OPTIMIZAR O PROGRAMA DE DISTRIBUIÇÃO DIÁRIO
DO LEITE.
   
©2000-2001 Prof.ª Gladys Castillo
2
Problema de Transporte. Exemplo Protótipo
Os dados dos custos de uma carga de leite para cada combinação
fábrica-armazém e das ofertas(produção) e procuras, em cargas de
camião/dia, são os seguintes:
24 cargas diárias
de leite devem ser
produzidas e
distribuídas
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
   
©2000-2001 Prof.ª Gladys Castillo
3
Formulação do Problema de Transporte.
Exemplo Protótipo.
Custo por carga de
camião
Armazéns
Fábricas
1
2
3
4
Oferta
1
1
2
3
4
6
2
4
3
2
4
8
3
0
2
2
1
10
Procura
4
7
6
7
Minimizar z =
x11 + 2 x12 + 3 x13 + 4 x14 +
4 x21 + 3 x22 + 2 x23 + 4 x24 +
2 x32 + 2 x33 + x34
sujeito a:
x11 + x12 + x13+ x14
x11
x12
x13
x21 + x22 + x23+ x24
x31 + x32 + x33+ x34
+ x21
+ x31
+ x22
+ x32
+ x23
+ x33
x14
+ x24
+ x34
= 6
= 8
= 10
= 4
= 7
= 6
= 7
xij  0 ( i=1,2,3; j=1,2,3,4 )
   
©2000-2001 Prof.ª Gladys Castillo
4
Matriz de Restrições do Problema de Transporte.
Exemplo Protótipo.
A matriz das restrições do problema de transporte para
o exemplo protótipo apresenta a seguinte estrutura:
x11 x12 x13 x14 x21 x22 x23 x24
x31 x32 x33 x34
A=
   
©2000-2001 Prof.ª Gladys Castillo
5
Problema de Transporte sob a forma de Rede.
Exemplo Protótipo.
Fábricas
1
Armazéns
c11
x11
1
2
2
3
3
c34
x34
4
   
©2000-2001 Prof.ª Gladys Castillo
6
Problema de Transporte.
Do Exemplo ao Modelo do PT
Cargas de leite
Unidades de um produto
3 fábricas
m origens
4 armazéns
n destinos
Produção da fábrica i
ai oferta da origem i
Procura no armazém j
bj procura no destino j
Custo de transporte
por carga da fábrica i
para o armazém j
cij custo por unidade
transportada da origem i
para o destino j
   
©2000-2001 Prof.ª Gladys Castillo
7
Problema de Transporte.
Do Exemplo ao Modelo do PT
xij cargas a distribuir
da fábrica i
para o armazém j
xij unidades a
distribuirda origem i
para o destino j
Determinar o plano
óptimo de distribuição
diária do leite das
fábricas pelos
armazéns tendo como
objectivo a
minimização do custo
total
Determinar o plano
óptimo de distribuição
desse produto das
origens pelos destinos
tendo como objectivo
a minimização do
custo total
   
©2000-2001 Prof.ª Gladys Castillo
8
Problema de Transporte. Caso Equilibrado.
Oferta total = Procura total
Destino
Origem
1
2
1
c11
x11
Procura
c12
c22
c21
x22
.
.
.
b1
…
…
c1n
x1n
b2
c2n
x2n
…
…
xmn
a1
a2
.
.
.
.
.
.
cm2
xm2
Oferta
n
.
.
.
cm1
xm1
…
x12
x21
.
.
.
m
2
cmn
bn
am
ai = bj
Um problema de transporte está equilibrado se
a oferta total é igual à procura total, caso
contrário está não equilibrado.
   
©2000-2001 Prof.ª Gladys Castillo
9
Problema de Transporte.Caso equilibrado.
Exemplo protótipo
Oferta total = Procura total
Destino
Origem
1
2
1
1
2
3
Procura
x11
3
x21
x22
4
x32
7
8
x24
x23
1
2
x33
6
6
4
2
2
0
4
x14
x13
x12
Oferta
4
3
2
4
x31
3
x34
7
10
24 =24
Para o exemplo protótipo a oferta total é igual à
procura total . Este problema está equilibrado.
   
©2000-2001 Prof.ª Gladys Castillo
10
Problema de Transporte.
Formulação como problema de PL.
m
z   cij xij
Minimizar
i 1 j 1
sujeito a:
n
x
j 1
m
ij
x
i 1
n
ij
 ai , i  1,2,...,m
 b j , j  1,2,...,n
restrições de
oferta
restrições de
procura
xij  0 , i  1,2,...,m , j  1,2,...,n
   
©2000-2001 Prof.ª Gladys Castillo
11
Problema de transporte sob a forma de rede.
Destinos
Origens
a1
1
c11
x11
i
cij
xij
.
.
.
am
m
b1
.
.
.
.
.
.
ai
1
j
bj
.
.
.
cmn
xmn
n
bn
Esta figura ilustra o problema de transporte sob a forma de rede
representados por nodos e arcos.
Os nodos representam as origens e os destinos e
os arcos representam os percursos das origens aos destinos
através dos quais o produto pode ser transportado.
   
©2000-2001 Prof.ª Gladys Castillo
12
Problema de Transporte.
Estrutura especial da matriz de restrições.
A matriz dos
coeficientes das
restrições é apenas
constituída por uns (1)
e zeros (0) . Cada
variável xij tem como
coeficientes apenas 2
uns : um na linha
associada à origem i e
outro na linha relativa
ao destino j
O problema de transporte apresenta uma
estrutura especial evidenciada pela disposição
das restrições:
x11 x12 ... x1n x21 x22 ... x2n …
A=
xm1 xm2 ... xmn
.
.
.
.
restrições das
origens
.
.
restrições dos
destinos
   
©2000-2001 Prof.ª Gladys Castillo
13
Problema de Transporte.
Oferta total superior à procura total
Destino
Origem
1
2
1
c11
x11
Procura
x12
x21
c22
x22
.
.
.
b1
…
…
n
x1n
x2n
b2
a1
x1 n+1
0
c2n
a2
x2 n+1
.
.
.
cmn
…
xmn
…
bn
Adicionar destino
fictício
©2000-2001 Prof.ª Gladys Castillo
0
.
.
.
cm2
xm2
Oferta
n+1
c1n
.
.
.
cm1
xm1
…
c12
c21
.
.
.
m
2
0
am
xm n+1
ai - bj
   
14
Oferta total superior à procura total.
Exemplo 1: Plano de Produção.
Uma multinacional produz aviões comerciais para diversas
companhias de aviação. A última etapa no processo de
produção é a produção de motores seguido da sua instalação
no avião.
Para cumprir os contratos estabelecidos deve ser determinado
o plano óptimo de produção dos motores para os próximos
quatro meses.
   
©2000-2001 Prof.ª Gladys Castillo
15
Oferta total superior à procura total.
Exemplo 1: Plano de Produção.
Os dados para o plano da produção para os quatro meses
futuros são os seguintes:
Mês
Instalações
programadas
Produção
máxima
Custo
unitário
de produção
1
10
25
1.08
2
15
35
1.11
0.015
3
25
30
1.10
0.015
4
20
10
1.13
0.015
Custo unitário
de
armazenamento
os custos em milhões de dólares
   
©2000-2001 Prof.ª Gladys Castillo
16
Oferta total superior à procura total.
Exemplo 1: Plano de Produção.
Este problema pode ser reformulado como um problema de
transporte, tomando como:

Origem i - produção de motores no mês i
(i =1,2,3,4)

Destino j - instalação de motores no mês j
(j=1,2,3,4)

xij - quantidades de motores produzidos no mês i a serem
instalados no mês j
 xij = 0, se i>j (primeiro produzir, depois instalar)
 cij - custo por unidade de produção e armazenamento
 cij=
M, se i>j, como não existe custo real associado com
estes dados, podem ser penalizados com um M
arbitrariamente grande.
   
©2000-2001 Prof.ª Gladys Castillo
17
Oferta total superior à procura total.
Exemplo 1. Restrições de ofertas.
As restrições de oferta correspondem à produção de motores
para cada mês i. Estas restrições são de desigualdade
limitadas pela capacidade máxima de produção por mês.
Mês
Instalações
programadas
Produção
máxima
Custo
unitário
de produção
1
10
25
1.08
2
15
35
1.11
0.015
3
25
30
1.10
0.015
4
20
10
1.13
0.015
Custo unitário
de
armazenamento
x11 + x12 + x13+ x14  25
x21 + x22 + x23+ x24  35
x31 + x32 + x33+ x34  30
x41 + x42 + x43+ x44  10
Como estas restrições são de desigualdade é preciso introduzir variáveis de
folga para converte-las em restrições de igualdade.
Isto significa que é preciso introduzir um destino fictício, em que as variáveis
de folga representam a capacidade de produção não utilizada por cada mês .
   
©2000-2001 Prof.ª Gladys Castillo
18
Oferta total superior à procura total.
Exemplo 1. Restrições de procuras.
As restrições de procura correspondem ao plano de
instalação para cada mês j. Estas restrições são de igualdade,
correspondendo ao número de instalações requisitadas para
cada mês.
Mês
Instalações
programadas
Produção
máxima
Custo
unitário
de produção
1
10
25
1.08
2
15
35
1.11
0.015
3
25
30
1.10
0.015
4
20
10
1.13
0.015
Custo unitário
de
armazenamento
x11 + x21 + x31+ x32 = 10
x21 + x22 + x23+ x24 = 15
x31 + x32 + x33+ x34 = 25
x41 + x42 + x43+ x44 = 20
Como é impossível produzir motores num mês determinado para serem
instalados num mês anterior, todas as variáveis de decisão correspondentes
a i >j devem ser nulas. Para obter isto, é preciso penalizar os custos
correspondentes a estas variáveis com um M arbitrariamente grande, tal
como no método do “big M”.
   
©2000-2001 Prof.ª Gladys Castillo
19
Oferta total superior à procura total.
Exemplo 1. Quadro do problema de transporte.
Este problema reformulado como problema de transporte
apresenta o seguinte quadro:
Os custos são calculados
tomando os dados dos custos
de produção e de
armazenamento. Por exemplo
para a variável x24 que
representa o número de
motores produzidos no mês 2
a serem instalados no mês 4,
o custo correspondente
c24 = 1.11 + 0.015+0.015
=1.140
Destino
1
Origem
1
2
3
4
Procura
x11
1.080
2
x12
M
x21
x22
1.095
M
M
10
1.100
x33
M
x42
15
0
M
x43
25
x15
0
x25
1.115
x34
20
25
35
0
30
0
10
x35
1.130
x44
Oferta
5
1.110
x13
x32
x41
4
1.125
x14
1.110
1.140
1.125
x23
x24
M
x31
3
x45
30
30
Como a oferta total é superior à procura total foi adicionado um destino fictício
com uma procura igual a: Oferta Total -Procura Total = 100 -70 = 30 u.
   
©2000-2001 Prof.ª Gladys Castillo
20
Problema de Transporte.
Oferta total inferior à procura total
Destino
Origem
1
2
1
c11
x11
x12
x21
c22
x22
.
.
.
xm1
…
c12
c21
.
.
.
m
2
…
…
c1n
x1n
xm2
0
m+1
xm+1,1
Procura
b1
cm2
b2
…
…
…
xmn
a1
a2
.
.
.
.
.
.
0
xm+1,2
c2n
x2n
.
.
.
cm1
Oferta
n
cmn
0
am
xm+1,n
bj - ai
bn
Origem fictícia
   
©2000-2001 Prof.ª Gladys Castillo
21
Oferta total inferior à procura total
Exemplo 2: distribuição de recursos de agua.
Uma empresa administra a distribuição de água duma região.
Para isto é preciso canalizar a água de 3 rios que estão
situados fora da região e distribui-la para 4 cidades.
Agora o gerente da empresa pretende distribuir toda a água
disponível dos 3 rios para as 4 cidades, de forma a pelo
menos satisfazer as necessidades essenciais de cada uma,
minimizando o custo total.
   
©2000-2001 Prof.ª Gladys Castillo
22
Oferta total inferior à procura total
Exemplo 2: distribuição de recursos de água.
Os dados dos custos e requerimentos para o plano de
distribuição de água são os seguintes:
 A cidade 3 tem uma fonte
independente da água que satisfaz
as suas necessidades mínimas
O rio 3 não pode fornecer
a cidade 4, o que significa nos
termos do problema de transporte
que este percurso é impossível.
Neste caso é preciso penalizar
este percurso com um M
arbitrariamente grande.
A cidade 4 aceita toda a água
que seja possível enviar além da
sua necessidade mínima de 10
u.m.
Cidade
1
2
3
4
Fornece
1
16
13
22
17
50
2
14
13
19
15
60
3
19
20
23
-
50
Necessidades
mínimas
30
70
0
10
Procura
50
70
30

Rio
os custos por unidade de medida.
   
©2000-2001 Prof.ª Gladys Castillo
23
Oferta total inferior à procura total
Exemplo 2: distribuição de recursos de água.
Este problema pode ser reformulado como um problema de
transporte, tomando como:

Origem i – o rio i (i =1,2,3)

Destino j – a cidade j (j=1,2,3,4)

xij - quantidade de água a enviar do rio i para a cidade j
 cij - custo unitário da distribuição da água do rio
i para a cidade j
   
©2000-2001 Prof.ª Gladys Castillo
24
Oferta total inferior à procura total
Exemplo 2. Restrições de ofertas.
As restrições de oferta correspondem às restrições dos rios
(origens). Como deverá ser distribuída toda a água disponível
dos 3 rios, estas 3 restrições são de igualdade, uma por cada
rio.
Cidade
1
2
3
4
Fornece
1
16
13
22
17
50
x11 + x12 + x13+ x14 = 50
2
14
13
19
15
60
3
19
20
23
-
50
Necessidades
mínimas
30
70
0
10
x21 + x22 + x23+ x24 = 60
x31 + x32 + x33+ x34 = 50
Procura
50
70
30

Rio
   
©2000-2001 Prof.ª Gladys Castillo
25
Oferta total inferior à procura total
Exemplo 2. Restrições de procura.
As restrições de procura determinam a quantidade de água que
deve ser fornecida a cada cidade, e têm limites superiores e inferiores
(excepto a cidade 2, onde coincidem a procura com a necessidade
mínima).
Cidade
1
2
3
4
Fornece
Rio
1
16
13
22
17
50
2
14
13
19
15
60
3
19
20
23
-
50
Necessidades
mínimas
30
70
0
10
Procura
50
70
30

O limite superior para a cidade 4 pode ser calculado
como a diferença entre a oferta total (50+ 60+50=160)
e a soma das necessidades mínimas para as restantes
cidades (30+ 70 =100)  160 - 100 = 60 unidades.
(a quantidade máxima que pode receber a cidade 4
para além da necessidade mínima )
Cidade 1: procura > necessidade
x11 + x21 + x31  30
x11 + x21 + x31  50
limite inferior
limite superior
Cidade 2: procura = necessidade
x12 + x22 + x32 = 70
Cidade 3: procura > necessidade
x13+ x23 + x33  30
limite superior
Cidade 4: procura > necessidade
x14 + x24 + x34  10
x14 + x24 + x34  60
limite inferior
limite superior
   
©2000-2001 Prof.ª Gladys Castillo
26
Oferta total inferior à procura total
Exemplo 2. Quadro do problema de transporte.
Cidades
Origem
1
2
16
Rio 1
Rio 2
Rio 3
x11
x21
x31
Procura
x41
50
x24
20
19
x32
x42
70
15
19
x23
x22
17
x14
x13
13
14
Oferta
4
22
13
x12
0
Rio Ficticio
3
M
23
x33
0
x43
30
x34
0
50
60
50
0
x44
50
60
Como a oferta total é inferior à procura total foi adicionada
uma origem fictícia com uma oferta igual a:
Procura Total -Oferta Total = 210 -160 = 50 unidades.
   
©2000-2001 Prof.ª Gladys Castillo
27
Oferta total inferior à procura total
Exemplo 2. Análise do rio fictício.
Para satisfazer as necessidades mínimas de água é preciso re-analisar os dados
para cada cidade de forma a garantir que o mínimo procurado não seja fornecido
pelo rio fictício.
Cidade
1
2
3
4
Fornece
1
16
13
22
17
50
2
14
13
19
15
60
3
19
20
23
-
50
Necessidades
mínimas
30
70
0
10
Procura
50
70
30

Rio
Cidade 3: Como não tem
necessidade mínima, então não é
preciso alterar nada.
Cidade 4: procura > necessidade
(60 > 10). Como o rio fictício
fornece apenas 50 unidades, pelo
menos fica garantido que as 10
unidades mínimas não podem ser
obtidas deste rio. Não é preciso
alterar nada.
   
©2000-2001 Prof.ª Gladys Castillo
28
Oferta total inferior à procura total
Exemplo 2. Análise do rio fictício.
Cidade
Cidade 2: procura = necessidade
Esta cidade não pode ser fornecida
pelo rio fictício. Para isto é preciso
penalizar com M o percurso que une
o rio fictício com a cidade 2.
1
2
3
4
Fornece
1
16
13
22
17
50
2
14
13
19
15
60
3
19
20
23
-
50
Necessidades
mínimas
30
70
0
10
Cidade 1: procura > necessidade
Procura
50
70
30

Esta cidade deve ser dividida em 2
destinos: um que verifica a
necessidade mínima (onde o rio
fictício fica penalizado) e o outro
que corresponde à quantidade de
água que pode ser tomada além do
requerimento mínimo.
Rio
   
©2000-2001 Prof.ª Gladys Castillo
29
Oferta total inferior à procura total
Exemplo 2. Formulação como P.T.
Este é o quadro final dos custos para o problema de
distribuição da água, formulado como problema de transporte:
Cidades
Origem
A cidade 1 foi dividida
em duas para garantir as
necessidades mínimas
de 30 unidades.
O rio fictício está
penalizado para a cidade
1'.
1' 1''
Rio 3
3
Oferta
4
16
16
13
22
17
14
14
13
19
15
19
19
20
23
M
M
0
M
0
0
Rio 1
Rio 2
2
60
50
50
Rio Ficticio
Procura
50
30 20
70
30
60
O rio fictício está penalizado para
a cidade 2
   
©2000-2001 Prof.ª Gladys Castillo
30
Problema de Transporte. Propriedades fundamentais(1).

Se um problema de transporte está equilibrado, i.e., a oferta
total é igual à procura total, então tem sempre soluções
admissíveis.

Se um problema de transporte não está equilibrado,i.e., a oferta
total não é igual à procura total, então pode ser introduzida
uma origem ou um destino fictício para converter as restrições
de desigualdade em igualdade e poder obter assim um problema
equilibrado.

O problema de transporte tem sempre óptimo finito.

Qualquer SBA do problema de transporte tem no máximo m+n-1
variáveis básicas
Do total de m+n equações só m+n-1 são linearmente independentes, existindo
sempre uma equação redundante, i.e., uma equação pode ser obtida como
combinação linear das restantes.
   
©2000-2001 Prof.ª Gladys Castillo
31
Problema de Transporte. Propriedades fundamentais(2).
A
base correspondente a qualquer SBA do problema de
transporte é uma matriz triangular.
B=
1 1 0 …0
0 1 1 …0
0 0 1 …0
...
0 0 0 …1
0 0 0 …0
0
0
0
1
1
Se as quantidades das ofertas e procuras são valores inteiros,
então qualquer SBA tem sempre valores inteiros.
Como a matriz da base é uma matriz triangular composta por 0 e 1, a resolução
do sistema conduz necessariamente a uma solução cujas variáveis assumem
apenas valores inteiros, pois apenas exige adições e subtracções.

   
©2000-2001 Prof.ª Gladys Castillo
32
Base e Solução Básica Admissível para o PT.
Minimizar z =
x11 + 2 x12 + 3 x13 + 4 x14 +
4 x21 + 3 x22 + 2 x23 + 4 x24 +
2 x32 + 2 x33 + x34
sujeito a:
x11 + x12 + x13+ x14
x21 + x22 + x23+ x24
x11
+ x21
x12
x13
x14
x31 + x32 + x33+ x34
+ x31
+ x22
+ x32
+ x23
+ x33
+ x24
+ x34
xij  0 ( i=1,2,3; j=1,2,3,4 )
A=
=
=
=
=
=
=
=
6
8
10
4
7
6
7
Como m=3 e n=4 e a característica de A, c(A)=m+n-1=6,
qualquer base B tem dimensão 6x6. Uma base pode ser
obtida, por exemplo, tomando as colunas P11, P12, P22, P23,
P33, P34 e eliminando à restrição 4.
P11 P12 P13 P14P21P22P23P24P31P32P33P34
(1) 1 1 1 1 0 0 0 0 0 0 0 0
(2) 0 0 0 0 1 1 1 1 0 0 0 0
(3) 0 0 0 0 0 0 0 0 1 1 1 1
(4) 1 0 0 0 1 0 0 0 1 0 0 0
(5) 0 1 0 0 0 1 0 0 0 1 0 0
(6) 0 0 1 0 0 0 1 0 0 0 1 0
(7) 0 0 0 1 0 0 0 1 0 0 0 1
Trocando as
linhas obtém-se
uma matriz B
triangular
B=
©2000-2001 Prof.ª Gladys Castillo
B=
P11 P12P22P23P33P34
(1) 1 1 0 0 0 0
(2) 0 0 1 1 0 0
(3) 0 0 0 0 1 1
(5) 0 1 1 0 0 0
(6) 0 0 0 1 1 0
(7) 0 0 0 0 0 1
P11 P12P22P23P33P34
(1) 1 1 0 0 0 0
(5) 0 1 1 0 0 0
(2) 0 0 1 1 0 0
(6) 0 0 0 1 1 0
(3) 0 0 0 0 1 1
(7) 0 0 0 0 0 1
   
33
Uma Solução básica Admissível para o PT.
Como a matriz B é triangular a solução do sistema é imediata:
P11 P12P22P23P33P34
(1) 1 1 0 0 0 0
(5) 0 1 1 0 0 0
(2) 0 0 1 1 0 0
(6) 0 0 0 1 1 0
(3) 0 0 0 0 1 1
(7) 0 0 0 0 0 1
XB
x11
x12
x22
x23
x33
x34
x34 =7
=
6
7
8
6
10
7
x33 + x34 =10
x33 =3
x23 + x33 = 6
x23 =3
x22 + x23 = 8
x22 =5
x12 + x22 = 7
x12 =2
x11 + x12 = 6
x11 =4
Uma SBA do problema é: X = (4, 2, 0, 0, 0, 5, 3, 0, 0, 0, 3, 7)
   
©2000-2001 Prof.ª Gladys Castillo
34