Unidade 02 - PROGRAMAÇÃO LINEAR

Prévia do material em texto

- -1
PESQUISA OPERACIONAL
UNIDADE 2 - PROGRAMAÇÃO LINEAR
Luciano Wallace Gonçalves Barbosa
- -2
Introdução
Os ambientes coorporativos vêm sendo cada vez mais pressionados devido ao aumento da competitividade. Com
o avanço de mudanças e recursos tecnológicos, a tomada de decisão tem sido um tema que exige cada vez mais
atenção e cuidado dos gestores – afinal, a cada dia que passa, surgem mais e mais possibilidades de condução de
um negócio, com suas peculiaridades distintas, demandando então a seleção da decisão que retorne o maior
lucro possível dentro daquelas que foram selecionadas como candidatas, ou paralelamente, ao menor custo.
A Pesquisa Operacional vem ganhando espaço dentro do contexto de tomada de decisão desde a Segunda Guerra
Mundial (1939-1945), quando surgiu. Desde então, técnicas vêm sendo desenvolvidas e aprimoradas no sentido
de tornar essa ciência cada vez mais viável e promissora. Afinal, quais as técnicas matemáticas que mais auxiliam
decisões nos ambientes empresariais?
A Programação Linear é uma das mais clássicas técnicas da Pesquisa Operacional. Veremos, nesta unidade, que
sua principal função é reduzir o sistema real a um conjunto de equações e/ou inequações de primeiro grau,
resolvendo a modelagem por métodos algébricos. Mas como seria feita essa solução, uma vez que um sistema
pode ter inúmeras variáveis e restrições? A Programação Linear possui um poderoso algoritmo, denominado
simplex, que é capaz de resolver problemas com várias variáveis. Durante esta unidade, veremos seu
funcionamento.
Como você se sentiria ao saber que existe uma técnica relativamente simples, que pode auxiliar em problemas
complexos, chegando à melhor solução possível dentro de todas as candidatas? Pois bem, siga atento a este
estudo, pois a Programação Linear, ou PL, tem muito a te surpreender.
1.1 Definição
Muitos problemas das realidades das organizações podem ser construídos com a Programação Linear, que é uma
das técnicas mais utilizadas para a otimização. O motivo está relacionado à simplicidade dos modelos que são
gerados por esse método e pelas várias técnicas, incluindo computacionais, que conseguem encontrar a solução
do problema.
Um problema é considerado um Problema de Programação Linear (PPL) se, e somente se, for modelado e escrito
como um sistema real com função objetivo e restrições, formando um conjunto de equações e/ou inequações
lineares, ou seja, as variáveis de decisão sendo polinômios de primeiro grau (WINSTON, 2004).
Mas o que são função objetivo, variáveis de decisão e restrições? Bom, o começo da modelagem em PL parte
desses três pilares. As variáveis de decisão são o início do problema e são responsáveis por descrever as
decisões a serem tomadas. Assim, caso seu problema seja a maximização de custos dentro de um de mix
produção, as variáveis de decisão serão responsáveis por retornar à quantidade de cada produto do portfólio a
ser produzido. Portanto, se sua carteira de produtos contar com 30 itens, por exemplo, seu modelo terá 30
variáveis de decisão, uma correspondente a cada item, que ao final trará a quantidade exata de cada um que deve
ser produzida.
Em seguida, deve-se traçar a função objetivo, que está relacionada à meta buscada, sendo possível modelos de 
, geralmente relacionados a diminuição de custos, e , que são voltados ao aumento dosminimização maximização
lucros. Assim, a função objetivo deve ser composta das variáveis de decisão que são acompanhadas pelos
respectivos valores correspondentes no tipo da modelagem. Por exemplo, se o problema é de maximização de
lucros, a função objetivo será composta pela soma dos 30 itens de seu portfólio, multiplicando cada variável de
decisão pelo lucro correspondente de cada item.
Assim, ao final do modelo, como as variáveis de decisão correspondem às quantidades de produção de cada item,
foram multiplicadas pelo lucro unitário de venda de cada unidade, a função objetivo retorna ao valor que a
empresa obterá, caso siga o plano de produção ótimo indicado pela modelagem. Por ser um modelo de
maximização, não existe nenhum outro plano que retornará um valor maior do que o estabelecido, cumprindo
- -3
maximização, não existe nenhum outro plano que retornará um valor maior do que o estabelecido, cumprindo
todas as restrições do sistema.
Falando de restrições, estas são as próximas a serem definidas, e isso deve ser feito com muita atenção: elas são
responsáveis por trazer para o modelo matemático a realidade total do sistema. Caso alguma limitação do
processo não seja traduzida para restrição, o modelo passa a não representar a realidade, comprometendo sua
solução. Assim como a função objetivo, as restrições acompanham as variáveis de decisão, porém em forma de
equações e inequações, sempre de primeiro grau, para caracterização da linearidade do problema.
Dessa forma, a primeira parte da restrição deve apresentar o quanto cada variável de decisão consome de um
determinado recurso, e a segunda parte (após os sinais de ≤, = ou ≥), representa a disponibilidade total desse
recurso. Portanto, no exemplo seguido, caso cada item do portfólio necessite ser processado por um
determinado tempo em uma máquina e a disponibilidade dessa máquina seja de 1000 horas, a restrição dessa
tecnologia é definida como a soma da multiplicação da quantidade de tempo que cada item necessita de
transformação nessa máquina pela variável de decisão correspondente a esse item, até que sejam somados todos
os produtos da carteira. A segunda parte da restrição é composta por “≤ 1000”, o que indica que a soma do
tempo dispendido para a fabricação de todos os produtos pela máquina deve ser menor que ou igual à
disponibilidade dela.
Todas essas restrições são as chamadas . Ainda, os PPLs devem apresentar as restrições tecnológicas
, em que todas as variáveis de decisão devem assumir valor igual ou maior querestrições de não negatividade
zero (≥ 0), já que se pode optar em produzir ou em deixar de produzir algo, mas nunca em produzir
negativamente. Determinadas as variáveis de decisão, a função objetivo e as restrições, o PPL está pronto para
ser resolvido.
Para garantir a linearidade de um PPL, três propriedades básicas devem ser satisfeitas, as quais são exibidas a
seguir (TAHA, 2008). Clique nos itens a conheça-as.
Proporcionalidade
Diz respeito à exigência de que a contribuição de cada variável de decisão, tanto na função objetivo quanto nas
restrições, seja diretamente proporcional ao valor da própria variável. Na prática, como foi falado sobre a
contribuição de cada lucro dos produtos na função objetivo, essa regra exige que este não seja alterado no
decorrer da situação real. Por exemplo, caso a empresa que modelou o problema tenha uma política de desconto
para clientes que comprarem a partir de certa quantidade, essa política fere a regra da proporcionalidade da
contribuição de cada variável de decisão, deixando o problema de ser um PPL.
Aditividade
Diz respeito à necessidade de que todas as variáveis da função objetivo e das restrições contribuam
individualmente na soma da contribuição total. Isso quer dizer que, por exemplo, na função objetivo, a soma do
lucro total é igual à soma individual que cada variável de decisão (item produzido) retorna. Então, caso o
aumento da venda de algum produto afete no comércio de algum outro produto, essa regra não é satisfeita,
tornando o problema não linear.
Certeza
Por ser um problema quantitativo, determinístico, todos os coeficientes que acompanham as variáveis de
decisão, tanto nas restrições quanto na função objetivo, devem ser constantes conhecidas. Alguns valores podem
ser baseados em previsões estatísticas, porém serão válidos apenas se o desvio padrão dessas estatísticas seja
suficientemente pequeno.
Satisfeitas as três regras e definidos os três pilares, o problema está pronto para ser resolvido por técnicas de
programação linear. Conheceremos essas técnicas e aprenderemos a interpretar as soluções trazidas por elas.
1.2 Espaço viável de um PPL
A Pesquisa Operacional é uma ciênciapara auxílio na tomada de decisão, que, como se sabe, é uma tarefa cada
vez mais complexa dentro das empresas, uma vez que, com o avanço e a mudança de tecnologias, as possíveis
alternativas para se resolver um problema têm sido cada vez mais numerosas. Assim, técnicas de PO, como a
- -4
alternativas para se resolver um problema têm sido cada vez mais numerosas. Assim, técnicas de PO, como a
Programação Linear, emergem no sentido de enumerar essas alternativas e solucionar aquela que retorne o
ganho mais positivo, seja em maximização de lucros ou minimização de custos.
Vimos que os problemas são descritos em um conjunto de equações e inequações lineares. As restrições desse
problema, então, são responsáveis por delinear o espaço de suas possíveis soluções. Além disso, o conjunto de
restrições deve ser observado como um todo, uma vez que a desobediência de apenas uma das métricas do
problema descaracteriza toda a solução.
Dizemos ser a solução de um PPL os valores resultados de todas as variáveis de decisão que, quando substituídos
na função objetivo, retornam ao valor ótimo do problema e ao ganho gerado nessa solução, ou seja, quanto de
lucro se obtém em problemas de maximização ou o quão dispendioso ficou o plano de custos em casos de
minimização.
Os valores das variáveis de decisão na solução ótima são um conjunto tal que seria impossível atender a todas as
restrições e resultar em uma função objetivo tão ótima quanto ele. Assim, é fácil entender que toda solução ótima
é uma solução viável, porém a recíproca não é verdadeira, isto é, dentro da região de soluções viáveis, haverá
uma (ou, em alguns casos, mais de uma, porém que resultem em um valor idêntico da função objetivo final) com
valor da função objetivo máximo ou mínimo possível.
Para entendermos melhor esse conceito de espaço viável, observamos esse exemplo adaptado da obra de Silva et
(2010), que pede para representar graficamente o PPL a seguir.al. 
VOCÊ O CONHECE?
Marcone Jamilson Freitas Souza é graduado em Engenharia Metalúrgica pela Universidade
Federal de Ouro Preto (Ufop), mestre e doutor em Engenharia de Sistemas e Computação pela
Universidade Federal do Rio de Janeiro (UFRJ). Atualmente é professor na Ufop e se dedica, há
décadas, ao estudo da Pesquisa Operacional, tendo várias publicações e orientações na área.
Um de seus focos é a aplicação industrial de modelos de Programação Linear, como na
otimização operacional de lavra em minas de céu aberto e subterrâneas (CURRÍCULO LATTES,
2019).
VOCÊ SABIA?
Na PL, existe o conceito de , que é uma solução que atende a todas as restriçõessolução viável
do problema, e o conceito de , que além de cumprir todos os requisitos dosolução ótima
modelo, ainda retorna o valor da função objetivo, que é o máximo possível que ela podeótimo
alcançar, em problemas de maximização e, analogamente, o mínimo possível em problemas de
minimização.
- -5
A lógica de representação desse problema vem da clássica Álgebra Linear: equações/inequações de primeiro
grau com duas variáveis podem ser descritas em um plano cartesiano por meio da criação das retas
correspondentes. Como se sabe, para se traçar uma reta, deve-se encontrar apenas dois pontos. Assim, iniciando
pelas restrições, encontra-se os pontos referentes a cada uma e, posteriormente, esboça-se o plano contendo
todas elas.
As primeiras restrições a serem levadas em consideração são as de não negatividade: e . 
Considerando o eixo das abcissas como as variáveis e o das ordenadas como , e considerando que ambas
devem ser maior que ou igual a zero, isso indica que, no plano cartesiano, apenas o primeiro quadrante contém
as soluções viáveis, já que em qualquer outro quadrante existe a necessidade de ao menos uma delas ser
negativa.
A posteriori, trabalhamos as restrições tecnológicas. Para encontrar o primeiro ponto, arbitrariamente
escolhemos um valor para e substituímos na inequação, encontrando . Analogamente, para o segundo ponto,
arbitra-se um valor para e encontra-se . Dados os dois pontos, traça-se a reta. A dica é sempre escolher
valores de e igual a zero, para facilitar o encontro da outra variável. Para encontrar o outro ponto,
inequações são consideradas como equações. Os sinais de ≥ e ≤ voltam a ser analisados ao traçar o plano. A
representação dos pontos é dada por ( ). Vejamos o exemplo:
A representação das restrições é exibida na figura a seguir, lembrando que a cor das retas corresponde à cor de
cada restrição:
- -6
Figura 1 - Representação gráfica das restrições.
Fonte: Elaborada pelo autor, 2019.
Agora, voltamos a reconsiderar as equações como inequações. Sabemos que as retas precisam ter um sentido,
uma vez que as soluções são maiores que ou igual ou menores que ou igual. Para isso, usamos um ponto
qualquer, dentro do plano cartesiano, e testamos se esse ponto faz parte ou não daquela restrição. Se a resposta
for positiva, o sentido da reta é ir ao encontro do ponto. Caso contrário, a reta de restrição vai em sentido
contrário ao ponto. Para facilitar, é sugerido utilizar o ponto (0,0), que é a origem do plano cartesiano.
Ao se determinar os sentidos de todas as restrições, pode-se encontrar o espaço de soluções viáveis de
problema, que consiste na região onde todas as restrições são atendidas. Assim, esse espaço se dá como:
- -7
Figura 2 - Representação da região viável do problema.
Fonte: Elaborada pelo autor, 2019.
Assim, a restrição azul, que deu negativa no teste do ponto, vai contra a origem (0,0), conforme a seta. O mesmo
ocorreu com a restrição verde. Já a laranja aceitaria o ponto de teste, porém, como as demais já o haviam
retirado como inviável, ele já não pode participar do problema. A orientação das setas demonstra que, até certo
ponto, uma restrição restringe mais do que outra. O conjunto de tudo dá o espaço viável do problema. Dentro da
área destacada de cinza, qualquer ponto é solução viável do PPL, isto é, atende a todas as restrições. Se testarmos
o ponto (4,4), por exemplo, que está na área viável, veremos que ele respeita todas as restrições. Porém, não
quer dizer que seja o ponto ótimo.
Note que a área viável desse problema é infinita, isso é, para todo e qualquer e , as soluções são
viáveis. Isso é muito comum em problemas de minimização, já que as soluções no espaço infinito, por mais que
sejam viáveis, estão longe de ser ótimas.
Dentro de um PPL, a solução ótima sempre estará em algum extremo, isto é, no encontro de duas (ou mais) retas.
Você acaba de aprender como é feita a delineação de uma área de soluções viáveis, passo a
passo. Essa é uma das etapas mais importantes de um Problema de Programação Linear e seria
interessante que você soubesse exatamente como é feito esse processo. Para isso, refaça o
exemplo exibido à mão, traçando o plano cartesiano e as respectivas restrições. Isso te ajudará
ao realizar provas, pois terá a noção de tudo isso sem a necessidade de auxílio computacional.
Para reproduzir as imagens realizadas no exemplo, utilize o Geogebra gratuitamente. Nesse 
, basta você delinear as variáveis de decisão como ‘x’ e ‘y’, que as retas logo aparecemsoftware
no plano cartesiano. Experimente: https://www.geogebra.org/m/KGWhcAqc
https://www.geogebra.org/m/KGWhcAqc
- -8
Dentro de um PPL, a solução ótima sempre estará em algum extremo, isto é, no encontro de duas (ou mais) retas.
Portanto, nesse exemplo, os pontos candidatos a ótimos são (5,0), (8,0), (0,10) e o ponto de encontro das retas
azul e verde, que é encontrado na solução do sistema de equações que contém as duas restrições referentes às
retas.
Para a solução desse problema via método gráfico, basta traçar a função objetivo como uma reta, conforme
fizemos com todas as restrições, e transladá-la até que encontre o último ponto extremo no sentido de
minimização, que nesse caso será o ponto (5,0), retornando um valor mínimo de 10.
O método gráfico é viável quando se tem apenas duas variáveis de decisão. Mas e quando tivermos mais? Bom, aí
existem outras técnicas, que usam o raciocínio algébrico dessemétodo para encontrar a solução. Venha conhecer!
1.3 O algoritmo simplex
Importantes acontecimentos na Programação Linear, segundo Arenales (2007), sucederam-se no ano deet al.
1947, quando foi desenvolvido o método simplex, seguido de pesquisas de novos métodos e implementações
eficientes. Muitos gerados para solução de problemas de PL trabalham na lógica do algoritmo simplex.softwares
Como visto, problemas com duas variáveis de decisão podem, facilmente, ser trazidos para o método gráfico e
ser resolvidos. Porém, a maior parte dos PPLs conta com mais variáveis de decisão, o que demanda uma técnica
mais robusta. Assim, surge o algoritmo simplex, que segue a lógica da solução gráfica, porém por meio de
quadros que realizam operações com as equações das restrições.
1.3.1 Conversão das inequações em equações
O primeiro passo a se realizar para iniciar o método simplex é converter todas as inequações do modelo para
equações e, para isso, usaremos o conceito de , que são variáveis adicionadas nas restriçõesvariável de folga
para torná-las equações.
Imagine a restrição . Note que o primeiro lado da expressão (1 ) deve ser maior que o
segundo lado (10). Para que isso aconteça e possamos alterar o sinal de para o sinal de =, devemos então 
 algum valor desse lado, isso porque, como a restrição garante que ele é maior que 10, ao diminuirmosdiminuir
algo, podemos dizer que ele é igual a 10. Esse valor diminuído será a variável de folga, que trataremos aqui com
o índice , remetendo à ‘sobra’. Essa restrição, então, ficaria da seguinte forma: .
Analogamente, se a restrição fosse , deveríamos então a variável de folga, pois se já existe asomar
garantia de que seja menor que ou igual, apenas somando algo (até mesmo somando 0), podemos garantir a
igualdade. A equação ficaria dessa forma: .
Atenção: as variáveis de folga devem sempre ser maiores que ou iguais a zero. Nunca negativas.
VOCÊ QUER VER?
Quer fixar ainda melhor o entendimento do conteúdo? Certeza que sim. Então, venha comigo e
assista ao vídeo Pesquisa operacional I – Aula 6 – Método simplex: interpretação gráfica
(UNIVESP, 2016). Nele, você consegue ver como é definida a região de soluções viáveis de um
problema e como é feito o translado da função objetivo para encontrar o extremo ótimo dentro
da área viável. Disponível em: https://www.youtube.com/watch?v=29q6FcbTWeU
https://www.youtube.com/watch?v=29q6FcbTWeU
- -9
1.3.2 Natureza iterativa do método simplex
O método simplex é baseado na lógica do aumento de uma variável por vez, sendo selecionada aquela que tem a
melhor taxa de melhoria na função objetivo. São denominadas aquelas que assumem valoresvariáveis básicas
positivos na solução, ao passo que as que assumem zero são denominadas (TAHA, 2008).variáveis não básicas 
As soluções são denominadas até que alcancem a otimalidade. Esses conceitos ficarão maissolução básica
claros a seguir.
Por enquanto, é importante saber, também, que ao terminar uma solução básica, o método busca uma próxima
variável não básica a entrar e contribuir positivamente na função objetivo. Entre uma iteração e outra do
algoritmo, serão realizadas estas perguntas: qual variável não básica entrará na base? Qual das variáveis básicas
sairá da base para que a não básica entre?
1.3.3 Detalhes do algoritmo simplex
Elucidados os pontos acima, vamos a um exemplo, que é a melhor forma para se compreender um problema
determinístico. Acompanhe os detalhes, as iterações e as regras para responder às perguntas da subseção
anterior, com esse exercício retirado da obra de Taha (2008, p. 43).
Exemplo:
Use o algoritmo simplex para resolver o seguinte PPL:
Sujeito a
Como sabemos, o primeiro passo é transformar as inequações em equações, por meio da adição das variáveis de
folga. Elas entram na função objetivo com multiplicador zerado, já que não possuirão contribuição. O modelo
canonizado fica da seguinte forma:
Sujeito a
Note que cada restrição possui sua própria variável de folga. A seguir, a função objetivo é reescrita como: 
. Assim, a tabela simplex é escrita pelos coeficientes de cada variável. A primeira tabela é assim
representada:
VNB: 
VB: 
- -10
VB: 
Como visto, as iterações do simplex inicial em (0,0) para ( ). Assim, substituindo essa solução na tabela,
encontra-se imediatamente os valores das VBs, por leitura direta:
Como existem variáveis não básicas ( ) com valores negativos (porque invertemos o sinal no início do
algoritmo), indica que o problema ainda pode melhorar. Então, entramos com a variável , que pode agregar
cinco unidades na função objetivo. Essa é a chamada .regra de otimalidade
Agora, para saber a variável que sairá, é necessário o entre a coluna soluçãocálculo das razões não negativas
da tabela, que corresponde ao lado direito das restrições, e o coeficiente da restrição correspondente à variável
que está entrando, no caso . Observe a tabela abaixo:
Assim, na nova tabela do algoritmo, as variáveis são:
VNB: 
VB: 
Para montar a próxima tabela, são realizadas operações de , onde a é denominada aGauss-Jordan coluna pivô
coluna da variável que entra na base, e a é a linha da variável que sai da base. O elemento delinha pivô
interseção da coluna pivô com a linha pivô é o . Veja:elemento pivô
Os cálculos necessários são:
- -11
Os cálculos necessários são:
1. Linha do pivô:
a) Realizar a substituição da variável que saiu da base, na coluna Base, pela variável que entrou;
b) Nova linha pivô 
2. Todas as demais linhas, incluindo a linha :z
Nova linha 
Seguindo o exemplo, esses cálculos ficam:
1. Substituição de na coluna base por :
Nova linha 
2. Nova linha 
(1 -5 -4 0 0 0 0 0) – (-5) 
3. Nova linha 
 
4. Nova linha 
(0 -1 1 0 0 1 0 1) – (–1) 
5. Nova linha 
(0 0 1 0 0 0 1 2) – (0) 
A solução básica e a nova tabela são:
Solução básica: , , , .
Seguindo o mesmo raciocínio empregado, vê-se que , pertencente às VNBs, possui valor negativo, então ainda
pode contribuir na função objetivo, portanto, é a variável que entra na base. Entre as variáveis que estão na base,
a que possui a menor razão é (1,5), portanto, é a variável escolhida para sair. Realizando exatamente as
analogias da iteração passada, a próxima tabela do simplex é a seguinte:
- -12
VNB: 
VB: 
Como nenhum coeficiente das VNBs é negativo, o algoritmo para e essa é a solução ótima.
Veja, na imagem abaixo, a representação gráfica do problema tratado neste exemplo:
Figura 3 - Representação gráfica do problema.
Fonte: TAHA, 2008, p. 43.
As variáveis de folga adicionadas no modelo, ao fim do algoritmo, têm o papel de demonstrar o do recursostatus
da restrição a qual foi associada. Como , as restrições às quais essas variáveis foram associadas são
abundantes, ao passo que , as restrições associadas a estas são escassas, isto é, utilizaram todos os
recursos disponíveis. O último quadro simplex traz inúmeras informações úteis, que serão vistas a .posteriori
- -13
1.4 Análise de sensibilidade
A análise de sensibilidade é uma importante consideração a ser feita do modelo de Programação Linear
resolvido, porque os dados coletados para esse problema dependem de aspectos, como o desempenho do
processo produtivo, o mercado etc. Assim, ela é responsável por analisar até quanto esses aspectos podem
variar, mantendo estável a solução adotada (SILVA 2010). Assim, trazemos um exemplo da obra doset al., 
referidos autores, para contextualizar o conceito (p. 129):
Exemplo:
Sujeito a
 jeito ualizar o conceito: o autor, para melhor entender o coara ficar mais claro o entendiento 
O quadro simplex inicial do algoritmo é dado a seguir:
Quadro final:
A solução apresentada no quadro final será alterada caso entre na base alguma variável não básica, ou seja, 
. O objetivo é maximizar o lucro e o foco é saber qual tipo de variação a variável pode sofrer sem
alterar a solução ótima.
Entrada de 
Pelo quadro final, observando a coluna dos coeficientes de , se alterarmos seu valor de 0 para 1, temos:x1
 diminui em 0,154
 diminui em 0,385
 diminui em 0,462
O coeficientede que permite a entrada de é um coeficiente que iguala o aumento de lucro com a entrada de 
 com a diminuição do lucro devido às outras variáveis .
Os lucros são conhecidos da tabela inicial do algoritmo e, para termos analíticos, traremos o lucro de para a
- -14
Os lucros são conhecidos da tabela inicial do algoritmo e, para termos analíticos, traremos o lucro de para a
terminologia Assim, tem-se:
Entrada de 
Alterarmos seu valor de 0 para 1, temos:
 diminui em -0,308
 diminui em 0,231
 diminui em 0,077
Entrada de 
Alterarmos seu valor de 0 para 1, temos:
 diminui em -0,23
 diminui em -0,077
 diminui em 0,308
Portanto, as análises foram feitas e encontrados os valores críticos para , que ordenados ficam da seguinte
forma:
Como os valores não podem ser negativos, assume-se então que, para manter a solução estável, o lucro de tem
que estar entre 0,75 e 2, ou seja, .
Existem outras formas de se analisar a sensibilidade de um modelo de Programação Linear, mas, para o
ambiente industrial, a mais importante é saber até quanto um lucro pode variar, mantendo a otimalidade do
problema.
1.5 Dualidade
Segundo Taha (2008, p. 68, grifos nossos), “[...] o problema é um PPL definido direta e sistematicamente dedual
acordo com PPL (original). Os dois problemas guardam uma relação tão estreita que a solução ótima deprimal
um [...] é a solução ótima do outro”.
Uma das grandes vantagens dos problemas duais é a análise pós-otimização, que permite a identificação de
importantes características do modelo resolvido. Para construção do problema dual, existem regras, que são
enunciadas a seguir.
A primeira delas é que o tipo da função objetivo é diferente no dual. Então, problemas primais de maximização
possuem dual de minimização e vice-versa. Ainda, as restrições do problema primal tornam-se as variáveis de
decisão do dual, assim como as variáveis de decisão do primal são as restrições do dual.
Evidentemente que esse conceito é complexo. Exibiremos como deve ser feita a transformação de um problema
em dual e seguiremos com um exemplo, para facilitar o seu entendimento. Vamos ver!
Acabamos de aprender como se faz a análise de sensibilidade de um Problema de Programação
Linear, ou seja, agora já sabemos até quanto os coeficientes da função objetivo podem ser
alterados, sem que a solução ótima seja modificada. Isso quer dizer que, dentro dos intervalos
aceitos, a quantidade de cada produto a ser fabricado é a mesma, a única coisa que altera é o
valor da função objetivo. Você imagina o motivo? Analise a Figura 3 deste e-book para
raciocinar. A dica é: a inclinação da função objetivo faz toda a diferença.
- -15
Quadro 1 - Regras para construção do problema dual.
Fonte: Elaborado pelo autor, baseado em TAHA, 2008.
A ideia é a inversão. Os coeficientes das variáveis de decisão na função objetivo tornam-se a parte direita das
restrições do dual. Ao obedecer às regras exibidas no quadro acima, as restrições do primal passam a ter relação
com a função objetivo do dual. Vejamos, na prática, com esse exemplo retirado da obra de Taha (2008, p. 69).
- -16
Em termos práticos, caso um problema primal vise à maximização dos lucros, sua versão dual será responsável
pela minimização dos recursos necessários para a fabricação, considerando aspectos do lucro. A vantagem disso
na prática industrial, por exemplo, é analisar em termos de estoque, como um PPL está se comportando após a
otimização.
1.4.1 Interpretação econômica do dual
Para a Engenharia, a maior vantagem de uma análise pós-otimização é a interpretação econômica de como será a
atuação desse modelo na prática. Silva (2010, p. 85) trazem um tópico sobre essa parte muito interessante,et al.
o qual será adaptado e abordado aqui.
Exemplo: Considere o exemplo abaixo, que trata de um de produção dos produtos A e B, que dependem dosmix
recursos X e Y. O quadro abaixo resume os dados:
CASO
Entendamos o conceito da dualidade. O problema, que era de maximização, tornou-se de
minimização. O primal tinha duas restrições tecnológicas, portanto o dual terá duas variáveis
de decisão, , que são acompanhadas pelos coeficientes das restrições do primal. Como ele
contava com três variáveis de decisão, o dual contará com três restrições e os coeficientes
destas será acompanhado pelo valor que acompanhava cada variável de decisão
correspondente na função objetivo do primal.
Como a primeira restrição do primal era de , a variável de decisão correspondente a esta no
dual será . Paralelamente, como a segunda restrição era uma igualdade, se torna irrestrita
no dual. Assim:
- -17
Agora, observe os modelos primal e dual desse PPL:
Primal:
Sujeito a
 (recurso X)
 (recurso Y)
A resolução desse modelo pelo algoritmo simplex retorna o seguinte quadro final:
Dual:
Sujeito a
A resolução deste modelo dual pelo algoritmo simplex retorna o seguinte quadro final:
Assim, as seguintes interpretações econômicas são retiradas desse caso e podem ser adaptadas para todo e
qualquer modelo de PPL que se deseja construir o modelo dual:
o valor de C (C=30) é obtido no primal S1, representando o valor de oportunidade do recurso X, ou seja, cada
unidade do recurso X tem a capacidade de geração de um lucro de 30. Isso é validado pelo fato de a variável S1,
no primal, ter sido igual a zero, indicando esse ser um recurso escasso. A mesma coisa é feita para analisar o
recurso Y, que tem ligação com a variável D no dual. O fato de ele ser zero é coerente, uma vez que o valor de S2,
- -18
recurso Y, que tem ligação com a variável D no dual. O fato de ele ser zero é coerente, uma vez que o valor de S2,
sua representação no primal, é igual a 500, portanto, não é um recurso escasso;
no problema dual, a função objetivo mede o valor de oportunidade dos recursos envolvidos na produção, ou seja,
a capacidade do estoque gerar lucro. Na solução ótima, esse valor é exatamente igual ao lucro atribuído aos
produtos pelo mercado;
cada restrição compara o valor de oportunidade dos produtos pelos recursos. Na primeira, por exemplo, 2C +
10D indica que o produto A, que usa duas unidades de X e 10 de Y, tem esse valor em termos desses produtos. O
lado esquerdo, 50, indica o valor de mercado, que é exatamente o lucro do produto A.
Chegamos ao fim dos conceitos principais de PPLs. Agora, você já é capaz de resolver um PPL e analisá-lo de
diferentes formas. Vale lembrar que existem pacotes computacionais que auxiliam nesse quesito. Busque sobre
complementos, como o , do Excel, que é bem simples e prático.Solver
Síntese
Legal, terminamos uma unidade inteira que tratou da Programação Linear e de seus métodos de resolução,
gráfico e simplex. Além disso, aprendemos a realizar análises que são muito úteis no contexto de engenharia e
tomada de decisão.
Nesta unidade, você teve a oportunidade de:
VOCÊ QUER VER?
Quer ver como é aplicada, na prática das indústrias, a PL? Leia o artigo de Barbosa et al.
(2016), no qual os autores utilizaram a técnica para a solução de um problema em uma
empresa de pequeno porte. Nesse texto, você conseguirá observar todos os detalhes da
formulação do problema e a solução, além das interpretações econômicas. Disponível em:
http://www.simpep.feb.unesp.br/abrir_arquivo_pdf.php?
tipo=artigo&evento=11&art=992&cad=22265&opcao=com_id.
Caro, estudante, para que você possa se apropriar cada vez mais dos conhecimentos
adquiridos nesta unidade, disponibilizamos uma lista de exercícios e suas respectivas
resoluções.
Lembre-se: A prática é um dos caminhos mais assertivos para ter domínio sobre os conceitos
aprendidos. Faça as atividades e, na sequência, confira as respostas. Bons estudos!
Clique aqui para acessar os exercícios.
Clique aqui para acessar as resoluções.
https://laureatebrasil.blackboard.com/bbcswebdav/institution/laureate/conteudos/ENG_PESOPE_19/unidade_2/ebook/ENG_PESOPE_19_E_2_exercicios.pdf
https://laureatebrasil.blackboard.com/bbcswebdav/institution/laureate/conteudos/ENG_PESOPE_19/unidade_2/ebook/ENG_PESOPE_19_E_2_gabarito.pdf
- -19
Nesta unidade,você teve a oportunidade de:
• aprender a definição detalhada de um Problema de Programação Linear, todas as suas peculiaridades e 
exigências para que seja assim caracterizado;
• ver como deve ser feita a delimitação das regiões viáveis de um PPL;
• diferenciar as soluções viáveis das soluções ótimas;
• fazer a montagem de um PPL na forma canônica para que possa ser modelado dentro do algoritmo de 
solução;
• conhecer o simplex e suas iterações para resolução de PPLs;
• por meio dos quadros simplex, aprender a analisar os intervalos viáveis que as variáveis podem assumir;
• criar modelos duais que auxiliam na interpretação econômica da solução otimizada.
Bibliografia
ARENALES, M. N. . Rio de Janeiro: Elsevier, 2007.et al. Pesquisa operacional 
CURRÍCULO LATTES. . Disponível em: Marcone Jamilson Freitas Souza http://buscatextual.cnpq.br
/ b u s c a t e x t u a l / v i s u a l i z a c v . d o ?
id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-
X 2 x K U s g u Q r p d 7 G Z y L M S E q i k P E H -
hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-
7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
. Acesso em: 28 jul. 2019.
SILVA, E. M. : para os cursos de administração e engenharia. 4. ed. São Paulo: Atlas,et al. Pesquisa operacional 
2010.
TAHA, H. A. . 8. ed. São Paulo: Pearson, 2008.Pesquisa operacional
UNIVERSIDADE VIRTUAL DO ESTADO DE SÃO PAULO (Univesp). – Aula 6 – MétodoPesquisa operacional I
simplex: interpretação gráfica. 10 ago. 2016. Disponível em: https://www.youtube.com/watch?v=29q6FcbTWeU
. Acesso em: 28 jul. 2019.
WINSTON, W. L. . 4. ed. Belmont: Thomson Learning, 2004.Operations research, applications and algorithms
BARBOSA, L. G. W. Programação linear na decisão de mix de produtos para estocagem: um caso do setor
moveleiro. In: SIMPÓSIO DE ENGENHARIA DE PRODUÇÃO, 23. Anais [...]. Bauru, 2016. Disponível em: 
http://www.simpep.feb.unesp.br/abrir_arquivo_pdf.php?
. Acesso em: 28 jul. 2019.tipo=artigo&evento=11&art=992&cad=22265&opcao=com_id
•
•
•
•
•
•
•
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6&tokenCaptchar=03AOLTBLQjiCyc3lIjsdhWJQ7O1VpLuqWLv8p3Z_O-X2xKUsguQrpd7GZyLMSEqikPEH-hCBUQsgLSyTKpohiv5RVZERZI1A_yFZgHR93BO9WtiIR9lYS0ZEQEA9i1_73elpJjD5d2LTF-7qhwB8PuNz3pbaFipHu5ihMiZ3AQTZiqGtQ_qxIluzJqcwQEeUgGAKXflSA77FshcpnaWT6HimmlBRClOqnAzdgHkjkFQPrULtqYF7nSlZ86Zpi8Y9RF-nJRJtO5A4-0b3isqr48rheE1y7gXeDihYPnxlatqIFCeZkazXCpgNbgZYjgfPFMcXzYBjfaT51p5V64ylQH3r06euuTESx7tw
https://www.youtube.com/watch?v=29q6FcbTWeU
http://www.simpep.feb.unesp.br/abrir_arquivo_pdf.php?tipo=artigo&evento=11&art=992&cad=22265&opcao=com_id
http://www.simpep.feb.unesp.br/abrir_arquivo_pdf.php?tipo=artigo&evento=11&art=992&cad=22265&opcao=com_id
	Introdução
	1.1 Definição
	1.2 Espaço viável de um PPL
	1.3 O algoritmo simplex
	1.3.1 Conversão das inequações em equações
	1.3.2 Natureza iterativa do método simplex
	1.3.3 Detalhes do algoritmo simplex
	1.4 Análise de sensibilidade
	1.5 Dualidade
	1.4.1 Interpretação econômica do dual
	Síntese
	Bibliografia