Explicação do método húngaro

Prévia do material em texto

O Me´todo Hu´ngaro de Otimizac¸a˜o para o
Problema da Alocac¸a˜o de Tarefas
La´ıs Ba´ssame Rodrigues∗ Flaviano Bahia P. Vieira† Edson Agustini‡
Faculdade de Matema´tica - Famat
Universidade Federal de Uberlaˆndia - Ufu - MG
Abril de 2005
Resumo
Neste trabalho, apresentamos o estudo de um algoritmo de otimizac¸a˜o de um
caso particular de problema de transporte em programac¸a˜o linear: o problema da
alocac¸a˜o de tarefas. O algoritmo e´ chamado de “Me´todo Hu´ngaro” e foi criado
pelos hu´ngaros D. Ko¨nig e E. Egerva´ry. Por tratar-se de um me´todo discreto de
otimizac¸a˜o, baseado na manipulac¸a˜o de matrizes, no qual na˜o e´ necessa´rio o uso
de Ca´lculo Diferencial e Integral, os pre´-requisitos sa˜o mı´nimos, o que torna sua
compreensa˜o e utilizac¸a˜o extremamente acess´ıveis.
1 Introduc¸a˜o
Em nossa sociedade, e´ muito frequ¨ente depararmos com problemas que requerem tomadas
de deciso˜es visando a melhoria da relac¸a˜o custo-benef´ıcio por meio da maximizac¸a˜o ou
minimizac¸a˜o de elementos do problema. Esse tipo de problema forma uma classe especial
de problemas de otimizac¸a˜o, ou seja, problemas cuja soluc¸a˜o consiste em maximizar ou
minimizar uma func¸a˜o nume´rica de um determinado nu´mero de varia´veis (ou func¸o˜es),
estando estas sujeitas a certas restric¸o˜es.
Por exemplo: quantidades dadas xij de um determinado produto esta˜o dispon´ıveis em
cada origem i de um determinado nu´mero m de origens (por exemplo, armaze´ns). Dese-
jamos remeter essas quantidades de produto a cada destino j de um determinado nu´mero
n de destinos (por exemplo, mercados varejistas). E´ conhecido o custo do transporte
cij da quantidade xij de qualquer origem i para qualquer destino j. Considerando que e´
poss´ıvel embarcar de qualquer um dos armaze´ns para qualquer um dos mercados, estamos
interessados em determinar os itinera´rios de menor custo dos armaze´ns aos mercados.
∗laisbassame@hotmail.com Orientanda do Programa de Educac¸a˜o Tutorial da Faculdade de
Matema´tica (PetMat) de jan/04 a dez/04.
†fbahia@mat.ufu.br Orientando do Programa de Educac¸a˜o Tutorial da Faculdade de Matema´tica
(PetMat) de jan/04 a dez/04.
‡agustini@ufu.br Professor orientador.
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 25
O exemplo acima e´ um t´ıpico problema de transporte com mn varia´veis e n + m
restric¸o˜es, estudado e resolvido com te´cnicas de programac¸a˜o linear. Neste caso, a func¸a˜o
a ser minimizada e´
z (x11, x12, ..., xmn) =
n∑
j=1
m∑
i=1
cijxij,
sujeita a`s restric¸o˜es
n∑
j=1
xij ≤ ai
m∑
i=1
xij = bj
sendo ai a quantidade de produto dispon´ıvel na origem i e bj a quantidade do produto
requerida no destino j.
Nosso objetivo neste trabalho e´ estudar um caso bastante particular de problema de
transporte: os problemas de alocac¸a˜o de tarefas, em que as varia´veis xij podem assumir
apenas valores 0 ou 1 (portanto, minimizac¸a˜o ou maximizac¸a˜o de uma func¸a˜o z discreta);
ai = bj = 1 e n = m.
Um ponto do domı´nio de z, sujeita a`s restric¸o˜es do para´grafo acima, corresponde a
uma alocac¸a˜o de tarefas. A imagem de z no referido ponto e´ o custo da alocac¸a˜o. Quando
uma alocac¸a˜o e´ efetuada (escolhida) tendo em vista a minimizac¸a˜o ou maximizac¸a˜o de z,
temos uma alocac¸a˜o o´tima de tarefas. A matriz
C =
 c11 ... c1n... . . . ...
cn1 ... cnn

e´ chamada de matriz-custo.
Mais adiante redefiniremos esses conceitos baseados apenas na matriz-custo, particu-
larizada para os casos que sera˜o levados em conta nesse trabalho.
Mais especificamente, nas pro´ximas sec¸o˜es, objetivamos trabalhar um me´todo (algo-
ritmo) de otimizac¸a˜o discreto sobre a matriz C para problemas de alocac¸a˜o de tarefas
chamado de Me´todo Hu´ngaro. Esse nome teve origem em 1955 devido a H. W. Kuhn,
pesquisador na a´rea de programac¸a˜o linear, que em um de seus trabalhos, [7], fez home-
nagem aos descobridores do algoritmo em 1931: os hu´ngaros E. Egerva´ry [4] e D. Ko¨nig,
sendo que este u´ltimo demonstrou um teorema combinato´rio em 1916 que serviu de base
para o algoritmo (Teorema de Ko¨nig).
O Me´todo Hu´ngaro pode ser aplicado em diversos problemas pra´ticos de alocac¸a˜o de
tarefas desde que se construa, de forma conveniente, a matriz-custo C com as informac¸o˜es
de que dispomos do problema. A partir de C, apo´s a demonstrac¸a˜o de alguns resultados,
o referido algoritmo recursivo de execuc¸a˜o e´ montado e aplicado; podendo, inclusive, ser
implementado computacionalmente, quando o volume de informac¸o˜es do problema for
muito grande.
Algumas situac¸o˜es e problemas sa˜o exemplificados no trabalho, dentre os quais alguns
que possuem mais de uma alocac¸a˜o o´tima de tarefas.
Edson
Edson
26 FAMAT em Revista - Número 04 - Abril de 2005
2 Um Problema de Alocac¸a˜o de Tarefas
Consideremos o seguinte exemplo:
Uma construtora possui treˆs garagens cada qual possui uma escavadeira. As escav-
adeiras devem ser transportadas para treˆs obras distintas e o custo do transporte de cada
escavadeira para cada obra e´ dado pela seguinte matriz-custo:
Obra 1 Obra 2 Obra 3
Escavadeira 1 R$ 900,00 R$ 750,00 R$ 750,00
Escavadeira 2 R$ 350,00 R$ 850,00 R$ 550,00
Escavadeira 3 R$ 1.250,00 R$ 950,00 R$ 900,00
Cada poss´ıvel alocac¸a˜o de tarefas (escavadeira ←→ obra) resulta em um certo custo.
Nosso objetivo e´ minimizar esse custo. E´ claro que, nesse exemplo, uma listagem dos seis
custos poss´ıveis resolveria o problema:
Escavadeira 1 - Obra 1 R$ 900,00
Escavadeira 2 - Obra 2 R$ 850,00
Escavadeira 3 - Obra 3 R$ 900,00
Total R$ 2.650,00
Escavadeira 1 - Obra 1 R$ 900,00
Escavadeira 2 - Obra 3 R$ 550,00
Escavadeira 3 - Obra 2 R$ 950,00
Total R$ 2.400,00
Escavadeira 1 - Obra 2 R$ 750,00
Escavadeira 2 - Obra 1 R$ 350,00
Escavadeira 3 - Obra 3 R$ 900,00
Total R$ 2.000,00
Escavadeira 1 - Obra 2 R$ 750,00
Escavadeira 2 - Obra 3 R$ 550,00
Escavadeira 3 - Obra 1 R$ 1.250,00
Total R$ 2.550,00
Escavadeira 1 - Obra 3 R$ 750,00
Escavadeira 2 - Obra 1 R$ 350,00
Escavadeira 3 - Obra 2 R$ 950,00
Total R$ 2.050,00
Escavadeira 1 - Obra 3 R$ 750,00
Escavadeira 2 - Obra 2 R$ 850,00
Escavadeira 3 - Obra 1 R$ 1.250,00
Total R$ 2.850,00
No entanto, para matrizes-custo maiores, esse procedimento se torna impratica´vel.
Observemos que, de acordo com o que descrevemos na Sec¸a˜o “Introduc¸a˜o”, a func¸a˜o
a ser minimizada e´
z (x11, x12, ..., x33) =
3∑
j=1
3∑
i=1
cijxij
sujeita a`s restric¸o˜es:
3∑
j=1
xij ≤ 1⇒

x11 + x12 + x13 ≤ 1
x21 + x22 + x23 ≤ 1
x31 + x32 + x33 ≤ 1
e
3∑
i=1
xij = 1⇒

x11 + x21 + x31 = 1
x12 + x22 + x32 = 1
x13 + x23 + x33 = 1
.
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 27
Como xij ∈ {0, 1} , temos que as restric¸o˜es acima implicam que a matriz [xij]3×3 deve
possui apenas um “1” em cada linha e em cada coluna. O resto das entradas devem ser
“0”.
A matriz-custo e´ dada por:
C =
 c11 c12 c13c21 c22 c23
c31 c32 c33
 =
 900 750 750350 850 550
1250 950 900

Pelo rastreamento feito acima, z tera´ valor mı´nimo quando
Escavadeira 1 - Obra 2 ⇒ x12 = 1
Escavadeira 2 - Obra 1 ⇒ x21 = 1
Escavadeira 3 - Obra 3 ⇒ x33 = 1
e o resto dos xij
′s sa˜o zeros.
Assim,
z (0, 1, 0, 1, 0, 0, 0, 0, 1) = 900. (0) + 750. (1) + 750. (0)
+ 350. (1) + 850. (0) + 550. (0)
+ 1250. (0) + 950. (0) + 900. (1)
= 2000
e´ o custo mı´nimo. Notemos tambe´m que z e´ a soma de todas as entradas da “matriz-
produto”  c11 c12 c13c21 c22 c23
c31 c32 c33
 .
 x11 x21 x31x12 x22 x32
x13 x23 x33
 =
 c11x11 c12x12 c13x13c21x21 c22x22 c23x23
c31x31 c32x32 c33x33

Ha´ va´riassituac¸o˜es onde problemas de otimizac¸a˜o discretos aparecem. Ale´m de
maquina´rio em locais de construc¸a˜o, podemos querer encontrar a melhor distribuic¸a˜o de
trabalhadores em empregos, jogadores em posic¸o˜es no campo, ofertas em leilo˜es e assim
por diante.
Adotando a nomenclatura tarefas e instalac¸o˜es independente da natureza do problema,
para tratar o problema de alocac¸a˜o de tarefas que estamos interessados, e´ necessa´rio que
haja n tarefas e n instalac¸o˜es. Assim, temos n maneiras de alocar a primeira tarefa, n−1
maneiras de alocar a segunda tarefa, n − 2 maneiras de alocar a terceira tarefa e assim
por diante. Ou seja, existem n! maneiras distintas de alocar as tarefas a`s instalac¸o˜es.
3 Algumas Definic¸o˜es e o Teorema da Alocac¸a˜o O´tima
Embora ja´ tenhamos utilizado as nomenclaturas matriz-custo, alocac¸a˜o de tarefas, custo
da alocac¸a˜o e alocac¸a˜o o´tima de tarefas na Sec¸a˜o “Introduc¸a˜o” quando cita´vamos o prob-
lema de alocac¸a˜o de tarefas em termos da func¸a˜o z e suas restric¸o˜es, iremos redefinir esses
termos com o objetivo de, doravante, simplificar as notac¸o˜es e preparar os pre´-requisitos
para o Me´todo Hu´ngaro.
Edson
Edson
28 FAMAT em Revista - Número 04 - Abril de 2005
Definic¸a˜o Uma matriz-custo C e´ definida como sendo uma matriz n × n dada
por:
C =

c11 c12 ... c1n
c21 c22 ... c2n
...
...
. . .
...
cn1 cn2 ... cnn
 ,
sendo cij ∈ R o custo para alocar a` i-e´sima instalac¸a˜o a j-e´sima tarefa.
Definic¸a˜o Dada uma matriz-custo C de ordem n, uma alocac¸a˜o de tarefas e´ um
conjunto de n entradas da matriz tais que na˜o ha´ duas dessas n entradas em uma mesma
linha e nem em uma mesma coluna.
Definic¸a˜o A soma das n entradas de uma alocac¸a˜o e´ chamada de custo da alocac¸a˜o.
Uma alocac¸a˜o com o menor custo poss´ıvel e´ denominada uma alocac¸a˜o o´tima de tare-
fas.
O problema da alocac¸a˜o de tarefas consiste em encontrar uma alocac¸a˜o o´tima a partir
de uma matriz-custo dada.
Teorema (da Alocac¸a˜o O´tima) Se um nu´mero real e´ somado ou subtra´ıdo de todas
as entradas de uma linha ou coluna de uma matriz-custo, enta˜o uma alocac¸a˜o o´tima para
a matriz-custo resultante e´ tambe´m uma alocac¸a˜o de tarefas o´tima para a matriz-custo
original.
Demonstrac¸a˜o
Seja a matriz n× n:
C =

c11 c12 ... c1i ... c1n
c21 c22 ... c2i ... c2n
...
...
...
...
...
...
cj1 cj2 ... cji ... cjn
...
...
...
...
...
...
cn1 cn2 ... cni ... cnn

n×n
.
Suponhamos que as entradas da alocac¸a˜o o´tima da matriz sejam c1k1, c2k2, ..., ciki, ..., cnkn,
sendo os ı´ndices 1k, 2k, ..., nk diferentes dois a dois.
Logo, o custo mı´nimo de alocac¸a˜o e´ a soma de todas as entradas acima, isto e´:
S = c1k1 + c2k2 + ...+ ciki + ...+ cnkn.
Adicionando um valor p ∈ R em todas as entradas de uma coluna da matriz-custo C,
temos a seguinte matriz:
D =

c11 c12 ... c1i + p ... c1n
c21 c22 ... c2i + p ... c2n
...
...
...
...
...
...
cj1 cj2 ... cji + p ... cjn
...
...
...
...
...
...
cn1 cn2 ... cni + p ... cnn

n×n
.
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 29
Utilizando as mesmas entradas da alocac¸a˜o o´tima da matriz C, temos a seguinte soma:
S + p = c1k1 + c2k2 + ...+ (ciki + p) + ...+ cnkn
e temos, mais uma vez, que essas entradas correspondem a uma alocac¸a˜o o´tima. De fato,
qualquer outra sequ¨eˆncia de entradas de D fornece uma soma maior (ou igual) a S + p,
uma vez que, na matriz-custo C a soma mı´nima e´ S e em D esta˜o sendo somados p′s em
todas as entradas de uma coluna.
A demonstrac¸a˜o se processa de modo ana´logo no caso de adicionarmos p ∈ R a todas
as entradas de uma linha de C. ¤
Observemos que se pudermos aplicar o teorema acima em uma matriz-custo n× n de
tal modo a gerar uma matriz-custo que possua todas as entradas na˜o negativas e, mais
ainda, tal que possua n zeros de modo que dois deles na˜o estejam na mesma linha ou
coluna, na˜o teremos dificuldades em achar a alocac¸a˜o o´tima que, na u´ltima matriz, tera´
soma nula. O algoritmo chamado de Me´todo Hu´ngaro para alocac¸a˜o o´tima de tarefas
baseia-se nessa ide´ia.
4 O Me´todo Hu´ngaro
Baseados no teorema da sec¸a˜o anterior, temos o seguinte algoritmo para descobrir uma
alocac¸a˜o o´tima para uma dada matriz-custo n× n:
Algoritmo justificado passo a passo.
(1) Subtraia a menor entrada de cada linha de todas as entradas da mesma linha.
Justificativa:
Pelo Teorema da Alocac¸a˜o O´tima, uma alocac¸a˜o o´tima na matriz-custo resultante e´
alocac¸a˜o o´tima na matriz-custo original. Neste passo, estamos criando em cada linha pelo
menos uma entrada zero e, ale´m disso, todas as outras entradas sa˜o na˜o negativas.
(2) Subtraia a menor entrada de cada coluna de todas as entradas da mesma coluna.
Justificativa:
Pelo teorema acima, uma alocac¸a˜o o´tima na matriz-custo resultante e´ alocac¸a˜o o´tima
na matriz-custo original. Neste passo, estamos criando em cada coluna pelo menos uma
entrada zero e, ale´m disso, todas as outras entradas sa˜o na˜o negativas.
(3) Risque um trac¸o ao longo de linhas e colunas de tal modo que todas as entradas zero
da matriz-custo sejam riscadas e utilizando um nu´mero mı´nimo de trac¸os.
Justificativa:
Pode haver va´rias maneiras de realizar esse procedimento. O que e´ importante e´ usar
o nu´mero mı´nimo de trac¸os que e´, obviamente, menor ou igual a n.
(4) Teste de Otimalidade:
Edson
Edson
30 FAMAT em Revista - Número 04 - Abril de 2005
(4-i) Se o nu´mero mı´nimo de trac¸os necessa´rios para cobrir os zeros e´ n, enta˜o uma
alocac¸a˜o o´tima e´ poss´ıvel e encerramos o procedimento.
Justificativa:
Esta etapa e´ central no algoritmo. Provar a afirmac¸a˜o acima e´ o mesmo que provar
que se n e´ o nu´mero mı´nimo de trac¸os para cobrir todos os zeros da matriz-custo, enta˜o
existem n zeros de tal modo que dois deles na˜o esta˜o em uma mesma linha ou coluna
(ou seja, existe uma alocac¸a˜o o´tima correspondendo a essas entradas nulas). Esse e´ o
“Teorema de Ko¨nig” cuja demonstrac¸a˜o pode ser encontrada em [7]. Por ser necessa´rio
diversos pre´-requisitos de programac¸a˜o linear, iremos omitir sua demonstrac¸a˜o.
(4-ii) Se o nu´mero mı´nimo de trac¸os para cobrir os zeros e´ menor que n continue ate´
o pro´ximo passo.
Justificativa:
Observemos que se o nu´mero mı´nimo de trac¸os para cobrir os zeros e´ menor que n, na˜o
e´ poss´ıvel identificar uma alocac¸a˜o o´tima na matriz-custo obtida. De fato, uma alocac¸a˜o
o´tima em tal matriz sera´ identificada quando existirem n zeros de tal modo que dois deles
na˜o estejam em uma mesma linha ou coluna. Ora, nessas condic¸o˜es, sa˜o necessa´rios no
mı´nimo n trac¸os para cobr´ı-los.
(5) Determine a menor entrada que na˜o tenha sido riscada. Subtraia essa entrada de
todas as entradas na˜o riscadas e a some a todas as entradas riscadas tanto horizontalmente
quanto verticalmente. Retorne ao passo (3).
Justificativa:
Sejam m o nu´mero de linhas e colunas riscadas e a > 0 a menor entrada na˜o riscada.
Pelo teorema acima, podemos somar a a todas as entradas das linhas e colunas riscadas
e subtrair a de todas as entradas. Isso equivale a subtrair a de todas as entradas na˜o
riscadas e somar a a todas as entradas riscadas tanto horizontalmente quanto vertical-
mente. Notemos ainda que a diferenc¸a entre todas as entradas da matriz-custo inicial
desse passo e da matriz-custo final desse passo e´ − [m (na)− n2a] = na (n−m) > 0, pois
n > m. Isso garante que a soma das entradas da matriz-custo final desse passo (que e´
positiva) esta´ decrescendo, ou seja, havera´ uma iterac¸a˜ofinal nesse algoritmo.
E´ importante mencionar que para utilizarmos o Me´todo Hu´ngaro treˆs condic¸o˜es teˆm
que ser satisfeitas:
• O problema tem que ser de minimazac¸a˜o. Para transformar um problema de max-
imizac¸a˜o em um problema de minimizac¸a˜o basta que multipliquemos todas as entradas
da matriz-custo por −1.
• A matriz-custo precisa ser quadrada. Caso isso na˜o acontec¸a, basta criar uma tarefa
ou uma instalac¸a˜o fict´ıcia que na˜o interfira no resultado final.
• E´ aconselha´vel que, ao utilizarmos softwares, as entradas da matriz-custo sejam
nu´meros inteiros, para evitarmos problemas de arredondamento. Em problemas pra´ticos,
caso isso acontec¸a, basta multiplicar as entradas da matriz por uma poteˆncia conveniente
de 10.
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 31
5 Exemplos
Exemplo 1 (o problema e´ de minimizac¸a˜o e a matriz-custo e´ quadrada) Recon-
siderando o exemplo da Sec¸a˜o “Um Problema de Alocac¸a˜o de Tarefas”, temos:
Uma construtora possui treˆs garagens cada qual possui uma escavadeira. As escav-
adeiras devem ser transportadas para treˆs obras distintas e o custo do transporte de cada
escavadeira para cada obra e´ dado pela seguinte matriz-custo:
Obra 1 Obra 2 Obra 3
Escavadeira 1 R$ 900,00 R$ 750,00 R$ 750,00
Escavadeira 2 R$ 350,00 R$ 850,00 R$ 550,00
Escavadeira 3 R$ 1.250,00 R$ 950,00 R$ 900,00
Como devemos alocar as escavadeiras (uma em cada obra) de modo a minimizar o
custo?
Resoluc¸a˜o
Aplicando o Me´todo Hu´ngaro na matriz custo:
Obra 1 Obra 2 Obra 3
Escavadeira 1 900 750 750
Escavadeira 2 350 850 550
Escavadeira 3 1250 950 900
temos:
Passo 1: subtra´ımos 750 das entradas da primeira linha, 350 das entradas da segunda e
900 das entradas da terceira. O resultado e´
Obra 1 Obra 2 Obra 3
Escavadeira 1 150 0 0
Escavadeira 2 0 500 200
Escavadeira 3 350 50 0
Passo 2: subtra´ımos 0 das entradas da primeira coluna, 0 das entradas da segunda e 0
das entradas da terceira. O resultado (neste exemplo) permanece inalterado:
Obra 1 Obra 2 Obra 3
Escavadeira 1 −− 150−− −− 000−− −− 000−−
Escavadeira 2 −− 000−− −− 500−− −− 200−−
Escavadeira 3 −− 350−− −− 050−− −− 000−−
Passos 3 e 4: o nu´mero mı´nimo de trac¸os para cobrir todos os zeros da matriz e´ treˆs.
Logo, existem treˆs zeros, um em cada linha e em cada coluna da matriz, que corresponde
a` alocac¸a˜o o´tima:
Obra 1 Obra 2 Obra 3
Escavadeira 1 150 0 0
Escavadeira 2 0 500 200
Escavadeira 3 350 50 0
Edson
Edson
32 FAMAT em Revista - Número 04 - Abril de 2005
que neste caso e´: Escavadeira 1 na Obra 2; Escavadeira 2 na Obra 1 e Escavadeira 3 na
Obra 3, perfazendo o custo mı´nimo de R$ 2.000, 00.
Exemplo 2 (o problema e´ de maximizac¸a˜o e a matriz-custo na˜o e´ quadrada) Um
negociante de moedas vai vender quatro moedas raras em um leila˜o eletroˆnico. Ele recebe
propostas para cada uma das quatro moedas de cinco interessados, mas estes interessados
tambe´m afirmam que podem honrar no ma´ximo uma das propostas. As propostas sa˜o
dadas pela seguinte tabela:
Moeda 1 Moeda 2 Moeda 3 Moeda 4
Interessado 1 R$ 150, 00 R$ 65, 00 R$ 210, 00 R$ 135, 00
Interessado 2 R$ 175, 00 R$ 75, 00 R$ 230, 00 R$ 155, 00
Interessado 3 R$ 135, 00 R$ 85, 00 R$ 200, 00 R$ 140, 00
Interessado 4 R$ 140, 00 R$ 70, 00 R$ 190, 00 R$ 130, 00
Interessado 5 R$ 170, 00 R$ 50, 00 R$ 200, 00 R$ 160, 00
Como o negociante deveria alocar as quatro moedas para maximizar a soma das pro-
postas correspondentes?
Resoluc¸a˜o
Para utilizar o Me´todo Hu´ngaro, observamos que duas condic¸o˜es na˜o sa˜o satisfeitas:
a “matriz-custo” na˜o e´ quadrada e esse problema e´ de maximizac¸a˜o. Para resolver esses
problemas, criamos uma moeda fict´ıcia (Moeda 5) e uma coluna de “zeros” de modo que
ela na˜o altere o resultado final (observe que quem receber a moeda fict´ıcia na˜o estara´
recebendo nenhuma moeda real) e multiplicamos as entradas da matriz-custo por −1 de
modo que esse se torne um problema de minimizac¸a˜o.
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 −150 −65 −210 −135 0
Interessado 2 −175 −75 −230 −155 0
Interessado 3 −135 −85 −200 −140 0
Interessado 4 −140 −70 −190 −130 0
Interessado 5 −170 −50 −200 −160 0
Agora, podemos aplicar o Me´todo Hu´ngaro:
Passo 1: Subtra´ımos −210 das entradas da primeira linha, −230 da segunda, −200 da
terceira, −190 da quarta e −200 da quinta.
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 60 145 0 75 210
Interessado 2 55 155 0 85 230
Interessado 3 65 115 0 60 200
Interessado 4 50 120 0 60 190
Interessado 5 30 150 0 40 200
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 33
Passo 2: Subtra´ımos 30 das entradas da primeira coluna, 115 da segunda, 0 da terceira,
40 da quarta e 190 da quinta.
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 30 30 00 | 35 20
Interessado 2 25 40 00 | 45 40
Interessado 3 −− 35−− −− 00−− −− 00 | − − −− 20−− −− 10−−
Interessado 4 −− 20−− −− 05−− −− 00 | − − −− 20−− −− 00−−
Interessado 5 −− 00−− −− 35−− −− 00 | − − −− 00−− −− 10−−
Passos 3 e 4: Como o nu´mero mı´nimo de trac¸os em linhas e colunas usados para riscar
todos os zeros da matriz e´ inferior a quatro, enta˜o ainda na˜o e´ poss´ıvel uma alocac¸a˜o
o´tima de zeros.
Passo 5: Subtra´ımos 20 (que e´ a menor entrada na˜o riscada) das entradas na˜o riscadas
e somamos esse valor a`s entradas riscadas por dois trac¸os.
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 10 10 00 | 15 00 |
Interessado 2 05 20 00 | 25 20 |
Interessado 3 −− 35−− −− 00−− −− 20 | − − −− 20−− −− 10 | − −
Interessado 4 20 05 20 | 20 00 |
Interessado 5 −− 00−− −− 35−− −− 20 | − − −− 00−− −− 10 | − −
Passos 3 e 4: Mais uma vez o nu´mero de trac¸os em linhas e colunas usados para riscar
os zeros e´ menor que cinco, por isso ainda na˜o e´ poss´ıvel uma alocac¸a˜o o´timo de zeros.
Passo 5: Subtra´ımos 5 (que e´ a menor entrada na˜o riscada) das entradas na˜o riscadas e
somamos 5 a`s entradas riscadas por dois trac¸os.
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 −− 05−− −− 05−− −− 00−− −− 10−− −− 00−−
Interessado 2 −− 00−− −− 15−− −− 00−− −− 20−− −− 20−−
Interessado 3 −− 35−− −− 00−− −− 25−− −− 20−− −− 15−−
Interessado 4 −− 15−− −− 00−− −− 20−− −− 15−− −− 00−−
Interessado 5 −− 00−− −− 35−− −− 25−− −− 00−− −− 15−−
Passos 3 e 4: Como o nu´mero mı´nimo de trac¸os usados para riscar os zeros e´ cinco,
enta˜o e´ poss´ıvel uma alocac¸a˜o o´tima de zeros dada por:
Moeda 1 Moeda 2 Moeda 3 Moeda 4 Moeda 5
Interessado 1 5 5 0 10 0
Interessado 2 0 15 0 20 20
Interessado 3 35 0 25 20 15
Interessado 4 15 0 20 15 0
Interessado 5 0 35 25 0 15
A alocac¸a˜o o´tima de zeros (que na˜o e´ u´nica) indica que a maior quantia que ele poderia
amealhar seria com a venda da Moeda 1 ao Interessado 2, da Moeda 2 ao Interessado 3, da
Edson
Edson
34 FAMAT em Revista - Número 04 - Abril de 2005
Moeda 3 ao Interessado 1 e da Moeda 4 ao Interessado 5 ao passo que ao Interessado 4 na˜o
seria vendida nenhuma moeda. Isso significaria uma soma de R$ 175, 00+R$ 85, 00+R$
210, 00 +R$ 160, 00 = R$ 630, 00.
Exemplo 3 (o problema e´ de maximizac¸a˜o e a matriz-custo e´ quadrada) Dizem que
o futebol moderno esta´ se tornando cada vez mais te´cnico ou ta´tico. Excetuando-se
o goleiro, um te´cnico de um time de futebol pode mudar a escalac¸a˜o dos outros nove
jogadores titulares em nove posic¸o˜es diferentes. O te´cnico testa os jogadores em cada
posic¸a˜o e classifica-os em uma escala de 0 a 25 para cada uma das posic¸o˜es testadas. O
resultado e´ a tabela seguinte:
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9Posic¸a˜o 1 20 15 10 10 17 23 25 5 15
Posic¸a˜o 2 10 10 12 15 9 7 8 7 8
Posic¸a˜o 3 12 9 9 10 10 5 7 13 9
Posic¸a˜o 4 13 14 10 15 15 5 8 20 10
Posic¸a˜o 5 12 13 10 15 14 5 9 20 10
Posic¸a˜o 6 15 14 15 16 15 5 10 20 10
Posic¸a˜o 7 7 9 12 12 7 6 7 15 12
Posic¸a˜o 8 5 6 8 8 5 4 5 10 7
Posic¸a˜o 9 5 6 8 8 5 4 5 10 7
Como deveria o te´cnico escalar os nove jogadores para maximizar o rendimento em jogo?
Resoluc¸a˜o
Como este e´ um problema de maximizac¸a˜o, devemos multiplicar as entradas da matriz
por −1 para que este se torne um problema de minimizac¸a˜o e possamos utilizar o Me´todo
Hu´ngaro.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 −20 −15 −10 −10 −17 −23 −25 −05 −15
Posic¸a˜o 2 −10 −10 −12 −15 −09 −07 −08 −07 −08
Posic¸a˜o 3 −12 −09 −09 −10 −10 −05 −07 −13 −09
Posic¸a˜o 4 −13 −14 −10 −15 −15 −05 −08 −20 −10
Posic¸a˜o 5 −12 −13 −10 −15 −14 −05 −09 −20 −10
Posic¸a˜o 6 −15 −14 −15 −16 −15 −05 −10 −20 −10
Posic¸a˜o 7 −07 −09 −12 −12 −07 −06 −07 −15 −12
Posic¸a˜o 8 −05 −06 −08 −08 −05 −04 −05 −10 −07
Posic¸a˜o 9 −05 −06 −08 −08 −05 −04 −05 −10 −07
Passo 1: Subtra´ımos −25 de todas as entradas da primeira linha da matriz, −15 da
segunda, −13 da terceira, −20 da quarta, −20 da quinta, −20 da sexta, −15 da se´tima,
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 35
−10 da oitava e −10 da nona. E assim ficamos com a seguinte matriz:
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 05 10 15 15 08 02 00 20 10
Posic¸a˜o 2 05 05 03 00 06 08 07 08 07
Posic¸a˜o 3 01 04 04 03 03 08 06 00 04
Posic¸a˜o 4 07 06 10 05 05 15 12 00 10
Posic¸a˜o 5 08 07 10 05 06 15 11 00 10
Posic¸a˜o 6 05 06 05 04 05 15 10 00 10
Posic¸a˜o 7 08 06 03 03 08 09 08 00 03
Posic¸a˜o 8 05 04 02 02 05 06 05 00 03
Posic¸a˜o 9 05 04 02 02 05 06 05 00 03
Passo 2: Subtra´ımos 1 de todas as entradas da primeira coluna, 4 da segunda, 2 da
terceira, 0 da quarta, 3 da quinta, 2 da sexta, 0 da se´tima, 0 da oitava e 3 da nona.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 04 06 13 15 05 00 00 20 07
Posic¸a˜o 2 04 01 01 00 03 06 07 08 04
Posic¸a˜o 3 00 00 02 03 00 06 06 00 01
Posic¸a˜o 4 06 02 08 05 02 13 12 00 07
Posic¸a˜o 5 07 03 08 05 03 13 11 00 07
Posic¸a˜o 6 04 02 03 04 02 13 10 00 07
Posic¸a˜o 7 07 02 01 03 05 07 08 00 00
Posic¸a˜o 8 04 00 00 02 02 04 05 00 00
Posic¸a˜o 9 04 00 00 02 02 04 05 00 00
Passo 3: Riscamos todos os zeros da matriz com o menor nu´mero de trac¸os poss´ıvel.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 −04− −06− −13− −15− −05− −00− −00− −| 20− −| 07−
Posic¸a˜o 2 −04− −01− −01− −00− −03− −06− −07− −| 08− −| 04−
Posic¸a˜o 3 −00− −00− −02− −03− −00− −06− −06− −| 00− −| 01−
Posic¸a˜o 4 06 02 08 05 02 13 12 | 00 | 07
Posic¸a˜o 5 07 03 08 05 03 13 11 | 00 | 07
Posic¸a˜o 6 04 02 03 04 02 13 10 | 00 | 07
Posic¸a˜o 7 07 02 01 03 05 07 08 | 00 | 00
Posic¸a˜o 8 −04− −00− −00− −02− −02− −04− −05− −| 00− −| 00−
Posic¸a˜o 9 −04− −00− −00− −02− −02− −04− −05− −| 00− −| 00−
Passos 4 e 5: Como o nu´mero de trac¸os em linhas e colunas que cobrem zeros e´ menor
que nove, devemos sutrair 1, que e´ a menor entrada na˜o riscada, de todas as entradas na˜o
riscadas e somar 1 a`s entradas riscadas por dois trac¸os. Em seguida, riscamos todos os
Edson
Edson
36 FAMAT em Revista - Número 04 - Abril de 2005
zeros da matriz com o menor nu´mero de trac¸os poss´ıvel.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 −04− −| 06− −| 13− −15− −05− −00− −00− −| 21− −| 08−
Posic¸a˜o 2 −04− −| 01− −| 01− −00− −03− −06− −07− −| 09− −| 05−
Posic¸a˜o 3 −00− −| 00− −| 02− −03− −00− −06− −06− −| 01− −| 02−
Posic¸a˜o 4 05 | 01 | 07 04 01 12 11 | 00 | 07
Posic¸a˜o 5 06 | 02 | 07 04 02 12 10 | 00 | 07
Posic¸a˜o 6 03 | 01 | 02 03 01 12 09 | 00 | 07
Posic¸a˜o 7 06 | 01 | 00 02 04 06 07 | 00 | 00
Posic¸a˜o 8 04 | 00 | 00 02 02 04 05 | 01 | 01
Posic¸a˜o 9 04 | 00 | 00 02 02 04 05 | 01 | 01
Passos 3, 4 e 5: O nu´mero de trac¸os ainda e´ menor que nove, por isso devemos continuar
o processo: subtra´ımos as entradas na˜o riscadas por 1, somamos 1 a`s entradas riscadas
por dois trac¸os e riscamos os zeros novamente.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Pos.1 −04− −| 07− −| 14− −15− −| 05− −00− −00− −| 22− −| 09−
Pos.2 −04− −| 02− −| 02− −00− −| 03− −06− −07− −| 10− −| 06−
Pos.3 −00− −| 01− −| 03− −03− −| 00− −06− −06− −| 02− −| 03−
Pos.4 04 | 01 | 07 03 | 00 11 10 | 00 | 07
Pos.5 05 | 02 | 07 03 | 01 11 09 | 00 | 07
Pos.6 02 | 01 | 02 02 | 00 11 08 | 00 | 07
Pos.7 05 | 01 | 00 01 | 03 05 06 | 00 | 00
Pos.8 03 | 00 | 00 01 | 01 03 04 | 01 | 01
Pos.9 03 | 00 | 00 01 | 01 03 04 | 01 | 01
Passo 3, 4 e 5: Conseguimos riscar os zeros com oito trac¸os. Assim, continuamos
subtraindo as entradas na˜o riscadas por 1 e somando 1 a`s entradas na˜o riscadas. Depois,
riscamos os zeros.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Pos.1 −| 04− −| 08− −| 15− −| 15− −| 06− −00− −00− −| 23− −| 10−
Pos.2 | 04 | 03 | 03 | 00 | 04 06 07 | 11 | 07
Pos.3 | 00 | 02 | 04 | 03 | 01 06 06 | 03 | 04
Pos.4 | 03 | 01 | 07 | 02 | 00 10 09 | 00 | 07
Pos.5 | 04 | 02 | 07 | 02 | 01 10 08 | 00 | 07
Pos.6 | 01 | 01 | 02 | 01 | 00 10 07 | 00 | 07
Pos.7 | 04 | 01 | 00 | 00 | 03 04 05 | 00 | 00
Pos.8 | 02 | 00 | 00 | 00 | 01 02 03 | 01 | 01
Pos.9 | 02 | 00 | 00 | 00 | 01 02 03 | 01 | 01
Passos 3, 4 e 5: O nu´mero de trac¸os que cobrem os zeros ainda e´ inferior a nove, enta˜o
subtra´ımos 2 das entradas na˜o riscadas e somamos esse valor a`s entradas riscadas por dois
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 37
trac¸os e, em seguida, riscamos os zeros.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 −06− −10− −17− −17− −| 08− −00− −00− −| 25− −12−
Posic¸a˜o 2 −04− −03− −03− −00− −| 04− −04− −05− −| 11− −07−
Posic¸a˜o 3 −00− −02− −04− −03− −| 01− −04− −04− −| 03− −04−
Posic¸a˜o 4 03 01 07 02 | 00 08 07 | 00 07
Posic¸a˜o 5 04 02 07 02 | 01 08 06 | 00 07
Posic¸a˜o 6 01 01 02 01 | 00 08 05 | 00 07
Posic¸a˜o 7 −04− −01− −00− −00− −| 03− −02− −03− −| 00− −00−
Posic¸a˜o 8 −02− −00− −00− −00− −| 01− −00− −01− −| 01− −01−
Posic¸a˜o 9 −02− −00− −00− −00− −| 01− −00− −01− −| 01− −01−
Passo 3, 4 e 5: O nu´mero de trac¸os que cobrem os zeros ainda e´ inferior a nove, enta˜o
subtra´ımos 1 das entradas na˜o riscadas e somamos esse valor a`s entradas riscadas por dois
trac¸os e, em seguida, riscamos os zeros.
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 −06− −10− −17− −17− −09− −00− −00− −26− −12−
Posic¸a˜o 2 −04− −03− −03− −00− −05− −04− −05− −12− −07−
Posic¸a˜o 3 −00− −02− −04− −03− −02− −04− −04− −04− −04−
Posic¸a˜o 4 −02− −01− −06− −01− −00− −07− −06− −00− −06−
Posic¸a˜o 5 −03− −01− −06− −01− −01− −07− −05− −00− −06−
Posic¸a˜o 6 −00− −00− −01− −00− −00− −07− −04− −00− −06−
Posic¸a˜o 7 −04− −01− −00− −00− −04− −02− −03− −01− −00−
Posic¸a˜o 8 −02− −00− −00− −00− −02− −00− −01− −02− −01−
Posic¸a˜o 9 −02− −00− −00− −00− −02− −00− −01− −02− −01−
Passos 3 e 4: Agora, o nu´mero mı´nimo de trac¸os utilizados para riscar todos os zeros
da matriz e´ nove e, pelo Me´todo Hu´ngaro, e´ poss´ıvel uma alocac¸a˜o o´tima de zeros (na˜o
u´nica) dada abaixo:
Jog.1 Jog.2 Jog.3 Jog.4 Jog.5 Jog.6 Jog.7 Jog.8 Jog.9
Posic¸a˜o 1 6 10 17 17 9 0 0 26 12
Posic¸a˜o 2 4 3 3 0 5 4 5 12 7
Posic¸a˜o 3 0 2 4 3 2 4 4 4 4
Posic¸a˜o 4 2 1 6 1 0 7 6 0 6
Posic¸a˜o 5 3 1 6 1 1 7 5 0 6
Posic¸a˜o 6 0 0 1 0 0 7 4 0 6
Posic¸a˜o 7 4 1 0 0 4 2 3 1 0
Posic¸a˜o 8 2 0 0 0 2 0 1 2 1
Posic¸a˜o 9 2 0 0 0 2 0 1 2 1
Conclusa˜o: Nesse caso, o treinador deve escalar o jogador 1 na posic¸a˜o 3, o jogador
2 na 6, o jogador 3 na 8, o jogador 4 na 2, ojogador 5 na 4, o jogador 6 na 9, o jogador
7 na 1, o jogador 8 na 5 e o jogador 9 na 7. Escalando o time desse jeito o te´cnico tera´ o
melhor rendimento do time.
Edson
Edson
38 FAMAT em Revista - Número 04 - Abril de 2005
Refereˆncias
[1] Anton, H & Rorres, C. A´lgebra Linear com Aplicac¸o˜es. 8a. ed. Porto Alegre:
Editora Bookman, 2001.
[2] Bertsimas, D. & Tsitsiklis, J. N. Introduction to Linear Optimization. Belmont-
Massachussets: Athena Scientific, 1997.
[3] Bodrini, J. L.; Costa, S. I. R.; Figueiredo, V. L. & Wetzler, H. G. A´lgebra
Linear. 3a. ed. Sa˜o Paulo: Editora Harbra, 1980.
[4] Egervary, E. “On Combinatorial Properties of Matrices”. In: Matematikae´s Fizikai
Lapok, vol. 38, 1931; translated as “On Combinatorial Properties of Matrices” by H. W.
Kuhn, Office of Naval Research Logistics Project Report, Department of Mathematics,
Princeton University, Princeton, NJ, 1953.
[5] Gass, S. I. Linear Programming: methods and applications. 5th. ed. New York: Mc
Graw-Hill, 1985.
[6] Hadley, G. Programac¸a˜o Linear. Rio de Janeiro: Editora Guanabara Dois, 1982.
[7] Kuhn, H. W. “The Hungarian Method for the Assignment Problem”. In: Naval
Research Logistics Quarterly, vol. 2, n. 1 e 2, 1955, pp. 83-97.
[8] Lipschutz S. A´lgebra Linear. 3a. ed. (Colec¸a˜o Schaum). Sa˜o Paulo: Editora Makron
Books, 1994.
[9] Prado, D. Programac¸a˜o Linear. 3a. ed. Belo Horizonte: Editora DG, 2003.
Edson
Edson
FAMAT em Revista - Número 04 - Abril de 2005 39