Métodos de transporte e critérios de otimalidade
Classificado em Computação
Escrito em em 
português com um tamanho de 3,76 KB.
Métodos de transporte
Fazer a tabela e descobrir se está balanceada, se não, deve criar uma variável auxiliar (A) e colocar no valor final o que falta para balancear.
Na solução básica inicial deve calcular os valores para atingir o máximo e mínimo sem criar circuito.
3 métodos para a construção da solução inicial:
Método do canto noroeste; Método de Vogel ou método das penalidades; Método de custo mínimo
Método do canto noroeste
A partir da cela superior esquerda transportamos o máximo possível da origem ao destino correspondente. Esse procedimento zera a disponibilidade da linha ou da coluna da cela. O próximo transporte será feito na cela contígua (à direita ou abaixo) que tenha disponibilidade de linha e coluna correspondente.
Método de Vogel ou método das penalidades
A ideia desse método é fazer o transporte com prioridade na linha ou coluna que apresenta a maior penalidade. Como o transporte é feito na célula de menor custo, tenta-se evitar com isso o transporte na célula de custo maior, evitando-se assim incorrer num aumento de custo igual à penalidade calculada.
Passos:
1. Calcular a penalidade para cada linha e coluna. Escolher a linha ou coluna para transporte, que tenha a maior penalidade. Caso haja empate, escolha arbitrariamente uma delas.
2. Transportar o máximo possível na linha ou coluna escolhida, elegendo a célula de menor custo unitário de transporte. Esse procedimento zera a oferta ou demanda da célula correspondente. A linha ou coluna que tenha sua disponibilidade zerada deve ser eliminada.
3. Retornar ao passo 1, até que todos os transportes tenham sido realizados.
Método de custo mínimo
1. Atribuir o máximo possível à variável com menor custo unitário e preenche com zeros a linha ou coluna satisfeita.
2. Ajustar os elementos da linha ou coluna não ajustada a partir da variável com menor custo.
3. O processo é repetido para as variáveis com outros custos, em ordem crescente, até preencher toda a tabela.
Critério de Otimalidade
Aqui vamos testar a solução básica para saber se é uma solução ótima. Vamos realizar os cálculos utilizando a solução básica inicial obtida pelo método de custo mínimo no exemplo anterior.
Cada célula com valor zero representa uma variável não básica que poderia entrar na base.
Para cada variável zerada, devemos determinar um caminho fechado de forma a calcular a sua contribuição na função objetivo. Estes caminhos são definidos por linhas verticais ou horizontais, delimitando um polígono fechado. Apenas em um vértice deste polígono deve haver uma variável zerada, que é a própria variável não básica que será incluída na base. Só é possível formar um único caminho com essas características para cada variável zerada.
Encontrado o caminho mínimo da variável, sua contribuição é calculada alternando soma (+) e subtração (-) dos custos unitários dos vértices, começando da variável a ser incluída na base (não-básica).
Vamos agora calcular a contribuição de cada variável não básica na função objetivo. Para não confundir, vamos gerar o circuito para cada variável não básica em tabelas diferentes.
Cálculo dos custos:
(variável x11) Roteiro 1: 8 – 6 + 12 – 15 = -1
(variável x22) Roteiro 2: 10 – 5 + 6 – 12 = -1
(variável x32) Roteiro 3: 9 – 3 + 15 – 12 + 6 – 5 = 10
(variável x33) Roteiro 4: 10 – 12 + 15 – 3 = 10