Unidade_05

Prévia do material em texto

PROGRAMAÇÃO LINEAR
PROBLEMAS DE FORMA NÃO-PADRÃO
� Problemas de Forma Não Padrão
� Minimização
� Restrições de Maior ou Igual
� Restrições com Constantes Negativas
� Método da Função Artificial
1 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
� Método da Função Artificial
� Restrições de Igualdade
� Variáveis Negativas
PROGRAMAÇÃO LINEAR
PROBLEMAS DE FORMA NÃO-PADRÃO
� Problemas de programação linear podem apresentar outras formas, 
tais como, igualdades e formas maior ou igual e/ou constantes não tais como, igualdades e formas maior ou igual e/ou constantes não 
positivas nas restrições, ou ainda problemas de minimização.
� Estas formas de modelo apresentam problemas de se encontrar a 
solução básica inicial.
1- Por não existir esta solução básica inicial;
2 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
1- Por não existir esta solução básica inicial;
2 - Por não ser óbvia a solução inicial como no caso do formato padrão.
FORMA NÃO-PADRÃO
MINIMIZAÇÃO
� Minimização � Maximização
122
4
:
53
2
1
21
≤
≤
−=
x
x
sa
xxZMin
122
4
:
53
2
1
21
≤
≤
+−=−=
x
x
sa
xxZWMax
3 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
0,
1823
122
21
21
2
≥
≤+
≤
xx
xx
x
0,
1823
21
21
2
≥
≤+
xx
xx
FORMA NÃO-PADRÃO
PROBLEMAS DE INICIALIZAÇÃO
� No caso de alguma restrição, for representada por uma igualdade, 
ou por uma inequação do tipo maior ou igual, ao invés de uma ou por uma inequação do tipo maior ou igual, ao invés de uma 
restrição de menor ou igual, duas soluções possíveis podem 
ocorrer:
� Processo do “M Grande”
4 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
� Método das Duas fases 
FORMA NÃO-PADRÃO
RESTRIÇÕES DO TIPO MAIOR OU IGUAL
QUADRO SIMPLEX
Max Z x x= −3 51 2
1
2x ≤ 122
3x x+ ≥2 181 2
sa: x ≤ 4
x x≥ ≥0 0,
Associada Solução
53
1823
212
4
21
215
24
13
−=
−+=
−=
−=
xxZ
xxx
xx
xx
5 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
x x≥ ≥0 01 2, )18;12;4;0;0(
Associada Solução
−
FORMA NÃO-PADRÃO
MÉTODO DA FUNÇÃO ARTIFICIAL
QUADRO SIMPLEX ARTIFICIAL
Associada Solução
53
1823
212
4
21
215
24
13
−=
−+=
−=
−=
xxZ
xxx
xx
xx
0,,,,,
053
1823
122
4
154321
21
1521
42
31
≥
=+−
=+−+
=+
=+
Txxxxx
xxZ
Txxx
xx
xx
6 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
)18;12;4;0;0(
Associada Solução
−
)18;0;12;4;0;0(
Associada Solução
FORMA NÃO-PADRÃO
MÉTODO DA FUNÇÃO ARTIFICIAL
� Como T1 é uma variável artificial (não faz parte do problema original) 
deseja-se encontrar uma solução para o simplex artificial, na qual o deseja-se encontrar uma solução para o simplex artificial, na qual o 
valor de T1 seja igual a zero.
� Esta solução fará parte do conjunto de soluções viáveis de ambos os 
problemas (original e artificial).
� Para tal, deve-se modificar a função-objetivo de maneira a encontrar 
7 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
� Para tal, deve-se modificar a função-objetivo de maneira a encontrar 
esta solução.
FORMA NÃO-PADRÃO
MÉTODO DO GRANDE M
� Para obter a solução inicial, a variável Xfolga deve assumir valor igual 
à zero enquanto a variável artificial T1 assumirá valor igual a bm (neste 1 m
caso ela será uma variável básica e Xfolga não básica).
� Deve-se, ainda, forçar o método simplex a zerar a variável artificial. 
Para isso, se faz necessário utilizar o método do grande M, que 
consiste em penalizar a variável artificial na função objetivo com um 
valor extremamente grande. Isso fará com que o simplex zere as 
variáveis artificiais.
8 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
variáveis artificiais.
� Com o uso do método do grande M a função objetivo será dada por:
Z = C1X1 + C2X2 + ... + CnXn - MT1
FORMA NÃO-PADRÃO
MÉTODO DO GRANDE M
� E a linha Z- transformada na tabela será:
Eq. [0] = Z - C1X1 - C2X2 - ... - CnXn + MT1 Eq. [0] = Z - C1X1 - C2X2 - ... - CnXn + MT1 
� Foi comentado anteriormente que a variável artificial T1 seria uma 
variável básica. Porém, sabe-se que as variáveis básicas devem 
possuir valores nulos na linha Z-transformada. Neste caso, antes de 
começar a solucionar o problema tem-se que modificar o quadro 
simplex para garantir este formato.
9 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
simplex para garantir este formato.
� A modificação será semelhante ao que foi realizado quando as 
variáveis básicas foram modificadas. A nova linha Z será dada por:
Nova Linha Z = linha Z – M * (Linha da variável artificial) 
Modelo original e Modelo Adaptado
Quadro 1 - Modelo original. Quadro 2 - Modelo modificado e adaptado.
EXEMPLO
MÉTODO DO GRANDE M
Quadro 1 - Modelo original.
MAX Z = 10X1 + 15X2 + 12X3
s.a.
0,75X1 + X2 + 1,5X3 ≤ 160
X2 ≤ 35
X3 ≥ 40
Quadro 2 - Modelo modificado e adaptado.
MAX Z = 10X1 + 15X2 + 12X3 – MT1
s.a.
0,75X1 + X2 + 1,5X3 + X4 = 160
X2 + X5 = 35
X3 - X6 + T1 = 40
10 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
X3 - X6 + T1 = 40
X1, X2, X3 ≥ 0
X4, X5, X6 ≥ 0
T1 ≥ 0
Quadro 1 (Inicial)
Passo 2
- Deve-se modificar a linha (0) para poder iniciar as iterações no quadro simplex. 
EXEMPLO
MÉTODO DO GRANDE M
x1E.q.
Z
Z Lado 
direito
Coeficientes
E.q. x3 x4Variável
Básica
-10 -12 -M 0 01[0]
x5x2
-15 M
x6
0
T1
-40M
- Deve-se modificar a linha (0) para poder iniciar as iterações no quadro simplex. 
- A modificação é feita subtraindo da linha (0) M vezes a linha (3), que é a linha que 
possui a variável artificial.
11 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
x5
x4 0,75
0
1,5
0
1
0
0
1
0
0
[1]
[2]
1
1
0
0
0
0
160
35
40T1 0 1 0 00[3] 0 -1 1
Solução Inicial
Passo 3
Solução Viável Inicial: Z= -40M
EXEMPLO
MÉTODO DO GRANDE M
Solução Viável Inicial: Z= -40M
X1 = 0
X2 = 0
X3 = 0
X4 = 160
X5 = 35
X6 = 0
T1 = 40
12 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
Decisão:
� Enquanto variáveis não básicas da F.O. tiverem coeficientes positivo, a solução atual 
pode ser melhorada. 
Quadro após 1ª iteração
Passo 6
Coeficientes
EXEMPLO
MÉTODO DO GRANDE M
x5
x4
x1E.q.
Z
Z Lado 
direito
E.q. x3 x4Variável
Básica
-10
0,75
0
0
0
0
0
1
0
0
0
1
1
0
0
[0]
[1]
[2]
x5x2
-15
1
1
-12
1,5
0
x6
12+M
-1,5
0
T1
480
100
35
13 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
40x3 0 1 0 00[3] 0 -1 1
1ª Operação: 
Linha [1] = (-1,5) * linha pivô + linha [1]
2ª Operação: 
Linha [0] = (12+M) * linha pivô + linha [0]
Quadro após 2ª iteração
Coeficientes
EXEMPLO
MÉTODO DO GRANDE M
x2
x4
x1E.q.
Z
Z Lado 
direito
Coeficientes
E.q. x3 x4Variável
Básica
-10
0,75
0
0
0
0
0
1
0
15
-1
1
1
0
0
[0]
[1]
[2]
x5x2
0
0
1
-12
1,5
0
x6
12+M
-1,5
0
T1
1005
65
35
14 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
1ª Operação: 
Linha [1] = (-1) * linha pivô + linha [1]
2ª Operação: 
Linha [0] = (15) * linha pivô + linha [0]
40x3 0 1 0 00[3] 0 -1 1
Quadro após 3ª iteração
Coeficientes
EXEMPLO
MÉTODO DO GRANDE M
x2
x6
x1
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica
-4
0,5
0
0
0
0
8,04
0,67
0
6,96
-0,67
1
1
0
0
[0]
[1]
[2]
x5x2
0
0
1
0
1
0
x6
M
-1
0
T1
1524,96
43,33
35
15 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
1ª Operação: Linha [1] = linha 1 / (1,5)
2ª Operação: Linha [3] = linha pivô + linha [3]
83,33x3 0,5 1 0,67 -0,670[3] 0 0 0
3ª Operação: 
Linha [0] = (12) * linha pivô + linha [0]
Quadro após 4ª iteração
Coeficientes
EXEMPLO
MÉTODO DO GRANDE M
x2
x1
x1
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica0
1
0
0
0
0
13,4
1,34
0
0,4
-1,34
1
1
0
0
[0]
[1]
[2]
x5x2
0
0
1
8
2
0
x6
M-8
-2
0
T1
1871,6
86,66
35
16 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
40x3 0 1 0 00[3] 0 -1 1
Z= 1871,6
X1 = 86,66 X3 = 40 
X2 = 35 X4 = X5 = X6 = 0
Encontrada a 
solução ótima
FORMA NÃO-PADRÃO
MÉTODO DAS DUAS FASES
Passos:
1 – Encontrar o modelo adaptado;1 – Encontrar o modelo adaptado;
2 – Definir a função artificial W
- (soma de cada variável de decisão e folga) = - (soma dos termos independentes)
3 – Fase 1 (objetivo: anular a função artificial W);
4 – Fase 2 (retirar a função W e as colunas das variáveis artificiais – continuar o processo 
17 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
4 – Fase 2 (retirar a função W e as colunas das variáveis artificiais – continuar o processo 
de solução)
5 – Solução Ótima
Modelo original e Modelo Adaptado
Quadro 1 - Modelo original. Quadro 2 - Modelo modificado e adaptado.
EXEMPLO
MÉTODO DAS DUAS FASES
Quadro 1 - Modelo original.
MAX Z = 10X1 + 15X2 + 12X3
s.a.
0,75X1 + X2 + 1,5X3 ≤ 160
X2 ≤ 35
X3 ≥ 40
Quadro 2 - Modelo modificado e adaptado.
MAX Z = 10X1 + 15X2 + 12X3
MIN W = 
s.a.
0,75X1 + X2 + 1,5X3 + X4 = 160
X + X = 35
18 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
X2 + X5 = 35
X3 - X6 + T1 = 40
X1, X2, X3 ≥ 0
X4, X5, X6 ≥ 0
T1 ≥ 0
FASE 1
EXEMPLO
MÉTODO DAS DUAS FASES
x1 Lado 
direito
Coeficientes
E.q. x3 x4Variável
Básica
x5x2 x6 T1
19 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
Resolução Tabular : O Método Simplex In: PASSOS, E. J. P. F.
REFERÊNCIAS BIBLIOGRÁFICAS
Leitura obrigatória
Resolução Tabular : O Método Simplex In: PASSOS, E. J. P. F.
Programação Linear como Instrumento da Pesquisa Operacional.
São Paulo: Editora Atlas, 2008 - capítulo 4.
Problemas de Programação Linear – Problemas de Forma Não-Padrão
Leitura complementar
20 Unidade 5 – Programação Linear – Forma Não-Padrão Profª MsC. Andressa Azevedo
Problemas de Programação Linear – Problemas de Forma Não-Padrão
In: LACHTERMACHER, G. Pesquisa Operacional na Tomada de
Decisão. Rio de Janeiro: Editora Elsevier, 2007 - capítulo 2.5.