Plano Financeiro

IO I

Método do Simplex

Introdução
O algoritmo do simplex foi criado pelo matemático norte americano
George Dantzig em 1947.
O algoritmo do simplex é um processo iterativo que consiste em resolver repetidas vezes um sistema de equações lineares para obter uma sucessão de SBA, em que o valor da função objetivo da SBA seguinte é melhor que o da anterior, quando não é possível melhorar mais o valor da função objetivo então essa solução é ótima.
O método Simplex é uma técnica utilizada para determinar analiticamente a solução ótima de um modelo de Programação Linear que se encontre na forma Standard e em que x j  0 e bi  0 i, j.

1

Teorema: Um ponto XK é uma solução básica admissível sse é um ponto extremo.
O método do simplex baseia-se no seguinte:
• O conjunto K de soluções admissíveis de um problema de P.L. é convexo. • A solução ótima encontra-se num ponto extremo de K
• Um ponto extremo é uma SBA
Então a ideia principal é iniciar o método com uma SBA inicial e analisar o ponto extremo que lhe é adjacente e em que existe melhoria do valor da função objetivo até obter o ponto extremo ótimo.

2

Considere o exemplo 1:

Forma canónica
Max Z=x1 +2x2

Forma standard
Max Z=x1 +2x2 +0s1 +0s2 +0s3

 x1
+s1 =60

x2 +s2 =40


s.a.  x1  x2 +s3  80
 x  0 j  1, 2
 j
 si  0 i  1, 2,3

A standardização do problema consiste na introdução de variáveis auxiliares s1 , s2 e s3 positivas de modo a passar de inequações a equações, em que o coeficiente das variáveis na função objetivo é nulo.
A matriz A do problema é a seguinte:

 60
 x1

x2  40

s.a. 
 x1  x2  80
 x j  0 j  1, 2


1 0 1 0 0 
A  0 1 0 1 0 


1 1 0 0 1 



Base= s1 , s2 , s3  do espaço R 3 s1 , s2 , s3 variáveis básicas x1 e x2 variáveis não básicas
3

O conjunto das soluções admissíveis do problema e os seus pontos extremos (SBA) estão representados no gráfico seguinte:

A=(0,0,60,40,80)