Modelo Linear

Prévia do material em texto

PESQUISA
OPERACIONAL
Organizador: 
Rodrigo Rodrigues
Catalogação na publicação: Poliana Sanchez de Araujo – CRB 10/2094
R696p Rodrigues, Rodrigo.
 Pesquisa operacional / Rodrigo Rodrigues. – 
 Porto Alegre : SAGAH, 2017.
 121 p. : il. ; 22,5 cm. 
 ISBN 978-85-9502-004-7
 1. Pesquisa operacional – Engenharia de 
 produção. I. Título. 
CDU 658.5
Modelos lineares e o 
método simplex
Objetivos de aprendizagem
Ao final deste texto, você deve apresentar os seguintes aprendizados:
 � Descrever a implementação do método simplex.
 � Introduzir variáveis artificiais na resolução de problemas.
 � Resolver um problema de programação linear com o método simplex.
Introdução
Os processos de planejamento das atividades de uma organização com 
o uso da pesquisa operacional buscam uma solução ótima. Neste texto, 
você vai acompanhar as características específicas de programação linear
(PL). Por meio das operações de maximização, você vai ver os passos de
resolução de situações-problema com a aplicação do método simplex
para elaborar modelos de resolução. Será utilizado exemplo prático para 
subsidiar as atividades relativas à identificação, estruturação e resolução 
matemática de problemas comuns nas tomadas de decisões do cotidiano 
de uma organização.
Programação linear
Programação linear (PL) é uma técnica de otimização aplicada em sistemas 
de equações e inequações lineares que representam modelos já projetados. 
Trata-se de uma aplicação matemática utilizada por profissionais para proble-
mas relativos à produção, por exemplo, para evitar desperdícios de produtos 
e matérias-primas ou otimizar mão de obra, baseado em funções e restrições 
lineares para modelagem e solução de problemas de otimização.
Aplicação da função objetivo e das restrições em PL
Quando se fala de problemas de otimização, significa que queremos maximi-
zar (aumentar) ou minimizar (diminuir) uma função, relacionada a finanças, 
produção, entre outras áreas. Nesses casos, é necessário verificar a função 
objetivo e as restrições apresentadas pelo sistema analisado (BARBOSA, 2015).
 � 1. Função objetivo
Para definir a função objetivo, você pode, por exemplo, maximizar o lucro 
ou minimizar o custo. Assim, a função objetivo pode ser escrita de duas formas:
 ■ Para maximizar Z: 
máx. z = c1x1 + c2x2 +...+ cn xn 
 ■ Para minimizar Z:
min. z = c1x1 + c2x2 +...+ cn xn
Você pode estranhar o fato de a minimização de uma função z ser equivalente à 
maximização dessa função em sua versão negativa – z, como nos itens a e b, em que 
ambas são somatórias. Nas duas situações, c seriam os números reais, e x, as variáveis 
do problema. Lembrando que, em a, é feita a maximização do lucro e, em b, o objetivo 
é minimizar o custo.
Além da função objetivo, representada por uma função matemática, em 
PL temos também as restrições.
 � 2. Restrições em PL
Considere uma indústria de alimentos que queira otimizar sua produção, 
maximizando o lucro. Para essa otimização, surgiram limitações na prática, que 
são denominadas restrições do problema PL. Essas limitações são as seguintes:
Pesquisa operacional34
 ■ disponibilidade de matéria-prima;
 ■ capacidade da produção;
 ■ mão de obra;
 ■ limitações no preço.
Podem existir diferentes limitações, de acordo com o problema de PL, 
como localização ou espaço físico. Veja algumas dessas situações:
 ■ Restrição de capital: um investidor que quer aumentar ou diversificar 
seus investimentos, mas possui pouco capital.
 ■ Restrição de quantidade: uma empresa de logística que deseja ampliar 
suas entregas, mas possui poucos veículos.
 ■ Restrição espacial: um pequeno agricultor que deseja cultivar diversas 
culturas, porém, não possui espaço suficiente.
Há restrições de igualdade e desigualdade, que são representadas por 
equações e inequações. Elas são representadas a seguir:
 ■ Equação de restrições de igualdade:
a11x1 + a12x2 + ... + a1nxn = b1
 ■ Inequações de restrições de desigualdade:
a11x1 + a12x2 + ... + a1nxn ≤ b1
ou
a11x1 + a12x2 + ... + a1nxn ≥ b1
 � 3. Forma geral ou padrão
Um problema de PL é caracterizado, na sua forma geral, pela padroni-
zação, com o objetivo de facilitar o entendimento. A seguir apresentamos a 
sua estrutura:
 � Máx. z = c1x1 + c2x2 +...+ cn xn 
 � a11x1 + a12x2 + ... + a1nxn ≤ b1
 � a21x1 + a22x2 + ... + a2nxn ≥ b2
am1x1 + am2x2 + ... + amnxn ≤ bm
x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0
35Modelos lineares e o método simplex
Onde os termos aij, bi e cj são coeficientes das equações e inequações que 
indicam no problema os números de quantidade, valor e custos (i = 1, 2, 3,..., 
m; e j = 1, 2, 3, ..., n), semelhantes a operações com matrizes em que esses 
termos indicam a posição dos elementos de uma matriz.
As variáveis x1, x2, ..., xn são selecionadas de modo que satisfaçam as 
restrições e otimizem a função objetivo. O uso de s.a. (“sujeita a”) indica 
que temos uma função objetivo que está sujeita a determinadas restrições. 
As limitações das restrições são representadas pelos termos b1, b2, ..., bm, 
que são chamados de parâmetros da função. E são chamados de restrições de 
não negatividade os termos x1, ≥ 0, x2 ≥ 0, ..., xn ≥ 0. Como não podemos ter 
quantidades negativas de produtos ou recursos, essas restrições são utilizadas.
Veja agora um exemplo detalhado de PL:
 � Quantidade mensal disponível de couro – 1 t.
 � Quantidade mensal disponível de borracha – 600 kg.
 � O lucro referente a uma unidade de sandália é de R$ 12,00.
 � O lucro referente a uma unidade de sapato é de R$ 15,00.
Caso toda a produção de calçados seja vendida e a empresa consiga vender 
no máximo 700 sandálias por mês, qual quantidade de cada modelo deve ser 
produzida para que o lucro seja máximo?
Não se esqueça de que, para formular um problema, é preciso identificar 
as variáveis, a função objetivo e as restrições.
Identificação das variáveis
Nesse exemplo, as quantidades de cada modelo a serem produzidas são as 
variáveis. Onde:
 � x1: quantidade de sandálias
 � x2: quantidade de sapatos
Pesquisa operacional36
Formulação da função objetivo
Transcrevendo as informações para a linguagem matemática, obteremos 
a função objetivo. Como você sabe, o lucro unitário referente à sandália é 
de R$ 12,00, e o lucro unitário referente ao sapato é de R$ 15,00. Para ter 
lucro, representado por z, devem-se multiplicar os lucros unitários por suas 
respectivas quantidades produzidas:
 � Z = 12x1 + 15x2
Para obter o lucro máximo, a função objetivo será:
 � Max z = 12x1 + 15x2
O lucro unitário é a diferença entre o valor utilizado pela empresa para 
a venda do produto e o gasto para a sua produção.
Formulação das restrições
Na definição das restrições do problema, você deve, primeiramente, verificar 
os fatores que podem limitar a produção. No exemplo dos calçados em ques-
tão, as restrições estão relacionadas às quantidades disponíveis de couro e 
de borracha. Há, ainda, uma restrição relacionada à quantidade máxima de 
sandálias que poderá ser comercializada. Portanto, o número de restrições 
para esse problema é igual a três:
A primeira restrição, referente à quantidade de couro consumida, pode ser 
descrita com a seguinte formulação matemática:
0,7x1 + 0,4x2 ≤ 1.000
Nessa conta, é possível saber a quantidade de couro consumida na fabri-
cação de sandálias, pois sabemos que, para a fabricação de uma sandália, são 
necessários 700 g de couro (0,7 kg). Para cada sapato, são necessários 400 
g de couro (0,4 kg). Para saber o total de couro utilizado na produção, basta 
multiplicar 0,7 por x1 e 0,4 por x2 e, logo, somar essas quantias, obtendo a 
expressão:
0,7x1 + 0,4x2
37Modelos lineares e o método simplex
Se a quantidade máxima de couro que a indústria tiver disponível é 1 t 
(1.000 kg), a soma 0,7x1 + 0,4x2 não pode ultrapassar essa quantidade. Por esse 
motivo, escrevemos que 0,7x1 + 0,4x2 tem de ser menor ou igual a 1.000, ou seja:
0,7x1 + 0,4x2 ≤ 1.000
Da mesma forma, é possível obter a segunda restrição, referente ao consumo 
de borracha. Já que paraproduzir a sandália são necessários 150 g de borracha 
(0,15 kg) e para produzir o sapato são necessários 300 g (0,3 kg) do material, 
o total de borracha consumido na produção dos modelos é:
0,15x1 + 0,3x2
Sendo a disponibilidade mensal de borracha de 600 kg, a segunda restrição 
fica assim:
0,15x1 + 0,2x2 ≤ 600
Por fim, a terceira restrição, relacionada à produção máxima de sandália, 
é dada por: 
x2 ≤ 700
Então, a formulação do problema de PL proposto a que chegamos é dada 
como:
Máx. z = 12x1 + 15x2
s.a. 0,7x1 + 0,4x2 ≤ 1.000
0,15x1 + 0,3x2 ≤ 600
 x1 ≤ 700
x1 ≥ 0, x2 ≥ 0
Observação:
Para resolver problemas de PL, caso existam, as restrições ≥ (maior ou igual) 
devem ser trocadas por ≤ (menor ou igual). Para isso, basta multiplicar cada res-
trição de ≥ por (-1) e, em seguida, inverter a desigualdade ≥ por ≤. Por exemplo:
Pesquisa operacional38
A restrição
a11x1 + a12x2 + ... a1nxn ≥ b1
é equivalente a
-a11x1 – a12x2 - ... a1n xn ≤ -b1
Como você viu, as restrições x1 ≥ 0, x2 ≥ 0, ..., xn ≥ 0 são chamadas restrições 
de não negatividade. Elas são utilizadas quando as variáveis do problema não 
podem assumir valores negativos.
Interpretação geométrica e solução gráfica
Como todo problema PL tem restrições lineares, podemos representar as restri-
ções de um problema de duas variáveis em um sistema de eixos coordenados, 
chamado “plano cartesiano”.
Vamos relembrar: um par ordenado (x;y) representa um ponto no plano 
(Fig. 1), conforme estudamos no ensino médio.
Figura 1 Pontos coordenados no plano cartesiano
Fonte: Barbosa (2015).
39Modelos lineares e o método simplex
Então, com base em seus conhecimentos matemáticos, você pode apresentar 
os dados por meio de um gráfico para construir um modelo com duas ou até 
três variáveis.
Escrevemos uma equação associada a cada restrição de desigualdade 
nesse sistema de eixos coordenados para representá-las, contendo os mesmos 
coeficientes e o mesmo termo independente. No caso do exemplo da indústria 
de calçados que fabrica dois modelos (sandália e sapato), a restrição 0,7x1 + 
0,4x2 ≤ 1.000 está associada à equação 0,7x1 + 0,4x2 = 1.000. Do mesmo modo, 
a restrição 0,15x1 + 0,3x2 ≤ 600 está associada à equação 0,15x1 + 0,3x2 = 600, 
e a restrição x1 ≤ 700 está associada à equação x1 = 700.
Obtendo a representação da primeira restrição
Você deve construir uma tabela atribuindo dois valores quaisquer para a 
variável x1 para obter a representação da primeira restrição. Logo, você deve 
calcular o respectivo valor da variável x2.
A seguir apresentamos como é feito o cálculo dos valores das variáveis:
Os pares ordenados são os pontos da forma (x1; x2). Uma forma simpli-
ficada de obter os pares ordenados é atribuir o valor zero à variável x1 para 
encontrar o respectivo valor de x2. Logo, atribuímos à variável x2 o valor zero 
para encontrar o valor de x1.
Desse modo, os pontos obtidos estarão sob os eixos coordenados, facili-
tando o processo de representação gráfica de cada uma das restrições. Como 
as restrições são de desigualdade, é importante ainda considerar em qual 
semiplano vai estar a região factível (região delimitada pelas restrições do 
problema). Um método muito prático é considerar a origem do plano carte-
siano, o par ordenado (0,0). Se, ao substituir os valores de x1 e x2 por zero, a 
desigualdade for verdadeira, então a região factível estará no semiplano que 
contém a origem. Caso contrário, a região factível estará no semiplano oposto, 
ou seja, aquele que não contém a origem. Esse processo é usado também para 
as demais restrições.
Veja o cálculo desse processo:
A primeira equação é 0,7x1 + 0,4x2 = 1.000. 
Pesquisa operacional40
Sendo:
X1 = 0, temos que x2 = 2.500, 
pois resolvendo 0,7 . 0 + 0,4. X2 = 1.000
0 + 0,4x2 = 1.000
X2 = 1000/0,4
X2 = 2.500
Sendo:
X2 = 0, temos que x1 = 1.428,57, pois 0,7 . x1 + 0,4 . 0 = 1.000
0,7 . x1 + 0 = 1.000
0,7 . x1 = 1.000
X1 = 1.428,57
Assim, você obterá a Tabela 1 com os valores de x1 e x2 e os respectivos 
pares ordenados:
x1 x2 (x1;x2)
0 2500 (0;2500)
1428,57 0 (1428,57;0)
Tabela 1. Valores de x1 e x2 para 0,7x1 + 0,4x2 = 1.000.
Logo:
 � o ponto (0; 2.500) está localizado no eixo da variável x2, pois x1 é igual 
a zero;
 � o ponto (1.428,57; 0) fica sobre o eixo x1, pois x2 é igual a zero.
Assim, como o ponto (0; 0), origem do sistema, satisfaz a inequação 0,7x1 
+ 0,4x2 ≤ 1.000, a região factível está no semiplano que contém a origem . 
Veja na Figura 2, a representação da primeira restrição.
41Modelos lineares e o método simplex
No mesmo plano cartesiano em que representamos a primeira restrição, 
representamos também a segunda e a terceira restrições.
Figura 2. Representação da primeira restrição.
Fonte: Barbosa (2015).
Método simplex
Simplex é um método importante e amplamente utilizado na resolução de 
problemas lineares de otimização. 
O método simplex foi desenvolvido em 1947, por George B. Dantzig (1914-2005), 
professor emérito de pesquisa operacional e ciência da computação.
O método simplex busca, caso existam, uma ou mais soluções a partir de 
uma solução básica factível, gerando uma sequência de soluções factíveis. 
Quando essa sequência é concluída, a solução ótima é obtida.
Você deve ficar atento às duas situações em que não é possível chegar à 
solução ótima (BARBOSA, 2015):
1. por apresentar restrições de incompatibilidade, não há uma solução 
que deva ou possa executar;
Pesquisa operacional42
2. não encontrar um máximo ou um mínimo – caso em que uma das va-
riáveis pode se estender ao infinito (apresentar essa tendência), embora 
as restrições sejam satisfeitas; consequentemente, teremos um valor 
sem limites para a função objetivo. 
É importante que você conheça esse método justamente porque ele apre-
senta, excetuando-se as duas situações descritas anteriormente, a possibilidade 
de resolvermos, por meio de um esquema de equações lineares, o modelo PL.
Antes de continuarmos, vamos para duas definições importantes:
 � Variáveis básicas e não básicas: variáveis básicas são as que compõem a solução 
ótima do problema, e as variáveis não básicas são aquelas cujo valor é igual a zero.
 � Variáveis de folga ou excesso: são aquelas que acrescentamos ao problema, para 
resolvê-lo pelo método proposto, transformando as desigualdades do tipo “menor 
ou igual” em igualdades.
Considerando os passos apresentados, você pode representar a operacio-
nalização por meio da Tabela 2:
z c1 c2 cn
xb1 a11 a12 a1n
xb2 a21 a22 A2n
.
.
.
.
.
.
.
.
.
.
.
.
xbm am1 am2 amn
Tabela 2. Representação genérica da tabela utilizada no método simplex.
43Modelos lineares e o método simplex
Ainda considerando a fábrica de calçados, supomos que, mensalmente, 
toda a produção de sapatos seja vendida, enquanto a venda de sandálias seja 
no máximo de 700 pares. De acordo com essas informações, determine a 
quantidade de cada modelo que deve ser produzida de modo que o lucro seja 
máximo.
À formulação do modelo-padrão de PL para o problema vamos acrescentar 
novas variáveis de folga para cada restrição:
Max z = 12x1 + 15x2
s.a. 0,7x1 + 0,4x2 + x3 = 1.000
 0,15x1 + 0,3x2 + x4 = 600
 X1
x1 ≥ 0, x2 ≥ 0
Veja passo a passo o processo pelo qual realizamos esses cálculos. Para 
facilitar a resolução, elaboramos a Tabela 3, utilizando o modelo a seguir:
Fonte: Barbosa (2015).
Função objetivo Coeficientes da função objetivo
Termos independentes Coeficientes da restrições
Tabela 3. Modelo de tabela para o uso de método simplex.
Colocamos na linha zero o valor de z (que é a função objetivo e cuja solução 
inicial tem valor de z = 0) e os coeficientes da função objetivo, todos com os 
sinais trocados. Observe a Tabela 4:
Z = 0 -12 -15 0 0 0
Tabela 4. Coeficientes da função objetivo.
Pesquisa operacional44
Veja os coeficientes que foram colocados. Completamos os campos vazios 
sempre com zero para identificar os campos nulos. Então, temos o seguinte:
 � Na linha um, colocamos a quantidade de recursosdisponíveis referente à 
primeira restrição. Não se esqueça de que são somente coeficientes: 0,7; 
0,4; 1. O valor de 1.000 entrará na primeira coluna, pois é o coeficiente 
do termo independente ou do recurso disponível.
 � Na linha dois, escrevemos os valores: 600 (disponibilidade de recursos 
para a segunda restrição); 0,15; 0,3; 0; 1, que são os coeficientes.
 � Na linha três, registramos os valores da última restrição: 700, que é 
a disponibilidade de recursos, e 1; 0; 0; 0; 1, que são os coeficientes.
Então, nossa Tabela 5 fica assim:
x1 x2 x3 x4 x5
Z = 0 -12 -15 0 0 0
x3 1000 0,7 0,4 1 0 0
x4 600 0,15 0,3 0 1 0
x5 700 1 0 0 0 1
Tabela 5. Tabela inicial do método simplex
Inicialmente, nesse processo de resolução, as variáveis básicas de folga são: 
x3, x4 e x5. As variáveis não básicas são x1 e x2, ou seja, as variáveis originais 
do problema.
Para decidir qual variável entrará na base, precisamos verificar qual variável não básica 
fornecerá o maior lucro possível. Para isso, basta verificar qual variável tem o coeficiente 
mais negativo na linha zero. Assim, a variável que entra na base é x2, cujo coeficiente 
na linha zero é igual a -15. 
45Modelos lineares e o método simplex
Em seguida, deve ser determinada a variável básica que sairá da base. Então, 
você deverá dividir cada termo independente pelos respectivos coeficientes 
positivos (não são considerados os valores negativos ou nulos) da coluna 
referente à variável x2 (variável que entra na base):
1.000 : 0,4 = 2.500
600 : 0,3 = 2.000
Veja que a divisão de 700 por 0 não é possível. Como o menor resultado 
obtido é 2.000 (divisão de 600 por 0,3), a variável que sairá da base é x4, pois 
essa é a variável básica que tem o elemento unitário na linha referente a essa 
divisão.
Observe que o pivô, nesse caso, é igual a 0,3. Precisamos transformar o 
pivô em 1. Como 0,3 = 3/10, basta multiplicar todos os termos da linha dois 
por 10/3 (inverso multiplicativo de 3/10):
Linha dois 
multiplicada 
por 10/3
600 × 
10/3
= 2000
0,15 × 10/3
= 0,5
0,3 × 10/3
= 1
0 × 10/3
= 0
1 × 10/3
= 3,33
0 × 10/3
= 0
Figura 3. Processo de resolução.
Pesquisa operacional46
Resultando em:
Nova linha 
dois
2000 0,5 1 0 3,33 0
A linha anterior será substituída pela nova linha dois. Essa linha será utili-
zada para zerar os demais elementos não nulos da coluna referente à variável x2.
Linha zero - multiplicamos a nova linha por 15 com o intuito de zerar o 
elemento a1 = -15. Logo, somamos os resultados obtidos com os respectivos 
elementos da linha zero: 
Linha zero 0 - 12 - 15 0 0 0
Nova 
linha dois 
multiplicada 
por 15
2000 × 
=30000
0,5 × 15
= 7,5
0,5 × 15
= 15
0 × 15
= 0
3,33 × 15
= 50
0 × 15
= 0
Nova linha 
zero (soma 
da linha zero 
com a nova 
linha dois 
multiplicada 
por 15)
0 
+30000
= 
30000
- 12 + 
7,5
= - 4,5
- 15 + 15
= 0
0 + 0
= 0
0 + 50
= 50
0 + 0
= 0
Portanto, a nova linha zero é:
Nova linha 
zero
30000 -4,5 0 0 50 0
47Modelos lineares e o método simplex
Para zerar o elemento a12 = 0,4, a nova linha dois foi multiplicada por -0,4 
e, a seguir, somamos os resultados obtidos com os respectivos elementos da 
linha um:
Linha um 1000 0,7 0,4 1 0 0
Nova 
linha dois 
multiplicada 
por - 0,4
2000 × 
(- 0,4)
= -800
0,5 × 
(- 0,4)
= -0,2
1 × (- 0,4)
= -0,4
0 × (- 0,4)
= 0
3,33 × 
(- 0,4)
= -1,33
0 × (- 0,4)
= 0
Nova linha 
um (soma 
da linha um 
com a nova 
linha dois 
multiplicada 
por - 0,4)
1000 
- 800
= 200
0,7 – 0,2
= 0,5
0,4 – 0,4
= 0
1 + 0
= 1
0 – 1,33
= - 1,33
0 + 0
= 0
Assim, a nova linha é:
Nova 
linha um
200 0,5 0 1 -1,33 0
Sendo o elemento a22 igual a zero, a linha não precisa ser alterada. 
Então, a primeira iteração se resume a seguir:
x1 x2 x3 x4 x5
Z = 
30000
-4,5 0 0 50 0
x3 200 0,5 0 1 -1,33 0
x4 2000 0,5 1 0 3,33 0
x5 700 1 0 0 0 1
Agora, temos a primeira solução ótima , que é z = 30.000.
Contudo, como variável não básica (x1), ainda apresenta valor negativo, 
portanto, devemos partir para uma nova iteração.
Segunda iteração – buscando nova solução.
Pesquisa operacional48
Construímos nova tabela a partir dos resultantes recém-obtidos:
x1 x2 x3 x4 x5
Z = 
30000
-4,5 0 0 50 0
x3 200 0,5 0 1 -1,33 0
x4 2000 0,5 1 0 3,33 0
x5 700 1 0 0 0 1
Há, ainda, um coeficiente negativo na linha zero. Então, a variável que 
entrará na base é x1. A decisão sobre qual variável sairá da base se dará a partir 
das seguintes divisões: 200 : 0,5 e 700 : 1.
O valor da divisão de 200 por 0,5 é 400, o menor resultado obtido, corres-
pondente à linha um. Logo, a variável que sairá da base é x3.
x1 x2 x3 x4 x5
Z = 
30000
-4,5 0 0 50 0
x3 200 0,5 0 1 -1,33 0
x4 2000 0,5 1 0 3,33 0
x5 700 1 0 0 0 1
Variáveis básicas: x2, x3 e x5
Variáveis não básicas: x1 e x4
Entra: x1
Sai: x3
Pivô = 0,5
Z = 30.000
O elemento a11 é igual 0,5 = ½. Assim, multiplicamos a linha um por 2 
(inverso multiplicativo de ½):
Linha um 
multiplicada 
por 2
200 × 2
= 400
0,5 × 2
=1
0 × 2
= 0
1 × 2
= 2
-1,33 × 2
= -2,66
0,2
= 0
49Modelos lineares e o método simplex
Então:
Nova 
linha um
400 1 0 2 -2,66 0
Zerando o elemento da linha zero:
Linha zero 30000 -4,5 0 0 50 0
Nova linha dois 
multiplicada por 4,5
400 × 
4,5
= 1 800
1 × 4,5
= 4,5
0 × 4,5
= 0
2 × 4,5
= 9
-2,66 
× 4,5
= - 12
0 × 4,5
= 0
Nova linha zero 
(soma da linha zero 
com a nova linha 
um multiplicada 
por 4,5)
30000 
+ 1800
= 
31800
- 4,5 
+ 4,5
= 0
0 + 0
= 0
0 + 9
= 9
50 – 12
= 38
0 + 0
= 0
Nas demais linhas, faremos o mesmo para zerar os coeficientes da coluna 
referente à variável x1:
Nova linha um 
multiplicada por -0,5
4000 × 
(- 0,5)
= - 200
1 × 
(- 0,5)
= - 0,5
0 × 
(- 0,5)
= 1
2 × 
(- 0,5)
= 0
-2,66 × 
(- 0,5)
= 3,33
0× 
(- 0,5)
= 0
Linha dois 2000 0,5 1 0 3,33 0
Nova linha dois 
(soma da nova linha 
um multiplicada por 
-0,5 com a linha dois)
-200 + 
2000
= 1800
-0,5 + 
0,5
= 0
0 + 1
= 1
-1 + 0
= -1
1,33 + 
3,33
= 4,66
0+0
= 0
Nova linha um 
multiplicada por -1
400 × 
(- 1)
1 × 
(- 1)
0 × 
(- 1)
2 × 
(- 1)
-2,66 
× (- 1)
0 × 
(- 1)
Linha três 700 1 0 0 0 1
Nova linha três (soma 
da nova linha um 
multiplicada por -1 
com a linha três)
-400 
+700
= 300
-1 + 1
= 0
0 + 0
= 0
-2 + 0
= -2
2,66 
+ 0
= 2,66
0 + 1
=1
Pesquisa operacional50
A seguir você encontra o resultado de todo esse processo:
x1 x2 x3 x4 x5
Z = 
31800
0 0 9 38 0
x3 400 1 0 2 - 2,66 0
x4 1800 0 1 -1 4,66 0
x5 300 0 0 -2 2,66 1
Variáveis básicas: x1, x2 e x5
Variáveis não básicas: x3 e x4
Solução ótima:
X1 = 400
X2 = 1.800
X5 = 300
Z = 31.800
Como todos os coeficientes da linha zero são positivos ou nulos, chegamos 
à seguinte solução ótima para o problema de PL:
X1 = 400
X2 = 1.800
Z = 31.800
Portanto, a solução ótima para atender à função objetivo será produzir 400 
sandálias e 1.800 sapatos, totalizando R$ 31.800,00 de lucro mensal.
Você acompanhou o processo de resolução de problema mediante as ite-
rações (tabelas), em que resolvemos um modelo de PL por meio de método de 
solução de sistemas de equações lineares. Resumidamente, esse foi o processo:
1. Formulamos o modelo apresentando o problema (recursos, disponibi-
lidade, situação atual do processo, lucro atual).
2. Montamos um modelo com variáveis de decisão do problema:
X1 – quantidade a produzir de sandálias;
X2 – quantidade a produzir de sapatos.
51Modelos lineares e o método simplex
3. Apresentamos a função objetivo matematicamente, com lucro:
Z = 12x1 + 15x2
4. Quanto às restrições, apresentamos a relação lógica que há no problema 
e acrescentamos as variáveis de folga, transformando as inequações 
em equações. Dessa forma, a estrutura lógica que era:
Emprego dos recursos ≤ disponibilidade
mudou para:
Emprego dos recursos + folga = disponibilidade.
Essa relação traduz como condição o seguinte raciocínio:
Se o emprego do recurso < disponibilidade, então a folga > 0.
Se o emprego do recurso = disponibilidade, então a folga = 0.
Nessa modelagem, a variável de folga pode ser expressa por uma variávelcuja forma seja igual à fabricação de cada produto.
Pesquisa operacional52
1. Com relação à programação linear 
(PL), marque a alternativa correta:
a) Programação linear (PL) é 
uma técnica de maximização 
aplicada em sistemas de 
equações lineares.
b) Trata-se de uma aplicação 
não matemática utilizada 
por profissionais para 
problemas relativos à 
produção, por exemplo.
c) É uma programação 
baseada em funções lineares 
utilizada em problemas em 
que não há restrições.
d) Quando se fala de problemas 
de otimização, significa que 
queremos exclusivamente 
maximizar os lucros.
e) Nos casos de maximização 
e minimização, é necessário 
verificar a função objetivo e 
as restrições apresentadas 
pelo sistema analisado.
2. Marque a opção que está relacionada 
corretamente às restrições em 
programação linear (PL):
a) Em um problema de PL, 
ou há a função objetivo 
ou há as restrições.
b) As restrições de igualdade são 
representadas por inequações.
c) Na prática, as limitações, que 
são denominadas restrições 
do problema PL, podem ser 
disponibilidade de matéria prima, 
capacidade da produção, mão 
de obra e limitações no preço.
d) O uso de s.a (“sujeita a”) indica 
que temos uma função objetivo 
que está sujeita à otimização.
e) São chamados de restrições 
de negatividade os termos 
x1, ≥ 0, x2 ≥ 0, ..., xn ≥ 0.
3. Observe as Figuras 1 e 2 e 
marque a alternativa que está 
relacionada corretamente 
53Modelos lineares e o método simplex
com a respectiva figura:
a) Figura 2: x1 = 10, x2 = 0, z = 30.
b) Figura 1: x1 = 4,5, x2 = 3,5, z = 28,5.
c) A Figura 1 é a resolução gráfica do problema de PL 
cuja maximização é: maxz = 4x1 + 3x2.
d) Na Figura 2, a s.a é 2x1 ≤ 9 X2 ≤ 7 X1 + x2 ≤ 8 X1, x2 ≥ 0.
4. Supondo que uma indústria de implementos agrícolas produza os modelos A 
1.
2.
Pesquisa operacional54
e B, que proporcionam lucros unitários de R$ 16,00 e R$ 30,00 respectivamente. 
A exigência de produção mínima mensal é de 20 unidades para o modelo A 
e de 120 para o modelo B. Cada tipo de implemento requer certa quantidade 
de tempo para a fabricação das partes que os compõem, para a montagem 
e para os testes de qualidade. Ou seja, uma dúzia de unidades do modelo 
A requer 3 horas para fabricar, 4 horas para montar e 1 hora para testar. 
Considerando, ainda, que uma dúzia de unidades do modelo B requer 3,5 
horas para fabricar, 5 horas para montar e 1,5 hora para testar. Contudo, 
durante o próximo mês, a fábrica terá disponível 120 horas de tempo de 
fabricação, 160 horas de montagem e 48 horas de testes de qualidade. 
De acordo com a imagem do gráfico, assinale a alternativa correta:
a) X1 é a quantidade de implementos do modelo A.
b) O tempo total gasto para a produção de 20 peças do modelo A é de 8 horas.
c) Para o próximo mês, há somente duas restrições: 160 horas de 
tempo para montagem e 48 horas para testes de qualidade.
d) A função objetivo é = 120x1 + 20x2.
5. Suponha que uma fábrica produza dois tipos de aço: normal e especial. Uma 
tonelada de aço normal requer 2 horas no forno de soleira aberta e 5 horas de 
55Modelos lineares e o método simplex
molho; uma tonelada de aço especial requer 2 horas no forno de soleira aberta 
e 3 horas de molho. O forno de soleira aberta está disponível 8 horas por dia, 
e o molho está disponível 15 horas por dia. O lucro para 1 tonelada de aço 
normal é de $120,00 e para 1 tonelada de aço especial é de $100,00. A empresa 
precisa produzir diariamente no mínimo 2 toneladas de aço normal e 1 tonelada 
de aço especial. Com base nesse problema, marque a alternativa correta.
a) 1 tonelada de aço normal é uma restrição.
b) X1 é a quantidade, em toneladas, de aço especial.
c) Para maximizar os lucros, é preciso produzir 2 toneladas de aço especial.
d) Produzir no mínimo 2 toneladas de aço normal é uma variável.
e) A disponibilidade diária de 8 horas para o forno de soleira e 15 
horas para o forno de molho é uma restrição do problema.
Pesquisa operacional56
BARBOSA, M. A. Iniciação à pesquisa operacional no ambiente de gestão. Curitiba: 
Intersaberes, 2015.
Leitura recomendada
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à pesquisa operacional. 9. ed. Porto Alegre: 
AMGH, 2013.
57Modelos lineares e o método simplex
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra.