1_-_Programação_Linear

Prévia do material em texto

Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
1
 
 PRIMEIRA AULA 
Programação Linear 
 
 
 
1. Introdução 
 
Este capítulo visa estudar alguns problemas de otimização que envolve maximizar ou 
minimizar uma função restrita a certas condições. Estamos sempre interessados em minimizar custos, 
maximizar lucros, rendimentos etc. A programação linear é uma técnica que permite a resolução 
destes problemas no caso específico em que as funções a serem analisadas são lineares. 
 
2. Conjuntos Convexos 
 
Definição 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 regiões de ℝ . 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
2
 
 
3. Região Poliedral Convexa Fechada 
 
Definição 2 – Um conjunto que divide um espaço vetorial em dois semi-espaços é chamado de 
hiperplano. 
 
Exemplo 2. Considere os seguintes espaços vetoriais: 
 No espaço tridimensional o hiperplano é um plano; 
 No espaço bidimensional o hiperplano é uma reta; 
 No espaço unidimensional o hiperplano é um ponto. 
Observe que o hiperplano divide o espaço vetorial em 2 semi-espaços. 
 
 Para hiperplanos definidos por uma equação de mais do que três variáveis não teremos uma 
visão geométrica dos semi-espaços vetoriais como nos exemplos anteriores, mas estes conceitos são 
abordados da mesma maneira: 
 
Definição 3 – Uma região poliedral convexa fechada em ℝ é uma interseção de uma quantidade 
finita de semi-espaços fechados do ℝ . 
 
4. Desigualdades Lineares 
 
Os semi-espaços são dados por desigualdades lineares, uma desigualdade linear é 
simplesmente uma equação linear, onde o sinal de igual é substituído por <,  , > ou  . 
 
Exemplo 3. Seja a desigualdade linear 2 8x y  . 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
3
Solução: Primeiramente substituímos o sinal  por =, assim tornamos a desigualdade uma equação 
linear, representamos essa equação no plano e em seguida, observamos qual semiplano satisfaz a 
desigualdade (pela simplicidade dos cálculos, geralmente utilizamos a origem do plano para verificar 
a região satisfeita pela desigualdade). 
 
 
 
5. Atividades 
 
Exercício 1. Faça o gráfico dos seguintes sistemas de desigualdades simultâneas: 
 
(a) 
6 + 3 ≥ 12
≤ 10≤ 8
, ≥ 0
 
(b) 
2 + 3 ≤ 15
5 + 2 ≤ 20
, ≥ 0 
(c) 
> 5≥ 2
≤ 10< 13
 
(d) 
2 + 3 ≥ 24
4 + 2 ≥ 25, ≥ 0 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
4
6. Programação Linear (PL) 
 
A programação linear trata do problema específico de: maximizar ou minimizar uma função 
do tipo: 
1 1 1( , , ) , , ,n n nf x x a x a x b   
restrita a um subconjunto A poliedral convexo de ℝ . Na linguagem de programação linear (PL), f 
é chamada função objetivo (f.o.) e A é denominada região factível, ou seja, região onde é obtida a 
solução do problema. 
 
Definição 4 – Dada uma região poliedral convexa fechada do ℝ , os vértices dessa região são os 
pontos da região que satisfazem um dos possíveis sistemas de equações lineares independentes, 
obtidas substituindo-se as desigualdades por igualdades. 
 
Exemplo 4. Observe a situação a seguir, onde há uma empresa que pretende otimizar a produção 
mensal de dois produtos A e B: 
 
Nesta situação é necessária entender que: 
 O objetivo é maximizar o lucro total da venda da produção; 
 A produção está superiormente limitada pelos 300 metros de madeira e 110 horas de trabalho 
disponíveis; 
 São possíveis vários níveis de produção; 
 Dos possíveis níveis de produção é necessário conhecer qual ou quais podem classificar-se 
de ótimos. 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
5
Como programar matematicamente esta situação (modelo matemático linear) para obter 
informações para a tomada de decisão? 
 
Primeira pergunta: Quantas unidades de A e B podemos produzir? 
Definir as duas variáveis de decisão: 
x1 como o número de unidades do produto A; 
x2 como o número de unidades do produto B. 
 
Segunda pergunta: Que valores podemos admitir para as variáveis de decisão? 
Em x1 unidades de A consomem-se 30x1 metros de madeira; 
Em x2 unidades de B consomem-se 20x2 metros de madeira. 
Não podemos ultrapassar os 300 metros de madeira disponíveis então 1 230 20 300x x  . 
Em x1 unidades de A consomem-se 5x1 horas de trabalho; 
Em x2 unidades de B consomem-se 10x2 horas de trabalho. 
Não podemos ultrapassar as 110 horas de trabalho disponíveis então 1 25 10 110x x  . 
E a restrição de não negatividade do problema 1 0x  e 2 0x  . 
 
Terceira pergunta: Qual o objetivo a ser alcançado com a produção 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 é possível ao atingir o lucro total 1 26 8x x , ou seja, é 
necessário calcular o máximo da função linear 1 2 1 2( , ) 6 8f x x x x  , condicionado às restrições. 
Resumindo: 
 Maximizar o lucro total das vendas 1 2 1 2( , ) 6 8f x x x x  (função objetivo); 
 Restrições do problema 1 2: 30 20 300Madeira x x  e :Horas de trabalho 
1 25 10 110x x  ; 
 Restrições de não negatividades 1 2, 0x x  . 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
6
Geometria do modelo de Programação Linear 
 
Considere um sistema de eixos cartesianos com o eixo das abscissas associado a x1 (produção de 
A) e o eixo das ordenadas associado a x2 (produção de B). Relaxando a condição de desigualdade 
das restrições técnicas, estas passam a ser equações que definem retas. Cada uma destas retas 
divide o espaço ℝ em dois semi-espaços. 
 
A figura a seguir apresenta o sistema de eixos e as duas retas: 
 
 
Pela condição de não negatividade temos que, somente os pontos do 1° quadrante são soluções 
admissíveis. Pela outras restrições técnicas dos problemas obtemos a região das possíveis soluções 
do problema. 
 
Pelas interseções de todos os semi-espaços definidos pelas desigualdades temos a região poliedral 
convexa fechada (região factível). 
 
A figura a seguir apresenta o espaço de soluções possíveis (região factível) 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
7
 
Qualquer ponto da região factível é uma possível solução, então agora resta saber qual deste ponto 
torna o valor máximo para a função objetivo. 
 
Considere: 
 A função tem valor 0, a equação desta curva de nível é 1 26 8 0x x  ; 
 A função tem valor 24, a equação desta curva de nível é 1 26 8 24x x  ; 
 A função tem valor 48, a equação desta curva de nível é 1 26 8 48x x  . 
 
Programação Linear – Primeira aula 
Pesquisa Operacional IJhoab Negreiros 
8
Da análise da figura acima, verificamos que o valor da função aumenta à medida que nos afastamos 
da origem, então a última curva de nível que podemos traçar contendo um ponto da região factível é 
a correspondente ao máximo da função objetivo. 
 
Obs: Se a última curva de nível pertencer a mais do que um ponto da região factível, haverá várias 
soluções ótimas alternativas, dizemos que a solução ótima é indeterminada ou múltipla. 
 
A figura a seguir mostra que o ponto de interseção das retas 1 230 20 300x x  e 1 25 10 110x x  
é o ponto ótimo com coordenada (4, 9) sendo o máximo da função objetivo: 
(4,9) 6 4 8 9 24 72 96f        
 
 
A produção ótima é, portanto de 4 unidades de A e 9 unidades de B a que está associada o lucro 
máximo de 96 dólares. 
 
Vetor gradiente: 
O gradiente da função é perpendicular às curvas de nível da função e indica a direção e o sentido em 
que a função aumenta mais rapidamente, portanto podemos utilizá-lo para identificar o ponto ótimo 
na região factível. 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
9
O vetor gradiente é o conjunto das derivadas parciais de uma função e representaremos por: 
 
∇ ( , , … , ) = ( , , … , ) 
 
Retornando ao exemplo, calculemos o gradiente da função objetivo. 
 
∇ ( , ) = ( = 6, = 8) 
A última reta que se pode traçar indica o ponto ou pontos em que a função atinge o seu máximo. 
Na figura a seguir podemos ver o espaço das soluções admissíveis, o gradiente da função e as curvas 
de nível na origem dos eixos (função com valor nulo) e no ponto ótimo (função com valor 96). 
 
 
 
Obs: Se o objetivo for minimizar a função objetivo, o sentido em que a função decresce é o oposto ao 
indicado pelo vetor gradiente. 
 
 
 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
10
Exemplo 5. Uma empresa pode fabricar dois produtos. Na fabricação do produto A a empresa gasta 
nove horas-homem e três horas-máquina. Na fabricação do produto B a empresa gasta uma hora-
homem e uma hora-máquina. Sendo e as quantidades fabricadas dos produtos A e B e 
sabendo-se que a empresa dispõe de 18 horas-homem e12 horas-máquina e ainda que os lucros dos 
produtos são RS 40,00 e RS 10,00 respectivamente, quanto deve a empresa fabricar de cada produto 
para obter o maior lucro possível? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
11
7. Atividades 
 
Exercício 2. Determine o valor máximo e o valor mínimo da função lucro 15 25L x y  , sujeita às 
seguintes condições: 
(a) 
0
0
3 4 15
x
y
x y
   
 
(b) 
0
0
5
3
x
y
x
y
   
 
(c) 
0
0
25
2 2 10
x
y
x y
x y
     
 
 
Exercício 3. (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 depósito 
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 máximo, 60 artigos 
A e 50 artigos B. Quantos artigos de cada tipo deverão o comerciante encomendar ao distribuidor 
para que, supondo que os venda todos, obtenha o lucro máximo? 
 
Exercício 4. (Problema de transporte) Uma firma comercial tem 40 unidades de mercadoria no 
depósito D1 e 50 unidades no depósito D2. Deve enviar 30 unidades ao cliente A e 40 ao cliente B. 
Os gastos de transporte por unidade de mercadoria estão indicados no esquema abaixo. De que 
maneira deve enviar essas mercadorias para que o gasto com transporte seja mínimo? 
 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
12
Exercício 5. (Problema de dieta) Dois produtos P e Q contêm as vitaminas A, B e C nas quantidades 
indicadas na tabela a seguir. A última coluna indica a quantidade mínima necessária de cada vitamina 
para uma alimentação sadia, e a última linha indica o preço de cada produto por unidade. Que 
quantidade de cada produto uma dieta deve conter para que proporcione uma alimentação sadia com 
o mínimo custo? 
 P Q 
A 3 1 12 
B 3 4 30 
C 2 7 28 
 3 2 
 
Exercício 6. Uma empresa fabrica dois produtos, A e B. O volume de vendas de A é de no mínimo 
80% do total de vendas de ambos. Contudo, a empresa não pode vender mais do que 100 unidades 
de A por dia. Ambos os produtos usam uma matéria-prima cuja disponibilidade máxima diária é 240 
lb. As taxas de utilização da matéria-prima são 2 lb por unidade de A e 4 lb por unidade de B. Os 
lucros unitários para A e B são $ 20 e $ 50, respectivamente. Determine a quantidade de cada produto 
para que o lucro seja máximo. 
 
Exercício 7. Uma empresa fabrica chapas e barras de alumínio. A capacidade máxima de produção 
estimada são 800 chapas ou 600 barras por dia. A demanda máxima diária são 550 chapas e 580 
barras. O lucro por tonelada é $ 40 por chapa e $ 35 por barra. Determine a quantidade ótima de 
produção diária. 
 
Exercício 8. Um indivíduo quer investir $ 5.000 no próximo ano em dois tipos de investimento: o 
investimento A rende 5% e o investimento B rende 8%. Pesquisas de mercado recomendam uma 
alocação de no mínimo 25% em A e no máximo 50% em B. Além do mais, o investimento em A deve 
ser no mínimo metade do investimento em B. Como o fundo deveria ser alocado aos dois 
investimentos? 
 
Exercício 9. Uma companhia de transporte dispõe de 4 caminhões com capacidade para transportar 
5.000 kg, 4 caminhões de 10.000 kg de capacidade e 2 caminhões de 20.000 kg de capacidade. O 
custo por hora dos caminhões do primeiro tipo é $ 200, do segundo $ 300 e do terceiro $ 400. Como 
devem ser usados os caminhões para transportar uma carga de 80.000 kg, para que o custo seja 
mínimo? 
Programação Linear – Primeira aula 
Pesquisa Operacional I Jhoab Negreiros 
13
Exercício 10. Numa indústria química há uma caldeira cuja margem de segurança é tal que a pressão 
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 
reação. Para que isto ocorra da forma desejada, a temperatura deve estar entre 80°C e 300°C, e a 
pressão entre 1 e 20 atmosferas. A que temperatura e pressão deve trabalhar a caldeira para que a 
reação se processe no menor tempo possível, se sabemos que a velocidade da reação é dada por 
2 30 20v T P   ?