Graduação
  1. Álgebra  1.1. Álgebra linear  1.1.1. Matrizes  1.1.2. Determinantes  1.1.3. Sistemas de equações lineares  1.1.4. Compreendendo espaços vetoriais na álgebra linear  1.1.5. Transformações lineares  1.1.6. Autovalores e autovetores  1.1.7. Diagonalização  1.1.8. Espaço de produto interno  1.1.9. Ortogonalidade e base ortonormal  1.1.10. Decomposição em valores singulares  1.2. Álgebra abstrata  1.2.1. Grupo  1.2.2. Subgrupos  1.2.3. Grupos cíclicos  1.2.4. Grupo de Permutações  1.2.5. Homeomorfismo  1.2.6. Subgrupos normais  1.2.7. Introdução aos anéis na álgebra abstrata  1.2.8. Campo  1.2.9. Ideais e anéis quocientes  1.2.10. Anéis de polinômios  1.2.11. Espaço vetorial sobre um campo  1.2.12. Módulo  1.2.13. Introdução à teoria de Galois
  2. Cálculos  2.1. Cálculo diferencial  2.1.1. Compreendendo limites no cálculo diferencial  2.1.2. Compreendendo o contínuo no cálculo diferencial  2.1.3. Derivadas  2.1.4. Compreendendo a regra da cadeia no cálculo diferencial  2.1.5. Diferenciação implícita  2.1.6. Aplicações das derivadas  2.1.7. Problemas de otimização  2.1.8. Entendendo o teorema do valor médio  2.2. Cálculo integral  2.2.1. Integral definida  2.2.2. Integral indefinida  2.2.3. Técnicas de integração  2.2.4. Integrais impróprias  2.2.5. Aplicações da integração  2.2.6. Comprimento de arco e área de superfície  2.3. Cálculo Multivariável  2.3.1. Derivada parcial  2.3.2. Gradiente em cálculo multivariável  2.3.3. Divergência e rotacional  2.3.4. Introdução à integração múltipla  2.3.5. Compreendendo integrais de linha  2.3.6. Integrais de superfície  2.3.7. Explicação do teorema de Green  2.3.8. Teorema de Stokes  2.3.9. Teorema da divergência  2.3.10. Jacobian
  3. Equações diferenciais  3.1. Equação diferencial ordinária  3.1.1. Equações diferenciais de primeira ordem  3.1.2. Equações diferenciais de ordem superior  3.1.3. Sistemas de equações diferenciais  3.1.4. Solução por séries  3.1.5. Métodos numéricos para EDOs  3.2. Equações diferenciais parciais  3.2.1. Compreendendo a equação do calor  3.2.2. Equação da onda  3.2.3. Equação de Laplace  3.2.4. Separação de variáveis  3.2.5. Métodos de transformação de Fourier em equações diferenciais parciais
  4. Análise Real  4.1. Sequências e séries  4.1.1. Convergência de sequências  4.1.2. Teste de Séries  4.1.3. Séries de potência  4.1.4. Convergência uniforme  4.2. Funções de variáveis reais  4.2.1. Limites e continuidade  4.2.2. Compreendendo a continuidade uniforme  4.2.3. Diferenciação de funções de variáveis reais  4.2.4. Integração de Riemann  4.2.5. Integração de Lebesgue
  5. Introdução à Análise Complexa  5.1. Números complexos  5.1.1. Forma polar  5.1.2. Forma exponencial em números complexos  5.2. Funções de uma variável complexa  5.2.1. Funções Analíticas  5.2.2. Equações de Cauchy-Riemann  5.2.3. Integrais de contorno  5.2.4. Teorema de integração de Cauchy  5.2.5. Teorema de Resíduos na Análise Complexa  5.2.6. Mapeamento Conformal
  6. Probabilidade e estatística  6.1. Teoria da Probabilidade  6.1.1. Conceitos Básicos de Probabilidade  6.1.2. Variáveis aleatórias  6.1.3. Compreendendo Distribuições de Probabilidade  6.1.4. Expectativa e variação  6.1.5. Probabilidade condicional e o teorema de Bayes  6.2. Figuras  6.2.1. Estatísticas descritivas  6.2.2. Estatística inferencial  6.2.3. Teste de hipótese  6.2.4. Análise de regressão  6.2.5. Compreendendo a ANOVA: Análise de Variância
  7. Métodos numéricos  7.1. Algoritmo de busca de raízes  7.2. Integração numérica  7.3. Diferenciação numérica  7.4. Soluções numéricas de equações diferenciais  7.5. Cálculos com matrizes  7.6. Interpolação e extrapolação
  8. Introdução à Matemática Discreta  8.1. Argumentos e provas  8.2. Companheirismo  8.3. Teoria dos grafos  8.4. Álgebra booleana  8.5. Relação de recorrência
  9. Programação Linear e Otimização  9.1. Entendendo o método simplex em programação linear e otimização  9.2. Dualidade em programação linear e otimização  9.3. Programação inteira  9.4. Otimização não linear
  10. Compreendendo topologia: uma jornada através de formas e espaços  10.1. Espaço métrico  10.2. Espaços topológicos  10.3. Continuidade e homeomorfismos  10.4. Densidade  10.5. Associatividade em topologia
  11. Introdução à Geometria  11.1. Geometria euclidiana  11.2. Geometria diferencial  11.3. Geometria não euclidiana  11.4. Geometria projetiva
  12. Física matemática  12.1. Séries de Fourier  12.2. Transformada de Laplace  12.3. Aplicações de equações diferenciais  12.4. Funções especiais
  13. Teoria dos conjuntos e lógica  13.1. Conjuntos e subconjuntos  13.2. Relações e funções  13.3. Compreendendo a cardinalidade na teoria dos conjuntos e na lógica  13.4. Compreendendo a lógica formal em teoria dos conjuntos e lógica  13.5. Teoria dos conjuntos de Zermelo–Fraenkel
  14. Introdução à análise funcional  14.1. Localização padrão  14.2. Espaços de Banach  14.3. Compreensão do espaço de Hilbert na análise funcional  14.4. Operadores lineares

Graduação → Programação Linear e Otimização ↓


Programação inteira


A programação inteira é um ramo da otimização ou programação matemática. Significa encontrar a melhor solução a partir de um conjunto de soluções possíveis. Enquanto a programação linear lida com equações lineares e algumas restrições, a programação inteira é um tipo especial onde as variáveis de solução devem ser inteiros. Essa restrição torna a programação inteira mais complexa e desafiadora, mas também mais aplicável em cenários reais onde alguns recursos podem ser apenas unidades inteiras.

O que é programação inteira?

A programação inteira envolve problemas matemáticos que visam otimizar uma função objetivo dada. À primeira vista, pode parecer programação linear, mas há uma diferença importante: na programação inteira, a probabilidade de uma função ser otimizada é constante, a menos que algumas ou todas as variáveis sejam inteiros. são limitados apenas.

A programação inteira pode ser usada para resolver uma variedade de problemas de otimização. Alguns exemplos incluem planejamento e programação, alocação de recursos e tomada de decisões em indústrias como logística, manufatura, telecomunicações e finanças.

Formulação matemática

A forma geral de um problema de programação linear pode ser expressa da seguinte forma:

Max ou Min: c1*x1 + c2*x2 + ... + cn*xn

sujeito a:

a11*x1 + a12*x2 + ... + a1n*xn (<=, = ou >=) b1
a21*x1 + a22*x2 + ... + a2n*xn (<=, = ou >=) b2
,
am1*x1 + am2*x2 + ... + amn*xn (<=, = ou >=) bm

x1, x2, ..., xn >= 0

Aqui, c denota os coeficientes da função objetivo, a denota os coeficientes das restrições e b denota as constantes do lado direito. O objetivo é encontrar os valores de x1, x2, ..., xn que maximizem ou minimizem a função objetivo. Faça o mínimo.

Na programação inteira, uma ou mais das variáveis x1, x2, ..., xn são restringidas a assumir apenas valores inteiros. Quando todas as variáveis são restringidas a serem inteiros, o problema é denominado problema de programação inteira pura. Quando apenas algumas das variáveis são inteiros, trata-se de um problema de programação inteira mista.

Exemplo

Problema simples de programação inteira

Vamos analisar um exemplo simples de programação inteira para entender esses conceitos. Suponha que uma empresa queira decidir qual é o número ideal de produtos A e B a serem produzidos. O lucro de uma unidade do produto A é de $3 e de $5 do produto B. A empresa não pode produzir mais de 7 unidades de A e 4 unidades do produto B em conjunto.

O modelo de programação inteira pode ser configurado da seguinte forma:

Max: 3A+5B

sujeito a:

a + b <= 7
b <= 4
A, B >= 0 e inteiro

Aqui, tanto A quanto B devem ser inteiros porque a empresa não pode fabricar uma fração de um produto. Este requisito é onde a programação inteira se torna mais complexa do que a simples programação linear.

Visualização das soluções inteiras

Para nosso exemplo, vamos visualizar a região viável e a solução. Considere as restrições plotadas no gráfico marcando especialmente os inteiros:

A B 2,4 3,4 4,3

No exemplo de SVG, a linha A + B = 7 e a linha B = 4 são esboçadas com pontos inteiros. Estes pontos têm (2,4), (3,4) e (4,3) estão incluídos.

Como nosso objetivo é maximizar nossa função objetivo 3A + 5B para os pontos de solução (3,4) e (4,3), os valores objetivos são:

  • Para o ponto (3,4): 3 * 3 + 5 * 4 = 9 + 20 = 29
  • Para o ponto (4,3): 3 * 4 + 5 * 3 = 12 + 15 = 27

Assim, o lucro máximo é obtido em (3,4), produzindo 3 unidades de A e 4 unidades de B.

Desafios na programação inteira

A programação inteira possui dificuldades inerentes que a programação linear geral não possui. Os problemas de programação linear podem ser resolvidos usando métodos como o algoritmo simplex, que navega eficientemente em regiões viáveis.

No entanto, adicionar restrições inteiras complica a busca por uma solução. Como os espaços matemáticos envolvidos na programação inteira não são formas convexas agradáveis, algoritmos especiais são necessários para visualização e cálculo, como:

  • Branch-and-bound: divide repetidamente o problema em subproblemas ("ramos"), encontra regiões viáveis e resolve programas lineares mais fáceis.
  • Figura de corte: Esta é uma adição ao relaxamento padrão da programação linear. Adiciona restrições para criar uma região viável mostrando apenas soluções inteiras.
  • Branch-and-Cut: Combina os métodos acima, proporcionando eficiência e maior praticidade na resolução de programas inteiros e inteiros mistos.

Aplicações de programação inteira

Devido à sua natureza, a programação inteira encontra amplas aplicações em várias áreas. Essas funções resolvem problemas em vez de explorar partes teóricas.

A seguir estão algumas das principais áreas de aplicação:

  • Fabricação: contratação, utilização de máquinas, mistura e distribuição.
  • Telecomunicações: Alocação de largura de banda, design de rede e roteamento.
  • Logística: gestão de inventário, roteirização de veículos e programação de pessoal.
  • Finanças: Seleção de portfólio e orçamento de capital.

Cada área faz uso de fatores que favorecem a programação inteira, como a natureza discreta e a otimização de escolhas explícitas entre possibilidades finitas.

Conclusão

A programação inteira serve como um recurso chave no campo da otimização. Sua funcionalidade acrescenta à praticidade, pois as restrições frequentemente vistas na realidade são naturalmente tratadas por suas soluções discretas. Sendo complexa na natureza e no cálculo, a programação inteira é um processo muito simples e caro. Independentemente disso, os métodos existentes tornam-no viável e amplamente aplicável. O potencial de otimização continua a crescer em adoção à medida que as indústrias avançam, impulsionadas em parte pelos avanços e pelo entendimento da programação inteira.


Graduação → 9.3


U
username
0%
concluído em Graduação

← Anterior (9.2)
Dualidade em programação linear e otimização
Próximo (9.4) →
Otimização não linear

Comentários 



Programação inteira

https://www.buddymath.com/ug/9.3?bmal=pt