Programação Linear (PL)

Prof. Paulo Cesar F. De Oliveira, BSc, PhD

07/08/15 © P C F de Oliveira 2014 1

Características

07/08/15 © P C F de Oliveira 2014 2

Trata com alocação de recursos a atividades

em competição, da melhor maneira

possível (i.e., ótima).

Técnica de solução programável em computador facilitam sua aplicação.

Técnicas mais utilizadas na abordagem de problemas em PO

Requer que todas as funções neste modelo sejam lineares. Esta característica de linearidade é interessante no que se refere à simplificação da estrutura matemática envolvida.

Resolvendo Problemas

07/08/15 © P C F de Oliveira 2014 3

Variáveis de Decisão

RestriçõesFunção Objetivo

Aquilo que se pode controlar e que deseja saber exatamente quanto vale

Limitam as combinações das variáveis a determinados limites

Quando se quer (maximizar ou minimizar) um determinado objetivo. Éexpressa em função das variáveis do problema

Exemplos

07/08/15 © P C F de Oliveira 2014 4

Exemplo 1: Certa empresa fabrica dois produtos P1 e P2. O Lucro unitário do produto P1 é de 1.000 unidadesmonetárias e o lucro unitário do produto P2 é de 1.800 unidades monetárias. A empresa precisade 20 horas para fabricar uma unidade de P1 e 30 horas para fabricar uma unidade de P2. Otempo anual de produção disponível para isso é de 1.200 horas. A demanda esperada para cadaproduto é de 40 unidades anuais para P1 e 30 unidades anuais para P2. Qual é o plano deprodução para que a empresa maximize seu lucro anual nesses itens?

Solução:

I – Construção do modelo de programação linear:

a) Quais as variáveis de decisão: aqui o trabalho consiste em explicitar as decisões que devem ser tomadas e representar as possíveis decisões. Neste caso, o que deve ser decidido é o plano de produção, i. é, quais as quantidades anuais que devem ser produzidas de P1 e P2.

Portanto, as variáveis de decisão serão x1 e x2

x1 = quantidade anual a produzir de P1

x2 = quantidade anual a produzir de P2

Exemplos

07/08/15 © P C F de Oliveira 2014 5

b) Qual o objetivo: aqui deve-se identificar o objetivo da tomada de decisão. Eles geralmenteaparecem na forma de maximização de lucros ou receitas ou minimização de custos, perdas, etc.É a expressão (função) que calcula o valor do objetivo em função das variáveis de decisão. Nesteproblema o objetivo é maximizar o lucro, que pode ser calculado:Lucro devido a P1: 1000.x1 (lucro por unidade de P1 x a quantidade produzida de P1)

Lucro devido a P2: 1800.x2 (lucro por unidade de P2 x a quantidade produzida de P2)Lucro total: L = 1000.x1 + 1800.x2

Logo, o objetivo é: Maximizar L= 1000.x1 + 1800.x2

c) Quais as restrições: Cada restrição imposta na descrição do sistema deve ser expressa comouma relação linear (igualdade ou desigualdade), montadas com as variáveis de decisão. Noexemplo 1 as restrições impostas pelo sistema são:- Disponibilidade (anual) de horas para a produção: 1200 h.

horas necessárias para P1: 20.x1 (necessidade unitária x quantidade produzida)horas necessárias para P2: 30.x2 (necessidade unitária x quantidade produzida)

Total de horas necessárias para produção: 20.x1+ 30.x2

Restrição de disponibilidade de horas: 20.x1 + 30.x2 ≤ 1200

Exemplos

07/08/15 © P C F de Oliveira 2014 6

- Demanda (anual) de mercado para os produtos P1 e P2Demanda por P1: 40 unidadesQuantidade a produzir de P1: x1unidades

Restrição de demanda por P1: x1 ≤ 40Demanda por P2: 30 unidadesQuantidade a produzir de P2: x2unidades

Restrição de demanda por P2: x2 ≤ 30Observação: x1 e x2 não podem assumir valores negativos, pois não há nenhumsentido nisto. Por esta razão colocam-se mais duas restrições denominadasrestrições de não negatividade.x1 ≥ 0 e x2 ≥ 0

d) Resumo do modelo:

Maximizar: L= 1000.x1 + 1800.x2

20.x1 + 30.x2 ≤ 1200

P1: x1 ≤ 40

P2: x2 ≤ 30x1 ≥ 0 e x2 ≥ 0

Sujeito a:

07/08/15 7

ExemplosII – Método gráfico para modelos de PL com duas variáveis de decisão:Esta técnica consiste em representar num sistema de eixos ortogonais o conjunto daspossíveis soluções do problema, i. é, o conjunto de pares (x1,x2) que obedecem ao grupode restrições impostas pelo sistema em estudo. O desempenho do modelo é avaliadoatravés da representação gráfica da função objetivo.

A representação gráfica de uma equação linear com duas variáveis é uma reta. Já arepresentação gráfica de uma inequação linear com duas variáveis é um dos semiplanosdefinidos pela reta correspondente à equação e o sinal da desigualdade.

Representação gráfica das restrições:

20.x1 + 30.x2 ≤ 1200

O conjunto de pontos do plano que satisfazem a esta restrição é o conjunto dos pontos

da reta 20.x1 + 30.x2 = 1200 unido com o conjunto de pontos da correspondente

desigualdade ≤ , que corresponde a um dos 2 semiplanos abertos divididos pela reta.

Para traçar a reta precisaremos de dois pontos (ver figura 1):

fazendo-se x1 = 0 teremos: 30.x2 = 1200 ⇒ x2 = 40

fazendo-se x2 = 0 teremos: 20.x1 = 1200 ⇒ x1 = 60

07/08/15 © P C F de Oliveira 2015 8

Exemplos

O conjunto de pontos do plano que satisfazem a esta restrição é o conjunto dos pontos dareta x1 = 40 unido com o conjunto de pontos da correspondente desigualdade, ⩽ , quecorresponde a um dos 2 semiplanos abertos divididos pela reta. Esta reta é perpendicular aoeixo x1 passando por 40 (ver figura 1).

x1 ≤ 40

x2 ≤ 30

x1 ≥ 0 e x2 ≥ 0

O conjunto de pontos do plano que satisfazem a esta restrição é o conjunto dos pontos dareta x2 = 30 unido com o conjunto de pontos da correspondente desigualdade ≤ ⩽ , quecorresponde a um dos 2 semiplanos abertos divididos pela reta. Esta reta é perpendicular aoeixo x2 passando por 30 (ver figura 1).

O conjunto de pontos do plano que satisfazem a estas restrições é o conjunto de todos ospontos que formam o primeiro quadrante do plano cartesiano x1 X x2.

07/08/15 © P C F de Oliveira 2007 9

ExemplosComo deve ser considerado o sistema de restrições simultâneas, o conjunto das soluções compatíveisao problema de PL, resulta da intersecção destes semiplanos fechados, o que constitui um polígonoconvexo fechado.

Qualquer ponto deste polígono corresponde a uma solução compatível, i. é, atende a todas restrições.Há infinitos pontos nesse conjunto. Porém, o valor da função objetivo muda de acordo com o ponto.Procura-se, então, aquele ponto ( ou aqueles pontos, se mais de um) que maximiza(m) o valor dafunção objetivo.

x2

x1

20.x1 +    30.x2 ≤ 1200

x1   ≤ 40x2   ≤ 30

45000   =  1000.x1+1800.x2

Ponto  Ótimo

30

40

25

6040

45

Conjunto  de  soluções  compatíveis  ao  problema

Figura  1

07/08/15 © P C F de Oliveira 2007 10

Exemplos

Para determinar o “ponto ótimo” considere a função objetivo L= 1000.x1 + 1800.x2 ela também é umafunção linear, ou seja, sua representação gráfica é uma reta. O coeficiente angular da reta determina suainclinação. Por esta razão, atribuindo-­se valores ao lucro pode-­se determinar uma família de retasparalelas, uma reta para cada valor de L.

Deve-­se, assim, tomar desta família de retas paralelas aquela com maior valor de L, porém esta reta deverápossuir ao menos um ponto do conjunto de soluções compatíveis. Esta determinação pode ser feitagraficamente através do uso de uma régua e um esquadro. Ao deslocar-­se o esquadro sobre a régua,consegue-­se abranger todas as retas da família. O movimento do esquadro deverá ser feito no sentido decrescimento da função, uma vez que o objetivo deste problema é maximizar o lucro.Para encontrar o valor exato do par ordenado (x1,x2) solução do problema, basta resolver o sistema deequações formado pelas retas que definem o vértice do polígono onde se encontra o ponto ótimo.

x2 =  3020.x1 +    30.x2 =  1200  

X1 =15

X2 =  30

12 18001000

1800xLx −=

07/08/15 © P C F de Oliveira 2007 11

ExemplosExemplo 2:

Uma empresa química opera uma pequena usina. Operar a usina exige a utilização deduas matérias-primas, A e B. O fornecimento máximo disponível por semana é de 2.700litros de A e 2.000 litros de B. A usina pode operar usando um dos dois processos, quepossuem diferentes exigências de matéria-prima, conforme tabela abaixo.

A Usina pode funcionar por um total de 120 horas por semana mas, por motivo desegurança, o Processo 1 não pode ser operado por mais de 100 horas por semana. Sabe-se ainda que a contribuição dos Processos 1 e 2 para o lucro são respectivamente R$ 50,00e R$ 60,00 por hora.Determine através de um programa linear, quantas horas cada processo da usina devefuncionar para que se tenha lucro máximo.

I - Resolver pelo processo gráfico:II - Resolver pela utilização de software (Solver/Excel):

Matérias-primas consumidas (litros/hora)Processo

A B1 20 102 30 25

07/08/15 © P C F de Oliveira 2007 12

Exemplos

a) Quais as variáveis de decisão:x1 = no. de horas que o Processo 1 deve funcionarx2 = no. de horas que o Processo 1 deve funcionar

b) Função Objetivo: Maximizar L = 50.x1 + 60.x2

c) Restrições:20.X1  +  30.X2  =  270010.X1  +  25.X2  =  2000X1  +  X2  =  120X1  =  100X1=  0  e    X2  =  0

I – Resolução pelo método gráfico:

07/08/15 © P C F de Oliveira 2007 13

O Problema do Pintor

Um Pintor faz quadros artesanais para vender numafeira que acontece todo dia à noite. Ele faz quadrosgrandes e desenhos pequenos, e os vende por R$5,00 eR$3,00, respectivamente. Ele só consegue vender 3quadros grandes e 4 quadros pequenos por noite. Oquadro grande é feito em uma hora (grosseiro) e opequeno é feito em 1 hora e 48 minutos (detalhado). Odesenhista desenha 8 horas por dia antes de ir para afeira. Quantos quadros de cada tipo ele deve pintarpara maximizar a sua receita?

Exemplos

07/08/15 © P C F de Oliveira 2007 14

O Problema do Pintor

§ A Decisão do Pintor

§ O que o desenhista precisa decidir?

§ O que ele pode fazer para aumentar oudiminuir a sua receita?

§ A decisão dele é como usar as 8 horas diárias.

§ Quantos desenhos pequenos e grandes ele deve fazer.

Exemplos

07/08/15 © P C F de Oliveira 2007 15

O Problema do Pintor

§ Precisamos traduzir a decisão do Pintor emum modelo de programação linear pararesolvê-lo;

§ Chamemos de x1 e x2 as quantidades dequadros grandes e pequenos que ele faz pordia, respectivamente.

§ O Objetivo do Pintor é aumentar sua receitaao máximo.

Exemplos

07/08/15 © P C F de Oliveira 2007 16

Modelo para decisão do pintor

Max Z x x= +5 31 2§ Função-objetivo

§ Maximizar a receita

1x ≤ 3§ Restrição de vendas de quadros grandes

x ≤ 42§ Restrição de vendas de quadros pequenos

x x+ ≤1,8 81 2§ Restrição de tempo

x ≥ 01 , x ≥ 02§ Não negatividade

Exemplos

07/08/15 © P C F de Oliveira 2007 17

Modelo para decisão do pintor

970

135

2

21370

135

2

21

35

350

+−=

+==

−=

+==

xx

xxz

xx

xxz

c

c(3 ; 50/18)

Exemplos

07/08/15 © P C F de Oliveira 2007 18

Caso AluminâminasA Indústria Alumilâminas S/A iniciou suas operações em janeiro de 2001 e jávem conquistando espaço no mercado de laminados brasileiro, tendocontratos fechados de fornecimento para todos os 3 tipos diferentes delâminas de alumínio que fabrica: espessura fina, média ou grossa. Toda aprodução da companhia é realizada em duas fábricas, uma localizada em SãoPaulo e a outra no Rio de Janeiro. Segundo os contratos fechados, a empresaprecisa entregar 16 toneladas de lâminas finas, 6 toneladas de lâminasmédias e 28 toneladas de lâminas grossas. Devido à qualidade dos produtosda Alumilâminas S/A, há uma demanda extra para cada tipo de lâmina. Afábrica de São Paulo tem um custo de produção de R$ 100.000,00para uma capacidade produtiva de 8 toneladas de lâminas finas, 1 toneladade lâminas médias e 2 toneladas de lâminas grossas por dia. O custo deprodução diário da fábrica do Rio de Janeiro é de R$ 200.000,00 parauma produção de 2 toneladas de lâminas finas, 1 tonelada de lâminasmédias e 7 toneladas de lâminas grossas. Quantos dias cada uma dasfábricas deverá operar para atender os pedidos ao menor custo possível?(resolva pela análise gráfica – deslocamento da função objetivo).

Exemplos

07/08/15 © P C F de Oliveira 2007 19

Caso Aluminâminas§ Variáveis de Decisão

§ x1 – Quantos dias de funcionamento da Fábrica de SP§ x2 – Quantos dias de funcionamento da Fábrica do RJ

§ Função-Objetivo

§ Minimizar Custo de Produção (mil R$) = 100x1+ 200x2

Exemplos

07/08/15 © P C F de Oliveira 2007 20

Caso Aluminâminas

§ Restrições de Demanda

§ Placas Finas 8x1+2x2 ≥16

§ Placas Médias x1+x2 ≥ 6

§ Placas Grossas 2x1+7x2 ≥ 28

§ Restrições de Não Negatividade x1,x2 ≥ 0

Exemplos

07/08/15 © P C F de Oliveira 2007 21

Caso Aluminâminas§ Solução Gráfica

Z = 920x1 = 14/5 e x2 = 16/5

Exemplos

07/08/15 © P C F de Oliveira 2007 22

Caso Esportes RadicaisA Esportes Radicais S/A produz pára-quedas e asa-deltas emduas linhas de montagem. A primeira linha de montagem tem100 horas semanais disponíveis para a fabricação dos produtos,e a segunda linha tem um limite de 42 horas semanais. Cada umdos produtos requer 10 horas de processamento na linha 1,enquanto que na linha 2 o pára-quedas requer 3 horas e a asa-delta requer 7 horas. Sabendo que o mercado está disposto acomprar toda a produção da empresa, bem como que o lucropela venda de cada pára-quedas é de R$ 60,00 e o lucro paracada asa-delta vendida é R$ 40,00, encontre a programação deprodução que maximize o lucro da Esportes Radicais S/A.(resolva pela análise gráfica – deslocamento da função objetivo).

Exemplos

07/08/15 © P C F de Oliveira 2007 23

Caso Esportes Radicais

§ Variáveis de Decisão

§ x1 – Quantidade de Pára-Quedas a serem

produzidos

§ x2 – Quantidade de Asa Deltas a serem

produzidas

§ Função-Objetiva

§ Max 60x1 + 40x2

Exemplos

07/08/15 © P C F de Oliveira 2007 24

Caso Esportes Radicais

§ Restrição de Produção

§ Linha 1

§ Linha 2

§ Restrição de Não Negatividade

1001010 21 ≤+ xx

4273 21 ≤+ xx

0, 21 ≤xx

Exemplos

07/08/15 © P C F de Oliveira 2007 25

Caso Esportes Radicais

§ O Modelo

0,4273

10010104006

21

21

21

21

≥

≤+

≤+

+

xxxxxx

xxMax

Exemplos

07/08/15 © P C F de Oliveira 2007 26

Caso Esportes Radicais

§ Solução Gráfica

Z = 600x1 = 10 , x2 = 0

Exemplos