Programação Linear: Método Simplex

Prévia do material em texto

MÉTODOS QUANTITATIVOS PARA TOMADA DE DECISÃO
Aula 05: PROGRAMAÇÃO LINEAR (PL): MÉTODO SIMPLEX
OBJETIVOS DA AULA:
Nesta aula será abordado o seguinte assunto:
- A utilização do método simplex para a solução de problemas de Programação Linear.
MÉTODO SIMPLEX
O Algoritmo dos Simplexos usa os conceitos básicos da álgebra matricial para a obtenção da solução viável ou ótima e que satisfaz a todas as restrições, sendo, portanto, uma ferramenta eficiente e eficaz, bem como rápida na localização de pontos ótimos que melhoram fortemente a função que queremos otimizar e indica quando a solução ótima foi atingida. 
Exemplo 1
Um fazendeiro deseja otimizar as suas plantações de arroz e de milho na sua fazenda. Ele deseja saber que áreas de arroz e milho devem plantar, para que o seu lucro seja máximo.
O lucro unitário esperado por área plantada de arroz é de R$ 5.000,00 e de milho R$ 2.000,00.
Sabe-se que as áreas plantadas de arroz e de milho não podem superar a 3 e 4 alqueires respectivamente.
O consumo total de homens-hora utilizados nas duas plantações não podem exceder a 9 homens-hora. Cada unidade de arroz plantada consome 1 homem-hora e de milho 2 homens-hora.
As áreas plantadas não podem ser negativas.
SOLUÇÃO
Variáveis de decisão:
	X1 = Qtd. de áreas de arroz
	X2 = Qtd. de áreas de milho
Parâmetros:
Áreas de arroz, áreas de milho e homens-hora
Restrições: 
Disponibilidade máxima de cada parâmetro: 3 alqueire de arroz, 4 alqueire de milho e 9 homens-hora
Função Objetivo:
Função objetivo a ser maximizada: 
		Zmáx.. = 5.000 X1 + 2.000 X2 
- Restrições técnicas: 
	áreas de arroz X1 3 
	áreas de milho 		 X2 	 4 
	homens-hora 	X1 + 2 X2 9 
 
 - Restrições de não negatividade: X1 0 e X2 0 
 	
 As variáveis controladas ou variáveis de decisão são: X1 e X2. 
 A função objetivo mede o desempenho do sistema, no caso a capacidade de maximizar o custo, para cada solução apresentada.
- REGRAS DO SIMPLEX
A utilização das regras do Algoritmo dos Simplexos, facilita o entendimento do seu uso.
1ª) O primeiro passo é transformar as inequações em equações. Isto é feito, utilizando-se as chamadas variáveis de folga. As variáveis de folga assumirão o sinal positivo (+), se o sentido da restrição for do tipo menor e igual (≤); se o sentido da restrição for do tipo maior e igual (≥), assumirão o sinal negativo (-).
2ª) No caso das restrições do tipo maior e igual (≥), cuja variável de folga assume o sinal negativo (-), é necessário também da utilização das chamadas variáveis artificiais; 
3ª) As variáveis de folga assumirão os valores crescentes, após as variáveis originais do problema. Um problema com três inequações e duas variáveis (X1 e X2), as variáveis de folga serão: X3 para a primeira inequação, X4 para a segunda inequação e X5 para a terceira inequação.
4ª) A função objetiva deverá ser multiplicada por (-1), para que o valor final do quadro do simplex seja positivo.
5ª) O passo seguinte é a construção do quadro do simplex, que tem a seguinte estrutura:
__________________________________________
BASE X1 X2 X3 X4 X5 b
__________________________________________
X3 1 0 1 0 0 3
__________________________________________
X4 0 1 0 1 0 4
__________________________________________
X5 1 2 0 0 1 9
__________________________________________
 -Z -5 -2 0 0 0 0
6ª) DETERMINAÇÃO DA VARIÁVEL QUE ENTRARÁ NA BASE: escolhe-se na linha de –Z, dentre as variáveis que tenham sinal negativo, a mais negativa de todas.
7ª) DETERMINAÇÃO DA VARIÁVEL QUE SAIRÁ DA BASE: divide-se os valores da coluna b, pelos valores da coluna que entrará na base. Escolhe-se o menor valor da divisão. 
BASE X1 X2 X3 X4 X5 b
__________________________________________
X3 1 0 1 0 0 3
__________________________________________
X4 0 1 0 1 0 4
__________________________________________
X5 1 2 0 0 1 9
__________________________________________
 -Z -5 -2 0 0 0 0
No quadro do simplex, quando uma variável está na base, o encontro da linha com a coluna é 1 e os demais valores da coluna é zero. No quadro anterior, verificamos que isso acontece com as variáveis X3, X4 e X5 que estão na base.
O passo seguinte (regra 6) é a determinação da variável que vai entrar da base. O objetivo do método simplex é colocar na base as variáveis originais do problema (X1 e X2). A regra diz que deve-se escolher na linha de –Z, o valor mais negativo. No exemplo acima o valor mais negativo é –500, que corresponde a variável X2. 
8ª) Em caso de empate na escolha da variável que entrará na base ou que sairá da base, a escolha deverá ser feita de forma arbitrária. Essa escolha tanto poderá levar a um caminho mais curto, como a um caminho mais longo.
 9ª) O valor correspondente a variável que entrará na base, com o que sairá da base, deverá ser igual a 1. Quando isso não ocorrer, é necessário dividir a linha pelo seu próprio valor.
10ª) Os demais valores da coluna que entrará na base, com o que sairá da base, deverão ser iguais a zero. Para zerar esses valores, deve-se utilizar a linha que “entrou na base", com as demais linhas.
11ª) Só chegaremos ao final do problema, quando toda a linha de Z for positiva.
12ª) A resposta do problema encontra-se na coluna b. Portanto, temos que fazer a relação das variáveis da coluna BASE, com a coluna b.
__________________________________________
BASE X1 X2 X3 X4 X5 b
__________________________________________
X3 1 0 1 0 0 3
__________________________________________
X4 0 1 0 1 0 4
__________________________________________
X5 1 2 0 0 1 9
__________________________________________
 -Z -5 -2 0 0 0 0
__________________________________________
- Multiplicar a linha X1 por -1 e somar a linha X5
- Multiplicar a linha X1 por +5 e somar a linha -Z 
BASE X1 X2 X3 X4 X5 b
__________________________________________
X1 1 0 1 0 0 3
__________________________________________
X4 0 1 0 1 0 4
__________________________________________
X5 0 2 -1 0 1 6
__________________________________________
 -Z 0 -2 5 0 0 15
______________________________________
- Multiplicar a linha X1 por -1 e somar a linha X5
- Multiplicar a linha X1 por +5 e somar a linha -Z 
BASE X1 X2 X3 X4 X5 b
__________________________________________
X1 1 0 1 0 0 3
__________________________________________
X4 0 0 1/2 1 0 1
__________________________________________
X2 0 1 -1/2 0 1 3
_______________________________________
 -Z 0 0 4 0 1 21
_________________________________________
- Dividir a linha X5 por 2
- Multiplicar a linha X2 por -1 e somara linha X4
- Multiplicar a linha X2 por +2 e somar a linha -Z
SOLUÇÃO DO PROBLEMA
A regra 12 diz que, a resposta do problema encontra-se na coluna b. Portanto, temos que fazer a relação das variáveis da coluna BASE, com a coluna b. Neste caso, a resposta do problema é: X1 = 3, X2 = 3, X3 = 0 (toda a variável que não está na base é zero) e X4 = 1 (o que corresponde que do recurso quantidade de áreas de milho, haverá uma sobra de 1 área), e X5 = 0. 
O lucro máximo será de R$ 21.000,00.
Exemplo 2
A Esportes Radicais S.A. produz pára-quedas e asas-deltas em duas linhas de montagem. A primeira linha tem 
100 horas semanais disponíveis para a fabricação dos produtos, e a segunda linha tem um limite de 42 horas semanais. Cada um dos produtos requer 10 h de processamento na linha 1, enquanto na linha 2 o pára-quedas requer 3 h e a asa-delta, 7 horas. Sabendo-se que o mercado está disposto a comprar toda a produção da empresa e que o lucro unitário do pára-quedas é de R$ 60,00 e o da asa-delta é de R$ 40,00.
Qual a quantidade que deve ser produzida, para que a empresa tenha um lucro máximo? 
SOLUÇÃO
Variáveis de decisão:
	X1 = Qtd. de pára-quedas 
	X2 = Qtd. de asas-deltas
 Parâmetros:
- Linha 1 e linha 2
Restrições: 
Disponibilidade máxima de cada parâmetro: 
 100 horas na linha 1 e 42 horas na linha 2
Função Objetivo:
- Função objetivo a ser maximizada:
		Zmáx.. = 60 X1 + 40 X2 
Restrições técnicas:
 
Linha 1	10 X1 + 10 X2 100
Linha 2	 3 X1 + 7 X2 42 
- Restrições de não negatividade: X1 0 e X2 0 
 
	As variáveis controladas ou variáveis de decisão são X1 e X2. A função objetivo mede o desempenho do sistema, no caso a capacidade de maximizar o lucro, para cada solução apresentada.
MODELO MATEMÁTICO PRIMAL:
 	10 X1 + 10 X2 100
	 3 X1 + 7 X2 42 
Zmáx.. = 60 X1 + 40 X2 
Com base nas regras 1 a 3 do simplex, vamos transformar as inequações em equações, utilizando as variáveis de folga: 
	10 X1 + 10 X2 + X3 = 100
	 3 X1 + 7 X2 + X4 = 42 
-Zmáx.. = - 60 X1 - 40 X2
5ª) O passo seguinte é a construção do quadro do simplex, que tem a seguinte estrutura:
_____________________________________
BASE X1 X2 X3 X4 b
_____________________________________
X3 10 10 1 0 100
_____________________________________
X4 3 7 0 1 42
_____________________________________
-Z -60 -40 0 0 0
BASE X1 X2 X3 X4 b
_____________________________________
X1 1 1 1/10 0 10
_____________________________________
X4 0 4 -3/10 1 12
_____________________________________
-Z 0 20 6 0 600
_____________________________________
Dividir a linha X3 por 10
Multiplicar a linha X1 por -3 e somar a linha X4
Multiplicar a linha X1 por 60 e somar a linha -Z
Na próxima aula você vai aprender:
- A utilização do Solver para a solução de problemas de Programação Linear.