Aula01.ppt
O Planejamento Social
de um Galinha
 Considere que você está saindo com duas
namoradas: Ana Paula Arósio e Scheila
Carvalho.
1 / 43
Aula01.ppt
Pesquisa Operacional:
A Ciência da Decisão
Uma decisão pode ser classificada em
estruturada se envolve uma série de fatores
que possam ser quantificados, e logo,
equacionados;
 Pesquisa Operacional é uma ferramenta de
apoio à decisão estruturada;
 Alguns problemas são surpreendentemente
equacionáveis!

2 / 43
Aula01.ppt
Qual é a decisão?




Se você pudesse, estou certo, planejaria sair com
as duas ao mesmo tempo, e a todo tempo, acertei?
Mas, sair com as duas ao mesmo tempo não dá.
Elas não aceitariam sair com você juntas.
Ciumentas!
E, sair todo dia também não dá. Você não tem
dinheiro (entre outras coisas) para sair todo dia.
Para garantir a sua felicidade, considerando estes
problemas desagradáveis, você precisa decidir
quantas vezes na semana sair com cada uma!
3 / 43
Aula01.ppt
A Decisão

Chamemos assim:
• x1 a quantidade de vezes que você vai sair com
a Ana por semana;
• x2 a quantidade de vezes que você vai sair com a
Scheila por semana;
4 / 43
Aula01.ppt
Variáveis de Decisão
O que nós criamos, x1 e x2, são as chamadas
Variáveis de Decisão;
 As variáveis de decisão são aqueles valores
que representam o cerne do problema, e que
podemos escolher (decidir) livremente;

Veja que, a princípio, você pode sair quantas
vezes quiser com Ana Paula e com Scheila.
5 / 43
Aula01.ppt
Problemas Financeiros
Entretanto, existe um pequeno problema:
Ana é chique e gosta de lugares caros.
Uma
noite com ela custa R$180,00;
Scheila é mais simples, gosta de passeios
baratos. Sair com ela custa só R$100,00;
Mas a sua semanada é de apenas R$ 800,00!
Como fazer para garantir que você não vai se
endividar?
6 / 43
Aula01.ppt
Garantindo a mesada
Se você sai com a Ana x1 vezes no mês, e
cada vez gasta R$180,00, então você gasta
R$ 180x1 por mês!
 Fazendo o mesmo raciocínio para Scheila
obtemos o seguinte:
garantia

180 x1  100 x 2  800
gasto total
da semana
total disponível
por semana 7 / 43
Aula01.ppt
Problemas com o relógio
As diferenças entre as duas não são apenas no
volume de gastos:
Scheila é muito agitada. Cada vez que você
sai com ela gasta em média 4 horas do seu
precioso tempo.
 Quando sai com Ana, que é mais sossegada,
você gasta apenas 2 horas.

8 / 43
Aula01.ppt
Garantindo os estudos
Considere que os seus afazeres escolares
só lhe permitem 20 horas de lazer por
semana.
 Usando a notação anterior, como fazer para
garantir que não vai extrapolar este tempo?
garantia

2 x1  4 x 2  20
total de horas
tempo livre
9 / 43
Aula01.ppt
Pensando em tudo junto:
Restrições
2 x1  4 x 2  20 (horas por semana)
180 x1  100 x 2  800 (R$ p/ semana)
Você já pode se planejar! Decida quantas
vezes você vai sair com Ana (x1) e com
Scheila (x2]!
 Vamos ver quantas horas e quanto de
dinheiro nós consumimos, e depois quanto
sobra!

10 / 43
Aula01.ppt
Quanto Consumo?
2 x1  4 x 2  20 (horas por semana)
180 x1  100 x 2  800 (R$ p/ semana)

Por exemplo:
• Sair com a Ana 3 vezes e com a Scheila 2:
x1 = 3
x2 = 2
2  3  4  2  14 horas
Consumo
180  3  100  2  740 Reais
11 / 43
Aula01.ppt
Quanto sobra?
2 x1  4 x 2  20 (horas por semana)
180 x1  100 x 2  800 (R$ p/ semana)

Saindo 3 vezes com a Ana e 2 vezes com a
Scheila:
Consumo:
14 horas e
R$740,00
Sobra
20  14  6 horas
800  740  60 reais
12 / 43
Aula01.ppt
Outra situação:
2 x1  4 x 2  20 (horas por semana)
180 x1  100 x 2  800 (R$ p/ semana)

Outro exemplo:
• Sair com a Ana 3 vezes e com a Scheila 4:
x1 = 3
x2 = 4
2  3  4  4  22 horas
Consumo
180  3  100  4  940 reais
13 / 43
Aula01.ppt
Quanto sobra?
2 x1  4 x 2  20 (horas por semana)
180 x1  100 x 2  800 (R$ p/ semana)

Saindo com a Ana 3 vezes e com a Scheila 4,
temos a seguinte situação:
Sobra
Consumo:
22 horas e
R$940,00
20  22   2 horas
800  940   140 reais
14 / 43
Aula01.ppt
Isso eu não Posso!
2 x1  4 x 2  20 (horas por semana)
180 x1  20 x 2  600 (R$ p/ semana)

Neste exemplo eu gastaria 22 horas, e eu só
tenho disponíveis 20! Gastaria R$940,00 e
eu só tenho disponível R$800,00!
 Esta é uma situação impossível, dentro
das condições que foram propostas.
15 / 43
Aula01.ppt
Falta um Objetivo

É preciso pensar no objetivo final. O que eu
quero, para obter a maior felicidade?

Algumas Opções:
• Sair a maior quantidade de vezes por semana
possível;
total de saídas,
independente de com quem
Ou Seja:
max x1  x 2
16 / 43
Aula01.ppt
Outro objetivo possível
Suponha que você gosta da Scheila duas
vezes mais do que gosta da Ana.
 Assim, você pode criar um índice que
representa a sua preferência:

max x1  2 x 2
um valor unitário
para Ana
Scheila terá
o dobro
17 / 43
Aula01.ppt
Criamos dois modelos
diferentes!
funções objetivo
s.r.
2 x1  4 x 2  20
180 x1  100 x 2  800
x1 , x 2  0
restrições
max x1  x 2
max x1  2 x 2
s.r.
2 x1  4 x 2  20
180 x1  100 x 2  800
condições de
x1 , x 2  0
não-negatividade
modelo com o primeiro
objetivo
modelo com o segundo
objetivo
18 / 43
Aula01.ppt
O Objeto que trabalharemos:
Problemas de Otimização

Em problemas reais de otimização busca-se
maximizar ou minimizar uma quantidade
específica, chamada objetivo, que depende
de um número finito de variáveis de entrada.

As variáveis de entrada podem ser
• Independentes uma das outras
• Relacionadas umas com as outras por meio de
uma ou mais restrições
19 / 43
Aula01.ppt
Programação Matemática

Um problema de programação matemática é um
problema de otimização no qual o objetivo e as
restrições são expressas como funções
matemáticas e relações funcionais
Otimizar: z  f ( x1 , x2 ,..., xn )
g1 ( x1 , x2 ,..., xn )  b1
 
g2 ( x1 , x2 ,..., xn )  b2
Sujeito a:
 
:
  :
gn ( x1 , x2 ,..., xn ) 
 
bn
20 / 43
Aula01.ppt
Programação Linear

Um problema de programação matemática é
linear se a função objetivo e cada uma das
restrições forem lineares das respectivas
variáveis de entrada
f ( x1 , x2 ,..., xn )  c1 x1  c2 x2 ...cn xn
gi ( x1 , x2 ,..., xn )  ai1 x1  ai 2 x2 ...ain xn
21 / 43
Aula01.ppt
Quebrando a linearidade

A presença de qualquer das expressões
abaixo tornam o problema não linear
 x1 
n
; n  1;
1
x1
log  x1 ; com qualquer
base
x1
a ; para qualquer v alor de a
sen ( x1 ); cos( x1 ); etc.
22 / 43
Aula01.ppt
Exemplos

Os exemplos criados anteriormente eram
Problemas de Programação Linear:
max x1  x 2
max x1  2 x 2
s.r.
s.r.
2 x1  4 x 2  20
2 x1  4 x 2  20
180 x1  20 x 2  600
180 x1  20 x 2  600
x1 , x 2  0
x1 , x 2  0
23 / 43
Aula01.ppt
Programação Linear
Forma Padrão

Existem 4 características para um problema
na forma padrão:
• A função objetivo é de Maximizar;
• As restrições são todas com sinal de menor ou
igual;
• As constantes de todas as restrições são não
negativas;
• As variáveis são todas não negativas
24 / 43
Aula01.ppt
Programação Linear
Forma Padrão
Maximizar
Sujeito
Z  c1 x1  c 2 x 2  ...  c n x n
a:
a 11 x1  a 12 x 2  ...  a 1 n x n  b1
a 21 x1  a 22 x 2  ...  a 2 n x n  b 2
:
não
negativos
a m 1 x1  a m 2 x 2  ...  a mn x n  b m
x1 , x 2 , x 3 ,... x n  0
25 / 43
Aula01.ppt
Exemplos

Os exemplos criados anteriormente além de
serem lineares, estão na forma padrão:
max x1  x 2
max x1  2 x 2
s.r.
s.r.
2 x1  4 x 2  20
2 x1  4 x 2  20
180 x1  100 x 2  800
180 x1  100 x 2  800
x1 , x 2  0
x1 , x 2  0
26 / 43
Aula01.ppt
Forma Padrão:
Notação de Somatório
n
M axim izar: Z 
cx
i
i
Função-Objetivo
i 1
n
Sujeito a:
a
ij
x j  bi ( i  1, 2 , ... m )
j 1
x 1 , x 2 , x 3 , ... x n  0
Restrições
27 / 43
Aula01.ppt
Áreas de Aplicação da
Programação Linear

Administração da Produção:
• Alocação de Recursos Limitados;
Análise de Investimentos;
 Logística:

• Custo de transporte;
• Localização de rede de distribuição;

Alocação de Recursos em Marketing.
28 / 43