Faculdade de Ciência e Tecnologia da Universidade de Coimbra Departamento de Matemática Programação Linear 2002/2003



Baixar 204.3 Kb.
Página3/3
Encontro19.07.2016
Tamanho204.3 Kb.
1   2   3

2.5.3 CASOS PARTICULARES

Em qualquer dos problemas anteriores pode afirmar-se que se está presente problemas de P.L. “bem comportados”, uma vez que ambos têm uma única solução óptima. Existe contudo a possibilidade de situações “anómalas” que devem ser consideradas quando, se pretende apresentar uma técnica capaz de resolver qualquer problema de P.L..

Essas situações são:


  • situações em que a solução não é limitada 1– Quando a função

objectivo pode assumir valores arbitrariamente grandes e, consequentemente, não existe um valor máximo finito para Z.

Consideremos o enunciado do problema de maximização estudado anteriormente eliminando as restrições y  6, 3x +2y  18, a região de admissibilidade fica não limitada e o valor da função objectivo pode crescer indefinidamente nesta região.

Deve salientar-se, contudo, que o facto do conjunto das soluções admissíveis ser não limitado não implica necessariamente que a solução seja não limitada (isto é, com variáveis a poderem assumir valores arbitrariamente grandes com Z  ).

Vejamos a formulação matemática do problema é agora:


Maximizar Z = 3x + 2y,
Sujeito a

x  4

x 0, y 0

Fig. 2.5.3.1 Solução não limitada

Verificamos que , traçando uma qualquer recta de nível do plano definido pela f.o. , aquela pode ser deslocada paralelamente a si própria, no sentido do crescimento de Z, e conter ainda pontos do conjunto das soluções admissíveis.



  • situações em que existem soluções óptimas alternativas Quando um problema de P. L. possui mais do que uma solução óptima diz-se que se está em presença de soluções óptimas alternativas; isto significa que o lucro máximo pode ser obtido através de várias (infinitas) combinações dos recursos.

Se um problema de P.L. tem

Consideremos o enunciado do problema de maximização considerado, mudando o lucro unitário do produto 2 de 5 euros para 2 euros, a função objectivo é agora a recta Z = 3x + 2y (a f.o. tem o mesmo gradiente da recta da 3ª restrição 3x+ 2y = 18).


A formulação matemática do problema é agora,
Maximizar Z = 3x + 2y,

Sujeito a

x  4

y  6


3x + 2y 18

x 0, y 0

cuja resolução gráfica é:

Fig. 2.5.3.2 Soluções óptimas alternativas

Da representação gráfica deste problema conclui-se, sem dúvida, que Z = 18 é o valor máximo da função objectivo. Igualmente se conclui que quer o ponto extremo2 A quer o ponto extremo B são soluções óptimas do problema; por outras palavras, neste caso, dois pontos extremos conduzem ao mesmo valor (máximo) para a f.o.. Mais, qualquer ponto da aresta AB é também solução óptima, dado que a recta de nível Z = 18 assenta sobre aquela aresta; existe pois uma infinidade de soluções óptimas.


  • Situações em que o problema é impossível – Isto pode acontecer por não

existirem valores das variáveis a satisfazerem as restrições do problema ou as condições de não negatividade, ou ambas simultaneamente. Esta situação “anómala” surge , normalmente, derivada de erros de formalização, é a não existência de qualquer solução admissível.
No exemplo de maximização, modificando a restrição x  4 para x  7 e mantendo todas as outras, não há nenhuma solução que verifique todas as restrições do problema.

Esta situação é observada a partir da representação gráfica deste problema assim formulado:


Maximizar Z = 3x + 2y,

Sujeito a

x  7

y  6


3x + 2y 18


x 0, y 0

Fig. 2.5.3.3 Problema impossível

3. O MÉTODO SIMPLEX
3.1 INTRODUÇÃO
Como já foi referido, o Método Simplex foi proposto por Dantzig. O primeiro e mais importante passo na sua descoberta foi a conclusão de que a região admissível é o que se chama um polítopo (poliedro convexo limitado), e donde concluiu que o ponto óptimo tem que estar sobre algum dos vértices desse conjunto. Além disso, Dantzig argumentou que a função objectivo tem geralmente valores diferentes para cada vértice escolhido arbitrariamente, no qual a função objectivo tem um determinado valor, passando de vértice para vértice, na procura do ponto óptimo.

Inicialmente, Dantzig pensou que tal procedimento poderia ser irremediavelmente ineficaz, ou seja , divagar durante muito tempo ao longo das arestas, de vértice para vértice, antes de alcançar o vértice em que a função objectivo atinge o valor óptimo. Mas estava enganado, pois, na realidade veio a descobrir que, em quase todos os casos, encontrar a solução somente exigia tantos movimentos quantas as restrições do problema.


3.2 ALGUNS CONCEITOS FUNDAMENTAIS NO MÉTODO SIMPLEX
A introdução destes conceitos é fundamental para a apresentação do método simplex. Ao considerarmos um problema de programação linear, ele terá sempre a seguinte forma padrão:
Optimizar Z = c1x1 + c2x2 + ... +cnxn (1)
Sujeito a a11x1 + a12x2 + ... + a1nxn = b1

a21x1 + a22x2 + ... + a2nxn = b2

(2)

am1x1 + am2x2 + ... + amnxn = bn

x1, x2, …, xm, ..., xn ≥ 0 (m ≤ n) (3)

onde:

m = número de restrições funcionais;



n = número de variáveis de restrição.
Supõe-se ainda que os termos independentes são não negativos: bi ≥ 0 (i = 1, 2, ..., m). Caso contrário pode sempre multiplicar-se por (-1) toda a equação.

O problema pode ser escrito em notação matricial do seguinte modo:


Opt Z = CTX (1’)

Suj a AX = B (2’)

X ≥ 0 (3’)

em que:


X é o vector-coluna das incógnitas;

CT é o vector-linha dos coeficientes correspondentes;

A é a matriz dos coeficientes das incógnitas das restrições;

B é o vector-coluna dos membros direitos das restrições.


Suponha-se que a característica (número máximo de colunas linearmente independentes) da matriz A é igual a m, ou seja, C(A) = m. Isto significa que existe uma submatriz de A quadrada de ordem m (Bm x m) com determinante não nulo. Esta submatriz permite efectuar uma classificação das variáveis em: básicas (as correspondentes às colunas daquela submatriz) e não básicas (as restantes n-m variáveis).

Um sistema nas condições (2) é um sistema indeterminado de grau n-m, em que m variáveis podem ser escritas em termos das restantes n-m, e tem, por consequência, uma infinidade de soluções (correspondente à infinidade de valores que arbitrariamente podem ser atribuídos às n-m variáveis).

Suponha-se então que X = (x1, x2, …, xm, xm+1, …, xn) é uma solução desse sistema.

Se uma submatriz Bm x m da matriz A do sistema considerado é não singular, isto é, o seu determinante é nulo, então a submatriz Bm x m designa-se por base. Sem perda de generalidade, suponha-se que a base é composta pelas m últimas colunas, isto é, B = {P1, P2, …, Pm}.

As m variáveis x1, x2, …, xm correspondentes às colunas de Bm x m designam-se por variáveis básicas. As restantes n-m variáveis xm+1, xm+2, …, xn designam-se variáveis não básicas.
Uma solução básica para o sistema obtém-se atribuindo o valor zero a todas as variáveis não básicas xm+1, xm+2, …, xn e determinando depois uma solução para as m variáveis básicas restantes x1, x2, …, xm . Isto é, X = (0, ..., 0, x1, x2, …, xm), onde XB = (x1, x2, …, xm) é a única solução do sistema de equações BXB = b.

Se uma solução básica X verifica ainda as condições de não-negatividade (3’), isto é, todas as variáveis da solução são não negativas então, esta solução é uma solução básica admissível.


Duas soluções básicas que apenas diferem numa variável básica designam-se por soluções básicas adjacentes.
Uma solução básica admissível é óptima quando nenhuma das soluções básicas admissíveis adjacentes é “melhor”, isto é, nenhuma melhora o valor da função objectivo.
Se todas as variáveis básicas x1, x2, …, xm são não nulas, a solução básica designa-se por solução básica não degenerada. Se alguma variável básica for igual a zero a solução básica designa-se por solução básica degenerada.
Os simétricos dos coeficientes associados a cada variável na função objectivo (no caso da maximização) designam-se custos reduzidos.
3.3 ALGORITMO DO MÉTODO SIMPLEX

O que é um algoritmo?


Um algoritmo é um processo que repete (itera) sucessivas vezes um procedimento sistemático até obter um resultado. Além disso, também inclui um procedimento para iniciar e um critério para terminar.

O algoritmo do método simplex pode ser sintetizado nos seguintes passos:


Obter uma primeira solução básica admissível;
Verificar se a solução básica admissível é óptima, isto é, se os coeficientes da função objectivo, expressa em termos das variáveis não básicas são todos positivos. Se a solução for óptima, o algoritmo termina;
Se algum coeficiente for negativo, considerar o negativo com maior valor absoluto como o correspondente à variável que deve entrar na base e, portanto, correspondente à coluna do pivot;
Determinar o maior valor possível da variável que vai entrar na base, dividindo os termos independentes pelos coeficientes da variável nas várias restrições, para os casos em que sejam positivos, e considerando o menor dos quocientes positivos. A linha a que corresponde este menor quociente é a linha do pivot.

Se todos os quocientes forem negativos, a variável a entrar na base pode tomar um valor infinitamente grande e o problema diz-se sem solução limitada (ou sem óptimo finito);


Manipular as linhas do quadro, de acordo com as operações elementares realizadas com linhas de matrizes, de modo a obter um quociente unitário no lugar do pivot e valores nulos para os outros elementos da coluna pivot.

Obtém-se assim uma nova solução básica. Regressar ao 2º passo.


Para tornar mais simples a aplicação deste algoritmo recorre-se à construção de vários quadros. Uma vez que qualquer problema de maximização pode ser facilmente convertido num problema de minimização, consideraremos apenas o caso da minimização para facilitar a exposição.

Assim, o problema na forma canónica corresponde ao seguinte quadro:







x1

x2

...

xm

...

xn

bi




a11

a12

...

a1m

...

a1n

b1




...
















...




am1

am2

...

amm

...

amn

bm

Z

c1

c2

...

cm

...

cn

0

Quadro 3.3.1
Em que o canto inferior direito representa o simétrico do valor da função objectivo.

Segue-se o algoritmo descrito, registando-se as várias fases em diferentes quadros. No fim do processo iterativo:

- a solução óptima é obtida atribuindo-se a cada variável não básica o valor zero e a cada variável básica o valor da linha correspondente ao número 1, da sua coluna, na última coluna;

- o valor óptimo da função objectivo é o simétrico do número resultante na última linha e na última coluna. Caso se trata-se de um problema de maximização, seria mesmo o valor e não o seu simétrico.


3.4 EXEMPLOS DE APLICAÇÃO DO MÉTODO SIMPLEX
Dado que a representação gráfica da resolução de P.L. com mais de duas variáveis se torna difícil de interpretar, usa-se nesses casos o método simplex.

Iremos expor de seguida dois exemplos de resolução de problemas usando este método.

Apresentamos primeiramente um problema com duas variáveis (exemplo de maximização, já exposto anteriormente) pois consideramos que ajuda à compreensão do método. Posteriormente, apresentamos o problema com três variáveis.
1º Problema

Retomemos o problema de maximização descrito em 2.5.1


Resolução usando o método simplex:
x = x1 = n.º de unidades do Produto 1

y = x2 = n.º de unidades do Produto 2


max Z = 3x1 + 5x2

sujeito a x1 ≤ 4

2x2 ≤ 12

3x1 + 2x2 ≤ 18


Introduzindo as variáveis de folga x3, x4, x5, obtemos:
x1 + x3 = 4

2x2 + x4 = 12

3x1 + 2x2 + x5 = 18
Aplicando o método simplex, obtemos sucessivamente os quadros:





x1

x2

x3

x4

x5

b

x3

1

0

1

0

0

4

x4

0

2*

0

1

0

12

x5

3

2

0

0

1

18

Z

-3

-5

0

0

0

0

Quadro 3.4.1
A primeira solução básica admissível é (x1, x2, x3, x4, x5) = (0, 0, 4, 12, 8); onde x1, x2 são variáveis não básicas e x3, x4, x5 são as variáveis básicas. Verificamos que esta solução não é óptima, visto que existem custos reduzidos negativos: -3 e -5.

A variável a entrar na base é x2, porque entre as variáveis não básicas com custo reduzido negativo é a que tem menor valor.

A variável de saída é x4, porque o min  12/2, 18/2 corresponde à linha definida por esta variável básica.

O pivot neste caso é 2 (assinalado com um asterisco).

A actualização do quadro simplex é feita utilizando as seguintes operações elementares:

L1  L1



L2  1/2L2

L3  L3 – L2

L4  L4 + 5/2L2






x1

x2

x3

x4

x5

b

x3

1

0

1

0

0

4

x2

0

1

0

1/2

0

6

x5

3*

0

0

-1

1

6

Z

-3

0

0

5/2

0

30

Quadro 3.4.2
Obtemos uma nova solução básica admissível (x1, x2, x3, x4, x5) = (0, 6, 4, 0, 6); esta solução ainda não é óptima pois existe um custo reduzido negativo.

Repare-se que para esta solução a função objectivo é 30.

A variável a entrar na nova base é x1, porque entre as duas variáveis não básicas é a única que tem um custo reduzido negativo.

A variável de saída é x5, porque o min {4/1,6/3} corresponde à linha definida por x5.

O novo pivot é 3 (assinalado com um asterisco).

A nova actualização do quadro simplex é feita utilizando as seguintes operações elementares:

L1  L1 – 1/3L3

L2  L2

L3  1/3L3

L4  L4 + L3







x1

x2

x3

x4

x5

b

x3

0

0

1

1/3

-1/3

2

x2

0

1

0

1/2

0

6

x1

1

0

0

-1/3

1/3

2

Z

0

0

0

3/2

1

36

Quadro 3.4.3
A nova solução básica admissível é (x1, x2, x3, x4, x5) = (2, 6, 2, 0, 0) ; uma vez que neste último quadro não existem custos reduzidos negativos, esta solução é óptima. Sendo o valor máximo da função objectivo 36.

2º Problema
Considere-se o seguinte problema:

Uma empresa fabrica três tipos de kits electrónicos (I, II, III). Estes tipos de kits são processados em três secções distintas (A, B, C).

Considerando como variáveis o número de kits a produzir de cada tipo, e sabendo que:

- o kit do tipo I necessita de: 2 horas de trabalho diárias nas secções A e B e apenas 1 na C;

- o kit do tipo II necessita de: 2 horas de trabalho diárias na secção A, 1 na B e 3 na C;

- o kit do tipo III necessita de: 1 hora de trabalho diário nas secções A e B e 2 na C;

- as horas de trabalho diárias nas secções A, B e C não podem exceder as 12, 9 e 16 horas respectivamente.

Por outro lado, o lucro unitário de cada um dos tipos de kits é de: 8 euros para os do tipo I e II e 1 euro para os do tipo III.

Pretende-se determinar quantas unidades dos diferentes tipos de kits devem ser fabricados de modo a maximizar o lucro.
Resolução usando o método simplex:
x1 = n.º de kits a produzir do tipo I

x2 = n.º de kits a produzir do tipo II

x3 = n.º de kits a produzir do tipo III
max Z = 8x1 + 8x2 + x3
sujeito a 2x1 + 2x2 + x3 ≤ 12

2x1 + x2 + x3 ≤ 9

x1 + 3x2 + 2x3 ≤ 16
Introduzindo as variáveis de folga x4, x5, x6, obtemos:
2x1 + 2x2 + x3 + x4 = 12

2x1 + x2 + x3 + x5 = 9

x1 + 3x2 + 2x3 + x6 = 16

Aplicando o método simplex, obtemos sucessivamente os quadros:







x1

x2

x3

x4

x5

x6

b

x4

2

1

1

0

0

0

12

x5

2*

1

1

0

1

0

9

x6

1

3

2

0

0

1

16

Z

-8

-8

-1

0

0

0

0

Quadro 3.4.4
A primeira solução básica admissível é (x1, x2, x3, x4, x5, x6) = (0, 0, 0, 12, 9, 16); onde x1, x2, x3 são variáveis não básicas e x4, x5, x6 são as variáveis básicas. Verificamos que esta solução não é óptima, visto que existem custos reduzidos negativos: -8 e -1.

A variável a entrar na base é x1 porque, entre as variáveis não básicas com custo reduzido negativo, é a que tem menor valor.

A variável de saída é x5, porque o min  12/2, 9/2, 16/1 corresponde à linha definida por esta variável básica.

O pivot neste caso é 2 (assinalado com um asterisco).

A actualização do quadro simplex é feita utilizando as seguintes operações elementares:

L1  L1 – L2



L2  1/2L2

L3  L3 – 1/2L2

L4  L4 + 4L







x1

x2

x3

x4

x5

x6

b

x4

0

1*

0

1

-1

0

3

x1

1

1/2

1/2

0

1/2

0

9/2

x6

0

5/2

3/2

0

-1/2

1

23/2

Z

0

-4

3

0

4

0

36

Quadro 3.4.5

Obtemos uma nova solução básica admissível (x1, x2, x3, x4, x5, x6) = (9/2, 0, 0, 3, 0, 23/2); esta solução ainda não é óptima pois existe um custo reduzido negativo.

Repare-se que para esta solução a função objectivo é 36.

A variável a entrar na nova base é x2, porque entre as duas variáveis não básicas é a única que tem um custo reduzido negativo.

A variável de saída é x4, porque o min {3, 9, 23/5} corresponde à linha definida por x4.

O novo pivot é 1 (assinalado com um asterisco).

A nova actualização do quadro simplex é feita utilizando as seguintes operações elementares:

L1  L1



L2  L2 – 1/2L1

L3  L3 – 5/2L1

L4  L4 + 4L1







x1

x2

x3

x4

x5

x6

b

x2

0

1

0

1

-1

0

3

x1

1

0

1/2

-1/2

1/4

0

3

x6

0

0

3/2

-5/2

2

1

4

Z

0

0

3

4

0

0

48

Quadro 3.4.6
A nova solução básica admissível é (x1, x2, x3, x4, x5, x6) = (3, 3, 0, 0, 0, 4); uma vez que neste último quadro não existem custos reduzidos negativos, esta solução é óptima. Sendo o valor máximo da função objectivo 48.
Assim, concluímos que se devem produzir 3 unidades de kits do tipo I e do tipo II e nenhuma do tipo III para que o lucro seja máximo (48 euros).
Este exemplo foi resolvido usando o algoritmo primal do método simplex. A resolução do método simplex depende do tipo de restrições que estamos a considerar e neste trabalho abordámos apenas restrições do tipo  ; se as restrições forem do tipo  ou do tipo = existem outras formas de resolução. Por exemplo, no caso da igualdade existem dois processo de resolução: o dos grandes M’s e o das duas fases. Existem ainda outros algoritmos: primal-dual e dual. No entanto, é de destacar que o método simplex é único.

  1. CONCLUSÃO

Terminado este trabalho e após a pesquisa realizada para o mesmo, verifica-se que de facto a Programação Linear é uma ciência com uma vasta aplicação em problemas reais e do quotidiano e, por isso mesmo, muito útil.

Tentou-se corresponder ao pretendido, apresentando os conteúdos teóricos do tema em questão, seguidos de exemplos de situações reais, em que a interpretação gráfica toma principal destaque. Dada a complexidade inerente ao Método Simplex, não foi possível abordá-lo em toda a sua extensão; contudo, procurou-se elucidar a sua grande utilidade na resolução de problemas P.L. com três ou mais variáveis e/ou com muitas restrições.

No entanto, muito mais se poderia falar, pois a P.L. é uma ciência bastante vasta e que actualmente abrange muitas e variadas áreas de actividades.



Assim, importa realçar o seu contributo na área da Matemática e, em particular, no âmbito do ensino secundário.


Bibliografia




  • CASTI, John L. – Cinco Regras de Ouro. Lisboa: Gradiva, 1999.




  • Danø, Sven - Linear Programming. Viena: 1972.




  • FERREIRA, Manuel A. M.; AMARAL, Isabel – Programação Matemática. Lisboa: Edições Sílabo, 1995.




  • LIMA, Yolanda; Gomes, Francelino – XEQ MAT, Matemática 11º ano. Lisboa: Editorial O Livro, 1997.




  • MOKHTAN, S. Bazanaa; John, J. Jarvis; HANIF, D. Sherali – Linear Programming and Network Flows. 2ª edição. Singapura: 1990.




  • RAMALHETE, Manuel; GUERREIRO, Jorge; Magalhães, Alípio – Programação Linear, Volume 1. Alfragide: McGraw-Hill, 1984.




  • TAVARES, L. Valadares; OLIVEIRA, R. Carvalho; THEMIDO, I. Hall; CORREIA, F. Nunes – Investigação Operacional. Alfragide: McGraw-Hill, 1997.




  • Sites da internet

www.terravista.pt

www.sapo.pt

www.google.pt

www.clix.pt

www.yahoo.com


  • Programa utilizado: Graphmatica



1Esta situação não ocorre em problemas de minimização devido às condições de não negatividade.

2 Ponto extremo de um conjunto convexo K é um ponto que não pertence ao segmento de recta a unir dois pontos quaiquer de K.






Compartilhe com seus amigos:
1   2   3


©principo.org 2019
enviar mensagem

    Página principal