Métodos Quantitativos I

Prévia do material em texto

1
Métodos Quantitativos I - SA056
Prof. Dr. Leonardo Lima (leonardo.delima@ufpr.br)
Departamento de Administração Geral e Aplicada
S U M Á R I O
i modelos matemáticos em problemas gerenciais
1 formulação de modelos 7
1.1 Hipóteses do Modelo de Programação Linear 9
1.2 Forma Geral de um PPL 9
1.3 Exemplos de formulação matemática 10
1.4 Exercı́cios 23
2 resolução de modelos : método gráfico 29
2.1 Forma matricial de um PPL 29
2.2 Definições Básicas 30
2.3 Representação Geométrica 30
3
Parte I
M O D E L O S M AT E M Á T I C O S E M P R O B L E M A S
G E R E N C I A I S
1
F O R M U L A Ç Ã O D E M O D E L O S
A modelagem matemática consiste na tentativa de se descrever mate-
maticamente o comportamento de um determinado fenômeno. Para
que um modelo represente fielmente uma dada realidade, ou uma
parte desta, os seus dados necessitam ser consistentes e o seu resultado
coerente com o objetivo ao qual se pretende atingir.
As técnicas de otimização podem se apresentar fortemente funda-
mentadas pelas ferramentas de apoio a decisão e é nesse cenário que
gestores otimizam seus objetivos através dos recursos oferecidos pelas
técnicas de modelagem e de simulação. A intuição se faz presente
em todas as etapas da tomada de decisão, desde a formulação do
problema em seu contexto até a tomada de decisão propriamente
dita, o que pode sinalizar sua relevância no processo em função da
sua capacidade de sintetizar a situação através da leitura do todo,
enquanto a lógica e a razão dos modelos matemáticos realizam essa
análise de forma fragmentada.
A etapa de formulação do problema e construção do modelo ma-
temático consiste na representação de um determinado problema real
em forma de equações e inequações matemáticas. Esta representação
contém alguns elementos fundamentais e que sempre estarão presen-
tes em todos os problemas. Estes elementos são:
i. As constantes do modelo, que são chamadas de parâmetros.
Exemplos de parâmetros são os custos e receitas de itens envol-
vidos no problema, as disponibilidades máximas e/ou necessi-
dades mı́nimas de cada recurso, dentre outros. Os parâmetros
são obtidos na fase de coleta de dados.
ii. As variáveis de decisão do problema. Estas correspondem ao
conjunto de n decisões quantificáveis que são representadas
em formas de variáveis de decisão, a saber x1, x2, . . . , xn, cujos
respectivos valores devem ser determinados.
iii. A medida de desempenho apropriada para o problema, o qual
denominamos função objetivo. Esta pode ser otimizada no
sentido de sua maximização (por exemplo, aumentar o lucro) ou
minimização (por exemplo, diminuir custo) do problema.
iv. As restrições do problema. As expressões matemáticas para re-
presentar as limitações em recursos são denominadas restrições
7
8 formulação de modelos
do problema. As restrições são escritas em função das variáveis
de decisão.
A partir do modelo matemático definido com os elementos acima, o
problema passa a ser escolher adequadamente os valores das variáveis
de decisão de forma a maximizar (ou minimizar) a função objetivo e
obedecer a todas as restrições estabelecidas.
Um modelo matemático contendo os elementos acima, e pequenas
variações deles, tipifica os modelos usados na Pesquisa Operacional.
No contexto desta disciplina, nosso foco é modelar matematicamente
os problemas e resolvê-los. Todos os modelos desenvolvidos neste
material envolverão somente funções lineares e por esse motivo, de-
nominaremos daqui em diante, os problemas aqui abordados como
problemas de programação linear (mais comumente por PPL).
Definição 1.1 (Mapa ou Função Linear). Uma função F : Rn → R é
dita linear se para quaisquer dois vetores x, y ∈ Rn possui as seguintes
propriedades:
• F(x + y) = F(x) + F(y)
• F(αx) = αF(x), para α ∈ R.
Exemplos de funções lineares são:
F1(x1, x2) = x1 + 3x2
e
F2(x1, x2) = x1 − 2x2 − 5x3 + 0.3x4.
Três exemplos de funções não-lineares são:
x1 + x2 + x1x2,
x21 + x
3
2 e
ex1 + cos(x2) + x3,
e esses tipos de funções estão fora do escopo desta disciplina. Abor-
daremos somente problemas com funções lineares.
Desta forma, podemos definir um problema de programação linear
como abaixo.
Definição 1.2 (Problemas de Programação Linear - PPL). Dizemos
que um modelo matemático é de programação linear se todas as funções
envolvidas no modelo são funções lineares. Adicionalmente, todas as variáveis
de decisão devem ser contı́nuas, ou seja, podem assumir quaisquer valores em
um intervalo de números reais.
1.1 hipóteses do modelo de programação linear 9
1.1 hipóteses do modelo de programação linear
1. Proporcionalidade: a hipótese de proporcionalidade exige que
cada variável de decisão do problema tenha uma contribuição
para a função objetivo e para as restrições proporcional ao valor
da variável de decisão.
2. Aditividade: a hipótese de aditividade assume que o valor total
da função objetivo ou das funções das restrições é dado pela
soma das contribuição individuais de cada variável de decisão.
3. Divisibilidade e não negatividade: cada uma das variáveis de
decisão utilizadas no modelo podem assumir quaisquer valo-
res não negativos dentro de um intervalo, incluindo valores
fracionários, desde que satisfaça as restrições do modelo.
4. Certeza: a hipótese de certeza indica que todos os parâmetros
(custos, disponibilidades e etc) utilizados no modelo são deter-
minı́sticos (constantes e conhecidos com certeza).
A seguir, apresentamos o enunciado de vários problemas e construi-
remos juntos os correspondentes modelos matemáticos. Isso será um
bom começo para desenvolvermos a arte de modelar problemas mas
não é suficiente. Aconselha-se que outras referências citadas no Guia
da Disciplina sejam consultadas.
Observação 1.1
É importante ressaltar que não há uma regra para modelar
qualquer problema. A criatividade é bem-vinda; experiência e
vivência em modelar vários problemas diferentes é fundamental.
Por esse motivo, é importante que você pratique bastante e faça
todos os exercı́cios.
1.2 forma geral de um ppl
Em geral, o modelo de programação linear objetiva definir os valores
das n variáveis de decisão x1, x2, · · · , xn que maximizam ou minimi-
zam a função objetivo e respeitem todas as m funções de restrições do
modelo.
Uma possı́vel forma de aparecimento do modelo matemático é dado
por:
10 formulação de modelos
maximizar Z = c1x1 + c2x2+ · · · +cnxn
sujeito a:
a11x1 + a12x2+ · · · +a1nxn ≤ b1
a21x1 + a22x2+ · · · +a2nxn ≤ b2
...
...
...
am1x1 + am2x2+ · · · +amnxn ≤ bm
x1, x2, . . . , xn ≥ 0.
Os sı́mbolos Z, xj,j , aij e bi aparecerão frequentemente nos modelos
dos capı́tulos seguintes. O sı́mbolo Z representa o valor da função
objetivo, ou seja, é uma medida de desempenho global do sistema. O
parâmetro aij representa a quantidade do recurso i consumido com
a atividade j; o parâmetro cj é o incremento em Z que resultaria de
cada incremento unitário no nı́vel de atividade j; bi é o parâmetro
que indica a quantidade disponı́vel do recurso i para alocação em
atividades.
É importante ressaltar que no lugar da desigualdade “≤” podem
aparecer ainda a desigualdade “≥” ou a igualdade “=”. Ainda,
no lugar de maximizar pode aparecer minimizar. Estas modificações
dependem da natureza do problema modelado. Portanto, estejamos
cientes de que há muitas outras variações de modelo matemático
que podem aparecer.
1.3 exemplos de formulação matemática
Nesta seção vamos explorar problemas gerenciais com diferentes
complexidades e apresentar as suas formulações matemáticas.
Exemplo 1.1. [Problema de Mix de Produção, Hillier e Lieberman, página
26] Considere uma fábrica de produtos de vidro de alta qualidade, entre os
quais janelas e portas de vidro. A empresa possui três fábricas industriais. As
esquadrais dealumı́nio e ferragens são feitas na Fábrica 1, as esquadrias de
madeira são produzidas na Fábrica 2 e, finalmente, a Fábrica 3 produz o vidro
e monta os produtos. Em consequência da queda nos ganhos, a direção decidiu
modernizar a linha de produtos da empresa. Produtos não rentáveis estão
sendo descontinuados, liberando capacidade produtiva para o lançamento de
dois novos produtos com grande potencial de vendas:
• Produto 1: uma porta de vidro de 2.5m com esquadria de alumı́nio.
• Produto 2: uma janela duplamente adornada com esquadrias de madeira
de 1.20 × 1.80m.
O produto 1 requer parte da capacidade produtiva das Fábricas 1 e 3, mas
nenhuma da Fábrica 2. O produto 2, precisa apenas das Fábricas 2 e 3. A
divisão de marketing concluiu que a empresa poderia vender tanto quanto
fosse possı́vel produzir desses produtos por essas fábricas. Entretanto, pelo
1.3 exemplos de formulação matemática 11
fato de ambos os produtos poderem estar competindo pela mesma capacidade
produtiva na Fábrica 3, não está claro qual mix dos dois produtos seria o
mais lucrativo. Portanto, foi constituı́da uma equipe de PO para estudar essa
questão.
A equipe de PO começou promovendo discussões com a alta direção
para identificar os objetivos da diretoria para tal estudo. Essas dis-
cussões levaram à seguinte definição do problema:
Determinar quais devem ser as taxas de produção de modo a ma-
ximizar o lucro total, sujeito à restrições impostas pelas capacidades
produtivas limitadas disponı́veis nas três fábricas. (Cada produto será
fabricado em lotes de 20, de forma que a taxa de produção é definida
como o número de lotes produzidos por semana.) É permitida qual-
quer combinação de taxas de produção que satisfaça essas restrições,
inclusive não produzir nada de um produto e o máximo possı́vel do
outro.
A equipe de PO também identificou os dados que precisavam ser
coletados:
1. Número de horas de tempo de produção disponı́vel por semana
em cada fábrica para esses novos produtos. (A maior parte do
tempo nessas fábricas já está comprometida com os produtos atu-
ais, de modo que a capacidade disponı́vel para novos produtos
é bastante limitada.)
2. Número de horas de tempo de produção usado em cada fábrica
para cada lote produzido de cada novo produto.
3. Lucro por lote produzido de cada novo produto. Foi escolhido
o lucro por lote produzido como uma medida apropriada após
a equipe de PO ter concluı́do que o incremento de lucro de
cada lote adicional produzido ser aproximadamente constante
independentemente do número de lotes produzidos. Pelo fato
de nenhum custo adicional incorrer para o inı́cio da produção
e a comercialização de tais produtos, o lucro total de cada um
deles é aproximadamente esse lucro por lote vezes o número de
lotes produzidos.
A obtenção das estimativas razoáveis dessas quantidades exigiu o
apoio de pessoal-chave em várias unidades da empresa. A Tabela 1
sintetiza os dados reunidos.
A equipe de PO reconheceu imediatamente que se tratava de um
problema de programação linear clássico tipo mix de produtos e então
empreendeu a formulação do modelo matemático correspondente.
Apresentamos a solução nos seguintes passos:
A. Definição das variáveis de decisão:
x1 = número de lotes do produto 1 produzidos semanalmente
12 formulação de modelos
x2 = número de lotes do produto 2 produzidos semanalmente
Note que as variáveis de decisão devem assumir valores inteiros,
pois a produção dá-se por número de lotes. Este fato torna este
problema um problema de programação inteira. Porém, neste
exemplo especı́fico, podemos eliminar esta exigência de integra-
lidade e relaxar o problema, pois a solução ótima do problema
relaxado é igual à solução do problema com as exigências de
integralidade das variáveis. Assim, a formulação do problema
que apresentamos é de um modelo de programação linear.
B. Definição da função objetivo:
Z = lucro total por semana (em milhares de reais) obtido pela
produção dos produtos 1 e 2.
Assim, a função objetivo é descrita como:
Maximizar Z = 3x1 + 5x2.
C. Definição das restrições:
As restrições impostas pelo problema são de disponibilidade de
tempo de produção das fábricas 1, 2 e 3. A Tabela 1 indica que
cada lote de produto 1 fabricado por semana usa uma hora de
tempo de produção por semana na Fábrica 1, ao passo que estão
disponı́veis 4 (quatro) horas semanais. Essa restrição é expressa
matematicamente pela desigualdade
x1 ≤ 4.
De forma similar, a Fábrica 2 impõe a restrição
2x2 ≤ 12.
Observe que cada lote dos produtos 1 e 2 fabricados por semana
ocupam 3 e 2 horas de tempo de produção por semana na Fábrica
3, enquanto somente 18 horas de produção estão disponı́veis.
Essa restrição pode ser expressa matematicamente por:
Tabela 1: Dados para o Exemplo 1.1
Fábrica
Tempo de Produção por Lote
(em horas)
Tempo de Produção
Disponı́vel por Semana
(em horas)
Produto
1 2
1 1 0 4
2 0 2 12
3 3 2 18
Lucro por lote R$ 3000 R$ 5000
1.3 exemplos de formulação matemática 13
3x1 + 2x2 ≤ 18.
Para finalizar, precisamos adicionar as restrições de não-negatividade:
x1 ≥ 0, x2 ≥ 0
uma vez que produções negativas não fazem sentido.
Observação 1.2
As restrições de não-negatividade estarão presentes na
maioria dos problemas apresentados ao longo do curso.
Observação 1.3
As restrições de não-negatividade reduzem o estudo do
problema ao primeiro quadrante para o caso de duas
variáveis de decisão.
Em resumo, o problema de programação linear definido pode
ser entendido como escolher os valores de x1 e x2 de forma a:
Maximizar Z = 3x1 + 5x2
Sujeito às restrições
x1 ≤ 4
+ 2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 ≥ 0, x2 ≥ 0
Observação 1.4
O problema acima tem somente duas variáveis e o conjunto de
restrições pode ser representado no plano definindo uma região
que chamaremos de região viável. Isso é assunto para mais tarde,
mas vale a pena ficar atento.
Exemplo 1.2. Uma indústria vende dois produtos P1 e P2, ao preço por
tonelada de R$70, 00 e R$60, 00, respectivamente. A fabricação dos produtos
é feita em toneladas e consome dois tipos de recursos, que chamaremos de R1
e R2. Esses recursos estão disponı́veis nas quantidades de 10 e 16 unidades,
respectivamente. A produção de 1 tonelada de P1 consome 5 unidades de R1 e
2 unidades de R2, e a produção de 1 tonelada de P2 consome 4 unidades de
14 formulação de modelos
R1 e 5 unidades de R2. Formule um problema de programação linear para
determinar quantas toneladas de cada produto devem ser fabricadas para se
obter o maior faturamento possı́vel.
Solução:
Apresentamos a solução nos seguintes passos:
A. Definição das variáveis de decisão:
Observe que a decisão a ser tomada é a quantidade em toneladas
a ser produzida dos produtos 1 e 2. Importante notar que
as disponibilidades dos recursos são dadas. Portanto, estas
constituem parâmetros do problema, e não decisões a serem
tomadas. Desta forma, as duas variáveis de decisão são:
x1 = quantidade, em toneladas, fabricadas do produto 1
x2 = quantidade, em toneladas, fabricadas do produto 2
B. Definição da função objetivo:
Os custos unitários de fabricação dos produtos 1 e 2 são R$70, 00
e R$60, 00, respectivamente. Assumimos que tudo que é fabri-
cado é vendido. Assim, atribuı́mos a Z o valor da função objetivo
como:
Z = preço por tonelada vendida do produto vezes a quantidade
produzida do produto.
Matematicamente, a função objetivo é descrita como:
Maximizar Z = 70x1 + 60x2.
C. Definição das restrições:
As restrições dizem respeito às disponibilidades dos recursos
utilizados na produção. Veja que os processos de fabricação dos
produtos 1 e 2 consomem o recurso 1 e o total consumido está
limitado a disponibilidade deste recurso que é de 10 toneladas.
Assim, a primeira restrição é escrita como:
5x1 + 4x2 ≤ 10
e restriçãode utilização do recurso 2 é dada por:
2x1 + 5x2 ≤ 16.
Para finalizar, precisamos adicionar as restrições de não-negatividade:
x1 ≥ 0, x2 ≥ 0.
1.3 exemplos de formulação matemática 15
Exemplo 1.3 (Livro de Belfiore e Fávero, página 24). A empresa Venix
de brinquedos está revendo seu planejamento de produção de carrinhos e
triciclos. O lucro lı́quido por unidade de carrinho e triciclo é de R$12, 00 e
R$60, 00, respectivamente. As matérias-primas e os insumos necessários para
a fabricação de cada um dos produtos são terceirizados, cabendo à empresa
os processos de usinagem, pintura e montagem. O processo de usinagem
requer 15 minutos de mão de obra especializada por unidade de carrinho e 30
minutos por unidade de triciclo produzida. O processo de pintura requer 6
minutos de mão de obra especializada por unidade de carrinho e 45 minutos
por unidade de triciclo produzida. Já o processo de montagem necessita de
6 minutos e 24 minutos para uma unidade de carrinho e triciclo produzido,
respectivamente. O tempo disponı́vel por semana é de 36, 22 e 15 horas para
os processos de usinagem, pintura e montagem, respectivamente. A empresa
quer determinar quanto produzir de cada produto por semana, respeitando
as limitações de recursos, de forma a maximizar o lucro lı́quido semanal.
Formule o problema de programação linear que maximiza o lucro lı́quido da
empresa Venix.
Solução:
Apresentamos a solução nos seguintes passos:
A. Definição das variáveis de decisão:
Observe que as decisões a serem tomadas são as quantidades
de carrinhos e triciclos que devem ser produzidos por semana.
Representamos essas decisões por:
x1 = quantidade de carrinhos a serem produzidos por semana
x2 = quantidade de triciclos a serem produzidos por semana
Note que as variáveis de decisão devem assumir valores inteiros,
pois não faz sentido produzir uma quantidade fracionária de
carrinhos ou triciclos. Este fato torna este problema um pro-
blema de programação inteira. Porém, neste exemplo especı́fico,
podemos eliminar esta exigência de integralidade e relaxar o
problema, pois a solução ótima do problema relaxado é igual
à solução do problema com as exigências de integralidade das
variáveis. Assim, a formulação do problema que apresentamos
é de um modelo de programação linear.
B. Definição da função objetivo:
O lucro lı́quido por unidade de carrinho produzido é R$12,00, en-
quanto o lucro lı́quido por unidade de triciclo é R$60,00. Assim,
atribuı́mos a Z o valor da função objetivo como:
Z = lucro lı́quido semanal gerado a partir das quantidades de
carrinhos e triciclos fabricados.
Matematicamente, a função objetivo é descrita como:
16 formulação de modelos
Maximizar Z = 12x1 + 60x2.
C. Definição das restrições:
c1. Restrição para a atividade de usinagem:
0, 25x1 + 0, 5x2 ≤ 36
c2. Restrição para a atividade de usinagem:
0, 1x1 + 0, 75x2 ≤ 22.
c2. Restrição para a atividade de montagem:
0, 1x1 + 0, 4x2 ≤ 15.
Para finalizar, precisamos adicionar as restrições de não-negatividade:
x1 ≥ 0, x2 ≥ 0.
Assim, o modelo de programação linear final é dado por:
Maximizar Z = 12x1 + 60x2
Sujeito às restrições
0, 25x1 + 0, 50x2 ≤ 36
0, 10x1 + 0, 75x2 ≤ 22
0, 10x1 + 0, 40x2 ≤ 15
x1 ≥ 0, x2 ≥ 0.
Exemplo 1.4. Uma determinada empresa firmou um contrato para entrega
de janelas de casa para os próximos seis meses. As demandas para cada
mês são de 100, 250, 190, 140, 220 e 110 unidades, respectivamente. O
custo de produção por janela varia de mês para mês, dependendo do custo
da mão-de-obra, do material e de utilidades. A empresa estima que o custo
de produção por janela nos próximos seis meses seja 50, 45, 55, 48, 52 e
50, respectivamente. Para aproveitar a vantagem das variações no custo
de fabricação, a empresa pode optar por produzir mais do que o necessário
em determinado mês e reter as unidades excedentes para entregar em meses
posteriores. Entretanto, isso incorrerá em custos de armazenagem de R$ 8 por
janela, por mês, considerando o estoque no final do mês. Ao final do horizonte
de planejamento deseja-se que o estoque seja zero. Formule um modelo de
programação linear para determinar a programação ótima de produção como
o menor custo possı́vel.
Solução:
Apresentamos a solução nos seguintes passos:
1.3 exemplos de formulação matemática 17
A. Definição das variáveis de decisão: neste caso, o primeiro bloco de
variáveis de decisão corresponde ao quanto será produzido a
cada mês do horizonte de planejamento. Assim, as variáveis são
descritas como:
x1 = número de janelas produzidas no mês 1
x2 = número de janelas produzidas no mês 2
x3 = número de janelas produzidas no mês 3
x4 = número de janelas produzidas no mês 4
x5 = número de janelas produzidas no mês 5
x6 = número de janelas produzidas no mês 6
O quanto ficará armazenado em estoque ao final de cada mês
é também uma decisão do problema porque está intimamente
relacionada com a demanda e a quantidade produzida. Desta
forma, estas decisões também são descritas num segundo bloco
de variáveis de decisão da seguinte forma:
E1 = estoque de janelas ao final do mês 1
E2 = estoque de janelas ao final do mês 2
E3 = estoque de janelas ao final do mês 3
E4 = estoque de janelas ao final do mês 4
E5 = estoque de janelas ao final do mês 5
E6 = estoque de janelas ao final do mês 6
B. Definição da função objetivo: neste caso, a função objetivo é de mi-
nimizar todos os custos envolvidos. De acordo com o enunciado,
estes custos são: custo de estoque, custo de produção. Assim,
Z = custo total envolvido na produção = custo de produção +
custo de estoque
Assim, a função objetivo é descrita como:
Minimizar Z = 50x1 + 45x2 + 55x3 + 48x4 + 52x5 + 50x6 +
8(E1 + E2 + E3 + E4 + E5)
C. Definição das restrições: as restrições impostas pelo problema
são de atendimento de demanda. Isso significa, que para um
determinado mês a quantidade produzida deve ser no mı́nimo a
demanda do mês. Caso a produção seja excedente, o excedente
é armazenado na variável estoque. Assim, pode-se perceber que
o estoque ao final do mês 1 é igual a quantidade produzida
menos a quantidade demandada, o que matematicamente pode
ser escrito como:
E1 = x1 − 100.
18 formulação de modelos
Para os meses 2 a 5, observe que o estoque do mês anterior é
transmitido para o mês seguinte. Ou seja, no inı́cio do mês 2, a
disponibilidade de produtos é dada pela quantidade em estoque
advindo do mês anterior mais a quantidade a ser produzida,
que é representada matematicamente por x2 + E1.
Assim, o estoque ao final do mês 2 é dado pela diferença entre a
disponibilidade de produtos do mês menos a demanda do mês,
que pode ser escrito matematicamente por:
E2 = x2 + E1 − 250.
As restrições para os meses 3, 4 e 5 são similares:
E3 = x3 + E2 − 190
E4 = x4 + E3 − 140
E5 = x5 + E4 − 220.
Como no último mês não há estoque restante (ou seja, E6 = 0), a
restrição fica da seguinte forma:
0 = x6 + E5 − 110.
Para finalizar, precisamos adicionar as restrições de não-negatividade,
que de forma mais geral podem ser escritas como:
xi ≥ 0, Ei ≥ 0, para i = 1, 2, 3, 4, 5, 6,
uma vez que produções e estoque negativos não fazem sentido.
Exemplo 1.5 (Problema da Dieta, Belfiore e Fávero, página 32). A
anemia é uma doença decorrente de baixos nı́veis de hemoglobina no sangue,
proteı́na esta responsável pelo transporte de oxigênio. Segundo a hematolo-
gista Adriana Ferreira, a “ferropriva” é a anemia mais comum e é causada
pela deficiência de ferro no organismo. Para sua prevenção, deve-se adotar
uma dieta rica em ferro, vitamina A, vitamina B12 e ácido fólico. Esses
nutrientes podem ser encontrados em diversos alimentos, como espinafre,
brócolis, agrião, tomate, cenoura, ovo, feijão, gfraão de bico, soja, carne, fı́gado
e peixe. A tabela abaixo apresenta as necessidades diárias decada nutriente, a
respectiva quantidade em cada um dos alimentos e o preço por alimento. A
fim de previnir que seus pacientes apresentem esse tipo de anemia, o Hospital
Metrópole está estudando uma nova dieta. O objetivo é selecionar os ingredi-
entes, com o menor custo possı́vel, que farão parte das suas principais refeições
diárias (almoço e jantar), de forma que 100% das necessidades diárias de cada
um desses nutrientes sejam atendidas nas duas refeições. Além disso, o total
ingerido nas duas refeições não pode ultrapassar 1,5Kg.
1.3 exemplos de formulação matemática 19
Porção
de 100 gramas
Ferro Vit. A Vit. B12 Ác. fólico Preço
(mg) (UI) (mcg) (mg) (R$)
Espinafre 3 7400 0 0,4 0,3
Brócolis 1,2 138,8 0 0,5 0,2
Agrião 0,2 4725 0 0,1 0,18
Tomate 0,49 1130 0 0,25 0,16
Cenoura 1 14500 0,1 0,005 0,3
Ovo 0,9 3215 1 0,05 0,3
Feijão 7,1 0 0 0,056 0,4
Grão de bico 4,86 41 0 0,4 0,4
Soja 3 1000 0 0,08 0,45
Carne 1,5 0 3 0,06 0,75
Fı́gado 10 32000 100 0,38 0,8
Peixe 1,1 140 2,14 0,002 0,85
Necessidades
diárias
8 4500 2 0,4
Solução:
Apresentamos a solução nos seguintes passos:
A. Definição das variáveis de decisão: neste caso, o primeiro bloco de
variáveis de decisão corresponde ao quanto será produzido a
cada mês do horizonte de planejamento. Assim, as variáveis são
descritas como:
x1 = quantidade, em Kg, de espinafre consumido diariamente.
x2 = quantidade, em Kg, de brócolis consumido diariamente.
x3 = quantidade, em Kg, de agrião consumido diariamente.
x4 = quantidade, em Kg, de tomate consumido diariamente.
...
x12 = quantidade, em Kg, de peixe consumido diariamente.
B. Definição da função objetivo:
minimizar Z = 3x1 + 2x2 + 1, 8x3 + 1, 6x4 + 3x5 + 3x6 + 4x7 +
4x8 + 4, 5x9 + 7, 5x10 + 8x11 + 8, 5x12
C. Definição das restrições: as restrições dizem respeito às necessida-
des diárias mı́nimas de cada nutriente.
1. As necessidades mı́nimas diárias de ferro devem ser aten-
didas:
30x1 + 12x2 + 2x3 + 4, 9x4 + 10x5 + 9x6 + 71x7 +
+ 48, 6x8 + 30x9 + 15x10 + 100x11 + 11x12 ≥ 80.
20 formulação de modelos
2. As necessidades mı́nimas diárias de vitamina A devem ser
atendidas:
74000x1 + 1388x2 + 47250x3 + 11300x4 + 145000x5 +
+ 32150x6 + 410x8 + 10000x9 + 320000x11 + 1400x12 ≥ 45000.
3. As necessidades mı́nimas diárias de vitamina B12 devem
ser atendidas:
x5 + 10x6 + 30x10 + 1000x11 + 21, 4x12 ≥ 20.
4. As necessidades mı́nimas diárias de ácido fólico devem ser
atendidas:
4x1 + 5x2 + x3 + 2, 5x4 + 0, 05x5 + 0, 5x6 + 0, 56x7 +
+4x8 + 0, 8x9 + 0, 6x10 + 3, 8x11 + 0, 02x12 ≥ 4.
5. Total de alimento ingerido:
x1 + x2 + x3 + · · ·+ x12 ≤ 1, 5.
6. Restrições de não-negatividade:
xi ≥ 0, i = 1, . . . , 12.
Exemplo 1.6. Um hospital trabalha com um atendimento variável em de-
manda durante as 24 horas do dia. As necessidades distribuem-se segundo a
Tabela 2 exibe os turnos de trabalho com os horários e o número mı́nimo de
enfermeiros em cada turno.
Tabela 2: Tabela de Turnos e Horários
Turnos Horários Necessidade mı́nima
1 08:00 - 12:00 50
2 12:00 - 16:00 60
3 16:00 - 20:00 50
4 20:00 - 00:00 40
5 00:00 - 04:00 30
6 04:00 - 08:00 20
O horário de trabalho de um enfermeiro é de 8 horas quando ele entra nos
turnos 1, 2, 3, 4 e 6. O enfermeiro que entra no turno 5 trabalha apenas quatro
horas. Considere que cada enfermeiro recebe R£100 por hora de trabalho no
perı́odo diurno (08 às 20h) e R£125 no perı́odo noturno (20 às 08 h).Elaborar
o modelo de programação linear que minimize o gasto com a mão-de-obra.
Solução:
Apresentamos a solução nos seguintes passos:
1.3 exemplos de formulação matemática 21
A. Definição das variáveis de decisão:
A decisão a ser tomada é o número de enfermeiros alocados
no inı́cio de cada perı́odo. Desta forma, temos 6 variáveis de
decisão que são:
x1 = quantidade de enfermeiros alocados no inı́cio do turno 1
x2 = quantidade de enfermeiros alocados no inı́cio do turno 2
x3 = quantidade de enfermeiros alocados no inı́cio do turno 3
x4 = quantidade de enfermeiros alocados no inı́cio do turno 4
x5 = quantidade de enfermeiros alocados no inı́cio do turno 5
x6 = quantidade de enfermeiros alocados no inı́cio do turno 6
B. Definição da função objetivo:
O custo de alocação de enfermeiros num dado turno pode ser
escrito como:
Quantidade de horas × Custo por hora × quantidade de
enfermeiros alocados no perı́odo.
Desejamos minimizar a quantidade de enfermeiros em cada
turno. Assim, a função objetivo Z pode ser escrita como:
Z = 8× 100× (x1 + x2 + x3)+ 4× 125× x5 + 8× 125× (x4 + x6).
E finalmente fica:
Minimizar
Z = 800x1 + 800x2 + 800x3 + 1000x4 + 500x5 + 1000x6.
C. Definição das restrições:
As restrições dizem respeito às necessidades mı́nimas de enfer-
meiros em cada turno, ou seja, o total de enfermeiros alocados
em cada turno deve ser maior ou igual ao número mı́nimo
estabelecido na Tabela 2.
Observe que no turno 1, a disponibilidade de enfermeiros é dada
pelo número de enfermeiros que entraram no turno 6 mais os
enfermeiros que entraram no turno 1 que é dado por x6 + x + 1.
Assim, a restrição de necessidade mı́nima no turno 1 fica:
x1 + x6 ≥ 50.
As restrições para os turnos 2, 3, 4 e 5 são similares ao turno 1:
x1 + x2 ≥ 60
22 formulação de modelos
x2 + x3 ≥ 50
x3 + x4 ≥ 40
x4 + x5 ≥ 30
Uma vez que os enfermeiros que entraram no turno 5 trabalham
somente 4 horas, temos que no turno 6 aparecem somente os
enfermeiros que ingressaram neste turno.
x6 ≥ 20
Para finalizar, precisamos adicionar as restrições de não-negatividade:
xi ≥ 0 para i = 1, . . . , 6.
Exemplo 1.7. A Chidfair Company possui três fábricas que produzem car-
rinhos de bebê que devem ser remetidos para quatro centros de distribuição
(CDs). As fábricas 1, 2 e 3 produzem, respectivamente, 12,17, 11 remessas
por mês. Cada centro de distribuição precisa receber 10 remessas por mês.
O custo unitário de transporte entre cada fábrica e os respectivos centros de
distribuição é dada abaixo.
CD1 CD2 CD3 CD4 Produção
F1 10 2 20 11 12
F2 12 7 9 16 17
F3 4 14 16 18 11
Demanda 10 10 10 10 40
Quanto deve ser remetido de cada fábrica para cada um dos centros de
distribuição para minimizar o custo total de transporte? Formule um modelo
de programação linear que resolva o problema.
Solução:
Apresentamos a solução nos seguintes passos:
A. Definição das variáveis de decisão:
Temos 12 decisões a serem tomadas, que consistem em determi-
nar as quantidades transportadas das fábricas para os centros
consumidores.
xi,j = é a quantidade transportada da fábrica i para o centro de
distribuição j, onde i = 1, 2, 3 e j = 1, 2, 3, 4.
1.4 exercícios 23
B. Definição da função objetivo:
O custo é dado pela quantidade transportada vezes o custo
unitário de transporte. Dessa forma, a função objetivo é
Minimizar
Z = 10x1,1 + 2x1,2 + 20x1,3 + 11x1,4 + 12x2,1 +
+ 7x2,2 + 9x2,3 + 16x2,4 + 4x3,1 + 14x3,2 + 16x3,3 + 18x3,4
C. Definição das restrições:
Temos dois tipos de restrição. As primeiras são aquelas de
atendimento de demanda dos CDs. Todos os CDs devem re-
ceber exatamente a quantidade demandada. Matematicamente
escrevemos isso como:
x1,1 + x2,1 + x3,1 = 10
x1,2 + x2,2 + x3,2 = 10
x1,3 + x2,3 + x3,3 = 10
x1,4 + x2,4 + x3,4 = 10.
As próximas restrições são aquelas de capacidade produtiva
das fábricas, ou seja, devem ser transportadas exatamente as
quantidade produzidas em cada fábrica, que é representado
matematicamente como:
x1,1 + x1,2 + x1,3 + x1,4 = 12
x2,1 + x2,2 + x2,3 + x2,4 = 17
x3,1 + x3,2 + x3,3 + x3,4 = 11
Para finalizar, precisamos adicionar as restrições de não-negatividade:
xi,j ≥ 0 para i = 1, 2, 3 e j = 1, 2, 3, 4.
1.4 exercícios
1. Uma empresa fabrica dois produtos, A e B. O volume de vendas
de A é no mı́nimo 80% do total de vendas de ambos (A e B).
Contudo, a empresa não pode vender mais do que 100 unidades
de A por dia. Ambos os produtos usam uma matéria-prima cuja
disponibilidademáxima diária é 240 lb. As taxas de utilização da
matéria prima são 2 lb por unidade de A e 4 lb por unidade de B.
Os lucros unitários para A e B são R$20 e R$50, respectivamente.
Formule o problema como um problema de mix de produto.
24 formulação de modelos
2. Uma refinaria produz três tipos de gasolina: verde, azul e co-
mum. Cada tipo requer gasolina pura, octana e aditivo que são
disponı́veis nas quantidades de 9.600.000 litros, 4.800.000 litros e
2.200.000 litros por semana, respectivamente. As especificações
de cada tipo são:
• 1 litro de gasolina verde requer 0,22 litro de gasolina pura,
0,5 litro de octana e 0,28 litro de aditivo;
• 1 litro de gasolina azul requer 0,52 litro de gasolina pura,
0,34 litro de octana e 0,14 litro de aditivo;
• 1 litro de gasolina comum requer 0,74litro de gasolina pura,
0,20 litro de octana e 0,06 litro de aditivo.
Como regra de produção, baseada em demanda de mercado, o
planejamento da refinaria estipulou que a quantidade de gaso-
lina comum deve ser, no mı́nimo, igual a 16 vezes a quantidade
de gasolina verde e que a quantidade de gasolina azul seja no
máximo igual a 600.000 litros por semana. A empresa sabe que
cada litro de gasolina verde, azul e comum dá uma margem de
contribuição para o lucro de R$0,30, R$0,25 e R$0,20 respectiva-
mente, e seu objetivo é determinar o programa de produção que
maximiza a margem total de contribuição para o lucro. Formule
o problema como um problema de programação linear.
3. A cidade de Progress está estudando a viabilidade de introduzir
um sistema de ônibus para transporte de massa que aliviará
o problema da mistura de nevoeiro com fumaça pela redução
do trânsito no centro da cidade. O estudo procura o número
mı́nimo de ônibus que possa dar conta das necessidades de trans-
porte. Após colher as informações necessárias, o engenheiro da
prefeitura percebeu que o número mı́nimo de ônibus necessários
variava de acordo com a hora do dia, e que o número de ônibus
requeridos poderia ser aproximado para valores constantes em
intervalos sucessivos de 4 horas. A Figura 1 abaixo resume as
constatações do engenheiro. Devido à manutenção diária obri-
gatória, cada ônibus pode circular apenas 8 horas sucessivas
por dia. Formule um problema de programação linear de modo
que o número de ônibus em funcionamento em cada turno que
atenda à demanda seja mı́nimo e que ao mesmo tempo minimize
o número total de ônibus em funcionamento.
4. Um fabricante de geladeira precisa decidir quais modelos deve
produzir em uma nova fábrica recentemente instalada. O de-
partamento de marketing e vendas realizou uma pesquisa de
mercado que indicou que, no máximo, 1500 unidades do modelo
de luxo e 6000 unidades do modelo básico podem ser vendidas
no próximo mês. A empresa já contratou um certo número de
empregados e, com isso, dispõe de uma força de trabalho de
1.4 exercícios 25
Figura 1: Número mı́nimo de ônibus em funcionamento por horário
25000 homens-hora por mês. Cada modelo de luxo requer 10
homens-hora e cada modelo básico requer 8 homens-hora para
ser montado. Além disso, uma mesma linha de montagem é
compartilhada pelos dois modelos e considere que a capacidade
de produção desta linha seja de 4500 geladeiras por mês. O
lucro unitário do modelo de luxo é de $100,00, e do modelo
básico é de $50,00. Deseja-se determinar quanto produzir de
cada modelo de modo a maximizar o lucro da empresa.
5. Considere uma fábrica de pré-moldados que produz dois tipos
de vigas, cujas demandas para as próximas três semanas são
conhecidas, conforme a Tabela 3.
Os produtos utilizam os mesmos tipos de recursos, porém em
quantidades diferentes. Suponha, por simplicidade, que apenas
um centro de trabalho esteja disponı́vel para a produção dos
dois itens, cuja disponibilidade é de 40 horas por perı́odo e que a
produção de uma unidade do item 1 consuma 15 minutos e uma
unidade do item 2 consuma 20 minutos. Os custos de produção
por perı́odo são conhecidos e dados pela Tabela 4.
Admite-se que a produção possa ser antecipada e estocada para
ser utilizada nos perı́odos seguintes. Os custos de estocagem são
dados na Tabela 5 (por exemplo, uma unidade do item 1 pode
ser produzida no perı́odo 2 e guardada em estoque para atender
a demanda no perı́odo 3, por $3,00/unidade). Deseja-se definir
um plano da produção de modo que os pedidos sejam atendidos
ao menor custo de produção e estocagem. Os estoques iniciais
dos dois produtos são nulos e deseja-se que seus estoques ao
final do horizonte de planejamento também sejam nulos.
26 formulação de modelos
Tabela 3: Demanda de Vigas
Demanda de Vigas Perı́odo 1 Perı́odo 2 Perı́odo 3
Item 1 100 90 120
Item 2 40 50 80
Tabela 4: Custos de Produção
Custos de Produção Perı́odo 1 Perı́odo 2 Perı́odo 3
Item 1 20 20 30
Item 2 20 20 30
6. A Investe e Futuro possui um capital de 14000 reais para in-
vestir numa carteira de 4 projetos, tendo estudado a rentabili-
dade dos mesmos. Na Tabela 6 apresenta-se, para cada pro-
jeto/investimento, o montante de capital a investir e a rentabili-
dade esperada.
Formule um modelo de programação linear que maximiza a
rentabilidade esperada.
7. Uma empresa produz uma vasta variedade de bicicletas. Esta-
mos interessados em determinar um plano de produção para
bicicleta de corrida cuja produção requer materiais especiais e
equipamentos de produção. No máximo, um lote de bicicleta
é produzido por mês, por conta da baixa demanda e importan-
tes economias de escala nos custos de confecção do produto.
Por causa da necessidade de instalar equipamentos especiais e
ferramentas no começo de cada lote de produção, há um alto
custo de set-up, e por isso não há sentido em produzir muito
freqüentemente. O custo de produção de um lote é aproxima-
damente dado pelo custo de set-up mais o custo marginal, que
corresponde ao tempo exigido para a produção de cada bicicleta.
Para a bicicleta de corrida, o custo de set-up é de R$ 5000 e o
custo marginal é de R$ 100. Assim, o custo de produzir uma
bicicleta de corrida é R$ 5100, e R$ 6000 para a produção de um
lote de 10 bicicletas. As restrições de capacidade são ignoradas
no planejamento deste único produto, pois trabalhadores podem
ser contratados temporariamente caso seja necessário.
1.4 exercícios 27
Tabela 5: Custos de Estocagem
Custos de Estocagem Perı́odo 1 Perı́odo 2
Item 1 2 3
Item 2 2,5 3,5
Tabela 6: Tabela de Investimento
Projeto Capital Rentabilidade
1 5000 16000
2 7000 22000
3 4000 12000
4 3000 8000
2
R E S O L U Ç Ã O D E M O D E L O S : M É T O D O G R Á F I C O
Antes de introduzir os principais conceitos deste capı́tulo, vamos preci-
sar de algumas definições e conceitos preliminares. O primeiro ponto
é de que todo problema de programação linear pode ser escrito em
forma matricial. Conhecimentos em Álgebra Linear são importantes
para esta disciplina.
2.1 forma matricial de um ppl
Dado um PPL com m restrições e n variáveis de decisão, sempre é
possı́vel reescrevê-lo em formato matricial. Considere o seguinte PPL
com 2 variáveis (n = 2) e 2 restrições (m = 2).
max 12x1 + 8x2
2x1 + 3x2 ≤ 4
2x1 + x2 ≤ 1
x1, x2 ≥ 0.
Vamos converter o problema no formato matricial do tipo:
max z = cx
Ax ≤ b
x ≥ 0
onde A é uma matrix m × n, c é um vetor no Rn, b é um vetor no
Rm e x é um vetor no Rn. De outro modo, a matriz A é a matriz dos
coeficientes das restrições, c é o vetor de custos, b é o vetor de termos
independentes e x é o vetor de variáveis de decisão.
Neste caso, A =
(
2 3
2 1
)
, b =
(
4
1
)
, cT =
(
12
8
)
e x =(
x1
x2
)
.
Observação 2.1: D
da uma matrix B, a sua matriz transposta BT é obtida a partir
da troca de linhas e colunas. Assim, se A =
(
2 3
2 1
)
, então a
sua transposta é dada por AT =
(
2 2
3 1
)
.
29
30 resolução de modelos : método gráfico
2.2 definições básicas
Definição 2.1 (Solução Viável). Dizemosque uma solução x′ é viável se
Ax′ = b.
De outro modo, se uma solução satisfaz a todas as restrições do PPL
simultaneamente, dizemos que essa solução é viável (ou factı́vel).
Definição 2.2 (Região viável F). A região viável de um PPL, denotada por
F, é o conjunto de todos os pontos x tais que Ax = b.
De outro modo, a região viável de um PPL é formada pelo conjunto
de todas as soluções viáveis.
Definição 2.3 (Solução ótima). Uma solução viável x∗ é ótima se Z∗ =
cx∗ ≥ Z = cx para todo x ∈ F.
Retomando o PPL
max 12x1 + 8x2
2x1 + 3x2 ≤ 4
2x1 + x2 ≤ 1
x1, x2 ≥ 0
note que, dentre outros, os pontos (0, 0), (0, 1), (1/2, 0), (0, 1/2) são
viáveis, enquanto os pontos (1/2, 1/2), (2, 0) são inviáveis, pois violam
a uma das restrições impostas pelo problema. A seguir, vamos ver
como representar graficamente a região viável desse problema, u seja,
delimitar uma região onde todos os conjuntos de pontos dentro dessa
região são pontos viáveis.
2.3 representação geométrica
Todos os PPLs com somente duas variáveis podem ser representados
no plano e os estudos das diversas situações que podem acontecer nes-
ses casos nos dá uma dica do que acontece em espaços de dimensões
maiores. Desta forma, o estudo destes casos se torna importante.
Dividiremos em 3 passos a representação geométrica e a solução do
problema com duas variáveis:
1. Transformar as inequações em equações e representar as retas
no plano
2. Determinar a região delimitada pelas restrições
3. Determinar a solução ótima
2.3 representação geométrica 31
Exemplo 2.1. Considere o seguinte problema de programação linear abaixo.
max 12x1 + 8x2
2x1 + 3x2 ≤ 4
2x1 + x2 ≤ 1
x1, x2 ≥ 0
Vamos detalhar o passo a passo da representação geométrica e solução do
PPL. Antes de resolvermos o problema propriamente dito, estamos interes-
sados em representar a região viável (factı́vel) no plano. Vamos dividir esta
representação em dois passos, Passo 1 e Passo 2. A solução do problema é
obtida no Passo 3.
Passo 1: Transformar as inequações em equações e representar as retas
no plano. As restrições em forma de equação ficam:
2x1 + 3x2 = 4
2x1 + x2 = 1
Para o desenho da reta definimos os interceptos das curvas com os eixos:
na reta 1, quando x1 = 0, a equação é dada por 2.0 + 3x2 = 4 , e portanto,
x2 = 4/3. Quando x2 = 0, a equação é dada por 2x1 + 3.0 = 4, e portanto
x1 = 2. Assim, os dois interceptos são os pontos (2,0) e (0,4/3). A reta
desejada é obtida conectando-se os interceptos.
Na reta 2, quando x1 = 0, a equação é dada por 2.0 + x2 = 1, e portanto,
x2 = 1. Quando x2 = 0, a equação é dada por 2x1 + 1.0 = 1, e portanto
x1 = 1/2. Assim, os dois interceptos são os pontos (0,1) e (1/2,0). A reta
desejada é obtida conectando-se os interceptos.
A Figura 2 mostra o desenho das equações das retas 1 e 2.
-1 1 2 3 4 5 6
x1
-1
1
2
3
4
x2
2x1 + 3x2 = 4
2x1 + x2 = 1
Figura 2: Desenho das equações das retas do Exemplo 1
Passo 2: Determinar a região delimitada pelas restrições
32 resolução de modelos : método gráfico
Observe que o ponto (x1, x2) = (0, 0) satisfaz à inequação da restrição 1,
uma vez que 2.0 + 3.0 = 0 ≤ 4. O ponto (x1, x2) = (0, 0) também satisfaz
à inequação da restrição 2, uma vez que 2.0 + 1.0 = 0 ≤ 1. Desta forma,
o semi-plano definido pelas inequações do PPL estão abaixo das retas das
restrições. As restrições de não negatividade, x1 ≥ 0 e x2 ≥ 0 delimitam a
região ao primeiro quadrante. A região viável então fica definida pela região
hachurada F da Figura 3.
-1 1 2 3 4 5 6
x1
-1
1
2
3
4
x2
F
2x1 + 3x2 4
2x1 + x2 1
Figura 3: Região Viável do Exemplo 1
Passo 3: Determinar a solução ótima
Nesta etapa, desejamos encontrar o ponto x = (x1, x2) da região viável
F que apresenta o maior valor para a função objetivo Z = cx, o qual deno-
minamos de solução ótima. Desta forma, dizemos que x∗ é solução ótima
se
Z∗ = cx∗ ≥ Z = cx
para todo ponto x ∈ F. Note que a região F tem infinitos pontos que satisfazem
às restrições do problema, o que torna o método de inspeção de todos os
pontos viáveis e sua correspondente avaliação na função objetivo uma tarefa
impossı́vel. A melhor estratégia para encontrar a solução ótima é identificar
a direção na qual a função lucro z = 12x1 + 8x2 aumenta, pois estamos
interessados em maximizar . Para tal, atribuı́mos valores crescentes arbitrários
para z gerando as curvas de nı́vel da função objetivo, que são as linhas
pontilhadas da Figura 4. Por exemplo, usar z = 6 e z = 8 equivaleria a
representar em gráfico as duas retas, 12x1 + 8x2 = 6 e 12x1 + 8x2 = 6.
Assim, a direção de aumento de z é a mostrada pelas linhas pontilhadas na
Figura 4.
O ponto ótimo será o último ponto viável que a curva de nı́vel tangenciar
na região viável, ou seja, qualquer incremento em z faz com que a curva
de nı́vel saia da região viável. Por exemplo, em z = 9 a curva de nı́vel
2.3 representação geométrica 33
-1 1 2 3 4 5 6
x1
-1
1
2
3
4
x2
F
2x1 + 3x2 4
2x1 + x2 1
Figura 4: Curvas de Nı́vel do Exemplo 1
12x1 + x2 = 9 não passa mais pela região viável. Neste caso, a solução ótima
do Exemplo 1 é dada pela resolução das equações relacionadas com as retas
x1 = 0
2x1 + x2 = 1.
(1)
Logo, a solução ótima é x1 = 0 e x2 = 1, e o valor ótimo é igual a Z = 8.
Exemplo 2.2. Considere o PPL a seguir.
min 3x1 + 9x2
x1 + x2 ≥ 8
2x1 − 3x2 ≤ 0
3x1 + x2 ≥ 0
x1 , x2 ≥ 0
Solução: Veja que este é um problema de minimizar e que os sinais das
desigualdades são “≥” e “≤”.
Passo 1: Transformar as inequações em equações e representar as retas
no plano. As equações correspondentes são:
x1 + x2 = 8 (2)
2x1 − 3x2 = 0 (3)
3x1 + x2 = 0 (4)
Para o desenho da reta definimos os interceptos das curvas com os eixos:
na equação 2, quando x1 = 0, a equação é dada por 0 + x2 = 8 , e portanto,
34 resolução de modelos : método gráfico
x2 = 8. Quando x2 = 0, a equação é dada por x1 + 0 = 8, e portanto x1 = 8.
Assim, os dois interceptos são os pontos (0,8) e (8,0).
Na equação 3, vamos determinar dois pontos sobre a reta. Quando x1 = 3,
a equação é dada por 2.3− 3x2 = 0, e portanto, x2 = 2. Quando x2 =
1, a equação é dada por 2x1 − 3.2 = 0, e portanto x1 = 3/2. Assim, a
reta correspondente à equação 3 passa pelos pontos (3, 2) e (3/2, 1). Com
raciocı́nio análogo, obtém-se que a reta correspondente à equação 4, passa
pelos pontos (1,−3) e (−1, 3).
A Figura 5 mostra as equações das retas.
-2 2 4 6 8 10 12
x1
-2
2
4
6
8
x2
x1 + x2 = 8
2x1 − 3x2 = 0
3x1 + x2 = 0
Figura 5: Desenho das equações das retas do Exemplo 2
Passo 2: Determinar a região delimitada pelas restrições
Observe que o ponto (x1, x2) = (0, 0) não satisfaz à inequação da restrição
1, uma vez que 1.0 + 1.0 = 0 ≤ 8. Assim, o semi-plano definido pela
inequação está acima da reta. O ponto (x1, x2) = (0, 4) satisfaz à inequação
da restrição 2. Desta forma, o semi-plano definido pela inequação 2 do PPL
está acima da reta. O ponto (x1, x2) = (0, 2) satisfaz à inequação da restrição
3. Desta forma, o semi-plano definido pela inequação 2 do PPL está acima
da reta. As restrições de não negatividade, x1 ≥ 0 e x2 ≥ 0 delimitam a
região ao primeiro quadrante. A região viável então fica definida pela região
hachurada F da Figura 6.
Passo 3: Determinar a solução ótima
O ponto ótimo é encontrado a partir das curvas de nı́vel da função objetivo.
A estratégia consiste em identificar a direção de decréscimo da função objetivo
z = 3x1 + 9x2, pois estamos interessados em minimizar o valor de z. Para
tal, atribuı́mos valores decrescentes arbitrários para z gerando as curvas de
nı́vel da função objetivo, que são as linhas pontilhadas da Figura 7. Por
exemplo, usar z = 90 e z = 72 equivaleria a representar em gráfico as duas
2.3 representação geométrica 35-2 2 4 6 8 10 12
x1
-2
2
4
6
8
x2
F
x1 + x2 ≥ 8
2x1 − 3x2 0
3x1 + x2 ≥ 0
Figura 6: Região Viável do Exemplo 2
retas, 3x1 + 9x2 = 90 e 3x1 + 9x2 = 72. Assim, a direção de decréscimo de
z é a mostrada pelas linhas pontilhadas na Figura 4.
A solução ótima é dada pelo último ponto viável tangenciado pela curva de
nı́vel. Portanto, a solução ótima é x1 = 24/5 e x2 = 16/5. O valor ótimo é
dado por z = 216/5.
36 resolução de modelos : método gráfico
-2 2 4 6 8 10 12
x1
-2
2
4
6
8
x2
F
x1 + x2 ≥ 8
2x1 − 3x2 0
3x1 + x2 ≥ 0
Figura 7: Curvas de Nı́vel do Exemplo 2
EXERCÍCIOS: Resolva os PPLs abaixo pelo método gráfico.
Problema 1
Maximizar z = 5x1 + 2x2
x1 ≤ 4
x2 ≤ 3
x1 + 2x2 ≤ 8
x1 , x2 ≥ 0
Solução: A região viável do problema é dada pela Figura 8
A partir do traçado das curvas de nı́vel da função objetivo, conforme a
Figura 9, obtém-se a solução ótima x1 = 4 e x2 = 2, e o valor ótimo z = 24.
2.3 representação geométrica 37
-2 2 4 6 8 10 12
x1
-2
2
4
6
8
x2
F
x1 4
x2 3
x1 + 2x2 8
Figura 8: Região Viável
Problema 2
Maximizar z = x1 + 3x2
x1 ≤ 40
x2 ≤ 60
x2 ≥ 10
x1 + x2 ≥ 20
3x1 + 2x2 ≤ 180
x1 , x2 ≥ 0
Solução:
A região viável do problema é dada pela Figura 10.
A partir do traçado das curvas de nı́vel da função objetivo, conforme a
Figura 11, obtém-se a solução ótima x1 = 20 e x2 = 60, e o valor ótimo
z = 200.
38 resolução de modelos : método gráfico
-2 2 4 6 8 10 12
x1
-2
2
4
6
8
x2
F
x1 4
x2 3
x1 + 2x2 8
Figura 9: Curvas de Nı́vel e solução ótima
-50 50 100 150 200 250
x1
50
100
150
x2
F
x1 40
x2 60
x2 ≥ 10
x1 + x2 ≥ 20
3x1 + 2x2 180
Figura 10: Região Viável
2.3 representação geométrica 39
-50 50 100 150 200 250
x1
50
100
150
x2
F
x1 40
x2 60
x2 ≥ 10
x1 + x2 ≥ 20
3x1 + 2x2 180
Figura 11: Curvas de Nı́vel e solução ótima
Problema 3
Minimizar z = 4x1 + x2
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Solução: Neste problema temos uma restrição de igualdade. Neste caso,
a região viável do problema está exatamente em cima de um segmento
de reta da equação 3x1 + x2 = 3. Este segmento de reta vai do ponto
(3/5, 6/5) (intersecção entre as retas 3x1 + x2 = 3 e 4x1 + 3x2 = 6) ao
ponto (2/5, 9/5) (intersecção entre as retas 3x1 + x2 = 3 e x1 + 2x2 = 4).
Veja o gráfico da Figura 12.
A partir do traçado das curvas de nı́vel da função objetivo, conforme a
Figura 13, obtém-se a solução ótima x1 = 2/5 e x2 = 9/5, e o valor ótimo
z = 17/5.
40 resolução de modelos : método gráfico
-2 2 4 6 8
x1
-1
1
2
3
4
5
6
x2
F
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 4
Figura 12: Região Viável
-2 2 4 6 8
x1
-1
1
2
3
4
5
6
x2
F
3x1 + x2 = 3
4x1 + 3x2 ≥ 6
x1 + 2x2 4
Figura 13: Curvas de Nı́vel e solução ótima
2.3 representação geométrica 41
Exercı́cios de Autoavaliação
1. Minimizar Z = 40x1 + 50x2
Sujeito a:
2x1 + 3x2 ≥ 30
x1 + x2 ≥ 12
2x1 + x2 ≤ 20
x1 ≥ 0 , x2 ≥ 0
Solução: Solução ótima: x1 = x2 = 6. Valor ótimo: Z = 540.
2. Maximize Z = x1 + 2x2
Sujeito a:
−x1 + x2 ≤ 2
4x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0
Solução: Solução ótima: x1 = 2/5, x2 = 12/5. Valor ótimo:
Z = 26/5.
3. Maximize Z = 6x1 + 4x2
Sujeito a:
2x1 + 3x2 ≤ 18
5x1 + 4x2 ≤ 40
x1 ≤ 6
x2 ≤ 8
x1 ≥ 0, x2 ≥ 0
Solução: Solução ótima: x1 = 6, x2 = 2. Valor ótimo: Z = 44.
4. Minimizar Z = 10x1 + 6x2
Sujeito a:
4x1 + 3x2 ≥ 24
2x1 + 5x2 ≥ 20
x1 ≤ 8
x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Solução: Solução ótima: x1 = 3/2, x2 = 6. Valor ótimo: Z = 51.
42 resolução de modelos : método gráfico
5. Maximizar Z = 3x1 + 2x2
Sujeito a:
x1 + x2 ≤ 6
5x1 + 2x2 ≤ 20
x1 ≥ 0, x2 ≥ 0
Solução: Solução ótima: x1 = 8/3, x2 = 10/3. Valor ótimo:
Z = 44/3.
	Modelos Matemáticos em Problemas Gerenciais
	Formulação de Modelos
	Hipóteses do Modelo de Programação Linear
	Forma Geral de um PPL
	Exemplos de formulação matemática
	Exercícios
	Resolução de Modelos: Método Gráfico
	Forma matricial de um PPL
	Definições Básicas
	Representação Geométrica