Metodo Simplex

Objectivo Geral: Resolver problemas de programação linear, usando o algoritmo simplex a partir do seu modelo matemático.

Fundamentação Teórica

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.

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 = c₁x₁ + c₂x₂ + ... +c_nx_n  

         Sujeito a:   a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁

                                      a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b                      

                               a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_n

                              

                          x₁, x₂, …, x_m, ..., x_n   ≥  0   (m  ≤ n)    

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: b_i ≥ 0                     (i = 1, 2, ..., m). Caso contrário pode sempre multiplicar-se por (-1) toda a equação.

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 (B_{m 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 das restrições é 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 = (x₁, x₂, …, x_m, x_m+1, …, x_n) é uma solução desse sistema.

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

As m variáveis x₁, x₂, …, x_m correspondentes às colunas de B_{m x m} designam-se por variáveis básicas. As restantes n-m variáveis x_m+1, x_m+2, …, x_n 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 x_m+1, x_m+2, …, x_n e determinando depois uma solução para as m variáveis básicas restantes x₁, x₂, …, x_m . Isto é, X = (0, ..., 0, x₁, x₂, …, x_m), onde          X_B = (x₁, x₂, …, x_m) é a única solução do sistema de equações BX_B = 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 x₁, x₂, …, x_m 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.

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  simplex pode ser sintetizado nos seguintes passos:

1º Obter uma primeira solução básica admissível;

2º 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;

3º 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;

4º 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);

       5º 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

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.

 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

Resolução usando o método simplex:

x = x₁ = n.º de unidades do Produto 1

y = x₂ = n.º de unidades do Produto 2

max Z = 3x₁ + 5x₂

sujeito a         x₁ ≤ 4

2x₂ ≤ 12

3x₁ + 2x₂ ≤ 18

Introduzindo as variáveis de folga x₃, x₄, x₅, obtemos:

x₁ + x₃ = 4

2x₂ + x₄ = 12

3x₁ + 2x₂ + x₅ = 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

A primeira solução básica admissível é (x₁, x₂, x_3, x₄, x₅) = (0, 0, 4, 12, 8); onde x₁, x₂ são variáveis não básicas e x₃, x₄, x₅ 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 é x₂, porque entre as variáveis não básicas com custo reduzido negativo é a que tem menor valor.

A variável de saída é x₄, 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:

                        L₁ ® L₁

                               L₂ ® 1/2L₂

                               L₃ ® L₃ – L₂

L₄ ® L₄ + 5/2L₂

	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

Obtemos uma nova solução básica admissível (x₁, x₂, x_3, x₄, x₅) = (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 é x₁, porque entre as duas variáveis não básicas é a única que tem um custo reduzido negativo.

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

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

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

            L₁ ® L₁ – 1/3L₃

                               L₂ ® L₂

                               L₃ ® 1/3L₃

                        L₄ ® L₄ + L₃

	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

A nova solução básica admissível é (x₁, x₂, x₃, x₄, x₅) = (2, 6, 2, 0, 0) ; uma vez que neste último quadro não existem custos reduzidos negativos, esta solução é óptima.

Como resposta: precisa­se de 2 unidades do produto1 e 6 unidades do produto2 para que se atinja um lucro máximo de 36.

BIBLIOGRAFIA

1. Goldbarg, M.C. Luna, H.P.L. (2005) Otimização Combinatória e Programação Linear. Modelos e Algoritmos. 2ª Edição. Editora Campus.

2.  Hillier F. S., Lieberman G. J. (2010) Introdução à Pesquisa Operacional. 8ª Edição. Editoras Mc Graw Hill e bookman.

3. Taha, Hamdy A. (2008) Pesquisa Operacional: Uma Visão Geral. 8ª Edição. São Paulo. Pearson Prentice Hall.

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

5. Tavares, L. Valadares; Oliveira, R. Carvalho; Themido, I. Hall; Correia, F. Nunes – Investigação Operacional.  Alfragide: McGraw-Hill, 1997.