Unidade III Programação Linear Metodos e Aplicações

Prévia do material em texto

Simulação e Tomada 
de Decisão
Material Teórico
Responsável pelo Conteúdo:
Prof. Ms. Roberto Luiz Garcia Vichinisky
Revisão Textual:
Profa. Ms. Fátima Furlan
Programação Linear: Métodos e Aplicações
• Método Simplex
• Ferramentas Computacionais 
• Roteiro para Utilização do Software “SIMPLEX in PHP”
 · O objetivo desta unidade é detalhar os procedimentos para aplicação 
do método SIMPLEX para a resolução de problemas de Programação 
Linear, introduzindo os conceitos de análise e interpretações econômi-
cas a partir dessa aplicação. 
OBJETIVO DE APRENDIZADO
Programação Linear: Métodos 
e Aplicações
Orientações de estudo
Para que o conteúdo desta Disciplina seja bem 
aproveitado e haja uma maior aplicabilidade na sua 
formação acadêmica e atuação profissional, siga 
algumas recomendações básicas: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
da sua rotina. Por exemplo, você poderá determinar um dia e 
horário fixos como o seu “momento do estudo”.
Procure se alimentar e se hidratar quando for estudar, lembre-se de que uma 
alimentação saudável pode proporcionar melhor aproveitamento do estudo.
No material de cada Unidade, há leituras indicadas. Entre elas: artigos científicos, livros, vídeos e 
sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você também 
encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão sua 
interpretação e auxiliarão no pleno entendimento dos temas abordados.
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discussão, 
pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o contato 
com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e aprendizagem.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Não se esqueça 
de se alimentar 
e se manter 
hidratado.
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Programação Linear: Métodos e Aplicações
Contextualização
Para resolvermos problemas de programação linear, cujos modelos matemáticos 
possuam apenas duas variáveis de decisão, podemos aplicar, com certo grau de 
facilidade, as técnicas gráfica e analítica. No entanto, para problemas que envolvem 
três ou mais variáveis de decisão, essas técnicas são inviáveis. Nesses casos, lança-
se mão de outros recursos, como por exemplo, o método SIMPLEX.
Esse método, desenvolvido em 1947 pelo matemático norte-americano George 
Dantzig, vem sendo utilizado desde então para a solução de problemas complexos 
que envolvem muitas variáveis de decisão, demonstrando-se bastante eficiente 
nesse aspecto. Porém, devido ao grande volume de dados manipulados durante a 
resolução de problemas complexos, o método SIMPLEX é normalmente executado 
em computadores, por meio de softwares específicos ou aplicativos matemáticos 
que oferecem ferramentas para sua implementação. Entretanto, para problemas 
pequenos, a execução manual desse método ainda é uma opção viável.
No ambiente empresarial, por razões de produtividade e precisão, obviamente 
a resolução de problemas de programação linear não é realizada de forma 
manual. Nesse contexto, utilizam-se programas de computadores, onde o modelo 
matemático do problema é introduzido e as soluções são rapidamente apresentadas, 
permitindo ao usuário realizar diversas simulações a partir de versões modificadas 
do modelo matemático original, o que seria impraticável caso a resolução fosse 
realizada manualmente.
Entretanto, o conhecimento dos métodos de resolução de problemas de 
programação linear, assim como a habilidade para aplicá-los sem o uso de 
ferramentas computacionais, são requisitos fundamentais para que o profissional 
desenvolva o seu pensamento crítico e expanda sua capacidade de análise em 
relação aos problemas organizacionais complexos
8
9
Método Simplex
O método Simplex, desenvolvido em 1947 pelo matemático norte-americano 
George Bernard Dantzig, é um procedimento algébrico para solucionar problemas 
de programação linear. Baseia-se na aplicação de um algoritmo com o propósito 
de se obter a otimização de sistemas de equações lineares.
Em linhas gerais, o método Simplex consiste em executar um algoritmo de forma 
iterativa (repetidamente), até que se encontre a solução ótima para um determinado 
problema de programação linear a partir de seu modelo matemático. A Figura 1 
apresenta o fluxograma genérico que ilustra o princípio básico do método Simplex.
INÍCIO
Obter modelo
matemático
Encontrar
solução viável
Solução
ótima?
Encontrar
solução viável
melhor FIM
Figura 1 - Fluxograma genérico do método Simplex
O método Simplex foi concebido para resolver problemas de maximização, cujas 
inequações de restrição, presentes em seus modelos matemáticos, devem conter 
apenas operadores relacionais do tipo “menor ou igual” (≤ ), com exceção da restri-
ção de não negatividade das variáveis de decisão. Portanto, modelos matemáticos 
que não atendem essas condições, devem ser adequadamente transformados.
9
UNIDADE Programação Linear: Métodos e Aplicações
Aplicação do Método Simplex 
Para demonstrarmos a aplicação do método Simplex, vamos tomar como 
exemplo o seguinte problema de maximização:
Uma empresa fabrica dois produtos: A e B, sendo que o lucro por unidade do 
produto A é R$ 10,00 e do produto B é R$ 8,00. Na manufatura desses produtos são 
empregadas apenas duas matérias-primas: MP1 e MP2, na seguinte proporção: 3 
unidades de MP1 e 3 unidades de MP2 para cada unidade do produto A e 6 unidades 
de MP1 e 3 unidades de MP2 para cada unidade do produto B. A empresa possui 
um estoque de 300 unidades de MP1 e 480 unidades de MP2. Considerando que as 
variáveis de decisão são X1 (quantidade de A a ser produzida) e X2 (quantidade de B 
a ser produzida), quais devem ser as quantidades de A e B a serem produzidas para 
que a empresa obtenha o lucro máximo?
Vamos agora aplicar os quatro passos básicos do método Simplex para resolver 
esse problema.
Passo 1 - Elaboração do modelo matemático
O primeiro passo para iniciarmos a resolução de um problema de programação 
linear, independentemente do método utilizado, é a construção do modelo 
matemático correspondente. De forma particular, o método Simplex exige que 
façamos algumas alterações nesse modelo matemático para que ele possa ser 
adequadamente resolvido. Essas adequações envolvem, basicamente, duas ações: 
igualar a função objetivo a zero e introduzir variáveis de folga nas inequações de 
restrição para transformá-las em equações.
Analisando o nosso problema, podemos construir o modelo matemático e ajustá-
lo aos padrões exigidos pelo método Simplex, conforme demonstração a seguir.
 
Modelo Matemático Original Modelo Matemático Ajustado
Maximizar: Z = 10.X1 + 8.X2 
Sujeito a
3.X1 + 3.X2 ≤ 300 (restrição de MP1) 
6.X1 + 3.X2 ≤ 480 (restrição de MP2)
X1 , X2 ≥ 0 (restrição de não negatividade)
Maximizar: Z - 10.X1 - 8.X2 = 0
Sujeito a
3.X1 + 3.X2 + X3 = 300 
6.X1 + 3.X2 + X4 = 480
X1 , X2 , X3 , X4 ≥ 0
Observe que no modelo matemático ajustado, a função objetivo aparece 
como uma equação igualada a zero, onde as variáveis independentes X1 e X2, 
com seus respectivos coeficientes, são colocadas à esquerda do sinal como 
parcelas negativas.
As novas variáveis X3 e X4, inseridas nas restrições do modelo matemático 
ajustado, têm como propósito transformar as inequações (desigualdades) em 
equações (igualdades), permitindo a substituição do operador “menor ou igual” (≤ ) 
pelo operador “igual” (=). Essas variáveis auxiliares são chamadas de “Folga”. 
10
11
Importante!
Para cada restrição técnica do problema é necessário introduzir uma variável de folga 
específica (a restriçãode não negatividade não é uma restrição técnica, portanto, ela 
não deve ser considerada). No exemplo apresentado, temos apenas duas restrições 
técnicas, sendo assim, introduzimos duas variáveis de folga, as quais identificamos como 
X3 e X4. Veja que para nomear essas variáveis, estamos adotando a letra “X” seguida de 
um identificador numérico sequencial. Como já temos as variáveis de decisão X1 e X2, os 
identificadores das variáveis de folga devem ser X3 e X4. 
Importante!
A variável de folga é o elemento de uma restrição que indica a quantidade não 
utilizada de um determinado recurso. Para ilustrar, vamos tomar como exemplo a 
segunda restrição do nosso modelo matemático ajustado: 6.X1 + 3.X2 + X4 = 480. 
As variáveis X1 e X2 (variáveis de decisão) correspondem às quantidades de produtos 
A e B a serem fabricadas, respectivamente, sendo que seus coeficientes (6 e 3) 
correspondem às quantidades de matéria-prima MP2 empregadas na fabricação de 
uma unidade de cada produto (6 unidades de MP2 para fabricar o produto A, e 3 
unidades para fabricar o produto B). O valor 480 corresponde à quantidade de MP2 
disponível no estoque da empresa (restrição de recurso). Para melhor compreensão, 
os componentes dessa equação de restrição são apresentados a seguir.
 
6.X1 + 3.X2 + X4 = 480 
 disponível 
 Quantidade de MP2 não utilizada (folga) 
 Quantidade fabricada do produto B 
 Quantidade de MP2 utilizada no produto B 
 Quantidade fabricada do produto A 
 Quantidade de MP2 utilizada no produto A
Passo 2 - Montagem da tabela de coeficientes
Este passo consiste em montar uma tabela de coeficientes, onde as linhas devem 
representar a função objetivo (Z) e as restrições técnicas do modelo (a restrição de 
não negatividade não é considerada). As colunas dessa tabela devem representar as 
variáveis de decisão (X1 e X2), as variáveis de folga (X3 e X4) e o termo independente 
(b), conforme mostra a Figura 2.
 
 X1 X2 X3 X4 b 
Z 
R1 
R2 
Variáveis de decisão, variáveis de folga e termo 
independente, compondo as colunas da tabela 
Função obje�vo e 
restrições técnicas, 
compondo as linhas 
da tabela 
Figura 2 - Linhas e colunas da tabela de coeficientes
11
UNIDADE Programação Linear: Métodos e Aplicações
Essa tabela deve ser preenchida com os coeficientes e os termos independentes 
das equações do modelo matemático, conforme demonstrado a seguir:
Modelo Matemático Tabela de Coe�cientes
Maximizar Z - 10.X1 - 8.X2 = 0
Sujeito a
 3.X1 + 3.X2 + 1.X3 = 300
 6.X1 + 3.X2 + 1.X4 = 480
 X1 , X2 , X4 = 480
X1
Z
R1
R2
X2 X3 X4 b
-10 -8 0 0 0
3 3 1 0 300
6 3 0 1 480
Passo 3 - Determinação da solução inicial
Para encontrarmos a solução inicial do problema, devemos atribuir o valor 
zero às variáveis de decisão, encontrando dessa forma o resultado da função 
objetivo e os valores positivos das variáveis de folga. Sendo assim, teremos os 
seguintes resultados:
Função Objetivo Restrição 1 (R1) Restrição 2 (R2)
Equação original Z - 10.X1 - 8.X2 = 0 3.X1 + 3.X2 + X3 = 300 6.X1 + 3.X2 + X4 = 480
Substituindo X1 e X2 por zero Z - 10.(0) - 8.(0) = 0 3.(0) + 3.(0) + X3 = 300 6.(0) + 3.(0) + X4 = 480
Resultado Z = 0 X3 = 300 X4 = 480
Observando os resultados encontrados, podemos dizer que, se a empresa não 
fabricar nenhum dos produtos (X1 = 0 e X2 = 0), o lucro obtido, obviamente, será 
zero (Z = 0). Nesse caso não haverá consumo de matéria-prima, sendo assim, os 
valores das folgas representarão toda a quantidade de matéria-prima disponível (X3 
= 300 e X4 = 480). 
Apesar de esse resultado ser uma solução viável do problema, fica claro que ele 
não é a solução ótima. Portanto, devemos encontrar outra solução.
Uma maneira simples para detectarmos se a solução ótima do problema foi 
encontrada, é verificarmos, na tabela de coeficientes, a existência de algum valor 
negativo na linha da função objetivo, ou seja, se algum coeficiente da função 
objetivo for negativo, a solução ótima ainda não foi encontrada. Observe na nossa 
tabela inicial (mostrada a seguir) que a função objetivo apresenta os coeficientes 
negativos -10 e -8, sendo assim, a solução inicial (X1 = 0 e X2 = 0) não é a solução 
ótima do problema. 
X1 X2 X3 X4 b
Z -10 -8 0 0 0
X1 3 3 1 0 300
X2 6 3 0 1 480
12
13
Passo 4 - Determinação da próxima solução viável
Para encontrarmos a próxima solução viável, devemos realizar uma sequência 
de operações sobre a tabela de coeficientes original, com o objetivo de gerar uma 
nova tabela otimizada. Essa sequência de operações tem o propósito de realizar a 
otimização matemática das equações do modelo por meio de iterações (repetições), 
até que a solução ótima seja encontrada. Como citado anteriormente, a solução 
ótima é determinada quando todos os coeficientes da função objetivo forem 
positivos ou zero. Dessa forma, o “Passo 4” deve ser repetido enquanto existir 
pelo menos um valor negativo na linha Z da tabela de coeficientes.
Neste passo, para cada iteração, devemos realizar as seguintes operações:
a. Identificar a “variável que entra”;
b. Identificar a linha pivô;
c. Calcular a nova linha pivô;
d. Calcular as novas linhas da tabela. Essas operações estão destacadas no 
fluxograma do algoritmo Simplex apresentado na Figura 3. 
 
INÍCIO
Passo 1
Elaboração do modelo matemático
Passo 2
Montagem da tabela de coe�cientes
Passo 3
Determinação da solução inicial
Passo 4
Determinação da próxima solução viável
a. Identi�cação da "variável que entra"
b. Identi�cação da linha pivô
c. Cálculo a nova linha pivô
d. Cálculo das novas linhas da tabela
Solução ótima?
FIM
Figura 3 - Fluxograma genérico do algoritmo Simplex
Vamos agora realizar a primeira iteração do algoritmo, executando as quatro 
operações citadas. 
13
UNIDADE Programação Linear: Métodos e Aplicações
Primeira Iteração
Identificação da “variável que entra”
Esta operação consiste em encontrar a variável de decisão que apresenta a 
maior contribuição para o aumento da função objetivo, ou seja, aquela que possui 
como coeficiente o maior valor absoluto (essa variável é tratada como “variável 
que entra”, pois, será ela que entrará na base para a composição da nova tabela). 
Analisando a nossa tabela original, facilmente podemos ver que o maior valor 
absoluto existente na linha da função objetivo é 10, que corresponde ao coeficiente 
da variável X1. Portanto, a variável que “entra” é a própria X1. Devemos então 
destacar a coluna que representa essa variável, conforme mostrado a seguir:
 X1 X2 X3 X4 b 
Z -10 -8 0 0 0 
R1 3 3 1 0 300 
R2 6 3 0 1 480 
Identificação da linha pivô
A linha pivô da tabela de coeficientes, também chamada de “linha que sai”, é 
uma das linhas que contêm os coeficientes das restrições do problema (a linha da 
função objetivo não é considerada). Para encontrá-la, devemos inicialmente dividir 
o termo independente b (última coluna da tabela) pelo respectivo coeficiente da 
variável que “entra” (coluna destacada, que neste caso é a coluna da variável X1). 
Dessa forma, encontraremos para a restrição R1 o valor 100 (300 ÷ 3) e para a 
restrição R2 o valor 80 (480 ÷ 6), conforme demonstrado a seguir:
Z
R2
R1
X1 X2 X3 X4
-10
3
6
b
-8 0 0 0
3
3
1
0
0
1
300
480
(300 ÷ 3 = 100)
(480 ÷ 6 = 80)
A linha pivô é aquela que apresenta o menor quociente positivo obtido por 
meio da divisão do termo independente pelo coeficiente da “variável que entra”. 
No nosso caso, o menor valor positivo encontrado é 80, portanto, a linha pivô da 
nossa tabela é aquela que representa a restrição R2. Devemos então destacá-la, 
conforme segue:
14
15
Z
R2
R1
X1 X2 X3 X4
-10
3
6
b
-8 0 0 0
3
3
1
0
0
1
300
480
O coeficiente que se encontra na intersecção da linha pivô e da coluna da “variável 
que entra” é chamado de “elemento pivô” (no nosso caso é o coeficiente 6). Esse 
elemento será utilizado no cálculo da nova linha pivô, conforme veremos a seguir.
Cálculo da nova linha pivô
O procedimento paracalcularmos a nova linha pivô é bastante simples, basta 
dividirmos todos os elementos da linha base atual pelo elemento pivô, encontrando 
assim os novos elementos (coeficientes) que farão parte da nova base. 
Z
R2
R1
X1 X2 X3 X4
-10
3
6
b
-8 0 0 0
3
3
1
0
0
1
300
480
Z
R2
R1
X1 X2 X3 X4
-10
3
1
b
-8 0 0 0
3
1/2
1
6
0
1/6
300
80
(÷6)
Cálculo das novas linhas da tabela
Após obter a nova linha pivô, conforme procedimento anterior (apresentado no 
item “c”), devemos recalcular os coeficientes para a obtenção das outras linhas da 
nova tabela. 
Vamos começar pela primeira linha, que corresponde à função objetivo. Pri-
meiramente, devemos identificar, nessa linha, o valor do coeficiente da “variá-
vel que entra”, que nosso caso é o valor da variável X1. Em seguida, devemos 
multiplicar todos os elementos da linha pivô atual pelo oposto desse valor (se 
negativo, vira positivo, e vice-versa), e somá-los aos respectivos coeficientes da 
função objetivo. Dessa forma, obteremos a nova linha da função Z. Para melhor 
compreensão desse procedimento, vamos realizá-lo passo a passo:
15
UNIDADE Programação Linear: Métodos e Aplicações
I. Identificar o valor do coeficiente da “variável que entra” na função objetivo.
Z
R2
R1
X1 X2 X3 X4
-10
3
1
b
-8 0 0 0
3
1/2
1
0
0
1/6
300
80
Coe�ciente da “variável
que entra” (-10)
II. Multiplicar todos os elementos da linha pivô atual pelo oposto do valor 
encontrado no procedimento anterior. 
Z
R2
R1
X1 X2 X3 X4
-10
3
1
b
-8 0 0 0
3
1/2
1
0
0
1/6
300
80
10 5 0 5/3 800
(x 10)
Linha pivô atual
Coe�cientes da linha pivô
multiplicados por 10 (oposto
do valor - 10 que é o coe�ciente 
de X1 na função objetivo)
III. Somar os resultados encontrados com os coeficientes da função objetivo. 
Z
R2
R1
X1 X2 X3 X4
-10
3
1
b
-8 0 0 0
3
1/2
1
0
0
1/6
300
80
+ + + + +
10 5 0 5/3 800
0 0 5/3-3 800
Linha atual da
função objetivo
Nova linha da
função objetivo
E assim teremos a nova linha da função objetivo. Nossa nova tabela de coeficien-
tes tem agora o seguinte aspecto:
16
17
Z
R2
R1
X1 X2 X3 X4
-10
3
1
b
-3 0 5/3 800
3
1/2
1
0
0
1/6
300
80
Vamos agora calcular os coeficientes da linha correspondente à restrição R1. 
Lembre-se de que já temos os novos coeficientes da função objetivo Z e da restrição 
R2 (linha pivô). Portanto, para finalizar a primeira iteração do algoritmo, falta 
calcularmos os novos coeficientes da restrição R1.
Para recalcularmos essa linha, devemos empregar os mesmos procedimentos 
realizados para o cálculo da linha da função objetivo, tomando por base, obviamente, 
a linha da restrição R1 ao invés da linha da função objetivo. Vamos realizar esses 
procedimentos passo a passo: 
I. Identificar o valor do coeficiente da “variável que entra” na equação da 
restrição R1.
Z
R2
R1
X1 X2 X3 X4
0
3
1
b
-3 0 5/3 800
3
1/2
1
0
0
1/6
300
80
Coen�ciente da
“variável que entra” (3)
II. Multiplicar todos os elementos da linha pivô atual pelo oposto do valor 
encontrado no procedimento anterior. 
Z
R2
R1
X1 X2 X3 X4
0
3
1
b
-3 0 5/3 800
3
1/2
1
0
0
1/6
300
80
Coen�ciente da
“variável que entra” (3)
-3 -3/2 0 -1/2 -240
(x -3)
Linha pivô atual
Elementos da linha pivô
multiplicados por -3 (oposto
do valor 3, que é o coe�ciente
de X1 na restrição R1)
17
UNIDADE Programação Linear: Métodos e Aplicações
III. Somar os resultados encontrados com os coeficientes da restrição R1. 
Z
R2
R1
X1 X2 X3 X4
0
3
1
b
-3 0 5/3 800
3
1/2
1
0
0
1/6
300
80
+ + + + +
-3 -3/2 0 -1/2 -240
0 3/2 1 -1/2 60
Linha atual da
restrição R1
Nova linha da
restrição R1
E assim teremos a nova linha da restrição R1, concluindo desta forma a primeira 
iteração do algoritmo Simplex. Nossa nova tabela de coeficientes tem agora o 
seguinte aspecto:
Z
R2
R1
X1 X2 X3 X4
0
0
1
b
-3 0 5/3 800
3/2
1/2
1
0
-1/2
1/6
60
80
Observe que ainda existe um coeficiente negativo na linha da função objetivo, 
que é justamente o coeficiente da variável de decisão X2 (-3), sendo assim, sabemos 
que a solução ótima ainda não foi encontrada. Portanto, devemos realizar uma 
nova iteração, repetindo as quatro operações descritas no “passo 4” para a nova 
tabela de coeficientes.
Segunda Iteração 
Identificação da “variável que entra”
Observando a nova tabela, podemos notar que a “variável que entra” agora é a 
X2, pois é ela, dentre as variáveis de decisão (X1 e X2), que apresenta o coeficiente 
de maior valor absoluto na linha da função objetivo.
Z
R2
R1
X1 X2 X3 X4
0
0
1
b
-3 0 5/3 800
3/2
1/2
1
0
-1/2
1/6
60
80
A variável que entra é a X2 (possui o 
coe�ciente de maior valor absoluto 
na linha da função Z)
18
19
Identificação da linha pivô
Já sabemos que a linha pivô, chamada também de base, é uma das linhas que 
representam as restrições do problema (R1 ou R2). Mais precisamente, é aquela 
onde o termo independente “b”, dividido pelo respectivo coeficiente da “variável 
que entra”, gerará o menor resultado. Na nossa nova tabela, podemos constatar 
que a linha pivô é a linha da restrição R1, pois, o quociente da divisão de “b” por 
X2 é 40 (60÷3/2=40), e esse valor é menor que o valor calculado para a linha da 
restrição R2 (80÷1/2=160), conforme podemos observar a seguir.
 X1 X2 X3 X4 b 
Z 0 -3 0 5/3 800 
R1 0 3/2 1 -1/2 60 
R2 1 1/2 0 1/6 80 
(60 ÷ 3/2 = 40) 
(80 ÷ 1/2 = 160) 
Linha pivô Elemento pivô 
Lembre-se de que o coeficiente que se encontra na intersecção da linha pivô e 
da coluna da “variável que entra” é chamado de “elemento pivô” (no nosso caso é 
o coeficiente 3/2). 
Cálculo da nova linha pivô
Para calcularmos a nova linha pivô, basta dividirmos todos os elementos da linha 
base atual pelo elemento pivô, conforme demonstrado a seguir: 
 
 X1 X2 X3 X4 b 
Z 0 -3 0 5/3 800 
R1 0 1 2/3 -1/3 40 
R2 1 1/2 0 1/6 80 
(÷ 3/2) 
 X1 X2 X3 X4 b 
Z 0 -3 0 5/3 800 
R1 0 3/2 1 -1/2 60 
R2 1 1/2 0 1/6 80 
Nova linha pivô 
19
UNIDADE Programação Linear: Métodos e Aplicações
Cálculo das novas linhas da tabela
Devemos agora recalcular as outras linhas da nova tabela. Vamos recordar os 
procedimentos que devem ser realizados para cada uma dessas linhas:
I. Identificar, na linha em questão, o coeficiente da “variável que entra”;
II. Multiplicar todos os elementos da linha pivô pelo oposto do coeficiente 
identificado;
III. Somar os resultados encontrados aos respectivos coeficientes da linha 
em questão.
Aplicando esses três procedimentos na linha da função objetivo, teremos os 
novos elementos dessa linha, conforme demonstração a seguir: 
 X1 X2 X3 X4 b 
Z 0 -3 0 5/3 800 
R1 0 1 2/3 -1/3 40 
R2 1 1/2 0 1/6 80 
 
(x 3) 0 3 2 -1 120 
 
(+) 0 -3 0 5/3 800 
 
(=) 0 0 2 2/3 920 
 
Linha pivô atual 
Elementos da linha pivô 
mul�plicados por 3 (oposto do 
valor -3, que é o coeficiente de 
X2 na função obje�vo) 
Elementos atuais da linha da 
função obje�vo 
Novos elementos da linha da 
função obje�vo 
A nova tabela terá o seguinte aspecto:
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 1/2 0 1/6 80 
Nova linha da função obje�vo 
Resta agora recalcular a nova linha da restrição R2. Devemos aplicar o mesmo 
procedimento, conforme demonstração a seguir:
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 1/2 0 1/6 80 
 
(x -1/2) 0 -1/2 -1/3 1/6 -20 
 
(+) 1 1/2 0 1/6 80 
 
(=) 1 0 -1/3 1/3 60 
 
Linha pivô atual 
Elementos da linha pivô 
mul�plicados por -1/2 (oposto do 
valor 1/2, que é o coeficiente de 
X2 na restrição R2 
Elementos atuais da linha da 
restrição R2 
Novos elementos da linha da 
restrição R2 
20
21
A nova tabela terá o seguinte aspecto:
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 0 -1/3 1/3 60 Nova linha da restrição R2 
Observe que agora não existe nenhum valor negativo na linha da função objetivo 
Z. Isso sinaliza que a solução ótima do problema foi encontrada. 
Para obtermosos valores das variáveis de decisão X1 e X2, que correspondem às 
quantidades dos produtos A e B a serem fabricados, respectivamente, para que a 
empresa obtenha o lucro máximo, devemos analisar as linhas de restrições R1 e R2 
da tabela de coeficientes. Essa análise consiste em encontrar, para cada variável de 
decisão, a linha onde o seu coeficiente é igual a 1 (um), sendo que o valor do termo 
independente “b” dessa linha é o próprio valor da variável de decisão em questão. 
Vejamos a seguir os procedimentos para obtenção desses valores. 
Procedimento para encontrarmos o valor da variável de decisão X1: 
Na coluna da variável X1, devemos localizar o coeficiente cujo valor é 1 (um). 
Na linha desse coeficiente, devemos obter o valor do termo independente “b”, que 
é o próprio valor da variável de decisão. Portanto, o valor de X1 é 60, conforme 
podemos observar por meio da demonstração a seguir:
 
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 0 -1/3 1/3 60 
Coluna da variável X1 
Linha onde o 
coeficiente de X1 é 
igual a 1 
Valor da variável X1 
Procedimento para encontrarmos o valor da variável de decisão X2:
Da mesma forma, na coluna da variável X2, devemos localizar o coeficiente 
cujo valor é 1 (um). Na linha desse coeficiente, devemos obter o valor do termo 
independente “b”, que é o próprio valor da variável de decisão. Portanto, o valor 
de X2 é 40, conforme demonstração a seguir:
21
UNIDADE Programação Linear: Métodos e Aplicações
 
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 0 -1/3 1/3 60 
Coluna da variável X2 
Linha onde o 
coeficiente de X2 é 
igual a 1 
Valor da variável X2 
Para concluirmos a análise, vamos relembrar o enunciado do problema e o seu 
modelo matemático:
ENUNCIADO
Uma empresa fabrica dois produtos: A e B, sendo que o lucro por unidade do 
produto A é R$ 10,00 e do produto B é R$ 8,00. Na manufatura desses produtos 
são empregadas apenas duas matérias-primas: MP1 e MP2, na seguinte proporção: 
3 unidades de MP1 e 3 unidades de MP2 para cada unidade do produto A e 6 
unidades de MP1 e 3 unidades de MP2 para cada unidade do produto B. A empresa 
possui um estoque de 300 unidades de MP1 e 480 unidades de MP2. Considerando 
que as variáveis de decisão são X1 (quantidade de A a ser produzida) e X2 (quantidade 
de B a ser produzida), quais devem ser as quantidades de A e B a serem produzidas 
para que a empresa obtenha o lucro máximo?
MODELO MATEMÁTICO
Maximizar Z = 10.X1 + 8.X2 
Sujeito a
3.X1 + 3.X2 ≤ 300 (restrição de MP1) 
6.X1 + 3.X2 ≤ 480 (restrição de MP2)
X1 , X2 ≥ 0 (restrição de não negatividade)
Sabendo-se que a solução ótima é dada por X1=60 e X2=40 (conforme aplicação 
do método Simplex), podemos dizer que o lucro máximo será obtido se a empresa 
fabricar 60 unidades do produto A e 40 unidades do produto B. O valor do lucro 
pode ser encontrado substituindo-se as variáveis X1 e X2 da função objetivo Z por 
seus respectivos valores:
Z = 10.X1 + 8.X2
Z = 10.(60) + 8.(40)
Z = 920
22
23
Observe que esse valor pode ser obtido através da própria tabela de coeficientes:
 X1 X2 X3 X4 b 
Z 0 0 2 2/3 920 
R1 0 1 2/3 -1/3 40 
R2 1 0 -1/3 1/3 60 
Lucro 
Quan�dade do produto B a ser 
fabricada (X2) 
Quan�dade do produto A a ser 
fabricada (X1) 
E assim, a solução do problema pode ser escrita da seguinte forma:
Para que a empresa obtenha o lucro máximo de R$ 920,00, ela deverá produzir 60 
unidades do produto A e 40 unidades do produto B. 
Ferramentas Computacionais 
É fácil perceber que a aplicação do algoritmo Simplex para a resolução de 
problemas de programação linear não é uma tarefa rápida. Apesar da simplicidade 
do algoritmo, a sua aplicação envolve procedimentos repetitivos (iterações) que 
demandam muito tempo de trabalho na reconstrução das várias versões da 
tabela de coeficientes, o que propicia a introdução de eventuais valores errados, 
comprometendo todo o trabalho. 
O algoritmo Simplex não foi concebido para ser uma receita a ser seguida 
manualmente, mas sim para ser implementado por meio de programas de 
computadores. Nesse sentido, foram desenvolvidas diversas ferramentas 
computacionais voltadas à resolução de problemas de programação linear baseadas 
nesse algoritmo, das quais destacamos o software LINDO, desenvolvido pela 
LINDOTM Systems (http://www.lindo.com). 
Além das ferramentas específicas, o algoritmo Simplex pode ser implementado 
por meio de aplicativos matemáticos, como por exemplo, o Excel (desenvolvido pela 
Microsoft Corporation), o MatLab (desenvolvido pela MathWorks Inc.), dentre outros.
Existem ainda diversas ferramentas online, disponibilizadas gratuitamente pela 
internet, que oferecem recursos para a resolução de problemas de programação 
linear por meio do método Simplex. Como exemplo desse tipo de ferramenta, 
destacamos o “SIMPLEX in PHP”, cujo código é disponibilizado nos termos 
da GNU (General Public License) pela Free Software Foundation Inc. Uma 
versão dessa ferramenta, adaptada às nossas necessidades, pode ser encontrada 
no endereço http://vichinsky.com.br/simplex. Para ilustrar o seu uso, segue um 
pequeno roteiro para a resolução do problema apresentado nesta unidade. 
23
UNIDADE Programação Linear: Métodos e Aplicações
Roteiro para Utilização do Software 
“SIMPLEX in PHP”
Acesse o endereço http://vichinsky.com.br/simplex e siga os passos descritos 
a seguir. 
1. Na tela inicial, informe o tipo de problema (maximização ou minimização), 
a quantidade de variáveis de decisão e o número de restrições técnicas. O 
nosso problema é de maximização, com duas variáveis de decisão (X1 e X2) e 
duas restrições técnicas (R1 e R2). Após o preenchimento dos campos, clique 
em “PROSSEGUIR”.
 
2. Na próxima tela, introduza o modelo matemático conforme indicações a 
seguir. Ao final, clique em “PROSSEGUIR”.
Modelo Matemático
Max Z = 10.X1 + 8.X2
Sujeito a
3.X1 + 3.X2 ≥ 300
6.X1 + 3.X2 ≥ 480
X1 , X2 ≥ 0 
 Coeficiente de X1 na 
função obje�vo: 10 
 Coeficiente de X2 na 
função obje�vo: 8 
 
Termos independentes 
das restrições: 300 e 480 
 
Coeficientes de X2 
nas restrições: 3 e 3 
Coeficientes de X1 
nas restrições: 3 e 6 
≥
24
25
3. A resolução do problema é apresentada em uma única tela que contém os 
seguintes elementos:
a. Modelo matemático original e modelo ajustado
b. Solução inicial e iterações
25
UNIDADE Programação Linear: Métodos e Aplicações
c. Solução ótima e análise gráfica
Observe que a solução encontrada pelo software é a mesma que encontramos 
com os procedimentos realizados manualmente.
26
27
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Pesquisa Operacional na Tomada de Decisões
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 4. ed. Sao Paulo: 
Pearson Prentice Hall, 2012. Capítulo 2.
Introdução à Pesquisa Operacional
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. Porto Alegre: 
Mc Graw-Whill, 2013. Capítulo 4.
 Leitura
Utilização da Programação Linear e do Método SIMPLEX para Otimização da Produção de Pães em uma Empresa 
de Panificação
Utilização da Programação Linear e do Método SIMPLEX para Otimização da Produção de 
Pães em uma Empresa de Panificação, disponível em:
https://goo.gl/nKUQy2
O Uso da Ferramenta SOLVER do EXCEL na Resolução de Problemas de Programação Linear
O Uso da Ferramenta SOLVER do EXCEL na Resolução de Problemas de Programação Linear, 
disponível em:
https://goo.gl/iXk9rb
27
UNIDADE Programação Linear: Métodos e Aplicações
Referências
ANDRADE, E. L. Introdução à Pesquisa Operacional: Métodos e Modelos Para 
a Análise de Decisão. 4. ed. Rio de Janeiro: Ltc-Livros Técnicos e Científicos, 2011.
HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. 9. ed. 
Porto Alegre: Mc Graw-Whill, 2013.
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. 4. ed. 
São Paulo: Pearson Prentice Hall, 2012.
28