Resolução de Problemas de Programação Linear com Algoritmo Simplex

Prévia do material em texto

XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
1
 
RESOLUÇÃO DE PROBLEMAS DE PESQUISA OPERACIONAL ANTES DO 
SURGIMENTO DOS SOFTWARES: UMA ABORDAGEM SOBRE O ALGORITMO SIMPLEX 
 
Elvis Magno da Silva, autor 
Vladas Urbanavicius Júnior, autor 
 
1FACESM/Gpde, Av. Presidente Tancredo de Almeida Neves, 45 - Itajubá – MG 
2FAPEMIG/IC, Rua Raul Pompéia 101, São Pedro, Belo Horizonte – MG 
3UNINOVE/PMDA, Rua Guaranésia, 425, Vila Maria, São Paulo-SP 
 
Resumo 
Sendo muito requisitada nos últimos anos, a Pesquisa Operacional é um método científico de tomada de 
decisão, e tem como uma de suas principais ferramentas o estudo da Programação Linear. A Programação 
Linear é uma formulação matemática que determina um montante fixo de recursos que satisfaça certa 
demanda de tal modo que uma função-objetivo seja otimizada e ainda satisfaça a outras condições pré-
definidas pelo problema. A Programação Linear pode ser resolvida por alguns métodos diferentes que são o 
método gráfico, o método algébrico e por softwares como o solver do Microsoft Office ou QM for Windows 
ou ainda o Lindo, entre outros. O objetivo deste trabalho é apresentar o método algébrico Simplex de 
cálculo de problemas de programação linear. Este é um trabalho quantitativo e de pesquisa bibliográfica. 
Também será proposto um caso hipotético para auxiliar na compreensão da aplicação do Algoritmo 
Simplex. Durante o trabalho será visto conceitos sobre Pesquisa Operacional, Programação Linear e sobre 
o Simplex. Também poderá ser observado como resolver um problema de maximização utilizando o 
Simplex. Para isso será demonstrado à formulação matemático do problema e todos os passos para a 
aplicação do Simplex até se chegar à solução ótima, e por fim, serão mostradas quais as conclusões que se 
pode obter da tabela do resultado ótimo. 
 
Palavras-chave: Simplex, Pesquisa Operacional, Programação Linear. 
 
1. Introdução 
 
Girão e Ellenrieder (1971, p.xi) comentam 
que nos últimos anos, um novo ramo do 
conhecimento altamente geral vem sendo 
desenvolvido, sob o nome de Pesquisa 
Operacional. O objetivo deste novo ramo do 
conhecimento é resolver problemas de decisão 
nas áreas de economia, administração, finanças e 
organização em geral; e isso com uma 
abordagem científica de tais problemas. Dentro 
da Pesquisa Operacional, pode ser encontrada 
uma ferramenta chamada de Programação 
Linear. 
Dantzing (1991, p.1) coloca que a 
Programação Linear pode ser encarada como 
parte de um grande desenvolvimento 
revolucionário que deu a humanidade a 
capacidade geral de estabelecer metas e um 
caminho detalhado para se tomar decisões no 
sentido de "melhor" atingir os seus objetivos 
quando confrontados com situações concretas de 
grande complexidade. Uma forma de calcular 
problemas de Programação Linear de forma 
algébrica é através do Algoritmo Simplex, o qual 
será visto neste trabalho. 
Ainda sobre o Simplex, Mirshawka (1978, 
p.28-29) explica que este algoritmo utiliza 
conceitos básicos de álgebra matricial para achar 
a intersecção de duas ou mais retas ou planos. 
Afirma que parte de um pressuposto de uma 
solução ótima viável, e sucessivamente obtém 
soluções em intersecções que fornecem valores 
cada vez melhores para a função objetivo. E que, 
além disso, fornece um indicador que determina 
quando a solução ótima é atingida. 
Para confecção deste trabalho será 
utilizada o método de pesquisa bibliográfica, onde 
Medeiros (2007, p.49), diz que pesquisa 
bibliográfica se constitui num procedimento formal 
para a aquisição de conhecimento sobre a 
realidade. E que ainda, exige pensamento 
reflexivo e tratamento científico. Este se 
aprofunda na procura de resposta para todos os 
porquês envolvidos pela pesquisa. Também será 
utilizado um caso hipotético onde será 
demonstrada a resolução do método Simplex. 
 
2. Pesquisa Operacional 
 Para Shamblin e Stevens Jr (1979, p. 13), 
Pesquisa Operacional (PO) é “um método 
científico de tomada de decisão”. Ela iniciar-se 
descrevendo um sistema por intermédio de um 
modelo e depois lida com este modelo para 
levantar o melhor modo de operar o sistema. 
 Duckworth (1972, p. 16-17) diz também 
que a parte mais importante do conceito de 
Pesquisa Operacional é “soluções ótimas para os 
problemas... que dizem respeito ao 
funcionamento de um sistema”. 
Lachtermacher (2004), salienta que até a 
década de 1990, os problemas matemáticos de 
programação na resolução de questões 
gerenciais eram muito difíceis de se implementar. 
 
XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
2
Que somente com o advento das planilhas 
eletrônicas e sua crescente utilização, 
proporcionaram um aumento significativo na 
aplicabilidade da Pesquisa Operacional. 
Ainda segundo Lachtermacer (2004, p.1), 
a PO pode ser utilizada para ajudar nos 
processos de decisão. Como por exemplo: 
• Problemas de Otimização de Recursos; 
• Problemas de Localização; 
• Problemas de Roteirização; 
• Problemas de Carteiras de Investimento; 
• Problemas de Alocação de Pessoas; e 
• Problemas de Previsão e Planejamento. 
 Segundo Lachtermacer (2004, p.27) fala-
se que um problema de programação linear está 
em sua forma padrão se “tivermos uma 
Maximização da função-objetivo e se todas as 
restrições forem do tipo menor ou igual, bem 
como os termos constantes e variáveis de 
decisão não-negativos”. De forma matemática 
pode-se representar um problema padrão por: 
 Maximizar: Z = c1x1 + c2x2 + ... + cnxn 
 
Sujeito a: 
 a11x1 + a12x2 + ... + a1nxn ≤ b1 
 a21x1 + a22x2 + ... + a2nxn ≤ b2 
 . . . 
 . . . 
 am1x1 + am2x2 + … + amnxn ≤ bm 
 x1, x2, …, xn ≥ 0 
 
Shamblin e Stevens Jr (1979, p. 263) 
afirmam que “é possível expressar 
matematicamente tanto o objetivo como as 
restrições. Como o próprio nome da técnica 
sugere, estas relações devem ser todas lineares”. 
Para eles, a programação linear, é de forma 
resumida, a aplicação da álgebra matricial para 
resolver estas equações usando algumas regras 
especiais que garantem que a solução seja 
satisfatória à todas as condições necessárias e 
ainda, trazer os melhores resultados com relação 
ao objetivo. 
 Garvin (1960, p.3) comenta que o 
problema central de programação linear é para 
minimizar ou maximizar uma função linear, e que 
proponha condições de que as variáveis sejam 
não negativas e devam satisfazer a formulação 
da equação linear. 
 Para melhor se entender a formação 
algébrica da formulação do problema. Observe 
um exemplo hipotético de Montevechi (2006, 
p.20): 
 Uma fábrica produz dois tipos de 
brinquedos de madeira: soldados e trens. Um 
soldado é vendido por $27 e usa $10 de matéria 
prima. Cada soldado que é fabricado tem um 
custo adicional de $14 relativo à mão de obra. Um 
trem é vendido por $21 e gasta $9 de matéria 
prima. O custo de mão de obra adicional para 
cada trem é de $10. A fabricação destes 
brinquedos requer dois tipos de mão de obra: 
carpintaria e acabamento. Um soldado necessita 
de 2 horas para acabamento e 1 hora de 
carpintaria. Um trem necessita de 1hora para 
acabamento e 1 hora de carpintaria. Cada 
semana, a fábrica pode obter qualquer 
quantidade de matéria prima, mas tem a 
disposição até 100 horas de acabamento e 80 de 
carpintaria. A demanda por trens é ilimitada, mas 
a venda de soldados é de no máximo 40 por 
semana. A fábrica quer maximizar seu lucro diário 
(receitas-custo). Com estes dados, será 
formulado o modelo matemático que poderá 
auxiliar na maximização do lucro semanal. 
 Montevechi (2006, p. 20- 25), nos ajuda a 
esclarecer este exemplo. Primeiramentedevemos 
levantar a questão problemas, que é “quantos 
soldados e trens devem ser feitos na semana?”. 
Para esclarecer ainda mais, devem-se 
representar as variáveis de decisão. Neste caso, 
o número de soldados produzidos e o número de 
trens produzidos. Veja: 
• X1 = número de soldados produzidos a cada semana 
• X2 = número de trens produzidos a cada semana 
 
 Para obtenção da função objetivo, 
consideremos três pontos: a receita e custos 
podem ser expressos em termos das variáveis X1 
e X2, será assumido que todo brinquedos 
produzidos possam ser vendidos, e que a receita 
da semana é igual a receita dos soldados mais a 
receita dos trens, disto posto: 
 Receita por semana = 27*X1 + 21*X2, e 
 Custos de M.P. = 10*X1 + 9*X2 
 Custos de M.O. = 14*X1 + 10*X2 
 Desta forma afirma-se que a fábrica quer 
maximizar: 
 (27*X1 + 21*X2) – (10*X1 + 9*X2) – 
(14*X1 + 10*X2) 
 
Simplificando esta equação, obtemos que 
a maximização da questão é: 
 Max Z = 3X1 + 2X2 
 X1 e X2 são limitadas por algumas 
restrições. Vejam quais são: 
1) Cada semana, não há mais que 100 
horas de acabamento; 
2) Cada semana, não há mais que 80 
horas de carpintaria; 
3) Limitação da demanda, não mais de 40 
soldados por semana 
 
 O passo a seguir, é a transformação 
destas restrições em expressões matemáticas em 
termo das variáveis de decisão X1 e X2. 
 Restrição 1: 2X1 + X2 ≤ 100 
 Restrição 2: X1 + X2 ≤ 80 
 Restrição 3: X1 ≤ 40 
 
 Porém, Montevechi (2006, p. 25) nos 
lembra que deve-se tomar outras duas restrições 
matemáticas para a formulação deste problema, 
que são: 
 
XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
3
 Restrição adicional 1: X1 ≥ 0 
 Restrição adicional 2: X2 ≥ 0 
 De forma resumida, se tem, 
matematicamente: 
 Max Z = 3X1 + 2X2 
 Sujeito a: 
 2X1 + X2 ≤ 100 
 X1 + X2 ≤ 80 
 X1 ≤ 40 
X1 ≥ 0 
 X2 ≥ 0 
 O problema deste exemplo hipotético é 
típico de muitas empresas, que precisam 
maximizar os lucros e ao mesmo tempo estão 
sujeitos a recursos limitados. 
 
3. O Método Simplex e o Caso Hipotético 
 Hillier e Lieberman (2005, p.103) afirmam 
que o método simplex é um procedimento 
algébrico. Contudo, ele também traz consigo um 
conceito geométrico. Comentam que se 
entendermos estes conceitos geométricos os 
quais pertencem a resolução gráfica que vimos 
no capítulo anterior, podemos então prosseguir 
com os estudos do simplex. 
Segundo Girão e Ellenrieder (1971, p.38) 
o algoritmo conhecido por ‘simplex original’ é o 
algoritmo que pode parar quando é encontrada a 
solução ótima, ou quando não existe solução 
ótima. Para Silva et al (1998, p.46) o método 
simplex é formado por um grupo de critérios para 
escolha de soluções básicas que melhorem o 
desempenho do modelo. 
 Montevechi (2006, p.40), afirma que 
problemas com mais de duas variáveis não 
poderiam ser solucionados com o método gráfico, 
e que desta forma torna-se necessário outro 
caminho para a busca de soluções. 
 Corrar e Theóphilo (2007, p.344) dizem 
que para iniciar a aplicação do método simplex, 
retoma-se as equações das restrições definidas 
anteriormente, incluídas as variáveis de folga. 
 Assim, dos dados do problema: 
 Max Z = 3X1 + 2X2 
 Sujeito a: 
 2X1 + X2 ≤ 100 
 X1 + X2 ≤ 80 
 X1 ≤ 40 
X1 ≥ 0 
 X2 ≥ 0 
 
Montevechi (2006, p.42) coloca que 
existem três condições para o uso do método 
simples, que são: 
1) Todas as restrições são do tipo “≤ bi”; 
2) Todos os “bi ≥ 0”; 
3) Se quiser maximizar “Z”. 
Martín (2003, p.28-29) ainda explica que 
para a aplicação do simplex, é necessário 
acrescentar uma variável artificial em cada uma 
das restrições, e por fim, a própria função 
objetivo. Chamaremos esta variável artificial de 
variável de folga, devido à literatura nacional usar 
esta nomenclatura. 
 
Max Z = 3X1 + 2X2 � 
Max Z = 3X1 + 2X2 + 0.X3 + 0.X4 + 0.X5 
Sujeito a: 
2X1 + X2 + X3 ≤ 100 
X1 + X2 + X4 ≤ 80 
X1 + X5 ≤ 40 
 
Martín (2003, p.32) diz que após se 
acrescentar as novas variáveis, deve-se montar a 
tabela de algoritmo do simplex com os 
coeficientes da função objetivo e das restrições. 
Na função “Z” da equação de maximização, 
deixa-se um lado da igualdade igual a zero, de 
forma a deixar os coeficientes todos inversamente 
proporcionais. 
Por exemplo, na função Z= 3X1 + 2X2, 
têm-se: Z – 3X1 – 2X2 = 0., e que os coeficientes 
das variáveis de folga são zero. 
 
 
Tabela 1: Tabela de montagem do algoritmo simplex 
 
Para Montevechi (2006, p.43) após 
montado a tabela com os coeficientes das 
variáveis, tem-se que determinar uma solução 
inicial viável para poder prosseguir. Assim, pode 
ser demonstrado que a solução ótima de um 
problema de programação linear é uma solução 
básica. Uma solução básica para um sistema de 
M equações e N incógnitas, possui M variáveis 
diferentes de zero e N várias iguais a zero. As 
variáveis que são diferentes de zero, chama-se 
de variáveis básicas, e aquelas iguais a zero são 
as não básicas. Para o método do simplex, deve 
ser escolhido para ocuparem o lugar de variáveis 
básicas, aquelas cujas colunas apareçam um 
valor igual a 1, e os demais valores iguais a zero. 
 Assim volta-se a figura anterior e 
identifica-se na tabela, quais colunas tem um 
único valor 1, (um) e os demais valores 0 (zero). 
 
 
Tabela 2: Tabela de entrada da solução básica 
 
 Disto posto, irá ser procurado na linha de 
Z o menor número negativo. Neste caso é X1, 
pois seu coeficiente é “-3”. Assim, dividem-se os 
valores da coluna “b” pelos coeficientes 
respectivos na coluna X1 (coluna do menor valor 
negativo na linha Z). Chama-se este passo de 
verificação da solução. 
 
XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
4
 
Tabela 3: tabela de verificação da solução através da razão 
entre coluna “b” e coluna do menor negativo de “Z”. 
 
 Cabe lembrar que para Martín (2003, 
p.36) pode-se chegar a uma solução finita ou a 
uma solução não finita. 
Se a solução for finita, há duas 
possibilidades nesta verificação: 
1) Que o problema admita uma solução ótima, 
com todas as variáveis de folga iguais a 
zero, então a solução obtida é uma solução 
única e ótima. 
2) Que o problema admita uma solução ótima 
na qual encontremos uma variável de folga 
diferente de zero, então o problema original 
é impossível e não há solução. 
 
Caso a solução seja não finita, também 
há outras duas possibilidades: 
 
1) Com todas as variáveis de folga iguais a 
zero, neste caso temos uma solução não 
finita. 
2) Que exista ao menos uma variável de 
folga que seja positiva, então o problema 
original é impossível. 
 
Ainda neste raciocínio, Montevechi (2006, 
p.43), coloca que se devem examinar os valores 
dos coeficientes das variáveis não básicas na 
primeira linha (linha de Z) e concluir: 
1) Se todos os valores forem positivos a 
solução é ótima e única; 
2) Se aparecerem valores positivos e alguns 
nulos a solução é ótima mas não única; e 
3) Se aparecer algum valor negativo a 
solução não é ótima. Deve-se então 
continuar o método do simplex. 
 
 Após fazer a verificação que pode ser 
vista na tabela 3, têm-se que na linha de Z, ainda 
há ao menos um valor negativo, o que indica que 
ainda não se chegou a uma solução ótima. Então, 
é-se necessário prosseguir com o método do 
simplex, de forma a substituir uma coluna por 
uma linha da base. A linha que sai é a linha da 
menor razão não negativa, que no caso é a linha 
de X5, pois apresentou a razão 40, que é a 
menor, como pode ser visto na tabela 4. 
 
 
Tabela 4: Identificação da Linha que sai. 
 
Assim, aparece como resultados parciais:X1 = 0 X3 = 100 
 X5 = 40 
 X2 = 0 X4 = 80 
A intercessão advinda da união da coluna 
do menor Z negativo com a linha que sai que é a 
da menor razão, tem o que se chama de Pivô. 
 
Tabela 5: Identificação do Pivô. 
 
 Este pivô indica que X1 entra no lugar de 
X5. Desta forma na base da próxima tabela se 
terá: X3, X4 e X1. 
 Montevechi (2006, p.44) explica que deve 
ser dividido a linha pivô pelo próprio pivô para se 
ter uma nova linha pivô que será colocada na 
tabela seguinte do algoritmo do simplex. Ou seja, 
para o Pivô = 1: 
 0 ÷ 1 = 0 
 1 ÷ 1 = 1 
 0 ÷ 1 = 0 
0 ÷ 1 = 0 
0 ÷ 1 = 0 
 1 ÷ 1 = 1 
40 ÷ 1 = 40 
 
Assim a nova linha pivô é dada pela 
tabela 6: 
 
Tabela 6: Nova Linha Pivô 
 
 Então será iniciada a nova tabela do 
simplex que começa com a nova linha pivô, como 
mostra a tabela 7. 
 
 
Tabela 7: Nova Linha Pivô Na Tabela do Simplex 
 
 Prosseguindo com a montagem da 
tabela, agora é necessário realizar um cálculo em 
cada uma das demais linhas para a entrada na 
nova tabela do simplex. Deve-se utilizar a 
fórmula: 
 
Nova Linha 0 = Linha 0 – (Fo × Nova Linha Pivô); 
 
Onde Fo é o coeficiente menor negativo 
em Z (neste caso “-3”). Então: 
(1 -3 -2 0 0 0 0) - [(-3) × (0 1 0 0 0 1 40)] 
 
Resolvendo, tem-se que a Nova Linha 0 
será: 
_ 1 -3 -2 0 0 0 0 
 0 -3 0 0 0 -3 -120 
1 0 -2 0 0 3 120 
 
 
XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
5
 Disto posto, a segunda linha que entrará 
na tabela do simplex, é a linha nova de Z. 
 
 
Tabela 8: Nova Linha de Z Na Tabela do Simplex 
 
 Este passo será repetido para as duas 
próximas linhas. Assim, têm-se: 
Nova Linha 1 = Linha 1 – (F1 × Nova 
Linha Pivô); onde o F1 é o coeficiente seguinte 
da coluna de -3, que é o “2”. 
 
(0 2 12 1 1 0 0 100) - [(2) × (0 1 0 0 0 1 40)] 
 
_ 0 2 1 1 0 0 100 
 0 2 0 0 0 2 80 
0 0 1 1 0 -2 20 
 
 
Tabela 9: Nova Linha ‘1’ Na Tabela do Simplex 
 
Nova Linha 2 = Linha 2 – (F2 × Nova 
Linha Pivô); onde o F2 é o coeficiente seguinte 
da coluna de -3, que é o “1”. 
 
(0 1 1 0 1 0 80) - [(1) × (0 1 0 0 0 1 40)] 
 
_ 0 1 1 0 1 0 80 
 0 1 0 0 0 1 40 
 0 0 1 0 1 -1 40 
 
 
Tabela 10: Nova Tabela do Simplex 
 
 Da identificação do Pivô, tem-se que X1 
entra no lugar de X5. 
 
Tabela 11: Identificação da Saída de X5 e Entrada de X1 
 
 Assim, na coluna da base, se terá X3, X4 
e X1. 
 
Tabela 12: Composição da Base da Nova Tabela do Simplex 
 
 Cabe lembrar que Martín (2003, p.36-37) 
comenta que uma vez que existe coeficiente 
negativo na primeira linha (-2), a solução ainda 
não é ótima. Assim, deve-se calcular novamente 
a variável que entra e a variável que sai. E esse 
processo como descrito anteriormente, começa 
com a identificação do menor negativo na linha de 
Z. 
 
Tabela 13: Identificação da Coluna do Menor Negativo na 
Nova Tabela do Simplex. 
 
Assim, é identificado a variável que 
entrará na base. Após este passo, como já 
mostrado, faz-se a razão da coluna X2 com a 
coluna “b”. 
 
Tabela 14: Razão na Nova Tabela do Simplex. 
 
Depois de concluída a razão, identifica-se 
o menor valor não negativo, achando por 
conseqüência a variável que sai da base, bem 
como o novo Pivô. 
 
 
Tabela 15: Nova Linha que Sai, que Entra e Pivô. 
 
Desta forma, pode ser observada a 
solução parcial do problema, bem como as novas 
variáveis que estarão na base para a próxima 
tabela do simplex que será montada (X2, X4, e 
X1). 
 X1 = 40 X4 = 40 
 X2 = 0 X5 = 0 
X3 = 20 
 
Após verificar a solução parcial, tem-se 
que calcular a nova linha Pivô que é a linha Pivô 
dividida pelo próprio Pivô. Assim dividindo a linha 
de X3 por 1, se tem: 
 
Tabela 16: Nova Linha Pivô (Linha de X3 ÷ 1 – Pivô). 
 
Com a nova linha Pivô, prossegue com o 
cálculo das novas da tabela através do 
procedimento: Nova Linha 0 = Linha 0 – (Fo × 
Nova Linha Pivô), conforme demonstrado 
anteriormente. Após refeito os cálculos, obteve-se 
a nova tabela: 
 
 
XIII Encontro Latino Americano de Iniciação Científica e 
IX Encontro Latino Americano de Pós-Graduação – Universidade do Vale do Paraíba 
6
 
Tabela 17: Nova Tabela do Simplex 3. 
 
Desta nova tabela do Simplex montada, 
ainda pode ser percebido que não se chegou a 
uma solução ótima, visto ainda haver um 
coeficiente negativo na linha de “Z”. Desta forma 
deve ser repetido todos os novamente: calcular a 
variável que entra, que saí, menor negativo, 
razão, pivô, novas linha e nova tabela, até chegar 
a uma tabela que não possua coeficientes 
negativos na primeira linha. 
Repetindo-se todos os passos 
novamente, pode-se chegar a quarta tabela do 
algoritmo Simplex. 
 
 
Tabela 18: Cálculo do Pivô para 4ª Tabela do 
Simplex. 
 
 
Tabela 19: Nova Tabela do Simplex. 
 
Desta ultima tabela do Simplex pode ser 
observado que não há coeficiente negativo na 
primeira linha, ou linha de “Z”. Assim, tem-se a 
solução ótima tanto almejada. 
 
4. Conclusão 
Foi visto neste trabalho que a Pesquisa 
Operacional é “um método científico de tomada 
de decisão”. Ela iniciar-se descrevendo um 
sistema por intermédio de um modelo e depois 
lida com este modelo para levantar o melhor 
modo de operar o sistema. (SHAMBLIN e 
STEVENS JR, 1979, p. 13). 
Foi então proposto um caso hipotético 
para ilustrar como proceder a resolução de um 
problema de Programação Linear por intermédio 
do método Simplex. Da ultima tabela deste caso 
hipotético, que indicou a solução ótima do 
Simplex, pode ser observado: 
 
 
Tabela 20: Considerações Quanto a Solução na Nova Tabela 
do Simplex. 
 
Das conclusões que podem ser obtidas 
da tabela do Simplex, tem-se: 
• O máximo valor que é possível para a função 
objetivo é de 180; 
• A solução ótima do problema é X1 = 20; X2 = 60; 
e X5 = 20; 
• A restrição 4 (restrição da demanda de soldados) 
que está relacionada com X5 (variável de folga) 
não é escassa, possuí uma folga de 20 o que 
significa que será deixado de atender a demanda 
de 20 unidades de soldados. 
 
Disto posto, este trabalho traz uma 
contribuição ímpar para o estudo científico, visto 
não haver muitas publicações descrevendo os por 
menores da aplicação do Simplex. Essa é uma 
dificuldade tanto de educadores como de alunos. 
Vários livros da área de Pesquisa Operacional 
não mencionam mais o Simplex e outros de forma 
superficial, mas este não é um problema recente, 
pois literaturas datadas deste as décadas de 60 e 
70 já não traziam muita contribuição. É claro que 
há boas referencias sobre o assunto, contudo não 
são fáceis de serem encontradas. 
 
5. Referências 
AGOSTI, Cristiano. Apostila de Pesquisa 
Operacional; Universidade do Oeste de Santa 
Catarina; 2003. 
CERVO, Amado Luiz; BERVIAN, Pedro Alcino. 
Metodologia Científica; 3ª edição; Ed. McGraw Hill do 
Brasil; São Paulo; 1983. 
DANTZIG, George B. Linear Programming. 
Departmente of Management Science and 
engineering, Satnford Unviersity. 1991, encontrado em 
http://www2.informs.org/History/dantzig/LinearProgram
ming_article.pdf, em 08/04/2009. 
DUCKWORTH, Eric. Guia à Pesquisa Operacional; 
Editora Atlas; São Paulo, 1972. 
GARVIN, Walter W. Introduction to Linear 
Programming. Ed. McGraw-Hill; New Yourk/USA; 
1960. 
GIRÃO, Sérgio Ellery; ELLENRIEDER, Alberto Ricardo 
Von. Programação Linear; Ed.Alveida Neves; Rio de 
Janeiro; 1971. 
LACHTERMACHER, Gerson. Pesquisa Operacional 
Na TomadaDe Decisões, 2ª edição; editora Campus; 
São Paulo/SP; 2004. 
HILLIER, Frederick S.; LIEBERMAN, Gerald J. 
Introduction To Operations Research; 8ª edition; Ed. 
McGraw-Hill; New York/USA; 2005. 
MARTÍN, Quintín Martí. Investigación Operativa; Ed. 
Prentice Hall; Madrid; 2003. 
MONTEVECHI, José Arnaldo. Pesquisa Operacional; 
Universidade Federal de Itajubá (UNIFEI); 2006. 
OLIVEIRA, Silvio Luiz de. Tratado de Metodologia 
Científica; Ed. Pioneira; São Paulo; 2002. 
SHAMBLIN, James E. & STEVENS JR, G.T. . 
Pesquisa Operacional – Uma Abordagem Básica; 
editora Atlas, São Paulo/SP; 1979. 
SILVA, Ermes Medeiros da. Et Al. Pesquisa 
Operacional; editora Atlas; 3ª edição; São Paulo; 
1998. 
http://www.iepg.unifei.edu.br/arnaldo/ensino/pos/mba/TURMA
2/po/aulas/aula_04/Aula_MetodoSimplex/Metodo_Simplex.htm 
consultado em 06/11/2008.