INVESTIGAÇÃO OPERACIONAL

7ª Aula

Método dos Transportes e de Distribuição
O método dos transportes é um dos métodos de programação linear e deve o nome à sua aplicação em
problemas que envolvem a optimização do transporte de bens.
O método de distribuição é outro método de programação linear destinado à alocação (ou distribuição) de
pessoas por tarefas, podendo-se considerar um tipo de problemas de transportes.
As aplicações relativas a problemas de Transportes e Alocação envolvem inúmeras variáveis de decisão e
restrições. No entanto, uma grande parte dos coeficientes das variáveis nas restrições são zero, o que
permite que as simplificações introduzidas pelo método dos transportes levem a um menor volume de
cálculo.
Cecília Rocha # 1
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula

Exercício- Exemplo
Suponha que Inglaterra, França e Espanha produzem todo o trigo, cevada e aveia disponível no mundo. A procura mundial
de trigo corresponde à produção de 125 milhões de acres de solo. Com o mesmo objectivo são necessários 60 milhões de acres para
cevada e 75 milhões de acres para aveia. O total de solo agrícola disponível para este propósito, em Inglaterra, França e Espanha é de,
respectivamente, 70 milhões, 110 milhões e 80 milhões de acres. O número de horas de trabalho necessárias para produzir 1 acre de
trigo é de 18h em Inglaterra, 13 em França e 16 em Espanha. No caso do cevada são necessárias 15h em Inglaterra e 12h em França
e em Espanha. Para o aveia são precisas 12h em Inglaterra, 10 em França e 16 em Espanha. O custo da hora de trabalho para
produção de trigo é de 3 u.m., 2.4 u.m. e 3.3 u.m., respectivamente em Inglaterra, França e Espanha. Para a produção de cevada o
custo da hora de trabalho será de 2.7 u.m., 3.0 u.m. e 2.8 u.m. em Inglaterra, França e Espanha. No caso da aveia haverá um custo da
hora de trabalho de 2.3 u.m. em Inglaterra, 2.5 u.m. em França e 2.1 u.m. em Espanha. O problema é definir a melhor distribuição da
produção em cada país, de forma a satisfazer as necessidades mundiais de trigo, cevada e aveia mas minimizando o custo de
produção total.
a) Formular este problema como um Problema de Transportes, construindo o quadro de custos e requisitos;
b) Utilize uma rotina automática do SOLVER para encontrar um solução óptima para o problema;
c) Utilize o método de Vogel e o método do Custo Mínimo para determinar uma solução básica admissível inicial;
d) Resolva pelo Método dos Transportes.
Cecília Rocha # 2
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)
[70]
[110]
[80]
Cecília Rocha # 3
Inglaterra
França
Espanha
x11
18*3.0 u.m. = 54
x12
15*2.7 u.m. = 40.5
x13
12*2.3 u.m. = 27.6
x21
13*2.4 u.m. = 31.2
x22
12*3.0 u.m. = 36
x23
10*2.5 u.m. = 25
x31
16*3.3 u.m. = 52.8
x33
16*2.10 u.m. = 33.6
Trigo
Cevada
Aveia
[125]
[60]
[75]
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Formulação do Problema

Minimizar Z = 54 x11 + 40.5 x12 + 27.6 x13 + 31.2 x21 + 36 x22 + 25 x23 + 52.8 x31 + 33.6 x32 + 33.6 x33
s.a.:
Restrições de Origem

x11 + x12 + x13


= 70
x21 + x22 + x23
= 110
x31 + x32 + x33 = 80
Restrições de Destino



x11
+ x21
x12
+ x31
+ x22
x13
+ x23
= 120
+ x32
= 60
+ x33 = 75
O facto de todos os coeficientes das variáveis terem o valor UM e estarem dispostos da forma evidenciada neste
problema, é que permite distinguir este problema dos restantes e não a sua aplicabilidade a este tipo específico de
problemas. Pode ser aplicado noutras situações em que esta estrutura se repita.
Cecília Rocha # 4
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Modelo do Problema de Transportes

Genericamente, o problema de transportes refere-se à distribuição de qualquer tipo de bem,
proveniente de um conjunto de fornecedores – denominados Origens – para um conjunto de clientes
– denominados Destinos.

Assim, uma origem i (i = 1, 2, ..., m) pode fornecer si unidades de um dado bem por vários destinos e
um dado destino j (j = 1, 2, ..., n) tem uma procura de dj unidades a receber das origens.

Um pressuposto básico é que o custo de distribuição entre a origem i e o destino j é proporcional ao
número de unidades transportadas, sendo ci j o custo de distribuição unitário.

Para o exercício exemplo apresentado o Quadro de Custos e Requisitos é o seguinte:
Destinos
Cevada
Aveia
18 * 3.0 = 54
15 * 2.7 = 40.5
12 * 2.3 = 27.6
70
França
13 * 2.4 = 31.2
12 * 3.0 = 36.0
10 * 2.5 = 25.0
110
Espanha
16 * 3.3 = 52.8
12 * 2.8 = 33.6
16 * 2.1 = 33.6
80
125
60
75
Inglaterra
Origens
Procura
Cecília Rocha # 5
Oferta
Trigo
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Modelo do Problema de Transportes

Genericamente, o Quadro de Custos e Requisitos é o seguinte:
Destinos
D2
...
Dn
S1
c11
c12
...
c1n
s1
S2
c21
c22
...
c2n
s2
Sm
cm1
cm2
...
cmn
sm
Procura
d1
d2
...
dn
Origens

Oferta
D1
...
A formulação deste tipo de problema é a seguinte:
m n
Minimizar
Sujeito a:
 cij xij
i 1 j 1
n
 xij  si
j 1
Cecília Rocha # 6
m
e
 xij  d j
i 1
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Propriedades das Soluções nos Problemas de Transportes

Solução Inteira:


Para os problemas de transportes, em que a procura e oferta têm valores inteiros, todas as variáveis básicas em
todas as Soluções Básicas Admissíveis (incluindo a óptima) também têm valor inteiro.
Solução Admissível:

É condição necessária e suficiente para que um problema de transportes tenha alguma solução admissível que:
m
n
i 1
j 1
 si   dj

Esta propriedade pode ser analisada observando a seguinte situação
m
n
m n
i 1
j 1
i 1 j 1
 si   dj   xi j

Cecília Rocha # 7
Esta condição “A oferta total tem de igualar a procura total” implica que, nos casos em que tal não aconteça, seja
necessário adoptar uma Origem Fictícia ou um Destino Fictício, consoante exista maior procura ou maior oferta,
respectivamente.
2001/2002
INVESTIGAÇÃO OPERACIONAL
 7ª Aula (cont.)

Propriedades das Soluções nos Problemas de Transportes – Exemplo 1

Solução Admissível:

Mês
Cecília Rocha # 8
Distribuição da Produção
Uma empresa constrói aviões comerciais para diversas companhias de aviação. A última etapa de produção
consiste na construção dos motores a jacto e sua instalação (operação muito rápida) na fuselagem já totalmente
montada. Esta empresa tem estado a trabalhar para cumprir alguns contratos já adjudicados que envolvem o
fornecimento de um grande número de aviões, pelo que a produção de motores a jacto terá de ser equacionada
para os próximos 4 meses, de forma a minimizar o custo de construção e armazenamento.
Para satisfazer os prazos de entrega estabelecidos nos contratos, a empresa deverá ter construídos no final
do 1º, 2º, 3º e 4º meses, pelo menos, 10, 25, 50 e 70 motores a jacto.
As instalações onde serão construídos os motores variam conforme seja necessária a sua afectação para
outras actividades, pelo que o número de motores construídos será bastante distinto. A capacidade máxima de
construção mensal está indicada no quadro seguinte.
Dado que existe variação no custo de construção dos motores, pode compensar que alguns motores sejam
construídos nos meses anteriores à sua colocação na fuselagem, o que implicará custo de armazenamento. No
entanto, é uma opção que deverá ser analisada. Os custos envolvidos são indicados no quadro seguinte.
Produção Mínima Capacidade Máxima Custo de Construção/unidade Custo de Armazenamento/unidade
1
10 (10)
25
1.08
0.015
2
15 (25)
35
1.11
0.015
3
25 (50)
30
1.10
0.015
4
20 (70)
10
1.13
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação da resolução pelo Método dos Transportes

Origem


Destino



Custo associado à construção do motor e seu eventual armazenamento
Não se pode instalar um motor que ainda não foi construído  cij = M, para obrigar a variável
correspondente a ser zero.
Deverá ser a mais favorável em termos de diminuição de custos. Como não se conhece esse valor vamos assumir a
capacidade máxima de construção de motores em cada mês.
Procura, dj




Cecília Rocha # 9
Se i  j,
Se i > j,
Oferta, si


Número de motores a construir no mês i e a instalar no mês j
Parâmetros, cij


Colocação de motores na fuselagem nos meses j = 1, 2, 3 e 4
Variáveis de decisão, xij


Produção de motores nos meses i = 1, 2, 3 e 4
Corresponde aos valores incluídos nos contratos assinados para fornecimento de aviões.
No entanto, ao analisarmos a propriedade da existência de solução admissível verifica-se que o número de motores a
produzir (100, no máximo) é superior ao número de motores necessários (70).
Assim, será necessário adicionar um Destino Fictício (Df) cuja procura será igual ao “excesso” de oferta (30).
O custo de construção e armazenamento de motores associado a este destino fictício tem de ser nulo (não existe !...)
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação da resolução pelo Método dos Transportes
Assim, o quadro de custos e requisitos deste problema será:

Destinos
D1
Origens
D3
S1
1.080
S2
M
1.110
S3
M
M
1.100
S4
M
M
10
15
Procura
Cecília Rocha # 10
D2
D4
1.08+1*0.015= 1.095 1.08+2*0.015=1.110 1.08+3*0.015=1.125
DF
Oferta
0
25
0
35
1.10+1*0.015=1.115
0
30
M
1.130
0
10
25
20
(30)
1.11+1*0.015=1.125 1.11+2*0.015=1.140
2001/2002
INVESTIGAÇÃO OPERACIONAL
 7ª Aula (cont.)

Propriedades das Soluções nos Problemas de Transportes – Exemplo 2

Solução Admissível:

Distribuição de Recursos
Uma empresa é responsável pela distribuição de água a 4 concelhos (Berdoo, Los Devils, San Go e Hollyglass),
numa região muito árida, pelo que é necessário comprar e transportar a água de outras regiões para abastecer estes
concelhos. As fontes de fornecimento de água possíveis têm captação em 3 linhas de água – Rio Colombo, Rio
Sacron e Rio Calorie. Esta empresa compra a água a esses fornecedores e revende-a à população dos 4 concelhos.
É possível abastecer todos os concelhos a partir de qualquer dos rios, excepto a localidade de Hollyglass que não
pode ser abastecida pelo rio Calorie. Consoante o rio que abasteça estes concelhos assim variará o custo da água,
devido ao percurso a percorrer e aos acidentes geográficos a ultrapassar. Independentemente desta situação o
custo da água no cliente será sempre o mesmo.
A administração da empresa enfrenta agora o problema de garantir o fornecimento mínimo necessário aos 4
concelhos e distribuir toda a água disponível proveniente dos 3 rios da forma mais económica possível.
Os custos e necessidades envolvidos são indicados no quadro seguinte.
Custo por distância entre os rios e os concelhos
Cecília Rocha # 11
Berdoo
Los Devils
San Go
Hollyglass
Oferta de água
disponível
Rio Colombo
16
13
22
17
50
Rio Sacron
14
13
19
15
60
Rio Calorie
19
20
23
Ñ pode haver fornecimento
50
Necessidades mínimas
30
70
0
10
Fornecimento pretendido
50
70
30
Toda a que puder ser fornecida
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação da resolução pelo Método dos Transportes

Origem, i


Destino, j



É a máxima possível disponibilizada pelos rios.
Procura, dj


Cecília Rocha # 12
Custo associado ao transporte e distribuição de água entre os 3 rios e os 4 concelhos
Dado que não existe possibilidade de fornecimento de água a Hollyglass a partir do rio Calorie, este parâmetro será M
Oferta, si


Quantidade de água a fornecer do rio i e a distribuir para o concelho j
Parâmetros, cij


Distribuição de água para os 4 concelhos Berdoo. Los Devils, San Go e Hollyglass
Variáveis de decisão, xij


Fornecimento de água a partir dos rios Colombo, Sacron e Calorie
A quantidade de água a receber por cada concelho é uma variável de decisão com limite inferior (necessidades
mínimas) e limite superior. Este limite superior será a quantidade pretendida, a não ser que o somatório das
quantidades pretendidas exceda a água disponível após satisfação das necessidades mínimas. Neste contexto, o
concelho de Hollyglass não poderá dispor de mais de 60 u.a. = (50+60+50) – (30+70+0).
Como a procura tem de ser um valor único, temos um problema a resolver. Poderemos começar por supor que não
existem necessidades mínimas. Assim, as quantidades pretendidas serão as únicas restrições em relação à
quantidade de água a distribuir pelos concelhos. No entanto, teremos de fazer um ajuste ao problema dado que não
cumprimos a propriedade da solução admissível, ou seja, precisaremos de uma Origem Fictícia (Of) que deverá
garantir 50 u.a. = (50+70+30+60) - (50+60+50). O custo associado a esta Origem Fictícia será zero.
2001/2002
INVESTIGAÇÃO OPERACIONAL
 7ª Aula (cont.)

Procura, dj (cont.)

Para entrarmos em consideração com as necessidades mínimas de cada concelho, será preciso garantir que a
proveniência da água não seja a Origem Fictícia. Assim:
 Para o concelho de San Go, não há qualquer problema dado que não tem necessidades mínimas;
 Para o concelho de Hollyglass, também não haverá nenhum inconveniente, dado que as suas necessidades
mínimas de 10 u.a. estão garantidas (a quantidade pedida excede em 10 u.a. a oferta atribuída à Origem Fictícia);
 No caso do concelho de Los Devils, como a quantidade pretendida é igual às necessidades mínimas, toda a procura
terá de ser satisfeita pelas origens reais, o que implica considerar um parâmetro M para esta situação na Origem
Fictícia;
 Quanto ao concelho de Berdoo, como a Origem Fictícia tem capacidade para satisfazer a quantidade pretendida por
este concelho, é preciso assegurar que as necessidades mínimas sejam satisfeitas pelos outros 3 rios. Assim, terá
de ser feito o desdobramento do concelho de Berdoo em 2 fracções, uma correspondente às necessidades mínimas
e outra ao excedente de água pretendido, respectivamente, com procura de 30 e 20. Será ainda indispensável
garantir que as necessidades mínimas não sejam satisfeitas pela Origem Fictícia, atribuindo um parâmetro M ao
respectivo custo.
Destinos
Berdoo*
Los Devils
San Go
Hollyglass
Rio Colombo
16
16
13
22
17
50
Rio Sacron
14
14
13
19
15
60
Rio Calorie
19
19
20
23
M
50
OF
M
0
M
0
0
50
Procura
30
20
70
30
60
Origens
Cecília Rocha # 13
Oferta
Berdoo
2001/2002
INVESTIGAÇÃO OPERACIONAL
7ª Aula (cont.)

Método Simplex aplicado ao Problema de Transportes
Como os Problemas de Transportes são um dos tipos de problemas de programação linear, por isso, é
possível resolvê-los pelo método Simplex dado nas 2 aulas anteriores. No entanto, dada a especificidade destes
problemas, o método simplex pode ser simplificado – Método Simplex dos Transportes.

Preparação do Método
Após construir o quadro dos coeficientes das restrições para o método simplex, converter a função objectivo para
a forma de maximização e introduzir as variáveis artificiais z1, z2, ..., zm+n, obter-se-á o seguinte quadro simplex:
Variáveis
Equação
Básicas
Z
(0)
Coeficientes
Z
...
xij
...
zi
-1
cij
M
0
1
1
0
1
...
zm+j
M
...
Lado
Direito
0
(1)
...
zi
(i)
si
...
zm+j
(m+j)
1
dj
...
(m+n)
Cecília Rocha # 14
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação do Método
Falta agora realizar algumas operações algébricas antes da 1ª iteração para eliminar os coeficientes das
variáveis (artificiais) básicas iniciais da linha (0) que sejam diferentes de zero.
Após essas operações, a nova linha (0) terá a seguinte forma:
Variáveis
Básicas
Z
Equação
(0)
Coeficientes
Z
-1
...
xij
Cij – ui - vj
...
zi
M - ui
...
zm+j
M - vj
...
Lado Direito
m
n
i 1
j 1
 si ui   dj v j
Onde:
 ui – múltiplo da linha original (i) que tem de ser subtraído (directa ou indirectamente) à linha original (0)
no método simplex, durante todas as operações que levam ao quadro actual
 vj – múltiplo da linha original (m+j) que tem de ser subtraído (directa ou indirectamente) à linha original
(0) no método simplex, durante todas as operações que levam ao quadro actual
 Se xij é uma variável não básica, então cij – ui – vj é interpretada como a taxa a que Z se irá alterar à
medida que xij aumenta
Cecília Rocha # 15
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação do Método


Em primeiro lugar, não são necessárias variáveis artificiais porque se pode obter uma solução básica
inicial com métodos auxiliares simples
A linha (0) pode ser obtida sem utilizar qualquer outra linha, calculando os valores actuais de ui e vj
directamente. Dado que cada variável básica tem de ter coeficiente zero na linha (0), os valores de ui e
vj podem ser obtidos pela resolução de um conjunto de equações:
cij – ui – vj = 0



Cecília Rocha # 16
para cada i e j em que xij é variável básica
A variável básica de saída pode ser identificada facilmente sem utilizar os coeficientes das variáveis
básicas de entrada, assim como, a nova SBA pode ser detectada imediatamente sem se realizarem
nenhumas operações algébricas.
Deste modo podemos prescindir de quase todo o quadro do método simplex.
Além dos dados de base (parâmetros cij, oferta si e procura dj), o método simplex dos transportes só
precisa da SBA inicial, dos valores actuais de ui e vj e dos valores resultantes da operação cij – ui – vj
para as variáveis não básicas xij. Estes dados podem ser organizados num quadro denominado –
Quadro Simplex dos Transportes.
2001/2002
INVESTIGAÇÃO OPERACIONAL

7ª Aula (cont.)

Preparação do Método
Formato do quadro simplex dos transportes
Iteração
?
1
2
1
2
Destino
...
...
n
Origem
c11
c12
c1n
c21
c22
c2n
cm1
cm2
cmn
Oferta
s1
s2
...
m
Procura
d1
d2
sm
dn
Vj = cij - ui
cij
xij
Cecília Rocha # 17
ui = cij - vj
Variável Básica
cij
cij – ui - vj
Z=
Variável Não Básica
2001/2002