Chapter 4 Simplex Fase II
4.1 A forma padrão
O algoritmo Simplex (criado por George B. Dantzig) é o método padrão utilizado para resolver modelos de PL de forma genérica. O método opera os modelos na chamada forma padrão. Um modelo está na forma padrão se puder ser escrito como:
\[\begin{align} \text{min $z$ = } & c_1x_1 + c_2x_2 + ... + c_nx_n \\ s.a &\\ & a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1 \\ & a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2 \\ & ... \quad + \quad ... \quad + \quad ... \quad = \quad ... \\ & a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_m \\ & x_1, x_2, ..., x_n \geq 0 \\ & b_1, b_2, ..., b_m \geq 0 \\ \end{align}\]
Podemos escrever na forma matricial:
\[\begin{align} \text{min $z$ = } & c^Tx \\ &Ax = b \\ &x \geq 0, b \geq 0 \end{align}\]
Com:
\[\begin{equation*} A = \left[ \begin{array}{ccc&} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{m1} & a_{m2} & ... & a_{mn} \\ \end{array} \right] \end{equation*}\] \[\begin{equation*} c^T = \left[ \begin{array}{cccc} c_1 & c_2 & ... & c_n \end{array} \right] \end{equation*}\] \[\begin{equation*} x^T = \left[ \begin{array}{cccc} x_1 & x_2 & ... & x_n \end{array} \right] \end{equation*}\] \[\begin{equation*} b^T = \left[ \begin{array}{cccc} b_1 & b_2 & ... & b_m \end{array} \right] \end{equation*}\]
Em que \(A\) é a matriz tecnologica (ou dos coeficientes), \(c\) é o vetor de custos, \(x\) o vetor das variáveis e \(b\) o vetor das constantes.
EXEMPLO Escreva o seguinte modelo de PL na forma matricial e identifique cada termo (o modelo não está na forma padrão, o exempo é simplesmente para identificar os termos matriciais):
\[\begin{align} \text{max $f$ = } & 2x_1 + 3x_2 \\ s.a &\\ & x_1 + x_2 = 3\\ & x_1 + 2x_2 = 4\\ & x_1, x_2 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Nesse caso temos:
\[\begin{equation*} \text{max z = } \underbrace{ \left[ \begin{array}{c} 2 & 3 \\ \end{array} \right] }_{c^t} \underbrace{ \left[ \begin{array}{cc} x_1 \\ x_2 \end{array} \right] }_{x} \\ \text{s.a} \end{equation*}\] \[\begin{equation*} \underbrace{ \left[ \begin{array}{cc} 1 & 1 \\ 1 & 2 \end{array} \right] }_{A} \underbrace{ \left[ \begin{array}{cc} x_1 \\ x_2 \end{array} \right] }_{x} = \underbrace{ \left[ \begin{array}{cc} 3 \\ 4 \end{array} \right] }_{b} \end{equation*}\]
Ou seja, para que um modelo de PL esteja na forma padrão, ele deve possuir as seguintes caracteristicas:
A. A função objetivo deve ser minimizada
B. As restrições do problema são definidas por um sistema de equações lineares
C. Todos os valores independentes \(b\) são positivos (\(b \geq 0\))
D. Todas as variáveis \(x\) são positivas \(x \geq 0\)
Se o modelo não se econtra na forma padrão, podemos trasnformá-lo em um modelo equivalente, aplicando algumas operações. Vejamos cada caso:
A. A função objetivo deve ser minimizada
Os valores de \(x\) que maximizam uma função \(f(x)\) são os mesmos que minimizam \(-f(x)\). Temos então que:
\(\text{max } f(x) = \text{min } -f(x)\)
Considere a função \(f(x) = -(x-2)^2-3\) plotada em azul abaixo:
A função em em vermelho representa \(-f(x)\). Perceba que o ponto \(x\) que maximiza \(f(x)\) (\(x = 2\)) é exatamente o mesmo que minimiza \(-f(x)\). No entanto, os valores das funções ficaram invertidos: o máximo de \(f(x)\) é -3 na medida em que o mínimo de \(-f(x)\) é 3.
Ou seja, para modelos de PL, podemos simplesmente transformar uma função de max em min alterando os coeficientes da fo. Lembrando que ao final da otimização, o valor da função deve ser alterado novamente.
EXEMPLO \(\text{max z} = 3x_1 + 2x_2\) é o mesmo que \(\text{min z} = -3x_1 + -2x_2\).
B. Restrições na forma de inequações
Uma inequação pode facilmente ser convertida em uma equação criando uma nova variável \(\geq 0\) com valor coeficiente positiva, para compensar a folga de uma restrição do tipo \(\leq\), ou uma variável negativa para absorver o excesso em uma restrição do tipo \(\geq\).
Considere a inequação:
\[\begin{cases} x_1 \leq 10 \end{cases}\]Existe uma folga de \(x_1\) em relação a 10, podemos representar essa folga por \(x_2\) e somar na inequação, ficando então:
\[\begin{cases} x_1 + x_2 = 10 \\ x_1 \geq0, x_2 \geq 0 \end{cases}\]As duas formas são equivalentes. De maneira semelhante, podemos ter inequações da forma \(\geq\):
\[\begin{cases} x_1 \geq 10 \end{cases}\]Neste caso, existe um excesso de \(x_1\) em relação a 10, portanto removemos o valor de uma variável:
\[\begin{cases} x_1 - x_2 = 10 \\ x_1 \geq0, x_2 \geq 0 \end{cases}\]De forma geral, para tranformar uma desigualdade em uma igualdade temos:
- Se for do tipo \(\leq\): crie uma variável positiva e adicione na desigualdade
- Se for do tipo \(\geq\): crie uma variável positiva e remova da desigualdade
C. RHS < 0
O vetor \(b\) (também chamado de Right Hand Side - RHS) deve ser positivo. Para equações, basta multiplicar todos os termos por -1:
\[\begin{cases} x_1 -3x_2 + x_3 = -10 \end{cases}\]É equivalente a:
\[\begin{cases} -x_1 +3x_2 - x_3 = 10 \end{cases}\]ATENÇÃO Podemos usar a mesma técnica para as inequações, mas lembre-se de alterar o sinal de desigualdade!
\[\begin{cases} x_1 -3x_2 + x_3 \geq -10 \end{cases}\]É equivalente a:
\[\begin{cases} -x_1 +3x_2 - x_3 \leq 10 \end{cases}\]D. x irrestrito ( < 0)
As variáveis \(x\) devem ser positivas, porém, em alguns casos pode acontecer de o problema a ser modelado demandar a possibilidade de variáveis negativas. A PL pode lidar com esses casos, sendo necessário somente realizar uma troca de variáveis.
Qualquer número real (positivo ou negativo) pode ser representado pela diferença de dois números positivos. Ou seja, se uma variável \(x_i\) em um PL pode assumir valores reais positivos e negativos, basta realizar a substituição:
\[\begin{cases} x_i = x_i^+ - x_i^- \\ x_i^+ \geq 0 \\ x_i^- \geq 0 \end{cases}\]Em todos os lugares do modelo em que aparecer \(x_i\), aplicar a substituição. Em seguida resolver o modelo (encontrando valores para \(x_i^+\) e \(x_i^-\)) e recoletar o valor de \(x_i\) pela substituição.
EXEMPLOS Encontre a forma padrão para cada um dos modelos abaixo. Resolva o último modelo (variáveis irrestritas) no GUSEK e colete o resultado após a otimização.
A
\[\begin{align} \text{max $z$ = } & x_1 + 2x_2 \\ s.a &\\ & x_1 + x_2 \leq 6\\ & x_1 - x_2 \leq 4\\ & -x_1 + x_2 \leq 4\\ & x_1, x_2 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Na forma padrão:
\[\begin{align} \text{min $z$ = } & -x_1 + -2x_2 \\ s.a &\\ & \quad x_1 + x_2 + x_3 \quad \quad \quad = 6\\ & \quad x_1 - x_2 \quad \quad + x_4 \quad = 4\\ & -x_1 + x_2 \quad \quad \quad + x_5 = 4\\ & x_1, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \end{align}\]
B
\[\begin{align} \text{min $z$ = } & x_1 + x_2 \\ s.a &\\ & x_1 + x_2 \leq -6\\ & x_1 + 3x_2 \geq 10\\ & x_1, x_2 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Na forma padrão:
\[\begin{align} \text{min $z$ = } & x_1 + x_2 \\ s.a &\\ & -x_1 - x_2 -x_3 \quad \quad = 6\\ & \quad x_1 + 3x_2 \quad \quad - x_4 = 10\\ & x_1, x_2, x_3, x_4 \in \mathbb{R}^+ \end{align}\]
C
\[\begin{align} \text{max $z$ = } & 3x_1 + 11x_2 + 9x_3 -x_4 - 29x_5 \\ s.a &\\ & \quad \quad x_2 + x_3 + x_4 - 2x_5 \leq 4\\ & x_1 - x_2 + x_3 + 2x_4 + x_5 \geq 0 \\ & x_1 + x_2 + x_3 \quad \quad - 3x_5 \leq 1 \\ & x_1 \text{ irrestrito}, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \\ \end{align}\]
SOLUÇÃO
Como \(x_1\) é irrestrito, precisamos fazer a transformação de variáveis:
\[\begin{cases} x_1 = x_1^+ - x_1^- \\ x_1^+ \geq 0 \\ x_1^- \geq 0 \end{cases}\]Agora substituimos todos os lugares que aparecem \(x_1\) pela diferença \(x_1^+ - x_1^-\)
\[\begin{align} \text{max $z$ = } & 3(x_1^+ - x_1^-) + 11x_2 + 9x_3 -x_4 - 29x_5 \\ s.a &\\ & \quad \quad \quad \quad x_2 + x_3 + x_4 - 2x_5 \leq 4\\ & (x_1^+ - x_1^-) - x_2 + x_3 + 2x_4 + x_5 \geq 0 \\ & (x_1^+ - x_1^-) + x_2 + x_3 \quad \quad - 3x_5 \leq 1 \\ & (x_1^+,x_1^-, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \\ \end{align}\]
Transformando a fo em minimização, adicionando variáveis de folga temos então:
\[\begin{align} \text{min $z$ = } & -3(x_1^+ - x_1^-) - 11x_2 - 9x_3 + x_4 + 29x_5 \\ s.a &\\ & \quad \quad \quad \quad \quad x_2 + x_3 + x_4 - 2x_5 + x_6 \quad \quad = 4\\ & (x_1^+ - x_1^-) - x_2 + x_3 + 2x_4 + x_5 \quad - x_7 \quad = 0 \\ & (x_1^+ - x_1^-) + x_2 + x_3 \quad \quad - 3x_5 \quad \quad +x_8 = 1 \\ & x_1^+,x_1^-, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \\ \end{align}\]
Passando esse modelo para o formato .lp, temos o seguinte (OBS: os solvers já passam o modelo para a forma padrão, a única coisa que eles não fazem é o tratamento das variáveis irrestritas, portanto precisamos fazer essa conversão antes de otimizar o problema):
Ao otimizarmos o problema temos a solução:
- x1p = 0
- x1n = 3
- x2 = 0.5
- x3 = 3.5
- x4 = 0
- x5 = 0
De forma que, ao coletarmos o valor original de x1, temos que x1 = -3.
4.2 O Algoritmo Simplex
Para a explicação completa do algoritmo, veja a apresentação.
O Algoritmo fica então:
- (menor custo reduzido): encontre
\(s = \underset{\{ \forall j \in 1,...,n \} }{argmin} c_{j}\)
em que \(s\) é o índice da coluna em que \(c_{j}\) é mínimo:
\(c_s = \underset{\{ \forall j \in 1,...,n \} }{min} c_{j}\)
(teste de otimalidade): se \(c_s\geq 0\) PARE. Solução atual é ótima.
(variável que entra da base): se \(c_s < 0\), \(s\) é o índice da variável que entra na base.
(teste da solução ilimitada): se \(A_{\bullet s} \leq 0\) PARE; o problema é ilimitado.
(variável que sai da base): a variável básica atual da linha \(r\) que sai da base (linha do mínimo), e o valor da variável \(x_s\) que entra na base é dado por:
\(x_s = \underset{\{ \forall a_{is} > 0, i=1,...,m \} }{min} \dfrac{b_i}{a_{is}}\)
- (atualização da tabela): faça o pivoteamento da tabela com o elemento \(a_{rs}\) como pivô. Atualize as variáveis básicas na primeira coluna e volte para o passo 1.
4.2.1 Exemplos
EXEMPLO 1 (SAPATEIRO)
Resolva o modelo do sapateiro pelo método Simplex. Mostre o caminho Simplex graficamente.
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*}\]
SOLUÇÃO
O modelo na forma padrão fica:
\[\begin{alignat*}{4} & \text{min z = } & -5x_1 & + -2x_2 \\ & \text{Sujeito à} & 10x_1 & + 12x_2 & + x_3 \quad = 60\\ & & 2x_1 & + x_2 & \quad + x_4 = 6\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]
Na tabela Simplex:
| VB | X1 | X2 | X3 | X4 | b |
|---|---|---|---|---|---|
| -5 | -2 | 0 | 0 | 0 | |
| \(x_3\) | 10 | 12 | 1 | 0 | 60 |
| \(x_4\) | 2 | 1 | 0 | 1 | 6 |
Selecionando \(x_1\) para entrar na base e \(x_4\) para sair, temos o pivô \(a_{31} = 2\), realizando as operações:
\(L_3 \leftarrow L_3/2\)
\(L_1 \leftarrow L_1 + 5L_3\)
\(L_2 \leftarrow L_2 - 10 L_3\)
Temos a tabela:
| 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 |
Com solução ótima: \(x_B^T = [x_3,x_1] = [30,3]\) e \(x_N^T = [x_2,x_4] = [0,0]\).
O caminho Simplex é descrito pelos pontos A e B no gráfico abaixo:
EXEMPLO 2 (ILIMITADO)
Resolva o modelo de PL e mostre o caminho Simplex:
\[\begin{alignat*}{4} & \text{min z = } & -x_1 & + -x_2 \\ & \text{Sujeito à} & x_1 & - x_2 &\leq 4 \\ & & -x_1 & + x_2 & \leq 4\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]
SOLUÇÃO
Na forma padrão:
\[\begin{alignat*}{4} & \text{min z = } & -x_1 & + -x_2 \\ & \text{Sujeito à} & x_1 & - x_2 &\leq 4 \\ & & -x_1 & + x_2 & \leq 4\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]
Na forma padrão:
\[\begin{alignat*}{4} & \text{min z = } & -x_1 & + -x_2 \\ & \text{Sujeito à} & x_1 & - x_2 & + x_3 \quad = 4 \\ & & -x_1 & + x_2 & \quad + x_4 = 4\\ & & x_1 \geq 0 & \quad x_2 \geq 0& \end{alignat*}\]
Na tabela Simplex:
| VB | X1 | X2 | X3 | X4 | b |
|---|---|---|---|---|---|
| -1 | -1 | 0 | 0 | 0 | |
| \(x_3\) | 1 | -1 | 1 | 0 | 4 |
| \(x_4\) | -1 | 1 | 0 | 1 | 4 |
Selecionando \(x_2\) para entrar na base e \(x_4\) para sair:
\(L_1 \leftarrow L_1 + L_3\)
\(L_2 \leftarrow L_2 + L_3\)
| VB | X1 | X2 | X3 | X4 | b |
|---|---|---|---|---|---|
| -2 | 0 | 0 | 1 | 4 | |
| \(x_3\) | 0 | 0 | 1 | 1 | 8 |
| \(x_2\) | -1 | 1 | 0 | 1 | 4 |
Note que ainda existe uma variável que pode melhorar a solução (\(x_1\)), no entanto \(A_{\bullet s} \leq 0\), ou seja, o problema é ilimitado. Graficamente, a primeira solução básica está no ponto A da Figura abaixo, e a segunda no ponto B.
EXEMPLO 3 (MULTIPLAS SOLUÇÕES)
Toda vez que um PL tiver múltiplas soluções ótimas, pelo menos uma das variáveis não básicas terá custo 0 (\(c_j\)) na função objetivo. Ou seja, existe uma variável que pode entrar na base, mas não altera a função objetivo em nada.
Considere o PL:
\[\begin{align} \text{min $z$ = } & -2x_1 - x_2 \\ s.a &\\ & 2x_1 + x_2 \leq 2\\ & x_1, x_2 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Colocando na tabela Simplex:
| VB | X1 | X2 | X3 | b |
|---|---|---|---|---|
| -2 | -1 | 0 | 0 | |
| \(x_3\) | 2 | 1 | 1 | 2 |
Executando as operações (\(x_1\) entra na base e \(x_3\) sai):
\(L_2 \leftarrow L_2/2\)
\(L_1 \leftarrow L_1 + 2L_2\)
| VB | X1 | X2 | X3 | b |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | |
| \(x_1\) | 1 | 1/2 | 1/2 | 1 |
Embora esta seja uma solução ótima, com \(x_B^T = [x_1] = [1]\) e \(x_N^T = [x_2,x_3] = [0,0]\), temos uma variável não básica com custo 0 na função objetivo (\(x_2\)), isso indica que existem multiplas soluções ótimas, e uma delas é com \(x_2\) na base. Para encontrar os valores, basta realizar o pivoteamento necessário para inserir \(x_2\) na base:
\(L_2 \leftarrow 2L_2\)
| VB | X1 | X2 | X3 | b |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | |
| \(x_1\) | 2 | 2 | 2 | 2 |
Uma nova solução ótima, de mesmo custo da anterior é então:
\(x_B^T = [x_2] = [2]\) e \(x_N^T = [x_1,x_3] = [0,0]\). Veja graficamente as duas soluções encontradas (pontos A e B):
Note que os dois pontos estão na curva de nível, indicando o mesmo valor da função objetivo (\(z = -2\)).
EXEMPLO 4
Resolva o PL e mostre o caminho Simplex.
\[\begin{align} \text{max $z$ = } & x_1 + 2x_2 \\ s.a &\\ & x_1 + x_2 \leq 6\\ & x_1 - x_2 \leq 4\\ & -x_1 + x_2 \leq 4\\ & x_1, x_2 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Na forma padrão:
\[\begin{align} \text{min $z$ = } & -x_1 -2x_2 \\ s.a &\\ & x_1 + x_2 + x_3 \quad\quad \quad = 6\\ & x_1 - x_2 \quad\quad + x_4\quad = 4\\ & -x_1 + x_2 \quad \quad + x_5 = 4\\ & x_1,...,x_5 \in \mathbb{R}^+ \end{align}\]
| VB | X1 | X2 | X3 | X4 | X5 | b |
|---|---|---|---|---|---|---|
| -1 | -2 | 0 | 0 | 0 | 0 | |
| \(x_3\) | 1 | 1 | 1 | 0 | 0 | 6 |
| \(x_4\) | 1 | -1 | 0 | 1 | 0 | 4 |
| \(x_5\) | -1 | 1 | 0 | 0 | 1 | 4 |
\(x_2\) entra na base e \(x_5\) sai, com as operações:
\(L_1 \leftarrow L_1 + 2L_4\)
\(L_2 \leftarrow L_2 - L_4\)
\(L_3 \leftarrow L_3 + L_4\)
| VB | X1 | X2 | X3 | X4 | X5 | b |
|---|---|---|---|---|---|---|
| -3 | 0 | 0 | 0 | 2 | 8 | |
| \(x_3\) | 2 | 0 | 1 | 0 | -1 | 2 |
| \(x_4\) | 0 | 0 | 0 | 1 | 1 | 8 |
| \(x_2\) | -1 | 1 | 0 | 0 | 1 | 4 |
Selecionando \(x_1\) para sair da base e \(x_3\) para entrar:
\(L_2 \leftarrow L_2/2\)
\(L_1 \leftarrow L_1 + 3L_2\)
\(L_4 \leftarrow L_4 + L_2\)
| VB | X1 | X2 | X3 | X4 | X5 | b |
|---|---|---|---|---|---|---|
| 0 | 0 | 3/2 | 0 | 1/2 | 11 | |
| \(x_1\) | 1 | 0 | 1/2 | 0 | -1/2 | 1 |
| \(x_4\) | 0 | 0 | 0 | 1 | 1 | 8 |
| \(x_2\) | 0 | 1 | 1/2 | 0 | 1/2 | 5 |
Temos a solução ótima com: \(x_B^T = [x_1,x_4,x_2] = [1,8,5]\) e \(x_N^T = [x_3,x_5] = [0,0]\)
E valor da função objetivo \(z = 10\).
O caminho Simplex é representado abaixo, pelos pontos A, B e C:
EXEMPLO 5
Resolva o PL:
\[\begin{align} \text{max $z$ = } & x_1 + 2x_2 + x_3 \\ s.a &\\ & 2x_1 + x_2 - x_3 \leq 2\\ & 4x_1 + x_2 + x_3 \leq 6\\ & -x_1 - 2x_2 - x_3 \leq 6\\ & x_1,x_2,x_3 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
Na forma padrão:
\[\begin{align} \text{min $z$ = } & -x_1 - 2x_2 - x_3 \\ s.a &\\ & 2x_1 + x_2 - x_3 + x_4 \quad \quad = 2\\ & 4x_1 + x_2 + x_3 \quad + x_5 \quad = 6\\ & -x_1 - 2x_2 - x_3 \quad \quad + x_6 = 6\\ & x_1,...,x_5 \in \mathbb{R}^+ \end{align}\]
Colocando na tabela Simplex:
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| -1 | -2 | -1 | 0 | 0 | 0 | 0 | |
| \(x_4\) | 2 | 1 | -1 | 1 | 0 | 0 | 2 |
| \(x_5\) | 4 | 1 | 1 | 0 | 1 | 0 | 6 |
| \(x_6\) | -1 | -2 | -1 | 0 | 0 | 1 | 6 |
Selecionando \(x_2\) para entrar na base e \(x_4\) para sair:
\(L_1 \leftarrow L_1 + 2L_2\)
\(L_3 \leftarrow L_3 - L_2\)
\(L_4 \leftarrow L_4 + 2L_2\)
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| 3 | 0 | -3 | 2 | 0 | 0 | 4 | |
| \(x_2\) | 2 | 1 | -1 | 1 | 0 | 0 | 2 |
| \(x_5\) | 2 | 0 | 2 | -1 | 1 | 0 | 4 |
| \(x_6\) | 3 | 0 | -3 | 2 | 0 | 1 | 10 |
Selecionando \(x_3\) para entrar na base e \(x_5\) para sair:
\(L_3 \leftarrow L_3/2\)
\(L_1 \leftarrow L_1 + 3L_3\)
\(L_2 \leftarrow L_2 + L_3\)
\(L_4 \leftarrow L_4 + 3L_3\)
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| 6 | 0 | 0 | 1/2 | 3/2 | 0 | 10 | |
| \(x_2\) | 3 | 1 | 0 | 1/2 | 1/2 | 0 | 4 |
| \(x_3\) | 1 | 0 | 1 | -1/2 | 1/2 | 0 | 2 |
| \(x_6\) | 6 | 0 | 0 | 1/2 | 3/2 | 1 | 16 |
Temos a solução ótima com \(x_B^T = [x_2,x_3,x_6] = [4,2,16]\) e \(x_N^T = [x_1,x_4,x_5] = [0,0,0]\) e valor da função objetivo de \(z=-10\). Lembrando, como o problema original era de máximização (e portanto fizemos a transformação da função), temos que o valor para o problema original é \(z = 10\).
EXEMPLO 6 (Katta Murty)
Resolva o PL com o auxilio do Excel (não use o solver, resolva o Simplex usando as planilhas para ajudar), em seguida confira o resultado usando o solver GUSEK:
\[\begin{align} \text{min $z$ = } & 12x_1 -10x_2 -30 x_3 \\ s.a &\\ & -3x_1 + 2x_2 + 8x_3 \leq 17\\ & -1x_1 + x_2 + 3x_3 \leq 9\\ & -2x_1 + x_2 + 8x_3 \leq 16\\ & x_1,x_2,x_3 \in \mathbb{R}^+ \end{align}\]
SOLUÇÃO
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| 12 | -10 | -30 | 0 | 0 | 0 | 0 | |
| \(x_4\) | -3 | 2 | 8 | 1 | 0 | 0 | 17 |
| \(x_5\) | -1 | 1 | 3 | 0 | 1 | 0 | 9 |
| \(x_6\) | -2 | 1 | 8 | 0 | 0 | 1 | 16 |
\(x_3\) entra e \(x_6\) sai da base.
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| 4 1/2 | 6 1/4 | 0 | 0 | 0 | 3 3/4 | 60 | |
| \(x_4\) | -1 | 1 | 0 | 1 | 0 | -1 | 1 |
| \(x_5\) | -1/4 | 5/8 | 0 | 0 | 1 | -3/8 | 3 |
| \(x_3\) | -1/4 | 1/8 | 1 | 0 | 0 | 1/8 | 2 |
\(x_2\) entra e \(x_4\) sai da base.
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| -1 3/4 | 0 | 0 | 6 1/4 | 0 | -2 1/2 | 66 1/4 | |
| \(x_2\) | -1 | 1 | 0 | 1 | 0 | -1 | 1 |
| \(x_5\) | 3/8 | 0 | 0 | -5/8 | 1 | 1/4 | 2 3/8 |
| \(x_3\) | -1/8 | 0 | 1 | -1/8 | 0 | 1/4 | 1 7/8 |
\(x_6\) entra e \(x_3\) sai da base.
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| -3 | 0 | 10 | 5 | 0 | 0 | 85 | |
| \(x_2\) | -1 1/2 | 1 | 4 | 1/2 | 0 | 0 | 8 1/2 |
| \(x_5\) | 1/2 | 0 | -1 | -1/2 | 1 | 0 | 1/2 |
| \(x_6\) | -1/2 | 0 | 4 | -1/2 | 0 | 1 | 7 1/2 |
\(x_1\) entra e \(x_5\) sai da base.
| VB | X1 | X2 | X3 | X4 | X5 | X6 | b |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 4 | 2 | 6 | 0 | 88 | |
| \(x_2\) | 0 | 1 | 1 | -1 | 3 | 0 | 10 |
| \(x_1\) | 1 | 0 | -2 | -1 | 2 | 0 | 1 |
| \(x_6\) | 0 | 0 | 3 | -1 | 1 | 1 | 8 |
Com solução ótima \(x_B^T = [x_2,x_1,x_6] = [10,1,8], x_N^T = [x_3,x_4,x_5] = [0,0,0]\)
EXEMPLO 7 (irrestrito - Katta Murty)
Resolva o PL com o auxilio do Excel (não use o solver, resolva o Simplex usando as planilhas para ajudar), em seguida confira o resultado usando o solver GUSEK:
\[\begin{align} \text{max $z$ = } & 3x_1 + 11x_2 + 9x_3 -x_4 - 29x_5 \\ s.a &\\ & \quad \quad x_2 + x_3 + x_4 - 2x_5 \leq 4\\ & x_1 - x_2 + x_3 + 2x_4 + x_5 \leq 0 \\ & x_1 + x_2 + x_3 \quad \quad - 3x_5 \leq 1 \\ & x_1 \text{ irrestrito}, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \\ \end{align}\]
SOLUÇÃO
Passando para a forma padrão, com a substituição de variáveis:
\[\begin{cases} x_1 = x_1^+ - x_1^- \\ x_1^+ \geq 0 \\ x_1^- \geq 0 \end{cases}\]Temos:
\[\begin{align} \text{min $z$ = } & -3(x_1^+ - x_1^-) - 11x_2 - 9x_3 + x_4 + 29x_5 \\ s.a &\\ & \quad \quad \quad \quad \quad x_2 + x_3 + x_4 - 2x_5 + x_6 \quad \quad = 4\\ & (x_1^+ - x_1^-) - x_2 + x_3 + 2x_4 + x_5 \quad + x_7 \quad = 0 \\ & (x_1^+ - x_1^-) + x_2 + x_3 \quad \quad - 3x_5 \quad \quad +x_8 = 1 \\ & x_1^+,x_1^-, x_2, x_3, x_4, x_5 \in \mathbb{R}^+ \\ \end{align}\]
| VB | X1p | X1n | X2 | X3 | X4 | X5 | X6 | X7 | X8 | b |
|---|---|---|---|---|---|---|---|---|---|---|
| -3 | 3 | -11 | -9 | 1 | 29 | 0 | 0 | 0 | 0 | |
| \(x_6\) | 0 | 0 | 1 | 1 | 1 | -2 | 1 | 0 | 0 | 4 |
| \(x_7\) | 1 | -1 | -1 | 1 | 2 | 1 | 0 | 1 | 0 | 0 |
| \(x_8\) | 1 | -1 | 1 | 1 | 0 | -3 | 0 | 0 | 1 | 1 |
\(x_2\) entra na base e \(x_8\) sai:
| VB | X1p | X1n | X2 | X3 | X4 | X5 | X6 | X7 | X8 | b |
|---|---|---|---|---|---|---|---|---|---|---|
| 8 | -8 | 0 | 2 | 1 | -4 | 0 | 0 | 11 | 11 | |
| \(x_6\) | -1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | -1 | 3 |
| \(x_7\) | 2 | -2 | 0 | 2 | 2 | -2 | 0 | 1 | 1 | 1 |
| \(x_2\) | 1 | -1 | 1 | 1 | 0 | -3 | 0 | 0 | 1 | 1 |
\(x_1^-\)(X1n) entra na base e \(x_6\) sai da base:
| VB | X1p | X1n | X2 | X3 | X4 | X5 | X6 | X7 | X8 | b |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 2 | 9 | 4 | 8 | 0 | 3 | 35 | |
| \(x_1^-\) | -1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | -1 | 3 |
| \(x_7\) | 0 | 0 | 0 | 2 | 4 | 0 | 2 | 1 | -1 | 7 |
| \(x_2\) | 0 | 0 | 1 | 1 | 1 | 2 | 1 | 0 | 0 | 4 |
Temos a solução básica \(x_B^T = [x_1^-,x_7,x_2] = [3,7,4]\) com custo de -35. Retomando a variável \(x_1\) original, temos que \(x_1\) = -3.
EXEMPLO 8 (teórico - Katta Murty)
Considere o seguinte PL, já na tabela Simplex:
\[\begin{aligned} &\begin{array}{cccc} \hline \hline x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & b \\ \hline 0 & 0 & 0 & {\color{red}\delta} & 3 & {\color{red}\gamma} & {\color{red}\zeta} & 0 \\ 0 & 1 & 0 & {\color{red}\alpha} & 1 & 0 & 3 & {\color{red}\beta} \\ 0 & 0 & 1 & -2 & 2 & {\color{red}\Delta} & -1 & 2 \\ 1 & 0 & 0 & 0 & -1 & 2 & 1 & 3\\ \hline \end{array} \end{aligned}\]
Os valores de \[{\color{red}\alpha}, {\color{red}\beta}, {\color{red}\gamma}, {\color{red}\delta}, {\color{red}\Delta},{\color{red}\zeta}\] são parâmetros na tabela. Todas as questões abaixo são independentes.Defina o intervalo dos parâmetros que farão as proposições abaixo verdadeiras, considerando que as variáveis básicas são: \[x_B^T = [x_2,x_3,x_1]\]
A primeira restrição indica que o problema é infactível.
\(x_B\) é factível, porém não é ótima.
\(x_B\) é factível, e a tabela indica que o problema é ilimitado.
\(x_B\) é factível, \(x_6\) é um candidato a entrar na base, e quando \(x_6\) entrar, \(x_3\) deixa a base.
A solução atual é ótima, porém o problema tem multiplas soluções ótimas, uma delas com \(x_7\) na base.
SOLUÇÃO
Para o problema ser infactível, a solução básica não pode ser factível, ou seja: \[\beta < 0\]
Para que \(x_B\) não seja ótimo, deve existir algum \(c_j <0\), ou seja: \[(\delta < 0)\cup(\gamma < 0)\cup(\zeta < 0)\]
Para que o problema seja ilimitado, \(A_{\bullet s} \leq 0\), em que \(s\) é a coluna da variável que entra na base. Olhando para todos os \(A_{\bullet s}\), percebe-se que a única possibilidade é com \(x_4\) entrando na base, assim: \[(\delta < 0) \cap (\delta = min\{\delta,\gamma,\zeta\}) \cap (\alpha \leq 0)\]
\[(\gamma < 0) \cap (\gamma = min\{\delta,\gamma,\zeta\})\cap(2/\Delta < 3/2)\]
Para que o problema tenha multiplas soluções ótimas, o custo (\(c_j\)) de uma variável não-basica deve ser 0. No caso o custo de \(x_7\): \[\zeta = 0\]