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 ↓


Método simplex


O método simplex é um algoritmo usado para resolver problemas de programação linear, que envolve encontrar o valor máximo ou mínimo de uma função linear sujeita a restrições lineares. A programação linear é uma importante ferramenta de otimização em várias áreas, como economia, engenharia, militar, negócios e ciência.

Introdução à programação linear

A programação linear envolve um conjunto de equações e desigualdades que representam um modelo matemático cujo objetivo óptimo é procurado. Para um problema de programação linear, o objetivo é otimizar (maximizar ou minimizar) uma função objetivo linear sujeita a restrições de igualdade e/ou desigualdade lineares. A forma geral de um problema de programação linear é dada como:

Máximo (ou mínimo): 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

O que é o método simplex?

O método simplex é um procedimento iterativo que examina sistematicamente os pontos de canto (ou vértices) da região viável para encontrar o valor ótimo da função objetivo. Esse procedimento envolve mover-se de um vértice para outro, melhorando o valor da função objetivo a cada passo, até que o melhor valor possível seja alcançado.

Procedimento do método simplex

  1. Converta o problema para a forma padrão.
  2. Identifique uma solução inicial viável.
  3. Continue trabalhando para encontrar uma solução melhor até que não seja possível mais melhorias.
  4. Avalie e interprete a solução.

Passo 1: Convertendo para a forma padrão

Para aplicar o método simplex, o problema de programação linear deve ser transformado na forma padrão. Isso envolve:

  • Garantir que todas as restrições estejam na forma de equações lineares.
  • Introduzir variáveis de folga para converter desigualdades em igualdades.
  • Garantir que todas as variáveis sejam não negativas.

Considere o seguinte exemplo:

Máximo: 3x 1 + 5x 2

sujeito a:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12

x 1 , x 2 ≥ 0

Introdução às variáveis de folga:

x 1 + 2x 2 + s 1 = 8
3x 1 + 2x 2 + s 2 = 12

x 1 , x 2 , s 1 , s 2 ≥ 0

As variáveis de folga s 1 e s 2 representam recursos não utilizados das restrições.

Passo 2: Identifique a solução inicial

Ao definir as variáveis de decisão (aqui, x 1 e x 2) iguais a zero, enquanto se permite que as variáveis de folga sejam iguais aos valores das restrições, uma solução básica inicial viável é identificada.

Em nosso exemplo, a solução inicial é:

x 1 = 0, x 2 = 0, s 1 = 8, s 2 = 12

Passo 3: Itere para melhorar a solução

Para realizar a recursão, uma tabela é criada. A linha objetiva contém os coeficientes negativos da função objetivo. A recursão envolve:

  • O objetivo é selecionar a variável de entrada com coeficiente mais negativo na linha.
  • Selecionar variáveis de queda usando o teste de proporção mínima.
  • Pivoteamento para atualizar a solução.
Tabela inicial:
| base | x 1 | x 2 | s 1 | s 2 | lado direito |
| S 1 | 1 | 2 | 1 | 0 | 8 |
| S 2 | 3 | 2 | 0 | 1 | 12 |
| z | -3 | -5 | 0 | 0 | 0 |

Iteração 1:

A variável de entrada é x 2 (coeficiente mais negativo na linha z: -5 ).

Para proporção mínima: RHS / Coeficiente de x 2 = min(8/2, 12/2) = 4, portanto s 1 é a variável de queda.

Pivote para substituir s 1 por x 2.

Tabela Pivoteada:
| base | x 1 | x 2 | s 1 | s 2 | lado direito |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| S2 | 2.0 | 0 | -1 | 1 | 4 |
| z | -0.5 | 0 | 2.5 | 0 | 20 |

Iteração 2:

O coeficiente mais negativo na nova linha z é -0.5 (para x 1 ).

Usando proporção mínima: RHS / Coeficiente de x 1 = min(4/0.5, 4/2) = 2, portanto s 2 é a variável de queda.

Pivote para substituir s 2 por x 1.

Tabela Pivoteada:
| base | x 1 | x 2 | s 1 | s 2 | lado direito |
| x 2 | 0.5 | 1 | 0.5 | 0 | 4 |
| x1 | 1 | 0 | -0.5 | 0.5 | 2 |
| Z | 0 | 0 | 3 | 0.5 | 22 |

O valor da função objetivo melhorou para 22, e não há mais coeficientes negativos, então a solução atual é ótima.

Exemplo visual

A região sombreada no gráfico representa a região viável onde todas as restrições se sobrepõem. O círculo marca o ponto de solução ótima onde o valor máximo da função objetivo é alcançado.

Passo 4: Avaliar e interpretar a solução

O método simplex fornece os melhores valores possíveis para as variáveis de decisão dentro da região viável. Da tabela final, podemos determinar a solução ótima:

x 1 = 2, x 2 = 4

Valor da função objetivo: 22

Isso significa que o valor máximo da função objetivo 3x 1 + 5x 2 é 22 quando x 1 = 2 e x 2 = 4.

Propriedades do método simplex

  • O método simplex se move ao longo da borda da região viável, garantindo que a solução melhore ou permaneça a mesma a cada passo até que a solução ótima seja encontrada.
  • Lida de forma eficiente com funções objetivo lineares com restrições, tornando-o adequado para problemas de programação linear em larga escala.
  • Embora o método geralmente comece do zero, algum pré-processamento ainda é necessário para converter qualquer problema em uma forma padrão.
  • O algoritmo é finito; ele converge para a solução ótima ou reconhece que nenhuma solução existe para as restrições dadas.

Benefícios e limitações

As vantagens do método simplex incluem sua capacidade de fornecer soluções ótimas exatas para problemas de programação linear e sua aplicabilidade a uma ampla gama de problemas além de apenas restrições do tipo ≤. No entanto, este método tem algumas limitações:

Benefício

  • Fornece solução precisa.
  • Pode lidar com problemas complexos de forma eficiente.
  • É amplamente compreendido e usado, e existem muitas bibliotecas e softwares para suportá-lo.

Limitações

  • Pode ser computacionalmente caro em conjuntos de dados muito grandes.
  • Não funciona diretamente com problemas não-lineares.
  • Ciclagem pode ser problemática (às vezes, mas isso pode ser resolvido com estratégias anti-ciclagem).

Conclusão

O método simplex continua sendo uma ferramenta poderosa para otimização, especialmente na área de pesquisa operacional. Ele oferece uma abordagem estruturada para encontrar soluções ótimas para problemas que requerem maximização ou minimização com restrições lineares. Compreender tanto suas forças quanto suas limitações permite que os profissionais apliquem efetivamente este método para resolver problemas do mundo real com confiabilidade e precisão.


Pós-graduação → 9.1.1


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

← Anterior (9.1)
Programação linear
Próximo (9.1.2) →
Dualidade na programação linear

Comentários 



Método simplex

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