Unidade II
PESQUISA OPERACIONAL
Profa. Ana Carolina Bueno
Programação linear
É um subitem da programação
matemática.
É um dos modelos utilizados
em pesquisa operacional.
Consiste em otimizar
(maximizar ou minimizar) uma dada
função linear, que se chama função
objetivo, definida num dado conjunto
convexo, tendo em conta que as variáveis
estão sujeitas a restrições.
Modelagem do problema – exemplo
Uma fábrica produz CPUs de dois tamanhos
diferentes – grande e pequena – que
apresentam lucros unitários de,
respectivamente, R$ 500 e R$ 200. Ela
deseja saber quantas unidades de cada
um destes aparelhos deverá fazer para que
o lucro obtido pela operação seja máximo.
A capacidade de produção da fábrica
é a seguinte:
Componentes CPU CPU Produção
grande pequena horária
Gabinete grande 1 6
Gabinete pequeno 1 15
Placa-mãe 3 1 24
Placa de vídeo 2 1 20
Modelagem do problema
Modelar o problema significa definir:
as variáveis de entrada;
a função objetivo;
as restrições e, a partir delas, montar um
sistema de equações e inequações
inequações.
Modelagem do problema – exemplo
Variáveis de entrada:
o número de CPUs a serem produzidas;
x1 = número de CPUs grandes
a serem montadas;
x2 = número de CPUs pequenas
a serem montadas.
Função objetivo para maximizar o lucro:
Lucro = 500x1 + 200x2
Modelagem do problema – exemplo
Restrições relativas à capacidade
produtiva de cada componente:
gabinete grande: x1 ≤ 6
gabinete pequeno: x2 ≤ 15
placas-mãe:
placas mãe: 3x1 + x2 ≤ 24
placas de vídeo: 2x1 + x2 ≤ 20
restrição de negatividade: x1 0 e x2 0
Os valores de x1 e x2 que maximizam
o lucro desta operação
p ç serão obtidos
pela resolução deste sistema de
equações e inequações.
Métodos de solução de pesquisa
operacional
Método gráfico
Método Simplex: método geral, aplicável
a problemas com qualquer quantidade
de variáveis de entrada.
Método computacional: aplicável
a um tipo específico de problema,
mas com qualquer quantidade
de variáveis de entrada.
Método gráfico
Para problemas com duas variáveis
de entrada.
Traça-se o gráfico com seus dois eixos,
sendo as duas variáveis x1 e x2.
Traçam-se as retas referentes às restrições
do problema e delimita
delimita-se
se então a região
região.
viável.
x1 + 2x2 10
Método gráfico
Encontrada a região viável, deve-se
traçar uma reta com a inclinação
da função objetivo.
São então traçadas diversas paralelas a ela.
O ponto ótimo é o ponto onde a reta de maior
(menor) valor possível corta a região viável
viável.
x1 + 2x2 10
Método gráfico – exemplo
1ª restrição é a
dos gabinetes
grandes.
0 x1 6
Método gráfico – exemplo
2ª restrição é a
dos gabinetes
pequenos.
0 x 1 15
Método gráfico – exemplo
3ª restrição é a
quantidade de placas-
mãe produzidas.
3 x1 x2 24
x1 0 x2 24
x2 0 x1 8
Método gráfico – exemplo
4ª restrição:
restrição placas de
vídeo.
2 x1 x2 20
x1 0 x2 20
x2 0 x1 10
Método gráfico – exemplo
Método gráfico – exemplo
Antes tínhamos infinitas soluções
possíveis. Agora, com este teorema,
restaram apenas seis soluções que
podem ser ótimas e por tentativas
podemos definir qual é essa
solução ótima.
ótima
Vértice CPU CPU Lucro = 500x1 + 22x2
grande pequena
A 0 0 0+0
B 0 15 0 + 300 = 300
C 2,5 15 1.250 + 3.000 = 4.250
D 4 12 200 + 2.400 = 4.400
E 5 6 3.000 + 1.200 = 4.200
F 5 0 3.000 + 0 = 3.000
Método gráfico – exemplo
O ponto de máximo lucro é o ponto D.
Deve-se montar 4 CPUs grandes por
hora e 12 CPUs pequenas por hora.
Gerará um lucro de $ 4.400,00 por hora.
Para se atingir esse lucro máximo
máximo, serão
produzidos:
4 gabinetes grandes por hora;
12 gabinetes pequenos por hora;
24 p
placas-mãe p
por hora;;
20 placas de vídeo por hora.
Interatividade
Apresente qual é o espaço de solução da
função objetivo e as restrições da apresentação
gráfica abaixo.
a) 8x1 + 12x2 48; x1 4; 14x1 + 10x2 28; x2 1; x1, x2 0
b) 5x1 + 10x2 40; x1 5; 25x1 + 10x2 50; x2 3; x1, x2 0
c) 5x1 + 10x2 40; x1 3; 25x1 + 10x2 50; x2 2; x1, x2 0
d) 30x1 + 20x2 300; x1 8; 5x1 + 20x2 100; x2 0; x1, x2 0
e) x1 + x2 3; x1 4; 5x1 + 8x2 28; x2 1; x1, x2 0
Método Simplex
Objetivo
Procedimento geral para resolver
problemas de programação linear.
É sempre usado um computador, e os
programas estão amplamente disponíveis.
Utilizaremos em nosso curso o aplicativo
Solver, disponível nas ferramentas
do MS Excel®.
Serão apresentados os principais
aspectos do método Simplex para resolver
qualquer problema de programação linear
tal que bi > 0 para todo i = 1, 2, ...,m.
Método Simplex
Trabalha com equações e não com
inequações. As inequações devem
ser transformadas em equações, e isso
é feito com a adição de variáveis.
Determinar as variáveis que podem
aparecer em um problema desse tipo:
variável de entrada;
termo independente;
variável de folga ou residual;
variável de excesso;
variável artificial.
Relembrando o exemplo
Uma fábrica produz CPUs de dois
tamanhos diferentes – grande e pequena –
que apresentam lucros unitários de,
respectivamente, R$ 500 e R$ 200. Ela
deseja saber quantas unidades de cada um
destes aparelhos deverá fazer para que o
lucro obtido pela operação seja máximo.
A capacidade de produção da fábrica
é a seguinte:
Componentes CPU CPU Produção
grande pequena horária
Gabinete grande 1 6
Gabinete pequeno 1 15
Placas-mãe 3 1 24
Placas de vídeo 2 1 20
Método Simplex – exemplo
Variável de entrada: número de CPUs
grandes (x1) e número de CPUs
pequenas (x2).
Termo independente: as quantidades
limitantes produzidas para cada
componente.
Variável de folga ou residual: as eventuais
sobras de componentes (gabinetes ou
placas).
Variável de excesso: não existirão valores
deste tipo, pois é um problema de
maximização.
Variável artificial: não existem variáveis
deste tipo, visto serem inequações
do tipo ≤.
Método Simplex – exemplo
As inequações seriam transformadas
em equações:
gabinete grande x1 6
gabinete pequeno x2 15
placas-mãe 3 x1 x2 24
placas de vídeo 2 x1 x2 20
Então:
gabinete grande 1x1 0 x2 1x3 0 x4 0 x5 0 x6 6
g
gabinete pequeno
p q 0x1 1x2 0x3 1x4 0x5 0x6 15
placas-mãe 3 x1 1x2 0 x3 0 x4 1x5 0 x6 24
placas de vídeo 2 x1 1x2 0 x3 0 x4 0 x5 1x6 20
Método Simplex – exemplo
Estabelecer a planilha do algoritmo.
Um algoritmo é um processo em que um
procedimento sistemático é repetido
(iterado) seguidamente até que o
resultado desejado seja obtido.
´
Método Simplex – exemplo
1º passo:
x1 x3 6 se x1 0 então: x3 6
2º passo: início do preenchimento
da planilha.
´
Método Simplex – exemplo
Na linha de controle colocamos o lucro
respectivo com sinal trocado, ou seja,
-500 para CPU grande, -200 para CPU
pequena e zero para as demais colunas.
´
Método Simplex – exemplo
^
Método Simplex – exemplo
3º passo
´
Método Simplex – exemplo
Quando uma coluna cruza com uma
linha correspondente à mesma variável,
o valor será um.
´
Método Simplex – exemplo
Quando uma coluna cruza com uma
linha correspondente a outra variável,
o valor será zero.
´
Método Simplex – exemplo
Regra do retângulo
Calcular o valor da célula D12. Usar o
retângulo definido pelo pivô (célula C5)
e pelo valor correspondente anterior
(célula D6). O valor pedido será obtido
pela
l formulação:
f l ã
´
Método Simplex – exemplo
Novo valor = valor anterior (produtos dos
elementos da diagonal oposta) pivô.
No nosso exemplo seria:
D12 D 6 (C 6 D5) C 5 1 (0 0) 1 1
´
Método Simplex – exemplo
Calcular o termo independente
correspondente à placa-mãe.
I13 I 7 (C 7 15) C 5 24 (3 6) 1 6
´
Método Simplex – exemplo
Calculando os outros valores:
´
Método Simplex – exemplo
´
Método Simplex – exemplo
Podemos partir então para a terceira
tentativa, substituindo primeiro a linha
de x5 por x2.
´
Método Simplex – exemplo
Preencher os valores das colunas que
não estão zeradas na tentativa.
´
Método Simplex – exemplo
Calcular pela regra do retângulo os valores
correspondentes às três colunas restantes.
´
Método Simplex – exemplo
Por fim, calcular quem entra e quem sai
para a próxima tentativa.
´
Método Simplex – exemplo
Essas tentativas serão repetidas
sucessivamente e tantas vezes
quantas necessárias até que na
linha de controle todos os números
sejam positivos ou nulos.
´
Método Simplex – exemplo
´
Método Simplex – exemplo
Observe a última coluna da última
tentativa. Ela nos oferece a alternativa
ótima para esse problema de
programação linear.
Variável Item Qtd.
Programa de produção: CPUs Grandes 4
CPUs Pequenas 12
Sobras (recursos residuais): Gabinetes Grandes 2
Gabinetes
Gab etes Pequenos
eque os 3
Placas‐mãe 0
Placas de vídeo 0
Interatividade
Uma empresa produz dois tipos de produtos
produtos,
Artigo 1 e Artigo 2. A produção destes artigos
requer três tipos diferentes de recursos (material,
tempo-máquina e mão de obra). A tabela mostra o
nível de recursos disponíveis, o consumo de
recursos por cada unidade de cada um dos
artigos produzidos
produzidos, bem como o lucro líquido
obtido da venda de cada unidade dos artigos.
Admite-se que o objetivo da Gestão corresponde
à maximização do seu lucro total, e que pretende
saber qual o Plano de Produção que cumpre
esse objetivo.
Interatividade
O método Simplex foi utilizado
para maximizar o lucro total
e foi construído o quadro.
Assinale a alternativa incorreta:
a) A última linha (Z) inclui os coeficientes da função
objetivo, mas com sinal trocado (problema de
maximização).
i i ã )
b) Examinar as entradas na linha Z. Se não houver
nenhum coeficiente negativo, o algoritmo terminou,
e o problema está resolvido.
c) A coluna D inclui as disponibilidades relativas
a cada um dos recursos.
d) Na parte superior do quadro são colocados
os identificadores das variáveis de folga e das
variáveis de excesso.
e) Ao lado esquerdo do quadro são colocados
os identificadores das variáveis de folga
para constituírem uma base de partida
para a solução do problema.
Método computacional – Solver
O algoritmo Simplex é uma sequência
repetitiva de cálculos, situação ideal para
as chamadas planilhas eletrônicas como,
por exemplo, o MS Excel®.
Vamos, portanto, tornar a resolver
o exemplo das CPUs, utilizando o
referido programa da Microsoft.
Pacote Solver
Pacote Solver
Relembrando o exemplo
Uma fábrica produz CPUs de dois tamanhos
diferentes – grande e pequena – que
apresentam lucros unitários de,
respectivamente, R$ 500 e R$ 200. Ela deseja
saber quantas unidades de cada um destes
aparelhos deverá fazer para que o lucro
obtido pela operação seja máximo.
A capacidade de produção da fábrica
é a seguinte:
Componentes CPU CPU Produção
grande pequena horária
Gabinete grande 1 6
Gabinete pequeno 1 15
Placas-mãe 3 1 24
Placas de vídeo 2 1 20
Iniciar o processo de programação
linear – exemplo
1º passo: elaborar uma planilha inicial
com os dados fundamentais do
problema.
-
Solver – exemplo
Nas células sombreadas são colocadas
as fórmulas de cálculo.
Na célula D5 é colocada a função
objetivo: FO = lucro = 500x1 + 200x2.
Na planilha de Excel será: B4
B4*B3+C4*C3
B3 C4 C3
-
Solver – exemplo
Nas células D7 a D10 serão colocadas as
quantidades a serem utilizadas de cada
componente, ou seja, a quantidade de
CPUs a serem produzidas (célula B4 para
CPU grande e C4 para CPU pequena)
multiplicada pela quantidade de
componentes utilizados em cada CPU.
-
Solver – exemplo
Gabinete grande (D7): 1x1 – no Excel: B7*B3.
Gabinete pequeno (D8): 1x2 – no Excel:
C8*C3.
Placas-mãe (D9): 3x1 + x2 – no Excel:
B9*B3+C9*C3.
Placas de vídeo (D10): 2x1 + x2 – no Excel:
B10*B3+C10*C3.
-
Solver – exemplo
Montada a planilha, podemos resolver
o problema com a utilização da
ferramenta computacional: Dados/Solver
Solver – exemplo
Preencher informações em Parâmetros
do Solver.
Solver – exemplo
Adicionar as restrições.
Indicar três aspectos: Referência de célula
(D7 a D10); escolher o sinal adequado (<=);
Restrição (E7 a E10).
Clicar em adicionar.
-
Solver – exemplo
N
Nesse ponto
t ttemos ttodas
d as
informações para o MS Excel® efetuar
os cálculos.
Solver – exemplo
Iniciar os cálculos: estabelecer algumas
opções de cálculo. No exemplo, manter todas
as definições padrão, acrescentando apenas
as opções: Presumir modelo linear; Presumir
não negativos; Usar escala automática.
Solver – exemplo
Conferir as diversas informações
introduzidas e pressionar o botão
Resolver.
Solver – exemplo
O Solver irá fazer as tentativas de
resolução e, após encerrado o processo
de cálculo, apresentará o quadro
Resultados do Solver.
Solver – exemplo
A planilha montada apresenta valores
nas células que estavam zeradas,
apresentando o número de CPUs
grandes a serem montadas (4), o número
de CPUs pequenas a serem montadas
(12) e o lucro total
total, de R$ 4
4.400,00.
400 00
-
Solver – exemplo
Relatório de resposta
-
Solver – exemplo
Relatório de limites
Solver – exemplo
Relatório de sensibilidade
-
Interatividade
Problema do “dilema do fabricante”: um
fabricante deseja maximizar a receita bruta. A
tabela ilustra as composições das ligas, seus
preços e as limitações na disponibilidade de
matéria-prima. Pode ser usado o método
computacional por meio do programa Solver.
Assinale a alternativa que corresponde ao
desenvolvimento do problema:
Liga Tipo Liga Tipo Matéria-prima
A B disponível
Cobre 2 1 16
Zinco 1 2 11
Chumbo 1 3 15
Preço R$ 30,00 R$ 50,00
unitário
Interatividade
a) Os dados de entrada correspondem somente
à quantidade de cada tipo de matéria-prima.
b) Nas células variáveis, isto é, as células em
que os valores das variáveis de decisão são
colocados, que serão os níveis de produção,
pode-se entrar com qualquer valor inicial
inicial.
c) Recursos utilizados: calcular as unidades
de cobre, chumbo e zinco utilizadas pelas
quantidades de ligas digitadas inicialmente.
Deve-se multiplicar as unidades entre si.
d) É necessário obter o total de “receita”,
somando o preço unitário de cada liga.
e) Usar a ferramenta Solver. Ela pede que você
especifique somente a célula destino
(resultado da função objetivo).
Problemas envolvendo minimização
da função objetivo
O problema de minimização tem pelo
menos uma de suas restrições do tipo ≥.
Introduzir variáveis de excesso nas
restrições do tipo ≥.
Variável de excesso é uma variável não
negativa, subtraída do lado esquerdo
da desigualdade, e é numericamente
igual à diferença entre o valor do termo
independente e o valor das variáveis
que estão à esquerda da desigualdade.
Variável artificial é adicionada à esquerda
em todas as restrições que não
contenham uma variável de folga, sendo
utilizada nas restrições que têm
originalmente o sinal ≥.
Alterações no algoritmo Simplex
Introduzir as variáveis de excesso
e artificial.
Transformar a função objetivo de
minimizar para maximizar,
trocando seu sinal.
Mudar a maneira de calcular a linha
de controle da primeira solução básica.
A variável que entrará na base seguinte
é aquela da coluna que apresentar maior
valor positivo na linha de Controle.
A variável que vai sair da base é aquela
que apresentar o menor valor não
negativo na coluna Termo Independente
dividido pela coluna de Trabalho.
Problemas envolvendo minimização
da função objetivo – exemplo
Um fabricante de ração deseja produzir
um determinado tipo de ração, conforme
especificação do Ministério da Agricultura
e pelo mínimo custo. O Ministério especifica
apenas quatro nutrientes – A, B, C e D –,
exigindo que um quilo de razão contenha:
no mínimo 120g do nutriente A;
no mínimo 360g do nutriente B;
no máximo 360g do nutriente C;
exatamente 180g do nutriente D.
D
Problemas envolvendo minimização
da função objetivo – exemplo
O fabricante dispõe de três alimentos: milho,
alfafa e silagem. Cada quilo destes alimentos
contém os seguintes pesos em quilos dos
nutrientes:
NUTRIENTE MILHO ALFAFA SILAGEM
A 0,1 0,2 0,1
B 0,4 0,4 0,3
C 0,2 0,2 0,1
D 0,1 0,2 0,1
outros 0,2 0,4
TOTAL 1,0 1,0 1,0
Sabendo-se que o quilo do milho custa R$
0,50, o da alfafa R$ 0,20 e o da silagem R$
0,10, determinar qual a mistura
que proporciona mínimo
custo da ração especificada.
Problemas envolvendo minimização
da função objetivo – exemplo
Modelagem do problema
Variáveis: quantidades num quilo de ração
de milho (x), alfafa (y) e silagem (z).
A função objetivo, portanto, será:
custo da ração = 0
0,5x
5x + 0
0,2y
2y + 0
0,1z
1z
O objetivo é minimizar o valor do custo da
ração. Então, determinar os valores de x, y
e z que resultem no menor custo possível
(a solução ótima).
Problemas envolvendo minimização
da função objetivo – exemplo
Restrições
Nutriente A: 0,1x + 0,2y + 0,1z 0,12 kg
Nutriente B: 0,4x + 0,4y + 0,3z 0,36 kg
Nutriente C: 0,2x + 0,2y + 0,1z 0,36 kg
Nutriente D: 0,1x + 0,2y + 0,1z = 0,18 kg
Outros nutrientes: 0,2x + 0y + 0,4z 0 kg
Definir que os três alimentos juntos
perfaçam um quilo: x + y + z = 1 kg
Problemas envolvendo minimização
da função objetivo – exemplo
Redundância: as inequações para
o nutriente A e para o nutriente D
são redundantes. Ficaremos com
a mais restritiva, ou seja, a inequação
do nutriente D (se a inequação for igual
a 18
18, será automaticamente maior do que
12, daí a redundância).
Redundância: é a inequação para outros
nutrientes. Também pode ser eliminada,
pois se os valores de x, y e z têm de ser
positivos a inequação será
positivos,
automaticamente positiva.
Problemas envolvendo minimização
da função objetivo – exemplo
Restrições (multiplicar por 10)
Nutriente B: 4x + 4y + 3z 36 kg
Nutriente C: 2x + 2y + 1z 36 kg
Nutriente D: 1x + 2y + 1z = 18 kg
1x + 1y + 1z = 100 kg
Problemas envolvendo minimização
da função objetivo – exemplo
Restrições
Nutriente A: 1x + 2y + 1z 12 kg
Nutriente B: 4x + 4y + 3z 36 kg
Nutriente C: 2x + 2y + 1z 36 kg
Nutriente D: 1x + 2y + 1z = 18 kg
Outros nutrientes: 2x + 0y + 4z 0 kg
Definir que os três alimentos juntos
perfaçam um quilo: x + y + z = 10 kg
Problemas envolvendo minimização
da função objetivo – exemplo
Modelo formal
Introduzir as variáveis de folga, variável
de excesso e variável artificial.
Nutriente B: 4x + 4y + 3z - E1 + A1 = 36 kg
Nutriente C: 2x + 2y + 1z + R2 = 36 kg
Nutriente D: 1x + 2y + 1z + A3 = 18 kg
1x + 1y + 1z + A4 = 10 kg
Variável de excesso: representa a
quantidade de nutriente B que
q q
exceder os 360 gramas.
Problemas envolvendo minimização
da função objetivo – exemplo
Função objetivo
Mín. (5x + 2y + 1z + 0R2 + 0E1 + MA1 + MA2 + MA3)
Maximizar a função simétrica.
Máx. (-5x - 2y - 1z - 0R2 - 0E1 - MA1 - MA2 - MA3)
ç
Submetendo as restrições.
4x + 4y + 3z + 1E1 + 0R2 + 1A1 + 0A3 + 0A4 = 36 kg
2x + 2y + 1z + 0E1 + 1R2 + 0A1 + 0A3 + 0A4 = 36 kg
1x + 2y + 1z + 0E1 + 0R2 + 0A1 + 1A3 + 0A4 = 18 kg
1x + 1y + 1z + 0E1 + 0R2 + 1A1 + 0A3 + 1A4 = 10 kg
Solução computacional
Um investidor tem R$ 850.000,00 para
aplicar no mercado financeiro, podendo
escolher entre duas opções: um fundo
de ações e um fundo de renda fixa.
Cada quota do fundo de ações custa
R$ 160 e proporciona uma taxa de
retorno de 9%. Por outro lado, cada
quota do fundo de renda fixa custa
R$ 215 e proporciona uma taxa de
retorno de 5%.
O objetivo do cliente é minimizar
o risco, mas pretende obter o
retorno de pelo menos R$ 48.000.
Solução computacional
A aquisição de uma quota do fundo
de ações apresenta um índice de risco
igual a 5, enquanto uma quota do fundo
de renda fixa apresenta um índice
de risco igual a 2.
O último desejo do cliente é que pelo
menos 650 quotas do fundo de renda
fixa sejam adquiridas.
O que se deseja é determinar quantas
quotas de cada um dos investimentos
disponíveis devem ser adquiridas, para
que se atinja o objetivo de minimizar
o índice de risco total da carteira
deste investidor.
Solução computacional
Variáveis de entrada:
x1 = quantidade de quotas do fundo
de ações;
x2 = quantidade de quotas do fundo
de renda fixa.
Função objetivo:
Risco total da carteira = 5x1 + 2x2
Essa função objetivo deve ser
evidentemente minimizada.
Solução computacional
Restrições:
160x1 + 215x2 = 850.000
(0,09 160)x1 + (0,05 215)x2 25.000
x 650
Retorno
Solução computacional
No Solver: presumir modelo linear;
presumir não negativos; usar
escala automática.
Solução computacional
Solução computacional
Retorno
Solução computacional
Relatório de resposta
Retorno
Solução computacional
Relatório de sensibilidade
Retorno
Solução computacional
Relatório de limites
Interatividade
A Granja Cocoró quer misturar dois tipos de
alimentos para criar um tipo especial de ração
para suas galinhas poedeiras. A primeira
característica a ser atingida com a nova ração
é o menor preço possível por unidade de peso.
Cada um dos alimentos contém os nutrientes
necessários à ração final (aqui chamados de
nutrientes X, Y e Z), porém em proporções
variáveis. FO = 0,006x + 0,008y Restrições:
0,1x + 0,2y 2 ( I ) → X
0,4x + 0,6y 64 ( II ) → Y
0 5x + 0
0,5x 2y 34 ( III ) → Z
0,2y
Interatividade
Assinale a alternativa correta sobre
o problema:
a) 0,6x + 0,8y (função objetivo para
minimização de 1g do alimento 1 e 1g
do alimento 2).
b) Uma das restrições é a quantidade parcial
do nutriente Y; em x gramas do alimento 1
e y gramas do alimento 2, deve ser pelo
menos igual a 34g.
c) Se x = 34,5g e y = 83,6g,
o custo será de 0,88.
0 88
d) Se x = 34,5g e y = 83,6g,
o custo será de 1,4.
e) Se x = 34g e y = 83,6g do alimento X, então
(0,5 * 34,5) + (0,2 * 83,6) = 33,97g.
ATÉ A PRÓXIMA!