Pesquisa Operacional

Prévia do material em texto

2009
Pesquisa OPeraciOnal
Prof. Paulo Afonso Lunardelli
Prof. Roy Wilhelm Probst
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
Impresso por:
III
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
IV
Você já me conhece das outras disciplinas? Não? É calouro? Enfim, tanto para 
você que está chegando agora à UNIASSELVI quanto para você que já é veterano, há 
novidades em nosso material.
Na Educação a Distância, o livro impresso, entregue a todos os acadêmicos desde 2005, é 
o material base da disciplina. A partir de 2017, nossos livros estão de visual novo, com um 
formato mais prático, que cabe na bolsa e facilita a leitura. 
O conteúdo continua na íntegra, mas a estrutura interna foi aperfeiçoada com nova 
diagramação no texto, aproveitando ao máximo o espaço da página, o que também 
contribui para diminuir a extração de árvores para produção de folhas de papel, por exemplo.
Assim, a UNIASSELVI, preocupando-se com o impacto de nossas ações sobre o ambiente, 
apresenta também este livro no formato digital. Assim, você, acadêmico, tem a possibilidade 
de estudá-lo com versatilidade nas telas do celular, tablet ou computador. 
 
Eu mesmo, UNI, ganhei um novo layout, você me verá frequentemente e surgirei para 
apresentar dicas de vídeos e outras fontes de conhecimento que complementam o assunto 
em questão. 
Todos esses ajustes foram pensados a partir de relatos que recebemos nas pesquisas 
institucionais sobre os materiais impressos, para que você, nossa maior prioridade, possa 
continuar seus estudos com um material de qualidade.
Aproveito o momento para convidá-lo para um bate-papo sobre o Exame Nacional de 
Desempenho de Estudantes – ENADE. 
 
Bons estudos!
NOTA
Olá acadêmico! Para melhorar a qualidade dos 
materiais ofertados a você e dinamizar ainda mais 
os seus estudos, a Uniasselvi disponibiliza materiais 
que possuem o código QR Code, que é um código 
que permite que você acesse um conteúdo interativo 
relacionado ao tema que você está estudando. Para 
utilizar essa ferramenta, acesse as lojas de aplicativos 
e baixe um leitor de QR Code. Depois, é só aproveitar 
mais essa facilidade para aprimorar seus estudos!
UNI
V
VI
VII
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.................................334 APLICAÇÃO DE PLI ..........................................................................................................................34
4.1 CONSIDERAÇÕES FINAIS SOBRE A PLI ................................................................................39
LEITURA COMPLEMENTAR .............................................................................................................40
RESUMO DO TÓPICO 3......................................................................................................................44
AUTOATIVIDADE ...............................................................................................................................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 ....................................................................................................50
2.3 VARIÁVEIS DE FOLGA ...............................................................................................................51
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
sumáriO
VIII
4.1 DEGENERESCÊNCIA...................................................................................................................67
4.2 MÉTODO DAS DUAS FASES ......................................................................................................68
5 DUALIDADE .......................................................................................................................................73
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
UNIDADE 3 - PROGRAMAÇÃO DE PROJETOS ..........................................................................93
TÓPICO 1 - ANÁLISE DE REDES......................................................................................................95
1 INTRODUÇÃO ...................................................................................................................................95
2 TEORIA DOS GRAFOS ....................................................................................................................95
2.1 O PROBLEMA DO CAIXEIRO VIAJANTE ...............................................................................97
2.2 PROBLEMAS DE FLUXO MÁXIMO ..........................................................................................100
2.3 PROBLEMAS DE CAMINHO MAIS CURTO ...........................................................................102
RESUMO DO TÓPICO 1......................................................................................................................108
AUTOATIVIDADE ...............................................................................................................................109
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 .........................................................................118
RESUMO DO TÓPICO 2......................................................................................................................121
AUTOATIVIDADE ...............................................................................................................................122
TÓPICO 3 - SIMULAÇÃO ...................................................................................................................125
1 INTRODUÇÃO ...................................................................................................................................125
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
REFERÊNCIAS .......................................................................................................................................137
1
UNIDADE 1
PROGRAMAÇÃO LINEAR
OBJETIVOS DE APRENDIZAGEM
PLANO DE ESTUDOS
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çõesde 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.
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.
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
2
3
TÓPICO 1
UNIDADE 1
PROBLEMAS DE 
PROGRAMAÇÃO LINEAR
1 INTRODUÇÃO
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 processo que 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.).
Deve-se tomar o cuidado para que todas as relações do PPL sejam, realmente, 
lineares.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
4
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 for definir a quantidade 
de operários necessários a otimizar certa produção, não há sentido em declarar 
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
5
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 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.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
6
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
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 
especificidadesdo 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;
XP=quantidade de Prateleiras que a fábrica deve produzir.
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 -
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
7
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 2m de 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 1 | PROGRAMAÇÃO LINEAR
8
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-se de que não há medidas 
negativas para terras. Vamos detalhar cada restrição:
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
9
• 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 1 | PROGRAMAÇÃO LINEAR
10
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 a ser 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.
• Restrição quanto ao consumo de vitamina D: Da mesma forma, 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
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
11
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.
Vamos à modelagem do problema.
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
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.
UNI
UNIDADE 1 | PROGRAMAÇÃO LINEAR
12
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 à 
TÓPICO 1 | PROBLEMAS DE PROGRAMAÇÃO LINEAR
13
14
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.
15
AUTOATIVIDADE
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) C o n s u m o 
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 10 12 8 0,8 65
Tipo III 5 4 3 0,6 30
Disponibilidade 4800 4000 3600 480 -
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:
16
(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.
17
TÓPICO 2
SOLUÇÃO GRÁFICA DE PROBLEMAS 
DE PROGRAMAÇÃO LINEAR
UNIDADE 1
1 INTRODUÇÃO
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 1 | PROGRAMAÇÃO LINEAR
18
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 x
T
 E x
M
FIGURA 2 - PLANO CARTESIANO COM A RESTRIÇÃO x
T
 + x
M 
≤ 50
Região onde
x1 + x2 ≤ 50
x
1 + x
2 = 50
50
50
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
19
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 3x
T
 + 2x
M
 ≤ 120
FIGURA 4 - PLANO CARTESIANO COM A REGIÃO DE INTERSECÇÃO DAS 
RESTRIÇÕES x
T
 + x
M
 ≤ 50 E 3x
T
 + 2x
M
 ≤ 120
Região onde
3x1 + 2x2 ≤ 120
3x
1 + 2x
2 = 120
40
60
Região onde
3x1 + 2x2 ≤ 120 e x1 + x2 ≤ 50
x
1 + x
2 = 50
3x
1 + 2x
2 = 120
40 60
60
50
UNIDADE 1 | PROGRAMAÇÃO LINEAR
20
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
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
21
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 1 | PROGRAMAÇÃO LINEAR
22
Em nosso exemplo, a reta definida pelo esquadro determina um único 
ponto que fornece o máximo lucro paraa 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.
TÓPICO 2 | SOLUÇÃO GRÁFICA DE PROBLEMAS DE PROGRAMAÇÃO LINEAR
23
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!
24
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.
25
AUTOATIVIDADE
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.
26
27
TÓPICO 3
PROGRAMAÇÃO LINEAR INTEIRA
UNIDADE 1
1 INTRODUÇÃO
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 1 | PROGRAMAÇÃO LINEAR
28
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 
FIGURA 8 - SOLUÇÃO GRÁFICA DO PPL DE EXEMPLO
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
29
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 ramificado em:
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.
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.
UNIDADE 1 | PROGRAMAÇÃO LINEAR
30
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, vistoque 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 PL
1
 COM AS SUAS RESTRIÇÕES
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
31
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 PL
4
 COM SUAS RESTRIÇÕES E O VETOR GRADIENTE
UNIDADE 1 | PROGRAMAÇÃO LINEAR
32
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
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
33
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.
34
UNIDADE 1 | PROGRAMAÇÃO LINEAR
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.
Os ganhos são de três reais para cada x1 e mais quatro reais para cada x 2. 
Podemos representar por 3x1 + 4x2.
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
35
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
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.
AUTOATIVIDADE
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.
36
UNIDADE 1 | PROGRAMAÇÃO LINEAR
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.
Um critério de escolha para decidir que variá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, x
2
. 
UNI
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
37
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. 
Perceba quea restrição de não negatividade do PL
4
 é redundante já que temos 
x
1
 ≥ 2 e x
2
 ≥ 2.
UNI
38
UNIDADE 1 | PROGRAMAÇÃO LINEAR
No diagrama vemos que:
• PL4 é eliminado, pois não tem solução.
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.
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
39
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.
• 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.
40
UNIDADE 1 | PROGRAMAÇÃO LINEAR
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 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 
LEITURA COMPLEMENTAR
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
41
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 focalizar na 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 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, mesmoque 
42
UNIDADE 1 | PROGRAMAÇÃO LINEAR
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 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.
 
TÓPICO 3 | PROGRAMAÇÃO LINEAR INTEIRA
43
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.
44
RESUMO DO TÓPICO 3
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.
45
AUTOATIVIDADE
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.
46
47
UNIDADE 2
SOLUÇÃO ÓTIMA
OBJETIVOS DE APRENDIZAGEM
PLANO DE ESTUDOS
A partir desta unidade, você estará apto(a) a:
• escrever um PPL na sua forma normal;
• representar um PPL no tableau Simplex;
• encontrar a solução ótima de um PPL através do método Simplex e do 
método das duas fases;
• encontrar o problema dual de um problema primal;
• representar um PPL no Microsoft Excel;
• encontrar a solução ótima de um PPL através do Solver;
• realizar a análise de pós-otimalidade de um PPL.
Esta unidade está dividida em dois tópicos. No final de cada um deles, você 
encontrará atividades que reforçarão o seu aprendizado.
TÓPICO 1 – MÉTODO SIMPLEX
TÓPICO 2 – UTILIZAÇÃO DO COMPUTADOR
48
49
TÓPICO 1
MÉTODO SIMPLEX
UNIDADE 2
1 INTRODUÇÃO
O Simplex é um método de resolução de problemas de Programação 
Linear que se baseia em operações matriciais na busca da solução ótima. Esse 
método utiliza-se de uma solução conhecida no PPL para encontrar as principais 
soluções compatíveis do problema, determinando a maior dentre elas, em 
problemas de maximização, ou a menor dentre as soluções compatíveis, em 
problemas de minimização.
A aplicação do método Simplex se dá através de um quadro específico 
que contém as informações necessárias à resolução. Seguindo uma sequência de 
procedimentos padrão, já definidos, a solução ótima e os valores das variáveis 
de decisão são determinados facilmente. Mas, para isso, é necessário que o 
modelo do PPL esteja escrito de uma maneira especial, chamada de Forma 
Padrão do PPL.
2 FORMA PADRÃO DO PPL
A fim de trabalhar com os modelos de PLs utilizando o Método Simplex, 
precisaremos reescrevê-los em sua forma padrão, obedecendo alguns critérios. 
Essa forma padrão visa organizar os modelos de PL de uma mesma forma, 
facilitando os cálculos nos quadros do Método Simplex, minimizando o tempo de 
busca pela solução ótima do PPL.
Para escrever um modelo de PPL em sua forma padrão devemos:
1. fazer com que os coeficientes da mão direita sejam números não negativos;
2. restringir todas as variáveis de decisão não restritas;
3. substituir as restrições definidas por ≤ usando variáveis de folga;
4. substituir as