Método Simplex Resolução Algébrica

O método algébrico para solução de um modelo linear
A solução de problemas de programação linear com mais de duas variáveis, não pode
ser obtida utilizando-se o algoritmo gráfico. Como cada variável é representada por um eixo
do gráfico, um problema com mais de duas variáveis não pode ser representado no plano, o
que torna a visualização da solução impossível ou muito complexa, como podemos observar
no exemplo a seguir.
Exemplo de P.P.L. com três variáveis de decisão.
Modelo:
Função Objetivo
MÁX Z = 4 * X1 + 4 * X2 + 4 * X3
Restrições:
R1  -->4 * X1 + 3 * X2 <= 12
R2 --> X2 <= 3
R3 --> X3 <= 2
Restrições implícitas:
R4 --> X1 >=0
R5 --> X2 >= 0
R6 --> X3 >= 0
OBS.:
- O conjunto de soluções viáveis para o modelo acima, será representado
graficamente em três dimensões, como um poliedro, cujas faces são os planos limites das
restrições.
- A função objetivo será representada como uma família de planos paralelos ao plano
Zqq apresentado na figura 6.1, que faz um ângulo de 45o com os três eixos.
- O ponto ótimo será o vértice do poliedro mais afastado da origem.
PESQUISA OPERACIONAL

Conceitos da álgebra linear utilizados pelo algoritmo SIMPLEX

Um sistema de equações lineares pode ser resolvido, algebricamente, dividindo-se e

multiplicando-se por constantes as equações e somando-as entre si. Estas operações alteram o

sistema inicial, mas não modificam o resultado dos sistemas.

Resolvendo o sistema abaixo algebricamente e acompanhando pelo gráfico temos:

Sistema Inicial: R1 --> 3 * x1 + 3 * x2 = 9

R2 --> 2 * x1 + 4 * x2 = 8

Determinamos um novo sistema executando as seguintes operações:

a) Dividindo R1 por (3) encontramos uma nova equação R1,

b) Multiplicando a nova R1 por (-2) e somando com R2 do sistema inicial,

encontramos a nova equação R2.

O novo sistema é mais simples, mas possui a mesma solução do sistema inicial.

O novo sistema: R1 --> 1 * x1 + 1 * x2 = 3

R2 --> 2 * x2 = 2

Determinamos um novo sistema executando as seguintes operações:

a) Dividindo R2 por (2) encontramos uma nova equação R2,

b) Multiplicando a nova R2 por (-1) e somando com R1 do sistema anterior,

encontramos a nova equação R1.

O novo sistema é mais simples, mas possui a mesma solução do sistema inicial.

O novo sistema: R1--> 1 * x1 = 2

R2 --> 1 * x2 = 1

Generalizando, a partir do exemplo anterior, verificamos que para resolver um

sistema qualquer de equações lineares, devemos transformar o sistema da forma geral para

uma forma reduzida onde cada variável apareça independente, associada à uma equação.

Exemplo: Forma Geral de um sistema linear com duas equações.

R1 --> a11 * x1 + a12 * x2 = b1

R2 --> a21 * x1 + a22 * x2 = b2

Forma Reduzida.

R1 --> x1 = d1

R2 --> x2 = d2

O sistema reduzido possui a mesma solução do sistema original.

Usando a notação matricial temos:

Forma geral: A*X = B Forma reduzida: I* X = D

Onde: A é uma matriz genérica;

X é um vetor de variáveis;

B e D são vetores de constantes e

I é a matriz identidade com a mesma ordem da matriz A.