Programação Binária e Inteira

Programação Inteira (PI)

• Todas as variáveis de decisão são discretas (conjunto finito ou quantidade enumerável de valores provenientes de uma contagem)

Programação Binária (PB)

• Todas as variáveis de decisão são binárias (podem assumir valores 1 – quando a característica de interesse está presente ou 0, caso contrário)

Observação

• Muitos autores não diferenciam as variáveis discretas das binárias,chamando o modelo simplesmente de programação inteira

Exemplos de Problemas (PB)• Problema de designação de tarefas

(programação em redes)• Problema do caminho mais curto (programação

em redes)• Problema da mochila;• Problema de orçamento de capital • Programação de produção• Problema do caixeiro viajante• Problemas de roteirização de veículos

Exemplos de Problemas (PI)

• Problema de escalonamento de pessoal

Exemplos de Problemas (PBM)

• Problema de localização de facilidades– Possíveis localidades (variável binária)– Quantidades entregues (variável contínua)

• Muitos problemas de programação binária e inteira são NP-completos.

• Muitos problemas de programação binária e inteira são NP-completos.– Não podem ser resolvidos em tempo

polinomial em função da alta complexidade computacional.

– Alternativas

Formulação matemática

<=, =, >=

• Uma abordagem para achar a solução ótima é relaxar ou eliminar as restrições de integralidade das variáveis (e/ou a restrição de que as variáveis são binárias)– Relaxação linear do problema de

programação inteira

Exemplo

Exemplo

• Em alguns problemas, mesmo após a relaxação das restrições de integralidade do problema original de PI e resolução do mesmo pelo método Simplex, por exemplo, a solução obtida pode ainda satisfazer as condições de integralidade (e/ou de que as variáveis são binárias) e, portanto, representar a solução ótima do problema original.

• Em muitos casos, não é possível obter diretamente a solução ótima do problema original de PI (PB ou PIB) por meio do relaxamento das condições de integralidade (e/ou relaxamento da restrição de que as variáveis são binárias)– Alternativa: arredondamento da solução obtida após

a relaxação linear– Problema: pode resultar em uma nova solução

infactível não existe garantia de que a solução

encontrada seja ótima- Solução: uso de outros métodos exatos

Métodos de solução exatos

• Branch-and-bound• Algoritmos de plano de corte• Branch-and-cut• Decomposição de Benders,• Relaxação Lagrangeana

• Uma indústria quer se expandir, construindo nova fábrica ou em Los Angeles ou em São Francisco. Também será considerada a construção de um novo depósito na cidade que for selecionada para receber a nova fábrica. O valor presente líquido de cada alternativa está na tabela abaixo. A última coluna dá o capital requerido para os investimentos, sendo o capital total disponível $25 milhões. Achar a combinação viável de alternativas que maximize o valor presente líquido total.

Solução

Exemplo – “Grouping problems”

Exemplo – Problema da Mochila

• Um estudante dispõe de uma mochila com capacidade para 14 kg e tem quatro itens para colocar nela, com pesos e valores (utilidade) diferenciados: Item 1 – peso de 5 kg e valor de 8; Item 2 – peso 7 e valor 11, Item 3 – peso 4 e valor 6, Item 4 – peso 3 e valor 4.

• Deseja maximizar a soma dos valores dos itens colocados na mochila