Logo Passei Direto
Buscar

Ferramentas de estudo

Questões resolvidas

Para solucionar problemas de PL com o método simplex, seguimos cinco etapas fundamentais. Acompanhe! Formulação do problema: Etapa em que se traduz o problema do mundo real para a linguagem matemática da programação linear. Definimos as variáveis que representam as quantidades a serem otimizadas (por exemplo, a produção de diferentes produtos), a função objetivo que queremos maximizar ou minimizar (por exemplo, o lucro total), e as restrições que limitam as variáveis (por exemplo, a disponibilidade de matéria-prima, a mão de obra ou o tempo). Conversão para a forma padrão: Etapa em que são realizadas transformações algébricas para garantir que o problema esteja na forma padrão, facilitando a aplicação do algoritmo. Aqui, percebemos que nem todo problema de PL está formulado da maneira ideal para o método simplex. Encontrando uma solução viável: Etapa em que o primeiro passo para a escalada rumo à solução ótima é encontrar um ponto de apoio na região viável, ou seja, um conjunto de valores para as variáveis que respeitam todas as restrições do problema. O método simplex dispõe de técnicas específicas para encontrar essa solução inicial viável. Otimização da solução: Etapa em que, a partir da solução viável inicial, o método simplex inicia sua jornada iterativa. A cada iteração, ele avalia as variáveis básicas (aquelas que estão no valor limite imposto por alguma restrição) e não básicas (aquelas que ainda possuem folga). Ele identifica oportunidades de substituir variáveis não básicas por básicas, desde que isso melhore o valor da função objetivo. Esse processo continua até que nenhuma melhoria seja possível, indicando que a solução ótima foi alcançada. Análise da solução: Chegamos ao pico da montanha! Etapa em que se analisa a solução encontrada para garantir que ela seja realmente ótima. O método simplex fornece indicadores para verificar se a solução é ótima local (a melhor em um entorno específico) ou global (a melhor considerando todas as possibilidades). Em alguns casos, pode ser necessário realizar análises complementares para garantir a otimização global.
Quais são as cinco etapas fundamentais do método simplex para a solução de problemas de programação linear?

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

Para solucionar problemas de PL com o método simplex, seguimos cinco etapas fundamentais. Acompanhe! Formulação do problema: Etapa em que se traduz o problema do mundo real para a linguagem matemática da programação linear. Definimos as variáveis que representam as quantidades a serem otimizadas (por exemplo, a produção de diferentes produtos), a função objetivo que queremos maximizar ou minimizar (por exemplo, o lucro total), e as restrições que limitam as variáveis (por exemplo, a disponibilidade de matéria-prima, a mão de obra ou o tempo). Conversão para a forma padrão: Etapa em que são realizadas transformações algébricas para garantir que o problema esteja na forma padrão, facilitando a aplicação do algoritmo. Aqui, percebemos que nem todo problema de PL está formulado da maneira ideal para o método simplex. Encontrando uma solução viável: Etapa em que o primeiro passo para a escalada rumo à solução ótima é encontrar um ponto de apoio na região viável, ou seja, um conjunto de valores para as variáveis que respeitam todas as restrições do problema. O método simplex dispõe de técnicas específicas para encontrar essa solução inicial viável. Otimização da solução: Etapa em que, a partir da solução viável inicial, o método simplex inicia sua jornada iterativa. A cada iteração, ele avalia as variáveis básicas (aquelas que estão no valor limite imposto por alguma restrição) e não básicas (aquelas que ainda possuem folga). Ele identifica oportunidades de substituir variáveis não básicas por básicas, desde que isso melhore o valor da função objetivo. Esse processo continua até que nenhuma melhoria seja possível, indicando que a solução ótima foi alcançada. Análise da solução: Chegamos ao pico da montanha! Etapa em que se analisa a solução encontrada para garantir que ela seja realmente ótima. O método simplex fornece indicadores para verificar se a solução é ótima local (a melhor em um entorno específico) ou global (a melhor considerando todas as possibilidades). Em alguns casos, pode ser necessário realizar análises complementares para garantir a otimização global.
Quais são as cinco etapas fundamentais do método simplex para a solução de problemas de programação linear?

Prévia do material em texto

Método simplex
Você vai estudar a programação linear (PL), uma técnica de otimização que aponta as relações entre
variáveis como relações lineares, o que simplifica sua modelagem e permite o uso de métodos
computacionais eficazes para encontrar a solução ótima, como é o caso do método simplex.
Prof. Mauro Rezende Filho
1. Itens iniciais
Propósito
O estudo do método simplex permite capacitar estudantes e profissionais para resolver problemas complexos
de otimização linear de forma eficiente. Estudar o simplex contribui para o desenvolvimento de habilidades
analíticas e de resolução de problemas essenciais para diversas áreas, como engenharia, economia, logística
e gestão.
Objetivos
Reconhecer o método simplex para a resolução de problemas de PL.
 
Reconhecer como o método simplex atua na resolução de problemas de PL.
 
Aplicar o método simplex na resolução de problemas de PL.
Introdução
A modelagem matemática nos permite representar, de forma simplificada, um problema complexo por meio de
linguagem matemática. Com isso, conseguimos analisar diferentes cenários de forma mais rápida e barata do
que se a situação fosse avaliada na realidade, auxiliando-nos, assim, no processo de tomada de decisão.
 
No contexto da programação linear (PL), que se aplica, por exemplo, no planejamento de redes logísticas, há
métodos, como o método gráfico, que se restringem à solução de problemas com apenas duas ou no máximo
três variáveis de decisão. Como solucionar, então, problemas mais complexos, com maior número de variáveis
de decisão? Esse é o assunto a ser tratado neste conteúdo. A seguir, abordaremos o método simplex para a
solução de problemas de PL e aprenderemos a utilizar o solver do Excel para a solução desse tipo de
problema. Acompanhe!
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
• 
• 
• 
1. O método simplex para a solução de problemas de PL
Conceito e história do método simplex
Antes da década de 1940, a otimização linear era um território inexplorado. Resolver problemas que envolviam
a alocação ideal de recursos, como a produção de bens ou o planejamento de transporte, era um processo
lento e ineficiente. Então, em 1947, concebido por George Dantzig, surgiu o método simplex como um
algoritmo revolucionário para desbravar esse universo.
Visualizando o método simplex
Imagine um poliedro tridimensional, como um cubo ou uma pirâmide. Cada face desse poliedro representa
uma solução possível para um problema de programação linear (PL). O método simplex funciona como um
alpinista experiente explorando esse terreno. Seu objetivo é encontrar o vértice (um ponto em que as faces
encontram-se) que represente a melhor solução, aquela que otimiza determinado critério, como o lucro
máximo ou o menor custo.
 
Para percorrer esse terreno de forma estratégica, o método simplex adota um processo iterativo. Em cada
iteração, ele avalia a altitude de cada vértice visitado, ou seja, o valor do objetivo (lucro, custo etc.) associado
àquela solução. Ele então se move para o vértice adjacente com um valor objetivo melhor, até alcançar o pico
mais alto — a solução ótima.
Desconstruindo o processo: as etapas do método simplex
Para solucionar problemas de PL com o método simplex, seguimos cinco etapas fundamentais. Acompanhe!
Formulação do problema
Etapa em que se traduz o problema do mundo real para a linguagem matemática da programação
linear. Definimos as variáveis que representam as quantidades a serem otimizadas (por exemplo, a
produção de diferentes produtos), a função objetivo que queremos maximizar ou minimizar (por
exemplo, o lucro total), e as restrições que limitam as variáveis (por exemplo, a disponibilidade de
matéria-prima, a mão de obra ou o tempo).
Conversão para a forma padrão
Etapa em que são realizadas transformações algébricas para garantir que o problema esteja na forma
padrão, facilitando a aplicação do algoritmo. Aqui, percebemos que nem todo problema de PL está
formulado da maneira ideal para o método simplex.
Encontrando uma solução viável
Etapa em que o primeiro passo para a escalada rumo à solução ótima é encontrar um ponto de apoio
na região viável, ou seja, um conjunto de valores para as variáveis que respeitam todas as restrições
do problema. O método simplex dispõe de técnicas específicas para encontrar essa solução inicial
viável.
Otimização da solução
Etapa em que, a partir da solução viável inicial, o método simplex inicia sua jornada iterativa. A cada
iteração, ele avalia as variáveis básicas (aquelas que estão no valor limite imposto por alguma
restrição) e não básicas (aquelas que ainda possuem folga). Ele identifica oportunidades de substituir
variáveis não básicas por básicas, desde que isso melhore o valor da função objetivo. Esse processo
continua até que nenhuma melhoria seja possível, indicando que a solução ótima foi alcançada.
Análise da solução
Chegamos ao pico da montanha! Etapa em que se analisa a solução encontrada para garantir que ela
seja realmente ótima. O método simplex fornece indicadores para verificar se a solução é ótima local
(a melhor em um entorno específico) ou global (a melhor considerando todas as possibilidades). Em
alguns casos, pode ser necessário realizar análises complementares para garantir a otimização global.
O método simplex não é apenas uma ferramenta teórica, ele tem um vasto leque de aplicações práticas em
diversos setores. Vamos conhecê-los!
Economia
O método é utilizado pelas empresas para otimizar a alocação de recursos em processos produtivos,
definir estratégias de investimento e planejar o mix de produtos a serem fabricados.
Engenharia
O método auxilia a otimização de projetos de estruturas, como pontes e edifícios, para minimizar o
uso de materiais e garantir a resistência necessária. Também é utilizado para dimensionar peças
industriais e planejar processos de manufatura de forma eficiente.
Logística
O método é utilizado pelas empresas de transporte para definir rotas de entrega otimizadas,
minimizando as distâncias percorridas e os custos com combustível. Também é aplicado no
planejamento de frotas de veículos, garantindo que se tenha a quantidade ideal de caminhões, vans
etc.
Pesquisa operacional
O método é uma ferramenta basilar na pesquisa operacional, área que busca soluções otimizadas
para problemas complexos em diversos ramos, como: saúde, finanças, manufatura e gestão de
projetos.
O simplex na indústria
Agora, vamos conferir alguns exemplos de simplex na indústria.
Empresas
A gigante Amazon utiliza o método simplex para
otimizar sua complexa rede de logística,
garantindo entregas rápidas e eficientes a seus
clientes.
Governos
Diversos países, com o aval de seus
governantes, utilizam o método simplex para
otimizar a alocação de recursos públicos em
diferentes áreas, como: saúde, educação e
infraestrutura.
Organizações sem fins lucrativos
O método simplex auxilia ONGs na otimização
de seus recursos, para que possam maximizar o
impacto de seus programas e serviços na
sociedade.
Impacto transformador do método simplex
O método simplex impactou significativamente diversos setores, impulsionando avanços consideráveis, como:
Melhoria na tomada de decisão
As informações precisas fornecidas pelo método simplex embasam as decisões estratégicas,
permitindo que empresas e organizações escolham as melhores alternativas com maior segurança.
Redução de custos
A otimização proporcionada pelo método simplex leva à redução de custos em diversos processos,
aumentando a lucratividade e a competitividade das empresas.
Aumento da produtividade
A otimização dos processos proporcionada pelo método simplex aumenta a produtividade, gerando
mais resultados com os mesmos recursos.
Aumento da competitividade
A utilização do método simplex pelas empresas pode propiciar uma vantagem competitiva no
mercado, pois são capazes de operar de forma mais eficiente e eficaz.
Método simplex: considerações importantes
Como toda ferramenta, o método simplex também possui limitações, como sere espaço de armazenamento. 
 
Dados:
 
Lucro por medicamento:
 
Medicamento A: R$ 10
Medicamento B: R$ 15
Medicamento C: R$ 20
 
Custo por medicamento:
 
Medicamento A: R$ 5
Medicamento B: R$ 7
Medicamento C: R$ 10
 
Orçamento disponível: R$ 1000
 
Espaço de armazenamento disponível: 100 m²
 
Espaço ocupado por medicamento:
 
Medicamento A: 0,5 m²
Medicamento B: 1 m²
Medicamento C: 2 m²
 
Faça uma modelagem matemática para solucionar o problema.
Chave de resposta
Variáveis de decisão:
• 
• 
• 
• 
• 
x1: Quantidade de medicamentos A a serem comprados.
x2: Quantidade de medicamentos B a serem comprados.
x3: Quantidade de medicamentos C a serem comprados.
Modelo matemático: função objetivo (maximizar lucro):
Restrições:
Orçamento:
Espaço de armazenamento:
Não negatividade:
Questão 4
Uma empresa precisa determinar a quantidade ideal de cada ingrediente a ser utilizado na produção de um
novo tipo de biscoito, de modo a minimizar o custo total da mistura e atender às restrições nutricionais e de
sabor. 
 
Dados:
 
• 
• 
• 
• 
Ingredientes:
 
Farinha de trigo
 
Açúcar
 
Cacau em pó
 
Manteiga
 
Custo por kg de ingrediente:
 
Farinha de trigo: R$ 2,00
 
Açúcar: R$ 3,00
 
Cacau em pó: R$ 5,00
 
Manteiga: R$ 8,00
 
Restrições nutricionais:
 
Teor de gordura máximo: 20%
 
Teor de açúcar máximo: 30%
 
Teor de cacau em pó mínimo: 10%
 
Restrição de sabor:
 
A proporção de farinha de trigo e açúcar deve ser entre 2:1 e 3:1.
Chave de resposta
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Variáveis de decisão:
x1: Quantidade de farinha de trigo a ser utilizada (kg)
x2: Quantidade de açúcar a ser utilizada (kg)
x3: Quantidade de cacau em pó a ser utilizada (kg)
x4: Quantidade de manteiga a ser utilizada (kg)
Modelo matemático: função objetivo (minimizar custo total):
Restrições:
Teor de gordura:
Teor de açúcar:
Teor de cacau em pó:
Proporção farinha/açúcar:
Não negatividade:
• 
• 
• 
• 
Questão 5
Uma empresa precisa determinar a alocação ideal de seu orçamento de marketing entre diferentes canais
(como TV, rádio, internet e mídia impressa) para maximizar o retorno sobre o investimento (ROI).
 
Dados:
 
Orçamento total de marketing: R$ 100.000
Custo por clique (CPC) em cada canal:
TV: R$ 10
Rádio: R$ 5
Internet: R$ 2
Mídia impressa: R$ 3
Taxa de conversão (CR) em cada canal:
TV: 2%
Rádio: 1%
Internet: 5%
Mídia impressa: 3%
Valor médio de uma venda: R$ 100
 
Qual modelagem matemática maximiza o ROI?
Chave de resposta
Variáveis de decisão:
x1: Quantidade de cliques a serem comprados na TV.
x2: Quantidade de cliques a serem comprados no rádio.
x3: Quantidade de cliques a serem comprados na internet.
• 
• 
• 
• 
• 
• 
• 
x4: Quantidade de cliques a serem comprados na mídia impressa.
Modelo matemático:
Função objetivo (maximizar ROI):
Restrições:
Orçamento:
Não negatividade:
Questão 6
Uma empresa de sucos precisa determinar a quantidade ideal de laranjas para polpa e suco concentrado para
minimizar o custo total de produção de um litro de suco de laranja. 
 
Dados:
 
Custo por kg de laranja para polpa: R$ 0,50
 
Custo por litro de suco concentrado: R$ 2,00
 
Rendimento:
• 
• 
• 
 
1 kg de laranja para polpa rende 0,8 litro de suco.
 
1 litro de suco concentrado misturado com água rende 5 litros de suco final.
 
Quantidade de suco final a ser produzida: 100 litros.
 
Qual modelagem matemática determinaria a melhor solução para o problema?
Chave de resposta
Variáveis de decisão:
x1: Quantidade de kg de laranja para polpa a ser usada (kg).
x2: Quantidade de litros de suco concentrado a ser usada (litros).
Modelo matemático:
Função objetivo (minimizar custo total):
Restrições:
Quantidade de suco da polpa:
Como são necessários 100 litros de suco final, e o suco concentrado representa 4/5 do volume final (pois é
diluído em água), precisamos de: 0.8x1 \geq (4/5) * 100 litros = 80 litros
Quantidade de suco do concentrado:
x2 * 5 = suco do concentrado diluído
• 
• 
• 
• 
• 
• 
• 
• 
x2 * 5 = (1/5) * 100 litros = 20 litros (já que o suco concentrado representa 1/5 do volume final)
Não negatividade:
Neste vídeo, veja a resolução da questão!
https://play.yduqs.videolib.live/player?token=991660c7a7a34b80abbe3d8601f40b8c
Teoria na prática
Uma lanchonete oferece três tipos de lanches: sanduíche de frango, hambúrguer simples e hambúrguer
completo. O proprietário quer maximizar o lucro diário, considerando que o estoque de ingredientes é limitado.
 
Aqui estão os dados:
 
Lucro por lanche:
 
· Sanduíche de frango: R$ 8,00
· Hambúrguer simples: R$ 10,00
· Hambúrguer completo: R$ 15,00
 
Estoque de ingredientes disponíveis para o dia:
 
· Pão: 100 unidades
· Peito de frango desfiado: 20 kg
· Carne de hambúrguer: 30 kg
· Queijo: 15 kg
· Alface: 5 kg
· Tomate: 8 kg
 
Ingredientes necessários por lanche:
 
· Sanduíche de frango: 1 pão, 0,2 kg de peito de frango, 0,1 kg de queijo e 0,05 kg de alface.
· Hambúrguer simples: 1 pão, 0,3 kg de carne, 0,1 kg de queijo, 0,05 kg de alface e 0,05 kg de tomate.
· Hambúrguer completo: 1 pão, 0,4 kg de carne, 0,2 kg de queijo, 0,1 kg de alface e 0,1 kg de tomate.
• 
• 
• 
 
Como maximizar o lucro?
Chave de resposta
Neste vídeo, confira a resolução a seguir!
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Suponha que uma empresa fabrica dois tipos de produtos: camisetas e calças. O objetivo é determinar a
quantidade de cada produto a ser produzida para maximizar o lucro total da empresa, sujeito a certas
restrições.
 
Aqui estão os dados:
 
O lucro por unidade de camiseta é $5 e por unidade de calça é $8.
Para produzir uma camiseta, são necessários 2 metros de tecido e 1 hora de trabalho.
Para produzir uma calça, são necessários 3 metros de tecido e 2 horas de trabalho.
A empresa tem 100 metros de tecido e 80 horas de trabalho disponíveis por semana.
 
O lucro da fábrica será igual a:
A 266, 67
B 266,00
C 305,48
D 305,00
E 180,00
A alternativa B está correta.
Vamos ao modelo matemático do problema, que envolve programação linear.
Considere:
x = quantidade de camisetas a serem produzidas.
y = quantidade de calças a serem produzidas.
Nossa função objetivo é maximizar o lucro total, dado por:
Sujeito às seguintes restrições:
Restrição de tecido: (não podemos usar mais de 100 metros de tecido).
Restrição de trabalho: (não podemos exceder 80 horas de trabalho).
Além disso, as variáveis devem ser não negativas e inteiras: e y .
Agora, você pode usar o LINDO para encontrar os valores ótimos de x e y que maximizam o lucro total Z.
Resolvendo, obtemos:
• 
• 
• 
• 
• 
Questão 2
Suponha que uma empresa fabrique três tipos de produtos: X, Y e Z. O objetivo é determinar a quantidade de
cada produto a ser produzida para maximizar o lucro total da empresa, sujeito a certas restrições. Aqui estão
os dados:
 
O lucro por unidade de produto X é $10, por unidade de produto Y é $12, e por unidade de produto Z é
$15.
 
Para produzir uma unidade de produto X, são necessárias 2 unidades do recurso A e 1 unidade do
recurso B.
 
Para produzir uma unidade de produto Y, são necessários 1 unidade do recurso A e 2 unidades do
recurso B.
 
Para produzir uma unidade de produto Z, são necessárias 3 unidades do recurso A e 2 unidades do
recurso B.
 
A empresa tem 200 unidades do recurso A e 150 unidades do recurso B disponíveis.
 
Assinale a alternativa correta:
A x = 83.333336, y =33.333332 e z = 2.333333
B x = 83.333336, y =33.333332 e z = 0,000000
C x = 82.333336, y =33.333332 e z = 1,000000
• 
• 
• 
• 
• 
D x = 82.000000, y =33.000000 e z = 1,000000
E x = 75.000000, y =28.000000 e z = 12,000000
A alternativa D está correta.
Então, vamos formular o problema como um problema de programação linear. 
Considere:
x = quantidade de unidades do produto X a serem produzidas
y = quantidade de unidades do produtoY a serem produzidas
z = quantidade de unidades do produto Z a serem produzidas
Nossa função objetivo é maximizar o lucro total, dado por:
Sujeito às seguintes restrições:
Restrição do recurso A: (não podemos usar mais de 200 unidades do recurso A).
Restrição do recurso B: (não podemos usar mais de 150 unidades do recurso B). Além
disso, as variáveis e devem ser não negativas e inteiras: x , y e z .
Agora, podemos usar o LINGO para encontrar os valores ótimos de x, y e z que maximizam o lucro total Z.
Temos, portanto, a seguinte solução:
• 
• 
• 
4. Conclusão
Considerações finais
O método simplex é amplamente reconhecido como um dos algoritmos fundamentais da pesquisa operacional
para resolver problemas de programação linear. A popularidade desse método decorre de sua capacidade de
otimizar uma variedade de problemas em diferentes setores, como transporte, logística, finanças e
manufatura, oferecendo uma abordagem sistemática para maximizar lucros ou minimizar custos. No entanto,
apesar de suas vantagens, o simplex enfrenta alguns desafios significativos que precisam ser superados para
garantir sua eficácia em cenários complexos.
 
Um desses desafios é a escalabilidade limitada do simplex, o que significa que ele pode enfrentar dificuldades
na resolução de problemas de grande porte com muitas variáveis e restrições. Nesses casos, podem ser
necessárias soluções alternativas ou até mesmo o uso de métodos mais avançados de otimização. Além
disso, o simplex está sujeito a armadilhas subótimas, cenário em que pode encontrar soluções que não são as
melhores possíveis no contexto do problema. Isso requer cautela na interpretação dos resultados e pode
exigir ajustes no modelo ou nos parâmetros do algoritmo.
 
Outro desafio crítico é a precisão computacional. Como o simplex realiza cálculos iterativos, ele é sensível a
erros de arredondamento e precisão numérica, o que pode impactar a qualidade da solução final. Portanto, é
preciso que analistas e pesquisadores estejam atentos aos detalhes durante a implementação do algoritmo
para evitar distorções nos resultados.
Por fim, a modelagem prévia adequada do problema como um modelo de programação linear é uma etapa
fundamental para o sucesso do método simplex. Isso envolve definir corretamente a função objetivo, as
variáveis de decisão e as restrições, garantindo que o modelo captura com precisão as complexidades do
problema real e orienta o simplex na direção da solução ótima.
Explore +
Não pare por aqui! Para você continuar explorando os assuntos abordados, recomendamos a leitura dos
seguintes artigos:
Maximization of a linear function of variables subject to linear inequalities, de Dantzig, G. B. (1947),
publicado no American Journal of Operations Research. O artigo introduz o conceito de programação
linear como técnica fundamental para otimizar problemas com restrições lineares. Vale a pena conferir!
 
The many facets of linear programming, de Todd (1976), publicado no jornal acadêmico Management
Science. O artigo discute as diferentes formulações da programação linear, apresenta o conceito de
dualidade e aborda a importância desse tipo de programação na tomada de decisão em diversas áreas,
como finanças, logística e engenharia.
Referências
BAZARAA, M. S.; JARVIS, J. J.; SHERALI, H. D. Linear programming and network flows. 4th ed. Hoboken, NJ:
Wiley, 2009.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to algorithms. 3rd ed. Cambridge, MA:
The MIT Press, 2009.
HILLIER, F. S.; LIEBERMAN, G. J. Introduction to operations research. 8th ed. New York, NY: McGraw-Hill
Higher Education, 2005.
• 
• 
KAGAN, N. et al. Métodos de otimização aplicados a sistemas elétricos de potência. São Paulo: Blucher, 2009.
TAHA, H. A. Operations research: an introduction. 10th ed. Upper Saddle River, NJ: Pearson, 2016.
	Método simplex
	1. Itens iniciais
	Propósito
	Objetivos
	Introdução
	Conteúdo interativo
	1. O método simplex para a solução de problemas de PL
	Conceito e história do método simplex
	Visualizando o método simplex
	Desconstruindo o processo: as etapas do método simplex
	Formulação do problema
	Conversão para a forma padrão
	Encontrando uma solução viável
	Otimização da solução
	Análise da solução
	Economia
	Engenharia
	Logística
	Pesquisa operacional
	O simplex na indústria
	Empresas
	Governos
	Organizações sem fins lucrativos
	Impacto transformador do método simplex
	Melhoria na tomada de decisão
	Redução de custos
	Aumento da produtividade
	Aumento da competitividade
	Método simplex: considerações importantes
	Conceito e história do método simplex
	Conteúdo interativo
	Vantagens e desvantagens do método simplex
	Conteúdo interativo
	Vantagens
	Eficiência
	Simplicidade
	Versatilidade
	Aplicações práticas
	Desvantagens
	Dificuldade com problemas grandes
	Soluções ótimas locais
	Sensibilidade a erros
	Limitações teóricas
	Complexidade de implementação
	Relação do método simplex com outros métodos de otimização
	Similaridades com outros métodos
	A reta
	Plano α
	Plano α
	Diferenças do método simplex
	Método do lagrange
	Programação linear mista
	Programação linear semidefinida
	Programação convexa
	Relação com a programação linear
	Método do gradiente
	Método das bissecções
	Algoritmos genéticos
	Relação do método simplex com outros métodos de otimização
	Conteúdo interativo
	Verificando o aprendizado
	2. Problemas de PL com o método simplex
	Teorema da fundamentalidade da PL
	Mergulhando na essência do teorema
	Existência de solução ótima
	Dualidade
	Exemplo 1: Maximização da produção
	Exemplo 2: Minimização de custos
	Exemplo 3: Modelagem matemática
	Teorema da fundamentalidade da PL
	Conteúdo interativo
	Condições de otimalidade
	Essência das condições
	Condições de primalidade
	Condições de dualidade
	Exemplos de maximização e minimização
	Maximização da produção
	Minimização de custos
	Aplicações práticas e relevância
	Exemplo detalhado
	Condições de otimalidade
	Conteúdo interativo
	Dualidade na PL
	O surgimento da dualidade
	Conceitos fundamentais
	Explorando as aplicações práticas
	Maximização da produção
	Minimização de custos
	Alocação de recursos em um hospital
	Interpretação das variáveis duais
	Relaxamento de restrições
	Dualidade e sensibilidade
	Problema de transporte com capacidades
	Problema de mistura de ração animal
	Desafios e considerações acerca do simplex
	Exemplo detalhado da dualidade na PL
	Limite inferior para o custo total de transporte
	Preços sombra das restrições
	Análise da solução dual
	Dualidade na PL
	Conteúdo interativo
	O software LINDO
	Regras do software LINDO para PL
	Definir o modelo
	Executar a solução
	Analisar a solução
	Geração de relatórios
	Análise de sensibilidade
	Programação
	O software LINDO
	Conteúdo interativo
	Resolução de problemas de PL com o método simplex
	Formulação do problema
	Conversão para a forma padrão
	Construção da tabela simplex
	Seleção da variável entrante
	Seleção da variável saliente
	Cálculo da razão pivô
	Atualização da tabela simplex
	Teste de otimalidade
	Resolução de problemas de PL com o método simplex
	Conteúdo interativo
	Verificando o aprendizado
	3. Aplicações do método simplex
	Conceitos básicos da programação linear (PL)
	Conceitos, formulação de problemas, métodos de resolução
	Conteúdo interativo
	Maximizar
	Minimizar
	Tipos de restrições
	Igualdade
	Desigualdade
	Não negatividade
	Exemplo 1
	Conteúdo interativo
	Formulação de problemas de PL
	Exemplo 2
	Conteúdo interativo
	Métodos de resolução de problemas de PL
	Método gráfico
	Método simplex
	Branch-and-bound
	Programação linear inteira mista (MILP)
	Considerações importantes para a escolha do método adequado
	Interpretação de resultados
	Solução ótima
	Valor da função objetivo
	Sensibilidade
	Interpretação de sombras
	Relatórios e outputs
	Mão na massa
	Teoria na prática
	Conteúdo interativo
	Verificando o aprendizado
	4. Conclusão
	Considerações finais
	Explore +
	Referênciasineficiente para resolver
problemas de PL com grande número de variáveis e restrições, exigindo recursos computacionais robustos, e
poder encontrar soluções ótimas que não são necessariamente ótimas em um contexto global, necessitando
de técnicas adicionais para garantir a solução ideal.
 
O método simplex é um marco na história da otimização linear, uma ferramenta promissora que contribuiu
consideravelmente para a eficiência e o progresso em diversas áreas. Apesar de suas limitações, o método
continua sendo um algoritmo fundamental para a resolução de problemas de PL, abrindo portas para um
futuro de decisões mais inteligentes e resultados otimizados.
 
Confira, a seguir, um esquema que usa o método simplex!
Esquema de um problema de transporte.
Na sequência, vamos dar continuidade ao nosso estudo entendendo melhor as vantagens e as desvantagens
do método.
Conceito e história do método simplex
Confira, neste vídeo, como o método simplex pode ser uma técnica poderosa no auxílio à tomada de decisões
complexas.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vantagens e desvantagens do método simplex
Confira neste vídeo as características básicas do método simplex!
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Como você já sabe, o método simplex revolucionou a otimização linear. Sua capacidade de resolver problemas
de programação linear (PL) com notável rapidez impulsionou o desenvolvimento de técnicas de otimização em
diversas áreas e suas vantagens são inúmeras. Acompanhe!
Vantagens
Chegou a hora de detalhar algumas das muitas vantagens do método simplex. Vamos lá!
1
Eficiência
O método simplex é um dos métodos mais eficientes para resolver problemas de PL,
especialmente quando comparado a métodos preexistentes.
 
A capacidade que o método tem de encontrar soluções ótimas rapidamente o torna ideal
para problemas que exigem respostas em tempo hábil.
 
A simplicidade do algoritmo facilita a implementação em softwares e ferramentas
computacionais.
• 
• 
• 
2 Simplicidade
O método simplex é baseado em conceitos matemáticos relativamente simples, o que o
torna fácil de entender e aprender.
 
A estrutura lógica e intuitiva do método facilita a implementação e o acompanhamento do
processo de resolução.
 
A simplicidade da ferramenta também o torna acessível a um público mais amplo, não
apenas a especialistas em matemática ou otimização.
3
Versatilidade
O método simplex pode ser aplicado a inúmeros problemas de PL em diferentes áreas.
 
A flexibilidade do método permite adaptá-lo a diferentes tipos de problemas e restrições.
 
A versatilidade do método o torna uma ferramenta basilar para diversos setores da
economia e da sociedade.
4
Aplicações práticas
O método simplex é utilizado em diversas áreas, como economia, engenharia, logística e
pesquisa operacional.
 
A aplicação prática contribui para a otimização de recursos, o aumento da produtividade e a
redução de custos.
 
O método simplex tem impacto significativo na tomada de decisões estratégicas em
diversas organizações.
E então, o que achou do método? Bastante positivo, não é mesmo? Mas tenha atenção às suas desvantagens,
afinal, nada é perfeito. 
Desvantagens
Agora, confira algumas das desvantagens que merecem nossa atenção ao escolher o método.
• 
• 
• 
• 
• 
• 
• 
• 
• 
1 Dificuldade com problemas grandes
O método simplex pode ser ineficiente para resolver problemas de PL com grande número de
variáveis e restrições. Nesses casos, o tempo de processamento pode ser excessivo,
tornando a solução inviável na prática.
 
A necessidade de recursos computacionais robustos pode limitar a aplicação do método em
problemas de grande escala.
2
Soluções ótimas locais
O método simplex pode encontrar soluções ótimas que não são necessariamente ótimas em
um contexto global. Em alguns casos, o método pode parar em um ponto que é ótimo
localmente, mas não é o melhor possível globalmente.
 
Técnicas adicionais, como o método das big-M ou o método das barreiras, podem ser
necessárias para garantir a solução ótima global.
3
Sensibilidade a erros
O método simplex pode ser sensível a erros de arredondamento e imprecisões nos dados.
 
Pequenas alterações nos dados podem levar a grandes mudanças na solução final.
 
É importante ter cuidado ao inserir dados e interpretar os resultados do método simplex.
4
Limitações teóricas
O método simplex não é capaz de resolver todos os problemas de PL.
 
Existem alguns tipos de problemas de PL para os quais o método simplex não é aplicável.
Nesses casos, outros métodos de otimização podem ser necessários.
• 
• 
• 
• 
• 
• 
• 
• 
• 
5Complexidade de implementação
A implementação eficiente do método simplex pode ser complexa, especialmente para
problemas de grande escala.
 
É importante ter conhecimento de matemática e programação para implementar o método
simplex de forma eficaz, e a necessidade de expertise pode limitar a aplicação do método
por usuários menos experientes.
O método simplex é uma ferramenta que apresenta muitas vantagens, mas algumas desvantagens, portanto,
sua escolha depende da natureza do problema a ser solucionado, dos recursos computacionais disponíveis e
da expertise do usuário. Antes de decidir, analise!
Relação do método simplex com outros métodos de
otimização
Embora muito vantajoso, o método simplex não é o único método de otimização disponível. Na sequência,
vamos explorar a relação do simplex com outros métodos de otimização, destacando suas similaridades,
diferenças e aplicações específicas. Vamos lá!
Similaridades com outros métodos
A maioria dos métodos de otimização, incluindo o simplex, baseia-se em princípios matemáticos como a teoria
dos conjuntos convexos e a programação linear, e o objetivo central de todos eles é encontrar a solução ótima
para um problema, seja maximizando uma função objetivo ou minimizando um custo.
Além disso, muitos desses métodos, incluindo o simplex, utiliza um processo iterativo para encontrar a
solução ótima, ajustando as variáveis a cada iteração até alcançar o ponto ideal.
A reta
É um conjunto de pontos convexo.
Plano α
É uma região convexa.
• 
• 
Plano α
É uma região côncava.
Diferenças do método simplex
O método simplex utiliza um algoritmo específico para navegar pelo politopo convexo (região viável — é um
objeto geométrico delimitado por um número finito de segmentos de linha reta ou plano) do problema de PL,
buscando o vértice com o melhor valor objetivo.
O simplex é considerado um dos métodos mais eficientes para resolver problemas de PL, especialmente
quando comparado a métodos preexistentes.
É preciso destacar ainda que o simplex, por ser baseado em conceitos matemáticos relativamente simples, é
mais fácil de entender e implementar.
 
Veja, a seguir, uma comparação do simplex com outros métodos.
Método Similaridades Diferenças Vantagens Desvantagens Aplicações
Método do
gradiente
Base
matemática,
objetivo
comum,
iteração.
Abordagem,
eficiência,
simplicidade.
Eficiente
para
funções não
lineares.
Sensível a erros,
pode convergir para
soluções ótimas
locais.
Otimização de
carteiras de
investimento,
planejamento
de produção e
logística.
Método
das
bissecções
Base
matemática,
objetivo
comum,
iteração.
Abordagem,
eficiência,
simplicidade.
Simples de
implementar.
Pode ser lento para
problemas com
grande número de
variáveis.
Encontrar
raízes de
equações,
determinar o
ponto de
máximo de
uma função
unimodal.
Algoritmos
genéticos
Base
matemática,
objetivo
comum.
Abordagem,
eficiência,
simplicidade.
Eficaz para
problemas
complexos.
Pode ser
computacionalmente
caro.
Otimização de
design de
produtos,
planejamento
de rotas
complexas,
seleção de
características
em problemas
de machine
learning.
Método do
ponto
interior
Base
matemática,
objetivo
comum,
iteração.
Abordagem,
eficiência.
Mais
eficiente
que o
simplex para
alguns
problemas.
Mais complexo de
implementar.
Problemasde
PL com
grande
número de
variáveis.
Método da
ramificação
e corte
Base
matemática,
objetivo
comum.
Abordagem,
eficiência.
Eficaz para
problemas
de PL com
estrutura
especial.
Pode ser lento para
alguns problemas.
Otimização de
problemas de
transporte,
planejamento
de produção.
Quadro: Comparação do método simplex com outros métodos de solução de problemas de otimização.
Mauro Rezende Filho
Ainda temos outras opções relevantes, como:
Método do lagrange
Encontra soluções para problemas com restrições de igualdade.
Programação linear mista
Resolve problemas com variáveis contínuas e discretas.
Programação linear semidefinida
Otimiza problemas com variáveis definidas por matrizes.
Programação convexa
Abrange uma gama de problemas com funções objetivas e restrições convexas.
Relação com a programação linear
O simplex é um dos principais métodos para resolver problemas de programação linear. Sua relação com a PL
é tão intrínseca que é frequentemente utilizado como sinônimo de resolução de problemas de PL.
O método é especialmente eficiente para resolver problemas de PL com um número limitado de variáveis e
restrições.
Vejamos algumas aplicações específicas de outros métodos!
Método do gradiente
Otimização de carteiras de investimento,
planejamento de produção e logística.
Método das bissecções
Encontro de raízes de equações, determinar o
ponto de máximo de uma função unimodal.
Algoritmos genéticos
Otimização de design de produtos,
planejamento de rotas complexas, seleção de
características em problemas de machine
learning.
A compreensão das similaridades, diferenças e aplicações específicas do simplex e de outros métodos de
otimização é fundamental para a escolha da ferramenta mais adequada para cada caso. Lembre-se disso!
Relação do método simplex com outros métodos de otimização
Confira, neste vídeo, os métodos aplicados em otimização linear.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Um empresário precisa otimizar a produção de sua fábrica para maximizar o lucro, considerando diversas
restrições de capacidade, demanda e matéria-prima. Ele tem à disposição diversos métodos de otimização,
mas qual deles é mais adequado para essa situação, considerando que o problema pode ser modelado como
um problema de programação linear de grande escala?
A Método simplex
B Busca local
C Programação dinâmica
D Algoritmo genético
E Ponto interior
A alternativa E está correta.
Como o simplex pode ser lento para resolver problemas de grande escala, o método ponto interior pode ser
uma alternativa mais eficiente para esse tipo de problema, pois converge à solução ótima mais
rapidamente.
Questão 2
Um cientista precisa determinar a estrutura molecular de um composto químico por meio de métodos
computacionais. Ele tem à disposição o método simplex e outros métodos de otimização. Qual método é mais
adequado para essa situação, considerando que o problema pode ser modelado como um problema de
otimização não linear com muitas variáveis?
A Método simplex
B Busca local
C Programação dinâmica
D Algoritmo genético
E Gradiente descendente
A alternativa D está correta.
O método simplex e o gradiente descendente não são adequados para problemas de otimização não linear
com muitas variáveis. O algoritmo genético é uma técnica robusta que pode lidar com esse tipo de
problema, buscando a solução ótima global por meio de uma simulação inspirada na evolução natural.
2. Problemas de PL com o método simplex
Teorema da fundamentalidade da PL
O teorema fundamental da programação linear (TFLP) é um pilar na área de otimização, fornecendo uma base
sólida para a resolução de problemas de maximização ou minimização de funções lineares sob restrições
lineares. Esse teorema garante que, se um problema de programação linear (PL) for viável e limitado, então ele
possui uma solução ótima, e essa solução pode ser encontrada por meio de um método finito de busca.
Mergulhando na essência do teorema
O TFLP pode ser dividido em duas partes principais, confira!
1
Existência de solução ótima
Todo problema de PL viável e limitado possui pelo menos uma solução ótima. Isso significa que
existe um conjunto de valores para as variáveis que maximiza ou minimiza a função objetivo nas
restrições impostas.
2
Dualidade
Para cada problema de PL, existe outro problema, chamado de problema dual, que fornece
informações sobre a solução ótima do problema original. A solução ótima do problema dual fornece
um limite inferior ou superior para o valor da função objetivo do problema original.
Agora, vejamos alguns exemplos para esclarecer o conceito.
Exemplo 1: Maximização da produção
1. Formulação do problema:
 
Variáveis de decisão:
x₁: quantidade de A produzida
 
x₂: quantidade de B produzida
Função objetivo:
Lucro = 2x₁ + 3x₂
Restrições:
 
Disponibilidade de recursos:
Matéria-prima: 2x₁ + x₂ ≤ 6
 
Mão de obra: x₁ + 2x₂ ≤ 8
• 
• 
• 
• 
• 
Demanda do mercado:
A: x₁ ≥ 1
 
B: x₂ ≥ 2
2. Resolução:
 
Utilizando o método do simplex, obtemos a solução ótima:
x₁ = 1
 
x₂ = 3
3. Verificação da solução:
Função objetivo:
Lucro = 1(2) + 3(3) = 11
Restrições:
Matéria-prima: 2(1) + 3 = 5 ≤ 6 (verdadeiro)
 
Mão de obra: 1 + 2(3) = 7 ≤ 8 (verdadeiro)
Demanda do mercado:
A: 1 ≥ 1 (verdadeiro)
 
B: 2 ≥ 2 (verdadeiro)
Exemplo 2: Minimização de custos
1. Formulação do problema:
 
Variáveis de decisão:
xᵢⱼ: quantidade de produtos transportada do armazém i para a loja j
Colocando a matriz, temos:
 Armazém 1 Armazém 2 Armazém 3
Loja 1 x11 x12 x13
Loja 2 x21 x22 x23
Loja 3 x31 x32 x33
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Loja 4 x41 x42 x43
Tabela: Dados do problema para minimização de custos.
Mauro Rezende Filho.
Função objetivo:
• Custo = 4x₁₁ + 6x₁₂ + 5x₁₃ + 7x₁₄ + 2x₂₁ + 3x₂₂ + 2x₂₃ + x₂₄ + 3x₃₁ + x₃₂ + 2x₃₃ + 3x₃₄
Restrições:
 
Demanda das lojas:
Loja 1: 2x₁₁ + x₁₂ + x₁₃ ≥ 4
 
Loja 2: x₂₁ + 3x₂₂ + x₂₃ ≥ 6
 
Loja 3: x₃₁ + x₃₂ + 2x₃₃ ≥ 5
 
Loja 4: x4₁ + 2x4₂ + 3x4₃ ≥ 7
Disponibilidade dos armazéns:
Armazém 1: x₁₁ + x₂₁ + x₃₁ + x4₁ ≤ 8
 
Armazém 2: x₁₂ + 3x₂₂ + x₃₂ + x4₂ ≤ 12
 
Armazém 3: 2x₁₃ + x₂₃ + x₃₃+ 2x4₃≤ 10
Colocando de forma matricial, temos:
 
2. Resolução:
Utilizando o método simplex, obtemos a solução ótima:
x₁₂ = 4
 
x₂₃ = 5
 
x₃₂ = 1
x₃₃ = 4
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
x42 = 7
3. Verificação da solução:
 
Função objetivo:
Custo = 4X2 + 5X1 + 1X2 + 4X2 +7X1 = 30
Restrições:
Apresentando as restrições de forma matricial, temos que todas as restrições foram atendidas. Observe!
 Armazém 1 Armazém 2 Armazém 3 Total 
Loja 1 0 4 0 4
Loja 2 0 0 5 5
Loja 3 0 1 4 5
Loja 4 0 7 0 7
Total 0 12 9 21
Tabela: Restrições de forma matricial.
Mauro Rezende Filho.
Exemplo 3: Modelagem matemática
Formulação do problema:
 
Variáveis de decisão:
 x₁: quantidade de milho (kg)
 
x₂: quantidade de soja (kg)
 
x₃: quantidade de farelo de algodão (kg)
Função objetivo:
Custo = 2x₁ + 3x₂ + 4x₃
Restrições:
 
Nutrição:
Proteína: 0.2x₁ + 0.4x₂ + 0.5x₃ ≥ 12
• 
• 
• 
• 
• 
• 
• 
 
Energia: 3x₁ + 4x₂ + 5x₃ ≥ 20
Disponibilidade:
Milho: x₁ ≤ 8
 
Soja: x₂ ≤ 6
 
Farelo de algodão: x₃ ≤ 5
2. Resolução:
 
Utilizando o método simplex ou o solver, obtemos a solução ótima:
x₁ = 4
 
x₂ = 2
 
x₃ = 3
3. Verificação da solução:
 
Função objetivo:
Custo = 2(4) + 3(2) + 4(3) = 26
Restrições:
 
Nutrição:
Proteína: 0.2(4) + 0.4(2) + 0.5(3) = 1.6 + 0.8 + 1.5 = 3.9 ≥ 12 (verdadeiro)
 
Energia: 3(4) + 4(2) + 5(3) = 12 + 8 + 15 = 35 ≥ 20 (verdadeiro)
Disponibilidade:
Milho: 4 ≤ 8 (verdadeiro)
 
Soja: 2 ≤ 6 (verdadeiro)
 
Farelo de algodão: 3 ≤ 5 (verdadeiro)
Interpretação da solução:
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
A dieta ótima para as vacas leiteiras consiste em 4 kg de milho, 2 kg de soja e 3 kg de farelo de algodão. Essa
dieta fornece os nutrientes necessários para as vacas e tem um custo mínimo de R$ 26.
 
O TFLP éutilizado em diversas áreas, como:
Logística: otimização de rotas de transporte, alocação de recursos em armazéns.
 
Finanças: otimização de carteiras de investimento, gestão de riscos.
 
Indústria: otimização da produção, planejamento de recursos.
 
Engenharia: projeto de estruturas, planejamento de obras.
Teorema da fundamentalidade da PL
Confira, neste vídeo, um exemplo de aplicação do teorema fundamental da programação linear (TFLP).
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Condições de otimalidade
Em problemas de otimização, encontrar a solução ótima é fundamental para alcançar o melhor resultado
possível. As condições de otimalidade fornecem um conjunto de critérios que garantem que uma solução seja
realmente ótima.
Essência das condições
As condições de otimalidade podem ser divididas em dois tipos: primalidade e dualidade. Conheça-as!
1
Condições de primalidade
Envolvem:
 
Condição de viabilidade: a solução deve satisfazer todas as restrições do problema.
Condição de complementaridade: para cada restrição, o produto entre a folga (diferença
entre o limite da restrição e o valor da variável) e o multiplicador de Lagrange deve ser igual a
zero.
Condição de estacionariedade: a derivada da função objetivo em relação a cada variável,
considerando as restrições, deve ser igual a zero.
• 
• 
• 
• 
• 
• 
• 
2 Condições de dualidade
Envolvem:
 
Dualidade fraca: o valor da função objetivo no problema primal é sempre maior ou igual ao
valor da função objetivo no problema dual.
Dualidade forte: se os problemas primal e dual forem viáveis e limitados, então os valores
das funções objetivo no primal e no dual serão iguais.
Condições de complementaridade dual: similar à primalidade, mas para as variáveis duais e
folgas das restrições duais.
Exemplos de maximização e minimização
Vamos exemplificar ambos os casos. Observe!
Maximização da produção
Considere o problema de maximizar a produção
de uma fábrica com duas máquinas, A e B,
sujeito a restrições de tempo e recursos. As
condições de primalidade garantem que a
solução escolhida seja a que maximize a
produção, respeitando as restrições de tempo e
recursos. As condições de dualidade fornecem
informações sobre o valor máximo da produção
e sobre os preços sombra dos recursos.
Minimização de custos
Considere o problema de minimizar o custo de
transporte de produtos entre armazéns e lojas.
As condições de primalidade garantem que a
solução escolhida seja a que minimize o custo
de transporte, respeitando as restrições de
demanda e disponibilidade. As condições de
dualidade fornecem informações sobre o custo
mínimo de transporte e sobre os preços sombra
das restrições de demanda e disponibilidade.
Aplicações práticas e relevância
As condições de otimalidade são utilizadas em diversas áreas, como:
Logística: otimização de rotas de transporte e alocação de recursos em armazéns.
 
Finanças: otimização de carteiras de investimento e gestão de riscos.
 
Indústria: otimização da produção e planejamento de recursos.
 
Engenharia: projeto de estruturas e planejamento de obras.
Agora, vamos a algumas considerações importantes para ajudar você a sintetizar. 
As condições de otimalidade são um conjunto de critérios matemáticos que garantem a otimalidade de
uma solução.
• 
• 
• 
• 
• 
• 
• 
• 
 
A verificação das condições de otimalidade pode ser complexa, especialmente para problemas de
grande porte.
 
Existem diversos métodos para verificar as condições de otimalidade.
Exemplo detalhado
Considere o problema de maximizar a função objetivo:
1. Formulação do problema:
 
Função objetivo:
Restrição:
2. Condições de primalidade:
 
Viabilidade:
Complementaridade:
Estacionariedade:
• 
• 
3. Solução:
Resolvendo o sistema de equações, encontramos a solução ótima: 
4. Verificação das condições:
Viabilidade:
Complementaridade:
Estacionariedade:
5. Condições de dualidade:
 
Dualidade fraca:
Dualidade forte:
Complementaridade dual:
 
6. Interpretação da solução:
A solução ótima para o problema de maximização é x = y = 1/2, com um valor máximo da função
objetivo de f(x, y) = 1/2.
 
O multiplicador de Lagrange λ = 1 representa o preço sombra da restrição.
Observações:
Esse é um exemplo simples de um problema de otimização com restrições.
 
Problemas de otimização mais complexos podem ter grande número de variáveis e restrições.
 
Existem diversos softwares disponíveis para resolver problemas de otimização.
Resumindo, as condições de otimalidade são responsáveis por garantir que uma solução seja realmente ótima.
Por meio da verificação das condições de primalidade e dualidade, podemos ter certeza de que a solução
escolhida é a que melhor atende aos objetivos do problema.
Condições de otimalidade
Aprenda, neste vídeo, como assegurar a otimalidade em um problema de PL.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Dualidade na PL
A programação linear (PL) é uma técnica matemática importantíssima para otimizar a alocação de recursos em
diversos cenários, mas isso você já sabe, não é mesmo? É preciso que se lembre que ela tem como base
formular um problema como uma função objetiva a ser maximizada ou minimizada, sob um conjunto de
restrições lineares. Ao longo da história, a PL se tornou um instrumento inegociável em determinadas áreas,
especialmente logística, finanças, indústria e engenharia.
O surgimento da dualidade
Em 1947, o matemático John von Neumann introduziu o conceito de dualidade na PL, abrindo um novo
capítulo na compreensão e resolução de problemas de otimização. A dualidade estabelece uma relação
profunda entre um problema de PL (chamado problema primal) e outro problema de PL derivado (chamado
problema dual). Essa relação permite explorar o problema original sob diferentes perspectivas, revelando
informações relevantes e facilitando a sua resolução.
 
Imagine um problema de PL que busca minimizar o custo de transporte de produtos entre armazéns e lojas. A
dualidade cria um problema dual associado, que analisa o mesmo cenário sob a ótica de maximizar o lucro
obtido pelas lojas ao vender os produtos, considerando os custos de recebimento de cada armazém.
• 
• 
• 
• 
• 
Conceitos fundamentais
Nesse cenário, dois conceitos são basilares: 
Explorando as aplicações práticas
O problema dual em programação linear oferece diversas vantagens estratégicas. Primeiramente, ele
estabelece limites basilares para a função objetivo: o valor dual fornece um limite inferior para problemas de
minimização e superior para maximização, sendo essencial na avaliação de soluções aproximadas quando
resolver o problema primal for complexo ou computacionalmente custoso.
 
Além disso, as variáveis duais identificam os preços sombra das restrições do problema primal, indicando o
valor marginal pelo qual a função objetivo se altera ao relaxar essas restrições. Essa informação é
imprescindível para decisões estratégicas, permitindo avaliar a importância de cada restrição e seu impacto
potencial em mudanças. 
 
Em certos cenários, resolver o problema dual pode ser mais simples do que o primal, especialmente quando o
número de restrições é substancialmente menor que o de variáveis, o que possibilita encontrar soluções de
forma mais rápida ou lidar eficientemente com problemas de grande escala.
 
Além das vantagens mencionadas, o problema dual também facilita a análise de sensibilidade. Isso significa
que ele permite entender como a solução ótima do problema primal é afetada por mudanças nos coeficientes
dos objetivos ou nas constantes das restrições. Essa capacidade de análise é importante para ajustar
estratégias de produção, planejamento financeiro ou alocação de recursos de forma dinâmica, considerando
as flutuações e mudanças no ambiente operacional.
 
Portanto, o uso eficaz do problema dual não apenas simplifica a resolução de problemas complexos, mas
fortalece a capacidade das organizações de tomar decisões informadas e adaptativasem resposta às
condições do mercado e às necessidades operacionais.
 
Vamos ver alguns exemplos para esclarecer os conceitos citados!
Dualidade fraca 
O valor mínimo da função objetivo no
problema primal é sempre maior ou igual ao
valor máximo da função objetivo no problema
dual. Essa propriedade garante que a busca
pela solução ótima no primal nunca resultará
em um valor inferior ao que poderia ser
obtido no dual.
Dualidade forte 
Se o problema primal for viável e
limitado (possui soluções e restrições
finitas), e o problema dual também for
viável e limitado, então os valores das
funções objetivo no primal e no dual
serão iguais. Essa propriedade garante
que, se ambos os problemas forem
solucionados com sucesso, os resultados
serão consistentes e fornecerão a
solução ótima para o problema original.
Maximização da produção
Primal: maximizar a produção de uma fábrica, respeitando restrições de tempo e recursos.
Dual: minimizar o custo associado a essas restrições (custo do tempo e recursos utilizados).
Minimização de custos
Primal: minimizar o custo de transporte de produtos.
Dual: maximizar o lucro obtido pelas lojas ao vender os produtos, considerando os custos de
recebimento de cada armazém.
Alocação de recursos em um hospital
Primal: minimizar o custo total de atendimento a pacientes em um hospital, considerando a
disponibilidade de recursos (médicos, enfermeiros, leitos etc.).
Dual: maximizar a qualidade do atendimento aos pacientes, considerando os custos de cada
tipo de recurso.
Vamos aprofundar alguns conceitos!
1
Interpretação das variáveis duais
As variáveis duais no problema dual representam os preços sombra das restrições do problema
primal. Imagine que uma empresa enfrenta uma restrição de disponibilidade de um determinado
material. A variável dual associada a essa restrição indicaria o valor máximo que a empresa estaria
disposta a pagar por uma unidade adicional do material, caso esta estivesse disponível.
2
Relaxamento de restrições
A dualidade permite analisar o impacto de relaxar (aumentar) as restrições do problema primal. Ao
resolver o problema dual com as restrições modificadas, é possível determinar o valor máximo que a
função objetivo pode atingir sem violar a viabilidade do problema.
• 
• 
• 
• 
• 
• 
3Dualidade e sensibilidade
A dualidade está intimamente ligada à análise de sensibilidade em PL. Ao analisar as variáveis duais,
é possível determinar quais restrições são mais críticas para a solução ótima e como a função
objetivo é alterada em resposta a mudanças nos parâmetros do problema.
Confira mais exemplos avançados de uso do simplex!
Problema de transporte com
capacidades
Considere um problema de transporte com
restrições de capacidade nos armazéns e nas
lojas. A dualidade pode ser utilizada para
determinar os preços sombra das capacidades,
fornecendo insights sobre a importância de
cada armazém e loja na solução ótima.
Problema de mistura de ração animal
Considere um problema de mistura de ração
para animais com restrições nutricionais. A
dualidade pode ser utilizada para determinar os
preços sombra dos nutrientes, indicando a
importância de cada nutriente para a saúde dos
animais.
Desafios e considerações acerca do simplex
A interpretação das variáveis e restrições do problema dual pode ser complexa, especialmente em problemas
com grande número de variáveis e restrições. Em alguns casos, a resolução do problema dual pode ser tão
complexa quanto a do problema primal.
A dualidade é aplicada principalmente a problemas de PL com funções objetivo e restrições lineares. Para
modelos não lineares, existem técnicas alternativas de análise e otimização.
Ao compreender e utilizar a dualidade, é possível: 
Obter limites para a função objetivo.
 
Identificar preços sombra das restrições. 
 
Simplificar a resolução em alguns casos.
 
Avaliar o impacto de relaxar restrições.
 
Realizar análises de sensibilidade. 
A dualidade contribui para uma compreensão mais profunda dos problemas de PL e fornece informações
importantíssimas para a tomada de decisão. A aplicação da dualidade em diversas áreas demonstra sua
importância como ferramenta para otimizar recursos e alcançar resultados mais eficientes.
Exemplo detalhado da dualidade na PL
Vamos considerar o seguinte cenário: uma empresa de logística precisa transportar produtos entre três
armazéns (A, B e C) e cinco lojas (1, 2, 3, 4 e 5). A empresa possui informações sobre a demanda de cada loja,
a capacidade de cada armazém e o custo de transporte entre cada armazém e loja.
• 
• 
• 
• 
• 
 
Seu objetivo é: minimizar o custo total de transporte, considerando as restrições de demanda e capacidade.
Problema primal
 
Função objetivo:
Variáveis:
xij: quantidade de produtos transportados do armazém i para a loja j
 
Restrições:
 
Demanda:
Capacidade:
Não negatividade:
Problema dual
 
Função objetivo:
Variáveis:
Restrições:
Resolução:
Utilizando um software de PL, podemos resolver o problema primal e o problema dual, e obter as seguintes
soluções ótimas:
Solução primal:
yi: preço sombra da demanda da loja i zi: preço sombra da capacidade do armazém i
Solução dual:
Análise da solução:
 
Custo total de transporte:
Dualidade fraca:
Observe que o valor da função objetivo no problema dual (G) é igual ao valor da função objetivo no problema
primal (F), confirmando a dualidade forte.
 
Interpretação dos preços sombra:
yi: preço sombra da demanda da loja i. Indica o valor máximo que a empresa estaria disposta a pagar
por uma unidade adicional de demanda na loja i.
 
zi: preço sombra da capacidade do armazém i. Indica o valor marginal que a empresa perde ao reduzir
a capacidade do armazém i em uma unidade.
Exemplo:
O preço sombra da demanda da loja 1 (y1) é 1. Isso significa que a empresa estaria disposta a pagar até
R$ 1 por uma unidade adicional de demanda na loja 1, pois isso resultaria em uma redução de R$ 1 no
custo total de transporte.
• 
• 
• 
 
O preço sombra da capacidade do armazém 1 (z1) é 2. Isso significa que a empresa perde R$ 2 em
valor marginal ao reduzir a capacidade do armazém 1 em uma unidade.
A dualidade na PL fornece informações relevantes sobre o problema original, como:
Limite inferior para o custo total de
transporte
O valor da função objetivo no problema dual (G)
fornece um limite inferior para o custo total de
transporte (F).
Preços sombra das restrições
As variáveis duais no problema dual fornecem
os preços sombra das restrições do problema
primal.
Análise da solução dual
Permite identificar as restrições mais críticas
para o problema e avaliar o impacto de relaxar
(aumentar) as restrições. A dualidade é uma
ferramenta para otimizar a solução de
problemas de PL e para a tomada de decisões
estratégicas.
Observações adicionais:
A interpretação dos preços sombra pode ser complexa em problemas com grande número de variáveis
e restrições.
 
Existem técnicas para relaxar as restrições do problema primal e analisar o impacto na solução ótima.
 
A dualidade também pode ser aplicada a problemas de PL com funções objetivo e restrições não
lineares.
Dualidade na PL
Confira, neste vídeo, como assegurar a dualidade em um problema de PL.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
O software LINDO
A LINDO Systems é conhecida pelos seus softwares de otimização, em especial o LINDO API e o LINDO
Solver. Essas ferramentas são amplamente utilizadas para a programação linear, a programação inteira, a
programação não linear e outras tarefas de otimização. A LINDO Systems fornece soluções de software para
empresas, pesquisadores e analistas que precisam resolver problemas complexos de otimização.
• 
• 
• 
• 
 
Para baixar o aplicativo, visite o site da LINDO e baixe a versão mais recente.
 
Um modelo LINDO deverá conter os seguintes itens:
Função objetivo (fo), que deverá iniciar com os comandos MAX para maximizar e MIN para minimizar, e
à frente, deverá ser colocada a função objetivo.A declaração SUBJECT TO (sujeito a), que pode ser substituída por st ou s.t., e logo após, serão
declaradas as restrições do problema. 
 
Para finalizar, devemos declarar o comando END.
Observe o modelo a seguir.
Executando o aplicativo, teclando no ícone de dardo e flecha, obtemos o seguinte resultado:
Regras do software LINDO para PL
O LINDO é um software importante para a resolução de problemas de PL. Ele oferece uma interface amigável
e recursos avançados para otimizar modelos de programação linear.
 
• 
• 
• 
Acompanhe algumas regras básicas!
Definir o modelo
Criar variáveis e definir seus tipos (reais, inteiras, binárias).
Especificar a função objetivo (maximizar ou minimizar).
Incluir as restrições do problema (igualdades e desigualdades).
Executar a solução
Carregar o modelo no LINDO.
Resolver o problema usando o comando Solve.
Visualizar a solução ótima, incluindo valores das variáveis, função objetivo e valores duais.
Analisar a solução
Avaliar a viabilidade e otimalidade da solução.
Interpretar os valores das variáveis e dos preços sombra.
Identificar restrições críticas e realizar análises de sensibilidade.
Os recursos adicionais são:
Geração de relatórios
O LINDO permite gerar relatórios detalhados
com a solução do problema, incluindo valores
das variáveis, função objetivo, valores duais e
outros indicadores.
Análise de sensibilidade
O LINDO oferece ferramentas para analisar o
impacto de mudanças nos parâmetros do
problema, como coeficientes da função objetivo
e restrições sobre a solução ótima.
• 
• 
• 
• 
• 
• 
• 
• 
• 
Programação
O LINDO permite escrever scripts para
automatizar tarefas e resolver problemas de PL
de forma mais complexa.
Confira alguns exemplos de regra!
GIN y: define a variável y como inteira.
 
Especificar função objetivo:
 
MAX: maximiza a função objetivo (MIN minimiza).
 
2x + 3y = 0: define a restrição como x >= 0.
O software LINDO
Confira, neste vídeo, o software LINDO, da LINDO Systems, muito utilizado em programação linear.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Resolução de problemas de PL com o método simplex
O método simplex é um algoritmo poderoso para resolver problemas de PL. Sua simplicidade e eficiência o
tornaram a ferramenta mais utilizada para otimizar problemas em diversas áreas, desde logística e finanças
até engenharia e pesquisa operacional.
 
O método simplex funciona iterativamente, explorando vértices do poliedro viável (região definida pelas
restrições do problema) até encontrar a solução ótima. Em cada iteração, o método avalia a solução corrente e
determina uma direção de movimento que melhora a função objetivo. Esse processo é repetido até que a
solução ótima seja alcançada.
 
Acompanhe as etapas do método simplex!
Formulação do problema
Definir a função objetivo e as restrições do problema em forma de equações lineares.
• 
• 
• 
• 
• 
Conversão para a forma padrão
Transformar o problema para a forma padrão da PL, com variáveis de folga e artificiais, se necessário.
Construção da tabela simplex
Organizar as informações do problema em uma tabela que facilita a visualização e o
acompanhamento das iterações.
Seleção da variável entrante
Identificar a variável que, ao entrar na base, resultará no maior aumento da função objetivo.
Seleção da variável saliente
Determinar a variável que deve sair da base para manter a viabilidade do problema.
Cálculo da razão pivô
Encontrar o valor que determina a quantidade a ser adicionada à variável entrante e a quantidade a
ser retirada da variável saliente.
Atualização da tabela simplex
Atualizar a tabela com os novos valores das variáveis após a iteração.
Teste de otimalidade
Verificar se a solução atual é ótima. Se não, retornar à etapa 4.
Vamos a um exemplo detalhado. Um produtor independente dispõe de 2 unidades de geração de energia
elétrica, que podem ser conectadas ao sistema elétrico em pontos distintos, para a venda do excedente de
energia elétrica que são capazes de produzir. Tanto os custos de produção quanto as tarifas negociadas para
a venda de energia são distintos para os 2 geradores. O produtor deseja vender o máximo possível de energia
seguindo, entretanto, seu plano de negócios, que não permite gastar acima de um valor preestabelecido para
a produção de energia (Kagan et al., 2009).
 Gerador 1 Gerador 2
Capacidade de produção (MWh) 5.000 7.000
Custo de produção (R$/MWh) 50 100
Tarifa de venda (R$/MWh) 90 120
Máximo custo de produção total (R$) 800.000
Tabela: Valores associados à geração de energia.
Mauro Resende.
Escrevendo o problema em forma de inequações, temos o seguinte problema de geração: 
 
Função objetivo:
Sujeito a:
Confira a solução pelo método simplex no LINDO!
Observe que existem poucas diferenças entre o modelo escrito e o colocado no software. Executando,
obtemos o seguinte:
Veja a tela a seguir, em que rodamos a análise de sensibilidade.
Preste atenção nas seguintes dicas!
No software LINDO para PL, o termo Reduced Cost (custo reduzido) refere-se à quantidade pela qual o
coeficiente de uma variável não básica na função objetivo precisaria melhorar para que essa variável se
tornasse uma candidata a entrar na base. Em outras palavras, o custo reduzido indica o potencial
benefício de incluir uma variável não básica na solução.
 
Dual Price (preço dual) refere-se ao valor marginal de cada restrição no problema. Em outras palavras,
o preço dual indica o quanto a função objetivo (lucro) pode aumentar se a RHS (lado direito) de uma
restrição for relaxada em uma unidade.
 
Coefficient Ranges (intervalos de coeficientes) refere-se a uma saída opcional que fornece
informações sobre a sensibilidade da solução ótima em relação às variações nos coeficientes da
função objetivo e das restrições. Especificamente, o Coefficient Ranges indica o intervalo no qual um
coeficiente pode ser alterado sem afetar a variável básica atual na solução e a otimalidade do
problema.
Right-hand Side Ranges (intervalos do lado direito) é uma subseção específica dentro da saída
opcional Coefficient Ranges (intervalos de coeficientes). Como vimos, o Coefficient Ranges analisa a
sensibilidade da solução ótima em relação a variações nos coeficientes da função objetivo e das
restrições. O Right-hand Side Ranges foca especificamente as mudanças no lado direito (RHS) das
restrições do problema.
Considere o seguinte problema de programação linear:
Sujeito às seguintes restrições:
• 
• 
• 
• 
Colocando no LINDO, temos:
Executando com o relatório de análise de sensibilidade, temos:
Observe que as variáveis x1 e x3 não participam do problema, e a resposta será x3 = 5 e .
 
Uma empresa está tentando otimizar a produção de três produtos diferentes, denotados como Produto A,
Produto B e Produto C. O objetivo é maximizar o lucro total obtido com a venda desses produtos, sujeito a
várias restrições operacionais e de mercado.
 
As quantidades produzidas dos três produtos são representadas pelas variáveis de decisão x1 (Produto A), x2 
(Produto B) e x3 (Produto C). O lucro obtido com a venda de cada produto é diferente devido às suas
características e à demanda no mercado.
 
A empresa definiu as seguintes restrições:
A disponibilidade de matéria-prima e mão de obra limita a produção total, representada pela primeira
restrição: 3x1−x2+2x3≤10.
• 
 
Devido à demanda do mercado, a produção total dos produtos deve atender a um mínimo de lucro,
representado pela segunda restrição: 2x1+2x2+3x3≥12.
 
Há uma relação específica entre os produtos A, B e C, indicando que a produção deles deve satisfazer
a uma relação fixa, representada pela terceira restrição: x1+2x2−x3=5.
 
As quantidades produzidas de cada produto devem ser não negativas: x1,x2,x3≥0.
O objetivo da empresa é determinar as quantidades ideais de cada produto a serem produzidas para
maximizar o lucro total, seguindo as restrições mencionadas anteriormente.
Temoso seguinte modelo matemático para colocar no LINDO:
Transferindo para o LINDO, temos:
Executando, obtemos:
• 
• 
• 
Maximizar Sujeito a: 
Mas atenção, essa solução está errada! Isso porque, se estamos falando de produtos, temos que pensar que
eles não podem ser fracionários. Veja a solução correta:
E a solução:
Resolução de problemas de PL com o método simplex
Confira, neste vídeo, um exemplo de aplicação do método simplex.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Uma empresa de manufatura está tentando otimizar a produção de dois produtos para maximizar seu lucro. A
função objetivo foi definida e as restrições foram estabelecidas. O problema foi convertido para a forma
padrão da programação linear (PL) e uma tabela simplex foi construída. Durante o processo, a empresa
identificou a variável que entrará na base para maximizar a função objetivo e determinou a variável que deve
sair da base para manter a viabilidade. Em seguida, calculou a razão pivô e atualizou a tabela simplex. No
entanto, após várias iterações, ainda não estava certa se havia alcançado a solução ótima. 
 
Considerando o texto, analise as alternativas a seguir e assinale a correta.
A A próxima etapa é construir a tabela simplex novamente com novas variáveis.
B A próxima etapa é reavaliar a função objetivo original.
C A próxima etapa é identificar novamente as variáveis de folga e artificiais.
D A próxima etapa é verificar a otimalidade da solução atual e, se necessário, retornar à seleção da
variável entrante.
E A próxima etapa é converter o problema de volta à sua forma original.
A alternativa D está correta.
Após atualizar a tabela simplex com os novos valores das variáveis, a próxima etapa é verificar se a solução
atual é ótima. Se não for, o processo deve retornar à seleção da variável entrante para continuar com as
iterações até que a solução ótima seja encontrada. As demais alternativas estão incorretas, pois não
seguem a sequência correta do método Simplex.
Questão 2 
Em uma empresa de engenharia, foi realizado um estudo profundo sobre a aplicação da dualidade na
programação linear (PL) para otimizar processos de produção. Durante a análise, identificou-se que a
dualidade oferece benefícios como a obtenção de limites para a função objetivo e a identificação de preços
sombra das restrições. No entanto, os engenheiros enfrentaram desafios na interpretação das variáveis e
restrições do problema dual, especialmente devido à complexidade de modelos com muitas variáveis. Apesar
das vantagens, a resolução do problema dual também se mostrou complicada em alguns casos, comparável à
do problema primal.
 
Considerando o texto, analise as alternativas a seguir e assinale a correta.
A A dualidade na programação linear não oferece benefícios práticos na interpretação de variáveis e
restrições.
B A dualidade na programação linear simplifica automaticamente a resolução de problemas com muitas
variáveis.
C A resolução do problema dual sempre é mais simples do que a do problema primal.
D A dualidade na programação linear é aplicável apenas a problemas com funções objetivo e restrições
não lineares.
E A dualidade na programação linear contribui para uma compreensão mais profunda dos problemas e
oferece informações valiosas para a tomada de decisão.
A alternativa E está correta.
A dualidade na programação linear contribui positivamente e oferece informações valiosas para a tomada
de decisão. As alternativas A, B e C estão incorretas porque não refletem corretamente os benefícios e as
características da dualidade na PL mencionados no estudo de caso. A alternativa D também está incorreta,
pois a dualidade na PL aplica-se a problemas com funções objetivo e restrições lineares, não
necessariamente não lineares.
3. Aplicações do método simplex
Conceitos básicos da programação linear (PL)
Conceitos, formulação de problemas, métodos de resolução
Confira, neste vídeo, um bate-papo sobre os conceitos básicos e a formulação, assim como os métodos de
resolução e a interpretação de resultados de problemas de PL.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
A programação linear pode trazer benefícios significativos para as empresas, como a redução de custos, o
aumento da produtividade e a melhoria da tomada de decisão. A PL é uma técnica matemática utilizada para
resolver problemas de otimização, em que se busca:
Maximizar
Lucro, produção e quantidade de recursos.
Minimizar
Custos, tempo e desperdícios.
A PL funciona como uma receita para resolver problemas de otimização. Cada componente é um ingrediente
essencial para formular e solucionar o problema. Vamos detalhar cada um deles!
 
No centro de um problema de PL está a função objetivo, que define o objetivo a ser maximizado ou
minimizado, como lucro, produção, custo ou tempo. Essa função representa a meta final que se busca
alcançar com a otimização das variáveis de decisão — os parâmetros controláveis, como quantidades de
produtos a fabricar ou horas de trabalho. As restrições, por sua vez, estabelecem as limitações ou as
condições que as variáveis de decisão devem respeitar, como disponibilidade de recursos ou capacidade de
produção máxima. A interseção das restrições forma a região viável, que representa o conjunto de todas as
combinações possíveis das variáveis de decisão que satisfazem todas as restrições.
 
A solução ótima de um problema de PL é o ponto dentro da região viável que maximiza ou minimiza a função
objetivo, conforme desejado. Essa solução é a combinação ideal de valores para as variáveis de decisão que
proporciona o melhor resultado possível, seja maximizando lucro, minimizando custo ou atingindo qualquer
outro objetivo estipulado. Para encontrar essa solução ótima, utilizamos métodos como o método simplex, que
explora sistematicamente os vértices da região viável até encontrar o ponto que otimiza a função objetivo. A
PL é uma técnica matemática fundamental para a tomada de decisões eficientes e estratégicas, permitindo às
empresas e organizações resolverem problemas complexos de modo estruturado e objetivo.
Tipos de restrições
Conheça, a seguir, alguns tipos de restrições!
Igualdade
Representa equilíbrios (ex.: x + y = 2, em que x e y são ingredientes que precisam somar 2 unidades).
Desigualdade
Define limites (ex.: x + y ≤ 2, em que a soma de x e y não pode ultrapassar 2 unidades).
Não negatividade
Algumas variáveis não podem ser negativas (ex.: x ≥ 0, você não pode ter uma quantidade negativa
de ingredientes).
Veja agora alguns exemplos!
Exemplo 1: uma empresa fabrica dois produtos, A e B. O lucro por unidade de A é R$ 2,00 e o lucro por
unidade de B é R$ 3,00. A empresa tem 10 horas de mão de obra disponíveis por dia e 12 horas de máquina
disponíveis por dia. O produto A exige 1 hora de mão de obra e 2 horas de máquina por unidade, enquanto o
produto B exige 2 horas de mão de obra e 1 hora de máquina por unidade. A empresa deseja determinar a
quantidade de cada produto a ser fabricada para maximizar o lucro total.
Exemplo 1
Confira, neste vídeo, a resolução da questão!
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Exemplo 1.1: uma atleta precisa definir sua dieta diária para otimizar a ingestão de proteína e carboidrato,
respeitando suas necessidades nutricionais e seus limites calóricos.
 
Variáveis de decisão:
x = gramas de frango (fonte de proteína)
 
y = gramas de arroz (fonte de carboidrato)
Função objetivo (FO): maximizar a proteína total (PT)
 (em que 2 é a proteína por grama de frango e 0,5 é a proteína por grama de arroz).
Restrições:
Necessidade mínima de proteína: a atleta precisa de pelo menos 100 gramas de proteína por dia.
Necessidade mínima de carboidrato: a atleta precisa de pelo menos 200 gramas de carboidrato por
dia.
• 
• 
• 
• 
• 
Limite calórico: a ingestão diária não pode ultrapassar 2000 calorias.
Atenção: 10 é o valor calórico por grama de frango e 4 é o valorcalórico por grama de arroz.
Não negatividade: a atleta não pode comer quantidades negativas de frango ou arroz.
Resolução:
O problema pode ser resolvido graficamente (para 2 variáveis) ou pelo método simplex (para mais variáveis)
ou pelo solver. A solução ótima determina a quantidade ideal de frango (x) e arroz (y) que a atleta deve
consumir para maximizar a proteína total, respeitando todas as restrições alimentares.
 
Exemplo 2: um fazendeiro precisa criar uma mistura de ração para alimentar seu gado, utilizando três tipos de
grãos: milho, soja e aveia. Cada tipo de grão possui diferentes teores de proteína, gordura e fibra, além de
diferentes custos. O fazendeiro deseja formular a mistura de ração que atenda às necessidades nutricionais
do gado, minimizando o custo total da mistura.
 
Variáveis de decisão:
 porcentagem de milho na mistura
 
 porcentagem de soja na mistura
 
 porcentagem de aveia na mistura
Função objetivo (FO): minimizar o custo total (CT)
Atenção: 0,5 é o custo por kg de milho, 0,8 é o custo por kg de soja e 0,4 é o custo por kg de aveia.
Restrições:
Teor de proteína: a mistura precisa ter no mínimo 20% de proteína.
• 
10x + 4y ≤ 2000 
• 
• 
• 
• 
Teor de gordura: a mistura precisa ter no máximo 10% de gordura.
Teor de fibra: a mistura precisa ter entre 15% e 25% de fibra.
Totalização: a soma das porcentagens deve ser igual a 100%.
Não negatividade: as porcentagens não podem ser negativas.
Resolução:
 
O problema pode ser resolvido pelo método simplex ou pelo solver. A solução ótima determinará a
porcentagem ideal de cada grão (milho, soja e aveia) na mistura de ração para minimizar o custo total,
respeitando as necessidades nutricionais do gado.
Formulação de problemas de PL
É a etapa inicial para utilizar a ferramenta de otimização. É nessa fase que você transforma um problema
complexo do mundo real em um modelo matemático que a PL pode resolver. Vamos apresentar alguns
exemplos de formulação de modelo matemático.
 
Exemplo 1: uma padaria produz dois tipos de pães: francês e integral. O lucro por unidade de pão francês é R$
1,50, e o lucro por pão integral é R$ 2,00. A padaria tem 6 horas de forno disponíveis por dia e 4 horas de mão
de obra disponíveis por dia. O pão francês leva 0,5 horas de forno e 0,3 horas de mão de obra por unidade,
enquanto o pão integral leva 1 hora de forno e 0,4 horas de mão de obra por unidade. A padaria deseja
determinar a quantidade de cada tipo de pão a ser produzida para maximizar o lucro total.
 
Variáveis de decisão:
 = quantidade de pães franceses a serem produzidos.
 
 quantidade de pães integrais a serem produzidos.
Função objetivo:
Restrições:
 (horas de forno)
 
 (horas de mão de obra)
 (não negatividade)
Dicas para formulação efetiva:
Identifique claramente o objetivo e as limitações do problema.
 
Defina variáveis de decisão que representem quantidades controláveis.
 
Traduza as restrições em inequações ou equações matemáticas.
 
Certifique-se de que todas as variáveis são não negativas.
 
Verifique se o modelo é consistente e bem definido.
Exemplo 2: uma fábrica produz três tipos de brinquedos: carrinhos, bonecas e bicicletas. Cada brinquedo
necessita de diferentes quantidades de matéria-prima e horas de mão de obra para ser produzido. A fábrica
possui limitações diárias de ambas as quantidades, e deseja determinar a produção ideal de cada brinquedo
para maximizar o lucro total, respeitando essas restrições.
 
Variáveis de decisão:
 = número de carrinhos a serem produzidos.
 
 número de bonecas a serem produzidas.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
 número de bicicletas a serem produzidas.
Função objetivo: maximizar o lucro total (LT)
Atenção: 5 é o lucro por carrinho, 3 é o lucro por boneca e 8 é o lucro por bicicleta.
 
Restrições:
 
Mão de obra: a produção diária não pode ultrapassar 100 horas de mão de obra.
Matéria-prima (plástico): a produção diária não pode exceder 80 kg de plástico.
Matéria-prima (metal): a produção diária não pode exceder 50 kg de metal.
Não negatividade: a produção de cada brinquedo não pode ser negativa.
Estoque mínimo de bicicletas: a fábrica precisa produzir pelo menos 10 bicicletas por dia.
Explicação das restrições:
A primeira restrição limita a produção total de brinquedos conforme a disponibilidade de mão de obra.
• 
• 
 
A segunda e a terceira restrições limitam a produção conforme a disponibilidade de plástico e metal,
respectivamente.
 
A quarta restrição garante que a produção de brinquedos seja representada por valores reais e não
negativos.
 
A quinta restrição estabelece uma demanda mínima de bicicletas que deve ser atendida.
Solução:
 
O problema pode ser resolvido utilizando o método simplex ou outros métodos de otimização. A solução ótima
indicará a quantidade ideal de cada brinquedo (carrinhos, bonecas e bicicletas) a ser produzida para
maximizar o lucro total da fábrica, respeitando as limitações de mão de obra, material e a demanda mínima de
bicicletas.
 
Considerações adicionais:
Este exemplo demonstra como incorporar restrições de diferentes naturezas (quantidade, mínimo) na
formulação do problema.
 
A escolha dos coeficientes na função objetivo e restrições reflete os custos de produção e valores de
lucro de cada brinquedo.
Exemplo 2
Confira a resolução a seguir!
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Conclusão:
 
A formulação precisa de problemas de PL com três variáveis e cinco restrições permite modelar situações
complexas de produção e otimizar a tomada de decisão. Com essa técnica, empresas podem maximizar lucros
ao alocar recursos de modo eficiente, respeitando restrições e demandas.
 
Exemplo 3: uma pizzaria oferece três tipos de pizza: muçarela (M), calabresa (C) e frango com catupiry (FC).
Cada pizza necessita de diferentes quantidades de ingredientes, e a pizzaria possui um estoque limitado
desses ingredientes para o dia. O objetivo é determinar a quantidade ideal de cada tipo de pizza a ser
produzida para maximizar o lucro total, respeitando as restrições de ingredientes.
 
Estoque disponível de ingredientes: queijo: 10 kg, tomate: 8 kg, calabresa: 5 kg, frango: 7 kg e catupiry: 3 kg.
Lucro por pizza: M = R$ 10, C = R$ 12, FC = R$ 15.
 
• 
• 
• 
• 
• 
Ingredientes por pizza:
Pizza Queijo
(kg)
Tomate
(kg)
Calabresa
(kg)
Frango
(kg)
Catupiry
(kg)
Muçarela (M) 0,2 0,1 
Calabresa (C) 0,15 0,1 0,2 
Frango com catupiry
(FC)
0,18 0,12 3 0,1
Mauro Resende Filho
Variáveis de decisão:
 número de pizzas muçarela a serem produzidas.
 
 número de pizzas calabresa a serem produzidas.
 
 = número de pizzas frango com catupiry a serem produzidas.
Função objetivo: maximizar o lucro total (LT)
Restrições:
 
Queijo: a quantidade total de queijo utilizada não pode exceder o estoque disponível.
Tomate: a quantidade total de tomate utilizada não pode exceder o estoque disponível.
Calabresa: a quantidade total de calabresa utilizada não pode exceder o estoque disponível.
• 
• 
• 
Frango: a quantidade total de frango utilizada não pode exceder o estoque disponível.
Catupiry: a quantidade total de catupiry utilizada não pode exceder o estoque disponível.
Não negatividade: a produção de cada tipo de pizza não pode ser negativa.
Solução:
 
O problema pode ser resolvido utilizando o método simplex ou outros métodos de otimização. A solução ótima
indicará a quantidade ideal de cada tipo de pizza a ser produzida (muçarela, calabresa e frango com catupiry)
para maximizar o lucro total da pizzaria, respeitando as limitações de ingredientes.
 
Exemplo de resultado:
Por meio da resolução do problema de PL, a pizzaria pode descobrir que a produção ideal é de:
 pizzas muçarela
 
 pizzas calabresa
 
 pizzas frango com catupiry
Com essa produção, a pizzaria maximiza o lucro total e utiliza todo o estoque disponível de ingredientes de
forma eficiente.
Métodos de resolução de problemas de PL
Como você sabe,a PL é uma técnica matemática poderosa para otimizar decisões em diversas áreas. Ela
permite modelar problemas de otimização com variáveis lineares, restrições e uma função objetivo a ser
maximizada ou minimizada. Diversos métodos eficientes foram desenvolvidos para resolver problemas de PL,
cada um com suas vantagens e desvantagens.
• 
• 
• 
Método gráfico
Ideal para problemas com duas variáveis e fácil visualização da solução gráfica.
Útil para entender conceitos básicos de PL e para problemas simples.
Limitado a problemas com duas variáveis; pode ser difícil encontrar a solução ótima em
problemas mais complexos.
Método simplex
Algoritmo iterativo que busca a solução ótima passo a passo.
Amplamente utilizado e eficiente para resolver problemas de PL com diversas variáveis.
Pode ser lento para problemas com grande número de variáveis e restrições.
Implementado em diversos softwares de otimização.
Branch-and-bound
Utilizado para resolver problemas de PL com variáveis inteiras.
Divide o problema em subproblemas e explora as soluções candidatas de forma eficiente.
Pode ser lento para problemas com grande número de variáveis inteiras.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
Programação linear inteira mista (MILP)
Combinação de PL e programação linear inteira para problemas com variáveis contínuas e
inteiras.
Abrange uma gama mais ampla de problemas de otimização.
Pode ser mais difícil de resolver do que PL pura.
Pode ser utilizado o solver do Microsoft Excel.
Agora vamos a um resumo importante sobre o que estudamos neste conteúdo! Os fatores na escolha do
método são:
Tamanho do problema (número de variáveis e restrições).
 
Natureza das variáveis (contínuas, inteiras ou mistas).
 
Complexidade do problema.
 
Disponibilidade de software.
 
Tempo e recursos disponíveis.
Conheça os softwares de otimização!
GAMS
 
LINDO
 
LINGO
 
CPLEX
 
Solver
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
AMPL
 
Python com bibliotecas PuLP, Pyomo
Considerações importantes para a escolha do método adequado
A escolha do método depende das características do problema e dos recursos disponíveis. É importante ter
conhecimento dos diferentes métodos para escolher o mais adequado. Além disso, softwares de otimização
facilitam a resolução de problemas de PL e podem ser muito úteis.
 
Escolher o método de resolução de problemas de PL é imprescindível para alcançar a solução ótima de modo
eficiente. O conhecimento dos diferentes métodos, suas vantagens e desvantagens, além da utilização de
softwares de otimização, permite que você maximize os resultados de sua análise e otimize seus processos
de tomada de decisão.
Interpretação de resultados
Ao resolver um problema de PL, você obtém resultados que fornecem informações valiosíssimas sobre a
solução ideal e o cenário otimizado. Vamos entender melhor!
Solução ótima
A solução de um problema de PL fornece os valores das variáveis de decisão que otimizam a função
objetivo, seja maximizando o lucro ou minimizando o custo. Essa solução indica a quantidade ideal de
cada recurso a ser alocada para alcançar o objetivo desejado.
Valor da função objetivo
O valor da FO na solução ótima indica o lucro máximo ou o custo mínimo que pode ser atingido sob as
restrições do problema. Esse valor é uma medida da performance da solução e permite comparar
diferentes cenários e decisões.
Sensibilidade
A análise de sensibilidade avalia como a solução ótima muda em resposta a alterações nos
parâmetros do problema, como coeficientes da função objetivo, valores de demanda e restrições.
Essa análise fornece informações significativas acerca da robustez da solução e ajuda a identificar os
parâmetros mais críticos para o problema.
Interpretação de sombras
As sombras, também conhecidas como preços duais, indicam o valor marginal de cada restrição na
solução ótima. Elas revelam o impacto de relaxar cada restrição em uma unidade e podem ser
utilizadas para identificar gargalos e oportunidades de otimização.
• 
• 
Relatórios e outputs
Softwares de PL geralmente fornecem relatórios detalhados com a solução, valores da função
objetivo, sensibilidade, sombras e coeficientes. É importante analisar esses outputs cuidadosamente
para interpretar os resultados e extrair insights relevantes.
Confira alguns exemplos de interpretação! 
Em um problema de otimização de produção, a solução pode indicar a quantidade ideal de cada
produto a ser produzida para maximizar o lucro.
 
A análise de sensibilidade pode mostrar como o lucro muda em resposta a alterações no preço de
venda de cada produto.
 
As sombras podem indicar quais produtos são mais lucrativos e quais restrições limitam a produção.
A interpretação de resultados em PL é fundamental para extrair insights da solução e tomar decisões
estratégicas mais informadas. Por meio da análise cuidadosa da solução, da sensibilidade das sombras, você
pode compreender o impacto de diferentes variáveis e identificar oportunidades de otimização em seus
problemas.
Mão na massa
Questão 1
Uma empresa de produtos alimentícios precisa determinar a quantidade ideal de biscoitos de chocolate e
biscoitos de aveia a serem produzidos para maximizar o lucro. 
 
Dados:
Lucro por biscoito:
 
Chocolate: R$ 0,50
 
Aveia: R$ 0,60
 
Tempo de produção por biscoito:
 
Chocolate: 2 minutos
 
Aveia: 3 minutos
• 
• 
• 
• 
• 
• 
• 
 
Tempo total disponível de produção: 600 minutos
 
Matéria-prima disponível:
 
Farinha: 120 kg
 
Açúcar: 80 kg
 
Qual modelo matemático soluciona esse problema?
Chave de resposta
Variáveis de decisão:
x: Quantidade de biscoitos de chocolate a serem produzidos.
y: Quantidade de biscoitos de aveia a serem produzidos.
Modelo matemático:
Função objetivo (maximizar lucro):
Restrições:
Tempo de produção:
Matéria-prima:
Farinha:
• 
• 
• 
• 
• 
Açúcar:
Não negatividade:
Solução:
O modelo matemático apresentado pode ser resolvido usando softwares específicos de programação
linear, como simplex, LINGO ou solver. A solução ótima para esse problema é a seguinte:
x = 200 (biscoitos de chocolate)
y = 100 (biscoitos de aveia)
Lucro máximo:
Interpretação da solução:
A empresa deve produzir 200 biscoitos de chocolate e 100 biscoitos de aveia para maximizar o lucro, que
será de R$ 160.
Análise de sensibilidade:
É importante realizar uma análise de sensibilidade para avaliar como a solução ótima muda em resposta a
alterações nos parâmetros do problema. Por exemplo, podemos analisar como o lucro máximo muda se o
tempo de produção de um biscoito de chocolate aumentar para 3 minutos.
• 
• 
• 
• 
Questão 2
Uma empresa de produção de móveis precisa determinar a quantidade ideal de mesas e cadeiras a serem
produzidas para maximizar o lucro. A empresa possui agora 4 tipos de móveis: mesas de madeira, mesas de
vidro, cadeiras de madeira e cadeiras de plástico. 
 
Dados:
 
Lucro por móvel:
 
Mesa de madeira: R$ 100
 
Mesa de vidro: R$ 120
 
Cadeira de madeira: R$ 80
 
Cadeira de plástico: R$ 70
 
Tempo de produção por móvel:
 
Mesa de madeira: 2 horas
 
Mesa de vidro: 3 horas
 
Cadeira de madeira: 1 hora
 
Cadeira de plástico: 0,5 horas
 
Tempo total disponível de produção: 80 horas
 
Matéria-prima disponível:
 
Madeira: 120 m²
 
Vidro: 80 m²
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
 
Plástico: 50 m²
 
Qual meio matemático otimiza a produção?
Chave de resposta
Variáveis de decisão:
x1: quantidade de mesas de madeira a serem produzidas.
x2: quantidade de mesas de vidro a serem produzidas.
x3: quantidade de cadeiras de madeira a serem produzidas.
x4: quantidade de cadeiras de plástico a serem produzidas.
Modelo matemático: função objetivo (maximizar lucro):
Restrições:
Tempo de produção:
Matéria-prima:
Não negatividade:
• 
• 
• 
• 
• 
• 
 
Questão 3
Uma farmácia precisa determinar a quantidade ideal de medicamentos a serem comprados para maximizar o
lucro, considerando as restrições de orçamento

Mais conteúdos dessa disciplina