Bases de Otimização com o MS Excel

Prévia do material em texto

Bases de Otimização com o MS Excel
Renata Albergaria de Mello Bandeira
false
Descrição
A Pesquisa Operacional e a construção de modelos lineares utilizando o
método simplex, no MS Excel.
Propósito
Conhecer a natureza da Pesquisa Operacional e dominar a solução de
problemas de Programação Linear, por meio do método simplex ou pela
utilização de softwares, permitirá que você aplique a técnica de
modelagem ao processo de decisão de problemas complexos de
diversas origens, em especial, em sua atuação profissional.
Preparação
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
1 of 115 25/09/2024, 12:37
Preparação
Para este conteúdo, são necessários uma calculadora e um software
editor de planilhas eletrônicas com o add-in do solver habilitado.
Objetivos
Módulo 1
Pesquisa Operacional
Descrever conceitos gerais de Pesquisa Operacional e sua
importância no processo de tomada de decisão.
Módulo 2
Modelo de programação linear
Descrever as principais características e propriedades de um modelo
de Programação Linear.
Módulo 3
Método simplex para a resolução de
problemas de programação linear
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
2 of 115 25/09/2024, 12:37
Empregar o método simplex para a solução de problemas de
Programação Linear.
Módulo 4
Solução de problemas de programação linear
Aplicar o solver para a solução de problemas de Programação Linear.
É comum termos dificuldades para identificar a melhor solução
quando nos deparamos com um problema complexo. Afinal, são
tantos os dados e possíveis cenários que não conseguimos
processar sozinhos tantas informações. Esse tipo de situação é
comum em nossas vidas pessoais e, especialmente, nos negócios.
Acabamos, nesses casos, tomando decisões com base em
opiniões, intuições ou em experiências passadas – nossas ou
mesmo de outras pessoas ou empresas. Sem dúvidas, esses
caminhos são importantes e devem ser sempre considerados no
processo de tomada de decisão. No entanto, em situações
complexas, o desenvolvimento de modelos pode ser uma poderosa
ferramenta de auxílio à tomada de decisão.
Modelos são simplificações do objeto ou do problema de decisão
que representam. A grande vantagem em adotar um modelo para
apoio ao processo de tomada de decisão é a possibilidade de
examinar diferentes cenários, em geral, de forma mais rápida e
barata do que se fosse analisado na realidade. Entre os diversos
Introdução
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
3 of 115 25/09/2024, 12:37
barata do que se fosse analisado na realidade. Entre os diversos
tipos de modelo que podem ser utilizados, destacam-se os
modelos matemáticos, que adotam a lógica e a formulação
matemática para representar o problema estudado.
A Pesquisa Operacional (PO) é o campo do conhecimento que trata
do desenvolvimento de modelos matemáticos e algoritmos para
auxiliar o decisor na análise de problemas complexos. A PO se
destaca por fornecer uma ferramenta quantitativa para apoio ao
processo de tomada de decisão para problemas complexos.
No contexto da programação linear, que se aplica, por exemplo, no
planejamento de redes logísticas, há métodos, como o método
gráfico, que se restringem à solução de problemas com apenas
duas ou no máximo três variáveis de decisão. Como solucionar,
então, problemas mais complexos, com maior número de variáveis
de decisão? Este é o assunto a ser tratado neste tema. Além dos
conceitos básicos de Pesquisa Operacional e modelagem de
problemas com equações lineares, abordaremos o método simplex
para a solução de problemas de programação linear e
aprenderemos a utilizar o solver do Excel para a solução desse tipo
de problema.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
4 of 115 25/09/2024, 12:37
1 - Pesquisa Operacional
Ao �nal deste módulo, você será capaz de descrever conceitos gerais de Pesquisa Operacional
e sua importância no processo de tomada de decisão.
Apresentação do tema
Neste vídeo você conhecerá o conceito de Pesquisa Operacional, sua
origem e as áreas de aplicação:

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
5 of 115 25/09/2024, 12:37
Pesquisa operacional
A Pesquisa Operacional (PO) é definida pela Sociedade Brasileira de
Pesquisa Operacional (SOBRAPO) 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.
SOBRAPO, 2021
A Pesquisa Operacional fornece ferramentas quantitativas ao processo
de tomada de decisões (PRADO, 2016). Dessa forma, a PO auxilia o
decisor na análise de variados aspectos e situações de um problema
complexo, por meio de uso de técnicas de modelagem matemática e
eficientes algoritmos computacionais. Isso permite a tomada de
decisões efetivas e a construção de sistemas mais produtivos
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
6 of 115 25/09/2024, 12:37
(SOBRAPO, 2021).
O estudo da PO permite o domínio de diversas técnicas
relacionadas à programação e modelagem
matemática.
Por meio desses conceitos e das ferramentas quantitativas, poderemos
analisar os mais variados tipos de problemas, e fornecendo dados e
informações concretos para auxiliar no processo de tomada de decisão.
Saiba mais
Sociedade Brasileira de Pesquisa Operacional
Fundada em 1969, a Sociedade Brasileira de Pesquisa Operacional
(SOBRAPO) reúne os profissionais de Pesquisa Operacional que atuam
no País – em universidades, na iniciativa privada e no setor público –,
com o objetivo de incentivar o desenvolvimento desse campo do
conhecimento.
Além de organizar simpósios anuais, a SOBRAPO mantém as revistas
Pesquisa Operacional e Pesquisa Operacional para Desenvolvimento,
buscando incentivar a publicação sobre o tema.
Origem – Circo de Blacket
A PO teve seus primeiros casos de aplicação no meio militar, durante a
Segunda Guerra Mundial.
Na ocasião, foram formados grupos de cientistas de diferentes
especialidades a fim de oferecer apoio quantitativo aos comandantes
das operações militares inglesas e norte-americanas para a solução de
complexos problemas de natureza logística e de tática e estratégia
militar (BELFIORE; FÁVERO, 2012).
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
7 of 115 25/09/2024, 12:37
militar (BELFIORE; FÁVERO, 2012).
Saiba mais
Entre os grupos formados, destacou-se o aquele liderado por Patrick
Maynard Stuart Blackett – o Barão de Blackett. A equipe do Barão de
Blackett, composta por membros de formações diversas – físicos,
matemático, topógrafos, astrofísicos e fisiólogos –, era conhecida como
o Circo de Blackett. A equipe foi responsável pela publicação de um dos
primeiros artigos sobre Pesquisa Operacional.
O artigo apresentava um modelo matemático para analisar o emprego
dos meios antiaéreos das tropas aliadas para fazer frente aos
bombardeiros alemães (Stuckas). Outros problemas típicos abordados
na ocasião se referiam ao tamanho e roteamento de comboios, ao
gerenciamento da produção e à distribuição de armamentos e
munições, à coleta e distribuição de correspondência, ao problema de
escala e à localização de radares, de modo a maximizar as áreas de
cobertura.
Os bons resultados obtidos com a aplicação das
técnicas de Pesquisa Operacional durante a Segunda
Guerra levaram à disseminação desse conhecimento
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
8 of 115 25/09/2024, 12:37
entre organizações de diversas áreas após o fim do
período de combate.
A partir de 1947, é crescenteda Glass Co., ao aumentarmos o valor de de 0
a 6, temos mudanças na solução.
f
2
= 12 − 2x
2
≥= 0 → x
2
≤ 12/2 = 6 ←
f
3
= 18 − 2x
2
≥ 0 → x
2
≤ 18/2 = 9
x
2
f
2
x
2
Solução inicial 
x
1
= 0
x
2
= 0
F
1
= 4
F
2
= 12
F
3
= 18
Nova solução 
x
1
= 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
69 of 115 25/09/2024, 12:37
Temos que é igual a 6 e continua sendo zero. Portanto, temos que
. Devemos determinar, então, os
valores de , e .
A nova solução é ( ) e !
Então, devemos verificar se essa solução é ótima ou não, por meio do
teste de otimalidade. Sendo , verificamos que tem o
coeficiente positivo ( ), de modo que aumentar implica em
aumentar . Portanto, a solução atual não é ótima e devemos realizar
nova iteração, analisando a entrada de como variável básica. Dessa
forma, devemos realizar o teste da mínima razão para determinar qual
variável básica deve se tornar nula, saindo então da base, para permitir a
“entrada” de .
Teste da mínima razão
 nenhum limite superior em 
 mínima
x
2
= 6
F
1
=?
F
2
= 0
F
3
=?
x
2
x
1
Z = 3x
1
+ 5x
2
= 3 ∗ 0 + 5 ∗ 6 = 30
f
1
f
2
f
3
x
1
+ f
1
= 4 → 0 + f
1
= 4 → f
1
= 4
2x
2
+ f
2
= 12 → 2 ∗ 6 + f
2
= 12 f
2
= 0
3x
1
+ 2x
2
+ f
3
= 18 → 3 ∗ 0 + 2 ∗ 6 + f
3
= 18 → f
3
= 6
0, 6, 4, 0, 6 Z = 30
Z = 3x
1
+ 5x
2
x
1
= 3 x
1
Z
x
1
x
1
Z − 3x
1
− 2, 5x
2
= 30
x
1
+ f
1
= 4
2x
2
+ f
2
= 12
3x
1
+ 2x
2
+ f
3
= 18
f
1
= 4 − x
1
≥ 0 → x
1
≤ 4/1 → x
1
≤ 4
f
2
= 12 − 2x
2
≥ 0 → x
1
f
3
= 6 − 3x
1
≥ 0 → x →≤ 6/3 → x
1
≤ 2 →
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
70 of 115 25/09/2024, 12:37
 mínima
razão
Logo, sai da base para entrar com o valor igual a 2. Porém, ao
aumentarmos o valor de de 0 a 2, temos mudanças na solução.
Temos que é igual a 6 e equivale a 2. Logo, temos que
. Devemos determinar, então, os
valores de , e .
f
3
= 6 − 3x
1
≥ 0 → x →≤ 6/3 → x
1
≤ 2 →
f
3
x
1
x
1
Solução inicial 
x
1
= 0
x
2
= 6
F
1
= 4
F
2
= 0
F
3
= 18
Nova solução 
x
1
= 2
x
2
= 6
F
1
=?
F
2
= 0
F
3
=?
x
2
x
1
Z = 3x
1
+ 5x
2
= 3 ∗ 2 + 5 ∗ 6 = 36
f
1
f
2
f
3
x
1
+ f
1
= 4 → 2 + f
1
= 4 → f
1
= 2
2x
2
+ f
2
= 12 → 2 ∗ 6 + f
2
= 12 → f
2
= 0
3x
1
+ 2x
2
+ f
3
= 18 → 3 ∗ 2 + 2 ∗ 6 + f
3
= 18 → f
3
= 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
71 of 115 25/09/2024, 12:37
Portanto, concluímos que substitui como variável básica, sendo a
nova solução igual a ( ) e . As variáveis não básicas
agora são e . Verificamos que aumentar as atuais variáveis não
básicas não implica em aumento em , o que garante que esta é a
solução ótima.
Método simplex em sua forma tabular
Aprendemos até agora a forma algébrica do simplex, que é a melhor
para aprender a lógica por trás do algoritmo. Porém, não é a forma mais
conveniente para realizar cálculos necessários. As operações realizadas
no método simplex podem ser organizadas em tabelas, chamadas
tabelas simplex. Essa organização é a mais indicada para quando
estivermos resolvendo um problema de programação linear
manualmente.
Considere um problema de otimização linear:
Nesse problema, temos as variáveis . Os coeficientes da
função objetivo são . Os coeficientes das restrições são
 e .
Arenales et al. (2007) descrevem as operações realizadas em cada
iteração do algoritmo simplex em tabelas, em duas fases.
3x
1
+ 2x
2
+ f
3
18 → 3 ∗ 2 + 2 ∗ 6 + f
3
18 → f
3
0
x
1
f
3
2, 6, 2, 0, 0 Z = 36
f
2
f
3
Z
 Minimizar f(x) = cx
Ax = b
x ≥ 0
x
1
, x
2
… x
n
c
1
, c
2
… c
n
a
1
, a
2
… a
n
b
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
72 of 115 25/09/2024, 12:37
Fase 1:
Determine a tabela simplex inicial.

A matriz dos coeficientes contém uma matriz identidade (m é o
número de equações) e o vetor independente .

A função objetivo é escrita em termos das variáveis não básicas, isto é,
os coeficientes das variáveis básicas são nulos.

Faça a iteração .
Fase 2:
mxm
b ≥ 0
= 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
73 of 115 25/09/2024, 12:37
Determine o menor dos custos relativos: = mínimo { para toda
variável não básica}.

Se , então pare (a solução básica na iteração é ótima). Se não, a
variável entra na base.

Se , então e o problema não tem
solução ótima finita. Nesse caso, pare.
Se não, determine mínimo tal que . (a
variável básica da linha l sai da base).

Atualize a tabela simplex (pivoteamento do elemento . A variável
 passa a ser a variável básica na linha l. Faça a iteração = iteração +1
e retorne ao passo 1.
Na forma de algoritmo, como apresentado por Arenales et al. (2007), o
método simplex tabular pode parecer difícil, mas vamos entendê-lo
resolvendo o exemplo da Glass Co., cujo modelo em formato canônico é
c
k
c
j
c
k
≥ 0
x
k
a
ik
≤ 0, i = 1, … , m f → −∞
b
l
a
lk
{
b
i
a
ik
a
ik
> 0, i = 1, … , m}
(l, k))
x
k
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
74 of 115 25/09/2024, 12:37
resolvendo o exemplo da Glass Co., cujo modelo em formato canônico é
apresentado a seguir.
Inicialmente, vamos definir o formato da tabela de maneira a facilitar
sua compreensão. A tabela simplex tem, do lado esquerdo, as variáveis
básicas e, do lado direito, as constantes das equações. No meio da
tabela, ficam todos os coeficientes das restrições e da função objetivo.
Por padronização, colocaremos na primeira linha (zero) a equação que
representa a função objetivo, conforme apresentado na figura a seguir.
Tabela simplex.
Uma escolha viável para a primeira base para o problema da Glass Co.
MaxZ = 3x
1
+ 5x
2
 s.a. 
x
1
+ f
1
= 4 →  restrição 1
2x
2
+ f
2
= 12 →  restrição 2
3x
1
+ 2x
2
+ f
3
= 18 →  restrição 3
x
1
, x
2
, f
1
, f
2
, f
3
>= 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
75 of 115 25/09/2024, 12:37
Uma escolha viável para a primeira base para o problema da Glass Co.
seria ( , e ), pois facilitaria o preenchimento da tabela simplex
inicial, dado que .
Quando as variáveis de folga constituem a primeira base, na primeira
linha da tabela simplex, apenas escrevemos o negativo dos coeficientes
de custo das variáveis não básicas. Como representa a
potencial melhoria no valor de da função objetivo representada pela j-
ésima variável, as variáveis atualmente básicas devem receber o valor
zero, pois já se encontram na base. Assim, a primeira linha da tabela
simplex para o exemplo da Glass Co. é:
f
1
f
2
f
3
B = I e B
−1
= I
MaxZ = 3x
1
+ 5x
2
x
1
+ f
1
= 4
2x
2
+ f
2
= 12
3x
1
+ 2x
2
+ f
3
= 18
  a
3
a
4
a
5
a
1
a
2
A = [ ] =
  f
1
f
2
f
3
x
1
x
2
B I N
⎡
⎣
1 0 0 I 1 0
0 1 0 I 0 2
0 0 1 I 3 2
⎤
⎦
B = B
−1
=
⎡
⎣
1 0 0
0 1 0
0 0 1
⎤
⎦
⎡
⎣
1 0 0
0 1 0
0 0 1
⎤
⎦
z
j
− c
j
z
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
76 of 115 25/09/2024, 12:37
simplex para o exemplo da Glass Co. é:
-3 -5
O valor atual de , , para esta primeira tabela, com as variáveis
básicas sendo , , , seria igual a zero, pois e
. Assim, atualizando a tabela, tem-se:
-3 -5
Em seguida, devem-se escrever as linhas que compõem as restrições da
tabela simplex, conforme indicado na figura a seguir.
Restrições da tabela simplex.
Para cada variável do problema, deve-se determinar . Como as
variáveis de folga foram escolhidas como aprimeira base, temos 
x
1
x
2
Z
Z Z
0
f
1
f
2
f
3
Z = 3x
1
+ 5x
2
x
1
= x
2
= 0
x
1
x
2
Z
y
j
B I
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
77 of 115 25/09/2024, 12:37
variáveis de folga foram escolhidas como a primeira base, temos 
e . Logo, temos , de modo que as linhas que compõem
as restrições no tableau são copiadas diretamente do problema. Ainda,
as variáveis atualmente na base ( , , ) são identificadas à esquerda
da tabela simplex, como pode ser identificado na figura a seguir.
Preenchendo a tabela simplex para o problema da Glass Co.
Observa-se, por meio da figura anterior, que os únicos elementos
faltantes estão do lado direito da tabela simplex e correspondem à
fórmula:
Desse modo, para a tabela inicial, basta copiar os valores de no lado
direito da tabela, conforme apresentado na figura a seguir.
B = I
B
−1
= I y
j
= a
j
f
1
f
2
f
3
Max Z = 3x
1
+ 5x
2
s. a.
¯
b = B
−1
b = Ib = b
b
Max Z = 3x
1
+ 5x
2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
78 of 115 25/09/2024, 12:37
Tabela simplex inicial para o problema da Glass Co.
Uma vez preenchida a tabela inicial, devemos identificar as variáveis
candidatas a entrar na base na primeira linha da tabela. Para isso,
devemos analisar os valores dos coeficientes de cada variável
apresentados na segunda linha da tabela simplex, levando em
consideração o tipo de problema apresentado, maximização ou
minimização:
Problema de
maximização
Em um problema de
maximização, a variável
cujo coeficiente é
negativo e apresenta o
maior valor absoluto é
aquela que entrará na
base.
Problema de
minimização
Em um problema de
minimização, a variável
a entrar na base será a
que tiver o maior valor
positivo.
s. a.

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
79 of 115 25/09/2024, 12:37
Por meio da figura da Tabela simplex inicial para o problema da Glass
Co., observamos que a variável a entrar na base no problema da Glass
Co. é , uma vez que tanto quanto têm valores negativos na
segunda linha da tabela, sendo .
Depois de identificarmos a variável que entra na base, é preciso
determinar a variável básica que deve dar lugar para que entre na
base. Para isso, aplicamos o teste da mínima razão, conforme indicado
na figura a seguir. Observa-se que o menor valor é 6, de modo que a
variável a sair da base é .
Teste da mínima razão para o problema da Glass Co.
Para completar a iteração do simplex, devemos, então, proceder com as
operações elementares que utilizam a linha que contém o elemento de
pivot, de modo que a coluna (da variável entrante) assuma a
configuração da coluna (variável que sai da base). Observe, na figura
a seguir, que a linha pivot é a quarta linha da tabela (atual linha do no
lado esquerdo da tabela) e que os valores para as colunas e não
coincidem, de modo que é necessário executar a operação elementar.
Portanto, sendo a linha a quarta linha da tabela (3) após a operação
elementar, tem-se que a operação que transformará 2 em 1 é:
.
x
2
x
x
x
2
5 > 3.
x
2
f
2
x
2
f
2
f
2
x
2
f
2
(3)
′
(3)
′
= (3)/2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
80 of 115 25/09/2024, 12:37
Operações com a linha pivot para o problema da Glass Co.
Observe, na segunda tabela da figura anterior, que, para a coluna 
assumir a configuração anterior da coluna , é preciso ainda realizar
operações elementares nas linhas (1) e (4) da tabela simplex. Assim,
para a linha , é preciso que , enquanto para a
linha devemos fazer , conforme indicado na
próxima figura.
Dica
Para a linha (2), não é preciso realizar nenhuma operação, uma vez que
os valores para as colunas e já são coincidentes.
Operações com a linha pivot para o problema da Glass Co.
Verifique, na figura anterior, que a coluna ainda apresenta um valor
negativo na segunda linha da tabela simplex, de modo que esta variável
x
2
f
2
(4)
′
(4)
′
= (4) − 2
∗
(3)
(1)
′
(1)
′
= (1) + 5
∗
(3)
′
x
2
f
2
x
1
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
81 of 115 25/09/2024, 12:37
negativo na segunda linha da tabela simplex, de modo que esta variável
deve entrar na base, sendo necessária, então, mais uma iteração. Logo,
faz-se o teste da mínima razão, conforme indicado na figura a seguir,
sendo verificado que a variável a sair da base para que entre é .
Portanto, são necessárias as operações elementares para que a coluna
 receba os valores da coluna .
Teste da mínima razão para o problema da Glass Co. — 2a iteração
Observa-se, na figura do Teste da mínima razão para o problema da
Glass Co. — 2a iteração, que a quinta linha (4) da tabela simplex é a
linha pivot. Assim, para que a coluna receba os valores da coluna ,
a primeira operação elementar a ser feita é: , tal como
apresentado na figura a seguir.
Primeira operação elementar (linha (4)) para o problema da Glass Co. — 2a iteração.
x
1
f
3
x
1
f
3
x
1
f
3
(4)
′
= (4)/3
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
82 of 115 25/09/2024, 12:37
Primeira operação elementar (linha (4)) para o problema da Glass Co. — 2a iteração.
Para a coluna assumir a configuração anterior da coluna , ainda é
preciso realizar operações elementares nas linhas (1) e (2) da tabela
simplex. Assim, para a linha , é preciso que ,
enquanto para a linha devemos fazer ,
conforme indicado na próxima figura.
Dica
Para a linha (3) não é preciso realizar nenhuma operação, uma vez que
os valores para as colunas e já são coincidentes nesta linha.
Operações com a linha pivot para o problema da Glass Co. — 2a iteração.
Atenção!
Verifique, na figura anterior, que não há mais valores negativos na
segunda linha da tabela simplex (1), de modo que não há mais variáveis
para entrar na base. Logo, concluímos que a solução ótima para o
problema da Glass Co. é , e , tal como
apresentado na seção método simplex, quando resolvemos este mesmo
problema por meio do método simplex em sua forma analítica.
x
1
f
3
(2)
′
(2)
′
= (2) − (4)
′
(1)
′
(1)
′
= (1) + 3
∗
(4)
′
x
1
f
3
x
1
= 2 x
2
= 6 z = 36
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
83 of 115 25/09/2024, 12:37
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
A Fitwear S/A é uma confecção de roupas esportivas, tendo uma
linha fitness feminina, na qual produz roupas de ginástica
exclusivas para mulheres, como tops e calças de lycra.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
84 of 115 25/09/2024, 12:37
Cada top de ginástica é vendido por R$80,00 e utiliza R$20,00 de
matéria-prima, como tecido e alinhamentos, e R$32,00 de mão de
obra. Trinta minutos de corte e 15 minutos de costura são
demandados para a confecção de um top de ginástica.
Cada calça de ginástica é vendida por R$120,00 e utiliza R$35,00 de
matéria-prima, como tecido e alinhamentos, e R$40,00 de mão de
obra. Quinze minutos de corte e 30 minutos de costura são
demandados para a confecção de uma calça de ginástica.
A Fitwear só pode contar com 100 horas de corte por semana e 160
horas de costura. A confecção não tem problemas no fornecimento
de matérias-primas, de modo que seu suprimento pode ser
considerado ilimitado, bem como a demanda semanal de seus
produtos.
Considerando que seria possível produzir números não inteiros,
qual deve ser a produção semanal a ser adotada pela Fitwear de
modo a maximizar seus lucros? Considere as seguintes variáveis de
decisão:• = número de tops de ginástica confeccionados a cada
semana
• = número de calças de ginástica confeccionadas a cada
semana
x
1
x
2
A x
1
= 320, x
2
= 160
B x
1
= 200, x
2
= 160
C x
1
= 160, x
2
= 320
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
85 of 115 25/09/2024, 12:37
Parabéns! A alternativa A está correta.
O modelo matemático para este problema é:
Máx 
Sujeito a:
 restrição de horas de corte
 restrição de horas de costura
 restrição de não negatividade das variáveis de
decisão
Em sua forma canônica, temos:
Máx 
Sujeito a:
A solução do problema pela tabela simplex é:
D x
1
= 280, x
2
= 220
E x
1
= 280, x
2
= 120
Z = 28x
1
+ 40x
2
0, 5x
1
+ 0, 25x
2
≤ 100 →
0, 25x
1
+ 0, 5x
2
≤ 160 →
x
1
, x
2
≥ 0 →
Z = 28x
1
+ 40x
2
0, 5x
1
+ 0, 25x
2
+ f
1
= 100
0, 25x
1
+ 0, 5x
2
+ f
2
= 160
x
1
, x
2
≥ 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
86 of 115 25/09/2024, 12:37
A solução do problema pela tabela simplex é:
Solução da Atividade 1 pela tabela simplex.
Questão 2
Utilize o método simplex para a solução desta programação linear:
Máx: 
Sujeito a:
 O valor de z para a solução ótima do problema
apresentado é igual a:
350x
1
+ 300x
2
X
1
+ X
2
= 0
X
2
>= 0
A Zero
B 54.000
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
87 of 115 25/09/2024, 12:37
Parabéns! A alternativa E está correta.
A resposta correta é a letra E, conforme pode ser verificado na
solução obtida pelo método gráfico, apresentada na figura a seguir.
Solução da atividade 2 pela tabela simplex.
C 60.900
D 64.000
E 66.100
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
88 of 115 25/09/2024, 12:37
4 - Solução de problemas de programação linear
Ao �nal deste módulo, você será capaz de aplicar o solver para solução de problemas de
programação linear.
Utilização do solver para solução de
problemas de programação linear
No módulo 1, aprendemos a resolver problemas de programação linear
por meio do método simplex, tanto o analítico quanto o tabular.
Aplicamos essas técnicas em alguns exemplos, de modo a entender a
lógica do algoritmo. Porém, pudemos verificar que são muitos os
cálculos que precisam ser feitos para resolvermos problemas de
programação linear manualmente, e apenas um erro em uma conta nos
levaria a um resultado errado. Contudo, felizmente, existem diversos
softwares de computador que podem ser utilizados para nos auxiliar a
encontrar a solução ótima para problemas de programação matemática,
por exemplo:
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
89 of 115 25/09/2024, 12:37
LINDO
CPLEx
Aimms
GAMS
MathPro
Usando o software de computador adequado, podemos
resolver facilmente quaisquer problemas de
programação linear.
As técnicas para a solução de problemas de programação linear são,
inclusive, desenvolvidas por meio de pacotes de planilhas eletrônicas.
Assim sendo, aprenderemos nesta seção a utilizar o solver do pacote de
planilhas eletrônicas Excel para solução de problemas de programação
linear.
Dica
Os mesmos conceitos e técnicas que apresentaremos a seguir também
podem ser aplicados em outros pacotes de planilhas, dadas as
necessidades de alterações em detalhes de implementação.
Passos para implementar um
problema de programação linear em
planilha
Ragsdale (2009) apresenta cinco passos que devem ser feitos para
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
90 of 115 25/09/2024, 12:37
Ragsdale (2009) apresenta cinco passos que devem ser feitos para
implementar qualquer problema de programação linear em uma
planilha:
 Organize os dados para o modelo (os coeficientes
das restrições, os coeficientes da função objetivo
etc.) na planilha.
 Reserve as células separadas na planilha para
representar cada variável de decisão do modelo
algébrico. Isso é útil na determinação de fórmulas
para a função e restrições do objetivo.
 Crie uma fórmula para cada célula da planilha que
corresponda à função objetivo no modelo algébrico.
 Para cada restrição, crie uma fórmula em uma
célula separada na planilha. Muitas das fórmulas de
restrição têm estrutura semelhante, de modo que,
quando possível, crie fórmulas de restrição que
possam ser copiadas para implementar outras
fórmulas de restrição.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
91 of 115 25/09/2024, 12:37
Instalando o solver
Demonstraremos, neste módulo, como usar o solver do Excel
resolvendo o problema enfrentado pela Fitwear. No entanto, antes de
iniciarmos a resolução do problema, é preciso instalar o solver nos
pacotes de planilhas eletrônicas Excel. Para isso, siga o passo a passo:
Clique em arquivos > opções no Excel, conforme indicado na figura.
Instalando o solver — Passo 1.
O segundo passo é clicar em suplementos na tela que foi aberta.
 Use sombras e cores de fundo e/ou bordas para
identificar as células que representam as variáveis
de decisão, restrições e funções objetivos do
modelo.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
92 of 115 25/09/2024, 12:37
Instalando o solver — Passo 2.
Na tela seguinte, clique no botão ir, em gerenciar suplementos do Excel.
Instalando o solver — Passo 3.
Na próxima tela, clique na opção solver.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
93 of 115 25/09/2024, 12:37
Instalando o solver — Passo 4.
Para finalizar, basta clicar na aba dados para visualizar a opção solver.
Instalando o solver — Passo 5.
Utilizando o solver
Agora que já temos o solver instalado no nosso Excel, vamos iniciar a
resolução do problema da Fitwear visto no módulo 1.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
94 of 115 25/09/2024, 12:37
resolução do problema da Fitwear visto no módulo 1.
Dica
Caso seja necessário, retorne ao módulo anterior e relembre como
desenvolvemos o modelo matemático do problema.
Observe a seguir o modelo matemático, considerando as variáveis de
decisão:
Número de tops de ginástica confeccionados a cada semana.
Número de calças de ginástica confeccionadas a cada semana.
Temos a formulação matemática em sua forma-padrão.
Uma das primeiras etapas para a solução do problema deve ser a
organização dos dados. Vamos começar representando as variáveis de
decisão, como indicado na figura a seguir. Observe que descrevemos as
variáveis de decisão na planilha, bem como os ganhos semanais com a
venda de cada produto ( e ), deixando destacado em amarelo as
x
1
x
2
MáxZ = 28x
1
+ 40x
2
 Sujeito a: 
0, 5x
1
+ 0, 25x
2
≤ 100 →  restrição de horas de corte 
0, 25x → +0, 5x →≤ 160 →  restrição de horas de costura 
x
1
, x
2
≥ 0 →  restrição de não negatividade das variáveis de decisão 
x
1
x
2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
95 of 115 25/09/2024, 12:37
venda de cada produto ( e ), deixando destacado em amarelo as
células variáveis (ou ajustáveis), que reservamos na planilha para
representar as variáveis de decisão do modelo.
Variáveis de decisão.
O próximo passo é criar uma fórmula que represente a função objetivo
de acordo com as variáveis de decisão indicadas na figura. Para isso,
devemos utilizar a função “somarproduto” do Excel, que faz o produto
escalar entre dois vetores.
x
1
x
2
Bases de Otimização com o MSExcel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
96 of 115 25/09/2024, 12:37
Função “somarproduto”.
A figura a seguir ilustra como inserimos a função objetivo na planilha
eletrônica no caso do problema da Fitwear. Observe que fizemos a
função “somarproduto” entre o vetor (28,40), que corresponde aos
coeficientes da função objetivo, e as células que destinamos para
receber o valor das variáveis de decisão. Com isso, teremos que a célula
destacada em amarelo para a função objetivo recebeu a fórmula
.
Função objetivo.
De maneira análoga à que fizemos a representação da função objetivo,
precisamos representar as restrições. Para isso, também vamos utilizar
a função “somarproduto” do Excel. Veja a seguir como inserimos as
duas restrições para o problema da Fitwear na planilha eletrônica.
Observe que fizemos a função “somarproduto” entre os vetores
que indicam os coeficientes das restrições e as células que
28 ∗ x
1
+ 40 ∗ x
2
Restrição de horas de corte 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
97 of 115 25/09/2024, 12:37
que indicam os coeficientes das restrições e as células que
destinamos para receber o valor das variáveis de decisão. Com
isso, teremos que a célula destacada em amarelo na figura
restrição de horas de corte recebeu a fórmula .
Restrição de horas de corte.
Observe que a célula destacada em amarelo na figura restrição
de horas de costura recebeu a fórmula .
0, 5x
1
+ 0, 25x
2
Restrição de horas de costura 
0, 25x
1
+ 0, 5x
2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
98 of 115 25/09/2024, 12:37
Restrição de horas de costura.
Finalmente, terminamos a implementação do
modelo do problema de programação linear da
Fitwear no Excel. Entretanto, ainda precisamos
resolvê-lo.
Para isso, é preciso indicar para o solver o que cada célula da planilha
representa:
A função objetivo
As variáveis de decisão
As restrições
Assim sendo, devemos definir a célula de destino, ou seja, aquela que
representa a função objetivo na caixa de diálogo parâmetros do solver,
como indicado na próxima figura. Observe que a célula E9 contém a
fórmula que representa a função objetivo para o nosso problema, como
havíamos preparado anteriormente. Neste momento, devemos instruir
também o solver para tentar maximizar seu valor, especificando o botão
max.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
99 of 115 25/09/2024, 12:37
Definindo a função objetivo na célula de destino.
O próximo passo consiste em indicar as células que representam as
variáveis de decisão no modelo. Observe, na figura a seguir, que as
células C8 e D8, em nossa planilha, representam as variáveis de decisão
para o modelo. O solver determinará os valores ótimos para essas
células.
Definindo as variáveis de decisão.
A seguir, devemos definir as células de restrição na planilha e as
restrições que se aplicam a essas células.
Atenção!
As células de restrição são aquelas em que implementamos as
fórmulas para cada restrição.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
100 of 115 25/09/2024, 12:37
Para definir as células de restrição, siga os passos:
Clique no botão incluir.
Especificando as células de restrição — passo 1.
Preencha a caixa de diálogo incluir restrições.
Especificando as células de restrição — passo 2.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
101 of 115 25/09/2024, 12:37
Observe que as células E13 e E14 representam as células de restrição
cujos valores devem ser menores ou iguais aos indicados nas células
G13 e G14, respectivamente.
Especificando as células de restrição — passo 3.
Já especificamos as restrições, mas ainda precisamos determinar que
as variáveis de decisão devem ser iguais ou maiores do que zero. Para
isso, basta clicar em tornar variáveis irrestritas não negativas na caixa
de diálogo parâmetros do solver, conforme indicado na figura a seguir.
Enfim, para encontrarmos a solução ótima para o problema, basta clicar
no botão resolver.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
102 of 115 25/09/2024, 12:37
Condições de não negatividade.
A figura a seguir apresenta a tela de saída do Excel com a solução ótima
para o problema da Fitwear.
Solução ótima para o problema da Fitwear.
Observe que deve ser 53,33, recebe 293,333 e o
valor ótimo de é igual a 13.226,67.
x
1
x
2

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
103 of 115 25/09/2024, 12:37
Utilização do solver para a solução de
problemas de programação linear
O vídeo mostra um passo a passo para a resolução de um problema de
programação linear no solver do Excel.

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
104 of 115 25/09/2024, 12:37
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
A fábrica XYZ produz rações para a alimentação de gado. As rações
são elaboradas a partir da mistura de três diferentes tipos de grãos:
1, 2 e 3. Três nutrientes são considerados no produto final: A, B e C.
Sabe-se que o grão do tipo 1 custa R$35,00 por kg. Um quilo de
grão 1 possui 30mg de nutriente A, 10mg de nutriente B e 43mg de
nutriente C. O grão do tipo 2 custa R$23,00 por kg. Ainda, um quilo
do grão 2 possui 28mg do nutriente A, 17mg do nutriente B e 40mg
do nutriente C. O grão do tipo 3 possui apenas 70mg do nutriente
tipo A e um quilo deste tipo de grão custa R$78,00.
A ração para gado deve conter, no mínimo, 1250mg de nutriente A,
380mg do nutriente B e 980mg do nutriente C.
O analista deseja determinar uma composição da ração que
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
105 of 115 25/09/2024, 12:37
minimize os custos de produção, considerando que as
necessidades mínimas dos nutrientes sejam atendidas. Desse
modo, é possível afirmar que a solução ótima para o problema tem
um valor de igual a:
Parabéns! A alternativa B está correta.
Como as rações são elaboradas a partir de três diferentes tipos de
grãos, temos que as variáveis de decisão são:
 = quilos de grão tipo 1 usados na produção de um quilo de ração
 = quilos de grão tipo 2 usados na produção de um quilo de ração
 = quilos de grão tipo 3 usados na produção de um quilo de ração
Como se deseja minimizar o custo de produção e sabe-se o custo
do quilo de cada tipo de grão, temos a seguinte função objetivo:
A 262,84
B 1262,84
C 2262,84
D 3262,84
E 4262,84
x
1
x
2
x
3
M Z 7
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
106 of 115 25/09/2024, 12:37
Logo, podemos afirmar que a resposta certa para o exercício é a
Letra E. Porém, vamos continuar a construção do modelo
matemático para este problema.
A ração deve conter, no mínimo, 1250mg de nutriente A, 380mg do
nutriente B e 980mg do nutriente C. Assim, teremos três restrições
com relação à quantidade dos diferentes tipos de nutrientes. São
elas:
 Nutriente A
 Nutriente B
 Nutriente C
Portanto, temos que o modelo para este problema é:
Sujeito a:
A figura apresenta a tela de saída do Excel com a solução ótima
para o problema. Observe que deve ser 22,79, recebe 20,22 e
 é nulo, sendo o valor ótimo de igual a 1262,84.
Min Z = 35x
1
+ 23x
2
+ 78x
3
30x
1
+ 28x
2
+ 70x
3
≥ 1250 →
10x
1
+ 17x
2
≥ 380 →
43x
1
+ 40x
3
≥ 980 →
Min Z = 35x
1
+ 23x
2
+ 78x
3
30x
1
+ 28x
2
+ 70x
3
≥ 1250
10x
1
+ 17x
2
≥ 380
43x
1
+ 40x
3
≥ 980
x
1
, x
2
, x
3
, x
4
≥0
x
1
x
2
x
3
z
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
107 of 115 25/09/2024, 12:37
Solução ótima para o problema da Atividade 1.
Questão 2
Uma mãe está muito preocupada com a alimentação de seus filhos.
Ela deseja que as crianças tenham uma alimentação equilibrada e,
por isso, consultou uma nutricionista que lhe recomendou que eles
comam, no mínimo, 10mg de vitamina A, 70mg de vitamina C e
250mg de vitamina D por dia.
Porém, além de se preocupar com a qualidade da alimentação, essa
mãe também está preocupada com os custos. Ela deseja oferecer
aos seus filhos essa dieta equilibrada, porém ao menor custo
possível. Por isso, ela fez uma pesquisa e descobriu as
informações nutricionais para diferentes tipos de alimento,
conforme apresentado na tabela.
Vitamina Leite (l) Carne (kg)
A 2 2
C 50 20
D 80 70
Informações nutricionais em mg
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
108 of 115 25/09/2024, 12:37
A mãe também foi ao supermercado e verificou que um litro de leite
custa R$2,00, um quilo de carne custa R$20,00, um quilo de peixe
custa R$25,00 e para preparar 100g de salada ela gastaria R$3,00.
Desse modo, é possível afirmar que a solução ótima para o
problema tem um valor de z igual a:
Parabéns! A alternativa E está correta.
A variável de decisão deve ser , sendo x a quantidade de alimento
do tipo “i” a ser consumida por dia. Logo, temos:
 = litros de leite a serem consumidos por dia pelas crianças
 = quilos de carne a serem consumidos por dia pelas crianças
 = quilos de peixe a serem consumidos por dia pelas crianças
 = 100g de salada a serem consumidos por dia pelas crianças
A 2,46
B 3,46
C 4,46
D 5,46
E 6,46
x
i
x
1
x
2
x
3
x
4
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
109 of 115 25/09/2024, 12:37
O modelo para este problema é:
Sujeito a:
A figura apresenta a tela de saída do Excel com a solução ótima
para o problema. Observe que deve ser 2,91 litros de leite, e
 são nulos, enquanto é igual a 208,33g de salada, sendo o
valor ótimo de igual a 6,46.
Solução ótima para o problema da Atividade 2.
Considerações �nais
Min Z = 2x
1
+ 20x
2
+ 25x
3
+ 3x
4
2x
1
+ 2x
2
+ 10x
3
+ 20x
4
≥ 10
50x
1
+ 20x
2
+ 10x
3
+ 30x
4
≥ 70
80x
1
+ 70x
2
+ 10x
3
+ 80x
4
≥ 250
x
1
, x
2
, x
3
, x
4
≥ 0
x
1
x
2
x
3
x
4
z
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
110 of 115 25/09/2024, 12:37
Neste conteúdo, visitamos os principais conceitos da Pesquisa
Operacional, abordando a sua origem e evolução como campo do
conhecimento. Verificamos a sua importância e a aplicabilidade de suas
técnicas e ferramentas no apoio ao processo de tomada de decisão em
diferentes campos de atuação e setores.
Trabalhamos o conceito de modelo e vimos como um modelo nos traz
benefícios na análise de decisão. Nesse sentido, um modelo é uma
simplificação do problema a ser analisado, de modo que nos permite
avaliar diferentes cenários em menor tempo e com menos recursos.
Para que possamos de fato usufruir desses benefícios, é fundamental
que o modelo e a qualidade dos dados de entrada sejam fidedignos.
Nesse contexto, foram apresentados os principais passos a serem
seguidos para o desenvolvimento de um modelo matemático em
estudos de Pesquisa Operacional.
Uma das técnicas mais difundidas de Pesquisa
Operacional é a Programação Linear, cujos conceitos
também foram apresentados. Aprendemos sobre os
principais elementos de um modelo de Programação
Linear e vimos como construir esse tipo de modelo e
encontrar sua solução por meio do Método Gráfico.
Todo esse conhecimento foi apresentado por meio do
desenvolvimento do modelo matemático para o
exemplo da Fitwear!
A Pesquisa Operacional pode nos auxiliar no apoio a processos de
decisão, em especial, para problemas complexos. Estudamos o método
simplex, tanto pelo modo analítico quanto pelo tabular, por meio do qual
aprendemos a resolver problemas de Programação Linear, encontrando
a solução ótima para esse tipo de problema. Contudo, resolvê-los
manualmente é muito trabalhoso, envolvendo um grande número de
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
111 of 115 25/09/2024, 12:37
cálculos. Um simples erro em uma das contas requeridas implica
encontrar uma solução equivocada para o problema. Por isso, é muito
importante conhecer softwares computacionais que permitem a
solução de problemas de programação matemática.
São muitos os softwares computacionais dedicados à solução de
problemas de programação matemática, como o CPLEx, o GAMS, o
LINDO, o LINGO etc. No entanto, problemas de Programação Linear
podem ser resolvidos pelo solver de pacotes de planilhas eletrônicas.
Por fim, aprendemos a solucionar problemas de Programação Linear por
meio do solver do Excel. Isso certamente facilitará a aplicação da
Pesquisa Operacional à solução de problemas reais.
Podcast
Agora, a(o) especialista finaliza fazendo um resumo dos conteúdos
estudados.

Explore +
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
112 of 115 25/09/2024, 12:37
Assista ao vídeo O que é Pesquisa Operacional?, da Sociedade Britânica
de Pesquisa Operacional (OR Society), disponível no YouTube, para
entender melhor o que é a Pesquisa Operacional, o desenvolvimento
desse campo do conhecimento e suas possibilidades de aplicação.
Leia os capítulos 1 e 2 do livro Pesquisa operacional na tomada de
decisões, de Gerson Lachtermacher, publicado em 2016.
Leia os capítulos 1, 2 e 3 do livro Modelagem e análise de decisão, de
Cliff T. Ragsdale, publicado em 2009.
Conheça métodos preparatórios (utilizados antes do emprego do
simplex) para resolver problemas diferentes do padrão de maximização
com restrições do tipo menor ou igual no capítulo 4 do livro Operations
research: applications and algorithms (Vol. 3), de Winston e Goldberg
(2004).
Referências
ARENALES, M. et al. Pesquisa operacional. Rio de Janeiro: Elsevier,
2007.
FOGLIATO, F. Pesquisa operacional. Porto Alegre, 2006. (Notas de aula).
GOLDBARG, M. C.; LUNA, H. P. Otimização combinatória e programação
linear. 2. ed. São Paulo: Campus, 2005.
LACHTERMACHER, G. Pesquisa operacional na tomada de decisões. Rio
de Janeiro: Campus, 2009.
RAGSDALE, C. T. Modelagem e análise de decisão. São Paulo: Cengage
Learning, 2014.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
113 of 115 25/09/2024, 12:37
RODRIGUES, L. H.; AHLERT, F.; LACERDA, D. P.; CAMARGO, L. F. R.; LIMA,
P. Pesquisa operacional: programação linear passo a passo: do
entendimento do problema à interpretação da solução. São Leopoldo:
Unisinos, 2014.
COUGO, P. Modelagem conceitual e projeto de banco de dados. Rio de
Janeiro: Elsevier Brasil, 2013.
FÁVERO, L. P.; BELFIORE, P. Pesquisa operacional para cursos de
administração. Rio de Janeiro: Elsevier Brasil, 2012.
OLIVEIRA, F. Métodos quantitativos. Rio de Janeiro, 2016. (Notas de
aula).
PRADO, D. Programação linear. Vol. 1. São Paulo: Falconi, 2016.
SOBRAPO – SOCIEDADE BRASILEIRA DE PESQUISA OPERACIONAL. O
que é Pesquisa Operacional? Disponível em meio eletrônico. Consultado
em: 04 fev. 2021.
WINSTON, W. L.; GOLDBERG, J. B. Operations research: applications and
algorithms. Vol. 3. Belmont, Califórnia: Thomson/Brooks/Cole, 2004.
Material para download
Clique no botão abaixo para fazer o download do
conteúdo completo em formato PDF.
Download material
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
114 of 115 25/09/2024, 12:37
javascript:CriaPDF()
javascript:CriaPDF()javascript:CriaPDF()
javascript:CriaPDF()
javascript:CriaPDF()
javascript:CriaPDF()
O que você achou do conteúdo?
Relatar problema
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
115 of 115 25/09/2024, 12:37o interesse das indústrias na utilização das
técnicas desenvolvidas na área militar para auxiliar no planejamento e
controle da produção.
Atenção
A disseminação da Pesquisa Operacional na área de planejamento e
controle, no entanto, só foi possível devido aos avanços que ocorriam
no campo da informática. Tais avanços permitiram o advento de
microcomputadores, bem como o aumento da velocidade e de
capacidade de processamento computacional.
Aplicação da PO na análise de
decisão
Empresas dos mais diversos setores, atualmente, empregam técnicas
de Pesquisa Operacional com intuito de tornar seu processo de tomada
de decisão mais eficiente e assertivo. Além do meio militar, a PO é
aplicada em indústrias de manufaturas, empresas de transporte,
empresas de construção, de telecomunicações, bancos, em assistência
médica e até no serviço público.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
9 of 115 25/09/2024, 12:37
médica e até no serviço público.
Veja algumas empresas que utilizam a PO:
A Petrobrás é uma empresa petroleira que possui diversos
especialistas em pesquisa operacional em seu quadro de
funcionários. Esses especialistas utilizam modelos matemáticos
para analisar e criar cenários para diferentes problemas de
natureza complexa.
Entre os problemas resolvidos com auxílio da PO, podemos citar
o dimensionamento da frota e a roteirização de helicópteros para
o transporte de pessoal para as plataformas offshore, a previsão
de reservas de petróleo, a programação de operações em poços
de petróleo, a alocação de equipes em diversas atividades ou o
gerenciamento da distribuição de derivados de petróleo.
A MRS Logística – operador ferroviário que atua na Malha
Regional Sudeste da antiga Rede Ferroviária Federal S.A. –
também é um exemplo de empresa brasileira que adota
diferentes técnicas de pesquisa operacional para apoiar seus
diferentes processos de tomada de decisão.
A MRS possui especialistas em diversas técnicas de PO que
utilizam seu conhecimento para apoiar a solução de problemas
complexos. Entre esses problemas, estão a alocação eficiente da
tripulação nos trens, a alocação de locomotivas e vagões nas
diferentes composições de trens, a programação de manutenção
preventiva de seus ativos, ou o processo de planejamento e
Petrobrás 
MRS Logística 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
10 of 115 25/09/2024, 12:37
preventiva de seus ativos, ou o processo de planejamento e
programação do transporte ferroviário de carga.
Existem empresas de consultoria especializadas em Pesquisa
Operacional, que fornecem seus serviços para auxiliar outras
organizações na solução em seus processos de tomada de
decisão. Tais empresas utilizam conceitos das diversas áreas da
PO – como programação matemática, simulação ou Inteligência
Computacional – para modelar os problemas de seus clientes.
As empresas conseguem, com isso, rodar diversas análises,
fornecendo dados aos seus clientes sobre como o evento em
estudo se comportaria em diversos cenários, sujeito a alterações
dos parâmetros.
Problemas do cotidiano
É evidente a importância da Pesquisa Operacional na análise de
decisão, em especial no ambiente gerencial. No entanto, as técnicas de
pesquisa operacional também podem auxiliar a tomar decisões no seu
dia a dia.
Exemplo
Vamos supor que você queira comprar seu primeiro carro. Para isso,
tem economizado a remuneração que recebe no estágio e deseja
selecionar investimentos para obter o melhor rendimento possível.
Nesse caso, o planejamento financeiro pode ser modelado por um
modelo matemático que auxiliará a maximizar os seus rendimentos.
Consultoria especializada 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
11 of 115 25/09/2024, 12:37
O planejamento financeiro é apenas um exemplo de como você pode
aplicar conceitos de PO em sua vida cotidiana.
Ao aplicar conceitos de PO para a solução de um problema,
desenvolvemos um modelo matemático para representar o fenômeno
estudado. Dessa forma, conseguimos analisar diversos cenários e ter
estimativas baseadas em uma análise quantitativa.
As decisões, portanto, não serão tomadas apenas com base em
opiniões, intuições ou experiências passadas de outras pessoas ou
empresas. Ao modelar um problema, temos um processo decisório
mais criterioso e com menos incertezas.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
12 of 115 25/09/2024, 12:37
Modelo
"Um modelo é uma representação
abstrata e simplificada de um
sistema real, com o qual se pode
explicar, reproduzir, simular ou testar
seu comportamento, no todo ou em
partes".
COUGO, 1997
Um mapa é um modelo, assim como uma maquete que o arquiteto
utiliza para que seus clientes consigam ter noção da visão espacial, em
3D, do projeto desenvolvido. Uma formulação matemática usada para
expressar um fenômeno físico também é um modelo.
É importante ter em mente que os modelos são
versões simplificadas do objeto ou problema de
decisão que representam.
Entretanto, para que seja válido, o modelo precisa representar, de forma
precisa, as características relevantes do objeto ou problema de decisão
estudado. Afinal, espera-se que o modelo melhore os processos de
tomada de decisão ao ser implementado.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
13 of 115 25/09/2024, 12:37
tomada de decisão ao ser implementado.
Atenção
A modelagem permite explicitar objetivos, bem como a possibilidade de
ganhar conhecimento e entendimento sobre o problema investigado.
Além disso, a implantação de um modelo quantifica as decisões,
permitindo a análise de cenários que seriam impossíveis de serem
analisados na realidade. Outra vantagem da construção de modelos é a
economia de recursos e de tempo.
Na PO, modelamos os problemas matematicamente e, a partir do
modelo obtido, usamos algoritmos para encontrar soluções para
diferentes cenários do problema a ser analisado. Podemos utilizar
diferentes tipos de modelos, como veremos a seguir nesta aula.
Os diferentes tipos de modelo nos levam a adotar diferentes técnicas de
PO, como Programação Linear, Programação Não Linear, Teoria das
Filas, Simulação, Inteligência Computacional e Teoria dos Jogos. Nesta
aula, vamos conhecer os modelos de Programação Linear.
Veja o posicionamento da Associação Brasileira de Pesquisa
Operacional (ABEPRO) sobre Disciplinas da pesquisa Operacional:
Disciplinas da Pesquisa Operacional
A Associação Brasileira de Pesquisa Operacional (ABEPRO) é a
instituição representativa de docentes, discentes e profissionais
de Engenharia de Produção no País. Em 2017, a ABEPRO
organizou as áreas do conhecimento relacionadas à Engenharia
de Produção, tanto na graduação quanto na Pós-Graduação, na
pesquisa e nas atividades profissionais.
Disciplinas da pesquisa operacional 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
14 of 115 25/09/2024, 12:37
A Pesquisa Operacional, por ser uma importante área do
conhecimento para a Engenharia de Produção, foi incluída na
organização da ABEPRO.
De acordo com o documento da ABEPRO, a PO envolve
resolução de problemas reais, envolvendo situações de tomada
de decisão, por meio de modelos matemáticos processados
computacionalmente. Aplica conceitos e métodos de outras
disciplinas científicas na concepção, no planejamento ou na
operação de sistemas para atingir seus objetivos. Procura,
assim, introduzir elementos de objetividade e racionalidade nos
processos de tomada de decisão, sem descuidar dos elementos
subjetivos e de enquadramento organizacional que caracterizam
os problemas.
O documento ainda organiza as principais disciplinas de PO em:
1.Modelagem, Simulação e Otimização
2. Programação Matemática
3. Processos Decisórios
4. Processos Estocásticos
5. Teoria dos Jogos
6. Análise de Demanda
7. Inteligência Computacional
O foco deste tema é a Programação Matemática.
Modelos matemáticos
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
15 of 115 25/09/2024, 12:37
Ragsdale (2009) define um modelo matemático como:
Conjunto de relacionamentos matemáticos e
suposições lógicas, geralmente implementados
em um computador, como representação de
algum problema ou fenômeno de decisão do
mundo real.
O modelo matemático usa a lógica e a formulação matemática para
obter uma representação do problema ou do evento a ser analisado e, a
partir de então, analisar, desenvolver cenários e obter soluções para a
situação modelada.
O uso de modelos matemáticos é mais barato do que
replicar a estrutura real, além de permitir testar todas
as possíveis soluções para diferentes cenários
(RODRIGUES et al., 2014).
Composição
Um modelo matemático em pesquisa operacional é composto,
basicamente, por variáveis de decisão, funções objetivo e restrições. O
modelo de otimização busca os valores das variáveis de decisão que
otimizam – maximizam ou minimizam – a função objetivo, ao mesmo
tempo em que atendem às restrições às quais o problema é submetido.
Vejamos alguns exemplos:
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
16 of 115 25/09/2024, 12:37
Função objetivo - maximizar ou minimizar
Maximizar lucro de uma empresa
Sujeito a restrições
Disponibilidade de matérias-primas, de mão de obra etc.
Por exemplo, para aplicar o dinheiro que você conseguiu economizar
com a remuneração de seu estágio, você vai ao banco verificar as
diferentes opções de investimento disponíveis.
Nesse problema, você deseja maximizar seu rendimento – função
objetivo. Os recursos que você aplicará em cada opção de investimento
são as variáveis de decisão. Além disso, você está sujeito às restrições
relativas ao total de recurso disponíveis e às exigências do banco para
que sejam realizadas as diferentes aplicações.
Classi�cação
Os modelos matemáticos de otimização, segundo Winston (2004),
podem ser classificados em:
As variáveis de decisões nos modelos estáticos não envolvem
sequências de decisões em múltiplos períodos de tempo, ao
contrário do que ocorre em modelos dinâmicos.
Em outras palavras, em um modelo estático, analisamos o
problema em um único intervalo de tempo. Já em um modelo
Modelos estáticos ou dinâmicos 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
17 of 115 25/09/2024, 12:37
problema em um único intervalo de tempo. Já em um modelo
dinâmico, analisamos o problema ao longo do tempo.
Quando as funções objetivo e restrições envolvem apenas
equações lineares, temos um modelo linear. Quando a função
objetivo ou alguma restrição é função polinomial ou de qualquer
outro tipo, temos modelos não lineares.
A solução de modelos não lineares é mais complexa do que a de
modelos lineares.
Quando todas as variáveis de decisão estão livres para assumir
valores fracionais, temos um modelo não inteiro. No entanto, se
uma ou mais variáveis de decisão adotadas no modelo
matemático necessitam ser inteiras, temos um modelo inteiro.
Os componentes são definidos a priori, ou seja, sem
aleatoriedade. No entanto, quando os elementos apresentam
probabilidade de ocorrência – ou seja, há aleatoriedade –, temos
um modelo estocástico.
Neste conteúdo, abordaremos apenas os modelos determinísticos.
Modelos lineares ou não lineares 
Modelos inteiros ou não inteiros 
Modelos determinísticos ou estocásticos 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
18 of 115 25/09/2024, 12:37
Neste conteúdo, abordaremos apenas os modelos determinísticos.
Fases de um estudo de pesquisa
operacional
Winston (2004) propõe um procedimento composto por sete passos
para o desenvolvimento de modelos matemáticos em estudos de
pesquisa operacional, conforme apresentado na imagem abaixo:
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
19 of 115 25/09/2024, 12:37
Procedimento para desenvolvimento de modelos matemáticos em estudos de pesquisa
operacional.
O passo inicial do procedimento proposto por Winston (2004)
consiste em entender e definir o problema a ser analisado. Para
tanto, é preciso identificar os objetivos e processos
organizacionais que precisam ser estudados antes de resolver o
problema. De tal forma, é fundamental ouvir aquele que lida com
o problema.
A comunicação com o cliente, nesse momento, é indispensável
para entender a situação real a ser modelada. No exemplo da
seleção dos investimentos a serem realizados com a
remuneração de seu estágio, o problema consiste em maximizar
os rendimentos de suas aplicações financeiras.
Formulação do problema 
Observação do sistema 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
20 of 115 25/09/2024, 12:37
É necessário, em seguida, observar o sistema para descobrir o
que deve ser determinado – as variáveis do problema – e aquilo
que está disponível – os dados do problema. Nessa etapa,
devem ser coletados os dados necessários para estimar os
valores das variáveis e os parâmetros que afetam o problema
analisado. Tais estimativas são adotadas no desenvolvimento do
modelo (passo 3) e em sua análise (passo 4).
É nesse momento que coletamos os dados para nossos
parâmetros e as variáveis de entrada. É importante ressaltar a
importância do processo de coleta de dados, pois a qualidade
dos dados de entrada é fundamental para a qualidade dos
resultados obtidos pelo modelo.
No exemplo da seleção dos investimentos a serem realizados
com a remuneração de seu estágio, é preciso que você conheça
as taxas de administração do banco, o rendimento de cada
opção de investimento e o valor mínimo que deve ser aplicado
em cada opção.
O modelo matemático é desenvolvido nessa etapa, com a
identificação das variáveis de decisão, sua função objetivo e
suas restrições. Ao longo desta aula, desenvolveremos a
formulação de vários modelos matemáticos para a solução de
problemas.
Observação do sistema 
Formulação do modelo matemático 
Verificação do modelo matemático e uso para predição 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
21 of 115 25/09/2024, 12:37
Após o desenvolvimento do modelo matemático, é necessário se
certificar de que o modelo é válido e representa a realidade de
forma fidedigna. Deve-se ter em mente que não basta aplicar
cegamente o modelo desenvolvido.
Caso ocorram modificações na situação real que está sendo
analisada, é necessário que tais modificações possam ser
incorporadas no modelo. No exemplo da seleção dos
investimentos, novas opções de investimento poderiam ser
oferecidas pelo banco, e você deve poder incorporá-las em sua
análise.
Este é o momento de selecionar a alternativa – ou as
alternativas, afinal, podemos ter mais de uma solução ótima –
que otimiza a função objetivo do problema analisado.
As melhores alternativas e os diferentes cenários devem ser
apresentados ao decisor, para que ele tenha todas as
informações necessárias para uma tomada de decisão mais
assertiva. Nesse momento, pode ser que o decisor não esteja
contente com os resultados apresentados.
Isso pode ocorrer em função de alguma definição incorreta do
problema analisado, devido a problemas na etapa de formulação
do problema – etapa 1 –, ou mesmo à falha por parte do
modelador em envolver o decisor no projeto desde o início.
Seleção da melhor alternativa 
Apresentação dos resultados e conclusão 
Bases de Otimização com oMS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
22 of 115 25/09/2024, 12:37
modelador em envolver o decisor no projeto desde o início.
Desse modo, pode ser necessário retornar para os passos 1, 2 ou
3.
O sistema deve ser constantemente monitorado, e qualquer
alteração deve ser incorporada ao modelo, de modo que as
recomendações permitam que a organização atinja seus
objetivos.
Implantação e análise das recomendações 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
23 of 115 25/09/2024, 12:37
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
A modelagem matemática consiste na arte (ou tentativa) de
descrever um fenômeno pela representação de sistemas, a fim de
prever o comportamento deles ou propor soluções não previstas.
Com relação ao processo de modelagem matemática em Pesquisa
Operacional, assinale a alternativa INCORRETA.
Fonte: questão adaptada do Concurso da Fundação o de
Desenvolvimento da Pesquisa – UFMG (FUNDEP) para Indústrias
Nucleares do Brasil (INB) 2018 para o cargo de Engenheiro de
Produção.
A
A qualidade da solução do modelo depende da
qualidade dos dados de entrada no modelo.
Modelos matemáticos são objetos abstratos que
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
24 of 115 25/09/2024, 12:37
Parabéns! A alternativa E está correta.
Basta que apenas uma variável de decisão seja inteira para termos
um modelo inteiro. Todas as variáveis de decisão precisam estar
livres para assumir valores fracionais para o modelo ser não inteiro.
Questão 2
A qualidade da solução de um modelo matemático depende da
B
Modelos matemáticos são objetos abstratos que
procuram representar as principais características
de um objeto real.
C
Modelos matemáticos podem ser classificados
como estáticos ou dinâmicos em função de como a
variação do tempo é considerada no processo de
modelagem.
D
Uma das vantagens relacionadas à modelagem
matemática é a possibilidade testar todas as
possíveis soluções para diferentes cenários,
geralmente, a um custo reduzido e em menor
intervalo de tempo.
E
Todas as variáveis de decisão devem ser inteiras
para que um modelo matemático seja considerado
inteiro.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
25 of 115 25/09/2024, 12:37
qualidade dos dados de entrada no modelo. Para o
desenvolvimento de modelos matemáticos em estudos de
Pesquisa Operacional, o processo de coleta de dados ocorre no
seguinte passo:
Parabéns! A alternativa B está correta.
Após a formulação do problema, os dados necessários devem ser
coletados, na fase de observação do sistema, para que sejam
estimados os valores das variáveis e os parâmetros a serem
adotados na modelagem do problema analisado. Tais estimativas
são adotadas no desenvolvimento do modelo (passo 3) e em sua
análise (passo 4).
A Formulação do problema
B Observação do sistema
C Formulação do modelo matemático
D
Verificação do modelo matemático e uso para
predição
E Seleção da melhor alternativa
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
26 of 115 25/09/2024, 12:37
2 - Modelo de programação linear
Ao �nal deste módulo, você será capaz de descrever as principais características e
propriedades de um modelo de Programação Linear.
Programação linear
A Programação Matemática – geralmente chamada de otimização –,
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
27 of 115 25/09/2024, 12:37
pode ser definida como:
Um campo da ciência de
gerenciamento que encontra a
maneira ideal ou mais eficiente de
usar recursos limitados para atingir
os objetivos de um indivíduo ou de
uma empresa.
RASGADALE, 2009
A Programação Linear, por sua vez, é uma das técnicas mais difundidas
de otimização, e sua aplicação é indicada para a solução de problemas
de otimização que podem ser modelados por meio de equações
lineares.
Saiba mais
A Programação Linear vem sendo aplicada em problemas de indústrias
de diferentes setores, como bancos, petroleiras, empresas de educação
ou em operadores de transportes. Empresas como a Fedex e a Amazon,
por exemplo, utilizam essas técnicas para programar as rotas e
determinar o caminho mínimo na gestão de suas cadeias de
distribuição.
No processo de modelagem, é preciso entender as características do
problema a fim de traduzi-las para uma linguagem matemática. No caso
específico da Programação Linear, essa “tradução” ocorre por meio do
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
28 of 115 25/09/2024, 12:37
específico da Programação Linear, essa “tradução” ocorre por meio do
desenvolvimento de uma série de equações lineares, que representam
as características do problema analisado.
Atenção
A Programação Linear, em suma, é uma técnica de solução de
problemas que visa determinar o máximo ou o mínimo de uma função
linear cujas variáveis estão sujeitas a um conjunto de restrições
representadas por um sistema de equações ou inequações lineares.
Características
As principais características de problemas de Programação Linear são:
1. Todas as equações são da forma linear, ou seja:
2. Há sempre um objetivo a ser otimizado – maximizado ou
minimizado. Isso significa que há sempre a busca pela melhor
solução entre várias alternativas. Apenas um objetivo pode ser
otimizado por vez, sendo representado pela função objetivo.
3. No problema, há fatores controláveis que serão analisados,
verificando-se os valores desses fatores que levam ao melhor
resultado para otimizar o objetivo. Tais fatores controláveis são as
variáveis de decisão (x1, x2, ..., xm). A função objetivo é escrita em
termos das variáveis de decisão.
4. No problema, há fatores não controláveis que influenciam os
resultados encontrados para as variáveis de decisão. Esses fatores
não controláveis são os parâmetros (a1, a2, ..., am).
a
1
x
1
+ a
2
x
2
+ … + a
m
x
m
= a
n
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
29 of 115 25/09/2024, 12:37
Elementos
Um modelo de Programação Linear apresenta elementos principais – as
variáveis de decisão, os parâmetros, a função objetivo e o conjunto de
restrição. A seguir, vejamos cada um deles.
Variáveis de decisão
São os fatores controláveis do problema a ser analisado. Trata-se,
portanto, das incógnitas a serem definidas na solução do problema de
otimização. Podemos citar como exemplo a quantidade de um produto
a ser transportado da origem i para o destino j, xij, sendo x a quantidade
do produto a ser transportado de i para j.
Parâmetros
São os fatores não controláveis do problema a ser analisado, ou seja, os
dados de entrada que devem ser coletados antes da etapa de
modelagem do problema. Os parâmetros influenciam diretamente os
valores obtidos para a solução ótima do problema de otimização.
Como exemplo, podemos citar o custo de transportar uma unidade de
um produto por quilômetro, cij. Nesse caso, c corresponde ao custo por
quilômetro percorrido no transporte de um determinado produto de i
para j – R$/km.
Função objetivo
É a expressão matemática do objetivo a ser maximizado ou minimizado
na situação analisada. Por exemplo, pode-se desejar minimizar o custo
total do transporte de um produto de n origens i para m possíveis
destinos j. Dessa forma, a função objetivo seria Min Custo=
∑
n
i=1
∑
m
j=1
c
ij
x
ij
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
30 of 115 25/09/2024, 12:37
Restrições
É um conjunto de equações lineares que traduzem o limite físico à
solução do problema, ou seja, são os limitantesdos valores das
variáveis de decisão. Por exemplo, a quantidade total de um produto que
pode ser transportado da origem i para o destino j não pode ser infinita.
Esse total é limitado pela disponibilidade de produtos na origem i. Desse
modo, temos que , sendo Si a disponibilidade de
produto na origem i
Representação
Podemos representar um modelo de Programação Linear da seguinte
forma:
Otimizar: 
Onde as funções são lineares.
Passo a passo para a construção de
um modelo de programação linear
∑
m
j=1
x
ij
≤ Si,
¯
∨i
z = f(x
1
, x
2
, … , x
n
)
 sujeito a  : g
1
(x
1
, x
2
, … , x
n
)
g
2
(x
1
, x
2
, … , x
n
)
… … … … … …
g
m
(x
1
, x
2
, … , x
n
)
⎫
⎬
⎭
 Os valores das variáveis de decisão 
 devem satisfazer um 
 conjunto de restrições. 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
31 of 115 25/09/2024, 12:37
um modelo de programação linear
Uma vez compreendidas as principais características e os principais
elementos de problemas de Programação Linear, podemos passar para
a construção de modelos matemáticos de Programação Linear.
No processo de modelagem, devemos transformar a
linguagem do problema em uma linguagem
matemática. Para isso, devemos começar definindo as
variáveis de decisão e, posteriormente, a função
objetivo e as restrições.
Sugerimos que seja seguida uma sequência de três passos para a
modelagem de um problema de Programação Linear, conforme
apresentado na imagem a seguir:
Procedimento para desenvolvimento de modelos de Programação Linear.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
32 of 115 25/09/2024, 12:37
Procedimento para desenvolvimento de modelos de Programação Linear.
O passo inicial do procedimento proposto consiste em identificar
as variáveis desconhecidas a serem determinadas – variáveis de
decisão.
Nessa etapa, deve-se identificar o objetivo a ser atingido e
representá-lo como uma função linear das variáveis de decisão.
Conforme Rodrigues et al. (2014) orientam, essa etapa é
explicitada no enunciado do problema, bastando uma leitura
atenta do texto.
Deve-se prestar especial atenção a alguns sinalizadores, como:
• Deseja-se minimizar o custo total de transporte –
minimização.
• Deseja-se maximizar o lucro da empresa. - maximização.
Nessa etapa, devem ser listadas todas as restrições do
problema, sendo expressas como equações (=) ou inequações
lineares (>,para o
problema de Programação Linear do caso da Fitwear são positivos, e
este é um problema de maximização. Desse modo, à medida que x1 e x2
crescem, o valor da função objetivo aumenta. No entanto, x1 e x2 não
podem crescem indefinidamente, pois existem as restrições.
Comentário
No caso do problema da Fitwear, foram consideradas ilimitadas a
demanda por seus produtos e a oferta de matéria-prima, de modo que
não entram como restrições no modelo matemático.
Existem, no entanto, duas restrições relacionadas ao tempo disponível
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
38 of 115 25/09/2024, 12:37
Existem, no entanto, duas restrições relacionadas ao tempo disponível
para corte e ao tempo disponível para a costura.
Essas restrições devem ser definidas em termos das variáveis de
decisão x1 e x2. Com isso, temos:
Cada top de ginástica requer 30 minutos de corte, e cada calça
de ginástica requer 15 minutos de corte para sua confecção.
Além disso, a Fitwear só pode contar com 100 horas de corte por
semana.
(total de horas de corte/semana) = (0,5x1 + 0,25x2)
Logo, a restrição 1 é dada por: 0,5x1 + 0,25x2 ≤ 100.
Cada top de ginástica requer 15 minutos de costura, e cada calça
de ginástica requer 30 minutos de costura para sua confecção.
Além disso, a Fitwear só pode contar com 160 horas de corte por
semana.
(total de horas de costura/semana) = (horas de costura/top) *
(tops produzidos/semana) + (horas de costura/calça) * (calças
produzidas/semana)
(total de horas de corte/semana) = (0,25x1 + 0,5x2)
Restrição 1: 100 horas de corte por semana. 
Restrição 2: 160 horas de costura por semana. 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
39 of 115 25/09/2024, 12:37
Logo, a restrição 2 é dada por: 0,25x1 + 0,5x2 ≤ 160.
Há ainda a restrição de não negatividade das variáveis de
decisão, uma vez que não se pode produzir um número negativo
de calças e tops de ginástica.
Logo, a restrição 3 é dada por: x1, x2 ≥ 0.
Após seguirmos os passos indicados para a construção de um modelo
de Programação Linear, temos a formulação matemática para o
problema da Fitwear S/A, conforme apresentado a seguir:
Devemos considerar que o modelo está sujeito a:
0,5x1 + 0,25x2 ≤ 100 � restrição de horas de corte
0,25x1 + 0,5x2 ≤ 160 � restrição de horas de costura
x1, x2 ≥ 0 � restrição de não negatividade das variáveis de decisão
Restrição 3: restrição de não negatividade das variáveis de
decisão. 
MáxZ = 28x
1
+ 40x
2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
40 of 115 25/09/2024, 12:37
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
Questão 1
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
41 of 115 25/09/2024, 12:37
Entre os principais elementos de um modelo de programação linear,
os fatores não controláveis do problema a ser analisado, ou seja, os
dados de entrada que devem ser coletados previamente a etapa de
modelagem do problema, são denominados:
Parabéns! A alternativa C está correta.
Os principais elementos de um modelo de programação linear são
as variáveis de decisão, os parâmetros, a função objetivo e o
conjunto de restrição.
As variáveis de decisão são os fatores controláveis do problema a
ser analisado, ou seja, são as incógnitas a serem definidas na
solução do problema de otimização. Os parâmetros são os fatores
não controláveis do problema a ser analisado, ou seja, são os dados
de entrada que devem ser coletados previamente à etapa de
modelagem do problema.
A Variáveis de decisão
B Variáveis condicionantes
C Parâmetros
D Função objetivo
E Restrições
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
42 of 115 25/09/2024, 12:37
É importante ressaltar que os parâmetros influenciam diretamente
os valores obtidos para a solução ótima do problema de
otimização.
Questão 2
Um sapateiro conserta 3 sapatos por hora, se somente consertar
sapatos. Para fazer um par de sapatos novos, o sapateiro leva 2
horas, se fizer somente sapatos. Ele gasta 4 unidades de couro para
fabricar um par de sapatos. Para consertar uma unidade de sapato,
ele gasta uma unidade de couro.
Sabe-se que o total disponível de couro é de 12 unidades e que o
sapateiro trabalha 10 horas por dia. O lucro unitário por par de
sapatos é de 8 unidades monetárias e o do conserto de uma
unidade de sapato é de 2 unidades monetárias. O sapateiro deseja
planejar seu sistema de produção diário de modo a maximizar seu
lucro por hora.
Pedido 1 – A função objetivo do problema é:
A
Max Z = x1 + 2x2, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
B
Max Z = 2x1 + 8x2, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
C
Max Z = 2x1 + 8x2, sendo x1 a unidade de sapato
fabricada e x2 a unidade de sapato consertada.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
43 of 115 25/09/2024, 12:37
Parabéns! A alternativa D está correta.
Para modelar o problema, o primeiro passo é definir as variáveis de
decisão, que, no caso, são:
• x1: unidade de sapato consertada.
• x2: unidade de sapato fabricada.
O lucro por unidade de sapato fabricada é de 4,00 unidades
monetárias (8,00 pelo par). O lucro por unidade de sapato
consertado é de 2,00 unidades monetárias. Logo, a função objetivo
é: Max Z = 2x1 + 4x2.
Questão 3
Pedido 2 – A restrição em referente à disponibilidade de couro é:
fabricada e x2 a unidade de sapato consertada.
D
Max Z = 2x1 + 4x2, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
E
Max Z = 2x1 + 4x2, sendo x1 a unidade de sapato
fabricada e x2 a unidade de sapato consertada.
A
x1 + 2x2 ≤ 12, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
44 of 115 25/09/2024, 12:37
Parabéns! A alternativa A está correta.
Para modelar o problema, o primeiro passo é definir as variáveis de
decisão. Nesse caso, as variáveis de decisão são:
• x1: unidade de sapato consertada.
• x2: unidade de sapato fabricada.
O sapateiro tem disponível um total de 12 unidades de couro, de
modo que a restrição será uma inequação do tipo ≤.
O sapateiro gasta uma unidade de couro para consertar uma
unidade de sapato e 4 unidades de couro para fabricar um par de
sapatos. Com isso, para fabricar uma unidade de sapato, o
sapateiro precisa de 2 unidades de couro. Podemos afirmar,
portanto, que a restrição referente à disponibilidade de couro para a
B
x1 + 2x2 ≤ 12, sendo x1 a unidade de sapato
fabricada e x2 a unidade de sapato consertada.
C
x1 + 4x2 ≤ 12, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
D
x1 + 4x2 ≤ 12, sendo x1 a unidade de sapato
fabricada e x2 a unidade de sapato consertada.
E
3x1 + x2 ≤ 12, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
45 of 115 25/09/2024, 12:37
portanto, que a restrição referente à disponibilidade de couro para a
produção ou conserto de sapatos é x1 + 2x2 ≤ 12.
Questão 4
Pedido 3 – A restrição referente às horas trabalhadas é:
Parabéns! A alternativa C está correta.
Para modelar o problema, o primeiro passo é definir as variáveis de
A
, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
3x
1
+ x
2
≤ 10
B
, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
3x
1
+ 2x
2
≤ 10
C
, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
x
1
3
+ x
2
≤ 10
D, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
x
1
3
+ 2x
2
≤ 10
E
, sendo x1 a unidade de sapato
consertada e x2 a unidade de sapato fabricada.
3x
1
+ x
2
≥ 10
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
46 of 115 25/09/2024, 12:37
Para modelar o problema, o primeiro passo é definir as variáveis de
decisão, que são:
• x1: unidade de sapato consertada.
• x2: unidade de sapato fabricada.
A jornada diária do sapateiro é de 10 horas. Logo, ele trabalha um
total de 10 horas diárias, no máximo, e podemos concluir que a
restrição será uma inequação do tipo ≤.
O sapateiro conserta 3 sapatos por hora, se somente consertar
sapatos. Logo, ele leva 20 minutos (1/3 da hora) para consertar
cada unidade de sapato. O sapateiro leva 2 horas para fazer um par
de sapatos novos. Desse modo, ele fabrica uma unidade de sapato
por hora, levando 1 hora para fabricar cada unidade de sapato.
Podemos afirmar, portanto, que a restrição referente às horas
trabalhadas para a produção ou o conserto de sapatos é
x
1
3
+ x
2
≤ 10
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
47 of 115 25/09/2024, 12:37
3 - Método simplex para a resolução de problemas de
programação linear
Ao �nal deste módulo, você será capaz de empregar o método simplex para a resolução de
problemas de programação linear
Apresentação do tema
O vídeo aborda o método simplex e sua importância para a resolução de
problemas.
O método simplex para a solução de
modelos de programação linear
Podemos resolver, de forma simples, problemas de programação linear
com duas variáveis de decisão por meio do método gráfico. Entretanto,
são poucos os problemas de programação linear no mundo real que

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
48 of 115 25/09/2024, 12:37
são poucos os problemas de programação linear no mundo real que
envolvem apenas duas variáveis de decisão, de modo que a aplicação
do método gráfico é bastante limitada.
Então, como fazemos para solucionar
problemas mais complexos, com um maior
número de variáveis de decisão?
Existe uma série de técnicas matemáticas para resolver problemas de
programação linear com qualquer número de variáveis sem a
necessidade de visualizar em gráficos as regiões viáveis. Dentre tais
técnicas, destaca-se o algoritmo simplex, que foi o primeiro método
desenvolvido para resolver problemas de programação linear.
O algoritmo simplex foi desenvolvido por George B. Dantzig, em 1947,
enquanto trabalhava como consultor em matemática para o controle da
Força Aérea norte-americana. O método simplex é específico para a
solução de problemas de otimização linear (equações ou inequações
lineares). Trata-se de um algoritmo eficiente que se baseia na solução
sucessiva de sistemas de equações indeterminados, em que sistemas
adjacentes são avaliados de forma iterativa, sendo, assim, adaptável ao
cálculo computacional. Na época, os computadores estavam
começando a surgir, e a resolução desse tipo de problema se tornava
importante na prática!
O simplex é considerado uma das grandes
contribuições à programação matemática.
Antes de estudarmos o algoritmo simplex, é importante entendermos o
conceito do simplex e recordarmos alguns pontos sobre a solução de
problemas de programação linear com duas variáveis de decisão por
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
49 of 115 25/09/2024, 12:37
problemas de programação linear com duas variáveis de decisão por
meio do método gráfico.
O que é um simplex?
Um simplex é um polígono convexo, ou seja, com propriedade especial:
uma reta que passe por quaisquer dois pontos pertencentes a um
simplex deve estar contida inteiramente dentro do simplex. Logo, na
figura a seguir, observa-se que o polígono representado em (a) não é
convexo, enquanto o ilustrado em (b) é um simplex.
Polígono não convexo e polígono simplex.
As restrições de um problema de programação linear sempre definem
hiperespaços convexos. Esta é a premissa do algoritmo simplex e de
boa parte da teoria de otimização convexa. Assim, o espaço de
soluções de um problema de programação linear, ou seja, a área
formada pela intersecção das restrições do problema, é uma forma
geométrica simplex.
Método grá�co
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
50 of 115 25/09/2024, 12:37
Para encontrar a solução ótima pelo método gráfico, precisamos seguir
os seguintes passos:
Em um caso bidimensional, o espaço de soluções viáveis é um plano, e
a função objetivo é representada por um vetor. Assim, por meio do
método gráfico, buscamos a reta (x2 = z — ax1) perpendicular ao vetor
da função objetivo com o maior (ou menor) possível dentro do espaço
 Desenhe as retas correspondentes às restrições do
problema e encontre o espaço de soluções.
 Desenhe o vetor z (função objetivo).
 Desenhe linhas ortogonais ao vetor z. Essas são as
linhas de isocusto, isto é, são as retas que têm o
mesmo valor de z.
 Calcule o valor de z no ponto ótimo, ou seja, a linha
de isocusto com maior z que ainda pertence ao
espaço de soluções.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
51 of 115 25/09/2024, 12:37
da função objetivo com o maior (ou menor) possível dentro do espaço
de soluções. Como o espaço de soluções é simplex, a reta x2 = z — ax1
para z ótimo que corta o plano, obrigatoriamente, corta as retas de
restrições. Ainda, como nos pontos de interseção (vértices) temos
mudança de inclinação (retas diferentes), garante-se que a solução
ótima se dá na interseção entre retas de restrições (nos vértices), de
modo que o algoritmo simplex analisa apenas os pontos de interseção
do espaço de soluções.
Na verdade, esta foi a grande ideia de Dantzig para o
desenvolvimento do algoritmo simplex: dado que a
solução ótima está em um vértice do espaço de
soluções viáveis, por que não percorrê-los em busca da
melhor solução possível?
Método simplex
Conforme verificamos, a chave do algoritmo simplex está no formato da
região limitada pelas restrições. Portanto, apesar de ser um
procedimento algébrico, os conceitos subjacentes ao método simplex
são geométricos.
O simplex é um algoritmo iterativo, que se utiliza de um ferramental
baseado em álgebra linear para a resolução sucessiva de sistemas de
equações, embora as restrições de problemas de programação
matemática sejam tipicamente inequações. Desse modo, a primeira
etapa do método simplex consiste em converter as restrições de
desigualdade em restrições de igualdade equivalente. O algoritmo
simplex só pode ser rodado se o problema estiver escrito na forma
canônica, que é a forma de se representar programas matemáticos por
meio de equações. Para isso, precisamos criar as chamadas variáveis
de folga ou de excesso.
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
52 of 115 25/09/2024, 12:37
de folga ou de excesso.
Exemplo (forma canônica):
 + = 10
 = Variável de folga
Assim, se , então teríamos que a variável de folga seria
igual a 2. Se , então teríamos que a variável de folga 
seria igual a 7.
Exemplo (forma canônica):
 - = 10
 = Variável de excesso
Assim, se , então teríamos que a variável de excesso e1
seria igual a 2. Se , então teríamos que a variável de
excesso seria igual a 5.
Veja o caso do problema da Fitwear, apresentado a seguir. Será que
conseguimos escrevê-lo em sua forma canônica?
Variáveis de folga (f) 
x
1
≤ 10 → x
1
f
1
f
1
x
1
= 8 f
1
x
1
= 3 f
1
Variáveis de excesso (e) 
x
1
≥ 10 → x
1
e
1
e
1
x
1
= 12
x
1
= 15
e
1
Bases de Otimização com o MS Excelhttps://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
53 of 115 25/09/2024, 12:37
conseguimos escrevê-lo em sua forma canônica?
Caso Fitwear S/A
A Fitwear S/A é uma confecção de roupas esportivas, tendo uma linha
fitness feminina, na qual produz roupas de ginástica exclusivas para
mulheres, como tops e calças de lycra.
Cada top de ginástica é vendido por R$80,00 e utiliza R$20,00 de
matéria-prima, como tecido e alinhamentos, e R$32,00 de mão de obra.
Trinta minutos de corte e 15 minutos de costura são demandados para
a confecção de um top de ginástica.
Cada calça de ginástica é vendida por R$120,00 e utiliza R$35,00 de
matéria-prima, como tecido e alinhamentos, e R$40,00 de mão de obra.
Quinze minutos de corte e 30 minutos de costura são demandados para
a confecção de uma calça de ginástica.
A Fitwear só pode contar com 100 horas de corte por semana e 160
horas de costura. A confecção não tem problemas no fornecimento de
matérias-primas, de modo que seu suprimento pode ser considerado
ilimitado, bem como a demanda semanal de seus produtos.
A Fitwear deseja planejar sua produção semanal de modo a maximizar
seus lucros.
Quando modelamos o problema, consideramos as seguintes variáveis
de decisão:
x1
Número de tops de ginástica confeccionados a cada semana.
x2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
54 of 115 25/09/2024, 12:37
Número de calças de ginástica confeccionadas a cada semana.
Assim, chegamos à seguinte formulação matemática em sua forma-
padrão.
Sujeito a (forma-padrão):
 ➜ restrição de horas de
corte
 ➜ restrição de horas de
costura
 ➜ restrição de não negatividade das
variáveis de decisão
Observe que tanto a restrição referente às horas de corte quanto a
restrição referente às horas de costura são do tipo ≤. Logo,
precisaremos de duas variáveis de folga, e , para passar o
problema para sua forma canônica.
Sujeito à (forma canônica):
MáxZ = 28x
1
+ 40x
2
0, 5x
1
+ 0, 25x
2
≤ 100
0, 25x
1
+ 0, 5x
2
≤ 160
x
1
, x
2
≥ 0
f
1
f
2
MáxZ = 28x
1
+ 40x
2
0, 5x
1
+ 0, 25x
2
+ f
1
= 100
0, 25x
1
+ 0, 5x
2
+ f
2
= 160
x
1
x
2
≥ 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
55 of 115 25/09/2024, 12:37
Uma vez adicionadas as variáveis de folga, o problema da Fitwear é dito
no formato canônico e pronto para ser resolvido pelo método simplex!
Para resolver o problema de programação linear, o algoritmo simplex se
baseia na solução sucessiva de sistemas de equações, utilizando-se do
conceito de variáveis básicas e não básicas:
São aquelas para as quais o sistema de equações é resolvido.
São aquelas que são zeradas para que o sistema de equações
apresente uma solução, ou seja, para que o número de equações
seja igual ao número de variáveis, permitindo, assim, a solução
do sistema de equações.
No problema da Fitwear, por exemplo, temos quatro variáveis ( , , 
e ) e apenas duas equações (restrições). Entretanto, para que um
sistema de equações lineares seja resolvido, é necessário que o número
de equações seja igual ao número de variáveis. De tal modo, para
resolver o problema da Fitwear, devemos considerar duas variáveis
como nulas (não básicas) e resolver o problema para outras duas
(variáveis básicas), e assim fazemos por iterações sucessivas, até que
encontremos o par de variáveis básicas que nos dá a solução ótima.
Em linhas gerais, o algoritmo simplex parte de uma solução viável do
x
1
, x
2
≥ 0
Variáveis básicas 
Variáveis não básicas 
x
1
x
2
f
1
f
2
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
56 of 115 25/09/2024, 12:37
Em linhas gerais, o algoritmo simplex parte de uma solução viável do
sistema de equações que constituem as restrições do problema de
programação linear, solução essa normalmente extrema (vértice). A
partir dessa solução inicial, o algoritmo adota um critério de escolhas
para encontrar novos e melhores vértices da envoltória convexa do
problema, e outro critério para determinar se o vértice escolhido
(solução básica) é ou não um vértice ótimo (GOLDBARG; LUNA, 2005).
Assim, pelo método simplex, devemos:
 Transformar o modelo em sua forma canônica, ou
seja, transformar o sistema de inequações em
sistema de equações.
 Determinar uma solução básica inicial, que será
iterativamente melhorada.
 Realizar o teste da otimalidade, ou seja, verificar se
a iteração atual é ótima ou se outras variáveis não
base (ou seja, que estão zeradas) devem entrar na
base, pois têm potencial para contribuir para
melhorar a solução.
 Realizar o teste da mínima razão, que determinará
qual variável básica deve sair da base, ou seja,
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
57 of 115 25/09/2024, 12:37
Arenales et al. (2007) descrevem o algoritmo simplex em duas fases. A
fase 1 traz o procedimento de como determinar uma solução inicial,
enquanto o método simplex propriamente dito é apresentado na fase 2.
Escreva o problema na forma canônica
Minimizar 
, sendo A uma matriz mxn
Determine inicialmente uma partição básica factível A = [B.N], ou
seja, com dois vetores de índices básicos e não básicos:
(B1, B2, ..., Bm)e N1, N2, ..., Nn — m.
Faça iteração=1.
qual variável básica deve sair da base, ou seja,
verificará quais das variáveis devem passar a ser
nulas para que a nova variável entre na base.
 Calcular a nova solução básica e voltar ao passo 3.
Passo 1 
f(x) = c
T
x
Ax = b
x ≥ 0
Passo 2 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
58 of 115 25/09/2024, 12:37
Faça iteração=1.
Fase 2: {início da iteração simplex}
 (equivalentemente, resolva o sistema )
{vetor multiplicador simplex}
 (equivalentemente, resolva o sistema
)
{custos relativos}
)
{determinação da variável a entrar na base}
 = mínimo (a
variável entra na base)
Passo 1: {cálculo da solução básica} 
x̂
b
= B
−1
b Bx
b
= b
x̂
n
= 0
Passo 2: {cálculo dos custos relativos} 
λ
T
= c
T
B
B
−1
B
T
λ = c
b
ĉ
N
j
= c
N
j
− λ
T
a
Nj
, j = 1, 2, … , n − m
ĉ
N
j
{ĉ
N
, j = 1, 2, … , n − m}
x
Nk
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
59 of 115 25/09/2024, 12:37
Se , então pare {solução na iteração atual é
ótima}
(equivalentemente, resolva o sistema
Se , então: pare {problema não tem solução ótima finita:
Caso contrário, determine a variável a sair da base pela razão
mínima:
 mínimo
 (a
variável sai da base)
Passo 3: {teste da otimalidade} 
ĉ
N
j
≥ 0
Passo 4: {cálculo da direção simplex} 
y = B
−1
a
Nk
By = a
Nk
)
Passo 5: {determinação do passo e variável a sair da base} 
y ≤ 0
f(x) → −∞}
ε̂ =
x̂
Bl
y
l
=
{
x̂
Bi
y
i
, talque yi > 0, yi > 0, i = 1, 2, … m}
x
Bl
Passo 6: {atualização: nova variável básica, troque a l-
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
60 of 115 25/09/2024, 12:37
Matriz básica nova:
Matriz não básica nova:
Iteração = iteração +1
Retorne ao passo 1
{fim da iteração simplex}
Na forma de algoritmo, como apresentado por Arenales et al. (2007), o
método simplex pode parecer difícil, mas vamos entender o que Dantzig
propôs por meio de um exemplo.
Caso da empresa Glass Co.
A empresa Glass Co., que possui três fábricas, produz janelas e portas
de vidro. As esquadrias e ferragens em aço são feitas na fábrica 1, as
esquadrias de madeira são produzidas na fábrica 2 e a fábrica 3 produz
o vidro e monta os produtos.
A direção da empresa decidiu modernizar sua linha de produtos e
propôs o lançamento de dois novos produtos:
• Produto 1: porta de vidro de 2,5m com esquadriade alumínio.
Passo 6: {atualização: nova variável básica, troque a l-
ésima coluna de b pela k-ésima coluna de n} 
B = [ ]a
B1
… aB
l−k
a
Nk
a
Bl+1
… a
Bm
N = [ ]a
N1
… a
Nk−1
a
Bl
a
Nk+1
… a
Nn−m
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
61 of 115 25/09/2024, 12:37
• Produto 2: janela adornada com esquadria de madeira 1,2m x
1,8m.
O produto 1 requer capacidade produtiva das fábricas 1 e 3. O produto 2
precisa das fábricas 2 e 3. A divisão de marketing concluiu que a
empresa poderia vender tanto quanto fosse possível produzir desses
produtos por essas fábricas. Porém, ambos os produtos competem por
capacidade produtiva da fábrica 3, não estando claro qual mix dos dois
seria mais lucrativo. Determine quais devem ser as taxas de produção
para maximizar o lucro total, sujeitas às restrições impostas pela
capacidade produtiva:
Fábrica
Tempo de produção por lote (em horas)
Produtos
1 2
1 1 0
2 0 2
3 3 2
Lucro por lote R$3.000,00 R$5.000,00
Produção empresa Glass Co.
Extraída de Hellier e Lieberman, 2013, pág. 21.
Inicialmente, devemos escrever o modelo matemático para o problema
da Glass Co., seguindo os passos do procedimento para construção do
modelo de programação linear:

Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
62 of 115 25/09/2024, 12:37

Identificação das variáveis de decisão

Identificação da função objetivo

Identificação do conjunto de restrições
A seguir, vamos seguir cada um dos passos indicados.
No caso da Glass Co., a empresa deve decidir os produtos a
serem fabricados. Logo, a definição da variável de decisão seria:
 — quantidade de produto i confeccionada
Assim, temos:
 - Quantidade de lotes produtos 1 fabricados.
 - Quantidade de lotes produtos 2 fabricados.
Identificação das variáveis de decisão 
x
i
x
1
x
2
Identificação da função objetivo 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
63 of 115 25/09/2024, 12:37
No caso da Glass Co., a empresa deseja maximizar seu lucro
total:
Determine quais devem ser as taxas de
produção para maximizar o lucro total (…).
Para cada lote de portas de vidro de 2,5m com esquadria de
alumínio (produto 1) vendido, a empresa lucra R$3.000,000,
enquanto o lucro de venda de cada lote de janela adornada com
esquadria de madeira 1,2m x 1,8m (produto 2) equivale a
R$5.000,00. Logo, o lucro total é igual a ., de
modo que a função objetivo para o problema é:
No caso do problema da Glass Co., foram consideradas
ilimitadas a demanda por seus produtos e a oferta de matéria-
prima, de modo que não entram como restrições no modelo
matemático. Porém, há restrições relacionadas ao tempo de
produção disponível por semana em cada fábrica.
Fábrica
Tempo de produção por lote (em horas)
Produtos
3000x
1
+ 5000x
2
MaxZ = 3x
1
+ 5x
2
Identificação do conjunto de restrições 
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
64 of 115 25/09/2024, 12:37
1
1 1
2 0
3 3
Produção empresa Glass Co.
Extraída de Hellier e Lieberman, 2013, pág. 21.
Há, ainda, a restrição de não negatividade das variáveis de
decisão, uma vez que não se pode produzir um número negativo
de portas ou janelas. Logo, a restrição 4 é dada por: 
Logo, temos as seguintes restrições:
• 
• 
• 
Enfim, temos o seguinte modelo matemático para o problema da Glass
Co.:
x
1
, x
2
≥ 0
x
1
≤ 4
2x
2
≤ 12 → x
2
≤ 6
3x
1
+ 2x
2
≤ 18
MaxZ = 3x
1
+ 5x
2
 s.a. 
x
1
≤ 4
2x
2
≤ 12
3x
1
+ 2x
2
≤ 18
x
1
, x
2
≥ 0
≥ 0
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
65 of 115 25/09/2024, 12:37
Mas qual é o mix de produção que nos dá a
solução ótima?
O primeiro passo do algoritmo simplex é transformar o modelo em seu
formato canônico.
Passando para o formato canônico, temos:
Em seguida, devemos escolher uma solução básica inicial. Observe que
temos três equações no sistema de equações e cinco variáveis. Dessa
forma, devemos ter três variáveis-base e duas não base. O modo mais
fácil de resolver esta etapa é escolher as variáveis e como
variáveis não básicas, uma vez que essa opção elimina o trabalho
necessário para encontrar a solução quando as variáveis básicas são as
variáveis de folga (ou excesso) ( , e ). Nesse caso, se e
, z seria igual a zero também, enquanto , e
.
x
1
, x
2
≥ 0
MaxZ = 3x
1
+ 5x
2
 s.a. 
x
1
+ f
1
= 4 →  restrição 1
2x
2
+ f
2
= 12 →  restrição 2
3x
1
+ 2x
2
+ f3 = 18 →  restrição 3
x
1
, x
2
, f
1
, f
2
, f
3
>= 0
x
1
x
2
f
1
f
2
f
3
x
1
= 0
x
2
= 0 f
1
= 4 f
2
= 12
f
3
= 18
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
66 of 115 25/09/2024, 12:37
Função objetivo: , logo, para a solução inicial de 
e , temos .
Restrição 1: .
Restrição 2: .
Restrição 3: .

Portanto, temos a solução inicial de .
Passamos, então, para o teste da otimalidade. Como ,
verificamos que o coeficiente de cada variável não básica ( e )
fornece a taxa de crescimento em .
Como as taxas de crescimento são positivas (3 e 5) e
este é um problema de maximização, concluímos que
Z = 3x
1
+ 5x
2
x
1
= 0
x
2
= 0 Z = 0
x
1
+ f
1
= 4 → 0 + f
1
= 4 → f
1
= 4
2x
2
+ f
2
= 12 → 0 + f
2
= 12 → f
2
= 12
3x
1
+ 2x
2
+ f
3
= 18 → 0 + 0 + f
3
= 18 → f
2
= 18
(0, 0, 4, 12, 18)
Z = 3x
1
+ 5x
2
x
1
x
2
Z
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
67 of 115 25/09/2024, 12:37
este é um problema de maximização, concluímos que
a solução inicial não é a solução ótima!
Já sabemos que a solução básica inicial não é ótima, então uma
variável não básica ( ou ) deve entrar na base. Porém, devemos
aumentar ou ?
Para determinar isso, devemos verificar a direção de deslocamento.
Observe que, para cada unidade que aumentarmos , temos uma taxa
de crescimento em de 3. Ao mesmo tempo, para cada unidade que
aumentarmos , temos uma taxa de crescimento em de 5. Sendo
, devemos optar por para crescer. Logo, é a variável básica
que entra.
Entretanto, para que passe a ser uma variável básica, uma das
variáveis-base da solução inicial ( , e ) precisa sair da base.
Porém, como determinar qual delas?
Para essa etapa, devemos ter em mente que, ao aumentar , eleva-se
. Contudo, não podemos sair do espaço de soluções, ou seja, da
região de soluções viáveis. Assim, devemos aumentar , mantendo a
variável não básica e respeitando que todas as variáveis sejam
não negativas.
 (variável não básica)
Como :
Teste da mínima razão
 não implica em limite superior em 
 MÍNIMO
(0, 0, 4, 12, 18)
x
1
x
2
x
1
x
2
x
1
Z
x
1
Z
5 > 3 x
2
x
2
x
2
f
1
f
2
f
3
x
2
Z
x
2
x
1
= 0
x
1
= 0
x
1
+ f
1
= 4 → f
1
= 4
2x
2
+ f
2
= 12 → f
2
= 12 − 2x
2
3x
1
+ 2x
2
+ f
3
= 18 → f
3
= 18 − 2x
2
x
1
, x
2
, f
1
, f
2
, f
3
≥ 0
f
1
= 4 → x
2
f 12 2 0 12/2 6
Bases de Otimização com o MS Excel https://stecine.azureedge.net/repositorio/00212ti/03824/index.html?bra...
68 of 115 25/09/2024, 12:37
 MÍNIMO
Verificamos, então, que passa a receber o valor de 6, enquanto se
torna uma variável não base e nula. Assim, deduzimos intuitivamente o
teste da mínima razão.
O objetivo do teste da mínima razão é determinar qual
variável básica cai a zero primeiro à medida que a
variável básica que entra é aumentada.
Podemos descartar imediatamente a variável básica em qualquer
equação cujo coeficiente da variável básica que entra é zero ou negativo,
já que uma variável básica não decresceria à medida que a variável
básica que entra aumentasse.
No caso do problema