R Noroeste e Custo min

Regra do Noroeste para problemas de transporte 09/11/2013 Profa. Maria Isabel
Passo 0
Sejam i = 1 e j = 1

Passo 1
Seja xij = min { ai, bj },
Faça ai = ai - xij e bj = bj - xij

Passo 2
Se ai ≠ 0 então faça j = j + 1
Se ai = 0 e bj ≠ 0, então faça i= i + 1,
Se ai = 0 e bj = 0, então faça i = i+ 1 e J= J + 1
Se i= m + 1 e j = n + 1 → Fim
Caso contrário vá para o passo 1

Processo do Custo Mínimo para problemas de transporte

Passo 0
Sejam I = {1,...,m} e j = {1,...,n}

Passo 1
Determine
(k, l) = tal que ck,l = min { cij, i ϵ I e j ϵ J } e ak ≠ 0 e bl ≠ 0

Passo 2
Calcule
xk,l = min {ak, bl}

Passo 3
Atualize ak e bl Ak = ak – xkl e bl = bl - xkl

Passo 4 Se ak = 0 então I = I - {k} Se bl = 0 então J = J - {l} Se I ≠ 0 e J ≠ 0 vá para o passo 1 Caso contrário Fim

Exercícios
1) Dar uma solução pela Regra do Noroeste e Processo do Custo Mínimo para os problemas de transporte. Calcule o custo de cada solução:
a) Tabela de custos das origens para os destinos d1 d2 d3 oferta O1
2
5
3
25
O2
7
4
1
25
demanda
15
15
20

b) Tabela de custos das origens para os destinos; d1 d2 d3 d4 oferta
O1
5
6
2
4
35
O2
3
6
8
2
42
O3
4
1
9
10
23 demanda 20
10
40
30

3) Uma empresa tem fábricas em Americana, Campinas e Jundiaí que produzem peças para três montadoras A, B e C ( localizadas no ABC Paulista). Os custos de transporte unitário das fábricas até as montadoras, a oferta e demanda são:
A B C D oferta
I 17 20 13 12 80
II 15 21 26 25 90
III 15 14 15 17 120
Demanda 60 60 70 100 Pede-se:
a) Formule o modelo de programação matemática para o problema.
b) Encontre uma solução pela Regra do Noroeste e seu custo.
c) Encontre uma solução pelo processo do Custo Mínimo e seu custo.
d) Encontre uma solução através do Solver do Excel e seu custo.

4) Construir a árvore binária e dar a solução ótima dos problemas abaixo através do Método de Branch and Bound:
a) Max L = 2 x1 + x2 sc x1 + x2 ≤ 5