Semana 1-2

1

Pesquisa Operacional

22

Apresentação

Everaldo de Barros

• Mestre em Engenharia Aeronáutica-Mecânica - ITA

• Mestre em Técnicas Aeronáuticas e Espaciais – SUPAERO/França

• Doutor em Engenharia Mecânica – UNESP

• Pesquisador DCTA

• Prof. Titular da Faculdade Anhanguera de Taubaté

3

Capítulos 1-2

Programação Linear

4

1. Programação linear

Pesquisa Operacional – aspectos históricos

O nome “Pesquisa Operacional” surgiu pela 1a vez durante a

Segunda Guerra Mundial.

Foi resultado de estudos realizados por equipes

interdisciplinares de cientistas contratados para resolver

problemas militares.

A técnica se consolidou em 1947, com a equipe liderada por

George B. Dantzig (Rand Corporation no projeto SCOOP-

Scientific Computation of Optimum Programs) trabalhando para

Força Aérea Americana desenvolvendo técnicas para a

distribuição ótima de tropas.

5


Pesquisa Operacional – definição

É um método científico que fornece instrumentos para a

tomada de decisões.

6


Aspectos históricos

O nome “Pesquisa Operacional” surgiu pela 1a vez durante a

Segunda Guerra Mundial.

Foi resultado de estudos realizados por equipes

interdisciplinares de cientistas contratados para resolver

problemas militares.

A técnica se consolidou em 1947, com a equipe liderada por

George B. Dantzig (RAND CORPORATION no projeto SCOOP-

Scientific Computation of Optimum Programs) trabalhando para

Força Aérea Americana (EUA) desenvolvendo técnicas para a

distribuição ótima de tropas

.

7


Modelos de programação matem ática

A escassez de certo produto ou matéria-prima ocorre pela

dificuldade de produção e/ou obtenção, entre outras razões.

Tal dificuldade exige que esses recursos escassos sejam

empregados de forma mais eficiente e eficaz.

Busca-se, portanto, maximizar ou minimizar uma

quantidade (lucro, custo, receita, número de produtos, entre

outros), chamada de fun ção objetivo , que depende de um

ou mais recursos escassos.

8

Modelos de programação matem ática

Em problemas reais de otimização, busca-se maximizar ou

minimizar uma quantidade específica, chamada objetivo, que

depende de um número finito de variáveis de entrada.

As variáveis de entrada podem ser:

• Independentes uma das outras.

• Relacionadas uma com as outras por meio de uma ou mais

restrições.


9

Áreas de aplicação da programação linear

• Administração da produção

• Análise de investimentos

• Alocação de recursos limitados

• Planejamento regional

• Logística

- Custo de transporte

- Localização de rede de distribuição

• Alocação de recursos em marketing entre diversos meios de comunicação.


10

Programação matem ática

Um problema de programação matemática é um problema

de otimização no qual o objetivo e as restrições são expressos

como funções matemáticas e relações funcionais.

≥=≤

=

nnn

n

n

n

b

b

b

xxxg

xxxg

xxxg

xxxfz

:

),...,,(

:

),...,,(

),...,,(

:a Sujeito

),...,,( :Otimizar

2

1

21

212

211

21


11

Programação matem ática

≥=≤

=

nnn

n

n

n

b

b

b

xxxg

xxxg

xxxg

xxxfz

:

),...,,(

:

),...,,(

),...,,(

:a Sujeito

),...,,( :Otimizar

2

1

21

212

211

21

xj - representa as quantidades das variáveis de decisão utilizadas (j = 1, 2,...,n)

bi - representa a quantidade disponível de determinado recurso (i = 1, 2,...,m)

f(x) - função-objetivo

g(x) - funções utilizadas nas restrições do problema (i = 1, 2,..., m)


12

Variáveis de decisão

• x1 , x2,...,xn , são as chamadas Variáveis de Decisão.

• As variáveis de decisão são aqueles valores que representam o

cerne do problema, e que podemos escolher (decidir) livremente.

• As variáveis de decisão representam as opções que um

administrador têm para atingir um objetivo. Ex.:

- Quanto produzir para maximizar o lucro?

- Quanto comprar de uma ação para minimizar o risco da carteira?


13

Problema de programação linear (PPL)

Um problema de programação matemática é linear se a

função-objetivo e cada uma das funções que representam as

restrições forem lineares, isto é, na forma abaixo:

nnn xcxcxcxxxf +++= ...),...,,( 221121

g x x x a x a x a xi n i i in n( , , . . . , ) . . .1 2 1 1 2 2= + + +

),...,,(21 n

xxxf


14

Problema de programação NÃO linear

A presença de qualquer das expressões abaixo tornam o

problema não linear:

( ) 1 para 1 ≠nx n

( ) a basequalquer para log 1xa

aa x devalor qualquer para 1


15

Programação linear

Exemplos:

0,

60020180

2042

s.r.

max

21

21

21

21

≥≤+

≤+

+

xx

xx

xx

xx

0,

60020180

2032

s.r.

2min

21

21

21

21

≥=+

≥+

+

xx

xx

xx

xx


16

PPL na forma padrão


0x,...x,x,x

bxa...xaxa

bxa...xaxa

bxa...xaxa

xc...xcxcZ

n321

mnmn22m11m

2nn2222121

1nn1212111

nn2211

≥≤+++

≤+++≤+++

+++= :a Sujeito

Maximizar

não negativos

17

PPL na forma padrão


0,

60020180

2032

s.r.

2min

21

21

21

21

≥=+

≥+

+

xx

xx

xx

xx

0,

60020180

2042

s.r.

max

21

21

21

21

≥≥≥≥≤≤≤≤+

≤≤≤≤+

+

xx

xx

xx

xx

0,

60020180

2042

s.r.

max

21

21

21

21

≥≥≥≥≤≤≤≤+

≤≤≤≤+

+

xx

xx

xx

xx

PPL na forma não padrão

18

Formulação do PPL

A formulação de qualquer problema a ser resolvido segue alguns passos

básicos:

• Quais as variáveis de decisão ?

• Qual o objetivo ? Aqui devemos identificar o objetivo da tomada de decisão, que deve ser

único. Por exemplo, maximização de lucro, minimização de tempo, custo. Tal

objetivo será representado por uma função objetivo.

• Quais as restrições ?Cada restrição imposta na descrição do sistema deve ser expressa como

uma relação linear (igualdade ou desigualdade), definidas com as variáveis de

decisão.


19

Exercícios

Exercícios. Apresente modelos de PL para as situações descritas.

≥=≤

=

nnn

n

n

n

b

b

b

xxxg

xxxg

xxxg

xxxfz

:

),...,,(

:

),...,,(

),...,,(

:a Sujeito

),...,,( :Otimizar

2

1

21

212

211

21

xj - variáveis de decisão

f(x) - função-objetivo

g(x) - restrições

20

Exercício 1. Um pintor faz quadros artesanais para vender numa feira que

acontece todo noite. Ele faz quadros grandes e desenhos pequenos, e os vende

por R$ 5,00 e R$ 3,00, respectivamente. Ele só consegue vender 3 quadros

grandes e 4 quadros pequenos por noite. O quadro grande é feito em 1 hora

(grosseiro) e o pequeno é feito em 1 hora e 48 minutos = 1,8 hora (detalhado).

O desenhista desenha 8 horas por dia antes de ir para a feira. Quantos quadros

de cada tipo ele deve pintar para maximizar a sua receita?.

Solução: uma forma de facilitar o processo de modelagem consiste em responder

às perguntas na seguinte sequência:

• O que decide ?

• Para que decide ?

• Com que restrições ?


21

Solução.

• Precisamos traduzir a decisão do pintor em um modelo de programação

linear para resolvê-lo.

• Variáveis de decisão: x1 e x2 as quantidades de quadros grandes e pequenos

que ele faz por dia, respectivamente.

• O objetivo do pintor é aumentar sua receita ao máximo.

• Restrições do problema:

- venda de quadros grandes e pequenos;

- tempo de pintura.


22

Modelo para a tomada de decisão:

• Variáveis de decisão x1 – no. quadros grandes

x2 – no. quadros pequenos

• Função-objetivo max Z = 5x1 + 3x2

• Restrição de venda de quadros grandes x1 ≤ 3

• Restrição de venda de desenhos x2 ≤ 4

• Restrição de tempo x1 + 1,8x2 ≤ 8 (1h48 min = 1,8h)

• Não negatividade x1, x2 ≥ 0


23

Exercício 2. Um alfaiate tem, disponíveis, os seguintes tecidos: 16 metros de

algodão, 11 metros de seda e 15 metros de lã.

Para um terno são necessários: 2 metros de algodão, 1 metro de seda e 1metro de lã.

Para um vestido, são necessários: 1 metro de algodão, 2 metros de seda e3 metros de lã.

Se um terno e vendido por $300,00 e um vestido por $500,00, quantas pecas decada tipo o alfaiate deve fazer, de modo a maximizar o seu lucro?

Solução:

• Variáveis de decisão

• Função objetivo

• Restrições


24

Solução.

• Variáveis de decisão: x1 e x2 as quantidades de ternos e vestidos que o alfaite

produz.

• O objetivo do alfaiate é maximizar o seu lucro.


- algodão;

- seda;

- lã.


25


• Variáveis de decisão x1 – no. ternos

x2 – no. vestidos

• Função-objetivo max Z = 300x1 + 500x2

• Restrição de algodão 2x1 +x2 ≤ 16

• Restrição de seda x1 + 2x2 ≤ 11

• Restrição de lã x1 + 3x2 ≤ 15



26

Exercício 3. Sabe-se que uma pessoa necessita em sua alimentação diária de

um mínimo de 15 unidades de proteínas e 20 unidades de carboidratos.

Supondo que, para satisfazer esta necessidade, ela disponha dos produtos soja

e feijão. Um kg do soja contém 3 unidades de proteínas, 10 unidades de

carboidratos custa R$ 2,00. Um kg de feijão contém 6 unidades de proteínas, 5

unidades de carboidratos e custa R$ 3,00. Que quantidade deve-se comprar de

cada produto de modo que as exigências de alimentação sejam satisfeitas a um

custo mínimo ?


27

Solução.

• Variáveis de decisão:

x1 - quantidade de soja

x2 - quantidade de feijão

• O objetivo é minimizar o custo da alimentação.


- proteínas;

- carboidratos .


28


• Variáveis de decisão x1 – quantidade de soja

x2 – quantidade de feijão

• Função-objetivo min Z = 2x1 + 3x2

• Restrição de qtide. proteínas (mínima) 3x1 + 6x2 ≥ 15

• Restrição de qtide. carboidratos 10x1 + 5x2 ≥ 20



29

Exercício 4. Uma companhia de aluguel de caminhões possuía-os de dois tipos:

• o tipo A com 2 m3 de espaço refrigerado e 4 m3 de espaço não refrigerado;

• o tipo B com 3 m3 refrigerados e 3 m3 não refrigerados.

Uma fábrica precisou transportar 90 m3 de produto refrigerado e 120 m3

de produto não refrigerado. Quantos caminhões de cada tipo ela deve alugar, de

modo a minimizar o custo, se o aluguel do caminhão A era R$ 0,30 por km e o do B,

R$ 0,40 por km. Elabore o modelo de programação linear.


30

Solução.

• Variáveis de decisão:

x1 – caminhão tipo A

x2 – caminhão tipo B

• O objetivo é minimizar o custo da alimentação.


- espaço refrigerado ;

- espaço não refrigerado.


31


• Variáveis de decisão x1 – caminhão tipo A

x2 – caminhão tipo B

• Função-objetivo min Z = 0,30x1 + 0,40x2

• Restrição do espaço refrigerado 2x1 + 3x2 ≤ 90

• Restrição do espaço não refrigerado 4x1 + 3x2 ≤ 120



32

Exercício 5 (PLT ex. 6 p. 26). A 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,

tendo contratos fechados de fornecimento para todos os 3 tipos diferentes de

lâminas de alumínio que fabrica: espessura fina, média ou grossa. Toda a produção

da companhia é realizada em duas fábricas, uma localizada em São Paulo e a outra

no Rio de Janeiro. Segundo os contratos fechados, a empresa precisa entregar

16 ton de lâminas finas, 6 ton de lâminas médias e 28 ton de lâminas grossas.

Devido à qualidade dos produtos da Alumilâminas S/A, há uma demanda extra para

cada tipo de lâmina.

• Fábrica de SP: custo de produção/dia de R$ 100.000,00 para uma capacidade

produtiva de 8 ton de lâminas finas, 1 ton de médias e 2 ton de lâminas grossas.

• Fábrica do RJ: custo de produção/dia R$ 200.000,00 para uma produção de 2 ton

de lâminas finas, 1 ton médias e 7 ton de lâminas grossas.

Quantos dias cada uma das fábricas deverá operar para atender os

pedidos ao menor custo possível ?


33

Exercício 6 (PLT ex. 7 p. 26). Um pizzaiolo trabalha 8 horas por dia e faz

16 pizzas por hora, caso faça somente pizzas, e 9 calzones por hora, se fizer

somente calzones. Ele gasta 40 g de queijo para preparar uma pizza e 60 g de

queijo para fazer um calzone.

Sabendo que o total disponível de queijo é de 5 kg por dia, e que a pizza é

vendida a R$ 18,00 e o calzone a R$ 22,00, pergunta-se:

Quantas unidades de pizzas e calzones uma pizzaria deve vender diariamente

para maximizar a sua receita, considerando que ela tem três pizzaiolos ?


34

Exercício 7 (PLT ex. 8 p. 26). A Esportes Radicais S/A produz pára-quedas e asa-

deltas em duas linhas de montagem. A primeira linha de montagem tem

100 horas semanais disponíveis para a fabricação dos produtos, e a segunda

linha tem um limite de 42 horas semanais.

Cada um dos produtos requer 10 horas de processamento na linha 1, enquanto

que na linha 2 o para-quedas requer 3 horas e a asa-delta requer 7 horas.

Sabendo que o mercado está disposto a comprar toda a produção da empresa,

bem como que o lucro pela venda de cada pára-quedas é de R$ 60,00 e o lucro

para cada asa-delta vendida é R$ 40,00, encontre a programação de produção

que maximize o lucro da Esportes Radicais S/A.


35

Exercício 7. (CORRAR, Luiz J. ex. 6 p. 333). A indústria Maximóveis fabrica dois tipos de produtos: cadeiras e mesas, que as seguintes margens de contribuição por unidade:


Produto Margem de contribuição/un. (R$)

Cadeiras 10

Mesas 8

Os produtos são processados por dois departamentos: montagem e acabamento. Ao passar por esses deptos., cada unidade do produto consome determinado no horas:

DepartamentoConsumo de horas pelos produtos

Cadeira Mesa

Montagem 3 3

Acabamento 6 8

Os deptos. apresentam limitação na capacidade produtiva:

Depto Capacidade máx (horas)

Montagem 30

Acabamento 48

Qual é a melhor combinação possível de cadeiras e mesas a serem produzidas para obter a maior margem de contribuição total ?

36

Curso de AdministraçãoPesquisa Operacional

Documents

Semana 1-2