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 compreensã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 Um pouco de história . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Organização da apostila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1
3
2
Problemas típicos
2.1 Deve conter: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Modelos matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Exemplos de modelos de programação linear . . . . . . . . . . . . . . . .
5
5
6
6
3
Programação linear
3.1 Deve conter: . . . . . . .
3.2 Conceitos básicos . . . .
3.3 Método gráfico . . . . .
3.4 Método Simplex . . . . .
3.5 Análise de sensibilidade
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Exercícios de revisão
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
11
11
14
16
16
19
i
C APÍTULO
1
Introdução à Pesquisa Operacional
“A PO como ciência aplica-se a pessoas (organização e gerência, relações de trabalho, economia, decisões individuais, pesquisa do mercado, etc) a pessoas e máquinas (eficiência e produtividade, 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, comunicaçã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 organizaçã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 experimentais, 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 à invençã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 iniciada 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 operacional), 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 internacional 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 pelos 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 operacional 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 (SOBRAPO).
“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 reflexõ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 modelar 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 otimizar sistemas
numéricos que resultam quando se usam dados nos modelos” (Arenales et al., 2007).
CAPÍTULO 1. INTRODUÇÃO À PESQUISA OPERACIONAL
1.2
3
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.
C APÍTULO
2
Problemas típicos
Para facilitar a compreensão deste capítulo, vamos citar novamente o trecho do livro de Mirshawka (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, desenvolvimento 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 afirmando 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 podem ser classificados de acordo com a técnicas utilizadas para a resolução dos modelos matemáticos: problemas lineares, problemas inteiros, problemas não-lineares. Neste curso nos preocuparemos apenas com os problemas lineares.
2.1
Modelos matemáticos
Para Goldbarg & Luna (2000) um modelo tenta a representação substitutiva da realidade. Intuitivamente 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 realidade através de metáforas/modelos.
“Um modelo não é igual à realidade, mas suficientemente similar para que as conclusões obtidas 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 modelos 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 classificados 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 alguma 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 adequada 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 concentrase 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 abandonada 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 pequeno 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 Linear. 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 outros. 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.
C APÍ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 custo de
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 (maximizaçã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
𝑐𝑇 𝑥
(3.4)
𝐴𝑥 = 𝑏
(3.5)
𝑥≥0
(3.6)
Maximizar
sujeito a:
Em que:
𝐴𝑚𝑥𝑛
𝑎11
𝑎
= [ 21
...
𝑎21
𝑎12
𝑎22
...
𝑎22
... 𝑎1𝑛
... 𝑎2𝑛
]
... ...
... 𝑎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 satisfizer 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 visualizaçã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 factibilidade, 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 estraté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!!!
C APÍ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
(𝑃 2) Maximizar 𝑓 (𝑥1 , 𝑥2 ) = 𝑥1 + 2𝑥2
sujeito a:
sujeito a:
−3𝑥1 + 𝑥2 ≤ 2
−3𝑥1 + 𝑥2 ≤ 2
𝑥2 ≤ 3
𝑥2 ≤ 3
𝑥1 + 2𝑥2 ≤ 9
𝑥1 + 2𝑥2 ≤ 9
3𝑥1 + 𝑥2 ≤ 18
3𝑥1 + 𝑥2 ≤ 18
𝑥1 ≥ 0; 𝑥2 ≥ 0.
𝑥1 ≥ 0; 𝑥2 ≥ 0.
(𝑃 3) Maximizar 𝑓 (𝑥1 , 𝑥2 ) = 𝑥1 + 3𝑥2
(𝑃 4) Minimizar 𝑓 (𝑥1 , 𝑥2 ) = −2𝑥1 − 3𝑥2
sujeito a:
sujeito a:
𝑥2 ≤ 4
𝑥1 ≤ 3
𝑥1 + 𝑥2 ≤ 6
𝑥1 + 𝑥2 ≤ 4
𝑥1 ≤ 3
𝑥2 ≤
5𝑥1 + 𝑥2 ≤ 18
7
2
𝑥1 ≥ 0; 𝑥2 ≥ 0.
𝑥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
(𝑃 6) Minimizar 𝑓 (𝑥1 , 𝑥2 ) = −𝑥1 − 𝑥2
sujeito a:
sujeito a:
𝑥1 + 𝑥2 ≤ 6
𝑥1 + 𝑥2 ≤ 6
𝑥1 − 𝑥2 ≤ 4
𝑥1 − 𝑥2 ≤ 4
−𝑥1 + 𝑥2 ≤ 4
−𝑥1 + 𝑥2 ≤ 4
𝑥1 ≥ 0; 𝑥2 ≥ 0.
𝑥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
A NDRADE , E. L. Introdução à pesquisa operacional: Métodos e modelos para análise de decisão. Editora LTC, 2004.
A RENALES , M.; A RMENTANO , V.; M ORABITO , R.; YANASSE , H. Pesquisa operacional para
cursos de engenharia. Editora Campus, 2007.
C OSTA , J. J. S. Tópicos de pesquisa operacional. Editora LTC, 1973.
G OLDBARG , M. C.; L UNA , H. P. L. Oimização combinatória e programação linear. Editora
Campus, 2000.
M IRSHAWKA , V. Aplicações de pesquisa operacional. Editora Nobel, 1981.
S ILVA , E. M. Pesquisa operacional. 1988.
T OLEDO , C.; F RANÇA , P.; M ORABITO , R.; K IMMS , 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