AGREGAÇÃO DE UMA ABORDAGEM “WIN-WIN” À ...helcio/Agregacao.pdfii VIEIRA JUNIOR, HÉLCIO Agregação de uma Abordagem “WIN-WIN” à Modelagem Multi-Objetivo [Rio de Janeiro]

AGREGAÇÃO DE UMA ABORDAGEM “WIN-WIN” À MODELAGEMMULTI-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

ii

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)

iii

À minha amada esposa Nathália,

cujo amor, suporte e compreensão

permitiram que eu alçasse mais

este degrau na vida.

iv

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


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.

v

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


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 Affine-

Scaling 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.

vi

Í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

vii

“Para ser grandesê inteiro, nada teu

exagera ou exclui, ... esê todo em cada coisa

põe quanto és nomínimo que fazes.

Assim em cada lagoa tua lua brilha

porque alta vive!”

Fernando Pessoa

1

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

2

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 Pontos Interiores Pareto Race

Aspecto

positivo

Obtenção de uma solução na fronteira

não dominada que, ou seja a preferida

pelo DM, ou esteja próxima àquela.

Possibilidade de vasculhar toda

fronteira não dominada na busca

da solução preferida pelo DM.

Aspecto

negativo

O algoritmo não provê meios de

continuar a busca após atingir a

fronteira não dominada.

O algoritmo não provê um ponto

inicial de busca próximo à

solução preferida pelo DM.

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 trade-

off entre as FO´s, pois para aumentar o valor de uma, obrigatoriamente outra deverá

ter seu valor diminuído.

3

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.

4

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.

5

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 3.5( )O n 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

6

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).

7

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( ) 0B = . Se det( ) 0B ≠ a matriz

B é dita não singular.

III.1.3. A transposta de uma matriz i x jB∈R é denotada por TB . A matriz TB é obtida

pela troca das linhas pelas respectivas colunas da matriz B , ou seja:

, .Ti j j ib b i I e j J= ∀ ∈ ∀ ∈

III.1.4. A inversa de uma matriz i x jB∈R é denotada por 1B− . A matriz 1B− pré ou pós

multiplicada pela matriz B resulta na matriz identidade:

1 1B B BB I− −= =

Uma matriz i x jB∈R só possuirá inversa se for não singular.

III.1.5. A norma euclidiana de um vetor nx∈R é denotada por || ||x , e equivale a:

2

1|| || ( )

nT

ii

x x x x=

= = ∑

III.1.6. Uma transformação linear : n mA →R R definida em nR com valores em mR , é

representada por uma matriz m x nA∈R .

III.1.7. O espaço imagem de A é definido como:

( ) { | , }m nI A y y Ax x= ∈ = ∈R R

( )I A corresponde ao conjunto de todas as combinações lineares das colunas

da matriz A .

8

III.1.8. O espaço nulo de A é definido como:

( ) { | 0}nN A x Ax= ∈ =R

( )N A corresponde ao conjunto de pontos de nR 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

( ) min{ , }r A m n= .

A menos que o contrário seja dito, trabalharemos sempre em nR , com

matrizes em m x nR 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:

{ | , 0}nS x Ax b x= ∈ = ≥R .

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:

{ | , }kZ z z Cx x S= ∈ = ∈R .

III.1.13. Um ponto nx∈R é um ponto interior de um problema de PL sss x S∈ e

0x > .

III.1.14. Um vetor nh∈R é 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: 1f C∈ . Em geral, se uma função tem

derivada parcial contínua de ordem p , isto é denotado por: pf C∈ .

9

III.1.16 Se 1f C∈ é uma função real em nR , o gradiente de f é definido por:

1 2

( ) ( ) ( )( ) , ,...,n

f x f x f xf xx x x

∂ ∂ ∂∇ = ∂ ∂ ∂

III.1.17 Se 2f C∈ é uma função real em nR , a Hessiana de f em x é definida pela

matriz simétrica n x n:

22 ( )( )

i j

f xf xx x

∂∇ =

∂ ∂

III.1.18 Fórmula de Taylor: para uma função definida em um intervalo aberto T ⊂ Rdiferenciável até a ordem conveniente, pode-se escrever a fórmula de Taylor,

para x h T+ ∈ :

1( ) ( ) ( ) ... ( ) ( , )!

T p T ppf x h f x f x h f x h O x h

p+ = +∇ + + ∇ +

onde:

1( 1)( , ) ( )

( 1)!

pp

phO x h f x hp

θ+

+= ∇ ++

, para algum [0,1]θ ∈ .

A expressão acima ( ( , )pO 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 ( , )pO x h , com

o valor de 1p = ; da mesma forma, para a aproximação quadrática, basta

pegarmos os três primeiros termos da fórmula de Taylor e utilizarmos um

2p = na expressão do erro da aproximação.

III.1.19 O complemento ortogonal de um subespaço { | , }nU x x Av v= = ∈R é

{ | 0}y yA = . A notação disto é y U⊥ .

10

III.1.20 MOLP – Multiple Objective Linear Program – Programação Linear Multi-

Objetivo: é definida como:

1 1

2 2

max { }max { }

...max { }

.:0

p p

C x zC x z

C x z

SA Ax bx

==

=

≤≥

ou, simplificadamente:

max.:z Cx

SA x S=∈

III.1.21 pMétrica L : Uma métrica em nR é a função distância que associa a cada par

de vetores , nx y∈R um escalar || ||x y− ∈R e é definida por:

1

1

1,2, ... ,

|| || | | {1, 2,3,...}

|| || {| |}

n pp

p i ii

i ii n

x y x y p

x y Max x y=

∞ =

− = − ∈

− = −

∑

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 b

Variaveis básicas 1( )BA A− 1( )BA b−

jc 1( ) ( )TB Bc c A A−− 1( ) ( )T

B Bc A b−−

11

III.2. Ferramentas

A seguir algumas ferramentas que terão utilidade no decorrer do trabalho são

esplandas:

III.2.1. Um vetor nv∈R é ortogonal a ( )TI A sss ( )v N A∈ .

o Prova: ( )Tv I A⊥ sss , 1, ... ,Tiv A i m⊥ = , onde iA representa as linhas

de A . Esta última relação é equivalente a 0, 1, ... ,iA v i m= = , ou 0Av = ,

o que completa a prova.

Deste fato conclui-se que nR é a soma direta dos subespaços ( )N A e ( )TI A ,

isto é, dado qualquer vetor nw∈R , ele pode ser escrito como:

N Iw w w= + , onde ( )Nw N A∈ e ( )TIw I A∈ .

III.2.2. A matriz TAA é não singular.

o Prova: Por absurdo suponha que para algum 0, 0Ty AA y≠ = .

Multiplicando esta expressão à esquerda por Ty :

0, ( ) ( ) 0T T T T Ty AA y ou A y A y= = .

Esta última expressão é equivalente a || || 0TA y = , ou ainda a 0TA y = . Isto

é impossível uma vez que as colunas de TA são linearmente

independentes (veja III.1.9), completando, assim, a prova.

III.2.3. 1( )T TIw A AA Aw−= .

o Prova: Sabemos que o vetor w pode ser decomposto em:

N Iw w w= +

Como ( )TIw I A∈ , existe my∈R tal que TIw A y= , e então:

TNw w A y= + .

Multiplicando à esquerda pela matriz A :

TNAw Aw AA y= +

12

Como, por definição, 0NAw = (vide III.1.8):

TAw AA y=

E, como a matriz TAA é não singular (vide III.2.2), a mesma possui uma

inversa, que pré- multiplicará a expressão anterior:

1 1

1

1 1

( ) ( )( )( ) ( )

T T T

T

T T

AA Aw AA AA yAA Aw I yAA Aw y ou y AA Aw

− −

−

− −

=

=

= =

.

Substituindo a expressão acima em TIw A y= completamos a prova.

III.2.4. Nw Pw= , onde 1( )T TP I A AA A−= − .

o Prova: N Iw w w= + pode ser escrito como N Iw w w= − .

Substituindo 1( )T TIw A AA Aw−= na expressão acima temos:

1( )T TNw w A AA Aw−= −

Colocando w em evidência, completamos a prova:

1[ ( ) ]T TNw I A AA 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 nh∈R é viável a partir de x sss ( )h N A∈ .

o Prova: Se nh∈R é 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 0Ah = , o que é equivalente a

( )h N A∈ .

13

III.2.6. Considere um ponto x S∈ e uma direção nh∈R viável a partir de x , então:

Se 0h ≥ então x hλ+ é viável para qualquer 0λ ≥ ;

Senão, o maior valor de λ tal que x h Sλ+ ∈ é dado por:

min{ | 0, 1, ..., }ii

i

x h i nh

λ = − < =

o Prova: Como ( )h N A∈ (vide item III.2.5), então para qualquer λ∈Rtem-se que ( )A x h bλ+ = .

Se 0h ≥ , então para qualquer 0, 0x hλ λ≥ + ≥ , 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 1, ...,i n= associa-se um valor:

sup{ | 0}i i ix hλ λ λ= + ≥

Se 0ih < então 0ii ix hλ+ = e conseqüentemente ii

i

xh

λ = − . O maior

passo agora que garante a viabilidade é 1, ... ,min ii n λ= , o que é equivalente à

expressão: min{ | 0, 1, ..., }ii

i

x h i nh

λ = − < = .

14

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{ | || || 1}Tg h h ≤

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:

| | 1|| || . || ||xy

x y≤ ou 1 1

|| || . || ||xy

x y− ≤ ≤

Logo, a solução para o problema de minimização em uma bola é obtida

imediatamente:

|| ||.|| ||Tg 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 || || 1h ≤ , deveremos normalizar o vetor resultante h :

|| ||ghg

= −

Isto é chamado de direção de máximo declive.

15

Algoritmos para o problema:

( ). : n

Min f xSA x∈R

geram, a partir de um ponto inicial 0x , sucessivamente, os pontos:

1 , 0k kx x h kλ+ = + ≥

nos quais o ponto 1kx + é 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:

( ) ( )k kf x h f x+ <

e, como os seguintes problemas são equivalentes:

( ). : n

Min f xSA x∈R ≡

( ). : n

Min f x hSA h

+

∈R

a solução ideal pode ser obtida calculando-se a direção h através de:

( ). : n

Min f x hSA h

+

∈R

Dado um ponto nx∈R , no qual a função ( )f x h+ é diferenciável, a sua

aproximação linear pela Fórmula de Taylor (vide III.1.18) é:

( ) ( ) ( )Tf x h f x f x h+ ≅ +∇

Como o termo ( )f x é constante (em relação a h ), podemos eliminá-lo,

obtendo o seguinte sub-problema:

( ). :

T

n

Min f x hSA h

∇

∈R

“Observe que, devido à linearidade da função objetivo relativamente a h , a não

ser que x seja um ponto estacionário ( ( ) 0f x∇ = ), 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)

16

( ).: || || 1

T

n

Min f x hSA h

h

∇≤

∈R

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:

( )|| ( ) ||f xhf 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 ”.

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:

1 22. . : 0Max Z x xS A x

= +≥

(4.1)

x

x h+

17

Na figura 4.2 abaixo, temos o ponto inicial arbitrário ( )5,000 3,000Ta = e o

vetor gradiente ( )2,000 1,000Tc = 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:

Figura 4.2

O ponto resultante da minimização da FO através da direção de máximo declive é

( )2,317 1,658Tb = .

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): 1h D h−= , onde 1( , ... , ) 0, 1, ...,n iD diag d d e d i n= > = .

Realizando a mudança de escala no problema (4.1) temos: o ponto a é obtido

através de1

1 5,000 0,000 5,000 1,0000,000 3,000 3,000 1,000

a D a−

− = = =

, e o vetor gradiente c

através de5,000 0,000 2,000 10,0000,000 3,000 1,000 3,000

c Dc

= = =

. Observemos na figura 4.3 o

problema anterior no espaço escalado:

a

b

6,292Z = 13,000Z =

1x

2x

c

18

Figura 4.3

O ponto obtido minimizando o novo gradiente c através da direção de máximo

declive foi: ( )0,042 0,713Tb = . Re-escalando o ponto b novamente para o espaço

original, temos: ( )( ) 0,211 2,138T Tb Db= = . Podemos observar a mecânica deste

procedimento no espaço original através da figura 4.4 abaixo:

Figura 4.4

a

b

c

1x

2x

a

b

6,292Z = 13,000Z =

b

2,560Z =

1x

2x

c

19

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:

11, ( , ... , ) 0, 1, ...,Tn ih DDh onde D diag d d e d i n≤ = > = .

Os eixos coincidem com os eixos coordenados e seus comprimentos valem 1id.

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.: 1

T

T

g hSA h DDh ≤

é facilmente resolvido por uma mudança de variáveis (mudança de escala) h Dh= , o

que resulta em:

1min

.: 1

T

T

g D h

SA h h

−

≤

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 é:

1,|| ||gh onde g D gg

−= − =

No espaço original, a direção resultante é:

1

11

1|| ||

h D hD gh DD g

−

−−

−

=

= −

Que, sem a normalização, fica:

2h D g−= −

20

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

e em um elipsóide) quando restritos a um hiperplano, isto é, Ax b= , onde mxnA∈R ,

correspondem às soluções anteriores projetadas no nulo de A :

Minimização em uma bola:

. : 0|| || 1

TMin g hSA Ah

h=≤

o problema acima tem como solução:

|| ||N

N

ghg

= − , onde Ng Pg=

o Prova: Como N Ig g g= + , onde ( )Ng N A∈ e ( )Ig N A⊥ , podemos

escrever Tg h como:

T T TN Ig h g h g h= +

Para qualquer direção viável ( )h N A∈ , temos que 0TIg h = e, dessa

forma:

T TNg h g h=

O problema original é equivalente a minimizar TNg h em uma bola de

raio unitário, com solução conhecida:|| ||

N

N

gg

.

Sem a normalização, teremos como solução:

Nh g Pg= − = −

Dado um ponto nx∈R , no qual a função ( )f x h+ é diferenciável, a

minimização de sua aproximação linear ( ) ( )Tf x f x h+∇ na bola de raio

unitário restrita a um hiperplano é (sem normalização):

( )h P f x= − ∇

21

Minimização em uma elipsóide:

min.: 0

1

T

T

g hSA Ah

h DDh=

≤

que com a mudança de escala h Dh= fica:

1 1

min

.: 0

|| || 1

e

Tg h

SA Ah

h

onde g D g A AD− −

=

≤

= =

A solução não normalizada é dada pela projeção no nulo de ( )AA P :

Ah P g= −

que, no espaço original, equivale a:

2Ah D P g−= −

Dado um ponto nx∈R , no qual a função ( )f x h+ é diferenciável, a

minimização de sua aproximação linear ( ) ( )Tf x f x h+∇ no elipsóide

restrito a um hiperplano é (sem normalização):

2 ( )Ah D P f x−= − ∇

A idéia exposta acima pode ser mais facilmente observada através da figura

4.5 abaixo, onde o vetor gradiente ( )1 1 2Tc = e a projeção do mesmo (linha

pontilhada) no hiperplano 1 2 3 1x x x+ + = estão plotados:

Figura 4.51x

2x

3x

1

11

c

22

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 0x :

• : 0k =

• Repetir:

o : ( )kh f x= −∇ ⇒Achar uma direção de busca através da direção de

máximo declive.

o Fazer uma busca unidirecional a partir de kx 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:

( ) ( )k kf x h f xλ+ <

o 1 :k kx x hλ+ = +

o : 1k k= +

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 : ( )kh P f x= − ∇ .

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 busca2: ( )kAh D P f x−= − ∇ 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:

23

Figura 4.6

onde temos plotadas as curvas de níveis de duas FO’s: a da esquerda ( 1Z ) uma

FO não linear e a da direita ( 2Z ) uma FO linear. Observemos que na FO não

linear, partindo do ponto A na direção 1h , 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 1h . Na FO linear,

temos que, partindo do ponto D na direção 2h , o valor da função objetivo sempre

decresce. O ponto E é o ultimo ponto que, partindo de D na direção 2h , 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.

A

B

C

E

D

2h

1 20Z =

1 10Z =

2 20Z =

2 10Z =

1h

24

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).

25

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 0x é disponível e que o conjunto

viável é limitado.

Consideraremos o problema de programação linear na sua forma padrão

descrita abaixo:

min.:

0, .

T

n m

c xSA Ax b

xonde x R b R e a matriz A tem dimensão m x n

=≥

∈ ∈

O algoritmo inicia seu processo interativo de uma solução 0x que é tanto

interior quanto viável; isto é:

0 0, 0Ax b x= >

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 newx , enquanto

mantém a viabilidade; isto é:

0

newT T

new

Ax b

c x c x

=

≤

26

Sendo a relação entre as soluções corrente e nova:

0newx x h= +

concluímos que:

0Ah = (4.2)

0Tc h ≤ (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. :

1( )T TnP I A AA A−= −

Para a condição (4.3), utilizando como direção de busca h Pc= − , observamos

que:

2 2|| || 0T T Tc h c Pc c P c Pc= − = − = − ≤

Isto só é válido devido ao fato do operador de projeção P ser simétrico e

idempotente ( 2P 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:

1 2( , ,..., )nD diag x x x=

onde ix é o ésimoi componente da solução corrente 0x .

Utilizando a transformação:

11 0x D x−=

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:

1 1

1 1

1

1 1

min.:

0

Tc xSA A x b

xonde A AD e c Dc

=≥= =

27

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:

: ( )kh P f x= − ∇

Projetando o gradiente da função objetivo (o vetor de custo escalado 1c ) no

espaço nulo de 1A obtemos o vetor 1h :

11 1 1 1 1 1 1 1

1

2 1 2

2 1 2

[ ( ) ]

[ ( ) ][ ( ) ]

[ ( ) ]

T Tn

T T T Tn

T Tn

T T

h Pc I A A A A c

I A D ADA D AD DcD I A AD A AD c

D c A AD A AD c

−

−

−

−

= − = − −

= − −

= − −

= − −

e utilizando a relação entre o espaço escalado e o espaço original dada por:

1h Dh=

temos que o vetor h no espaço original é dado por:

2

2 1 2

[ ][( ) ]

T

T

h D c Aonde AD A AD c

ωω −

= − −

=(4.4)

sendo ω a estimativa do vetor dual.

A nova solução será dada por:

( 1)

: 0 1

min , 0, 1

º

new

ik i

kik

x x hsendo

xh i n

h

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 newx

28

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:

|| || precisãogap h= ≤

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.

29

IV.4. Um Exemplo Numérico

Consideremos o seguinte problema:

1 2

1 2

1 2

1 2

1 2

1 2

2.: 4 5 20

2 7 498 15 12013 9 117

, 0

Max x xSA x x

x xx xx x

x x

+− + ≤

+ ≤+ ≤+ ≤≥

cuja solução ótima é o vértice (0,000; 9,000).

A região viável do problema está diagramada na figura 4.7:

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:

( )0 1,000 1,000 19,000 40,000 97,000 95,000T

x =

Faremos

4,000 5,000 1,000 0,000 0,000 0,0002,000 7,000 0,000 1,000 0,000 0,0008,000 15,000 0,000 0,000 1,000 0,000

13,000 9,000 0,000 0,000 0,000 1,000

A

− =

;

1x

2x

30

Faremos ( )2,000 1,000 0,000 0,000 0,000 0,000Tc = − − ;

Faremos

1,000 0,000 0,000 0,000 0,000 0,0000,000 1,000 0,000 0,000 0,000 0,0000,000 0,000 19,000 0,000 0,000 0,0000,000 0,000 0,000 40,000 0,000 0,0000,000 0,000 0,000 0,000 97,000 0,0000,000 0,000 0,000 0,000 0,000 95,000

D

=

;

Como:

2

2 1 2

[ ][( ) ]

T

T

h D c Aonde AD A AD c

ω

ω −

= − −

=

Temos:

0,008-0,006-0,003-0,004

ω

=

;

Temos:

1,8830,9182,944

-10,189-28,828-32,737

h

=

;

Como:

( 1)

: 0 1

min , 0, 1

º

new

ik i

kik

x x hsendo

xh i n

h

k n da iteração

ρ λρ

λ −

= +

< <

= − ∀ < ≤ ≤

=

Temos: { }1 2 31 1 1min 0; 0; 0; 3,926; 3,365; 2,902 = 2,902h h hλ = > > > ;

31

E, utilizando um 0,800ρ = , temos:

5,3713,13025,83416,34630,07619,000

newx

=

.

Os valores da variável newx nas demais iterações está explicitado na tabela

abaixo:

Iteração 0 1 2 3 4 5 6 7 8 9

1x 1,000 5,371 6,861 7,901 8,747 8,942 8,978 8,995 8,998 9,000

2x 1,000 3,130 2,667 1,503 0,301 0,060 0,027 0,005 0,003 0,000

3x 19,000 25,834 34,109 44,088 53,484 55,466 55,778 55,952 55,978 56,000

4x 40,000 16,346 16,607 22,676 29,402 30,696 30,856 30,973 30,986 31,000

5x 97,000 30,076 25,103 34,245 45,516 47,565 47,773 47,962 47,978 48,000

6x 95,000 19,000 3,800 0,760 0,585 0,217 0,043 0,021 0,004 0,000

Tabela 4.1

O valor de ρ foi mantido em 0,800ρ = até um gap menor que 41,000e− ,

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 newx nas diversas iterações

plotados:

Figura 4.81x

2x

32

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:

1

2

1 2

1 2

. : 2 10, 0

Max xMax xSA x x

x x+ ≤≥

(5.1)

figura 5.1

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 0,000 maximiza

2x

1x

33

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 1x domina 2x sss:1 1 1 2 2 21 2 n 1 2 nz [x ,x ,...,x ] z [x ,x ,...,x ]≥ para todo z|z C∈ , e

1 1 1 2 2 21 2 n 1 2 nz [x ,x ,...,x ] z [x ,x ,...,x ]> para algum z|z C∈ .

o Um ponto 3x é chamado de não dominado se não existir outro ponto 4x

que domine 3x .

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 7,500 para o ponto do ótimo individual da FO2

( )0,000 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.

34

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:

1 1

2 2

max { ( ) }max { ( ) }

...max { ( ) }

.:k k

f x zf x z

f x zSA 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)

35

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):

1,2, ... ,|| || {| |}i ii nx y Max x y∞ =− = −

Utilizemos como ponto de referência no espaço objetivo o ponto kb∈R . 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:

( , , ) j j

j

b C xs b x w Max

w −

=

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:

1( , , )

. : ,0

pj j

kkj

i i

b C xMin s b x w Min Max C x

w

SA A x b i Rx

ε=

−= −

≤ ∈

≥

∑

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).

36

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.

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.

2x

1x

37

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:

1( , , )

. : ,0

pj j j

kkj

i i

b td C xMin s b x w Min Max C x

w

SA A x b i Rx

ε=

+ −= −

≤ ∈

≥

∑

Ao introduzir uma variável y∈R , podemos reescrever a formulação acima

como:

1

( , , )

. : ,

,

0

p

kk

i i

j j j

j

Min s b x w Min y C x

SA A x b i Rb td C x

y j Gw

xy

ε=

= −

≤ ∈+ −

≥ ∈

≥∈

∑

R

novamente, pode-se reescrever a mesma formulação como:

1

. : ,,

0

p

kk

i i

j j j j

Min y C x

SA A x b i RC x w y b td j G

xy

ε=

−

≤ ∈

+ ≥ + ∈

≥∈

∑

R

38

Como a variável y é livre, para efeitos computacionais, a mesma é reescrita

como y y y+ −= − , com , 0y y+ − ≥ . Temos, assim, a formulação final do Pareto

Race:

1

. : ,,

, , 0

p

kk

j j j j j

i i

Min y y C x

SA C x w y w y b td j GA x b i R

x y y

ε+ −

=

+ −

+ −

− −

+ − ≥ + ∈

≤ ∈

≥

∑(5.2)

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)

39

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:

1 1

2 2

3 3

1 2 3

1 2 3

1 2

1 2 3

. : 53 9

3 4 16, , 0

Max z xMax z xMax z xSA x x x

x x xx x

x x x

==

=+ + ≤

+ + ≤+ ≤≥

Cuja região viável S está diagramada na figura 5.3 abaixo:

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,

1x3x

2x

40

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:

( )6,000 5,000 5,000 5,000 9,000 16,000Tb =

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:

,:

0,k

k

b se k Gw

se k R∆ ∈

= ∈

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,5006,000 2,500 3,5006,000 2,000 4,000

0,000 0,0000,000 0,0000,000 0,000

d w

− − −

= = =

Posteriormente, o vetor d será normalizado pela constante ks d iniciais=∑ .

No nosso exemplo 2,500 3,500 4,000 0,000 0,000 0,000 10,000s = + + + + + = .

Temos, assim, o seguinte problema:

1 2 3

1

2

3

1 2 3

1 2 3

1 2

1 2 3

0,001( )

. : 2,500 2,500 6,000 2,5003,500 3,500 5,000 3,5004,000 4,000 5,000 4,000

5,0003,000 9,000

3,000 4,000 16,000, , , , 0

Min y y x x x

SA x y y tx y y t

x y y tx x xx x xx x

x x x y y

+ −

+ −

+ −

+ −

+ −

− − + +

+ − ≥ +

+ − ≥ +

+ − ≥ +

+ + ≤+ + ≤

+ ≤

≥

41

Introduzindo as variáveis de folga 1 2 6, ,...,S S S , e fazendo inicialmente

0,000t = , temos como solução ótima do PL acima a base 1 2 3 5 6, , , , ,X X X Y S S+ ,

com tableau Simplex ótimo:

1X 2X 3X Y + Y −1S 2S 3S 4S 5S 6S b

1X 1,000 0,000 0,000 0,000 0,000 -0,750 0,250 0,250 0,250 0,000 0,000 3,250

2X 0,000 1,000 0,000 0,000 0,000 0,350 -0,650 0,350 0,350 0,000 0,000 1,150

3X 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

5S 0,000 0,000 0,000 0,000 0,000 -0,700 1,300 -0,700 -1,700 1,000 0,000 1,700

6S 0,000 0,000 0,000 0,000 0,000 0,850 1,850 -2,150 -2,150 0,000 1,000 1,650

jc 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:

1( )Bx B b td−= +

na qual Bx é o vetor das variáveis básicas e 1B− a matriz inversa da base. Se

variarmos de t para t θ+ , teremos:

1( )B Bx x B dθ θ −= +

que, para garantir a viabilidade do primal, deverá ser maior ou igual a zero:

( ) 0Bx θ ≥

42

obtemos com isto o intervalo [ ]1 2;t t t t− + , onde 1t t− e 2t t+ são,

respectivamente, o menor e o maior valor que obedecem à restrição ( ) 0Bx θ ≥ .

No nosso exemplo:

1

2

3 1

5

6

( )B

XXX

x B b tdYSS

−+

= = +

0,750 -0,250 -0,250 0,250 0,000 0,000-0,350 0,650 -0,350 0,350 0,000 0,000-0,400 -0,400 0,600 0,400 0,000 0,0000,100 0,100 0,100 -0,100 0,000 0,0000,700 -1,300 0,700 -1,700 1,000 0,000-0,850 -1,850 2,150 -2,150 0,000 1,000

Bx

=

6,000 2,5005,000 3,5005,000 4,000

. .5,000 0,0009,000 0,000

16,000 0,000

t

+

3,250 0,000.1,150 0,000.0,600 0,000.1,100 0,000.1,700 0,000.1,650 1,000.

B

ttt

xttt

+ + +

= +

+ +

. Como ( ) 0Bx θ ≥ :

3,250 0,000. 0,0001,150 0,000. 0,0000,600 0,000. 0,0001,100 0,000. 0,0001,700 0,000. 0,0001,650 1,000. 0,000

B

ttt

xttt

+ + +

= ≥ +

+ +

Como 0,000t = , [ ]1 2;t t t t t∈ − + , e o espaço de variação de t que satisfaz a

restrição ( ) 0Bx θ ≥ é [ ]1,100;t∈ − +∞ , temos que 1 21,100t e t= = +∞ .

V.5.1 Mudança de direção obrigatória

Como 2t = +∞ , 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 3d é alterado, utilizando a

fórmula:

43

( )

:

constante igual a 0,5 (valor recomendadopelos autores do método)limite superior do intervalo de variaçãolimite inferior do intervalo de varia

i i i i

i

i

d d LS LI

onde d vetor novod vetor original

LSLI

σ

σ

= + −

===

=

= ção

No nosso exemplo:

3 4,000 0,500(6,000 0,600) 6,700d = + − =

O vetor d será normalizado de modo que id s=∑ , pela seguinte fórmula:

1

. , 1, 2,...,i i m p

jj

sd d i m pd

onde d vetor novod vetor original

+

=

= = +

==

∑

no nosso exemplo 10,000s = , logo:

10,000. , 1,2,... , 62,500 3,500 6,700i id d i= =

+ +

obteremos, então, como novo vetor d :

( )1,969 2,756 5,276 0,000 0,000 0,000Td =

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,

0,000 0,000y e y+ −≥ = , os valores de w são inversamente proporcionais à

importância das FO, isto é, quanto menor o valor de iw , maior importância terá a

ésimai FO. No nosso exemplo: desejamos melhorar a FO3, logo teremos que

diminuir o valor de 3w . Os autores do método recomendam dividir iw por (1 )σ+ ,

ou seja, por 1,500 , logo:

34,000 2,6671,500

w = =

44

Procedendo novamente à normalização (idêntica à realizada para o vetor d ),

temos como novo vetor w :

( )2,885 4,038 3,077 0,000 0,000 0,000Tw =

O ponto de referência é atualizado com o valor das funções objetivo da última

solução, gerando o novo vetor b :

( )3, 250 1,150 0,600 5,000 9,000 16,000b =

O que gera, novamente, o seguinte problema de PL:

1 2 3

1

2

3

1 2 3

1 2 3

1 2

1 2 3

0,001( )

. : 2,885 2,885 3,250 1,9694,038 4,038 1,150 2,7563,077 3,077 0,600 5, 276

5,0003,000 9,000

3,000 4,000 16,000, , , , 0

Min y y x x x

SA x y y t

x y y tx y y t

x x xx x xx x

x x x y y

+ −

+ −

+ −

+ −

+ −

− − + +

+ − ≥ +

+ − ≥ +

+ − ≥ +

+ + ≤+ + ≤

+ ≤

≥

Cujo tableau Simplex ótimo, para 0,000t = , é:

1X 2X 3X Y + Y −1S 2S 3S 4S 5S 6S b

1X 1,000 0,000 0,000 0,000 0,000 -0,712 0,289 0,289 0,289 0,000 0,000 3,250

2X 0,000 1,000 0,000 0,000 0,000 0,404 -0,596 0,404 0,404 0,000 0,000 1,150

3X 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

5S 0,000 0,000 0,000 0,000 0,000 -0,808 1,192 -0,808 -1,808 1,000 0,000 1,700

6S 0,000 0,000 0,000 0,000 0,000 0,519 1,519 -2,481 -2,481 0,000 1,000 1,650

jc 0,000 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,110 0,000 0,000 0,050

45

Calculando o intervalo de variação de t para o qual a base ótima se mantém,

temos:

1

2

3 1

5

6

( )B

XXX

x B b tdYSS

−+

= = +

0,712 -0,289 -0,289 0,289 0,000 0,000-0,404 0,596 -0,404 0,404 0,000 0,000-0,308 -0,308 0,692 0,308 0,000 0,0000,100 0,100 0,100 -0,100 0,000 0,0000,808 -1,192 0,808 -1,808 1,000 0,000-0,519 -1,519 2,481 -2,481 0,000 1,000

Bx

=

3, 250 1,9691,150 2,7560,600 5,276

. .5,000 0,0009,000 0,000

16,000 0,000

t

+

3, 250 0,916 0,0001,150 1, 282 0,0000,600 2,199 0,0000,000 1,000 0,0001,700 2,564 0,0001,650 7,878 0,000

B

ttt

xttt

− − +

= ≥ +

+ +


restrição ( ) 0Bx θ ≥ é [0,000; 0,897]t∈ , temos que 1 20,000 0,897t e t= = .

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 constante410β −= . No nosso exemplo, o DM desejou uma velocidade 0,020t∆ = . Para

0,020t = , a solução é calculada como se segue:

1

2

3

5

6

3, 250 0,916.0,020 3,2321,150 1,282.0,020 1,1240,600 2,199.0,020 0,6440,000 1,000.0,020 0,0201,700 2,564.0,020 1,7511,650 7,878.0,020 1,808

B

XXX

xYSS

+

− − +

= = = +

+ +

46

Prosseguindo nesta direção, com incrementos 0,020t∆ = temos:

t=0,020 t=0,040 t=0,060 t=0,080 … t=0,897

1X 3,232 3,213 3,195 3,177 2,428

2X 1,124 1,099 1,073 1,047 0,000

3X 0,644 0,688 0,732 0,776 2,572

Y + 0,020 0,040 0,060 0,080 0,897

5S 1,751 1,803 1,854 1,905 4,000

6S 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ô 2X (variável básica com valor igual a

zero), temos o seguinte teste da razão:

Teste da razão Y −1S 2S 3S 4S

min | 0,000jij

ij

c aa

<

0,000ija = 0,000ija > 0,168 0,000ija > 0,000ija >

Logo, a variável que entra no lugar da 2X é a 2S , ficando como base

ótima: 1 2 3 5 6, , , , ,X S X Y S S+ .

47

Quando calculamos o intervalo de variação de t para o qual a base ótima se

mantém, temos:

1

2

3 1

5

6

( )B

XSX

x B b tdYSS

−+

= = +

0,516 0,000 -0,484 0,484 0,000 0,0000,677 -1,000 0,677 -0,677 0,000 0,000-0,516 0,000 0,484 0,516 0,000 0,0000,168 0,000 0,168 -0,168 0,000 0,0000,000 0,000 0,000 -1,000 1,000 0,000-1,548 0,000 1,452 -1,452 0,000 1,000

Bx

=

3, 250 1,9691,150 2, 7560,600 5, 276

. .5, 000 0,0009,000 0,000

16,000 0,000

t

+

3,806 1,537 0,000-1,929 2,150 0,0001,194+1,537 0,000-0,193+1,215 0,0004,000+0,000 0,0004,581 4,611 0,000

B

ttt

xttt

− +

= ≥ +


restrição ( ) 0Bx θ ≥ é [ ]0,897; 2, 477t∈ , temos que 1 20,000 1,580t e t= = .

Para o valor mínimo de 0,897t = , temos a seguinte solução:

( ) ( )1 2 3 2, 428 0,000 2,572X X X =

Observemos que os valores de 1X e 2X 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].

48

Suponhamos que o DM deseje aumentar a velocidade, por exemplo, para

0,030t∆ = . 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

1X 2,428 2,382 2,336 2,197

2S 0,000 0,065 0,129 0,323

3X 2,572 2,618 2,664 2,803

Y + 0,897 0,933 0,970 1,079

5S 4,000 4,000 4,000 4,000

6S 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 3Z ) até o valor de 2, 477t = , no ponto 1,047t = , 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 2Z , é necessário um incremento na componente

correspondente à 2Z no vetor direção d e uma diminuição da mesma componente

no vetor de pesos w :

2 2 ( ) 2,756 0,500(6,000 0,000) 5,756i id d LS LIσ= + − = + − =

22

4,038 2,6921,500 1,500ww = = =

49

Após a normalização, temos:

1,514 3,3334,428 3,1114,058 3,555

,0,000 0,0000,000 0,0000,000 0,000

d w

= =

O ponto de referência é atualizado com os valores da última solução:

( )2,197 0,000 2,803 5,000 9,000 16,000Tb =

Resolve-se o seguinte problema considerando 0,000t = :

1 2 3

1

2

3

1 2 3

1 2 3

1 2

1 2 3

0,001( )

. : 3,333 3,333 2,197 1,5143,111 3,111 0,000 4, 4283,555 3,555 2,803 4,058

5,0003,000 9,000

3,000 4,000 16,000, , , , 0

Min y y x x x

SA x y y t

x y y tx y y t

x x xx x xx x

x x x y y

+ −

+ −

+ −

+ −

+ −

− − + +

+ − ≥ +

+ − ≥ +

+ − ≥ +

+ + ≤+ + ≤

+ ≤

≥

Cujo Tableau Simplex Ótimo é o seguinte:

1X 2X 3X Y + Y −1S 2S 3S 4S 5S 6S b

1X 1,00 0,000 0,000 0,000 0,000 -0,667 0,333 0,333 0,333 0,000 0,000 2,197

2X 0,00 1,000 0,000 0,000 0,000 0,311 -0,689 0,311 0,311 0,000 0,000 0,000

3X 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

5S 0,00 0,000 0,000 0,000 0,000 -0,622 1,378 -0,622 -1,622 1,000 0,000 4,000

6S 0,00 0,000 0,000 0,000 0,000 0,755 1,755 -2,245 -2,245 0,000 1,000 9,409

jc 0,00 0,000 0,000 0,000 0,000 0,100 0,100 0,100 0,101 0,000 0,000 0,005

50

Fazendo a análise de sensibilidade, temos que:

1

2

3 1

5

6

( )B

XXX

x B b tdYSS

−+

= = +

0,667 -0,333 -0,333 0,333 0,000 0,000-0,311 0,689 -0,311 0,311 0,000 0,000-0,356 -0,356 0,644 0,356 0,000 0,0000,100 0,100 0,100 -0,100 0,000 0,0000,622 -1,378 0,622 -1,622 1,000 0,000-0,755 -1,755 2,245 -2,245 0,000 1,000

Bx

=

2,197 1,5140,000 4,4282,803 4,058

. .5, 000 0,0009,000 0,000

16,000 0,000

t

+

2,197 1,819 0,0000,000 1,317 0,0002,803+0,503 0,0000,000+1,000 0,0004,000 2,633 0,0009,409 0,191 0,000

B

ttt

xttt

− +

= ≥ − +


restrição ( ) 0Bx θ ≥ é [ ]0,000; 1, 208t∈ , temos que 1 0,000t = e 2 1,208t = .

Mantendo a mesma velocidade 0,030t∆ = , as seguintes soluções são

apresentadas ao DM:

t=0,000 t=0,030 t=0,060 … t=0,420

1X 2,197 2,142 2,088 1,433

2X 0,000 0,040 0,079 0,553

3X 2,803 2,818 2,833 3,014

Y + 0,000 0,030 0,060 0,420

5S 4,000 3,921 3,842 2,894

6S 9,409 9,415 9,420 9,489

51

V.5.4 Fixando o valor de uma FO

Suponhamos que, neste ponto ( 0,420t = ), o DM deseje continuar nesta

direção (aumentando 2Z ) mas não deseje que o valor de 1Z diminua, ou seja, o

DM quer fixar 1 1,433Z = .

Para tanto, devemos fazer a componente correspondente àquela FO nos

vetores w e d igual a zero:

0,000; 0,000onde é o índice da FO fixadai iw di

= =

No nosso exemplo, faremos:

0,000 0,0004, 428 3,1114,058 3,5550,000 0,0000,000 0,0000,000 0,000

d w

= =

que, após a normalização, ficará:

0,000 0,0005, 218 4,6674,782 5,3330,000 0,0000,000 0,0000,000 0,000

d w

= =

Atualizando novamente o intervalo de variação da FO1, obteremos:

[1,433; 7,000]

52

Teremos, assim, o seguinte PPL:

1 2 3

1

2

3

1 2 3

1 2 3

1 2

1 2 3

0,001( )

. : 0,000 0,000 1, 433 0,0004,667 4,667 0,553 5, 2185,333 5,333 3,014 4,782

5,0003,000 9,000

3,000 4,000 16,000, , , , 0

Min y y x x x

SA x y y t

x y y tx y y t

x x xx x xx x

x x x y y

+ −

+ −

+ −

+ −

+ −

− − + +

+ − ≥ +

+ − ≥ +

+ − ≥ +

+ + ≤+ + ≤

+ ≤

≥

Cujo Tableau Simplex Ótimo é o seguinte:

1X 2X 3X Y + Y −1S 2S 3S 4S 5S 6S b

1X 1,000 0,000 0,000 0,000 0,000 -1,000 0,000 0,000 0,000 0,000 0,000 1,433

2X 0,000 1,000 0,000 0,000 0,000 0,467 -0,533 0,467 0,467 0,000 0,000 0,553

3X 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

5S 0,000 0,000 0,000 0,000 0,000 -0,933 1,067 -0,933 -1,933 1,000 0,000 2,894

6S 0,000 0,000 0,000 0,000 0,000 1,133 2,133 -1,867 -1,867 0,000 1,000 9,489

jc 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:

1

2

3 1

5

6

( )B

XXX

x B b tdYSS

−+

= = +

53

1,000 0,000 0,000 0,000 0,000 0,000-0,467 0,533 -0,467 0,467 0,000 0,000-0,533 -0,533 0,467 0,533 0,000 0,0000,100 0,100 0,100 -0,100 0,000 0,0000,933 -1,067 0,933 -1,933 1,000 0,000-1,133 -2,133 1,867 -1,867 0,000 1,000

Bx

=

1, 433 0,0000,553 5, 2183,014 4, 782

. .5,000 0,0009,000 0,000

16,000 0,000

t

+

1,433 0,000 0,0000,553 0,551 0,0003,014 0,551 0,0000,000+1,000 0,0002,894 1,102 0,0009,489 2,204 0,000

B

ttt

xttt

+ + −

= ≥ − −


restrição ( ) 0Bx θ ≥ é [ ]0,000; 2,626t∈ , temos que 1 0,000t = e 2 2,626t = .

Mantendo a mesma velocidade 0,030t∆ = , as seguintes soluções são

apresentadas ao DM:

t=0,000 t=0,030 t=0,060 … t=0,960

1X 1,433 1,433 1,433 1,433

2X 0,553 0,570 0,586 1,082

3X 3,014 2,998 2,981 2,485

Y + 0,000 0,030 0,060 0,960

5S 1,000 2,861 2,828 1,836

6S 1,000 9,423 9,357 7,373

Supondo que o DM ache ( ) ( )1 2 3 1, 433 1,082 2, 485Z Z Z = 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:

54

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:

2

1

min{ ; }, 0max{ ; }, 0

t t t se tt

t t t se t+ ∆ ∆ >

= + ∆ − ∆ <

Se 2t = ∞ ou então 1 0,000t = e 0,000t∆ < , é alcançado o limite do politopo

naquela direção; logo, o DM deverá ser questionado sobre nova direção. Se

2 0,000t = e 0,000t∆ > , 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 [ ]1 2;t t t t− + .

Para liberar novamente uma FO fixada anteriormente, deve-se fazer:

: ; :onde é o índice da FO fixadai i i iw b d bi

= ∆ = ∆

3Z

(3,250; 1,150; 0,600)

(2,428; 0,000; 2,572)(2,197; 0,000; 2.803)

(1,433; 0,553; 3,014)

(1,433; 1,082; 2,485)

1Z

2Z

55

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

56

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.

57

VI.2. O Algoritmo

Para um problema MOLP do tipo:

1 1

2 2

max { }max { }

...max { }

.: , 1, 2, ...,0

p p

i i

C x zC x z

C x zSA A x b i m

x

==

=

≤ =≥

onde , , , epxn n p mxn mC x z A b∈ ∈ ∈ ∈ ∈R R R R R .

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:

1

. : ,

,, , , , 0

p

kk

j j j F j

i I i

F I

Min y y C x

SA C x w y w y S b j G

A x S b i Rx y y S S

ε+ −

=

+ −

+ −

− −

+ − − = ∈

+ = ∈

≥

∑

(6.1)

onde: ε é um escalar muito pequeno maior que zero; C é a matriz dos

coeficientes das metas flexíveis; w é o vetor de pesos; FS são as variáveis

de folga das metas flexíveis; A é a matriz dos coeficientes das metas

inflexíveis; e IS são as variáveis de folga das metas inflexíveis.

58

2.1. Fazer o vetor φ igual aos valores que as FO’s assumem com o vetor x :

,j jC 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:

,:0,000,k

se k Gwse 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 ( ib )

das metas inflexíveis.

2.5. Calcular o vetor κ de modo que:

{ | }i i ib A x i Rκ = − ∈

2.6. Fazer o ponto inicial:

( ) ( )0 1,000 1,000TT TT T T T T

I Fx x S y y S x eκ+ −= =

onde e é um vetor unitário de dimensão adequada.

2.7. Fazer a matriz0

0 0 0

C w w IA

A I

− −= , onde 0 é um vetor nulo composto por

n componentes; 0 é uma matriz nula de dimensão adequada

( x ou xp n n p ); e I é uma matriz identidade de dimensão adequada

( x ou xp p n n ).

2.8. Fazer c o vetor gradiente da função objetivo do PPL (6.1):

1( )

p

kk

c y y C xε+ −

=

= ∇ − − ∑

2.9. Fazer 1v = 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= .

59

2.10. Fazer o vetor inicial de soluções intermediárias 1sol φ= .

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:

1,000, 1,2,...,j j 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:

1

. , 1, 2,...,

vetor crescimento normalizadovetor crescimento original

i i p

jj

p i p

onde

µ µµ

µµ

=

= =

==

∑

3.1.2.2. Atualizar o vetor b de acordo com o seguinte:

1vjj jb C x tµ−= + ∆

3.1.2.3. Fazer 1,000y− = (componente de 1vx − );

3.1.2.4. Fazer y+ (componente de 1vx − ) o menor inteiro positivo que

atenda às restrições:

1 ( 1) 0,vjjC x y w b j G− ++ − − > ∀ ∈

2,000y+ ≥

3.1.2.5. Atualizar o vetor FS (componente de 1vx − ) de modo que:

1 ( 1) 0,000,j

vj j Fb C x y w S j G− +− − − + = ∀ ∈

3.1.2.6. Fazer mud N= ;

60

3.1.3. Fazer D uma matriz diagonal, onde1,

0,000,

vi

ijx se i j

dse i j

− ==

≠ .

3.1.4. Fazer: 2[ ]Tv vh D c A ω= − − , onde 2 1 2[( ) ]

Tv AD A AD cω −= .

3.1.5. Fazer: 1v v vx x hρ λ−= + ,

onde ( 1)( )

( )

0 1

min , 0, 1v

viiv

i

x h i nh

ρ

λ−

< <

= − ∀ < ≤ ≤

Utilizar inicialmente um 0,100ρ = .

3.1.6. Fazer: || ||v vgap h= .

3.1.7. Se ( ) ( )v vy y− +≥ fazer:

1π π= + ;

1v vx x −= ;

vsol Cxπ = ;

mud S= .

3.1.8. Se 41,000vgap e−> e 1,j jsol sol j Gπ π −≥ ∀ ∈ , fazer 1v v= + e retornar

ao início do loop.

3.1.9. Se 41,000vgap e−≤ ou então 1,j jsol sol j Gπ π −< ∀ ∈ , parar o loop, fazer

1π π= + e vsol Cxπ = .

61

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:

,2,000

,2,000

j j

j j

LS b j G

LI b j G

φ

φ

= + ∀ ∈

= − ∀ ∈

4.3. Fazer:

,jb j Gφ∆ = ∀ ∈ .

4.4. Fazer os vetores de direção d e de pesos w iguais a:

,: :0,000,

kk k

b se k Gw dse k R

∆ ∈= = ∈

.

5. Formular o seguinte PPL de acordo com os dados referentes ao problema:

1

. : ,

,

, , 0

p

kk

jj j j j

ii

Min y y C x

SA C x w y w y b td j G

A x b i R

x y y

ε+ −

=

+ −

+ −

− −

+ − ≥ + ∈

≤ ∈

≥

∑

(6.2)

6. Resolver o PPL (6.2) pelo método Pareto Race:

6.1. Fazer ks w iniciais=∑

6.2. Resolver o PPL (6.2) pelo método SIMPLEX para 0,000t = e apresentar as

soluções ao DM. Caso o mesmo esteja satisfeito com as soluções finalizar o

algoritmo.

62

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 ,j j jb LS LI 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:

0,000; 0,000onde é o índice da FO fixadai iw di

= =

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:

0,500

: vetor novovetor original

intervalo de variaçãodos níveis de aspirações

i i i

i

d d b

onde ddb

= + ∆

==

∆ =

6.3.2.2.2. Alterar o vetor w utilizando a seguinte fórmula:

1,500i

iww =

6.3.3. Normalizar os vetores d e w pela seguinte fórmula:

1

. , 1, 2,...,

vetor ou normalizadovetor ou original

i i m p

jj

sv v i m pv

onde v d wv d w

+

=

= = +

==

∑

63

6.3.4. Atualizar o vetor b com os valores das funções objetivo da última

solução e os vetores e w d com os valores normalizados calculados

acima;

6.3.5. Resolver o PPL (6.2) pelo método SIMPLEX para 0,000t = ;

6.3.6. Calcular o intervalo de variação de t para o qual a base se mantém

ótima pela seguinte fórmula:

1( ) 0,000B b td− + ≥

e achar o intervalo de variação [ ]1 2;t t t t− + .

6.3.7. Se 2t = ∞ ou então 1 0,000t = e 0,000t∆ < , é alcançado o limite do

politopo naquela direção; logo, o DM deverá ser questionado sobre

nova direção. Se 2 0,000t = e 0,000t∆ > , 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 [ ]1 2;t t t t− + .

6.3.8. Loop dois:

6.3.8.1. Fazer 2

1

min{ ; }, 0,000max{ ; }, 0,000

t t t se tt

t t t se t+ ∆ ∆ >

= + ∆ − ∆ <

6.3.8.2. Apresentar a solução 1( )Bx B 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 [ ]1 2;t t t t− + :

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.

64

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: e/ou tal quei i i iA x b A x b i R∃ ≥ ∃ = ∈ .

Caso o PPL esteja na forma padrão, a solução inicial x fica trivial:

*ix ε=

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:

* *

* *

*

, {restrições }2 , {restrições }

- , {restrições }

i i i

i j j

i j j

b A ib A j

b A j

β ε ε

β ε ε

β ε

= − − ∈ ≤

= − + ∈ ≥

= ∈ =(6.3)

formulamos o seguinte PPL auxiliar:

*

1

*

* *

*

* * *

*

. : , {restrições }

, {restrições }

, {restrições }

, {1,2,..., }

, 0onde é um número muito grand

i

j

k m

n

ii

i I i i

j I i j

j i j

k I

I

Min My x

SA A x S y b i

A x S y b j

A x y b j

x S y k n

y SM

β

β ε

β

ε ε+

=

+

+ + = ∈ ≤

− + = + ∈ ≥

+ = ∈ =

− + = =

≥

∑

e

(6.4)

65

Tal PPL auxiliar pode ser resolvido tanto pelo SIMPLEX quanto pelo método

dos pontos interiores. Utilizando como ponto inicial 0 *( ) ( 1)T T TT T

Ix x S y ε ε= = , que é

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 .

66

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.

67

Após o estabelecimento do vetor de crescimento, um novo vetor de aspirações

( jb ) é 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 , 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.

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

68

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 41,000e− , 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. Ressalta-

se que, a partir deste ponto, para cada aumento em uma FO, outra deverá

obrigatoriamente ter seu valor decrescido.

69

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

70

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:

1

2

3

4

5

6

7

8

9

( ) 0,569 6,423( ) 0,814 22,093( ) 0,324 9,259( ) 0,343 8,039( ) 0,343 8,039( ) 0,297 11,017( ) 0,479 0,685( ) 0,479 0,685( ) 0,479 0,685

f x xf x xf x xf x xf x xf x xf x xf x xf x x

= −= −= +

= += +

= += −

= −= −

onde x é a quantidade de horas voadas.

As funções capacitação acima descritas estão plotadas nas figuras abaixo:

Figura 7.1 – Aviação de Caça

1( )f x

2 ( )f x

( )f x

x

71

Figura 7.2 – Aviação de Ataque

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,

3( )f x

4 5( ) e ( )f x f x

( )f x

x

6( )f x7 8 9( ), ( )e ( )f x f x f x

( )f x

x

72

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:

• 1( ) 25,570g x x= • 6( ) 1,000g x x=

• 2 ( ) 49,780g x x= • 7 ( ) 3,035g x x=

• 3( ) 6,153g x x= • 8( ) 5,165g x x=

• 4 ( ) 28,682g x x= • 9 ( ) 8,859g x x=

• 5( ) 47,668g x 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.

73

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

11

1 1 2 22

3 3 4 4 5 53

6 6 7 7 8 8 9 94

9

1

1 1 2 2

3 3 4 4

3 3 5 5

4 4 5 5

( )

9( ) ( )

2( ) ( ) ( )

3( ) ( ) ( ) ( )

4

.: ( ) 32000

| ( ) ( ) | 10%| ( ) ( ) | 10%| ( ) ( ) | 10%| ( ) ( ) | 10%

(

k kk

k kk

k

f xMax z

f x f xMax z

f x f x f xMax z

f x f x f x f xMax z

SA g x

f x f xf x f xf x f xf x f xf x

=

=

=

+=

+ +=

+ + +=

≤

− ≤− ≤

− ≤− ≤

∑

∑

) 30%, {1,2,...,9}( ) 100%, {1,2,...,9}k

k k

kf x k

≥ ∀ ∈≤ ∀ ∈

onde: kx = quantidade de horas voadas por piloto na aeronave k .

74

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:

*

1

*

* *

*

* * *

*

. : , {restrições }

, {restrições }

, {restrições }

, {1,2,..., }

, 0onde é um número muito grand

i

j

k m

n

ii

i I i i

j I i j

j i j

k I

I

Min My x

SA A x S y b i

A x S y b j

A x y b j

x S y k n

y SM

β

β ε

β

ε ε+

=

+

+ + = ∈ ≤

− + = + ∈ ≥

+ = ∈ =

− + = =

≥

∑

e

(7.1)

Ao fazer *ε igual a um e calcular o vetor β através da seguinte fórmula:

* *

* *

*

, {restrições }2 , {restrições }

- , {restrições }

i i i

i j j

i j j

b A ib A j

b A j

β ε ε

β ε ε

β ε

= − − ∈ ≤

= − + ∈ ≥

= ∈ =

(7.2)

obteremos:

(31823,089 7,799 10,201 7,799 10,201 9,000 9,0006,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,000298,000 208,000 208,000 208,000 185,000 148,000)

Tβ =

Fazendo o ponto inicial do PPL auxiliar igual à:

0 * * *( ) ( 1)T T T

Ix x S y ε ε= =

e resolvendo o seguinte PPL auxiliar:

75

1

2

3

4

5

6

9*

19

*

1

*1 1 2 2

*2 2 1 1

*3 3 4 4

*4 4 3 3

*3 3 5 5

1000

.: ( ) 31823,089 32000

( ) ( ) 7,799 10%

( ) ( ) 10,201 10%

( ) ( ) 7,799 10%

( ) ( ) 10,201 10%

( ) ( ) 9,000 10

kk

k k Ik

I

I

I

I

I

Min y x

SA g x S y

f x f x S y

f x f x S y

f x f x S y

f x f x S y

f x f x S y

=

=

+

+ + =

− + + =

− + + =

− + + =

− + + =

− + + =

∑

∑

7

8

9

9

18

27

*5 5 3 3

*4 4 5 5

*5 5 4 4

*

*

*

9

18

%

( ) ( ) 9,000 10%

( ) ( ) 6,425 10%

( ) ( ) 24,425 10%

( ) 30% 1%, {1,2, ... ,9}

( ) 100%, {1,2, ... ,9}

1, {1,2, ... ,9}

I

I

I

k k I

k k I

k I

k

k

k

k

k

f x f x S y

f x f x S y

f x f x S y

f x S y k

f x S y k

x S y k

β

β+

+

+

+

+

− + + =

− + + =

− + + =

− + = + =

+ + = =

− + = =

obteremos o seguinte ponto inicial para a fase um:

T-27 67,086AT-26 66,914

A-1 66,914C-98 67,371R-95 66,086R-35 66,086R-99 66,086F-5E 65,757F-103 65, 229

x

= =

Solicitar ao DM a velocidade que lhe convém. Simularemos que o mesmo

desejou 10t∆ = .

Formular o seguinte PPL:

1

. : ,

,, , , , 0

p

kk

j j j F j

i I i

F I

Min y y C x

SA C x w y w y S b j G

A x S b i Rx y y S S

ε+ −

=

+ −

+ −

− −

+ − − = ∈

+ = ∈

≥

∑

(7.3)

76

Fazer o vetor

FAe III 31,000Ataque 31,000

Reconhecimento 31,000Caça 31,000

Cxφ

= = =

.

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,:0,000,k

se k Gwse k R

φ = ∈= ∈

.

Calcular o vetor κ de modo que:

{ | }i i ib A x i Rκ = − ∈

(20355,150 10,000 10,000 10,000 10,000 10,000 10,00010,000 10,000 3,086 2,914 2,914 3,371 2,0862,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)

Tκ =

Fazer o ponto inicial:

( ) ( )0 1,000 1,000TT TT T T T T

I Fx x S y y S x eκ+ −= =

Fazer 1v = 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:

1



sol φ

= = =

.

Fazer: 1



µ

= =

.

77

Apresentar o vetor de crescimento µ , os valores das FO’s (vetor 1sol ) 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:

1

31,000 1,000 41,00031,000 1,000 41,000

*10,00031,000 1,000 41,00031,000 1,000 41,000

vjj jb C x tµ−

= + ∆ = + =

Fazer y+ (componente de 1vx − ) o menor inteiro positivo que atenda às

restrições:

1 ( 1) 0,vjjC x y w b j G− ++ − − > ∀ ∈

2,000y+ ≥

No nosso exemplo: 2,000y+ = .

Atualizar o vetor FS (componente de 1vx − ) de modo que:

1 ( 1) 0,000,v Fj j jb C x y w S j G− +− − − + = ∀ ∈

No nosso exemplo:

30,00030,00030,00030,000

FS

=

.

Fazer mud N= .

A formulação (7.3), com os valores numéricos do nosso exemplo, fica, na forma

matricial:

78

Ataque Reconhecimento Caça Variáveis de Folga das Metas Inflexíveis Pesos V. Folga M. Flex. RHS

T-27 AT-26 A-1 C-98 R-95 R-35 R-99 F-5E F-1031IS

2IS

3IS

4IS

5IS

6IS

7IS

8IS

9IS

10IS

11IS

12IS

13IS

14IS

15IS

16IS

17IS

18IS

19IS

20IS

21IS

22IS

23IS

24IS

25IS

26IS

27IS y+ y− 1F

S2F

S3F

S4F

S b

FAE III 0,04 0,04 0,04 0,03 0,05 0,05 0,05 0,06 0,09 0,000,000,000,000,000,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 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,000,000,000,000,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 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,000,000,000,000,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 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,000,000,000,000,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 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,000,000,000,000,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 32000,00

10% ataque 0,32 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,001,000,000,000,000,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 8,78

10% ataque -0,32 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,001,000,000,000,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 11,22

10% ataque 0,32 0,00 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,001,000,000,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 8,78

10% ataque -0,32 0,00 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,001,000,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 11,22

10% ataque 0,00 0,34 -0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,001,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 10,00

10% ataque 0,00 -0,34 0,34 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 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,000,000,000,000,000,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,000,000,000,000,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 25,67

min 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,000,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,000,000,000,000,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 64,00

min 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,000,000,000,000,000,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 64,00

min 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,000,000,000,000,000,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 64,00

max 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 280,00

max 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 268,00

max 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 268,00

max 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 300,00

max 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,00 0,000,000,000,000,000,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 210,00

max 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,00 0,000,000,000,000,000,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 210,00

max 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,00 0,000,000,000,000,000,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 210,00

max 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,00 0,000,000,000,000,000,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 187,00

max 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,00 0,000,000,000,000,000,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 150,00

FO -1e-4

-1e-4

-1e-4

-1e-4

-1e-4

-1e-4

-1e-4

-1e-4

-1e-4 0,000,000,000,000,000,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 -1,00 0,00 0,00 0,00 0,00

79

O ponto inicial 0x ficará:

T0x =(67,086 66,914 66,914 67,371 66,086 66,086 66,08665,757 65,229 20355,150 10,000 10,000 10,000 10,00010,000 10,000 10,000 10,000 3,086 2,914 2,9143,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,24384,771 2,000 1,000 30,000 30,000 30,000 30,000)

Observemos que o vetor jb 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 ( ) ( )v vy y− +≥ , obteremos o seguinte ponto no espaço

objetivo:

2



sol

= =

Apresentando o vetor de crescimento µ , os valores das FO’s (vetor 2sol ) 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:

2



µ

= =

Que depois de normalizado ficará:

( )0,571 1,143 0,571 1,714T

µ =

80

Atualizando o vetor jb teremos:

1

38,790 0,571 44,50538,779 1,143 50, 207

*1038,646 0,571 44,36139,096 1,714 56, 238

vjj jb C x tµ−

= + ∆ = + =

Fazendo 1y− = e calculando o valor de y+ , obteremos 2y+ = .

Atualizando FS teremos que: ( )34, 286 28,571 34, 286 22,857TFS = .

Resolvendo, com o valor de 0,100ρ = , as diversas iterações pelo método dos

pontos interiores, até que ( ) ( )v vy y− +≥ , obteremos o seguinte ponto no espaço

objetivo:

3



sol

= =

Prosseguindo desta maneira, listaremos a seguir apenas os vetores de

crescimento fornecidos pelo DM, o vetor jb gerado, assim como a solução

intermediária:

3 4

1,000 57,947 69,1852,000 64,176 70,0291,500 55,820 61, 4363,000 76,859 83, 414

jb solµ

= = =

4 5

1,000 78,708 82,6031, 200 81, 457 82,1781,100 71,912 77, 4900,900 91,986 93, 465

jb solµ

= = =

5 6

1,000 89, 269 82,5842,000 95,511 85,1091,000 84,157 73,7832,000 106,798 96, 400

jb solµ

= = =

81

O mecanismo de parada da 6sol foi o 41,000gap e−< , e não ( ) ( )v vy y− +≥ ;

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

82

Fase 2: Pareto Race

Inicialmente, atualizamos as componentes do vetor jb com os valores

assumidos pela última solução intermediária da fase um:


Reconhecimento 73,783Caça 96, 400

jb

= =

Fazendo os limites de variação superior e inferior igual à:

,2,000

,2,000

j j

j j

LS b j G

LI b 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:

,: :0,000,

kk k

b se k Gw dse k R

∆ ∈= = ∈

83

Formular o seguinte PPL:

1

. : ,

,

, , 0

p

kk

jj j j j

ii

Min y y C x

SA C x w y w y b td j G

A x b i R

x y y

ε+ −

=

+ −

+ −

− −

+ − ≥ + ∈

≤ ∈

≥

∑

(7.4)

Que resolvido pelo SIMPLEX para 0,000t = nos fornecerá o primeiro ponto

localizado na fronteira não dominada:

7



sol

= =

Observemos que a 7sol está bem próxima da 6sol . 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 0,020t∆ = . Para tanto, os

vetores ew d , já normalizados, ficarão:

43,636 35,55629,091 53,333

e 43,636 35,55643,636 35,556

w d

= =

Atualizar o vetor jb com os valores da 7sol . Resolvendo o PPL (7.4) com os

vetores e jw b atualizados, faremos a seguinte análise de sensibilidade:

1( ) 0,000B b td− + ≥

que nos fornecerá o seguinte intervalo de variação:

[ ] [ ]1 2; 0,000;0,064t t t t− + =

84

Prosseguindo nesta direção, com incrementos 0,020t∆ = 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ável8IS

pela26I

S . Computando a nova base e realizando novamente a análise de

sensibilidade, obteremos:

[ ] [ ]1 2; 0,064;0,385t t t t− + =


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,9120,000 0,000

e 40,000 70,17560,000 44,912

w d

= =

85

Atualizemos o vetor jb com os valores da última solução. Resolvendo o PPL

(7.4) com os vetores e jw b atualizados, teremos a seguinte análise de sensibilidade:

[ ] [ ]1 2; 0,000;0,363t t t t− + =


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, 285AT-26 220, 237

A-1 220,237C-98 300,000R-95 210,000R-35 140, 469R-99 64,000F-5E 182,308F-103 134, 434

x

= =

86

Os valores que a função capacitação assumem na solução preferida são:

T-27 93,611AT-26 83,611

A-1 83,611C-98 100,000

( ) R-95 100,000R-35 66,663R-99 30,000F-5E 97,330F-103 87,330

f x

= =

FAe III 82, 462Ataque 86,944

( )Reconhecimento 74,166

Caça 92,330

f x

= =

87

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.

88

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;

89

• 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 utilizar-

se 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).

90

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.

91

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.

92

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.

Documents

AGREGAÇÃO DE UMA ABORDAGEM “WIN-WIN” À ...helcio/Agregacao.pdfii VIEIRA JUNIOR, HÉLCIO Agregação de uma Abordagem “WIN-WIN” à Modelagem Multi-Objetivo [Rio de Janeiro]