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
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
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
Introdução
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
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:

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
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).
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:
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 frotae
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
Petrobrás 
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 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
MRS Logística 
Consultoria especializada 
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
Disciplinas da pesquisa operacional 
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:
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
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
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:
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 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 estáticos ou dinâmicos 
Modelos lineares ou não lineares 
Modelos inteiros ou não inteiros 
Modelos determinísticos ou estocá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.
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.
É 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
Formulação do problema 
Observação do sistema 
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.
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.
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 
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.
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!
Módulo 1 - Vem que eu te explico!
Pesquisa Operacional
Módulo 1 - Vem que eu te explico!
Modelos Matemáticos
Apresentação dos resultados e conclusão 
Implantação e análise das recomendações 

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.
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.
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 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
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.
E Seleção da melhor alternativa
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).

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 quepodem 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é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).
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
a1x1 + a2x2 +…+ amxm = an
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.
∑ni=1∑
m
j=1 cijxij
∑mj=1 xij ≤ Si, ∨̄i
z = f(x1,x2,… ,xn)
 sujeito a  : g1(x1,x2,… ,xn)
g2(x1,x2,… ,xn)
………………
gm(x1,x2,… ,xn)
⎫⎪⎬⎪⎭ Os valores das variáveis de decisão  devem satisfazer um  conjunto de restrições. 
Rotacione a tela. 
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.
O passo inicial do procedimento proposto consiste em identificar as variáveis desconhecidas a
serem determinadas – variáveis de decisão.
N t d id tifi bj ti ti id tá l f ã
Identificação das 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.
Nessa etapa, devem ser listadas todas as restrições do problema, sendo expressas como
equações (=) ou inequações lineares (>,<) em termos das variáveis de decisão. Tal como na
identificação da função objetivo, uma leitura atenta do enunciado é a melhor forma de
identificar os limitantes à função objetivo.
Segundo Rodrigues et al. (2014), deve-se dar especial atenção a passagens do problema em
que aparecem expressões como:
A quantidade transportada não poderá ultrapassar (...)
A quantidade recebida não poderá ser menor do que (...)
O máximo de horas disponíveis é (...), entre outras.
Programação linear
No vídeo a seguir você conhecerá o conceito de Programação Linear, os principais elementos de um
modelo de Programação Linear e os passos para a construção desse tipo de modelo:
Identificação do conjunto de restrições 

Aplicação do passo a passo para a construção de um
modelo de programação linear
Agora, iremos revisar os conceitos de Programação Linear estudados até aqui a partir de um exemplo.
Com isso, serão reforçados os elementos e as principais características de um problema de
Programação Linear por meio da construção de um modelo. Para isso, seguiremos os passos
apresentados previamente.
Exemplo
A Fitwear S/A é uma confecção de roupas esportivas e tem uma linha fitness feminina. Essa linha
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 com mão de obra. Além disso, são demandados 30 minutos de corte e 15
minutos de costura 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. São demandados 15 minutos de corte e 30 minutos de
costura 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 o seu suprimento pode ser
considerado ilimitado assim como a demanda semanal de seus produtos.
A Fitwear deseja planejar sua produção semanal de modo a maximizar seus lucros.
Vamos usar, a seguir, os passos do procedimento proposto para construção do modelo de
Programação Linear para o caso da Fitwear S/A.
Identi�cação das variáveis de decisão
As variáveis de decisão devem descrever completamente as decisões a serem tomadas. No caso da
Fitwear, a empresa deve decidir os produtos a serem confeccionados. Com isso, a definiçãoda
Variável de Decisão seria:
xi – quantidade de produto i confeccionada
Desse modo, temos: 
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.
Identi�cação da função objetivo
Em qualquer problema de Programação Linear, o analista sempre deseja maximizar ou minimizar
alguma função das variáveis de decisão. No enunciado do problema, devemos procurar pelo propósito
que se procura atingir. Dessa forma, saberemos o que deve ser maximizado ou minimizado a fim de
definirmos a função objetivo.
No caso da Fitwear, a empresa deseja maximizar seu lucro semanal:
A Fitwear deseja planejar sua produção semanal de modo a maximizar seus
lucros.
Atenção
Lucro semanal = lucro semanal oriundo da venda de tops + lucro semanal oriundo da venda de calças.
Precisamos, portanto, determinar o ganho semanal obtido com a venda dos produtos e subtrair destes
os gastos semanais com matéria-prima e mão de obra. Vejamos:
Ganho semanal da venda de tops e calças
Cada 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
Rotacione a tela. 
A função objetivo, portanto, é
Os coeficientes da função objetivo indicam a contribuição de cada variável nos lucros da Fitwear.
Identi�caçã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:
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. 
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:
Rotacione a tela. 
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
Vem que eu te explico!
Módulo 2 - Vem que eu te explico!
Programação Matemática
Restrição 3: restrição de não negatividade das variáveis de decisão. 
MáxZ = 28x1 + 40x2

Módulo 2 - Vem que eu te explico!
Variáveis de Decisão, Parâmetros e Função Objetivo
Falta pouco para atingir seus objetivos.
Vamos praticar alguns conceitos?
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
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.
É 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.
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 é:
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.
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ívelum 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 x1 a unidade de sapato consertada e x2 a unidade de sapato
fabricada.
3x1 + x2 ≤ 10
B
, sendo x1 a unidade de sapato consertada e x2 a unidade de
sapato fabricada.
3x1 + 2x2 ≤ 10
C
, sendo x1 a unidade de sapato consertada e x2 a unidade de sapato
fabricada.
x1
3 + x2 ≤ 10
D
, sendo x1 a unidade de sapato consertada e x2 a unidade de sapato
fabricada.
x1
3 + 2x2 ≤ 10
E
, sendo x1 a unidade de sapato consertada e x2 a unidade de sapato
fabricada.
3x1 + x2 ≥ 10
Parabéns! 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 é $$$ \frac{x_{1}}{3}+x_{2} \leq 10 $$$
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 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á�co
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.
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
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.
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.
Exemplo (forma canônica):
 + = 10
Rotacione a tela. 
 = 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
Rotacione a tela. 
 = Variável de excesso
Variáveis de folga (f) 
x1 ≤ 10 → x1 f1
f1
x1 = 8 f1 x1 = 3
f1
Variáveis de excesso (e) 
x1 ≥ 10 → x1 e1
e1
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.
x1 = 12 x1 = 15
e1
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.
Rotacione a tela. 
Sujeito à (forma canônica):
Rotacione a tela. 
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:
MáxZ = 28x1 + 40x2
0, 5x1 + 0, 25x2 ≤ 100
0, 25x1 + 0, 5x2 ≤ 160
x1,x2 ≥ 0
f1 f2
MáxZ = 28x1 + 40x2
0, 5x1 + 0, 25x2 + f1 = 100
0, 25x1 + 0, 5x2 + f2 = 160
x1,x2 ≥ 0
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 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:
Variáveis básicas 
Variáveis não básicas 
x1 x2 f1 f2
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.
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
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.
Passo 1 
f(x) = cT x
Ax = b
x ≥ 0
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}
 (equivalentemente, resolva o sistema )
{vetor multiplicador simplex}
 (equivalentemente, resolva o sistema )
Rotacione a tela. 
{custos relativos}
)
Rotacione a tela. 
Passo 2 
Passo 1: {cálculo da solução básica} 
x̂b = B
−1b Bxb = b
x̂n = 0
Passo 2: {cálculo dos custos relativos} 
λT = cTBB
−1 BT λ = cb
ĉNj = cNj − λ
T aNj, j = 1, 2,… ,n −
m
{determinação da variável a entrar na base}
 = mínimo (a variável entra na
base)
Rotacione a tela. 
Se , então pare {solução na iteração atual é ótima}
Rotacione a tela. 
(equivalentemente, resolva o sistema 
Rotacione a tela. 
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
ĉNj {ĉN , j = 1, 2,… ,n − m} xNk
Passo 3: {teste da otimalidade} 
ĉNj ≥ 0
Passo 4: {cálculo da direção simplex} 
y = B−1aNk By = aNk)
Passo 5: {determinação do passo e variável a sair da base} 
y ≤ 0 f(x) → −∞}
ε̂ = x̂Bl = { x̂Bi , talque yi > 0, yi > 0, i = 1, 2,…m}
o (a
variável sai da base)
Rotacione a tela. 
Matriz básica nova:
Rotacione a tela. 
Matriz não básica nova:
Rotacione a tela. 
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.
ε
yl
{
yi
, talque yi > 0, yi > 0, i , , m}
xBl
Passo 6: {atualização: nova variável básica, troque a l-ésima coluna de b pela k-ésima
coluna de n} 
B =
[ ]aB1 … aBl−k aNk aBl+1 … aBm
N =
[ ]aN1 … aNk−1 aBl aNk+1 … aNn−m
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:
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.
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.
No casoda Glass Co., a empresa deseja maximizar seu lucro total:
Determine quais devem ser as taxas de produção para
Identificação das variáveis de decisão 
xi
x1
x2
Identificação da função objetivo 
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 é:
Rotacione a tela. 
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 p
semana (hor
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
3000x1 + 5000x2
MaxZ = 3x1 + 5x2
Identificação do conjunto de restrições 
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.:
Rotacione a tela. 
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:
x1,x2 ≥ 0
x1 ≤ 4
2x2 ≤ 12 → x2 ≤ 6
3x1 + 2x2 ≤ 18
MaxZ = 3x1 + 5x2
 s.a. 
x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1,x2 ≥ 0
x1,x2 ≥ 0
MaxZ = 3x1 + 5x2
Rotacione a tela. 
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 .
Função objetivo: , logo, para a solução inicial de e , temos .
Restrição 1: .
Rotacione a tela. 
Restrição 2: .
Rotacione a tela. 
Restrição 3: .
 s.a. 
x1 + f1 = 4 →  restrição 1
2x2 + f2 = 12 →  restrição 2
3x1 + 2x2 + f3 = 18 →  restrição 3
x1,x2, f1, f2, f3 >= 0
x1 x2
f1 f2 f3 x1 = 0 x2 = 0
f1 = 4 f2 = 12 f3 = 18
Z = 3x1 + 5x2 x1 = 0 x2 = 0 Z = 0
x1 + f1 = 4 → 0 + f1 = 4 → f1 = 4
2x2 + f2 = 12 → 0 + f2 = 12 → f2 = 12
3x1 + 2x2 + f3 = 18 → 0 + 0 + f3 = 18 → f2 = 18
Rotacione a tela. 

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 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) 
 
 
(0, 0, 4, 12, 18)
Z = 3x1 + 5x2
x1 x2 Z
(0, 0, 4, 12, 18)
x1 x2
x1 x2
x1 Z
x1 Z 5 > 3
x2 x2
x2 f1
f2 f3
x2 Z
x2
x1 = 0
x1 = 0
x1 + f1 = 4 → f1 = 4
2x2 + f2 = 12 → f2 = 12 − 2x2
Rotacione a tela. 
Como :
Teste da mínima razão 
 não implica em limite superior em 
 MÍNIMO 
Rotacione a tela. 
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 da Glass Co., ao aumentarmos o valor de de 0 a 6, temos mudanças na
solução.
f f
3x1 + 2x2 + f3 = 18 → f3 = 18 − 2x2
x1,x2, f1, f2, f3 ≥ 0
f1 = 4 → x2
f2 = 12 − 2x2 ≥= 0 → x2 ≤ 12/2 = 6 ←
f3 = 18 − 2x2 ≥ 0 → x2 ≤ 18/2 = 9
x2 f2
x2
Solução inicial 
x1 = 0
x2 = 0
F1 = 4
F2 = 12
F3 = 18
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 !
Rotacione a tela. 
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 
 
Nova solução 
x1 = 0
x2 = 6
F1 =?
F2 = 0
F3 =?
x2 x1
Z = 3x1 + 5x2 = 3 ∗ 0 + 5 ∗ 6 = 30 f1 f2 f3
x1 + f1 = 4 → 0 + f1 = 4 → f1 = 4
2x2 + f2 = 12 → 2 ∗ 6 + f2 = 12 f2 = 0
3x1 + 2x2 + f3 = 18 → 3 ∗ 0 + 2 ∗ 6 + f3 = 18 → f3 = 6
0, 6, 4, 0, 6 Z = 30
Z = 3x1 + 5x2 x1 = 3 x1
Z
x1
x1
Z − 3x1 − 2, 5x2 = 30
x1 + f1 = 4
2x2 + f2 = 12
3x1 + 2x2 + f3 = 18
f1 = 4 − x1 ≥ 0 → x1 ≤ 4/1 → x1 ≤ 4
 nenhum limite superior em 
 mínima razão
Rotacione a tela. 
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 .
 
 
Rotacione a tela. 
f /
f2 = 12 − 2x2 ≥ 0 → x1
f3 = 6 − 3x1 ≥ 0 → x →≤ 6/3 → x1 ≤ 2 →
f3 x1 x1
Solução inicial 
x1 = 0
x2 = 6
F1 = 4
F2 = 0
F3 = 18
Nova solução 
x1 = 2
x2 = 6
F1 =?
F2 = 0
F3 =?
x2 x1 Z = 3x1 + 5x2 = 3 ∗ 2 + 5 ∗ 6 = 36
f1 f2 f3
x1 + f1 = 4 → 2 + f1 = 4 → f1 = 2
2x2 + f2 = 12 → 2 ∗ 6 + f2 = 12 → f2 = 0
3x1 + 2x2 + f3 = 18 → 3 ∗ 2 + 2 ∗ 6 + f3 = 18 → f3 = 0
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 coeficientesda 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.
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
x1 f3
2, 6, 2, 0, 0 Z = 36 f2 f3
Z
 Minimizar f(x) = cx
Ax = b
x ≥ 0
x1,x2 …xn
c1, c2 … cn a1, a2 … an b
mxm
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:
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,
b ≥ 0
= 0
ck cj
ck ≥ 0 xk
aik ≤ 0, i = 1,… ,m f → −∞
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 é apresentado a seguir.
Rotacione a tela. 
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.
bl
alk
{ biaik aik > 0, i = 1,… ,m}
(l, k)) xk
MaxZ = 3x1 + 5x2
 s.a. 
x1 + f1 = 4 →  restrição 1
2x2 + f2 = 12 →  restrição 2
3x1 + 2x2 + f3 = 18 →  restrição 3
x1,x2, f1, f2, f3 >= 0
Tabela simplex.
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 .
Rotacione a tela. 
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 
f1 f2 f3
B = I e B−1 = I
MaxZ = 3x1 + 5x2
x1 + f1 = 4
2x2 + f2 = 12
3x1 + 2x2 + f3 = 18
  a3 a4 a5 a1 a2
A = [ ] =
  f1 f2 f3 x1 x2
B I N
⎡⎢⎣1 0 0 I 1 00 1 0 I 0 20 0 1 I 3 2⎤⎥⎦B = B−1 =⎡⎢⎣1 0 00 1 00 0 1⎤⎥⎦ ⎡⎢⎣1 0 00 1 00 0 1⎤⎥⎦ zj − cj
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. é:
-3 -5 0
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 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 . Como as 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.
z
x1 x2 f1
Z
Z Z0 f1 f2 f3
Z = 3x1 + 5x2 x1 = x2 = 0
x1 x2 f1
Z
yj
B = I B−1 = I yj = aj
f1 f2 f3
MaxZ = 3x1 + 5x2
s. a.
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.
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
b̄ = B−1b = Ib = b
b
MaxZ = 3x1 + 5x2
s. a.
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.
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 é: .

x2 xx x2
5 > 3.
x2
f2
x2
f2
f2
x2 f2
(3)′
(3)′ = (3)/2
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 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 .
x2
f2
(4)′ (4)′ = (4) − 2∗(3) (1)′
(1)′ = (1) + 5∗(3)′
x2
f2
x1
x1 f3
x1 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 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.
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 valorespara as colunas e
 já são coincidentes nesta linha.
x1
f3 (4)
′ = (4)/3
x1 f3
(2)′
(2)′ = (2) − (4)′ (1)′ (1)′ = (1) + 3∗(4)′
x1
f3
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.
Vem que eu te explico!
Módulo 3 - Vem que eu te explico!
O que é um simplex?
Módulo 3 - Vem que eu te explico!
O método simplex
x1 = 2 x2 = 6 z = 36

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.
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
x1
x2
A x1 = 320,x2 = 160
B x1 = 200,x2 = 160
C x1 = 160,x2 = 320
D x1 = 280,x2 = 220
E x1 = 280,x2 = 120
Parabéns! A alternativa A está correta.
O modelo matemático para este problema é:
Máx $$$Z=28 x_{1}+40 x_{2}$$$
Sujeito a:
$$$0,5 x_{1}+0,25 x_{2} \leq 100 \rightarrow$$$ restrição de horas de corte 
$$$0,25 x_{1}+0,5 x_{2} \leq 160 \rightarrow$$$ restrição de horas de costura 
$$$x_{1}, x_{2} \geq 0 \rightarrow$$$ restrição de não negatividade das variáveis de decisão
Em sua forma canônica, temos:
Máx $$$Z=28 x_{1}+40 x_{2}$$$
Sujeito a:
$$$0,5 x_{1}+0,25 x_{2}+f_{1}=100$$$ 
$$$0,25 x_{1}+0,5 x_{2}+f_{2}=160$$$ 
$$$x_{1}, x_{2} \geq 0$$$
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:
350x1 + 300x2
X1 + X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
A Zero
B 54.000
C 60.900
D 64.000
E 66.100
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.

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:
LINDO
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
bj ti
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.
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.
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 — 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.
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.
x1
x2
Temos a formulação matemática em sua forma-padrão.
Rotacione a tela. 
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 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.
MáxZ = 28x1 + 40x2
 Sujeito a: 
0, 5x1 + 0, 25x2 ≤ 100 →  restrição de horas