Matéria P1

Prévia do material em texto

UNIVERSIDADE FEDERAL FLUMINENSE 
ESCOLA DE ENGENHARIA 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
 
 
 
 
 
 
APOSTILA 
PESQUISA OPERACIONAL II 
 
 
 
 
 
 
 
PROFESSOR: LUIS TORRES 
MONITOR: ANDREW DE JESUS 
 
 
 
 
 
 
 
 
 
NITERÓI - RJ 
PERÍODO 2013.2 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
 
 
 
Sumário 
1. Problema do Transporte ..................................................................................... 1 
1.1 Definição: ................................................................................................... 1 
1.2 Função Objetivo: ........................................................................................ 2 
1.3 Representação Matricial: ........................................................................... 4 
1.4 Solução Inicial: ........................................................................................... 5 
Método Noroeste (NO): ......................................................................................... 5 
Método Mínimo da Linha (ML): .............................................................................. 6 
Método Mínimo da Coluna (MC): .......................................................................... 8 
Método Mínimo da Matriz (MM): ............................................................................ 9 
1.5 Encontrando o Valor das Casas não Básicas: ......................................... 10 
Método Loop: ...................................................................................................... 11 
Método UV: ......................................................................................................... 13 
1.6 Encontrando a Solução Ótima: ................................................................ 15 
1.7 Casos Especiais: ..................................................................................... 18 
PT com número de casas básicas diferente de M + N – 1: ................................. 18 
PT não equilibrado: ............................................................................................. 19 
2. Alocação ou Designação: ................................................................................. 20 
2.1 Definição: ................................................................................................. 20 
2.2 Método de Resolução: ............................................................................. 21 
2.3 Quando a Alocação não é Perfeita: ......................................................... 23 
3. Caminho Mais Curto: ........................................................................................ 24 
3.1 Definição: ................................................................................................. 24 
3.2 Método de Resolução: ............................................................................. 24 
 
 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
1 
 
 
1. Problema do Transporte 
 
1.1 Definição: 
 
O PT (Problema do Transporte) tem por objetivo determinar as quantidades de um 
determinado produto que deverão ser transportados de i origens para j destinos, dadas 
as restrições de oferta destas origens e as restrições de demanda de cada destino. 
 
 
O PT, sempre é um problema de minimização, pois tem por finalidade 
minimizar o custo do volume de transporte seguindo as necessidades de recebimento 
do destino j e a capacidade de envio das origens i. Denotando o custo unitário da 
origem i para o destino j de e chamando de o número de produtos a serem 
transportados da origem i para o destino j, segue abaixo um exemplo genérico: 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
2 
 
 
 
Na prática o problema do transporte é um problema de logística, onde 
queremos saber de qual centro de produção eu devo efetuar minha demanda a fim de 
economizar meus gastos com o transporte desse produto. Com isso, certo centro de 
produção pode oferecer uma quantidade de produtos vantajoso até certo limite e 
assim o que faltar para preencher a demanda é conseguido por meio de outro centro 
de produção. Desta forma, pode-se ter em uma demanda a chegada de mais de um 
destino, como mostrado no esquema abaixo. 
 
 
1.2 Função Objetivo: 
 
Utilizando a figura acima vamos montar a função objetivo para ver como ela fica na 
prática. Seja o PT um problema de minimização do custo do transporte temos: 
Min z = 6 + 5 + 8 + 13 + 12 + + 7 + 9 + 5 + 10 + 6 + 
4 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
3 
 
As restrições de demanda são equacionadas da seguinte maneira: 
Destino 1 tem demanda = 8, então 
 + + + = 8 
 
Destino 2 tem demanda = 32, então 
 + + + = 32 
 
Destino 3 tem demanda = 15, então 
 + + + = 15 
 
As restrições da origem são equacionadas da seguinte maneira: 
Origem 1 tem disponibilidade = 10, então 
 + + = 10 
 
Origem 2 tem disponibilidade = 20, então 
 + + = 20 
 
Origem 3 tem disponibilidade = 12, então 
 + + = 12 
 
Origem 4 tem disponibilidade = 13, então 
 + + = 13 
 
A última restrição é meio intuitiva, mas é necessário mencionar: 
Nenhuma origem pode enviar uma quantidade negativa de produtos, por isso: 
 ; 
 
Então a função objetivo completa para o exemplo acima fica: 
Min z = 6 + 5 + 8 + 13 + 12 + + 7 + 9 + 5 + 10 + 6 + 
4 
S. A: + + + = 8 
 + + + = 32 
 + + + = 15 
 + + = 10 
 + + = 20 
 + + = 12 
 + + = 13 
 ; 
 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
4 
 
1.3 Representação Matricial: 
 
A tabela matricial é usada para ilustrar e resolver o PT. Segue abaixo como é essa 
representação: 
 
Demanda 
 
 
D1 D2 D3 
 
Oferta 
O1 
Custo Custo Custo 
∑ O1 
O2 
Custo Custo Custo 
∑ O2 
O3 
Custo Custo Custo 
∑ O3 
 
∑ D1 ∑ D2 ∑ D3 
 
 Para ficar mais claro, vamos utilizar o exemplo numérico, seja o Problema de 
transporte abaixo: 
 
Para esse modelo a tabela matricial Fica: 
 
1 2 3 4
1 2 3 1 4 10
2 5 7 8 6 8
3 3 2 4 5 12
8 6 9 7
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
5 
 
1.4 Solução Inicial: 
 
Existem muitas maneiras de se encontrar a solução inicial, nesse curso, serão 
apresentadas 4 (quatro) maneiras diferentes. É preciso salientar que qualquer maneira 
pode ser utilizada e ao usar métodos diferentes pode acarretar em encontrar soluções 
iniciais diferentes. Outro ponto que devemos estar atentos é que o PT está equilibrado, 
ou seja, o somatório das demandas é igual ao somatório das ofertas, depois veremos 
que como calculamos para PTs não equilibrados. 
Método Noroeste (NO): 
Para encontrar a solução inicial usando o Método NO, começa-se alocando o 
Maior valor possível na casa (1,1), isto é, oferta 1 (um) e demanda 1 (um). O que seria 
esse maior valor possível? Perceba que existe o valor do somatório da oferta em cada 
linha e o valor do somatório da demanda em cada coluna. Quando escolhemos um 
número para colocar numa casa estamos preenchendo tanto a linha, quanto a coluna, 
desta forma o maior valor possível que podemos colocar na casa é o menor valor 
entre o somatório da demanda e somatório da oferta.Vamos usar o exemplo fornecido 
para esclarecer essa questão. 
 
No Método NO, temos que começar sempre pela casa (1,1). Depois temos que 
alocar o maior valor possível. Já que temos na linha, como somatório de oferta 10 
(dez), e na coluna, como somatório de demanda 8 (oito), escolheremos o menor deles. 
Nesse caso é o 8 (oito). 
 
Quando alocamos um número ele irá subtrair tanto a coluna, quanto na linha. 
Como escolhemos o 8 (oito), agora iremos subtrair 8 (oito) da linha, que fica 10 (dez) – 
8 (oito) = 2 (dois). E subtrairemos 8 (oito) da coluna, que fica 8 (oito) – 8 (oito) = 0 
(zero). 
Desta forma, aparece o zero na coluna, isto significa que não podemos alocar 
mais nenhum número nessa coluna, esgotou-se a demanda. Entretanto, ainda há 
oferta de 2 (dois), na primeira linha. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
6 
 
 Para continuarmos o Método NO, temos que terminar a primeira linha ou a 
primeira coluna. Em nosso exemplo falta terminar a primeira linha, então na casa ao 
lado, ou seja, casa (1,2) deve ser alocado o maior valor possível, que será ou 2 (dois) 
que é o somatório da oferta na linha ou 6 (seis) que é o somatório da demanda na 
coluna. Escolheremos o 2 (dois) e procederemos da mesma forma. Retiramos 2 (dois) 
tanto da linha de oferta quanto da coluna de demanda. 
 
Igualmente procedemos anteriormente, devemos continuar. Temos que pensar 
sempre em eliminar uma linha e uma coluna. No passo anterior eliminamos a primeira 
coluna, agora eliminamos a primeira linha. O próximo passo é eliminar a segunda 
coluna. Então descemos para a casa (2,2) e repetimos rigorosamente os mesmos 
procedimentos até chegarmos em: 
 
Logo a solução inicial é: = 8, = 2, = 4, = 4, = 5 e = 7, as 
demais variáveis são zero. 
Com isso o valor da função objetivo que é: 
Min Z = 2 + 3 + +4 +5 +7 +8 +6 +3 +2 +4 +5 , ficará: 
Z = 2(8)+ 3(2)+ (0)+ 4(0)+ 5(0)+ 7(4)+ 8(4)+ 6(0)+ 3(0)+ 2(0)+ 4(5)+ 5(7)= 137 
OBS: Se não quiser montar a função objetivo para achar seu valor, basta multiplicar o 
valor da casa alocada pelo seu respectivo custo e somar todos esses valores. 
Método Mínimo da Linha (ML): 
O Método ML é bem intuitivo e para exemplificar utilizaremos o mesmo 
exemplo usado no Método NO. 
Começamos na primeira linha e encontramos a casa de menor custo; 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
7 
 
Se tiver mais de uma casa com o menor custo, escolha a que o somatório da 
posição da casa for o menor. Por exemplo. Se a casa (1,1) tiver o mesmo custo da 
casa (1,2), escolheremos a casa (1,1), pois o somatório 1(um) + 1(um) é menor que 
1(um) + 2(dois). 
Colocamos o maior valor possível na casa escolhida, esse maior valor deve ser 
escolhido da mesma forma que no método anterior, se atentando tanto para o 
somatório da linha, quanto o somatório da coluna; 
 
Se por acaso o somatório da primeira linha ainda não for 0(zero), escolhemos, 
na mesma linha, o próximo número que tiver o menor custo e colocamos o máximo 
nessa posição. Faça isso até a primeira linha não ter mais ofertas; 
 
 
Terminando a primeira linha vá para a segunda linha e repita os mesmos 
passos; 
 
 
Seguindo rigorosamente os mesmos passos para as demais linhas 
chegaremos a matriz completa; 
 
 
Logo a solução inicial é: = 1, = 9, = 7, = 1, = 6 e = 6, as 
demais variáveis são zero. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
8 
 
Com isso o valor da função objetivo é: Z = 2(1)+ 1(9)+ 5(7)+ 6(1)+ 2(6)+ 5(6)= 
94. 
OBS: Perceba que a solução inicial data pelo Método ML foi diferente do Método NO. 
Método Mínimo da Coluna (MC): 
O Método MC segue as mesmas regras do Método ML, só que agora as regras 
valem para as colunas. Usaremos o mesmo exemplo usado nos métodos anteriores. 
Começamos na primeira coluna e encontramos a casa de menor custo; 
 
 
Se tiver mais de uma casa com o menor custo, escolha a que o somatório da 
posição da casa for o menor. Por exemplo. Se a casa (1,1) tiver o mesmo custo da 
casa (3,1), escolheremos a casa (1,1), pois o somatório 1(um) + 1(um) é menor que 
3(três) + 1(um). 
 
Colocamos o maior valor possível na casa escolhida, esse maior valor deve ser 
escolhido da mesma forma que no método anterior. 
 
 
 
Se por acaso o somatório da primeira coluna ainda não for 0(zero), 
escolhemos, na mesma coluna, o próximo número que tiver o menor custo e 
colocamos o máximo nessa posição. Faça isso até a primeira coluna não ter mais 
demandas; 
 
Terminando a primeira coluna vá para a segunda e repita os mesmos passos; 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
9 
 
 
 
Como terminamos a segunda coluna, seguimos para as próximas sempre 
repetindo os mesmos passos. E assim chega-se na matriz completa. 
 
 
 
Logo a solução inicial é: = 8, = 2, = 1, = 7, = 6 e = 6, as 
demais variáveis são zero. 
Com isso o valor da função objetivo é: Z = 2(8) + 1(2) + 8(1) + 6(7) + 2(6) + 4(6)= 104 
OBS: Perceba que a solução inicial data pelo Método MC foi diferente tanto do 
Método ML, quando do Método NO. 
Método Mínimo da Matriz (MM): 
O Método MM é como se fosse a união dos dois métodos apresentados 
anteriormente. Encontramos a casa de menor custo da Matriz inteira e colocamos o 
maior valor possível; 
 
 
Se tiver mais de uma casa com o menor custo, escolha a que o somatório da 
posição da casa for o menor. Nesse caso, acontece um empate temos o custo 2 na 
casa (1,1) e na casa (3,2). Escolheremos a casa (1,1), pois o somatório de sua 
posição 1(um) + 1(um) é menor que o da casa (3,2) que é 3(três) + 1(um). Logo 
alocamos primeiro na casa (1,1). Se após alocarmos nesse local ainda for possível 
usar a casa de mesmo custo, nós a usamos. Que é o que acontece nesse exemplo. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
10 
 
 
 
Nesse método não importa se estamos preenchendo uma linha ou coluna 
completa, o que importa é colocar o maior valor possível nos menores custos da 
matriz. Irá chegar um momento que todos os somatórios das linhas e colunas estarão 
completos. 
 
Quando fomos alocar em uma casa de menor custo e sua linha e/ou coluna 
estiverem completas, então procure a próxima casa de menor custo. 
 
 
Nesse caso temos as casas (1,2), (1,4), (3,3) e (3,4), menores que a casa (2,4), 
só somente a casa (2,4), pode receber fluxo as demais casas já possuem demanda 
e/ou oferta esgotadas Assim segue a matriz completa. 
 
Logo a solução inicial é: = 1, = 9, = 1, = 7, = 6 e = 6, as 
demais variáveis são zero. 
Com isso o valor da função objetivo é: Z = 2(1)+ 1(9)+ 5(1)+ 6(7)+ 3(6)+ 2(6)= 
88. 
OBS: Perceba que a solução inicial data pelo Método MM, foi menor que a dos outros 
métodos. No geral, esse método oferecerá uma solução inicial menos, pois busca os 
menores custos da matriz desde o início. 
1.5 Encontrando o Valor das Casas não Básicas: 
 
Antes de descobrir quais os passos para encontrar a solução ótima do PT, 
precisamos apresentar algumas notações importantes. As casas da matriz que são 
preenchidas com fluxo, isto é, com valores são conhecidas como casas básicas. Logo, 
as casas que não tem fluxo são chamadas de casas não básicas. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
11 
 
Para ser possível encontrar a solução ótima é necessárioque se tenha M + N – 1 
casas básicas, ou seja as casas básicas devem ter o número correspondente a soma 
do número de ofertas mais o número de demandas menos 1(um). No exemplo anterior 
o número de casas básicas era 6(seis) = 4(quatro) + 3(três) – 1(um). 
Esse dado é importante, pois para se achar a solução ótima de um PT é preciso 
conhecer o valor das casas não básicas. Veremos abaixo dois métodos para se 
encontrar o valor das casas não básicas, que são o Loop e o UV. 
 
Método Loop: 
Depois de achar a solução inicial por NO, MM, MC ou ML, temos os valores das casas 
básicas. Agora o objetivo é encontrar os valores das casas não básicas. O Método 
Loop é usado para encontrar o valor das casas não básicas. Como é um método novo, 
usaremos como base uma solução inicial para explicar seu passo a passo. 
Escolhendo a solução inicial obtida pelo Método NO, temos: 
 
Verifique se possui M+ N– 1 números de casas básicas; 
Nesse exemplo 4(quatro) + 3(três)– 1(um) = 6(seis) e é esse o número de casas 
básicas desse exemplo. 
 
 Escolhemos ao acaso uma casa não básica qualquer, que se deseja saber seu 
valor; 
Por exemplo a casa (2,1): 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
12 
 
Após escolher essa casa não básica, iremos percorrer a matriz até voltar para a 
mesma casa não básica, passando somente por casas básicas da seguinte maneira: 
Alternando caminhos horizontais e verticais ou alternando caminhos verticais e 
horizontais. 
a) 
Ou 
b) 
No caso a) começamos indo para uma casa básica horizontal, então a próxima 
casa básica terá que ser, obrigatoriamente, na vertical. Já o caso b) começamos para 
uma casa básica vertical, assim a próxima casa básica, obrigatoriamente, será na 
horizontal. 
a) 
Ou 
 
b) 
Repita essa alternância até retornar a casa não básica inicial. Para o nosso 
exemplo, em ambos os casos chegaremos na matriz da seguinte forma: 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
13 
 
Após completar a volta até a casa não básica escolhida, iremos intercalar adições 
e subtrações com os custos de cada casa fazendo (+, -, +, -,...). Sempre iniciará 
adicionando (positivo) e terminará subtraindo (negativo). 
Saber se é positivo ou negativo independe se é horizontal ou vertical, só depende 
da sequencia que é começar com positivo e ir alternando com negativo, até chegar na 
última casa, que necessariamente tem que ser negativa. 
 
O valor que restar após adicionarmos e subtrairmos os custos, esse sim, será o 
valor da casa não básica. No nosso exemplo o valor da casa não básica (2,1), será: 
Casa (2,1) = +7 –3 +2 –5 = 1. 
Repete-se esse procedimento para todas as outras casas não básicas, até 
encontrar o valor de todas elas. 
 
A solução será ótima se todas as casas não básicas forem negativas, pois o PT 
é um problema de minimização. Se elas não forem negativas ou 0(zero) teremos que 
transforma-las. 
Método UV: 
Outro método para achar os valores das casas não básicas é o Método UV. 
Segue abaixo o esquema desse método e suas respectivas etapas: 
 
 
Fixamos qualquer valor para um determinado U ou V. Pode ser qualquer U ou 
qualquer V da matriz. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
14 
 
No nosso exemplo vamos escolher o e daremos o valor 0(zero), isto é, =0 . 
 
 
Iremos utilizar esse valor determinado para encontrar os demais U’s e V’s. 
Para encontrar o valor dos outros U’s e V’s use a equação: 
 + = 
 
 
 
Agora repita o processo até achar todos os U’s e V’s. Sempre usando como 
base um U ou um V que já foi encontrado. 
 
Para encontrar o valor das casas não básicas use a equação: 
 + – = Valor da Casa não Básica 
 
Basta fazer o mesmos passos até encontrar o valor de todas as casas não 
básicas. O valor das casas não básicas encontradas pelo Método Loop tem que ser 
rigorosamente os mesmos encontrados pelo Método UV. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
15 
 
 
1.6 Encontrando a Solução Ótima: 
Agora que já sabemos como encontrar os valores das casas não básicas, 
podemos encontrar a solução ótima, a qual acontecerá quando todos os valores das 
casas não básicas forem negativos. Portanto, utilizando qualquer método, seja Loop 
ou seja UV, encontre a solução inicial. Para o nosso exemplo, temos: 
 
Para encontrar a solução ótima, primeiramente escolhemos a casa não básica com 
maior valor positivo, se der empate escolha a que tiver menor custo. 
 
Refaça o Loop e escolha, dentre os valores positivos desse Loop, a casa que 
tiver o menor valor de fluxo. Se der empate, escolha a que tem o menor custo. 
 
As casas positivas do Loop são a casa (1,2), a qual tem valor 2, e a casa (2,3), que 
tem valor 4. Escolhemos a casa (1,2), pois seu valor é menor. 
Então, colocamos esse valor, o 2 (dois) da casa (1,2), na posição do maior valor 
da casa não básica escolhido anteriormente, na casa (1,3) a qual era a posição do 3 
(três) que era o maior valor de casa não básica. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
16 
 
Agora esse novo valor “se transforma” em casa básica e temos que encontrar uma 
nova solução inicial para esse PT, pois agora ele não está equilibrado, isto é, na 
coluna 2 está faltando completar 2 (dois) da demanda e em contra partida está 
sobrando 2 (dois) na coluna 3. E será mudado os valores de fluxo que participaram do 
Loop, os outros permaneceram com os mesmos valores de fluxo. 
 
Depois de encontrar a nova solução inicial, calcula-se o valor da função 
objetivo que tem que ser menor ou no mínimo igual ao valor anterior. Para esse 
exemplo, temos como valor da função objetivo é: Z = 2(8)+ 1(2)+ 7(6)+ 8(2)+ 4(5)+ 
5(7)= 131, que é menor que o valor anterior, o qual era z = 137. 
 
Refazendo o calculo das casas não básicas, por Loop ou UV, chegamos a: 
 
Como todas as casas não básicas não são negativas, significa que ainda não 
chegamos até solução ótima, para encontrá-la basta repetir o mesmo processo 
anterior, de ver a casa não básica com maior valor, refazer seu Loop e substituir o 
menor valor de fluxo da casa positiva do Loop pela casa não básica de maior valor 
escolhida anteriormente. Fazendo esse processo, teremos: 
 
Ainda não é a solução ótima, mas a função objetivo reduziu para Z = 123. 
Contudo, necessitaremos refazer o processo, assim a nova matriz fica: 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
17 
 
Por mais que tenhamos reduzido a função objetivo para Z = 98, ainda não é a 
solução ótima. É possível reduzir mais, pois todas as casas não básicas ainda não são 
todas negativas. Refazendo o processo teremos: 
 
Consegui-se reduzir a função objetivo para Z = 97, mas não teremos a solução 
ótima enquanto tivermos casas não básicas positivas. Por isso, mais uma vez 
devemos aplicar o processo. Desta forma chegaremos na matriz: 
 
Não é a solução ótima, e inclusive, o valor da função objetivo não foi alterado. 
Novamente repetindo o procedimento teremos a nova matriz: 
 
Por mais que tenhamos apenas um valor positivo, isso é o suficiente para essa 
solução não ser ótima, apesar de termos reduzido o valor da função objetivo para Z = 
94. Então, deveremos repetir todo o passa a passo novamente. 
 
Depois de muitas tentativas, agora sim temos a solução ótima com Z = 88 com 
soluçãoótima: = 1, = 9, = 1, = 7, = 6 e = 6. Com isso, vemos que 
pode ser bem trabalho encontrar a solução ótima, todavia, basta repetirmos sempre o 
mesmo processo que chegaremos até a solução do PT. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
18 
 
1.7 Casos Especiais: 
PT com número de casas básicas diferente de M + N – 1: 
 
Algumas vezes, ao resolvermos um PT, não encontramos M + N – 1 casas 
básicas, desta forma, precisaremos acrescentar uma casa básica para assim 
conseguirmos dar prosseguimento a resolução do PT. Vamos utilizar o PT abaixo para 
ajudar na explicação: 
 
 
 
Achando a solução inicial por NO, temos: 
 
Perceba que não há M + N – 1 casas básicas. Isto ocorre pelo fato de na 
primeira casa, eliminarmos simultaneamente a oferta (linha) e a demanda (coluna). 
Neste momento, devemos escolher na casa (1,1), que foi a casa onde foram 
eliminados simultaneamente a linha e coluna, colocar um 0 (zero), como casa básica, 
ou na linha 1 ou na coluna 1. 
 
 
 
Agora temos que determinar o valor das casas não básicas, pode ser pelo 
Método Loop ou Método UV. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
19 
 
O valor da função objetivo é Z = 220. Porém, não encontramos a solução ótima 
ainda. Consequentemente, teremos que utilizaremos o procedimento aprendido 
anteriormente, que é escolher o maior valor positivos das casas não básicas e 
substituí-lo pela casa positiva do Loop que tiver menor fluxo. Com isso, teremos a 
seguinte matriz, após recalcularmos o valor das casas básicas: 
 
Essa matriz não é a ótima, a casa (1,4) é a única positiva e isso nos mostra 
que não é a solução ótima. O valor da função objetivo reduziu para Z = 175. 
Refazendo os passos para encontrar a solução ótima obteremos a matriz: 
 
Chegamos então na matriz ótima que apresenta como valor ótimo de Z = 175, 
com solução ótima: = 5, = 0, = 10, = 15, = 5 e = 10. 
OBS: Como existe um 0 (zero) em casa não básica, significa que essa solução é 
ótima, porém não é única. 
PT não equilibrado: 
 
Quando a soma das linhas (oferta) e das colunas (demanda) não dá o mesmo 
resultado, dizemos que o PT não está equilibrado. Veja o exemplo abaixo: 
 
 
Se tivermos mais oferta que demanda, que é o nosso exemplo, deveremos 
acrescentar uma coluna de demanda “fantasma” com cada custo igual a zero e com 
valor de demanda grande o suficiente para equilibrar com a oferta. O mesmo vale para 
a oferta. Caso tenhamos mais demanda que oferta, teremos que acrescentar uma 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
20 
 
linha de oferta “fantasma” com cada custo igual a zero e com valor de oferta grande o 
suficiente para equilibrar com a demanda. Realizando o procedimento descrito 
chegamos a matriz: 
 
Agora podemos resolver normalmente o PT. 
2. Alocação ou Designação: 
2.1 Definição: 
É um caso particular do problema do transporte. É uma matriz quadrada, isto é, o 
número de centros de produção (linhas) é igual ao número de centros de consumo 
(colunas). Se tiver algum centro de produção ou consumo a menos, deveremos 
acrescentar um centro “fantasma”. 
Nos problemas de Alocação e designação as demandas e as ofertas são iguais a 1 
(um). Vejamos um exemplo abaixo que mostra os centros de produção e centros de 
consumo (em azul), os custos (em vermelho) e o somatório do produzido e do 
consumido (em preto), sendo igual a 1 (um). 
 
OBS: Esse tipo de Problema do Transporte sempre terá solução e ela sempre será 
inteira. 
 
 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
21 
 
A função objetivo e as restrições para esse tipo de PT é obtida igualmente a feita 
nos itens anteriores: 
Min Z= 3 + 2 + 5 + 4 + 0 + 1 + 2 + 3 + 4 + 1 + (-1) +3 
+ 2 + 5 +3 +4 
S. A: + + + = 1 
 + + + = 1 
 + + + = 1 
 + + + = 1 
 
 + + + = 1 
 + + + = 1 
 + + + = 1 
 + + + = 1 
 
1 ; 
2.2 Método de Resolução: 
Para resolver os problemas de Alocação e Designação, usando a tabela abaixo 
como exemplo, temos que seguir os seguintes procedimentos: 
 
Primeiramente temos que ter, pelo menos, um zero em cada linha, isto é, um custo 
igual a 0 (zero). Caso não tenhamos, iremos pegar o menor custo da 1º linha e 
subtraí-lo dos demais custos da 1º linha. Depois pegamos o menor custo da 2º linha e 
subtraímos dos demais custos da 2º linha. Iremos fazer isso em cada linha começando 
da 1º linha, até a última. Caso tenhamos zeros nas linhas devemos mantê-lo e não 
efetuar a subtração. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
22 
 
Com isso a tabela ficará com os seguintes valores: 
 
Depois que encontrar um 0 (zero) em cada linha, repita o mesmo procedimento 
para as colunas, pegando o menor número de cada coluna e subtraindo dos demais 
da mesma coluna até que todas tenham pelo menos um 0 (zero). 
 
Agora, alocaremos exatamente 1 (uma) oferta com 1 (uma) demanda, somente 
onde existam zeros. A alocação é da seguinte maneira: se alocamos a casa (1,1) não 
poderemos mais alocar nenhum zero que esteja na 1º linha e na 1º coluna. 
 
Nesse exemplo conseguimos a alocação perfeita. Desta forma temos como 
solução ótima: = = = = 1; caso contrário = 0. 
Perceba que como alocamos a casa (1,2), não poderíamos alocar a casa (1,4), 
pois por mais que seja zero, já alocamos um 0 (zero) na primeiro centro de produção 
(1º linha). 
Entenda este problema como uma analogia a uma faculdade que possui 
professores (linhas) e disciplinas (colunas). Porém, um professor só pode lecionar uma 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
23 
 
disciplina. Assim, não podemos ter dois professores para uma disciplina e nem um 
professor para duas disciplinas. 
2.3 Quando a Alocação não é Perfeita: 
Vejamos o exemplo abaixo para o caso de não conseguirmos a alocação perfeita. 
 
Inicialmente encontre um 0 (zero) em cada linha e depois, encontre um 0 (zero) em 
cada coluna. Utilizando o método descrito anteriormente. 
 
Agora que já possuímos pelo menos um 0 (zero) em cada linha e em cada coluna, 
podemos alocá-los. Contudo, não conseguiremos alocar a quantidade suficiente para 
que todas os centros de produção e centros de consumo se equilibrem. O máximo que 
chegaremos é a duas alocamos como por exemplo: 
 
Para conseguir resolver esse problema iremos fazer o seguinte. Como possuímos 
dois 0 (zeros) alocados, iremos traçar duas retas que cortem todos os zeros da 
matriz. 
 
Dos números que não foram cortados, pegamos o menor deles e subtraímos dos 
demais. E o número que foi cortado por duas retas, nesse exemplo o 3 (três), iremos 
adicionar esse menor número. 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
24 
 
 
Neste exato momento possuímos um número maior de 0 (zeros), com isso, 
conseguiremos a alocação perfeita. 
 
Agora conseguimos a alocação perfeita. Desta forma temos como solução 
ótima: = = = 1; caso contrário = 0. 
3. Caminho Mais Curto: 
3.1 Definição: 
Um dos problemas mais comuns a serem resolvidos em redes é determinar o 
caminho mais curto que pode fluir em determinada rede. Ela é importante, pois 
sabemos efetuar a escolha dequal caminho terá o menor custo entre os nós. 
3.2 Método de Resolução: 
 
Para resolver o problema do Caminho Mais Curto é preciso salientar que só 
podemos ter fluxo de um nó de número menor para um nó de número maior. 
 Começamos marcando um 0 (zero) sobre o primeiro nó. Depois devemos ir de nó 
a nó avaliando qual é o caminho de menor custo e escolhendo esse caminho de 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
25 
 
menor custo devemos colocar esse valor sobre o seu respectivo nó. Por exemplo, 
quantos caminhos temos para se chegar ao nó 2 (dois) ? Apenas o caminho (1,2) que 
possui um custo de 6 (seis) unidades monetárias. Com isso, precisa-se colocar o valor 
desse custo sobre o nó 2 (dois). 
 
Continuando temos que nos fazer a pergunta: quantos caminhos temos para 
chegar no próximo nó ? Nesse caso, o próximo nó é o 3 (três), e existe somente o 
caminho (1,3) que custa 9 (nove) unidades monetárias. Colocamos esse valor de 
custo sobre o nó 3 (três) e continuamos o processo. 
Quantos caminhos existem para chegar ao nó 4 (quatro) ? Para esse caso, há os 
caminhos (1,4), (2,4) e o (3,4), que custam respectivamente 3 (três), 10 (dez) e 11 
(onze). Repare que os valores de custo são acumulativos. Do nó 2 (dois) para o 4 
(quatro) custa apenas 4 (quatro) unidades monetárias, só que para ter chegado ao nó 
2(dois) já foram gastos 6 (seis) unidades monetárias, de modo que se faz necessário 
efetuar a soma dos custos, o mesmo aconteceu com o caminho (3,4) ele acumula o 
valor do caminho (1,3). Por isso, escolheremos o caminho (1,4), porque é o de menor 
custo. 
 
 
Apostila Pesquisa Operacional II 
Professor: Luis Torres 
Monitor: Andrew de Jesus 
 
 
26 
 
Prosseguimos com essa metodologia até o término dessa rede. Segue abaixo a 
rede preenchida completamente. 
 
Logo, depois de certificarmos todos os caminhos, conseguimos enxergar qual é o mais 
curto. Esse caminho mais curto é: (1,4), (4,5) e (5,7) com custo . Segue abaixo 
a representação gráfica do caminho mais curto.