6. Kapittel: Avslutning
6.1 Hovedfunn og konklusjon
Method)
O M´etodo da Programa¸c˜ao de Metas foi proposto por Charnes e Cooper (1961), cuja id´eia baseia-se em encontrar uma solu¸c˜ao que atinja metas pr´e-definidas para cada uma das fun¸c˜oes objetivo. Contudo, se n˜ao existir uma solu¸c˜ao que satisfa¸ca esse crit´erio, faz-se necess´ario, ent˜ao, encontrar solu¸c˜oes que minimizam os desvios em rela¸c˜ao `as metas. Por outro lado, se esta solu¸c˜ao existir, a tarefa do m´etodo ´e identificar esta solu¸c˜ao particular. A programa¸c˜ao de metas ganhou popularidade depois dos trabalhos de Lee (1972) e Ignizio (1976). Romero (1991) fez um levantamento do “estado da arte” desta t´ecnica e listou algumas aplica¸c˜oes em engenharia.
Essa abordagem considera essas metas como sendo restri¸c˜oes adicionais, fazendo assim com que novas vari´aveis sejam acrescentadas para representar os desvios com rela¸c˜ao `as metas pr´e-determinadas. Com isso, a fun¸c˜ao objetivo especifica os desvios em rela¸c˜ao a essas metas e prioriza o sucesso de cada meta, em termos quantitativos.
Seja a minimiza¸c˜ao de v´arias fun¸c˜oes objetivo fi(x) com um vetor solu¸c˜ao x. No m´etodo da Programa¸c˜ao de Metas, um valor alvo ti ´e escolhido pelo usu´ario para cada uma das fun¸c˜oes objetivo. A tarefa agora ´e encontrar uma solu¸c˜ao que tenha um valor objetivo igual a ti, sujeito `a condi¸c˜ao de que a solu¸c˜ao encontrada seja vi´avel, isto ´e, x ∈ S (S → regi˜ao vi´avel). Desse modo, o problema de otimiza¸c˜ao pode ent˜ao ser reformulado como:
Meta ⇛ fi(x) = ti, i = 1, ..., M (3.20)
Se a meta ti ´e menor que o valor ´otimo, f (x∗), naturalmente n˜ao existe uma solu¸c˜ao vi´avel que atingir´a exatamente a meta acima. Portanto, o objetivo dessa abordagem ´e a obten¸c˜ao da solu¸c˜ao que minimiza o desvio △ entre a meta encontrada e a desejada (ti). A solu¸c˜ao para este problema ´e x∗, e o desvio ´e definido como △ = fi(x∗) − ti.
Analogamente, se o valor da fun¸c˜ao objetivo na meta ti´e maior que o m´aximo poss´ıvel fi,max, a solu¸c˜ao do problema ´e x, que faz fi(x) = fi,max. Por outro lado, se o valor da fun¸c˜ao objetivo na meta ti est´a dentro da faixa [fi(x), fi,max], a solu¸c˜ao para o problema ´e o valor de x que faz o valor do objetivo exatamente igual a ti. Embora esta solu¸c˜ao possa n˜ao ser a solu¸c˜ao ´otima da fun¸c˜ao restrita fi(x), esta ser´a o resultado ´otimo obtido atrav´es do m´etodo da programa¸c˜ao de metas (OSYCZKA, 1984).
De forma a permitir a obten¸c˜ao das metas apresentadas a seguir, duas vari´aveis n˜ao negativas denominadas desvios (ni e pi) s˜ao usualmente introduzidas (OSYCZKA, 1978). Segundo o autor, as metas podem ser de quatro tipos diferentes:
• fi(x) ≤ ti ⇒ nessa meta o desvio positivo pi ´e subtra´ıdo da fun¸c˜ao objetivo, ent˜ao, fi(x) − pi ≤ ti com ni = 0, isto ´e, o desvio pi, representa uma quantidade a ser subtra´ıda do valor do objetivo quando esta ultrapassar a meta ti. Portanto, o objetivo ´e minimizar o desvio pi para encontrar a solu¸c˜ao:
(
fi(x) > ti se pi > 0 fi(x) ≤ ti se pi = 0
(3.21)
• fi(x) ≥ ti ⇒ nesse caso, um desvio negativo ni ´e adicionado `a fun¸c˜ao objetivo, ent˜ao, fi(x) + ni ≤ ti com pi = 0. O desvio ni representa uma quantidade a ser
3.2. M´etodos para o Tratamento de POMO 37
adicionada `a fun¸c˜ao objetivo quando esta n˜ao atinge a meta ti. Aqui, o objetivo ´e minimizar o desvio ni:
(
fi(x) < ti se ni > 0 fi(x) ≥ ti se ni = 0
(3.22)
• fi(x) = ti ⇒ a fun¸c˜ao objetivo precisa ter o valor ti, assim s˜ao usados ambos os desvios positivos e negativos, ent˜ao fi(x) − pi+ ni = ti. O m´etodo minimiza a soma pi+ ni, logo a solu¸c˜ao obtida ´e a distˆancia m´ınima em rela¸c˜ao `a meta.
Se fi(x) > ti, o desvio pi deve ser um valor positivo diferente de zero, se fi(x) < ti, o desvio ni deve ser um valor positivo diferente de zero e para fi(x) = ti, ambos os desvios pi e ni devem ser zeros.
• fi(x) ∈ [tmin
i , tmaxi ] ⇒ esse tipo de meta ´e tratada usando duas restri¸c˜oes: (
fi(x) − pi ≤ tmini fi(x) + ni ≥ tmax
i
(3.23)
Todas as restri¸c˜oes acima podem ser substitu´ıdas por uma restri¸c˜ao de igualdade:
fi(x) − pi + ni = ti (3.24)
Resumidamente, no problema de programa¸c˜ao de metas, cada meta ´e convertida em ao menos uma restri¸c˜ao de igualdade, o que nesse caso resulta em um problema onde se deseja minimizar todos os desvios pi e ni. Existem v´arios tipos de M´etodos de Programa¸c˜ao de Metas. A seguir s˜ao apresentados e discutidos apenas os mais populares.
◦ Programa¸c˜ao de Meta Ponderada
Seja o problema de minimiza¸c˜ao multi-objetivo, onde para cada fun¸c˜ao objetivo se estabelece uma meta:
min k X j=1 (wjpj + βjnj) (3.25) ( fj(x) − pj + nj = tj, j = 1, ..., k nj, pj ≥ 0, j = 1, ..., k (3.26)
Aqui os parˆametros wj e βj s˜ao os fatores de pondera¸c˜ao para minimizar os desvios do j -´esimo objetivo em rela¸c˜ao `a j -´esima meta.
Para a meta menor ou igual a ti (fi(x) ≤ ti), o parˆametro βj ´e zero (nj = 0). Analogamente, para a meta maior ou igual a ti (fi(x) ≥ ti), o parˆametro wj ´e zero (pj = 0). Para o intervalo de ti (fi(x) ∈ [tmini , tmaxi ]), existe um par de restri¸c˜oes para cada fun¸c˜ao objetivo. Usualmente, os fatores de pondera¸c˜ao wj e βj s˜ao fixados pelo usu´ario.
◦ Programa¸c˜ao Lexocogr´afica
Nessa abordagem, o usu´ario tem que definir uma ordem relativa ou n´ıveis de priori- dades, sem o uso de pesos para ponderar os objetivos. Assim, a meta definida como primeira prioridade ´e muito mais importante que a definida como segunda.
De forma geral, seja o problema com dois objetivos f1 e f2 representados na Fig. 3.4.
f2 f 1 F B A min f DC min f 2 1 E
Figura 3.4: Programa¸c˜ao lexocogr´afica (Reproduzido de Osyczka (1978)).
Se o objetivo f1 ´e mais importante que f2, minimiza-se o problema com f1 primeiro, ignorando f2. Neste caso, encontram-se solu¸c˜oes m´ultiplas em AB e CD no primeiro n´ıvel da programa¸c˜ao de meta. Da´ı, como existe mais de uma solu¸c˜ao para este problema, procede-se para o segundo n´ıvel de otimiza¸c˜ao, onde f2´e minimizada. A procura ´e limitada entre solu¸c˜oes encontradas no primeiro n´ıvel de programa¸c˜ao. A solu¸c˜ao do segundo n´ıvel da programa¸c˜ao ´e D, que ´e solu¸c˜ao m´ınima de f2 entre todas as solu¸c˜oes em AB e CD. Portanto, a solu¸c˜ao D ´e a solu¸c˜ao principal do problema. ´E interessante notar que se f2 ´e considerada mais importante que f1, ent˜ao a solu¸c˜ao E poder´a ser a ´unica do primeiro n´ıvel de otimiza¸c˜ao e o processo poder´a parar aqui. Nesse caso, a solu¸c˜ao E ser´a declarada como solu¸c˜ao do problema.
3.2. M´etodos para o Tratamento de POMO 39
Segundo Osyczka (1978), a principal limita¸c˜ao dessa abordagem ´e que, quando o n´umero de objetivos ´e grande, ele tende a otimizar prioritariamente os mais importantes.
◦ Programa¸c˜ao de Meta Min-Max
Esta metodologia ´e an´aloga `a programa¸c˜ao de meta ponderada, mas em vez de mini- mizar a soma ponderada dos desvios em rela¸c˜ao `as suas metas, esta deve obedecer a um valor m´aximo de desvio △, escrito na forma de restri¸c˜ao, e este desvio m´aximo ´e minimizado. Resulta um problema de programa¸c˜ao n˜ao-linear dado por:
min △ (3.27) wjpj+ βjnj ≤ △ fj(x) − pj + nj = tj pj, nj ≥ 0