Pesquisa Operacional - PEOP

AULA 20: RESOLVENDO PROBLEMAS LINEARES POR MEIO DO MÉTODO SIMPLEX

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 das aulas anteriores
  • Formulário do Simplex
  • Exercícios.

Revisão de conceitos

Escolha a alternativa correta

1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa

  1. Um modelo matemático de otimização linear contendo 5 variáveis de decisão e 4 restrições do tipo “\(\le\)” terá na forma padrão um total de \(n=9\) variáveis incluindo as de folga.

  2. Uma variável de folga é aquela que minimiza a função objetivo.

  3. Um vértice viável em um problema de maximização permanece viável se multiplicarmos a função objetivo desse problema por \(-1\).

  4. A restrição \(2x_1+3x_2\ge10\) é equivalente a \(2x_1+3x_2+x_3=10\) com \(x_1,x_2,x_3\ge0\)

  5. Quando um problema de programação linear apresenta uma solução viável, podemos afirmar que existe pelo menos um vértice ótimo.

Confira sua resposta

1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa

  1. Um modelo matemático de otimização linear contendo 5 variáveis de decisão e 4 restrições do tipo “\(\le\)” terá na forma padrão um total de \(n=9\) variáveis incluindo as de folga. (V)

  2. Uma variável de folga é aquela que minimiza a função objetivo. (F)

  3. Um vértice viável em um problema de maximização permanece viável se multiplicarmos a função objetivo desse problema por \(-1\). (V)

  4. A restrição \(2x_1+3x_2\ge10\) é equivalente a \(2x_1+3x_2+x_3=10\) com \(x_1,x_2,x_3\ge0\) (F)

  5. Quando um problema de programação linear apresenta uma solução viável, podemos afirmar que existe pelo menos um vértice ótimo. (F)

Explique o que está errado nas afirmativas falsas

  1. Uma variável de folga é aquela que minimiza a função objetivo. (F)

  2. A restrição \(2x_1+3x_2\ge10\) é equivalente a \(2x_1+3x_2+x_3=10\) com \(x_1,x_2,x_3\ge0\) (F)

  3. Quando um problema de programação linear apresenta uma solução viável, podemos afirmar que existe pelo menos um vértice ótimo. (F)

Confira sua resposta

  • Uma variável de folga é um recurso matemático para tornar uma inequação do tipo \(\le\) em uma equação, por exemplo \(2x_1+3x_2\le10\) se torna \(2x_1+3x_2+x_3=10\) com o acréscimo da variável de folga \(x_3\), supondo que \(x_1,x_2,x_3\ge0\)

  • A restrição \(2x_1+3x_2\ge10\) é equivalente a \(2x_1+3x_2-x_3=10\) com \(x_1,x_2,x_3\ge0\) pois a inequação é do tipo \(\ge\) e portanto devemos subtrair uma variável de excesso, no caso \(x_3\)

  • Quando um problema de programação linear apresenta uma solução viável, NÃO podemos afirmar que existe pelo menos um vértice ótimo pois o problema pode ser ilimitado e não apresentar uma solução ótima. (Veja o último exercício da aula anterior)

O primeiro passo do Simplex

Reescrever o problema na forma padrão:

  • Função objetivo deve ser de minimização

  • As restrições devem estar na forma \(Ax=b\)

  • Os vetores \(x\) e \(b\) devem ser positivos.

Exercício 1

Coloque o problema na forma padrão

\(max\) \(z=x_1+x_2\)

Sujeito a:

\(1x_1+x_2\le6\)

\(1x_1-1x_2\le4\)

\(-1x_1+1x_2\le4\)

\(x_1,x_2\ge0\)

Exercício 1 - resposta

Coloque o problema na forma padrão

\(max\) \(z=x_1+x_2\)

Sujeito a:

\(1x_1+x_2\le6\)

\(1x_1-1x_2\le4\)

\(-1x_1+1x_2\le4\)

\(x_1,x_2\ge0\)

\(min\) \(z=-x_1-x_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\)

Exercício 2

Reescreva na forma matricial, apresentando todos os elementos matriciais do modelo.

\(min\) \(z=-x_1-x_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\)

Exercício 2 - resposta

Reescreva na forma matricial, apresente todos elementos matriciais do modelo.

\(min\) \(z=-x_1-x_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\)

\(min\) \(z=c^T\cdot x\)

Sujeito a:

\(A\cdot x= b\), \(x\ge 0\)

Tal que:

\(c^T=(-1,-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} \]

Exercício 3: Solução Gráfica

Indique a solução ótima com base no gráfico.

Exercício 3 - Resposta Esperada

Considerando que a região viável é formada pelos polígono com vértices \((0,0)\), \((0,3)\), \((1.82,4.09)\) e \((10,0)\) e que se existe uma solução ótima então será um destes vértices.

Com base no gráfico observamos que a restrição 3 é paralela à curva de nível (\(z=10\)) e todos os pontos (por exemplo \((6,2)\)) que pertencem ao segmento de reta entre os vértices \((1.82, 4.09)\) e \((10,0)\) são soluções ótimas para o problema, resultando em \(z^*=10\).

Portanto este problema possui infinitas soluções ótimas.

Exercício 3a: Solução via algoritmo simplex

Considere o problema anterior que foi resolvido pelo método gráfico. Obtenha a solução pelo método simplex.

1a. iteração produzirá \(I_N=\{1,2\}\) e \(I_B=\{3,4\}\) \(x^T=(0,0,30,10)\) com \(z=0\)

2a. iteração produzirá \(I_N=\{1,3\}\) e \(I_B=\{2,4\}\) \(x^T=(0,3,0,4)\) com \(z=-6\)

3a. iteração produzirá \(I_N=\{4,3\}\) e \(I_B=\{2,1\}\) \(x^T=(1.82,4.09,0,0)\) com \(z=-10\)

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}\)

Exercício 3a: Particionamento - 1a. iteração

\(I_N=\{1,2\}\) e \(I_B=\{3,4\}\). Apresente os elementos matriciais deste particionamento sabendo que: \(c^T=(-1,-2,0,0,0)\)

\(x=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{bmatrix} \]

\(b=\) \[ \begin{bmatrix} 30 \\ 10 \end{bmatrix} \]

\(A=\) \[ \begin{bmatrix} -6 &10 &1 &0\\ 1 &2 & 0 &1\\ \end{bmatrix} \]

Resposta

\(I_N=\{1,2\}\) e \(I_B=\{3,4\}\)

O particionamento será:

\(c_B^T=(c_{3},c_{4} )=(0,0)\) e \(c_N^T=(c_{1},c_{2})=(-1,-2)\)

\(x_B=\) \[ \begin{bmatrix} x_{3} \\ x_{4} \end{bmatrix} \]

\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \\ \end{bmatrix} \]

\(B=\) \[ \begin{bmatrix} 1 & 0 \\ 0 & 1\\ \end{bmatrix} \]

\(N=\) \[ \begin{bmatrix} -6 & 10 \\ 1 & 2 \end{bmatrix} \]

Exercício 3a: Obter a solução corrente

1a. iteração: \(I_N=\{1,2\}\) e \(I_B=\{3,4\}\)

Solução corrente deve apresentar o vetor \(x^T=(x_1,x_2,x_3,x_4)\), especificando TODOS OS VALORES. Resolva \(Bx_B=b\):

\[\begin{bmatrix} 1 &0 \\ 0&1 \end{bmatrix}\begin{bmatrix} x_3 \\ x_4 \end{bmatrix}=\begin{bmatrix} 30 \\ 10 \end{bmatrix}\]

obtendo \(x_3=30, x_4=10\). Como as variáveis não básicas são sempre nulas na iteração, \(x_1=x_2=0\) e \(x^T=(0,0,30,10)\)

Exercício 3a: Obter os custos relativos

1a. iteração: \(I_N=\{1,2\}\) e \(I_B=\{3,4\}\)

Para testar a OTIMALIDADE, verificar se os custos relativos são todos positivos,

\(C'_{N_i}\ge0\) para todos os índices \(I_N\)

\(B^{T}\lambda = c_B\)

\[\begin{bmatrix} 1 &0 \\ 0&1 \end{bmatrix}\begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} \rightarrow \begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} 0 \\ 0 \end{bmatrix}\]

\(C'_{N_i}=c_{N_i}-\lambda^T a_{N_i}\)

\[C'_{1}=c_{1}-\lambda^T a_{1}= -1-\begin{bmatrix} 0&0 \end{bmatrix}\begin{bmatrix} -6 \\ 1 \end{bmatrix}=-1\]

\[C'_{2}=c_{2}-\lambda^T a_{2}= -2-\begin{bmatrix} 0&0 \end{bmatrix}\begin{bmatrix} 10 \\ 2 \end{bmatrix}=-2\]

Como todos são negativos conclui-se que a solução corrente não é ótima, continua a busca em direção ao ótimo.

Exercício 3a: Escolher qual variável entrará na base na próxima iteração

A variável associada ao menor custo relativo deve entrar na base. No caso \(C´_2 = -2\) é o menor valor, logo \(x_2\) entrará na base e anotamos \(k=2\) representando o índice da variável que entrará na base.

Exercício 3a: Obter a direção simplex e o menor tamanho de passo

1a. iteração: \(I_N=\{1,2\}\) e \(I_B=\{3,4\}, k=2\)

Para testar se é possível obter um novo vértice, deve verificar se há pelo menos um tamanho de passo positivo, ou seja, a variável associada ao menor tamanho de passo positivo deve sair da base.

\[By=a_k\rightarrow By=a_2\rightarrow\begin{bmatrix} 1 &0 \\ 0&1 \end{bmatrix}\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=\begin{bmatrix} 10 \\ 2 \end{bmatrix} \rightarrow \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=\begin{bmatrix} 10 \\ 2 \end{bmatrix}\]

\[\epsilon_z=\frac{x_{Bz}}{y_z}\rightarrow \epsilon_1=\frac{x_{B1}}{y_1}=\frac{x_{3}}{y_1}=\frac{30}{10}=3\space e \space \epsilon_2=\frac{x_{B2}}{y_2}=\frac{x_{4}}{y_2}=\frac{10}{2}=5\] No caso \(\epsilon_1= 3\) é o menor valor positivo, logo \(x_3\) sairá da base, anotamos \(s=3\) como o índice da variável que sairá da base.

Exercício 3a: Particionamento - 2a. iteração

Trocamos os índices \(k=2\) e \(s=3\) obtendo-se: \(I_N=\{1,3\}\) e \(I_B=\{2,4\}\).

O particionamento será:

\(c_B^T=(c_{2},c_{4} )=(-2,0)\) e \(c_N^T=(c_{1},c_{3})=(-1,0)\)

\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{4} \end{bmatrix} \]

\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{3} \\ \end{bmatrix} \]

\(B=\) \[ \begin{bmatrix} 10 & 0 \\ 2 & 1\\ \end{bmatrix} \]

\(N=\) \[ \begin{bmatrix} -6 & 1 \\ 1 & 0 \end{bmatrix} \]

Exercício 3a: Obter a solução corrente

2a. iteração: \(I_N=\{1,3\}\) e \(I_B=\{2,4\}\)

Solução corrente deve apresentar o vetor \(x^T=(x_1,x_2,x_3,x_4)\), especificando TODOS OS VALORES. Resolva \(Bx_B=b\):

\[\begin{bmatrix} 10 &0 \\ 2&1 \end{bmatrix}\begin{bmatrix} x_2 \\ x_4 \end{bmatrix}=\begin{bmatrix} 30 \\ 10 \end{bmatrix}\]

obtendo \(x_2=3, x_4=4\). Como as variáveis não básicas são sempre nulas na iteração, \(x_1=x_3=0\) e \(x^T=(0,3,0,4)\)

Exercício 3a: Obter os custos relativos

2a. iteração: \(I_N=\{1,3\}\) e \(I_B=\{2,4\}\)

Para testar a OTIMALIDADE, verificar se os custos relativos são todos positivos,

\(C'_{N_i}\ge0\) para todos os índices \(I_N\)

\(B^{T}\lambda = c_B\)

\[\begin{bmatrix} 10 &2 \\ 0&1 \end{bmatrix}\begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} -2 \\ 0 \end{bmatrix} \rightarrow \begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} -0.2 \\ 0 \end{bmatrix}\]

\(C'_{N_i}=c_{N_i}-\lambda^T a_{N_i}\)

\[C'_{1}=c_{1}-\lambda^T a_{1}= -1-\begin{bmatrix} -0.2&0 \end{bmatrix}\begin{bmatrix} -6 \\ 1 \end{bmatrix}=-2.2\]

\[C'_{3}=c_{3}-\lambda^T a_{3}= 0-\begin{bmatrix} -0.2&0 \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix}=0.2\]

Como há um custo negativo conclui-se que a solução corrente não é ótima, continua a busca em direção ao ótimo.

Exercício 3a: Escolher qual variável entrará na base na próxima iteração

A variável associada ao menor custo relativo deve entrar na base. No caso \(C´_1 = -2.2\) é o menor valor, logo \(x_1\) entrará na base e anotamos \(k=1\) representando o índice da variável que entrará na base.

Exercício 3a: Obter a direção simplex e o menor tamanho de passo

2a. iteração: \(I_N=\{1,3\}\) e \(I_B=\{2,4\}, k=1\)

Para testar se é possível obter um novo vértice, deve verificar se há pelo menos um tamanho de passo positivo, ou seja, a variável associada ao menor tamanho de passo positivo deve sair da base.

\[By=a_k\rightarrow By=a_1\rightarrow\begin{bmatrix} 10 &0 \\ 2&1 \end{bmatrix}\begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=\begin{bmatrix} -6 \\ 1 \end{bmatrix} \rightarrow \begin{bmatrix} y_1 \\ y_2 \end{bmatrix}=\begin{bmatrix} -0.6 \\ 2.2 \end{bmatrix}\]

\[\epsilon_z=\frac{x_{Bz}}{y_z}\rightarrow \epsilon_1=\frac{x_{B1}}{y_1}=\frac{x_{2}}{y_1}=\frac{3}{-0.6}=-5\space e \space \epsilon_2=\frac{x_{B2}}{y_2}=\frac{x_{4}}{y_2}=\frac{4}{2.2}=1.82\] No caso \(\epsilon_1= 1.82\) é o único valor positivo, logo \(x_4\) sairá da base, anotamos \(s=4\) como o índice da variável que sairá da base.

Exercício 3a: Particionamento - 3a. iteração

Trocamos os índices \(k=1\) e \(s=4\) obtendo-se: \(I_N=\{4,3\}\) e \(I_B=\{2,1\}\).

O particionamento será:

\(c_B^T=(c_{2},c_{1} )=(-2,-1)\) 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} 10 & -6 \\ 2 & 1\\ \end{bmatrix} \]

\(N=\) \[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \]

Exercício 3a: Obter a solução corrente

3a. iteração: \(I_N=\{4,3\}\) e \(I_B=\{2,1\}\)

Solução corrente deve apresentar o vetor \(x^T=(x_1,x_2,x_3,x_4)\), especificando TODOS OS VALORES. Resolva \(Bx_B=b\):

\[\begin{bmatrix} 10 &-6 \\ 2&1 \end{bmatrix}\begin{bmatrix} x_2 \\ x_1 \end{bmatrix}=\begin{bmatrix} 30 \\ 10 \end{bmatrix}\]

obtendo \(x_2=4.09, x_1=1.82\). Como as variáveis não básicas são sempre nulas na iteração, \(x_3=x_4=0\) e \(x^T=(1.82,4.09,0,0)\)

Exercício 3a: Obter os custos relativos

3a. iteração: \(I_N=\{4,3\}\) e \(I_B=\{2,1\}\)

Para testar a OTIMALIDADE, verificar se os custos relativos são todos positivos,

\(C'_{N_i}\ge0\) para todos os índices \(I_N\)

\(B^{T}\lambda = c_B\)

\[\begin{bmatrix} 10 &2 \\ -6&1 \end{bmatrix}\begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} -2 \\ -1 \end{bmatrix} \rightarrow \begin{bmatrix} \lambda_1 \\ \lambda_2 \end{bmatrix}=\begin{bmatrix} 0.0 \\ -1 \end{bmatrix}\]

\(C'_{N_i}=c_{N_i}-\lambda^T a_{N_i}\)

\[C'_{4}=c_{4}-\lambda^T a_{4}= 0-\begin{bmatrix} 0.0&-1 \end{bmatrix}\begin{bmatrix} 0 \\ 1 \end{bmatrix}=1\]

\[C'_{3}=c_{3}-\lambda^T a_{3}= 0-\begin{bmatrix} 0&-1 \end{bmatrix}\begin{bmatrix} 1 \\ 0 \end{bmatrix}=0\]

Como todos os custos são positivo, atingimos a regra de otimalidade. Portanto a solução corrente é ótima.

Quando na regra de parada obtemos algum custo relativo nulo, significa que podemos encontrar outro vértice ótimo. Neste caso, o problema terá infinitas soluções ótimas.

Revise

  • Terminou? Revise os conceitos desta aula.

  • Verifique se permanece alguma dúvida sobre como representar matricialmente um problema e colocá-lo na forma padrão.

  • Faça os exercícios propostos no moodle.

https://rpubs.com/LucianeA/Aula20_PEOP