Upload
internet
View
115
Download
3
Embed Size (px)
Citation preview
Programação Não-linear
Prof. Fernando Augusto Silva Marins
www.feg.unesp.br/~fmarins
1
Programação Não-Linear - PNL• De forma geral um problema de PNL tem a
seguinte forma:
A função objetivo f e uma ou mais de uma das funções nas restrições gi possuem termos não lineares.
• Nenhum algoritmo resolve todos os problemas que podem ser incluídos neste formato.
),...,,(= xonde 0 x
,...,2,1 para )x(
)x( )(ou
21 n
ii
xxx
mibgasujeito
fMinMax
2
Programação Não LinearAplicações
• Problemas de Mix de Produtos em que o “lucro” obtido por produto varia com a quantidade vendida.
• Problemas de Transporte com custos variáveis de transporte em relação à quantidade enviada.
• Seleção de Portfolio com Risco
3
• Considere o Problema de Programação Linear e sua solução gráfica
1
Max Z x x 3 51 2
1
2x 122
3x x 2 18 1 2
s r x 4. .
x x 0 01 2,
x2
x1
(0;6)(2;6)
(0;0)(4;0)
(4;3)SoluçõesViáveis
Programação LinearSolução Gráfica
4
• Considere o Problema e sua solução gráfica.
Max Z x x 3 51 2
1s.t. x 4
x x 0 01 2,
9 5 21612
22x x
x2
1 2 3 4
4
2
6
00 x1
SoluçõesViáveis
(2;6)
Programação Não LinearSolução Gráfica
5
• A solução ótima:– é a mesma do problema
linear.– continua na fronteira do
conjunto de soluções viáveis.
– não é mais um extremo do conjunto de soluções viáveis mas poderia ainda ocorrer em um ponto extremo.
– Não existe a simplificação existente em Programação Linear
x2
1 2 3 4
4
2
6
00 x1
SoluçõesViáveis
(2;6)
Programação Não LinearSolução Gráfica
6
1
2x 122
3x x 2 18 1 2
s r x 4. .
x x 0 01 2,
MaxZ= x x x x 126 9 182 131 12
2 22
x2
x1
(0;6)(2;6)
(0;0)(4;0)
(4;3)SoluçõesViáveis
Programação Não LinearSolução Gráfica
7
• A função objetivo é uma equação quadrática.
Programação Não LinearSolução Gráfica
Z= x x x x
Z x x x x
Z x x
Para x x
Para
126 9 182 13
9126
1813
182
269
126
9
126
1813
182
13
182
26
441 637 9 7 13 7
9 7 13 7
1 12
2 22
2 2
12
1
2
22
2
2
1
2
2
2
1
2
2
2
Z = 907 171 =
Z = 857
221 =
Z = 807 =
9 7 13 7
271 9 7 13 7
1
2
2
2
1
2
2
2
x x
Para x x8
Max Z = x x x x = 857 126 9 182 131 12
2 22
2
4
4
6
2 x 1
x2
SoluçõesViáveis
Z = 907
Z = 807Z = 857
Programação Não LinearSolução Gráfica
Ótima
9
1
2x 122
3x x 2 18 1 2
s r x 4. .
x x 0 01 2,
Max Z= x x x x 54 9 78 131 12
2 22
x2
x1
(0;6)(2;6)
(0;0)(4;0)
(4;3)SoluçõesViáveis
Programação Não LinearSolução Gráfica
10
• A função objetivo é uma equação quadrática
Z= x x x x
Z x x x x
Z x x
Para x x
Para
54 9 78 13
954
1813
78
269
54
9
54
1813
78
13
78
26
81 117 9 3 13 3
9 3 13 3
1 12
2 22
2 2
12
1
2
22
2
2
1
2
2
2
1
2
2
2
Z = 198 0 =
Z = 189
9 9 3 13 3
36 9 3 13 3
1
2
2
2
1
2
2
2
=
Z = 162 =
x x
Para x x
Programação Não LinearSolução Gráfica
11
Solução no interior doconjunto de soluçõesviáveis e não mais na fronteira do conjunto
4
2
6
2 4 x1
x2
SoluçõesViáveis
3
3
Z = 162Z = 189
Z = 198
222
211 1378954 xxxxZMax
222
211 1378954198 xxxx=ZMax
Programação Não LinearSolução Gráfica
12
Programação Não Linear
• A solução ótima de PNL, diferentemente de um problema de LP, pode ser qualquer valor do conjunto de soluções viáveis.
• Isso torna os problemas de PNL muito mais complexos, obrigando os algoritmos de solução a pesquisar todos os valores possíveis.
13
Programação Não LinearExcel
• O Excel utiliza o algoritmo GRG (Generalized Reduced Gradient) para chegar à solução para um dado problema.
• O algoritmo não garante que a solução encontrada é uma solução global.
• O Solver às vezes tem dificuldades de achar soluções para problemas que tenham condições iniciais para as variáveis iguais a zero. Uma boa medida é começar a otimização com valores diferentes de zero para as variáveis de decisão.
14
Programação Não LinearExcel
• Uma maneira prática para tentar minorar o
problema de máximos e mínimos locais é começar
a otimização de diversos pontos iniciais, gerados
aleatoriamente.
• Se todas as otimizações gerarem o mesmo
resultado, você pode ter maior confiança, não a
certeza, de ter atingido um ponto global.
15
• One special class of NLPs knowed by “Convex Programming Problems” can be solved by algorithms that are guaranteed to converge to the optimal solution.
16
• The objective is to maximize a concave function or to minimize a convex function.
• The set of constraints form a convex set.
Properties of Convex Programming Problems
17
• A smooth function (no sharp points, no discontinuities)• One global maximum (minimum).• A line drawn between any two points on the curve of
the function will lie below (above) the curve or on the curve.
A One Variable Concave (Convex) Function
X
A Concave function
A convex function
X18
An illustration of a two variable convex function
19
If a straight line that joins any two points in the set lies within the set, then the set is called a convex set.
Convex set Non-convex set
Convex Sets
20
In a NLP model if all the constraints are of the “less than or equal to” form Gi(X) B.
If all the functions Gi are convex, the set of constraints forms a convex set.
Nonlinear LP and Convex Sets
21
Unconstrained Nonlinear Programming
• One-variable unconstrained problems are demonstrated by the Toshi Camera problem.
• The inverse relationships between demand for an item and its value (price) are utilized in this problem.
22
TOSHI CAMERA
• Toshi camera of Japan has just developed a new product, the Zoomcam.
• It is believed that demand for the initial product will be linearly related to the price.
Price EstimatedP ($) Demand (X)
100 350.000150 300.000200 250.000250 200.000300 150.000350 100.000
23
• Unit production cost is estimated to be $50.• What is the production quantity that maximizes
the total profit from the initial production run?
SOLUTION
Total profit = Revenue - Production cost
F(X) = PX - 50X
TOSHI CAMERA
24
From the Price / Demand table it can be verified that P = 400 - .001X
The Profit function becomesF(X) = (400 - .001X)X = 400X - .001X2
This is a concave function. 400,0000
TOSHI CAMERA
25
• To obtain an optimal solution (maximum profit), two conditions must be satisfied:– A necessary condition dF/dX = 0– A sufficient condition d2F/dX2 < 0.
• The necessary condition is satisfied at:dF/dX = 400 - 2(.001)X = 0; X = 200,000.
• The sufficient condition is satisfied since d2F/dX2 = -.002.
• The optimal solution:– Produce 200,000 cameras.– The profit is F(200,000) = $40,000,000.
TOSHI CAMERA
26
If a function is known to be concave or convex at all points, the following condition is both a necessary and sufficient condition for optimality:
The point X* gives the maximum value for a concave function, or the minimum value for a convex function, F(X), if at X*
dF/dX = 0
Optimal solutions for concave/convex functions with one variable
27
– Determining whether or not a multivariate function is concave or convex requires analysis of the second derivatives of the function.
– A point X* is optimal for a concave (convex) function if all its partial derivatives are equal to zero at X*.
– For example, in the three variable case:
FX
FX
FX
11
22
33
0 0 0 ; ; ;
FX
FX
FX
11
22
33
0 0 0 ; ; ;
Optimal solutions for concave/convex functions with more than one variable
28
Constrained Nonlinear Programming Problems – one variable
• The feasible region for a one variable problem is a segment on a straight line (X a or X b).
• When the objective function is nonlinear the optimal solution must not be at an extreme point.
29
TOSHI CAMERA - revisited
• Toshi Camera needs to determine the optimal production level from among the following three alternatives: 150,000 X 300,000
50,000 X 175,000
150,000 X 350,000
30
4000
X 250,000X 350,000
X* = 250,000
40004000
Maximize F(X) = 400X - .001X2
X 150,000X 300,000
150
X 50,000X 175,000
50 175X*=200,000 X* = 175,000
The objective function does not change:
TOSHI CAMERA – solution
31
Constrained Nonlinear Programming Problems – n variables, m contraints
mn21m
2n212
1n211
n21
B)X..., ,X ,(XG
.
.
.
B)X..., ,X ,(XG
B)X..., ,X ,(XG
ST
)X..., ,X,(
XFMaximize
Let us define Y1, Y2, …,Ym as the instantaneous improvementin the value of F for one unitincrease in B1, B2, …Bm
respectively. 32
Variáveis Duais ou Preços Sombra
• This is a set of “necessary conditions” for optimality of most nonlinear problems.
• If the problem is convex, the K-T-K conditions are also sufficient for a point X* to be optimal.
m
mm
m
mm
mm
XGYX
GYXGYXn
F
XGYX
GYXGYX
F
SYSYSY
feasibleisX
...2
.
.
.
....4
0...,,0,0.3
0Y..., ,Y ,Y .2
.*.1
2
2
1
11
22
1
11
1
2211
m21
2
S1, S2, …,Sm
are defined as the slack variablesin each constraint.
Kuhn-Tucker-Karush optimality conditions
33
PBI INDUSTRIES
• PBI wants to determine an optimal production schedule for its two CD players during the month of April.
• Data– Unit production cost for the portable CD player = $50.
– Unit production cost for the deluxe table player = $90.
– There is additional “intermix” cost of $0.01(the number of portable CD’s)(the number of deluxe CD’s).
34
• Forecasts indicate that unit selling price for each CD player is related to the number of units sold as follows:– Portable CD player unit price = 150 - .01X1
– Deluxe CD player unit price = 350 - .02X2
PBI INDUSTRIES
35
• Resource usage– Each portable CD player uses 1 unit of a particular
electrical component, and .1 labor hour.– Each deluxe CD player uses 2 units of the electrical
component, and .3 labor hour.
• Resource availability– 10,000 units of the electrical component units; – 1,500 labor hours.
PBI INDUSTRIES
36
PBI INDUSTRIES – SOLUTION
• Decision variablesX1 - the number of portable CD players to produce
X2 - the number of deluxe CD players to produce
• The model
0
0 X-
1,500 .3X+ .1X
000,102
26010001.02..01X-
=X.01X-90X-50X-)X.02X-(350+)X.01X-(150
2
1
21
21
21212
22
1
21212211
X
XX
ST
XXXXX
Max
Production cannot be negative
Resource constraints
37
• For a point X1, X2 to be optimal, the K-T-K conditions require that:Y1S1 = 0; Y2S2 = 0; Y3S3 = 0; Y4S4 = 0, and
)1()0()3(.)2(26004.01.
)0()1()1(.)1(10001.02.
4
432121
2
44
2
33
2
22
2
11
2
432121
1
4
1
33
1
22
1
11
1
YYYYXX
or
XGYX
GYXGYX
GYXF
YYYYXX
or
XGYX
GYXGYX
GYXF
PBI INDUSTRIES – SOLUTION
38
• Finding an optimal production plan.– Assume X1>0 and X2>0.
• The assumption implies S3>0 and S4>0.
• Thus, Y3 = 0 and Y4 = 0.
– Add the assumption that S1 = 0 and S2 = 0.
• From the first two constraints we have X1 = 0 and X2 = 5000.X1= 0
A contradictionX1>0
AS A RESULT THE SECOND ASSUMPTION CANNOT BE TRUE
PBI INDUSTRIES – SOLUTION
39
– Change the second assumption. Assume that S1 = 0 and S2 > 0.
• As before, from the first assumption S3 > 0 and S4 > 0.
• Thus, Y3 = 0 and Y4 = 0.
• From the second assumption Y2 = 0.
• Substituting the values of all the Ys in the partial derivative equations we get the following two equations:
-.02 X1 - .01X2 + 100 = Y1
-.01 X1 - .04X2 + 260 = 2Y1
• Also, since S1 = 0 (by the second assumption)X1 + 2X2 = 10,000
• Solving the set of three equations in three unknowns we get:
PBI INDUSTRIES – SOLUTION
40
X1 = 1,000, X2 = 4,500, Y1 = 35
– This solution is a feasible point (check the constraints).• X1 and X2 are positive.
• 1X1 + 2X2 <= 10,000 [1000 + 2(4500) = 10,000]
• .1X1 + .3X2 <= 1,500 [.1(1000) + .3(4500) = 1450]
– This problem represents a convex program since• It can be shown that the objective function F is concave.
• All the constraints are linear, thus, form a convex set.
The K-T-K conditions yielded an optimal solution
PBI INDUSTRIES – SOLUTION
41
Portable Deluxe Total ProfitApril Production 1000 4500 810000
Portable Deluxe Used AvailableElectrical Components 1 2 10000 10000Labor Hours 0,1 0,3 1450 1500
PBI INDUSTRIES
PBI INDUSTRIES – Excel SOLUTION
42
Programação Não Linear Controle de Estoque
• Um dos modelos mais simples de controle de
estoque é conhecido como Modelo do Lote
Econômico.
• Esse tipo de modelo assume as seguintes hipóteses
– A demanda (ou uso) do produto a ser pedido é
praticamente constante durante o ano.
– Cada novo pedido do produto deve chegar de uma vez
no exato instante em que este chegar a zero.
43
Programação Não Linear Controle de Estoque
• Determinar o tamanho do pedido e a sua periodicidade dado os seguintes custos:– Manutenção de Estoque – Custo por se manter o
capital no estoque e não em outra aplicação, rendendo benefícios financeiros para a empresa.
– Custo do Pedido – Associado a trabalho de efetuar o pedido de um determinado produto.
– Custo de Falta – Associado a perdas que venham a decorrer da interrupção da produção por falta do produto.
44
Demanda Anual =100Lote=25,Pedido= 4Estoque Médio = 12,5
3 6 9 12meses
25
12,5
25
Demanda Anual =100Lote=50, Pedidos = 2Estoque Médio = 25
6 12meses
50
Programação Não Linear Controle de Estoque
45
Programação Não Linear Controle de Estoque
mC2
QS
Q
DCDTotal Custo
Constante• Variável de DecisãoQ – Quantidade por Pedido
• Função Objetivo =
Onde:D = Demanda Anual do Produto
C = Custo Unitário do Produto
S = Custo Unitário de Fazer o Pedido
Cm= Custo unitário de manutenção em estoque por ano
46
Caso LCL Computadores
• A LCL Computadores deseja diminuir o seu
estoque de mainboards. Sabendo-se que o custo
unitário da mainboard é de R$50,00, o custo
anual unitário de manutenção de estoque é de
R$20,00 e o custo unitário do pedido é de
R$10,00, encontre o lote econômico para atender
a uma demanda anual de 1000 mainboards.
47
Caso LCL Computadores
48
Caso LCL Computadores
49
Caso LCL Computadores
50
Caso LCL Computadores
• Na solução apresentada do lote econômico, a quantidade de pedidos por ano é fracionário, já que
• Isso não representa um problema
25,3132
1000
º
LotedoTamanho
AnualDemandalotesden
51
PNL - Problemas de Localização
• Um problema muito usual na área de negócios é o de localização de Fábricas, Armazéns, Centros de distribuição e torres de transmissão telefônica.
• Nesses problemas deve-se Minimizar a distância total entre os centros consumidores e o centro de distribuição, reduzindo assim teoricamente o custo de transporte.
• Para tal, o usual é sobre um mapa colocar-se um eixo cartesiano e determinar a posição dos centro consumidores em relação a uma origem aleatória.
52
Caso LCL Telefonia Celular S.A.
Localidade X Y
Nova Iguaçu -5 10
Queimados 2 1
Duque de Caxias 10 5
• O Gerente de Projetos da LCL Telecom, tem que localizar uma antena de retransmissão para atender a três localidades na Baixada Fluminense.
• Por problemas técnicos a antena não pode estar a mais de 10 km do centro de cada cidade. Considerando as localizações relativas abaixo, determine o melhor posicionamento para a torre.
53
Caso LCL Telefonia Celular S.A.
Nova Iguaçu(-5,10)
Queimados (2,1)
Duque deCaxias(10,5)
X
Y
54
Caso LCL Telefonia Celular S.A.
3
1
22 )()(i
ii YyXxMin
• Variáveis de Decisão– X – Coordenada no eixo X da torre de
transmissão– Y – Coordenada no eixo Y da torre de
transmissão
• Função Objetivo
55
Caso LCL Telefonia Celular S.A.
10)()(
10)()(
10)()(
23
23
22
22
21
21
YyXx
YyXx
YyXx
• Restrições de Distância
56
Caso LCL Telefonia Celular S.A. Modelo no Excel
=SOMA(D2:D4)
57
Caso LCL Telefonia Celular S.A.Parametrização
58
Caso LCL Telefonia Celular S.A. Solução
59