flowchart LR
A{A origem é solução viável?} -->|Sim| B
A -->|Não| C[Use o método Simplex Duas Fases]
B[Procure por outro vértice] --> H
H{Encontrou novo vértice?} -->|Sim| D
H --> |Não| I
D{O vértice é ótimo?} -->|Sim| E
D --> |Não| B
E[PARE! Solução Ótima!]
I[PARE! Não há Solução Ótima!]
Pesquisa Operacional - PEOP
AULA 26: RESOLVENDO PROBLEMAS LINEARES POR MEIO DO MÉTODO SIMPLEX
Profa. Luciane Alcoforado / Profa. Renata
Academia da Força Aérea
Objetivos
Verifique ao final desta aula se você é capaz de:
1- Estruturar um modelo matemático na forma matricial (Ap); 2- Colocar o modelo na forma padrão (Ap); 3- Compreender a lógica do Algoritmo Simplex (Cp)
Roteiro da Aula
- Revisão de conceitos das aulas anteriores
- A lógica do Algoritmo Simplex
- Particionamento
- Primeira Iteração do Simplex
- Exercícios.
Revisão de conceitos
Escolha a alternativa correta
1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa. Caso seja FALSA, identifique e corrija o erro.
Um modelo matemático na forma padrão é sempre de minimização.
Modelos que possuem restrições na forma \(A\cdot x \leq b\) tem como vértice natural o vetor \(x=0\).
A restrição \(5x_1-4x_2\geq 10\) na forma padrão será reescrita como \(5x_1-4x_2 +x_3 = 10\).
A função objetivo do modelo de programação linear expressa por min \(z= 8\cdot x_1+3\cdot x_2\), sujeito a 2 restrições, na forma padrão será expressa por \(max \space z=8\cdot x_1+3\cdot x_2+0\cdot x_3+0\cdot x_4\).
Suponha que \(x^T=(0,-2,0,5)\) seja solução do sistema \(A\cdot x = b\), com \(A_{2 \times 4}\) de um modelo de programação linear na forma padrão. Podemos afirmar esta solução é um vértice viável do modelo correspondente.
Confira sua resposta
1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa. Caso seja FALSA, identifique e corrija o erro.
Um modelo matemático na forma padrão é sempre de minimização. (V)
Modelos que possuem restrições na forma \(A\cdot x \leq b\) tem como vértice natural o vetor \(x=0\). (V)
A restrição \(5x_1-4x_2\geq 10\) na forma padrão será reescrita como \(5x_1-4x_2 +x_3 = 10\). (F) Correção: A restrição \(5x_1-4x_2\geq 10\) na forma padrão será reescrita como \(5x_1-4x_2 -x_3 = 10\).
A função objetivo do modelo de programação linear expressa por min \(z= 8\cdot x_1+3\cdot x_2\), sujeito a 2 restrições, na forma padrão será expressa por \(max \space z=8\cdot x_1+3\cdot x_2+0\cdot x_3+0\cdot x_4\). (F) Correção: A função objetivo do modelo de programação linear expressa por min \(z= 8\cdot x_1+3\cdot x_2\), sujeito a 2 restrições, na forma padrão será expressa por \(min \space z=8\cdot x_1+3\cdot x_2+0\cdot x_3+0\cdot x_4\).
Suponha que \(x^T=(0,-2,0,5)\) seja solução do sistema \(A\cdot x = b\), com \(A_{2 \times 4}\) de um modelo de programação linear na forma padrão. Podemos afirmar esta solução é um vértice viável do modelo correspondente. (F) Correção: Suponha que \(x^T=(0,-2,0,5)\) seja solução do sistema \(A\cdot x = b\), com \(A_{2 \times 4}\) de um modelo de programação linear na forma padrão. Podemos afirmar esta solução é um vértice, mas NÃO é viável, pois \(x_2=-2\) não atende a restrição de sinal.
A lógica do algoritmo Simplex
Considerando que o problema esteja na forma padrão, os passos do algoritmo são:
1- Encontrar uma solução factível inicial. A fim de garantir a factibilidade dessa solução, o método simplex parte sempre da origem dos eixos coordenados.
2- A estratégia simplex prevê a busca nos vértices da região de factibilidade afinal se existe solução ótima existe também um vértice ótimo.
3- Se for possível o simplex parte de um vértice factível em direção a outro melhor e assim sucessivamente, buscando sempre encontrar um vértice ótimo.
4- A busca é interrompida quando:
- a solução ótima é encontrada ou
- o método simplex verificar que o modelo não apresenta solução ótima.
Esquematicamente
Particionamento dos elementos matriciais
Considere um problema de minimização com \(n'\) variáveis de decisão, \(m\) restrições do tipo \(\le\) e portanto \(m\) variáveis de folga. O número total de variáveis do problema na forma padrão será \(n=n'+m\)
Sempre que iniciamos uma iteração realizamos um particionamento dos elementos matriciais de tal forma que teremos uma parte denominada básica e outra parte denominada não básica. Este particionamento está associado ao fato de que um vértice possui \(n'\) posições nulas, logo \[x_N^T= \begin{matrix} \underbrace{(0,...,0) \space}_{n'} \end{matrix} \]
Contadores Simplex
O particionamento é guiado pelos índices (contadores Simplex):
\(I_N\) = índices dos elementos da partição não básica.
\(I_B\) = índices dos elementos da partição básica.
\(I_N\cup I_B=\{1,2,...,n\}\)
Particionamento Inicial
Na primeira iteração do Simplex, o particionamento é realizado, considerando a origem como primeiro vértice viável. Assim:
\(I_N = \{1,2,\dots,n'\}\) e \(I_B = \{n'+1, \dots, n\}\) em que \(n=n'+m\)
O vetor de custos será particionado em \(c^T=[c^T_B |\space c^T_N]\). O vetor \(x\) será particionado em \(x^T=[x^T_B |\space x^T_N]\). A matriz \(A\) será particionada em \(A=[B |\space N]\).
Tal que:
\(c_B^T=(0,...,0)\) e \(c_N^T=(c_{1},...,c_{n'})\)
\[x_B= \begin{bmatrix} x_{n'+1} \\ ... \\ x_{n} \end{bmatrix} \]
\[x_N= \begin{bmatrix} x_{1} \\ ... \\ x_{n'} \end{bmatrix} \]
\[B=I= \begin{bmatrix} 1 &... & 0 \\ \vdots & \ddots & \vdots\\ 0 &... & 1 \end{bmatrix} \]
\[N= \begin{bmatrix} a_{11} &... & a_{1n'} \\ ... & ... & ...\\ a_{m1} &... & a_{mn'} \end{bmatrix} \]
Exemplo de Particionamento
\(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\)
Suponha o particionamento inicial \(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)\)
\[x_B= \begin{bmatrix} x_{3} \\ x_{4} \\ x_{5} \end{bmatrix} \]
\[x_N= \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \]
\[B= \begin{bmatrix} a_{13} &a_{14} & a_{15} \\ a_{23} &a_{24} & a_{25} \\ a_{33} &a_{34} & a_{35} \end{bmatrix} \]
\[B= \begin{bmatrix} 1 &0 & 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 3 \\ -3 & 4 \\ 0 & 1 \end{bmatrix} \]
Treine o particionamento inicial no aplicativo
https://lucianefalcoforado.shinyapps.io/Simplex_Formas/
Considere
\(max\) \(z=-8x_1+x_2+x_3\)
Sujeito a:
\(x_1+0x_2+x_3\leq 2\)
\(4x_1+4x_2+x_3\leq 4\)
\(x_1,x_2,x_3\ge0\)
Coloque-o na forma padrão e apresente o particionamento inicial do método Simplex.
A primeira iteração: SOLUÇÃO CORRENTE
1- Sempre que as restrições do problema forem do tipo \(\le\), a origem é uma solução viável, ou seja, \(x_1=x_2=...=x_n'=0\). O primeiro particionamento será:
\(I_N=\{1,2,...,n'\}\) e \(I_B=\{n'+1,n'+2, ..., n\}\)
Para obtermos a solução corrente desse particionamento resolvemos o sistema \(B\cdot x_B=b \rightarrow I\cdot x_B=b\) ou seja \(x_B=b\) e \(x_N=\overrightarrow{0}\).
As variáveis não básicas são sempre NULAS
Em Qualquer iteração
1- Obter a solução corrente, resolva:
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
Em Qualquer iteração
2- Calcular o custo relativo e verificar a regra de otimalidade \(c'_{i}>0 \space \forall i\in I_N\)
\(c'_{i}=c_{i}-\lambda^T \cdot a_{i}, i\in I_N\)
\(\lambda = B^{T^-1}c_B\)
Em Qualquer iteração
3- Se a regra de otimalidade foi atingida a solução corrente é ótima. Caso contrário devemos realizar a troca da base para obtermos um novo vértice:
Entra na base a variável não básica com o menor custo relativo. Chamaremos seu índice de \(k\) em que \(k \in I_N\)
Sai da base a variável básica com o menor tamanho de passo. Chamaremos seu índice de \(s\) em que \(s \in I_B\)
Em Qualquer iteração
Obtendo o tamanho de passo
- Calculamos a direção simplex \(y\)
\(y=B^{-1}a_k\)
- Calculamos o tamanho de passo \(\epsilon\)
\(\epsilon_z=x_{z}/y_z, z \in I_B\)
Regra de Parada: Não Existe \(\epsilon>0\)? PARE! Não há solução ótima.
Caso contrário, a variável básica com o menor \(\epsilon>0\) deixará a base. Chamaremos seu índice de \(s\) em que \(s \in I_B\).
Atualizando os contadores Simplex
Os novos contadores serão atualizados, considerando tal mudança e nova iteração será iniciada com \(I_N=\{1,2,...,n'\}-\{k\}\cup \{s\}\) e \(I_B=\{n'+1,n'+2, ..., m\}-\{s\}\cup \{k\}\)
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)\)
\(x_B=\) \[ \begin{bmatrix} x_{3} \\ x_{4} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{13} &a_{14} & a_{15} \\ a_{23} &a_{24} & a_{25} \\ a_{33} &a_{34} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1 &0 & 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 3 \\ -3 & 4 \\ 0 & 1 \end{bmatrix} \]
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 [,1]
x3 2
x4 5
x5 2A 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\)
[,1]
[1,] 0
[2,] 0
[3,] 0cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -3 -4Os 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 \(c'_N=\) (-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_{k}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\) e \(c'_N=\) (-3, -4) e \(\epsilon=\) (0.6666667, 1.25, 2)
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_{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\}\)
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)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{4} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{3} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{14} & a_{15} \\ a_{22} &a_{24} & a_{25} \\ a_{32} &a_{34} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 &0 & 0 \\ 4 &1 & 0 \\ 1 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 1 \\ -3 & 0 \\ 0 & 0 \end{bmatrix} \]
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}\).
a2 a4 a5
[1,] 3 0 0
[2,] 4 1 0
[3,] 1 0 1 [,1]
x2 0.6666667
x4 2.3333333
x5 1.3333333A 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'_{i}>0 \space \forall i\in I_N\)?
\(c'_{i}=c_{i}-\lambda^T a_{i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] -1.333333
[2,] 0.000000
[3,] 0.000000cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -9.666667 1.333333Os custos relativos são negativos, logo a solução corrente não é ótima.
## Obtendo um novo vértice {.smaller .scrollable}
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(c'_N=\) (-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_{k}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(c'_N=\) (-9.6666667, 1.3333333) e \(\epsilon=\) (-0.4, 0.6363636, 0.8)
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_{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\}\)
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)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{1} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_{3} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{11} & a_{15} \\ a_{22} &a_{21} & a_{25} \\ a_{32} &a_{31} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 & -5 &0 \\ 4 & -3 &0 \\ 1 & 1 &1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ 0 & 0 \end{bmatrix} \]
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}\).
a2 a1 a5
[1,] 3 -5 0
[2,] 4 -3 0
[3,] 1 0 1 [,1]
x2 1.7272727
x1 0.6363636
x5 0.2727273A 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'_{i}>0 \space \forall i\in I_N\)?
\(c'_{i}=C_{i}-\lambda^T a_{-i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] 2.181818
[2,] -2.636364
[3,] 0.000000cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] 2.636364 -2.181818Os 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 \(c'_N=\) (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_{k}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\) e \(c'_N=\) (2.6363636, -2.1818182) e \(\epsilon=\) (-6.3333333, -1.75, 1)
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_{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\}-\{I_{B_s}\}\cup \{I_{N_k}\}\)
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)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{1} \\ x_{3} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_{5} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{11} & a_{13} \\ a_{22} &a_{21} & a_{23} \\ a_{32} &a_{31} & a_{33} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 & -5 &1 \\ 4 & -3 &0 \\ 1 & 1 &0 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \]
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}\).
a2 a1 a3
[1,] 3 -5 1
[2,] 4 -3 0
[3,] 1 0 0 [,1]
x2 2
x1 1
x3 1A 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\)
[,1]
[1,] 0
[2,] 1
[3,] -8cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -1 8Os 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 \(c'_N=\) (-1, 8)
O menor custo relativo é -1 e corresponde a \(k=\) 4. Logo a variável não básica k, \(x_{k}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\) e \(c'_N=\) ( -1, 8) e \(\epsilon=\) (\(\infty\), -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.
Faça os exercícios propostos no moodle.
