Simplex - Glossário
Atualização da Base : procedimento do método Simplex que ocorre quando trocamos a variável que deixará de ser básica (escolhida por possuir o menor tamanho do passo) pela variável que passará a ser básica (escolhida por possuir o menor custo relativo).
Construção de um Modelo : processo que vai desde avaliar a natureza do problema; interrogar pessoas envolvidas; levantar dados; identificar os contornos do problema; entender relações de causa e efeito, construir o modelo através de equações matemáticas. PIZZOLATO; GANDOLPHO (2009)
Contadores Simplex : é um índice que fornece o mapeamento da partição do sistema matricial do modelo de programação linear em que \(B_i, i=1,2,...,m\) representa o índice de cada coluna de A que formará a particão básica, ou seja, a matriz B, assim como os índices de cada posição dos vetores x_B e c_B que formará o particionamento básico dos correspondentes vetores x e c; \(N_i, i=1, 2, ..., n-m\) representa o índice de cada coluna de A que formará a particão não básica, ou seja, a matriz N, assim como os índices de cada posição dos vetores \(x_N\) e \(c_N\) que formará o particionamento não básico dos correspondentes vetores x e c.
Critério de Otimalidade : reflete o objetivo principal da otimização do problema.
Custo Relativo : é o custo de uma variável não básica em uma certa iteração do método Simplex, obtido através do cálculo de \(C_{Nj} = \hat C_{Nj}-\lambda^Ta_{Nj}, j=1,2,...,m-n\)
Decisão : curso de ação escolhido pela pessoa, como o meio mais efetivo à sua disposição para alcançar os objetivos procurados, ou seja, para resolver o problema que a incomoda. ANDRADE (2000)
Direção Simplex : fornece a taxa de variação de cada uma das variáveis básicas em função da perturbação na k-ésima variável não básica em uma certa iteração do método Simplex, obtido através do cálculo de \(y = B^{-1}a_k\), sendo k o índice da variável não básica selecionada para entrar na base.
Forma Canônica : Estrutura do sistema de restrições no qual esteja embutida a matriz identidade, garantindo assim uma solução trivial para as variáveis associadas às colunas da matriz identidade.
Forma Padrão : Estrutura mátemática que representa as restrições do problema por meio de equações lineares, ou seja, a i-ésima restrição na forma padrão é representada por \(a_{i1}x_1+a_{i2}x_2+...+a_{in}x_n=b_i\)
Função Objetivo : expressa o critério de otimalidade, escrita em termos das variáveis de decisão do problema. A função objetivo é uma função linear que deverá ser otimizada, ou seja, maximizada ou minimizada.
Matriz Básica : resultado do particionamento da matriz A que é formada pelos coeficientes das restrições de um modelo de otimização linear, em geral a matriz básica é representada pela letra B, sendo uma matriz quadrada e inversível. No método Simplex B é usada para calcular a solução básica viável numa dada iteração.
Matriz dos coeficientes : é a matriz que representa os coeficientes das restrições de um modelo de programação linear.
\[\begin{split} A= & \begin{bmatrix} a_{11}& ...& a_{1n}\\ a_{21}& ...& a_{2n}\\ ...& ...& ...\\ a_{m1}& ...& a_{mn} \end{bmatrix} \end{split}\]Método Simplex : desenvolvido por Dantzig em 1947 é um algoritmo que realiza a busca pela solução ótima de um problema de programação linear, podendo encontrar uma única solução, infinitas soluções, solução ilimitada ou solução infactível.
Metodologia da Pesquisa Operacional : é composta de cinco etapas, PIZZOLATO; GANDOLPHO (2009)
Identificação do problema
Construção do modelo
Determinação da solução do modelo
Teste e validação da solução proposta
Implementação da solução
Modelo Matemático de Otimização Linear : constituído por uma expressão linear denominada de função objetivo e por um conjunto de expressões lineares, ou restrições, envolvendo as variáveis de decisão. As restrições lineares podem ser relações de desigualdades (\(\le ou \ge)\) ou de igualdade (\(=\)), podendo ocorrer os três tipos de relações em um mesmo modelo. Sua estrutura genérica possui a forma a seguir.
Min ou Max \({c_{1}x_1+ ... +c_{n}x_n}\)
Sujeito a
\(a_{11}x_1+ ... +a_{1n}x_n\) \((\le, \ge,=)\) \(b_1\), \(R_1\)
\(a_{21}x_1+ ... +a_{2n}x_n\) \((\le, \ge,=)\) \(b_2\), \(R_2\)
\(...\)
\(a_{m1}x_1+ ... +a_{mn}x_n\) \((\le, \ge,=)\) \(b_m\), \(R_m\)
\(x_i \ge0\) \((i=1,2,...,n)\)
Multiplicador Simplex : é um vetor auxiliar denominado \(\lambda\) obtido da solução do sistema \(B^T\lambda=c_B\) que será usado para obter os custos relativos da função objetivo do modelo. MORI; BRAUN (2021)
Notação Matricial de um modelo de otimização linear : é a representação das expressões lineares em estrutura matricial, considerando o modelo na forma padrão.
Min ou Max \(c^Tx\)
Sujeito a \(Ax=b\), \(x\ge0\), em que
\(A\) é a matriz dos coeficientes
\(c\) é o vetor de custos
\(x\) é o vetor das variáveis de decisão
\(b\) é o vetor de recursos
Partição Básica : é o particionamento realizado na estrutura matricial de um modelo de programação linear na forma padrão tal que \(n-m\) posições formarão a parte Não Básica da matriz A e dos vetores c e x e as demais posições formarão a parte Básica.
Pesquisa Operacional : conjunto de métodos para resolver problemas inicialmente de operações militares e atualmente em problemas envolvendo a tomada de decisão aplicados às mais diversas áreas do conhecimento. Consiste basicamente em construir um modelo de um sistema real existente como meio de analisar e compreender o comportamento dessa situação, com o objetivo de levá-lo a apresentar o desempenho que se deseja. ANDRADE (2000)
Pressupostos da Programação Linear : é composto de 4 hipóteses, PIZZOLATO; GANDOLPHO (2009), MORI; BRAUN (2021)
Os coeficientes numéricos são constantes no modelo (CERTEZA)
Divisibilidade das variáveis, ou seja, as variáveis podem assumir valores reais (FRACIONAMENTO OU DIVISIBILIDADE)
Proporcionalidade, significa que o valor da função-objetivo é diretamente proporcional ao valor de cada variável de decisão pela qual não há economias nem perdas de escala (PROPORCIONALIDADE)
Aditividade, significa que o resultado de um problema de Otimização Linear será o resultado somado das diversas atividades que compõe o problema sem haver sinergia, ou seja, os coeficientes de cada variável são fixos e independem dos demais. (ADITIVIDADE)
Região de Factibilidade : é a região do espaço \(ℝ^n\) que contém todas as soluções factíveis.
Regra de Parada do Simplex : há duas regras de parada, quando todos os custos relativos forem maiores ou iguais a zero, isto é, \(C_{Nj}\ge0, j=1,2,...,m-n\) o que significa que a solução ótima foi obtida ou quando todos os componentes da direção simplex forem menores ou iguais a zero, isto é, \(y_{Bj}\le0, j=1,2,...,m\) o que significa que o problema não tem solução ótima. MORI; BRAUN (2021)
Restrições de Sinal : valores pré-estabelecidos no domínio dos números reais (isto é, valores positivos, negativos ou ambos).
Restrições Estruturais : um conjunto de restrições que determina a região de soluções factíveis (viáveis) para o problema. Os valores assumidos pelas variáveis de decisão devem satisfazer a esse conjunto de restrições.
Solução Básica : é uma solução obtida pela solução do sistema \(Bx_B=b\) em que B é a matriz básica de um modelo de programação linear e b é o vetor de recursos.
Solução Factível : solução possível para o sistema de restrições do modelo, é aquela que atende a todas as restrições ao mesmo tempo.
Solução Gráfica : método de solução restrito a problemas de duas variáveis que oferece elementos para facilitar a compreensão dos procedimentos do método Simplex.
Solução Infactível : refere-se a um conjunto de restrições incompatíveis, significa que o conjunto viável é vazio, ou seja, não há nenhum ponto que satisfaça todas a restrições ao mesmo tempo.
Solução Ótima : é a melhor solução dentre as soluções factíveis para o modelo.
Solução Viável : é o mesmo que solução factível, solução possível para o sistema de restrições do modelo, é aquela que atende a todas as restrições ao mesmo tempo.
Tamanho de Passo : é o limitante para o valor de crescimento de uma variável não básica \(x_{Nk}\) em uma certa iteração do método Simplex, obtido através do cálculo de \(\epsilon_z={\frac{x_{Bz}}{y_z}}, z=1,2,...m\) e \(y_z>0\). MORI; BRAUN (2021)
Variáveis de Decisão : um conjunto de variáveis manipuláveis no procedimento de busca pelo ótimo.
Variável Artificial : é uma variável positiva adicionada ao modelo para garantir a forma canônica do modelo, isto é, garantir a formação de uma matriz identidade a partir da seleção de algumas variáveis do modelo. É adicionada sempre que uma variável de excesso for acrescentada ao modelo. Por exemplo,em uma restrição do tipo \(a_{i1}x_1+ ... +a_{in}x_n-x_{n+1} = b_i\), será adicionada uma variável artificial \(x_{a1}\) tal que a nova restrição passará a ser \(a_{i1}x_1+ ... +a_{in}x_n-x_{n+1}+x_{a1}= b_i\)
Variável de excesso : é uma variável positiva adicionada ao modelo para garantir a igualdade em uma restrição do tipo \(a_{i1}x_1+ ... +a_{in}x_n \ge b_i\), tornando-a \(a_{i1}x_1+ ... +a_{in}x_n-x_{n+1} = b_i\).
Variável de folga : é uma variável positiva adicionada ao modelo para garantir a igualdade em uma restrição do tipo \(a_{i1}x_1+ ... +a_{in}x_n \le b_i\), tornando-a \(a_{i1}x_1+ ... +a_{in}x_n+x_{n+1} = b_i\).
Vértice Viável : um vetor de variáveis associado ao modelo de programação linear na forma padrão que soluciona o sistema \(Ax=b\) e tal que \(n-m\) variáveis assumem o valor zero e as demais possuem valores maiores ou iguais a zero.
Vértice : um vetor de variáveis associado ao modelo de programação linear na forma padrão em que \(n-m\) variáveis assumem o valor zero.
Vetor Custo : é o vetor que representa os coeficientes da função objetivo de um modelo de programação linear.
\[\begin{split} c= & \begin{bmatrix} c_{1}\\ c_{2}\\ ...\\ c_{n} \end{bmatrix} \end{split}\]Vetor de Recursos : é o vetor que representa os limites de recursos de um modelo de programação linear.
\[\begin{split} b= & \begin{bmatrix} b_{1}\\ b_{2}\\ ...\\ b_{m} \end{bmatrix} \end{split}\]Vetor de Variáveis : é o vetor que representa as variáveis de decisão de um modelo de programação linear.
\[\begin{split} x= & \begin{bmatrix} x_{1}\\ x_{2}\\ ...\\ x_{n} \end{bmatrix} \end{split}\]