Verificando a otimalidade
O teste de otimalidade pode ser realizado se duas condições forem satisfeitas,
1. Existem m + n - 1 alocações, cujo m é o número de linhas, n é o número de colunas. Aqui m + n - 1 = 6. Mas o número de alocação é cinco.
2. Essas alocações m + n-1 devem estar em posições independentes. Isto é, não deve ser possível aumentar ou diminuir qualquer alocação sem alterar a posição das alocações ou violar as restrições de filas ou colunas.
Uma regra simples para alocações em posições independentes é que é impossível viajar de qualquer alocação, retornando a si mesmo por uma série de etapas horizontais e verticais de uma célula ocupada para outra, sem uma reversão direta da rota. Pode ver-se que, no presente exemplo, a atribuição está em posições independentes, uma vez que não pode ser formado um ciclo fechado nas células alocadas.
Portanto, a primeira condição não é satisfeita e, portanto, a fim de satisfazer a primeira condição, teremos que alocar uma pequena quantidade E nas células vazias com o menor custo de transporte. Pode ser visto que t pode ser alocado na célula (2, 2) com custo de 7 unidades e ainda assim as alocações permanecerão na posição independente conforme descrito abaixo:
Agora o número de alocação é m + n- = 6 e eles estão em posições independentes.
Anote a matriz de custo nas células alocadas.
Matriz de custo inicial para células alocadas.
Escreva também os valores de ui e vj como explicado anteriormente.
Matriz de avaliação celular
Pode ser visto a partir da tabela 5 que a avaliação celular na célula (1, 4) é negativa, isto é, -4, portanto, alocando ao custo de transporte da célula (1, 4), ser ainda mais reduzida. Vamos anotar as alocações originais e a nova alocação proposta.
Pode ser visto na tabela 6 que se alocarmos na célula (1, 4) um loop é formado como mostrado e alocamos 10 unidades de modo que a alocação na célula (2, 4) se desvanece como mostrado abaixo na tabela 7.
Nova tabela de alocação se tornará
Custo de transporte = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 unidades. Ou seja, o custo de transporte desceu de 475 unidades para 435 unidades.
Verifique a Optimaiity:
Vamos ver se esta solução é ótima! ou não? Para isso, duas condições devem ser verificadas
Nº de alocação = m + n - 1 = 6 (satisfeito)
Alocação na posição independente (satisfeita desde que o laço fechado para as células alocadas não é formado)
Escreva o custo nos alocados alls e valores de ui e v j
Exemplo 2:
(Oferta e Demanda Desequilibrada). Resolva o seguinte problema de transporte
Oferta total = 200 unidades, demanda = 185 unidades.
Solução:
Como a oferta e a demanda não são iguais, o problema é desequilibrado. Para equilibrar o problema, uma colméia fictícia deve ser adicionada como mostrado abaixo. A demanda dessa colunata fictícia (loja) será de 15 unidades.
Solução Básica Viabilizável:
Usaremos o método de aproximação de Vogel para encontrar a solução inicial viável.
A solução inicial viável é dada pela seguinte matriz:
Teste de otimalidade:
Da matriz acima, descobrimos que:
(a) Número de alocações = m + n - 1 = 4 + 5-1 = 8
(b) Essas alocações m + n - 1 estão em posições independentes.
Portanto, teste de otimalidade pode ser realizado. Isso consiste nas sub-etapas explicadas anteriormente, conforme mostrado nas tabelas abaixo:
Como os valores das células são + ve, a primeira solução viável é a ideal. Como a tabela 6 contém entradas zero, existem soluções ótimas alternativas. O significado prático da demanda ser 15 unidades a menos que a oferta é que a empresa pode reduzir a produção de 15 unidades na fábrica, onde não é econômico.
O melhor transporte (mínimo) mais o custo de produção.
Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 +10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)
= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1, 465.
Exemplo 3:
Resolva o problema de transporte a seguir para maximizar o lucro. Devido à diferença no custo da matéria-prima e no custo de transporte, o lucro por unidade em rupias difere do que é dado na tabela abaixo:
Resolva o problema para maximizar o lucro.
Solução:
Problema é desequilibrado e, portanto, uma linha fictícia deve ser adicionada para torná-lo equilibrado.
Encontre a solução básica inicial viável:
Usaremos o método de aproximação de vogel para determinar a solução inicial viável.
Note que estamos lidando com o problema de maximização. Assim, devemos inserir a diferença entre os elementos mais alto e segundo maior em cada linha à direita da linha e a diferença entre o maior e o segundo maior elemento em cada coluna abaixo da coluna correspondente.
Cada uma dessas diferenças representa o lucro unitário perdido por não alocar na célula de lucro mais alta. Assim, ao fazer alocações, primeiro selecionamos a célula (2, 3) com a entrada mais alta na linha 2, o que corresponde à maior diferença de [45].
Teste de otimalidade:
Número necessário de alocações = m + n - 1 = 3 + 4 - 1 = 6
Número real de alocação = 5.
Por isso, alocamos o número positivo pequeno de € a célula (1, 3) (célula com lucro máximo de células vazias), de modo que o número de alocações se torne 6. Essas 6 alocações estão em posições independentes. Portanto, teste de otimalidade pode ser realizado.
Como todos os valores das células são negativos ou zero (problema de maximização), a solução básica viável inicial é ótima. A demanda no primeiro destino é 'deixada insatisfeita por 5 unidades. O lucro é
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31.600.
