Pesquisa Operacional e Modelagem Matemática

Prévia do material em texto

Bases de Otimização com o MS Excel
A Pesquisa Operacional e a construção de modelos lineares utilizando o método simplex, no MS Excel.
Renata Albergaria de Mello Bandeira
1. Itens iniciais
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
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
Descrever conceitos gerais de Pesquisa Operacional e sua importância no processo de tomada de 
decisão.
Descrever as principais características e propriedades de um modelo de Programação Linear.
Empregar o método simplex para a solução de problemas de Programação Linear.
Aplicar o solver para a solução de problemas de Programação Linear.
Introdução
É 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
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. 
• 
• 
• 
• 
1. Pesquisa Operacional
Apresentação do tema
Neste vídeo você conhecerá o conceito de Pesquisa Operacional, sua origem e as áreas de aplicação:
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
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 (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
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).
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 entre organizações de diversas áreas após o fim do período de combate.
A partir de 1947, é crescente o 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.
Veja algumas empresas que utilizam a PO:
Petrobrás
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.
MRS Logística
A MRS Logística – operador ferroviário que atua na Malha Regional2. 
3. 
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.
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.
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. 
Instalando o solver — Passo 2.
Na tela seguinte, clique no botão ir, em gerenciar suplementos do Excel. 
4. 
5. 
Instalando o solver — Passo 3.
Na próxima tela, clique na opção solver.
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.
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.
 
MáxZ = 28X1 + 40 X2
 
Sujeito a:
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 (x1 e x2),
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.
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.
Restrição de horas de corte
Observe que fizemos a função “somarproduto” entre os vetores 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 costura
Observe que a célula destacada em amarelo na figura restrição de horas
de costura recebeu a fórmula .
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. 
• 
• 
• 
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. 
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.
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.
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 x1 deve ser 53,33, x2 recebe 293,333 e o valor ótimo de é igual a 13.226,67.
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.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Vem que eu te explico!
Utilização do solver para solução de problemas de Programação
Linear
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Passos para implementar um problema de Programação Linear em
planilha
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
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 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:
A
262,84
B
1262,84
C
2262,84
D
3262,84
E
4262,84
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:
X1 = quilos de grão tipo 1 usados na produção de um quilo de ração
X2 = quilos de grão tipo 2 usados na produção de um quilo de ração
X3 = quilos de grão tipo 3 usados na produção de um quilo de ração
Como se deseja minimizaro custo de produção e sabe-se o custo do quilo de cada tipo de grão, temos a
seguinte função objetivo:
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:
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 X1 deve ser
22,79, X2 recebe 20,22 e X3 é nulo, sendo o valor ótimo de Z igual a 1262,84.
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) Peixe (kg) Salada (100g)
A 2 2 10 20
C 50 20 10 80
D 80 70 10 80
Informações nutricionais em mg
 
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:
A
2,46
B
3,46
C
4,46
D
5,46
E
6,46
A alternativa E está correta.
A variável de decisão deve ser , sendo a quantidade de alimento do tipo "i" a ser consumida por dia.
Logo, temos:
X1 = litros de leite a serem consumidos por dia pelas crianças
X2 = quilos de carne a serem consumidos por dia pelas crianças
X3 = quilos de peixe a serem consumidos por dia pelas crianças
X4 = 100g de salada a serem consumidos por dia pelas crianças
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 X1 deve ser
2,91 litros de leite, X2 e X3 são nulos, enquanto X4 é igual a 208,33g de salada, sendo o valor ótimo de Z
igual a 6,46.
Solução ótima para o problema da Atividade 2.
 
 
5. Conclusão
Considerações finais
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 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.
Conteúdo interativo
Acesse a versão digital para ouvir o áudio.
Explore +
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.
 
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.
	Bases de Otimização com o MS Excel
	1. Itens iniciais
	Propósito
	Preparação
	Objetivos
	Introdução
	1. Pesquisa Operacional
	Apresentação do tema
	Conteúdo interativo
	Pesquisa operacional
	Saiba mais
	Origem – Circo de Blacket
	Saiba mais
	Atenção
	Aplicação da PO na análise de decisão
	Petrobrás
	MRS Logística
	Consultoria especializada
	Problemas do cotidiano
	Exemplo
	Modelo
	Atenção
	Disciplinas da pesquisa operacional
	Modelos matemáticos
	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.
	Composição
	Função objetivo - maximizar ou minimizar
	Sujeito a restrições
	Classificação
	Modelos estáticos ou dinâmicosModelos lineares ou não lineares
	Modelos inteiros ou não inteiros
	Modelos determinísticos ou estocásticos
	Fases de um estudo de pesquisa operacional
	Formulação do problema
	Observação do sistema
	Formulação do modelo matemático
	Verificação do modelo matemático e uso para predição
	Seleção da melhor alternativa
	Apresentação dos resultados e conclusão
	Implantação e análise das recomendações
	Vem que eu te explico!
	Pesquisa Operacional
	Conteúdo interativo
	Modelos Matemáticos
	Conteúdo interativo
	Verificando o aprendizado
	2. Modelo de programação linear
	Programação linear
	Saiba mais
	Atenção
	Características
	Elementos
	Variáveis de decisão
	Parâmetros
	Função objetivo
	Restrições
	Representação
	Passo a passo para a construção de um modelo de programação linear
	Identificação das variáveis de decisão
	Identificação da função objetivo
	Identificação do conjunto de restrições
	Programação linear
	Conteúdo interativo
	Aplicação do passo a passo para a construção de um modelo de programação linear
	Exemplo
	Identificação das variáveis de decisão
	Identificação da função objetivo
	Atenção
	Ganho semanal da venda de tops e calças
	Gasto semanal com matéria-prima
	Gasto semanal com mão de obra
	Identificação do conjunto de restrições
	Comentário
	Vem que eu te explico!
	Programação Matemática
	Conteúdo interativo
	Variáveis de Decisão, Parâmetros e Função Objetivo
	Conteúdo interativo
	Verificando o aprendizado
	3. Método simplex para a resolução de problemas de programação linear
	Apresentação do tema
	Conteúdo interativo
	O método simplex para a solução de modelos de programação linear
	O que é um simplex?
	Método gráfico
	Método simplex
	Caso Fitwear S/A
	X1
	X2
	Variáveis básicas
	Variáveis não básicas
	Caso da empresa Glass Co.
	Identificação das variáveis de decisão
	Identificação da função objetivo
	Identificação do conjunto de restrições
	Função objetivo
	Restrição 1
	Restrição 2
	Restrição 3
	Método simplex em sua forma tabular
	Fase 1
	Fase 2
	Dica
	Dica
	Atenção
	Vem que eu te explico!
	O que é um simplex?
	Conteúdo interativo
	O método simplex
	Conteúdo interativo
	Verificando o aprendizado
	Questão 2
	4. Solução de problemas de programação linear
	Utilização do solver para solução de problemas de programação linear
	Dica
	Passos para implementar um problema de programação linear em planilha
	Instalando o solver
	Utilizando o solver
	Dica
	Restrição de horas de corte
	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.
	Atenção
	Utilização do solver para a solução de problemas de programação linear
	Conteúdo interativo
	Vem que eu te explico!
	Utilização do solver para solução de problemas de Programação Linear
	Conteúdo interativo
	Passos para implementar um problema de Programação Linear em planilha
	Conteúdo interativo
	Verificando o aprendizado
	5. Conclusão
	Considerações finais
	Podcast
	Conteúdo interativo
	Explore +
	ReferênciasSudeste 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 programação do
transporte ferroviário de carga.
Consultoria especializada
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. 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.
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.
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.
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:
Modelagem, Simulação e Otimização
Programação Matemática
Processos Decisórios
Processos Estocásticos
Teoria dos Jogos
Análise de Demanda
Inteligência Computacional
O foco deste tema é a Programação Matemática.
Modelos matemáticos
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: 
1. 
2. 
3. 
4. 
5. 
6. 
7. 
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. 
Classificação
Os modelos matemáticos de otimização, segundo Winston (2004), podem ser classificados em:
Modelos estáticos ou dinâmicos
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 dinâmico, analisamos o problema ao longo do tempo.
Modelos lineares ou não lineares
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 modeloslineares.
Modelos inteiros ou não inteiros
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.
Modelos determinísticos ou estocásticos
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.
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:
Procedimento para desenvolvimento de modelos matemáticos em estudos de
pesquisa operacional.
Formulação do problema
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.
Observação do sistema
É 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.
Formulação do modelo matemático
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.
Verificação do modelo matemático e uso para predição
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.
Seleção da melhor alternativa
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.
Apresentação dos resultados e conclusão
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. Desse modo, pode ser necessário retornar para os
passos 1, 2 ou 3.
Implantação e análise das recomendações
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.
Vem que eu te explico!
Pesquisa Operacional
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Modelos Matemáticos
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
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.
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.
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 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:
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
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).
2. Modelo de programação linear
Programação linear
A Programação Matemática – geralmente chamada de otimização –, 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
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écnicade 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).
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= 
Restrições
É um conjunto de equações lineares que
traduzem o limite físico à solução do problema,
ou seja, são os limitantes dos 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
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.
Identificação das variáveis de decisão
O passo inicial do procedimento proposto consiste em identificar as variáveis desconhecidas a serem
determinadas – variáveis de decisão.
Identificação da função objetivo
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.
• 
• 
Identificação do conjunto de restrições
Nessa etapa, devem ser listadas todas as restrições do problema, sendo expressas como equações
(=) ou inequações lineares (>,top é vendido por R$ 80,00, e cada calça
é vendida por R$ 120,00. Logo, o ganho
semanal é igual a 80x1 + 120x2.
Observe que também devemos considerar os custos. Vejamos:
Gasto semanal com matéria-prima
Cada top utiliza R$ 20,00 em matéria-prima, e
cada calça utiliza R$ 35,00.Logo, o gasto
semanal com matéria-prima é igual a 20x1 +
35x2.
Gasto semanal com mão de obra
Para confeccionar cada top, gasta-se R$ 32,00
em mão de obra. Para cada calça, gasta-se R$
40,00. Logo, o gasto semanal com mão de obra
é igual a 32x1 + 40x2.
Desse modo, para determinar a função objetivo, tem-se:
(+) Ganho semanal com vendas: (80x1 + 120x2)
(-) Custo de matéria-prima: – (20x1 + 35x2)
(-) Custo de mão de obra: – (32x1 + 40x2)
(80x1 + 120x2) – (20x1 + 35x2) – (32x1 + 40x2) = 28x1 + 40x2
A função objetivo, portanto, é
Os coeficientes da função objetivo indicam a contribuição de cada variável nos lucros da Fitwear.
Identificação do conjunto de restrições
Observa-se que os valores dos coeficientes da função objetivo 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 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: 
 
Restrição 1: 100 horas de corte por semana.
 
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.
Restrição 1: 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.
 
Restrição 2: 160 horas de costura por semana.
 
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)
 
Logo, a restrição 2 é dada por: 0,25x1 + 0,5x2 ≤ 160.
 
Restrição 3: restrição de não negatividade das variáveis de decisão.
 
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
01 F
8 2 E ≤ 100 restrição de horas de corte
0,25x1 + 0,5x2
01 F
8 2 E ≤ 160 restrição de horas de costura
x1, x2
01 F
8 2 E ≥ 0 restrição de não negatividade das variáveis de decisão
Vem que eu te explico!
Programação Matemática
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Variáveis de Decisão, Parâmetros e Função Objetivo
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
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:
A
Variáveis de decisão
B
Variáveis condicionantes
C
Parâmetros
D
Função objetivo
E
Restrições
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.
É 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.
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 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 é:
A
x1 + 2x2 ≤ 12, sendo x1 a unidade de sapato consertada e x2 a unidade de sapato fabricada.
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.
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
produção ou conserto de sapatos é x1 + 2x2 ≤ 12.
Questão 4
Pedido 3 – A restrição referente às horas trabalhadas é:
A
, sendo a unidade de sapato consertada e a unidade de sapato fabricada.
B
, sendo a unidade de sapato consertada e a unidade de sapato fabricada.
C
, sendo a unidade de sapato consertada e a unidade de sapato fabricada.
D
, sendo a unidade de sapato consertada e a unidade de sapato fabricada.
E
, sendo a unidade de sapato consertada e a unidade de sapato fabricada.
A alternativa C está correta.
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 é 
3. 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.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
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
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 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áfico
Para encontrar a solução ótima pelo método gráfico, precisamos seguir os seguintes passos:
 
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.
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 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.
 
Variáveis de folga (f) 
 
Exemplo (forma canônica): 
 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.
 
Variáveis de excesso (e)
 
Exemplo (forma canônica):
 = 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?
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
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, f1 e f2, para passar o problema para sua forma
canônica.
Sujeito à (forma canônica):
 
Uma vez adicionadas as variáveis de folga, o problema da Fitwear é dito no formato canônico e prontopara
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:
Variáveis básicas
São aquelas para as quais o sistema de equações é resolvido.
Variáveis não básicas
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 (x1, x2, f1 e f2) 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 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,
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.
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.
 
Passo 1: escreva o problema na forma canônica.
Minimizar 
, sendo A uma matriz mxn
 
Passo 2: 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.
Fase 2: {início da iteração simplex}
 
Passo 1: {cálculo da solução básica}
 (equivalentemente, resolva o sistema )
 
Passo 2: {cálculo dos custos relativos}
 
{vetor multiplicador simplex}
1. 
2. 
3. 
4. 
5. 
{custos relativos}
{determinação da variável a entrar na base}
Passo 3: {teste de otimalidade}
 
Se , então pare \{solução na iteração atual é ótima\}
 
Passo 4: {cálculo da direção simplex}
 
 (equivalentemente, resolva o sistema 
 
Passo 5: {determinação do passo e variável a sair da base} 
 
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:
Passo 6: {atualização: nova variável básica, troque a l-ésima coluna de b pela k-ésima coluna de n} 
 
Matriz básica nova:
 (equivalentemente, resolva o sistema )
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 esquadria de alumínio.
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. 
Observe a tabela seguinte. 
Fábrica
Tempo de produção por lote (em
horas)
Tempo de produção disponível por
semana (horas)Produtos
1 2
1 1 0 4
2 0 2 12
3 3 2 18
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:
• 
• 
 
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.
Identificação das variáveis de decisão
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:
xi — quantidade de produto i confeccionada
Assim, temos:
x1 - Quantidade de lotes produtos 1 fabricados.
x2 - Quantidade de lotes produtos 2 fabricados.
Identificação da função objetivo
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 3000X1+5000x2.,
de modo que a função objetivo para o problema é:
• 
• 
• 
Identificação do conjunto de restrições
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)
Tempo de produção disponível por
semana (horas)Produtos
1 2
1 1 0 4
2 0 2 12
3 3 2 18
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:
x1≤4
2x2≤12→x2≤6
3x1+2x2≤18
Enfim, temos o seguinte modelo matemático para o problema da Glass Co.:
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 x1 e x2 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) (f1, f2 e f3). Nesse caso, se x1=0 e x2=0, z seria igual a zero também, enquanto f1=4, f2=12 e
f3=18.
Função objetivo
Z=3x1+5x2, logo, para a solução inicial de x1=0
e x2=0, temosZ=0.
Restrição 1
 x1+f1=4→0+f1=4→f1=4.
Restrição 2
2x2+f2=12→0+f2=12→f2=12.
Restrição 3
 3x1+2x2+f3=18→0+0+f3=18→f2=18.
Portanto, temos a solução inicial de (0,0,4,12,18).
 
Passamos, então, para o teste da otimalidade. Como Z=3x1+5x2, verificamos que o coeficiente de cada
variável não básica (x1 e x2) fornece a taxa de crescimento em Z.
Como as taxas de crescimento são positivas (3 e 5) e este é um problema de maximização,
concluímos que a solução inicial (0,0,4,12,18) 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 (x1 ou x2) deve entrar na
base. Porém, devemos aumentar x1 ou x2 ?
Para determinar isso, devemos verificar a direção de deslocamento. Observe que, para cada unidade que
aumentarmos x1, temos uma taxa de crescimento em Z de 3. Ao mesmo tempo, para cada unidade que
aumentarmos x1, temos uma taxa de crescimento em Z de 5. Sendo 5>3, devemos optar por x2 para crescer.
Logo, x2 é a variável básica que entra.
Entretanto, para que x2 passe a ser uma variável básica, uma das variáveis-base da solução inicial (f1, f2 e f3)
precisa sair da base. Porém, como determinar qual delas?
Para essa etapa, devemos ter em mente que, ao aumentar x2, eleva-se Z. Contudo, não podemos sair do
espaço de soluções, ou seja, da região de soluções viáveis. Assim, devemos aumentar x2, mantendo a variável
não básica x1=0 e respeitando que todas as variáveis sejam não negativas.
Como 
 
Teste da mínima razão
Verificamos, então, que x2 passa a receber o valor de 6, enquanto f2 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 da Glass Co., ao aumentarmos o valor de x2 de 0 a 6, temos mudanças na solução.
 
Solução inicial: 
 
Nova solução: 
Temos que x2 é igual a 6 e x1 continua sendo zero. Portanto, temos que Z=3x1+5x2=3∗0+5∗6=30. Devemos
determinar, então, os valores de f1, f2 e f3.
Então, devemos verificar se essa solução é ótima ou não, por meio do teste de otimalidade. Sendo
Z=3x1+5x2, verificamos que x1 tem o coeficiente positivo (=3), de modo que aumentar x1 implica em
Teste da mínima razão não implica em limite superior em 
 
aumentar Z. Portanto, a solução atual não é ótima e devemos realizar nova iteração, analisando a entrada de
x1 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 x1.
Logo, f3 sai da base para x1 entrar com o valor igual a 2. Porém, ao aumentarmos o valor de x1 de 0 a 2, temos
mudanças na solução.
 
Solução inicial: 
 
Nova solução: 
Temos que x2 é igual a 6 e x1 equivale a 2. Logo, temos que Z=3x1+5x2=3∗2+5∗6=36. Devemos determinar,
então, os valores de f1, f2 e f3.
Portanto, concluímos que x1 substitui f3 como variável básica, sendo a nova solução igual a (2,6,2,0,0) e Z=36.
As variáveis não básicas agora são f2 e f3. Verificamos que aumentar as atuais variáveis não básicas não
implica em aumento em Z, 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 x1,x2…xn. Os coeficientes da função objetivo são c1,c2…cn. Os
coeficientes das restrições são a1,a2…an e b.
 
Arenales et al. (2007) descrevem as operações realizadas em cada iteração do algoritmo simplex em tabelas,
em duas fases.
Fase 1
Determine a tabela simplex inicial.
A matriz dos coeficientes contém uma matriz identidade mxm (m é o número de equações) e o vetor
independente b≥0.
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 =0.
Fase 2
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 I. 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 é
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. seria (f1, f2 e f3), pois facilitaria o
preenchimento da tabela simplex inicial, dado que B=I e B−1=I.
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 zj−cj representa a
potencial melhoria no valor de z 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. é:
 RHS
-3 -5 0 0 0
O valor atual de Z, Z0, para esta primeira tabela, com as variáveis básicas sendo f1, f2, f3, seria igual a zero,
pois Z=3x1+5x2 e x1 = x2=0. Assim, atualizando a tabela, tem-se:
 RHS
-3 -5 0 0 0 0
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 yj. Como as variáveis de folga foram escolhidas como a
primeira base, temos B=I e B−1=I. Logo, temos yj=aj, 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 (f1, f2, f3) 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 b no lado direito da tabela, conforme
apresentado na figura a seguir.
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:
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. é x2, uma vez que tanto xx quanto x2 têm valoresnegativos na segunda
linha da tabela, sendo 5>3..
Depois de identificarmos a variável que entra na base, é preciso determinar a variável básica que deve dar
lugar para que x2 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 é f2.
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 x2 (da variável entrante) assuma a configuração
da coluna f2 (variável que sai da base). Observe, na figura a seguir, que a linha pivot é a quarta linha da tabela
(atual linha do f2 no lado esquerdo da tabela) e que os valores para as colunas x2 e f2 não coincidem, de
modo que é necessário executar a operação elementar. Portanto, sendo a linha (3)′ a quarta linha da tabela (3)
após a operação elementar, tem-se que a operação que transformará 2 em 1 é: (3)′=(3)/2.
Operações com a linha pivot para o problema da Glass Co.
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.
Observe, na segunda tabela da figura anterior, que, para a coluna x2 assumir a configuração anterior da coluna
f2, é preciso ainda realizar operações elementares nas linhas (1) e (4) da tabela simplex. Assim, para a linha
(4)′, é preciso que (4)′=(4)−2∗(3), enquanto para a linha (1)′ devemos fazer (1)′=(1)+5∗(3)′, 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 x2 e
f2 já são coincidentes. 
Operações com a linha pivot para o problema da Glass Co.
Verifique, na figura anterior, que a coluna x1 ainda apresenta um valor 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 x1 entre é f3. Portanto, são necessárias as operações elementares para que a coluna x1 receba
os valores da coluna f3.
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 x1 receba os valores da coluna f3, a
primeira operação elementar a ser feita é: (4)′=(4)/3, tal como apresentado na figura a seguir.
Primeira operação elementar (linha (4)) para o problema da Glass Co. — 2a iteração.
Para a coluna x1 assumir a configuração anterior da coluna f3, ainda é preciso realizar operações elementares
nas linhas (1) e (2) da tabela simplex. Assim, para a linha (2)′, é preciso que (2)′=(2)−(4)′, enquanto para a linha
(1)′ devemos fazer (1)′=(1)+3∗(4)′, 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 x1 e f3
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. é x1=2, x2=6 e z=36, 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. 
Vem que eu te explico!
O que é um simplex?
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
O método simplex
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
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.
 
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:
 
x1 = número de tops de ginástica confeccionados a cada semana
x2 = número de calças de ginástica confeccionadas a cada semana
A
B
• 
• 
C
D
E
A alternativa A está correta.
O modelo matemático para este problema é:
Sujeito a:
Em sua forma canônica, temos:
Sujeito a:
A solução do problema pela tabela simplex é:
 restrição de horas de corte restrição
de horas de costura restrição de não negatividade das variáveis de
decisão
Solução da Atividade 1 pela tabela simplex.
Questão 2
Utilize o método simplex para a solução desta programação linear:
Sujeito a:
A
Zero
B
54.000
C
60.900
D
64.000
E
66.100
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.
Solução da atividade 2 pela tabela simplex.
4. 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:
 
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 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.
• 
• 
• 
• 
• 
1.