TRANSPORTES, - silabo.pt

1 INVESTIGA OOPERACIONALMANUELA MAGALH ES HILL licenciou-se em Matem tica Aplicada pela Faculdade de Ci ncias de Lisboa,frequentou o curso de p s-gradua o em Matem tica Aplicada Investiga o Operacional da Funda oCalouste Gulbenkian e, em 1987, doutorou-se em Economia (Universidade de Keele, R. U.). Actualmente Professora Catedr tica no Departamento de M todos Quantitativos do ISCTE onde coordena o mestrado emProspec o e An lise de Dados e lecciona nas licenciaturas e mestrados em Gest o de Empresas eEconomia. Tem coordenado e participado em v rios projectos de investiga o na especializa o de m todosestat sticos e econom tricos aplicados s Ci ncias Sociais. De 1972 a 1988 acumulou as fun es docentescom as de t cnica no Gabinete de Estudos e Planeamento do Minist rio da Educa MARQUES DOS SANTOS BELMAR DA COSTA licenciada em Gest o de Empresas pelaUniversidade Cat lica Portuguesa e det m um MBA pelo INSEAD (Fontainebleau), tendo tamb m frequen-tado o mesmo programa em Kellogg Northwestern University, em Chicago.

2 De 1989 a 2006, afecta aoDepartamento de M todos Quantitativos, foi docente universit ria no ISCTE. A par das actividadesacad micas, desenvolveu uma carreira empresarial ligada a diversas reas e fun es. Come ando porcolaborar com uma institui o financeira internacional na rea de gest o de carteiras de t tulos, ingressoudepois numa equipa de capital de risco, onde foi analista de projectos, noutra institui o financeira tamb m consultora em Madrid, numa empresa multinacional, estando associada a diversos projectosentre os quais o lan amento da sucursal portuguesa. Assumiu de seguida uma sucess o de pelourosinternacionais, dentro de um grupo de empresas na rea da constru o e engenharia civil, nomeadamenteem Mo ambique e na Alemanha, gerindo projectos em diversas reas como a alimentar ou a produ o edistribui o de materiais de constru o.

3 Finalmente, iniciou um projecto empresarial pr prio na rea docom rcio internacional de medicamentos, ao qual se dedica L BANO MONTEIRO licenciada em Matem tica Aplicada pela Faculdade de Ci ncias da Universi-dade de Lisboa, com especializa o no ramo da Estat stica e Investiga o Operacional, fez um est gioprofissionalizante na Quimigal sob o tema da Gest o de Stocks, e possui um mestrado em Investiga oOperacional, com tese na rea do. Foi at 2007 docente universit ria no ISCTE,leccionando as disciplinas de Matem tica, Estat stica e Investiga o Operacional nas licenciaturas deGest o de Empresas e Gest o e Engenharia Industrial. Actualmente dirige uma Institui o Particular deSolidariedade and SchedulingCom aplicabilidade muito variada na vida real, os temas abordados nestelivro d o ao leitor uma oportunidade para diversificar os seus conheci-mentos de Investiga o Operacional.

4 Semelhan a dos volumes anteriores,procura-se abordar os v rios temas de uma forma simples e pratica,permitindo assim uma apreens o mais f cil dos mesmos. Para comple-mentar a explica o te rica, al m dos exemplos ilustrativos, s o tamb mapresentados e resolvidos v rios exerc cios que permitir o um estudomais completo e 1 Programa o LinearVol. 2 Exerc cios de Programa o LinearVol. 3 Transportes, Afecta o e Optimiza o em redesINVESTIGA O OPERACIONALINVESTIGA OOPERACIONALTRANSPORTES, AFECTA OE OPTIMIZA O DE REDESTRANSPORTES,AFECTA OE OPTIMIZA ODE Magalh es HillMariana Marques dos SantosAna L bano MonteiroEDI ES S 1881629 ISBN 978-972-618-816-2 INVESTIGA O OPERACIONALVol. 1 Programa o LinearVol. 2 Exerc cios de Programa o LinearVol. 3 Transportes, Afecta o e Optimiza o em redesINVESTIGA OOPERACIONALT ransportes, Afecta oe Optimiza o em redesManuela Magalh es HillMariana Marques dos SantosAna L bano Monteiro2 Edi oRevista e CorrigidaEDI ES S LABO expressamente proibido reproduzir, no todo ou em parte, sob qualquermeio ou forma, nomeadamenteFOTOC PIA, esta obra.

5 As transgress esser o pass veis das penaliza es previstas na legisla o em T CNICAT tulo: Investiga o Operacional Vol. 3 Transportes, Afecta o e Optimiza o em RedesAutoras: Manuela Magalh es Hill, Mariana Marques dos Santos, Ana L bano Monteiro@ Edi es S labo, : Pedro Mota1 Edi o Lisboa, Setembro de Edi o Lisboa, Setembro de o e acabamentos: Europress, sito legal: 297699/09 ISBN: 978-972-618-816-2 EDI ES S LABO, LDAR. Cidade de Manchester, 21170-100 LISBOATelf.: 218130345 Fax: 218166719e-mail: NDICEPREF CIO9 Cap tulo 1O problema de transportes1. Introdu o132. Formula o de um problema de A formula o gen Arranjos da formula o gen Considera es importantes213. A resolu o de problemas de Introdu Determina o de uma base inicial admiss Teste de Melhoria da solu o interm dia414. Caso pr tico de problemas de O Formula Problema Resolu o do Interpreta o da solu o ptima e do quadro finalde resolu o do problema de transportes665.

6 Casos especiais em problemas de Solu es Solu es m ltiplas736. An lise de sensibilidade em problemas de altera es nos coeficientes da fun o Altera es nas restri es837. Problema de transexpedi o918. Exerc cio final de O Formula o do Resolu o do problema106 Cap tulo 2 Exerc cios sobre transportes125 EXERC CIOS PROPOSTOS185 Cap tulo 3O problema de afecta o1. Introdu o1972. Formula o de um problema de afecta A formula o gen Arranjos da formula o gen Considera es importantes2053. A resolu o de problemas de afecta introdu O m todo H ngaro2094 Casos pr ticos de problemas de afecta Um caso de solu o m Um caso de afecta es Um caso de maximiza Um caso de valores negativos e fraccion Um caso de afecta o generalizada2365. An lise de sensibilidade em problemas de afecta o242 Cap tulo 4 Exerc cios sobre afecta o251 EXERC CIOS PROPOSTOS270 Cap tulo 5 Optimiza o em redes1.

7 Introdu o2752. Alguns conceitos da teoria dos Defini o de A no o de rede2853. rvore geradora (ou de suporte) de custo m Algoritmo de Algoritmo de Algumas considera es finais2994. O problema do caminho mais Algoritmo de Algoritmo de Algoritmo de Floyd3195. O problema do fluxo m Corte de uma Algoritmo de Casos especiais do problema do fluxo m ximo3346. O problema do fluxo de custo m Algoritmo de Formula o de outros problemascomo problemas de fluxo de custo m nimo342 Cap tulo 6 Exerc cios sobre optimiza o em redesEXERC CIOS PROPOSTOS418 ANEXO DOS ALGORITMOS421 BIBLIOGRAFIA431 PREF CIOCom a publica o deste terceiro volume de Investiga o Operacional,damos por conclu da a nossa inten o de apresenta o de uma vis o pr ticade um conjunto de t cnicas de optimiza o n o abordadas nos dois volumesanteriores transportes, afecta oeoptimiza o em redesas quais, aolongo dos anos, t m obtido um crescente reconhecimento por parte parecendo problemas de aplica o restrita na vida real, cada umdeles tem a versatilidade de ser adapt vel a situa es diferentes das descri-tas.

8 Por essa raz o, encontram-se dentro do conjunto de problemas maisconhecidos em Investiga o Operacional e, como tal, alvo da nossa aten obra mant m subjacente a mesma filosofia das obras modo foi dado especial nfase formula o de problemas, interpre-ta o econ mica da solu o ptima e an lise subsequente obten odessa solu o, aspecto este normalmente n o abordado em problemas detransporte e de afecta perspectiva de que este livro tenha grande valor pr tico, foi destinado,para cada um dos temas, um cap tulo s com exerc cios resolvidos e propos-tos para ajudar o leitor na melhor apreens o dos amos de deixar uma palavra de agradecimento s colegas daequipa de Investiga o Operacional do ISCTE pelo apoio e inspira o quenos deram. Contudo, quaisquer erros que o leitor possa encontrar s o inteira-mente da nossa autoras1O problemade transportesINTRODU OO problema de transportes um dos casos particulares de programa olinear que, pela sua import ncia e frequ ncia de utiliza o, se imp e serestudado de forma aprofundada.

9 Para al m disso, mesmo podendo recorrerao algoritmo do Simplex, foi desenvolvido um algoritmo espec fico para aresolu o de problemas deste tipo, que vem facilitar sobremaneira a procurada solu o ptima. A situa oSempre que nos encontramos perante um produto homog neo, oferecidopor um conjunto decentros de ofertaouorigense procurado por um outroconjunto decentros de procuraoudestinos, estamos perante um problemade transportes, desde que: se pretenda transportar o produto mencionado, dos centros de ofertapara os centros de procura; seja nosso objectivo encontrar a forma mais barata ou mais r pida de forma a melhor visualizar o tipo de problema que queremos apresen-tar neste cap tulo, vejamos o seguinte exemplo:Uma sociedade que det m 4 padarias pretende distribuir o p o que fabricadiariamente por 6 pastelarias tamb m por si exploradas. As 4 padarias t mcapacidade para produzir diariamente 300, 400, 400 e 500 p es respectiva-mente.

10 Por outro lado, o consumo de p o nas pastelarias estima-se em 250,360, 280, 200, 250 e 200 por dia, em cada uma, respectivamente. Os custos detransporte por unidade, de cada uma das padarias para cada uma das pastela-rias, s o os constantes do quadro que se segue:13O PROBLEMA DE TRANSPORTESP astelariasP1P2P3P4P5P6 Oferta totalPadariasO1325113300O2224325400O3542 451400O4343432500 Procura total250360280200250200 Este um problema t pico de transportes, em que se pretende determinarqual a melhor forma de distribuir p o, desde os quatro pontos de oferta (aspadarias) at aos seis centros de procura (as pastelarias). O objectivo queassiste procura do melhor plano de distribui o ser a minimiza o doscustos de transporte. As limita es do problema dizem respeito, quer m xima quantidade de p o que cada padaria consegue oferecer quer aoconsumo m nimo de cada de passarmos formula o do problema podemos represent -lo numdiagrama simples, designado por rede (Figura ), colocando as padarias numacoluna ( esquerda) e as pastelarias noutra coluna ( direita) e lig -las com setas,colocando junto de cada seta o custo unit rio de transporte que lhe est asso-ciado.