Calculadora de Programação Linear (Método Simplex)

O que a programação linear faz

A programação linear é a ferramenta de trabalho da pesquisa operacional: um método para extrair o melhor resultado possível de uma situação governada por limites.

Você descreve o que quer em um único objetivo, maximizar lucro ou produção, ou minimizar custo, desperdício ou tempo, lista as decisões que controla como variáveis, e escreve as restrições que as cercam, sejam horas de máquina, material, orçamento ou demanda.

Cada uma dessas relações é linear, uma soma ponderada sem produtos nem potências das variáveis, e essa linearidade é justamente o que torna o problema resolúvel de forma rápida e confiável mesmo com centenas de variáveis. O resultado é a única combinação de decisões que rende melhor sem quebrar nenhuma regra.

O poder do método vem de um fato geométrico. As restrições recortam uma região viável, o conjunto de todas as decisões que satisfazem cada limite ao mesmo tempo, e como tanto a região quanto o objetivo são lineares, a melhor solução sempre está em um canto dessa região, e não no seu interior. Isso transforma uma busca infinita em uma finita: examine os cantos de forma organizada e você encontrará o ótimo. O método simplex, que esta calculadora implementa, faz exatamente isso, caminhando de canto em canto que melhora até que nenhum vizinho seja melhor. No caminho produz não apenas a resposta, mas os preços-sombra, que dizem o que cada recurso escasso realmente vale na margem.

Esta calculadora resolve qualquer programa linear que você consiga digitar: escolha maximizar ou minimizar, informe os coeficientes do objetivo e liste as restrições uma por linha com uma relação de menor que, maior que ou igualdade. Ela devolve o valor ótimo do objetivo, o valor de cada variável de decisão, se cada restrição é ativa ou tem folga de sobra, e o preço-sombra de cada restrição. Quando o seu problema tem exatamente duas variáveis também desenha a região viável e marca o canto ótimo, para que você veja a geometria que a álgebra descreve. Tudo roda no seu navegador e nada do que você informa é armazenado.

Como esta calculadora funciona, passo a passo

Comece escolhendo a direção do objetivo. Escolha maximizar quando mais é melhor, lucro, unidades produzidas, margem de contribuição, e minimizar quando menos é melhor, custo, refugo ou horas. Depois informe os coeficientes do objetivo, um número por variável, separados por espaços ou vírgulas. A ordem que você usa aqui fixa a ordem das variáveis em todo o resto: se você digita três coeficientes, a ferramenta espera três coeficientes em cada linha de restrição, na mesma ordem. A calculadora abre com um exemplo resolvido de duas variáveis já preenchido, um problema clássico de mix de produtos, para que você veja uma solução correta e o seu gráfico antes de mudar qualquer coisa.

Depois informe as restrições, uma por linha. Cada linha lista o coeficiente de cada variável, depois o operador relacional, depois o valor do lado direito, por exemplo “3 2 <= 18". Você pode usar <=, >= e = (os símbolos e o simples < ou > também funcionam). Você não precisa acrescentar as condições de não negatividade de que cada variável é ao menos zero, porque a calculadora as supõe automaticamente, como faz a programação linear padrão. Enquanto você digita, a ferramenta resolve de novo ao vivo, então o valor do objetivo, os valores das variáveis e a tabela de restrições se atualizam de imediato, e o gráfico é redesenhado em problemas de duas variáveis.

O painel de resultados encabeça com o valor ótimo do objetivo, depois lista cada variável de decisão com o seu valor ótimo. Abaixo, uma tabela mostra cada restrição com quanto do seu limite a solução usa, se é ativa ou quanta folga ou excedente resta, e o seu preço-sombra. Uma restrição ativa é uma que a solução usa por completo; o seu preço-sombra é a melhora do objetivo que você ganharia com uma unidade a mais desse recurso. Quando o problema não pode ser resolvido a ferramenta diz isso com clareza, reportando inviável quando as restrições se contradizem e ilimitado quando o objetivo pode crescer sem limite. Baixe um PDF ou CSV da solução ou compartilhe; tudo acontece localmente.

Percorrer os cantos: como o solucionador trabalha

O motor por trás desta calculadora é o método simplex de duas fases, o algoritmo padrão da programação linear. O seu fundamento é o teorema de que uma solução ótima, se existir, sempre é encontrada em um vértice, um canto, da região viável. Em vez de testar cada canto às cegas, o método simplex parte de um canto viável e passa repetidamente a um canto adjacente que melhora o objetivo, parando quando nenhum vizinho é melhor, o que pela teoria garante o ótimo. Cada passo é um pivoteamento, uma pequena operação algébrica que coloca uma variável no conjunto ativo e retira outra, deslizando geometricamente por uma aresta da região de um vértice ao seguinte.

As duas fases resolvem um detalhe prático. Quando um problema tem apenas restrições de menor ou igual com lados direitos não negativos, a origem é um canto inicial viável cômodo. Mas as restrições de maior ou igual e de igualdade muitas vezes excluem a origem, então não há um ponto óbvio por onde começar.

A fase um resolve um problema auxiliar que leva a zero um conjunto de variáveis artificiais temporárias, o que coloca o algoritmo em um canto viável genuíno; a fase dois otimiza então o objetivo real a partir dali.

Esta calculadora roda as duas fases automaticamente, então você pode misturar restrições <=, >= e = livremente e ainda assim obter uma resposta correta, junto com a detecção do caso inviável, quando a fase um não alcança a viabilidade, e do caso ilimitado, quando a fase dois pode melhorar para sempre.

Uma tranquilidade sobre a velocidade: embora uma região possa ter um número enorme de cantos, o método simplex quase nunca visita mais do que um pequeno múltiplo do número de restrições antes de chegar ao ótimo, por isso se mantém rápido no tamanho de problema que uma pessoa digita aqui e em modelos industriais muito maiores. Cada pivoteamento também carrega a solução em curso de forma exata, mantendo os valores das variáveis e os preços-sombra consistentes a cada passo, então as cifras que a calculadora finalmente reporta são o ótimo exato do modelo que você informou, e não uma aproximação arredondada, exceto por valores minúsculos ajustados a zero por legibilidade.

Cinco exemplos resolvidos que você pode seguir

Exemplo 1: o mix de produtos padrão

A calculadora abre maximizando 3x₁ + 5x₂ sujeito a x₁ ≤ 4, 2x₂ ≤ 12 e 3x₁ + 2x₂ ≤ 18. O ótimo é x₁ = 2, x₂ = 6, dando um objetivo de 36. A segunda e a terceira restrição são ativas, usadas por completo, enquanto a primeira tem folga, já que x₁ = 2 está abaixo do seu limite de 4. Os preços-sombra são 0 para a primeira restrição, 1,5 para a segunda e 1 para a terceira, o que significa que uma unidade a mais do segundo recurso elevaria o objetivo em 1,5 e uma a mais do terceiro em 1, enquanto mais do primeiro não vale nada porque não é o gargalo.

Exemplo 2: ler o gráfico

Como esse exemplo tem duas variáveis, a calculadora desenha a sua região viável como um polígono e marca o ótimo no canto (2, 6). Trace as arestas e você verá por que a resposta está ali: a linha do objetivo, inclinada pela razão 3 para 5 dos seus coeficientes, é empurrada o mais para cima e para a direita que pode enquanto ainda toca a região, e toca pela última vez nesse canto. Este é o quadro geométrico que a álgebra simplex calcula, e ver que os dois concordam constrói a intuição para problemas com mais variáveis onde o quadro não pode ser desenhado.

Exemplo 3: uma minimização

Mude o objetivo para minimizar e informe 2 3 com as restrições x₁ + x₂ ≥ 10, x₁ ≤ 8 e x₂ ≤ 8. Agora a meta é a forma mais barata de cumprir um requisito de ao menos dez unidades combinadas. O ótimo é x₁ = 8, x₂ = 2 com um objetivo de 22, já que a primeira variável é mais barata por unidade e é empurrada ao seu limite antes de a segunda, mais cara, cobrir a diferença. A restrição de maior ou igual é ativa, e a fase um do simplex é o que torna resolúvel um problema assim, porque a origem não é viável aqui.

Exemplo 4: uma mistura de três variáveis

A programação linear não se limita a duas variáveis. Minimize 2 3 1 sujeito a x₁ + x₂ + x₃ ≥ 10 e x₁ + 2x₂ ≥ 8, um pequeno problema de mistura. O ótimo é x₁ = 0, x₂ = 4, x₃ = 6 com um objetivo de 18, porque o terceiro ingrediente é a forma mais barata de preencher o primeiro requisito enquanto a segunda variável cobre mais barato o segundo. Com três variáveis a calculadora tira o gráfico, já que a região viável agora vive em três dimensões, mas a solução numérica e os preços-sombra são calculados exatamente como antes.

Exemplo 5: um modelo inviável

Informe uma única variável com as duas restrições x₁ ≥ 10 e x₁ ≤ 5. Nenhum valor pode ser ao mesmo tempo ao menos dez e no máximo cinco, então a região viável está vazia e a calculadora reporta o problema como inviável em vez de devolver um número. Ver isso é útil: um resultado inviável quase sempre significa que uma restrição foi digitada errado ou que o modelo está apertado demais, e é um convite a reexaminar os limites, não uma falha do método. O caso companheiro, um objetivo ilimitado, aparece quando uma maximização não tem uma restrição que impeça o objetivo de crescer.

Três dicas de especialista para um bom modelo

Preços-sombra e o valor de um recurso escasso

O subproduto mais útil de resolver um programa linear é o conjunto de preços-sombra, e entendê-los transforma a calculadora de um solucionador em uma ferramenta de planejamento. Um preço-sombra é a taxa à qual o objetivo ótimo mudaria se você tivesse uma unidade a mais do recurso de uma dada restrição, mantendo tudo o mais fixo. Se uma restrição de horas de máquina tem um preço-sombra de 12, então uma hora de máquina a mais elevaria o lucro ótimo em 12, que é precisamente o máximo que você deveria estar disposto a pagar por essa hora extra. Os preços-sombra convertem a noção abstrata de um gargalo em um valor concreto por unidade, ordenando os seus recursos por quanto vale liberá-los.

O padrão dos preços-sombra segue uma regra simples e importante. Uma restrição ativa, que a solução ótima usa por completo, em geral tem um preço-sombra diferente de zero, porque relaxá-la deixaria o objetivo melhorar. Uma restrição não ativa, com folga ou excedente sobrando, sempre tem preço-sombra zero, porque você já tem mais desse recurso do que o plano ótimo pode usar, então uma unidade extra não vale nada.

Por isso a calculadora marca o estado de cada restrição ao lado do seu preço-sombra: os dois juntos dizem não só onde o dinheiro é feito, mas onde acrescentar capacidade ajudaria e onde não. No exemplo padrão, a primeira restrição fica ociosa com preço-sombra zero enquanto a segunda e a terceira, ambas ativas, carregam preços-sombra positivos, identificando-as de imediato como os gargalos que vale a pena atacar.

Ler a tabela assim é como os analistas experientes decidem onde investir, qual contrato de fornecedor ampliar e qual limite aparente não está limitando nada de verdade.

O método gráfico para duas variáveis

Quando um programa linear tem só duas variáveis todo o problema pode ser desenhado em um plano, e o método gráfico é a forma mais clara de construir intuição sobre o que o algoritmo simplex faz de forma invisível em dimensões maiores.

Cada restrição vira uma linha, e a desigualdade que ela carrega fica com um lado dessa linha; a sobreposição de todos esses semiplanos, junto com o quadrante não negativo, é a região viável, um polígono.

A função objetivo, por sua vez, é uma família de linhas paralelas, uma para cada valor do objetivo, e otimizar significa deslizar essa linha o mais longe que ela for na direção que melhora enquanto ainda toca a região. O último ponto que ela toca, sempre um canto, é o ótimo.

Esta calculadora desenha exatamente esse quadro para problemas de duas variáveis: calcula o polígono intersecando as fronteiras das restrições, sombreia a região viável e marca o vértice ótimo que o método simplex encontrou. Ver o ótimo cair em um canto, e ver quais arestas de restrição se encontram ali, torna tangível a noção de restrições ativas, as arestas que passam pelo canto ótimo são as ativas, e os seus preços-sombra são diferentes de zero.

Também torna visuais os casos patológicos: uma região vazia significa inviável, e uma região aberta na direção que melhora significa ilimitado.

Embora problemas reais costumem ter mais de duas variáveis e por isso não possam ser desenhados, o quadro de duas variáveis é o modelo mental que todo praticante de programação linear leva aos casos de dimensão maior, onde a mesma lógica de cantos, arestas e um objetivo que desliza continua valendo mesmo quando não pode mais ser vista.

Dualidade: todo problema tem uma imagem espelhada

Por trás de todo programa linear está um segundo, o seu dual, e a relação entre os dois é um dos resultados mais profundos e práticos do campo. Partindo do problema original, chamado de primal, o dual é formado convertendo as restrições em variáveis e as variáveis em restrições.

Se o primal maximiza lucro sujeito a recursos limitados, o seu dual minimiza o valor total imputado desses recursos sujeito à condição de que o valor atribuído aos recursos usados por cada produto seja ao menos o lucro do produto.

As variáveis duais são, uma a uma, os preços-sombra das restrições do primal, por isso os preços-sombra que a calculadora reporta carregam uma interpretação econômica clara como o valor implícito de cada recurso.

O teorema central, a dualidade forte, diz que quando qualquer um dos dois problemas tem solução ótima, o outro também tem, e os seus valores ótimos do objetivo são exatamente iguais. O lucro máximo que o primal pode ganhar é igual ao valor mínimo de recursos que o dual atribui, uma afirmação de que o valor total dos recursos escassos, precificados aos seus preços-sombra, dá conta de todo o lucro.

Isso não é apenas elegante; é a base do raciocínio econômico que faz da programação linear uma ferramenta de decisão e não só um exercício aritmético. A dualidade garante que os preços-sombra sejam consistentes, que nunca super nem subvalorizem os recursos no agregado, e sustenta a análise de sensibilidade, o estudo de quanto os dados podem mudar antes que o plano ótimo mude.

Embora esta calculadora apresente a solução primal e os seus preços-sombra diretamente, esses preços-sombra são as variáveis duais ótimas, então lê-los é ler de graça a resposta ao problema imagem espelhada.

Onde os pressupostos do modelo podem morder

A programação linear repousa em pressupostos que costumam ser razoáveis mas que às vezes se quebram, e conhecê-los mantém um modelo honesto.

O primeiro é a proporcionalidade: a contribuição de cada variável ao objetivo e a cada restrição é estritamente proporcional ao seu valor, então dobrar uma variável dobra o seu efeito, sem economias de escala, custos de preparação nem retornos decrescentes.

O segundo é a aditividade: o efeito total é a soma dos efeitos individuais, sem termos de interação onde dois produtos juntos usem mais ou menos que a soma do que cada um usa sozinho. O terceiro é a divisibilidade: as variáveis podem assumir valores fracionários, então o método pode devolver 2,5 unidades, o que está bem para toneladas de uma mistura mas não para máquinas ou pessoas inteiras.

Quando a divisibilidade falha, porque a resposta deve ser um número inteiro, o problema vira programação inteira, que é genuinamente mais difícil e precisa de outros algoritmos; arredondar uma solução de programação linear pode dar uma resposta inviável ou longe do ótimo, então deve ser feito com cuidado e verificado.

Quando a proporcionalidade ou a aditividade falham, por custos de preparação, saltos de preço ou atividades que interagem, a resposta honesta é um modelo mais elaborado, às vezes com variáveis binárias ou aproximações lineares por partes, em vez de forçar um ajuste linear.

O pressuposto de certeza, de que todos os coeficientes são conhecidos exatamente, também vale a pena lembrar: dados reais são estimados, que é justamente por que importam a análise de sensibilidade e os preços-sombra, já que mostram o quanto o plano é sensível aos números dos quais você está menos seguro. Esta calculadora resolve o modelo linear com fidelidade; julgar se o modelo linear se encaixa na sua situação é trabalho do analista, e esses pressupostos são a lista de verificação para isso.

Erros comuns a evitar

Um punhado de erros se repete e produz em silêncio respostas erradas ou enganosas. Fique atento a eles.

• Coeficientes desalinhados. Os coeficientes de cada linha de restrição devem coincidir exatamente com a ordem das variáveis do objetivo. Uma coluna deslocada resolve um problema diferente sem nenhuma mensagem de erro.
• Esquecer uma restrição. Um resultado ilimitado geralmente significa que um limite real foi deixado de fora. Todo problema prático tem algo que impede o objetivo de crescer para sempre.
• Arredondar uma resposta fracionária. Se as variáveis devem ser inteiras, arredondar a solução linear pode ser inviável ou subótimo. Isso é um programa inteiro, não um linear.
• Ignorar os preços-sombra. O mix ótimo sozinho não diz onde investir. Os preços-sombra ordenam os gargalos; pulá-los desperdiça o resultado mais acionável.
• Direção de otimização errada. Maximizar um custo ou minimizar um lucro dá uma resposta tecnicamente correta à pergunta errada. Confirme que a direção coincide com a meta.
• Restrições de igualdade apertadas demais. Escrever = onde se queria <= ou >= pode tornar inviável um problema resolúvel. Use a igualdade só quando o requisito realmente precisar ser cumprido exatamente.
• Tratar estimativas como exatas. Os coeficientes costumam ser estimados, então um plano ótimo para um conjunto de números pode não ser para outro. Verifique o quanto a resposta é sensível antes de se comprometer.

De uma pergunta de negócio a um modelo resolúvel

A parte mais difícil de usar este método raramente é a aritmética, que a calculadora resolve; é traduzir uma pergunta real e desorganizada nas três peças limpas de que o modelo precisa. Comece pelo objetivo perguntando qual quantidade única a decisão realmente tenta mover, e em qual direção.

Se um gerente de fábrica diz que quer operar com eficiência, insista no substituto mensurável, é maximizar a margem de contribuição, maximizar unidades enviadas ou minimizar o custo de hora extra?, porque o modelo otimiza exatamente uma coisa e a escolha muda a resposta.

Resista a juntar várias metas em um objetivo; se dois fins genuinamente competem, modele o menos importante como uma restrição com um limiar em vez de misturar ambos no objetivo, o que turva os preços-sombra.

Depois nomeie as variáveis de decisão, as alavancas que o tomador de decisão realmente controla.

Costumam ser quantidades, quantos de cada produto fabricar, quantas horas rodar cada linha, quanto de cada ingrediente misturar, e ajuda escrever cada uma em palavras com a sua unidade antes de torná-la símbolo, porque uma variável cuja unidade não está clara tende a produzir uma restrição cujo significado também não está.

Depois escreva as restrições percorrendo cada limite que a decisão enfrenta: os recursos que podem acabar, a demanda que deve ser atendida, as razões que devem valer, os mínimos que um contrato exige. Cada uma vira uma linha, e o coeficiente de uma variável nessa linha é simplesmente quanto do recurso uma unidade dessa variável consome.

Uma disciplina útil é verificar as unidades de cada restrição como um engenheiro verifica uma fórmula: o lado esquerdo e o direito devem medir a mesma coisa, horas contra horas disponíveis, quilogramas contra quilogramas disponíveis. Uma restrição que mistura unidades é um erro de modelagem que o solucionador não pode detectar, porque para o algoritmo são só números.

Por fim, contraste o plano resolvido com a intuição antes de confiar nele: se o ótimo ignora um produto que você esperava fabricar, ou leva uma variável a um extremo implausível, isso costuma ser o modelo ensinando você algo, seja uma ideia genuína ou um sinal de que falta ou está mal escalada uma restrição.

Ler a solução com senso crítico, não só aceitar o número, é o que transforma a calculadora de uma máquina de respostas em um auxílio para pensar.

Onde este modelo se encaixa nas ferramentas

A programação linear é o motor geral de otimização da pesquisa operacional, e vários dos outros modelos clássicos são na verdade casos especiais dela com outra roupa. O hub de Pesquisa Operacional os agrupa por essa razão.

O problema de transporte, enviar de origens a destinos ao mínimo custo, e o de designação, emparelhar um conjunto com outro um a um, são ambos programas lineares com uma estrutura de rede tão específica que existem algoritmos dedicados mais rápidos para eles; quando o seu problema tem essa forma, essas ferramentas o resolvem mais diretamente, mas a resposta que dão é a mesma que o simplex geral daria.

Quando o seu problema não se encaixa em uma estrutura especial, esta calculadora geral de programação linear é a ferramenta certa.

Além do grupo de otimização, a programação linear se conecta com o resto das ferramentas de engenharia industrial por meio das decisões que informa. Os limites de recursos que você informa como restrições costumam vir de estudos de capacidade, e as cifras de demanda da previsão; o plano que ela produz alimenta decisões de programação e estoque tratadas em outra parte da rede.

A análise de decisão assume quando o futuro é incerto e são as probabilidades, não restrições fixas, que guiam a escolha, e a teoria das filas responde às perguntas de capacidade que a programação linear supõe dadas. Visto assim, a programação linear está no centro do planejamento: converte os limites que outros análises estabelecem no único melhor plano, e os seus preços-sombra apontam de volta para qual desses limites vale a pena mudar.

Volte ao hub de Pesquisa Operacional para o conjunto completo de modelos.

Uma breve história do método

A programação linear como método geral data da década de 1940, e a sua história está ligada tanto à logística de guerra quanto à economia do pós-guerra.

O passo decisivo foi a formulação do método simplex por George Dantzig em 1947, que deu ao campo pela primeira vez um algoritmo prático e de propósito geral; o trabalho anterior de Leonid Kantorovich na União Soviética havia proposto problemas de otimização semelhantes, e as duas linhas de pensamento, junto com a interpretação econômica desenvolvida por Tjalling Koopmans, deram forma à disciplina.

Kantorovich e Koopmans dividiram um prêmio Nobel de economia em 1975 por essa contribuição, um raro reconhecimento do impacto de uma técnica essencialmente matemática em como os recursos são alocados.

O método se espalhou rápido porque respondia a uma pergunta universal, como fazer o máximo com meios limitados, e porque o algoritmo simplex se mostrou notavelmente veloz na prática apesar de resultados teóricos posteriores mostrarem que ele podia ser lento em piores casos artificiais. Esses piores casos motivaram os métodos de ponto interior desenvolvidos na década de 1980, que são comprovadamente eficientes e são usados ao lado do simplex nos solucionadores modernos de grande escala.

Para o tamanho de problema que uma pessoa digita em uma calculadora, o método simplex que esta ferramenta usa é ao mesmo tempo rápido e transparente, produzindo não só o ótimo, mas os preços-sombra e a lógica canto a canto que fazem da programação linear uma ferramenta explicativa tanto quanto computacional.

Essa combinação de uma ideia geométrica clara, um algoritmo prático e uma interpretação econômica limpa pela dualidade é a razão de a programação linear continuar sendo, décadas depois, o primeiro método de otimização que todo estudante de pesquisa operacional aprende.

Formato de entrada e referência rápida

Informe o objetivo como uma linha de coeficientes, um por variável, separados por espaços ou vírgulas, e escolha maximizar ou minimizar acima. Informe cada restrição na sua própria linha como os coeficientes das variáveis na mesma ordem, depois o operador, depois o valor do lado direito; use ≤, ≥ ou = (também são aceitos <, > e as palavras). As variáveis são tomadas automaticamente como não negativas. A referência abaixo resume o que cada parte do resultado significa.

Perguntas frequentes

Fontes, aviso legal e transparência editorial

Esta calculadora resolve programas lineares com o método simplex de duas fases e reporta os preços-sombra como as variáveis duais ótimas, seguindo referências padrão de pesquisa operacional (o método simplex de Dantzig; a teoria primal-dual da programação linear). Esta calculadora e este guia são criados e revisados pela equipe da OpsCalculators; consulte a nossa Política Editorial para saber como cada ferramenta é pesquisada, construída e testada.

Os resultados são estimativas precisas para planejamento e educação, não consultoria de engenharia certificada, e a ferramenta resolve o modelo linear contínuo; se as suas variáveis devem ser inteiras o problema é um programa inteiro e arredondar pode não ser ótimo. Valide contra os seus próprios dados antes de se comprometer. Consulte o nosso Aviso Legal completo. OpsCalculators.com é operado pela MAFHH INTERNATIONAL LTD. Os seus dados são processados no seu navegador e nunca são guardados; consulte a nossa Política de Privacidade.