O método simplex



Baixar 104.12 Kb.
Encontro20.07.2016
Tamanho104.12 Kb.
O 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 obtida é INVIÁVEL.


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

temos as variáveis básicas x1 = 6



f2 = -4

como f2 < 0, a solução obtida é INVIÁVEL.


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

temos as variáveis básicas x1 = 4



f1 = 4

dando o lucro z = 16



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

temos as variáveis básicas x1 = 3



x2 = 2

dando o lucro z = 14

Comparando todas as soluções encontradas por este processo, achamos à solução ótima, ou seja,

x1 = 4, x2 = 0, f1 = 4, f2 = 0, dando um lucro z = 16.
4.2 Desenvolvimento do Método Simplex
Da forma como foi resolvido o problema anteriormente, é necessário que muitos sistemas de equações sejam resolvidos e suas soluções comparadas. Para problemas reais de programação linear, esta solução se torna inviável. Desta forma, para termos condições de resolver um problema de programação linear, precisamos de uma sistemática que nos diga:

qual o sistema de equações que deve ser resolvido;

que o próximo sistema a ser resolvido fornecerá uma solução melhor que os anteriores;

como identificar um solução ótima, uma vez que a tenhamos encontrado.

Essa sistemática é o método Simplex, e as regras que o método utiliza para atender às três questões acima são, basicamente, os critérios que desenvolvemos nos itens anteriores. Vamos voltar ao nosso pequeno problema, já com as variáveis de folga:
maximizar z = 4 x1 + x2

sujeito a 2 x1 + 3 x2 + f1 = 12

2 x1 + x2 + f2 = 8

x1, x2, f1, f2 <0

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:

de: z = 4 x1 + x2

para: z - 4 x1 - x2 = 0



Quadro 1


Base

x1

x2

f1

f2

b

f1

2

3

1

0

12

f2

2

1

0

1

8

z

-4

-1

0

0

0

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. Nessa última linha teremos sempre a contribuição que cada variável dá para o lucro total z, por unidade, em cada iteração do processo de solução. Essa última linha será chamada de função objetivo transformada, ou função z-transformada.


a) Solução inicial

A solução inicial para o problema será sempre obtida fazendo as variáveis originais do modelo (no caso x1 e x2) iguais a zero e achando o valor das demais.

Assim, fazendo x1 = x2 = 0 (variáveis não básicas), obtemos do Quadro 1:

f1 = 12

f2 = 8 (variáveis básicas)

z = 0

As variáveis básicas estão indicadas no Quadro 1, para facilitar o acompanhamento das operações.


b) Segunda solução

Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um valor maior para z. O problema é descobrir:

*Das duas variáveis não básicas (nulas) na primeira solução, qual deve se tornar positiva?

*Das duas variáveis básicas (positivas) na primeira solução, qual deverá ser anulada?


Qual variável deverá se tornar positiva?
Vamos observar que na última linha do Quadro 1 temos os coeficientes da função objetivo que mostram a contribuição para o lucro z de cada unidade produzida de mesa (x1) e de armário (x2).

Assim, aplicando o critério de que devemos produzir primeiro o produto que mais contribui para o lucro, vamos começar a produção pela variável x1, já que sua contribuição unitária para o lucro (4) é maior que a contribuição de x2, igual a 1.

Logo, a variável que deverá se tornar positiva é x1.
Qual variável deverá ser anulada?
Nota-se pelo Quadro 1 que, na primeira equação, o maior valor possível de x1 é 6, quando f1 for igual a zero (note que x2 vale zero por ser variável não básica). Qualquer valor maior de x1 fará com que o valor de f1 fique negativo, o que não é permitido. Na segunda equação, o maior valor permitido para x1 é 4, quando f2 for igual a zero. Analisando simultaneamente as duas equações, percebe-se que o maior valor possível para x1 é 4, já que atende às duas equações.

Observe que esta análise pode ser feita diretamente do Quadro 1, através da divisão dos elementos da coluna b pelos correspondentes elementos da coluna x1. O menor quociente indica, pela linha em que ocorreu, qual a variável básica que deve ser anulada. Assim, como o menor quociente é dado pela divisão 8 / 2 = 4, a variável básica a ser anulada é f2, que é a variável positiva na atual solução, cujo valor foi encontrado na segunda linha.

Assim temos:

x2 = 0

f2 = 0

e o sistema restante deve ser resolvido para acharmos o valor de x1 e f1. A solução desse sistema será feita usando o Quadro 1 com as equações completas e usando as operações válidas com as linhas da matriz.



1ª operação: Dividir a segunda linha por 2 (L2 =L2 / 2)
Quadro 1A


Base

x1

x2

f1

f2

b

f1

2

3

1

0

12

x1

1

1/2

0

1/2

4

z

-4

-1

0

0

0


2ª operação: Multiplicar a segunda linha do Quadro 1A por (-2) e somar com a primeira linha do mesmo quadro, colocando o resultado na primeira linha (L1 L1 - 2 L2)
Quadro 1B


Base

x1

x2

f1

f2

b

f1

0

2

1

-1

4

x1

1

1/2

0

1/2

4

z

-4

-1

0

0

0


3ª operação: Multiplicar a segunda linha do Quadro 1B por (4) e somar com a terceira linha do mesmo quadro, colocando o resultado na terceira linha (L3 =L3 + 4 L2)
Quadro 2


Base

x1

x2

f1

f2

b

f1

0

2

1

-1

4

x1

1

1/2

0

1/2

4

z

0

1

0

2

16

Como a última linha (função z-transformada) mostra as contribuições líquidas para o lucro, caso as variáveis x1 e f2 venha a ter seus valores aumentados de 0 para 1 e como estas contribuições têm seus valores trocados com relação ao quadro original, concluímos que a solução encontrada é ótima.

x1 = 4,

x2 = 0,

f1 = 4,

f2 = 0 e

z = 16
4.3 Procedimento do Método Simplex (Problemas de Maximização)
Passo 1: Introduzir as variáveis de folga; uma para cada desigualdade.

Passo 2: Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo transformada.

Passo 3: Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis originais e achando valores positivos para as variáveis de folga.

Passo 4: Como próxima variável a entrar na base, escolher a variável não básica que oferece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução ótima, com o mesmo valor da função objetivo.

Passo 5: Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:

a) 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 nesta coluna, o processo deve parar, já que a solução seria ilimitada.

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

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

Passo 7: Retornar ao passo 4 para iniciar outra iteração.
4.4 Outro Exemplo
Vamos resolver pelo método Simplex o problema das rações proposto no Capítulo 1, cujo modelo foi apresentado no Capítulo 3.

Maximizar Z = 11 x1 + 12 x2

Sujeito a: x1 + 4 x2 <10000

5 x1 + 2 x2 <30000



x1, x2 <0

a) Inclusão das variáveis de folga

Com a inclusão das variáveis de folga, o problema torna-se:

Maximizar Z = 11 x1 + 12 x2

Sujeito a: x1 + 4 x2 + f1 <10000

5 x1 + 2 x2 + f2 < 30000

x1, x2, f1, f2 < 0

b) Solução inicial


Base

x1

x2

f1

f2

b

f1

1

4

1

0

10000

f2

5

2

0

1

30000

z

-11

-12

0

0

0


c) Primeira iteração

Variável a entrar na base: x2 (coluna com maior valor negativo na última linha)

Variável a sair da base: f1 (o quociente 10000/4 é o menor quociente entre a última coluna e a coluna da variável x2, que vai entrar na base).

L1 =L1 / 4

L2 =L2 - 2 L1

L3 =L3 + 12 L1




Base

x1

x2

f1

f2

b

x2

1/4

1

1/4

0

250

f2

4,5

0

-1/2

1

25000

z

-8

0

3

0

30000


d) Segunda iteração

Variável a entrar na base: x1 (coluna com maior valor negativo na última linha)

Variável a sair da base: f2 (o quociente 25000/ 4,5 é o menor quociente entre a última coluna e a coluna da variável x1, que vai entrar na base)

L2 =L2 / 4,5

L1 =L1 - L2 / 4

L3 =L3 + 8 L2



Base

x1

x2

f1

f2

b

x2

0

1

0,2778

-0,0556

111,11

x1

1

0

-0,1111

0,2222

5555,56

z

0

0

2,1111

1,7778

74444,44


e) Solução ótima encontrada

Como todos os valores da última linha (função z-transformada) são positivos ou nulos, concluímos que a solução encontrada é ótima, ou seja:



x1 = 5555,55

x2 = 1111,11

z = 74444,44

Exercícios sobre Método Simplex:


  1. Um empregado decidiu comercializar barcos. Depois de empregar alguns trabalhadores e de descobrir os preços aos quais venderia nos modelos, chegou às seguintes observações. Cada modelo comum rende um lucro de R$ 520,00 e cada modelo rápido rende um lucro de R$ 450,00. Um modelo rápido requer 40 horas para ser construído e 24 horas para o acabamento. Cada modelo rápido requer 25 horas para ser construído e 30 horas para o acabamento. Este empregador dispõe de 400 horas de trabalho por minuto para construção e 360 horas por mês para acabamento. Quanto deve produzir de cada modelo de maneira a maximizar o lucro?

2) Encontre a solução ótima da seguinte problema de programação linear testando o valor da função objetivo em cada um dos pontos abaixo descritos:
a) Max Z = 20 x1 + 40 x2

Restrições: x1 + x2 ≤3

2x + x2 ≤5

4x 1 + x2 ≤12

x1, x2 ≥0
b) Max => Z = 12x + 4y

Restrições: x + 2y <800

x + 3y <600

2x +3y <200

x, y ≥0


  1. 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, vamos considerar que a marcenaria tem limitações em somente dois recursos: madeira e mão de obra, cuja disponibilidade diária é mostrada na tabela a seguir:

Recurso

Disponibilidade

Madeira

12 m2

Mão de obra

8 H.h (homens /hora)

O processo de produção é tal que, para fazer uma mesa e fabrica gasta 2 m2 de madeira e 2 H. h de mão de obra. Para fazer o 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. Encontre a margem que maximinize o lucro.


  1. A Óleos Unidos S.A. é uma empresa do ramo de derivados de petróleo que manufatura três combustíveis especiais com base na mistura de dois insumos: um extrato mineral e um solvente. No processo de produção não existe perda do material, de forma que a quantidade de litros de extrato mineral somada a quantidade de litros de solvente utilizada para a fabricação de um tipo de combustível resulta no total de litros daquele combustível. A proporção da mistura está descrita na tabela a seguir:







Combustível A

Combustível B

Combustível C

Extrato Mineral

8 litros

5 litros

4 litros

Solvente

5 litros

4 litros

2 litros

Suponha que a Óleos Unidos S.A. tenha disponíveis 120 litros de extrato mineral e 200 litros de solvente, e que os lucros líquidos esperados para os três combustíveis sejam de R$ 20,00, R$ 22,00 e R$ 18,00, respectivamente. Responda:



  1. Estabeleça um modelo de programação linear que determine a quantidade de cada combustível a ser fabricada, dadas as restrições de matéria primas.

  2. Quanto de cada produto deve ser manufaturado de modo a maximizar o lucro da companhia? De quanto é esse lucro? (Utilize o método simplex)

5) Um pequeno entregador pode transportar madeira ou frutas em seu carrinho de mão, mas cobra R$ 20,00 para cada fardo de madeira e R$ 35,00 por saco de frutas. Os fardos pesam 1 kg e ocupam 2 dm3 de espaço. Os fados de frutas pesam 1 kg e ocupam 3 dm3 de espaço. O carrinho tem capacidade para transportar 12 kg e 10 dm3, e o entregador pode levar quantos sacos e fardos desejar. Resolva o problema pelo método simplex e determine qual será o lucro do entregador e como ele deve preencher o seu carrinho.

    1. Uma pequena malharia produz dois tipos de camisas: de manga curta e de manga comprida. Toda a produção feita é vendida para um distribuidor, que compra tudo o que é produzido. A confecção de cada camisa passa por três seções de trabalho: corte, costura e acabamento. A tabela 1 mostra os tempos necessários em cada seção:

Tabela 1

Tempo de fabricação de uma camisa em cada seção

Produto

Tempo de fabricação (em horas)

Corte

Costura

Acabamento

Manga Curta

3

1,5

5

Manga Comprida

3

3

3

A tabela 2 mostra a quantidade de horas por semana em cada seção de trabalho.


Limites de capacidade de fabricação

Seção de trabalho

Homens/ horas por semana

Corte

210

Costura

160

Acabamento

330
Tabela 2

Determine a quantidade de cada tipo de camisa que deve ser fabricada de forma a maximizar o lucro da empresa sabendo que o lucro unitário proporcionado pela camisa de manga curta é de R$ 2,00 e o proporcionado pela de manga comprida é de R$ 3,00. Faça através do método simplex.


7) Uma empresa de móveis de cozinha fabrica três tipos de meses de fórmica: quadrada, retangular e redonda. Cada mesa passa por dois processos: de produção e de acabamento. A tabela a seguir resume o número e horas requeridas por mesa em cada um dos processos, bem como o lucro unitário de cada mesa. A partir desses dados utilize o método simplex para achar a solução ótima a fim de maximizar os lucros da produção.


Modelo de mesa

Produção

Acabamento

Lucro unitário

Quadrada

2 horas

2 horas

30

Retangular

3 horas

2 horas

60

Redonda

4 horas

2 horas

80

Total semanal disponível

1.000 horas

600 horas

-

8) Considere uma fábrica de rádios que possui duas linhas de produção:


Rádios Standard (RS); Rádios Luxo (RL). A tabela de produtividade fornece as seguintes informações:




Máximo de funcionários na linha de produção

Mão-de-obra empregada na produção (homem/dia/unidade)

Lucro unitário (R$)

RS

24

1

30,00

RL

32

2

40,00

A fábrica possui um total de 40 funcionários a serem alocados nas duas linhas de produção. Maximize os lucros diários através do método simplex.
9) A SugarCo S.A. produz três tipos de barras de chocolate industriais, todas consistindo exclusivamente de açúcar e chocolate. A composição e lucro relacionado a cada uma desses produtos, bem como a disponibilidade de matérias-primas vêm dados abaixo. Formule o problema de forma a maximizar os lucros da empresa.




Quantidade de açúcar (Kg)

Quantidade de Chocolate (Kg)

Lucro ($)

Produto 1

1

2

3

Produto 2

1

3

7

Produto 3

1

1

5

Disponibilidade

50

100





10) A Brinquedos S.A. fabrica dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido por R$27 e usa R$10 de matéria-prima. Cada soldado fabricado aumenta os custos diretos de mão-de-obra e custos indiretos em R$14. Um trem é vendido a R$21 e utiliza R$9 de matéria-prima. Cada trem aumenta os de mão-de-obra e indiretos em R$10. A fabricação requer dois tipos de mão-de-obra: carpinteiro e pintor. A fabricação de um soldado requer 2h de um pintor e 1 h de carpinteiro. Um trem demanda 1hora de pintura e 1h de carpintaria. Para cada semana, a Brinquedos pode conseguir toda a matéria-prima necessária, mas apenas 100h de pintura e 80h de carpintaria. A demanda para os trens é ilimitada, mas a de soldados é de no máximo 40 por semana. Resolva pelo método simplex.


©principo.org 2016
enviar mensagem

    Página principal