Solucionador de Programação Linear

Solucionador de Programação Linear

O Solucionador de Programação Linear é uma calculadora online que encontra o máximo ou mínimo de uma função objetivo linear sujeita a um sistema de desigualdades ou igualdades lineares. Ele utiliza o método simplex (variante Big-M) para que as restrições <=, >= e = possam ser misturadas livremente e, para problemas de 2 variáveis, desenha um gráfico interativo da região viável com cada vértice e o ótimo destacados.

O que é Programação Linear?

Um problema de programação linear (PL) propõe:

O conjunto de pontos que satisfazem todas as restrições é chamado de região viável, um poliedro convexo. O Teorema Fundamental da Programação Linear afirma que se a PL tem um ótimo finito, ele é alcançado em um vértice (ponto extremo) deste poliedro. É por isso que o método simplex — que caminha de vértice em vértice — é tão eficaz.

Como Funciona o Método Simplex

A partir de um vértice viável, o método simplex melhora repetidamente o objetivo pivotando para um vértice vizinho com um valor melhor. A mecânica:

1. Forma padrão: converte a PL para max c^Tx sujeito a Ax = b, x ≥ 0. Para restrições <=, adiciona variáveis de folga; para >=, subtrai um excesso e adiciona uma artificial com uma grande penalidade −M; para igualdades, adiciona uma artificial.
2. Quadro inicial: a base consiste em folgas e artificiais, o que fornece um vértice inicial óbvio.
3. Variável de entrada: escolhe a variável não básica com o maior custo reduzido positivo \( c_j - z_j \). Se não existir tal variável, a solução atual é a ótima.
4. Variável de saída: a partir da coluna de entrada, realiza o teste da razão mínima — divide o RHS de cada linha por sua entrada positiva na coluna de entrada e escolhe a linha com a menor razão. Se não existir entrada positiva, a PL é ilimitada.
5. Pivô: utiliza a eliminação gaussiana para tornar a coluna de entrada um vetor unitário, com 1 na linha de saída.
6. Repete até que o critério de parada seja atingido.

Se qualquer variável artificial permanecer na base com um valor positivo ao final, a PL original é inviável.

Método Gráfico (para 2 Variáveis)

Para problemas de duas variáveis, a região viável é um polígono convexo 2D. Como o ótimo está sempre em um vértice, enumerar cada vértice e avaliar a função objetivo é suficiente para resolver o problema. Esta calculadora realiza essa enumeração interceptando cada par de limites de restrição, mantendo apenas as interseções que satisfazem todas as outras restrições e ordenando-as no sentido anti-horário para a visualização.

Sintaxe de Entrada

Escreva o objetivo na primeira linha e, em seguida, uma restrição por linha. Os nomes das variáveis podem ser qualquer identificador (x, y, x1, lucro…). Os operadores são <=, >= e =. A não-negatividade pode ser escrita como x, y >= 0 como um atalho.

Linhas em branco e comentários iniciados com # são ignorados. O solucionador aceita até 8 variáveis de decisão e 20 restrições.

Exemplo Prático

Considere uma oficina de móveis que fabrica mesas e cadeiras. Cada mesa rende \\$3 de lucro e requer 1 unidade de madeira e 2 unidades de mão de obra. Cada cadeira rende \\$5 de lucro e requer 1 unidade de madeira, 1 unidade de mão de obra e 3 unidades de verniz. Disponível: 10 de madeira, 16 de mão de obra, 18 de verniz. Com x = mesas e y = cadeiras, a PL é:

A região viável é um pentágono. Avaliando Z em cada vértice:

Portanto, a oficina deve fabricar 6 mesas e 4 cadeiras para um lucro máximo de \\$38. As restrições de madeira e mão de obra são ativas (elas se igualam ao seu RHS no ótimo); o verniz tem uma folga de 0 (também ativa neste caso), o que significa que todos os três recursos foram esgotados.

Erros Comuns e o que o Solucionador Detecta

Aplicações

• Mix de produtos e planejamento de produção — quantos de cada produto fabricar para obter o lucro máximo sob limites de recursos.
• Problemas de dieta e mistura — minimizar o custo de uma dieta ou ração que ainda atenda aos mínimos nutricionais.
• Transporte e atribuição — minimizar o custo de envio quando a oferta e a demanda devem ser equilibradas.
• Otimização de portfólio — maximizar o retorno esperado sob restrições de risco ou exposição (linearizadas).
• Fluxo de rede — problemas de fluxo máximo e fluxo de custo mínimo reduzem-se a PLs com matrizes de coeficientes totalmente unimodulares.
• Escalonamento — organização de escalas de trabalho com requisitos de turno e limites de horas totais.

Como Usar Esta Calculadora

1. Digite sua PL na caixa de texto. A primeira linha deve começar com Maximize ou Minimize. Cada linha seguinte é uma restrição, uma por linha.
2. Use o atalho x, y >= 0 para declarar a não-negatividade de todas as variáveis listadas de uma só vez.
3. Clique em Resolver Problema de PL. O solucionador informa o valor ótimo Z, os valores ótimos de cada variável de decisão, uma lista de restrições ativas e, para PLs de 2 variáveis, um gráfico interativo da região viável.
4. Passe o mouse sobre um vértice no gráfico para ver suas coordenadas e o valor Z. O ótimo é destacado com uma estrela.
5. Revise os quadros simplex para ver cada pivô e rastrear como o método melhora Z. A coluna de entrada é destacada em âmbar; a linha de saída em vermelho.

Perguntas Frequentes

O que é um problema de programação linear?

Um problema de programação linear (PL) busca o máximo ou mínimo de uma função objetivo linear sobre um conjunto de variáveis de decisão que satisfazem um sistema de desigualdades ou igualdades lineares. O conjunto viável é um poliedro convexo, e o ótimo é sempre alcançado em um de seus vértices — o fato fundamental que o método simplex explora.

Como funciona o método simplex?

O método simplex caminha pelos vértices do poliedro viável. Cada etapa (um "pivô") troca uma variável na base por outra, movendo-se para um vértice vizinho com um objetivo estritamente melhor. O algoritmo para quando nenhum pivô pode melhorar Z — o vértice atual é então o ótimo. Esta ferramenta utiliza a variante Big-M para que restrições <=, >= e = possam ser misturadas.

O que é a região viável?

A região viável é o conjunto de todos os valores de variáveis que satisfazem todas as restrições simultaneamente. Para 2 variáveis, é um polígono convexo 2D; para n variáveis, é um poliedro n-dimensional. Um poliedro vazio significa que a PL é inviável; um poliedro que se estende infinitamente na direção de melhoria significa que a PL é ilimitada.

O que significa "ilimitado" na programação linear?

Uma PL é ilimitada quando a região viável se alonga ao infinito em uma direção onde o objetivo continua melhorando. Por exemplo, Maximize x sujeito apenas a x ≥ 0 não tem máximo finito. PLs do mundo real que retornam ilimitado geralmente revelam uma restrição ausente — frequentemente um limite superior em um recurso ou variável.

O que significa "múltiplos ótimos"?

Múltiplos ótimos ocorrem quando mais de um ponto atinge o mesmo melhor valor objetivo. Geometricamente, o objetivo é paralelo a uma aresta ativa do polígono, então cada ponto ao longo dessa aresta — e cada combinação convexa de seus pontos finais — é ótimo. O solucionador sinaliza isso quando qualquer variável de decisão não básica tem um custo reduzido de zero ao final.

Quantas variáveis e restrições o solucionador aceita?

Até 8 variáveis de decisão e 20 restrições. O gráfico interativo da região viável é desenhado apenas para problemas de 2 variáveis; com 3 ou mais variáveis, você ainda obtém a solução numérica completa do simplex, quadros passo a passo e o relatório de restrições ativas.

Leitura Adicional

• Programação linear — Wikipédia
• Algoritmo simplex — Wikipédia
• Método Big M — Wikipédia (em inglês)
• Dualidade em otimização — Wikipédia

Operações matemáticas avançadas:

• Calculadora de Matriz de Adjacência Novo
• Calculadora de Antilog
• Calculadora de Função Beta
• Calculadora de Coeficiente Binomial
• Calculadora de distribuição binomial
• Calculadora de Lógica Binária
• Simplificador de Álgebra Booleana Novo
• Calculadora do Teorema Central do Limite
• Calculadora do Teorema Chinês do Resto
• Calculadora de Combinação Popular
• Calculadora de Função de Erro Complementar
• Calculadora de Números Complexos Popular
• Calculadora de Frações Contínuas
• Calculadora de Desarranjo (Subfatorial)
• Calculadora de Caminho Mais Curto de Dijkstra
• Calculadora de Entropia
• Calculadora da função de erro
• Calculadora da Função Totiente de Euler
• Calculadora de decaimento exponencial
• Calculadora de Crescimento Exponencial de Alta Precisão
• Calculadora de Integral Exponencial
• Calculadora de Expoentes (Alta Precisão)
• Calculadora do Algoritmo Euclidiano Estendido
• Calculadora de Fatorial
• Calculadora de Função Gama
• Calculadora de Proporção Áurea
• Calculadora de Coloração de Grafos Novo
• Validador de Sequência de Graus de Grafo
• Calculadora de Ordem em Teoria dos Grupos Novo
• Calculadora de Meia-Vida
• Verificador de Caminho Hamiltoniano Novo
• Calculadora de Inclusão-Exclusão Novo
• Solucionador de Mapa de Karnaugh (K-Map) Novo
• Solucionador de Programação Linear Novo
• Calculadora de Estado Estacionário da Cadeia de Markov
• Calculadora de Árvore Geradora Mínima
• Calculadora de Exponenciação Modular Novo
• Calculadora do Inverso Multiplicativo Modular
• Calculadora de Distribuição Binomial Negativa Novo
• Calculadora de Fluxo em Rede (Fluxo Máximo) Novo
• Calculadora de Taxa de Crescimento Percentual Popular
• Calculadora de Permutação
• Calculadora de Permutações com Repetição Novo
• Calculadora do Princípio da Casa dos Pombos
• Verificador de Grafo Planar Novo
• Calculadora de Distribuição de Poisson Popular
• Calculadora de Raízes de Polinômios
• Calculadora de Raiz Primitiva
• Calculadora de Probabilidade
• Calculadora de Distribuição de Probabilidade
• Calculadora de Proporção Popular
• Calculadora de Fórmula Quadrática
• Calculadora de Anéis e Corpos Novo
• Calculadora de Arredondamento Novo
• Calculadora Científica
• Calculadora de notação científica
• Calculadora de Teoria dos Conjuntos
• Calculadora de Algarismos Significativos Novo
• Solucionador do Problema do Casamento Estável Novo
• Calculadora de Números de Stirling
• Calculadora de Soma de Cubos
• Calculadora de soma de inteiros positivos
• Calculadora de Soma dos Quadrados
• Calculadora de Ordenação Topológica Novo
• Solucionador do Caixeiro Viajante (TSP) Novo
• Gerador de Tabela Verdade Popular
• Gerador de Diagrama de Venn (3 Conjuntos)