Resolução de problemas de programação linear

Prévia do material em texto

PESQUISA OPERACIONAL 
AULA 02 
 
 
 
 
 
 
 
 
 
 
 
Prof. Ricardo Alexandre Deckmann Zanardini 
 
 
2 
CONVERSA INICIAL 
Em outra ocasião, aprendemos que as técnicas de otimização da 
pesquisa operacional podem ser utilizadas nas mais diversas aplicações reais. 
Vimos que o processo de modelar matematicamente um problema é muito 
importante. Como exemplo, foi apresentado de forma resumida o processo de 
produção de toalhas de rosto e de banho e, em seguida, formulamos dois 
exemplos relacionados a este processo. 
Nesta aula, iremos aprender a resolver problemas de programação linear. 
Inicialmente, estudaremos o método gráfico. Do ponto de vista prático, ele é 
pouco utilizado, pois está limitado a problemas com duas variáveis. No entanto, 
é um método importante para a resolução de pequenos problemas e, 
principalmente, para a compreensão do significado das variáveis, da função 
objetivo, das restrições e da solução ótima de um problema de PL. Em seguida, 
estudaremos o Método Simplex, primeiro e importante método destinado à 
resolução de problemas de programação linear. Como em muitos casos a 
solução analítica de problemas de programação linear é trabalhosa e sujeita a 
erros, veremos que é possível obtermos a solução de problemas de PL por meio 
da computação. 
TEMA 1 – MÉTODO GRÁFICO 
O método gráfico é a primeira forma de resolução de problemas de PL 
que iremos estudar. A sua importância consiste na representação gráfica de um 
problema de PL. Assim, fica mais fácil de compreendermos melhor os elementos 
associados a estes problemas: variáveis, função objetivo, restrições e solução 
ótima. 
Também é um método útil para a resolução de pequenos problemas de 
PL, quando temos duas variáveis e poucas restrições. 
Para resolvermos um problema por meio do método gráfico, o primeiro 
passo é representarmos dois eixos coordenados, um para cada variável. 
Chamando a primeira variável de x1 e a segunda variável de x2, temos: 
 
 
 
3 
Figura 1 – Gráfico 
 
Observe que estamos considerando apenas as porções positivas das 
retas associadas a cada uma das variáveis e a origem do sistema de eixos. Isto 
é feito porque temos as restrições de não negatividade, ou seja, x1 ≥ 0 e x2 ≥ 0. 
Caso tenhamos um problema em que valores negativos são considerados, 
utilizaremos um sistema de eixos coordenados, contendo as partes negativas 
também. Lembrando que a partir da origem, no eixo x1, os valores à direita são 
positivos e os valores à esquerda são negativos. Em relação ao eixo x2, os 
valores acima da origem são positivos e abaixo são negativos. 
Para que possamos compreender como é possível resolvermos 
problemas de PL por meio do método gráfico e para que possamos compreender 
melhor o significado dos elementos destes problemas, vamos considerar um 
exemplo anterior de nossos estudos. 
Exemplo 1: 
Uma indústria têxtil produz toalhas de banho e de rosto. No processo de 
fabricação, cada toalha de banho consome 400 g de tecido, enquanto que para 
a produção de cada toalha de rosto são necessários 180 g de tecido. O lucro da 
indústria para a venda de cada toalha de banho corresponde a R$ 15,00 e para 
cada toalha de rosto corresponde a R$ 7,00. Mensalmente, a indústria tem uma 
disponibilidade de matéria-prima equivalente a 5 toneladas de tecido. Quantas 
toalhas de rosto e quantas toalhas de banho deverão ser produzidas de modo 
 
 
4 
que o lucro mensal seja o maior possível? Formule o problema como um 
problema de programação linear e resolva-o pelo método gráfico. 
Resolução comentada: 
Anteriormente, vimos que a formulação deste problema corresponde a 
max L = 15b + 7r 
s.a. 0,4b + 0,18r ≤ 5000 
b ≥ 0, r ≥ 0 
onde b indica a quantidade de toalhas de banho a serem produzidas e r 
indica a quantidade de toalhas de rosto a serem produzidas. 
Precisamos agora de um sistema de eixos coordenados em que cada 
uma das variáveis está associada a cada um dos eixos. Vamos considerar b 
como sendo o eixo horizontal e r o eixo vertical. 
Figura 2 – Gráfico 
 
 
 
 
5 
 Observe que, se não temos restrições no problema, b e r podem crescer 
infinitamente e qualquer ponto da forma P(b, r) é uma possível solução para o 
problema, já que não limitações. 
Figura 3 – Gráfico 
 
No entanto, a partir do momento que adicionamos uma ou mais restrições, 
passamos a limitar o problema e, consequentemente, limitarmos as possíveis 
soluções do problema, caso existam, a uma região denominada de região 
factível (ou região viável). 
Para entendermos melhor, vamos fazer a representação gráfica da 
restrição: 
0,4b + 0,18r ≤ 5000 
O primeiro passo é escrevermos uma equação associada à inequação 
0,4b + 0,18r ≤ 5000 para que possamos fazer a representação da reta associada 
à restrição. Sendo assim, temos: 
0,4b + 0,18r = 5000. 
Sabemos que para representarmos graficamente uma reta, precisamos 
de dois pontos pertencentes a esta reta. Há uma infinidade de pontos possíveis 
a serem escolhidos. Para facilitarmos os cálculos, primeiro faremos b = 0 e 
 
 
6 
iremos obter o respectivo valor de r. Em seguida, faremos r = 0 para obtermos o 
respectivo valor de b e, assim, termos os dois pontos necessários. 
Para b = 0, temos: 
 
0,4b + 0,18r = 5000 
0,4 (0) + 0,18r = 5000 
0 + 0,18r = 5000 
0,18r = 5000 
r = 5000/0,18 
r = 27777,78 
Logo, o primeiro ponto é A (0; 27777,78), onde o ponto e vírgula separa 
as coordenadas do ponto e a vírgula separa as casas decimais. 
Para r = 0, temos 
0,4b + 0,18r = 5000 
0,4b + 0,18 (0) = 5000 
0,4b + 0 = 5000 
0,4b = 5000 
b = 5000/0,4 
b = 12500 
Assim, temos o segundo ponto B (12500; 0). 
Vamos representar os pontos A (0; 27777,78) e B (12500; 0) no sistema 
de eixos coordenados. 
 
 
 
7 
Figura 4 – Gráfico 
 
Para a representação da restrição, basta considerar a reta que passa 
pelos pontos A e B. Como a restrição consiste em 0,4b + 0,18r ≤ 5000, ou seja, 
é uma desigualdade com sinal de menor ou igual, temos uma região que fica 
abaixo desta reta como sendo a região viável, ou seja, a região que limita as 
possíveis soluções do problema. Por este motivo, desenhamos na reta uma 
pequena seta apontando para a esquerda e para baixo, indicando de que lado 
da reta estão os valores que satisfazem a desigualdade. 
 
 
 
8 
Figura 5 – Gráfico 
 
Considerando ainda as restrições de não negatividade b ≥ 0 e r ≥ 0, a 
região factível está abaixo da restrição, acima do eixo b e à direita do eixo r. 
Figura 6 – Gráfico 
 
 
 
9 
É importante ressaltar que como a restrição b ≥ 0 é uma restrição de maior 
ou igual, colocamos uma pequena seta apontando para a esquerda no eixo r 
indicando de que lado da reta estão os valores de b maiores ou igual a zero e 
como r ≥ 0, colocamos no eixo b uma seta para cima indicando a região que 
contém os valores de r maiores ou igual a zero. 
O significado das restrições de um problema de PL é a limitação da região 
que contém as soluções do problema. Estamos falando em “soluções”, pois nos 
referimos aos pontos que estão na região factível, ou seja, qualquer ponto da 
forma P (b, r) que satisfaz as restrições do problema. 
Dentro da região factível, temos infinitas soluções. No entanto, 
precisamos obter a solução que maximiza a função objetivo e, neste caso, 
podemos ter uma única solução, infinitas soluções ou podemos ter também 
problemas que não possuem solução ótima. 
Em particular, no caso do nosso exemplo, para obtermos a solução ótima, 
vamos fazer a representação da função objetivo. 
Graficamente, a função objetivo é um vetor que tem as componentes 
dadas pelos coeficientes das variáveis. Assim, como a função objetivo do nosso 
exemplo é: 
max L = 15b + 7r 
o respectivo vetor corresponde a: 
v = (15, 7). 
Como os elementos de v são bem menores do que as coordenadas dos 
pontos A e B, e como precisamos da direção de crescimento da função objetivo, 
ou seja, da direçãodo vetor v, para que possamos visualizar o vetor, vamos 
considerar um múltiplo de v dado por kv, onde k é um número real positivo, que 
tem a seguinte representação: 
 
 
 
10 
Figura 7 – Gráfico 
 
O vetor v, assim como o vetor kv, indica o crescimento da função objetivo, 
ou seja, é um vetor que aponta para a solução ótima. E como faremos para 
identificar qual é a solução ótima? Basta considerarmos retas paralelas, 
representadas a seguir por linhas pontilhadas, ortogonais ao vetor kv, ou seja, 
retas que formam 90° com o vetor kv, e, a partir delas, vamos obter a solução do 
problema. 
 
 
 
11 
Figura 8 – Gráfico 
 
Figura 9 – Gráfico 
 
 
 
 
12 
Figura 10 – Gráfico 
 
Figura 11 – Gráfico 
 
Note que na medida em que fomos traçando as retas paralelas, ortogonais 
ao vetor kv no sentido do crescimento do vetor, o ponto da região factível 
 
 
13 
associado à reta mais distante da origem do vetor é o ponto A (0; 27777,78). 
Assim, podemos dizer que este ponto maximiza a função objetivo e, portanto, é 
a solução ótima do problema. 
Assim, para que o lucro mensal da indústria seja o maior possível, a 
empresa precisa produzir 0 toalhas de banho e 27777 toalhas de rosto. Como 
não podemos ter toalhas fracionadas (0,78 de uma toalha), consideramos 
apenas a parte inteira da solução. 
E o valor da função objetivo? Basta substituirmos b por 0 e r por 27777,78 
na função objetivo ou, para estar de acordo com o valor inteiro, podemos 
substituir r por 27777. Vamos considerar r = 27777,78. Assim, temos 
L = 15b + 7r 
L = 15(0) + 7(27777,78) 
L = 0 + 194444,50 
L = 194444,50 
Observe que a solução de um problema de PL sempre estará em um 
vértice da região factível. Podemos ter uma única solução ou infinitas soluções. 
O caso onde temos infinitas soluções ocorre quando a restrição que contém 
solução ótima também é ortogonal ao vetor kv. 
Como a solução ótima está em um vértice da região factível, uma outra 
maneira de obtermos esta solução é substituirmos cada vértice da região factível 
na função objetivo e identificar em qual deles temos o maior lucro. 
Para este exemplo, os vértices são: O (0, 0), A (0; 27777,78) e B (12500, 
0). 
Considerando O (0, 0), temos: 
L = 15b + 7r 
L = 15(0) + 7(0) 
L = 0 + 0 
L = 0 
ou seja, para o vértice O (0, 0), L = 0. 
Para o vértice A (0; 27777,78), temos: 
L = 15b + 7r 
L = 15(0) + 7(27777,78) 
L = 0 + 194444,5 
L = 194444,5 
Para B (12500, 0), temos: 
 
 
14 
L = 15b + 7r 
L = 15(12500) + 7(0) 
L = 187500 + 0 
L = 187500 
 Assim, a solução ótima ocorre no vértice A (0; 27777,78), onde o lucro 
máximo é dado por L = 194444,5. 
Vamos considerar agora o mesmo exemplo, mas com uma nova restrição, 
uma limitação na produção máxima de toalhas de rosto. 
Exemplo 2: 
Uma indústria têxtil produz toalhas de banho e de rosto. No processo de 
fabricação, cada toalha de banho consome 400 g de tecido, enquanto que para 
a produção de cada toalha de rosto são necessários 180 g de tecido. O lucro da 
indústria para a venda de cada toalha de banho corresponde a R$ 15,00 e para 
cada toalha de rosto corresponde a R$ 7,00. Mensalmente, a indústria tem uma 
disponibilidade de matéria-prima equivalente a 5 toneladas de tecido. A indústria 
tem um limite de produção de no máximo 20000 toalhas de rosto. Quantas 
toalhas de rosto e quantas toalhas de banho deverão ser produzidas de modo 
que o lucro mensal seja o maior possível? Formule o problema como um 
problema de programação linear e resolva-o pelo método gráfico. 
Resolução comentada: 
Anteriormente, chegamos à conclusão de que a formulação do problema 
é dada por 
max L = 15b + 7r 
s.a. 0,4b + 0,18r ≤ 5000 
r ≤ 20000 
b ≥ 0, r ≥ 0 
onde b é a quantidade de toalhas de banho a serem produzidas e r a quantidade 
de toalhas de rosto a serem produzidas. 
 A partir das restrições do problema, vimos no Exemplo 1 que a restrição 
0,4b + 0,18r ≤ 5000 corresponde à região do plano abaixo da reta que passa 
pelos pontos A (0; 27777,78) e B (12500; 0). Como a restrição é de menor ou 
igual, os pontos pertencentes à reta também satisfazem a desigualdade. 
 
 
 
15 
Figura 12 – Gráfico 
 
Neste exemplo, temos também a restrição relacionada à quantidade 
máxima de toalhas de rosto a serem produzidas: 
r ≤ 20000 
Precisamos representar graficamente esta restrição. Como r ≤ 20000 para 
qualquer valor de b, temos que r = 20000 é uma reta paralela ao eixo b e que 
passa pelo ponto C (0, 20000). 
 
 
 
16 
Figura 13 – Gráfico 
 
 Temos ainda que a restrição é de menor ou igual. Assim, precisamos 
traçar a reta que passa por C e é paralela ao eixo b e indicaremos com uma seta 
para baixo a região do plano que satisfaz esta restrição. 
Figura 14 – Gráfico 
 
 
 
17 
A região factível está limitada pelos eixos b e r e pelas restrições 0,4b + 
0,18r ≤ 5000 e r ≤ 20000. 
Figura 15 – Gráfico 
 
Como a solução do problema está em um dos vértices da região factível, 
precisamos obter as coordenadas do vértice D associado à intersecção das retas 
0,4b + 0,18r = 5000 e r = 20000. Como r = 20000, basta substituirmos este valor 
na equação 0,4b + 0,18r = 5000 para obtermos o respectivo valor de b. 
0,4b + 0,18r = 5000 
0,4b + 0,18(20000) = 5000 
0,4b + 3600 = 5000 
0,4b = 5000 – 3600 
0,4b = 1400 
b = 1400/0,4 
b = 3500 
Logo, o vértice D tem coordenadas (3500; 20000) 
 
 
 
18 
Figura 16 – Gráfico 
 
Agora que já sabemos as coordenadas dos vértices da região factível, ou 
seja, O(0, 0), B(12500; 0), C(0; 20000) e D(3500; 20000), podemos obter a 
solução ótima do problema de duas formas: graficamente, considerando o vetor 
kv associado à função objetivo ou substituindo as coordenadas de cada vértice 
na função objetivo L = 15b + 7r. É importante comentar que o ponto A(0; 
27777,78) está fora da região factível e neste caso não pode ser considerado 
uma solução do problema. 
Considerando o vetor kv = k(15, 7) e as respectivas retas paralelas que 
são ortogonais a este vetor, temos: 
 
 
 
19 
Figura 17 – Gráfico 
 
Figura 18 – Gráfico 
 
 
 
 
 
20 
Figura 19 – Gráfico 
 
 
 
 
21 
Figura 20 – Gráfico 
 
 
 
 
 
22 
Figura 21 – Gráfico 
 
 
Fica fácil perceber que a solução ótima do problema está no vértice 
D(3500, 20000), pois é o vértice mais afastado seguindo a direção do vetor kv. 
Assim, temos que a solução ótima para este problema consiste na produção de 
3500 toalhas de banho e 20000 toalhas de rosto. O lucro mensal máximo é 
calculado a partir da substituição de b = 3500 e r = 20000 na função objetivo L = 
15b + 7r. 
L = 15b + 7r 
L = 15(3500) + 7(20000) 
L = 52500 + 140000 
L = 192500 
ou seja, o lucro máximo corresponde a R$ 192500,00. 
 Comparando a solução obtida no Exemplo 1 com a solução do 
Exemplo 2, a restrição r ≤ 20000 limitou a produção máxima de toalhas de rosto 
e, consequentemente, reduziu o lucro mensal máximo. No entanto, esta restrição 
pode estar relacionada a uma estratégia da empresa ou a uma demanda máxima 
para as toalhas de rosto. 
 
 
23 
A seguir, estudaremos o Método Simplex, um método destinado à 
resolução de problemas de programação linear onde podemos resolver 
problemas com mais restrições e mais do que duas variáveis. 
TEMA 2 – MÉTODO SIMPLEX 
O Método Simplex é muito utilizado na resolução de problemas de 
programação linear. Foi desenvolvido por George B. Dantzig, e marca o início da 
pesquisa operacional. Para a utilização do método, partimos de uma solução 
inicial básica onde as variáveis do problema são iguais a zero e vamos 
caminhando pelos vértices da região factível até obtermos a solução ótima. O 
Método Simplex pode ser utilizado em problemas com duas ou mais variáveis. 
Para que possamos entender como o método funciona, vamos considerar 
o seguinte exemplo: 
Exemplo 1: 
Uma indústria têxtil produz toalhas de banho e de rosto. No processo de 
fabricação,cada toalha de banho consome 400 g de tecido enquanto que para 
a produção de cada toalha de rosto são necessários 180 g de tecido. O lucro da 
indústria para a venda de cada toalha de banho corresponde a R$ 15,00 e para 
cada toalha de rosto corresponde a R$ 7,00. Mensalmente, a indústria tem uma 
disponibilidade de matéria-prima equivalente a 5 toneladas de tecido. A indústria 
tem um limite de produção de no máximo 20000 toalhas de rosto. Quantas 
toalhas de rosto e quantas toalhas de banho deverão ser produzidas de modo 
que o lucro mensal seja o maior possível? Formule o problema como um 
problema de programação linear e resolva-o por meio do Método Simplex. 
Resolução comentada: 
Sabemos que a formulação deste problema é 
max L = 15b + 7r 
s.a. 0,4b + 0,18r ≤ 5000 
r ≤ 20000 
b ≥ 0, r ≥ 0 
Para podermos resolver o problema, precisamos de equações 
equivalentes às inequações de cada uma das restrições. Assim, precisamos 
adicionar uma variável de folga para cada restrição de <= (menor ou igual). A 
variável de folga indica a quantidade que falta para que a igualdade entre os dois 
membros da inequação seja verificada. Como a folga não representa lucro, o 
 
 
24 
coeficiente de cada variável de folga na função objetivo é sempre igual a zero. 
Logo, acrescentando as variáveis de folga f1 e f2, temos a seguinte formulação. 
max L = 15b + 7r + 0f1 + 0f2 
s.a. 0,4b + 0,18r + f1 = 5000 
r + f2 = 20000 
b ≥ 0, r ≥ 0 
Agora que temos a formulação, vamos criar uma tabela contendo os 
coeficientes da função objetivo, das restrições e contendo os termos 
independentes. 
Tabela 1 – Tabela com coeficientes, restrições e termos independentes 
 b r f1 f2 
L0 0 -15 -7 0 0 
L1 5000 0,4 0,18 1 0 
L2 20000 0 1 0 1 
Em função das características do Método Simplex, os coeficientes da 
função objetivo estão na tabela com os respectivos sinais invertidos. Isto ocorre 
para que a cada iteração do método, o valor de L, número que aparece no canto 
superior esquerdo, esteja com o sinal correto. Para facilitar os cálculos que 
veremos a seguir, é importante colocarmos nomes em cada uma das linhas da 
tabela (L0, L1 e L2). 
As variáveis b e r são as de variáveis não básicas. Toda variável não 
básica tem valor igual a zero. Assim, b = 0, r = 0 e, consequentemente, L = 0. As 
variáveis básicas f1 e f2 possuem seus valores apresentados na primeira coluna 
das linhas L1 e L2: f1 = 5000 e f2 = 20000. 
Agora que temos a tabela inicial, vamos começar as iterações do Método 
Simplex, lembrando que o nosso objetivo é maximizar a função objetivo. Assim, 
o primeiro passo é identificar qual é o coeficiente da função objetivo que aumenta 
mais o valor de L. É importante lembrar que na tabela os coeficientes da função 
objetivo estão com os sinais trocados. Assim, o valor mais negativo é o que mais 
aumenta o valor da função objetivo no momento. Olhando a primeira linha da 
tabela, podemos concluir que -15 é o valor procurado. Como -15 é o coeficiente 
de b, dizemos que a variável b irá entrar na base, ou seja, passará a fazer parte 
da solução do problema. Mas para que uma variável não básica entre na base, 
uma variável básica precisa sair da base. No momento, as variáveis básicas são 
 
 
25 
f1 e f2. A variável que sai da base é aquela cujo recurso limita primeiro o 
problema. Para sabermos qual é o máximo que podemos produzir referente à 
variável que está entrando na base, precisamos dividir o total dos recursos 
disponíveis pela quantidade utilizada pela variável. Assim, vamos dividir 5000 
por 0,4 e 20000 por 0, lembrando que a divisão por 0 não existe, mas quando o 
denominador é um número muito próximo de 0, o resultado da divisão é infinito, 
ou seja, uma quantidade muito grande. Assim, o menor resultado que indica qual 
é a variável que deixará a base corresponde à divisão de 5000 por 0,4. Logo, f1 
é a variável que sai da base. Observe que quando olhamos a coluna referente à 
variável f1, identificamos em qual linha o coeficiente é igual a 1. 
Precisamos agora identificar quem é o pivô, elemento que está na 
intersecção da coluna da variável que entra com a linha da variável que sai. 
Tabela 2 – Identificação do pivô 
 ↓ 
b 
 
r 
 
f1 
 
f2 
L0 0 -15 -7 0 0 
 ← L1 5000 0,4 0,18 1 0 
L2 20000 0 1 0 1 
 
5000/0,4 = 12500 
20000/0 = Não existe 
Entra: b 
Sai: f1 
Pivô: 0,4 
Devemos sempre transformar o pivô em 1. Como o pivô é igual a 0,4, 
basta dividirmos toda a linha L1 por 0,4, ou seja, 5000 / 0,4 = 12500, 0,4 / 0,4 = 
1, 0,18 / 0,4 = 0,45, 1 / 0,4 = 2,5 e 0 / 0,4 = 0, o que resulta em 
 
 
 
26 
Tabela 3 – Transformação do pivô em “1” 
 b r f1 f2 
L0 0 -15 -7 0 0 
L1 12500 1 0,45 2,5 0 
L2 20000 0 1 0 1 
Agora vamos zerar os demais coeficientes da coluna da variável básica. 
Esta é uma das características da variável básica, o pivô é igual a 1 e os demais 
elementos são iguais a zero. 
Observe que o elemento da coluna referente a b que está na linha L2 já é 
igual a zero. Assim, basta zerarmos o coeficiente da linha L0. Vamos multiplicar 
a linha do pivô (linha L1) pelo coeficiente da linha a ser zerada (linha L0) com o 
sinal invertido, ou seja, vamos multiplicar por 15. Em seguida, precisamos somar 
os resultados com os respectivos coeficientes da linha L0. 
As operações a serem feitas são: 
12500 . 15 + 0 = 187500 
1 . 15 + (-15) = 0 
0,45 . 15 + (-7) = -0,25 
2,5 . 15 + 0 = 37,5 
0 . 15 + 0 = 0 
A partir destes resultados, temos a seguinte tabela referente ao final da 
primeira iteração: 
Tabela 4 – Resultado 
 b r f1 f2 
L0 187500 0 -0,25 37,5 0 
L1 12500 1 0,45 2,5 0 
L2 20000 0 1 0 1 
Olhando na linha L0, podemos perceber que o coeficiente de r é negativo 
(-0,25). Portanto, precisamos realizar mais uma iteração do Método Simplex. A 
variável que entra na base é r e a variável que sai da base pode ser b ou f2. 
Precisamos fazer as seguintes divisões para identificarmos qual variável básica 
deixará a base: 
 
 
 
 
27 
12500 / 0,45 = 27777,78 
20000 / 1 = 20000 
Como o menor valor resultado obtido é 20000, temos que f2 deixará a 
base, pois esta é a variável básica associada à linha L2. O pivô é o número que 
está na coluna de r e na linha L2, ou seja, o pivô é igual a 1. 
Tabela 5 – Iteração para o pivô 
 
B 
↓ 
R 
 
f1 
 
f2 
L0 187500 0 -0,25 37,5 0 
L1 12500 1 0,45 2,5 0 
← L2 20000 0 1 0 1 
 
Entra: r 
Sai: f2 
Pivô: 1 
 Precisamos zerar 0,45 e -0,25. 
 Inicialmente, vamos multiplicar a linha L2 por -0,45 e vamos somar com a 
linha L1. 
 As operações são: 
-0,45 . 20000 + 12500 = 3500 
-0,45 . 0 + 1 = 1 
-0,45 . 1 + 0,45 = 0 
-0,45 . 0 + 2,5 = 2,5 
-0,45 . 1 + 0 = -0,45 
 Assim, a tabela com a nova linha L1 é: 
 
 
 
28 
Tabela 6 – Tabela com nova linha L1 
 b r f1 f2 
L0 187500 0 -0,25 37,5 0 
L1 3500 1 0 2,5 -0,45 
L2 20000 0 1 0 1 
Agora vamos multiplicar a linha L2 por 0,25 e vamos somar com a linha 
L0. 
 As operações feitas são: 
0,25 . 20000 + 187500 = 192500 
0,25 . 0 + 0 = 0 
0,25 . 1 + (-0,25) = 0 
0,25 . 0 +37,5 = 37,5 
0,25 . 1 + 0 = 0,25 
 A tabela referente ao final da segunda iteração é: 
Tabela 7 – Tabela final da segunda iteração 
 b r f1 f2 
L0 192500 0 0 37,5 0,25 
L1 3500 1 0 2,5 -0,45 
L2 20000 0 1 0 1 
 Como não temos coeficientes negativos na linha L0, a solução ótima é: 
b = 3500 
c = 20000 
L = 192500 
Vimos como é possível resolvermos problemas de programação linear por 
meio do Método Simplex. Na prática, problemas de PL são resolvidos pelo 
Método Simplex, mas com o uso de recursos computacionais que auxiliam na 
obtenção da solução de uma forma rápida e eficiente. 
TEMA 3 – RECURSOS COMPUTACIONAIS PARA A RESOLUÇÃO DE 
PROBLEMAS DE PROGRAMAÇÃO LINEAR 
Um problema de programação linear pode ser resolvido pelo método 
simplex: ele consiste em realizarmos operações de soma, subtração, 
multiplicação e divisão na função objetivo e nas restrições seguindo alguns29 
critérios. A resolução manual pode ser feita, mas é trabalhosa e quanto maior o 
número de variáveis e de restrições, maior é o tempo e o esforço para obtermos 
a solução. Por isso, existem alguns softwares destinados à resolução, não 
apenas de problemas deste tipo, mas de muitos outros problemas relacionados 
à pesquisa operacional. Alguns softwares são gratuitos e alguns deles são 
pagos. No decorrer de nossos estudos, utilizaremos bastante a biblioteca PuLP 
destinada à resolução de problemas de programação linear. Esta biblioteca foi 
desenvolvida para ser utilizada por uma importante linguagem de programação, 
o Python. Veremos nesta aula como é possível utilizar a biblioteca PuLP. 
Uma outra solução gratuita e muito utilizada é a Aplicação PO1. Podemos 
utilizar esta aplicação para a resolução de problemas de programação linear, 
problemas de transporte, árvore mínima, fluxo máximo, além de outros tipos de 
problemas de PO. 
Figura 22 – Interface da Aplicação PO 
 
Fonte: Maurício Pereira dos Santos. 
Outro software bastante útil é o WinQSB, um software gratuito 
desenvolvido por Yih-Long Chang. É um pacote de ferramentas com o intuito de 
servir de suporte para a tomada de decisões baseada em problemas de pesquisa 
operacional. O problema é que este software foi desenvolvido para ambientes 
32 bits e atualmente a maioria dos sistemas são 64 bits. Além destes, existe 
também o Solver do Microsoft® Office Excel, Linear Interactive and Discret 
 
1 Disponível em: <mpsantos.com.br>. Acesso em: 15 dez. 2021. 
 
 
30 
Optimizer (LINDO), Language for Interactive General Optimizer (LINGO), entre 
outros. 
O uso de softwares na pesquisa operacional é de extrema importância, 
pois precisamos resolver problemas de uma forma rápida e sem erros. 
TEMA 4 – INTRODUÇÃO AO PYTHON EM PROBLEMAS DE PROGRAMAÇÃO 
LINEAR 
O Python é uma importante linguagem de programação. É uma linguagem 
simples e muito poderosa. Seu início foi em 1991, no Centrum Wiskunde & 
Informatica, CWI, um centro de matemática e computação localizado em 
Amsterdam, na Holanda. O pioneiro no desenvolvimento da linguagem foi o 
matemático Guido Van Rossum e o objetivo principal era a criação de uma 
linguagem interpretada, mas com comandos simples de entender. Para 
resolvermos problemas de programação linear utilizando o Python, não 
precisamos ter conhecimentos relacionados à programação de computadores. 
Iremos utilizar a bibliotecas PuLP desenvolvida para o Python. 
Antes de aprendermos a utilizar esta biblioteca, precisamos aprender a 
acessar um serviço gratuito hospedado pelo Google que tem como objetivo 
incentivar a aprendizagem de máquina e a inteligência artificial. Este ambiente é 
o Google Colaboratory, mais conhecido como Google Colab. 
Para trabalharmos com o Python, no navegador, precisamos acessar 
esse site2. 
Na página inicial do Google Colab, são apresentadas informações 
importantes e alguns exemplos do que pode ser feito. 
 
 
2 Disponível em: <colab.research.google.com>. Acesso em: 15 dez. 2021. 
 
 
31 
Figura 23 – Página Inicial do Google Colab 
 
Fonte: Google/Ricardo Zanardini. 
Para utilizarmos o ambiente, precisamos efetuar o login com uma conta 
Google. Vamos clicar em “Fazer login”, digitar o e-mail ou clicar em um já 
existente e digitar a senha. 
Figura 24 – Login 
 
Fonte: Google/Ricardo Zanardini. 
Caso já tenha utilizado o Google Colab, na página inicial aparecerão os 
projetos recentes. 
Caso contrário, teremos as informações iniciais relacionadas ao Colab. 
 
 
32 
Figura 25 – Projetos Recentes 
 
Fonte: Google/Ricardo Zanardini. 
Para começarmos a utilizar o Colab, o primeiro passo é clicarmos em 
Arquivo e em seguida em Novo notebook. 
Figura 26 – Tela do Google Colab, com a função “Novo notebook” destacada 
 
Fonte: Google/Ricardo Zanardini. 
 
 
33 
 Após estes passos, estamos prontos para utilizarmos a biblioteca PuLP. 
TEMA 5 – USO DO PYTHON EM PROBLEMAS DE PROGRAMAÇÃO LINEAR 
Utilizamos a biblioteca “PuLP” do Python para resolvermos problemas de 
otimização. Veremos como é possível resolver problemas de programação linear 
por meio do Python. 
Exemplo 1: Uma indústria têxtil produz toalhas de banho e de rosto. No 
processo de fabricação, cada toalha de banho consome 400 g de tecido, 
enquanto que para a produção de cada toalha de rosto são necessários 180 g 
de tecido. O lucro da indústria para a venda de cada toalha de banho 
corresponde a R$ 15,00 e para cada toalha de rosto corresponde a R$ 7,00. 
Mensalmente, a indústria tem uma disponibilidade de matéria-prima equivalente 
a 5 toneladas de tecido. A indústria tem um limite de produção de no máximo 
20000 toalhas de rosto. Quantas toalhas de rosto e quantas toalhas de banho 
deverão ser produzidas de modo que o lucro mensal seja o maior possível? 
Formule o problema como um problema de programação linear e resolva-o 
utilizando a biblioteca PuLP do Python. 
Resolução comentada: 
Vimos que a formulação relacionada a este problema é dada por 
max L = 15b + 7r 
s.a. 0,4b + 0,18r ≤ 5000 
r ≤ 20000 
b ≥ 0, r ≥ 0 
Para resolvermos este problema, o primeiro passo é instalarmos o pacote 
PuLP executando os seguintes comandos em uma célula de código do Google 
Colab: 
import sys 
!{sys.executable} -m pip install Pulp 
 
 
 
34 
Figura 27 – Execução dos comandos do exemplo 
 
Fonte: Google/Ricardo Zanardini. 
Agora que já instalamos a biblioteca PuLP, podemos resolver o problema. 
A sequência de comandos é: 
from pulp import * 
prob = LpProblem('Exemplo1',LpMaximize) 
x1=LpVariable("Toalha de Banho",0) 
x2=LpVariable("Toalha de Rosto",0) 
prob += 15*x1 + 7*x2 
prob += 0.4*x1 + 0.18*x2 <= 5000 
prob += x2 <= 20000 
prob.solve() 
for v in prob.variables(): 
 print(v.name, "=", v.varValue) 
print("Lucro máximo = ", value(prob.objective)) 
 
 
 
35 
Figura 28 – Código 
 
Fonte: Google/Ricardo Zanardini. 
A solução consiste na produção de 3500 toalhas de banho, 20000 toalhas 
de rosto e o lucro máximo referente a estas quantidades corresponde a R$ 
192500,00. 
Seguindo estes comandos e alterando apenas as variáveis, a função 
objetivo e as restrições, é possível resolvermos problemas de programação 
linear de uma forma bastante fácil, rápida e eficiente. 
FINALIZANDO 
Chegamos ao final da aula sobre pesquisa operacional. Começamos 
estudando o método gráfico e, a partir deste método, conseguimos entender 
melhor o significado das variáveis, restrições, função objetivo e da solução ótima 
de um problema de Programação Linear. Em seguida, vimos como é possível 
utilizar o Método Simplex na resolução de problemas de PL. Apresentamos 
diversos softwares destinados à resolução de problemas de pesquisa 
operacional e, finalmente, vimos que é possível utilizarmos a biblioteca PuLP 
desenvolvida para o Python para a resolução de problemas de programação 
linear.