Exercícios de Transporte designação Resolvido-2023 1

UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 1 EXERCÍCIOS DE TRANSPORTE / DESIGNAÇÃO 1) Verifique a validade/viabilidade da solução de um problema de transporte. Se a solução não for válida/viável gere uma que seja sem alterar os valores já transportados (em parênteses) a partir da solução inicial dada. Utilize os métodos u-v e stepping stone para determinar a solução ótima. Κ1 Κ2 Κ3 Κ4 Κ5 Oferta L1 3 (100) 2 3 4 1 100 L2 4 1 (60) 2 (40) 4 (25) 2 125 L3 1 0 5 3 (50) 2 (25) 75 Demanda 100 60 40 75 25 Κ1 Κ2 Κ3 Κ4 Κ5 Oferta L1 3 (100) 2 3 4 1 100 L2 4 (0) 1 (60) 2 (40) 4 (25) 2 125 L3 1 0 5 3 (50) 2 (25) 75 Demanda 100 60 40 75 25 3 (100) 2 (2) 3 (2) 4 (1) 1 (-1) U1=-1 100 4 (0) 1 (60) 2 (40) 4 (25) 2 (-1) U2=0 0-T 60 40 25+T 1 (-2) 0 (0) 5 (4) 3 (50) 2 (25) U3=-1 +T 50-T 25 V1=4 V2=1 V3=2 V4=4 V5=3 T=0 3 (100) 2 (0) 3 (0) 4 (-1) 1 (-3) U1=1 100-T +T 4 (2) 1 (60) 2 (40) 4 (25) 2 (-1) U2=0 60 40 25 1 (0) 0 (0) 5 (4) 3 (50) 2 (25) U3=-1 0+T 50 25-T V1=2 V2=1 V3=2 V4=4 V5=3 T=25 3 (75) 2 (0) 3 (0) 4 (-1) 1 (25) U1=1 75-T +T 25 4 (2) 1 (60) 2 (40) 4 (25) 2 (2) U2=0 60 40 25 1 (25) 0 (0) 5 (4) 3 (50) 2 (3) U3=-1 25+T 50-T V1=2 V2=1 V3=2 V4=4 V5=0 T=50 3 (25) 2 (1) 3 (1) 4 (50) 1 (25) U1=0 25 50 25 4 (1) 1 (60) 2 (40) 4 (25) 2 (1) U2=0 60 40 25 1 (75) 0 (1) 5 (5) 3 (1) 2 (3) U3=-2 75 V1=3 V2=1 V3=2 V4=4 V5=1 2) Considere a solução parcial do problema de transporte. 1 2 3 4 Suprimento A 8 (3) 9 10 11 (2) 5 B 11 12 11 14 (5) 5 C 7 11 14 (6) 8 6 D 12 13 (5) 12 12 5 E 9 (4) 10 (1) 9 10 5 7 6 6 7  Demanda UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 2 i) Inclua de forma apropriada uma variável para completar a solução básica. Se incluir de forma errada não consegue encontrar a solução ótima. Justifique a escolha. ii) Determine a solução ótima do problema a partir do item i) para minimizar o custo total. Mostre todos os procedimentos e cálculos utilizados. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 3 3) Três Técnicos devem ser designados para trabalhar em seis setores. Cada Técnico deve trabalhar em dois setores, e cada um classificou os seis períodos de tempo durante os quais os trabalhos são executados, conforme tabela. Uma classificação de 10 significa que o Técnico deseja trabalhar naquele instante de tempo, e uma classificação de 1 significa que ele não quer trabalhar naquele momento. Determine uma designação dos Técnicos para os setores que irão maximizar a satisfação total dos Técnicos. Técnico 09:00 10:00 11:00 13:00 14:00 15:00 1 8 7 6 5 7 6 2 9 9 8 8 4 4 3 7 6 9 6 9 9 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 4 Solução ótima (min): Solução ótima (max): 0 (1) 1 2 3 1 (1) 2 8 (1) 7 6 5 7 (1) 6 0 0 (1) 1 1 (1) 5 5 9 9 (1) 8 8 (1) 4 4 2 3 0 (1) 3 0 0 (1) 7 6 9 (1) 6 9 9 (1) Satisfação máxima = 8*1 + 7*1 + 9*1 + 8*1 + 9*1 + 9*1 = 50 (Obs: A questão pode ser resolvida como problema de Designação, duplicando cada um dos técnicos) 4) Uma empresa quer planejar a produção agregada para os próximos 6 meses. As encomendas previstas estão listados na tabela. Ao longo do período de 6 meses, as unidades podem ser produzidas em um mês e estocadas/armazenadas para satisfazer a procura de meses mais tarde. Devido a fatores sazonais, o custo de produção não é constante, como mostrado na tabela. O custo de manter um item estocado por 1 mês é $ 4/unidade/mês. Itens produzidos e vendidos no mesmo mês não são colocados no estoque. O número máximo de unidades que podem ser mantidos em estoque é 250. O nível de estoque inicial no início do horizonte de planejamento é de 200 unidades; o nível estocado no fim do horizonte de planejamento deve ser 100. O problema é determinar a quantidade ideal para produzir em cada mês de modo que a demanda seja atendida enquanto minimiza o custo total de produção e de estocagem. Escassez não é permitida. Mês Demanda (unidades ) Custo da Produção ($/unid) 1 1300 100 2 1400 105 3 1000 110 4 800 115 5 1700 110 6 1900 110 Resolva o problema como um problema de transporte. Problema de Transporte com Transbordo E2 E3 E4 E5 E6 1 2 3 4 5 6 Oferta P 100 105 110 115 110 100 105 110 115 110 110 8000 E2 0 inf inf inf inf inf 4 inf inf inf inf 250 E3 inf 0 inf inf inf inf inf 4 inf inf inf 250 E4 inf inf 0 inf inf inf inf inf 4 inf inf 250 E5 inf inf inf 0 inf inf inf inf inf 4 inf 250 E6 inf inf inf inf 0 inf inf inf inf inf 4 250 Demanda 250 250 250 250 250 1100 1400 1000 800 1700 2000 Transformar em minimização: 9h 10h 11h 13h 14h 15h Oferta T1 0 1 2 3 1 2 2 T2 0 0 1 1 5 5 2 T3 2 3 0 3 0 0 2 Demanda 1 1 1 1 1 1 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 5 Solução Ótima: 100 (250) 105 (250) 110 (250) 115 110 100 (1100) 105 (1150) 110 (750) 115 (550) 110 (1700) 110 (2000) 0 999 999 999 999 999 4 (250) 999 999 999 999 999 0 999 999 999 999 999 4 (250) 999 999 999 999 999 0 999 999 999 999 999 4 (250) 999 999 999 999 999 0 (250) 999 999 999 999 999 4 (d) 999 999 999 999 999 0 (250) 999 999 999 999 999 4 (d) Custo mínimo = 100*(250+1100) + 105*(250+1150) + 110*(750+250) + 115*550 + 110*1700 + 110*2000 + 4*(250+250+250+0+0) Custo mínimo = $ 865.250 5) A Propenso produz balanços em dois locais: em M e em D. A fábrica de M pode produzir até 170 balanços por dia, e a fábrica em D pode produzir 210 balanços por dia. Os balanços são enviados por via aérea para clientes em L e em B. Os clientes em cada cidade requerem 140 balanços por dia. A Propenso acredita que pode ser mais barato primeiro enviar alguns balanços para N ou para C e depois levá-los aos seus destinos finais. Os custos de enviar um balanço são mostrados na tabela. Propenso deseja minimizar o custo total de envio dos balanços necessários para seus clientes. Para De N C L B M 8 13 25 28 D 15 12 26 25 N 0 6 16 17 C 6 0 14 16 M e D são pontos de abastecimento, com suprimentos de 170 e 210 balanços por dia, respectivamente. N e C são pontos de transbordo. L e B são pontos de demanda, cada um com uma demanda de 140 balanços por dia. De N C L B DF Oferta M 8 13 25 28 0 170 D 15 12 26 25 0 210 N 0 6 16 17 0 380 C 6 0 14 16 0 380 Demanda 380 380 140 140 100 Solução Ótima: 8 (140) 13 25 28 0 (30) 15 12 26 25 (140) 0 (70) 0 (240) 6 (d) 16 (140) 17 0 6 0 (380) 14 16 0 Custo mínimo = 8*140 + 16*140 + 25*140 = 6.860 6) Uma companhia faz esquis em 3 fábricas através do mundo. As fábricas suprem 4 depósitos que distribuem os esquis diretamente às lojas. O problema é achar quantos pares de esquis devem ser transportados de cada fábrica para os vários depósitos para minimizar o custo total UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 6 a) Ache a solução inicial pelo método do Canto Noroeste b) Ache a solução inicial pelo método do Custo Mínimo c) Ache a solução inicial pelo método de Vogel d) Ache a solução do problema pelo método u-v a) Canto Noroeste 19 (100) 17 3 21 15 (50) 21 (100) 18 (150) 6 11 14 15 (50) 22 (150) Custo inicial = 19*100 + 15*50 + 21*100 + 18*150 + 15*50 + 22*150 Custo inicial = 11.500 b) Custo Mínimo 19 17 3 (100) 21 15 21 (50) 18 (100) 6 (150) 11 (150) 14 (50) 15 22 Custo inicial = 3*100 + 21*50 + 18*100 + 6*150 + 11*150 + 14*50 Custo inicial = 6.400 c) Vogel 19 17 3 (100) 21 15 (50) 21 18 (100) 6 (150) 11 (100) 14 (100) 15 22 Custo inicial = 3*100 + 15*50 + 18*100 + 6*150 + 11*100 + 14*100 Custo inicial = 6.250 d) Solução: 19 17 3 (100) 21 15 (50) 21 18 (100) 6 (150) 11 (100) 14 (100) 15 22 Custo mínimo = 3*100 + 15*50 + 18*100 + 6*150 + 11*100 + 14*100 Custo mínimo = 6.250 7) Uma companhia locadora de automóveis se defronta com um problema de alocação resultante dos contratos de locação que permitem que os automóveis sejam devolvidos em localidades outras que aquelas onde foram originalmente alugados. Atualmente há 2 agências de locação com, respectivamente, 15 e 13 carros excedentes e 4 outras agências necessitando de 9, 6, 7 e 9 carros, respectivamente. Os custos unitários de transporte entre as locadoras são os apresentados no quadro abaixo. Determine um plano de transporte ótimo que minimize o custo de transporte. L Dest 1 L Dest 2 L Dest 3 L Dest 4 Oferta L Or 1 45 17 21 30 15 L Or 2 14 18 19 31 13 Fictício 0 0 0 0 3 Demanda 9 6 7 9 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 7 Solução Ótima: 45 17 (6) 21 (3) 30 (6) 14 (9) 18 19 (4) 31 0 0 0 0 (3) Custo mínimo = 17×6 + 21×3 + 30×6 + 14×9 + 19×4 + 0×3= 547 8) O Expresso Rápido Faxina é uma empresa de transporte com quatro grandes terminais localizados em Curitiba, Cascavel, Londrina e Campo Mourão. Os pneus utilizados pela frota dessa empresa são padronizados. A empresa fez uma tomada de preços em três grandes revendedores de pneus e obteve as seguintes cotações: Se o objetivo da empresa Expresso Rápido Faxina é minimizar o custo total de aquisição dos pneus, quanto ela deverá comprar de cada revendedor? Ache a solução inicial pelo método de Vogel. A B C Demanda Curitiba 70 64 68 4000 Londrina 74 62 65 8000 Cascavel 62 68 64 3000 Campo Mourão 62 72 66 5000 Fictício 0 0 0 2000 Oferta 12000 6000 4000 Solução Ótima: 70 (2000) 64 (2000) 68 74 62 (4000) 65 (4000) 62 (3000) 68 64 62 (5000) 72 66 0 (2000) 0 0 Custo mínimo = 70×2000 + 64×2000 + 62×4000 + 65×4000 + 62×3000 + 62×5000 + 0×2000 Custo mínimo = 1.272.000 9) Determinada empresa pretende transportar um certo produto, que é fabricado nas suas 3 fábricas, para 3 centros de distribuição. A capacidade de produção por dia de cada fábrica é a que consta na última coluna da tabela em baixo. A última linha da tabela dá-nos as necessidades máximas de cada centro de distribuição. Os custos de transporte, por unidade de produto, das fábricas para cada centro encontram-se mencionados na mesma tabela. Centro 1 Centro 2 Centro 3 Capacidade Fábrica 1 2 6 4 50 Fábrica 2 6 ---- 8 80 Fábrica 3 4 7 3 60 Necessidade Máx. 70 40 50 Pretende-se determinar a solução mais econômica para transportar o produto das fábricas para os centros de distribuição. Uma das soluções é a que consta no quadro seguinte: UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 8 Centro 1 Centro 2 Centro 3 Fábrica 1 10 40 0 Fábrica 2 50 0 0 Fábrica 3 10 0 50 a) Verifique, e justifique, se a solução apresentada é ou não é ótima. Não é ótima (verificar/justificar utilizando u-v) b) Se não for ótima, a partir da solução dada, determine a solução ótima. Solução ótima: 2 (20) 6 (30) 4 6 (50) 999 8 4 7 (10) 3 (50) c) Interprete os resultados obtidos e diga qual o custo total de transporte. Custo total = 2×20 + 6×30 + 6×50 + 7×10 + 3×50 = 740 10) O Xoping aposta na segurança. Para isso dispõe de seguranças privados colocados em pontos estratégicos dentro do Xoping de modo a, ao serem vistos, inibirem o furto e controlarem a maior área possível. No setor térreo foram determinadas 6 localizações possíveis para os seguranças. No entanto, é claro para o responsável pela segurança, de que o Patolino, o Zezão, o Botas e o Galhardo são suficientes para vigiar o setor térreo. Dadas as características dos seguranças mencionados (peso, força, agilidade, etc.) e dos locais de vigilância, o responsável pela segurança construiu um índice (consta na tabela) que indica o proveito/benefício de um dado segurança estar “parado" num dado local (quanto mais vantajoso alocar um segurança a um determinado local, maior o índice): Local No entanto, após uma inspeção aos locais, o responsável decidiu que o Patolino não poderia ficar no local A nem no local B, por serem adjacentes a lojas de bebidas. Determine quais locais devem ser ocupados e por quais seguranças. A B C D E F Patolino 5 6 4 4 6 2 Zezão 4 1 5 3 5 2 Botas 3 4 2 3 1 3 Galhardo 5 2 1 4 6 4 maximização A B C D E F Patolino 5 6 4 4 6 2 Zezão 4 1 5 3 5 2 Botas 3 4 2 3 1 3 Galhardo 5 2 1 4 6 4 minimização A B C D E F min Patolino inf inf 2 2 0 4 0 Zezão 2 5 1 3 1 4 1 Botas 3 2 4 3 5 3 2 Galhardo 1 4 5 2 0 2 0 Ficticio1 0 0 0 0 0 0 0 Ficticio2 0 0 0 0 0 0 0 * UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 9 * inf inf 2 2 0 4 1 4 0 2 0 3 1 0 2 1 3 1 * 1 4 5 2 0 2 0 0 0 0 0 0 0 0 0 0 0 0 mínimo: 1 inf inf 1 1 0 3 1 4 0 2 1 3 1 0 2 1 4 1 0 3 4 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 Solução ótima: Patolino em E; Zezão em C; Botas em B e Galhardo em A = 6 + 5 + 4 + 5 = 20 11) Executou-se algumas iterações do Algoritmo Húngaro num problema de designação de maximização, e chegou-se à seguinte matriz: I II III IV V A 0 15 0 0 0 B 0 0 20 5 0 C 5 20 5 5 0 D 20 5 5 20 0 E 10 15 10 15 0 Determine a solução ótima via Algoritmo Húngaro. Mostre todos os procedimentos. 12) Considere o problema de atribuir equipes (A,B,C,D,E) a serviços com a seguinte matriz de custos (minimização) 1 2 3 4 5 A 7 7 7 8 7 B 10 12 6 2 12 C 14 9 6 5 11 D 1 12 15 7 5 E 3 12 11 6 11 Realize uma redução gerando zeros por LINHA de modo que todas as linhas contenham pelo menos um zero e que os demais “custos alterados” sejam não negativos. A partir desta nova matriz de “custos alterados”, determine a solução ótima via algoritmo Húngaro. Mostre todos os procedimentos e cálculos utilizados na resolução. UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 10 13) Cinco colaboradores (A, B, C, D, E) estão disponíveis para operar cinco tratores (1, 2, 3, 4, 5) e os respectivos custos para cada combinação colaborador-trator é dado na tabela. Um sexto trator está disponível para substituir um dos tratores existentes e os custos associados são dados na última coluna da tabela. Determine: i) se o novo trator será aproveitado; ii) a designação ótima e seu custo total considerando o trator 6; iii) se houver ganhos no custo, em quanto diminui o custo com o novo trator. 1 2 3 4 5 6 A 4 0  -- 1 0  7 B 0  -- 3 -- 10 1 C 1 3 6 6 0 4 D 3 5 0  1 2 -- E -- 1 0  4 5 0  Fictício 0  0  1 0  2 0  i) O novo trator será aproveitado pelo colaborador E ii) Designação ótima: A – 2; B – 1; C – 5; D – 3; E – 6 Custo = 16 + 14 + 13 + 17 + 16 = 76 iii) Diminui em 1 14) Quatro diferentes trabalhos podem ser feitos em quatro máquinas diferentes. A matriz abaixo indica os custos de se fazer o trabalho i na máquina j: 1 2 3 4 5 6 A 20 16 -- 17 14 23 B 14 -- 16 -- 22 15 C 16 18 20 21 13 19 D 21 23 17 19 18 -- E -- 17 15 20 19 16 UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 11 Machines 𝑴𝟏 𝑴𝟐 𝑴𝟑 𝑴𝟒 Trabalhos 𝑱𝟏 5 7 11 6 𝑱𝟐 8 5 9 6 𝑱𝟑 4 7 10 7 𝑱𝟒 10 4 8 3 Como os trabalhos devem ser designados às máquinas para que o custo total seja mínimo? 𝑴𝟏 𝑴𝟐 𝑴𝟑 𝑴𝟒 𝑱𝟏 0  0  0  0  𝑱𝟐 5 0  0  2 𝑱𝟑 0  1 0  2 𝑱𝟒 8 0  0  0  Custo mínimo = Rs. 23 15) Uma empresa tem um caminhão excedente em cada uma das cidades A, B, C, D e E e um caminhão faltante em cada uma das cidades 1, 2, 3, 4, 5 e 6. A distância entre as cidades em quilômetros é mostrada na matriz abaixo. Encontre a alocação de caminhões de cidades com extras para cidades com déficit de modo que a distância total percorrida pelos veículos seja mínima. 1 2 3 4 5 6 A 12 10 15 22 18 8 B 10 18 25 15 16 12 C 11 10 3 8 5 9 D 6 14 10 13 13 12 E 8 12 11 7 13 10 1 2 3 4 5 6 A 6 0  5 12 8 0  B 0  4 11 1 2 0  C 12 7 0  5 2 8 D 0  4 0  3 3 4 E 5 5 4 0  6 5 Fictício 4 0  0  0  0  2 Distância mínima = 38 km UNIVERSIDADE FEDERAL DO PARANÁ – DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO TECNOLOGIA DA DECISÃO II - PROF. VOLMIR EUGÊNIO WILHELM 12 16) Uma rede de fast-food quer construir quatro lojas. No passado, a rede já contratou seis construtoras diferentes e, satisfeita com cada uma delas, convidou-as a licitar cada obra. Os lances finais (em milhares de rúpias) são mostrados na tabela a seguir: Construtoras 1 2 3 4 5 6 Lojas 1 85.3 90 87.5 82.4 89.1 91.3 2 78.9 84.5 99.4 80.4 89.3 88.4 3 82 31.3 28.5 66.5 80.4 109.7 4 84.3 34.6 86.2 83.3 85 85.5 Como a rede de fast-food deseja ter cada uma das novas lojas prontas o mais rápido possível, ela destinará no máximo um trabalho a uma construtora. Qual atribuição resultará no custo total mínimo? 1 2 3 4 5 6 1 29 76 51 0  67 89 2 0  56 205 15 104 95 3 535 28 0  380 519 812 4 497 0  516 487 504 509 𝑫𝟏 0  0  0  0  0  0  𝑫𝟐 0  0  0  0  0  0  Custo mínimo = R$ 224,400 17) A Xan Consulting deseja determinar a melhor distribuição de trabalho para seus três principais consultores. O objetivo é obter a distribuição que estabeleça o menor tempo total para a execução das tarefas. Os tempos que cada consultor levaria para cada tarefa são: Ajude Xan a determinar a melhor solução. ABC PQR XYZ Luiz A 0  0  3 Geraldo 0  4 0  Agivaldo 0  2 0  Menor tempo = 15 + 9 + 3 = 27