Modelagem e Análise de Sensibilidade em Programação Linear

Processo de Modelagem em Programação Linear

Etapas para Modelar um Problema de Programação Linear

• Determinar e definir o objetivo (maximizar ou minimizar).
• Desenvolver a lista de opções.
• Definir as variáveis de decisão (X1, X2, ..., Xn).
• Desenvolver uma lista de restrições que as afetam.
• Definir a função objetivo, por exemplo: Max Z = 40X1 + 50X2.

Tipos de Restrições em Programação Linear

As restrições devem estabelecer limitações na disponibilidade de recursos e a necessidade de cumprir os compromissos para o período.

Restrições de Capacidade e/ou Disponibilidade de Recursos

São limites que são devidos às limitações do sistema em termos da quantidade de equipamentos, espaço, financiamento, matérias-primas e mão de obra disponível. Um exemplo seria a restrição que se refere à terra disponível para plantações. Estas restrições são expressas como limitações, ou desigualdades do tipo (≤). O que se lida com um recurso não pode ser maior do que o que temos disponível.

Restrições de Mercado

Existem limites (inferior, superior ou ambas) da quantidade de produto que pode ser vendido ou usado. Por exemplo, o máximo de vendas e o mínimo histórico para um produto. Este último seria um requisito ou uma desigualdade do tipo (≥), porque se houver um compromisso de vendas para um determinado produto, não se pode decidir produzir menos do que essa quantidade, pois não seria possível cumprir os compromissos de entrega. A primeira é uma restrição ou uma desigualdade do tipo (≤), pois não se deve produzir mais produto do que historicamente tem sido possível vender em cada época.

Restrições de Qualidade ou Composição de Misturas

Estas restrições limitam a mistura de ingredientes que geralmente definem a qualidade dos produtos resultantes. Podem ser de limitação (≤), requisitos (≥) ou requisitos mais restritivos do tipo (=).

Restrições de Tecnologia de Produção ou Balanço de Material

São restrições que definem a saída de um processo como uma função das entradas, muitas vezes com um desperdício ou perda de rendimento. Estas restrições, como as anteriores, também podem ser de limitação (≤), requisitos (≥) ou requisitos mais restritivos do tipo (=), o que depende do processo que está sendo modelado.

Restrições de Definição

Estas restrições definem uma variável como uma função das outras. Muitas vezes, essas restrições vêm de definições de contabilidade ou de equilíbrio de materiais, tais como a relação entre a quantidade de um produto, que deve ser igual ao que foi vendido mais o que sobrou em estoque. Estas restrições geralmente são requisitos do tipo (=).

Caracterização da Solução Ótima

Tipos de Restrições na Solução Ótima

• Restrições Ativas:

  São aquelas que definem diretamente a localização do ótimo.

• Restrições Não Ativas:

  Não estão diretamente envolvidas na determinação da localização ótima.

• Restrições Redundantes:

  São restrições não ativas que não participam diretamente ou sequer determinam os limites da zona de soluções viáveis.

Preço-Sombra da Restrição

O preço-sombra de uma restrição é uma medida quantitativa de como cada restrição influencia o valor ótimo da função objetivo, indicando se ele melhora ou piora. Existem duas definições equivalentes para o preço-sombra:

• Definição Nº 1: A taxa de melhoria experimentada no valor ótimo da função objetivo para cada unidade que AUMENTA o termo livre de uma restrição.

• Definição Nº 2: A taxa de piora experimentada no valor ótimo da função objetivo para cada unidade que DIMINUI o termo livre de uma restrição.

Estas duas definições são baseadas no pressuposto de que o preço-sombra é positivo. Normalmente, o preço-sombra de uma restrição do tipo limitação (≤), que é ativa, é sempre positivo. Quando o preço-sombra de uma restrição é negativo, o que normalmente acontece com restrições do tipo exigência (≥), o efeito sobre a função objetivo é o oposto da definição: quando o termo livre aumenta, o valor piora; e quando diminui, melhora.

Faixas de Valores para o Preço-Sombra da Restrição

• O preço-sombra de uma restrição ativa será não-negativo (≥ 0) se a restrição for uma limitação (≤).

• O preço-sombra de uma restrição ativa será não-positivo (≤ 0) se a restrição for do tipo exigência (≥).

• O preço-sombra de uma restrição ativa será positivo, negativo ou igual a 0 se a restrição for um requisito do tipo (=); isso dependerá de cada modelo.

• O preço-sombra de uma restrição inativa é sempre zero.

Faixa de Validade do Preço-Sombra da Restrição

• O valor do preço-sombra de uma restrição é válido apenas para aumentos ou diminuições em seu termo livre que não causem a inativação de nenhuma das restrições ativas da solução ótima original.

Impacto do Termo Livre no Valor da Função Objetivo

• O valor da função objetivo irá melhorar (aumentar se maximizando, diminuir se minimizando) quando o termo livre de uma restrição ativa do tipo limitação (≤) aumenta.

• O valor da função objetivo irá piorar (diminuir se maximizando, aumentar se minimizando) quando o termo livre de uma restrição ativa do tipo limitação (≤) diminui.

• O valor da função objetivo irá melhorar (aumentar se maximizando, diminuir se minimizando) quando o termo livre de uma restrição ativa do tipo exigência (≥) diminui.

• O valor da função objetivo irá piorar (diminuir se maximizando, aumentar se minimizando) quando o termo livre de uma restrição ativa do tipo exigência (≥) aumenta.

• O valor da função objetivo manterá seu valor (não se alterará) quando o termo livre de uma restrição inativa de qualquer tipo for alterado.