Tópico 1 Modelagem Resolugráfica e Simplex tabular versão 15 1

Prévia do material em texto

PESQUISA OPERACIONAL 
P R O F E S S O R : A D A L B E R T O N U N E S D E S I Q U E I R A 
Os resultados positivos conseguidos pela equipe de pesquisa 
operacional inglesa motivaram os Estados Unidos a iniciarem 
atividades semelhantes. Apesar de ser creditada à Inglaterra a 
origem da Pesquisa Operacional, sua propagação deve-se 
principalmente à equipe de cientistas liderada por George B. 
Dantzig, dos Estados Unidos, convocada durante a Segunda 
Guerra Mundial. Ao resultado deste esforço de pesquisa, 
concluído em 1947, deu-se o nome de Método Simplex. 
1.1 - A origem da Pesquisa Operacional 
 
Durante a Segunda Guerra Mundial, um grupo de cientistas foi 
convocado na Inglaterra para estudar problemas de estratégia 
e de tática associados com a defesa do país. O objetivo era 
decidir sobre a utilização mais eficaz de recursos militares 
limitados. A convocação deste grupo marcou a primeira 
atividade formal de pesquisa operacional. 
Uma característica importante da pesquisa operacional e 
que facilita o processo de análise e de decisão é a 
utilização de modelos. Eles permitem a experimentação 
da solução proposta. Isto significa que uma decisão pode 
ser mais bem avaliada e testada antes de ser 
efetivamente implementada. A economia obtida e a 
experiência adquirida pela experimentação justificam a 
utilização da Pesquisa Operacional. . 
1.2 - O que é Pesquisa Operacional? 
 
A pesquisa operacional é um ramo interdisciplinar da 
matemática aplicada que faz uso de modelos 
matemáticos e de algoritmos na ajuda à tomada de 
decisões. É usada sobretudo para analisar sistemas 
complexos do mundo real, tipicamente com o objetivo de 
melhorar ou otimizar a performance. 
A programação linear ou pesquisa operacional é uma 
das muitas técnicas analíticas recentemente 
desenvolvidas que se têm mostrado úteis na resolução 
de certos tipos de problemas empresariais. Esses 
métodos quantitativos de resolução de problemas, como 
muitos aplicados na pesquisa operacional, são baseados 
em conceitos matemáticos e estatísticos. 
1.3 - Objetivos de estudo da Pesquisa Operacional 
 
a) reconhecer os problemas que passíveis de análise 
pelo modelo; 
 
b) auxiliar o analista no estágio inicial da investigação; 
 
c) avaliar e interpretar inteligentemente os resultados; 
 
d) aplicar os resultados com a confiança que é adquirida 
somente com a compreensão dos problemas e dos 
resultados envolvidos. 
A confiabilidade da solução obtida através do modelo 
depende da validação do modelo na representação do 
sistema real. A validação do modelo é a confirmação de que 
ele realmente representa o sistema real. A diferença entre a 
solução real e a solução proposta pelo modelo depende 
diretamente da precisão do modelo em descrever o 
comportamento original do sistema. 
1.4 Modelagem 
 
Um modelo é uma representação de um sistema real, que 
pode já existir ou ser um projeto aguardando execução. 
No primeiro caso, o modelo pretende reproduzir o 
funcionamento do sistema, de modo a aumentar sua 
produtividade. No segundo caso, o modelo é utilizado 
para definir a estrutura ideal do sistema. . 
1.5 – Equação Linear 
 
Uma equação linear é uma equação composta exclusivamente 
de adições e subtrações de termos que são constantes ou o 
produto de uma constante pela primeira potência de uma 
variável. 
Conforme a natureza do problema que dá origem a equação, as 
constantes e as variáveis podem ser números inteiros, reais, 
complexos ou ter uma estrutura ainda mais geral. 
Uma equação linear em n variáveis é uma equação que pode 
ser colocada na forma: 
a1x1 + a2x2 + a3x3 +....+anxn=b 
 
sendo que os escalares a1, a2, a3....an são denominados 
coeficientes, e b é chamado de termo independente, ou termo 
constante. 
Por exemplo, ( − 1, − 1) é uma solução da equação linear 
 x + 3y = − 4, uma vez que -1 + 3(-1) = − 4, mas (1,5) não. 
 
 No caso em que a quantidade de variáveis em uma 
equação linear é menor ou igual a três, pode-se associar ao 
seu conjunto solução, uma interpretação geométrica 
Uma solução da equação linear 
a1x1 + a2x2 + a3x3 +....+anxn=b é uma n-upla (um vetor) , 
s=(s1,s2,s3...sn) cujas entradas sj podem ser colocadas no 
lugar de cada xj, para j=1,...,n , de modo que a igualdade 
seja verdadeira. O conjunto solução de uma equação 
linear é aquele formado por todas as suas soluções. 
Se n é igual a 2, a equação linear tem como 
correspondente geométrico uma linha reta. 
Exemplos: 
 
Y= -x + 5 pode ser representada pela reta que passa 
pelos pontos (0,5) e (5,0). 
 
Y= x/2 + 2 corresponde a reta que contém os pontos 
( − 4,0) e (2,3). 
 
 
 
 
 
Sistemas de equações lineares 
Um sistema de equações lineares (ou sistema linear) é uma 
coleção de equações lineares envolvendo o mesmo 
conjunto de variáveis. Um sistema geral de m equações 
lineares com n incógnitas (ou variáveis) pode ser escrito 
como 
Se n for 3, o conjunto solução é representado 
geometricamente como um plano no espaço 
tridimensional. 
Uma solução de um sistema linear é uma n-upla de valores 
s = (s1,s2,....,sn) que simultaneamente satisfazem todas as 
equações do sistema. 
Cada equação de um sistema linear em três variáveis determina 
um plano. Uma solução do sistema corresponde a um ponto na 
interseção desses planos. O conjunto solução de um sistema linear 
é a interseção entre os conjuntos soluções de cada equação do 
sistema (veja a figura). Um sistema linear é dito consistente se 
possui alguma solução. Caso contrário, é chamado de 
inconsistente. 
 
Cada equação de um sistema linear em três variáveis determina 
um plano. Uma solução do sistema corresponde a um ponto na 
interseção desses planos 
Em geral, para qualquer sistema linear existem três 
possibilidades a respeito das soluções: 
 
Uma única solução: Neste caso, existe apenas uma solução 
específica (uma certa n-upla). O conjunto S tem um único 
elemento. Geometricamente, isto implica que os n-planos 
determinados pelas equações do sistema se intersectam todos 
em um mesmo ponto do espaço, que é especificado pelas 
coordenadas da solução (as "entradas" da n-upla). O sistema é 
dito possível (existe alguma solução) e determinado (existe uma 
única solução); 
 
Nenhuma solução: Nesta situação, não existe qualquer n-upla 
de valores que verifiquem simultaneamente todas as 
equações do sistema. O conjunto S é vazio. Geometricamente, 
os n-planos correspondentes as equações não se intersectam 
(são paralelos). O sistema é dito impossível (não existe 
solução). 
Infinitas soluções: As equações especificam n-planos cuja 
intersecção é um m-plano onde é possível explicitar um 
conjunto S com infinitas soluções. O sistema é dito possível 
(existe alguma solução) e indeterminado (sua quantidade é 
infinita) 
 
As seguintes figuras ilustram os casos citados 
anteriormente: 
2 A Modelagem Matemática na Pesquisa Operacional 
2.1 - Componentes iniciais da Modelagem 
Em um modelo matemático, são incluídos três conjuntos 
principais de elementos: 
1. Variáveis de decisão e parâmetros: variáveis de decisão são 
as incógnitas a serem determinadas pela solução do modelo. 
Parâmetros são valores fixos no problema; 
2. Restrições: de modo a levar em conta as limitações físicas 
do sistema, o modelo deve incluir restrições que limitam as 
variáveis de decisão a seus valores possíveis (ou viáveis); 
3. Função Objetivo: é uma função matemática que define 
a qualidade da solução em funçãodas variáveis de 
decisão. 
Para melhor ilustrar ao conjuntos acima, considere o seguinte 
exemplo: 
"Uma empresa de comida canina produz dois tipos de 
rações: Tobi e Rex. Para a manufatura das rações são 
utilizados cereais e carne. Sabe-se que: 
I) a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a 
ração Rex utiliza 4 kg de carne e 2 kg de cereais; 
 
Deseja-se saber qual a quantidade de cada ração a 
produzir de modo a maximizar o lucro. 
II) o pacote de ração Tobi custa $ 20 e o pacote de ração 
Rex custa $ 30; 
III) o kg de carne custa $ 4 e o kg de cereais custa $ 1; 
IV) estão disponíveis por mês 10 000 kg de carne e 
30 000 kg de cereais. 
variáveis de decisão: quantidades de ração de cada tipo a 
serem produzidas. 
 
parâmetros fornecidos: preços unitários de compra e 
venda, além das quantidades de carne e cereais 
utilizadas em cada tipo de ração. 
 
 
Restrições: limites de carne e cereais e a 
 
 
função objetivo: função matemática que determine o lucro 
em função das variáveis de decisão e que deve ser 
maximizada. 
Um estudo de pesquisa operacional geralmente envolve 
as seguintes fases: 
 
(1) definição do problema; 
(2) construção do modelo; 
(3) solução do modelo; 
(4) validação do modelo; 
(5) implementação da solução 
Apesar da seqüência acima não ser rígida, ela indica as 
principais etapas a serem vencidas. A seguir, é 
apresentado um resumo da cada uma das fases. 
2.2.1 Definição do problema A definição do problema 
baseia-se em três aspectos principais: 
 
I) descrição exata dos objetivos do estudo; 
II) identificação das alternativas de decisão existentes; 
III) reconhecimento das limitações, restrições e exigências 
do sistema. 
A descrição dos objetivos é uma das atividades mais 
importantes em todo o processo do estudo, pois a partir 
dela é que o modelo é concebido. Da mesma forma, é 
essencial que as alternativas de decisão e as limitações 
existentes sejam todas explicitadas, para que as soluções 
obtidas ao final do processo sejam válidas e aceitáveis. 
2.2.2 Construção do modelo 
A escolha apropriada do modelo é fundamental para a 
qualidade da solução fornecida. Se o modelo elaborado 
tem a forma de um modelo conhecido, a solução pode ser 
obtida através de métodos matemáticos convencionais. 
Por outro lado, se as relações matemáticas são muito 
complexas, talvez se faça necessária a utilização de 
combinações de metodologias. 
2.2.3 Solução do modelo 
O objetivo desta fase é encontrar uma solução para o 
modelo proposto. Ao contrário das outras fases, que não 
possuem regras fixas, a solução do modelo é baseada 
geralmente em técnicas matemáticas existentes. No caso 
de um modelo matemático, a solução é obtida pelo 
algoritmo mais adequado, em termos de rapidez de 
processamento e precisão da resposta. 
2.2.4 Validação do modelo 
 
Nessa altura do processo de solução do problema, é 
necessário verificar a validade do modelo. Um modelo é 
válido se ele for capaz de fornecer uma previsão aceitável 
do comportamento do sistema. 
 
2.2.4 Validação do modelo 
 
Um método comum para testar a validade do sistema é 
analisar seu desempenho com dados passados do 
sistema e verificar se ele consegue reproduzir o 
comportamento que o sistema apresentou. 
2.2.5 Implementação da solução 
 
 Avaliadas as vantagens e a validação da solução obtida, 
esta deve ser convertida em regras operacionais. 
 
 A implementação, por ser uma atividade que altera uma 
situação existente, é uma das etapas críticas do estudo. 
 
3 Programação Linear 
3.1 - Definição 
 
O problema geral de programação linear é utilizado para 
otimizar (maximizar ou minimizar) uma função linear de 
variáveis, chamada de "função objetivo", sujeita a uma série de 
equações ou inequações lineares, chamadas restrições. A 
formulação do problema a ser resolvido por programação linear 
segue alguns passos básicos. 
Deve ser definido o objetivo básico do problema, ou seja, a 
otimização a ser alcançada. Por exemplo, maximização de 
lucros, ou de desempenhos, ou de bem-estar social; 
minimização de custos, de perdas, de tempo. Tal objetivo será 
representado por uma função objetivo, a ser maximizada ou 
minimizada; 
3 Programação Linear 
Para que esta função objetivo seja matematicamente 
especificada, devem ser definidas as variáveis de decisão 
envolvidas. Por exemplo, número de máquinas, a área a ser 
explorada, as classes de investimento à disposição etc. 
Normalmente, assume-se que todas estas variáveis possam 
assumir somente valores positivos; 
Estas variáveis normalmente estão sujeitas a uma série de 
restrições, normalmente representadas por inequações. Por 
exemplo, quantidade de equipamento disponível, tamanho da 
área a ser explorada, capacidade de um reservatório, 
exigências nutricionais para determinada dieta etc 
3 Programação Linear 
3.2 - Formulação de Modelos 
 
O problema geral de programação linear pode ser definido por 
Maximizar (ou minimizar) Z = c¹ x¹ + c² x² + ...+ cn xn 
3 Programação Linear 
Exemplo 
Voltando ao exemplo anterior: Uma empresa de comida canina 
produz dois tipos de rações: Tobi e Rex. Para a manufatura das 
rações são utilizados cereais e carne. Sabe-se que: 
a) a ração Tobi utiliza 5 kg de cereais e 1 kg de carne, e a ração 
Rex utiliza 4 kg de carne e 2 kg de cereais; 
b) o pacote de ração Tobi custa $ 20 e o pacote de ração Rex 
custa $ 30; 
c) o kg de carne custa $ 4 e o kg de cereais custa $ 1; 
d) estão disponíveis por mês 10 000 kg de carne e 30 000 kg 
de cereais. 
 
Deseja-se saber qual a quantidade de cada ração a produzir de 
modo a maximizar o lucro. 
3 Programação Linear 
Nosso modelo deseja maximizar o lucro (Z) a partir da 
quantidade de ração Tobi (x1) e de ração Rex (x2). A Tabela a 
seguir apresenta o cálculo do lucro unitário de cada ração. 
Variáveis de decisão: 
X1: Quantidade da ração Tobi a ser produzida 
X2: Quantidade da ração Rex a ser produzida 
Função objetivo: 11 X1 + 12X2 
 
Restrições: 
 
 
4 Solução Gráfica 
Os problemas de pesquisa operacional com apenas duas 
variáveis podem ser resolvidos através da solução gráfica. 
A solução gráfica pode ser feita em 03 passos: 
 
a) Identificação e construção das retas de restrição; 
b) Identificação da região viável; 
c) Identificação do ponto ótimo; 
a) Voltando ao exemplo anterior 
 
O problema da empresa de comida canina com apenas duas 
variáveis pode ser resolvido graficamente. Traça-se um gráfico 
com os seus eixos sendo as duas variáveis x1 e x2. A partir daí, 
traçam-se as retas referentes às restrições do problema e 
delimita-se a região viável (Figura A). 
b) Identificação e construção das retas de restrição 
 
As variáveis X e Y representam os eixos do plano cartesiano. 
As restrições definem o que é chamado de região viável, ou 
sejam a região onde a solução ótima deve estar. A região 
viável é criada utilizando-se todas as restrições do problema. 
As restrições de não-negatividade estabelecem que a solução 
ótima deve estar apenas na região onde as variáveis 
assumem valores positivos. 
Exemplo do exercício da Ração Tobi e Rex: 
c) Identificação da região viável 
Após definidas todas as retas (ou planos) de restrições, o próximo passo é 
identificar a região viável, que será a região de intersecção de todos os 
planos ou retas, conforme demonstrado abaixo: 
Exemplo 2 
Uma artesã produz colares e pulseiras. Os colares sãovendidos a R$18,00 e as pulseiras à R$15,00. Ela gasta 
R$ 15,00 em matéria prima para fabricar o colar e 
R$13,00 para a pulseira . Cada colar utiliza 2 pedras de 
cristal e 1 detalhe de metal. Já a pulseira utiliza 1 pedra 
de cristal e 1 detalhe de metal. 
A artesã consegue comprar apenas 100 pedras de cristal 
por dia e 80 detalhes de metal. Ambos os adornos 
utilizam outros materiais como couro, linha, etc. mas que 
não tem problemas para serem obtidos. A artesã também 
percebeu que ela não consegue vender mais que 35 
colares por dia. 
Qual a quantidade de colares e pulseiras que ela deve 
fazer? 
 
 
1) Variáveis de decisão: 
X1=Quantidade de colares 
X2=Quantidade de pulseiras 
 
2) Função objetivo: 
Max L=18X1+15X2-(15X1+13X2) 
Max L=3X1+2X2 
 
3) Restrições 
Pedras de Cristal:2X1+X2≤100 
Detalhes de Metal:X1+X2≤80 
Demanda de colares:X1≤35 
X1 e X2≥0 
Resumo: 
Max L=3X1+2X2 
 
Sujeito a: 
 
2X1+X2≤100 
X1+X2≤80 
X1≤35 
X1≥0 
X2≥0 
Solução gráfica: 
Inicialmente vamos encontrar a região de solução do 
problema que é o conjunto dos pontos que satisfazem 
todas as restrições 
1) Para 2X1+X2≤100, temos 
X1=0;X2=100 e X2=0;X1=50 
2) Para X1+X2≤80, temos 
X1=0;X2=80 e X2=0;X1=80 
3) Para X1≤35, temos 
X1=35 
Dessa maneira, definimos a 
região de solução, que se 
encontra entre as retas 
traçadas 
(0;100) 
(50;0) 
Agora, para acharmos o ponto 
ótimo, precisamos definir no gráfico 
a reta que será maximizada. 
Para isso, escolhe-se qualquer 
ponto (dentro da região de 
solução), ex.(10,0) 
Substituindo na Função objetiva 
3X1+2X2=3x10+2x0=30 assim 
Para 3X1+2X2=30, 
X2=(30-3X1)/2=15-(3/2)*X1 
Assim, para 
X1=0=>X2=15 
Então temos a reta que passa por 
(10,0) e (0,15). 
Finalmente, o ponto ótimo é (20,60) 
Max L=3X1+2X2=3x20+2x60=180 
Giapetto fabrica 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 a 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 de carpintaria. Um trem necessita de 1 hora para 
acabamento e 1 hora de carpintaria. 
Cada semana, Giapetto 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. Giapetto quer maximizar seu lucro diário 
(receitas-custos). Formular o modelo matemático que poderá ser usado 
por Giapetto para maximizar seu lucro semanal. 
Variáveis de decisão 
• X1 = número de soldados produzidos cada semana; 
• X2 = número de trens produzidos a cada semana. 
FUNÇÃO OBJETIVO 
 
• Receita por semana = 27*X1 + 21*X2 
• Custos de M.P. = 10*X1 + 9*X2 
• Custos de M.O. = 14*X1 + 10*X2 
 
Então Giapetto quer maximizar: 
(27X1 + 21X2) - (10X1 + 9X2) - (14X1 + 10 X2) = 3X1 + 2X2 
Restrição 1: 2X1 + X2 <= 100 (não mais de 100 h de acabamento) 
Restrição 2: 1X1 + X2 <= 80 (não mais de 80 h de carpintaria) 
Restrição 3: X1 <= 40 (venda máxima de soldados: 40) 
Restrições adicionais • X1 >= 0 
• X2 >= 0 
Se nós queremos delimitar em um gráfico o conjunto de pontos que satisfaça a: 
2X1+3X2 <= 6 eq (1) Onde, 6 atribuição inicial para F.O. 
3X2 <= 6 - 2X1 
X2<=1/3*(6 - 2X1) = 2 - 2/3X1 eq(2) 
Encontrando a solução ótima: 
 
Após a identificação da região de solução, nós devemos procurar a solução ótima, 
que será o ponto da região que levar ao maior valor de Z = 3X1+2X2 
Para encontrar a solução ótima, nós precisamos desenhar uma linha sobra a qual todos os 
pontos levem ao mesmo valor de Z. 
 
 
Escolhe-se qualquer ponto da região de solução: 
Escolhendo o ponto (20, 0) , temos que Z = 3X1+2X2 = 60 Assim (20, 0) cai sobre a reta: 
Z = 3X1 + 2X2 = 60 daí podemos concluir que X2 = 30 - 3/2X1 
 
Fazendo X1=0, temos que o outro ponto da reta é (0, 30) 
Importante: uma vez desenhada a reta, podemos encontrar todas as outras pelo 
movimento paralelo da reta que desenhamos. 
Ponto ótimo: 
Z = 3*20 + 2*60 = 180 
Após a identificação da região de solução, nós devemos procurar a solução 
ótima, que será o ponto da região que levar ao maior valor de Z = 3X1+2X2 
Método de Tentativas pelos extremos ou vértices: 
 
Como normalmente o ponto ótimo é localizado em algum dos vértices da 
região viável, o procedimento para encontrar a solução ótima é o da 
tentativa pelos extremos ou vértices. Ou seja, definida a região viável, 
encontra-se a coordenada (x;y) de cada vértice e logo após substitui-se na 
equação da função-objetivo. Das soluções encontradas, aquela que 
apresentar o maior valor ou menor valor esperado (dependendo da função-
objetivo) é a que deverá ser escolhida 
Exemplo (Minimização): 
Em uma dieta, cada 100 g de alimento A e B fornecem os 
seguintes elementos nutritivos (em unidades): 
As quantidade mínimas necessárias de elementos nutritivos, 
por dia, são 8 unidades de carboidratos, 19 unidades de 
vitaminas e 7 unidades de proteínas. Cada 100 g do alimento 
A contem 300 kcal (kilocalorias) e custa $ 50 u:m: enquanto 
cada 100 g do alimento B tem 500 kcl e custa $ 25 u:m: Como 
é possível minimizar o custo e a quantidade de calorias 
da dieta formada pelos alimento A e B? 
 visualmente é possível identificar o ponto (1,4) do plano cartesiano como sendo o ponto 
onde a função custo é minimizada, obtendo um custo mínimo de $ 150 u:m: com o 
consumo total de 2.300 kcal, enquanto o ponto (5,1) minimiza a quantidade 
de calorias, 2.000 kcal, com custo de $ 275 u:m: 
z1 = 50x1 + 25x2 (minimizar o custo) 
z2 = 300x1 + 500x2 (minimizar calorias) 
z1 
z2 
Restrição dos carboidratos 
Restrição das vitaminas 
Restrição das proteínas 
Região Viável 
O Método Simplex 
O Método Simplex caminha pelos vértices da região viável 
até encontrar uma solução que não possua soluções 
vizinhas melhores que ela. Esta é a solução ótima. A 
solução ótima pode não existir em dois casos: quando não 
há nenhuma solução viável para o problema, devido a 
restrições incompatíveis. 
 
Ou quando não há máximo (ou mínimo), isto é, uma ou 
mais variáveis podem tender a infinito e as restrições 
continuarem sendo satisfeitas, o que fornece um valor sem 
limites para a função objetivo. 
4.1 Exemplo de um Problema 
Uma marcenaria deseja estabelecer uma programação diária 
de produção. Atualmente, a oficina faz apenas dois produtos: 
mesa e armário, ambos de um só modelo. 
O processo de produção é tal que, para fazer uma mesa a 
fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. Para 
fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h 
de mão de obra. 
Para efeito de simplificação, vamos considerar que a 
marcenaria tem limitações em somente dois recursos: 
madeira e mão-de-obra, cujas disponibilidades diárias são 
mostradas na tabela a seguir. 
Cada mesa dá uma margem de contribuição para o lucro de 
$ 4 e cada armário de $ 1. O problema é maximizar a 
margem de contribuição total para o lucro." 
Montagem do modelo 
As variáveis de decisão envolvidas no problema são: 
x1: quantidade a produzir de mesas 
x2: quantidade a produzir de armários 
A função objetivo é: Lucro: z = 4x1 + x2 
Para as restrições, a relação lógica existente é: 
Utilização de recurso disponibilidade 
Assim temos 
O modelo completo é: 
Solução do modelo 
Já conhecemos o método de solução gráfica para 
problemas de programação linear de duas variáveis. 
Será agora apresentada a solução por sistemas de 
equações lineares. 
Ao se introduzir o conceito de folga de recurso, a 
inequação pode ser escrita como 
De forma a transformar as restrições do problema de 
programação linear de inequações em equações, são 
introduzidas as variáveis de folga. Neste problema, as 
restrições têm a seguinte estrutura lógica: 
Isso significa que 
Deste modo, a folga de cada recurso pode ser representada 
por uma variável de forma exatamente igual à produção de 
cada produto. Desse modo, vamos chamar: 
f1: folga de madeira; 
f2: folga de mão-de-obra. 
O problema se transformou em encontrar a solução do 
sistema de equações lineares que maximiza o lucro. Como 
neste caso o número de variáveis (m = 4) é superior ao 
número de equações (n = 2), o sistema é indeterminado, 
apresentando infinitas soluções. 
Introduzindo as variáveis de folga, o problema a ser 
resolvido passa a ser: 
No entanto, todas as variáveis devem ser maiores ou iguais 
a zero. Atribuir zero a uma variável significa não produzir um 
dos produtos (se a variável for x1 ou x2) ou utilizar toda a 
disponibilidade de recursos (se a variável for f1 ou f2). 
Uma vez resolvido um sistema, serão aplicados na função 
objetivo os valores encontrados. As variáveis zeradas são 
chamadas variáveis não-básicas. As variáveis cujos valores 
são calculados pelo sistema de equações são chamadas 
variáveis básicas. 
Desta forma, podemos encontrar soluções para o sistema 
de equações zerando duas variáveis (n - m = 2) e 
encontrando o valor para as duas variáveis restantes. 
Teremos que resolver então 
 Sistemas lineares a serem 
resolvidos. 
 
Comparando todas as soluções encontradas por este processo, achamos a 
solução ótima, ou seja, x1 = 4, x2 = 0, f1 = 4, f2 = 0, dando um lucro z = 16. 
 Desenvolvimento do Método Simplex 
Da forma como foi resolvido o problema anteriormente, é 
necessário que muitos sistemas de equações sejam resolvidos 
e suas soluções comparadas. 
 Para problemas reais de programação linear, esta solução se 
torna inviável. Desta forma, para termos condições de resolver 
um problema de programação linear, precisamos de uma 
sistemática que nos diga: 
• qual o sistema de equações que deve ser resolvido; 
• que o próximo sistema a ser resolvido fornecerá uma 
solução melhor que os anteriores; 
• como identificar um solução ótima, uma vez que a tenhamos 
encontrado. 
 Essa sistemática é o método Simplex, e as regras que o método 
utiliza para atender às três questões acima são, basicamente, 
os critérios que desenvolvemos nos itens anteriores. Vamos 
voltar ao nosso pequeno problema, já com as variáveis de folga: 
 
A última linha contém os coeficientes (contribuição para o lucro 
total z, por unidade em cada interação) das variáveis na função 
objetivo. Essa última linha será chamada de função objetivo 
transformada, ou função z-transformada. 
Vamos montar um quadro para ordenarmos as operações, 
colocando nele apenas os coeficientes das variáveis. No caso da 
função objetivo, vamos realizar a seguinte transformação: 
a) Solução inicial 
A solução inicial para o problema será sempre obtida fazendo 
as variáveis originais do modelo (no caso x1 e x2) iguais a zero e 
achando o valor das demais. 
Assim, fazendo x1 = x2 = 0 (variáveis não básicas), obtemos do 
Quadro 1: 
f1 = 12 
f2 = 8 (variáveis básicas) 
z = 0 
As variáveis básicas estão indicadas no Quadro 1, para facilitar 
o acompanhamento das operações. 
b) Segunda solução 
Como a primeira solução não é a melhor, vamos procurar outra 
que dê um valor maior para z. O problema é descobrir: 
• Das duas variáveis não básicas (nulas) na primeira solução, 
qual deve se tornar positiva? 
• Das duas variáveis básicas (positivas) na primeira solução, 
qual deverá ser anulada? 
Assim, aplicando o critério de que devemos produzir 
primeiro o produto que mais contribui para o lucro, vamos 
começar a produção pela variável x1, já que sua 
contribuição unitária para o lucro (4) é maior que a 
contribuição de x2, igual a 1. 
Logo, a variável que deverá se tornar positiva é x1. 
Qual variável deverá se tornar positiva (entrar na base)? 
Vamos observar que na última linha do Quadro 1 temos os 
coeficientes da função objetivo que mostram a contribuição 
para o lucro z de cada unidade produzida de mesa (x1) e de 
armário (x2). 
Qual variável deverá ser anulada (deixar a base)? 
Para identificá-la, deve-se realizar o seguinte procedimento: 
a) Dividir os elementos da última coluna pelos 
correspondentes elementos positivos da coluna da variável 
que vai entrar na base. caso não haja elemento algum 
positivo nesta coluna, o processo deve parar, já que a 
solução seria ilimitada. 
b) O menor quociente indica a equação cuja respectiva 
variável básica deverá ser anulada, tornando-se variável 
não básica. 
Assim, como o menor quociente é dado pela divisão 
8 / 2 = 4, a variável básica a ser anulada é f2, que é a 
variável positiva na atual solução, cujo valor foi 
encontrado na segunda linha. 
Assim temos: x2 = 0 e f2 = 0 
e o sistema restante deve ser resolvido para acharmos o 
valor de x1 e f1. A solução desse sistema será feita usando o 
Quadro 1 com as equações completas e usando as 
operações válidas com as linhas da Matriz. 
Gerar identidades 
Gerar este 
número 1 
Gerar este 
número 0 
Gerar este 
número 0 
Como todas as variáveis que estão fora da base têm 
coeficientes nulos ou positivos na linha da função 
objetivo, a solução atual é ótima 
x1 = 4, 
x2 = 0, 
f1 = 4, 
f2 = 0 e 
z = 16 
Procedimento do Método Simplex (Problemas de Maximização) 
Passo 1: Introduzir as variáveis de folga; uma para cada desigualdade. 
Passo 2: Montar um quadro para os cálculos, colocando os 
coeficientes de todas as variáveis com os respectivos sinais e, na 
última linha, incluir os coeficientes da função objetivo transformada. 
Passo 3: Estabelecer uma solução básica inicial, usualmente 
atribuindo valor zero às variáveis originais e achando valores positivos 
para as variáveis de folga. 
Passo 4: Como próxima variável a entrar na base, escolher a variável 
não básica que oferece, na última linha, a maior contribuição para o 
aumento da função objetivo (ou seja, tem o maior valor negativo). Se 
todas as variáveis que estão fora da base tiverem coeficientes nulos 
ou positivos nesta linha, a solução atual é ótima. Se alguma dessas 
variáveis tiver coeficiente nulo, isto significa que ela pode ser 
introduzida na base sem aumentar o valor da função objetivo. Isso 
quer dizer que temos uma solução ótima, com o mesmo valor da 
função objetivo. 
Procedimento do Método Simplex (Problemas de Maximização) 
Passo 5: Para escolher a variável que deve deixar a base, deve-se 
realizar o seguinte procedimento: 
a) Dividir os elementos da última coluna pelos correspondentes 
elementos positivos da coluna da variável que vai entrar na base. caso 
não haja elemento algum positivo nesta coluna, o processo deve parar, 
já que a solução seria ilimitada. 
b) O menor quociente indica a equação cuja respectiva variável básica 
deverá ser anulada, tornando-se variável não básica. 
Passo 6: Usando operações válidas com as linhas da matriz,transformar o quadro de cálculos de forma a encontrar a nova solução 
básica. A coluna da nova variável básica deverá se tornar um vetor 
identidade, onde o elemento 1 aparece na linha correspondente à 
variável que está sendo anulada. 
Passo 7: Retornar ao passo 4 para iniciar outra iteração. 
0,11 
Resposta : x2=0,11 (variável na base) 
Resposta : xF2 =0 (variável fora da base) 
Qual o valor da variável XF2? 
12 
Resposta : Z =12