Capitulo 2 - Parte IV - Método de Grande M e Duas Fases 2020

Investigação Operacional
Regente: Dr. Cachimo Assane
Capítulo 2: Tema 4 - Os Métodos Grande M e das Duas fases
Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I
Regente: Dr. Cachimo Assane (ISUTC) Investigação Operacional Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem
Solução Inicial Artificial
Até agora abordamos o método simplex para PPLs com restrições do tipo (≤)
e bj ≥ 0.
A SBV inicial desses PPLs é encontrada de forma trivial, deixando as variáveis
de folga serem VBs iniciais.
No entanto, quando o PPL possuir restrições da forma:
Xn
aij xj = bj ;
j=1
n
X
aij xj ≥ bj ; ou
j=1
Xn
aij xj ≤ −bj ,
j=1
a sua forma padrão não equivale à forma canônica e, por conseguinte, não terá
uma SBV inicial.
Nesse caso, é preciso transformar o problema e buscar esta SBV.
Solução inicial artificial
Como encontrar a SBV inicial? usa-se a técnica das variáveis artificiais

Introduz-se uma variável artificial em cada restrição que assim necessitar;
Essa variável artificial desempenha o papel de folga na primeira iteração;
Todas as variáveis artificiais são descartadas (tornado-as zero), uma por vez,
em iterações posteriores do simplex;
Exemplo 1: Considere o seguinte PPL:
Minimizar W = x1 − 2x2
Sujeito a :
x1 + x2 ≥ 2
x1 ≤ 1
x2 ≤ 3
x1 , x2 ≥ 0.
Colocando o PPL na forma padrão, temos:
x1 + x2 − x3 = 2
x1 + x4 = 1
s.a.
x2 + x5 = 3
x1 , x2 , x 3, x4 , x5 ≥ 0.
Na forma matricial, esta formulação fica:

x1 x2 x3 x4 x5

Min 1 −2 0 0 0
   
1 1 −1 0 0 2
s.a  1 0 0 1 0 = 1 
0 1 0 0 1 3
Colocando o PPL na forma padrão, temos:
x1 + x2 − x3 = 2
x1 + x4 = 1
s.a.
x2 + x5 = 3
x1 , x2 , x 3, x4 , x5 ≥ 0.
Na forma matricial, esta formulação fica:

x1 x2 x3 x4 x5

Min 1 −2 0 0 0
   
1 1 −1 0 0 2
s.a  1 0 0 1 0 = 1 
0 1 0 0 1 3
Observe que não existe nenhuma sequência tal que o PPL está na forma
canônica (6 ∃ uma sequência S, t.q AS = I e CS = 0);
Como proceder?: adiciona-se uma variável artificial na 1a restrição:
Minimizar Z = x1 − 2x2
x1 + x2 − x3 + x1a = 2
x1 + x4 = 1
s.a.
x2 + x5 = 3
x1 , x2 , x 3, x4 , x5 , x1a ≥ 0.
x1a

x1 x2 x3 x4 x5

Min 1 −2 0 0 0 0
   
1 1 −1 0 0 1 2
s.a  1 0 0 1 0 0 = 1 
0 1 0 0 1 0 3
Agora, a sequência {1a , 4,5} é uma base para o problema;
Dois métodos pelos quais se busca a SBV inicial: O método Grande M (Big
M) e o Método das duas fases.
O objectivo desses métodos é eliminar esta variável da base, chegando a SBV
inicial do PPL original.
O método Grande M
O método grande M começa com um PPL na forma padrão (equações);

Se a equação i não tiver uma folga (ou uma variável que desempenhe esse
papel), uma variável artificial xia é adicionada para formar uma solução inicial;
Como as variáveis artificiais não são parte do PPL original, elas recebem uma
penalidade muito grande na função objectivo;
Os coeficientes dessas variáveis artificiais na FO é um número muito grande,
representado por M (dai o nome do método);
Essa penalidade força as variáveis artificiais a serem iguais a zero na solução

óptima. Isso sempre ocorrerá se o PPL for viável;
O método Grande M
Assim, com o PPL já colocado na forma canônica, a formulação completa seria:
Minimizar W = x1 − 2x2 + Mx1a

x1 + x2 − x3 + x1a = 2
x1 + x4 = 1
s.a.
x2 + x5 = 3
x1 , x2 , x 3, x4 , x5 , x1a ≥ 0.
VB x1 x2 x3 x4 x5 x1a b
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O 1 -2 0 0 0 M W
Devem ser feitas transformações na última linha de forma que o problema fique
na forma canônica.
0
Fazendo L4 = L4 − ML1 , encontra-se o seguinte resultado:
O método Grande M
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O 1-M -2-M M 0 0 0 W − 2M
Na 1a iteração, a variável x2 entrará na base no lugar de x1a .

Operações VB x1 x2 x3 x4 x5 x1a b
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
SBV inicial
x5 0 1 0 0 1 0 3
F.O 1-M -2-M M 0 0 0 W − 2M
0
L1 = L1 x2 1 1 -1 0 0 1 2
0
L2 = L2 x4 1 0 0 1 0 0 1
0 0
L3 = L3 − L1 x5 -1 0 1 0 1 -1 1
0 0
L4 = L4 + (2 + M)L1 F.O 3 0 -2 0 0 2+M W +4
0 0
L1 = L1 + L3 x2 0 1 0 0 1 0 3
0
L2 = L2 x4 1 0 0 1 0 0 1
0
L3 = L3 x3 -1 0 1 0 1 -1 1
0 0
L4 = L4 + 2L3 F.O 1 0 0 0 2 M W +6
O método Grande M
A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;
O método Grande M
A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;

O método grande M encontrou a SBV incial através da inserção de penalidades
nas variáveis artificial, que foram prontamente retiradas da base, na busca de
uma SBV do problema original.
Observação: A utilização da penalidade do M não forçará uma variável artificial
ao nível zero na iteração final se o PPL não tiver uma solução viável.
Nesse caso, pelo menos uma variável artificial será positivo na iteração final do
método simplex.
O método Grande M
Exemplo 2: Utilize o método de Big M para resolver o seguinte PPL

Minimizar W = 2x1 + 3x2
Sujeito à
2x1 + 1x2 ≥ 3
1x1 + 1x2 = 2
x1 ,x2 ≥ 0
O método Grande M
Exemplo 2: Utilize o método de Big M para resolver o seguinte PPL

Sujeito à
2x1 + 1x2 ≥ 3
1x1 + 1x2 = 2
x1 ,x2 ≥ 0
Transformação do PPL na forma padrão e introdução da variável artificial:
Minimizar W = 2x1 + 3x2 + 0x3 + Mx1a + Mx2a
Sujeito à
2x1 + 1x2 − x3 + x1a + 0x2a = 3
1x1 + 1x2 + 0x3 + 0x1a + x2a = 2
x1 ,x2 , x3 , x1a , x1a ≥ 0
O principal objectivo é tentar eliminar das variáveis artificiais da base
O método Grande M
Exemplo 2 (Continuação):
VB x1 x2 x3 x1a x2a b
x1a 2 1 -1 1 0 3
x2a 1 1 0 0 1 2
FO 2 3 0 M M W
FO 2-3M 3-2M M 0 0 W − 5M
x1 1 1/2 -1/2 1/2 0 3/2
x2a 0 1/2 1/2 -1/2 1 1/2
F0 0 2-M/2 1-M/2 3M/2-1 0 W − M/2 − 3
x1 1 1 0 0 1 2
x3 0 1 1 -1 2 1
FO 0 1 0 M M-2 W −4
2
" #
∗
Solução: x = 0 , W ∗ = 4 u.m.
1
O método das duas fases
Este método consiste em introduzir uma nova função objectivo com o intuito
de minimizar a soma das variáveis artificiais;
Primeira fase: Busca de uma SBV inicial do PPL original:
Ü Coloque o PPL na forma padrão e adicione as variáveis artificiais necessárias
às restrições para garantir a SBV inicial;
Ü Ache uma SBV que minimize a soma das variáveis artificiais;
Ü O PPL só tem solução viável se a solução (o valor da F.O.) da primeira fase
for igual a zero.
Ü Se o valor mínimo da soma for positivo, o PPL não tem nenhuma solução
viável, o que encerra o processo.
Segunda fase: Considerando a SBV calculada na primeira fase como SBV
inicial, aplica-se o simplex em busca da solução óptima do PPL original.
Exemplo 3: Consideremos o PPL do exemplo 1 na forma canônica:
Sujeito a :
x1 + x2 − x3 + x1a = 2
x1 + x4 = 1
x2 + x5 = 3
x1 , x2 , x 3, x4 , x5 , x1a ≥ 0.
Na primeira fase o PPLa a ser criado terá como FO
Minimizar W a = x1a .
Desta forma, se a solução deste problema for zero, foi obtida uma SBV do PPL
original e a variável artificial pode ser eliminada.
Primeira fase
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O 0 0 0 0 0 1 Wa
Primeira fase
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O 0 0 0 0 0 1 Wa
A linha da FO deve ser transformada para o PPL assumir a forma canônica em
0
relação a sequência {1a , 4, 5}. Assim, fazendo L4 = L4 − L1 , tem-se:
Primeira fase
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O 0 0 0 0 0 1 Wa
A linha da FO deve ser transformada para o PPL assumir a forma canônica em
0
relação a sequência {1a , 4, 5}. Assim, fazendo L4 = L4 − L1 , tem-se:
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
x5 0 1 0 0 1 0 3
F.O -1 -1 1 0 0 0 Wa − 2
O problema está na forma canônica. O simplex pode ser iniciado. Como há
empate na variável que entra na base, a escolha é arbitrária.
Primeira fase (Continuação)

Operações VB x1 x2 x3 x4 x5 x1a b
x1a 1 1 -1 0 0 1 2
x4 1 0 0 1 0 0 1
SBV inicial
x5 0 1 0 0 1 0 3
F.O -1 -1 1 0 0 0 Wa − 2
0
L1 = L1 x2 1 1 -1 0 0 1 2
0
L2 = L2 x4 1 0 0 1 0 0 1
0 0
L3 = L3 − L1 x5 -1 0 1 0 1 -1 1
0 0
L4 = L4 + L1 F.O 0 0 0 0 0 1 Wa
A SBV x ∗ = {0, 2, 0, 1, 1, 0} é também a solução óptima do PPLa , pois todos

os coeficientes da FO são não negativos.
A variável artificial é nula e saiu da base. Portanto, pode ser retirada do

problema, e este continuará na forma canônica, a menos da FO do PPL original;
Neste caso, o PPL deverá ser recolocado na forma canônica através de

operações algébricas.
Segunda fase
Operações VB x1 x2 x3 x4 x5 b
x2 1 1 -1 0 0 2
x4 1 0 0 1 0 1
x5 -1 0 1 0 1 1
F.O 1 -2 0 0 0 W
0 0
L4 = L4 + 2L1 F.O 3 0 -2 0 0 W +4
Esta tabela é exactamente igual à do método grande M quando da eliminação

das variáveis artificiais.
A partir deste ponto, a resolução é exactamente a mesma. Ou seja
Segunda fase (continuação)

Operações VB x1 x2 x3 x4 x5 b
x2 1 1 -1 0 0 2
x4 1 0 0 1 0 1
SBV inicial
x5 -1 0 1 0 1 1
F.O 3 0 -2 0 0 W +4
0 0
L1 = L1 + L3 x2 0 1 0 0 1 3
0
L2 = L2 x4 1 0 0 1 0 1
0
L3 = L3 x3 -1 0 1 0 1 1
0 0
L4 = L4 + 2L3 F.O 1 0 0 0 2 W +6
Encontramos a solução óptima do PPL original: x ∗ = {0, 3, 1, 1, 0} com Z =

−6.
Observação importante: Se ao final da primeira fase do método de duas fases
o somatório das variáveis não for zero, então, não existe a SBV para o PPL
original (PPL inviável).
Exemplo 4: Considere o PPL do exemplo 2, utilize o método das fases para

resolve-lo:
Sujeito à
2x1 + 1x2 ≥ 3
1x1 + 1x2 = 2
x1 ,x2 ≥ 0
Exemplo 4: Considere o PPL do exemplo 2, utilize o método das fases para

resolve-lo:
Sujeito à
2x1 + 1x2 ≥ 3
1x1 + 1x2 = 2
x1 ,x2 ≥ 0
Transformação do PPL na forma padrão e introdução da variável artificial:
Minimizar W = 2x1 + 3x2 + 0x3 + 0x1a + 0x2a
Sujeito à
2x1 + 1x2 − x3 + x1a + 0x2a = 3
1x1 + 1x2 + 0x3 + 0x1a + x2a = 2
x1 ,x2 , x3 , x1a , x1a ≥ 0
Primeira fase: a Função objectivo é Minimizar W a = x1a + x2a
Exemplo 4: Resolução da primeira fase

VB x1 x2 x3 x1a x2a b
x1a 2 1 -1 1 0 3
x2a 1 1 0 0 1 2
F 0a 0 0 0 1 1 Wa
F 0a -3 -2 1 0 0 Wa − 5
x1 1 1/2 -1/2 1/2 0 3/2
x2a 0 1/2 1/2 -1/2 1 1/2
Wa 0 -1/2 -1/2 3/2 0 Wa − 1/2
x1 1 1 0 0 1 2
x3 0 1 1 -1 2 1
Wa 0 0 0 1 1 Wa
Segunda fase: A partir da SB óptima do PPL artificial, eliminando as colunas

das variáveis artificiais e a linha de FOa que é substituída pela FO origninal,
tem-se:
Exemplo 4 (continuação): Segunda fase
VB x1 x2 x3 b
x1 1 1 0 2
x3 0 1 1 1
F0 2 3 0 W
F0 0 2 0 W −4
Portanto X ∗ = (2, 0, 1); W ∗ = 4

Capitulo 2 - Parte IV - Método de Grande M e Duas Fases 2020

Enviado por

Direitos autorais:

Formatos disponíveis

Capitulo 2 - Parte IV - Método de Grande M e Duas Fases 2020

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Capitulo 2 - Parte IV - Método de Grande M e Duas Fases 2020

Enviado por

Direitos autorais:

Formatos disponíveis

Investigação Operacional

Regente: Dr. Cachimo Assane

Capítulo 2: Tema 4 - Os Métodos Grande M e das Duas fases

Cursos de Licenciatura: LEMT, LECT e LEF-2020/Sem I

Como encontrar a SBV inicial? usa-se a técnica das variáveis artificiais

 Na forma matricial, esta formulação fica:

 Na forma matricial, esta formulação fica:

 O método grande M começa com um PPL na forma padrão (equações);

 Essa penalidade força as variáveis artificiais a serem iguais a zero na solução

Minimizar W = x1 − 2x2 + Mx1a

 Na 1a iteração, a variável x2 entrará na base no lugar de x1a .

 A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;

 A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;

Exemplo 2: Utilize o método de Big M para resolver o seguinte PPL

Exemplo 2: Utilize o método de Big M para resolver o seguinte PPL

Exemplo 3: Consideremos o PPL do exemplo 1 na forma canônica:

 Na primeira fase o PPLa a ser criado terá como FO

 Primeira fase (Continuação)

 A SBV x ∗ = {0, 2, 0, 1, 1, 0} é também a solução óptima do PPLa , pois todos

 A variável artificial é nula e saiu da base. Portanto, pode ser retirada do

 Neste caso, o PPL deverá ser recolocado na forma canônica através de

 Esta tabela é exactamente igual à do método grande M quando da eliminação

 Segunda fase (continuação)

 Encontramos a solução óptima do PPL original: x ∗ = {0, 3, 1, 1, 0} com Z =

Exemplo 4: Considere o PPL do exemplo 2, utilize o método das fases para

Exemplo 4: Considere o PPL do exemplo 2, utilize o método das fases para

 Primeira fase: a Função objectivo é Minimizar W a = x1a + x2a

Exemplo 4: Resolução da primeira fase

 Segunda fase: A partir da SB óptima do PPL artificial, eliminando as colunas

Exemplo 4 (continuação): Segunda fase

Portanto X ∗ = (2, 0, 1); W ∗ = 4

Você também pode gostar

Na forma matricial, esta formulação fica:

Na forma matricial, esta formulação fica:

O método grande M começa com um PPL na forma padrão (equações);

Essa penalidade força as variáveis artificiais a serem iguais a zero na solução

Na 1a iteração, a variável x2 entrará na base no lugar de x1a .

A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;

A solução óptima é x ∗ = {0, 3, 1, 1, 0}, com W ∗ + 6 = 0, ou seja, W ∗ = −6;

Na primeira fase o PPLa a ser criado terá como FO

Primeira fase (Continuação)

A SBV x ∗ = {0, 2, 0, 1, 1, 0} é também a solução óptima do PPLa , pois todos

A variável artificial é nula e saiu da base. Portanto, pode ser retirada do

Neste caso, o PPL deverá ser recolocado na forma canônica através de

Esta tabela é exactamente igual à do método grande M quando da eliminação

Segunda fase (continuação)

Encontramos a solução óptima do PPL original: x ∗ = {0, 3, 1, 1, 0} com Z =

Primeira fase: a Função objectivo é Minimizar W a = x1a + x2a

Segunda fase: A partir da SB óptima do PPL artificial, eliminando as colunas