Modelos em rede

Uma rede é um conjunto de nós ligados entre si por arcos.
Terminologia de redes: é formalmente representada por um Grafo G=(N,A),onde:
N é o conjunto de nós (vértices);
A é o conjunto de Arcos ,tais que cada arco conecta dois nós.
Quando se faz necessário definir sentidos de fluxos, a rede é representada por um Dígrafo(Direct Graph),o qual é um Grafo em cada Arco(i,j) pode ter um sentido a parti de seu nó inicial i para seu nó terminal j.

aavtcl.jpg

Neste ramo da pesquisa operacional, serão apresentados quatro grupos de problemas de otimização que podem ser ilustrados através de redes (arcos e nós) e são bastante utilizados para resolver diversos problemas do mundo real.

Elementos de uma rede

Para conhecer os elementos de uma rede, acompanhe o problema de distribuição de insumos. Considere que existam 4 escritórios do IEF que realizam combate a incêndio. Cada escritório necessita de insumos que são utilizados para reduzir a velocidade do incêndio. Esses insumos podem ser comprados em três fornecedores diferentes localizados em diferentes locais do estado de Minas Gerais.

A necessidade de cada escritório é:

  • Escritório 1: 200 sacos
  • Escritório 2: 300 sacos
  • Escritório 3: 200 sacos
  • Escritório 4: 100 sacos

O insumo pode ser fornecido por três fornecedores que apresentam diferentes estoques:

  • Fornecedor 1: 500 sacos
  • Fornecedor 2: 100 sacos
  • Fornecedor 3: 200 sacos

O problema acima pode ser representado por meio de uma rede. Os vértices ou nós representam os locais, neste problema são escritórios e fornecedores.

t8nk9v.jpg

Figura. Representação dos nós do problema. Fonte: autor

Arcos ou arestas representam a possibilidade de enviar insumo entre dois nós. Logo, arcos conectam os nós.

25hz3uf.jpg

Figura. Representação dos nós e dos arcos do problema, também conhecido como grafo. Fonte: autor

GRAFOS

A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.para tal são empregadas estruturas chamadas de grafos , onde é um conjunto não vazio de objetos denominados vértices (ou nós) e (do inglês Edges-arestas) é um subconjunto de pares não ordenados de v.
Antes de mais nada, vamos tentar entender o que é um grafo. Um grafo é uma estrutura matemática usada para representar as relações entre as coisas, composta por um conjunto não vazio de objetos denominados vértices e um conjunto de pares não ordenados de arestas. O sentido de enviar insumo de um nó para outro é representada por um arco orientado. A ocorrência de um sentido, não obrigado a ocorrência de comunicação no outro sentido.

Imagine:

Um mapa rodoviário: nele, as cidades se relacionam entre si através das várias estradas.
Um sistema de distribuição de água: nele, as casas se relacionam entre si (e entre as centrais de distribuição) através dos canos de água. Esse exemplo também vale para distribuição de energia (casas/postes), de gás (casas/canos), etc.
A hierarquia de uma empresa: nela, os funcionarios se relacionam entre si através da relação "é chefe de". Podemos desenhar então aquelas hierarquias, com o presidente no topo (pois é chefe de todo mundo) e os estagiários lá no fim (pois não mandam em ninguém).
O relacionamento social entre pessoas: nele, as pessoas se interligam entre si atráves da amizade. Se A é amigo de B e B é amigo de C, indiretamente, A está "conectado" a C. O Orkut é um exemplo de rede de amigos que, no fim das contas, é um grafo. Você possui amigos e está "conectado" a eles. Estes, eventualmente estão conectados a outras pessoas. Já notou quando você entra no perfil de alguém que você não conhece (diretamente) e o Orkut mostra um "caminho" de pessoas, de você até aquela pessoa? Aquilo é um clássico problema de grafos! Devemos partir de uma pessoa (você) e, percorrendo seus relacionamentos, encontrar um "caminho" até outra pessoa.
Essas "coisas" que se relacionam entre si são chamados de nós do grafo. Cada relacionamento entre os nós é chamado de aresta. Normalmente, para facilitar sua visualização e sua compreensão, grafos são representados graficamente. Atenção! Não confunda as duas palavras! Grafos são entidades matemáticas, abstratas, que possuem nós (coisas) e arestas (relacionamento entre essas coisas). Gráficos são imagens. Grafos podem ser representados graficamente, mas o grafo não é a sua representação gráfica - existem várias outras maneiras de representar grafos que não graficamente.

25qvw53.jpg

Figura: Representação de um grafo composto por nós e arcos orientados. Fonte: autor

A cada arco associa-se um custo, que neste problema pode ser distância entre os locais, tempo de viagem, consumo de combustível, entre outros. A escolha do custo a ser associado a cada arco depende do objetivo do problema. Neste exemplo, será considerado o custo monetário para se enviar uma unidade de insumo (R$ por unidade) de um fornecedor para um escritório:

E1 E2 E3 E4
F1 8 19 22 6
F2 15 6 16 5
F3 7 8 9 12

Atribuindo a cada arco seu respectivo custo, obtem-se uma rede ou árvore.

1492pa0.jpg

Figura. Representação da rede do problema, contendo nós, arcos orientados e pesos de cada arco. Fonte: autor

Otimizando um problema de rede

Algoritmos para a solução de problemas com estrutura de rede antecedem o surgimento da programação linear em cerca de 200 anos. No entanto, os modelos de redes podem ser resolvidos por meio da programação linear.

Em linhas gerais, um problema de rede pode ser resolvido com os seguintes passos:

  1. Crie o grafo do problema.
  2. Atribua custos aos arcos.
  3. Construa as variáveis de decisão.
  4. Construa o modelo matemático.
  5. Resolva o problema via programação linear.

Tipos de problemas de rede

Os problemas podem ser divididos em quatro grupos:

  • Distribuição de produtos entre vários destinos, a partir de várias origens (Problema de transporte).
  • Distribuição de produtos entre vários destinos, a partir de várias origens, com possibilidade de transbordo (Problema de transbordo).
  • Atribuição de tarefas (Problema de assinalamento).
  • Roteamento (Problema do menor caminho).

Problema de transporte

O Problema de Transporte é talvez o mais representativo dos Problemas de Programação Linear. É um problema de grande aplicação prática, tendo sido estudado por vários investigadores, embora tenha sido Dantzig o primeiro a estabelecer a sua formulação em PL e a propor um método sistemático de resolução.
A Pesquisa Operacional também se aplica a situações de transporte e logística. Os estudos de problemas de transporte têm o objetivo de “determinar o carregamento da rede de transporte de forma que minimize o custo total”. Em outras palavras, as ferramentas de problemas de transporte em Pesquisa Operacional têm o objetivo de fazer com que as empresas transportem as quantidades certas de produtos para seus destinos com o menor custo possível.

Neste tipo de problema o objetivo é relacionar fornecedores e consumidores desde que:

  • Conheça o custo por unidade transportada (não precisa ser custo monetário).
  • Não ocorra transbordo.
  • Conheça a demanda dos consumidores.
  • Conheça a oferta dos fornecedores.
2u63a5k.png

Figura.1
Disponível:http://www.decom.ufop.br/gustavo/bcc342/Aula_11_Transporte.pdf

A formulação básica do problema do transporte é definido por:

$Min Z = \sum_{i=1}^{forn} \sum_{j=1}^{cons} C_{ij}X_{ij}$

S.a.

$\sum_{i=1}^{forn} X_{ij} = Oferta_i$

$\sum_{j=1}^{cons} X_{ij} = Demanda_j$

Construção do Modelo de Transporte

Para construir modelos em Problemas de Transporte utilizamos as três etapas que já
foram abordadas em Programação Linear: definição das variáveis de decisão, definição da
função objetivo e definição das restrições (LEDERMANN; KINALSKI, 2012).

A) Determinação das variáveis de decisão

O primeiro passo é determinar as variáveis de decisão. Por variáveis de decisão entende-se as quantidades que devem ser transportadas de cada origem para cada destino.

B) Determinação da função objetivo

A função objetivo sempre se refere à maximização ou minimização de algo. Nos casos
de Problemas de Transporte, a função objetivo é de minimizar custos.

C) Determinação das restrições

São duas as restrições em Problemas de Transporte: demanda e capacidade produtiva/
necessidades.

Para melhor entendimento, vamos exemplificar:

Exemplo 1

kuo3n.png

Fonte: Ledermann; Kinalski

Pela análise da figura acima podemos evidenciar as seguintes situações: primeiramente, é possível perceber a existência de duas origens e de dois destinos. A origem 1 (Fábrica Ijuí) tem capacidade de produzir 120 unidades de determinado produto. Já a origem 2 (Fábrica Ajuricaba) possui capacidade produtiva de 150 unidades. Por outro lado, o destino 1 (Panambi) tem uma demanda de 150 unidades, e o destino 2 (Três Passos) tem a necessidade de 120 unidades (LEDERMANN; KINALSKI, 2012).

Por outro lado, o custo unitário de transporte da origem 1 para o destino 1 (c11) é de R$
25,00. Já o custo unitário de transporte da origem 1 para o destino 2 (c12) é de R$ 12,00.
Além disso, o custo unitário de transporte do destino 2 para a origem 1(c21) é de R$ 30,00 e
o custo unitário de transporte do destino 2 para o origem 2 (c22) é de R$ 65,00. Estas informações também são expostas na tabela a seguir (LEDERMANN; KINALSKI, 2012).

1j7pf5.png

Onde:

• C11 é a quantidade a ser transportada de Ijuí para Panambi;
• C12 é a quantidade a ser transportada de Ijuí para Três Passos;
• C21 é a quantidade a ser transportada de Ajuricaba para Panambi;
• C22 é a quantidade a ser transportada de Ajuricaba para Três Passos;
• 25 é o custo unitário de transporte de Ijuí para Panambi;
• 75 é o custo unitário de transporte de Ijuí para Três Passos;
• 30 é o custo unitário de transporte de Ajuricaba para Panambi;
• 65 é o custo unitário de transporte de Ajuricaba para Três Passos;
• 150 é a demanda do município de Panambi;
• 120 é a demanda do município de Três Passos;
• 120 é a capacidade produtiva do município de Ijuí;
• 150 é a capacidade produtiva do município de Ajuricaba;

As variáveis de decisão serão:
• C 11
• C 12
• C 21
• C 22

A função objetivo será:

Min: 25.c11 + 75. c12 + 30.c21 + 65. c22;

As restrições de demanda serão:

Demanda do município de Panambi: c11 + c22 = 150;
Demanda do município de Três Passos: c12 + c21 = 120;

As restrições de disponibilidade

Capacidade produtiva da fábrica de Ijuí: c11 + c12 = 120;
Capacidade produtiva da fábrica de Ajuricaba: c21 + c22 = 150;

Para obter-se a solução ótima do problema, poderá ser utilizado softwares de otimização. O software adotado para resolução do problema acima foi o LPSolve.
Após aplicar-se o modelo matemático acima, por meio da aba Results no LPSolve, foi possível obter-se a solução ótima.

dm78lc.png

Fonte: Editor

Para obter-se o menor custo possível, a distribuição seguiria de tal forma:

  • A fábrica de Ijuí distribuíra 75 unidades para Panambi; e 45 unidades para a cidade de Três Passos.
  • A fábrica de Ajuricaba distribuíra 75 unidades para Panambi; e 75 unidades para a cidade de Três Passos.

Desta forma, todos os produtos serão distribuídos de maneira otimizada e com o menor custo possível.

Problema de Transporte Balanceado

Um problema de transporte é considerado balanceado se:

2zog57a.png

Ou seja, o fornecimento supre toda a demanda.

Num problema balanceado, as restrições são todas igualdades.


Disponível:https://www.youtube.com/watch?v=xMu3shq1UNw

Problema de Transporte Desbalanceado

O Problema de Transporte pressupõe que a oferta e demanda são equilibradas, ou seja, iguais. Caso isso não ocorra, é necessário aplicar métodos de "correção" deste desequilíbrio antes de utilizar os algoritmos específicos para o problema.

• Como balancear um problema de transporte quando a capacidade de fornecimento excede a demanda?

É necessário a criação de um ponto fictício de demanda e a demanda nesse ponto será igual ao excedente da capacidade.

• Como balancear o problema quando a demanda é maior que a capacidade de fornecimento?

Neste caso, provavelmente o problema não possui soluções viáveis. Como alternativa, pode-se adicionar um ponto fictício de fornecimento e o custo de fornecimento daquele ponto será igual à penalização incorrida pelo não fornecimento do insumo.


Disponível:https://www.youtube.com/watch?v=U70erox4S3c

Problema de transbordo

A grande dificuldade dos problemas de transbordo é o desconhecimento das quantidades demandadas ou disponíveis nos pontos de transbordo. Se trata de um problema de transporte mas possuí nós intermediários com b = 0 (pode ser ≠ 0) ou seja a oferta e a demanda dos nós intermediários é igual a 0. O problema só terá solução se a soma de todos os níveis de oferta se igualar à soma dos níveis de demanda.

Formulação básica:

$Min Z = \sum_{i=1}^{forn} \sum_{j=1}^{cons} C_{ij}X_{ij}$

S.a.

$\sum_{i=1}^{forn} X_{ij} = Oferta_i$

$\sum_{j=1}^{cons} X_{ij} = Demanda_j$

$\sum_{i=1}^{cons} X_{ix} - \sum_{j=1}^{cons} X_{xj}= 0$

2z4inug.png

Figura.1
Disponível:http://www.decom.ufop.br/gustavo/bcc342/Aula_11_Transporte.pdf

Como observado na figura anterior e na formulação matemática, o problema do transbordo irá apresentar três pontos, sendo eles:

• Ponto de fornecimento - pode remeter insumos para outros pontos, mas não pode receber.
• Ponto de demanda - pode receber insumos de outros pontos, mas não pode remeter.
• Ponto de transbordo - remete e recebe insumos de outros pontos.

O problema do transbordo terá resolução semelhante ao problema do transporte balanceado.

Exemplo 1:

Uma empresa que produz máquinas florestais possui duas plantas: uma em Porto Alegre e outra em Goiânia. A distribuição das máquinas é feita através de duas revendas: uma localizada em BH e outra em Curitiba. A partir das revendas, as máquinas são transportadas para os clientes finais em Ipatinga, Três Lagoas e Jacareí. A capacidade de produção é de 50 unidade em Porto Alegre e 30 em Goiânia. A demanda em Ipatinga, Três Lagoas e Jacareí é de 20, 35 e 25 respectivamente. A matriz de custo de transporte, em mil reais / máquina, é:

BH Curitiba Ipatinga Três Lagoas Jacareí
Goiânia 8 10
Porto Alegre 7 4
Porto Alegre 1 5 4
Curitiba 4 3 2

Formulação conceitual:
F.O: Minimizar o custo de transporte entre os fornecedores e o cliente final.
S.a.

  • Quantidade de demanda em Ipatinga;
  • Quantidade de demanda em Três Lagoas;
  • Quantidade de demanda em Jacareí;
  • Capacidade produtiva em Porto Alegre;
  • Capacidade produtiva em Curitiba;
  • Transbordo entre as cidades de Belo horizonte para Ipatinga, Três Lagoas e Jacareí.
  • Transbordo entre as cidades de Curitiba para Ipatinga, Três Lagoas e Jacareí.

Formulação matemática:
F.O (MinZ): 7PABH+ 4PACU+ 8GOBH+ 10GOCU+ 1BHIPA+ 5BHTLA+ 4BHJA+ 4CUIPA+3CUTLA+2CUJA;
S.a.
P.A: PACU+PABH=50;
GO:GOBH+GOCU=30;
IPA:CUIPA+BHIPA=20;
TLAGOAS: BHTLA+CUTLA=35;
JACAREI: CUJA+BHJA=25;
BH: PABH+GOBH-BHIPA-BHTLA-BHJA=0;
CURITIBA: PACU+GOCU-CUIPA-CUTLA-CUJA=0;

Solução do problema no LPSolve:
O custo final será de R$ 635.000,00.
Todas as 50 unidades produzidas em Porto Alegre serão entregues em Curitiba e na sequência, serão distribuídas 35 em Três Lagoas e 15 em Jacareí. Todas as 30 unidades produzidas em Goiânia serão entregues em Belo Horizonte e na sequência, serão distribuídas 20 em Ipatinga e 10 em Jacareí.

Vídeo aula de transbordo:

Problema de assinalamento

Este modelo é muito utilizado para atribuir tarefas a diferentes agentes. Neste tipo de problema, utiliza-se variáveis binárias (0/1) terminando assinalamento ou não assinalamento. O número de tarefas deve ser igual ao número de agentes. Para contornar problemas reais de falta de tarefa/agente, deve-se criar uma entidade fictícia.

2h58h01.png

Figura.1
Disponível:http://www.decom.ufop.br/gustavo/bcc342/Aula_11_Transporte.pdf

Formulação básica:

$Min Z = \sum_{i=1}^{tarefa} \sum_{j=1}^{agente} C_{ij}X_{ij}$

S.a.

$\sum_{i=1}^{tarefa} X_{ij} = 1$

$\sum_{j=1}^{agente} X_{ij} = 1$

Exemplo 1:
Uma empresa deseja direcionar um funcionário para cada cliente, de forma a garantir a maior satisfação possível. Cada cliente recebeu uma descrição de cada funcionário e atribuiu uma nota, que quanto maior, melhor avaliado o funcionário foi. Como a empresa deve distribuir os funcionários entre os clientes de forma a maximizar a satisfação dos mesmos?

2cf5e93.png

Formulação conceitual:
F.O: Maximizar a satisfação do cliente por meio das notas dadas a cada funcionário.
S.a
Restrições
Notas distribuídas pelo cliente 1 a cada funcionário;
Notas distribuídas pelo cliente 2 a cada funcionário;
Notas distribuídas pelo cliente 3 a cada funcionário;
Notas distribuídas pelo cliente 4 a cada funcionário;
Notas distribuídas pelo cliente 5 a cada funcionário;
Notas recebidas pelo funcionário 1 de cada cliente;
Notas recebidas pelo funcionário 2 de cada cliente;
Notas recebidas pelo funcionário 3 de cada cliente;
Notas recebidas pelo funcionário 4 de cada cliente;
Notas recebidas pelo funcionário 5 de cada cliente;

Formulação matemática:
F.O (Max): 38F1C1+39F2C1+ 36F3C1+38F4C1+ 40F5C1+ 51F1C2+ 54F2C2+ 55F3C2+ 54F4C2+ 50F5C2 +42F1C3+36F2C3+40F3C3+ 43F4C3+40F5C3 +39F1C4+38F2C4+39F3C4+37F4C4+36F5C4+39F1C5+36F2C5+42F3C5+ 37F4C5+ 38F5C5;
S.a
C1: F1C1+F2C1+F3C1+F4C1+ F5C1=1;
C2: F1C2+F2C2+F3C2+F4C2+ F5C2=1;
C3: F1C3+F2C3+F3C3+ F4C3+F5C3 =1;
C4: F1C4+F2C4+F3C4+F4C4+F5C4 =1;
C5: F1C5+F2C5+F3C5+ F4C5+ F5C5=1;
F1: F1C1+F1C2+F1C3+F1C4+ F1C5=1;
F2: F2C1+F2C2+F2C3+F2C4+ F2C5=1;
F3: F3C1+F3C2+F3C3+F3C4+ F3C5=1;
F4: F4C1+F4C2+F4C3+F4C4+ F4C5=1
F5: F5C1+F5C2+F5C3+F5C4+ F5C5=1;

Solução do problema no LPSolve:
A máxima pontuação alcançada pelos funcionários será de 218 pontos.
Para total satisfação dos clientes, os atendimentos sucederiam de tal forma:

  • Cliente 1 será atendido pelo funcionário 5.
  • Cliente 2 será atendido pelo funcionário 2.
  • Cliente 3 será atendido pelo funcionário 4.
  • Cliente 4 será atendido pelo funcionário 1.
  • Cliente 5 será atendido pelo funcionário 3.

Vídeo aula de Assinalamento

Exemplo de Assinalamento


Disponível: https://www.youtube.com/watch?time_continue=14&v=kMRWOYLlYBw

Modelo do menor caminho

Problemas deste tipo tem o objetivo de delinear o menor caminho unindo uma origem e um destino através de uma rede conectada. Os arcos desta rede devem estar associados a distâncias, tempo, custo, consumo de combustível ou qualquer outra propriedade mensurável. Em caso de arcos contendo receitas, o problema pode ser adaptado para maximização!

Formulação básica:

$Min Z = \sum_{i=1}^{origem} \sum_{j=1}^{destino} C_{ij}X_{ij}$

S.a.

$\sum_{j=1}^{destinos} X_{0j} = 1$

$\sum_{j=1}^{destinos} X_{inter,j} - \sum_{i=1}^{origens} X_{i,inter} = 0$

$\sum_{i=1}^{origens} X_{i0} = 1$

Caminhos e ciclos em grafos

Os conceitos de caminho e ciclo são muito importantes no estudo de grafos. É preciso fazer distinções um tanto sutis entre caminhos, caminhos simples, passeios, ciclos, e ciclos simples.

Caminhos

Um passeio em um grafo é uma sequência de vértices dotada da seguinte propriedade: se v e w são vértices consecutivos na sequência então v-w é um arco do grafo. O inverso de um passeio em geral não é um passeio. Um arco do passeio é qualquer arco v-w do grafo tal que w é o sucessor de v no passeio. Um passeio é fechado se tem pelo menos dois arcos e seu primeiro vértice coincide com o último.
Um caminho em um grafo é um passeio sem arcos repetidos, onde os arcos são diferentes entre si. Um caminho é simples se não tem vértices repetidos. Por exemplo, 1 - 2 - 3 - 5 - 6 é um caminho simples no grafo da figura 1.

2cngxsz.jpg

Figura 1. Grafo caminhos Fonte. Autor

Todos os arcos de um caminho apontam na mesma direção -> de um vértice para o seu sucessor. A origem de um caminho é o seu primeiro vértice. O término é o seu último vértice. Se um caminho tem origem s e término t, dizemos que vai de s a t.
O comprimento de um caminho é o número de arcos do caminho. Se um caminho tem n vértices, seu comprimento é pelo menos n−1; se o caminho é simples, seu comprimento é exatamente n−1.

Exemplo 1) Caminho Simples: 0 - 1 - 2 , 1 - 2 -3 - 5 - 6 , 0 - 7 - 0 , 0 - 7 - 1 - 2 - 3 - 1 - 2.

Os dois primeiros caminhos são simples e possuem comprimento 2 e 4 respectivamente. Os dois últimos não são simples e possuem comprimento de pelo menos 2 e 6.

Exemplo 2) Não são caminhos: 0 - 1 - 6 - 7 - 0 - 7 , 3 - 4 - 5.

Ciclos

Um ciclo em um grafo é um caminho fechado. (Portanto, todo ciclo tem comprimento maior que 1 e não tem arcos repetidos.) Dizemos que um arco v-w pertence a um dado ciclo (ou que o ciclo passa pelo arco) se o vértice w é o sucessor de v no ciclo. Um ciclo é simples se não tem vértices repetidos exceto pelo último (que coincide com o primeiro).
É apropriado abusar um pouco do conceito de igualdade e tratar dois ciclos simples como iguais se eles têm o mesmo conjunto de arcos, ainda que tenham origens diferentes. Por exemplo, trataremos como iguais os ciclos do grafo da figura 2: 0 – 1 – 3 – 0, 1 – 3 – 0 – 1, 3 – 0 – 1 – 3.

14mgljc.png

Fugura 2. Grafo Fonte. Autor

Todos os arcos de um ciclo apontam no mesmo sentido — de um vértice do ciclo para o seu sucessor.
2 – 3 – 4 – 2 e 0 – 1 – 3 – 3, são exemplos de ciclo simples, e possuem comprimento iguais a 3. Já os exemplos 5 – 1 – 3 – 0 – 1 – 2, 5 e 5 – 4 não são ciclos.

Fonte: https://www.ime.usp.br/~pf/algoritmos_para_grafos/index.html#contents
https://visualgo.net/pt/mst

Atividade 1

Menor caminho

Desenvolva a formulação matemática e apresente a solução utilizando o LPSolve para o problema de menor caminho:

2w6xlah.png

Solução:

Formulação Matemática

11lirgg.png

Solução do LPSolve

Image and video hosting by TinyPic
2d8gqc6.png

Atividade 2

Construa, um caminho da portaria da UFVJM – Campus JK até o DEF, com a menor quantidade de buracos.

1° passo: Identificação e quantificação dos buracos existentes nas vias de acesso, que possibilitem a realização do objetivo.

2°passo : Com auxilio do LPSolve faça a modelagem do modelo matemático para a minimização de buracos na rota, e represente o grafo.

Modelo Matemático

5efkhf.png2j65tat.jpg2a80ytu.png

Resultado

jzwp4m.png

Grafo

ics0ua.png
11j55ih.jpg
images?q=tbn:ANd9GcQzSj16N3aiIajs9J59gUVeZWZNGcaI4a_gzb2iX7KP9VfPjH9E

Problema do Transporte - Resoluções LP Solve

O Problema de Transporte é uma das aplicações mais importantes da programação linear para resolver problemas empresariais na distribuição física de produtos, que, geralmente, chamamos de problemas de transporte.
Encontramos um problema de transporte quando precisamos enviar unidades de um produto por uma rede de rodovias que conectam um determinado grupo de cidades. Cada cidade é considerada uma “fonte”, em que unidades serão transportadas para fora do local, ou um “receptor”, onde as unidades são exigidas no local. Cada fonte tem uma determinada provisão, cada receptor tem uma determinada demanda e cada rodovia que conecta um par de fontes e receptores tem um determinado custo de transporte por unidade de remessa.
Isto pode ser visualizado na forma de uma rede. O objetivo é determinar um modelo ótimo de transporte que minimize o custo
O problema geral de transporte consiste em determinar a forma mais eficiente, isto é, mais econômica de enviar um bem disponível em quantidades limitadas em determinados locais para outros locais onde é necessário. Como qualquer problema de PL, este pode ser resolvido pelo método do simplex. Porém a sua estrutura particular, permitiu a utilização de métodos que embora derivados do simplex, são bastante mais eficientes.
eaffwj.png

Exemplo 01

Cinco regiões metropolitanas recebem energia elétrica de quatro hidrelétricas, que produzem respectivamente 10, 8, 5 e 3 megawatts/hora. As regiões metropolitanas, por sua vez, demandam respectivamente 2, 5, 8, 4 e 7 megawatts/hora. O custo de distribuição entre as hidrelétricas e as regiões metropolitanas por megawatt/hora está descrito na tabela abaixo:
10wunoz.png
Representação da rede
hvtkqu.png

Formulação Conceitual
F.O.: Minimizar o custo de distribuição entre as Hidrelétricas e as Regiões Metropolitanas.

S.a:
- Capacidade de produção das hidrelétricas
- Demanda das regiões metropolitanas

Resolução pelo LPSolve

Modelo Matemático:
2cwtp3r.png
Solução do problema
2cojxnm.png

Sendo assim, a Hidroelétrica 1 deve enviar: 2 megawatts/hora para a Metrópole 2, 1 megawatts/hora para a Metrópole 4 e 7 megawatts/hora para a Metrópole 5.
A Hidroelétrica 2 deve enviar: 5 megawatts/hora para a Metrópole 3 e 3 megawatts/hora para a Metrópole 4.
A Hidroelétrica 3 deve enviar: 2 megawatts/hora para a Metrópole 1 e 3 megawatts/hora para a Metrópole 2.
A Hidroelétrica 4 deve enviar: 3 megawatts/hora para a Metrópole 3

Problema do Assinalamento

Rede bipartida onde o número de nós de oferta é igual ao número de nós de
demanda.
Nesse tipo de problema não há oferta e demanda.

Exemplo 01

Uma empresa deseja direcionar um funcionário para cada cliente, de forma a garantir a maior satisfação possível. Cada cliente recebeu uma descrição de cada funcionário e atribuiu uma nota, que quanto maior, melhor avaliado o funcionário foi.

2dawzew.jpg

Representação da rede

Como a empresa deve distribuir os funcionários entre os clientes de forma a maximizar a satisfação dos mesmos?

Formulação Conceitual
F.O.: Maximizar a distribuição dos funcionários entre os clientes.

S.a:
-O funcionário deverá exercer uma tarefa;
-O cliente deverá ter um funcionário;

Resolução pelo LPSolve

Modelo Matemático:

34oajcw.jpg

Solução do problema

6dzecg.jpg
1zf0r2q.jpg

Para atingir o objetivo de maximizar a satisfação dos clientes, a empresa deverá direcionar o funcionário 1 para o cliente 4. O funcionário 2 para o cliente 2.O funcionário 3 para o cliente 5. O funcionário 4 para o cliente 3 e o funcionário 5 para o cliente 1.

Problema do Transbordo

É um problema de transporte com nós intermediários com b = 0 ou seja a oferta e a
demanda dos nós intermediários é igual a 0.

Exemplo 01

Uma empresa que produz máquinas florestais possui duas plantas: uma em Porto Alegre e outra em Goiânia. A distribuição das máquinas é feita através de duas revendas: uma localizada em BH e outra em Curitiba. A partir das revendas, as máquinas são transportadas para os clientes finais em Ipatinga, Três Lagoas e Jacareí. A capacidade de produção é de 50 unidade em Porto Alegre e 30 em Goiânia. A demanda em Ipatinga, Três Lagoas e Jacareí é de 20, 35 e 25 respectivamente. A matriz de custo de transporte, em mil reais / máquina, é:

s2unhj.jpg
Representação da rede
xduu6f.png

Formulação Conceitual
F.O.: Minimizar os custos de transporte de distribuição entre fornecedores e clientes.

S.a:

-Todo fornecedor tem que distribuir a mercadoria;
-Todo cliente tem que receber a mercadoria;
-Todo intermediário deve receber e despachar a mercadoria;

Resolução pelo LPSolve

Modelo Matemático:

34gx0s4.jpg

Solução do problema

2cq0b5j.jpg

A solução que minimiza os custos seria:
As máquinas que sairão de Goiânia serão 30, passando por BH, será distribuído 20 máquinas para Ipatinga e 10 máquinas para Jacareí.
As máquinas que sairão de Porto Alegre serão 50, passando por Curitiba, serão distribuídas 35 máquinas para Três Lagoas, e 15 máquinas para Jacareí.

Salvo indicação em contrário, o conteúdo desta página é licenciado sob Creative Commons Attribution-ShareAlike 3.0 License