Andréa Cardoso
Fundamentos da
PESQUISA OPERACIONAL
UNIFAL-MG
Fevereiro 2011
SUMÁRIO
1 Conhecendo a Pesquisa Operacional
4
1.1
Modelos Matemáticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2
Primeiros Exemplos e Aplicações . . . . . . . . . . . . . . . . . . . . . . .
8
1.3
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Programação Matemática
24
2.1
Modelos de Otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2
Problemas de Programação Matemática
2.3
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Programação Linear
. . . . . . . . . . . . . . . . . . . 28
44
3.1
Estruturação de Modelos Lineares . . . . . . . . . . . . . . . . . . . . . . . 45
3.2
Resolução Gráfica de um PPL . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3
3.2.1
Representação Gráfica das Restrições . . . . . . . . . . . . . . . . . 48
3.2.2
Representação Gráfica da Função Objetivo . . . . . . . . . . . . . . 54
3.2.3
Soluções do Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4 Resolução de PPL
64
4.1
Estruturação de Modelos Lineares . . . . . . . . . . . . . . . . . . . . . . . 64
4.2
Fundamentação Teórica
4.3
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2
5 O Método Simplex
79
5.1
Fluxograma para soluções finitas . . . . . . . . . . . . . . . . . . . . . . . 91
5.2
Análise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.4
Lista de Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
CAPÍTULO
1
CONHECENDO A PESQUISA OPERACIONAL
O termo Pesquisa Operacional (PO) designa uma área do conhecimento que consiste no
desenvolvimento de métodos cientı́ficos de sistemas complexos, com a finalidade de prever
e comparar estratégias ou decisões alternativas, cujo objetivo é dar suporte à definição de
polı́ticas e determinação de ações.
O trabalho do matemático russo Leonid Kantorovich de 1939 intitulado “Métodos
matemáticos na organização e no planejamento de produção” é considerado um dos precursores da PO, porém manteve-se desconhecido da comunidade cientı́fica ocidental até
1959. O próprio termo Pesquisa Operacional, do inglês Operations Research, foi cunhado
pelo matemático russo na tentativa de englobar, sob uma única denominação, todas as
técnicas existentes ou que viriam a ser desenvolvidas e que tinham o mesmo objetivo
citado. De fato, o termo PO designa um conjunto de disciplinas isoladas tais como Programação Linear, Teoria das Filas, Simulação, Programação Dinâmica, Teoria dos Jogos,
dentre outras.
A Pesquisa Operacional tal qual como a conhecemos surgiu durante a Segunda Guerra
Mundial tendo como objetivo o desenvolvimento de metodologia para solução de problemas relacionados com as operações militares quando os Aliados se viram confrontados
com problemas complexos de natureza logı́stica, tática e de estratégia militar. Para apoiar
os comandos operacionais na resolução desses problemas foram criados grupos multidisciplinares compostos por matemáticos, fı́sicos, engenheiros e cientistas sociais. O que
esses cientistas fizeram foi aplicar o método cientı́fico, que tão bem conheciam, aos problemas que lhes foram sendo colocados. Desenvolveram então a idéia de criar modelos
4
5
matemáticos, apoiados em dados e fatos, que lhes permitissem perceber os problemas em
estudo, simular e avaliar o resultado hipotético de estratégias bem como propor decisões
alternativas. Em 1941 a Inglaterra inaugura a Seção de Pesquisa Operacional do Comando da Força Aérea de Combate para trabalhar com problemas de operações de guerra,
manutenção e inspeção de aviões, melhoria da probabilidade de destruição de submarinos,
controle de artilharia antiaérea, dimensionamento de comboios de frota, entre outros.
O sucesso e credibilidade ganhos durante a guerra foram tão grandes que, terminado o
conflito, esses grupos de cientistas e a sua nova metodologia de abordagem dos problemas
se transferiram para as empresas que, com o vertiginoso crescimento econômico que se
seguiu, se viram também confrontadas com problemas de decisão de grande complexidade.
Em 1947 os Estados Unidos implantam o projeto SCOP (Scientific Computation of Optimal Programs) com o objetivo de apoiar decisões de operações da força aérea americana,
coordenado por um economista e por um matemático George Dantzig que desenvolveu e
formalizou o Método Simplex para resolver problemas de otimização linear.
Face ao seu caráter multidisciplinar, atualmente as contribuições da PO estende-se
por praticamente todos os domı́nios da atividade humana, da Engenharia à Medicina,
passando pela Economia e à Gestão Empresarial.
Os ramos mais importantes desenvolvidos em PO são:
Programação Matemática
Outros Ramos
X Programação Linear
X Análise Estatı́stica
X Programação Não Linear
X Teoria dos Jogos
X Programação Dinâmica
X Teoria das Filas
X Programação Inteira
X Simulação
X Otimização Global
X Gestão de estoques
Resumidamente podemos dizer que o objetivo principal da PO é determinar a programação otimizada de atividades ou recursos, fornecendo um conjunto de procedimentos
e métodos quantitativos para tratar de forma sistematizada problemas que envolvam a
utilização de recursos escassos. Para apoiar a tomada de decisão, a PO busca a solução
de problemas que podem ser representados por modelos matemáticos.
De modo geral, para a resolução de um problema, um estudo de PO é desenvolvido
em fases como indicado no esquema abaixo.
6
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
Figura 1.1: Passos para implementação de PO
Identificado o problema a ser estudado, a fase de formulação consiste na estruturação
dos dados e informações disponı́veis, a próxima fase de modelagem concentra-se na construção do modelo que é uma representação simplificada do sistema, em geral descrito
por um conjunto de equações e desigualdades matemáticas. A solução é obtida através
de um método que pode ser um procedimento matemático ou algoritmo para alcançar o
resultado. A avaliação consiste na validação do modelo, nesta fase ajustes podem ser
feitos. A decisão é a escolha e operacionalização da solução encontrada.
As fases de formulação e modelagem do problema devem ser executadas com muita
responsabilidade pois “É muito difı́cil encontrar uma solução certa para um problema mal
formulado!”.
1.1
Modelos Matemáticos
Observar, compreender, reproduzir e aprimorar fenômenos, que podem ser naturais, sociais ou econômicos, tem sido desde sempre uma preocupação básica da Ciência. Eventualmente tais fenômenos podem ser controláveis e haverá então condições de realizar previsões
com pequeno nı́vel de incerteza, para tanto é necessária a construção de modelos que são
representações idealizadas para tais fenômenos, processos ou sistemas.
Um modelo descreve, representa e imita o procedimento que ocorre no mundo real, estabelecendo o relacionamento das variáveis com os objetivos, da melhor maneira possı́vel,
obedecendo à limitação de tempo e de custo. Os modelos podem ser assim classificados:
1.1. MODELOS MATEMÁTICOS
7
verbais: quando são descritos e representados por palavras e sentenças.
fı́sicos: quando representados por algum tipo de material concreto, alterando-se suas
dimensões, formato e custo. Por exemplo: maquetes e protótipos.
esquemáticos: quando descritos por meio de gráficos, tabelas ou diagramas.
matemáticos: quando representados por relações matemáticas, como equações, inequações, funções ou lógica simbólica.
Um modelo matemático é uma representação simplificada de uma situação real e deve
refletir a essência do problema, representando as grandezas envolvidas por variáveis e as
relações de interdependência existentes entre elas por expressões matemáticas. Esquematicamente, um modelo matemático pode ser visto como uma Caixa Preta, representando as
relações que descrevem a dependência das variáveis, que recebe a entrada formada pelas
variáveis do problema que se quer otimizar e processa essas informações para produzir a
saı́da que é a solução do problema ou resultado da decisão.
Entrada
Modelo
Matemático
Saída
O modelo mais adequado depende de vários fatores: a natureza das relações entre
as variáveis, os objetivos almejados, a extensão do controle sobre as variáveis e o nı́vel
de incerteza existente tanto nas relações entre as variáveis como na própria definição
das variáveis. Para cada conjunto de situações especı́ficas o modelo matemático, doravante denominado somente modelo, deverá ter uma forma padronizada e a solução poderá
ser obtida por métodos matemáticos especı́ficos para cada caso, que serão estudados
posteriormente.
De maneira geral, um problema de tomada de decisão requer solução que responda a
três perguntas:
1. Qual é a meta a ser atingida?
(objetivo)
2. Quais são as alternativas para a decisão?
(variáveis de decisão)
3. Sob quais condições a decisão deve ser tomada? (restrições)
8
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
1.2
Primeiros Exemplos e Aplicações
Nesta seção serão apresentadas os primeiras formulações de problemas de otimização como
auxı́lio na tomada de decisão, para serem analisados, modelados e, exceto o sexto exemplo,
resolvidos. Os três primeiros exemplos são bem simples e podem ser resolvidos intuitivamente ou por enumeração não necessitando de modelos matemáticos formais. O quarto
problema requer o uso de planilhas eletrônicas para realizar simulações de maneira mais
rápida e eficaz. O quinto problema necessita de conhecimentos prévios de Cálculo Diferencial. O sexto exemplo, é um pouco mais complexos e necessita de modelos matemáticos
estruturados de Programação Matemática assunto do capı́tulo seguinte cujas técnicas de
resolução serão estudadas no capı́tulo 3. Finalmente, o sétimo exemplo apresenta um
problema clássico da Teoria dos Jogos e suas implicações.
. . . Exemplo 1.1. O problema da dona-de-casa
1
Considere a situação em que uma dona de casa precisa decidir entre comprar manteiga
ou margarina para o consumo da famı́lia. Ela vai seguir intuitivamente um raciocı́nio
lógico através do qual procurará alinhar as vantagens e desvantagens de cada alternativa,
segundo seus critérios de decisão.
De inı́cio, a dona de casa irá identificar as diferenças entre os produtos segundo vários
fatores que poderiam ser tomados para comparação como: o custo, o sabor, a durabilidade,
a consistência quando gelado, os efeitos para saúde, dentre outros. Para simplificar, ela se
limitará a avaliar apenas os itens que considera mais importantes: custo, sabor e efeitos
para a saúde. Esses serão os critérios para a tomada de decisão da dona-de-casa.
As consequencias de cada alternativa serão:
1. Comprando manteiga, a dona-de-casa
• gasta mais dinheiro;
• agrada a famı́lia;
• põe em risco a famı́lia devido ao teor mais alto de colesterol.
2. Comprando margarina, a dona-de-casa
• economiza dinheiro;
• desagrada a famı́lia;
• não coloca em risco a saúde da famı́lia.
1
Extraı́do de Andrade, 2004
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
9
Dependendo do peso que atribuir a cada consequencia, a dona-de-casa poderá chegar
a uma conclusão. Se, por exemplo, a restrição da famı́lia for dinheiro, a decisão que lhe
parecerá melhor será comprar margarina.
. . . Exemplo 1.2. Problema da travessia do rio
Imagine que você esteja a margem leste de um rio juntamente com três amigos Felipe,
João e Kelly. Vocês querem atravessar para a margem oeste e dispõem de um único meio
de locomoção, uma canoa que pode levar no máximo duas pessoas por vez e não pode
ir nem voltar vazia. Você tem constituição mais atlética e pode atravessar o rio a remo
em 1 minuto, enquanto Felipe, João e Kelly levam 2, 5 e 10 minutos, respectivamente.
Se houver duas pessoas na canoa, o tempo da travessia será a média dos tempos que
seriam gastos individualmente. Após duas travessias seguidas a pessoa fica cansada e leva
o dobro do tempo para atravessar o rio. Como é mais conveniente realizar a travessia de
modo que os quatro estejam do outro lado do rio no menor tempo possı́vel?
As seguintes alternativas podem ser consideradas:
1. Ir você e Felipe, você volta pega João, você volta e pega Kelly.
2. Ir você e Felipe, Felipe volta pega João, você volta e pega Kelly.
3. Ir você e Felipe, você volta vai João e Kelly, Felipe volta e pega você.
Calculando os tempos gastos em cada uma das alternativas, temos:
T1 =
1, 5 + 1 + 3, 5 + 2 + 6
T2 =
1, 5 + 2 + 4, 5 + 1 + 5, 5
= 14 min
= 14, 5 min
T3 = 1, 5 + 1 + 7, 5 + 2 + 1, 5 = 13, 5 = 13, 5 min
Dentre as três alternativas, a melhor é a alternativa 3, onde o tempo total para a
travessia será de 13,5 minutos. Você pode identificar alternativas distintas cujo tempo
seja igual a 13,5 minutos? Existe outra alternativa melhor?
Variáveis de decisão: Alternativas 1, 2 e 3
10
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
Objetivo:
Minimizar o tempo de travessia
Restrições:
Tempo individual para travessia,
Duas pessoas por vez na canoa,
A canoa não atravessa o rio sozinha,
Penalidade para atravessar mais que duas vezes seguidas.
. . . Exemplo 1.3. Decisão com risco ou incerteza
2
A tabela seguinte apresenta os retornos (ganhos ou perdas médias) para um valor fixo
de insvetimento associados às decisões de investir em conta poupança, em dólar ou fundos
de investimentos.
Decisão A1
Decisão A2
Decisão A3
Estados possı́veis Probabilidades Investir em Investir em Investir em
da economia
poupança
dólar
fundos
S1 : Recessão
0,40
$ 300
$ 400
- $ 100
S2 : Estabilidade
0,40
$ 300
$ 300
$ 200
S3 : Expansão
0,20
$ 300
$ 200
$ 700
Qual é o melhor investimento?
Se a decisão for baseada nos valores médios ou esperados dos ganhos, teremos:
GA1 =
0, 40 × 300 + 0, 4 × 300 + 0, 2 × 300
= 300
GA2 =
0, 40 × 400 + 0, 4 × 300 + 0, 2 × 200
= 320
GA3 = 0, 40 × (−100) + 0, 4 × 200 + 0, 2 × 700 = 180
a melhor decisão a ser tomada é a alternativa A2 , investir em dólar.
Variáveis de decisão: Investir em A1 , A2 ou A3
Objetivo:
Maximizar o retorno
Restrições:
Estados possı́veis da economia, probabilidades e retornos.
2
Baseado em Shimizu, 2006
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
11
. . . Exemplo 1.4. O caso da Casa das Esfirras
A Casa das Esfirras produz e comercializa esfirras de carne a partir de dois ingredientes
básicos: massa e recheio. A empresa necessita estabelecer um modelo para simulação de
lucros que lhe permita a formação do melhor preço de venda a ser praticado. Considera-se
que o preço unitário da esfirra e o preço médio praticado pela concorrência são os únicos
fatores relevantes na determinação da demanda. Atualmente a empresa pratica o mesmo
preço médio do mercado local e comercializa 70.000 unidades de esfirras mensalmente.
Um estudo encomendado pela empresa constatou que, a cada 1% a menos cobrado pela
unidade de esfirra em relação ao preço médio praticado pela concorrência implica em um
aumento nas vendas de 5.000 unidades mensais.
Dados relevantes para o estudo são fornecidos na tabela seguinte:
em R$
Preço médio praticado pela concorrência (por unidade)
1,00
Custo unitário da massa
0,10
Custo unitário do recheio
0,30
Custo do processo de fabricação (por unidade)
0,40
Custo fixo
8.000,00
Variáveis de decisão: Preço unitário da esfirra
Objetivo:
Maximizar o lucro
Restrições:
Demanda de mercado
Para este problema, é preciso desenvolver um modelo que permita a simulação do lucro
operacional mensal a partir da demanda d e dos custos para estabelecer o preço p a ser
praticado.
O lucro (L) é obtido pela diferença entre a receita (R) e o custo total (CT),
L = R − CT.
12
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
A receita pode ser calculada pelo produto entre o preço praticado por unidade e a
quantidade vendida, neste caso a quantidade demandada, que por sua vez depende do
preço praticado. Assim,
R(p) = p · d(p).
O custo total é a soma do custo fixo com o custo variável, que depende da quantidade
a ser produzida, neste caso a demanda.
CT = C + C(d)
Para construir um modelo para formação de preço, é primeiro necessário calcular a
função demanda, isto é, encontrar a lei que determina a quantidade de esfirras comercializadas mensalmente em função do preço praticado.
De acordo com os dados, o preço médio praticado é de R$ 1,00 e para este valor a
quantidade demandada é 70.000 unidades. Assim a função d(p) a ser determinada satisfaz:
d(1) = 70000.
Levando-se em conta que a cada desconto de 1% no preço corresponde uma demanda
extra de 5.000 unidades, temos:
d(0, 99) = 75000.
Admitindo que a função demanda seja uma função afim do tipo:
d(p) = ap + b
onde o coeficiente angular a pode ser determinado por:
a=
70000 − 75000
∆d
=
= −500000
∆p
1 − 0, 99
Para encontrar o coeficiente linear b e determinar d, basta substituir d(1) = 70000 na
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
13
expressão d(p) = −500000p + b, desta forma
70000 = d(1) = −500000(1) + b
Logo,
b = 570000.
Portanto, a função demanda nas condições do problema é:
d(p) = −500000p + 570000
Para este caso o modelo será construı́do em planilha eletrônica alcançando assim facilidade de interação com o usuário e possibilitando rápidas alterações. Admitindo que o
preço praticado seja R$ 1,00 a unidade de esfirras, é possı́vel calcular a quantidade vendida, a receita e os custos mensais e consequente prever o lucro operacional. O modelo em
planilha eletrônica é apresentado na tabela abaixo, onde as fórmulas para os respectivos
cálculos estão explicitadas na coluna C.
Na tabela a seguir são apresentados os resultados do Lucro Operacional para diversos
valores simulados para o preço a ser praticado, onde lucro negativo é representado por
valores entre parênteses.
14
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
Uma rápida inspeção garante que:
• Preço acima de 1,00 retorna em lucro menor;
• Lucro crescente para valores entre 1,00 e 0,95;
• Lucro decrescente para valores entre 0,95 e 0,90.
Desta primeira análise, conclui-se que o melhor preço está entre 1,00 e 0,95. Para
decidir qual preço retorna o maior lucro, é preciso simular todos os valores neste intervalo.
Observando a segunda parte da tabela, concluı́mos que o melhor preço a ser praticado é
R$ 0,97 resultando num lucro de R$ 6.450,00 que é 7,5% maior do que o lucro mensal
atual da empresa.
. . . Exemplo 1.5. Gestão do estoque
Um posto de combustı́veis tem uma demanda de gasolina e álcool ao longo dos últimos
três anos, conforme a tabela dada em milhões de litros:
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
15
Ano
Álcool
Gasolina
2007
2,00
5,00
2008
2,05
5,80
2009
3,00
6,20
Seus custos estimados de colocação de um pedido são cerca de R$ 325,00 e os custos de
manutenção dos estoques são de 23% do custo de aquisição, por ano. A empresa adquire
os combustı́veis a R$ 30,00 o galão de 50 litros de álcool e R$ 78,00 o galão de gasolina.
Atualmente o suprimento de combustı́vel é feito em quantidades constantes a intervalos
regulares quinzenalmente, qual a quantidade ideal de cada combustı́vel que o posto deve
pedir por vez?
O objetivo do problema é determinar o lote de compra que deve ser encomendado
por vez, de modo a minimizar o custo total de operação do estoque dos dois tipos de
combustı́veis.
Variáveis de decisão: Quantidade de álcool a ser encomentada por vez
Quantidade de gasolina a ser encomendada por vez
Objetivo:
Minimizar o custo de operação de estoque
Restrições:
Custo do pedido
Custo de Manutenção do estoque
O custo total é a soma dos custos de manutenção de estoques e de emissão e colocação
de pedidos, considerando que a demanda e os custos são relativamente estáveis durante o
ano.
minimizar
Custo Total (CT)
= custo de manutenção do álcool (CMA) +
+ custo de manutenção da gasolina (CMG) +
+ custo do pedido (CP)
O custo de manutenção é o produto do nı́vel médio em estoque pelo custo unitário
de manutenção, onde o nı́vel médio é a metade da quantidade encomendada (dados
16
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
empı́ricos). O custo do pedido é o produto do número de pedidos anuais pelo custo
unitário de colocação do pedido.
Devemos identificar os elementos conhecidos e desconhecidos do problema que fornecerão
os dados e as variáveis de decisão.
n: total de pedidos anuais
qA : quantidade de álcool (em milhões de litros) encomendados por vez
qG : quantidade de gasolina (em milhões de litros) encomendados por vez
aA : quantidade de álcool (em milhões de litros) comercializada anualmente
aG : quantidade de gasolina (em milhões de litros) comercializada anualmente
A partir dos dados fornecidos, podemos calcular a média de vendas da empresa dos
últimos três anos:
aA =
2 + 2, 05 + 3
= 2, 35
3
aG =
5 + 5, 8 + 6, 2 ∼
= 5, 67
3
e
É possı́vel obter qA e qG a partir do valor de n.
qA =
aA
n
qG =
aG
n
e
Portanto, podemos admitir que a única variável independente do problema é o número
de pedidos anuais n.
Sabe-se que o custo de manutenção dos estoques é de 23% do custo de aquisição de
cada combustı́vel. A partir desta informação é possı́vel calcular CMA, considerando que
a unidade que estamos utilizando é um milhão de litros de combustı́vel que equivale a
20.000 galões de 50 litros, como cada galão de álcool custa R$ 30,00, o custo da unidade
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
17
de álcool é R$ 600.000,00. Calculando a porcentagem para manutenção dos estoques,
temos que o custo unitário para manutenção do álcool é 138.000 e portanto,
CMA = 138.000
qA
= 69.000qA
2
De forma análoga calculamos que o custo da unidade de gasolina é R$ 1.560.000,00
e obtemos 358.800 como o custo unitário para manutenção do estoque de gasolina e
consequentemente:
CMG = 358.800
qG
= 179.400qG
2
Escrevendo o custo total em função das variáveis e constantes assim definadas e calculadas:
CT = 69.000qA + 179.400qG + 325n
2, 35
5, 67
+ 179.400
+ 325n
n
n
1
1
= 162.150 + 1.017.198 + 325n
n
n
= 69.000
Portanto,
CT (n) = 1.179.348
1
+ 325n
n
Como o objetivo é minimizar uma função em uma variável real, devemos encontrar os
pontos crı́ticos da função utilizando a primeira derivada.
d
1
CT (n) = −1.179.348 2 + 325 = 0
dn
n
A equação diferencial acima é satisfeita para n ∼
= 60, 24 ou n ∼
= −60, 24. Entretanto
no contexto do problema proposto n deve ser um número inteiro positivo, sendo assim
tomamos, por arredondamento, n = 60. E o teste da segunda derivada nos garante que
este é um ponto de mı́nimo.
d2
1
CT (n) = 2.358.696 3 > 0,
2
dn
n
∀n>0
Assim, deve-se encomendar 39.166,67 litros de álcool e 94.500 litros de gasolina por
18
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
vez totalizando 60 pedidos anuais com custo total de R$ 39.155,80 contra os custos atuais
de R$ 53.809,54 referentes a 26 pedidos anuais, o que representa uma economia para a
empresa de aproximadamente 27,21%.
. . . Exemplo 1.6. Problema da dieta ótima:
3
Em uma dieta, cada 100 g de alimento A e B fornecem os seguintes elementos nutritivos
(em unidades):
Elemento nutritivo
A
B
Carboidratos
1
3
Vitaminas
3
4
Proteı́nas
3
1
As quantidade mı́nimas necessárias de elementos nutritivos, por dia, são 8 unidades de
carboidratos, 19 unidades de vitaminas e 7 unidades de proteı́nas. Cada 100 g do alimento
A contém 300 kcal (kilocalorias) e custa $ 50 u.m. enquanto cada 100 g do alimento B tem
500 kcl e custa $ 25 u.m. Como é possı́vel minimizar o custo e a quantidade de calorias
da dieta formada pelos alimento A e B?
Variáveis de decisão: x1 : quantidade de A (em 100 g)
x2 : quantidade de B (em 100 g)
Objetivo:
Restrições:
min z1 = 50x1 + 25x2
(minimizar o custo)
min z2 = 300x1 + 500x2
(minimizar quantidade de calorias)




x1 + 3x2 ≥ 8 (quantidade de carboidratos)







 3x1 + 4x2 ≥ 19 (quantidade de vitaminas)



3x1 + x2 ≥








x1 , x2 ≥
3
7 (quantidade de proteı́nas)
0 (condição de não-negatividade)
Adaptado do exemplo inicialmente formulado por George Dantzig
1.2. PRIMEIROS EXEMPLOS E APLICAÇÕES
19
Representando as inequações e funções do problema no plano cartesiano obtemos o
seguinte gráfico.
Por simples inspeção visual é possı́vel identificar o ponto (1,4) do plano cartesiano
como sendo o ponto onde a função custo é minimizada, obtendo um custo mı́nimo de
$ 150 u.m. com consumo total de 2.300 kcal, enquanto o ponto (5,1) minimiza a quantidade
de calorias, 2.000 kcal, com custo de $ 275 u.m.
. . . Exemplo 1.7. O dilema do prisioneiro
4
Dois prisioneiros acusados de terem cometido um crime em conjunto estão presos em
celas separadas e são interrogados separadamente por um delegado de polı́cia. Se os dois
prisioneiros confessarem o crime, ambos serão condenados à pena de 10 anos de prisão.
Se nenhum dos dois prisioneiros confessar, o delegado, usando provas circunstanciais, só
pode condená-los à pena de 2 anos. Se apenas um dos dois prisioneiros confessar, este
prisioneiro receberá, como prêmio, um pena leve de 1 ano de prisão, e o outro, que não
confessou, será condenado à pena maior, de 12 anos de prisão. Qual decisão deve ser
tomada?
4
Proposto originalmente por M.Flood e M.Dresher em 1950, posteriormente adaptado por A.W.Tucker.
20
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
A tabela seguinte resume as penalidades atribuidas a cada prisioneiro
Prisioneiro B
C
Prisioneiro A NC
C
NC
(10, 10)
(1,12)
(12,1)
(2,2)
onde a primeira entrada do par ordenado corresponde à decisão do prisioneiro A e a
segunda entrada à decisão do prisioneiro B.
Examinemos o problema do ponto de vista de um dos prisioneiros, objetivando determinar a melhor estratégia assumindo que o cúmplice também é racional.
Se seu companheiro confessar, o prisioneiro A, por exemplo, será condenado a 10 anos
de prisão se confessar e a 12 anos se permanecer calado. Neste caso a melhor decisão é
confessar. Agora, se B permanecer calado, A será condenado a 1 ano se confessar e a 2
anos se não confessar. O melhor estratégia nesta situação é confessar.
Aparentemente a melhor estratégia é portanto confessar! Entretanto se ambos seguirem
o mesmo raciocı́nio, os dois prisioneiros serão condenados a 10 anos de prisão. Se optarem
por cooperar e permanecerem calados, receberão pena menor de 2 anos. E aı́ está o dilema,
buscando individualmente a melhor estratégia para si acabam ambos por serem punidos
rigorosamente. O fato é que pode haver dois vencedores neste jogo, se o problema for
analisado em conjunto buscando a melhor solução para o grupo e consequentemente a
cooperação resultará na melhor solução para ambos.
“A teoria dos jogos sugere que,
embora a cooperação não seja nada fácil de ser alcançada,
é possı́vel demonstrar que muitas vezes ela é preferı́vel ao conflito.”
David P. Barash
1.3. LISTA DE PROBLEMAS
1.3
21
Lista de Problemas
Resolva cada um dos seguintes problemas, identificando as variáveis de decisão, objetivo
e restrições:
1. Durante a construção de uma casa, seis vigas de 8m cada devem ser recortadas
para atingir o comprimento correto de 7, 5m. As operações para cortar uma viga
obedecem a seguinte sequencia:
Operação
Tempo [s]
1. Colocar vigas nos cavaletes
15
2. Marcar o comprimento
10
3. Cortar a viga
20
4. Armazenar a viga cortada
20
Há três pessoas envolvidas: dois carregadores devem trabalhar simultaneamente nas
operações 1,2 e 4, e um cortador se encarregará da operação 3. Há dois pares de
cavaletes nos quais as vigas a recortar são colocadas na preparação para o corte, e
cada par pode suportar até três vigas lado a lado. Sugira um boa programação para
recortar as seis vigas.
2. Como deve ser montado um retângulo a partir de uma corda de comprimento 10m
para que a área seja máxima.
3. Em um jogo de beisebol, Jim é o lançador e Joe o rebatedor. Suponha que Jim
possa atirar uma bola com velocidade ou um bola curva de maneira aleatória. Se
Joe previr corretamente que será uma bola curva, poderá manter uma média de
rebates de 0,5. Ao contrário, se Jim atirar uma bola curva e Joe se preparar para
uma bola com velocidade, sua média de rebates ficará em 0,2. Por outro lado, se Joe
previr corretamente que será uma bola com velocidade, conseguirá uma média de
rebates de 0,3; caso contrário, sua média será de apenas 0,1. Defina as alternativas
para essa situação.
22
CAPÍTULO 1. CONHECENDO A PESQUISA OPERACIONAL
4. A Pastéis e Pastelões Ltda. fabrica pastéis de forno a partir de dois ingredientes
básicos: massa semipronta e recheio congelado. A empresa pretende estabelecer um
modelo para previsão de seu lucro operacional mensal que lhe permita estabelecer o
preço dos pastéis que deve ser praticado pela empresa. Desconsiderando a hipótese
de alteração do tamanho e da qualidade dos pastéis, a diretoria considera que o preço
unitário do pastel e o preço médio praticado pela concorrência são os únicos fatores
relevantes na determinação da demanda, a qual se comporta segundo a seguinte
equação:
Z = 15000 − 5000x + 5000y
onde x é o preço do pastel da Pastéis e Pastelões e y é o preço médio dos pastéis
vendidos pelos concorrentes.
Dados adicionais são fornecidos pela tabela:
em R$
Preço médio praticado pela concorrência (por pastel)
7,00
Custo unitário da massa
1,30
Custo unitário do recheio
2,00
Custo do processo de fabricação (por pastel)
0,40
Custo fixo
6.000,00
5. Refaça o exemplo 1.5, considerando que o posto está interessado em resolver o
problema do estoque separadamente para cada combustı́vel, isto é, determine o
número de pedidos anuais para o álcool que minimize o custo total e, após calcule
o número de pedidos a ser realizados para a gasolina. Qual a relação entre estes
dois valores encontrados e o número ótimo de pedidos determinado para o problema
original?
6. Um atacadista de materiais de construção obtém seu cimento de um fornecedor
único. A demanda de cimento é razoavelmente constante ao longo do ano. No
1.3. LISTA DE PROBLEMAS
23
último ano, a empresa vendeu 2000 toneladas de cimento. Seus custos estimados de
colocação de um pedido são cerca de $25, e os custos de manutenção dos estoques
são de 20% do custo de aquisição, por ano. A empresa adquire cimento a $60 por
tonelada. Quanto cimento a empresa deveria pedir por vez?
7. Uma empresa comercializa queijos deseja estudar sua polı́tica de estocagem de modo
a otimizar sua operação, reduzindo os custos. Após um cuidadoso levantamento, o
gerente estimou que o custo anual de manter um item em estoque é de $50,00. Tal
custo foi obtido considerando-se o custo do capital investido, o custo das instalações,
refrigeração, limpeza e seguros, durante um ano, e dividindo-se pelo número estimado de itens que irão compor o estoque no mesmo perı́odo. Consideremos que este
número seja constante e igual a 1.000 por ano. O suprimento do produto é feito
em quantidades constantes e intervalos regulares, a colocação de cada encomenda
tem um custo fixo de $ 1.000,00, incluindo documentação, despesas de pedido e
transporte. Qual a quantidade de mercadoria que deve ser encomendada de cada
vez?
CAPÍTULO
2
PROGRAMAÇÃO MATEMÁTICA
Desde a antiguidade vários cientistas tais como Euclides, Newton, Lagrange, Leontief, Von
Neumann, dentre outros, tem dedicado seus estudos à pesquisa do ótimo. A área que estuda Problemas de Otimização é denominada Programação Matemática que engloba uma
ampla classe de problemas. O termo programação significa que existe um planejamento
das atividades.
A Programação Matemática vem se constituindo como uma das mais poderosas ferramentas matemáticas para diversos segmentos, propiciando melhorias mensuráveis nos
processos e automatização dos mesmos, análises operacionais, de projetos, reengenharia e
identificação de gargalos. Seus benefı́cios são exatamente aqueles procurados por qualquer
empresa: diminuição dos custos e aumento dos lucros. Em algumas organizações ela está,
inclusive, embutida em suas rotinas informatizadas de planejamento diário dos processos
de operação.
Segundo pesquisas efetuadas em empresas que tem utilizado esta ferramenta, a redução
de custos se enquadra facilmente na faixa entre 1% e 5%, existindo casos que chegam
até a 15%. A magnitude do benefı́cio da Programação Matemática na performance das
empresas pode ser avaliada nos casos listados a seguir referentes a diferentes áreas de
atividade econômica:
24
25
1. A companhia de óleos TEXACO utilizou a Programação Linear para obter condições
ideais de processamento do grude bruto para produzir quantidades proporcionais às
necessidades do mercado aos diversos derivados do grude: gasolina, óleos com diversas graduações ou asfalto. A aplicação da metodologia em sete das suas refinarias
permitiu obter uma melhoria de 30% nos lucros, atingindo 30 milhões de dólares.
2. A rede de fast food McDonald’s nos Estados Unidos aplicou a Programação Matemática para otimização dos horários de trabalho em quatro de seus estabelecimentos, pertencentes a Al Boxley. Este tipo de atividade recorre freqüentemente
à mão-de-obra em part-time, tendo como resultado uma grande aleatoriedade na
disponibilidade dos recursos humanos. A Programação Linear proporcionou um
melhor aproveitamento dos recursos disponı́veis, com a exigência de cobertura durante todo perı́odo de funcionamento das unidades, obtendo-se uma programação
de horários mais conveniente de acordo com as preferências de horário de cada funcionário.
3. O exército norte-americano desenvolveu um sistema designado de MLRPS
“Manpower Long-Range Planning System” que permite estimar as necessidades de
recursos humanos num horizonte que vai dos 7 aos 20 anos. O modelo de otimização
analisa a forma com que as forças armadas podem obter no futuro a estrutura
militar desejada. Para tal, aspectos como as admissões, abandonos, promoções e
transferências são tidos em conta no modelo que determina o número de recursos
necessário.
Uma das caracterı́sticas principais de Programação Matemática é sua extensibilidade, pode ser aplicada a diverso número de organizações e sistemas: indústrias, governos, agências, hospitais, economia, sociologia, biologia, dentre outros. Algumas de suas
aplicações se tornaram clássicas:
Problema de transporte;
Administração da produção;
26
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
Análise de investimentos;
Problemas de distribuição de recursos, pessoal e tarefas;
Problemas de corte materiais, etc.
Em um Problema de Otimização pretende-se maximizar ou minimizar uma quantidade
especı́fica, designada objetivo, que depende de um número finito de variáveis independentes ou interrelacionadas por limitações ou restrições técnicas do sistema. Resolver o
problema significa aplicar uma sequencia de operações matemáticas para distribuir recursos limitados sobre operações que exigem a sua utilização simultânea, de forma ótima para
o objetivo especı́fico. Um Problema de Programação Matemática (PPM) é um problema
de otimização satisfazendo dois fatos principais:
• A existência de um objetivo que pode ser explicitado em termos das variáveis de
decisão do problema;
• A existência de restrições à aplicação dos recursos, tanto com relação às quantidades
disponı́veis quanto com relação à forma de emprego.
2.1
Modelos de Otimização
Especificamente, o objetivo primordial de um PPM é encontrar a melhor solução para
problemas que podem ser representados por modelos matemáticos onde o objetivo pode ser
expresso em função das variáveis e as restrições expressas como equações ou inequações.
Os modelos matemáticos utilizados em PPM seguem, em geral, uma estrutura padrão
composta por uma função-objetivo, um critério de otimização e um conjunto de restrições.
A forma geral de um modelo para um PPM com n variáveis e m restrições é apresentada
a seguir:
2.1. MODELOS DE OTIMIZAÇÃO
27
otimizar: z = f (x1 , x2 , . . . , xn )




g1 (x1 , x2 , . . . , xn )







 g2 (x1 , x2 , . . . , xn )
sujeito a:

..


.







 gm (x1 , x2 , . . . , xn )








b1








≤ 






 b2
= 

..




.









 ≥ 




 bm
(2.1)
onde as variáveis do problema estão representadas por xj com j = 1, . . . , n e bi , para
i = 1, . . . , m, representa a quantidade disponı́vel de determinado recurso. Utilizaremos a
notação vetorial para representar as variáveis de decisão, assim define-se:
x=
x1 x2 . . . xn
(2.2)
f (x) é denominada função-objetivo e gi (x) são as funções restrições do problema.
A solução do modelo pode ser obtida por técnicas matemáticas e algoritmos especı́ficos,
e a construção do modelo deve levar em consideração a disponibilidade de uma técnica
para o cálculo da solução. Para melhor estudar as técnicas disponı́veis para resolução de
PPM, a área pode ser subdividida em duas subáreas determinadas pelas propriedades das
funções envolvidas no problema:
Programação Linear: Todas as funções do modelo são lineares em relação às variáveis.
Programação Não-Linear: Pelo menos uma das funções envolvidas não é linear.
A solução de um PPM inicia-se pela modelagem, esta etapa é tão importante tanto
quanto o desenvolvimento de métodos de solução, visto que a qualidade de todo o processo
é consequencia direta do grau de representatividade do modelo.
O exemplo 1.6 apresentado no capı́tulo anterior foi modelado seguindo certa sistematização e agora iremos nos concentrar na estruturação de modelos especı́ficos para PPM.
A tarefa de construção do modelo a partir do enunciado do problema deve seguir uma
metodologia básica, apresentada a seguir:
28
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
Identificação das variáveis de decisão
Todas as grandezas envolvidas devem ser determinadas, explicitando as decisões que
devem ser tomadas, nomeando-as xj , j = 1, . . . , n.
Definição do critério de otimização
Critérios de avaliação capazes de indicar que uma decisão é preferı́vel a outras
devem ser definidos. Deve-se identificar as metas que se pretendem alcançar com
a resolução do problema, expressando-as como funções matemáticas. Em geral, o
objetivo aparece na forma de maximização ou minimização de quantidades.
Formulação das restrições
Todos os requisitos, condicionalismos e limitações do problema, tanto explı́citas
como implı́citas, devem ser identificados. Cada limitação imposta na descrição do
problema deve ser expressa como uma equação ou inequação em função das variáveis
de decisão.
2.2
Problemas de Programação Matemática
Para melhor ilustrar os conceitos discutidos, serão apresentadas algumas situações que podem ser descritas com o auxı́lio de um modelo de Programação Matemática. A seguir são
propostos alguns PPM onde espera-se exemplificar e detalhar o processo de modelagem,
entretanto será a experiência individual responsável pelo desenvolvimento de habilidades
para a criação de bons modelos matemáticos, eficientes e realistas. Salientamos que, ainda
não há a preocupação com a solução de problemas que poderá ser obtida posteriormente.
. . . Exemplo 2.1. Produção de balas
Considere que uma doceira deseja abrir um pequeno negócio para produção de balas.
A princı́pio ela está considerando produzir dois tipos de balas: caramelo e nozes. Na
produção são utilizados três ingredientes: leite, açúcar e nozes. A doceira tem em estoque
10kg de açúcar, 1kg de nozes e 6l de leite. A composição da bala de caramelo é: 40%
de leite e 60% de açúcar, e para as balas de nozes os ingredientes devem ser misturados
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
29
na seguinte proporção: 40% de leite, 50% de açúcar e 10% de nozes. Cada quilo de bala
de caramelo pode ser vendido a R$10,00 enquanto um quilo de bala de nozes pode ser
vendido por R$13,00. Qual deve ser a produção de cada tipo de bala para obter a maior
receita?
De acordo com a sistemática estabelecida anteriormente para a construção de modelos
de PPM, vamos elaborar o modelo para este problema em etapas.
Etapa 1: Identificação das variáveis de decisão
O objetivo do problema é determinar as quantidades de cada tipo de bala a ser
produzida de forma a resultar na máxima receita. Portanto, este problema tem
duas variáveis de decisão:
x1 : a quantidade (em kg) a ser produzida de bala de caramenlo
x2 : a quantidade (em kg) a ser produzida de bala de nozes
Etapa 2: Formulação da função objetivo
O critério para a seleção do melhor combinação possı́vel é a receita máxima. Cada
tipo de bala gera uma receita que é o produto do preço de venda pela quantidade
vendida e a função receita é obtida pela soma das contribuições de cada tipo de bala
produzido. Matematicamente, temos:
max z = f (x1 , x2 ) = 10x1 + 13x2
Etapa 3: Formulação das restrições
O problema impõe restrições na quantidade de matéria prima para fabricação dos
doces:
0, 6x1 + 0, 5x2 ≤ 10 (quantidade utilizada de açúcar)
0, 4x1 + 0, 4x2 ≤
0, 1x2 ≤
6 (quantidade utilizada de leite)
1 (quantidade utilizada de nozes)
30
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
Ainda há uma condição implı́cita ao problema que devemos considerar, quais os valores que as variáveis de decisão podem assumir?
Nesta situação estamos
interessados em valores não-negativos que satisfaçam as limitações de matéria-prima.
Devemos também considerar o tipo de variável, neste problema podemos admitir
que a variável xj pode receber qualquer valor real. Assim temos definido o domı́nio
da função objetivo e o critério de não-negatividade: xj ≥ 0,
xj ∈ R
O modelo completo para o problema da produção de balas representado no formato
(2.1) é:
max
s.a. :
z = 10x1 + 13x2




0, 6x1 + 0, 5x2 ≤ 10 (quantidade utilizada de açúcar)







 0, 4x1 + 0, 4x2 ≤ 6 (quantidade utilizada de leite)











0, 1x2 ≤ 1
(quantidade utilizada de nozes)
x1 , x2 ≥ 0
(condição de não-negatividade)
Observe que a condição xj ∈ R foi omitida do modelo final, isto deve-se ao fato que
em modelos de Programação Matemática, por convenção, esta condição é considerada
implı́cita ao modelo. A informação sobre o domı́nio da função constará no modelo caso o
domı́nio seja outro conjunto numérico.
. . . Exemplo 2.2. Localização da antena de transmissão
O Gerente de Projetos da LCL Telecom deve localizar uma antena de retransmissão
para atender a três localidades na Baixada Maranhense: Viana, Penalva e Cajari. Por
problemas técnicos a antena não pode estar a mais de 10 km do centro de cada cidade.
Considerando as localizações relativas indicadas no mapa, determine o melhor posicionamento para a torre.
Sejam (xi , yi ) as coordenadas no plano cartesiano da localização das cidades.
Etapa 1: Identificação das variáveis de decisão
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
31
O objetivo do problema é determinar a localização (x, y) da antena que minimize a
soma das distâncias até as três localidades, as variáveis de decisão já estão definidas:
x: abscissa no plano cartesiano da localização da torre de transmissão
y: ordenada no plano cartesiano da localização da torre de transmissão
Etapa 2: Formulação da função objetivo
Admitamos que a localidade 1 seja Viana, a localidade 2 seja Cajari e a localidade 3 seja Penalva, as coordenadas cartesianas das localidades serão (xi , yi ),
com i = 1, 2, 3. Fixado uma localidade i, a distância entre esta e a antena de
p
transmissão pode ser calculada por (xi − x)2 + (yi − y)2 .
A função distância é obtida pela soma três distâncias entre a antena e as localidades.
min z =
3
X
p
(xi − x)2 + (yi − y)2
i=1
Etapa 3: Formulação das restrições
As restrições técnicas são as únicas limitações do problema:
p
(xi − x)2 + (yi − y)2 ≤ 10,
∀i ∈ {1, 2, 3}
As condições práticas do problema não requer restrições de não-negatividade e as
variáveis de decisão podem assumir valores reais.
32
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
O modelo completo é apresentado a seguir:
min
3
X
p
z=
(xi − x)2 + (yi − y)2
i=1

p



(x1 − x)2 + (y1 − y)2 ≤ 10 (distância a Viana)




p
s.a. :
(x2 − x)2 + (y2 − y)2 ≤ 10 (distância a Cajari)





p

 (x3 − x)2 + (y3 − y)2 ≤ 10 (distância a Penalva)
. . . Exemplo 2.3. O problema da dieta
Um indivı́duo deve seguir uma dieta balanceada por recomendação médica baseada
no consumo de diversos tipos de alimentos de forma a suprir suas necessidades diárias de
energia, que pode variar de 3100 a 3300 kcal, e nutrientes essenciais para a boa saúde. Uma
porção de cada alimento fornece uma porcentagem da Quantidade Diária Recomentada
(QDR) de diferentes nutrientes de acordo com a tabela. Preço e quantidade calórica de
cada porção também são informados na tabela. Deseja-se saber qual a combinação ideal
de alimentos com custo mı́nimo e que satisfaça às necessidades nutricionais.
Alimentos
1
2
3
unidade QDR carne arroz feijão
Valor energético
Proteı́na
kcal
4
5
6
7
pão
ovos laranja leite
225
170
76
300
146
45
160
g
37
35
3
4,8
8
13
0,6
8
Vitamina A
mg
900
7
-
2
-
87
21
99
Vitamina C
mg
300
-
-
3
-
12
59
2
Ferro
mg
10
2,9
1,3
1,6
1
1,3
0,2
0,9
Cálcio
mg
500
5
12
27
16
49
45
285
0,50
0,14
0,19
0,15
0,20
0,10
0,30
Custo (R$)
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
33
Etapa 1: Identificação das variáveis de decisão
O objetivo do problema é determinar uma composição ideal de alimentos com custo
mı́nimo, para calcular o custo de destas combinações é necessário saber o número
de porções diárias de cada alimento, que é um elemento desconhecido do problema.
Portanto as quantidades de porções diárias de cada alimento definirão as variáveis
de decisão deste problema.
Sejam xj : número de porções consumidas do alimento j, j = 1, . . . , 7
Etapa 2: Formulação da função objetivo
O critério para a seleção do melhor combinação possı́vel é o custo mı́nimo. Cada
tipo de alimento gera um custo que é o produto do preço da porção pelo número de
porções consumidas e a função custo é obtida pela soma das contribuições de cada
alimento consumido. Matematicamente, temos:
z = f (x1 , . . . , x7 ) = 0, 5x1 + 0, 14x2 + 0, 19x3 + 0, 15x4 + 0, 2x5 + 0, 1x6 + 0, 3x7
Utilizando a notação vetorial para simplificar: z = f (x) =
7
X
cj x j
j=1
onde cj são os componentes do vetor
c = 0, 50 0, 14 0, 19 0, 15 0, 20 0, 10 0, 30
Etapa 3: Formulação das restrições
O menor custo é obviamente zero, entretanto esta solução não atende a recomendação
médica. O problema impõe algumas condições explicitas que devem ser satisfeitas:
(a) A dieta deve suprir a necessidade diária de energia
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≥ 3100 (mı́nimo kcal)
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≤ 3300 (máximo kcal)
(b) A dieta deve fornecer as quantidades mı́nimas recomendadas de nutrientes
34
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
35x1 + 3x2 + 4, 8x3 + 8x4 + 13x5 + 0, 6x6 + 8x7
≥
7x1 + 2x3 + 87x5 + 21x6 + 99x7
≥ 900 (Vitamina A)
3x3 + 12x5 + 59x6 + 2x7
≥ 300 (Vitamina C)
2, 9x1 + 1, 3x2 + 1, 6x3 + x4 + 1, 3x5 + 0, 2x6 + 0, 9x7 ≥
5x1 + 12x2 + 27x3 + 16x4 + 49x5 + 45x6 + 285x7
37 (Proteı́na)
10 (Ferro)
≥ 500 (Cálcio)
(c) Ainda há uma condição implı́cita ao problema que devemos considerar, quais
os valores que as variáveis de decisão podem assumir? Nesta situação estamos interessados em valores não-negativos que satisfaçam os nı́veis mı́nimos
de nutrientes. Devemos também considerar o tipo de variável, neste problema
podemos admitir que a variável xj pode receber qualquer valor real. Assim
temos definido o domı́nio da função objetivo e o critério de não-negatividade:
xj ≥ 0,
xj ∈ R.
O modelo completo para o problema da dieta representado no formato padrão conforme
(2.1) é:
min
s.a. :
z = 0, 5x1 + 0, 14x2 + 0, 19x3 + 0, 15x4 + 0, 2x5 + 0, 1x6 + 0, 3x7





























225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≥ 3100
225x1 + 170x2 + 76x3 + 300x4 + 146x5 + 45x6 + 160x7 ≤ 3300
35x1 + 3x2 + 4, 8x3 + 8x4 + 13x5 + 0, 6x6 + 8x7
≥
37
7x1 + 2x3 + 87x5 + 21x6 + 99x7
≥
900
≥
300
≥
10
≥
500
≥
0



3x3 + 12x5 + 59x6 + 2x7









2, 9x1 + 1, 3x2 + 1, 6x3 + x4 + 1, 3x5 + 0, 2x6 + 0, 9x7








5x1 + 12x2 + 27x3 + 16x4 + 49x5 + 45x6 + 285x7








xj
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
35
. . . Exemplo 2.4. Distribuição da produção
Uma empresa montadora de eletrônicos produz rádio, toca-CD e aparelhos de DVD
em três fábricas localizadas em Diadema, Ribeirão Preto e Campinas. As quantidades
despendidas na produção de cada produto, em peças por hora, em cada uma das fábricas
são as seguintes:
Rádio
Toca-CD
DVD
Diadema
10
20
20
Ribeirão
20
10
20
Campinas
20
20
10
Os custos de operação por hora das fábricas são R$ 10.000,00, R$ 8.000,00 e
R$ 11.000,00 para Diadema, Ribeirão Preto e Campinas, respectivamente.
A empresa recebeu um pedido de 300 unidades de rádio, 500 unidades de toca-CD
e 600 unidades de aparelho de DVD, como deve distribuir a produção entre suas três
fábricas para cumprir o pedido ao menor custo possı́vel?
Etapa 1: Identificação das variáveis de decisão
O objetivo é distribuir a produção ao menor custo possı́vel, sendo assim deve-se
decidir quanto produzir de cada produto em cada uma das fábricas, o que define as
variáveis de decisão do problema. Sejam:
x1d :
número de
rádios
a produzir na fábrica de Diadema
x2d :
número de
toca-CD
a produzir na fábrica de Diadema
x3d :
número de
DVD
a produzir na fábrica de Diadema
x1r :
número de
rádios
a produzir na fábrica de Ribeirão
x2r :
número de
toca-CD
a produzir na fábrica de Ribeirão
x3r :
número de
DVD
a produzir na fábrica de Ribeirão
x1c :
número de
rádios
a produzir na fábrica de Campinas
36
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
x2c :
número de
toca-CD
a produzir na fábrica de Campinas
x3c :
número de
DVD
a produzir na fábrica de Campinas
Etapa 2: Formulação da função objetivo
O objetivo é primordial é determinar quantas horas cada uma das fábricas deve
dispor para o pedido com o menor custo possı́vel. O custo é dado por
z = f (x, y, z) = 10.000x + 8.000y + 11000z
onde x é o número total de horas que fábrica de Diadema funciona para atender o
pedido, y é o número total de horas da fábrica de Ribeirão e z corresponde ao total
de horas da fábrica de Campinas.
De acordo com a tabela fornecida podemos determinar x em função das variáveis
de decisão x1d , x2d e x3d , y em função de x1r , x2r e x3r e z em função de x1c , x2c e
x3c :
x1d x2d x3d
+
+
= 0, 10x1d + 0, 05x2d + 0, 05x3d
10
20
20
x1r x2r x3r
+
+
= 0, 05x1r + 0, 10x2r + 0, 05x3r
y =
20
10
20
x1c x2c x3c
z =
+
+
= 0, 05x1c + 0, 05x2c + 0, 10x3c
20
20
10
x =
Etapa 3: Formulação das restrições
A limitações explicı́tas do problema são o atendimento da quantidade demandada
no pedido, isto é a soma das produções das três fábricas de um determinado produto
não deve ser inferior à quantidade encomendada:
x1d + x1r + x1c ≥ 300 (encomenda de rádios)
x2d + x2r + x2c ≥ 500 (encomenda de toca-CD)
x3d + x3r + x3c ≥ 600 (encomenda de DVD)
As condições implicı́tas do problema são a não-negatividade e o domı́nio da função
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
37
objetivo restrito ao conjunto dos números inteiros Z.
O modelo completo é:
min
z = 10.000(x1d + x2d + x3d ) + 8.000(x1r + x2r + x3r ) + 11.000(x1c + x2c + x3c )





x1d + x1r + x1c ≥ 300 (encomenda de rádios)








x2d + x2r + x2c ≥ 500 (encomenda de toca-CD)




s.a. :
x2d + x2r + x2c ≥ 600 (encomenda de DVD)







xia ≥ 0
para i = 1, 2, 3 e a = d, r, c









xia ∈ Z
. . . Exemplo 2.5. O caso da Loja dos queijos:
1
A Loja dos Queijos produz e comercializa dois tipos de queijos (Delux e Standard),
muito procurados na época do Natal. Estes queijos são produzidos a partir de uma mistura
de frutas da época e de um queijo especial muito caro. A Loja dos Queijos pode dispor
de 20 kg de mistura de frutas e 60 kg do queijo especial utilizado. Cada kg de Delux
consiste em 0,2 kg da mistura de frutas e 0,8 kg do queijo especial, enquanto que 1 kg de
Standard consiste em 0,2 kg da mistura de frutas, 0,3 kg do queijo especial e 0,5 kg de um
queijo comum, disponı́vel em grande quantidade. De acordo com a experiência da Loja
dos Queijos, foi possı́vel descobrir que a procura de cada um dos dois queijos depende do
preço adotado:
d1 = 190 − 25p1
d2 = 250 − 50p2
onde d representa a procura (em kg), p denota o preço (em u.m./kg), e os ı́ndices 1 e 2
designam os tipos Delux e Standard, respectivamente.
Que quantidade de cada tipo de queijo deverá a Loja dos Queijos preparar, e que
1
Baseado em Bronson & Naadimuthu, 2001.
38
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
preços deverão ser adotados para maximizar a receita e garantir que, após a época do
Natal, nada reste dos dois queijos em estoque?
Variáveis de decisão: x1 : quantidade (em kg) a produzir de queijo tipo Delux
x2 : quantidade (em kg) a produzir de queijo tipo Standard
Objetivo:
Restrições:
max z = p1 x1 + p2 x2
(maximizar a receita)




0, 2x1 + 0, 2x2 ≤ 20 (disponibilidade de frutas)




0, 8x1 + 0, 3x2 ≤ 60 (disponibilidade de queijo especial)







x1 , x2 ≥ 0 (condição de não-negatividade)
O modelo ainda não está completo pois é necessário garantir que toda a produção seja
vendida, para tanto a produção xi não deve ultrapassar a demanda di , isto é,
xi ≤ d i ,
i = 1, 2
Considerando as equações de demanda, temos:
x1 ≤ 190 − 25p1
e x2 ≤ 250 − 50p2
Reescrevendo as inequações, obtemos as seguintes restrições de demanda:
x1 + 25p1 ≤ 190
x2 + 50p2 ≤ 250
Para simplificar o problema, o objetivo também deve ser reescrito somente em função
das variáveis de decisão. Observe que para quaisquer valores fixos de x1 e x2 a função
z = p1 x1 + p2 x2 aumenta conforme aumentarem os preços p1 e p2 , assim para maximizar
z, p1 e p2 devem assumir valores máximos, isto é assumir valores tais que as inequações
2.2. PROBLEMAS DE PROGRAMAÇÃO MATEMÁTICA
39
referente às restrições de demanda se tornem equações. Desta forma, os preços podem ser
assumidos como:
p1 =
190 − x1
= 7, 6 − 0, 04x1
25
p2 =
250 − x2
= 5 − 0, 02x2
50
Substituindo os valores dos preços na função objetivo temos:
z = (7, 6 − 0, 04x1 )x1 + (5 − 0, 02x2 )x2
= 7, 6x1 + 5x2 − 0, 04x21 − 0, 02x22
O modelo completo é apresentado a seguir e deve-se notar que as restrições de demanda
foram incorporadas na construção da função objetivo e não serão incorporadas às restrições
do problema.
z = 7, 6x1 + 5x2 − 0, 04x21 − 0, 02x22
max
s.a. :




0, 2x1 + 0, 2x2 ≤ 20 (disponibilidade de frutas)




0, 8x1 + 0, 3x2 ≤ 60 (disponibilidade de queijo especial)







x1 , x2 ≥ 0 (condição de não-negatividade)
. . . Exemplo 2.6. Um problema de transporte:
Uma companhia de panificação pode produzir pão de forma em duas fábricas, de
acordo com a tabela:
Capacidade de produção
Custo de Produção
Fábrica
(pães de forma)
(u.m./pão de forma)
A
2500
2,3
B
2100
2,5
Quatro redes de restaurantes pretendem comprar pães de forma, suas necessidades e
os preços que estão dispostos a pagar são os seguintes:
40
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
Rede de
Necessidade máxima
Preço máximo
Restaurantes
(pães de forma)
(u.m./pão de forma)
1
1800
3,9
2
2300
3,7
3
550
4,0
4
1750
3,6
O custo (em u.m.) de transporte de uma unidade de pão de forma de cada padaria
para cada rede de restaurantes é dado na tabela seguinte.
Restaurantes
Padaria
1
2
3
4
A
0,6
0,8
1,1
0,9
B
1,2
0,6
0,8
0,5
Determine o plano ótimo de fornecimento de pães de forma a maximizar o lucro total
da empresa de panificação.
Variáveis de decisão: xij : quantidade a ser transportada (em unidades)
da origem i = A, B para o destino j = 1, 2, 3, 4
De acordo com tabela de preços, a função receita será:
r = 3, 9xi1 + 3, 7xi2 + 4xi3 + 3, 6xi4
para i = A, B
A seguir é apresentado o modelo para maximização da função lucro obtida subtraindose dos preços unitários os custos de produção e de transporte.
Objetivo:
max z = xA1 + 0, 2xB1 + 0, 6xA2 + 0, 6xB2 + . . .
. . . + 0, 6xA3 + 0, 7xB3 + 0, 4xA4 + 0, 6xB4
2.3. LISTA DE PROBLEMAS


P4



j=1 xAj





P4



j=1 xBj








xA1 + xB1




Restrições:
xA2 + xB2







xA3 + xB3









xA4 + xB4








xij
2.3
41
≤ 2500 (capacidade de produção da fábrica A)
≤ 2100 (capacidade de produção da fábrica B)
≤ 1800 (necessidade do restaurante 1)
≤ 2300 (necessidade do restaurante 2)
≤
550 (necessidade do restaurante 3)
≤ 1750 (necessidade do restaurante 4)
≥
0 (condição de não-negatividade)
Lista de Problemas
Para cada PPM abaixo, elabore um modelo do sistema descrito de acordo com (2.1):
1. Sol Ltda. faz dois tipos de brinquedos de madeira: soldados e trens. Um soldado
é vendido por R$ 27,00 e usa R$ 10,00 de matéria prima. Cada soldado produzido
aumenta os custos de Sol Ltda. em R$ 14,00. Um trem é vendido por R$ 21,00 e
usa R$ 9,00 de matéria prima. O custo adicional para construı́-lo é de R$ 10,00.
Para construir os soldados e os trens de madeira é necessário dois tipos de trabalho:
carpintaria e acabamento. Um soldado precisa de duas horas de acabamento e
um hora de carpintaria. Um trem necessita de uma hora de cada. Cada semana
Sol Ltda. pode obter toda matéria-prima necessária, mas somente 100 horas de
acabamento e 80 horas na seção de carpintaria.
A demanda de trem é ilimitada mas somente 40 soldados são comprados por semana.
Sol Ltda. deseja maximizar o seu lucro.
2. Uma importante companhia petrolı́fera pretende construir uma refinaria que será
abastecida por três cidades portuárias A,B e C. O porto A está situado a 300 km a
leste e a 400 km a norte do porto B; o porto C está situado a 100 km a sul do porto
B. Determine a localização da refinaria que minimiza o comprimento total das vias
necessárias para interligar a refinaria aos três portos.
42
CAPÍTULO 2. PROGRAMAÇÃO MATEMÁTICA
3. Uma empresa produz três tipos de portas a partir de um determinado material.
Sabendo que diariamente a empresa dispõe de 500 kg de material e 600 horas de
trabalho, determinar um plano ótimo de produção que corresponda ao maior lucro.
A tabela seguinte indica a quantidade de material e horas de trabalho necessárias
para a produção de uma porta de cada tipo, assim como o lucro unitário de cada
uma delas:
Recursos
Quantidade material
Porta 1
Porta 2
Porta 3
8 kg
4 kg
3 kg
7
6
8
R$ 50,00
R$ 40,00
R$ 55,00
Horas de trabalho
Lucro unitário
4. A tabela de alimentação utilizada numa determinada loja de animais de estimação
especifica as seguintes necessidades mı́nimas para um hamster: 70 unidades de
proteı́na, 100 unidades de hidratos de carbono, 20 unidades de gordura. Há seis tipos
de rações disponı́veis na loja cujas caracterı́sticas são dadas no quadro seguinte:
Proteı́nas
H.Carbono
Gordura
(unidades/kg) (unidades/kg)
Custo
Ração
(unidades/kg)
(u.m./kg)
A
20
50
4
2
B
30
30
9
3
C
40
20
11
5
D
40
25
10
6
E
45
50
9
8
F
30
20
10
8
Como deve ser feita uma mistura que satisfaça os requisitos da alimentação diária
de um hamster a um custo mı́nimo?
2.3. LISTA DE PROBLEMAS
43
5. Uma rede de depósitos de material de construção tem 4 lojas que devem ser abastecidas com 50 m3 (loja 1), 80 m3 (loja 2), 40 m3 (loja 3) e 100 m3 (loja 4) de areia
grossa. Essa areia pode ser carregada em 3 portos P1, P2 e P3, cujas distâncias às
lojas estão no quadro (em km): O caminhão pode transportar 10 m3 por viagem.
L1
L2
L3 L4
P1
30
20
24
18
P2
12
36
30
24
P3
8
15
25
20
Os portos tem areia para suprir qualquer demanda. Estabelecer um plano de transporte que minimize a distância total percorrida entre os portos e as lojas e que supra
as necessidades das lojas.
6. O departamento de marketing de uma empresa estuda a forma mais econômica de
aumentar em 30% as vendas de seus dois produtos P1 e P2. As alternativas são:
a) Investir em um programa institucional com outras empresas do mesmo ramo.
Esse programa requer um investimento mı́nimo de $3.000,00 e deve proporcionar um aumento de 3% nas vendas de cada produto, para cada $1.000,00
investidos.
b) Investir diretamente na divulgação dos produtos. Cada $1.000,00 investidos em
P1 retornam um aumento de 4% nas vendas, enquanto que para P2 o retorno
é de 10%.
A empresa dispõe de $10.000,00 para esse empreendimento. Quanto deverá destinar
a cada atividade?
CAPÍTULO
3
PROGRAMAÇÃO LINEAR
O objetivo da Programação Linear (PL) é encontrar a melhor solução para problemas
que admitam modelos representados por funções e inequações lineares, neste sentido o
termo programação significa que existe um planejamento das atividades e o termo linear
refere-se à linearidade nas equações envolvidas na modelagem do problema. Conforme já
visto no capı́tulo anterior, um Problema de Programação Linear (PPL) é um Problema
de Programação Matemática cuja função objetivo e todas as restrições são lineares relativamente às variáveis de decisão. Especificamente, as hipóteses seguintes caracterizam
um PPL:
Certeza: Assume que o modelo seja determinı́stico, isto é, todos os parâmetros são
constantes conhecidas.
Proporcionalidade: Admite que a contribuição individual de cada variável de decisão,
tanto na função objetivo quanto nas restrições, seja diretamente proporcional ao
valor da variável.
Aditividade: Exige que a contribuição total na função objetivo e nas restrições seja
soma direta da contribuições individuais de cada variável de decisão, não podendo
haver interdependência entre as mesmas.
Divisibilidade: As variáveis de decisão podem assumir valores fracionários.
44
3.1. ESTRUTURAÇÃO DE MODELOS LINEARES
3.1
45
Estruturação de Modelos Lineares
De acordo com as hipóteses de proporcionalidade e aditividade, a função objetivo e as
restrições de um PPL podem ser apresentadas da seguinte forma:
f (x1 , x2 , . . . , xn ) = c1 x1 + c2 x2 + . . . + cn xn
gi (x1 , x2 , . . . , xn ) ∼ ai1 x1 + ai2 x2 + . . . + ain xn
onde os coeficientes aij e cj são constantes para i = 1, . . . , m e j = 1, . . . , n, e o sinal ∼
pode ser substituido pelos sinais de = ou ≤ ou ≥, indistintamente.
De acordo com o formato (2.1), um modelo de PPL apresenta a seguinte estrutura:
min ou max
s.a. :
z = c1 x 1 + c2 x 2 + . . . + cn x n

















a11 x1 + a12 x2 + . . . + a1n xn ∼ b1
a21 x1 + a22 x2 + . . . + a2n xn ∼ b2
..
.
(3.1)







am1 x1 + am2 x2 + . . . + amn xn ∼ bm









x1 , x2 , . . . , xn ≥ 0
Apesar da aparente limitação do modelo, existem aplicações de PL nas mais diversas
áreas. De fato, é uma das técnicas mais utilizadas em PO justamente pela simplicidade
do modelo envolvido e facilidade para resolução de problemas utilizando técnicas gráficas,
algébricas ou algoritmı́cas.
Como exemplos de PPL citamos os exemplos 1.6, 2.1, 2.3, 2.4 e 2.6 apresentados nos
capı́tulos anteriores, utilizaremos o problema da produção de balas exposto no exemplo
2.1 para ilustrar as hipóteses de linearidade.
. . . Exemplo 3.1.
Considere que doceira deseja abrir um pequeno negócio para produção de balas. A
46
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
princı́pio ela está considerando produzir dois tipos de balas: caramelo e nozes. Na
produção são utilizados três ingredientes: leite, açúcar e nozes. A doceira tem em estoque 10kg de açúcar, 1kg de nozes e 6l de leite. A composição da bala de caramelo é:
40% de leite e 60% de açúcar, e para as balas de nozes os ingredientes devem ser misturados na seguinte proporção: 40% de leite, 50% de açúcar e 10% de nozes. Cada quilo de
bala de caramelo pode ser vendido a R$10,00 enquanto um quilo de bala de nozes pode
ser vendido por R$13,00. Qual deve ser a produção de cada tipo de bala para obter a
maior receita?
O modelo completo é:
max
s.a. :
z = 10x1 + 13x2




0, 6x1 + 0, 5x2 ≤ 10 (qtde.utilizada de açúcar)







 0, 4x1 + 0, 4x2 ≤ 6 (qtde. utilizada de leite)











0, 1x2 ≤ 1
(qtde. utilizada de nozes)
x1 , x2 ≥ 0
(não-negatividade)
1. Certeza: No contexto do Exemplo 2.1, tanto preços de venda dos produtos, como
a quantidade a ser utilizada de cada ingrediente para fabricação dos doces são
constantes conhecidas. Entretanto este é um fato rara na maioria das aplicações
práticas, em geral utiliza-se como coeficientes para o modelo de textitPPL aproximações do valor médio das distribuições de probabilidade quando os respectivos
desvios-padrões forem suficientemente pequenos, caso contrário, o problema não
poderá ser modelado como PPL.
2. Proporcionalidade: Se a doceira vender 1kg de bala de caramelado ela receberá
R$10, 00, se vender 2kg obterá R$20, 00, se vender x1 kg obterá 10x1 . O valor obtido
na venda de balas de caramelo é proporcional à quantidade vendida e preço de venda
do produto é a constante de proporcionalidade. A receita referente à produção
de bala de nozes é 13x2 , sendo o produto da constante de proporcionalidade 13
pela quantidade vendida. Portanto, a receita referente à determinado produto é
proporcional a quantidade vendida, se a doceira conceder algum tipo de desconto
3.1. ESTRUTURAÇÃO DE MODELOS LINEARES
47
quando a quantidade adquirida ultrapassar certo patamar, a receita não será mais
proporcional às quantidades vendidas e a função receita se tornará não-linear. De
maneira análoga, para produzir 1kg de bala de caramelo utiliza-se 0, 6kg de açúcar,
para produzir o dobro necessita-se do dobro de açúcar, sendo assim a quantidade
utilizada do ingrediente é proporcional a quantidade produzida. Similarmente para
os outros ingredientes, constatamos a proporcionalidade em todas as restrições do
problema.
3. Aditividade: Para a função objetivo, a receita total é a soma das receitas referentes
a cada um dos produtos. Também para as restrições o todo é igual a soma das
partes, o total consumido de açúcar é a soma do açúcar utilizado para produção
da bala de caramelo e do açúcar gasto na produção da bala de nozes. Analogamente para os demais ingredientes. O comportamento aditivo é bastante comum,
entretanto há situações onde não é possı́vel assumir o princı́pio da aditividade, por
exemplo, se os produtos competirem entre si de forma que o aumento nas vendas
de um provoque diminuição na procura do outro, a hipótese de aditividade não será
satisfeita. Outro exemplo ocorre com reações quı́micas, se adicionarmos a um litro
de água o equivalente a 0,1 litro de açúcar o volume resultante não será 1,1 litro de
água doce.
4. Divisibilidade: Neste problema é possı́vel vender 1kg de bala como 0, 5kg. Dependendo do problema, as variáveis de decisão deverão assumir valores inteiros, neste
caso é ainda possı́vel modelar o problema como linear utilizando arredondamento,
entretanto este procedimento pode resultar em valores distorcidos, requerendo a
utilização de algoritmos especı́ficos de programação inteira.
Às etapas estabelecidas anteriormente para modelar um PPM, é necessário acrescentar
a verificação das hipóteses de linearidade. Portanto, para proceder a análise do problema
e formular um modelo de PPL o analista seguir as seguintes fases:
X Identificação das variáveis de decisão
X Identificação da função objetivo
48
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
X Identificação das restrições
X Verificação dos axiomas de linearidade
X Formulação matemática no formato padronizado de acordo com (4.1)
3.2
Resolução Gráfica de um PPL
Após a obtenção da formulação matemática é preciso se preocupar com a resolução do
problema de otimização. Em particular, PPL´s com duas variáveis permitem visualização
geométrica, sendo assim, a princı́pio recorreremos ao método gráfico para resolver problemas mais simples. O método gráfico consiste em, primeiramente determinar o conjunto
de todas as possı́veis soluções para o problema, determinado pelo sistema de restrições, e
dentre estas identificar aquela onde ocorre o valor ótimo, avaliado pela função objetivo.
3.2.1
Representação Gráfica das Restrições
O espaço das soluções de problemas com duas variáveis é o plano R2 . Dois pontos distintos
A = (xa , ya ) e B = (xb , yb ) do plano determinam um reta, e pelas condições de alinhamento, um ponto qualquer P = (x, y) ∈ R2 pertence à reta AB que passa por A e B, se
e somente se, a inclinação da reta AB for a mesma inclinação da reta AP . Assim, temos:
y − ya
yb − ya
=
x b − xa
x − xa
⇐⇒
(yb − ya )(x − xa ) = (y − ya )(xb − xa )
⇐⇒
(yb − ya )x − (yb − ya )xa = (xb − xa )y − (xb − xa )ya
⇐⇒
(yb − ya )x − (xb − xa )y = xa yb − xa ya − xb ya + xa ya ⇐⇒
(y − y ) x + (xa − xb ) y = xa yb − xb ya
{z
}
|
| b {z a}
| {z }
a
b
c
3.2. RESOLUÇÃO GRÁFICA DE UM PPL
49
Sendo assim, toda reta no plano tem equação geral da forma:
ax + by = c
(3.2)
onde a,b e c são constantes que podem assumir qualquer valor real. E, reciprocamente,
toda equação deste tipo representa uma reta no plano R2 .
Uma reta divide o plano em duas regiões denominadas semiplanos, e as inequações
ax + by > c e ax + by < c
representam semiplanos abertos distintos, enquanto as inequações
ax + by ≥ c e ax + by ≤ c
determinam semiplanos fechados cuja interseção é a reta ax + by = c.
. . . Exemplo 3.2.
Considere a equação da reta r : −2x + y = 1, representada graficamente abaixo em
linhas pontilhadas. A região hachurada é a representação gráfica do semiplano aberto
−2x + y < 1
Se um semiplano é a representação gráfica de uma inequação em duas variáveis, então
a representação gráfica de um sistema de inequações lineares em duas variáveis será a
intersecção dos semiplanos correspondentes a cada inequação. As restrições de um PPL
50
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
juntamente com as condições de não-negatividade é um conjunto de semiplanos cuja
intersecção determina um conjunto de pontos do R2 denominado Região das Soluções
Viáveis ou simplesmente Região Viável (RV).
. . . Exemplo 3.3.
A empresa TécniBOLA S.A. tem como única atividade a fabricação de bolas, sendo
todas elas em couro e fabricadas segundo os processos primordiais. Atualmente fabrica
dois produtos, a bola de futebol Catechumbo e a bola de vólei Voleitok. Ambos os produtos
são feitos do mesmo material, variando apenas na dimensão, tipo de costuras e rotulagem.
Os recursos que definem a fabricação das bolas são: o corte do couro, o trabalho de
costura, a pintura de inscrições na bola e preparação final. Esta última é composta pelas
atividades de enchimento, controle de qualidade (inspeção visual, calibração e pesagem)
e embalagem.
Os dados fornecidos pela empresa referentes à quantidade de recursos necessários para
a produção de cada tipo de bola e as quantidades disponı́veis para o dia de amanhã são
os indicados na tabela:
Recursos
unid. Voleitok
Catechumbo
Disponibilidade
Couro
m2
0,25
0,3
ilimitada
Linha
m
2,5
4
ilimitada
Câmera de Ar
un
1
1
25
Embalagens
un
1
1
ilimitada
Operação de Corte
min
2
8
ilimitada
Operação de Costura
min
9
25
480
Operação de Logotipagem
min
1,5
1
ilimitada
Operações de Finalização
min
11
6
240
Para a tomada de decisão, a empresa disponibilizou informações a respeito dos valores
monetários envolvidos (em u.m.) nos seus produtos, apresentados a seguir:
3.2. RESOLUÇÃO GRÁFICA DE UM PPL
Bola
51
Custo de Produção Preço de Venda
Catechumbo
26,00
32,50
Voleitok
15,00
25,00
Como deve ser distribuı́da a produção amanhã de forma a maximizar o lucro, tendo
em conta os recursos existentes?
De acordo com o objetivo do problema, as variáveis de decisão podem ser assim
definidas:
x1 : número de bolas Catechumbo a ser produzido amanhã.
x2 : número de bolas Voleitok a ser produzido amanhã.
Utilizando as hipóteses de linearidade, obtemos o seguinte modelo:
max
s.a. :
z = 6, 5x1 + 10x2 (Lucro Total)




x1 + x2 ≤ 25 (restrição de câmera de ar)







 25x1 + 9x2 ≤ 480 (restrição de operação de costura)



6x1 + 11x2 ≤ 240 (restrição de operações de finalização)








x1 , x2 ≥ 0
(restrição de não-negatividade)
Neste caso, estamos admitindo a hipótese de divisibilidade, entretando o problema requer variáveis inteiras, na próxima seção este PPL será resolvido com as técnicas usuais,
mas a resposta final deverá respeitar a imposição prática de quantidades inteiras, utilizando arredondamento, se necessário.
. . . Exemplo 3.4. Construir a região viável do problema da TécniBOLA S.A., apresentado no exemplo 3.3, cujo modelo é:
52
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
max
s.a. :
z = 6, 5x1 + 10x2 (Lucro Total)




x1 + x2 ≤ 25 (restrição de câmera de ar)







 25x1 + 9x2 ≤ 480 (restrição de operação de costura)
(1)
(2)



6x1 + 11x2 ≤ 240 (restrição de operações de finalização)
(3)








x1 , x2 ≥ 0
(restrição de não-negatividade)
(4) e (5)
Somente as restrições do problema são consideradas para determinar a região viável,
sendo assim as restrições foram identificadas e numeradas. A seguir é apresentada a
representação gráfica de cada semiplano fechado correspondente às restrições do problema.
(1) x1 + x2 ≤ 25
A reta r1 : x1 + x2 = 25 determina o semiplano correspondente à primeira restrição, e
pode ser determinada por dois de seus pontos,
da seguinte maneira:
se x1 = 0 então x2 = 25
∴ (0; 25) ∈ r1
se x2 = 0 então x1 = 25
∴ (25; 0) ∈ r1
(2) 25x1 + 9x2 ≤ 480
(3) 6x1 + 11x2 ≤ 240
(4) x1 ≥ 0
(5) x2 ≥ 0
A intersecção dos cinco semiplanos definidos pelas restrições (1), (2), (3), (4) e (5),
determina a região das possı́veis soluções do problema e está representada pela região
hachurada abaixo:
3.2. RESOLUÇÃO GRÁFICA DE UM PPL
53
O polı́gono ABCDE é o conjunto de todos os pontos X = (x1 , x2 ) que satisfazem
todas as restrições simultaneamente. Sendo assim, toda combinação possı́vel da produção
de x1 unidades de bolas Catechumbo e de x2 unidades de bolas Voleitok será um ponto
54
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
do polı́gono ABCDE, do seu interior ou ponto de fronteira.
3.2.2
Representação Gráfica da Função Objetivo
Funções lineares com duas variáveis do tipo z = f (x1 , x2 ) = c1 x1 + c2 x2 são geometricamente planos em R3 , e somente admitem máximo e/ou mı́nimo se estiverem sujeitas a
restrições, como no caso de um PPL. As curvas de nı́vel desse tipo de função são retas
paralelas que crescem monotonamente na direção do gradiente
∇f (x1 , x2 ) =
∂f ∂f
,
∂x1 ∂x2
A cada ponto do conjunto de soluções viáveis está associada uma, e somente uma, reta
da famı́lia de retas paralelas correspondente à função objetivo. E solucionar graficamente
um PPL é determinar quais pontos da RV retornam o melhor valor para a função objetivo.
A origem do sistema de coordenadas é o único ponto crı́tico de funções lineares, para
o caso especı́fico de PPL com duas variáveis o ponto crı́tico é (0, 0), que é um dos vértices
da RV e qualquer outro ponto extremo da função objetivo deve necessariamente estar
na fronteira da região delimitada pelas restrições. Para encontrar tais pontos deve-se
percorrer a famı́lia de retas paralelas no sentido do gradiente.
Considere um ponto arbitrário P ∈ RV e a reta z = c passando por P . Se P for
um ponto interior do polı́gono, será possı́vel melhorar o valor da função objetivo porque
existem pontos de RV no semiplano determinado por z = c e pelo gradiente. Para
3.2. RESOLUÇÃO GRÁFICA DE UM PPL
55
melhorar este valor basta tomar outro ponto de RV localizado à direita de P e traçar o
representante da famı́lia de retas paralelas que passa por este ponto retornando maior
valor para a função objetivo. Se, por outro lado, P for tomado de maneira que não exista
nenhuma outra solução viável situada no semiplano à direita então não será mais possı́vel
melhorar o valor da função objetivo e a solução ótima foi determinada.
A solução do problema foi obtida tangenciando-se à direita o polı́gono das soluções
viáveis e este fato implica que a solução ótima, quando existe, localiza-se em ao menos
um dos vértices de RV.
O procedimento de busca pelo vértice ótimo é análogo para problemas de minimização,
entretanto o sentido da busca pela solução do problema deve seguir a direção contrária
ao crescimento indicado pelo vetor gradiente.
. . . Exemplo 3.5. Resolver graficamente o problema da TécniBOLA S.A., apresentado
no exemplo 3.2
Na figura abaixo estão representadas algumas retas paralelas correspondentes à função
objetivo z = 6, 5x1 + 10x2 para z = 0, z = −100, z = 100 e z = c.
A reta z = c pode ser deslocada até atingir o vértice C, onde não será mais possı́vel aumentar o valor da função objetivo respeitando todas as restrições do problema. Portanto,
o ponto C é o ponto onde o valor de z é máximo nas condições do PPL.
56
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
A solução ótima do problema pode ser obtida calculando-se as coordenadas do vértice
C, que é o resultado da intersecção das retas correspondentes às restrições (1) e (3). Sendo
assim, as coordenadas de C é a solução do seguinte sistema linear de ordem 2.
(
x1 + x2
=
25
6x1 + 11x2 = 240
cuja solução é: x1 = 7 e x2 = 18.
Portanto a solução ótima do PPL é: deverão ser produzidas amanhã 7 bolas Catechumbo e 18 bolas Voleitok para obter um lucro máximo de $ 225,50.
3.2.3
Soluções do Modelo
As condições para existência de solução para um PPL é garantida pelo seguinte teorema:
TEOREMA 3.1. (Teorema do Valor Extremo) Se f (x1 , x2 , . . . , xn ) é contı́nua em um
subconjunto fechado e limitado do Rn , então f atinge valores globais de máximo e mı́nimo.
Como funções lineares são contı́nuas, se o conjunto das soluções viáveis, para o caso
especı́fico do R2 , formar um polı́gono fechado então o problema admite solução.
Ao resolver graficamente um PPL em duas variáveis, três situações podem ocorrer:
1. RV é um conjunto vazio
Neste caso, as restrições são conflitantes e o PPL não admite solução.
2. RV é não vazio e limitado
O PPL tem solução ótima, única ou não.
3.2. RESOLUÇÃO GRÁFICA DE UM PPL
57
(a) O problema tem uma única solução ótima.
(b) O problema tem múltiplas soluções ótimas, isto é, todos os infinitos pontos de
um segmento de reta são soluções ótimas, e dão o mesmo valor para a função
objetivo.
(a)
(b)
3. RV é não vazio e ilimitado
Duas situações podem ocorrer:
(a) O PPL tem solução ótima, única ou não.
(b) O PPL não tem ótimo finito, o valor a função objetivo cresce indefinidamente
no sentido favorável.
(a)
(b)
Roteiro 58
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
De acordo com o que foi estudado até aqui, a resolução gráfica de um modelo de PPL
com apenas duas variáveis segue os seguintes passos:
1. Construir o plano cartesiano, tomando como eixos as variáveis de decisão;
2. Determinar os semiplanos correspondentes às restrições para delimitar a região
viável;
3. Traçar uma reta referência qualquer com a inclinação da função objetivo;
4. Traçar retas paralelas à referência no sentido de crescimento da função (maximização
da função) até tangenciar a região viável. O ponto ótimo, se existir, será um vértice
ou um lado da região viável.
Ainda um PPL com três variáveis é possı́vel de ser resolvido graficamente, embora
exija habilidade em desenho e boa visão espacial. Problemas com mais que três variáveis
necessitam de métodos algébricos para serem resolvidos. O interesse maior em estudar o
método gráfico está em, através da representação gráfica, intuir propriedades teóricas e
delinear um método de resolução algébrica que possa ser utilizado em problemas com um
número qualquer de variáveis.
3.3
Lista de Problemas
Para cada item abaixo, modele o problema de acordo com as hipóteses de linearidade e
resolva graficamente os PPL com duas variáveis.
1. Certa empresa fabrica 2 produtos P1 e P2. O lucro por unidade de P1 é de 100 u.m.
e o lucro unitário de P2 é de 150 u.m. A empresa necessita de 2 horas para fabricar
uma unidade de P1 e 3 horas para fabricar uma unidade de P2. O tempo mensal
disponı́vel para essas atividades é de 120 horas. As demandas esperadas para os
dois produtos levaram a empresa a decidir que os montantes produzidos de P1 e P2
3.3. LISTA DE PROBLEMAS
59
não devem ultrapassar 40 unidades de P1 e 30 unidades de P2 por mês. Qual deve
ser o sistema de produção mensal para maximizar o lucro da empresa?
2. 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 uma unidade de cinto. Sabendo-se que o
total disponı́vel de couro é de 6 unidades e que o lucro unitário por sapato é de 5
u.m. e o do cinto é de 2 u.m. Qual deve ser o sistema de produção do sapateiro, se
o objetivo é maximizar o seu lucro por hora?
3. Um pizzaiolo trabalha 8h por dia e faz 16 pizzas por hora, caso faça somente pizzas,
e 9 calzones por hora, se fizer somente calzones. Ele gasta 40gr de queijo para
preparar uma pizza e 60gr de queijo para fazer um calzone. Sabendo-se que o total
disponı́vel de queijo é de 5kg por dia, e que a pizza é vendida a R$18,00 e o calzone
a R$22,00, pergunta-se: quantas unidade de pizzas e calzones uma pizzaria com três
pizzaiolos deve vender diariamente para maximizar a sua receita?
4. Um vendedor de frutas pode transportar 800 caixas de frutas para sua região de
vendas. Ele necessita transportar 200 caixas de laranjas a 20 u.m. de lucro por
caixa, pelo menos 100 caixas de pêssegos a 10 u.m. de lucro por caixa, e no máximo
200 caixas de tangerina a 30 u.m. de lucro por caixa. De que forma deverá ele
carregar o caminhão para obter o lucro máximo?
5. Uma rede de televisão local tem o seguinte problema: foi descoberto que o programa
A com 20 minutos de música e 1 minuto de propaganda chama a atenção de 30.000
telespectadores, enquanto o programa B, com 10 minutos de música e 1 minuto de
propaganda chama a atenção de 10.000 telespectadores. No decorrer de uma semana,
o patrocinador insiste no uso de no mı́nimo, 5 minutos para sua propaganda e que
não há verba para mais de 80 minutos de música. Quantas vezes por semana cada
programa deve ser levado ao ar para obter o número máximo de telespectadores?
6. Uma empresa fabrica 2 modelos de cintos de couro. O modelo M1, de melhor
qualidade, requer o dobro de tempo de fabricação em relação ao modelo M2. Se
60
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
todos os cintos fosse do modelo M2, a empresa poderia produzir 1.000 unidades por
dia. A disponibilidade de couro permite fabricar 800 cintos de ambos os modelos
por dia. Os cintos empregam fivelas diferentes, cuja disponibilidade diária é de 400
para M1 e 700 para M2. Os lucros unitários são de $4,00 para M1 e $3,00 para M2.
Qual o programa ótimo de produção que maximiza o lucro total diário da empresa?
7. Um empresa, após um processo de racionalização de produção, ficou com disponibilidade de 3 recursos produtivos, R1, R2 e R3. Um estudo sobre o uso desses
recursos indicou a possibilidade de se fabricar 2 produtos P1 e P2. Levantando
os custos e consultando o departamento de vendas sobre o preço de colocação no
mercado, verificou-se que P1 daria um lucro de $120,00 por unidade e P2, $150,00
por unidade. O departamento de produção forneceu a seguinte tabela de uso de
recursos:
Produto
P1
P2
Disponibilidade de
recursos por mês
R1 p.u.
2
4
R2 p.u.
3
2
R3 p.u.
5
3
100
90
120
Que produção mensal de P1 e P2 traz o maior lucro para empresa?
8. Um fazendeiro está estudando a divisão de sua propriedade nas seguintes atividades
produtivas:
- A (Arrendamento): Destinar certa quantidade de sua propriedade para a
plantação de cana-de-açúcar, a uma usina local, que se encarrega da atividade
e paga pelo aluguel da terra $300,00 por alqueire por ano.
- P (Pecuária): Usar outra parte para a criação de gado de corte. A recuperação
das pastagens requer adubação (100 kg/Alq) e irrigação (100.000 litros/Alq)
por ano. O lucro estimado nessa atividade é de $400,00 por alqueire por ano.
- S (Plantio de Soja): Usar uma terceira parte para o plantio de soja. Essa
cultura requer 200 kg por alqueire de adubos e 200.000 litros de água por
alqueire para irrigação por ano. O lucro estimado nessa atividade é de $500,00
por alqueire por ano.
3.3. LISTA DE PROBLEMAS
61
Sabendo que há disponibilidade de 12.750.000 litros de água, 14.000 kg de adubo e
100 alqueires de terra por ano, quantos alqueires deverá destinar a cada atividade
para proporcionar o melhor retorno?
9. Um indivı́duo quer investir $ 5.000,00 no próximo ano em dois tipos de investimento:
o investimento A rende 5% e o investimento B rende 8%. Pesquisas de mercado,
recomendam uma alocação de no mı́nimo 25% em A e no máximo 50% em B. Além
do mais o investimento em A deve ser no mı́nimo metade do investimento em B.
Como o fundo deveria ser alocado aos dois investimentos?
10. Uma liga especial constituı́da de ferro, carvão, silı́cio e nı́quel pode ser obtida usando
a mistura desses minerais puros além de 2 tipos de materiais recuperados:
Material Recuperado 1 (MR1) - Composição:



ferro - 60%



carvão - 20% custo por kg $0,20 Material Recuperado 2 (MR2) 



 silı́cio - 20%



ferro - 70%





 carvão - 20%
Composição:


silı́cio - 5%





 nı́quel - 5%
custo por kg $0,25
A liga deve ter a seguinte composição final
Matéria-prima % mı́nima % máxima
ferro
60
65
carvão
15
20
silı́cio
15
20
nı́quel
5
8
O custo dos materiais puros (por kg) são: ferro $0,30; carvão $0,20; silı́cio $0,28;
nı́quel $0,50. Qual deverá ser a composição da mistura em termos dos materiais
disponı́veis, com menor custo por kilo?
62
CAPÍTULO 3. PROGRAMAÇÃO LINEAR
11. A indústria Alumilâminas S/A iniciou suas operações em janeiro de 2006 e já vem
conquistando espaço no mercado de laminados brasileiros, tendo contratos fechados
de fornecimento para todos os 3 tipos diferentes de lâminas de alumı́nio que fabrica:
espessuras fina, média ou grossa. Toda a produção da companhia é realizada em
duas fábricas, uma localizada em São Paulo e a outra no Rio de Janeiro. Segundo
os contratos fechados, a empresa precisa entregar 16 toneladas de lâminas finas, 6
toneladas de lâminas médias e 28 toneladas de lâminas grossas. Devido à qualidade
dos produtos de Alumilâminas S/A, há uma demanda extra para cada tipo de
lâminas. A fábrica de São Paulo tem um custo de produção diária de R$ 100.000,00
para uma capacidade produtiva de 8 toneladas de lâminas finas, 1 tonelada de
lâminas médias, 2 toneladas de lâminas grossas por dia. O custo de produção diário
da fábrica do Rio de Janeiro é de R$ 200.000,00 para uma produção de 2 toneladas
de lâminas finas, 1 tonelada de lâminas médias, 7 toneladas de lâminas grossas.
Quantos dias cada uma das fábricas deverá operar para atender aos pedidos ao
menor custo possı́vel?
12. Uma companhia de transporte tem dois tipos de caminhões: O tipo “A”tem 2m3
de espaço refrigerado e 3m3 de espaço não refrigerado; tipo “B”tem 2m3 de espaço
refrigerado e 1m3 de espaço não refrigerado. O cliente quer transportar um produto
que necessitará 16m3 de espaço refrigerado e 12m3 de espaço não refrigerado. A
companhia calcula em 1.100 litros o consumo de combustı́vel para a viagem com o
caminhão “A”e 750 litros para o caminhão “B”. Quantos caminhões de cada tipo
deverão ser usados no transporte do produto, com o menor consumo de combustı́vel?
13. A empresa Have Fun S/A. produz uma bebida energética muito consumida pelos
freqüentadores de danceterias noturnas. Dois componentes utilizados na preparação
da bebida são soluções compradas de laboratórios terceirizados - solução Red e a
solução Blue - e que proveem os principais ingredientes ativos do energético: extrato
de guaraná e cafeı́na. A companhia quer saber quantas doses de 10ml. de cada
solução deve incluir em cada lata da bebida, para satisfazer às exigências mı́nimas
padronizadas de 48gr. de extrato de guaraná e 12gr. de cafeı́na e, ao mesmo tempo,
3.3. LISTA DE PROBLEMAS
63
minimizar o custo da produção. Por acelerar o batimento cardı́aco, a norma padrão
também prescreve que a quantidade de cafeı́na seja no máximo 20gr. por lata. Uma
dose da solução Red contribui com 8gr de extrato de guaraná e 1gr de cafeı́na,
enquanto uma dose da solução Blue contribui com 6gr. de extrato de guaraná e 2gr.
de cafeı́na. Uma dose de Red custa R$0,06 e uma dose de Blue custa R$0,08.
14. Um fabricante de carros produz duas versões de seu modelo popular de tamanho
médio: um utilitário direcionado ao mercado de famı́lias e um esportivo projetado
para atrair clientes ricos e solteiros. Ambos são montados sobre os mesmos chassis e diferem somente na carroceria. Ambos são também produzidos na mesma
fábrica. Existem 10.000 horas de força de trabalho e 1.325 unidades de chassis
básicos disponı́veis a cada semana. O modelo utilitário leva seis horas para ser montado, enquanto o modelo esportivo leva 9 horas. Pelo menos 400 unidades do modelo
utilitário devem ser produzidas por semana. A produção também é restringida pelo
fato de que, devido a problemas com um fornecedor, somente 6.000 maçanetas estão
disponı́veis por semana. Um utilitário utiliza cinco dessas maçanetas, enquanto um
esportivo utiliza três. O lucro da fábrica sobre um modelo utilitário é estimado em
$ 1.500,00, enquanto o lucro sobre um modelo esportivo é de $ 2.000,00. A demanda
do mercado pelos carros é alta. Sabe-se que a demanda excederá a produção em
algum momento; então, a fábrica deve ser capaz de vender qualquer mix de carros
que for produzido.
(a) Quantas maçanetas em excesso seriam recebidas pela fábrica a cada semana se
o mix de carros de produção recomendado for seguido.
(b) Se a fábrica pudesse obter somente uma das coisas a seguir, o que a permitiria
produzir mais carros?
i. Mais unidades de chassis.
ii. Mais maçanetas.
iii. Maior margem de lucro sobre cada carro.
iv. Remoção da restrição sobre a produção do modelo utilitário.
CAPÍTULO
4
RESOLUÇÃO DE PPL
A importância do método gráfico visto no capı́tulo anterior, reside no fato de permitir a
visualização de um método algébrico mais geral, que consiste em procurar o vértice do
polı́gono que otimize a função objetivo.
4.1
Estruturação de Modelos Lineares
Definição 4.1. Em problemas de minimização, uma solução viável x∗ = (x∗1 , x∗2 , . . . , x∗n )
é dita ótima se f (x∗ ) ≤ f (x), para toda solução viável x.
Definição 4.2. Um modelo de PPL está na forma padrão quando for formulado da
seguinte maneira:
min
s.a. :
z = c1 x 1 + c2 x 2 + . . . + cn x n












a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
..
.
(4.1)





am1 x1 + am2 x2 + . . . + amn xn = bm






x1 , x2 , . . . , xn ≥ 0
Observe que, na forma padrão, a função objetivo deve ser minimizada, as restrições
64
4.1. ESTRUTURAÇÃO DE MODELOS LINEARES
65
são definidas como um sistema de equações lineares e todas as variáveis devem satisfazer
as condições de não-negatividade.
A forma padrão não é restritiva pois todo PPL pode ser posto como em (4.1), de fato:
1. Para PPL de minimização, encontrar uma solução viável x∗ que minimize f (x) é
equivalente a encontrar uma solução que maximização −f (x).
Suponha que x∗ é um ponto ótimo de f (x), então
×(−1)
⇐⇒
f (x∗ ) ≤ f (x),
∀x viável
−f (x∗ ) ≥ −f (x),
∀x viável
⇐⇒ (−f )(x∗ ) ≥ (−f )(x), ∀x viável
2. Para ocorrência de desigualdades
Toda inequação pode ser convertida em equação adicionando ou subtraindo-se variáveis adicionais positivas denominadas variáveis de folga ou de excesso para
o caso de ocorrência de desigualdades do tipo ≤ ou ≥, respectivamente.
3. Para ocorrência de variáveis livres
São consideradas livres, as variáveis que não apresentam qualquer tipo de restrição
0
de sinal. Uma variável livre xj pode ser substituı́da por outras duas variáveis xj e
0
x00 j não-negativas, bastando para isto tomar xj = xj − x00 j
Na forma padrão um PPL pode ser escrito equivalentemente em notação matricial
como:
max f (x) = cT x
Ax = b
x≥ 0
onde:
(4.2)
66
CAPÍTULO 4. RESOLUÇÃO DE PPL


 a11 . . . a1n

..
A = 
.


am1 . . . amn
c
T
x
T
=
é o vetor dos custos;
c1 c2 . . . cn
=
é o vetor das variáveis de decisão;
x1 x2 . . . xn
é o vetor dos recursos;
b1 b2 . . . bm
=
é a matriz dos coeficientes;
bT =
0





é o vetor nulo.
0 0 ... 0
. . . Exemplo 4.1. Problema ilustrativo
Uma fábrica tem três tipos de máquinas (M1 , M2 , M3 ) cada uma das quais dever ser
usada na manufatura de seus produtos P1 e P2 . Sabendo que o lucro por unidade de P1
é 40 u.m. e o lucro por unidade de P2 é 60 u.m., decida quanto fabricar de cada produto
por semana a fim de maximizar os lucros de acordo com a seguinte tabela:
Máquinas Horas P1
Horas P2
Horas disponı́veis
M1
2
1
70
M2
1
1
40
M3
1
3
90
O modelo para este PPL é:
x1 : produção semanal de P1
x2 : produção semanal de P2
max
z = 40x1 + 60x2



2x1 + x2 ≤ 70





 x1 + x2 ≤ 40
s.a. :


x1 + 3x2 ≤ 90






x1 , x2 ≥ 0
Para que o sistema de restrições do problema seja posto na forma (Ax = b, x ≥ 0)
4.2. FUNDAMENTAÇÃO TEÓRICA
67
variáveis de folga devem ser definidas:
x3 = 70 − 2x1 − x2 ≥ 0
x4 = 40 − x1 − x2
≥0
x5 = 90 − x1 − 3x2 ≥ 0
Inserido as variáveis de folga, obtemos o modelo do PPL na forma padrão:
max
z = 40x1 + 60x2



2x1 + x2 + x3 =





 x1 + x2 + x4 =
s.a. :


x1 + 3x2 + x5 =






xj ≥
4.2
70
40
90
0
j = 1, . . . , 5
Fundamentação Teórica
O método algébrico Simplex para solucionar PPL está fundamentado nas técnicas e conceitos da Álgebra Linear. Para generalizar as ideias discutidas no método geométrico
algumas definições e reformulações se farão necessárias.
A definição seguinte generaliza o conceito de semiplano definido na capı́tulo anterior.
Definição 4.3. A equação a1 x1 + a2 x2 + . . . + an xn = b, com a1 , . . . , an , b ∈ R define um Hiperplano em Rn , que divide o espaço Rn em dois semi-espaços disjuntos:
a1 x 1 + a2 x 2 + . . . + an x n < b
e
a1 x1 + a2 x2 + . . . + an xn > b.
Analogamente ao que foi visto para PPL em duas variáveis, para problemas com três
ou mais variáveis a função objetivo representa uma famı́lia de hiperplanos paralelos entre
si.
Definição 4.4. A intersecção de um número finito de semi-espaços fechados é denominado politopo. Isto é, um politopo é definido por
(
P =
x ∈ Rn :
n
X
j=1
)
aij xj ≤ bi , para i = 1, 2, . . . , m
68
CAPÍTULO 4. RESOLUÇÃO DE PPL
O conjunto das soluções viáveis de um PPL é um politopo pois é obtida pela intersecção
de um número finito de restrições. Mesmo as inequações do tipo ≥ que possivelmente
compõem o sistema de restrições facilmente são transformadas em inequações do tipo ≤
pela simples multiplicação da expressão por -1.
Definição 4.5. Sejam x1 , x2 , . . . , xk vetores do Rn e α1 , α2 , . . . , αk números reais.
k
X
x=
αi xi é uma Combinação Linear Convexa se αi ≥ 0 para todo i = 1, 2 . . . , k
e se
i=1
k
X
αi = 1. Se αi > 0 para todo i = 1, 2 . . . , k, dizemos que é uma Combinação
i=1
Linear Convexa Legı́tima.
. . . Exemplo 4.2. Dados os vetores x1 = (1, 0) e x2 = (0, 1) de R2 .
O vetor x1 + x2 é uma combinação linear dos vetores x1 e x2 , mas não é uma combinação
linear convexa pois α1 + α2 = 2 6= 1.
O vetor 2x1 − x2 não é uma combinação linear convexa dos vetores x1 e x2 , apesar
de α1 + α2 = 1, não satisfaz a condição de não-negatividade dos escalares pois
α2 = −1 < 0.
4.2. FUNDAMENTAÇÃO TEÓRICA
69
Os vetores 0, 5x1 + 0, 5x2 , 0, 6x1 + 0, 4x2 , 0, 4x1 + 0, 6x2 , 0, 7x1 + 0, 3x2 e 0, 3x1 + 0, 7x2
são exemplo de combinações lineares convexas legı́timas pois satisfazem α1 +α2 = 1,
com α1 , α2 > 0.
Geometricamente pode-se interpretar uma combinação linear convexa de dois pontos
como um ponto do segmento de reta que une os dois pontos originais.
Definição 4.6. Um conjunto M é convexo se toda combinação linear convexa de qualquer par de pontos do conjunto também for elemento de M .
Em outras palavras, M é convexo se todo segmento de reta definido por dois quaisquer
de seus pontos estiver contido no conjunto.
. . . Exemplo 4.3. Os conjuntos representados nas figuras (a) e (b) são exemplos de
conjuntos convexos, enquanto as figuras (c) e (d) são conjuntos não convexos.
TEOREMA 4.1. A região viável de um PPL é um politopo convexo.
Dem.: Já vimos que a região viável de um PPL é um politopo e para mostrar que é
uma região convexa, sejam y, z ∈ RV .
Para ser uma solução viável y e z devem satisfazer todas as restrições e as condições
de não-negatividade, assim tem-se que Ay = b, Az = b e que y, z ≥ 0.
Seja αy + βz uma combinação linear convexa, isto é, α, β ≥ 0 e α + β = 1 . Então
a) αy + βz ≥ 0 pois α, β, y, z ≥ 0
b) A(αy + βz) = αAy + βAz = αbβb = (α + β)b = b
O que demonstra αy + βz ∈ RV e portanto RV é um politopo convexo.
70
CAPÍTULO 4. RESOLUÇÃO DE PPL
Definição 4.7. Um ponto x de um politopo convexo, denomina-se vértice quando ele não
puder ser obtido como uma combinação linear convexa legı́tima de nenhum par de pontos
distintos do politopo.
. . . Exemplo 4.4. Problema ilustrativo (continuação)
Retornando ao exemplo 4.1, utilizando a notação matricial o sistema de equações
lineares correspondente às restrições explı́citas do problema é da forma Ax = b,
 
x

  1  
2 1 1 0 0 
x2 
 70



1 1 0 1 0 x3 
= 40

 
  

1 3 0 0 1 
90
x4 
x5
Apesar do problema passar a ter cinco variáveis, qualquer par ordenado (x1 , x2 ) ∈ R2
determina unicamente todas as variáveis, pois as variáveis de folga são dependentes das
duas variáveis de decisão do modelo original.
Observe que posto(A) = 3, sendo assim o sistema Ax = b com m = 3 equações e
m + n = 5 variáveis é um Sistema Possı́vel e Indeterminado. Portanto, o sistema tem
duas variáveis livres, para as quais podemos atribuir quaisquer valores.
Vamos admitir que atribuiremos apenas valores nulos para as variáveis livres, como
são cinco variáveis agrupadas em conjunto de dois elementos, teremos 10 combinações
possı́veis:
1. Fixar x1 = x2 = 0 resulta em x3 = 70, x4 = 40, x5 = 90







x1 = 35
2x1 = 70





 x2 = 0


resulta em
2. Fixar
x = 5
x + x4 = 40 cuja solução é
 1
 4

 x3 = 0






 x1 + x5 = 90
 x5 = 55







2x1 + x2 = 70
x1 = 30





 x3 = 0


3. Fixar
resulta em
x1 + x2 = 40 cuja solução é
x2 = 10



 x4 = 0






 x1 + 3x2 + x5 = 90
 x5 = 30
4.2. FUNDAMENTAÇÃO TEÓRICA
71







2x1 + x2 + x3 = 70
x1 = 15






 x4 = 0

4. Fixar
resulta em
x1 + x2 = 40 cuja solução é
x2 = 25




 x5 = 0





 x3 = 15

x1 + 3x2 = 90
5. Fixar


 x3 = 0

 x5 = 0
resulta em






2x1 + x2
x1 + x2 + x4





x1 + 3x2



= 70
x1 = 24



= 40 cuja solução é
x2 = 22




 x4 = −6
= 90







x2 = 70
x2 =
70





 x1 = 0


6. Fixar
resulta em
x2 + x4 = 40 cuja solução é
x4 = −30



 x3 = 0






 3x2 + x5 = 90
 x5 = −120







x2 =
40
x2 + x3 = 70







 x1 = 0
7. Fixar
resulta em
x4 =
30
x2 = 40 cuja solução é





 x4 = 0




 x5 = −30
 3x2 + x5 = 90







x2 + x3 = 70
x2 = 30





 x1 = 0


8. Fixar
resulta em
x + x4 = 40 cuja solução é
x = 40
 x = 0
 2
 3





5



 x4 = 10
3x2 = 90
9. Fixar






2x1 + x3 = 70
x1 =
40






resulta em
x1 = 40 cuja solução é
x3 = −10




= 0




 x1 + x5 = 90
 x5 =
50


 x2 = 0

 x4







2x1 + x3 = 70
x1 =
90





 x2 = 0


10. Fixar
resulta em
x1 + x4 = 40 cuja solução é
x3 = −110
 x = 0







5



 x4 = −50
x1 = 90
A solução gráfica do problema pode ser visualizada na figura seguinte.
As soluções encontradas nas alternativas 5, 6, 7, 9 e 10 são inviáveis, isto é, apesar de
ser solução do sistema Ax = b estão fora da região viável. Enquanto a solução encontrada
na alternativa 1 corresponde ao vértice A do polı́gono que representa a região viável do
72
CAPÍTULO 4. RESOLUÇÃO DE PPL
problema, a solução 2 é o vértice B, a solução 3 é o vértice C, a solução 4 é o vértice D e
a solução 8 é o vértice E.
Para encontrar a solução ótima de um PPL é necessário encontrar soluções para o
sistema de equações lineares Ax = b, com m equações e n + m incógnitas.
É comum, em problema reais, m << n. Sendo assim, sem perda de generalidade,
podemos supor que posto(A) = m, eliminando previamente as combinações lineares. O
sistema Ax = b tem infinitas soluções e apresenta n variáveis livres que uma vez fixadas, os
valores das m variáveis restantes podem ser determinados unicamente por algum método
numérico para resolução de sistemas lineares.
A matriz A pode ser particionada convenientemente da seguinte maneira:
A= B N
onde:
Bm×m é chamada matriz Básica, formada por m colunas de A que a torne invertı́vel.
Nm×n é chamada matriz Não básica, formada pelas n colunas restantes de A.
4.2. FUNDAMENTAÇÃO TEÓRICA
73
Desta forma, o sistema Ax = b pode ser reescrito como



 xB 
B N  =b
xN

 xB 
onde  
xN
é uma partição de x induzida pela partição de A,
xB
é um vetor m × 1 denominado vetor das variáveis básicas e,
xN
de ordem n × 1 é o vetor das variáveis não básicas.
De acordo com a partição do sistema, é possı́vel obter o vetor das variáveis básicas xB
da seguinte maneira:
BxB + N xN = b
⇐⇒
xB = B −1 b − B −1 N xN


 x̂B 
Se considerarmos o vetor das variáveis não básicas xN nulo, obtemos o vetor x̂ =  
x̂N


 x̂B = B −1 b
denominado solução básica da seguinte maneira:

 x̂N = 0
Se todas as variáveis básicas que compõem x̂B forem não-negativas então a solução x̂
é denominada solução básica viável.
. . . Exemplo 4.5. Problema ilustrativo (continuação)
O sistema obtido no exemplo 4.1
 
x

  1  
2 1 1 0 0 
x2 
 70



1 1 0 1 0 
x  = 40


 3  

1 3 0 0 1 
90
x4 
x5
Pode ser particionado da seguinte maneira:
74
CAPÍTULO 4. RESOLUÇÃO DE PPL

 
  

"
#
70
0 0
2 1 1 x1

 
  

1 1 0 x2  + 1 0 x4 = 40
 x
 
  

5
90
0 1
1 3 0 x3
B
xB
N
xN
b
Fixando xN = 0, obtemos a solução básica viável x̂T = (15 25 15 0 0), que já
constatamos tratar-se do vértice C da região viável.
Estamos em condições de enunciar duas propriedades fundamentais:
TEOREMA 4.2. Um ponto x ∈ RV é um vértice se, e somente se, for uma solução
básica viável.
TEOREMA 4.3. Se um PPL tem solução ótima, então existe um vértice ótimo.
TEOREMA 4.4. A região viável de um PPL tem um número finito de vértices.
Dem.: O número de soluções básicas do sistema Ax = b é a combinação de m vetores
linearmente independentes tomados de um conjunto de n + m vetores correspondentes
n+m
às colunas da matriz A, isto é, a quantidade de soluções básicas será dada por Cm
.
Por definição, as soluções básicas viáveis formam um subconjunto das soluções básicas
do PPL e como, pelo teorema 4.2 cada vértice corresponde a uma solução básica viável,
concluimos que o número de vértices de RV é no máximo
n+m
Cm
=
(n + m)!
m! n!
que é finito.
Conclui-se que, se existe uma solução ótima para o PPL então existe uma solução
básica viável e para resolver um PPL basta procurar a solução ótima nos vértices da
região viável.
Assim para resolver o problema, basta determinar todas as soluções básicas viáveis,
digamos x̂1 , x̂2 , . . . , x̂k e obter a solução ótima x∗ tal que
f (x∗ ) = min{f (x̂1 ), f (x̂2 ), . . . , f (x̂k )}
4.2. FUNDAMENTAÇÃO TEÓRICA
75
Entretanto k pode ser uma quantidade demasiadamente grande, e o procedimento de
busca e comparação entre todos os vértices se torna inviável computacionalmente. O
método simplex irá economizar cálculos efetuando a busca de soluções ótimas somente
nos vértices que apresentem soluções melhores que as anteriores.
. . . Exemplo 4.6. Problema ilustrativo (continuação)
A região viável do problema das máquinas apresentado e formulado no exemplo 4.1
tem 5 vértices que foram todos obtidos como soluções básicas viáveis no exemplo 4.4
dentre os elementos do conjunto das soluções básicas cuja ordem é
C35 =
5!
= 10
2! 3!
Diferentemente do que foi feito no exemplo 4.4, queremos estabelecer um procedimento
que determine o vértice ótimo sem calcular todas as soluções básicas. Para tanto, tomemos
para começar xN = (x1 x2 )T .
Neste caso, x1 = x2 = 0 e portanto o lucro será z = 0. Como o objetivo do problema é
maximizar o lucro e o produto P2 retorna maior lucro por unidade, iremos tentar produzir
o máximo possı́vel de P2 . Assim x1 continua nula e x2 deve se tornar positiva. Mas qual
o valor que x2 deve assumir?
Para responder a esta questão, devemos retornar à definição das variáveis de folga
dadas no exemplo 4.1 e assumindo que x1 = 0, temos:
x3 = 70 − x2
x4 = 40 − x2
x5 = 90 − 3x2
Como as variáveis de folga também devem obedecer as condições de não-negatividade,
o valor limite para a variável x2 na primeira equação é 70, na segunda é 40 e na terceira
é 30, logo para que todas as variáveis de folga sejam não negativas o valor máximo que
pode ser assumido para a variável de decisão x2 deve ser 30.
Assim xB = (0 30)T , que corresponde ao vértice E da região viável, e retorna um
76
CAPÍTULO 4. RESOLUÇÃO DE PPL
lucro de z = 1800. Observe que partimos do vértice A = (0, 0) e encontramos o vértice
consecutivo E, se optássemos pelo vértice B = (35, 0) o retorno seria menor z = 1400.
Como já construimos geometricamente a região das soluções viáveis, sabemos que só
temos uma opção, ir para o vértice D que resultará no lucro máximo de z = 2100.
Mas como determinar este vértice algebricamente? Esta questão será respondida
pelo desenvolvimento do Método Simplex utilizando a caracterização das soluções básicas
viáveis, que será feito no próximo capı́tulo.
4.3
Lista de Problemas
1. Seja um triângulo ABC. Esse triângulo, no caso de retirarmos o baricentro, é um
conjunto convexo? Justifique.
2. Mostre que qualquer ponto de um triângulo ABC pode ser obtido como combinação
linear convexa de seus três vértices.
3. Num problema de programação linear somente os vértices podem ser solução ótima?
Justifique.
4. Assinalar a afirmativa que julgar mais correta.
I. A principal importância dos vértices para a resolução de um PPL consiste:
(a) na visualização do problema;
(b) ao invés de procurar a solução entre um número infinito de pontos, podemos
limitar-nos a um número finito de pontos;
(c) na determinação de outros pontos do espaço de soluções viáveis e que podem
ser formados como combinação linear convexa desses vértices.
II. Se o conjunto de soluções viáveis do PPL não for um conjunto limitado:
(a) o problema é impossı́vel;
(b) a função objetivo assume um valor infinito;
4.3. LISTA DE PROBLEMAS
77
(c) o problema tem sempre uma solução ótima;
(d) nenhuma dessas afirmativas é correta.
5. Considere o seguinte problema de PL:
max
z = 2x1 + 3x2



x1 + 3x2 ≤ 6



s.a. :
3x1 + 2x2 ≤ 6





x1 , x2 ≥ 0
(a) Expresse o problema na forma padrão.
(b) Determine todas as soluções básicas do problema e classifique-as como viáveis
e inviáveis.
(c) Determine a solução básica viável ótima do problema.
(d) Confronte com a resolução gráfica e verifique a solução obtida é realmente a
solução ótima do PPL. E conclua que a solução ótima pode ser determinada
algebricamente considerando somente soluções básicas viáveis.
(e) Mostre como as soluções básicas não viáveis são representadas graficamente na
região de soluções.
6. Considere um PPL cujas as restrições são dada a seguir



2x1 + 3x2





 x 1 + x2


x1 + 3x2






x1 , x2
≤ 33
≤ 15
≤ 27
≥
0
Sabendo que os pontos: A = (6, 7) e B = (12, 3) são soluções ótimas do problema,
(a) Determine a função objetivo;
(b) Verifique e justifique que o ponto C = (9, 5) também é uma solução ótima;
(c) Mostre que A e B são vértices da região viável e que C não é.
78
CAPÍTULO 4. RESOLUÇÃO DE PPL
7. Seja o PPL
max
s.a. :
z = x1 + x2 + x 3






x1 + x2 ≥ 6
x2 − 2x3 = 4




 x1 , x2 , x3 ≥ 0
(a) Determine todos os vértices da região viável do PPL ;
(b) Considere os seguintes pontos de R3 :
A = (1, 5, 21 ), B = (2, 6, 2),
) e D = (k, 4, 0), com k ∈ R+ . Quais deles são soluções do PPL?
C = (0, k, k−4
2
Quais são soluções básicas? Quais são soluções viáveis? Quais são vértices?
(c) É possı́vel garantir que existe, ao menos, um vértice que é solução ótima do
PPL ? Por que? Se sim, determine a solução ótima.
8. Responda Verdadeiro ou Falso e justifique:
(a) Toda solução ótima de um PPL é vértice.
(b) Se o PPL tiver mais de uma solução ótima, ele terá sempre uma infinidade de
soluções ótimas que não são vértices.
(c) Seja um PPL na forma padrão. Todas as soluções básicas viáveis tem obrigatoriamente o mesmo número de variáveis nulas.
CAPÍTULO
5
O MÉTODO SIMPLEX
O método simplex é um procedimento algébrico e iterativo que fornece a solução exata
de qualquer PPL em um número finito de iterações, o método é composto por critérios
especı́ficos para escolha das soluções que melhorem o desempenho do modelo e de um
teste de otimalidade. É também capaz de indicar se o problema tem solução ilimitada,
se não tem solução ou se possui infinitas soluções. Tais caracterı́sticas permitem sua
implementação em programas extremamente rápidos e eficientes, possibilitando a soluções
de problemas com centenas de variáveis de decisão. Atualmente extensões do método
são capazes de analisar sistemas com centenas de milhares de variáveis. O método foi
desenvolvido pelo matemático americano George Dantizig em 1947, e resultou em uma
economia de bilhões de dólares para a indústria e o governo americano.
Para resolver um PPL algebricamente, é preciso desenvolver uma sistemática que seja
capaz de determinar:
• Qual o sistema de equações que deve ser resolvido;
• Que o próximo sistema a ser resolvido fornecerá uma solução melhor que os
anteriores;
• Como identificar uma solução ótima, uma vez que a tenhamos encontrado.
Essa sistemática é denominada método ou algoritmo Simplex e consiste em:
79
80
CAPÍTULO 5. O MÉTODO SIMPLEX
1. Escolher uma solução básica viável inicial;
2. Determinar soluções básicas viáveis cada vez melhores;
3. Encontrar a solução ótima.
Inicialmente vamos considerar para análise e desenvolvimento do método PPls de
maximização cujo modelo original apresente restrições somente do tipo “ ≤ ”.
Dado o PPL
max
z = c1 x 1 + c2 x 2 + . . . + cn x n



a11 x1 + a12 x2 + . . . + a1n xn





..


.





 ar1 x1 + ar2 x2 + . . . + arn xn
s.a. :
..


.







am1 x1 + am2 x2 + . . . + amn xn






xj
≤ b1
≤ br
≤ bm
≥ 0 (j = 1, . . . , n)
Acrescentando as variáveis de folga para escrever o PPL na forma padrão, resulta no
seguinte modelo:
max
z = c1 x 1 + c2 x 2 + . . . + cn x n



a11 x1 + a12 x2 + . . . + a1n xn + xn+1




..



.






ar1 x1 + ar2 x2 + . . . + arn xn + xn+r



..
s.a. :
.





am1 x1 + am2 x2 + . . . + amn xn + xn+m







xj






(j = 1, . . . , n, n + 1 . . . , n + m)
= b1
= br
(5.1)
= bm
≥ 0
Podemos representar o último modelo em uma tabela com a seguinte configuração:
81
x2
...
a11
..
.
a12
. . . a1n
1
...
0
...
0
b1
..
.
ar1
..
.
ar2
. . . arn
0
...
1
...
0
br
..
.
am1 am2 . . . amn
0
...
0
...
1
bm
0
...
0
...
0
z = f (x)
c1
c2
...
xn
b
x1
xn+1 . . . xn+r . . . xn+m
cn
(5.2)
Considerando que estamos analisando PPl cujas restrições são todas do tipo “ ≤ ”,
sabemos que a origem do sistema de coordenadas é um dos vértices da região viável, logo
naturalmente podemos tomar a seguinte partição:

1 0 ...

0 1 . . .
.
..
.
.
.
0 0 ...

 
0
xn+1
a11 a12

 
0  xn+2   a21 a22

 
.. 
 .  +  .
.   ..   ..
1 xn+m
am1 am2
Bm×m
xB
...
...
..
.
...
 
 x1
 
a1n  
b1
  x2   
a2n   .   b2 
.  
.. 
 .  =  . 
.   .   .. 
 .. 
amn
bm
xn
Nm×n

xN
(5.3)
b

b1
 .. 
Fixando x̂N = 0 obtemos x̂B =  . 
bm
T
Desta forma, tomando x̂ = 0 0 . . . 0 b1 b2 . . . bm como solução básica
viável inicial, podemos reescrever a forma tabular (5.2) do PPL, adicionando a informação
das variáveis básicas escolhidas, para obter o quadro simplex inicial:
base
x1
xn+1
..
.
a11
..
.
a1r
a1n
1
0
0
b1
..
.
xn+r
..
.
ar1
..
.
arr
arn
0
1
0
br
..
.
xn+m am1
amr
amn
0
0
1
bm
−c1
−cr
−cn
0
0
0
0
z
...
xr
...
xn
xn+1 . . . xn+r . . . xn+m
b
82
CAPÍTULO 5. O MÉTODO SIMPLEX
A primeira coluna do quadro simplex informa quais são as variáveis básicas e a última
coluna corresponde aos termos independentes das equações de restrição do problema. A
última linha contém os coeficientes das variáveis na função objetivo que representam a
contribuição de cada variável para a função objetivo z, por unidade, em cada iteração do
processo de solução.
Para compor o quadro simplex a função objetivo z = c1 x1 +c2 x2 +. . .+cn xn necessitou
da seguinte transformação:
z = c1 x1 + c2 x2 + . . . + cn xn + 0xn+1 + . . . + 0xn+m
⇒
z − c1 x1 − c2 x2 − . . . − cn xn + 0xn+1 + . . . + 0xn+m = 0
Para problemas de maximização, a solução inicial claramente não é a melhor. Logo,
devemos procurar outra solução básica viável que retorne maior valor para z. Para isto é
necessário primeiramente,
Passo 1: Escolher uma variável não-básica que deve se tornar positiva para compor a base.
Obviamente, conforme já observado no exemplo 4.6 a variável que retorna a maior
contribuição para a função objetivo deverá ser selecionada, isto é, aquela variável
cuja contribuição unitária expressa na última linha do quadro simplex tenha sinal
negativo e maior módulo.
Escolhida a variável xr que entra na base, nosso problema agora é:
Passo 2: Determinar qual das variáveis básicas do quadro inicial deve sair base.
Em outras palavras, qual variável se tornará nula para dar lugar à nova variável
básica. Para tanto, observemos que todas as variáveis básicas do quadro inicial
podem ser escritas em função somente da variável xr , visto que
x1 = x2 = . . . = xr−1 = xr+1 = . . . = xn = 0
Assim,
xn+i = bi − air xr
para i = 1, . . . , m
83
bi
determina o valor de xr que anula a
air
variável básica xn+i , para qualquer i = 1, . . . , n. Seja k o ı́ndice tal que
Para cada coeficiente positivo air , a razão
bk
= min
akr
bi
, air > 0, i = 1, . . . , n
air
Definido desta forma, a variável básica xn+k se anula, isto é, se torna variável não
básica e todas as outras variáveis básicas do quadro inicial permanecem positivas.
É importante observar que para PPL com solução finita, sempre existe pelo menos um
coeficiente air > 0 pois, caso contrário, se air ≤ 0 para todo i = 1, . . . , m então f → −∞
e o PPL não teria solução ótima finita.
Observando a partição (5.3) constatamos que a matriz B correspondente às variáveis
básicas é exatamente a matriz identidade e deve permanecer assim exceto por rearranjo
de colunas, mesmo com alterações na composição do vetor das variáveis básicas.
Passo 3: Aplicar o método de Gauss-Jordan para resolução de sistemas lineares.
A redefinição das variáveis básicas e não-básicas exige um pivoteamento do quadro
simplex para que os coeficientes das variáveis básicas formem a matriz identidade,
mediante possivelmente remanejamento de colunas, e que a contribuição individual
para a função objetivo da variável que entrou na base seja zerada.
O processo de entrada e saı́da de variáveis da base deverá ser repetido até que todos os coeficientes da última linha se tornem nulos ou positivos, pois neste caso não há
mais possibilidade de crescimento da função objetivo e a solução ótima (caso exista) foi
encontrada. Sendo assim, ao final de cada iteração, deve-se:
Passo 4: Verificar se existe contribuição individual para a função objetivo, expressas na última
linha do quadro simplex, negativa.
. . . Exemplo 5.1. Resolver pelo método Simplex o problema ilustrativo apresentado no
exemplo 4.1, cujo modelo na forma padrão é:
84
CAPÍTULO 5. O MÉTODO SIMPLEX
max
z = 40x1 + 60x2



2x1 + x2 + x3 =





 x1 + x2 + x4 =
s.a. :


x1 + 3x2 + x5 =






xj ≥
70
40
90
0
j = 1, . . . , 5
O quadro simplex inicial é dado a seguir:
↓
x1
x2
x3 x4 x5
b
x3
2
1
1
0
0
70
x4
1
1
0
1
0
40
← x5
1
3
0
0
1
90
0
0
0
0
z
−40 −60
Quadro 1
A variável que deve entrar na base é x2 porque a contribuição individual de x2 para
o lucro é maior, no quadro -60 é a contribuição negativa com maior módulo. Para sair
40 90 da base devemos escolher x5 visto que 90
= min 70
, ,
. Isto é, na divisão termo a
3
1 1 3
termo do vetor dos termos independentes b pelo vetor dos coeficientes de x2 o menor valor
obtido foi 30, que corresponde à saı́da da variável x5 da base.
Escalonando por Gauss-Jordan, obtemos:
↓
x1
x2 x3 x4 x5
b
x3
5
3
0
1
0
−1
3
40
← x4
2
3
0
0
1
−1
3
10
x2
1
3
1
0
0
1
3
30
z
−20
0
0
0
Quadro 2
20 1800
85
De acordo com o quadro 2, a variável x1 entra na base pois há somente a contribuição
desta variável com sinal negativo na última linha. A variável x4 sai da base pois
10
2
3
= min
40 10 30
5 , 2 , 1
3
3
= min {24, 15, 90}
3
Assim, após escalonamento temos:
x1 x2 x3 x4
x5
b
x3
0
0
1
−5
2
1
2
15
x1
1
0
0
3
2
−1
2
15
x2
0
1
0
−1
2
1
2
25
z
0
0
0
30 10 2100
Quadro 3
O fato de não haver contribuição com sinal negativo no quadro simplex garante que a
solução básica viável no quadro 3 é ótima. Portanto a solução do problema é fabricar 15
unidades do produto P1 e 25 unidades de P2 para obter um lucro máximo de $ 2.100,00,
sendo que há uma folga na operação da máquina M1 de 15 horas.
De acordo com o que estudamos do método simplex, o modelo de programação linear
pode ser resolvido por um método de resolução de sistemas lineares e a programação linear
pode ser vista como um aprimoramento do Método de Gauss-Jordan para resolução de
sistemas lineares, incorporando uma equação adicional que representa o comportamento
que deve ser otimizado e utilizando um sistemática para troca de variáveis básicas e não
básica.
Roteiro Passo 1: Introduzir as variáveis de folga; uma para cada desigualdade.
Passo 2: Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis
com os respectivos sinais e, na última linha, incluir os coeficientes da função objetivo
transformada.
86
CAPÍTULO 5. O MÉTODO SIMPLEX
Passo 3: Estabelecer uma solução básica inicial, usualmente atribuindo valor zero às variáveis
originais e achando valores positivos para as variáveis de folga.
Passo 4: Como próxima variável a entrar na base, escolher a variável não básica que oferece,
na última linha, a maior contribuição para o aumento da função objetivo (ou seja,
tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem
coeficientes nulos ou positivos nesta linha, a solução atual é ótima. Se alguma dessas
variáveis tiver coeficiente nulo, isto significa que ela pode ser introduzida na base
sem aumentar o valor da função objetivo. Isso quer dizer que temos uma solução
ótima, com o mesmo valor da função objetivo.
Passo 5: Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento:
a) Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base, caso não haja elemento algum
positivo nesta coluna, o processo deve parar, já que a solução seria ilimitada.
b) O menor quociente indica a equação cuja respectiva variável básica deverá ser
anulada, tornando-se variável não-básica.
Passo 6: Usando operações elementares com as linhas da matriz (soma e multiplicação por
um escalar não-nulo), transformar o quadro de cálculos de forma a encontrar a
nova solução básica. A coluna da nova variável básica deverá se tornar um vetor
identidade, onde o elemento 1 aparece na linha correspondente à variável que está
sendo anulada.
Passo 7: Se ainda houver elementos negativos na linha da função objetivo, retornar ao passo
4 para iniciar outra iteração.
. . . Exemplo 5.2. Considere o PPL do exemplo 3.3 resolvido graficamente no exemplo
3.4, cujo modelo é:
87
max
z = 6, 5x1 + 10x2



x1 + x2 ≤ 25





 25x1 + 9x2 ≤ 480
s.a. :


6x1 + 11x2 ≤ 240






x1 , x2 ≥ 0
(Lucro Total)
(restrição de câmera de ar)
(restrição de operação de costura)
(restrição de operações de finalização)
(restrição de não-negatividade)
Para determinar a solução do PPL por sistemas de equações lineares é preciso primeiro
transformar o sistema de inequações lineares que representam as restrições do problema
em um sistema equivalente de equações lineares. Para isto, será preciso introduzir novas
variáveis no problema, denominadas variáveis de folga.
Neste exemplo, as restrições têm a seguinte estrutura lógica:
utilização de recursos ≤ disponibilidade
Introduzindo o conceito de variável de folga de recurso, a inequação pode ser reescrita
como:
utilização de recursos + folga = disponibilidade
A folga correspondente a cada recurso pode ser representada por uma variável de modo
a transformar cada inequação do PPL em uma equação linear. Sejam
x3 : folga de câmeras de ar;
x4 : folga de operações de costura;
x5 : folga de operações de finalização.
Introduzindo as variáveis de folga e trocando os termos de lado na equação referente
à função objetivo, obtemos o modelo do PPL a ser resolvido é:
88
CAPÍTULO 5. O MÉTODO SIMPLEX
z − 6, 5x1 − 10x2



x1 + x2 + x3





 25x1 + 9x2 + x4
s.a. :


6x1 + 11x2 + x5






xj
max
= 0
= 25
= 480
= 240
≥ 0
j = 1, 2, 3, 4, 5
Desta forma, o problema consiste em encontrar a solução de um sistema de equações
lineares que maximize o lucro. Para montar o quadro simplex inicial, é necessário estabelecer uma solução inicial para o problema, que será sempre obtida, para problemas
nesta configuração, fazendo as variáveis originais do modelo iguais a zero. Assim, fazendo
x1 = x2 = 0 (variáveis não-básicas) e tomando as variáveis de folga x3 , x4 e x5 como
variáveis básicas, obtemos do Quadro 1:
x1
x2
x3 x4 x5
b
x3
1
1
1
0
0
25
x4
25
9
0
1
0
480
x5
6
11
0
0
1
240
0
0
0
0
z
−6, 5 −10
Quadro 1
Onde a primeira coluna corresponde às variáveis básicas, a última coluna corresponde
aos termos independentes das equações, e a última linha contém os coeficientes das
variáveis na função objetivo. Nessa última linha teremos sempre a contribuição que cada
variável dá para o lucro total z, por unidade, em cada iteração do processo de solução.
Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um
valor maior para z. O problema é descobrir:
• Das duas variáveis não-básicas (nulas) na primeira solução, qual deve se tornar
positiva?
Observando que na última linha do Quadro 1 temos os coeficientes da função objetivo
que mostram a contribuição para o lucro z de cada unidade produzida de bola
89
Catechumbo (x1 ) e de bola Voleitok (x2 ). Assim, aplicando o critério de que devemos
produzir primeiro o produto que mais contribui para o lucro, vamos começar a
produção pela variável x2 , já que sua contribuição unitária para o lucro é maior que
a contribuição de x2 . Logo, a variável que deverá entrar na base é x2 .
• Das três variáveis básicas (positivas) na primeira solução, qual deverá ser anulada?
Nota-se pelo Quadro 1 que, na primeira equação, o maior valor possı́vel de x2 é 25,
quando x3 = 0 pois x1 = 0 por ser variável não-básica. Qualquer valor maior para
x2 fará com que o valor de x3 fique negativo, o que não é permitido. Na segunda
equação, o maior valor permitido para x2 é 53, 33, quando x4 = 0. Finalmente, na
terceira equação o maior valor permitido para x2 é 21, 82, quando x5 = 0.
Analisando simultaneamente todas as equações, percebe-se que o maior valor possı́vel
para x2 é 21, 82, já que atende às três equações. Observe que esta análise pode ser
feita diretamente do Quadro 1, através da divisão dos elementos da coluna b pelos
correspondentes elementos da coluna x2 . O menor quociente indica, pela linha em
que ocorreu, qual a variável básica que deve ser anulada.
Assim, como o menor quociente é dado pela divisão
240
,
11
a variável que deverá sair
da base é x5 .
Portanto, x1 = 0 e x5 = 0 são as novas variáveis não-básicas e o sistema deve ser
resolvido para encontrar os valores x3 , x4 e x2 . A solução desse sistema será feita usando
o Quadro 1 com as equações completas e usando as operações elementares de multiplicação
de uma linha por um escalar não nulo e soma de linhas da matriz.
x1 x2 x3 x4
x5
b
3, 18
x3
0, 4546
0
1
0 −0, 09091
x4
20, 09
0
0
1
−0, 8182 283, 6
x2
0, 5454
1
0
0
0, 09091 21, 82
z
−1, 046
0
0
0
0, 9091 218, 2
Quadro 2
90
CAPÍTULO 5. O MÉTODO SIMPLEX
O processo de entrada e saı́da de variáveis da base deverá ser repetido até que todos
os coeficiente da linha 4 se tornem nulos ou positivos.
falta fazer quadro 3
x1 x2 x3 x4
x5
b
3, 18
x3
0, 4546
0
1
0 −0, 09091
x4
20, 09
0
0
1
−0, 8182 283, 6
x2
0, 5454
1
0
0
0, 09091 21, 82
z
−1, 046
0
0
0
0, 9091 218, 2
Quadro 2
5.1. FLUXOGRAMA PARA SOLUÇÕES FINITAS
5.1
Fluxograma para soluções finitas
5.2
Análise de Sensibilidade
5.3
Lista de Problemas
91
Lista de Exercı́cios 5.1. Resolver os modelos em PL, usando o método Simplex:
1. Um fabricante de fantasias tem em estoque 32m de brim, 22m de seda e 30m de
cetim e pretende fabricar dois modelos de fantasias. O primeiro modelo consome
4m de brim, 2m de seda e 2m de cetim. O segundo modelo consome 2m de brim,
4m de seda e 6m de cetim. Se o primeiro modelo é vendido a 6.000u.m. e o segundo
92
CAPÍTULO 5. O MÉTODO SIMPLEX
modelo a 10.000u.m., quantas peças de cada tipo o fabricante deve fazer para obter
a receita máxima?
2. Um dono de loja estoca dois tipos de leite, semidesnatado e integral, e está tentando
decidir quantos de cada um encomendar. Ele precisa encomendar o leite para entrega
com um dia de antecedência. Sabe que venderá pelo menos 75 litros em um só
dia, e então não encomendará menos do que essa quantidade. Seu contrato com
o fornecedor diz que deve comprar pelo menos 30 litros de semidesnatado, e não
possui espaço no refrigerador para mais de 100 litros ao todo. Se o dono da loja
obtém 15 centavos de lucro com um litro de leite semidesnatado e 17 centavos de
lucro cm um litro de leite integral, o que deve fazer para maximizar seu lucro?
3. A Gutchi Company fabrica carteiras, estojos de barbear e mochilas. A produção das
peças utiliza couro e materiais sintéticos, sendo o couro a matéria-prima que limita
a produção. O processo de produção requer dois tipos de mão-de-obra especializada:
costura e acabamento. A Tabela dá a disponibilidade dos recurso, sua utilização
nos três produtos e os lucros por unidade.
Recursos necessários por unidade
Recurso
Carteira
Estojo de barbear
Mochila
Disponibilidade diária
Couro(pés2 )
2
1
3
42
Costura(h)
2
1
2
40
Acabamento(h)
1
0,5
1
45
Preço de Venda($)
24
22
45
(a) Formule a questão como um problema de programação linear e ache a solução
ótima.
(b) De acordo com a solução ótima, determine o status de cada recurso.
4. Uma fábrica têxtil labora em 3 turnos: das 7 às 15 horas; das 15 às 23 horas; das
23 às 7 horas. Em cada turno necessita de modelistas, costureiras e embaladoras
que auferem por hora de trabalho, respectivamente 23,00, 19,00 e 7,50 u.m. As
5.3. LISTA DE PROBLEMAS
93
modelistas e costureiras auferem um adicional de 2,00 u.m./hora quando trabalham
no último dos turnos indicados sendo o salário das embaladoras, neste turno, de
8,50 u.m./h.
As necessidades da produção exigem, em cada turno, 1 hora de modelista por cada
3 horas de costureira não podendo haver mais do que um total de 200 horas de embaladora em cada turno. Pretende-se que o total de horas de trabalho de modelista
e costureira seja no mı́nimo de 400 horas no turno da manhã, 376 horas no turno
da tarde e 270 horas no turno da noite. Em cada turno deve haver o mı́nimo de 600
horas de trabalho.
5. Um banco decidiu ter os seus balcões abertos ao público das 08 horas às 20 horas
pelo que necessita planejar novos horários de serviço para os seus funcionários. Para
tal decidiu dividir o dia de trabalho em 6 perı́odos de 2 horas e fixar para cada um
destes perı́odos o seguinte número mı́nimo de funcionários:
8-10h 10-12h 12-14h 14-16h 16-18h 18-20h
no . mı́nimo de
funcionários
6
10
12
11
5
4
Os funcionários trabalham diariamente 6 horas consecutivas, podendo a empresa
fixar a hora de entrada ao serviço. Apresentar o modelo de PL que minimiza o
número total de empregados necessários diariamente.
6. Um distribuidor de produtos para festas infantis compra dos produtores chapéus de
papel, lı́nguas-de-sogra e bexigas, e prepara caixas com esses três produtos na forma
de kits para festas. Observações anteriores mostram que:
a. A quantidade de chapéus e lı́nguas-de-sogra deve ser pelo menos 50% do total.
b. O pacote deve ter pelo menos 20 bexigas.
c. Cada item deve concorrer com pelo menos 25% do total da caixa.
94
CAPÍTULO 5. O MÉTODO SIMPLEX
Chapéu de papel: 50.000
O custo dos componentes (em milhares de unidades) é: Lı́ngua-de-sogra: 20.000
Bexiga: 5.000
Qual a composição da caixa que tem o menor custo?
7. Uma empresa quı́mica opera uma pequena usina. Operar a usina exige duas matériasprimas, A e B. O fornecimento máximo disponı́vel por semana é 2.700 litros de A e
2.000 litros de B. A usina pode operar usando um dos dois processos, que possuem
diferentes exigências de matéria-prima, como demonstrado a seguir:
Matérias-primas consumidas
(litros por hora)
Processo
A
B
1
20
10
2
30
25
A usina pode funcionar por um total de 120 horas por semana mas, por motivo de
segurança, o Processo 1 não pode ser operado por mais de 100 horas por semana.
Quantas horas cada processo deve funcionar?
8. Uma pequena padaria local recebeu um pedido para fornecer dois tipos de pão:
sabor queijo e pãozinho de semente de papoula, para um serviço de entrega de
sanduı́ches. Eles receberão 5 centavos por cada pãozinho e 8 centavos por cada pão
sabor queijo que fornecerem. Inicialmente a empresa de entrega de sanduı́ches está
feliz em comprar quanto a padaria conseguir produzir desses dois tipos de pão. A
padaria já possui encomendas semanais de 100 kg de farinha e 1 kg de fermento, e
gostaria de ser capaz de cumprir seu novo contrato sem aumentar essas quantidades.
Cada pãozinho utiliza 30g de farinha e e 0,5g de fermento, enquanto cada pão sabor
queijo utiliza 125g de farinha e 1g de fermento. O acordo diz que eles devem fornecer
pelo menos 1.000 pães de semente de papoula e entre 300 e 500 pães sabor queijo
por semana.
5.3. LISTA DE PROBLEMAS
95
(a) Quantos pães de cada tipo a padaria deve ter com objetivo fornecer a cada
semana para maximizar seu lucro?
(b) Se a padaria desejasse reduzir sua encomenda de farinha, poderia faze-lo?
Meses depois, a padaria decidiu expandir sua variedade de produtos, e agora produzirá um segundo tipo de pão (tomate seco), que necessita de 140g de farinha,
1,2g de fermento e contribui com um lucro de 10 centavos por unidade. Ela mudou
seus pedidos para atender a crescente demanda e agora recebe entregas de 250kg de
farinha e 3kg de fermento. Os pedidos existentes significam que ele deve produzir
pelo menos 1.500 pãezinhos e 800 bisnagas por semana. Que quantidade de cada
produto a padaria deve produzir e vender para maximizar seu lucro? Ela pode
reduzir a quantidade de fermento encomendada?
96
CAPÍTULO 5. O MÉTODO SIMPLEX
5.4
Lista de Problemas
1. O quadro a seguir mostra o processo de resolução de um PPL . A partir dos dados
fornecidos, responda às seguintes questões:
BASE
L
X1
X2
X3
Y1
Y2
B
1
2
1
3
2
5
2
0
9
2
(Recurso A)
2
0
–1
–1
1
6
(Recurso B)
− 12
0
3
2
3
2
0
27
2
(a) Complete o quadro indicando as variáveis que estão na base.
(b) Escreva a solução que o quadro indica. A solução obtida nessa etapa é otima?
2. Uma empresa fabricante de móveis de copa trabalha com três modelos principais de
conjuntos aos quais denomina MXA, MXB e MXC (x1 , x2 e x3 , respectivamente),
cuja produção semanal deseja programar. As margens unitárias de lucro dos modelos são respectivamente, $20, $8 e $ 3. Os três conjuntos utilizam as três principais
seções da fábrica, que chamaremos Seção 1, Seção 2 e Seção 3, conforme os coeficientes unitários de utilização mostrados no modelo de programação linear abaixo.
As seções dispõem das seguintes capacidades semanais de trabalho, respectivamente:
240 homens-horas (H.h), 320 H.h e 480 H.h. O modelo de programação linear utilizado pelo setor de planejamento da empresa para a programação da produção da
próxima semana é o seguinte:
Achar x1 , x2 e x3 de modo a
Maximizar lucro = 20x1 + 8x2 + 3x3
respeitando as restrições:
4x1 + 1x3
≤ 240
(Seção 1)
4x1 + 2x2 + 2x3
≤ 320
(Seção 2)
3x1 + 4x2
≤ 480
(Seção 3)
O quadro a seguir mostra os resultados do processo de solução do Método Simplex.
5.4. LISTA DE PROBLEMAS
BASE
LUCRO
97
X1
X2
X3
Y1
Y2
Y3
B
1
0
1
4
1
4
0
0
60
0
1
1
2
− 14
1
2
0
40
0
0
− 11
4
5
4
–2
1
140
0
0
6
1
4
0
1520
Pede-se:
(a) Na solução ótima do problema, identifique as utilidades marginais das três
seções utilizadas no processo de produção da empresa.
(b) Caso a Seção 1 tenha sua disponibilidade alterada para 200 H.h, quais os novos
valores das produções ótimas dos conjuntos MXA e MXB?
(c) Caos a empresa possa acrescentar mais 60 H.h a alguma seção, qual deverá ser
a seção escolhida? Por quê?
(d) Na hipótese anterior, quais os novos valores das produções ótimas e quais as
novas utilizações dos recursos?
3. Uma empresa produz dois produtos A e B. As receitas unitárias são $ 2 e $ 3,
respectivamente. A disponibilidade das duas matérias-primas (M1 e M2 ) usadas na
fabricação dos produtos é de 8 e 18 unidades. Uma unidade de A usa duas unidades
de M1 e duas unidades de M2 , e uma unidade de B usa três unidades de M1 e seis
unidades de M2 .
(a) Determine as faixas de viabilidade de cada restrição.
(b) Suponha que quatro unidades adicionais de M1 podem ser adquiridas ao custo
de 30 centavos por unidade. Você recomendaria essa compra adicional?
(c) Qual é o valor máximo que a empresa pode pagar por unidade de M1 ?
(d) Determine a receita ótima se a disponibilidade de M2 for aumentada em cinco
unidades.
(e) Determine as faixas de otimalidade para as receitas unitárias considerando que
as alterações são feitas uma por vez.
98
CAPÍTULO 5. O MÉTODO SIMPLEX
(f) Como fica a solução ótima se a receita unitária do produto A passar a ser $ 5?
E se a receita unitária do produto B passar a ser $ 4?
4. Uma pequena empresa produz pôsteres de bandas de Rock. Ela fabrica quatro tipos
de pôsteres, que diferem em tamanho e nas cores utilizadas. A empresa conseguiu
uma impressora para produzir os pôsteres e estabeleceu um limite mı́nimo de 1000
pôsteres para produção. Cada pôster deve ser impresso, cortado e dobrado. O
tempo (em minutos) para fazer isso para os quatro tipos de pôsteres é de:
Tipo de Pôster
Impressão
Corte
Dobragem
A
1
2
3
B
2
4
2
C
3
1
5
D
3
3
3
Disponı́vel
15000
20000
20000
(a) Quais as quantidades ótimas produzidas e o lucro projetado?
(b) Quanto a empresa está disposta a pagar por tempo extra de impressão, de
corte e de dobragem?
(c) Suponha que reduzı́ssemos o limite mı́nimo de produção de 1000 em um dos
itens para 900. Qual pôster deveria ter sua produção diminuı́da, e qual seria o
lucro adicional da empresa?
5. A Distribuidora de Bebidas Desce Redondo deseja programar suas vendas para o
mês de janeiro, de acordo com as cotas por produtos determinadas pela empresa
produtora Ambe, fabricante de diferentes marcas de cerveja. Neste perı́odo, a Desce
Redondo consegue vender quaisquer quantidades de produto entregues pela Ambe,
tendo uma margem de lucro de 12% sobre sua receita. A Ambe autorizou um pedido
de 150.000 caixas com 24 garrafas cada, de diversos produtos, podendo a Desce
5.4. LISTA DE PROBLEMAS
99
Redondo determinar dentro de certos limites impostos pela fábrica que quantidade
deseja receber de cada cerveja. A tabela abaixo discrimina os lucros unitários por
caixa dos produtos e limites de cotas impostos pela fábrica.
Cerveja
Capacidade
Preço de venda
Max (%)
Min(%)
Recipiente (ml)
por caixa (R$)
Antártida
600
55,00
60
55
Antártida
350
37,50
40
35
Boemia Regressa
600
60,00
3,0
1,0
Mudweiser
350
40,50
1,5
0,5
Malebier
350
34,00
1,5
1,0
Bama Chopp
350
40,50
1,7
0,5
Lambati
350
44,30
5,0
2,0
Desce Redondo
600
44,30
3,0
0,5
Pede-se
(a) Quais são as quantias ótimas a serem solicitadas? Qual o lucro total?
(b) Se você pudesse aumentar seu pedido em 50 caixas, que cerveja solicitaria?
6. Considere o PPL
z = −5x1 + 5x2 + 13x3
max
s.a. :






−x1 + x2 + 3x3 ≤ 20
12x1 + 4x2 + 10x3 + 2x4 ≤ 90





x1 , x2 , x3 ≥ 0
bem como o seu quadro Simplex ótimo
x1
x2
x3
x4
x5
x2
-1
1
3
1
0
20
x5
16
0
-2
-4
1
10
z
0
0
-2
-5
0
-100
100
CAPÍTULO 5. O MÉTODO SIMPLEX
Resolva as seguintes questões:
(a) Qual a nova solução ótima se alterarmos o vetor b de (20 90)T para (10 100)T ?
(b) Qual a nova solução ótima se alterarmos o custo c3 da variável x3 de 13 para
8?
(c) Qual a nova solução ótima se alterarmos os coeficientes de x2 nas restrições de
(1 4)T para (2 5)T ?
(d) Qual a nova solução ótima se introduzirmos no PPL original uma nova variável
x6 com coeficientes a6 = (3 5)T e c6 = 10?
(e) Qual a nova solução ótima se introduzirmos uma nova restrição no PPL original: 2x1 + 3x2 + 5x3 ≤ 50?
7. A Electra produz quatro tipos de motores elétricos, cada um em uma linha de
montagem separada. As capacidades respectivas das linha são 500, 500, 800 e 750
motores por dia. O motor do tipo 1 usa oito unidades de um certo componente
eletrônico, o motor do tipo 2 usa cinco unidades, o motor do tipo 3 usa quatro
unidades e o motor do tipo 4 usa seis unidades. O fabricante do componente pode
fornecer 8.000 peças por dia. Os preços dos componentes para os respectivos tipos
de motor são $ 60, $ 40, $ 25 e $ 30 por motor.
(a) Determine o mix ótimo de produção diária.
(b) A atual programação de produção atende às necessidades da Electra. Contudo, devido à concorrência, pode ser que a empresa precise reduzir o preço do
motor do tipo 2. Qual é a maior redução que pode ser efetuada sem alterar a
programação de produção atual?
(c) A Electra decidiu reduzir em 25% o preço de todos os tipos de motores. Use
a análise de sensibilidade para determinar se a solução ótima permanecerá
inalterada.
(d) Atualmente, o motor do tipo 4 não é produzido. De quanto deveria ser o
aumento no preço desse motor para ser incluı́do na programação de produção?
5.4. LISTA DE PROBLEMAS
101
8. Um fazendeiro dispõe de 100 hectares de terra e um total de mão-de-obra anual
disponı́vel correspondente a 10 000 homens/hora. O fazendeiro tem a opção de
plantar trigo, soja ou milho. O gasto anual de mão-de-obra por hectare para cada
uma destas culturas é respectivamente h1 , h2 e h3 homens/hora. O lucro por hectare
para trigo, soja e milho é respectivamente 10, 8 e i unidades monetárias. O filho
do fazendeiro, Pedro, que estuda P.O., montou então o seguinte modelo, que visa
maximizar o lucro da fazenda:
max
s.a. :
z = 10x1 + 8x2 + x3






x1 + x2 + x3 ≥ 100
h1 x1 + h2 x2 + h3 x3 ≥ 10000





x1 , x2 , x3 ≥ 0
onde x1 , x2 e x3 representam a quantidade de terra por hectare a ser plantada
respectivamente com o trigo, soja e milho. Em seguida, Pedro pediu ao pai para
especificar os valores de h1 , h2 e h3 , com o auxı́lio do Simplex determinou a solução
ótima através do seguinte quadro:
x1
x2
x3
x4
x5
1
1
1
1
0
100
0
-2
-2
-5
1
9500
0
2
9
10
0
Visando prevenir-se contra possı́veis mudanças na fazenda, estude os seguintes casos
(os casos não podem ocorrer simultaneamente):
(a) Uma indústria se instala nas proximidades da fazenda e absorve toda a mãode-obra da região. O fazendeiro fica restrito ao caseiro, que não pode dispor
de mais de 300 horas por ano. O plano de produção da fazenda seria alterado?
Como? Caracterize a nova solução.
(b) Por uma questão de segurança (mudança de preços do trigo), o fazendeiro
decide plantar no máximo 50 hectares de trigo. Qual seria a nova solução
102
CAPÍTULO 5. O MÉTODO SIMPLEX
ótima?
(c) Determine o valor das variáveis do dual para três soluções obtidas (a dada
no enunciado e mais as obtidas em (a) e (b)). Interprete o significado dessas
variáveis para as três soluções caracterizando as alterações sofridas.