Relatório PO - ALGORITMO DE PLANO DE CORTE

Prévia do material em texto

UNIVERSIDADE FEDERAL RURAL DO SEMI-ÁRIDO 
DEPARTAMENTO DE ENGENHARIAS (DENGE) 
CURSO ENGENHARIA DE PRODUÇÃO 
 
 
 
 
 
 
 
RELATÓRIO SOBRE ALGORITMO DE PLANO DE CORTE 
 
 
 
 
 
 
 
ALICE MONIQUE ARAÚJO ALBINO 
 
 
 
 
 
 
 
 
 
ANGICOS 
2022 
1 
 
ALICE MONIQUE ARAÚJO ALBINO 
 
 
 
 
 
 
 
 
 
 
RELATÓRIO SOBRE ALGORITMO DE PLANO DE CORTE 
 
 
 
 
 
 
 
 
Relatório apresentado à Universidade Federal 
Rural do Semi-Árido como complemento para 
obtenção da segunda nota da disciplina 
Pesquisa Operacional I. 
 
Professor Dr. Ciro José Jardim de Figueiredo. 
 
 
 
 
 
 
 
 
ANGICOS 
2022 
 
2 
 
LISTA DE SÍMBOLOS 
 
≤ Menor - Igual 
≥ Maior - Igual 
= Igual 
+ 
- 
Mais 
Menor 
𝜖 Limite 
∑ Somatório 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 
SUMÁRIO 
 
1 INTRODUÇÃO ................................................................................................................. 4 
2 DEFINIÇÃO DE ALGORITMO DE PLANO DE CORTE ......................................... 4 
2.1 Programação Inteira ......................................................................................................... 5 
3 PROCEDIMENTO PARA GERAÇÃO DE PLANOS DE CORTE ............................ 6 
4 CONSIDERAÇÕES FINAIS ........................................................................................... 7 
REFERÊNCIAS........................................................................................................................ 7 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 
1 INTRODUÇÃO 
 
Segundo a Associação Brasileira de Engenharia de Produção - ABEPRO, Pesquisa 
Operacional, popularmente conhecida como PO, é a área de conhecimento e desenvolvimento 
que estuda e aplica métodos científicos a problemas complexos, com o foco de colaborar no 
processo de tomada de decisão. Possui aplicação no planejamento, projeção e operações de 
sistemas e áreas de atuação humana. 
PO possui diversas atribuições profissionais essas atribuições encontram-se 
subdivididas em diferentes áreas de conhecimento: a) Avaliação operacional dos sistemas; b) 
apoio a tomada de decisão; c) estruturação de problemas; d) otimização de processos 
produtivos; e) simulação dos processos (SANTOS et al. 2010). 
Em função de sua flexibilidade de aplicações e interação multidisciplinar a PO é 
reconhecida como uma área com vasta oportunidade de carreiras e de trabalhos. Um 
profissional em PO é preparado para compreender e resolver problemas em diversas áreas, 
tendo como base o uso de métodos analíticos e o foco em resultados. 
O objetivo deste trabalho, é definir e conceituar Pesquisa Operacional e abordar o 
assunto algoritmo de plano de corte, bem como o método exato, que busca iterativamente 
refinar um conjunto viável ou função objetivo por meio de inequações lineares, chamadas 
cortes. 
 
2 DEFINIÇÃO DE ALGORITMO DE PLANO DE CORTE 
 
Um dos primeiros métodos utilizados para resolver problemas de programação inteira. 
Em Pesquisa Operacional (PO), o método de planos de corte é um método exato para 
Programação Linear (LI), que busca iterativamente refinar um conjunto viável ou função 
objetivo por meio de inequações lineares, chamadas cortes. Os procedimentos são utilizados 
para encontrar soluções inteiras para problemas de Programação Linear Inteira (PLI), bem 
como para resolver problemas gerais de otimização convexa. Esse método foi criado pelo 
matemático estadunidense, Ralph Gomory. 
A resolução do problema a partir de uma solução de um problema de Programação linear 
inicia com cada iteração, o algoritmo adiciona uma restrição linear que é satisfeita por uma 
solução inteira do problema original, eliminando as partes fracionárias da solução não-inteira. 
O algoritmo chega ao seu fim quando uma solução inteira é obtida. 
 
https://pt.wikipedia.org/wiki/Pesquisa_Operacional
https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_linear
https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_inteira
https://pt.wikipedia.org/wiki/Otimiza%C3%A7%C3%A3o
https://www.wikiwand.com/pt/Programa%C3%A7%C3%A3o_linear
https://www.wikiwand.com/pt/Algoritmo
5 
 
De acordo com o problema de maximização: 
 
𝑍 = ∑ 𝐶𝐽𝑋𝐽
𝑛
𝑗=1
 
𝑍 = ∑ 𝑎𝑖𝑗𝑥𝑗𝑛𝑗=1 = 𝑏𝑖 (𝑖 = 1,2, . . . , 𝑚) 
𝑥𝑗 𝜖 𝑍 + (𝑗 = 1,2, . . . , 𝑛) 
 
Segundo os autores Hillier e Lieberman (2013), o plano de corte de qualquer problema 
de Programação Inteira (PI), é uma nova restrição funcional que reduz a área de soluções viáveis 
para o relaxamento de PL sem eliminar nenhuma solução viável para o problema de PI. 
Ainda segundo os autores, foi desenvolvida uma série de técnicas para a geração de 
planos de corte que tenderão a acelerar a velocidade para um algoritmo de ramificação e 
avaliação progressiva para encontrar uma solução ótima para um problema de PIB puro. 
Algoritmos PI mais modernos agora usam o método de ramificação e corte. Essa 
abordagem algorítmica combina pré-processamento automático de problemas, geração de 
planos de corte e técnicas mais inteligentes de ramificação e avaliação incremental. A pesquisa 
nesta área continua à medida que novos pacotes de software sofisticados incorporando essas 
técnicas são desenvolvidos. O mais recente avanço nos métodos PI é começar a incorporar a 
programação de restrição. Parece que essa abordagem expandirá muito nossa capacidade de 
formular e resolver modelos (HILLIER E LIEBERMAN, 2013). 
 
2.1 Programação Inteira 
 
A programação inteira pode ser entendida como um caso especial de Programação 
linear, onde as variáveis devem ser inteiras (ou pelo menos parciais essas variáveis). A rigor, o 
nome mais correto para programação inteira é programação linear. Quando todas as variáveis 
devem ter valores inteiros, o modelo é chamado de problema de programação inteira pura, caso 
contrário é chamado de problema de programação inteira mista (NOGUEIRA, 2010). 
Logo abaixo observamos o modelo formal: 
 
𝑀𝑎𝑥 𝑜𝑢 𝑀𝑖𝑛 𝑍 = ∑𝑛𝑗=1 𝑐𝑗𝑥𝑗 
𝑆. 𝐴 
∑ 𝑎𝑖𝑗𝑋𝑗 ≤ 𝑏𝑖𝑛𝑗=1 para 𝑖 = 1,2, . . . 𝑚 
(2) 
(1) 
(3) 
(4) 
6 
 
 𝑥𝑗 𝜖 𝑍 + para 𝑗 = 1,2, . . . , 𝑝 (≤ 𝑛) 
 𝑥𝑗 ≥ 0 para 𝑗 = 𝑝 + 1, . . . , 𝑛 
 
Os problemas de PI geralmente surgem porque algumas ou todas as variáveis de decisão 
devem ser restritas a valores inteiros. Existem também muitas aplicações envolvendo decisões 
sim ou não que podem ser representadas por variáveis binárias (0-1) (incluindo relações 
combinatórias que podem ser representadas por tais decisões). Esses fatores fazem da 
programação inteira uma das técnicas de PO mais utilizadas (HILLIER E LIEBERMAN, 2013). 
 
3 PROCEDIMENTO PARA GERAÇÃO DE PLANOS DE CORTE 
 
I - Considere qualquer restrição funcional na forma contendo apenas coeficientes não negativos. 
II - Encontre um grupo de variáveis (chamado cobertura mínima da restrição) tal que: 
(a) A restrição é violada caso todas as variáveis do grupo forem iguais a 1 e todas as demais 
variáveis básicas forem igual a 0. 
(b) No entanto, a restrição é satisfeita, caso o valor de qualquer uma dessas variáveis for 
modificado de 1 para 0. Fazendo que N represente o número de variáveis no grupo, o 
plano de corte resultante tem a se- guinte forma: 
Soma de variáveis no grupo ≤ 𝑁 − 1. 
Aplicando-se esse procedimento à restrição 6𝑥1 + 3𝑥2 + 5𝑥3 + 2𝑥4 ≤ 10, 
observamos que o grupo de variáveis {𝑥1, 𝑥2, 𝑥4} é uma cobertura mínima, pois: 
 
(a) (1, 1, 0, 1) viola a restrição; 
(b) No entanto, a restrição é satisfeita, caso o valor de qualquer uma dessas três 
variáveis for modificado de 1 para0. 
 
Já que nesse caso 𝑁 = 3, o plano de corte resultante é 𝑥1 + 𝑥2 + 𝑥4 ≤ 2. Essa mesma 
restrição também tem uma segunda cobertura mínima {x1, x3}, visto que (1, 0, 1, 0) 
viola a restrição, mas tanto (0, 0, 1, 0) quanto (1, 0, 0, 0) satisfazem a restrição. Portanto, é mais 
um plano de corte válido. 
A abordagem de ramificação e corte envolve primeiro a geração de muitos planos de 
corte semelhantes e, em seguida, a aplicação de técnicas mais inteligentes de ramificação e 
avaliação progressiva. Os resultados de incluí-los podem ser bastante drásticos no aperto da 
7 
 
folga do PL. Em alguns casos, a distância entre a solução ótima Z do relaxamento PL de todo 
o problema GDP e a solução ótima Z do problema é reduzida em até 98%. 
4 CONSIDERAÇÕES FINAIS 
 
 Após a realização do trabalho, foi constatada a importância do método de plano de corte 
na Pesquisa Operacional, não só no que consiste na realização dos problemas de PI, mas 
também as variáveis de decisão precisarem ser restritas e possuir valores inteiros, assim sendo 
necessárias para aplicações que envolvem tomada de decisão. 
REFERÊNCIAS 
 
ABEPRO (org.). Pesquisa Operacional. Disponível em: 
https://abepro.org.br/internasub.asp?ss=18&c=545#:~:text=ABEPRO%20%2D%20Associa%
C3%A7%C3%A3o%20Brasileira%20de%20Engenharia%20de%20Produ%C3%A7%C3%A3
o&text=Pesquisa%20operacional%20%C3%A9%20a%20aplica%C3%A7%C3%A3o,aloca%
C3%A7%C3%B5es%20eficientes%20de%20recursos%20escassos.. Acesso em: 21 set. 2022. 
 
NOGUEIRA, Fernando. Programação Inteira. 2013. Disponível em: 
https://www.ufjf.br/epd015/files/2010/06/ProgramacaoInteira.pdf. Acesso em: 21 set. 2022. 
 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. Introdução à Pesquisa Operacional. 
Grupo A, 2013. E-book. ISBN 9788580551198. Disponível em: 
https://app.minhabiblioteca.com.br/#/books/9788580551198/. Acesso em: 21 set. 2022. 
 
SANTOS, Valquíria Lilian et al. Efinições e Conceitos da Área de Pesquisa Operacional. 
2010. Disponível em: https://silo.tips/download/definioes-e-conceitos-da-area-de-pesquisa-
operacional. Acesso em: 22 set. 2022.