Programação Linear Solução Inicial Básica Viável-2022-1

08 Programação Linear – Solução Inicial Básica Viável © 2022 Prof. Sérgio F. Mayerle 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 2 of 12  Método das duas fases  Exemplo 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 3 of 12 Método das Duas Fases Seja o PPL genérico em sua forma padrão, denominado de P1, onde ib  0 , i  , para o qual não é possível obter uma solução básica inicial trivial: 1 1 . : 1,..., 0 1,..., (P1) (1.a) (1.b) (1.c) n j j j n ij j i j j Max z c x s a a x b i m x j n            Então, sempre é possível construir o PPL abaixo, denominado de P2, incluindo variáveis artificiais ( id ): 1 1 . : 1,..., 0 1,..., 0 1,..., (P2) (2.a) (2.b) (2.c) (2.d) n j j j n ij j i i j j i Max z c x s a a x d b i m x j n d i m                O problema P2 sempre tem uma solução básica viável trivial, como segue: 1,..., 0 1,..., (3.a) (3.b) i i j d b i m x j n       Para garantir a equivalência entre os problemas P1 e P2, é necessário que: 0 1,..., P1 P2 (4) id i m      Considere o PPL abaixo, denominado de P3: 1 1 . : 1,..., 0 1,..., 0 1,..., (P3) (5.a) (5.b) (5.c) (5.d) m i i n ij j i i j j i Min w d s a a x d b i m x j n d i m                08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 4 of 12 Então:  toda solução de P3 é também solução de P2;  se a solução ótima de P3 tiver w  0 , então também será uma solução básica viável para o P1. Algoritmo 1. Se P1 tem solução básica viável trivial, vá para 4; 2. Formule P3, e resolva-o; 3. Se na solução ótima de P3 as variáveis artificiais forem nulas, então uma solução básica viável para P1 foi encontrada; vá para 4. Em caso contrário, PARE; P1 não tem solução viável; 4. Resolva P1, considerando a solução básica viável conhecida. 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 5 of 12 Exemplo 01 (Forma Matricial) Seja o PPL: 1 2 3 1 2 3 1 2 3 1 2 3 3 2 4 . : 2 1 3 60 3 3 5 120 , , 0 (P1) Min z x x x s a x x x x x x x x x           Construindo a forma equivalente com a inclusão das variáveis de folga e as variáveis artificiais, além de transformar o problema em maximização, tem-se: 1 2 3 1 2 3 1 1 2 3 2 2 1 2 3 2 1 2 ( ) 3 2 4 . : 2 1 3 60 3 3 5 120 , , , , , 0 (P2) Max z z x x x s a x x x d x x x S d x x x S d d                  Substituindo a função objetivo original por uma função que minimiza a soma das variáveis artificiais, tem-se: 1 2 1 2 3 1 1 2 3 2 2 1 2 3 2 1 2 ( ) 1 1 . : 2 1 3 60 3 3 5 120 , , , , , 0 (P3) Max w w d d s a x x x d x x x S d x x x S d d                 Resolvendo o problema P3, obtém-se a seguinte solução ótima: 1 2 1 2 , , , , 0 w d d x S   2 , 3 x x 15 (* Sugestão: encontre este resultado) Note-se que esta solução atende às condições de viabilidade de P2 e, também, apresenta valor nulo para as variáveis artificiais. 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 6 of 12 Usando esta solução básica como solução inicial de P2, e excluindo as variáveis artificiais do problema, tem-se: 1 2 3 1 2 3 1 2 3 2 1 2 3 2 3 2 4 . : 2 1 3 60 3 3 5 120 , , , 0 (P2) Max z x x x s a x x x x x x S x x x S              ou, na forma matricial:   1 2 3 2 1 1 2 2 3 3 2 2 3 2 4 0 0 2 1 3 0 60 0 . : , 3 3 5 1 120 0 0 (P2) x x Max z x S x x x x s a x x S S                                                                     Particionando o problema de acordo com a solução de P3:     2 1 3 2 1 60 0 0 120 0 0 1 3 5/ 4 3/ 4 2 0 3 5 3/ 4 1/ 4 3 1 2 4 3 0 R B T T B R x x b x x x S B B R c c                                                                  Determinando a solução:   1 2 2 1 3 0 ˆ 0 5/ 4 3/ 4 60 15 ˆ 3/ 4 1/ 4 120 15 15 ˆ ˆ 2 4 90 90 15 R B T B B x x S x x B b x z c x z                                                             08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 7 of 12 Condição de otimalidade       1 5/ 4 3/ 4 2 0 2 4 3 0 3/ 4 1/ 4 3 1 1/ 2 1/ 2 T T B R z c B R c z z                           Logo, a solução atual é ótima. A tabela a seguir resume os resultados obtidos. Resultado Variável Valor z  1x 0 1/2 2x 15 0 3x 15 0 2 S 0 1/2 z 90 1 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 8 of 12 Exemplo 02 (Forma Tableau) Seja o PPL abaixo, sem solução inicial básica viável: 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 . : 5 4 6 12 2 15 3 18 , , 0 Max s a z x x x x x x x x x x x x x x x              Não havendo uma solução inicial básica viável trivial, utiliza-se o método das duas fases. Montando o problema na forma padrão estendida, tem-se: 1 3 1 1 2 3 3 1 2 3 1 1 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 . : 1 1 1 , , , , , , 5 4 6 12 2 15 3 18 , , 0 Max d Max s a S d S S d S S S S d d w d z x x x x x x x x x x x x x x x                      onde na primeira fase maximiza-se a variável w e na segunda fase a variável z. Usando a primeira e a terceira restrição para anular as variáveis 1d e 3d na função objetivo da primeira fase, tem-se o seguinte sistema: Maxw Maxz Sujeito a: 1 1 2 3 3 1 2 3 1 3 1 2 3 1 2 3 1 2 3 1 2 3 0 4 30 12 2 15 3 18 5 4 6 2 2 S d S S d x S S x x x x x x x x x z x x x w x x                                  1 2 3 1 3 1 2 3, , , , , , , 0 x x x S S S d d  08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 9 of 12 Construindo o tableau: Base w z x1 x2 x3 S1 S2 S3 d1 d3 RHS Razão d1 0 0 1 1 1 -1 0 0 1 0 12 12 S2 0 0 2 1 1 0 1 0 0 0 15 15 d3 0 0 1 1 3 0 0 -1 0 1 18 6 ◄ z 0 1 -5 -4 -6 0 0 0 0 0 0 w 1 0 -2 -2 -4 1 0 1 0 0 -30 ▲ Base w z x1 x2 x3 S1 S2 S3 d1 d3 RHS Razão d1 0 0 0,6667 0,6667 0 -1 0 0,3333 1 -0,333 6 9 S2 0 0 1,6667 0,6667 0 0 1 0,3333 0 -0,333 9 5,4 ◄ x3 0 0 0,3333 0,3333 1 0 0 -0,333 0 0,3333 6 18 z 0 1 -3 -2 0 0 0 -2 0 2 36 w 1 0 -0,667 -0,667 0 1 0 -0,333 0 1,3333 -6 ▲ Base w z x1 x2 x3 S1 S2 S3 d1 d3 RHS Razão d1 0 0 0 0,4 0 -1 -0,4 0,2 1 -0,2 2,4 6 ◄ x1 0 0 1 0,4 0 0 0,6 0,2 0 -0,2 5,4 13,5 x3 0 0 0 0,2 1 0 -0,2 -0,4 0 0,4 4,2 21 z 0 1 0 -0,8 0 0 1,8 -1,4 0 1,4 52,2 w 1 0 0 -0,4 0 1 0,4 -0,2 0 1,2 -2,4 ▲ 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 10 of 12 Base w z x1 x2 x3 S1 S2 S3 d1 d3 RHS x2 0 0 0 1 0 -2,5 -1 0,5 2,5 -0,5 6 x1 0 0 1 0 0 1 1 0 -1 0 3 x3 0 0 0 0 1 0,5 0 -0,5 -0,5 0,5 3 z 0 1 0 0 0 -2 1 -1 2 1 57 w 1 0 0 0 0 0 0 0 1 1 0 A solução encontrada para a primeira fase é ótima. Todas as variáveis artificiais ( 1d , 3d e w) foram anuladas. Portanto esta solução atende às restrições do problema original. Eliminando as colunas das variáveis artificiais, bem como a equação artificial, fica: Base z x1 x2 x3 S1 S2 S3 RHS Razão x2 0 0 1 0 -2,5 -1 0,5 6 ? x1 0 1 0 0 1 1 0 3 3 ◄ x3 0 0 0 1 0,5 0 -0,5 3 6 z 1 0 0 0 -2 1 -1 57 ▲ Base z x1 x2 x3 S1 S2 S3 RHS Razão x2 0 2,5 1 0 0 1,5 0,5 13,5 27 ◄ S1 0 1 0 0 1 1 0 3 ? x3 0 -0,5 0 1 0 -0,5 -0,5 1,5 ? z 1 2 0 0 0 3 -1 63 ▲ 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 11 of 12 Base z x1 x2 x3 S1 S2 S3 RHS S3 0 5 2 0 0 3 1 27 S1 0 1 0 0 1 1 0 3 x3 0 2 1 1 0 1 0 15 z 1 7 2 0 0 6 0 90 Solução ótima Encontrada a solução ótima, através do método Simplex duas fases, tem-se como solução ótima. Variável Valor z  1x 0 7 2x 0 2 3x 15 0 1S 3 0 2 S 0 6 3 S 27 0 Z 90 0 08 Programação Linear – Solução Inicial Básica Viável EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 12 of 12 F I M (© 2022 Prof. Sérgio Mayerle)