Aula 09 - Pesquisa Operacional, Programação Linear, Método Simplex e Otimização com Solver

📘 Modelagem Matemática: Aula 09

📌 Sumário da Aula

1. Pesquisa Operacional e Programação Linear (PL): Método Gráfico, Algoritmo Simplex Tabular, Análise de Sensibilidade e Otimização com MS Excel Solver e Python
   • Fases do Processo de Pesquisa Operacional:
   • Classificação das Variáveis e Termos:
   • Casos Especiais em Programação Linear:
   • 5.1 Transformação para a Forma Padrão
   • 5.2 Estrutura do Tableau Simplex e Regras de Decisão
   • 6.1 Preço-Sombra (*Shadow Price* / Valor Dual)
   • 6.2 Custo Reduzido (*Reduced Cost*)
   • 7.1 Procedimento Passo a Passo no MS Excel Solver:
   • 7.2 Código Python de Alta Performance com SciPy (HiGHS):
   • Questão 1 (Apostila 05 - Seção 1 / Questão 1): Conceito de Modelagem em Pesquisa Operacional
   • Questão 2 (Apostila 05 - Seção 1 / Questão 2): Etapa de Coleta de Dados na Pesquisa Operacional
   • Questão 3 (Apostila 05 - Seção 2 / Questão 1): Elementos de um Modelo de Programação Linear
   • Questão 4 (Apostila 05 - Seção 2 / Questão 2 - Pedido 1): Problema do Sapateiro - Formulação da Função Objetivo
   • Questão 5 (Apostila 05 - Seção 2 / Questão 3 - Pedido 2): Problema do Sapateiro - Restrição de Couro
   • Questão 6 (Apostila 05 - Seção 2 / Questão 4 - Pedido 3): Problema do Sapateiro - Restrição de Tempo de Trabalho
   • Questão 7 (Apostila 05 - Seção 3 / Questão 1): Modelagem da Indústria de Confecção Fitwear S/A
   • Questão 8 (Apostila 05 - Seção 3 / Questão 2): Resolução Simplex do Modelo Fitwear S/A
   • Questão 9 (Apostila 05 - Seção 4 / Questão 1): Problema de Mistura de Rações da Fábrica XYZ
   • Questão 10 (Apostila 05 - Seção 4 / Questão 2): Problema da Dieta Saudável de Menor Custo
2. 📚 Referências Bibliográficas

---

Pesquisa Operacional e Programação Linear (PL): Método Gráfico, Algoritmo Simplex Tabular, Análise de Sensibilidade e Otimização com MS Excel Solver e Python

Navegação Rápida no Cofre

📍 Disciplina: Modelagem Matemática | 📚 MOC: 01 Matemática e Estatística | 🏠 Início: Hub Principal 📄 Apostila Base: Bases de Otimização Com ms Excel ⬅️ Aula Anterior: Aula 08 - EDOs de 1ª Ordem 💻 Códigos Associados: otimizacao_simplex.py 🖼️ Diagrama Técnico: modelagem_programacao_linear_simplex_grafico.svg

---

🎯 Objetivos de Aprendizagem

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

1. Compreender o papel da Pesquisa Operacional (PO) na Engenharia Elétrica e de Produção: mapear problemas reais de alocação de recursos escassos (despacho econômico térmico/hidráulico, dimensionamento de cabos, planejamento de geração e transmissão) em modelos matemáticos formais.
2. Dominar os Elementos Constitutivos de um Modelo de Programação Linear (PL):
   • Variáveis de Decisão ($x_j$): incógnitas controláveis do sistema.
   • Parâmetros ($c_j,a_{ij},b_i$): constantes não controláveis coletadas no sistema físico.
   • Função Objetivo ($Z$): maximização de lucro/eficiência ou minimização de custos/perdas.
   • Conjunto de Restrições: limitações de capacidade, matéria-prima, tempo e não-negatividade ($x_j\ge 0$).
3. Dominar a Resolução Geométrica pelo Método Gráfico (2D):
   • Delinear o Poliedro da Região Viável Convexa no plano cartesiano.
   • Traçar as curvas de nível da função objetivo e o vetor gradiente $\nabla Z$.
   • Aplicar o Teorema Fundamental da Programação Linear: a solução ótima sempre ocorre em pelo menos um dos Vértices Extremos (Solução Básica Viável - SBV).
   • Identificar patologias: Múltiplas Soluções Ótimas, Região Ilimitada e Inviabilidade.
4. Dominar o Algoritmo Simplex Tabular:
   • Transformar o modelo para a Forma Padrão introduzindo variáveis de folga ($s_i\ge 0$) e variáveis de excesso ($e_i\ge 0$).
   • Construir o Tableau Simplex, selecionar a variável que entra na base (custo reduzido mais negativo) e a variável que sai da base (teste da menor razão positiva $b_i/a_{ik}$).
   • Executar o pivoteamento de Gauss-Jordan até atingir a otimalidade (todos os coeficientes da linha $Z$ não-negativos).
5. Dominar a Análise de Sensibilidade e Pós-Otimalidade:
   • Interpretar o Preço-Sombra (Shadow Price) / Variável Dual: taxa de variação do valor ótimo $\frac{\partial Z^{\ast }}{\partial b_i}$ e o Teorema das Folgas Complementares.
   • Analisar o Custo Reduzido (Reduced Cost) e os intervalos de admissibilidade para coeficientes $c_j$ e recursos $b_i$.
6. Implementar e Resolver Modelos no MS Excel Solver e em Python:
   • Parametrizar planilhas industriais com o suplemento Solver do Excel (método Simplex LP).
   • Resolver problemas de grande porte em Python via scipy.optimize.linprog(method='highs').

---

📊 1. Diagrama Técnico Estrutural

O diagrama a seguir sintetiza a interpretação geométrica do Método Gráfico, a mecânica tabular do Algoritmo Simplex e os fundamentos da Análise de Sensibilidade.

---

🏭 2. Introdução à Pesquisa Operacional e Modelagem Matemática

A Pesquisa Operacional (PO) originou-se durante a Segunda Guerra Mundial para otimizar o posicionamento de radares, rotas de comboios e suprimentos militares. Com o pós-guerra, expandiu-se vertiginosamente para a indústria moderna.

Fases do Processo de Pesquisa Operacional:

1. Formulação do Problema: definição clara dos objetivos e delimitação do escopo.
2. Observação do Sistema e Coleta de Dados: medição de tempos, custos unitários e capacidades máximas (onde são estimados os parâmetros).
3. Formulação do Modelo Matemático: tradução dos objetivos em equações e inequações.
4. Dedução da Solução (Otimização): execução de algoritmos matemáticos (Simplex, Branch-and-Bound, Gradiente).
5. Verificação, Validação e Sensibilidade: testes com dados históricos e análise de robustez frente a incertezas.
6. Implementação e Controle: implantação do plano operacional na rotina da empresa.

---

📐 3. Formulação Canônica de Programação Linear (PL)

Um modelo é denominado Linear quando todas as relações matemáticas (função objetivo e restrições funcionais) são estritamente lineares:

undefined