Introdução ao metodo simplex

CURSO DE ENGENHARIA DE AUTOMAÇÃO E CONTROLE

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS

NOTA DE AULA - DISCIPLINA OTIMIZAÇÃO

 MÉTODO SIMPLEX –

Introdução -

Neste texto é apresentada a introdução ao “Método Simplex”, técnica utilizada para achar algebricamente, a solução ótima de um modelo de Programação Linear (PL). Inicialmente é apresentada uma formulação teórica baseada em três teoremas fundamentais, nos quais a técnica se baseia. Após, com base em exemplo numérico de PL é aplicado o algoritmo do “Método Simplex” para solução de problemas de PL, e apresentação de estudo de casos especiais.

O PROBLEMA PROGRAMAÇÃO LINEAR 

Começamos nossa discussão, formulando um determinado tipo de problema de programação linear.  Como se verá posteriormente, qualquer tipo de problema geral de programação linear pode ser manipulado para a  forma do método simplex.

Definições básicas- 
Considere o seguinte problema de programação linear.

O problema pode ser colocado na forma:

Minimizar  z  = c1x1 + c2x2 +..........+ cnxn 
sujeito as restrições

a11x1+ a12x2+ ........... +a1nxn ≥ b1

      a21x1+ a22x2+ ........... +a2nxn ≥ b2

      am1x1+ am2x2+ ...........+amnxn ≥ bm
     

      x1 ≥ 0; x2 ≥ 0; ................; xn ≥ 0

 Aqui, c1x1 + c2x2 +...+ cnxn é a função objetivo (ou função critério) a ser minimizada (ou maximizada) e será denotada por z. Os coeficientes c1, c2,..., cn são conhecidos e corresponde aos coeficientes de custo, x1, x2,..., xn são as variáveis de decisão (variáveis estruturais ou níveis de atividades) a serem determinados.
A desigualdade  representa a i-ésima restrição tecnológica ou estrutural. Os coeficientes aij para i = 1, 2,..., m e j = 1, 2,..., n são chamados de coeficientes tecnológicos. Estes coeficientes tecnológicos formam a matriz de restrição A.[pic 1]

[pic 2]

O vetor coluna cuja i-ésima componente é bi, que é referido como vetor do lado direito, representa as exigências mínimas a serem satisfeitas. As restrições x1 ≥ 0; x2 ≥ 0;...; xn ≥ 0 são restrições não negativas. Um conjunto de valores de x1; x2;...; xn satisfazendo todas as restrições é chamado de um ponto viável ou solução viável. O conjunto de todos os pontos constituem a região viável  ou o espaço viável.

Usando a terminologia precedente, o problema de programação linear pode ser estabelecido como segue:

Entre todas as soluções viáveis, encontrar uma que minimize (ou maximize) a função objetivo.

Fundamentação Teórica- do Método Simplex

Nesta seção são apresentados os Teoremas básicos para fundamentação teórica do Método Simplex.

Teorema 1:

O conjunto de todas as soluções viáveis (factíveis) do modelo de PL é um conjunto convexo.

Sendo o conjunto constituído pelas restrições:

  ( conjunto convexo de soluções viáveis)[pic 3]

Demonstração:

Vamos considerar o modelo matricial:

[pic 4]

[pic 5]

[pic 6]

Seja D o conjunto convexo formado por {}. Tem que provar que D é convexo. Para isto basta demonstrar que,[pic 7]

[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