Lista de Exercicios - Pesquisa Operacional (44)

Prévia do material em texto

Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 88
 
Solução inicial pelo método de Vogel. P1 P2 P3 
 20 0 10 170 10 – – 
 20 0 10 150 10 10 10 
 20 0 10 200 10 10 10 
200 200 120 
P1 0 0 0 
P2 0 0 0 
P3 0 0 0 
 
Penalidade P1: transportar na linha 1 (maior penalidade) e coluna 2 (menor custo). X12 = 170. 
Linha 1 eliminada. 
Penalidade P2: transportar na linha 2 (maior penalidade) e coluna 2 (menor custo). X22 = 150. 
Coluna 2 eliminada. 
Penalidade P3: transportar na linha 3 (maior penalidade) e coluna 3 (menor custo). X33 = 120 
Quadro da solução inicial. 
 170 170/0 
120 30 150/120 
 80 120 200/80 
200 200/30/0 120/0 
Cálculo da solução ótima. Coeficientes das variáveis básicas. 
X12: 0 – U1 – V2 = 0 X21: 20 – U2 – V1=0 X22: 0 – U2 – V2 = 0 
X31: 20 – U3 – V1 = 0 X33: 10 – U3 – V3 = 0 
Fazendo U1 = 0, vem: U2 = 0 U3 = 0 V1 = 20 V2 = 0 V3 = 10 
Coeficiente das variáveis não básicas. 
X11: 20 – 0 – 20 = 0 X13: 10 – 0 – 10 = 0 X23: 10 – 0 – 10 = 0 x32: 0 – 0 – 0 = 0 
A solução é ótima. Os coeficientes das variáveis não básicas (todos nulos) indicam que existem 
outras soluções ótimas. 
Receita = 200 x 500 + 200 x 520 + 120 x 510 = 265.200 
 
 
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 89
Pesquisa Operacional Quarta Edição 
 Medeiros, Medeiros, Gonçalves, Murolo 
Exercícios propostos – Lista 6 Ex 14 
Cada lixeiro faz 5 viagens até os coletores, no total de 30 viagens. Para que os coletores se 
enchamde maneira uniforme, cada coletor deve receber 10 viagens. O quadro será, então: 
200 300 500 400 250 300 10 
100 150 200 300 150 180 10 
120 200 50 180 220 100 10 
5 5 5 5 5 5 
Solução inicial pelo método de Vogel. P1 P2 P3 P4 
200 300 500 400 250 300 10 50 50 50 50 
100 150 200 300 150 180 10 50 50 50 50 
120 200 50 180 220 100 10 50 20 20 20 
5 5 5 5 5 5 
P1 20 50 150 120 70 80 
P2 20 50 – 120 70 80 
P3 100 150 – – 100 120 
P4 100 – – – 100 120 
 
Penalidade P1: transportar na coluna 3 (maior penalidade) e linha 3 (menor custo). X33 = 5. 
Coluna 3 eliminada. 
Penalidade P2: transportar na coluna 4 (maior penalidade) e linha 3 (menor custo). X34 = 5. 
Coluna 4 e linha 3 eliminadas. 
Penalidade P3: transportar na coluna 2 (maior penalidade) e linha 2 (menor custo). X22 = 5. 
Coluna 2 eliminada. 
Penalidade P4: transportar na coluna 6 (maior penalidade) e linha 2 (menor custo). X26 = 5. 
Coluna 6 e linha 2 eliminadas. 
Quadro da solução inicial 
5 5 10 
A 5 5 10/5/0 
 5 5 A 10/5/0 
5 5/0 5/0 5/0 5 5/0 
Cálculo da solução ótima. Coeficientes das variáveis básicas. 
O sistema apresenta 6 equações e 9 variáveis. Devemos adicionar duas variáveis auxiliares de 
maneira que não formem circuitos com as variáveis básicas existentes. Escolhemos A21 e A36 
X11: 200 – U1 – V1 = 0 X15: 250 – U1 – V5 = 0 X22: 150 – U2 – V2 = 0 
X26: 180 – U2 – V6 = 0 X33: 50 – U3 – V3 = 0 X34: 180 – U3 – V4 = 0 
X21: 100 – U2 – V1 = 0 X36: 100 – U3 – V6 = 0. 
Fazendo U1 = 0, vem: U2 = – 100 U3 = – 180 V1 = 200 V2 = 250 V3 = 230 
V4 = 360 V5 = 250 V6 = 280 
Coeficientes das variáveis não básicas. 
Exercícios Propostos – Lista 6
Exercício 14