Capítulo_1_-_Programação_Linea

Prévia do material em texto

Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
1
 
 
 
 
 
 
 
 
 
 
CAPÍTULO 1 
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. 
 
Desigualdades Lineares 
 
Desigualdades lineares é simplesmente uma equação linear, onde o sinal de igualdade é 
substituído por < (menor que), ≤ (menor ou igual a), > (maior que) e ≥ (maior ou igual a). 
 
Exemplo 1. Seja a desigualdade linear 2 8x y+ ≤ . 
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 semi-plano 
(“metade do plano”) satisfaz a desigualdade. 
 
Observação: Pela simplicidade dos cálculos, geralmente utilizamos a origem do plano para verificar 
a região satisfeita pela desigualdade. 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
2
 
 
Programação Linear 
 
A programação linear trata do problema específico de: maximizar ou minimizar uma função 
do tipo: ����, �
, ��, … , �
� � ���� � �
�
 � ���� �⋯� �
�
 � �, 
 
restrita a um subconjunto � poliedral convexo de �
 Na linguagem de programação linear PL, � é 
chamada função objetivo f.o. e � é denominada região factível. 
 
Definição 1 – 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 2. Observe a situação a seguir, onde há uma empresa que pretende otimizar a produção 
mensal de dois produtos A e B: 
 
 
 
 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
3
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. 
 
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 podem-se 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 ≥ . 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
4
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) 
 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
5
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+ = . 
 
 
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 = × + × = + = 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional IIJhoab Negreiros 
6
 
 
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. 
 
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). 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
7
 
 
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. 
 
Exemplo 3. Considere que um agricultor queira adubar a sua plantação e disponha de dois tipos de 
adubo. O primeiro contém 3 g de fósforo, 1 g de nitrogênio e 8 g de potássio, e custa $ 10 por 
quilograma. O segundo tipo contém 2 g de fósforo, 3 g de nitrogênio e 2 g de potássio, e custa $ 8 
por quilograma. Sabemos que um quilograma de adubo dá para 10 m² de terra, e que o solo em que 
estão suas plantações necessita de pelo menos 3 g de fósforo, 1,5 g de nitrogênio e 4 g de potássio 
a cada 10m². Quanto o agricultor deve comprar de cada adubo, para cada 10² de terra, de modo a 
conseguir ter o mínimo custo? 
Solução: 
 x primeiro adubo y segundo adubo Necessidades mínimas de adubo 
Fósforo 3 2 3 
Nitrogênio 1 3 1,5 
Potássio 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 restrição 0x ≥ e 0y ≥ ; 
� Segunda restrição 3 2 3x y+ ≥ ; 
� Terceira restrição 3 1,5x y+ ≥ ; 
� Quarta restrição 8 2 4x y+ ≥ . 
Colocando num gráfico as quantidades � (como abscissa) e � (como ordenada) temos: 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
8
 
 
 
 
 
 
 
 
 
 
2 Atividades 
 
Exercício 1. Faça o gráfico dos seguintes sistemas de desigualdades simultâneas: 
(a) 
2 4
1
4
x y
x y
y
− ≤

+ ≥ −
 ≤
 
(b) 
4 3 12
2 2
3 3
x y
x y
y x
+ ≤

− ≤

− ≤
 
 
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
5
3
x
y
x
y
≥
 ≥
 ≤
 ≤
 
(b) 
0
0
25
2 2 10
x
y
x y
x y
≥
 ≥

+ ≤
 + ≥
 
 
Exercício 3. Determine o máximo da função expressa por 2 ,x y+ sujeita às restrições 0x ≥ , 
0y ≥ , 3x y+ ≤ e 4 0x y+ ≤ : 
 
Exercício 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 
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 vendam todos, obtenha o lucro máximo? 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
9
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 máquina produz dois tipos A e B de frascos de vidro, mas não 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 máquina pode trabalhar no máximo 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 máximo? 
 
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= + + ? 
 
 
Capítulo 1 Programação Linear e PLI 
Pesquisa Operacional II Jhoab Negreiros 
10
3 Programação Linear Inteira 
 
Programação linear inteira (PLI) são programações lineares nas quais algumas ou todas as 
variáveis estão restritas a valores inteiros. 
De maneira geral, o problema passívelde solução por programação inteira deve apresentar 
as seguintes características: 
 
i. Função objetivo linear; 
ii. Restrições lineares; 
iii. Variáveis positivas; 
iv. Algumas ou todas variáveis inteiras. 
 
Exemplo 4. Maximizar o problema de programação linear inteira. 
Função objetivo: � � 5�� � 4�
 
Restrições:" �� � �
 ≤ 5,510�� � 6�
 ≤ 45,2��, �
	'�()'*�+	�ã-	�).�('/�+ 
 
 
 
 
 
4 Atividades 
 
Exercício 11. Uma máquina é usada para produzir produtos intercambiáveis. A máquina é capaz de 
fazer no máximo 20 unidades do produto 1 e 10 unidades do produto 2. Alternativamente, a 
máquina pode ser ajustada para produzir no máximo 12 unidades do produto 1 e 25 unidades do 
produto 2 por dia. A análise de mercado mostra que a máxima demanda diária dos dois produtos 
combinados é 35 unidades. Dado que os lucros unitários para os dois produtos respectivos são R$ 
10 e R$ 12, qual dos dois ajustes da máquina deve ser selecionado? Formule a questão como um 
problema de PLI e ache a solução ótima. 
 
Exercício 12. Uma fábrica produz três produtos. Os requisitos de mão-de-obra e matéria-prima para 
os três produtos são dados na tabela a seguir. 
Produto 
Mão-de-obra requerida Matéria-prima requerida 
por dia (hora/unidade) por dia (Kg/unidades) 
1 3 4 
2 4 3 
3 5 6 
Disponibilidade diária 100 100 
 
Os lucros por unidade para os três produtos são R$ 25, R$ 30 e R$ 45, respectivamente. Se a 
fábrica quiser mesmo fabricar o produto 3, seu nível de produção deve ser no mínimo de cinco 
unidades diárias. Formule a questão como um problema de PLI mista e ache o mix ótimo.