APOL 2 PO

Prévia do material em texto

Disciplina Pesquisa Operacional 
Aula 2 
Professor Ricardo Zanardini 
 
 
 
 Objetivos do Estudo 
Olá! Seja bem-vindo à nossa segunda aula de Pesquisa Operacional! 
Na aula anterior, aprendemos o que é um problema de Programação Linear e como é possível formular 
problemas desse tipo. 
Nessa aula estudaremos como é possível resolver problemas de Programação Linear utilizando o método 
gráfico, o método Simplex e um software chamado WinQSB. 
Vamos acessar o material on-line e assistir ao vídeo do professor Ricardo no qual os conteúdos e 
objetivos da aula são melhor apresentados. 
 
 
Agora, para que possamos iniciar nossos estudos, vamos relembrar o problema da indústria de artigos de 
couro visto anteriormente. 
Acesse o material on-line e Leia atentamente o texto “Problema de Programação Linear”, pois 
vamos utilizar esse exemplo para que possamos apresentar diferentes formas de resolvermos um 
problema de programação linear. 
Inicialmente estudaremos o método gráfico. Sob o ponto de vista prático, não é um método muito 
eficiente, pois está limitado a duas variáveis. No entanto ele tem uma importância conceitual bastante 
forte. 
Por intermédio do método gráfico é possível visualizar um problema de PL bem como o significado 
geométrico das restrições e da função objetivo. 
 
 
Mas o que é o método gráfico e como ele pode ser utilizado? 
Para responder essa pergunta é importante que façamos a leitura do texto que está disponível no 
material on-line. Não deixe de acessar! Não perca, também, à aula do professor Ricardo para 
assimilarmos melhor esse conhecimento. 
Agora que vimos o que é o método gráfico e qual é o significado geométrico da função objetivo e das 
restrições, podemos aprender como é possível resolver um problema de programação linear utilizando o 
método Simplex. 
Acesse o material on-line e leia atentamente o texto chamado “Método Simplex”. Lá você encontrará, 
também um vídeo para para fixarmos melhor os passos do método Simplex. Confira o que o professor 
Ricardo preparou para você! 
 
Excelente! Agora sabemos como podemos resolver um problema de PL utilizando o método Simplex. 
Lembre-se, em caso de dúvidas, não hesite em retomar alguns pontos da aula! 
 
Software WinQSB 
Depois de ter visto os métodos gráfico e Simplex, veremos o software WinQSB, que é uma importante 
ferramenta para a resolução de problemas de Pesquisa Operacional. 
Em alguns casos, podemos resolver manualmente um problema de Programação Linear. 
No entanto, quanto maior for o número de variáveis e maior for o número de restrições, maior é o tempo 
e o esforço necessários para que possamos obter a solução de um problema de PL. 
 
 
 
Na prática, a imensa maioria dos problemas de pesquisa operacional é resolvida com o auxílio de algum 
software específico. O uso de softwares na pesquisa operacional é muito comum pois, além de agilizar a 
resolução dos problemas, diminui os possíveis erros que podem ser cometidos no processo de resolução 
desses problemas. 
Existem softwares bastante conhecidos no meio científico tais como GAMS, LINDO, LINGO, WinQSB... 
Alguns são gratuitos e outros não. A estrutura e funcionamento dos softwares destinados à resolução de 
problemas de pesquisa operacional é muito parecida entre eles. Em algumas empresas, devido à 
complexidade dos problemas ou às características particulares, é comum que haja a necessidade de se 
desenvolver um software específico, mas na maioria das vezes os softwares existentes já são suficientes 
para que os problemas possam ser resolvidos. 
 
Nas nossas aulas utilizaremos o software gratuito WinQSB que pode ser obtido clicando no link a seguir. 
http://winqsb.en.softonic.com/download#downloading 
Atualmente, a versão do WinQSB é a 2.0, que roda apenas em ambientes 32 bits. Ao clicar no link a 
seguir, você verá os passos necessários para a instalação do WinQSB. 
http://www.tantragyan.com/2013/11/download-and-install-winqsb-xp-windows7.html 
É claro que a escolha do software deve ser feita de modo que as necessidades sejam atendidas da 
melhor maneira possível. Uma alternativa muito interessante é o software denominado PO que foi 
desenvolvido pelo professor Mauricio Pereira dos Santos. 
O link para download do software e de outros materiais está a seguir. Clique e confira! 
http://www.mpsantos.com.br/ 
 
 
Vamos aprender então a resolver um problema de PL utilizando o WinQSB. É bem simples! Acesse o 
material on-line! 
Se preferir, o mesmo problema também pode ser resolvido utilizando o PO ou outro software. 
Para fixarmos melhor o que aprendemos, vamos acessar o material on-line e assistir ao vídeo do 
professor Ricardo explicando como podemos resolver problemas de PL utilizando o WinQSB. 
Depois de apreendermos o conteúdo desta aula e vermos as explicações do professor Ricardo, vamos 
colocar em prática nosso conhecimento resolvendo os exercícios propostos que estão ao final deste 
material. Depois verifique se as respostas estão de acordo com o esperado. 
 
Resumo 
Nessa aula aprendemos a resolver um problema de PL de maneiras diferentes: pelo método gráfico, pelo 
método Simplex e também através do uso de um software, em particular, o WinQSB. 
Para saber mais acesse os links a seguir: 
http://pt.wikipedia.org/wiki/Programação_linear 
http://www.marcogandra.com.br/2012/08/o-que-e-programacao-linear.html 
É importante também realizar a leitura dos capítulos 2, 3 e 4 da obra “Iniciação à pesquisa 
operacional no ambiente de gestão”, 2. Ed., dos professores Marcos Antônio Barbosa e Ricardo A. 
D. Zanardini, da editora Intersaberes. 
 
 
 
Se possível, resolva os exercícios propostos no final de cada capítulo. 
Outra sugestão de leitura são os capítulos 2 e 3 da obra “Pesquisa Operacional”, Hamdy A. Taha, da 
editora Pearson. 
Bons estudos! 
Exercícios 
1. Uma emissora de rádio está fazendo algumas alterações na programação com o intuito de 
aumentar a audiência. Para isso, pretende decidir o número de apresentações semanais de cada 
programa. O programa A, dedicado à música Pop, tem 50 minutos de música e 10 minutos de 
comerciais, atingindo uma audiência de aproximadamente 15000 espectadores. O programa B, 
dedicado à música clássica, tem 40 minutos de música e 20 minutos de comerciais, alcançando 
aproximadamente 22000 espectadores. A emissora, com esses programas, pretende ter pelo menos 
200 minutos semanais de comerciais e, no máximo, 900 minutos de música. Determine quantas 
vezes cada programa irá semanalmente ao ar de modo que a respectiva audiência semanal seja 
maximizada. 
 
 
2. Um comerciante possui uma loja de informática e precisa adquirir alguns produtos. A tabela a 
seguir apresenta informações importantes a respeito de cada produto a ser adquirido. 
Produto Preço de Custo Lucro Unitário Quant. Mínima Quant. Máxima 
Laptop R$ 470,00 R$ 200,00 10 
Tablet R$ 190,00 R$ 225,00 20 35 
Mouse R$ 9,00 R$ 10,00 
 
Sabendo que o capital disponível para a aquisição desses produtos é de R$ 25.000,00, determine 
quantas unidades devem ser compradas de cada produto de modo que o lucro referente à posterior 
venda desses produtos seja o maior possível. 
3. As seguintes informações se referem aos produtos de uma indústria de alimentos congelados. 
Produto Custo Unitário Lucro Unitário 
Quantidade de 
Carne de Frango 
Quantidade de 
Carne de Gado 
Hambúrguer R$ 4,00 R$ 5,00 350 g 
Quibe R$ 4,70 R$ 4,20 300 g 
Frango Empanado R$ 3,80 R$ 6,00 470 g 
Lasanha de Carne R$ 4,00 R$ 5,70 250 g 
Lasanha de 
Frango 
R$ 3,60 R$ 5,50 300 g 
 
 
 
Diariamente a indústria tem a seguinte disponibilidade dematéria-prima: 
 Carne de frango: 2.200 kg 
 Carne de gado: 3.700 kg 
Determine a solução ótima do problema sabendo que o propósito da indústria é determinar a 
produção de alimentos congelados que maximiza o lucro. 
 
4. Uma transportadora possui uma frota de caminhões e deseja otimizar a utilização mensal deles de 
tal maneira que o lucro total referente aos serviços prestados seja o maior possível. A 
transportadora possui, atualmente, os seguintes veículos: 7 carretas, 12 caminhões médios e 8 
caminhões pequenos. Devido às atuais demandas, no quadro de funcionários há 20 motoristas e 48 
ajudantes. Cada veículo, para trafegar, precisa de 1 motorista. O número de ajudantes depende do 
tipo de veículo: 1 para cada caminhão pequeno, 2 para cada caminhão médio e 3 ajudantes para 
cada carreta. Independentemente da distância a ser percorrida ou da quantidade de carga a ser 
transportada, o lucro mensal de cada carreta corresponde a R$ 3400,00. O lucro mensal de cada 
caminhão médio corresponde a R$ 2200,00 e de cada caminhão pequeno, R$ 1500,00. Formule o 
problema como um problema de PL e encontre a solução ótima. 
 
 
 
5. Resolva os seguintes problemas de PL: 
a. max z=200x1+300x2+340x3 
S.A. 2x1+2x2+5x3<=733 
 2x1+3x2 >=100 
 2x1 <= 77 
 x2 <= 20 
Variáveis contínuas 
 
b. max z=70x1+40x2 
S.A. 33x1+14x2<=2200 
 4x1+17x2<=1344 
Variáveis contínuas 
 
 
 
Gabarito 
1. 
Solução: 
Variáveis: 
a = Quantidade de repetições semanais do programa A 
b = Quantidade de repetições semanais do programa B 
 
Formulação: 
max aud = 15000a+22000b 
S.A. 10a+20b>=200 (Comerciais) 
 50a+40b<=900 (Música) 
 a>=0, b>=0 
 Variáveis inteiras (Os programas irão ao ar em sua totalidade) 
 
 
 
Tela de entrada dos dados iniciais do WinQSB: 
 
 
Tela de entrada dos dados do problema: 
 
Obs.: Para, no WinQSB, alterar a desigualdade “<=” para “>=”, basta clicar duas vezes sobre o 
sinal “<=”. 
 
 
 
Solução ótima: 
 
 
a = 0 
b = 22 
aud = 484.000 
2. 
Solução: 
Variáveis: 
l = Quantidade de laptops 
t = Quantidade de tablets 
m = Quantidade de mouses 
 
 
 
 
Formulação: 
max L = 200l+225t+10m 
S.A. 470l+190t+9m<=25000 (Capital) 
 l >= 10 (Mínimo de laptops) 
 t >= 20 (Mínimo de tablets) 
 t <= 35 (Máximo de tablets) 
l>=0, t>=0, m>=0 
Variáveis inteiras 
 
Tela de entrada dos dados iniciais do WinQSB: 
 
 
 
 
Tela de entrada dos dados do problema: 
 
 
Solução ótima: 
 
 
 
l = 10 
t = 35 
m = 1.516 
L = R$ 25.035,00 
 
3. As seguintes informações se referem aos produtos de uma indústria de alimentos congelados. 
Produto Custo Unitário Lucro Unitário 
Quantidade de 
Carne de Frango 
Quantidade de 
Carne de Gado 
Hambúrguer R$ 4,00 R$ 5,00 350 g 
Quibe R$ 4,70 R$ 4,20 300 g 
Frango Empanado R$ 3,80 R$ 6,00 470 g 
Lasanha de Carne R$ 4,00 R$ 5,70 250 g 
Lasanha de Frango R$ 3,60 R$ 5,50 300 g 
 
 
 
Diariamente a indústria tem a seguinte disponibilidade de matéria-prima: 
 Carne de frango: 2.200 kg 
 Carne de gado: 3.700 kg 
Determine a solução ótima do problema sabendo que o propósito da indústria é determinar a 
produção de alimentos congelados que maximiza o lucro. 
 
Solução: 
Variáveis: 
h = Quantidade de hambúrgueres 
q = Quantidade de quibes 
fe = Quantidade de frangos empanados 
lc = Quantidade de lasanhas de carne 
lf = Quantidade de lasanhas de frango 
 
 
 
Formulação: 
max L = 5h+4,2q+6fe+5,7lc+5,5lf 
S.A. 0,47fe+ 0,3lf<=2200 
 0,35h+0,3q+ 0,25lc <=3700 
 h>=0, q>=0, fe>=0, lc>=0, lf>=0 
Variáveis inteiras 
 
 
 
 
Tela de entrada dos dados iniciais do WinQSB: 
 
 
 
 
Tela de entrada dos dados do problema: 
 
 
Solução ótima: 
 
 
h = 0 
q = 0 
fe = 0 
lc = 14.800 
lf = 7.333 
L = R$ 124.691,50 
 
4. Uma transportadora possui uma frota de caminhões e deseja otimizar a utilização mensal deles de 
tal maneira que o lucro total referente aos serviços prestados seja o maior possível. A 
transportadora possui, atualmente, os seguintes veículos: 7 carretas, 12 caminhões médios e 8 
caminhões pequenos. Devido às atuais demandas, no quadro de funcionários há 20 motoristas e 48 
ajudantes. Cada veículo, para trafegar, precisa de 1 motorista. O número de ajudantes depende do 
tipo de veículo: 1 para cada caminhão pequeno, 2 para cada caminhão médio e 3 ajudantes para 
cada carreta. Independentemente da distância a ser percorrida ou da quantidade de carga a ser 
transportada, o lucro mensal de cada carreta corresponde a R$ 3400,00. O lucro mensal de cada 
caminhão médio corresponde a R$ 2200,00 e de cada caminhão pequeno, R$ 1500,00. Formule o 
problema como um problema de PL e encontre a solução ótima. 
 
 
 
Solução: 
Variáveis: 
c = Quantidade de carretas 
m = Quantidade de caminhões médios 
p = Quantidade de caminhões pequenos 
 
max L = 3400c+2200m+1500p 
S.A. 1c+1m+1p<=20 (Motoristas) 
 3c+2m+1p<=48 (Ajudantes) 
 c <= 7 (Quantidade máxima de carretas) 
 m <=12 (Quantidade máxima de caminhões médios) 
 p<= 8 (Quantidade máxima de caminhões pequenos) 
c>=0, m>=0,p>=0 
Variáveis inteiras 
 
 
 
Tela de entrada dos dados iniciais do WinQSB: 
 
 
Tela de entrada dos dados do problema: 
 
 
 
 
Solução ótima: 
 
 
c = 7 
m = 12 
p = 1 
L = R$ 51.700,00 
 
 
 
5. 
a. 
 
 
 
 
 
x1 = 38,5 
x2 = 20 
x3 = 123,2 
z = 55.588 
 
 
 
b. 
 
 
 
 
x1 = 36,8 
x2 = 70,4 
z = 5.392