agregação de uma abordagem “win-win” à modelagem multi

AGREGAÇÃO DE UMA ABORDAGEM “WIN-WIN” À MODELAGEM
MULTI-OBJETIVO
Hélcio Vieira Junior
TESE
SUBMETIDA
AO
CORPO
DOCENTE
DA
COORDENAÇÃO
DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS NECESSÁRIOS
PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM ENGENHARIA DE
PRODUÇÃO.
Aprovada por:
______________________________________
Prof. Marcos Pereira Estellita Lins, D.Sc.
______________________________________
Prof. Virgílio José Martins Ferreira Filho, D.Sc.
______________________________________
Prof. Luiz Flavio Autran Monteiro Gomes, Ph.D.
______________________________________
Prof. Michal Gartenkraut, Ph.D.
RIO DE JANEIRO, RJ – BRASIL
DEZEMBRO DE 2003
VIEIRA JUNIOR, HÉLCIO
Agregação de uma Abordagem “WIN-WIN” à
Modelagem Multi-Objetivo [Rio de Janeiro] 2003
VII, 92 p. 29,7 cm (COPPE / UFRJ, M.Sc.,
Engenharia de Produção, 2003)
Tese – Universidade Federal do Rio de
Janeiro, COPPE
1. Metodologia para resolução de problemas
MOLP
2. Algoritmo Afim Escala Primal
3. Pareto Race
I. COPPE / UFRJ
II. Título (série)
ii
À minha amada esposa Nathália,
cujo amor, suporte e compreensão
permitiram que eu alçasse mais
este degrau na vida.
iii
Resumo da Tese apresentada à COPPE / UFRJ como parte dos requisitos
necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
AGREGAÇÃO DE UMA ABORDAGEM “WIN-WIN” À MODELAGEM
MULTI-OBJETIVO
Hélcio Vieira Junior
Dezembro / 2003
Orientador: Marcos Pereira Estellita Lins
Programa: Engenharia de Produção
Este trabalho tem como objetivo propor uma metodologia que auxilie o
Tomador de Decisão (DM) a obter a solução não dominada preferida em problemas de
Programação Linear Multi-Objetivo. Para tanto, a metodologia proposta vale-se de
duas fases. Na primeira fase, um algoritmo inédito de Pontos Interiores baseado no
algoritmo Afim Escala Primal é utilizado. Tal algoritmo possibilita obter a solução não
dominada inicial através de um uma seqüência de pontos localizados no interior do
politopo das restrições. Ao percorrer este caminho, o DM não necessita realizar a
árdua tarefa de estabelecer trade-off’s entre as Funções Objetivo (FO’s). Esta
característica da fase um, na qual todas as FO’s têm seus valores sempre crescentes
a cada iteração, é denominada WIN-WIN. Após a obtenção da solução não dominada
inicial, caso o DM deseje continuar a busca, o método de comprovada eficiência
denominado Pareto Race é utilizado na segunda fase. Um exemplo numérico, no qual
foi estudada a distribuição orçamentária realizada pela Força Aérea Brasileira por suas
Unidades Aéreas, é apresentado com o objetivo de ilustrar a metodologia proposta.
iv
Abstract of Thesis presented to COPPE / UFRJ as a partial fulfillment of the
requirements for the degree of Master of Science (M.Sc.)
AGGREGATING A WIN-WIN APPROACH WITH THE MULTIPLE OBJECTIVE
MODEL
Hélcio Vieira Junior
December / 2003
Adviser: Marcos Pereira Estellita Lins
Department: Production Engineering
The objective of this work is to purpose a methodology that is able to help the
Decision Marker (DM) on the nondominated solution obtainment in Multiple Objective
Linear Programming (MOLP) problems. The proposed methodology uses two phases.
In the first phase, an unpublished Interior Point algorithm that is based in the AffineScaling Primal algorithm is used. Such algorithm obtains the first nondominated
solution through a sequence of points located in the interior of the polytope. Going
through this path, the DM does not have to establish trade off among the Objectives
Functions (OF’s). This characteristic of the phase one, where all the OF’s have their
values always increasing, is called WIN-WIN. After obtaining the first nondominated
solution, in case the DM wishes to continue the search, the efficient method called
Pareto Race is used in the phase two. A numerical example, in which the sharing of the
budget made by the Brazilian Air Force among their Air Units was studied, is presented
in order to illustrate the proposed methodology.
v
ÍNDICE
Capítulo ........................................................................................................... Página
I. Introdução..........................................................................................................1
I.1. Comentários Iniciais ............................................................................1
I.2. Estrutura do Trabalho ..........................................................................3
II. Histórico............................................................................................................4
III. Definições, Notações e Ferramentas ...............................................................7
III.1. Definições e Notações.......................................................................7
III.2. Ferramentas .....................................................................................11
IV. Método Afim Escala Primal.............................................................................14
IV.1. Embasamento de Programação Não Linear.....................................14
IV.2. Algoritmos Afins ...............................................................................24
IV.3. O Algoritmo Afim Escala Primal........................................................25
IV.4. Um Exemplo Numérico.....................................................................29
V. Método Pareto Race........................................................................................32
V.1. Conceito de Não Dominância............................................................32
V.2. Comentários Iniciais Sobre o Método Pareto Race ...........................34
V.3. Função Escalarizante........................................................................35
V.4. O Método Pareto Race......................................................................37
V.5. Um Exemplo Numérico......................................................................39
VI. O Algoritmo Proposto .....................................................................................55
VI.1. Comentários Iniciais .........................................................................55
VI.2. O Algoritmo .....................................................................................57
VI.3. Obtenção do Vetor Viável Inicial.......................................................64
VI.4. Comentários Sobre o Algoritmo........................................................66
VII. Um Exemplo Numérico..................................................................................69
VII.1. Descrição do Problema ...................................................................69
VII.2. Aplicação da Metodologia Proposta ................................................74
VIII. Conclusão ....................................................................................................87
IX. Bibliografia......................................................................................................90
vi
“Para ser grande
sê inteiro, nada teu
exagera ou exclui, ... e
sê todo em cada coisa
põe quanto és no
mínimo que fazes.
Assim em cada lago
a tua lua brilha
porque alta vive!”
Fernando Pessoa
vii
CAPÍTULO I
INTRODUÇÃO
I.1. Comentários Iniciais
“Se existe uma área da ciência de gerenciamento / pesquisa operacional que é
excitante e desafiadora, mas assustadora, com decepções e armadilhas, ela é a
Otimização Multi-Critério. Este campo é fascinante porque ele é claramente uma arte
assim como uma ciência” (Steuer,1989).
Arbel (1993a) propôs o uso de um algoritmo de pontos interiores para a
solução de problemas de Programação Linear Multi-Objetivo – MOLP (Multiple
Objective Linear Programming). Tal algoritmo foi aperfeiçoado diversas vezes pelo
autor (Arbel, 1993b, 1994, 1996, 2001), e permite a obtenção de um ponto localizado
na fronteira não dominada através de uma seqüência de pontos situados no interior do
politopo das restrições. Uma das grandes vantagens, se não a maior, desta
metodologia é que as soluções apresentadas ao Tomador de Decisão – DM (Decision
Maker), tem seus valores sempre crescentes a cada iteração, não sendo necessária a
árdua tarefa de estabelecer trade-offs (vide item V.1) entre as diversas funções
objetivo. Apesar das diversas melhorias implementadas no algoritmo, o mesmo ainda
encontra um óbice: ao atingir a fronteira não dominada, se o DM ainda não estiver
satisfeito com a solução apresentada, o algoritmo não provê meios de continuar a
busca, sendo necessário o reinício de todo o procedimento.
Korhonen e Laakso (1986a, 1986b) propuseram uma abordagem visual na
resolução de problemas MOLP. Esta abordagem foi implementada em um programa
denominado Pareto Race (Korhonen e Wallenius, 1988). Tal algoritmo permitiu a
busca da solução preferida pelo DM, percorrendo toda a fronteira não dominada. Os
autores, porém, não sugeriram nenhum procedimento que auxiliasse a definição de
um ponto de início da busca, o que em problemas de grande instância, isto é,
problemas MOLP com quantidade muito grande de dados a serem tratados, pode ser
muito prejudicial ao DM, visto que a fronteira a ser percorrida é muito extensa. Um dos
próprios autores do Pareto Race (Korhonen et al, 1990) discutiu sobre o problema do
rápido grau de convergência (parada prematura) em métodos interativos nos quais ao
DM são apresentadas apenas soluções não dominadas. Kahneman e Tversky (1979)
sugeriram uma teoria com uma explicação plausível para o problema da parada
1
prematura: pessoas sobrevalorizam as perdas e subvalorizam os ganhos. Em
problemas MOLP de grande instância, mesmo com a abordagem sugerida por
Korhonen e Wallenius (1998), o problema da parada prematura pode vir a ocorrer se o
início da busca na fronteira não dominada não se iniciar em um ponto próximo ao
ponto final preferido pelo DM.
O objetivo deste trabalho é propor um algoritmo para a resolução de problemas
de Programação Linear Multi-Objetivo que agregue as duas abordagens acima
comentadas (pontos interiores e Pareto Race), adicionando os aspectos positivos de
cada uma e eliminando as deficiências inerentes a cada abordagem, quais sejam:
Método
Aspecto
positivo
Aspecto
negativo
Pontos Interiores
Pareto Race
Obtenção de uma solução na fronteira
Possibilidade de vasculhar toda
não dominada que, ou seja a preferida
fronteira não dominada na busca
pelo DM, ou esteja próxima àquela.
da solução preferida pelo DM.
O algoritmo não provê meios de
O algoritmo não provê um ponto
continuar a busca após atingir a
inicial
fronteira não dominada.
solução preferida pelo DM.
de
busca
próximo
à
Resumindo, o algoritmo proposto neste trabalho possibilita obter, via algoritmo
de pontos interiores, uma solução localizada na fronteira não dominada que, ou seja a
preferida pelo DM, ou esteja próxima àquela, e, caso não seja a preferida pelo DM,
que a busca possa ser continuada, vasculhando a fronteira com o método Pareto
Race. Na obtenção da solução inicial localizada na fronteira não dominada, o DM não
é obrigado a realizar a complexa tarefa de estabelecer trade-off’s entre as funções
objetivo, pois os valores das mesmas são sempre crescentes. Após obter a solução
inicial, caso ainda não satisfeito, o DM poderá continuar a busca na fronteira não
dominada, porém, a partir deste ponto, o mesmo deverá sempre estabelecer um tradeoff entre as FO´s, pois para aumentar o valor de uma, obrigatoriamente outra deverá
ter seu valor diminuído.
2
I.2. Estrutura do Trabalho
Este trabalho é organizado como se segue: no capítulo dois, é apresentado um
histórico da abordagem de pontos interiores e dos problemas MOLP; no capítulo três,
são abordadas algumas definições, notações e ferramentas necessárias para o
restante do trabalho; o quarto capítulo discute o método Afim Escala Primal de pontos
interiores; no capítulo cinco, discute-se o método Pareto Race; o capítulo seis trata do
algoritmo proposto por este trabalho; um estudo de caso, no qual o algoritmo proposto
é utilizado para a resolução de um problema MOLP, é discutido no capítulo sete; no
capítulo oito, apresenta-se uma conclusão juntamente com indicações de trabalhos
futuros.
3
CAPÍTULO II
HISTÓRICO
O problema da Programação Linear (PL) consiste na otimização de uma função
matemática conhecida como função objetivo. Esta otimização nada mais é que a
obtenção, ou do maior valor possível (maximização), ou do menor valor possível
(minimização) para a função objetivo. Os valores que as variáveis assumem, ao
otimizarem a função objetivo, devem satisfazer várias outras funções matemáticas
conhecidas como restrições. A união destas restrições forma um conjunto convexo.
Os primórdios da PL datam de 1928, quando John Von Newman publicou o
teorema central da Teoria dos Jogos. Entretanto, foi apenas durante a Segunda
Guerra Mundial que a PL se consolidou. Naquela ocasião, um grupo de cientistas foi
chamado pela Força Aérea Americana para solucionar problemas orçamentários e de
planejamento militar com técnicas matemáticas. Dantzig (1963), um dos cientistas
recrutados, veio a formular o método SIMPLEX em 1947.
A idéia central do método SIMPLEX é percorrer os vértices do politopo formado
pelas restrições até alcançar a solução que otimiza a função objetivo.
O método SIMPLEX reinou absoluto até Khachiyan (1979) criar o Algoritmo das
Elipsóides. Este algoritmo tem como conceito a obtenção de uma trajetória no interior
do politopo das restrições para a busca da solução ótima, diferentemente do método
SIMPLEX, que tem a sua trajetória pelo exterior do mesmo politopo. O método das
Elipsóides resolveu um importante aspecto teórico da PL: ele demonstrou que o
problema da PL pode ser resolvido com um número de operações aritméticas limitado
por um polinômio no tamanho do problema, evidenciando com isto que problemas de
PL não mais seriam classificados apenas como NP e sim no importante sub-conjunto
de NP conhecido como P. Apesar de possuir uma teoria muito importante, o método
das Elipsóides provou ser excessivamente lento com problemas da vida real.
Nos anos compreendidos entre 1979 e 1984, a ciência conviveu com dois
métodos: o método SIMPLEX que possuía complexidade exponencial, mas que para
problemas da vida real tinha desempenho excelente, e o método das Elipsóides, que
possuía complexidade polinomial, mas que era ineficiente para problemas da vida real.
4
Com a publicação de seu algoritmo, Karmarkar (1984) conseguiu baixar muito
a complexidade teórica do método das Elipsóides, ao obter como limite superior para o
número de operações aritméticas O(n3.5 L) .
Inicialmente com Khachiyan (1979), e posteriormente com Karmarkar (1984), o
método de pontos interiores nasceu, vindo trazer nova luz para a área de PL.
No
ano
de
1985,
o
método
Afim
Escala
Primal
foi
redescoberto
simultaneamente por Barnes (1986), Vanderbei et al (1986) e por Cavalier e Soyster
(1985). O método já existia há vinte anos, publicado por Dikin (1967) e era
desconhecido. Este método é uma simplificação radical da abordagem de Karmarkar
(1984).
Como visto acima, nos últimos cinqüenta anos, a PL mono-objetivo foi
exaustivamente estudada. No entanto, métodos de auxílio à decisão mono-objetivo
refletem uma era anterior e mais simples que a vivida atualmente. O mundo tem-se
tornado mais complicado e, com o advento da tecnologia da informação, problemas
importantes da vida real raramente demonstram ter apenas um objetivo. Mais do que
nunca, os DM’s necessitam de ferramentas que os auxiliem na tomada de decisão ao
avaliarem múltiplas alternativas de acordo com múltiplos critérios. A PL mono-objetivo
teve de se adaptar a esta nova realidade, migrando, a partir do início dos anos
setenta, para o que conhecemos como MOLP.
A Tomada de Decisão Multi-Critério - MCDM (Multiple Criteria Decision Making)
é formada pela Análise de Decisão Multi-Atributo (Multiattribute Decision Analysis) e
pela Otimização Multi-Critério (Multiple Criteria Optimization). Enquanto a Análise de
Decisão Multi-Atributo é, freqüentemente, aplicada a problemas com menor número de
alternativas em um ambiente de incerteza, a Otimização Multi-Critério é utilizada em
problemas determinísticos nos quais o número de alternativas é muito grande.
Segundo Steuer (1989), a Análise de Decisão Multi-Atributo tem sido mais aplicada na
resolução de problemas de política pública tais como localização de usinas nucleares,
aeroportos, tipos de programas de reabilitação de drogados, etc..., enquanto a
Otimização Multi-Critério tem sido utilizada em problemas com menos controvérsias
nos negócios e / ou no governo, tais como planejamento de refinarias de óleo,
planejamento da produção de fábricas, seleção de portfólio (carteira de títulos),
gerenciamento ambiental, transportes, etc... A principal ferramenta da Otimização
Multi-Critério é a MOLP.
Em problemas MOLP, a interação com o DM é fundamental, visto a não
existência de uma solução ótima, e sim uma solução preferida pelo DM. O momento
5
em que ocorre a interação com o DM versus a otimização em si, nos permite
classificar os métodos MOLP em três classes: Articulação a priori das preferências (a
priori à otimização); Articulação progressiva das preferências (durante ou em
seqüência com a otimização); Articulação a posteriori das preferências.
Na articulação a priori das preferências, o DM é questionado sobre qual valor o
mesmo atribui a cada função objetivo a ser otimizada. Esta valoração das funções
objetivo é conhecida como função utilidade. Após a obtenção da função utilidade, a
otimização é realizada. O grande óbice desta classe de algoritmos é que, na maioria
absoluta dos casos, o DM não tem conhecimento de tal função utilidade, ou seja, o DM
não sabe qual valor atribuir a cada função objetivo.
Na articulação a posteriori das preferências, a otimização é realizada, e ao DM
são apresentadas todas as soluções não dominadas. O representante mais famoso
desta classe de algoritmos é o SIMPLEX Multi-Objetivo. O maior problema desta
classe de algoritmos é que, em problemas de grande instância, o DM fica perdido em
meio a tantas soluções não dominadas, vindo a ocorrer o problema da parada
prematura comentado anteriormente.
Na articulação progressiva das preferências, o DM interage com o algoritmo à
medida que fornece suas preferências a cada iteração, o que possibilita ao mesmo
(DM) a chegada a uma solução preferida mesmo sem o conhecimento explícito da
função utilidade.
Os algoritmos da classe articulação progressiva das preferências são
conhecidos como algoritmos interativos e são considerados como os melhores e de
interface mais amigável com o DM. Os métodos de pontos interiores e Pareto Race,
assim como a metodologia proposta por este trabalho, pertencem a esta classe.
Os algoritmos interativos se iniciaram com o método STEM proposto por
Benayoun et al (1971). Os métodos que se seguiram ao STEM, e que foram anteriores
aos dos pontos interiores e Pareto Race abordados neste trabalho, foram os propostos
por Geoffrion et al (1972): GDF procedure; Zionts e Wallenius (1976); Steuer (1977):
Interval Criterion Weights; e Steuer (1983): Interactive Weighted Sums. Para uma
excelente abordagem sobre tais métodos, consultar Steuer (1989).
6
CAPÍTULO III
DEFINIÇÕES, NOTAÇÕES E FERRAMENTAS
III.1. Definições e Notações
Veremos a seguir algumas definições e notações utilizadas neste trabalho:
III.1.1. A expressão se e somente se é denotada por sss.
III.1.2. Uma matriz quadrada B é dita singular sss det( B ) = 0 . Se det( B ) ≠ 0 a matriz
B é dita não singular.
III.1.3. A transposta de uma matriz B ∈ R i x j é denotada por B T . A matriz B T é obtida
pela troca das linhas pelas respectivas colunas da matriz B , ou seja:
bi j = bTj i , ∀ i ∈ I e ∀ j ∈ J .
III.1.4. A inversa de uma matriz B ∈ R i x j é denotada por B −1 . A matriz B −1 pré ou pós
multiplicada pela matriz B resulta na matriz identidade:
B −1 B = BB −1 = I
Uma matriz B ∈ R i x j só possuirá inversa se for não singular.
III.1.5. A norma euclidiana de um vetor x ∈ R n é denotada por || x || , e equivale a:
n
|| x || = xT x = (∑ xi2 )
i =1
III.1.6. Uma transformação linear A : R n → R m definida em R n com valores em R m , é
representada por uma matriz A ∈ R m x n .
III.1.7. O espaço imagem de A é definido como:
I ( A) = { y ∈ R m | y = Ax, x ∈ R n }
I ( A) corresponde ao conjunto de todas as combinações lineares das colunas
da matriz A .
7
III.1.8. O espaço nulo de A é definido como:
N ( A) = { x ∈ R n | Ax = 0}
N ( A) corresponde ao conjunto de pontos de R n que são mapeados na
origem.
III.1.9. O rank de uma transformação linear A é representado por r ( A) e corresponde
à dimensão de seu espaço imagem, que é igual ao número de colunas (ou
linhas) linearmente independentes. A matriz é de rank máximo se
r ( A) = min{m, n} .
A menos que o contrário seja dito, trabalharemos sempre em R , com
n
matrizes em R m x n de rank máximo, ou seja, a matriz A possui linhas
linearmente independentes. Caso a matriz A tenha linhas dependentes,
supomos que as redundâncias serão eliminadas de modo a reduzir o número
de linhas a r ( A) .
III.1.10. A matriz p x n , na qual as linhas são os gradientes das p funções objetivo, é
chamada matriz objetivo e é denotada por C .
III.1.11 O conjunto viável de um problema de PL é chamado de espaço de decisão, e é
definido por:
S = {x ∈ R n | Ax = b, x ≥ 0} .
III.1.12 A imagem do espaço de decisão S pela(s) função(ões) objetivo(s) é chamado
de espaço objetivo, e é definido por:
Z = {z ∈ R k | z = Cx, x ∈ S} .
III.1.13. Um ponto x ∈ R n é um ponto interior de um problema de PL sss x ∈ S e
x >0.
III.1.14. Um vetor h ∈ R n é uma direção viável a partir de x ∈ S sss existir λ > 0 tal
que para qualquer λ ∈ [0, λ ], x + λ h ∈ S .
III.1.15. Se uma função tem derivada parcial contínua de primeira ordem em um
conjunto, nós denotamos isto como: f ∈ C 1 . Em geral, se uma função tem
derivada parcial contínua de ordem p , isto é denotado por: f ∈ C p .
8
III.1.16 Se f ∈ C 1 é uma função real em R n , o gradiente de f é definido por:
 ∂f ( x ) ∂f ( x)
∂f ( x) 
,
,...,
∇f ( x ) = 

∂x2
∂xn 
 ∂x1
III.1.17 Se f ∈ C 2 é uma função real em R n , a Hessiana de f em x é definida pela
matriz simétrica n x n:
 ∂ 2 f ( x) 
∇ 2 f ( x) = 

 ∂xi ∂x j 
III.1.18 Fórmula de Taylor: para uma função definida em um intervalo aberto T ⊂ R
diferenciável até a ordem conveniente, pode-se escrever a fórmula de Taylor,
para x + h ∈ T :
f ( x + h) = f ( x ) + ∇f ( x )T h + ... +
1 p
∇ f ( x)T h p + Op ( x, h)
p!
onde:
h p +1
∇ ( p +1) f ( x + θ h) , para algum θ ∈ [0,1] .
O p ( x, h) =
( p + 1)!
A expressão acima ( O p ( x, h) ) serve para limitar o erro da aproximação
desejada. Por exemplo: se desejamos a aproximação linear de uma função,
basta pegarmos os dois primeiros termos da fórmula de Taylor e teremos
como erro desta aproximação linear o resultado da expressão O p ( x, h) , com
o valor de p = 1 ; da mesma forma, para a aproximação quadrática, basta
pegarmos os três primeiros termos da fórmula de Taylor e utilizarmos um
p = 2 na expressão do erro da aproximação.
III.1.19 O complemento ortogonal de um subespaço U = {x | x = Av, v ∈ R n } é
{ y | yA = 0} . A notação disto é y ⊥ U .
9
III.1.20 MOLP – Multiple Objective Linear Program – Programação Linear MultiObjetivo: é definida como:
max {C1 x = z1}
max {C2 x = z2 }
...
max {C p x = z p }
SA.: Ax ≤ b
x≥0
ou, simplificadamente:
max z = Cx
SA.: x ∈ S
III.1.21 Métrica L p : Uma métrica em R n é a função distância que associa a cada par
de vetores x, y ∈ R n um escalar || x − y || ∈ R e é definida por:
1
 n
 p
|| x − y || p =  ∑ | xi − yi | p 
p ∈ {1, 2,3,...}
 i =1

|| x − y ||∞ = Max {| xi − yi |}
i =1,2, ... , n
A métrica L∞ é chamada de métrica de Tchebycheff ou distância de
Tchebycheff.
III.1.22 A notação que será utilizada para o tableau do SIMPLEX será a seguinte:
Variaveis
Variaveis básicas
cj
( AB )−1 A
b
( AB ) −1 b
c − ( cB )T ( AB ) −1 A −(cB )T ( AB ) −1 b
10
III.2. Ferramentas
A seguir algumas ferramentas que terão utilidade no decorrer do trabalho são
esplandas:
III.2.1. Um vetor v ∈ R n é ortogonal a I ( AT ) sss v ∈ N ( A) .
o
Prova: v ⊥ I ( AT ) sss v ⊥ AiT , i = 1, ... , m , onde Ai representa as linhas
de A . Esta última relação é equivalente a Ai v = 0, i = 1, ... , m , ou Av = 0 ,
o que completa a prova.
Deste fato conclui-se que R n é a soma direta dos subespaços N ( A) e I ( AT ) ,
isto é, dado qualquer vetor w ∈ R n , ele pode ser escrito como:
w = wN + wI , onde wN ∈ N ( A) e wI ∈ I ( AT ) .
III.2.2. A matriz AAT é não singular.
o
Prova:
Por
absurdo
suponha
que
para
algum
y ≠ 0, AAT y = 0 .
Multiplicando esta expressão à esquerda por y T :
y T AAT y = 0, ou ( AT y )T ( AT y ) = 0 .
Esta última expressão é equivalente a || AT y || = 0 , ou ainda a AT y = 0 . Isto
é impossível uma vez que as colunas de
AT
são linearmente
independentes (veja III.1.9), completando, assim, a prova.
III.2.3. wI = AT ( AAT ) −1 Aw .
o
Prova: Sabemos que o vetor w pode ser decomposto em:
w = wN + wI
Como wI ∈ I ( AT ) , existe y ∈ R m tal que wI = AT y , e então:
w = wN + AT y .
Multiplicando à esquerda pela matriz A :
Aw = AwN + AAT y
11
Como, por definição, AwN = 0 (vide III.1.8):
Aw = AAT y
E, como a matriz AAT é não singular (vide III.2.2), a mesma possui uma
inversa, que pré- multiplicará a expressão anterior:
( AAT ) −1 Aw = ( AAT )−1 AAT y
( AAT ) −1 Aw = I y
.
( AAT ) −1 Aw = y ou y = ( AAT ) −1 Aw
Substituindo a expressão acima em wI = AT y completamos a prova.
III.2.4. wN = Pw , onde P = I − AT ( AAT )−1 A .
o
Prova: w = wN + wI pode ser escrito como wN = w − wI .
Substituindo wI = AT ( AAT ) −1 Aw na expressão acima temos:
wN = w − AT ( AAT )−1 Aw
Colocando w em evidência, completamos a prova:
wN = [ I − AT ( AAT )−1 A]w .
A matriz P é a matriz de projeção sobre o espaço nulo de A .
III.2.5. Se x é um ponto interior, a direção h ∈ R n é viável a partir de x sss h ∈ N ( A) .
o
Prova: Se h ∈ R n é viável a partir de x , então x + h ∈ S .
A expressão acima é idêntica a:
A( x + h) = b .
Aplicando a propriedade distributiva: Ax + Ah = b .
Como x é um ponto interior, Ax = b , logo Ah = 0 , o que é equivalente a
h ∈ N ( A) .
12
III.2.6. Considere um ponto x ∈ S e uma direção h ∈ R n viável a partir de x , então:
‰
Se h ≥ 0 então x + λ h é viável para qualquer λ ≥ 0 ;
‰
Senão, o maior valor de λ tal que x + λ h ∈ S é dado por:
λ = min{−
o
xi
| hi < 0, i = 1, ..., n}
hi
Prova: Como h ∈ N ( A) (vide item III.2.5), então para qualquer λ ∈ R
tem-se que A( x + λ h) = b .
Se h ≥ 0 , então para qualquer λ ≥ 0, x + λ h ≥ 0 , demonstrando a primeira
parte.
Se alguma componente de h é negativa, então o maior λ vai ser
determinado pela primeira entre essas componentes a anular-se. A cada
componente i = 1, ..., n associa-se um valor:
λ i = sup{λ | xi + λ hi ≥ 0}
Se hi < 0 então xi + λ i hi = 0 e conseqüentemente λ i = −
xi
. O maior
hi
passo agora que garante a viabilidade é min i =1, ... ,n λ i , o que é equivalente à
expressão: λ = min{−
xi
| hi < 0, i = 1, ..., n} .
hi
13
CAPÍTULO IV
MÉTODO AFIM ESCALA PRIMAL
IV.1. Embasamento de Programação Não Linear
Algoritmos para a resolução de problemas de PNL (Programação Não Linear)
definem, a cada iteração, um problema fácil de ser resolvido. Problemas fáceis são
aqueles que possuem tanto a região viável como a função objetivo simples. Este
problema fácil é obtido tomando uma aproximação linear da função objetivo do
problema original de PNL em torno do último ponto viável disponível, e escolhendo
uma região fácil sobre a qual essa aproximação é minimizada. Esta região fácil
recebe o nome de região de confiança.
Um dos problemas considerados fáceis é a minimização de uma função linear
em uma bola:
Minimizar {g T h | || h || ≤ 1}
Cauchy (1821) provou em seu trabalho, que:
‰
| xy | ≤ || x ||.|| y || (desigualdade de Cauchy-Schwarz); e
‰
| xy | = || x ||.|| y || sss x = α y para algum escalar α .
Obteremos, caso os vetores x e y sejam não nulos, que:
xy
| xy |
≤ 1 ou −1 ≤
≤1
|| x || . || y ||
|| x || . || y ||
Logo, a solução para o problema de minimização em uma bola é obtida
imediatamente:
g T h ≥ − || g ||.|| h ||
Como a igualdade só é valida se h = α g , o mínimo da função acima ocorrerá para
α = −1 , ou seja, se g e h forem colineares em sentidos opostos. A fim de
preservar a restrição || h || ≤ 1 , deveremos normalizar o vetor resultante h :
h=−
g
|| g ||
Isto é chamado de direção de máximo declive.
14
Algoritmos para o problema:
Min f ( x)
SA.: x ∈ R n
geram, a partir de um ponto inicial x0 , sucessivamente, os pontos:
xk +1 = xk + λ h, k ≥ 0
nos quais o ponto xk +1 é obtido através de um deslocamento (passo) de tamanho
λ na direção h .
Como nos interessam direções descendentes, i.e., direções h de tal modo que:
f ( xk + h) < f ( xk )
e, como os seguintes problemas são equivalentes:
Min f ( x)
SA.: x ∈ R
n
≡
Min f ( x + h)
SA.: h ∈ R n
a solução ideal pode ser obtida calculando-se a direção h através de:
Min f ( x + h)
SA.: h ∈ R n
Dado um ponto x ∈ R n , no qual a função f ( x + h) é diferenciável, a sua
aproximação linear pela Fórmula de Taylor (vide III.1.18) é:
f ( x + h ) ≅ f ( x ) + ∇ f ( x )T h
Como o termo
f ( x ) é constante (em relação a h ), podemos eliminá-lo,
obtendo o seguinte sub-problema:
Min ∇f ( x)T h
SA.: h ∈ R n
“Observe que, devido à linearidade da função objetivo relativamente a h , a não
ser que x seja um ponto estacionário ( ∇f ( x ) = 0 ), este problema não possui
solução finita. Ora, queremos apenas uma direção, seu comprimento não
importando, visto que se determinará ulteriormente um deslocamento sobre ele a
partir de x (o passo λ ). Pode-se assim definir o sub-problema de obtenção de
uma direção:” (Oliveira, 1989)
15
Min ∇f ( x)T h
SA.: || h ||≤ 1
h ∈ Rn
Vemos que este problema nada mais é do que a minimização de uma função
linear sobre uma bola, com solução conhecida: a direção de máximo declive:
h=−
∇f ( x )
|| ∇f ( x) ||
Gonzaga (1989) menciona que “este resultado é bem conhecido, e é
fundamental em otimização: a direção de máximo declive de uma função é a
direção oposta ao gradiente. Isto foi descoberto por Cauchy na primeira metade do
século passado, e foi na realidade a motivação para a formalização do conceito de
gradiente.
A construção é ilustrada na figura 4.1: uma função não linear é representada
por suas curvas de nível. A aproximação linear tem curvas de nível retas, e x + h é
o minimizador da aproximação linear na bola. A direção de máximo declive é h ”.
x
x+h
Figura 4.1
A minimização na bola gera uma direção normalizada. Não é mandatória e,
muitas vezes, não é apropriada a utilização de direções normalizadas em
algoritmos de busca. Utiliza-se, em vez disto, como direção de máximo declive:
h = − g = −∇f ( x)
A utilização da direção de máximo declive pode ser observada através do
seguinte exemplo:
Max Z = 2 x1 + x2
S . A.: x ≥ 0
16
(4.1)
Na figura 4.2 abaixo, temos o ponto inicial arbitrário aT = ( 5, 000 3, 000 ) e o
vetor gradiente cT = ( 2,000 1, 000 ) plotados, assim como a região de confiança
(a maior circunferência centrada no ponto inicial restrita ao primeiro quadrante) e
as curvas de níveis correspondentes aos valores que a FO assume:
x2
Z = 13, 000
Z = 6, 292
c
a
b
x1
Figura 4.2
O ponto resultante da minimização da FO através da direção de máximo declive é
bT = ( 2,317 1, 658 ) .
Observemos que a utilização da direção de máximo declive proporcionou um
considerável progresso na minimização da FO, porém, tal progresso foi muito mais
acentuado no eixo horizontal do que no eixo vertical. Um progresso maior poderia ser
alcançado se o ponto inicial estivesse na mesma distância de todos os eixos. Isto
poderá ser facilmente conseguido através de uma operação de mudança de variáveis
(mudança de escala): h = D −1h , onde D = diag ( d1 , ... , d n ) e di > 0, i = 1, ..., n .
Realizando a mudança de escala no problema (4.1) temos: o ponto a é obtido
−1
 5,000 0, 000   5, 000   1, 000 
através de a = D a = 
, e o vetor gradiente c
 
=
 0, 000 3, 000   3, 000   1, 000 
−1
 5, 000 0, 000  2, 000   10, 000 
. Observemos na figura 4.3 o

=
 0, 000 3, 000  1, 000   3, 000 
através de c = Dc = 
problema anterior no espaço escalado:
17
x2
c
a
b
x1
Figura 4.3
O ponto obtido minimizando o novo gradiente c através da direção de máximo
declive foi: b = ( 0, 042
T
0, 713) . Re-escalando o ponto b novamente para o espaço
T
T
original, temos: b = ( Db) = ( 0, 211 2,138 ) . Podemos observar a mecânica deste
procedimento no espaço original através da figura 4.4 abaixo:
x2
Z = 13, 000
Z = 6, 292
Z = 2, 560
c
a
b
b
x1
Figura 4.4
18
Notemos que, através da mudança de escala, conseguimos uma redução
maior no valor da FO. O que a mudança de escala realmente fez foi realizar a
minimização utilizando como região de confiança, no lugar de uma bola, um elipsóide
com eixos coincidentes com os eixos coordenados. Chamaremos esta figura de
elipsóide simples.
Neste caso, o elipsóide é determinado por uma forma quadrática com hessiana
diagonal:
hT DDh ≤ 1, onde D = diag (d1 , ... , d n ) e di > 0, i = 1, ..., n .
Os eixos coincidem com os eixos coordenados e seus comprimentos valem 1
di
.
Olhando o problema no sentido oposto, i.e., em vez de transformar a região viável
original (bola) em um elipsóide, iremos transformar o elipsóide em uma bola. O
problema de minimização de uma função linear nesta região:
min g T h
SA.: hT DDh ≤ 1
é facilmente resolvido por uma mudança de variáveis (mudança de escala) h = Dh , o
que resulta em:
min g T D −1 h
T
SA.: h h ≤ 1
A mudança de escala transformou a elipsóide em uma bola, cuja solução é
conhecida: a direção de máximo declive.
Logo, a solução para o problema modificado é:
h=−
g
, onde g = D −1 g
|| g ||
No espaço original, a direção resultante é:
h = D −1 h
h = − D −1
D −1 g
|| D −1 g ||
Que, sem a normalização, fica:
h = − D −2 g
19
Esta estratégia, segundo Arbel (1993c), pode ser definida como: “o politopo original
é transformado a cada iteração em outro politopo, no qual o passo corrente é dado, e
então re-transformado novamente em seu formato original no fim daquele passo”.
Os problemas fáceis vistos acima (minimização de uma função linear em uma bola
mxn
e em um elipsóide) quando restritos a um hiperplano, isto é, Ax = b , onde A ∈ R ,
correspondem às soluções anteriores projetadas no nulo de A :
‰
Minimização em uma bola:
Min g T h
SA.: Ah = 0
|| h ||≤ 1
o problema acima tem como solução:
h=−
o
gN
, onde g N = Pg
|| g N ||
Prova: Como g = g N + g I , onde g N ∈ N ( A) e g I ⊥ N ( A) , podemos
escrever g T h como:
g T h = g TN h + g TI h
Para qualquer direção viável h ∈ N ( A) , temos que g TI h = 0 e, dessa
forma:
g T h = g TN h
O problema original é equivalente a minimizar g TN h em uma bola de
raio unitário, com solução conhecida:
gN
.
|| g N ||
Sem a normalização, teremos como solução:
h = − g N = − Pg
Dado um ponto x ∈ R n , no qual a função f ( x + h) é diferenciável, a
minimização de sua aproximação linear f ( x) + ∇f ( x)T h na bola de raio
unitário restrita a um hiperplano é (sem normalização):
h = − P∇f ( x)
20
‰
Minimização em uma elipsóide:
min g T h
SA.: Ah = 0
hT DDh ≤ 1
que com a mudança de escala h = Dh fica:
T
min g h
SA.: Ah = 0
|| h ||≤ 1
onde g = D −1 g e A = AD −1
A solução não normalizada é dada pela projeção no nulo de A ( PA ) :
h = − PA g
que, no espaço original, equivale a:
h = − D −2 PA g
Dado um ponto x ∈ R n , no qual a função f ( x + h) é diferenciável, a
minimização de sua aproximação linear f ( x) + ∇f ( x)T h no elipsóide
restrito a um hiperplano é (sem normalização):
h = − D −2 PA∇f ( x )
A idéia exposta acima pode ser mais facilmente observada através da figura
4.5 abaixo, onde o vetor gradiente cT = (1 1 2 ) e a projeção do mesmo (linha
pontilhada) no hiperplano x1 + x2 + x3 = 1 estão plotados:
x2
1
c
x3
1
1
Figura 4.5
21
x1
Veremos, a seguir, o mais antigo e um dos mais importantes algoritmos para
PNL: o método de Cauchy. Este método também é conhecido por método de
máximo declive e utiliza a cada iteração a direção de máximo declive:
Dado um ponto inicial x 0 :
•
k := 0
•
Repetir:
o
h := −∇f ( x k ) ⇒ Achar uma direção de busca através da direção de
máximo declive.
o
Fazer uma busca unidirecional a partir de x k na direção h , obtendo
solução λ ⇒ Tal busca unidirecional objetiva encontrar o tamanho
do passo a ser dado na direção h , de modo a preservar que:
f ( xk + λh) < f ( xk )
o
x k +1 := x k + λ h
o
k := k + 1
o
Se || h ||< ε , para uma precisão ε dada: parar o algoritmo.
O método de Cauchy em um problema restrito a um hiperplano Ax = b é
idêntico ao algoritmo acima, sendo a direção de busca h := − P∇f ( x k ) .
O método de Cauchy restrito a um hiperplano com mudanças de escala
(regiões
de
confiança
elipsoidais)
utiliza
como
direção
de
busca
h := − D −2 PA∇f ( x k ) e é o algoritmo no qual o método Afim Escala Primal se baseia.
Um ponto que merece esclarecimentos é a busca unidirecional: devido ao fato
de que iremos trabalhar com funções objetivo lineares e de que as curvas de níveis
de funções lineares são retas, podemos concluir que uma direção h que seja
inicialmente descendente, será sempre descendente, diferentemente do que
ocorre com funções não lineares. Tal fato pode ser observado na figura 4.6 abaixo:
22
h1
Z1 = 20
Z 2 = 20
C
D
h2
B
E
Z1 = 10
Z 2 = 10
A
Figura 4.6
onde temos plotadas as curvas de níveis de duas FO’s: a da esquerda ( Z1 ) uma
FO não linear e a da direita ( Z 2 ) uma FO linear. Observemos que na FO não
linear, partindo do ponto A na direção h1 , os valores que a FO assume são
decrescentes até o ponto C , quando então passam a ser crescentes. No ponto B ,
temos o mínimo valor que a FO atinge a partir de A na direção h1 . Na FO linear,
temos que, partindo do ponto D na direção h2 , o valor da função objetivo sempre
decresce. O ponto E é o ultimo ponto que, partindo de D na direção h2 , ainda
permanece dentro da região viável.
Como em FO’s lineares devemos apenas nos preocupar em não sairmos da
região viável, uma boa busca unidirecional para problemas lineares pode ser o
teste da razão visto no item III.2.6.
23
IV.2. Algoritmos Afins
Algoritmos Afins são os algoritmos que geram pontos no conjunto viável S , em
contraste com o algoritmo de Karmarkar (1984), que gera pontos em uma região
maior (o cone gerado por S ).
Estes algoritmos realizam buscas em direções de máximo declive sobre o
conjunto viável S e utilizam mudanças de escala, o que é o mesmo que utilizar
regiões de confiança elipsoidais.
A escolha da direção da busca e a determinação de um novo ponto por um
processo de busca unidirecional é que determinarão em qual sub-classe dos
Algoritmos Afins o algoritmo em questão se enquadrará.
Os Algoritmos Afins são divididos em:
•
Algoritmo Afim Escala Primal;
•
Algoritmo Afim Escala Dual;
•
Método de Barreiras; e
•
Algoritmo Afim Polinomial.
Para este trabalho foi escolhido o Algoritmo Afim Escala Primal. O motivo da
escolha não foi por este ser o melhor em sua classe, e, sim, pela simplicidade de
compreensão e de implementação.
Para uma abordagem mais profunda sobre os demais algoritmos da classe
Algoritmos Afins, consultar Gonzaga (1989).
24
IV.3. O Algoritmo Afim Escala Primal
Este algoritmo é o mais simples de sua classe. “Foi publicado em russo por
Dikin (1967) e permaneceu desapercebido até recentemente, quando foi
redescoberto por várias pessoas independentemente. Um fato interessante é que
a demonstração de convergência assintótica publicada por Dikin (1974) é melhor
que as posteriores, pois tem menos hipóteses.
O Algoritmo Afim Escala Primal usa como critério a própria função custo, e
necessita de um procedimento heurístico na determinação do passo” (Gonzaga,
1989).
Vale mencionar também que, segundo Gonzaga (1989), o algoritmo de Dikin
(1967) era conhecido e utilizado por Karmarkar (1984) anteriormente à publicação
de seu método de pontos interiores.
Assumiremos que um ponto inicial interior x0 é disponível e que o conjunto
viável é limitado.
Consideraremos o problema de programação linear na sua forma padrão
descrita abaixo:
min cT x
SA.: Ax = b
x≥0
onde x ∈ R n , b ∈ R m e a matriz A tem dimensão m x n.
O algoritmo inicia seu processo interativo de uma solução x0 que é tanto
interior quanto viável; isto é:
Ax0 = b, x0 > 0
Os passos do algoritmo procuram achar um vetor h , que mova da solução
corrente em uma direção decrescente para uma nova solução xnew , enquanto
mantém a viabilidade; isto é:
Axnew = b
cT xnew ≤ cT x0
25
Sendo a relação entre as soluções corrente e nova:
xnew = x0 + h
concluímos que:
Ah = 0
(4.2)
cT h ≤ 0
(4.3)
A condição (4.2) requer que o vetor h esteja no nulo de A . Para que isto
ocorra, utilizaremos o operador de projeção visto no item III.2.4. :
P = I n − AT ( AAT )−1 A
Para a condição (4.3), utilizando como direção de busca h = − Pc , observamos
que:
cT h = −cT Pc = −cT P 2 c = − || Pc ||2 ≤ 0
Isto só é válido devido ao fato do operador de projeção P ser simétrico e
2
idempotente ( P = P ).
Como visto anteriormente, a região de confiança mais apropriada é a elipsóide,
e a matriz escalarizante D é definida através da seguinte matriz n x n:
D = diag ( xi1 , xj2 ,..., xjn )
onde xii é o i ésimo componente da solução corrente x0 .
Utilizando a transformação:
x1 = D −1 x0
nós transformamos a região de confiança elipsoidal em uma bola.
Esta operação (mudança de escala) converte o problema original para o
seguinte problema escalado:
min c1T x1
SA.: A1 x1 = b
x1 ≥ 0
onde A1 = AD e c1 = Dc
26
Como a região de confiança do problema acima foi transformada de um
elipsóide restrito a um hiperplano em uma bola restrita a um hiperplano, a direção
de busca, como visto anteriormente, é dada por:
h := − P∇f ( x k )
Projetando o gradiente da função objetivo (o vetor de custo escalado c1 ) no
espaço nulo de A1 obtemos o vetor h1 :
T
T −1
h1 = − Pc
1 1 = −[ I n − A1 ( A1 A1 ) A1 ] c1
= −[ I n − AT DT ( ADAT DT )−1 AD]Dc
= − D[ I n − AT ( AD 2 AT )−1 AD2 ]c
= − D[c − AT ( AD 2 AT )−1 AD2 c ]
e utilizando a relação entre o espaço escalado e o espaço original dada por:
h = Dh1
temos que o vetor h no espaço original é dado por:
h = − D 2 [c − AT ω ]
onde ω = [( AD 2 AT ) −1 AD 2 c ]
(4.4)
sendo ω a estimativa do vetor dual.
A nova solução será dada por:
xnew = x + ρ λ h
sendo : 0 < ρ < 1
 x(ik −1)

λ = min − i , ∀ hki < 0, 1 ≤ i ≤ n 
 hk

k = nº da iteração
(4.5)
Conforme abordado no item III.2.6, o teste da razão mede o maior comprimento
do passo até alguma variável anular-se. O tamanho do passo que previne a
violação das restrições é a variável λ . A variável ρ é usada para especificar a
proporção do tamanho do passo em relação com o tamanho máximo possível do
passo. Para podermos continuar o processo nas demais iterações, é necessário
que o ponto resultante da iteração corrente esteja no interior do ortante, isto é, seja
interior (veja III.1.13). Para tanto, este algoritmo toma um passo um pouco menor
que λ (que zeraria alguma componente do vetor, fazendo com que o ponto xnew
27
ficasse localizado na fronteira do politopo, não sendo então um ponto interior),
reduzido por um fator heurístico ρ , da ordem de 80%. Se o ponto resultante não
for interior, i.e., alguma das suas componentes for nula, a matriz D não será
inversível, o que impede a continuidade do processo iterativo.
O mecanismo de parada do algoritmo será quando a norma do vetor h ficar
menor que uma precisão dada:
gap = || h || ≤ precisão
Este algoritmo, segundo Gonzaga (1989), tem sido utilizado para a resolução,
com uma precisão de dez casas decimais, de problemas com milhares de
restrições e variáveis em cerca de trinta iterações.
28
IV.4. Um Exemplo Numérico
Consideremos o seguinte problema:
Max 2 x1 + x2
SA.: − 4 x1 + 5 x2 ≤ 20
2 x1 + 7 x2 ≤ 49
8 x1 + 15 x2 ≤ 120
13x1 + 9 x2 ≤ 117
x1 , x2 ≥ 0
cuja solução ótima é o vértice (0,000; 9,000).
A região viável do problema está diagramada na figura 4.7:
x2
x1
Figura 4.7
Reproduziremos, a seguir, a primeira iteração do problema pelo método de
pontos interiores Afim Escala Primal:
‰
Utilizando como ponto inicial o vetor:
x 0 = (1, 000 1, 000 19, 000 40, 000 97, 000 95, 000 )
T
‰
 −4, 000 5, 000
 2, 000 7, 000
Faremos A = 
 8, 000 15, 000

 13, 000 9, 000
1, 000
0, 000
0, 000
0, 000
29
0, 000
1, 000
0, 000
0, 000
0, 000
0, 000
1, 000
0, 000
0, 000 
0, 000
;
0, 000
1, 000 
‰
Faremos cT = ( −2, 000
‰
 1, 000
 0, 000

 0, 000
Faremos D = 
 0, 000
 0, 000

 0, 000
‰
Como:
−1, 000 0, 000 0, 000 0, 000 0, 000 ) ;
0, 000 0, 000 0, 000 0, 000 0, 000 
1,000 0, 000 0,000 0, 000 0, 000
0, 000 19, 000 0,000 0, 000 0, 000
;
0, 000 0, 000 40, 000 0, 000 0, 000
0, 000 0, 000 0,000 97, 000 0, 000
0, 000 0, 000 0,000 0, 000 95, 000 
h = − D 2 [c − AT ω ]
onde ω = [( AD 2 AT ) −1 AD 2 c ]
‰
 0,008 
 -0,006
Temos: ω = 
;
 -0,003

 -0,004 
‰
 1,883 
 0,918

 2,944
Temos: h = 
;
 -10,189
 -28,828

 -32,737 
‰
Como:
xnew = x + ρ λ h
sendo : 0 < ρ < 1
 x(ik −1)

, ∀ hki < 0, 1 ≤ i ≤ n 
i
 hk

λ = min −
k = nº da iteração
‰
Temos: λ = min
{h
1
1
> 0; h12 > 0; h13 > 0; 3,926; 3,365; 2,902} = 2,902 ;
30
‰
E, utilizando um ρ = 0,800 , temos: xnew
 5,371 
 3,130

 25,834
.
=
16,346

 30,076

 19,000 
Os valores da variável xnew nas demais iterações está explicitado na tabela
abaixo:
0
1
2
3
4
5
6
x1
1,000
5,371
6,861
7,901
8,747
8,942
8,978
8,995 8,998 9,000
x2
1,000
3,130
2,667
1,503
0,301
0,060
0,027
0,005 0,003 0,000
x3
19,000 25,834 34,109 44,088 53,484 55,466 55,778 55,952 55,978 56,000
x4
40,000 16,346 16,607 22,676 29,402 30,696 30,856 30,973 30,986 31,000
x5
97,000 30,076 25,103 34,245 45,516 47,565 47,773 47,962 47,978 48,000
x6
95,000 19,000 3,800
0,760
0,585
0,217
0,043
7
8
Iteração
9
0,021 0,004 0,000
Tabela 4.1
O valor de ρ foi mantido em ρ = 0,800 até um gap menor que 1, 000e −4 ,
quando foi mudado para ρ = 1, 000 (no nosso exemplo na 8ª iteração).
Na figura 4.8, temos a região viável e os valores de xnew nas diversas iterações
plotados:
x2
x1
Figura 4.8
31
CAPÍTULO V
MÉTODO PARETO RACE
V.1. Conceito de Não Dominância
Como visto em III.1.20, problemas MOLP têm a seguinte forma:
max z = Cx
SA.: x ∈ S
À exceção do caso em que exista um ponto na região viável S que maximize
simultaneamente todas as funções objetivo, sempre teremos que vasculhar o
espaço de tradeoffs ou espaço de trocas existente entre as diversas funções
objetivo. Ilustraremos isto com o seguinte exemplo:
Max x1
Max x2
(5.1)
SA.: 2 x1 + x2 ≤ 10
x1 , x2 ≥ 0
x2
figura 5.1
x1
Este problema, diagramado na figura 5.1, não possui um ponto que maximize
as duas funções objetivo simultaneamente, pois o ponto ( 5, 000
32
0, 000 ) maximiza
a FO1 com o valor 5,000, e o ponto ( 0, 000 10, 000 ) maximiza a FO2 com o valor
10,000. Logo, o DM possui um espaço de trocas entre as duas funções objetivo,
que, no nosso exemplo, está situado na linha que une os dois pontos de máximo
individuais.
No nosso exemplo, é fácil verificar que o ponto (1, 000
7, 000 ) , que possui
como valores das FO1 e FO2, respectivamente, 1,000 e 7,000, tem valores das
FO1 e FO2 menores que de algum outro ponto [por exemplo: o ponto
(1, 250
7, 500 ) , com valores de 1,250 e 7,500 para as FO1 e FO2]. O ponto
(1, 000
7, 000 ) é chamado de dominado, pois possui valores das funções objetivo
menores que outro ponto viável; o ponto
(1, 250
7, 500 ) é chamado de não
dominado, pois não existe outro ponto viável que possua valores de todas as
funções objetivo maiores ou iguais e pelo menos um maior que os seus. Podemos
formalizar este conceito como:
o
O ponto x1 domina x 2 sss:
z [x11 ,x12 ,...,x1n ] ≥ z [x12 ,x22 ,...,x 2n ] para todo z|z ∈ C , e
z [x11 ,x12 ,...,x1n ] > z [x12 ,x22 ,...,x2n ] para algum z|z ∈ C .
o
Um ponto x 3 é chamado de não dominado se não existir outro ponto x 4
que domine x 3 .
O conjunto formado por todos os pontos não dominados é chamado de
Fronteira Não Dominada.
Partindo do ótimo individual da FO1 ( 5, 000
0, 000 ) , para aumentar o valor da
FO2 de zero para 7,500, tivemos que diminuir o valor da FO1 de 5,000 para 1,250;
continuando do ponto (1, 250
( 0, 000
7, 500 ) para o ponto do ótimo individual da FO2
10, 000 ) , para aumentar o valor da FO2 de 7,500 para 10,000, tivemos
que diminuir o valor da FO1 de 1,250 para zero: isto é o chamado tradeoff (ou
troca), pois para aumentar uma FO, obrigatoriamente deveremos diminuir outra.
Observemos que os pontos ( 5, 000
0, 000 ) , (1, 250 7, 500 ) e ( 0, 000 10, 000 )
são todos não dominados.
É de imediata conclusão o fato de que os únicos pontos que interessam ao DM
são os localizados na fronteira não dominada.
33
V.2. Comentários Iniciais Sobre o Método Pareto Race
“A idéia deste método [como descrito em Korhonen e Laakso (1986a)] é
interativamente projetar um segmento de linha aberto do espaço objetivo na
superfície não dominada de Z . Esta projeção na superfície não dominada é obtida
utilizando uma Função Escalarizante (Achievement Scalarizing Function) e
programação paramétrica do RHS (Right Hand Side). O método antecipa o uso da
computação gráfica na apresentação interativa da solução. O método é designado
para o seguinte problema de Programação Linear / Não Linear Multi-Objetivo:
max { f1 ( x ) = z1 }
max { f 2 ( x ) = z2 }
...
max { f k ( x ) = z k }
SA.: x ∈ S
Se a função utilidade do DM é pseudo-côncava, e S é formado por restrições
lineares e é limitado, a necessária e suficiente condição existe para determinar se
um dado ponto é ótimo.” (Steuer, 1989)
34
V.3. Função Escalarizante
O termo Função Escalarizante (Achievement Scalarizing Function) foi retirado
do trabalho de Wierzbicki (1980, 1982, 1983). Das diversas funções escalarizantes
propostas no estudo de Wierzbicki, existem aquelas que minimizam a distância a
um ponto de referência. Este ponto de referência representa os níveis que o DM
aspira para cada função objetivo, ou seja, os valores que o DM gostaria que cada
FO atingisse, mesmo que tais valores não sejam viáveis.
O Pareto Race utiliza, como função escalarizante, uma variação da distância
de Tchebycheff (vide III.1.21):
|| x − y ||∞ = Max {| xi − yi |}
i =1,2, ... , n
Utilizemos como ponto de referência no espaço objetivo o ponto b ∈ R k . Este
ponto pode ou não ser viável, isto é, pertencer ou não a Z . Façamos w um vetor
de pesos. A função escalarizante tipo Tchebycheff é dada por:
b − Cj x 
s (b, x, w) = Max  j

 w j 
Wierzbicki (1980, 1982, 1983) provou que a minimização da função
escalarizante tipo Tchebycheff acrescida de uma pequena perturbação, nos leva a
uma solução não dominada:
p


bj − C j x 
Min s (b, x, w) = Min  Max 
−
C
x
ε
 ∑ k

k =1
 w j 


SA.: Ai x ≤ bi , i ∈ R
x≥0
onde, ε é um escalar muito pequeno maior que zero, i ∈ R o conjunto das m
metas inflexíveis (restrições) e j ∈ G o conjunto das p metas flexíveis (funções
objetivo).
35
Para melhor compreensão da função escalarizante, vejamos o problema MOLP
da figura 5.2, que é idêntico ao problema (5.1) anterior. Se tomarmos o ponto
( 2, 000
3, 000 ) como vetor de aspirações e
( 2, 000
1, 000 ) como vetor de
pesos, obteremos, com a função escalarizante tipo Tchebycheff, como resposta o
ponto
( 3, 200
3, 600 ) , que está localizado na fronteira não dominada. Se
tomarmos o ponto ( 4, 000 8, 000 ) como vetor de aspirações e o vetor de pesos
(1, 000
1, 000 ) , obteremos, com a mesma função escalarizante tipo Tchebycheff,
o ponto ( 2, 000
6, 000 ) como resposta.
x2
x1
figura 5.2
Observemos que o vetor de pesos w , na verdade, nada mais é do que a
direção com que o vetor de aspirações é projetado na fronteira não dominada.
36
V.4. O Método Pareto Race
No lugar de projetar o vetor de aspirações b no conjunto de soluções não
dominadas N , pode-se projetar a semi-reta b + td em N , onde t é a velocidade
ou tamanho do passo, e d a direção, obtendo como função escalarizante:
p


 b j + td j − C j x 
ε
Min s (b, x, w) = Min  Max 
−
Ck x

∑

wj
k =1




SA.: Ai x ≤ bi , i ∈ R
x≥0
Ao introduzir uma variável y ∈ R , podemos reescrever a formulação acima
como:
p


Min s (b, x, w) = Min  y − ε ∑ Ck x
k =1


SA.: Ai x ≤ bi ,
i∈ R
y≥
b j + td j − C j x
wj
, j ∈G
x≥0
y∈R
novamente, pode-se reescrever a mesma formulação como:
p


Min  y − ε ∑ Ck x 
k =1


SA.: Ai x ≤ bi ,
i∈ R
C j x + w j y ≥ b j + td j , j ∈ G
x≥0
y∈R
37
Como a variável y é livre, para efeitos computacionais, a mesma é reescrita
como y = y + − y − , com y + , y − ≥ 0 . Temos, assim, a formulação final do Pareto
Race:
p


Min  y + − y − − ε ∑ Ck x 
k =1


+
−
SA.: C j x + w j y − w j y ≥ b j + td j , j ∈ G
Ai x ≤ bi ,
(5.2)
i∈R
x, y + , y − ≥ 0
onde, ε é um escalar muito pequeno maior que zero, i ∈ R o conjunto das m
metas inflexíveis (restrições) e j ∈ G o conjunto das p metas flexíveis (funções
objetivo).
A idéia é que “a partir de níveis de aspiração para os valores das funções
objetivo, especificados inicialmente pelo decisor, é construída uma direção de
referência (direção que, partindo de um ponto admissível no espaço dos objetivos,
oferece uma variação nos valores das funções objetivos que está de acordo com
as preferências do decisor). Esta direção de referência é então projetada sobre o
conjunto de soluções eficientes, gerando uma trajetória (subconjunto de soluções
eficientes) que é apresentada ao decisor. O decisor pode assim percorrer a
fronteira eficiente, controlando a direção do movimento (privilegiando diferentes
funções objetivo) e a velocidade (obtendo soluções mais ou menos próximas umas
das outras) como se estivesse conduzindo um automóvel (daí a denominação de
Pareto Race) sobre essa superfície”. (Climaco et al, 1996)
38
V.5. Um Exemplo Numérico
Esta sub-seção foi baseada no exemplo numérico constante no trabalho de
Climaco et al (1996).
Consideremos o seguinte MOLP:
Max z1 = x1
Max z 2 =
x2
Max z3 =
SA.:
x3
x1 + x2 + x3 ≤ 5
x1 + 3 x2 + x3 ≤ 9
3 x1 + 4 x2
≤ 16
x1 , x2 , x3 ≥ 0
Cuja região viável S está diagramada na figura 5.3 abaixo:
x2
x3
x1
Figura 5.3
O primeiro passo no método Pareto Race é questionar o DM sobre os seus
níveis de aspirações para as funções objetivo. Neste exemplo, o mesmo forneceu
como resposta 6,000, 5,000 e 5,000. Logo após, devemos questionar o DM sobre
o intervalo de variação que os níveis de aspirações podem sofrer. Deve-se
esclarecer ao DM que estes intervalos de variação são apenas indicativos,
39
podendo acontecer de os valores das funções objetivo não estarem nos
respectivos intervalos. No nosso exemplo, o DM informou [4,500; 7,000], [2,500;
6,000] e [2,000; 6,000]. De posse destes dados, temos como vetor resultante:
bT = ( 6, 000 5, 000 5, 000 5, 000 9, 000 16,000 )
no qual as três primeiras componentes referem-se às aspirações do DM para as
metas flexíveis (funções objetivo) e as três últimas, ao RHS (Right Hand Side) das
metas inflexíveis (restrições). O vetor de pesos w condiciona implicitamente a
importância relativa de cada função objetivo através de:
∆bk , se k ∈ G
wk := 
se k ∈ R
0,
Inicialmente, faremos o vetor de referência d , que controla a direção do
movimento, igual ao vetor w , logo:
 7, 000 − 4,500   2,500 
 6, 000 − 2, 500   3,500

 
 6, 000 − 2, 000   4, 000
d =w = 
=
0,000

  0, 000

  0, 000
0,000

 
0,000

  0, 000 
Posteriormente, o vetor d será normalizado pela constante s =
∑d
k
iniciais .
No nosso exemplo s = 2,500 + 3,500 + 4, 000 + 0,000 + 0, 000 + 0, 000 = 10, 000 .
Temos, assim, o seguinte problema:
Min y + − y − − 0,001( x1 + x2 + x3 )
SA.:
+ 2,500 y + − 2,500 y − ≥ 6, 000 + 2,500t
x1
+ 3,500 y + − 3,500 y − ≥ 5, 000 + 3,500t
x2
x3 + 4, 000 y + − 4, 000 y − ≥ 5, 000 + 4, 000t
+ x2 + x3
≤ 5, 000
x1 + 3, 000 x2 + x3
≤ 9, 000
x1
3, 000 x1 + 4, 000 x2
+
≤ 16, 000
−
x1 , x2 , x3 , y , y ≥ 0
40
Introduzindo as variáveis de folga S1 , S2 ,..., S6 , e fazendo inicialmente
t = 0, 000 , temos como solução ótima do PL acima a base  X1 , X 2 , X 3 , Y + , S5 , S6  ,
com tableau Simplex ótimo:
X1
X2
X3
Y+
S1
Y−
S2
S3
S4
S5
S6
b
X 1 1,000 0,000 0,000 0,000 0,000 -0,750 0,250 0,250 0,250 0,000 0,000 3,250
X 2 0,000 1,000 0,000 0,000 0,000 0,350 -0,650 0,350 0,350 0,000 0,000 1,150
X 3 0,000 0,000 1,000 0,000 0,000 0,400 0,400 -0,600 0,400 0,000 0,000 0,600
Y + 0,000 0,000 0,000 1,000 -1,000 -0,100 -0,100 -0,100 -0,100 0,000 0,000 1,100
S5 0,000 0,000 0,000 0,000 0,000 -0,700 1,300 -0,700 -1,700 1,000 0,000 1,700
S6 0,000 0,000 0,000 0,000 0,000 0,850 1,850 -2,150 -2,150 0,000 1,000 1,650
c j 0,000 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,110 0,000 0,000 -1,050
Observemos que os valores de X não estão compreendidos nos intervalos de
variação previamente fornecidos pelo DM ([4,500; 7,000], [2,500; 6,000] e
[2,000; 6,000]). Procedemos à atualização de tais intervalos: [3,250; 7,000], [1,150;
6,000] e [0,600; 6,000]. Estes valores são sempre atualizados, caso algum
componente da nova solução achada não pertença ao respectivo intervalo.
O intervalo de variação de t que mantém a base ótima, quando se altera o lado
direito das metas de b para b + td , é calculado pela análise de sensibilidade:
xB = B −1 (b + td )
na qual xB é o vetor das variáveis básicas e B −1 a matriz inversa da base. Se
variarmos de t para t + θ , teremos:
xB (θ ) = xB + θ B −1d
que, para garantir a viabilidade do primal, deverá ser maior ou igual a zero:
xB (θ ) ≥ 0
41
obtemos
com
isto
o
intervalo
[t − t1; t + t2 ] ,
onde
t − t1
e
t + t2
são,
respectivamente, o menor e o maior valor que obedecem à restrição xB (θ ) ≥ 0 .
No nosso exemplo:
 X1 
X 
 2
 X3 
xB =  +  = B −1 (b + td )
Y 
 S5 
 
 S6 
 0,750
 -0,350

 -0,400
xB = 
 0,100
 0,700

 -0,850
-0,250
0,650
-0,400
0,100
-1,300
-1,850
-0,250
-0,350
0,600
0,100
0,700
2,150
0,250
0,350
0,400
-0,100
-1,700
-2,150
0,000
0,000
0,000
0,000
1,000
0,000
0,000   6, 000   2,500  


0,000   5, 000   3,500 
0,000   5, 000   4, 000 

 . 
 + t. 
0,000   5, 000   0, 000 
0,000   9, 000   0, 000 

 
 
1,000  16,000   0, 000  
 3,250 + 0, 000.t 
 3,250 + 0, 000.t   0, 000 
 1,150 + 0, 000.t
 1,150 + 0, 000.t   0, 000


 
 0, 600 + 0, 000.t
 0, 600 + 0, 000.t   0, 000
. Como xB (θ ) ≥ 0 : xB = 
xB = 
≥
 1,100 + 0, 000.t
 1,100 + 0, 000.t   0, 000
 1,700 + 0, 000.t
 1,700 + 0, 000.t   0, 000


 
 1,650 + 1, 000.t 
 1,650 + 1, 000.t   0, 000 
Como t = 0, 000 , t ∈ [t − t1 ; t + t2 ] , e o espaço de variação de t que satisfaz a
restrição xB (θ ) ≥ 0 é t ∈ [ −1,100; + ∞ ] , temos que t1 = 1,100 e t2 = +∞ .
V.5.1 Mudança de direção obrigatória
Como t2 = +∞ , não é possível prosseguir a busca na direção atual. Neste
caso, o DM é questionado sobre nova direção para continuar a busca.
Suponhamos que o DM deseje melhorar a FO3. O vetor d3 é alterado, utilizando a
fórmula:
42
di = d i + σ ( LSi − LI i )
onde : d = vetor novo
d = vetor original
σ = constante igual a 0,5 (valor recomendado
pelos autores do método)
LSi = limite superior do intervalo de variação
LI i = limite inferior do intervalo de variação
No nosso exemplo:
d3 = 4, 000 + 0, 500(6, 000 − 0, 600) = 6, 700
O vetor d será normalizado de modo que
∑d
i
= s , pela seguinte fórmula:
s
di = di . m+ p , i = 1, 2,..., m + p
∑dj
j =1
onde d = vetor novo
d = vetor original
no nosso exemplo s = 10, 000 , logo:
di = d i .
10, 000
, i = 1, 2,... , 6
2,500 + 3, 500 + 6, 700
obteremos, então, como novo vetor d :
d T = (1,969 2, 756 5, 276 0, 000 0, 000 0, 000 )
O vetor w também deve ser atualizado. É importante notar que, quando o
ponto de referência se situa na fronteira não dominada, ou fora dela, ou seja,
y + ≥ 0, 000 e y − = 0, 000 , os valores de w são inversamente proporcionais à
importância das FO, isto é, quanto menor o valor de wi , maior importância terá a
i ésima FO. No nosso exemplo: desejamos melhorar a FO3, logo teremos que
diminuir o valor de w3 . Os autores do método recomendam dividir wi por (1 + σ ) ,
ou seja, por 1, 500 , logo:
w3 =
4, 000
= 2, 667
1, 500
43
Procedendo novamente à normalização (idêntica à realizada para o vetor d ),
temos como novo vetor w :
wT = ( 2,885 4, 038 3, 077 0, 000 0, 000 0, 000 )
O ponto de referência é atualizado com o valor das funções objetivo da última
solução, gerando o novo vetor b :
b = ( 3, 250 1,150 0, 600 5, 000 9, 000 16, 000 )
O que gera, novamente, o seguinte problema de PL:
Min y + − y − − 0,001( x1 + x2 + x3 )
SA.:
+ 2,885 y + − 2,885 y − ≥ 3, 250 + 1,969t
x1
+ 4, 038 y + − 4, 038 y − ≥ 1,150 + 2, 756t
x2
x3 + 3, 077 y + − 3, 077 y − ≥ 0, 600 + 5, 276t
+ x2 + x3
≤ 5, 000
x1 + 3, 000 x2 + x3
≤ 9, 000
x1
3, 000 x1 + 4, 000 x2
≤ 16, 000
x1 , x2 , x3 , y + , y − ≥ 0
Cujo tableau Simplex ótimo, para t = 0, 000 , é:
X1
X2
X3
Y+
Y−
S1
S2
S3
S4
S5
S6
b
X 1 1,000 0,000 0,000 0,000 0,000 -0,712 0,289 0,289 0,289 0,000 0,000 3,250
X 2 0,000 1,000 0,000 0,000 0,000 0,404 -0,596 0,404 0,404 0,000 0,000 1,150
X 3 0,000 0,000 1,000 0,000 0,000 0,308 0,308 -0,692 0,308 0,000 0,000 0,600
Y + 0,000 0,000 0,000 1,000 -1,000 -0,100 -0,100 -0,100 -0,100 0,000 0,000 0,000
S5 0,000 0,000 0,000 0,000 0,000 -0,808 1,192 -0,808 -1,808 1,000 0,000 1,700
S6 0,000 0,000 0,000 0,000 0,000 0,519 1,519 -2,481 -2,481 0,000 1,000 1,650
c j 0,000 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,110 0,000 0,000 0,050
44
Calculando o intervalo de variação de t para o qual a base ótima se mantém,
temos:
 X1 
X 
 2
 X3 
xB =  +  = B −1 (b + td )
Y 
 S5 
 
 S6 
 0,712
 -0,404

 -0,308
xB = 
 0,100
 0,808

 -0,519
-0,289
0,596
-0,308
0,100
-1,192
-1,519
-0,289
-0,404
0,692
0,100
0,808
2,481
0,289
0,404
0,308
-0,100
-1,808
-2,481
0,000
0,000
0,000
0,000
1,000
0,000
0,000   3, 250   1,969  


0,000   1,150   2, 756 
0,000   0, 600   5, 276 

 . 
 + t. 
0,000   5, 000   0, 000 
0,000   9, 000   0, 000 

 
 
1,000  16,000   0, 000  
 3, 250 − 0,916t   0, 000 
 1,150 − 1, 282t   0, 000

 
 0, 600 + 2,199t   0, 000
xB = 
≥
 0, 000 + 1, 000t   0, 000
 1, 700 + 2, 564t   0, 000

 
 1, 650 + 7,878t   0, 000 
Como t = 0, 000 , t ∈ [t − t1 ; t + t2 ] , e o espaço de variação de t que satisfaz a
restrição xB (θ ) ≥ 0 é t ∈ [0, 000; 0,897] , temos que t1 = 0, 000 e t2 = 0,897 .
A partir deste ponto, o DM pode melhorar a FO3 com a velocidade que lhe
convier. Os autores do Pareto Race estabelecem, como default de ∆t , a constante
β = 10−4 . No nosso exemplo, o DM desejou uma velocidade ∆t = 0, 020 . Para
t = 0, 020 , a solução é calculada como se segue:
 X 1   3, 250 − 0, 916.0, 020   3,232 
X  
 
 2   1,150 − 1, 282.0, 020   1,124
 X 3   0, 600 + 2,199.0, 020   0,644
xB =  +  = 
=
 Y   0, 000 + 1, 000.0, 020   0,020
 S5   1, 700 + 2,564.0, 020   1,751
  
 
 S6   1, 650 + 7,878.0, 020   1,808 
45
Prosseguindo nesta direção, com incrementos ∆t = 0, 020 temos:
t=0,020
t=0,040
t=0,060
t=0,080
…
t=0,897
X1
3,232
3,213
3,195
3,177
2,428
X2
1,124
1,099
1,073
1,047
0,000
X3
0,644
0,688
0,732
0,776
2,572
Y+
0,020
0,040
0,060
0,080
0,897
S5
1,751
1,803
1,854
1,905
4,000
S6
1,808
1,965
2,123
2,280
8,716
Quando t atinge o valor limite superior, que no nosso exemplo é 0,897, é
alcançada uma aresta do politopo das restrições (uma variável básica tem valor
zero) e, para continuar na mesma direção, isto é, incrementando o valor da FO3, é
necessária uma mudança de base.
V.5.2 Mudança de base (a direção atual é mantida)
Ao aplicar o Dual-Simplex na linha pivô X 2 (variável básica com valor igual a
zero), temos o seguinte teste da razão:
Teste da razão
S1
Y−
S2
S3
S4
c

min  j
| aij < 0, 000 aij = 0, 000 aij > 0, 000 0,168 aij > 0, 000 aij > 0, 000
 aij

Logo, a variável que entra no lugar da X 2 é a S 2 , ficando como base
ótima:  X 1 , S 2 , X 3 , Y + , S5 , S6  .
46
Quando calculamos o intervalo de variação de t para o qual a base ótima se
mantém, temos:
 X1 
S 
 2
 X3 
xB =  +  = B −1 (b + td )
Y 
 S5 
 
 S6 
 0,516

 0,677
 -0,516
xB = 
 0,168
 0,000
 -1,548

0,000 -0,484 0,484 0,000 0,000   3, 250   1, 969  

 
 
-1,000 0,677 -0,677 0,000 0,000   1,150   2, 756 
0,000 0,484 0,516 0,000 0,000   0, 600   5, 276 

 . 
 + t. 
0,000 0,168 -0,168 0,000 0,000   5, 000   0, 000 
0,000 0,000 -1,000 1,000 0,000   9, 000   0, 000 

 
 
0,000 1,452 -1,452 0,000 1,000  16, 000   0, 000  
 3,806 − 1,537t   0, 000 
 -1,929 + 2,150t   0, 000

 
 1,194+1,537t   0, 000
xB = 
≥
-0,193+1,215
t

  0, 000
 4,000+0,000t   0, 000

 
 4,581 + 4,611t   0, 000 
Como t = 0,897 , t ∈ [t − t1 ; t + t2 ] , e o espaço de variação de t que satisfaz a
restrição xB (θ ) ≥ 0 é t ∈ [0,897; 2, 477 ] , temos que t1 = 0, 000 e t2 = 1,580 .
Para o valor mínimo de t = 0,897 , temos a seguinte solução:
( X1
X2
X 3 ) = ( 2, 428 0, 000 2,572 )
Observemos que os valores de X 1 e X 2 não estão compreendidos nos
intervalos de variação anteriores: [3,250; 7,000] e [1,150; 6,000]. Logo, os mesmos
são atualizados para, respectivamente: [2,428; 7,000] e [0,000; 6,000].
47
Suponhamos que o DM deseje aumentar a velocidade, por exemplo, para
∆t = 0, 030 . A seguinte seqüência de soluções é então gerada para o DM:
t=0,897
t=0,927
t=0,957
…
t=1,047
X1
2,428
2,382
2,336
2,197
S2
0,000
0,065
0,129
0,323
X3
2,572
2,618
2,664
2,803
Y+
0,897
0,933
0,970
1,079
S5
4,000
4,000
4,000
4,000
S6
8,716
8,855
8,993
9,408
Suponhamos que, apesar de o DM poder vasculhar a fronteira não dominada
nesta direção (aumentando Z 3 ) até o valor de t = 2, 477 , no ponto t = 1, 047 , o
mesmo (DM) desejou mudar de direção, aumentando o valor da segunda função
objetivo, que atualmente está com valor zero.
V.5.3 Mudança de direção voluntária
Atualizando o intervalo de variação da FO1, temos os seguintes intervalos:
[2,197; 7,000], [0,000; 6,000], e [0,600; 7,000].
Como o DM deseja aumentar Z 2 , é necessário um incremento na componente
correspondente à Z 2 no vetor direção d e uma diminuição da mesma componente
no vetor de pesos w :
d 2 = d2 + σ ( LSi − LI i ) = 2, 756 + 0,500(6, 000 − 0, 000) = 5, 756
w2 = w2
1,500
= 4, 038
48
1,500
= 2, 692
Após a normalização, temos:
 1, 514 
 4, 428 


 4, 058 
d =
,
 0, 000 
 0, 000 


 0, 000 
 3,333 
 3,111

 3,555
w=
 0, 000
 0, 000

 0, 000 
O ponto de referência é atualizado com os valores da última solução:
bT = ( 2,197 0, 000 2,803 5, 000 9, 000 16, 000 )
Resolve-se o seguinte problema considerando t = 0, 000 :
Min y + − y − − 0, 001( x1 + x2 + x3 )
SA.:
+ 3,333 y + − 3,333 y − ≥ 2,197 + 1,514t
x1
+ 3,111y + − 3,111 y − ≥ 0, 000 + 4, 428t
x2
x3 + 3,555 y + − 3,555 y − ≥ 2,803 + 4, 058t
+ x2 + x3
≤ 5, 000
x1 + 3, 000 x2 + x3
≤ 9, 000
x1
3, 000 x1 + 4, 000 x2
≤ 16, 000
x1 , x2 , x3 , y + , y − ≥ 0
Cujo Tableau Simplex Ótimo é o seguinte:
X1
X2
X3
Y+
Y−
S1
S2
S3
S4
S5
S6
b
X 1 1,00 0,000 0,000 0,000 0,000 -0,667 0,333 0,333 0,333 0,000 0,000 2,197
X 2 0,00 1,000 0,000 0,000 0,000 0,311 -0,689 0,311 0,311 0,000 0,000 0,000
X 3 0,00 0,000 1,000 0,000 0,000 0,356 0,356 -0,644 0,356 0,000 0,000 2,803
Y + 0,00 0,000 0,000 1,000 -1,000 -0,100 -0,100 -0,100 -0,100 0,000 0,000 0,000
S5 0,00 0,000 0,000 0,000 0,000 -0,622 1,378 -0,622 -1,622 1,000 0,000 4,000
S6 0,00 0,000 0,000 0,000 0,000 0,755 1,755 -2,245 -2,245 0,000 1,000 9,409
c j 0,00 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,101 0,000 0,000 0,005
49
Fazendo a análise de sensibilidade, temos que:
 X1 
 
 X2 
X 
xB =  +3  = B −1 (b + td )
Y 
 S5 
 
 S6 
 0,667

 -0,311
 -0,356
xB = 
 0,100
 0,622

 -0,755
-0,333 -0,333 0,333 0,000 0,000   2,197   1, 514  

 
 
0,689 -0,311 0,311 0,000 0,000   0, 000   4, 428 
-0,356 0,644 0,356 0,000 0,000   2,803   4, 058 

 . 
 + t. 
0,100 0,100 -0,100 0,000 0,000   5, 000   0, 000 
-1,378 0,622 -1,622 1,000 0,000   9, 000   0, 000 

 
 
-1,755 2,245 -2,245 0,000 1,000  16, 000   0, 000  
 2,197 − 1,819t   0, 000 
 0,000 + 1,317t   0, 000

 
 2,803+0,503t   0, 000
xB = 
≥
 0,000+1,000t   0, 000
 4,000 − 2,633t   0, 000

 
 9,409 + 0,191t   0, 000 
Como t = 0, 000 , t ∈ [t − t1 ; t + t2 ] , e o espaço de variação de t que satisfaz a
restrição xB (θ ) ≥ 0 é t ∈ [0, 000; 1, 208] , temos que t1 = 0, 000 e t2 = 1, 208 .
Mantendo a mesma velocidade ∆t = 0, 030 , as seguintes soluções são
apresentadas ao DM:
t=0,000
t=0,030
t=0,060
X1
2,197
2,142
2,088
1,433
X2
0,000
0,040
0,079
0,553
X3
2,803
2,818
2,833
3,014
Y+
0,000
0,030
0,060
0,420
S5
4,000
3,921
3,842
2,894
S6
9,409
9,415
9,420
9,489
50
…
t=0,420
V.5.4 Fixando o valor de uma FO
Suponhamos que, neste ponto ( t = 0, 420 ), o DM deseje continuar nesta
direção (aumentando Z 2 ) mas não deseje que o valor de Z1 diminua, ou seja, o
DM quer fixar Z1 = 1, 433 .
Para tanto, devemos fazer a componente correspondente àquela FO nos
vetores w e d igual a zero:
wi = 0, 000;
d i = 0, 000
onde i é o índice da FO fixada
No nosso exemplo, faremos:
 0, 000 
 4, 428 


 4, 058 
d =

 0, 000 
 0, 000 


 0, 000 
 0, 000 
 3,111

 3, 555
w=
 0, 000
 0, 000

 0, 000 
que, após a normalização, ficará:
 0, 000 
 5, 218 


 4, 782 
d =

 0, 000 
 0, 000 


 0, 000 
 0,000 
 4,667

 5,333
w=
 0,000
 0,000

 0,000 
Atualizando novamente o intervalo de variação da FO1, obteremos:
[1,433; 7,000]
51
Teremos, assim, o seguinte PPL:
Min y + − y − − 0, 001( x1 + x2 + x3 )
SA. :
+ 0, 000 y + − 0, 000 y − ≥ 1, 433 + 0, 000t
x1
+ 4, 667 y + − 4, 667 y − ≥ 0,553 + 5, 218t
x2
x3 + 5,333 y + − 5,333 y − ≥ 3, 014 + 4, 782t
+ x2 + x3
≤ 5, 000
x1 + 3, 000 x2 + x3
≤ 9, 000
x1
3, 000 x1 + 4, 000 x2
≤ 16, 000
x1 , x2 , x3 , y + , y − ≥ 0
Cujo Tableau Simplex Ótimo é o seguinte:
X1
X2
X3
Y+
Y−
S1
S2
S3
S4
S5
S6
b
X 1 1,000 0,000 0,000 0,000 0,000 -1,000 0,000 0,000 0,000 0,000 0,000 1,433
X 2 0,000 1,000 0,000 0,000 0,000 0,467 -0,533 0,467 0,467 0,000 0,000 0,553
X 3 0,000 0,000 1,000 0,000 0,000 0,533 0,533 -0,467 0,533 0,000 0,000 3,014
Y + 0,000 0,000 0,000 1,000 -1,000 -0,100 -0,100 -0,100 -0,100 0,000 0,000 0,000
S5 0,000 0,000 0,000 0,000 0,000 -0,933 1,067 -0,933 -1,933 1,000 0,000 2,894
S6 0,000 0,000 0,000 0,000 0,000 1,133 2,133 -1,867 -1,867 0,000 1,000 9,489
c j 0,000 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,101 0,000 0,000 0,005
Fazendo a análise de sensibilidade, teremos que:
 X1 
 
 X2 
X 
xB =  +3  = B −1 (b + td )
Y 
 S5 
 
 S6 
52
 1,000

 -0,467
 -0,533
xB = 
 0,100
 0,933

 -1,133
0,000 0,000 0,000 0,000 0,000   1, 433 
 0, 000  

 


0,533 -0,467 0,467 0,000 0,000   0,553 
 5, 218 
 4, 782 
-0,533 0,467 0,533 0,000 0,000   3, 014 

 . 
 + t. 
0,100 0,100 -0,100 0,000 0,000   5, 000 
 0, 000 
 0, 000 
-1,067 0,933 -1,933 1,000 0,000   9, 000 

 


-2,133 1,867 -1,867 0,000 1,000  16, 000 
 0, 000  
 1,433 + 0,000t   0, 000 
 0,553 + 0,551t   0, 000

 
 3,014 − 0,551t   0, 000
xB = 
≥
 0,000+1,000t   0, 000
 2,894 − 1,102t   0, 000

 
 9,489 − 2,204t   0, 000 
Como t = 0, 000 , t ∈ [t − t1 ; t + t2 ] , e o espaço de variação de t que satisfaz a
restrição xB (θ ) ≥ 0 é t ∈ [0, 000; 2, 626] , temos que t1 = 0, 000 e t2 = 2, 626 .
Mantendo a mesma velocidade ∆t = 0, 030 , as seguintes soluções são
apresentadas ao DM:
t=0,000
t=0,030
t=0,060
X1
1,433
1,433
1,433
1,433
X2
0,553
0,570
0,586
1,082
X3
3,014
2,998
2,981
2,485
Y+
0,000
0,030
0,060
0,960
S5
1,000
2,861
2,828
1,836
S6
1,000
9,423
9,357
7,373
Supondo que o DM ache
( Z1
Z2
…
t=0,960
Z3 ) = (1, 433 1, 082 2, 485 ) uma boa
solução, o processo termina. A trajetória das soluções apresentadas ao DM, neste
nosso exemplo, no espaço objetivo, está diagramada na figura 5.4 abaixo:
53
Z2
(1,433; 1,082; 2,485)
(3,250; 1,150; 0,600)
(1,433; 0,553; 3,014)
(2,197; 0,000; 2.803)
Z3
(2,428; 0,000; 2,572)
Z1
Figura 5.4
V.5.5 Comentários Finais
Na análise de sensibilidade, que determina os limites de variação que t pode
ter, deveremos utilizar:
t + min{∆t ; t2 }, se ∆t > 0
t=
t + max{∆t ; −t1}, se ∆t < 0
Se t2 = ∞ ou então t1 = 0, 000 e ∆t < 0, 000 , é alcançado o limite do politopo
naquela direção; logo, o DM deverá ser questionado sobre nova direção. Se
t2 = 0, 000 e ∆t > 0, 000 , significa que não é possível avançar na direção atual
sem que haja mudança de base. Após a mudança de base, deve-se atualizar o
intervalo [t − t1 ; t + t2 ] .
Para liberar novamente uma FO fixada anteriormente, deve-se fazer:
wi := ∆bi ;
di := ∆bi
onde i é o índice da FO fixada
54
CAPÍTULO VI
O ALGORITMO PROPOSTO
VI.1. Comentários Iniciais
Como visto no capítulo anterior, o método Pareto Race é uma excelente
ferramenta para a busca da solução final preferida pelo DM. Ao possibilitar vasculhar
toda a fronteira não dominada de uma maneira bastante intuitiva ao DM, pois a única
interação necessária é a definição de qual FO deverá ter seu valor aumentado e de
quanto deverá ser este aumento, o método cumpre sua finalidade de maneira muito
eficiente e eficaz.
O escopo deste trabalho é proporcionar um auxílio ao método Pareto Race,
possibilitando a obtenção do ponto inicial localizado na fronteira não dominada o mais
próximo possível da solução final preferida pelo DM. Como, via de regra, o DM não
conhece a fronteira não dominada, o mesmo não tem idéia de qual ponto não
dominado a primeira iteração do Pareto Race irá gerar a partir dos seus níveis de
aspirações. Na verdade, o DM não tem juízo se seus níveis de aspirações são viáveis,
se não são viáveis, ou mesmo da distância em que os mesmos se encontram da
fronteira não dominada. Devido a esta ignorância da fronteira não dominada pelo DM,
o ponto inicial gerado pelo Pareto Race pode e, provavelmente, irá estar localizado
muito distante da solução final preferida.
Como comentado no capítulo primeiro (Introdução), o problema da parada
prematura é aquele no qual o DM se satisfaz com uma solução diferente da solução
final que o mesmo escolheria, se tivesse perfeito conhecimento de toda a fronteira não
dominada, ou seja, o DM resolve parar a busca da solução final preferida antes da
obtenção da solução final preferida ótima (aquela que o DM escolheria se tivesse
prévia e total ciência da fronteira não dominada). Caso a busca da solução final
preferida seja iniciada em um ponto muito distante da mesma, o problema da parada
prematura poderá ocorrer.
A metodologia proposta por este trabalho objetiva, primeiramente, auxiliar o DM
ao facilitar o seu trabalho no estabelecimento de trade off’s entre as FO’s, pois, em
uma fase inicial, esta necessidade não existe; este trabalho tem, como escopo
secundário, a diminuição da probabilidade da existência do problema da parada
55
prematura, uma vez que, ao fornecer um ponto localizado na fronteira não dominada
mais próximo da solução final preferida ótima, esta probabilidade fica diminuta.
A idéia da metodologia proposta por este trabalho é a resolução do problema
de programação linear inicial do Pareto Race pelo método dos pontos interiores, em
vez do método SIMPLEX. Devido à geometria do algoritmo proposto, podemos
observar que a seqüência de pontos gerados pelo método dos pontos interiores possui
os valores das FO’s crescentes durante quase todo o seu percurso, não havendo a
árdua necessidade de o DM estabelecer trade off’s entre as mesmas. Ao aproximar-se
da fronteira não dominada, esta característica denominada WIN-WIN, na qual todas as
FO’s possuem seus valores crescentes, não mais existe como via de regra, havendo
possibilidade da existência de trade-off’s entre as FO’s. Como vantagem do método
dos pontos interiores, temos que, durante a maior parte de sua trajetória no interior do
politopo, a característica WIN-WIN é predominante.
A fase um do algoritmo proposto gera, após um numero variável de iterações
do método dos pontos interiores, uma solução intermediária (localizada no interior do
politopo das restrições, ou seja, uma solução dominada) que é apresentada ao DM. Já
na primeira solução intermediária, o DM poderá observar a relação existente entre os
valores das FO’s e, assim, intuir se haverá necessidade ou não de mudar o vetor de
crescimento.
Ao atingir a fronteira não dominada, caso o DM não esteja satisfeito com a
solução apresentada, a busca poderá ser continuada através do método Pareto Race.
56
VI.2. O Algoritmo
Para um problema MOLP do tipo:
max {C1 x = z1}
max {C2 x = z2 }
...
max {C p x = z p }
SA.: Ai x ≤ bi , i = 1, 2, ..., m
x≥0
onde C ∈ R pxn , x ∈ R n , z ∈ R p , A ∈ R mxn e b ∈ R m .
Os seguintes passos da metodologia proposta deverão ser seguidos:
Fase 1: Pontos Interiores
1. Inicialização:
1.1. Obter o ponto interior viável inicial x (como obter tal ponto será discutido
adiante).
1.2. Fazer R o conjunto das m metas inflexíveis (restrições) e G o conjunto das p
metas flexíveis (funções objetivo).
1.3. Solicitar ao DM a velocidade que lhe convêm, e fazer ∆t = velocidade;
2. Formular o seguinte PPL de acordo com os dados referentes ao problema:
p


Min  y + − y − − ε ∑ Ck x 
k =1


SA.: C j x + w j y + − w j y − − S F = b j , j ∈ G
Ai x + S I = bi ,
(6.1)
i∈ R
x, y + , y − , S F , S I ≥ 0
onde: ε é um escalar muito pequeno maior que zero; C é a matriz dos
coeficientes das metas flexíveis; w é o vetor de pesos; S F são as variáveis
de folga das metas flexíveis; A é a matriz dos coeficientes das metas
inflexíveis; e S I são as variáveis de folga das metas inflexíveis.
57
2.1. Fazer o vetor φ igual aos valores que as FO’s assumem com o vetor x :
φ j = C j x , ∀ j ∈ G
2.2. Fazer φ igual a 50% do valor médio esperado das FO’s.
2.3. Fazer o vetor de pesos w igual a:
φ ,
se k ∈ G
.
wk := 
0,000, se k ∈ R
2.4. Fazer as componentes do vetor b iguais a:
2.4.1. as p primeiras componentes são denominadas vetor de aspirações e
tem o valor igual ao vetor φ ; e
2.4.2. as m últimas componentes referem-se ao RHS - Right Hand Side ( bi )
das metas inflexíveis.
2.5. Calcular o vetor κ de modo que:
κ i = { bi − Ai x | i ∈ R}
2.6. Fazer o ponto inicial:
x 0 = ( xT
y+
S IT
y−
(
T
T
SFT ) = x
κ T 1, 000 1, 000 eT
)
T
onde e é um vetor unitário de dimensão adequada.
2.7. Fazer a matriz A =
n
componentes;
C
0 w −w −I
A
I 0
0
é
( p x n ou n x p ); e I
0
uma
, onde 0 é um vetor nulo composto por
0
matriz
nula
de
dimensão
adequada
é uma matriz identidade de dimensão adequada
( p x p ou n x n ).
2.8. Fazer c o vetor gradiente da função objetivo do PPL (6.1):
p
c = ∇( y − y − ε ∑ Ck x )
+
−
k =1
2.9. Fazer v = 1 o contador do número de iterações do método de pontos
interiores; fazer π = 1 o contador de soluções intermediárias e fazer mud = S .
58
2.10. Fazer o vetor inicial de soluções intermediárias sol1 = φ .
3. Resolver o PPL (6.1) pelo método dos pontos interiores:
3.1. Loop:
3.1.1. Fazer os componentes do vetor de crescimento µ iguais a:
µ j = 1, 000, j = 1, 2,..., p
3.1.2. Se mud = S :
3.1.2.1.
apresentar o vetor de crescimento µ , os valores das FO’s (vetor
sol π ) e questionar o DM se o mesmo deseja mudar o vetor de
crescimento. Caso positivo, atualizar o vetor de crescimento µ
e normalizar o mesmo de acordo com o seguinte:
µ i = µi .
p
, i = 1, 2,..., p
p
∑µ
j =1
j
onde µ = vetor crescimento normalizado
µ = vetor crescimento original
3.1.2.2.
Atualizar o vetor b de acordo com o seguinte:
b j = C j x v −1 + µ j ∆t
3.1.2.3.
Fazer y − = 1, 000 (componente de x v −1 );
3.1.2.4.
Fazer y + (componente de x v −1 ) o menor inteiro positivo que
atenda às restrições:
C j x v−1 + ( y + − 1) w − b j > 0, ∀ j ∈ G
y + ≥ 2, 000
3.1.2.5.
Atualizar o vetor S F (componente de x v −1 ) de modo que:
b j − C j x v −1 − ( y + − 1) w + S F j = 0, 000, ∀ j ∈ G
3.1.2.6.
Fazer mud = N ;
59
 xiv −1 , se i =
3.1.3. Fazer D uma matriz diagonal, onde dij = 
0, 000, se i ≠
T
j
.
j
T
3.1.4. Fazer: hv = − D 2 [c − A ω v ] , onde ω v = [( AD 2 A )−1 AD 2 c] .
3.1.5. Fazer: x v = x v −1 + ρ λ h v ,
0 < ρ < 1

onde 
 xi( v−1)

(v)
λ
min
=
− ( v ) , ∀ hi < 0, 1 ≤ i ≤ n 

 hi


Utilizar inicialmente um ρ = 0,100 .
3.1.6. Fazer: gap v =|| hv || .
3.1.7. Se ( y − )v ≥ ( y + )v fazer:
π = π +1 ;
x v = x v −1 ;
sol π = Cx v ;
mud = S .
3.1.8. Se gap v > 1, 000e −4 e sol πj ≥ sol πj −1 , ∀ j ∈ G , fazer v = v + 1 e retornar
ao início do loop.
3.1.9. Se gap v ≤ 1, 000e −4 ou então sol πj < sol πj −1 , ∀ j ∈ G , parar o loop, fazer
π = π + 1 e sol π = Cx v .
60
Fase 2: Pareto Race
4. Inicialização:
4.1. Fazer as componentes do vetor b iguais a:
4.1.1. as p primeiras componentes referem-se aos valores das p funções
objetivo obtidas na última iteração da fase um; e
4.1.2. as m últimas ao RHS (Right Hand Side) das metas inflexíveis
(restrições).
4.2. Fazer os intervalos de variação dos níveis de aspirações iguais a:
LS j = b j + φ
2, 000
, ∀ j∈G
LI j = b j − φ 2, 000 , ∀ j ∈ G
4.3. Fazer:
∆b j = φ , ∀ j ∈ G .
4.4. Fazer os vetores de direção d e de pesos w iguais a:
∆b k , se k ∈ G
.
wk := d k := 
0, 000, se k ∈ R
5. Formular o seguinte PPL de acordo com os dados referentes ao problema:
p
 +

−
Min  y − y − ε ∑ Ck x 
k =1


SA.: C j x + w j y + − w j y − ≥ b j + td j , j ∈ G
Ai x ≤ bi ,
+
(6.2)
i∈ R
−
x, y , y ≥ 0
6. Resolver o PPL (6.2) pelo método Pareto Race:
6.1. Fazer s =
∑w
k
iniciais
6.2. Resolver o PPL (6.2) pelo método SIMPLEX para t = 0, 000 e apresentar as
soluções ao DM. Caso o mesmo esteja satisfeito com as soluções finalizar o
algoritmo.
61
6.3. Loop um:
6.3.1. Atualizar, se necessário, os intervalos de variação dos níveis de
aspirações,
caso
os
valores
atuais
das
FO’s
não
estejam
compreendidos nestes intervalos, e fazer ∆b j = LS j − LI j , ∀ j ∈ G .
6.3.2. Caso o DM não esteja satisfeito com as soluções, questionar o mesmo
sobre qual FO deverá ter seu valor aumentado ou fixado, fazer i =qual
FO terá o valor aumentado/fixado, solicitar ao DM a velocidade que lhe
convêm, e fazer ∆t = velocidade;
6.3.2.1.
Caso o DM deseje fixar o valor de alguma FO fazer:
wi = 0, 000;
d i = 0, 000
onde i é o índice da FO fixada
6.3.2.2.
Caso contrário (o DM deseja aumentar o valor de alguma FO):
6.3.2.2.1. Alterar o vetor d utilizando a seguinte fórmula:
di = d i + 0,500∆bi
onde : d = vetor novo
d = vetor original
∆bi = intervalo de variação
dos níveis de aspirações
6.3.2.2.2. Alterar o vetor w utilizando a seguinte fórmula:
wi =
wi
1,500
6.3.3. Normalizar os vetores d e w pela seguinte fórmula:
s
vi = vi . m + p
∑v
j =1
, i = 1, 2,..., m + p
j
onde v = vetor d ou w normalizado
v = vetor d ou w original
62
6.3.4. Atualizar o vetor b com os valores das funções objetivo da última
solução e os vetores w e d com os valores normalizados calculados
acima;
6.3.5. Resolver o PPL (6.2) pelo método SIMPLEX para t = 0, 000 ;
6.3.6. Calcular o intervalo de variação de t para o qual a base se mantém
ótima pela seguinte fórmula:
B −1 (b + td ) ≥ 0, 000
e achar o intervalo de variação [t − t1 ; t + t2 ] .
6.3.7. Se t2 = ∞ ou então t1 = 0, 000 e ∆t < 0, 000 , é alcançado o limite do
politopo naquela direção; logo, o DM deverá ser questionado sobre
nova direção. Se t2 = 0, 000 e ∆t > 0, 000 , significa que não é possível
avançar na direção atual sem que haja mudança de base. Após a
mudança de base, deve-se atualizar o intervalo [t − t1 ; t + t2 ] .
6.3.8. Loop dois:
t + min{∆t ; t2 }, se ∆t > 0, 000
t + max{∆t ; −t1}, se ∆t < 0, 000
6.3.8.1.
Fazer t = 
6.3.8.2.
Apresentar a solução xB = B −1 (b + td ) ao DM. Caso o mesmo
esteja satisfeito com a solução, ou então deseje mudar a direção
de busca, ou então t = limite superior do intervalo [t − t1 ; t + t2 ] :
terminar o loop dois; caso contrário fazer t = t e reiniciar o loop
dois.
6.3.9. Caso o DM esteja satisfeito com a solução terminar o loop um; caso
contrário reiniciar o loop um.
6.4. Fim.
63
VI.3. Obtenção do Vetor Viável Inicial
De posse dos dados do problema e após a modelagem matemática do mesmo,
deve-se verificar qual das duas possibilidades abaixo retrata a realidade do nosso
PPL:
o
O PPL está na forma padrão: Ax ≤ b ; ou
o
O PPL não está na forma padrão: ∃ Ai x ≥ bi e/ou ∃ Ai x = bi tal que i ∈ R .
Caso o PPL esteja na forma padrão, a solução inicial x fica trivial:
x i = ε *
onde ε * é um valor pequeno comparado com a dimensão do problema.
Caso o PPL não esteja na forma padrão: adicionando uma variável y * ao PPL
original, somando ao RHS das restrições tipo maior ou igual um valor pequeno ε * , e
fazendo o vetor β de modo que:
β i = bi − Aiε * − ε * ,
i ∈ {restrições ≤ }
β i = b j − Aj ε * + 2ε * , j ∈ {restrições ≥ }
β i = b j - Aj ε ,
(6.3)
j ∈ {restrições = }
*
formulamos o seguinte PPL auxiliar:
n


Min  My * + ∑ xi 
i =1


SA.: Ai x + S Ii + β i y * = bi ,
i ∈ {restrições ≤ }
Aj x − S I j + βi y* = b j + ε * , j ∈ {restrições ≥ }
A j x + β y *i = b j ,
xk − S Ik +m + ε * y * = ε * ,
j ∈ {restrições = }
k = {1, 2,..., n}
y* , S I ≥ 0
onde M é um número muito grande
64
(6.4)
Tal PPL auxiliar pode ser resolvido tanto pelo SIMPLEX quanto pelo método
T
T
dos pontos interiores. Utilizando como ponto inicial x 0 = ( xT S IT y * ) = (ε ε 1) , que é
T
tanto interior quanto viável, estaremos aptos a resolver o PPL auxiliar pelo método dos
pontos interiores. O vetor ε tem todas as suas componentes ε i = ε * e possui
dimensão adequada.
A solução ótima do PPL auxiliar, resolvido tanto pelo SIMPLEX quanto pelo
método dos pontos interiores, nos fornecerá o ponto inicial x .
65
VI.4. Comentários Sobre o Algoritmo
Como comentado anteriormente, a idéia central da metodologia proposta é a
resolução da primeira iteração do Pareto Race pelo método de pontos interiores. Para
tanto, na fase um, durante a inicialização, o DM é questionado sobre a velocidade que
lhe convém. Tal velocidade será a média dos acréscimos que as FO’s sofrerão a cada
solução intermediária. Convém ressaltar ao DM que esta velocidade é apenas um
indicativo, não sendo uma medida fixa e rígida. Durante as várias soluções
intermediárias que lhe serão apresentadas, o mesmo (DM) irá notar que os
acréscimos sofridos pelas FO’s terão seus valores próximos à velocidade estabelecida
na inicialização. O DM será também questionado sobre o valor médio esperado das
FO’s. Este valor será utilizado para a determinação do vetor de pesos w . Caso o DM
não tenha idéia sobre tal valor, uma alternativa é realizar a otimização de uma FO
escolhida aleatoriamente. Fazendo
x* a solução ótima desta FO escolhida
aleatoriamente, teremos como valor médio esperado das FO’s a média dos valores
que todas as FO’s assumem com este vetor ótimo x* .
Durante as diversas interações do algoritmo com o DM, o mesmo é
apresentado ao vetor de crescimento e é questionado se deseja modificá-lo ou não.
Tal vetor de crescimento é o indicativo ao DM de quanto será o aumento individual das
FO’s na próxima solução intermediária que lhe será apresentada. Ao aumentar (ou
diminuir) uma componente do vetor de crescimento, a FO correspondente àquele
aumento (ou diminuição), terá o acréscimo do seu valor na próxima iteração maior (ou
menor) do que teria se não houvesse tal aumento (ou diminuição) no vetor de
crescimento. Como o vetor de crescimento é normalizado, a média dos aumentos será
próxima ao valor da velocidade estabelecida durante a inicialização. Se o DM
estabelecer o vetor de crescimento unitário (todos componentes iguais a um), isto
significará que o mesmo deseja que todas as FO’s tenham crescimento similar e o
valor destes crescimentos será igual ao valor da velocidade ( ∆t ). Caso o DM deseje,
por exemplo, que a FO1 tenha o dobro do crescimento das demais, o mesmo deverá
estabelecer o vetor de crescimento como: µ = ( 2 1 1 ... 1) e, na próxima solução
intermediária, o acréscimo da FO1 será aproximadamente o dobro do acréscimo
sofrido pelas demais FO’s, e a média dos acréscimos será igual à velocidade.
66
Após o estabelecimento do vetor de crescimento, um novo vetor de aspirações
( b j ) é gerado através do valor atual das FO’s somadas aos acréscimos (vetor de
crescimento vezes velocidade). Deste modo, a fase um irá sempre oferecer um ponto
no espaço de decisão que é dominado, e questionar o DM sobre a direção na qual um
passo de tamanho aproximadamente igual à velocidade será dado. Após tal passo ser
dado, o novo ponto gerado é apresentado ao DM e o ciclo recomeça. Esta geometria,
que proporciona a característica WIN-WIN, durante quase todo caminho no interior do
politopo, está ilustrada na figura 6.1 abaixo, onde a cruz representa a solução
intermediária gerada pela iteração anterior, o X representa o vetor de aspirações
gerado pela iteração corrente e o
representa o vetor de aspirações gerado pela
iteração anterior. Observemos que na iteração Z, o vetor de aspirações gerado se
encontra após a fronteira não dominada; logo, a solução gerada na iteração [ será
um ponto não dominado, terminando assim a fase um.
X
Y
Z
[
Figura 6.1
Um ponto que merece atenção é o seguinte: se o vetor de aspirações é um
ponto dominado, na solução ótima do PPL a componente da solução ótima y − terá
seu valor maior do que a componente y + . O mecanismo de parada das iterações do
método Afim Escala Primal se baseia nisto. Caso y − > y + , isto significará que a
solução gerada pela atual iteração, estará localizada entre o vetor de aspirações e a
fronteira não dominada. Quando detectado tal fato, o algoritmo pára e mostra a
solução anterior ao DM. Após o estabelecimento do novo vetor de crescimento, um
novo vetor de aspirações é gerado e o ciclo irá se repetir. Ao proceder deste modo, o
algoritmo prossegue até que o vetor de aspirações gerado se encontre além da
fronteira não dominada. Outro ponto que merece atenção é o valor da variável ρ : na
descrição formal do algoritmo, ele foi fixado em ρ = 0,100 . Este valor proporcionará
passos muito pequenos, o que fará com que a próxima solução intermediária a ser
gerada possa estar bem próxima do vetor de aspirações. Isto, porém, acarretará um
67
esforço computacional maior, requerendo um número muito grande de iterações do
método Afim Escala Primal. Uma maneira de se contrapor a isto é elevar o valor de ρ
e, quando a solução gerada estiver próxima ao valor do vetor de aspirações, diminuí-lo
novamente.
O algoritmo termina quando o gap , que determina se a solução ótima foi
alcançada, ficar abaixo do limite de 1, 000e −4 , ou então se ocorrer decréscimo em
alguma FO. Como para o estabelecimento de trade-off’s entre FO’s o método Pareto
Race se mostra muito mais eficiente que o de Pontos Interiores, caso tal fato ocorra
(decréscimo em alguma FO), a fase um é finalizada, passando-se à fase seguinte: o
método Pareto Race.
O ponto final gerado pelo método de pontos interiores não pertence à fronteira
não dominada, mas está muito próximo da mesma. Modificando o valor do vetor de
aspirações para a solução final gerada pelo método de pontos interiores, e resolvendo
o PPL pelo SIMPLEX, chegaremos à solução não dominada inicial do Pareto Race.
Caso o DM deseje continuar a busca, o método Pareto Race será utilizado. Ressaltase que, a partir deste ponto, para cada aumento em uma FO, outra deverá
obrigatoriamente ter seu valor decrescido.
68
CAPÍTULO VII
UM EXEMPLO NUMÉRICO
VII.1. Descrição do Problema
A Força Aérea Brasileira (FAB), anualmente, na ocasião do recebimento da
dotação orçamentária aprovada pelo Congresso Brasileiro, necessita distribuir seus
recursos por suas diversas unidades. Grande parte destes recursos destina-se à
manutenção do treinamento das Unidades Aéreas.
Abordaremos, nesta seção, um exemplo de como a adoção da metodologia
proposta por este trabalho pode ser utilizada para auxiliar na distribuição orçamentária
descrita no parágrafo anterior. Para tanto, faremos uma simplificação, com fins
didáticos, do problema real da FAB: só realizaremos a distribuição orçamentária dentro
da sub-divisão da FAB chamada FAE III. A FAE III é o órgão responsável pela parte
operacional da FAB e nela encontram-se os esquadrões de caça, ataque e
reconhecimento aéreo. Outra simplificação adotada é a assunção de que o custo da
hora de vôo é fixo e de que o treinamento de uma equipagem aérea (piloto) pode ser
medido apenas pela quantidade de horas voadas.
No nosso exemplo, estudaremos a distribuição do esforço aéreo dentre nove
tipos de aeronaves:
•
Aviação de Caça: aeronaves F-5E e F-103E;
•
Aviação de Ataque: aeronaves T-27, AT-26 e A-1;
•
Aviação de Reconhecimento: aeronaves C-98A, R-95, R-35 e R-99.
Para o nosso exemplo, utilizaremos o seguinte índice para as diferentes
aeronaves:
1. F-5E
6. C-98A
2. F-103
7. R-95
3. T-27
8. R-35
4. AT-26
9. R-99
5. A-1
69
Foi estipulado por órgãos competentes do Comando da Aeronáutica que a
capacitação individual dos pilotos seja medida pelas seguintes aproximações lineares
da curva de aprendizado:
f1 ( x) = 0,569 x − 6, 423
f 2 ( x ) = 0,814 x − 22,093
f3 ( x ) = 0,324 x + 9, 259
f 4 ( x ) = 0,343 x + 8,039
f5 ( x) = 0,343 x + 8,039
f 6 ( x) = 0, 297 x + 11,017
f 7 ( x ) = 0, 479 x − 0,685
f8 ( x ) = 0,479 x − 0,685
f9 ( x ) = 0, 479 x − 0,685
onde x é a quantidade de horas voadas.
As funções capacitação acima descritas estão plotadas nas figuras abaixo:
f ( x)
f2 ( x)
f1 ( x)
x
Figura 7.1 – Aviação de Caça
70
f ( x)
f3 ( x )
f 4 ( x) e f5 ( x)
x
Figura 7.2 – Aviação de Ataque
f ( x)
f 7 ( x ), f8 ( x )e f9 ( x)
f 6 ( x)
x
Figura 7.3 – Aviação de Reconhecimento
Consideraremos que a distribuição de horas dentro do Esquadrão se dará
uniformemente, isto é, todos os pilotos voarão as mesmas quantidades de horas; logo,
71
a capacitação de uma Unidade Aérea será igual à capacitação de um integrante da
mesma.
Também foi estipulado pelos órgãos competentes que a capacitação mínima
de uma equipagem aérea é de 30% e a máxima é de 100%, assim como a máxima
diferença de treinamento admissível entre as unidades de caça e de ataque é de 10%
dentro da mesma aviação.
Considerando fixos os custos da hora de vôo, temos as seguintes funções
custo para as diversas aeronaves:
•
g1 ( x) = 25,570 x
•
g 6 ( x) = 1,000 x
•
g 2 ( x) = 49,780 x
•
g 7 ( x ) = 3,035 x
•
g3 ( x ) = 6,153 x
•
g8 ( x ) = 5,165 x
•
g 4 ( x ) = 28,682 x
•
g9 ( x ) = 8,859 x
•
g5 ( x) = 47,668 x
A função custo da hora de vôo foi calculada pela multiplicação do custo real da
hora de vôo pelo número de pilotos da unidade, ou seja, os valores acima
discriminados representam quanto custa para que todos os pilotos daquela aeronave
realizem uma hora de vôo. Devido ao sigilo do assunto, os valores da função custo
foram normalizados pelo menor resultado da multiplicação mencionada acima. O
número de pilotos, assim como os valores reais da hora de vôo, por motivos de
segurança, foram omitidos.
Para o nosso exemplo, simularemos que, da dotação orçamentária recebida
pela FAB, a mesma destinou para o treinamento aéreo $32.000,00. Observemos que
este valor representa o montante real dividido pelo menor valor da multiplicação do
custo real da hora de vôo pelo número de pilotos da unidade dentre as diversas
aviações.
72
Simularemos, também, que existem quatro objetivos almejados pelo alto
escalão de DM’s da FAB:
•
Maximizar o treinamento da Terceira Força Aérea como um todo;
•
Maximizar o treinamento da Aviação de Caça;
•
Maximizar o treinamento da Aviação de Ataque;
•
Maximizar o treinamento da Aviação de Reconhecimento.
Isto pode ser formulado matematicamente como:
9
Max z1 =
∑ f (x )
k =1
k
k
9
f ( x ) + f 2 ( x2 )
Max z2 = 1 1
2
f ( x ) + f 4 ( x4 ) + f5 ( x5 )
Max z3 = 3 3
3
f ( x ) + f 7 ( x7 ) + f8 ( x8 ) + f9 ( x9 )
Max z4 = 6 6
4
9
SA.:
∑g
k =1
k
( xk ) ≤ 32000
| f1 ( x1 ) − f 2 ( x2 ) | ≤ 10%
| f3 ( x3 ) − f 4 ( x4 ) | ≤ 10%
| f3 ( x3 ) − f5 ( x5 ) | ≤ 10%
| f 4 ( x4 ) − f5 ( x5 ) | ≤ 10%
f k ( xk ) ≥ 30%, ∀ k ∈ {1,2,...,9}
f k ( xk ) ≤ 100%, ∀ k ∈ {1,2,...,9}
onde: xk = quantidade de horas voadas por piloto na aeronave k .
73
VII.2. Aplicação da Metodologia Proposta
Fase 1: Pontos Interiores
O primeiro passo é a obtenção do ponto interior viável inicial x . Para tanto, o
seguinte PPL auxiliar é formulado:
n


Min  My * + ∑ xi 
i =1


SA.: Ai x + S Ii + β i y * = bi ,
i ∈ {restrições ≤ }
Aj x − S I j + βi y* = b j + ε * , j ∈ {restrições ≥ }
A j x + β y *i = b j ,
xk − S Ik +m + ε * y * = ε * ,
j ∈ {restrições = }
(7.1)
k = {1, 2,..., n}
y* , S I ≥ 0
onde M é um número muito grande
Ao fazer ε * igual a um e calcular o vetor β através da seguinte fórmula:
β i = bi − Aiε * − ε * ,
i ∈ {restrições ≤ }
β i = b j − Aj ε * + 2ε * , j ∈ {restrições ≥ }
β i = b j - Aj ε * ,
(7.2)
j ∈ {restrições = }
obteremos:
β T = (31823,089
7,799 10, 201
7,799 10,201
9,000
9,000
6, 425 24,425 67,086 66,914 66,914 67,371 66,086
66,086 66,086 65,757 65, 229 278,000 266,000 266,000
298,000 208,000 208,000 208,000 185,000 148,000)
Fazendo o ponto inicial do PPL auxiliar igual à:
T
T
T
x 0 = ( x S I y * ) = (ε * ε * 1)
e resolvendo o seguinte PPL auxiliar:
74
9
Min 1000 y * + ∑ xk
k =1
9
SA.:
∑g
k =1
k
( xk ) + S I1 + 31823,089 y * = 32000
f1 ( x1 ) − f 2 ( x2 ) + S I2 + 7,799 y * = 10%
f 2 ( x2 ) − f1 ( x1 ) + S I3 + 10,201 y * = 10%
f 3 ( x3 ) − f 4 ( x4 ) + S I4 + 7,799 y * = 10%
f 4 ( x4 ) − f 3 ( x3 ) + S I5 + 10, 201 y* = 10%
f 3 ( x3 ) − f5 ( x5 ) + S I6 + 9,000 y* = 10%
f 5 ( x5 ) − f 3 ( x3 ) + S I7 + 9,000 y * = 10%
f 4 ( x4 ) − f5 ( x5 ) + S I8 + 6, 425 y * = 10%
f5 ( x5 ) − f 4 ( x4 ) + S I9 + 24,425 y * = 10%
k +9
+ β k + 9 y * = 30% + 1%, k = {1,2, ... ,9}
k +18
+ β k +18 y * = 100%, k = {1,2, ... ,9}
f k ( xk ) − S I
f k ( xk ) + S I
xk − S I
k + 27
+ y * = 1, k = {1, 2, ... ,9}
obteremos o seguinte ponto inicial para a fase um:
 T-27   67, 086 
 AT-26   66, 914

 
 A-1   66, 914

 
 C-98   67,371
x =  R-95  =  66, 086

 
 R-35   66, 086
 R-99   66, 086

 
 F-5E   65, 757
 F-103   65, 229


 
Solicitar ao DM a velocidade que lhe convém. Simularemos que o mesmo
desejou ∆t = 10 .
Formular o seguinte PPL:
p


Min  y + − y − − ε ∑ Ck x 
k =1


SA.: C j x + w j y + − w j y − − S F = b j , j ∈ G
Ai x + S I = bi ,
x, y + , y − , S F , S I ≥ 0
75
i∈ R
(7.3)
FAe III

  31, 000 

  31, 000
Ataque

=
Fazer o vetor φ = C x =
.
 Reconhecimento   31, 000

 
Caça

  31, 000 
Questionando o DM sobre o valor médio que o mesmo acredita que as FO’s
venham a atingir, obteremos φ = 80, 000 * 50% = 40, 000 .
Fazer o vetor de pesos w igual a:
φ = 40, 000, se k ∈ G
.
wk := 
se k ∈ R
0, 000,
Calcular o vetor κ de modo que:
κ i = { bi − Ai x | i ∈ R}
κ T = (20355,150 10, 000 10, 000
10, 000 10, 000
10, 000 10, 000
10, 000 10, 000
3, 086
2,914
2,914
3,371
2, 086
2, 086 2, 086
1,757
1, 229 212,914 201, 086 201, 086
232, 629 143,914 143,914 143, 914 121, 243 84, 771)
Fazer o ponto inicial:
x 0 = ( xT
S IT
y+
y−
(
T
T
SFT ) = x
κ T 1, 000 1, 000 eT
)
T
Fazer v = 1 o contador do número de iterações do método de pontos interiores;
fazer π = 1 o contador de soluções intermediárias e fazer mud = S .
Fazer o vetor inicial de soluções intermediárias:
FAe III

  31, 000 

 
Ataque
1

 =  31, 000 .
sol = φ =
 Reconhecimento   31, 000

 
Caça

  31, 000 
FAe III

 1, 000 

  1, 000
Ataque
=
Fazer: µ 1 = 
.
 Reconhecimento   1, 000

 
Caça

 1, 000 
76
Apresentar o vetor de crescimento µ , os valores das FO’s (vetor sol1 ) e
questionar o DM se o mesmo deseja mudar o vetor de crescimento. No nosso
exemplo, o DM não quis modificar o vetor de crescimento µ .
Atualizar o vetor b de acordo com o seguinte:
 31,000  1,000 
 41,000 

 


31,000  1,000 
41,000
v −1

b j = C j x + µ j ∆t =
+
*10,000 = 
 31,000  1,000 
 41,000

 


 31,000  1,000 
 41,000 
Fazer y + (componente de x v −1 ) o menor inteiro positivo que atenda às
restrições:
C j x v−1 + ( y + − 1) w − b j > 0, ∀ j ∈ G
y + ≥ 2, 000
No nosso exemplo: y + = 2, 000 .
Atualizar o vetor S F (componente de x v −1 ) de modo que:
b j − C j x v −1 − ( y + − 1) w + S Fj = 0, 000, ∀ j ∈ G
 30, 000 
 30, 000
No nosso exemplo: S F = 
.
 30, 000

 30, 000 
Fazer mud = N .
A formulação (7.3), com os valores numéricos do nosso exemplo, fica, na forma
matricial:
77
Ataque
Reconhecimento
Caça
Variáveis de Folga das Metas Inflexíveis
T-27 AT-26 A-1 C-98 R-95 R-35 R-99 F-5E F-103
Pesos
S I1 S I 2 S I 3 S I 4 S I 5 S I 6 S I 7 S I8 S I 9 S I10 S I11 S I12 S I13 S I14 S I15 S I16 S I17 S I18 S I19 S I 20 S I 21 S I 22 S I 23 S I 24 S I 25 S I 26 S I 27 y +
y
−
V. Folga M. Flex.
RHS
S F1 S F2 S F3 S F4
b
FAE III
0,04 0,04 0,04 0,03 0,05 0,05 0,05 0,06 0,09 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 40,00-40,00-1,00 0,00 0,00 0,00 40,357
Ataque
0,11 0,11 0,11 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 40,00-40,00 0,00 -1,00 0,00 0,00 32,554
Reconhe. 0,00 0,00 0,00 0,07 0,12 0,12 0,12 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 40,00-40,00 0,00 0,00 -1,00 0,00 38,759
Caça
0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,28 0,41 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 40,00-40,00 0,00 0,00 0,00 -1,00 55,258
Recursos 6,15 28,68 47,67 1,00 3,03 5,17 8,86 25,57 49,78 1,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 32000,00
10% ataque 0,32 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,001,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
8,78
10% ataque -0,32 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
11,22
10% ataque 0,32 0,00 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
8,78
10% ataque -0,32 0,00 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
11,22
10% ataque 0,00 0,34 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
10,00
10% ataque 0,00 -0,34 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
10,00
10% caça 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -0,57 0,81 0,000,00 0,00 0,00 0,00 0,00 0,00 -1,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
5,67
10% caça 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -0,57 0,81 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
25,67
min
1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
min
0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
64,00
64,00
min
0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 -1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00
max
1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 280,00
max
0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 268,00
max
0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 268,00
max
0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 300,00
max
0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 210,00
max
0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 210,00
max
0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,000,00 0,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 210,00
max
0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 187,00
max
0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 150,00
FO
-4
-1e
-1e
-4
-1e
-4
-1e
-4
-1e
-4
-1e
-4
-1e
-4
-1e
-4
-1e
-4
0,000,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 -1,00 0,00 0,00 0,00 0,00
78
O ponto inicial x 0 ficará:
T
x 0 =(67,086 66,914
66,914 67,371 66,086 66,086 66,086
65,757 65,229 20355,150 10,000 10,000 10,000 10,000
10,000 10,000
10,000 10,000
3,086
2,914
2,914
3,371 2,086
2,086 2,086
1,757
1,229 212,914
201,086 201,086
232,629 143,914 143,914 143,914 121,243
84,771 2,000
1,000 30,000 30,000 30,000 30,000)
Observemos que o vetor b j na formulação matricial está com os valores
diferentes do estipulado anteriormente. Isto se deve aos valores dos termos livres b
das funções capacitação ( f ( x) = ax + b ), cujo somatório foi subtraído do valor
estipulado anteriormente.
Resolvendo, com o valor de ρ = 0,100 , as diversas iterações pelo método dos
pontos interiores, até que ( y − )v ≥ ( y + )v , obteremos o seguinte ponto no espaço
objetivo:
FAe III

  38, 790 

  38, 779
Ataque
=
sol 2 = 
 Reconhecimento   38, 646

 
Caça

  39, 096 
Apresentando o vetor de crescimento µ , os valores das FO’s (vetor sol 2 ) e
questionando o DM se o mesmo deseja mudar o vetor de crescimento, o mesmo
respondeu que desejaria que Aviação de Caça tivesse um crescimento três vezes
maior e que a Aviação de Ataque tivesse um crescimento duas vezes maior que as
demais. Isto nos leva ao seguinte vetor de crescimento:
FAe III

  1, 000 

  2, 000
Ataque
2

=
µ =
 Reconhecimento   1, 000

 
Caça

  3, 000 
Que depois de normalizado ficará:
T
µ = ( 0,571 1,143 0,571 1,714 )
79
Atualizando o vetor b j teremos:
 38, 790   0,571
 44,505 

 


38, 779   1,143 
50, 207
v −1

b j = C j x + µ j ∆t =
+
*10 = 
 38, 646   0,571
 44,361

 


 39, 096   1, 714 
 56, 238 
Fazendo y − = 1 e calculando o valor de y + , obteremos y + = 2 .
Atualizando S F teremos que: S FT = ( 34, 286
28,571 34, 286 22,857 ) .
Resolvendo, com o valor de ρ = 0,100 , as diversas iterações pelo método dos
pontos interiores, até que ( y − )v ≥ ( y + )v , obteremos o seguinte ponto no espaço
objetivo:
FAe III

  52, 614 

  53,510
Ataque
=
sol 3 = 
 Reconhecimento   47,820

 
Caça

  60,859 
Prosseguindo desta maneira, listaremos a seguir apenas os vetores de
crescimento fornecidos pelo DM, o vetor b j
gerado, assim como a solução
intermediária:
 1, 000 
 2, 000 
3

µ =
 1,500 


 3, 000 
 57,947 
 64,176 

bj = 
 55,820 


 76,859 
 69,185 
 70, 029
4
sol = 
 61, 436

 83, 414 
 1, 000 
 1, 200 
4

µ =
 1,100 


 0,900 
 78, 708 
 81, 457 

bj = 
 71,912 


 91,986 
 82,603 
 82,178
5
sol = 
 77, 490

 93, 465 
 1, 000 
 2, 000 
5

µ =
 1, 000 


 2, 000 
 89, 269 
 95,511 

bj = 
 84,157 


 106, 798 
 82,584 
 85,109
6
sol = 
 73, 783

 96, 400 
80
O mecanismo de parada da sol 6 foi o gap < 1,000e −4 , e não ( y − )v ≥ ( y + )v ;
logo, a fase um termina. Notemos que o mecanismo de término da fase um poderia
também ter sido o fato de que tanto a FO1 quanto a FO3 tiveram seus valores
decrescidos em relação à solução intermediária anterior. A partir deste ponto, ao
iniciar a fase dois, existirá a necessidade do estabelecimento de trade-off’s entre as
FO’s.
A gráfico 7.1 ilustra os valores das soluções intermediárias apresentadas ao
DM. Observemos que a característica WIN-WIN esteve presente em quase toda a fase
um. A existência total ou parcial da característica WIN-WIN, durante a fase um,
dever-se-á ao vetor crescimento fornecido pelo DM na última interação com o
algoritmo. Se houver mudança considerável no vetor de aspirações, a característica
WIN-WIN não existirá no ultimo passo dado pela fase um.
Gráfico 7.1
81
Fase 2: Pareto Race
Inicialmente, atualizamos as componentes do vetor b j com os valores
assumidos pela última solução intermediária da fase um:
FAe III

  82, 584 

  85,109
Ataque

=
bj =
 Reconhecimento   73, 783

 
Caça

  96, 400 
Fazendo os limites de variação superior e inferior igual à:
LS j = b j + φ
2, 000
, ∀ j∈G
LI j = b j − φ 2, 000 , ∀ j ∈ G
teremos:
LS
LI
FAe III
102,584
62,584
Ataque
105,109
65,109
Reconhecimento
93,783
53,783
Caça
116,400
76,400
Fazer:
∆b k , se k ∈ G
wk := d k := 
0, 000, se k ∈ R
82
Formular o seguinte PPL:
p


Min  y + − y − − ε ∑ Ck x 
k =1


SA.: C j x + w j y + − w j y − ≥ b j + td j , j ∈ G
Ai x ≤ bi ,
(7.4)
i∈ R
x, y + , y − ≥ 0
Que resolvido pelo SIMPLEX para t = 0, 000 nos fornecerá o primeiro ponto
localizado na fronteira não dominada:
FAe III

  82,597 

  85,122
Ataque
7

=
sol =
 Reconhecimento   73, 796

 
Caça

  96, 412 
Observemos que a sol 7 está bem próxima da sol 6 . Questionando o DM se o
mesmo está satisfeito com a solução, o mesmo diz que desejaria que a FO2 (Ataque)
tivesse seu valor aumentado e que a velocidade seria ∆t = 0, 020 . Para tanto, os
vetores w e d , já normalizados, ficarão:
 43, 636 
 35,556 
 29, 091 
 53,333


w=
e d =
 43, 636 
 35,556



 43, 636 
 35,556 
Atualizar o vetor b j com os valores da sol 7 . Resolvendo o PPL (7.4) com os
vetores w e b j atualizados, faremos a seguinte análise de sensibilidade:
B −1 (b + td ) ≥ 0, 000
que nos fornecerá o seguinte intervalo de variação:
[t − t1; t + t2 ] = [0, 000; 0, 064]
83
Prosseguindo nesta direção, com incrementos ∆t = 0, 020 teremos:
t=0,000
t=0,020
t=0,040
t=0,060
t=0,064
FAe III
82,597
82,405
82,213
82,021
81,978
Ataque
85,122
85,422
85,722
86,023
86,089
Reconhecimento
73,796
73,358
72,919
72,481
72,384
Caça
96,412
95,974
95,535
95,097
95,000
Neste ponto é atingida uma aresta do politopo. Para continuar nesta direção,
realizaremos uma mudança de base, que, no nosso exemplo, é a troca da variável S I8
pela S I26 . Computando a nova base e realizando novamente a análise de
sensibilidade, obteremos:
[t − t1; t + t2 ] = [0, 064; 0,385]
Prosseguindo nesta direção, com incrementos ∆t = 0, 020 teremos:
t=0,064
t=0,084
t=0,104
t=0,124
FAe III
81,978
81,766
81,553
81,340
Ataque
86,089
86,374
86,659
86,944
Reconhecimento
72,384
71,923
71,461
71,000
Caça
95,000
94,539
94,077
93,616
Neste ponto, o DM desejou fixar o valor da FO2 e aumentar o da FO3. Isto nos
gerou os seguintes vetores normalizados:
 60, 000 
 44,912 
 0, 000 

 e d =  0, 000
w=
 40, 000 
 70,175



 60, 000 
 44,912 
84
Atualizemos o vetor b j com os valores da última solução. Resolvendo o PPL
(7.4) com os vetores w e b j atualizados, teremos a seguinte análise de sensibilidade:
[t − t1; t + t2 ] = [ 0, 000; 0,363]
Prosseguindo nesta direção, com incrementos ∆t = 0, 020 teremos:
t=0,000
t=0,020
t=0,040
…
t=0,100
FAe III
81,340
81,565
81,789
82,462
Ataque
86,944
86,944
86,944
86,944
Reconhecimento
71,000
71,633
72,266
74,166
Caça
93,616
93,359
93,101
92,330
Supondo que o DM esteja satisfeito com tal resultado, a busca é encerrada.
Os valores que as variáveis naturais assumem na solução preferida são:
 T-27   260, 285 
 AT-26   220, 237

 
 A-1   220, 237

 
 C-98   300, 000
x =  R-95  =  210, 000

 
 R-35   140, 469
 R-99   64, 000

 
 F-5E   182,308
 F-103   134, 434


 
85
Os valores que a função capacitação assumem na solução preferida são:
 T-27   93, 611 
 AT-26   83, 611

 
 A-1   83, 611

 
 C-98   100, 000
f ( x) =  R-95  =  100, 000

 
 R-35   66, 663
 R-99   30, 000

 
 F-5E   97,330
 F-103   87,330

 

FAe III

  82, 462 

  86,944
Ataque

=
f ( x) =
 Reconhecimento   74,166

 
Caça

  92,330 
86
CAPÍTULO VIII
CONCLUSÃO
Foi proposta por este trabalho uma abordagem para a resolução de problemas
de Programação Linear Multi-Objetivo que une duas correntes bem distintas: a de
Pontos Interiores e a Abordagem Visual denominada Pareto Race. Com o objetivo de
sanar as deficiências de cada abordagem, assim como de realçar seus pontos fortes,
a metodologia por nós sugerida utiliza-se de duas fases. Na primeira fase, um
algoritmo inédito de Pontos Interiores, cuja principal vantagem é a característica
WIN-WIN durante a maior parte da trajetória pelo interior do politopo, guia o DM para a
fronteira não dominada de maneira fácil e muito intuitiva, pois a única interação que o
DM tem que fazer é explicitar o vetor de crescimento. Tal vetor de crescimento é o
indicativo de quão maior ou menor será o crescimento de uma FO em relação às
demais. Após a obtenção de um ponto localizado na fronteira não dominada, caso o
DM deseje prosseguir na busca da solução preferida, o método Pareto Race será
utilizado na fase dois da metodologia proposta.
Para uma melhor compreensão da dinâmica proposta, uma pequena
introdução foi feita no capítulo primeiro. Nesta introdução, o objetivo do trabalho foi
enunciado, assim como a estrutura que o texto iria seguir.
No capítulo segundo, um pequeno sumário tanto do histórico da abordagem
Multi-Objetivo quanto da metodologia de Pontos Interiores foi realizado. Neste
sumário, foi possível observar quão moderna é a abordagem proposta por este
trabalho.
Para facilitar o trabalho do leitor, foram reunidas, no capítulo terceiro, todas as
Notações, Definições e Ferramentas utilizadas neste texto. As demonstrações
matemáticas não triviais necessárias para o perfeito entendimento da mecânica
utilizada pelo algoritmo proposto, foram reunidas na sub-seção chamada de
Ferramentas.
A metodologia para a resolução de problemas de Programação Linear
denominada Pontos Interiores foi discutida no quarto capítulo. Especificadamente, o
algoritmo Afim Escala Primal, o escolhido dentre os vários de Pontos Interiores
disponíveis, foi extensivamente explorado neste capítulo. Para os leitores não
familiarizados com Programação Não Linear, que é a base do algoritmo Afim Escala
Primal, uma pequena introdução ao assunto foi feita no sub-capítulo IV.1.
87
A Abordagem Visual para problemas MOLP foi estudada no capítulo quinto,
onde, além da descrição formal do algoritmo, um extenso exemplo numérico foi
apresentado.
Finalmente, nos capítulos sexto e sétimo, a metodologia proposta por este
trabalho foi formalmente apresentada, assim como um exemplo numérico da sua
utilização. No exemplo numérico, foi realizado um estudo da distribuição orçamentária
realizada pela Força Aérea Brasileira.
Como o objetivo primeiro da nossa proposta é facilitar o trabalho do DM na
obtenção da solução preferida, o estudo detalhado do algoritmo feito no capítulo
sétimo demonstrou que o mesmo (objetivo primeiro) foi alcançado. Ao explorar a
característica WIN-WIN, o trabalho do DM foi facilitado pela não existência da
necessidade do estabelecimento de trade-off’s entre as FO’s. Caso após a obtenção
da primeira solução não dominada, o DM deseje continuar a busca, trade-off’s deverão
ser feitos entre as FO’s, porém, pelo fato da existência explicita ou implícita da função
utilidade na mente do DM, esta função utilidade deixa sua marca nas diversas
interações do DM com a fase um do algoritmo: a definição do vetor de crescimento.
Logo, a primeira solução não dominada estará próxima da solução preferida final.
Adicionalmente ao objetivo primário, nossa metodologia proporciona uma
menor possibilidade da existência do problema da parada prematura. Ao fornecer uma
solução não dominada próxima à solução preferida final, a probabilidade da ocorrência
de tal problema fica reduzida, pois a parte da busca realizada com trade-off’s fica
diminuta.
Podemos concluir da análise da metodologia proposta que:
•
A mesma fornece uma solução localizada na fronteira não dominada:
subentende-se que um DM racional não irá se interessar por soluções
dominadas;
•
Ao utilizar uma geometria na qual a característica WIN-WIN é
predominante, a fase um do algoritmo facilita o trabalho do DM: é
sabido e extensivamente discutido na literatura que uma das tarefas
mais árduas ao DM é o estabelecimento de trade-off’s entre FO’s. Ao
possibilitar a obtenção da solução não dominada inicial por uma
metodologia que não exige esta penosa tarefa, o DM tem seu trabalho
facilitado;
88
•
O algoritmo proposto possibilita a pesquisa de toda a fronteira não
dominada: ao utilizar-se do bem conhecido e provado Pareto Race na
sua fase dois, o algoritmo proposto consegue prover o DM de uma
ferramenta útil e de fácil utilização para a busca da solução preferida;
•
A metodologia sugerida diminui a probabilidade da ocorrência do
problema da parada prematura: tal problema ocorre quando ao DM é
exigida uma quantidade grande de trade-off’s entre as FO’s. Ao utilizarse da fase um para a obtenção da solução não dominada inicial, o
algoritmo possibilita a redução do tamanho da busca a ser realizada
com o Pareto Race. Ao restringir a quantidade de trade-off’s solicitados
ao DM, a possibilidade da ocorrência do problema da parada prematura
fica minimizada.
Como trabalhos futuros, temos:
•
A
implementação
da
metodologia
proposta
em
um
programa
computacional;
•
A realização de estudos de sensibilidade nos resultados gerados;
•
A validação da metodologia ora proposta através da aplicação
exaustiva da mesma em diversos ambientes e com diferentes DM’s;
•
A realização de análises comparativas do algoritmo proposto com
outros algoritmos existentes;
•
A aplicação do algoritmo proposto em contextos mais amplos;
•
A análise de desempenho computacional do algoritmo proposto com a
substituição do método Afim-Escala Primal por outros métodos de
pontos interiores mais modernos, como, por exemplo, os da classe de
trajetória central (barreira passos curtos e barreira passos longos).
89
CAPÍTULO IX
BIBLIOGRAFIA
ARBEL, A., 1993a, “An Interior Multiobjective Linear Programming Algorithm”,
Computers & Operations Research, n. 20, pp. 723-735.
ARBEL, A., 1993b, “A Weighted-Gradient Approach to Multi-Objective Linear
Programming Problems Using the Analytic Hierarchy Process”, Mathematical
Computations and Modelling, Vol. 17, n. 4/5, pp. 27-39.
ARBEL, A., 1993c, Exploring Interior-Point Linear Programming: Algorithms and
Software. London, The MIT Press.
ARBEL, A., 1994, “Anchoring points and cones of opportunities in interior multiobjective
linear programming problems”, Journal of the Operational Research Society, n.
45, pp. 83-96.
ARBEL, A., KORHONEN, P., 1996, “Using aspiration levels in an interactive interior
multiobjective linear programming algorithm”, European Journal of Operational
Research, n. 89, pp. 193-201.
ARBEL, A., KORHONEN, P., 2001, “Using objective values to start multiple objective
linear programming algorithms”, European Journal of Operational Research, n.
128, pp. 587-596.
BARNES, E. R., 1986, “A Variation on Karmarkar’s Algorithm for Solving Linear
Programming Problems”, Mathematical Programming, n. 36, pp.174-182.
BENAYOUN, R., MONTGOLFIER, J., TERGNY, J., LARITCHEV, O., 1971, “Linear
Programming with Multiple Objective Functions: Step Method (STEM)”,
Mathematical Programming, Vol. 1, n. 3, pp. 366-375.
CAUCHY, A. L., 1821, Cours D’Analyse de L’École Royale Polytechinque, 1.: Analyse
Algebrique. Paris, Imprim. Royale.
CAVALIER, T., SOYSTER, A., 1985, Some Computational Experience and a
Modification of the Karmarkar Algorithm. The Pennsylvania State University,
ISME Working Paper, pp. 85-105.
CLIMACO, J., ANTUNES, C. H., ALVES, M. J., 1996, Programação Linear
Multiobjectivo – Métodos Interactivos, “Software” e Aplicações. Coimbra, Secção
de Textos da Faculdade de Economia da Universidade de Coimbra.
90
DANTZIG, G. B., 1963, Linear Programming and Extensions. Princeton, Princeton
University Press.
DIKIN, I. I., 1967, “Iterative solution of problems of linear and quadratic programming”,
Soviet Mathematics Doklady, n. 8, pp. 674-675.
DIKIN, I. I., 1974, “On the speed of an iterative process”, Upravlyaemye Sistemi, n. 12,
pp. 54-60.
GEOFFRION, A. M., DYER, J. S., FEINBERG, A., 1972, “An Interactive Approach for
Multicriterion Optimization, with an Application to the Operation of an Academic
Department”, Management Science, Vol. 19, n. 4, pp. 357-368.
GONZAGA, C. C., 1989, Algoritmos de Pontos Interiores para Programação Linear.
Rio de Janeiro, Instituto de Matemática Pura e Aplicada do CNPq.
KAHNEMAN, D., THERSKY, A., 1979, “Prospect theory: An analysis of decisions
under risk”, Econometrica, n. 47, pp. 262-291.
KARMARKAR, N., 1984, “A new polynomial time algorithm for linear programming”,
Combinatorica, n. 4, pp.373-395.
KHACHIYAN, L. G., 1979, “A polynomial algorithm for linear programming”, Soviet
Mathematical Doklady, n. 20, pp. 191-194.
KORHONEM, P., LAAKSO, J., 1986a, “A Visual Interactive Method for Solving the
Multiple Criteria Problem”, European Journal of Operational Research, n. 24, pp.
277-287.
KORHONEM, P., LAAKSO, J., 1986b, “Solving Generalized Goal Programming
Problems Using a Visual Interactive Approach”, European Journal of Operational
Research, n. 26, pp. 355-363.
KORHONEM, P., MOSKOWITZ, H., WALLENIUS, J., 1990, “Choice Behavior in
Interactive Multiple Criteria Decision Making”, In: Annals of Operations Research,
n. 23, pp. 161-179.
KORHONEM, P., WALLENIUS, J., 1988, “A Pareto Race”, Naval Research Logistics,
n. 35, pp. 615-623.
OLIVEIRA, P. R., 1989, Introdução à programação não linear. Rio de Janeiro, Gráfica
da UFRJ / Coordenação do Programa de Pós Graduação em Engenharia.
STEUER, R. E., 1977, “An Interactive Multiple Objective Linear Programming
Procedure”, TIMS Studies in the Management Science, n. 6, pp. 225-239.
91
STEUER, R. E., 1989, Multiple Criteria Optimization: Theory, Computation, and
Application. Reprinted ed, Malabar, Robert E. Krieger Publishing Company.
STEUER, R. E., CHOO, E. U. 1983, “An Interactive Weighted Tchebycheff Procedure
for Multiple Objective Programming ”, Mathematical Programming, Vol. 26, n. 1,
pp. 326-344.
VANDERBEI, R. J., MEKETON, M. J., FREEDMAN, B. A., 1986, “A Modification of
Karmarkar’s Linear Programming Algorithm”, Algorithmica, n. 1, pp. 395-407.
WIERZBICKI, A. P., 1980, “The Use of Reference Objectives in Multiobjective
Optimization”, In: Fandel, G., Gal, T., Multiple Objective Decision Making, Theory
and Application, New York, Springer-Verlag.
WIERZBICKI, A. P., 1982, “A Mathematical Basis for Satisficing Decision Making”,
Mathematical Modelling, Vol. 3, n. 5, pp. 391-405.
WIERZBICKI, A. P., 1983, “Critical Essay on the Methodology of Multiobjective
Analysis”, Regional Science and Urban Economics, Vol. 13, n. 1, pp. 5-29.
ZIONTS, S., WALLENIEUS, J., 1976, “An Interactive Programming Method for Solving
the Multiple Criteria Problem”, Management Science, Vol. 22, n. 6, pp. 652-663.
92