Obtendo uma solu ção básica factível inicial

Método Simplex duas fases

Base inicial – FASE I

• Como determinar uma partição básica factível inicial (A=(B, N)).

• Algumas classes de problemas de otimização linear oferecem naturalmente a solução básica factível

Minimizar f(x) = cTx

sujeito a: Ax ≤ b

x ≥ 0

em que b ≥ 0.

Base inicial – FASE IMinimizar f(x) = cTx

sujeito a: Ax ≤ b

x ≥ 0

em que b ≥ 0.

Após a introdução das variáveis de folga, digamos, xf, temos:

Minimizar f(x) = cTx

sujeito a: Ax + xf = b

x ≥ 0, xf ≥ 0,

A matriz dos coeficientes das restrições agora é dada por [A I] euma partição básica factível é dada por:

• B = I : as variáveis básicas são as variáveis de folga xB = xf

• N = A: as variáveis não-básicas são as variáveis originais xN = x,

e a solução básica factível é dada por:

==

≥==

.

,

0xx

0bxx

N

B f

• Suponha agora que as restrições são, originalmente, de igualdade:

• Precisamos encontrar uma partição básica factível de A, isto é, uma partição da forma:

tal que existe e

Base inicial – FASE I

Quantas partiçõ es existem ?

• Tome A10 x 20

Precisamos identificar dez colunas L.I. de A para formar B, e o sistema Bxb = b, tem que ter xB ≥ 0.

• Procedimento possível:– 1. Escolher dez (m) colunas– 2. Verificar se xB ≥0.

– 3. Se não, escolher outras dez colunas e retornar ao passo 2.

Quantas poss íveis parti ções existem ?

• Se formos testar partição a partição, quantos testes temos que fazer ?

impraticável para problemasgrandes!

Introduzindo novas vari áveis de folga

• Quando tínhamos variáveis de folga, funcionava, pois:

• Se não for o caso, podemos forçar variáveis de folga:

uma partição [I N] onde as variáveis de folga começam como as variáveis básicas.

Fase I

• Obviamente, essas variáveis não podem aparecer na solução final (pois elas não existem - são variáveis artificiais).

• Método duas-fases: resolvemos primeiro um problema:

Fase I

• Se conseguimos uma solução de custo zero para o problema acima (fase I), a base final não contém nenhuma variável artificial (por quê ?)

• Neste caso, a base final do problema da fase I éuma base inicial para o problema real (fase II).

Fase I

• E se não conseguimos uma solução de custo zero ? (Isto é, na solução ótima da fase I, existe uma variável artificial na base).

(Não existe solução factível para o nosso problema)

Exemplo

Forma padrão

Qual o problema da fase I a resolver ?

• Caso A: introduzimos uma variável artificial pra cada restrição:

e minimizamos o custo destas variáveis.

Qual o problema da fase I a resolver ?

• Caso B: note que x4 já fornece uma coluna da matriz identidade. Assim, a rigor, precisamos apenas de uma variável artificial:

e minimizamos o custo desta variável.

Exemplo

Obtenha a solução do problema original.

Outra possibilidade

• Em vez de resolver um problema auxiliar (fase I) para encontrar a base, simplesmente penalizamos as variáveis artificiais no problema original (fase II), de modo a garantir que elas sejam nulas na solução ótima:

valor suficientemente grande para garantir que xvalor suficientemente grande para garantir que x55 nnãão aparece na soluo aparece na soluçãção o óótima.tima.

Considere o Exemplo

3,2,1i,0x

4x3xx

3xxx

x2xxf

i

321

321

321

=≥≤+−=+++−=

2

:asujeito

)(minimizar x

4,...,1i,0x

4xx3xx

3xxx

x0x2xxf

i

4321

321

4321

=≥=++−

=++++−=

2

:asujeito

)(minimizar x

Forma Padrão

Variável artificial apenas primeira restrição:Obter uma solução Inicial para o problema.

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:asujeito

)(minimizar

Exemplo

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar

Para resolver o problema artificial, aplicamos o método simplex.

Fase I: Partição básica factível inicial: 41 =B 52 =B 11 =N 22 =N

33 =N

=01

10B e

−=

312

111N

1a. Iteração

1. Solução básica:

Resolva o sistema bxB =Bˆ , cuja matriz aumentada é

4

3

01

10 e obtenha a

solução:

=

=

3

4

x

xˆ

5

4Bx

Exemplo

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar

1. Teste de otimalidade:

i) Vetor multiplicador: Resolva o sistema BT cλB = , cuja matriz aumentada

é

1

0

01

10 e obtenha

=0

1λ

ii) Custos relativos

11 =N : 1cc 1T

11 −=−= aλ ← 1Nx = x1 entra na base

22 =N : 1cc 2T

22 −=−= aλ

33 =N : 1cc 3T

33 −=−= aλ

Exemplo

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar

1. Direção simplex: Resolva o sistema 1aBy = , cuja matriz aumentada é

2

1

01

10 e obtenha y =

1

2

1. Tamanho do passo

1

Bi

i

B

y

x2

1

3,

2

4min0y

y

xmin 1i ==

=

>=ε (1Bx = x4 sai da base)

2. Atualização

1B1 = 5B2 = 4N1 = 2N2 = 3N3 =

=02

11B e

−=

311

110N

Exemplo

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar2a. Iteração: 1B1 = 5B2 = 4N1 = 2N2 = 3N3 =

1. Solução básica: Resolva o sistema bxB =Bˆ :

4

3

02

11 e obtenha

=1

2ˆ Bx

2. Teste de otimalidade

i) Vetor multiplicador: Resolva o sistema BT cλB = :

1

0

01

21 e obtenha

λλλλ =

− 21

1

ii) Custos relativos

4N1 = : 21

444 =−= aλTcc

22 =N : 23

222 −=−= aλTcc ← 2Nx = x2 entra na base

3N3 = : 31

3T

33 cc =−= aλ

Exemplo

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar

1. Direção simplex: resolva o sistema 2aBy = :

− 1

1

02

11 e obtenha

−=

2321

y

2. Tamanho do passo

2

B32

23i

i

B

y

x;

1min0y

y

xmin 2i ==

=

>=ε (2Bx = x5 sai da base - Variável

artificial )

1. Atualização:

1B1 = 2B2 = 41 =N 5N2 = 3N3 =

−=

12

11B

Fim da FASE I

Exemplo – FASE II

5,...,1i,0x

4xx3xx

3xxxx

xx,...,xf

i

4321

5321

551a

=≥=++−=+++

=

2

:a sujeito

)(minimizar

FASE I – Problema Artificial

Fase II: Aplicar o método simplex a partir da base obtida na Fase I. A variável

artificial (segunda variável não básica: N2 = 5) é descartada e os índices não

básicos são redefinidos: N1 = 4, N2 = 3. �

Exerc ício

Obtenha a uma base factível inicial do problema.

1 2

1 2

1 2

1 2

3 4

:

4

2 3 1 8

0 , 0

M i n i m i z e x x

s u j e i t o a

x x

x x

x x

− +

+ ≤+ ≥

≥ ≥