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.