pesquisa_operacional

Prévia do material em texto

Educação a Distância
GRUPO
PESQUISA OPERACIONAL
Caderno de Estudos
Prof. Paulo Afonso Lunardelli
Prof. Roy Wilhelm Probst
UNIASSELVI
2009
NEAD
Copyright  UNIASSELVI 2009
Elaboração:
Prof. Paulo Afonso Lunardelli 
Prof. Roy Wilhelm Probst
Revisão, Diagramação e Produção:
Centro Universitário Leonardo da Vinci - UNIASSELVI
Ficha catalográfica elaborada na fonte pela Biblioteca Dante Alighieri
UNIASSELVI – Indaial.
003
L961p Lunardelli, Paulo Afonso.
 Caderno de Estudos: Pesquisa Operacional/
 Paulo Afonso Lunardelli [e] Roy Wilhelm Probst.
 Centro Universitário Leonardo da Vinci –
 Indaial: Grupo UNIASSELVI, 2009. x ; 138 p. : il.
 Inclui bibliografia.
 ISBN 978-85-7830-212-2
 1. Pesquisa Operacional 2. Teoria de Sistema
 I.Centro Universitário Leonardo da Vinci II. Probst, Roy 
 Wilhelm III. Núcleo de Ensino a Distância. IV. Título.
PESQUISA OPERACIONAL
APRESENTAÇÃO
Caro(a) acadêmico(a)!
A Segunda Guerra Mundial foi o marco inicial para os estudos da Pesquisa Operacional. 
A convocação de um grupo de cientistas ingleses para estudar problemas de estratégia para 
a defesa do país levou-os a pesquisar as operações e recursos militares mais eficazes no 
campo de batalha.
Logo os Estados Unidos perceberam o grande avanço desencadeado pelos cientistas 
da Inglaterra e começaram a estudar atividades semelhantes. Os métodos mais conhecidos 
hoje na área de Pesquisa Operacional têm fontes reconhecidas nos trabalhos de equipes como 
a liderada por George B. Dantzig, dos Estados Unidos, convocada durante a Segunda Guerra 
Mundial, em 1947, com seu Método Simplex. 
Ao término da guerra, ficou o aprendizado e as técnicas de Pesquisa Operacional logo 
caíram no agrado de outras áreas, especialmente a administração e a economia. As indústrias 
perceberam a grande ideia do planejamento e as técnicas desenvolvidas para a tomada de 
decisões fizeram-nas observar os processos industriais com outros aspectos e melhoras 
significativas foram sendo elaboradas com o passar dos anos.
O avanço da informática trouxe mais facilidade na elaboração de projetos cada vez 
mais arrojados, e o uso de computadores mais rápidos e sofisticados trouxe modernidade aos 
métodos que já faziam grande diferença na competitividade do mercado. 
A Pesquisa Operacional firmou-se como ferramenta imprescindível nas diversas áreas 
do conhecimento, fazendo com que sua aplicação, em conjunto com a intuição e o know-how 
de grandes setores do mercado, seja de fundamental importância na busca de avanços no 
planejamento de processos.
“A modelagem matemática, atualmente usada, tem contribuído sobremaneira para a 
evolução do conhecimento humano, seja nos fenômenos microscópicos, em tecnobiologia, 
seja nos macroscópicos, com a pretensão de conquistar o universo. Mas não é um processo 
próprio dos cientistas”. (BIEMBENGUT, 2002, p. 17). 
Assim, nossos estudos voltam-se para a pesquisa operacional, buscando novos 
conhecimentos que melhorem não apenas nossa qualidade de vida como indivíduo, mas 
também a de todos em nossa volta.
E a você, caro(a) acadêmico(a), bons estudos e que este caderno seja uma referência 
nos trabalhos de sucesso que lhe aguardam em breve.
Professor Paulo Afonso Lunardelli
Professor Roy Wilhelm Probst
iii
PESQUISA OPERACIONAL iv
UNI
Oi!! Eu sou o UNI, você já me conhece das outras disciplinas. 
Estarei com você ao longo deste caderno. Acompanharei os seus 
estudos e, sempre que precisar, farei algumas observações. 
Desejo a você excelentes estudos! 
 UNI
PESQUISA OPERACIONAL
SUMÁRIO
UNIDADE 1 – PROGRAMAÇÃO LINEAR ......................................................................... 1
TÓPICO 1: PROBLEMAS DE PROGRAMAÇÃO LINEAR ................................................ 3
1 INTRODUÇÃO ................................................................................................................. 3
2 FORMULAÇÃO DE MODELOS DE PPL ........................................................................ 3
3 MODELAGEM MATEMÁTICA ......................................................................................... 5
3.1 INDÚSTRIA MOVELEIRA.............................................................................................. 6
3.2 PLANEJAMENTO DE PRODUÇÃO AGRÍCOLA ........................................................... 8
3.3 DIETA ALIMENTAR ....................................................................................................... 9
3.4 PROBLEMAS DE TRANSPORTE ................................................................................11
RESUMO DO TÓPICO 1 ................................................................................................... 14
AUTOATIVIDADE ............................................................................................................. 15
TÓPICO 2: SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR ... 17
1 INTRODUÇÃO ............................................................................................................... 17
2 REPRESENTAÇÃO GRÁFICA ...................................................................................... 17
3 VETOR GRADIENTE - ▼ Z ........................................................................................... 20
4 CONSIDERAÇÕES SOBRE O MÉTODO GRÁFICO .................................................... 22
RESUMO DO TÓPICO 2 ................................................................................................... 24
AUTOATIVIDADE ............................................................................................................. 25
TÓPICO 3: PROGRAMAÇÃO LINEAR INTEIRA ............................................................ 27
1 INTRODUÇÃO ............................................................................................................... 27
2 UM MODELO DE PL INTEIRA ...................................................................................... 27
3 O MÉTODO DE BRANCH AND BOUND ....................................................................... 29
3.1 CONSIDERAÇÕES SOBRE O MÉTODO DE BRANCH AND BOUND ...................... 33
4 APLICAÇÃO DE PLI ...................................................................................................... 34
4.1 CONSIDERAÇÕES FINAIS SOBRE A PLI ................................................................. 39
LEITURA COMPLEMENTAR ............................................................................................ 39
RESUMO DO TÓPICO 3 ................................................................................................... 43
AUTOATIVIDADE ............................................................................................................. 44
AVALIAÇÃO ...................................................................................................................... 45
UNIDADE 2 – SOLUÇÃO ÓTIMA ..................................................................................... 47
TÓPICO 1: MÉTODO SIMPLEX ....................................................................................... 49
1 INTRODUÇÃO ............................................................................................................... 49
2 FORMA PADRÃO DO PPL ............................................................................................ 49
2.1 NÃO NEGATIVIDADE DA MÃO DIREITA ................................................................... 50
2.2 VARIÁVEIS NÃO RESTRITAS .................................................................................... 51
2.3 VARIÁVEIS DE FOLGA ............................................................................................... 51
v
PESQUISAOPERACIONAL vi
2.4 VARIÁVEIS DE EXCESSO ......................................................................................... 52
2.5 ALTERAÇÕES NA FUNÇÃO OBJETIVO .................................................................... 53
3 O ALGORÍTMO SIMPLEX ............................................................................................. 53
4 TABLEAU SIMPLEX ...................................................................................................... 60
4.1 DEGENERESCÊNCIA................................................................................................. 67
4.2 MÉTODO DAS DUAS FASES ..................................................................................... 68
5 DUALIDADE .................................................................................................................. 72
5.1 ALGORITMO PRIMAL-DUAL ...................................................................................... 73
RESUMO DO TÓPICO 1 ................................................................................................... 78
AUTOATIVIDADE ............................................................................................................. 80
TÓPICO 2: UTILIZAÇÃO DO COMPUTADOR ................................................................ 81
1 INTRODUÇÃO ............................................................................................................... 81
2 RESOLVENDO MODELOS NO EXCEL ........................................................................ 82
3 ANÁLISE DE PÓS-OTIMALIDADE ............................................................................... 87
3.1 ANALISANDO A FUNÇÃO OBJETIVO........................................................................ 87
3.2 ANALISANDO OS COEFICIENTES DA MÃO DIREITA DAS RESTRIÇÕES ............. 89
RESUMO DO TÓPICO 2 ................................................................................................... 91
AUTOATIVIDADE ............................................................................................................. 92
AVALIAÇÃO ...................................................................................................................... 93
UNIDADE 3 – PROGRAMAÇÃO DE PROJETOS ........................................................... 95
TÓPICO 1: ANÁLISE DE REDES .................................................................................... 97
1 INTRODUÇÃO ............................................................................................................... 97
2 TEORIA DOS GRAFOS ................................................................................................. 97
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE .................................................................. 99
2.2 PROBLEMAS DE FLUXO MÁXIMO.......................................................................... 102
2.3 PROBLEMAS DE CAMINHO MAIS CURTO ............................................................. 104
RESUMO DO TÓPICO 1 ................................................................................................. 109
AUTOATIVIDADE ............................................................................................................110
TÓPICO 2: TÉCNICAS PERT/CPM .................................................................................111
1 INTRODUÇÃO ..............................................................................................................111
2 APLICAÇÃO DE PERT/CPM ........................................................................................111
2.1 REDE DE ATIVIDADES ..............................................................................................112
2.2 CAMINHO CRÍTICO ...................................................................................................113
2.3 PROGRAMAÇÃO DAS ATIVIDADES - PERT ............................................................114
2.4 PROGRAMAÇÃO DAS ATIVIDADES – CPM ............................................................117
RESUMO DO TÓPICO 2 ................................................................................................. 121
AUTOATIVIDADE ........................................................................................................... 122
TÓPICO 3: SIMULAÇÃO ................................................................................................ 125
1 INTRODUÇÃO ............................................................................................................. 125
PESQUISA OPERACIONAL vii
2 SIMULAÇÃO DE MONTE CARLO .............................................................................. 125
2.1 GERANDO NÚMEROS ALEATÓRIOS NO COMPUTADOR .................................... 126
3 PLANEJAMENTO DE SIMULAÇÕES ......................................................................... 128
3.1 EXEMPLO DE SIMULAÇÃO ..................................................................................... 129
LEITURA COMPLEMENTAR .......................................................................................... 132
RESUMO DO TÓPICO 3 ................................................................................................. 135
AUTOATIVIDADE ........................................................................................................... 136
AVALIAÇÃO .................................................................................................................... 137
REFERÊNCIAS ............................................................................................................... 138
PESQUISA OPERACIONAL viii
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
UNIDADE 1
PROGRAMAÇÃO LINEAR
OBJETIVOS DE APRENDIZAGEM
A partir do estudo desta unidade, você será capaz de:
	reconhecer um Problema de Programação Linear (PPL);
	identificar as variáveis de decisão de um PPL;
	escrever a Função Objetivo de um modelo de PPL;
	escrever o conjunto de restrições de um modelo de PPL;
	reconhecer um modelo de Problema de Transporte;
	representar graficamente o conjunto de restrições de um PPL;
	representar o Vetor Gradiente da Função Objetivo;
	determinar a solução do PPL por via gráfica;
	construir um modelo de Programação Linear Inteira;
	resolver um modelo de PLI através do Método de Branch and 
Bound;
	representar a resolução de um PLI por diagramas.
TÓPICO 1 – PROBLEMAS DE PROGRAMAÇÃO LINEAR
TÓPICO 2 – SOLUÇÃO GRÁFICA DE PROBLEMAS DE 
PROGRAMAÇÃO LINEAR
TÓPICO 3 – PROGRAMAÇÃO LINEAR INTEIRA
PLANO DE ESTUDOS
Esta primeira unidade será dividida em três tópicos. No final 
de cada tópico, você encontrará atividades que contribuirão para sua 
reflexão e análise dos estudos já realizados.
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
PROBLEMAS DE PROGRAMAÇÃO 
LINEAR
1 INTRODUÇÃO
TÓPICO 1
UNIDADE 1
Os Problemas de Programação Linear (PPL) são, em sua maioria, problemas de 
otimização que visam maximizar ou minimizar uma função linear de várias variáveis. Essa 
função é chamada de Função Objetivo (FO) e está sujeita a respeitar certo número de relações 
lineares de igualdade ou desigualdade, chamadas de restrições do problema.
Nesta unidade, estudaremos como é feita a formulação dos problemas de programação 
linear através da modelagem matemática, e como se dá a busca pela solução ótima de um 
PPL de duas variáveis através do método gráfico.
2 FORMULAÇÃO DE MODELOS DE PPL
Segundo Wagner (1985, p. 6), a construção de modelos é a essência da abordagem de 
pesquisa operacional. Normalmente, a formulação de um problema de PPL envolve três etapas:
1. A definição do objetivo básico do problema, ou seja, se queremos otimizar por meio de 
maximização (por exemplo, de lucros, ou de um processoque envolva tempo, ou desempenho, 
etc.) ou minimização (de custos, perdas, tempo etc.).
2. A escolha das variáveis de decisão envolvidas (como exemplo, podemos citar a colheita 
de algum tipo de alimento, cuja área destinada ao plantio de diversas espécies de alimentos é uma 
variável a ser decidida) para a formulação da Função Objetivo.
3. Escrever o sistema de restrições do PPL em relação às variáveis de decisão do problema 
(no caso da colheita, podem-se levar em conta as condições ambientais, a demanda pelos alimentos, 
a disponibilidade de mão de obra para plantio, a capacidade de estocagem etc.).
UNIDADE 1TÓPICO 14
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Deve-se tomar o cuidado para que todas as relações do PPL sejam, realmente, lineares.
Os problemas de PL ficam são definidos da seguinte maneira:
(max ou min)Z = c1x1 + c2x2 + ... + cnxn É a função objetivo
Neste modelo, interpretamos:
	x1, x2,...,xn como o conjunto de variáveis de decisão (estruturais) do problema
	c1, c2,...,cn são os coeficientes da função objetivo do problema de PL
	aij e bi são os coeficientes das restrições.
Loesch e Hein (1999, p. 20) chamam os coeficientes bi de coeficientes da mão direita. 
Utilizaremos essa nomenclatura para referenciá-los posteriormente. E ainda, para o Método 
Simplex de resolução de PPL, esses coeficientes deverão ser necessariamente não-negativos.
A última restrição é chamada restrição de não negatividade das variáveis de decisão. 
Normalmente, essa restrição é utilizada em problemas de PL cujas variáveis envolvidas não 
podem assumir valores negativos, como por exemplo, tempo, área, quantidade de mão de obra 
etc., afinal, não faria sentido falar em oito homens negativos trabalhando, por exemplo. Por 
outro lado, alguns problemas podem envolver variáveis que aceitam sinais negativos (como 
exemplo, podem-se citar problemas que envolvam saldos bancários ou temperaturas).
Perceba, no modelo, que as restrições podem ter três opções de sinal ≤ (menor que 
ou igual a), ≥ (maior que ou igual a) e = (igual a). É claro que só podemos usar um sinal em 
cada restrição.
A função objetivo traduz o tipo de otimização que se deseja obter (maximização ou 
minimização, optando por uma das duas).
Todos os coeficientes, tanto da Função Objetivo, quanto das restrições são determinados 
na modelagem do problema. Já os valores das variáveis dependem de um algoritmo de resolução 
para serem calculados. Essas variáveis devem ser valores reais, mas, eventualmente, podem 
assumir valores inteiros, dependendo do tipo de problema que se deseja resolver. Se o problema 
UNIDADE 1 TÓPICO 1 5
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
for definir a quantidade de operários necessários a otimizar certa produção, não há sentido em 
declarar que a solução ótima é, por exemplo, 1,4 homens. Nesse caso, esse tipo de problema 
de PL é chamado de Problema de Programação Linear Inteira e estudaremos métodos de 
resoluções específicos para sua resolução, como o Método de Branch and Bound.
3 MODELAGEM MATEMÁTICA
A modelagem matemática é a mais importante etapa na resolução de problemas de 
PL, constitui o começo do trabalho na busca por soluções. Após a modelagem, podem ser 
usados vários métodos, inclusive computacionais, para a resolução, mas é na modelagem que 
a experiência e o conhecimento do pesquisador atuam com maior ênfase.
Para modelar um problema deve-se saber selecionar o que é mais importante para a 
resolução e, consequente, solução. Um trabalho em equipe, com profissionais de áreas diversas, 
que possam ajudar a esclarecer as variáveis do problema, é muito bem vindo. Geralmente, 
a multidisciplinaridade contribui, e muito, para uma melhor formação do modelo, tendendo a 
uma melhor solução para o mesmo.
Conforme Loesch e Hein (1999, p. 21):
Um modelo é uma representação da realidade. Através de um modelo procura-
se capturar os aspectos relevantes de algum problema ou sistema e representar 
a situação. Os modelos matemáticos constituem uma abstração da realidade, 
representada por um conjunto de equações e relações.
Alguns aspectos devem ser considerados na formulação de um modelo de PPL:
•	se existir a possibilidade, pode-se separar o problema em um grupo de problemas menores, 
resolvendo-os, resolve-se o problema todo;
•	as variáveis de decisão devem ser cuidadosamente selecionadas e definidas (se é real ou 
inteira, qual sua unidade de medida e se pode ser negativa ou não);
•	definir claramente o objetivo, a meta a ser alcançada. Se maximizar ou minimizar as variáveis, 
e qual a função objetivo;
•	construir a rede de relações entre as variáveis, seus limites ou fatores restritivos. Determinar 
o sistema de restrições do problema;
•	deve-se verificar a possibilidade de haver aspectos ou situações que sejam repetitivas, 
redundantes, ou que não tragam relevância à solução do problema. Muitas restrições 
UNIDADE 1TÓPICO 16
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
podem fazer o modelo ficar muito grande e talvez sua resolução seja impraticável. Conferir 
a necessidade de trabalhar com algumas dessas restrições, ou não, é uma boa prática.
Podemos dizer que modelar é uma arte e, por isso, a experiência é um fator 
importante para que se tenha um bom modelo. A prática, o treinamento, o estudo de casos, o 
comprometimento com o problema, as informações extras que possam ser levantadas sobre 
ele, tudo isso leva a uma melhor formulação de um modelo matemático.
Para que você possa ver como tudo isso funciona, selecionamos alguns exemplos de 
situações reais (com algumas considerações, é claro) e os modelamos em termos de problemas 
de programação linear com sua função objetivo e suas restrições. Confira:
Problema: Uma grande fábrica de móveis dispõe em estoque de 800m de tábuas, 600m de 
pranchas e 500m de painéis de conglomerado. A fábrica oferece uma linha de móveis composta 
pelos seguintes produtos: escrivaninha, mesa de reunião, armário e prateleira. Cada tipo de móvel 
consome certa quantidade de matéria prima, conforme a Tabela 1. A escrivaninha é vendida por 
R$ 100,00, a mesa por R$ 80,00, o armário por R$ 120,00 e a prateleira por R$ 20,00.
3.1 INDÚSTRIA MOVELEIRA
TABELA 1 - DISTRIBUIÇÃO DOS MATERIAIS DOS PRODUTOS
Quantidade de material consumido por produto Disponibilidade 
do materialEscrivaninha Mesa Armário Prateleira
Tábua 0 2 2 3 800
Prancha 2 0 1 1 600
Painel 2 1 2 0 500
Valor do 
produto 100 80 120 20 -
FONTE: Os autores
Modelagem: Vamos supor que o fabricante deseje obter o maior lucro possível com a 
venda de seus produtos, não nos preocupando com as especificidades do mercado consumidor, 
digamos que o que se produz se vende. Assim, nossa função objetivo é definida como uma busca 
pelo máximo lucro. Este será calculado através da venda dos produtos por seus respectivos 
valores, assim, é natural que tenhamos as seguintes variáveis de decisão:
XE=quantidade de escrivaninhas que a fábrica deve produzir;
XM=quantidade de mesas que a fábrica deve produzir;
XA=quantidade de armários que a fábrica deve produzir;
UNIDADE 1 TÓPICO 1 7
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
XP=quantidade de Prateleiras que a fábrica deve produzir.
Escrevendo a função objetivo em termos de suas variáveis de decisão, temos;
max L = 100xE + 80xM + 120xA + 20xP , em que max L descreve o lucro máximo.
Com a função objetivo definida, passamos a formulação do sistema de restrições do 
modelo, escrevendo-os em função das variáveis de decisão. Vamos considerar cada um dos 
tipos de matéria-prima como uma restrição quanto ao uso da mesma em cada produto. Assim:
•	Restrição quanto ao uso de tábuas: As unidades produzidas de mesa e de armário 
consomem 2mde tábuas cada, e cada unidade de prateleira produzida consome 3m 
de tábuas, mas não é necessário o uso de tábuas na produção de escrivaninhas. 
Lembrando que a fábrica dispõe de 800m de tábuas, podemos traduzir essas condições 
através da expressão 0xE + 2xM + 2xA + 3xP ≤ 800. O sinal de ≤ indica que a fábrica pode 
consumir qualquer quantidade menor que 800m de tábuas ou igual a este valor.
•	Restrição quanto ao uso de pranchas: A fábrica dispõe de 600m de pranchas, podendo distribuir 
2m para cada escrivaninha produzida, 1m para cada armário e 1m para cada prateleira. 
Assim, escrevemos a restrição 2xE + 0xM + 1xA + 1xP ≤ 600.
•	Restrição quanto ao uso de painéis: Da mesma forma, temos 2xE + 1xM + 2xA + 0xP ≤ 500. Dessa 
vez, xP fica de fora por não utilizar painéis em sua composição. E o limite de uso desse material 
é de até 500m.
•	Essas são as restrições quanto ao uso dos materiais, mas devemos lembrar que estamos 
tratando de produção de unidades de móveis, e essa fábrica não pode produzir, ou vender, 
por exemplo, meio armário, ou uma mesa de reuniões e meia, ou então quatro prateleiras 
negativas. Desse modo, devemos restringir as variáveis de decisão para que sejam todas 
inteiras e não negativas, ou seja, maiores que zero, ou iguais a zero (pode-se optar pela não 
produção de um tipo de produto se isso significar um melhor lucro para a empresa).
Assim, nosso problema de PL fica traduzido no modelo:
max L = 100xE + 80xM + 120xA + 20xP Função Objetivo (maximizar o lucro)
Sujeito a
0xE + 2xM + 2xA + 3xP ≤ 800 Restrição ao uso de tábuas
2xE + 0xM + 1xA + 1xP ≤ 600 Restrição ao uso de pranchas
2xE + 1xM + 2xA + 0xP ≤ 500 Restrição ao uso de painéis
xE , xM , xA , xP ≥ 0 e inteiros Restrição à não negatividade e a natureza da variável
UNIDADE 1TÓPICO 18
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
3.2 PLANEJAMENTO DE PRODUÇÃO AGRÍCOLA
Problema: Um sitiante, possuidor de 50 ares de terra fértil, está planejando sua estratégia 
de plantio para o próximo ano. Por informações obtidas nos órgãos governamentais, sabe-se 
que as culturas de trigo e milho serão as mais rentáveis na próxima safra. Por experiência, 
ele sabe que a produtividade de sua terra é de oito sacas por cada are cultivado de trigo, 
necessitando de três homens-hora de trabalho por are, e dez sacas por cada are cultivado de 
milho, com dois homens-hora de trabalho por are. A mão de obra custa $100,00 por homem-hora 
e a disponibilidade é de 120 hh. Também é sabido que o mercado de consumo se limita a 240 
sacas de trigo, vendidas a $75 cada uma, e 400 sacas de milho, vendidas a $60 cada uma.
Modelagem: Esse agricultor deseja planejar sua produção de modo a conseguir o maior 
lucro possível com o plantio desses dois produtos (ou um deles, se for o caso). Desse modo, 
nosso modelo representa, novamente, um problema de maximização de lucros, em que lucro 
é a diferença entre receita (o que se ganha) e custo (o que se gasta) da produção. Para as 
variáveis de decisão, usaremos então:
xT = quantidade de ares de terra destinados ao plantio de trigo;
xM = quantidade de ares de terra destinados ao plantio de milho.
A receita é proveniente da venda de seus produtos (venda das sacas de trigo e milho) 
e o custo vem dos gastos com mão de obra. Assim, nossa função objetivo será escrita com 
base nessas informações. Para o cálculo da receita, sabemos que 1 are de trigo rende 8 sacas 
do produto ao valor de $75 por saca, e, portanto, 1 are de trigo rende 8 • $75 = $600, e que 
um are de milho rende dez sacas do produto ao valor de $60 por saca, e, portanto, um are de 
milho rende 10 • $60 = $600. Assim, a receita se resume a 600xT + 600xM.
Já os custos de mão de obra também podem ser calculados em função das quantidades 
de ares, já que um are de cultivo de trigo necessita de três homens-hora ao custo de $100 por 
homem-hora, temos que um are de trigo custa 3 • $100 = $300. E como um are de cultivo de 
milho necessita de dois homens-hora ao custo de $100 por homem-hora, temos que um are 
de milho custa 2 • $100 = $200. Assim o custo se resume a 300xT + 200xM.
Como devemos tratar com o lucro, calculamos a diferença (600xT + 600xM)–(300xT + 200xM) 
e temos 300xT + 400xM. Nossa função objetivo fica definida então por max L = 300xT + 400xM .
As restrições do modelo referem-se à quantidade de terra, mão de obra disponível, 
e necessidades do mercado consumidor. Como as variáveis de decisão são referentes à 
quantidade de ares cultivados, não temos necessidade de restringi-los a unidades inteiras, já 
que há a possibilidade de plantar partes de ares (por exemplo, 35,7 ares de trigo). Mas lembre-
UNIDADE 1 TÓPICO 1 9
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
se de que não há medidas negativas para terras. Vamos detalhar cada restrição:
•	Restrição quanto ao tamanho do terreno: Esse agricultor possui cinquenta ares de terra para 
dividir entre a produção de trigo e milho, então, xT + xM ≤ 50.
•	Restrição quanto ao consumo de mão de obra: Dispomos de 120 homens-hora de mão 
de obra para distribuir três hh para cada are cultivado de trigo (3 • xT) e 2 hh para cada are 
cultivado de milho (2 • xM). Resumindo em 3xT + 2xM ≤ 120.
•	Restrição quanto às necessidades de mercado: É sabido que o mercado de consumo se 
limita a 240 sacas de trigo, então a produção deve se limitar a esse valor. Note que a unidade 
de medida em questão é saca, portanto, devemos fazer uma transformação de unidades de 
sacas para ares, lembrando que cada are de trigo rende oito sacas, para a produção de 240 
sacas são necessários trinta ares. Assim, 8xT ≤ 240, ou simplificando, xT ≤ 30.
•	De maneira análoga, podemos calcular a restrição quanto ao consumo de milho, lembrando 
que cada are cultivado de milho produz dez sacas e que o mercado demanda, no máximo, 
quatrocentas sacas (ou seja, quarenta ares). Assim, 10xM ≤ 400, ou simplificando, xM ≤ 40.
•	É preciso ainda restringir as variáveis quanto à não negatividade, ou seja, xT ≥ 0 e xM ≥ 0.
Finalmente, nosso problema de PL fica modelado da seguinte forma:
max L = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não-negatividade
3.3 DIETA ALIMENTAR
Problema: Devemos determinar, em uma dieta para redução calórica, as quantidades de 
certos alimentos que deverão ser ingeridos diariamente, de modo que determinados requisitos 
nutricionais sejam satisfeitos a custo mínimo. Suponha que uma dieta alimentar esteja restrita 
a leite desnatado, carne magra de boi, peixe e uma salada pré-definida. Sabe-se ainda que os 
requisitos nutricionais deveriam ser expressos em termos de vitaminas A, C e D e controlados 
por suas quantidades mínimas (em mg). A tabela 2 resume a quantidade de cada vitamina em 
disponibilidade nos alimentos e a necessidade diária para a boa saúde da pessoa.
UNIDADE 1TÓPICO 110
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
TABELA 2 - QUANTIDADE DE VITAMINAS DISPONÍVEL NOS ALIMENTOS
Vitamina (mg) Leite (l) Carne (kg) Peixe (kg) Salada (kg) Requisito Nutricional
A 2 2 10 20 11
C 50 20 10 30 70
D 80 70 10 80 250
Custo (R$) 2,00 4,00 1,50 1,00 -
FONTE: Disponível em: <www.decom.ufop.br/prof/marcone>. Acesso em: 19 maio 2009.
Modelagem: Nesse caso, buscamos não maximizar e sim minimizar o custo de uma 
alimentação que equilibre as quantidades ingeridas de cada alimento e as quantidades de 
vitaminas, não podendo ultrapassar os limites mínimos a uma alimentação saudável.
Nossas variáveis de decisão serão:
x1 quantidade de leite a ser consumida
x2 quantidade de carne de boi aser consumida
x3 quantidade de carne de peixe a ser consumida
x4 quantidade de salada a ser consumida
E nossa função objetivo será dada em relação aos custos de cada alimento:
min C = 2x1 +4x2 + 1,5x3 +1x4, em que C representa o custo total.
As restrições do problema são determinadas pelos requisitos nutricionais mínimos de 
vitaminas que devem ser incluídas nessa dieta. Assim:
•	Restrição quanto ao consumo de vitamina A: Cada litro de leite ingerido acrescenta 2mg de 
vitamina A na dieta; cada kg de carne acrescenta, também, 2mg; cada kg de peixe acrescenta 
10mg de vitamina A; e cada kg de salada, 20mg; restritos a um mínimo de 11mg dessa 
vitamina, então podemos escrever essa restrição na forma 2x1 +2x3+ 10x3 +20x4 ≥ 11.
•	Restrição quanto ao consumo de vitamina C: De modo análogo, podemos escrever 
50x1 +20x2 + 10x3+30x4 ≥ 70.
•	Rest r i ção quan to ao consumo de v i tamina D: Da mesma fo rma, temos 
80x1 +70x2+ 10x3+80x4 ≥ 250.
E ainda é necessária a restrição de não-negatividade, pois não há possibilidade de 
ingerir, por exemplo, uma quantidade negativa de leite (Você já pensou em beber meio litro 
negativo de leite?). Então x1 , x2, x3 , x4 ≥ 0 .
Organizando nosso modelo, obtemos:
min C = 2x1 +4x2+ 1,5x3+1x4 Função objetivo
Sujeito à
2x1 +2x2+ 10x3+20x4 ≥ 1 Restrição ao consumo de vitamina A
UNIDADE 1 TÓPICO 1 11
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
50x1 +20x2+ 10x3+30x4 ≥ 70 Restrição ao consumo de vitamina C
80x1 +70x2+ 10x3+80x4 ≥ 250 Restrição ao consumo de vitamina D
x1, x2, x3, x4 ≥ 0 Restrição à não negatividade
3.4 PROBLEMAS DE TRANSPORTE
Um dos problemas de Programação Linear mais comum é o problema de transporte. 
Envolve o transporte de cargas entre uma (ou mais) fonte(s) e um (ou mais) destino(s). 
Conhecidos os custos de transporte entre cada fonte e cada destino, conhecidas as capacidades 
de produção das fontes e as capacidades de estoque dos destinos, deseja-se determinar o 
custo mínimo dos transportes.
Acompanhe o exemplo para entender melhor esse tipo de problema.
Duas fábricas (F1 e F2) de brinquedos devem enviar sua produção para três Centros 
de Distribuição (D1, D2 e D3). Os brinquedos são transportados em contêineres fechados em 
um número inteiro de caminhões. Os custos de transporte de cada fábrica (fonte) para cada 
centro de distribuição (destino), as capacidades de produção das fábricas e capacidades de 
estoque dos centros de distribuição estão especificados na tabela 3.
TABELA 3 - CUSTOS DE TRANSPORTE, CAPACIDADES DE PRODUÇÃO DAS FÁBRICAS E 
CAPACIDADES DE ESTOQUE DOS CENTROS DE DISTRIBUIÇÃO
FÁBRICA\CENTRO DE DISTRIBUIÇÃO D1 D2 D3 PRODUÇÃO
F1 8 5 6 120
F2 3 9 10 80
Capacidade de Estoque 90 40 70 200
FONTE: Os autores
UNI
Perceba que o total produzido pelas fábricas é igual à capacidade total 
de estoque dos centros de distribuição. Nesse caso, chamamos esse 
problema de Problema de Transporte Balanceado.
Vamos à modelagem do problema.
UNIDADE 1TÓPICO 112
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Nosso objetivo é minimizar os custos de transporte das cargas entre as fábricas e os 
centros de distribuição, portanto min C. Para isso, nossas variáveis de decisão são seis:
x11 quantidade a ser transportada da Fábrica F1 para o Centro de Distribuição D1
x12 quantidade a ser transportada da Fábrica F1 para o Centro de Distribuição D2
x13 quantidade a ser transportada da Fábrica F1 para o Centro de Distribuição D3
x21 quantidade a ser transportada da Fábrica F2 para o Centro de Distribuição D1
x22 quantidade a ser transportada da Fábrica F2 para o Centro de Distribuição D2
x23 quantidade a ser transportada da Fábrica F2 para o Centro de Distribuição D3
Como minimizar os custos de transporte das cargas depende das quantidades 
transportadas, temos a função objetivo definida por: 
min C = 8x11 + 5x12 + 6x13 + 3x21 + 9x22 + 10x23.
As restrições do nosso problema são de duas naturezas: quanto à produção e quanto 
ao estoque:
•	Restrições quanto à produção: A quantidade de unidades produzidas a serem transportadas 
da Fábrica F1 para D1, D2 e D3 deve ser igual ao total de unidades produzidas por F1, ou 
seja, x11 + x12 + x13 = 120. E a quantidade de unidades produzidas a serem transportadas da 
Fábrica F2 para D1, D2 e D3 deve ser igual ao total de unidades produzidas por F2, ou seja, 
x21 + x22 + x23 = 80.
•	Restrições quanto à capacidade de estoque: A quantidade de unidades produzidas a serem 
transportadas das fábricas F1 e F2 para D1 deve ser igual à capacidade total de estoque de 
D1, ou seja, x11 + x21 = 80. A quantidade de unidades produzidas a serem transportadas das 
fábricas F1 e F2 para D2 deve ser igual à capacidade total de estoque de D2, ou seja, x12 + x22 
= 40. A quantidade de unidades produzidas a ser transportada das fábricas F1 e F2 para D3 
deve ser igual à capacidade total de estoque de D3, ou seja, x13 + x23 = 70.
•	Não negatividade e tipo da variável: Não há como transportar quantidades negativas de 
cargas. Então, todas as variáveis devem ser maiores que zero ou iguais a zero. Podemos 
representar matematicamente essa restrição por xij ≥ 0, com i = 1, 2 e j = 1, 2, 3. As variáveis 
devem ser inteiras.
Assim, podemos resumir nosso modelo através de 
min C = 8x11 + 5x12 + 6x13 + 3x21 + 9x22 + 10x23.
Função objetivo
Sujeito à 
UNIDADE 1 TÓPICO 1 13
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
UNIDADE 1TÓPICO 114
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
RESUMO DO TÓPICO 1
Neste tópico, você estudou que:
	A formulação de um problema de PL envolve três etapas:
	A definição do objetivo básico do problema (Maximizar ou Minimizar) e das variáveis de 
decisão.
	A função objetivo com base nas variáveis de decisão
 (max ou min)Z = c1x1 + c2x2 + ... + cnxn. 
		O sistema de restrições do PPL em relação às variáveis de decisão do
 
	A modelagem matemática é a principal ferramenta para a formulação dos problemas de 
programação linear.
	Um dos tipos mais comuns de problemas de PL envolve transportes.
UNIDADE 1 TÓPICO 1 15
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
AUT
OAT
IVID
ADE �
Agora é sua vez de escrever modelos matemáticos para algumas situações 
encontradas em nossa volta. Tome o devido cuidado na escolha das variáveis de decisão 
e preste muita atenção ao escrever a função objetivo e o conjunto de restrições. Bom 
trabalho!
1 Para uma boa alimentação, o corpo necessita de vitaminas e proteínas.
A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínas é de 
36 unidades por dia.
Uma pessoa tem disponível carne e ovos para se alimentar.
Cada unidade de carne contém quatro unidades de vitaminas e seis unidades de 
proteínas, a um custo de três unidades monetárias por unidade.
Cada unidade de ovo contém oito unidades de vitaminas e seis unidades de proteínas, 
a um custo de 2,5 unidades monetárias por unidade.
Qual o modelo matemático que descreve a quantidade diária de carne e ovos que 
deve ser consumida para suprir as necessidades de vitaminas e proteínas com o 
menor custo possível?
2 Uma indústria têxtil produz três tipos de produtos, cada um dos quais necessariamente 
precisa ser processado em uma máquina de costura reta, em uma máquina de 
costura overlock e embalado. Os tempos consumidos por cada unidade de produto 
em cada processo, a disponibilidade de tempo, os custos e a receita pela venda de 
cada unidade dos produtos seguem na tabela a seguir.
Produto
Tempo de processo (minutos) Consumo 
de matéria 
prima (kg)
Receita 
unitária (RS)Máquina 
reta
Máquina 
overlock Embalagem
Tipo I 15 10 5 1,5 50
Tipo II 1012 8 0,8 65
Tipo III 5 4 3 0,6 30
Disponibilidade 4800 4000 3600 480 -
UNIDADE 1TÓPICO 116
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Deseja-se planejar a produção da próxima semana de forma que o lucro dessa indústria 
seja o máximo possível.
Assumindo com variáveis de decisão:
x1 = quantidade de unidades a produzir do produto tipo A
x2 = quantidade de unidades a produzir do produto tipo B
x3 = quantidade de unidades a produzir do produto tipo C
Responda:
a) Escreva a função objetivo que representa o modelo.
b) Escreva as restrições do problema quanto:
(i) ao tempo de processo na máquina de costura reta;
(ii) ao tempo de processo na máquina de costura overlock;
(iii) ao tempo de processo de embalagem;
(v) à não negatividade.
(vi) ao consumo de matéria-prima.
3 Modele, sem resolver, os seguintes PPLs:
a) Uma indústria produz porcas, parafusos e pregos, podendo usar dois métodos (distintos 
e não simultâneos) para produzi-los. O primeiro método produz 3000 porcas, 2000 
parafusos e 2500 pregos por hora, enquanto que o segundo método produz 4000 
parafusos e 4000 pregos por hora, mas nenhuma porca. A indústria trabalha dezoito 
horas por dia e tem uma encomenda de 5000 parafusos, 5000 pregos e 5000 porcas. 
Ela deve empregar os dois métodos de modo a entregar sua encomenda o mais rápido 
possível, planejando o tempo de operação de cada método.
b) Segundo Wagner (1986, p. 47), o presidente Antônio Castor, da Companhia Ramos de 
Carvalho, quer utilizar do melhor modo possível os recursos de madeira de uma de suas 
regiões florestais. Dentro dessa região, há uma serraria e uma fábrica de compensados; 
assim, as toras podem ser convertidas em madeira beneficiada ou compensada.
Produzir uma mistura comercializável de um metro cúbico de produtos beneficiados 
requer um metro cúbico de pinho e quatro metros cúbicos de canela. Produzir cem 
metros quadrados de madeira compensada requer dois metros cúbicos de pinho e 
quatro metros cúbicos de canela. Essa região tem disponível 32 metros cúbicos de 
pinho e 72 metros cúbicos de canela.
Compromissos de venda exigem que sejam produzidos, durante o período do 
planejamento, pelo menos cinco metros cúbicos de madeira beneficiada e 1200 m2 
de madeira compensada. As contribuições ao lucro são $45 por um metro cúbico de 
produtos beneficiados e $60 por 100 m2 de madeira compensada.
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
SOLUÇÃO GRÁFICA DE PROBLEMAS 
DE PROGRAMAÇÃO LINEAR
1 INTRODUÇÃO
TÓPICO 2
UNIDADE 1
A solução ótima (Z*), ou seja, o máximo lucro ou mínimo custo, por exemplo, de um 
problema de programação linear que tenha duas, ou até três, variáveis de decisão pode ser 
encontrada usando-se representações no sistema de eixos cartesianos ortogonais (plano 
cartesiano). Para simplificar sua compreensão, usaremos o exemplo 2, sobre o planejamento 
de produção agrícola, buscando a solução ótima, ou seja, o máximo lucro que pode ser obtido 
com o plantio dos cereais. 
Segue o modelo do problema de PL para facilitar a leitura dos dados:
maxL = 300xT + 400xM Função Objetivo (maximizar o lucro)
Sujeito a
xT + xM ≤ 50 Restrição ao tamanho do terreno
3xT + 2xM ≤ 120 Restrição ao uso de mão de obra
 xT ≤ 30 Restrição a demanda por trigo
xM ≤ 40 Restrição a demanda por milho
xT , xM ≥ 0 Restrição à não-negatividade
2 REPRESENTAÇÃO GRÁFICA
Para essa representação, usaremos o eixo das abscissas do plano (eixo Ox) para 
representar a variável xT (a quantidade de ares de terra destinados ao plantio de trigo). E 
usaremos o eixo das ordenadas (eixo Oy) para a representação da variável xM (quantidade de 
ares de terra destinados ao plantio de milho). Assim, temos o plano mostrado na Figura 1.
UNIDADE 1TÓPICO 218
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Inicialmente, faremos a representação da 1ª restrição do problema usando a equação 
da reta xT + xM = 50. Os pontos abaixo dessa reta correspondem à desigualdade < da restrição 
do PPL. O gráfico fica definido conforme a Figura 2.
FONTE: Os autores
Fazemos o mesmo com a segunda restrição do problema, usando a equação da reta 
3xT + 2xM ≤ 120. Os pontos abaixo dessa reta correspondem à desigualdade < da restrição do 
PPL. O gráfico fica definido conforme a Figura 3.
FIGURA 1 - PLANO CARTESIANO COM AS COORDENADAS DE xT E xM
FIGURA 2 - PLANO CARTESIANO COM A RESTRIÇÃO xT + xM ≤ 50.
550
50
UNIDADE 1 TÓPICO 2 19
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Como as restrições devem ser respeitadas simultaneamente, deve-se mostrar no gráfico 
a intersecção entre as regiões delimitadas pelas restrições. Imagine-se colando a Figura 2 
sobre a Figura 3.
FONTE: Os autores
Mas você deve lembrar que o PPL deve considerar todas as restrições juntas na 
busca pela solução ótima. Então, devemos graficar todas as equações de retas referentes às 
desigualdades relativas às restrições, tomando o devido cuidado de destacar a área (acima ou 
abaixo da reta da restrição) conforme o sinal da desigualdade (> ou <). O PPL fica graficado 
como mostra a Figura 5.
FIGURA 3 - PLANO CARTESIANO COM A RESTRIÇÃO 3xT + 2xM ≤ 120 
FIGURA 4 - PLANO CARTESIANO COM A REGIÃO DE INTERSECÇÃO DAS 
RESTRIÇÕES xT + xM ≤ 50 E 3xT + 2xM ≤ 120
UNIDADE 1TÓPICO 220
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Perceba que intersecção das restrições do PPL limita o gráfico a uma figura poligonal 
fechada convexa que contém todos os pontos (xT , xM) chamados de Soluções Compatíveis do 
problema de PL, que formam o Conjunto das Soluções Compatíveis. A solução ótima Z* = (x*T , x*M) 
deve ser um destes pontos (ou mais de um ponto, se o problema permitir essa possibilidade).
3 VETOR GRADIENTE - ▼ Z
Uma ferramenta importante na busca da solução ótima é o vetor gradiente da função 
objetivo, que indica a direção do máximo crescimento dela, ou seja, onde devemos procurar o 
ponto do Conjunto de Soluções Compatíveis que faça com que a função objetiva adquira seu 
maior valor. Esse vetor gradiente, representado agora por ▼L (já que queremos o máximo 
lucro), tem como extremidades os coeficientes da função objetivo, ou seja, ▼L = (300, 400). 
Representar esse vetor em nosso gráfico seria loucura, visto o tamanho do vetor, 
mas como o que nos importa é a direção do vetor, basta simplificá-lo dividindo por dez as 
suas coordenadas e então teremos a direção do máximo crescimento de L em (30,40), 
representado na Figura 6.
FIGURA 5 - PLANO CARTESIANO COM O SISTEMA DE RESTRIÇÕES, 
MOSTRANDO A REGIÃO DE INTERSECÇÃO DE TODAS AS 
RESTRIÇÕES
UNIDADE 1 TÓPICO 2 21
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Podemos observar como usar o vetor gradiente para encontrar a solução ótima (L*), 
usando para isso, nada mais do que um simples esquadro (aquele usado na escola). Basta 
colocar um dos lados retos do esquadro em cima do vetor gradiente e deslizá-lo no sentido 
do vetor, desde a origem, observando as retas perpendiculares ao vetor gradiente que são 
definidas pelo outro lado do esquadro (se o problema for de minimização usa-se o sentido 
oposto ao de ▼L). Deve-se manter esse movimento até encontrar o último ponto da região de 
soluções compatíveis que toque o esquadro.
FONTE: Os autores
FIGURA 6 - USO DO VETOR GRADIENTE NA BUSCA DE L*
FIGURA 7 - USO DO ESQUADRO COMO APOIO AO VETOR GRADIENTE NA BUSCA DE Z*
UNIDADE 1TÓPICO 222
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Em nosso exemplo, a reta definida pelo esquadro determina um único ponto que fornece 
o máximo lucro para a função objetivo, que é um vértice do polígono (conjunto)de soluções 
compatíveis. Esse ponto é determinado pelo encontro (intersecção) das equações das retas 
xM = 40 e xT + xM = 50. Para descobri-lo basta calcular o sistema de equações lineares
 
em que temos x*T = 10 e x*M = 40.
A solução ótima para o problema de PL é dada pela função objetivo calculada para estes 
valores. Assim, maxL = 300xT + 400xM = 300 • x*T + 400 • x*M = 300 • 10 + 400 • 40 = 19000.
Podemos ainda interpretar os resultados da seguinte maneira: se o sitiante destinar dez 
ares de sua terra à plantação de trigo e quarenta ares à plantação de milho, seu lucro com a 
venda da safra será de $19.000,00.
Apenas para fins didáticos iremos conferir se a solução ótima encontrada respeita todos 
os limites impostos pelas restrições:
Restrição ao tamanho do terreno xT + xM ≤ 50 
Temos 10 + 40 = 50 ≤ 50 OK!
Restrição ao uso de mão de obra 3xT + 2xM ≤ 120
Temos 3 • 10 + 2 • 40 = 30 + 80 = 110 ≤ 120 OK!
Restrição a demanda por Trigo xT ≤ 30
Temos x*T = 10 ≤ 30
OK!
Restrição a demanda por Milho xM ≤ 40
Temos x*M = 40 ≤ 40 OK!
E é evidente que as varáveis não são negativas. 
Portanto, nossa solução ótima L* = (x*T , x*M) = (10,40) = 19000 respeita todas as 
restrições.
xT + xM = 50
xM = 40{
4 CONSIDERAÇÕES SOBRE O MÉTODO GRÁFICO
Quando o número de restrições do PPL for muito grande, ou os coeficientes da função 
objetivo e restrições forem valores muito “distantes” (um muito grande e outro muito pequeno), 
pode haver uma grande dificuldade em representar esse PPL graficamente. Muitas restrições 
deixam o gráfico “poluído” e dificultam o trabalho com o vetor gradiente.
UNIDADE 1 TÓPICO 2 23
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Para problemas de PL com três variáveis de decisão, devem-se usar não retas para as 
restrições, mas sim planos no espaço (3D) e assim exige-se de você uma grande (diríamos 
espetacular) capacidade para a representação gráfica. 
Você pode optar por resolver graficamente o exemplo 1 (da fábrica de móveis), mas 
entenda isso como muito trabalho e muito tempo dedicado. Vale pela experiência, mas não há 
necessidade. Como veremos adiante, outras técnicas serão muito bem-vindas!
UNIDADE 1TÓPICO 224
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
RESUMO DO TÓPICO 2
Neste tópico, vimos que:
	A solução ótima de um PPL de duas variáveis pode ser encontrada através do gráfico das 
restrições em planos cartesianos, com a ajuda do vetor gradiente.
	Basta traçar num plano cartesiano as equações de cada restrição e definir a região de 
soluções compatíveis como a intersecção das regiões limitadas pelas restrições.
	Com a direção do vetor gradiente e a ajuda de um esquadro, a solução ótima é o último 
ponto de contato do esquadro na região de soluções compatíveis.
	A solução ótima do PPL é o ponto de intersecção das equações no ponto encontrado com 
o esquadro, que pode ser determinada resolvendo um sistema de equações lineares.
UNIDADE 1 TÓPICO 2 25
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
AUT
OAT
IVID
ADE �
Mãos à obra! Resolva as atividades a seguir em uma folha separada. Capriche 
nos gráficos, usando régua ou esquadro, para que fiquem bem visíveis e para que você 
possa compreender perfeitamente os pontos (soluções), as retas (equações) e os planos 
(região compatível).
1 Faça um plano cartesiano ortogonal e represente nele o Vetor Gradiente da função 
objetivo definida por Max Z = 3x1 + 5x2.
2 Em relação ao modelo referente à autoatividade 1 do tópico anterior:
a) Faça o gráfico que representa o conjunto de restrições do modelo.
b) Encontre as coordenadas dos vértices da região de soluções compatíveis do 
modelo.
c) Indique a direção do Vetor Gradiente no plano cartesiano.
c) Qual a solução ótima do problema?
3 Resolva, graficamente, o modelo referente à autoatividade 3(b) do tópico anterior.
UNIDADE 1TÓPICO 226
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
PROGRAMAÇÃO LINEAR INTEIRA
1 INTRODUÇÃO
TÓPICO 3
UNIDADE 1
Os Problemas de Programação Linear Inteira são uma classe de problemas de PL que 
contém uma particularidade: alguma restrição em relação ao tipo de uma ou mais variáveis de 
decisão, como por exemplo, variáveis que podem assumir apenas valores inteiros.
Esse tipo de problema pode ser resolvido do mesmo modo como os problemas de PL, 
mas devem-se utilizar alguns métodos especiais quando a solução encontrada não respeita a 
restrição quanto ao tipo das variáveis. Um dos métodos mais utilizados é o Método de Branch 
and Bound (Ramificação e Limite), que adotaremos em nossos estudos nesse caderno.
2 UM MODELO DE PL INTEIRA
Para compreender melhor esse tipo de problema vamos recorrer a um exemplo.
Seja o problema de PL modelado da seguinte maneira:
max Z = 6x1 + 1x2 É a função objetivo
Sujeito à
 
 
 
Que são as restrições do PPL
Perceba que a última restrição indica duas restrições, a não negatividade das variáveis 
e a restrição quanto ao tipo de variável (são aceitos apenas números inteiros, os decimais 
estão descartados). Resolvendo o PPL através do método gráfico conforme figura 8, sem se 
preocupar com essa restrição encontramos a solução que corresponde a x1 = 0 e x2 ≅	5,67,	
que nos leva a um máximo Z ≅	62,37.
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiros
}
UNIDADE 1TÓPICO 328
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Mas essa solução encontrada não é aceita pelo problema, pois o valor da variável não 
é um número inteiro.
Podemos ficar tentados a resolver esse mero detalhe fazendo um simples arredondamento 
do valor encontrado para o número inteiro mais próximo e recalculando a solução do PPL. 
Assim teríamos x*2 = 6, e a solução ótima, nesse caso, seria Z* = 6 • 0 + 11 • 6 = 66 . Mas 
se fizermos um teste de verificação dessa solução para a compatibilidade com o sistema de 
restrições do problema veremos que a restrição não aceita a solução encontrada:
5x1 + 3x2 ≤ 17 ⇒ 5 . 0 + 3 . 6 = 18 ≤ 17 Não aceita!
Ou seja, a solução ótima arredondada encontrada não satisfaz as restrições do PPL e, 
portanto, não é uma solução compatível com o PPL.
Outra maneira de encontrar a solução ótima inteira e compatível com o sistema de 
restrições do PPL seria procurar, na região do plano cartesiano, as soluções inteiras que se 
encontram dentro da área de soluções compatíveis. Mas há o inconveniente de poder haver 
muitos pontos com essa característica dentro da área de compatibilidade e esse processo pode 
tornar-se demorado e cansativo.
Considerando as alternativas, faz-se necessário um algoritmo de busca que possa 
encontrar a solução ótima de maneira mais eficaz e que obedeça às restrições do problema. 
Empregaremos o Método de Branch and Bound, pois é o mais conhecido e utilizado na resolução 
desse tipo de problema.
FIGURA 8 - SOLUÇÃO GRÁFICA DO PPL DE EXEMPLO
UNIDADE 1 TÓPICO 3 29
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
3 O MÉTODO DE BRANCH AND BOUND
Nosso problema origina-se ao perceber que a solução ótima encontrada, x*1 = 0 e 
x*2 ≅ 5,67 , não obedece à restrição quanto ao tipo da variável, ou seja, não é um numero inteiro 
e a solução arredondada não satisfaz às restrições do PPL. Para resolver esses problemas, 
vamos imaginar a solução como 5 ≤ x2 ≤ 6 e criar dois novos modelos de PL, baseados no 
PPL original, um PPL com a restrição x2 ≤ 5 e outro com a restrição x2 ≥ 6. Esse é o chamado 
processo de ramificação. 
Assim o PPL original, que chamaremos de PL0, que era
max Z = 6x1 + 11x2
Sujeito à
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiro
Fica ramificadoem:
PL1 e PL2
max Z = 6x1 + 11x2 max Z = 6x1 + 11x2 
Sujeito à Sujeito à
5x1 + 3x2 ≤ 17 5x1 + 3x2 ≤ 17
x2 ≤ 5 x2 ≥ 6
x1 , x2 ≥ 0 e inteiro x1 , x2 ≥ 0 e inteiro
Agora, temos o trabalho de resolver dois problemas de PPL, porém, ignorando as 
restrições sobre valores inteiros.
UNIDADE 1TÓPICO 330
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
FONTE: Os autores
Através do método gráfico, podemos observar que:
	A solução encontrada para o PL1 é dada por x*1 = 0,4 e x*2 = 5 , que fornece Z* = 57,4.
	Mas o PL2 não tem solução. Observando as restrições, não há valor de x2 que as satisfaça 
simultaneamente, visto que x1 não pode ser negativo e o mínimo valor para x2 é 6 (restrição 
x2 ≥ 6) Mas a restrição 5x1 + 3x2 ≤ 17 não aceita valores de x2 maiores que 6.
Se o PL2 tivesse solução faríamos uma comparação entre os valores de Z nos PPL 1 
e 2, continuando a busca de Z* pelo PPL que tivesse maior valor.
Para compreender a situação em que nos encontramos, vamos organizar nosso trabalho 
em um diagrama:
FIGURA 9 - GRÁFICO DO PL1 COM AS SUAS RESTRIÇÕES
UNIDADE 1 TÓPICO 3 31
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Como o PL2 não tem solução (é eliminado), e a solução encontrada para o PL1 
ainda não é viável, já que x1* não é inteiro, seguimos a resolução do problema usando o 
PL1, lembrando que temos novamente uma variável com valor decimal. Dessa vez temos 
que pensar em 0 ≤ x1 ≤ 1, e a partir disso, criar dois novos PPLs, ramificando mais uma 
vez nosso problema.
Criamos então os PPLs:
PL3 e PL4
max Z = 6x1 + 11x2 max Z = 6x1 + 11x2
Sujeito à Sujeito à
5x1 + 3x2 ≤ 17 5x1 + 3x2 ≤ 17
x2 ≤ 5 x2 ≤ 5
x1 ≤ 0 x2 ≥ 1
x1 , x2 ≥ 0 e inteiro x1 , x2 ≥ 0 e inteiro 
Analisando as restrições do PL3, percebemos que não há a necessidade de fazer o gráfico. 
As restrições x1 ≥ 0 e x1 ≤ 0 só aceitam uma solução: x1 = 0. Em conseqüência disso, usando a 
restrição 5x1 + 3x2 ≤ 17, temos x2 = 5, que é o máximo valor aceito pela restrição x2 ≤ 5.
Assim, para o PL3 temos: x1 = 0, x2 = 5 e Z = 6 • 0 + 11 • 5 = 55.
Resolvendo o PL4 utilizando o método gráfico, temos:
FONTE: Os autores
FIGURA 10 - GRÁFICO DO PL4 COM SUAS RESTRIÇÕES E O VETOR 
GRADIENTE
UNIDADE 1TÓPICO 332
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
A solução ótima é o ponto de intersecção das retas de equações:
Assim, para o PL4 temos: x1 = 1, x2 = 4 e Z = 6 • 1 + 11 • 4 = 6 + 44 = 50.
Vamos organizar novamente todo o trabalho em um diagrama.
Comparando as soluções dos PPLs, criados a partir do PPL original (PL0) temos, nesse 
caso, duas possíveis soluções (Z = 55, no PL3 e z = 50, no PL4).
Como nosso objetivo é encontrar o valor máximo para Z, obedecendo às restrições, 
obviamente devemos concluir que:
max Z = 6x1 + 11x2
UNIDADE 1 TÓPICO 3 33
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Sujeito à
5x1 + 3x2 ≤ 17
x1 , x2 ≥ 0 e inteiro
E o PPL tem como solução ótima: x*1 = 0, x*2 = 5 e Z* = 55.
3.1 CONSIDERAÇÕES SOBRE O MÉTODO 
DE BRANCH AND BOUND
Esse método de resolução para problemas de Programação Linear Inteira (PLI) trabalha 
em dois momentos:
•	Ramificação: 
Resolve-se o PPL buscando valores inteiros para as variáveis. Caso não os encontre, 
ramifica-se o PPL em dois novos, atribuindo a cada um deles novas restrições, delimitando 
novos conjuntos de soluções compatíveis, eliminando a possibilidade de reencontrar os valores 
que originaram a ramificação. 
O processo de ramificação continua até que:
•	Encontramos um PPL sem solução;
•	Encontramos as soluções de todos os PPLs ramificados que obedeça a restrição quanto 
ao tipo de variável (inteira).
•	Limite: 
Ao encontrar um ramo do PPL que apresente solução compatível (inteira), define-se o 
valor de Z desse ramo do PPL como o Limite Inferior. Qualquer ramo que apresente solução 
(inteira ou não) menor que o limite inferior é imediatamente eliminado (poupando trabalho).
As ramificações continuam nos PPLs que tenham soluções não inteiras cujo valor de Z 
seja maior que o limite inferior. Se um PPL apresentar uma solução inteira maior que o Limite 
inferior, então esse valor de Z passa a ser o novo Limite Inferior, e o PPL que fazia esse papel 
anteriormente também é eliminado, assim como todos os ramos que tenham solução menor 
que o novo limite inferior.
Fazemos esse procedimento até que se eliminem todos os ramos sem solução ou com 
solução menor que o Limite Inferior, e esse limite é a solução ótima do PPL original.
UNIDADE 1TÓPICO 334
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Vamos, novamente, analisar nosso PPL de exemplo:
O PPL original (PL0) não tem solução inteira e foi ramificado em:
•	PL1 que também não tem solução inteira (mas tem solução);
•	PL2 que não tem solução e por isso é eliminado.
O PL1 é ramificado em:
PL3 que tem solução inteira (x1 = 0 e x2 = 5) definindo o limite inferior Z = 55.
PL4 que tem solução inteira (x1 = 1 e x2 = 4), mas seu valor Z = 50 é menor que o limite 
inferior, portanto, também é eliminado.
Como não há mais necessidade de ramificar o PL3, este traz a solução ótima para o 
PL0, dada pelo limite inferior Z* = 55.
4 APLICAÇÃO DE PLI
Um técnico em eletrônica produz dois tipos de componentes eletrônicos. Ele dispõe de 6 
capacitores, usados na produção, e de 9 horas de trabalho. O componente do tipo 1 necessita 
de 2 capacitores e 2 horas de trabalho para ser produzido, enquanto que o componente do 
tipo 2 necessita apenas 1 capacitor, mas de 3 horas de trabalho para sua produção. Esse 
técnico vende seus componentes eletrônicos ganhando três reais pela venda de uma unidade 
do componente do tipo 1 e quatro reais pela venda de uma unidade do componente do tipo 2. 
Quantos componentes de cada tipo ele deve produzir de modo a obter o maior lucro possível 
com a venda?
Vamos ao modelo:
•	Variáveis de decisão:
x1 – unidade a produzir do componente tipo 1
x2 – unidade a produzir do componente tipo 2
•	Função Objetivo:
Deve-se buscar o máximo lucro com a venda, logo, max L.
UNIDADE 1 TÓPICO 3 35
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
AUT
OAT
IVID
ADE �
Os ganhos são de três reais para cada x1 e mais quatro reais para cada x 2. Podemos representar 
por 3x1 + 4x2.
Assim, a função objetivo é dada por Max L = 3x1 + 4x2.
•	Restrições:
Quanto ao material utilizado: 2 capacitores para cada x1 e 1 capacitor para cada x2, não 
excedendo ao limite de 6 capacitores. Portanto, 2x1 + x2 ≤ 6.
Quanto ao tempo: 2 horas para cada x1 e 3 horas para cada x2, não excedendo ao limite de 9 
horas. Portanto, 2x1 + 3x2 ≤ 9.
Não negatividade: Não há como produzir quantidades negativas de x1 e x2, então x1 ≥ 0 
e x2 ≥ 0.
Integralidade: Não há ganho na venda de componentes inacabados, logo esse deverão ser 
produzidos em unidades inteiras. Assim, x 1 inteiro e x2 inteiro.
Nosso modelo de PLI fica:
Max L = 3x1 + 4x2.
Sujeito a
2x1 + x2 ≤ 6
2x1 + 3x2 ≤ 9
x1 , x2 ≥ 0 e inteiros
Por ser um problema de apenas duas variáveis (x1 e x2), a solução pode ser 
através do método gráfico. Como o espaço em nosso caderno é reduzido, 
fica ao seu encargo fazer os gráficos para a verificação das soluções.
Ao resolver o PLI (agora PL0), graficamente chegamos à solução x1 = 2,55 e x2 = 1,5, 
com L = 12,75. Mas x1 e x2 não são inteiros, então devemos ramificar o PL0 em dois novos. 
Nesse caso escolhendo entre uma das variáveis para criar a nova restrição dos PPLs. Optamos 
por x2, e usando 1 ≤ x2 ≤ 2, criamos PL1 e PL2.
UNIDADE 1TÓPICO 336
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
UNI
Um critério de escolha para decidir quevariável usar na criação das 
novas restrições é usar a variável que possui valor mais “longe” de um 
número inteiro. No nosso caso, x2. 
Nos dois casos a solução (x1, x2) não é inteira e devem-se criar ramificações a partir dos 
dois PPLs. Vamos começar ramificando o PL2 (L = 12,5) por apresentar uma solução melhor 
que o PL1 (L = 11,5). A ramificação a partir do PL2 gera PL3, com a restrição x1 ≤ 1, e PL4, com 
a restrição x1 ≥ 2, criadas com base no fato de que 1 ≤ x1 ≤ 2 no PL2.
UNIDADE 1 TÓPICO 3 37
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
UNI
Perceba que a restrição de não negatividade do PL4 é redundante já 
que temos x1 ≥ 2 e x2 ≥ 2.
Novamente, deve-se resolver os dois PPLs, e as soluções são:
•	Para o PL3: x1 = 1, x2 = 2,33 e L = 12,33.
•	Para o PL4: Não há solução. (Tente usar os valores mínimos x1 = 2 e x2 = 2 na 2ª restrição 
do PL4 para certificar-se dessa afirmação.)
Eliminando o PL4, podemos escolher entre ramificar o PL1 ou o PL3. Escolhemos esse 
último por ter o maior valor para L (que não é o Limite Inferior).
No PL3, usamos 2 ≤ x2 ≤ 3 para criar PL5 com a restrição x2 ≤ 2 e o PL6 com a restrição 
x2 ≥ 3.
Comparando as soluções encontradas (que são inteiras), podemos definir 12 como o Limite 
Inferior para os ramos do PPL e todos os ramos que têm solução menor que 12 são eliminados. 
Vamos analisar o diagrama de soluções encontradas até agora e verificar o que resta 
no PPL para que se possa encontrar a solução ótima.
UNIDADE 1TÓPICO 338
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
No diagrama vemos que:
•	PL4 é eliminado, pois não tem solução.
•	PL6 é definido como Limite Inferior, pois apresenta a maior solução inteira (L = 12).
•	PL1 e PL5 são eliminados, pois apresentam soluções menores que o Limite Inferior.
•	PL6 define a solução ótima do PPL, pois é o único ramo restante e apresenta a solução 
compatível com as restrições.
Assim, fica definida a solução ótima do problema como x*1 = 0 , x*2 = 3 e L* = 12, o 
que pode ser interpretado da seguinte forma: O técnico em eletrônica deve produzir apenas 
o componente do tipo 2, pois vendendo três unidades desse produto seu lucro será de doze 
reais.
UNIDADE 1 TÓPICO 3 39
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
4.1 CONSIDERAÇÕES FINAIS SOBRE A PLI
Como vimos no início dos estudos sobre PLI, a solução pode ser encontrada pelo 
arredondamento do PPL, sem levar em conta a restrição de integralidade. Mas essa técnica 
acarreta em uma série de dificuldades.
Vamos relembrar a primeira solução encontrada no PPL do exemplo de aplicação, em que 
tínhamos x1 = 2,25 e x2 = 1,5. Desrespeitando os acordos matemáticos para arredondamentos, 
poderíamos arredondar os valores das soluções encontrando quatro pares de soluções: x1 = 2 
e x2 = 1, x1 = 2 e x2 = 2, x1 = 3 e x2 = 1 e, por último, x1 = 3 e x2 = 2. Dessas soluções, apenas 
encontra-se dentro da região de soluções compatíveis o par x1 = 2 e x2 = 1, que nos traz L = 
10. Comparando esse valor com a solução ótima encontrada através do Método de Branch 
and Bound, em que L = 12, temos uma variação de, aproximadamente, 16% na solução ótima 
do PPL. Por mais esse motivo, é interessante perceber a necessidade de utilizar os algoritmos 
corretamente para que se possa chegar às melhores conclusões.
LEITURA COMPLEMENTAR
SOBRE A DEFINIÇÃO DE UM PROBLEMA DE PESQUISA 
OPERACIONAL E A COLETA DE DADOS
Frederick S. Hillier e Gerald J. Liebermann
A maioria dos problemas práticos enfrentados pelas equipes de PO é inicialmente descrita 
a eles de uma forma vaga e imprecisa. Consequentemente, a primeira ordem do dia é estudar o 
sistema relevante de e desenvolver um enunciado bem-definido do problema a ser considerado. 
Isso abrange determinar coisas como os objetivos apropriados, restrições sobre o que pode ser 
feito, relação entre a área a ser estudada e outras áreas da organização, possíveis caminhos 
alternativos, limites de tempo para tomada de decisão e assim por diante. Esse processo de 
definição de problema é crucial, pois afeta enormemente quão relevantes serão as conclusões 
do estudo. É difícil obter uma resposta “correta” a partir de um problema “incorreto”!
A primeira coisa a ser reconhecida é que uma equipe de PO normalmente trabalha na 
qualidade de consultores. Aos membros da equipe não somente é apresentado um problema 
e solicitado a resolvê-lo conforme julguem apropriado. Em vez disso, eles aconselham a 
gerência (geralmente um tomador de decisões importante). A equipe realiza uma análise técnica 
detalhada do problema e a seguir apresenta recomendações à gerência. Frequentemente, o 
relatório à gerência identificará uma serie de alternativas particularmente atrativas de acordo 
com diversas suposições ou segundo um intervalo de valores diferente de algum parâmetro da 
política adotada que pode ser avaliado somente pela a gerência (por exemplo, o conflito entre 
UNIDADE 1TÓPICO 340
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
custos e benefício). A gerência avalia o estudo e suas recomendações, leva em consideração 
uma série de fatores intangíveis e toma a decisão final baseada em seu melhor julgamento. 
Consequentemente, é vital para a equipe de PO sintonizar-se com a gerência e obter o seu 
apoio ao longo do projeto.
Determinar os objetivos apropriados é um aspecto muito importante na definição de 
um problema. Para tanto, é necessário, primeiramente, identificar o membro (ou membros) da 
gerência que efetivamente decidirá(ão) no que se refere ao sistema em estudo e, depois sondar 
o pensamento desse(s) indivíduo(s) no que tange aos objetivos pertinentes (envolver o tomador 
de decisões desde o princípio é essencial para obter seu apoio à implementação do estudo).
Em razão de sua natureza, a PO se preocupa com o bem-estar de toda a organização e 
não apenas com aquele de certos membros da organização. Um estudo de PO busca soluções 
que são ótimas para a organização subotimizadas que são boas apenas para um membro. 
Portanto, os objetivos que são formulados idealmente devem ser aqueles de toda a organização. 
Entretanto, isso nem sempre é conveniente. Muitos problemas referem-se primariamente 
apenas a uma porção da organização, de forma que a análise passaria a ser incontrolável caso 
os objetivos declarados fossem muito genéricos e se fosse dada consideração categórica a 
rodos os efeitos colaterais no restante da organização. Em vez disso, os objetivos usados no 
estudo devem ser os mais específicos possíveis e, ao mesmo tempo, englobar os principais 
objetivos do tomador de decisões e manter um grau de consistência razoável com objetivos 
mais altos da organização.
Para organizações com fins lucrativos, uma abordagem possível para contornar o 
problema de subotimização é usar a maximização de lucros no logo prazo (levando-se em 
conta o valor do dinheiro no tempo) como o único objetivo. A qualificação no longo prazo 
indica que esse objetivo fornece a flexibilidade de considerar atividades que não se traduzem 
imediatamente em lucros, por exemplo, projetos de pesquisa e desenvolvimento, mas precisam 
fazê-lo com o tempo de modo a valer a pena. Essa abordagem tem seus méritos. Esse 
objetivo é suficientemente especifico para ser usado de forma conveniente e ainda assim ser 
suficientemente abrangente para abarcar o objetivo básico das organizações que visam ao 
lucro. De fato, algumas pessoas acreditam que todos os demais objetivos legítimos podem 
ser traduzidos nesse único.
Entretanto, na prática, muitas organizações com fins lucrativos não adotam esse enfoque. 
Uma série de estudos de corporações norte-americana revela que a gerência tende a adotar 
o objetivo de lucros satisfatórios, combinados com outros objetivos, em vez de focalizarna 
maximização de lucros no longo prazo. Tipicamente, alguns desses outros objetivos podem ser 
o de manter lucros estáveis, aumentar (ou manter) a fatia de mercado, propiciar a diversificação 
de produtos, manter preços estáveis, levantar o moral dos trabalhadores, manter o controle 
familiar do negócio e aumentar o prestígio da companhia. Completando-se esses objetivos, 
pode ser que se alcance a maximização, porém o inter-relacionamento pode ser suficientemente 
UNIDADE 1 TÓPICO 3 41
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
obscuro para não ser conveniente incorporar todos eles nesse único objetivo. 
Além disso, há considerações adicionais envolvendo responsabilidades sociais que são 
distintas do motivo lucro. As cinco partes, geralmente afetadas por uma empresa comercial 
localizada em um único país são: (1) os proprietários (acionistas etc.) que desejam lucros 
(dividendos, valorização das ações e assim por diante); (2) os empregados, que desejam emprego 
estável com salários razoáveis; (3) os clientes, que desejam um produto confiável a preços 
razoáveis; (4) os fornecedores, que desejam integridade e um preço de venda razoável para 
suas mercadorias; e (5) o governo e, consequentemente, a nação, que desejam o pagamento 
de impostos razoáveis e consideração pelo interesse nacional. Todas as cincos partes dão 
contribuições essenciais para a empresa e essa não deve ser vista como um servidor exclusivo 
de qualquer uma das partes para exploração das demais. Pelo mesmo critério, corporações 
internacionais assumem obrigações adicionais para seguirem práticas socialmente responsáveis. 
Portanto, mesmo que a principal responsabilidade da gerência seja a de gerar lucros (o que, 
em ultima instância, acabará beneficiando as cinco partes envolvidas), percebemos que suas 
responsabilidades sociais mais amplas também devam ser reconhecidas.
As equipes de PO tipicamente investem uma quantidade de tempo surpreendentemente 
grande coletando dados relevantes sobre o problema. Grande parte dos dados normalmente 
é necessário tanto para se obter o entendimento preciso sobre o problema como também 
para fornecer a entrada necessária para o modelo matemático que está sendo formulado na 
próxima fase do estudo. Frequentemente, grande parte dos dados necessários não estará 
disponível quando se inicia o estudo, seja porque as informações jamais foram guardadas, 
seja pelo fato de o que foi registrado se encontrar desatualizado ou, então, na forma incorreta. 
Consequentemente, às vezes, normalmente é necessário instalar um sistema de informações 
gerenciais baseados em computadores para coletar regularmente os dados necessários e no 
formato desejado. A equipe de PO, em geral, precisa obter o apoio de diversos outros indivíduos-
chave da organização para conseguir todos os dados vitais. Mesmo com esse empenho, 
grande parte dos dados pode ser relativamente “frágil”, isto é, estimativas grosseiras baseadas 
apenas em conjeturas. Tipicamente, uma equipe de PO despenderá um tempo considerável 
tentando melhorar a precisão dos dados para depois se adequar e trabalhar com o que de 
melhor possível possa ser obtido.
Com a ampla difusão do emprego de banco de dados e o crescimento explosivo m seus 
tamanhos em anos recentes, as equipes de PO agora frequentemente acham que o maior 
problema relativo a dados não são aqueles pouco disponíveis, mas sim o fato de haver dados 
particularmente relevantes e identificar os padrões de interesse nesses dados torna-se uma 
tarefa assustadora. Uma das ferramentas mais novas para as equipes de PO é uma técnica 
chamada data mining que atende a essa tarefa. Os métodos de data mining pesquisam grandes 
bancos de dados na busca de padrões de interesse que possam levar a decisões úteis.
 
Um estudo de uma equipe de PO realizado para o Departamento de Polícia de São 
UNIDADE 1TÓPICO 342
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Francisco, Califórnia – USA, resultou no desenvolvimento de um sistema computadorizado 
para a escala e emprego de patrulheiros. O novo sistema gerou uma economia anual de US$ 
11 milhões e um aumento de US$ 3 milhões em receitas por multas de trânsito e melhoria 
em 20% em tempos de respostas. Ao avaliar os objetivos apropriados para esse estudo, três 
objetivos foram identificados:
1. Manter alto nível de segurança para o cidadão.
2. Manter o moral da tropa elevado.
3. Minimizar o custo de operações.
 
Para satisfazer o primeiro objetivo, o Departamento de Polícia e o governo municipal 
estabeleceram conjuntamente um nível de proteção desejado. O modelo matemático propôs 
então a necessidade de que esse nível de proteção fosse atingido. De modo semelhante, 
o modelo impôs a exigência de equilibrar a carga de trabalho entre os policiais de modo a 
trabalhar rumo ao segundo objetivo. Finalmente, o terceiro objetivo foi incorporado adotando 
o objetivo de longo prazo de minimizar o número de policiais necessários para atender esses 
dois primeiros objetivos.
FONTE: HILLIER, Frederick S.; LIEBERMANN, Gerald J. Introdução à pesquisa operacional. São 
Paulo: McGraw-Hill, 2006. p. 8.
UNIDADE 1 TÓPICO 3 43
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
Neste tópico, você viu que:
	Um PPLI é um problema de Programação Linear em que uma ou mais variáveis pode ser 
apenas números inteiros.
	Resolve-se o PPL sem se preocupar com essa restrição.
	Caso as soluções encontradas não sejam inteiras, ramifica-se o PPL em dois novos, atribuindo 
a cada um deles novas restrições.
	O processo de ramificação continua até que:
	Encontramos um PPL sem solução;
	Encontramos as soluções de todos os PPLs ramificados que obedeçam a restrição quanto 
ao tipo de variável (inteira).
	Ao encontrar um ramo do PPL que apresente solução compatível (inteira), define-se o valor 
de Z desse ramo do PPL como o Limite Inferior. Qualquer ramo que apresente solução (inteira 
ou não) menor que o limite inferior é imediatamente eliminado (poupando trabalho).
	As ramificações continuam nos PPLs que tenham soluções não inteiras onde o valor de Z 
seja maior que o limite inferior. 
	Se um PPL apresentar uma solução inteira maior que o Limite inferior, então esse valor de 
Z passa a ser o novo Limite Inferior, e o PPL que fazia esse papel anteriormente também 
é eliminado, assim como todos os ramos que tenham solução menor que o novo limite 
inferior.
	Fazemos esse procedimento até que se eliminem todos os ramos sem solução ou com 
solução menor que o Limite Inferior, e esse limite é a solução ótima do PPL original.
RESUMO DO TÓPICO 3
UNIDADE 1TÓPICO 344
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
AUT
OAT
IVID
ADE �
1 Modele e resolva o problema de PLI:
Uma fábrica de cristais procura planejar a produção de dois tipos de produtos 
de modo a maximizar seu lucro. Essa fábrica possui um forno para a fabricação de 
cristais que pode operar no máximo 16 horas por dia. Nesse forno, são produzidos dois 
produtos: um elefante de cristal, que precisa de 15 minutos de forno para ficar pronto, 
e uma borboleta de cristal, que precisa de 25 minutos para ficar pronta. Cada elefante 
é vendido por R$ 12,00 e a borboleta é vendida por R$ 15,00. Quanto de cada produto 
essa fábrica deve produzir num dia de trabalho?
2 Segundo Loesch e Hein (1999, p. 146), encontre a solução ótima dos problemas de 
PLI:
a) MaxZ = 7x1 + 5x2
Sujeito a
–2x1 + x2 ≤ 2
10x1 + 6x2 ≤ 60
6x1 + 10x2 ≤ 60
x1 ≤ 5
x1 , x2 ≥ 0
x1 e x2 inteiros.
b) MinZ = 4x1 + 3x2
Sujeito a
8x1 +3 x2 ≤ 24
5x1 + 6x2 ≤ 30
x1 + 2x2 ≤ 8
x1 , x2 ≥ 0
x1 e x2 inteiros.
UNIDADE 1 TÓPICO 3 45
P
E
S
Q
U
I
S
A
 
O
P
E
R
A
C
I
O
N
A
L
AVAL
IAÇÃ
O
Prezado(a)