Aula 05 (2)

Prévia do material em texto

MÉTODOS QUANTITATIVOS – AULA 5 (SEMESTRAL) 
ANTONIO VIANA MATIAS
Rio de Janeiro, 2011
1
 AULA 5 - PROGRAMAÇÃO LINEAR: MÉTODO SIMPLEX
AULA 05 – PROGRAMAÇÃO LINEAR: MÉTODO SIMPLEX
Nesta aula serão abordados os seguintes assuntos:
- 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.
	
PROGRAMAÇÃO LINEAR: MÉTODO SIMPLEX 
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.
	
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.
	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 vaiá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
	 X4
	 X5
__________________________________________________
 -Z
__________________________________________________
		
	
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 VAIÁVEL QUE SAIRÁ DA BASE: dividi-se os valores da coluna b, pelos valores da coluna que entrará na base. Escolhe-se o menor valor da divisão.
	
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.
	SOLUÇÃO
	
	
Exemplo 2
A Esportes Radicais S.A. produz pára-quedas e asas-delta 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?
	
Variáveis de decisão:
	X1 = Qtd. de pára-quedas
	X2 = Qtd. de asa-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.
	
SOLUÇÃO
Nesta aula você aprendeu:
	- A utilização do método Simplex para a solução de problemas de Programação Linear.