Simplex passo a passo

Disponível somente no TrabalhosFeitos
  • Páginas : 27 (6638 palavras )
  • Download(s) : 0
  • Publicado : 17 de novembro de 2011
Ler documento completo
Amostra do texto
3- O MÉTODO SIMPLEX 3.1- Introdução O Método Simplex é uma técnica utilizada para se determinar, numericamente, a solução ótima de um modelo de Programação Linear. Será desenvolvido inicialmente para Problemas de Programação Linear, na forma padrão, mas com as seguintes características para o sistema linear de equações: i) ii) iii) Todas as variáveis são não-negativas: Todos os bi’ sãonão-negativos; Todas as equações iniciais do sistema são do tipo “ ≤ “. Assim, na forma padrão, só encontra-se variáveis de folga.

Se uma das características vistas não ocorrer, então, casos especiais do método devem ser considerados e esses serão vistos na seção 3.8, como o Método Simplex de Duas Fases. 3.2- Introdução e fundamentos teóricos para o Método Simplex 3.2.1- Determinação de soluções básicasem um sistema de equações lineares m x n , m ≤ n (sistemas lineares) Se ao resolver-se um sistema Ax=b, onde A ⊂ rmxm, x ∈ rm e b ∈ rm e A fosse uma matriz inversível, então a solução seria facilmente determinada.
A ∈ℜ mxn

Porém, se dado um sistema Ax=b, onde: b ∈ℜ m
x ∈ℜ n

m≤n

(3.1)

Tal que m≤ n, ou seja, sistema é retangular, como determinar soluções de Ax=b? O sistema acima sempretem solução?

29

Teorema 3.2.1.1: Seja a matriz A ∈ ℜmxn com m ≤ n. Se a matriz A possui m colunas a1, a2,…, am linearmente independentes (LI’s), então para qualquer b ∈ ℜm , o sistema Ax=b tem ao menos uma solução em ℜn . Definição 3.2.1.1: Seja Ax=b, A ∈ ℜmxn , b ∈ ℜm, x ∈ ℜn (m ≤ n). Se A possui uma submatriz B ∈ ℜmxn onde det B ≠ 0 então diz-se que B é uma submatriz base de A, o que éequivalente a dizer: “Se A tem m colunas LI, então a matriz B formada por estas colunas é uma base para ℜm”. Definição 3.2.1.2 - Variáveis básicas e não básicas: Considerando-se o sistema Ax=b, definido em (3.1) e B ∈ ℜmxm uma submatriz base de A, então, as variáveis associadas à submatriz B ∈ ℜmxm são denominadas variáveis básicas. Notação: variáveis básicas: xB. Definida a submatriz base B restamem A submatriz N são denominadas variáveis não básicas. Notação: variáveis não básicas: xN. 3.2.1.2- Uma possível solução para Ax=b da definição acima Seja o sistema Ax=b e suponha que extrai-se de A uma (n - m) colunas que

chamará-se de submatriz não base N. As variáveis associadas a esta

submatriz B ∈ ℜmxm. Pelas definições anteriores pode-se fazer as seguintes partições no sistema Ax=b: A= [B; N], x = Logo pode-se escrever:
xB . xN

30

Ax=b ⇔ [B: N]

xB = b ⇔ BxB+NxN=b. xN
(3.2)

Portanto, o sistema Ax=b é equivalente ao sistema: BxB+NxN=b.

Isto define que xB = B-1b - B-1NxN é uma possível solução de Ax=b. Definição 3.2.1.3 - Solução básica de Ax=b: Seja o sistema Ax=b definido em (3.1), então uma solução x de Ax=b, ou seja, A x =b, é denominada solução básica, see somente se, em (3.2), xN=0, então: A x =b ⇔ x B = B-1b
x B: solução básica.

Definição 3.2.1.4 - Solução básica factível (viável):
x é denominada solução básica factível para Ax=b se, e somente se: x B = B-1b e x N = 0, para x ≥ 0 (ou seja x B ≥ 0).

3.3- Definições e Teoremas Fundamentais Seja o conjunto S = { x ∈ ℜ n tal que Ax = b, x ≥ 0} onde A ∈ℜ mxn , b ∈ ℜ m e x ∈ℜ n com m ≤ n.Definição 3.3.1: x será um ponto extremo de S se possuir n-m variáveis nulas. Teorema 3.3.1: “O conjunto S, de todas as soluções factíveis do modelo de Programação Linear, é um conjunto convexo”. Prova: Sejam x1 e x2 ∈ S , λ ∈ [0,1].
31

Mostrará-se que: i) λ x1 + (1- λ )x2 ∈ S; ii) λ x1 + (1- λ ) x2 ≥ 0. Para se mostrar i) basta notar que, Se x1 ∈ S e x2 ∈ S Ax1 = b Ax2 = b; Assim, A( λ x1 + (1-λ )x2) = λ A x1 + (1- λ ) Ax2 = λ b + (1- λ )b = b. Logo, A( λ x1 + (1- λ )x2) = b. Para se mostrar ii): x1 ≥ 0 e x2 ≥ 0 assim , λ x1 + (1- λ ) x2 ≥ 0.
∴ λ x1 + (1- λ ) x2 ∈ S . ∴ S é convexo. λ x1 ≥ 0 e (1- λ ) x2 ≥ 0;

Teorema 3.3.2: “Toda solução básica do sistema conjunto de soluções factíveis S”. Prova: Seja x uma solução básica associada a uma submatriz base B ∈ ℜ mxm . Então, sem...
tracking img