Programação Linear

A PL é um método para encontrar o valor máximo ou mínimo de uma função linear sujeita a restrições lineares. A função objetivo e as restrições são representadas por equações ou inequações lineares.

Método Simplex

O Método Simplex é uma técnica bem estabelecida e amplamente utilizada na programação linear (PL) para encontrar o valor máximo ou mínimo de uma função linear objetivo. Desenvolvido por George Dantzig em 1947, o método permanece um pilar na pesquisa operacional e na ciência da decisão. A abordagem opera iterativamente, movendo-se ao longo das arestas de um poliedro convexo para alcançar o ponto ótimo.

O Método Simplex é utilizado em diversas áreas, como economia, engenharia, transporte e logística. Pode ser usado para resolver problemas como alocação de recursos, otimização de rotas, planejamento de produção, e muito mais.

Passo 1: Transformar o problema em forma canônica

O primeiro passo é converter o problema original para uma forma padrão. Isso significa que todas as restrições devem ser convertidas para equações com variáveis não negativas. Fazemos isso introduzindo variáveis "slack" que transformam as inequações em equações.

Por exemplo, a inequação

pode ser transformada em

onde aqui é a variável slack.

Passo 2: Encontrar uma solução básica viável

Uma Solução Básica Viável (SBV) é um ponto no espaço de soluções que satisfaz todas as restrições. Este ponto serve como o ponto de partida para as iterações do Simplex.

• Método das Duas Fases: Pode ser usado se uma SBV não for facilmente identificável.
• Método do Big M: Outra abordagem utilizada quando uma SBV não é óbvia.

Passo 3: Determinar a direção de movimento para melhorar a solução atual

Para melhorar a solução atual, o algoritmo identifica qual variável deve ser aumentada ou diminuída para otimizar a função objetivo. O critério comumente utilizado para isso é a Regra da Razão Mínima.

Passo 4: Continuar iterando até encontrar a solução ótima

O algoritmo continua movendo-se de vértice em vértice ao longo das arestas do poliedro convexo. Esta iteração continua até que nenhuma melhoria adicional possa ser feita ao valor da função objetivo.

Critério de Parada

O algoritmo para de iterar quando todos os coeficientes na linha da função objetivo são não-negativos (no caso de maximização) ou não-positivos (no caso de minimização). Formalmente, se estamos maximizando a função objetivo , o algoritmo para quando:

Da mesma forma, para minimização:

Exemplo

Considere o problema de programação linear abaixo:

Após adicionarmos variáveis de folga, o problema toma a forma a seguir:

O sistema coloca o problema de programação linear em uma forma conhecida por "dicionário'', na qual a função objetivo e um subconjunto de variáveis variáveis básicas com cardinalidade igual ao número de restrições são expressos em termos das variáveis restantes em variáveis não básicas. As variáveis não básicas assumem valores nulos e, portanto, uma solução pode ser obtida diretamente a partir do dicionário.

Para o dicionário acima, a base é formada pelas variáveis , e , enquanto que as variáveis não básicas são , e . Já que as variáveis não básicas assumem valores nulos, obtemos diretamente os valores das variáveis básicas: , e .

Note que a solução obtida é factível para o problema em questão uma vez que todas as variáveis (básicas e não básicas) são não negativas. Além disso, a função objetivo corrente tem valor .

O método Simplex é um processo iterativo que inicia com uma solução , onde e, satisfazendo as equações de .

Partindo do dicionário , o Simplex busca uma nova solução tal que:. Para tanto, é necessário fazer uma solução não básica com coeficiente positivo na equação de entrar na base que, por sua vez, fará a variável não básica aumentar e consequentemente elevar o valor da função objetivo. Obviamente, a variável que entra na base não pode aumentar seu valor indefinidamente, a menos que o problema seja ilimitado. A primeira variável básica a se tornar nula passa a ser uma variável não básica na iteração seguinte. O processo então se repete até que se convirja para uma solução ótima ou até que se detecte que o problema é ilimitado.

Inicialização: Para iniciarmos o processo, necessitamos de uma solução factível, tal como:

Esta solução induz o valor para a função objetivo.

Passo 1: A solução corrente não é ótima. Qualquer acréscimo no valor de aumenta o valor de. Mas não podemos aumentar o valor de ilimitadamente já que este está limitado pelas desigualdades abaixo:

Assim, o valor de na próxima iteração é o menor dentre , o que leva a igualdade:

Substituindo-se no sistema de maneira atransferir-se a variável para o lado direito, obtém-se:

Agora, substituindo as equações no "dicionário'' , obtém-se o dicionário abaixo:

A solução induzida pelo dicionário é

cujo valor da função objetivo é .

Neste dicionário, as variáveis , , e são ditas variáveis básicas tal que o conjunto contém as variáveis básicas. As demais variáveis são ditas não básicas, sendo o conjunto o conjunto das variáveis não básicas.

Passo 2: A solução corrente não é ótima! Note que um pequeno acréscimo no valor de invariavelmente aumenta o valor de .

Mas não podemos aumentar o valor de ilimitadamente uma vez que isto poderia tornar a solução infactível (outras variáveis poderiam assumir valores negativos).

Para que a solução resultante seja factível, as desigualdades abaixo devem ser respeitadas:

Portanto, deve sair da base para que a variável possa entrar na base sem violar as restrições.

Após substituirmos a equação nas equações do dicionário , obtemos:

Substituindo as equações do dicionário pelas equações obtemos um novo dicionário:

cuja base é .

A solução dada pelo dicionário é ótima: , , , , , , e é uma solução ótima pois os coeficientes das variáveis não básicas na equação de , no dicionário correspondente dado pelo sistema , são todos negativos; aumentando o valor de qualquer variável não básica reduzirá o valor da função objetivo.

---

Implementação Real do Simplex Dual e Suas Utilidades

O algoritmo Simplex é uma das ferramentas mais poderosas em pesquisa operacional e otimização. No entanto, a implementação real do Simplex, especialmente a versão dual, vai além do algoritmo básico ensinado em cursos introdutórios. Vamos explorar algumas das técnicas avançadas e "truques" usados na indústria.

Utilidade em Branch-and-Bound

O Simplex Dual é particularmente útil em métodos de Branch-and-Bound para resolver problemas de programação inteira. Uma das principais vantagens é que ele permite a adição de restrições adicionais ao problema sem perder a factibilidade do tableau do Simplex. Isso é crucial em Branch-and-Bound, onde frequentemente adicionamos restrições para dividir o espaço de soluções.

Steepest Edge Rule

Na implementação padrão do Simplex, a escolha da variável a entrar na base é feita com base no custo reduzido. No entanto, essa abordagem nem sempre é a mais eficiente. A regra do "Steepest Edge" escolhe a variável que maximiza o avanço na direção do gradiente do objetivo. Isso pode acelerar a convergência do algoritmo.

Pricing Strategies

Em problemas grandes, calcular o custo reduzido para todas as variáveis pode ser computacionalmente caro. Estratégias de "pricing" como o Devex pricing ou o método de múltiplos pivôs são usadas para tornar essa etapa mais eficiente.

Degeneracy and Anti-cycling

A degenerescência é um problema bem conhecido no Simplex, podendo levar a um grande número de iterações. Técnicas como a regra de Bland ou perturbações lexicográficas são usadas para evitar ciclos infinitos.

Warm Starts

Em cenários onde o modelo é resolvido várias vezes com pequenas modificações, como em algoritmos de decomposição, o "warm start" pode ser usado para iniciar o Simplex Dual a partir de uma solução factível próxima, economizando tempo de computação.

Paralelização e Distribuição

O Simplex Dual também pode ser adaptado para execução em paralelo ou em ambientes distribuídos, embora isso possa ser bastante desafiador devido à natureza sequencial do algoritmo.

Essas técnicas e estratégias tornam o Simplex Dual uma ferramenta poderosa e flexível, adaptável a uma ampla gama de problemas industriais e de pesquisa.

---

Degeneração

O método Simplex é um algoritmo popular para resolver problemas de programação linear. Embora seja extremamente eficiente na prática, há casos em que o método pode ser ineficiente devido à degeneração. Degeneração ocorre quando o método Simplex visita mais de um vértice adjacente que tem o mesmo valor da função objetivo, potencialmente causando um número excessivo de iterações.

Definição Matemática da Degeneração

Em qualquer iteração do método Simplex, uma solução básica factível (BFS) é obtida, e a degeneração ocorre quando essa BFS tem mais de um vértice adjacente com o mesmo valor da função objetivo.

Consequências

• Ciclagem: Em casos raros, o método Simplex pode entrar em um ciclo infinito, o que é mais provável em problemas degenerados.

• Ineficiência Computacional: Mesmo que a ciclagem não ocorra, a degeneração pode causar um aumento no número de iterações necessárias para encontrar a solução ótima.

Estratégias para Lidar com Degeneração

1. Regra do Menor Índice: Escolher o vértice adjacente de menor índice se houver empate na razão mínima pode evitar a ciclagem.

2. Perturbação: Adicionar uma pequena quantidade ao lado direito pode remover a degeneração, mas pode introduzir erros na solução.

3. Método de Bland: Este é um critério de seleção de variável específico que garante a terminação do método Simplex, mesmo na presença de degeneração.

4. Revisão Lexicográfica: Esta é uma outra maneira de resolver empates em degeneração, considerando múltiplos critérios em vez de apenas um.

O problema de degeneração é um aspecto importante do método Simplex que pode afetar a eficiência do algoritmo. No entanto, várias estratégias podem ser empregadas para lidar com esta questão, tornando o método Simplex uma ferramenta robusta para resolver problemas de programação linear.

---

Shadow Price

O conceito de "shadow price" ou "preço sombra" é um conceito-chave na programação linear e na otimização. Em termos simples, o shadow price associa um valor à restrição de um recurso limitado em um problema de otimização. Esse valor representa quanto a função objetivo irá melhorar (ou piorar) com uma unidade adicional do recurso.

Definição Matemática

Considere um problema de programação linear em forma padrão:

Onde:

• é a função objetivo
• são as variáveis de decisão
• são os coeficientes da função objetivo
• são os coeficientes das restrições
• são os limites das restrições

O "shadow price" da i-ésima restrição é definido como a taxa de variação da função objetivo ótima com relação a uma pequena variação na i-ésima restrição . Ou seja, matematicamente:

• Interpretação Econômica

Em um contexto econômico, o "shadow price" pode ser interpretado como o valor adicional que um objetivo derivado (como o lucro) poderia ganhar se uma unidade adicional de um recurso (como mão-de-obra, material, etc.) fosse disponibilizada.

• Nota

É importante observar que os shadow prices são válidos apenas dentro de uma região específica em torno da solução ótima. Se a variação em é muito grande, o modelo pode precisar ser resolvido novamente para obter novos shadow prices.

---

Método Matricial do Simplex

O Método Matricial do Simplex é uma forma de implementar o algoritmo Simplex usando matrizes, o que torna mais fácil a computação e a automação do método. Nesta abordagem, todas as informações sobre as restrições e a função objetivo são armazenadas em matrizes, e as operações matriciais são usadas para navegar pelo espaço de soluções até encontrar a solução ótima.

Forma Padrão do Problema

Para o Método Matricial do Simplex, é crucial que o problema de programação linear esteja em forma padrão. Um problema de maximização em forma padrão pode ser representado como:

Aqui, é a matriz das restrições, é o vetor coluna das variáveis de decisão, é o vetor coluna dos termos constantes das restrições e é o vetor linha dos coeficientes da função objetivo.

Inicialização

1. Escolher uma solução básica viável inicial, frequentemente dada pela matriz identidade.
2. Calcular o custo relativo usando a fórmula , onde é a matriz das variáveis básicas e é a matriz das variáveis não-básicas.

Iteração

Para cada iteração, siga os seguintes passos:

1. Identificar a variável a entrar na base: Selecionar tal que (para maximização).
2. Identificar a variável a sair da base: Utilizar a Regra da Razão Mínima. Calcular e escolher tal que seja mínimo.
3. Atualizar a base: Utilizar transformações de Gauss-Jordan para atualizar .

Critério de Parada

O algoritmo para quando para todas as componentes (em um problema de maximização), indicando que a solução ótima foi alcançada.

Deste modo, o Método Matricial do Simplex permite uma execução mais eficiente e precisa do algoritmo Simplex, especialmente quando se trata de problemas de grande escala.