2.3 Operasjonaliseringar
2.3.2 Variablar på individnivå
O m´etodo primal-dual aqui apresentado baseia-se na proposta de Akrotiri- ankis e Rustem [4], que apresenta uma prova de convergˆencia global para problema de programa¸c˜ao n˜ao-linear. Consideremos, um problema de programa¸c˜ao n˜ao linear representado por:
M in. f (x)
S.a. g(x) = 0, x≥ 0 (2.34)
Neste caso tem-se f (x) : Rn → R e g(x) : Rn → Rm, cont´ınua e diferenci´avel.
Tomemos a aproxima¸c˜ao do problema (2.34) dada por
min f (x) + β2||g(x)||2− µPn
i=1ln(x)
Sujeito a: g(x) = 0 (2.35)
Um m´etodo primal-dual 40
penalidade quadr´atica e uma fun¸c˜ao de barreira logar´ıtmica. A fun¸c˜ao de penalidade quadr´atica aqui usada ´e a mesma fun¸c˜ao de m´erito apresentada na se¸c˜ao 2.3.1 e ´e usada aqui para refor¸car a satisfa¸c˜ao das restri¸c˜oes de igualdade adicionando um alto custo na fun¸c˜ao objetivo a pontos que n˜ao sejam fact´ıveis. A fun¸c˜ao de barreira logar´ıtmica ´e introduzida no MPI para garantir a factibilidade estrita enquanto aproxima da solu¸c˜ao ´otima.
O m´etodo de penalidade/barreira envolve itera¸c˜oes internas e externas. As itera¸c˜oes externas s˜ao associadas com o decrescimento do parˆametro de barreira µ, tal que µ → 0. As itera¸c˜oes internas determinam o parˆametro de penalidade β e ent˜ao resolve o problema (2.35) para determinados valores de µ e β.
As condi¸c˜oes de otimalidade para o problema (2.35) s˜ao dadas pelo sistema n˜ao linear de equa¸c˜oes
∇f(x) − µX −1e + β∇g(x)Tg(x)− ∇g(x)Ty g(x) = 0, x > 0 Utilizando a transforma¸c˜ao n˜ao-linear z = µX−1, obtemos:
F (x, y, z; β, µ) = ∇f(x) − zβ∇g(x)Tg(x)− ∇g(x)Ty g(x) XZe− µe = 0, x, z > 0. (2.36)
Para µ fixo, o sistema (2.36) ´e resolvido pelo m´etodo de Newton, onde temos:
H −∇gT −I ∇g 0 0 Z 0 X △x △y △z = − ∇f − z + β∇gTg − ∇gTy g XZe− µe (2.37) Onde, H =∇2 xxLβ =∇2f (x) + m X i=1 ∇gi(x)(βgi(x)− yi) + β∇g(x)∇g(x)T. X, Z
s˜ao matrizes diagonais em que os elementos diagonais s˜ao respectivamente as coorde- nadas de x e z. A solu¸c˜ao de (2.37) ´e obtida quando N = H + X−1Z ´e invers´ıvel, onde
Um m´etodo primal-dual 41
temos as seguintes dire¸c˜oes: △x = N−1(∇gT
△y − ∇f + z − β∇gTg
− ∇gTy)
△y = −[∇gN−1∇gT]−1[g− ∇gN−1(∇f − z + β∇gTg− ∇gTy)]
△z = −z + µX−1Z△x
Como no m´etodo primal-dual com barreira-logar´ıtmica visto na se¸c˜ao (2.3.1), uma vez que a dire¸c˜ao de busca tenha sido definida, o algoritmo processa interativa- mente determinando novas estimativas para a solu¸c˜ao ´otima calculando:
xk+1 = xk+ αk p△xk yk+1 = yk+ αk d△yk zk+1 = zk+ αk d△zk (2.38)
O controle do passo ´e feito de forma a assegurar que as itera¸c˜oes gerem pontos es- tritamente interiores `a regi˜ao fact´ıvel e, al´em disto, o algoritmo move por pontos que minimizem a fun¸c˜ao de m´erito
Φ = f (x) + β 2||g(x)|| 2 − µ n X i=1 ln(x)
que nada mais ´e do que a fun¸c˜ao objetivo do problema (2.35). Este decrescimento, como no m´etodo PDBL ´e garantido pela adequada sele¸c˜ao do parˆametro β a cada itera¸c˜ao. Em seu trabalho Akrotiriankis e Rustem [4] demonstra que esta fun¸c˜ao decresce monotonicamente e garante a convergˆencia para a solu¸c˜ao de (2.36) para µ fixo. Com a redu¸c˜ao de µ, tal que {µ} → 0, ´e encontrado o valor ´otimo para (2.34). A cada itera¸c˜ao o valor de β ´e definido de forma a poder garantir o decresci- mento da fun¸c˜ao Φ . Para µ fixo, o gradiente de Φ na k-´esima itera¸c˜ao ´e 9
∇Φ(xk; βk, µ) =∇f + βk∇gTkgk− µX−1e
Considerando a segunda equa¸c˜ao do sistema de Newton (2.37), a derivada direcional pode ser escrita como
△xT
k∇Φ(xk; βk, µ) =△xTk∇f(xk)− βk||gk||2− µ△xTkX −1 k e
Como o parˆametro µ das itera¸c˜oes internas ´e fixo, ent˜ao ´e poss´ıvel verificar que o sinal de ∇Φ(xk; βk, µ)△xk depende do valor de β. Sendo assim, β ´e definido
Conclus˜ao 42 como sendo superior a
△xT
k∇fk− µ△xTkXK−1e +||△xk||2H
||gk||2
garantindo o decrescimento da fun¸c˜ao de m´erito Φ e, conseq¨uentemente da fun¸c˜ao objetivo do problema original (2.34).
Na sele¸c˜ao do tamanho do passo primal, αp ´e selecionado conforme a regra de
Armijo (A.3) aplicado `a fun¸c˜ao objetivo a partir de um valor m´aximo para αmax p = ξminh min △xi k<0 xi k |△xi k| i com 0 < ξ < 1.
Enquanto o parˆametro de barreira µ ´e fixo, o passo αd´e determinado ao longo
da dire¸c˜ao △zk para cada vari´avel dual zki, i = 1, 2, ..., n, de forma que as seguintes
restri¸c˜oes sejam satisfeitas
αid= max{α > 0 : L i k ≤ (x i k+ αp△xik)(z i k+ α△z i k)≤ U i k}
Onde os limites inferior Li
k e superior Uki, i = 1, 2, ..., n s˜ao definidos como Lik =
min{1
2mµ, (x i
k+αp△xik)zki e Uki = max{2Mµ, (xik+αp△xik)zki}, sendo que os parˆametros
m e M s˜ao definidos como:
0 < m < minn1,(1−γk)(1−2µγ) mini{x i kz i k} µ γk∈ (0, 1) o e M ≥ maxn1,maxi{xikzik} µ o > 0 Os valores de m e M s˜ao mudados `a medida que µ decresce.
O algoritmo primal-dual para programa¸c˜ao n˜ao-linear aqui descrito encontra sua prova de convergˆencia global apresentada por Akrotirianakis e Rustem [4] desde que sejam satisfeitas certas condi¸c˜oes. Dentre essas condi¸c˜oes, o problema de job-shop n˜ao satisfaz a condi¸c˜ao referente a segunda condi¸c˜ao de otimalidade. Sendo assim, essa demonstra¸c˜ao n˜ao se aplica de forma direta ao nosso caso.
Conclus˜ao
Pela breve descri¸c˜ao do m´etodo de pontos interiores feita ao longo deste cap´ıtulo ´e poss´ıvel perceber a sua importˆancia como ferramenta de resolu¸c˜ao de pro-
Conclus˜ao 43 blemas de otimiza¸c˜ao tanto na forma de programa¸c˜ao linear como na forma de pro- grama¸c˜ao n˜ao linear.
Quanto aos m´etodos aplic´aveis a programa¸c˜ao n˜ao linear apresentados nas se¸c˜oes 2.3.1 e 2.3.2, as solu¸c˜oes obtidas para os sistemas (2.36) e (2.17) s˜ao as mesmas significando que os sistemas s˜ao equivalentes. Entretanto, estes n˜ao s˜ao algoritmos de Newton equivalentes (El-Bakry et al [17], Akrotirianakis e Rustem [4]).
No caso de um problema de job-shop temos duas possibilidades para a sua modelagem. Como especificado no cap´ıtulo 1, escolhemos uma modelagem cont´ınua de programa¸c˜ao n˜ao linear. Neste caso, alguns cuidados dever˜ao ser tomados em fun¸c˜ao de se tratar de um espa¸co de busca n˜ao convexo. Vale ressaltar em rela¸c˜ao ao m´etodo PDBL que toda discuss˜ao em torno da fun¸c˜ao de penalidade proposta (2.19) assume que a matriz N seja positiva definida. Entretanto, veremos que n˜ao podemos oferecer esta garantia no caso do problema de job-shop em quest˜ao. Ser´a, portanto, preciso fazer alguma altera¸c˜ao na Hessiana para que possamos garantir a positividade da matriz N . Veremos, portanto, no pr´oximo cap´ıtulo como efetuar estas mudan¸cas e quais as implica¸c˜oes no espa¸co de busca do primal e do dual.
Cap´ıtulo 3
M´etodo de Pontos Interiores
Aplicado ao Problema Job-Shop
Como apresentado anteriormente na se¸c˜ao 1.3.3 podemos modelar um pro- blema de seq¨uenciamento job-shop com uma modelagem cont´ınua, mas n˜ao linear e n˜ao convexa.
´
E fato que modelos de programa¸c˜ao n˜ao linear constituem geralmente um desafio maior para a busca de solu¸c˜oes (Wright [57]). Entretanto, o m´etodo de pontos interiores, conforme apresentamos na se¸c˜ao 2.3 tem apresentado bons resultados como ferramenta na busca de solu¸c˜oes de problemas de programa¸c˜ao n˜ao linear e n˜ao convexo (El-Bakry et al [17], Vanderbei e Shanno [56], Sousa e Costa [53]). Desta forma, a aparente dificuldade de modelos cont´ınuos pode ser superada com o uso de um m´etodo de ponto interior adequado, o que nos levou a adotar neste trabalho um modelo cont´ınuo inspirado na proposta de Pinson [42]. Neste cap´ıtulo discutiremos em mais detalhes o modelo cont´ınuo para o problema de job-shop adotado na se¸c˜ao 3.1. A seguir na se¸c˜ao 3.2 analisaremos o m´etodo de pontos interiores e as altera¸c˜oes que ser˜ao necess´arias para us´a-lo na resolu¸c˜ao do problema de job-shop considerado. Finalmente, faremos na se¸c˜ao 3.3 uma an´alise de convergˆencia da metodologia proposta.
An´alise do Modelo de Seq¨uenciamento Job-Shop Adotado 45
3.1
An´alise do Modelo de Seq¨uenciamento Job-Shop
Adotado
No primeiro cap´ıtulo foi feita uma descri¸c˜ao mais detalhada do problema de seq¨uenciamento job-shop (§1.2) e de formas pelas quais ´e poss´ıvel construir um modelo matem´atico para tal problema (§1.3). O que nos propomos agora ´e fazer uma an´alise mais acurada do modelo matem´atico n˜ao linear apresentado na se¸c˜ao (§1.3.3). Este modelo foi adotado em nosso trabalho pelos motivos mencionados anteriormente no cap´ıtulo 1, e por outros motivos que se evidenciar˜ao ao longo de nossas an´alises nas se¸c˜oes seguintes. Relembrando as defini¸c˜oes feitas nestas se¸c˜oes (§1.2, §1.3.3), podemos descrever um problema de seq¨uenciamento job-shop com em m´aquinas e p produtos como um problema de otimiza¸c˜ao restrito da forma:
M in. f (t) = n0 X j=1 tj S.a. tj+1− tj− dj ≥ 0 ∀j ∈ C −(tv− tu + dv)× (tu− tv+ du)≥ 0 ∀(u, v) ∈ D tj ≥ 0 j = 1, ..., p0 B − tj ≥ 0 j = 1, ..., p0 (3.1)
Fizemos uma mudan¸ca de sinal nas restri¸c˜oes tornando-as n˜ao negativas para adequar ao modelo padr˜ao de programa¸c˜ao n˜ao linear em que estaremos aplicando o m´etodo de pontos interiores. Al´em disto, inclu´ımos um limite superior B `as vari´aveis do problema. Este limite superior apenas serve como garantia de que se trata de um espa¸co de busca limitado facilitando demonstra¸c˜oes de teoremas subseq¨uentes. Vale ressaltar que essa altera¸c˜ao n˜ao altera em nada a solu¸c˜ao do problema original. O calculo desse limite foi feito tomando-se B =
n0
X
j=1
dj + 1 que ´e um valor superior ao
tempo de in´ıcio de qualquer opera¸c˜ao na pior de todas as hip´oteses.
ConsideremosR = {r = 1, ..., r0} como sendo um conjunto de ´ındices referen-
tes a cada restri¸c˜ao. Sendo assim, observe que nosso modelo foi dividido em quatro grupos de restri¸c˜oes. O primeiro, terceiro e quarto grupo de restri¸c˜oes s˜ao lineares e
An´alise do Modelo de Seq¨uenciamento Job-Shop Adotado 46
referindo-se respectivamente `as restri¸c˜oes conjuntivas ou de precedˆencia na gama ope- rat´oria, `as restri¸c˜oes de n˜ao negatividade das vari´aveis e ao limite superior imposto `as vari´aveis. A segunda restri¸c˜ao ´e onde se centraliza nossa principal aten¸c˜ao e refere-se aos pares de restri¸c˜oes disjuntivas. Este grupo de inequa¸c˜oes n˜ao ´e linear e al´em disto introduz uma componente n˜ao conexa em nosso espa¸co de busca de solu¸c˜oes. Vamos, portanto, analisar um pouco melhor este grupo de restri¸c˜oes. Consideremos a seguinte fun¸c˜ao:
g(tu, tv) = −(tv− tu+ dv)× (tu − tv+ du)
Fazendo as devidas multiplica¸c˜oes podemos reescrevˆe-la assim: g(tu, tv) = t2u+ t
2
v− 2tutv+ (du− dv)tu+ (dv − du)tv− dvdu (3.2)