Aula 05Métodos quantitativos para tomada de decisão

Prévia do material em texto

- -1
MÉTODOS QUANTITATIVOS PARA 
TOMADA DE DECISÃO
PROGRAMAÇÃO LINEAR: MÉTODO 
SIMPLEX
- -2
Olá!
Ao final desta aula, você será capaz de:
- Utilizar o Método Simplex para resolver problemas de Programação Linear.
1 REGRAS DO ALGORITMO DO SIMPLEX
O Algoritmo dos Simplex os 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.
É, portanto, uma ferramenta eficiente, eficaz e 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.
A utilização das 12 regras que você estudará a seguir facilita o entendimento do uso desse algoritmo.
Regra nº 1
O primeiro passo é transformar as inequações em equações. Isto é feito utilizando-se das 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 (-).
Regra nº 2
No caso das restrições do tipo maior e igual (≥), cuja variável de folga assume o sinal negativo (-), é necessária,
também, a utilização das chamadas variáveis artificiais.
- -3
Regra nº 3
As variáveis de folga assumirão os valores crescentes, após as variáveis originais do problema.
Em 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.
Regra nº 4
A função objetiva deverá ser multiplicada por (-1), para que o valor final do quadro do simplex seja positivo.
Regra nº 5
O passo seguinte é a construção do quadro do simplex, que tem a seguinte estrutura:
Regra nº 6
DETERMINAÇÃO DA VARIÁVEL QUE ENTRARÁ NA BASE - escolhe-se na linha de , dentre as variáveis que–Z
tenham sinal negativo, a mais negativa de todas.
Regra nº 7
DETERMINAÇÃO DA VARIÁVEL QUE SAIRÁ DA BASE - dividem-se os valores da coluna b pelos valores da coluna
que entrará na base. Escolhe-se o menor valor da divisão.
Regra nº 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.
Regra nº 9
O valor correspondente à variável que entrará na base, com o que sairá da base (o encontro da linha e coluna),
deverá ser igual a 1.
Quando isso não ocorrer, é necessário dividir a linha pelo seu próprio valor.
Regra nº 10
- -4
Os demais valores da coluna que entrará na base deverão ser iguais a zero. Para zerar esses valores, deve-se
utilizar a linha que “entrou na base", com as demais linhas.
Regra nº 11
Só chegaremos ao final do problema quando toda a linha de Z for positiva.
Regra nº 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.
2 APLICAÇÃO DO ALGORITMO DO SIMPLEX
Vamos utilizar um exemplo para exemplificar o Método do Simplex, partindo do seu modelo matemático
primal.
2 X + X 1 2 ≤ 16
X1 + 2X2 ≤ 11
X1 + 3X2 ≤ 15
Z = 300 X + 500 XMáx. 1 2
Com base na e na do simplex, vamos transformar as inequações em equações, utilizando asRegra 1* Regra 3* 
variáveis de folga.
*Regra 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 (-).
*Regra 3: As variáveis de folga assumirão os valores crescentes, após as variáveis originais do problema. Em 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.
2 X + X + X = 161 2 3
X1 + 2X2 + X = 114
X1 + 3X2 + X = 155
A manda multiplicar a função objetivo por –1.Regra 4*
*Regra 4: A função objetiva deverá ser multiplicada por (-1), para que o valor final do quadro do simplex seja
positivo.
- Z = - 300 X - 500 XMáx. 1 2
- -5
O passo 5 (Regra 5) é a construção do quadro do simplex.
O quadro montado:
No quadro do simplex, quando uma variável está na base, o encontro da linha com a coluna é e os demais1
valores da coluna são . No quadro, verificamos que isso acontece com as variáveis , que estão nazero X3, X4 e X5
base.
O passo seguinte (Regra 6) é a determinação da variável que vai entrar na 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.
Observe o quadro e clique sobre o valor mais negativo da linha -Z.
- -6
No exemplo, o valor mais negativo é que corresponde à variável .–500, X2
A Regra 7 aborda a determinação da variável que sairá da base, para dar lugar à variável que entrará na base. A
escolha sempre deverá ser feita nas variáveis de folga que estão na base.
O menor valor da divisão foi (15 ÷ 3), que corresponde à variável . Portanto, a variável X5 sairá da base para5 X5
dar lugar à variável .X2
Clique aqui para ver como ficará a nova base.
- -7
Como está na base, o encontro da linha com a coluna , tem que ser igual a .X2 X2 X2 1
Para tornar esse valor igual a , teremos que dividir a linha por .1 X2 3
Os demais valores da coluna de terão que ser iguais a zero. Veja como fazê-lo na próxima tela.X2 
Para zerar os demais valores da coluna de , vamos utilizar a linha (já dividida por 3), da maneira explicadaX2 X2
a seguir.
 Etapa 1: Para zerar o valor da linha de , vamos multiplicar a linha por .X3 X2 –1
- -8
Etapa 2: Em seguida, somamos a linha com a linha . X2 X3
Etapa 3:
- -9
Veja como zerar o valor da linha de .X4
Etapa1: Multiplique a linha X2 por –2. 
Etapa 2: Em seguida, some a linha com a linha .X2 X4
- -10
Etapa 3:
Clique aqui para saber como zerar o valor da linha –Z.
Para zerar o valor da linha de -Z, vamos multiplicar a linha X2 por +500 e somar à linha –Z.
Com base nas operações feitas até aqui, teremos este novo quadro do simplex. Observe.
- -11
Enquanto tivermos um valor negativo no quadro do simplex, teremos que construir um novo quadro.
*Base: O procedimento para saber qual a variável que sairá da base está na Regra 7. Dividindo 11 por 5/3,
encontramos 6,6 e dividindo 1 por 1/3, encontramos 3. Portanto, a variável que sairá da base é , para darX4
lugar à variável .X1
*-400/3: Como o valor da coluna de é negativo , a variável deverá entrar na base no lugar de X1 (- 400/3) X1 X3
ou .X4
Como está na base, o encontro da linha com a coluna tem que ser igual a . Para tanto, teremos queX1 X1 X1 1
multiplicar a linha por . Os demais valores da coluna de terão que ser iguais a zero. Para zerar os demaisX1 3 X1 
valores da coluna de , vamos utilizar a linha (que já foi multiplicada por 3), da maneira descrita a seguir.X1 X1 
Veja.
- -12
*X : Para zerar o valor da linha de , vamos multiplicar a linha por e somar à linha .
1
X3 X1 - 5/3 X3
*X : Para zerar o valor da linha de , vamos multiplicar a linha por e somar à linha .
2
X2 X1 - 1/3 X2
*-Z: Para zerar o valor da linha de , vamos multiplicar a linha por e somar à linha .-Z X1 + 400/3 - Z
Como o valor da coluna de na linha de é negativa , a variável vai entrar na base no lugar de , poisX5 - Z (-1) X5 X3
é a única variável de folga na base. Como está na base, o encontro da linha com a coluna , tem que serX5 X5 X5
igual a 1, para tanto, teremos que dividir a linha por . Os demais valores da coluna de terão que ser iguaisX5 3 X5 
a zero. Para zerar os demais valores da coluna de , vamos utilizar a linha (que já foi dividida por 3), daX5 X5 
maneira descrita a seguir. Veja.
- -13
*X1: Para zerar o valor da linha de X1, vamos multiplicar a linha X5 por 2 e somar a linha X1.
*X2: Para zeraro valor da linha de X2, vamos multiplicar a linha X5 por -1 e somar à linha X2.
*-Z: Para zerar o valor da linha de -Z, vamos somar a linha X5 à linha -Z.
Clique aqui para ver como fica o quadro Simplex.
Com base nas operações realizadas até aqui, temos o novo quadro do simplex.
A Regra 12 diz que a resposta do problema encontra-se na . Portanto, temos que fazer a relação dascoluna b
variáveis da coluna , com a .BASE coluna b
Neste caso, a resposta do problema é:
- -14
X1 = 7, X2 = 2, e . X3 e X4 = 0 X5 = 2
* X3 e X4 = 0: Toda a variável que não está na base é zero.
* X5 = 2: Isto significa que haverá uma sobra de 2 kg do recurso chumbo, conforme demonstrado na aula 04, em
que a restrição era ≤ 15 kg e o resultado final foi igual a 13 kg de chumbo.
O lucro máximo será de R$ 3.100,00.
CONCLUSÃO
Nesta aula, você:
• 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;
• O primeiro passo é transformar as inequações em equações;
• As variáveis de folga assumirão os valores crescentes, após as variáveis originais do problema;
• A função objetiva deverá ser multiplicada por (-1), para que o valor final do quadro do simplex seja 
positivo;
• Na coluna base do primeiro quadro do simplex, ficam as variáveis de folga, na coluna b, o valor das 
restrições de cada inequação e, nas demais colunas, os coeficientes das variáveis de cada inequação;
• Para 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;
• Para determinação da variável que sairá da base, dividem-se os valores da coluna b pelos valores da 
coluna que entrará na base e escolhe-se o menor valor da divisão; a escolha sempre deverá ser feita nas 
variáveis de folga que estão na base;
• 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;
• O valor correspondente à 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;
• 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;
• Só chegaremos ao final do problema quando toda a linha de Z for positiva;
• 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.
•
•
•
•
•
•
•
•
•
•
•
•