H2 Glossário de Termos Essenciais em Otimização

Glossário de Termos Essenciais em Otimização

Tipos de Modelos e Hipóteses

• Determinísticos

  Todas as variáveis e parâmetros são assumidos como certos e disponíveis. Não há incerteza ou risco.

• Probabilísticos ou Estocásticos

  Uma ou mais variáveis ou parâmetros têm algum grau de incerteza. O tratamento da incerteza ou risco é feito através de variáveis aleatórias ou randômicas.

• Dedutiva

  Parte de hipóteses sobre as variáveis, parâmetros e suas relações. Modelagem de cima para baixo (da teoria para os fatos). O conhecimento do modelador é fundamental.

• Programação Linear (PL)

  Programação Matemática em que todas as funções-objetivo e restrições são representadas por funções lineares.

• Programação Não Linear

  Programação Matemática em que pelo menos uma das funções-objetivo ou restrições é representada por funções não lineares.

Hipóteses Fundamentais da Programação Linear

• Hipótese de Aditividade

  Considera as atividades (variáveis de decisão) do modelo como entidades totalmente independentes, não permitindo interdependência entre elas, isto é, não permitindo a existência de termos cruzados, tanto na função-objetivo quanto nas restrições.

• Proporcionalidade

  O valor da função-objetivo é diretamente proporcional ao nível de atividade de cada variável de decisão, isto é, o valor da função-objetivo se altera de um valor constante dada uma variação constante da variável de decisão.

• Divisibilidade

  Assume que todas as variáveis de decisão (unidades de atividades) podem ser divididas em qualquer nível de fracionamento, isto é, qualquer variável de decisão pode assumir qualquer valor positivo fracionário.

• Hipótese de Certeza

  Assume que todos os parâmetros do modelo são constantes conhecidas. Em problemas reais, quase nunca é satisfeita, provocando a necessidade de análise de sensibilidade dos resultados.

Tipos de Solução e Viabilidade

• Solução

  Qualquer especificação de valores para as variáveis de decisão, independentemente de se tratar de uma escolha desejável.

• Solução Viável

  Uma solução em que todas as restrições são satisfeitas.

• Solução Inviável

  Uma solução em que alguma das restrições ou das condições de não-negatividade não é atendida.

• Solução Ótima

  É uma solução viável especial. Aquela que produz o valor da função-objetivo otimizando é chamada de ótima. Tem o valor mais favorável da função-objetivo, $f(x)$, isto é, maximiza ou minimiza a função-objetivo. Pode ser única ou não.

• Soluções Múltiplas

  Ocorre quando mais de uma solução viável leva a função-objetivo ao mesmo valor ótimo.

• Região Ilimitada

  O polígono da região não está fechado. Geralmente relacionada a um problema que foi mal modelado.

• Região Inviável

  Quando o conjunto de soluções viáveis é vazio. Na ausência de soluções viáveis, não há também soluções ótimas. Significa que as restrições são rigorosas.

• Restrições Redundantes

  Quando sua exclusão do conjunto de restrições não altera o conjunto de soluções viáveis de um problema.

Método Simplex e Teoremas Fundamentais

• Método Simplex, Teorema 1

  O conjunto de todas as soluções viáveis de um modelo de Programação Linear forma um conjunto convexo.

• Teorema 2

  Se a função-objetivo possui um único ótimo finito, então esta solução ótima é um ponto extremo do conjunto convexo de soluções viáveis.

• Teorema 3

  Se a função-objetivo assume o ótimo em mais de um ponto extremo do conjunto de soluções viáveis, então ela assume o mesmo valor para qualquer ponto do segmento de reta que une esses pontos extremos.

Análise de Sensibilidade e Solver

A análise de sensibilidade é geralmente apresentada em relatórios que cobrem:

• Relatório de Resposta: Focado na Função-Objetivo.
• Sensibilidade: Focada nas Variáveis de Decisão.
• Limites: Focados nas Restrições.

Restrições Comuns no Solver

• Int (Inteiro): Variáveis devem assumir valores inteiros.
• Bin (Binário): Variáveis devem assumir valor 0 ou 1.
• Dif (Diferente): As variáveis citadas na referência de célula devem ser diferentes umas das outras.

Preço-Sombra

Para o recurso $i$, mede o valor marginal deste recurso em relação ao lucro total. É a quantidade que o valor ótimo da função-objetivo ($Z$) seria melhorado, caso a quantidade do recurso $i$ ($b_i$) fosse aumentada de uma unidade. É a quantidade pela qual a função-objetivo é alterada, dado um incremento de uma unidade na constante da restrição, assumindo que todos os outros coeficientes e constantes permanecem inalterados.

No Excel, o preço-sombra pode ser positivo, zero ou negativo e está relacionado ao valor nominal do efeito na função-objetivo (quanto a função-objetivo aumenta ou diminui em valor absoluto).

Custo Reduzido

A quantidade total que o coeficiente da variável na função-objetivo deve melhorar para que ela deixe de ser zero na solução ótima. É a penalização que deverá ser paga para tornar uma variável não básica em básica.

• Se o Custo Reduzido for positivo, subtrair o mesmo do coeficiente da função-objetivo.
• Se o Custo Reduzido for negativo, adicionar o mesmo ao coeficiente da função-objetivo.

Solução Degenerada

Ocorre quando o valor de incremento (acréscimo permissível) e decremento (decréscimo permissível) de uma restrição é igual a zero. A presença de degeneração altera a interpretação da análise de sensibilidade em um certo número de maneiras.

Coluna Limite Inferior e Superior

• Limite Inferior: Indica o menor valor que cada variável pode assumir, considerando que todas as outras não se alterem, para que a solução continue viável.
• Limite Superior: Indica o maior valor que cada variável pode assumir, mantendo a solução viável.

Modelos de Rede

• Rede

  Coleção de diagramas (conjunto de vértices) ou nós ligados entre si por um conjunto de arcos. Utilizada em transportes, energia e comunicação para modelagem de diversos tipos de problemas.

• Regra de Fluxo Balanceado

  Regra utilizada para modelar as restrições. Para cada nó da rede, estabelece-se a diferença entre as variáveis que estão chegando (entradas) ao nó menos as variáveis que estão deixando o nó (saídas). O lado direito das restrições serão as ofertas ou demandas de cada nó. (Nota: O valor de oferta/demanda em cada nó é igual a zero, exceto nos nós de origem e destino.)

• Menor Caminho

  Problema onde os arcos significam a distância entre dois pontos (nós) e se deseja achar a rota que une esses pontos com a menor distância.

• Fluxo Máximo

  Problema onde se deseja o maior fluxo de uma grandeza que possa fluir de um determinado nó para outro. Mais de um caminho pode ser utilizado simultaneamente. Aplica-se na rede de distribuição de água, luz, gás e tráfego na internet.

Programação Inteira

• Programação Inteira

  Problemas de Programação Matemática em que a função-objetivo, bem como as restrições, são lineares, porém uma ou mais variáveis de decisão são representadas apenas por valores inteiros.

• Inteira Total

  Todas as variáveis de decisão são do tipo inteiro.

• Inteira Mista

  Apenas uma parte das variáveis é do tipo inteiro, enquanto as outras são do tipo real.

• Problema Relaxado

  A todo problema de Programação Linear Inteira está associado um problema com a mesma função-objetivo e as mesmas restrições, com exceção da condição de variáveis inteiras. Em um problema de maximização, o valor ótimo da função-objetivo do problema relaxado sempre representa um limite superior. Em um problema de minimização, o valor ótimo representa um limite inferior.

  Importante: Nenhum ponto inteiro vizinho ao ponto ótimo relaxado é necessariamente viável. Mesmo que um dos vizinhos seja viável, ele pode não ser o ponto ótimo inteiro, não sendo obrigatoriamente uma solução aceitável.

Controle de Estoques (Modelo de Lote Econômico - EOQ)

• Solução Ótima da Programação Não Linear

  Diferentemente da Programação Linear, a solução ótima pode ser qualquer ponto do conjunto de soluções viáveis.

• Modelo de Lote Econômico (EOQ)

  Modelo de controle de estoques que assume que a demanda (ou uso) de um produto é praticamente constante durante o ano e que cada novo pedido deve chegar (de uma vez) no exato instante em que o estoque chega a zero. O objetivo é determinar, pelo balanceamento dos custos associados ao estoque, o tamanho e a periodicidade do pedido que minimizam o custo total.

Custos Associados ao Estoque

• Custo de Manutenção de Estoque

  Custo por se manter o capital no estoque e não em outra aplicação, rendendo benefícios financeiros para a empresa.

• Custo de Pedido

  Custo associado ao trabalho de efetuar o pedido de um determinado produto. Engloba custo de mão de obra, de transporte do pedido e outros, como controle do recebimento e controle de quantidade do lote recebido.

• Custo de Falta

  Custo relacionado a perdas decorrentes da interrupção da produção devido à falta de produto.