Pesquisa Operacional - PEOP
AULA 30: RESOLVENDO PROBLEMAS LINEARES POR MEIO DO MÉTODO SIMPLEX E 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
- Revisão de conceitos
- Simplex Duas Fases
- Iterações do Simplex
- Solução Gráfica
Revisão de conceitos
A Forma Padrão
Um modelo matemático na forma padrão é sempre de minimização.
\[min \space z=c^T \cdot x\]
Sujeito a:
\[A\cdot x = b, \space \space x\ge 0\]
Variáveis de Folga, Excesso e Artificiais.
Variáveis de Folga são utilizadas em restrições do tipo \(\le\) e entram com coeficiente \(+1\) na restrição.
Variáveis de Excesso são utilizadas em restrições do tipo \(\ge\) e entram com coeficiente \(-1\) na restrição.
Variáveis Artificiais são utilizadas em restrições do tipo \(\ge\) ou \(=\) e entram com coeficiente \(+1\) na restrição. Neste caso serão utilizadas somente na fase 1 do método Simplex Duas fases.
Fase1 versus Fase 2
\[min \space z=c^T \cdot x\]
Sujeito a:
\[A\cdot x = b, \space \space x\ge 0\]
Supondo \[x^T= \begin{matrix}( \underbrace{x_1,x_2,...,x_{n'}, \space}_{n'} \underbrace{x_{f1},...,x_{fi}, \space}_{i} \underbrace{x_{e1},...,x_{ej} \space}_{j} ) \end{matrix} \] em que \(n'\) representa o número de variáveis de decisão do modelo, \(i\) representa o número de variáveis de folga do modelo na forma padrão e \(j\) representa o número de variáveis de excesso do modelo na forma padrão. Isso significa que na fase 1 haverá \(j\) variáveis artificiais relacionadas a cada variável de excesso.
- Função Objetivo do modelo da Fase 1
\(min \space w_a = 0x_1+...+0x_{e_j}\)
\(+1x_{a_1}+...+1x_{a_j}\)
- Função Objetivo do modelo da Fase 2
\(min \space z = c_1x_1+...+c_{n'}x_{n'}\)
\(+0x_{f_1}+...+0x_{e_j}\)
As restrições são sempre do tipo \(A\cdot x=b\), com valores apropriados para estes elementos matriciais.
Regras de Parada do Algoritmo Simplex
Regra 1: Verificar se a solução corrente é ótima através do teste
\(c'_j \ge 0\) para todo \(j \in I_N\) (custo relativo)
Se o teste for verdadeiro a solução corrente é ótima.
Regra 2: Verificar a possibilidade de um novo vértice melhor do que o atual
\(\epsilon_i > 0\) para algum \(i \in I_B\) (tamanho de passo)
Se o teste for verdadeiro realiza-se a troca da base; caso contrário conclui-se que não há solução ótima.
Ex1-Simplex Duas Fases
Considere o modelo:
min \(z=-10x_1-30x_2\)
Sujeito a
\(R_1: 1x_1 + 1x_2 \geq 50\)
\(R_2: 2x_1 + 1x_2 \leq 100\)
\(R_3: 0x_1 + 1x_2 \geq 10\)
\(R_4: 1x_1 + 0x_2 \geq 2\)
\(x_1,x_2 \geq 0\)
Apresente a função objetivo da primeira fase do algoritmo simplex, considerando as variáveis de folga, excesso e artificiais criadas. Deixe claro quem são estas variáveis.
Apresente o particionamento inicial da fase 1.
Apresente a solução corrente desta iteração.
Resposta
Restrições do modelo original:
\(R_1: 1x_1 + 1x_2 \geq 50\)
\(R_2: 2x_1 + 1x_2 \leq 100\)
\(R_3: 0x_1 + 1x_2 \geq 10\)
\(R_4: 1x_1 + 0x_2 \geq 2\)
Na forma padrão da fase 1 teremos:
\[x^T= \begin{matrix}( \underbrace{x_1,x_2, \space}_{decisão} \underbrace{x_3, \space}_{excesso} \underbrace{x_4, \space}_{folga} \underbrace{x_5,x_6, \space}_{excesso} \underbrace{x_7,x_8,x_9 \space}_{artificiais} ) \end{matrix} \]
Função Objetivo (fase 1): \(min \space w_a=0x_1+0x_2+0x_3+0x_4+0x_5+0x_6+1x_7+1x_8+1x_9\)
Particionamento Inicial (fase 1)
\(I_N=\{1,2,3,5,6\}\) e \(I_B=\{7,4,8,9\}\)
Solução Corrente (fase 1) \(B\cdot x_B=b\) e \(x_N=0\)
\(x^T=(0,0,0,100,0,0,50,10,2)\)
Ex2 - Iterações do Simplex
Considere o modelo na forma padrão. Analise as iterações e obtenha a solução ótima.
min \(z=c^Tx\)
Sujeito a: \(Ax=b\), \(x\geq 0\) com \(A=\begin{bmatrix} 1 &2 & 1& 0& 0 \\ 1 &0 & 0& 1& 0 \\ 3 &2 & 0& 0& 1 \end{bmatrix}\)
\(c^T=(-8,-10,0,0,0)\); \(x^T=(x_1,x_2,x_3,x_4,x_5)\); \(b^T=(6,8,20)\)
Os cálculos das iterações do algoritmo Simplex apresentam-se resumidos na Tabela
| Iteração | 1 | 2 | 3 |
|---|---|---|---|
| Contadores Não Básicos | \(I_N=\{1,2\}\) | \(I_N=\{1,3\}\) | \(I_N=\{2,3\}\) |
| Contadores Básicos | \(I_B=\{3,4,5\}\) | \(I_B=\{2,4,5\}\) | \(I_B=\{1,4,5\}\) |
| Custo Relativo \(c^T_N\) | \((-8, -10)\) | \((-3, 5)\) | \((6,8)\) |
| Tamanho de Passo | \((3,\infty, 10)\) | \((6,8,7)\) | - |
| \(x^T_B\) | \((6,8,20)\) | \((3,8,14)\) | calcule! |
Resposta
Na iteração 1, as variáveis básicas eram \(x_3,x_4,x_5\) com valores iguais a \((6,8,20)\) respectivamente. Analisando o custo relativo, conclui-se que a solução corrente não é ótima pois temos valores negativos, portanto o menor valor (\(c'_2=-10\) está associado a \(k=2\). Analisando o tamanho de passo, identificamos que o menor valor positivo (\(\epsilon_3=3\)) está associado a \(s=3\). Portanto \(x_2\) entra na base e \(x_3\) sai da base.
Na iteração 2, as variáveis básicas são \(x_2,x_4,x_5\) com valores iguais a \((3,8,14)\) respectivamente. Analisando o custo relativo, conclui-se que a solução corrente não é ótima pois temos valores negativos, portanto o menor valor (\(c'_1=-3\) está associado a \(k=1\). Analisando o tamanho de passo, identificamos que o menor valor positivo (\(\epsilon_2=6\)) está associado a \(s=2\). Portanto \(x_1\) entra na base e \(x_2\) sai da base.
Na iteração 3, as variáveis básicas são \(x_1,x_4,x_5\) com valores iguais a \((6,2,2)\) respectivamente que se obtém resolvendo \(B\cdot x_b=b\). Analisando o custo relativo, conclui-se que a solução corrente é ótima pois todos os valores são positivos e portanto o algoritmo termina com \(x^T=(6,0,0,2,2), z=-48\)
Ex3 - Iterações do Simplex
Resolva o mesmo problema anterior pelo método gráfico.
min \(z=c^Tx\)
Sujeito a: \(Ax=b\), \(x\geq 0\) com \(A=\begin{bmatrix} 1 &2 & 1& 0& 0 \\ 1 &0 & 0& 1& 0 \\ 3 &2 & 0& 0& 1 \end{bmatrix}\)
\(c^T=(-8,-10,0,0,0)\); \(x^T=(x_1,x_2,x_3,x_4,x_5)\); \(b^T=(6,8,20)\)
Resposta
1- Desenho o gráfico do modelo no plano cartesiano, considerando as seguintes restrições:
\(R_1: 1x_1+2x_2\le6\)
\(R_2: 1x_1+0x_2\le8\)
\(R_3: 3x_1+2x_2\le20\)
2- Identifique a região viável no primeiro quadrante.
3- Desenhe o vetor gradiente
4- Realize a busca no sentido oposto à seta do vetor gradiente pois o problema é de minimização.
5- Obtenha o vértice ótimo que será o ponto mais extremo dentro da região viável no sentido da busca, podendo ser identificado com melhor precisão desenhando-se as curvas de nível.
Sua resposta deve ser a mesma do exercício 2.
Gráfico
Região Viável: triângulo ABC, A=(0,0), B=(0,3) e C=(6,0). Vértice ótimo: (6,0). Valor ótimo: z=-48.
