Resumo - revisão - para a prova de Pesquisa Operacional
Material desenvolvido com base em anotações das Aulas de Pesquisa Operacional da UCL (2018/1).
Lembre-se de deixar seu comentário, caso seja necessário realizar alguma correção ou melhoria no material de revisão. Obrigado. Bons estudos.
Lucas T R Freitas
lucastrfreitas@gmail.com
Casos estudados para aplicação do método da matriz Simplex ("Normal", "Primal e Dual", "Restrições mistas", "Soluções Múltiplas"):
Caso normal
- Características:
*Todas as restrições estão com menor ou igual ("≤")
*O problema é de maximização
Procedimentos
Incluir as variáveis de sobra transformando as restrições de menor ou igual para igual.
- Exemplo: 2 . X
1 + 1 . X
2 ≤ 1000 passa a ser 2 . X
1 + 1 . X
2 + S
1 = 1000 (a variável de sobra preenche o espaço até completar 1000 unidades)
- cada restrição terá uma variável de sobra correspondente (se for inequação)
Acertar a disposição da função objetivo para o modo de inserção na matriz Simplex.
- Exemplo: 45 . X
1 + 30 . X
2 = f passa a ser escrito - 45 . X
1 - 30 . X
2 + f = 0
Preencher a matriz Simplex.
Primeiro coloca-se cada restrição. Na última linha da matriz coloca-se a função objetivo reescrita.
- Exemplo
Matriz A
linha 1 - Restrição 1
linha 2 - Restrição 2
...
última linha - função objetivo (FO)
Pivotar a Matriz
- Olhar na última linha da matriz a entrada mais negativa. Ela será a indicadora da coluna pivô.
- Dividir o último número da direita de cada linha das restrições pelo número da coluna pivô. O menor número encontrado indicará a linha em que a entrada pivô está.
- Deverá ser construída uma nova matriz através da pivotagem. O número da entrada entrada pivô deverá ser transformado em "1" através de uma operação de divisão ou de multiplicação. As demais "entradas" da coluna pivô deverão ser transformadas em "0" a partir do número "1" obtido da entrada pivô anterior.
Exemplo de pivotagem
Matriz A
X1
|
X2
|
S1
|
S2
|
S3
|
S4
|
f
|
|
escolha da entrada pivô
|
2
|
1
|
1
|
0
|
0
|
0
| 0 |
1000
|
1000 / 2 = 500
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
800
|
800 / 1 = 800
|
1*
|
0
|
0
|
0
|
1
|
0
|
0
|
400
|
400 / 1 = 400*
|
0
|
1
|
0
|
0
|
0
|
1
|
0
|
700
|
700 / 0 = não existe
|
-45
|
-30
|
0
|
0
|
0
|
0
|
1
|
0
|
|
Escolhe-se primeiramente a coluna pivô, a partir da última linha que deverá ter o número mais negativo da linha. Deu -45 na Matriz A.
Depois calcula-se o menor coeficiente positivo dividindo-se a última linha da direita pela coluna pivô. Deu 400 na Matriz A.
Daí encontramos a coluna pivô e a linha pivô. E pode-se começar a pivotagem.
Para construirmos a matriz B seguiremos alguns passos.
Primeiro deve-se fazer a entrada pivô igualar a "1", caso ela já não seja (por meio de operações de multiplicação e divisão). Como na Matriz A a entrada pivô já é "1", a linha dela pode permanecer como está.
A partir da nova entrada pivô, deve-se zerar os demais números da coluna pivô.
Matriz B
cálculo realizado
|
|
|
|
|
|
|
|
|
escolha da nova entrada pivô
|
R1' = -2 . R3 + R1
|
|
|
|
|
|
|
|
|
|
R2' = -1 . R3 + R2
|
|
|
|
|
|
|
|
|
|
linha pivô permanece igual
|
|
|
|
|
|
|
|
|
|
R4 já era zero: permanece
|
|
|
|
|
|
|
|
|
|
R5' = 45 . R3 + R5
|
|
|
|
|
|
|
|
|
|
Na matriz B verifica-se que a menor entrada negativa na última linha é o "-30". Daí encontramos a nova coluna pivô.
Calculando-se o coeficiente a partir da última linha da direita, encontramos que o menor coeficiente positivo é o "200". Daí encontramos a nova linha pivô.
Assim a nova entrada pivô é "1". Como ela já é igual a 1, a nova linha pivô permanecerá igual na Matriz C.
Matriz C
cálculo realizado
|
|
|
|
|
|
|
|
|
escolha da nova entrada pivô
|
linha pivô permanece igual
|
|
|
|
|
|
|
|
|
|
R2'' = -1 . R1' + R2'
|
|
|
|
|
|
|
|
|
|
R3 permanece igual
|
|
|
|
|
|
|
|
|
|
R4' = -1 . R1' + R4
|
|
|
|
|
|
|
|
|
|
R5'' = 30 . R1' + R5'
|
|
|
|
|
|
|
|
|
|
Como ainda resta um número negativo na última linha, deve-se novamente realizar o procedimento de pivotagem.
A coluna pivô será a que tem o número mais negativo na última linha: "-15".
A partir do menor coeficiente positivo obtido pela divisão da última coluna da direita pela coluna pivô ("200"), encontra-se a linha pivô. Daí encontra-se a entrada pivô "1".
Como a entrada pivô já é "1", basta repetir a linha pivô e zerar as demais entradas da coluna pivô na pivotagem.
Matriz D
cálculo realizado
|
|
|
|
|
|
|
|
|
|
R2''' = 2 . R2'' + R1'
|
|
|
|
|
|
|
|
|
|
linha pivô permanece igual
|
|
|
|
|
|
|
|
|
|
R3''' = (-1) . R2'' + R3
|
|
|
|
|
|
|
|
|
|
R4'' = (-1) . R2'' + R4'
|
|
|
|
|
|
|
|
|
|
R5''' = 15 . R2'' + R5''
|
|
|
|
|
|
|
|
|
|
Como não há mais valores negativos na última linha, e nem na última coluna da direita, a pivotagem está encerrada.
A Matriz D informa o seguinte:
- X1 = 200 unidades do produto A
- X2 = 600 unidades do produto B
- Não há sobras dos recursos da restrição 1 e da restrição 2.
- Há sobra de 200 unidades do recurso da restrição 3.
- Há sobra de 100 unidades do recurso da restrição 4.
- A função objetivo é maximizada em 27000 reais.
Caso Primal e Dual
- Características:
*Todas as restrições estão com maior ou igual ("≥")
*O problema é de minimização
*A matriz transposta (Dual, obtida da Primal) poderá possibilitar a resolução do problema pelo método Simplex, transformando o problema para um caso de maximização.
Exemplo:
Minimizar g = 18.y
1 + 12.y
2
Sujeito a:
- 2 . y1 + y2 ≥ 8
- 6 . y1 + 6 . y2 ≥ 36
Para construir a matriz PRIMAL vamos inserir primeiro as restrições, e na última linha a função objetivo.
Matriz PRIMAL A
y1
|
y2
|
__
|
2
|
1
|
8
|
6
|
6
|
36
|
18
|
12
|
g
|
Realizando-se a transposição obtém a transposta, a Matriz DUAL A
T. Assim, de minimizar g, passamos a maximizar f.
Matriz DUAL A
T
Seguindo as linhas da Matriz DUAL A
T, obtém-se as restrições para maximizar f. Nota-se que agora as restrições são escritas com "≤".
Restrições da Matriz Dual:
2 . y
1 + 6. y
2 ≤ 18
1 . y
1 + 6 . y
2 ≤ 12
Função objetivo da Matriz Dual:
8 . y
1 + 36 . y
2 = f
Como a Matriz Dual passou a se tratar de uma função de maximização, precisamos encontrar o valor de f. Procedemos então à adequação das restrições com inserção das variáveis de sobra para a montagem da matriz Simplex.
Restrição 1:
2 . y
1 + 6. y
2 + S
1 = 18
Restrição 2:
1 . y
1 + 6 . y
2 + S
2 = 12
Adequamos também a função objetivo para:
- 8 . y1 - 36 . y2 + f = 0
Agora podemos montar a matriz Simplex para tentar solucionar o problema.
Matriz A
Y1
|
Y2
|
S1
|
S2
|
f
|
|
escolha da entrada pivô
|
2
|
6
|
1
|
0
| 0 |
18
|
18 / 6 = 3
|
1
|
6*
|
0
|
1
| 0 |
12
|
12 / 6 = 2
|
-8
|
-36
|
0
|
0
| 1 |
0
|
|
Encontramos a coluna pivô a partir do número mais negativo da última linha ("-36").
Dividindo-se os números da última coluna da direita pelos números da coluna pivô, encontra-se a linha pivô, indicada pelo menor coeficiente positivo obtido. Daí a entrada pivô será "6".
Iniciamos então a pivotagem da Matriz A, obtendo a Matriz B.
Primeiro é preciso tornar a entrada pivô igual a "1". Depois é preciso zerar os demais números da coluna pivô.
Matriz B
cálculo realizado
|
Y1
|
Y2
|
S1
|
S2
|
f
|
|
escolha da entrada pivô
|
| R1' = (-6) . R2 + R1 |
1
|
0
|
1
|
-1
| 0 |
6
|
6 / 1 = 6
|
R2' = 1/6 . R2
|
1/6
|
1
|
0
|
1/6
| 0 |
2
|
2 / (1/6) = 12
|
| R3' = (36) . R2' + R3 |
-2
|
0
|
0
|
6
| 1 |
72
|
|
A partir do número mais negativo da última linha da matriz B ("-2") encontra-se a nova coluna pivô. Dividindo-se os valores da última coluna da direita pelos da coluna pivô, o menor coeficiente positivo indicará a linha pivô ("6").
Como a nova entrada pivô já é igual a "1", basta repetí-la e zerar os demais números da coluna pivô.
Matriz C
cálculo realizado
|
Y1
|
Y2
|
S1
|
S2
|
f
|
|
pivotagem encerrada
|
| R1' |
1
|
0
|
1
|
-1
| 0 |
6
|
-
|
R2'' = (-1/6) . R1' + R2'
|
0
|
1
|
-1/6
|
1/3
| 0 |
1
|
-
|
| R3'' = (2) . R1' + R3' |
0
|
0
|
2
|
4
| 1 |
84
|
|
Como não há mais números negativos na última linha nem na última coluna da matriz C, a pivotagem está encerrada.
A matriz C informa o seguinte, lembrando que estamos lidando com um caso de matriz Primal e Dual:
- Os valores abaixo das variáveis de sobra indicarão os valores das variáveis principais:
Y1 = 2
Y2 = 4
f é maximizada em 84, o que significa que g é minimizada em 84.
Restrições mistas
- Características:
*As restrições estão com menor ou igual ("≤") e com maior ou igual ("≥"), ou seja, estão misturadas (mistas)
*O problema pode ser de maximização ou de minimização. Se for de maximização, busca-se encontrar o valor de "f". Se for de minimização, busca-se encontrar o valor de "-f".
Explicação: como o método Simplex maximiza, para encontrarmos o valor de uma minimização (no caso de restrições mistas), iremos maximizar o valor de "-f". Como resultado final, poderemos obter a maximização de "-f", que nos possibilitará encontrar o valor desejado de "f".
Exemplo:
Minimizar f = 3.X + 4.Y
Sujeito a:
X + Y ≥ 20
X + 2.Y ≥ 25
-5.X + Y ≤ 4
Como se trata de um problema de minimização com restrições mistas, deveremos encontrar o valor maximizado de "-f" na matriz Simplex, para depois encontrarmos o valor de "f".
Assim:
3.X + 4.Y - f = 0
As restrições precisam ser passadas para o modo de maximização, que é o modo em que a matriz Simplex trabalha:
Restrição 1 (ajustada):
-X - Y ≤ -20
Restrição 2 (ajustada):
-X - 2 . Y ≤ -25
Restrição 3 (mantida):
-5 . X + Y ≤ 4
Agora, com as restrições ajustadas, inserimos as variáveis de folga, uma para cada restrição:
Restrição 1:
-X - Y + S
1 = -20
Restrição 2:
-X - 2 . Y + S
2 = -25
Restrição 3:
-5 . X + Y + S
3 = 4
Agora está tudo preparado para tentar resolver o problema pela matriz Simplex para maximização. Para montar a matriz Simplex, primeiro entramos com as restrições, e na última linha inserimos a função objetivo.
Matriz A
X1
|
Y
|
S1
|
S2
|
S3
|
-f
|
|
escolha da entrada pivô
|
-1
|
-1
|
1
|
0
|
0
| 0 |
-20
|
linha pivô escolhida
|
-1
|
-2
|
0
|
1
|
0
|
0
|
-25
|
-
|
-5
|
1
|
0
|
0
|
1
|
0
|
4
|
-
|
3
|
4
|
0
|
0
|
0
|
1
|
0
|
|
Trata-se de um caso especial de pivotagem. Como há números negativos na última coluna da direita, começamos a pivotagem olhando por ela. Vemos que há dois números negativos ("-20" e "-25"). Nesse caso, poderemos escolher qualquer um deles para definir qual será a linha pivô. Vamos escolher o "-20". Falta agora decidir qual será a coluna pivô, que deverá ser escolhida a partir de números negativos na linha pivô. Verificamos que há dois números negativos na linha, todos os dois iguais a "-1". A escolha entre eles é opcional e define qual será a coluna pivô, que será a coluna do número escolhido. Vamos escolher o primeiro para dar início à pivotagem.
Primeiro, tornamos igual a "1" a entrada pivô. Depois zeramos os demais números da coluna pivô.
Matriz B
cálculo realizado
|
X1
|
Y
|
S1
|
S2
|
S3
|
-f
|
|
escolha da entrada pivô
|
| R1' = (-1) . R1 |
1
|
1
|
-1
|
0
|
0
| 0 |
20
|
|
| R2' = R1' + R2 |
0
|
-1
|
-1
|
1
|
0
|
0
|
-5
|
nova linha pivô
|
| R3' = 5 . R1' + R3 |
0
|
6
|
-5
|
0
|
1
|
0
|
104
|
|
| R4' = (-3) . R1' + R4 |
0
|
1
|
3
|
0
|
0
|
1
|
-60
|
|
Olhamos então novamente para a última coluna da direita da Matriz A e observamos que existe um número negativo ("-5") na coluna. É importante observar que não consideramos a linha da função objetivo para a análise da última coluna da direita da matriz Simplex.
Daí, o "-5" indica a nova linha pivô. Precisamos agora encontrar a coluna pivô, e temos duas opções, todas iguais a "-1". Vamos escolher a primeira novamente para iniciar a pivotagem.
Devemos realizar o procedimento padrão de tornar a entrada pivô igual a "1" e zerar os demais números da coluna pivô.
Matriz C
cálculo realizado
|
X1
|
Y
|
S1
|
S2
|
S3
|
-f
|
|
pivotagem encerrada
|
| R1'' = (-1) . R2'' + R1' |
1
|
0
|
-2
|
1
|
0
| 0 |
15
|
|
| R2'' = (-1) . R2' |
0
|
1
|
1
|
-1
|
0
|
0
|
5
|
|
| R3'' = (-6) . R2'' + R3' |
0
|
0
|
-11
|
6
|
1
|
0
|
74
|
|
| R4'' = (-1) . R2'' + R4' |
0
|
0
|
2
|
1
|
0
|
1
|
-65
|
|
Como não há mais números negativos na última coluna da direita da Matriz C (excetuando-se a linha da função objetivo), a pivotagem está encerrada.
A Matriz C informa o seguinte:
X1 = 15 unidades
Y = 5 unidades
Há sobra de 74 unidades do recurso da restrição 3
"-f" é maximizada em "-65", logo f é minimizada em 65
Soluções múltiplas
- Características:
*Todas as restrições estão com menor ou igual ("≤")
*O problema é de maximização
*O coeficiente angular da função objetivo é igual ao coeficiente angular de uma ou mais de uma das restrições.
Exemplo:
Maximizar Z = 2 .
X1 +
X2
Sujeito a:
X1 + (1/2) . X2 ≤ 16
X1 +
X2 ≤ 24
Vamos calcular os coeficientes angulares para ver se existe igualdade entre eles.
- Função objetivo: m = -a/b = -2/1 = -2
- Restrição 1: m = -a/b = -1/(1/2) = -2
- Restrição 2: m = -a/b = -1/1 = -1
Logo, é possível observar que o coeficiente angular da função objetivo é igual ao coeficiente angular da restrição 1. Assim, pode ser que existam múltiplas soluções para o problema.
Vamos prosseguir com a montagem da matriz Simplex.
De Z = 2 .
X1 +
X2 obtemos -2 .
X1 -
X2 + f = 0
Inserindo as variáveis de sobra nas restrições:
Restrição 1:
X1 + (1/2) . X2 + S1 = 16
Restrição 2:
X1 +
X2 +
S2 = 24
Para montar a matriz Simplex, primeiro inserimos as restrições, e depois a função objetivo.
Matriz A
X1
|
X2
|
S1
|
S2
|
f
|
|
escolha da entrada pivô
|
1
|
1/2
|
1
|
0
| 0 |
16
|
16 / 1 = 16
|
1
|
1
|
0
|
1
| 0 |
24
|
24 / 1 = 24
|
-2
|
-1
|
0
|
0
| 1 |
0
|
|
Olhando a linha da função objetivo, observa-se que o menor número negativo é o "-2". Daí obtém-se a coluna pivô.
Dividindo-se os números da última coluna da direita pelos números da coluna pivô, o menor coeficiente positivo encontrado indicará a linha pivô ("16").
Agora podemos prosseguir com a pivotagem. Como a entrada pivô já é igual a "1", ela não precisará de ajustes. Basta zerar os demais números da coluna pivô.
Matriz B
cálculo realizado
|
X1
|
X2
|
S1
|
S2
|
f
|
|
escolha da entrada pivô
|
| linha pivô permanece igual |
1
|
1/2
|
1
|
0
| 0 |
16
|
16 / (1/2) = 32
|
R2' = (-1) . R1 + R2
|
0
|
1/2*
|
-1
|
1
| 0 |
8
|
8 / (1/2) = 16
|
| R3' = (2) . R1' + R3 |
0
|
0
|
2
|
0
| 1 |
32
|
|
Como não há mais nenhum indicador negativo na última linha, isso indica que o valor ótimo de f foi encontrado.
A matriz indica o seguinte:
X1 = 16 unidades.
X2 = 0 unidades.
Há sobra de 8 unidades do recurso da restrição 2.
f = 32.
Um detalhe importante é que se uma variável não básica possuir um indicador nulo na última linha (caso de
X2), a coluna com o indicador nulo poderá ser utilizada como coluna pivô para encontrar uma segunda solução.
Assim, vamos prosseguir com a pivotagem
Matriz C
cálculo realizado
|
X1
|
X2
|
S1
|
S2
|
f
|
|
pivotagem encerrada
|
| R1' = (-1/2) . R2'' + R1 |
1
|
0
|
2
|
-1
| 0 |
8
|
|
R2'' = (2) . R2'
|
0
|
1
|
-2
|
2
| 0 |
16
|
|
| linha permanece igual |
0
|
0
|
2
|
0
| 1 |
32
|
|
Da matriz C pode-se entender o seguinte:
X1 = 8 unidades.
X2 = 16 unidades.
Não há sobras de recursos das restrições.
f continua maximizado em 32.
Testando os valores obtidos no método Simplex na Função Objetivo:
Z = 2 .
X1 +
X2
(16, 0): Z = 2 . 16 + 0 = 32
(8, 16): Z = 2 . 8 + 16 = 16 + 16 = 32
Assim, o método Simplex se mostrou capaz de solucionar problemas com soluções múltiplas.
Lucas Tiago Rodrigues de Freitas
-- // -- Definite Chief Aim: "Viver tecnologicamente, cientificamente, trabalhando em parceria com Deus, melhorando o meio ambiente e gerando prosperidade."
