Unidade 1 - Programação Matemática

Prévia do material em texto

Pesquisa Operacional I 
 
13 
 
O que é a Pesquisa Operacional? 
 
A origem histórica da Pesquisa Operacional (PO) foi realizada por indivíduos 
como Charle Baggage. Sua pesquisa foi sobre o custo de transporte e triagem do 
correio para a "Penny Post" da Inglaterra universal em 1840, e estudos sobre o 
comportamento dinâmico de veículos ferroviários em defesa de bitola larga do 
GWR. Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre 
problemas em física na década de 1920 e, mais tarde, tentar estender estes para as 
ciências sociais. 
A Pesquisa Operacional moderna teve origem na Estação de Pesquisa Bawdsey 
no Reino Unido em 1937 e foi o resultado de uma iniciativa do superintendente da 
estação, AP Rowe. Rowe concebeu a ideia como um meio para analisar e melhorar 
o funcionamento do sistema de radar de alerta, nos seus primórdios, no Reino 
Unido, Chain Home (CH). Inicialmente, ele analisou o funcionamento do 
equipamento de radar e de suas redes de comunicação, expandindo 
posteriormente para incluir o comportamento do pessoal de operação. Isto revelou 
limitações não reconhecidas da rede CH e permitiu medidas corretivas a tomar. 
O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares na 
Segunda Guerra Mundial. Por conta do esforço requerido pela guerra na alocação de 
recursos escassos às várias operações militares e às atividades dentro de cada 
operação de uma maneira efetiva, várias seções de pesquisa operacional foram 
estabelecidas nas forças armadas britânicas. Logo depois, esses esforços similares 
foram empreendidos nos Estados Unidos. Muitos cientistas foram reunidos para 
aplicar uma abordagem científica a problemas estratégicos e táticos. Esses cientistas 
foram chamados a realizar “pesquisas operacionais militares”, daí vem o nome. 
Um passo natural tomado foi estender o sucesso da Pesquisa Operacional nos 
esforços de guerra para as organizações civis. A indústria pós-guerra havia crescido 
muito e se deparava com os problemas causados pela crescente complexidade das 
organizações. Vale lembrar que após a guerra houve inúmeros movimentos para a 
reconstrução dos países arrasados. Os problemas que apareceram durante a guerra 
e a complexidade das organizações na reconstrução dos países eram muito 
Pesquisa Operacional I 
 
14 
semelhantes, porém em um contexto diferente. Em 1948, o Massachusetts Institute 
of Tecnology (MIT) instituiu o primeiro programa formal de estudos em Pesquisa 
Operacional para campos não militares. A “idade de ouro” da PO vai de 1945 até 
meados da década de 1970, devida à rápida expansão. 
Dois fatores foram cruciais para o crescimento da PO naquele período: O 
primeiro foi o avanço na melhoria nas técnicas de PO e na formulação dos 
problemas - Ex. o método simplex para resolver problemas de programação linear. 
O segundo foi a popularização dos computadores. 
 
Problemas de otimização 
 
A construção de modelos. 
O desafio da PO é transformar um problema real de produção ou de processo 
em um modelo matemático que reproduza fielmente essa realidade; destacar as 
variáveis que se queira controlar - variáveis essas que estão sujeitas a restrições de 
ordem técnica; validar o modelo matemático e implementá-lo. Para facilitar nosso 
estudo vamos dividir esse problema em etapas: 
 Definição da situação-problema; 
 Formulação de um modelo quantitativo; 
 Resolução do modelo e encontro da melhor solução; 
 Consideração de fatores imponderáveis; 
 Implementação da solução. 
 
Agora vamos ver cada uma destas etapas. 
Definição da situação-problema 
Nessa fase os gerentes do projeto deverão discutir o problema de forma mais 
clara e coerente, definir o escopo do projeto, definir os objetivos a serem 
alcançados e quais são os possíveis caminhos a seguir. 
Pesquisa Operacional I 
 
15 
As limitações técnicas devem ser levantadas e as relações deste sistema com 
os demais da empresa ou do ambiente externo. Sejam micro clientes ou micro 
fornecedores internos da corporação e stakeholders de outras organizações, com a 
finalidade de validar esse modelo. 
 
Formulação de um modelo quantitativo 
Em PO os modelos quantitativos são modelos matemáticos formados por um 
conjunto de equações e inequações. 
A eficiência do modelo é medida pela função objetivo, que pode ser de 
maximização ou de minimização. Por exemplo, maximizar o lucro ou minimizar o 
custo. Quanto melhor o valor obtido na função objetivo para cada solução 
proposta, melhor a eficiência do modelo: A solução ótima. 
 
Resolução do modelo e encontro da melhor solução 
Variáveis controladas ou de decisão: são aquelas cujo valor está sob o controle 
do administrador. Cabe a ele decidir um particular valor a cada uma dessas 
variáveis. Numa programação de produção uma possível variável a ser controlada 
pode ser a quantidade a ser produzida em um período de tempo, o que é 
competência do administrador. 
Variáveis não controladas: são aquelas cujos valores são arbitrados por 
sistemas fora do controle do administrador. Custos de produtos ou insumos, 
demanda de produtos, preços de mercado, são alguns exemplos desse tipo de 
variável. 
Podemos afirmar que um bom modelo é aquele que tem desempenho que 
mais chega próximo da realidade. O modelo deve ser rodado sempre, comparado 
com a realidade e revisado a fim de chegar o mais próximo possível dessa 
realidade. O modelo se torna mais fiel à realidade, incorporando características, 
com a adição de variáveis. 
 
 
Pesquisa Operacional I 
 
16 
Consideração de fatores imponderáveis 
Por outro lado, existem fatores que podem ser importantes, mas são difíceis de 
quantificar. O comportamento humano é um deles. A interação homem-máquina 
também. Faz-se necessário estimar o impacto desses fatores na solução que foi 
gerada pelo modelo matemático. Providências preliminares devem ser tomadas 
visando esses fatores. 
Implementação da solução 
Essa é a fase final. Deve ser apresentado ao administrador. A implantação deve 
ser acompanhada observando o comportamento do sistema com a solução 
adotada. Novos ajustes serão requeridos. É desejável que nessa fase do processo as 
pessoas que serão atingidas pelas mudanças estejam envolvidas. 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
 
Fonte: Adaptado de Moreira (2004 apud Moreira, 2010). 
Figura 1.1 – Processo de solução de um problema de Pesquisa Operacional. 
Pesquisa Operacional I 
 
17 
 
Programação Linear 
 
A programação linear é um dos mais populares modelos matemáticos 
estruturados utilizados para resolver problemas que apresentam variáveis que 
podem ser medidas e cujos relacionamentos podem ser expressos por meio de 
equações e/ou inequações lineares. As aplicações podem ser em vários campos das 
áreas científicas ou sociais, tais como administração da produção, análise de 
investimento, controle de estoque, economia, logística e etc. 
O modelo matemático de programações linear, que de agora em diante 
denominaremos de Problema de Programação Linear (PPL) é constituído de uma 
função objetivo linear; de restrições técnicas representadas por um grupo de 
equações e/ou inequações também lineares; e da restrição matemática de não 
negatividade (não pode ser negativa). 
Otimizar: 
),,,()( 21 nxxxfXf  – Função objetivo 
Sujeito a: 

















mnm
n
n
b
b
b
xxxg
xxxg
xxxg





2
1
21
212
211
),,,(
),,,(
),,,(
 
 
Onde: 
nnn xcxcxcxxxfXf   221121 ),,,()( 
),,1(
),,,( 33221121
mi
xaxaxaxaxxxg niniiini




 
 
Pesquisa Operacional I 
 
18 
 
n é o número de variáveis do problema 
m é o número de restrições do problema 
i é o índice de determinada restrição ),,1( mi  
j é o índice de determinada variável ),,1( nj  
jc é o coeficiente (constante) da variável jx , da função objetivo 
ija é o coeficiente (constante)na i-ésima restrição e da variável jx 
ib é constante da i-ésima restrição 
Um problema de programação linear está na sua forma padrão, quando o 
problema de otimização linear tiver as seguintes características: 
 A função objetivo deve ser minimizada ou maximizada; 
 As restrições do problema são definidas por um sistema de equações e/ou 
inequações lineares; 
 As condições de não negatividade de todas as variáveis de decisão 
complementam as restrições do problema. 
 
Matematicamente, podemos representar um problema na forma-padrão por: 
nnxcxcxcMaxZ  2211 
S.R. (Segundo as Restrições) 
11212111 bxaxaxa nn   
0,,, 21
2211
22222121







xx
bmxaxaxa
bxaxaxa
nmnmm
nn
 
 
Pesquisa Operacional I 
 
19 
Ou na forma reduzida: 
j
n
j j
xcMaxZ   1 
S.R. 
ij
n
j ij
bxa  1 ),,1( mipara  
0,,, 21 nxxx  
 
Agora iremos introduzir alguns termos: 
 Solução: qualquer valor obtido dentro do domínio da função objetivo, 
)(Xf , para as variáveis de decisão; 
 Solução viável: são soluções que satisfaçam todas as restrições; 
 Solução ótima: uma solução viável que tenha o melhor valor da função 
objetivo, )(Xf , isto é, que maximiza ou minimiza a função objetivo, 
podendo ser única ou múltipla; 
 Proporcionalidade: o valor da função objetivo é diretamente proporcional 
ao valor de cada variável de decisão. 
 
Formulação do Problema 
 
Não há uma regra fixa para a construção do modelo matemático. Mas a 
maioria dos problemas de programação linear (PPL) segue um roteiro que norteia o 
raciocínio. Veremos a seguir um roteiro básico em quatro etapas: 
1.Definir as variáveis de decisão ),,1( njxj  . Se estivermos estudando 
uma programação da produção, as variáveis de decisão podem representar as 
quantidades produzidas de produtos; se for uma programação de investimento, as 
variáveis representarão o tipo de portfólio escolhido. 
Pesquisa Operacional I 
 
20 
2.Definir a função objetivo da tomada de decisão. Que pode ser maximizar 
lucro, minimizar custos e etc. Ela é uma expressão formada por uma combinação 
linear das variáveis de decisão. 
3.Definir as restrições técnicas as quais estará sujeito. Como por exemplo, 
quantidade em estoque; homem-hora disponível na produção; 
4.A não negatividade. Sempre. 0,,, 21 nxxx  
Exemplo 1.1: 
Na fábrica de Brinquedos Eletrônicos X-Playhouse, são produzidos dois tipos 
de brinquedos: B1 e B2. O setor de contabilidade e custos informa que o lucro 
unitário do brinquedo B1 é de R$ 20,00 e do brinquedo B2 é de R$ 35,00. Na linha de 
produção o brinquedo B1 consome 2 horas e o brinquedo B2 consome 4 horas de 
trabalho. Essa linha de montagem tem 24 horas de trabalho disponíveis por dia. 
Sabe-se ainda que a demanda esperada pelo brinquedo B1 é de 8 unidades e de B2 
é de 4 unidades por dia. Como o engenheiro de produção da fábrica Brinquedos 
Eletrônicos X-Playhouse, monte o plano de produção de forma que o lucro seja 
maximizado. 
Solução: 
1. Comece definindo as variáveis de decisão, ou seja, as quantidades a 
serem produzidas de cada brinquedo. 
1x = quantidade de B1 a produzir; 
2x = quantidade de B2 a produzir; 
2. Formule a função objetivo que irá maximizar o lucro da empresa. 
O objetivo é maximizar o lucro, que pode ser calculado da seguinte 
forma: 
Lucro auferido com a venda de B1: 20 x 1x (lucro por unidade de B1 
vezes quantidade produzida de B1). 
 
Pesquisa Operacional I 
 
21 
Lucro auferido com a venda de B2: 35 x 2x (lucro por unidade de B2 x 
quantidade produzida de B2). 
Então o lucro total obtido será: 2121 3520);( xxxxL  
Objetivo: 2121 3520);( xxxxLMax  
 
3. Sujeito às restrições técnicas: 
4
8
2442
2
1
21



x
x
xx
 
4. A não negatividade. 
0, 21 xx 
 
Convenção da solução 
 
A solução de um problema de programação linear, P.P.L., pode ter uma única 
solução ótima ou pode ter infinitas soluções ótimas, como veremos nos próximos 
capítulos. 
A função objetivo pode ser de maximização, por exemplo, maximizar o lucro 
de uma empresa; como pode ser de minimização, minimizar custos. 
As restrições técnicas podem ser =,  ou : se um insumo será utilizado em 
sua totalidade, a restrição será de igualdade (=); se um insumo que está estocado, 
então, esta restrição será ( ), porque ele vai até a quantidade que está disponível 
no estoque; se há a necessidade desse insumo ser pelo menos, então, esta restrição 
será ( ). 
 
 
Pesquisa Operacional I 
 
22 
Estamos encerrando a unidade. Sempre que tiver uma dúvida entre em 
contato com seu tutor virtual através do ambiente virtual de aprendizagem e 
consulte sempre a biblioteca do seu polo. 
 
É hora de se avaliar 
Lembre-se de realizar as atividades desta unidade de estudo. Elas irão 
ajudá-lo a fixar o conteúdo, além de proporcionar sua autonomia no processo de 
ensino-aprendizagem. 
 
 
Pesquisa Operacional I 
 
23 
 
Exercícios – Unidade 1 
 
1) Sobre a origem da Pesquisa Operacional, é correto afirmar que: 
a) Sua origem histórica foi realizada por indivíduos como Charle Baggage. 
b) Baggage pesquisou o custo de transporte e triagem do correio. 
c) Percy Bridgman trouxe a pesquisa operacional para dar suporte sobre 
problemas em física na década de 1920. 
d) TODAS as alternativas acima estão CORRETAS. 
e) TODAS as alternativas acima estão INCORRETAS. 
 
2) Considere as seguintes afirmações sobre a Pesquisa Operacional na era 
moderna: 
I- O termo “pesquisa operacional” foi atribuído a algumas iniciativas militares 
na Segunda Guerra Mundial. 
II- Até hoje a Pesquisa Operacional é utilizada apenas nas pesquisas militares. 
III- Dois fatores foram fundamentais para o crescimento da Pesquisa 
Operacional: o primeiro foi o avanço na melhoria nas técnicas de PO e na 
formulação dos, e o segundo foi a popularização dos computadores. 
 
São corretas as afirmações: 
a) I, apenas. 
b) I e II, apenas. 
c) I e III, apenas. 
d) TODAS as afirmações estão CORRETAS. 
e) TODAS as afirmações estão INCORRETAS. 
jhona
Realce
jhona
Realce
Pesquisa Operacional I 
 
24 
3) São etapas para a resolução de problemas de Pesquisa Operacional, 
EXCETO: 
a) Definição da situação-problema. 
b) Formulação de um modelo qualitativo. 
c) Formulação de um modelo quantitativo. 
d) Implementação da solução. 
e) Consideração de fatores imponderáveis. 
 
4) Sobre as etapas para a resolução de problemas de Pesquisa Operacional 
(PO), é INCORRETO afirmar que: 
a) Em PO os modelos quantitativos são modelos matemáticos formados por 
um conjunto composto tanto por equações, quanto por inequações. 
b) A eficiência do modelo é medida pela função objetivo, que pode ser de 
maximização ou de minimização. 
c) As variáveis controladas ou de decisão são aquelas cujo valor está sob o 
controle do administrador. 
d) Numa programação de produção uma possível variável a ser controlada 
pode ser a quantidade a ser produzida em um período de tempo. 
e) Custos de produtos ou insumos, demanda de produtos, preços de mercado, 
são alguns exemplos de variáveis controladas. 
 
5) Sobre a Programação Linear, é correto afirmar que: 
a) A função objetivo deve ser minimizada ou maximizada. 
b) A solução viável é aquela que maximiza ou minimiza a função objetivo. 
c) Uma solução ótima não precisa ser uma solução viável. 
d) TODAS as alternativas acima estão CORRETAS. 
e) TODAS as alternativas acima estão INCORRETAS. 
jhona
Realce
jhona
Realce
jhona
Realce
Pesquisa Operacional I 
 
25 
 
6) Certa fabrica produz dois produtos P1 e P2. O lucro unitário do produto P1 é 
de R$ 100,00, enquanto o lucro do produto P2 é de R$ 180,00. A empresa precisa de 
20 horas para fabricar uma unidade de P1 e de 30 horas para fabricar uma unidade 
de P2. O tempo de produção disponível para isso é de 1.200 horas. A demanda 
esperada para cada produto é de 40 unidades para P1 e 30 unidades para P2. Qual é 
oplano de produção para que a empresa maximize o seu lucro nesses itens? 
Considere: 
1x = quantidade de P1 a produzir; 2x = quantidade de P2 a produzir; 
a) 2121 180100);( xxxxLMax  
Restrições técnicas 
30
40
200.13020
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 2121 180100);( xxxxLMax  
Restrições técnicas 
60
50
200.13020
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 2121 3020);( xxxxLMax  
Restrições técnicas 
30
40
200.1180100
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 180100);( xxxxLMax  
jhona
Realce
Pesquisa Operacional I 
 
26 
 
Restrições técnicas 
30
40
200.13020
2
1
21



x
x
xx
 
e) 2121 180100);( xxxxLMax  
Restrições de não negatividade 0, 21 xx 
 
7) Um vendedor de legumes pode transportar 800 caixas de legumes para sua 
região de vendas. Ele necessita transportar 200 caixas de cenouras a R$ 20,00 de 
lucro por caixa, pelo menos 100 caixas de batata a R$ 10,00 de lucro por caixa, e no 
máximo 200 caixas de mandioca a R$ 30,00 por caixa. De que forma deverá ele 
carregar o caminhão para obter o lucro máximo? Considere: 
1x = quantidade de caixas de batata; 2x = quantidade de caixas de mandioca; 
a) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 4000200100);( 2121  xxxxLMax 
Pesquisa Operacional I 
 
27 
Restrições técnicas 
30
10
600
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 3010);( xxxxLMax  
Restrições técnicas 
200
100
800
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
e) 40003010);( 2121  xxxxLMax 
Restrições técnicas 
200
100
800
2
1
21



x
x
xx
 
Restrições de não negatividade 0, 21 xx 
 
8) Na fabricação de dois de seus produtos, uma empresa utiliza dois 
equipamentos que limitam a produção. Em um dado período de tempo, estão 
disponíveis 30 horas do equipamento 1 e 60 horas do equipamento 2. Para a 
fabricação de uma unidade do produto A, usa-se 1 hora do equipamento 1 e 2 
horas do equipamento 2. Já para uma unidade do produto B, são gastas 2 horas do 
equipamento 2. O equipamento 1 não toma parte na produção do produto B. Por 
outro lado, uma unidade do produto A leva a um lucro de R$120,00, enquanto cada 
unidade do produto B gera um lucro de R$ 52,00. Formule o modelo de 
programação linear para maximizar o lucro da empresa. Considere: 
1x = quantidade do produto A; 2x = quantidade do produto B; 
 
Pesquisa Operacional I 
 
28 
a) 2121 3060);( xxxxLMax  
Restrições técnicas 
30
12022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
b) 2121 52120);( xxxxLMax  
Restrições técnica s 
60
60
2
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
c) 2121 3060);( xxxxLMax  
Restrições técnicas 
30
60
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
d) 2121 52120);( xxxxLMax  
Restrições técnicas 
30
6022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
e) 2121 52120);( xxxxLMax  
Restrições técnicas 
30
12022
1
21


x
xx
 
Restrições de não negatividade 0, 21 xx 
 
 
Pesquisa Operacional I 
 
29 
9) Uma alfaiataria está considerando quanto deve produzir de seus dois 
modelos de terno, denominados de Executivo e Despojado, de forma a maximizar 
o lucro. Será impossível fabricar quanto se queira de cada um dos modelos, porque 
existem limitações nas horas disponíveis para a operação de costura e a operação 
de acabamento, as duas operações são básicas na fabricação. No caso da costura, 
existem 160 horas-máquinas disponíveis, enquanto para o acabamento, que é feito 
manualmente, haverá, no máximo, 220 homens-horas. Em termos de lucro unitário 
e produção, os dois modelos apresentam as seguintes características: 
a. Executivo: 
I. Lucro unitário: R$ 105,00 
II. Horas-máquina de costura por unidade: 2 
III. Homens-hora de acabamento por unidade: 1 
 
b. Despojado: 
I. Lucro unitário: R$ 70,00 
II. Horas-máquina de costura por unidade: 1 
III. Homens-hora de acabamento por unidade: 4 
 
Formule o modelo de programação linear para maximizar o lucro da 
alfaiataria. Considere: 
1x = quantidade do terno Executivo; 2x = quantidade do terno Despojado; 
 
Pesquisa Operacional I 
 
30 
10) Uma rádio FM local tem o seguinte problema: foi descoberto que o 
programa de sertanejo com 20 minutos de música e 1 minuto de propaganda 
chama a atenção de 30.000 ouvintes, enquanto o programa de MPB, com 10 
minutos de musica e 1 minuto de propaganda chama a atenção de 10.000 
ouvintes. No decorrer de uma semana, o patrocinador insiste no uso mínimo, 5 
minutos pra sua propaganda e que não há verba para mais de 80 minutos de 
música. Quantas vezes por semana cada programa deve ser levado ao ar para obter 
o número máximo de telespectadores: Construa o modelo do PPL. 
 
 
Pesquisa Operacional I 
 
156 
 
Gabaritos 
 
Exercícios – Unidade 1 
1. d 
2. c 
3. b 
4. e 
5. a 
6. a 
7. b 
Observação no gabarito da questão: Note que nesse caso há a obrigatoriedade 
de transportar as 200 caixas de cenoura, por isso a parcela fixa de R$ 4.000,00 na 
função objetivo (200 caixas x R$ 20,00 reais do lucro). E as caixas de cenouras 
devem ser subtraídas da restrição técnica. 
8. d 
9. 
2121 70105);( xxxxLMax  
Restrições técnicas 
2204
1602
21
21


xx
xx
 
Restrições de não negatividade 0, 21 xx 
 
 
 
 
Pesquisa Operacional I 
 
157 
10. 
1x = frequência semanal do programa sertanejo; 
2x = frequência semanal do programa MPB; 
2121 000.10000.30);( xxxxTMax  
Restrições técnicas 
5
801020
21
21


xx
xx
 
Restrições de não negatividade 0, 21 xx 
 
Exercícios – Unidade 2 
1. d 
2. c 
Solução: 
2
2
2
4
42
42
1
2
1
2
12
21
x
x
x
x
xx
xx





 
2
3
2
6
62
62
1
2
1
2
12
21
x
x
x
x
xx
xx




