Simplex - Glossário

Autor

Luciane Ferreira Alcoforado

Data de Publicação

17 de fevereiro de 2025

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 ()

Contadores Simplex : é um índice que fornece o mapeamento da partição do sistema matricial do modelo de programação linear em que Bi,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; Ni,i=1,2,...,nm 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 xN e cN que formará o particionamento não básico dos correspondentes vetores x e c. MORI; BRAUN ()

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 CNj=C^NjλTaNj,j=1,2,...,mn. MORI; BRAUN ()

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 ()

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=B1ak, sendo k o índice da variável não básica selecionada para entrar na base. MORI; BRAUN ()

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 ai1x1+ai2x2+...+ainxn=bi

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.

A=[a11a12a1na21a22a2nam1am2amn]

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 ()

  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 (ou) 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 c1x1+...+cnxn

Sujeito a

a11x1+...+a1nxn (,,=) b1, R1

a21x1+...+a2nxn (,,=) b2, R2

...

am1x1+...+amnxn (,,=) bm, Rm

xi0 (i=1,2,...,n)

Multiplicador Simplex : é um vetor auxiliar denominado λ obtido da solução do sistema BTλ=cB que será usado para obter os custos relativos da função objetivo do modelo. MORI; BRAUN ()

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 cTx

Sujeito a Ax=b, x0, 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 nm 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 ()

Pressupostos da Programação Linear : é composto de 4 hipóteses, PIZZOLATO; GANDOLPHO (), MORI; BRAUN ()

  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 é, CNj0,j=1,2,...,mn 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 é, yBj0,j=1,2,...,m o que significa que o problema não tem solução ótima. MORI; BRAUN ()

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 BxB=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 xNk em uma certa iteração do método Simplex, obtido através do cálculo de ϵz=xBzyz,z=1,2,...m e yz>0. MORI; BRAUN ()

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 ai1x1+...+ainxnxn+1=bi, será adicionada uma variável artificial xa1 tal que a nova restrição passará a ser ai1x1+...+ainxnxn+1+xa1=bi

Variável de excesso : é uma variável positiva adicionada ao modelo para garantir a igualdade em uma restrição do tipo ai1x1+...+ainxnbi, tornando-a ai1x1+...+ainxnxn+1=bi.

Variável de folga : é uma variável positiva adicionada ao modelo para garantir a igualdade em uma restrição do tipo ai1x1+...+ainxnbi, tornando-a ai1x1+...+ainxn+xn+1=bi.

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 nm 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 nm 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.

c=[c1c2...cn]

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

b=[b1b2...bm]

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

x=[x1x2...xn]

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.