Algoritmo da Designação
Passo 1: Subtrair o elemento mínimo de cada linha (coluna) de todos os elementos daquela linha (coluna).
Passo 2: Examinar as linhas e colunas sucessivamente. Para cada linha (coluna) com exatamente um zero
restante, reserve aquela posição para uma designação, e elimine os outros da coluna (linha) correspondente.
Repetir, se necessário, para as linhas e colunas sem posições reservadas até que todos os zeros tenham sido
reservados ou eliminados. Se as posições reservadas completam a designações a solução é ótima. Caso
contrário, seguir para o Passo 3.
Passo 3: Traçar um número mínimo de retas para cobri todos os zeros:
i) Marcar todas as linhas que não tenham designações
ii) Marcar todas as colunas que tenham zeros em linhas marcadas
iii) Marcar todas as linhas que tenham designações em colunas marcadas
iv) Repetir os passos ii) e iii) até não ser mais possível marcar linhas ou colunas
v) Traçar uma reta sobre cada linha não marcada e sobre cada coluna marcada
Passo 4: Examinar todos os elementos não cobertos pr uma reta ?Escolher o elemento mínimo desses
elementos e subtraí-lo de todos os elementos nõ cobertos por uma reta. Somar esse elemento mínimo a cada
elemento situado na interseção de duas retas. Retornar ao Passo 2.
Algoritmo da Designação
Passo 1: Subtrair o elemento mínimo de cada linha (coluna) de todos os elementos daquela linha (coluna).
Passo 2: Examinar as linhas e colunas sucessivamente. Para cada linha (coluna) com exatamente um zero
restante, reserve aquela posição para uma designação, e elimine os outros da coluna (linha) correspondente.
Repetir, se necessário, para as linhas e colunas sem posições reservadas até que todos os zeros tenham sido
reservados ou eliminados. Se as posições reservadas completam a designações a solução é ótima. Caso
contrário, seguir para o Passo 3.
Passo 3: Traçar um número mínimo de retas para cobri todos os zeros:
i)
Marcar todas as linhas que não tenham designações
ii)
Marcar todas as colunas que tenham zeros em linhas marcadas
iii)
Marcar todas as linhas que tenham designações em colunas marcadas
iv)
Repetir os passos ii) e iii) até não ser mais possível marcar linhas ou colunas
v)
Traçar uma reta sobre cada linha não marcada e sobre cada coluna marcada
Passo 4: Examinar todos os elementos não cobertos pr uma reta ?Escolher o elemento mínimo desses
elementos e subtraí-lo de todos os elementos nõ cobertos por uma reta. Somar esse elemento mínimo a cada
elemento situado na interseção de duas retas. Retornar ao Passo 2.
Algoritmo da Designação
Passo 1: Subtrair o elemento mínimo de cada linha (coluna) de todos os elementos daquela linha (coluna).
Passo 2: Examinar as linhas e colunas sucessivamente. Para cada linha (coluna) com exatamente um zero
restante, reserve aquela posição para uma designação, e elimine os outros da coluna (linha) correspondente.
Repetir, se necessário, para as linhas e colunas sem posições reservadas até que todos os zeros tenham sido
reservados ou eliminados. Se as posições reservadas completam a designações a solução é ótima. Caso
contrário, seguir para o Passo 3.
Passo 3: Traçar um número mínimo de retas para cobri todos os zeros:
i)
Marcar todas as linhas que não tenham designações
ii)
Marcar todas as colunas que tenham zeros em linhas marcadas
iii)
Marcar todas as linhas que tenham designações em colunas marcadas
iv)
Repetir os passos ii) e iii) até não ser mais possível marcar linhas ou colunas
v)
Traçar uma reta sobre cada linha não marcada e sobre cada coluna marcada
Passo 4: Examinar todos os elementos não cobertos pr uma reta ?Escolher o elemento mínimo desses
elementos e subtraí-lo de todos os elementos nõ cobertos por uma reta. Somar esse elemento mínimo a cada
elemento situado na interseção de duas retas. Retornar ao Passo 2.