PESQUISA OPERACIONAL Exercícios de apoio

Prévia do material em texto

1 
 
 
 
 
 
PESQUISA OPERACIONAL 
 
 
Autor: Prof. Dr. Arturo Alejandro Zavala Zavala 
 
Professor do quadro efetivo da Universidade Federal de Mato Grosso - Faculdade de 
Economia. 
 
Especialista em Estatística Econômica, Modelos de Regressão, Series Temporais, 
Pesquisa Operacional e Econometria. 
2 
 
 
 
 
Caros Alunos, 
Na administração, economia e outras áreas das ciências, precisam de modelos 
matemáticos com a finalidade de otimizar problemas e desta forma descobrir a 
combinação perfeita de variáveis que façam ótimas nossas necessidades. 
Este trabalho foi escrito com o intuito de apresentar ao aluno de Economia e em geral 
a os alunos da área social, elementos da pesquisa operacional com a finalidade de 
encontrar subsídios necessários para entender a modelagem e estabelecer pontos de 
decisão que podem ser útil a formadores de opiniões em suas decisões. 
Este trabalho apresenta 5 Capítulos, sendo a introdução a pesquisa operacional, a 
solução de problemas em pesquisa operacional, um estudo de analise da sensibilidade, 
modelo de transporte e problemas de programação inteira. Estes capítulos pretendem 
dar bases suficientes para que o aluno se inicie na área de programação matemática. 
A pesquisa operacional por seu alto conteúdo matemático muitas vezes é rejeitada 
pelos alunos pela suposta complexidade da mesma, mas o presente texto apresenta 
um auxilio adicional que é o software Solver do Excel, ele de uma forma simples 
interpretam a solução a partir de um modelo matemático proposto, o grande 
problema então, na pesquisa operacional é entender o problema e levar a sistema de 
equações que logo poderão ser implementados no Solver. 
 
Convido a vocês a leitura deste trabalho e a sua aplicação. 
 
Abraços e boa leitura. 
 
 
 
 
Arturo A. Z. Zavala 
 
3 
 
Sumário 
 
CAPITULO 1: INTRODUÇÃO À PESQUISA OPERACIONAL 7 
1.1 Modelo Matemático 10 
1.2 Programação Linear 11 
1.3 Exemplos usuais de problemas de Programação Linear 12 
1.4 Construção do modelo de Programação Linear 13 
1.5 Solução Gráfica de Programação Linear 18 
1.6 Analise Gráfico da Sensibilidade 22 
1.7 Exercícios 27 
 
CAPITULO 2: SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO LINEAR PELO MÉTODO SIMPLEX
 35 
2.1 Variável de Folga: 35 
2.2 Variável de Superávit 35 
2.3 Variável não restrita 36 
2.4 Algoritmo SIMPLEX Geral 36 
2.5 EXEMPLO DO USO DO ALGORITMO SIMPLEX 37 
 
CAPITULO 3: ANALISE DE DUALIDADE E DE SENSIBILIDADE 67 
3.1 Dualidade na Programação Linear 67 
3.1.1 Relações entre primal-dual 67 
3.1.2 Exemplos de transformação Primal – Dual 68 
3.1.3 Interpretação Econômica do Problema Dual 70 
3.2 Analise de Sensibilidade 72 
3.2.1 Alteração em um dos coeficientes da função objetivo. 73 
3.2.2 Alteração em um dos coeficientes de uma restrição. 74 
 
CAPITULO 4: Modelo de Transporte 87 
4.1 O Modelo 87 
4.2 Observações 88 
4.3 Exemplos de Problemas de Transporte 88 
4.4 Exercícios 97 
4 
 
 
CAPITULO 5: PROGRAMAÇÃO LINEAR INTEIRA 109 
5.1 Algoritmo Branch-Bound (Ramifica-e-Limita) 109 
5.2 Exemplos de Programação Inteira 110 
5.3 Exercícios 118 
Referências Bibliográficas 128 
Mini Currículo 129 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
5 
 
 
Unidade 1 
6 
 
 
7 
 
CAPITULO 1: INTRODUÇÃO À PESQUISA OPERACIONAL 
 
 
O desenvolvimento da Pesquisa Operacional, segundo muitos autores, esta 
apresentando grandes avanços científicos mais importantes desde os mediados do 
século XX. Na atualidade é uma grande ferramenta que é utilizada pelos diferentes 
campos da administração, economia e da engenharia. 
A Pesquisa Operacional era quase desconhecida antes da Segunda Guerra 
Mundial. O matemático russo Leonid Vitalievitx Kantorovitx, publicou uma extensa 
monografia em 1939, onde apresentou uma ampla gama de problemas de produção e 
distribuição que tinham estruturas matemáticas de álgebra linear, mas a Pesquisa 
Operacional teve um exorbitante desenvolvimento com a chegada da segunda guerra 
mundial, devido à necessidade de organização de informações, maximizar 
rendimentos ou minimizar custos de operação. 
A Pesquisa Operacional tem como base o método científico para pesquisar e ajudar 
na toma de decisões sobre problemas complexos das organizações nos dias de hoje. 
Basicamente a Pesquisa Operacional é construída a partir dos seguintes passos: 
a) A observação de um problema; 
b) A construção de um modelo matemático que apresente elementos essenciais 
do problema; 
c) A obtenção das melhores soluções possíveis com a ajuda de algoritmos exatos 
ou heurísticos (aproximados); 
d) A calibração e interpretação da solução e sua comparação com outros 
métodos. 
Muitas vezes para encontrar alguma solução na toma de decisão recorremos sem 
querer a modelos matemáticos, podendo estas ser simples, mas contendo um 
raciocínio logico em sua concepção. 
Por exemplo, imaginemos que por motivos de trabalho tenhamos que viajar a São 
Paulo, todas as semanas, durante 5 semanas, mas para não deixar nossas obrigações 
em Cuiabá, destinamos nossas tarefas em São Paulo de segunda até quarta feira, 
devendo sair sempre na segunda feira e voltar na quarta feira, deixando a quinta e 
sexta para solucionar problemas em Cuiabá. 
Viajar em avião ida-volta para São Paulo custa em média R$ 400,00. A empresa de 
viagens possibilitou um desconto de 20% se as datas de viagens pegavam fins de 
8 
 
semana, já seja em Cuiabá ou São Paulo. Além disso, uma passagem de ida ou de volta 
custava 75% do preço da viagem de ida-volta para São Paulo. 
Como se poderiam comprar as passagens de forma que se possa estar em São 
Paulo e Cuiabá nos dias de semana considerados, com o mínimo custo possível? 
Para a solução a este problema simples o primeiro que devemos fazer é identificar 
o problema e nos perguntar o seguinte: 
i) Quais são as alternativas de decisão? 
ii) Quais são as restrições de decisão? 
iii) Qual é o objetivo para avaliar as alternativas? 
Comecemos por identificar nossas alternativas de decisão de compra de 
passagem, sendo estas: 
� Comprar 5 passagens Cuiabá – São Paulo – Cuiabá. 
� Comprar uma passagem Cuiabá – São Paulo, quatro passagens São Paulo – 
Cuiabá – São Paulo, as quais permitam que as datas incluam os fins de semana 
em Cuiabá, e uma passagem São Paulo – Cuiabá. 
� Comprar uma passagem Cuiabá – São Paulo – Cuiabá, que considere a segunda 
feira da primeira semana e a quarta feira da ultima semana, e quatro 
passagens São Paulo – Cuiabá – São Paulo, que considerem os finais de semana 
em Cuiabá. 
A restrição para nossa decisão será o fato que para cumprir a tarefa deve sair de 
Cuiabá uma segunda feira e voltar uma quarta feira. 
Uma forma obvia de avaliação das alternativas proposta, será aquele que 
apresente o menor custo possível. 
 
Custo da Alternativa 1: 
 
Como o custo de uma passagem ida-volta para São Paulo é de R$ 400,00. Então 
o custo para as cinco semanas é de 5 x R$ 400,00 = R$ 2.000,00 
Custo da Alternativa 2: 
9 
 
 
Como a passagem só de ida o só de volta corresponde a 75% do preço de ida-
volta, além disso, se as datas contemplam um final de semana teremos um desconto 
de 20% do preço de ida-volta, então temos o seguinte: 
0,75 x R$ 400,00 + 4 x 0,80 x R$ 400,00 + 0,75 x R$ 400,00 = R$ 1.880,00 
 
Custo da Alternativa 3: 
 
 
Para esta ultima alternativa temos que os 5 passagens contemplam o final de 
semana, porem um desconto de 20%do preço de ida-volta será considerada, desta 
forma o custo será 5 x 0,80 x R$ 400,00 = R$ 1.600,00 
Observa-se que a partir disto podemos indicar que a melhor alternativa a ser 
considerada seria a terceira, já que ela apresenta o menor custo possível. 
Outro exemplo se poderia considerar o fato de ter um arame de longitude L cm. 
e se deseja configurar esse pedaço de arame numa forma retangular, de forma que 
seja maximizada a área cercada, qual deveriam ser os lados dessa forma retangular? 
Para isto, podemos imaginar que a forma retangular tem a seguinte estrutura: 
 
Então devido a necessidade de maximizar a área cercada, o modelo 
matemático pode ser definido por: 
 
Sujeito a 
10 
 
 
 
Em termos gerais um modelo matemático para um problema de decisão, 
estaria dado por: 
 
 
 Figura 1. Estrutura de um modelo matemático 
 
Notemos que no exemplo anterior a Função Objetivo estaria dada pela Área 
definida pela letra A, e as restrições estaria dado pelas duas expressões matemáticas. 
 
1.1 Modelo Matemático 
 
Um modelo matemático se pode entender como a representação simplificada da 
realidade, expressada na forma de equações matemáticas que serve para simular a 
realidade. Na pesquisa Operacional este modelo matemático tem alguns componentes 
de interesse: 
 
a) Variáveis de decisão 
b) Função Objetivo 
c) Restrições 
a) Variáveis de decisão: são variáveis utilizadas no modelo que podem ser controladas 
pelo tomador de decisão. 
Exemplo: Número de caminhões que chegam de São Paulo a Cuiabá. 
b) Função Objetivo: É uma função matemática que representa o principal objetivo do 
tomador de decisão. Ele apresenta dois tipos: Maximização (pudendo ser lucro, 
renda, utilidade, etc.) ou Minimização (pudendo ser de custos, perdas, etc.) 
Exemplo: Minimizar os custos de transporte. 
11 
 
c) Restrições: São regras que dizem o que podemos ou não fazer e quais são as 
limitações dos recursos ou atividades que estão associados ao modelo. 
Exemplo: O número total de caminhões despachados pela manhã é menor ou igual 
ao número de motoristas que a empresa tem a disposição no primeiro turno. 
 
1.2 Programação Linear 
 
A programação linear é uma técnica de modelado matemático, desenhada para 
otimizar o uso de recursos limitados. 
Suposições da Programação Linear 
Existem 6 características necessárias nos problemas de programação linear: 
a) Divisibilidade 
b) Linearidade 
c) Aditividade 
d) Proporcionalidade 
e) Certeza 
f) Não Negatividade 
 
a) Divisibilidade: Este suposto indica que as variáveis podem ter valores fraccionários, 
isto é, em essência os valores que tomam as variáveis pertencem aos números 
reais. 
b) Linearidade: Neste caso as expressões algébricas para as variáveis só consideram 
expressões de ordem 1 e não permitem multiplicação entre as variáveis tanto na 
função objetivo, quanto nas restrições implementadas. 
b) Aditividade: Este suposto indica que os relacionamentos entre variáveis são de 
somas e subtrações, nenhuma outra operação além dessas. 
c) Proporcionalidade: Indica que as contribuições de cada variável de decisão são 
proporcionais ao valor da variável de decisão. As contribuições da variável de 
decisão acontecem tanto na função objetivo como no lado esquerdo das restrições. 
d) Certeza: Esta suposição indica que todos os parâmetros utilizados nos modelos são 
conhecidos com certeza. Muitas vezes essa suposição não é verdadeira, para isto, é 
necessário fazer a analise de sensibilidade com a finalidade de atender os 
parâmetros em questão. 
12 
 
e) Não Negatividade: Não Economia, Administração e em geral nas Ciências Sociais, as 
variáveis só aceitam valores positivos, isto é, as soluções se encontram no primeiro 
quadrante. 
 
 
1.3 Exemplos usuais de problemas de Programação Linear 
 
i) Problema do Caminho Mínimo: Seu objetivo é determinar a rota de menor caminho 
(distância, tempo ou custo) existente entre um ponto de origem (cidade, endereço, 
computador, objeto etc.) e um ponto de destino. 
 
ii) Problema de Localização de Facilidades: Seu objetivo é determinar a localização e 
capacidade das facilidades (restaurantes, depósitos, antenas de rádio etc.) de forma 
a suprir a demanda da região toda com um custo mínimo e/ou lucro máximo 
(considerando um determinado período). Cada facilidade possui normalmente um 
custo fixo de instalação e custos variáveis de operação 
 
iii) Problema da Mochila: Seu objetivo consiste em determinar as capacidades 
adequadas de cada compartimento e como esses devem ser carregados, 
maximizando o valor de utilidade total, descontado o custo de incluir 
compartimentos. 
iv) Escolha da Mistura para Rações: Seu objetivo é formular uma ração formada a 
partir da mistura dos grãos que atenda às necessidades mínimas e máximas de 
nutrientes e tenha um custo mínimo. 
 
v) Bin-packing / Cutting Stock: Seu objetivo é determinar a quantidade mínima 
possível de barras para que sejam cortados todos os pedaços necessários para 
suprir a demanda. 
 
vi) Fornecimento de Produtos através de uma Rede de Transportes: Seu objetivo é 
determinar a quantidade do produto que cada fornecedor deve enviar para cada 
depósito, de forma que o custo total do transporte seja mínimo, que cada depósito 
tenha sua demanda atendida, e que nenhum depósito estoure sua capacidade de 
fornecimento. 
 
vii) Problemas de Produção: Seu objetivo é determinar as atividades que devem ser 
realizadas ou produzidas de forma a maximizar o lucro ou minimizar o custo de 
produção, levando-se em conta a quantidade máxima disponível para cada insumo. 
 
viii) O Problema de Designação (caso particular do problema de transporte): Seu 
objetivo é minimizar o custo total para executar um conjunto de tarefas, onde 
13 
 
cada tarefa deve ser executada por uma única máquina, e cada máquina executa 
uma única tarefa. 
 
1.4 Construção do modelo de Programação Linear 
 
Para construir um modelo de programação linear é necessário seguir o modelo 
matemático apresentado na figura 1. 
 
Problema de Produção: Para entender o modelo matemático consideremos o seguinte 
exemplo, imaginemos que exista a empresa de tintas “Bela” que produz tintas para 
interiores e exteriores, ela utiliza para a produção dos dois tipos de tintas, dois tipos de 
matérias primas, digamos T1 e T2. A tabela a seguir proporciona a disponibilidade de 
Matéria Prima e sua utilidade por cada tipo de tinta. 
 
Para Exteriores Para Interiores
Materia Prima T1 6 4 24
Materia Prima T2 1 2 6
Utilidade por Tonelada 
(US$ 1.000,00)
5 4
Toneladas de Materia Prima 
por Tonelada de Pintura
Disponibilidade 
Máxima diaria 
(em Toneladas)
 
 
Uma pesquisa de mercado restringe a demanda máxima diária de pintura para 
interiores a 2 toneladas. Além disso, a demanda diária de pintura para interiores não 
pode exceder a de pintura para exteriores por mais de uma tonelada. 
 
A empresa tintas “Belas” quer determinar a mistura de produto ótima para 
interiores e exteriores de forma que produza a máxima utilidade possível diariamente. 
 
Para estabelecer o modelo matemático apropriado o primeiro que se tem a fazer é 
definir claramente os três elementos da programação linear: 
a) Variáveis 
b) Função Objetivo 
c) Restrições 
 
a) Variáveis: Neste caso estamos frente a duas variáveis. Como a empresa precisa 
determinar as quantidades que se vão a produzir de pinturas para interiores e 
exteriores, as variáveis que se deverão definir são: 
 
X1:= Toneladas diárias produzidas de pintura para exterior 
X2:= Toneladas diárias produzidas de pintura para interior 
 
b) Função Objetivo:Neste caso nossa meta é maximizar a utilidade diária por 
toneladas de pintura, se definimos a Z como a utilidade diária por venda de pinturas 
para interiores ou para exteriores, nosso objetivo, então, pode ser reduzido a: 
14 
 
 
maximizar Z = 5 X1 + 4 X2 
 
c) Restrições: Para as restrições considerarmos todas aquelas que apresentam alguma 
limitação, neste caso a limitação é de disponibilidade máxima de matéria prima. 
Desta forma as restrições são: 
 
i) Emprego de Matéria Prima M1: 
 
6 X1 + 4 X2 ≤ 24 
 
ii) Emprego de Matéria Prima M2: 
 
X1 + 2 X2 ≤ 6 
 
iii) Outra restrição importante esta no fato de que a pintura para interiores não pode 
exceder a pintura para exteriores em 1 tonelada, isto é: 
X2 – X1 ≤ 1 
 
iv) Uma restrição refere-se a demanda máxima diária de pintura para interiores é de 2 
toneladas, isto é: 
X2 ≤ 2 
 
v) Como não é possível produzir valores negativos para ambos tipos de pintura, temos 
a restrição: 
X1, X2 ≥ 0 
 
Desta forma o modelo completo é definido por: 
 
maximizar Z = 5 X1 + 4 X2 
 
Sujeito a 
6 X1 + 4 X2 ≤ 24 
 X1 + 2 X2 ≤ 6 
 X2 – X1 ≤ 1 
 X2 ≤ 2 
 X1, X2 ≥ 0 
 
Problema de Mistura para rações: Outro caso, poderíamos considerar, por exemplo, a 
empresa “Completa”, que utiliza diariamente pelo menos 800 Kgs de alimento 
especial. Este alimento especial é uma mistura de milho e semente de soja com a 
composição seguinte: 
 
15 
 
Proteinas Fibras Custo/Kg
Milho 0,09 0,02 0,30 
Semente de Soja 0,60 0,06 0,90 
Alimento 
Especial
Quantidade de quilos de composto 
por quilo de alimento especial
 
 
Os requerimentos dietéticos diários de alimento especial consideram que pelo 
menos um 30% de proteínas e quanto muito 5% de fibras, devem ser considerados na 
mistura. A empresa “Completa” deseja determinar o custo mínimo diário de mistura 
de alimentos. 
 
Para a solução do presente exercício, precisamos seguir com os passos seguintes: 
 
a) Variáveis: Neste caso estamos frente a dois tipos de variáveis, estas são as que 
conformam o alimento especial, sendo estas: 
 
X1:= Quantidade de quilogramas de milho 
X2:= Quantidade de quilogramas de semente de soja 
 
b) Função Objetivo: Já que nosso interesse é minimizar o custo diário de mistura de 
alimentos, esta pode ser escrita por: 
 
minimizar Z = 0,30 X1 + 0,90 X2 
 
c) Restrições: 
 
i) Conter 800 Kg de alimento especial 
 
X1 + X2 = 800 
 
ii) Disponibilidade da proteína na mistura 
 
0,09 X1 + 0,60 X2 ≥ 30% (X1 + X2) 
 ou seja 
 
 - 0,21 X1 + 0,06 X2 ≥ 0 
 
iii) Disponibilidade de fibra na mistura 
 
0,02 X1 + 0,06 X2 ≤ 5% (X1 + X2) 
 
 ou seja 
 
 0,03 X1 – 0,01 X2 ≥ 0 
 
 
16 
 
iv) Restrição de não negatividade 
 
X1, X2 ≥ 0 
 
Em resumo o modelo pode ser definido por: 
 
minimizar Z = 0,30 X1 + 0,90 X2 
Sujeito a 
X1 + X2 = 800 
 - 0,21 X1 + 0,06 X2 ≥ 0 
 0,03 X1 – 0,01 X2 ≥ 0 
X1, X2 ≥ 0 
 
Problema de Transporte: Uma transportadora utiliza burros e jumentos para 
transportar cargas entre duas cidades. A capacidade de carga de um burro é de até 
100 Kg, enquanto a do jumento é de até 50 Kg. Durante a viagem, um burro consome 3 
montes de capim e 100 litros de água. Um jumento consome 2 montes de capim e 30 
litros de água. A empresa possui várias estações de alimentação intermediárias entre 
as duas cidades. Estas estações dispõem, no momento, de 900 litros de água e 300 
montes de capim. Os burros e jumentos utilizados pela firma são alugados e o preço 
do aluguel é de R$ 30,00 por burro e R$ 20,00 por jumento. Existe no momento uma 
necessidade de transporte de 1.000 Kg. Quantos burros e jumentos devem ser 
utilizados de modo a minimizar o custo do aluguel pago? 
Para a elaboração do modelo matemático devemos considerar: 
 
a) Variáveis: 
X1:= Quantidade de burros para o transporte 
X2:= Quantidade de Jumentos para o transporte 
 
b) Função Objetivo: 
 
minimizar Z = 30 X1 + 20 X2 
 
c) Restrições: 
 
i) Consumo de Capim na viagem 
 
 3 X1 + 2 X2 ≤ 300 
 
ii) Consumo de Água na viagem 
 
 100 X1 + 30 X2 ≤ 900 
 
iii) Necessidade de Transporte 
 
 100 X1 + 50 X2 = 1000 
17 
 
 
iv) Não Negatividade 
 
 X1, X2 ≥ 0 
 
Em forma resumida, temos: 
minimizar Z = 30 X1 + 20 X2 
Sujeito a 
 3 X1 + 2 X2 ≤ 300 
 100 X1 + 30 X2 ≤ 900 
 100 X1 + 50 X2 = 1000 
 X1, X2 ≥ 0 
 
Fornecimento de Produtos através de uma Rede de Transportes: Deseja-se 
transportar arroz de três armazéns (1, 2 e 3) a três centros consumidores distintos (A, 
B e C). Cada armazém apresentou os seguintes níveis de estoque de arroz em 
determinado mês: 
 
Os custos unitários de transporte ($/Kg) envolvidos são os seguintes: 
 
Qual será a quantidade de arroz a ser transportada entre armazém e cada 
centro consumidor, de tal forma que as demandas de cada centro sejam supridas e 
que o custo total de transporte seja mínimo? 
Para encontrar o modelo matemático, precisamos definir o seguinte: 
a) Variáveis: 
X11 = {transportar arroz do armazém 1 ao centro consumidor 1} 
X12 = {transportar arroz do armazém 1 ao centro consumidor 2} 
X13 = {transportar arroz do armazém 1 ao centro consumidor 3} 
X21 = {transportar arroz do armazém 2 ao centro consumidor 1} 
X22 = {transportar arroz do armazém 2 ao centro consumidor 2} 
X23 = {transportar arroz do armazém 2 ao centro consumidor 3} 
X31 = {transportar arroz do armazém 3 ao centro consumidor 1} 
X32 = {transportar arroz do armazém 3 ao centro consumidor 2} 
X33 = {transportar arroz do armazém 3 ao centro consumidor 3} 
18 
 
 
b) Função Objetivo: 
Minimizar Z = 10 X11 + 5 X12 + 12 X13 + 4 X21 + 9 X22 + 15 X23 + 15 X31 + 8 X32 + 6 X33 
c) Restrições: Neste caso existem três tipos de restrições 
� Estoques disponíveis nos armazéns 1, 2 e 3 
X11 + X12 + X31 ≤ 200 
X21 + X22 + X23 ≤ 150 
X31 + X32 + X33 ≤ 300 
 
� Quantidades demandadas nos centros consumidores A,B e C 
X11 + X21 + X31 ≥ 100 
X12 + X22 + X32 ≥ 300 
X13 + X32 + X33 ≥ 250 
 
� Não negatividade 
X11, X12, X13, X21, X22, X23, X31, X32, X33 ≥ 0 
1.5 Solução Gráfica de Programação Linear 
 
Para a solução gráfica o procedimento seguem os seguintes passos: 
 
a) O problema só poderá contemplar duas variáveis a serem avaliados 
b) Disponibilizar todas as retas no gráfico 
c) Identificar a direção das restrições 
d) Identificar o polígono com a região de possíveis soluções 
e) Testar a função objetivo em cada ponto do vértice do polígono 
 
Para a aplicação pratica da solução gráfica podemos considerar os casos seguintes: 
 
Problema de Produção: 
maximizar Z = 5 X1 + 4 X2 
 
Sujeito a 
6 X1 + 4 X2 ≤ 24 
 X1 + 2 X2 ≤ 6 
 X2 – X1 ≤ 1 
 X2 ≤ 2 
 X1, X2 ≥ 0 
 
19 
 
 
Gráfico 1.- Polígono de interseção de restrições do Problema de Produção 
 
 
Como o polígono formado é OABCDE, tendo neste caso 5 vértices possíveis de 
solução, então: 
 
No Ponto A: temos que X1 = 0 e X2 = 1, destaforma o valor que toma a função objetivo 
é: 
 
ZA = 5 (0) + 4 (1) = 4 
 
No ponto B: temos que X2 = 2 e a reta X2 – X1 = 1, desta forma X1 = 1, então estes 
valores permitem obter uma função objetivo igual a: 
 
ZB = 5 (1) + 4 (2) = 13 
 
No ponto C: temos que X2 = 2 e a reta X1 + 2 X2 = 6, desta forma X1 = 2, então estes 
valores permitem obter uma função objetivo igual a: 
 
ZC = 5 (2) + 4 (2) = 18 
 
No ponto D: temos a interseção das retas 6 X1 + 4 X2 = 24 e X1 + 2 X2 = 6, resolvendo o 
sistema de equações formada, temos que X1 = 3 e X2 = 3/2, então na função objetivo: 
 
ZD = 5 (3) + 4 (3/2) = 21 
 
No ponto E: temos que X1 = 4 e X2 = 0, na função objetivo temos: 
 
ZE = 5 (4) + 4 (0) = 20 
 
20 
 
Como nosso interesse é escolher o valor maior dentre os obtidos, podemos 
concluir que a melhor solução se encontra no ponto D, oferecendo esta uma utilidade 
de US$ 21.000,00 dólares pela produção diária de 3 toneladas de pintura para 
exteriores e de 1,5 toneladas diárias de pintura para interiores. 
 
Problema de Mistura para rações: 
 
minimizar Z = 0,30 X1 + 0,90 X2 
 
Sujeito a 
X1 + X2 = 800 
 - 0,21 X1 + 0,06 X2 ≥ 0 
 0,03 X1 – 0,01 X2 ≥ 0 
X1, X2 ≥ 0 
 
 
Gráfico 2.- Polígono de interseção de restrições do Problema de Mistura para Rações 
 
 
A solução ótima se encontra na região sombreada, como desejamos minimizar 
devemos encontrar o menor valor nos vértices do polinômio assim formado. 
 
 
No ponto A: Os valores de X1 e X2 se encontram na fronteira da interseção das retas 
X1+X2=800 e 0,03 X1 – 0,01 X2 = 0, desta forma X1 = 200 e X2 = 600, desta forma o valor 
da função objetivo é: 
 
 
ZA = 0,30 (200) + 0,90 (600) = 600 
 
 
21 
 
No ponto B: Os valores de X1 e X2 se encontram na fronteira da interseção das retas 
X1+X2=800 e -0,21 X1 + 0,30 X2 = 0, desta forma X1 = 470,59 e X2 = 329,41, desta forma 
o valor da função objetivo é: 
 
 
ZB = 0,30 (470,59) + 0,90 (329,41) = 437,65 
 
 
Destas duas soluções encontramos que no ponto B, encontram-se o menor 
valor observado, pelo que podemos dizer que produzir alimento especial será 
necessário de 470,59 Kg de Milho, assim como de 329,41 Kg de sementes de soja, 
tendo desta forma um custo de R$ 437,65 por quilograma produzido de mistura. 
 
 
 
 
Problema de Transporte: 
 
minimizar Z = 30 X1 + 20 X2 
Sujeito a 
 3 X1 + 2 X2 ≤ 300 
 100 X1 + 30 X2 ≤ 900 
 100 X1 + 50 X2 = 1000 
 X1, X2 ≥ 0 
 
 
Gráfico 2.- Polígono de interseção de restrições do Problema de Transporte 
 
 
22 
 
Dadas às restrições colocadas o único ponto com solução possível é o ponto A, este 
ponto tem como pontos a interseção das retas 100 X1 + 30 X2 = 900 e 100 X1 + 50 X2 = 
1000, sendo seus valores X1 = 7,5 e X2 = 5, obtendo a função objetivo seguinte: 
 
ZA = 30 (7,5) + 20 (5) = 325 
 
Pelo que podemos dizer que com um mínimo de 8 burros e 5 jumentos poderemos ter 
um lucro de 340 unidades monetárias. 
 
1.6 Analise Gráfico da Sensibilidade 
 
A análise de sensibilidade se faz porque se supõe que os coeficientes 
encontrados para as varáveis sejam constantes, mas no mundo real quase nunca se 
tem certeza da existência desses valores. Ao mudar os coeficientes pode se encontrar 
o seguinte: 
 
i) Possíveis variações nos coeficientes, não modificam a solução ótima. 
ii) Caso houver alteração significativa o que fazer para encontrar a nova 
solução ótima sem resolver novamente o problema. 
 
A analise de sensibilidade deve responder as seguintes perguntas: 
 
� Qual é o efeito de uma mudança num coeficiente da função objetivo? 
� Qual é o efeito de uma mudança num coeficiente nas restrições do modelo 
matemático? 
� Qual é o efeito de uma mudança na disponibilidade das restrições? 
 
A analise de sensibilidade serve também para estabelecer hipóteses de certeza dos 
coeficientes, assim como a disponibilidade das restrições. 
 
Entre os tipos de analise de sensibilidade a considerar, temos: 
 
a) Estabelece limites inferiores e superiores para todos os coeficientes da função 
objetivo e disponibilidades das restrições. 
b) Verifica se uma ou mais mudanças em um problema alteram a sua solução 
ótima. Esta pode ser feita a través da alteração do problema e sua nova 
resolução. 
 
i) Estudo de Sensibilidade dos coeficientes da função objetivo 
 
Para fazer a analise de sensibilidade consideremos o Problema de Produção. 
 
23 
 
 
Do gráfico acima, observemos os seguintes fatos: 
 
� As três retas pertencem a uma mesma família de retas, pois tem o ponto (3, 
3/2) em comum. 
� A diferencia entre as três retas encontra-se no coeficiente angular. 
� A mudança de um coeficiente da função objetivo causará uma alteração no 
coeficiente angular da função objetivo. 
 
Daqui se entende que desde que o coeficiente angular da função objetivo estiver 
entre as duas retas limites a solução ótima não será alterada. 
 
Em forma geral uma Função Objetivo com duas variáveis pode ser representada 
pela expressão seguinte: 
 
Z = c1 X1 + c2 X2 
 
Então a variável X2 pode ser definido por: 
 
 ... (1) 
 
Desta forma pretenderemos identificar as condições da Função Objetivo, em 
função das mudanças das duas retas que pertencem a família das retas a que 
pertencem a função objetivo, para isto, em ambas retas isolemos o valor de X2 em 
ambas retas. 
 
Na reta 6 X1 + 4 X2 = 24, temos: 
 
 ... (2) 
 
24 
 
Na reta X1 + 2 X2 = 6, temos: 
 
 ... (3) 
 
Das expressões (1), (2) e (3), temos que: 
 
 
 
Considerando que c2 se mantem constante na função objetivo, neste caso, c2 = 
4, então as variações que pode sofrer c1 sem alterar a função objetivo é: 
 
2 ≤ c1 ≤ 6 
 
Da mesma forma se considerarmos c1 = 5, constante, os valores que pode ser 
considerado por c2 sem alterar a função objetivo é: 
 
20/6 ≤ c2 ≤ 10 
 
Observação: Em alguns casos pode acontecer que o limite de crescimento acontece 
quando a rotação da função objetivo passa pela vertical ou horizontal, nesses casos se 
disse que não existe limite inferior ou superior para os coeficientes. 
 
Gráfico 4.- Problema de declividade indeterminada 
 
 
ii) Mudanças na disponibilidade das Restrições 
 
Para isto o que se deseja é identificar o Preço Sombra do modelo, entendendo-
se por preço sombra como aquele que contabiliza quanto o lucro total seria acrescido 
se a quantidade da disponibilidade da restrição aumentasse em uma unidade. Esta 
pode indicar o que esta sendo pago por não ter mais unidades do recurso 
(maximização do lucro) ou pode indicar o preço justo a ser pago por ter uma unidade 
extra do produto (minimização de custo). 
 
25 
 
 
Gráfico 5.- Mudanças da Restrição quantidade de Matéria Prima 1 
 
 
No gráfico 5, observa-se que a quantidade de Matéria Prima 1, pode diminuir 
seu valor num máximo de 20 toneladas ocasionando uma redução do lucro de 3 mil 
dólares, enquanto que se a Matéria Prima 1, aumenta a 36 Toneladas, pode-se 
experimentar um aumento no lucro de 9 mil dólares, em termos simples a penalização 
(aumento ou diminuição do lucro por unidade aumentada ou diminuída de Matéria 
Prima 1) sofrida será de 0,75 mil dólares. 
 
 
Gráfico 6.- Mudanças da Restrição disponibilidade de Matéria Prima 2 
 
 
No gráfico6, quando a disponibilidade de matéria prima 2, experimenta uma 
redução em sua disponibilidade até em 2 toneladas, o efeito que isto produz no lucro é 
26 
 
na diminuição do lucro até em mil dólares, um aumento da disponibilidade matéria 
prima 2, em até 0,67 Toneladas, produz um incremento no lucro de até 0,33 mil 
dólares, isto quer dizer, que por cada mudança unitária na disponibilidade de 
toneladas de matéria prima 2, o lucro sofrerá um impacto de 0,5 milhes de dólares. 
 
 
Gráfico 7.- Mudanças da Restrição da comparação por tipos de Pinturas 
No gráfico 7, se pode experimentar mudanças na restrição de diferencias entre 
tipos de pinturas, observa-se que esta restrição só melhora em 2,5 unidades quando 
ele consegue chegar ao ponto D, que em este caso é o ponto de otimização, o que 
indica que mudanças não nesta restrição não afetam o aumento ou diminuição do 
lucro obtido pela empresa, desta forma variações unitárias desta restrição não afetam 
o comportamento da função objetivo. 
 
27 
 
Gráfico 8.- Mudanças na Restrição por capacidade máxima da pintura para Interiores 
 
 
Da mesma forma no gráfico 8, se pode observar que podemos diminuir até em 
0,5 unidades da restrição capacidade máxima de pintura para Interiores, mas esta 
restrição não faz muito efeito sobre a lucratividade da empresa, isto é, variações 
unitárias desta restrição não produz efeitos significativos na função objetivo. 
 
1.7 Exercícios 
 
Em cada um dos exercícios apresente o modelo matemático, a solução gráfica e um 
estudo da sensibilidade tanto da função objetivo como das restrições. 
 
1. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 um, e o 
lucro unitário de P2 é de 150 um. A empresa necessita de 2 horas para fabricar uma 
unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal 
disponível para essas atividades é de 120 horas. As demandas esperadas para os 2 
produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2 não 
devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Construa o 
modelo do sistema de produção mensal com o objetivo de maximizar o lucro da 
empresa. 
 
2. Uma empresa de comida canina produz dois tipos de rações: Tobi e Rex. Para a 
manufatura das rações são utilizadas cereais e carne. Sabe-se que: 
 
� A ração Tobi utiliza 5 Kg de cereais e 1 kg de carne, e ração Rex utiliza 4 Kg 
de carne e 2 Kg de cereais; 
� O pacote de Tobi custa R$ 20,00 e o pacote de Rex custa R$ 30; 
� O Kg de carne custa R$ 4,00 e o Kg de cereal custa R$ 1,00; 
� Estão disponíveis por mês 10.000 Kg de carne e 30.000 Kg de cereais. 
 
Deseja-se saber qual é a quantidade de cada ração a produzir de modo a 
maximizar o lucro. 
 
3. Um sapateiro faz 6 sapatos por hora, se fizer somente sapatos e 5 cintos por hora, se 
fizer somente cintos. Ele gasta 2 unidades de couro para fabricar 1 unidade de 
sapato e 1 unidade de couro para fabricar 1 unidade de cinto. Sabendo-se que o 
total disponível de couro é de 6 unidades e que o lucro unitário por sapato é de 5 
reais e o de cinto é de 4 reais, pede-se: o modelo do sistema de produção do 
sapateiro, se o objetivo é maximizar seu lucro por hora. 
 
4. Uma empresa fabrica dois modelos de cintos de couro. O modelo M1, de melhor 
qualidade, requer o dobro do tempo de fabricação em relação ao modelo M2. Se 
todos os cintos fossem do modelo M2, a empresa poderia produzir 1000 unidades 
por dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os 
modelos por dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária 
28 
 
é de 400 para M1 e 700 para M2. Os lucros unitários são de R$ 4,00 para M1 e R$ 
3,00 para M2. Qual o programa ótimo de produção que maximiza o lucro total 
diário da empresa?. 
 
5. Um fazendeiro tem que decidir o quanto vai plantar de milho e de alfafa. Os lucros 
são de R$ 2.000,00 por alqueire de milho e de R$ 1.000,00 por alqueire de alfafa. 
Suponha que suas limitações sejam: terra disponível é de 8 alqueires e água 
disponível para irrigação de 80.000 litros sendo que deseja-se plantar no máximo 4 
alqueires de milho. Cada alqueire de milho requererá 10.000 litros de água para 
irrigação e cada alqueire de alfafa requererá 20.000 litros de água. 
 
6. Para uma determinada área, utilizada para o plantio de Soja e Algodão, calcula-se, 
que há 800 homens-horas disponíveis durante o período de semeadura; e que são 
necessários 20 homens-horas por hectare de soja e 40 homens-horas por hectare 
de algodão. Oferece-se ainda uma linha máxima de crédito de $ 6.00, dividida da 
seguinte forma: $ 300 por hectare de soja e $ 100 por hectare de algodão. Como 
organizar esta área de plantio se é sabido que as margens de lucro esperadas são $ 
100 por hectare de soja e $ 80 por hectare de algodão? 
 
7. Um açougue prepara almôndegas misturando carne bovina magra e carne de porco. 
A carne bovina contem 80% de carne e 20% de gordura e custa R$ 0,80 o Kg; a 
carne de porco contém 68% de carne e 32% de gordura e custa R$ 0,60 o Kg. 
Quanto de carne bovina e quanto de carne de porco deve o açougue utilizar por 
quilograma de almôndega se se deseja minimizar seu custo e conservar o teor de 
gordura da almôndega não superior a 25% 
 
8. Uma empresa siderúrgica adquire petróleo para produzir gasolina comum, gasolina 
especial e óleo diesel. Ela necessita manter em seus tanques, no início de cada 
semana, um estoque mínimo dos produtos. A tabela abaixo mostra, para uma 
determinada semana, as composições, disponibilidades e estoques mínimos. Qual é 
o esquema de produção de custo mínimo? 
 
 
 
 
9. Uma empresa do ramo de madeiras produz madeira tipo compensado e madeira 
serrada comum e seus recursos são 40 m3 de pinho e 80 m3 de canela. A madeira 
serrada dá um lucro de R$ 5,00 por m3 e a madeira compensada dá um lucro de 
29 
 
R$0,70 por m2. Para produzir uma mistura comerciável de 1 metro cúbico de 
madeira serrada são requeridos 1 m3 de pinho e 3 m3 de canela. Para produzir 100 
m2 de madeira compensada são requeridos 3 m3 de pinho e 5 m3 de canela. 
Compromissos de venda exigem que sejam produzidos pelo menos 5 m3 de madeira 
serrada e 900 m2 de madeira compensada. Qual é o esquema de produção que 
maximiza o lucro de tal forma a usar o máximo possível do estoque de matéria 
prima e produzir, no mínimo, o compromisso contratual? 
 
10. Uma micro empresa produz dois tipos de jogos para adultos e sua capacidade de 
trabalho é de 50 horas semanais. O jogo “A” requer 3 horas para ser confeccionado 
e propicia um lucro de R$ 30,00, enquanto o jogo “B” precisa de 5 horas para ser 
produzido e acarreta um lucro de R$40,00. Quantas unidades de cada jogo devem 
ser produzidas semanalmente a fim de maximizar o lucro?. 
 
11. A loja de comestíveis B&K vende dois tipos de bebidas não alcoólicas, a marca de 
sabor A1 e a marca da loja. A utilidade por lata da bebida A1 é de 5 centavos de 
dólar, e pela bebida B&K é de 7 centavos de dólar. Em média, a loja não vende mais 
de 500 latas de ambas bebidas ao dia. Devido ao preço da bebida as pessoas 
preferem mais a bebida B&K. Calcula-se que as vendas da marca B&K superam à 
marca A1 numa relação de 2:1 pelo menos. B&K vende como mínimo 100 latas de 
A1 ao dia. Quantas latas de cada marca devem ter em existência a loja diariamente 
para maximizar sua utilidade. 
 
12. A empresa Popeye tem um contrato para receber 600.000 libras de tomates 
maduros a 7 centavos de dólar por libra, com isto produz suco de tomate enlatado, 
assim como a pasta de tomate. Os produtos de tomate em lata são dispostos em 
caixas de 24 latas. Uma lata de suco precisa uma libra de tomates frescos e uma lata 
de pasta só precisa de 1/3 de libra. O mercado ganho pela empresa Popeye é 
limitado por 2.000 caixas de suco e 6.000 caixasde pasta. Os preços por caixa de 
suco e de pasta são de 18 e 9 dólares respectivamente. Desenvolva um programa 
de produção ótima para a empresa Popeye. 
 
13. Blending de Minério: Uma empresa de mineração deseja cumprir um contrato de 
fornecimento de 4 milhões de toneladas por ano do minério Sind Fedd e, para 
tanto, conta com os seguintes minérios ( a tabela abaixo mostra a composição 
porcentual e o custo/tonelada de cada minério): 
 
 M1 M2 
Fe 66% 64% 
Si 1,5% 3,7% 
Custo 5,60 3,30 
 
O minério a ser produzido por este Blending deve conter no mínimo 65% de 
Ferro e no máximo 3% de Silício. Qual é o blending a custo mínimo? 
30 
 
14. A PC-Express é uma loja de computadores que vende dois tipos de 
microcomputadores: desktops e laptops. A empresa ganha R$600,00 por cada 
desktop vendido e R$900,00 por cada laptop vendido. Os computadores que a PC-
Express vende são montados por outra empresa. Esta outra empresa tem outro 
pedido para atender, de forma que não poderá montar mais do que 80 desktops e 
75 laptops no próximo mês. Os funcionários da PC-Express gastam 2 horas 
instalando softwares e testando os desktops. No caso dos laptops eles gastam 3 
horas. No próximo mês os empregados da PC-Express trabalharão 300 horas 
nessas atividades. A PCExpress quer saber quantos desktops e laptops serão 
solicitados à empresa que faz a montagem, de forma a maximizar seu lucro. 
Formule e resolva o problema de programação linear. 
 
15. Uma pequena siderúrgica recebe encomenda de um lote de lingotes de ferro que 
deverá totalizar 240 toneladas de conteúdo do elemento ferro (Fe). O cliente 
admitirá que o lote homogêneo tenha quantidades adicionais do elemento silício 
(Si), mas para cada tonelada de Si deverá haver na liga pelo menos 15 toneladas 
de Fe. A firma tem em estoque quantidade mais que suficiente: 
• Minério do tipo A (min A), que custa R$6.000,00 cada centena de toneladas 
e que tem2% de Si e 60% de Fe. 
• Minério do tipo B (min B), que custa R$3.000,00 cada centena de toneladas 
e que tem 4% de Si e 40% de Fe. 
 
A firma tem ainda a oportunidade de usar como matéria-prima uma sucata de boa 
qualidade, que custa R$2.500,00 a tonelada, e que possui praticamente 100% de 
Fe. Formule o problema de programação linear que calcula a mistura de mínimo 
custo de matérias-primas necessárias para a produção dos lingotes 
encomendados. 
16. Uma fábrica manufatura 5 tipos de prateleiras ( 1p , 2p , 3p , 4p , 5p ) utilizando dois 
processos de produção (processo normal (N) e processo acelerado (A)). Cada 
produto requer certo número de horas para ser trabalhado dentro de cada 
processo e alguns produtos só podem ser fabricados através de um dos tipos de 
processos. O quadro a seguir resume o consumo (em horas) dentro de cada 
esquema de fabricação e os lucros obtidos (em R$) após a dedução dos custos de 
produção. 
Prateleiras 1p 2p 3p 4p 5p 
Lucro/Unidade (R$) 570 575 555 550 560 
Processo Normal (horas) 12 16 - 12 9 
Processo Acelerado (horas) 10 16 5 - - 
31 
 
 
A montagem final de cada prateleira requer 16 horas de mão-de-obra por 
unidade. A fábrica possui 3 máquinas para o processo normal e 2 para o processo 
acelerado. As máquinas trabalham em dois turnos de 8 horas por dia, em um 
regime de 6 dias semanais. Uma equipe de 8 homens trabalha em turno único de 8 
horas e durante 6 dias, na montagem das prateleiras junto aos clientes. Formule o 
problema de programação linear que calcula o melhor esquema de produção. 
17. Um investidor pode investir dinheiro em duas atividades A e B disponíveis no início 
dos próximos 5 anos. Cada $1 investido em A no começo de um ano retorna $1,40 
(um lucro de $0,40) dois anos mais tarde (a tempo de imediato 
reinvestimento).Cada $1 investido em B no início de um ano retorna $1,70, três 
anos mais tarde. Existem ainda 2 atividades C e D que estarão disponíveis no futuro. 
Cada $1 investido em C no início do segundo ano retorna $2,00, quatro anos mais 
tarde. Cada $1 investido em D no começo do quinto ano, retorna $1,30 um ano 
mais tarde. O investidor tem $10.000. Ele deseja conhecer como investir de 
maneira a maximizar a quantidade de dinheiro acumulado no início do sexto ano. 
Formule um modelo de Programação Linear para este problema. Considere que 
não há inflação. 
 
18. Com seus conhecimentos do curso, um aluno calcula que poderia se preparar com 
perfeição para o exame de uma certa disciplina D1 em 20 horas de estudo 
intensivo. Para uma outra disciplina D2 ele precisa de 25 horas. Para passar, ele 
precisa obter no mínimo 50 pontos (num máximo de 100) em cada uma delas. 
Além disso, ele deseja alcançar a maior média ponderada possível, sendo 3 e 5 os 
pesos de D1 e D2 respectivamente. Ele dispõe de apenas 30 horas para estudar. 
Formule o problema como um modelo de Programação Linear, a fim de obter a 
distribuição das horas de estudo, considerando proporcionalidade entre o esforço 
e o rendimento de seus estudos. 
 
19. Um fazendeiro deseja otimizar as plantações de arroz e milho na sua fazenda. O 
fazendeiro quer saber as áreas de arroz (x1) e milho (x2) que devem ser plantadas 
para que o seu lucro nas plantações sejam o máximo. O seu lucro por unidade de 
área plantada de arroz é 5 u.m., e por unidade de área plantada de milho é 2 u.m. 
As áreas plantadas de arroz e milho não devem ser maiores que 3 e 4 
Respectivamente. Cada unidade de área plantada de arroz consome 1 homem 
hora. Cada unidade de área plantada de milho consome 2 homens-hora. O 
consumo total de homens hora nas duas plantações não deve ser maior que 9. 
Resolva o problema utilizando o método gráfico. 
 
32 
 
20. Uma escola prepara uma excursão para 400 alunos. A empresa de transporte 
possui 8 ônibus de 40 lugares e 10 de 50 lugares mas, somente dispõe de 9 
motoristas. O aluguel de um ônibus grande custa R$1.800,00 e de um pequeno 
R$1.000,00. Calcular quantos ônibus de cada tipo devem ser utilizados para que a 
excursão resulte o mais econômica possível para a escola. Construa o modelo de 
programação linear correspondente e resolva aplicando o método gráfico. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
33 
 
 
Unidade 2 
34 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
35 
 
CAPITULO 2: SOLUÇÃO DE UM PROBLEMA DE PROGRAMAÇÃO 
LINEAR PELO MÉTODO SIMPLEX 
 
 
O método SIMPLEX é um algoritmo desenvolvido por George B. Dantzig em 
1947, é uma técnica popular para dar soluções de programação linear. 
 
A Idea Básica deste método consiste em resolver repetidamente um sistema de 
equações lineares para obter uma sucessão de soluções básicas, cada uma melhor que 
as anteriores, até chegar a uma solução básica ótima. 
 
O nome SIMPLEX é derivado de uma generalização do conceito de triângulo a 
outras dimensões. O método usa o conceito de polítopo de N+1 vértices em N 
dimensões. 
Exemplo de Polítopo: 
 
0 – SIMPLEX é um ponto 
1 – SIMPLEX é um segmento de reta 
2 – SIMPLEX é um triângulo 
3 – SIMPLEX é um tetraedro 
 
Para efetuar o método SIMPLEX devemos passar um modelo matemático a 
solução básica, para isto, teremos que definir os seguintes conceitos: 
 
2.1 Variável de Folga: 
 
É aquela variável que identifica quanto falta para completar a restrição, esta é 
considerada como uma variável fictícia, usualmente é usada nas restrições de tipo “≤”. 
 
Exemplo: 
 
 
Nosso desejo é que esta inequação seja convertida em equação, para isto, devemos 
incrementar uma variável adicional, podendo ser: 
 
 
 
Onde S1 é chamada de variável de folga. 
2.2 Variável de Superávit 
 
São aquelas variáveis quediminuem o valor da restrição numa inequação, para 
lograr converter a uma equação, esta também é considerada variável fictícia, é 
usualmente usada nas restrições de tipo “≥”. 
 
36 
 
Exemplo: 
 
 
 
Como desejamos converter a igualdade a inequação acima, então criamos a 
variável de superávit S1, e o disponibilizamos da forma a seguir: 
 
 
 
Onde S1 é chamada de variável de superávit. 
 
2.3 Variável não restrita 
 
Existem situações nas quais uma variável pode assumir qualquer valor real. 
Neste caso a variável em questão pode ser definida como a diferencia de duas 
variáveis não negativas. 
 
Consideramos que seja uma variável irrestrita, então podemos considerar 
dois valores, e , de forma que 
 
Exemplo: 
 
Se , então podemos definir e , de forma que . 
 
 
2.4 Algoritmo SIMPLEX Geral 
 
 
Em termos gerais o algoritmo SIMPLEX segue a seguinte estrutura: 
 
a) INICIO: Identificar uma solução básica admissível inicial 
 
Nesta parte se procura levar as inequações a equações, conformando-se desta 
forma a solução básica do modelo matemático proposto. 
 
b) ITERAÇÃO: Passar a uma solução básica admissível melhor 
 
Para isto será necessário fazer as seguintes perguntas: 
 
� Que variável deve de entrar como solução do sistema? 
� Que variável deve de sair da solução do sistema? 
 
A ideia é melhorar a função objetivo com a saída e entrada de variáveis na 
solução do sistema de equações. 
37 
 
 
 
 
c) PARAGEM: 
 
O algoritmo para quando não houver mais variáveis que possam entrar como 
solução ao sistema de equações. 
 
2.5 EXEMPLO DO USO DO ALGORITMO SIMPLEX 
 
Exemplo1: Problema extraído de Caixeta-Filho (2001), adaptado de Hillier e Lieberman 
(1988) 
Certa agroindústria do ramo alimentício tirou de produção uma certa linha de 
produto não lucrativo. Isso criou uma considerável excedente na capacidade de 
produção. A gerência está considerando dedicar essa capacidade excedente a um ou 
mais produtos, identificados como produtos 1, 2 e 3. A capacidade disponível das 
máquinas que poderia limitar a produção e o número de horas de máquinas requerido 
por unidade dos respectivos produtos é conhecida como coeficiente de produtividade 
(em horas de máquinas por unidade), está resumida na tabela a seguir: 
 
1 2 3
A 9 3 5 500
B 5 4 0 350
C 3 0 2 150
Tempo disponível 
(horas de máquina)
ProdutosTipo de 
Maquina
 
 
O lucro unitário estimado é de US $ 30,00, US $ 12,00 e US $ 15,00, 
respectivamente, para os produtos 1, 2 e 3. Determine a quantidade de cada produto 
que a agroindústria deve produzir para maximizar seu lucro. 
 
Para a interpretação do modelo matemático precisamos os seguintes procedimentos: 
 
a) Definição das variáveis: 
 
X1: Quantidade a produzir pela máquina 1 
X2: Quantidade a produzir pela máquina 2 
X3: Quantidade a produzir pela máquina 3 
 
b) Definição das restrições do modelo: 
 
Restrições que sofrem o sistema dependem do tempo disponível de produção, 
da tabela de coeficiente de produtividade, temos: 
 
Maquina A: 9 X1 + 3 X2 + 5 X3 ≤ 500 horas 
Maquina B: 5 X1 + 4 X2 ≤ 350 horas 
38 
 
Maquina C: 3 X1 + 2 X3 ≤ 150 horas 
 
c) Definição da Função Objetivo 
 
O que é o que se deseja? ==> Maximizar Lucros 
 
Maximizar Z = 30 X1 + 12 X2 + 15 X3 
 
Desta forma o modelo matemático é definido por: 
 
Maximizar Z = 30 X1 + 12 X2 + 15 X3 
Sujeito a 
9 X1 + 3 X2 + 5 X3 ≤ 500 
5 X1 + 4 X2 ≤ 350 
3 X1 + 2 X3 ≤ 150 
X1, X2, X3 ≥ 0 
 
Procedimento SIMPLEX 
 
a) INICIO: Identificar uma solução básica admissível inicial 
 
Esta metodologia trabalha com pontos de igualdade, isto é, se temos equações 
com desigualdades devemos converter a equações de igualdade, desta forma o 
modelo matemático muda ao seguinte formato 
 
9 X1 + 3 X2 + 5 X3 + S1 = 500 
5 X1 + 4 X2 + S2 = 350 
3 X1 + 2 X3 + S3 = 150 
X1, X2, X3, S1, S2, S3 ≥ 0 
 
Como S1, S2, S3 são variáveis de folga o valor que representa na função objetivo 
é nula, desta forma a função objetivo é definida por: 
 
Z - 30 X1 - 12 X2 - 15 X3 - 0 S1 - 0 S2 - 0 S3 = 0 
 
A partir destas equações podemos gerar a solução básica do SIMPLEX da forma 
seguinte: 
 
X1 X2 X3 S1 S2 S3 Z
Z -30 -12 -15 0 0 0 0
S1 9 3 5 1 0 0 500
S2 5 4 0 0 1 0 350
S3 3 0 2 0 0 1 150 
 
As variáveis que podem entrar são todas aquelas que estão atuando como 
inicio de coluna na tabela acima e as variáveis que podem sair são todas as variáveis 
que estão colocadas como inicio da linha na tabela acima. 
39 
 
b) ITERAÇÃO: Passar a uma solução básica admissível melhor 
 
Iteração 1: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável X1. Encontrar a razão que é a relação 
entre as disponibilidades das restrições e os coeficientes da variável que entra, neste 
caso 
 
 
 
A escolha da variável que sai será aquele que proporcione o menor valor entre 
os valores positivos, caso de ter no sistema razões negativas, não serão considerados 
como solução, o mesmo acontece com valores infinitos, eles levam a resultados in 
determinados 
 
 
 
A variável que sai é aquela que apresenta a menor razão entre as variáveis 
soluções do modelo, neste caso a variável S3. 
 
O seguinte passo é incluir a variável X3 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 3) a toda linha da variável que entra, obtendo: 
 
 
 
Agora se devem preencher os espaços em branco, de a forma a seguir: 
 
40 
 
 
 
 
 
 
Obtendo 
 
 
 
Devemos perguntar: na linha do Z existem valores negativos? -----------> SIM!!!!!!!! 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
Iteração 2: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável X2, a variável que sai é S1, por ser a 
variável que menor razão apresenta 
 
 
 
O seguinte passo é incluir a variável X2 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 3) a toda linha da variável que entra, obtendo: 
 
41 
 
 
 
Agora se devem preencher os espaços em branco, de a forma a seguir: 
 
 
 
 
 
Então o resultado obtido é 
 
 
Devemos perguntar: na linha do Z existe valores negativos? 
 
 
 
 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
 
Iteração 3: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável S3, a variável que sai é S2, por ser a 
variável que menor razão apresenta 
 
 
 
 
SIM! 
42 
 
 
 
 
O seguinte passo é incluir a variável X2 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 7/3) a toda linha da variável que entra, obtendo: 
 
 
 
 
 
 
 
Os cálculos para a interação são as seguintes: 
 
 
 
Daqui o resultado desta iteração é: 
 
X1 X2 X3 S1 S2 S3 Z
Z 0 0 -5/7 20/7 6/7 0 12100/7
X2 0 1 25/21 -5/21 3/7 0 650/21
S3 0 0 -6/7 -4/7 3/7 1 100/7
X1 1 0 20/21 4/21 -1/7 0 950/21 
 
Devemos perguntar: na linha do Z existe valores negativos? 
 
 
 
 
 
 
SIM! 
43 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
 
Iteração 4: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível na função objetivo, em nosso caso é a variável X3, a variável que sai é 
X1, por ser a variável que menor razão apresenta 
 
 
 
 
O seguinte passo é incluir a variável X3 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 20/21) a toda linha da variável que entra, obtendo: 
 
X1 X2 X3 S1 S2 S3 Z
Z
X2
S3
X3 21/20 0 1 1/5 -3/20 0 950/20= 47,5 
 
Os outros valores são obtidos a partir das operações seguintes 
 
 
 
c) PARAGEM 
 
Os resultados destes cálculos apresenta a seguinte solução: 
 
 
44 
 
 
Devemos perguntar: na linha do Z existe valores negativos? 
] 
 
 
 
 
 
Então paramos de utilizar a metodologia SIMPLEX 
 
Segundo o resultado do método SIMPLEX, temos que: 
 
X1 = 0 Não se produz nada da maquina 1; 
X2 = 87,5 É necessário produzir 87,5 unidades da maquina 2; 
X3 = 47,5 É necessário produzir 47,5 unidades da maquina 3; 
S3 = 55 temos 55 horas disponíveis na maquina C; 
S1 = S2 = 0 Consumimos todas as horas das máquinas A e C; 
 
Contudo teremos um lucro de: 
 Z = R$1.762,50 
 
Exemplo 2: Extraída do Livro Pesquisa Operacional de Caixeta Filho 
Um produtor comprou uma propriedade com 500 ha de pasto. Ele tem um capital de $ 
10.400 para gastar na compra de gado bovino ou ovino. Os preços de mercado, os 
lucros anuais estimados por animal e o número de hectares requeridos por animal são 
dados na tabela a seguir: 
 
 
 
Determine a melhor combinação de investimentos a ser perseguida. 
 
Se bem é certo este problema exige uma programação inteira, já que o resultado 
adequado é um valor inteiro em sua colocação, mas para efeitos de exemplificar esta 
seção consideraremos que podemos ter frações de bichos (Gados ou Carneiros). Para a 
interpretação do modelo matemático precisamos os seguintes procedimentos: 
 
a) Definição das variáveis: 
 
X1: Quantidade de Carneiro Merino 
X2: Quantidade de Gado Herefold 
X3: Quantidade de Carneiro Romey 
 
NÃO 
45 
 
b) Definição das restrições do modelo: 
O produtor comprou a propriedade com 500 ha de pasto, isto é: 
 
 X1 + 3 X2 + 0,5 X3 ≤ 500 
 
Ele tem um capital de $ 10.400 para adquirir algum das três espécies de animais 
 
 7 X1 + 100 X2 + 10 X3 ≤ 10.400 
 
c) Definição da Função Objetivo 
 
Nosso objetivo é que com a adequada compra destes animais o proprietário possa 
lucrar, desta forma: 
 
Maximizar Z = 12 X1 + 40 X2 + 7 X3 
 
 
 
Desta forma o modelo matemático é definido por: 
 
Maximizar Z = 12 X1 + 40 X2 + 7 X3 
Sujeito a 
 X1 + 3 X2 + 0,5 X3 ≤ 500 
 7 X1 + 100 X2 + 10,0 X3 ≤ 10.400 
X1, X2, X3 ≥ 0 
 
Procedimento SIMPLEX 
 
a) INICIO: Identificar uma solução básica admissível inicial 
 
 X1 + 3 X2 + 0,5 X3 + S1 = 500 
7 X1 + 100 X2 + 10,0 X3 + S2 = 10.400 
X1, X2, X3, S1, S2 ≥ 0 
 
Como S1, S2 são variáveis de folga o valor que representa na função objetivo é 
nula, desta forma a função objetivo é definida por: 
 
Z - 12 X1 - 40 X2 - 7 X3 - 0 S1 - 0 S2 - 0 S3 = 0 
 
A partir destas equações podemos gerar a solução básica do SIMPLEX da forma 
seguinte: 
 
46 
 
X1 X2 X3 S1 S2 S3 Z
Z -30 -12 -15 0 0 0 0
S1 9 3 5 1 0 0 500
S2 5 4 0 0 1 0 350
S3 3 0 2 0 0 1 150 
 
As variáveis que podem entrar são todas aquelas que estão atuando como 
inicio de coluna na tabela acima e as variáveis que podem sair são todas as variáveis 
que estão colocadas como inicio da linha na tabela acima. 
 
b) ITERAÇÃO: Passar a uma solução básica admissível melhor 
 
Iteração 1: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável X1. Encontrar a razão que é a relação 
entre as disponibilidades das restrições e os coeficientes da variável que entra, neste 
caso 
 
 
 
A escolha da variável que sai será aquele que proporcione o menor valor entre 
os valores positivos, caso de ter no sistema razões negativas, não serão considerados 
como solução, o mesmo acontece com valores infinitos, eles levam a resultados in 
determinados 
 
 
 
A variável que sai é aquela que apresenta a menor razão entre as variáveis 
soluções do modelo, neste caso a variável S3. 
 
O seguinte passo é incluir a variável X3 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 3) a toda linha da variável que entra, obtendo: 
 
 
 
Agora se devem preencher os espaços em branco, de a forma a seguir: 
47 
 
 
 
 
Obtendo 
 
 
Devemos perguntar: na linha do Z existem valores negativos? 
 
 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
Iteração 2: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável X2, a variável que sai é S1, por ser a 
variável que menor razão apresenta 
 
 
 
O seguinte passo é incluir a variável X2 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 3) a toda linha da variável que entra, obtendo: 
 
 
SIM! 
48 
 
 
Agora se devem preencher os espaços em branco, de a forma a seguir: 
 
 
 
Então o resultado obtido é 
 
 
Devemos perguntar: na linha do Z existem valores negativos? 
 
 
 
 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
Iteração 3: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível, em nosso caso é a variável S3, a variável que sai é S2, por ser a 
variável que menor razão apresenta 
 
 
 
O seguinte passo é incluir a variável X2 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 7/3) a toda linha da variável que entra, obtendo: 
 
 
 
SIM! 
49 
 
Os cálculos para a interação são as seguintes: 
 
 
 
Daqui o resultado desta iteração é: 
 
X1 X2 X3 S1 S2 S3 Z
Z 0 0 -5/7 20/7 6/7 0 12100/7
X2 0 1 25/21 -5/21 3/7 0 650/21
S3 0 0 -6/7 -4/7 3/7 1 100/7
X1 1 0 20/21 4/21 -1/7 0 950/21 
 
Devemos perguntar: na linha do Z existe valores negativos? 
 
 
 
 
Então seguimos utilizando a metodologia SIMPLEX 
 
 
Iteração 4: Identificar a variável que entra, que será a variável cujo valor é a mais 
negativa possível na função objetivo, em nosso caso é a variável X3, a variável que sai é 
X1, por ser a variável que menor razão apresenta 
 
 
 
O seguinte passo é incluir a variável X3 na tabela SIMPLEX e dividi-la pelo pivô (o 
valor 20/21) a toda linha da variável que entra, obtendo: 
 
SIM! 
50 
 
X1 X2 X3 S1 S2 S3 Z
Z
X2
S3
X3 21/20 0 1 1/5 -3/20 0 950/20 = 47,5 
 
Os outros valores são obtidos a partir das operações seguintes 
 
 
 
c) PARAGEM 
 
Os resultados destes cálculos apresenta a seguinte solução: 
 
 
 
Devemos perguntar: na linha do Z existe valores negativos? ------------> NÃO!!!!!!!! 
 
Então paramos de utilizar a metodologia SIMPLEX 
 
Segundo o resultado do método SIMPLEX, temos que: 
 
X1 = 0 Não se produz nada da maquina 1; 
X2 = 87,5 É necessário produzir 87,5 unidades da maquina 2; 
X3 = 47,5 É necessário produzir 47,5 unidades da maquina 3; 
S3 = 55 temos 55 horas disponíveis na maquina C; 
S1 = S2 = 0 Consumimos todas as horas das máquinas A e C; 
 
Contudo teremos um lucro de: Z = R$1.762,50 
 
 
 
51 
 
2.6 Solução de um problema de Programação Linear pelo 
Software SOLVER do Excel 
 
 
 Para instalar o recurso Solver, clique em Suplementos no menu Ferramentas e 
marque a caixa de seleção Solver, Clique em OK e o Excel instalará o recurso Solver, 
Após a instalação do suplemento, você poderá executá-lo clicando em Solver no menu 
Ferramentas. 
 
 Para resolver o problema na planilha, devemos definir células para representar 
as variáveis de decisão, uma célula para representar o valor da função objetivo e 
também devemos representar as restrições. 
 
Para entender o Solver consideramos o seguinte exemplo: 
 
Exemplo3. O Sr. A. Galo, diretor - técnico de um aviário, pretende determinar a 
composição da alimentação que deverá ser fornecida diariamente aos animais 
misturando rações, de forma a conseguir certa qualidade nutritiva a um custo mínimo. 
Os dados relativos ao custo e às propriedades nutritivas de cada tipo de ração constam 
da tabela abaixo. 
 
Super Galo Extra Galo Milho
Energia Calorias/Kg 500 400 300 150
Vitaminas u.i./Kg 300 500 200 150
Proteinas gr/Kg 60 70 30 20
Custo U.M./Kg Ração 250 300 100
Ração Quantidade 
Minima Requerida
Propriedades 
Nutritivas
Unidades
 
 
a) Definição das variáveis: 
 
X1: Quantidade de Ração Super Galo 
X2: Quantidade de Ração Extra Galo 
X3: Quantidade de Ração de Milho 
 
b) Definição das restrições do modelo: 
 
Quantidade de Calorias/Kg necessária para produzir a ração: 
 
 500 X1 + 400 X2 + 300 X3 ≥ 150 
 
Quantidade de Vitaminas por Kg necessária para produzir a razão: 
 
 300 X1 + 500 X2 + 200 X3 ≥ 150 
 
Quantidade de Proteínas por Kg necessária para produzir a razão: 
 
52 
 
 60 X1 + 70 X2 + 30 X3 ≥ 20 
 
c) Definição da Função Objetivo 
 
Nosso objetivo é conseguir certa qualidade nutritiva a um custo mínimo, desta 
forma: 
 
Minimizar Z = 250 X1 + 300 X2 + 100 X3 
Desta forma o modelo matemático é definido por: 
 
Minimizar Z = 250 X1 + 300 X2 + 100 X3 
Sujeito a 
 500 X1 + 400 X2 + 300 X3 ≥ 150 
 300 X1 + 500 X2 + 200 X3 ≥ 150 
 60 X1 + 70 X2 + 30 X3 ≥ 20 
X1, X2, X3 ≥ 0 
 
No Excel devemos criar um espaço que define as variáveis em estudo, neste 
caso 
 
 
 
Uma vez composto a estrutura, devemos utilizar o SOLVER para encontrar a 
solução, da maneira seguinte, primeiro no Excel fazer um click em Dados e logo em 
Solver, como se indica abaixo. 
 
 
 
53 
 
 
 
 
 
Uma vez feito o passo anterior se abre a janela parâmetros do Solver, aqui em 
principio devemos definir Objetivo e as Células Variáveis, como se amostra a 
continuação: 
 
 
 
 
 
 
 
 
 
 
Após temos que introduzir as restrições, neste caso se deve clicar no ícone 
Adicionar, da forma seguinte: 
 
 
 
54 
 
 
 
 
 
Agora só falta a inclusão da disponibilidade Mínima na janela de restrição, da 
maneira seguinte: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Após fazer OK, voltamos a janela inicial de Parâmetros do Solver, tendo que 
fazer o seguinte: 
 
55 
 
 
 
Para nossa solução devemos assegurar que esses dois elementos em circulo 
estejam ativados, após fazer um click em Resolver, obtendo a resposta seguinte: 
 
 
 
Observemos que: 
 
X1 = 0 X2 = 0 X3 = 0,75 Z = 75 
 
De Calorias se precisou 225 
De Vitaminas se precisou 150 
De Proteínas se precisou 22,5 
 
 
 
 
 
 
 
 
 
 
 
 
56 
 
2.7 Exercícios 
 
1. Para produzir 3 tipos de telefones celulares, a fábrica da Motorela utiliza três 
processos diferentes, o de montagem, a configuração e a verificação. Para fabricar o 
celular Multi-Tics, são necessárias 0,1 h de montagem, 0,2 h de configuração e 0,1 h 
de verificação. O mais popular Star Tic Tac requer 0,3 h de montagem, 0,1 h de 
configuração e 0,1 h de verificação. Já o moderno Vulcano necessita de 0,4 h de 
montagem, 0,3 h para configuração, porém, em virtude de seu circuito de última 
geração, não necessita de verificação. A fábrica dispõe de capacidade de 290 
hs/mês na linha de montagem, 250 hs/mês na linha de configuração e 110 hs/mês 
na linha de verificação. Os lucros unitários dos produtos Multi-Tics, Star Tic-Tac e 
Vulcano são R$ 100, R$ 210 e R$ 250, respectivamente e a Motorela consegue 
vender tudo o que produz. Sabe-se ainda que o presidente da Motorela exige que 
cada um dos três modelos tenha produção mínima de 100 unidades e quer lucrar 
pelo menos R$ 25.200/mês com o modelo Star Tic-Tac. O presidente também exige 
que a produção do modelo Vulcano seja pelo menos o dobro do modelo Star Tic-
Tac. 
 
2. Uma empresa do ramo de madeiras produz madeira tipo compensado e madeira 
serrada comum e seus recursos são 40 m3 de pinho e 80 m3 de canela. A madeira 
serrada dá um lucro de R$ 5,00 por m3 e a madeira compensada dá um lucro de 
R$0,70 por m2. Para produzir uma mistura comerciável de 1 metro cúbico de 
madeira serrada são requeridos 1 m3 de pinho e 3 m3 de canela. Para produzir 100 
m2 de madeira compensada são requeridos 3 m3 de pinho e 5 m3 de canela. 
Compromissos de venda exigem que sejam produzidos pelo menos 5 m3 de madeira 
serrada e 900 m2 de madeira compensada. Qual é o esquema de produção que 
maximiza o lucro de tal forma a usar o máximo possível do estoque de matéria 
prima e produzir, no mínimo, o compromisso contratual? 
 
3. A empresa PARMALAT tem duas maquinas distintas para processar leite puro e 
produzir leite desnatado, manteiga ou queijo. A quantidade de tempo necessário 
em cada maquina para produzir cada unidade de produto resultante e os lucros 
netos são proporcionados na tabla a seguir: 
 
MAQUINA #1 (min/galão) 0,2 0,5 1,5
MAQUINA #2 (min/galão) 0,3 0,7 1.2
LUCRO NETO (US$/Galão) 0,22 0,38 0,72
Unidade
LEITE 
DESCREMADO
MANTEIGA QUEIJO
 
 
Supondo que se dispõe de 8 horas em cada maquina diariamente, como Gerente do 
Departamento de Administração, formule um modelo para determinar um plano de 
produção diária que maximize os lucros netos e que produza um mínimo de 300 
galões de leite desnatada, 200 libras de manteiga e 100 libras de queijo. 
57 
 
 
4. Uma certa corporação tem três fábricas filiais com capacidade de produção 
excedente. As três unidades têm capacidade para fabricar um certo produto, tendo 
a gerência decidido utilizar parte dessa capacidade de produção excedente para 
fazê-lo. Ele pode ser feito em três tamanhos - grande, médio e pequeno -, os quais 
geram um lucro unitário líquido de $ 140, $ 120 e $ 100, respectivamente. As 
fábricas l, 2 e 3 têm capacidade excedente de mão-de-obra e de equipamento para 
produzirem 750, 900 e 450 unidades do produto por dia, respectivamente, 
independentemente do tamanho ou combinação de tamanhos envolvidos. 
Entretanto, a quantidade de espaço disponível para estoque de produtos em 
processo também impõe um limite às taxas de produção. As fábricas 1, 2 e 3 têm 
1.170, 1.080 e 450 metros quadrados de espaço disponível para estoque de 
produtos em processo, em um dia de produção, sendo que cada unidade dos 
tamanhos grande, médio e pequeno, produzida por dia, requer 1,80; 1,35 e 1,08 
metros quadrados, respectivamente. 
 
As previsões indicam que podem ser vendidas, por dia, 900, 1.200 e 750 unidades 
dos tamanhos grande, médio e pequeno, respectivamente. Para manter uma carga 
de trabalho uniforme entre as fábricas, e para reter algum tipo de flexibilidade, a 
gerência decidiu que a produção adicional designada a cada fábrica deve utilizar a 
mesma porcentagem da capacidade excedente de mão-de-obra e de equipamento. 
A gerência deseja saber a quantidade de produto, por tamanho, que deveria ser 
produzida em cada uma das fábricas, para maximizar o lucro (HILLIER e LIEBERMAN, 
1988). 
5. Uma fábrica de implementos agrícolas produz os modelos A, B e C, que 
proporcionam lucros unitários da ordem de $ 16, $ 30 e $ 50, respectivamente. As 
exigências de produção mínimas mensais são de 20 para o modelo A, 120 para o 
modelo B e 60 para o modelo C. 
 
Cada tipo de implemento requer uma certa quantidade de tempo paraa fabricação 
das partes componentes, para a montagem e para testes de qualidade. 
Especificamente, uma dúzia de unidades do modelo A requer três horas para 
fabricar, quatro horas para montar e uma para testar. Os números correspondentes 
para uma dúzia de unidades do modelo B são 3,5, 5 e 1,5; e para uma dúzia de 
unidades do modelo C, são 5, 8 e 3. Durante o próximo mês, a fábrica tem 
disponíveis 120 horas de tempo de fabricação, 160 horas de montagem e 48 horas 
de testes de qualidade. 
 
Formule e resolva o problema de programação de produção como um modelo de 
programação linear (CAIXETA-FILHO, 2001, adaptado de WAGNER, 1986). 
 
6. Uma refinaria produz três tipos de gasolina: verde, azul e comum. Cada tipo requer 
gasolina pura, octana e aditivo que são disponíveis nas quantidades de 9.000.000, 
4.800.000 e 2.200.000 litros por semana, respectivamente. As especificações de 
cada tipo são: 
58 
 
 
� Um litro de gasolina verde requer 0,22 litro de gasolina pura, 0,50 litro de 
octana e 0,28 litro de aditivo; 
� Um litro de gasolina azul requer 0,52 litro de gasolina pura, 0,34 litro de octana 
e 0,14 litro de aditivo; 
� um litro de gasolina comum requer 0,74 litro de gasolina pura, 0,20 litro de 
octana e 0,06 litro de aditivo. 
 
Como regra de produção, baseada em demanda de mercado, o planejamento da 
refinaria estipulou que a quantidade de gasolina comum deve ser no mínimo igual a 
16 vezes a quantidade de gasolina verde e que a quantidade de gasolina azul seja 
no máximo igual a 600.000 litros por semana. A empresa sabe que cada litro de 
gasolina verde, azul e comum dá uma margem de contribuição para o lucro de $ 
0,30, $ 0,25 e $ 0,20 respectivamente, e seu objetivo é determinar o programa de 
produção que maximiza a margem total de contribuição para o lucro (ANDRADE, 
2000). 
 
7. A LCL Equipamentos produz 3 tipos de furadeiras que necessitam de tempos 
diferentes na linha de montagem. Para que cada tipo de furadeira seja fabricado, 
um custo de preparação da fábrica é incorrido (ajustes que devem ser feitos na 
linha de montagem). Suponha que todas as furadeiras do mesmo tipo serão 
produzidas de uma só vez (apenas uma preparação por tipo). Os dados relevantes à 
análise do problema encontram-se na tabela a seguir. Encontre as quantidades a 
serem fabricadas para maximizar o lucro do próximo mês. 
 
 
8. Um fazendeiro está estudando a divisão de sua propriedade nas seguintes 
atividades produtivas: 
� Destinar certa quantidade de alqueires para a plantação de cana-de-açucar, a 
uma usina local, que se encarrega da atividade e paga aluguel da terra $ 300,00 
por alqueire por ano 
� Usar outra parte para a criação de gado de corte. A recuperação das pastagens 
requer adubação (100 kg/Alq) e irrigação (100.000 litros de água/Alq) por ano. 
O lucro estimado nessa atividade é de $ 400,00 por alqueire no ano 
� Usar uma terça parte para o plantio de soja. Essa cultura requer 200 kg por 
alqueire de adubos e 200.000 litros de água/Alq para irrigação por ano. O lucro 
estimado nessa atividade é de $ 500,00 / Alqueire no ano 
� Disponibilidade de recursos por ano: 12.750.000 litros de água, 14.000 kg de 
adubo e 100 alqueires de terra. 
59 
 
Quantos alqueires deverão destinar a cada atividade para proporcionar o melhor 
retorno? Construa o modelo de decisão. 
 
9. Uma tarefa é constituída de três operações: Preparação, Embalagem e Transporte. 
As capacidades máximas diárias de cada seção são: Preparação: 160 up (unidades 
de preparação), Embalagem: 240 ue (unidades de embalagem), Transporte: 170 ut 
(unidades de transporte). A manipulação de uma unidade de produto A exige 5up, 
10ue e 5ut; para o produto B, cada unidade exige 2up, 2ue e 6ut; uma unidade do 
produto C exige 8up, 6ue e 3ut. Os lucros líquidos de cada unidade A, B e C são, 
respectivamente 10, 8, 5 unidades monetárias. Formule o programa de tarefas 
(decisão quanto às quantidades de A, B e C), sob a forma de um Modelo de 
Programação Linear, de modo a maximizar o lucro líquido total sem ultrapassar as 
capacidades máximas das seções. 
10. Um fazendeiro tem 200 unidades de área de terra, onde planeja cultivar trigo, 
arroz e milho. A produção esperada é de 1800 Kg por unidade de área plantada de 
trigo, 2100 Kg por unidade de área plantada de arroz e 2900 Kg por unidade de área 
plantada de milho. Para atender o consumo interno de sua fazenda, ele deve 
plantar pelo menos 12 unidades de área de trigo, 16 unidades de área de arroz e 20 
unidades de área de milho. Ele tem condições de armazenar no máximo 700.000,0 
Kg. Sabendo que o trigo dá um lucro de 0,20 R$/Kg, o arroz 0,15 R$/Kg e o milho 
0,11 R$/Kg, quantas unidades de área de cada produto ele deve plantar para que 
seu lucro seja o maior possível? 
 
11. Em uma fazenda deseja-se fazer 10.000 Quilos de ração com o menor custo 
possível. De acordo com as recomendações do veterinário dos animais da fazenda, 
a mesma deve conter: 
 
� 15% de proteína. 
� Um mínimo de 8% de fibra. 
� No mínimo 1100 calorias por Quilo de ração e no máximo 2250 calorias por 
Quilo. 
 
Para se fazer a ração, estão disponíveis 4 ingredientes cujas características 
técnico-econômicas estão mostradas abaixo:(Dados em %, exceto calorias e custo) 
 
 
 
A ração deve ser feita contendo no mínimo 20% de milho e no máximo 12% de 
soja. Formule um modelo de Programação Linear para o problema. 
 
60 
 
12. Uma fábrica de papel recebeu 3 pedidos de rolos de papel com as larguras e 
comprimentos mostrados abaixo: 
 
 
A fabrica tem que produzir os pedidos a partir de 2 rolos de tamanho padrão que 
tem 100 e 200 centímetros de largura e cumprimento muito grande (para efeitos 
práticos pode-se considerar infinito). Os rolos dos pedidos não podem ser 
emendados na largura embora possam ser emendados no cumprimento. 
Deseja-se determinar como devem ser cortados os 2 rolos de tamanho padrão 
para atender os pedidos, com o objetivo de que a perda de papel seja a mínima 
possível. 
 
13. O gerente de um restaurante que está encarregado de servir o almoço, em uma 
convenção, nos próximos 5 dias tem que decidir como resolver o problema do 
suprimento de guardanapos. As necessidades para os 5 dias são 110, 210, 190,120 
e 100 unidades respectivamente. Como o guardanapo é de um tipo especial, o 
gerente não tem nenhum em estoque e suas alternativas durante os 5 dias são: 
 
• Comprar guardanapos novos ao preço de $10 cada um. 
• Mandar guardanapos já usados para a lavanderia onde eles podem receber 2 
tratamentos: 
 
(a)Devolução em 48 horas ao preço de $3 a peça. 
(b) Devolução em 24 horas ao preço de $5 a peça. 
 
Considerando que o objetivo do gerente é minimizar o custo total com os 
guardanapos formule um modelo de Programação Linear para o problema. 
 
As seguintes observações devem ser levadas em conta: 
 
• O tempo da lavanderia é considerado ser exato, ou seja, o guardanapo enviado 
as 15 horas de um dia volta as 15 horas do dia seguinte (serviço de 24 horas) ou 
seja após o almoço. Idem para o serviço de 48 horas. 
• Após a convenção os guardanapos serão jogados no lixo. 
 
 
61 
 
14. A Motorauto S/A fabrica 3 modelos de automóveis nas suas fábricas: Modelo de 
1.100 cilindradas (c.c.), modelo de 1.400 c.c. e modelo de 1.800 c.c. Um problema 
trabalhista faz prever uma greve prolongada na fábrica 1 num futuro muito 
próximo. Para fazer frente a esta situação, a direção da empresa decidiu preparar 
um plano excepcional de produção e vendas para o próximo período, pressupondo 
que não haverá produção na fábrica 1 durante este período. Neste mesmo 
período, a capacidade de produção da fábrica 2 será de 4.000 unidades de 1.100 
c.c., ou 3.000 unidades de 1.400 c.c. ou 2.000 unidades de 1.800 c.c. ou qualquer