Optimização
Numérica
Modelação de problemas
1ª aula teórico-prática
11/Setembro/2006
Introdução

Problema de Programação Matemática
É um problema de optimização escrito da
seguinte forma
Função objectivo
Optimizar: z = f(x1, …,xn)
g1(x1,…,xn)

Problema sem …
restrições =

gm(x1,…,xn)
Restrições
sujeito a:
b1
…
bm
Tipos de problemas

Problemas de Programação Linear


Problemas de Programação Quadrática


Função objectivo quadrática; restrições lineares; variáveis reais
Problemas de Programação Não Linear


Função objectivo linear; restrições lineares; variáveis reais
Função objectivo não linear; restrições lineares ou não lineares;
variáveis reais
Problemas de Programação Inteira

Variáveis inteiras
Problema Programação Linear

Variáveis



confeccionar 10 Kg de carne picada,
com no máximo 25% de gordura,
ao menor preço.
Função objectivo


v: Kg de carne de vaca utilizados
p: Kg de carne de porco utilizados
Pedido


%
Preço
gordura Kg
Min z = 8v + 6p
Restrições


0.2v + 0.3p  2.49
v + p = 10
Vaca
20
8
Porco
30
6
min z
s.a.
0.2v + 0.3p  2.49
v + p = 10
v, p  0
Problema Programação Linear
v0
p0
p
0.2v+0.3p  2.49
v
v+p = 10
Problema Programação Linear
Solução óptima
v = 5.1; p = 4.9
p
Região admissível
(segmento de recta)
v
z
Problema Programação Linear

Algoritmo Simplex (utilizando o MatLab)
>> options = optimset('LargeScale', 'off', 'Simplex', 'on');
>> f = [8; 6]; lb = zeros(2,1);
>> A = [0.2 0.3]; b = [2.49];
>> Aeq = [1 1]; beq = [10];
>> [x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,[],[],options)
Optimization terminated.
x=
5.1000
4.9000
fval =
70.2000
exitflag =
1
output =
iterations: 1
algorithm: 'medium scale: simplex'
cgiterations: []
message: 'Optimization terminated.'
lambda =
ineqlin: 20.0000
eqlin: -12.0000
upper: [2x1 double]
lower: [2x1 double]

Solução: v = 5.1; p = 4.9; z = 70.2
Problema Programação Inteira

Admita-se agora que a carne é vendida em embrulhos de
1Kg (não divisíveis)
min z
s.a.
0.2v + 0.3p  2.49
v + p = 10
v, p  0
v, p inteiros



Solução óptima do problema anterior
x = [5.1 4.9]T  [5 5]T
x = [5 5]T não é solução óptima do problema de
programação inteira pois não é admissível
A solução óptima deste problema é x = [6 4]T
Problema Programação Inteira

De uma forma geral
Solução óptimo do
problema inteiro
Solução óptimo do
problema contínuo
z
Problema Programação Quadrática






Quejo
Variáveis
d: Kg de queijo DeLux
DeLux
s: Kg de queijo Standard
Standard
Pd: preço por Kg DeLux
Ps: preço por Kg Standard quatidade
Frutas
Especial
Normal
20%
80%
0%
20%
30%
50%
20Kg
60Kg
Muito
Relação procura (D) / preço (P)
Dd = 190-25Pd; Ds = 250 – 50Ps

Pedido

Determinar a quantidade de queijo a produzir de cada tipo e o
respectivo preço, de forma a que


todo o queijo seja vendido
maxime a receita
Problema Programação Quadrática

Função objectivo


Max Z = d*Pd + s *Ps
Restrições





0.2d + 0.2s  20
0.8d + 0.3s  60
d = 190 - 25Pd
s = 250 - 50Ps
d, s  0
Pode ser reescrito com 2 variáveis
max z = d*(7.6 - 0.004*d)+
s*(5 - 0.02*s)
sujeito a:
0.2 d + 0.2 s  20
0.8 d + 0.3 s  60
d, s  0
z
d=55;
s=45
Problema Programação Quadrática

Resolução com o MatLab (max z  - min -z)
>> H = [0 0 -1 0; 0 0 0 -1; -1 0 0 0; 0 -1 0 0]; f = [0; 0; 0; 0];
>> A = [1 0 25 0; 0 1 0 50; 0.2 0.2 0 0; 0.8 0.3 0 0]; b = [190; 250; 20; 60];
>> lb = zeros(3,1); x0 = [1; 1; 1; 1];
>> [x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],x0)
Warning: Large-scale method does not currently solve this problem
formulation,
switching to medium-scale method.
output =
> In quadprog at 242
iterations: 4
Optimization terminated.
algorithm: 'medium-scale: active-set'
x=
firstorderopt: []
55.0000
cgiterations: []
45.0000
message: 'Optimization terminated.'
5.4000
lambda =
4.1000
lower: [4x1 double]
fval =
upper: [4x1 double]
-481.5000
eqlin: [0x1 double]
exitflag =
ineqlin: [4x1 double]
1
Problema Programação Não Linear

Problema dos mínimos quadrados
Dados os pontos (xi, yi), 1  i  n, e uma família
de funções y = f(x),   |Rp, pretende-se
minimizar {ni=1(yi – f(xi))2,   |Rp}
 Exemplo (recta dos mínimos quadrados):
f(x) = 1 + 2 x

Problema Programação Não Linear





Minimizar a soma as distâncias dos pontos à recta
aproximadora
A equação normal de uma recta é
c + a x + b y = 0, onde (a, b)  0 é um vector perpendicular à
recta
Podemos supor, sem perda de generalidade que
||(a, b)||2 = a2 + b2 = 1
A distância de (xi, yi) a recta é ri = c + a xi + b yi
Pretende-se então min z = ni=1(ri)2,
sujeito a:
ri = c + a xi + b yi, 1  i  n
a2 + b 2 = 1
Problema Programação Não Linear
Problema do trajecto mais curto