2019416_92146_5-+PROBLEMA+DE+TRANSPORTE+-+SOLVER (2)

Prévia do material em texto

PESQUISA OPERACIONAL
Prof. MsC. Carlos Mariano 
O PROBLEMA DE TRANSPORTE
O problema do transporte constitui uma classe de problemas com as seguintes características: existem m fornecedores de itens a serem transportados (também chamados de fontes), cada um com determinada oferta ai (i = 1,2,...,m) e n consumidores, cada um com uma demanda bj (j = 1,2,...,n) que deverão receber as mercadorias ofertadas pelas fontes. É conhecido ainda o custo de transporte por item de cada fonte i para cada endereço j, designado por cij.
Suponha que a oferta total é igual a demanda total, isto é, é sempre possível transportar todas as ofertas e atender todas as demandas. O objetivo é efetuar o transporte ao menor custo total possível.
A modelagem pode ser estruturada da seguinte forma:
sujeito a
, para i = 1,…,m que corresponde as m restrições de cada oferta ai.
, para j = 1,…,n que corresponde as n restrições de cada ponto de demanda bi.
, para i = 1,…,m e para j = 1,…,n que corresponde as não-negatividades do modelo.
Não entendi nada, mas observe os seguintes exemplos:
Caso 1: A oferta total é igual a demanda total
Exemplo 1:
Três fábricas de automóveis, F1, F2 e F3, devem suprir a demanda de quatro centros de distribuição, denominados C1, C2, C3 e C4. Os automóveis são transportados em números inteiros de caminhões. Assim, o custo de transporte entre uma fábrica e o centro de distribuição dependerá da distância rodoviária entre cada fábrica e o centro de distribuição.
As rotas mais curtas foram determinadas, os custos foram calculados e esses dados encontram-se na tabela abaixo:
	
	C1
	C2
	C3
	C4
	Oferta ai
	F1
	5,5
	4,5
	9,9
	2,7
	10
	F2
	6,4
	2,5
	3,3
	4,2
	9
	F3
	2,5
	4,9
	4,6
	4,7
	9
	Demanda bj
	4
	7
	5
	12
	28
Solução:
Variáveis: Xij = quantidade a ser transportada da fábrica i até o endereço j, com i = 1, 2 , 3 e j = 1, 2,3,4.
A solução ótima, obtida pelo Solver, deste problema é a seguinte:
X14 = 10
X22 = 7
X24 = 2
X31 = 4
X33 = 3
Com Z = 85,9
O problema de transporte anterior apresenta situação de equilíbrio entre a oferta e a demanda, isto é, a demanda era igual a oferta. Todas as restrições apresentavam sinais de igualdade.
Agora veremos a modelagem para dois casos distintos: a oferta total é maior que a demanda total ou a demanda total é maior que a oferta total.
Caso 2: A oferta total é maior que a demanda total
Neste caso, nem todas as fábricas produzirão em plena capacidade, porém os centros consumidores receberão as quantidades que desejam.
A modelagem fica:
sujeito a
, para i = 1,…,m que corresponde as m restrições de cada oferta ai.
(obs.: estas restrições representam a condição de que as fábricas podem produzir quantidades menores ou iguais às suas capacidades instaladas).
, para j = 1,…,n que corresponde as n restrições de cada ponto de demanda bi.
(obs.: estas restrições representam a condição de que como as fábricas possuem capacidade excedente, toda a demanda pode ser atendida).
, para i = 1,…,m e para j = 1,…,n que corresponde as não-negatividades do modelo.
Caso 3: A demanda total é maior que a oferta total
Neste caso, nem todos os centros consumidores receberão toda a quantidade que desejam, porém as fábricas produzirão tudo o que puderem, ou seja, trabalharão em plena capacidade.
A modelagem fica:
sujeito a
, para i = 1,…,m que corresponde as m restrições de cada oferta ai.
(obs.: estas restrições representam a condição de que as fábricas podem produzir em plena capacidade).
, para j = 1,…,n que corresponde as n restrições de cada ponto de demanda bi.
(obs.: estas restrições representam a condição de que nem todos os centros consumidores serão atendidos plenamente).
, para i = 1,…,m e para j = 1,…,n que corresponde as não-negatividades do modelo.
Exemplo 2:
A Vainamaha é uma fábrica de bicicletas que possui três fábricas localizadas no Rio de Janeiro, em São Paulo e em Belo Horizonte. A produção da empresa deve ser entregue e Recife, Salvador e Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores da tabela abaixo, faça a modelagem matemática do problema afim de calcular o quanto deve ser produzido e entregue por fábrica em cada centro consumidor, de forma a minimizar os custos de transporte.
	Fábrica
	Centro Consumidor
	Oferta ai
	
	Recife (1)
	Salvador (2)
	Manaus (3)
	
	Rio de Janeiro (1)
	25
	20
	30
	2000
	São Paulo (2)
	30
	25
	25
	3000
	B. Horizonte (3)
	20
	15
	23
	1500
	Demanda bj
	2000
	2000
	1000
	
Solução:
Variáveis: Xij = quantidade a ser transportada da fábrica i até o endereço j, com i = 1, 2 , 3 e j = 1, 2,3.
Considerações e Interpretações:
	Capacidade > Demanda
	Demanda > Capacidade
	Ação: Busca de novos centros consumidores
	Ação: Criação de nova fábrica
	Interpretação: Capacidade ociosa das fábricas
	Interpretação: demanda não atendida
EXERCÍCIOS PROPOSTOS
1 
Temos que transportar produtos das várias origens, onde estão estocados, para vários destinos, onde são necessários. Conhecemos os custos unitários de transporte de cada origem para cada destino ( Cij = custo unitário de transporte da origem i para o destino j). Devemos decidir quanto transportar de cada origem para cada destino (Xij = quantidade a ser transportada da origem i para o destino j).
O objetivo é completar a transferência dos produtos com o menor custo possível. Considere que a quantidade disponível nas origens seja exatamente igual ao total das necessidades nos destinos.
Complete a tabela de necessidades, disponibilidades e custos para o problema proposto. Faça a modelagem de programação linear e resolva o problema aplicando o Solver.
	Origens \ Destinos
	D1
	D2
	Disponibilidades
	O1
	
	
	
	O2
	
	
	
	O3
	
	
	
	Necessidades
	
	
	
2 Uma companhia tem três instalações industriais que podem produzir, cada uma delas, três diferentes produtos P1, P2 e P3. Os custos em cada instalação variam de acordo com a tabela:
	Instalações
	Custos unitários
	Capacidade em unidades/semana
	
	P1
	P2
	P3
	
	1
	8
	4
	10
	600
	2
	9
	6
	10
	900
	3
	12
	10
	11
	800
	Demanda dos produtos (unidades por semana)
	500
	1000
	1000
	
 Faça a modelagem completa a fim de minimizar os custos de produção.
3 Uma vinícola do sul de Santa Catarina possui três fábricas e três armazéns nos quais os vinhos são envelhecidos. Como as fábricas e os armazéns estão localizados em diferentes locais do estado, a empresa deseja saber quantos tonéis de vinho deve enviar de cada fábrica para cada armazém de forma a minimizar o seu custo de transporte. As capacidades das fábricas e dos armazéns (em número de tonéis), bem como os custos de transporte por tonel, estão explicitados na tabela a seguir.
4- A PowerCo tem três usinas elétricas para suprir as necessidades de quatro cidades; Jacareí, São José, Caçapava e Taubaté., sendo suas potências instaladas, respectivamente, de 35 milhões de kW/h; 50 milhões de kW/h e 40 milhões de kW/h. A demanda de energia atinge o pico nas cidades no mesmo momento (19 h) e é como se segue (em kW/h): Jacare´, 45 milhões, São José, 20 milhões, Caçapava, 30 milhões e Taubaté 30 milhões. O custo (em reais) de enviar um milhão de kw/h de eletricidade de cada usina para cada uma das cidades está na tabela a seguir:
	
	Jacareí
	São José
	Caçapava
	Taubaté
	Usina 1
	8
	6
	10
	9
	Usina 2
	9
	12
	13
	7
	Usina 3
	14
	9
	16
	5
	
Modele o problema como um de transporte a fim de minimizar o custo de transporte.
Sugestão: Fazer Xij = quantidade produzida na usina ie entregue na cidade j
5- A MG Auto tem três fábricas: uma em Los Angeles, uma em Detroit e outra em Nova Orleans, e duas grandes centrais de distribuição: uma em Denver e outra em Miami. As capacidades das três fábricas para o próximo trimestre são 1.000, 1.500 e 1.200 carros. As demandas trimestrais nas duas centrais de distribuição são 2.300 e 1.400 carros, para Denver e Miami, respectivamente. O mapa de distâncias entre as fábricas e as centrais de distribuição é dado na tabela 1.
A empresa transportadora encarregada do transporte dos carros cobra 8 centavos por milha por carro. Os custos de transporte por carro nas diferentes rotas, arredondados para o valor mais próximo, são dados na tabela 2.
Modele o problema de transporte a fim de minimizar o custo de transporte.
Tabela 1: Mapa de Distâncias
	
	Denver
	Miami
	Los Angeles
	1.000
	2.690
	Detroit
	1.250
	1.350
	Nova Orleans
	1.275
	850
Tabela 2: Custo de Transporte por carro
	
	Denver
	Miami
	Los Angeles
	80
	215
	Detroit
	100
	108
	Nova Orleans
	102
	68
6- A Miss Daisy é um laboratório de manipulação que presta serviços de entrega para idosos. A empresa possui duas filiais e fornece o serviço a seis bairros diferentes. Tendo em vista que atualmente a demanda é superior à capacidade de entrega da companhia, ela gostaria de saber a quais clientes atender, em cada filial, de maneira a minimizar o custo de entrega. As capacidades das filiais, as demandas dos bairros e os custos unitários de entrega são mostrados na tabela a seguir.
	
	Ipanema
	Copacabana
	Centro
	Barra
	Leblon
	Tijuca
	Capacidade
	Filial Centro
	7
	9
	1
	12
	7
	4
	2500
	Filial Barra
	4
	5
	12
	1
	3
	8
	2000
	Demanda
	1400
	1560
	400
	150
	870
	620
	
7- A organização Criança do Futuro está organizando a festa de aniversariantes do mês. Para isso, ela começa a pesquisar o preço de doces e salgados em cinco diferentes bufês de São José dos Campos. Como a festa vai ser realizada com o dinheiro de doações, ela deseja ter os menores custos possíveis. Dada a tabela a seguir, que relaciona os custos de cada item por empresa, bem como as quantidades requeridas para a festa (demanda) e as capacidades de produção de cada empresa (oferta), faça a modelagem do problema afim de calcular quantos doces e salgados a empresa deve encomendar de cada empresa.
	
	Ouriço
(1)
	Cajuzinho
(2)
	Brigadeiro
(3)
	Bolinha de queijo
(4)
	Rissole
(5)
	Croquete
(6)
	Coxinha
(7)
	Oferta
	Empresa 1
	0,08
	0,07
	0,07
	0,08
	0,09
	0,08
	0,08
	25000
	Empresa 2
	0,08
	0,07
	0,08
	0,06
	0,06
	0,06
	0,06
	23000
	Empresa 3
	0,05
	0,04
	0,04
	0,03
	0,03
	0,04
	0,07
	15000
	Empresa 4
	0,05
	0,05
	0,04
	0,04
	0,04
	0,04
	0,05
	22000
	Empresa 5
	0,06
	0,06
	0,05
	0,05
	0,06
	0,06
	0,07
	20000
	Demanda
	5000
	4000
	7000
	5000
	4000
	3500
	6000
	
Sugestão: Fazer Xij = quantidade encomendada da empresa i do produto j
PROGRAMAÇÃO LINEAR – RESOLUÇÃO COM O EXCEL (SOLVER)
1 – Disponibilizando a ferramenta Solver do Excel:
Abrindo o Excel, ir até o menu Ferramentas e escolher a opção Suplementos. Abrindo a caixa de diálogo, selecione a opção Solver. Dê OK e confirme no menu Ferramentas se o programa Solver foi instalado com sucesso.
2 – Resolvendo um problema de Programação Linear com o Solver:
Considere o seguinte exemplo:
a) Abrir uma planilha de Excel e digitar o problema conforme a modelagem.
As células D5, D7, D8 e D9 (na cor preta) indicam fórmulas e são, respectivamente,:
=SOMARPRODUTO($B$5:$C$5;B8:C8)
=SOMARPRODUTO($B$5:$C$5;B11:C11)
=SOMARPRODUTO($B$5:$C$5;B12:C12)
=SOMARPRODUTO($B$5:$C$5;B13:C13)
As células B5 e C5 devem permanecer vazias e serão “preenchidas” automaticamente com a solução do problema ao ser implementado o Solver do Excel.
b) Para instalar o aplicativo Solver, proceder da seguinte forma:
Clicar em “arquivo” e, então, em “suplementos”:
Selecionar o aplicativo “Solver”, clicar em “ir”:
Selecionar, novamente, “Solver” e “ok”:
C) Resolvendo um problema de P.L. com o Solver:
Abrir o Solver:
- Entrar com a célula da função objetivo no campo “Definir Objetivo”.
- Selecionar o tipo de função objetivo: “Max” ou “Min”.
- Entrar com as células das variáveis de decisão no campo “Alterando Células Variáveis”.
- Entrar com as restrições no campo “Sujeito às Restrições” através do comando “Adicionar”. Observe bem os sinais das restrições.
- Selecionar o método “LP Simplex”.
- Clicar em “Resolver”.
- Selecionar os relatórios “Resposta” e “Sensibilidade”.
Cada célula preenchida automaticamente pelo Solver será devidamente explicada nos relatórios de resposta, sensibilidade e limites a seguir.
3- Análise dos relatórios do Solver:
3.1 – Relatório de Respostas:
O valor final da função objetivo (neste caso é de maximização) é obtido através da célula de destino. Os valores ótimos a serem produzidos para cada variável de decisão estão representados nas células ajustáveis. Nas células de restrições estão os valores de cada restrição, se estas foram atingidas ou se está sobrando algo (transigência), que é o que está acontecendo com a restrição “b”.
3.2- Relatório de Sensibilidade:
Este relatório analisa como podem variar as constantes do problema, ou seja, os coeficientes da função objetivo e o lado direito das restrições, sem que a solução ótima sofra alterações substanciais. Esta análise baseia-se na teoria do método simplex (que será visto mais tarde...).
No primeiro quadro (células ajustáveis) analisam-se os coeficientes da função objetivo. Analisando, por exemplo, o coeficiente da variável X1, conclui-se que ela pode variar de (4 – 2) até (4 + ∞) sem que haja alteração da solução ótima, ou seja, sem que a solução ótima mude de vértice da região viável. 
No segundo quadro (células restrições) é feita uma análise no lado direito das restrições. Ao alterar um desses valores estamos alterando uma restrição e conseqüentemente a região ótima do problema inicial. Isto pode afetar no sentido que a solução ótima mude de um vértice para outro. Os valores nas colunas “permissível acréscimo” e “permissível decréscimo”, são, respectivamente, os valores que podemos aumentar ou diminuir no lado direito das restrições sem que a solução ótima mude de vértice. 
Finalmente, a coluna “Preço Sombra”, dá exatamente o acréscimo na função objetivo por cada unidade adicional no lado direito das restrições. Por exemplo, se tivéssemos (5 + 1 = 6) na restrição “a” teríamos mais 2 unidades na função objetivo.
4- Resolução do problema de transporte utilizando o Solver:
4.1- Problema da fábrica de bicicletas:
A Vainamaha é uma fábrica de bicicletas que possui três fábricas localizadas no Rio de Janeiro, em São Paulo e em Belo Horizonte. A produção da empresa deve ser entregue e Recife, Salvador e Manaus. Considerando os custos de transporte unitários, a capacidade de produção das fábricas e a demanda dos centros consumidores da tabela abaixo, faça a modelagem matemática do problema afim de calcular o quanto deve ser produzido e entregue por fábrica em cada centro consumidor, de forma a minimizar os custos de transporte.
	Fábrica
	Centro Consumidor
	Oferta ai
	
	Recife (1)
	Salvador (2)
	Manaus (3)
	
	Rio de Janeiro (1)
	25
	20
	30
	2000
	São Paulo (2)
	30
	25
	25
	3000
	B. Horizonte (3)
	20
	15
	23
	1500
	Demanda bj
	2000
	2000
	1000
	
4.2 Programação Linear - Modelagem:
Variáveis: Xij = quantidade a ser transportada da fábrica i até o endereço j, com i = 1, 2 , 3 e j = 1, 2,3.
4.3 Programação no Solver:Função Objetivo
	Célula
	Fórmula
	
	C20
	=SOMARPRODUTO(C5:E7;C13:E15)
	Restrições
	Célula
	Lado Direito da Restrição (LHS)
	
X11+X12+X13 ≤ 2000
	F13
	=SOMA(C13:E13)
	
X21+X22+X23 ≤ 3000
	F14
	=SOMA(C14:E14)
	
X31+X32+X33 ≤ 1500
	F15
	=SOMA(C15:E15)
	
X11+X21+X31 = 2000
	C16
	=SOMA(C13:C15)
	
X12+X22+X32 = 2000
	D16
	=SOMA(D13:D15)
	
X13+X23+X33 = 1000
	E16
	=SOMA(E13:E15)
4.4 Solução do Solver:
4.5 Relatórios (Análise de Sensibilidade):
Referencia para este material:
Pesquisa Operacional na Tomada de Decisões – 4ª edição
Gerson Lachtermacher
Pearson
Pesquisa Operacional Para Decisão em Contabilidade e Administração – 2ª edição
Luiz Corrar e Carlos Renato Theóphilo
Atlas
� EMBED Microsoft Equation 3.0 ���
�PAGE �
�PAGE �2�
_1424082992.unknown
_1518850159.unknown
_1518850558.unknown
_1518851599.unknown
_1518850539.unknown
_1424083196.unknown
_1424083216.unknown
_1424082243.unknown
_1424082883.unknown
_201882360.unknown