Unidade_04

Prévia do material em texto

Profª MsC. Andressa Azevedo1 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
SOLUÇÃO ANALÍTICA
� Conceitos Básicos de Álgebra Linear
� Problemas de Programação Linear
� Resolução Analítica pelo Método SIMPLEX
� Solução Inicial 
� Decisão de Otimalidade
� Variável que Entra na Base
� Variável que Sai da Base
� Nova Solução Viável 
Profª MsC. Andressa Azevedo2 Unidade 4 – Programação Linear – Solução Analítica
ÁLGEBRA LINEAR












=×
nmnn
m
m
mn
aaa
aaa
aaa
A
L
MOMM
L
L
21
22221
11211
Matriz
É um conjunto de elementos 
numéricos dispostos na forma 
retangular:
n linhas
m colunasNúmero de linhas
Número de colunas
Elementos da matriz
aij é o elemento que está na 
linha i e na coluna j
Vetor é uma matriz que possui 
uma única linha ( 1 x m ) ou 
coluna ( n x 1 ).














=
n
n
v
v
v
V
M
2
1
Profª MsC. Andressa Azevedo3 Unidade 4 – Programação Linear – Solução Analítica
ÁLGEBRA LINEAR










=
76
54
32
A 





=
753
642TA












=
100
010
001
L
MOMM
L
L
nI
AIA =×
{ } { }
nmji
T
mnij aAaA ×× =⇒=
Matriz Identidade
Apenas os elementos da diagonal principal da 
matriz são diferentes de zeros e iguais a 1.
Matriz Transposta
É obtida através da troca das linhas pelas 
colunas da matriz original.
( ) AA TT = jia
jia
ij
ij
≠∀=
=∀=
 0
 1
Profª MsC. Andressa Azevedo4 Unidade 4 – Programação Linear – Solução Analítica












−−−
=
3402
2011
2111
1201
A












−
−
−−−
=
−
1002
0110
1121
1223
1A
O Resultado da multiplicação de uma 
matriz pela sua inversa é a matriz identidade
Matriz Inversa
nnnnn IAAAA =×=×
−−
××
11












=× −
1000
0100
0010
0001
 
1AA
ÁLGEBRA LINEAR
Profª MsC. Andressa Azevedo5 Unidade 4 – Programação Linear – Solução Analítica














=














×












mpmm
p
p
npnn
p
p
mnmm
n
n
ababab
ababab
ababab
bbb
bbb
bbb
aaa
aaa
aaa
L
MOMM
L
L
L
MOMM
L
L
L
MOMM
L
L
21
22221
11211
21
22221
11211
21
22221
11211






=×+×+×=×+×+×
=×+×+×=×+×+×
=










×





2836241276867402
2235231161857301
38
27
10
642
531
Multiplicação de matrizes
mpnpmn ABBA =×
Exemplo
=
∑
=
×=
n
k
kjikij baab
1
ÁLGEBRA LINEAR
Profª MsC. Andressa Azevedo6 Unidade 4 – Programação Linear – Solução Analítica
ÁLGEBRA LINEAR






=





×





15
6
5,75
32
2
1
x
x






=





+
+
⇒





=





×





2
1
222121
212111
2
1
2
1
2221
1211
b
b
xaxa
xaxa
b
b
x
x
aa
aa






=





×





9
6
41
32
2
1
x
x
Sistemas de Equações Lineares
BXA =×
Única solução
a) Ter uma única solução
b) Ter múltiplas soluções
c) Não ter soluções






=





×





10
6
5,75
32
2
1
x
x
Múltiplas Soluções Sistema impossível
[ ]4,26,0=X [ ]θθ5,13 −=X
Não admite solução
Profª MsC. Andressa Azevedo7 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
PROPRIEDADES
Propriedade 1: A solução de um problema de 
programação linear está em um dos vértices da 
região de viabilidade;
Propriedade 2: A região de viabilidade possui 
um número finito de vértices;
Propriedade 3: Se um vértice possuir solução 
melhor do que todos os seus vizinhos este é o 
ponto ótimo.
Profª MsC. Andressa Azevedo8 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX
� O método simplex percorre os vértices 
da região viável até encontrar uma solução 
que não possua soluções vizinhas melhores 
que ela.
� O método simplex percorre os vértices da região viável até encontrar uma solução 
que não possua soluções vizinhas melhores que ela.
� No entanto a solução ótima pode não existir em dois casos: 
- quando não existe nenhuma solução viável para o problema;
- quando não há limite para o valor da função objetivo.
Sol. Inicial
Sol. Ótima
Profª MsC. Andressa Azevedo9 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX
Terminologia
� Variáveis Básicas: m variáveis 
com valor maior que zero
� Variáveis Não Básicas: (n-m) 
variáveis com valor igual a zero
� Solução Básica: Solução com m 
variáveis básicas e m-n não 
básicas
Sol. Básica Viável
( X1>0; X2>0; F1=0; F2=0 )
Sol. Não Básica ( X1>0; X2>0; F1>0; F2>0 )
Profª MsC. Andressa Azevedo10 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX
Quadro SIMPLEX
...............
bm1...0amn...am10(m)fm
b10...1a1n...a110(1)f1
00
...
0-cn...-c11(0)Z
fm...f1xn...x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
Variáveis Originais
Variáveis de Folga
Coeficientes da F.O.
Coeficientes das 
restrições
...............
bm1...0amn...am10(m)fm
b10...1a1n...a110(1)f1
00
...
0-cn...-c11(0)Z
fm...f1xn...x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
Variáveis Originais
Variáveis de Folga
Coeficientes da F.O.
Coeficientes das 
restrições
Profª MsC. Andressa Azevedo11 Unidade 4 – Programação Linear – Solução Analítica
PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX
Considerações sobre a Classificação das Variáveis
� A quantidade de variáveis não básicas coincide com a quantidade de variáveis 
do problema como foi fornecido, e a quantidade de variáveis básicas coincide 
com a quantidade de restrições;
� A cada nova solução, uma variável básica trocará de lugar com uma não 
básica; as quantidades se manterão fixas.
� As variáveis não básicas do quadro Simplex inicial são as próprias variáveis do 
problema;
� As variáveis básicas do quadro Simplex inicial são as variáveis de folga em um 
problema na forma padrão, e existe uma variável de folga para cada restrição.
Profª MsC. Andressa Azevedo12 Unidade 4 – Programação Linear – Solução Analítica
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
Procedimento de Solução Iterativa
Início
Determine
uma solução viável
Solução
Ótima?
Não
Fim
Sim
Determine uma solução 
viável melhor
InInííciocio
• Escrever o problema na forma padrão;
• Inclusão das variáveis de folga;
• Classificação das variáveis do problema;
Profª MsC. Andressa Azevedo13 Unidade 4 – Programação Linear – Solução Analítica
Algoritmo SIMPLEX
SOLUÇÃO ANALÍTICA
Introduzir as variáveis de folga; uma para cada 
desigualdade.
[1]:
Montar um quadro para os cálculos, colocando os 
coeficientes de todas as variáveis com os respectivos 
sinais e, na primeira linha, incluir os coeficientes da função 
objetivo transformada.
[2]:
Estabelecer uma solução básica inicial, usualmente 
atribuindo valor zero às variáveis originais e achando 
valores positivos para as variáveis de folga.
[3]:
Como próxima variável a entrar na base, escolher a 
variável não básica que oferece, na primeira linha, a maior 
contribuição para o aumento da função objetivo (ou seja, 
tem o maior valor negativo). Se todas as variáveis que 
estão fora da base tiverem coeficientes nulos ou positivos 
nesta linha, a solução atual é ótima. Se alguma dessas 
variáveis tiver coeficiente nulo, isto significa que ela pode 
ser introduzida na base sem aumentar o valor da função 
objetivo. Em outras palavras temos uma nova solução 
ótima, com o mesmo valor da função objetivo.
[4]:
ALGORITMO SIMPLEX
Para escolher a variável que deve deixar a 
base, deve-se realizar o seguinte 
procedimento:
1. Dividir os elementos da última coluna 
pelos correspondentes elementos 
positivos da coluna da variável que vai 
entrar na base. Caso não haja elemento 
algum positivo nesta coluna, o processo 
deve parar, já que a solução seria 
ilimitada.
2. O menor quociente indica a equação 
cuja respectiva variável básica deverá
ser anulada, tornando-se variável não 
básica.
[5]:Usando operações válidas com as linhas 
da matriz, transformar o quadro de cálculos 
de forma a encontrar a nova solução 
básica. Retornar ao passo quatro para 
iniciar outra iteração.
[6]:
ALGORITMO SIMPLEX
Profª MsC. Andressa Azevedo14 Unidade 4 – Programação Linear – Solução Analítica
Etapas do Algoritmo SIMPLEX
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
Variável que deverá
entrar na base: X2
1
Coluna pivô
2
6/1 = 6 (min)
18/2 = 9 
3
Variável que deverá
sair da base
4
Linha pivô
56
Número Pivô
60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010 60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
Variável que deverá
entrar na base: X2
1
Coluna pivô
2
6/1 = 6 (min)
18/2 = 9 
3
Variável que deverá
sair da base
4
Linha pivô
56
Número Pivô
Profª MsC. Andressa Azevedo15 Unidade 4 – Programação Linear – Solução Analítica
Construção do Novo Quadro
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
60(2)x2
0(3)fm
0(1)f1
300500-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1x2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
1
Variável entra na base
2
/ 1
3
- (-5)x(NLP)
Nova linha pivô
Nova linha
60(2)x2
0(3)fm
0(1)f1
300500-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1x2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
1
Variável entra na base
2
/ 1
3
- (-5)x(NLP)
60(2)x2
0(3)fm
0(1)f1
300500-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010 60(2)x2
0(3)fm
0(1)f1
300500-31(0)Z
f3f2f1X2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1x2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010 60(2)f2
18100230(3)fm
4001010(1)f1
0000-5-31(0)Z
f3f2f1x2x1Z
Lado 
direito
CoeficientesE.q.
No
Variável 
Básica
01010
1
Variável entra na base
2
/ 1
3
- (-5)x(NLP)
Nova linha pivô
Nova linha pivônúmero
opivlinha
opivlinhanova ˆˆ =
Nova linha = linha antiga – (coeficiente 
da coluna pivô) X (nova linha pivô)
Profª MsC. Andressa Azevedo16 Unidade 4 – Programação Linear – Solução Analítica
Problema-Exemplo
Uma marcenaria deseja estabelecer uma programação diária de produção. 
Atualmente a oficina fabrica apenas dois produtos: mesa e armário, ambos de 
um só modelo. Supondo que a mercenária apresente limitações em somente 
dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são 
mostradas na tabela a seguir:
O processo de produção é tal que, para fazer 1 mesa, a fábrica gasta 2 m2 de 
madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m2 de 
madeira e 1 H.h de mão-de-obra. Além disso, o fabricante sabe que cada mesa 
dá uma margem de contribuição para o lucro de R$ 4,00 e cada armário dá uma 
margem de R$ 1,00. O problema do fabricante é encontrar o programa de 
produção que maximiza a margem de contribuição total para o lucro.
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
8 H.hMão-de-obra
12 m2Madeira
DisponibilidadeRecurso
Profª MsC. Andressa Azevedo17 Unidade 4 – Programação Linear – Solução Analítica
Modelo Completo
MAXIMIZAR Z = 4 x1 + 1 x2
sujeito a: 2 x1 + 3 x2 ≤ 12
2 x1 + 1 x2 ≤ 8
com x1 e x2 ≥ 0
Lucro da mesa Lucro do armário
Utilização de madeira Disponibilidade
Utilização de mão-de-obra Disponibilidade
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
Profª MsC. Andressa Azevedo18 Unidade 4 – Programação Linear – Solução Analítica
Transformando Inequação em Equação
Quando afirma-se que , certamente pode-se dizer que existe algum 
valor c, não negativo, tal que: , em que c é chamado de folga 
da inequação.
ba ≤≤≤≤
bca ====++++
R1 - 2 x1 + 3 x2 + x3 = 12
R2 - 2 x1 + 1 x2 + x4 = 8
com x1 , x2 , x3 e x4 ≥ 0
Utilização de madeira Folga
Utilização de mão-de-obra
Disponibilidade
Folga Disponibilidade
REGRA: 
Uma variável 
de folga para 
cada 
inequação
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEXPasso 1
Profª MsC. Andressa Azevedo19 Unidade 4 – Programação Linear – Solução Analítica
0
0
0
0
812
1232
s.a.
14 Z
4
3
2
1
421
321
21MAX
≥
≥
≥
≥
=++
=++
+=
X
X
X
X
XXX
XXX
XX
Modelo Original Modelo Adaptado Sistema Linear
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
0
0
812
1232
s.a.
14 Z
2
1
21
21
21MAX
≥
≥
≤+
≤+
+=
X
X
XX
XX
XX
812]2[
1232[1]
014Z [0]
421
321
21
=++
=++
=+−
XXX
XXX
XX
� A determinação da solução inicial é feita a partir do quadro inicial.
� Em um problema da forma padrão considere as variáveis não básicas assumindo 
o valor zero e obtenha os outros valores por substituição de valores.
Profª MsC. Andressa Azevedo20 Unidade 4 – Programação Linear – Solução Analítica
Quadro 1 (Inicial)
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
x4
x3
x2x1Z
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica
-4
2
2
-1
3
1
0
1
0
0
0
1
0
12
8
1
0
0
[0]
[1]
[2]
Passo 2
Profª MsC. Andressa Azevedo21 Unidade 4 – Programação Linear – Solução Analítica
Solução Inicial
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEXPasso 3
Solução Viável Inicial:
Z= 0
X1 = 0
X2 = 0
X3 = 12
X4 = 8
X3 = 12 - 2X1 - 3X2
Quando, X1 = X2 = 0
X3 = 12
X4 = 8 - 2X1 - 1X2
Quando, X1 = X2 = 0
X4 = 8
Decisão:
� Enquanto variáveis não básicas da F.O. tiverem coeficientes positivo, a solução atual 
pode ser melhorada. 
� Neste caso, a segunda solução também deverá ter duas variáveis nulas e duas 
variáveis positivas. O desafio é buscar resposta para as seguintes questões:
1 - Das duas variáveis não básicas (nulas) na primeira solução, qual deverá se tornar positiva?
2 - Das duas variáveis básicas (positivas) na primeira solução, qual deverá ser anulada?
Profª MsC. Andressa Azevedo22 Unidade 4 – Programação Linear – Solução Analítica
Escolha da variável que entra na base e da que sai da base
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
Passo 4
Passo 5
a variável que entra na base é X1.
a variável que sai da base é X4.
� Assim, X2 = X4 = 0.
� Neste caso, X1 = 4
Primeiro Critério:
Iniciar a produção pelo produto 
que mais contribui para o lucro. 
Neste caso, a variável que se 
torna positiva é a que tem maior 
coeficiente em Z.
Segundo Critério:
Escolhido o produto, sua produção 
deve ser estabelecida no maior 
valor possível. Ou seja, dá-se à
variável o maior valor positivo 
possível.
Profª MsC. Andressa Azevedo23 Unidade 4 – Programação Linear – Solução Analítica
Construção do Novo Quadro
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEXPasso 6
x1
x3
x2x1Z
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica
-4
2
1
-1
3
1/2
0
1
0
0
0
1/2
0
12
4
1
0
0
[0]
[1]
[2]
1ª Operação: 
dividir a terceira 
linha por 2
2ª Operação: 
multiplicar a terceira 
linha por (-2) e somar 
com a segunda linha 
do mesmo quadro, 
colocando o resultado 
na segunda linha
Quadro 1 A
x1
x3
x2x1Z
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica
-4
0
1
-1
2
1/2
0
1
0
0
-1
1/2
0
4
4
1
0
0
[0]
[1]
[2]
Quadro 1 B
Profª MsC. Andressa Azevedo24 Unidade 4 – Programação Linear – Solução Analítica
Construção do Novo Quadro
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEXPasso 6
3ª Operação: 
multiplicar a terceira 
linha do Quadro 1B 
por (4) e somar com 
a primeira linha, 
substituindo esta pelo 
resultado obtido.
x1
x3
x2x1Z
E.q.
Z
Z
Lado 
direito
CoeficientesE.q.
x3 x4
Variável
Básica
0
0
1
1
2
1/2
0
1
0
2
-1
1/2
16
4
4
1
0
0
[0]
[1]
[2]
Quadro 2
3ª Linha x (4): 4 2 0 2 16
1ª Linha : -4 -1 0 0 0
-------------------------------------------------------------------Soma Z= 0 1 0 2 16
Profª MsC. Andressa Azevedo25 Unidade 4 – Programação Linear – Solução Analítica
Solução Final
SOLUÇÃO ANALÍTICA
MÉTODO SIMPLEX
Como a primeira linha (Função Z transformada), mostra as contribuições líquidas para o 
Lucro Z, em caso de as variáveis X2 e X4 terem seus valores aumentados de 0 para 1, a 
novo solução será pior que a anterior. 
Neste caso, pode-se concluir que a solução encontrada é ótima.
Z= 16
X1 = 4
X2 = 0
X3 = 4
X4 = 0
Profª MsC. Andressa Azevedo26 Unidade 4 – Programação Linear – Solução Analítica
Resolução Tabular: O Método Simplex In: PASSOS, E. J. P. F. Programação 
Linear como Instrumento da Pesquisa Operacional. São Paulo: Editora 
Atlas, 2008 - capítulo 4.
Problemas de Programação Linear – Resolução Analítica In: 
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisão. 
Rio de Janeiro: Editora Elsevier, 2007 - capítulo 2.2 - 2.4.
REFERÊNCIAS BIBLIOGRÁFICAS
Leitura obrigatória
Leitura complementar