aula01

Prévia do material em texto

1ºAula
Programação Linaer e suas Formas 
de Resolução
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
•  entender o que é a pesquisa operacional;
•  conhecer a metodologia utilizada na pesquisa operacional;
•  entender o que é modelagem;
•  entender o que é programação linear;
•  entender o que é e como usar o método SIMPLEX;
•  aprender a usar o Solver do Excel para resolver problemas de PO.
Prezados(as) alunos(as),
Nesta primeira aula, estudaremos um pouco da história 
da pesquisa operacional, e também vamos entender como 
a pesquisa operacional pode ser útil em nosso dia a dia, 
apresentando dois casos de modelagem usando pesquisa 
operacional. Também estudaremos as formas de resolução de 
problemas de Pesquisa Operacional.
Bons estudos!
6Pesquisa Operacional
Seções de estudo
1- Origem e defi nições da pesquisa operacional
2 - Programação Linear – equações e solução gráfi ca
3 - Modelo de PL em forma de equação – simplex 
4 - Solução com computador com o excel solver
1 - Origem e defi nições da pesquisa 
operacional
 
O termo pesquisa operacional (PO) é uma tradução para o 
português brasileiro da expressão inglesa operational research. 
As primeiras atividades formais de PO foram iniciadas 
na Inglaterra durante a segunda guerra mundial, quando 
um grupo de cientistas britânicos decidiu tomar decisões 
com base científi ca sobre a melhor utilização de material 
de guerra, mais especifi camente aos radares. O termo 
pesquisa operacional é atribuído ao superintendente da 
estação A.P.Rowe, que em 1938 coordenava equipes para 
examinar a efi ciência de técnicas de operações advindas 
de experimentos com intercepção de radar. Em 1941 foi 
inaugurada a Seção de Pesquisa Operacional do Comando 
da Força Aérea de Combate (ARENALES et al., 2015).
Em 1952 foi fundada a sociedade científi ca americana 
de pesquisa operacional (ORSA – Operations Research 
Society of America) e em 1953 foi fundada a sociedade 
inglesa de pesquisa operacional (ORS – Operational 
Research Society) e a americana de ciências e administração 
(TIMS – The Institute of Manegement Sciences). Em 
1995 a ORSA e TIMS foram agregadas pelo INFORMS 
(Institute for Operational Research and the Manegement 
Sciences), que se mantém até os dias atuais (ARENALES 
et al., 2015).
No Brasil, a pesquisa operacional teve sua primeira 
aparição formal em 1968 no primeiro simpósio brasileiro 
de pesquisa operacional, realizado no ITA (Instituto 
Tecnológico de Aeronáutica), em São José dos Campos. 
No ano seguinte, em 1969, foi fundada a SOBRAPO 
(Sociedade Brasileira de Pesquisa Operacional), que publica 
o periódico científi co Pesquisa Operacional aqui no Brasil.
 Tratando-se de defi nição, a SOBRAPO se refere a 
Pesquisa Operacional como a área de conhecimento que 
estuda, desenvolve e aplica métodos analíticos avançados 
para auxiliar na tomada de melhores decisões nas mais 
diversas áreas de atuação humana. Já a INFORMS defi ne 
PO como uma disciplina profi ssional que trata de aplicação 
da tecnologia da informação para a tomada de decisão 
informada (ARENALES et al., 2015). 
1.2 - Solução do Modelo de Po
Em PO, não temos uma única técnica para resolver 
todos os modelos matemáticos que podem surgir na prática, 
onde a técnica mais utilizada é a programação linear. Ela é 
aplicada a modelos cujas funções objetivo e restrição são 
lineares. Outras técnicas são a programação inteira (na 
qual as variáveis assumem valores inteiros), a programação 
dinâmica (na qual o modelo original pode ser decomposto 
em subproblemas mais fáceis de tratar), a otimização em 
redes (na qual o problema pode ser modelado como uma 
rede) e a programação não linear (na qual as funções do 
modelo são não lineares). Estas são apenas algumas das 
muitas ferramentas de PO disponíveis (TAHA, 2008).
1.3 - Arte da modelagem
De acordo com Taha (2008), os modelos hipotéticos 
são representações verdadeiras de situações reais. Essa é 
uma ocorrência rara em PO porque, de modo geral, a maioria 
das aplicações envolve (graus variados de) aproximações. 
Abstraímos o mundo real considerado da situação real, 
concentrando-nos nas variáveis dominantes que controlam 
o comportamento do sistema real. O modelo expressa de 
maneira tratável as funções matemáticas que representam o 
comportamento do mundo real considerado.
Geralmente a atividade de uma equipe de PO envolve 
as seguintes fases:
•	 Identifi cação do problema e coleta de dados;
•	 Formulação de um modelo matemático 
(modelagem matemática);
•	 Obtenção da solução com base no modelo;
•	 Teste do modelo e avaliação da solução;
•	 Implantação e acompanhamento da solução.
Deve-se salientar que tais fases não são distintas, 
superpondo-se e interagindo entre si, na tentativa de se 
obter uma melhor identifi cação entre o modelo e o real. 
2 Programação Linear – equações e 
solução gráfi ca
Os problemas de Programação Linear (PL) buscam a 
distribuição efi ciente de recursos limitados para atender a 
um determinado objetivo, em geral, maximizar lucros ou 
minimizar custos. Em se tratando de PL, esse objetivo é 
expresso através de uma função linear, denominada de 
“Função Objetivo”. 
2.2 - Modelo de Pl de duas variáveis
Embora seja raro existirem problemas de duas variáveis 
na prática, seu tratamento proporciona uma forma didática 
de apresentar os conceitos de resolução de problemas 
envolvendo PO. Na prática, geralmente encontramos 
problemas com muitas variáveis. Porém, aqui iremos 
apresentar dois exemplos de problemas de duas variáveis 
para facilitar o entendimento, um de maximização e um de 
minimização.
2.3 – Resolvendo um problema de 
maximização
Para exemplifi car como resolvemos um problema de 
maximização, usaremos um exemplo fi ctício, adaptado de 
7
Taha (2008), de uma fábrica de tintas que busca maximizar 
seus lucros.
2.3.1 – A fábrica de tintas Aquarela 
Tintas
A Aquarela Tintas produz tintas para interiores e 
exteriores com base em duas matérias-primas, M1 e M2. A 
Tabela 1 apresenta os dados básicos do problema:
Tabela 1: Produção de tintas da Aquarela Tintas
Tonelada de matéria- 
prima por tonelada de:
Disponi-
bilidade 
máxima 
diária 
(ton)
Tinta para 
exteriores
Tinta para 
interiores
Matéria-prima M1 6 4 24
Matéria-prima M2 1 2 6
Lucro por tonelada 
(R$ 1.000,00) 5 4
Fonte: adaptado de Taha (2008).
Uma pesquisa de mercado indica que a demanda diária 
de tintas para interiores não pode ultrapassar a de tintas para 
exteriores por mais de 1 tonelada. Além disso, a demanda 
máxima diária de tinta para interiores é 2 t.
A Aquarela Tintas quer determinar o mix ótimo (o 
melhor) de produtos de tintas para interiores e exteriores 
que maximize o lucro total diário.
De acordo com Taha (2008), o modelo de PL, como 
qualquer modelo de PO, tem três componentes básicos.
1. Variáveis de decisão que procuramos determinar.
2. Objetivo (meta) que precisamos otimizar 
(maximizar ou minimizar).
3. Restrições que a solução deve satisfazer.
A definição adequada das variáveis de decisão é uma 
primeira etapa essencial no desenvolvimento do modelo. 
Uma vez concluída, a tarefa de construir a função objetivo 
e as restrições torna-se mais direta.
Para o problema da Aquarela Tintas, precisamos 
determinar as quantidades diárias a produzir de tintas para 
exteriores e interiores. Assim, as variáveis do modelo são 
definidas como:
x1.= toneladas de tinta para exteriores produzidas 
diariamente
x2: toneladas de tinta para interiores produzidas 
diariamente
 
Para construir a função objetivo, observe que a empresa 
quer maximizar (isto é, aumentar o máximo possível) o 
lucro total diário para as duas tintas. Dado que os lucros 
por tonelada de tintas para exteriores e interiores são de 5 e 
4 (mil) dólares, respectivamente, decorre que
Lucro total da tinta para exteriores = 5x1 (mil) dólares
Lucro total da tinta para interiores = 4x2 (mil) dólares
Representando o lucro total diário (em milhares de 
dólares) por z, o objetivo da empresa é
Maximizarz = 5x1 + 4x2
Em seguida, construímos as restrições que limitam a 
utilização da matéria-prima e a demanda do produto. As 
restrições sobre a matéria-prima são expressas em palavras 
como
Utilização de uma matéria-prima para ambas as tintas 
≤ Máxima disponibilidade de matéria-prima
A utilização por dia da matéria-prima M1 é de 6 t por 
tonelada de tinta para exteriores, e de 4 t por tonelada de 
tinta para interiores. Assim,
Utilização da matéria-prima M1 para tinta para 
exteriores = 6x1 t/dia
Utilização da matéria-prima M1 para tinta para 
interiores = 4x2 t/dia
Então temos que
Utilização da matéria-prima M1 para ambas as tintas = 
6x1 + 4x2 t/dia
De maneira semelhante,
Utilização da matéria-prima M2 para ambas as tintas = 
1x1 + 2x2 t/dia
Como as disponibilidades diárias das matérias-primas 
M1 e M2 estão limitadas a 24 e 6 ton, respectivamente, as 
restrições relacionadas são dadas como
6x1 + 4x2 ≤ 24 (matéria-prima M1)
x1 + 2x2 ≤ 6 (matéria-prima M2)
A primeira restrição relacionada à demanda estipula 
que o excesso da produção diária de tinta para interiores 
em relação à de tinta para exteriores, x2 – x1, não deve 
ultrapassar 1 ton, o que poderia ser traduzido para:
x2 - x1 ≤ 1 (limite de mercado)
A segunda restrição relacionada à demanda estipula 
que a demanda diária máxima de tinta para interiores está 
limitada a 2 ton, o que é traduzido para
x2 ≤ 2 (limite de demanda)
Ainda de acordo com Taha (2008), uma restrição 
implícita é que as variáveis x1 e x2 não podem assumir 
valores negativos. As restrições de não-negatividade, x1 ≥ 
0, x2 ≥ 0, são as responsáveis por esse requisito. O modelo 
completo da Aquarela Tintas é:
Maximizar z = 5x1 + 4x2
sujeito a:
1) 6x1 + 4x2 ≤ 24
2) x1 + 2x2 ≤ 6
3) -x1 + x2 ≤ 1
4) x2 ≤ 2
5) x1 ≥ 0
6) x2 ≥ 0
Quaisquer valores de x1 e x2 que satisfaçam todas 
as cinco restrições constituem uma solução viável. Caso 
contrário, a solução é inviável. Por exemplo, a solução x1 = 
3 t/d e x2 = 1 t/d é viável-porque não viola nenhuma das 
restrições, entre elas as de não-negatividade. Para verificar 
esse resultado, substitua (x1 = 3, x2 = 1) no lado esquerdo 
de cada restrição. Na restrição (1) temos 6x1 + 4x2 = 6 x 3 
+ 4 x 1 = 22, que é menor do que o lado direito da restrição 
(= 24). As restrições 2 a 6 resultarão em conclusões 
semelhantes (Verifique!). Por outro lado, a solução x1 = 4 
8Pesquisa Operacional
e x2 = 1 é inviável porque não satisfaz a restrição (1) — ou 
seja, 6 x 4 + 4 x 1 = 28, que é maior do que o lado direito 
(= 24). 
2.4 - Solução Gráfi ca em PL
Para exemplifi car como resolvemos um problema de 
PL com solução gráfi ca, usaremos o exemplo da fábrica 
de tintas Aquarela Tintas. De acordo com Taha (2008), 
o procedimento para resolução com gráfi co inclui duas 
etapas:
1. Determinação da região de soluções viáveis.
2. Determinação da solução ótima entre todo da região 
de soluções dos pontos viáveis.
O procedimento utiliza dois exemplos para mostrar 
como a maximização e a minimização das funções objetivo 
são tratadas. Vamos então resolver o modelo da Aquarela 
Tintas do Exemplo:
2.4.1 - Etapa 1: determinação da 
região de soluções viáveis 
Seguindo Taha (2008), em primeiro lugar, levamos 
em conta as restrições de não-negatividade x1 ≥ 0 e x2 
≥ 0. Na Figura 1, o eixo horizontal x1 e o eixo vertical x2 
representam as variáveis tinta para exteriores e tinta para 
interiores, respectivamente. Assim, a não negatividade das 
variáveis restringe a área da região de soluções ao primeiro 
quadrante que se encontra acima do eixo x1 e à direita do 
eixo x2. 
Figura 1: Representação gráfi ca do problema da fábrica 
de tintas.
Fonte: Taha (2008).
Para levar em conta as quatro restrições restantes, em 
primeiro lugar substitua cada desigualdade por uma equação 
e depois represente em gráfi co a linha reta resultante 
localizando dois pontos distintos nela. Por exemplo, após 
substituir 6x1 + 4x2 ≤ 24 pela linha reta 6x1 + 4x2 = 24, 
podemos determinar dois pontos distintos, primeiro ao 
fazer x1 = O para obter x2 = 24/4 = 6, e, após, ao fazer x2 = 
O para obter x1 = 24/6 = 4. Assim, a reta passa pelos dois 
pontos, (0, 6) e (4, 0), como mostra a reta (1) na Figura 1.
Ainda de acordo com Taha (2008), na sequência, 
considere o efeito da desigualdade. Tudo que ela faz é 
dividir o plano (x1, x2) em dois meios-espaços, um de cada 
lado da reta representada no gráfi co. Só uma dessas duas 
metades satisfaz a desigualdade. Para determinar o lado 
correto, tome (0, 0) como um ponto de referência. Se ele 
satisfi zer a desigualdade, o lado no qual ele se encontra é a 
meia-região viável; caso contrário, o viável é o outro lado. 
A utilização do ponto de referência (0,0) é ilustrada com a 
restrição 6x1 + 4x2 ≤ 24. Como 6 x 0 + 4 x 0 = 0 é menor do 
que 24, a meia-região que representa a desigualdade inclui a 
origem (como é mostrado pela seta na Figura 1).
Em termos de cálculo, é conveniente selecionar (0, 
0) como o ponto de referência, a menos que, por acaso, 
a reta passe pela origem, quando então qualquer outro 
ponto pode ser usado. Por exemplo, se usarmos o ponto 
de referência (6, 0), o lado esquerdo da primeira restrição 
é 6 x 6 + 4 x 0 = 36, que é maior do que seu lado direito 
(= 24), o que signifi ca que o lado no qual (6,0) se encontra 
não é viável para a desigualdade 6x1 + 4x2 5 24. A conclusão 
é consistente com a baseada no ponto de referência (0,0).
A aplicação do procedimento do ponto de referência a 
todas as restrições do modelo produz as restrições mostradas 
na Figura 1. A região de soluções viáveis do problema 
representa a área do primeiro quadrante na qual todas as 
restrições são satisfeitas simultaneamente. Na Figura 1, 
qualquer ponto que esteja dentro ou sobre o contorno da 
área ABCDEF é parte da região de soluções viáveis. Todos 
os pontos fora dessa área são inviáveis (TAHA, 2008).
2.4.2 - Etapa 2: determinação da 
solução ótimo
Seguindo o raciocínio exposto por Taha (2008), vemos 
que a região viável da Figura 1 é delimitada pelos segmentos 
de reta que unem os pontos A, B, C, D, E e F. Qualquer 
ponto dentro ou sobre o contorno do espaço ABCDEF 
é viável. Como a região viável ABCDEF consiste em um 
número infi nito de pontos, precisamos de um procedimento 
sistemático para identifi car a solução ótima. A determinação 
da solução ótima requer identifi car a direção na qual a 
função lucro z = 5x1 + 4x2 aumenta (lembre-se de que 
estamos maximizando z). Podemos fazer isso designando 
valores crescentes arbitrários a z. Por exemplo, usar z = 10 
e z = 15 equivaleria a representar em gráfi co as duas retas, 
5x1 + 4x2 = 10 e 5x1 + 4x2 = 15. 
Assim, a direção do aumento de z é a mostrada na 
Figura 2. A solução ótima ocorre em C, que é o ponto na 
região de soluções além do qual qualquer aumento adicional 
levará z para fora dos contornos de ABCDEF.
Os valores de x1 e x2 relacionados com o ponto ótimo C 
são determinados pela resolução das equações relacionadas 
com as retas (1) e (2), isto é, 
6x1 + 4x2 = 24
x1 + 2x2 = 6
A solução é x1 = 3 e x 2 = 1,5,com z = 5 x 3 + 4 x 1,5 
= 21. Isso representa um mix de produto diário de 3 t de 
tinta para exteriores e 1,5 t de tinta para interiores. O lucro 
diário associado é $ 21.000.
Figura 2: solução ótima do exemplo da fábrica de tintas
9
Fonte: Taha (2008). 
De acordo com Taha (2008), uma característica 
importante da solução ótima de PL e que ela sempre está 
relacionada com um ponto extremo da região de soluções 
(em que duas retas se cruzam). Isso é válido até se, por 
acaso, a função objetivo for paralela a uma restrição. Por 
exemplo, se a função objetivo for z = 6x1 + 4x2, que é 
paralela à restrição 1, sempre podemos dizer que a solução 
ótima ocorre no ponto extremo B ou no ponto extremo 
C. Na verdade, qualquer ponto sobre o segmento de reta 
BC será uma alternativa, mas a observação importante aqui 
é que o segmento de reta BC é totalmente definido pelos 
pontos extremos B e C.
A observaçãode que a solução ótima em PL está sempre 
associada a um ponto extremo significa que a solução ótima 
pode ser encontrada pela simples enumeração de todos os 
pontos extremos, como mostra a Tabela 2.
Tabela 2: Pontos e solução ótima do problema da 
fábrica de tintas.
Ponto extremo (x1; x2) z
A (0;0) 0
B (4;0) 20
C (3;1,5) 21 Ótimo
D (2;2) 18
E (1;2) 13
F (0;1) 4
Fonte: adaptado de Taha (2008).
À medida que o número de restrições e variáveis 
aumenta, o número de pontos extremos também aumenta, 
e o procedimento de enumeração proposto torna-se menos 
viável em termos de cálculo. Não obstante, a ideia mostra 
que, do ponto de vista da determinação da solução ótima 
em PL, o espaço de solução ABCDEF com seu número 
infinito de soluções pode, de fato, ser substituído por um 
número finito de soluções – ou seja, os pontos extremos A, 
B, C, D, E e F (TAHA, 2008).
2.5 - Solução de um modelo de 
minimização
Para exemplificar o problema de minimização, 
usaremos um exemplo adaptado de Taha (2008), de modelo 
de dieta, aqui apresentado como diminuir os custos de ração 
de uma fazenda, mas atendendo às restrições nutricionais 
da dieta da ração. 
A Fazenda São João usa, no mínimo, 800 lb de ração 
especial por dia. Essa ração especial é uma mistura de milho 
e soja com as composições elencadas na Tabela 3.
Tabela 3: Composição da ração na Fazenda São João
lb por lb de ração
Ração Proteína Fibra
Custo (R$/
lb)
Milho 0,09 0,02 0,3
Soja 0,6 0,06 0,9
Fonte: adaptado de Taha (2008).
Os requisitos nutricionais da ração especial são de no 
mínimo 30% de proteína e de no máximo 5% de fibra. 
A Fazenda São João quer determinar a mistura que gera 
a ração de mínimo custo diário. Como a ração consiste 
em milho e preparado de soja, as variáveis de decisão do 
modelo são definidas como:
x1 = lb de milho na mistura diária
x2 = lb de preparado de soja na mistura diária
A função objetivo procura minimizar o custo total 
diário da ração e, por isso, é expressa como:
Minimizar z = 0,3x1 + 0,9x2
As restrições do modelo refletem a quantidade diária 
necessária e os requisitos nutricionais. Como a Fazenda 
São João precisa de no mínimo 800 lb de ração por dia, a 
restrição associada pode ser expressa como
x1 + x2 ≥ 800
Quanto à restrição ao requisito nutricional de proteína, 
a quantidade de proteína presente em x1 lb de milho e x2 lb 
de preparado de soja é (0,09x1 + 0,6x2) lb. Essa quantidade 
deve ser igual a no mínimo 30% do total da mistura das 
rações (x1 + x2) lb, isto é:
0,09x1 + 0,6x2 ≥ 0,3(x1 + x2)
De modo semelhante, o requisito de no máximo 5% 
de libras é expresso por
0,02x1 + 0,06x2 ≥ 0,05(x1 + x2)
Podemos simplificar as restrições passando os termos 
em x1 e x2 para o lado esquerdo de cada desigualdade, 
deixando somente uma constante no lado direito. Assim, o 
modelo completo se torna: 
Minimizar z = 0,3x1 + 0,9x2
Sujeito a
x1 + x2 ≥ 800
0,21x1 - 0,30x2 ≤ 0
0,03x1 - 0,01x2 ≥ 0
X1, x2 ≥ 0
10Pesquisa Operacional
Figura 3: Solução gráfi ca para o modelo da dieta.
Fonte: Taha (2008).
A Figura 3 apresenta a solução gráfi ca do modelo. 
Diferente das restrições do modelo da Aquarela Tintas, a 
segunda e a terceira restrições passam pela origem. Para 
representar em gráfi co as retas associadas, precisamos de um 
ponto adicional, que pode ser obtido com a designação de 
um valor a uma das variáveis e depois com a resolução para 
a outra variável. Por exemplo, na segunda restrição, x1 = 200 
fará 0,21 x 200 - 0,3x2 = 0, ou x2 = 140. Isso signifi ca que 
a linha reta 0,21x1 - 0,3x2 = 0 passa por (0, 0) e (200, 140). 
Observe também que (0,0) não pode ser usado como um 
ponto de referência para as restrições 2 e 3 porque ambas 
as retas passam pela origem. Em vez disso, pode-se usar um 
outro ponto (por exemplo, (100,0) ou (0, 100)) para essa 
fi nalidade.
Solução:
Como o presente modelo busca a minimização da função 
objetivo, precisamos reduzir o valor de Z o máximo possível 
na direção mostrada na Figura 3. A solução ótima e o extremo 
das duas retas x1 + x2 = 800 e 0,21x1 - 0,3x2 = 0, o que dá 
como resultado x1 = 470,59 lb e x2 = 329,41 lb. O custo da 
ração e z = 0,3 x 470,59 + 0,9 x 329,42 = $ 437,65 por dia.
3 Modelo de PL em forma de equação 
– simplex
Nem sempre os problemas de PL são de fácil solução 
através de gráfi cos, e o dia a dia do engenheiro não permite 
fi car à mercê desse fato. Para resolver essa limitação, foi 
padronizado uma metodologia matemática para resolução 
dos problemas de programação linear, chamado de método 
simplex. De acordo com Taha (2008), o desenvolvimento dos 
cálculos do método simplex é facilitado pela imposição de 
novos requisitos às restrições do problema: 
1. Todas as restrições (com exceção da não negatividade 
das variáveis) são equações cujos lados direitos são 
não negativos.
2. Todas as variáveis são não negativas.
Aqui, a fi nalidade primordial desses dois requisitos e 
padronizar e tornar mais efi cientes os cálculos do método 
simplex. É importante saber que todos os pacotes comerciais 
aceitam diretamente restrições de desigualdade. Lados 
direitos não negativos e variáveis irrestritas. Qualquer 
precondicionamento necessário do modelo é realizado 
internamente no software antes de o método simplex resolver 
o problema.
3.2 - Conversão de desigualdades em 
equações com o lado direito não negativo
De acordo com Taha (2008), em restrições (≤), o lado 
direito pode ser considerado como a representação do limite 
imposto a disponibilidade de um recurso, caso em que o lado 
esquerdo representaria a utilização desse recurso limitado pelas 
atividades (variáveis) do modelo. Assim, a diferença entre o 
lado direito e o lado esquerdo da restrição (≤) resultaria na 
quantidade do recurso não utilizada ou folga.
Para converter uma desigualdade (é) em uma equação, 
uma variável de folga não negativa é adicionada ao lado 
esquerdo da restrição. Por exemplo, no modelo da Fazenda 
São João, a restrição associada com a utilização da matéria-
prima M1 é dada como
6x1 + 4x2 ≤ 24
Defi na-se S1 como a folga ou a quantidade não utilizada 
de M1, a restrição pode ser convertida na seguinte equação:
6x1 + 4x2 + 51 = 24, S1≥ 0
De forma semelhante, uma restrição (≥) estabelece um 
limite inferior para as atividades do modelo de PL, de modo 
que a quantidade pela qual o lado esquerdo excede o limite 
mínimo representa uma sobra (TAHA, 2008). Consegue-se 
a conversão de (≥) em (=) com a subtração de uma variável 
de sobra não negativa do lado esquerdo da desigualdade. Por 
exemplo, no modelo da dieta, a restrição que representa os 
requisitos mínimos da ração é: 
x1+ x2 ≥ 800
Defi na-se S1 como a variável de sobra, a restrição pode 
ser convertida na seguinte equação:
x1 + x2 – S1= 800, S1 ≥ 0
O único requisito restante é que o lado direito da equação 
resultante seja não negativo. A condição sempre pode 
ser satisfeita multiplicando-se ambos os lados da equação 
resultante por -1, onde necessário. Por exemplo, a restrição:
-x1 + x2 ≤ -3
é equivalente a equação:
-x1 + x2 +S1 =-3, S1 ≥ O
Agora, multiplicando ambos os lados por -1, teremos um 
lado direito não negativo, como desejado, isto é:
x1 - x2 -s1 = 3
3.3 - Detalhes de cálculo do algoritmo 
simplex
Esta seção apresenta os detalhes de cálculo de uma iteração 
do método simplex, incluindo as regras para determinar as 
variáveis que entram na base e que saem da base, bem como 
as regras para interromper os cálculos quando a solução ótima 
tiver sido alcançada. A explicação se dará por meio de um 
exemplo numérico.
Usamos o modelo da Fazenda São João para explicar 
os detalhes do método simplex. O problema é expresso na 
forma de equações como: 
Maximizar z = 5x1 + 4x2 + 0s1 + 0s2 + 0s3 + 0s4
11
sujeito a:
6x1 + 4x2 + s1 = 24 (matéria-prima M1)
x1 + 2x2 + s2 = 6 (matéria-prima M2)
-x1 + x2 + s3 = 1 (limite de mercado)
x2 + s4 = 2 (limite da demanda)
x1,x2,s1,s2,s3,s4 ≥ 0
As variáveis s1, s2, s3 e s4 são as folgas associadas às 
respectivas restrições.
Em seguida, escrevemos afunção objetivo como:
z - 5x1 - 4x2 = 0
Dessa maneira, a tabela simplex inicial pode ser 
representada da seguinte maneira:
Base z x1 x2 s1 s2 s3 s4 Solução  
z 1 -5 -4 0 0 0 0 0 linha z
s1 0 6 4 1 0 0 0 24 linha s1
s2 0 1 2 0 1 0 0 6 linha s2
s3 0 -1 1 0 0 1 0 1 linha s3
s4 0 0 1 0 0 0 1 2 linha s4
Fonte: Taha (2008). 
O arranjo da tabela especifica o conjunto de variáveis 
básicas e não básicas, bem como apresenta a solução associada 
com a iteração inicial. As iterações simplex começam na 
origem, (x1, x2) = (0,0), cujos conjuntos associados de variáveis 
não básicas e básicas são definidos como:
Variáveis (zero) não básicas = (x1, x2)
Variáveis básicas = (s1,s2,s3,s4)
Substituindo as variáveis não básicas (x1, x2) = (0,0), a 
seguinte solução está imediatamente disponível (sem nenhum 
cálculo):
z = 0
s1=24
s2 = 6
s3 = 1
s4 =2
Essa informação é mostrada na tabela pela listagem das 
variáveis básicas na coluna da extrema esquerda, “Base”, 
e seus valores aparecem na coluna da extrema direita, 
“Solução”. Na verdade, a tabela define o ponto extremo atual 
especificando suas variáveis básicas e seus valores bem como 
o valor correspondente da função objetivo, z. Lembre-se de 
que as variáveis não básicas (as que não aparecem na lista da 
coluna Base) sempre são iguais a zero.
A solução inicial é ótima? Não, pois a função objetivo z = 
5x1 + 4x2 mostra que um aumento em x1 ou x2 (ou em ambas) 
acima de seus valores zero atuais melhorará o valor de z. O 
projeto do método simplex exige o aumento de uma variável 
por vez, sendo que a variável selecionada será aquela que tiver 
a maior taxa de melhoria em z. O valor de z aumentará em 5 
para cada unidade de aumento de x1 e em 4 para cada unidade 
de aumento em x2. Isso significa que a taxa de melhoria no 
valor de z é 5 para x1 e 4 para x2. Assim, optamos por aumentar 
x1, a variável que tem a maior taxa de melhoria. Essa regra é 
denominada condição de otimalidade.
A mecânica da determinação da variável que sai com base 
na tabela simplex exige o cálculo das razões não negativas entre 
o lado direito das equações (coluna Solução) e o coeficiente 
de restrição correspondente da variável que entra, x1, como 
mostra a tabela: 
Entrando
Base x1 Solução Razão
s1 6 24 x1 = 26/6 =  mínimo
s2 1 6 x1 = 6/1 = 6
s3 -1 1 x1 = 1/-1 = -1 (ignorar)
s4 0 2 x1 = 2/0 = ∞ (ignorar)
Conclusão: x1 entra e s1 sai
A razão mínima não negativa identifica automaticamente 
a variável s1 como a variável que sai da base e designa a variável 
que entra na base (x1) o valor de 4.
Segundo Taha (2008), o processo de troca é baseado 
nas operações de Gauss-Jordan, que identifica a coluna da 
variável que entra na base como a coluna do pivô, e a linha da 
variável que sai como a linha do pivô. A interseção da coluna 
do pivô com a linha do pivô é denominada elemento pivô. A 
tabela seguinte é uma reafirmação da tabela do começo com 
sua coluna e linhas dos pivôs em destaque.
Entra
  Base z x1 x2 s1 s2 s3 s4 Solução  
  Z 1 -5 -4 0 0 0 0 0  
Sai s1 0 6 4 1 0 0 0 24 Linha pivô
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2  
Coluna 
Pivô
Os cálculos por Gauss-Jordan necessários para produzir 
a nova solução básica são de dois tipos.
1. Linha do pivô
b. Substituir & variável que sai da base na coluna Base 
pela variável que entra na base.
c. Nova linha do pivô = Linha do pivô atual + 
Elemento pivô
2. Todas as outras linhas, incluindo z
Nova linha = (Linha atual) - (Seu coeficiente de coluna 
do pivô) x(Nova linha do pivô)
  Base z x1 x2 s1 s2 s3 s4 Solução
  Z 1 0 -2/3 5/6 0 0 0 20
x1 0 1 2/3 1/6 0 0 0 4
 s2 0 0 4/3 -1/6 1 0 0 2
s3 0 0 5/3 1/6 0 1 0 5
12Pesquisa Operacional
  s4 0 0 1 0 0 0 1 2
Observe que a nova tabela tem as mesmas propriedades 
da tabela inicial. Quando igualamos as novas variáveis não 
básicas x2 e s1 a zero, a coluna Solução dá automaticamente 
a nova solução básica (x1 = 4, s2 = 2, s3 = 5, s4 = 2). Esse 
“condicionamento” da tabela é o resultado da aplicação das 
operações de linha por Gauss-Jordan. O novo valor da função 
objetivo correspondente e z = 20, que é consistente com
Novo z =Velho z + Novo valor x1 x Seu coefi ciente na 
função objetivo
= 0 + 4 x 5 = 20
Na última tabela, a condição de otimalidade mostra 
que x2 é a variável que deve entrar na base. A condição de 
viabilidade produz o seguinte
Entrando
Base x2 Solução Razão
x1 2/3 4 x2 = 2/(2/3) = 6
s2 4/3 2 x2 = 2/(4/3) = 1,5 (mínimo)
s3 5/3 5 x2 = 5/(5/3) = 3
s4 1 2 x2 = 2/1 = 2
Assim, s2 sai da solução básica e o novo valor de x2 é 1,5, 
o que da
z = 20 + 1 = 21.
Substituindo s2 na coluna Base por x2 que entra, as 
seguintes operações de fi la por Gauss-Jordan são aplicadas:
Base z x1 x2 s1 s2 s3 s4 Solução
Z 1 0 0 3/4 1/2 0 0 21
x1 0 1 0 1/4 -1/2 0 0 3
x2 0 0 1 -1/8 3/4 0 0 3/2
s3 0 0 0 3/8 -5/4 1 0 5/2
s4 0 0 0 1/8 -3/4 0 1 1/2
Com base na condição de otimalidade, nenhum dos 
coefi cientes da linha z associados com as variáveis não básicas, 
s1 e sz, é negativo. Assim, essa tabela simplex é ótima.
A solução ótima pode ser lida na tabela simplex da 
seguinte maneira: os valores ótimos das variáveis na coluna 
Base são dados na coluna Solução do lado direito da tabela, 
e podem ser interpretados como demonstrado na tabela a 
seguir
Variável de 
decisão
Valor 
ótimo Recomendação
x1 3
Produzir 3 ton diárias de tintas para exterio-
res
x2 3/2
Produzir 1,5 ton diária de tintas para interio-
res
z 21 Lucro diário é de $ 21.000,00
4 - Solução com computador com o 
excel solver
Na prática, quando vamos resolver um problema de 
programação linear, geralmente encontramos muitas variáveis 
e restrições, inviabilizando a resolução pelo método gráfi co. 
Nesses casos, o modo viável para resolução é a utilização 
de computador. Existem vários softwares que auxiliam 
a resolução de problemas de programação linear, dentre 
eles podemos citar: Excel Solver; a linguagem AMPL; o 
What’sBest!; e o Lingo.
A seguir, usaremos o exemplo da fábrica de tintas para 
demonstrar a forma de solução usando o Solver. A planilha do 
excel deve contar os dados de entrada, como função objetivo 
e as restrições. Veja na Figura 4, abaixo, um exemplo de como 
montar essa planilha de entrada de dados.
Figura 4: exemplo de como montar essa planilha de 
entrada de dados
Fonte: adaptado de Taha (2008) 
Essa planilha é apenas um modelo, demonstrando como 
inserir os dados. A Tabela 4 mostra as funções da programação 
linear e seu posicionamento adequado nas células.
Tabela 4: funções a serem inseridas no modelo 
apresentado na Figura 4
Expressão algébrica Fórmula na planilha
Inserida 
na célula
Objetivo (z) 5x1 + 4x2 =C5*$C$16+$D$16*D5 E5
Restrição 1 6x1 + 4x2 =C9*$C$16+$D$16*D9 E9
Restrição 2 x1 + 2x2 =C10*$C$16+$D$16*D10 E10
Restrição 3 -x1 + x2 =C11*$C$16+$D$16*D11 E11
Restrição 4 0x1 + x2 =C12*$C$16+$D$16*D12 E12
Fonte: adaptado de Taha (2008).
Agora, com a planilha montada, vamos utilizar o solver 
do excel para achar a solução ótima. Para adicionar o solver 
em seu excel, primeiramente clique em “Arquivo”, e em 
seguida “Opções”, conforme a Figura 5. Na sequência vá em 
“Suplementos” e adicione o “Solver”, conforme a Figura 6.
13
Figura 5: Opções do Excel
Fonte: o autor
Figura 6: Suplementos do Excel
 
Fonte: o autor.
Após o solver devidamente adicionado em seu Excel, clique na aba “dados” e em seguida abra a opção “solver”, conforme 
a Figura 7.
Figura 7: Solver no Excel
Fonte: o autor.
14Pesquisa Operacional
Conforme mostra a Figura 8, aberta a janela “Parâmetros 
do Solver”, primeiramente clique a opção “Defi nir objetivo” e 
selecione a célula E5, que é a função objetivo a ser maximizada. 
Em seguida, clique na opção “Max”, de maximização, e por 
último, clique na opção “Alterando Células Variáveis” e 
selecione as células C16 e D16, instruindo assim o Solver a 
alterar os valores dessas células para achar o ponto ótimo de z. 
No método de solução opte p ela opção “LP Simplex”.
Figura 8: janela de parâmetros do solver
Fonte:o autor.
Após isso, temos que inserir as restrições na janela do 
solver. Fazemos isso clicando no botão adicionar. Ao abrir 
o popup do botão adicionar, faremos conforme a Figura 
6, selecionando as células C16 e D16, selecionando o sinal 
“≥” e no campo “restrição” digitaremos o valor “0” (zero). 
Dessa forma informaremos que os valores que o solver 
deve nos passar tem que ser “não negativos”. Na sequência 
devemos clicar novamente no botão “adicionar”, para inserir 
as restrições do problema. No campo “referência de célula” 
devemos selecionar de uma só vez as células E9, E10, E11 e 
E12 (clicando e arrastando). O sinal é o mesmo da planilha 
(≤), e no campo restrição devemos selecionar os valores da 
coluna limite (G9, G10, G11 e G12).
Figura 9: programando restrições do solver
Fonte: o autor.
Inseridas as restrições, basta clicar em “ok” e em seguida 
no botão “resolver”. O Excel irá automaticamente preencher 
os valores das células C16 e D16 com a solução ótima que 
maximize o valor da célula E5. 
Ao chegar ao fi nal da primeira aula, vamos recordar o 
que aprendemos:
Retomando a aula
1- Origem e defi nições da pesquisa operacional 
Nesta seção, iniciamos vendo a origem e defi nições de 
pesquisa operacional (PO). Vimos que teve suas inspirações 
na Segunda Guerra Mundial e depois foi se desvinculando aos 
poucos da origem militar. Na sequência, falamos um pouco 
sobre modelagem e vimos exemplos de problemas reais de 
aplicação de PO.
2- Programação Linear – equações e solução gráfi ca
Na segunda seção da aula, falamos da Programação 
Linear (PL), que é a espinha dorsal da maioria dos problemas 
de PO. Vimos exemplos de maximização e minimização, 
além de uma técnica de resolução muito útil, principalmente, 
no mercado de trabalho, que é a resolução gráfi ca.
3 - Modelo de Pl em forma de equação – simplex 
Na terceira parte da aula, vimos uma forma mais 
elaborada de resolução de problemas de PL, que é o algoritmo 
SIMPLEX, que é muito utilizado academicamente e também 
em criação de softwares, por ser mais conceitual.
4 - Solução com computador com o excel solver
 Finalmente, na quarta parte da aula, vimos a solução 
computacional através do Excel, que é mais comum de ser 
utilizada no dia a dia de um engenheiro em seu local de 
trabalho. 
ARENALES, M.; ARMENTANO, V. A.; MORABITO, 
R.; YANASSE, H. H. Pesquisa operacional. Rio de Janeiro: 
Campus/Elsevier, 2015.
HILLIER, F.S. e Lieberman G.J., Introdução à Pesquisa 
Operacional, 8ª. edição. São Paulo: McGraw-Hill, 2006.
LACHTERMACHER, G. Pesquisa operacional na 
tomada de decisões, 5ª. edição. São Paulo: Prentice Hall, 
2016.
TAHA, H. A.. Pesquisa Operacional. 8ª edição. São 
Paulo: Pearson, 2008.
Vale a pena ler
Vale a pena
15
Disponível em: https://www.informs.org/. Acesso 
em: 09 dez. 2019.
Disponível em: https://www.sobrapo.org.br/. Acesso 
em: 09 dez. 2019.
Vale a pena acessar
Minhas anotações