| it | IN | IB | CR | E |
|---|---|---|---|---|
| 1 | (1,2,3,4,5,6) | (8,9,7) | (0, 0, -1, -2, 1, 1) | (2, Inf, 10) |
| 2 | (1,2,3,8,5,6) | (4,9,7) | (-1, 1, 0, 1, 0, 1) | (-4, 1, Inf) |
| 3 | (9,2,3,8,5,6) | (4,1,7) | (1, 0, 0, 1, 0, 0) | - |
Pesquisa Operacional - PEOP
AULA 28: 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- 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
- Identificar o modelo a ser resolvido pelo Simplex Duas Fases
- Formular o modelo da Fase 1
- Realizar o Particionamento Inicial da Fase 1
- Finalizar a Fase 1 e Iniciar a Fase 2
Modelo a ser resolvido pelo Simplex Duas Fases
Sempre que o modelo possuir alguma restrição do tipo \(\ge\) ou \(=\), será necessário utilizar o procedimento do Simplex Duas Fases
\[min \space z= x_1-x_2+2x_3-3x_4\]
Sujeito a:
\[R_1:\space -x_1+x_2+x_3+2x_4\color{red}{\ge}4\] \[R_2:\space x_1-x_2+0x_3+0x_4\color{red}{\ge}1\] \[R_3:\space 0x_1+0x_2+2x_3+x_4\le10\]
\[{x_1,x_2,x_3,x_4}\ge0\]
Forma Padrão
| Var. Decisão | Var. Excesso | Var. Folga |
|---|---|---|
| \(x_1,...,x_4\) | \(x_5,x_6\) | \(x_7\) |
| Originais | \(R_1,R_2\) | \(R_3\) |
\[min \space z= 1x_1-1x_2+2x_3-3x_4+0x_5+0x_6+0x_7\]
Sujeito a:
\[R_1:\space -1x_1+1x_2+1x_3+2x_4\color{red}{-1x_5+0x_6+0x_7=}4\] \[R_2:\space 1x_1-1x_2+0x_3+0x_4\color{red}{+0x_5-1x_6+0x_7=}1\] \[R_3:\space 0x_1+0x_2+2x_3+1x_4\color{red}{+0x_5+0x_6+1x_7=}10\]
\[{x_1,x_2,x_3,x_4, \color{red}{x_5,x_6,x_7}}\ge0\]
Elementos Matriciais:
\[x^T= \begin{matrix}( \underbrace{x_1,x_2,x_3,x_4 \space}_{x_0}, x_5,x_6,x_7) \end{matrix} \]
\[c^T= \begin{matrix}( \underbrace{1,-1,2,-3 \space}_{c_0}, 0,0,0) \end{matrix} \]
\[A= \begin{bmatrix} \begin{matrix} \underbrace{\begin{matrix} -1 & 1 &1&2\\ 1& -1 &0&0\\ 0 & 0& 2& 1\\ \end{matrix}}_{A_0} \space\underbrace{\begin{matrix} -1 & 0&0 \\ 0& -1&0 \\ 0&0&1 \end{matrix}}_{I?\space não} \end{matrix} \end{bmatrix} \]
Criando Variáveis Artificiais
Para formar uma base inicial, criamos variáveis artificias para cada variável de excesso:
| Var. Decisão | Var. Excesso/Artificial | Var. Folga |
|---|---|---|
| \(x_1,...,x_4\) | \(x_5,x_6\)/\(\color{red}{x_8,x_9}\) | \(x_7\) |
| Originais | \(R_1,R_2\) | \(R_3\) |
Criamos um modelo artificial de minimização das variáveis artificiais para a fase 1:
\[\color{blue}{min \space w_a= 0x_1+0x_2+0x_3+0x_4+0x_5+0x_6+0x_7}\color{red}{+1x_8+1x_9}\]
Sujeito a:
\[R_1:\space -1x_1+1x_2+1x_3+2x_4{-1x_5+0x_6+0x_7}+\color{red}{1x_8+0x_9=}4\] \[R_2:\space 1x_1-1x_2+0x_3+0x_4{+0x_5-1x_6+0x_7}+\color{red}{0x_8+1x_9=}1\] \[R_3:\space 0x_1+0x_2+2x_3+1x_4{+0x_5+0x_6+1x_7}+\color{red}{0x_8+0x_9=}10\]
\[{x_1,x_2,x_3,x_4, \color{blue}{x_5,x_6,x_7},\color{red}{x_8,x_9}}\ge0\]
Particionamento Inicial da Fase 1:
\(I_N=\{1,2,3,4,5,6\}\)
\(I_B=\{8,9,7\}\)
Com esse particionamento
\(B=I\)
Modelo Artificial da Fase 1
\[\color{blue}{min \space w_a= 0x_1+0x_2+0x_3+0x_4+0x_5+0x_6+0x_7}\color{red}{+1x_8+1x_9}\]
Sujeito a:
\[R_1:\space -1x_1+1x_2+1x_3+2x_4{-1x_5+0x_6+0x_7}+\color{red}{1x_8+0x_9=}4\] \[R_2:\space 1x_1-1x_2+0x_3+0x_4{+0x_5-1x_6+0x_7}+\color{red}{0x_8+1x_9=}1\] \[R_3:\space 0x_1+0x_2+2x_3+1x_4{+0x_5+0x_6+1x_7}+\color{red}{0x_8+0x_9=}10\]
\[{x_1,x_2,x_3,x_4, \color{blue}{x_5,x_6,x_7},\color{red}{x_8,x_9}}\ge0\]
Fase 1
Na fase 1 criamos um modelo artificial de minimização das variáveis artificiais que terão coeficiente 1 na função objetivo, as demais terão coeficiente zero.
Note que o particionamento inicial \(I_B\) conterá os índices das variáveis artificiais + os índices das variáveis de folga, garantindo sempre que \(B=I\)
O modelo da fase 1 é resolvido pelo algoritmo simplex até que todas as variáveis artificiais estejam no particionamento Não Básico.
Desse modo as variáveis artificiais se anulam e fornecem o particionamento inicial para a fase 2.
Resumo das iterações da fase 1
Na iteração 3 conclui-se que a solução corrente é ótima pois todos os custos relativos (CR) são positivos. Em \(I_B\) não temos nenhuma variável artificial, isso garante o particionamento da fase 2 com:
\(I_N=\{2,3,5,6\}\) (elimine os índices das variáveis artificiais)
\(I_B=\{4,1,7\}\) (certifique-se não ter nenhum índice de variável artificial)
Iniciando a fase 2
O modelo da fase 2 é o modelo original na forma padrão, antes da inclusão das variáveis artificiais que foram anuladas e eliminadas na fase 1.
\[min \space z= 1x_1-1x_2+2x_3-3x_4+0x_5+0x_6+0x_7\]
Sujeito a:
\[R_1:\space -1x_1+1x_2+1x_3+2x_4\color{red}{-1x_5+0x_6+0x_7=}4\] \[R_2:\space 1x_1-1x_2+0x_3+0x_4\color{red}{+0x_5-1x_6+0x_7=}1\] \[R_3:\space 0x_1+0x_2+2x_3+1x_4\color{red}{+0x_5+0x_6+1x_7=}10\]
\[{x_1,x_2,x_3,x_4, \color{red}{x_5,x_6,x_7}}\ge0\]
Elementos Matriciais:
\[x^T= \begin{matrix}( \underbrace{x_1,x_2,x_3,x_4 \space}_{x_0}, x_5,x_6,x_7) \end{matrix} \]
\[c^T= \begin{matrix}( \underbrace{1,-1,2,-3 \space}_{c_0}, 0,0,0) \end{matrix} \]
\[A= \begin{bmatrix} \begin{matrix} \underbrace{\begin{matrix} -1 & 1 &1&2\\ 1& -1 &0&0\\ 0 & 0& 2& 1\\ \end{matrix}}_{A_0} \space\underbrace{\begin{matrix} -1 & 0&0 \\ 0& -1&0 \\ 0&0&1 \end{matrix}}_{I?\space não} \end{matrix} \end{bmatrix} \]
\(I_N=\{2,3,5,6\}\) , \(I_B=\{4,1,7\}\), Elementos Matriciais:
\[x_N^T= \begin{matrix}( {x_2,x_3,x_5,x_6}) \end{matrix}, x_B^T= \begin{matrix}( {x_4,x_1,x_7}) \end{matrix} \]
\[c_N^T= \begin{matrix}(-1,2,0,0) \end{matrix}, c_B^T= \begin{matrix}(-3,1,0) \end{matrix} \]
\[B= \begin{bmatrix} 2&-1&0\\ 0&1&0\\ 1&0&1\\ \end{bmatrix},b=\begin{bmatrix}4\\1\\10 \end{bmatrix} \]
Obtenha a solução corrente
Considere o particionamento inicial da fase2 do modelo fornecido anteriormente. Obtenha a solução corrente desta iteração.
Sua resposta deve ser \(x^T=(1,0,0,2.5,0,0,7.5)\)
Analise a iteração
Sabendo que:
| IN | IB | Solucao_corrente | CR | E |
|---|---|---|---|---|
| (2,3,5,6) | (4,1,7) | (1, 0, 0, 2.5, 0, 0, 7.5) | (0.0, 3.5, -1.5, -0.5) | (-4,Inf,Inf) |
