Pesquisa Operacional I - Método Simplex

Pesquisa Operacional I - Método Simplex

Engenharia de Produção Elétrica-CESF

Graduando: Carlos Alberto F. Cruz Aula I

Solução para os Modelos de

Problemas de Programação Linear

Método Gráfico e Método Simplex

Método Gráfico Método Gráfico

Programação Linear

Solução para Modelos de Problemas Programação Linear com duas Variáveis de Decisão

Método Gráfico

Essa técnica consiste em representar num sistema de eixos ortogonais o conjunto das possíveis soluções do problema, isto é, o conjunto de pontos (x1 e x2) que obedecem ao grupo de restrições impostas pelo sistema que está sendo estudado.

O desempenho do modelo é avaliado através da representação gráfica da função objetivo. As soluções são classificadas de acordo com sua posição no gráfico.

Programação Linear

Gráfico do Conjunto de Soluções

A representação gráfica de uma equação linear com duas variáveis é uma reta. A representação gráfica de uma inequação linear com duas variáveis é um dos semiplanos definidos pela reta correspondente à equação.

Exemplo 1: Representar graficamente a inequação:

x1 + 2x2  10
Construir a reta correspondente à equação:

Programação Linear

Para construir a reta correspondente a equação x1 + 2x2 = 10 precisase de dois pontos: fazendo x1 = 0, teremos: 2x2 = 10 x2 = 5 e fazendo x2 = 0, teremos: x1 = 10

Programação Linear

Vamos tomar um ponto qualquer fora da reta, por

Testar a inequação: x1 + 2x2 10 exemplo o ponto (x1 = 10 e x2 = 5) e testemos na inequação.

Substituindo os valores de x1 e x2 na inequação:

portanto a região das soluções da inequação é aquela que contém o ponto testado.

Programação Linear

Exemplo 2: Representar graficamente a solução do modelo:

s.a. :

Max L = 2x1 + 5x2 x1 + 3x2 12

x1 0

x2 0 Solução

Vamos representar primeiramente cada uma das restrições:

Programação Linear

x1 + 3x2 = 12, se x1 = 0, então 0 + 3x2 = 12.

se x2 = 0, então x1 + 3 * 0 = 12

Portanto, x2 = 12/3, x2 = 4 Portanto, x1 = 12

 2x1 + x2 = 16, se x1 = 0, então 2 * 0 + x2 = 16
se x2 = 0, então 2x1 + 0 = 16

Portanto, x2 = 16 Portanto, x1 = 16/2, x1 = 8

Programação Linear

As restrições de não negatividade x1 0 e x2 0 representam o primeiro quadrante do gráfico de soluções.

Valores Atribuídos a X1 e X2

Programação Linear

Vamos testar para cada reta, qual o semiplano que corresponde à solução das inequações. Para isso vamos escolher um ponto qualquer fora das retas. Por exemplo o ponto (8,16).

8 + 3 * 16 12 ou 56 12; a desigualdade é falsa. Portanto a região das soluções da inequação está do lado oposto ao ponto testado.

2 *8 + 16 16 ou 32 16; a desigualdade é verdadeira. Portanto a região das soluções da inequação está do lado do ponto testado.

A combinação dos dois semiplanos resulta na região comum as duas retas, formada pelo triângulo ABC. Observe no gráfico a seguir.

Programação Linear Valores Atribuídos a X1 e X2

Programação Linear

Os pontos A, B e C são chamados pontos extremos da região permissível, que nesse caso é finita e delimita pelas arestas do triângulo ABC. Não é difícil determinar as coordenadas desses pontos extremos.

Os pontos A e B, por sua localização especial, têm coordenadas imediatas:

O ponto C é a intersecção das duas retas limites das restrições, ou seja, é a intersecção de:

x1 + 3x2 = 12 2x1 + x2 = 16

Uma combinação linear adequada entre as duas equações permitirá obter uma das variáveis, cujo o valor poderá ser então substituído em qualquer uma das equações originais para dar o valor da outra variável restante.

Programação Linear

Embora tenhamos no momento uma região permissível para a solução do problema e conheçamos as coordenadas dos pontos limite dessa região, ainda não temos a solução propriamente dita.

Os pontos extremos da região guardam uma importante propriedade: “A solução ótima encontra-se em um dos pontos extremos”.

Para descobrir qual o ponto que dá a solução ótima, basta substituirmos as coordenadas de todos os pontos extremos na função objetivo, como será mostrado na tabela a seguir.

Programação Linear

A solução ótima encontra-se no ponto B, fornecendo o valor 24 para a função objetivo. Que corresponde a x1 = 12 e x2 = 0

Tabela das coordenadas dos pontos x1 e x2

Ponto X 1 X 2 2x 1 5x 2 2x 1 +5x 2

C 7,2 1,6 14,4 8 2,4

Programação Linear

Exemplo 3: Representar graficamente a solução do modelo:

Min Z = 2x1 + 3x2 s.a.:

1x1 + 1x2 5

1x1 8
x1 0

Programação Linear

Exemplo 4: Representar graficamente a solução do modelo:

Max L = 2x1 + 3x2 s.a.:

4x1 + 6x2 60

x1 0

Programação Linear

Exemplo 5: Representar graficamente a solução do modelo

Max L = 2x1 + 3x s.a.:

1x1 + 2x2 6

x1 0

18 Método Simplex

Método Simplex Conceito

É a ferramenta utilizada normalmente para resolução de problemas de alocação de recursos e pertence a um capítulo da Pesquisa Operacional chamado Programação Linear.

Os modelos com restrições do tipo e com os termos da direita não negativos têm uma solução básica formada pelas variáveis de folga.

Para transformarmos as desigualdades lineares das restrições em equações lineares, de forma que possam ser aplicados os métodos de soluções destas últimas, vamos escrever:

Método Simplex

Ao introduzirmos o conceito de folga de recurso podemos escrever a relação anterior da seguinte forma:

Isso implica que:

UTILIZAÇÃO DISPONIBILIDADE, então folga 0 UTILIZAÇÃO = DISPONIBILIDADE, então folga = 0

Assim, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de um produto qualquer.

Método Simplex

Exemplo:

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

Madeira 12 m3 Mão-de-obra 8 H.h

Método Simplex

O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m3 de madeira e 2 H.h de mão-de-obra.

Para fazer um armário, a fábrica gasta 3 m3 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 R$ 4,0 e cada armário, de R$ 1,0. O problema do fabricante é encontrar o programa de produção que maximize a margem de contribuição total para o lucro.

Método Simplex

A construção do modelo matemático é mostrado abaixo:

Max L = 4x1 + 1x2 s.a.:

x1 0

Procedimento do Método Simplex (Problemas de Maximização)

Passo 1:

Vamos acrescentar as variáveis de folga nas restrições e transformar as desigualdades em igualdades.

2x1 + 3x2 + x3= 12
2x1 + 1x2 +x4 = 8
xi  0 i = 1,, 4

Podemos ter assim uma solução básica inicial formada pelas variáveis de folga, fazendo x1 = x2 = 0, teremos então: x3 = 12 e x4 = 8

Procedimento do Método Simplex (Problemas de Maximização)

Podemos escrever a solução em forma de vetores, então teremos:

A solução básica inicial seria x1 = 0 , x2 = 0, x3 = 12 e x4 = 8, formada portanto pelas variáveis de folga.

Procedimento do Método Simplex (Problemas de Maximização)

Vamos montar um quadro para ordenarmos as operações, colocando nele apenas os coeficientes das variáveis. No caso da função objetivo, vamos realizar a seguinte

transformação: L = 4x1 + 1x2para: L - 4x1 - 1x2 = 0

Quadro I

Procedimento do Método Simplex (Problemas de Maximização)

A última coluna corresponde aos termos independentes das equações, e a última linha contém os coeficientes das variáveis na função objetivo. Na última linha teremos sempre a contribuição que cada variável dá para o lucro total L, por unidade, em cada interação do processo de solução.

Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um valor maior para L. Para fazermos isso, vamos nos basear no Quadro I da primeira solução.

Procedimento do Método Simplex (Problemas de Maximização)

Passo 2: Identificação da variável que entra na base

Escolher a variável não básica que fornece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, a mais negativa). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nessa linha, a solução atual é ótima.

Procedimento do Método Simplex (Problemas de Maximização)

Passo 3: Identificação da variável a deixar da base

Para sabermos qual a variável deve deixar a base, devemos fazer o seguinte procedimento:

processo deveparar, já que a solução seria ilimitada; e

dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Caso não haja elemento algum positivo nessa coluna, o

o menor quociente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não básica.

Procedimento do Método Simplex

(Problemas de Maximização) Passo 4:

Usar operações válidas com as linhas da matriz e transformar o quadro de cálculos de formar a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o algarismo 1 aparece na linha correspondente à variável que está sendo anulada.

Retornar ao passo 2 para iniciar outra iteração.

A solução desse exemplo será feita utilizando o Quadro I com as equações completas e usando as operações válidas com as linhas da matriz.

Procedimento do Método Simplex

(Problemas de Maximização)

1ª Operação: dividir a 2ª linha do Quadro I por 2 Quadro 1A

Procedimento do Método Simplex (Problemas de Maximização)

2ª Operação:

multiplicar a 2ª linha do Quadro 1A por (- 2) e soma com a 1ª linha do mesmo quadro, colocando o resultado na 1ª linha do Quadro 1B

Quadro 1B

Procedimento do Método Simplex (Problemas de Maximização)

3ª Operação:

Vamos fazer o mesmo procedimento com a 3ª linha.

Multiplicar a 2ª linha do Quadro 1B por 4 e somar com a 3ª linha do mesmo quadro. O resultado obtido formará um novo quadro, o Quadro I.

Quadro I

Comentários