Pesquisa Operacional_Unidade 2

Prévia do material em texto

unidade 
2
Guilherme Corrêa Gonçalves
Ricardo Buneder
(Orgs.)
OPERACIONAL
Pesquisa
Programação Linear e 
Método/Algoritmo Simplex
Prezado estudante,
Estamos começando uma unidade desta disciplina. Os textos que a compõem foram 
organizados com cuidado e atenção, para que você tenha contato com um conteúdo 
completo e atualizado tanto quanto possível. Leia com dedicação, realize as atividades e 
tire suas dúvidas com os tutores. Dessa forma, você, com certeza, alcançará os objetivos 
propostos para essa disciplina.
OBJETIVO GERAL 
Entender os principais conceitos relacionados à Programação Linear e aplicar o 
modelo Simplex.
OBJETIVOS ESPECÍFICOS 
• Identificar e modelar problemas de tomada de decisão sobre a alocação de recursos 
utilizando Programação Linear;
• Resolver problemas de Programação Linear por meio do algoritmo Simplex.
QUESTÕES CONTEXTUAIS
1. Como alocar os recursos empresariais nas inúmeras atividades presentes em 
uma organização a fim de obter o melhor resultado possível?
2. Você já ouviu falar em Programação Linear? 
3. Será que esse conceito está relacionado à programação de computadores?
4. E função linear, você conhece esse conceito?
5. A expressão “solução ótima” é familiar para você? 
6. E quanto a “modelo de otimização”, você já ouviu falar ou sabe como pode ser 
utilizado em uma empresa? 
unidade 
2
PESQUISA OPERACIONAL | Ricardo Buneder40
2.1 Introdução
Nesta segunda Unidade da disciplina de Pesquisa Operacional veremos os 
conceitos e aplicações relacionados à Programação Linear e ao método/algoritmo 
Simplex. Na área da gestão, é muito comum termos de decidir em relação à alocação 
ótima de recursos escassos para a realização de atividades e, para tal, faz-se uso da 
técnica de Programação Linear (PL). Ótimo, nesse caso, diz respeito à melhor solução 
possível, ou seja, não há um valor melhor que o encontrado (pode haver outros tão bons 
quanto, mas não melhores).
E por que os recursos utilizados pelas empresas são ditos escassos? Colin (2013) 
afirma que o termo escasso está relacionado à existência finita dos recursos, por mais 
abundantes que sejam. Por fim, segundo esse mesmo autor, as atividades têm a ver com 
aquelas relacionadas à fabricação de produtos, à mistura de substâncias, ao atendimento 
ao público, ao transporte e armazenagem de mercadorias etc.
Nesta Unidade também abordaremos o método/algoritmo Simplex, utilizado para 
a determinação da solução ótima de um problema de programação linear e que, de acordo 
com Longaray (2013), em certas circunstâncias, permite concluir se esse problema tem 
múltiplas soluções, é inviável ou ilimitado. Feita esta breve introdução, convido você 
para, juntos, desbravarmos esses tópicos. 
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 41
2.2 Programação Linear
Conforme vimos na introdução desta Unidade, a Programação Linear (PL) é 
uma ferramenta da Pesquisa Operacional (PO) que utiliza modelos matemáticos para 
a resolução de problemas de alocação ótima de recursos escassos. O termo “linear” diz 
respeito ao fato de que todas as funções matemáticas do modelo são, obrigatoriamente, 
lineares. Outro aspecto importante a lembrar relaciona-se ao fato que, segundo Santos 
(2007), programação, nesse caso, não se refere à programação de computadores e, sim, 
ao planejamento das atividades que conduzem a um resultado ótimo. Ou seja, àquele que 
atenda, da melhor forma possível, a um determinado objetivo. Nesse sentido, prossegue 
esse autor dizendo que “[...] qualquer problema cujo modelo matemático se enquadre na 
forma geral de um modelo de PL, é um problema de programação linear”. (p. 121).
Cabe salientar que, de acordo com Colin (2013), uma função f (x1, x2, ... xn) das 
variáveis x1, x2, ... , xn, é uma função linear se for do tipo f (x1, x2, ... , xn) = c1x1 + 
c2x2 + ... + cnxn, sendo c1, c2, ... , cn valores constantes.
A PL, segundo Colin (2013), é uma ferramenta usada para resolver problemas de 
otimização e, como tal, utiliza um modelo que contempla, de forma geral:
• As variáveis para as quais o tomador de decisão tem o poder de alterar, ou seja, 
as variáveis de decisão;
• As constantes ou parâmetros, que são aqueles valores que o tomador de decisão 
não tem o poder de alterar;
f (x1, x2) = 2x1 + 5x2 é uma função linear, ao passo que as funções f (x1, x2) 
= 5x1.x2 e f (a, b) = a.b² + 2 não são lineares.
Da mesma forma, para um número qualquer b e uma função linear f (x1, x2, 
..., xn), define-se uma inequação linear como sendo do tipo f (x1, x2, ..., xn) 
≤ b e f (x1, x2, ..., xn) ≥ b.
Exemplo:
2x1 + 5x2 ≤ 8 e 12a + 3b ≥ 3 são inequações lineares, mas 5x1.x2 + x3 ≥ 4 e 
a.b³ ≤ 6 não são inequações lineares.
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder42
• A função-objetivo, que pode ser de maximização ou minimização, e que define 
e mensura o principal objetivo do modelo;
• As restrições que combinam variáveis de decisão e parâmetros para estabelecer 
regras, relações e limites do modelo;
• A utilização única e exclusivamente de funções lineares para expressar as relações 
matemáticas entre as variáveis de decisão e os parâmetros em relação à função-
objetivo e às restrições. 
Na PL, o termo solução relaciona-se às atribuições de valores às variáveis de 
decisão, o que faz com que existam soluções viáveis, inviáveis e ótimas. Para Colin 
(2013) uma solução é viável quando os valores das variáveis de decisão atendem a todas 
as restrições. Uma solução, por sua vez, é considerada inviável quando os valores das 
variáveis de decisão fazem com que pelo menos uma das restrições não seja atendida.
Por fim, uma solução é considerada ótima quando, além de ser viável, gera um 
valor de função-objetivo extremo: o maior valor dentre todos os existentes no caso de 
maximização, e o menor valor no caso de minimização.
2.2.1 Suposições da Programação Linear
Os problemas de PL são resolvidos partindo-se de quatro suposições: 
a. divisibilidade; 
b. aditividade; 
c. proporcionalidade; 
d. certeza.
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 43
Figura 2.1 – Suposições da Programação Linear.
Fonte: Colin (2013, p. 112).
a. Divisibilidade: esta suposição parte do princípio de que as variáveis podem ter 
valores fracionados, ou seja, podem ser divididas em qualquer nível fracional. 
A implicação desse fato é a de que não pode haver a exigência de as variáveis 
serem inteiras. Se as variáveis de decisão precisarem ser inteiras (número 
de veículos a serem produzidos, por exemplo), então deverá ser utilizada a 
Programação Linear Inteira.
b. Aditividade: indica que os relacionamentos entre as variáveis são sempre adições 
e subtrações, mas nunca outras operações. Isso significa que não pode haver 
relacionamentos de dependência/funcionais entre as variáveis. A título de exemplo, 
vamos imaginar uma empresa que produza dois tipos de itens, P1 e P2, cada um 
deles gerando um lucro unitário de R$ 20 e R$ 60, respectivamente. O lucro gerado 
pelos produtos P1 e P2 será, respectivamente, a quantidade produzida de cada um 
deles (x1 e x2) multiplicada pelo respectivo lucro unitário. Assim, o lucro total será 
dado por 20.x1 + 60.x2. De forma resumida, a suposição de aditividade afirma que 
os custos totais e quantidades totais de recursos utilizados são determinados pela 
soma de custos e recursos consumidos na produção de cada um dos produtos. No 
entanto, no “mundo real”, as coisas são um pouco diferentes, pois a quantidade 
produzida de P1 pode influenciar na quantidade produzida de P2.
Certeza
Proporcionalidade
Divisibilidade
Aditividade
Suposições
da PL
PESQUISA OPERACIONAL | Ricardo Buneder44
c. Proporcionalidade: esta suposição está relacionada ao fato de que o nível de 
contribuição de uma variável de decisão é sempre proporcional ao seu valor. 
Utilizando o exemplo anterior da produção dos produtos P1 e P2, teremos que 
a contribuição de P1 para o lucro totalé dada por 20.x1, independentemente 
da quantidade x1 produzida. O mesmo ocorre para P2. No entanto, isso nem 
sempre é verdadeiro, pois deve ser levado em conta um fator chamado economia 
de escala.
Figura 2.2 – Economia de Escala.
Fonte: Colin (2013, p. 124).
d. Certeza: essa suposição está relacionada ao fato de que todos os parâmetros do 
sistema são constantes conhecidas, não se aceitando incerteza de qualquer tipo.
Economia de Escala
Custo Médio
de Produção
Quantidade Produzida
A fim de obter mais informações sobre o conceito de economia de escala 
sugere-se acessar o link a seguir, do Portal Sebrae, com o título “Saiba 
como gastar menos e produzir mais com economia de escala”: http://
gg.gg/frn7b.
SAIBA MAIS
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 45
Para obter mais informações 
sobre o conceito de economia de 
escala assista ao vídeo “Economia 
de Escala”, no canal de Daniel 
Eduardo dos Santos, no Youtube: 
http://gg.gg/frn7o.
VÍDEO
PESQUISA OPERACIONAL | Ricardo Buneder46
2.3 Modelos Matemáticos de Otimização
Otimizar significa criar condições mais favoráveis para determinado evento ou 
situação, estabelecer o melhor valor possível de alguma coisa. Dessa forma, Longaray 
(2013) cita que um modelo de otimização é um esquema lógico de representação de 
determinado problema organizado de forma a obter uma solução única e ótima. Vamos 
relembrar os componentes de um modelo matemático de otimização.
2.3.1 Objetivo de um Modelo de Otimização
O conceito de otimizar algo pode criar a falsa ideia de que se está sempre 
buscando atingir um valor superior (maior quantia de dinheiro, maior número de unidades 
vendidas, maior lucro, maior receita etc.). No entanto, conforme cita Longaray (2013), 
essa associação somente é correta quando o modelo de otimização tem por finalidade a 
maximização (MAX) do objetivo. Devemos ter em mente que um modelo de otimização 
pode também ter como finalidade reduzir ao mínimo possível o valor de algo. Ou seja, 
minimizar os custos de produção de dado produto, seu tempo de produção, o número 
de horas extras utilizadas etc. Nesses casos, o modelo de otimização busca minimizar 
(MIN) o objetivo. Assim, o objetivo de um modelo pode ser o de maximizar (MAX) ou 
o de minimizar (MIN).
2.3.2 Restrições de um Modelo de Otimização
Os modelos matemáticos de otimização também estão submetidos a restrições. 
Ou seja, a fatores limitantes como, por exemplo, disponibilidade de matérias-primas, de 
recursos financeiros, do número de colaboradores, de recursos tecnológicos, de tempo, 
de demanda de produtos acabados etc.
Nesse sentido, Longaray (2013) cita o exemplo seguinte:
Um fabricante de perfumes emprega o insumo água esterilizada na 
produção de dado perfume. Supondo-se que a fábrica tenha capacidade de 
armazenagem de 2.000 litros desse insumo por dia, a restrição diária para o 
uso de água esterilizada é de 2.000 litros/dia. 
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 47
2.3.3 Variáveis de um Modelo de Otimização
São os aspectos que se quer quantificar e sobre os quais o tomador de decisão 
tem controle – número de produtos fabricados por uma empresa em um determinado 
período de tempo, montante de dinheiro a ser investido em cada tipo de carteira de 
ações, número de colaboradores a serem alocados em um turno de trabalho, frequência 
de visitas de um vendedor a seus clientes etc. Normalmente, as variáveis de decisão são 
representadas pela letra x minúscula. Por exemplo: x1, x2 etc. Cabe salientar que, em 
modelos de otimização, a maioria das variáveis de decisão assume valores positivos ou 
nulos. 
2.3.4 Constantes/Parâmetros de um Modelo de Otimização
De modo geral, nos modelos matemáticos de otimização, as constantes/parâmetros 
são componentes do objetivo como, por exemplo, custo unitário de produção, lucro 
unitário gerado pela comercialização de um produto etc., sobre as quais o tomador de 
decisão não tem controle.
PESQUISA OPERACIONAL | Ricardo Buneder48
2.4 Estrutura Algébrica de um Modelo de Otimização
Já vimos que os modelos de otimização são compostos por variáveis de decisão, 
constantes/parâmetros, função-objetivo e restrições. Cabe, no entanto, questionar, 
conforme menciona Longaray (2013), como organizar esses elementos de forma lógica 
e estruturada para dar sentido a tais modelos. Segundo esse autor, tal estruturação é 
viabilizada através da construção de um algoritmo.
Algoritmo: sequência de instruções que, para uma dada entrada, gera 
determinado resultado. Uma receita culinária é um exemplo clássico de 
algoritmo: a descrição detalhada dos ingredientes e do modo de preparo 
permite que pratos sejam preparados sempre da mesma forma, gerando 
sempre os mesmos resultados (COLIN, 2013).
GLOSSÁRIO
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 49
2.5 Estrutura Matemática de um Modelo de Otimização
De forma geral, os modelos matemáticos de otimização são representados da 
seguinte forma:
MAX Z ou MIN Z = f (x1, x2, ..., xn) 
sujeito a (s.a.):
g1 (x1, x2, ..., xn) ≤, =, ≥ b1
g2 (x1, x2, ..., xn) ≤, =, ≥ b2
g3 (x1, x2, ..., xn) ≤, =, ≥ b3
.....
gn (x1, x2, ..., xn) ≤, =, ≥ bn
onde:
x = variáveis de decisão do modelo;
Z = f (x1, x2, ..., xn) = função objetivo do modelo que pode ser do tipo MAX 
ou MIN;
b = termo independente das restrições do modelo;
g (x) = funções das restrições do modelo.
Cada uma das restrições do modelo apresenta um dos seguintes sinais: ≥, = ou ≤.
PESQUISA OPERACIONAL | Ricardo Buneder50
2.6 Exemplos de Estruturas de Modelagem Algébrica 
de Programação Linear
Neste item serão apresentados alguns modelos de programação linear comumente 
utilizados no cotidiano empresarial, segundo a perspectiva de Longaray (2013).
2.6.1 Problema da Análise de Atividades ou do 
Mix de Produção
Consiste em determinar o objetivo ótimo – maior lucro possível, maior receita 
possível – que se pode alcançar com a produção de n unidades de um produto em 
situações em que os recursos empresariais disponíveis são limitados ou escassos.
Vamos analisar o exemplo a seguir, segundo Silva et al. (2017):
Certa empresa fabrica dois produtos P1 e P2. O lucro unitário gerado pelo 
produto P1 é de 1.000 unidades monetárias e o lucro unitário gerado por 
P2 é de 1.800 unidades monetárias. A empresa citada precisa de 20 horas 
para fabricar uma unidade P1 e de 30 horas para fabricar uma unidade P2. 
O tempo anual de produção disponível para a produção desses produtos é 
de 1.200 horas. A demanda máxima esperada para cada produto é de 40 
unidades anuais para P1, e 30 unidades anuais para P2. Qual é o plano de 
produção para que a empresa maximize seu lucro total anual com a produção 
de P1 e P2? Construa o modelo de programação linear para esse caso. 
Solução
Para solucionar esse problema vamos seguir um roteiro.
a) Quais as variáveis de decisão? O que deve ser decidido é o plano de 
produção, isto é, quais as quantidades anuais que devem ser produzidas de 
P1 e P2. Portanto, as variáveis de decisão serão:
x1 = quantidade anual a produzir de P1;
x2 = quantidade anual a produzir de P2. 
(Cont...)
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 51
(...)
b) Qual é a função-objetivo? A função-objetivo (representada pela letra Z) é 
a de maximizar o lucro anual total. 
O lucro anual devido a P1 = 1.000.x1 (lucro unitário de P1 x quantidade anual 
produzida de P1);
O lucro anual devido a P2 = 1.800.x1 (lucro unitário de P2 x quantidade anual 
produzida de P2);
Lucro anual total = 1.000.x1 + 1.800.x2
Função-objetivo = MAX Z = 1.000.x1 + 1.800.x2
c) Quais as restrições? As restrições impostas pelo sistema são:
• Disponibilidade de horas para a produção de ambos os produtos = 1.200 
horas anuais
• Horas ocupadas com a produção de P1 = 20.x1 (horas necessárias para 
produzir uma unidade de P1 x quantidade anual de P1 a ser produzida);
• Horas ocupadas com aprodução de P2 = 30.x2 (horas necessárias para 
produzir uma unidade de P2 x quantidade anual de P2 a ser produzida);
• Total de horas ocupadas para a produção de P1 e P2, por ano = 20.x1 + 
30.x2
• Restrição do número de horas anuais disponíveis para a produção: 20.x1 
+ 30.x2 ≤ 1.200
• Demanda anual de P1 e P2
Demanda esperada para P1 = 40 unidades/ano;
Restrição de demanda para P1: x1 ≤ 40
Demanda esperada para P2 = 30 unidades/ano;
Restrição de demanda para P2: x2 ≤ 30
• Restrição de não negatividade (pois não é possível produzir um valor 
negativo de P1 ou P2) = x1, x2 ≥ 0
Resumo do modelo
MAX Z = 1.000.x1 + 1.800.x2
s.a. (sujeito a):
20.x1 + 30.x2 ≤ 1.200
x1 ≤ 40
x2 ≤ 30
x1, x2 ≥ 0
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder52
2.6.2 Problema da Dieta
Consiste em determinar o objetivo ótimo, ou seja, o menor custo possível para 
obter uma alimentação adequada a partir de um conjunto de nutrientes dado.
Vamos a um exemplo, segundo Silva et al. (2017): para uma boa alimentação 
o corpo humano necessita de vitaminas e proteínas. A necessidade mínima 
de vitaminas é de 32 unidades por dia e a de proteínas é de 36 unidades 
por dia. Vamos supor que uma pessoa tenha disponível carne e ovos para 
se alimentar. Cada unidade de carne contém 4 unidades de vitaminas e 6 
unidades de proteínas. Cada unidade de ovo, por sua vez, contém 8 unidades 
de vitaminas e 6 unidades de proteínas. Qual a quantidade diária de carne 
e ovos que deve ser consumida para suprir as necessidades de vitaminas e 
proteínas ao menor custo diário possível, considerando-se que cada unidade 
de carne custa R$ 3,00 e cada unidade de ovo custa R$ 2,50? 
Solução
Da mesma forma que no problema anterior, vamos seguir um roteiro.
a) Quais as variáveis de decisão? Devemos decidir quais as quantidades 
diárias de carne e ovos devem ser consumidas. As variáveis de decisão 
serão:
x1 = quantidade diária de carne a ser consumida;
x2 = quantidade diária de ovos a ser consumida. 
b) Qual é a função-objetivo? A função-objetivo (representada pela letra Z) é 
minimizar o custo total diário com a ingestão de carne e ovos. 
O custo devido ao consumo diário de carne = 3.x1 (custo unitário da carne x 
quantidade diária consumida);
O custo devido ao consumo diário de ovos = 2,5.x2 (custo unitário do ovo x 
quantidade diária consumida);
Custo diário total = 3.x1 + 2,5.x2
Função-objetivo = MIN Z = 3.x1 + 2,5.x2
c) Quais as restrições? As restrições impostas pelo sistema são:
Necessidade mínima diária de vitaminas = 32 unidades
Quantidade de vitaminas na carne = 4.x1 (quantidade de vitaminas por 
unidade de carne x quantidade diária de carne a ser consumida);
Quantidade de vitaminas no ovo = 8.x2 (quantidade de vitaminas por unidade 
de ovo x quantidade diária de ovo a ser consumida);
(Cont...)
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 53
2.6.3 Problema do Transporte
Trata-se um problema muito utilizado na logística. Consiste na minimização 
do custo total de transporte (ou distância total percorrida) necessário para abastecer 
n destinos (mercados) diferentes a partir de m fornecedores (fontes de suprimentos) 
diferentes.
A Figura 2.3 exemplifica o problema do transporte a partir do deslocamento de 
um produto qualquer de m origens (fornecedores/fontes de suprimentos) até n destinos 
(mercados), mostrando para cada rota origem/destino o custo unitário do transporte 
(representado pela letra c minúscula).
(...)
Consumo total diário de vitaminas = 4.x1 + 8.x2
Necessidade mínima diária de vitaminas = 32 unidades
Restrição de consumo diário de vitaminas: 4.x1 + 8.x2 ≥ 32
Necessidade mínima diária de proteínas = 36 unidades
Quantidade de proteínas na carne = 6.x1 (quantidade de proteínas por 
unidade de carne x quantidade diária de carne a ser consumida);
Quantidade de proteínas no ovo = 6.x2 (quantidade de proteínas por unidade 
de ovo x quantidade diária de ovo a ser consumida);
Consumo total diário de proteínas = 6.x1 + 6.x2
Necessidade mínima diária de proteínas = 36 unidades
Restrição de consumo diário de vitaminas: 6.x1 + 6.x2 ≥ 36
Restrição de não negatividade (pois não é possível consumir um valor 
negativo de carne e ovos) = x1, x2 ≥ 0
Resumo do modelo
MIN Z = 3.x1 + 2,5.x2
s.a. (sujeito a):
4.x1 + 8.x2 ≥ 32
6.x1 + 6.x2 ≥ 36
x1, x2 ≥ 0
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder54
Figura 2.3 – Problema do Transporte.
Fonte: Santos (2010, p. 111).
Vamos analisar um exemplo de um problema de transporte: 
Uma empresa de transportes possui quatro centros de distribuição (CD’s), com 
capacidade de armazenagem de mercadorias de 200 m³ (CD1), 240 m³ (CD2), 300 m³ 
(CD3) e 200 m³ (CD4). Os produtos que abastecem esses CD’s têm como ponto de origem 
três portos, P1, P2 e P3, localizados em regiões geográficas distintas. 
Essas mercadorias estão acondicionadas em contêineres de 20 m³ de capacidade 
e devem ser transportadas por modal rodoviário, levando-se em consideração que 
cada caminhão tem capacidade para transportar um contêiner por viagem até os CD’s. 
As distâncias dos portos aos CD’s (em km) são mostradas na Tabela 2.1 a seguir.
Tabela 2.1 – Distâncias (em km) entre os portos P e os CD’s.
CD1 CD2 CD3 CD4
P1 16 36 12 32
P2 44 24 12 21
P3 20 10 8 16
Fonte: Longaray (2013, p. 125).
Origens Destinos
a₁
a₂
am
.
.
.
c₁₁
c₁₂
c₁n
d₁
d₂
dn
.
.
.
1
2
11
1
2
111
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 55
Vamos determinar o modelo de programação linear que permite calcular o 
número de viagens de caminhão a serem realizadas de cada porto para cada 
CD a fim de minimizar a distância total percorrida entre os portos e os CD’s.
Solução
Como nos problemas anteriores, vamos seguir um roteiro.
a) Quais as variáveis de decisão? Devemos decidir quantas viagens devem 
ser feitas entre cada porto P e cada CD. As variáveis de decisão serão:
x11 = número de viagens a ser realizada entre o porto P1 e o CD1; 
x12 = número de viagens a ser realizada entre o porto P1 e o CD2;
x13 = número de viagens a ser realizada entre o porto P1 e o CD3;
x14 = número de viagens a ser realizada entre o porto P1 e o CD4;
x21 = número de viagens a ser realizada entre o porto P2 e o CD1;
x22 = número de viagens a ser realizada entre o porto P2 e o CD2;
x23 = número de viagens a ser realizada entre o porto P2 e o CD3;
x24 = número de viagens a ser realizada entre o porto P2 e o CD4;
x31 = número de viagens a ser realizada entre o porto P3 e o CD1;
x32 = número de viagens a ser realizada entre o porto P3 e o CD2;
x33 = número de viagens a ser realizada entre o porto P3 e o CD3;
x34 = número de viagens a ser realizada entre o porto P3 e o CD4.
b) Qual é a função-objetivo? A função-objetivo (representada pela letra Z) é 
minimizar a distância total percorrida pelos caminhões em viagens entre os 
portos P e os CD’s. 
MIN Z = 16.x11 + 36.x12 + 12.x13 + 32.x14 + 44.x21 + 24.x22 + 12.x23 + 
21.x24 + 20.x31 + 10.x32 + 8.x33 + 16.x34
c) Quais as restrições? As restrições impostas pelo sistema são:
Capacidade de armazenagem do CD1 = 200 m³ 
Capacidade de transporte de cada caminhão em cada viagem = 20 m³ (1 
contêiner)
Restrição do número de viagens entre P1, P2 e P3 e CD1: 20.x11 + 20.x21 
+ 20.x31 ≤ 200;
Capacidade de armazenagem do CD2 = 240 m³ 
Capacidade de transporte de cada caminhão em cada viagem = 20 m³ (1 
contêiner)
(Cont...)
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder56
(...)
Restrição do número de viagens entre P1, P2 e P3 e CD2: 20.x12 + 20.x22 
+ 20.x32 ≤ 240;
Capacidade de armazenagem do CD3 = 300 m³ 
Capacidade de transporte de cada caminhão em cada viagem = 20 m³ (1 
contêiner)
Restrição do número de viagens entre P1, P2 e P3 e CD3: 20.x13 + 20.x23 
+ 20.x33 ≤ 300;
Capacidade de armazenagem do CD4 = 200 m³ 
Capacidade de transporte de cada caminhão em cada viagem = 20 m³ (1 
contêiner)
Restrição do número de viagens entre P1, P2 e P3 e CD4: 20.x14 + 20.x24 
+ 20.x34 ≤200;
Restrição de não negatividade (pois não é possível realizar um número 
negativo de viagens entre P e CD) = x11, x12, x13, x14, x21, x22, x23, x24, 
x31, x32, x33, x34 ≥ 0
Resumo do modelo
MIN Z = 16.x11 + 36.x12 + 12.x13 + 32.x14 + 44.x21 + 24.x22 + 12.x23 + 
21.x24 + 20.x31 + 10.x32 + 8.x33 + 16.x34
s.a. (sujeito a):
20.x11 + 20.x21 + 20.x31 ≤ 200, ou simplificando:
x11 + x21 + x31 ≤ 10
20.x12 + 20.x22 + 20.x32 ≤ 240, ou simplificando:
x12 + x22 + x32 ≤ 12
20.x13 + 20.x23 + 20.x33 ≤ 300, ou simplificando:
x13 + x23 + x33 ≤ 15
20.x14 + 20.x24 + 20.x34 ≤ 200, ou simplificando:
x14 + x24 + x34 ≤ 10
x11, x12, x13, x14, x21, x22, x23, x24, x31, x32, x33, x34 ≥ 0
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 57
2.6.4 Problema da Alocação de Equipes de Trabalho
Consiste em organizar a distribuição de equipes de colaboradores nos diversos 
horários de escala de uma organização. O objetivo principal é a minimização do número 
de colaboradores escalados para cada turno, respeitando as restrições de número mínimo 
de indivíduos por turno.
Vamos a um exemplo: uma refinaria processa petróleo e seus derivados 
ininterruptamente. O esquema de trabalho diário funciona em turnos de 4 horas, atendidos 
por equipes. Como há diferença na quantidade e no tipo de atividade em cada turno, 
existe variação no número de colaboradores que compõem as equipes nos diferentes 
turnos. Nesse sentido, a gerência fixou um número mínimo de colaboradores que deve 
integrar a equipe de cada um dos turnos. A jornada diária de cada colaborador é de 8 
horas. A Tabela 2.2 apresenta a relação entre turnos e número mínimo de colaboradores 
fixado pela gerência.
Tabela 2.2 – Relação entre turnos e número mínimo de colaboradores.
Turno Duração Número mínimo de colaboradores
A 0 a 4 7
B 4 a 8 6
C 8 a 12 14
D 12 a 16 9
E 16 a 20 12
F 20 a 24 8
Fonte: Longaray (2013, p. 128).
Determine um algoritmo de programação linear que viabilize a alocação 
do menor número possível de colaboradores por turno, atendendo às 
exigências da gerência e respeitando a jornada de trabalho. 
Solução
De forma idêntica ao problema anterior, vamos seguir um roteiro:
a) Quais as variáveis de decisão? Devemos decidir sobre o número de 
colaboradores que iniciam seu trabalho em cada turno. As variáveis de 
decisão serão:
(Cont...)
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder58
(...)
x1 = número de colaboradores que iniciam seu trabalho no turno A;
x2 = número de colaboradores que iniciam seu trabalho no turno B;
x3 = número de colaboradores que iniciam seu trabalho no turno C;
x4 = número de colaboradores que iniciam seu trabalho no turno D;
x5 = número de colaboradores que iniciam seu trabalho no turno E;
x6 = número de colaboradores que iniciam seu trabalho no turno F;
b) Qual é a função-objetivo? A função-objetivo (representada pela letra 
Z) é minimizar o número de colaboradores alocados por turno, atendendo 
às exigências da gerência e respeitando a jornada de trabalho. Assim, a 
função-objetivo é:
Função-objetivo = MIN Z = x1 + x2 + x3 + x4 + x5 + x6
c) Quais as restrições? As restrições impostas pelo sistema são dadas por:
x1 + x2 ≥ 6
x2 + x3 ≥ 14
x3 + x4 ≥ 9
x4 + x5 ≥ 12
x5 + x6 ≥ 8
x1 + x6 ≥ 7
x1, x2, x3, x4, x5, x6 ≥ 0
Resumo do modelo
MIN Z = x1 + x2 + x3 + x4 + x5 + x6
s.a. (sujeito a):
x1 + x2 ≥ 6
x2 + x3 ≥ 14
x3 + x4 ≥ 9
x4 + x5 ≥ 12
x5 + x6 ≥ 8
x1 + x6 ≥ 7
x1, x2, x3, x4, x5, x6 ≥ 0
(Cont....)
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 59
2.6.5 Problema da Mistura
Consiste na minimização do custo total da formulação de determinada quantidade 
de mistura composta por um conjunto de ingredientes. 
Vamos a um exemplo: uma fábrica de ração para animais possui em estoque três 
misturas a partir das quais deve ser produzida uma nova ração que apresente quantidades 
mínimas de dois nutrientes presentes nas misturas estocadas. 
A Tabela 2.4 apresenta as misturas em estoque com a porcentagem de ingredientes 
presentes em cada uma, bem como seu custo e quantidades mínimas exigidas na nova 
ração.
(...)
Veja a Tabela 2.3 para um melhor entendimento das restrições deste 
modelo:
Tabela 2.3 – Resumo das Restrições.
Turnos A B C D E F
X1 X1
X2 X2
X3 X3
X4 X4
X5 X5
X6
X6
 ≥
Equipes 7 6 14 9 12 8
Fonte: Longaray (2013, p. 129).
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder60
Tabela 2.4 – Percentual dos Ingredientes nas Misturas e Custo.
% por kg
Ingredientes Mistura 1 Mistura 2 Mistura 3
Exigência mínima 
(em kg) por saco de 
30 kg
1 25 9 32 5
2 20 30 18 6
Custo (R$/kg) 0,30 0,25 0,28
Fonte: Silva et al. (2017, p. 12).
Agora, o problema consiste em determinar a composição do saco de 30 kg 
da nova ração a partir das três misturas com o menor custo possível.
Solução
Vamos elaborar um roteiro:
a) Quais as variáveis de decisão? Devemos decidir quais as quantidades 
de cada mistura devem ser colocadas na nova ração, por saco de 30 kg, 
respeitando-se às exigências nutricionais. As variáveis de decisão serão:
x1 = quantidade da mistura 1, em kg, a ser adicionada em um saco de 30 kg 
da nova ração;
x2 = quantidade da mistura 2, em kg, a ser adicionada em um saco de 30 
kg da nova ração;
x3 = quantidade da mistura 3, em kg, a ser adicionada em um saco de 30 
kg da nova ração;
b) Qual é a função-objetivo? A função-objetivo (representada pela letra Z) é 
minimizar o custo total de fabricação de cada saco de 30 kg da nova ração. 
Função-objetivo = MIN Z = 0,30.x1 + 0,25.x2 + 0,28.x3
c) Quais as restrições? As restrições impostas pelo sistema são:
Cada saco da nova ração deve conter 30 kg:
x1 + x2 + x3 = 30
A mistura 1 apresenta 25% do ingrediente 1 e 20% do ingrediente 2;
A mistura 2 apresenta 9% do ingrediente 1 e 30% do ingrediente 2;
A mistura 3 apresenta 32% do ingrediente 1 e 18% do ingrediente 2;
(Cont...)
DESTAQUE
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 61
(...)
Cada saco de 30 kg da nova ração deve conter, no mínimo, 5 kg do 
ingrediente 1 e 6 kg do ingrediente 2, assim:
0,25.x1 + 0,09.x2 + 0,32.x3 ≥ 5 
0,20.x1 + 0,30.x2 + 0,18.x3 ≥ 6
x1, x2, x3 ≥ 0
Resumo do modelo
MIN Z = 0,30.x1 + 0,25.x2 + 0,28.x3
s.a. (sujeito a):
x1 + x2 + x3 = 30
0,25.x1 + 0,09.x2 + 0,32.x3 ≥ 5 
0,20.x1 + 0,30.x2 + 0,18.x3 ≥ 6
x1, x2, x3 ≥ 0
Existem outros tantos problemas de programação linear envolvendo a 
alocação ótima de recursos escassos, mas no momento finalizamos com 
os exemplos apresentados até aqui.
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder62
2.7 Método Gráfico - Técnica de Solução para 
Modelos de Programação Linear com Duas 
Variáveis de Decisão
Segundo Silva et al. (2017), o método gráfico é uma técnica de solução limitada 
a duas variáveis de decisão. Consiste em representar em um conjunto de eixos 
perpendiculares entre si o conjunto das possíveis soluções do problema (x1, x2) que 
satisfazem às restrições impostas pelo sistema. O desempenho do modelo é avaliado pela 
representação gráfica da função-objetivo e as soluções são classificadas de acordo com 
sua posição no gráfico.
Para iniciarmos o estudo gráfico de um modelo de programação linear com 
duas variáveis, devemos ter em mente que a representação gráfica de uma equação linear 
com duas variáveis é uma reta. Já a representação gráfica de uma inequação linear com 
duas variáveis é um dos semiplanos definidos pela reta correspondente à equação. 
Para melhor compreensão do que está sendo exposto, vamos nos valer de um 
exemplo dado pelo autor anteriormente referenciado: 
Exemplo 1: representar graficamente a inequação x1 + 2x2 ≥ 10
a. Primeiramente, construímos a reta correspondente à equação x1 + 2x2 = 10
Para tal, são necessários 2 pontos: x1 e x2. Fazendo x1 = 0 teremos 0 + 2x2 = 10, 
ou seja:
x2 = 5
Se fizermos x2 = 0, teremos x1 + 0 = 10, ou seja, x1 = 10;
b. Devemos agora testar a inequação x1 + 2x2 ≥ 10. Para tal, veja a Figura 2.4 a 
seguir.Vamos tomar um ponto qualquer de uma das regiões limitadas pela reta, 
por exemplo, o ponto x1 = 10 e x2 = 5. 
Substituindo esses valores de x1 e x2 na inequação temos:
10 + 2. 5 ≥ 10, ou 20 ≥ 10, o que é verdadeiro, portanto, a região das soluções 
da inequação é aquela que contém o ponto testado. Vamos agora testar mais um 
ponto: x1 = 2 e x3 = 3. Substituindo na inequação temos: 2 + 2. 3 ≥ 10, ou seja, 8 
≥ 10, o que é falso, por isso a região das soluções não contém esse ponto. 
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 63
Uma outra forma de determinar a região de soluções é através do teste do ponto 
que representa a origem (0,0) na inequação. Assim, se substituirmos x1 = 0 e x2 
= 0 na inequação x1 + 2x2 ≥ 10 teremos:
0 + 2. 0 ≥ 10 
0 + 0 ≥ 10
0 ≥ 10, o que é FALSO, ou seja, o ponto (0,0) não pertence à região das soluções, 
logo a região onde está o ponto (0,0), ou seja, abaixo da equação da reta x1 + 2x2 
= 10 não pertence à região de soluções da inequação em questão.
Figura 2.4 – Gráfico da inequação x1 + 2x2 ≥ 10.
Fonte: Silva et al. (2017, p. 15).
Vamos a mais um exemplo.
Exemplo 2: representar graficamente a solução do sistema:
x1 + 3x2 ≤ 12
2x1 + x2 ≥ 16
x1, x2 ≥ 0
Região de Soluções
(10,5)
10 X₁
X₂
5
(0,0)
PESQUISA OPERACIONAL | Ricardo Buneder64
a. O primeiro passo é representar cada uma das retas correspondentes às equações 
seguintes:
x1 + 3x2 = 12
Fazendo x1 = 0 teremos x2 = 4
Fazendo x2 = 0 teremos x1 = 12
2x1 + x2 = 16
Fazendo x1 = 0 teremos x2 = 16
fazendo x2 = 0 teremos x1 = 8
As restrições x1 ≥ 0 e x2 ≥ 0 representam o 1º quadrante do gráfico (x1, x2).
A Figura 2.5 mostra a representação gráfica das equações desse sistema.
Figura 2.5 – Representação gráfica do sistema proposto.
Fonte: Silva et al. (2017, p. 16).
b. Depois de representar as equações no gráfico devemos testar para cada reta qual 
região corresponde à solução de cada inequação.
Vamos tomar a reta 1, correspondente à inequação x1 + 3x2 ≤ 12, e testar o ponto 
correspondente à origem (0,0):
(8,16)
8 122
2
1
4
5
16
x₂
x₁
Região solução do
sistema
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 65
0 + 3.0 ≤ 12
0 + 0 ≤ 12
0 ≤ 12, o que é VERDADEIRO, assim, todos os pontos abaixo da reta x1 + 3x2 
= 12 fazem parte da solução da inequação x1 + 3x2 ≤ 12.
Agora vamos testar o ponto (0,0) para a inequação 2x1 + x2 ≥ 16:
2.0 + 0 ≥ 16
0 + 0 ≥ 16
0 ≥ 16, o que é FALSO, logo o ponto (0,0) e todos os pontos abaixo da reta 2x1 + 
x2 = 16 não fazem parte da solução da inequação 2x1 + x2 ≥ 16.
Dessa forma, a região solução do sistema proposto será aquela abaixo da reta 1 e 
acima da reta 2 (região sombreada da Figura 2.5). 
2.7.1 Avaliação do Objetivo
Vamos agora estudar como avaliar o desempenho de uma função-objetivo por 
meio do método gráfico. Para tal, vamos nos valer da função-objetivo MAX Z = 2x1 + 
5x2, na região de soluções do gráfico representado na Figura 2.6.
Figura 2.6 – Representação gráfica de Z = 2x1 + 5x2.
Fonte: Silva et al. (2017, p. 18).
840
x₂
x₁
Região de soluções
8
6
PESQUISA OPERACIONAL | Ricardo Buneder66
Vamos seguir o roteiro proposto por Silva et al. (2017), partindo de um valor 
arbitrário para Z, por exemplo, Z = 10. Substituindo esse valor na função-objetivo dada 
teremos: 10 = 2x1 + 5x2. 
Agora precisamos encontrar um conjunto de pontos x1 e x2 que levem ao valor 
Z = 10. Para isso fazemos primeiramente x1 = 0 e, depois x2 = 0.
Assim, se x1 = 0:
10 = 2.0 + 5x2, ou seja, x2 = 2.
Para x2 = 0, teremos:
10 = 2x1 + 5.0, ou seja, x1 = 5.
Escolhendo um segundo valor para Z, como por exemplo, 15, teremos:
15 = 2x1 + 5x2
Procedendo da mesma forma que anteriormente:
se x1 = 0, teremos 
15 = 2.0 + 5x2 
x2 = 3
Se x2 = 0, teremos 15 = 2x1 + 5.0
15 = 2x1, logo, x1 = 15/2 = 7,5
A Figura 2.7 mostra a representação gráfica da avaliação do desempenho da 
função-objetivo.
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 67
Figura 2.7 – Representação gráfica da avaliação do desempenho da função-objetivo.
Fonte: Silva et al. (2017, p. 22).
A partir da análise da Figura 2.7 podemos verificar que:
a. À medida em que atribuímos valores a Z obtemos retas paralelas;
b. À medida em que o valor de Z aumenta, a reta se afasta da origem do sistema de 
eixos.
Conclui-se, então, que o ponto P do gráfico, representado na Figura 2.7, é o ponto 
pertencente à reta paralela de maior valor que ainda estará na região de soluções (região 
sombreada). Portanto, o ponto P representa a solução que maximiza Z na região de 
soluções apresentada. Como P é (0, 6), Z será igual à 2.0 + 5.6 = 30.
P
7,5 8
2
4
6
x₁50
3
Z= máximo
Z= 10 Z= 15
PESQUISA OPERACIONAL | Ricardo Buneder68
2.8 Método/Algoritmo Simplex
Vamos agora estudar um dos métodos algébricos mais utilizados para a resolução 
de problemas de programação linear, o método Simplex. Conforme Longaray (2013), 
esse método foi desenvolvido pelo matemático norte-americano George Dantzig (1914-
2005).
Figura 2.8 – George Dantzig – Criador do método Simplex.
Fonte: Adaptado por Universidade La Salle (2019).
Longaray (2013) menciona que o método Simplex determina a solução ótima de 
um problema de programação linear e, em certas circunstâncias, permite concluir que o 
problema em questão tem múltiplas soluções, é inviável ou ilimitado.
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 69
2.8.1 Etapas do Método Simplex
Antes de aplicarmos o método para a resolução de um modelo de otimização 
envolvendo programação linear, é necessário reduzir o sistema algébrico do modelo à 
forma canônica. Mas como fazer isso? Basta seguirmos a seguinte sequência de passos:
Exemplo 1
Uma fábrica produz dois produtos, A e B. Cada um deles deve ser processado 
por duas máquinas, M1 e M2. Devido à programação de produção de outros itens que 
também utilizam esses equipamentos, a máquina M1 tem 24 horas semanais de tempo 
disponível para processar os produtos A e B, enquanto a máquina M2 tem 16 horas de 
tempo disponível semanal para processar os produtos A e B. Para produzir uma unidade 
do produto A, gastam-se 4 horas em cada uma das máquinas M1 e M2. Já, para produzir 
uma unidade do produto B, gastam-se 6 horas na máquina M1 e 2 horas na máquina M2. 
Cada unidade produzida e comercializada do produto A gera um lucro de R$ 
80,00 e cada unidade produzida e comercializada do produto B gera um lucro de R$ 
60,00. O produto B tem uma previsão de demanda semanal máxima de 3 unidades, não 
havendo restrições à demanda do produto A. 
Passo 1 
Determinar as variáveis de decisão do modelo representando-as por x1, x2, 
x3 etc.;
Passo 2
Determinar a função-objetivo do modelo (Z), a qual pode ser de maximização 
(MAX Z) ou minimização (MIN Z). Lembre-se que a função-objetivo de um 
modelo de otimização envolvendo programação linear é a que representa o 
principal objetivo do tomador de decisão.
Passo 3
Identificar as restrições do modelo e representá-las através de equações (=) 
ou inequações (≤, ≥) lineares utilizando as variáveis definidas no passo 1;
A título de exemplo, vamos determinar a solução canônica do seguinte 
problema de programação linear. 
DESTAQUE
PESQUISA OPERACIONAL | Ricardo Buneder70
A partir da utilização do método Simplex, deseja-se saber quantas unidades de 
A e B devem ser produzidas semanalmente de forma a maximizar o lucro e, ao mesmo 
tempo, satisfazer a todas as restrições colocadas.
SOLUÇÃO
Vamos seguir os passos propostos.
Passo 1
As variáveis de decisão de um modelo matemático de otimização são aquelas 
que podem ser controladas pelo tomador de decisão. Em outras palavras, é aquilo que o 
decisor quer descobrir. No caso de nosso problema, as variáveis de decisão são:
x1 = nº de unidades semanais do produto A a serem fabricadas;
x2 = nº de unidades semanais do produto B a serem fabricadas.
Passo 2
O passo seguinte é descobrirmos qual a função-objetivo(Z) do problema. 
O objetivo do modelo de nosso exemplo é maximizar o lucro semanal, então 
a função-objetivo será: MAX Z = 80x1 + 60x2. MAX Z porque o que se deseja é 
maximizar o lucro (representado por Z).
Como calcular esse lucro? Através da multiplicação do lucro unitário gerado pela 
produção e comercialização de cada um dos produtos pela quantidade de unidades a 
serem fabricadas desses produtos.
Passo 3 
Agora vamos determinar as restrições do problema.
Elas são em número de quatro:
R1: 4x1 + 6x2 ≤ 24 (restrição de disponibilidade da máquina M1)
R2: 4x1 + 2x2 ≤16 (restrição de disponibilidade da máquina M2)
R3: x2 ≤ 3 (restrição de demanda do produto B)
R4: x1, x2 >= 0 (restrição de não-negatividade), pois não é possível produzir um 
número negativo de unidades dos produtos A e B.
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 71
De forma resumida, temos a seguinte solução:
MAX Z = 80x1 + 60x2
s.a. (sujeita à):
4x1 + 6x2 ≤ 24 
4x1 + 2x2 ≤16 
x2 ≤ 3 
x1, x2 >= 0
Essa é a solução canônica.
Uma vez determinada a solução canônica, o problema está no formato correto 
para a aplicação do método Simplex. Nesse ponto de nosso estudo, julgamos importante 
a compreensão de dois conceitos necessários para a utilização do método Simplex: o de 
variável de folga (xF) e o de solução básica.
Variáveis de folga: representada por xF – são aquelas utilizadas para transformar 
as restrições de um problema de programação linear, de inequações para equações, com 
exceção às inequações que representam as restrições de não negatividade. Dessa forma, 
cada inequação que representa uma restrição do modelo é transformada em uma equação 
mediante a adição de uma variável de folga. Para tal, devemos respeitar as seguintes regras:
a. Se o sinal de desigualdade da inequação que representa a restrição for do tipo < 
ou ≤, uma variável de folga xF com sinal positivo (+ xF) deverá ser acrescentada 
no lado esquerdo da inequação e o sinal de desigualdade deverá ser substituído 
pelo de igualdade (=);
b. Se o sinal de desigualdade da inequação que representa a restrição for do tipo > 
ou ≥, uma variável de folga xF com sinal negativo (- xF) deverá ser acrescentada 
no lado esquerdo da inequação e o sinal de desigualdade deverá ser substituído 
pelo de igualdade (=).
Quanto à solução básica, trata-se do ponto de partida para a resolução do problema 
de programação linear através da utilização do método Simplex. Entendemos que a forma 
mais simples de compreender o método seja por meio da resolução de um problema. 
Nesse sentido, convidamos você a resolver conosco o problema de programação linear 
proposto no Exemplo 1 através de roteiro que preparamos para facilitar sua compreensão 
e aprendizagem. Vamos ver juntos?
PESQUISA OPERACIONAL | Ricardo Buneder72
Roteiro de resolução de um problema de programação linear pelo Algoritmo 
Simplex
Etapa 1 
Transformar as inequações que representam as restrições em equações (exceto 
as restrições de não negatividade), mediante o acréscimo das variáveis de folga 
a cada uma delas, conforme as regras já estudadas anteriormente. 
Assim, temos:
R1: 4x1 + 6x2 + xF1 = 24
R2: 4x1 + 2x2 + xF2 = 16
R3: x2 + xF3 = 3
Observe que:
a) As restrições de não-negatividade não são levadas em consideração para a 
solução de um modelo de PL pelo Método Simplex;
b) Para esse problema, as variáveis de folga xF são sempre positivas, pois as 
restrições são compostas por inequações do tipo ≤;
c) Na função-objetivo nunca são colocadas variáveis de folga, assim, nessa 
função elas têm coeficiente 0. 
Logo: MAX Z = 80x1 + 60x2 + 0xF1 + 0xF2 + 0xF3
Etapa 2 
Encontrar a função-objetivo transformada (função Z transformada).
Para tal, basta isolar Z e as variáveis de decisão no lado esquerdo da equação, 
deixando o lado direito igual à zero.
Observação: desconsidera-se a indicação MAX ou MIN na frente de Z.
Assim:
Z = 80x1 + 60x2 (função-objetivo original)
Z – 80x1 – 60x2 = 0 (função-objetivo transformada)
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 73
(...)
Etapa 3 
Montar o primeiro quadro Simplex.
Observe que:
• na 1ª linha são colocados os coeficientes da função Z transformada;
• na 2ª linha são colocados os coeficientes da 1ª restrição (note que o 
coeficiente de Z em qualquer restrição é sempre = 0);
• na 3ª linha são colocados os coeficientes da 2ª restrição;
• na 4ª linha são colocados os coeficientes da 3ª restrição;
Tabela 2.5 – Primeiro quadro Simplex.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 -80 -60 0 0 0 0
2ª linha 0 4 6 1 0 0 24
3ª linha 0 4 2 0 1 0 16
4ª linha 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
Etapa 4 
Determinar a solução básica inicial, bem como as variáveis básicas e não básicas. 
O que são variáveis básicas? São aquelas cujas respectivas colunas do quadro 
Simplex estão na forma de vetor identidade. Como saber se uma coluna está na 
forma de vetor identidade? Muito simples: colunas na forma de vetor identidade 
são aquelas onde existe apenas um coeficiente diferente de zero e igual a 1. Se 
observarmos o Quadro Simplex anterior, veremos que as colunas das variáveis 
xF1, xF2 e xF3 satisfazem essa condição, logo essas são as variáveis básicas 
desse quadro Simplex.
Lembre-se de que Z não é uma variável e, sim, a função-objetivo do modelo, e 
que b representa o termo independente da função-objetivo transformada e das 
restrições, ou seja, o valor que está do lado direito do sinal de igualdade.
(Cont...)
PESQUISA OPERACIONAL | Ricardo Buneder74
(...)
Etapa 5 
Determinar os valores das variáveis básicas.
Para isso, devemos tomar as colunas correspondentes às variáveis básicas 
(xF1, xF2 e xF3) e buscar o valor das mesmas.
Como fazer isso? Basta verificar para cada uma dessas colunas a linha que possui 
o coeficiente 1 e buscar o valor do termo independente “b” para essa linha.
Vamos a um exemplo utilizando o Quadro Simplex anterior. Qual o valor da 
variável básica xF1? Examinando a coluna de xF1 verificamos que o coeficiente 
1 encontra-se na linha 2 do quadro. O valor do termo independente b para essa 
linha corresponde ao valor de xF1, ou seja, 24.
Para a coluna de xF2, o coeficiente 1 está na linha 3 e, para essa linha, o valor de 
b = 16, logo: xF2 = 16;
Pelo mesmo raciocínio, na coluna de xF3, o coeficiente 1 está na linha 4 e, para 
essa linha, o valor de b = 3, logo xF3 =3.
Determinamos, assim, os valores das variáveis que correspondem às colunas na 
forma de vetor identidade, as quais são chamadas de variáveis básicas.
Assim, para o exemplo proposto, as variáveis básicas e seus respectivos valores 
são:
xF1 = 24
xF2 = 16
xF3 = 3
As demais variáveis (neste caso, x1 e x2) são as chamadas variáveis não-básicas 
e, como tal, sempre apresentam valor zero.
Observação: as variáveis não básicas – aquelas cujas colunas não estão na 
forma de vetor identidade – sempre apresentam valor zero.
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 75
(...)
Etapa 6 
Determinar a variável não básica (nesse caso, x1 ou x2) que deverá entrar na 
base, e a variável básica (nesse caso, xF1, xF2 ou xF3) que deverá sair da base.
Como fazer isso?
a) A variável que deverá entrar na base será aquela variável não básica (nesse 
caso, x1 ou x2) que na linha da função Z transformada (linha 1 do quadro) 
apresentar o coeficiente negativo de maior valor absoluto. Lembre-se que valor 
absoluto de um número é o valor desse número sem considerarmos seu sinal.
Assim, a título de exemplo, temos que o valor absoluto de + 3 é 3 e o de -3 
também é 3. Se observarmos o Quadro Simplex anterior, veremos que na linha 
1 - linha da função Z transformada - os coeficientes das variáveis não básicas x1 
e x2 são, respectivamente, -80 e -60. 
Assim, o maior coeficiente em valor absoluto é 80, o qual corresponde à variável 
não básica x1. Essa é a variável não básica que entrará na base (passando a ser 
uma variável básica).
b) Se uma variávelnão básica entrou na base, então uma variável básica terá de 
sair da base. Qual será essa variável? Será aquela que corresponder à linha que 
apresentar o menor valor para o quociente, calculado termo a termo, de cada 
um dos coeficientes da coluna dos termos independentes b pelos coeficientes 
positivos e não nulos da coluna da variável que entra na base, nesse caso, x1.
Vamos exemplificar tomando todos os elementos da coluna dos termos 
independentes b e dividindo cada um deles pelos termos da coluna de x1:
1ª linha: 0 ÷ (-80) = não é válido porque nesse caso o coeficiente de x1 é negativo;
2ª linha: 24 ÷ 4 = 6;
3ª linha: 16 ÷ 4 = 4;
4ª linha: 3 ÷ 0 = não é válido porque o coeficiente de x1 é nulo.
O menor quociente corresponde à linha 3. Devemos agora procurar nessa linha 
qual das colunas das variáveis básicas (xF1, xF2 e xF3, ou seja, aquelas que vão 
sair da base) apresenta coeficiente = 1. Em nosso exemplo, a coluna que satisfaz a 
essa condição é a da variável básica xF2, logo, essa é a variável que sairá da base.
Em resumo:
Variável não básica que entra na base: x1;
Variável básica que sai da base: xF2.
(Cont...)
PESQUISA OPERACIONAL | Ricardo Buneder76
(...)
Etapa 7 
Calcular a solução básica. Para tal, é necessário determinar o elemento pivô, a 
linha pivô e as linhas do novo quadro Simplex. Vamos começar determinando o 
elemento pivô e calculando a linha pivô.
Como determinar o elemento pivô? Ele é dado pela intersecção da coluna da 
variável que entra na base (nesse caso, x1) com a linha da variável que sai da 
base (nesse caso, xF2). Analisando nosso quadro Simplex, veremos que essa 
intersecção corresponde ao valor 4. Logo, ele é o elemento pivô.
Tabela 2.6 – Novo quadro Simplex.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 -80 -60 0 0 0 0
2ª linha 0 4 6 1 0 0 24
3ª linha 0 4 2 0 1 0 16
4ª linha 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
E a linha pivô, como determinar? Para isso devemos dividir a linha da variável 
que sai da base (nesse caso, linha 3 – que é a da variável xF2) pelo elemento 
pivô (4), ou seja:
Tabela 2.7 – Linha pivô.
linha de
xF2 0 4 2 0 1 0 16
 elemento pivô (4)
= linha pivô 0 1 1/2 0 1/4 0 4
Fonte: Elaborado pelo autor (2019).
A linha pivô será aquela que substituirá a linha da variável que sai da base, ou 
seja, a linha 3 no novo quadro Simplex. Agora temos como construir o novo 
quadro Simplex.
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 77
(...)
Etapa 8 
Calcular as linhas do novo quadro Simplex. Devemos, em primeiro lugar, 
multiplicar cada termo da linha pivô calculada na etapa 7 pelo coeficiente com 
sinal invertido da intersecção da coluna da variável que entra na base (x1) com a 
linha que está sendo calculada. A linha resultante dessa multiplicação deverá ser 
somada à correspondente linha antiga. Assim, por exemplo, para a o cálculo da 
nova linha 1 deveremos somar o resultado mencionado à antiga linha 1. Não se 
preocupe, vamos mostrar o passo a passo deste procedimento.
Tabela 2.8 – Cálculo da nova linha 1.
Linha pivô 0 1 1/2 0 1/4 0 4
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção da 
coluna de x1 com 
a linha 1 (80)
= linha obtida 0 80 40 0 20 0 320
+ linha 1 antiga 1 -80 -60 0 0 0 0
= nova linha 1 1 0 -20 0 20 0 320
Fonte: Elaborado pelo autor (2019).
Tabela 2.9 – Cálculo da nova linha 2.
Linha pivô 0 1 1/2 0 1/4 0 4
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção da 
coluna de x1 com 
a linha 2 (-4)
= linha obtida 0 -4 -2 0 -1 0 -16
+ linha 2 antiga 0 4 6 1 0 0 24
= nova linha 2 0 0 4 1 -1 0 8
Fonte: Elaborado pelo autor (2019).
(Cont...)
PESQUISA OPERACIONAL | Ricardo Buneder78
(...)
A nova linha 3 é a linha pivô já calculada anteriormente na etapa 7.
Tabela 2.10 – Cálculo da nova linha 4.
Linha pivô 0 1 1/2 0 1/4 0 4
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção 
da coluna de 
x1 com a linha 
4 (0)
= linha obtida 0 0 0 0 0 0 0
+ linha 4 antiga 0 0 1 0 0 1 3
= nova linha 4 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
Etapa 9 
Tabela 2.11 – Montar o novo quadro Simplex.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 0 -20 0 20 0 320
2ª linha 0 0 4 1 -1 0 8
3ª linha 0 1 1/2 0 1/4 0 4
4ª linha 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
A análise desse quadro nos dá a solução básica, ou seja, Z = 320, x1 = 4, x2 = 0, 
xF1 = 8, xF2 = 0 e xF3 = 3.
Z = 320 (o valor de Z é sempre dado pelo coeficiente do termo independente b na 
1ª linha do quadro);
As variáveis básicas são aquelas cujas colunas estão na forma de vetor identidade:
x1 = 4
xF1 = 8
xF3 = 3
As variáveis não básicas são aquelas cujas colunas não estão na forma de vetor 
identidade e, como tal, assumem valor igual à zero: x2 = 0 e xF2 = 0.
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 79
(...)
Etapa 10 
Determinar se a solução básica encontrada corresponde à solução ótima. Para 
isso, devemos analisar os coeficientes das variáveis não básicas (x2 e xF2) na 
linha 1 - linha da função Z transformada do novo quadro.
Se qualquer um desses coeficientes possuir valor negativo nessa linha, então 
a solução obtida não é a ótima e deveremos voltar à etapa 5 (determinação de 
nova solução básica). Analisando o novo quadro Simplex, verificamos que o 
coeficiente da coluna de x2 (variável não básica) na linha 1 é negativo, logo a 
solução encontrada não é a ótima e temos que retornar à etapa 5.
Etapa 5 
Determinar os valores das variáveis básicas. Quais colunas de variáveis (x1, x2, 
xF1, xF2 e xF3) estão na forma de vetor identidade? 
Observando o segundo quadro Simplex, veremos que as colunas de variáveis 
que satisfazem essa condição são x1, xF1 e xF3. Os valores das variáveis básicas 
são: x1 = 4, xF1 = 8 e xF3 = 3.
Etapa 6 
Determinar a variável não básica (nesse caso, x2 ou xF2), que deverá entrar na 
base, e a variável básica (nesse caso, x1, xF1 ou xF3) que deverá sair da base. 
Variável não básica que entrará na base: será aquela variável (x2 ou xF2) que 
na linha da função Z transformada (linha 1 do quadro) apresentar o coeficiente 
negativo de maior valor absoluto.
Observando o quadro anterior, veremos que na linha 1, o coeficiente de x2 = -20 
e o coeficiente de xF2 = 20. Assim, o maior (e único) coeficiente negativo é 20, 
correspondente à variável x2, logo essa é a variável que entrará na base.
Variável que sairá da base: será aquela que corresponder à linha que apresentar 
o menor valor para o quociente entre a coluna dos termos independentes b e 
os coeficientes positivos e não nulos da coluna da variável que entrará na base, 
nesse caso, x2.
1ª linha: 320 ÷ -20 = 0 (não é válido porque o coeficiente de x2 é negativo);
2ª linha: 8 ÷ 4 = 2;
3ª linha: 4 ÷ 1/2 = 8;
4ª linha: 3 ÷ 1 = 3.
(Cont...)
PESQUISA OPERACIONAL | Ricardo Buneder80
(...)
O menor quociente corresponde à linha 2. Assim, devemos procurar nessa linha, 
para qual coluna das variáveis básicas (x1, xF1 e xF3) há o coeficiente = 1. No 
nosso caso, a coluna que satisfaz essa condição é a da variável básica xF1, logo, 
essa é a variável que sairá da base.
Em resumo:
Variável que entrará na base: x2
Variável que sairá da base: xF1
Etapa 7
Cálculo da nova solução. Para isso é preciso determinar o elemento pivô, a linha 
pivô e as novas linhas do quadro. O elemento pivô é dado pela intersecção da 
coluna da variável que entra na base (x2) com a linha da variável que sairá da base 
(xF1). Analisando o quadro anterior, veremos que essa intersecção corresponde 
ao valor 4. Logo, esse é o elemento pivô.
Tabela 2.12 – Elemento pivô.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 0 -20 0 20 0 320
2ª linha 0 0 4 1 -1 0 8
3ª linha 0 1 1/2 0 1/4 0 4
4ª linha 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
E a linha pivô? Para determinar a linha pivô devemos dividir a linha da variável 
que sairá da base (xF1) pelo elemento pivô, ou seja:
Tabela 2.13 – Linha pivô.
linha de xF1 0 0 4 1 -1 0 8
 elemento pivô (4)
= linhapivô 0 0 1 1/4 -1/4 0 2
Fonte: Elaborado pelo autor (2019).
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 81
(...)
A linha pivô será a linha que substituirá a linha da variável que sairá da base, 
ou seja, a linha de xF1 (linha 2). Assim, começaremos a montar o novo quadro 
Simplex, conforme segue.
Tabela 2.14 – Novo quadro Simplex.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 0 -20 0 20 0 320
2ª linha 0 0 1 1/4 -1/4 0 2
3ª linha 0 1 1/2 0 1/4 0 4
4ª linha 0 0 1 0 0 1 3
Fonte: Elaborado pelo autor (2019).
Etapa 8 
Calcular as novas linhas do quadro Simplex. Para esse cálculo devemos, em 
primeiro lugar, multiplicar cada termo da linha pivô pelo coeficiente com sinal 
invertido da intersecção da coluna da variável que entrará na base (x2) com a 
linha que está sendo calculada. A linha resultante dessa multiplicação deverá ser 
somada à linha antiga correspondente à linha nova que está sendo calculada.
Tabela 2.15 – Cálculo da nova linha 1.
Linha Pivô 0 0 1 1/4 -1/4 0 2
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção da 
coluna de x2 com 
a linha 1 (20)
= linha obtida 0 0 20 5 -5 0 40
+ linha 1 antiga 1 0 -20 0 20 0 320
= nova linha 1 1 0 0 5 15 0 360
Fonte: Elaborado pelo autor (2019).
(Cont...)
PESQUISA OPERACIONAL | Ricardo Buneder82
(...)
A linha 2 é a linha pivô já calculada.
Tabela 2.16 – Cálculo da nova linha 3.
Linha Pivô 0 0 1 1/4 -1/4 0 2
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção da 
coluna de x2 com 
a linha 3 (-1/2)
= linha obtida 0 0 -1/2 -1/8 1/8 0 -1
+ linha 3 antiga 0 1 1/2 0 1/4 0 4
= nova linha 3 0 1 0 -1/8 3/4 0 3
Fonte: Elaborado pelo autor (2019).
Tabela 2.17 – Cálculo da nova linha 4.
Linha Pivô 0 0 1 1/4 -1/4 0 2
Multiplicar pelo 
coeficiente com 
sinal invertido 
da intersecção da 
coluna de x2 com 
a linha 4 (-1)
= linha obtida 0 0 -1 -1/4 1/4 0 -2
+ linha 4 antiga 0 0 1 0 0 1 3
= nova linha 4 0 0 0 -1/4 1/4 1 1
Fonte: Elaborado pelo autor (2019).
Tabela 2.18 – Montar o novo quadro Simplex.
Z x1 x2 xF1 xF2 xF3 b
1ª linha 1 0 0 5 15 0 360
2ª linha 0 0 1 1/4 -1/4 0 2
3ª linha 0 1 0 -1/8 3/8 0 3
4ª linha 0 0 0 -1/4 1/4 1 1
Fonte: Elaborado pelo autor (2019).
(Cont...)
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 83
(...)
Assim, a nova solução encontrada é:
Z = 360
Variáveis básicas:
x1 = 3
x2 = 2
xF3 = 1
Variáveis não básicas (são as que consideramos iguais a zero, pois suas colunas 
não estão na forma de vetor identidade): xF1 = 0 e xF2 = 0.
Etapa 10:
Determinar se a solução encontrada e a ótima. Para tal, devemos analisar 
os coeficientes das variáveis não básicas (xF1 e xF2) na linha da função Z 
transformada (linha 1). Se qualquer um deles possuir coeficiente negativo, então 
a solução obtida não é a ótima e deveremos voltar ao passo 5. Nesse caso, 
verificamos que os coeficientes das colunas xF1 e xF2 na primeira linha do 
quadro são ambos positivos, logo a solução encontrada é a ótima.
Essa solução mostra que o lucro semanal máximo é de 360 (valor da função-
objetivo Z) e que, para obtê-lo, devem ser fabricadas 3 unidades/semana do 
produto A (valor da variável de decisão x1) e 2 unidades/semana do produto B 
(valor da variável de decisão x2).
PESQUISA OPERACIONAL | Ricardo Buneder84
SÍNTESE DA UNIDADE
Chegamos ao final da Unidade 2 de nossa disciplina de Pesquisa Operacional. 
Tivemos a oportunidade de adquirir conhecimentos importantes relacionados à 
programação linear, modelagem de problemas de programação linear, identificação 
dos componentes de um modelo de programação linear, o conceito de solução ótima, a 
representação gráfica de um problema de programação linear e, finalmente, a utilização 
do método algébrico Simplex para resolução de problemas de programação linear.
Programação Linear e Método/Algoritmo Simplex | UNIDADE 2 85
REFERÊNCIAS
COLIN, E. C. Pesquisa Operacional: 170 aplicações em estratégia, finanças, logística, produção, 
marketing e vendas. Rio de Janeiro: LTC, 2013.
IBL - DESCOMPLICANDO A ECONOMIA. Economia de escala. 2018. Disponível em: 
http://gg.gg/frnzc. Acesso em: 29 out. 2019. 
ECONOMICAMENTE FALANDO. Economia de escala simplificadamente. 2017. Disponível 
em: http://gg.gg/frnz6. Acesso em: 29 out. 2019. 
O EXPLORADOR. George Dantzig pode ser considerado o pai da programação linear, pois 
ele é o inventor do Simplex. 2014. Disponível em: http://gg.gg/frnz3. Acesso em: 29 out. 2019. 
LONGARAY, A. A. Introdução à Pesquisa Operacional. São Paulo: Saraiva, 2013.
SANTOS, M. O. dos. Introdução à Pesquisa Operacional: otimização linear. Universidade de 
São Paulo – USP - Instituto de Ciências Matemáticas e de Computação – ICMC, 2010.
SANTOS, M. O. dos. Programação Linear. Departamento de Matemática Aplicada do Instituto 
de Matemática e Estatística. Universidade Federal do Rio de Janeiro: 2007.
SEBRAE. Saiba como gastar menos e produzir mais com economia de escala. 2019. 
Disponível em: http://gg.gg/frnz0. Acesso em: 29 out. 2019. 
SILVA, E. et al. Pesquisa Operacional: programação linear: simulação. São Paulo: 
Atlas, 2017.
PESQUISA OPERACIONAL | Ricardo Buneder150
Se você encontrar algum problema nesse material, entre em 
contato pelo email eadproducao@unilasalle.edu.br. Descreva o 
que você encontrou e indique a página.
Lembre-se: a boa educação se faz com a contribuição de todos!
CONTRIBUA COM A QUALIDADE DO SEU CURSO
Av. Victor Barreto, 2288
Canoas - RS
CEP: 92010-000 | 0800 541 8500
ead@unilasalle.edu.br