Chapter 7 A inversa, simplex e dualidade

(Para uma explicação completa do material deste capítulo, vejas a apresentações Simplex e Dualidade I e Simplex e Dualidade II)

A partir da inversa da base (B) de um PL podemos escrever todos os dados da tabela simplex na iteração referente a esta base. Ainda, podemos determinar como calcular a solução dual (\(\pi\)). O quadro genérico fica:

\(x_B\)	\(x_N\)	\[-z\]
\(0\)	\(c_N^T - c_B^TB^{-1}N\)	\(-c_B^TB^{-1}b\)
\(I\)	\(B^{-1}N\)	\(B^{-1}b\)

7.1 Encontrando os elementos da tabela pelas fórmulas genéricas

EXERCICIO 1: Considere o modelo do sapateiro:

\[\begin{alignat*}{4} & \text{max z = } & 5x_1 & + 2x_2 \\ & \text{Sujeito à} & 10x_1 & + 12x_2 &\leq 60\\ & & 2x_1 & + x_2 & \leq 6\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]

Sabendo que a solução ótima tem as variáveis básicas \(x_B^T = (x_3,x_1)\), encontre o quadro Simplex ótimo:

Na forma padrão, temos que:

\[\begin{alignat*}{4} & \text{min z = } & -5x_1 & - 2x_2 \\ & \text{Sujeito à} & 10x_1 & + 12x_2 & + x_3 & & = 60\\ & & 2x_1 & + x_2 & & & + x_4& = 6\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]

Portanto, com \(x_B^T = (x_3,x_1)\):

\[\begin{equation*} B = \left[ \begin{array}{cc} 1 & 10 \\ 0 & 2 \end{array} \right], c_B^T = \left[ \begin{array}{cc} 0 & -5 \\ \end{array} \right] \end{equation*}\]

\[\begin{equation*} N = \left[ \begin{array}{cc} 12 & 0 \\ 1 & 1 \end{array} \right], c_N^T = \left[ \begin{array}{cc} -2 & 0 \\ \end{array} \right] \end{equation*}\]

\[\begin{equation*} b^T = \left[ \begin{array}{cc} 60 & 6 \\ \end{array} \right] \end{equation*}\]

Encontrando a inversa \(B^{-1}\):

\[\begin{equation*} B|I = \left[ \begin{array}{cccc} 1 & 10 & 1& 0\\ 0 & 2 & 0 & 1 \end{array} \right] \end{equation*}\]

Realizando as operações:

\(L_2 \leftarrow L_2/2\)

\(L_1 \leftarrow L_1 - 10 L_2\)

Temos:

\[\begin{equation*} B^{-1} = \left[ \begin{array}{cc} 1 & -5\\ 0 & 1/2 \end{array} \right] \end{equation*}\]

Calculando \(N\) atualizado:

\[\begin{equation*} B^{-1}N = \left[ \begin{array}{cc} 1 & -5\\ 0 & 1/2 \end{array} \right] \left[ \begin{array}{cc} 12 & 0 \\ 1 & 1 \end{array} \right] = \left[ \begin{array}{cc} 7 & -5 \\ 1/2 & 1/2 \end{array} \right] \end{equation*}\]

Calculando \(c_N^T\) atualizado:

\[\begin{equation*} c_N^T - c_B^TB^{-1}N = \left[ \begin{array}{cc} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{cc} 0 & -5 \\ \end{array} \right] \left[ \begin{array}{cc} 1 & -5\\ 0 & 1/2 \end{array} \right] \left[ \begin{array}{cc} 12 & 0 \\ 1 & 1 \end{array} \right] \end{equation*}\]

\[\begin{equation*} = \left[ \begin{array}{cc} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{cc} 0 & -5 \\ \end{array} \right] \left[ \begin{array}{cc} 7 & -5 \\ 1/2 & 1/2 \end{array} \right] \end{equation*}\]

\[\begin{equation*} = \left[ \begin{array}{cc} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{cc} -5/2 & -5/2 \\ \end{array} \right] = \left[ \begin{array}{cc} 1/2 & 5/2 \\ \end{array} \right] \end{equation*}\]

Calculando \(b\) atualizado:

\[\begin{equation*} B^{-1}b = \left[ \begin{array}{cc} 1 & -5\\ 0 & 1/2 \end{array} \right] \left[ \begin{array}{c} 60 \\ 6 \end{array} \right] = \left[ \begin{array}{c} 30 \\ 3 \end{array} \right] \end{equation*}\]

Calculando \(-z\) atualizado:

\[\begin{equation*} -c_BB^{-1}b = - \left[ \begin{array}{cc} 0 & -5\\ \end{array} \right] \left[ \begin{array}{c} 30 \\ 3 \end{array} \right] = 15 \end{equation*}\]

Portanto o quadro Simplex considerando as variáveis básica \(x_B^T = (x_3,x_1)\) fica:

VB	X1	X2	X3	X4	b
	0	1/2	0	5/2	15
\(x_3\)	0	7	1	-5	30
\(x_1\)	1	1/2	0	1/2	3

EXERCICIO 2: Considerando o seguinte modelo de PL:

\[\begin{alignat*}{4} & \text{max z = } & 100x_1 & + 150x_2 \\ & \text{Sujeito à} & 2x_1 & + 3x_2 & \leq 120\\ & & x_1 & & \leq 40\\ & & & \quad x_2 & \leq 30\\ & & x_1 \geq 0 & \quad \quad x_2 \geq 0& \end{alignat*}\]

A: A solução básica com variáveis \(x_B^T = (x_3,x_4,x_2)\) é ótima?

B: Se a solução não for ótima, calcule qual deve ser a variável que sai da base.

C: Com a definição da variável que sai e da que entra na base, qual seria o próximo passo considerando o algoritmo Simplex e a tabela genérica?

SOLUÇÃO A

Sabemos que o critério de parada do algoritmo Simplex é quando todos os \(c_i\) na função objetivo são \(\geq 0\). Portanto, podemos determinar quais são os \(c_N\) atualizados na tabela (dado que os \(c_B\) são sempre 0), considerando as variávieis básicas \(x_B^T = (x_3,x_4,x_2)\), e então verificar se algum é negativo.

O valores atualizados são dados por:

\[\begin{equation*} c_N^T - c_B^TB^{-1}N \end{equation*}\]

Temos que:

\[\begin{equation*} B = \left[ \begin{array}{ccc} 1 & 0 & 3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right], N = \left[ \begin{array}{ccc} 2 & 0 \\ 1 & 0 \\ 0 & 1 \end{array} \right] \end{equation*}\]

\[\begin{equation*} c_B^T = \left[ \begin{array}{ccc} 0 & 0 & -150 \end{array} \right], c_N^T = \left[ \begin{array}{ccc} -100 & 0 \\ \end{array} \right] \end{equation*}\]

Para encontrar a inversa \(B^{-1}\)

\[\begin{equation*} B|I = \left[ \begin{array}{cccccc} 1 & 0 & 3 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array} \right] \end{equation*}\]

Com a operação: \(L_1 \leftarrow L_1 - 3L_3\)

Temos a inversa:

\[\begin{equation*} B^{-1} = \left[ \begin{array}{ccc} 1 & 0 & -3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \end{equation*}\]

Portanto os valores atualizados ficam:

\[\begin{equation*} c_N^T - c_B^TB^{-1}N = \left[ \begin{array}{ccc} -100 & 0 \\ \end{array} \right] - \left[ \begin{array}{ccc} 0 & 0 & -150 \end{array} \right] \left[ \begin{array}{ccc} 1 & 0 & -3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{ccc} 2 & 0 \\ 1 & 0 \\ 0 & 1 \end{array} \right] \end{equation*}\]

\[\begin{equation*} = \left[ \begin{array}{ccc} -100 & 0 \\ \end{array} \right] - \left[ \begin{array}{ccc} 0 & -150 \\ \end{array} \right] \end{equation*}\]

\[\begin{equation*} c_N^T = \left[ \begin{array}{ccc} -100 & 150 \\ \end{array} \right] \end{equation*}\]

Temos que o custo atualizado de \(x_1\) é -100, portanto a solução não é ótima.

SOLUÇÃO B

Sabemos que para determinar a variável que deixa a base, é necessário encontrar:

\[\begin{equation*} \underset{\{ \forall a_{is} > 0, i=1,...,m \} }{min} \dfrac{b_i}{a_{is}} \end{equation*}\]

Ou seja, precisamos dos valores de \(b\) e da coluna \(A_i\) atualizados.

Calculando \(b\) atualizado:

\[\begin{equation*} B^{-1}b = \left[ \begin{array}{ccc} 1 & 0 & -3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{ccc} 120 \\ 40 \\ 30 \end{array} \right] = \left[ \begin{array}{ccc} 30 \\ 40 \\ 30 \end{array} \right] \end{equation*}\]

Para calcular \(A_1\) atualizado (pois \(x_1\) é a variável que entra na base), podemos usar a fórmula \(B^{-1}N\), porém usamos a \(A_1\) antiga no lugar de toda a matriz \(N\):

\[\begin{equation*} B^{-1}A_1 = \left[ \begin{array}{ccc} 1 & 0 & -3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right] \left[ \begin{array}{ccc} 2 \\ 1 \\ 0 \end{array} \right] = \left[ \begin{array}{ccc} 2 \\ 1 \\ 0 \end{array} \right] \end{equation*}\]

Portanto, temos que o mínimo entre

\[\begin{equation*} \dfrac{30}{2}, \dfrac{40}{1} = 15 \end{equation*}\]

Com \(x_3\) deixando a base e \(x_1\) entrando em seu lugar.

SOLUÇÃO C

Sabemos então que na próxima iteração a solução terá as variáveis \(x_B^T = (x_1,x_4,x_2)\). O próximo passo seria calcular a matriz inversa dessa nova base e verificar os valores atualizados de \(c_i\) (como na letra A). Note que fizemos toda uma iteração do algoritmo Simplex sem usar o quadro-Simplex, somente com as fórmulas genéricas. Em modelos maiores, isso evita que muitos cálculos. Essa é a base do algoritmo Simplex-revisado (ver apresentação no site).

7.2 Encontrando a solução dual na tabela primal

Sabemos que o negativo dos valores duais estão presentes na própria tabela primal. São os \(c_i\) atualizados acima da matriz identidade inicial.

EXEMPLO 1: Considere o modelo do sapateiro:

\[\begin{alignat*}{4} & \text{max z = } & 5x_1 & + 2x_2 \\ & \text{Sujeito à} & 10x_1 & + 12x_2 &\leq 60\\ & & 2x_1 & + x_2 & \leq 6\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]

Com quadro ótimo:

VB	X1	X2	X3	X4	b
	??	??	??	??	??
\(x_3\)	??	??	1	-5	30
\(x_1\)	??	??	0	1/2	3

Determine a solução ótima do modelo dual e verique se a solução é ótima.

Para determinar a solução ótima, basta encontrarmos os valores de \(c_i\) atualizados. Pela tabela ótima, sabemos que \(x_B^T = (x_3,x_1)\), com matriz inversa:

\[\begin{equation*} B^{-1} = \left[ \begin{array}{c} 1 & -5 \\ 0 & 1/2 \end{array} \right] \end{equation*}\]

Para encontrar os valores de \(c_N\) atualizados:

\[\begin{equation*} c_N^T - c_B^TB^{-1}N = \\ \left[ \begin{array}{c} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{c} 0 & -5 \\ \end{array} \right] \left[ \begin{array}{c} 1 & -5 \\ 0 & 1/2 \end{array} \right] \left[ \begin{array}{c} 12 & 1 \\ 1 & 1 \end{array} \right] = \\ \left[ \begin{array}{c} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{c} 0 & -5 \\ \end{array} \right] \left[ \begin{array}{c} 7 & -4 \\ 1/2 & 1/2 \end{array} \right] = \\ \left[ \begin{array}{c} -2 & 0 \\ \end{array} \right] - \left[ \begin{array}{c} -5/2 & -5/2 \\ \end{array} \right] = \\ \left[ \begin{array}{c} 1/2 & 5/2 \\ \end{array} \right] \end{equation*}\]

Portanto, os valores de \(c_i\) atualizados ficam:

\[\begin{equation*} c^T = \left[ \begin{array}{ccc} c_1 & c_2 & c_3 & c_4 \\ \end{array} \right] = \\ \left[ \begin{array}{ccc} 0 & 1/2 & 0 & 5/2 \\ \end{array} \right] \end{equation*}\]

Temos então que:

\[\begin{equation*} -\pi^T = \left[ \begin{array}{ccc} 0 & 5/2 \\ \end{array} \right] \\ \pi^T = \left[ \begin{array}{ccc} 0 & -5/2 \\ \end{array} \right] \end{equation*}\]

Como, para transformar o problema na forma padrão fizemos max z = - min z, temos que:

\[\begin{equation*} \pi^T = \left[ \begin{array}{ccc} 0 & 5/2 \\ \end{array} \right] \end{equation*}\]

O modelo dual do problema do sapapeiro fica:

\[\begin{alignat*}{4} & \text{min v = } & 60\pi_1 & + 6\pi_2 \\ & \text{Sujeito à} & 10\pi_1 & + 2\pi_2 &\geq 5\\ & & 12\pi_1 & + \pi_2 & \geq 2\\ & & \pi_1 \geq 0 & \quad \pi_2 \geq 0& \end{alignat*}\]

Substituindo os valores de \(\pi\) no modelo, temos:

\[\begin{alignat*}{4} & \text{min v = } & 60(0) & + 6(5/2) \\ & \text{Sujeito à} & 10(0) & + 2(5/2) &\geq 5\\ & & 12(0) & + 5/2 & \geq 2\\ & & \pi_1 \geq 0 & \quad \pi_2 \geq 0& \end{alignat*}\]

Portanto a solução é dual-factível. Seu custo fica \(v = 15\). Substituindo a solução primal em \(z\) temos que \(z = 15\). Como \(v = z\) temos que a solução é ótima.