AULA 005 - O PROBLEMA DO CUSTO MINIMO

Prévia do material em texto

PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
Fernando Tadeu Pongelupe Nogueira 
fernando.nogueira@prof.una.br 
PESQUISA OPERACIONAL 
Otimização de Redes e Filas e Simulação 
I – MODELOS DE OTIMIZAÇÃO DE REDES 
O problema do fluxo de custo mínimo ocupa 
uma posição fundamental entre os modelos 
de otimização de redes, pelo fato de englobar 
uma classe de aplicações abrangente como 
também pelo fato de ser resolvido de forma 
extremante eficiente. 
 
Assim como o problema do fluxo máximo, ele 
considera o fluxo através de uma rede com 
capacidades de arcos limitadas. 
O Problema do Fluxo de Custo Mínimo 
Da mesma forma como o problema do 
caminho mais curto, ele considera um custo 
(ou distância) para o fluxo através de um 
arco. 
 
Como o problema de transporte ele pode 
considerar várias origens (nós de suprimento) 
e vários destinos (nós de demandas) para o 
fluxo, novamente com custos associados. 
O Problema do Fluxo de Custo Mínimo 
1. A rede é uma rede direcionada e conectada. 
 
2. Pelo menos um dos nós é um nó de suprimento. 
 
3. Pelo menos um dos demais nós é um nó de demanda. 
 
4. Todos os nós remanescentes são nós transshipment (transbordo). 
 
5. O fluxo através de um arco é permitido somente na direção indicada 
pela seta, em que a quantidade máxima de fluxo é dada pela 
capacidade desse arco. Se o fluxo puder ocorrer em ambas as direções, 
isso seria representado por um par de arcos apontando em direções 
opostas. 
O Problema do Fluxo de Custo Mínimo 
6. A rede tem arcos suficientes com capacidade suficiente 
para permitir que todo o fluxo gerado nos nós de suprimento 
atinjam todos os nós de demanda. 
 
7. O custo do fluxo através de cada arco é proporcional à 
quantidade desse fluxo, no qual o custo por fluxo unitário é 
conhecido. 
 
8. O objetivo é minimizar o custo total de enviar a provisão 
disponível através da rede a fim de satisfazer a demanda 
dada. Um objetivo alternativo é maximizar o lucro total de se 
fazer isso. 
 
O Problema do Fluxo de Custo Mínimo 
Aplicações 
A CIA. DISTRIBUIDORA ILIMITADA fabricará um produto 
em duas fábricas diferentes e depois o produto terá de 
ser despachado para dois depósitos onde qualquer 
uma das fábricas poderá suprir ambos os depósitos. 
 
A rede de distribuição disponível para despachar este 
produto é mostrada a seguir, em que F1 e F2 são as 
duas fábricas, W1 e W2 os dois depósitos e DC o centro 
de distribuição. As quantidades a serem enviadas de F1 
e F2 estão indicadas à esquerda delas e as quantidades 
a serem recebidas em W1 e W2 se encontram à direita 
destes. 
O Problema da Cia de Distribuição 
Cada seta representa uma rota viável. Portanto, F1 pode 
despachar produtos diretamente para W1 e possui três rotas 
possíveis (F1DCW2, F1F2DCW2 e F1W1W2) 
para despachar para W2. A fábrica F2 possui apenas uma rota 
para W2 (F2DCW2) e outra para W1 
(F2DCW2W1). 
 
O custo por unidade enviada através de cada rota está 
indicado próximo à seta. Também indicados próximos a 
F1F2 e a DCW2 estão as quantidades máximas que 
podem ser enviadas por essas rotas. As demais rotas possuem 
capacidade de embarque suficiente para lidar com qualquer 
volume que essas fábricas consigam enviar. 
O Problema da Cia de Distribuição 
O Problema da Cia de Distribuição 
O problema acima pode ser modelado da 
seguinte forma: 
O Problema da Cia de Distribuição 
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑟 Z = 2𝑥𝐹1−𝐹2 + 4𝑥𝐹1−𝑊1 + 3𝑥𝐹2−𝐷𝐶 + 𝑥𝐷𝐶−𝑊2 + 3𝑥𝑊1−𝑊2 + 2𝑥𝑊2−𝑊1 
Sujeito a 𝑥𝐹1−𝐹2 + 𝑥𝐹1−𝐷𝐶 + 𝑥𝐹1−𝑊1 = 50 
-𝑥𝐹1−𝐹2 + 𝑥𝐹2−𝐷𝐶 = 40 
−𝑥𝐹1−𝐷𝐶 − 𝑥𝐹2−𝐷𝐶 + 𝑥𝐷𝐶−𝑊2 = 0 
−𝑥𝐹1−𝑊1 + 𝑥𝑊1−𝑊2 − 𝑥𝑊2−𝑊1 = −30 
−𝑥𝐷𝐶−𝑊2 − 𝑥𝑊1−𝑊2 + 𝑥𝑊2−𝑊1 = −60 
𝑥𝐹1−𝐹2 ≤ 10, 𝑥𝐷𝐶−𝑊1 ≤ 80 
𝑥𝐹1−𝐹2 ≥ 0, 𝑥𝐹1−𝐷𝐶 ≥ 0, 𝑥𝐹1−𝑊1 ≥ 0, 𝑥𝐹2−𝐷𝐶 ≥ 0, 𝑥𝐷𝐶−𝑊2 ≥ 0, 𝑥𝑊1−𝑊2 ≥ 0, 𝑥𝑊2−𝑊1 ≥ 0 
O Problema da Cia de Distribuição 
 
 
O custo total resultante é: US$ 
49.000,00. 
O Problema da Cia de Distribuição 
 
 
Veja solução no EXCEL. 
O Problema da Cia de Distribuição 
Agradecimento 
 
 
• Agradeço à Profa. Alaine Cardoso Silva (Msc) 
pelas orientações e materiais que serviram de 
base para elaboração deste power point. 
Bibliografia 
 
 
HILLIER, Frederick S. e LIEBERMAN, Gerald J. 
Introdução à Pesquisa Operacional. 9ª 
edição. Porto Alegre: AMGH Editora Ltda 
(McGraw Hill), 2013. Capitulo 9 – pg. 341-
403.