CENTRO DE CIÊNCIAS EXATAS – CCE
DEPARTAMENTO DE ESTATÍSTICA
Curso de Especialização “Lato Sensu” em Engenharia de Produção
com enfoque em Pesquisa Operacional
PESQUISA OPERACIONAL NA
TOMADA DE DECISÃO
Professores: Dr. Waldir Medri
[email protected]
Ms. Ana Satie Yotsumoto
[email protected]
Londrina/Pr
Setembro 2009
ii
ÍNDICE
PESQUISA OPERACIONAL NA TOMADA DE DECISÃO........................................................................... 1
1 PESQUISA OPERACIONAL ........................................................................................................................... 1
1.1 INTRODUÇÃO .................................................................................................................................................. 1
2 PROGRAMAÇÃO LINEAR............................................................................................................................. 2
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR ...................................................................................... 2
2.2 FORMULAÇÃO DO PROBLEMA......................................................................................................................... 4
2.3 MONTAGEM DO MODELO ............................................................................................................................... 4
2.4 MODELO COMPLETO ...................................................................................................................................... 5
2.4.1 RESOLUÇÃO GRÁFICA DO PROBLEMA DE MAXIMIZAÇÃO DE PROGRAMAÇÃO LINEAR....... 5
2.4.2RESOLUÇÃO GRÁFICA DO PROBLEMA DE MINIMIZAÇÃO DE PROGRAMAÇÃO LINEAR......... 8
2.4.3 APLICAÇÕES EM SISTEMAS PRODUTIVOS ...................................................................................... 9
2.5 MÉTODO SIMPLEX ........................................................................................................................................ 11
2.5.1 INTRODUÇÃO DAS VARIÁVEIS DE FOLGA .................................................................................... 11
2.5.2 MÉTODO SIMPLEX EM DUAS FASES .............................................................................................. 14
2.5.2.1 OBTENÇÃO DA SOLUÇÃO BÁSICA INICIAL ................................................................................................................ 14
2.5.2.2 MÉTODO DAS DUAS FASES ............................................................................................................................................ 15
2.5.3 APLICAÇÕES EM SISTEMAS PRODUTIVOS .................................................................................... 19
2. 6 ANÁLISE DE SENSIBILIDADE ........................................................................................................................ 21
2.6.1 MUDANÇAS PARAMÉTRICAS EM UM COEFICIENTE CJ DA FUNÇÃO OBJETIVO.................... 22
2.6.1.1 MUDANÇA NO COEFICIENTE DE UMA VARIÁVEL NÃO-BÁSICA .......................................................................... 22
2.6.1.2 MUDANÇA NO COEFICIENTE DE UMA VARIÁVEL BÁSICA .................................................................................... 24
2.6.1.2.1 Intervalo de Estabilidade para o Coeficiente de x1 (c1)..................................................................................................... 24
2.6.1.2.2 Intervalo de Estabilidade para o Coeficiente de x2 (c2)..................................................................................................... 25
2.6.2 ENTRADA DE UMA NOVA VARIÁVEL .............................................................................................. 27
2.6.3 MUDANÇAS NOS VALORES DOS RECURSOS BJ............................................................................. 27
2.6.4 APLICAÇÕES EM SISTEMAS PRODUTIVOS .................................................................................... 31
2.7 DUALIDADE EM PROGRAMAÇÃO LINEAR ..................................................................................................... 32
3 PROGRAMAÇÃO INTEIRA ......................................................................................................................... 39
3.1 INTRODUÇÃO ................................................................................................................................................ 39
3.2 MÉTODOS DE RESOLUÇÃO ............................................................................................................................ 39
3.3 MÉTODO DE PARTIÇÃO E AVALIAÇÃO SUCESSIVAS ..................................................................................... 39
3.4 APLICAÇÃO .................................................................................................................................................. 40
3.5 APLICAÇÕES EM SISTEMAS PRODUTIVOS ..................................................................................................... 45
BIBLIOGRAFIA............................................................................................................................................... 46
1
PESQUISA OPERACIONAL NA TOMADA DE DECISÃO
1 PESQUISA OPERACIONAL
1.1 INTRODUÇÃO
A Pesquisa Operacional apareceu pela primeira vez durante a 2a.
Guerra Mundial, quando equipes de pesquisadores procuraram desenvolver
métodos para resolver problemas de operações militares. Neste período observouse uma atividade global de planejamento a nível mundial. Este planejamento
envolvia instrumentos e sistemas econômicos, políticos e sociais diferentes entre
si, mas com objetivos e funções perfeitamente determinados pela guerra, ligada
de alguma forma, ao próprio desenvolvimento da pesquisa operacional.
Desde seu nascimento, esse novo campo de análise de decisão
caracterizou-se pelo uso de técnicas e métodos científicos qualitativos por equipes
interdisciplinares, com a finalidade de determinar a melhor utilização de recursos
limitados e para a programação otimizada das observações de uma empresa.
Essa característica multidisciplinar das aplicações de pesquisa operacional deu
origem a um novo enfoque.
A pesquisa operacional é uma metodologia administrativa que agrega,
em sua teoria, quatro ciências fundamentais para o processo de preparação,
análise e tomada de decisão: economia, matemática, estatística e informática.
Uma característica importante que a pesquisa operacional possui e que facilita
muito processo de análise de decisão é a utilização de modelos, uma vez que, a
P.O. consiste, basicamente, em construir um modelo de um sistema real existente
como meio de analisar e compreender o comportamento dessa situação, com o
objetivo de levá-lo a apresentar o desempenho que se deseja.
Este sistema pode existir atualmente ou pode ainda estar em
concepção. No primeiro caso, o objetivo do estudo é analisar o desempenho do
sistema para escolher uma ação no sentido de aprimorá-lo. No segundo, o
objetivo é identificar a melhor estrutura do sistema futuro.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
2
A pesquisa operacional tem sido vista pelos gerentes e praticantes sob
dois enfoques diferentes quanto à abordagem, mas coerentes e complementares
na aplicação prática no campo da gestão empresarial:
•
Enfoque clássico – busca da solução ótima.
•
Enfoque atual – uso do modelo para identificação do problema correto.
O enfoque clássico ou tradicional é derivado do conceito quantitativo da
pesquisa operacional. Aqui a P.O. é definida como a arte de aplicar técnicas de
modelagem a problemas de decisão e resolver os modelos obtidos através da
utilização de métodos matemáticos e estatísticos, visando à obtenção de uma
solução ótima, sob uma abordagem sistêmica.
A outra visão decorre de um conceito qualitativo da pesquisa
operacional. O esforço despendido para a modelagem de um problema leva a uma
compreensão mais profunda do próprio problema, identificando melhor seus
elementos internos, suas interações com o ambiente externo, as informações
necessárias e os resultados possíveis de obter.
Nessa abordagem qualitativa, o enfoque central é deslocado do método
de solução para a formulação e para a modelagem, ou seja, para o diagnóstico de
problema.
2 PROGRAMAÇÃO LINEAR
A Programação Linear é hoje o instrumento de Pesquisa Operacional
mais comumente empregado na resolução prática de problemas decisórios
objetivos e de certa complexidade. Em linhas gerais, a programação linear
consiste na descrição de um sistema organizado com auxílio de um modelo
matemático, e através da resolução deste modelo, encontrar a melhor solução.
2.1 MODELO MATEMÁTICO DE PROGRAMAÇÃO LINEAR
Usa-se programação matemática para a determinação da solução ótima
de problemas que exigem que se decida sobre a utilização eficaz de uma
quantidade limitada de recursos, para a obtenção de um determinado objetivo.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
3
A programação linear é uma técnica de programação matemática e,
consiste na otimização (maximização ou minimização) de uma função linear,
denominada de Função Objetivo, respeitando-se um sistema linear de igualdades
ou desigualdades que recebem o nome de Restrições do modelo.
Matematicamente, a função objetiva a ser maximizada pode ser escrita
da seguinte maneira:
Max Z = c1 x1 + c2 x2 + ... + cn xn
s.a.:
a11 x1 + a12 x2 + ... + a1n xn ≤ b1
a21 x1 + a22 x2 + ... + a2n xn ≤ b2
..................................................
am1 x1 + am2 x2 + ... + amn xn ≤ bm
x1, x2, …, xn ≥ 0
onde: xj = número de unidades do produto j produzidas num certo período de
tempo (variáveis de decisão);
Z = função a ser otimizada (maximizada ou minimizada);
cj = aumento no lucro Z pelo acréscimo de uma unidade xj (coeficiente
de lucro);
aij = quantidade do recurso i consumida na produção de uma unidade
de atividade j (coeficiente de restrições);
bj = quantidade de recurso i disponível no período para as n atividades
(limitação de capacidade da restrição).
Pode-se apresentar esse modelo de forma mais compacta:
n
Max Z = ∑ c j x j
j =1
n
s.a. :
∑a
j =1
ij
xj ≥ 0
x j ≤ bi
para i = 1, 2, ..., m
para j = 1, 2, ..., n
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
4
2.2 FORMULAÇÃO DO PROBLEMA
Definindo o problema através de um exemplo de programação linear.
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. Para efeito de simplificação, considere que a mercearia tem limitações
em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias
são mostradas no quadro 1.
Quadro 1
Recurso
Disponibilidade
Madeira
12 m2
Mão-de-obra
8 H.h.
O processo de produção é tal que, para fazer uma mesa a fábrica gasta
2
2 m 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, de
R$ 1,00. O problema do fabricante é encontrar o programa de produção que
maximize a margem de contribuição para o lucro.
2.3 MONTAGEM DO MODELO
Como variáveis de decisão, considera-se:
•
quantidade a produzir de mesa:
x1
•
quantidade a produzir de armário:
x2
Com essa definição de variáveis, pode-se escrever as relações
matemáticas que formam o modelo. Assim, para função objetivo tem-se:
Margem de Contribuição Total: Z = 4x1 + x2
Para as restrições, a relação lógica existente é:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
5
Utilização de recursos ≤ Disponibilidade de recurso
Para a madeira:
2x1 + 3x2
≤
Utilização de
madeira para os
dois produtos
Para a mão-de-obra:
2x1 + 1x2
Utilização de
mão-de-obra para
os dois produtos
12
Disponibilidade
de madeira
≤
8
Disponibilidade
de mão-de-obra
2.4 MODELO COMPLETO
Maximizar Z = 4x1 + x2
s.a.:
2x1 + 3x2 ≤ 12
2x1 + 1x2 ≤ 8
x1, x2 ≥ 0
Observa-se que o conjunto de restrições forma um sistema de
desigualdades lineares. Assim existem infinitas combinações de valores de x1 e x2
que satisfazem as restrições.
2.4.1 RESOLUÇÃO GRÁFICA DO PROBLEMA DE MAXIMIZAÇÃO DE PROGRAMAÇÃO
LINEAR
Mesmo na era do computador, o método de solução gráfica de
programação linear é ainda útil para pequenos problemas envolvendo duas
variáveis de decisão, bem como para mostrar como é que se pode resolver,
sistematicamente, problemas de programação linear.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
6
gradiente de Z, representado por ∇ (nabla)
Z = 4x1 + x2 ∇Z = (
∂Z ∂Z
,
)
∂x1 ∂x2
∇Z = (4, 1) a função objetiva sempre é
perpendicular ao ∇ e sobe no sentido que está apontado o ∇.
2x1 + 3x2 ≤ 12 A: 2x1 + 3x2 = 12
X2
A
12 − 3 x 2
x1 =
2
8
2x1 + 1x2 ≤ 8
4
X1
6
0
X2
0
4
B: x2 = 8 - 2x1
B
X1
0
4
1
0
4
6
X2
8
0
X1
Solução ótima (x1 = 4; x2 = 0 e Z = 16)
A área hachurada representa a região onde estão todas as soluções
possíveis para o problema. Cada ponto dessa região, definido por um par de
coordenadas (x1, x2) é uma solução viável, pois satisfaz o conjunto de restrições.
Portanto, o problema admite infinitas soluções, porém o que se quer é encontrar o
ponto que dá a solução ótima, ou seja, que maximize o lucro total.
Importante: o ponto (solução ótima) sempre se encontra em um dos vértices da
região exeqüível.
Deslocando-se
uma
reta
que
representa
a
função
objetiva,
paralelamente a si mesma para cima, implica em fazer crescer o valor de Z. O
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
7
nosso problema consiste, portanto, em procurar o último ponto pertencente ao
conjunto viável, tal que por ele passe a reta que maximize Z.
Outra forma de garantir que a função objetiva cresce sempre num
sentido determinado é nos apoiar num teorema de cálculo diferencial e integral
que diz que se uma função f: !Rn → !R é diferenciável, então o vetor gradiente,
representado por (∇), fica:
∇f (x) = (
∂f
∂f
∂f
,
, L,
)
∂ x1 ∂ x2
∂ xn
em cada x ∈ !Rn aponta no sentido do máximo crescimento da função. Quando for
linear, ∇f(x) (gradiente) é constante e aponta sempre no mesmo sentido.
No problema em questão ∇Z = (4, 1) que é o vetor que dá o sentido de
máximo crescimento de Z. Nota-se também que ele é perpendicular á reta da
função objetiva.
Em se tratando de Problema de Minimização, a função objetiva é
expressa como,
Minimizar z = b1 y1 + b2 y2 + ... + bn yn
e as restrições, geralmente, são apresentadas da seguinte maneira:
a11 y1 + a21 y2 + ... + an1 yn ≥ c1
a12 y1 + a22 y2 + ... + an2 xn ≥ c2
..................................................
a1m y1 + a2m y2 + ... + amn yn ≥ bm
y1, y2, …, ym ≥ 0
Pode-se apresentar esse modelo de forma mais compacta:
m
Min z = ∑ci yi
i =1
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
8
m
s.a. :
∑a
i =1
ij
yi ≥ cj
para j = 1, 2, ..., n
yi j ≥ 0
Exemplo:
para i = 1, 2, ..., m
Min z = 2x1 + 3x2
s.a.:
x1 + x2 ≥ 5
5x1 + x2 ≥ 10
x1, x2 ≥ 0
Observa-se que o conjunto de restrições forma um sistema de
desigualdades lineares. Assim existem infinitas combinações de valores de x1 e x2
que satisfazem as restrições.
2.4.2RESOLUÇÃO GRÁFICA DO PROBLEMA DE MINIMIZAÇÃO DE PROGRAMAÇÃO LINEAR
Z = 2x1 + 3x2
∇z = (
∂Z ∂Z
,
)
∂x1 ∂x 2
gradiente de z, representado por ∇ (nabla)
∇z = (2, 3) a função objetiva sempre é
perpendicular ao ∇ e sobe no sentido que está apontado o ∇.
X2
10
x1 + x2 ≥ 5 A: x1 + x2 = 5
A
x2 = 5 – x1
X1
5
0
X2
0
5
5
5x1 + 1x2 ≥ 10 B: x2 = 10 - 5x1
3
B
X1
0
2
0
2
5
X2
10
0
X1
Solução ótima (x1 = 5; x2 = 0 e z = 10)
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
9
2.4.3 APLICAÇÕES EM SISTEMAS PRODUTIVOS
1. Resolver graficamente o modelo de programação linear
1.1. Maximizar RECEITA = 0,3x1 + 0,5x2
Sujeito a:
2x1 + x2 ≤ 2
x1 + 3x2 ≤ 3
x1, x2 ≥ 0
1.2. Minimizar CUSTO = 10x1 + 12x2
Sujeito a:
x1 + x2 ≤ 20
x1 + x2 ≥ 10
5x1 + 6x2 ≥ 54
x1, x2 ≥ 0
1.3. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100
u.m. e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas
para fabricar uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O
tempo mensal disponível para essas atividades é de 120 horas. As demandas
esperadas para os dois produtos levaram a empresa a decidir que os
montantes produzidos de P1 e P2 não devem ultrapassar 40 unidades de P1 e
30 unidades de P2 por mês. Construa o modelo do sistema de produção
mensal com o objetivo de maximizar o lucro da empresa.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
10
1.4. Duas fábricas produzem 3 diferentes tipos de papel. A companhia que controla
as fábricas tem um contrato para produzir 16 toneladas de papel fino, 6
toneladas de papel médio e 28 toneladas de papel grosso. Existe uma
demanda para cada tipo de espessura. O custo de produção na primeira
fábrica é de 1.000 u.m. e o da segunda fábrica é de 2.000 u.m., por dia. A
primeira fábrica produz 8 toneladas de papel fino, 1 tonelada de papel médio e
2 toneladas de papel grosso por dia, enquanto a segunda fábrica produz 2
toneladas de papel fino, 1 tonelada de papel médio e 7 toneladas de papel
grosso. Quantos dias cada fábrica deverá operar para suprir os pedidos mais
economicamente?
1.5. Uma companhia de transporte tem dois tipos de caminhões: O tipo “A” tem
2m3 de espaço refrigerado e 3m3 de espaço não refrigerado; O tipo “B” tem
2m3 de espaço refrigerado e 1m3 de espaço não refrigerado. O cliente quer
transportar um produto que necessitará 16 m3 de área refrigerada e 12 m3 de
área não refrigerada. A companhia calcula em 1.100 litros o combustível para
uma viagem com o caminhão “A” e 750 litros para o caminhão “B”.Quantos
caminhões de cada tipo deverão ser usados no transporte do produto, com o
menor consumo de combustível.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
11
2.5 MÉTODO SIMPLEX
O algoritmo Simplex de resolução de problema de programação linear
foi desenvolvido pelo matemático norte americano George B. Dantzig em 1947.
O Método Simplex de programação linear utiliza os conceitos básicos
da álgebra matricial para achar a intersecção de duas ou mais retas ou planos. Ele
começa em alguma solução viável, isto é aquela que satisfaça todas as restrições,
e sucessivamente obtém soluções em intersecções que fornecem valores cada
vez melhores para a função objetiva. Além disso, esse método fornece um
indicador que determina quando a solução ótima é atingida.
Dentro da matriz, tem-se uma coluna para cada variável real positiva,
uma coluna para cada variável auxiliar ou de folga e uma última coluna é para
cada constante indicando a limitação do recurso.
2.5.1 INTRODUÇÃO DAS VARIÁVEIS DE FOLGA
Se as restrições são expressas em inequações, é preciso modificá-las
em equações. Isto é feito pela introdução de um termo adicional em cada
restrição. Este termo recebe o nome de variável de folga (si). Conforme já visto
anteriormente, que as restrições do problema têm a seguinte estrutura lógica:
Utilização de recursos ≤ disponibilidade
Se introduzir o conceito de folga de recurso pode-se escrever a relação
acima da seguinte forma:
Utilização mais folga = disponibilidade
Isto significa que:
•
utilização < disponibilidade
folga > 0
•
utilização = disponibilidade
folga = 0
Assim, a folga de cada recurso pode se representada por uma variável
de forma exatamente igual à produção de cada produto.
Desse modo, Chamando-se de:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
12
•
s1 = folga da madeira
•
s2 = folga de mão-de-obra
Introduzindo a variável s1 para a primeira desigualdade e s2 para a
segunda, tem-se o sistema anterior transformado. É óbvio que ao introduzir duas
variáveis de folga (auxiliares) nesse sistema de inequações lineares terá o sistema
de equações lineares:
Max Z = 4x1 + 1x2 + 0s1 + 0s2
s.a.:
2x1 + 3x2 + 1s1 + 0s2 = 12
2x1 + 1x2 + 0s1 + 1s2 = 8
x1, x2, s1, s2 ≥ 0
onde s1, s2 são as variáveis de folga. Estas variáveis representam a parte não
utilizada dos recursos a que se referem às inequações de restrição.
O objetivo agora é encontrar valores não negativos de x1, x2, s1 e s2 que
satisfaçam as duas novas condições de restrição e maximizem o valor da função
objetivo (Z).
Inicialmente monta-se a Tabela 1
Base
x1
x2
s1
s2
constantes (b)
S1
2
3
1
0
12
S2
2
1
0
1
8
Z
4
1
0
0
0
A última coluna corresponde aos termos independentes das equações,
e a última linha contém os coeficientes da função objetiva.
Nesta última linha, sempre tem a contribuição que cada variável dá para
o lucro total L, por unidade, em cada iteração do processo de solução.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
13
Solução inicial:
A solução inicial para o problema será sempre obtida fazendo as
variáveis originais do modelo (no caso x1, x2) iguais a zero e achando o valor das
demais. Assim temos x1 = x2 = 0 (variáveis não básicas) e s1 = 12 e s2 = 8
(variáveis básicas) e Z = 0.
Como a primeira solução não é a melhor, procura-se outra que dê um
valor maior para Z.
O problema é descobrir:
• Das duas variáveis não básicas (nulas) na primeira solução, qual
deverá ser básica, isto é, se tornar positiva?
• Das duas variáveis básicas (positivas) qual deverá ser anulada?
Observando a tabela 1, nota-se que a contribuição unitária para o lucro
da variável x1, é maior que a contribuição de x2. Logo, a variável que deverá se
tornar positiva é x1. Por outro lado, examinando as duas equações, o maior valor
possível para x1 na primeira equação, será 6, quando s1 for igual a zero, e o maior
valor possível para x1 na segunda equação, será 4, quando s2 for igual a zero.
Observe que essa análise pode ser feita diretamente no tabela 1,
através da divisão dos elementos da coluna b pelos correspondentes elementos
da coluna x1.
O menor quociente indica, pela linha em que ocorreu, qual a variável
básica que deve ser anulada, isto é, sair da base.
Como 12/2 = 6 e 8/2 = 4, a variável básica a ser anulada é s2 e, em seu
lugar entra a variável x1.
1a. operação: Dividir a segunda linha por 2.
Tabela 2
Base
x1
x2
s1
s2
b
s1
2
3
1
0
12
x1
1
0,5
0
0,5
4
Z
4
1
0
0
0
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
14
2a. operação: a) Multiplicar a 2a linha por (-2) e somar com a 1a linha, colocando o
resultado na linha 1.
b) Multiplicar a 2a linha por (-4) e somar com a 3a linha, colocando o
resultado na linha 3.
Tabela 3
Base
x1
x2
s1
s2
b
S1
0
2
1
-1
4
X1
1
0,5
0
0,5
4
Z
0
-1
0
-2
-16
-2L2 + L1
-4L2 + L3
Como a última linha mostra as contribuições líquidas para o Z, e como
estas contribuições têm seus valores com sinais (-) trocados com relação à tabela
original, concluímos que a solução encontrada, x1 = 4; x2 = 0; s1 = 4; s2 = 0 e Z=16
é a solução ótima.
O valor positivo de s1 representa uma quantidade não usada de
madeira, isto é, 4m2.
2.5.2 MÉTODO SIMPLEX EM DUAS FASES
O processo iterativo do Método Simplex sempre exige uma solução
básica para iniciar a busca da solução ótima.
2.5.2.1 OBTENÇÃO DA SOLUÇÃO BÁSICA INICIAL
Essa solução básica inicial vista até o presente momento era formada
pelas variáveis de folga, já que as restrições eram do tipo (≤). Quando as
restrições são do tipo (=) ou (≥), não existe essa solução básica inicial natural.
Veja o exemplo:
Min z = 16x1 + 12x2 + 5x3
s.a.:
8x1 + 4x2 + 4x3 ≥ 16
4x1 + 6x2
≥ 12
x1, x2, x3 ≥ 0
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
15
Como as restrições são tipo (≥), as variáveis de folga (variáveis
auxiliares) a serem acrescentadas devem ter coeficientes negativos, tendo o
significado de variáveis de excesso. Assim o problema fica:
Min z = 16x1 + 12x2 + 5x3 – 0s1 – 0s2
s.a.:
8x1 + 4x2 + 4x3 – 1s1
4x1 + 6x2
= 16
– 1s2 = 12
x1, x2, x3, s1, s2 ≥ 0
Ressalta-se que quando o problema original não assume a forma
canônica, após a introdução de variáveis auxiliares, deve-se acrescentar variáveis
artificiais (ai) ao mesmo, formando um novo problema de programação linear.
A introdução de variáveis artificiais, que não tem significado algum para
o problema real, mas que permitem a inicialização do processo usando o mesmo
algoritmo simplex descrito anteriormente. Com a introdução de variáveis artificiais,
o método simplex deverá desdobrar-se em duas fases, conforme será visto a
seguir.
2.5.2.2 MÉTODO DAS DUAS FASES
Passo 1: Introduzidas as variáveis de folga ou de excesso, para as restrições do
tipo (≤) ou (≥) respectivamente, devem ser adicionadas as variáveis artificiais para
todas as restrições do tipo (=) ou (≥), tal como:
8x1 + 4x2 + 4x3 – 1s1
4x1 + 6x2
+ 1a1
– 1s2
= 16
+ 1a2 = 12
Passo 2: Cria-se uma Função Objetiva Artificial da seguinte maneira. Para todas
as variáveis reais e de folga, o coeficiente da função artificial será a soma dos
coeficientes destas variáveis, e zero para as variáveis artificiais. Em nosso
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
16
exemplo, com as restrições do problema, tem-se a seguinte função objetiva
artificial:
F.O. artificial: 12x1 + 10x2 + 4x3 – 1s1 – 1s2 + 0a1 + 0a2 = 28
Passo 3: Monta-se a tabela de solução de forma exatamente igual à sistemática
anterior, colocando-se a função objetiva artificial na última linha.
Tabela 4
Base
x1
x2
x3
s1
s2
a1
a2
B
A1
8
4
4
-1
0
1
0
16
a2
4
6
0
0
-1
0
1
12
Z
16
12
5
0
0
0
0
0
za
12
10
4
-1
-1
0
0
28
Passo 4: Aplica-se o Método Simplex normalmente, usando como função objetiva
a última linha. Quando a solução for atingida, dois casos podem ocorrer:
1) Za = 0: Neste caso foi obtida uma solução básica do problema original e o
processo de solução deve continuar, desprezando-se as variáveis artificiais
e os elementos da última linha. É o início da fase 2 do processo.
2) Za ≠ 0: Neste caso o problema original não tem solução viável, o que
significa que as restrições devem ser inconsistentes.
Fase 1: Resolver o problema de forma completa
Tabela 5
Base
x1
x2
x3
s1
s2
a1
a2
b
a1
8
4
4
-1
0
1
0
16
a2
4
6
0
0
-1
0
1
12
Z
16
12
5
0
0
0
0
0
za
12
10
4
-1
-1
0
0
28
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
17
1a. iteração: entra a variável x1 e sai a variável a1
Tabela 6
Base
x1
x2
x3
s1
s2
a1
a2
B
x1
1
0,5
0,5
-0,125
0
0,125
0
2
a2
0
4
-2
0,5
-1
-0,5
1
12
Z
0
4
-3
2
0
-2
0
-32
za
0
4
-2
0,5
-1
-1,5
0
4
2a. iteração: entra a variável x2 e sai a variável a2
Tabela 7
Base
x1
x2
x3
s1
s2
a1
a2
b
X1
1
0
0,75
-0,1875
0,125
0,1875
-0,125
1,5
X2
0
1
-0,5
0,125
-0,25
-0,125
0,25
1
Z
0
0
-1
1,5
1
-1,5
-1
-36
za
0
0
0
0
0
-1
-1
0
Como na última linha o valor da função objetiva artificial é zero, a fase 1
termina e a solução encontrada é a solução básica inicial para a fase 2.
Fase 2: Resolver o problema para minimização da função
Tabela 8 inicial
Base
x1
x2
x3
s1
s2
B
x1
1
0
0,75
-0,1875
0,125
1,5
x2
0
1
-0,5
0,125
-0,25
1
Z
0
0
-1
1,5
1
-36
Como o problema é de minimização, então entra a variável de menor
contribuição.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
18
1a. iteração: entra a variável x3 e sai a variável x1
Tabela 9 final
Base
x1
x2
x3
s1
s2
b
x3
1,333
0
1
-0,25
0,1667
2
x2
0,667
1
0
0
-0,1667
2
Z
1,333
0
0
1,25
1,1667
-34
Como os coeficientes da última linha são todos nulos ou positivos, a
solução obtida é ótima. No caso, x2 = 2, x3 = 2 e z = 34
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
19
2.5.3 APLICAÇÕES EM SISTEMAS PRODUTIVOS
1. Resolver os modelos de programação linear, usando o método simplex.
1.1. Max LUCRO = 2x1 + 3x2 + 4x3
Sujeito a .:
x1 + x2 + x3 ≤ 100
2x1 + x2
x1
≤ 210
≤ 80
x1, x2, x3 ≥ 0
1.2. Min CUSTO = 2x1 + 3x2
Sujeito a .:
x1 + x2 ≥ 5
5x1 + x2 ≥ 10
x1, x2 ≥ 0
1.3. Uma companhia fabrica dois produtos P1 e P2 que utilizam os mesmos
recursos produtivos: matéria-prima, forja e polimento. Cada unidade de P1
exige 4 horas de forjaria, 2 horas de polimento e utiliza 100 u. de matériaprima. Cada unidade de P2 requer 2 horas de forjaria, 3 horas de polimento e
200 u. de matéria-prima. O preço de venda de P1 é 1.900 u.m. e de P2, 2.100
u.m. Toda produção tem mercado garantido. As disponibilidades são de: 20
horas de forja; 10 horas de polimento e 500 unidades de matéria-prima, por
dia. Determinar as quantidades de P1 e P2 que otimizem a receita diária dos
produtos.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
20
1.4. Um fabricante de fantasias tem em estoque 32 m de brim, 22 m de seda e 30
m de cetim e pretende fabricar dois modelos de fantasias. O primeiro modelo
(M1) consome 4 m de brim, 2 m de seda e 2 de cetim. O segundo modelo
(M2) consome 2 m de brim, 4 m de seda e 6 de cetim. Se M1 é vendida a
6.000 u.m e M2 a 10.000 u.m., quantas peças de cada tipo o fabricante deve
fazer para obter a receita máxima?
1.5. Uma fábrica de calçados pode produzir sapatos femininos, infantis e
masculinos. A produção de uma dezena de pares de calçados femininos
requer 2 horas de serviço do setor de montagem e 8 horas de serviço do
setor de acabamento. A produção de uma dezena de pares de calçados
infantis requer 1 hora de serviço do setor de montagem e 6 horas de serviço
do setor de acabamento. A produção de uma dezena de pares de calçados
masculinos requer 2 horas de serviço do setor de montagem e 4 horas de
serviço do setor de acabamento. Os ganhos líquidos unitários na produção
de sapatos femininos, infantis e masculinos, em unidades monetárias por
dezenas de pares, são respectivamente 10, 8 e 10. Em cada turno de
trabalho a fábrica dispõe de 300 horas de serviço no setor de montagem e de
720 horas de serviço no setor de acabamento. Determine o plano de
produção que maximiza ganhos líquidos totais.
2. Resolver os modelos de programação linear (1.3, 1.4 e 1.5), usando o Excel, ou
Simplex e Lindo.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
21
2. 6 ANÁLISE DE SENSIBILIDADE
A análise de sensibilidade refere-se ao estudo de certas questões de
pós-otimização. Freqüentemente, o agente econômico tem interesse em saber até
que ponto a solução encontrada para o seu problema de programação linear seria
alterada se um ou mais parâmetros do problema original fossem modificados.
Dessa forma, deve-se examinar o efeito de mudanças paramétricas nos
coeficientes da função objetiva e nos coeficientes do lado direito das restrições. A
análise será totalmente desenvolvida a partir do problema numérico a seguir
descrito. Uma fábrica pode produzir três produtos: 1, 2 e 3. Definimos xj (j=1, 2, 3)
como a quantidade mensal produzida do j-ésimo produto. Os preços de mercado
dos três produtos são P1 = 10,00, P2 = 6,00 e P3 = 4,00. Para produzir uma
unidade do produto 1 são necessárias 1 hora de serviços técnicos, 10 horas de
mão-de-obra e 2 horas de administração. Para produzir uma unidade do produto 2
são necessárias 1 hora de serviços técnicos, 4 horas de mão-de-obra e 2 horas de
administração. Para produzir uma unidade do produto 3 são necessárias 1 hora de
serviços técnicos, 5 horas de mão-de-obra e 6 horas de administração. Existe uma
disponibilidade de 100 horas de serviços técnicos, 600 horas de mão-de-obra e
300 horas de administração. O objetivo da fábrica é maximizar os lucros.
Formalmente o problema é representado como:
Max L = 10x1 + 6x2 + 4x3
S.a .:
x1 + x2 + x3 ≤ 100
(serviços técnicos)
10x1 + 4x2 + 5x3 ≤ 600
(mão-de-obra)
2x1 + 2x2 + 6x3 ≤ 300
(administração)
x1, x2, x3 ≥ 0
onde: x1, x2 e x3 são as quantidades dos produtos 1, 2 e 3 produzidos.
Introduzindo as variáveis de folga, tem-se:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
22
Max L = 10x1 + 6x2 + 4x3 + 0s1 + 0s2 + 0s3
x1 + x2 + x3 + 1s1 + 0s2 + 0s3 = 100
S.a .:
10x1 + 4x2 + 5x3 + 0s1 + 1s2 + 0s3 = 600
2x1 + 2x2 + 6x3 + 0s1 + 0s2 + 1s3 = 300
x1, x2, x3, s1, s2, s3 ≥ 0
As tabelas do problema ficam:
Tabela 10: Inicial
Base
X1
x2
x3
s1
s2
s3
b
s1
1
1
1
1
0
0
100
s2
10
4
5
0
1
0
600
s3
2
2
6
0
0
1
300
Z
10
6
4
0
0
0
0
x3
Tabela 11: Final
Base
x1
x2
s3
b
x2
0
1
0,8333 1,6667 -0,1667
0
66,6667
x1
1
0
0,1667 -0,6667
0
33,3333
s3
0
0
1
100
Z
0
0 -2,6667 -3,3333
0
-733,333
4
s1
-2
s2
0,1667
0
-0,6667
Solução: x1 = 33,33; x2 = 66,67; x3 = 0; s1 = 0; s2 = 0; s3 = 100 e Z = 733,33.
2.6.1 MUDANÇAS PARAMÉTRICAS EM UM COEFICIENTE CJ DA FUNÇÃO OBJETIVO
2.6.1.1 MUDANÇA NO COEFICIENTE DE UMA VARIÁVEL NÃO-BÁSICA
Nota-se, em primeiro lugar, que a coluna associada à atividade x3 não
faz parte da base ótima (exemplo anterior), isto é, a atividade x3 é não-básica.
Dada a própria natureza do problema, de imediato pode-se concluir que, se o
produto 3 não é produzido quando c3 = 4,00, também não irá entrar no plano ótimo
para c3 < 4,00. Portanto, a solução ótima dada na tabela 11 é completamente
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
23
estável com relação à diminuição de c3. O que pode acontecer se c3 > 4,00? Neste
caso é de se esperar que para um valor de c3 suficientemente alto a atividade x3
acabe entrando no plano ótimo. Então, a solução da tabela 11 não deve ser
completamente estável com relação a aumentos de c3.
Supondo que c3 = 4,00 + ∆. Neste caso, a solução da tabela 11 deveria
ser modificada para incorporar esta mudança. Assim, para a solução básica
apresentada na tabela 11 continuar sendo uma solução ótima, o valor de
∆≤2,6667, pois ainda, o valor do coeficiente relativo de lucro permaneceria
negativo ou nulo. Entretanto, nota-se também que para ∆ > 2,6667 tem-se o valor
do coeficiente relativo de lucro maior que 0 (zero) e a solução básica apresentada
na tabela 11 deixará de ser ótima. Concluí-se então que a solução da tabela 11 é
estável com relação a aumentos de c3 até o acréscimo máximo de 2,6667
unidades ao valor utilizado inicialmente. Para c3 > 4 + 2,6667 > 6,6667 a atividade
x3 passa a ser candidata à entrada na base.
Outra maneira de calcular é como segue: quando uma variável é nãobásica, o que se deseja saber é qual seu coeficiente crítico para a estabilidade da
solução, isto é, qual o valor a partir do qual a variável entra na base, mudando a
solução.
No exemplo, a entrada de x3 com valor 1 provoca um aumento no lucro
de 4,00 (1x4) e a diminuição devido às outras variáveis de:
0,8333 x 6 + 0,1667 x 10 + 4 x 0 = 6,6667
O resultado é um decréscimo do lucro de 6,6667 – 4 = 2,6667,
exatamente o valor de seu coeficiente em módulo na tabela final. Para que a
entrada de x3 não diminua o lucro, é necessário que seu lucro unitário seja de: 4 +
2,6667 = 6,6667. Isto é, o lucro corrente mais seu valor de oportunidade. Portanto,
a solução é estável para c3 ≤ 6,6667, e para c3 > 6,6667 a atividade x3 passa a ser
candidata à entrada na base.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
24
2.6.1.2 MUDANÇA NO COEFICIENTE DE UMA VARIÁVEL BÁSICA
Estando interessado agora em saber que tipo de variação podem sofrer
os coeficientes de x1 e x2 sem alterar a solução ótima da tabela 11.
2.6.1.2.1 Intervalo de Estabilidade para o Coeficiente de x1 (c1)
É intuitivamente claro que quando c1 fica abaixo de um certo nível, pode
não ser lucrativo incluir o produto 1 na composição ótima de produtos. Quando c1
cresce, é possível que isto traga uma mudança da composição ótima de produtos
em algum nível. Isto ocorre porque o produto 1 pode tornar-se tão lucrativo que a
mistura ótima pode incluir apenas o produto 1. Portanto, existe um limite superior e
um inferior na variação de c1 dentro da qual a solução ótima dada na tabela 11
não é influenciada.
Para determinar a amplitude de variação sobre c1, deve-se observar
que uma mudança em c1 muda o lucro das variáveis básicas.
Entrada de x3 na base (passa de x3 = 0 para x3 = 1)
Na tabela final 11, a coluna dos coeficientes de x3 nos mostra que,
quando x3 passa de x3 = 0 para x3 =1
•
x2 diminui em 0,8333
•
x1 diminui em 0,1667
•
s3 diminui em 4
O coeficiente de x1 que permite a entrada de x3 é um coeficiente que
iguala o aumento de lucro com a entrada de x3 com a diminuição do lucro devido
às outras variáveis x2, x1 e s3. Conhecidos os lucros unitários da tabela inicial 10, e
chamando o lucro de x1 de c1, teremos:
Aumento devido a x3:
1x4=4
Diminuição devido às outras variáveis e compensação:
0,8333x6 + 0,1667xc1 + 4x0 = 4 c1 = -6
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
25
Entrada de s1 na base (passa de s1 = 0 para s1= 1)
Tem-se que
•
x2 diminui em 1,6667
•
x1 diminui em –0,6667
•
s3 diminui em -2
Aumento devido a s1:
1x0=0
Diminuição devido às outras variáveis e compensação:
1,6667x6 – 0,6667xc1 - 2x0 = 0 c1 = 15
Entrada de s2 na base (passa de s2 = 0 para s2= 1)
Tem-se que
•
x2 diminui em –0,1667
•
x1 diminui em 0,1667
•
s3 diminui em 0
Aumento devido a s2:
1x0=0
Diminuição devido às outras variáveis e compensação:
-0,1667x6 + 0,1667xc1 + 0x0 = 0 c1 = 6
Ordenando os valores críticos de c1: -6≤ 6≤ 10≤ 15 A solução é
6≤ c1 ≤ 15
estável para:
2.6.1.2.2 Intervalo de Estabilidade para o Coeficiente de x2 (c2)
Entrada de x3 na base (passa de x3 = 0 para x3 = 1)
•
x2 diminui em 0,8333
•
x1 diminui em 0,1667
•
s3 diminui em 4
Aumento devido a x3:
1x4=4
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
26
Diminuição devido às outras variáveis e compensação:
0,8333xc2+ 0,1667x10+ 4x0 = 4 c2 = 2,8
Entrada de s1 na base (passa de s1 = 0 para s1= 1)
Tem-se que
•
x2 diminui em 1,6667
•
x1 diminui em –0,6667
•
s3 diminui em -2
Aumento devido a s1:
1x0=0
Diminuição devido às outras variáveis e compensação:
1,6667xc2- 0,6667x10 - 2x0 = 0
c2 = 4
Entrada de s2 na base (passa de s2 = 0 para s2= 1)
Tem-se que
•
x2 diminui em –0,1667
•
x1 diminui em 0,1667
•
s3 diminui em
0
Aumento devido a s2:
1x0=0
Diminuição devido às outras variáveis e compensação:
-0,1667xc2+ 0,1667x10 + 0x0 = 0 c2 = 10
Ordenando os valores críticos de c1: 2,8 ≤ 4 ≤ 10 ≤ 10
A solução é estável para 4 ≤ c2 ≤ 10
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
27
2.6.2 ENTRADA DE UMA NOVA VARIÁVEL
Suponha que tenha sido desenvolvido um quarto produto P4, que usa
os mesmos insumos de P1, P2 e P3, e que não seja possível aumentar a
capacidade gerada por esses insumos. Isto significa que se colocar P4 em
produção, ele concorrerá com P1, P2 e P3 em termos de insumos. A pergunta é
qual deveria ser o lucro mínimo de P4 para que sua fabricação fosse interessante?
Um levantamento de dados mostra que a produção de P4 exige uma
unidade de R1, duas unidades de R2 e uma unidade de R3. Portanto, para fabricálo terá que forçar essas folgas nos recursos, o que implicará uma perda de:
3,33 x 1 + 0,67 x 2 + 0 x 1 = 4,67
onde: 3,33; 0,67 e 0 são os preços sombra ou preço de oportunidade dos
recursos. Portanto, o produto P4 poderia ser fabricado se seu lucro por unidade
fosse no mínimo 4,67.
2.6.3 MUDANÇAS NOS VALORES DOS RECURSOS BJ
Considerando-se a tabela inicial do problema de programação linear
anterior
Tabela 12: Representando novamente a Tabela 10
Base
x1
x2
x3
s1
s2
s3
B
s1
1
1
1
1
0
0
100
s2
10
4
5
0
1
0
600
s3
2
2
6
0
0
1
300
Z
10
6
4
0
0
0
0
A tabela final (solução ótima) resolvida pelo método simplex nos dá
uma série de informações com relação aos recursos usados.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
28
Tabela 13: Tomando novamente a Tabela 11
Base
x1
x2
x3
s1
s3
b
x2
0
1
0,8333 1,6667 -0,1667
0
66,6667
x1
1
0
0,1667 -0,6667
0
33,3333
s3
0
0
1
100
Z
0
0 -2,6667 -3,3333
0
-733,333
4
s2
0,1667
-2
0
-0,6667
a) O recurso R1 cuja folga é s1 é um recurso escasso no programa. Seu
coeficiente na função objetivo, 3,33 indica que se s1 entrar na base com valor 1, a
nova solução terá o lucro diminuído em 3,33. Por outro lado, se conseguir mais
uma unidade desse recurso aos custos correntes, a nova solução que incorpora
essa unidade adicional tem lucro aumentado em 3,33.
O problema agora é saber até quando isso pode ser feito, isto é,
quantas unidades adicionais do recurso R1 alocadas aos custos correntes podem
ser incorporadas na produção com aumento no lucro de 3,33 por unidade. Da
mesma forma, quantas unidades podem retirar ocasionando uma diminuição de
3,33 no objetivo, por unidade retirada.
Chamando essa variação de ∆1. O que se sabe sobre ∆1 é que ela não
poderá torna os valores de b negativos na tabela final.
Da tabela inicial, os valores de b ficariam:
100+∆1
600
100
ou
300
600
1
+
0
300
∆1
0
Na tabela final, esses vetores se transformam em:
66,6667
33,3333
100
1,6667
+
-0,6667
∆1
-2
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
29
Os valores limites para ∆1 são dados por:
66,67 + 1,67∆1 = 0 ∆1 = -40
33,33 - 0,67∆1 = 0 ∆1 = 50
100
-
2∆1
=0
∆1 = 50
Ordenando os valores críticos de b1: -40 ≤ ∆1 ≤ 50. Estes valores limites
(inferior e superior) devem ser somados a 100. Logo, a variação do coeficiente b1
será: 60 ≤ b1 ≤ 150.
b) O recurso R2 cuja folga é s2 é um recurso escasso no programa. Seu
coeficiente na função objetivo, 0,67 indica que se s2 entrar na base com valor 1, a
nova solução terá o lucro diminuído em 0,67. Por outro lado, se conseguir mais
uma unidade desse recurso aos custos correntes, a nova solução que incorpora
essa unidade adicional tem lucro aumentado em 0,67.
Chamando de ∆2 a variação em R2, que mantém a informação do
coeficiente de s2. Como argumentado anteriormente, da tabela inicial tem-se:
100
600+∆2
100
ou
300
0
600
+
300
1
∆2
0
Na tabela final, esses dois vetores se transformam em:
66,6667
33,3333
100
-0,1667
+
0,1667
∆2
0
Os valores limites para ∆2 são dados por:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
30
66,667 - 0,1667∆2 = 0
∆2 = 400
33,333 + 0,1667∆2 = 0
∆2 = -200
100
impossível
+ 0∆2
=0
Ordenando os valores críticos de b2: -200 ≤ ∆2 ≤ 400. Estes valores
limites (inferior e superior) devem ser somados a 600. Logo, a variação do
coeficiente b1 será: 400 ≤ b2 ≤ 1000.
c) O recurso R3 cuja folga é representada por s3 é um recurso não
escasso. Isto significa que uma redução de até 100 horas no recurso não afeta a
solução.
Chamando ∆3 a variação em R3, a tabela inicial ficará:
100
100
600
ou
600
300
300+∆3
0
+
0
∆3
1
Na tabela final, esses dois vetores se transformam em:
66,6667
33,3333
100
0
+
0
∆3
1
Os valores limites para ∆3 são dados por:
66,6667 + 0∆3 = 0 impossível
33,3333 + 0∆3 = 0 impossível
100
+ 1∆3 = 0
∆3 = -100
Somando este valor (-100 + 300), o coeficiente b3 será: b3 ≥ 200.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
31
2.6.4 APLICAÇÕES EM SISTEMAS PRODUTIVOS
Dado o modelo de programação linear:
Max. L = 2.100x1 + 1.200x2 + 600x3
s. a.: 6x1 + 4x2 + 6x3 ≤ 4.800
12x1 + 16x2 + 2x3 ≤ 7.200
(horas de máquina para produção de bens)
(horas de mão-de-obra para produção)
≤ 800
(demanda de P1)
≤ 600
(demanda de P2)
x3 ≤ 600
(demanda de P3)
x1
x2
onde: xj são as decisões de produção dos bens Pj. O objetivo é maximizar o lucro
pela venda desses produtos.
O quadro final pelo método simplex é o seguinte:
base
X1
x2
X3
s1
S2
s3
s4
s5
b
x3
0
-0,8
1
0,20
-0,10
0
0
0
240
x1
1
1,467
0
-0,033 0,10
0
0
0
560
s3
0
-1,467
0
0,033 -0,10
1
0
0
240
s4
0
1
0
0
0
0
1
0
600
s5
0
0,8
0
-0,20
0,10
0
0
1
360
L
0
-1.400
0
-50
-150
0
0
0
1.320.000
Pede-se:
1.1. Qual o intervalo de estabilidade para o coeficiente de x1? O que isto significa?
1.2. Qual o intervalo de estabilidade para o coeficiente de x3? O que isto significa?
1.3. Qual deveria ser o lucro no produto (2) para que valesse a pena fabricá-lo?
1.4. Qual o limite para aquisição do recurso R1, sem alterar a solução.
1.5. Um novo produto que use 3 horas máquina, 5 horas de mão-de-obra e com
demanda garantida de 200 unidades para um lucro máximo de 800 u.m., teria
interesse no programa?
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
32
2.7 DUALIDADE EM PROGRAMAÇÃO LINEAR
Em determinadas situações, a quantidade de cálculos necessária para
resolver um modelo linear pelo método simplex pode ser reduzida. O modelo
inicial, chamado PRIMAL, pode ser substituído por outro chamado DUAL, cuja
solução é mais rápido.
Portanto, todo problema de programação linear
Maximizar Z = c1 x1 + c2 x2 + ... + cn xn
s.a.:
a11 x1 + a12 x2 + ... + a1n xn ≤ b1
a21 x1 + a22 x2 + ... + a2n xn ≤ b2
..................................................
am1 x1 + am2 x2 + ... + amn xn ≤ bm
x1, x2, …, xn ≥ 0
que se chama de PRIMAL pode ser associado um outro problema, chamado de
DUAL.
Minimizar z = b1 y1 + b2 y2 + ... + bn yn
s.a.:
a11 y1 + a21 y2 + ... + an1 yn ≥ c1
a12 y1 + a22 y2 + ... + an2 xn ≥ c2
..................................................
a1m y1 + a2m y2 + ... + amn yn ≥ bm
y1, y2, …, ym ≥ 0
Genericamente, pode-se representar os modelos da seguinte forma:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
33
• Problema Primal:
n
Max Z = ∑ c j x j
j =1
n
s.a. :
∑a
j =1
ij
x j ≤ bi
xj ≥ 0
para i = 1, 2, ..., m
para j = 1, 2, ..., n
• Problema Dual:
m
Min z = ∑ ci yi
i =1
m
s.a. :
∑a
i =1
ij
yi ≥ c j
yi ≥ 0
para j = 1, 2, ..., n
para i = 1, 2, ..., m
Analisando-se os problemas Primal e Dual, pode-se concluir que:
a) Se a função objetiva do dual é de minimização a do primal é de
maximização, e vice-versa.
b) Os termos constantes das restrições do dual são os coeficientes da função
objetiva do primal.
c) Os coeficientes da função objetiva do dual são os termos constantes das
restrições do primal.
d) Se as restrições do dual são do tipo (≥), as do primal são do tipo (≤).
e) O número de incógnitas do dual (m valores de yi) é igual ao número de
restrições do primal.
f) O número de restrições do dual é igual ao número de incógnitas do primal
(n valores de xj).
g) A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes
do primal.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
34
Exemplo: Uma indústria dispõe de três recursos A, B e C, em quantidades
limitadas, com os quais pretende produzir dois produtos (Prod.1) e (Prod.2). O
quadro abaixo dá a utilização unitária de cada recurso em cada um dos produtos e
a disponibilidade de cada recurso. A indústria sabe que cada unidade produzida
do Prod.1 dá uma margem unitária de lucro de R$ 5,00, e cada unidade produzida
do Prod.2 dá uma margem unitária de lucro de R$ 6,00. O problema de
programação da produção da indústria é determinar a quantidade a ser feita de
Prod.1 e Prod.2 de forma a maximizar a margem de lucro total.
Recurso
Disponibilidade
A
B
C
14
9
56
Recurso gasto para fazer
1 unidade do
prod.1
prod.2
1
1
7
2
1
4
Problema 1 - PRIMAL: Em forma matemática, o problema de programação pode
ser:
Max Z = 5x1 + 6x2
s. a .:
x1 + 2x2 ≤ 14
x1 +
x2 ≤ 9
7x1 + 4x2 ≤ 56
x1, x2 ≥ 0
Acrescentando as variáveis de folga (auxiliares), tem-se:
Max Z = 5x1 + 6x2 + 0s1 + 0s2 + 0s3
s. a .: x1 + 2x2 + 1s1 + 0s2 + 0s3 = 14
x1 +
x2 + 0s1 + 1s2 + 0s3 = 9
7x1 + 4x2 + 0s1 + 0s2 + 1s3 = 56
x1, x2, s1, s2, s3 ≥ 0
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
35
Tabela 14
Base
X1
x2
s1
s2
s3
B
S1
1
2
1
0
0
14
s2
1
1
0
1
0
9
s3
7
4
0
0
1
56
Z
5
6
0
0
0
0
Base
x1
x2
s1
s2
s3
b
x2
0,5
1
0,5
0
0
7
s2
0,5
0
-0,5
1
0
2
s3
5
0
-2
0
1
28
Z
2
0
-3
0
0
-42
Base
x1
x2
s1
s2
s3
b
x2
0
1
1
-1
0
5
x1
1
0
-1
2
0
4
s3
0
0
3
-10
1
8
Z
0
0
-1
-4
0
-50
Tabela 15
Tabela 16
Para análise da tabela acima, a solução obtida é ótima, tendo os
seguintes valores: x1 = 4; x2 = 5; s1 = 0; s2 = 0; s3 = 8 e Z = 50.
Por outro lado, supondo que a indústria tenha a alternativa de vender os
recursos A, B e C, em vez de empregá-los na produção dos dois produtos.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
36
O problema que se coloca agora é encontrar o valor da unidade de
cada recurso. É evidente que a venda dos recursos deve fornecer um ganho pelo
menos igual ao obtido com a utilização deles na produção. Chamando:
y1 : valor do recurso A Por unidade;
y2 : valor do recurso B Por unidade;
y3 : valor do recurso C Por unidade.
Em termos de avaliação dos recursos, cada um dos produtos pode
também ser avaliado, levando em conta a utilização dos recursos por unidade
fabricada. Assim, Prod.1 gasta 1 unidade do recurso A, 1 unidade do recurso B e 7
unidades do recurso C. O Prod.2 gasta 2 unidades do recurso A, 1 unidade do
recurso B e 4 unidades do recurso C. É claro que essas avaliações dos produtos
não podem ser inferiores às margens unitárias de lucro fornecidas por cada um.
Além disso, o gerente tem interesse em determinar o valor mínimo do estoque
total, respeitando as restrições de que as avaliações dos produtos sejam pelo
menos iguais aos lucros unitários fornecidos.
Problema 2 - DUAL: Em forma matemática, o problema de programação pode ser:
Min z = 14y1 + 9y2 + 56y3
s. a .: 1y1 + 1y2 + 7y3 ≥ 5
2y1 + 1y2 + 4y3 ≥ 6
y1, y2, y3 ≥ 0
Acrescentando as variáveis de excesso (auxiliares) e as variáveis
artificiais, temos:
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
37
Min z = 14y1 + 9y2 + 56y3 – 1s1 + 0s2 + 0a1 + 0a2
s. a .:
1y1 + 1y2 + 7y3 – 1s1 + 0s2 + 1a1 + 0a2 = 5
2y1 + 1y2 + 4y3 + 0s1 – 1s2 + 0a1 + 1a2 = 6
y1, y2, y3, s1, s2, a1, a2 ≥ 0
Tabela 17
Base
y1
y2
y3
s1
s2
a1
a2
b
a1
1
1
7
-1
0
1
0
5
a2
2
1
4
0
-1
0
1
6
Z
14
9
56
0
0
0
0
0
za
3
2
11
-1
-1
0
0
11
1ª. Iteração
Tabela 18
Base
y1
Y3
0,14285
a2
1,42857
Z
6
za
1,42857
y2
y3
s1
s2
0,14285
1
-0,14286
0
0,42857
0
0,57143
0
8
1
0,42857
0
a2
b
0,14286
0
0,71428
-1
-0,57143
1
3,14285
0
-8
0
-40
-1,57143
0
3,14285
0,57143 -1
a1
2ª. Iteração
Tabela 19
Base
y1
y2
y3
0
0,1
y1
1
Z
za
y3
s1
s2
a1
a2
b
1
-0,2
0,1
0,2
-0,1
0,4
0,3
0
0,4
-0,7
-0,4
0,7
2,2
0
-0,8
0
6
4,2
-5,6
-4,2
-53,2
0
0
0
0
0
-1
-1
0
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
38
3ª. Iteração
Tabela 20
Base
y1
y2
y3
s1
s2
b
y2
0
1
10
-2
1
4
y1
1
0
-3
1
-1
1
Z
0
0
8
4
5
-50
Para análise da tabela acima, a solução obtida é ótima, tendo os
seguintes valores: y1 = 1; y2 = 4; y3 = 0; s1 = 0; s2 = 0 e z = 50.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
39
3 PROGRAMAÇÃO INTEIRA
3.1 INTRODUÇÃO
Um problema de Programação Linear Inteira (PLI) é um problema de
Programação linear (PL) em que todas as variáveis de decisão são discretas, isto
é, têm que assumir valores inteiros. Embora na Programação Inteira (PI) inclua
também a Programação Não-Linear Inteira, em praticamente todos os modelos da
vida real se preserva a estrutura linear das funções. Assim, neste trabalho serão
apresentados apenas os modelos de Programação Linear Inteira.
3.2 MÉTODOS DE RESOLUÇÃO
Poderia aparecer à primeira vista que os problemas de PLI são
relativamente fáceis de resolver: os problemas de PL são resolvidos de forma
extremamente eficiente e, entre os problemas de PL e de PLI, a única diferença é
haver, no caos da PLI, muito menos soluções a serem consideradas (soluções
inteiras e não reais).
3.3 MÉTODO DE PARTIÇÃO E AVALIAÇÃO SUCESSIVAS
O método “Branch and Bound” consiste na partição (ramificação)
sucessiva do conjunto de soluções possíveis do problema de PLI em subconjuntos
e na limitação (avaliação) do vetor ótimo da função objetiva (limite inferior se tratar
de maximização, ou limite superior se tratar de minimização), de modo a excluir os
subconjuntos que não contenham a solução ótima.
Partindo da constatação de que “se, na solução ótima da relaxação
linear de um problema de PLI, as variáveis tomam valores inteiros, então essa
solução é a solução ótima do PLI”.
Começa-se por resolver a relaxação linear do PLI inicial: se as variáveis
que no problema de PLI são inteiras tomam, na solução ótima de PL, valores
inteiros, então foi encontrada a solução ótima do PLI; caso contrário, divide-se o
problema de PL em dois, através da introdução de restrições adicionais que fazem
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
40
a partição do conjunto das soluções possíveis. Vão então resolvendo sucessivos
problemas de PL, estabelecendo-se limites para o valor ótimo da função objetiva
e, assim, eliminando diversos subconjuntos, até alcançar a solução ótima do PLI.
3.4 APLICAÇÃO
Considere-se o seguinte exemplo: Pedro, proprietário de uma empresa
moveleira “Mulher Feliz”, decidiu criar uma secção para fabricar móveis de
madeira, começando por apenas dois tipos de móveis: armários (lucro unitário de
R$ 240,00) e escrivaninhas (lucro unitário de R$ 150,00). Cada armário requer
uma hora de trabalho e 9 m2 de madeira, enquanto que cada escrivaninha requer
uma hora de trabalho e 5 m2 de madeira. Supondo que estão disponíveis 6 horas
de trabalho e 45 m2 de madeira, que quantidades de forma a maximizar o lucro?
Variáveis de decisão:
• x1 = quantidade a produzir de armário
• x2 = quantidade a produzir de escrivaninha
Com essa definição de variáveis, pode-se escrever as relações que
formam o modelo matemático. Assim, o problema de Programação Inteira será:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
x1, x2 ≥ 0 e inteiros
O primeiro passo consiste na resolução da relaxação linear do PLI, que
corresponde no método simplex. Por outro lado, já que envolve apenas duas
variáveis de decisão, a solução pode ser obtida graficamente.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
41
Resolvendo o modelo acima, a solução ótima do problema de PL é:
x1 = 3,75 e x2 = 2,25 e Lucro = 1.237,50
Desde já se sabe que o valor ótimo da função objetiva não pode
exceder 1.237,50. Como na solução ótima deste problema, as variáveis de
decisão x1 e x2 não são inteiras, há necessidade de efetuar a sua partição, dando
origem a dois novos problemas (A e B), pela introdução de novas restrições de
eliminação de soluções não inteiras: x1 ≤ 3 e x1 ≥ 4. Poderia ter escolhido a
variável x2 para fazer a partição. Neste caso, o problema de PI, fica:
A:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x1
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
≤ 3
x1, x2 ≥ 0 e inteiros
Solução ótima do subproblema A: x1 = 3 e x2 = 3 e L = 1.170,00
B:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x1
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
≥4
x1, x2 ≥ 0 e inteiros
Solução ótima do subproblema B: x1 = 4 e x2 = 1,8 e L = 1.230,00
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
42
Primeira partição: Introduzindo, no problema de PL inicial, a restrição x1 ≤ 3
obtém-se o subproblema A, cuja solução ótima é inteira, e introduzindo a restrição
x1 ≥ 4 obtém-se o subproblema B cuja solução ótima ainda não é inteira, pelo que
se tem de continuar a partição.
A solução ótima do subproblema A é inteira, o que significa que se
encontrou uma solução inteira cujo valor da função objetiva é 1.170,00. O valor
ótimo da função objetiva estará compreendido entre estes dois limites, 1.170,00 ≤
L ≤1.237,50. Como a solução ótima do subproblema B não é inteira e o valor da
função objetiva é 1.230,00 (> 1.170,00) este problema pode conter uma solução
inteira melhor que a do subproblema A; logo, é necessário efetuar a sua partição,
dando origem aos subproblemas B1 e B2, pela introdução das restrições x2 ≥ 2 e
x2≤ 1. Assim, os subproblemas são da forma:
B1:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
≥4
x1
x2 ≥ 2
x1, x2 ≥ 0 e inteiros
Resolvendo-se o subproblema B1 notou-se que o mesmo não tem
soluções possíveis, sendo por isso excluído.
B2:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x1
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
≥4
x2 ≤ 1
x1, x2 ≥ 0 e inteiros
Solução ótima do subproblema B2: x1 = 4,44 e x2 = 1 e L = 1.216,67
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
43
Segunda partição: Introduzindo, no subproblema B, a restrição x2 ≥ 2 obtém-se o
subproblema B1 (solução impossível) e introduzindo a restrição x2 ≤ 1 obtém-se o
subproblema B2 cuja solução ainda não é inteira, pelo que se tem de continuar a
partição.
O subproblema B1 não tem soluções possíveis, sendo por isso excluído.
O subproblema B2, pelas mesmas razões do subproblema B, é objeto de partição
e dá origem aos subproblemas B21 e B22, pela introdução das restrições x1 ≤ 4 e
x1≥ 5 e. Assim, os subproblemas são da forma:
B21:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
≥4
x1
x2 ≤ 1
x1 =4
≤4
x1
x1, x2 ≥ 0 e inteiros
Solução ótima do subproblema B21: x1 = 4 e x2 = 1 e L = 1.110,00
B22:
Max L = 240x1 + 150x2
s.a.:
x1 +
9x1 +
x2 ≤ 6 (horas de trabalho)
5x2 ≤ 45 (quantidade de madeira)
x2 ≤ 1
x1
≥5
x1, x2 ≥ 0 e inteiros
Solução ótima do subproblema B22: x1 = 5 e x2 = 0 e L = 1.200,00
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
44
Terceira partição: Introduzindo, no subproblema B2, a restrição x1 ≥ 5 obtém-se o
subproblema B21 e introduzindo a restrição x1 ≤ 4 obtém-se o subproblema B22.
Como todas as soluções são inteiras não há necessidade de efetuar mais
nenhuma partição. Portanto a solução ótima do problema de PLI foi encontrada,
cujos valores são: x1 = 5, x2 = 0 e L = 1.200,00.
Dessa forma, tanto o subproblema B21 quanto o subproblema B22 têm
soluções inteiras. O valor ótimo da função objetiva do subproblema B21 é menor
que 1.170,00, ou seja, pior do que a solução de que já se dispunha. O valor ótimo
da função objetiva do subproblema B22 é 1.200,00. A seqüência total de partições
é particularmente apresentada abaixo no seguinte diagrama, estruturado em forma
de árvore, isto é, método “Branch and Bound”.
(x1 = 3,75; x2 = 2,25)
L = 1.237,50
x1 ≤ 3
x1 ≥ 4
A
(x1 = 3; x2 = 3)
L = 1.170,00
B
x2 ≥ 2
x2 ≤ 1
B1
Solução
Impossível
(x1 = 4; x2 = 1,8)
L = 1.230,00
B2
x1 ≤ 4
B21
(x1 = 4; x2 = 1)
L = 1.110,00
(x1 = 4,44; x2 = 1)
L = 1.216,67
x1 ≥ 5
B22
(x1 = 5; x2 = 0)
L = 1.200,00
Diagrama estruturado em forma de árvore - método “Branch and Bound”.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
45
3.5 APLICAÇÕES EM SISTEMAS PRODUTIVOS
Uma fábrica pode produzir três produtos: 1, 2 e 3. Definimos xj (j=1, 2,
3) como a quantidade mensal produzida do j-ésimo produto. Os preços de
mercado dos três produtos são P1 = 10,00, P2 = 6,00 e P3 = 4,00. Para produzir
uma unidade do produto 1 são necessárias 1 hora de serviços técnicos, 10 horas
de mão-de-obra e 2 horas de administração. Para produzir uma unidade do
produto 2 são necessárias 1 hora de serviços técnicos, 4 horas de mão-de-obra e
2 horas de administração. Para produzir uma unidade do produto 3 são
necessárias 1 hora de serviços técnicos, 5 horas de mão-de-obra e 6 horas de
administração. Existe uma disponibilidade de 100 horas de serviços técnicos, 600
horas de mão-de-obra e 300 horas de administração. O objetivo da fábrica é
maximizar os lucros.
Max L = 10x1 + 6x2 + 4x3
S.a .:
x1 + x2 + x3 ≤ 100
(serviços técnicos)
10x1 + 4x2 + 5x3 ≤ 600
(mão-de-obra)
2x1 + 2x2 + 6x3 ≤ 300
(administração)
x1, x2, x3 ≥ 0 e inteiros
onde: x1, x2 e x3 são as quantidades dos produtos 1, 2 e 3 produzidos.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto
46
BIBLIOGRAFIA
ANDRADE, E. L. Introdução à Pesquisa Operacional – Métodos e Modelos
para Análise de Decisão. 2. ed. Rio de Janeiro: LTC , 1998.
BREGALGA, P. F.; OLIVEIRA, A. F.; BORNSTEIN, C. T. Introdução a
Programação Linear. 3. ed. Rio de Janeiro: Campus, 1988.
CHAPRA, S. C.; CANALE, R. P. Numerical Methods for Engineers whit
Programming Software Applications. Tird Edition McGraw-Hill, New York, 1998.
EHRLICH, P. J. Pesquisa Operacional. São Paulo: Atlas, 1991.
LANZER, E. A. Programação Linear: Conceitos e Aplicações. 2. ed. Rio de
Janeiro, IPEA/INPES, 1988.
LACHTERMACHER, G. Pesquisa Operacional na Tomada de decisão.
Modelagem em Excel. 3. ed. Rio de Janeiro: Campus, 2007.
SILVA, E. M.; SILVA, E.M.; GONÇALVES, V.; MUROLO, A C. Pesquisa
Operacional para os Cursos de: Economia, Administração e Ciências
Contábeis. 3. ed. São Paulo: Atlas, 1998.
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto