Método Simplex - Como solucionar

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO

GIOVANI FRANÇA

JOÃO PEDRO CORRÊA

TRABALHO DE ANÁLISE NUMÉRICA

Solução de Sistemas de Inequações – Método Simplex

Macaé[pic 1]

2016

[pic 2]

GIOVANI FRANÇA

JOÃO PEDRO CORRÊA

TRABALHO DE ANÁLISE NUMÉRICA

Solução de Sistemas de Inequações – Método Simplex

Esse trabalho é uma atividade avaliativa para a matéria

 Análise Numérica, ministrada pelo professor Marcio Magini,

na Universidade Federal do Rio de Janeiro – Campus Macaé

Macaé

2016

1. INTRODUÇÃO

Esse trabalho consiste em analisar uma aplicação de um método de solução de inequações. Os objetivos desse trabalho são aprender tal método, em quais situações podemos utiliza-lo, qual informação ele nos passa além de todos os seus benefícios.

Foi escolhido um artigo no qual os estudantes da UEPA (Universidade do Estado do Pará) aplicaram o método Simplex para a maximização do lucro de uma panificadora local. Em primeiro lugar, foi escolhido quais as variáveis de interesse, que são 2:

 Pães de massa grossa -> X1

 Pães de massa fina -> X2

Depois, identificou-se as respectivas restrições de recursos:

                 Trigo (Kg)[pic 3]

                                        Fermento (Kg)

Quantidades disponíveis            

         Água (Litro)

 Mão de obra (homens x hora)

1.  MÉTODO SIMPLEX

Montagem do modelo:

Elementos	Pão massa grossa (1 lote de 2000 pães) – X1	Pão massa fina (1 lote de 1200 pães) – X2	Total/Mês
Trigo (Kg)	100	50	15000
Fermento (Kg)	0,5	0,5	50
Água (L)	30	40	4500
Mão de obra (homens x hora)	4	4	940
Lucro por lote	R$ 300,00	R$120	Z

Com os dados organizados na tabela modelou-se o problema:

Função objetivo => F.O máx. = Lucro = Z = 300X1 + 120X2 [pic 4]

                        Trigo: 100X1+ 50X2 ≤ 15000

                        Fermento: 0,5X1 + 0,5X2 ≤ 500

Restrições                    Água: 30X1 + 40X2 ≤ 4500

                        Mão de Obra: 4X1 + 4X2 = 940

                        Não negatividade: X1 e X2 ≥ 0

    2.2     SOLUÇÃO DO MODELO

De forma a transformar as restrições do problema 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:

Utilização de recurso <= Disponibilidade.

Ao se introduzir o conceito de folga de recurso, a inequação pode ser escrita como:

Utilização de recurso + Folga = Disponibilidade.

Isso significa que

Utilização de recurso < Disponibilidade implica               Folga > 0;

Utilização de recurso = Disponibilidade implica               Folga = 0.

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 trigo;

F2 = folga de fermento;

F3 = folga de água;

F4 = folga de mão de obra;

Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser:

        

Lucro => Z = 300X1 + 120X2 => Z – 300X1 – 120X2 = 0

        Trigo => 100X1 + 50X2 + F1 = 15000

        Fermento => 0.5X1 + 0.5X2 + F2 = 50

        Água => 30X1 + 40X2 + F3 = 4500

        Mão de obra => 4X1 + 4X2 + F4 = 940        

 

 

  2.3     APLICAÇÃO DO MÉTODO

Primeiro, montamos a tabela:

Z	X1	X2	F1	F2	F3	F4	B
1	-300	-120	0	0	0	0	0
0	100	50	1	0	0	0	15000
0	0.5	0.5	0	1	0	0	50
0	30	40	0	0	1	0	4500
0	4	4	0	0	0	1	940

• 1º Passo: Identificar a variável que entra => identificada como a variável que possui o maior valor absoluto na segunda linha da tabela, ou seja, X1.

• 2º Passo: Identificar a linha que sai => Fazemos Bi/X1i, e selecionamos a fração de menor valor.

3ª linha => 15000/100 = 150

4ª linha => 50/0.5 = 100        

5ª linha => 4500/30 = 150

6ª linha => 940/4 = 235

• 3º Passo: Identificar o elemento pivô => é o elemento que está na coluna da variável que entra (X1) e na linha que sai (4ª linha)

Elemento pivô => 0,5

        Agora com o elemento pivô, serão realizadas operações matemáticas para construção de uma nova tabela, que terá como base a nova linha pivô (linha que contém o elemento pivô).