Prévia do material em texto

PESQUISA OPERACIONAL
UNIDADE 2 - PROGRAMAÇÃO LINEAR
Luciano Wallace Gonçalves Barbosa
INICIAR
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 mix de
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
minimização, geralmente relacionados a diminuição de custos, e maximização, que são voltados ao aumento dos
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
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 restrições tecnológicas. Ainda, os PPLs devem apresentar as
restrições de não negatividade, em que todas as variáveis de decisão devem assumir valor igual ou maior que
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.
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.
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.
Proporcionalidade Aditividade Certeza
1.2 Espaço viável de um PPL
A Pesquisa Operacional é uma ciência para 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
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, quandosubstituí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 al. (2010), que pede para representar graficamente o PPL a seguir.
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:
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:
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. 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 desse método para encontrar a solução. Venha
conhecer!
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Ê O CONHECE?
VOCÊ SABIA?
Na PL, existe o conceito de solução viável, que é uma solução que atende a todas as restrições do problema, e o
conceito de solução ótima, que além de cumprir todos os requisitos do modelo, ainda retorna o valor ótimo da função
objetivo, que é o máximo possível que ela pode alcançar, em problemas de maximização e, analogamente, o mínimo
possível em problemas de minimização.
Figura 1 - Representação gráfica das restrições.
Fonte: Elaborada pelo autor, 2019.
Clique para abrir a imagem no tamanho original
Figura 2 - Representação da região viável do problema.
Fonte: Elaborada pelo autor, 2019.
Clique para abrir a imagem no tamanho original
VAMOS PRATICAR?
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  so!ware, basta você
delinear as variáveis de decisão como ‘x’ e ‘y’, que as retas logo aparecem no plano cartesiano. Experimente:
https://www.geogebra.org/m/KGWhcAqc
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
VOCÊ QUER VER?
1.3 O algoritmo simplex
Importantes acontecimentos na Programação Linear, segundo Arenales et al. (2007), sucederam-se no ano de
1947, quando foi desenvolvido o método simplex, seguido de pesquisas de novos métodos e implementações
eficientes. Muitos so!wares gerados para solução de problemas de PL trabalham na lógica do algoritmo
simplex.
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 variável de folga, que são variáveis adicionadas nas restrições
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
diminuir algum valor desse lado, isso porque, como a restrição garante que ele é maior que 10, ao diminuirmos
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 somar a variável de folga, pois se já
existe a 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.
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 variáveis básicas aquelas que assumem
valores positivos na solução, ao passo que as que assumem zero são denominadas variáveis não básicas
(TAHA, 2008). As soluções são denominadas solução básica até que alcancem a otimalidade. Esses conceitos
ficarão mais 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: 
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 cálculo das razões não negativas entre a coluna solução
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 Gauss-Jordan, onde a coluna pivô é denominada a
coluna da variável que entra na base, e a linha pivô é a linha da variável que sai da base. O elemento de
interseção da coluna pivô com a linha pivô é o elemento pivô. Veja:
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:
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:
As variáveis de folga adicionadas no modelo, ao fim do algoritmo, têm o papel de demonstrar o status do
recurso 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.
Clique para abrir a imagem no tamanho original
Clique para abrir a imagem no tamanho original
Clique para abrir a imagem no tamanho original
Clique para abrir a imagem no tamanho original
Clique para abrir a imagem no tamanho original
Figura 3 - Representação gráfica do problema.
Fonte: TAHA, 2008, p. 43.
Clique para abrir a imagem no tamanho original
23/02/2023 20:03
Página 1 de 1