Buscar

aula 4 Pesquisa Operacional

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Programação Linear com o uso 
do Método Simplex 
Fabiana Gomes dos Passos 
Roteiro da aula 
 
• Método Simplex 
 
– Apresentação e fundamentos do Método Simplex; 
– Procedimento do Método Simplex para problemas na 
forma padrão – Maximização; 
– Exemplo de Aplicação. 
 
 
 
 
 
 
 Apresentação do Método Simplex 
 Resolver um problema de Programação Linear significa basicamente 
resolver sistemas de equações lineares e calcular o valor da função 
objetivo; 
 Esse procedimento, apesar de correto, é bastante trabalhoso, podendo 
ficar impraticável 
 Para resolver um problema real 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 a solução ótima, uma vez que a tenhamos 
encontrado 
 Essa sistemática é dada pelo Método Simplex 
Fundamentos do Método Simplex 
 
 O método SIMPLEX exige que o problema de otimização apresente 
todas as restrições em igualdade; 
 
 
 Isto não é uma limitação para a aplicação do método, pelo fato que 
é possível transformar todos os problemas para esta forma; 
 
 
 
 
Fundamentos do Método Simplex 
 
 Caso 1 – Desigualdade do tipo menor ou igual 
 
 
 
 
 Pode incluir uma variável de folga de tal forma que a nova 
restrição é: 
 
 
 
 
 
31 x
03 x
331  xx
Fundamentos do Método Simplex 
 
 Caso 2 – Desigualdade do tipo maior ou igual 
 
 
 
 
 Pode incluir uma variável de excesso de tal forma que a nova 
restrição é: 
 
 
 
 
 
04 x
942  xx
92 x
Fundamentos do Método Simplex 
 
• Restrição ≤ ⇒ Variável de Folga 
– Representa, economicamente, à quantidade de recurso 
não consumido; 
 
• Restrição ≥ ⇒ Variável de Excesso 
- Corresponde, economicamente, à quantidade de recurso 
consumido além do mínimo requerido; 
Fundamentos do Método Simplex 
 
 Caso 3 – Lado direito negativo ( b < 0) 
 
 
 Multiplica-se a expressão por (-)1. 
 
 
 
 
Procedimento do Método Simplex 
(problemas na forma padrão - Maximização) 
Introduzir as variáveis de folga, uma para cada desigualdade 
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. 
Estabelecer uma solução básica inicial, usualmente atribuindo 
zero às variáveis originais e achando valores positivos para as 
variáveis de folga. 
Como próxima variável a entrar na base, escolher a variável não-
básica que fornece, 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 nessa linha, a solução atual é ótima. 
Se alguma dessas variáveis tiver valor nulo, temos outra solução 
ótima, com o mesmo valor da função-objetivo. 
Passo 1: 
Passo 2: 
 
Passo 3: 
 
Passo 4: 
 
Procedimentos do Método Simplex 
(problemas na forma padrão - Maximização) 
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. Se não houver elemento 
nenhum positivo nessa coluna, o processo deve parar, já 
que a solução é ilimitada. 
b)O menor coeficiente indica a equação cuja respectiva 
variável básica deverá ser anulada, tornando-se variável 
não-básica. 
Usando operações com as linhas da matriz, transformar a 
coluna da nova variável básica num vetor identidade, onde o 
elemento 1 aparece na linha correspondente à variável que 
está sendo anulada. 
Retornar ao PASSO 4 para iniciar nova iteração. 
Passo 5: 
 
 
 
 
 
Passo 6: 
 
 
Passo 7: 
Exemplo 
o A Companhia MAXIMÓVEIS fabrica 2 tipos de produtos: 
o Cadeiras e Mesas 
o Margem de Contribuição Unitária: 
o Cadeira = $ 8,00 
o Mesa = $ 6,00 
o As cadeiras e mesas são processadas em 2 departamentos: 
o Montagem 
o Acabamento 
 
 Através dos dados contidos na tabela , formule um modelo de 
programação linear para determinar a produção diária de cada 
um dos modelos de modo a maximizar o lucro total da 
companhia. 
Exemplo 
o Cada unidade dos produtos consome as seguintes horas na fabricação: 
Departamento 
Montagem 
Acabamento 
 Cadeiras 
4 
2 
Mesas 
2 
4 
Horas totais 
disponíveis 
60 
48 
Horas por unidade 
 
 
• Variáveis 
X1 = Quantidade de cadeiras; 
X2 = Quantidade de mesas; 
Z = lucro total da companhia. 
• Restrições 
a) Limitação de montagem ; 
b) Limitação de acabamento; 
c) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da companhia 
0,
4842
6024:.
68
21
21
21
21




xx
xx
xxas
xxZMax
 
1. Qual o mix de produção entre mesas e cadeiras que 
maximiza o lucro da firma? 
 
2. Qual será o lucro máximo da companhia? 
Problema 
 
Solução Gráfica 
4 – Encontrar a solução pela comparação dos pontos 
extremos 
 Através de todos os pontos extremos da área de soluções viáveis 
e escolhemos aquele com maior MCT 
CADEIRA 
MESA 
(0,12) 
Solução ótima 
(15,0) (0,0) 
(12,6) 
MCT = 8x1 + 6x2 
(0,0) MCT = 0 
(0,12) MCT = 72 
(15,0) MCT = 120 
(12,6) MCT = 132 
 
 Desenvolvimento do Método Simplex 
Passo1: Introduzir as variáveis de folga 
 Max MCT = 8x1 + 6x2 + 0x3 + 0x4 
 Sujeito a: 
 4x1 + 2x2 + 1x3 = 60 
 2x1 + 4x2 + + 1x4 = 48 
 x1, x2, x3 e x4  0 
 
Transformar a função-objetivo: 
 de L = 8x1 + 6x2 
 para L - 8x1 - 6x2 = 0 
 
Desenvolvimento do Método Simplex 
Passo 2: Montar o quadro 
 Quadro 1: Fazendo as variáveis originais iguais a zero 
 x1 x2 x3 x4 b 
4 2 1 0 60 
2 4 0 1 48 
-8 -6 0 0 0 
a) Solução Inicial: 
 Fazendo as variáveis originais do modelo iguais a zero e 
achando o valor das demais 
 x1= x2 = 0 (variáveis não-básicas) 
 x3 = 60; x4= 48 e L= 0 
x3 
x4 
Variáveis 
básicas 
Base 
Função-objetivo 
transformada 
L 
 
 Desenvolvimento do Método Simplex 
b) Segunda Solução: 
 O problema é descobrir: 
 Das 2 variáveis não-básicas (nulas) na primeira solução, qual 
deverá se tornar positiva? 
 Das 2 variáveis básicas (positivas) na primeira solução, qual 
deverá ser anulada? 
 
 Qual deverá se tornar positiva? 
 Produzir primeiro o produto que mais contribui para o lucro, 
como indicado na última linha (maior valor negativo 
“absoluto”) 
 x1= 8 e x2 = 6 
 
18 
 
 Desenvolvimento do Método Simplex 
 Qual variável deverá ser anulada? 
Se formos produzir apenas o produto que mais contribui para o 
lucro (x1), qual a quantidade máxima possível? 
 1ª restrição: 4x1 + 0x2 = 60  Max x1 = 15 
 2ª restrição: 2x1 + 0x2 = 48  Max x1 = 24 
Essa análise pode ser feita diretamente do Quadro 1, dividindo-se os elementos 
da coluna b pelos correspondentes elementos da coluna x1 
O menor quociente indica, pela linha em que ocorreu, qual variável básica deve 
ser anulada. 
x1 x2 x3 x4 b 
4 2 1 0 60 
2 4 0 1 48 
-8-6 0 0 0 
x3 
x4 
Base 
L 
1ª linha: 60 / 4 = 15 
2ª linha: 48 / 2 = 24 
Variável a ser anulada: x3 
x2 = 0 
X3 = 0 
x1 = ? 
X4= ? 
 
 Desenvolvimento do Método Simplex 
Solução: fazendo operações com linhas, a partir do quadro 1, 
transformar a coluna da nova variável (x1) num vetor identidade, com 
o elemento 1 na linha correspondente à variável a ser anulada 
 1ª Operação: Dividir a 1ª linha por 4 
 
Quadro 1A: 
 
Base 
 x1 
 x4 
 L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
2 4 0 1 48 
-8 -6 0 0 0 
x1 x2 x3 x4 b 
4 2 1 0 60 
2 4 0 1 48 
-8 -6 0 0 0 
x3 
x4 
Base 
L 
Quadro 1: 
 
 
 Desenvolvimento do Método Simplex 
2ª Operação: Multiplicar a 1ª linha por –2 e somar à 2ª linha 
 
Quadro 1B: 
 
Base 
x1 
x4 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
0 3 -1/2 1 18 
-8 -6 0 0 0 
Quadro 1A: 
 
Base 
x1 
x4 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
2 4 0 1 48 
-8 -6 0 0 0 
21 
 
 Desenvolvimento do Método Simplex 
3ª Operação: Multiplicar a 1ª linha por 8 e somar à 3ª linha 
 
Quadro 1B: 
 
Base 
x1 
x4 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
0 3 -1/2 1 18 
-8 -6 0 0 0 
Quadro 2: 
 
Base 
x1 
x4 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
0 3 -1/2 1 18 
0 -2 2 0 120 
2ª Solução: X1 = 15; x4 = 18; L = 120 
22 
 
 Desenvolvimento do Método Simplex 
c) Terceira solução: 
 Qual deverá se tornar positiva? 
 Produzir primeiro o produto que mais contribui para o lucro, 
como indicado na última linha (maior valor negativo 
“absoluto”) 
 x2 
  Qual variável deverá ser anulada? 
O menor quociente (b/ x2) indica, pela linha em que ocorreu, qual 
variável básica deve ser anulada. 
x1 x2 x3 x4 b 
1 1/2 1 /4 0 15 
0 3 -1/2 1 18 
0 -2 2 0 120 
x1 
x4 
Base 
L 
1ª linha: 15 / 0,5 = 30 
2ª linha: 18 / 3 = 6 
Variável a ser anulada: x4 
x3 = 0 
X4 = 0 
x1 = ? 
X2= ? 
 
 Desenvolvimento do Método Simplex 
Quadro 2: 
 
x1 x2 x3 x4 b 
1 1/2 1 /4 0 15 
0 3 -1/2 1 18 
0 -2 2 0 120 
x1 
x4 
Base 
L 
Quadro 2A: 
 Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
0 1 -1/6 1/3 6 
0 -2 2 0 120 
Solução: fazendo operações com linhas, a partir do quadro 2, 
transformar a coluna da nova variável (x2) num vetor identidade, com 
o elemento 1 na linha correspondente à variável a ser anulada (x4) 
 4ª Operação: Dividir a 2ª linha por 3 
 
 
 Desenvolvimento do Método Simplex 
5ª Operação: Multiplicar a 2ª linha por – ½ e somar à 1ª linha 
 
Quadro 2B: 
 
Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 0 1/3 –1/6 12 
0 1 -1/6 1/3 6 
0 -2 2 0 120 
Quadro 2A: 
 
Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 1/2 1/4 0 15 
0 1 -1/6 1/3 6 
0 -2 2 0 120 
Desenvolvimento do Método Simplex 
6ª Operação: Multiplicar a 2ª linha por 2 e somar à 3ª linha 
 
Quadro 3: 
 
Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 0 1/3 –1/6 12 
0 1 -1/6 1/3 6 
0 0 5/3 2/3 132 
Quadro 2B: 
 
Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 0 1/3 –1/6 12 
0 1 -1/6 1/3 6 
0 -2 2 0 120 
 
 Desenvolvimento do Método Simplex 
 A última linha mostra as contribuições líquidas para o lucro, 
caso as variáveis x3 e x4 venham a ter seus valores 
aumentados de 0 para 1. 
 Como essas contribuições têm sinais trocados em relação ao 
quadro original, concluímos que a solução encontrada: 
 x1=12; x2= 6; x3= 0 e x4=0 é a solução ótima 
Quadro 3: 
 
Base 
x1 
x2 
L 
x1 x2 x3 x4 b 
1 0 1/3 –1/6 12 
0 1 -1/6 1/3 6 
0 0 5/3 2/3 132 
Exercício de Fixação 1 
 A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos 
produtos. A demanda é muito maior que a capacidade disponível (toda 
produção poderá ser vendida). 
 Através dos dados contidos na tabela, logo abaixo, qual o mix de produção 
entre janelas e portas que maximiza o lucro da Inc. E qual será o lucro 
máximo da companhia? 
Setor Produtivo 
Produto Capacidade 
Disponível Janelas Portas 
Montagem 1 hora/unid. - 4 horas/mês 
Laminação - 2 hora/unid. 12 horas/mês 
Corte 3 hora/unid. 2 hora/unid. 18 horas/mês 
Lucro Unitário $ 3,00 $ 5,00 
• Variáveis 
X1 = qtde. de janelas, em milhares de unidades; 
X2 = qtde. de portas, em milhares de unidades; 
Z = lucro total obtido com novos produtos. 
• Restrições 
a) disponibilidade do setor de montagem; 
b) disponibilidade do setor de laminação; 
c) disponibilidade do setor de corte; 
d) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da empresa 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Setor Produtivo 
Produto Capacidade 
Disponível Janelas Portas 
Montagem 1 hora/unid. - 4 horas/mês 
Laminação - 2 hora/unid. 12 horas/mês 
Corte 3 hora/unid. 2 hora/unid. 18 horas/mês 
Lucro Unitário $ 3,00 $ 5,00 
Exercício de Fixação 1 
Solução Gráfica 1 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
2 x 
9 
8 
7 
6 
5 
4 
3 
2 
1 
0 
0 1 2 3 4 5 6 7 8 9 
1 x 
12 2 2  x 
4 1  x 
18 2 3 2 1   x x 
0 2  x 
0 1  x Neste exemplo, a solução 
ótima está na interseção 
entre: 
a função-objetivo e 
qualquer uma das 
restrições, ou 
as 2 restrições 
Resolução do problema pelo Método Gráfico 
 Pelo gráfico, na intercessão entre 
as 2 restrições 
 
Laminação 2x2 = 12 (1) 
Corte 3x1 + 2x2 = 18 (2) 
 
Calculando x2 pela 1ª equação: 
2x2 = 12  x2 = 6 (3) 
Substituindo em 2: 
3x1 + 2(6) = 18 
3x1 + 12 = 18  3x1 = 6 x1 = 2 
 
Solução ótima: 2 janelas e 6 portas 
Calculando o Lucro Máximo 
 Substitua o ponto ótimo, encontrado 
anteriormente, na equação da 
função objetivo Z 
Solução ótima: 2 janelas e 6 portas 
 
Como X1 = 2 e X2 = 6 
 
Substituindo esses valores na função 
objetivo: 
 
 
3(2) + 5(6) = 6 + 30 = 36 
 
 O lucro máximo da companhia é 
R$ 36,00 
 
 
Exercício de Fixação 2 
Uma fábrica pretende produzir dois produtos, o produto 1 e o produto 2. Ambos os 
produtos passampor três fases de desenvolvimento durante o processo de 
manufatura, cada uma das quais se realiza num departamento diferente. No próximo 
mês, cada um dos departamentos tem um determinado números disponível de horas 
por máquina, para ser utilizado na concepção destes dois produtos. Por sua vez, cada 
um dos produtos requer, por unidade, um dado tempo de utilização de cada máquina. 
Tempo disponível (h) 
Tempo requerido por unidade (h) 
Produto 1 
Produto 2 
1 0 
0 2 2 
3 
4 12 18 
Departamentos 
1 2 3 
 
Para manter o problema simples, vamos assumir que os custos de produção de cada 
produto são constantes, independentemente da quantidade produzida. 
Supondo que o lucros, por unidade, de cada produto são de R$ 3 para o produto 1 e 
R$ 5 para o produto 2. Formule um modelo de programação linear para determinar a 
produção diária de cada um dos modelos de modo a maximizar o lucro total da 
companhia. 
• Variáveis 
X1 = produção diária do produto 1; 
X2 = produção diária do produto 2; 
Z = lucro total obtido com os dois produtos. 
• Restrições 
a) Tempo disponível para fabricar no departamento 1; 
b) Tempo disponível para fabricar no departamento 2; 
c) Tempo disponível para fabricar no departamento 3; 
d) quantidades não negativas. 
• Objetivo 
Maximizar o lucro total da companhia 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Exercício de Fixação 2 
Tempo disponível (h) 
Tempo requerido por unidade (h) 
Produto 1 
Produto 2 
1 0 
0 2 2 
3 
4 12 18 
Departamentos 
1 2 3 
Representação gráfica do problema 
 
x1 
x2 
2 4 
6 
8 
2 
4 
6 8 
x1 = 4 
2x2 = 12 
3x1 + 2x2 = 18 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
x1 
x2 
2 4 
6 
8 
2 
4 
6 8 
Z = 10 = 3x1 + 5x2 
Z = 20 = 3x1 + 5x2 
Z = 36 = 3x1 + 5x2 
(2, 6) 
Solução ótima: 2 produtos 1 e 
6 produtos 2 
 
Como X1 = 2 e X2 = 6 
3(2) + 5(6) = 6 + 30 = 36 
Lucro máximo é R$ 36,00 
 
Referências 
 
 
 
 
 
 
ANDRADE, Eduardo Leopoldino de. Introdução 
à pesquisa operacional: métodos e modelos 
para análise de decisões. 3. ed. Rio de Janeiro: 
LTC, 2004.192 p.

Outros materiais