AULA 2 - Aplicações da Programação Linear (17pág)

Prévia do material em texto

APLICAÇÕES DA PROGRAMAÇÃ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. 
 
PREPARAÇÃO 
Tenha em mãos uma calculadora ou um software editor de planilhas eletrônicas para que possa realizar as operações 
matemáticas necessárias. 
 
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! 
 
APRESENTAÇÃO DO TEMA 
No vídeo a seguir, o especialista apresenta o tema programação linear como ferramenta de gestão (Crédito Digital), 
reforçando a importância da modelagem e apresentando alguns problemas clássicos que podem ser solucionados pela 
programação linear. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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 
 DENTIFICAÇÃ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. 
 
DICA 
Estude e faça a maior quantidade de exercícios possível. Apenas com a prática você internalizará a lógica 
e desenvolverá seus modelos com maior facilidade. 
 
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: 
 
Vitamina Leite (l) Carne (kg) Peixe (kg) Salada ( __100g) 
A 2 2 10 20 
C 50 20 10 30 
D 80 70 10 80 
Tabela de informações nutricionais em mg 
Fonte: Adaptado de Goldbarg e Luna (2005) 
 
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: 
 
 
 
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 saladasão 
apresentadas na tabela de informações nutricionais, já apresentada. Assim, podemos identificar o conjunto de inequações 
que representam estas restrições. São elas: 
 
 
 
Não podemos nos esquecer das restrições de não negatividade para as variáveis de decisão. Logo, temos que: 
 
 
 
Modelo 
Enfim, temos que o modelo para este exemplo do problema da dieta é: 
 
 
 
Sujeito a: 
 
 
 
 
PROBLEMA DO PLANEJAMENTO DE PRODUÇÃO E DE ESTOQUES 
Neste tipo de problema, 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: 
 
 
 
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: 
 
 
 
A fábrica tem capacidade máxima de produção de 300 bicicletas. Logo, a restrição com relação à capacidade da fábrica é: 
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. 
 
 
 
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. 
 
 
 
Por sua vez, devem ser produzidos 15 lotes de bicicletas de adultos, com 5 bicicletas em cada um, de modo que: 
 
 
 
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção estático é: 
 
 
 
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: 
 
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 
Dados de produção de bicicletas. 
Fonte: Adaptado de Ragsdale (2009). 
 
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: 
 
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. 
 
 
 
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: 
 
 
 
Ainda em relação ao estoque, é necessário o balanço do inventário, representado pelas seguintes restrições: 
 
 
 
Enfim, temos que o modelo para este exemplo do problema de planejamento da produção dinâmico é: 
 
 
 
 
PROBLEMA FAZER X COMPRAR 
As organizações enfrentam, 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. Assimsendo, 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. 
 
 
 
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. 
 
É 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. 
 
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 
 
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 
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 
 
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 . 
 
 Rede do problema de transportes. 
 
 
 
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 é: 
 
 
 
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: 
 
 
 
Para facilitar o entendimento do modelo matemático para o problema clássico de transportes, vamos resolver o exemplo a 
seguir: 
 
 
 
Sujeito a: 
 
 
 
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. 
 
 
Rede do problema de transportes.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 
Distâncias para a rede do problema de transportes. 
Fonte: Renata Albergaria de Mello Bandeira 
 
Formule o problema de programação linear que minimize os custos de distribuição da empresa. 
 
SAIBA MAIS 
Os problemas de 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: 
 
 Rede do problema de transbordo. 
 
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 é: 
 
 
 
Sujeito a: 
 
 
 
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. 
 Rede do problema de transbordo. 
 
 
 
 
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 
Demandas e custos de transporte por unidade. 
Fonte: Renata Albergaria de Mello Bandeira 
 
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: 
 
Depósitos Distância Ofertas 
Mercados 
D1 D2 
O1 15 35 60 
O2 43 27 90 
O3 6 38 200 
Demandas 150 200 
Fonte: Renata Albergaria de Mello Bandeira 
 
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 ≤. 
 
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: 
 
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 
 
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 x ij, 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. 
 
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 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 a1. 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: 
 
 
 
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: 
 
 
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 
Tempo para execução das tarefas 
Fonte: Renata Albergaria de Mello Bandeira 
 
Formule o problema de programação linear que minimize o tempo de arrumação do quarto. 
 
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 algoritmo 
hú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: 
 
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 
 
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 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). 
 
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: 
 
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 
 
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. 
 
CONCLUSÃO 
CONSIDERAÇÕES FINAIS 
Vimos como a Pesquisa Operacional pode auxiliar no apoio a processos de decisão, em especial para problemas complexos. 
Ao longo dos módulos, aprendemos sobre modelos matemáticos e como estes podem nos ajudar na análise de decisão, em 
especial por permitirem avaliar a solução do problema em diferentes cenários a um menor tempo e custo. Além disso, 
colocamos estes conceitos em prática à medida que aprendemos a construir modelos matemáticos para problemas de 
programação linear. 
 
Entretanto, é preciso ter em mente que a modelagem não é uma tarefa simples, principalmente para aqueles que estão 
iniciando neste campo do conhecimento. Assim, para nos familiarizarmos com a técnica de modelagem e podermos 
construir modelos com mais facilidade, é preciso praticar por meio de exercícios. A prática é essencial para nos ajudar a 
entender e a dominar a lógica por trás da modelagem matemática. Outro ponto que também facilita a internalização deste 
conhecimento é entender que alguns modelos, conhecidos como problemas típicos, seguem padrões semelhantes. 
 
Portanto, se entendemos a lógica por trás dessa “categoria” de problemas, conseguiremos modelar os demais problemas 
desta mesma classe. Por isso, é importante conhecer esses padrões! 
 
No módulo 1, apresentamos os problemas clássicos da mistura, do planejamento de produção e de estoques, e fazer versus 
comprar. Dedicamos os módulos 2 e 3 para entender a lógica do problema de transporte e de seus casos particulares. O 
destaque para o problema de transporte ocorre porque trata-se do modelo de programação linear mais aplicado na área da 
logística. Abordamos, ainda, no módulo 2 o problema de transbordo, enquanto no módulo 3 tratamos especificamente do 
problema de alocação. 
 
Até o momento, aprendemos a solucionar os modelos matemáticos por meio da aplicação do Método Gráfico. Contudo, tal 
método é restrito a problemas mais simples, com até duas variáveis de decisão.