OTIMIZAÇÃO LINEAR

Prévia do material em texto

Ga
ldi
no
UE
NF
Engenharia de Produc¸a˜o
Pesquisa Operacional
Aplicac¸a˜o do me´todo cientı´fico a processos de tomada de
decisa˜o, tais como planejar, projetar, e operar sistemas em
situac¸o˜es que requerem alocac¸a˜o eficiente de recursos es-
cassos — Arenales et al., 2007
Ga
ldi
no
UE
NF
Me´todo Cientı´fico
O
bs
er
va
r
e
qu
es
tio
na
r
Te
st
ar
 a
s 
hi
pó
te
se
s,
 
co
nd
uz
in
do
 
ex
pe
rim
en
to
s
Fo
rm
ul
ar
 h
ip
ót
es
es
P
es
qu
is
ar
C
ol
et
ar
 d
ad
os
A
ná
lis
e 
e 
sí
nt
es
e
E
xa
m
in
ar
 o
s 
re
su
lta
do
s 
ex
pe
rim
en
ta
is
 e
 
ch
eg
ar
 a
 c
on
cl
us
õe
s
P
en
sa
r n
ov
am
en
te
A
 h
ip
ót
es
e 
é 
ve
rd
ad
ei
ra
A
 h
ip
ót
es
e 
é 
fa
ls
a
R
el
at
ar
 r
es
ul
ta
do
s
Ga
ldi
no
UE
NF
Origem
A Pesquisa Operacional teve suas origens nos
anos 1930, quando foi pedido a um grupo de
oficiais da Real Força Aérea Britânica e a cien-
tistas civis que determinassem como a recente
tecnologia de radares poderia ser usada para in-
terceptação controlada de aeronaves inimigas
Ga
ldi
no
UE
NF
A´reas da Pesquisa Operacional
Otimizac¸a˜o Linear
Otimizac¸a˜o Na˜o–Linear
Otimizac¸a˜o Inteira
Otimizac¸a˜o Dinaˆmica
Otimizac¸a˜o Estoca´stica
Otimizac¸a˜o Geome´trica
Fluxos em Rede
Heurı´sticas e Metaheurı´sticas
Filas
Estoques
Simulac¸a˜o
Confiabilidade
Previsa˜o
Ga
ldi
no
UE
NF
Otimização Linear
Programação LinearÑ Otimização Linear
Ga
ldi
no
UE
NF
Otimização Linear
Programação LinearÑ Otimização Linear
Ga
ldi
no
UE
NF
O problema de otimizac¸a˜o linear
Considera-se uma instalac¸a˜o industrial capaz de
produzir uma variedade de n produtos. Esses sa˜o
enumerados como 1,2,…,n.
Eles sa˜o manufaturados a partir de algumas
mate´rias primas.
Assume-se que existam m mate´rias primas
diferentes, que sa˜o enumeradas como 1,2,…,m.
Ga
ldi
no
UE
NF
O problema de otimizac¸a˜o linear
Considera-se uma instalac¸a˜o industrial capaz de
produzir uma variedade de n produtos. Esses sa˜o
enumerados como 1,2,…,n.
Eles sa˜o manufaturados a partir de algumas
mate´rias primas.
Assume-se que existam m mate´rias primas
diferentes, que sa˜o enumeradas como 1,2,…,m.
Ga
ldi
no
UE
NF
O problema de otimizac¸a˜o linear
Considera-se uma instalac¸a˜o industrial capaz de
produzir uma variedade de n produtos. Esses sa˜o
enumerados como 1,2,…,n.
Eles sa˜o manufaturados a partir de algumas
mate´rias primas.
Assume-se que existam m mate´rias primas
diferentes, que sa˜o enumeradas como 1,2,…,m.
Ga
ldi
no
UE
NF
O problema de otimizac¸a˜o linear
Considera-se uma instalac¸a˜o industrial capaz de
produzir uma variedade de n produtos. Esses sa˜o
enumerados como 1,2,…,n.
Eles sa˜o manufaturados a partir de algumas
mate´rias primas.
Assume-se que existam m mate´rias primas
diferentes, que sa˜o enumeradas como 1,2,…,m.
Ga
ldi
no
UE
NF
O modelo de otimizac¸a˜o linear
maximizar `1x1` `2x2`¨¨ ¨` `nxn
sujeito a a11x1` a12x2`¨¨ ¨` a1nxnď b1
a21x1` a22x2`¨¨ ¨` a2nxnď b2
...
am1x1`am2x2`¨¨ ¨`amnxnďbm
xj ě 0, j “ 1,2,…,n
Ga
ldi
no
UE
NF
Modelo de otimizac¸a˜o linear
(com crite´rio de minimizac¸a˜o)
minimizar c1x1` c2x2`¨¨ ¨` cnxn
sujeito a a11x1` a12x2`¨¨ ¨` a1nxně b1
a21x1` a22x2`¨¨ ¨` a2nxně b2
...
am1x1`am2x2`¨¨ ¨`amnxněbm
xj ě 0, j “ 1,2,…,n
Ga
ldi
no
UE
NF
Exemplo
maximizar 3x1`2x2
sujeito a ´x1`3x2ď12
x1` x2ď 8
2x1´ x2ď10
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NF
Representac¸a˜o gra´fica
5. GEOMETRY 23
1 2 3 4 5 60
0
1
2
3
4
5
6
x1
x2
−x1+3x2=12 x1+x2=8
2x1−x2=10
3x1+2x2=22
3x1+2x2=11
FIGURE 2.1. The set of feasible solutions together with level sets
of the objective function.
solution. To illustrate, consider the following problem:
maximize 3x1 + 2x2
subject to −x1 + 3x2 ≤ 12
x1 + x2 ≤ 8
2x1 − x2 ≤ 10
x1, x2 ≥ 0.
Each constraint (including the nonnegativity constraints on the variables) is a half-
plane. These half-planes can be determined by first graphing the equation one obtains
by replacing the inequality with an equality and then asking whether or not some
specific point that doesn’t satisfy the equality (often (0, 0) can be used) satisfies the
inequality constraint. The set of feasible solutions is just the intersection of these half-
planes. For the problem given above, this set is shown in Figure 2.1. Also shown
are two level sets of the objective function. One of them indicates points at which
the objective function value is 11. This level set passes through the middle of the
set of feasible solutions. As the objective function value increases, the corresponding
level set moves to the right. The level set corresponding to the case where the objec-
tive function equals 22 is the last level set that touches the set of feasible solutions.
Conjunto de soluc¸o˜es via´veis com as curvas de nı´vel da func¸a˜o
objetivo
Ga
ldi
no
UE
NF
Modelagem
O processo de modelagem esta´ inserido num conjunto de iniciativas
que sa˜o resumidas por
Entender o ambiente ou objeto de decisa˜o
Construir o modelo
Solucionar o modelo
Interpretar e validar os resultados do modelo
Retornar ao ambiente ou objeto de decisa˜o
Ga
ldi
no
UE
NF
Exemplos de modelos de otimizac¸a˜o linear
Programas lineares
Ga
ldi
no
UE
NF
Uma refinaria de petro´leo pode adquirir dois tipos de o´leo: o´leo cru
leve e o´leo cru pesado. Os custos por barril sa˜o, respectivamente, 40
e 30. A tabela a seguir indica as quantidades (em barris) de gasolina,
querosene e combustı´vel de avia˜o, que podem ser produzidas por barril
de cada tipo de o´leo cru.
Tipo de o´leo cru Gasolina Querosene Combustı´vel de avia˜o
Leve 0,45 0,18 0,32
Pesado 0,34 0,36 0,22
A refinaria tem contrato de fornecimento de 1.200.000 barris de ga-
solina, 500.000 barris de querosene e 300.000 barris de combustı´vel
de avia˜o. Formule um modelo de otimizac¸a˜o linear para determinar o
nu´mero de barris de cada tipo de o´leo a serem adquiridos pela refinaria,
visando minimizar o custo de atendimento da demanda.
Ga
ldi
no
UE
NF
Soluc¸a˜o:
x1 e´ o nu´mero de barris de o´leo cru do tipo leve e
x2 e´ o nu´mero de barris de o´leo cru do tipo pesado
Tem-se:
minimizar z “ 40x1 ` 30x2
sujeito a 0,45x1 ` 0,34x2 ě 1.200.000
0,18x1 ` 0,36x2 ě 500.000
0,32x1 ` 0,22x2 ě 300.000
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NF
Soluc¸a˜o:
x1 e´ o nu´mero de barris de o´leo cru do tipo leve e
x2 e´ o nu´mero de barris de o´leo cru do tipo pesado
Tem-se:
minimizar z “ 40x1 ` 30x2
sujeito a 0,45x1 ` 0,34x2 ě 1.200.000
0,18x1 ` 0,36x2 ě 500.000
0,32x1 ` 0,22x2 ě 300.000
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NF
Soluc¸a˜o:
x1 e´ o nu´mero de barris de o´leo cru do tipo leve e
x2 e´ o nu´mero de barris de o´leo cru do tipo pesado
Tem-se:
minimizar z “ 40x1 ` 30x2
sujeito a 0,45x1 ` 0,34x2 ě 1.200.000
0,18x1 ` 0,36x2 ě 500.000
0,32x1 ` 0,22x2 ě 300.000
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NFUma cooperativa agrı´cola cria vacas e carneiros. A cooperativa tem
esta´bulos para 50 vacas e instalac¸o˜es para 200 carneiros. Tem tambe´m
72 hectares de pasto. Um hectare e´ necessa´rio para sustentar uma vaca
e 0,2 hectare para um carneiro. Para cuidar dos animais, a cooperativa
pode prover ate´ 110.000 horas de trabalho por ano. Uma vaca requer
150 horas e um carneiro 25 horas por ano. O lucro anual e´ de 250,00
por vaca e 45,00 por carneiro.A cooperativa gostaria de determinar o
nu´mero de vacas e carneiros a serem criados de forma a maximizar seu
lucro.
Ga
ldi
no
UE
NF
Soluc¸a˜o:
x1 e´ o nu´mero de vacas e
x2 e´ o nu´mero de carneiros a serem criados
Tem-se:
maximizar z “ 250x1 ` 45x2
sujeito a x1 ď 50
x2 ď 200
x1 ` 0,2x2 ď 72
150x1 ` 25x2 ď 110.000
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NF
Soluc¸a˜o:
x1 e´ o nu´mero de vacas e
x2 e´ o nu´mero de carneiros a serem criados
Tem-se:
maximizar z “ 250x1 ` 45x2
sujeito a x1 ď 50
x2 ď 200
x1 ` 0,2x2 ď 72
150x1 ` 25x2 ď 110.000
xj ě 0, j “ 1,2
Ga
ldi
no
UE
NF
Uma fa´brica produz treˆs tipos de chapas meta´licas, A, B e C, que sa˜o
primeiramente prensadas e depois esmaltadas. A prensa dispo˜e de
2000 minutos livres por meˆs e cada chapa A ou B, leva um minuto
para ser prensada, enquanto que a chapa C leva o dobro do tempo de-
vido ao tamanho maior. Por outro lado, a aplicac¸a˜o de esmalte nesta
u´ltima chapa leva apenas um minuto, enquanto que as chapas A e B
exigem 3 e 4,5 minutos, respectivamente. O total de tempo disponı´vel
na sec¸a˜o de esmaltagem e´ de 8000 minutos por meˆs. A demanda dos
treˆs tipos de chapa absorve facilmente toda a produc¸a˜o e o lucro rela-
tivo a`s chapas A, B e C e´ de 205, 107 e 308 por unidade, respectiva-
mente. Formule um modelo de otimizac¸a˜o linear que permita a` fa´brica
determinar a produc¸a˜o o´tima de chapas.
Ga
ldi
no
UE
NF
xA, xB , xC representam as quantidades de chapas de cada tipo.
Tem-se:
maximizar z “ 205xA ` 107xB ` 308xC
sujeito a xA ` xB ` 2xC ď 2000
3xA ` 4,5xB ` xC ď 8000
xj ě 0, j “A,B,C
Ga
ldi
no
UE
NF
xA, xB , xC representam as quantidades de chapas de cada tipo.
Tem-se:
maximizar z “ 205xA ` 107xB ` 308xC
sujeito a xA ` xB ` 2xC ď 2000
3xA ` 4,5xB ` xC ď 8000
xj ě 0, j “A,B,C
Ga
ldi
no
UE
NF
Uma fa´brica de geradores ele´tricos tem treˆs depo´sitos nas regio˜es A, B
e C. Estes depo´sitos abastecem cinco depo´sitos secunda´rios mediante
pedidos dirigidos a uma gereˆncia central. Os depo´sitos secunda´rios
esta˜o localizados nas regio˜es 1, 2, 3, 4 e 5. A gereˆncia tem pedidos
para entrega de 52 geradores distribuı´dos de acordo com a tabela a
seguir.
depo´sito demanda depo´sito oferta
1 8 A 27
2 12 B 23
3 8 C 12
4 9
5 15
Ga
ldi
no
UE
NF
A gereˆncia observa que existe a possibilidade de entrega imediata
dos pedidos. Todavia o custo de transporte de um gerador, de um
depo´sito para outro, e´ diferente. A tabela abaixo informa esses cus-
tos. O problema da gereˆncia consiste em determinar quantos geradores
cada depo´sito central deve despachar para cada depo´sito secunda´rio de
modo a atender os pedidos com o menor custo de transporte possı´vel.
Formule um modelo de otimizac¸a˜o linear para resolver este problema.
depo´sito (destino)
depo´sito (origem) 1 2 3 4 5
A 6 3 1 4 2
B 7 2 2 7 3
C 5 4 5 5 2
Ga
ldi
no
UE
NF
xij ,pi “ A,B,C, j “ 1,2,3,4,5q e´ o nu´mero de geradores enviados
pelo depo´sito central i ao depo´sito secunda´rio j. cij e´ o custo unita´rio
de transporte correspondente.
Tem-se:
minimizar z“6xA1`3xA2` xA3`4xA4`2xA5`
7xB1`2xB2`2xB3`7xB4`3xB5`
5xC1`4xC2`5xC3`5xC4`2xC5
sujeito a xA1` xA2` xA3` xA4` xA5ď27
xB1` xB2` xB3` xB4` xB5ď23
xC1` xC2` xC3` xC4` xC5ď12
xA1` xB1` xC1 “ 8
xA2` xB2` xC2 “12
xA3` xB3` xC3 “ 8
xA4` xB4` xC4 “ 9
xA5` xB5` xC5 “15
xij ě 0, i“A,B,C, j “ 1,2,3,4,5
Ga
ldi
no
UE
NF
xij ,pi “ A,B,C, j “ 1,2,3,4,5q e´ o nu´mero de geradores enviados
pelo depo´sito central i ao depo´sito secunda´rio j. cij e´ o custo unita´rio
de transporte correspondente. Tem-se:
minimizar z“6xA1`3xA2` xA3`4xA4`2xA5`
7xB1`2xB2`2xB3`7xB4`3xB5`
5xC1`4xC2`5xC3`5xC4`2xC5
sujeito a xA1` xA2` xA3` xA4` xA5ď27
xB1` xB2` xB3` xB4` xB5ď23
xC1` xC2` xC3` xC4` xC5ď12
xA1` xB1` xC1 “ 8
xA2` xB2` xC2 “12
xA3` xB3` xC3 “ 8
xA4` xB4` xC4 “ 9
xA5` xB5` xC5 “15
xij ě 0, i“A,B,C, j “ 1,2,3,4,5
Ga
ldi
no
UE
NF
xij ,pi “ A,B,C, j “ 1,2,3,4,5q e´ o nu´mero de geradores enviados
pelo depo´sito central i ao depo´sito secunda´rio j. cij e´ o custo unita´rio
de transporte correspondente. Tem-se:
minimizar z“6xA1`3xA2` xA3`4xA4`2xA5`
7xB1`2xB2`2xB3`7xB4`3xB5`
5xC1`4xC2`5xC3`5xC4`2xC5
sujeito a xA1` xA2` xA3` xA4` xA5ď27
xB1` xB2` xB3` xB4` xB5ď23
xC1` xC2` xC3` xC4` xC5ď12
xA1` xB1` xC1 “ 8
xA2` xB2` xC2 “12
xA3` xB3` xC3 “ 8
xA4` xB4` xC4 “ 9
xA5` xB5` xC5 “15
xij ě 0, i“A,B,C, j “ 1,2,3,4,5
Ga
ldi
no
UE
NF
xij ,pi “ A,B,C, j “ 1,2,3,4,5q e´ o nu´mero de geradores enviados
pelo depo´sito central i ao depo´sito secunda´rio j. cij e´ o custo unita´rio
de transporte correspondente. Tem-se:
minimizar z“6xA1`3xA2` xA3`4xA4`2xA5`
7xB1`2xB2`2xB3`7xB4`3xB5`
5xC1`4xC2`5xC3`5xC4`2xC5
sujeito a xA1` xA2` xA3` xA4` xA5ď27
xB1` xB2` xB3` xB4` xB5ď23
xC1` xC2` xC3` xC4` xC5ď12
xA1` xB1` xC1 “ 8
xA2` xB2` xC2 “12
xA3` xB3` xC3 “ 8
xA4` xB4` xC4 “ 9
xA5` xB5` xC5 “15
xij ě 0, i“A,B,C, j “ 1,2,3,4,5
Ga
ldi
no
UE
NF
O corpo de enfermagem de um hospital tem a necessidade de pessoal
de acordo com a tabela a seguir.
Nu´mero mı´nimo de
Perı´odo 24 horas/dia enfermeiras necessa´rias
1 06 a`s 10 30
2 10 a`s 14 40
3 14 a`s 18 30
4 18 a`s 22 20
5 22 a`s 02 10
6 02 a`s 06 15
As enfermeiras se apresentam na enfermaria do hospital no inı´cio de
cada perı´odo e trabalham 8 horas consecutivas. A administrac¸a˜o do
hospital deseja determinar o nu´mero mı´nimo de enfermeiras a se-
rem empregadas, de forma a atender satisfatoriamente a cada perı´odo.
Estabelec¸a um modelo de otimizac¸a˜o linear que permita atingir este
objetivo.
Ga
ldi
no
UE
NF
Seja xj e´ o nu´mero de enfermeiras que entram no perı´odo j “ 1,…,6.
Tem-se:
minimizar z“x1`x2`x3`x4`x5`x6
sujeito a x1 `x6ě30
x1`x2 ě40
x2`x3 ě30
x3`x4 ě20
x4`x5 ě10
x5`x6ě15
xj ě 0, j “ 1,…,6
Ga
ldi
no
UE
NF
Seja xj e´ o nu´mero de enfermeiras que entram no perı´odo j “ 1,…,6.
Tem-se:
minimizar z“x1`x2`x3`x4`x5`x6
sujeito a x1 `x6ě30
x1`x2 ě40
x2`x3 ě30
x3`x4 ě20
x4`x5 ě10
x5`x6ě15
xj ě 0, j “ 1,…,6
Ga
ldi
no
UE
NF
Uma empresa pode fabricar, com uma ma´quina trabalhando 45 horas
por semana, treˆs artigos diferentes: A1, A2, A3. O artigo A1 da´ um
lucro lı´quido de 4,00, o artigo A2 de 12,00 e o artigo A3 de 3,00. Os
rendimentos da ma´quina sa˜o, respectivamente, 50, 25 e 75 artigos por
hora. Um estudo de mercado mostrou que as possibilidades de venda
na˜o ultrapassam 100 objetosA1, 500 objetosA2 e 1500 objetosA3, por
semana. Pede-se que se reparta a capacidade de produc¸a˜o da empresa
entre os treˆs produtos, de maneira a maximizar o lucro lı´quido total.
Ga
ldi
no
UE
NF
Primeira Soluc¸a˜o:
Artigo Lucro Artigos por hora Demanda por semana
A1 4 50 100
A2 12 25 500
A3 3 75 1500
xj e´ o nu´mero de horas dedicadas ao artigo Aj , por semana.
maximizar z“p4 × 50qx1`p12 × 25qx2`p3 × 75qx3
sujeito a x1` x2` x3ď 45
50x1 ď 100
25x2 ď 500
75x3ď1500
xj ě 0, j “ 1,2,3
Ga
ldi
no
UE
NF
Primeira Soluc¸a˜o:
Artigo Lucro Artigos por hora Demanda por semana
A1 4 50 100
A2 12 25 500
A3 3 75 1500
xj e´ o nu´mero de horas dedicadas ao artigo Aj , por semana.
maximizar z“p4 × 50qx1`p12 × 25qx2`p3 × 75qx3
sujeito a x1` x2` x3ď 45
50x1 ď 100
25x2 ď 500
75x3ď1500
xj ě 0, j “ 1,2,3
Ga
ldi
no
UE
NF
Segunda soluc¸a˜o: xj e´ o nu´mero de artigos, do tipo Aj , produzidos
por semana. Se sa˜o produzidos 50 artigos do tipo A1 por hora, cada
artigo gasta para ser produzido, 150 da hora. Dessa forma os artigos
A2 e A3 gastam, respectivamente, 125 e
1
75 da hora. Com esses valores
cria-se uma ‘taxa de produc¸a˜o’ ou ‘taxa de uso do tempo’, usada numa
restric¸a˜o do problema.
maximizar z “ 4x1 `12x2 ` 3x3
sujeito a 150x1 ` 125x2 ` 175x3 ď 45
x1 ď 100
x2 ď 500
x3 ď 1500
xj ě 0, j “ 1,2,3
Ga
ldi
no
UE
NF
Segunda soluc¸a˜o: xj e´ o nu´mero de artigos, do tipo Aj , produzidos
por semana. Se sa˜o produzidos 50 artigos do tipo A1 por hora, cada
artigo gasta para ser produzido, 150 da hora. Dessa forma os artigos
A2 e A3 gastam, respectivamente, 125 e
1
75 da hora. Com esses valores
cria-se uma ‘taxa de produc¸a˜o’ ou ‘taxa de uso do tempo’, usada numa
restric¸a˜o do problema.
maximizar z “ 4x1 ` 12x2 ` 3x3
sujeito a 150x1 ` 125x2 ` 175x3 ď 45
x1 ď 100
x2 ď 500
x3 ď 1500
xj ě 0, j “ 1,2,3
Ga
ldi
no
UE
NFUma Ageˆncia de Propaganda planeja uma campanha de publicidade
em treˆs diferentes meios de comunicac¸a˜o: televisa˜o, ra´dio e mı´dia im-
pressa. O propo´sito da propaganda e´ o de alcanc¸ar tantos “consumi-
dores em potencial” quanto possı´vel. O resultado de um estudo de
mercado esta´ na tabela a seguir
Televisão
Horário Horário Rádio
Mídia
comum nobre
impressa
Custo de uma unidade de propaganda 40.000 75.000 30.000 15.000
Número de consumidores (*) 400.000 900.000 500.000 200.000
Número de consumidores do sexo feminino (*) 300.000 400.000 200.000 100.000
(*) em potencial alcançados por unidade de propaganda
Ga
ldi
no
UE
NF
A empresa que encomendou a campanha na˜o quer gastar mais de
800.000 com a propaganda. Ale´m disso requer que:
pelo menos 2 milho˜es de pessoas alcanc¸adas sejam do sexo
feminino.
a propaganda veiculada pela televisa˜o seja limitada a um custo
de 500.000.
pelo menos 3 unidades de propaganda veiculadas no hora´rio
comum, e pelo menos 2 unidades durante o hora´rio nobre, e
o nu´mero de unidades de propaganda, no ra´dio e na mı´dia
impressa, fique, individualmente, entre 5 e 10, inclusive.
Soluc¸a˜o:
x1 unidades de propaganda
no hora´rio comum
x2 unidades de propaganda
no hora´rio nobre
x3 unidades de propaganda
no ra´dio
x4 unidades de propaganda
na mı´dia impressa
Ga
ldi
no
UE
NF
A empresa que encomendou a campanha na˜o quer gastar mais de
800.000 com a propaganda. Ale´m disso requer que:
pelo menos 2 milho˜es de pessoas alcanc¸adas sejam do sexo
feminino.
a propaganda veiculada pela televisa˜o seja limitada a um custo
de 500.000.
pelo menos 3 unidades de propaganda veiculadas no hora´rio
comum, e pelo menos 2 unidades durante o hora´rio nobre, e
o nu´mero de unidades de propaganda, no ra´dio e na mı´dia
impressa, fique, individualmente, entre 5 e 10, inclusive.
Soluc¸a˜o:
x1 unidades de propaganda
no hora´rio comum
x2 unidades de propaganda
no hora´rio nobre
x3 unidades de propaganda
no ra´dio
x4 unidades de propaganda
na mı´dia impressa
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NF
Tem-se:
maximizar z“400x1`900x2`500x3`200x4
sujeito a 40x1` 75x2` 30x3` 15x4ď800
30x1` 40x2` 20x3` 10x4ě200
40x1` 70x2 ď500
x1 ě 3
x2 ě 2
x3 ě 5
x3 ď 10
x4ě 5
x4ď 10
Observac¸a˜o: Simplificar para nu´meros menores, quando for possı´vel,
reduz os erros de arredondamento que podem ocorrer nas soluc¸o˜es
por computador.
Ga
ldi
no
UE
NFUm fazendeiro tem que decidir o quanto vai plantar de milho e de al-
fafa. Os lucros sa˜o de 20.000 por alqueire de milho e de 10.000 por al-
queire de alfafa. Supo˜e-se que suas limitac¸o˜es sejam: terra disponı´vel:
8 alqueires; a´gua disponı´vel para irrigac¸a˜o: 80.000 litros. Que ele de-
seja plantar no ma´ximo 4 alqueires de milho; cada alqueire de milho
requerera´ 10.000 litros de a´gua para irrigac¸a˜o; cada alqueire de alfafa
requerera´ 20.000 litros de a´gua para irrigac¸a˜o. Formule um programa
linear para este problema. Supo˜e-se agora requerido que a quantidade
de alfafa plantada na˜o seja inferior a 30% do total cultivado. Refor-
mule o programa linear para atender a essa nova restric¸a˜o.
Ga
ldi
no
UE
NFx1 representa quantidade de alqueires a serem plantados com milho, e
x2 quantidade de alqueires a serem plantados com alfafa.
Tem-se:
maximizar z “ 20.000x1 ` 10.000x2
sujeito a x1 ` x2 ď 8
x1 ď 4
10.000x1 ` 20.000x2 ď 80.000
xj ě 0, j “ 1,2
Para atender a restric¸a˜o de que a quantidade de alfafa plantada na˜o
seja inferior a 30%do total cultivado, acrescenta-se ao programa a
restric¸a˜o x2 ě 0,3px1 ` x2q.
Ga
ldi
no
UE
NFx1 representa quantidade de alqueires a serem plantados com milho, e
x2 quantidade de alqueires a serem plantados com alfafa. Tem-se:
maximizar z “ 20.000x1 ` 10.000x2
sujeito a x1 ` x2 ď 8
x1 ď 4
10.000x1 ` 20.000x2 ď 80.000
xj ě 0, j “ 1,2
Para atender a restric¸a˜o de que a quantidade de alfafa plantada na˜o
seja inferior a 30% do total cultivado, acrescenta-se ao programa a
restric¸a˜o x2 ě 0,3px1 ` x2q.
Ga
ldi
no
UE
NF
Hipo´teses da otimizac¸a˜o linear
A formulac¸a˜o de um programa linear para modelar um problema de
otimizac¸a˜o e´ feita sob treˆs hipo´teses (ou axiomas):
proporcionalidade
aditividade e
divisibilidade
Ga
ldi
no
UE
NF
Hipo´tese de proporcionalidade:
Em otimizac¸a˜o linear “na˜o ha´ economia de escala”. Isto e´, se para
produzir uma unidade de um produto o custo e´ c, enta˜o, para produzir
x unidades do mesmo produto, o custo e´ cx.
Hipo´tese de aditividade:
Em otimizac¸a˜o linear “o todo e´ a soma das partes”. Se para produzir
uma unidade do produto 1 o custo e´ c1, e para produzir uma unidade
do produto 2 o custo e´ c2, enta˜o, para produzir x1 unidades do
produto 1 e x2 unidades do produto 2, o custo e´ c1x1 ` c2x2.
Hipo´tese de divisibilidade:
Os procedimentos de soluc¸a˜o dos programas lineares “na˜o garantem
a obtenc¸a˜o de valores inteiros” quando as atividades do modelo
forem representadas por quantidades inteiras, como nu´mero de casas,
de veı´culos ou de ma´quinas, por exemplo.
Ga
ldi
no
UE
NF
Hipo´tese de proporcionalidade:
Em otimizac¸a˜o linear “na˜o ha´ economia de escala”. Isto e´, se para
produzir uma unidade de um produto o custo e´ c, enta˜o, para produzir
x unidades do mesmo produto, o custo e´ cx.
Hipo´tese de aditividade:
Em otimizac¸a˜o linear “o todo e´ a soma das partes”. Se para produzir
uma unidade do produto 1 o custo e´ c1, e para produzir uma unidade
do produto 2 o custo e´ c2, enta˜o, para produzir x1 unidades do
produto 1 e x2 unidades do produto 2, o custo e´ c1x1 ` c2x2.
Hipo´tese de divisibilidade:
Os procedimentos de soluc¸a˜o dos programas lineares “na˜o garantem
a obtenc¸a˜o de valores inteiros” quando as atividades do modelo
forem representadas por quantidades inteiras, como nu´mero de casas,
de veı´culos ou de ma´quinas, por exemplo.
Ga
ldi
no
UE
NF
Hipo´tese de proporcionalidade:
Em otimizac¸a˜o linear “na˜o ha´ economia de escala”. Isto e´, se para
produzir uma unidade de um produto o custo e´ c, enta˜o, para produzir
x unidades do mesmo produto, o custo e´ cx.
Hipo´tese de aditividade:
Em otimizac¸a˜o linear “o todo e´ a soma das partes”. Se para produzir
uma unidade do produto 1 o custo e´ c1, e para produzir uma unidade
do produto 2 o custo e´ c2, enta˜o, para produzir x1 unidades do
produto 1 e x2 unidades do produto 2, o custo e´ c1x1 ` c2x2.
Hipo´tese de divisibilidade:
Os procedimentos de soluc¸a˜o dos programas lineares “na˜o garantem
a obtenc¸a˜o de valores inteiros” quando as atividades do modelo
forem representadas por quantidades inteiras, como nu´mero de casas,
de veı´culos ou de ma´quinas, por exemplo.
Ga
ldi
no
UE
NF
Otimizac¸a˜o em nu´meros inteiros
x1
x2
´3x1 ` 4x2 “ 4
3x1 ` 2x2 “ 11
2x1 ´ x2 “ 5
(2,2)
(0,1)
(0,0) (2,0) (2.5,0)
(3,1)
(2,2.5)