www.EditoraAtlas.com.br
Além de ser um livro-texto ajustado às necessidades de ensino, auxilia o professor a direcionar o estudo
da disciplina, liberando-o de transcrever a matéria no quadro, pois essa atividade é uma fonte de pro-
pagação de erros e pouco traz de retorno ao aluno em termos de entendimento e fi xação de conhecimentos.
A Programação Linear e a Simulação são enfocadas. A Programação Linear tem o mérito de envolver conhe-
cimentos matemáticos relativamente simples e de larga aplicação no campo da administração. Além disso,
sua técnica resolutiva é programável em computador, havendo no mercado softwares específi cos para isso.
A Simulação é o modelo mais geral em Pesquisa Operacional. Seu estudo estimula o conhecimento do sis-
tema envolvido e da metodologia da Pesquisa Operacional. Sua técnica resolutiva envolve conhecimentos
simples de Estatística Básica no nível apresentado, sendo também facilmente programável em computador.
Algumas planilhas (Lotus e Excel, por exemplo) são de grande auxílio e podem ser facilmente encontradas.
Aplicação
Livro-texto para a disciplina Pesquisa Operacional dos cursos de Administração de Empresas e Engenharia
de Produção.
Os autores acumulam larga experiência
no ensino de Matemática, Estatística e
Pesquisa Operacional em cursos superio-
res de Economia, Administração e Ciên-
cias Contábeis.
Ermes Medeiros da Silva é licencia-
do em Matemática pela Faculdade de Fi-
losofi a, Ciências e Letras de Rio Claro-SP.
Elio Medeiros da Silva é bacharel e
licenciado em Matemática pela PUC-SP e
pós-graduado em Matemática Aplicada
pela USP e em Administração de Empre-
sas pela EAESP-FGV.
Valter Gonçalves é graduado em
Ciên cias Econômicas e Administração de
Empresas, pós-graduado em Engenharia
de Produção e Didática do Ensino Superior.
Afrânio Carlos Murolo é graduado
em Matemática, com especialização em
Estatística pela Unicamp, pós-graduado
em Administração de Empresas, Didática
do Ensino Superior e mestre em Engenha-
ria de Produção.
Outros livros dos autorespublicados pela Atlas
• Cálculo básico para cursos superiores
• Estatística: para os cursos de Economia, Administração e Ciências Contábeis (2 volumes)
• Matemática: para os cursos de Economia, Administração e Ciências Contábeis (2 volumes)
• Matemática básica para cursos superiores
• Tabelas de estatística
Para os cursos de
Administração e Engenharia
Para os cursos de
Administração e Engenharia
Quarta Edição
PesquisaOperacional
Pesq
uisa
Oper
ac
ion
al
Pesquisa Operacional Ermes Medeiros da Si lvaEl io Medeiros da Si lva
Val ter GonçalvesAfrânio Car los Murolo
• Programação linear• Simulação
Med
eiros •
M
edeiros
Gon
çalves •
M
urolo
5963.indd 1 20/7/2010 11:37:40
Ermes Medeiros da SilvaElio Medeiros da Silva
Valter GonçalvesAfrânio Carlos Murolo
Pesquisa OperacionalPara os cursos de Administração e Engenharia
Solução dos Exercícios Propostos
Referente à 4ª edição
São Paulo
Editora Atlas S.A. – 2012
Livro do Professor
Portal Atlas
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 2
Exercícios Propostos – Lista 1
Exercício 1Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 1
Variáveis de decisão: X1 = quantidade de sapatos a fabricar por hora
x2 = quantidade de cintos a fabricar por hora
Objetivo: max Lucro = 5 x1 + 2 x2
Restrições
R1 : tempo disponível para a programação = 1 hora ou 60 minutos
Tempo para fabricar um sapato (6 sapatos/h) = 60 min 10min por sapato6 sapatos
=
Tempo para fabricar um cinto (5 cintos/h) = 60 min 12 min por cinto5 cintos
=
Resumo: 10 x1 + 12 x2 ≤ 60
R2 : couro disponível = 6 unidades
Couro usado nos sapatos: x1 sapatos a 2 unidades de couro por sapato = 2 x1
Couro usado nos cintos : x2 cintos a 1 unidade de couro por cinto = 1 x2
Resumo: 2 x1 + x2 ≤ 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 3
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 4
x1: frequência semanal do programa A
x2: frequênia semanal do programa B
Objetivo: número de telespectadores alocados pelos programas
Programa A em x1 edições e 30.000 telespectadores por edição: 30.000 x1
Programa B em x2 edições e 10.000 telespectadores por edição: 10.000 x2
Objetivo: max Telespectadores = 30.000 x1 + 10.000 x2
Restrições:
R1. Exigência do patrocinador: no mínimo 5 minutos de propaganda na semana
Programa A: x1 edições e 1 minuto de propaganda por edição = 1 x1
Programa B: x2 edições e 1 minuto de propaganda por edição = 1 x2
Para satisfazer a exigência: x1 + x2 ≥ 5
R2. Restrição financeira do patrocinador: disponibilidade para 80 minutos de música .
Programa A: Tempo de música = x1 edições a 20 min por edição = 20 x1
Programa B: Tempo de música = x2 edições a 10 min por edição = 10 x2
Portanto, 20 x1 + 10 x2 ≤ 80
Exercícios Propostos – Lista 1
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 4
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 5
x1: quantidade a produzir do modelo M1 por dia
x2: quantidade a produzir do modelo M2 por dia
Objetivo max Lucro = 4 x1 + 3 x2
Restrições
R1. Capacidade de produção diária de M2 = 1.000
Tempo do dia usado para a produção da unidade de M2: 11.000
.
Produção diária de M2: x2. Parte do dia gasto para a produção de M2 = 21
1.000x
Tempo do dia usado para a produção de M1: 121.000
. Da mesma forma, a parte do
dia gasto para a produção de M1 é 11
500x .
A soma dos tempos fica restrito a um dia: 1 21 1 1
500 1.000x x+ ≤ ou 1 22 1.000x x+ ≤
R2. Disponibilidade de couro para a produção de M1 ou M2: 800. Então, x1 + x2 ≤ 800
R3. Disponibilidade de fivelas: para M1: 400. Então x1 ≤ 400
para M2: 700. Então x2 ≤ 700
Exercícios Propostos – Lista 1
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 5
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 8
X1: quantidade a investir no programa institucional ( em 1.000)
x2: quantidade a investir diretamente em P1 (em 1.000)
x3: qantidade a investir diretamente em P2 (em 1.000)
Objetivo: minimizar a soma dos investimentos. Min custo = x1 + x2 + x3
Restrições.
R1. Investimento mínimo requerido pelo programa institucional: x1 ≥ 3.000
R2. Proporcionar aumento mínimo de 30% na venda de P1
Aumento devido ao programa institucional (3% para cada 1.000 investido): 0,03 x1
Aumento devido ao investimento direto (4% para cada 1.000 investido): 0,04x2
Conclusão: 0,03 x1 + 0,04 x2 ≥ 0,30 ou 3 x1 + 4 x2 ≥ 30
R3. Proporcionar aumento mínimo de 30% na venda de P2.
Aumento devido ao programa institucional (3% para cada 1.000 investido): 0,03 x1
Aumento devido ao investimento direto (10% para cada 1.000 investido): 0,10 x3
Conclusão: 0,03 x1 + 0,10 x3 ≥ 0,30 ou 3 x1 + 10 x3 ≥ 30
R3. Restrição orçametária (disponibilidade de 10 milhares): x1 + x2 + x3 ≤ 10
Obs. Escrevendo o objetivo em $ 1 ao invés de em $ 1.000 teremos o valor final em unidades de capital: Min Custo = 1.000 x1 + 1.000 x2 +1.000 x3 o que nada altera a solução do problema.
Exercícios Propostos – Lista 1
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 6
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 9
Quantidade de materiais que comporão a mistura ( em Kg)
X1: quantidade de MR1 ; x2: quantidade de MR2; x3: qantidade de ferro puro ;
x4 quantidade de carvão; x5 : quantidade de silício; x6: quantidade de níquel
Objetivo: minimizar o custo do Kg da mistura.
Min custo = 0,20 x1 + 0,25 x2 + 0,30 x3 + 0,20 x4 + 0,28 x5 + 0,50 x6
Restrições.
R1. Quantidade de ferro na mistura:0,60 x1 (devido a MR1)+0,70 x2 (devido a MR2) + x3
0,60 ≤ 0,60 x1 + 0,70 x2 + x3 ≤ 0,65
R2. Quantidade de carvão na mistura:0,20 x1 (devido a MR1)+0,20 x2 (devido a MR2) + x4
0,15 ≤ 0,20 x1 + 0,20 x2 + x4 ≤ 0,20
R3. Quantidade de silício na mistura:0,20 x1 (devido a MR1)+0,05 x2 (devido a MR2) + x5
0,15 ≤ 0,20 x1 + 0,05 x2 + x5≤ 0,20
R4. Quantidade de níquel na mistura: 0,05 x2 (devido a MR2) + x6
0,05 ≤ 0,05 x2 + x6≤ 0,08
R5. A soma dos materiais usados na mistura deve pesar 1 Kg: x1 + x2 + x3 + x4 + x5 + x6 = 1
Exercícios Propostos – Lista 1
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 7
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 10
X I J é a quantidade de viagens (com carga de 10 ton) que serão realizadas daos portos i para as lojas j.
Objetivo.
Min distância total percorrida (veja o quadro de distâncias de cada porto para cada loja) = 30 x11 + 20 x12 + 24 x13 + 18 x14 + 12 x21 + 36 x22 + 30 x23 + 24 x24 + 8 x31 + 15 x32 + 25 x33 + 20 x34
Restrições:
R1. Suprir a loja L1 com 50 m3 (5 viagens) a partir dos 3 portos: x11 + x21 + x31 = 5
R2. Suprir a loja L2 com 80 m3 (8 viagens) a partir dos 3 portos: x12 + x22 + x32 = 8
R3. Suprir a loja L3 com 40 m3 (4 viagens) a partir dos 3 portos: x13 + x23 + x33 = 4
R4. Suprir a loja L4 com 100 m3 (10 viagens) a partir dos 3 portos: x14 + x24 + x34 = 10
Exercícios Propostos – Lista 1
Exercício 10
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 8
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 11
Variáveis de decisão:
xm , xe, xc são as quantidades a fabricar de mesas, estantes e cadeiras.
ym, ye ,yc são as quantidades a comprar de mesas, estantes e cadeiras.
Objetivo: Minimizar Custo = 100 xm + 130 xe + 90 xc + 120 ym + 150ye + 115 yc
Restrições:
R1.Para entregar 1.000 mesas temos que fabricar (xm) ou terceirizar a produção (ym) no mínimo esta quantidade: xm + ym ≥ 1000
R2 e R3. Da mesma forma em relação à estantes e cadeiras: xe + ye ≥ 800 e xc + yc ≥ 1.200
R4. Uso do recurso mão de obra (7.600 h disponíveis)
3 h por mesa em xm mesas + 4 h por estante em xe estantes + 2 h por cadeira em xc cadeiras
Resulta: 3 xm + 4 xe + 2 xc ≤ 7600
R5. Uso do recurso madeira (7.000 m2 disponíveis – veja o quadro de uso por unidade)
Resulta: 3 xm + 5 xe + 0,5 xc ≤ 7.000
R6. Uso do recurso metais (4.000 Kg disponíveis – veja o quadro de uso por unidade)
Resulta: 0,5 xm + xe + 2 xc ≤ 4.000
Exercícios Propostos – Lista 1
Exercício 11
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 9
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 11
Variáveis de decisão:
Variáveis de decisão: x1, x2, x3 são as quantidades (em kg) das misturas 1,2 e 3 no saco de 30 Kg da nova ração.
Objetivo: Min Custo = 0,30 x1 + 0,25 x2 + 0,28 x3
Restrições.
R1. O saco de 30 Kg de ração é composto exclusivamente pelas misturas M1, M2 e M3, participando com as quantidades x1, x2 e x3. Portanto, x1 + x2 + x3 = 30.
R2. O ingrediente 1 deve participar com pelo menos 5Kg no saco de ração. Esse total é obtido com 25% da Mistura 1 (0,25 x1), 9% da Mistura 2 (0,09 x2) e 32% da Mistura 3 (0,32 x3). Portanto, 0,25 x1 + 0,09 x2 + 0,32 x3 ≥ 5.
R3. O ingrediente 2 deve participar com pelo menos 6Kg no saco de ração. Esse total é obtido com 20% da Mistura 1 (0,20 x1), 0,30% da Mistura 2 (0,30 x2) e 18% da Mistura 3 (0,18 x3). Portanto, 0,20 x1 + 0,30 x2 + 0,18 x3 ≥ 6
Obs. Por erro de trancrição o porcentual do ingrediente 1 na mistura 2 que aparece como 0,20 no quadro de apresentação do problema (Pág12) e como 0,12 no modelo (resposta Pág 16) deve ser corrigido. O valor original é 0,09 como mostrado no modelo acima.
Exercícios Propostos – Lista 1
Exercício 12
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 10
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 13
Variáveis de decisão: x1, x2, x3 são as quantidades de Máq 1, Máq 2 e Máq 3 que deverão ser usadas na produção do lote de peças encomendado.
Objetivo.
Custo da Máq 1.
80 h de operação a R$ 85 por hora= 6.800
Custo do descarte é 5% da produção (80 h a 20 peças/h) ao custo de R$ 2 a peça descartada = 0,05 x (80 x 20) x 2 = 160.
O custo da Maq 1 é: 6.800 + 160 =6.960
Custo da Máq 2: da mesna forma é o custo de operação (80 x 75 = 6.000) mais o custo do descarte (0,03 x (80 x 15) x 2 = 72). O custo da Máq 2 é 6.000+72 = 6.072
Custo da Máq 3: (80 x 70) + 0,01 x (80 x 12) x 2 = 5.600 + 19,20 = 5.619,20
Objetivo: Min Custo = 6.960 x1 + 6.072 x2 + 5.619,20 x3
Restrições.
Produção da Máq 1 no período (total menos 5% de descarte): 80 h x 20 peças/h x 0,95 = 1.520. Produção da Máq 2. Da mesma forma: 80h x 15 peças/h x 0,97 = 1.164. Produção da Máq 3: 80 h x 12 peças/h x 0,99 = 950,40
R1, R2 e R3. Restrições ao número de máquinas disponíveis: x1 ≤ 4 x2 ≤3 x3 ≤ 1
R4. Produção a ser atingida no período: 7.240 peças.
Contribuição da Máq 1: produto de 1520 peças/máq pelo número de Máq 1 (x1) = 1.520 x1.
Contribuição da Máq 2: da mesma forma = 1.164 x2
Contribuição da Máq 3: 950,40 x3
Resultado: 1.520 x1 + 1.164 x2 + 950,40 x3 ≥ 7.240
Exercícios Propostos – Lista 1
Exercício 13
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 11
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 14
Este modelo é o mesmo do exercício anterior da mesma lista ( Lista 1 - Ex 13), com uma modificação.
Uma das Máq 1 deverá trabalhar 20 horas extras. Isto resulta um custo e uma diminuição do número de peças a ser produzida em regime de horas normais.
Custo.
Custo da hora extra: 85 + 0,20 x 85 = 102. Custo de 20 h xstras = 20 x 102 = 2.040
Custo do descarte: 5% da produção (20 h a 20 peças/h) a R$ 2 a peça = 0,05 x 400 x 2 = 40
Custo total devido a 20 h extras: 2.040 + 40 = 2.080
Produção em regime de horas extras: 400 peças menos o descarte de 5% =0,95 x 400 = 380
Peças a produzir em horário normal = 7.240 – 380 = 6.860
O modelo fica na forma:
Min Custo = 6.960 x1 + 6.072 x2 + 5.619,20 x3 + 2.080
s.a. x1 ≤ 4 x2 ≤ 3 x3 ≤ 1
1.520 x1 + 1.164 x2 + 950,40 x3 ≥ 6.860
Exercícios Propostos – Lista 1
Exercício 14
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 12
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 1 Ex 15
O modelo do problema 15 é o mesmo do problema 13 da Lista 1, com as modificações.
1. As 4 máquinas do tipo Máq 1 estarão em manutenção por 5 dias, o que significa que estarão disponíveis para produção durante os restantes 5 dias, podendo realizar apenas 40 horas de trabalho.
2. Após a manutenção o descarte deste tipo de máquina diminui de 5% para 3%, mantendo a produção de 20 peças por hora. No texto é citada diminuição para 18 peças, o que inviabiliza a solução do problema.
O custo da Máq 1 fica assim:
Custo de operação: 40 horas a R$ 85 por hora = 40 x 85 = 3.400
Custo do descarte: 3% da produção(40 horas a 20 peças/h) a R$ 2 cada peça
=0,03 x(40 x 20 ) x 2=48
Custo total da Máq 1 = 3.400 + 48 = 3.448
Produção da Máq 1: peças produzidas em 40 horas menos o descarte (97% do total)
= 40 x 20 x 0,97 = 776
Modelo. Min custo = 3.448 x1 + 6.072 x2 + 5.619,20 x3
s.a. x1 ≤ 4 x2 ≤ 3 x3 ≤ 3
776 x1 + 1164 x2 + 950,40 x3 ≥ 7240
Exercícios Propostos – Lista 1
Exercício 15
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 13
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 1.1
R1 1 2 2 4x x− + = 1 2 2 10 2 e 0 4x x x x= ⇒ = = ⇒ =
Teste: 1 20 e 0 0 4x x= = ⇒ ≤ . O ponto ( )0,0 está na região de soluções.
R2 e R3 são construídas da mesma forma.
Objetivo Atribuindo um valor arbitrário para o objetivo, por exemplo o valor 12.
1 2 1 2 2 12 3 12 temos: 0 4 e 0 6 x x x x x x+ = = ⇒ = = ⇒ =
Observamos que à medida que esse valor aumenta a reta afasta-se mais da origem do sistema.
O ponto que maximiza o objetivo na região de soluções é o ponto ( )6,0 . Lucro = 12
Exercícios Propostos – Lista 2
Exercício 1.1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 14
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos - Lista 2
Ex 1.2
R1 2 1 2 2x x+ = 1 2 2 10 2 e 0 1x x x x= ⇒ = = ⇒ =
Teste: 1 20 e 0 0 2x x= = ⇒ ≤ . O ponto ( )0,0 está na região de soluções.
R2 é construída da mesma forma.
Objetivo: Atribuindo um valor arbitrário para o objetivo, por exemplo o valor 0,7.
1 2 1 2 2 10,3 0,5 0,7 temos: 0 1, 4 e 0 2,33x x x x x x+ = = ⇒ = = ⇒ =
Observamos que à medida que esse valor aumenta a reta afasta-se mais da origem do sistema. O ponto que maximiza o objetivo na região de soluções é a interseção das retas R1 e R2.
1 2 1 2 1 1 1 2De R : 2 2 . Substituindo em R 6 6 3 0,6 e 0,8x x x x x x= − + − = ⇒ = =
Lucro = 0,3 0,6 0,5 0,8 0,58× + × =
Exercícios Propostos – Lista 2
Exercício 1.2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 15
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 1.3
Construção das restrições:
1 1 2 2 1R : 0 3 0 9x x x x= ⇒ = = ⇒ =
2 1 2 2 1R : 0 2 0 6x x x x= ⇒ = = ⇒ =
3 1 2 2 1R : 0 6 0 6x x x x= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 15, por exemplo: 1 2 2 10 5 0 7,5x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto com maior valor do objetivo na região de restrições é a interseção das retas R1 e R3.
3 1 2 1 2 2 2 1de R : 6 . Substituindo em R : 6 3 9 1,5 e 4,5x x x x x x= − − + = ⇒ = =
Objetivo=13,5
Exercícios Propostos – Lista 2
Exercício 1.3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 16
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 1.4
Construção das restrições:
1 1 2 2 1R : 0 20 0 20x x x x= ⇒ = = ⇒ =
2 1 2 2 1R : 0 10 0 10x x x x= ⇒ = = ⇒ =
3 1 2 2 1R : 0 9 0 10,8x x x x= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 84, por exemplo: 1 2 2 10 7 0 8,4x x x x= ⇒ = = ⇒ =
À medida que diminuímos o valor do objetivo, a reta aproxima-se da origem. As retas R3 e Objet são paralelas e todos os pontos do segmento de R3 com 6 < x<10,8 são pontos da solução ótima. Por exemplo, o ponto x = 10,8 e y=0
Objetivo=108
Exercícios Propostos – Lista 2
Exercício 1.4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 17
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 1.5
Construção das restrições:
1 1 2 2 1R : 0 2 0 2x x x x= ⇒ = = ⇒ = −
2 3: 5 R : 6R x x= = 4 1 2 2 1R : 0 3 0 5x x x x= ⇒ = = ⇒ =
5 1 2 2 1R : 0 5 0 4x x x x= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 21, por exemplo: 1 2 2 10 2,33 0 3x x x x= ⇒ = = ⇒ =
À medida que diminuímos o valor do objetivo, a reta aproxima-se da origem. O ponto da região de soluções viáveis com o menor valor do objetivo é a interseção das retas R4 e R5.
4 2 1 5 1 1 1 2de R : 3 0,6 . Subst em R : 5 12 2,4 20 3,077 e 1,154x x x x x x= − + − = ⇒ = =
Objetivo = 7 30,77 9 1,054 31,923× + × =
Exercícios Propostos – Lista 2
Exercício 1.5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 18
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 2
Construção das restrições:
1 1 2 2 1R : 0 5 0 6x x x x= ⇒ = = ⇒ =
2 1 2 2 1R : 0 6 0 3x x x x= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 21, por exemplo: 1 2 2 10 2,33 0 3x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto da região de soluções viáveis com o maior valor do objetivo é o ponto x1 = 3, x2 = 0
Objetivo = 5 3 2 0 15× + × = Recurso ocioso R1 (tempo): 30 minutos.
Exercícios Propostos – Lista 2
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 19
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 3
Construção das restrições:
1 1 2 2 1R : 0 40 0 60x x x x= ⇒ = = ⇒ =
2 1R : 40x =
3 2: 30R x =
Atribuindo ao objetivo o valor 6.600, por exemplo:
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. A reta do objetivo é paralela a R1. Todos os pontos de R1 de x = 15 a x = 40 são soluções ótimas. Por exemplo o ponto (15,30). Objetivo = 100 15 150 30 6.000× + × =
Recurso ocioso R2 (mercado de P1): 40 – 15 = 25 unidades.
Exercícios Propostos – Lista 2
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 20
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 4
Construção das restrições:
1 1 2 2 1R : 0 600 0 600x x x x= ⇒ = = ⇒ =
2 1R : 100x =
3 2: 200R x =
Atribuindo ao objetivo o valor 15.000, por exemplo:
1 2 2 10 500 0 1500x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto ótimo é a interseção das retas R1 e R3. De R3, x = 200. De R1 , 2 600 200 400x = − =
Objetivo = 10 200 30 400 4.000 18.000× + × + =
Recurso ocioso : não há.
Exercícios Propostos – Lista 2
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 21
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 5
Construção das restrições:
1 1 2 2 1R : 0 5 0 5x x x x= ⇒ = = ⇒ =
2 1 2 2 1R : 0 8 0 4x x x x= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 90.000, por exemplo:
1 2 2 10 9 0 3x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto ótimo é a interseção das retas R1 e R2.
( )1 2 1 2 1 1 1 2: 5 R : 20 10 5 80 3 , 2R x x x x x x= − + − = ⇒ = =
Objetivo = 30.0000 3 10.000 2 110.000× + × =
Recurso ocioso: não há.
Exercícios Propostos – Lista 2
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 22
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2
Ex 6
Construção das restrições:
1 1 2 2 1R : 0 1.000 0 500x x x x= ⇒ = = ⇒ =
2 1 2 2 1R : 0 800 0 800x x x x= ⇒ = = ⇒ =
4 1: 400R x = 5 2: 700R x =
Atribuindo ao objetivo o valor 900, por exemplo:
1 2 2 10 300 0 225x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto ótimo é a interseção das retas R1 e R2.
1 2 1 2 1 1 1 2: 1.000 2 R : 1.000 2 800 200 , 600R x x x x x x= − + − = ⇒ = =
Objetivo = 4 200 3 600 2.600× + × =
Recursos ociosos: fivela A (R3): 200 unidades e fivela B (R4): 100 unidades
Exercícios Propostos – Lista 2
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 23
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2 Ex 7
X1: número de dias de operação da F1 x2: número de dias de operação da F2
Objet. Min Custo = 1000x1+2000x2 sujeito a 1 2
1 2
1 2
8 2 16 papel fino
6 papel médio
2 7 28 papel grosso
x x
x x
x x
+ ≥
+ ≥ + ≥
Construção das restrições:
1 1 2 2 1
2 1 2 2 1
3 1 2 2 1
R : 0 8 0 2
: 0 6 0 6
: 0 4 0 14
x x x x
R x x x x
R x x x x
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 5.000, por exemplo:
1 2 2 10 2,5 0 5x x x x= ⇒ = = ⇒ =
À medida que diminuímos o valor do objetivo, a reta aproxima-se da origem. O ponto ótimo é a interseção das retas R3 e R2.
( )2 2 1 3 1 1 1 2: 6 R : 2 7 6 28 2,8 e 3, 2R x x x x x x= − + − = ⇒ = =
Objetivo = 1.000 2,8 2.000 3,2 9.200× + × =
Exercícios Propostos – Lista 2
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 24
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2 Ex 8
X1: número de caminhões tipo A a usar x2: número de caminhões tipo B a usar
Objet. Min Custo = 1.100 x1+750 x2
sujeito a 1 2
1 2
2 2 16 espaço refrigerado necessário
3 12 espaço não refrigerado necessário
x x
x x
+ ≥ + ≥
Construção das restrições:
1 1 2 2 1
2 1 2 2 1
R : 0 8 0 8
: 0 12 0 4
x x x x
R x x x x
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
Atribuindo ao objetivo o valor 3.000, por exemplo:
1 2 2 10 4 0 2,73x x x x= ⇒ = = ⇒ =
À medida que diminuímos o valor do objetivo, a reta aproxima-se da origem. O ponto ótimo é a interseção das retas R1 e R2.
( )2 2 1 3 1 1 1 2: 12 3 R : 2 2 12 3 16 2 e 6R x x x x x x= − + − = ⇒ = =
Objetivo = 1.100 2 750 6 6.700× + × =
Exercícios Propostos – Lista 2
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 25
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2 Ex 9
X1: quantidade a produzir de P1 por dia x2: quantidade a produzir de P2 por dia
Objet. Max receita = 1.900 x1+2.100 x2 sujeito a
1 2
1 2
1 2
4 2 20 forjaria
3 10 polimento
100 200 500 matéria prima
x x
x x
x x
+ ≤
+ ≤ + ≤
Construção das restrições:
1 1 2 2 1
2 1 2 2 1
3 1 2 2 1
R : 0 10 0 5
: 0 3,33 0 5
: 0 2,5 0 5
x x x x
R x x x x
R x x x x
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
a) Atribuindo ao objetivo o valor 15.000, por exemplo:
1 2 2 10 7,14 0 7,89x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto ótimo é
1 25, 0x x= = . Objetivo = 1.900 5 750 0 9.500× + × =
( ) ( )1 2
1 2
b) Max Lucro 1900 100 4 150 2 100 2100 200 2 150 3 100
ou max lucro = 1000 1300
x x
x x
= − − × − × + − − × − ×
+
1 2 2 1Atribuindo o valor 11.700 ao lucro: 0 9 3 7,8x x x x= ⇒ = = ⇒ =
O ponto ótimo é ainda x1 = 5, x2 = 0 com lucro de 5.000
Exercícios Propostos – Lista 3
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 26
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 2 Ex 10
X1: quantidade (ton) de gasolina por ano x2: quantidade (ton) de óleo diesel por ano
Objet. Max receita = 7 x1+5 x2 sujeito a
1
2
1 2
1 2
400.000 reforming catalítico
450.000 craqueamento catalítico
1 1 1 capacidade de destilação500.000 600.000
1 1 1 capacidade de dessulfuração700.000 500.000
x
x
x x
x x
≤
≤ + ≤ + ≤
Construção das restrições:
1 1 2 2
3 1 2 2 1
4 1 2 2 1
R : 400.000 R : 450.000
: 0 600.000 0 500.000
: 0 500.000 0 700.000
x x
R x x x x
R x x x x
= =
= ⇒ = = ⇒ =
= ⇒ = = ⇒ =
a) Atribuindo ao objetivo o valor 15.000, por exemplo:
1 2 2 10 7,14 0 7,89x x x x= ⇒ = = ⇒ =
À medida que aumentamos o valor do objetivo, a reta afasta-se da origem. O ponto ótimo é a interseção das retas R1 e R3.
1 1 3 2400000: 400.000 R : 1 600000 120.000500000
R x x = = − × =
.
Objetivo = 7 400.000 5 120.000 3.400.000× + × =
Exercícios Propostos – Lista 2
Exercício 10
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 27
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.1
Exercícios Propostos – Lista 2
Exercício 1.1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 28
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.2
Exercícios Propostos – Lista 3
Exercício 1.2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 29
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.3
Exercícios Propostos – Lista 3
Exercício 1.3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 30
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.4
Exercícios Propostos – Lista 3
Exercício 1.4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 31
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.5
Exercícios Propostos – Lista 3
Exercício 1.5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 32
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 1.6
Exercícios Propostos – Lista 3
Exercício 1.6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 33
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 2.1
Variáveis de decisão: x1 número de sapatos a fabricar por hora
X2 – número de cintos a fabricar por hora
Modelo: Max lucro = 5x1 + 2x2
s.a. 10x1 + 12x2 ≤ 60 uso do recurso tempo - xf1 é a sobra de tempo
2x1 + x2 ≤ 6 uso do recurso couro - xf2 é a sobra de couro
X1 ≥ 0 x2 ≥ 0
Exercícios Propostos – Lista 3
Exercício 2.1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 34
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 2.2
Variáveis de decisão: x1 – quantidade de P1 a fabricar no mês
X2 – quantidade de P2 a fabricar no mês
Modelo: Max lucro = 100 x1 + 150 x2
s.a. 2 x1 + 3 x2 ≤ 120 uso do recurso tempo - xf1 é a sobra do tempo
x1 ≤ 40 demanda de P1 - xf2 é a demanda não suprida de P1
x2 ≤ 30 demanda de P2 - xf3 é a demanda não suprida de P2
X1 ≥ 0 x2 ≥ 0
Exercícios Propostos – Lista 3
Exercício 2.2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 35
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 2.3
Variáveis de decisão: x1 número de caixas de pêssegos a transportar; X2 – número de caixas de tangerinas a transportar
Modelo: Max lucro = 10 x1 + 30 x2
s.a. x1 + x2 ≤ 600 espaço disponível no caminhão - xf1 é a sobra do espaço
x1 ≥ 100 venda certa de cxs de pêssegos - xf2 é a venda eventual
x2 ≤ 200 demanda por cxs de tangerinas – xf3 é a sobra da demanda
Exercícios Propostos – Lista 3
Exercício 2.3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 36
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 3
Variáveis de decisão: x1 quantidade de peças do modelo M1
X2 quantidade de peças do modelo M2
Objetivo: Max Receita = 6.000 x1 + 10.000 x2
s.a. 4 x1 + 2 x2 ≤ 32 uso do recurso brim - xf1 é a sobra de brim
2 x1 + 4x2 ≤22 uso do recurso seda - xf2 é a sobra de seda
2 x1 + 6x2 ≤ 30 uso do recurso cetim - xf3 é a sobra de cetim
Exercícios Propostos – Lista 3
Exercício 3
obj
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 37
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 4
Variáveis de decisão: x1 quantidade de P1 a produzir no período
X2 quantidade de P2 a produzir no período
Objetivo: MaxLucro = (50 - 20 – 20%x50) x1 + (70 - 30 -20% x 70) x2 = 20 x1 + 26 x2
s.a. 2 x1 + 3 x2 ≤ 3.000 uso do recurso R1 - xf1 é a sobra do recurso R1
4 x1 + 2x2 ≤4.000 uso do recurso R2 - xf2 é a sobra do recurso R2
x1 + 5x2 ≤ 4.500 uso do recursoR3 - xf3 é a sobra do recurso R3
x1 + x2 ≤ 1.000 demanda conjunta – xf4 é a sobra de mercado
Exercícios Propostos – Lista 3
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 38
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 5
Variáveis de decisão: xm, xe, xc são as quantidades a produzir de mesas, estantes e cadeiras
ym,ye,yc são as quantidades a comprar de mesas, estantes e cadeiras
Objetivo: Min Custo = 100xm + 130xe + 90xc + 120ym + 150ye + 115yc
Necessidades mínimas Uso dos recursos
xm + ym ≥ 1000 de mesas 3 xm+4 xe+2 xc ≤ 7.600 horas disponíveis
xe + ye ≥800 de estantes 3 xm + 5 xe + 0,5 xc ≤7.000 madeira disponível
xc + yc ≥1.200 de cadeiras 0,5 xm + xe + 2 xc ≤ 4.000 componestes metálicos
Vamos resolver o problema usando a ferramenta Solver da planilha Excel. Veja roteiro no anexo ao livro pág 179. A solução encontrada é a que segue.
Exercícios Propostos – Lista 3
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 39
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 6
Variáveis de decisão: x1, x2, x3 são as quantidades ( em kg) das misturas 1,2 e 3 no saco de 30 Kg da nova ração.
Objetivo: Min Custo = 0,30 x1 + 0,25 x2 + 0,28 x3
s.a. x1 + x2 + x3 = 30
0,25 x1 + 0,09 x2 + 0,32 x3 ≥ 5
0,20 x1 + 0,30 x2 + 0,18 x3 ≥ 6
Vamos resolver usando a ferramenta Solver do Excel. Veja roteiro no Anexo, Pág 179 do texto.
Após carregar objetivo e restrições, a solução aparece a seguir.
Obs. Por erro de trancrição o porcentual do ingrediente 1 na mistura 2 que aparece como 0,20 no quadro de apresentação do problema ( Pág12 ) e como 0,12 no modelo( resposta Pág 16) deve ser corrigido. O valor original é 0,09 como mostrado no modelo acima.
Exercícios Propostos – Lista 3
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 40
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 7
Variáveis de decisão: x1, x2, x3 são as quantidades de Máq 1, Máq 2 e Máq 3 que deverão ser usadas na produção do lote de peças encomendado.
Custo da Máq 1: 80 h de operação a R$ 85 por hora mais o custo do descarte que é 5% da produção a R$ 2 a peça descartada = 80 x 85 +0,05 x (20 x 80) x 2 = 6.800 + 160 = 6.960
Custo da Máq 2: da nesna forma = 80 x 75+0,03 x (15 x 80) x 2 = 6.000+72 = 6.072
Custo da Máq 3: 80 x 70 + 0,01 x (80 x 12) x 2 = 5.600 + 19,20 = 5.619,20
Objetivo: Min Custo = 6.960 x1 + 6.072 x2 + 5.619,20 x3
Produção da Máq 1 no período: 80 h x 20 peças/h x 0,95 = 1.520. Da mesma forma produção da Máq 2 : 80h x 15 peças/h x 0,97 = 1.164. Para a Máq 3: 80 h x 12 peças/h x 0,99 = 950,40
Restrições x1 ≤ 4 x2 ≤3 x3 ≤ 1 restrições ao número de máquinas disponíveis
1.520 x1 + 1.164 x2 + 950,40 x3 ≥ 7.240 produção a ser atingida no período
Vamos resolver usando a ferramenta Solver do Excel. Veja roteiro no Anexo, Pág 179 do texto. Após carregar objetivo e restrições, a solução aparece a seguir.
Considerando resultados inteiros, a solução seria: Máq1 : 4 Máq 2 : 1 Custo : R$ 33.912,00.
Exercícios Propostos – Lista 3
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 41
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 3 Ex 8
Variáveis de decisão: x1, x2, x3 são as quantidades de Máq 1, Máq 2 e Máq 3 que deverão ser usadas na produção do lote de peças encomendado.
Custo da Máq 1: 40 h de operação a R$ 85 por hora mais o custo do descarte que é 3% da produção a R$ 2 a peça descartada = 40 x 85 +0,03 x (20 x 40) x 2 = 3.400 + 43,20 = 3.448
Custo da Máq 2: da nesna forma = 80 x 75+0,03 x (15 x 80) x 2 = 6.000+72 = 6.072
Custo da Máq 3: 80 x 70 + 0,01 x (80 x 12) x 2 = 5.600 + 19,20 = 5.619,20
Objetivo: Min Custo = 3.448 x1 + 6.072 x2 + 5.619,20 x3
Produção da Máq 1 no período: 40 h x 20 peças/h x 0,97 = 776. Da mesma forma produção da Máq 2 : 80h x 15 peças/h x 0,97 = 1.164. Para a Máq 3: 80 h x 12 peças/h x 0,99 = 950,40
Restrições x1 ≤ 4 x2 ≤3 x3 ≤ 1 restrições ao número de máquinas disponíveis
776 x1 + 1.164 x2 + 950,40 x3 ≥ 7.240 produção a ser atingida no período
Vamos resolver usando a ferramenta Solver do Excel. Veja roteiro no Anexo, Pág 179 do texto. Após carregar objetivo e restrições, a solução aparece a seguir.
Ajuste. A Máq 3 deverá trabalhar apenas 54 horas e 13 minutos.
Exercícios Propostos – Lista 3
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 42
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 1
Exercícios Propostos – Lista 4
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 43
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 2
Construção da função objetiva auxiliar W.
1 2 1 2
1 2 1 2
11
2 2 2 2
1 12 f 10 a 10 2 f
5 f 15 15 5 f
x x x a x x x
x x x a a x x x
+ − + = ⇒ = − − +
+ − + = ⇒ = − − +
1 21 2 2125 3 6 f fW a a x x x x= + = − − + +
Min W = Max (-W) = 1 2 213 6 f f 25x x x x+ − − +
Exercícios Propostos – Lista 4
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 44
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 3
X2 é variável livre: x2 = x4 – x5. O modelo fica na forma:
Max z = x1 + x4 – x5 + 2x3 s.a. x1 + 2x4 – 2x5 ≤ 10
3x1 + 4x4 – 4x5 + x3 ≤ 20
A variável que deve entrar na base apresenta os coeficientes nas restrições todos negativos. A solução neste caso é ilimitada.
Exercícios Propostos – Lista 4
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 45
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 4
Função objetivo Min z = 2 x1 + 4 x2 + 10 x3 equivale a Max (-z) = - 2 x1 – 4x2 – 10x3
A solução encontrada é x1 = 30, x2 = 0, x3 = 0 com z = 60. Como as variáveis não básicas x2 e x3 apresentam coeficientes nulos na função objetivo, elas poderão entrar na base gerando uma outra solução, sem alterar o valor do objetivo. Portanto, o problema apresenta várias soluções ótimas equivalentes.
Exercícios Propostos – Lista 4
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 46
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 5
Vamos usar o método do M grande para compor a solução básica inicial. Construção da função objetivo. Min z = Máx (-z) = - 2x1 – 4x2 – 5x3
Com a adição da variável auxiliar a2 a função fica: Max (- z)= - 2x1 – 4x2 – 5x3 – Ma2
A solução é: x1 = 50, x2 = 0, x3 = 0, com z = 100.
Exercícios Propostos – Lista 4
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 47
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 6
Precisamos de variáveis auxiliares a1 e a2 para a solução básica inicial. A função objetivofica na forma: Max z = x1 + 2 x2 + x3 - M1a1 - M2a2.
A variável que deve entrar na base tem os coeficientes nas restrições todos negativos. A solução é, portanto, ilimitada.
Exercícios Propostos – Lista 4
Exercício 6
obj
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 48
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 7
Para construir a função objetivo devemos passar para a forma de maximização e agregar duas variáaveis auxiliares para as restrições R1 e R2.
Min z = Max (-z) = -3x1 - 2x2 - x3 - M1a1 - M2a2
Solução: X1 = 1,6 X2 = 0,6 X3 = 0,2 Z = 6,2
Exercícios Propostos – Lista 4
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 49
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex 8
Montagem do modelo.
Variáveis de decisão. . custo unitário Custo do material
x1 = quantidade de chapéus na caixa 50 50 x1
x2 = quantidade de línguas de sogra na caixa 20 20 x2
x3 = quantidade de bexigas na caixa 5 5 x3
Objetivo. Minimizar o custo = 50 x1 + 20 x2 + 5 x3
Restrições.
R1. Quantidade de chapéus e línguas de sogra: x1 + x2. Quantidade total: x1 + x2 + x3.
X1 + x2 ≥0,50( x1 + x2 + x3) ou - 0,5 x1 - 0,5 x2 + 0,5 x3 ≤ 0
R2. Pacote com pelo menos 20 bexigas: x3 ≥ 20
R3. Cada item concorre com pelo menos 25% da caixa.
Chapéu: x1 ≥ 0,25(x1 + x2 + x3) ou -0,75 x1 +0,25 x2 + 0,25x3 ≤0
R4. Língua de sogra: x2 ≥ 0,25(x1 + x2 + x3) ou 0,25 x1 – 0,75 x2 + 0,25x3 ≤ 0
R5. Bexiga: x3 ≥ 0,25(x1 + x2 + x3) ou 0,25x1 + 0,25x2 – 0,75x3 ≤ 0
Solução. Precisamos de uma variável auxiliar para R2. A função fica assim:
Min z = Max (-z) = -x1 – x2 – x3 – Ma2
Exercícios Propostos – Lista 4
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 50
A função auxiliar W tem valor zero. A solução é x1 = 10 x2 = 10 x3 = 20 Custo = 800
Obj
Obj
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 51
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 4 Ex9
Variáveis de decisão.
x1: quantidade diária a produzir de P1 x2: quantidade diária a produzir de P2
x3: quantidade diária a produzir de P3
Objetivo. Maximizar o lucro = 500 x1 + 800 x2 + 400 x3
Restricões.
R1. Armazenar no máximo 5 dias de produção .
Espaço ocupado por unidade de P1 no armazém: 1/1.000
Produção de 5 dias de P1: 5 x1
Espaço do armazém ocupado pelo produto P1 produzido em 5 dias: 1 5 1 0,005 1
1.000x x=
Espaço do armazém ocupado pelo produto P2 produzido em 5 dias: 1 15 2 2
900 180x x=
Espaço do armazém ocupado pelo produto P3 produzido em 5 dias: 1 15 3 3
1.200 240x x=
Armazenagem: 1 2 31 10,005 1
180 240x x x+ + ≤ (armazém)
R2, R3, R4. Capacidade de produção diária. Para P1: 8H a 10 un/h=80 un/dia. Portanto x1 ≤ 80.
Para P2: 8h a 6 un/h =48 un/dia . Portanto x2 ≤ 48. Da mesma forma, x3 ≤ 120.
R5. Matéria prima. Disponibilidade diária de 240 Kg.
Uso para P1: x1 unidades por dia a 1,5 Kg por unidade = 1,5 x1
Uso para P2: x2 unidades por dia a 2,4 kg por unidade = 2,4 x2
Uso para P3: 2 x3
Restrição da matéria prima: 1,5 x1 + 2,4 x2 + 2 x3 ≤2.40º
Obs. Para melhorar as operações com a restrição R1, vamos multiplicá-la por 720:
R1. 3,6 x1 + 4 x2 + 3 x3 ≤ 720
Exercícios Propostos – Lista 4
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 52
Solução: Produzir 80 un. de P1, 48 un. de P2, 2,4 un. de P3 Lucro 79.360.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 53
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 5 Ex1
Respostas
a. Solução do quadro. Produzir 3 unidades de P3. Sobra de recursos: 7 unidades de R1 (valor de xf1) e 12 unidades de R3 (valor de xf3). O lucro obtido é de 9,00.
b. Recursos escassos: R2 (xf2 = 0)
c. O novo programa ótimo teria lucro de 9,00-0,50 = 8,50
d. Venderia pelo valor de mercado (no caso o preço de custo), pois há sobra deste recurso para o programa.
e. O preço de venda deve ser no mínimo o seu custo mais o valor de oportunidade 0,75.
f. Modelo dual min D = 10 y1 + 12 y2 + 9 y3
y1 + 2y2+y3 ≥ 1 s.a. y1 + y2 + 3y3 ≥ 0,3 y1 + 4y2 – y3 ≥ 3 , y1≥0, y2≥0, y3≥0
g. Quadro de solução ótima dual.
D Y1 Y2 Y3 Yf1 Yf2 Yf3 C -1 7 0 12 0 0 3 -9 0 1 0 0 0,75 0 0 1 0 0,45 0 0 0 1 0,50 Solução dual: y1 = 0, y2 = 0,75, y3 = 0, D = 9
h. A variável dual y1 é o valor de oportunidade do recurso R1, isto é, a capacidade de uma unidade deste recurso de gerar lucro.
i. A função objetivo dual mede o valor de oportunidade do estoque de recursos, isto é, a capacidade de o estoque de recursos gerar lucro.
j. O lado esquerdo da segunda restrição dual mede o valor interno do produto P2, calculado em termos dos recursos nele empregados. O lado direito mede o valor externo ou valor de mercadode P2, isto é, a capacidade do mercado de atribuir lucro a P2.
l. O valor interno de P2 é y1 + y2 + 3 y3 = 0,75 e o valor externo 0,30. Portanto, o mercado não remunera suficientemente o produto P2 ( valor interno maior que valor externo), e não devemos produzí-lo.
m. O valor interno de P3 é y1 + 4 y2 – y3 = 3, e o valor externo é 3,00. O mercado remunera convenientemente o produto P3 e podemos produzí-lo.
Exercícios Propostos – Lista 5
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 54
n. Pagaria no máximo 0,75 além do preço normal de mercado (meu preço de custo) pois o recurso R1 tem capacidade de gerar lucro de 0,75, gerando receita = custo + 0,75.
o. Em ptincípio não tenho interêsse em adquirir uma unidade de R3 pois este recurso está sobrando no meu programa.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 55
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 5 Ex 2
Respostas
a. Modelo linear
1. Variáveis de decisão. Quantidades (em Kg) de ingredientes, em 40 Kg de ração. x1 : ingrediente 1; x2 : ingrediente 2; x3 : ingrediente 3.
2. Objetivo. Min custo do saco de40 Kg de ração = 200 x1 + 150 x2 + 240 x3
s.a.
( )1 2 3 1 2 3
1 2 3 1 2 3
1 2 3 1 2 3
50 20 10 6 nutriente 1 ou 50 20 10 600100 100 10020 30 20 5 (nutriente 2) ou 20 30 20 500
100 100 10010 30 50 8 (nutriente 3) ou 10 30 50 800100 100 100
x x x x x x
x x x x x x
x x x x x x
+ + ≥ + + ≥
+ + ≥ + + ≥
+ + ≥ + + ≥
b. Modelo dual Max D = 600 y1 + 500 y2 + 800 y3
50 y1 + 20 y2 + 10 y3 ≤ 200
s.a. 20 y1 + 30 y2 + 30 y3 ≤ 150
10 y1 + 20 y2 + 50 y3 ≤ 240
c. Solução do modelo dual
Quadro final primal
Exercícios Propostos – Lista 5
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 56
D X1 X2 X3 Xf1 Xf2 Xf3 b -1 0 0 70,77 3,46 0 2,69 -4230,77 0 1 0 0 1,54 0 0 1 0 26,15 0 0 0 1 315,38
d. xf1 representa o excesso de nutriente 1 no saco de ração, em relação à exigência mínima.
xf2 representa o excesso de nutriente 2 no saco de ração, em relação à exigência mínima.
xf3 representa o excesso de nutriente 3 no saco de ração, em relação à exigência mínima.
e. y1 representa o valor de oportunidade do nutriente 1, isto é, o valor acima do seu custo para o programa. O uso de uma unidade a mais do nutriente 1 na mistura, aumenta o custo da mistura em 3,46.
y2 o mesmo que y1 em relação ao nutriente 2. No caso, o uso de uma unidade a mais do nutriente 2 não aumenta o custo da mistura.
y3 o mesmo que o nutriente 1 em relação ao nutriente 3. O uso de uma unidade a mais do nutriente 3 acarreta um aumento de custo de 2,69.
f. yf1 é o valor de oportunidade do ingrediente 1, isto é, o acréscimo no custo com a introdução de mais uma unidade do ingrediente 1 na mistura. No caso o valor é zero.
yf2 o mesmo que yf1 em relação ao ingrediente 2. O uso de uma unidade a mais não aumenta o custo .
yf o mesmo que yf1 em relação ao ingrediente 3. No caso, o acréscimo no custo pela introdução de uma unidade a mais do ingrediente 3 eleva o custo da mistura em 70,77.
g. A função objetivo dual mede o valor de oportunidade da mistura em relação aos níveis mínimos de nutrientes requeridos na sua composição.
h. O lado esquerdo da segunda restrição dual 20 y1 + 30 y2 + 30 y3, mede o valor interno (ou de oportunidade) do ingrediente 2. O lado direito mede o valor externo ou de mercado do ingrediente 2.
i. O lado esquerdo da primeira restrição primal mede o aporte de nutriente 1 a partir dos 3 ingredientes. O lado direito mede a necessidade mínima deste ingrediente na mistura.
j. Se a exigência mínima aumentar de 6 para 7 Kg na participação do nutriente 1 por saco de ração, o custo da mistura aumenta em 3,46.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 57
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 5 Ex3
a. Modelo primal
1. Variáveis de decisão: x1 quantidade a adquirir de P1; x2 quantidade a adquirir de P2; x3 quantidade a adquirir de P3.
2. Objetivo max Lucro = 60 x1 + 30 x2 +120 x3
3. Restrições 1 2 3
1 2 3
10 5 100.000
240 90 300 30.000.000
x x x
x x x
+ + ≤ + + ≤
b. Modelo dual Min D = 100.000 y1+30.000.000 y2
sujeito a
10 1 240 2 601 90 2 30
5 1 300 2 80
y yy yy y
+ ≥ + ≥ + ≥
c. Solução do modelo primal.
Quadro da solução ótima dual, obtida a partir do quadro da solução ótima primal.
Y1 Y2 Yf1 Yf2 Yf3 D 0 21.000.000 0 100.000 0 3.000.000 1 0 0 30 0 1 0 240 0 0 1 30
d. Comprar 100unidades de P2.
Exercícios Propostos – Lista 5
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 58
e. A função objetivo dual mede o valor de oportunidade (capacidade de gerar lucro, no caso) dos recursos capital e espaço de estocagem.
f. y1 é o valor de oportunidade (capacidade de gerar lucro) do recurso espaço de estocagem.
Y2 é o valor de oportunidade (capacidade de gerar lucro) do recurso capital.
g. yf1 é a diferença entre os valores interno e externo do produto 1.
yf2 é a diferença entre os valores interno e externo do produto P2.
h. A expressão 10 x1 + x2 + 5x3 mede o uso do espaço de estocagem pelos produtos. O lado direito mede a disponibilidade deste recurso.
i. A expressão 90 y1 + y2 mede o valor de oportunidade (valor interno) do produto P2. O lado direito mede o valor externo do produto P2, ou então, o lucro atribuído a P2 pelo mercado.
j. Se tivéssemos mais um metro cúbico de espaço de estocagem, aumentaríamos o nosso lucro em 30, ou seja, o metro cúbico a mais gera uma receita que supera em $30 o custo corrente de estocagem. Se o custo corrente (CC) for diferente de $20 o aumento no lucro seria de 30-(20-CC). Por exemplo, se o CC for 15 o lucro passaria a 30-(20-15) = 30-5 = 25. Se o CC for 25 o lucro passaria a 30-(20-25) = 30+5 = 35.
l. Não interessa alocar mais uma unidade de capital, pois o programa apresenta uma sobra de $ 21.000.000 deste recurso.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 59
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex1
Solução inicial pelo método do canto noroeste.
40 40/0 10 40 50 100/90/50/0 10 10/0 50/10/0 40/0 60/10/0 Otimização. Coeficientes das variáveis básicas Cij – Ui - Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X22: 25 – U2 – V2 = 0
X23: 18 – U2 – V3 = 0 X33: 24 – U3 – V3 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 23; V3 = 16; U3 = 8
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 23 = - 8 X13: 20 – 0 – 16 = 4 X31: 16 – 8 – 10 = - 2 X32: 14 – 8 – 23 = – 17
Entra X32. Circuito de compensação.
40 40 10 40 – θ 50 + θ 100 θ 10 – θ 10 50 40 60 O maior valor possível para θ é 10, A Nova solução é
40 40 10 30 60 100 10 10 50 40 60 . Coeficientes das variáveis básicas Cij – Ui - Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X22: 25 – U2 – V2 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 23; V3 = 16; U3 = – 9
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 23 = - 8 X13: 20 – 0 – 16 = 4 X31: 16 + 9 – 10 = 15 X33: 24 + 9 – 16 = 17
Entra X12. Circuito de compensação.
Exercícios Propostos – Lista 6
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 60
40 – θ θ 40 10 + θ 30 – θ 60 100 10 10 50 40 60 O maior valor possível para θ é 30, A Nova solução é
10 30 40 40 60 100 10 10 50 40 60 . Coeficientes das variáveis básicas Cij – Ui - Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X12: 15 – U1 – V2 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 15; V3 = 16; U3 =-1
Coeficientes das variáveis não básicas.
X22: 25 – 2 – 15 = 8 X13: 20 – 0 – 16 = 4 X31: 16 + 1 – 10 = 7 X33: 24 + 1 – 16 = 9
A solução é ótima. O custo é C = 10 x10 + 30 x 15 + 40 x 12 + 60 x 18 + 10 x 14 = 2.250
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 61
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 2
Solução inicial pelo método de Vogel. Penalidade é a diferença entre os dois menores custos.
10 15 20 40 P1= 15 – 10= 5 P2= 5 P3 = 5 12 25 18 100 P1= 18 – 25=7 P2= 7 P3= 7 16 14 24 10 P1= 16 – 14=2 P2= 10 50 40 60 P1 = 12 – 10 = 2 P1= 15 – 14 = 1 P1 = 20 – 18 = 2 . P2= 15 – 14 = 1 P2 = 20 – 18 = 2 . P3= 10 P3= 2
Penalidade P1. Transporte na linha 2 (maior penalidade) e coluna 1 (menor custo). X21 = 50. Coluna 1 eliminada. Penalidade P2. Transporte na linha 3 (maior penalidade) e coluna 2 (menor custo). X32 = 10. Linha 3 eliminada. Penalidade P3. Transporte na linha 2 (maior penalidade) e coluna 3 (menor custo) . X23 = 50 Linha 2 eliminada. .
40 40/30 60/10 Observando o resultado, a solução está definida. X12= 30 e X13= 10
30 10 40 50 50 100 10 10 50 40 60 Otimização. Coeficientes das variáveis básicas Cij – Ui – Vj
X12: 15 – U1 – V2 = 0 X13: 20 – U1 – V3 = 0 X21: 12 – U2 – V1 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V2 = 15; V3 = 20; U2 = – 2; V1 = 14; U3 = – 1
Coeficientes das variáveis não básicas.
X11: 10 – 0 – 14 = – 4 X22: 25 +2 – 15 = 12 X31: 16 +1 – 14 = 3 X33: 24 +1 – 20 = 5
Entra X11. Circuito de compensação.
θ 30 10 – θ 40 50 – θ 50 + θ 100 10 10 50 40 60 O maior valor possível para θ é 10, A Nova solução é
10 30 40
Exercícios Propostos – Lista 6
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 62
40 60 100 10 10 50 40 60 . Coeficientes das variáveis básicas Cij – Ui - Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X12: 15 – U1 – V2 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 15; V3 = 16; U3 = – 1
Coeficientes das variáveis não básicas.
X13: 20 – 0 – 16 = 4 X22: 25 – 2 – 15 = 8 X31: 16 + 1 – 10 = 7 X33: 24 + 1 – 16 = 9
A solução é ótima. O custo é C = 10 x10 + 30 x 15 + 40 x 12 + 60 x 18 + 10 x 14 = 2.250
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 63
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 3
Devemos equilibrar o sistema adicionando uma linha (quarta linha), com custo de transporte zero para receber a diferença de 10 unidades entre origens e destino. Solução inicial pelo método do canto noroeste
100 100/0 A 50 30 80/30/0 20 20/0 10 10/0 100/0 50/0 60/30/10/0
Otimização. Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X22: 25 – U2 – V2 = 0 X23: 18 – U2 – V3 = 0
X33: 24 – U3 – V3 = 0 X43: 0 – U4 – V3 = 0.
O sistema apresenta 5 equações e 7 variáveis. Devemos criar um transporte auxiliar A em uma célula que não forme circuito com as outras variáveis básicas. Vamos optar por A21. A nova equação é: 12 – U2 – V1 =0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 23; V3 = 16; U3 = 8; U4 = – 16
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 23 = –8 X13: 20 – 0 – 16 = 4 X31: 16 – 8 – 10 = –2 X32: 14 – 8 – 23 = –17
X41: 0 + 16 – 10 = 6 X42: 0 + 16 – 23 = –7
Entra X32. Circuito de compensação.
100 100 A 50 – θ 30 + θ 80 θ 20 – θ 20 10 10 100 50 60 O maior valor possível para θ é 20, A Nova solução é
100 100 A 30 50 80 20 20 10 10 100 50 60 Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X22: 25 – U2 – V2 = 0
Exercícios Propostos – Lista 6
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 64
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0 X43: 0 – U4 – V3 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 23; V3 = 16; U3 = –9: U4 = –16
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 23 = –8 X13: 20 – 0 – 16 = 4 X31: 16 + 9 – 10 = 15 X33: 24 + 9 – 16 = 17
X41: 0 + 16 – 10 = 6 X42: 0 + 16 – 23 = –7
Entra X12. Circuito de compensação.
100 – θ θ 100 A + θ 30 – θ 50 80 20 20 10 10 100 50 60 O maior valor possível para θ é 30, A Nova solução é
70 30 100 30 50 80 20 20 10 10 100 50 60 . Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X12: 15 – U1 – V2 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0 X43: 0 – U4 – V3 = 0 Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 15; V3 = 16; U3 = –1; U4 = –16
Coeficientes das variáveis não básicas.
X22: 25 – 2 – 15 = 8 X13: 20 – 0 – 16 = 4 X31: 16 + 1 – 10 = 7 X33: 24 + 1 – 16 = 9
X41: 0 + 16 – 10 = 6 X42: 0 + 16 – 15 = 9
A solução é ótima. O custo é C = 70 x10 + 30 x 15 + 30 x 12 + 50 x 18 + 20 x 14 = 2.690,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 65
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 4
Devemos equilibrar o sistema adicionando uma linha (quarta linha), com custo de transporte zero para receber a diferença de 10 unidades entre origens e destino. Solução inicial pelo método de Vogel
10 15 20 100 P1=10 – 15=5 P2=5 P3=5 P3=20 – 15=5 12 25 18 80 P1=18 – 12=6 P2=6 16 14 24 20 P1=16 – 14=2 P2=2 P3=2 P3=24 – 14=10 0 0 0 10 P1=0 100 50 60 P1=12 – 10=2 P1=14 – 0=14 P1=18 – 0=18 P2=12 – 10=2 P2=15 – 14=1 P2=20 – 18=2 P3=16 – 10=6 P3=15 – 14=1 P3=24 – 20=4 . P4=15 – 14=1 P4=24 – 20=4
Resultado de P1: entra X43 (coluna de maior penalidade + linha de menor custo). X43 = 10. Linha 4 eliminada. Resultado de P2: entra X21 (linha de maior penalidade + coluna de menor custo). X21 = 80. Linha 2 eliminada. .Resultado de P3: entra X11 (linha de maior penalidade + coluna de menor custo). X11= 20. Coluna 1 eliminada. .Resultado de P4: entra X32 (linha de maior penalidade + coluna de menor custo). X32 = 20. Linha 3 eliminada. O quadro restante é:
100/80 50/30 60/50 Completando: X12 = 30 e X13 = 50. A solução encontrada é a seguinte.
20 30 50 100 80 80 20 20 10 10 100 50 60
Otimização. Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X12: 15 – U1 – V2 = 0 X13: 20 – U1 – V3 = 0
X21: 12 – U2 – V1 = 0 X32: 14 – U3 – V2 = 0. X43: 0 – U4 – V3
Fazendo U1 = 0 temos:
U1 = 0; V1 = 10; U2 = 2; V2 = 15; V3 = 20; U3 = – 1; U4 = – 20
Coeficientes das variáveis não básicas.
Exercícios Propostos – Lista 6
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 66
X22: 25 – 2 – 15 = 8 X23: 18 – 2 – 20 = – 4 X31: 16 + 1 – 10 = 7 X33: 24 + 1 – 20 = 5
X41: 0 + 20 – 10 = 10 X42: 0 + 20 – 15 = 5
Entra X23. Circuito de compensação.
20 + θ 30 50 – θ 100 80 – θ θ 80 20 20 10 10 100 50 60 O maior valor possível para θ é 50, A Nova solução é
70 30 100 30 50 80 20 20 10 10 100 50 60 Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X21: 12 – U2 – V1 = 0 X12: 15 – U1 – V2 = 0
X23: 18 – U2 – V3 = 0 X32: 14 – U3 – V2 = 0 X43: 0 – U4 – V3 = 0 Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 2; V2 = 15; V3 = 16; U3 = – 1; U4 = – 16
Coeficientes das variáveis não básicas.
X22: 25 – 2 – 15 = 8 X13: 20 – 0 – 16 = 4 X31: 16 + 1 – 10 = 7 X33: 24 + 1 – 16 = 9
X41: 0 + 16 – 10 = 6 X42: 0 + 16 – 15 = 9
A solução é ótima. O custo é C = 70 x10 + 30 x 15 + 30 x 12 + 50 x 18 + 20 x 14 = 2.690,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 67
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 5
Devemos equilibrar o sistema adicionando uma linha (quarta linha), com custo de transporte zero para receber a diferença de 20 unidades entre origens e destino. Solução inicial pelo método do canto noroeste
50 X 50/0 X 50 20 70/20/0 30 30/0 20 20/0 80/30/0 50/0 40/0
Otimização. Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X22: 25 – U2 – V2 = 0 X23: 18 – U2 – V3 = 0
X31: 16 – U3 – V1 = 0 X43: 0 – U4 – V3 = 0.
O sistema apresenta 5 equações e 7 variáveis. Devemos criar um transporte auxiliar A em uma célula que não forme circuito com as outras variáveis básicas. Vamos optar por A32. A nova equação é: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0 ; V1 = 10 ; U2 = 17 ; V2 = 8 ; V3 = 1 ; U3 = 6 ; U4 = – 1
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 8 = 7 X33: 24 – 6 – 1 = 17 X41: 0 +1 – 10 = – 9 X42: 0 +1 – 8= – 7
Entra X41. Circuito de compensação.
50 X 50 X 50 – θ 20 + θ 70 30 – θ A + θ 30 θ 20 – θ 20 80 50 40 O maior valor possível para θ é 20, A Nova solução é
50 X 50 X 30 40 70 10 20 30 20 20 80 50 40 Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X22: 25 – U2 – V2 = 0 X23: 18 – U2 – V3 = 0
X31: 16 – U3 – V1 = 0 X32: 14 – U3 – V2 = 0. X41: 0 – U4 – V1 = 0
Exercícios Propostos – Lista 6
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 68
Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 17 ; V2 = 8; V3 = 1 ; U3 = 6: U4 = – 10
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 8 = 7 X33: 24 – 6 – 1 = 17
X42: 0 + 10 – 8 = 2 X43: 0 + 10 – 1 = 9
A solução é ótima. X11 = 50; X22 = 30; X23 = 40; X31 = 10; X32 = 20
Custo = 50 x 10 + 30 x 25 + 40 x 18 + 10 x 16 + 20 x 14 = 2.410,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 69
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 6
Devemos equilibrar o sistema adicionando uma linha (quarta linha), com custo de transporte zero para receber a diferença de 20 unidades entre origens e destino. Solução inicial pelo método de Vogel
10 15 200 50 P1 = 15 – 10 = 5 P2 = 5 P3 = 5 200 25 18 70 P1 = 25 – 18 = 7 P2 = 7 P3 = 175 16 14 24 30 P3 = 16 – 14 = 2 P2 = 2 P3 = 2 0 0 0 20 P1 = 0 80 50 40 P1 = 10 – 0 = 10 P1 = 14 – 0 = 14 P1 = 18 – 0 = 18 P2 = 16 – 10 = 6 P2 = 15 – 14 = 1 P2 = 24 – 18 = 6 .P3 = 6 P2 = 1
Penalidade P1: transportar na coluna 3 (maior penalidade) e linha 4 (menor custo). X43 = 20. Linha 4 eliminada. Penalidade P2: transportar na linha 2 (maior penalidade) e coluna 3 (menor custo). X23 = 20. Coluna 3 eliminada. Penalidade P3: transportar na linha 2 (maior penalidade) e coluna 2 (menor custo). X22 = 50. Linha 2 e coluna 2 eliminadas. O quadro restante é o seguinte.
50 0 30 0 80 0 0 A solução está definida. X11 = 50; X31 = 30. O quadro com a solução é o seguinte.
50 50 50 20 70 30 A 30 20 20 80 50 40
Otimização. Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X22: 25 – U2 – V2 = 0 X23: 18 – U2 – V3 = 0
X31: 16 – U3 – V1 = 0 X43: 0 – U4 – V3 = 0.
O sistema apresenta 5 equações e 7 variáveis. Devemos criar um transporte auxiliar A em uma célula que não forme circuito com as outras variáveis básicas. Vamos optar por A32. A nova equação é: 14 – U3 – V2 = 0. Escolhendo o valor zero para U1, teremos:
U1 = 0 ; V1 = 10 ; U2 = 17 ; V2 = 8 ; V3 = 1 ; U3 = 6 ; U4 = – 1
Exercícios Propostos – Lista 6
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 70
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 8 = 7 X33: 24 – 6 – 1 = 17 X41: 0 +1 – 10 = – 9 X42: 0 +1 – 8 = – 7
Entra X41. Circuito de compensação.
50 X 50 X 50 – θ 20 + θ 70 30 – θ A + θ 30 θ 20 – θ 20 80 50 40 O maior valor possível para θ é 20, A Nova solução é
50 X 50 X 30 40 70 10 20 30 20 20 80 50 40 Coeficientes das variáveis básicas Cij – Ui – Vj
X11: 10 – U1 – V1 = 0 X22: 25 – U2 – V2 = 0 X23: 18 – U2 – V3 = 0
X31: 16 – U3 – V1 = 0 X32: 14 – U3 – V2 = 0. X41: 0 – U4 – V1 = 0
Escolhendo o valor zero para U1, teremos:
U1 = 0; V1 = 10; U2 = 17 ; V2 = 8; V3 = 1 ; U3 = 6: U4 = – 10
Coeficientes das variáveis não básicas.
X12: 15 – 0 – 8 = 7 X33: 24 – 6 – 1 = 17
X42: 0 + 10 – 8 = 2 X43: 0 + 10 – 1 = 9
A solução é ótima. X11 = 50; X22 = 30; X23 = 40; X31 = 10; X32 = 20
Custo = 50 x 10 + 30 x 25 + 40 x 18 + 10 x 16 + 20 x 14 = 2.410,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 71
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 7
Devemos criar um cliente auxiliar para receber o excedente dos depósitos. a. Solução inicial pelo método do canto noroeste
100 60 160/60/0 20 120 60 200/180/60/0 20 80 100/80/0 100/0 80/20/0 120/0 80/20/0 80 b. Solução melo método de Vogel P1 P2 P3 P4 P5
2,1 1,8 1,8 1,8 0 160 1,8 0 0 0 0 1,5 2,4 1,8 2,1 0 200 1,5 0,3 0,3 0,3 0,3 2,4 1,5 2,4 1,8 0 100 1,5 0,3 0,3 0,6 100 80 120 80 80 P1 = 0,6 P1 = 0,3 P1 = 0 P1 = 0 P1 = 0 P2 = 0,6 P2 = 0,3 P2 = 0 P2 = 0 . P3 = 0,3 P3 = 0 P3 = 0 . P4 = 0 P4 = 0 . P5 = 0 P5 = 0,3
Penalidade 1: transporte na linha 1 (maior penalidade) e coluna 5 (menor custo). X15 = 80. Coluna 5 eliminada. Penalidade 2: transporte na coluna 1 (maior penalidade) e linha 2 (menor custo). X21 = 100. Coluna 1 eliminada. Penalidade 3: transporte na linha 3 (maior penalidade) e coluna 2 (menor custo). X32 = 80. Coluna 2 eliminada. Penalidade 4: transporte na linha 3 (maior penalidade) e coluna 4 (menor custo). X34 = 20. Linha 3 eliminada. Pemalidade 5: transporte na coluna 4 (maior penalidade) e linha 1 (menor custo). X14 = 60. Coluna 4 eliminada.
Os transportes restantes estão definidos: X13 = 20 e X23 = 100.
20 60 80 160 100 100 200 80 20 100 100 80 120 80 80 c. Solução ótima a partir da inicial pelo canto noroeste.
Coeficientes das variáveis básicas. X11: 2,1 – U1 – V1 = 0 X12: 1,8 – U1 – V2 = 0 X22: 2,4 – U2 – V2 = 0 X23: 1,8 – U2 – V3 = 0 X24: 2,1 – U2 – V4 = 0 X34: 1,8 – U3 – V4 = 0 X35: 0 – U3 – V5 = 0
Exercícios Propostos – Lista 6
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 72
Fazendo U1 = 0, vem: V1 = 2,1 V2 = 1,8 U2 = 0,6 V3 = 1,2 U3 = 0,3
V4 = 1,5 V5 = – 0,3
Coeficientes das variáveis não básicas.
X13: 1,8 – 0 – 1,2 = 0,6 X14: 1,8 – 0 – 1,5 = 0,3 X15: 0 – 0 + 0,3 = 0,3 X21: 1,5 – 0,6 – 2,1 = – 1,2 X25: 0 – 0,6 + 0,3 = – 0,3 X31: 2,4 – 0,3 – 2,1 = 0 X32: 1,5 – 0,3 – 1,8 = – 0,6 X33: 2,4 – 0,3 – 1,2 = 0,9
Entra X21. Circuito de compensação.
100 – θ 60 + θ 160 θ 20 – θ 120 60 200 20 80 100 100 80 120 80 80 X21 entra com valor 20. A Nova solução é:
80 80 160 20 120 60 200 20 80 100 100 80 120 80 80 Coeficientes das variáveis básicas. X11: 2,1 – U1 – V1 = 0 X12: 1,8 – U1 – V2 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X24: 2,1 – U2 – V4 = 0 X34: 1,8 – U3 – V4 = 0 X35: 0 – U3 – V5 = 0.
Fazendo U1 = 0, vem: V1 = 2,1 U2 = – 0,6 V2 = 1,8 U3 = – 0,9 . V3 = 2,4 V4 = 2,7 V5 = 0,9
Coeficientes das variáveis não básicas.
X13: 1,8 – 0 – 2,4 = – 0,6 X14: 1,8 – 0 – 2,7 = – 0,9 X15: 0 – 0 – 0,9 = – 0,9 X22: 2,4 + 0,6 – 1,8 = 1,2 X25: 0 + 0,6 – 0,9 = – 0,3 X31: 2,4 + 0,9 – 2,1 = 1,2 X32: 1,5 + 0,9 – 1,8 = 0,6 X33: 2,4 + 0,9 – 2,4 = 0,9
Entra X14. Circuito de compensação.
80 – θ 80 θ 160 20 + θ 120 60 – θ 200 20 80 100 100 80 120 80 80 X14 entra com valor 60. Nova solução.
20 80 60 160 80 120 200 20 80 100 100 80 120 80 80 Coeficientes das variáveis básicas.
X11: 2,1 – U1 – V1 = 0 X12: 1,8 – U1 – V2 = 0 X14: 1,8 – U1 – V4 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X34: 1,8 – U3 – V4 = 0 X35: 0 – U3 – V5 = 0
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 73
Fazendo U1 = 0, vem: V1 = 2,1 U2 = – 0,6 V2 = 1,8 U3 = 0 V3 = 2,4 . V4 = 1,8 V5 = 0
Coeficientes das variáveis não básicas.
X13: 1,8 – 0 – 2,4 = – 0,6 X15: 0 – 0 – 0 = 0 X22: 2,4 + 0,6 – 1,8 = 1,2 X24: 2,1 + 0,6 – 1,8 = 0,9 X25: 0 + 0,6 – 0 = 0,6 X31: 2,4 – 0 – 2,1 = 0,3 X32: 1,5 – 0 – 1,8 = – 0,3 X33: 2,4 – 0 – 2,4 = 0
Entra X13. Circuito de compensação.
20 – θ 80 θ 60 160 80 + θ 120 – θ 200 20 80 100 100 80 120 80 80 X13 entra com valor 20. Nova solução.
80 20 60 160 100 100 200 20 80 100 100 80 120 80 80 Coeficientes das variáveis básicas.
X12: 1,8 – U1 – V2 = 0 X13: 1,8 – U1 – V3 = 0 X14: 1,8 – U1 – V4 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X34: 1,8 – U3 – V4 = 0 X35: 0 – U3 – V5 = 0
Fazendo U1 = 0, vem: U2 = 0 U3 = 0 V1 = 1,5 V2 = 1,8 V3 = 1,8 V4 = 1,8 V5 = 0
Coeficientes das variáveis não básicas.
X11: 2,1 – 0 – 1,5 = 0,6 X15: 0 – 0 – 0 = 0 X22: 2,4 – 0 – 1,8 = 0,6 X24: 2,1 – 0 – 1,8 = 0,3 X25: 0 – 0 – 0 = 0 X31: 2,4 – 0 – 1,5 = 0,9 X32: 1,5 – 0 – 1,8 = – 0,3 X33: 2,4 – 0 – 1,8 = 0,6
Entra X32. Circuito de compensação.
80 – θ 20 60 + θ 160 100 100 200 θ 20 – θ 80 100 100 80 120 80 80 X32 entra com valor 20. Nova solução.
60 20 80 160 100 100 200 20 80 100 100 80 120 80 80 Coeficientes das variáveis básicas.
X12: 1,8 – U1 – V2 = 0 X13: 1,8 – U1 – V3 = 0 X14: 1,8 – U1 – V4 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X32: 1,5 – U3 – V2 = 0 X35: 0 – U3 – V5 = 0
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 74
Fazendo U1 = 0, vem: U2 = 0 U3 = – 0,3 V1 = 1,5 V2 = 1,8 V3 = 1,8 . V4 = 1,8 V5 = 0,3
Coeficientes das variáveis não básicas.
X11: 2,1 – 0 – 1,5 = 0,6 X15: 0 – 0 – 0,3 = – 0,3 X22: 2,4 – 0 – 1,8 = 0,6 X24: 2,1 – 0 – 1,8 = 0,3 X25: 0 – 0 – 0,3 = – 0,3 X31: 2,4 + 0,3 – 1,5 = 1,2 X33: 2,4 + 0,3 – 1,8 = 0,9 X34: 1,8 + 0,3 – 1,8 = 0,3
Entra X25. Circuito de compensação.
60 – θ 20 + θ 80 160 100 100 – θ θ 200 20 + θ 80 – θ 100 100 80 120 80 80 X25 entra com valor 60. Nova solução.
80 80 160 100 40 60 200 80 20 100 100 80 120 80 80 Coeficientes das variáveis básicas.
X13: 1,8 – U1 – V3 = 0 X14: 1,8 – U1 – V4 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X25: 0 – U2 – V5 = 0 X32: 1,5 – U3 – V2 = 0 X35: 0 – U3 – V5 = 0
Fazendo U1 = 0, vem: U2 = 0 U3 = 0 V1 = 1,5 V2 = 1,5 V3 = 1,8 . V4 = 1,8 V5 = 0
Coeficientes das variáveis não básicas.
X11: 2,1 – 0 – 1,5 = 0,6 X12: 1,8 – 0 – 1,5 = 0,3 X15: 0 – 0 – 0 = 0 X22: 2,4 – 0 – 1,5 = 0,9 X24: 2,1 – 0 – 1,8 = 0,3 X31: 2,4 – 0 – 1,5 = 0,9 X33: 2,4 – 0 – 1,8 = 0,6 X34: 1,8 – 0 – 1,8 = 0
A solução é ótima. Custo = 100 x 1,5 + 80 x 1,8 + 80 x 1,8 + 40 x 1,8 + 80 x 1,5 = 630
Observe que pelo fato do coeficiente da variável X34 ser nulo, o problema tem mais de uma solução ótima. Colocando X34 na base, o cicuito de compensação fica assim.
80 + θ 80 – θ 160 100 40 – θ 60 + θ 200 80 θ 20 – θ 100 100 80 120 80 80 X34 pode entrar com valor 20, gerando a resposta ótima do texto.
100 60 160 100 20 80 200 80 20 100 100 80 120 80 80
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 75
d. solução do modelo a partir da inicial pelo método de Vogel.
20 60 80 160 100 100 200 80 20 100 100 80 120 80 80 Coeficientes das variáveis básicas.
X13: 1,8 – U1 – V3 = 0 X14: 1,8 – U1 – V4 = 0 X15 0 – U1 – V5 = 0 X21: 1,5 – U2 – V1 = 0 X23: 1,8 – U2 – V3 = 0 X32: 1,5 – U3 – V2 = 0 X34: 1,8 – U3 – V4 = 0
Fazendo U1 = 0 temos: U2 = 0 U3 = 0 V1 = 1,5 V2 = 1,5 V3 = 1,8 V4 = 1,8 V5 = 0
Coeficientes das variáveis não básicas.
X11: 2,1 – 0 – 1,5 = 0,6 X12: 1,8 – 0 – 1,5 = 0,3 X22: 2,4 – 0 – 1,5 = 0 X24: 2,1 – 0 – 1,8 = 0,3 X25: 0 – 0 – 0 = 0 X31: 2,4 – 0 – 1,5 = 0,9 X33: 2,4 – 0 – 1,8 = 0,6 X35: 0 – 0 – 0 = 0
A solução é ótima. Custo = 20 x 1,8 + 60 x 1,8 + 100 x 1,5 + 100 x 1,8 + 80 x 1,5 + 20 x 1,8 = 630
Como na solução anterior, o fato de variáveis não básicas comparecerem com coeficientes nulos, o problema apresenta outras soluções ótimas. Por exemplo, se a variável X25 entrar na base o circuito de compensação seria:
20 + θ 60 80 – θ 160 100 100 – θ θ 200 80 20 100 100 80 120 80 80 X25 entra com valor 80, gerando a solução ótima que aparece na resposta do texto.
100 60 160 100 20 80 200 80 20 100 100 80 120 80 80
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 76
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 8
Para transformar o modelo de transporte (de minimização) em um modelo de maximização devemos trabalhar com os complementos para um valor fixo da tabela de lucro. Minimizando esses complementos estaremos maximizando os lucros. Faremos os complementos para 12 (maior valor da tabela).
0 1,5 3 3 0 160 4,5 1,5 0 1,5 0 200 1,5 4,5 0 3 0 100 100 80 120 80 80 Vamos calcular a solução inicial pelo método de Vogel.
P1 P2 P3 P4 P5
0 1,5 3 3 0 160 0 1,5 1,5 – – 4,5 1,5 0 1,5 0 200 0 0 0 0 0 1,5 4,5 0 3 0 100 0 0 0 0 0 100 80 120 80 80 P1 = 1,5 P1 = 0 P1 = 0 P1 = 1,5 P1 = 0 . P2 = 0 P2 = 0 P2 = 1,5 P2 = 0 . P3 = 0 P3 = 0 P3 = 0 . P4 = 3 P4 = 0 P4 = 0 . P5 = 0 P5 = 0
Penalidade P1: transportar na coluna 1 (maior penalidade) e linha 1 (menor custo). X11 = 100. Coluna 1 eliminada. Penalidade P2: transportar na coluna 4 (maior penalidade) e linha 2 (menor custo). X24 = 80. Coluna 4 eliminada. Penalidade P3: transportar na linha 1 (maior penalidade) e coluna 5 (menor custo). X15 = 60. Linha 1 eliminada. Penalidade P4: transportar na coluna 2 (maior penalidade) e linha 2 (menor custo). X22 = 80. Coluna 2 eliminada. Penalidade P5: transportar na linha 2 (maior penalidade) e coluna 3 (menor custo). X23 = 40. Linha 2 eliminada. Os transportes restantes ficam definidos. X33 = 80 e X35 = 20
80 20 100 120/80 80/20 Quadro com a solução inicial
100 60 160/60/0 80 40 80 200/120/40/0 80 20 100/20/0 100/0 80/0 120/80/0 80/0 80/20/0
Exercícios Propostos – Lista 6
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 77
Cálculo da solução ótima.
Coeficientes das variáveis básicas.
X11: 0 – U1 – V1 = 0 X15: 0 – U1 – V5 = 0 X22: 1,5 – U2 – V2 = 0 X23: 0 – U2 – V3 = 0 X24: 1,5 – U2 – V4 = 0 X33: 0 – U3 – V3 = 0 X35: 0 – U3 – V5 = 0.
Fazendo U1 = 0, teremos: U2 = 0 U3 = 0 V1 = 0 V2 = 1,5 V3 = 0 V4 = 1,5 . V5 = 0 Coeficientes das variáveis não básicas.
X12: 1,5 – 0 – 1,5 = 0 X13: 3 – 0 – 0 = 3 X14: 3 – 0 – 1,5 = 1,5 X21: 4,5 – 0 – 0 = 4,5 X25: 0 – 0 – 0 = 0 X31: 1,5 – 0 – 0 = 1,5 X32: 4,5 – 0 – 1,5 = 3 X34: 3 – 0 – 1,5 = 0
A solução é ótima. Lucro = 100 x 12 + 80 x 10,5 + 40 x 12 + 80 x 10,5 + 80 x 12 = 4.320
Observe que algumas variáveis não básicas apresentam coeficiente zero. Isto significa que podem entrar na base gerando outra solução ótima como a apresentada no texto. Por exemplo, se X12 entrar com valor 60, a resposta ótima é a mencionada no texto.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 78
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 9
Para transformar o modelo de transporte (de minimização) em um modelo de maximização devemos trabalhar com os complementos para um valor fixo da tabela de lucro. Minimizando esses complementos estaremos maximizando os lucros. Faremos os complementos para 400 (maior valor da tabela). Devemos criar um quinto destino (40 unidades com lucro zero) para receber a diferença entre a oferta e a demanda e equilibrar o sistema.
A solução inicial será calculada usando o método de Vogel.
P1 P2 P3 P4
240 190 200 270 400 360 10 10 40 40 320 10 160 90 400 440 80 80 70 160
0 150 310 210 400 200 150 – 240 200 340 180 40
P1 240 140 40 120 0 P2 80 180 40 180 0 P3 80 – 40 180 0 P4 80 40 – 0
Penalidade P1: transportar na coluna 1 (maior penalidade) e linha 3 (menor custo). X31 = 200. Linha 3 eliminada. Penalidade P2: transportar na coluna 2 (maior penalidade) e linha 2 (menor custo). X22 = 200. Coluna 2 eliminada. Penalidade P3: transportar na coluna 4 (maior penalidade) e linha 2 (menor custo). X24= 180. Coluna 4 eliminada. Penalidade P4: transportar na linha 2 (maior penalidade) e coluna 3 (menor custo). X23 = 60 Linha 2 eliminada.
Os outros transportes estão definidos. X11 = 40 X13 = 280 X15 = 40
40 280 40 360 200 60 180 440/240/60/0 200 200/0 240/40 200/0 340/280 180/0 40 Cálculo da solução ótima. Coeficientes das variáveis básicas.
X11: 240 – U1 – V1 = 0 X13: 200 – U1 – V3 = 0 X15: 400 – U1 – V5 = 0 X22: 10 – U2 – V2 = 0 X23: 160 – U2 – V3 = 0 X24: 90 – U2 – V4 = 0 X31: 0 – U3 – V1 = 0
Fazendo U1 = 0, vem: V1 = 240 V3 = 200 V5 = 400 U2 = – 40 V4 = 130 . U3 = – 240 V2 = 50
Exercícios Propostos – Lista 6
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 79
Coeficientes das variáveis não básicas.
X12: 190 – 0 – 50 = 140 X14: 270 – 0 – 130 = 140 X21: 320 + 40 – 240 = 120 X25: 400 + 40 – 400 = 40 X32: 150 + 240 – 50 = 340 X33: 310 + 240 – 200 = 350 X34: 210 + 240 – 130 = 320 X35: 400 + 240 – 400 = 240 .
A solução é ótima.
Lucro = 40 x 160 + 280 x 200 + 200 x 390 + 60 x 240 + 180 x 310 + 200 x 400 =290.600
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 80
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 10
Devemos calcular a tabela de lucro unitário para cada produto e cada instalação. Além disso, devemos criar uma demanda com capacidade de 300 unidades e lucro zero para equilibrar o sistema.
12 21 20 0 800 11 19 20 0 1.000
8 15 19 0 1.200 1.000 900 800 300
Para transformar o problema para o objetivo de minimização, vamos trabalhar com os complementos dos lucros unitários para um número fixo (no caso 21, o maior da tabela). Assim, minimizando os complementos estaremos maximizando os lucros.
9 0 1 21 800 10 2 1 21 1.000 13 6 2 21 1.200
1.000 900 800 300 A partir desse quadro, a solução inicial é calculada pelo método de Vogel.
P1 P2 P3 P4
9 0 1 21 800 1 9 – – 10 2 1 21 1.000 1 8 8 11 13 6 2 21 1.200 4 7 7 8
1.000 900 800 300 P1 1 2 0 0 P2 1 2 – 0 P3 3 4 – 0 P4 3 4 – 0
Penalidade P1: transporte na linha 3 (maior penalidade) e coluna 3 (menor custo). X33 = 800. Coluna 3 eliminada. Penalidade P2: transporte na linha 1 (maior penalidade) e coluna 2 (menor custo). X12 = 800 Linha 1 eliminada. Penalidade P3: transportar na linha 2 (maior penalidade) e coluna 2 (menor custo). X22 = 100. Coluna 2 eliminada. Penalidade P4: transportar na linha 2 (maior penalidade) e coluna 1 (menor custo). X21=900. Linha 2 eliminada.
Os outros transportes ficam definidos pelos anteriores. X31 = 100 e X34 = 300
Solução inicial
800 800 900 100 1.000 100 800 300 1.200 1.000 900 800 300
Exercícios Propostos – Lista 6
Exercício 10
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 81
Coeficientes das variáveis básicas.
X12: 0 – U1 – V2 = 0 X21: 10 – U2 – V1 = 0 X22: 2 – U2 – V2 = 0 X31: 13 – U3 – V1 = 0 X33: 2 – U3 – V3 = 0 X34: 21 – U3 – V4 = 0
Fazendo U1 = 0, vem: U2 = 2 U3 = 5 V1 = 8 V2 = 0 V3 = – 3 V4 = 16
Coeficientes das variáveis não básicas.
X11: 9 – 0 – 8 = 1 X13: 1 - 0 + 3 = 4 X14: 21 – 0 – 16 = 5 X23: 1 – 2 + 3 = 2 X24: 21 – 2 – 16 = 3 X32: 6 – 5 – 0 = 1
A solução é ótima.
Lucro = 900 x 11 + 100 x 8 + 800 x 21 + 100 x 19 + 800 x 19 = 44.600,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 82
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 11
Nas células onde o transporte não é possível, vamos colocar um custo de transporte unitário M (número muito maior do que os outros custos, para impedir o transporte nesta célula)
10 12 M 12 12 14 15 18 6 8 10 30 10 20 30 Solução pelo método do canto noroeste.
10 2 12/2/0 18 18/0 A 30 30/0 10/0 20/18/0 30/0 O problema apresenta 6 variáveis e quatro equações. Devemos acrescentar um transporte auxiliar A para construir mais uma equação. O transporte auxiliar A deve ficar em célula que não forme circuito com os já existentes. Escolhemos A31.
Coeficientes das variáveis básicas.
X11: 10 – U1 – V1 = 0 X31: 6 – U3 – V1 = 0 X12: 12 – U1 – V2 = 0 X22: 14 – U2 – V2 = 0 X33: 10 – U3 – V3 = 0
Fazendo U1 = 0, vem: U2 = 2 U3 = – 4 V1 = 10 V2 = 12 V3 = 14
Coeficientes das variáveis não básicas.
X13: M – 0 – 14 = M – 14 X21: 12 – 2 – 10 = 0 X23: 15 – 2 – 14 = – 1 X32: 8 + 4 – 12 = 0
Entra X23. Circuito de compensação.
10 – θ 2 + θ 12 18 – θ θ 18 A + θ 30 – θ 30 10 20 30 X23 entra com valor 10. Nova solução.
12 12 8 10 18 10 20 30 10 20 30 Coeficientes das variáveis básicas.
X31: 6 – U3 – V1 = 0 X12: 12 – U1 – V2 = 0 X22: 14 – U2 – V2 = 0 X23: 15 – U2 – V3 = 0 X33: 10 – U3 – V3 = 0
Exercícios Propostos – Lista 6
Exercício 11
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 83
Fazendo U1 = 0, Vem: U2 = 2 U3 = – 3 V1 = 9 V2 = 12 V3 = 13
Coeficientes das variáveis não básicas.
X11: 10 – 0 – 3 = 7 X21: 12 – 2 – 9 = 1 X32: 8 + 3 – 12 = – 1 X13: M + 0 + 3 = M + 3
Entra X32. Circuito de compensação.
12 12 8 – θ 10 + θ 18 10 θ 20 – θ 30 10 20 30 X32 entra com valor 8. Nova solução.
12 12 18 18 10 8 12 30 10 20 30 Coeficientes das variáveis básicas.
X31: 6 – U3 – V1 = 0 X12: 12 – U1 – V2 = 0 X32: 8 – U3 – V2 = 0 X23: 15 – U2 – V3 = 0 X33: 10 – U3 – V3 = 0
Fazendo U1 = 0, vem : U2 = 1 U3 = – 4 V1 = 10 V2 = 12 V3 = 14
Coeficientes das variáveis não básicas.
X11: 10 – 0 – 10 = 0 X21: 12 – 1 – 10 = 1 X22: 14 – 1 – 12 = 1 X13: M – 0 – 14 = M – 14
A solução é ótima. Custo = 10 x 6 + 12 x 12 + 8 x 8 + 18 x 15 + 12 x 10 = 658,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 84
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 12
Nas células onde não deve haver transporte, colocamos um custo unitário M, muito maior que os outros custos, evitando desta forma, o transporte nestas células. Vamos criar um ponto de venda auxiliar para receber a diferença 140 entre as disponibilidades e as necessidades. O custo do transporte nesta coluna é zero. Cálculo da solução inicial pelo método de Vogel. P1 P2 P3 P4 P5 P6
16 14 12 100 16 0 170 12 2 2 2 2 12 4 14 8 8 0 60 4 0 4 4 –
8 6 100 14 10 0 90 6 2 2 4 4 15 69 36 18 42 140
P1 4 2 2 6 2 0 P2 4 2 2 6 2 – P3 4 2 2 – 2 P4 – 2 2 – 2 P5 – 8 88 – 6
Penalidade P1: transportar na linha 1 (maior penalidade) e coluna 6 (menor custo). X16 = 140. Coluna 6 eliminada. Penalidade P2: transportar na coluna 4 (maior penalidade) e linha 2 (menor custo). X24 = 18. Coluna 4 eliminada. Penalidade P3: transportar na coluna 1 (maior penalidade) e linha 3 (menor custo). X31 = 15. Coluna 1 eliminada. Penalidade P4: transportar na linha 2 (maior penalidade) e coluna 2 (menor custo). X22 = 42. Linha 2 eliminada. Penalidade P5: transportar na coluna 3 (maior penalidade) e linha 1 (menor custo). X13 = 30. Linha 1 eliminada. Quadro da solução inicial.
30 140 170/30/0 42 18 60/42/0 15 27 6 42 90/75 15/0 69/27 36/6 18/0 42 140/0 Cálculo da solução ótima. Coeficientes das variáveis básicas.
X13: 12 – U1 – V3 = 0 X16: 0 – U1 – V6 = 0 X22: 4 – U2 – V2 = 0 X24: 8 – U2 – V4 = 0 X31: 8 – U3 – V1 = 0 X32: 6 – U3 – V2= 0 X33: 88 – U3 – V3 = 0 X35: 10 – U3 – V5 = 0
Fazendo U1 = 0, vem: U2 = 74 U3 = 76 V1 = – 68 V2 = – 70 V3 = 12 V4 = – 66 V5 = – 66 V6 = 0
Coeficientes das variáveis não básicas.
X11: 16 – 0 + 68 = 84 X12: 14 – 0 + 70 = 84 X14: 100 – 0 + 66 = 166 X21: 12 – 74 + 68 = 6 X23: 14 – 74 – 12 = – 72 X25: 8 – 74 + 66 = 0 X26: 0 – 74 – 0 = – 74 X34: 14 – 76 + 66 = 4 X36: 0 – 76 – 0 =1 – 76
Exercícios Propostos – Lista 6
Exercício 12
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 85
Entra a variável X36. Circuito de compensação.
30 + θ 140 – θ 170 42 18 60 15 27 6 – θ 42 θ 90 15 69 36 18 42 140 X36 entra com valor 6. Nova solução.
36 134 170 42 18 60 15 27 42 6 90 15 69 36 18 42 140 Coeficientes das variáveis básicas.
X13: 12 – U1 – V3 = 0 X16: 0 – U1 – V6 = 0 X22: 4 – U2 – V2 = 0 X24: 8 – U2 – V4 = 0 X31: 8 – U3 – V1 = 0 X32: 6 – U3 – V2 = 0 X35: 10 – U3 – V5 = 0 X36: 0 – U3 – V6 = 0
Fazendo U1 = 0, vem: U2 = – 2 U3 = 0 V1 = 8 V2 = 6 V3 = 12 V4 = 10 V5 = 10 V6 = 0
Coeficientes das variáveis não básicas.
X11: 16 – 0 – 8 = 8 X12: 14 – 0 – 6 = 8 X14: 100 – 0 – 10 = 90 X15: 16 – 0 – 10 = 6 X21: 12 + 2 – 8 = 6 X23: 14 + 2 – 12 = 4 X25: 8 + 2 – 10 = 0 X33: 100 – 0 – 12 = 88 X34: 14 – 0 – 10 = 4
A solução é ótima. Custo = 36 x 12 + 42 x 4 + 18 x 8 + 15 x 8 + 27 x 6 + 42 x 10 = 1.446,00
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 86
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 13
a. Plano de distribuição com o menor custo possível. Solução inicial peli método de Vogel
P1 P2
410 418 416 170 6 6 392 400 394 150 2 2 375 372 375 200 3 – 200 200 120
P1 17 28 19 P2 17 – 22
Penalidade P1: transportar na coluna 2 (maior penalidade) e linha 3 (menor custo). X32 = 200. Coluna 2 e linha 3 eliminadas. Penalidade P2: transportar na coluna 3 (maior penalidade) e linha 2 (menor custo). X23 = 120. Coluna 3 eliminada. Quadro da solução inicial.
170 170 30 120 150/30 200 A 200/0 200 200/0 120/0 Cálculo da solução ótima. Coeficientes das variáveis básicas. O sistema vai apresentar 4 equações e 6 variáveis. Devemos criar uma variável básica auxiliar A, que não forme circuito com as já existentes. Escolhemos A33.
X11: 410 – U1 – V1 = 0 X21: 392 – U2 – V1 = 0 X23: 394 – U2 – V3 = 0 X32: 372 – U3 – V2 = 0 X33: 375 – U3 – V3 = 0
Fazendo U1 = 0, vem: U2 = –18 U3 = –37 V1 = 410 V2 = 409 V3 = 412
Coeficiente das variáveis não básicas.
X12: 418 – 0 – 409 = 9 X13: 416 – 0 –412 = 4 X22: 400 + 18 – 409 = 9 X31: 375 + 37 – 410 = 2
A solução é ótima. Custo = 170 x 410 + 30 x 392 + 200 x 372 + 120 x 394 = 203.140,00
b. Quadro de lucros (para cada célula: Preço de venda – preço de custo – custo de transporte)
90 102 94 170 108 120 116 150 125 148 135 200 200 200 120
Exercícios Propostos – Lista 6
Exercício 13
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 87
Para maximizar o lucro devemos minimizar os complementos dos lucros para um valor fixo. No caso escolhemos o valor 148, o maior da tabela.
Solução inicial pelo método de Vogel. P1 P2
58 46 54 170 8 4 40 28 32 150 4 12 23 0 13 200 13 – 200 200 120
P1 17 28 19 P2 18 – 22
Penalidade P1: transportar na coluna 2 (maior penalidade) e linha 3 (menor custo). X32 = 200. Coluna 2 e linha 3 eliminadas. Penalidade P2: transportar na coluna 3(maior penalidade) e linha 2 (menor custo) X23 = 120. Coluna 3 eliminada.
Quadro da solução inicial.
170 A 170 30 120 150/30 200 200/0 200 200/0 120/0 Cálculo da solução ótima. O sistema vai apresentar 4 equações e 6 variáveis. Devemos criar uma variável básica auxiliar A, que não forme circuito com as já existentes. Escolhemos A12.
X11: 58 – U1 – V1 = 0 X12: 46 – U1 – V2 = 0 X21: 40 – U2 – V1 = 0 X23: 32 – U2 – V3 = 0 X32: 0 – U3 – V2 = 0
Fazendo U1 = 0, vem: U2 = – 18 U3 = – 46 V1 = 58 V2 = 46 V3 = 50
Coeficientes das variáveis não básicas. X13: 54 – 0 – 50 = 4 X22: 28 + 18 – 46 = 0 X31: 23 + 46 – 58 = 11 X33: 13 + 46 – 50 = 9
A solução é ótima. Lucro = 170 x 90 + 30 x 108 + 120 x 116 + 200 x 148 = 62.060
c. Quadro de receitas.
500 520 510 170 500 520 510 150 500 520 510 200 200 200 120 Para maximizar o lucro devemos minimizar os complementos dos lucros para um valor fixo. No caso escolhemos o valor 520, o maior da tabela.
20 0 10 170 20 0 10 150 20 0 10 200 200 200 120
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
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 90
X12: 300 – 0 – 200 = 100 X13: 500 – 0 – 230 = 270 X14: 400 – 0 – 360 = 40 X16: 300 – 0 – 280 = 20 X23:200 + 100 – 230 = 70 X24: 300 + 100 – 360 = 40 X25: 150 + 100 – 250 = 0 X31: 120 + 180 – 200 = 100 X32: 200 + 180 – 250 = 130 X35:220 +1 80 – 250 = 150
A solução é ótima. Distância percorrida pelos lixeiros
D = 5 x 200 + 5 x 250 + 5 x 150 + 5 x 180 + 5 x 50 + 5 x 180 = 5.050
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 91
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 6 Ex 15
Quadro de transportes. Devemos criar um destino para receber o excesso de disponibilidades das transportadoras e com isso, equilibrar o sistema.
100 120 105 90 105 110 0 30 80 100 110 100 100 110 0 40 90 105 90 100 80 105 0 25
120 130 110 100 95 105 0 20 20 12 15 10 18 25 15
Cálculo da solução inicial pelo método de Vogel. P1 P2 P3 P4 P5 P6 P7
100 120 105 90 105 110 0 30 90 10 15 0 5 5 5 80 100 110 100 100 110 0 40 80 20 0 0 0 0 10 90 105 90 100 80 105 0 25 80 10 10 10 25 – –
120 130 110 100 95 105 0 20 95 5 5 10 10 10 10 20 12 15 10 18 25 15
P1 10 5 15 0 15 0 0 P2 10 5 15 0 15 0 – P3 – 5 15 0 15 0 – P4 – 5 15 – 15 0 – P5 – 5 – – 15 0 – P6 – 20 – – 5 5 – P7 – – – – 5 5
Penalidade P1: transportar na linha 1 (maior penalidade) e coluna 7 (menor custo). X17 = 15. Coluna 7 eliminada. Penalidade P2: transportar na linha 2 (maior penalidade) e coluna 1 (menor custo). X21 = 20. Coluna 1 eliminada. Penalidade P3: transportar na linha 1 (maior penalidade) e coluna 4 (menor custo). X14 = 11. Coluna 7 eliminada. Penalidade P4: transportar na coluna 3 (maior penalidade) e linha 3 (menor custo). X33 = 15. Coluna 3 eliminada. Penalidade P5: transportar na linha 3 (maior penalidade) e coluna 5 (menor custo). X35 = 10. Linha 3 eliminada. Penalidade P6: transportar na coluna 2 (maior penalidade) e linha 2 (menor custo). X22 = 12. Coluna 2 eliminada. Penalidade P7: transportar na linha 4 (maior penalidade) e coluna 5 (menor custo). X45 = 8. Coluna 5 eliminada.
Quadro da solução inicial
10 5 15 30/15/5 20 12 8 40/20/8 15 10 25/10/0 8 12 20/12 20/0 12/0 15/0 10/0 18/8/0 25 15/0
Exercícios Propostos – Lista 6
Exercício 15
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 92
Cálculo da solução ótima. Coeficientes das variáveis básicas.
X14: 90 – U1 – V4 = 0 X16: 110 – U1 – V6 = 0 X17: 0 – U1 – V7 = 0 X21: 80 – U2 – V1 = 0 X22: 100 – U2 – V2 = 0 X26: 110 – U2 – V6 = 0 X33: 90 – U3 – V3 = 0 X35: 80 – U3 – V5 = 0 X45: 95 – U4 – V5 = 0 X46: 105 – U4 – V6 = 0
Fazendo U1 = 0, vem: U2 = 0 U3 = – 20 U4 = – 5 V1 = 80 V2 = 100 V3 = 110 V4 = 90 V5 = 100 V6 = 110 V7 = 0
Coeficientes das variáveis não básicas.
X11: 100 – 0 – 80 = 20 X12: 120 – 0 – 100 = 20 X13: 105 – 0 – 110 = – 5 X15: 105 – 0 – 100 = 5 X23: 110 – 0 – 110 = 0 X24: 100 – 0 – 90 = 10 X25: 100 – 0 – 100 = 0 X27: 0 – 0 – 0 = 0 X31: 90 + 20 – 80 = 30 X32: 105 + 20 – 100 = 25 X34: 100 + 20 – 90 = 30 X36: 105 + 20 – 110 = 15 X37: 0 +20 – 0 = 20 X41: 120 + 5 – 80 = 45 X42: 130 + 5 – 100 = 35 X43: 110 + 5 – 110 = 5 X44: 100 + 5 – 90 = 15 X47: 0 + 5 – 0 = 5
Entra X13. Circuito de compensação.
θ 10 5 – θ 15 30 20 12 8 40 15 – θ 10 + θ 25 8 – θ 12 + θ 20 20 12 15 10 18 25 15
X13 entra com valor 5. Nova solução.
5 10 15 30 20 12 8 40 10 15 25 3 17 20 20 12 15 10 18 25 15 Coeficientes das variáveis básicas.
X13: 105 – U1 – V3 = 0 X14: 90 – U1 – V4 = 0 X17: 0 – U1 – V7 = 0 X21: 80 – U2 – V1 = 0 X22: 100 – U2 – V2 = 0 X26: 110 – U2 – V6 = 0 X33: 90 – U3 – V3 = 0 X35: 80 – U3 – V5 = 0 X45: 95 – U4 – V5 = 0 X46: 105 – U4 – V6 = 0
Fazendo U1 = 0, vem: U2 = 5 U3 = – 15 U4 = 0 V1 = 75 V2 = 95 V3 = 105 V4 = 90 V5 = 95 V6 = 105 V7 = 0
Coeficientes das variáveis não básicas.
X11: 100 – 0 – 75 = 25 X12: 120 – 0 – 95 = 25 X15: 105 – 0 – 95 = 10 X16: 110 – 0 – 105 = 5 X23: 110 – 5 – 105 = 0 X24: 100 – 5 – 90 = 5 X25: 100 – 5 – 95 = 0 X27: 0 – 5 – 0 = – 5 X31: 90 + 15 – 75 = 30 X32: 105 + 15 – 95 = 25 X34: 100 + 15 – 90 = 25 X36: 105 + 15 – 105 = 15 X41: 120 – 0 – 75 = 45 X42: 130 – 0 – 95 = 35 X43: 110 – 0 – 105 = 5 X44: 95 – 0 – 90 = 5 X47: 0 – 0 – 0 = 0
Entra X27. Circuito de compensação.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 93
5 + θ 10 15 – θ 30 20 12 8 – θ θ 40 10 – θ 15+θ 25 3 – θ 17 + θ 20 20 12 15 10 18 25 15 X27 entra com valor 3. Nova solução.
8 10 12 30 20 12 5 3 40 7 18 25 20 20 20 12 15 10 18 25 15 Coeficientes das variáveis básicas.
X13: 105 – U1 – V3 = 0 X14: 90 – U1 – V4 = 0 X17: 0 – U1 – V7 = 0 X21: 80 – U2 – V1 = 0 X22: 100 – U2 – V2 = 0 X26: 110 – U2 – V6 = 0 X27: 0 – U2 – V7 = 0 X33: 90 – U3 – V3 = 0 X35: 80 – U3 – V5 = 0 X46: 105 – U4 – V6 = 0
Fazendo U1 = 0, vem: U2 = 0 U3 = – 15 U4 = – 5 V1 = 80 V2 = 100 V3 = 105 V4 = 90 V5 = 95 V6 = 110 V7 = 0
Coeficientes das variáveis não básicas.
X11: 100 – 0 – 80 = 20 X12: 120 – 0 – 100 = 20 X15: 105 – 0 – 95 = 10 X16: 110 – 0 – 110 = 0 X23: 110 – 0 – 105 = 5 X24: 100 – 0 – 90 = 10 X25: 100 – 0 – 95 = 5 X31: 90 + 15 – 80 = 25 X32: 105 + 15 – 100 = 20 X34: 100 + 15 – 90 = 25 X36: 105 + 15 – 110 = 10 X37: 0 + 15 – 0 = 15 X41: 120 + 5 – 80 = 45 X42: 130 + 5 – 100 = 35 X43: 110 + 5 – 105 = 0 X44: 100 + 5 – 90 = 15 X45: 95 + 5 – 95 = 5 X47: 0 + 5 – 0 = 5
A solução é ótima.
Custo = 8 x 105 + 10 x 90 + 20 x 80 + 12 x 100 + 5 x 110 + 7 x 90 + 18 x 80 + 20 x 105 = 9.260
Observe que como X16 e de X46 apresentam coeficiente zero, o problrma admite outras soluções ótimas.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 94
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 1
Subtrair de cada linha o seu menor valor
10 23 8 9 – 8 4 5 6 7 – 4
12 10 10 8 – 8 6 4 9 7 – 4
A designação está completa: L1 – C3; L2 – C1; L3 – C4; L4 – C2.
Custo = 8 + 4 + 8 + 4 = 24
2 15 0 1 0 1 2 3 4 2 2 0 2 0 5 3
Exercícios Propostos – Lista 7
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 95
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 2
Devemos adicionar uma origem com custo zero, para equilibrar o sistema.A seguir, subtraímos de cada linha o seu menor valor.
6 8 10 9 – 6 4 3 6 5 – 3 7 9 12 6 – 6 0 0 0 0 – 0
0 2 4 3 1 0 3 2 1 3 6 0 0 0 0 0
A designação está completa. L4 – C3 (coluna com apenas um zero); L1 – C1; L2 – C2; L3 – C4.
Custo = 6 + 3 + 6 + 0 = 15
Exercícios Propostos – Lista 7
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 96
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 3
Devemos acrescentar um destino com custo zero para equilibrar o sistema. Na célula onde não é possível a designação, vamos colocar um custo alto em relação aos custos da tabela, 100, por exemplo. A seguir, (1)subtrair de cada linha o seu menor elemento; (2) . Subtrair de cada coluna o seu menor elemento.
(1) (2)
6 100 8 0 4 9 3 0 5 6 4 0 8 10 12 0
(3) Designar, D, nos zeros, priorizando linhas ou colunas com apenas um zero. A designação não se completa. (4) Cobrir os zeros com o menor número de linhas possível: L2;L3 e C4. (5)
2 94 5 D D 3 0 0 1 D 1 0 4 4 9 0
Subtrair o menor número não coberto (no caso o número 2), compensando nas linhas e colunas com zeros.
0 92 3 0 0 3 0 2 1 0 1 2 2 2 7 0
Designar, D, nos zeros, priorizando linhas ou colunas com apenas um zero.
D 92 3 0 0 3 D 2 1 D 1 2 2 2 7 D
A designação está completa.
L 1 – C 1 L 2 – C 3 L 3 – C 2 L 4 – C 4 Custo = 6 + 3 + 6 +0 = 15
2 94 5 0 0 3 0 0 1 0 1 0 4 4 9 0
Exercícios Propostos – Lista 7
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 97
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 4
1. Subtrair de cada linha o seu menor valor.
0 20 30 40 10 0 50 20 10 0 20 30 10 10 40 0
2. Subrair de cada coluna o s eu menor valor.
0 20 10 40 10 0 30 20 20 0 0 30 10 10 20 0
3. Designar (D) nos zeros, priorizando linhas e colunas com apenas um zero.
D 20 10 40 10 D 30 20 20 0 D 30 10 10 20 D
A designação está completa.
L 1 – C 1 L 2 – C2 L 3 – C3 L 4 – C 4 Custo = 100 + 70 + 100 + 80 = 350
Exercícios Propostos – Lista 7
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 98
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 5
Na célula correspondente ao depósito 1 e local 3, vamos colocar um custo alto (no caso, 500) para impedir o transporte nesta célula. A seguir:
1. Subtrair de cada linha o seu menor valor.
0 20 400 40 10 0 50 20 20 0 20 30 10 10 40 0
2. Subrair de cada coluna o s eu menor valor.
0 20 380 40 10 0 30 20 20 0 0 30 10 10 20 0
3. Designar (D) nos zeros, priorizando linhas e colunas com apenas um zero.
D 20 10 40 10 D 30 20 20 0 D 30 10 10 20 D
A designação está completa.
L 1 – C 1 L 2 – C2 L 3 – C3 L 4 – C 4 Custo = 100 + 70 + 100 + 80 = 350
Exercícios Propostos – Lista 7
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 99
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 6
Temos que criar um equipamento E 4 com custo de manuseio de materiais zero para equilibrar o sistema. A seguir:
1. Subtrair de cada linha o seu menor valor.
6 0 4 2 2 0 5 6 0 2 3 4 0 0 0 0 2. Subrair de cada coluna o s eu menor valor. No caso, nada se modifica.
3. Designar (D) nos zeros, priorizando linhas e colunas com apenas um zero.
6 D 4 2 2 0 5 6 D 2 3 4 0 0 0 D A designação não está completa.
5. Vamos cobrir os zeros com o menor número de linhas possível. L 4; C 2; C 1. Vamos subtrair o menor dos números não cobertos da tabele, e compensar nas linhas e colunas cobertas. No caso o menor número não coberto é 2.
6 0 2 0 2 0 3 4 0 2 1 2 2 2 0 D 6. Designar (D) nos zeros, priorizando linhas e colunas com apenas um zero.
6 0 2 D 2 D 3 4 D 2 1 2 2 2 D 0 A designação está completa.
L 1 – C 4; L 2 – C 2; L 3 – C 1; L 4 – C 3
Custo = 6 + 4 + 5 + 0 = 15
Exercícios Propostos – Lista 7
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 100
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 7
Temos que criar um equipamento E 4 com custo de manuseio de materiais zero para equilibrar o sistema e atribuir um custo elevado para o transporte na célula X 12 (no caso 20). A seguir:
1. Subtrair de cada linha o seu menor valor.
4 14 2 0 2 0 5 6 0 2 3 4 0 0 0 0 2. Subrair de cada coluna o s eu menor valor. No caso, nada se modifica.
3. Designar (D) nos zeros, priorizando linhas e colunas com apenas um zero.
4 14 2 D 2 D 5 6 D 2 3 4 0 0 D 0 A designação está completa.
L 1 – C 4; L 2 – C 2; L 3 – C 1; L 4 – C 3
Custo = 6 + 4 + 5 + 0 = 15
Exercícios Propostos – Lista 7
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 101
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 8
Devemos transformar o problema de maximização em minimização, trabalhando com a tabela dos complementos dos retornos mensais. Faremos o complemento para o maior valor da tabela, 95.
35 15 25 30 25 35 15 35 15 55 35 25 35 5 0 10 1. Subtrair de cada linha o seu menor valor.
20 0 10 15 10 20 0 20 0 40 20 10 35 5 0 10 2. Subtrair de cada coluna o seu menor valor.
20 0 10 5 10 20 0 10 0 40 20 0 35 5 0 0 3. Designar nos zeros da tabela, priorizando as linha e colunas com apenas um zero.
20 D 10 5 10 20 D 10 D 40 20 0 35 5 0 D A designação está completa.
R 1 – V 2; R 2 – V 3; R 3 – V 1; R 4 – V 4
Retorno mensal = 0, 80 x 100 +0, 80 x 150 + 0,80 x 120 +0, 85 x 250 = 508,50
Exercícios Propostos – Lista 7
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 102
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 9
Devemos transformar o problema de maximização em minimização, trabalhando com a tabela dos complementos dos retornos mensais. Faremos o complemento para o maior valor da tabela, 10. Temos que criar uma unidade produtora com ganho zero para equilibrar o sistema.
4 0 5 10 5 2 3 10 2 0 2 10 3 1 1 10 1. Subtrair de cada linha o seu menor valor.
4 0 5 10 3 0 1 8 2 0 2 10 2 0 0 9 2. Subtrair de cada coluna o seu menor valor.
2 0 5 2 1 0 1 0 0 0 2 2 0 0 0 1 3. Designar nos zeros da tabela, priorizando as linha e colunas com apenas um zero.
2 D 5 2 1 0 1 D D 0 2 2 0 0 D 1 A designação está completa.
R 1 – U 2; R 3 – U 1; R 4 – U3
Lucro total = 10 + 8 + 9 = 27
Exercícios Propostos – Lista 7
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 103
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 10
Temos que criar uma unidade produtora com ganho zero para equilibrar o sistema. Devemos transformar o problema de maximização em minimização, trabalhando com a tabela dos complementos dos retornos mensais. Faremos o complemento para o maior valor da tabela, 10. Na célula onde não deve haver designação, colocamos um custo alto (50 por exemplo).
4 0 5 10 5 2 3 10 50 0 2 10 3 1 1 10 1. Subtrair de cada linha o seu menor valor.
4 0 5 10 3 0 1 8 50 0 2 10 2 0 0 9 2. Subtrair de cada coluna o seu menor valor.
2 0 5 2 1 0 1 0 48 0 2 2 0 0 0 1 3. Designar nos zeros da tabela, priorizando as linha e colunas com apenas um zero.
2 D 5 2 1 0 1 D 48 0 2 2 0 0 D 1 A designação não está completa.
4. Cobrir os zeros da tabela com o menor número de linhas possível: C 2; L 2; L 4. Subtrair dos elementos da tabela o menor número não coberto, compensando as linhas e colunas que tenham zeros.
0 0 3 0 1 2 1 0 46 0 0 0 0 2 0 1 5. Designar nos zeros da tabela, priorizando linhas e colunas com apenas um zero.
D 0 3 0 1 2 1 D 46 D 0 0 0 2 D 1
Exercícios Propostos – Lista 7
Exercício 10
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 104
A designação está completa: R 1 – U 1 R 3 – U 2 R 4 – U 3
Lucro = 6 + 10 + 9 = 25
Observe que o problema tem mais de uma solução ótima
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 105
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 11
Como cada empresa pode realizar duas obras, cada uma delas aparece duas vezes nas propostas de custos (linhas). Como temos agora 10 linhas, temos que equilibrar o sistema, criando quatro obras com custo zero (colunas).
12 20 25 30 22 20 0 0 0 0 12 20 25 30 22 20 0 0 0 0 15 20 22 26 19 20 0 0 0 0 15 20 22 26 18 20 0 0 0 0 16 24 26 22 21 21 0 0 0 0 16 24 26 22 21 21 0 0 0 0 14 25 24 28 24 20 0 0 0 0 14 25 24 28 24 20 0 0 0 0 13 22 30 27 20 15 0 0 0 0 13 22 30 27 20 15 0 0 0 0 Vamos diminuir de cada coluna o seu menor elemento.
0 0 3 8 4 5 0 0 0 0 0 0 3 8 4 5 0 0 0 0 3 0 0 4 0 5 0 0 0 0 3 0 0 4 0 5 0 0 0 0 4 4 4 0 3 6 0 0 0 0 4 4 4 0 3 6 0 0 0 0 2 5 2 6 6 5 0 0 0 0 2 5 2 6 6 5 0 0 0 0 1 2 8 5 2 D 0 0 0 0 1 2 8 5 2 0 D 0 0 0 Designar nos zeros, priorizando as linhas e colunas com menos zeros.
D 0 3 8 4 5 0 0 0 0 0 D 3 8 4 5 0 0 0 0 3 0 D 4 0 5 0 0 0 0 3 0 0 4 D 5 0 0 0 0 4 4 4 D 3 6 0 0 0 0 4 4 4 0 3 6 0 D 0 0 2 5 2 6 6 5 0 0 D 0 2 5 2 6 6 5 0 0 0 D 1 2 8 5 2 D 0 0 0 0 1 2 8 5 2 0 D 0 0 0 A designação está completa.
Emp A : Obras 1 e 2 Emp B: Obras 3 e 5 Emp C: Obra 4 Top Clima: Obra 6
Custo = 12 + 20 + 22 + 18 + 22 + 15 = 109 . Não há plano alternativo
Exercícios Propostos – Lista 7
Exercício 11
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 106
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 12
O acréscimo para o orçamento das empresas (para aquelas cujo número de horas estimado
seja superior a 240 horas) será: A = ( )horas planejadas 240 0,20
orçamentohoras planejadas
− ××
E B, ob1: A = ( )250 240 0,20
15 0,12250
− ×× = E A ,Ob2: A=
( )250 240 0,2020 0,16
250− ×
× =
E A, Ob 3: A = 1 E A, Ob 4: A = 1,35 E A, Ob5: A = 0,63
E B, Ob 3: A = 1,38 E B, Ob 4: A = 0,40 E B, Ob 5: A = 0,14 E C, Ob 2: A = 0,37
E C, Ob 3: A = 1,92 E C, Ob 4: A = 0,18 E C, Ob 5: A = 0,32 E C, Ob 6: A = 0,17
E D, Ob 2: A = 0,2 E D, Ob 3: A = 1,20 E D, Ob 4: A = 1,12 E D, Ob 5: A = 0,19
Tabela com os orçamentos acrescidos dos aumentos. Para cada empreiteira teremos duas linhas de orçamento, pois cada uma delas pode fazer duas obras. Devemos acrescentar 4 obras com orçamentos zerados para equilibrar o sistema
Ob 1 Ob 2 Ob 3 Ob 4 Ob 5 Ob 6 Aux 1 Aux 2 Aux 3 Aux 4 A 12 20,16 26 31,35 22,63 20 0 0 0 0 A 12 20,16 26 31,35 22,63 20 0 0 0 0 B 15,12 20 23,38 26,40 18,14 20 0 0 0 0 B 15,12 20 23,38 26,40 18,14 20 0 0 0 0 C 16 24,37 27,92 22,18 21,32 21,17 0 0 0 0 C 16 24,37 27,92 22,18 21,32 21,17 0 0 0 0 D 14 25,20 25,20 29,12 24,19 20 0 0 0 0 D 14 25,20 25,20 29,12 24,19 20 0 0 0 0 TC 13 22 30 27 20 15 0 0 0 0 TC 13 22 30 27 20 15 0 0 0 0 1. Subtrair de cada coluna o seu menor elemento.
Ob 1 Ob 2 Ob 3 Ob 4 Ob 5 Ob 6 Aux 1 Aux 2 Aux 3 Aux 4 A 0 0,16 2,62 9,17 4,49 5 0 0 0 0 A 0 0,16 2,62 9,17 4,,49 5 0 0 0 0 B 3,12 0 0 4,22 0 5 0 0 0 0 B 3,12 0 0 4,22 0 5 0 0 0 0 C 4 4,37 4,54 0 3,18 6,17 0 0 0 0 C 4 4,37 4,54 0 3,18 6,17 0 0 0 0 D 2 5,20 1,82 6,94 6,05 5 0 0 0 0 D 2 5,20 1,82 6,94 6,05 5 0 0 0 0 TC 1 2 6,62 4,82 1,86 0 0 0 0 0 TC 1 2 6,62 4,82 1,86 0 0 0 0 0
Exercícios Propostos – Lista 7
Exercício 12
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 107
2. Designar nos zeros da tabela, priorizando as linhas e colunas com menor número de zeros.
Ob 1 ×
Ob 2 Ob 3 Ob 4 ×
Ob 5 Ob 6 ×
Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D 0,16 2,62 9,17 4,49 5 0 0 0 0 A 0 0,16 2,62 9,17 4,,49 5 0 0 0 0 B × 3,12 D 0 4,22 0 5 0 0 0 0 B × 3,12 0 D 4,22 0 5 0 0 0 0 C 4 4,37 4,54 D 3,18 6,17 0 0 0 0 C 4 4,37 4,54 0 3,18 6,17 0 0 0 0 D 2 5,20 1,82 6,94 6,05 5 0 0 0 0 D 2 5,20 1,82 6,94 6,05 5 0 0 0 0 TC 1 2 6,62 4,82 1,86 D 0 0 0 0 TC 1 2 6,62 4,82 1,86 0 0 0 0 0 Obra 5 ficou sem designação. 3 Cobrir os zeros com o menor número de linhas possível. C7; C8; C9; C10; L3; L4; C1; C4; C6. Subtrair da tabela o menor número descoberto, compensando linhas e colunas com zeros, neste caso, 0,16. Designar priorizando linhas e colunas com menos zeros.
Ob 1 ×
Ob 2 Ob 3 Ob 4 ×
Ob 5 Ob 6 ×
Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D 0 2,46 9,17 4,33 5 0 0 0 0 A 0 D 2,46 9,17 4,,33 5 0 0 0 0 B × 3,28 0,16 D 4,38 0 5,16 0,16 0,16 0,16 0,16 B × 3,28 0,16 0 4,38 D 5,16 0,16 0,16 0,16 0,16 C 4 4,37 4,38 D 3,02 6,17 0 0 0 0 C 4 4,37 4,38 0 3,02 6,17 0 0 0 0 D 2 5,20 1,66 6,94 5,89 5 0 0 0 0 D 2 5,20 1,66 6,94 5,89 5 0 0 0 0 TC 1 2 6,46 4,82 1,70 D 0 0 0 0 TC 1 2 6,46 4,82 1,70 0 0 0 0 0
A designação está completa.
Emp. A – Ob 1 e 2. Emp. B – Ob 3 e 5. Emp. C – Ob 4. Top Clima – Ob 6
Custo = 12 + 20,16 + 23,38 + 18,14 + 22,18 + 15 = 110,86
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 108
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 13
A tabela de orçamentos (Veja Problema 12) deve receber custos altos nas células onde a designação não é possível. Usaremos o orçamento 100.
Ob 1 Ob 2 Ob 3 Ob 4 Ob 5 Ob 6 Aux 1 Aux 2 Aux 3 Aux 4 A 12,00 20,16 26,00 31,35 100,00 100,00 0 0 0 0 A 12,00 20,16 26,00 31,35 100,00 100,00 0 0 0 0 B 15,12 20,00 23,38 100,00 100,00 20,00 0 0 0 0 B 15,12 20,00 23,38 100,00 100,00 20,00 0 0 0 0 C 100,00 24,37 27,92 100,00 21,32 21,17 0 0 0 0 C 100,00 24,37 27,92 100,00 21,32 21,17 0 0 0 0 D 14,00 25,20 25,20 29,12 24,19 20,00 0 0 0 0 D 14,00 25,20 25,20 29,12 24,19 20,00 0 0 0 0 TC 13,00 22,00 30,00 27,00 20,00 15,00 0 0 0 0 TC 13,00 22,00 30,00 27,00 20,00 15,00 0 0 0 0 1. Subtrair de cada coluna o seu menor elemento.
Ob 1 Ob 2 Ob 3 Ob 4 Ob 5 Ob 6 Aux 1 Aux 2 Aux 3 Aux 4 A 0,00 0,16 2,62 4,35 80,00 85,00 0 0 0 0 A 0,00 0,16 2,62 4,35 80,00 85,00 0 0 0 0 B 3,12 0,00 0,00 73,00 80,00 5,00 0 0 0 0 B 3,12 0,00 0,00 73,00 80,00 5,00 0 0 0 0 C 88,00 4,37 4,54 73,00 1,32 6,17 0 0 0 0 C 88,00 4,37 4,54 73,00 1,32 6,17 0 0 0 0 D 2,00 5,20 1,82 2,12 4,19 5,00 0 0 0 0 D 2,00 5,20 1,82 2,12 4,19 5,00 0 0 0 0 TC 1,00 2,00 6,62 0,00 0,00 0,00 0 0 0 0 TC 1,00 2,00 6,62 0,00 0,00 0,00 0 0 0 0 2. Designar nos zeros, priorizando linhas e colunas com menos zeros.
Ob 1 × Ob 2 ×
Ob 3 ×
Ob 4 Ob 5 Ob 6 Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D,00 0,16 2,62 4,35 80,00 85,00 0 0 0 0 A 0,00 0,16 2,62 4,35 80,00 85,00 0 0 0 0 B 3,12 D,00 0,00 73,00 80,00 5,00 0 0 0 0 B 3,12 0,00 D,00 73,00 80,00 5,00 0 0 0 0 C 88,00 4,37 4,54 73,00 1,32 6,17 0 0 0 0 C 88,00 4,37 4,54 73,00 1,32 6,17 0 0 0 0 D 2,00 5,20 1,82 2,12 4,19 5,00 0 0 0 0 D 2,00 5,20 1,82 2,12 4,19 5,00 0 0 0 0 TC × 1,00 2,00 6,62 0,00 D,00 0,00 0 0 0 0 TC × 1,00 2,00 6,62 0,00 0,00 D,00 0 0 0 0 3. A obra 4 não recebeu designação. Cobrir os zeros com o menor número de linhas possível. No caso: Aux 1; Aux 2; Aux 3; Aux 4; L 9; L 10; Ob 1; Ob2; Ob3.
Exercícios Propostos – Lista 7
Exercício 13
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 109
3. Subtrair da tabela o menor número não coberto, compensando as linhas e colunas com zeros. No caso, 1,32.
Ob 1 × Ob 2 ×
Ob 3 ×
Ob 4 Ob 5 Ob 6 Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A 0,00 0,16 2,62 3,03 78,68 83,68 0,00 0,00 0,00 0,00 A 0,00 0,16 2,62 3,03 78,68 83,68 0,00 0,00 0,00 0,00 B 3,12 0,00 0,00 71,68 78,68 3,68 0,00 0,00 0,00 0,00 B 3,12 0,00 0,00 71,68 78,68 3,68 0,00 0,00 0,00 0,00 C 88,00 4,37 4,54 71,68 0,00 4,85 0,00 0,00 0,00 0,00 C 88,00 4,37 4,54 71,68 0,00 4,85 0,00 0,00 0,00 0,00 D 2,00 5,20 1,82 0,80 2,87 3,68 0,00 0,00 0,00 0,00 D 2,00 5,20 1,82 0,80 2,87 3,68 0,00 0,00 0,00 0,00 TC × 2,32 3,32 7,94 0,00 0,00 0,00 1,32 1,32 1,32 1,32 TC × 2,32 3,32 7,94 0,00 0,00 0,00 1,32 1,32 1,32 1,32 4. Designar nos zeros da tabela, priorizando linhas e colunas com menos zeros
Ob 1 × Ob 2 × Ob 3 × Ob 4 Ob 5 Ob 6 Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D,00 0,16 2,62 3,03 78,68 83,68 0,00 0,00 0,00 0,00 A 0,00 0,16 2,62 3,03 78,68 83,68 0,00 0,00 0,00 0,00 B 3,12 D,00 0,00 71,68 78,68 3,68 0,00 0,00 0,00 0,00 B 3,12 0,00 D,00 71,68 78,68 3,68 0,00 0,00 0,00 0,00 C 88,00 4,37 4,54 71,68 D,00 4,85 0,00 0,00 0,00 0,00 C 88,00 4,37 4,54 71,68 0,00 4,85 0,00 0,00 0,00 0,00 D 2,00 5,20 1,82 0,80 2,87 3,68 0,00 0,00 0,00 0,00 D 2,00 5,20 1,82 0,80 2,87 3,68 0,00 0,00 0,00 0,00 TC × 2,32 3,32 7,94 0,00 0,00 D,00 1,32 1,32 1,32 1,32 TC × 2,32 3,32 7,94 D,00 0,00 0,00 1,32 1,32 1,32 1,32 A designação está completa.
E A – Ob 1 E B – Ob 2 e 3 E C – Ob 5 TC – Ob 4 e 6.
Custo = 12 + 20 + 23,38 + 21,32 + 27 + 15 = 118,70
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 110
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 14
O desenvolvimento deste exercício é o mesmo do Ex 12 com a eliminação da coluna Ob 6, já que esta obra não participa da atribuição (já está atribuída). Esta coluna deve ser substituída pela auxiliar Aux 5 com custo zero para reequilibrar o sistema.
Quadro final (mesmo do Ex 12 com a substituição feita)
Ob 1 ×
Ob 2 Ob 3 Ob 4 ×
Ob 5 Aux 5 ×
Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D 0 2,46 9,17 4,33 0 0 0 0 0 A 0 D 2,46 9,17 4,,33 0 0 0 0 0 B × 3,28 0,16 D 4,38 0 0,16 0,16 0,16 0,16 0,16 B × 3,28 0,16 0 4,38 D 0,16 0,16 0,16 0,16 0,16 C 4 4,37 4,38 D 3,02 0 0 0 0 0 C 4 4,37 4,38 0 3,02 0 0 0 0 0 D 2 5,20 1,66 6,94 5,89 0 0 0 0 0 D 2 5,20 1,66 6,94 5,89 0 0 0 0 0 TC 1 2 6,46 4,82 1,70 0 0 0 0 0 TC 1 2 6,46 4,82 1,70 0 0 0 0 0
A designação está completa.
E A – Ob 1 e 2. E B – Ob 3 e 5. E C – Ob 4
Custo parcial = 12 + 20,16 + 23,38 + 18,14 + 22,18 = 95,86
Custo incluindo a obra 6 = 95,86 + 21,17 = 117,03
No caso, corresponde a simplesmente substituir um custo de 15 (TC) por um custo de 21,17 (E C). O custo da política é 21,17 – 15 = 6,17.
Exercícios Propostos – Lista 7
Exercício 14
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 111
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 7 Ex 15
O desenvolvimento deste exercício é o mesmo do Ex 12 com a eliminação da coluna Ob 6, já que esta obra não participa da atribuição (já está atribuída). Esta coluna deve ser substituída pela auxiliar Aux 5 com custo zero para reequilibrar o sistema.
Quadro final (mesmo do problema 12 com a substituição feita)
Ob 1 ×
Ob 2 Ob 3 Ob 4 ×
Ob 5 Aux 5 ×
Aux 1 ×
Aux 2 ×
Aux 3 ×
Aux 4 ×
A D 0 2,46 9,17 4,33 0 0 0 0 0 A 0 D 2,46 9,17 4,,33 0 0 0 0 0 B × 3,28 0,16 D 4,38 0 0,16 0,16 0,16 0,16 0,16 B × 3,28 0,16 0 4,38 D 0,16 0,16 0,16 0,16 0,16 C 4 4,37 4,38 D 3,02 0 0 0 0 0 C 4 4,37 4,38 0 3,02 0 0 0 0 0 D 2 5,20 1,66 6,94 5,89 0 0 0 0 0 D 2 5,20 1,66 6,94 5,89 0 0 0 0 0 TC 1 2 6,46 4,82 1,70 0 0 0 0 0 TC 1 2 6,46 4,82 1,70 0 0 0 0 0
A designação está completa.
E A – Ob 1 e 2. E B – Ob 3 e 5. E C – Ob 4
Custo parcial = 12 + 20,16 + 23,38 + 18,14 + 22,18 = 95,86
Custo incluindo a obra 6 = 95,86 + 20 = 115,86
No caso, corresponde a simplesmente substituir um custo de 15 (TC) por um custo de 20 (E C). O custo da política é 20 – 15 = 5
Exercícios Propostos – Lista 7
Exercício 15
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 112
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo Exercícios propostos – Lista 8 Ex 1 Modelo: max Z = x1 + 0,30 x2 + 3 x3 x1 + x2 + x3 ≤ 10 . sujeito a 2 x1 + x2 + 4 x3 ≤ 12 . x1 + 3 x2 – x3 ≤ 9 Quadro final de solução pelo simplex. X1 X2 X3 Xf1 Xf2 Xf3 b 0,50 0,45 0 0 0,75 0 9 Linha 1 0,50 0,75 0 1 –0,25 0 7 2 0,50 0,25 1 0 0,25 0 3 3 1,50 3,25 0 0 0,25 1 12
1.1 Intervalo de estabilidade para o coeficiente de x3. Paraque a variável básica x3 saia da base é necessário que alguma variável não básica entre para completar a base em seu lugar. Para que isso aconteça, os ganhos com a entrada da variável não básica deve compensar as perdas das outras variáveis. Vamos verificar em que condições isso acontece. a. Entrada de x1 (x1 passa do valor zero para um) Ganho: 1x 1(coeficiente no objetivo) = 1 Perdas (acompanhe no quadro de solução ótima). Xf1 diminui em 0,50 x3 diminui em 0,50 xf3 diminui em 1,50 Se C3 é o coeficiente de X3 na função objetivo , a perda total é: 0 x 0,50 +0,50 C3 + 0 x 1,50 Igualando perdas e ganhos: 0,50 C3 = 1 ou C3 = 2 b. Entrada de x2 (x2 passa do valor zero para um) Ganho: 0,30 x 1(coeficiente no objetivo) = 0,30 Perdas (acompanhe no quadro de solução ótima). Xf1 diminui em 0,75 x3 diminui em 0,25 xf3 diminui em 3,25 Se C3 é o coeficiente de X3 na função objetivo , a perda total é: 0 x 0,75 +0,25 C3 + 0 x 1,50 Igualando perdas e ganhos: 0,25 C3 = 0,30 ou C3 = 1,20 a. Entrada de xf2 (xF2 passa do valor zero para um) Ganho: 1x 0(coeficiente no objetivo) = 0 Perdas (acompanhe no quadro de solução ótima). Xf1 diminui em – 0,25 x3 diminui em 0,25 xf3 diminui em 0,25 C3 é o coeficiente de X3 na função objetivo . A perda total é: 0 x(– 0,25) +0,25 C3 + 0 x 0,25 Igualando perdas e ganhos: 0,25 C3 = 0 ou C3 = 0 Ordenando os valores críticos de C3, temos: 0 ≤ 1,20 ≤ 2 ≤ 3 (coeficiente no objetivo) Portanto, a solução é estável em relação ao coeficiente de x3 se C3 ≥ 2. 1.2 Intervalo de estabilidade para xf1(Xf1 mede a sobra do refurso R1)
Exercícios Propostos – Lista 8
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 113
Como o recurso há sobra de 7 unidades do recurso R1, uma diminuição de até 7 unidades deste recurso não altera a solução. O mesmo ocorre com o aumento deste recurso, ou seja –7 ≤ V1 < ∞ 1.3 Significa que a solução do modelo não se altera se o lucro por unidade do produto P3 (coeficiente de x3 no objetivo) for no mínimo 2. 1.4 O estoque deste recurso para o programa tem que ser no mínimo 3 unidades (o estoque era de 10 unidades e sobraram 7). 1.5 Intervalo de estabilidade para o coeficiente de x1. Como x1 não é variável básica, a entrada de x1 na base diminui o valor do lucro em 0,5, exatamente seu valor de oportunidade. Para compensar esta perda teríamos que aumentar o coeficiente de x1 no objetivo em 0,5. Como seu coeficiente no objetivo é 1, a solução é estável em relação ao seu coeficiente se ele for no máximo 1,5, ou seja, C1 ≤ 1,5. 1.6 A entrada de x2 na base tende a diminuir o lucro em 0,45. Para compensar, devemos aumentar o seu coeficiente em 0,45 no objetivo. Desta forma, a solução é estável se seu coeficiente for no máximo 0,30 + 0,45 = 0,75, ou seja, C2 ≤ 0,75. 1.7 Se P4 usa os recursos R1, R2 e R3, para que ele seja viável deve repor o lucro perdido com os outros produtos pela escassez que ele pode provocar. Uso de recursos por P4 Valor de oportunidade Capacidade de gerar dos recursos lucro necessária 2 unidades de R1 0 (folga de 7 un) 2 x 0 + 1 unidade de R2 0,75 1 x 0,75 + 3 unidades de R3 0 (folga de 12 un) 3 x 0 =0,75 Portanto, o lucro por unidade de P4 deverá ser no mínimo 0,75. 1.8 Indicando a variação do recurso por V2, teremos: No quadro inicial No quadro final
10 10 0̀12 V2 12 1 V29 9 0
+ = +
7 0,253 0,25 V212 0,25
− +
Como V2 não pode tornar alguma variável negativa no quadro final, devemos ter: 7 – 0,25 V2 ≥ 0 ou V2 ≤ 28 3 + 0,25 V2 ≥ 0 ou V2 ≥ – 12 12 + 0,25 V2 ≥ 0 ou V2 ≥– 48 Portanto, –12 ≤ V2 ≤ 28, de onde o aumento possível é 28. 1.9 No quadro de solução ótima o recurso R1 aparece com sobra de 7 unidades (xf1 = 7). Portanto qualquer aumento em sua disponibilidade não afeta a solução.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 114
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo Exercícios propostos – Lista 8 Ex 2
Modelo a ser analisado: Max z = 2.100 x1 + 1.200 x2 + 600 x3 6 x1 + 4 x2 + 6 x3 ≤ 4.800 s.a 12 x1 + 16 x2 + 2 x3 ≤ 7.200 X1 ≤800 x2 ≤ 600 x3 ≤ 600 Quadro final pelo simplex. 1 0 1.400 0 50 150 0 0 0 1.320.000 0 0 0 0 0
0 – 0,8 1 0,20 – 0,10 0 0 0 1 1,467 0 – 0,033 0,10 0 0 0 0 – 1,467 0 0,033 – 0,10 1 0 0 0 1 0 0 0 0 1 0 0 0,8 0 – 0,20 0,10 0 0 1
240 560 240 600 360
2.1 O valor crítico para o coeficiente de x1 é C1. No quadro final, a saída de x1 requer a entrada de alguma variável não básica: x2, xf1 ou xf2. A entrada da variável não básica deve compensar a perda pela saída de x1. Do quadro final podemos deduzir os fatos: a. Entrada de x2: x3 diminui em – 0,8 ; x1 diminui em 1,467 ; xf3 diminui em – 1,467 xf4 diminui em 1; xf5 diminui em 0,8. Aumento pela entrada de x2: 1 x 1.200 = 1.200 Diminuição devido às outras variáveis: – 0,8 x 600 + 1,467 C1 + (– 1,467) x 0 + 0,8 x 0 Portanto, – 480 + 1,467 C1 = 1.200, de onde C1 = 1.145,19 b. Entrada de xf1: x3 diminui em 0,20; x1 diminui em – 0,033; Xf3 diminui em 0,033; xf4 diminui em 0; xf5 diminui em – 0,20 Aumento pela entrada de xf1: 1 x 0 = 0 Diminuição devido às outras variáveis: 600 x 0,20 + – 0,033 C1 + 0,033 x 0 + 0 x 0 + 0,20 x 0 Portanto, 120 – 0,33C1 = 0 ou C1 = 3.600 c. Entrada de xf2: x3 diminui em – 0,10; x1 diminui em 0,10; xf3 diminui em – 0,10; xf4 diminui em 0; xf5 diminui em 0,10 Aumento pela entrada de xf2: 0 x 1 = 0 Diminuição devido às outras variáveis: 600 x (– 0,10) + C1 x 0,10 + 0 x (–0,10) + 0 x 0 Portanto. –60 + 0,10C1 = 0 ou C1 = 600 Ordenando os valores de C1, vem: 600 ≤ 1.145,19 ≤2.100 ≤ 3.600, ou seja, a solução é estável para 1.145,19 ≤ C1 ≤ 3.600. Isto significa que se o lucro por unidade de P1, atualmente em 2.100, diminuir até 1.145,19 ou aumentar até 3.600 a solução do problema não se altera. 2.2 O valor crítico para o coeficiente de x3 é C3. No quadro final, a saída de x1 requer a entrada de alguma variável não básica: x2, xf1 ou xf2. A entrada da variável não básica deve compensar a perda pela saída de x3.
Exercícios Propostos – Lista 8
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 115
Do quadro final podemos deduzir os fatos: a. Entrada de x2: x3 diminui em – 0,8 ; x1 diminui em 1,467 ; xf3 diminui em – 1,467 xf4 diminui em 1; xf5 diminui em 0,8. Aumento pela entrada de x2: 1 x 1.200 = 1.200 Diminuição devido às outras variáveis: C3 x (– 0,8) + 2.100 x 1,467 + (– 1,467) x 0 + 0,8 x 0 Portanto, – 0,8 C3 + 3.080,70 = 1.200, de onde C3 = 2.380,88 b. Entrada de xf1: x3 diminui em 0,20; x1 diminui em – 0,033; Xf3 diminui em 0,033; xf4 diminui em 0; xf5 diminui em – 0,20 Aumento pela entrada de xf1: 1 x 0 = 0 Diminuição devido às outras variáveis: C3 x 0,20 + 2.100 x (– 0,033) Portanto, 0,20C3 – 70 = 0 ou C3 = 350 c. Entrada de xf2: x3 diminui em – 0,10; x1 diminui em 0,10; xf3 diminui em – 0,10; xf4 diminui em 0; xf5 diminui em 0,10 Aumento pela entrada de xf2: 0 x 1 = 0 Diminuição devido às outras variáveis: C3 x (– 0,10) + 2.100 x 0,10 Portanto. – 0,10 C3 + 210 = 0 ou C3 = 2.100 Ordenando os valores de C3, vem: 350 ≤ 600 ≤2.100 ≤ 2.380,88, ou seja, a solução é estável para 350 ≤ C3 ≤ 2.100. Isto significa que se o lucro por unidade de P1, atualmente em 600, diminuir até 350 ou aumentar até 2.100 a solução do problema não se altera 2.3 xf3 representa a sobra do recurso R3. Como seu valor é 240 no quadro final, concluímos que uma diminuição até 240 unidades desse recurso não altera a solução. Um aumento só faria aumentar essa disponibilidade. 2.4 xf1 = 0 o que indica que R1 é um recurso escasso e seu coeficiente 50 indica a tendência ao aumento de lucro caso possamos agregar mais uma unidade de R1 ao estoque deste recurso, aos custos correntes. Caso o estoque seja diminuído em uma unidade o coeficiente 50 indica a diminuição do lucro por contar com uma unidade a menos de R1. Chamando de V1 a variação do estoque de R1. A variação de V2 não pode tornar negativos os termos da direita (b) do quadro final do simplex, pois isto daria valor negativo para alguma variável. Valores de b no quadro final
240 0,20560 0,033240 0,033 1600 0360 0,20
V
− + −
de onde,
240 + 0,20 V1 = 0 → V1 = – 1.200 560 – 0,033 V1 = 0 → V1 = 16.800 240 + 0,033 V1 = 0 → V1 = – 7.200 600 + V1 = 0 → V1 = ∞ 360 – 0,20 V1 = 0 → V1 = 1.800 Ordenando os valores de V1: – 7.200 ≤ – 1.200 ≤ 1.800 ≤ 16800 < ∞
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 116
Portanto – 1.200 ≤ V1 ≤ 1800 ou seja, se o estoque de R1 diminuir até 1.200 unidades a perda de lucro por unidade diminuída será de 50; se o estoque aumentar até 1.800 unidades aos preços correntes, o ganho de lucro por unidade aumentada será de 50. 2.5 Se um novo produto P4 que consome 3 horas de máquina (R1) e 5 horas de mão de obra (R2) entrar na base, ele retira do lucro: 3 h de R1 a 50/h (valor de oportunidade de R1) + 5 h de R2 a 150/h (valor de oportunidade de R2 = 150 + 750 = 900. O lucro do produto é 800, o que indica um prejuízo de 100 se for fabricado. Não há interesse. 2.6 Vamos chamar de V a variação deste (R1). A variação permitida para esse recurso é a que não torna negativo algum elemento d o lado direito das equações, o que daria um valor negativo para uma variável. No quadro final esta condição pode ser escrita na forma:
240 0,20 0560 0,033 0240 0,033 0600 0 0360 0,20 0
V
− + = −
de onde vem
240 + 0,20 V = 0 → V = – 1.200 560 – 0,033 V = 0 → V = 16.800 240 + 0,033 V = 0 → V = – 7.200 600 + 0 V = 0 → V = –∞ 360 – 0,20 V = 0 → V = 1.800 Ordenando os valores de V: – ∞ < – 7.200 ≤ – 1.200 ≤ 1.800 ≤16.800. Portanto uma diminuição até 1.200 ou um aumento até 1.800 não altera o custo de oportunidade deste recurso. 2.7 Da mesma forma que o item anterior, como o recurso R2 é escasso, a variação vista no quadro final pode ser equacionada na forma:
0,10 240 00,10 560 0
0,10 240 00 600 00,10 360 0
V
− − + =
de onde vem
240 – 0,10 V = 0 → V = 2.400 560 + 0,10 V = 0 → V = – 5.600 240 – 0,10 V = 0 → V = 2.400 600 + 0 V = 0 → V = – ∞ 360 + 0,10 V = 0 → V = – 3.600 Ordenando os valores de : – ∞< – 5.600 ≤ – 3.600 ≤ 2.400. Portanto, uma aquisição de 2.400 unidades aos custos correntes, mantém a informação contida no custo de oportunidade deste recurso. 2.8 O custo de oportunidade nulo do recurso demanda de P3 indica que há sobra deste recurso. Uma diminuição de 360 unidades na demanda de P3 não afeta u lucro.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 117
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo Exercícios propostos – Lista 8 Ex 3 Modelo do problema. Obj. min custo = x1 + 1,20 x2 + 1,30 x3 0,3 x1 + 0,25 x2 + 0,10 x3 ≥ 6 Restrições 0,20 x1 + 0,30 x2 + 0,20 x3 ≥4 0,25x1 + 0,15 x2 + 0,30 x3 ≥4 0,25x1 + 0,30x2 + 0,40x3 ≥6 3.1 A saída de x1 da base implica na entrada de uma variával não básica, de modo que o aumento de custo pela entrada da variável não básica seja compensada pela diminuição de custo pela saída de x1. Seja C1 a variação no custo da ração 1 (R1). Entrada de x2. x1 diminui em 0,732 ; xf2 diminui em – 0,095; xf3 diminui em 0,121; x3 diminui em 0,289. Total da diminuição: 0,732 C1 + 0,289 x 1,30 Aumento do custo devido a x2: 1,20 . Compensando: 0,732 C1 + 0,376 = 1,20 → C1 = 1,126 Entrada de xf1. x1 diminui em – 4,211; xf2 diminui em – 0,316; xf3 diminui em – 0,263; x3 diminui em 2,632 Total da diminuição: – 4,211 C1 + 2,632 x 1,3 Aumento devido a xf1: zero Compensando: -4,211 C1 + 3,422 = 0 → C1 = 0,813 Entrada de xf4. x1 diminui em 1,053 ; xf2 diminui em – 0,421; xf3 diminui em 0,684; x3 diminui em – 3,158. Total da diminuição: 1,053 C1 – 3,158 x 1,3 Compensando: 1,053 C1 – 4,105 = 0 → C1 = 3,899 Ordenando os valores de C1: 0,813 ≤ 1,126 ≤ 3,899. O intervalo procurado é: 0,813 ≤ C1 ≤ 1,126. 3.2 O preco da ração 2 no quadro inicial é 1,20, e no quadro final 0,087, o que indica que se usarmos a ração 2 haveria um aumento de custo de 0,087. Se diminuirmos o custo da ração em0,087 no quadro inicial, seu valor no quadro final seria zero, o que indica que a ração passa a ser interessante. 3.3 A solução é alterada devido ao preco da R3 quando x3 sai da base. A saída de x3 da base implica na entrada de uma variával não básica, de modo que o aumento de custo pela entrada da variável não básica seja compensada pela diminuição de custo pela saída de x3. Seja C3 a variação no custo da ração 3 (R3). Entrada de x2. x1 diminui em 0,732 ; xf2 diminui em – 0,095; xf3 diminui em 0,121; x3 diminui em 0,289. Total da diminuição: 0,732 x 1 + 0,289 C3 Aumento do custo devido a x2: 1,20. Compensando: 0,732 + 0,289 C3 = 1,20 → C3 = 1,619
Exercícios Propostos – Lista 8
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 118
Entrada de xf1. x1 diminui em – 4,211; xf2 diminui em – 0,316; xf3 diminui em –0,263; x3 diminui em 2,632 Total da diminuição: – 4,211 x 1 + 2,632 x C3 Aumento devido a xf1: zero Compensando: -4,211 + 2,632 C3 = 0 → C3 = 1,6 Entrada de xf4. x1 diminui em 1,053 ; xf2 diminui em – 0,421; xf3 diminui em 0,684; x3 diminui em – 3,158. Total da diminuição: 1,053 – 3,158 x C3 Compensando: 1,053 – 3,158 C1 = 0 → C1 = 0,333 Ordenando os valores de C1: 0,333 ≤ 1,60 ≤ 1,619. O intervalo procurado é: 0,333 ≤ C3 ≤ 1,60. 3.4 O valor de oportunudade do nutriente 1 é 0,789 e expressa a tendência de aumento de custo no caso de aumentar a exigência em 1 Kg do nutriente 1 na mistura. 3.5 Essa informação contida no valor de oportunidade do nutriente 4, vale para variações de exigência do nutriente até que não torne negativa alguma variável básica no quadro final do simplex. Sendo V a variação desta exigência, o seu valor crítico pode ser calculado pela equação. 18,947 1,053 00,421 0,421 01,684 0,684 03,158 3,158 0
V
− + = − −
, de onde:
18,497 + 1,053 V = 0 → V = –17,566; 0,421 – 0,421 V = 0 → V = 1 1,684 – 0,684 V = 0 → V = 2,462 3,158 – 3,158 V = 0 → V = 1 Ordenando os valores –17,566 ≤ 1≤ 2,462. Então –17, 566 ≤ V ≤ 1. A informação vale até o limite de 1 Kg.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 119
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 1
Classes Ponto fi% Fi% Limites p/
números número de
médio
Aleatórios
aleatórios atendimentos
10 ------ 12 11 15 15 00 a 14
10 11 12 ------ 14 13 20 35 15 a 34
85 17
14 ------ 16 15 35 70 35 a 69
36 15 16 ------ 18 17 20 90 70 a 89
49 15
18 ------ 20 19 10 100 90 a 99
58 15
5 11
67 15
fi% frequência relativa
Fi% frequência acumulada relativa
Exercícios Propostos – Lista 9
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 120
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 2
Exercícios Propostos – Lista 9
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 121
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 3
O estoque após 7 dias simulados é de 6 unidades.
Exercícios Propostos – Lista 9
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 122
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 4
O estoque final após 7 dias é de 6 unidades
Exercícios Propostos – Lista 9
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 123
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 5
.
Custo semanal: 39,00
Exercícios Propostos – Lista 9
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 124
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 6
O custo é 33,00. A tendência é a diminuição de custo
Exercícios Propostos – Lista 9
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 125
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 7
Exercícios Propostos – Lista 9
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 126
Respostas . a. A dispenda do funcionário 3 (o de menor média) aumenta os custos de operação.
b. A contratação de um funcionário 4 (de mesmo desempenho que o func 3) diminui os custos de operação.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 127
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 8
Resp. Sim. Com o técnico o custo é menor.
Exercícios Propostos – Lista 9
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 128
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 9
a. Deixar o carro em local proibido. Custo: 130
b. Usar o estacionamento. Custo = 22 x 5 = 110
Melhor usar o estacionamento.
Exercícios Propostos – Lista 9
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 129
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 9 Ex 10
Há 10 clientes na fila de espera após 10 minutos. O tempo de atendimento não parece compatível com a demanda. A tendência é a fila crescer continuamente.
Exercícios Propostos – Lista 9
Exercício 10
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 130
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 1
Exercícios Propostos – Lista 10
Exercício 1
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 131
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 2
Exercícios Propostos – Lista 10
Exercício 2
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 132
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 3
Exercícios Propostos – Lista 10
Exercício 3
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 133
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 4
A distribuição empírica tem ajuste normal ao nível de 10% de significância.
Exercícios Propostos – Lista 10
Exercício 4
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 134
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 5
Exercícios Propostos – Lista 10
Exercício 5
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 135
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 136
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 6
No exercício 3 após 10 simulações, concluímos que a TIR do projeto tem média 24,33% e
desvio padrão 8,30%. Supondo a distribuição das TIR normal, a variável TIR 24,33
8,30z −= tem
distribuição normal padrão. Para o cálculo das probabilidades usar a tabela ou a função do Excel DIST.NORMP.
a. 24 24,33 30 24,33TIR 24 0,04 TIR 30 0,68
8,30 8,30z z− −
= → = = − = → = =
( ) ( )24 30 0,04 0,68 0,7517 0,4840 0,2677P TIR P z≤ ≤ = − ≤ ≤ = − =
b. O intervalo de confiança de 95% para a TIR é dado por:
( )¨ ¨ 1P TIR e TIR eµ α− ≤ ≤ + = − onde e(erro padrão de estimativa) = ( )
2
s TIRt
nα
Substituindo os valores: s(TIR) = 8,30; α =0,05; 0,052 2
2, 26t tα = = tabela t ou função INVT do
Excel com 9 graus de liberdade; n = 10, vem: 8,302,26 5,93
10e = = .Portanto,
( ) ( )24,33 5,93 24,33 5,93 18,4 30,26 0,95P Pµ µ− ≤ ≤ + = ≤ ≤ =
c. Teste 0 : 27: 27a
H TIRH TIR
= <
( )
¨ 24,33 27 1,028,30
10
cTIRts TIR
n
µ− −= = −=
1,38tt = com probabilidade 0,20 e 9 graus de liberdade. Como ct está na região de aceitação
do teste, podemos afirmar que a TIR é de 27% ao nível de 10% de significância.
Exercícios Propostos – Lista 10
Exercício 6
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 137
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 7
No exercício 4 mostramos que os valores simulados do projeto de investimento é uma amostra de uma variável normal com média 20,60 e desvio padrão 1,26, ao nível de
significância de 10%. A normal padrão correspondente é dada por: 20,601,26
TIRz −= .
a. Para 19 20,6019 1,261,26
TIR z −= → = = −
( ) ( )19 1,26 0,1038P TIR P z< = < − =
b. b. O intervalo de confiança de 95% para a TIR é dado por:
( )¨ ¨ 1 ,P TIR e TIR eµ α− ≤ ≤ + = − onde e(erro padrão de estimativa) = ( )
2
s TIRt
nα
Substituindo os valores: s(TIR) = 1,26; α =0,05; 0,052 2
2, 26t tα = = tabela t ou função INVT do
Excel com 9 graus de liberdade; n = 10, vem: 1,262,26 0,90
10e = = . Portanto,
( ) ( )20,60 0,90 20,60 0,90 19,7 21,5 0,95P Pµ µ− ≤ ≤ + = ≤ ≤ =
Exercícios Propostos – Lista 10
Exercício 7
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 138
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 8
Exercícios Propostos – Lista 10
Exercício 8
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 139
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 9
Como a demanda é normal com média 20 e desvio - padrão 3. Podemos começar com demanda 10 (mais de3 desvios-padrão à esquerda) que deve apresentar demanda zero. Vamos calcular P(10) = P(9,5≤ d ≤10,5). Para o cálculo das probabilidades com a tabela da normal padrão, devemos calcular os correspondentes valores de z. Para quem usa o Excel, esses valores podem ser obtidos diretamente com a função DIST.NORM. Pode-se usar também a probabilidade de massa da DIST.NORM que dá diretamente o valor de P(10), P(11), ...
203
dz −=
9,5 20 10,5 209,5 3,5 10,5 3,173 3
d z d z− −= → = = − = → = = −
P(10) = P(9,5≤ d ≤10,5)=P(–3,5 ≤ z ≤–3,17)=0,000762 – 0,000233=0,00 . A tabela a seguir mostra os resultados para P(11), P(12), etc.
Exercícios Propostos – Lista 10
Exercício 9
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 140
c. Sim, o custo por falta está alto. Testar políticas que aumentem a reposição.
Pesquisa Operacional | Medeiros | Medeiros | Gonçalves | Murolo 141
Pesquisa Operacional Quarta Edição Medeiros, Medeiros, Gonçalves, Murolo
Exercícios propostos – Lista 10 Ex 10
a) 0 4800 1,413411,12
z −= = − P(L > 0)= P( z > –1,41) = 92,07%
b) 10000 4800 1,52
3411,12z −= = P(L > 10000) = P(z > 1,52) = 6,43%
Exercícios Propostos – Lista 10
Exercício 10