Problema de Atribuição em Programação Linear: Introdução e Modelo de Atribuição

Problema de atribuição é um tipo especial de problema de programação linear que lida com a alocação dos vários recursos para as várias atividades numa base de um para um. Ele o faz de tal forma que o custo ou o tempo envolvido no processo é mínimo e o lucro ou a venda é o máximo. Embora haja problemas que podem ser resolvidos pelo método simplex ou pelo método de transporte, o modelo de atribuição oferece uma abordagem mais simples para esses problemas.

Em uma fábrica, um supervisor pode ter seis funcionários disponíveis e seis empregos para serem acionados. Ele terá que decidir qual trabalho deve ser dado a qual trabalhador. Problema forma uma a uma base. Este é um problema de atribuição.

1. Modelo de Atribuição:

Suponha que há n facilita e n empregos, é claro que, neste caso, haverá n atribuições. Cada instalação ou trabalhador diz pode executar cada trabalho, um de cada vez. Mas deve haver determinado procedimento pelo qual a atribuição deve ser feita para que o lucro seja maximizado ou o custo ou o tempo seja minimizado.

Na tabela, Co _ij é definido como o custo quando o trabalho é atribuído ao trabalhador. Talvez seja notado aqui que esse é um caso especial de problema de transporte quando o número de linhas é igual ao número de colunas.

Formulação Matemática:

Qualquer solução viável básica de um problema de Atribuição consiste em variáveis ​​(2n - 1) das quais as variáveis ​​(n - 1) são zero, n é o número de tarefas ou número de instalações. Devido a esta alta degenerescência, se resolvermos o problema pelo método de transporte habitual, será um trabalho complexo e demorado. Assim, uma técnica separada é derivada para isso. Antes de ir para o método absoluto, é muito importante formular o problema.

Suponha que _xjj seja uma variável definida como

1 se o primeiro trabalho for atribuído à sua máquina ou instalação

0 se o i- ^ésimo trabalho não estiver atribuído à sua máquina ou instalação.

Agora, como o problema se forma, uma a uma base ou um trabalho deve ser atribuído a uma instalação ou máquina.

O custo total de atribuição será dado por

A definição acima pode ser desenvolvida em modelo matemático como segue:

Determine x _ij > 0 (i, j = 1, 2, 3… n) para

Sujeito a restrições

e x _ij é zero ou um.

Método para resolver o problema (técnica húngara):

Considere a função objetiva do tipo de minimização. As seguintes etapas estão envolvidas na solução deste problema de atribuição,

1. Localize a menor classe de custo em cada linha da tabela de custos fornecida, começando pela primeira linha. Agora, esse menor elemento é subtraído de cada elemento dessa linha. Então, estaremos recebendo pelo menos um zero em cada linha desta nova tabela.

2. Tendo construído a mesa (como no passo 1), pegue as colunas da mesa. Começando da primeira coluna, localize o menor elemento de custo em cada coluna. Agora subtraia esse menor elemento de cada elemento dessa coluna. Tendo realizado o passo 1 e o passo 2, estaremos recebendo pelo menos um zero em cada coluna na tabela de custo reduzido.

3. Agora, as atribuições são feitas para a tabela reduzida da seguinte maneira.

(i) As linhas são examinadas sucessivamente, até que a linha com exatamente um (um) zero seja encontrada. A atribuição é feita para este único zero colocando o quadrado □ ao redor dele e, na coluna correspondente, todos os outros zeros são riscados (x), porque eles não serão usados ​​para fazer nenhuma outra atribuição nesta coluna. A etapa é conduzida para cada linha.

(ii) Etapa 3 (i) agora executada nas colunas como segue: - as colunas são examinadas sucessivamente até que uma coluna com exatamente um zero seja encontrada. Agora, a atribuição é feita para este único zero colocando o quadrado em torno dele e, ao mesmo tempo, todos os outros zeros nas linhas correspondentes são riscados (x) o passo é conduzido para cada coluna.

(iii) Os passos 3, (i) e 3 (ii) são repetidos até que todos os zeros sejam marcados ou riscados. Agora, se o número de zeros marcados ou as atribuições feitas forem iguais ao número de linhas ou colunas, a solução ideal foi alcançada. Haverá exatamente uma única atribuição em cada coluna ou sem qualquer atribuição. Neste caso, iremos para o passo 4.

4. Nesta fase, desenhe o número mínimo de linhas (horizontal e vertical) necessárias para cobrir todos os zeros na matriz obtida no passo 3. O procedimento a seguir é adotado:

(i) marca de escala (

(ii) agora marca de escala (

(iii) Agora marque todas as linhas que ainda não estão marcadas e que tenham atribuição nas colunas marcadas.

(iv) Todas as etapas, ou seja, (4 (i), 4 (ii), 4 (iii) são repetidas até que mais linhas ou colunas não possam ser marcadas.

(v) Agora desenhe linhas retas que passam por todas as linhas não marcadas e colunas marcadas. Também pode ser notado que em uma matriz nxn, sempre menos de 'n' linhas cobrirão todos os zeros se não houver solução entre eles.

5. No passo 4, se o número de linhas desenhadas for igual a n ou o número de linhas, então é a solução ideal se não, então vá para o passo 6.

6. Selecione o menor elemento entre todos os elementos descobertos. Agora, esse elemento é subtraído de todos os elementos descobertos e adicionado ao elemento que fica na interseção de duas linhas. Esta é a matriz para novas atribuições.

7. Repita o procedimento a partir do passo (3) até que o número de atribuições seja igual ao número de linhas ou número de colunas.