Apostila UNIJUÍ - Pesquisa_Operacional
164 pág.

Apostila UNIJUÍ - Pesquisa_Operacional


DisciplinaPesquisa de Mercado5.028 materiais75.693 seguidores
Pré-visualização31 páginas
encontrar a linha pivô.
6º passo: encontrar a nova linha pivô.
Linha pivô 0 4 6 0 1 50
Dividindo por 6: 0 0,67 1 0 0,17 8,33 Nova linha pivô
7º passo: encontrar a nova linha do custo (primeira linha).
Nova linha pivô 0 0,67 1 0 0,17 8,33
Multiplicando por 15 0 10,05 15 0 2,55 124,95
+ Linha do Custo -1 -10 -15 0 0 0
= Nova Linha do Custo -1 0,05 0 0 2,55 124,95
8º passo: encontrar a nova segunda linha.
Nova linha pivô 0 0,67 1 0 0,17 8,33
Multiplicando por -3 0 -2,01 -3 0 -0,51 -25
+ Segunda Linha 0 5 3 1 0 60
= Nova Linha Dois 0 2,99 0 1 -0.51 35
C x1 x2 xf1 xf2 b 
-1 -10 -15 0 0 0 
0 5 3 1 0 60 
0 4 6 0 1 50 
 
C x1 x2 xf1 xf2 b 
-1 -10 -15 0 0 0 
0 5 3 1 0 60 
0 4 6 0 1 50 
 
EaD
55
PESQUISA OPERACIONAL
Reescrevendo a tabela:
Resultado:
C: R$ 124,95
x
1
: 0
x
2
: 8,33
xf
1
: 35
xf
2
: 0
Dessa forma, a empresa deve produzir 8,33 unidades de x
2 
, nenhuma unidade de x
1
tendo, dessa forma, um custo de produção de R$ 124,95. Diante dessa situação, foi utiliza-
da toda a disponibilidade do recurso produtivo 2 (xf
2
), sobrando 35 unidades do recurso
produtivo 1 (xf
1
).
EXERCÍCIOS (LISTA 3)
1. Variáveis de decisão:
x
1
: Quantidade de P1 a produzir
x
2
: Quantidade de P2 a produzir
Função Objetivo:
Minimizar C: 20.x
1
 + 25.x
2
Restrições:
R1 3.x
1 
+ 3.x
2 
\u2264 4
R2 5. x
1 + 
4. X
2
 \u2264 4
R3 8. x
1 + 
7. X
2
 \u2264 14
2. Variáveis de decisão:
x
1
: Número de unidades de P1 a produzir
x
2
: Número de unidades de P2 a produzir
x
3
: Número de unidades de P3 a produzir
C x1 x2 xf1 xf2 b 
-1 0,05 0 0 2,55 124,95 
0 2,99 0 1 -0.51 35 
0 0,67 1 0 0,17 8,33 
 
EaD Martin Ledermann \u2013 N iv ia Maria Kinalski
56
Função Objetivo:
Minimizar C: 5.x
1
 + 6.x
2
 + 7. x
3
Restrições:
R1 2. x
1 
+ 2.x
2 
+
 
2.x
3 
\u2264 80
R2 4.x
1 
+ 2.x
2 
\u2264 100
R3 x
1 
\u2264 60
Seção 2.5
O Problema da Solução Básica Inicial
Até esta etapa do livro-texto trabalhamos os problemas de Programação Linear com
restrições do tipo = com os termos da direita positivos. O acréscimo das variáveis de folga
fornece neste caso uma solução básica inicial.
De acordo com Silva et al. (2009), o problema aparece quando:
\u2022 A restrição é do tipo \u201c³\u201d: a variável de folga é subtraída e seu valor é negativo, quando se
anulam as variáveis de decisão.
\u2022 A restrição é do tipo \u201c=\u201d: não recebe a variável de folga.
Neste caso, segundo Silva et al. (2009), a cada uma das restrições do tipo = e =
acrescenta-se variáveis auxiliares a
i
 com a formação de um novo modelo. A solução básica
inicial do novo modelo é formada pelas variáveis de folga das restrições do tipo = e pelas
variáveis auxiliares a
i
. Para explicar a resolução de problemas com esse tipo de situação,
utilizaremos o exemplo proposto por Silva et al. (2009).
Exemplo: o problema da solução básica inicial
Variáveis de decisão
x
1
: Quantidade de P1 a produzir
x
2
: Quantidade de P2 a produzir
x
3
: Quantidade de P3 a produzir
EaD
57
PESQUISA OPERACIONAL
Função Objetivo
Max L: x
1
+ x
2 
+ x
3
Restrições
Recurso Produtivo 1 (R1): 2. x
1
 + x
2 
\u2013 x
3
 \u2264 10
Recurso Produtivo 2 (R2): x
1
 + x
2 
+ 2.x
3
 \u2265 20
Recurso Produtivo 3 (R3): 2. x
1
 + x
2
 + 3.x
3
= 60
A pergunta que se faz é a seguinte: Como resolver problemas com restrições do tipo
\u201c\u2265\u201d e \u201c=\u201d? A seguir apresentaremos duas formas de resolver esse tipo de problema: o Método
do M Grande e o Método da Função Objetivo Auxiliar.
a) O Método do M Grande
Primeiramente reescreveremos as restrições, acrescentando na restrição com sinal \u201c\u2264\u201d
uma variável de folga; na restrição com sinal \u201c\u2265\u201d acrescentaremos uma variável de excesso
(-xf), seguida de uma variável auxiliar (a). Já na restrição com sinal de \u201c=\u201d, acrescentare-
mos uma variável auxiliar (a). As equações das restrições resultam na seguinte forma:
R1: 2. x
1
 + x
2 
\u2013 x
3
 + xf
1
 = 10
R2: x
1
 + x
2 
+ 2.x
3
 \u2013 xf
2
 + a
2
= 20
R3: 2. x
1
 + x
2
 + 3.x
3
 + a
3
= 60
Em seguida, escrevemos a função objetivo acrescentando as variáveis auxiliares com
coeficientes \u2013M
2
 e -M
3
, sendo M
2
 e M
3 
números grandes.
Max L: x
1
+ x
2 
+ x
3
 \u2013 M
2
a
2
 \u2013 M
3
a
3
À medida que o lucro é maximizado, as variáveis a
2 
e a
3 
deixam a base, devido ao gran-
de valor de M
2
 e M
3
. O quadro inicial fica da seguinte forma:
Realizada esta etapa, os próximos passos são os mesmos de quando resolvemos os
exercícios com sinal de \u201c\u2264\u201d.
L x1 x2 x3 xf1 xf2 a2 a3 b 
1 -1 -1 -1 0 0 M2 M3 0 
0 2 1 -1 1 0 0 0 10 
0 1 1 2 0 -1 1 0 20 
0 2 1 3 0 0 0 1 60 
 
EaD Martin Ledermann \u2013 N iv ia Maria Kinalski
58
1º passo: isolar a variável de decisão que apresenta o maior lucro unitário. Como nesse
caso todas as variáveis de decisão apresentam o mesmo lucro unitário, escolheremos uma
delas, de forma aleatória. Optaremos por x
3
.
2º passo: determinar a linha pivô.
3º passo: determinar a nova linha pivô.
Linha pivô 0 1 1 2 0 -1 1 0 20
Dividindo por 2 =
nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10
4º passo: determinar a nova linha do lucro.
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10
Multiplicando por 1 0 0,5 0,5 1 0 -0,5 0,5 0 10
+ Linha do lucro 1 -1 -1 -1 0 0 M
2
M
3
0
= Nova linha do lucro 1 -0,5 -0,5 0 0 -0,5 M
2
M
3
10
5º passo: determinar a nova segunda linha.
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10
Multiplicando por 1 0 0,5 0,5 1 0 -0,5 0,5 0 10
+ Segunda linha 0 2 1 -1 1 0 0 0 10
= Nova linha dois 0 2,5 1,5 0 1 -0,5 0,5 0 20
6º passo: determinar a nova quarta linha.
Nova linha pivô 0 0,5 0,5 1 0 -0,5 0,5 0 10
Multiplicando por -3 0 -1,5 -1,5 -3 0 1,5 -1,5 0 -30
+ Quarta Linha 0 2 1 3 0 0 0 1 60
= Nova linha quatro 0 0,5 -0,5 0 0 1,5 -1,5 1 30
L x1 x2 x3 xf1 xf2 a2 a3 b 
1 -1 -1 -1 0 0 M2 M3 0 
0 2 1 -1 1 0 0 0 10 
0 1 1 2 0 -1 1 0 20 
0 2 1 3 0 0 0 1 60 
 
EaD
59
PESQUISA OPERACIONAL
 
Linha pivô 
 
0 
 
0,5 
 
-0,5 
 
0 
 
0 
 
1,5 
 
-1,5 
 
1 
 
30 
Dividindo por 1,5 = 
Nova linha pivô 0 0,33 
 
-0,33 0 0 1 -1 0,67 20 
 
Resultado:
L: R$ 10,00
x
1
: 0
x
2
: 0
x
3
: 10
xf
1
: 20
xf
2
: 0
a
2
: 0
a
3
: 30
Como podemos observar, esta solução não é a melhor possível, pois os coeficientes das
variáveis de decisão resultaram em valores negativos. Então, vamos à segunda solução.
Observação: com a intenção de eliminar as variáveis auxiliares, isolaremos agora a
variável de folga que apresentou coeficiente negativo, no caso xf
2
.
1º passo: isolar xf2.
2º passo: determinar a linha pivô.
3º passo: determinar a nova linha pivô.
L x1 x2 x3 xf1 xf2 a2 a3 b 
 1 -0,5 -0,5 0 0 -0,5 M2 M3 10 
0 2,5 1,5 0 1 -0,5 0,5 0 20 
0 0,5 0,5 1 0 -0,5 0,5 0 10 
0 0,5 -0,5 0 0 1,5 -1,5 1 30 
 
L x1 x2 x3 xf1 xf2 a2 a3 b 
1 -0,5 -0,5 0 0 -0,5 M2 M3 10 
0 2,5 1,5 0 1 -0,5 0,5 0 20 
0 0,5 0,5 1 0 -0,5 0,5 0 10 
0 0,5 -0,5 0 0 1,5 -1,5 1 30 
 
EaD Martin Ledermann \u2013 N iv ia Maria Kinalski
60
4º passo: determinar nova linha do lucro.
5º passo: determinar nova segunda linha.
6º passo: determinar nova terceira linha.
Tabela com o resultado:
 Resultado:
L: R$ 20,00 xf
1
: 30
x
1
: 0 xf
2
: 20
x
2
: 0 a
2
: 0
x
3
: 20 a
3
: 0
Linha pivô 0 0,33 -0,33 0 0 1 -1 0,67 20 
Multiplicando por 0,5 0 0,17 -0,17 0 0 0,5 -0,5 0,33 10 
+ Linha do lucro 1 -0,5 -0,5 0 0 -0,5 M2 M3 10 
= Nova linha do lucro 1 -0,33 -0,667 0 0 0 M2 M3 20 
 
Linha pivô 0 0,33 -0,33 0 0 1 -1 0,67 20 
Multiplicando por 0,5 0 0,17 -0,17 0 0 0,5 -0,5 0,33 10 
+ Segunda linha 0 2,5 1,5 0 1 -0,5 0,5 0 20 
= Nova linha dois 0 2,67 1,33 0 1 0 0 0,33 30 
 
Linha pivô 0 0,33 -0,33 0 0 1 -1 0,67 20 
Multiplicando por 0,5 0 0,17 -0,17 0 0 0,5 -0,5 0,33 10 
+ Terceira linha 0 0,5 0,5 1 0 -0,5 0,5 0 10 
= Nova linha três 0 0,67 0,33 1 0 0 0 0,33 20 
 
L x1 x2 x3 xf1 xf2 a2 a3 b 
1 -0,33 -0,667 0 0 0 M2 
 
M3 20 
0 2,67 1,33 0 1 0 0 
0,33 
30 
0 0,67 0,33 1 0 0 0 
0,33 
20 
0 0,33 
 
-0,33 0 0 1 -1 0,67 20 
 
EaD
61
PESQUISA OPERACIONAL
A solução básica é