PESQUISA OPERACIONAL EXERCICIOS RESOLVIDOS

Prévia do material em texto

1/13 
 
 
 
 
CENTRO UNIVERSITÁRIO DA GRANDE DOURADOS 
Curso: Engenharia de Produção 
Semestre: 6º 
Disciplina: Pesquisa Operacional 
Professor: Bárbara Helen Rodrigues Ramires Seribeli 
 
ATIVIDADE 1 - REFERENTE AS AULA 01 A 04 
 
Construção de modelos 
 
1) A empresa NYZ, fez uma recente pesquisa onde aponta que a necessidade mínima de vitaminas 
na alimentação é de 37 unidades por dia e a de proteínas de 31 unidades por dia. Considerando 
que uma pessoa tem disponível carne e ovo para se alimentar e que cada unidade de carne 
contém 4 unidades de vitaminas e 6 unidades de proteínas e cada unidade de ovo contém 8 
unidades de vitaminas e 6 unidades de proteínas. Construa o modelo matemático que representa 
qual a quantidade de carne e ovo que deve ser consumida de forma a ter o “Menor custo 
possível”. Cada unidade de carne custa R$ 3,00 e cada unidade de ovo custa R$ 2,5. 
 
Solução: 
Necessidade minima de vitamina: 37 unidades/dia 
Necessidade minima de proteina: 31 unidades/dia 
- 1 unidade de carne: 4 unidade de vitamna; 6 unidades de proteinas, custo de R$ 3,00. 
- 1 unidade de ovo: 8 unidade de vitamna; 6 unidades de proteinas, custo de R$ 2,50. 
- Determinção das variáveis de decisão: 
- Unidade de carne consumida: x1 
- Unidade de ovo consumida: x2 
Determinação da minha função objetivo: (minimizar custo) 
Min Z=3x1 +2,5x2 
 Sujeito as restrições 
4x1 + 6x2 ≥ 37 (unidade de carne) 
8x1 + 6x2 ≥ 31(unidade de ovo) 
X1, x2 ≥ 0 
 
 
 
 2/13 
 
 
2) A empresa Super-Mix deseja planejar a produção de Sucos. Os sucos requerem dois tipos de 
recursos: mão-de-obra e materiais. A empresa fabrica três tipos de sucos, cada qual com 
diferentes necessidades de mão-de-obra e materiais, conforme tabela abaixo: 
 Sabor A Sabor B Sabor C 
Mão de obra (horas/litro) 7 3 6 
Materiais (g/unidade produzida) 4 4 5 
Lucro (R$/unidade) 4 2 3 
 
 
A disponibilidade de materiais é de 200 g/dia. A mão-de-obra disponível por dia é de 150 
horas. Formule um problema de programação linear para determinar quanto deve ser produzido de 
cada tipo de suco, tal que o lucro total seja maximizado. 
 
Variáveis de decisão: xA=quant.do suco A, xB=quant.do suco B, xC quant do suco C. 
Restrições: 
7xA + 3xB + 6xC ≤ 150 
4xA + 4xB + 5xC ≤ 200 
xA,xB,xC ≥ 0. 
Função objetivo: Maximizar o Lucro 
 L=4xA+2xB+3xC 
 
 
 
 
3) A Só Janelas Ltda. é uma empresa com apenas três funcionários que fazem dois tipos 
diferentes de janelas feitas à mão: uma com esquadria de madeira e outra com esquadria de 
alumínio. Eles têm um lucro de R$ 60,00 por janela com esquadria de madeira e de R$ 30,00 
para janela com esquadria de alumínio. João faz as de esquadria de madeira e é capaz de 
construir seis delas por dia. Maria faz as janelas com esquadrias de alumínio e é capaz de 
construir quatro delas por dia. Roberto monta e corta os vidros e é capaz de fazer 48 m²/dia. 
Cada janela com esquadria de madeira usa 6 m² de vidro e cada janela com esquadria de 
alumínio usa 8 m² de vidro. A empresa quer determinar quantas janelas de cada tipo de 
esquadria podem ser fabricadas diariamente para maximizar o lucro total. 
(a) Formule um modelo de programação linear para este problema. 
(b) Use o método gráfico para solucionar esse modelo. 
 
a) Max Z = 60x1+30x2 
 
x1 ≤ 6 
x2 ≤ 4 
6x1 + 8x2 ≤ 48 
x1,x2 ≥ 0. 
 
 3/13 
 
 
 
 
 
 
 
b) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 4/13 
 
 
 
 
Método Gráfico 
 
4) Considere o modelo: 
Maximizar Z = 2x1 + 3x2 
Sujeito as restrições: 
x1 + 5x2 ≤ 20 
2x1 + x2 ≤ 10 
x1 ≥ 0, x2 ≥ 0 
a) Use o método gráfico para construir a região de soluções do modelo (construir o gráfico a 
mão). 
b) Testar a função objetivo em cada uma das soluções básicas e escolher o ponto mais 
favorável. 
Pontos de referencia (0,0) 
Para restrição 1=x1+5x2=20 Para restrição 2=2x1+x2=10 
Ponto A (0,4) Ponto D (0,10) 
Ponto B (20,0) Ponto E (5,0) 
Ponto C (3,35 ; 3,33) 
 
Teste do lado direito das restrições, tomando um ponto de referencia dentro da zona factivel 
Ponto F(1,1) 
 
Restrição 1.1+5=6≤ 20 - verdadeira 
Restrição 2.2+1=3≤ 10 - verdadeira 
Região factivel:ACE 
Função objetivo:2x1+3x2 
Ponto A: 2.0+3.4=12 (valor de Z) 
Ponto E: 2.5+3.0=10 (valor de Z) 
Ponto C: Intersecção do segmento das retas 1 e 2. 
(I) x1+5x2 = 20 
(II) 2x1+x2=10 
Isolamento de x1:20-5x2 
Substituir na 2 equação obten-se o valor de x2 na equação isolada temos:x1=3,35 
Ponto C; 2.3,35+3.3,33=16,66 
 
 
 
 
 
 
 
 
 Max Z=2.(3,35)+3(3,33)=16,66 
 
 5/13 
 
 
 
 
 
 
Método Simplex 
 
5) Resolva o exemplo de um modelo abaixo utilizando as regras e tabelas do simplex. 
Apresentar as tabelas do simplex para validação da resposta (fazer a mão). 
Maximizar Z = 4x1 + 3x2 
 
 Sujeito a: 
 
 
 
 Transformação das funções objetivas e restrições 
3x1 + 2x2 ≤ 15 Z -4x1 -3x2=0 
2x + x2 ≤ 8 3x1+2x2+F1=15 
x2 ≤6 2x+x2+F2=8 
x1 , x2 ≥ 0 x2+F3=6 
 
 
Montagem da tabela 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 -4 -3 0 0 0 0 LINHA Z 
F1 0 3 2 1 0 0 15 LINHA F1 
F2 0 2 1 0 1 0 8 LINHA F2 
F3 0 0 1 0 0 1 6 LINHA F3 
 
Definição da variável que entra na base, menor valor da linha Z 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 -4 -3 0 0 0 0 LINHA Z 
F1 0 3 2 1 0 0 15 LINHA F1 
F2 0 2 1 0 1 0 8 LINHA F2 
F3 0 0 1 0 0 1 6 LINHA F3 
 
 
Definição da variável que sai da base (calculo do quociente) 
 ENTRA 
BASE X1 SOLUÇÃO RAZÃO 
F1 3 15 X1=15/3=5 
 6/13 
 
 
F2 2 8 X1=8/2=4 
F3 0 6 X1=2/0 
 
Definição do elemento pivô 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 -4 -3 0 0 0 0 
F1 0 3 2 1 0 0 15 
F2 0 2 1 0 1 0 8 LINHA PIVÔ 
F3 0 0 1 0 0 1 6 
 
Alteração do elemento pivô 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 -4 -3 0 0 0 0 
F1 0 3 2 1 0 0 15 
X1 0 1 01/fev 0 01/fev 0 4 LINHA PIVÔ 
F3 0 0 1 0 0 1 6 
 
 
 
Alteração dos elementos da coluna pivô 
Definição da nova linha X1=mantendo a linha x1 
Nova linha Z=linha atual-(coeficiente da linha pivô) * (nova linha pivô) 
Z=(1;(-4);(-3);0;0;0;0;0)-(-4).(0;1;1/2;0;1/2;0;4)=Z(1;0;(-1);0;2;0;16). 
Nova tabela 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 0 -1 0 2 0 16 
F1 0 0 1/2 1 -3/2 0 3 
X1 0 1 1/2 0 1/2 0 4 
F3 0 0 1 0 0 1 6 
 
Análise da nova linha Z 
 ENTRA 
BASE X2 SOLUÇÃO RAZÃO 
F1 1/2 3 F1=0,5/3=6 
X1 1/2 4 X1=0,5/4=8 
F3 1 6 F3=6/1=6 SAI DA BASE 
 
 7/13 
 
 
Novo elemento pivô =1, encontrar as novas linhas (Z,X1,F3) elemento 
BASE Z X1 X2 F1 F2 F3 SOLUÇÃO 
Z 1 0 0 0 2 0 22 
F1 0 0 0 1 -3/2 - 1/2 0 
X1 0 1 1/2 0 1/2 - 1/2 1 
F3 0 0 1 0 0 1 6 
 
A Solução é ótima pois não existe a presença de elementos negativos na linha Z 
Logo, X1=1 e X2=3 
Na função Objetivo temos: Max Z =4.1 +3.6 =22 
 
 
 
 
 
 
 
 
Análise de Sensibilidade e Dualidade 
 
6) A ElectraPlus produz dois tipos de motores elétricos em duas máquinas. Uma unidade do 
motor 1 requer duas horas na máquina 1 e uma hora na máquina 2. Para o motor 2, uma 
unidade requer uma hora da máquina 1 e três horas da máquina 2. As receitas por unidade dos 
produtos 1 e 2 são $30 e $20, respectivamente. O tempo de processamento diário disponívelpara cada máquina é oito horas. 
Desta forma, representando o número diário de unidade dos motores 1 e 2 por x1 e x2, 
respectivamente, o modelo de programação linear é dado como: 
 
 
Max z = 30x1 + 20x2 
 
Sujeito a 
2x1 + x2 ≤ 8 (máquina 1) 
x1 + 3x2 ≤ 8 (máquina 2) 
x1, x2 ≥ 0 ( não-negatividade) 
 
 8/13 
 
 
 
 
Logo, pede-se: 
(a) Determine o mix ótimo de produção diária. 
Determinação dos pontos para os valores (0,0) 
1.2x+x2=8 2.x1+3x2=8 Ponto teste da região factível (1,1) 
A(0, 8) D(0,2,67) 2.1+1≤ 8=3≤ 8 -Verdadeiro 
B(4, 0) E(8, 0) 1+3≤8=4 ≤ 8 - verdadeiro 
 
Determinação do ponto C que se dá na intersecção das retas I e II 
Resolvido pelo sistema de equação 
(i) 2x1+x2 =8 
(ii) X1+3x2 =8 
Isolado x1 para encontrar o valor de x2 
Escolhido a ii equação x1=8.3x2 
Substituido x1 na equação i 
2(8+3x2)+x2 =8 
X2 =8/5 =1,6 
 
 
 
 
Trocado o valor de x2 na equação isolada x1 =8-3.(1, 
6)= 3,2 
Logo, ponto C (3,2 ; 1,6) 
TESTANDO SO VALORES DE Z: 
Ponto D(0,2,67) 
30x1+20x2=30.0+20.(2,67)=53,4 (Valor do ponto C(3,2 ;1,6)=128 (Valor de Z) 
Ponto B(4,0) 
30.4+20.0=120(Valor de Z) 
Solução ótima/:Z=128;x1=3,2 e x2=1,6 
 
 9/13 
 
 
 
 
(b) A Electraplus decidiu realizar alterações na máquina 1 em relação a capacidade de horas de 
8 horas para 9 horas diária. Use análise de sensibilidade para determinar se a solução ótima 
permanecerá inalterada e determine o seu preço dual. 
Max Z =30x1.20x2 Max Z=30x1+20x2 
Sujeito a Sujeito a 
2x1+x2≤8 (máqina1) 2x1+x2≤ 9(máquina 1) 
X1+3x2≤8(máquina 2) x1+3x2≤ 8(máquina2) 
X1, x2≤0(não negatividade) x1, x2 ≥ 0 (não negatividade) 
 
Pontos a considerar usando como referência os valores (0,0) 
1. 2x1+x2 = 9 2. X1+3x2 = 8 
A(0, 9) D(0,2,67) 
B(4,5,0) E (8,0) 
Determinando os pontos usandoa referencia dos valores (0,0) 
3.2x1+x2=9 2.x1+3x2=8 
G(0,9) D(0,2,67) 
H(4,5,0) E(8,0) 
Ponto F (intersecção das retas 2 e 3) 
ENTÃO 
 
 
Se a capacidade diária da máquina 1 for aumentada de 08 para 09 horas, a solução antes 
que era em C ocorrerá agora em F. 
 
 
 
 
 
 
 
 
A 
B 
C 
F 
 10/13 
 
 
 
 
 
Para determinar o ponto F(intersecção das retas 2 e 3) 
(i) 2x1+x2=9 
(ii) X1+3x2=8 
Isolando o x1 encontra-se o valor de x2 
Escolhido a reta ii=x1=(8-3x2) 
Substituido na equação i 
2.(8-3x2)+x2=9 
X2=1,4 
p/x1=8-(3.1,4)=3.8 
Ponto F(3,8;1,4) 
Conclusão 
Ponto F(3,8 ;1,4) 
Substituir na função objetivo: 
Z=30.3,8+20.1,4=142 
 
 
 
 
 
DETERMINAÇÃO DO PREÇO DUAL 
 
Conclusão : O preço dual pode ser determinado através da taxa de variação na receita resultante 
do aumento de uma hora na capacidade da máquina do ponto C para o ponto F, logo 
temos,$14/h. Isso significa que uma unidade de aumento na capacidade da máquina 1 
aumentará a receita em $14. 
 
 11/13 
 
 
Faixa de aplicabilidade: 
Em realação as varieções na capacidade da máquina 1 
 
Capacidade mínima da máquina 1(em D=0, 2.67))=2x0+1x2.67=2.67/h 
Capacidade máxima da máquina 1(em E=(8,0))=2x8+1x0=16/h 
Conclusão Preço dual permanecerá válido para a faixa. 
2.67/h≤16/h 
Fora dessa faixa produzirão um preço dual(equivalente por unidade) diferente 
 
 
7) Escreva o dual dos problemas primais abaixo: 
 
a) Min Z = 10x1 + 20x2 Max W=3y1+60y2 
Sujeito a: Sujeito a: 
x1 + 2x2 ≥ 3 Y1+2y2 ≤ 10 
2x1+ 5x2 ≥ 60 2Y1+5Y2 ≤ 20 
x1, x2 ≥ 0 Y1,Y2 ≥ 0 
 
 
 
 
 
b) Max Z = 5x1 + 6x2 Max W=5y1+3y2+8y3 
Sujeito a: Sujeito a: 
x1 + 2x2 ≤ 5 Y1+y2+4y3 ≥ 5 
x1 + 5x2 ≤ 3 2Y1+5Y2+7Y3 ≥ 6 
4x1 + 7x2 ≤ 8 2Y+5Y2+7Y3 ≥ 6 
x1, x2 ≥ 0 Y1, Y2, Y3 ≥ 0 
 
 
 
 
 
 
 
 
 
 
 12/13 
 
 
 
 
 
Problemas com transporte 
 
 
8) A prefeitura de Dourados está fazendo obras em três bairros. O material para essas obras é 
transportado de três depósitos O1, O2 e O3 de onde são retiradas 57, 76 e 93 toneladas de 
material, respectivamente. As obras são destinadas para os bairros D1, D2 e D3, que 
necessitam diariamente de 41, 80 e 105 toneladas, respectivamente. Os custos unitários para o 
transporte desse material estão na tabela a seguir. 
Tabela 01 - Custos Unitários dos Transportes (R$/unidade) 
 Destino 01 Destino 03 Destino 03 
Depósito 01 7 8 4 
Depósito 02 5 6 3 
Depósito 03 6 5 4 
 Pede-se para determinar: 
a) O modelo de transporte que minimiza o custo de transporte. 
Os depósitos podem transportar 57 + 76 + 93 =226 Toneladas 
Os pontos de destino recebem 41 + 80 + 105 =226 Toneladas 
Temos um sistema equilibrado! 
 Destino 01 Destino 02 Destino 03 
Depósito 01 X11 X12 X13 
Depósito 02 X21 X22 X23 
Depósito 03 X31 X32 X33 
 
Função objetivo: Minimizar C=7x11+8x12+4x13+5x21+6x21+3x23+6x31+5x32+4x33 
Função da disponibilidade de transporte dos depósitos e o recebimento dos pontos de 
destino. 
 Destino 01 Destino 02 Destino 03 
Depósito 01 X11 X12 X13 
Depósito 02 X21 X22 X23 
Depósito 03 X31 X32 X33 
Necessidade 
das demandas 
 
41 
 
80 
 
105 
 
 
 
Restrições da capacidade dos depósitos 
X11-X12-X13 ≤ 57 
X21+X22+X23 ≤ 76 
X31+X32+X33 ≤ 93 
 
 
 13/13 
 
 
 
 
Restrições da necessidade das demandas 
X11+X21+X31=40 
X12+X22+X32=80 
X13+X23+X33=105 
Restrições de não negatividades: 
X11, x12, ...X32, X33 ≥ 0 
 
b) O custo de transporte mínimo. 
Custo mínimo = CT = 57 * 4 + 28* 5 + 48* 3 + 13* 6 + 80*5 = R$ 990,00 
 
9) O problema da designação é um tipo especial de problema de programação linear em 
que os “designados” estão sendo indicados para a realização de tarefas. Diante da frase afirmada, 
cite pelo menos 02 exemplos reais onde utilizou-se problemas de designação, e explique a maneira 
como estes foram formulados. 
 
O numero de designados e o numero de tarefas são os mesmo, geralmente representado pela 
letra n. 
Cada uma das tarefas devem ser realizadas por um designado e sempre há um custo atrelado 
ao designado que executa a tarefa. 
O objetívo é determínar como todas as n desígnaçöes devem ser feitas 
para minimizar o custo total. 
De acordo com Taha (2008), a melhor pessoa para a tarefa é uma descrição adequada do 
problema de designação. A situação pode ser ilustrada pela designação de trabalhadores 
com graus variáveis de habilidade a determinadas tarefas. Uma tarefa que combine com a 
habilidade de um trabalhador custa menos do que uma tarefa para a qual o trabalhador não 
seja tão habilidoso. O objetivo do problema é determinar a designação de menor custo de 
trabalhadores a tarefas. 
O problema de designação é, na realidade, um caso especial do problema de transporte no 
qual os trabalhadores representam as origens e as tarefas representam os destinos. A 
quantidade fornecida (demandada) em cada origem (destino) é exatamente iguala 1. O 
custo de ‘transportar’ o trabalhador j para a tarefa j é Cjj. Na verdade, o problema de 
designação pode ser resolvido diretamente como um problema de transporte comum