Introdução ao metodo simplex

...

[pic 8]

Sejam e duas soluções viáveis quaisquer, então[pic 9][pic 10]

eq.1[pic 11]

eq.2[pic 12][pic 13]

Considere o vetor [pic 14][pic 15]

Temos que provar que

[pic 16]

[pic 17]

Considerando que

[pic 18]

Então para combinação convexa de temos;[pic 19][pic 20]

Se α = 0 → x = [pic 21]

Se α = 1 → x = [pic 22]

Então podemos escrever:

[pic 23]

Devido as relações eq.1 e eq.2 passa-se ter

[pic 24]

[pic 25]

Fazendo , e lembrando que , resulta[pic 26][pic 27]

[pic 28]

Teorema 2:

Enunciado:

Toda solução viável básica do sistema é um ponto extremo do conjunto de soluções viáveis, isto é, do conjunto convexo D.[pic 29]

Demonstração:

Considere o conjunto convexo formado por:

[pic 30]

[pic 31]

De maneira explicita tem-se:

[pic 32]

Considere a solução viável básica formada pelo vetor x de dimensão n x 1

com todas as variáveis de decisão [pic 33][pic 34]

Suponha que x é um ponto extremo do conjunto convexo D {[pic 35]

Então se x pode ser obtido como uma combinação convexa de dois outros pontos quaisquer y e z pertencentes a D isto é

[pic 36]

Como por hipótese (y e z) ∈ D as seguintes relações são válidas:

Ay = b y ≥ 0

Az = b z ≥ 0

Se x for um ponto extremo de D então não existem ( y e z ) ≠ x que satisfaçam a relação:

[pic 37][pic 38]

A relação anterior, expressa em termos das coordenadas de cada um dos três vetores, fornece as seguintes relações:

[pic 39]

[pic 40]

.....................................

[pic 41]

(n-m) [pic 42]

m+i ; i = 1, 2,..., n-m

Devido às relações: , y ≥ 0 e z ≥ 0, as últimas (n-m) relações só podem ser satisfeitas num dos seguintes casos:[pic 43]

- , . Neste caso tem-se x = y = z, pois as três soluções apresentam uma coincidência nas variáveis não básicas;[pic 44][pic 45]

- para i =1,... n – m. Neste caso tem-se x = z, pelas razões anteriores.[pic 46][pic 47]

3)Se e para i =1,......n – m. Neste caso tem-se x = y, pelas razões anteriores.[pic 48][pic 49]

Fica assim demonstrado que não existem soluções viáveis y e z distintas da solução viável básica x que satisfaçam a relação,

[pic 50][pic 51]

Então o ponto x é um ponto extremo.

Teorema III:

- “se a função objetivo possui um máximo (mínimo) finito, então pelo menos uma solução ótima é um ponto extremo (vértice) do conjunto convexo D do Teorema I”.

- “se uma função objetiva assume o máximo (mínimo) em mais de um ponto extremo, então ela toma o mesmo valor para qualquer combinação convexa desses pontos extremos.

Demonstração da parte a do Teorema III :

Seja D o conjunto convexo definido por { .[pic 52]

Seja Z(x) a função objetivo que toma o valor máximo (mínimo) M no ponto , então se pode afirmar que: [pic 53][pic 54]

Sejam , ,..., os pontos extremos do conjunto convexo D. [pic 55][pic 56][pic 57]

Tem-se que provar que é um destes pontos extremos.[pic 58]

Suponha que não seja um ponto extremo do conjunto convexo D, sendo assim ele pode ser obtido como uma combinação convexa conforme dado a seguir:[pic 59]

sendo que ≥0 (i = 1,2,.....p) e [pic 60][pic 61][pic 62]

Utilizando as relações anteriores pode-se obter:

=[pic 63][pic 64]

[pic 65]

Considere agora o ponto extremo d [pic 66][pic 67][pic 68]

Devido as relações e a relação [pic 69][pic 70]

pode sofrer a seguintes modificações:[pic 71]

ou seja[pic 72]

[pic 73]

Inicialmente tinha sido colocado que , então é necessário ter e utilizando as propriedades das desigualdade que diz: [pic 74][pic 75]

Se e então implica que Aplicando esta propriedade da desigualde resulta : [pic 76][pic 77][pic 78]

[pic 79]

Desta forma fica provado que a solução ótima é o ponto extremo do conjunto convexo D.[pic 80]

Demonstração