INVESTIGAÇÃO OPERACIONAL

5ª Aula

Método Simplex na forma Tabular

A forma tabular do método simplex permite guardar só a informação mais relevante do problema,
nomeadamente:




Coeficientes ou parâmetros das variáveis
As constantes correspondentes ao lado direito das restrições
As variáveis básicas que aparecem em cada equação
Seguidamente vamos confrontar a forma algébrica e a forma tabular
Forma Algébrica
(0) Z – 3x1 – 2x2
(1)
x1 +
x3
(2)
x1 + 3x2 +
(3)
2x1 + x2 +


Cecília Rocha # 1
x4
Forma Tabular
Variável
Básica
Eq.
=0
Z
=4
Coeficientes de:
Lado Dir.
Z
x1
x2
x3
x4
x5
(0)
1
-3
-2
0
0
0
0
x3
(1)
0
1
0
1
0
0
4
= 15
x4
(2)
0
1
3
0
1
0
15
x5 = 10
x5
(3)
0
2
1
0
0
1
10
A variável básica em cada equação está salientada com sombreado, todas as outras variáveis são não básicas
O valor das VB é lido directamente na coluna mais à direita
2001/2002
INVESTIGAÇÃO OPERACIONAL

5ª Aula (cont.)

Aplicação do Método Simplex na Forma Tabular

Inicialização




Teste de Optimização



A solução actual (SBA) é óptima se e só se todos os coeficientes da linha (0) são não negativos
Se não forem todos não negativos continuar para a próxima iteração
Iterações




Cecília Rocha # 2
Introduzir as variáveis de folga
Seleccionar as variáveis de decisão para Variáveis Não Básicas
Seleccionar as variáveis de folga para serem Variáveis Básicas
Determinar a Variável Básica de Entrada (VBE) seleccionando a variável com coeficiente mais negativo na linha (0)
(neste caso x1 cujo coeficiente é – 3) – Coluna Pivot
Determinar a Variável Básica de Saída (VBS) aplicando o teste do rácio mínimo

Dividir o Lado Direito de cada equação pelo valor correspondente do coeficiente da coluna da VBE

Identificar a linha com menor rácio – Linha Pivot

A VBS será a correspondente a esta linha de menor rácio que passará a ser VNB

Na intersecção da Linha Pivot com a Coluna Pivot estará o Número Pivot

Só se admitem para o teste do rácio mínimo coeficientes da Coluna Pivot positivos
Realizar operações algébricas elementares para determinar a nova SBA
Repetir o teste de optimização e, eventualmente, realizar nova iteração
2001/2002
INVESTIGAÇÃO OPERACIONAL

5ª Aula (cont.)

Cont.
Iteração
0
1
2
Cecília Rocha # 3
VB
Eq.
Z
Coeficientes
LD
rácio
0
0
-
0
0
4
4 1 = 4
0
1
0
15
15 1 = 15
1
0
0
1
10
10 2 = 5
0
-2
3
0
0
12
-
0
1
0
1
0
0
4
S/s
(2) – (1)
0
0
3
-1
1
0
11
113 = 3.67
X5
(3) – 2 (1)
0
0
1
-2
0
1
2
2 1 = 2
Z
(0) + 2 (3)
1
0
0
-1
0
2
16
-
X1
(1)
0
1
0
1
0
0
4
4 1 = 4
X4
(2) – 3 (3)
0
0
0
5
1
-3
5
5 5 = 1
X2
(3)
0
0
1
-2
0
1
2
S/s
Z
x1
x2
x3
x4
x5
(0)
1
-3
-2
0
0
X3
(1)
0
1
0
1
X4
(2)
0
1
3
x5
(3)
0
2
Z
(0) + 3 (1)
1
X1
(1)
X4
2001/2002
INVESTIGAÇÃO OPERACIONAL

5ª Aula (cont.)

Cont.
Iteração
2
3
Cecília Rocha # 4
VB
Eq.
Z
Coeficientes
LD
rácio
2
16
-
0
0
4
4 1 = 4
5
1
-3
5
5 5 = 1
1
-2
0
1
2
S/s
0
0
0
1/5 = 0.2
7/5 = 1.4
17
0
1
0
0
-1/5= - 0.2
3/5 = 0.6
3
(2)  5
0
0
0
1
1/5 = 0.2
-3/5 =- 0.6
1
(3) + 2 (2)
0
0
1
0
2/5 = 0.4
-1/5 =- 0.2
4
Z
x1
x2
x3
x4
x5
(0) + 2 (3)
1
0
0
-1
0
X1
(1)
0
1
0
1
X4
(2) – 3 (3)
0
0
0
x2
(3)
0
0
Z
(0) + (2)
1
X1
(1) – (2)
X3
X2

Sequência de SBA: (0, 0, 4, 15, 10)  (4, 0, 0, 11, 2)  (4, 2, 0, 5, 0)  (3, 4, 1, 0, 0)

Como não há mais coeficientes negativos na linha (0) já encontramos a solução óptima para Z = 17
2001/2002
INVESTIGAÇÃO OPERACIONAL

5ª Aula (cont.)

Desempates no Método Simplex

Desempate para a Variável Básica de Entrada





Cecília Rocha # 5
Se existem várias variáveis com coeficientes negativos na linha (0), podemos escolher a Variável Básica de Entrada
arbitrariamente.
Exemplo  Z – 3x1 – 3x2 = 0
Desempate para a Variável Básica de Saída – Solução Degenerada

Se várias variáveis básicas atingirem o valor zero ao mesmo tempo (ou seja, têm o mesmo rácio no teste do rácio
mínimo)

Resolve-se pela escolha arbitrária de uma das hipóteses para VBS e prossegue-se normalmente sem nos
preocuparmos com o facto de outras variáveis básicas também passarem a ter o valor zero
A função objectivo não é limitada

Não existem variáveis em condições para serem VBS

Exemplo: todos os coeficientes da Coluna Pivot têm valor nulo ou negativo
Existem múltiplas soluções óptimas

Quando se verifica que, na linha (0), existem variáveis não básicas com coeficiente zero

Se se realizarem iterações adicionais podemos determinar as outras SBA óptimas
2001/2002
INVESTIGAÇÃO OPERACIONAL

5ª Aula (cont.)

Utilização da Opção SOLVER do EXCEL


No menu Ferramentas (Tools) escolher a opção Suplementos (Add-Ins) e seleccionar Solver.
Transcrever o problema, já na forma de modelo matemático, para o Excel,tendo o cuidado de:





Seleccionar no menu Ferramentas a opção Solver:





Cecília Rocha # 6
O problema deve estar na forma de quadro, com os parâmetros das expressões das restrições, distribuídos por
linha, e afectos a cada variável de decisão, por coluna;
No final das colunas de parâmetros e antes da coluna do termo do lado direito das restrições, introduzir uma
coluna com as expressões das restrições.;
Deve haver uma ou mais linhas para as variáveis de decisão;
Seleccionar uma célula para ter a expressão da função objectivo;
No quadro que aparece deve ser seleccionada a célula onde está a expressão da função objectivo – Célula de
Destino (Target Cell);
Seguidamente, definir o tipo de operação a realizar: Minimizar, Maximizar ou atribuir um dado valor;
Na opção Por Alteração das Células (By changing cells) seleccionar o conjunto de células que representam o
valor das variáveis de decisão;
Na opção Sujeito às Restrições (Restrictions) seleccionar Adicionar (Add)

No lado esquerdo: células com expressão das restrições

Meio: sinal da restrição

No lado direito: lado direito das restrições
Ao seleccionar Opções pode-se escolher Mostrar resultados das Iterações (Show iterations results)
2001/2002