Programação Linear - 1

Faculdade de Engenharia - Campus de Guaratinguetá
Pesquisa Operacional
Livro: Introdução à Pesquisa Operacional

Capítulo 2 - Programação Linear
Fernando Marins – [email protected]

1
Sumário
• Modelagem e limitações da Programação Linear.
• Resolução Gráfica.
2
Pesquisa Operacional - UNESP / Campus de Guaratinguetá
Programação Linear
Programação Linear:
Preocupação em encontrar a melhor solução para problemas
associados com modelos lineares.
Atribuir recursos limitados a actividades concorrentes da melhor
forma possível ( de forma ótima).
Modelo de Programação Linear:

Maximização (ou minimização) de uma função objetivo linear com
relação as variáveis de decisão do modelo.
Respeitando-se as limitações (restrições) do problema expressas por
um sistema de equações e inequações associadas com as variáveis de
decisão do modelo.
3
Modelagem em Programação Linear
Razões para o uso da Programação Linear:
1. Grande variedade de situações podem ser aproximadas por

modelos lineares.
2. Existência de técnicas (algoritmos) eficientes para a solução

de modelos lineares.
3. Possibilidade de realização de análise de sensibilidade nos

dados do modelo.
4. Estágio de desenvolvimento da tecnologia computacional.

4
Passos básicos na obtenção de modelos de PL:
1. Identificar as variáveis de decisão, representá-las em simbologia

algébrica.
2. Identificar as restrições do problema, expressá-las como

equações ou inequações lineares em termos das variáveis de
decisão.
3. Identificar o objetivo de interesse no problema, representá-lo

como função linear em termos das variáveis de decisão, que
deverá ser maximizada ou minimizada.
5
Seleção de mídia para propaganda
Uma companhia de propaganda deseja planejar uma campanha em 03

diferentes meios: TV, rádio e revistas. Pretende-se alcançar o maior
número de clientes possível. Um estudo de mercado resultou em:
TV TV Rádio Revistas
horário horário
normal nobre
Custo 40.000 75.000 30.000 15.000

Clientes 400.000 900.000 500.000 200.000
Atingidos
Mulheres 300.000 400.000 200.000 100.000
Atingidas
0bs: valores válidos para cada veiculação da propaganda. 6

A companhia não quer gastar mais de $ 800.000 e, adicionalmente,

deseja:
(1) Que no mínimo 2 milhões de mulheres sejam atingidas;
(2) Gastar no máximo $ 500.000 com TV;
(3) Que no mínimo 03 veiculações ocorram no horário normal TV;
(4) Que no mínimo 02 veiculações ocorram no horário nobre TV;
(5) Que o nº. de veiculações no rádio e revistas fiquem entre 05 e 10, para
cada meio de divulgação.
Formular um modelo de PL que trate este problema,

determinando o nº. de veiculações a serem feitas em cada meio de
comunicação, de modo a atingir o máximo possível de clientes.
7
Resolução do exemplo “seleção de mídia para propaganda”
Variáveis de decisão:
X1 = nº. de exposições em horário normal na tv.
X2 = nº. de exposições em horário nobre na tv.
X3 = nº. de exposições feitas utilizando rádio
X4 = nº. de exposições feitas utilizando revistas.
Função-objetivo:
“Maximizar nº. de clientes atingidos”
Max Z = 400.000X1 + 900.000X2 + 500.000X3 + 200.000X4
8
Restrições:
Orçamento:
40.000X1 + 75.000X2 + 30.000X3 + 15.000X4  800.000
Mulheres atingidas:
300.000X1 + 400.000X2 + 200.000X3 + 100.000X4  2.000.000
Gasto com TV
40.000X1 + 75.000X2  500.000
Nº. de veiculações em TV, rádio e revistas
X1  3, X2  2, 5  X3  10, 5  X4  10
Não-negatividade
X1, X2, X3, X4  0.
9
Resolução gráfica de modelos de PL
Aplicável para modelos com 02 variáveis de decisão
Útil para a ilustração de alguns conceitos básicos utilizados na
resolução de modelos de maior porte.
Etapas a serem seguidas na resolução gráfica
1º Passo: identificar a região viável do modelo, isto é, quais são os

pares (X1, X2) que satisfazem a todas as restrições.
2º Passo: achar a melhor solução viável, denominada Solução

Ótima e denotada por (X1*, X2*), que leva ao valor ótimo da
função-objetivo Z*.
10
Problema de mix de Produção
Fabricação de dois modelos de computadores: T ( Toshiba) e H ( hp).
• Lucros unitários/dúzia: $8 para T e $5 para H

• Recursos disponíveis:
1000 kg de material para fabricação;
40 horas para produção semanal.
• Requisitos do Departamento de Marketing:

Produção total não pode exceder 700 dúzias;
A quantidade de dúzias de T não pode exceder em 350 a
quantidade de dúzias de H.
• Dados técnicos:
T requer 2 kg de material e 3 minutos por dúzia.
H requer 1 kg de material e 4 minutos por dúzia.
11
A Gerência está procurando um

programa de produção que aumente
o lucro da Companhia.
12
Variáveis de decisão:
X1: produção semanal de T (em dúzias).

X2: produção semanal de H (em dúzias).
Função Objetivo: Maximizar o Lucro semanal
13
Max 8X1 + 5X2 (Lucro semanal)
sujeito a:
2X1 + 1X2 ≤ 1000 (Material de fabrico - Kg)
3X1 + 4X2 ≤ 2400 (Tempo de produção - minutos)
X1 + X2 ≤ 700 (Produção total)
X1 - X2 ≤ 350 (mix)
Xj  0, j = 1,2 (Não negatividade)
14
Conceitos importantes:
Os pontos (X1, X2) que satisfazem todas as restrições do
modelo formam a Região Viável.
Esses pontos são chamados de Soluções Viáveis.
Usando a resolução gráfica pode-se representar todos as

restrições (semi-planos), a função objetivo (reta) e os três
tipos de pontos viáveis.
15
1º Passo:
Traçar eixos cartesianos, associando a cada um deles uma

variável de decisão.
No exemplo de fabricação de brinquedos: X1 para o eixo

das abscissas e X2 para o eixo das ordenadas.
As restrições de não-negatividade, X1  0 e X2  0,
implicam que os pares (X1, X2) viáveis estão no 1º quadrante
dos eixos considerados.
16
2º Passo:
Observar que a função-objetivo, ao se fixar um valor para Z,

representa uma reta. Alterações neste valor de Z gera uma família de
retas paralelas.
No exemplo dos brinquedos: considere a reta obtida fazendo

Z= 2000, isto é , a reta dada por 8X1 + 5X2 = 2000. Percebe-se que ao se
traçar retas paralelas no sentido de ficar mais afastado da origem (0, 0), o
valor de Z aumenta.
De fato pode-se verificar que a reta paralela, que contém algum

ponto da região viável, no caso o ponto ótimo X* = (320, 360), e está
mais afastada da origem, corresponde a um valor ótimo da função
objetivo Z* = 4360. 17
Representando as condições de não negatividade
X2
X1
18
Observar que no exemplo dos brinquedos, as restrições correspondem a
semi-planos associados, respectivamente, às retas suportes dadas por:
2X1 + 1X2 = 1000

3X1 + 4X2 = 2400
X1 + X2 = 700
X1 - X2 = 350
Xj  0, j = 1,2
Notar que cada reta suporte define dois semi-planos no espaço (X1, X2).
Para identificar qual destes semi-planos é de interesse no caso, ou seja,
contém os pontos que satisfazem a desigualdade da restrição, basta testar
algum ponto à esquerda ou à direita (acima ou abaixo) da reta suporte da
desigualdade.
Um ponto que torna isto fácil é a origem (0, 0), mas poderia ser qualquer
19
outro.
X2
1000 Restrição do plástico

2X1+X2  1000
700 Restrição da produção total
X1+X2  700
500
Inviável
Tempo de Viável
produção
3X1+4X2  2400 X1
500 700
20
X2
1000 Restrição do plástico
2X1+X2 1000
700 Restrição da produção total:
X1+X2 700 (redundante)
500
Inviável
Restrição do mix da produção:
X1-X2  350
Tempo de Viável
Produção
3X1+4X2  2400
X1
21
X2
1000
700
500
Inviável
Viável
X1
500 700
Pontos interiores. Pontos na fronteira. Pontos extremos.
Há três tipos de pontos viáveis. 22
A busca por uma Solução Ótima:

X2 Começar com algum valor de lucro arbitrário,
1000 Por exemplo $2000...
Depois aumentar o lucro, se possível...
...e continuar até que seja inviável
700
X* = (320, 360)
600 com Z* = 4.360
X1
23
500
Pontos extremos e Soluções Ótimas

Se o problema de Programação Linear tem uma Solução
Ótima, um ponto extremo é Solução Ótima.
24
Visualização de situações possíveis
X2 X2
Z
Z*
Solução X1 X1
Solução
única ilimitada
25
Soluções Ótimas Múltiplas

Quando a função objetivo é paralela a alguma restrição.
Todos os pontos do segmento de

reta serão Soluções Ótimas.
X*1 X* = X*1 + (1 - )X*2, com 0    1
X*2
26
X2
X2
Z*
X*
X*
X1 Z* X1
Múltiplas Soluções
Múltiplas
Ótimas 1 –
Soluções Ótimas 2
Segmento de Reta
Semi-reta Ótima
Ótimo
27
X2
O conjunto
viável é vazio. Problema
Há restrições inviável
incompatíveis.
X1
28
Comentários Gerais
Linhas de Pesquisa
• Algoritmos de pontos interiores e suas derivações.

• Implementações de algoritmos para processamento em paralelo.
• Linguagens de modelagem: ajudar no desenvolvimento e aplicação de
modelos de Pesquisa Operacional.
Exemplos:
• AMPL - Modeling Language for Mathematical Programming - R. Fourer,
D. M. Gay, and B. W. Kerningham, 1993.
• GAMS - General Algebraic Modeling System - J. Bisschop and A.

Meeraus, 1982.
• What’s best - The ABC of Optimization - S. L. Savage, 1992.

29

Programação Linear - 1

Enviado por

Direitos autorais:

Formatos disponíveis

Programação Linear - 1

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Programação Linear - 1

Enviado por

Direitos autorais:

Formatos disponíveis

Faculdade de Engenharia - Campus de Guaratinguetá

Livro: Introdução à Pesquisa Operacional

Fernando Marins – [email protected]

• Modelagem e limitações da Programação Linear.

Modelo de Programação Linear:

Razões para o uso da Programação Linear:

1. Grande variedade de situações podem ser aproximadas por

2. Existência de técnicas (algoritmos) eficientes para a solução

3. Possibilidade de realização de análise de sensibilidade nos

4. Estágio de desenvolvimento da tecnologia computacional.

Passos básicos na obtenção de modelos de PL:

1. Identificar as variáveis de decisão, representá-las em simbologia

2. Identificar as restrições do problema, expressá-las como

3. Identificar o objetivo de interesse no problema, representá-lo

Uma companhia de propaganda deseja planejar uma campanha em 03

Custo 40.000 75.000 30.000 15.000

0bs: valores válidos para cada veiculação da propaganda. 6

A companhia não quer gastar mais de $ 800.000 e, adicionalmente,

Formular um modelo de PL que trate este problema,

Etapas a serem seguidas na resolução gráfica

1º Passo: identificar a região viável do modelo, isto é, quais são os

2º Passo: achar a melhor solução viável, denominada Solução

• Lucros unitários/dúzia: $8 para T e $5 para H

• Requisitos do Departamento de Marketing:

A Gerência está procurando um

X1: produção semanal de T (em dúzias).

Função Objetivo: Maximizar o Lucro semanal

Max 8X1 + 5X2 (Lucro semanal)

Usando a resolução gráfica pode-se representar todos as

Traçar eixos cartesianos, associando a cada um deles uma

No exemplo de fabricação de brinquedos: X1 para o eixo

Observar que a função-objetivo, ao se fixar um valor para Z,

No exemplo dos brinquedos: considere a reta obtida fazendo

De fato pode-se verificar que a reta paralela, que contém algum

Representando as condições de não negatividade

2X1 + 1X2 = 1000

1000 Restrição do plástico

A busca por uma Solução Ótima:

Pontos extremos e Soluções Ótimas

Visualização de situações possíveis

Soluções Ótimas Múltiplas

Todos os pontos do segmento de

• Algoritmos de pontos interiores e suas derivações.

• GAMS - General Algebraic Modeling System - J. Bisschop and A.

• What’s best - The ABC of Optimization - S. L. Savage, 1992.

Você também pode gostar