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 ↓


Entendendo o método simplex em programação linear e otimização


Introdução à programação linear

A programação linear é uma técnica matemática para otimizar uma função objetivo linear, sujeita a restrições de igualdade e desigualdade lineares. É uma maneira de alcançar o melhor resultado em um modelo matemático cujos requisitos são representados por relações lineares. Esse tipo de otimização é importante em vários campos, como economia, engenharia, militar e planejamento empresarial.

Função objetivo e restrições

Na programação linear, nosso objetivo é maximizar ou minimizar uma função objetivo linear. Um problema geral de programação linear pode ser expresso como:

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

Aqui, x 1 , x 2 , ..., x n são variáveis, c 1 , c 2 , ..., c n são os coeficientes da função objetivo, a ij são os coeficientes das restrições, e b i são constantes nas equações de restrição.

O método simplex: uma visão geral

O método simplex é um algoritmo popular usado para resolver problemas de programação linear. Ele foi desenvolvido por George Dantzig em 1947. Este método consiste nas seguintes etapas principais:

  • Converter um problema de programação linear para a forma padrão.
  • Encontrar uma solução viável inicial.
  • Trabalhar iterativamente para melhorar a função objetivo até que a solução ótima seja alcançada.

Convertendo para a forma padrão

Antes de aplicar o método simplex, é necessário transformar o problema de programação linear dado na forma padrão. Isso envolve garantir que todas as restrições estejam na forma de igualdade e adicionar afrouxamentos, superposições ou variáveis artificiais, se necessário.

Suponha que tenhamos uma restrição como: 
a 11 x 1 + a 12 x 2 ≤ b 1

Para transformá-la em igualdade, introduzimos uma variável de folga s 1 :

a 11 x 1 + a 12 x 2 + s 1 = b 1

Encontrando a solução viável inicial

Uma vez que o problema esteja na forma padrão, é necessário encontrar uma solução básica viável. Isso envolve definir as variáveis não básicas como zero e resolver o sistema de equações para encontrar os valores das variáveis básicas.

Processo iterativo

O objetivo básico do método simplex é melhorar o valor da função objetivo processando através das soluções viáveis para identificar a solução ótima. Isso é feito por pivotamento.

Exemplo

Vamos ver um exemplo visual de um problema de programação linear. Suponha que temos o seguinte problema:

Maximizar: Z = 3x 1 + 5x 2
sujeito a:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12
x 1 , x 2 ≥ 0
x 1 x 2 x 1 + 2x 2 = 8 3x1 + 2x2 = 12

No exemplo acima, as restrições x 1 + 2x 2 = 8 e 3x 1 + 2x 2 = 12 são desenhadas como linhas. A região viável delimitada pelo polígono verde mostra onde todas as condições são atendidas.

Pivotamento no método simplex

Para melhorar a função objetivo, escolheremos elementos de pivô. Critérios de entrada e critérios de saída ajudam a identificar qual variável entra na base e qual sai. O pivotamento modifica nossa base para que ela se mova para uma solução viável adjacente com um valor mais alto (em caso de maximização) para a função objetivo.

Passos envolvidos no pivotamento

O processo de pivotamento inclui as seguintes etapas principais:

  1. Identificar a variável de entrada:
    • Olhe para a linha do objetivo (também chamada de linha de custo) no tableau simplex. Escolha a variável cujo coeficiente é mais positivo (para problemas de maximização). Esta é nossa variável de entrada.
  2. Determinar a variável de saída:
    • Para encontrar a variável de saída, calcule a razão mínima do lado direito para os coeficientes positivos da variável de entrada em cada linha de restrição.
  3. Realizar operações de linha:
    • Ajuste a tabela para refletir essa nova base. Isso envolve a operação de linha do elemento pivô para definir os outros elementos na coluna da variável de entrada como zero.

Continuação do exemplo

Vamos aplicar essas etapas ao nosso exemplo anterior.

Tableau simplex para a base inicial

A tabela inicial para converter desigualdades em igualdades é configurada com variáveis relaxadas s 1 e s 2 para cada restrição:

| x 1 | x 2 | s 1 | s 2 | lado direito | 
,
, 1 | 2 | 1 | 0 | 8 |
, 3 | 2 | 0 | 1 | 12 |
,
, -3 | -5 | 0 | 0 | 0 |

Vamos identificar as variáveis de entrada e saída:

Para maximização, o coeficiente mais negativo na linha do objetivo é -5 (sob x 2 ). Isso significa que x 2 é nossa variável de entrada.

Para encontrar a variável de saída, calculamos a razão do RHS para o coeficiente positivo de x 2 :

8/2 = 4 (para a primeira linha)
12/2 = 6 (para a segunda linha)
A razão mínima é 4, o que indica que a primeira linha sairá.

Realize operações de linha para criar a variável original x 2 na primeira linha.

Atualize o restante da tabela adequadamente.

Solução ótima

Continue com etapas de pivotamento semelhantes até que não haja coeficientes negativos na linha do objetivo (para maximização), indicando que a solução ótima foi encontrada.

Conclusão

O método simplex é um algoritmo eficiente que funciona iterando pelos vértices da região viável de maneira sistemática. É particularmente eficiente para problemas lineares envolvendo um grande número de variáveis e restrições, comprovando sua utilidade tanto em matemática teórica quanto em cenários práticos de tomada de decisão. Com uma implementação cuidadosa e compreensão de cada etapa, os alunos podem efetivamente aproveitar o poder do método simplex para encontrar soluções ótimas para problemas complexos.


Graduação → 9.1


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

← Anterior (9)
Programação Linear e Otimização
Próximo (9.2) →
Dualidade em programação linear e otimização

Comentários 



Entendendo o método simplex em programação linear e otimização

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