Pesquisa Operacional - PEOP
AULA 26: O MÉTODO SIMPLEX DUAS FASES
Profa. Luciane Alcoforado
Academia da Força Aérea
Objetivos
Verifique ao final desta aula se você é capaz de:
1- Identificar quando se deve usar o método duas fases (Cp); 2- Elaborar o modelo artificial (Ap); 3- Compreender a lógica do Algoritmo Simplex duas fases (Cp); 4- Aplicar o método duas fases (Ap)
Roteiro da Aula
- Revisão de conceitos das aulas anteriores
- Método Simplex duas fases
- Exercícios.
Revisão de conceitos
Lembretes
1- Antes de iniciar a aplicação do método simplex, coloque o problema na forma padrão.
2- Na forma padrão o problema é de minimização e todas as restrições estão na forma de igualdade.
3- Os contadores simplex da primeira iteração serão compostos por \(I_N=\{1,2,...,n'\}\) & \(I_B=\{n'+1,n'+2,...,n'+m\}\) sendo \(n'\) o número de variáveis de decisão originais e \(m\) o número de restrições.
4- Para obter a solução corrente de uma iteração resolva o sistema \(Bx_B=b\) e apresente o vetor \(x\) completo que deverá ter \(n'\) posições nulas de acordo com \(I_N\).
5- O algoritmo possui duas regras de parada, uma determina a condição de otimalidade do problema e outra indica que o problema não possui solução ótima.
6- Regra de parada 1: Verifica o critério de otimalidade testando a condição \(C´_{N_j}\ge0\) para \(j=1,...,n'\)
7- Regra de parada 2: Verifica que os tamanhos de passo são negativos ou tendem a infinito.
…
Origem não é solução viável
\(min\) \(z=-3x_1+x_2\)
Sujeito a:
\(1x_1+1x_2\ge6\)
\(1x_1-1x_2\le4\)
\(-1x_1+1x_2\le4\)
\(x_1,x_2\ge0\)
\(min\) \(z=-3x_1+1x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(1x_1+1x_2-1x_3+0x_4+0x_5=6\)
\(1x_1-1x_2+0x_3+1x_4+0x_5=4\)
\(-1x_1+1x_2+0x_3+0x_4+1x_5=4\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
Não se tem a matriz identidade embutida na matriz dos coeficientes:
\[ A=\begin{bmatrix} 1 & 1 & -1 & 0 & 0 \\ 1 &-1 & 0 & 1 & 0 \\ -1 &1 & 0 & 0 & 1 \\ \end{bmatrix} \]
Criando uma variável artificial
Restrições do tipo \(\ge\) \(\Rightarrow\) variável de excesso \(\Rightarrow\) variável artificial que denominaremos de \(x_{a_i}\).
\(1x_1+1x_2-1x_3+0x_4+0x_5+1x_{a_1}=6\)
\(1x_1-1x_2+0x_3+1x_4+0x_5+0x_{a_1}=4\)
\(-1x_1+1x_2+0x_3+0x_4+1x_5+0x_{a_1}=4\)
\(x_1,x_2,x_3,x_4,x_5,x_{a_1}\ge0\)
Esse artifício garantirá uma base inicial para um problema artificial da fase 1.
Fase 1: o problema artificial
Mantém a região viável do problema original e procura eliminar a variável artificial pois como \(x_{a_1}\ge0\), seu valor mínimo espera-se que seja zero.
A função objetivo na fase 1 é sempre de minimização das somas das variáveis artificiais.
\(min\) \(w_a= 0x_1+0x_2+0x_3+0x_4+0x_5+1x_{a_1}\)
Sujeito a:
\(1x_1+1x_2-1x_3+0x_4+0x_5+1x_{a_1}=6\)
\(1x_1-1x_2+0x_3+1x_4+0x_5+0x_{a_1}=4\)
\(-1x_1+1x_2+0x_3+0x_4+1x_5+0x_{a_1}=4\)
\(x_1,x_2,x_3,x_4,x_5,x_{a_1}\ge0\)
\(c^T=(0,0,0,0,0,1)\); \(x^T=(x_1,x_2,x_3,x_4,x_5,x_6=x_{a_1})\);
\(b^T=(6,4,4)\) e \[ A=\begin{bmatrix} 1 & 1 & -1 & 0 &0 &1 \\ 1 &-1 & 0 & 1 &0 &0 \\ -1 &1 & 0 & 0 &1 &0\\ \end{bmatrix} \]
Fase 1 x Fase 2
Cada fase possui uma função objetivo. As restrições serão as mesmas em ambas, exceto pelas variáveis artificiais, que não aparecem na fase 2. Vamos renomear \(x_{a1}\) como \(x_6\)
Fase 1
\(min\) \(0x_1+0x_2+0x_3+0x_4+0x_5+1x_{6}\)
Sujeito a:
\(1x_1+1x_2-1x_3+0x_4+0x_5+1x_{6}=6\)
\(1x_1-1x_2+0x_3+1x_4+0x_5+0x_{6}=4\)
\(-1x_1+1x_2+0x_3+0x_4+1x_5+0x_{6}=4\)
\(x_1,x_2,x_3,x_4,x_5,x_{6}\ge0\)
Fase 2
\(min\) \(-3x_1+1x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(1x_1+1x_2-1x_3+0x_4+0x_5=6\)
\(1x_1-1x_2+0x_3+1x_4+0x_5=4\)
\(-1x_1+1x_2+0x_3+0x_4+1x_5=4\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
Como funciona o método duas fases
Na fase 1, a origem é uma solução viável para minimizar a soma das variáveis artificiais. Aplica-se o método simplex normalmente até obter a solução ótima da fase 1.
Somente inicia-se a fase 2 se todas as variáveis artificiais forem não básicas, ou seja, todas nulas. Caso contrário concluímos que o problema da fase 2 não possui solução, é inviável.
Assim, quando terminamos a fase 1 com todas as variáveis artificiais fora da base, teremos um particionamento para iniciar a primeira iteração da fase 2, eliminando-se as variáveis artificiais do \(I_N\), mantendo-se apenas as variáveis de decisão e de folga/excesso. Note que em \(I_B\) não teremos variáveis artificiais.
Partição da Fase 1
Coloque em \(I_B\) as variável(is) artificial(is) e as de folga e em \(I_N\) as variáveis de decisão e as de excesso.
1a. Iteração
\(I_B=\{6,4,5\}\) & \(I_N=\{1,2,3\}\)
\(c_B^T=(c_{6},c_{4}, C_5 )=(1,0,0)\) e \(c_N^T=(c_{1},c_{2}, c_3)=(0,0,0)\) e \(b=(6,4,4)\)
\(x_B=\) \[ \begin{bmatrix} x_{6}\\ x_{4} \\ x_{5}\\ \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \\ x_3 \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1&0 & 0 \\ 0&1 & 0\\ 0&0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 1 & 1 & -1 \\ 1 & -1 &0 \\ -1 & 1 & 0 \end{bmatrix} \]
\(B\cdot x_B=b \rightarrow x_B^T=(6,4,4)\). A solução corrente será \(x^T=(\) 0, 0, 0, 4, 4, 6).
Fase 1 - iteração 1 Custos Relativos
\(I_B=\{6,4,5\}\) & \(I_N=\{1,2,3\}\) com \(k=1\) pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 1 & 0 & 0\\ 0 & 1& 0\\ 0 & 0& 1 \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ 0\\ 0\end{bmatrix}\]\(\lambda^T=(1,0,0)\)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_1=0-
\end{matrix}\begin{bmatrix}
1 & 0 & 0
\end{bmatrix}\begin{bmatrix}
1 \\
1 \\
-1
\end{bmatrix}\begin{matrix}
=-1
\end{matrix}\]
\[\begin{matrix}
C´_2=0-
\end{matrix}\begin{bmatrix}
1 & 0 & 0
\end{bmatrix}\begin{bmatrix}
1 \\
-1 \\
1
\end{bmatrix}\begin{matrix}
=-1
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
1 & 0 & 0
\end{bmatrix}\begin{bmatrix}
-1 \\
0 \\
0
\end{bmatrix}\begin{matrix}
=1
\end{matrix}\]
Fase 1 - iteração 1 Tamanho de Passo
\(I_B=\{6,4,5\}\) & \(I_N=\{1,2,3\}\), \(k=1\) e \(s=4\) pois
Custos relativos \(B\cdot y=a_1\)
\[\begin{bmatrix} 1 & 0 & 0\\ 0 & 1& 0\\ 0 & 0& 1 \end{bmatrix} \cdot \begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ 1\\ -1\end{bmatrix}\]\(y^T=(1,1,-1)\)
\(\epsilon_i=\frac{x_{I_{B_i}}}{y_i}\)
\(\epsilon_1=\frac{x_{6}}{y_1}=\frac{6}{1}=6\)
\(\epsilon_2=\frac{x_{4}}{y_2}=\frac{4}{1}=4\)
\(\epsilon_3=\frac{x_{5}}{y_3}=\frac{4}{-1}=-4\)
Partição da Fase 1 - it.2
\(k=1,s=4\)
1a. Iteração
\(I_B=\{6,1,5\}\) & \(I_N=\{4,2,3\}\)
\(c_B^T=(c_{6},c_{1}, C_5 )=(1,0,0)\) e \(c_N^T=(c_{4},c_{2}, c_3)=(0,0,0)\) e \(b=(6,4,4)\)
\(x_B=\) \[ \begin{bmatrix} x_{6}\\ x_{1} \\ x_{5}\\ \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_{2} \\ x_3 \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1&1 & 0 \\ 0&1 & 0\\ 0&-1 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & 1 & -1 \\ 1 & -1 &0 \\ 0 & 1 & 0 \end{bmatrix} \]
\(B\cdot x_B=b \rightarrow x_B=(2,4,8)\), logo a Solução Corrente será \(x=(\) 4, 0, 0, 0, 8, 2).
Fase 1 - iteração 2 Custos Relativos
\(I_B=\{6,1,5\}\) & \(I_N=\{4,2,3\}\) com \(k=2\) pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 1 & 0 & 0\\ 1 & 1& -1\\ 0 & 0& 1 \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ 0\\ 0\end{bmatrix}\]\(\lambda^T=(1,-1,0)\)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_4=0-
\end{matrix}\begin{bmatrix}
1 & -1 & 0
\end{bmatrix}\begin{bmatrix}
1 \\
1 \\
-1
\end{bmatrix}\begin{matrix}
=0
\end{matrix}\]
\[\begin{matrix}
C´_2=0-
\end{matrix}\begin{bmatrix}
1 & -1 & 0
\end{bmatrix}\begin{bmatrix}
1 \\
-1 \\
1
\end{bmatrix}\begin{matrix}
=-2
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
1 & -1 & 0
\end{bmatrix}\begin{bmatrix}
-1 \\
0 \\
0
\end{bmatrix}\begin{matrix}
=1
\end{matrix}\]
Fase 1 - iteração 2 Tamanho de Passo
\(I_B=\{6,1,5\}\) & \(I_N=\{4,2,3\}\), \(k=2\) e \(s=6\) pois
Custos relativos \(B\cdot y=a_2\)
\[\begin{bmatrix} 1 & 1 & 0\\ 0 & 1& 0\\ 0 & -1& 1 \end{bmatrix} \cdot \begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ -1\\ 1\end{bmatrix}\]\(y^T=(2,-1,0)\)
\(\epsilon_i=\frac{x_{I_{B_i}}}{y_i}\)
\(\epsilon_1=\frac{x_{6}}{y_1}=\frac{2}{2}=1\)
\(\epsilon_2=\frac{x_1}{y_2}=\frac{4}{-1}=-4\)
\(\epsilon_3=\frac{x_{5}}{y_3}=\frac{8}{0}\rightarrow \infty\)
Fim da fase 1
\(I_B=\{2,1,5\}\) & \(I_N=\{4,6,3\}\) pois \(x_6\) é a única variável artificial que saiu da base no final da iteração 2.
Iniciamos a fase 2 com os mesmos contadores, eliminando-se os índices das variáveis artificiais que deverão estar todos em \(I_N\)
Início da fase 2 com \(I_B=\{2,1,5\}\) & \(I_N=\{4,3\}\)
Partição da Fase 2
\(I_B=\{2,1,5\}\) & \(I_N=\{4,3\}\)
\(min\) \(z=c^T\cdot x\)
Sujeito a:
\(A\cdot x= b\), \(x\ge 0\)
Tal que:
\(c^T=(-3,1,0,0,0)\); \(x^T=(x_1,x_2,x_3,x_4,x_5)\);
\(b^T=(6,4,4)\) e \(A=\) \[ \begin{bmatrix} 1 & 1 & -1 & 0 & 0 \\ 1 &-1 & 0 & 1 & 0 \\ -1 &1 & 0 & 0 & 1 \\ \end{bmatrix} \]
\(c^T_N=(0,0)\); \(c^T_B=(1,-3,0)\); \(x^T_N=(x_4,x_3)\); \(x^T_B=(x_2,x_1,x_5)\); \(b^T=(6,4,4)\)
\[\begin{matrix} N= \end{matrix}\begin{bmatrix} 0& -1\\ 1& 0\\ 0 & 0 \end{bmatrix} \begin{matrix} B= \end{matrix}\begin{bmatrix} 1 & 1& 0\\ -1 & 1& 0\\ 1 & -1& 1 \end{bmatrix}\]\(B\cdot x_B=b \rightarrow x_B^T=(1,5,8)\), logo a Solução Corrente será \(x^T=(\) 5, 1, 0, 0, 8).
Fase 2 - iteração 1 Custos Relativos
\(I_B=\{2,1,5\}\) & \(I_N=\{4,3\}\) com \(k=3\) pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 1 & -1 & 1\\ 1 & 1& -1\\ 0 & 0& 1 \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2\\ \lambda_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ -3\\ 0\end{bmatrix}\]\(\lambda^T= (\) -1, -2, 0)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_4=0-
\end{matrix}\begin{bmatrix}
-1 & -2 & 0
\end{bmatrix}\begin{bmatrix}
0 \\
1 \\
0
\end{bmatrix}\begin{matrix}
=2
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
-1 & -2 & 0
\end{bmatrix}\begin{bmatrix}
-1 \\
0 \\
0
\end{bmatrix}\begin{matrix}
=-1
\end{matrix}\]
Fase 2 - iteração 1 Tamanho de Passo
\(I_B=\{2,1,5\}\) & \(I_N=\{4,3\}\), \(k=3\) e fim pois
Custos relativos \(B\cdot y=a_3\)
\[\begin{bmatrix} 1 & 1 & 0\\ -1 & 1& 0\\ 1 & -1& 1 \end{bmatrix} \cdot \begin{bmatrix} y_1\\ y_2\\ y_3 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} -1\\ 0\\ 0\end{bmatrix}\]\(y^T=(-0.5,-0.5,0)\)
\(\epsilon_i=\frac{x_{I_{B_i}}}{y_i}\)
\(\epsilon_1=\frac{x_{2}}{y_1}=\frac{1}{-0.5}=-2\)
\(\epsilon_2=\frac{x_{1}}{y_2}=\frac{5}{-0.5}=-10\)
\(\epsilon_3=\frac{x_{5}}{y_3}=\frac{8}{0} \rightarrow \infty\)
Não existe solução ótima pois a segunda regra de parada foi atingida, \(\nexists \space \epsilon_i>0\)
Exercício: Solução Gráfica
Indique a solução ótima com base no gráfico. Em seguida resolva pelo método simplex duas fases.
Exercício - Resposta Esperada
Considerando que a região viável é formada pelos polígono com vértices \((0,2)\), \((0,5)\) e \((1.25,2.5)\) e que se existe uma solução ótima então será um destes vértices.
Com base no gráfico observamos que o vértice mais extremo da região viável no sentido do vetor gradiente é \((1.25,2.5)\), resultando em \(z^*=8\cdot 1.25+2\cdot2.5=15\).
Portanto este problema possui uma única solução ótima, com \(x_1=1.25, x_2=2.5, z^*=15\).
Exercício Fase 1
1a. fase, 1a. iteração produzirá (\(x_5\) representa a variável artificial):
\(I_N=\{1,2,3\}\) e \(I_B=\{5,4\}\) \(x^T=(x_1,x_2,x_3,x_4,x_5)\), \(c^T=(0,0,0,0,1)\), \(b^T=(30,10)\)
\(c_B^T=(c_{5},c_{4})=(1,0)\) e \(c_N^T=(c_{1},c_{2}, c_3)=(0,0,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{5}\\ x_{4} \\ \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \\ x_3 \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1&0 \\ 0&1 \\ \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -6 & 15 & -1 \\ 4 & 2 &0 \\ \end{bmatrix} \]
\(B\cdot x_B=b \rightarrow x_B^T=(30,10)\), logo a Solução Corrente será \(x^T=(\) 0, 0, 0, 10, 30).
Exercício Fase 1 - iteração 1 Custos Relativos
\(I_B=\{5,4\}\) & \(I_N=\{1,2,3\}\) com \(k=2\) pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 1 & 0 \\ 0 & 1\\ \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 1\\ 0\end{bmatrix}\]\(\lambda^T=(1,0)\)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_1=0-
\end{matrix}\begin{bmatrix}
1 & 0
\end{bmatrix}\begin{bmatrix}
-6 \\
4
\end{bmatrix}\begin{matrix}
=6
\end{matrix}\]
\[\begin{matrix}
C´_2=0-
\end{matrix}\begin{bmatrix}
1 & 0
\end{bmatrix}\begin{bmatrix}
15 \\
2
\end{bmatrix}\begin{matrix}
=-15
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
1 & 0
\end{bmatrix}\begin{bmatrix}
-1 \\
0
\end{bmatrix}\begin{matrix}
=1
\end{matrix}\]
Exercício Fase 1 - iteração 1 Tamanho de Passo
\(I_B=\{5,4\}\) & \(I_N=\{1,2,3\}\) com \(k=2\) e \(s=5\) pois
\(B\cdot y=a_2\)
\[\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} y_1\\ y_2 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} 15\\ 2\end{bmatrix}\]\(y^T=(15,2)\)
\(\epsilon_i=\frac{x_{I_{B_i}}}{y_i}\)
\(\epsilon_1=\frac{x_{5}}{y_1}=\frac{30}{15}=2\)
\(\epsilon_2=\frac{x_{4}}{y_2}=\frac{10}{2}=5\)
Exercício Fase 1 Fim - Partição Fase 2
Fim da fase 1 pois o novo particionamento já não possui \(x_5\) na base: \(I_N=\{1,5,3\}\) e \(I_B=\{2,4\}\)
No início da fase 2, eliminamos o índice 5 de \(I_N\) e teremos:
\(I_N=\{1,3\}\) e \(I_B=\{2,4\}\) \(x^T=(x_1,x_2,x_3,x_4)\), \(c^T=(-8,-2,0,0)\), \(b^T=(30,10)\)
\(c_B^T=(c_{2},c_{4})=(-2,0)\) e \(c_N^T=(c_{1}, c_3)=(-8,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{2}\\ x_{4} \\ \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_3 \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 15&0 \\ 2&1 \\ \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -6 & -1 \\ 4 &0 \\ \end{bmatrix} \]
\(B\cdot x_B=b \rightarrow x_B=(2,6)\), logo a Solução Corrente será \(x=(\) 0, 2, 0, 6).
Exercício Fase 2 - iteração 1 Custos Relativos
\(I_B=\{2,4\}\) & \(I_N=\{1,3\}\) com \(k=1\) pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 15 & 2 \\ 0 & 1\\ \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} -2\\ 0\end{bmatrix}\]\(\lambda^T=(-0.13,0)\)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_1=-8-
\end{matrix}\begin{bmatrix}
-0.13 & 0
\end{bmatrix}\begin{bmatrix}
-6 \\
4
\end{bmatrix}\begin{matrix}
=-8.8
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
-0.13 & 0
\end{bmatrix}\begin{bmatrix}
-1 \\
0
\end{bmatrix}\begin{matrix}
=-0.13
\end{matrix}\]
Exercício Fase 2 - iteração 1 Tamanho de Passo
\(I_B=\{2,4\}\) & \(I_N=\{1,3\}\) com \(k=1\) e \(s=4\) pois
\(B\cdot y=a_1\)
\[\begin{bmatrix} 15 & 0\\ 2 & 1 \end{bmatrix} \cdot \begin{bmatrix} y_1\\ y_2 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} -6\\ 4\end{bmatrix}\]\(y^T=(-0.4,4.8)\)
\(\epsilon_i=\frac{x_{I_{B_i}}}{y_i}\)
\(\epsilon_1=\frac{x_{2}}{y_1}=\frac{2}{-0.4}=-5\)
\(\epsilon_2=\frac{x_{4}}{y_2}=\frac{6}{4.8}=1.25\)
Exercício Fase 2 iteração 2
2a. iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1\}\) \(x^T=(x_1,x_2,x_3,x_4)\), \(c^T=(-8,-2,0,0)\), \(b^T=(30,10)\)
\(c_B^T=(c_{2},c_{1})=(-2,-8)\) e \(c_N^T=(c_{4}, c_3)=(0,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{2}\\ x_{1} \\ \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_3 \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 15&-6 \\ 2&4 \\ \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & -1 \\ 1 &0 \\ \end{bmatrix} \]
\(B\cdot x_B=b \rightarrow x_B=(2.5,1.25)\), logo a Solução Corrente será \(x=(\) 1.25, 2.5, 0, 0).
Exercício Fase 2 - iteração 2 Custos Relativos
\(I_B=\{2,1\}\) & \(I_N=\{4,3\}\) e fim pois
\(B^T\cdot \lambda=c_B\)
\[\begin{bmatrix} 15 & -6 \\ 2 & 4\\ \end{bmatrix} \cdot \begin{bmatrix} \lambda_1\\ \lambda_2 \end{bmatrix}\begin{matrix} = \end{matrix} \begin{bmatrix} -2\\ -8\end{bmatrix}\]\(\lambda^T=(0.11,-1.83)\)
\(C´_i=c_i-\lambda^T\cdot a_i\)
\[\begin{matrix}
C´_4=0-
\end{matrix}\begin{bmatrix}
0.11 & -1.83
\end{bmatrix}\begin{bmatrix}
0 \\
1
\end{bmatrix}\begin{matrix}
=1.83
\end{matrix}\]
\[\begin{matrix}
C´_3=0-
\end{matrix}\begin{bmatrix}
0.11 & -1.83
\end{bmatrix}\begin{bmatrix}
-1 \\
0
\end{bmatrix}\begin{matrix}
=0.11
\end{matrix}\]
A solução corrente é ótima pois atingimos a regra de otimalidade, todos os custos relativos são positivos.
Formulário do Algoritmo Simplex
Será fornecido nas avaliações.
\(Bx_B=b\) ou \(x_B = B^{-1}b\);
\(B^{T}\lambda = c_B\) ou \(\lambda = B^{T^-1}c_B\)
\(C'_{N_i}=c_{N_i}-\lambda^T a_{N_i}\);
\(By=a_k\) ou \(y=B^{-1}a_k\)
\(\epsilon_z=\frac{x_{Bz}}{y_z}\)
Revise
Terminou? Revise os conceitos desta aula.
Verifique se permanece alguma dúvida sobre notação e procedimentos do algoritmo.
Faça os exercícios propostos no moodle.
