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 → Programação linear ↓


Dualidade na programação linear


A programação linear (PL) é um método para alcançar os melhores resultados em modelos matemáticos cujos requisitos são representados por relações lineares. É uma técnica usada para otimização, onde se procura minimizar ou maximizar uma função objetiva linear sujeita a um conjunto de restrições lineares. Um aspecto essencial da programação linear é o conceito de dualidade, que fornece um entendimento profundo sobre o comportamento das funções de otimização.

Fundamentos do dualismo

Na programação linear, para cada problema de otimização, há um problema dual correspondente. Se o problema original é chamado de 'problema primal', seu contraponto é conhecido como 'problema dual'. A dualidade fornece um poderoso insight - a solução ótima de um problema pode ser encontrada examinando-se a solução do outro.

Existem dois resultados principais sobre a dualidade na programação linear:

  • Dualidade fraca: O valor da função objetiva da dualidade em qualquer solução viável é sempre maior ou igual ao valor da função objetiva do original em qualquer solução viável.
  • Dualidade forte: Se tanto um primitivo quanto uma dualidade têm soluções ótimas, então o valor ótimo da função objetiva do primitivo é igual ao da dualidade.

Problema primal e dualidade

Problema primário

Maximizar: 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

             x 1 , x 2 , ..., x n ≥ 0

Problema dual

Minimizar: b 1 y 1 + b 2 y 2 + ... + b m y m
Sujeito a: a 11 y 1 + a 21 y 2 + ... + a m1 y m ≥ c 1
             a 12 y 1 + a 22 y 2 + ... + a m2 y m ≥ c 2
             ,
             a 1n y 1 + a 2n y 2 + ... + a mn y m ≥ c n

             y 1 , y 2 , ..., y m ≥ 0

Interpretação e significado econômico

No problema primário, o objetivo é determinar o benefício máximo (ou lucro) que pode ser obtido enquanto satisfaz as restrições impostas pelas limitações de recursos. Cada variável de decisão representa uma atividade ou estratégia possível, e as restrições representam os limites dos recursos necessários para essas atividades.

O problema de dualidade, por outro lado, busca o custo mínimo necessário para atingir ou superar um nível desejado de lucro total. Aqui, as variáveis de decisão podem ser interpretadas como preços sombra - o preço de minimizar cada restrição no problema de otimização primário. A dualidade fornece um tipo de sistema de preços de equilíbrio.

Interpretação geométrica

Considere um espaço bidimensional para uma visualização mais fácil. Para ambos os problemas primário e dual, as soluções encontram-se nos vértices (cantos) de suas regiões viáveis. As desigualdades primárias e duais correspondentes definem regiões geométricas, e sua interseção pode potencialmente conter a solução ótima para ambos os problemas primário e dual.


    
    
    
    
    X
    Y
    Obstáculo 1
    Obstáculo 2

O princípio da letargia complementar

Um componente integral que conecta as formulações primal e dual é o conceito de frouxidão complementar. Consiste nas condições que devem ser atendidas se ambos o primal e seu dual tiverem soluções ótimas. Para cada par de restrições primal e dual, as condições de frouxidão complementar devem ser atendidas:

Se x j > 0, então as condições de dualidade j th são estritas;
Se a restrição binária i for relaxada, então o fundamento variável é zero.

Assim, se qualquer restrição no problema original for relaxada, então a variável correspondente na dualidade deve ter valor zero na otimalidade, e vice-versa.

Exemplo de dualismo

Problema elementar de exemplo

Maximizar z = 2x 1 + 3x 2
sujeito a
             x 1 + 2x 2 ≤ 10
             2x 1 + x 2 ≤ 8
             x 1 , x 2 ≥ 0

Problema dual compatível

Minimizar w = 10y 1 + 8y 2
sujeito a
             y 1 + 2y 2 ≥ 2
             2y 1 + y 2 ≥ 3
             y 1 , y 2 ≥ 0

Aplicações e importância

O conceito de dualidade não é apenas teórico, mas também tem importantes implicações práticas. Ele nos permite derivar a solução de um problema a partir da solução de outro, potencialmente mais simples. A dualidade é usada em uma variedade de campos, como economia, engenharia, ciência militar e transporte.

Por exemplo, na economia, o problema dual fornece informações sobre otimização de preços e alocação de recursos. As soluções duais indicam que valor deve ser atribuído aos recursos adicionais, fornecendo informações valiosas de precificação para os tomadores de decisão.

Conclusão

A dualidade na programação linear preenche a lacuna entre diferentes abordagens de otimização, permitindo uma compreensão mais profunda e eficiência na resolução de problemas complexos. Seja por interesse acadêmico ou por soluções práticas, é importante entender o conceito de dualidade para aproveitar ao máximo as técnicas de programação linear.


Pós-graduação → 9.1.2


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

← Anterior (9.1.1)
Método simplex
Próximo (9.1.3) →
Análise de sensibilidade em programação linear

Comentários 



Dualidade na programação linear

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