Método Simplex

Suponha que a Óleos Unidos S.A. tenha disponíveis 120 litros de extrato mineral e 2O MÉTODO SIMPLEX

O Método Simplex caminha pelos vértices da região viável até encontrar uma solução que não possua soluções vizinhas melhores que ela. Esta é a solução ótima. A solução ótima pode não existir em dois casos: quando não há nenhuma solução viável para o problema, devido a restrições incompatíveis; ou quando não há máximo (ou mínimo), isto é, uma ou mais variáveis podem tender a infinito e as restrições continuarem sendo satisfeitas, o que fornece um valor sem limites para a função objetivo.

4.1 Exemplo de um Problema

O modelo de programação linear pode ser resolvido por um método de solução de sistema de equações lineares. O processo que será apresentado no exemplo a seguir, retirado de ANDRADE (2000), é bastante intuitivo e tem por finalidade apresentar a metodologia utilizada pelo método Simplex.

a) Formulação do problema

“Uma marcenaria deseja estabelecer uma programação diária de produção”. Atualmente, a oficina faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, amos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas na tabela a seguir.

Recurso Disponibilidade

Madeira 12m2

Mão-de-obra 8 H.h

O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m2 de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de madeira e 1 H.h de mão de obra.

Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de $ 4 e cada armário de $ 1. “O problema é encontrar o programa de produção que maximiza a margem de contribuição total para o lucro.”.

b) Montagem do modelo

As variáveis de decisão envolvidas no problema são:

x1: quantidade a produzir de mesas

x2: quantidade a produzir de armários

A função objetivo é:

Lucro: z = 4 x1 + x2

Para as restrições, a relação lógica existente é:

Utilização de recurso =Disponibilidade

Assim temos

Madeira: 2 x1 + 3 x2 <12

Mão-de-obra: 2 x1 + x2 <8

x1, x2 <0

O modelo completo é:

Maximizar: z = 4 x1 + x2

Sujeito a 2 x1 + 3 x2 <12

2 x1 + x2 <8

x1, x2 <0

c) Solução do modelo

Já conhecemos o método de solução gráfica para problemas de programação linear de duas variáveis. Será agora apresentada a solução por sistemas de equações lineares.

De forma a transformar as restrições do problema de programação linear de inequações em equações, são introduzidas as variáveis de folga. Neste problema, as restrições têm a seguinte estrutura lógica:

Utilização de recurso =Disponibilidade.

Ao se introduzir o conceito de folga de recurso, a inequação pode ser escrita como:

Utilização de recurso + Folga = Disponibilidade.

Isso significa que:

Utilização de recurso < Disponibilidade implica Folga > 0;

Utilização de recurso = Disponibilidade implica Folga = 0.

Deste modo, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de cada produto. Desse modo, vamos chamar:

f1: folga de madeira;

f2: folga de mão-de-obra.

Introduzindo as variáveis de folga, o problema a ser resolvido passa a ser:

Maximizar: z = 4 x1 + x2

Sujeito a 2 x1 + 3 x2 + f1 = 12

2 x1 + x2 + f2 = 8

x1, x2, f1, f2 <0

O problema se transformou em encontrar a solução do sistema de equações lineares que maximiza o lucro. Como neste caso o número de variáveis (m = 4) é superior ao número de equações (n = 2), o sistema é indeterminado, apresentando infinitas soluções.

No entanto, todas as variáveis devem ser maiores ou iguais a zero. Atribuir zero a uma variável significa não produzir um dos produtos (se a variável for x1 ou x2) ou utilizar toda a disponibilidade de recursos (se a variável for f1 ou f2).

Desta forma, podemos encontrar soluções para o sistema de equações zerando duas variáveis (n - m = 2) e encontrando o valor para as duas variáveis restantes. Teremos que resolver então:

= , sistemas de equações lineares.

Uma vez resolvido um sistema, serão aplicados na função objetivo os valores encontrados. As variáveis zeradas são chamadas variáveis não-básicas. As variáveis cujos valores são calculados pelo sistema de equações são chamadas variáveis básicas.

c.1) Variáveis não-básicas: x1 = 0 e x2 = 0

temos as variáveis básicas f1 = 12 e f2 = 8

dando o lucro z = 0

c.2) Variáveis não-básicas: x1 = 0 e f1 = 0

temos as variáveis básicas x2 = 4

f2 = 4

dando o lucro z = 4

c.3) Variáveis não-básicas: x1 = 0 e f2 = 0

temos as variáveis básicas x2 = 8

f1 = -12

como f1 < 0, a solução