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. MORI; BRAUN (2021)

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 }^T{a}_{Nj},j=1,2,...,m-n$. MORI; BRAUN (2021)

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. MORI; BRAUN (2021)

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{array}{rl}A=& \left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]\end{array}$$

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)

1. Identificação do problema

2. Construção do modelo

3. Determinação da solução do modelo

4. Teste e validação da solução proposta

5. 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\ge 0$ $(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^{T}x$

Sujeito a $Ax=b$, $x\ge 0$, 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)

1. Os coeficientes numéricos são constantes no modelo (CERTEZA)

2. Divisibilidade das variáveis, ou seja, as variáveis podem assumir valores reais (FRACIONAMENTO OU DIVISIBILIDADE)

3. 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)

4. 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}\ge 0,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}\le 0,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 $B{x}_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 ${ϵ}_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{array}{rl}c=& \left[\begin{array}{c}{c}_1\\ c_2\\ ...\\ c_n\end{array}\right]\end{array}$$

Vetor de Recursos : é o vetor que representa os limites de recursos de um modelo de programação linear.

$$\begin{array}{rl}b=& \left[\begin{array}{c}{b}_1\\ b_2\\ ...\\ b_m\end{array}\right]\end{array}$$

Vetor de Variáveis : é o vetor que representa as variáveis de decisão de um modelo de programação linear.

$$\begin{array}{rl}x=& \left[\begin{array}{c}{x}_1\\ x_2\\ ...\\ x_n\end{array}\right]\end{array}$$

Referências

ANDRADE, Eduardo Leopoldo. Introdução à Pesquisa Operacional: Métodos e Modelos para a Análise de Decisão. Rio de Janeiro: LTC, 2000.

MORI, Renata Belluzzo Z.; BRAUN, José F. Notas de Aula de Pesquisa Operacional. Pirassununga-SP: Academia da Força Aérea, 2021.

PIZZOLATO, Nélio D.; GANDOLPHO, André Alves. Técnicas de Otimização. Rio de Janeiro: LTC, 2009.