Notas de aula Pesquisa Operacional

Prévia do material em texto

Prof. Dr. Francisco Pessoa de Paiva Júnior
Introdução à Pesquisa Operacional
SANTA INÊS
2023
1
Sumário
1 Introdução à Pesquisa Operacional 3
2 Introdução à Programação Linear 5
2.1 Características de um modelo de Programação Linear . . . . . . . . . . . . . . . . . 5
2.2 Diretrizes para a formulação de modelos de Programação Linear . . . . . . . . . . . 7
2.3 Método Gráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 Problema de Maximização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.2 Problema de Minimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3.3 Formulação Padrão de Modelo de Programação Linear . . . . . . . . . . . . 12
2.4 Casos Especiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Restrições incompatíveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.2 Solução sem fronteiras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.3 Redundância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.4 Soluções alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5 Análise da sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Terminologias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Exercícios Propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Método Simplex 30
3.1 Variáveis de folga e soluções básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Como opera o Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Rotina de cálculos do Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Simplex: Maximização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.1 Construindo o tableau inicial . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Construindo o segundo tableau . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Restrições com lado direito negativo . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5 Simplex: Minimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Title 44
5 Respostas dos Exercícios Propostos 45
5.1 Exercícios Propostos 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2
Capítulo 1
Introdução à Pesquisa Operacional
O estudo da Pesquisa Operacional iniciou-se ha cerca de 70 anos, seu inicio é atribuído a algumas
iniciativas militares da Segunda Guerra Mundial, já que neste período havia uma necessidade
urgente de alocar recursos escassos à varias operações militares e às atividades dentro de cada
operação de uma maneira efetiva. Várias seções de Pesquisa Operacional foram estabelecidas nas
forças armadas britânicas. Logo após, esforços similares foram empreendidos nos Estados Unidos.
Nesse período, um grande número de cientistas foi reunido para aplicar uma abordagem científica
a problemas estratégicos e táticos. Após o término do conflito, foi natural estender o sucesso da
Pesquisa Operacional no esforço da guerra para as organizações civis, sobretudo às indústrias pós
guerra. A partir de então, e com a crescente popularização do computador a Pesquisa Operacional
vem crescendo cada vez mais.
A Pesquisa Operacional lida com problemas de como conduzir e coordenar operações em uma
organização, e tem sido aplicada a diversas áreas, tais como indústria, transportes, telecomunica-
ções, finanças, saúde, serviços públicos, operações militares, etc.
A Pesquisa Operacional baseia-se, principalmente, no método científico para tratar de seus
problemas. A observação inicial e a formulação do problema estão entre os mais importantes
passos da solução de um problema da Pesquisa Operacional.
Por tudo isso, a Pesquisa Operacional hoje se tornou uma ferramenta de gerência e tomada de
decisões, com ela o administrador melhora o seu pensamento lógico, a capacidade de coordenação
e estruturação de problemas, além de ter um embasamento científico para as suas decisões.
Para entendermos melhor o que é Pesquisa Operacional tomemos o seguinte exemplo:
Imagine que você tenha um compromisso de trabalho em outra cidade, que chamaremos de B,
por um período de 5 dias. Você pega um avião em sua cidade natal, chamaremos de A, na segunda-
feira e volta na quarta-feira. Uma passagem aérea normal de ida e volta custa R$ 400,00, mas há
um desconto de 20% se as datas do bilhete abrangerem um final de semana. Uma passagem só de
ida em qualquer direção custa 75% do preço normal. Como seria mais conveniente você comprar
as passagens para o período de cinco semanas?
Podemos considerar essa situação como um problema de tomada de decisão, cuja solução requer
a resposta a três perguntas:
1. Quais são as alternativas para a decisão?
2. Sob quais restrições a decisão é tomada?
3
CAPÍTULO 1. INTRODUÇÃO À PESQUISA OPERACIONAL 4
3. Qual seria um critério objetivo para avaliar as alternativas?
Vamos considerar então três alternativas
1. Comprar 5 passagens normais A-B-A partindo às segundas-feiras e retornando às quartas-
feiras da mesma semana
2. Comprar uma passagem A-B e quatro B-A-B que abranjam finais de semana e uma B-A
3. Comprar uma passagem A-B-A para cobrir a segunda-feira da primeira semana e a quarta-
feira da ultima semana e quatro B-A-B para cobrir as viagens restantes. Todos esses bilhetes nessa
alternativa abrangem pelo menos um final de semana
A restrição a essas opções é que você possa sair na segunda-feira de A e voltar na quarta-feira
O critério objetivo óbvio para avaliar as alternativas é o preço dos bilhetes. A alternativa de
menor custo é a melhor
Solução:
Custo da alternativa 1: 5 x 400 = R$ 2 000,00
Custo da alternativa 2: 0,75 x 400 + 4 x 0,8 x 400 = R$ 1 880,00
Custo da alternativa 3: 5 x 0,8 x 400 = R$ 1 600,00
Portanto a alternativa 3 é a melhor opção.
Em um mundo de negócios cada vez mais dinâmico e competitivo, um administrador não se
pode dar chance de errar, por isso a Pesquisa Operacional é uma ótima ferramenta para qualquer
administrador que está sempre a tomar decisões.
Capítulo 2
Introdução à Programação Linear
2.1 Características de um modelo de Programação Linear
Dentre os diversos modelos matemáticos existentes, concentraremos nossa atenção inicialmente
no modelo de Programação Linear (PL). Esse modelo é básico para a compreensão de todos
os outros modelos da Pesquisa Operacional. Os conceitos nele firmados serão estendidos aos
demais, concedendo suporte a estudos mais avançados. Outra vantagem da Programação Linear
está na extraordinária eficiência dos algorítimos de solução hoje existentes, disponibilizando alta
capacidade de cálculo e podendo ser facilmente implementado até mesmo através de planilhas e
com o auxílio de microcomputadores pessoais.
Os modelos de Programação Linear são um tipo especial de modelos de otimização. Para que
um determinado sistema possa ser representado por meio de um modelo de PL, ele deve possuir
as seguintes características fundamentais:
1. Proporcionalidade: a quantidade de recurso consumido por uma dada atividade deve ser
proporcional ao nível dessa atividade na solução final do problema. Além disso, o custo de
cada atividade é proporcional ao nível de operação da atividade
2. Não Negatividade: deve ser sempre possível desenvolver dada atividade em qualquer nível
não negativo e qualquer proporção de um dado recurso deve sempre poder ser utilizado.
3. Aditividade: o custo total é a soma das parcelas associadas a cada atividade
4. Separabilidade: pode-se identificar de forma separada o custo (ou consumo de recursos)
específico das operações de cada atividade
Podemos ainda resumir essas características de uma maneira mais perceptível ao leitor
1. Existe uma combinação de variáveis que deve ser maximizada ou minimizada. Essa com-
binação pode ser a expressão do custo de algumas operações industriais ou comerciais, do
tempo gasto emcertas atividades, do lucro atingido com a venda de alguns produtos, da
rentabilidade média de uma composição de ações e títulos, e assim por diante. Durante a
5
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 6
formulação do problema, a combinação de variáveis a que se chega é colocada na forma de
uma expressão matemática, que recebe o nome de função objetivo. Eis um exemplo simples:
4𝑥 + 3𝑦 , onde x e y são as duas variáveis de interesse, combinadas sempre na produção de
4 unidades de x para 3 unidades de y. O modelo de programação linear pode ser estrutu-
rado para maximizar ou minimizar o resultado dessa expressão, o que no fundo significa que
estamos procurando valores de x e de y. É claro que o problema vai impor limites sobre as
quantidades x e y
2. A estrutura do problema é tal que existe, em geral, uma certa restrição de recursos, ou
impossibilidade de economias, de forma que nunca é possível obter um lucro, por exemplo,
tão grande quanto se queira, ou um custo, por seu turno, tão pequeno quanto se deseje. Às
vezes, seria ótimo se pudéssemos fabricar o máximo possível de dois produtos, desde que
existisse demanda ilimitada para ambos. No entanto, não temos matéria-prima suficiente
para isso, nem horas disponíveis de máquina, nem operários, e assim por diante. Há de se
buscar uma combinação ótima para se chegar ao melhor lucro possível, dadas as restrições
práticas impostas pelo problema.
Visto tudo isso, é possível perceber que um problema típico de programação linear possui
apresenta duas importantes partes:
• Uma expressão que se quer maximizar ou minimizar, chamada função objetivo. Nessa ex-
pressão surgem as variáveis fundamentais cuja quantidade será a solução do problema. Essas
variáveis são chamadas de variáveis de decisão.
• Um certo número de restrições, expressas na forma de equações ou inequações matemáticas,
que aparecem e são assim formuladas devido à configuração dos próprios dados do problema.
Essas restrições representam, dependendo do cao, limitações da situação real, como escassez
de recursos, limitações legais, etc.
Podemos enfim dizer que a idéia principal de um modelo de programação linear é maximizar
ou minimizar a função objetivo, ao mesmo tempo obedecendo a todas as restrições. Devemos nos
atentar que o nome linear que refere-se a característica da proporcionalidade, ou seja, tanto a
expressão que forma a função objetivo, quanto as restrições, devem ser expressas linearmente, ou
seja, todas as variáveis aparecem com expoente igual a unidade.
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 7
2.2 Diretrizes para a formulação de modelos de Progra-
mação Linear
Quando estivermos diante de um problema, que deverá ser formulado como um modelo de
programação linear, devemos ficar atentos aos parâmetros e às variáveis de decisão.
Parâmetros são os valores já fixados, fora do controle da pessoa que monta o modelo. São
valores que devemos aceitar como são. Fazem parte do problema, mas não estão em discussão.
Variáveis de decisão são grandezas que poderão assumir diversos valores, sendo que há uma
certa combinação de valores que irá maximizar ou minimizar a função objetivo, conforme seja o
caso. É essa combinação de valores que será a solução do problema de programação linear. Em
outras palavras, as variáveis de decisão aparecem tanto na função objetivo como nas restrições.
Os parâmetros, por sua vez, aparecem como coeficientes das variáveis de decisão ou como valores
máximos ou mínimos de grandezas que comporão o modelo. Essas variáveis de decisão serão
indicadas por letras como x,y,z,... ou X,Y,Z ou ainda por letras indexadas, como 𝑥1, 𝑥2, 𝑥3,etc.
A programação linear pode dividir-se ainda em programação linear inteira e programação linear
simples, a diferença entre elas se dá quando por algum motivo se exige que pelo menos uma das
variáveis de decisão deva assumir apenas valores inteiros aí teremos uma programação linear inteira,
quando não houver tal exigência, ou seja, todas as variáveis de decisão forem livres para assumir
qualquer valor, inteiros ou não, teremos uma programação linear simples. Deverá o leitor atentar-
se ao fato de que a grande maioria dos exemplos deste curso são de programação linear simples
não sendo necessário portanto enfatizar tal característica, assim o leitor só deverá considerar como
programação linear inteira aqueles que forem assim caracterizados expressamente no texto. É
importantíssimo ressaltar que não basta resolver um problema de Programação Linear Simples,
arredondando depois o valor de alguma variável que deveria ser inteira, pois na verdade, as soluções
em um e em outro caso são diferentes, obtidas por caminhos diferentes, e não necessariamente
levando a valores próximos.
Um problema de programação linear pode ter duas ou mais variáveis de decisão. Quando da
formulação de um problema, isto é, sua colocação na forma padronizada do modelo de programação
linear, muitas vezes o fato de o problema se mais complexo, com diversas variáveis de decisão, torna-
os mais interessante e mais desafiador. O problema maior acontece com a solução: um problema
com muitas variáveis de decisão obrigatoriamente deve ser solucionado por meio de computador.
Hoje em dia, isto não acarreta grandes dificuldades, já que existem programas de computador
capazes de solucionar o problema, o grande problema é que estes programas só resolvem problemas
já modelados, ou seja, com todos os dados já organizados, e isso talvez seja o maior desafio de
um estudante de PO, modelar casos de programação linear. Iniciaremos o estudo de Programação
Linear com casos que envolvem apenas duas ou três variáveis de decisão e por hora o método
de solucioná-los será o método gráfico, posteriormente veremos o método simplex que é a base da
Programação Linear.
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 8
2.3 Método Gráfico
2.3.1 Problema de Maximização
Exemplo 1
Uma fábrica produz dois produtos, A e B. Cada um deles deve ser processado por duas maqui-
nas, 𝑀1 e 𝑀2. Devido à programação de outros produtos, que também utilizam essas maquinas,
a máquina 𝑀1 tem 24 hores de tempo disponível para os produtos A e B, enquanto a máquina
𝑀2 tem 16 horas de tempo disponível. Para produzir uma unidade do produto A, gastam-se 4
horas em cada uma das máquinas 𝑀1 e 𝑀2. Pra produzir uma unidade do produto B, gastam-se
6 horas na máquina 𝑀1 2 2 horas na máquina 𝑀2. Cada unidade vendida do produto A gera um
lucro de R$ 80 e cada unidade do produto B, um lucro de R$ 60. Existe uma previsão máxima de
demanda para o produto B de 3 unidades, não havendo restrições quanto à demanda do produto
A. Deseja-se saber quantas unidades de A e de B devem ser produzidas, de forma a maximizar o
lucro e, ao mesmo tempo, obedecer a todas as restrições desse enunciado.
Solução
Em toda formulação de problemas de programação linear, é conveniente sintetizar os dados
por meio de uma tabela, que facilita a consulta e evita que fiquemos, a todo momento, lendo o
enunciado original.
Agora devemos determinar os elementos que comporão o modelo
Função objetivo:
Restrições:
Formulação Completa:
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 9
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 10
2.3.2 Problema de Minimização
Exemplo 2
A granja Cocoró quer misturar dois tipos de alimentos para criar um tipo especial de ração
para suas galinhas poedeiras. A primeira característica a ser atingida com a nova ração é o menor
preço possível por unidade de peso. Cada um dos alimentos contém os nutrientes necessários à
ração final (aqui chamados de nutrientes X,Y e Z), porém em proporções variáveis. Cada 100 g do
alimento 1, por exemplo, possuem 10 g do nutriente X, 50 g do nutriente Y e 40 g do nutriente Z.
O alimento 2, por sua vez, para cada 100 g, possui 20 g do nutriente X, 60 g do nutriente Y e 20
g do nutriente Z. Cada 100 g do Alimento 1 custam, para a Granja Cocoró, R$ 0,60 e cada 100 g
do Alimento 2 custam R$ 0,60. Sabe-se que a ração final deve conter, no mínimo, 2 g do nutrienteX, 64 g do nutriente Y e 34 g do nutriente Z. É preciso obedecer a essa composição, minimizando
ao mesmo tempo o custo por peso da nova ração.
Solução
Função objetivo:
Restrições:
Formulação Completa:
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 11
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 12
2.3.3 Formulação Padrão de Modelo de Programação Linear
De forma geral os modelos de programação linear aqui apresentados serão representados na
forma:
Problemas de Maximização
Maximizar 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + ... + 𝑐2𝑥𝑛
sujeito às restrições
𝑎11𝑥1 + 𝑎12𝑥2 + ... + 𝑎1𝑛𝑥𝑛 ≤ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ... + 𝑎2𝑛𝑥𝑛 ≤ 𝑏2
.
.
.
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ... + 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚
e
𝑥1, 𝑥2, ..., 𝑥𝑛 ≥ 0
Problemas de Minimização
Minimizar 𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + ... + 𝑐2𝑥𝑛
sujeito às restrições
𝑎11𝑥1 + 𝑎12𝑥2 + ... + 𝑎1𝑛𝑥𝑛 ≥ 𝑏1
𝑎21𝑥1 + 𝑎22𝑥2 + ... + 𝑎2𝑛𝑥𝑛 ≥ 𝑏2
.
.
.
𝑎𝑚1𝑥1 + 𝑎𝑚2𝑥2 + ... + 𝑎𝑚𝑛𝑥𝑛 ≥ 𝑏𝑚
e
𝑥1, 𝑥2, ..., 𝑥𝑛 ≥ 0
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 13
Exemplo 3
Resolva graficamente:
Maximizar 𝑍 = 4𝑥 + 6𝑦
Sujeito a
8𝑥 + 7𝑦 ≤ 56
𝑦 ≤ 5
𝑥 ≤ 4
𝑥, 𝑦 ≥ 0
Solução
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 14
Exemplo 4
Resolva graficamente:
Minimizar 𝑍 = 2𝑥 + 4𝑦
Sujeito a
5𝑥 + 5𝑦 ≥ 25
2𝑥 + 6𝑦 ≥ 18
𝑥 ≥ 2
𝑥, 𝑦 ≥ 0
Solução
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 15
2.4 Casos Especiais
Vejamos alguns casos especiais de programação linear
2.4.1 Restrições incompatíveis
A impossibilidade de solução, como também é chamado este caso especial, ocorre quando não há
solução que satisfaça ao mesmo tempo todas as restrições colocadas no modelo. Isso vale também
para as condições de não negatividade. Do ponto de vista gráfico, não será possível determinar
uma só região possível.
Como exemplo, vamos supor o seguinte problema:
Maximizar 𝑍 = 𝑥 + 𝑦
Sujeito a
4𝑥 + 3𝑦 ≤ 12
𝑦 ≥ 5
𝑥 ≥ 4
𝑥, 𝑦 ≥ 0
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 16
2.4.2 Solução sem fronteiras
Um problema de programação linear apresentará uma solução sem fronteiras se o valor da solu-
ção puder ser ser feito infinitamente grande, sem violar qualquer uma das restrições. Geralmente,
se isso acontecer, é muito provável que o problema tenha sido mal formulado. Afinal, não existem
lucros infinitos ou despesas que possam ser infinitamente pequenas.
Cumpre notar que o fato de a solução não ter fronteiras não impede que se determine grafica-
mente uma região possível. O que acontecerá é que a região possível irá se estender infinitamente
em uma dada direção. Como exemplo, consideremos o problema a seguir:
Maximizar 𝑍 = 4𝑥 + 𝑦
Sujeito a
𝑥 ≥ 2
𝑦 ≤ 3
𝑥, 𝑦 ≥ 0
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 17
2.4.3 Redundância
Uma restrição será redundante se sua presença em nada afetar a região permissível delimitada
pelas outras restrições. Uma restrição redundante, portanto, pode ser eliminada sem alterar o
problema original ou sua solução.
Consideremos como um exemplo de redundância o problema:
Maximizar 𝑍 = 3𝑥 + 2𝑦
Sujeito a
10𝑥 + 5𝑦 ≤ 50
𝑥 + 𝑦 ≤ 7
𝑦 ≤ 15
𝑥, 𝑦 ≥ 0
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 18
2.4.4 Soluções alternativas
Pode ser que um problema apresente duas ou mais soluções. Graficamente, isso ocorre quando
a família de retas da função objetivo é paralela a uma das restrições. Nesse caso, não haverá apenas
um ponto extremo objetivo.
Como exemplo deste caso, vejamos o seguinte problema
Maximizar 𝑍 = 4𝑥 + 12𝑦
Sujeito a
𝑥 + 3𝑦 ≤ 6
5𝑥 + 3𝑦 ≤ 15
𝑥, 𝑦 ≥ 0
Resolução Gráfica
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 19
2.5 Análise da sensibilidade
Até este ponto, consideramos que eram fixos todos os coeficientes que apareciam em um pro-
blema de programação linear. Assim eram constantes todos os coeficientes da função objetivo,
ou seja, todos os números que apareciam multiplicando pelas variáveis na função objetivo. Em
diversos problemas de maximização, esses coeficientes indicam lucros unitários ou algum tipo de
contribuição. A hipótese, portanto, é a de que esses lucros unitários são constantes.
Por sua vez, também estamos considerando constantes todos os coeficientes das restrições, o
que em um problema de maximização pode indicar quanto de cada recurso será despendido para
se elaborar uma simples unidade de um dado produto. Esses coeficientes são, por vezes, chamados
de coeficientes tecnológicos, já que, de certa forma, dependem do grau de tecnologia de que se
dispõe. Supor constantes os coeficientes tecnológicos implica que estamos considerando como fixo
um dado estado da tecnologia.
Finalmente, podemos também considerar fixos os lados direitos das restrições, ou LDRs. Nesse
caso, em problemas usuais de programação linear, estaremos considerando a quantidade total de
recursos disponíveis.
Ocorre que todos esses coeficientes, em um ambiente real, podem sofrer variações. Denomi-
namos análise de sensibilidade o estudo de como a solução ótima irá mudar, caso variem esses
coeficientes. Em um nível elementar da análise de sensibilidade, iremos considerar sempre o efeito
da variação isolada de um certo coeficiente, ou seja, não analisaremos o que acontece com a solução
ótima quando dois ou mais coeficientes varam em conjunto. A análise de sensibilidade neste estudo
ser mostrada por meio de gráficos.
Análise dos coeficientes da função objetivo
Consideremos o exemplo 1, que relatava o problema de produção dos produtos A e B, nas
máquinas 𝑀1 e 𝑀2 e cuja formulação era
Maximizar 𝑍 = 80𝑥 + 60𝑦
Sujeito a
4𝑥 + 6𝑦 ≤ 24
4𝑥 + 2𝑦 ≤ 16
𝑦 ≤ 3
𝑥, 𝑦 ≥ 0
a) Até que ponto podem variar os coeficientes da função objetivo sem que varie a solução ótima?
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 20
Resumindo, se a reta da função objetivo girar apenas dentro da área hachurada, o ponto
será conservado como solução, embora não única. Em outros termos, girar dentro da área hachu-
rada significa que há um coeficiente mínimo e outro máximo, tanto para a variável x como para a
variável y, entre os quais podem variar os coeficientes da função objetivo.
b) O que ocorre caso a restrição relativa às horas disponíveis na máquina 𝑀1 aumentem de 24
para 27?
Neste caso, pudemos observar que aumentando o número de horas disponíveis na maquina 𝑀1
de 24 para 27 horas, também aumenta a região permissível, exatamente da área do quadrilátero
, sendo o ponto a nova solução, com 𝑥 = 2, 63 e 𝑦 = 2, 75.
De modo similar, você leitor pode tentar outras variações no lado direito da restrição 4𝑥+6𝑦 ≤
24 ou das outras duas restrições.
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 21
2.6 Terminologias
Definição 2.6.1. Análise de sensibilidade é o estudo da sensibilidade da solução ótima aos dados
do modelo de programação linear montado pelo analista.
Definição 2.6.2. Coeficientes tecnológicos são os coeficientes das variáveis nas equações ou inequa-
ções das restrições. Os coeficientes tecnológicos representam a quantidade de recursos necessária
para produzir uma unidade da variável.
Definição 2.6.3. Condições de não negatividade: um conjunto de restrições que requer que cada
variável em um problema de programação linear seja não negativa, isto é, maior ou igual a zero.
Definição 2.6.4. Função objetivo é uma expressão matemática em que aparecem as variáveis de
decisão, a qual deverá ser maximizada ou minimizada.
Definição 2.6.5. Ponto extremo da região permissível: na solução gráfica, são os vértices da região
permissível delimitada por todas as restrições.
Definição 2.6.6. Programação linear é uma tecnica matemática usada para ajudar na alocação
mais efetiva de recursos
Definição 2.6.7. Região permissível é o conjunto de todas as soluções possíveis.
Definição 2.6.8. Restrição é a expressão matemática de um limite aplicável a uma dada variável
ou combinação de variáveis, expressa na forma de uma equação ou inequação.
Definição 2.6.9. Restrição redundante é qualquer restrição que não afete a região permissível,
isto é,uma restrição que pode ser removida sem afetar a região possível.
Definição 2.6.10. Solução sem fronteiras é a situação na qual o valor da solução pode aumentar
sempre, sem violar qualquer uma das restrições.
Definição 2.6.11. Solução ótima de um problema de programação linear é qualquer conjunto de
valores que, ao mesmo tempo, satisfaça todas as restrições e maximize (ou minimize) a função
objetivo, conforme for o caso.
Definição 2.6.12. Solução permissível é uma solução que obedeça ao mesmo tempo todas as
restrições
Definição 2.6.13. Soluções alternativas são quaisquer soluções que satisfaçam todas as restrições
e maximizem (ou minimizem) a função objetivo, conforme for o caso.
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 22
2.7 Exercícios Propostos
1. Na fabricação de dois de seus produtos, uma empresa utiliza dois equipamentos que limitam
a produção. Em um dado período de tempo, estão disponíveis 30 horas do equipamento 1
e 80 horas do equipamento 2. Para a fabricação de uma unidade do produto A, usa-se 1
hora do equipamento 1 e 2 horas do equipamento 2. Já para uma unidade do produto B, são
gastas 2 horas do equipamento 2. O equipamento 1 não toma parte na produção do produto
B. Por outro lado, uma unidade do produto A leva um lucro de R$ 150,00 enquanto cada
unidade do produto B gera um lucro de R$ 50,00. Pede-se: a) Formular o problema como
um modelo de programação linear, visando maximizar o lucro
b) Resolvê-lo graficamente
2. Uma empresa do ramo de confecções está considerando quanto deve produzir de seus dois
modelos de terno, denominados Executivo Master e Caibem, de forma a maximizar o lucro.
Será impossível fabricar quanto se queira de cada um dos modelos, porque existem limitações
nas horas disponíveis para a costura e o acabamento, as duas operações básicas na fabrica-
ção. No caso da costura, existem apenas 180 horas-máquina disponíveis, enquanto para o
acabamento, que é feito manualmente, haverá, no máximo, 240 homens-hora. Em termos de
lucro unitário e produção, os dois modelos apresentam as seguintes características:
Executivo Master
• Lucro unitário: R$ 120,00
• Horas-máquina de costura por unidade: 2
• Homens-hora de acabamento por unidade: 2
Caibem
• Lucro unitário: R$ 70,00
• Horas-máquina de costura por unidade: 1
• Homens-hora de acabamento por unidade: 4
Pede-se:
a) Formular o problema como um modelo de programação linear
b) Resolver graficamente o problema
3. Na fabricação de dois produtos, X e Y, as seguintes restrições são válidas quanto aos dois
recursos escassos que são utilizados:
𝑥 + 2𝑦 ≤ 80
2𝑥 + 2𝑦 ≤ 120, onde
x = número de unidades produzidas do produto X
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 23
y = número de unidades produzidas do produto Y
Sabe-se também que cada unidade do produto X fornece um lucro de R$ 20 e cada unidade
do produto Y leva a um lucro de R$ 30. Pede-se:
a) Formular o modelo de programação linear apropriado, visando maximizar o lucro
b) Resolver o problema graficamente
4. A WYNDOR GLASS CO. fabrica produtos de vidro de alta qualidade, entre os quais janelas
e portas de vidro. A empresa possui três fábricas industriais. As esquadrias de alumínio e
ferragens são feitas na Fábrica 1, as esquadrias de madeira são produzidas na Fábrica 2 e,
finalmente, a fábrica 3 produz o vidro e monta os produtos. Em consequência da queda nos
lucros, a direção decidiu modernizar a linha de produtos da empresa. Produtos não rentáveis
estão sendo descontinuados, liberando a capacidade produtiva para o lançamento de dois
novos produtos com grande potencial de venda.
Produto 1: uma porta de vidro de 2,5 m com esquadria de alumínio
Produto 2: uma janela duplamente adornada com esquadrias de madeira de 1,20 m x 1,80 m
O produto 1 requer 1 h da capacidade produtiva da Fábrica 1, 3 h da Fábrica 3 e nenhuma
da Fábrica 2. O produto 2 precisa das 2 h da capacidade produtiva da Fábricas 2, 2 h da
Fábrica 3 e nenhuma da Fábrica 1. A divisão de marketing concluiu que a empresa poderia
vender tanto quanto fosse possível produzir nessas fábricas. Entretanto, pelo fato de ambos
os produtos competirem pela mesma capacidade produtiva da Fábrica 3, não está claro qual
mix dos dois produtos será o mais lucrativo. A equipe de PO também concluiu que o tempo
de produção por lote , em horas, disponível por semana em horas em cada Fábrica para a
produção destes produtos é, 4 h na Fábrica 1, 12 h na Fábrica 2 e 18 h na Fábrica 3. A equipe
identificou o lucro por lote produzido de cada produto, sendo R$ 3.000,00 o lucro do produto
1 e R$ 5.000,00 o lucro do produto 2. De posse destes dados, se pede, determinar quais
devem ser as taxas de produção para ambos os produtos de modo a maximizar o lucro total,
sujeito as restrições impostas pela capacidade produtiva limitada disponível nas três fábricas.
(Cada produto será fabricado em lotes de 20, de modo que a taxa de produção é definida
como o número de lotes produzidos por semana.) É permitida qualquer combinação de taxas
de produção que satisfaça essas restrições, inclusive não produzir nada de um produto e o
máximo possível de outro.
5. Resolva graficamente:
Maximizar 𝑍 = 3𝑥 + 𝑦
Sujeito a
2𝑥 + 𝑦 ≤ 30
𝑥 + 4𝑦 ≤ 40
𝑥, 𝑦 ≥ 0
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 24
6. Resolva graficamente:
Maximizar 𝑍 = 𝑥 + 2𝑦
Sujeito a
𝑥 ≤ 3
𝑦 ≤ 5
2𝑥 + 2𝑦 ≤ 12
𝑥, 𝑦 ≥ 0
7. Resolva graficamente:
Minimizar 𝑍 = 2𝑥 + 𝑦
Sujeito a
𝑥 + 𝑦 ≥ 10
2𝑥 + 3𝑦 ≥ 14
𝑥, 𝑦 ≥ 0
8. Resolva graficamente:
Minimizar 𝑍 = 4𝑥 + 𝑦
sujeito a
2𝑥 + 2𝑦 ≥ 10
𝑥 + 6𝑦 ≥ 20
𝑥, 𝑦 ≥ 0
9. Em uma fábrica, existem três recursos em quantidades limitadas, os quais impõem limites às
quantidades que o podem ser produzidas de dois produtos, A e B. Existem 1.200 unidades
disponíveis do recurso 1, 400 unidades disponíveis do recurso 2 e 80 unidades disponíveis do
recurso 3. Por outro lado, o produto A proporciona um lucro unitário de R$ 100, contra R$
300 do produto B. Sabe-se também que:
1 unidade do produto A requer:
• 20 unidades do recurso 1
• 4 unidades do recurso 2
• nenhuma unidade do recurso 3
1 unidade do produto B requer:
• 20 unidades do recurso 1
• 20 unidades do recurso 2
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 25
• 4 unidades do recurso 3
Pede-se:
a) Colocar o problema como um modelo de programação linear
b) Resolver graficamente o problema
10. Considere novamente o exercício 1. Suponha que o equipamento 1 tenha agora 31 horas
disponíveis, em vez de 30, permanecendo inalterada a quantidade de horas disponíveis do
equipamento 2. Conserve também todos os demais dados. Pede-se:
a) Resolver graficamente o novo problema
b) Determinar o novo lucro total
c) Determinar quanto foi adicionado ao lucro pela 31ª hora disponível do equipamento 1
11. Novamente retornando ao exercício 1, suponha agora que a quantidade de horas disponí-
veis do equipamento 2 possa ser de 81 horas, permanecendo inalteradas todas as demais
quantidades do exercício. Pede-se
a) Resolver graficamente o novo problema
b) Determinar o novo lucro total
c) Determinar quanto foi adicionado ao lucro pela 81ª hora disponível do equipamento 2
12. Dada a tabela abaixo, Pede-se:
a) Formule o problema como um modelo de programação linear
b) Resolva graficamente o modelo
13. Dada a tabela abaixo, Pede-se:
Jorleanderson Maia
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 26
a) Formule o problema como um modelo de programação linear para minimizar o custo diário
por comissionário
14. Resolva utilizando o método gráfico
Maximizar 𝑍 = 2𝑥 + 𝑦
Sujeitos a
𝑦 ≤ 10
2𝑥 + 5𝑦 ≤ 60
𝑥 + 𝑦 ≤ 18
3𝑥 + 𝑦 ≤ 44
𝑥, 𝑦 ≥ 0
15. Resolva utilizando o método gráfico
Maximizar 𝑍 = 10𝑥 + 20𝑦
Sujeitos a
−𝑥 + 2𝑦 ≤ 15
𝑥 + 𝑦 ≤ 12
5𝑥 + 3𝑦 ≤ 45
𝑥, 𝑦 ≥ 0
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 27
16. A WorldLight Company produz dois tipos de luminárias (produtos 1 e 2) que requerem
tanto estruturas metálicas quanto componentes elétricos. A direção quer determinar quan-
tas unidades de cada produto devem ser produzidas de modo a maximizar o lucro. Para
cadaunidade do produto 1, são necessárias uma unidade de estrutura metálica e duas de
componentes elétricos. Para cada unidade do produto 2 são necessárias três unidades de es-
trutura metálica e duas unidades de componentes elétricos. A empresa possui 200 unidades
de estruturas metálicas e 300 unidades de componentes elétricos. Cada unidade do produto
1 fornece lucro de US$ 1 e cada unidade do produto 2 fornece lucros na seguinte base: até
60 unidades, US$ 2 de lucro e acima de 60 unidades não dá lucro nenhum.
a) Formule um modelo de programação linear para esse problema
b) Resolva-o pelo método gráfico
17. A Cia. de Seguros Primo está introduzindo duas novas linhas de produtos: seguro de risco
especial e hipotecas. O lucro esperado é de US$ 5 por unidade em um seguro de risco especial
e de US$ 2 por unidade nas hipotecas. A direção quer estabelecer cotas de vendas para as
novas linhas de modo a maximizar o lucro total esperado. As exigências, em termos de
trabalho, são as seguintes:
a) Formule um modelo de programação linear para esse problema
b) Use o método gráfico para solucionar esse problema
18. A empresa de manufatura Ômega descontinuou a produção de determinada linha de produtos
não lucrativa. Esse fato acabou criando considerável excesso de capacidade produtiva. A
direção está levando em conta a possibilidade de dedicar esse excesso de capacidade produtiva
para um ou mais produtos. Vamos chamá-los produtos 1 , 2 e 3. A capacidade disponível
nas máquinas que poderiam limitar a produção encontra-se resumida na tabela a seguir:
Jorleanderson Maia
Jorleanderson Maia
Jorleanderson Maia
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 28
O número de horas/maquina exigidas para cada unidade do respectivo produto é
O departamento de vendas sinaliza que o potencial de vendas para os produtos 1 e 2 excede
a taxa de produção máxima e que o potencial de vendas do produto 3 é de 20 unidades por
semana. O lucro unitário seria, respectivamente US$ 50, US$ 20 e US$ 25 para os produtos
1, 2 e 3. O objetivo é determinar quanto de cada produto a Ômega deveria produzir para
maximizar os lucros.
a) Formule um modelo de programação linear para este problema
19. Use o método gráfico para demonstrar que o modelo, a seguir, não tem nenhuma solução
viável.
Maximizar 𝑍 = 5𝑥 + 7𝑦
Sujeitos a
2𝑥 − 𝑦 ≤ 1
−𝑥 + 2𝑦 ≤ −1
𝑥, 𝑦 ≥ 0
20. Use o método gráfico para solucionar os problemas seguintes:
a) Minimizar 𝑍 = 15𝑥 + 20𝑦
Sujeitos a
𝑥 + 2𝑦 ≥ 10
2𝑥 − 3𝑦 ≤ 6
𝑥 + 𝑦 ≥ 6
𝑥, 𝑦 ≥ 0
b) Minimizar 𝑍 = 3𝑥 + 2𝑦
Sujeitos a
4𝑥 + 𝑦 ≤ 12
𝑥 − 𝑦 ≥ 2
𝑥, 𝑦 ≥ 0
CAPÍTULO 2. INTRODUÇÃO À PROGRAMAÇÃO LINEAR 29
21. Considere o medelo
Minimizar 𝑍 = 40𝑥 + 50𝑦
2𝑥 + 3𝑦 ≥ 30
𝑥 + 𝑦 ≥ 12
2𝑥 + 𝑦 ≥ 20
𝑥, 𝑦 ≥ 0
a) Use o método gráfico para solucionar esse modelo
b) Como a solução ótima muda se a função objetivo for alterada para 𝑍 = 40𝑥+70𝑦? (Utilize
o método gráfico)
c) Como muda a solução caso a terceira restrição seja alterada para 2𝑥 + 𝑦 ≥ 15? (Utilize o
método gráfico)
22. Edmundo adora bifes e batatas. Assim, decidiu entrar em uma dieta rígida usando somente
esses alimentos (além de alguns líquidos e suplementos vitamínicos) em todas as suas re-
feições. Ele percebe que essa não é a dieta mais saudável e, portanto, quer certificar-se de
que se alimenta das quantidades corretas desses dois tipos de alimentos, a fim de atender
a determinados requisitos nutricionais. Ele obteve as informações nutricionais e de custo
mostradas no alto da tabela a seguir
Edmundo quer determinar o número de refeições diárias (pode ser fracionário) com bifes e
batatas que atenderá a essas exigências a um custo mínimo.
a) Formule um modelo de programação linear para este problema
b) Utilize o método gráfico para solucionar esse modelo
Capítulo 3
Método Simplex
O simplex é uma metodologia que envolve uma sequência de cálculos repetitivos por meio
dos quais é possível chegar à solução de um problema de programação linear. Essa sequência de
cálculos recebe o nome de algoritmo. Embora simples, os cálculos são tediosos, e para problemas
com três ou mais variáveis de decisão, pode-se facilmente errar em alguma das etapas, invalidando
assim todos os esforços. Rapidamente foram elaborados programas de computador para trabalhar
com o algorítimo. Os alunos devem, no entanto, entender qual a lógica por trás do cálculo, para
que não tenham a impressão de que o Simplex é apenas uma sequência sem sentido (e difícil
de reter na memória) de operações numéricas simples. O desejável seria que todos os estudiosos
de programação tivessem acesso a um microcomputador, para que pudessem concentrar-se na
estruturação (formulação) dos problemas, atividade que exige intelectualmente muito mais do
aluno, sendo bem mais estimulante. Por esse motivo, vamos nos restringir a exemplos abordando
problemas simples, com duas ou, no máximo, três variáveis de decisão.
Antes de passar ao Simplex, ou à sequência de cálculos que o constitui, vejamos como, na
verdade ele funciona. Comecemos com os conceitos de variável de folga e de solução básica de um
problema de programação linear
3.1 Variáveis de folga e soluções básicas
Para o que se segue, vamos nos apoiar no exemplo de maximização do capítulo anterior (pg.
8). Queríamos maximizar o lucro devido a venda de dois produtos, A e B, sob três restrições,
sendo duas delas representadas por horas disponíveis em duas máquinas, 𝑀1 e 𝑀2, a a terceira
representada por uma limitação da demanda do produto B. A formulação completa do problema
era a seguinte:
Maximizar 80𝑥 + 60𝑦
sujeito a
4𝑥 + 6𝑦 ≤ 24 (restrição de horas disponíveis ma máquina 𝑀1)
4𝑥 + 2𝑦 ≤ 16 (restrição de horas disponíveis na máquina 𝑀2)
0𝑥 + 1𝑦 ≤ 3 (restrição da demanda máxima do produto B)
𝑥, 𝑦 ≥ 0
30
CAPÍTULO 3. MÉTODO SIMPLEX 31
É possível transformar as inequações (que refletem as restrições) em equações, acrescentando
novas variáveis a cada uma delas. Na restrição de horas disponíveis na máquina 𝑀1, por exemplo,
podemos ter:
4𝑥 + 6𝑦 + 𝑠1 = 24
onde a variável 𝑠1 foi acrescentada. Essa nova variável é chamada de variável de folga (slack em
inglês, daí a designação pela letra s). O nome folga é dado porque muitas vezes pode-se associar
essa variável a recursos não utilizados ou não aproveitados. No caso da restrição que estamos
analisando, 𝑠1 representa o total de horas disponíveis na máquina 𝑀1, não utilizado. Por exemplo,
se 𝑥 = 0 e 𝑦 = 3, tem-se:
4(0) + 6(3) + 𝑠1 = 24
𝑠1 = 24 − 18 = 6 (3.1.1)
Nesse caso, ou seja, para esse ponto extremo, 𝑠1 indica que 6 horas disponíveis na máquina 𝑀1
não serão utilizadas. Claramente, tem-se sempre 𝑠1 ≥ 0.
Acrescentemos duas outras variáveis de folga às duas inequações seguintes:
4𝑥 + 2𝑦 + 𝑠2 = 16
0𝑥 + 1𝑦 + 𝑠3 = 3
Nesses casos, 𝑠2 representa horas disponíveis na máquina 𝑀2 e não utilizadas, mas 𝑠3 representa
demanda possível do produto B, não atendida (O máximo de unidades possíveis do produto B era
3, lembre-se). Tomando o mesmo ponto extremo do caso anterior temos:
CAPÍTULO 3. MÉTODO SIMPLEX 32
Fica claro ao leitor que também 𝑠2 ≥ 0 e 𝑠3 ≥ 0, ou ainda, de uma forma geral, que qualquer
variável de folga deve ser maior ou igual a zero.
A rigor, quando introduzimos as variáveis de folga e transformamos as inequações em equações,
devemos colocá-las em todas as inequações existentes e também na função objetivo. Quando uma
variável de folga não aparecer em uma inequação, nós a colocamos com coeficiente zero. No caso da
função objetivo, todas as variáveis de folga devem aparecer com coeficiente zero. Temos, portanto,
o seguinte quadro geral de formulação:
Maximizar 𝑍 = 80𝑥 + 60𝑦 + 0𝑠1 + 0𝑠2 + 0𝑠3
Sujeito a
4𝑥 + 6𝑦 + 1𝑠1 + 0𝑠2 + 0𝑠3 = 24
4𝑥 + 2𝑦 + 0𝑠1 + 1𝑠2 + 0𝑠3 = 16
0𝑥 + 1𝑦 + 0𝑠1 + 0𝑠2 + 1𝑠3 = 3
𝑥, 𝑦 ≥ 0
Embora isso não aconteça aqui, é bom notar que o Simplex exige que o segunda lado das
equações não sejam um número negativo. Veremos mais a frente como proceder quando este for o
caso. O leitor há de notar que chegamos a um sistemaindeterminado, pois temos cinco incógnitas
(𝑥, 𝑦, 𝑠1, 𝑠2, 𝑠3) e apenas três equações. Sempre que o número 𝑞 de equações (𝑞 = 3, no nosso caso),
o sistema será indeterminado, ou seja, não poderemos chegar aos valores finais das variáveis.
Por outro lado, se fixarmos os valores de (𝑘 − 𝑞) variáveis, o número de variáveis desconhecidas
torna-se igual ao número de equações, e o sistema torna-se determinado, ou seja, será possível
determinar o valor das variáveis desconhecidas restantes. No nosso exemplo, deveríamos fizar o
valor de duas variáveis, de modo a obter o valor das outras três. Atendendo-nos ao exemplo,
vamos supor que fixamos as variáveis, duas a duas, como solução igual a zero. As duas variáveis
igualadas a zero chamam-se uma solução não básica ao problema de programação linear. Por
sua vez, as 𝑞 variáveis restantes, calculadas, são chamadas de uma solução básica ao problema de
programação linear. Além disso, uma solução básica pode ser possível ou não, dependendo dos
valores encontrados para as variáveis obedecerem ou nais às restrições.
Vamos analisar o que acontece com os valores das cinco variáveis nos pontos extremos da região
possível para o problema de maximização anterior:
CAPÍTULO 3. MÉTODO SIMPLEX 33
Repare o leitor que, em qualquer um dos pontos extremos, existem sempre duas variáveis com
valores nulos. Em termos gerais, podemos enunciar: Em um problema de programação linear com
𝑘 incógnitas e 𝑞 equações, nos pontos extremos da região possível tem-se sempre (𝑘 − 𝑞) incógnitas
com valor igual a zero.
É essa propriedade que fornece o modus operandi do Simplex, pois a solução encontra-se em
um dos pontos extremos. Fazendo-se conjuntos diferentes de (𝑘 − 𝑞) incógnitas iguais a zero,
determinam-se soluções básicas possíveis. Com os valores das variáveis assim obtidos, determina-
se o valor correspondente da função objetivo e, portanto, chega-se à solução ótima. É o que
explicaremos um pouco mais na seção seguinte, quando veremos (intuitivamente) como funciona
o Simplex.
3.2 Como opera o Simplex
Sabemos que o Simplex é tão-somente uma sequência de cálculos simples levando à solução
de um problema de programação linear. É interessante, porém, ter uma visão geral de como
progridem esses cálculos, o que pode ser feito com auxilio da região permissível delimitada pelas
restrições. Essa região é delimitada por pontos, em cada um desses pontos, o Simplex fará uma
interação, até chegar à solução do problema. O Simplex começa sempre testando a origem como
solução. Na origem 𝑥 = 0 e 𝑦 = 0, e o valor da função objetivo também é zero. A origem não é
solução, mas é um ponto de partida para o Simplex.
Da origem, o Simplex passa aos demais pontos, sempre fazendo uma escolha pelo melhor
caminho, até chegar ao ponto ótimo, onde encerram-se as iterações, já que o valor da função
objetivo é máximo nesse ponto.
A técnica implica a geração de uma série de cálculos que são colocados em forma de tabela.
Cada tabela gerada recebe o nome de tableau. Cada interação do Simplex (ou seja, cada teste de
um ponto extremo) corresponde à criação de um tableau. O tableau é construido de tal forma que,
inspecionado-se sua linha mais baixa, é possível dizer se a solução que ele representa é ou não a
melhor possível.
O primeiro tableau corresponde à origem, em que o valor da função objetivo é zero. Melhora-
se essa solução, passando-se a outro ponto extremo da região permissível. Havendo outro ponto
extremo em que a solução seja ainda melhor, para lá se deslocarão os cálculos, e assim por diante,
até que a melhor solução possível seja encontrada.
CAPÍTULO 3. MÉTODO SIMPLEX 34
3.2.1 Rotina de cálculos do Simplex
1. Monta-se um tableau inicial que corresponde a origem;
2. Esse primeiro tableau é transformado em um segundo, que apresenta uma solução melhorada,
por meio de uma série de cálculos;
3. Esse procedimento se repete até que se chegue a um tableau que reflita a solução ótima
4. Quando da criação de cada tableau, existe um teste para verificar se a solução ótima foi ou
não atingida
Passemos agora a um exemplo simples, em que o leitor poderá acompanhar, passo a passo, a
montagem dos tableaux e as interações
3.3 Simplex: Maximização
Em um primeiro momento, vamos ilustrar a sequência de cálculos do Simplex usando um
exemplo que irá levar a dois tableaux apenas. O primeiro tableau, ou tableau inicial, como recorda
o leitor, corresponde à origem, com 𝑥 = 𝑦 = 0. O problema tratado é de maximização, apenas com
restrições do tipo ≤; veremos depois como são tratados outros tipos de restrições (≥ ou meramente
=) e como ledar com problemas de minimização.
Consideremos o seguinte problema de maximização:
Maximizar 𝑍 = 𝑥 + 2𝑦
Sujeito a
3𝑥 + 4𝑦 ≤ 24
5𝑥 + 2𝑦 ≤ 20
𝑥, 𝑦 ≥ 0
O tableau inicial parte do problema colocado na forma geométrica, como veremos a seguir.
3.3.1 Construindo o tableau inicial
Vamos colocar o problema em forma genérica, transformando as inequações em equações, com
a ajuda das variáveis de folga:
3𝑥 + 4𝑦 + 1𝑠1 + 0𝑠2 = 24
5𝑥 + 2𝑦 + 0𝑠1 + 1𝑠2 = 20
A colocação de coeficientes zero para 𝑠2 na primeira equação se 𝑠1 na segunda, respectivamente,
não é por acaso. Os coeficientes nulos estarão presentes no primeiro tableau, e é conveniente que
estejam evidenciados nas equações.
É preciso também alterar a função objetivo (alterar na sua forma, não na substância) para
incorporar as novas variáveis de folga. Tanto 𝑠1 como 𝑠2 devem aparecer na função objetivo, com
CAPÍTULO 3. MÉTODO SIMPLEX 35
coeficientes nulos. A nova formulação (completa) que deverá ser a base para o primeiro tableau é
a seguinte:
Maximizar 𝑍 = 𝑥 + 2𝑦 + 0𝑠1 + 0𝑠2
Sujeito a
3𝑥 + 4𝑦 + 1𝑠1 + 0𝑠2 = 24
5𝑥 + 2𝑦 + 0𝑠1 + 1𝑠2 = 20
𝑥, 𝑦 ≥ 0
O leitor irá reparar que o problema está escrito em uma forma tal que facilita bastante a
montagem do primeiro tableau, que passaremos agora a construir, passo a passo. Uma parte desse
tableau é construída tomando-se os coeficientes como aparecem na formulação, distribuídos da
forma a seguir, que configura um aspecto parcial do primeiro tableau:
Figura 3.1: Início da construção do primeiro tableau (ainda parcial)
Analisemos a Figura 3.1, que representa quatro linhas distintas. Na primeira delas estão listadas
as contribuições de cada variável à função objetivo, dadas pelos coeficientes dessas variáveis na
própria função objetivo. Como 𝑠1 e 𝑠2 em nada contribuem, aparecem com coeficientes zero, como
já foi visto.
A segunda linha é uma espécie de "linha guia", pois lista os elementos básicos que constituem
o tableau. Da esquerda para a direita, aparece primeiro 𝐶𝑗, que irá mostrar a contribuição, para a
função objetivo, das variáveis presentes na solução, ou seja, aquelas que estão sendo testadas. No
caso da Figura 3.1, os dois valores de 𝐶𝑗 são iguai a zero (ver a coluna de 𝐶𝑗), pois correspondem
a 𝑠1 e 𝑠2. Ainda na segunda linha, vem em seguida a coluna de "Variáveis na solução", que irá
indicar quais as variáveis que compõem na solução presente, no caso as variáveis de folga, 𝑠1 e 𝑠2,
por onde se começa a construção do primeiro tableau.
A segunda linha lista, em seguida, as variáveis que aparecem na função objetivo e nas restrições,
ou seja, 𝑥, 𝑦, e as variáveis de folga, 𝑠1 e 𝑠2. A coluna 𝑏𝑗 indica o lado direito das restrições, e
a relação 𝑏𝑗
𝑎𝑖𝑗
indica um cálculo intermediário na sequência de cálculos do Simplex, cuja utilidade
será vista mais adiante.
Note o leitor que, na Figura 3.1, os números que aparecem nas colunas de 𝑥, 𝑦, 𝑠1, 𝑠2 e 𝑏𝑗 são
copiados exatamente das restrições, ou seja, são os coeficientes das variáveis e os valores do lado
direito das restrições. Como o tableau inicial corresponde a 𝑥 = 𝑦 = 0, ou seja, à origem dos eixos
CAPÍTULO 3. MÉTODO SIMPLEX 36
𝑥, 𝑦, os valores de 𝑠1 e 𝑠2, lidos diretamente na coluna 𝑏𝑗, representam recursos ociosos, que não
estão sendo usados.
Falta ainda uma parte a acrescentar na Figura 3.1 para que se complete o primeiro tableau.
Duas linhasserão ainda colocadas, a linha 𝑍 e a linha 𝐶 − 𝑍. A linha 𝑍 terá seus valores nas
colunas 𝑥, 𝑦, 𝑠1, 𝑠2 e 𝑏𝑗. Dada uma linha qualquer, correspondente a uma dada variável, o valor
da linha 𝑍 nessa coluna indica a redução na função objetivo que iria ocorrer se uma unidade da
variável fosse acrescentada à solução. O valor da linha 𝐶 − 𝑍, sob uma dada coluna, indica o
acréscimo potencial à função objetivo se uma unidade da variável fosse acrescentada à solução.
Embora, em nosso exemplo, para o tableau inicial a linha 𝑍 seja uma linha só de zeros, é útil
enunciar uma regra geral para usa contrução e aplicá-la desde o começo. Para calcular a linha 𝑍,
partimos das linhas que representam as variáveis na solução - em nosso caso presente, as linhas
de 𝑠1 e 𝑠2. Multiplicam-se os coeficientes das variáveis e os lados direitos das restrições, em cada
coluna, pelos valores 𝑐𝑗 correspondentes que se encontram à esquerda e somam-se os produtos.
Essas somas, coluna a coluna, constituem a linha 𝑍. Vejamos:
Importante: a soma sob a coluna 𝑏𝑗, na linha 𝑍, indica sempre o valor da função objetivo
associado com o tableau. Sabíamos já que, no caso do primeiro tableau, esse valor era igual a zero,
pois 𝑥 = 𝑦 = 0.
Para calcular a linha 𝐶 − 𝑍, em cada coluna, subtraímos a linha 𝑍, coluna a coluna, dos
coeficientes das variáveis na função objetivo:
Podemos agora completar nosso tableau inicial, representado Figura 3.2
Dado que o tableau está completo, segue-se a pergunta: como saber se a solução que ele
representa é a solução ótima? Em outras palavras, como saber se a solução 𝑥 = 𝑦 = 0 é ótima?
Regra para teste da solução: se na linha 𝐶 − 𝑍 os valores são todos nulos ou negativos, então
a solução ótima foi encontrada. A inspeção da linha 𝐶 − 𝑍 revela que existem ainda dois valores
positivos; logo, devemos continuar a caminho do segundo tableau, rumo a uma nova solução.
CAPÍTULO 3. MÉTODO SIMPLEX 37
Figura 3.2: Tableau inicial, completo
3.3.2 Construindo o segundo tableau
O segundo taleau começa com a consideração de qual variável fornece, isoladamente, a maior
contribuição à função objetivo. Basta, para tanto, inspecionar a linha 𝐶 − 𝑍 que acabamos de
construir, pois ela mostra, coluna a coluna, a contribuição de cada unidade da variável respectiva
à função objetivo. Claramente, a variável 𝑦 é a que oferece essa maior contribuição, com o valor
2. Isso quer dizer que, a cada unidade de 𝑦 acrescida à solução, a função objetivo crescerá duas
unidades.
Na terminologia da programação linear, diz-se que, nesse caso, 𝑦 é a "variável que entra"no
tableau, o que se dará à custa de outra "variável que sai". É aqui que entra o calculo 𝑏𝑗/𝑎𝑖𝑗. Para
descobrir a "variável que sai", divide-se cada valor 𝑏𝑗 pelo valor correspondente (na mesma linha)
na coluna da variável que entra, 𝑦. A linha em que aparecer o menor coeficiente indica a variável
que irá sair. Veja o leitor os cálculos na Figura 3.2.
Quem deverá sair, portanto, é a variável 𝑠1, pois apresenta a menor relação 𝑏𝑗/𝑎𝑖𝑗 (24/4=6).
Novos valores deverão ser determinados, tanto para a linha da variável que sai como para as
linhas das outras variáveis (em nosso tableau, há apenas mais uma linha, a da variável 𝑠2). A linha
da variável que sai recebe o nome de linha principal.
Determinação da nova linha principal
O número que aparece na intersecção da coluna da variável que entra (y) com a linha principal,
da variável que sai (𝑠1), é chamado de elemento pivô e tem importante papel. Em nosso caso, esse
elemento vale 4. Para obter os novos valores da linha principal, todos os valores da antiga linha
principal são divididos pelo pivô.
CAPÍTULO 3. MÉTODO SIMPLEX 38
Determinação da nova linha da variável s2
A variável 𝑠1 saiu do tableau, entrando em seu lugar a variável 𝑦. Encontramos já os novos
valores da linha principal e vamos agora determinar novos valores para a outra variável, que
permaneceu no tableau, ou seja, 𝑠2. Em primeiro lugar, determinemos o número que se encontra
na intersecção da linha da variável 𝑠2 com a coluna da variável que entrou no tableau (𝑦). Esse
número é 2. Procedimento para definir a nova linha 𝑠2:
a) multiplicar cada valor da nova linha principal (já determinada) pelo número encontrado no
cruzamento referido (número 2):
b) os valores resultantes são agora subtraídos da antiga linha de 𝑠2:
Até o momento, o segundo tableau, que não está mais completo, tem o seguinte aspecto:
CAPÍTULO 3. MÉTODO SIMPLEX 39
Figura 3.3: Aspecto parcial do segundo tableau
Para completar o segundo tableau, precisamos das linhas 𝑍 e 𝐶 − 𝑍. A linha 𝑍 ficará assim:
A linha 𝐶 − 𝑍 ficará, portanto:
Estamos agora em condições de apresentar o segundo tableau completo, fa Figura 3.4:
Figura 3.4: O segundo tableau, completo
CAPÍTULO 3. MÉTODO SIMPLEX 40
A inspeção da linha 𝐶 − 𝑍 nos indica que encontramos a solução ótima, já que todos os valores
são nulos ou negativos. Observando a coluna 𝑏𝑗, o leitor perceberá que
𝑥 = 0 (pois 𝑥 não aparece)
𝑦 = 6
e o valor da função objetivo é 12.
Façamos um exercício complementar útil. Vamos substituir os valores de 𝑥 = 0 e 𝑦 = 6 nas
restrições:
3𝑥 + 4𝑦 + 1𝑠1 = 24
3(0) + 4(6) + 1𝑠1 = 24
24 + 1𝑠1 = 24, 𝑜𝑢 𝑠1 = 0 (𝑛ã𝑜 ℎá 𝑟𝑒𝑐𝑢𝑟𝑠𝑜𝑠 𝑜𝑐𝑖𝑜𝑠𝑜𝑠 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑡𝑒𝑠 𝑎 𝑠1)
e também
5𝑥 + 2𝑦 + 1𝑠2 = 20
5(0) + 2(6) + 1𝑠2 = 20
12 + 1𝑠1 = 20, 𝑜𝑢 𝑠2 = 8 (𝑒𝑥𝑖𝑠𝑡𝑒𝑚 8 𝑢𝑛𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑟𝑒𝑐𝑢𝑟𝑠𝑜𝑠 𝑜𝑐𝑖𝑜𝑠𝑜𝑠 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑒𝑛𝑡𝑒𝑠 𝑎 𝑠2)
Pode-se notar que as restrições foram obedecidas, embora existam 8 unidades de recursos não
aproveitados, incorporadas pela variável de forga 𝑠2.
Vejamos a seguir a resolução gráfica deste problema que acabamos de solucionar pelo Simplex.
Com isso o leitor poderá observar como o Simplex operou nesse caso. A região possível é determi-
nada pelo quadrilátero OPQR. Inicialmente foi feito o teste no ponto O, a origem, com a solução
𝑥 = 0 e 𝑦 = 0. Em seguida, fomos movidos diretamente para o ponto P, onde 𝑥 = 0 e 𝑦 = 6, que
é a solução ótima, encontrada com apenas duas interações ( dois tableaus).
CAPÍTULO 3. MÉTODO SIMPLEX 41
Exercício Resolvido
1. Resolva pelo método Simplex
Maximizar 𝑍 = 3𝑥1 + 5𝑥2
Sujeito a
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1, 𝑥2 ≥ 0
CAPÍTULO 3. MÉTODO SIMPLEX 42
CAPÍTULO 3. MÉTODO SIMPLEX 43
3.4 Restrições com lado direito negativo
Como o tableau exige que o lado direito das restrições seja um número positivo, sempre que
isso não ocorrer, deveremos fazer uma intervenção. Considere os leitor os três casos a seguir:
3𝑥 − 7𝑦 ≤ −12 (Caso A)
−2𝑥 + 3𝑦 ≥ −8 (Caso B)
−2𝑥 − 5𝑦 = −9 (Caso C)
A regra básica é: para eliminar o lado direito negativo, multiplique ambos os lados da restrição
por (-1) e inverta o símbolo de desigualdade, nos casos A e B. No caso C, tratando-se de uma
igualdade, basta fazer a multiplicação por (-1) e conservar a igualdade. Assim, temos, fazendo as
operações indicadas:
−3𝑥 + 7𝑦 ≥ 12
2𝑥 − 3𝑦 ≤ 8
2𝑥 + 5𝑦 = 9
3.5 Simplex: Minimização
Capítulo 4
Title
44
Capítulo 5
Respostas dos Exercícios Propostos
5.1 Exercícios Propostos 2.7
1.
2.
3.
4. (𝑥1, 𝑥2) = (2, 6)
5.
6.
7.
8.
9.
10.
11.
12. a) Minimizar 𝑍 = 0, 4𝑥1 + 0, 5𝑥2
sujeito a
0, 3𝑥1 + 0, 1𝑥2 ≤ 2, 7
0, 5𝑥1 + 0, 5𝑥2 = 6
0, 6𝑥1 + 0, 4𝑥2 ≥ 6
𝑥1𝑒𝑥2 ≥ 0
b) (152 ,
9
2)
45
CAPÍTULO 5. RESPOSTAS DOS EXERCÍCIOS PROPOSTOS 46
13. Minimizar 𝑍 = 170𝑥1 + 160𝑥2 + 175𝑥3 + 180𝑥4 + 195𝑥5
sujeito a
𝑥1 ≥ 48 (6h - 8h)
𝑥1 + 𝑥2 ≥ 79 (8h - 10h)
𝑥1 + 𝑥2 ≥ 65 (10h - 12h)
𝑥1 + 𝑥2 + 𝑥3 ≥ 87 (12h - 14h)
𝑥2 + 𝑥3 ≥ 64 (14h - 16h)
𝑥3 + 𝑥4 ≥ 73 (16h - 18h)
𝑥3 + 𝑥4 ≥ 82 (18h - 20h)
𝑥4 ≥ 43 (20h - 22h)
𝑥4 + 𝑥5 ≥ 52 (22h - 24h)
𝑥5 ≥ 15 (24h - 6h)
𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
14. (𝑥1, 𝑥2) = (13, 5); 𝑍 = 31
15.
16.
17.
18. 𝑥1 = 26, 19, 𝑥2 = 54, 76, 𝑥3 = 20; 𝑍 = 2.904, 76
19.
20.
21.
22.
Bibliografia
1 [1] MOREIRA, D. A. Pesquisa pperacional - curso introdutorio2. ed. Sao Paulo, Cengage Lear-ning, 2010
2 [2] GOLDBARG, M. C. Otimizacao combinatoria e programacao linear: modelos e algoriti-
mos.Rio de Janeiro, Campos, 2000
3 [3] HILLIER, F. S.,LIEBERMAN, G. J. Introducao a pesquisa operacional.9. ed. Porto Alegre,
AMGH, 2013
4 [4] TAHA, H. A. Pesquisa operacional: uma visao geral.8. ed. São Paulo, Pearson Prentice Hall,
2008
5 [5] ANDRADE, E. L, Introducao a pesquisa operacional.3. ed. Rio de Janeiro, LTC, 2004
6 [6] EHRLICH, P. J. Pesquisa operacional - curso introdutorio.Sao Paulo, Atlas, 1991
	Introdução à Pesquisa Operacional
	Introdução à Programação Linear
	Características de um modelo de Programação Linear
	Diretrizes para a formulação de modelos de Programação Linear
	Método Gráfico
	Problema de Maximização
	Problema de Minimização
	Formulação Padrão de Modelo de Programação Linear
	Casos Especiais
	Restrições incompatíveis
	Solução sem fronteiras
	Redundância
	Soluções alternativas
	Análise da sensibilidade
	Terminologias
	Exercícios Propostos
	Método Simplex
	Variáveis de folga e soluções básicas
	Como opera o Simplex
	Rotina de cálculos do Simplex
	Simplex: Maximização
	Construindo o tableau inicial
	Construindo o segundo tableau
	Restrições com lado direito negativo
	Simplex: Minimização
	Title
	Respostas dos Exercícios Propostos
	Exercícios Propostos 2.7