X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
ESTRATÉGIAS DE RESOLUÇÃO DE PROBLEMAS DE PESQUISA
OPERACIONAL
André Luis Trevisan
Universidade Tecnológica Federal do Paraná
[email protected]
Magna Natalia Marin Pires
Universidade Estadual de Londrina
[email protected]
Resumo:O objetivo deste minicurso é apresentar alguns problemas da Pesquisa
Operacional, com destaque àqueles que podem ser abordados no Ensino Médio. Por estar
alicerçada na modelagem matemática e fazer uso de situações-problema que fazem parte
da realidade, a Pesquisa Operacional mostra-se como um tópico que contribui tanto para o
desenvolvimento do raciocínio matemático do aluno quanto para a formação e capacitação
dos professores de Matemática. A partir das soluções apresentadas pelos participantes
pretende-se discutir estratégias de resoluções de problemas que podem ser ensinadas nas
aulas de matemática.
Palavras-chave: Resolução de Problemas; Pesquisa Operacional; Estratégias; Educação
Matemática.
AS ESTRATÉGIAS DE RESOLUÇÃO DE UM PROBLEMA
É fato que uma das estratégias de ensino da Matemática consiste na utilização da
Resolução de Problemas em sala de aula, como forma para um processo ensino e
aprendizagem que ofereça uma melhor compreensão da matéria por parte dos alunos.
Nesse sentido, a resolução de problemas, inserida em um ensino baseado em um processo
constante de construção de conhecimentos pode constituir como um modo de conceber as
atividades educativas.
A Resolução de Problemas, assim chamada porque considera que o estudo da
Matemática é resolver problemas, pode ser um bom caminho para fazer com que os alunos
construam novos conceitos matemáticos, participem mais ativamente das aulas, e vejam a
Matemática útil e prazerosa.
Neste minicurso, pretendemos apresentar estratégias diferentes de solução de um
mesmo problema a partir das soluções dadas pelos participantes.
Anais do X Encontro Nacional de Educação Matemática
Minicurso
1
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
Segundo MUSSER e SHAUGHNESSY (1997), tentativa-e-erro, padrões, resolver
um problema mais simples, trabalhar em sentido inverso e simulação são algumas
estratégias de resolução de problemas.
Segue algumas particularidades de cada uma das estratégias mencionadas:

tentativa-e-erro: envolve simplesmente a aplicação das operações pertinentes às
informações dadas;

padrões: generaliza a partir de casos particulares dos problema para chegar a
solução;

resolver um problema mais simples: pode envolver a resolução de um caso
particular de um problema, ou um recuo temporário de um problema
complicado para uma versão resumida;

trabalhar em sentido inverso: parte do objetivo, ou do que deve ser provado, e
não dos dados;

simulação: compreende em preparar e realizar um experimento, coletar dados e
tomar uma decisão baseada em uma análise de dados.
PESQUISA OPERACIONAL
Conforme nos colocam HILLIER e LIEBERMAN (2006), desde o advento da
Revolução Industrial, o mundo presencia um crescimento extraordinário no tamanho e na
complexidade das organizações. As pequenas oficinas de artesãos de outrora evoluíram
para as corporações bilionárias de hoje. Um fator crucial dessa mudança foi o
extraordinário aumento na divisão do trabalho e a segmentação das responsabilidades
gerenciais nessas organizações. Entretanto, junto com seus pontos positivos, essa crescente
especialização criou problemas novos, problemas estes que ainda ocorrem em muitas
organizações. À medida que aumentam a complexidade e a especialização em uma
organização, torna-se cada vez mais difícil alocar os recursos disponíveis para as diversas
atividades da maneira mais eficiente para a organização como um todo. Esses tipos de
problemas e a necessidade de encontrar o melhor caminho para solucioná- las criaram
condições necessárias para o surgimento da Pesquisa Operacional (comumente referida
como PO).
Anais do X Encontro Nacional de Educação Matemática
Minicurso
2
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
RESOLUÇÃO DE PROBLEMAS COM MODELOS MATEMÁTICOS
A pesquisa operacional e, em particular, a programação matemática tratam de
problemas de decisão e fazem uso de modelos matemáticos que procuram representar o
problema real. Segundo ARENALES et al (2007), para formular um modelo matemático,
simplificações razoáveis do sistema ou problema real precisam ser consideradas e a
validação deste modelo depende da coerência entre uma solução e o contexto original.
Variáveis (incógnitas) são definidas e relações matemáticas entre essas variáveis
são estabelecidas de forma a descrever o comportamento do sistema. O modelo
matemático é resolvido (isto é, são determinados valores para as incógnitas, produzindo
soluções que dependem dos dados do problema) e o passo seguinte consiste na validação
do modelo, isto é, verificar se as soluções obtidas pela resolução do modelo matemático,
para diversas situações alternativas (por exemplo, alterando-se dados do problema como
demandas, custos, etc) são compatíveis com a realidade.
A abordagem de resolução de um problema por meio da pesquisa operacional pode
ser sintetizada nas seguintes fases: (i) definição do problema; (ii) construção do modelo;
(iii) solução do modelo; (iv) validação do modelo e (v) implementação da solução.
EXEMPLOS ILUSTRATIVOS
Na Pesquisa Operacional, trabalhamos com situações cujo objetivo é encontrar a
melhor solução, que chamamos de solução ótima. Por exemplo, podemos objetivar
encontrar o maior lucro, ou o menor custo possível em determinada situação. No caso do
lucro, desejamos encontrar o lucro máximo, por isto também chamamos esses tipos de
problemas de problemas de maximização. Já se nosso objetivo é obter um custo mínimo
de produção, temos um problema de minimização. De forma geral, uma situação que exige
a obtenção de uma melhor solução para determinada função é um problema de otimização.
Para ilustrar a aplicação da Pesquisa Operacional na formulação de problemas,
consideremos os exemplos descritos a seguir, construindo, passo a passo, o modelo
matemático em cada um deles.
Anais do X Encontro Nacional de Educação Matemática
Minicurso
3
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
Num primeiro momento, abordaremos Problemas de Otimização Combinatória, ou
seja, problemas cujas variáveis são inteiras ou apenas 0 ou 1, tornando o conjunto de
possíveis soluções muito grande. Tais problemas podem ser abordados através de métodos
que levam em conta sua formulação ou por métodos heurísticos ou exatos de busca em
árvores ou grafos.
Na segunda etapa, trabalharemos com problemas de Programação Linear com duas
variáveis de decisão, cuja resolução será feita por meio de procedimento gráfico, e cuja
solução será determinada explorando a função objetivo e as regiões definidas por
inequações que representam as restrições do problema.
Durante as 1ª e 2ª etapas, descritas anteriormente, serão discutidas as estratégias
utilizadas pelos participantes do minicurso.
A última etapa será destinada a classificação das estratégias utilizadas, tomando
como parâmetro a classificação proposta por MUSSER e SHAUGHNESSY (1997). Nesta
etapa poderão ser desenvolvidas outras solução para os problemas trabalhados.
Problema 11 : João foi fazer compras no Paraguai e deseja obter o máximo de lucro
com as futuras vendas. Porém, ele só pode levar no ônibus 20 kg de produtos e tem
garantido a compra de uma e apenas uma unidade de cada produto. Ajude João a selecionar
quais produtos comprar para obter o máximo de lucro, levando em conta os dados da
tabela 1.
Tabela 1: Peso e lucro dos itens
1
Item
Peso (Kg)
Lucro (R$)
DVD
4
60
TV
Monitor LCD
Jogos Eletrônicos
Computador
Calculadora
Filmadora
Máquina Fotográfica
10
6
2
15
2
8
2
200
100
55
300
100
130
60
Adaptado de SALLES NETO (2006).
Anais do X Encontro Nacional de Educação Matemática
Minicurso
4
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
Problema 22 : A mãe de Tiago torceu um pé, mas as compras para o jantar têm de
ser feitas. A lista que a mãe do Tiago fez contempla idas aos seguintes locais: açougue (A),
mercearia (M), frutaria (F) e padaria (P). Tiago também precisa de um sapato novo e de
dois livros para a escola e, por isso, tem de passar na sapataria (S) e na livraria (L). Tome
como pontos os locais onde Tiago tem de ir e desenhe um trajeto que Tiago poderá
percorrer de modo a visitar cada um desses locais e regressar novamente a casa (C),
tomando por base a figura 1.
Figura 1: Esquema para o problema 2. Figura extraída de COSTA
a) sem restrições;
b) sabendo que quer ir primeiro à livraria;
c) sabendo que só vai ao açougue imediatamente antes de ir para casa.
Problema 33 : No esquema seguinte estão representadas as ligações entre cidades
asseguradas por uma companhia de ônibus, bem como as distâncias entre elas (em km).
Supondo que o ônibus sai da cidade A, qual é o percurso mais curto que lhe permite passar
por todas as cidades e regressar à A, conforme a figura 2?
2
3
Adaptado de COSTA.
Adaptado de COSTA.
Anais do X Encontro Nacional de Educação Matemática
Minicurso
5
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
Figura 2: Esquema para o problema 3. Figura extraída de COSTA
Problema 44 : Um vendedor de material de informática tem de visitar empresas em
diversos locais do país. No grafo seguinte estão indicadas as cidades a visitar, bem como as
distâncias entre elas (em km). Escolhendo um vértice qualquer como ponto de partida, qual
é o percurso que representa a menor distância a ser percorrida, conforme a figura 3?
Figura 3: Esquema para o problema 4. Figura extraída de COSTA
4
Adaptado de COSTA.
Anais do X Encontro Nacional de Educação Matemática
Minicurso
6
X Encontro Nacional de Educação Matemática
Educação Matemática, Cultura e Diversidade
Salvador – BA, 7 a 9 de Julho de 2010
Problema 55 : Uma confeitaria produz dois tipos de bolos de sorvete: chocolate e
creme. Cada lote de bolo de chocolate é vendido com um lucro de $3 e os lotes de creme
com o lucro de $1. Contratos com várias lojas impõem que sejam produzidos no mínimo
10 lotes de bolo de chocolate por dia e que o total de lotes fabricados nunca seja menor do
que 20. O mercado só é capaz de consumir até 40 bolos de creme e 60 de chocolate. As
máquinas de preparação de sorvete disponibilizam 180 horas de operação, sendo que cada
lote de bolos de chocolate consome 2 horas de trabalho e cada lote de bolos de creme 3
horas. Determinar o esquema de produção que maximize os lucros com a venda dos bolos
de sorvete.
Algo mudaria em sua solução de tivéssemos disponíveis 185 horas de operação?
REFERÊNCIAS
ARENALES, Marcos et. al. Pesquisa operacional. Rio de Janeiro: Elsevier, 2007.
COSTA, Álvara. Grafos hamiltonianos. Disponível em
http://w3.math.uminho.pt/~fmena/grafos.pdf . Acesso em: 15 mar. 2010.
HILLIER, F. S., LIEBERMAN, G. J. Introdução à pesquisa operacional. São Paulo:
McGraw-Hill, 2006.
MUSSER G.L. e SHAUGHNESSY J. M. Estratégias de resolução de problemas na
matemática escolar. In: KRULIK, S. e REYS, R. E. A resolução de proble mas na
matemática escolar. São Paulo: Atual, 1997. p.188 – 201.
SALLES NETO, Luiz Leduíno de. Tópicos de pesquisa operacional para o ensino médio.
In: III Bienal da Sociedade Brasileira de Matemática, 2006. Disponível em
http://www.mat.ufg.br/bienal/2006/mini/leduino.pdf . Acesso em: 08 mai. 2009.
SOUZA, Marcone Jamilson Freitas. Otimização combinatória. Disponível em
http://www.decom.ufop.br/prof/marcone . Acesso em: 15 mar. 2010.
5
Adaptado de SOUZA.
Anais do X Encontro Nacional de Educação Matemática
Minicurso
7