lista PNL

Prévia do material em texto

Lista de exercícios – Programação Não-linear 
 
1. Considere o seguinte problema: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 𝑥3 + 2𝑥 − 2𝑥2 − 0,25𝑥4 
(a) Aplique o método da bissecção para resolver (aproximadamente) esse 
problema. Use uma tolerância de erro 𝜖 = 0,04 e limites iniciais 𝑥 = 0, 𝑥 =
2,4. 
(b) Aplique o método de Newton, com 𝜖 = 0,001 e 𝑥1 = 1,2, a esse problema. 
 
2. Use o método da bisseção com uma tolerância de erro 𝜖 = 0,04 e com os 
seguintes limites iniciais para resolver interativamente (de forma aproximada) cada 
um dos seguintes problemas: 
(a) 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 6𝑥 − 𝑥2, com 𝑥 = 0, 𝑥 = 4,8. 
(b) 𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 6𝑥 + 7𝑥2 + 4𝑥3 + 𝑥4, com 𝑥 = −4, 𝑥 = 1. 
 
3. Considere o seguinte problema: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 𝑥3 + 30𝑥 − 𝑥6 − 2𝑥4 − 3𝑥2 
(a) Aplique o método da bissecção para resolver (aproximadamente) esse 
problema. Use uma tolerância de erro 𝜖 = 0,07 e encontre os limites 
iniciais apropriados por inspeção. 
(b) Aplique o método de Newton, com 𝜖 = 0,001 e 𝑥1 = 1, a esse problema. 
 
4. Considere o seguinte problema de otimização irrestrita: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 2𝑥1𝑥2 + 𝑥2 − 𝑥1
2 − 2𝑥2
2 
Partindo da solução experimental inicial (𝑥1, 𝑥2) = (1, 1), aplique 
interativamente o método de busca por gradiente com 𝜖 = 0,25 para obter uma 
solução aproximada. 
 
5. Partindo da solução experimental inicial (𝑥1, 𝑥2) = (0, 0), aplique 
interativamente o método de busca por gradiente com 𝜖 = 0,3 para obter uma 
solução aproximada para o problema a seguir: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 8𝑥1 − 𝑥1
2 − 12𝑥2 − 2𝑥2
2 + 2𝑥1𝑥2 
 
6. Partindo da solução experimental inicial (𝑥1, 𝑥2) = (0, 0), aplique uma iteração 
do método de busca por gradiente ao problema seguinte: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 4𝑥1 + 2𝑥2 + 𝑥1
2 − 𝑥1
4 − 2𝑥1𝑥2 − 𝑥2
2. 
Para completar essa iteração, encontre manualmente 𝑡∗ por aproximação 
aplicando duas iterações do método da bisseção com limites iniciais 𝑡 = 0, 𝑡 = 1. 
 
7. Considere o seguinte problema de programação não-linear: 
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 𝑥1
4 + 2𝑥1
2 + 2𝑥1𝑥2 + 4𝑥2
2 
sujeito a 
2𝑥1 + 𝑥2 ≥ 10 
𝑥1 + 2𝑥2 ≥ 10 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
Quais são as condições de KKT para esse modelo? Use essas condições para 
determinar se (𝑥1, 𝑥2) = (0, 10) pode ser ótima. 
 
8. Utilize as condições de KKT para obter a solução ótima do seguinte problema de 
programação não-linear: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 24𝑥1 − 𝑥1
2 + 10𝑥2 − 𝑥2
2 
sujeito a 
𝑥1 ≤ 8 
𝑥2 ≤ 7 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
 
9. Considere o seguinte problema de otimização restrita linearmente: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = ln(𝑥1 + 1) − 𝑥2
2 
sujeito a 
𝑥1 + 2𝑥2 ≤ 3 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
em que ln representa o logaritmo natural. 
(a) Confirme que esse problema é um problema de programação convexa. 
(b) Utilize as condições de KKT para obter uma solução ótima. 
 
10. Use as condições de KKT para obter uma solução ótima para cada um dos seguintes 
problemas. 
(a) 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 𝑥1 + 2𝑥2 − 𝑥2
3 
sujeito a 
𝑥1 + 𝑥2 ≤ 1 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
 
(b) 𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 20𝑥1 + 10𝑥2 
sujeito a 
𝑥1
2 + 𝑥2
2 ≤ 1 
𝑥1 + 2𝑥2 ≤ 2 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
 
11. Considere o seguinte problema de programação quadrática: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 8𝑥1 − 𝑥1
2 + 4𝑥2 − 𝑥2
2 
sujeito a 
𝑥1 + 𝑥2 ≤ 2 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
(a) Use as condições de KKT para obter uma solução ótima. 
(b) Suponha agora que esse problema deva ser resolvido pelo método simplex 
modificado. Formule o problema de programação linear que deve ser 
resolvido explicitamente e então identifique a restrição de 
complementaridade adicional que é automaticamente satisfeita pelo 
algoritmo. 
(c) Aplique o método simplex modificado ao problema conforme formulado no 
item (b). 
 
12. Considere o seguinte problema de programação quadrática: 
𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑓(𝑥) = 20𝑥1 − 20𝑥1
2 + 50𝑥2 − 5𝑥2
2 + 18𝑥1𝑥2 
sujeito a 
𝑥1 + 𝑥2 ≤ 6 
𝑥1 + 4𝑥2 ≤ 18 
e 
𝑥1 ≥ 0, 𝑥2 ≥ 0. 
Suponha que esse problema deva ser resolvido por meio do método 
simplex modificado. 
(a) Formule o problema de programação linear que deve ser resolvido 
explicitamente e depois identifique a restrição de complementaridade 
adicional que é garantida automaticamente pelo algoritmo. 
(b) Aplique o método simplex modificado ao problema conforme formulado no 
item (a). 
 
Respostas de alguns exercícios 
1. Solução aproximada 1,0125. 
5. A solução exata é (𝑥1, 𝑥2) = (2, −2) 
7. −4𝑥1
3 − 4𝑥1 − 2𝑥2 + 2𝑢1 + 𝑢2 = 0 (𝑜𝑢 ≤ 0 𝑠𝑒 𝑥1 = 0) 
 −2𝑥1 − 8𝑥2 + 𝑢1 + 2𝑢2 = 0 (𝑜𝑢 ≤ 0 𝑠𝑒 𝑥2 = 0) 
 −2𝑥1 − 𝑥2 + 10 = 0 (𝑜𝑢 ≤ 0 𝑠𝑒 𝑢1 = 0) 
 −𝑥1 − 2𝑥2 + 10 = 0 (𝑜𝑢 ≤ 0 𝑠𝑒 𝑢2 = 0) 
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑢1 ≥ 0, 𝑢2 ≥ 0 
10. (a) (𝑥1, 𝑥2) = (1 − 3
−1 2⁄ , 3−1 2⁄ ) 
11. (a) (𝑥1, 𝑥2) = (2, 0)