Lembrete: O primeiro passo do Simplex

Reescrever o problema na forma padrão:

• Função objetivo deve ser de minimização

• As restrições devem estar na forma \(Ax=b\)

• Os vetores \(x\) e \(b\) devem ser positivos.

Exercício 1: Solução Gráfica

Indique a solução ótima com base no gráfico.

O problema possui infinitas soluções ótimas pois a região viável é formada pelo polígono ABCD, tal que \(A=(0,0), B=(0,3), C=(1.82, 4.09), D=(10,0)\). O vetor gradiente aponta para a direção da aresta CD, sendo que esta aresta é paralela a curva de nível \(z=10\). Assim qualquer ponto sobre esta aresta será uma solução ótima e há dois vértices ótimos o C e o D.

Exercício 2: Solução via algoritmo simplex

Considere o problema anterior que foi resolvido pelo método gráfico. Obtenha a solução pelo método simplex, mostrando o passo e passo do algoritmo, ou seja, todas as iterações até a regra de parada.

iteração 1: \(I_N=\{1,2\}\) e \(I_B=\{3,4\}\)

A=cbind(a1=c(-6,1), a2=c(10,2), a3=c(1,0), a4=c(0,1))
ct=c(-1,-2,0,0)
b=c(30,10)
IN=c(1,2);IB=c(3,4)
B=A[,IB];B

     a3 a4
[1,]  1  0
[2,]  0  1

xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))

x=rep(0,length(IN)+length(IB))
j=1
for (i in IB){
x[i]=xB[j]
j=j+1}


cB=ct[IB]; cN=ct[IN]
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,]    0
[2,]    0

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo #analise

[1] -1 -2

k=which.min(cN_relativo)
k #posicao que entra na base

[1] 2

IN[k] #indice da variável q entra

[1] 2

A[,IN[k]]

[1] 10  2

y = solve(B)%*%A[,IN[k]]
y

   [,1]
a3   10
a4    2

xB

   [,1]
x3   30
x4   10

e=xB/y
e #analise

   [,1]
x3    3
x4    5

minimo = min(e[e>0])
s=which(e == minimo)
s #posicao que sai da base

[1] 1

IB[s] #indice da variável que sai da base

[1] 3

A solução corrente será \(x=(\) 0, 0, 30, 10) e não é ótima pois o vetor \(C_N\) não é positivo. Entra na base \(x_2\) e sai da base \(x_3\).

Iteração 2

iteração 2: \(I_N=\{1,3\}\) e \(I_B=\{2,4\}\)

IN=c(1,3);IB=c(2,4)
B=A[,IB];B

     a2 a4
[1,] 10  0
[2,]  2  1

xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))

x=rep(0,length(IN)+length(IB))
j=1
for (i in IB){
x[i]=xB[j]
j=j+1}


cB=ct[IB]; cN=ct[IN]
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,] -0.2
[2,]  0.0

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo #analise

[1] -2.2  0.2

k=which.min(cN_relativo)
k #posicao que entra na base

[1] 1

IN[k] #indice da variável q entra

[1] 1

A[,IN[k]]

[1] -6  1

y = solve(B)%*%A[,IN[k]]
y

   [,1]
a2 -0.6
a4  2.2

xB

   [,1]
x2    3
x4    4

e=xB/y
e #analise

        [,1]
x2 -5.000000
x4  1.818182

minimo = min(e[e>0])
s=which(e == minimo)
s #posicao que sai da base

[1] 2

IB[s] #indice da variável que sai da base

[1] 4

A solução corrente será \(x=(\) 0, 3, 0, 4) e não é ótima pois o vetor \(C_N\) não é positivo. Entra na base \(x_1\) e sai da base \(x_4\).

Iteração 3

iteração 3: \(I_N=\{4,3\}\) e \(I_B=\{2,1\}\)

IN=c(4,3);IB=c(2,1)
B=A[,IB];B

     a2 a1
[1,] 10 -6
[2,]  2  1

xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))

x=rep(0,length(IN)+length(IB))
j=1
for (i in IB){
x[i]=xB[j]
j=j+1}


cB=ct[IB]; cN=ct[IN]
lambda = solve(t(B))%*%cB
lambda

              [,1]
[1,]  1.387779e-17
[2,] -1.000000e+00

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo #analise

[1]  1.000000e+00 -1.387779e-17

k=which.min(cN_relativo)
k #posicao que entra na base

[1] 2

IN[k] #indice da variável q entra

[1] 3

A[,IN[k]]

[1] 1 0

y = solve(B)%*%A[,IN[k]]
y

          [,1]
a2  0.04545455
a1 -0.09090909

xB

       [,1]
x2 4.090909
x1 1.818182

e=xB/y
e #analise

   [,1]
x2   90
x1  -20

minimo = min(e[e>0])
s=which(e == minimo)
s #posicao que sai da base

[1] 1

IB[s] #indice da variável que sai da base

[1] 2

A solução corrente será \(x=(\) 1.82, 4.09, 0, 0) e não é ótima pois o vetor \(C_N\) não é positivo. Entra na base \(x_3\) e sai da base \(x_2\).

Iteração 4

iteração 4: \(I_N=\{4,2\}\) e \(I_B=\{3,1\}\)

IN=c(4,2);IB=c(3,1)
B=A[,IB];B

     a3 a1
[1,]  1 -6
[2,]  0  1

xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))

x=rep(0,length(IN)+length(IB))
j=1
for (i in IB){
x[i]=xB[j]
j=j+1}


cB=ct[IB]; cN=ct[IN]
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,]    0
[2,]   -1

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo #analise

[1] 1 0

#solução ótima atingida!

A solução corrente será \(x=(\) 10, 0, 90, 0) e é ótima pois o vetor \(C_N\) é positivo. O valor ótimo na função objetivo será \(z=10\) (valor máximo), com variáveis de decisão ótima sendo \(x_1=10, x_2=0\).

Cabe observar que a solução da iteração 3 já era ótima pois CN apesar de negativo na segunda posição, é uma representação numérica do zero no ponto de vista computacional. Assim, um número com muitas casas decimais e negativo pode se aproximar do zero computacionalmente falando. Percebemos este fato pois fizemos a solução gráfica no exercício anterior.

Resolvendo um problema passo a passo

\(min\) \(z=-3x_1-4x_2+0x_3+0x_4+0x_5\)

Sujeito a:

\(-5x_1+3x_2+1x_3+0x_4+0x_5=2\)

\(-3x_1+4x_2+0x_3+1x_4+0x_5=5\)

\(0x_1+1x_2+0x_3+0x_4+1x_5=2\)

\(x_1,x_2,x_3,x_4,x_5\ge0\)

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)

Obtendo o particionamento

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)

O particionamento será:

\(c_B^T=(c_{3},c_{4},c_{5} )=(0,0,0)\) e \(c_N^T=(c_{1},c_{2})=(-3,-4)\)

Obtendo a solução corrente

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)

\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).

A=cbind(a1=c(-5,-3,0), a2=c(3,4,1), a3=c(1,0,0), a4=c(0,1,0), a5=c(0,0,1))
IN=c(1,2);IB=c(3,4,5)
B=A[,IB];B

     a3 a4 a5
[1,]  1  0  0
[2,]  0  1  0
[3,]  0  0  1

b=c(2,5,2)
xB = solve(B)%*%b
rownames(xB)<-(paste0("x",c(3,4,5)))
xB

   [,1]
x3    2
x4    5
x5    2

A solução corrente será \(x=(\) 0, 0, 2, 5, 2).

Verificando a otimalidade

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)

\(C'_{N_i}>0 \space \forall i\in I_N\)?

\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)

\(\lambda = B^{T^-1}c_B\)

IN=c(1,2);IB=c(3,4,5)
cB=c(0,0,0); cN=c(-3,-4)
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,]    0
[2,]    0
[3,]    0

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo

[1] -3 -4

Os custos relativos são negativos, logo a solução corrente não é ótima.

Obtendo um novo vértice

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\) e \(cN'=\) (-3, -4)

O menor custo relativo é -4 e corresponde a \(k=\) 2. Logo a variável não básica da posição 2 de \(I_N\), \(x_{IN_{k}}\) entra na base.

Obtendo o tamanho do passo:

k=which.min(cN_relativo)
B

     a3 a4 a5
[1,]  1  0  0
[2,]  0  1  0
[3,]  0  0  1

A[,IN[k]]

[1] 3 4 1

y = solve(B)%*%A[,IN[k]]
y

   [,1]
a3    3
a4    4
a5    1

xB

   [,1]
x3    2
x4    5
x5    2

e=xB/y
e

        [,1]
x3 0.6666667
x4 1.2500000
x5 2.0000000

Quem sai da base

1a. Iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\) e \(cN'=\) (-3, -4) e \(\epsilon=\) (0.6666667, 1.25, 2)

minimo = min(e[e>0])
s=which(e == minimo)
IB[s]

[1] 3

O menor tamanho de passo positivo é 0.6666667 e corresponde a \(s=\) 3. Logo a variável básica da posição 1 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.

Fim da primeira iteração com \(k=\) 2, \(s=\) 3,

\(I_N=\{1,2\}-\{k\}\cup \{s\}\) e \(I_B=\{3,4,5\}-\{s\}\cup \{k\}\)

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)

Segunda Iteração passo a passo

2a. Iteração

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)

O particionamento será:

\(c_B^T=(c_{2},c_{4},c_{5} )=(-4,0,0)\) e \(c_N^T=(c_{1},c_{3})=(-3,0)\)

Obtendo a solução corrente

2a. Iteração

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)

\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).

IN=c(1,3); IB=c(2,4,5)
B=A[,IB];B

     a2 a4 a5
[1,]  3  0  0
[2,]  4  1  0
[3,]  1  0  1

b=c(2,5,2)
xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))
xB

        [,1]
x2 0.6666667
x4 2.3333333
x5 1.3333333

A solução corrente será \(x=(\) 0, 0.67, 0, 2.33, 1.33).

Verificando a otimalidade

2a. Iteração

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)

\(C'_{N_i}>0 \space \forall i\in I_N\)?

\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)

\(\lambda = B^{T^-1}c_B\)

cB=c(-4,0,0)
cN=c(-3,0)
lambda = solve(t(B))%*%cB
lambda

          [,1]
[1,] -1.333333
[2,]  0.000000
[3,]  0.000000

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo

[1] -9.666667  1.333333

Os custos relativos são negativos, logo a solução corrente não é ótima.

Obtendo um novo vértice

2a. Iteração

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(cN'=\) (-9.6666667, 1.3333333)

O menor custo relativo é -9.6666667 e corresponde a \(k=\) 1. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.

Obtendo o tamanho do passo:

k=which.min(cN_relativo)
B

     a2 a4 a5
[1,]  3  0  0
[2,]  4  1  0
[3,]  1  0  1

A[,IN[k]]

[1] -5 -3  0

y = solve(B)%*%A[,IN[k]]
y

        [,1]
a2 -1.666667
a4  3.666667
a5  1.666667

xB

        [,1]
x2 0.6666667
x4 2.3333333
x5 1.3333333

e=xB/y
e

         [,1]
x2 -0.4000000
x4  0.6363636
x5  0.8000000

Quem sai da base

2a. Iteração

\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(cN'=\) (-9.6666667, 1.3333333) e \(\epsilon=\) (-0.4, 0.6363636, 0.8)

minimo = min(e[e>0])
s=which(e == minimo)
IB[s]

[1] 4

O menor tamanho de passo positivo é 0.6363636 e corresponde a \(s=\) 4. Logo a variável básica da posição 2 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.

Fim da segunda iteração com \(k=\) 1, \(s=\) 4,

\(I_N=\{1,3\}-\{k\}\cup \{s\}\) e \(I_B=\{2,4,5\}-\{s\}\cup \{k\}\)

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)

Terceira Iteração passo a passo

3a. Iteração

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)

O particionamento será:

\(c_B^T=(c_{2},c_{1},c_{5} )=(-4,-3,0)\) e \(c_N^T=(c_{4},c_{3})=(0,0)\)

Obtendo a solução corrente

3a. Iteração

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)

\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).

IN=c(4,3); IB=c(2,1,5)
B=A[,IB];B

     a2 a1 a5
[1,]  3 -5  0
[2,]  4 -3  0
[3,]  1  0  1

b=c(2,5,2)
xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))
xB

        [,1]
x2 1.7272727
x1 0.6363636
x5 0.2727273

A solução corrente será \(x=(\) 0.64, 1.73, 0, 0, 0.27).

Verificando a otimalidade

3a. Iteração

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)

\(C'_{N_i}>0 \space \forall i\in I_N\)?

\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)

\(\lambda = B^{T^-1}c_B\)

cB=c(-4,-3,0)
cN=c(0,0)
lambda = solve(t(B))%*%cB
lambda

          [,1]
[1,]  2.181818
[2,] -2.636364
[3,]  0.000000

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo

[1]  2.636364 -2.181818

Os custos relativos são negativos, logo a solução corrente não é ótima.

Obtendo um novo vértice

3a. Iteração

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\) e \(cN'=\) (2.6363636, -2.1818182)

O menor custo relativo é -2.1818182 e corresponde a \(k=\) 3. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.

Obtendo o tamanho do passo:

k=which.min(cN_relativo)
B

     a2 a1 a5
[1,]  3 -5  0
[2,]  4 -3  0
[3,]  1  0  1

A[,IN[k]]

[1] 1 0 0

y = solve(B)%*%A[,IN[k]]
y

         [,1]
a2 -0.2727273
a1 -0.3636364
a5  0.2727273

xB

        [,1]
x2 1.7272727
x1 0.6363636
x5 0.2727273

e=xB/y
e

        [,1]
x2 -6.333333
x1 -1.750000
x5  1.000000

Quem sai da base

3a. Iteração

\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\) e \(cN'=\) (2.6363636, -2.1818182) e \(\epsilon=\) (-6.3333333, -1.75, 1)

minimo = min(e[e>0])
s=which(e == minimo)
IB[s]

[1] 5

O menor tamanho de passo positivo é 1 e corresponde a \(s=\) 5. Logo a variável básica da posição 3 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.

Fim da segunda iteração com \(k=\) 3, \(s=\) 5,

\(I_N=\{4,3\}-\{k\}\cup \{s\}\) e \(I_B=\{2,1,5\}-\{s\}\cup \{k\}\)

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)

Quarta Iteração passo a passo

4a. Iteração

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)

O particionamento será:

\(c_B^T=(c_{2},c_{1},c_{3} )=(-4,-3,0)\) e \(c_N^T=(c_{4},c_{5})=(0,0)\)

Obtendo a solução corrente

4a. Iteração

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)

\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).

IN=c(4,5); IB=c(2,1,3)
B=A[,IB];B

     a2 a1 a3
[1,]  3 -5  1
[2,]  4 -3  0
[3,]  1  0  0

b=c(2,5,2)
xB = solve(B)%*%b
rownames(xB)<-(paste0("x",IB))
xB

   [,1]
x2    2
x1    1
x3    1

A solução corrente será \(x=(\) 1, 2, 1, 0, 0).

Verificando a otimalidade

4a. Iteração

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)

\(C'_{N_i}>0 \space \forall i\in I_N\)?

\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)

\(\lambda = B^{T^-1}c_B\)

cB=c(-4,-3,0)
cN=c(0,0)
lambda = solve(t(B))%*%cB
lambda

     [,1]
[1,]    0
[2,]    1
[3,]   -8

cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo

[1] -1  8

Os custos relativos são negativos, logo a solução corrente não é ótima.

Obtendo um novo vértice

4a. Iteração

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\) e \(cN'=\) (-1, 8)

O menor custo relativo é -1 e corresponde a \(k=\) 4. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.

Obtendo o tamanho do passo:

k=which.min(cN_relativo)
B

     a2 a1 a3
[1,]  3 -5  1
[2,]  4 -3  0
[3,]  1  0  0

A[,IN[k]]

[1] 0 1 0

y = solve(B)%*%A[,IN[k]]
y

         [,1]
a2  0.0000000
a1 -0.3333333
a3 -1.6666667

xB

   [,1]
x2    2
x1    1
x3    1

e=xB/y
e

   [,1]
x2  Inf
x1 -3.0
x3 -0.6

Quem sai da base

4a. Iteração

\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\) e \(cN'=\) (-1, 8) e \(\epsilon=\) (, -3, -0.6)

Como não é possível obter um tamanho de passo positivo (note que o tamanho de \(\epsilon_1 \rightarrow \infty\) indica uma direção de crescimento ilimitado),este fato indica que a solução é ilimitada e portanto não é possível obter um valor ótimo.

Fim da quarta iteração , o problema não tem solução ótima, apenas soluções viáveis.

Revise

• Terminou? Revise os conceitos desta aula.

• Verifique se permanece alguma dúvida sobre como representar matricialmente um problema e colocá-lo na forma padrão.