apostila_POP1

Prévia do material em texto

PESQUISA OPERACIONAL I
Profa. Tamara Angélica Baldo
Apostila para auxiliar os estudos da disciplina de Pesquisa Operacional I
Esta apostila encontra-se em fase de construção e está sujeita a erros e alterações. Para melhoria
desta, gostaria de contar com a colaboração de todos e, agradeço desde já, qualquer sugestão e/ou
correção.
A disciplina
“Pesquisa Operacional é a aplicação de métodos científicos a problemas complexos para auxiliar
no processo de tomadas de decisão, tais como projetar, planejar e operar sistemas em situações que
requerem alocações eficientes de recursos escassos” (Arenales et al., 2007).
Objetivos
O objetivo principal desta disciplina é fazer com que o aluno compreenda a importância da Pesquisa
Operacional na engenharia de produção.
Conteúdo programático
O conteúdo programático da disciplina é:
∙ Introdução à Pesquisa Operacional;
∙ Problemas típicos;
∙ Fases da metodologia de um projeto de pesquisa operacional;
∙ Método científico;
∙ Programação linear;
∙ Método gráfico;
∙ Método simplex;
∙ Dualidade e análise de sensibilidade;
∙ Problema de transporte.
3
De acordo com o conteúdo programático proposto para esta disciplina, esta apostila foi organizada
de maneira que este conteúdo ficasse (sequencialmente) mais didático e agradável para compreen-
são.
Avaliação
A avaliação de assimilação do conteúdo abordado na disciplina será feita de diversas maneiras,
tendo estas pesos diferentes. Cada aluno que cursa a disciplina terá duas notas a qual chamaremos
de 푁푂푇퐴1 e 푁푂푇퐴2, assim, a média final da disciplina é dada pela fórmula (1).
푀퐸퐷퐼퐴 =
1 ∗ (푁푂푇퐴1) + 2 ∗ (푁푂푇퐴2)
3
(1)
Tem-se que 0 ≤ 푁푂푇퐴1/푁푂푇퐴2 ≤ 10, portanto 0 ≤ 푀퐸퐷퐼퐴 ≤ 10. Sendo 푁푂푇퐴1 ou
푁푂푇퐴2 composta por:
∙ (1,0) Trabalhos: resenha(s) de artigo(s) sobre o conteúdo, lista de exercícios;
∙ (9,0) Prova:
– (8,0) Prova com questões dissertativas (SEM consulta);
– (1,0) Refazer a prova em casa.
Assim, se o aluno cumprir com todos os itens de maneira excelente, a soma total de sua nota será
10. Entretanto, o cumprimento parcial ou não satisfatório terá nota com valor proporcional.
Bibliografia básica
Esta disciplina requer leitura complementar. Assim, as bibliografias básicas são: Arenales et al.
(2007) e Goldbarg & Luna (2000). Recomenda-se fortemente, também, a leitura de: Andrade
(2004), Silva (1988), Toledo et al. (2006), etc.
Sumário
1 Introdução à Pesquisa Operacional 1
1.1 Um pouco de história . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Organização da apostila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Problemas típicos 5
2.1 Deve conter: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Modelos matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Exemplos de modelos de programação linear . . . . . . . . . . . . . . . . 6
3 Programação linear 11
3.1 Deve conter: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Conceitos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Método gráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.5 Análise de sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Exercícios de revisão 19
i
CAPÍTULO
1
Introdução à Pesquisa Operacional
“A PO como ciência aplica-se a pessoas (organização e gerência, relações de trabalho, econo-
mia, decisões individuais, pesquisa do mercado, etc) a pessoas e máquinas (eficiência e produ-
tividade, organização de fluxos em fábricas, métodos de controle de qualidade, organização de
mudanças tecnológicas, etc) e ao movimento (transporte, estoque, distribuição, manipulação, co-
municação, localização, etc)” (Mirshawka, 1981).
“No mundo em que hoje vivemos a sobrevivência de uma organização impõe o planejamento.
Para auxiliar os planejadores a PO utiliza informações provenientes de todos os elementos do
sistema de ação, inclusive informações da própria organização e as relativas ao meio ambiente e a
concorrência” (Mirshawka, 1981).
“É por isto que as características da PO são: pesquisa sobre as operações de toda a organi-
zação, a otimização das operações, aplicação dos mais recentes métodos e técnicas científicas,
desenvolvimento e utilização dos modelos analíticos, projeto e utilização de operações experimen-
tais, e, emprego de equipes mistas de pesquisa” (Mirshawka, 1981).
Devido a importância da Pesquisa Operacional, para finalizar, um trecho extraído do livro de
Costa (1973): “Em 1973, a disciplina citada (Pesquisa Operacional) já está incluída nos currículos
de Engenharia, Economia, Administração, Química Agronomia, Atuária e Estatística”.
1.1 Um pouco de história
Por volta de 1938 surge o termo operational research que está estreitamente vinculado à in-
venção do radar, que ocorreu em 1934, na Inglaterra. O radar era utilizado principalmente para
1
2 1.1. UM POUCO DE HISTÓRIA
detectar presença de inimigos em território britânico. Pesquisa Operacional é a tradução direta do
termo para o português. Em 1941, foi criado a Seção de Pesquisa Operacional do Comando da
Força Aérea de Combate da Inglaterra com o intuito de auxiliar decisões de guerra para que estas
fossem tomadas da melhor forma.
“A análise científica do uso operacional de recursos militares de maneira sistemática foi inici-
ada na Segunda Guerra Mundial” (Arenales et al., 2007). Ao final da guerra, tanto na Inglaterra
como nos EUA, a pesquisa operacional evolui consideravelmente. Em 1947, foi implantado um
projeto militar no Pentágono, onde faziam parte deste projeto o matemático George Dantzig. Este
projeto tinha por objetivo apoiar decisões operacionais das forças aéreas americanas. No decorrer
deste projeto, Dantzig desenvolveu o método simplex para resolução de problemas de programação
linear.
Na década de 50 foram fundadas a ORSA (sociedade científica americana de pesquisa op-
eracional), a ORS (sociedade inglesa de pesquisa operacional) e a TIMS (sociedade americana
de ciências de administração). Nesta mesma década foi realizada a primeira conferência interna-
cional de pesquisa operacional, realizada em Oxford. Esta conferência foi a primeira oportunidade
de troca de informações e constatações de trabalhos diferentes em diversas áreas apresentados pe-
los cientistas ingleses (apresentaram problemas específicos) e americanos (apresentaram modelos
e métodos matemáticos em termas diversos).
Em 1967, o periódico inglês Operational Research propôs uma definição para pesquisa opera-
cional que diz, segundo a tradução de Arenales et al. (2007), “ Pesquisa Operacional é a aplicação
de métodos científicos a problemas complexos para auxiliar no processo de tomadas de decisão,
tais como projetar, planejar e operar sistemas em situações que requerem alocações eficientes de
recursos escassos”.
Na década de 60 a pesquisa operacional conquista os pesquisadores brasileiros e em 1968,
em São José dos Campos-SP, no ITA, foi realizado o primeiro simpósio brasileiro de pesquisa
operacional e, logo em seguida, foi fundada a Sociedade Brasileira de Pesquisa Operacional (SO-
BRAPO).
“De forma sucinta, podemos dizer que a pesquisa operacional é um enfoque científico sobre a
tomada de decisões. A denominação pesquisa operacional é comumente motivo de críticas e re-
flexões, pois não revela a abrangência da área e pode dar a falsa impressão de estar limitada análise
de operações... O componente científico está relacionado a idéias e processos para articular e mo-
delar problemas de decisão, determinando os objetivos do tomador de decisão e as restrições sob
as quais se deve operar. Também está relacionado a métodos matemáticos para otimizarsistemas
numéricos que resultam quando se usam dados nos modelos” (Arenales et al., 2007).
CAPÍTULO 1. INTRODUÇÃO À PESQUISA OPERACIONAL 3
1.2 Organização da apostila
Esta apostila tem por objetivo auxiliar os estudos da disciplina de PESQUISA OPERACIONAL
I. Entretanto, a disciplina requer complementação e auxílio de outros materiais didáticos. Sabemos
que devido a importância e abrangência da pesquisa operacional, este material, então, tem por
finalidade direcionar os estudos de forma que o aluno consiga ter um foco principal ao consultar
qualquer material didático.
A organização deste material é:
∙ Capítulo 2: problemas típicos e problema de transporte;
∙ Capítulo 3: programação linear, método gráfico, método simplex, dualidade e análise de
sensibilidade;
∙ Capítulo 4 (Exercícios de revisão): neste capítulo concentram-se exercícios sobre toda a
teoria discutida nos demais capítulos.
CAPÍTULO
2
Problemas típicos
Para facilitar a compreensão deste capítulo, vamos citar novamente o trecho do livro de Mir-
shawka (1981): “as características da PO são: pesquisa sobre as operações de toda a organização,
a otimização das operações, aplicação dos mais recentes métodos e técnicas científicas, desen-
volvimento e utilização dos modelos analíticos, projeto e utilização de operações experimentais, e,
emprego de equipes mistas de pesquisa”. Com base nesta frase, podemos começar o capítulo afir-
mando a importância da PO em qualquer tomada de decisão em uma organização. Estas decisões
devem ser tomadas de forma concisa, tentando atingir um determinado objetivo e é neste ponto
que entram os problemas de otimização.
Os problemas de otimização buscam maximizar ou minimizar uma quantidade (objetivo),
sendo esta quantidade vinculada a um número finito de variáveis. As variáveis são, a grosso modo,
a resposta que procuro no meu problema. Um problema de otimização que possui seu objetivo e
as suas restrições expressas como funções matemáticas e relações funcionais (≥,≤, >,<,=) são
chamados de problemas de programação matemática. Problemas de programação matemática po-
dem ser classificados de acordo com a técnicas utilizadas para a resolução dos modelos matemáti-
cos: problemas lineares, problemas inteiros, problemas não-lineares. Neste curso nos preocupare-
mos apenas com os problemas lineares.
2.1 Modelos matemáticos
Para Goldbarg & Luna (2000) um modelo tenta a representação substitutiva da realidade. In-
tuitivamente a maioria das pessoas já utilizou algum modelo para explicar algo a alguém, por
exemplo, quando plotamos gráficos, utilizamos equações que representam sólidos (cone, cubo,
5
6 2.1. MODELOS MATEMÁTICOS
pirâmide, etc), entre outras situações, ou seja, tentamos transmitir e fazer interpretações da reali-
dade através de metáforas/modelos.
“Um modelo não é igual à realidade, mas suficientemente similar para que as conclusões obti-
das através de sua análise e/ou operação, possam ser estendidas à realidade” (Goldbarg & Luna,
2000).
A PO reúne as mais diversas técnicas e algoritmos que tentam estruturar e solucionar mode-
los quantitativos expressos matematicamente. Os principais modelos de pesquisa operacional são
denominados de programação (no sentido de planejamento) matemática.
A Programação Matemática destaca-se principalmente devido a sua grande aplicabilidade na
solução de problemas de otimização. Problemas de programação matemática podem ser classifi-
cados de acordo com a técnicas utilizadas para a resolução dos modelos matemáticos: problemas
lineares (variáveis são contínuas e apresentam comportamento linear), problemas inteiros (se al-
guma variável está condicionada a assumir valores discretos), problemas não-lineares (quando
exibe qualquer tipo de não-linearidade).
A dificuldade em modelar matematicamente um problema está em representar de forma ade-
quada a realidade. Assim, um modelo que conseguir representar mais precisamente a realidade
será de melhor qualidade.
Dentre os diversos modelos de programação citados anteriormente, o foco deste curso concentra-
se em problemas de programação linear.
2.1.1 Exemplos de modelos de programação linear
A PO se aplicada a grande variedade de problemas. A maioria consiste em problemas de
natureza tática e não estratégica. A distinção entre problemas táticos e problemas estratégicos se
baseia em três aspectos:
1. Alcance do problema: Um problema é mais tático que outro se sua solução produzir efeito
de duração mais curta ou, o que e essencialmente se a solução pode ser modificada ou aban-
donada com facilidade.
2. Extensão do problema: Um problema é tanto mais estratégico quanto maior for a parte da
organização diretamente afetada pela solução.
3. Orientação do problema: Um problema é tanto mais estratégico quanto mais envolver a
determinação de finalidades, metas ou objetivos.
A aplicação da PO a grande variedade de problema táticos pode ser representada por um pe-
queno número de problemas típicos. Desenvolveram-se técnicas para modelá-los e obter soluções
a partir dos modelos.
Problemas típicos:
CAPÍTULO 2. PROBLEMAS TÍPICOS 7
∙ Alocação;
∙ Estoque;
∙ Substituição ou reposição;
∙ Filas de espera;
∙ Seqüência e coordenação;
∙ Determinação de rotas;
∙ Situações de competição;
∙ Busca de informação.
Algumas das técnicas matemáticas empregadas para resolução dos modelos e aplicam-se a
modelos de diferentes tipos. Os modelos são freqüentemente classificados segundo de métodos e
técnicas matemáticas empregadas na obtenção da sua solução. Estas técnicas e métodos são:
∙ Programação Linear;
∙ Programação Dinâmica;
∙ Programação Inteira;
∙ Teoria dos Estoques;
∙ Teoria das Filas;
∙ Simulação;
∙ Teoria dos Jogos;
∙ Teoria dos Grafos;
∙ Análise de Risco, etc.
Problema de transporte
O Problema de Transporte é talvez o mais representativo dos Problemas de Programação Lin-
ear. Há uma vasta aplicação prática, tendo sido estudado por vários pesquisadores, embora tenha
sido Dantzig o primeiro a estabelecer a sua formulação em programação linear (PL) e a propor um
método sistemático de resolução.
O problema (geral) de transporte consiste em: determinar a forma mais econômica (ou mais
lucrativa) de enviar um bem disponível em quantidades limitadas de determinados locais para ou-
tros. Como qualquer problema de PL, este pode ser resolvido pelo método do simplex, entretanto,
8 2.1. MODELOS MATEMÁTICOS
por possuir uma estrutura particular, permite-se a utilização de métodos que, embora derivados do
simplex, são bem mais eficientes.
Como já dito anteriormente, o modelo dos transportes visa minimizar o custo total do transporte
necessário para abastecer 푛 centros consumidores (destinos), a partir de 푚 centros fornecedores
(origens). Podendo ser esquematizado:
O objetivo consiste em encontrar os valores de 푥푖푗 (푖 = 1; ...;푚 e 푗 = 1; ...;푛) que minimize o
custo total do transporte. Portanto, o modelo matemático será:
Minimizar
∑푚
푖=1
∑푛
푗=1 푐푖푗푥푖푗
sujeito a:
푛∑
푗=1
푥푖푗 ≤ 푎푖 (푖 = 1; :::;푚)
푚∑
푖=1
푥푖푗 = 푏푗 (푗 = 1; :::;푛)
푥푖푗 ≥ 0
Em que,
푐푖푗 : custo unitário de transporte da origem 푖 para o destino 푗;
푎푖 : quantidade disponível na origem i;
푏푗 : quantidade requerida no destino j;
푥푖푗 : quantidade a ser transportada da origem 푖 para o destino 푗. São as incógnitas do problema.
CAPÍTULO
3
Programação linear
Os modelos de programação linear (PL) são importantes pois são a base para a compreensão
de todos os demais problemas da programação matemática.
3.1 Conceitos básicos
Para que um sistema possa ser representado utilizando um PL, as grandezas envolvidas devem
obedecer as seguintes características:
∙ Proporcionalidade: a quantidade de recurso consumido por uma determinada atividade deve
ser proporcional ao nível desta atividade na solução final do problema. E, ainda, o custode
cada atividade deve ser proporcional ao nível de operação da atividade. Por exemplo, se 1kg
de um ingrediente possui 0,3kg de proteína, então 0,5kg deste mesmo ingrediente contém
0,15kg de proteína;
∙ Aditividade: o custo total é soma das parcelas associadas a cada atividade. Por exemplo,
se um ingrediente (1kg) que compõe determinada ração possui 0,3 kg de proteína e, em
outro ingrediente (1kg) possui 0,1kg de proteína, a mistura de 1kg de cada um destes dois
componentes conterá 0,4 kg de proteína;
∙ Fracionamento: as variáveis podem assumir valores fracionados. Por exemplo, em uma
mistura (ração) pode-se utilizar 0,4kg de um determinado ingrediente.
Um PL pode, sem sofrer nenhuma alteração em suas propriedades matemáticas, usufruir das
seguintes operações elementares:
9
10 3.1. CONCEITOS BÁSICOS
1. Mudança no critério de otimização: transformação de um problema de minimização (maxi-
mização) em um problema de maximização (minimização), utilizando a seguinte propriedade:
Minimizar (푓(푥)) corresponde a Maximizar (−푓(푥))
Maximizar (푓(푥)) corresponde a Minimizar (−푓(푥))
2. Transformação de uma variável livre em variável não-negativa: neste caso irá ocorrer a
substituição da variável em transformação por duas variáveis auxiliares. Ambas maiores ou
iguais a zero, sendo a soma igual a variável original, ou seja:
푥푖 = 푥
1
푖 − 푥2푖 , com 푥1푖 ≥ 0 e 푥2푖 ≥ 0
3. Transformação da restrição de ≤ em =: Supondo a restrição 푥1 + 푥2 + 푥3 + ... + 푥푛 ≤ 푏,
para transformá-la em uma igualdade basta acrescentar à restrição uma variável de folga
푥푛+1 ≥ 0, ou seja, 푥1 + 푥2 + 푥3 + ...+ 푥푛 + 푥푛+1 = 푏.
4. Transformação da restrição de≥ em =: Supondo a restrição 푥1+푥2+푥3+ ...+푥푛 ≥ 푏, para
transformá-la em uma igualdade basta subtrair à restrição uma variável de folga 푥푛+1 ≥ 0,
ou seja, 푥1 + 푥2 + 푥3 + ...+ 푥푛 − 푥푛+1 = 푏.
Definição 1 (forma padrão): Um PL é dito estar na forma padrão se possuir as características a
seguir:
Maximizar 푐1푥1 + 푐2푥2 + 푐3푥3 + ...+ 푐푛푥푛 (3.1)
sujeito a:
푎11푥1 + 푎12푥2 + 푎13푥3 + ...+ 푎1푛푥푛 = 푏1
푎21푥1 + 푎22푥2 + 푎23푥3 + ...+ 푎2푛푥푛 = 푏2
... (3.2)
푎푚1푥1 + 푎푚2푥2 + 푎푚3푥3 + ...+ 푎푚푛푥푛 = 푏푚
푥1 ≥ 0, 푥2 ≥ 0, 푥3 ≥ 0, ..., 푥푛 ≥ 0 (3.3)
A função linear (3.1) de maximização, é chama de função objetivo. O sistema composto por
várias equações lineares (3.2), é conhecido como restrições do problema, conjuntamente com (3.3).
Sendo (3.3), conhecido como restrições de não negatividade das variáveis.
O mesmo problema (3.1- 3.3) pode ser escrito matricialmente:
CAPÍTULO 3. PROGRAMAÇÃO LINEAR 11
Maximizar 푐푇푥 (3.4)
sujeito a:
퐴푥 = 푏 (3.5)
푥 ≥ 0 (3.6)
Em que:
퐴푚푥푛 = [
푎11 푎12 ... 푎1푛
푎21 푎22 ... 푎2푛
... ... ... ...
푎21 푎22 ... 푎2푛
]
∙ é uma matriz de dimensão 푚푥푛, chamada de matriz dos coeficientes;
∙ 푐푇 = (푐1푐2...푐푛): é o vetor dos lucros (custos);
∙ 푥푇 = (푥1푥2...푥푛): é o vetor de variáveis;
∙ 푏푇 = (푏1푏2...푏푚): é o vetor dos termos independentes;
∙ 0푇 = (00...0): é um vetor de elementos nulos.
Definição 2 (região factível e solução factível): Uma solução (푥1푥2...푥푛) é dita factível se sat-
isfizer todas as restrições (3.2) e (3.3). O conjunto composto por todas as soluções factíveis é
chamado de região factível.
Definição 3 (solução ótima): Uma solução factível que proporcionar o maior valor a função
objetivo é chamado de solução ótima.
Exemplo 1 (colocar na forma padrão) Reescrever o problema a seguir na forma padrão:
Minimizar 푓(푥1, 푥2, 푥3) = 2푥1 − 3푥2 + 3푥3
sujeito a:
푥1 + 2푥2 − 푥3 ≥ 3
−2푥1 + 푥2 + 푥3 ≤ −1
푥1 livre, 푥2 ≥ 0, 푥3 ≥ 0.
Forma padrão:
12 3.2. MÉTODO GRÁFICO
Maximizar −푓(푥+1 , 푥−1 , 푥2, 푥3, 푥4, 푥5) = −2푥1 + 3푥2 − 3푥3 + 0푥4 + 0푥5
sujeito a:
푥1 + 2푥2 − 푥3 − 푥4 = 3
−2푥1 + 푥2 + 푥3 + 푥5 = −1
푥+1 ≥ 0, 푥−1 ≥ 0, 푥2 ≥ 0, 푥3 ≥ 0.
3.2 Método gráfico
O método gráfico não tem por objetivo encontrar a solução do problema, mas facilitar a visu-
alização do método Simplex. A solução ótima de PL sempre é um vértice (solução básica viável)
ou um ponto extremo da região de factibilidade. Portanto, para encontrar a solução ótima, basta
encontrar um vértice que forneça o maior valor (problema de maximização) à função objetivo. As
restrições do problema (3.2) e (3.3) definem a região de factibilidade.
Exemplo 2 (resolução gráfica) Encontrar a solução ótima para o problema a seguir utilizando o
método gráfico (extraído de Arenales et al. (2007)):
Maximizar 푓(푥1, 푥2) = 푥1 + 2푥2
sujeito a:
푥1 + 푥2 ≤ 4
푥1 ≤ 2
푥2 ≤ 3
푥1 ≥ 0, 푥2 ≥ 0.
CAPÍTULO 3. PROGRAMAÇÃO LINEAR 13
A solução ótima é o ponto C, onde 푥∗ = (푥∗1 푥
∗
2) = (1 3). Portanto, o valor ótimo da função
objetivo é 7.
OBESERVAÇÃO 1: Caso as restrições do problema não consigam fornecer uma região de facti-
bilidade, ou seja, se a intersecção entre a região factível produzida por todas as restrições for vazia,
este problema é infactível. Assim, podemos concluir que as restrições são conflitantes.
14 3.3. MÉTODO SIMPLEX
OBESERVAÇÃO 2: Se a região de factibilidade for ilimitada e ainda não há um ponto que forneça
o melhor valor à função objetivo, ou seja, 푓(푥)→∞, dizemos que o problema possui um conjunto
ilimitado de soluções ótimas.
3.3 Método Simplex
“O método simplex encontra o vértice ótimo pesquisando apenas um subconjunto (em geral,
pequeno) do conjunto de todos os vértices da região de factibilidade” (Arenales et al., 2007).
“O simplex é um algoritmo. Genericamente, podemos entender por algoritmo qualquer es-
tratégia para solucionar problemas; contudo, seremos mais precisos, reservando para a palavra
algoritmo (é um procedimento que termina em um número finito de passos) um conceito diferente
de procedimento (é uma sequência finita de instruções)” (Goldbarg & Luna, 2000).
Devido a importância deste capítulo, vamos utilizar como referência o livro do Goldbarg &
Luna (2000) como material de apoio, mais especificamente o Capítulo 3 do livro.
3.4 Análise de sensibilidade
Para ?, a análise de sensibilidade e uma técnica para avaliar os impactos que o programa sofre
quando existem modificações nas condições de modelagem. A análise de sensibilidade pode ser
definida como o estudo de um modelo de programação matemática submetido a mudanças em
suas condições iniciais. As mudanças poderão abranger: mudança no vetor de custos, mudança no
vetor de termos independentes, mudanca nos coeficientes das variáveis; acréscimo de restrições,
acréscimo de novas variáveis.
Consideraremos um exemplo:
Uma empresa fabrica dois tipos de produto: rádio standard e rádio luxo. Com relação ao rádio
standard temos as seguintes informações:
∙ A linha de produção comporta um máximo de 24 pessoas;
∙ Cada rádio consome 1homem/dia para ser produzido;
∙ Cada rádio fornece um lucro de R$ 30,00.
Com relação ao rádio luxo:
∙ A linha de produção comporta um máximo de 32 pessoas;
∙ Cada rádio consome 2 homens/dia para ser produzido;
∙ Cada rádio fornece um lucro de R$ 40,00.
CAPÍTULO 3. PROGRAMAÇÃO LINEAR 15
A fabrica possui 40 empregados a serem alocados nas duas linhas de produção. O objetivo e
maximizar o lucro. Que quantidade de produção de rádios maximiza o lucro?
Solucao:
Maximizar 푓(푥1, 푥2) = 30푥1 + 40푥2
sujeito a:
푥1 + 2푥2 ≤ 40
푥1 ≤ 24
푥2 ≤ 16
푥1 ≥ 0, 푥2 ≥ 0.
푓 ∗(푥1, 푥2) = 1040.000 : Indica o valor ótimo encontrado para a função objetivo.
O que aconteceria se o lucro de 푥2 aumentasse?
E, se 푥1 ≤ 19?
3.5 Dualidade
Completar!!!
CAPÍTULO
4
Exercícios de revisão
Para os exercícios apresentados neste capítulo considerem os problemas de otimização a seguir.
Extraído de Arenales et al. (2007):
(푃1) Maximizar 푓(푥1, 푥2) = 푥1 + 푥2
sujeito a:
−3푥1 + 푥2 ≤ 2
푥2 ≤ 3
푥1 + 2푥2 ≤ 9
3푥1 + 푥2 ≤ 18
푥1 ≥ 0;푥2 ≥ 0.
(푃2) Maximizar 푓(푥1, 푥2) = 푥1 + 2푥2
sujeito a:
−3푥1 + 푥2 ≤ 2
푥2 ≤ 3
푥1 + 2푥2 ≤ 9
3푥1 + 푥2 ≤ 18
푥1 ≥ 0;푥2 ≥ 0.
(푃3) Maximizar 푓(푥1, 푥2) =푥1 + 3푥2
sujeito a:
푥2 ≤ 4
푥1 + 푥2 ≤ 6
푥1 ≤ 3
5푥1 + 푥2 ≤ 18
푥1 ≥ 0;푥2 ≥ 0.
(푃4) Minimizar 푓(푥1, 푥2) = −2푥1 − 3푥2
sujeito a:
푥1 ≤ 3
푥1 + 푥2 ≤ 4
푥2 ≤ 72
푥1 ≥ 0;푥2 ≥ 0.
1. Quando e quem criou o método simplex? Ele é aplicado para resolver todos os problemas
de pesquisa operacional? Se não, quais problemas ele resolve e cite exemplos de problemas
que não podem ser resolvidos pelo método simplex.
17
18
(푃5) Minimizar 푓(푥1, 푥2) = −푥1 − 2푥2
sujeito a:
푥1 + 푥2 ≤ 6
푥1 − 푥2 ≤ 4
−푥1 + 푥2 ≤ 4
푥1 ≥ 0;푥2 ≥ 0.
(푃6) Minimizar 푓(푥1, 푥2) = −푥1 − 푥2
sujeito a:
푥1 + 푥2 ≤ 6
푥1 − 푥2 ≤ 4
−푥1 + 푥2 ≤ 4
푥1 ≥ 0;푥2 ≥ 0.
2. Qual a importância e aplicabilidade da Pesquisa Operacional para os dias de hoje?
3. Faça um resumo sobre Pesquisa Operacional (definição, aplicação, história, etc.).
4. O que difere os problemas lineares, inteiros e não-lineares?
5. Além do método simplex, qual(is) o(s) outro(s) método(s) utilizado(s) para resolução do
problema de transporte?
6. Resolva os problemas P1 a P6 utilizando o método gráfico.
7. Resolva os problemas P1 a P6 utilizando o método Simplex.
Referências Bibliográficas
ANDRADE, E. L. Introdução à pesquisa operacional: Métodos e modelos para análise de de-
cisão. Editora LTC, 2004.
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa operacional para
cursos de engenharia. Editora Campus, 2007.
COSTA, J. J. S. Tópicos de pesquisa operacional. Editora LTC, 1973.
GOLDBARG, M. C.; LUNA, H. P. L. Oimização combinatória e programação linear. Editora
Campus, 2000.
MIRSHAWKA, V. Aplicações de pesquisa operacional. Editora Nobel, 1981.
SILVA, E. M. Pesquisa operacional. 1988.
TOLEDO, C.; FRANÇA, P.; MORABITO, R.; KIMMS, A. Um modelo de otimização para o
problema integrado de dimensionamento de lotes e programação da produção em fábricas de
refrigerantes. Pesquisa Operacional, v. 20, p. 155–186, 2006.
19
	Introdução à Pesquisa Operacional
	Um pouco de história
	Organização da apostila
	Problemas típicos
	Deve conter:
	Modelos matemáticos
	Exemplos de modelos de programação linear
	Programação linear
	Deve conter:
	Conceitos básicos
	Método gráfico
	Método Simplex
	Análise de sensibilidade
	Exercícios de revisão