Modulo 2 - Programação Linear - Método Gráfico

Prévia do material em texto

Módulo 2 
Programação Linear
Método Gráfico
7
Prof. Ms. Antonio dos Santos
Problemas de Otimização
� 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.
8
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.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
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
9
relações funcionais







≥
=
≤







=
nnn
n
n
n
b
b
b
xxxg
xxxg
xxxg
xxxfz
:
),...,,(
:
),...,,(
),...,,(
 :a Sujeito
),...,,( :Otimizar
2
1
21
212
211
21
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
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 a resposta do problema, e que podemos
escolher (decidir) livremente.
10
escolher (decidir) livremente.
� As variáveis de decisão representam as opções que um
administrador têm para atingir um objetivo.
� Quanto produzir para maximizar o lucro?
� Quanto comprar de uma ação para minimizar o risco
da carteira?
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
� 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:
),...,,( 21 nxxxf
11
isto é, na forma abaixo:
e
nnn xcxcxcxxxf +++= ...),...,,( 221121
g x x x a x a x a xi n i i in n( , , . . . , ) . . .1 2 1 1 2 2= + + +
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Presença da Não Linearidade
� A presença de qualquer das expressões abaixo tornam o 
problema não linear.
� Exemplos:
12
�
�
�
( ) 1 para 1 ≠nx n
( ) a basequalquer para log 1xa
aa
x
 devalor qualquer para 1
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Exemplos
..
 Max Z 21=
as
x+x
..
2x Min Z 21=
as
+x
13
0
60020180
204x2x
21
21
21
≥
≤
≤
x,x
x+x
+
0
60020180
203x2x
21
21
21
≥
≥
x,x
=x+x
+
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Hipótese de Aditividade
� Considera as atividades (variáveis de decisão) do
modelo como entidades totalmente independentes, não
permitindo que haja interdependência entre as
mesmas, isto é, não permitindo a existência de termos
14
mesmas, isto é, não permitindo a existência de termos
cruzados, tanto na função-objetivo como nas restrições.
� Esta é a própria hipótese de linearidade do
problema de Programação Linear (PL)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Hipótese de Proporcionalidade
� O valor da função-objetivo é proporcional ao nível de
atividade de cada variável de decisão, isto é, o valor da
função objetivo se altera de um valor constante dada
uma variação constante da variável de decisão;
15
uma variação constante da variável de decisão;
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Hipótese de Divisibilidade
� Assume que todas as unidades de atividade possam ser
divididas em qualquer nível fracional, isto é, qualquer
variável de decisão pode assumir qualquer valor
fracionário, ou seja as variáveis são contínuas.
16
fracionário, ou seja as variáveis são contínuas.
� Esta hipótese pode ser quebrada, dando origem a um
problema especial de programação linear, chamado de
programação inteira.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Terminologia
� Solução
� No campo de Programação Linear é qualquer
especificação de valores para as variáveis de decisão,
não importando se esta especificação se trata de uma
17
não importando se esta especificação se trata de uma
escolha desejável ou permissível.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
A Solução Ótima
� A Solução Ótima é uma solução viável especial.
� Dentre todas as soluções viáveis, aquela(s) que
18
produzir(em) o valor da função objetivo otimizado é
chamada de ótima;
� A grande questão é como determinar a solução ótima.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Solução Gráfica
Exemplo:
Um fazendeiro deseja otimizar sua plantação de arroz e
milho. Ele quer saber as áreas de arroz e milho que
devem ser plantadas para obter lucro máximo. O lucro
19
devem ser plantadas para obter lucro máximo. O lucro
por unidade de área plantada de arroz é R$ 5,00 e de
milho é R$ 2,00. A área plantada de arroz não pode ser
maior que 3 unidades e a de milho maior do que 4.
Cada unidade de área plantada de arroz consome 1 hora
homem e de milho 2 horas homens. O consumo total de
horas homens não pode ser superior a 9 horas.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Solução Gráfica
� Quando o problema envolve apenas duas variáveis de
decisão, a solução ótima de um problema de
programação linear pode ser encontrada graficamente.
Max Z x x= +5 2
20
Max Z x x= +5 21 2
1
x (b)≤ 42
x x (c)+ ≤2 91 2
s r x (a)≤ 3. .
x x (d)≥ ≥0 01 2,
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Solução Gráfica
x2
x ≤≤≤≤424
x ≤≤≤≤31
21
21 4
1
2
x13
x ≤≤≤≤42
3
4
x ≥≥≥≥01
x ≥≥≥≥02
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear
Solução Gráfica
x ≤≤≤≤ 3
1
x2
(3,4)
LimiteReta
(1,4)
X1 + 2 X2 ≤ 9
X1 = 0 X2 = 0 
22
x ≤≤≤≤42
x1
x ≥≥≥≥ 01
x ≥≥≥≥ 02 (3,0)(0,0)
(0,4)
(3,4)
Região Limitada
(1,4)
(3,3)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
2X2 ≤ 9 X1 ≤ 9 
X2 = 9/2 
X2 = 4,5
Programação Linear
Solução Gráfica
x2
(0,4) (1,4) (3,3) = Solução
21 2521xxZ +==
(3,3)
23
x1
(0,4)
(0,0) (3,0)
Solução
Viável
(3,3)
21 2510 xxZ +==
= Solução
Ótima
(3,3)
21 250 xxZ +==
(0,0)
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear 
Solução Gráfica – Exercício 1
� 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,
24
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 quant. deve-se
comprar de cada produto de modo que as exigências de
alimentação sejam satisfeitas a um custo mínimo ?
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear 
Solução Gráfica – Exercício 2
� A Céu Azul 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
25
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 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 Céu Azul S/A. (resolva pela análise gráfica –
deslocamento da função objetivo).
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos
Programação Linear 
Solução Gráfica – Exercício 3
� Um empreendedor decidiu comercializar barcos. Depois de
empregar alguns trabalhadores e de descobrir os preços aos quais
venderia os modelos, chegou as seguintes observações: cada
modelo comum (A) rende um lucro de R$ 520,00, e cada modelo
rápido (B) rende um lucro de R$ 450,00. Um modelo comum
26
rápido (B) rende um lucro de R$ 450,00. Um modelo comum
requer 40 horas para ser construído e 24 horas para o acabamento.
Cada modelo rápido requer 25 horas para construção e 30 horas
para o acabamento. Este empreendedor dispõe de 400 horas de
trabalho por mês para a construção e 360 horas para o acabamento.
Quanto deve produzir de cada um dos modelos? Construa o
modelo matemático e encontre a solução ótima para o problema
utilizando o método gráfico.
Disciplina: Pesquisa Operacional Prof. Ms. Antonio dos Santos