Unidade III Programação Linear

Prévia do material em texto

Pesquisa 
Operacional
Material Teórico
Responsável pelo Conteúdo:
Prof. Esp. Roberto Seraglia Martins
Revisão Textual:
Prof. Ms. Claudio Brites
Programação linear
• Introdução
• Problemas lineares
• Solução
 · Os principais objetivos desta Unidade são conhecer modelos de 
programação linear; características e formulações dos modelos; 
exemplos de modelagem para resolver problemas empresariais; 
Método Simplex; análise de sensibilidade; e programação 
linear inteira.
OBJETIVO DE APRENDIZADO
Leia atentamente o conteúdo desta Unidade, que lhe possibilitará 
conhecimentos sobre a programação linear.
Você também encontrará aqui uma atividade composta por questões de 
múltipla escolha relacionadas com o conteúdo estudado. Além disso, terá 
a oportunidade de trocar conhecimentos e debater questões no fórum 
de discussão.
É extremante importante que você consulte os materiais complementares, 
pois são ricos em informações, possibilitando-lhe o aprofundamento de seus 
estudos sobre esse assunto.
ORIENTAÇÕES
Programação linear
UNIDADE Programação linear
Contextualização
A Programação Linear visa discutir aspectos relacionados ao processo de 
maximização do resultado nas indústrias, privilegiando o uso da margem de 
contribuição, instrumento do custeio variável.
O estudo compreende a identificação de um problema onde se torna necessária 
a escolha da melhor combinação, por exemplo, de produtos a serem fabricados 
num ambiente de múltiplas restrições.
A programação linear é proposta como alternativa para encontrar o melhor mix 
de produção, ou seja, aquele que maximize o resultado.
Finalmente, é apresentado um exemplo em que os conceitos são aplicados e os 
impactos na margem de contribuição total da empresa são analisados.
Dessa forma, a programação linear é capaz de fornecer uma combinação de 
produtos que proporciona resultados maiores do que o uso isolado da margem de 
contribuição.
Saiba mais acessando o link abaixo:
https://goo.gl/BDqPVsEx
pl
or
6
7
Introdução
Quando tratamos de problemas e possíveis soluções, estamos buscando uma 
saída que é a otimização, ou seja, uma forma eficiente de utilizar os recursos para 
se atingir um objetivo.
Falamos de otimização de recursos pois esses, na prática, sempre estão 
associados à natureza financeira e econômica, como equipamentos, mão de obra, 
matéria prima e o capital.
A Pesquisa Operacional tem como característica:
Fazer uma busca minuciosa por toda a organização, buscando otimização de 
operações pautada na aplicação de técnicas e métodos científicos a partir do 
desenvolvimento e da utilização de métodos analíticos, operações e integração 
de equipes.
A tomada de decisão sempre é um processo difícil e a Pesquisa Operacional 
surge para dar subsídios para a melhor escolha, buscando sempre alcançar objetivos 
e a otimização.
A otimização vem sempre ligada a uma busca de quantidades, maximizando-as 
ou minimizando-as, e finitas variáveis a serem consideradas.
Quando podemos expressar nosso problema organizacional de otimização 
com funções matemáticas e sinais (Figura 2), dizemos que são problemas de 
programação matemática.
Problemas de programação matemática são classificados de acordo com a 
técnica que se usa para montá-los, analisá-los e resolvê-los. 
Problemas lineares
Programação linear
A Programação Linear (PL) fundamenta-se na busca pela solução de problemas 
que possam ser parametrizados por expressões lineares. 
A Programação Linear tem a tarefa de trabalhar com a função objetivo, 
respeitando as restrições de modelo; em outras palavras, ela pode maximizar 
ou minimizar uma função linear observando o sistema linear de desigualdades e 
igualdades. As restrições determinam o que chamamos de conjunto viável para 
chegarmos à solução ótima!
7
UNIDADE Programação linear
Complicou?
Simplificando:
Temos um objetivo que é encontrar a melhor distribuição dos recursos de modo a 
alcançar um valor ótimo.
Considerando:
Que nosso Objetivo será transcrito como variável de decisão do problema.
E que existem restrições para a aplicação dos recursos, que podem ser fundadas na 
forma de utilização ou na disponibilidade dos mesmos.
Esquematizando
Onde queremos chegar?
Quais são as condiçõesa serem obedecidas?
Como escrever o problema com variáveis?
De�nição 
de Variáveis
Relações Matemáticas
Restrições
MODELO
Equação
Função Objetivo
Como podemos observar na concepção, não existe uma forma estática para 
montar o modelo de um problema, pois a modelagem envolve aspectos particulares 
que são modelados com a observação e prática de aplicação, contando com 
experiência, boa análise e síntese.
Na formulação de um modelo, é considerada muito importante a escolha 
adequada das variáveis de decisão. Quando as variáveis de decisão são bem 
selecionadas, a função objetivo e as restrições podem ser obtidas sem muita 
dificuldade. Os problemas na determinação da função objetivo e as restrições 
aparecem devido a uma escolha incorreta das variáveis de decisão.
8
9
Problemas típicos
A Pesquisa Operacional pode ser aplicada na resolução de uma gama muito 
grande de problemas de natureza tática e não estratégica.
TÁTICO X ESTRATÉGICO
Avaliando o alcance 
do problema:
Quando sua resolução produz 
um efeito de curta duração, 
sendo que essa solução pode 
ser redesenhada com facilidade, 
temos um problema TÁTICO.
x
Medindo a extensão e 
orientação do problema:
Quanto maior for a abrangência da 
solução na organização, uma lista 
maior de metas e objetivos, mais 
ESTRATÉGICO esse problema será 
para o grupo.
São exemplos:
 · Cadastro de rotas;
 · Filas de espera;
 · Reposição ou substituição;
 · Movimentação de Estoques;
 · Alocação de recursos;
Vamos exercitar?
Uma indústria de massas produz três tipos de biscoitos: quadrado, redondo 
e oval.
Cada tipo requer farinha pura, açúcar e aditivos que estão disponíveis 
nas quantidades de: 9.600.000, 4.800.000 e 2.200.000 quilos por mês 
respectivamente.
As receitas de cada tipo de biscoito são:
 · Um quilo de biscoito quadrado requer 0,22 quilos de farinha pura, 0,50 
quilos de açúcar e 0,28 quilos de aditivos;
 · Um quilo de biscoito redondo requer 0,52 quilos de farinha pura, 0,34 
quilos de açúcar e 0,14 quilos de aditivos;
 · Um quilo de biscoito oval requer 0,74 quilos de farinha pura, 0,20 quilos 
de açúcar e 0,06 quilos de aditivos.
Como programação de produção, com base na demanda de mercado, o 
planejamento da indústria estipulou que:
 · a quantidade de biscoito oval deve ser, no mínimo, igual a 16 vezes a 
quantidade de biscoito quadrado; e
9
UNIDADE Programação linear
 · que a quantidade de biscoito redondo deve ser, no máximo, igual a 
600.000 quilos por mês;
 · A empresa sabe que cada quilo de biscoito quadrado, redondo e oval 
dá uma margem de contribuição para o lucro de $0,30, $0,25 e $0,20, 
respectivamente;
 · e seu objetivo é determinar o programa de produção que maximiza a 
margem total de contribuição para o lucro.
Definição das variáveis:
X1: quantidade de biscoito quadrado a produzir
X2: quantidade de biscoito redondo a produzir
X3: quantidade de biscoito oval a produzir
Modelo completo:
Encontrar valores para x1, x2 e x3 de modo a: 
MAXIMIZAR 
L = 0,30 × x1 + 0,25 × x2 + 0,20 × x3
Respeitando as restrições:
0,22 × x1 + 0,52 × x2 + 0,74 × x3 ≤ 9.600.000
0,50 × x1 + 0,34 × x2 + 0,20 × x3 ≤ 4.800.000
0,28 × x1 + 0,14 × x2 + 0,06 × x3 ≤ 2.200.000
16 × x1 - x3 ≤ 0
X2 ≤ 600.000
x1 ≥ 0
X2 ≥ 0
X3 ≥ 0
10
11
Analisando esse exemplo como base, podemos afirmar que as grandezas 
envolvidas num sistema de Programação Linear obedecem às características gerais:
 · proporcionalidade – exemplo: se 1 quilo do biscoito quadrado possui 
0,50 quilos de açúcar, 3 quilos de biscoito quadrado possuirão 1,50 quilos 
de açúcar;
 · aditividade – exemplo: se 1 quilo de biscoito redondo requer 0,52 quilos 
de farinha pura, e 1 quilo de biscoito oval requer 0,74 quilos de farinha 
pura, logo 1 quilo da mistura deve conter1,26 quilos de farinha pura;
 · fracionamento – exemplo: 1 quilo de biscoito oval requer 0,74 quilos de 
farinha pura, 0,20 quilos de açúcar e 0,06 quilos de aditivos.
Outro exemplo delicioso:
Uma sorveteria vai fazer a programação mensal de mão de obra e material para 
a produção de sorvete. Ela deve considerar a produção de três tipos de sorvete 
utilizando 200 quilos de material por dia com disponibilidade de mão de ora de 
150 horas. 
Cone Massa Picolé
Mão de obra 7 3 6
Material 4 4 5
Lucro 4 2 3
Formule um modelo de Programação Linear para determinar a produção de 
cada um dos tipos de sorvete maximizando o lucro da sorveteria.
Definição das variáveis:
X1: quantidade de cone a produzir
X2: quantidade de massa a produzir
X3: quantidade de picolé a produzir
Modelo completo:
Encontrar valores para x1, x2 e x3, de modo a: 
MAXIMIZAR LUCRO TOTAL
Max Lucro = 4 × x1 + 2 × x2 + 3 × x3
11
UNIDADE Programação linear
Respeitando as restrições:
Mão de obra
7 × x1 + 3 × x2 + 6 × x3 ≤ 150
Material
4 × x1 + 4 × x2 + 5 × x3 ≤ 200
E;
x1 ≥ 0
X2 ≥ 0
X3 ≥ 0
Está esquentando?
Vamos avaliar duas linhas de produção que produzem três diferentes formatos 
de garrafas.
A organização se comprometeu a entregar 16 toneladas de garrafa 350mL, 6 
toneladas de garrafa 1500mL e 28 toneladas de garrafa 3000mL.
Existe uma demanda para cada tipo de garrafa.
O custo de produção na primeira linha é de R$ 1.000 e o da segunda linha é 
de R$ 2.000 por dia.
A primeira linha produz 8 toneladas de garrafa 350mL, 1 tonelada de garrafa 
1500mL e 2 toneladas de garrafa 3000mL por dia. A segunda linha produz 2 
toneladas de garrafa 350mL, 1 tonelada de garrafa 1500mL e 7 toneladas de 
garrafa 3000mL.
Quantos dias cada linha deverá operar para suprir os pedidos de forma 
mais econômica?
Garrafa 350mL Garrafa 1500mL Garrafa 3000mL
Linha 1 8 1 2
Linha 2 2 1 7
Total 16 6 28
12
13
Variáveis de decisão
x1 = dias de produção da linha 1
x2 = dias de produção da linha 2
Restrições Sujeito a:
8 x1 + 2 x2 ≥ 16
1 x1 + 1 x2 ≥ 6
2 x1 + 7 x2 ≥ 28
x1 ≥ 0
x2 ≥ 0
Objetivo do Problema:
Custo Mínimo!
Min. Custo = 1000 x1 + 2000 x2.
Agora ficou fácil!
Um produtor rural pode distribuir 800 caixas de vegetais para sua região. Ele 
necessita distribuir 200 caixas de brócolis, lucrando R$20 por caixa, pelo menos 
100 caixas de aipo, lucrando R$10 por caixa, e até 200 caixas de couve-flor, 
lucrando R$30 por caixa.
De que forma deverá ele carregar o caminhão para obter o lucro máximo? 
Caminhão
Brócolis 200
Aipo 100
Couve-flor 200
Total 800
Variáveis de decisão
x1 = quantidades de aipo a carregar
x2 = quantidades de couve-flor a carregar
13
UNIDADE Programação linear
Restrições Sujeito a:
x1 + x2 ≤ 600
x1 ≥ 100
x2 ≤ 200
x1 ≥ 0
x2 ≥ 0
Como o produtor deverá distribuir suas caixas para obter o lucro máximo?
Max.Lucro = 10 x1 + 30 x2 + 4000
Último!
Um ourives faz 6 brincos por hora, se fizer somente brincos. E produz 5 pingentes 
por hora, se fizer somente pingentes. Ele gasta 2 unidades de ouro para fabricar 1 
unidade de brinco e 1 unidade ouro para fabricar uma unidade de pingente.
Sabendo que o total disponível de ouro é apenas 10 unidades e que o lucro 
unitário por brinco é de 5 unidades monetárias, e o do pingente é de 2 unidades 
monetárias, responda:
Qual o modelo do sistema de produção do ourives para maximizar seu lucro 
por hora?
Tempo Ouro
Brincos 10 2
Pingentes 12 1
Total 60 10
Variáveis de decisão
x1 = quantidades de brincos a produzir por hora
x2 = quantidades de pingentes a produzir por hora
Restrições Sujeito a:
10 x1 + 12 x2 ≤ 60
2 x1 + 1 x2 ≤ 10
x1 ≥ 0
x2 ≥ 0
14
15
Solução
Max.Lucro = 5 x1 + 2 x2
Limitações
Existem situações nas organizações em que encontramos um número tão grande 
de variáveis e restrições que fica impossível viabilizar uma resolução manual. 
Nesses casos, recomenda-se a utilização de softwares específicos para a resolução 
de Programação Linear
Softwares computacionais
A utilização de ferramentas computacionais para a resolução de problemas de 
Programação Linear de grande porte é considerada pela grande quantidade de 
variáveis e restrições.
Ao abrir o computador hoje em dia, deparamo-nos com várias opções disponíveis 
no mercado para a resolução desse problema nas organizações. Temos, assim, 
desde programas que necessitam do suporte de potentes sistemas operacionais até 
outros que podem ser utilizados em computadores pessoais.
Método Gráfico
Um problema de Programação Linear pode ser resolvido pelo Método Gráfico 
sempre que o modelo em estudo apresentar duas variáveis.
As variáveis serão X1 e X2 e os eixos também serão nomeados X1 e X2 
Existem problemas de Programação Linear que apresentam:
 · Uma solução ótima;
 · Nenhuma solução ótima;
 · Infinitas soluções.
O Método Gráfico se apresenta como solução muito limitada pois grande 
parte dos problemas de Programação Linear contém mais de duas variáveis e 
muitas restrições.
15
UNIDADE Programação linear
Exemplo:
Vamos representar graficamente a solução de um sistema:
X1 + 3x2 ≤ 12
2 x1 + x2 ≥ 16
x1 ≥ 0
x2 ≥ 0
Suas retas correspondentes:
1- X1 + 3x2 ≤ 12 → se X1 = 0 x2 = 4
Se x2 = 0 e X1= 12
2 - 2 x1 + x2 ≥ 16 → se X1 = 0 x2= 16
se x2 = 0 e X1 = 8
x2
x1
Essa é a área de possíveis
Soluções, que respeita 
as restrições impostas 
pelo modelo
Função-objetivo:
Max. L = 2 x1 + 5 x2
16
17
Vamos atribuir valores aleatoriamente a L, começando com o número 10
1. Se L for igual a 10, então x1 = 5 e x2 = 2 .
2. Se L for igual a 15, então x1 = 7,5 e x2 = 3
À medida que formos aumentando o valor de L, obteremos retas paralelas. 
Podemos então perceber que, dentro da área de possíveis soluções, o ponto P e 
a reta paralela de maior valor. Portanto, esse ponto é a solução do problema que 
maximiza o valor de L na região de restrições dadas.
Método Simplex
Como vimos, problemas de Programação Linear com mais de duas variáveis 
não podem ser resolvidos pelo Método Gráfico. Dessa forma, surge o Método 
Simplex como proposta para a resolução desses casos. 
O Método Simplex foi desenvolvido para, a partir de algoritmos, encontrar 
algebricamente a solução para um problema de Programação Linear.
Existem duas etapas importantes na aplicação desse método:
 · O teste de otimalidade da solução, ou seja, a identificação de uma 
solução ótima;
 · A melhoria da solução, a obtenção de outra solução viável melhor do que 
a encontrada antes.
Análise de sensibilidade
Essa é uma técnica utilizada para avaliar os impactos que o programa sofre 
quando são impostas modificações nas condições iniciais de modelagem.
Em outras palavras, é o estudo de um modelo de programação matemática 
submetido a mudanças em suas condições iniciais.
17
UNIDADE Programação linear
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Introdução à pesquisa operacional: método e modelos para análise de decisões.
ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional: método 
e modelos para análise de decisões. 5. ed. Rio de Janeiro: LTC, 2015.
Introdução à pesquisa operacional.
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à pesquisa operacional. 
9. ed. Porto Alegre: AMGH, 2013.
Introdução à pesquisa operacional
LONGARAY, André Andrade. Introdução à pesquisa operacional. São Paulo: 
Saraiva, 2013.
 Leitura
Desenvolvimento e Otimização de Modelos Matemáticos por meio da Linguagem
SILVA, A, F. DA; MARINS, F. A. S.; SILVA, G. M.; LOPES, P.R. M. DE A. 
Desenvolvimento e Otimização de Modelos Matemáticos por meio da Linguagem. 
São Paulo: GAMS, 2011.
18
19
Referências
ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional: método 
e modelos para análise de decisões. 5. ed. Rio de Janeiro: LTC, 2015.
ARENALES, M.; ARMENTANO, V.; MORABITO, R.; YANASSE, H. Pesquisa 
operacional para cursos de engenharia: modelagem e algoritmos. Rio de 
Janeiro: Campus, 2007
BELFIORI, P.; FÁVERO, L. P. Pesquisa Operacionalpara cursos de Engenharia. 
Rio de Janeiro: Campus, 2013.
FOGLIATTI, M. C.; MATTOS, N. M. C. Teoria de Filas. São Paulo: Editora 
Interciência, 2007.
GOLDBARG, M. C.; LUNA, H. P. L. Otimização combinatória e programação 
linear. Rio de Janeiro: Campus, 2000.
HILLIER, F. S. e LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
São Paulo: McGrawHill / Bookman, 2013.
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisão 
(modelagem em Excel). 4. ed. Rio de Janeiro: Campus, 2009.
MARINS, F. A. S. Introdução à Pesquisa Operacional. São Paulo: Editora 
Cultura Acadêmica, 2011. Disponível em http://www.culturaacademica.com.br/
catalogo-detalhe.asp?ctl_id=158
MIRSHAWKA, V. Aplicações de pesquisa operacional. São Paulo: Editora 
Nobel, 1981.
PIZZOLATO, N. D. e GANDOLPHO, A. A. Técnicas de Otimização. Rio de 
Janeiro: Editora LTC, 2009.
19