Otimização Linear por Solução Gráfica

Prévia do material em texto

Otimização Linear 
 
Solução Gráfica 
Prof. Dr. Willy A. de Oliveira Soler 
Resolução Gráfica no ℝ𝟐 
 
𝑓 𝑥 = 𝑓 𝑥1, 𝑥2 = 𝑐1𝑥1 + 𝑐2𝑥2 
𝑓 𝑥1, 𝑥2 = 𝑘 ⟺ 𝑐1𝑥1 + 𝑐2𝑥2 = 𝑘 (curva de nível 𝑧 = 𝑘) 
𝛻𝑓 𝑥 = 𝑐1, 𝑐2 = 𝑐, ∀ 𝑥 ∈ ℝ
2 
Curva de nível 
𝑧 = 𝑘 
𝑥1 
𝑥2 
𝛻𝑓 = 𝑐 
𝑥0 
𝑥1 = 𝑥0 − 𝜖𝛻𝑓 𝑥0 
Uma solução 
factível inicial 
Uma nova solução obtida 
a partir de 𝑥0 se deslocando 
na direção oposta ao gradiente 
A Proposição 1 nos garante 
que 𝑓 𝑥1 < 𝑓 𝑥0 = 𝑘 
𝑥0 = 𝑥1
0, 𝑥2
0 uma solução inicial com valor 𝑓 𝑥0 = 𝑐1𝑥1
0 + 𝑐2𝑥2
0 = 𝑘 
Resolução Gráfica no ℝ𝟐 
A proposição 1 nos permite desenvolver um algoritmo para resolver graficamente qualquer 
problema de otimização linear com duas variáveis de decisão: 
Minimização 
Passo 1: Esboce a região factível (𝑆) do problema (𝑃) no plano cartesiano 
Passo 2: Identifique uma solução factível qualquer para (P) e trace a sua curva de nível 
Passo 3: Desloque a curva de nível na direção oposta ao vetor gradiente (para minimização) 
até alcançar um ponto extremo da região factível 
Passo 4: Identifique o ponto extremo e calcule o valor de função objetivo associado 
Maximização 
Basta substituir o Passo 3 pelo Passo 3’ 
Passo 3’: Desloque a curva de nível na direção do vetor gradiente até alcançar um ponto 
extremo da região factível 
Exemplo 1: Um artesão produz dois tipos de jogos de madeira e sua capacidade de trabalho é 
de 50 horas semanais. O jogo A requer 3 horas de trabalho para ser confeccionado e é vendido 
por R$ 30,00, enquanto que, o jogo B requer 5 horas para ser produzido e possui preço de 
venda de R$ 40,00. A demanda máxima para o jogo B é de 7 unidades e para o jogo A, 15. 
Determine a quantidade a ser produzida de cada jogo visando maximizar o lucro obtido pelo 
artesão. 
 
Exemplo 1: Um artesão produz dois tipos de jogos de madeira e sua capacidade de trabalho é de 50 
horas semanais. O jogo A requer 3 horas de trabalho para ser confeccionado e é vendido por R$ 
30,00, enquanto que, o jogo B requer 5 horas para ser produzido e possui preço de venda de R$ 
40,00. A demanda máxima para o jogo B é de 7 unidades e para o jogo A, 15. Determine a 
quantidade a ser produzida de cada jogo visando maximizar o lucro obtido pelo artesão. 
Solução: Primeiramente, vamos escrever um modelo para representar o problema. Em seguida, 
aplicaremos o método gráfico para encontrar a melhor solução. 
Variáveis de decisão: 
𝑥𝑗: quantidade a ser produzida do jogo 𝑗 = 𝐴, 𝐵. 
Objetivo: 
max 30𝑥𝐴 + 40𝑥𝐵 
Capacidade de trabalho: 
3𝑥𝐴 + 5𝑥𝐵 ≤ 50 
Demandas máximas: 
𝑥𝐴 ≤ 15 e 𝑥𝐵 ≤ 7 
Solução: O modelo é dado por 
 
 
 
 
Agora, vamos representar a região factível e curva de nível 𝑓∗ = 0. 
max30𝑥𝐴 + 40𝑥𝐵 
3𝑥𝐴 + 5𝑥𝐵 ≤50 
𝑥𝐴 ≤ 15 
𝑥𝐴 ≥ 0, 𝑥𝐵 ≥ 0 
s.a. 
𝑥𝐵 ≤ 7 
𝑓∗ = 0 
𝑥𝐴 = 15 
𝑥𝐵 = 7 
𝑓∗ = 0 
7 
15 5 
𝑓∗ = 0 
Solução ótima 
𝑥𝐴
∗ = 15 
𝑥𝐵
∗ = 1 
𝑧∗ = 30 ∗ 15 + 40 ∗ 1 = 490 
(valor ótimo) 
1 
𝑥𝐴 
𝑥𝐵 
30𝑥𝐴 + 40𝑥𝐵 = 0 
Exemplo 2: Resolva o problema de otimização linear abaixo utilizando o método gráfico. 
 
 
 
 
 
 
min𝑓 𝒙 = −𝑥1 − 2𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
𝑥1 + 𝑥2 ≤ 4 
𝑥1 ≤ 2 
𝑥2 ≤ 3 
Exemplo 2: 
 
 
 
 
Solução: Vamos aplicar o algoritmo desenvolvido. 
Passo 1: Esboçar a região factível 
𝑆 = 𝑥1, 𝑥2 ∈ ℝ
2|𝑥1 + 𝑥2 ≤ 4, 𝑥1≤ 2, 𝑥2≤ 3, 𝑥1≥ 0, 𝑥2≥ 0 
min𝑓 𝒙 = −𝑥1 − 2𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
𝑥1 + 𝑥2 ≤ 4 
𝑥1 ≤ 2 
𝑥2 ≤ 3 
𝑥1 
𝑥2 𝑥1 = 2 
2 
3 
2 
1 
𝑥2 = 3 
𝑥1 + 𝑥2 = 4 𝑆 
Exemplo 2: 
Solução: Vamos aplicar o algoritmo desenvolvido. 
Passo 2: Encontrar uma solução factível inicial e traçar a curva de nível 
Solução Factível: 𝑥0 = 0, 0 𝑓 𝑥 = −𝑥1 − 2𝑥2 
 
𝑓 𝑥0 = 𝑓 0, 0 = 0 
Curva de nível: 𝑓 𝑥1, 𝑥2 = 0⟺ −𝑥1 − 2𝑥2 = 0 
𝑥1 
𝑥2 
2 
3 
1 
𝑆 
𝑥0 
2 
−1 2 
𝑓 = 0 
Exemplo 2: 
Solução: Vamos aplicar o algoritmo desenvolvido. 
Passo 3: Deslocar a curva de nível na direção oposta ao vetor custo (vetor gradiente) até 
alcançar um ponto extremo da região factível 
𝑓 𝑥 = −𝑥1 − 2𝑥2 
 
𝛻𝑓 = 𝑐 = −1,−2 
𝑥1 
𝑥2 
2 
3 
1 
𝑆 
𝑥0 
2 
𝑓 = 0 
−1 
𝛻𝑓 
Solução 
Ótima 
Exemplo 2: 
Solução: Vamos aplicar o algoritmo desenvolvido. 
Passo 4: Identifique o ponto extremo e calcule o valor de função objetivo associado 
𝑓 𝑥 = −𝑥1 − 2𝑥2 
 
𝑥∗ = 1, 3 
𝑥1 
𝑥2 
2 
3 
1 
𝑆 
𝑥0 
2 
𝑓 = 0 
𝛻𝑓 
Solução 
Ótima 
𝑓(𝑥∗) = 𝑓 1, 3 = −1 − 2 ∗ 3 = −7 
(Solução ótima) 
(Valor ótimo) 
Exemplo 3: Resolva o problema de otimização linear abaixo utilizando o método gráfico. 
 
 
 
 
 
 
min 𝑓 𝒙 = −𝑥1 − 𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
−3𝑥1 + 𝑥2 ≤ 2 
𝑥1 + 2𝑥2 ≤ 9 
𝑥2 ≤ 3 
3𝑥1 + 𝑥2 ≤ 18 
Exemplo 3: 
 
 
 
 
Solução: 
Passo 1: Esboçar a região factível 
min𝑓 𝒙 = −𝑥1 − 𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
−3𝑥1 + 𝑥2 ≤ 2 
𝑥1 + 2𝑥2 ≤ 9 
𝑥2 ≤ 3 
3𝑥1 + 𝑥2 ≤ 18 
𝑥1 
𝑥2 
3 
1
3
 
𝑥2 = 3 
−3𝑥1 + 𝑥2 = 2 
5 3 
3𝑥1 + 𝑥2 = 18 
27
5
 
9
5
 
𝑥1 + 2𝑥2 = 9 
6 
Exemplo 3: 
Solução: 
Passo 2: Encontrar uma solução factível inicial e traçar a curva de nível 
Solução Factível: 𝑥0 = 0, 0 𝑓 𝑥 = −𝑥1 − 𝑥2 
 
𝑓 𝑥0 = 𝑓 0, 0 = 0 
Curva de nível: 𝑓 𝑥1, 𝑥2 = 0⟺ −𝑥1 − 𝑥2 = 0 ⟺ 𝑥2 = −𝑥1 
𝑥1 
𝑥2 
3 
1
3
 5 3 27
5
 
9
5
 
6 
𝑓 = 0 
𝒙𝟎 
Exemplo 3: 
Solução: 
Passo 3: Deslocar a curva de nível na direção oposta ao vetor custo (vetor gradiente) até 
alcançar um ponto extremo da região factível 
𝑓 𝑥 = −𝑥1 − 𝑥2 
 
𝛻𝑓 = 𝑐 = −1,−1 
𝑥1 
𝑥2 
3 
1
3
 5 3 27
5
 
9
5
 
6 
𝑓 = 0 Solução 
Ótima 
𝛻𝑓 
𝒙𝟎 
Exemplo 3: 
Solução: 
Passo 4: Identifique o ponto extremo e calcule o valor de função objetivo associado 
𝑓 𝑥 = −𝑥1 − 𝑥2 
 
𝑥∗ =
27
5
,
9
5
 
𝑓(𝑥∗) = 𝑓
27
5
,
9
5
= −
27
5
−
9
5
= −
36
5
= −7,2 
(Solução ótima) 
(Valor ótimo) 
𝑥1 
𝑥2 
3 
1
3
 5 3 27
5
 
9
5
 
6 
𝑓 = 0 Solução 
Ótima 
𝛻𝑓 
𝒙𝟎 
Exemplo 4: Resolva o problema de otimização linear abaixo utilizando o método gráfico. 
 
 
 
 
Solução: 
 
 
min 𝑓 𝒙 = −𝑥1 − 𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
−𝑥1 + 𝑥2 ≤ 2 
𝑥1 
𝑥2 
2 
𝑓 = 0 
𝛻𝑓 
𝒙𝟎 
Não existe uma 
solução ótima 
Exemplo 5: Resolva o problema de otimização linear abaixo utilizando o método gráfico. 
 
 
 
 
Solução: 
 
 
min 𝑓 𝒙 = −𝑥1 − 𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
−𝑥1 + 𝑥2 ≤ 2 
𝑥1 + 𝑥2 ≤ 5 
−𝑥1 + 𝑥2 = 2 
𝑥1 + 𝑥2 = 5 
𝑓
3
2
,
7
2
= −
3
2
−
7
2
= −
10
2
= −5 
𝑓 5, 0 = −5 − 0 = −5 
𝑥1 
𝑥2 
2 
𝑓 = 0 
𝛻𝑓 
𝒙𝟎 5 3
2
 
7
2
 
Existe um segmento (R) de 
soluções ótimas 
𝑅 =
𝑥1, 𝑥2 | 𝑥1 + 𝑥2 = 5;
3
2
≤ 𝑥1 ≤ 5; 0 ≤ 𝑥2 ≤
7
2
⊂ 𝑆 
𝑥∗ ∈ 𝑅 ⇒ 𝑓 𝑥∗ = −𝑥1
∗ − 𝑥2
∗ 
 = − 𝑥1
∗ + 𝑥2
∗ = −5 
 
Resolução Gráfica no ℝ𝟐 
Exemplo 5: Resolva o problema de otimização linear abaixo utilizando o método gráfico. 
 
 
 
 
Solução: 
 
 
min 𝑓 𝒙 = −𝑥1 − 𝑥2 
s.a. 
𝑥1 ≥ 0, 𝑥2 ≥ 0 
−𝑥1 + 𝑥2 ≤ 2 
𝑥1 + 𝑥2 ≤ 5 
−𝑥1 + 𝑥2 = 2 
𝑥1 + 𝑥2 = 5 
𝑥1 
𝑥2 
2 
𝑓 = 0 
𝛻𝑓 
𝒙𝟎 5 3
2
 
7
2
 
Existe um segmento (R) de 
soluções ótimas 
Isso pode ocorrer quando o vetor 
custo (𝑐) é paralelo a uma linha da 
matriz de recurso 𝐴. 
𝑐 = −1 , −1 = −1 1 , 1 = −1𝐴2 
 
 
Resolução Gráfica no ℝ𝟐 
Conclusões que podemos extrair dos exemplos resolvidos: 
• Um PL pode admitir uma única solução ótima 
• Um PL pode não possuir solução ótima (exemplo 4) 
• Um PL pode admitir um segmento de soluções ótimas (exemplo 5) 
• Se um PL admite solução ótima, então existe (pelo menos um) vértice ótimo 
 
Esse último fato, embora não intuitivo, é sempre verdadeiro independentemente do 
número de variáveis de decisão. Ele é a base para o estabelecimento do algoritmo simplex. 
 
Proposição 2: Se um problema de otimização linear admite solução ótima, então existe um 
vértice ótimo.