Scribd
Carregar
7 visualizações7 páginas

Resolução de Programação Linear Inteira

Este documento discute programação linear inteira, que difere da programação linear convencional ao exigir que as variáveis de decisão sejam inteiras em vez de fracionárias. Aborda como os problemas de programação linear inteira são mais difíceis de resolver do que os problemas de programação linear convexa devido à natureza não convexa de sua região viável. Também descreve o método branch-and-bound para resolver problemas de programação linear inteira.

Enviado por

bassizalcoatl
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
7 visualizações7 páginas

Resolução de Programação Linear Inteira

Este documento discute programação linear inteira, que difere da programação linear convencional ao exigir que as variáveis de decisão sejam inteiras em vez de fracionárias. Aborda como os problemas de programação linear inteira são mais difíceis de resolver do que os problemas de programação linear convexa devido à natureza não convexa de sua região viável. Também descreve o método branch-and-bound para resolver problemas de programação linear inteira.

Enviado por

bassizalcoatl
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd

Programação Linear Inteira

Programação Linear Inteira 1


Programação Linear Inteira

• Muitas das decisões e variáveis em casos reais são


inerentemente inteiros;
• Por exemplo, um número de produtos a serem
fabricados não pode ser fracionado e tem que ser
inteiro;
• Muitos dos problemas que são enfrentados em
casos reais, têm a escolha de uma opção em sua
estrutura, por exemplo:
– Em quais ações investir
– Qual rota escolher para se mudar
– Qual arco do gráfico escolher

Programação Linear Inteira 2


Variáveis inteiras

• A única diferença entre problemas de PL e problemas


de PI na estrutura é a definição das variáveis de decisão.
• No entanto, essa mudança mudará fundamentalmente
as características do problema em questão.
• Problemas de LP têm um conjunto convexo como sua
região viável, enquanto problemas de IP têm um
conjunto de vetores inteiros como sua região viável
(não-convexa).
• Lidar com problemas de otimização não convexa é
muito mais difícil do que problemas de otimização
convexa.

Programação Linear Inteira 3


Como resolver problemas de IP

• Relaxamento de LP: O relaxamento de LP e o


problema de IP é quando permitimos que as
variáveis assumam valores fracionários (como nosso
exemplo).
• A ideia para resolver problemas de IP é resolver
uma série de problemas específicos de LP que nos
guiarão para uma solução inteira viável.
• Esse método é chamado de Branch-and-Bound.
– Neste método, ramificamos em valores fracionários e os tornamos
o valor inteiro inferior ou superior.
– É importante notar que o arredondamento da solução de PL não
necessariamente dará a solução ideal ou mesmo viável.

Programação Linear Inteira 4


Características importantes dos problemas de IP
• Problemas de IP geralmente são muito mais
complicados do que problemas de LP.
• Muitas das classes IP são conhecidas como problemas
NP-hard, que leva muito tempo de processamento para
que os computadores encontrem a solução ideal (Anos,
para problemas de tamanho de caso real).
• Tem havido uma vasta investigação nesta área, a fim de
encontrar formas de resolver estes problemas.
– Cutting Planes
– Branch-and-Cut
– Column Generation techniques
– Branch-and-Price
– Meta Heuristics

Programação Linear Inteira 5


Exemplos

1. [Link]

2. [Link]

Programação Linear Inteira 6


Obrigado pela atenção

Programação Linear Inteira 7

Você também pode gostar