PEOP2020 Aula 10 Teoria Simplex V4-0-3

Prévia do material em texto

Pesquisa Operacional – PEOP
“Descobrir, analisar, resolver!”
1
http://www.fab.mil.br/dimensao22/
Pesquisa Operacional – PEOP
Teoria do Método SIMPLEX
2
http://www.fab.mil.br/dimensao22/
Academia da Força Aérea
Curso de Formação de Oficiais Aviadores
Divisão de Ensino
Disciplina: Pesquisa Operacional (PEOP)
Docentes: Profa. Dra. Renata Belluzzo Zirondi Mori (renatabzmori@gmail.com)
Cel Av R1 José Francisco Braun (coronelbraun@gmail.com)
mailto:renatabzmori@gmail.com
mailto:coronelbraun@gmail.com
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica; 
• Conversão para a Forma Padrão.
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
O método SIMPLEX foi
desenvolvido na década de 40
pelo matemático americano
George Bernard Dantzig
Consiste em um algoritmo (sequência de
passos) baseado em procedimentos matemáticos
e heurísticas.
Possui diversas versões de implementação
e é utilizado também nos softwares de resolução
de problemas de PL.
6
SIMPLEX
7
SIMPLEX é nome dado ao 
tetraedro de quatro dimensões
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
9
Conhecimento necessário
para compreensão do SIMPLEX
premissa
substantivo feminino
Ponto de partida para a organização de um
raciocínio ou de uma argumentação.
Dicionário Priberam da Língua Portuguesa, 
https://dicionario.priberam.org/premissa
https://dicionario.priberam.org/premissa
MIN f(x) = CTx
sujeito a
Ax = b
com
x ≥ 0
-O problema deve ser de minimização;
-Todas restrições devem estar na forma de equações
lineares (igualdades);
-As restrições de não negatividade das variáveis devem
estar presentes;
10
Premissa-1: Para aplicação do SIMPLEX
o problema deve estar na forma padrão
Nomenclatura:
C = Vetor "custos"
A = Matriz dos
"coeficientes"
x = Vetor "incógnitas"
b = Vetor "recursos"
* A conversão de problemas para a forma padrão será retomada posteriormente
Conversão de inequações em equações 
-x +2y -1 + w= 0
3x-y-2 ≥ 0
-x+2y -1 .......... w .......... 0
Introdução de variáveis de folga (exemplo genérico)
Adicionando ou subtraindo uma variável nas 
expressões elas passam a ser equações
-x +2y -1 ≤ 0
3x - y -2 – k = 0
w é uma variável de folga
(“slack”)
k=é uma variável de excesso 
(“surplus”)
Genericamente
(neste caso w e k) ambas
são chamadas de
variáveis de folga
0 ........... k ........... 3x-y-2
11
Falta algo para a expressão ser igual a 0 Sobra algo para a expressão ser igual a 0
Premissa-1: Para aplicação do SIMPLEX
o problema deve estar na forma padrão
Função Objetivo:
Min f(x)=- 2x1 - 4x2
Restrições de
não negatividade:
x1 , x2 ≥ 0
Restrições: 
(A) 1x1 ≤ 4
(B) 2x2 ≤ 12 
(C) 3x1 + 2x2 ≤ 18 
Considere o seguinte problema de Otimização Linear 
Problema original Problema com as variáveis de folga
Função Objetivo: 
Min f(x)= - 2x1 - 4x2
Restrições (na forma de equações): 
(A) 1x1 + 1x3 = 4
(B) 2x2 + 1x4 = 12
(C) 3x1 + 2x2 + 1x5 = 18
Restrições de
não negatividade:
x1,x2,x3,x4,x5 ≥ 0
12
Uma variável de folga
para cada restrição do
tipo ≤ ou ≥
Premissa-1: Para aplicação do SIMPLEX
o problema deve estar na forma padrão
Conversão de inequações em equações 
+ 0x3 + 0x4+ 0x5
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
14
Premissa-2: A Solução Ótima estará em
um vértice da Região de Factibilidade
O exemplo ao
lado se refere a
uma Região de
Factibilidade
bidimensional,
mas o conceito
se aplica à
qualquer número
de dimensões.
Veja mais sobre Regiões de Factibilidade multidimensionais
na aula extra "O Espaço Multidimensional".
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
16
x2 =0
x1 = 0
x2
x1
Restrições do
problema na forma
de equações
2x2 + 1x4 = 12 
1x1 + 1x3 = 4
Minimizar:
Z= - 2x1 - 4x2 + 0x3 + 
+ 0x4 + 0x5
Sujeito a:
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18 
Com: 
x1, x2, x3, x4, x5 ≥ 0
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
A
B C
D
E
F
G
H
17
Com a inclusão das variáveis de folga, verificamos que temos 3
restrições (m) e 5 variáveis (n) formando um sistema do tipo
"indeterminado" com n-m= 5-3=2 graus de liberdade.
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18 
Para definirmos as soluções de um sistema
indeterminado arbitramos valores para
algumas variáveis de acordo com o grau de
liberdade do sistema.
As variáveis que terão seus
valores arbitrados são as
variáveis "independentes" as
demais serão as variáveis
"dependentes". Neste exemplo
temos dois graus de liberdade
e duas variáveis independentes
O número de soluções para cada
quantidade de variáveis e
equações de um sistema
indeterminado é dado pela
fórmula."
C=
𝑛!
(𝑚!). 𝑛−𝑚 !
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
18
x2 =0
x1 = 0
x2
x1
Coordenadas do
ponto A (x1=0 e
x2=0)
2x2 + 1x4 = 12 
1x1 + 1x3 = 4
Solução do sistema:
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18
ou 
0 + 1x3 = 4
0 + 1x4 = 12 
0 + 0 + 1x5 = 18
Coordenadas de A = (x1, x2, x3, x4, x5) = (0, 0, 4,12,18)
A
B C
D
E
F
G
H
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
19
x2 =0
x1 = 0
x2
x1
Coordenadas do
ponto C (x1=2 e
x2=6)
2x2 + 1x4 = 12 
1x1 + 1x3 = 4
Solução do sistema:
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18
ou 
2 + 1x3 = 4
12 + 1x4 = 12 
6 + 12 + 1x5 = 18
Coordenadas de C = (x1, x2, x3, x4, x5) = (2, 6, 2, 0, 0)
A
B C
D
E
F
G
H
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
20
x2 =0
x1 = 0
x2
x1
Coordenadas do
ponto D (x1=4 e
x2=3)
2x2 + 1x4 = 12 
1x1 + 1x3 = 4
Solução do sistema:
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18
ou 
4 + 1x3 = 4
6 + 1x4 = 12 
12 + 6 + 1x5 = 18
Coordenadas de D = (x1, x2, x3, x4, x5) = (4, 3, 0, 6, 0)
A
B C
D
E
F
G
H
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
21
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
Continuando o raciocínio do exemplo
teríamos 10alternativas de soluções para
o sistema formado pelas restrições na
forma de equações (igualdades).
C=
𝑛!
𝑚! . 𝑛−𝑚 !
=
5!
(3!). 5−3 !
= 10
As soluções do sistema são denominadas
"BÁSICAS". Serão "viáveis" se estiverem
nos vértices da Região de Factibilidade.
As soluções "impossíveis" do sistema são 
ignoradas pelo SIMPLEX.
Pelos exemplos constatamos que o
sistema do exemplo possui dois graus de liberdade, duas variáveis
independentes e duas variáveis com valor zero em cada solução
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
(0, 9, 4, -6, 0) F NÃO
(4, 6, 0 , 0, -6) G NÃO
(6, 0, -2, 12, 0) H NÃO
Sistema sem solução 
quando (x1 e x3 =0) 
e (x2 e x4 =0)
I
J
22
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
Decorre da premissa 3 que: Como cada
ponto de vértice terá um determinado
número de variáveis com valor zero (neste
exemplo são duas), se fixarmos duas
variáveis com valor zero e resolvermos o
sistema encontraremos as demais
coordenadas de um ponto de vértice.
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
(0, 9, 4, -6, 0) F NÃO
(4, 6, 0 , 0, -6) G NÃO
(6, 0, -2, 12, 0) H NÃO
Sistema sem solução 
quando (x1 e x3 =0) 
e (x2 e x4 =0)
I
J
Coordenadas do ponto onde (x2=0 e x3=0)
Solução do sistema:
1x1 + 1x3 = 4
2x2 + 1x4 = 12 
3x1 + 2x2 + 1x5 = 18
ou 
1x1 + 0 = 4
0 + 1x4 = 12 
3x1 + 0 + 1x5 = 18
Coordenadas do ponto = (x1, x2, x3, x4, x5) = (4, 0, 0, 12, 6) = ponto E
23
Premissa-3: Em cada vértice haverá
variáveis nulas na mesma quantidade das
variáveis independentes do sistema
As variáveis de cada Solução Básica que possuírem valor igual a zero
são as Variáveis Não Básicas, as que possuírem valor diferente de zero
serão denominadas variáveis Básicas.
Grau de liberdade do sistema formado pelas restrições na forma de 
igualdade (n-m)
RESUMO DA PREMISSA 3
Número de variáveis com valor zero em cada ponto de vértice do 
sistema 
Número de variáveis de decisão do problema (no exemplo x1 e x2)
Número de variáveis Não Básicas do problema
=
=
=
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
25
Matriz "A"
dos "coeficientes"
Vetor "x"
das"incógnitas" Vetor "b"
dos "recursos"
Minimizar:
𝑓(𝑥) = - 2x1 - 4x2 + 0x3 + 0x4 + 0x5
Com:
x1 , x2 , x3 , x4 , x5 ≥ 0
Sujeito a: 
1x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4
0x1 + 2x2 + 0x3 + 1x4 + 0x5 = 12
3x1 + 2x2 + 0x3 + 0x4 + 1x5 = 18
Dado um problema já com 
as variáveis de folga
−2
−4
0
0
0
Vetor "C"
dos "custos"
1 0 1 0 0
0 2 0 1 0
3 2 0 0 1
𝑥1
𝑥2
𝑥3
𝑥4
𝑥5
Partes do problema
na forma matricial:
4
12
18
Premissa-4: Será utilizado o formato
matricial
26
Premissa-4: Será utilizado o formato
matricial
Vetor "CT" dos 
"custos" transposto
Vetor "x"
das"incógnitas"
A multiplicação do vetor de
custos transposto pelo
vetor das incógnitas resultará
na função objetivo
−2 −4 0 0 0 x
𝑥1
𝑥2
𝑥3
𝑥4
𝑥5
= 𝑓(𝑥)
(1 x 5)
(5 x 1)
Resultado da operação de matrizes
(somatório da multiplicação das linhas
da primeira matriz pelas colunas da segunda)
-2𝑥1 -4𝑥2 +0𝑥3 +0𝑥4 +0𝑥5 = 𝑓(𝑥)
MIN f(x) = CTx
sujeito a
Ax = b
com
x ≥ 0
Relembre a
forma padrão de
um problema de
Otimização
Linear= Função Objetivo com as variáveis de folga
27
(3 x 5)
1 0 1 0 0
0 2 0 1 0
3 2 0 0 1
x
𝑥1
𝑥2
𝑥3
𝑥4
𝑥5
=
4
12
18
(5 x 1) (3 x 1)
MIN f(x) = CTx
sujeito a
Ax = b
com
x ≥ 0
Relembre a
forma padrão de
um problema de
Otimização
Linear
A multiplicação da matriz dos
coeficientes das variáveis pelo
vetor das incógnitas resultará
no vetor dos recursos
Premissa-4: Será utilizado o formato
matricial
Matriz "A"
dos "coeficientes"
Vetor "x"
das"incógnitas"
Vetor "b"
dos "recursos
Resultado da operação de matrizes
(somatório da multiplicação das linhas
da primeira matriz pelas colunas da segunda)
1𝑥1 + 0𝑥2 + 1𝑥3 +0𝑥4 + 0𝑥5 = 4
0𝑥1 + 2𝑥2 + 0𝑥3 +1𝑥4 + 0𝑥5 = 12
3𝑥1 + 2𝑥2 + 0𝑥3 +0𝑥4 + 1𝑥5 = 18
= Restrições do problema na forma de equações
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
A lógica do Método Simplex é:
1-Definir um ponto de início em um dos vértices da região
de factibilidade (ponto de vértice factível) e testar se o ponto
é a solução ótima ou não. Se for a solução ótima PARE,
senão:
2-Escolher um novo ponto (que forneça um valor melhor
para a Função Objetivo) entre os pontos de vértice factíveis
adjacentes e testá-lo. Se for a solução ótima PARE, senão
continue até achar a solução ótima.
29
Partir de um ponto de vértice factível para outro
melhor até encontrar a solução ótima é a
ESTRATÉGIA SIMPLEX.
Premissa-5: Será empregada a
Estratégia SIMPLEX
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
31
Premissa-6: O ponto de início
será a origem dos eixos
Existem duas possibilidades para uma Região de Factibilidade:
1ª- A origem dos eixos é um dos
seus vértices e pode-se iniciar a
Estratégia SIMPLEX por ela.
2ª- A origem dos eixos não é um dos
seus vértices. Neste caso será
criado um "problema artificial" que
inclua a origem como um dos seus
vértices e o SIMPLEX também
poderá começar por ela. Este caso
será visto mais adiante na disciplina
(SIMPLEX em Duas Fases).
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
33
Premissa-7: A matriz dos coeficientes das
restrições será dividida.
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
𝟏 𝟎 𝟏 𝟎 𝟎
𝟎 𝟐 𝟎 𝟏 𝟎
𝟑 𝟐 𝟎 𝟎 𝟏
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟑 𝟐
Matrizes do Ponto A
B =
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟎
𝟎 𝟏
𝟏 𝟎
Matrizes do Ponto C
Matriz BÁSICA: Variáveis
que terão valor diferente de
zero no ponto de vértice.
Matriz NÃO BÁSICA:
Variáveis que terão valor
zero no ponto de vértice .
B =
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
N=
𝟏 𝟎
𝟎 𝟏
𝟑 𝟎
Matrizes do Ponto B Matrizes do Ponto D
Matrizes do Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏 𝒙𝟐
𝒙𝟑 𝒙𝟒𝒙𝟓 𝒙𝟏𝒙𝟐
𝒙𝟏 𝒙𝟓𝒙𝟑 𝒙𝟐 𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟏
𝟎 𝟎
𝟏 𝟎
𝒙𝟏 𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟎 𝟎
𝟎 𝟏 𝟑
N=
𝟎 𝟏
𝟐 𝟎
𝟐 𝟎𝒙𝟏𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
34
𝟏 𝟎 𝟏 𝟎 𝟎
𝟎 𝟐 𝟎 𝟏 𝟎
𝟑 𝟐 𝟎 𝟎 𝟏
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟑 𝟐
Matrizes do Ponto A
B =
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟎
𝟎 𝟏
𝟏 𝟎
Matrizes do Ponto C
Matriz BÁSICA: Variáveis
que terão valor diferente de
zero no ponto de vértice.
Matriz NÃO BÁSICA:
Variáveis que terão valor
zero no ponto de vértice .
B =
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
N=
𝟏 𝟎
𝟎 𝟏
𝟑 𝟎
Matrizes do Ponto B Matrizes do Ponto D
Matrizes do Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏 𝒙𝟐
𝒙𝟑 𝒙𝟒𝒙𝟓 𝒙𝟏𝒙𝟐
𝒙𝟏 𝒙𝟓𝒙𝟑 𝒙𝟐 𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟏
𝟎 𝟎
𝟏 𝟎
𝒙𝟏 𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟎 𝟎
𝟎 𝟏 𝟑
N=
𝟎 𝟏
𝟐 𝟎
𝟐 𝟎
𝒙𝟏𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
Premissa-7: A matriz dos coeficientes das
restrições será dividida.
35
𝟏 𝟎 𝟏 𝟎 𝟎
𝟎 𝟐 𝟎 𝟏 𝟎
𝟑 𝟐 𝟎 𝟎 𝟏
𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟑 𝟐
Matrizes do Ponto A
B =
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟎
𝟎 𝟏
𝟏 𝟎
Matrizes do Ponto C
Matriz BÁSICA: Variáveis
que terão valor diferente de
zero no ponto de vértice.
Matriz NÃO BÁSICA:
Variáveis que terão valor
zero no ponto de vértice .
B =
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
N=
𝟏 𝟎
𝟎 𝟏
𝟑 𝟎
Matrizes do Ponto B Matrizes do Ponto D
Matrizes do Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏 𝒙𝟐
𝒙𝟑 𝒙𝟒𝒙𝟓 𝒙𝟏𝒙𝟐
𝒙𝟏 𝒙𝟓𝒙𝟑 𝒙𝟐 𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟏
𝟎 𝟎
𝟏 𝟎
𝒙𝟏 𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟎 𝟎
𝟎 𝟏 𝟑
N=
𝟎 𝟏
𝟐 𝟎
𝟐 𝟎
𝒙𝟏𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
Premissa-7: A matriz dos coeficientes das
restrições será dividida.
Note que a Matriz Básica do
ponto de início (neste
exemplo, o ponto "A") deve
ser uma Matriz Identidade.
Caso não seja estaremos
em um caso de "SIMPLEX
em Duas Fases" (a ser visto
na sequência do curso).
Sobre as retas das restrições as variáveis de folga tem
valor = zero, veja o exemplo abaixo:
Exemplo de restrição na forma de desigualdade: x1+3x2 ≤ 6
• todos pontos acima da reta x1+ 3x2 = 6 (A) resultam maiores do que 6;
• todos os pontos abaixo da reta x1 + 3x2 = 6 (A) resultam menores do que 6;
• todos os pontos sobre a reta x1 + 3x2 = 6 (A) resultam = 6;
Restrição na forma de igualdade
(com inclusão da variável de
folga):
x1+ 3x2 + x3 = 6 (B)
região˂ 6
região > 6
36
Premissa-7: A matriz dos coeficientes das
restrições será dividida.
Sobre a reta A = B, então:
x1+ 3x2 - 6 = x1+ 3x2 + x3 -6
de onde concluímos que x3, 
sobre a reta da restrição, tem 
valor = zero
37
Um Conceito Chave do
SIMPLEX
Pt B:
x4 = 0 
x1 = 0
x2 troca 
com x4
Observe o comportamento das variáveis a cada ponto subsequente
Pt C:
x4 = 0 
x5 = 0
x1 troca
com x5
Pt D:
x3 = 0 
x5 = 0
x3 troca
com x4
Pt E:
x3 = 0 
x2 = 0
x5 troca
com x2
Em cada novo
ponto de vértice
da Região de
Factibilidade
uma variável
básica troca de
posição com
uma variável
não básica
Pt A:
x1 = 0 
x2 = 0
38
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟑 𝟐
Matrizes do Ponto A (início)
B =
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟎
𝟎 𝟏
𝟏 𝟎
Matrizes do Ponto C
B =
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
N=
𝟏 𝟎
𝟎 𝟏
𝟑 𝟎
Matrizes do Ponto B
Matrizes do Ponto D
Matrizes do Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏 𝒙𝟐
𝒙𝟑 𝒙𝟒𝒙𝟓 𝒙𝟏𝒙𝟐
𝒙𝟏 𝒙𝟓𝒙𝟑 𝒙𝟐 𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟐 𝟎
𝟎 𝟐 𝟑
N=
𝟎 𝟏
𝟎 𝟎
𝟏 𝟎
𝒙𝟏 𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
B =
𝟎 𝟎 𝟏
𝟏 𝟎 𝟎
𝟎 𝟏 𝟑
N=
𝟎 𝟏
𝟐 𝟎
𝟐 𝟎
𝒙𝟏𝒙𝟓 𝒙𝟑𝒙𝟐𝒙𝟒
Um Conceito Chave do
SIMPLEX
x2 troca 
com x4
Observe o comportamento das variáveis a cada ponto subsequente
x1 troca
com x5
x3 troca
com x4
x5 troca
com x2
Em cada novo ponto de
vértice da Região de
Factibilidade uma variável
básica troca de posição com
uma variável não básica
39
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟑 𝟐
Matrizes do Ponto A (início)
Matrizes do Ponto C
Matrizes do Ponto B
Matrizes do Ponto D
Matrizes do Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏 𝒙𝟐
Um Conceito Chave do
SIMPLEX
Observe o comportamento das variáveis a cada ponto subsequente
x1 troca
com x5
x3 troca
com x4
x5 troca
com x2
x1 troca
com x3
Em cada novo ponto de
vértice da Região de
Factibilidade uma variável
básica troca de posição com
uma variável não básica
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟑 𝟎 𝟏
N=
𝟏 𝟎
𝟎 𝟐
𝟎 𝟐
𝒙𝟏 𝒙𝟒 𝒙𝟓 𝒙𝟑 𝒙𝟐
B =
𝟏 𝟎 𝟎
𝟎 𝟏 𝟐
𝟑 𝟎 𝟐
N=
𝟏 𝟎
𝟎 𝟎
𝟎 𝟏
𝒙𝟏 𝒙𝟒 𝒙𝟐 𝒙𝟑 𝒙𝟓
B =
𝟏 𝟏 𝟎
𝟎 𝟎 𝟐
𝟑 𝟎 𝟐
N=
𝟎 𝟎
𝟏 𝟎
𝟎 𝟏
𝒙𝟏 𝒙𝟑 𝒙𝟐 𝒙𝟒 𝒙𝟓
B =
𝟎 𝟏 𝟎
𝟎 𝟎 𝟐
𝟏 𝟎 𝟐
N=
𝟎 𝟏
𝟏 𝟎
𝟎 𝟑
𝒙𝟓 𝒙𝟑 𝒙𝟐 𝒙𝟒 𝒙𝟏
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
41
Premissa-8: A matriz básica de cada ponto
definirá as coordenadas do ponto
Como a matriz não básica 
representa as variáveis com 
valor zero no ponto, será a 
matriz básica que definirá o 
valor do sistema no ponto.
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
x
𝒙𝟑
𝒙𝟐
𝒙5
=
4
12
18
Matriz Básica do Ponto B
𝒙𝟑 𝒙𝟓𝒙𝟐
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
x1=0;
x2=?;
x3=?;
x4=0;
x5=?
Resultado da operação com matrizes
(1𝑥3+ 0𝑥2+ 0𝑥5)
(0𝑥3+ 2𝑥2+ 0𝑥5)
(0𝑥3+ 2𝑥2+ 1𝑥5)
=
4
12
18
Sistema resultante da operação
com matrizes
1𝑥3+ 0𝑥2+ 0𝑥5 = 4
0𝑥3+ 2𝑥2+ 0𝑥5 = 12
0𝑥3+ 2𝑥2+ 1𝑥5 = 18
x1=0;
x2=6;
x3=4;
x4=0;
x5=6
42
Premissa-8: A matriz básica de cada ponto
definirá as coordenadas do ponto
Como a matriz não básica 
representa as variáveis com 
valor zero no ponto, será a 
matriz básica que definirá o 
valor do sistema no ponto.
Matriz Básica do Ponto C
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
x1=?;
x2=?;
x3=?;
x4=0;
x5=0
Resultado da operação com matrizes
(1𝑥3+ 0𝑥2+ 1𝑥1)
(0𝑥3+ 2𝑥2+ 0𝑥1)
(0𝑥3+ 2𝑥2+ 3𝑥1)
=
4
12
18
Sistema resultante da operação
com matrizes
1𝑥3+ 0𝑥2+ 1𝑥1 = 4
0𝑥3+ 2𝑥2+ 0𝑥1 = 12
0𝑥3+ 2𝑥2+ 3𝑥1 = 18
x1=2;
x2=6;
x3=2;
x4=0;
x5=0
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
x
𝒙𝟑
𝒙𝟐
𝒙1
=
4
12
18
𝒙𝟏𝒙𝟑 𝒙𝟐
43
Premissa-8: A matriz básica de cada ponto
definirá as coordenadas do ponto
𝟏 𝟎 𝟎
𝟎 𝟏 𝟎
𝟎 𝟎 𝟏
x
𝒙𝟑
𝒙𝟒
𝒙5
=
4
12
18
Ponto A
𝟏 𝟎 𝟏
𝟎 𝟐 𝟎
𝟎 𝟐 𝟑
x
𝒙𝟑
𝒙𝟐
𝒙1
=
4
12
18
Ponto C
Como a matriz não básica representa as variáveis com valor zero no ponto, 
será a matriz básica que definirá o valor do sistema no ponto.
𝟏 𝟎 𝟎
𝟎 𝟐 𝟎
𝟎 𝟐 𝟏
x
𝒙𝟑
𝒙𝟐
𝒙5
=
4
12
18
Ponto B Ponto D
Ponto E
𝒙𝟑 𝒙𝟒 𝒙𝟓
𝒙𝟑 𝒙𝟓𝒙𝟐
𝒙𝟏𝒙𝟑 𝒙𝟐
𝟎 𝟎 𝟏
𝟏 𝟐 𝟎
𝟎 𝟐 𝟑
x
𝒙𝟒
𝒙𝟐
𝒙1
=
4
12
18
𝒙𝟏𝒙𝟐𝒙𝟒
𝟎 𝟎 𝟏
𝟏 𝟎 𝟎
𝟎 𝟏 𝟑
x
𝒙𝟒
𝒙𝟓
𝒙1
=
4
12
18
𝒙𝟏𝒙𝟓𝒙𝟒
solução do sistema:
x3=4; x4=12; x5=18
SOLUÇÕES BÁSICAS
(x1, x2 , x3, x4, x5)
Pt Viável
(0, 0, 4, 12, 18) A SIM
(0, 6, 4, 0, 6) B SIM
(2, 6, 2, 0, 0) C SIM
(4, 3, 0, 6, 0) D SIM
(4, 0, 0, 12, 6) E SIM
solução do sistema:
x2=6; x3=4; x5=6
solução do sistema: x1=2; x2=6; x3=2 solução do sistema:
x1=4; x2=3; x4=6
solução do sistema:
x1=4; x4=12; x5=6
44
SOLUÇÃO DO SIMPLEX
Unindo todas as premissas do método SIMPLEX que foram
apresentadas pode-se concluir que basta seguir a Estratégia
SIMPLEX a partir do ponto de origem e calcular as coordenadas
de cada ponto subsequente até encontrar o ponto cujas
coordenadas, quando aplicadas na função objetivo, resultam na
solução ótima.
O problema que se apresenta é que, após a especificaçãodo
problema (enunciado) somente se conhece o ponto de início (a
origem dos eixos). Não se conhece (ainda) nenhum dos pontos
subsequentes e nem uma forma de saber quando o ponto
subsequente será a solução ótima.
Estas respostas serão encontradas por meio da implementação
do método SIMPLEX que será o assunto da próxima aula.
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
Casos que necessitam conversão para aplicação
do SIMPLEX:
• Problema na forma de MAXIMIZAÇÃO;
• Algum valor do "Vetor Recursos" (“Lado Direito” ou
vetor “b”) negativo;
• Restrições tipo ≤ ≥ ═;
• Existência de variáveis livres de sinal (que podem
ser tanto positivas quanto negativas no modelo);
46
SIMPLEX
Conversão para a Forma Padrão
Transformar problemas de Maximização em Minimização
Sendo o problema MAX f(x) = c1x1 + c2x2
É equivalente a: 
MIN -f(x) = -c1x1 - c2x2
Multiplica-se a função objetivo por (-1). Devemos lembrar que o
resultado do SIMPLEX será um valor negativo. Se o problema
original era de Maximização, o resultado do SIMPLEX deverá
ser multiplicado por (-1) que é o significado de –f(x).
47
SIMPLEX
Conversão para a Forma Padrão
Restrições tipo ≤ são o caso já visto no início desta aula:
Sendo um problema: MIN f(x) = -c1x1 - c2x2
Acrescenta-se uma variável de folga em cada restrição do tipo ≤
para transformá-las em igualdades.
Restrições: 
(A) x1 + 0x2 ≤ 4 
(B) 0x1 + 2x2 ≤ 12 
(C) 3x1 + 2x2 ≤ 18 
Restrições com as Variáveis de folga : 
(A) x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4
(B) 0x1 + 2x2 + 0x3 + 1x4 + 0x5 = 12
(C) 3x1 + 2x2 + 0x3 + 0x4 + 1x5 = 18
48
SIMPLEX
Conversão para a Forma Padrão
Restrições tipo “valor de b negativo” (Exemplo):
Não é possível ter um valor de “b” negativo. Multiplica-se a segunda por (-1) 
Restrições: 
(A) 2x1 + 0x2 ≤ 4 
(B) 0x1 + 2x2 ≤ - 12 
Restrições com as Variáveis de folga : 
(A) 2x1 + 0x2 + 1x3 + 0x4 = 4
(B) 0x1 + 2x2 + 0x3 + 1x4 = - 12
Restrições com a Variável Artificial: 
(A) 2x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4
(B) 0x1 - 2x2 + 0x3 - 1x4 +1x5 = 12
Restrições com as Variáveis de folga : 
(A) 2x1 + 0x2 + 1x3 + 0x4 = 4
(B) 0x1 - 2x2 + 0x3 - 1x4 = 12
49
SIMPLEX
Conversão para a Forma Padrão
2
0
0
−2
𝟏
𝟎
0
−1
𝟎
𝟏
Com a variável artificial x5
a matriz dos coeficientes
passa a conter uma matriz identidade
Caso esta conversão não gere
uma Matriz Identidade para
aplicação do SIMPLEX,
acrescentamos uma (ou mais)
Variável “Artificial” em cada
restrição e caímos no caso do
Método SIMPLEX EM DUAS
FASES (a ser explicado na
sequência do curso).
Restrições tipo ≥ (Exemplo):
Para inverter o sentido de uma 
desigualdade multiplica-se os 
dois lados por (-1) 
Restrições: 
(A) x1 + 0x2 ≤ 4 
(B) - 0x1 - 2x2 ≤ -12 
Multiplicando a segunda por (-1) (“b” negativo)
(A) 1x1 + 0x2 + 1x3 + 0x4 = 4
(B) 0x1 + 2x2 + 0x3 - 1x4 = 12
Caso esta conversão não gere
uma Matriz Identidade para
aplicação do SIMPLEX,
acrescentamos uma (ou mais)
Variável “Artificial” em cada
restrição e caímos no caso do
Método SIMPLEX EM DUAS
FASES (a ser explicado na
sequência do curso).
Restrições com a Variável Artificial: 
(A) 1x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4
(B) 0x1 + 2x2 + 0x3 - 1x4 + 1x5 = 12
Restrições com as Variáveis de folga : 
(A) 1x1 + 0x2 + 1x3 + 0x4 = 4
(B) -0x1 - 2x2 - 0x3 + 1x4 = -12
Restrições: 
(A) x1 + 0x2 ≤ 4 
(B) 0x1 + 2x2 ≥ 12 
50
SIMPLEX
Conversão para a Forma Padrão
Outra forma de entender a conversão 
de uma restrição do tipo ≥ (slide anterior)
Inclusão de Variáveis de Excesso:
Caso esta conversão não gere
uma Matriz Identidade para
aplicação do SIMPLEX,
acrescentamos uma (ou mais)
Variável “Artificial” em cada
restrição e caímos no caso do
Método SIMPLEX EM DUAS
FASES (a ser explicado na
sequência do curso).
Restrições com a Variável Artificial: 
(A) 1x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4
(B) 0x1 + 2x2 + 0x3 - 1x4 + 1x5 = 12
Restrições com as Variáveis de folga : 
(A) 1x1 + 0x2 + 1x3 + 0x4 = 4
(B) 0x1 + 2x2 + 0x3 - 1x4 = 12
Restrições: 
(A) x1 + 0x2 ≤ 4 
(B) 0x1 + 2x2 ≥ 12 
51
SIMPLEX
Conversão para a Forma Padrão
Restrições tipo = (Exemplo):
Caso esta conversão não gere uma Matriz Identidade para aplicação do
SIMPLEX, acrescentamos uma (ou mais) Variável “Artificial” em cada
restrição e caímos no caso do Método SIMPLEX EM DUAS FASES (a ser
explicado na sequência do curso).
Restrições com a Variável Artificial: 
(A) 1x1 + 0x2 + 1x3 + 0x4 = 4
(B) 0x1 + 2x2 + 0x3 + 1x4 = 12
Restrições com as Variáveis de folga : 
(A) 1x1 + 0x2 + 1x3 = 4
(B) 0x1 + 2x2 + 0x3 = 12
Restrições: 
(A) x1 + 0x2 ≤ 4 
(B) 0x1 + 2x2 = 12 
52
SIMPLEX
Conversão para a Forma Padrão
Existência de variável irrestrita (livre ) em sinal:
Se uma das variáveis de decisão puder assumir valores positivos ou
negativos a restrição de não negatividade será violada. Exemplo:
MIN f(x) = -3x1-x2
Sujeito a: 
2x1 + x2 ≤ 4 
6x1 + x2 ≤ 8 
Com x1 irrestrito em 
sinal e x2 ≥ 0
Deve-se substituir x1 pela diferença de duas
variáveis positivas tipo y e z.
Teríamos então
MIN f (x) = -3(y-z)-x2 = -3y +3z - x2
Sujeito a: 
2 (y-z) + x2 ≤ 4 
6 (y-z) + x2 ≤ 8 
Com y ≥ 0; z ≥ 0 e x2 ≥ 0
Quando z= 0 :
x1 = y 
valor positivo
Quando y =0 :
x1 = -z 
valor negativo
A solução do problema é y=1; x2=2; x3=0; x4=0; z=0 sendo que em
decorrência da mudança realizada nas variáveis teremos para o problema
original: x1=1 ; x2=2 ; x3=0 ; x4=0 (sempre y ou z serão iguais a zero dando
solução para o problema original
53
SIMPLEX
Conversão para a Forma Padrão
• Definição do SIMPLEX.
• Premissas do método:
• A Forma Padrão;
• Solução Ótima estará sempre em um vértice;
• Haverá variáveis nulas nos vértices;
• Uso do formato matricial;
• A Estratégia SIMPLEX;
• Início na origem dos eixos;
• Divisão da matriz dos coeficientes;
• Conceito chave do método.
• Obtenção das coordenadas dos pontos a partir 
da matriz básica;
• Conversão para a Forma Padrão.
Pesquisa Operacional – PEOP
Teoria do Método SIMPLEX
55
http://www.fab.mil.br/dimensao22/