INVESTIGAÇÃO OPERACIONAL
 8ª Aula

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 # 1
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª 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
Equação
Z
(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 # 2
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª 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 # 3
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

8ª 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 # 4
ui = cij - vj
Variável Básica
cij
cij – ui - vj
Z=
Variável Não Básica
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Inicialização do Método dos Transportes e de Distribuição
O objectivo da inicialização é obter uma Solução Básica Admissível (SBA) inicial.
Antes de começar este processo de inicialização, temos de garantir que:
Número de Variáveis Básicas = m + n - 1
A razão para esta situação é que as restrições têm a forma de igualdades e o conjunto das m+n restrições
tem uma que é dispensável (por exemplo, uma das restrições de procura é igual à soma das restrições de
oferta menos as outras restrições de procura). Assim, qualquer solução básica aparece no Quadro dos
Transportes com m+n-1 variáveis rodeadas com um círculo, em que a soma em linha e coluna, corresponde
à oferta e procura, respectivamente.

Procedimento para obter uma Solução Básica Inicial



Das linhas e colunas em consideração seleccionar a próxima VB, de acordo com algum critério
Atribuir à VB um valor que corresponda à oferta ou procura remanescente, a que for menor
Eliminar essa linha ou coluna dos cálculos seguintes (se a linha e colunas se anularem em simultâneo, escolha
a linha para ser eliminada, posteriormente, a coluna servirá para atribuir o valor zero a uma variável degenerada)

Cecília Rocha # 5
Se só resta uma linha ou coluna, então o processo termina com a consideração de todas as variáveis
ainda sem valor atribuído.
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Exercício Exemplo (recordar)
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 # 6
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Alternativas para escolher uma Solução Básica Inicial

Método do Canto Noroeste
Destinos
2
1
1
Origens
2
3
Procura
vj





Cecília Rocha # 7
54
Oferta
3
40.5
27.6
36
25
70
70
31.2
55
52.8
110
55
33.6
33.6
5
125
60
ui
75
75
80
Z = 10 164
Começar pela variável x11
Se houver ainda oferta disponível, passar para a variável xi+1, j
Se só houver procura disponível, passar para a variável xi, j+1
Prosseguir até obter todas as variáveis básicas (as que têm um círculo) e todas as outras variáveis (não básicas) serão
zero.
O valor da Função Objectivo Z = 54*70 + 31.2*55 + 36*55 + 33.6*5 + 33.6*75 = 10 164 u.m.
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Alternativas para escolher uma Solução Básica Inicial

Método de Vogel





Origens
Calcular as diferenças, em linha e coluna, entre os 2 valores menores
Seleccionar a maior diferença global (considerando as linhas e colunas em conjunto)
Na coluna da maior diferença, escolher o menor custo e atribuir à variável correspondente o menor valor entre a
oferta e a procura
Eliminar a linha ou coluna respectiva
Repetir o procedimento
1
2
3
Procura
Diferença entre colunas
1
Destinos
2
3
54
40.5
27.6
31.2
36
25
52.8
33.6
33.6
125
60
75
Seleccionar x21 = 110
52.8 – 31.2 = 21.6
36 – 33.6 = 2.4
27.6 – 25 = 2.6
Eliminar a linha (2)
1
Origens
1
2
3
Procura
Diferença entre colunas
Cecília Rocha # 8
Destinos
2
3
Oferta
70
110
80
Diferença entre
linhas
40.5 – 27.6 = 12.9
25 – 31.2 = 6.2
33.6 – 33.6 = 0
Oferta
Diferença entre
linhas
54
40.5
27.6
70
40.5 – 27.6 = 12.9
52.8
33.6
33.6
80
33.6 – 33.6 = 0
15
60
75
Seleccionar x13 = 70
54 – 52.8 = 1.2
40.5 – 33.6 = 6.9
33.6 – 27.6 = 6.0
Eliminar a linha (1)
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Alternativas para escolher uma Solução Básica Inicial

Método de Vogel
(repetido)
Origens
1
1
2
3
Procura
Diferença entre colunas
Origens
1
2
3
Procura
Destinos
2
3
Oferta
Diferença entre
linhas
54
40.5
27.6
70
40.5 – 27.6 = 12.9
52.8
33.6
33.6
80
33.6 – 33.6 = 0
15
60
75
Seleccionar x13 = 70
54 – 52.8 = 1.2
40.5 – 33.6 = 6.9
33.6 – 27.6 = 6.0
Eliminar a linha (1)
1
Destinos
2
3
52.8
33.6
33.6
15
60
5
Oferta
Diferença entre
linhas
80
33.6 – 33.6 = 0
Seleccionar x31 = 15
Seleccionar x32 = 60
Diferença entre colunas
Seleccionar x33 = 5
Z = 8 340
Cecília Rocha # 9
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Alternativas para escolher uma Solução Básica Inicial

Método do Custo Mínimo


Seleccionar o menor custo de todo o Quadro de Custos (atribuir à variável x23 = 75)
Procurar sequencialmente os menores valores possíveis

(x13 não pode ser, dado que já se satisfez toda a procura)

(x21 = 35, valor excedente da oferta)

(x32 = 60, satisfaz toda a procura)

( x12 e x22, não podem ser, dado que já se satisfez toda a procura)

(x31 = 20, valor excedente da oferta)

(x11 = 70, valor da oferta)
1
1
2
3
Origens
Procura
Cecília Rocha # 10
125
Destinos
2
3
54
70
40.5
27.6
31.2
35
36
25
52.8
20
33.6
90
70
60
60
33.6
75
Oferta
75
70
110 35
80 20
Z = 9 819
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Exercício Exemplo (recordar)
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 # 11
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Teste de Optimização
Uma Solução Básica Admissível é óptima se e só se
cij – ui – vj  0,
para todo (i, j) em que xij é variável não básica.


Assim, só é necessário calcular todos os valores de cij – ui – vj
Deve-se iniciar o cálculo pela linha ou coluna que tenha mais variáveis básicas, como forma de facilitar os
cálculos
Destinos
2
1
1
Origens
2
3
Procura
vj
Cecília Rocha # 12
54
40.5
27.6
7.2
12.9
0
36
25
24
13
31.2
110
0
52.8
15
0
33.6
60
0
Oferta
3
70
70
110
33.6
5
0
125
60
75
V1 = 52.8
V2 = 33.6
V3 = 33.6
80
ui
U1 = C13-V3
= -6
U2 = C21-V1
= -21.6
U3 = 0

Esta já é a Solução
Óptima, no caso de
utilizarmos como Solução
Básica Inicial a obtida pelo
Método de Vogel
Z = 8 340
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Processo Iterativo

Teste de Optimização
Destinos
2
1
1
Origens
2
3
Procura
vj


70
0
31.2
35
0
52.8
20
0
125
V1 = 0
40.5
27.6
5.7
36
-7.2
25
24
0
33.6
60
0
60
75
33.6
0
75
V2 = 33.6 – 52.8 = -19.2 V3 = 33.6 – 52.8 = -19.2
Oferta
ui
70
U1 = 54
110
U2 = 31.2
80
U3 = 52.8
Z = 9 819
Ainda não é a solução óptima !
Escolher a VB Entrada


Cecília Rocha # 13
54
3
Como cij – ui – vj representa a taxa a que a função objectivo irá evoluir à medida que a variável não básica xij
aumenta, a VBE deverá ter um coeficiente cij – ui – vj negativo para diminuir o custo total.
A VBE será a que tem coeficiente cij – ui – vj mais negativo, ou seja, x13
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Processo Iterativo

Escolher a VB Saída





Aumentar a VBE irá provocar uma reacção em cadeia, na cadeia por nós definida.
Assim, passaremos a ter células receptoras e células fornecedoras, representadas no Quadro dos Transportes
pelos sinais + e –
Neste caso iremos utilizar a cadeia marcada a vermelho
O valor a transferir das células fornecedoras para as receptoras é dado pelo mínimo (x11 = 70, x23 = 75), ou seja, 70
VBE = x11
Destinos
2
1
1
Origens
2
3
Procura
vj
Cecília Rocha # 14
54
70
0
31.2
35
0
52.8
20
0
+
3
40.5
27.6
5.7
36
-7.2
25
24
0
33.6
60
0
+
75
33.6
0
125
60
75
V1 = 0
V2 = 33.6 – 52.8 = -19.2
V3 = 33.6 – 52.8 = -19.2
-
Oferta
ui
70
U1 = 54
110
U2 = 31.2
80
U3 = 52.8
Z = 9 819
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)

Processo Iterativo

Identificar a nova SB Admissível
Destinos
2
1
1
Origens
2
3
54
40.5
27.6
20.2
25.9
0
36
25
24
0
31.2
0
52.8
Origens
2
3
Procura
vj
Cecília Rocha # 15
20
0
Procura
vj
1
105
+
-
33.6
60
0
Oferta
3
5
33.6
125
60
75
V1 = 0
V2 = 33.6 – 52.8 = -19.2
V3 = 25 – 31.2 = -6.2
1
Destinos
2
3
40.5
27.6
7.2
12.9
0
36
25
24
13
31.2
110
0
52.8
15
0
33.6
60
0
+
-13
54
70
70
5
-13
U1 = C13-V3
= 33.8
110
U2 = 31.2
80
U3 = 52.8
Z = 8 405
Oferta
70
33.6
ui
125
60
75
V1 = 0
V2 = 33.6 – 52.8 = -19.2
V3 = 33.6 – 52.8 = -19.2
70
ui
U1 = C13-V3
= 46.8
110
U2 = 31.2
80
U3 = 52.8
Z = 8 340
2001/2002
INVESTIGAÇÃO OPERACIONAL

8ª Aula (cont.)
Cecília Rocha # 16
2001/2002