MQ Aula_05

Prévia do material em texto

MÉTODOS QUANTITATIVOS – AULA 5 (SEMESTRAL) 
ANTONIO VIANA MATIAS
Rio de Janeiro, 2011
 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.