MÉTODOS QUANTITATIVOS TEMA 2

Prévia do material em texto

MÉTODOS QUANTITATIVOS – TEMA 2 
 
APLICAÇÃO DA PROGAMAÇÃO LINEAR 
 
DESCRIÇÃO: Modelagem de problemas clássicos de programação linear: 
fabricação versus compra, problemas de mistura, planejamento, produção e estoques, transporte, 
transbordo e alocação. 
PROPÓSITO: Discutir os problemas clássicos de programação linear a fim de entender a técnica 
de modelagem e a importância desse campo do conhecimento, essencial para a sua formação e 
atuação no processo de decisão de problemas complexos. 
 
INTRODUÇÃO: Os modelos são simplificações do objeto ou problema de decisão que 
representam. Você pode estar se perguntando: como a modelagem matemática pode auxiliar o 
processo de tomada de decisão, em especial em problemas complexos? A modelagem 
matemática possibilita examinar diferentes cenários, em geral, de forma mais rápida e barata do 
que analisar a situação na realidade. 
O foco deste conteúdo é a programação linear, uma das técnicas mais difundidas na Pesquisa 
Operacional (PO). Aqui, reforçaremos os conceitos sobre a construção de modelos 
de programação linear na modelagem de problemas clássicos de programação linear, 
abordando suas diferentes aplicações. Com isso, passaremos a dominar a técnica de modelagem 
e entenderemos melhor a importância desse campo do conhecimento, em especial, a sua 
aplicação no planejamento de redes logísticas, por meio do problema de transporte e 
transbordo, e de alocação, problemas clássicos de programação linear que merecem ser 
destacados! 
 
MÓDULO 1 - Aplicar a técnica de modelagem em problemas clássicos de programação 
linear 
MODELAGEM DE PROBLEMAS DE PROGRAMAÇÃO LINEAR - O processo de modelagem 
consiste em transformar a linguagem do problema em linguagem matemática. Para isso, 
devemos começar definindo as variáveis de decisão e, posteriormente, a função objetivo e as 
restrições, conforme os passos ilustrados abaixo: 
• Identificação das variáveis de decisão 
• Identificação da função objetivo 
• Identificação do conjunto de restrições 
 
Atenção! O passo mais importante no desenvolvimento de modelos de programação linear 
consiste na definição correta das variáveis de decisão. Um equívoco na seleção das variáveis de 
decisão implica erros na identificação da função objetivo e do conjunto de restrições. 
Existem classes de modelos de programação linear que são adaptáveis a uma série de situações 
práticas, sendo considerados como “problemas típicos.” Esses modelos seguem padrões 
semelhantes, de modo que podemos considerar que formam diferentes “classes” de problemas. 
Assim, se soubermos modelar um destes problemas típicos, provavelmente conseguiremos 
modelar os demais problemas da mesma classe. Por isso, é tão importante conhecer esses 
padrões e entender a lógica por trás da construção destes modelos matemáticos 
(RODRIGUES et al., 2014). 
Neste módulo, serão abordados alguns dos principais modelos de programação linear 
considerados “típicos.” Devemos entender como funciona o padrão de modelagem para cada 
problema típico para que, então, possamos aplicar essa mesma lógica a outros problemas da 
mesma classe, ou seja, que seguem o mesmo padrão. 
 
Trataremos, a seguir, dos problemas da mistura, do planejamento de produção e de estoques, e 
fazer versus comprar. Estes são problemas clássicos que podem ser aplicados em diferentes 
setores produtivos. 
 
PROBLEMA DA MISTURA - Muitos modelos de programação linear representam situações em 
que o tomador de decisão deseja minimizar o custo para atender a determinadas condições 
(restrições). O problema da mistura, também conhecido como o problema da dieta, é um dos 
modelos clássicos que se encaixa neste tipo de padrão. 
Veja mais informações sobre o problema da dieta: 
O PROBLEMA DA DIETA - O problema da dieta foi proposto pela primeira vez por Stiger 
(1945), tendo sido um dos primeiros problemas de otimização linear a ser implementado na 
prática com sucesso. Neste tipo de problema, o tomador de decisão deseja determinar níveis de 
utilização de matérias-primas na composição de uma ração alimentar, que deve respeitar certas 
características nutricionais, estando limitado à disponibilidade de matérias-primas e insumos, bem 
como ao atendimento da demanda. É importante destacar que este tipo de problema não se limita 
à dieta humana, sendo aplicado também à elaboração de rações para gado, peixe, aves etc. 
Entretanto, de forma mais ampla, o problema da mistura não se restringe apenas à composição 
de rações alimentares. O problema da mistura pode ser aplicado à produção de ligas metálicas, à 
especificação de combustíveis, à fabricação de remédios ou de produtos químicos em geral, à 
produção de adubos ou de papel. Em suma, o problema da mistura representa uma classe de 
modelos clássicos, que podem ser aplicados a diferentes setores. Neste tipo de problema, 
diferentes insumos devem ser misturados em uma proporção ideal para fabricar produtos para a 
comercialização. 
 
TEORIA NA PRÁTICA - EXEMPLO - PROBLEMA DA DIETA 
Uma mãe está muito preocupada com a alimentação de seus filhos. Ela deseja que as crianças 
tenham uma alimentação equilibrada e, assim, consultou uma nutricionista que lhe recomendou 
que eles comam, no mínimo, 10mg de vitamina A, 70mg de vitamina C e 250mg de vitamina D 
por dia. 
Porém, além de se preocupar com a qualidade da alimentação, essa mãe também está 
preocupada com os custos. Ela deseja oferecer aos seus filhos essa dieta equilibrada, porém ao 
menor custo possível. Por isso, ela fez uma pesquisa e descobriu as informações nutricionais 
para diferentes tipos de alimento, conforme apresentado na tabela a seguir: 
A mãe também foi ao supermercado e 
verificou que um litro de leite custa R$2,00, 
um quilo de carne custa R$20,00, um quilo 
de peixe custa R$25,00 e para preparar 
100g de salada ela gastaria R$3,00. 
Vamos usar nossos conhecimentos de programação linear para ajudar essa mãe a escolher a 
melhor dieta para seus filhos com o menor custo possível! 
RESOLUÇÃO: Definir variáveis de decisão 
O primeiro passo para a modelagem deste exemplo de um clássico problema da dieta é a 
definição das variáveis de decisão. A variável de decisão deve ser xi, sendo x a quantidade de 
alimento do tipo “i” a ser consumida por dia. Logo, temos: 
• x1 = litros de leite a serem consumidos por dia pelas crianças; 
• x2 = quilos de carne a serem consumidos por dia pelas crianças; 
• x3 = quilos de peixe a serem consumidos por dia pelas crianças; 
• x4 = 100g de salada a serem consumidos por dia pelas crianças. 
 
Identificar a função objetivo: Em seguida, devemos identificar a função objetivo. Sabemos que 
a mãe deseja gastar o menor valor possível, de modo que este deve ser um problema 
de minimização! A mãe já fez a pesquisa de preços, então só nos falta montar a função objetivo: 
Min Z= 2x1+20x2+25x3+3x4 
 
Identificar o conjunto de inequações: Porém, não se esqueça de que a mãe também está 
preocupada com a qualidade nutricional da alimentação de seus filhos e que a nutricionista 
indicou que as crianças devem comer, no mínimo, 10mg de vitamina A, 70mg de vitamina C e 
250mg de vitamina D por dia. As informações nutricionais em mg de vitamina A, C e D dos 
alimentos leite, carne, peixe e salada são apresentadas na tabela de informações nutricionais, já 
Vitamina Leite (l) Carne (kg) Peixe (kg) Salada (100g) 
A 2 2 10 20 
C 50 20 10 30 
D 80 70 10 80 
apresentada. Assim, podemos identificar o conjunto de inequações que representam estas 
restrições. São elas: 
2x1+2x2+10x3+20x4≥10→Vitamina A 
 
50x1+20x2+10x3+30x4≥70→Vitamina C 
 
80x1+70x2+10x3+80x4≥250 →Vitamina D 
 
Não podemos nos esquecer das restrições de não negatividade para as variáveis de decisão. 
Logo, temos que: 
x1,x2,x3,x4≥0 
 
Modelo 
Enfim, temos que o modelo para este exemplo do problema da dieta é: 
Min Z= 2x1+20x2+25x3+3x4 
Sujeito a: 
2x1+2x2+10x3+20x4≥10 
50x1+20x2+10x3+30x4≥70 
80x1+70x2+10x3+80x4≥250 
 x1,x2,x3,x4≥0 
 
 
PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO E DE ESTOQUES - Neste tipo deproblema, deseja-se determinar níveis para atividades de produção, considerando que a 
capacidade de produção de cada atividade sofra restrições de caráter tecnológico e prático. 
O problema do planejamento de produção pode ser estático ou dinâmico. 
Problema estático 
No problema estático, considera-se a produção em determinado horizonte de programação 
finito, de modo que as formulações contemplam apenas um período, conforme verificaremos no 
exemplo a seguir: 
 
TEORIA NA PRÁTICA - PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO ESTÁTICO 
Uma fábrica de bicicletas está planejando seus níveis de produção para o próximo semestre. O 
custo unitário da produção da bicicleta infantil é de R$280,00, enquanto o custo unitário da 
produção da bicicleta para adultos é de R$620,00. 
São necessários seis trabalhadores para fazer um lote de 8 bicicletas infantis por dia, enquanto 
três trabalhadores conseguem fabricar 5 bicicletas de adulto por dia. Existem 200 pessoas 
disponíveis para a produção de bicicletas, podendo ser alocadas em qualquer um dos dois 
serviços. 
A fábrica tem capacidade máxima de produção de 300 bicicletas. Ainda, para atender à demanda 
existente, devem ser produzidos, no mínimo, 20 lotes de bicicletas infantis e 15 lotes de bicicletas 
de adultos. Formule o modelo de programação linear para minimizar o custo de produção da 
fábrica. 
 
RESOLUÇÃO: O primeiro passo para a construção de qualquer modelo consiste em identificar as 
variáveis de decisão para o problema. Neste caso, a variável de decisão deve ser xi, sendo x a 
quantidade de bicicletas do tipo “i” a ser produzida por dia. Logo, temos: 
• x1 = número de bicicletas infantis a serem produzidas por dia; 
• x2 = número de bicicletas infantis a serem produzidas por dia. 
 
Em seguida, passamos à definição da função objetivo. A fábrica tem como meta minimizar o seu 
custo de produção diário. Assim, como o custo unitário da produção da bicicleta infantil é de 
R$280,00, e da bicicleta de adulto é de R$620,00, temos a seguinte função objetivo: 
Min Z= 280x1+620x2 
A fábrica emprega 200 funcionários por dia. São necessários seis trabalhadores para fazer um 
lote de 8 bicicletas infantis por dia, logo, cada trabalhador produziria 0,75 bicicletas por dia. Três 
trabalhadores fabricam 5 bicicletas de adulto por dia, logo, cada trabalhador produziria 0,625 
bicicletas. Com esses dados, conseguimos definir a restrição da fábrica com relação à 
capacidade de mão de obra: 
0,75x1+0,6x2 ≤200 
A fábrica tem capacidade máxima de produção de 300 bicicletas. Logo, a restrição com relação à 
capacidade da fábrica é: 
x1+x2 ≤300 
Além disso, para atender à demanda existente devem ser produzidos, no mínimo, 20 lotes de 
bicicletas infantis. Como cada lote é composto por 8 bicicletas infantis, devem ser produzidas, ao 
menos, 160 bicicletas infantis. 
x1 ≥160 
Por sua vez, devem ser produzidos 15 lotes de bicicletas de adultos, com 5 bicicletas em cada 
um, de modo que: 
x2 ≥75 
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção 
estático é: 
Min Z= 280x1+620x2 
Sujeito a: 
0,75x1+0,6x2 ≤200 
x1+x2 ≤300 
x1 ≥160 
x2 ≥75 
Repare que, neste caso, não são necessárias as restrições de não negatividade das variáveis de 
decisão devido às restrições para o atendimento mínimo da demanda. 
 
Neste exemplo, resolvemos um problema de planejamento de produção estático. Contudo, em 
situações reais, é mais comum realizar o planejamento para diferentes períodos de tempo. 
Nesses casos, são necessários modelos dinâmicos, ou seja, que utilizam formulações do tipo 
multiperíodo. 
 
PROBLEMA DINÂMICO - Nos modelos de programação dinâmica, as disponibilidades de 
matéria-prima e de mão de obra, e até os lucros, podem variar ao longo do tempo. Também são 
considerados os níveis de estoque, visando sempre atender à demanda em todos os períodos, 
com o menor custo possível. 
A seguir, vamos desenvolver o modelo matemático para um problema de planejamento de 
produção dinâmico. 
 
TEORIA NA PRÁTICA - PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO DINÂMICO 
Uma fábrica de bicicletas está planejando seus níveis de produção para os próximos seis meses. 
A fábrica tem capacidade máxima de estocar 6.000 bicicletas. Os dados com relação à produção 
máxima mensal, ao custo unitário de produção e à demanda mensal são apresentados na tabela 
a seguir: 
Sabe-se que o 
estoque inicial 
do semestre é 
de 2.750 
unidades, e 
que o custo de estoque é equivalente a 1,5% do custo unitário de produção no mesmo mês. 
Desenvolva o modelo matemático para minimizar o custo total da fábrica no próximo semestre. 
RESOLUÇÃO: O primeiro passo para a modelagem deste exemplo de um clássico problema de 
planejamento de produção dinâmico é a definição das variáveis de decisão. As variáveis de 
decisão devem ser xi, sendo x o número de unidades de bicicletas a serem produzidas no mês “i”, 
e ei, sendo e o inventário inicial do mês “i”. Logo, temos: 
Mês 1 2 3 4 5 6 
Custo unitário de produção (R$) 240,00 250,00 265,00 285,00 280,00 260,00 
Demanda (unidades) 1.000 4.500 6.000 5.500 3.500 4.000 
Produção máxima (unidades) 4.000 3.500 4.000 4.500 4.000 3.500 
• xi = número de unidades a produzir no mês i, i=1 a 6 
• ei = inventário inicial mês i, i=1 a 6 
Comentário: Repare que pela primeira vez estamos modelando um problema em que o índice da 
variável de decisão se refere ao período de tempo, pois estamos analisando a situação ao longo 
do tempo. 
Conhecendo o custo unitário de produção e o custo de estoque de cada mês, conseguimos 
determinar a função objetivo para a minimização dos custos da fábrica: 
Min Z= 240x1+250x2+265x3+285x4+280x5+260x6 + 3,6(e1+e2)/2 + 3,75(e2+e3)/2 + 3,98(e3+e4)/2+ 
4,28(e4+e5)/2 + 4,20(e5+ e6)/2 + 3,9(e6+e7)/2 
 
Observe que o estoque inicial em dado mês equivale ao estoque final do mês anterior, e que 
estamos considerando o custo do estoque médio no mês. Assim, para o custo de estoque, 
consideramos que o nível de estoque é a média entre o valor de inventário inicial e final do mês. 
 
𝒆𝒎 =
𝒆𝒊 + 𝒆𝒊 + 𝟏
𝟐
 
 
A produção de unidades de bicicleta por mês deve ser, no mínimo, o suficiente para atender à 
demanda, porém não pode superar a produção máxima mensal. Logo, temos as seguintes 
restrições com relação aos níveis de produção. 
2.000≤x1 ≤ 4.000 } mês 1 
1.750 ≤ x2 ≤3.500 } mês 2 
2.000 ≤ x3 ≤4.000 } mês 3 
2.250 ≤ x4 ≤ 4.500 } mês 4 
2.000 ≤ x5 ≤4.000 } mês 5 
1.750 ≤ x6 ≤3.500 } mês 6 
Sabe-se também que a capacidade máxima de estoque na fábrica é de 6.000 unidades de 
bicicletas. Logo, o estoque final em cada mês não pode ser superior a essa capacidade máxima, 
de modo que esta restrição será do tipo ≤. 
Como o Estoque final = Estoque inicial + produção - unidades vendidas, temos: 
x1 + e1 - 1.000 < 6.000 } mês 1 
x2 + e2 - 4.500 < 6.000 } mês 2 
x3 + e3 - 6.000 < 6.000 } mês 3 
x4 + e4 - 5.500 < 6.000 } mês 4 
x5 + e5 - 3.500 < 6.000 } mês 5 
x6 + e6 - 4.000 < 6.000 } mês 6 
Ainda em relação ao estoque, é necessário o balanço do inventário, representado pelas seguintes 
restrições: 
e1 = 2750 
e2 = e1 + x1 – 1.000 
e3 = e2 + x2 - 4.500 
e4 = e3 + x3 - 6.000 
e5 = e4 + x4 - 5.500 
e6 = e5 + x5 - 3.500 
e7 = e6 + x6 - 4.000 
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção 
dinâmico é: 
Min Z= 240x1+250x2+265x3+285x4+280x5+260x6 + 3,6(e1+e)/2 + 3,75(e2+e3)/2 + 3,98(e3+e4)/2+ 
4,28(e4+e5)/2 + 4,20(e5+ e6)/2 + 3,9(e6+e7)/2 
Sujeito a: 
2.000≤x1 ≤ 4.000 } mês 1 
1.750 ≤ x2 ≤3.500 } mês 2 
2.000 ≤ x3 ≤4.000 } mês 3 
2.250 ≤ x4 ≤ 4.500 } mês 4 
2.000 ≤ x5 ≤4.000 } mês 5 
1.750 ≤ x6 ≤3.500 } mês 6 
x1 + e1 - 1.000 < 6.000 } mês 1 
x2 + e2 - 4.500 < 6.000 } mês 2 
x3 + e3 - 6.000 < 6.000 } mês 3 
x4 + e4 - 5.500 < 6.000 } mês 4 
x5 + e5 - 3.500 < 6.000 } mês 5 
x6 + e6 - 4.000 < 6.000 } mês 6 
e1 = 2750 
e2 = e1 + x1 – 1.000 
e3 = e2 + x2 - 4.500 
e4 = e3 + x3 - 6.000 
e5 = e4 + x4 - 5.500 
e6 = e5 + x5 - 3.500 
e7 = e6 + x6 - 4.000 
 
PROBLEMA FAZER X COMPRAR- As organizaçõesenfrentam, no seu dia a dia, o dilema de 
fazer ou comprar. 
“Ao se decidir entre a fabricação interna ou a aquisição de determinado componente no 
mercado, as empresas costumam realizar a análise econômica, ou seja, comparar os 
custos de fabricação ao custo de aquisição. 
DiSERIO; SAMPAIO, 2001 
 
De acordo com Slack et al. (1997), fornecedores externos podem se especializar na produção de 
certos componentes e produzi-los a custos menores e com melhor qualidade que a própria 
empresa. Assim sendo, as empresas devem decidir entre “fazer ou comprar” determinado 
componente. 
Modelos de programação linear podem ser utilizados para auxiliar no processo decisório em 
relação à terceirização, tal como podemos verificar no exemplo a seguir. 
 
TEORIA NA PRÁTICA - PROBLEMA FAZER X COMPRAR 
Uma fábrica de bicicletas acaba de receber um pedido de R$750.000,00. Foram encomendadas 
3.000 bicicletas do modelo 1, 2.000 do modelo 2 e 1.000 do modelo 3. 
São necessárias 2 horas para a montagem da bicicleta do modelo 1 e 1 hora para sua pintura. 
Para a bicicleta do modelo 2, leva-se 1,5 horas para a montagem e 2 horas para a pintura. Para a 
bicicleta do modelo 3, são necessárias 3 horas de montagem e 1 hora de pintura. A fábrica tem 
disponibilidade de 10.000 horas para montagem e 6.000 horas para pintura até a entrega da 
encomenda. 
Os custos para a fabricação das bicicletas são: R$350,00 para a bicicleta 1, R$400,00 para a 
bicicleta 2 e R$430,00 para a bicicleta 3. 
A fábrica teme não ter tempo hábil para produzir toda a encomenda e, por isso, cotou o custo de 
terceirizar a sua fabricação. O custo para comprar uma bicicleta do modelo 1 seria de R$460,00, 
de R$540,00 para a bicicleta do modelo 2 e de R$ 580,00 para a bicicleta do modelo 3. 
Desenvolva o modelo de programação linear para minimizar o custo de produção da encomenda 
de bicicletas. 
 
RESOLUÇÃO: A fábrica teme não ter tempo hábil para realizar a produção de bicicletas para a 
entrega e, por isso, precisa decidir entre fabricá-las ou comprá-las de outro fabricante. Assim, 
teremos dois tipos de variáveis de decisão na modelagem deste problema. 
• xi = quantidade de bicicleta do modelo i a ser fabricada internamente; 
• ci = quantidade de bicicleta do modelo i a ser comprada de concorrente. 
Logo, as variáveis de decisão para este exemplo são: 
• x1 = quantidade de bicicleta do modelo 1 a ser fabricada internamente; 
• x2 = quantidade de bicicletas do modelo 2 a ser fabricada internamente; 
• x3 = quantidade de bicicletas do modelo 3 a ser fabricada internamente; 
• c1 = quantidade de bicicletas do modelo 1 a ser comprada de concorrente; 
• c2 = quantidade de bicicletas do modelo 2 a ser comprada de concorrente; 
• c3 = quantidade de bicicletas do modelo 3 a ser comprada de concorrente. 
Conhecendo os custos de produção e de aquisição dos diferentes modelos de bicicletas, temos a 
seguinte função objetivo: 
Min Z= 350x1+400x2+430x3+ 460c1+540c2+580c3 
Foram encomendadas 3.000 bicicletas do modelo 1, 2.000 do modelo 2 e 1.000 do modelo 3, de 
modo que a restrição de demanda é representada pelas seguintes equações: 
x1 + c1 = 3.000 } demanda para o modelo 1 
x2 + c2 = 2.000 } demanda para o modelo 2 
x3 + c3 = 900 } demanda para o modelo 3 
A fábrica tem disponibilidade de 10.000 horas para montagem e 6.000 horas para pintura até a 
entrega da encomenda. Essas restrições são: 
2x1 + 1,5x2 + 3x3 ≤10.000 } montagem 
1x1 + 2x2 + 1x3 ≤ 5.000 } pintura 
Além disso, há a condição de não negatividade das variáveis de decisão: 
x1, x2, x3, c1, c2, c3 >= 0 
Enfim, temos que o modelo para este exemplo do problema de fazer x comprar é: 
Min Z= 350x1+400x2+430x3+ 460c1+540c2+580c3 
Sujeito a: 
x1 + c1 = 3.000 
x2 + c2 = 2.000 
x3 + c3 = 900 
2x1 + 1,5x2 + 3x3 ≤10.000 
x1 + 2x2 + x3 ≤ 5.000 
x1, x2, x3, c1, c2, c3 >= 0 
É importante ressaltar que a decisão sobre a terceirização é um pouco simplificada, pois focam-
se apenas os aspectos econômicos. Contudo, a terceirização de determinados produtos ou 
serviços deve incluir outras considerações além de questões econômicas, devendo, além disso, 
considerar aspectos estratégicos como competências essenciais e vantagens competitivas. Ao 
delegar certos serviços a terceiros (outsourcing), a empresa pode se concentrar em sua 
competência central, mantendo-se competitiva no mercado. 
 
VERIFICANDO O APRENDIZADO 
1. A fábrica XYZ produz rações para a alimentação de gado. As rações são elaboradas a partir da 
mistura de três diferentes tipos de grãos: grão 1, 2 e 3. Três nutrientes são considerados no 
produto final: o nutriente A, B e C. 
Sabe-se que o grão do tipo 1 custa R$35,00 por kg. Um quilo de grão 1 possui 30mg de nutriente 
A, 10mg de nutriente B e 43mg de nutriente C. O grão do tipo 2 custa R$23,00 por kg. Além 
disso, 1kg do grão 2 possui 28mg do nutriente A, 17mg do nutriente B e 40mg do nutriente C. O 
grão do tipo 3 possui apenas 70mg do nutriente tipo A, e 1kg deste tipo de grão custa R$78,00. 
A ração para gado deve conter, no mínimo, 1.250mg de nutriente A, 380mg do nutriente B e 
980mg do nutriente C. 
O analista deseja determinar a composição da ração que minimize os custos de produção, 
considerando que as necessidades mínimas dos nutrientes sejam atendidas. Logo, é possível 
afirmar que: 
a) As variáveis de decisão que devem ser usadas na modelagem são: xa a quantidade de 
nutrientes A, xb a quantidade de nutrientes B e xc a quantidade de nutrientes C. 
b) A função objetivo do modelo é Máx Z=30xa+28xb+70xc, sendo xa a quantidade de 
nutrientes A, xb a quantidade de nutrientes B e xc a quantidade de nutrientes C. 
c) O modelo possui apenas duas restrições que garantem o suprimento mínimo da 
quantidade de nutrientes. 
d) As variáveis de decisão do modelo não precisam atender à condição de não negatividade. 
e) A função objetivo do modelo é Min Z= 35x1+23x2+78x3, sendo x1 = quilos de grão tipo 1 
usado na produção de um quilo de ração, x2 = quilos de grão tipo 2 usado na produção de 
um quilo de ração, e x3 = quilos de grão tipo 3 usado na produção de um quilo de ração. 
 A alternativa "E" está correta. Como as rações são elaboradas a partir de três diferentes tipos de 
grãos, temos que as variáveis de decisão são: 
• x1 = quilos de grão tipo 1 usado na produção de um quilo de ração; 
• x2 = quilos de grão tipo 2 usado na produção de um quilo de ração; 
• x3 = quilos de grão tipo 3 usado na produção de um quilo de ração. 
Como se deseja minimizar o custo de produção, conhecendo o custo do quilo de cada tipo de 
grão, temos a seguinte função objetivo: 
Min Z= 35x1+23x2+78x3 
Logo, podemos afirmar que a resposta certa para o exercício é a alternativa E. Porém, vamos 
seguir na construção do modelo matemático para este problema. 
A ração deve conter, no mínimo, 1250mg de nutriente A, 380mg do nutriente B e 980mg do 
nutriente C. Assim, teremos três restrições com relação à quantidade dos diferentes tipos de 
nutrientes. São elas: 
30x1+28x2+70x3≥1250→Nutriente A 
10x1+17x2≥380→Nutriente B 
43x1+40x3≥980→Nutriente C 
Logo, temos que o modelo para este exercício é: 
Min Z= 35x1+23x2+78x3 
Sujeito a: 
30x1+28x2+70x3≥1250 
10x1+17x2≥380 
43x1+40x3≥980 
x1,x2,x3,x4≥0 
 
2. Uma fábrica de eletrodomésticos está planejando seus níveis de estoque para as próximas 
quatro semanas. A loja tem capacidade máxima de estoque de 100 geladeiras. Os dados com 
relação à produção máxima semanal, ao custo unitário de produção e à demanda semanal são 
apresentados na tabela a seguir. 
30x1+28x2+70x3≥1250 
10x1+17x2≥380 
43x1+40x3≥980 
x1,x2,x3,x4≥0 
Dados de produção 
de geladeiras. Fonte: 
Renata Albergaria de 
Mello Bandeira 
Sabe-se que o 
estoque inicial do mês é de 30 unidades e que o custo de estoque é equivalente a 2% do custo 
unitário de produção da semana. Ao desenvolver o modelo matemático para minimizar o custo 
total da fábrica no próximo mês, consideramos que as variáveis de decisão devem ser xi, sendo x 
o número de unidades de geladeiras a serem produzidas na semana“i”, e ei, sendo e o inventário 
inicial da semana “i”. Assim, a(s) restrição(ões) referente(s) ao estoque na semana 3 é(são) 
representada(s) pela(s) seguinte(s) equação(ões): 
a) x3 + e3 - 65 < 100 
b) e3 = e2 + x2 – 50 
c) e4 = e3 + x3 – 65 
d) x3 + e3 - 65 < 100 e e3 = e2 + x2 – 50 
e) x3 + e3 - 65 < 100, e3 = e2 + x2 – 50 e e4 = e3 + x3 – 65 
 A alternativa "E" está correta. As variáveis de decisão são: 
• xi = número de unidades a produzir na semana i, i=1 a 4 
• ei = inventário inicial na semana i, i=1 a 4 
Conhecendo o custo unitário de produção e o custo de estoque de cada mês, conseguimos 
determinar a função objetivo para a minimização dos custos da fábrica, considerando o custo do 
estoque médio da semana(𝑒𝑠 =
𝑒𝑖+𝑒𝑖+1
2
): 
Mês 1 2 3 4 
Custo unitário de produção (R$) 1.240,00 1.300,00 1.265,00 1.285,00 
Demanda (unidades) 60 50 65 70 
Produção máxima (unidades) 100 100 100 100 
Min Z= 1.240x1+1.300x2+1.265x3+1.285x4+24,8(e1+e2)/2+26(e2+e3)/2+25,3(e3+e4)/2+ 
25,7(e4+e5)/2 
A produção de unidades de geladeira por semana deve ser, no mínimo, o suficiente para atender 
à demanda, porém não pode superar a produção máxima semanal. Logo, temos as seguintes 
restrições com relação aos níveis de produção: 
60≤x1 ≤ 100 } semana 1 
50 ≤ x2 ≤100 } semana 2 
65 ≤ x3 ≤100 } semana 3 
70 ≤ x4 ≤ 100 } semana 4 
Sabe-se também que a capacidade máxima de estoque na fábrica é de 100 geladeiras. Logo, o 
estoque final em cada semana não pode ser superior a tal capacidade máxima, de modo que esta 
restrição será do tipo ≤. Como o Estoque final = Estoque inicial + produção - unidades vendidas, 
temos: 
x1 + e1 - 60 < 100 } semana 1 
x2 + e2 - 50 < 100 } semana 2 
x3 + e3 - 65 < 100 } semana 3 
x4 + e4 - 70 < 100 } semana 4 
Ainda em relação ao estoque, é necessário o balanço do inventário, que é representado pelas 
seguintes restrições: 
e1 = 30 
e2 = e1 + x1 – 60 
e3 = e2 + x2 - 50 
e4 = e3 + x3 - 65 
e5 = e4 + x4 - 70 
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção 
dinâmico é: 
Min Z= 1.240x1+1.300x2+1.265x3+1.285x4+24,8(e1+e2)/2+26(e2+e3)/2+25,3(e3+e4)/2+ 
25,7(e4+e5)/2 
Sujeito a: 
60≤x1 ≤ 100 } semana 1 
50 ≤ x2 ≤100 } semana 2 
65 ≤ x3 ≤100 } semana 3 
70 ≤ x4 ≤ 100 } semana 4 
x1 + e1 - 60 < 100 } semana 1 
x2 + e2 - 50 < 100 } semana 2 
x3 + e3 - 65 < 100 } semana 3 
x4 + e4 - 70 < 100 } semana 4 
e1 = 30 
e2 = e1 + x1 – 60 
e3 = e2 + x2 - 50 
e4 = e3 + x3 - 65 
e5 = e4 + x4 - 70 
Logo, as equações que representam as restrições referentes ao estoque na semana 3 são: 
x3 + e3 - 65 < 100 } semana 3 
e3 = e2 + x2 - 50 
e4 = e3 + x3 – 65 
 
 
MÓDULO 2 - Aplicar a técnica de modelagem nos problemas de transporte e transbordo 
PROBLEMAS DE TRANSPORTE - O problema de transportes é a aplicação de programação 
linear mais frequente na logística. 
Esse padrão de problema envolve decisões como o volume a ser transportado entre localidades, 
podendo envolver ou não decisões referentes ao desenho da cadeia e também problemas de 
localização. 
O problema de programação linear para o problema clássico de transportes consiste em definir o 
melhor caminho (ou rota) para fazer com que determinada quantidade de produtos de um ponto 
de suprimento chegue a um ponto de demanda. O objetivo pode ser minimizar as distâncias 
percorridas, o custo de transporte ou até mesmo maximizar os níveis de serviço ou o lucro com 
vendas. 
O problema de transporte é um modelo fluxo em grafo bipartido, de modo que não existem nós 
intermediários de transbordo ou transição para fluxo, conforme ilustrado. 
 
Atenção! Na rede de transportes, os nós 
representam os pontos de suprimento e de 
demanda, enquanto os arcos representam a 
conexão entre os nós. 
 
Conforme pode ser observado, no problema de 
transportes, há m pontos de suprimento, cada um 
com capacidade de oferta máxima designada 
por Si, onde o índice i representa o ponto de 
suprimento em questão (i = 1,…, m). Existem ainda n pontos de demanda a serem abastecidos 
por estes pontos de suprimento. Cada ponto de demanda recebe pelo menos Dj unidades do 
produto a ser transportado, sendo que o índice j representa os pontos de demanda, tal que j = 1, 
…, n. Para cada unidade do ponto de fornecimento i remetida ao ponto de demanda j incorre um 
custo cij, que é o custo de fornecer o produto ao ponto de demanda j a partir do ponto de 
suprimento i. 
Assim sendo, para modelar o problema de transportes, consideramos a variável de decisão xij, 
que representa o número de unidades do produto específico despachadas do ponto de 
suprimento i para o ponto de demanda j. Considerando que a função objetivo seja minimizar o 
custo total de transporte, temos que a função objetivo é: 
 
𝑀𝑖𝑛 ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=𝑗
 
 
As condições de transporte estão sujeitas a restrições de fornecimento e de demanda. Logo, o 
total transportado para o ponto de demanda tem que, ao menos, atender à quantidade mínima 
demandada, enquanto o total transportado a partir do ponto de suprimento não pode ser superior 
à sua capacidade de oferta. Logo, as restrições para o problema clássico de transportes podem 
ser representadas pelas seguintes equações: 
 
∑ 𝑥𝑖𝑗 ≤
𝑛
𝑗=1
𝑆𝑖(𝑖 = 1, … , 𝑚) 
 
∑ 𝑥𝑖𝑗 ≥
𝑚𝑛
𝑖=1
𝑑𝑖(𝑗 = 1, … , 𝑛) 
 
 
Em suma, o modelo matemático para o problema clássico de transporte é: 
 
𝑀𝑖𝑛 ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=1
 
 
 
Sujeito a: 
 
∑ 𝑥𝑖𝑗 ≤
𝑛
𝑗=1
𝑆𝑖(𝑖 = 1, … , 𝑚) 
 
∑ 𝑥𝑖𝑗 ≥
𝑚
𝑖=1
𝑑𝑖(𝑗 = 1, … , 𝑛) 
 
𝒙𝒊𝒋 ≥ 𝟎 ∀𝒊, 𝒋 
 
Para facilitar o entendimento do modelo matemático para o problema clássico de transportes, 
vamos resolver o exemplo a seguir: 
TEORIA NA PRÁTICA - PROBLEMA 
DE TRANSPORTE 
Uma empresa fabricante de bicicletas 
conta com duas plantas, uma 
localizada em São Paulo e outra em 
Recife. A empresa atende ao público 
por meio de três revendedores, 
localizados em Porto Alegre, Brasília e Manaus. 
 
Formule o problema de programação linear que 
minimize os custos de distribuição da empresa. 
RESOLUÇÃO - Consideramos que i=1 para São 
Paulo e i=2 para Recife, enquanto j=1 para Porto 
Alegre, j=2 para Brasília e j=3 para Manaus. 
 Logo, as variáveis de decisão são: 
x11= quantidade de produtos transportados 
de São Paulo para Porto Alegre; 
x12= quantidade de produtos transportados de São Paulo para Brasília; 
x13= quantidade de produtos transportados de São Paulo para Manaus; 
x21= quantidade de produtos transportados de Recife para Porto Alegre; 
x22= quantidade de produtos transportados de Recife para Brasília; 
x23= quantidade de produtos transportados de Recife para Manaus. 
 
A função objetivo para minimizar o custo total de transporte é: 
Minz Z=25X11+30X12+70X13+60X21+35X22+50X23 
O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à 
demanda mínima da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 
300 bicicletas, respectivamente. Assim, as restrições referentes à demanda são: 
X11+X21 ≥450 à restrição quanto → demanda para Porto Alegre; 
X12+X22 ≥500à restrição quanto → demanda para Brasília; 
X13+X23 ≥300à restrição quanto → demanda para Manaus. 
O total transportado de São Paulo não pode ser superior a 600 unidades, pois trata-se da 
capacidade máxima de oferta da planta. Já o total transportado de Recife deve ser inferior a 700 
unidades, que é a capacidade máxima de oferta desta planta. Assim, as restrições referentes à 
oferta são: 
X11+X12+X13+≤600à restrição quanto ao suprimento de São Paulo; 
X21+X22+X23≤700à restrição quanto ao suprimento de Recife. 
O modelo matemático deste problema é: 
Minz Z=25X11+30X12+70X13+60X21+35X22+50X23 
Sujeito a: 
Plantas Custos de envio por unidade Ofertas 
Mercados 
Porto Alegre Brasília Manaus 
SP 25 30 70 600 
Recife 60 35 50 700 
Demandas 450 500 300 
X11+X21 ≥450 
X12+X22 ≥500 
X13+X23 ≥300 
X11+X12+X13≤600 
X21+X22+X23≤700 
X11, X12, X13, X21, X22, X23≥0 
 
Saiba mais: Os problemasde transporte são casos particulares de problemas de programação 
linear, de modo que sua resolução algébrica pode ser desenvolvida por algoritmos de 
programação linear. Entretanto, é possível aproveitar as particularidades do problema de 
transporte para resolvê-lo de forma mais eficiente que o caso geral do simplex. Assim, existem 
algoritmos específicos para a solução do problema de transporte, como o Método do Canto 
Noroeste e o Método de Vogel, porém não vamos abordá-los aqui. Caso você tenha interesse em 
aprofundar os seus conhecimentos, recomenda-se a leitura do capítulo 7 de Winston (2004). 
 
PROBLEMA DE TRANSBORDO - O problema de transbordo segue lógica semelhante ao 
problema de transportes, porém este não é um modelo fluxo em grafo bipartido, pois existem 
nós intermediários de transbordo ou de transição para fluxo, conforme ilustrado na figura a 
seguir: 
 
Além de um conjunto de m nós, que representam os 
pontos de suprimentos, e n nós, que representam os 
pontos de demanda, a rede também dispõe de l pontos 
de transbordo. 
É importante que você saiba bem a diferença entre 
estes diferentes tipos de nó: 
PONTOS DE SUPRIMENTO: São responsáveis pelo fornecimento de insumos, de modo que 
podem remetê-los para outros pontos, porém não podem recebê-los. 
PONTOS DE DEMANDA: São os pontos de consumo, de modo que devem receber insumos de 
outros pontos, porém não podem recebê-los. 
PONTOS DE TRANSBORDO: Podem tanto receber insumos de outros pontos quanto remeter 
insumos para outros pontos, ou seja, são locais onde é possível realizar a transferência da carga. 
Um centro de distribuição, por exemplo, pode funcionar como um ponto de transbordo em uma 
cadeia logística, recebendo insumos de diversas plantas ou diversos fornecedores, realizando a 
consolidação da carga e remetendo insumos para outras plantas, outros centros de distribuição 
ou clientes. Um depósito também é um bom exemplo de um ponto de transbordo. 
 
Uma particularidade do problema de transbordo é que aquilo que é transportado das unidades 
intermediárias (de transbordo) aos mercados consumidores não deve ultrapassar a quantidade de 
produto que chega a tais pontos. 
A quantidade que insumos que chega a um ponto de transbordo deve ser igual à quantidade de 
insumos que sai dele. 
Com essa restrição, garantimos o equilíbrio do fluxo neste nó, ou seja, o fluxo que entra deve ser 
igual a todo o fluxo que sai. Portanto, o modelo matemático para o problema de transbordo é 
semelhante ao do problema clássico de transporte, porém acrescenta-se a restrição de equilíbrio 
nos nós que representam pontos de transbordo. 
 
 
Temos que o modelo matemático para o problema de transbordo é: 
𝑀𝑖𝑛 ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗
𝑛
𝑗=1
𝑚
𝑖=1
 
Sujeito a: 
 
∑ 𝑥𝑖𝑗 ≤
𝑛
𝑗=1
𝑆𝑖(𝑖 = 1, … , 𝑚) 
 
∑ 𝑥𝑖𝑗 ≥
𝑚
𝑖=1
𝑑𝑖(𝑗 = 1, … , 𝑛) 
∑ 𝑥𝑖𝑘 = ∑ 𝑥𝑘𝑗(𝑘 = 1, … , 𝑙) → 𝐸𝑞𝑢𝑙í𝑏𝑟𝑖𝑜 𝑛𝑜𝑠 𝑛ó𝑠 𝑑𝑒 𝑡𝑟𝑎𝑛𝑠𝑏𝑜𝑟𝑑𝑜 𝑇
𝑛
𝑗=1
𝑚
𝑖=1
 
 
𝒙𝒊𝒋 ≥ 𝟎 ∀𝒊, 𝒋 
 
 
Para facilitar o entendimento do modelo matemático para o problema clássico de transbordo, 
vamos resolver o exemplo a seguir: 
 
TEORIA NA PRÁTICA - PROBLEMA DE 
TRANSBORDO 
Uma empresa fabricante de bicicletas conta com 
duas plantas, uma localizada em São Paulo e 
outra em Recife, e atende o público por meio de 
dois revendedores, localizados em Porto Alegre e 
Manaus. A empresa também dispõe de um centro 
de distribuição, localizado em Brasília, que pode 
ser usado como ponto de transbordo caso contribua para reduzir o custo total de transporte. 
 
RESOLUÇÃO: Consideramos que i=1 
para São Paulo, i=2 para Recife e i=3 
para Brasília, enquanto j=1 para Porto 
Alegre, j=2 para Manaus e j=3 para 
Brasília. Logo, as variáveis de decisão 
são: 
x11= quantidade de produtos 
transportados de São Paulo para Porto 
Alegre; 
x12= quantidade de produtos transportados de São Paulo para Manaus; 
x13= quantidade de produtos transportados de São Paulo para Brasília; 
x21= quantidade de produtos transportados de Recife para Porto Alegre; 
x22= quantidade de produtos transportados de Recife para Manaus; 
x23= quantidade de produtos transportados de Recife para Brasília; 
x31= quantidade de produtos transportados de Brasília para Porto Alegre; 
x32= quantidade de produtos transportados de Brasília para Manaus. 
 
A função objetivo para minimizar o custo total de transporte é: 
Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32 
O total transportado para Porto Alegre tem que ser, ao menos, igual a 450, para atender à 
demanda mínima da cidade. Para Brasília e Manaus, devem ser transportadas, no mínimo, 500 e 
300 bicicletas, respectivamente. Assim, as restrições referentes à demanda são: 
X11+X21 +X31≥450 → restrição quanto à demanda para Porto Alegre; 
X12+X22 +X32≥500 → restrição quanto à demanda para Manaus. 
O total transportado de São Paulo não pode ser superior a 600 unidades, pois esta é a 
capacidade máxima de oferta da planta. Já o total transportado de Recife deve ser inferior a 700 
Plantas/CD Custos de envio por unidade Ofertas 
Mercados/CD 
Porto Alegre Manaus Brasília 
SP 25 70 30 600 
Recife 60 50 35 700 
Brasília 45 65 0 
Demandas 450 500 
unidades, que é a capacidade máxima de oferta desta planta. Assim, as restrições referentes à 
oferta são: 
X11+X12+X13+≤600 → restrição quanto ao suprimento de São Paulo; 
X21+X22+X23≤700 → restrição quanto ao suprimento de Recife. 
Lembre-se ainda da restrição de equilíbrio nos nós que representam pontos de transbordo. Tudo 
o que chega no centro de distribuição de Brasília deve ser igual ao que sai de Brasília, conforme 
indicado na equação a seguir: 
X11+ X23+=X31+X32 
O modelo matemático deste problema é: 
Min Z=25X11+70X12+30X13+60X21+50X22+35X23+45X31+65X32 
Sujeito a: 
X11+X21 +X31≥450 
X12+X22 +X32≥500 
X11+X12+X13+≤600 
X21+X22+X23≤700 
X11+ X23+=X31+X32 
X11, X12 , X13, X21, X22, X23, X31,X32 ≥0 
 
PROBLEMA DE TRANSPORTE E TRANSBORDO- A seguir, o especialista apresenta os 
problemas de transporte e de transbordo, abordando as particularidades deste tipo de problema 
de programação linear e a importância de sua aplicação no ambiente gerencial. 
 
VERIFICANDO O APRENDIZADO 
1. Uma fábrica de bebidas tem três depósitos (O1, O2 e O3) na cidade do Rio de Janeiro que 
suprem duas lojas (D1 e D2). As distâncias, bem como as quantidades ofertadas de cada 
depósito e a demanda de cada loja, são apresentadas na tabela a seguir: 
A fábrica deseja planejar sua distribuição de modo a minimizar 
a distância total de transporte. Assim, em relação ao modelo 
matemático que representa este problema, é possível afirmar 
que: 
a) Deve possuir três variáveis de decisão. 
b) Possui três inequações que representam as restrições 
com relação à demanda a ser atendida. 
c) Possui duas inequações que representam as restrições 
com relação à capacidade de suprimento. 
d) As restrições quanto à demanda devem ser do tipo ≤. 
e) As restrições quanto à capacidade de suprimento devem ser do tipo ≤. 
 A alternativa "E" está correta. As variáveis de decisão a serem adotadas neste modelo 
matemático são: 
X11= quantidade de produtos transportados de O1 para D1; 
X12= quantidade de produtos transportados de O1 para D2; 
X21= quantidade de produtos transportados de O2 para D1; 
X22= quantidade de produtos transportados de O2 para D2; 
X31= quantidade de produtos transportados de O3 para D1; 
X32= quantidade de produtos transportados de O3 para D2. 
Logo, o modelo matemático deste problema é: 
Minz Z=15X11+35X12+43X21+27X22+6X31+38X32 
Sujeito a: 
X11+X21 +X31 ≥150 
X12+X22 +X321 ≥200 
X21+X22 ≤90 
X11+X12≤60 [As restrições de capacidade são do tipo ≤.] 
X31+X32 ≤200 
X11, X12, X21, X22, X31, X32≥0 
 
Depósitos Distância Ofertas 
Mercados 
D1 D2 
O1 15 35 60 
O2 43 27 90 
O3 6 38 200 
Demandas 150 200 
2. Uma empresa de bebidas tem três fábricas (O1, O2 e O3) e um centro de distribuição (C1) na 
cidade do Rio de Janeiro que suprem duas lojas (D1 e D2). As distâncias,bem como as 
quantidades ofertadas de cada depósito e a demanda de cada loja, são apresentadas na tabela a 
seguir: 
A fábrica deseja 
planejar sua 
distribuição de 
modo a minimizar 
a distância total de 
transporte. Para 
desenvolver o 
modelo 
matemático que 
representa este 
problema, consideramos a variável de decisão xij, que representa o número de unidades do 
produto específico despachadas do ponto de suprimento ou do centro de distribuição i para o 
ponto de demanda ou centro de distribuição j. Assim, é possível afirmar que: 
a) Deve possuir 3 variáveis de decisão. 
b) Deve possuir 6 variáveis de decisão. 
c) Deve possuir 8 variáveis de decisão. 
d) Deve possuir 11 variáveis de decisão. 
e) Deve possuir 12 variáveis de decisão. 
 A alternativa "D" está correta. As variáveis de decisão a serem adotadas neste modelo 
matemático são: 
X11= quantidade de produtos transportados de O1 para D1; 
X12= quantidade de produtos transportados de O1 para D2; 
X13= quantidade de produtos transportados de O1 para C1; 
X21= quantidade de produtos transportados de O2 para D1; 
X22= quantidade de produtos transportados de O2 para D2; 
X23= quantidade de produtos transportados de O2 para C1; 
X31= quantidade de produtos transportados de O3 para D1; 
X32= quantidade de produtos transportados de O3 para D2; 
X33= quantidade de produtos transportados de O3 para C1; 
X41= quantidade de produtos transportados de C1 para D1; 
X42= quantidade de produtos transportados de C1 para D2. 
Assim, temos 11 variáveis de decisão e a função objetivo para o modelo deste problema é: 
Minz Z=15X11+35X12+11X13 +43X21+27X22+21X23+6X31+38X32+15X33+10X41+20X42 
 
 
MÓDULO 3 - Aplicar a técnica de modelagem em problemas de alocação 
PROBLEMAS DE ALOCAÇÃO - No problema de alocação, também denominado problema de 
designação ou de matching, existem dois conjuntos e devem ser formados pares entre os 
elementos destes dois conjuntos. 
O problema consiste em determinar a formação destes pares, ou seja, a combinação destes 
elementos de modo a minimizar o custo total de todas as alocações, respeitando as restrições 
existentes. 
Atenção! O problema da alocação visa designar tarefas a designados, podendo ser pessoas, 
máquinas, veículos ou até mesmo fábricas. Neste tipo de problema, há um custo associado para 
o designado desempenhar cada tarefa. Assim, o objetivo final é determinar a combinação de 
alocações que minimiza o custo total. 
Também pode ser considerado que cada designado i tem determinado interesse em efetuar cada 
tarefa j, dado por pij. Logo, o objetivo é realizar a alocação de maneira que a soma dos interesses 
seja maximizada. 
Atenção! Destaca-se que, no problema de alocação, o número de designados e de tarefas 
devem ser iguais. Assim, temos n designados e n tarefas. Cada tarefa deve ser atribuída a 
Fábricas e Centro de Distribuição Distância Ofertas 
 Mercados e Centro de Distribuição 
 D1 D2 C1 60 
 01 15 35 11 90 
 02 43 27 21 200 
 03 6 38 15 
 C1 10 20 - 
 Demandas 150 200 
apenas um designado, que também só deve realizar uma única tarefa. Além disso, todas as 
tarefas devem ser executadas. 
O problema da alocação pode ser considerado um caso especial do modelo de transportes, no 
qual cada origem tem uma unidade disponível e cada destino requer também uma unidade. 
Assim, o problema de alocação é um problema de transporte balanceado, no qual todas as 
demandas e capacidades são iguais a 1. Desse modo, o problema de alocação utiliza variáveis 
binárias. A variável binária, ou booleana, pode assumir apenas dois valores, zero ou 1. No 
problema de alocação, a variável de decisão xij recebe o valor igual a “1” se decidirmos que a 
tarefa “i” será alocada para o designado “j”, sendo “0” se decidirmos o contrário. De tal forma, 
temos que o modelo matemático para o problema da alocação é: 
 
𝑀𝑖𝑛𝑍 = ∑ ∑ 𝑐𝑖𝑗𝑥𝑖𝑗
𝑗𝑖
 
 
Sujeito a: 
 
∑ 𝑥𝑖𝑗 = 1 (𝑖 = 1, … , 𝑛)
𝑗
→ cada designado é alocado a uma só tarefa. 
∑ 𝑥𝑖𝑗 = 1 (𝑗 = 1, … , 𝑛) → cada tarefa é alocada a apenas um trabalhador.
𝑖
 
𝑥𝑖𝑗𝜀{0,1}, (𝑖 = 1, … , 𝑛; 𝑗 = 1, … , 𝑛) 
 
𝑥𝑖𝑗 = 1, 𝑠𝑒 𝑜 𝑑𝑒𝑠𝑖𝑔𝑛𝑎𝑑𝑜 𝑖 𝑓𝑜𝑟 𝑎𝑙𝑜𝑐𝑎𝑑𝑜 𝑝𝑎𝑟𝑎 𝑟𝑒𝑎𝑙𝑖𝑧𝑎𝑟 𝑎 𝑡𝑎𝑟𝑒𝑓𝑎 𝑗. 
 
𝑥𝑖𝑗 = 0, 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 
 
Saiba mais: Os modelos de alocação podem ser adotados para auxiliar no processo de tomada 
de decisão em diversas situações reais, tal como na determinação da escala de vendedores para 
pontos de venda, na distribuição de atividades para membros de uma equipe ou na alocação de 
máquinas para resolver diferentes tarefas. 
Para facilitar o entendimento do modelo matemático para o problema clássico de alocação, 
vamos resolver o exemplo a seguir: 
 
TEORIA NA PRÁTICA: A supervisora de uma equipe de limpeza em um hotel necessita formar 
equipes de camareiras para realizar a limpeza dos quartos na hora de troca de hóspedes. Os 
hóspedes que estão realizando check-out precisam sair do quarto até às 12h, enquanto os novos 
hóspedes podem realizar o check-in a partir de 14h. Assim, as esquipes têm pouco tempo para 
organizar e limpar todos os cômodos. Logo, a supervisora precisa organizar as equipes de modo 
que os serviços sejam realizados o mais rápido possível. 
A supervisora precisa formar a equipe para cuidar dos quartos do terceiro andar do hotel. As 
tarefas a serem realizadas são: arrumar as camas, limpar o banheiro, varrer o quarto e tirar o pó. 
As camareiras desempenham as tarefas, por quarto, nos seguintes tempos: 
Formule o problema de 
programação linear que 
minimize o tempo de 
arrumação do quarto. 
RESOLUÇÃO: Neste 
problema de alocação, a 
variável de decisão xij recebe o 
valor igual a “1” se decidirmos que a tarefa “i” será alocada para o designado “j”, sendo “0” se 
decidirmos o contrário. De tal forma, temos: 
x11= 1, se Lara arruma a cama; zero, caso contrário; 
Camareira Tarefa 
Arrumar cama Limpar banheiro Varrer quarto Tirar o pó 
Lara 2 min 5 min 7 min 3 min 
Ana 3 min 6 min 8 min 4 min 
Julia 4 min 4 min 6 min 5 min 
Talita 2 min 5 min 7 min 2 min 
x12= 1, se Lara limpa banheiro; zero, caso contrário; 
x13 =1, se Lara varre o quarto; zero, caso contrário; 
x14=1, se Lara tira o pó; zero, caso contrário; 
x21= 1, se Ana arruma a cama; zero, caso contrário; 
x22= 1, se Ana limpa banheiro; zero, caso contrário; 
x23= 1, se Ana varre o quarto; zero, caso contrário; 
x24= 1, se Ana tira o pó; zero, caso contrário; 
x31= 1, se Julia arruma a cama; zero, caso contrário; 
x32= 1, se Julia limpa banheiro; zero, caso contrário; 
x33= 1, se Julia varre o quarto; zero, caso contrário; 
x34= 1, se Julia tira o pó; zero, caso contrário; 
x41= 1, se Talita arruma a cama; zero, caso contrário; 
x42= 1, se Talita limpa banheiro; zero, caso contrário; 
x43= 1, se Talita varre o quarto; zero, caso contrário; 
x44= 1, se Talita tira o pó; zero, caso contrário. 
 
O modelo matemático para o problema da alocação é: 
Min Z= 
2X11+5X12+7X13+3X14+3X21+6X22+8X23+4X24+4X31+4X32+6X33+5X34+2X41+5X42+7X43+2X44 
Sujeito a: 
X11+X12+X13+X14=1 
X21+X22+X23+X24=1 
X31+X32+X33+X34=1 Cada trabalhador desempenha apenas uma tarefa. 
X41+X42+X43+X44=1 
X11+X21+X31+X41=1 
X13+X23+X33+X43=1 
X12+X22+X32+X42=1 Cada tarefa é alocada para apenas um trabalhador. 
X14+X24+X34+X44=1 
 
 
X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44 ꞓ {0,1} 
 
Saiba mais: Assim como o problema de transportes, o problema da alocação também é um caso 
particular de problemas de programação linear, de modo que sua resolução algébrica pode ser 
desenvolvida por algoritmos de programação linear. Porém, tal como o problema de transportes, 
possui particularidades específicas que podem ser aproveitadas para resolvê-lo de forma mais 
eficiente. Assim como para a solução do problema de transporte, com o Método do Canto 
Noroeste e o Método de Vogel, também existem algoritmos específicos para a solução do 
problema de alocação, a exemplo do algoritmohúngaro. Porém, não vamos abordá-los aqui. 
Caso você tenha interesse em aprofundar os seus conhecimentos, recomenda-se a leitura do 
capítulo 7 de Winston (2004). 
EXEMPLO DE PROBLEMA DE ALOCAÇÃO - No vídeo a seguir, o especialista apresenta um 
problema de alocação e desenvolve a resolução detalhadamente, até a obtenção do resultado 
final. 
 
VERIFICANDO O APRENDIZADO 
1. Um treinador necessita formar um time de nadadores para competir em uma prova olímpica de 
400 metros medley. Os nadadores apresentam as seguintes médias de tempo em cada estilo: 
O treinador deseja designar os nadadores para os 
diferentes estilos, a fim de obter o menor tempo 
possível para completar o medley. Sobre o modelo 
matemático que representa este problema, é possível 
afirmar que: 
a) As variáveis de decisão que devem ser usadas 
na modelagem são: x1 que representa o nadador 
Nadador Tempo (s) / 100m 
Livre Peito Golfinho Costas 
1 54 54 51 53 
2 51 57 52 52 
3 50 53 54 56 
4 56 54 55 53 
alocado ao nado livre, x2 que representa o nadador designado para o peito, x3 que 
representa o nadador alocado para o golfinho, e x4 que indica o nadador alocado para o 
estilo de costas. 
b) As variáveis de decisão que devem ser usadas na modelagem são: x1 que representa o 
estilo designado para o nadador 1, x2 que representa o estilo designado para o nadador 2, 
x3 que representa estilo designado para o nadador 3, e x4 que indica o estilo alocado para 
o nadador 4. 
c) As variáveis de decisão usadas no modelo devem ser inteiras, porém não precisam ser 
binárias. 
d) O modelo matemático possui 16 variáveis de decisão, que são variáveis binárias. 
e) Não é possível tratar este problema como um problema de alocação, pois o número de 
tarefas (estilos) a serem alocadas é igual ao número de designados (nadadores). 
A alternativa "D" está correta. Neste problema de alocação, a variável de decisão xij recebe valor 
igual a “1” se decidirmos que o estilo “i” será alocado ao designado “j”, sendo “0” se decidirmos o 
contrário. De tal forma, temos: 
X11= 1, se o nado livre é alocado ao nadador 1; zero, caso contrário; 
X12= 1, se o estilo de peito é alocado ao nadador 1; zero, caso contrário; 
X13 =1, se o estilo de golfinho é alocado ao nadador 1; zero, caso contrário; 
X14=1, se o estilo de costas é alocado ao nadador 1; zero, caso contrário; 
X21= 1, se o nado livre é alocado ao nadador 2; zero, caso contrário; 
X22= 1, se o estilo de peito é alocado ao nadador 2; zero, caso contrário; 
X23= 1, se o estilo de golfinho é alocado ao nadador 2; zero, caso contrário; 
X24= 1, se o estilo de costas é alocado ao nadador 2; zero, caso contrário; 
X31= 1, se o nado livre é alocado ao nadador 3; zero, caso contrário; 
X32= 1, se o estilo de peito é alocado ao nadador 3; zero, caso contrário; 
.X33= 1, se o estilo de golfinho é alocado ao nadador 3; zero, caso contrário; 
X34= 1, se o estilo de costas é alocado ao nadador 3; zero, caso contrário; 
X41= 1, se o nado livre é alocado ao nadador 4; zero, caso contrário; 
X42= 1, se o estilo de peito é alocado ao nadador 4; zero, caso contrário; 
X43= 1, se o estilo de golfinho é alocado ao nadador 4; zero, caso contrário; 
X44= 1, se o estilo de costas é alocado ao nadador 4; zero, caso contrário. 
Logo, temos 16 variáveis de decisão binárias, o que faz com que a alternativa D seja a resposta 
correta. 
O modelo matemático para este problema da alocação é: 
Min Z= 
54X11+54X12+51X13+53X14+51X21+57X22+52X23+52X24+50X31+53X32+54X33+56X34+56X41+54X42+
55X43+53X44 
Sujeito a: 
X11+X12+X13+X14=1 
X21+X22+X23+X24=1 Cada nadador desempenha apenas um estilo. 
X31+X32+X33+X34=1 
X41+X42+X43+X44=1 
 
X11+X21+X31+X41=1 
X13+X23+X33+X43=1 Cada estilo é alocado para apenas um nadador. 
X12+X22+X32+X42=1 
X14+X24+X34+X44=1 
 
X11, X12, X13, X14, X21, X22, X23, X24, X31, X32, X33, X34, X41, X42, X43, X44 ꞓ {0,1} 
 
 
 
 
 
2. Um treinador necessita formar um time de nadadores para competir em uma prova olímpica de 
400 metros medley. Os nadadores apresentam as seguintes médias de tempo em cada estilo: 
O treinador deseja designar os nadadores para os 
diferentes estilos, a fim de obter o menor tempo 
possível para completar o medley. Considere que a 
variável de decisão do modelo matemático para este 
problema seja xij, que recebe o valor igual a “1” se 
decidirmos que o estilo “i” será alocado ao designado 
“j”, sendo “0” se decidirmos o contrário. Logo, é 
possível afirmar que: 
a) A equação X11+X12+X13+X14=1 restringe que o estilo 1 será desempenhado por apenas um 
nadador. 
b) A equação X11+X12+X13+X14=1 restringe que o nadador 1 desempenha apenas um estilo. 
c) A equação X11+X12+X13+X14=1 restringe que o estilo 1 pode ser desempenhado por todos 
os nadadores. 
d) A equação X11+X21+X31+X41=1 restringe que o nadador 1 pode desempenhar todos os 
estilos. 
e) A equação X11+X21+X31+X41=1 não é uma restrição do modelo. 
 A alternativa "D" está correta. A equação X11+X12+X13+X14=1 restringe que o estilo 1 será 
desempenhado por apenas um nadador, pois determina que apenas uma das variáveis X11, X12, 
X13 e X14 pode receber o valor 1. As demais passam a ser zero, para que a soma seja igual a 1. 
Avalie este módulo: 
 
 
 
Nadador Tempo (s) / 100m 
Livre Peito Golfinho Costas 
1 54 54 51 53 
2 51 57 52 52 
3 50 53 54 56 
4 56 54 55 53