Procedimento interactivo dedicado ao problema da
mochila bicritério
Carlos Gomes da Silva(2;3); José Figueira(1;3;4) e João Clímaco(1;3)
(1) Faculdade de Economia da Universidade de Coimbra
Av. Dias da Silva, 165
3004-512 Coimbra
Tel: 239 760 500, Fax: 239 403 511
E-mail: …[email protected]
(2) Instituto Politécnico de Leiria
Escola Superior de Tecnologia e Gestão de Leiria
Morro do Lena, Alto Vieiro
2401-951 Leiria
Tel: 244 820 300, Fax: 244 820 301
E-mail: [email protected]
(3) INESC-Coimbra
Rua Antero de Quental, 199
3000-033 Coimbra
Tel.: 239 851 040, Fax: 239 824 692
E-mail: [email protected]
(4) Dimacs Center-Rutgers University
96 Frelinghusysen, Road Piscataway, N108855-8018 USA
Tel.: 1732 445 5932
Fax: 1732 445 0075
March 17, 2003
1
Resumo
Apesar de inúmeros investigadores se terem dedicado ao estudo do problema
combinatório da mochila, a determinação de uma solução óptima permanece um
problema de difícil resolução. Para além disso, os problemas de decisão reais requerem frequentemente a incorporação de mais do que um critério. A noção de
óptimo dá lugar ao conceito de solução não dominada. Identi…car o conjunto completo das soluções não dominadas tem sido objecto dos trabalhos publicados nesta
área. No entanto, até à data, não se conhece um procedimento e…ciente para obter
esse conjunto. A adaptação e extensão dos resultados teóricos do caso monocritério
para o multicritério ainda não permitiu conceber algoritmos e…cientes. A dimensão
dos problemas que podem ser resolvidos por esta via não ultrapassa um milhar de
variáveis, para o caso mais simples, isto é, para instâncias bicritério.
Neste trabalho, abordamos o problema da mochila numa perspectiva de estudo
interactivo. O agente de decisão (AD) dispõe de procedimentos de pesquisa global
e local, o que lhe permite apreender a diversidade de soluções do problema, no que
se refere aos valores dos critérios. Pode, assim, circunscrever progressivamente o
âmbito da sua análise. Estes procedimentos são integrados num sistema interactivo
de apoio à decisão (SIAD) que incorpora diversas opções para interagir com o AD.
Palavras-chave: problema da mochila, análise multicritério, abordagem interactiva, sistema de apoio à decisão.
Agradecimentos: Projecto MONET (POCTI/GES/37707/2001).
O segundo autor agradece também o suporte da bolsa SFRH/BDP/6800/2001.
2
Índice
1 Introdução
5
2 A abordagem interactiva dedicada ao problema da mochila bicritério
2.1 Opções interactivas com informação de nível global . . . . . . . . . . . .
2.1.1 Óptimos individuais . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Subconjunto de soluções suportadas . . . . . . . . . . . . . . . . .
2.1.3 Conjunto das soluções suportadas . . . . . . . . . . . . . . . . . .
2.2 Opções interactivas com informação de nível local . . . . . . . . . . . . .
2.2.1 Análise de uma região de interesse . . . . . . . . . . . . . . . . . .
2.2.2 Análise de uma solução . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Análise decorrente da de…nição de um per…l de solução . . . . . .
.
.
.
.
.
.
.
.
8
11
11
11
12
14
14
21
26
3 Utilização da abordagem interactiva proposta com recurso a um SIAD 46
4 Conclusão
51
A Apêndice: Método simplex com variáveis limitadas
55
3
Índice de Figuras
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Opções interactivas segundo níveis de informação requeridos . . . . . . . .
Processo de obtenção do conjunto das soluções não dominadas suportadas
Soluções não dominadas numa região de interesse . . . . . . . . . . . . . .
Árvore de exploração da região de interesse . . . . . . . . . . . . . . . . . .
Soluções não dominadas na região de interesse . . . . . . . . . . . . . . . .
Vizinhança de uma solução . . . . . . . . . . . . . . . . . . . . . . . . . . .
Maximização de f(x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Espaço dos objectivos do problema relaxado . . . . . . . . . . . . . . . . .
Valor máximo para f (x) na região de interesse . . . . . . . . . . . . . . . .
Convergência para a região seleccionada . . . . . . . . . . . . . . . . . . .
Mudança de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Árvore binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Óptimos individuais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Subconjunto de soluções suportadas . . . . . . . . . . . . . . . . . . . . . .
Introdução de restrições por imposição de níveis mínimos nos critérios . . .
Análise de uma região de interesse de…nida por selecção de soluções . . . .
Per…l de solução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Soluções não dominadas num raio de vizinhança . . . . . . . . . . . . . . .
Soluções alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Conjunto de soluções não dominadas . . . . . . . . . . . . . . . . . . . . .
4
10
14
15
20
21
22
29
33
35
36
39
45
46
47
48
48
49
49
50
51
1
Introdução
Suponhamos que dispomos de um conjunto de objectos, com um peso e valor conhecidos,
e de uma mochila com capacidade limitada. Determinar o subconjunto destes objectos
cujo peso não excede aquela capacidade e que maximiza o seu valor total, corresponde a
resolver o problema da mochila.
Este problema, de natureza combinatória, é bastante conhecido e tem sido extensivamente estudado por muitos autores (ver, por exemplo, Martello e Toth, 1990 e Pissinger,
1995). Inúmeros problemas reais podem ser formulados como o problema da mochila,
ou como variantes deste. As aplicações mais familiares são os problemas de embalagem,
de carregamento de equipamentos, de corte de materiais, de controlo orçamental e de
selecção de projectos de investimento. O problema da mochila também é interessante por
constituir um subproblema de modelos mais vastos, como por exemplo, os de constituição de tripulações de voo, de planeamento da produção, de problemas de partição e de
concepção de circuitos eléctricos.
Enquanto problema combinatório, pode ser resolvido por enumeração exaustiva de
todas as soluções, procedendo-se posteriormente e por comparação, à identi…cação da
melhor solução. Todavia, a determinação exaustiva destas soluções é um processo computacionalmente moroso, tornando-se mesmo inviável a partir de determinadas dimensões
(um problema com apenas 20 itens pode possuir até 1.048.576 soluções). Assim, a via
de resolução por enumeração exaustiva é de utilidade muito reduzida, senão mesmo nula,
para problemas de grande dimensão.
A primeira resolução deste problema, por técnicas mais inteligentes, data dos anos
50, por aplicação da função recursiva (programação dinâmica) de Bellman. A partir de
então, foram propostos inúmeros melhoramentos: a de…nição do limite superior para o
valor óptimo da função objectivo, por Dantzig em 1957; a resolução do problema pela
técnica de partição e avaliação sucessivas, por Kolesar em 1967; a resolução de problemas
de grandes dimensões, igualmente pela técnica de partição e avaliação sucessivas, por
Harowitz e Sahni, nos anos 70; o primeiro procedimento de redução da dimensão do
problema (por …xação do valor de algumas variáveis) de Ingargiola e Korsh em 1973; um
novo limite superior, por Martello e Toth, em 1977; o algoritmo de Balas e Zemel, em
1980, baseado na ordenação de apenas um subconjunto de itens; um novo algoritmo de
Martello e Toth que permite resolver instâncias difíceis (Pissinger, 1995; Martello e Toth,
1998).
A totalidade destes estudos foram dedicados à resolução do problema monocritério. No
entanto, os problemas de decisão reais requerem, vulgarmente, uma análise considerando
explicitamente vários critérios. São exemplos de aplicação do problema da mochila multicritério a selecção de projectos de investimento com decisores e critérios múltiplos (Kwark
et al., 1996); a selecção de projectos de investimento que não são independentes entre si,
5
em vias de comunicação (Teng e Tzeng, 1996) e a geração da fronteira e…ciente discreta
na selecção de projectos de investimento (Rosenblatt e Sinnuany-Stern, 1989).
Nos problemas com mais do que um critério não existe, em geral, uma solução que
optimize simultaneamente todos os critérios envolvidos. Assim, a noção de solução óptima
deixa de fazer sentido. Em contrapartida, existem soluções admissíveis com características
particulares, designadas por soluções não dominadas, em que a melhoria do valor de um
dos critérios é sempre feita à custa da degradação do valor de pelo menos um dos restantes,
ou seja, os critérios estão em con‡ito.
É característica destes problemas o aumento signi…cativo do número de soluções não
dominadas com o aumento do número de critérios, o que di…culta a sua resolução. Existem
várias abordagens para analisar problemas deste tipo, como, por exemplo, a enumeração
exaustiva de todas as soluções não dominadas, a pesquisa de um conjunto reduzido de
soluções não dominadas, ou a pesquisa interactiva de soluções mediante um protocolo
do tipo questão-resposta, onde se incorporam progressivamente e de modo interactivo as
preferências do AD, durante o processo de decisão que, em geral, consiste na escolha da
”melhor solução possível”.
Os métodos utilizados podem classi…car-se como exactos ou aproximados. Nos métodos exactos as soluções obtidas são efectivamente não dominadas, ao contrário das apresentadas pelos métodos aproximados, onde são apenas potencialmente não dominadas.
Nos métodos exactos são utilizadas as técnicas soma ponderada, "¡restrição e a minimização da distância a um ponto de referência para obtenção das soluções não dominadas
(Steuer, 1986). Aos métodos aproximados pertencem as heurísticas e as meta-heurísticas,
tais como os algoritmos genéticos, os métodos evolutivos, o simulated annealing, as redes neuronais, a pesquisa tabu, entre outros. Nestes métodos pretende-se estabelecer um
compromisso entre a qualidade das soluções obtidas e o tempo necessário para as calcular.
Recentemente, foram propostos métodos para a geração de todas as soluções não dominadas para o caso bicritério, nomeadamente o método de Visée et al. (1998) e de Captivo
et al. (2003). O método proposto por Visée et al. (1998) encontra-se estruturado em
duas fases. Na primeira fase, determinam-se todas as soluções suportadas extremas e
não extremas da envolvente convexa da região admissível, com recurso a um problema
soma ponderada dos critérios. Na segunda fase, são analisadas, com recurso à técnica
de partição e avaliação sucessivas, todas as soluções suportadas adjacentes com o objectivo de obter o conjunto das soluções não suportadas. O método proposto por Captivo
et al. (2003) converte o problema da mochila bicritério numa rede acíclica sobre a qual
aplica um algoritmo de etiquetagem. O problema é transformado num problema de caminho mais longo bicritério. Este método calcula indistintamente as soluções suportadas
e as soluções não suportadas. Para o caso multicritério, Ulungu et al. (1997), apresentaram um procedimento de cálculo baseado na técnica de partição e avaliação sucessivas,
mas não publicaram quaisquer resultados, pelo que a sua e…ciência não foi avaliada.
Outras referências a métodos exactos e aproximados podem ser encontradas em Ehrgott
e Gandibleux (2002).
Mesmo no caso bicritério, os métodos disponíveis ainda não podem ser aplicados com
sucesso à resolução de problemas de grandes dimensões, o que tem motivado o desenvolvi6
mento de métodos aproximados. É o caso do método de Gandibleux e Fréville (2000),
que aproxima a fronteira não dominada através da aplicação da pesquisa tabu.
Contudo, mesmo quando a geração de todas as soluções não dominadas é possível,
muitas vezes grande parte do esforço computacional requerido é inútil, porque o AD pode
não ser capaz, ou não estar interessado, em analisar todas essas soluções. A abordagem
interactiva tira partido deste facto, articulando fases de cálculo com fases de diálogo
com o AD, propiciando a incorporação progressiva das suas preferências. Teghem et al.
(2000) utilizam de um modo interactivo um procedimento heurístico baseado no simulated
annealing, para estudar o problema da mochila multicritério de grandes dimensões.
Neste trabalho, abordamos o problema bicritério numa perspectiva interactiva, porém,
com recurso exclusivo a métodos exactos. São disponibilizadas diferentes opções interactivas que se caracterizam pelo tipo de informação que o AD pretende utilizar/obter.
Distinguimos entre informação global e informação local, na construção destas opções de
interacção. Desenvolvemos ainda um SIAD, em Delphi 4, da Borland, onde se encontram
implementados os procedimentos interactivos propostos.
Este texto está estruturado em quatro secções. Na secção 2 - Abordagem interactiva
dedicada ao problema da mochila bicritério - analisamos o problema da mochila numa perspectiva interactiva; propomos algumas opções de interacção com o AD divididas segundo
níveis de informação prestada; a exploração das propriedades do problema matemático
subjacente a cada uma daquelas opções é aqui apresentada, justi…cando os processos de
resolução propostos. Na secção 3 - Utilização da abordagem interactiva proposta com
recurso a um SIAD - utilizamos como instrumento de apoio à decisão num problema
simulado. Algumas janelas da aplicação são apresentadas. Na secção 4 - Conclusão sintetizamos as principais valências, as maiores limitações e os aspectos que merecem ser
desenvolvidos no futuro.
7
2
A abordagem interactiva dedicada ao problema da
mochila bicritério
O problema da mochila bicritério pode formular-se como segue:
max z1 (x1 ; :::; xn ) =
max z2 (x1 ; :::; xn ) =
n
P
j=1
n
P
j=1
n
P
sujeito a :
c1j xj
c2j xj
(1)
wj xj · W
j=1
xj 2 f0; 1g; j = 1; :::; n
onde xj = 1 se o item j (j = 1; :::; n) é incluído na mochila e xj = 0 caso contrário, W
é a capacidade da mochila, wj corresponde ao peso do item j e cij representa a valorização
do item j segundo o critério i, com i = 1; 2, assumindo-se ainda que cij ; W e wj são valores
n
P
inteiros positivos e que wj · W com
wj > W .
j=1
Mais sucintamente podemos reescrever (1) do seguinte modo:
max z1 (x) = c1 x
max z2 (x) = c2 x
sujeito a :
wx · W
x 2 f0; 1gn
(2)
em que c1 = (c11 ; :::; c1n ) ; c2 = (c21 ; :::; c2n ) ; w = (w1 ; :::; wn ) e xT = (x1 ; :::; xn ).
Não existindo, em geral, uma solução que maximize simultaneamente os dois critérios,
importa confrontar o AD apenas com as soluções em que a melhoria de um deles não
se pode concretizar sem a degradação do outro. Este conceito é explicitado na de…nição
seguinte.
De…nição 1 (Solução não dominada) Um vector z a = (z1a ; z2a ) 2 Z diz-se não dominado sse @ z = (z1 ; z2 ) 2 Z : z ¸ z a ; z 6= z a (z ¸ z a sse (zi ¸ zia , i = 1; 2) e z 6= z a sse
(9 i 2 f1; 2g : zi 6= zia )) :
No espaço de decisão o conceito de solução não dominada corresponde ao de solução
e…ciente. Assim, a solução x+ 2 X = fx 2 f0; 1gn : wx · W g diz-se uma solução e…ciente
sse @ x 2 X : z(x) ¸ z(x+ ); z(x) 6= z(x+ ).
8
Existem múltiplas técnicas que podem ser utitlizadas na determinação de soluções não
dominadas (ver Steuer, 1986). Uma delas consiste na optimização de uma função soma
ponderada dos critérios1 . O teorema seguinte fornece essa garantia.
Teorema 1 (Soluções e…cientes) Se x+ 2 X é uma solução do problema max f¸1 z1 (x)
+¸2 z2 (x) : x 2 Xg ;com ¸i > 0, i = 1; 2 e ¸1 + ¸2 = 1, então x+ é uma solução e…ciente
deste problema (e z(x+ ) é uma solução não dominada).
Contudo, a determinação de todas as soluções não dominadas nem sempre se revela
apropriada no sentido de utilização da capacidade cognitiva limitada do AD em analisar,
de uma só vez, um conjunto elevado de soluções, nomeadamente, porque estas podem
ser em número muito elevado, por outro lado, o esforço computacional subjacente à sua
determinação, em instâncias de dimensões elevadas, ou mesmo, médias, também é considerável. Os procedimentos interactivos são particularmente úteis nestas circunstâncias.
Aquelas duas di…culdades estão de facto presentes nos problemas da mochila com um
elevado número de itens. Por exemplo, em Visée et al. (1998), podemos veri…car que um
problema com 500 itens tem em média 1778 soluções não dominadas, sendo o tempo de
cálculo para as determinar de 55 minutos.
Os procedimentos interactivos caracterizam-se por alternar fases de cálculo com fases
em que existe incorporação de informação do AD. As fases de cálculo são dirigidas à
resolução de subproblemas originados por introdução e/ou modi…cação de parâmetros
com base nas indicações do AD. As soluções obtidas apresentam a dupla vantagem de
veri…carem os requisitos impostos e de serem em bastante menor número. A abordagem
interactiva, aqui apresentada, tem como principais vectores de orientação o tipo de informação que é prestada e requerida ao AD. A natureza da informação trocada com o
AD in‡uencia a qualidade do procedimento interactivo, sendo esta tanto maior quanto
mais simples e perceptível aquela for (ver, por exemplo, Roy, 1996, para detalhes sobre
características potenciadoras da qualidade dos métodos interactivos).
Neste trabalho, e relativamente ao nível da informação apresentada, distinguimos entre
informação de nível global e informação de nível local. Em cada um dos tipos o AD
pode seleccionar a informação a apresentar a partir de um conjunto de procedimentos
alternativos que de…nimos a seguir e que se ilustram na Figura 1. A intervenção do AD
consiste em utilizar as opções de interacção disponíveis, concretizando o valor de alguns
parâmetros requeridos e reagindo aos resultados que lhe são apresentados, procurando
reduzir de forma progressiva o âmbito da pesquisa.
No conjunto das opções disponíveis o AD é solicitado a especi…car um conjunto de
informações muito simples, como o número máximo de soluções a serem apresentadas, uma
região de interesse (delimitada pela indicação de duas soluções ou de níveis mínimos para
os critérios), a relaxação permitida nos valores dos critérios, ponderadores dos critérios,
com o objectivo único de guiar o processo de determinação de soluções não dominadas.
1
Mais adiante ressalvamos a impossibilidade de determinação de certas soluções com recurso a esta
técnica
9
Informação Global
Óptimos Individuais
Parâmetros requeridos
número máximo de soluções a
apresentar
Subconjunto de soluções
suportadas
Conjunto integral das soluções
suportadas
Informação Local
Análise de uma região de
interesse
¾ determinação de todas as soluções não dominadas
Análise de uma solução
¾ especificação de níveis de relaxação nos valores dos
critérios
¾ determinação das soluções não dominadas num raio de
vizinhança de uma solução
¾ determinação de soluções alternativas no espaço de decisão
Parâmetros requeridos
região de interesse (duas
soluções ou níveis mínimos
para os critérios)
relaxação permitida nos
critérios
uma solução não dominada
Análise decorrente da definição
de um perfil de solução
ponderadores dos critérios
¾determinação da solução que maximiza uma função numa região de interesse
Figura 1: Opções interactivas segundo níveis de informação requeridos
10
2.1
Opções interactivas com informação de nível global
Consideramos informação de nível global a que se destina a fornecer ao AD uma representação rápida e genérica do conjunto das soluções não dominadas do problema. Trata-se
de informação que não requer quaisquer parâmetros de entrada por parte do AD. Na
informação de nível global incluímos a determinação:
² dos óptimos individuais;
² do subconjunto de soluções suportadas;
² do conjunto integral das soluções suportadas;
2.1.1
Óptimos individuais
A determinação dos óptimos individuais para cada um dos critérios é feita pela resolução
do problema (3) com ponderador próximo de um no critério que se pretende maximizar
(não exactamente igual a um para evitar a obtenção eventual de soluções fracamente não
dominadas; ver Steuer, 1986).
max ¸1 c1 x + ¸2 c2 x
sujeito a :
wx · W
x 2 f0; 1gn
¸i > 0; i = 1; 2 e ¸1 + ¸2 = 1
(3)
Resolvemos este problema com o algoritmo MT1 de Martello e Toth (1990). Com a
solução óptima do problema é construída a sua imagem no espaço dos critérios. Ao AD
são apresentados os valores extremos de ambos os critérios.
2.1.2
Subconjunto de soluções suportadas
Comecemos por distinguir entre soluções não dominadas suportadas e soluções não dominadas não suportadas.
De…nição 2 (Solução não dominada suportada) Uma solução não dominada z a =
(z1a ; z2a ) 2 Z = f(z1 (x); z2 (x)) : x 2 Xg diz-se suportada se existir um vector (¸1 ; ¸2 ) com
¸i > 0 tal que z a =argmax f¸1 z1 + ¸2 z2 : (z1 ; z2 ) 2 Zg :
Portanto, a resolução de um problema soma ponderada tipo (3) permite determinar
soluções não dominadas, mais especi…camente, soluções não dominadas suportadas.
Existem, contudo, algumas soluções que, sendo não dominadas, não podem ser obtidas
pela resolução do problema de optimização da De…nição 2 (temos portanto que o reverso
do Teorema 1 não é verdade). Estas soluções designam-se por soluções não dominadas
não suportadas.
11
Com base nos desenvolvimentos presentes do problema da mochila, as soluções mais
fáceis de obter são as soluções suportadas. Estas são obtidas por resolução de instâncias
monocritério, para as quais existem métodos bastante rápidos. Esta opção é particularmente adequada em problemas com um elevado número de itens onde, em geral, o
conjunto de soluções não dominadas é bastante elevado.
Este subconjunto deve possuir, de preferência, soluções bem distribuídas no espaço dos
critérios. Em geral, uma distribuição uniforme dos ponderadores utilizados na resolução
daquelas instâncias permite obter soluções com aquela característica. Se representarmos
por À o número máximo de soluções a ser calculado, resolvemos À problemas do tipo (3),
em que ¸k1 e ¸k2 são os ponderadores utilizados na resolução do k ¡ e¶simo problema. Os
ponderadores são uniformemente distribuídos no intervalo [0,1]:
¸k1
1
1
=
+ (k ¡ 1) ) ¸k2 = 1 ¡
2À
À
µ
1
1
+ (k ¡ 1)
2À
À
¶
(4)
Note-se que é possível obter soluções repetidas, o que é particularmente frequente em
problemas com um número reduzido de itens e um À elevado.
2.1.3
Conjunto das soluções suportadas
Num procedimento interactivo, o cálculo exclusivo das soluções suportadas, permite ao
AD ter uma ideia aproximada da con…guração da fronteira não dominada do problema,
podendo estas, em geral, ser determinadas rapidamente. O conjunto das soluções não
dominadas suportadas é obtido por resolução de problemas monocritério onde os ponderadores são modi…cados iterativamente, à semelhança do método de Visée et al. (1998).
Na primeira fase deste método, começa-se por determinar as soluções que optimizam
individualmente os critérios e colocam-se essas soluções, ordenadas de modo lexicográ…co
segundo valores crescentes de z1 , numa lista S, que contém apenas soluções e…cientes. As
soluções desta lista serão utilizadas para de…nir os ponderadores dos critérios na função
soma ponderada em problemas seguintes, conforme segue: sendo xp e xq duas soluções
consecutivas de S, resolve-se o problema (3) com ¸1 = z2p ¡z2q e ¸1 = z1q ¡z1p (aqui deixamos
de satisfazer, sem consequências adicionais, a restrição ¸1 + ¸2 = 1): Designe-se por xr
uma solução do problema (3) com xr 6= xp 6= xq . Se f (xr ) = f (xp ) = f (xq ), coloca-se xr ,
numa outra lista, S0. Caso contrário, coloca-se xr em S, reordenando-a. Este processo é
repetido, resolvendo o problema (3) com novos ponderadores, até que todos os pares de
soluções consecutivas de S tenham sido analisados. A lista S0 tem como função evitar
que o mesmo problema de optimização (3) seja resolvido mais do que uma vez, já que as
suas soluções, no espaço dos critérios, se encontram sobre o segmento de recta que une z p
e zq .
O conjunto de todas as soluções suportadas e…cientes do problema corresponde às
soluções constantes nas listas S e S0. Este conjunto é ordenado lexicogra…camente segundo
valores crescentes de z1 .
12
Exemplo 1
Consideremos o seguinte problema bicritério com 10 itens.
max z1 = 68x1 + 26x2 + 32x3 + 70x4 + 48x5 + 75x6 + 42x7 + 89x8 + 48x9 + 6x10
max z2 = 23x1 + 37x2 + 32x3 + 91x4 + 30x5 + 56x6 + 55x7 + 67x8 + 41x9 + 55x10
sujeito a:
58x1 + 84x2 + 66x3 + 32x4 + 77x5 + 73x6 + 60x7 + 12x8 + 12x9 + 68x10 · 271
xj 2 f0; 1g; j = 1; :::; 10:
(a) S = ;; S 0 = ;:
(b) Óptimo de z1 : x¤1 = (1001110110) : No espaço dos critérios esta solução corresponde
ao ponto z(x¤1 ) = (398; 308):
© ª
S = x¤1 :
(c) Óptimo de z2 : x¤2 = (0001010111) : No espaço dos critérios esta solução corresponde
ao ponto z(x¤2 ) = (330; 365):
©
ª
S= x¤1 ; x¤2 .
(d) O próximo problema a ser resolvido é então,
max ¸1 (68x1 + 26x2 + 32x3 + 70x4 + 48x5 + 75x6 + 42x7 + 89x8 + 48x9 + 6x10 ) +
¸2 (23x1 + 37x2 + 32x3 + 91x4 + 30x5 + 56x6 + 55x7 + 67x8 + 41x9 + 55x10 )
sujeito a:
58x1 + 84x2 + 66x3 + 32x4 + 77x5 + 73x6 + 60x7 + 12x8 + 12x9 + 68x10 · 271
xj 2 f0; 1g; j = 1; :::; 10
com ¸1 = 330 ¡ 308 = 22 e ¸2 = 398 ¡ 365 = 33:
A solução óptima deste problema corresponde a x¤3 =(1001011110) que tem como
imagem no espaço dos critérios o ponto z(x¤3 ) =(392; 333).
S = f(1001110110) ; (1001011110) ; (0001010110)g :
(e) Como z(x¤2 ) = (330; 365) e z(x¤3 ) =(392; 333) são soluções adjacentes, a próxima
função soma ponderada a ser maximizada é (365 ¡ 333)z1 (x) + (392 ¡ 330)z2 (x) =
32z1 (x)+62z2 (x): A solução óptima obtida corresponde novamente ao ponto z(x¤2 ) =
(330; 365). Isto signi…ca que as únicas soluções suportadas, a exitirem entre estas
duas soluções, se situam no segmento que as une.
(f) Agora os pontos z(x¤3 ) = (392; 333) e z(x¤1 ) = (398; 308) são os primeiros pontos
adjacentes a serem analisados, a próxima função soma ponderada a ser maximizada
é então (333 ¡ 308)z1 (x) + (398 ¡ 392)z2 (x) = 25z1 (x) + 6z2 (x): A solução óptima
obtida corresponde ao ponto z(x¤3 ) =(392; 333), já anteriormente obtido. Mais uma
vez, isto signi…ca que as únicas soluções suportadas a existirem entre estas duas
soluções situam-se no segmento que as une. S0 permanece vazia o que signi…ca que
o problema tem como soluções não dominadas suportadas as imagens das soluções
em S.
13
z2
• z(x*2)=(330,365)
32
• z(x*3)= (392,333)
62
25
6
• z(x*1)= (398,308)
z1
Figura 2: Processo de obtenção do conjunto das soluções não dominadas suportadas
2.2
Opções interactivas com informação de nível local
Consideramos como informação de nível local a que respeita a uma dada solução, a uma
vizinhança de uma solução ou a uma subregião do espaço dos critérios. Associamos a
informação de nível local à análise:
² de uma área de interesse;
² de uma solução seleccionada;
² decorrente da de…nição de um per…l de solução.
2.2.1
Análise de uma região de interesse
A de…nição de uma região de interesse consiste na selecção de uma subregião do espaço
dos critérios, sobre a qual o AD pretende fazer incidir a sua análise. Esta selecção pode
ser realizada por indicação de níveis mínimos para o valor dos critérios, ou ainda, por
selecção de duas soluções previamente obtidas. Nesta região de interesse de…nimos como
objectivo conhecer todas as soluções não dominadas aí contidas.
A de…nição de uma área de interesse tem sido utilizada noutros procedimentos interactivos. Em Ferreira et al. (1994), por exemplo, o procedimento aplica-se a problemas de
localização de equipamentos perigosos contemplando a maximização de uma função soma
ponderada.
O problema a resolver quando se de…ne uma região de interesse com o objectivo de
conhecer todas as soluções não dominadas aí contidas, é o seguinte:
14
max z1 (x) = c1 x
max z2 (x) = c2 x
sujeito a :
x 2 X¸
(5)
©
ª
onde X ¸ = x 2 f0; 1gn : wx · W; z1 (x) ¸ z1min ; z2 (x) ¸ z2min .
Quando a região de interesse é de…nida por selecção de duas soluções (z11 ; z21 ) e (z12 ; z22 );
então z1min = z11 + " e z2min = z22 + " (com " > 0 e convenientemente pequeno).
Vamos resolver o problema de determinação do conjunto completo das soluções não
dominadas na região, por adaptação do método gerador de Visée et al. (1998). Assim,
após a determinação das soluções suportadas na região (ver Figura 3), e ainda da primeira
solução à esquerda de z1min (z e ) e da primeira abaixo de z2min (z a ), a única diferença em
relação ao caso geral, consiste na delimitação de triângulos para localização das soluções
não suportadas, resultado da redução da região de pesquisa.
z2
• ze
•
•
( z1min , z 2min )
• za
z1
Figura 3: Soluções não dominadas numa região de interesse
A principal preocupação, com a adaptação daquele método à região especí…ca, consiste
em minimizar o número de problemas (3) a serem resolvidos com vista a obter todas as
soluções não dominadas suportadas na região. De facto, se a região se situar próxima de
um dos óptimos individuais, e devido ao modo de selecção dos ponderadores, as primeiras
soluções dos problemas (3) tendem a afastar-se dos óptimos individuais dos critérios,
retardando-se assim a determinação das soluções procuradas.
Vamos tentar reduzir o número de problemas a serem resolvidos com a modi…cação
dos ponderadores do primeiro problema. Em vez de considerarmos como ponderadores
o vector perpendicular ao segmento de recta que une os óptimos individuais, vamos considerar o vector que une o ponto nadir ao ponto dos mínimos da região de interesse
15
¡
¢
z1min ; z2min : Procedendo deste modo, o gradiente da função a ser maximizada pode favorecer a obtenção de soluções na região. A partir daqui os ponderadores são obtidos
com base nas soluções consecutivas de S , sem que nesta lista sejam analisados os pares
de soluções com imagem no espaço dos critérios à esquerda de z1min ou abaixo de z2min .
A determinação das soluções não suportadas do problema faz-se analisando todos
os triângulos de…nidos pelas soluções suportadas adjacentes, região possível para a sua
localização. Cada triângulo é analisado separadamente por aplicação de um procedimento
de partição e avaliação sucessivas.
Consideremos z p e z q duas soluções suportadas adjacentes e notemos por ¢pq o triângulo correspondente. Quando z p ( z q ) se situa fora da região de…nida, substitui-se z p (z q )
pelo ponto de intersecção do segmento de recta z p z q com a recta z1min (z2min ): Começamos
por aplicar o procedimento de redução da dimensão do problema e que descrevemos de
seguida.
Designemos por zi+ um valor mínimo para o critério zi . Se ao colocarmos xk = µ; k 2
f1; :::; ng, com µ 2 f0; 1g e resolvermos o problema (6) abaixo se veri…car que fi¤ < zi+ ,
então pode-se …xar xk = 1 ¡ µ.
fi¤ = cik µ + max
(
n
X
cij xj :
j=1;j6=k
n
X
j=1;j6=k
)
wj xj · W ¡ wk µ; 0 · xj · 1; j 2 f1; :::; ng n fkg
(6)
O valor de fi¤ pode ser substituído pelo limite U2 , traduzindo-se numa restrição mais
exigente, o que em princípio permite …xar mais variáveis 2 .
2
Em Martello e Toth (1990) são apresentados limites mais exigentes para o valor óptimo da função
objectivo do problema
max
n
P
cj xj
j=1
s.a:
n
P
wj xj · W
(7)
j=1
xj 2 f0; 1g ; j = 1; :::; n
Neste trabalho, utilizamos frequentemente o limite U2 que consideramos ser um bom compromisso
entre o tempo necessário no seu cálculo e a sua qualidade. Este limite baseia-se na inclusão e exclusão
do item crítico:
U2 =
½
¾
cf +1
cf ¡1
cj + max w
; cf ¡ (wf ¡ w)
wf +1
wf ¡1
j=1
f¡1
X
fP
¡1
cj+1
cj
¸
; j = 1; :::; n ¡ 1 e w = W ¡
wj :
wj
wj+1
j=1
Como cj e wj são inteiros, U2 pode ser substituído por
onde
16
(8)
Consideremos o critério zi e ordenemos os itens segundo valores não crescentes do seu
j
P
valor relativo. Designemos por fzi o item crítico: f zi = minfj :
wh > W g e por '(k)
h=1
a posição do item k original na ordenação estabelecida. Sendo assim, o problema anterior
apenas tem que ser resolvido quando se está a analisar a rami…cação xk = 0 e '(k) · fzi ,
ou, quando se está a analisar a rami…cação xk = 1 e '(k) ¸ f zi .
No …nal do procedimento, designemos por N0 o conjunto dos índices das variáveis
…xadas a zero, por N1 o conjunto dos índices das variáveis …xadas a um, e por F o
conjunto dos índices das variáveis não …xadas: F = f1; :::; ngn(N0 [ N1 ).
O problema original (2) é reduzido, resumindo-se então a:
max z1 (x) =
P
c1j +
j2N1
max z2 (x) =
P
P
c1j xj
j2F
c2j
+
j2N1
P
c2j xj
j2F
sujeito a :
P
P
wj xj · W ¡
wj
j2F
(10)
j2N1
x 2 f0; 1gjF j
As variáveis, cujo valor não está de…nido (variáveis livres), são ordenadas segundo
valores não crescentes do rácio
¸1 c1j + ¸2 c2j
wj
(11)
com ¸1 = z2p ¡ z2q e ¸2 = z1q ¡ z1p :
Em cada nodo, distinguem-se então as variáveis livres e as variáveis …xas. Das variáveis
livres, escolhe-se a que apresenta maior valor no rácio (11). Designemos essa variável por
xk . Criam-se dois subnodos, por …xação de xk = 1 e de xk = 0, respectivamente.
Um subnodo é abandonado quando se veri…car pelo menos uma das seguintes condições:
² se para o valor das variáveis …xas e o valor nulo das variáveis livres, não se veri…car
a condição de admissibilidade da solução;
² se o valor de z1 for superior a z1q ; ou,
² se o valor de z2 for superior a z2p :
Caso contrário, determinam-se os limites superiores para z1 , z2 e zl (utilizamos o
limite U2 ). O subnodo é abandonado se:
U2 =
f
¡1
X
cj + max
j=1
½¹
º ¹
º¾
cf +1
cf ¡1
w
; cf ¡ (wf ¡ w)
wf +1
wf ¡1
onde b²c representa o maior inteiro não superior a ²:
17
(9)
² o limite para z1 não for superior a z1p , ou;
² o limite para z2 não for superior a z2q , ou
² o limite para zl não for superior ao seguinte limite u (Visée et al., 1998).
©
ª
u = min ¸1 z1i + ¸2 z2i+1
i=0;:::;m
(12)
com z 0 = z p e z m = z q :
Quando um determinado subnodo for abandonado, analisa-se o último subnodo criado.
Quando todas as variáveis estiverem …xadas (nodo terminal), coloca-se esta solução numa
lista L (vazia no início do procedimento) caso não seja dominada por nenhuma outra
solução dessa lista. As soluções em L que sejam dominadas pela solução introduzida, são
eliminadas. Actualiza-se o limite u e analisa-se o último nodo criado e não abandonado.
Quando todos os nodos forem abandonados ou quando todos os nodos forem terminais,
então a lista L contém todas as soluções e…cientes não suportadas no triângulo ¢pq .
Exemplo 2 Suponhamos que no problema bicritério do Exemplo 1 é de…nida uma região de
interesse pela introdução das restrições z1 (x) ¸ 354 e z2 (x) ¸ 338:
1. Apliquemos as Fases 1 e 2 do método de Visée et al. (1998).
Fase 1: Determinação das soluções suportadas na região
(a) Conforme referido anteriormente, os ponderadores do primeiro problema são obtidos
das componentes do vector que resulta da diferença entre o ponto mínimo (354; 338)
e o ponto nadir (330; 308) ; ou seja, ¸1 = 338 ¡ 308 = 30 e ¸2 = 354 ¡ 330 = 24.
Maximizando então a função 30z1 (x) + 24z2 (x) obtemos como solução óptima única
x¤ = (1001011110) que tem como imagem no espaço dos critérios o ponto (392,333),
que se situa fora da região.
S = f(1001110110) ; (1001011110) ; (0001010111)g :
(b) Consideremos agora a primeira e a segunda soluções de S. A próxima função a ser
maximizada é (365 ¡ 333)z1 (x)+ (392 ¡ 330)z2 (x) = 32z1 (x)+ 62z2 (x). A solução
óptima coincide com a solução obtida anteriormente. Como as únicas soluções obtidas neste problema são as soluções de partida, isto signi…ca que não existem soluções
não dominadas suportadas na região de interesse.
Fase 2: Determinação das soluções não suportadas na região
18
(a) Nesta fase consideramos a função f(x) = 32z1 (x) + 62z2 (x): Ordenando os itens
segundo valores não crescentes do rácio
x7 Â x1 Â x10 Â x3 Â x5 Â x2 :
32c1j +62c2j
wj
obtemos x8 Â x9 Â x4 Â x6 Â
(b) O valor mínimo para a função f (x), na região de…nida, é 32z1min + 62z2min = 32 £
354 + 62 £ 338 = 32284: Tendo como referência este valor, aplicamos o procedimento
de …xação de variáveis. O resultado do cálulo do limite U2 para cada valor de teste
é o seguinte:
Variável
x2 = 1
x3 = 1
x5 = 1
x10 = 1
Limite f(x)
31562
32820
32323
33253
Decisão
…xar x2 = 0
não …xar
não …xar
não …xar
Variável
x1 = 0
x4 = 0
x6 = 0
x7 = 0
x8 = 0
x9 = 0
x10 = 0
Limite f (x)
33807
28165
32199
32744
27829
30753
34248
Decisão
não …xar
…xar x4 = 1
…xar x6 = 1
.
não …xar
…xar x8 = 1
…xar x9 = 1
não …xar
Este procedimento permitiu …xar 5 das 10 variáveis. Com as variáveis …xadas temos
z1 = 282, z2 = 255 e f(x) = 24834. São variáveis livres x1 ; x3 ; x5 ; x7 e x10 : A
capacidade residual é igual a W ¡ w4 ¡ w6 ¡ w8 ¡ w9 = 142: Na Figura 4 apresentamos a árvore binária associada à exploração da região seleccionada. As razões de
abandono dos nodos encontram-se no quadro seguinte.
Nodo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
z1
324
392
324
330
324
356
356
324
372
282
350
356
356
282
356
z2
310
333
310
365
310
342
342
310
340
255
278
333
333
255
333
Limite z1 (x)
403
403
372
336
372
356
356
372
372
398
398
363
356
398
361
Limite z2 (x)
370
344
370
370
342
342
342
340
340
345
339
339
338
311
342
Limite f (x)
34283
34284
33807
33807
33212
33212
33212
32596
32984
32744
32744
32744
32203
32151
31695
Decisão
NA
A
NA
A
NA
NA
A
.
NA
A
NA
NA
NA
A
A
A
A - signi…ca abandonar; NA - signi…ca não abandonar
(c) Analisemos, por exemplo, o cálculo dos limites f(x) no nodo 1 (os restantes valores
foram obtidos de modo idêntico).
Atendendo à ordenação de acordo com f(x); obtemos como item crítico x10 dado que
19
0
x8=1
0
x9=1
0
x4=1
0
x6=1
0
x2=0
0
x7=0
x7=1
10
1
x1=1
2
x1=0
x1=1
x1=0
14
11
3
x10=1
x10=1
x10=0
12
4
15
5
x3=1
x3=0
6
8
x10=0
x5=0
13
x5=1
x5=0
7
9
Figura 4: Árvore de exploração da região de interesse
w7 + w1 + w10 > 142 e w7 ¡¥
+ w1 = 118 · 142: Calculamos
agora o limite¦¢U2 :
¦ ¥
¡
¡ 24) 3602
U2 = 4754 + 3602 + max (142 ¡ 118) £ 3008
;
3602
(68
= 8356+
66
58
max (1093; 869) = 9449:
Adicionando o valor da função com as variáveis …xadas a 1, otemos, …nalmente
24834 + 9449=34823.
(d) No interior do triângulo existem duas soluções não dominadas (ver Figura 5). A
primeira foi obtida no nodo 7, (356; 342) ; e a segunda foi obtida no nodo 9, (372; 340).
Com a obtenção da primeira solução actualizou-se o limite u, de acordo com (12),
passando o seu valor a ser igual a 3.2348 = min f32 £ 354 + 62 £ 342;
32 £ 356 + 62 £ 338g.
20
z2
•
• (356,340)
• (372,340)
338
•
354
z1
Figura 5: Soluções não dominadas na região de interesse
2.2.2
Análise de uma solução
Na análise de uma solução consideramos a especi…cação de níveis de relaxação para os
valores dos critérios, a especi…cação de um raio de vizinhança, a determinação de todas
as soluções não dominadas na subregião de…nida, assim como a determinação de soluções
alternativas no espaço de decisão, i.e., soluções que permitem obter os mesmos valores
dos critérios mas com diferente composição no espaço de decisão.Vejamos seguidamente
como é que estas opções são concretizadas.
2.2.2.1
Especi…cação de níveis de relaxação nos valores dos critérios
Perante uma solução não dominada já conhecida, o AD pronuncia-se relativamente aos
valores dos critérios.
Como resultado, especi…ca o valor que está disposto a prescindir num deles, de modo a
obter um acréscimo mínimo desejado no valor do outro. Matematicamente este problema
pode formular-se do seguinte modo:
max z1 (x) = c1 x
max z2 (x) = c2 x
sujeito a :
wx · W
z1 (x) ¸ z1+ + 41
z2 (x) ¸ z2+ + 42
x 2 f0; 1gn
(13)
com 41 £ 42 < 0:
A sua estrutura é equivalente à do problema da secção (2.2.1), tendo portanto o mesmo
processo de resolução.
21
De notar que o acréscimo pretendido para um dado critério pode não ser alcançável
com a relaxação máxima especi…cada para o outro critério. Neste caso, o problema (13)
é impossível.
2.2.2.2 Determinação das soluções não dominadas num determinado raio de
vizinhança de uma solução
Após conhecer uma solução que considera interessante, o AD pode pretender conhecer
soluções não dominadas na sua vizinhança. Para tal, especi…ca um raio de pesquisa em
relação aos critérios em análise. Como resultado apresentam-se todas as soluções não
dominadas contidas na região de…nida.
z2
∆z2 z+
•
∆ z1
z1
Figura 6: Vizinhança de uma solução
O raio pode ser de…nido em termos de incremento absoluto ou relativo (em percentagem do valor corrente dos critérios na solução escolhida) dos valores dos critérios
para a solução escolhida.
Como a solução seleccionada é não dominada, a região de vizinhança apenas de…ne
duas zonas possíveis para a localização de soluções não dominadas: a região à esquerda e
acima de z + e a região à direita e abaixo de z + (ver Figura 6) : De facto, uma vez que a
solução seleccionada é não dominada, a região à direita e acima de z + …ca excluída por
impossibilidade, i.e., apenas pode conter soluções não admissíveis, enquanto que a região
à esquerda e abaixo de z + …ca excluída por apenas poder conter soluções dominadas por
z+:
Cada uma daquelas regiões gera um problema que pode ser formulado conforme (5),
com z1min = z1+ ¡ ¢z1 e z2min = z2+ , no primeiro caso e com z1min = z1+ e z2min = z2+ ¡ ¢z2 ,
no segundo caso. A determinação das soluções não dominadas no raio de vizinhança
pode, portanto, efectuar-se com recurso aos procedimentos utilizados na resolução de (5)
(ver secção 2.2.1). Esta resolução, que envolve a determinação das soluções suportadas
adjacentes à região, tem como vantagem garantir que as soluções obtidas são efectivamente
não dominadas globalmente.
22
Adicionalmente, devem excluir-se as soluções com valor superior a z1+ +¢z1 no critério
z1 ; ou com valor superior a z2+ + ¢z2 no critério z2 :
Contudo, sendo o objectivo desta opção facultar uma análise local relativamente à
solução z + é de esperar que o raio de vizinhança seja, em geral, bastante pequeno. Assim,
o processo de separação do cálculo de soluções suportadas e de não suportadas é mais
moroso do que o cálculo indiferenciado das soluções.
2.2.2.3
Determinação de soluções alternativas no espaço de decisão
Nesta opção interactiva permite-se que o AD proceda a uma análise a posteriori de uma
solução não dominada já obtida, no sentido de poder averiguar se, no espaço de decisão,
existe(m) alguma(s) solução(ões) que embora tenham os mesmos valores nos critérios
da solução seleccionada, têm composição diversa no espaço de decisão (designaremos
estas soluções por soluções alternativas). Esta análise é justi…cada pela possibilidade de
muitos aspectos relevantes na análise das soluções não estarem retratados nos critérios
explicitados, o conhecimento do espaço de decisão revela-se útil, permitindo ao AD reter
uma solução que embora equivalente no espaço dos critérios de…nidos é preferível tendo
em conta outras perspectivas de análise.
Nesta opção interactiva possibilita-se ao AD a visualização das imagens no espaço de
decisão de uma solução não dominada que considera interessante.
Consideremos z + = (z1+ ; z2+ ) uma solução não dominada no espaço dos critérios. Perante esta solução, o AD pretende conhecer todas as soluções alternativas no espaço de
decisão. Caso as soluções alternativas ainda não tenham sido obtidas em interacções anteriores (isto é, quando não se coloca a obrigatoriedade de obter todas as soluções no espaço
de decisão), empregamos o procedimento de resolução que se segue.
Podemos formular o problema dos óptimos alternativos como o problema de determinação de todas as soluções óptimas do problema (14) :
max z1 (x)
sujeito a :
z2 (x) ¸ z2+
x2X
(14)
Um modo de obter todas as soluções alternativas de (14) seria recorrer a um programa
de optimização de programação linear inteira e resolver iterativamente o problema, introduzindo em cada iteração uma restrição adicional relativa à cardinalidade da solução
obtida, até que o problema fosse impossível ou o valor de z1 (x) fosse inferior
a z1+ . Ou
©
ª
k
k
k
seja, representando por
a
solução
óptima
obtida
na
iteração
com
,
x
k
N
=
j
:
x
=
1
1
j
P
k
inclui-se a restrição
xj · jN1 j ¡ 1 de modo a determinar a solução óptima alternativa
j2N1k
seguinte.
23
No entanto, este procedimento requer a resolução de vários problemas desde o ínício,
o que o torna ine…ciente. Para resolver esta questão vamos construir um procedimento
de partição e avaliação sucessivas com aproveitamento da informação disponível em cada
momento.
Começamos por tentar …xar o valor de algumas variáveis, utilizando o procedimento
da secção 2.2.1.
O problema reduzido é depois resolvido com um procedimento de partição e avaliação
sucessivas.
Neste procedimento utilizamos duas condições de cardinalidade para o número de itens
incluídos nas soluções alternativas, são elas as condições de cardinalidade máxima e de
cardinalidade mínima, que descrevemos de seguida.
Notemos por z1+ e por z2+ os valores pretendidos para os critérios z1 e z2 respectivamente. O número mínimo de itens necessário para se obter esta solução pode ser determinado resolvendo o problema (15) abaixo. À condição correspondente àquela solução,
chamamos condição de cardinalidade mínima para z + :
hmin
i
( n
)
n
X
X
= min
xj :
cij xj ¸ zi+ ; 0 · xj · 1; j = 1; :::; n
j=1
(15)
j=1
Representemos por #min(zi ) o valor de hmin
arredondado por excesso, i.e., #min(zi ) =
i
min
dhi e.
Uma vez que as soluções pretendidas devem ter como imagem no espaço dos critérios,
+
z1 e z2+ , respectivamente, a condição de cardinalidade mínima traduz-se por:
n
X
xj ¸ max (#min(zi ))
i=1;2
j=1
(16)
A resolução do problema (15) pode fazer-se ordenando os itens segundo valores não
crescentes de cij e incluir os itens até que se atinja o valor pretendido. A ideia subjacente
é simples: incluir os itens de maior valor, até que se atinja zi+ :
A restrição de capacidade também permite impor uma condição de cardinalidade máxima. De facto, o número máximo de itens que pode ser colocado na mochila corresponde
ao valor de hmax arredondado por defeito:
hmax
( n
)
n
X
X
= max
xj :
wj xj · W; 0 · xj · 1; j = 1; :::; n
j=1
(17)
j=1
Por conseguinte, a condição de cardinalidade máxima traduz-se por:
n
X
xj · bhmax c
j=1
24
(18)
A solução óptima do problema (17) pode ser obtida ordenando os itens segundo valores
não decrescentes de wj e incluindo os itens até que se atinja a capacidade da mochila.
No procedimento de partição e avaliação sucessivas, e como é usual, distinguem-se as
operações de rami…cação, cálculo de limites e abandono.
O procedimento que apresentamos, parte da árvore binária correspondente à solução
associada a z + = (z1+ ; z2+ ). Representemos essa solução por x+ .
1. Rami…cação
A rami…cação da variável xk pertencente à árvore de partida faz-se do seguinte
+
modo: xk = 1 se x+
k = 0, ou xk = 0 se xk = 1.
A partir de um nodo que não pertence à árvore de partida são criadas duas rami…cações xk = 1 e xk = 0, onde k representa o nível da árvore de partida.
Esta operação gera dois novos nodos. Analisa-se, primeiramente, a rami…cação
xk = 1.
No entanto, em qualquer nodo, não se procede à rami…cação xk = 1 se wk >
k¡1
P
W¡
wj xj (o peso do item excede a capacidade remanescente).
j=1
A rami…cação xk = 0 também pode ser evitada, se:
² n ¡ max (# min(zi )) =
i=1;2
k¡1
P
j=1;xj =0
(1 ¡ xj )
² xk 2
= F (variáveis …xadas a zero ou a um).
Por outro lado, a rami…cação xk = 1 também pode ser evitada, se:
1.
²
k
P
j=1;xj =1
xj = bhmax c
= F (variáveis …xadas a zero ou a um)
² xk 2
2. Cálculo de limites
Suponhamos que estamos a analisar uma rami…cação da variável xk , k 2 F . Neste
nodo veri…ca-se que o acréscimo alcançável no valor do i ¡ e¶simo critério é limitado
por:
(
n
n
n
k
P
P
P
P
cij + max
cij xj :
wj xj · W ¡ wj xj
¢zik = cik xk +
j=k+1;j2N1
j=k+1;j2F
25
j=k+1;j2F
j=1
¡
n
X
j=k+1;j2N1
wj ; 0 · xj · 1; j = k + 1; :::; n; j 2 F
)
(19)
A resolução do problema (19) pode ser efectuada por aplicação da heurística gulosa,
que consiste em preencher a capacidade remanescente, com os itens com maior valor
relativo. Um limite mais apertado para o acréscimo do valor do i ¡ e¶simo critério
pode ser conseguido por utilização do limite U2 .
3. Abandono
Um nodo, correspondente à rami…cação da variável xk , é abandonado se se veri…car pelo menos uma das seguintes condições:
k¡1
P i
a) ¢zik +
cj xj < zj+ ; j = 1; 2 (limite para os critérios inferior z + ) ;
j=1
b) nodo terminal.
Quando um nodo é abandonado, analisa-se o último nodo criado e não abandonado. Se
o nodo abandonado for terminal, a solução é colocada numa lista das soluções alternativas,
X a , vazia no início do procedimento, se a sua imagem no espaço dos critérios for z + =
(z1+ ; z2+ ). Quando todos os nodos forem abandonados o procedimento termina e as soluções
em X a são alternativas de x+ .
2.2.3
Análise decorrente da de…nição de um per…l de solução
Nesta opção interactiva o AD selecciona uma região no espaço dos critérios onde pretende
conhecer uma solução não dominada. Esta especi…cação de…ne um per…l de solução, uma
vez que se concretizam os valores possíveis para os critérios de…nidos.
Então, o AD especi…ca:
² a região de interesse, por indicação dos níveis mínimos para os critérios ou por
selecção de duas soluções não dominadas previamente obtidas;
² os ponderadores dos critérios, na função soma ponderada que pretende maximizar
na região de interesse. Estes ponderadores têm aqui a função exclusiva de privilegiar
a obtenção de uma solução mais próxima de um dado critério.
O AD pretende obter uma solução, pertencente à região, que maximiza a função
especi…cada. O problema matemático subjacente a resolver é o seguinte:
26
¤
frb
= max f (x) = ¸1 c1 x + ¸2 c2 x
sujeito a :
wx · W
c1 x ¸ z1min
c2 x ¸ z2min
x 2 f0; 1gn
(20)
Com a introdução das restrições adicionais o problema perde a estrutura do problema da mochila monocritério, o que inviabiliza, a priori, a sua resolução pelos métodos
conhecidos.
Vejamos um procedimento possível para a sua resolução.
Começamos por resolver o problema bicritério soma ponderada sem as restrições adicionais (problema 3). A solução óptima deste problema, x¤ , é obtida através da aplicação
do algoritmo MT1 de Martello e Toth (1990). Duas situações distintas podem ocorrer em
relação à solução óptima, x¤ :
1. Esta solução veri…ca as restrições adicionais c1 x¤ ¸ z1min e c2 x¤ ¸ z2min : Neste caso,
o procedimento termina.
2. Esta solução não veri…ca pelo menos uma das restrições adicionais. Neste caso, tem
início um processo que se divide em quatro fases:
Fase 1: obtenção de um limite superior para f (x) na região de interesse;
Fase 2: obtenção de um limite inferior para f (x) na região de interesse;
Fase 3: redução da dimensão do problema;
Fase 4: identi…cação da solução óptima.
Vejamos, em detalhe, cada uma destas quatro fases.
2.2.3.1
Obtenção de um limite superior para f (x) numa região de interesse
de…nida
Nesta fase, pretendemos obter um limite superior para o valor óptimo da função objectivo do problema (20).
Este limite será posteriormente utilizado nas fases 3 e 4. Vamos considerá-lo como o
valor óptimo da função objectivo do problema linear:
¤
= max f (x) = ¸1 c1 x + ¸2 c2 x
frc
sujeito a :
wx · W
c1 x ¸ z1min
c2 x ¸ z2min
x 2 [0; 1]n
27
(21)
A solução óptima de (21) pode determinar-se indirectamente atendendo ao facto de
que, sem as restrições adicionais, estamos perante a versão relaxada do problema da
mochila monocritério.
Para tal, começamos por resolver o problema (21) sem estas duas restrições, ou seja,
o problema (22):
fr¤ = max f (x) = ¸1 c1 x + ¸2 c2 x
sujeito a :
wx · W
x 2 [0; 1]n
(22)
O problema (22) tem uma estrutura particular o que permite determinar a solução
óptima de um modo elegante, conforme demonstrou Dantzig em 1957. A solução óptima
de (22) coincide com a solução obtida por aplicação da heurística gulosa, que consiste em
² ordenar os itens segundo valores relativos (
seguidamente;
¸1 c1j +¸2 c2j
wj
; j = 1; :::; n) não crescentes e,
² esgotar a capacidade da mochila, W; com a inclusão dos itens segundo a ordenação
de…nida anteriormente.
Com os itens ordenados segundo valores relativos não crescentes, o primeiro item que
não pode ser integralmente incluído designa-se por item crítico e representa-se por f , isto
é:
(
k
X
wj > W
f = min k :
Por conseguinte, a solução óptima, x¤
seguinte composição:
8
1
>
>
fP
¡1
<
W¡
wk
¤
xj =
k=1
>
wj
>
:
0
j=1
)
(23)
¡
¢
= x¤1 ; :::; x¤j ; :::; x¤n , do problema (22) tem a
se j = 1; :::; f ¡ 1
se j = f
se j = f + 1; :::; n
(24)
Assim, consideremos x¤ a solução óptima de (22). O valor de fr¤ constitui um limite
superior para f (x). Contudo, quando z(x¤ ) = (z1 (x¤ ) ; z2 (x¤ )) não respeita as restrições
adicionais e, de facto, tal é possível, o valor máximo desta função na região é sempre
inferior ou igual ao o valor de fr¤ , i.e., fr¤ ¸ f (x); x 2 X ¸ . Como consequência, teremos
uma menor e…cácia nas fases 3 e 4, uma vez que este valor é utilizado para reduzir a
dimensão do problema.
28
Importa, pois, determinar o valor máximo de f(x) na região de interesse. Para tal,
observemos que, se a solução óptima de um problema não veri…ca determinada restrição,
então, quando a restrição é incluída no problema, encontra-se activa na solução óptima
do mesmo.
Assim, a determinação da solução que maximiza f (x), na região, pode fazer-se através
da identi…cação da sucessão de pontos extremos adjacentes e…cientes. Esta sucessão iniciase em x¤ e termina quando se obtiver o primeiro ponto e…ciente na região ou, caso não
exista, o primeiro fora dela. A localização de z(x¤ ) indica o sentido de procura de pontos
e…cientes adjacentes. Sendo zi (x¤ ) < zimin e x+ um ponto e…ciente adjacente a x¤ com
zi (x+ ) ¸ zimin então o processo de determinação de pontos extremos e…cientes termina,
caso contrário, determinamos um novo ponto extremo e…ciente.
Consideremos os dois últimos pontos adjacentes determinados. A função f(x) atinge
o seu valor máximo no primeiro ponto de intersecção do segmento de recta que une esses
dois pontos com a recta de equação z1 = z1min ou z2 = z2min (ver Figura 7).
z2
z2
•
z
min
2
•2
•
•
•
•
z1min
z
•1
•2
•
•
min
2
•
z1
z1min
•1
z1
Figura 7: Maximização de f(x)
De modo a determinarmos a sucessão de pontos extremos e…cientes adjacentes utilizamos o método simplex bicritério, tendo por base o problema (25).
max z1 (x) = c1 x
max z2 (x) = c2 x
sujeito a :
wx · W
x 2 [0; 1]n
(25)
No entanto, observemos que o problema (25) é composto por n+1 restrições (excluindo
as de não negatividade), em que n das quais são referentes à limitação das variáveis. Considerar explicitamente estas restrições releva-se muito pouco e…ciente e não tira partido
da sua estrutura particular. Neste sentido, utilizaremos o método simplex com variáveis
limitadas. Neste método, o valor de todas as variáveis, à excepção da variável básica,
29
está …xado no seu limite superior (um) ou no seu limite inferior (zero). O quadro simplex
bicritério, que se apresenta a seguir, tem apenas uma restrição (restrição de capacidade).
Relativamente ao quadro simplex habitual, são introduzidas as seguintes alterações:
1. uma linha com os coe…cientes das variáveis em ambos os objectivos;
2. para cada variável básica apresenta-se o seu coe…ciente em ambos os objectivos;
3. uma linha de preços reduzidos associada a cada um dos objectivos, que é actualizada
como habitualmente.
c1
c2
c1b c2b xb
c1f c2f xf
c1j ¡ zj1
c2j ¡ zj2
c11
c21
x1
w1 =wf
c11 ¡ w1 =wf c1f
c21 ¡ w1 =wf c2f
:::
c1j
:::
c2j
:::
xj
:::
wj =wf
::: c1j ¡ wj =wf c1f
::: c2j ¡ wj =wf c2f
:::
c1n
:::
c2n
:::
xn
:::
wn =wf
::: c1n ¡ wn =wf c1f
::: c2n ¡ wn =wf c2f
0
0
s
1=wf
¡1=wf c1f
¡1=wf c2f
b
.
No quadro acima:
² xf é a variável fraccionária que também denominamos por variável básica (xf = xb );
² a variável xf constitui a base corrente, designação utilizada quando as restrições de
limitação das variáveis são incluídas implicitamente;
² s é a variável desvio da restrição de capacidade.
As condições de optimalidade do problema de maximização do critério zi , correspondem a:
8 i
i
>
< cj ¡ zj ¸ 0 se xj = 1;
i
cj ¡ zji · 0 se xj = 0;
:
i
>
: ¡ cf · 0 (o que é sempre verdade com ci ¸ 0 e w > 0):
f
f
wf
No quadro simplex anterior, as operações usuais (partindo da solução óptima) são as
seguintes: (1) identi…cação da variável básica que sai da base; (2) identi…cação da variável
não básica e…ciente, que entra na base; (3) actualização do valor da variável que entra
na base; e (4) de…nição do valor da variável que deixa a base. As operações (3) e (4)
efectuam-se de modo distinto do que é feito habitualmente, devido à inclusão implícita
das restrições de limitação das variáveis (ver Bazaraa et al., 1990 ou Nash e Sofer, 1996).
No Anexo (A) descrevemos o método simplex com variáveis limitadas e derivamos as
operações acima para o caso especí…co do problema da mochila, resultados que sintetizamos a seguir.
1. Variável que sai da base: A variável xf é a única candidata a sair da base corrente.
30
2. Variável que entra na base: Analisando a linha cij ¡ zji considera-se candidata a
entrar na base a variável xj que satisfaz as condições de optimalidade para uma
função combinação linear convexa dos objectivos3 e em que a alteração do seu valor
conduz à melhoria do critério zi (cij ¡ zji < 0 se xj = 1 ou cij ¡ zji > 0 se xj = 0).
De…nição 3 (Solução básica e…ciente) Uma solução x¤ diz-se uma solução básica
e…ciente para (25) sse for uma solução óptima de
max f¸1 z1 (x) + ¸2 z2 (x) : wx · w; 0 · x · 1g, com ¸1 ; ¸2 > 0 e ¸1 + ¸2 = 1:
De…nição 4 (Base e…ciente) B é uma base e…ciente sse corresponder à solução
óptima do problema max f¸1 z1 (x) + ¸2 z2 (x) : wx · w; 0 · x · 1g, com ¸1 ; ¸2 > 0
e ¸1 + ¸2 = 1.
De…nição 5 (Variável não básica e…ciente) Considere-se B uma base e…ciente
do problema (25). Então, xj ; uma variável não básica, diz-se e…ciente em relação a
B sse existir ¸1 ; ¸2 > 0 e ¸1 + ¸2 = 1, tal que
² ¸1 (c1k ¡ zk1 ) + ¸2 (c2k ¡ zk2 ) ¸ 0 se xk = 1(k 2 f1; :::; ngnff g);
² ¸1 (c1k ¡ zk1 ) + ¸2 (c2k ¡ zk2 ) · 0 se xk = 0(k 2 f1; :::; ngnff g);
² ¸1 (¡c1f =wf ) + ¸2 (¡c2f =wf ) · 0 (o que é sempre veri…cado);e,
² ¸1 (c1j ¡ zj1 ) + ¸2 (c2j ¡ zj2 ) = 0:
Teorema 2 (Base e…ciente adjacente) Se B é uma base e…ciente e xj uma variável não básica e…ciente, então a entrada na base de xj conduz a uma base e…ciente
adjacente a B.
Assim, a variável candidata a entrar na base é a que veri…ca as condições da De…nição
5 e que conduz à melhoria do valor do critério zi , i.e., cij ¡ zji < 0 se xj = 1; ou
cij ¡ zji > 0 se xj = 0: O Teorema 2 garante a obtenção de uma solução e…ciente
adjacente. Contudo, a variável xf pode permanecer básica se a variável xj transitar
do seu limite superior para o inferior ou vice-versa. Neste caso, xj permanece não
básica.
3. Actualização do valor da variável xj (candidata a pertencer à base): Vamos distinguir as seguintes situações:
² Se xj = 0; então o novo valor de xj corresponde a
3
A função ¸1 z1 (x) + ¸2 z2 (x) diz-se combinação linear convexa de z1 (x) e de z2 (x) sse ¸1 + ¸2 = 1 e
¸1 ; ¸2 ¸ 0:
31
½
¾
wf
min xf ; 1
wj
(26)
o
n
w
Se min xf wfj ; 1 = 1; então xj permanece não básica, agora no seu limite superior.
Caso contrário, xj passa a substituir xf na base.
² Se xj = 1; então o novo valor de xj corresponde a
¾
½
wf
1 ¡ min (1 ¡ xf ) ; 1
wj
(27)
n
o
wf
Se min (1 ¡ xf ) wj ; 1 = 1, então xj permanece não básica, mas desta vez no seu
limite inferior. Caso contrário, xj passa a substituir xf na base.
4. Actualização do valor da variável xf (candidata a sair da base): Se xf passa a ser
uma variável não básica, o seu valor é determinado atendendo à de…nição do valor
da variável que passa a pertencer à base. Isto é,
8
n
o
< Se xj = 0 e min xf wf ; 1 = xf wf , então xf = 0;
wj
nwj
o
.
w
: Se xj = 1 e 1 ¡ min (1 ¡ xf ) f ; 1 = 1 ¡ (1 ¡ xf ) wf , então xf = 1
wj
wj
No …nal do processo de determinação dos pontos e…cientes adjacentes, designemos por
x e x2 as duas últimas soluções obtidas e em que, sem perda de generalidade, admitimos
z1 (x1 ) < z1 (x2 ). O limite superior de f (x) é, então, dado por ¸1 z1 (x) + ¸2 z2 (x), com z1 (x)
e z2 (x) determinados pela resolução do sistema
½
®1 z1 (x) + ®2 z2 (x) = ®3
zi (x)
= zimin
1
onde
8
< ®1 = z2 (x1 ) ¡ z2 (x2 )
® = z1 (x2 ) ¡ z1 (x1 )
:
: 2
1
2
1
2
®3 = z2 (x )z1 (x ) ¡ z1 (x )z2 (x )
Exemplo 3 Consideremos o problema bicritério do Exemplo (1) onde introduzimos as restrições adicionais z1 (x) ¸ 300 e z2 (x) ¸ 350:
1. Suponhamos que o AD de…ne a seguinte função agregada, que pretende maximizar: f(x) =
0; 5z1 (x) + 0; 5z2 (x).
32
(a) Começamos por resolver o problema sem as restrições adicionais z1 (x) ¸ 300 e
z2 (x) ¸ 350:
max f(x) = 45; 5x1 + 31; 5x2 + 32x3 + 80; 5x4 + 39x5 + 65; 5x6 + 48; 5x7 + 78x8 +
44; 5x9 + 30; 5x10
sujeito a:
58x1 + 84x2 + 66x3 + 32x4 + 77x5 + 73x6 + 60x7 + 12x8 + 12x9 + 68x10 · 271
xj 2 f0; 1g; j = 1; :::; 10:
Aplicando o algoritmo MT1, obtemos como solução óptima x¤ = (1001011110),
com a imagem z(x¤ ) = (392; 333) no espaço dos critérios, que não pertence à região
seleccionada.
(b) Fase 1: Obtenção de um limite superior para f (x) na região de interesse
fr¤ = max f(x) = 45; 5x1 + 31; 5x2 + 32x3 + 80; 5x4 + 39x5 + 65; 5x6 + 48; 5x7 + 78x8 +
44; 5x9 + 30; 5x10
sujeito a:
58x1 + 84x2 + 66x3 + 32x4 + 77x5 + 73x6 + 60x7 + 12x8 + 12x9 + 68x10 · 271
xj 2 [0; 1]; j = 1; :::; 10:
Na Figura 8 mostramos o espaço dos objectivos deste problema.
z2
(336.79, 371.79) • • (346.41, 370.55)
• (394.12, 352.41)
350
• (406.96, 342.35)
•(0,0)
z1
300
Figura 8: Espaço dos objectivos do problema relaxado
(c) Ordenando os itens segundo valores relativos
µ
cj
wj
¶
não crescentes e incluindo-os,
nesta ordem, até que se esgote a capacidade da mochila, obtemos a solução óptima x¤ = (10010; 3111110), que no espaço dos critérios corresponde a z(x¤ ) =
(406; 96; 342; 35). Com esta solução, obtemos fr¤ = f(x¤ ) = 374; 657.
33
i. Reconstruindo o quadro simplex bicritério referido atrás, temos:
b
Solu ção x
c
c
1
2
1
0
0
1
0
1
1
1
1
0
0
68
26
32
70
48
75
42
89
23
37
32
91
30
56
55
67
48
6
0
41
55
0
1
cb
2
cb
xb
x1
x2
x3
x4
x5
x6
x7
x8
x9
x 10
s
b
48
30
x5
58/77
84/77
66/77
32/77
1
73 /77
60/77
12/77
12/77
68/77
1/77
0.3116
1 1
c j -z j
31,8
-26,4
-9,1
50,1
0
29,5
4,6
81,5
40,5
-36,4
-0,6
2 2
c j -z j
0,4
4,3
6,3
78,5
0
27,6
31,6
62,3
36,3
28,5
-0,4
.
Neste quadro o valor da variável x5 foi obtido do seguinte modo: x5 = (W ¡
wb
x)=w5 = (271 ¡ 247)=77 = 0; 3116. Uma vez que este valor é inferior ao
mínimo estabelecido, o valor de z2 (x) deve aumentar. De modo a identi…carmos a variável não básica e…ciente candidata a entrar na base, determinamos
o intervalo de valores dos ponderadores ¸1 e ¸2 que permite obter a solução.
Este intervalo é de…nido por resolução do sistema de inequações que garante a
optimalidade da solução encontrada:
¸0
31; 8¸1 + 0; 4¸2
¡26; 4¸1 + 4; 3¸2
·0
¡9; 1¸1 + 6; 3¸2
·0
¸0
50; 1¸1 + 78; 5¸2
¸0
29; 5¸1 + 27; 6¸2
¸0
4; 6¸1 + 31; 6¸2
¸0
81; 5¸1 + 62; 3¸2
¸0
40; 5¸1 + 36; 3¸2
¡36; 4¸1 + 28; 5¸2
¡0; 6¸1 ¡ 0; 4¸2
¸0
·0
Este sistema de inequações é coerente se ¸1 2 [0; 439264; 1]: Notemos então
que x10 é a variável que satisfaz a de…nição de variável não básica e…ciente
(ver De…nição (5)) e que permite, por activação, a melhoria do valor de z2 :
1 ) + (1 ¡ 0; 439264)(c2 ¡ z 2 ) = 0 e (c2 ¡ z 2 ) > 0: Assim, a
0; 439264(c110 ¡ z10
10
10
10
10
variável x10 é candidata a entrar na base em substituição de x5 .
ii. Efectuando a mudança de base, obtemos o quadro seguinte:
b
Solu ção x
c
c
.
1
2
1
0
0
1
0
1
1
1
1
0
0
68
26
32
70
48
75
42
89
23
37
32
91
30
56
55
67
48
6
0
41
55
0
1
cb
2
cb
xb
x1
x2
x3
x4
x5
x6
x7
x8
x9
x 10
s
6
55
x 10
58/68
84/68
32/68
7 7/68
77/68
73/68
60/68
12/68
12/68
1
1/68
1 1
c j -z j
2 2
c j -z j
62,9
18,6
26,2
67,2
41,2
68,6
36,7
87,9
46 ,9
0
-0,08
-23,9
-30,9
-21,4
65,1
-32,3
-0,3
6,5
57,3
31 ,3
0
-0,81
O valor da variável x10 corresponde a 0; 3116
34
¡ 77 ¢
68
= 0; 3529. Logo, x5 = 0.
0.3529
A solução (394; 12; 352; 41) já pertence à região seleccionada. Sendo assim,
paramos o procedimento de determinação de novos pontos extremos adjacentes.
iii. Os últimos dois pontos extremos adjacentes, a considerar seguidamente, são
(406; 96; 342; 35) e (394; 12; 352; 41), sendo a equação da recta que os une, z2 =
¡0; 7835z1 + 661; 2.
(d) Como na solução óptima, com as restrições adicionais, a restrição z2 (x) ¸ 350 está
activa, i.e. (z2 (x) = 350), podemos obter o valor máximo para f(x) na região, por
resolução
do sistema:
½
½
z2 = ¡0; 7835z1 + 661; 2
z1 = 397; 19
,
z2 = 350
z2 = 350
Obtemos então 0; 5 £ 397; 19 + 0; 5 £ 350 = 373; 595, como um limite superior para
f(x) na região.
z2
• (394.12, 352.41)
(300, 350)
f(x)=374.7
f(x)=373.6
z1
• (406.96, 342.35)
Figura 9: Valor máximo para f(x) na região de interesse
35
2.2.3.2
Obtenção de um limite inferior para f (x) na região de interesse de…nida
Nesta fase, pretendemos obter um limite inferior para a função f (x), na região de interesse. Este limite inferior é de…nido a partir de uma solução admissível para o problema,
que devido ao modo de de…nição da região, nunca será inferior a ¸1 z1min + ¸2 z2min . Assim,
é objectivo desta fase procurar uma ”boa solução” inteira admissível para o problema
(22). Reparemos que uma tal solução admissível pode ser facilmente obtida a partir de
b esta solução. Este é um arredondamento admissível
x¤ , fazendo xf = 0: Designemos por x
que, contudo, pode não satisfazer as restrições adicionais c1 x ¸ z1min e c2 x ¸ z2min .
Deste arredondamento ocorre uma das seguintes situações, que se ilustram na Figura
10:
1. x
x) ¸ z1min ;
b não pertence à região e z1 (b
2. x
b não pertence à região e z2 (b
x) ¸ z2min ;
3. x
b não pertence à região e z1 (b
x) < z1min ; z2 (b
x) < z2min ;
4. x
b pertence à região.
z2
• 2
•4
z
min
2
•1
•3
z1min
z1
Figura 10: Convergência para a região seleccionada
Para obtermos uma solução inteira na região seleccionada, se tal existir, o valor do
critério z2 deve aumentar, na situação 1, enquanto que na situação 2, deve ser o valor do
critério z1 a aumentar.
Na situação 3, os valores de ambos os critérios devem aumentar. Por …m, na situação
4, apenas se tem que explorar a região seleccionada, a partir de x
b.
Representemos por zi , o critério cujo valor deve aumentar (nas situações 3 e 4, escolhese o critério que mais se afasta do valor mínimo de referência) e aplicamos o procedimento heurístico seguinte, que susbtitui itens incluídos por itens excluídos na solução
arredondada, melhorando o valor do critério pretendido, e mantendo a admissibilidade da
solução.
Begin
Inicialização: Construção dos conjuntos N0 = fi :xbi = 0 g, N1 = fi :xbi = 1 g ordenados
segundo valores não crescentes do critério zi : Substituição dos itens de N1 por itens de
36
N0 , de acordo com o seguinte procedimento.
j = 1; k = 1;
P 1
P 2
ci ; z2 =
ci ;
z1 =
i2N1
¡
w =W¡
P
{ co n stru ir va lo re s in ic ia is}
i2N1
wi ; f min = 0;
i2N1
F imN 0 á false;
Repeat
Begin
If k > jN1 j then
Begin
j á j + 1;
If j > jN0 j then F imN 0 á true
else k á 1;
End
If F imN0 = f alse then
Begin
¡
i
> cikN1 and wjN0 · w + wkN1 then
If cjN
0
Begin
bkN1 = 0;
x
bjN0 = 1, x
N1 á N1 nfkg;
z1 á z1 + c1jN0 ¡ c1kN1 ;
z2 á z2 + c2jN0 ¡ c2kN1 ;
w á w + wkN1 ¡ wjN0 ;
If z1 ¸ z1min and z2 · z2min then
x) > f min then f min á f (b
x) ;
If f(b
Else j á j + 1;
End
Else k á k + 1 ;
End
End
Until FimN0=true;
End
{ve ri… ca r s e o valor d o crité rio
zi
m elh ora }
{ a ctu a liz a r a s o lu ç ã o inte ira }
N1 }
z1 }
{ actu aliz ar o va lo r d e z2 }
{ retirar o k -ésim o elem ento d e
{a ctu aliza r o valor d e
{ac tu a lizar a cap a cid ad e res id u a l}
{ ve ri… ca se a so lu çã o p erten ce à re g iã o }
{m elh o rar o valor d e
f(x)e a ctu a liz a va lo r d e f min }
Procedimento de obtenção de solução na região de interesse
No …nal da aplicação deste procedimento pode acontecer que nenhuma solução tenha
sido encontrada, devido à natureza heurística ou à inexistência de uma solução inteira
admissível na região. Neste caso, consideramos ¸1 z1min + ¸2 z2min como valor mínimo teórico
para f (x) na região de interesse.
Exemplo 4
(Continuação do Exemplo 3) Fase 2: Obtenção de um limite inferior para
f (x) na região de interesse.
Consideremos a solução não inteira obtida no …nal da fase 1: x¤ =(100101111 (0; 3529)).
37
(a) Arredondando esta solução, obtemos xb = (10 0 1 0 1 1 1 1 0), que corresponde
ao ponto z(b
x) =(392; 333), não pertencente à região de…nida. Vamos aplicar o
procedimento heurístico, tendo em conta que os conjuntos N0 e N1 serão ordenados
segundo valores crescentes do critério z2 , uma vez que é este o critério cujo valor deve
aumentar de modo a obtermos uma solução admissível na região. N0 = f2; 3; 5; 10g,
N1 = f1; 4; 6; 7; 8; 9g.
i. Ordenando os conjuntos obtidos, temos N0 = f5; 3; 2; 10g, N1 = f4; 8; 6; 7; 9; 1g.
ii. Reconstruamos estes conjuntos, com informação relativa ao valor dos itens nos
critérios e o seu peso:
j
c1
c2
w
x10
6
55
68
N0
x2
26
37
84
x3
32
32
66
x5
48
30
77
k
c1
c2
w
x4
70
91
32
x8
89
67
12
N1
x6
75
56
73
x7
42
55
60
x9
48
41
12
x1
68 :
23
58
Passo2: j = 1, k = 1; 55 > 91 falso; 55 > 67 falso; 55 > 56 falso; 55 > 55 falso;
55 > 41verdade, 68 · 24 + 12 falso; 55 > 23 verdade, 68 · 24 + 58 verdade
x1 = 0 ; N1 = f4; 8; 6; 7; 9g; z1 = 330; z2 = 365; w = 14;
(k = 6); xc
10 = 1, c
min
z1 ¸ z1 = 300 verdade; z2 ¸ z2min = 350 verdade; f min = 0; 5 £ 330 + 0; 5 £
350 = 347; 5; j = 2;k = 1; 37 > 91 falso; 37 > 67 falso; 37 > 56 falso;37 > 55
falso; 37 > 41 falso; j = 3;k = 1;
32 > 91 falso; 32 > 67 falso; 32 > 56 falso; 32 > 55 falso; 32 > 41 falso;
j = 4;k = 1;
30 > 91 falso; 30 > 67 falso; 30 > 56 falso; 30 > 55 falso; 30 > 41 falso.
Solução obtida: (330; 365): Com esta solução, f (x) = 347; 5, que é um limite
inferior para f (x) na região de interesse de…nida.
2.2.3.3
Redução da dimensão do problema
Nesta fase reduzimos a dimensão do problema. Esta redução vai efectuar-se com base
na proposição abaixo, que relaciona os limites superior e inferior conhecidos, e os preços
reduzidos das variáveis não básicas.
Proposição 1 (Nemhauser e Wolsey, 1988) Se xj é uma variável não básica e está no
seu limite inferior (superior) na solução óptima, x¤ , do problema relaxado e f(x¤ ) +
cj · f (b
x) (f (x¤ ) ¡ cj · f(b
x)), então existe uma solução óptima para o problema inteiro
correspondente, com xj no seu limite inferior (superior).
Em resumo, temos que:
a) se x¤j = 0 e f(x¤ ) + cj · f(b
x), então xj pode ser de…nitivamente …xada a zero;
38
b) se x¤j = 1 e f (x¤ ) ¡ cj · f(b
x), então xj pode ser de…nitivamente …xada a um.
Vejamos como obter os preços reduzidos.
Com base na resolução do problema (21) e caso a sua solução óptima tenha imagem
na região seleccionada, o preço reduzido de cada uma das variáveis não básicas (j =
c
1; :::; f ¡ 1; f + 1; :::; n) corresponde a cj = cj ¡ wj wff ; j = 1; :::; f ¡ 1; f + 1; :::; n, o que
não é mais do que a diferença entre o valor do item cj e a sua valorização segundo o item
c
fraccionário: wj wff .
Quando a imagem de x¤ não pertence à região, o cálculo dos preços reduzidos requer
o conhecimento da base associada à solução óptima.
Notemos que, na sucessão de pontos extremos e…cientes adjacentes,
e considerando
¡
¢
¤
min
os dois últimos pontos determinados, a restrição zi (x) ¸ zi
zi (x ) ¡ si = zimin passa
de uma situação de não satisfação (si < 0), para uma situação de satisfação (si ¸ 0).
Designemos por xf1 e por xf2 as soluções, no espaço de decisão, correspondentes aos dois
últimos pontos determinados e ainda, por B1 (xf1 ) e B2 (xf2 ) as bases correntes associadas
às soluções xf1 e xf2 , respectivamente.
Se considerarmos o sistema inicial com a inclusão desta restrição, veri…camos que
aquelas bases são compostas por B1 (xf1 ; ¡si ) e B2 (xf2 ; si ).
Por conseguinte, a base óptima adjacente, do problema com as restrições adicionais,
substituirá, na base B2 , si pelo item xf1 , obtendo-se B3 (xf1 ; xf2 ).
z2
B2 (xf2, s2) •
c 2 x − s 2 = z 2min
z 2min
B3 (xf1, xf2)
•B1 (xf1, -s2)
f(x)
z1
z1min
Figura 11: Mudança de base
Conhecida a base B3 , os preços reduzidos são determinados como habitualmente, i.e.,
cj = cj ¡
cB3 B3¡1
µ
wj
cij
¶
(28)
Uma vez determinados os preços reduzidos, podemos aplicar a proposição acima e
…xar o valor de algumas variáveis.
39
Exemplo 5
(Continuação do Exemplo 3) Fase 3: Redução da dimensão do problema.
Comecemos por determinar os preços reduzidos.
Recordemos que (397; 19; 350) é o ponto óptimo do problema relaxado (Fase 2). Neste
ponto, x10 e x5 são as variáveis básicas. Logo, temos:
¶
µ
¶
µ ¡6
77
68 77
¡1
439
2195
.
e B3 =
B3 =
¡68
11
55 30
439
2195
(a) Os preços reduzidos, para as variáveis não básicas, de acordo com (28), são:
¡
c1
= 45; 5 ¡
c2
c3
c4
c6
c7
c8
c10
= ¡10; 455
= ¡0; 559
= 75; 151
= 32; 336
= 22; 483
= 80; 536
= 43; 445
30; 5; 39
¢
µ
¡6
439
11
439
77
2195
¡68
2195
¶µ
58
23
¶
= 16; 179
.
(b) Utilizando os preços reduzidos obtidos, o limite superior (f(x) · 373; 595) e inferior
(f (x) ¸ 347; 5), podemos, então, com base na proposição acima, …xar o valor de
todas as variáveis com preço reduzido em módulo, superior à diferença entre os dois
limites (373; 595¡347; 5 = 26; 095). Assim, …xamos x4 = 1; x6 = 1; x8 = 1; x9 = 1.
(c) O problema original, após redução, é constituído por apenas 6 variáveis e corresponde
a:
max z1 = 282 + 68x1 + 26x2 + 32x3 + 48x5 + 42x7 + 6x10
max z2 = 255 + 23x1 + 37x2 + 32x3 + 0x5 + 55x7 + 55x10
sujeito a :
58x1 + 84x2 + 66x3 + 77x5 + 60x7 + 68x10 · 142
xi 2 f0; 1g; i = 1; 2; 3; 5; 7; 10:
2.2.3.4
Identi…cação da solução óptima
Nesta fase, determinamos a solução óptima do problema (20) depois de reduzido. Utilizamos um procedimento de partição e avaliação sucessivas para resolver o problema
reduzido da fase 3, ordenando os itens segundo valores relativos não crescentes, em relação a f (x). No …nal deste processo, será(ão) obtida(s) a(s) solução(ões) não dominada(s)
(caso existam) que maximizam f (x) na região de…nida.
O procedimento de partição e avaliação sucessivas é de…nido da seguinte forma:
1. Rami…cação
Consideremos a variável xk , cujo valor ainda não foi …xado. Seguimos a estratégia
de analisar primeiramente a rami…cação xk = 1.
40
Note-se que não se procede à rami…cação xk = 1 se wk > W ¡
item excede a capacidade remanescente).
k¡1
P
wj xj (o peso do
j=1
Também, não se procede à rami…cação xk = 0, se o nodo correspondente, for terminal e xk = 1 conduzir a uma solução admissível.
2. Cálculo de limite
Suponhamos que estamos a analisar uma rami…cação de xk . No nodo criado, veri…case que o acréscimo alcançável no valor do i-ésimo critério é limitado por:
( n
)
n
k
X
X
X
4zik = max
cij xj :
wj xj · W ¡
wj xj ; 0 · xj · 1; j = k + 1; :::; n
j=k+1
j=1
j=k+1
(29)
A resolução deste problema pode ser efectuada por aplicação da heurística gulosa.
Do mesmo modo, obtemos o acréscimo máximo para a função f (x):
4f k = max
(
n
X
cj xj :
j=k+1
n
X
)
k
X
wj xj · W ¡
wj xj ; 0 · xj · 1; j = k + 1; :::; n
j=1
j=k+1
(30)
Na resolução deste problema, determinamos os preços reduzidos, cj , das variáveis
livres não básicas, como anteriormente.
k
P
Se para alguma destas variáveis se veri…car jcj j > ( ci xi +4f k )¡f (b
x), então, o seu
i=1
valor é …xado e criam-se as rami…cações correspondentes ao valor …xado, passando-se
a analisar a variável que sucede a xk e que não está …xada.
Notemos que, devido à ordenação dos itens, o acréscimo máximo para a função f (x)
não se altera, até que se atinja o item crítico. Assim, podemos dispensar a sua
determinação enquanto k for inferior ao índice do item crítico.
3. Abandono
Um nodo, correspondente à rami…cação da variável xk , é abandonado se veri…car
pelo menos uma das seguintes condições:
a) Limite para o valor dos critérios, inferior ao limite mínimo especí…cado:
k
P
cij xj + 4zik < zimin , i = 1; 2 (limite para os critérios) ;
j=1
b) Limite para o valor de f (x), inferior ao seu melhor limite inferior conhecido:
41
k
P
cj xj + 4f k < f (b
x) , i = 1; 2 (limite para os critérios) ;
j=1
c) nodo terminal.
Estas condições serão substituídas por outras mais exigentes, que resultam da aplicação do limite U2 , na determinação de 4zik , i = 1; 2 e de 4f k . Esta substituição
não acarreta muitos cálculos adicionais e possibilita, potencialmente, o abandono
mais precoce de alguns nodos, impedindo que nodos não promissores sejam analisados. Assim, o acréscimo máximo para as funções envolvidas, passa a ser determinado
por:
fki ¡1
X
4zik =
cij xj + max
j=k+1
($
%)
(31)
% ¹
º)
cifk +1
cf ¡1
w
; cfk ¡ (wfk ¡ w) k
wfk +1
wfk ¡1
(32)
w
cif i +1
k
wfki +1
% $
; cif i ¡ (wfki ¡ wi )
k
cif i ¡1
k
wfki ¡1
e
4f k =
fk ¡1
X
cj xj + max
j=k+1
($
onde fki e fk representam, respectivamente, o item crítico dos subproblemas
(
4zik = max
n
X
cij xj :
j=k+1
)
n
X
k
X
wj xj · W ¡
wj xj ; 0 · xj · 1; j = k + 1; :::; n
n
X
)
k
X
wj xj · W ¡
wj xj ; 0 · xj · 1; j = k + 1; :::; n
j=1
j=k+1
(33)
e
4f k = max
wi = W ¡
w=W¡
Ã
Ã
(
n
X
cj xj :
j=k+1
k
P
wj xj +
j=1
k
P
wj xj +
j=1
j=1
j=k+1
fki ¡1
P
wj xj
j=k+1
fP
k ¡1
wj xj
j=k+1
(34)
!
!
;e
:
42
Neste cálculo, os itens encontram-se ordenados, sucessivamente, segundo valores
relativos não crescentes da função envolvida z1 (x), z2 (x) e f (x), respectivamente.
Quando um nodo é abandonado, analisa-se o último nodo criado e não abandonado.
Se o nodo abandonado for terminal e não veri…car a) e b), a solução é colocada numa
lista de soluções, X e , vazia no início do procedimento. As soluções dominadas são
eliminadas. Com a actualização de X e actualizamos também o limite inferior f (b
x).
Quando todos os nodos forem abandonados o procedimento termina e as soluções
em X e são as que maximizam f (x) na região seleccionada.
Exemplo 6
(Continuação do Exemplo 3) Fase 4: Identi…cação da solução óptima, uti-
lizando um procedimento de partição e avaliação sucessivas.
Ao problema reduzido, aplicamos agora o procedimento de partição e avaliação sucessivas.
Ordenando os itens cujo valor ainda não foi …xado, segundo valores relativos de f(x) não
crescentes, obtemos: x7 Â x1 Â x5 Â x3 Â x10 Â x2 .
(a) Começamos por construir os ramos x7 = 1 e x1 = 1. O limite para z2 (x) permite
abandonar o nodo associado a este ramo.
(b) Retrocedemos na árvore e rami…camos x1 = 0. Os limite calculados para z1 ; z2 e
f(x) não permitem abandonar o nodo criado.
(c) A próxima variável a ser rami…cada é x5 , onde fazemos x5 = 1. Mais uma vez, o
valor limite para z2 conduz ao abandono do nodo.
(d) Analisa-se a rami…cação x5 = 0. Calculamos os limites para as funções envolvidas,
que viabilizam a obtenção de um melhor valor para f(x) na região de…nida.
(e) Na rami…cação x3 = 1, o limite para a função z2 , conduz ao abandono do nodo
criado. Procedemos à análise da rami…cação x3 = 0. Os limites calculados não
impedem a rami…cação da variável x10 . Igual razão leva à rami…cação x2 = 0, já
que x2 = 1 não é admissível. O nodo é terminal, tendo-se obtido os valores 330
e 365 para os limites das funções f (x), z1 (x) e z2 (x), respectivamente. A solução
associada é colocada na lista X e .
(f) Retrocedendo na árvore, analisamos a rami…cação x10 = 0. Os valores limite para
f(x) e z2 (x) proíbem a análise das variáveis subsequentes. O nodo 11, correspondente
à rami…cação x7 = 0, é o último a ser analisado. O limite para z2 , conduz ao seu
abandono.
(g) Todos os nodos estão abandonados, pelo que o procedimento termina.
(h) X e contém as soluções e…cientes, que maximizam f (x) na região. Neste caso, a
solução em X e coincide com a solução obtida com a heurística da segunda fase.
43
(i) No quadro seguinte, encontra-se a informação relativa aos nodos gerados, e na Figura
12 encontra-se a exploração da
Nodo V alores observados
z1
z2
1
324
310
2
392
333
3
324
310
4
372
340
5
324
310
6
356
342
7
324
310
8
330
365
9
330
365
10
324
310
11
282
285
árvore binária correspondente ao procedimento.
Limites
Decis~
ao
f(x) z1
z2
–
403 371
NA
–
403 344
A
358 373 371
NA
358 373 342
A
.
355 357 371
NA
355 357 349
A
347 348 365
NA
347 330 365
NA
347 330 365
A
317 348 345
A
356 400 345
A
(j) Exempli…quemos o cálculo de alguns destes valores. Por exemplo, no nodo 3, o cálculo dos limites para z1 (x), z2 (x) e f(x) é o que se segue.
Capacidade residual: W ¡ (w8 + w9 + w4 + w6 + w7 + w1 + w5 ) = 271 ¡ 247 = 24.
Itens com valor não …xado: x3 ; x10 ; x2 .
Limite para z1 (x): A ordenação dos itens, de acordo com os valores relativos desta
 x2 ¦ x¥10 . x3 corresponde¦ª
função, é x3©¥
ao item crítico (w3 = 66 > 24),
0
4z18 = max 24 26
¡
¡
(66 24)) 1 = 7, logo lz18 = 392 + 7 = 399.
84 ; (32
Limite para z2 (x): A ordenação dos itens segundo valores relativos nesta função é
x10 ¡ x3 ¡ x2 . x10 é o item crítico (w10 = 68 > 24),
¦ ¥
¦ª
©¥
0
4z28 = max 24 32
¡
¡
;
(55
(68
24))
= 11 , logo lz28 = 333 + 11 = 344.
66
1
Limite para f (x): A ordenação dos itens segundo valores relativos nesta função é
. x3 é okitem crítico (w10 = 66o> 24),
x3 ¡ x10 ¡ x2nj
¦
¥
0
8
4f = max 24 30;5
= 10; 76, logo lf 8 = 362; 5 + 10; 76 =
68 ; (32 ¡ (66 ¡ 24)) 1
373; 26:
44
0
x8=1
0
x9=1
0
x4=1
0
x6=1
0
x7=1
x7=0
1
x1=1
11
x1=0
2
3
x5=1
x5=0
4
5
x3=1
x3=0
6
7
x10=0
x10=1
10
8
x2=0
9
Figura 12: Árvore binária
45
3
Utilização da abordagem interactiva proposta com
recurso a um SIAD
Nesta secção utilizamos a abordagem interactiva proposta na secção anterior incorporada
num sistema interactivo de apoio à decisão que desenvolvemos e implementámos em Delphi
4 da Borland. De referir que este SIAD é totalmente autónomo de outras aplicações ou
rotinas de programação linear e/ou inteira. O SIAD é aqui utilizado como instrumento
de apoio à decisão num problema da mochila bicritério, simulado, com 250 itens. Não
pertence ao âmbito deste texto a descrição de todas as funcionalidades do mesmo, pelo
que nos limitamos a apresentar o estritamente relacionado com as opções de interacção
concebidas.
Começamos por determinar os valores máximos de cada um dos critérios (Figura 13)
seleccionando a opção de determinação dos óptimos individuais (cf. secção 2.1.1).
Figura 13: Óptimos individuais
Com o objectivo de caracterizar a con…guração da fronteira não dominada, solicitamos a geração de um número máximo de 10 soluções não dominadas, preferencialmente
dispersas (cf. secção 2.1.2). As soluções obtidas podem ser visualizados na Figura 14.
Com base nas soluções obtidas pretendemos conhecer mais soluções numa região considerada de interesse, de…nida por soluções que possuam um valor não inferior a 9.520
unidades, no primeiro critério, e um valor não inferior a 8.200 unidades, no segundo
critério (cf. secção 2.2.1). Na Figura 15 constam as soluções que satisfazem os requisitos
46
Figura 14: Subconjunto de soluções suportadas
impostos.
As soluções (9057, 9661) e (9421, 9420) são utilizadas para de…nir uma região na qual
pretendemos conhecer, com maior detalhe, a con…guração da fronteira não dominada.
Com este objectivo, optamos por solicitar apenas soluções suportadas na região de…nida.
Foram obtidas 7 soluções, conforme ilustramos na Figura 16.
Consideramos agora interessante conhecer uma solução na região de…nida pelas soluções
(8683, 9824) e (9057, 9661)(cf. secção 2.2.3). Obtivemos a solução (8907, 9734), conforme
se visualiza na Figura 17.
A solução obtida é considerada interessante pelo que procedemos à inspecção de
soluções não dominadas numa vizinhança com raio de 1% relativamente aos valores dos
critérios (cf. secção 2.2.2.2). Foi obtido um conjunto considerável de soluções, que se
mostram na Figura 18.
Estas soluções foram analisadas sequencialmente considerando-se como uma potencial
solução de compromisso entre os critérios o ponto (8973, 9698). Averiguou-se ainda a possibilidade de existirem soluções alternativas para esta solução, que não existem conforme
se visualiza na Figura 19, pela presença de uma solução única.
Consideramos su…cientemente explorada a região de localização de soluções não dominadas e satisfatório o conhecimento das soluções possíveis para o problema, pelo que
damos por concluído o processo de interacção com o SIAD.
A utilização do SIAD permitiu obter, progressiva e interactivamente, possíveis soluções
de compromisso para o problema. Ao longo do processo de interacção, dirigiu-se o processo
47
Figura 15: Introdução de restrições por imposição de níveis mínimos nos critérios
Figura 16: Análise de uma região de interesse de…nida por selecção de soluções
48
Figura 17: Per…l de solução
Figura 18: Soluções não dominadas num raio de vizinhança
49
Figura 19: Soluções alternativas
de busca de soluções, circunscrevendo-o a regiões mais promissoras. O esforço computacional e cognitivo foi melhor aproveitado do que o necessário para analisar o conjunto
integral das soluções não dominadas do problema.
A título de curiosidade apresentamos o conjunto completo das soluções não dominadas
do problema, que é composto por 587 soluções, 39 suportadas e 548 não suportadas.
50
Figura 20: Conjunto de soluções não dominadas
4
Conclusão
Neste trabalho abordámos o problema da mochila bicritério numa perspectiva interactiva.
Esta abordagem estruturou-se segundo níveis de informação solicitados pelo AD: informação de nível global e informação de nível local. Em cada um destes níveis facultámos
diversas opções interactivas de modo a ‡exibilizar o processo de decisão.
Nas opções interactivas de informação de nível local, o AD de…ne uma subregião
que pretende analisar. Nesta região pode obter todas as soluções não dominadas ou
apenas aquela que optimiza uma função linear especí…ca. Em ambos os casos o problema
matemático subjacente passa a incluir duas restrições adicionais o que destrói a estrutura,
muito particular, do problema original. A resolução deste problema, não como um caso
genérico de programação inteira, ainda não tinha sido abordado na literatura.
No sentido de obtermos todas as soluções na região, adaptámos o método gerador de
Visée et al. (1998), e desenvolvemos um procedimento dividido em quatro fases para determinar a solução que maximiza uma certa função naquela região. O estudo do modo como
duas restrições adicionais podem ser integradas no problema da mochila, utilizando as
propriedades bem conhecidas do problema original, constituiu uma das questões centrais
deste trabalho.
As opções interactivas foram incorporadas num SIAD, desenvolvido em Delphi 4, totalmente autónomo de outras aplicações ou rotinas de programação linear e/ou inteira.
Inúmeros melhoramentos devem contudo ser considerados no futuro, nomeadamente ao
51
nível da sua arquitectura e da optimização de algumas rotinas de cálculo utilizadas. É
nosso objectivo desenvolver a aplicação, incorporando novos procedimentos de cálculo de
soluções não dominadas.
Como investigação futura apresentamos o estudo do problema com mais do que dois
critérios. Re…ra-se que esta pista não é inédita se a entendermos no âmbito de desenvolvimento de métodos geradores. Contudo, estamos particularmente interessados no caso
de aproximações interactivas. Também, importa alargar as opções interactivas, possibilitando a obtenção de soluções por minimização de uma distância a pontos de referência
especi…cados.
Habitualmente, o conjunto das soluções não dominadas é identi…cado por comparação das soluções obtidas, armazenadas numa única lista, retendo apenas as que são não
dominadas por outra solução. Se este modo de proceder é particularmente simples no
caso bicritério, a sua extensão requer a utilização de estruturas de dados mais complexas
e métodos mais e…cientes.
52
References
[1] Bazaraa, M., Jarvis, J., Sherali, H. (1992) Linear Programming and Network Flows,
2nd edition, John Wiley & Sons.
[2] Captivo, M., Clímaco, J., Figueira, J., Martins, E., Santos, J.L. (2003) ”Solving
Multiple Criteria 0-1 Knapsack Problems Using a Labeling Algorithm”, Computers
& Operations Research. (a aparecer)
[3] Ehrgott, M., Gandibleux, X. (2002) Multiobjective Combinatorial Optimization Theory, Methodology and Applications, in Multiple Criteria Optimization: State of
the art annotathed bibliographic surveys, Kluwer Academic Publishers.pp. 369-444.
[4] Ferreira, C., Santos, B., Captivo, M., Clímaco, J., Silva, Carlos C. (1996) ”Multiobjective Location of unwelcome or central facilities involving environmental aspects:
a prototype of a decision support system”, Belgium Journal of Operations Research,
Statistics and Computer Science, 36, pp. 159-172..
[5] Ferreira, C., Clímaco, J., Paixão, J. (1994) ”The location-covering problem: a bicriterion interactive approach”, Investigación Operativa, Vol. 4 No 2, pp. 119-140.
[6] Kwark, W., Lee, H., Lee, C. (1996) ”Capital Budgeting With Multiple Criteria and
Multiple Decision Makers”, Review of Quantitative Finance and Acounting, 7, pp.
97-112.
[7] Martello, S., Toth, P. (1990) Knapsack Problems - Algorithms and computer implementation, John Wiley & Sons, Inc.
[8] Nash, S., Sofer, A. (1996) Linear and Nonlinear Programming, Mcgraw-Hill International Editions.
[9] Nemhauser, G., Wolsey, L. (1988) Integer and Combinatorial Optimization, John
Wiley & Sons, Inc.
[10] Pissinger, D., Toth, P. (1998) Knapsak Problems in Handbook of Combinatorial
Optimization, Du, D-Z., Pardalos, P. (Eds), Vol 1, Kluwer Academic Publishers.
[11] Rosenblatt, M., Sinnuany-Stern, Z. (1989) ”Generating the Discrete E¢ciente Frontier to the Capital Budgeting Problem”, Operations Research, vol. 37, N.o 3, pp.384394.
[12] Roy, B. (1996) Multicriteria Methodology for Decision Aiding, Kluwer Academic Publishers.
[13] Steuer, R. (1986) Multiple Criteria Optimization, Theory, Computation and Application, John Wiley & Son, Inc.
53
[14] Teng, J., Tzeng G. (1996) ”A Multiobjective Programming Approach for Selecting Non-independent Transportation Investement Alternatives”, Transportation Research, B. Vol. 30, N.o 4, pp. 291-307.
[15] Visée, M., Teghem, J., Ulungu, E.L. (1998) ”Two-Phases method and branch and
bound procedures to solve the bi-objective knapasack problem”, Journal of Global
Optimization, 12, pp. 139-155.
[16] Wolsey, L. (1998) Integer Programming, John Wiley & Sons, Inc.
54
A
Apêndice: Método simplex com variáveis limitadas
Consideremos o problema linear na forma4
max z = cT x
sujeito a :
Ax = b
0·x·u
(35)
(36)
onde u > 0 e A é uma matriz m £ n, com característica m, c e x são vectores n £ 1 .
As inequações (36) traduzem os limites superiores e inferiores das variáveis x.
Uma solução x diz-se solução básica admissível se veri…car as condições do problema
linear e se as colunas da matriz A, correspondentes às componentes de x que estão estritamente compreendidas entre os seus limites, forem linearmente independentes.
Se alguma das variáveis básicas assumir o valor 0 ou o seu limite superior, u, então a
solução diz-se básica admissível degenerada, caso contrário, diz-se solução básica admissível não degenerada. As variáveis não básicas podem assumir ou o valor 0 ou o valor do
limite superior, u.
Suponhamos que se dispõe de uma base admissível inicial - base corrente - (utilizandose ou o método das duas fases ou o método do M-grande) e que se designa por B (matriz
invertível m £ m): Associada a esta base é possível identifcar m variáveis básicas, xB ;
e n ¡ m variáveis não básicas, xN . O sistema Ax = b, pode então escrever-se como
BxB + NxN = b. Isolando xB ; obtemos
xB = B ¡1 b ¡ B ¡1 N xN
(37)
Façamos bb = B ¡1 b ¡ B ¡1 N xN :
A função objectivo pode agora ser reescrita do seguinte modo
¡
¢
z = cTB xB + cTN xN = cTB B ¡1 b ¡ B ¡1 NxN + cTN xN
(38)
Representando cTB B ¡1 por y T e designando por G o conjunto dos índices das variáveis
não básicas, a expressão (38) vem,
X
¢
¡
(39)
z = y T b ¡ y T N ¡ cTN xN = y T b +
cbj xj
j2G
com cbj = cj ¡ y T Aj (preços reduzidos).
O teste de optimalidade da solução baseia-se, como habitualmente, no sinal dos preços
reduzidos das variáveis não básicas. Contudo, como as variáveis não básicas podem assumir valores diferentes de zero, este é agora mais complicado.
Assim, consideremos a variável não básica xj e as seguintes situações:
4
A descrição que fazemos do método simplex com variáveis limitadas segue as referências Nash e Sofer
(1996) e Bazaraa et al. (1990).
55
1. se xj for igual a zero (limite inferior), então, se cbj · 0, o valor da função objectivo
não melhora com a sua entrada na base;
2. se xj for igual a uj (limite superior), então, se cbj ¸ 0, o valor da função objectivo
não melhora com a sua entrada na base.
Se estas condições não forem veri…cadas para todas as variáveis não básicas, então a
solução não é óptima. Suponhamos então que o teste de optimalidade da solução acima
falha na variável xt , sendo, portanto, uma candidata a entrar na base. No quadro simplex,
a coluna associada a esta variável é
ct = B ¡1 At
A
(40)
A determinação da variável que deixa a base é também mais complicada do que habitualmente. Consideremos as diferentes situações que podem ocorrer:
1. a variável xt pode mover-se de um limite para o outro, i.e., se está no limite inferior
passa para o superior ou se está no limite superior passa para o limite inferior;
2. uma variável básica pode aumentar o seu valor, atingindo o seu limite superior, e
deixar a base;
3. uma variável básica pode diminuir o seu valor, atingindo o seu limite inferior, e
deixar a base.
Admitamos que a variável xt é alterada no valor de µ: Atendendo à expressão (37) o
valor das variáveis básicas passa a ser:
xB = B ¡1 b ¡ B ¡1 N(xN + µet )
(41)
onde et é um vector (n ¡ m) £ 1 com valor 1 na linha correspondente à variável xt e com
valor 0 nas restantes posições.
Esta expressão pode ainda simpli…car-se, reduzindo-se a:
ct
xB = bb ¡ µA
(42)
Como o valor de xB deve pertencer ao intervalo [0; uB ] (uB representa o vector com os
limites superiores das variáveis xB ) sob pena da solução não ser admissível, o valor que µ
pode assumir está portanto limitado.
Assim, para cada uma das m variáveis básicas devem veri…car-se as seguintes condições:
(
bbi ¡ µc
ait · ui
(43)
b
bi ¡ µc
ait ¸ 0
c
sendo ac
it o elemento i da coluna At .
56
Comecemos por considerar o caso da variável não básica xt estar no seu limite inferior
(µ > 0):
Se ac
it > 0 a veri…cação das condições (43) impõe que
8
u ¡ bbi
>
>
< µ¸ i
¡c
ait
(44)
b
>
b
i
>
: µ·
ac
it
Visto que
ui ¡ bbi
· 0;
¡c
ait
µ · min
i=1;:::;m
(
bbi
ac
it
)
(45)
Do mesmo modo, se ac
it < 0 a veri…cação das condições (43) impõe que
8
u ¡ bbi
>
>
< µ· i
¡c
ait
b
>
b
>
: µ¸ i
ac
it
Porque
bbi
· 0;
ac
it
µ · min
i=1;:::;m
(
ui ¡ bbi
¡c
ait
)
(46)
(47)
Vejamos agora o caso da variável não básica xt estar no seu limite superior (µ < 0):
Se ac
it > 0 a veri…cação das condições (43) impõe que
8
u ¡ bbi
>
>
< µ¸ i
¡c
ait
(48)
b
>
bi
>
: µ·
ac
it
Mas, visto que
bbi
¸ 0;
ac
it
µ ¸ max
i=1;:::;m
(
57
ui ¡ bbi
¡c
ait
)
(49)
De modo análogo, se ac
it < 0 a veri…cação das condições (43) impõe que
8
u ¡ bbi
>
>
< µ· i
¡c
ait
b
>
b
>
: µ¸ i
ac
it
Contudo, uma vez que
ui ¡ bbi
¸ 0;
¡c
ait
µ ¸ max
i=1;:::;m
(
bbi
ac
it
)
(50)
(51)
Os passos do método simplex com variáveis limitadas podem então ser sumariados
como segue.
Passo 1 Teste de optimalidade. Se para todas as variáveis não básicas se veri…car:
(a) xj = 0 e cbj · 0;
(b) xj = uj e cbj ¸ 0
então a base actual é óptima. Caso contrário, selecciona-se, como candidata a
entrar na base, a variável xt que mais viola o teste de optimalidade.
Passo 2 Cálculo da variação do valor de xt . Determinar o valor mínimo de µ nas hipóteses
seguintes:
(a) µ = ut ; k = t;
¯
¯
)
)
(
bbi ¯¯
ui ¡ bbi ¯¯
(b) se xt = 0, µ = min
;k é o
¯ ac
¯ ac
it > 0 ; µ = min
it < 0
i=1;:::;m
i=1;:::;m
ac
¡c
ait ¯
it ¯
índice associado à determinação de µ:
¯
)
)
( ¯
(
¯
b
b
bi ¯
ui ¡ bi ¯¯
(c) se xt = ut , µ = max
¯ ac
¯ ac
it < 0 ; µ = max
it > 0 ; k é o
i=1;:::;m
i=1;:::;m
ac
¡c
ait ¯
it ¯
índice associado à determinação de µ:
(
A variável que sai da base é xt ; no primeiro caso, e é a k-ésima variável básica, nos
restantes casos.
Passo 3 Pivotação: Alterar a base B e o vector das variáveis básicas xB . Se xt corresponder
simultaneamente à variável que deixa a base e entra na base, então B não sofre
alteração.
58
O valor das variáveis básicas e não básicas, na base corrente, passa a ser, respectivact e xN ¡ µet se xt = ut ou xB + µA
ct e xN + µet se xt = 0. O novo valor da
mente, xB ¡ µA
variável que entra na base passa a xt ¡ µ se xt = ut ou xt + µ se xt = 0:
No problema da mochila, por apenas possuir uma restrição e atendendo aos pressupostos assumidos para os seus coe…cientes, os passos do método simplex descrito são bastante
mais simples, dispensando-se mesmo a veri…cação de algumas condições.
Relembremos a estrutura do problema linear deste problema.
max z = cT x
sujeito a :
wx + s = W
0 · x · 1; s ¸ 0
Neste problema a base corrente é uma matriz 1 £ 1, sendo imediato o cálculo da sua
matriz inversa (inverso do elemento da matriz).
A variável candidata a deixar a base é obviamente única. A variável candidata a entrar
na base é a que mais viola as condições do teste de optimalidade.
A maior simpli…cação do método, neste problema particular, veri…ca-se no Passo 2,
que podemos resumir a:
Passo 2 Cálculo da variação do valor de xt : Determinar o valor mínimo de µ nas hipóteses
seguintes:
(a) µ = 1 (limite superior é 1); k = t;
bb1
(b) se xt = 0, µ =
(c
a1t é sempre positivo); k = 1;
ac
1t
1 ¡ bb1
(c) se xt = 1, µ =
; k = 1:
¡c
a1t
A variável que sai da base é a xt ; no primeiro caso, e é a variável básica, nos
restantes casos:
wt
Designando por xf a variável básica, ac
; e porque bb1 = xf ; podemos ainda
1t =
wf
wf
wf
se xt = 0 e µ = ¡(1 ¡ xf )
se xt = 1:
escrever: µ = xf
wt
wt
ct = xf ¡ xf wf wt = 0; se xt = 0 ou
O novo valor da variável xf passa a ser xf ¡ µA
wt wf
w
w
f
t
ct = xf + (1 ¡ xf )
= 1; se xt = 1:
xf ¡ µ A
wt wf
½
½
¾
¾
wf
wf
O valor da variável que entra na base é min 1; xf
; se xt = 0 ou min 1; (1 ¡ xf )
;
wt
wt
se xt = 1:
59