Unidade III - teorico

Prévia do material em texto

Pesquisa Operacional
Responsável pelo Conteúdo:
Prof. Dr. Luciano Rossi
Revisão Textual:
Aline Gonçalves
Análise de Problemas Típicos
Análise de Problemas Típicos
 
• Apresentar ao aluno problemas típicos do campo da pesquisa operacional e formas específicas 
de resolvê-los.
OBJETIVO DE APRENDIZADO 
• Análise de Sensibilidade;
• Problema de Redes;
• Método de Vogel.
UNIDADE Análise de Problemas Típicos
Análise de Sensibilidade
Na unidade anterior, exploramos o método Simplex para a resolução de problemas 
de programação linear. Nesse tipo de problema, vimos que o modelo do problema 
é formado por um sistema de inequações lineares. As inequações possuem coefi-
cientes que multiplicam as variáveis do problema. Note que os valores desses coefi-
cientes são constantes, ou seja, são predeterminados e indicam um grau de certeza 
para esses parâmetros.
Quando modelamos um problema, os valores dos coeficientes são, na prática, 
estimativas que podem mudar no decorrer do processo. Assim, se obtivemos uma 
solução ótima para determinado modelo, o que acontece com essa solução se algum 
coeficiente for alterado? Precisaremos aplicar o método Simplex novamente para o 
modelo alterado?
A Análise de Sensibilidade é o estudo do efeito que as alterações nos parâmetros 
do modelo (coeficientes) podem ter sobre a solução ótima encontrada. Assim, veri-
ficamos qual a tolerância permitida para a alteração dos parâmetros, sem que haja 
impacto na solução. Essa análise pode ser feita em diferentes categorias de alterações.
Antes de iniciarmos a discussão sobre a análise de sensibilidade, vamos resgatar 
um exemplo que foi explorado na unidade anterior. Considere o seguinte modelo:
( )
( )
( )
( )
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
2 3
60
2 2 110
2 90
, , 0
MAX Z x x x i
x x x ii
x x x iii
x x x iv
x x x
= + +
+ + ≤

+ + ≤

+ + ≤
 ≥
A solução ótima do modelo anterior foi obtida por meio do método Simplex, 
cujos passos foram apresentados, em detalhes, anteriormente. A solução foi obtida 
por meio da transformação do modelo em sua forma geral (anterior) para a forma 
padrão, cuja descrição é a seguinte:
( )
( )
( )
( )
1 2 3
1 2 3 4
1 2 3 5
1 2 3 6
2 3 0
60
2 2 100
2 90
Z x x x a
x x x x b
x x x x c
x x x x d
− − − =
+ + + =

+ + + =
 + + + =
A Tabela 1, a seguir, apresenta os valores para as variáveis, básicas e não básicas, 
da solução ótima do modelo:
8
9
Tabela 1 – Simplex – valores para variáveis da solução ótima
x1 x2 x3 x4 x5 x6 b
x4 1⁄2 0 0 1 –1⁄2 0 5
x5 0 1 0 0 1 –1 20
x6 1⁄2 0 1 0 –1⁄2 1 35
Z 1⁄2 0 0 0 1⁄2 1 145
A solução obtida considera as variáveis básicas (x2, x3 e x4) e não básicas (x1, x5 e x6), 
relembrando que as variáveis básicas são aquelas que compõem a solução e as não bási-
cas são aquelas que foram desconsideradas. A forma de representação da solução, a 
qual consideramos até o momento, descreve somente os valores para as variáveis 
básicas, sem considerar os coeficientes residuais das variáveis não básicas. Nesse 
sentido, os coeficientes das variáveis não básicas são importantes para que possamos 
realizar a análise de sensibilidade.
Vamos considerar uma nova forma de representar uma solução para um modelo 
de programação linear. Essa representação utiliza as variáveis não básicas, e seus 
respectivos coeficientes, juntamente com as variáveis básicas. Assim, a representação 
da solução ótima, para o modelo anteriormente descrito, ficaria da seguinte forma:
( )
( )
( )
( )
1 5 6
2 5 6
3 1 5 6
4 1 5
1 1 145
2 2
20
1 1 35
2 2
1 1 5
2 2
Z x x x A
x x x B
x x x x C
x x x D
+ + + =
+ − =
+ − + =
+ − =
A equação (A) representa o valor da solução ótima encontrada para a função Z = 145. 
Veja que as demais variáveis, pertinentes à função, são não básicas (x1, x5 e x6), portanto, 
são iguais a zero e estão acompanhadas dos respectivos coeficientes destacados na 
tabela da solução. A mesma lógica vale para a equação (B), na qual o valor x2 = 20 
e as variáveis não básicas x5 e x6 valem zero e os valores de seus coeficientes são 
iguais a um. A representação utilizando as variáveis não básicas não influencia a 
representação do valor da variável básica, pois elas sempre são iguais a zero. Nesse 
sentido, o que nos interessa são os valores de seus coeficientes, especificamente para 
a realização da análise de sensibilidade.
Análise de Sensibilidade dos Coeficientes da Função Objetivo
A análise de sensibilidade pode ser feita para diferentes categorias, sempre refe-
rente ao coeficiente, constante ou variável, que se pretende analisar. Nesta seção, 
examinaremos os coeficientes das variáveis básicas e não básicas na solução ótima.
9
UNIDADE Análise de Problemas Típicos
Variáveis não Básicas
Considerando o modelo anterior, vamos examinar a variação que o coeficiente 
da variável x1 pode sofrer, sem que haja uma alteração para o valor encontrado para 
a solução ótima. Vamos utilizar a equação (a) que descreve a função objetivo da 
seguinte forma:
( ) ( )1 2 31 2 3 0Z x x x a− − − =
O coeficiente original da variável x1 é 1, queremos saber quanta variação é pos-
sível adicionar ao coeficiente de x1 sem que o valor de Z seja alterado. Assim, con-
sidere que Δ (delta) representa a variação adicionada ao coeficiente, ou seja, o novo 
coeficiente de x1 é 1 + Δ (valor original do coeficiente mais a variação), de modo que 
Δ ≥ 0. Substituindo o novo coeficiente em (a), temos:
( ) 1 2 31 2 3 0Z x x x− + ∆ − − =
Que pode ser escrita da seguinte forma:
1 1 2 32 3 0Z x x x x− − ∆ − − =
A função objetivo foi acrescida de –Δx1, o que representa a variação adicional. 
Considerando a equação (A), que representa a solução ótima, com o acréscimo da 
variação, temos o seguinte:
( )
( )
1 1 5 6
1 5 6
1 1 145
2 2
1 1 145
2 2
Z x x x x A
Z x x x A
+ − ∆ + + =
 + − ∆ + + = 
 
A interpretação é fundamental na análise de sensibilidade. Nesse caso, temos um 
problema de maximização, isto é, queremos maximizar a função objetivo. Nesse 
sentido, temos que garantir que o novo coeficiente de x1 seja maior ou igual a zero, 
assim, temos o seguinte:
1 1 10
2 2 2
− ∆ ≥ ⇒ −∆ ≥ − ⇒ ∆ ≤
O valor identificado para a variação de x1, representado pelo Δ, indica que a va-
riação do coeficiente de x1 pode ser, no máximo, 
1
2
. Esse valor é denominado Limite 
Superior (LS), ou seja, essa é a variação máxima que podemos atribuir ao coeficiente 
de x1. Veja que não há, nas demonstrações matemáticas, uma especificação para o 
Limite Inferior (LI). Porém, dado que o problema em questão é de maximização, não 
faz sentido termos variação negativa, assim, o LI para o coeficiente de x1 é igual a 
zero. A representação do intervalo determinado pelos limites é [LI; LS], deste modo, 
o intervalo de variação para o coeficiente de x1, sem que haja impacto no resultado 
da função objetivo, é [0; 1 + Δ] ou [0; 1,5].
10
11
Importante!
Para os coeficientes de variáveis não básicas, o valor de Δ será sempre o coeficiente da 
variável em análise na função (A).
Variáveis Básicas
A análise de sensibilidade para as variáveis básicas segue a mesma lógica aplicada 
para as variáveis não básicas. Considere que vamos analisar a sensibilidade do coefi-
ciente de x2, notadamente uma variável básica. A função objetivo será utilizada para 
adicionarmos a variação Δ ao coeficiente de x2 da seguinte forma:
( )
1 2 3
1 2 3
1 2 2 3
2 3 0
2 3 0
2 3 0
Z x x x
Z x x x
Z x x x x
− − − =
− − + ∆ − =
− − − ∆ − =
Note que, se compararmos as funções inicial e final, observamos que a variação 
adicionada na função objetivo é representada por –Δx2. Assim, vamos utilizar essa 
variação na equação que descreve a solução ótima para o problema (equação (A)):
1 2 5 6
1 1 145
2 2
Z x x x x+ − ∆ + + =
A representação adotada aqui descreve o valor ótimo para Z e as respectivas variáveis 
não básicas, as quais, por não participarem da solução, têm seus valores iguais a zero, o 
que não altera o valor de Z. Porém, veja que x2 é uma variável básicae, nessa condição, 
se ela for mantida na equação anterior, o valor para Z será alterado, assim, devemos 
eliminá-la da equação. Para proceder com a eliminação, primeiro vamos multiplicar a 
equação (B) onde x2 é variável básica, por Δ, o que resultaria na seguinte equação:
2 5 6 20x x x∆ + ∆ − ∆ = ∆
Veja que, de forma conveniente, temos Δx5 positivo na equação que é resultado 
da multiplicação de (B) por Δ, desse modo, se somarmos ambas as equações, a vari-
ável básica será eliminada, o que resultará na seguinte equação:
( )1 5 6
1 1 1 145 20
2 2
Z x x x + + + ∆ + − ∆ = + ∆ 
 
Tendo em mente que estamos tratando um problema de maximização, é impor-
tante garantir que todos os coeficientes das variáveis não básicas na equação anterior 
sejam positivos. Assim, temos o seguinte:
1 10
2 2
1 0 1 1
+ ∆ ≥ ⇒ ∆ ≥ −
− ∆ ≥ ⇒ −∆ ≥ − ⇒ ∆ ≤
11
UNIDADE Análise de Problemas Típicos
Os intervalos para Δ se sobrepõem, assim, a Figura 1 a seguir apresenta a análise 
dessa sobreposição:
Figura 1 – Análise da sobreposição de intervalos para Δ
Fonte: Acervo do conteudista
O primeiro segmento de reta mostra que os valores válidos para Δ são aqueles 
maiores ou iguais a – 1
2
, por outro lado, o segundo segmento de reta apresenta os 
valores menores ou iguais a 1 como válidos para Δ. Assim, a análise da sobreposição 
resulta em:
1 1
2
− ≤ ∆ ≤
Desse modo, para o coeficiente de x2 na função objetivo, temos:
[ ]12 ;2 1 1,5;3
2
 − + ⇒  
Em outras palavras, o coeficiente de x2 na função objetivo pode variar entre 1,5 e 3, 
sem que a solução ótima identificada seja alterada.
Constantes do Lado Direito
Esse tipo de análise de sensibilidade considera a variação no resultado das restri-
ções, de modo a não alterar a solução ótima. Em outras palavras, queremos saber 
quanto a constante da restrição pode variar. Considerando o exemplo anterior, 
vamos analisar a restrição:
( )1 2 3 4 60x x x x b+ + + =
Para analisarmos essa restrição, vamos adicionar um valor Δ, que representa a 
variação, a constante 60:
1 2 3 4 60x x x x+ + + = + ∆
A variação adicionada Δ e a variável de folga x4 possuem o mesmo coeficiente, 
isso significa que, durante a aplicação do Simplex, tudo que for feito para a variá-
vel x4 valerá, também, para Δ. O próximo passo é verificar em quais equações da 
solução ótima a variável x4 aparece. Para esse caso, a variável x4 aparece somente 
12
13
na equação (D) e o valor do seu coeficiente é igual a 1, o Δ será adicionado à cons-
tante do lado direito, também, com esse coeficiente:
4 1 5
1 1 5
2 2
x x x+ − = + ∆
Conforme discutido anteriormente, o valor da constante do lado direito deve ser 
positivo; nesse caso, temos o seguinte:
5 0 5+ ∆ ≥ ⇒ ∆ ≥
O valor 5 representa a variação permissível para o LI, por outro lado, não há 
limitação quanto ao LS, o qual representamos por infinito, conforme descrito:
[ ] [ ]60 5;60 55;− + ∞ → ∞
Assim, podemos dizer que para a restrição (b) o valor da constante do lado direito 
pode variar entre 55 e ∞, sem que haja comprometimento da solução ótima obtida. 
Vejamos como a análise de sensibilidade para a constante do lado direito pode ser 
feita para a restrição (c), procedendo da mesma maneira, com a inclusão de Δ para 
representar a variação da constante:
1 2 3 52 2 110x x x x+ + + = + ∆
Pela lógica anterior, vemos que x5 e Δ possuem o mesmo coeficiente (1), nesse 
sentido, durante a aplicação do Simplex, tudo o que for feito na variável de folga x5
valerá, também, para Δ. 
Considerando a solução ótima, o próximo passo consiste em identificar quais 
as equações apresentam a variável x5 e considerar a inclusão de Δ com o mesmo 
coeficiente da variável:
2 5 6
3 1 5 6
4 1 5
20
1 1 135
2 2 2
1 1 15
2 2 2
x x x
x x x x
x x x
+ − = + ∆
+ − + = − ∆
+ − = − ∆
O próximo passo é garantir que as constantes nas restrições sejam maiores ou 
iguais a zero, assim, temos o seguinte:
20 0 20
1 135 0 35 70
2 2
1 15 0 5 10
2 2
+ ∆ ≥ ⇒ ∆ ≥ −
− ∆ ≥ ⇒ − ∆ ≥ − ⇒ ∆ ≤
− ∆ ≥ ⇒ − ∆ ≥ − ⇒ ∆ ≤
13
UNIDADE Análise de Problemas Típicos
Considerando as sobreposições das inequações referentes a Δ, a Figura 2 ilustra 
o resultado das sobreposições.
Figura 2 – Sobreposições das inequações de Δ
Fonte: Acervo do conteudista
Assim, o valor de Δ deve ser maior ou igual a –20 e menor ou igual a 10, e os limi-
tes para o intervalo de variação da constante na restrição (c) são [110 – 20; 110 + 10] 
ou [90; 120]. Isso significa que a constante pode variar entre os limites estabelecidos, 
sem impactar na solução encontrada.
Para finalizar, vamos analisar a restrição (d) do nosso problema, seguindo os mesmos 
passos descritos para as outras restrições. Primeiro atribuímos Δ juntamente com a 
constante do lado direito:
x1 + x2 + 2x3 + x6 = 90 + Δ
Nesse caso, a variável cujo coeficiente será considerado para a inserção da varia-
ção nas equações da solução ótima é x6. Essas inequações são as seguintes:
2 5 6
3 1 5 6
20
1 1 35
2 2
x x x
x x x x
+ − = − ∆
+ − + = + ∆
Como queremos garantir que as constantes sejam maiores ou iguais a zero, temos 
o seguinte:
20 0 20 20
35 0 35
− ∆ ≥ ⇒ −∆ ≥ − ⇒ ∆ ≤
+ ∆ ≥ ⇒ ∆ ≥ −
Assim, os limites para o intervalo de variação da constante em (d) são [90 – 35; 
90 + 20] ou [55; 110].
Problema de Redes
Uma classe específica de problemas de Pesquisa Operacional pode ser modelada 
como uma rede, facilitando sua visualização e interpretação. Redes são tipos de 
representação que utilizam estruturas denominadas grafos. Um grafo é um conjunto 
de vértices que são conectados por arestas. Os vértices podem representar qualquer 
14
15
objeto do mundo real, enquanto as arestas representam os relacionamentos existen-
tes entre os vértices.
Uma rede social pode ser modelada (representada) por meio de um grafo. Nesse 
caso, os vértices representam as pessoas e as arestas representam os relacionamentos 
de, por exemplo, amizade entre elas. Outro exemplo é a representação de um mapa 
por meio de um grafo; os vértices podem representar cidades e as arestas repre-
sentam as vias que interligam essas cidades. Nesse sentido, as arestas podem estar 
associadas a valores numéricos denominados pesos. Os pesos das arestas podem 
representar, por exemplo, a distância em quilômetros da cidade A até a cidade B.
Existem diferentes problemas de programação em redes. Para os nossos estudos, 
consideraremos o clássico problema do transporte. Essa classe de problemas foi 
inicialmente considerada para determinar o menor custo de transporte de produtos 
entre fábricas e consumidores. A solução desse tipo de problema é feita por meio do 
Método de Transporte.
A Figura 3 apresenta um exemplo de grafo (rede) no qual os vértices da esquerda 
representam fornecedores e os da direita são os consumidores. Para cada entidade 
na rede (fornecedor e consumidor) há um valor associado. Os valores associados aos 
fornecedores (CFi, com i = 1, …, m) referem-se à capacidade de fornecimento, ou 
seja, o quanto ele consegue produzir. Por outro lado, os valores associados aos con-
sumidores (DCj com j = 1, …, n) definem a demanda de consumo, isto é, o quanto 
aquele consumidor tem de demanda do produto. 
Todos os fornecedores podem entregar seus produtos a todos os consumidores. 
No entanto, para cada entrega há um custo (Wij) diferenciado em função da distância 
entre as entidades envolvidas e uma quantidade fornecida (Xij).
W Xnm, nm
W X11, 11
DCmCm
C2
C1
CFn
CF2
CF1 F1
F2
Fn
DC2
DC1
Figura 3 – Exemplo de rede (grafo) 
Fonte: Acervo do conteudista
Os vértices da esquerda representam os fornecedores, enquanto os vértices da 
direita representam os consumidores e as arestas direcionadas representam o 
fornecimento com um custo associado e uma quantidade de produtos fornecida.
O objetivo para a resolução do problema é determinar os valores para Xij que tor-
narão mínimo o custo total de transporte, satisfazendo todas as restrições de oferta 
15
UNIDADE Análise de Problemas Típicos
(capacidade de fornecimento) e demanda (necessidadede consumo). O modelo mate-
mático apresenta a seguinte forma geral:
1 1
n m
ij ij
i j
MIN z W X
= =
= ∑ ∑
Sujeito a:
( )
( )
1
1
: 1, 2, ,
: 1, 2, ,
0
n
i j i
i
m
i j j
i
i j
x CF i m
x DC j n
x
=
=
∑ ≤ =
∑ ≥ =
≥


O modelo, anteriormente descrito, descreve a função objetivo Z como a somatória 
dos produtos entre os custos de transporte (Wnm) pelas quantidades transportadas 
(Xnm). O objetivo é minimizar o custo total de transporte. As restrições descrevem 
que a somatória das quantidades transportadas pelo fornecedor i deve ser menor 
ou igual à capacidade de fornecimento. De maneira similar, temos que a somatória 
das quantidades fornecidas para o consumidor j deve ser maior ou igual à demanda 
desse consumidor. Em termos práticos, um fornecedor não pode vender mais do que 
produz e um consumidor não pode consumir mais do que é produzido. Além disso, 
as quantidades transportadas devem ser maiores ou iguais a zero.
O modelo apresentado para o problema do transporte é um problema de progra-
mação linear. Desse modo, poderia ser resolvido pelo método Simplex, conforme 
visto anteriormente. Entretanto, devido à estrutura particular do problema, há formas 
mais eficientes de resolvê-lo.
Quando temos uma demanda igual à capacidade de fornecimento, dizemos que 
o problema do transporte é balanceado. Assim, o modelo sofre uma pequena, mas 
importante, alteração. As restrições são alteradas de inequações para equações, de 
modo a refletir essa característica.
Considere o seguinte exemplo, um fornecedor fabrica seus produtos em três 
locais diferentes identificados como fabricantes A, B e C. Nesse sentido, há três 
consumidores principais, localizados, também, em lugares distintos e identificados 
como consumidores 1, 2 e 3. A Tabela 2 descreve os detalhes da operação logística 
da empresa em questão.
Tabela 2 – Detalhamento da operação logística da empresa exemplo
Custo Unitário de Transporte
Consumidor 1 Consumidor 2 Consumidor 3 Capacidade
Fornecedor A 12 22 30 100
Fornecedor B 18 24 32 140
Fornecedor C 22 15 34 160
Demanda 120 130 150 –
16
17
Note que a capacidade de fornecimento é igual à demanda de consumo, assim 
temos um problema do transporte balanceado. As variáveis de decisão xij descrevem 
o transporte do fornecedor i para o consumidor j, e são descritas da seguinte forma:
11
12
13
32
33
1
2
3
2
3
x transporte de A para
x transporte de A para
x transporte de A para
x transporte deC para
x transporte deC para
=
=
=
=
=

A função objetivo tem a seguinte representação:
11 12 13 21 22 23 31 32 3312 22 30 18 24 32 22 15 34MIN Z x x x x x x x x x= + + + + + + + +
As restrições referentes à capacidade do fornecedor em atender à demanda são:
11 12 13
21 22 23
31 32 33
100
140
160
x x x
x x x
x x x
+ + =
+ + =
+ + =
As restrições referentes à demanda dos consumidores são:
11 21 31
12 22 32
13 23 33
120
130
150
x x x
x x x
x x x
+ + =
+ + =
+ + =
A resolução do modelo desenvolvido consiste em alguns passos incrementais. Pri-
meiro, vamos construir uma representação tabular do modelo. Essa representação é 
similar àquela apresentada na Tabela 2, na qual as células representam as variáveis do 
problema, as colunas representam os consumidores com suas respectivas demandas e as 
linhas representam os fornecedores e suas capacidades correspondentes. O objetivo de 
se utilizar uma representação tabular é encontrar uma solução básica para o problema.
O segundo passo consiste em selecionar a célula x11, localizada no canto superior 
esquerdo da tabela, e preenchê-la com o menor valor entre a capacidade da linha e a 
demanda da coluna. Caso o limite da capacidade (linha) ou da demanda (coluna) seja 
atingido, as células correspondentes devem ser anuladas.
O procedimento descrito deve ser repetido, descontando o valor preenchido na 
célula dos totais de capacidade e demanda, até que o quadro esteja preenchido 
por completo. 
Após o preenchimento do quadro, a solução básica esperada para esse problema 
é x11 = 100, x21 = 20, x22 = 120, x32 = 10 e x33 = 150, com Z = 9690. As variáveis 
não básicas são: x12, x13, x23, x31.
17
UNIDADE Análise de Problemas Típicos
Consumidores
Demanda
C
B
A
1 2 3
100
140
160
150130120
X
31
X
32
X
33
X
23
X
22
X
21
X
11
X
12
X
13
Ca
pa
cid
ad
e
Fo
rn
ec
ed
or
Figura 4 – Representação de quadro tabular para determinação de uma solução básica
A solução anterior é denominada Método do Canto Noroeste, o que é uma refe-
rência à ordem pela qual as células devem ser consideradas. Note que essa ordem 
não considera os custos unitários associados a cada transporte. Nesse sentido, o 
Método do Custo Mínimo é uma adaptação do método anterior, no qual a ordem de 
escolha das células é dada em função do custo correspondente, ou seja, escolhe-se 
a célula com menor custo.
Os passos para a aplicação do método do custo mínimo são similares ao método 
do canto noroeste. Primeiro, selecionamos a célula com menor custo, em seguida, 
devemos alocar a maior quantidade possível àquela célula. Caso a capacidade ou a 
demanda seja atingida, as células correspondentes deverão ser anuladas de acordo 
com os totais na linha e/ou coluna.
Considerando o quadro tabular da Figura 2, a célula com menor custo, dentre as 
disponíveis para preenchimento, é, coincidentemente, a mesma do método anterior, 
ou seja, x11 cujo custo é igual a 12. Essa célula será preenchida com o menor valor 
possível entre a demanda e a capacidade, que será 100. Veja que esse valor atinge o 
máximo da capacidade do fornecedor A, assim, as demais células na linha do forne-
cedor A (x11, x12, x13) devem ser anuladas.
Nessa configuração, a próxima célula cujo custo é o menor é a x32, a qual será 
preenchida com o valor 130. Visto que esse valor atinge o total de demanda, as 
demais células nessa coluna (x22) devem ser anuladas; nesse exemplo, há somente 
uma célula disponível que será anulada.
Após a finalização do processo, a solução básica representada pelo quadro tabular 
é: x11 = 100, x21 = 20, x23 = 120, x32 = 130 e x33 = 30, com Z = 8370. As demais 
variáveis são as não básicas.
18
19
Método de Vogel
Os métodos para resolução de problemas que envolvem redes, especificamente 
para o problema do transporte, oferecem uma solução básica viável, porém, sem 
garantias de ser uma solução ótima. Assim, vamos explorar outro método que 
pode ser considerado como uma versão melhorada do método do custo mínimo, 
visto anteriormente.
O método de Vogel foi desenvolvido tendo como base o método do custo mínimo 
e, comumente, produz melhores soluções. Conforme descrito, o método de Vogel 
é muito similar ao do custo mínimo, a principal diferença entre eles é que a escolha 
da célula, na qual será atribuída a quantidade transportada, é feita por meio de uma 
penalidade calculada. 
O cálculo da penalidade no método de Vogel é feito por meio da diferença entre 
os dois menores custos unitários (W) considerando as linhas e colunas. A penalidade 
será calculada enquanto houver, pelo menos, duas células não alocadas ou bloquea-
das. A célula escolhida para a inserção da quantidade será aquela de menor custo na 
linha ou coluna de maior penalidade; em caso de empate, escolher arbitrariamente. 
A seguir, alocar a maior quantidade possível na célula, respeitando os limites de 
capacidade e demanda das linhas e colunas, respectivamente. Se a alocação atingir 
o limite de fornecimento ou de demanda, as células na linha ou coluna devem ser 
bloqueadas. Esses passos devem ser repetidos enquanto houver mais do que uma 
célula disponível para alocação. Quando houver uma única célula disponível, alocar 
a capacidade ou demanda remanescente.
Vejamos um exemplo prático, considere a Figura 5 para a descrição do exemplo.
Figura 5 – Exemplo de aplicação do método de Vogel
Fonte: Acervo do conteudista
19
UNIDADE Análise de Problemas Típicos
Na figura anterior, o primeiro quadro apresenta a configuração inicial. Os demais 
são representativos de cadaiteração.
O quadro em destaque na parte superior da figura representa a configuração ini-
cial, antes da implementação do método de Vogel. Os valores, destacados em cinza 
no canto superior direito de cada célula, indicam o custo de transporte unitário 
entre o fornecedor (linha) e o consumidor (coluna), os quais apresentam, respectiva-
mente, capacidade de fornecimento e demanda de consumo. Note que os cálculos 
das penalidades iniciais são feitos para cada linha e coluna. Por exemplo, a primeira 
linha tem uma penalidade igual a 10, esse valor é o resultado da diferença entre os 
dois menores custos unitários nas células (22 – 12).
A primeira atribuição de quantidade foi feita na célula localizada na primeira linha 
e coluna. A escolha dessa célula foi feita porque a primeira linha é aquela que apre-
senta a maior penalidade e a primeira célula tem o menor custo. Note que o valor 
preenchido na célula é igual a 100, que é o menor valor entre a capacidade (100) e a 
demanda (120). As outras células da linha escolhida foram bloqueadas, pois o valor 
preenchido atingiu o limite máximo da capacidade daquele fornecedor.
A iteração 2 se inicia com o recálculo das penalidades, desconsiderando as células 
preenchidas ou anuladas. Após o recálculo, note que a coluna com maior penalidade 
é a segunda, e dentre as células disponíveis para preenchimento, a última célula 
apresenta o menor custo. Assim, é nessa célula que será alocada a quantidade igual 
a 130, que é o menor valor entre a capacidade e a demanda. Considerando o critério 
anterior, a célula remanescente na coluna central deve ser bloqueada, por ter atingido 
o limite máximo da demanda para aquela coluna.
Procedemos, novamente, com o recálculo das penalidades para as células rema-
nescentes. Para a iteração 3, temos a segunda linha apresentando a maior penali-
dade (14). Dentre as células disponíveis nessa linha, selecionamos a primeira célula, 
pois ela apresenta o menor custo (18). Essa célula receberá a quantidade igual a 20, 
que é o saldo remanescente da demanda da primeira coluna.
A configuração do quadro, antes da iteração 4, apresenta somente duas células 
disponíveis na última coluna. O cálculo da penalidade para essa coluna resulta em 
dois; como esse valor é único, não havendo outras linhas ou colunas com condições 
de cálculo da penalidade, a atribuição da quantidade será feita na segunda célula dessa 
coluna, que apresenta o menor custo (32). O valor atribuído nessa célula é igual a 120, 
que representa o saldo remanescente da capacidade da segunda linha.
Finalmente, há somente uma célula disponível antes da última iteração (4). 
Nessa célula será atribuído o valor 30, que é o saldo remanescente da demanda 
da última coluna.
A solução básica para o nosso exemplo é: x11 = 100, x21 = 20, x23 = 120, x32 = 130 
e x33 = 30. Com Z = 8370. As demais variáveis são não básicas.
Para testar se a solução encontrada é ótima, vamos realizar um procedimento 
denominado método dos multiplicadores. Nesse método, toda linha i e toda coluna j 
20
21
são associadas aos multiplicadores ui e vj. Consideraremos que a soma dos multipli-
cadores é igual ao custo na linha e coluna correspondente (ui + vj = cij). Para a verifi-
cação da solução, o primeiro passo é atribuir, de maneira arbitrária, o valor zero para 
um dos multiplicadores. A solução será ótima se os custos de todas as variáveis não 
básicas forem negativos (ui + vj – cij ≤ 0). Havendo uma variável não básica com custo 
positivo, haverá uma solução básica melhor.
Para exemplificar a validação de uma solução básica, considere a solução encon-
trada, para o nosso exemplo, pelo método do canto noroeste, a qual foi apresentada 
anteriormente e resulta no quadro da figura a seguir.
Custo (Cij)
100
20 120
X 10 150
12 22 30
18 24 32
341522
X X
X
Quantidade (Xij)
Figura 6 – Quadro tabular que representa a solução encontrada pelo método do canto noroeste
 As variáveis básicas da solução devem ser descritas por meio da equação ui + vj = cij, 
assim, temos o seguinte:
11 1 1
21 2 1
22 2 2
32 3 2
33 3 3
12,
18,
24,
15,
34
x u v
x u v
x u v
x u v
x u v
⇒ + =
⇒ + =
⇒ + =
⇒ + =
⇒ + =
De acordo com a descrição anterior, precisamos escolher um dos multipli-
cadores e atribuir a ele o valor zero, assim, faremos u1 = 0 e calcularemos os 
demais valores dos multiplicadores. Os resultados para os demais multiplicadores 
são v1 = 12, u2 = 6, v2 = 18, u3 = –3, v3 = 37 Com a identificação dos valores 
dos multiplicadores, podemos determinar os custos reduzidos das variáveis não 
básicas considerando a fórmula cij = ui + vi – cij.
Importante!
Veja que para calcular os valores dos multiplicadores é preciso substituir os valores iden-
tificados nas demais equações de forma sucessiva.
21
UNIDADE Análise de Problemas Típicos
12 1 2 12
13 1 3 13
23 2 3 23
31 3 1 31
0 18 22 4
0 37 30 7
6 37 32 11
3 12 22 13
c u v c
c u v c
c u v c
c u v c
= + − = + − = −
= + − = + − =
= + − = + − =
= + − = − + − = −
Os custos reduzidos das variáveis não básicas apresentam dois valores positivos 
(7 e 11), isso é o indicativo de que há uma solução básica melhor, ou seja, a solução 
testada não é ótima.
Assim como vimos no método Simplex, aqui devemos escolher uma variável não 
básica para compor a nova solução. Dessa forma, escolhemos aquela que apresentou 
o maior custo reduzido, ou seja, a variável não básica que entra é x23.
A determinação de uma solução básica melhor é feita considerando um ciclo 
fechado que inicia e termina na variável que sai. Para compor esse ciclo, deve-se uti-
lizar segmentos de reta, verticais ou horizontais, que devem estar conectados. Toda 
variável que está conectada por um segmento de reta deve ser básica, com exceção 
de x23. O ciclo conectará as seguintes variáveis: x23 → x33 → x32 → x22 → x23. Veja 
que o ciclo inicia e termina na mesma variável. A variável que sairá da base será 
adjacente à variável que entra. Entre as duas variáveis adjacentes, devemos escolher 
a de menor valor. No caso do nosso exemplo, x23 tem duas variáveis adjacentes (vi-
zinhas), x22 = 120 e x23 = 150. Assim, a variável que sairá da base é x22 que tem o 
menor valor.
Na prática, a quantidade de x22 passará para x23, cujos novos valores serão x22 = 0 
e x23 = 120. Finalmente, para manter as restrições na demanda, devemos calcular 
os novos valores para as outras variáveis no ciclo. Desse modo, temos que x32 = 130 
e x33 = 30. Veja que o ciclo identificado tem a função de facilitar o intercâmbio das 
quantidades entre as variáveis no ciclo. Se transportarmos 120 de x22 para x23 temos 
que realizar o mesmo intercâmbio entre as outras variáveis no ciclo. Assim, também 
transportamos 120 de x33 para x32.
Na realização do teste de verificação para a nova solução, veremos que os custos 
reduzidos das variáveis não básicas serão todos negativos, o que indica uma solução 
ótima. A solução ótima, nesse caso, é x11 = 100, x21 = 20, x23 = 120, x32 = 130 e 
x33 = 30, com Z = 8370.
22
23
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Vídeos
 Transporte – solução básica inicial canto noroeste
Veja a solução básica inicial no exemplo calculado pelo professor no vídeo utilizando 
o método do canto noroeste.
https://youtu.be/4SSacL3ATuY
 Problemas de Transporte ou Designação
 O vídeo mostra um Problema de Transporte, designação, alocação (custo mínimo) 
resolvido via Programação Linear no SOLVER-Excel . 
https://youtu.be/nN_eD6qHMtg
 Transporte - solução básica inicial Vogel
Agora, o professor, no vídeo, traz a solução para um exercício utilizando o métido 
de Vogel.
https://youtu.be/GRTLiJL0hdQ
 Transporte Desbalanceado (Fornecimento menor que Demanda)
O professor Aurelio Murta fala sobre o transporte desbalanceado, quando o 
fornecimento é menor que a demanda.
https://youtu.be/fUM0iimpv0s
23
UNIDADE Análise de Problemas Típicos
Referências
ANDRADE, E. L. Introdução à pesquisa operacional: métodos e modelos para a 
análise de decisão.4. ed. Rio de Janeiro: LTC, 2011.
DANTZIG, G. B. Reminiscences about the origins of linear programming. In: 
Mathematical Programming The State of the Art. Springer, Berlin: Heidelberg, 
1983.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. 
Porto Alegre: Amgh, 2013.
24