Pós-graduação
  1. Introdução à análise real  1.1. Teoria dos conjuntos e lógica em análise real  1.1.1. Conjuntos e operações na teoria dos conjuntos e lógica em análise real  1.1.2. Relações e funções  1.1.3. Lógica e quantificadores  1.1.4. Cardinalidade dos conjuntos  1.2. Espaço métrico  1.2.1. Introdução aos conjuntos abertos e fechados em espaços métricos  1.2.2. Convergência de sequências em um espaço métrico  1.2.3. Função contínua em um espaço métrico  1.2.4. Compacidade e completude em espaços métricos na análise real  1.3. Sequências e séries  1.3.1. Convergência de sequências  1.3.2. Séries infinitas  1.3.3. Convergência uniforme  1.3.4. Séries de potências  1.4. Discriminação  1.4.1. Teorema do valor médio  1.4.2. Série de Taylor  1.4.3. Funções de várias variáveis  1.4.4. Derivada parcial  1.5. Integração  1.5.1. Integração de Riemann e Lebesgue  1.5.2. Integrais impróprias  1.5.3. Teoria da Medida: uma ferramenta fundamental na integração  1.5.4. Teorema de Fubini  1.6. Análise funcional  1.6.1. Compreendendo espaços de Banach  1.6.2. Espaços de Hilbert  1.6.3. Operadores em espaços  1.6.4. Teoria Espectral
  2. Álgebra Abstrata  2.1. Compreendendo grupos na álgebra abstrata  2.1.1. Definições e exemplos de grupos na álgebra abstrata  2.1.2. Homomorfismos de grupos  2.1.3. Introdução aos subgrupos normais  2.1.4. Teorema de Sylow  2.2. Anéis e campos  2.2.1. Ideais e anéis quocientes  2.2.2. Extensões de campos  2.2.3. Teoria de Galois  2.2.4. Anéis de polinômios  2.3. Introdução aos módulos em álgebra abstrata  2.3.1. Homomorfismo de Módulos  2.3.2. Módulos livres  2.3.3. Introdução aos produtos tensoriais  2.3.4. Sequência exata em módulos  2.4. Álgebra linear  2.4.1. Espaço vetorial  2.4.2. Autovalores e autovetores  2.4.3. Espaço de produto interno  2.4.4. Diagonalização
  3. Topologia  3.1. Topologia Geral  3.1.1. Conjuntos abertos e fechados  3.1.2. Compacidade e conexidade  3.1.3. Mapas contínuos  3.1.4. Axioma de separação  3.2. Topologia algébrica  3.2.1. Compreendendo grupos fundamentais em topologia algébrica  3.2.2. Homotopia e homologia  3.2.3. Complexo simplicial  3.2.4. Sequências exatas em homologia  3.3. Topologia Diferencial  3.3.1. Compreendendo variedades na topologia diferencial  3.3.2. Funções Suaves  3.3.3. Espaço tangente e cotangente  3.3.4. Feixes vetoriais
  4. Equações diferenciais  4.1. Equação diferencial ordinária  4.1.1. Equações de primeira ordem  4.1.2. Equações lineares de segunda ordem  4.1.3. Sistemas de equações diferenciais  4.1.4. Análise de estabilidade em equações diferenciais ordinárias  4.2. Equações diferenciais parciais  4.2.1. Classificação de PDE  4.2.2. Compreendendo séries de Fourier em equações diferenciais parciais  4.2.3. Introdução às funções de Green  4.2.4. Método de caracterização  4.3. Sistemas dinâmicos em equações diferenciais  4.3.1. Teoria da Sustentabilidade  4.3.2. Ciclos limite em sistemas dinâmicos  4.3.3. Teoria do caos  4.3.4. Teoria da bifurcação
  5. Probabilidade e estatística  5.1. Teoria da probabilidade  5.1.1. Variáveis aleatórias  5.1.2. Distribuições de probabilidade  5.1.3. Lei dos grandes números  5.1.4. Teorema Central do Limite  5.2. Inferência estatística  5.2.1. Teste de hipótese  5.2.2. Intervalo de confiança  5.2.3. Métodos bayesianos  5.2.4. Estimativa de máxima verossimilhança  5.3. Processos estocásticos  5.3.1. Cadeias de Markov  5.3.2. Movimento Browniano  5.3.3. Compreendendo os processos de Poisson  5.3.4. Martingales: Um estudo abrangente em probabilidade e estatística
  6. Análise numérica  6.1. Soluções numéricas de equações  6.1.1. Descoberta original  6.1.2. Métodos iterativos  6.1.3. Análise de convergência  6.1.4. Limites de erro em soluções numéricas de equações  6.2. Álgebra linear numérica  6.2.1. Fatoração de matrizes  6.2.2. Cálculo de autovalores  6.2.3. Matrizes esparsas  6.2.4. Técnicas de pré-condicionamento  6.3. Integração e diferenciação numéricas  6.3.1. Métodos de quadratura  6.3.2. Introdução às diferenças finitas  6.3.3. Análise de erro na integração e diferenciação numérica  6.3.4. Métodos adaptativos em integração e diferenciação numérica
  7. Análise complexa  7.1. Números complexos  7.1.1. Forma polar  7.1.2. Conjugados Complexos  7.1.3. Forma exponencial de números complexos  7.1.4. Raízes da unidade  7.2. Funções analíticas  7.2.1. Equações de Cauchy–Riemann  7.2.2. Séries de potências  7.2.3. Mapeamento conforme  7.2.4. Funções harmônicas  7.3. Integração no plano complexo  7.3.1. Teorema de Cauchy  7.3.2. Teorema do resíduo  7.3.3. Integração de contorno  7.3.4. Transformadas integrais
  8. Lógica Matemática e Fundamentos  8.1. Lógica proposicional  8.1.1. Tabelas de verdade  8.1.2. Equivalência lógica na lógica proposicional  8.1.3. Técnicas de prova em lógica proposicional  8.1.4. Solução na lógica proposicional  8.2. Lógica de predicados  8.2.1. Quantificadores na lógica de predicados  8.2.2. Sistemas formais na lógica de predicados  8.2.3. Completude e correção  8.2.4. Teoria dos modelos  8.3. Teoria dos conjuntos  8.3.1. Cardinalidade e ordinalidade  8.3.2. Sistemas axiomáticos  8.3.3. Compreendendo a teoria dos conjuntos de Zermelo-Fraenkel  8.3.4. Forças na teoria dos conjuntos
  9. Personalização  9.1. Programação linear  9.1.1. Método simplex  9.1.2. Dualidade na programação linear  9.1.3. Análise de sensibilidade em programação linear  9.1.4. Métodos de ponto interior  9.2. Programação não linear  9.2.1. Descida do Gradiente  9.2.2. Múltiplos de Lagrange  9.2.3. Otimização convexa  9.2.4. Programação quadrática  9.3. Otimização Combinatória  9.3.1. Algoritmos de grafos  9.3.2. Programação inteira  9.3.3. Fluxo de Rede  9.3.4. Algoritmos de aproximação
  10. Matemática discreta  10.1. Teoria dos grafos  10.1.1. Representação de grafos  10.1.2. Planicidade e cor  10.1.3. Algoritmo de caminho mais curto  10.1.4. Fluxo de rede  10.2. Companheirismo  10.2.1. Percmutações e combinações  10.2.2. Função geradora  10.2.3. Relação de recorrência  10.2.4. Compreendendo o Princípio da Inclusão-Exclusão  10.3. Criptografia  10.3.1. Aplicações da teoria dos números na criptografia  10.3.2. Criptografia Simétrica e Assimétrica  10.3.3. RSA e criptografia de curva elíptica  10.3.4. Criptografia pós-quântica

Pós-graduação → Personalização → Otimização Combinatória ↓


Programação inteira


Programação inteira é um ramo da otimização matemática ou programação matemática. Neste contexto, "otimização" significa selecionar o melhor elemento de um conjunto dado de alternativas disponíveis, com respeito a algum critério. A programação inteira lida especificamente com problemas de otimização onde algumas ou todas as variáveis são restritas a serem inteiros.

Tipos de programação inteira

  • Programação inteira pura (PIP): Todas as variáveis de decisão são obrigadas a assumir valores inteiros.
  • Programação inteira mista (PIM): Apenas algumas das variáveis são obrigadas a serem inteiros, enquanto outras podem ser não inteiros.
  • Programação inteira binária: Caso especial de programação inteira onde as variáveis são limitadas a 0 ou 1. É frequentemente usada para decisões de sim/não.

Importância na otimização combinatória

Muitos problemas em otimização combinatória podem ser formulados como problemas de programação inteira. A otimização combinatória foca em objetos que são discretos ou que podem ser contados. Já que valores inteiros são discretos, a programação inteira é a melhor maneira de resolver tais problemas e torna-se importante em solucioná-los.

Formulação de problema de programação inteira

O problema de programação inteira é geralmente formulado da seguinte forma:

 
Maximizar (ou Minimizar): c 1 x 1 + c 2 x 2 + ... + c n x n 
Sujeito a: 
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1 
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2 
... 
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m 
Onde: x 1 , x 2 , ..., x n são inteiros

Aqui, c i denota os coeficientes da função objetivo que você quer maximizar ou minimizar, a ij denota os coeficientes das restrições, e b i denota os limites das restrições.

Exemplo: o problema da mochila

Consideremos um exemplo clássico de programação inteira: o problema da mochila. O objetivo é maximizar o valor total dos itens colocados na mochila, sem exceder sua capacidade de carga.

Exemplo de um problema de mochila:

  • Itens: 4 itens com pesos w = [2, 3, 4, 5] e valores v = [3, 4, 5, 6]
  • Capacidade: Esta bolsa pode carregar o peso de no máximo 5 pessoas.

Formular o problema da mochila usando programação inteira:

 
Maximizar: 3x 1 + 4x 2 + 5x 3 + 6x 4 
Sujeito a: 2x 1 + 3x 2 + 4x 3 + 5x 4 ≤ 5 
Onde: x 1 , x 2 , x 3 , x 4 ∈ {0, 1}

A restrição x i ∈ {0, 1} assegura que cada item possa ser incluído na bolsa ou não.

Representação visual

5 (peso) 4 (peso) 3 (peso) 2 (peso)

Esta visualização mostra um modelo simplificado de uma bolsa com o peso embalado em ordem decrescente.

Resolvendo problemas de programação inteira

Problemas de programação inteira são geralmente NP-difíceis, o que significa que não há algoritmos conhecidos capazes de resolver todos esses problemas de forma eficiente (em tempo polinomial). No entanto, várias abordagens podem ser adotadas para resolver problemas específicos.

1. Método de branch and bound

Este é um método amplamente utilizado para resolver problemas de programação inteira. A ideia básica é dividir o problema em subproblemas menores (ramos) e encontrar a solução ótima avaliando os limites desses subproblemas enquanto os subproblemas devem ser sistematicamente eliminados se seus limites indicarem que não podem conter uma solução melhor (limite).

2. Método do plano de corte

Este método melhora o relaxamento linear do problema de programação inteira inserindo iterativamente restrições lineares (planos de corte) no problema, com o objetivo de filtrar regiões do espaço da solução que não possuem soluções inteiras.

Aplicações práticas da programação inteira

  • Alocação de recursos: alocação de recursos limitados entre atividades concorrentes.
  • Programação: Alocação de períodos de tempo para tarefas, tais como cronogramas de trabalho, cronogramas de transporte, etc.
  • Design de rede: design de caminhos de rede, especificação de largura de banda, etc.
  • Planejamento da produção: Planejamento de atividades de produção, como a quantidade de produtos a serem produzidos.

Problema exemplo: programação de tarefas

Considere um conjunto de algumas tarefas, cada uma das quais possui um tempo de processamento específico e uma data limite. O objetivo é programar as tarefas de forma que a latência total seja minimizada, o que é a quantidade pela qual as tarefas são atrasadas para completar e demorar mais do que a data limite.

Exemplo:

  • Jobs: Trabalho 1, Trabalho 2, Trabalho 3, tempos de processamento 2, 4, 3 e prazos 2, 6, 5 respectivamente.

Formular este problema de programação usando programação inteira:

 
Minimizar: T 1 + T 2 + T 3
Sujeito a: 
x 1,1 + x 1,2 + x 1,3 = 1 
x 2,1 + x 2,2 + x 2,3 = 1 
x 3,1 + x 3,2 + x 3,3 = 1 
Restrições de Conclusão: 
C 1 = 2x 1,1 + 4x 2,1 + 3x 3,1 
C 2 = C 1 + 2x 1,2 + 4x 2,2 + 3x 3,2 
C 3 = C 2 + 2x 1,3 + 4x 2,3 + 3x 3,3 
Onde: 
T i = max(0, C i - prazo i ) 
x i,j ∈ {0, 1}

Vantagens da programação inteira

A programação inteira fornece uma estrutura poderosa para resolver muitos problemas complexos de tomada de decisão, devido à sua capacidade de modelar requisitos lógicos dentro de problemas de otimização. Isto é particularmente benéfico quando:

  • As decisões podem ser naturalmente representadas em termos de ligado/desligado (por exemplo, investir ou não).
  • Sua solução deve aderir a restrições lógicas rigorosas.
  • Você terá que resolver problemas onde algumas das variáveis requerem valores diferentes.

Conclusão

A programação inteira desempenha um papel vital não apenas no amplo campo da otimização, mas também em muitas aplicações práticas em diversas indústrias. Apesar de sua complexidade e intensidade computacional, existem estratégias e heurísticas eficazes que podem ser usadas para obter soluções viáveis para problemas do mundo real. À medida que o poder computacional continua a aumentar, a programação inteira está se tornando mais útil e difundida no gerenciamento de desafios complexos de tomada de decisão.


Pós-graduação → 9.3.2


U
username
0%
concluído em Pós-graduação

← Anterior (9.3.1)
Algoritmos de grafos
Próximo (9.3.3) →
Fluxo de Rede

Comentários 



Programação inteira

https://www.buddymath.com/g/9.3.2?bmal=pt