Pesquisa Operacional - Big M

Prévia do material em texto

1
Pesquisa Operacional
BIG M
José Agostinho Baitello
Modelo de Programação Linear - Forma Padrão
Max Z = c1x1 + c2x2 + ........ + cnxn
sa
a11x1 + a12x2 + .......+ a1nxn  b1
a21x1 + a22x2 + .......+ a2nxn  b2
.
am1x1 + am2x2 +.....+ amnxn  bm
xij  0 i=1...n; j=1...m
Função Objetivo de 
Maximização
Restrições TODAS devem ser 
do tipo: 
≤ (menor ou igual)
TODOS os RHS (elementos 
do lado direito das 
inequações) devem ser 
POSITIVOS
TODAS as variáveis devem 
ser não negativas 
≥ (maior ou igual a zero)
1
2
2
3
Como resolver problemas de MINIMIZAÇÃO
Exemplo:
Min Z = -2x1 + x2 - x3
sa
3x1 + x2 + x3 ≤ 60
x1 - x2 + 2x3 ≤ 10
x1 + x2 - x3 ≤ 20
x1; x2; x3 ≥ 0 
Transformamos o Problema de Minimização 
em uma Maximização
Min Z = -2x1 + x2 - x3
sa
3x1 + x2 + x3 ≤ 60 
x1 - x2 + 2x3 ≤ 10
x1 + x2 - x3 ≤ 20
x1, x2, x3≥0
Novo problema de MAXIMIZAÇÃO agora na forma padrão:
Max (- Z) = 2x1 - x2 + x3
sa
3x1 + x2 + x3 ≤ 60 
x1 - x2 + 2x3 ≤ 10
x1 + x2 - x3 ≤ 20
x1, x2, x3≥0
3
4
3
Transformando o Modelo para a Forma Canônica e 
resolvendo pelo Algoritmo Simplex
Max(-Z)= 2x1 - x2 + x3
sa
3x1 + x2 + x3 + x4 = 60 
x1 - x2 + 2x3 + x5 = 10
x1 + x2 - x3 + x6 = 20
x1; x2; x3; x4; x5; x6 ≥ 0
Ao final do problema o valor da função objetivo encontrado sera o –Z, 
necessitando que se multiplique o seu valor por (-1) para obter o Z do 
modelo de minimização 
Quando o modelo possui 
outros tipos de restrições...
Restrições do tipo ≥
OU
Restrições do tipo =
5
6
4
Método Big M – Exemplo 1
Max Z = 6x1 – x2
sa:
Restr1) 4x1 + x2 ≤ 21
Restr2) 2x1 + 3x2 ≥ 13
Restr3) x1 - x2 = -1
x1≥ 0; x2≥ 0
Este modelo possui as seguintes não conformidades com o problema padrão:
• Restr3 com RHS negativo
• Restr2 do tipo ≥
• Restr3 do tipo =
7
8
5
Método Big M – Exemplo 1
Max Z = 6x1 – x2
sa:
Restr1) 4x1 + x2 ≤ 21
Restr2) 2x1 + 3x2 ≥ 13
Restr3) x1 - x2 = -1
x1≥ 0; x2≥ 0
Multiplicar por 
(-1) para que o 
RHS fique 
positivo
Método Big M – Exemplo 1
Max Z = 6x1 – x2
sa:
Restr1) 4x1 + x2 ≤ 21
Restr2) 2x1 + 3x2 ≥ 13
Restr3) - x1 + x2 = 1
x1≥ 0; x2≥ 0
9
10
6
Método Big M – Exemplo 1
Ao colocar o modelo na forma canônica constatamos ...
Max Z = 6x1 – x2 + 0x3 + 0x4
sa:
Restr1) 4x1 + x2 + x3 = 21
Restr2) 2x1 + 3x2 - x4 =13
Restr3) - x1 + x2 = 1
x1≥ 0; x2≥ 0
Para obter igualdade 
precisamos subtrair 
excessos (surplus)
Não conseguimos formar uma base inicial do tipo:
+ x3
+ x4
+ x5
Devemos recorrer à variáveis artificiais...
Método Big M – Exemplo 1
Modelo na forma canônica
Max Z = 6x1 – x2 + 0x3 + 0x4 - Mxa1 - Mxa2
sa:
Restr1) 4x1 + x2 + x3 = 21
Restr2) 2x1 + 3x2 - x4 + xa1 = 13
Restr3) - x1 + x2 + xa2 = 1
x1≥ 0; x2≥ 0; x3≥ 0; x4≥ 0; xa1≥ 0; xa2≥ 0
+ x3
+ xa1
+ xa2
Obtivemos assim a seguinte base:
11
12
7
Inclusão de Variáveis Artificiais
Mas devemos fazer mais alguma coisa no modelo para assegurar que as 
variáveis artificiais Xai, que não tem nenhum significado físico no modelo, 
cheguem ao final do SIMPLEX com o valor zero.
Para isso alteramos a função objetivo, fazendo com que as variáveis 
artificiais participem da mesma com um prejuízo (coeficiente M) tão 
grande que sempre supera qualquer outro número quando comparado a 
ele (na prática , pelo menos umas 10 vezes maior do que os demais 
coeficientes) e de forma a atuarem contra a maximização caso tenham um 
valor diferente de zero.
A Função objetivo ficará:
Max Z = 6x1 – x2 + 0x3 + 0x4 - Mxa1- Mxa2
Fase Inicial – Preparação para o Simplex
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Z 0 -6 1 0 0 M M
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Z 0 -6 1 0 0 M M
xa1*(-M)
xa2*(-M)
Nova Z 0 0 0
x(-M)
x(-M)
13
14
8
Fase Inicial – Preparação para o Simplex
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Z 0 -6 1 0 0 M M
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Z 0 -6 1 0 0 M M
xa1*(-M) -13M -2M -3M 0 M -M 0
xa2*(-M) -M M -M 0 0 0 -M
Nova Z -14M -6-M 1-4M 0 M 0 0
x(-M)
x(-M)
Método Big M – Exemplo 1
Aplicando o Simplex 1ª Interação
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Nova Z -14M -6-M 1-4M 0 M 0 0
Base RHS x1 x2 x3 x4 xa1 xa2
x3 0 1 0
xa1 0 0 1
x2 1 -1 1 0 0 0 1
Nova Z 0 0 0
Linha do pivô 
dividida pelo 
valor do pivô
Cálculo dos demais elementos 
pela regra do retângulo
Nova Base
21/1 = 21
Quociente
1/1 = 1
13/3 = 4,3
15
16
9
Método Big M – Exemplo 1
Aplicando o Simplex 2ª Interação
Base RHS x1 x2 x3 x4 xa1 xa2
x3 20 5 0 1 0 0 -1
xa1 10 5 0 0 -1 1 -3
x2 1 -1 1 0 0 0 1
Z -10M-1 -5-5M 0 0 M 0 -1+4M
Base RHS x1 x2 X3 x4 xa1
x3 0 0 1
x1 2 1 0 0 -1/5 1/5
x2 0 1 0 0
Z 0 0 0 0
Linha do pivô 
dividida pelo 
valor do pivô
Saiu da base e não deve voltar
DESCONSIDERAR NAS 
INTERAÇÕES POSTERIORES
Nova Base
20/5 = 4
Quociente
10/5 = 2
Método Big M – Exemplo 1
Aplicando o Simplex 3ª Interação
Base RHS x1 x2 x3 x4 xa1
x3 10 0 0 1 1 -1
X1 2 1 0 0 -1/5 1/5
X2 3 0 1 0 -1/5 1/5
Z 9 0 0 0 -1 1+M
Base RHS x1 x2 x3 x4
X4 10 0 0 1 1
X1 1 0 0
X2 0 1 0
Z 0 0 0
RETORNAMOS AO PROBLEMA ORIGINAL . . . sem as variáveis artificiais
Linha do pivô 
dividida pelo 
valor do pivô
Nova Base
Quociente
10/1 = 10
17
18
10
Método Big M – Exemplo 1
Aplicando o Simplex Solução Final
Base RHS x1 x2 x3 x4
X4 10 0 0 1 1
X1 4 1 0 1/5 0
X2 5 0 1 1/5 0
Z 19 0 0 1 0
Zmax = 19
X1 = 4
X2 = 5
X3 = 0
X4 = 10
Todos os coeficientes da função objetivo são positivos:
SOLUÇÃO ÓTIMA
Método Big M – Exemplo 1
Solução pelo LINDO
Não há 
necessidade de 
fazer qualquer 
preparação prévia, 
o LINDO faz isso 
internamente
19
20
11
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
Nova Z -14M -6-M 1-4M 0 M 0 0
Método Big M – Exemplo 1 
Adequação da função objetivo Fase INICIAL
Base RHS x1 x2 x3 x4 xa1 xa2
x3 21 4 1 1 0 0 0
xa1 13 2 3 0 -1 1 0
xa2 1 -1 1 0 0 0 1
z 0 -6 1 0 0 M M
xa1*(-M) -13M -2M -3M 0 M -M 0
xa2*(-M) -M M -M 0 0 0 -M
Nova Z -14M -6-M 1-4M 0 M 0 0
Linha Xa1
Multiplicada por 
(-M)
Linha xa2
Multiplicada por 
(-M)
A partir desta tabela aplica-se Algorítmo Simplex até chegar à 
solução ótima
Método Big M – Exemplo 1
Aplicando o Simplex
Base RHS x1 x2 x3 x4 xa1 xa2
x3 20 5 0 1 0 0 -1
xa1 10 5 0 0 -1 1 -3
x2 1 -1 1 0 0 0 1
z -10M-1 -5-5M 0 0 M 0 -1+4M
Base RHS x1 x2 x3 x4 xa1 xa2
x3 10 0 0 1 1 -1
X1 2 1 0 0 -1/5 1/5
X2 3 0 1 0 -1/5 1/5
z 9 0 0 0 -1 1+M
Base RHS x1 x2 x3 x4 xa1 xa2
X4 10 0 0 1 1
X1 4 1 0 1/5 0
X2 5 0 1 1/5 0
z 19 0 0 1 0
Solução Ótima: Z=19 ; x1=4; x2=5; x3=0; x4=10; xa1=0; xa2=0
21
22
12
Método Big M – Exemplo 1 
Usando o SW Didatico IOR Tutorial 
IOR Tutorial - Primeira tabela
Linha do Pivô 
dividida pelo valor 
do pivô
Transformação em 
vetor unitário
Novo componente 
da base
Nova Tabela
A solução é ótima?
23
24
13
IOR Tutorial - Segunda tabela
Linha do Pivô 
dividida pelo valor 
do pivô
Transformação em 
vetor unitário
Novo componente 
da base
Nova Tabela
A solução é ótima?
IOR Tutorial - Terceira Tabela
Linha do Pivô 
dividida pelo valor 
do pivô
Transformação em 
vetor unitário
Novo componente 
da base
Nova Tabela
A solução é ótima? Y
25
26
14
IOR Tutorial - Relatório
Linear Programming Model: 
 Number of Decision Variables: 2 
 Number of Functional Constraints: 3 
 Max Z = 6 X1 - 2 X2 
 subject to 
 1) 4 X1 + 1 X2 <= 21 
 2) 2 X1 + 3 X2 >= 13 
 3) 1 X1 - 1 X2 = -1 
 and 
 X1 >= 0, X2 >= 0. 
 
 Solve Interactively by the Simplex Method: 
 Bas|Eq| Coefficient of | Right 
 Var|No| Z|X1 X2 X3 X4 X5 X6 | side 
 ___|__|__|_____________________________________|______ 
 | | | -1M -4M 1M | -14M 
 Z | 0| 1|- 6 + 2 0 + 0 0 0 | 0 
 X3| 1| 0| 4 1 1 0 0 0 | 21 
 X5| 2| 0| 2 3 0 -1 1 0 | 13 
 X6| 3| 0| -1 1* 0 0 0 1 | 1 
 
 Bas|Eq| Coefficient of | Right 
 Var|No| Z| X1 X2 X3 X4 X5 X6 | side 
 ___|__|__|_____________________________________|______ 
 | | | -5M 1M 4M | -10M 
 Z | 0| 1|- 4 0 0 + 0 0 - 2 | -2 
 X3| 1| 0| 5 0 1 0 0 -1 | 20 
 X5| 2| 0| 5* 0 0 -1 1 -3 | 10 
 X2| 3| 0| -1 1 0 0 0 1 | 1 
 
 Bas|Eq| Coefficient of | Right 
 Var|No| Z| X1 X2 X3 X4 X5 X6 | side 
 ___|__|__|_____________________________________|______ 
 | | | 1M 1M | 
 Z | 0| 1| 0 0 0 -0,8 + 0,8 - 4,4 | 6 
 X3| 1| 0| 0 0 1 1* -1 2 | 10 
 X1| 2| 0| 1 0 0 -0,2 0,2 -0,6 | 2 
 X2| 3| 0| 0 1 0 -0,2 0,2 0,4 | 3 
 
 Bas|Eq| Coefficient of | Right 
 Var|No| Z| X1 X2 X3 X4 X5 X6 | side 
 ___|__|__|_____________________________________|______ 
 | | | 1M 1M | 
 Z | 0| 1| 0 0 0,8 0 + 0 - 2,8 | 14 
 X4| 1| 0| 0 0 1 1 -1 2 | 10 
 X1| 2| 0| 1 0 0,2 0 0 -0,2 | 4 
 X2| 3| 0| 0 1 0,2 0 0 0,8 | 5 
 
Impressão de todas 
as tabelas em um 
arquivo no formato 
texto e pode ser 
lido pelo Notepad
ou pelo Word
.TXT
Exercício 1
Max Z = 3x1 - 5x2
SA:
Restr1) x1 < 4
Restr2) 2x2 < 12
Restr3) 3x1 + 2x2 > 18
x1 >=0; x2 >=0
27
28
15
Exercício 1
Modelo na forma canônica:
Max Z = 3x1- 5x2+0x3+0x4+0x5-Mxa1
sa
x1 + x3 = 4
2x2 + x4 = 12
3x1 + 2x2 - x5 + xa1 = 18
x1; x2; x3; x4; x5; xa1 ≥0 
Exercício 1
30
Base RHS X1 X2 X3 X4 X5 Xa1 Quoc 
X3 4 1 0 1 0 0 0 
X4 12 0 2 0 1 0 0 
Xa1 18 3 2 0 0 -1 1 
Z 0 -3 5 0 0 0 M 
 
 
 -18M -3M -2M 0 0 M -M 
 
 
Z -18M -3M-3 -2M+5 0 0 M 0 
 
 
29
30
16
Base RHS X1 X2 X3 X4 X5 Xa1 Quoc 
X3 4 1 0 1 0 0 0 4/1=4 
X4 12 0 2 0 1 0 0 --- 
Xa1 18 3 2 0 0 -1 1 18/3=6 
 
 
Z -18M -3M-3 -2M+5 0 0 M 0 
 
 
Exercício 1
Entrar
Na
Base
Sair 
Da 
Base
Base RHS X1 X2 X3 X4 X5 Xa1 Quoc 
X1 4 1 0 1 0 0 0 
X4 12 0 2 0 1 0 0 12/2=6 
Xa1 6 0 2 -3 0 -1 1 6/2=3 
Z -6M+12 0 -2M+5 3M+3 0 M 0 
 
 
Exercício 1
Entrar
Na
Base
Sair 
Da 
Base
31
32
17
Base RHS X1 X2 X3 X4 X5 Xa1 Quoc 
X1 4 1 0 1 0 0 0 
X4 6 0 0 3 1 1 -1 
X2 3 0 1 -1,5 0 -0,5 0,5 
Z -3 0 0 10,5 0 2,5 1M-2,5 
 
 
Solução Ótima z= -3 x1 = 4
x2 = 3
x3 = 0
x4 = 6
x5 = 0
Exercício 1
Exercício 1
33
34
18
Exercício 2
Max Z= x1 + x2 + x3
SA:
2 x1 + x2 – x3 ≤ 10
x1 + x2 + 2x3 ≥ 20
2 x1 + x2 + 3x3 = 60
x1, x2 , x3 >=0
Exercício 2
Ao tentar colocar na forma canônica:
Max Z = x1 + x2 + x3
sa:
Rest1) 2x1 + x2 - x3 + x4 = 10
Rest2) x1 + x2 + 2 x3 - x5 = 20
Rest3) 2x1 + x2 + 3 x3 = 60
Não dá para resolver !
Pois não conseguimos construir uma base, já que a folga x5 é 
negativa e folga da Rest3 não existe. Para “enganar “o modelo 
introduzimos o conceito de variáveis artificiais tipo A
35
36
19
Exercício 2
introduzindo as variáveis artificiais xAi
Reescrevemos as equações :
Rest1) 2x1 + x2 - x3 + x4 = 10
Rest2) x1 + x2 + 2 x3 - x5 + xA1 = 20
Rest3) 2x1 + x2 + 3 x3 + xA2 = 60 
Agora temos uma base , pois fazendo 
x1= x2 = x3 = x5 = 0 ficamos com a seguinte solução inicial: 
x4 = 10 , xA1 = 20 e xA2 = 60
Resultando no modelo a seguir
Max Z = x1 + x2 + x3 + 0x4 + 0 x5 – M xA1 - M xA2 
SA
Rest1) 2x1 + x2 - x3 + x4 = 10
Rest2) x1 + x2 + 2 x3 - x5 + xA1 = 20
Rest3) 2x1 + x2 + 3 x3 + xA2 = 60 
x1; x2; x3; x4; x5; xA1; xA2 >= 0
Modelo na forma canônica
37
38
20
Exercício 2 – resolvendo pelo LINDO
Max x1 + x2 + x3
ST 
Rest1) 2x1 + x2 - x3 < 10
Rest2) x1 + x2 + 2x3 > 20
Rest3) 2x1 + x2 + 3x3 = 60
END
Exercício 3 – Problema de Minimização
Min Z = 16x1 + 12x2 + 5x3
SA:
Restr1) 8x1 + 4x2 + 4x3 ≥ 16
Restr2) 4x1 + 6x2 ≥ 12
x1; x2; x3 ≥ 0
39
40
21
Exercício 3
Transformação em Maximização
Min Z = 16x1 + 12x2 + 5x3
Novo modelo:
Max (-Z) = -16x1 - 12x2 - 5x3 - 0x4 - 0x5 - Mxa1 - Mxa2
SA:
Restr1) 8x1 + 4x2 + 4x3 - x4 + xa1 ≥ 16
Restr2) 4x1 + 6x2 - x5 + xa2 ≥ 12
X1; x2; x3 ; x4 ;x5 ;xa1 ;xa2 ≥0
Base RHS x1 x2 x3 x4 x5 xa1 xa2 quociente
Sai base xa1 16 8 4 4 -1 0 1 0 16/8=2
xa2 12 4 6 0 0 -1 0 1 12/4=3
-Z 0 16 12 5 0 0 M M
-16M -8M -4M -4M M 0 -M 0
-12M -4M -6M 0 0 M 0 -M
-28M 16-12M 12-10M 5-4M M M 0 0
Entra na base
Base RHS x1 x2 x3 x4 x5 xa1 xa2 quociente
x1 2 1 0,5 0,5 -0,125 0 0,125 0 2/0,5=4
Sai base xa2 4 0 4 -2 0,5 -1 -0,5 1 4/1=1
-Z -4M-32 0 -4M+4 2M-3 -0,5M+2 M 1,5M-2 0
Entra na base
Base RHS x1 x2 x3 x4 x5 xa1 xa2 quociente
Sai base x1 1,5 1 0 0,75 -0,188 0,125 0,1875 -0,125 1,5/0,75=2
x2 1 0 1 -0,5 0,125 -0,25 -0,125 0,25 Negativo
-Z -36 0 0 -1 1,5 1 M-1,5 M-1
Entra na base
Base RHS x1 x2 x3 x4 x5 xa1 xa2
x3 2 1,333 0 1 -0,25 0,167 0.25 -0,167
x2 2 0,667 1 0 0 -0,167 0 0,167
-Z -34 1,333 0 0 1,25 1,167 M-0,125 M-1.167
Todos coef. de z positivos- sol. ótima
SOLUÇÃO ÓTIMA
-Z = -34 LOGO Z = 34
X1=0
X2=2
X3=2
Exercício 3 - Solução
41
42
22
Exercício 3
Exercício 3
-Z = -34 logo Z = 34
X1 = 0
X2 = 2
X3 = 2
43
44
23
Exercício 3 – resolvendo pelo LINDO
Min 16x1 + 12x2 + 5x3
ST
Restr1) 8x1 + 4x2 + 4x3 > 16
Restr2) 4x1 + 6x2 > 12
END
45