(Parte 1 de 4)

Pesquisa OperacionalJhoab Negreiros

Capítulo 5 Algoritmo Simplex

CAPÍTULO 5 Algoritmo Simplex

5.1 Introdução

O algoritmo Simplex é a ferramenta básica da programação linear. O objetivo do algoritmo é transformar uma matriz dada em outra equivalente que contenha um certo “desenho” ou “padrão”.

Este capítulo faz um esboço do Simplex, destacando seu parentesco com o algoritmo de Gauss-Jordan discutido no capítulo três.

5.2 Conversão de desigualdade em uma equação

Em restrições ()≤, o lado direito pode ser considerado como a representação do limite imposto à disponibilidade de um recurso, caso em que o lado esquerdo representaria a utilização desse recurso limitado pelas atividades (variáveis) do modelo. Assim, a diferença entre direito e o lado esquerdo da restrição ()≤ resultaria na quantidade do recurso não utilizada ou folga.

Para converter uma desigualdade ()≤ em uma equação, uma variável de folga não negativa é adicionada ao lado esquerdo da restrição

Exemplo 1. Dada a seguinte desigualdade: 3212xy+≤.

Para transformar em uma equação adicionamos a variável de folga 1F e logo temos: 1 13 2 12, 0x y F com F+ + = ≥

Pesquisa OperacionalJhoab Negreiros

Capítulo 5 Algoritmo Simplex

De forma semelhante, uma restrição ()≥ estabelece um limite inferior para as atividades do modelo de programação linear, de modo que a quantidade pela qual o lado esquerdo excede o limite mínimo representa uma sobra. Consegue-se a conversão de ()≥ em uma igualdade com a subtração de uma variável de sobra não negativa do lado esquerdo da desigualdade.

Exemplo 2. Dada a seguinte desigualdade: 100xy+≥.

Para transformar em uma equação subtraímos a variável de folga 2F e logo temos: 22100,0xyFcomF+−=≥

A última possibilidade restante é que o lado direito da equação resultante seja negativo. A condição sempre pode ser satisfeita multiplicando-se ambos os lados da equação resultante por

Exemplo 3. Dada a seguinte desigualdade: 220xy−+≤−.

Para transformar em uma equação adicionamos a variável de folga 3F e logo temos:

Agora, multiplicando ambos os lados por ()1−, teremos um lado direito não negativo, como desejado, isto é:

5.3 Transição da Solução Gráfica para a Solução Algébrica

As idéias transmitidas pela solução gráfica do problema de programação linear lançam as bases para o desenvolvimento do método algébrico simplex. No método gráfico, a região de soluções é delineada pelos meios-espaços, que representam as restrições, e, no método simplex, a região de soluções é representada por m equações lineares simultâneas e n variáveis não negativas. A figura a seguir traça um paralelo entre os dois métodos.

Pesquisa OperacionalJhoab Negreiros

Capítulo 5 Algoritmo Simplex

Método Gráfico Método Algébrico

Represente todas as restrições em gráfico, entre elas as restrições de não-negatividade. Represente a região de soluções por m equações em n variáveis e restrinjam todas as variáveis a valores não negativos,mn<.

Identifique os pontos extremos viáveis da região de soluções.

Determine as soluções básicas viáveis das equações.

Candidatos à solução ótima são dados por um número finito de pontos extremos.

Candidatas à solução ótima são dadas por um número finito de soluções básicas viáveis.

Use a função objetivo para determinar o ponto extremo ótimo entre todos os candidatos.

Use a função objetivo para determinar a solução básica viável ótima entre todos os candidatos.

Podemos verificar visualmente pelo gráfico por que a região de soluções tem um número infinito de pontos de solução, mas como podemos tirar a mesma conclusão da representação algébrica de soluções? A resposta é que na representação algébrica o número de equações m é sempre menor do que ou igual ao número de variáveis n. Se mn=, e as equações forem consistentes, o sistema tem somente uma solução; mas se mn< (o que representa a maioria dos problemas de PL), então o sistema de equações, novamente, se consistente, dará como resultado um número infinito de soluções.

Exemplo 4. A equação 2x= tem ()1mn== e a solução é obviamente única. {}2S=, mas para a equação 1xy+=, temos ()1m= e ()2n=, que resulta em um número infinito de

5.4 Determinação Algébrica dos Pontos Extremos

Em um conjunto de mn× equações ()mn<, se igualarmos ()nm− variáveis a zero, e depois resolvermos as m equações para as m variáveis restantes, a solução resultante, se for única, é denominada solução básica e deve corresponder a um ponto extremo (viável ou inviável) da região de soluções. Isso significa que o número máximo de pontos extremos é:

Pesquisa OperacionalJhoab Negreiros

Capítulo 5 Algoritmo Simplex

Exemplo 5. Considere o seguinte problema de PL com duas variáveis:

Maximizar f x y x y

Restrições x y x y x y

Em linguagem algébrica, a região de soluções do problema de programação PL é representado por:

x y F x y F x y F F

O sistema tem 2m= equações e 4n= variáveis. Assim, de acordo com a regra dada, os pontos extremos podem ser determinados algebricamente igualando 422nm−=−= variáveis a zero e depois, resolvendo para as 2m= variáveis restantes.

Se fizermos 0x= e 0y=, as equações dão a solução (básica) única:

124,5FF==.(Esta solução corresponde ao ponto A.)

Um outro ponto pode ser determinado, fazendo 10F= e 20F=. Então resolvendo as duas equações:

Pesquisa OperacionalJhoab Negreiros

Capítulo 5 Algoritmo Simplex x y o que dá como resultado a solução básica 1x= e 2y=, que é o ponto C na figura.

É provável que você esteja imaginando como podemos decidir quais nm− variáveis devem ser igualadas a zero para chegar a um ponto extremo específico. Sem o auxílio da solução gráfica, não podemos dizer quais nm− variáveis zero estão associadas com quais pontos extremos. Mas isso não nos impede de enumerar todos os pontos extremos da região de soluções. Apenas considere todas as combinações nas quais nm− variáveis sejam igualadas a zero e resolva as equações resultantes. Isso feito, a solução ótima é a solução básica viável (pontos extremos) que resultar no melhor valor para a função objetivo.

Neste exemplo temos: 4,2 4 3 6

C × == pontos extremos.

Examinando a figura podemos localizar os quatro pontos A, B, C, D, E e F, todos são soluções para o problema, mas os dois últimos são não viáveis, porque não satisfazem todas as restrições.

Para resumir a transição da solução gráfica para a solução algébrica, as mn− variáveis zero são conhecidas como variáveis não básicas. As restantes m variáveis são denominadas variáveis básicas e sua solução é denominada solução básica.

Variáveis não básicas

(Parte 1 de 4)

Comentários