Boas-vindas!

Olá a todos! Sejam bem-vindos à aula sobre o Método Simplex.

Objetivos de Aprendizagem

Ao final desta aula, você será capaz de:

• Formular problemas de Programação Linear (PL) na forma padrão.
• Identificar soluções básicas viáveis.
• Aplicar o algoritmo Simplex para resolver problemas de maximização e minimização.
• Interpretar a solução ótima e suas implicações gerenciais.

O que é Programação Linear (PL)?

• Técnica matemática para otimizar (maximizar ou minimizar) uma função objetivo linear.
• Sujeita a um conjunto de restrições lineares (igualdades ou desigualdades).
• Variáveis de decisão não-negativas.

Componentes de um Modelo de PL

• Variáveis de Decisão: Quantidades a serem determinadas (ex: quantidade de produtos a fabricar).
• Função Objetivo (FO): Expressão linear a ser maximizada (lucro, receita) ou minimizada (custo, tempo).
• Restrições: Limitações de recursos (horas de máquina, matéria-prima, mão de obra, orçamento).
• Não-negatividade: Variáveis de decisão \(\ge 0\).

Exemplo de PL (Maximização)

Uma fábrica produz dois tipos de cadeiras: A e B.

• Cadeira A: Lucro de R$ 10, requer 2h de montagem e 1h de acabamento.
• Cadeira B: Lucro de R$ 15, requer 3h de montagem e 1h de acabamento.
• Disponibilidade: 120h de montagem e 50h de acabamento por semana.

Objetivo: Maximizar o lucro total.

Formulação Matemática

• Variáveis:
  • \(x_1\): número de cadeiras A
  • \(x_2\): número de cadeiras B
• Função Objetivo:
  • Maximizar \(Z = 10x_1 + 15x_2\)
• Restrições:
  • \(2x_1 + 3x_2 \le 120\) (Montagem)
  • \(1x_1 + 1x_2 \le 50\) (Acabamento)
  • \(x_1, x_2 \ge 0\) (Não-negatividade)

Forma Padrão do PL

Para aplicar o Simplex, o PL deve estar na forma padrão:

1. Função Objetivo: A ser maximizada. (Minimização é convertida para maximização).
2. Restrições: Todas devem ser igualdades.
3. Lados Direitos (RHS): Todos não-negativos.
4. Variáveis: Todas não-negativas.

Conversão para Forma Padrão

• Restrições \(\le\): Adicionar variáveis de folga (\(s_i \ge 0\)).
  • \(2x_1 + 3x_2 \le 120 \implies 2x_1 + 3x_2 + s_1 = 120\)
  • Variáveis de Folga representam o recurso não utilizado.
• Restrições \(\ge\): Subtrair variáveis de excesso (\(e_i \ge 0\)) e adicionar variáveis artificiais (\(a_i \ge 0\)).
  • \(x_1 + x_2 \ge 10 \implies x_1 + x_2 - e_1 + a_1 = 10\)
  • Variáveis de Excesso representam o quanto o lado esquerdo excede o direito.
  • Variáveis Artificiais são auxiliares para criar uma base inicial.
• Restrições \(=\): Adicionar variáveis artificiais (\(a_i \ge 0\)).
  • \(x_1 + x_2 = 10 \implies x_1 + x_2 + a_1 = 10\)
• Minimização: Multiplicar a FO por -1 e maximizar.
  • Min \(Z = c_1x_1 + c_2x_2 \implies\) Max \(Z' = -c_1x_1 - c_2x_2\)

Soluções Básicas Viáveis (SBV)

• Em um sistema de \(m\) equações com \(n\) variáveis (\(n > m\)):
  • Definimos \(n-m\) variáveis como não-básicas (valor 0).
  • Resolvemos para as \(m\) variáveis básicas restantes.
• Se todas as variáveis básicas forem não-negativas, a solução é uma SBV.
• O Simplex move-se de uma SBV para outra, melhorando a FO a cada passo.

O Tableau Simplex

O tableau é uma representação tabular do sistema de equações.

• Linha Z: Coeficientes da função objetivo (negativos para maximização).
• Linhas de Restrição: Coeficientes das variáveis e RHS.
• Variáveis Básicas: Variáveis com coluna de identidade (1 em sua linha, 0 nas outras).

Critérios de Entrada e Saída

1. Variável de Entrada (Coluna Pivô):
   • Escolha a variável não-básica com o coeficiente mais negativo na linha Z (para maximização).
   • Indica a variável que mais contribui para aumentar a FO.
2. Variável de Saída (Linha Pivô):
   • Para cada linha de restrição, calcule a razão: RHS / coeficiente da coluna pivô (apenas para coeficientes positivos).
   • A linha com a menor razão não-negativa indica a variável básica que sairá.
   • Garante que a nova SBV permaneça viável.

Operação de Pivotamento

• O elemento na interseção da linha pivô e coluna pivô é o elemento pivô.
• Passo 1: Divida toda a linha pivô pelo elemento pivô para torná-lo 1.
• Passo 2: Use operações de linha para tornar todos os outros elementos na coluna pivô iguais a 0.
• Isso transforma a variável de entrada em básica e a de saída em não-básica.

Exemplo de Maximização: Passo 1

Tableau Inicial:

• Variável de Entrada: \(x_2\) (coeficiente mais negativo na linha Z: -15).
• Razões:
  • Linha \(s_1\): \(120 / 3 = 40\)
  • Linha \(s_2\): \(50 / 1 = 50\)
• Variável de Saída: \(s_1\) (menor razão: 40).
• Elemento Pivô: 3 (na linha \(s_1\), coluna \(x_2\)).

Exemplo de Maximização: Tableau 1 (Após Pivotamento)

• Nova linha \(x_2\): \((2/3)x_1 + 1x_2 + (1/3)s_1 = 40\)
• Novas linhas \(Z\) e \(s_2\) calculadas.

• Interpretação: \(x_1=0, x_2=40, s_1=0, s_2=10\). Lucro \(Z=600\).
• Ainda há coeficientes negativos na linha Z? Não. A solução é ótima.

Condições de Otimidade

• Para Maximização: A solução é ótima quando todos os coeficientes na linha Z são não-negativos.
• Para Minimização: A solução é ótima quando todos os coeficientes na linha Z são não-positivos (ou, se convertida para maximização, todos não-negativos).

Interpretação da Solução Final

• Variáveis Básicas: Seus valores são dados na coluna RHS.
• Variáveis Não-Básicas: Seus valores são 0.
• Valor Ótimo da FO: O valor na coluna RHS da linha Z.
• Preços Sombra (Variáveis de Folga/Excesso): Coeficientes na linha Z das variáveis de folga/excesso na solução ótima. Indicam o quanto a FO melhoraria se a restrição correspondente fosse relaxada em uma unidade.

Solução Ótima do Exemplo de Maximização

• \(x_1 = 0\) cadeiras A

• \(x_2 = 40\) cadeiras B

• Lucro Máximo \(Z = 600\)

• Preços Sombra:

  • \(s_1\) (montagem): 5. Cada hora extra de montagem aumentaria o lucro em R$ 5.
  • \(s_2\) (acabamento): 0. Há folga na restrição de acabamento, então mais horas não aumentariam o lucro.

Atividade 1: Think-Pair-Share (10 min)

Problema: Uma empresa de software desenvolve dois aplicativos, AppX e AppY.

• AppX: Lucro de R$ 2000, requer 100h de desenvolvimento e 50h de testes.
• AppY: Lucro de R$ 3000, requer 150h de desenvolvimento e 75h de testes.
• Disponibilidade: 1500h de desenvolvimento e 800h de testes por mês.

Questão: Formule este problema como um modelo de Programação Linear.

• Think (3 min): Individualmente, escreva a formulação.
• Pair (5 min): Discuta com um colega, compare suas formulações e cheguem a um consenso.
• Share (2 min): Apresente a formulação da dupla para a turma.

Atividade 2: Prática Guiada em Pares (20 min)

Problema: Considere o seguinte problema de PL:

Maximizar \(Z = 3x_1 + 2x_2\) Sujeito a: \(x_1 + x_2 \le 4\) \(2x_1 + x_2 \le 6\) \(x_1, x_2 \ge 0\)

Tarefa:

1. Converta o problema para a forma padrão.
2. Monte o tableau Simplex inicial.
3. Identifique a variável de entrada e a variável de saída.
4. Realize o primeiro pivotamento.
5. Interprete a solução obtida após o primeiro pivotamento.

Desafio da Minimização

Problemas de minimização com restrições de \(\ge\) ou \(=\) não fornecem uma Solução Básica Viável (SBV) inicial trivial (como as variáveis de folga em restrições \(\le\)).

Para resolver isso, usamos o Método das Duas Fases [6]:

• Fase 1: Encontrar uma SBV para o problema original.
• Fase 2: Otimizar a Função Objetivo (FO) original a partir da SBV encontrada.

Etapa 1: Transformar Minimização em Maximização

Para usar o algoritmo Simplex padrão (que maximiza), multiplicamos a Função Objetivo (FO) de minimização por -1.

• Minimizar \(Z = c_1x_1 + c_2x_2\)
• Equivale a Maximizar \(Z' = -c_1x_1 - c_2x_2\)

Ao final, o valor mínimo de \(Z\) será o negativo do valor máximo de \(Z'\).

Etapa 2: Introduzir Variáveis de Folga, Excesso e Artificiais

Para colocar o problema na forma padrão (todas as restrições como igualdades e RHS não-negativos):

• Restrições \(\le\): Adicione variáveis de folga (\(s_i \ge 0\)). Elas representam recursos não utilizados e servem como variáveis básicas iniciais.
• Restrições \(\ge\):
  • Subtraia variáveis de excesso (\(e_i \ge 0\)). Elas representam o quanto o lado esquerdo excede o direito.
  • Adicione variáveis artificiais (\(a_i \ge 0\)). Elas são auxiliares para criar uma base inicial, pois as variáveis de excesso têm coeficiente -1 e não podem ser básicas iniciais.
• Restrições \(=\): Adicione variáveis artificiais (\(a_i \ge 0\)).

Exemplo de Minimização

Uma empresa deseja minimizar o custo de produção de dois produtos, P1 e P2.

• P1: Custo de R$ 4 por unidade, requer 1 unidade de matéria-prima A e 2 unidades de matéria-prima B.
• P2: Custo de R$ 3 por unidade, requer 1 unidade de matéria-prima A e 1 unidade de matéria-prima B.
• Requisitos Mínimos: 8 unidades de matéria-prima A e 10 unidades de matéria-prima B.

Objetivo: Minimizar o custo total.

Formulação Matemática (Original)

• Variáveis:
  • \(x_1\): número de unidades de P1
  • \(x_2\): número de unidades de P2
• Função Objetivo:
  • Minimizar \(Z = 4x_1 + 3x_2\)
• Restrições:
  • \(x_1 + x_2 \ge 8\) (Matéria-prima A)
  • \(2x_1 + x_2 \ge 10\) (Matéria-prima B)
  • \(x_1, x_2 \ge 0\) (Não-negatividade)

Formulação na Forma Padrão (para Simplex)

1. Função Objetivo (Convertida para Maximização):
   • Maximizar \(Z' = -4x_1 - 3x_2\)
2. Restrições (com variáveis de excesso e artificiais):
   • \(x_1 + x_2 - e_1 + a_1 = 8\)
   • \(2x_1 + x_2 - e_2 + a_2 = 10\)
   • \(x_1, x_2, e_1, e_2, a_1, a_2 \ge 0\)

• \(e_1, e_2\): variáveis de excesso.
• \(a_1, a_2\): variáveis artificiais, necessárias para formar uma base inicial.

Fase 1: Encontrar uma SBV (Minimizar a Soma das Artificiais)

Objetivo da Fase 1: Eliminar as variáveis artificiais da base, buscando uma SBV para o problema original.

1. Crie uma Função Objetivo Auxiliar (\(W\)):
   • Minimizar \(W = a_1 + a_2\) (soma das variáveis artificiais).
   • Isso equivale a Maximizar \(-W = -a_1 - a_2\).
2. Expresse \(W\) em termos das variáveis não-artificiais:
   • Das restrições: \(a_1 = 8 - x_1 - x_2 + e_1\) e \(a_2 = 10 - 2x_1 - x_2 + e_2\).
   • Substituindo em \(-W\): \(-W = -(8 - x_1 - x_2 + e_1) - (10 - 2x_1 - x_2 + e_2)\) \(-W = x_1 + x_2 - e_1 - 8 + 2x_1 + x_2 - e_2 - 10\) \(-W = 3x_1 + 2x_2 - e_1 - e_2 - 18\)
   • Reorganizando para a linha do tableau: \(-W - 3x_1 - 2x_2 + e_1 + e_2 = -18\).

Tableau Inicial (Fase 1)

• Variáveis Básicas Iniciais: \(a_1, a_2\).
• Objetivo: Maximizar \(-W\) (ou minimizar \(W\)) até que \(W=0\) e todas as variáveis artificiais saiam da base.

Fase 1 - Passo 1: Pivotamento

Tableau Atual:

• Variável de Entrada: \(x_1\) (coeficiente mais negativo na linha \(-W\): -3).
• Razões:
  • Linha \(a_1\): \(8 / 1 = 8\)
  • Linha \(a_2\): \(10 / 2 = 5\)
• Variável de Saída: \(a_2\) (menor razão: 5).
• Elemento Pivô: 2 (na linha \(a_2\), coluna \(x_1\)).

Fase 1 - Tableau 1 (Após Pivotamento)

• Operações de Linha:
  • \(L_{nova\_x_1} = L_{a_2} / 2\)
  • \(L_{nova\_{-W}} = L_{-W} + 3 \cdot L_{nova\_x_1}\)
  • \(L_{nova\_a_1} = L_{a_1} - 1 \cdot L_{nova\_x_1}\)

Fase 1 - Passo 2: Pivotamento

Tableau Atual:

• Variável de Entrada: \(x_2\) (coeficiente mais negativo na linha \(-W\): -1/2).
• Razões:
  • Linha \(a_1\): \(3 / (1/2) = 6\)
  • Linha \(x_1\): \(5 / (1/2) = 10\)
• Variável de Saída: \(a_1\) (menor razão: 6).
• Elemento Pivô: \(1/2\) (na linha \(a_1\), coluna \(x_2\)).

Fase 1 - Tableau 2 (Após Pivotamento)

• Operações de Linha:
  • \(L_{nova\_x_2} = L_{a_1} / (1/2)\)
  • \(L_{nova\_{-W}} = L_{-W} + (1/2) \cdot L_{nova\_x_2}\)
  • \(L_{nova\_x_1} = L_{x_1} - (1/2) \cdot L_{nova\_x_2}\)

• Fim da Fase 1: Todos os coeficientes na linha \(-W\) são não-negativos e o valor de \(-W\) é 0.
• As variáveis artificiais \(a_1\) e \(a_2\) saíram da base.
• Temos uma Solução Básica Viável para o problema original: \(x_1=2, x_2=6\).

Fase 2: Otimizar a FO Original

1. Remova as colunas das variáveis artificiais (\(a_1, a_2\)) e a linha da FO auxiliar (\(-W\)).
2. Reintroduza a FO original convertida (\(Z' = -4x_1 - 3x_2\)) na primeira linha do tableau.
3. Ajuste a linha \(Z'\): Garanta que os coeficientes das variáveis básicas (\(x_1, x_2\)) na linha \(Z'\) sejam zero.

• Tableau da Fase 1 (final, sem artificiais): | Base | \(x_1\) | \(x_2\) | \(e_1\) | \(e_2\) | RHS | |:—-:|:—–:|:—–:|:—–:|:—–:|:—:| | \(x_2\)| 0 | 1 | -2 | 1 | 6 | | \(x_1\)| 1 | 0 | 1 | -1 | 2 |

• FO Original: Max \(Z' = -4x_1 - 3x_2\).

• Para ajustar a linha \(Z'\):

  • \(Z' + 4x_1 + 3x_2 = 0\)
  • Substitua \(x_1\) e \(x_2\) pelas suas expressões em termos das variáveis não-básicas (ou use operações de linha para zerar os coeficientes de \(x_1\) e \(x_2\) na linha \(Z'\)).
  • \(Z' + 4(1x_1 + 0e_1 - 1e_2) + 3(1x_2 - 2e_1 + 1e_2) = 4(2) + 3(6)\)
  • \(Z' + 4x_1 + 3x_2 + (4-6)e_1 + (-4+3)e_2 = 8 + 18\)
  • \(Z' + 4x_1 + 3x_2 - 2e_1 - e_2 = 26\)
  • A linha \(Z'\) no tableau será: \(Z'\) | 0 | 0 | 2 | 1 | -26

Tableau Inicial (Fase 2)

• Verificação de Otimidade: Todos os coeficientes na linha \(Z'\) são não-negativos (2 e 1).
• A solução é ótima. Não há necessidade de mais pivotamentos.

Solução Ótima do Exemplo de Minimização

• Variáveis de Decisão:
  • \(x_1 = 2\) unidades de P1
  • \(x_2 = 6\) unidades de P2
• Variáveis de Excesso:
  • \(e_1 = 0\) (não-básica)
  • \(e_2 = 0\) (não-básica)
• Valor Ótimo da FO Convertida: \(Z' = -26\)
• Valor Ótimo da FO Original (Custo Mínimo): \(Z = -Z' = -(-26) = 26\)

Interpretação da Solução Final

• A empresa deve produzir 2 unidades de P1 e 6 unidades de P2.
• O custo mínimo total será de R$ 26.
• As variáveis de excesso \(e_1\) e \(e_2\) serem zero indicam que os requisitos mínimos de matéria-prima A e B são atendidos exatamente, sem excesso.

Revisão dos Conceitos Chave

• Programação Linear: Otimização de FO linear sujeita a restrições lineares.
• Forma Padrão: Essencial para o Simplex (FO de maximização, restrições de igualdade, RHS e variáveis não-negativas).
• Variáveis de Folga, Excesso e Artificiais: Cruciais para a conversão à forma padrão e para a criação de uma base inicial.
• Método das Duas Fases: Abordagem para problemas de minimização ou com restrições de \(\ge\) ou \(=\), garantindo uma SBV inicial.
• Tableau Simplex: Representação tabular para aplicar o algoritmo.
• Critérios de Pivotamento: Seleção da variável de entrada (maior contribuição) e de saída (menor razão).
• Otimidade: Linha Z sem coeficientes negativos (para maximização).

Aplicações em Engenharia de Produção

• Planejamento da Produção: Otimizar mix de produtos, alocação de recursos.
• Logística: Roteamento de veículos, localização de instalações, gestão de estoque.
• Finanças: Otimização de carteiras de investimento.
• Gestão de Projetos: Alocação de recursos, cronogramas.

Próximos Passos

• Estudar a dualidade em Programação Linear.
• Análise de sensibilidade: como a solução ótima muda com variações nos parâmetros.
• Uso de softwares (solvers) para resolver problemas de PL de grande escala.

Referências

• Hillier, F. S.; Lieberman, G. J. Introdução à Pesquisa Operacional. 10. ed. Porto Alegre: AMGH, 2017.
• Bazaraa, M. S.; Jarvis, J. J.; Sherali, H. D. Linear Programming and Network Flows. 4th ed. Hoboken: Wiley, 2010.

Dúvidas?

Obrigado pela atenção!