flowchart LR
A{A origem é solução viável?} -->|Sim| B
A -->|Não| C[Use o método Simplex Duas Fases]
B[Procure por outro vértice] --> H
H{Encontrou novo vértice?} -->|Sim| D
H --> |Não| I
D{O vértice é ótimo?} -->|Sim| E
D --> |Não| B
E[PARE! Solução Ótima!]
I[PARE! Não há Solução Ótima!]
Teoria de Decisão I
AULA 7: Método Simplex
Profa. Luciane Alcoforado
PPGEC/UFF
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
- Representação Matricial do modelo.
- Forma Padrão.
- Variáveis de Folga.
- A lógica do Algoritmo Simplex
- Exercícios.
Revisão de conceitos
Escolha a alternativa correta
1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa
Um modelo matemático de otimização linear deve conter 4 itens a saber: critério de otimalidade, variáveis de decisão, função objetivo e restrições.
Definição das variáveis é item obrigatório. A falta da definição ou a definição errada das varáveis de decisão invalida o modelo matemático.
Definir a variável de decisão como \(x_i = ingrediente \space i\) é uma forma correta e precisa no modelo matemático.
A função objetivo do modelo de programação linear pode ser expressa por min \(z= x_1^2+x_2^2\)
Quando um problema de programação linear apresenta uma solução ótima, podemos afirmar que existe pelo menos um vértice ótimo.
Confira sua resposta
1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa
Um modelo matemático de otimização linear deve conter 4 itens a saber: critério de otimalidade, variáveis de decisão, função objetivo e restrições. (V)
Definição das variáveis é item obrigatório. A falta da definição ou a definição errada das varáveis de decisão invalida o modelo matemático. (V)
Definir a variável de decisão como \(x_i = ingrediente \space i\) é uma forma correta e precisa no modelo matemático. (F)
A função objetivo do modelo de programação linear pode ser expressa por min \(z= x_1^2+x_2^2\). (F)
Quando um problema de programação linear apresenta uma solução ótima, podemos afirmar que existe pelo menos um vértice ótimo. (V)
O modelo matemático e sua representação matricial
Critério de otimalidade: minimizar o custo
\(x_i =\) quantidade (unidades) produzida do produto i, \(i=1,2\)
A função objetivo, assim como as restrições podem ser representadas na forma matricial.
\(min\) \(z=-3x_1-4x_2\)
Sujeito a:
\(-5x_1-3x_2\le2\)
\(-3x_1+4x_2\le5\)
\(0x_1+1x_2\le2\)
\(x_1,x_2\ge0\)
\(min\) \(z=c^T\cdot x\)
Sujeito a:
\(A\cdot x\le b\), \(x\ge 0\)
Tal que:
\(c^T=(c_1,...,c_n)\); \(x^T=(x_1,...,x_n)\); \(b^T=(b_1,...,b_m)\) e \(A=\) \[ \begin{bmatrix} a_{11} &... & a_{1n} \\ ... & ... & ...\\ a_{m1} &... & a_{mn} \end{bmatrix} \]
Graficamente
Notação Matricial
\(c^T=(c_1,...,c_n)\) é o vetor de custos.
\(x=\) \[ \begin{bmatrix} x_{1} \\ ... \\ x_{n} \end{bmatrix} \] é o vetor de variáveis de decisão.
\(b=\) \[ \begin{bmatrix} b_{1} \\ ... \\ b_{m} \end{bmatrix} \] é o vetor de recursos.
\(A=\) \[ \begin{bmatrix} a_{11} &... & a_{1n} \\ ... & ... & ...\\ a_{m1} &... & a_{mn} \end{bmatrix} \] é a matriz dos coeficientes.
\(a_{j}=\) \[ \begin{bmatrix} a_{1j} \\ ... \\ a_{mj} \end{bmatrix} \] é o vetor da j-ésima coluna da matriz A.
Forma Padrão
\(min\) \(z=c^T\cdot x\)
Sujeito a:
\(A\cdot x = b\), \(x\ge0\) e \(b\ge0\)
- a função objetivo linear deve ser minimizada;
- as restrições do problema são definidas por um sistema de equações lineares;
- as condições de não negatividade de todas as variáveis de decisão complementam as restrições do problema.
1- Nem todos os modelos matemáticos estarão na forma padrão.
2- Qualquer um deles poderá ser escrito na forma padrão
Manipulações Matemáticas
Maximizar \(z=c^T\cdot x\) é equivalente a Minimizar \(-z = -c^T\cdot x\)
Restrições de desigualdade do tipo \(a_{i1}x_1+...+a_{in}x_n\)\(\le\) \(b_i\) tornam-se igualdade ao inserir variáveis de folga \(x_{Fi}\), tal que \(a_{i1}x_1+...+a_{in}x_n\) \(+x_{Fi}\)\(= b_i\) \(i=1,2,...,n\)
Restrições de desigualdade do tipo \(a_{i1}x_1+...+a_{in}x_n\)\(\ge\) \(b_i\) tornam-se igualdade ao inserir variáveis de excesso \(x_{Fi}\), tal que \(a_{i1}x_1+...+a_{in}x_n\) \(-x_{Fi}\)\(= b_i\) \(i=1,2,...,n\)
O problema passará a ter \(n+m\) variáveis.
Exemplo
\(min\) \(z=3x_1+4x_2\)
Sujeito a:
\(-5x_1-3x_2\le2\)
\(-3x_1+4x_2\le5\)
\(0x_1+1x_2\le2\)
\(x_1,x_2\ge0\)
Na forma padrão ficará:
\(min\) \(z=3x_1+4x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(-5x_1-3x_2\)\(+1x_3\)\(+0x_4+0x_5=2\)
\(-3x_1+4x_2+0x_3\)\(+1x_4\)\(+0x_5=5\)
\(0x_1+1x_2+0x_3+0x_4+\)\(+1x_5\)\(=2\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
Forma Matricial:
\(c^T=(3,4,0,0,0)\)
\(A=\) \[ \begin{bmatrix} -5 &-3 &1&0&0 \\ -3 &4 &0&1&0 \\ 0 &1 &0&0&1 \\ \end{bmatrix} \]
\(x=\) \[ \begin{bmatrix} x_{1} \\ ... \\ x_{5} \end{bmatrix} \]
\(b=\) \[ \begin{bmatrix} 2 \\ 5 \\ 2 \end{bmatrix} \]
Execício
Coloque o problema na padrão e apresente a os elementos matriciais.
\(max\) \(z=x_1+x_2\)
Sujeito a:
\(x_1+x_2\le6\)
\(x_1-x_2\le4\)
\(-x_1+x_2\le4\)
\(x_1,x_2\ge0\)
Resposta
\(max\) \(z=x_1+x_2\)
Sujeito a:
\(x_1+x_2\le6\)
\(x_1-x_2\le4\)
\(-x_1+x_2\le4\)
\(x_1,x_2\ge0\)
Na forma padrão ficará:
\(min\) \(z=-x_1-x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(x_1+x_2+1x_3+0x_4+0x_5=6\)
\(x_1-x_2+0x_3+1x_4+0x_5=4\)
\(-x_1+x_2+0x_3+0x_4+1x_5=4\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
Forma Matricial:
\(c^T=(-1,-1,0,0,0)\)
\(A=\) \[ \begin{bmatrix} 1 &1 &1&0&0 \\ 1 &-1 &0&1&0 \\ -1 &1 &0&0&1 \\ \end{bmatrix} \]
\(x=\) \[ \begin{bmatrix} x_{1} \\ ... \\ x_{5} \end{bmatrix} \]
\(b=\) \[ \begin{bmatrix} 6 \\ 4 \\ 4 \end{bmatrix} \]
A lógica do algoritmo Simplex
Considerando que o problema esteja na forma padrão, os passos do algoritmo são:
1- Encontrar uma solução factível inicial. A fim de garantir a factibilidade dessa solução, o método simplex parte sempre da origem dos eixos coordenados.
2- A estratégia simplex prevê a busca nos vértices da região de factibilidade afinal se existe solução ótima existe também um vértice ótimo.
3- Se for possível o simplex parte de um vértice factível em direção a outro melhor e assim sucessivamente, buscando sempre encontrar um vértice ótimo.
4- A busca é interrompida quando:
- a solução ótima é encontrada ou
- o método simplex verificar que o modelo não apresenta solução ótima.
Esquematicamente
Particionamento dos elementos matriciais
Considere um problema de minimização com \(n'\) variáveis de decisão, \(m\) restrições do tipo \(\le\) e portanto \(m\) variáveis de folga. O número total de variáveis do problema na forma padrão será \(n=n'+m\)
Sempre que iniciamos uma iteração realizamos um particionamento dos elementos matriciais de tal forma que teremos uma parte denominada básica e outra parte denominada não básica.
O mapeamento deste particionamento é guiado pelos índices:
\(I_N\) = índices dos elementos da partição não básica.
\(I_B\) = índices dos elementos da partição básica.
\(I_N\cup I_B=\{1,2,...,n\}\)
Os elementos particionados
Seja \(I_N\) e \(I_B\) os índices dos elementos da partição não básica e básica respectivamente
O vetor de custos será particionado em \(c^T=[c^T_B \space c^T_N]\). O vetor \(x\) será particionado em \(x^T=[x^T_B \space x^T_N]\). A matriz \(A\) será particionada em \(A=[B \space N]\).
Tal que:
\(c_B^T=(c_{I_{B_1}},...,c_{I_{B_m}})\) e \(c_N^T=(c_{I_{N_1}},...,c_{I_{N_{n-m}}})\)
\(x_B=\) \[ \begin{bmatrix} x_{I_{B_1}} \\ ... \\ x_{I_{B_m}} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{I_{N_1}} \\ ... \\ x_{I_{N_{n-m}}} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{1I_{B_1}} &... & a_{1I_{B_m}} \\ ... & ... & ...\\ a_{mI_{B_1}} &... & a_{mI_{B_m}} \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} a_{1I_{N_1}} &... & a_{1I_{N{m-n}}} \\ ... & ... & ...\\ a_{mI_{N_1}} &... & a_{mI_{N{m-n}}} \end{bmatrix} \]
Exemplo de Particionamento
\(min\) \(z=3x_1+4x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(-5x_1+3x_2+1x_3+0x_4+0x_5=2\)
\(-3x_1+4x_2+0x_3+1x_4+0x_5=5\)
\(0x_1+1x_2+0x_3+0x_4+1x_5=2\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
Suponha \(I_N=\{1,5\}\) e \(I_B=\{3,4,2\}\)
O particionamento será:
\(c_B^T=(c_{3},c_{4},c_{2} )=(0,0,4)\) e \(c_N^T=(c_{1},c_{5})=(3,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{3} \\ x_{4} \\ x_{2} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{5} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{13} &a_{14} & a_{12} \\ a_{23} &a_{24} & a_{22} \\ a_{33} &a_{34} & a_{32} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1 &0 & 3 \\ 0 &1 & 4 \\ 0 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 0 \\ -3 & 0 \\ 0 & 1 \end{bmatrix} \]
A primeira iteração: SOLUÇÃO CORRENTE
1- Sempre que as restrições do problema forem do tipo \(\le\), a origem é uma solução viável, ou seja, \(x_1=x_2=...=x_n'=0\). O primeiro particionamento será:
\(I_N=\{1,2,...,n'\}\) e \(I_B=\{n'+1,n'+2, ..., m\}\)
Para obtermos a solução corrente desse particionamento resolvemos o sistema \(Bx_B=b\) ou seja \(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
As variáveis não básicas são sempre NULAS
Qualquer iteração
1- Obter a solução corrente resolvendo
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
2- Calcular o custo relativo e verificar a regra de otimalidade \(C'_{N_i}>0 \space \forall i\in I_N\)
\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)
\(\lambda = B^{T^-1}c_B\)
3- Se a regra de otimalidade foi atingida a solução corrente é ótima. Caso contrário devemos realizar a troca da base para obtermos um novo vértice:
Entra na base a variável não básica com o menor custo relativo. Chamaremos seu índice de \(k\)
Sai da base a variável básica com o menor tamanho de passo. Chamaremos seu índice de \(s\)
Obtendo o tamanho de passo
- Calculamos a direção simplex \(y\)
\(y=B^{-1}a_k\)
- Calculamos o tamanho de passo \(\epsilon\)
\(\epsilon_z=x_{Bz}/y_z\)
Regra de Parada: Não Existe \(\epsilon>0\)? PARE! Não há solução ótima.
Caso contrário, a variável básica com o menor \(\epsilon>0\) deixará a base. Chamaremos seu índice de \(s\).
Os novos contadores serão atualizados, considerando tal mudança e nova iteração será iniciada com \(I_N=\{1,2,...,n'\}-\{k\}\cup \{s\}\) e \(I_B=\{n'+1,n'+2, ..., m\}-\{s\}\cup \{k\}\)
Resolvendo um problema passo a passo
\(min\) \(z=-3x_1-4x_2+0x_3+0x_4+0x_5\)
Sujeito a:
\(-5x_1+3x_2+1x_3+0x_4+0x_5=2\)
\(-3x_1+4x_2+0x_3+1x_4+0x_5=5\)
\(0x_1+1x_2+0x_3+0x_4+1x_5=2\)
\(x_1,x_2,x_3,x_4,x_5\ge0\)
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)
Obtendo o particionamento
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)
O particionamento será:
\(c_B^T=(c_{3},c_{4},c_{5} )=(0,0,0)\) e \(c_N^T=(c_{1},c_{2})=(-3,-4)\)
\(x_B=\) \[ \begin{bmatrix} x_{3} \\ x_{4} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{2} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{13} &a_{14} & a_{15} \\ a_{23} &a_{24} & a_{25} \\ a_{33} &a_{34} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 1 &0 & 0 \\ 0 &1 & 0 \\ 0 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 3 \\ -3 & 4 \\ 0 & 1 \end{bmatrix} \]
Obtendo a solução corrente
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
A=cbind(a1=c(-5,-3,0), a2=c(3,4,1), a3=c(1,0,0), a4=c(0,1,0), a5=c(0,0,1))
IN=c(1,2);IB=c(3,4,5)
B=A[,IB];B a3 a4 a5
[1,] 1 0 0
[2,] 0 1 0
[3,] 0 0 1 [,1]
x3 2
x4 5
x5 2A solução corrente será \(x=(\) 0, 0, 2, 5, 2).
Verificando a otimalidade
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\)
\(C'_{N_i}>0 \space \forall i\in I_N\)?
\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] 0
[2,] 0
[3,] 0cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -3 -4Os custos relativos são negativos, logo a solução corrente não é ótima.
Obtendo um novo vértice
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\) e \(cN'=\) (-3, -4)
O menor custo relativo é -4 e corresponde a \(k=\) 2. Logo a variável não básica da posição 2 de \(I_N\), \(x_{IN_{k}}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
1a. Iteração
\(I_N=\{1,2\}\) e \(I_B=\{3,4,5\}\) e \(cN'=\) (-3, -4) e \(\epsilon=\) (0.6666667, 1.25, 2)
O menor tamanho de passo positivo é 0.6666667 e corresponde a \(s=\) 3. Logo a variável básica da posição 1 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.
Fim da primeira iteração com \(k=\) 2, \(s=\) 3,
\(I_N=\{1,2\}-\{k\}\cup \{s\}\) e \(I_B=\{3,4,5\}-\{s\}\cup \{k\}\)
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)
Segunda Iteração passo a passo
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)
O particionamento será:
\(c_B^T=(c_{2},c_{4},c_{5} )=(-4,0,0)\) e \(c_N^T=(c_{1},c_{3})=(-3,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{4} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{1} \\ x_{3} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{14} & a_{15} \\ a_{22} &a_{24} & a_{25} \\ a_{32} &a_{34} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 &0 & 0 \\ 4 &1 & 0 \\ 1 &0 & 1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} -5 & 1 \\ -3 & 0 \\ 0 & 0 \end{bmatrix} \]
Obtendo a solução corrente
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
a2 a4 a5
[1,] 3 0 0
[2,] 4 1 0
[3,] 1 0 1 [,1]
x2 0.6666667
x4 2.3333333
x5 1.3333333A solução corrente será \(x=(\) 0, 0.67, 0, 2.33, 1.33).
Verificando a otimalidade
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\)
\(C'_{N_i}>0 \space \forall i\in I_N\)?
\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] -1.333333
[2,] 0.000000
[3,] 0.000000cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -9.666667 1.333333Os custos relativos são negativos, logo a solução corrente não é ótima.
## Obtendo um novo vértice {.smaller .scrollable}
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(cN'=\) (-9.6666667, 1.3333333)
O menor custo relativo é -9.6666667 e corresponde a \(k=\) 1. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
2a. Iteração
\(I_N=\{1,3\}\) e \(I_B=\{2,4,5\}\) e \(cN'=\) (-9.6666667, 1.3333333) e \(\epsilon=\) (-0.4, 0.6363636, 0.8)
O menor tamanho de passo positivo é 0.6363636 e corresponde a \(s=\) 4. Logo a variável básica da posição 2 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.
Fim da segunda iteração com \(k=\) 1, \(s=\) 4,
\(I_N=\{1,3\}-\{k\}\cup \{s\}\) e \(I_B=\{2,4,5\}-\{s\}\cup \{k\}\)
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)
Terceira Iteração passo a passo
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)
O particionamento será:
\(c_B^T=(c_{2},c_{1},c_{5} )=(-4,-3,0)\) e \(c_N^T=(c_{4},c_{3})=(0,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{1} \\ x_{5} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_{3} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{11} & a_{15} \\ a_{22} &a_{21} & a_{25} \\ a_{32} &a_{31} & a_{35} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 & -5 &0 \\ 4 & -3 &0 \\ 1 & 1 &1 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ 0 & 0 \end{bmatrix} \]
Obtendo a solução corrente
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
a2 a1 a5
[1,] 3 -5 0
[2,] 4 -3 0
[3,] 1 0 1 [,1]
x2 1.7272727
x1 0.6363636
x5 0.2727273A solução corrente será \(x=(\) 0.64, 1.73, 0, 0, 0.27).
Verificando a otimalidade
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\)
\(C'_{N_i}>0 \space \forall i\in I_N\)?
\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] 2.181818
[2,] -2.636364
[3,] 0.000000cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] 2.636364 -2.181818Os custos relativos são negativos, logo a solução corrente não é ótima.
Obtendo um novo vértice
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\) e \(cN'=\) (2.6363636, -2.1818182)
O menor custo relativo é -2.1818182 e corresponde a \(k=\) 3. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
3a. Iteração
\(I_N=\{4,3\}\) e \(I_B=\{2,1,5\}\) e \(cN'=\) (2.6363636, -2.1818182) e \(\epsilon=\) (-6.3333333, -1.75, 1)
O menor tamanho de passo positivo é 1 e corresponde a \(s=\) 5. Logo a variável básica da posição 3 de \(I_B\), \(x_{I_{B_{s}}}\) deixa a base.
Fim da segunda iteração com \(k=\) 3, \(s=\) 5,
\(I_N=\{4,3\}-\{k\}\cup \{s\}\) e \(I_B=\{2,1,5\}-\{s\}\cup \{k\}\)
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)
Quarta Iteração passo a passo
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)
O particionamento será:
\(c_B^T=(c_{2},c_{1},c_{3} )=(-4,-3,0)\) e \(c_N^T=(c_{4},c_{5})=(0,0)\)
\(x_B=\) \[ \begin{bmatrix} x_{2} \\ x_{1} \\ x_{3} \end{bmatrix} \]
\(x_N=\) \[ \begin{bmatrix} x_{4} \\ x_{5} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} a_{12} &a_{11} & a_{13} \\ a_{22} &a_{21} & a_{23} \\ a_{32} &a_{31} & a_{33} \end{bmatrix} \]
\(B=\) \[ \begin{bmatrix} 3 & -5 &1 \\ 4 & -3 &0 \\ 1 & 1 &0 \end{bmatrix} \]
\(N=\) \[ \begin{bmatrix} 0 & 0 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} \]
Obtendo a solução corrente
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)
\(x_B=B^{-1}b\) e \(x_N=\overrightarrow{0}\).
a2 a1 a3
[1,] 3 -5 1
[2,] 4 -3 0
[3,] 1 0 0 [,1]
x2 2
x1 1
x3 1A solução corrente será \(x=(\) 1, 2, 1, 0, 0).
Verificando a otimalidade
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\)
\(C'_{N_i}>0 \space \forall i\in I_N\)?
\(C'_{N_i}=C_{N_i}-\lambda^T a_{N_i}\)
\(\lambda = B^{T^-1}c_B\)
[,1]
[1,] 0
[2,] 1
[3,] -8cN_relativo=NULL
for (i in seq_along(cN))
cN_relativo[i] = cN[i] - t(lambda)%*%A[,IN[i]]
cN_relativo[1] -1 8Os custos relativos são negativos, logo a solução corrente não é ótima.
Obtendo um novo vértice
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\) e \(cN'=\) (-1, 8)
O menor custo relativo é -1 e corresponde a \(k=\) 4. Logo a variável não básica k, \(x_{I_{N_k}}\) entra na base.
Obtendo o tamanho do passo:
Quem sai da base
4a. Iteração
\(I_N=\{4,5\}\) e \(I_B=\{2,1,3\}\) e \(cN'=\) (-1, 8) e \(\epsilon=\) (, -3, -0.6)
Como não é possível obter um tamanho de passo positivo (note que o tamanho de \(\epsilon_1 \rightarrow \infty\) indica uma direção de crescimento ilimitado),este fato indica que a solução é ilimitada e portanto não é possível obter um valor ótimo.
Fim da quarta iteração , o problema não tem solução ótima, apenas soluções viáveis.
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 a seguir.
Exercícios Propostos
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}\)
1) Escolha a alternativa correta
1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa
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.
Uma variável de folga é aquela que minimiza a função objetivo.
Um vértice viável em um problema de maximização permanece viável se multiplicarmos a função objetivo desse problema por \(-1\).
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\)
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
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)
Uma variável de folga é aquela que minimiza a função objetivo. (F)
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)
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)
Quando um problema de programação linear apresenta uma solução viável, podemos afirmar que existe pelo menos um vértice ótimo. (F)
2) Explique o que está errado nas afirmativas falsas
Uma variável de folga é aquela que minimiza a função objetivo. (F)
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)
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)
Lembrete: 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.
3) 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\)
3) resposta
\(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\)
4) 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\)
4) 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ícios sem resposta
Exercício 1: Solução Gráfica
Indique a solução ótima com base no gráfico.
Exercício 2: 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, mostrando o passo e passo do algoritmo, ou seja, todas as iterações até a regra de parada.
Mestrado em Engenharia Civil/UFF