AlgoritmoTransportes

Prévia do material em texto

1. Formular o problema através de um quadro de transportes. As linhas correspondem 
a origens e as colunas correspondem a destinos. 
a. Colocar a capacidade de produção de cada origem à direita da linha 
respectiva. Colocar o consumo em cada destino por baixo da coluna 
respectiva. O somatório de cada linha e de cada coluna representam as 
restrições do problema. 
b. Se a oferta for superior à procura, inserir um destino (coluna) artificial 
para representar a folga. Se a procura for superior à oferta, inserir uma 
origem (linha) artificial para representar o excesso de procura. A soma 
da coluna/linha representa o excesso/folga. 
c. Colocar o custo de transporte cij no canto superior direito de cada 
célula. O custo de transporte para as células da coluna/linha artificial é 
nulo porque essas células não têm qualquer influência sobre o valor da 
função-objectivo. 
2. Identificar uma solução básica admissível inicial (S.B.A.I.), por exemplo, utilizando 
o método do custo mínimo: 
a. Identificar a célula com o menor custo de transporte. 
b. Colocar no canto inferior esquerdo dessa célula o maior valor possível 
permitido pelas restrições. Ambas as restrições têm de ser obedecidas. 
c. Se a procura estiver totalmente satisfeita, cortar a coluna. Corrigir o 
valor da soma da linha respectiva (colocado na coluna mais à direita). 
d. Identificar a célula seguinte com o menor custo de transporte. Voltar à 
alínea b. 
Algoritmo de Transportes – passos elementares 
e. Parar quando toda a procura estiver satisfeita e tiverem sido 
preenchidas tantas células quanto o número de variáveis básicas. O 
número de variáveis básicas è igual a C+L-1; onde C é o número de 
colunas e L o número de linhas. 
3. Verificar se a solução encontrada é óptima. Esta tarefa faz uso do método dos us e 
dos vs, baseada na teoria da dualidade. A cada linha i é atribuído um valor ui e a 
cada coluna j é atribuído um valor vj. 
a. Fazer u1 = 0. 
b. Calcular os outros us e vs tendo em conta que a igualdade cij = ui + vj é 
válida para todas as variáveis básicas. 
c. Calcular o custo reduzido čij para todas as variáveis não-básicas (čij = ui 
+ vj – cij). Colocar esse valor no canto inferior direito da célula 
respectiva. 
d. A solução óptima de um problema de minimização não tem nenhum 
custo reduzido positivo. Num problema de maximização, a solução 
óptima não tem nenhum custo reduzido negativo. 
e. Se a solução encontrada não for óptima, escolher como variável para 
entrar na base aquela com o maior coeficiente positivo (minimização) 
ou negativo (maximização). 
4. Escolher uma variável para sair da base, através do método do θ: 
a. Colocar o valor θ no canto superior esquerdo da célula associada à 
variável de entrada. 
b. Criar um circuito fechado que começa e acaba na nova variável de 
entrada, em que todos os cantos caem sobre variáveis básicas. Só é 
permitido realizar movimentos horizontais e verticais. 
c. Alternadamente subtrair e somar θ ao valor de cada uma das variáveis 
básicas nos cantos do circuito fechado. Colocar esse valor no canto 
superior esquerdo da célula respectiva. Recordar que θ é inicialmente 
somado à variável de entrada. 
d. Determinar o valor máximo de θ, sabendo que nenhuma variável pode 
assumir valores negativos. A variável que primeiro limita o crescimento 
de θ é a variável de saída. 
5. Calcular um novo quadro em que θ assume o valor máximo calculado na alínea 
anterior. Voltar ao ponto 3.