pesquisa operacional na tomada de decisao (1)

Prévia do material em texto

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 
medri@uel.br 
Ms. Ana Satie Yotsumoto 
satie@uel.br 
 
 
 
 
 
 
 
 
 
 
 
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 
 
 
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 
 
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 observou-
se 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 demodelagem 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
j
jj xcZMax
1
 
 i
n
j
jij bxaas ≤∑
=1
:.. para i = 1, 2, ..., m 
 xj ≥ 0 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 
Mão-de-obra 
12 m2 
8 H.h. 
 
 O processo de produção é tal que, para fazer uma 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, 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 ≤ 12 
 
 
 
 
Para a mão-de-obra: 2x1 + 1x2 ≤ 8 
 
 
 
 
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. 
 
Utilização de 
madeira para os 
dois produtos 
Disponibilidade 
de madeira 
Utilização de 
mão-de-obra para 
os dois produtos 
Disponibilidade 
de mão-de-obra 
 
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 
 
6 
 
 
 Z = 4x1 + x2 � gradiente de Z, representado por ∇ (nabla) 
 
 ),(
21 x
Z
x
ZZ
∂
∂
∂
∂
=∇ � ∇Z = (4, 1) � a função objetiva sempre é 
perpendicular ao ∇ e sobe no sentido que está apontado o ∇. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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 
 
Solução ótima (x1 = 4; x2 = 0 e Z = 16) 
 
 X2 
 
 8 
 
 
 
 
 
 4 
 
 
 
 
 1 
 
 0 4 6 X1 
2x1 + 3x2 ≤ 12 � A: 2x1 + 3x2 = 12 
2x1 + 1x2 ≤ 8 � B: x2 = 8 - 2x1 
2
312 2
1
x
x
−
= 
A 
X1 X2 
6 
0 
0 
4 
 
B 
X1 X2 
0 
4 
8 
0 
 
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: 
 
 
),,,()(
21 nx
f
x
f
x
f
xf
∂
∂
∂
∂
∂
∂
=∇ L
 
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
i
ii yczMin
1
 
 
Pesquisa Operacional na Tomada de Decisão – Professores: Dr. Waldir Medri e Ana Satie Yotsumoto 
 
8 
j
m
i
iij cyaas ≥∑
=1
:..
 para j = 1, 2, ..., n 
 0≥jiy para i = 1, 2, ..., m 
Exemplo: 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 � gradiente de z, representado por ∇ (nabla) 
 
 ),(
21 x
Z
x
Z
z
∂
∂
∂
∂
=∇ � ∇z = (2, 3) � a função objetiva sempre é 
perpendicular ao ∇ e sobe no sentido que está apontado o ∇. 
 
 
 
 
 
 
 
 
 
 
 
 X2 
 10 
 
 
 
 
 
 
 5 
 
 
 3 
 
 
 
 
 
0 2 5 X1 
 
Solução ótima (x1 = 5; x2 = 0 e z = 10) 
x1 + x2 ≥ 5 � A: x1 + x2 = 5 
 
x2 = 5 – x1 
A 
X1 X2 
5 
0 
0 
5 
5x1 + 1x2 ≥ 10 � B: x2 = 10 - 5x1 
B 
X1 X2 
0 
2 
10 
0 
 
 
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 
S2 
 2 3 1 0 
 2 1 0 1 
12 
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ê umvalor 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 
x1 
 2 3 1 0 
 1 0,5 0 0,5 
12 
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 
X1 
 0 2 1 -1 
 1 0,5 0 0,5 
4 
4 
Z 0 -1 0 -2 -16 
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 
-2L2 + L1 
-4L2 + L3 
 
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 = 16 
 4x1 + 6x2 – 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 + 1a1 = 16 
4x1 + 6x2 – 1s2 + 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 
a2 
 8 4 4 -1 0 1 0 
 4 6 0 0 -1 0 1 
16 
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 
a2 
 8 4 4 -1 0 1 0 
 4 6 0 0 -1 0 1 
16 
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 
a2 
 1 0,5 0,5 -0,125 0 0,125 0 
 0 4 -2 0,5 -1 -0,5 1 
2 
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 
X2 
 1 0 0,75 -0,1875 0,125 0,1875 -0,125 
 0 1 -0,5 0,125 -0,25 -0,125 0,25 
1,5 
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 
x2 
 1 0 0,75 -0,1875 0,125 
 0 1 -0,5 0,125 -0,25 
1,5 
1 
Z 0 0 -1 1,5 1 -36 
 
 Como oproblema é 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 
x2 
 1,333 0 1 -0,25 0,1667 
 0,667 1 0 0 -0,1667 
2 
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 ≤ 210 
 x1 ≤ 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éria-
prima. 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 
 S.a .: x1 + x2 + x3 + 1s1 + 0s2 + 0s3 = 100 
 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 
s2 
s3 
 1 1 1 1 0 0 
10 4 5 0 1 0 
 2 2 6 0 0 1 
100 
600 
300 
Z 10 6 4 0 0 0 0 
 
Tabela 11: Final 
Base x1 x2 x3 s1 s2 s3 b 
x2 
x1 
s3 
 0 1 0,8333 1,6667 -0,1667 0 
 1 0 0,1667 -0,6667 0,1667 0 
 0 0 4 -2 0 1 
66,6667 
33,3333 
100 
Z 0 0 -2,6667 -3,3333 -0,6667 0 -733,333 
 
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 
docoeficiente 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ão-
bá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: 1 x 4 = 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: 1 x 0 = 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: 1 x 0 = 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 é 
estável para: 6≤≤≤≤ c1 ≤≤≤≤ 15 
 
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: 1 x 4 = 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: 1 x 0 = 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: 1 x 0 = 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 
s2 
s3 
 1 1 1 1 0 0 
10 4 5 0 1 0 
 2 2 6 0 0 1 
100 
600 
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 s2 s3 b 
x2 
x1 
s3 
 0 1 0,8333 1,6667 -0,1667 0 
 1 0 0,1667 -0,6667 0,1667 0 
 0 0 4 -2 0 1 
66,6667 
33,3333 
100 
Z 0 0 -2,6667 -3,3333 -0,6667 0 -733,333 
 
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 100 1 
 600 ou 600 + 0 ∆1 
 300 300 0 
Na tabela final, esses vetores se transformam em: 
 
 66,6667 1,6667 
 33,3333 + -0,6667 ∆1 
 100 -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 100 0 
 600+∆2 ou 600 + 1 ∆2 
 300 300 0 
 
Na tabela final, esses dois vetores se transformam em: 
 
 66,6667 -0,1667 
 33,3333 + 0,1667 ∆2 
 100 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 + 0∆2 = 0 � impossível 
 
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 0 
 600 ou 600 + 0 ∆3 
 300+∆3 300 1 
 
Na tabela final, esses dois vetores se transformam em: 
 
 66,6667 0 
 33,3333 + 0 ∆3 
 100 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 (horas de máquina para produção de bens) 
 12x1 + 16x2 + 2x3 ≤ 7.200 (horas de mão-de-obra para produção) 
 x1 ≤ 800 (demanda de P1) 
 x2 ≤ 600 (demanda de P2) 
 x3 ≤ 600 (demanda de P3) 
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 
x1 
s3 
s4 
s5 
0 
1 
0 
0 
0 
-0,8 
1,467 
-1,467 
1 
0,8 
1 
0 
0 
0 
0 
0,20 
-0,033 
0,033 
0 
-0,20 
-0,10 
0,10 
-0,10 
0 
0,10 
0 
0 
1 
0 
0 
0 
0 
0 
1 
0 
0 
0 
0 
0 
1 
240 
560 
240 
600 
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
j
jj xcZMax
1
 
 i
n
j
jij bxaas ≤∑
=1
:.. para i = 1, 2, ..., m 
 xj ≥ 0 para j = 1, 2, ..., n 
 
• Problema Dual: 
∑
=
=
m
i
ii yczMin
1
 
j
m
i
iij cyaas ≥∑
=1
:.. para j = 1, 2, ..., n 
 yi ≥ 0 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 gasto para fazer 
1 unidade do 
 
Recurso 
 
Disponibilidade 
prod.1 prod.2 
A 
B 
C 
14 
9 
56 
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 
s2 
s3 
 1 2 1 0 0 
 1 1 0 1 0 
 7 4 0 0 1 
14 
9 
56 
Z 5 6 0 0 0 0 
 
 Tabela 15 
Base x1 x2 s1 s2 s3 b 
x2 
s2 
s3 
 0,5 1 0,5 0 0 
 0,5 0 -0,5 1 0 
 5 0 -2 0 1 
7 
2 
28 
Z 2 0 -3 0 0 -42 
 
 Tabela 16 
Base x1 x2 s1 s2 s3 b 
x2 
x1 
s3 
 0 1 1 -1 0 
 1 0 -1 2 0 
 0 0 3 -10 1 
5 
4 
8 
Z 0 0 -1 -4 0 -50 
 
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 
a2 
 1 1 7 -1 0 1 0 
 2 1 4 0 -1 0 1 
5 
6 
Z 
za 
 14 9 56 0 0 0 0 
 3 2 11 -1 -1 0 0 
0 
11 
 
1ª. Iteração 
 Tabela 18 
Base y1 y2 y3 s1 s2 a1 a2 b 
Y3 
a2 
0,14285 0,14285 1 -0,14286 0 0,14286 0 
1,42857 0,42857 0 0,57143 -1 -0,57143 1 
0,71428 
3,14285 
Z 
za 
 6 1 0 8 0 -8 0 
1,42857 0,42857 0 0,57143 -1 -1,57143 0 
-40 
3,14285 
 
2ª. Iteração 
 Tabela 19 
Base y1 y2 y3 s1 s2 a1 a2 b 
y3 
y1 
 0 0,1 1 -0,2 0,1 0,2 -0,1 
 1 0,3 0 0,4 -0,7 -0,4 0,7 
0,4 
2,2 
Z 
za 
 0 -0,8 0 6 4,2 -5,6 -4,2 
 0 0 0 0 0 -1 -1 
-53,2 
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 
y1 
 0 1 10 -2 1 
 1 0 -3 1 -1 
4 
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-selimites 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 5x2 ≤ 45 (quantidade de madeira) 
 x1 ≤ 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 5x2 ≤ 45 (quantidade de madeira) 
 x1 ≥ 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 5x2 ≤ 45 (quantidade de madeira) 
 x1 ≥ 4 
 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 5x2 ≤ 45 (quantidade de madeira) 
 x1 ≥ 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 5x2 ≤ 45 (quantidade de madeira) 
 x1 ≥ 4 
 x2 ≤ 1 
 x1 ≤ 4 
 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 + x2 ≤ 6 (horas de trabalho) 
 9x1 + 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 
x1 =4 
 
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”. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Diagrama estruturado em forma de árvore - método “Branch and Bound”. 
B22 B21 
 A B 
 B1 B2 
(x1 = 3,75; x2 = 2,25) 
 L = 1.237,50
 
x1 ≤ 3 x1 ≥ 4 
(x1 = 4; x2 = 1,8) 
 L = 1.230,00 
(x1 = 3; x2 = 3) 
 L = 1.170,00 
 
(x1 = 4,44; x2 = 1) 
 L = 1.216,67 
 
(x1 = 5; x2 = 0) 
 L = 1.200,00 
 
(x1 = 4; x2 = 1) 
 L = 1.110,00 
 Solução 
Impossível 
 
x2 ≥ 2 x2 ≤ 1 
x1 ≤ 4 x1 ≥ 5 
 
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.