Universidade Federal de Uberlândia

Faculdade de Matemática
Pesquisa Operacional 1
Estatística
Professor Rafael Alves Figueiredo

Programação por Metas

Cássio Antonio Andrade 11711EST236

Julho
2019
 Sumário

1 INTRODUÇÃO.......................................................................................................... 1

2 OBJETIVOS .............................................................................................................. 2
2.1 Objetivo global .................................................................................................... 2
2.2 Objetivos específicos ........................................................................................... 2

3 METODOLOGIA ...................................................................................................... 3
3.1 Problemas de Otimização Multiobjetivo - POM.............................................. 3
3.2 Classificação dos métodos de resolução dos POM ........................................... 4
3.3 Programação por metas ..................................................................................... 5

4 EXEMPLO ............................................................................................................... 10
4.1 Método dos pesos .............................................................................................. 11
4.2 Método hierárquico .......................................................................................... 12

5 REFERÊNCIAS BIBLIOGRÁFICAS ................................................................... 14

 1

1 INTRODUÇÃO

Nos modelos de Programação Linear apresentados no curso buscava-se uma solução

ótima para uma única função objetivo. Entretanto, muitas vezes na modelagem dos problemas
reais é possível deparar com situações em que mais de um objetivo é almejado, podendo estes
serem conflitantes. Vários exemplos podem ser citados: um político que promete reduzir a
dívida nacional e ao mesmo tempo oferecer redução da carga tributária, um investidor que busca
aumentar os lucros e reduzir os riscos, uma indústria que deseja reduzir os custos de produção
e de estoque.

Neste trabalho, será explorada uma das técnicas de resolução de problemas de

otimização multiobjetivo (POM), denominada Programação por Metas. O mesmo é estruturado
em seis capítulos. No capítulo dois especificam-se os objetivos e no três a metodologia é
apresentada. Seguindo, uma breve revisão bibliográfica referente ao tema desenvolvido. Um
exemplo é mostrado no quinto capítulo e finaliza-se com as referências bibliográficas no último
capítulo.
 2

2 OBJETIVOS

2.1 Objetivo global

Como objetivo geral, pretende-se apresentar um panorama geral dos problemas de

otimização multiobjetivo.

2.2 Objetivos específicos

Como objetivo específico pretende-se:

i. Realizar uma revisão bibliográfica sobre o tema;

ii. Aprofundar em um dos métodos de resolução dos POM, a programação por metas;
iii. Apresentar a resolução de um exemplo.
 3

3 METODOLOGIA

Com a finalidade de atingir os objetivos, foi realizada uma revisão bibliográfica por
meio de livros e artigos sobre o tema, além da resolução de um exemplo aplicando a teoria
estudada.

3.1 Problemas de Otimização Multiobjetivo - POM

A maior parte dos problemas reais requer a otimização simultânea de múltiplos

objetivos. Gomes e Chaves (2004) ilustram na figura 1 um problema com dois objetivos
conflitantes em que é possível ver que a solução que otimiza uma função objetivo não é a mesma
que otimiza a outra. Para cada um dos objetivos, uma solução diferente seria escolhida.

Figura 1 - Funções Objetivos Distintas

Diante desse impasse, geralmente o que se busca como resultado de uma proposição
multiobjetivo é um conjunto de soluções que caracteriza o comprometimento entre os objetivos,
que é conhecido como Pareto-ótimo. As soluções que o compõem são ótimas no sentido que
não existe dentro do universo de busca qualquer solução melhor que elas quando todos os
objetivos são considerados simultaneamente. O principal alvo da Otimização Multiobjetivo
(também chamada de Multicritério ou Vetorial) é a obtenção das soluções Pareto e,
 4

consequentemente, conhecer o conjunto dos compromissos possíveis entre os objetivos

(ÁVILA, 2006)

Algumas definições básicas (GOMES; CHAVES, 2004) são relevantes para o tema:

 Alternativa Dominada: uma solução é dominada se e somente se existe uma outra

melhor em pelo menos um critério, sem ser pior em algum dos outros.
 Alternativa Eficiente (Não-Dominada ou Ótima de Pareto): uma solução é eficiente
se e somente se não é dominada por alguma solução admissível.

Pode-se afirmar, então, que enquanto o conceito chave da programação linear

monocritério é obter a solução ótima, na programação multicritério é encontrar a melhor
solução não dominada (ou conjunto das melhores ações não dominadas).

3.2 Classificação dos métodos de resolução dos POM

Existem vários métodos para resolução dos problemas de otimização multiobjetivo,

sendo que Rangaiah e Bonilla-Petriciolet (2013) ilustram uma classificação destes na figura 2.

Figura 2 - Métodos de resolução dos POM

 5

Cada ramificação do diagrama é explicada em Ramos et al. (2014):

 Métodos geradores: geram uma ou várias soluções de Pareto-ótimas sem considerar a

escolha do tomador de decisões. Apenas depois de encontrar as que o decisor entra em
ação.
 No-preference methods não considera as preferências do decisor (ex: Global
Criterion, Neutral Compromise Solution)
 a posteriori methods são baseados na solução do POM original através da
solução de uma série de problemas de otimização com um único objetivo para
encontrar a região de Pareto. Uma das abordagens utiliza processos de
escalarização (ex: método ε-restrito, método da soma ponderada). Já a
outra utiliza algoritmos estocásticos (ex: algoritmos genéticos, Simulated
Annealing).

 Métodos baseados nas preferências utiliza as escolhar do decisor em diferentes

estágios da solução do problema.
 A priori preference methods: As escolhas do decisor são incluídas desde o
início no POM, que é transformado em um ou vários problemas de otimização
com uma função objetivo apenas. No fim uma única solução é obtida conforme
as preferências do decisor (ex: método da distância a um ponto de referência,
programação por metas)
 Interactive methods: Evolui para a solução preferida a partir de decisões
parciais sobre hipóteses que vão sendo apresentadas ao decisor. Há uma
progressiva articulação das preferências do decisor, por meio de alternadas
fases de cálculos e fases de explicitação de preferências.

3.3 Programação por metas

A programação por metas permite considerar objetivos distintos, com unidades distintas
e com metas que são alvos desejáveis a serem atingidos e emprega a noção de uma distância
mínima do melhor. Assim, o objetivo passa a ser minimizar os desvios em ordem às metas pré-
fixadas.

Arenales et al. (2007) afirma que a programação por metas é um dos métodos de solução
de problemas de otimização mujltiobjetivo mais populares, no qual busca-se encontrar uma
solução de compromisso entre os objetivos conflitantes, estabelecendo a priori valores
aceitáveis (metas) para cada função objetivo. Considere o seguinte problema:
 6

Conforme as expressões acima, deseja-se encontrar um valor de f1(x) grande, ao passo

que f2(x) e f3(x) sejam pequenos. O decisor deve então estipular metas com as quais ele ficará
satisfeito, ou seja, um valor mínimo para f1(x), um valor máximo para f2(x) e um valor ideal
para f3(x), por exemplo.

Com isso, o problema anterior é reformulado transformando os objetivos em restrições-

metas, de acordo com as metas σ1, σ2 e σ3, buscando então encontrar uma solução factível para
o sistema:

Mesmo após essa reformulação, é possível que o problema seja infactível, sendo que o
decisor deve abrir mão de uma ou mais metas escolhidas. Deve-se supor que as restrições
originais do problema Ax=b, x>0 sejam factíveis, afim de que o problema multiobjetivo possa
ter solução. A flexibilização das restrições-meta pode ser traduzida com a introdução de novas
variáveis, chamadas variáveis de desvio (similares às variáveis artificiais):

Tanto Taha (20080) quanto Arenales et al.(2007) relatam que dois métodos têm sido
utilizado para otimização de modelos de programação por metas: o método dos pesos e o
 7

método hierárquico. Em ambos, a estratégia é a conversão dos múltiplos objetivos em uma

única função.

Método dos pesos

Neste método, o interesse é que as variáveis de desvio sejam o mais próximo de zero,
sendo que cada uma dessas variáveis de desvio tem uma importância que deve ser definida pelo
decisor conforme os pesos wi. O problema então é formulado de forma a minimizar as variáveis
de desvio conforme a ponderação feita pelo decisor:

Método Hierárquico

Nesta metodologia, os objetivos são tomados sequencialmente, conforme priorização

definida pelo decisor. Supondo o objetivo 1 como o mais prioritário, o objetivo 2 intermediário
e o objetivo 3 o menos prioritário, a estratégia então é minimizar primeiramente o desvio y1.
Resolve-se então o problema monoobjetivo, conforme o seguinte modelo:

𝑀𝑒𝑡𝑎 1:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 𝑦1

𝑠𝑎:

𝑓1 (𝒙) + 𝑦1 ≥ 𝜎1

𝑓2 (𝒙) − 𝑦2 ≤ 𝜎2

𝑓3 (𝒙) + 𝑦3+ − 𝑦3− = 𝜎3

𝑨𝒙 = 𝒃
 8

𝒙 ≥ 𝟎, 𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3+ ≥ 0, 𝑦3− ≥ 0

Encontra-se então o valor de y1 (denotado por k1) resolvendo o problema, que na etapa
dois será incluída como restrição e a função objetivo será minimizar y2.

𝑀𝑒𝑡𝑎 2:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 𝑦2

𝑠𝑎:

𝑓1 (𝒙) + 𝑦1 ≥ 𝜎1

𝑓2 (𝒙) − 𝑦2 ≤ 𝜎2

𝑓3 (𝒙) + 𝑦3+ − 𝑦3− = 𝜎3

𝑦1 = 𝑘1

𝑨𝒙 = 𝒃

𝒙 ≥ 𝟎, 𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3+ ≥ 0, 𝑦3− ≥ 0

Novamente o problema é resolvido, encontra-se o valor de y2 (denotado por k2) que será
uma restrição no passo 3, cuja função objetivo é minimizar o somatório𝑦3+ e 𝑦3− .

𝑀𝑒𝑡𝑎 3:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 𝑦3+ + 𝑦3−

𝑠𝑎:

𝑓1 (𝒙) + 𝑦1 ≥ 𝜎1

𝑓2 (𝒙) − 𝑦2 ≤ 𝜎2

𝑓3 (𝒙) + 𝑦3+ − 𝑦3− = 𝜎3

𝑦1 = 𝑘1

𝑦2 = 𝑘2

𝑨𝒙 = 𝒃
 9

𝒙 ≥ 𝟎, 𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3+ ≥ 0, 𝑦3− ≥ 0

Taha (202) conclui a programação por metas acha uma solução que simplesmente
cumpra as metas do modelo sem levar em conta a otimização. Essa é uma desvantagem da
utilização da programação por metas, visto que essa deficiência em encontrar uma solução
ótima pode levantar dúvidas sobre a viabilidade da técnica no objetivo de otimização
 10

4 EXEMPLO

Um exemplo bem didático é o de uma fábrica de pasta de papel (ROMERO, 1993) em

que há a produção de polpa de celulose, obtida por meios mecânicos e por meios químicos.
Represente-se por x1 e x2, respetivamente as toneladas diárias de polpa de celulose obtidas pelos
procedimentos referidos. As capacidades máximas de produção são estimadas em 300 (x1) e
200 (x2) toneladas por dia para cada um dos tipos de pasta de celulose. Cada tonelada de
celulose produzida requer 1 trabalhador e a empresa dispões de 400 trabalhadores. A margem
bruta por tonelada de celulose é de 1000 unidades monetárias para x1 e 3000 para x2. Os custos
fixos da fábrica de papel estimam-se em 300000 unidades monetárias. A empresa pretende
cobrir estes custos. As preferências da empresa vão no sentido de maximizar a produção e
minimizar os efeitos negativos no rio para onde escoam os seus resíduos produtivos (objetivo
ambiental). Os resíduos produzidos por tonelada de pasta de celulose obtida por meios
mecânicos e por meios químicos, medidas pelas necessidades biológicas na água do rio, são de
1 para x1 e 2 para x2.

O problema descrito acima pode ser modelado da seguinte forma:

𝑀𝑎𝑥 𝑓1 (𝒙) = 1000 𝑥1 + 3000 𝑥2

𝑀𝑖𝑛 𝑓2 (𝒙) = 1 𝑥1 + 2 𝑥2

𝑠𝑎:

𝑥1 ≤ 300

𝑥2 ≤ 200

1000 𝑥1 + 3000 𝑥2 ≥ 300.000

1 𝑥1 + 1 𝑥2 ≤ 400

𝑥1 , 𝑥2 ≥ 0

Supõe-se que o decisor se satisfaça com as seguintes metas:

 Margem bruto de, no mínimo, 600 mil (meta 1);

 Produção de, no máximo, 450 toneladas de resíduos (meta 2);
 11

4.1 Método dos pesos

Formulando o problema para resolução pelo método dos pesos, tomando-se peso 2 para
meta 1 e o peso 1 para meta 2, tem-se:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 0𝑥1 + 0𝑥2 + 2𝑦1 + 1𝑦2

𝑠𝑎:

1𝑥1 + 0𝑥2 + 0𝑦1 + 0𝑦2 ≤ 300

0𝑥1 + 1𝑥2 + 0𝑦1 + 0𝑦2 ≤ 200

1000 𝑥1 + 3000 𝑥2 + 1𝑦1 + 0𝑦2 ≥ 600.000

1 𝑥1 + 2 𝑥2 + 0𝑦1 − 1𝑦2 ≤ 450

1 𝑥1 + 1 𝑥2 ≤ 400

𝑥1 , 𝑥2 , 𝑦1 , 𝑦2 ≥ 0

Resolvendo esse problema linear com auxílio do software R, encontra-se:

> f.obj =c(0,0,2,1)

> restricao=matrix(c(1,0,0,0,0,1,0,0,1000,3000,1,0,1,2,0,-1,1,1,0,0),nrow=5
,byrow=TRUE)
> f.dir=c("<=","<=",">=","<=","<=")
> recursos=c(300,200,600000,450,400)
> lp(direction = "min",f.obj,restricao,f.dir,recursos) ##f otimo
Success: the objective function is 0
> lp ("min", f.obj, restricao,f.dir,recursos)$solution ## solucao oti
ma
[1] 0 200 0 0

Portanto, verifica-se que para as metas escolhidas σ1=600000 e σ2=400, obtém-se como
solução x1=0, x2=200, y1=0 e y2=0, ou seja, atinge-se um lucro de 600 mil e uma produção de
resíduos de 400 toneladas. Como y1 e y2 são nulos, verifica-se que as restrições meta foram
atendidas.
 12

4.2 Método hierárquico

Considerando que a meta 1 é mais prioritária que a meta 2, na primeira etapa formula-
se o problema da seguinte forma:

𝑀𝑒𝑡𝑎 1:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 0𝑥1 + 0𝑥2 + 1𝑦1 + 0𝑦2

𝑠𝑎:

1𝑥1 + 0𝑥2 + 0𝑦1 + 0𝑦2 ≤ 300

0𝑥1 + 1𝑥2 + 0𝑦1 + 0𝑦2 ≤ 200

1000 𝑥1 + 3000 𝑥2 + 1𝑦1 + 0𝑦2 ≥ 600.000

1 𝑥1 + 2 𝑥2 + 0𝑦1 − 1𝑦2 ≥ 450

1 𝑥1 + 1 𝑥2 ≤ 400

𝑥1 , 𝑥2 , 𝑦1 , 𝑦2 ≥ 0

Novamente com o auxílio do software R, encontra-se.

> f.obj =c(0,0,1,0)

> restricao=matrix(c(1,0,0,0,0,1,0,0,1000,3000,1,0,1,2,0,-1,1,1,0,0),nrow=5
,byrow=TRUE)
> f.dir=c("<=","<=",">=","<=","<=")
> recursos=c(300,200,600000,450,400)
> lp(direction = "min",f.obj,restricao,f.dir,recursos) ##f otimo
Success: the objective function is 0
> lp ("min", f.obj, restricao,f.dir,recursos)$solution ## solucao oti
ma
[1] 0 200 0 0

Ou seja, o valor de y1 encontrado foi 0. Esse resultado será inserido na próxima etapa
como uma restrição. Opcionalmente também pode-se retirar a variável y1 do modelo.

𝑀𝑒𝑡𝑎 2:

𝑀𝑖𝑛 𝜑(𝒙, 𝒚) = 0𝑥1 + 0𝑥2 + 0𝑦1 + 1𝑦2

𝑠𝑎:
 13

1𝑥1 + 0𝑥2 + 0𝑦1 + 0𝑦2 ≤ 300

0𝑥1 + 1𝑥2 + 0𝑦1 + 0𝑦2 ≤ 200

1000 𝑥1 + 3000 𝑥2 + 1𝑦1 + 0𝑦2 ≥ 600.000

1 𝑥1 + 2 𝑥2 + 0𝑦1 − 1𝑦2 ≥ 450

1 𝑥1 + 1 𝑥2 ≤ 400

𝑦1 = 0

𝑥1 , 𝑥2 , 𝑦1 , 𝑦2 ≥ 0

> f.obj =c(0,0,0,1)

> restricao=matrix(c(1,0,0,0,0,1,0,0,1000,3000,1,0,1,2,0,-1,1,1,0,0,0,0,1,0
),nrow=6,byrow=TRUE)
> f.dir=c("<=","<=",">=","<=","<=","=")
> recursos=c(300,200,600000,450,400,0)
> lp(direction = "min",f.obj,restricao,f.dir,recursos) ##f otimo
Success: the objective function is 0
> lp ("min", f.obj, restricao,f.dir,recursos)$solution ## solucao oti
ma
[1] 0 200 0 0

O valor de y2 encontrado foi 0. Assim, temos que a solução final é o vetor (x1, x2, y1, y2)
= (0,200,0,0). Observa-se que a solução encontrada no método dos pesos foi a mesma no mesmo
no método hierárquico. Isso geralmente ocorre quando utilizamos uma ponderação exagerada
no método dos pesos. Entretanto, não é necessário que as soluções dos métodos sejam as
mesmas.
 14

5 REFERÊNCIAS BIBLIOGRÁFICAS

AVILA, S. L., Otimização multiobjetivo e análise de sensibilidade para concepção de

dispositivos. 2006. 148 f. Tese (Doutorado em Engenharia Elétrica) - Universidade Federal de
Santa Catarina. Florianópolis, 2006.

ARENALES, M. N. et al. Pesquisa operacional. Rio de Janeiro: Elsevier Editora Ltda., 2007.

GOMES, C. F. S.; CHAVES, M. C. C. Aplicação da Programação por METAS e Método

Lexicográfico ao Método STEM – nova proposta de algoritmo de formulação linear
multiobjetivo. XXXVI SBPO, 2004, São João Del Rei. XXXVI SBPO. p. 1033-1044.
Disponível em: < http://www.din.uem.br/sbpo/sbpo2004/pdf/arq0157.pdf> Acesso em: 09
jul.2019.

RAMOS, M. et al. Multiobjective Optimization Using Goal Programming for Industrial

Water Network Design. Industrial and engineering chemistry research, American Chemical
Society, 2014, 53 (45), pp.17722-17735. 10.1021/ie5025408. hal-1893042

RANGAIAH, G. P.; BONILLA-PETRICIOLET, A. Multi-Objective Optimization in

Chemical Engineering: Developments and Applications, 1st ed.; Wiley: New York, 2013.a

ROMERO, C. Teoría de la Decisión Multicritério: Conceptos, Técnicas y Aplicacciones,

Madrid, Alianza Universidad Textos, 1993.

TAHA, H. A. Pesquisa Operacional. 8a Edição. São Paulo: Pearson Prentice Hall. 2008.