2001/2002Cecília Rocha # 1
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula6ª Aula Adaptação de problemas não standard ao Método Simplex
Ir-se-ão referir os procedimentos a adoptar para converter estes problemas em problemas que possam ser resolvidos pelo método simplex.
O maior problema passa a ser a determinação da SBA inicial
Será utilizada a técnica da Introdução de Variáveis Artificiais em cada restrição que delas precise de forma a criar um problema artificial que possa ser solucionado pelo Método Simplex.
Restrições de igualdade
A SBA inicial será dada por (x3, x4, x5) Como x5 tem um coeficiente diferente de zero na equação (0) teremos de o eliminar pelo método de Gauss
Z – 3x1 – 5x2 + Mx5 = 0 - M(3x1 +2x2 + x5 = 18) Z – (3M + 3) x1 – (2M + 5) x2 = - 18M , esta será a equação (0) para a resolução pela forma tabular
Max Z = 3x1 + 5x2 x1 4 2x2 12 3x1 + 2x2 18
x5x5 = 18 – 3x1 – 2x2
Max Z = 3x1 + 5x2 – Mx5
x1 4 2x2 12 3x1 + 2x2 18
Max Z - 3x1 - 5x2 + Mx5 = 0 x1 + x3 4 2x2 + x4 12 3x1 + 2x2 + x5 18
2001/2002Cecília Rocha # 2
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula6ª Aula
Adaptação de problemas não standard ao Método Simplex
Restrições de igualdade Na Função Objectivo (FO), o sinal da Variável Artificial varia consoante se está perante um
problema de minimização ou maximização, ou seja; Maximização
Z = 3x1 + 5x2 – Mx5, o sinal terá de ser negativo e ter um parâmetro de valor muito elevado (M) para obrigar a variável artificial
correspondente a ser zero.
MinimizaçãoZ = 0.4x1 + 0.5x2 + Mx3, o sinal positivo é utilizado para contrariar a evolução de minimização
que se pretende e obter e, assim, consegue-se obrigar a variável artificial a ser zero.
Nestes problemas, a Solução Óptima não pode ter valor diferente de zero para a Variável Artificial. Se existirem várias restrições de igualdade no mesmo problema, devem ser todas tratadas da forma
aqui descrita.
2001/2002Cecília Rocha # 3
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.)
Iteração VB Eq.Coeficientes
L D rácioZ x1 x2 x3 x4 x5
0
Z (0) 1 - 3M - 3 - 2M - 5 0 0 0 - 18M
x3 (1) 0 1 0 1 0 0 4 4/1 = 4
x4 (2) 0 0 2 0 1 0 12 S/s
x5 (3) 0 3 2 0 0 1 18 18/3 = 6
1
Z (0)-(-3M-3).(1) 1 0 - 2M - 5 3M + 3 0 0 - 6M + 12
x1 (1) 0 1 0 1 0 0 4 S/s
x4 (2) 0 0 2 0 1 0 12 12/2 = 6
x5 (3)-3(1) 0 0 2 - 3 0 1 6 6/2 = 3
2
Z (0 –(-2M-5).(3) 1 0 0 - 9/2 0 M + 5/2 27
x1 (1) 0 1 0 1 0 0 4 4/1 = 4
x4 (2) –2(3) 0 0 0 3 1 - 1 6 6/3 = 2
x2 (3)/ 2 0 0 1 - 3/2 0 1/2 3 S/s
3
Z (0) + 9/2.(2) 1 0 0 0 3/2 M + 1 36
Solução Óptima
(2,6,2,0,0)
x1 (1) – (2) 0 1 0 0 - 1/3 1/3 2
x3 (2) 3 0 0 0 1 1/3 - 1/3 2
x2 (3) + 3/2 (2) 0 0 1 0 1/2 0 6
2001/2002Cecília Rocha # 4
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula6ª Aula (cont.)(cont.)
Lados Direito negativos
Nestes casos, pode-se multiplicar a restrição por –1, tendo em atenção que o sinal passará a e vice-versa, exemplificando:
x1 – x2 -1 ficará como -x1 + x2 1
Se todas as variáveis tiverem restrições de Não- Negatividade, esta nova aparência da restrição permite considerar estes novos valores (positivos) como os valores da Solução Básica Inicial.
Restrições com a forma
Numa situação em que existam este tipo de restrições deve-se proceder da seguinte forma: Introduzir uma Variável Adicional (como forma de transformar o sinal em igual); Introduzir uma Variável Artificial (o procedimento recomendado anteriormente para restrições de =). Na função objectivo, introduzir as variáveis artificiais com um parâmetro muito elevado
Problema Inicial
Minimizar Z = 0.4x1 + 0.5x2s.a.: 0.3x1 + 0.1x2 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 6xi 0
Introdução da Var. Folga
Minimizar Z = 0.4x1 + 0.5x2s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 6xi 0
Introdução da Var. Artificial
Minimizar Z = 0.4x1 + 0.5x2 + Mx4x4s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 + x4x4 = 6 0.6x1 + 0.4x2 6xi 0
Introdução da Var. Adicional e Var. Artificial
Minimizar Z = 0.4x1 + 0.5x2 + Mx4x4 + Mx6x6s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 + x4x4 = 6 0.6x1 + 0.4x2 - x5x5 + x6x6 = 6xi 0
2001/2002Cecília Rocha # 5
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula6ª Aula (cont.)(cont.)
Minimização Uma das formas de resolver o problema é trocar o papel dos coeficientes positivos e negativos na linha (0), no teste de optimização e no primeiro passo do processo iterativo; No entanto, iremos adoptar outra abordagem – encontrar o problema equivalente de Maximização, por exemplo:
Iremos utilizar este procedimento para resolver o problema tratado no ponto anterior – Método do BIG MBIG M
Formulação do Problema Artificial
Vamos considerar como variáveis básicas, na Solução Básica Admissível Inicial, (x3x3, x4x4, x6x6) – as variáveis artificiais prevalecem sobre as adicionais.
Linha (0) x1 x2 x3x3 x4x4 x5x5 x6x6TInd
0.4 0.5 0 M 0 M0
- M [ 0.5 0.5 0 1 0 0 6]
- M [ 0.6 0.4 0 0 - 1 1 6 ] .
Nova Linha (0) (- 1.1M + 0.4) (- 0.9M + 0.5) 0 0 M 0 -12M
Minimizar Z = 0.4x1 + 0.5 x2 Maximizar - Z = - 0.4x1 – 0.5x2
Maximizar – Z = - 0.4x1 - 0.5x2 – Mx4x4 – Mx6x6s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 + x4x4 = 6 0.6x1 + 0.4x2 - x5x5 + x6x6 = 6
2001/2002Cecília Rocha # 6
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.)
Iteração VB EquaçãoCoeficientes
LD RácioZ x1 x2 x3x3 x4x4 x5x5 x6x6
0
Z (0) -1 -1.1M+0.4 -0.9M+0.5 0 0 M 0 -12M
x3x3 (1) 0 0.3 0.1 1 0 0 0 2.7 2.7/0.3 = 9
x4x4 (2) 0 0.5 0.5 0 1 0 0 6 6/0.5 = 12
x6x6 (3) 0 0.6 0.4 0 0 -1 1 6 6/0.6 = 10
1
Z (0)-(-1.1M+0.4)(1) -1 0 -16/30M+11/30 11/3M-4/3 0 M 0 -2.1M-3.6
x1 (1)/0.3 0 1 1/3 10/3 0 0 0 9 91/3=27
x4x4 (2)-0.5(1) 0 0 1/3 -5/3 1 0 0 1.5 1.51/3=4.5
x6x6 (3)-0.6(1) 0 0 0.2 -2 0 -1 1 0.6 0.6/0.2=3
3
Z (0)-(-5/3M+11/6)(2) -1 0 0 0.5 M-1.1 0 M -5.25
Solução Óptima
(7.5, 4.5, 00,00, 0.30.3, 00)
x1 (1)-20/3(2) 0 1 0 5 -1 0 0 7.5
x5x5 (2)5/3 0 0 0 1 3/5 1 -1 0.3
x2 (3)+10(2) 0 0 1 -5 3 0 0 4.5
2
Z (0)-(16/30M+11/30)(3) -1 0 0 -5/3M+7/3 0 -5/3M+11/6 8/3M-11/6 -0.5M-4.7
x1 (1)-1/3(3) 0 1 0 20/3 0 5/3 -5/3 8 85/3=4.8
x4x4 (2)-1/3(3) 0 0 0 5/3 1 5/3 -5/3 0.5 0.55/3=0.3
x2 (3)/0.2 0 0 1 -10 0 -5 5 3 S/s
2001/2002Cecília Rocha # 7
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula6ª Aula (cont.)(cont.)
Minimização Uma das formas de resolver o problema é trocar o papel dos coeficientes positivos e negativos na linha (0), no teste de optimização e no primeiro passo do processo iterativo; No entanto, iremos adoptar outra abordagem – encontrar o problema equivalente de Maximização, por exemplo:
Iremos utilizar este procedimento para resolver o problema tratado no ponto anterior – Método de DUAS FASESDUAS FASES
Formulação do Problema Artificial
A 1ª Fase tem como objectivo eliminar as variáveis artificiais, sendo obtida da equação da Nova Linha (0) do método do BIG M que é dividida por M, obtendo-se alguns termos infinitesimais que são negligenciados. No final desta fase como x4 e x6 se anularão, então poder-se-á utilizar esta solução com SBA Inicial para a 2ª Fase. A 2ª Fase resolve o problema pelo método simplex, utilizando como SBA inicial o resultado da fase anterior.
Minimizar Z = 0.4x1 + 0.5 x2 Maximizar - Z = - 0.4x1 – 0.5x2
1ª Fase1ª Fase
Maximizar – Z = – x4x4 – x6x6s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 + x4x4 = 6 0.6x1 + 0.4x2 - x5x5 + x6x6 = 6
2ª Fase2ª Fase
Maximizar – Z = - 0.4x1 - 0.5x2s.a.: 0.3x1 + 0.1x2 + x3x3 = 2.7 0.5x1 + 0.5x2 = 6 0.6x1 + 0.4x2 - x5x5 = 6
2001/2002Cecília Rocha # 8
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL 6ª Aula 6ª Aula (cont.)(cont.)
1ª Fase
Iteração VB EquaçãoCoeficientes
LD RácioZ x1 x2 x3x3 x4x4 x5x5 x6x6
0
Z (0) -1 -1. -0.9 0 0 1 0 -12
x3x3 (1) 0 0.3 0.1 1 0 0 0 2.7 2.7/0.3 = 9
x4x4 (2) 0 0.5 0.5 0 1 0 0 6 6/0.5 = 12
x6x6 (3) 0 0.6 0.4 0 0 -1 1 6 6/0.6 = 10
1
Z (0)-(-1.1)(1) -1 0 -16/30 11/3 0 1 0 -2.1
x1 (1)/0.3 0 1 1/3 10/3 0 0 0 9 91/3=27
x4x4 (2)-0.5(1) 0 0 1/3 -5/3 1 0 0 1.5 1.51/3=4.5
x6x6 (3)-0.6(1) 0 0 0.2 -2 0 -1 1 0.6 0.6/0.2=3
2
Z (0)-(16/30)(3) -1 0 0 -5/3 0 -5/3 8/3 -0.5
x1 (1)-1/3(3) 0 1 0 20/3 0 5/3 -5/3 8 85/3=4.8
x4x4 (2)-1/3(3) 0 0 0 5/3 1 5/3 -5/3 0.5 0.55/3=0.3
x2 (3)/0.2 0 0 1 -10 0 -5 5 3 S/s
3
Z (0)-(-5/3)(2) -1 0 0 0 1 0 1 0
Fim da
1ª Fase
x1 (1)/0.3 0 1 0 0 -4 -5 5 6
x3x3 (2)-0.5(1) 0 0 0 1 3/5 1 -1 0.3
x2 (3)-0.6(1) 0 0 1 0 6 5 -5 6
2001/2002Cecília Rocha # 9
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.)
Preparação da 2ª Fase
Iteração VB EquaçãoCoeficientes
LD RácioZ x1 x2 x3x3 x4x4 x5x5 x6x6
3
Z (0)-(-5/3)(2) -1 0 0 0 1 0 1 0
Fim da
1ª Fase
x1 (1)/0.3 0 1 0 0 -4 -5 5 6
x3x3 (2)-0.5(1) 0 0 0 1 3/5 1 -1 0.3
x2 (3)-0.6(1) 0 0 1 0 6 5 -5 6
4
Z (0) -1 0 0 0 0 0
x1 (1) 0 1 0 0 -5 6
x3x3 (2) 0 0 0 1 1 0.3
x2 (3) 0 0 1 0 5 6
6
Z (0)-0.4(1)-0.5(3) -1 0 0 0 -0.5 -5.4
Final da preparação da 2ª Fase
x1 (1) 0 1 0 0 -5 6
x3x3 (2) 0 0 0 1 1 0.3
x2 (3) 0 0 1 0 5 6
5
Z (0) -1 0.4 0.5 0 0 0
x1 (1) 0 1 0 0 -5 6
x3x3 (2) 0 0 0 1 1 0.3
x2 (3) 0 0 1 0 5 6
2001/2002Cecília Rocha # 10
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.)
2ª Fase
Iteração VB EquaçãoCoeficientes
LD RácioZ x1 x2 x3x3 x4x4 x5x5 x6x6
6
Z (0)-0.4(1)-0.5(3) -1 0 0 0 -0.5 -5.4
x1 (1) 0 1 0 0 -5 6 S/s
x3x3 (2) 0 0 0 1 1 0.3 0.3/1=0.3
x2 (3) 0 0 1 0 5 6 6/5=1.11
7
Z (0) -1 0 0 0.5 0 -5.25
Solução Óptima
(7.5, 4.5, 00,00, 0.30.3, 00)
x1 (1) 0 1 0 5 0 7.5
x5x5 (2) 0 0 0 1 1 0.3
x2 (3) 0 0 1 -5 0 4.5
2001/2002Cecília Rocha # 11
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.) Problema sem Solução Admissível
Se o problema inicial não tem Soluções Admissíveis então, tanto o método do BIG M como a 1ª Fase do método de DUAS FASES irão conduzir a soluções finais em que pelo menos uma variável artificial tem valor diferente de zero.
Como exemplo, se no problema anterior alterarmos a 1ª Restrição para 0.3x1 + 0.1x2 1.8 (anteriormente era 2.7)
Iteração VB EquaçãoCoeficientes
LD RácioZ x1 x2 x3x3 x4x4 x5x5 x6x6
0
Z (0) -1 -1.1M+0.4 -0.9M+0.5 0 0 M 0 -12M
x3x3 (1) 0 0.3 0.1 1 0 0 0 1.8 1.8/0.3 = 6
x4x4 (2) 0 0.5 0.5 0 1 0 0 6 6/0.5 = 12
x6x6 (3) 0 0.6 0.4 0 0 -1 1 6 6/0.6 = 10
1
Z (0) -1 0 -16/30M+11/30 11/3M-4/3 0 M 0 -5.4M-2.4
x1 (1) 0 1 1/3 10/3 0 0 0 6 61/3=18
x4x4 (2) 0 0 1/3 -5/3 1 0 0 3 31/3=9
x6x6 (3) 0 0 0.2 -2 0 -1 1 2.4 2.4/0.2=12
2
Z (0) -1 0 0 M+0.5 1.6M-1.1 M 0 -0.6M-5.7
Como x6x6 =0.6 >0Problema S/ solução
x1 (1) 0 1 0 5 -1 0 0 3
x2 (2) 0 0 1 -5 3 0 0 9
x6x6 (3) 0 0 0 -1 -0.6 -1 1 0.6
2001/2002Cecília Rocha # 12
IINVESTIGAÇÃONVESTIGAÇÃO OOPERACIONALPERACIONAL
6ª Aula 6ª Aula (cont.)(cont.)
Variáveis sem restrição de não negatividade Com limite no valor negativo admitidoCom limite no valor negativo admitido
xj Lj, sendo Lj um valor negativo constante Considerar x’j = xj – Lj, em que x’j 0
Que admitem qualquer valor negativoQue admitem qualquer valor negativo xj = xj
+ - xj-, em que xj
+ 0 e xj- 0
Z = 3x1 + 5x2
x1 4
2x2 12
3x1 + 2x2 18
x1 -10 x2 0
Z = 3(x’1-10) + 5x2
(x’1-10) 4
2x2 12
3(x’1-10) + 2x2 18
(x’1-10) -10 x2 0
Z = -30 + 3x’1 + 5x2
x’1 14
2x2 12
3x’1 + 2x2 18
X’1 0 x2 0
Z = 3x1 + 5x2
x1 4
2x2 12
3x1 + 2x2 18
x2 0
Z = 3(x1+
- x1-) + 5x2
(x1+
- x1-) 4
2x2 12
3(x1+
- x1-) + 2x2 18
(x1+
0; x1- 0); x2 0
Z = 3x1+
- 3x1-) + 5x2
x1+
- x1- 4
2x2 12
3x1+
- 3x1- + 2x2 18
(x1+
0; x1- 0); x2 0