Upload
alexis-lorentinni
View
19
Download
0
Embed Size (px)
DESCRIPTION
P.O
Citation preview
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
1
CAPTULO 1 Programao Linear
1.1 Introduo
Este captulo visa estudar alguns problemas de otimizao que envolve maximizar ou
minimizar uma funo restrita a certas condies. Estamos sempre interessados em minimizar
custos, maximizar lucros, rendimentos etc. A programao linear uma tcnica que permite a
resoluo destes problemas no caso especfico em que as funes a serem analisadas so
lineares.
1.2 Conjuntos Convexos
Definio 1 Um subconjunto S de chamado convexo se para quaisquer dois pontos A e B
de S o segmento AB est inteiramente contido em S.
Exemplo 1. Observe as seguintes regies de .
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
2
1.3 Regio Poliedral Convexa Fechada
Definio 2 Um conjunto que divide um espao vetorial em dois semi-espaos chamado de
hiperplano.
Exemplo 2. Considere os seguintes espaos vetoriais:
No espao tridimensional o hiperplano um plano;
No espao bidimensional o hiperplano uma reta;
No espao unidimensional o hiperplano um ponto.
Observe que o hiperplano divide o espao vetorial em 2 semi-espaos.
Para hiperplanos definidos por uma equao de mais do que trs variveis no teremos
uma viso geomtrica dos semi-espaos vetoriais como nos exemplos anteriores, mas estes
conceitos so abordados da mesma maneira:
Definio 3 Uma regio poliedral convexa fechada em uma interseo de uma quantidade
finita de semi-espaos fechados do .
1.4 Desigualdades Lineares
Os semi-espaos so dados por desigualdades lineares, uma desigualdade linear
simplesmente uma equao linear, onde o sinal de igual substitudo por ou .
Exemplo 3. Seja a desigualdade linear 2 8x y+ .
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
3
Soluo: Primeiramente substitumos o sinal por =, assim tornamos a desigualdade uma
equao linear, representamos essa equao no plano e em seguida, observamos qual semiplano
satisfaz a desigualdade (pela simplicidade dos clculos, geralmente utilizamos a origem do plano
para verificar a regio satisfeita pela desigualdade).
1.5 Programao Linear (PL)
A programao linear trata do problema especfico de: maximizar ou minimizar uma funo
do tipo:
1 1 1( , , ) , , ,n n nf x x a x a x b= +K K restrita a um subconjunto A poliedral convexo de . Na linguagem de programao linear (PL), f chamada funo objetivo (f.o.) e A denominada regio factvel, ou seja, regio onde obtida a
soluo do problema.
Definio 4 Dada uma regio poliedral convexa fechada do , os vrtices dessa regio so os
pontos da regio que satisfazem um dos possveis sistemas de equaes lineares independentes,
obtidas substituindo-se as desigualdades por igualdades.
Exemplo 4. Observe a situao a seguir, onde h uma empresa que pretende otimizar a produo
mensal de dois produtos A e B:
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
4
Nesta situao necessria entender que:
O objetivo maximizar o lucro total da venda da produo;
A produo est superiormente limitada pelos 300 metros de madeira e 110 horas de
trabalho disponveis;
So possveis vrios nveis de produo;
Dos possveis nveis de produo necessrio conhecer qual ou quais podem classificar-se
de timos.
Como programar matematicamente esta situao (modelo matemtico linear) para obter
informaes para a tomada de deciso?
Primeira pergunta: Quantas unidades de A e B podemos produzir?
Definir as duas variveis de deciso:
x1 como o nmero de unidades do produto A;
x2 como o nmero de unidades do produto B.
Segunda pergunta: Que valores podemos admitir para as variveis de deciso?
Em x1 unidades de A consomem-se 30x1 metros de madeira;
Em x2 unidades de B consomem-se 20x2 metros de madeira.
No podemos ultrapassar os 300 metros de madeira disponveis ento 1 230 20 300x x+ .
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
5
Em x1 unidades de A consomem-se 5x1 horas de trabalho;
Em x2 unidades de B consomem-se 10x2 horas de trabalho.
No podemos ultrapassar as 110 horas de trabalho disponveis ento 1 25 10 110x x+ .
E a restrio de no negatividade do problema 1 0x e 2 0x .
Terceira pergunta: Qual o objetivo a ser alcanado com a produo de A e B?
O lucro da venda de 1 unidade de A de $ 6;
O lucro da venda de 1 unidade de B de $ 8.
O lucro total da venda de x1 unidades de A e de x2 unidades de B de 1 26 8x x+ .
O objetivo conhecer o maior valor que possvel ao atingir o lucro total 1 26 8x x+ , ou seja,
necessrio calcular o mximo da funo linear 1 2 1 2( , ) 6 8f x x x x= + , condicionado s restries.
Resumindo:
Maximizar o lucro total das vendas 1 2 1 2( , ) 6 8f x x x x= + (funo objetivo);
Restries do problema 1 2: 30 20 300Madeira x x+ e :Horas de trabalho
1 25 10 110x x+ ;
Restries de no negatividades 1 2, 0x x .
Geometria do modelo de Programao Linear
Considere um sistema de eixos cartesianos com o eixo das abscissas associado a x1 (produo de
A) e o eixo das ordenadas associado a x2 (produo de B). Relaxando a condio de desigualdade
das restries tcnicas, estas passam a ser equaes que definem retas. Cada uma destas retas
divide o espao em dois semi-espaos.
A figura a seguir apresenta o sistema de eixos e as duas retas:
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
6
Pela condio de no negatividade temos que, somente os pontos do 1 quadrante so solues
admissveis. Pela outras restries tcnicas dos problemas obtemos a regio das possveis
solues do problema.
Pelas intersees de todos os semi-espaos definidos pelas desigualdades temos a regio poliedral
convexa fechada (regio factvel).
A figura a seguir apresenta o espao de solues possveis (regio factvel)
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
7
Qualquer ponto da regio factvel uma possvel soluo, ento agora resta saber qual deste ponto
torna o valor mximo para a funo objetivo.
Considere:
A funo tem valor 0, a equao desta curva de nvel 1 26 8 0x x+ = ;
A funo tem valor 24, a equao desta curva de nvel 1 26 8 24x x+ = ;
A funo tem valor 48, a equao desta curva de nvel 1 26 8 48x x+ = .
Da anlise da figura acima, verificamos que o valor da funo aumenta medida que nos afastamos
da origem, ento a ltima curva de nvel que podemos traar contendo um ponto da regio factvel
a correspondente ao mximo da funo objetivo.
Obs: Se a ltima curva de nvel pertencer a mais do que um ponto da regio factvel, haver vrias
solues timas alternativas, dizemos que a soluo tima indeterminada ou mltipla.
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
8
A figura a seguir mostra que o ponto de interseo das retas 1 230 20 300x x+ = e
1 25 10 110x x+ = o ponto timo com coordenada (4, 9) sendo o mximo da funo objetivo:
(4,9) 6 4 8 9 24 72 96f = + = + =
A produo tima , portanto de 4 unidades de A e 9 unidades de B a que est associada o lucro
mximo de 96 dlares.
Vetor gradiente:
O gradiente da funo perpendicular s curvas de nvel da funo e indica a direo e o sentido
em que a funo aumenta mais rapidamente, portanto podemos utiliz-lo para identificar o ponto
timo na regio factvel.
O vetor gradiente o conjunto das derivadas parciais de uma funo e representaremos por:
, , , , , ,
Retornando ao exemplo, calculemos o gradiente da funo objetivo.
, 6, 8
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
9
A ltima reta que se pode traar indica o ponto ou pontos em que a funo atinge o seu mximo.
Na figura a seguir podemos ver o espao das solues admissveis, o gradiente da funo e as
curvas de nvel na origem dos eixos (funo com valor nulo) e no ponto timo (funo com valor 96).
Obs: Se o objetivo for minimizar a funo objetivo, o sentido em que a funo decresce o oposto
ao indicado pelo vetor gradiente.
Exemplo 5. Considere que um agricultor queira adubar a sua plantao e disponha de dois tipos de
adubo. O primeiro contm 3 g de fsforo, 1 g de nitrognio e 8 g de potssio, e custa $ 10 por
quilograma. O segundo tipo contm 2 g de fsforo, 3 g de nitrognio e 2 g de potssio, e custa $ 8
por quilograma. Sabemos que um quilograma de adubo d para 10 m de terra, e que o solo em que
esto suas plantaes necessita de pelo menos 3 g de fsforo, 1,5 g de nitrognio e 4 g de potssio
a cada 10m. Quanto o agricultor deve comprar de cada adubo, para cada 10 de terra, de modo a
conseguir ter o mnimo custo?
Soluo:
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
10
x primeiro adubo y segundo adubo Necessidades mnimas de adubo
Fsforo 3 2 3
Nitrognio 1 3 1,5
Potssio 8 2 4
Custo $ 10 Custo $ 8
Chamemos de x a quantidade em kg do primeiro tipo de adubo e y a do segundo tipo;
Primeira restrio 0x e 0y ;
Segunda restrio 3 2 3x y+ ;
Terceira restrio 3 1,5x y+ ;
Quarta restrio 8 2 4x y+ .
Colocando num grfico as quantidades x (como abscissa) e y (como ordenada) temos:
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
11
1.6 Atividades
Exerccio 1. Faa o grfico dos seguintes sistemas de desigualdades simultneas:
(a)
2 41
4
x yx yy
+
(b)
00
22 3
x
yx y
x y
+ +
(c)
00
3 2
x
yx y
+
(d)
4 3 122 23 3
x yx yy x
+
Exerccio 2. Determine o valor mximo e o valor mnimo da funo lucro 15 25L x y= + , sujeita
s seguintes condies:
(a)
00
3 4 15
x
yx y
+
(b)
0053
x
yx
y
(c)
00
252 2 10
x
yx y
x y
+ +
Exerccio 3. Determine o mximo da funo expressa por 2 ,x y+ sujeita s restries 0x ,
0y , 3x y+ e 4 0x y+ :
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
12
Exerccio 4. (Problema de economia) Um comerciante vende dois tipos de artigos, A e B. Na venda
do artigo A tem um lucro de 20 por unidade e na venda do artigo B, um lucro de 30. Em seu
depsito s cabem 100 artigos e sabe-se que por compromissos j assumidos, ele vender pelo
menos 15 artigos do tipo A e 25 do tipo B. O distribuidor pode entregar ao comerciante, no mximo,
60 artigos A e 50 artigos B. Quantos artigos de cada tipo devero o comerciante encomendar ao
distribuidor para que, supondo que os venda todos, obtenha o lucro mximo?
Exerccio 5. (Problema de transporte) Uma firma comercial tem 40 unidades de mercadoria no
depsito D1 e 50 unidades no depsito D2. Deve enviar 30 unidades ao cliente A e 40 ao cliente B.
Os gastos de transporte por unidade de mercadoria esto indicados no esquema abaixo. De que
maneira deve enviar essas mercadorias para que o gasto com transporte seja mnimo?
Exerccio 6. (Problema de dieta) Dois produtos P e Q contm as vitaminas A, B e C nas
quantidades indicadas na tabela a seguir. A ltima coluna indica a quantidade mnima necessria de
cada vitamina para uma alimentao sadia, e a ltima linha indica o preo de cada produto por
unidade. Que quantidade de cada produto uma dieta deve conter para que proporcione uma
alimentao sadia com o mnimo custo?
P Q
A 3 1 12
B 3 4 30
C 2 7 28
3 2
Exerccio 7. Uma empresa fabrica dois produtos, A e B. O volume de vendas de A de no mnimo
80% do total de vendas de ambos. Contudo, a empresa no pode vender mais do que 100 unidades
de A por dia. Ambos os produtos usam uma matria-prima cuja disponibilidade mxima diria 240
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
13
lb. As taxas de utilizao da matria-prima so 2 lb por unidade de A e 4 lb por unidade de B. Os
lucros unitrios para A e B so $ 20 e $ 50, respectivamente. Determine a quantidade de cada
produto para que o lucro seja mximo.
Exerccio 8. Uma empresa fabrica chapas e barras de alumnio. A capacidade mxima de
produo estimada so 800 chapas ou 600 barras por dia. A demanda mxima diria so 550
chapas e 580 barras. O lucro por tonelada $ 40 por chapa e $ 35 por barra. Determine a
quantidade tima de produo diria.
Exerccio 9. Um indivduo quer investir $ 5.000 no prximo ano em dois tipos de investimento: o
investimento A rende 5% e o investimento B rende 8%. Pesquisas de mercado recomendam uma
alocao de no mnimo 25% em A e no mximo 50% em B. Alm do mais, o investimento em A
deve ser no mnimo metade do investimento em B. Como o fundo deveria ser alocado aos dois
investimentos?
Exerccio 10. Uma mquina produz dois tipos A e B de frascos de vidro, mas no
simultaneamente. Ao produzir um frasco do tipo A, ela gasta 0,2 horas, e ao produzir um tipo B,
gasta 0,4 horas. Sabendo que a mquina pode trabalhar no mximo 16 horas por dia e que o
fabricante tem um lucro de $ 2 com um frasco tipo A e $ 3 com um frasco tipo B, quantos frascos de
cada tipo devem ser produzidos para que o lucro seja mximo?
Exerccio 11. Uma companhia de transporte dispe de 4 caminhes com capacidade para
transportar 5.000 kg, 4 caminhes de 10.000 kg de capacidade e 2 caminhes de 20.000 kg de
capacidade. O custo por hora dos caminhes do primeiro tipo $ 200, do segundo $ 300 e do
terceiro $ 400. Como devem ser usados os caminhes para transportar uma carga de 80.000 kg,
para que o custo seja mnimo?
Exerccio 12. Uma indstria produz porcas, parafusos e pregos, podendo usar dois mtodos
distintos (mas no simultaneamente) para produzi-los. O primeiro mtodo produz 3.000 porcas,
2.000 parafusos e 2.500 pregos por hora, enquanto o segundo produz 4.000 parafusos e 4.000
pregos por hora, mas nenhuma porca. A indstria trabalha 18 horas por dia e tem uma encomenda
de 5.000 porcas, 5.000 parafusos e 5.000 pregos. Durante quantas horas ela deve empregar cada
mtodo para fazer a entrega o mais rapidamente possvel?
Captulo 1 Programao Linear
Pesquisa Operacional I Jhoab Negreiros
14
Exerccio 13. Numa indstria qumica h uma caldeira cuja margem de segurana tal que a
presso P medida em atmosferas, e a temperatura T, medida em graus Celsius, devem ser
reguladas de maneira que 10 400P T+ . Quer-se usar a caldeira para que seja processada uma determinada reao. Para que isto ocorra da forma desejada, a temperatura deve estar entre 80C
e 300C, e a presso entre 1 e 20 atmosferas. A que temperatura e presso deve trabalhar a
caldeira para que a reao se processe no menor tempo possvel, se sabemos que a velocidade da
reao dada por 2 30 20v T P= + + ?