Source: http://docplayer.es/1719604-F-u-n-i-v-e-e-s-i-i-a-t-de-vales-registre-genera-e-n-t-r-a-o-a-t-5-abr-2005-n-2-_-hora-oficina-auxiliar-nu-x.html
Timestamp: 2016-12-08 19:04:08+00:00

Document:
⭐^ f \ U N I V E E S í I A T DE VALES! REGISTRE GENERA E N T R A O A [ ~ T 5 ABR. 2005! N.2..._... HORA... OFICINA AUXILIAR NU?X
^ f \ U N I V E E S í I A T DE VALES! REGISTRE GENERA E N T R A O A [ ~ T 5 ABR. 2005! N.2..._... HORA... OFICINA AUXILIAR NU?X
Download "^ f \ U N I V E E S í I A T DE VALES! REGISTRE GENERA E N T R A O A [ ~ T 5 ABR. 2005! N.2..._... HORA... OFICINA AUXILIAR NU?X"
María Mercedes Valverde Carrasco
1 2 3 UNIVERSITAT DE VALENCIA Departam ent d Estadística e Investigació Operativa ^ f \ U N I V E E S í I A T DE VALES! l REGISTRE GENERA E N T R A O A [ ~ T 5 ABR. 2005! N.2..._... HORA... OFICINA AUXILIAR NU?X El Problema General de Rutas con Viento (W indy General Routing Problem, W GRP) UNIVERSITAT DE VALÉNCIA BIBLIOTECA CIÉNCIES N R egistre DATA SIGNATURA 70--M N UBIS; L2..r.a.3.r.aS... M3 V i c^m, 1> O T S Tesis doctoral Isaac Plana Andani 20054 UMI Number: U All rights reserved INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted. In the unlikely event that the author did not send a com plete manuscript and there are missing pages, th ese will be noted. Also, if material had to be removed, a note will indicate the deletion. Disscrrlation Püblish< ng UMI U Published by ProQ uest LLC Copyright in the Dissertation held by the Author. Microform Edition ProQ uest LLC. All rights reserved. This work is protected against unauthorized copying undertitle 17, United States C ode. ProQuest LLC 789 East Eisenhower Parkway P.O. Box 1346 Ann Arbor, MI5 6 D. Angel Corberán Salvador, profesor titular del Departament d Estadística i Investigació Operativa de la Universitat de Valéncia, y D. José María Sanchis Llopis, profesor titular del Departamento de M atemática Aplicada de la Universidad Politécnica de Valencia CERTIFICAN: que la presente memoria de investigación E l P ro b le m a G e n e ra l de R u ta s con V ie n to ha sido realizada bajo su dirección por Isaac Plana Andani y constituye su tesis para optar al grado de Doctor en Ciencias Matemáticas. Y para que así conste, en cumplimiento de la normativa vigente, autorizan su presentación ante la Facultat de Matemátiques de la Universitat de Valéncia para que puedan ser tram itadas su lectura y defensa públicas. Burjassot, 14 de abril de 2005 Ángel Corberán Salvador José María Sanchis Llopis7 8 A Fani9 10 Agradecimientos En primer lugar, quiero dar las gracias al Ministerio de Ciencia y Tecnología y a la Generalitat Valenciana, que han financiado los proyectos Un sistema de ayuda a la tom a de decisiones en problemas de rutas de vehículos y localización de servicios (TIC Q-C06-01). y Un sistema de ayuda a la toma de decisiones en problemas de rutas de vehículos y localización de servicios 2 (TIC C05-01), y Soluciones avanzadas para problemas de rutas, distribución, transporte y otros (GRUPOS03/189), respectivamente, bajo los cuales se ha realizado la labor investigadora recogida en esta memoria. Muchas han sido las personas que, a lo largo de estos años, han contribuido de alguna manera a que esta tesis pudiera ser llevada a cabo. A todos ellos quiero dar las gracias, con mención especial a algunas personas que han sido clave en que esta travesía llegara a buen puerto: Toda la gente que durante este tiempo ha pasado por el Departamento de Estadística e Investigación Operativa, profesores y compañeros de doctorado. Gracias por la formación, el apoyo y la ayuda cuando fue necesaria. Gracias por todos los buenos momentos que hicieron más agradable las horas de trabajo. Mis directores Ángel Corberán y José María Sanchis, a quienes pertenece el mérito de, al menos, dos terceras partes de esta tesis. Gracias por todas las horas de trabajo. Gracias por vuestra amistad. Mis padres y mis hermanas, porque sin ellos no sería quien soy ahora ni hubiera llegado hasta aquí. Gracias por estar siempre ahí. Gracias por toda una vida. Y, finalmente, Fani. Compañera primero, amiga después y, ahora, esposa. E sta aventura del doctorado nos ha llevado mucho más lejos de lo que jamás habríamos imaginado y nos ha dado mucho más de lo que nunca hubiéramos soñado. Gracias por tu ayuda, por tu paciencia, por tu comprensión, por tu ánim o, Simplemente, gracias. ni11 12 índice general Introducción 1 1. P relim inares M atem áticos Teoría de G r a f o s Álgebra L i n e a l Teoría de Poliedros Teoría de la Complejidad A lg o rítm ic a Programación Lineal y E n te ra Combinatoria P o liéd rica A lgunos Problem as de R utas Problemas de Rutas por Vértices o A r c o s El Problema del Cartero C h in o El Problema del Cartero Chino en un Grafo No Dirigido ( C P P ) El Prob. del Cartero Chino en un Grafo Dirigido (DCPP) El Problema del Cartero Chino en un Grafo Mixto (M CPP) El Problema del Cartero Chino Con Viento (W PP) El Problema del Cartero R u r a l El Problema del Cartero Rural en un Grafo No Dirigido ( R P P ) El Prob. del Cartero Rural en un Grafo Dirigido (DRPP) El Problema del Cartero Rural en un Grafo Mixto (M RPP) El Problema del Cartero Rural con Viento ( W R P P ) El Problema General de R u t a s El Problema General de Rutas sobre un Grafo No Dirigido (G R P ) El Problema General de Rutas en un Grafo Mixto (MGRP) E l P roblem a G eneral de R utas con V iento Descripción del p r o b le m a D efinición Casos p a rtic u la re s Aplicaciones v13 VI ÍN D IC E G E N E R A L Soluciones del p ro b le m a Form ulación Simplificación Notación Formulación Lineal E n te ra El poliedro de soluciones Dimensión del poliedro Propiedades generales del p o lie d r o Desigualdades de configuración Desigualdades de configuración d é b il D escrip ció n del p o liedro I Desigualdades triviales y de obligatoriedad Desigualdades de conectividad Desigualdades de corte R -im pares D escrip ció n del p o liedro I I Desigualdades K-C e stá n d a r Desigualdades K-C Desigualdades Path-Bridge Desigualdades Path-Bridgeo Desigualdades Honeycom b Desigualdades Honeycombo D escrip ció n del p o lied ro I I I Desigualdades Zigzag p a r e s Desigualdades Zigzag im p a re s Relación de las nuevas facetas con otros problemas similares Las desigualdades Zigzag en el W P P Las desigualdades Zigzag en grafos no d irig id o s Las desigualdades Zigzag en grafos dirigidos Las desigualdades Zigzag en grafos m ix to s B ra n c h A n d C u t Problema lineal in ic ia l Cota superior in ic ia l Tailing-off R am ificació n Variaciones menos densas de algunas restricciones Desigualdades R-impares Desigualdades K-C y K-C Cota superior artificial y re in ic io Filtrado de restricciones de R -im paridad Algoritmos de separación Desigualdades de c o n e c tiv id a d Cortaduras R -im p a re s...13314 In d i c e g e n e r a l V II Desigualdades K - C Desigualdades Honeycom b Desigualdades K-C02 y Honeycombo Desigualdades P a th -B rid g e Desigualdades Zigzag R esultados com putacionales In sta n c ia s Instancias en grafos w indy Instancias en grafos m ix to s Instancias en grafos no dirigidos Características de las instancias Pruebas computacionales C onclusiones 17515 16 índice de figuras 3.1. Aplicaciones. Estructuras a inspeccionar Aplicaciones. Robot teledirigido Representación del problema como W R PP Ejemplo de construcción de un grafo de configuración Grafo de configuración. Desigualdades de corte R - im p a r Ejemplo de W GRP-tour. Cortes R -im p a re s Grafo de configuración asociado a las desigualdades K - C Tour de coste mínimo en el grafo de configuración K -C W GRP-tour 1 (K-C estándar) W GRP-tour 2 (K-C estándar) W GRP-tour 3 (K-C estándar) Grafo de configuración asociado a las desigualdades K-C Grafo de configuración. Desigualdades P ath -B rid g e Tour de coste mínimo en el grafo de configuración P ath Bridge Tour x x (P ath -B rid g e) W GRP-tour 1 (Path-Bridge) W GRP-tour 2 (Path-Bridge) W GRP-tour 3 (Path-Bridge) W GRP-tour 4 (Path-Bridge) W GRP-tour 5 (Path-Bridge) Grafo de configuración asociado a las desigualdades Path-Bridgeo W GRP-tour 1 (Path-Bridgeo2) Grafo de configuración asociado a una desigualdad Honeycomb Árbol T asociado al grafo configuración de la figura W GRP-tour 1 (Honeycomb) W GRP-tour 2 (Honeycomb) W GRP-tour 3 (Honeycomb) W GRP-tour 4 (Honeycomb) W GRP-tour 5 (Honeycomb) Grafo configuración asociado a las desigualdades Honeycombo Vector x d (Honeycombo2 ) W GRP-tour 1 tipo 4b (Honeycombo2 ) IX17 X ÍN D IC E D E F IG U R A S W GRP-tour 2 tipo 4b (Honeycombo2) W GRP-tour 3 tipo 4c (Honeycombo2 ) W GRP-tour 4 tipo 4c (Honeycombo2 ) W GRP-tour 5 tipo 4d (Honeycombo2 ) Instancia del W GRP con solución fraccionaria Solución fraccionaria Solución óptima Instancia del W GRP con solución fraccionaria Solución fraccionaria Solución óptima Grafo de configuración asociado a una desigualdad Zigzag par Vector x d, caso p a r Componentes seleccionadas, caso p a r W GRP-tour 1 (Zigzag p a r ) W GRP-tour 2 (Zigzag p a r ) W GRP-tour 3 (Zigzag p a r ) W GRP-tour 4 (Zigzag p a r ) Partición del grafo, desigualdades Zigzag im p a re s Conjuntos Tí, V y T Grafo de configuración asociado a una desigualdad Zigzag impar Vector x d, caso i m p a r Componentes seleccionadas, caso i m p a r W GRP-tours 1 (Zigzag impar) W GRP-tours 2 (Zigzag impar) W GRP-tours 3 (Zigzag i m p a r ) W GRP-tours 4 (Zigzag i m p a r ) W GRP-tours 5 (Zigzag i m p a r ) W GRP-tours 6 (Zigzag impar) Wheel en forma de Z ig zag Grafo de configuración para las Zigzag en el D R P P Instancia con Zigzag válida para F2 pero no F Solución fraccionaria (formulación F 2 ) Desigualdad Zigzag válida para F Desigualdad Zigzag no válida para F Solución fraccionaria (formulación F l) Zigzag para F l como combinación lin e a l Coeficientes modificados para K - C Coeficientes modificados para K-C Solución que viola una restricción de conectividad y grafo G* Grafo comprimido y cortadura de peso < Solución que viola una restricción K-C y grafo G* Elección de M q y M k Elección de M q y M k alternativa Compresión de M q, M k y componentes R -c o n e x a s...13818 ÍN D IC E D E F IG U R A S XI 7.9. Árbol generador de peso máximo en el grafo com prim ido Compresión de vértices hasta formar un camino entre M q y M k Configuración K-C que sí da lugar a una restricción K-C violada Configuración K-C que no da lugar a una restricción K-C violada Compresión de vértices para obtener una desigualdad K-C violada Solución que viola una HC y grafo G * Etiquetado de los vértices de VT Conjuntos B i,..., B l Árbol generador y compresión de vértices con grado Configuración HC con L=4, K=9, que da lugar a una desigualdad violada por x * Descomposición en b lo q u e s Solución x* que viola una desigualdad PB y grafo G * Elección de caminos candidatos y etiquetado de aristas débiles Candidatos para inicio de caminos Configuración 2-PB asociada a una de las componentes candidatasl Elección de A, y V? Grafo comprimido Gs Árbol en Ga y compresión de vértices Configuración PB regular asociada a una de las componentes cand id atas Grafo ejemplo y solución fraccionaria para la separación de Z Obtención de la cortadura que contenga el z ig z a g Cortadura con zigzag Cortadura sin z ig z a g Numeración de los vértices del zigzag Partición de los conjuntos Vi y V Partición final del g r a f o Coeficientes de la desigualdad Zigzag identificada...15519 20 Introducción El origen de los Problemas de Rutas por Arcos se atribuye al problema de los puentes de Konigsberg, resuelto por Euler en el siglo XVIII. Las diferentes partes en las que el río Pregel dividía la ciudad de Konigsberg estaban comunicadas por siete puentes. La cuestión que resolvió Euler fue si era posible cruzar los siete puentes de la ciudad recorriendo exactamente una vez cada uno de ellos y volver al punto de partida. Este problema puede plantearse como un Problema de Rutas en un grafo, donde las diferentes partes de la ciudad están representadas por vértices y los puentes por aristas. En general, un Problema de Rutas por Arcos consiste en, dado un grafo, diseñar una ruta recorriendo sus aristas que cumpla una serie de condiciones. El interés por el estudio de este tipo de problema estriba en que modeliza un gran número de problemas reales: reparto de correo, recogida de basuras, transporte público, mantenimiento de redes, etc. Los Problemas de Rutas por Arcos pueden ser formulados como Problemas de Optimización Combinatoria, donde el objetivo es hallar, de entre un conjunto numerable de soluciones posibles, aquélla que minimiza o maximiza una función de coste. Desgraciadamente, salvo para algunos de los problemas más sencillos, no es razonable esperar encontrar algoritmos capaces de resolver cualquier instancia de un problema con un número de operaciones que crezca polinómicamente con el tamaño de la instancia. Estos problemas para los que no parece que existan algoritmos de tiempo polinómico son los llamados NP-duros, y entre ellos se encuentra el problema tratado en esta tesis. Entre los Problemas de Rutas NP-duros más conocidos y estudiados se encuentra el Problema del Viajante (TSP), en el cual, dado un grafo y unos costes asociados a las aristas, el objetivo es hallar una ru ta de coste mínimo que pase exactamente una vez por cada vértice del grafo. Este es caso particular de los Problemas de Rutas por vértices, aquéllos en los que la ruta ha de visitar algunos (o todos) de los vértices del grafo. Por otra parte, en los Problemas de Rutas por Arcos, el objetivo es diseñar una ruta que pase por algunas (o todas) de las aristas (y/o arcos) de un grafo. Algunos de los Problemas de Rutas por Arcos 121 2 Introducción más conocidos son el Problema del Cartero Chino (CPP), propuesto por Guan en 1962, en el que se busca una ruta de coste mínimo que pase al menos una vez por todas las aristas; o el Problema del Cartero Rural (RPP), presentado por Orloff (1974), similar al CPP pero donde no estamos obligados a recorrer todas las aristas del grafo, sino un subconjunto de ellas, llamadas aristas requeridas. El Problema General de Rutas (GRP), Orloff (1974), combina la demanda en las aristas con la demanda en los vértices. Así, una solución del GRP es una ruta que recorra todas las aristas requeridas y visite todos los nodos requeridos del grafo. Además de por el tipo de demanda, los Problemas de Rutas pueden clasificarse también según el tipo del grafo sobre el que están definidos. Si los enlaces del grafo pueden ser recorridos en ambos sentidos, estamos ante un grafo dirigido y los enlaces reciben el nombre de aristas. En el caso en que los enlaces tienen una única dirección posible de recorrido, reciben el nombre de arcos, y el grafo se dice que es dirigido. Si existen tanto aristas como arcos en el grafo, estamos ante un grafo mixto. Por último, existe un cuarto tipo de grafos que contienen únicamente aristas, pero cada una de estas aristas tiene dos costes asociados, uno para cada sentido de recorrido. Este tipo de grafos recibe el nombre de windy, con viento, ya que representan la situación en que el cartero o vehículo encargado de recorrer la ruta tiene que avanzar a favor o en contra del viento, lo que le supone un menor o mayor coste. Desde un punto de vista más práctico, si los costes de una arista representan, por ejemplo, el tiempo que se tarda en recorrer una calle, estos grafos pueden representar situaciones en las que el tiempo de recorrido no es simétrico (debido, por ejemplo, a la densidad del trá fico). Además, los grafos windy generalizan a los grafos dirigidos, no dirigidos y mixtos. Existen otros tipos de generalizaciones de los Problemas de R utas que incorporan otra serie de características, como son la utilización de más de un vehículo para realizar las rutas, condiciones de ventanas temporales para el servicio de la demanda, etc. Este tipo de generalizaciones, sin embargo, se alejan del problema central de esta memoria, por lo que no entraremos en más detalles acerca de ellas. El problema estudiado en esta tesis es el Problema General de Rutas con Viento (WGRP). En él, tenemos un grafo G = (V, E) con un conjunto de vértices V, entre los cuales tenemos un subconjunto de vértices requeridos Vr C V, y un conjunto de aristas E, con un subconjunto de aristas requeridas Er C E. Cada arista entre dos nodos i y j, que representamos por tiene dos costes asociados: d j es el coste de recorrerla de i a j, y Cj es el coste de recorrerla de j a i. El objetivo es hallar una ruta de coste mínimo que recorra al menos una vez todas las aristas requeridas y visite todos los vértices requeridos. Este problema tiene un gran interés teórico, puesto que generaliza la mayor parte de los Problemas de Rutas por Arcos con un único vehículo. Por ejemplo,22 In troducción 3 en el caso de que todas las aristas sean requeridas, tenemos el W PP, y si no hay aristas requeridas y todos los vértices son requeridos, tenemos el GTSP. Así pues, los resultados teóricos obtenidos en el estudio de este problema podrán ser de aplicación a muchos otros. También los métodos de resolución, puesto que los algoritmos desarrollados para el WGRP pueden ser adaptados fácilmente para resolver instancias de sus casos particulares. En cuanto a sus aplicaciones prácticas, en esta tesis presentamos una situación real que puede ser modelizada como un WGRP. Se trata del diseño de rutas para robots escaladores encargados de la inspección de estructuras arquitectónicas complejas, como puentes o edificios. Estos robots son teledirigidos y poseen una cámara mediante la cual los operarios pueden observar las superficies de la estructura en busca de posibles daños. Las superficies a explorar serán representadas por aristas requeridas, mientras que los movimientos realizados por el robot para moverse de una superficie a otra corresponden a aristas no requeridas. La necesidad de dos costes para cada arista viene impuesta por el efecto de la gravedad en el consumo de energía dependiendo del sentido de movimiento del robot. En esta tesis abordamos la resolución del WGRP desde el punto de vista de la Combinatoria Poliédrica, uno de los enfoques más utilizados en los problemas NP-duros. De esta manera, tratam os de resolver el problema como un Problema Lineal, para lo cual es necesario conocer una descripción lo suficientemente completa del poliedro definido por la envoltura convexa del espacio de soluciones posibles. En efecto, si conociéramos todas las desigualdades que definen faceta del poliedro, tendríamos su descripción completa y podríamos hallar la solución óptima del problema resolviendo un Problema Lineal. En la práctica, y puesto que se trata de un problema NP-duro, esto no es posible, por lo que hemos de conformarnos con una descripción parcial. En esta memoria, presentamos una serie de familias de desigualdades válidas para el WGRP que definen facetas del poliedro. Las siguientes clases de desigualdades, propuestas anteriormente para otros problemas, han sido generalizadas al WGRP en este trabajo, en el que también se ha demostrado que inducen faceta de su poliedro asociado: Desigualdades triviales. Desigualdades de obligatoriedad. Desigualdades de conectividad. Desigualdades de cortes R-impares. Desigualdades K-C y K-Co2 - Desigualdades Path-Bridge y Path-Bridgeo2 - /23 4 In troducción Desigualdades Honeycomb y Honeycombo2 - Estas desigualdades, a excepción de las triviales y las de obligatoriedad, tienen una serie de características comunes y se denominan desigualdades de configuración. Así, todas ellas pueden asociarse a un grafo que resulta de dividir el grafo original en subconjuntos de vértices y comprimir las aristas no requeridas paralelas (entre los mismos pares de subconjuntos) en una sola. Entonces, los coeficientes de las variables asociadas a las aristas entre vértices pertenecientes a un mismo subconjunto serán 0, mientras que los coeficientes de las aristas requeridas en paralelo serán iguales. El grafo así comprimido se denomina grafo de configuración. Hemos demostrado que, si una desigualdad induce una faceta del WGRP definido sobre el grafo de configuración, también define una faceta del poliedro correspondiente al problema en el grafo original. Sin embargo, a diferencia de lo que ocurre para otros casos particulares del WGRP, la afirmación recíproca no es cierta. Es decir, existen desigualdades que definen facetas del poliedro del WGRP, distintas de las triviales y las de obligatoriedad, que no son desigualdades de configuración. En esta tesis, presentamos una nueva familia de desigualdades, a las que llamamos desigualdades Zigzag que definen faceta del poliedro del WGRP sin ser desigualdades de configuración. Al igual que las otras, estas desigualdades pueden definirse sobre un grafo de configuración, donde las variables asociadas a las aristas internas de los subconjuntos tendrán coeficiente 0 en la desigualdad. Sin embargo, existen aristas paralelas en el grafo configuración que tienen coeficientes distintos en la desigualdad. Hasta donde sabemos, este es el primer caso de desigualdades para problemas de Rutas por Arcos con esta característica, por lo que hemos introducido el concepto de desigualdades de configuración débil. Puesto que es imposible incorporar explícitamente a la formulación la descripción parcial de la envoltura convexa del espacio de soluciones, esta puede ir siendo añadida de manera iterativa en lo que se conoce como un algoritmo de Planos de Corte. En este tipo de algoritmos, partimos de un Problema Lineal que es una versión relajada del problema a resolver. Este problema puede ser resuelto fácilmente, pero la solución obtenida no será, generalmente, una solución válida de nuestro problema, es decir, estará fuera de la envoltura convexa del espacio de soluciones. Existirá, por tanto, una desigualdad válida para el problema que no es satisfecha por la solución, es decir, violada por la solución. Podemos, entonces, intentar buscar, entre las familias conocidas, una desigualdad violada que nos permita cortar la solución no válida. Para ello se emplean los llamados algoritmos de separación, que se encargan de encontrar, si existe, dicha desigualdad. Sin embargo, a menudo, el problema de, dada una solución no válida, determinar si dentro de una determinada familia de desigualdades existe alguna violada, es NP-duro en sí mismo, por lo que deberemos recurrir a algoritmos heurísticos. Si mediante los algoritmos de separación hemos podido identificar alguna desigualdad violada, podemos añadirla al Problema Lineal actual y volver a resolverlo. Este proceso se repite hasta que, o bien obtenemos24 Introducción 5 una solución factible, que será óptima, o bien no somos capaces de hallar más desigualdades violadas. O tra alternativa a los algoritmos de Planos de Corte son los algoritmos de Ramificación y Acotación. Estos algoritmos se basan en la construcción de un árbol de enumeración para explorar el espacio de soluciones, utilizando cotas inferiores obtenidas mediante la resolución de Problemas Lineales así como cotas superiores pertenecientes a soluciones válidas conocidas, para limitar dicha búsqueda. Si en cada nodo del árbol de enumeración ejecutamos un algoritmo de Planos de Corte sobre el Problema Lineal correspondiente, podemos mejorar las cotas obtenidas más rápidamente. Estos algoritmos se conocen como algoritmos de Ramificación y Corte (Branch and Cut), y fueron aplicados por primera vez por Padberg y Rinaldi (1990). En esta memoria presentamos un algoritmo de Ramificación y Corte para el WGRP. Para probar la eficiencia de dicho algoritmo, hemos utilizado un gran número de instancias, tanto del W GRP como de los problemas que aparecen como casos particulares del WGRP. Alguna de estas instancias han sido generadas expresamente para este trabajo, mientras que otras son instancias tomadas de la literatura conocida. Los tamaños de las instancias varían desde los 7 nodos y 10 enlaces en los grafos de las instancias más pequeñas, hasta los 1000 nodos y más de 4000 enlaces para las más grandes. Para terminar la memoria, presentamos las conclusiones derivadas de este trabajo y las líneas de trabajo a seguir en el futuro.25 26 Capítulo 1 Preliminares Matemáticos Este capítulo recoge algunos conceptos básicos de Teoría de Grafos, Álgebra Lineal, Programación Lineal, Teoría de Poliedros y Teoría de la Complejidad Algorítmica que son utilizados en capítulos posteriores Teoría de Grafos Muchos problemas que encontramos en el mundo real, entre ellos los Problemas de R utas de Vehículos, pueden ser formulados mediante la Teoría de Grafos. Algunos problemas que a priori parecen complicados y ambiguos, representados en términos de Teoría de Grafos son claros y precisos, permitiendo así un acercamiento matemático más adecuado para su resolución. En esta sección, introduciremos algunos conceptos y resultados de Teoría de Grafos que hemos empleado en el presente trabajo. Algunas referencias clásicas en esta área son Harady (1969), Berge (1973), Bondy y M urty (1976) y Christofides (1975). Sea V un conjunto finito no vacío y sea E una familia finita de pares no ordenados (no necesariamente distintos) ( i,j) de elementos de V (no necesariamente distintos). Llamaremos grafo no dirigido al par G = (V, E ), vértices de G a los elementos de V y aristas de G a los elementos de E. Si el par e = (i,j) es una arista de G, diremos que i y j son los vértices extremos de e, o que la arista e une los vértices i y j, o que la arista e es incidente con los vértices i y j, o que los vértices i y j son adyacentes. A las aristas de la forma (i, i) las llamaremos bucles. Si dos aristas tienen 727 8 C apítulo 1. P relim inares M atem áticos los mismos vértices extremos diremos que son paralelas. Diremos que un grafo es simple si no tiene bucles ni aristas en paralelo y diremos que un grafo es completo si es simple y para cada par de vértices i ^ j existe una arista (i,j) entre ellos. A veces, por simplicidad, denotaremos la arista (i,j) simplemente por ij, y usaremos una coma entre los dos vértices si es necesario (por ejemplo para la arista i,i + 1). Dado un vértice i de un grafo G, denotaremos por Óg (í ) al conjunto de todas las aristas de G incidentes con i, o simplemente 5(i) si no hay ambigüedad. Llamaremos grado del vértice i a la cardinalidad de 6(i), i.e., el número de aristas incidentes con el vértice i, y diremos que un vértice i es par (resp. impar) si su grado es par (resp. impar). Diremos que G es un grafo par si todos sus vértices son pares. Teorem a Sea G un grafo no dirigido. G contiene un número par de vértices impares. Si Si y S 2 son dos subconjuntos disjuntos de V, denotaremos por (Si : S 2 ) al conjunto de todas las aristas de G con un vértice extremo en S i y el otro en S 2. En particular, si representamos por S a V \ S, llamaremos cortadura de G a (S : S) para cualquier S C V no vacío, y diremos que una cortadura es par (resp. impar) si el número de aristas que contiene es par (resp. impar). En particular, S(i), i G V, es una cortadura de G. Teorem a (S : S ) es una cortadura impar de G si y sólo si S y S contienen un número impar de vértices impares. Si G (V,E ) y Gi = (Vi, E i) son dos grafos tales que V\ C V y E i C E, diremos que Gi es un subgrafo de G. Dado un subconj unto V ' C V denotaremos por E (V ') al conjunto de aristas de G con ambos extremos en V ' y llamaremos subgrafo de G inducido por V ' al grafo G (V') = (V ', E (V ')). Del mismo modo, dado un subconjunto E ' de E, denotaremos por V (E ') al conjunto de vértices de G que son incidentes con al menos una arista de E 1, y llamaremos subgrafo de G inducido por E al grafo G (E') = (V (E '),E '). Sea G = {V,E) un grafo y sean u,v G V. Llamaremos camino entre u y v a cualquier secuencia w = ( o*i>ú*2 >, ik -iik ) de aristas de G con íq = u y ik = v, y diremos que w contiene o recorre las aristas o*i>ú 2 ), ik -iik, así como que contiene o pasa por los vértices ío,* i, 2 5 Si no hay ambigüedad, también representaremos w como una secuencia de vértices ( 0, 1, 2,..., fc-i, ik) o como el conjunto de aristas ijij+ 1,0 < j < k 1.28 1.1. Teoría de Grafos 9 Si w es un camino y la arista ikio E, llamaremos tour o camino cerrado a la secuencia ( 0 *15*1*2» V o)- Llamaremos ciclo de longitud k a cualquier tour ( 0 *1»*1*2»»*fc-i*jfc»*fe*o) tal que is ^ it 0 < s, t < k (no pasa más de una vez por el mismo vértice). Un ciclo hamiltoniano en el grafo G es un ciclo que pasa por cada vértice de G exactamente una vez. Podemos representar un grafo no dirigido en el plano mediante un diagrama de puntos y líneas. Cada punto corresponde a un vértice del grafo y para cada arista del grafo entre dos vértices u y v hay una línea que une los dos puntos correspondientes. T eo rem a Si w es un tour sobre las aristas de G, entonces w pasa un número par de veces (quizás cero) por las aristas de cualquier cortadura de G. Diremos que un grafo G es conexo si entre cada par de vértices de G existe al menos un camino. Por convenio, un grafo con un único vértice es conexo. Una componente conexa de G es un subgrafo conexo de G que es inducido por un conjunto de vértices de G y es maximal respecto a la cardinalidad del subconj unto de vértices. Es inmediato comprobar que un grafo G es conexo si y sólo si tiene una única componente conexa. Diremos que una arista e es un puente de G si el subgrafo de G inducido por E \{e} tiene más componentes conexas que G. Un tour Euleriano en el grafo G es un tour que recorre cada arista de G exactamente una vez y se dice que un grafo es Euleriano si existe un tour Euleriano en él. T eo rem a (Euler) G es Euleriano si y sólo si es conexo y par. Sea G = (V, E) un grafo no dirigido y sea c : E >R una función que asigna un coste o longitud ce a cada arista e E. Sea F C E. Llamaremos coste o longitud de F a c(f) = cf Del mismo modo, si w = ( 0*1»*1*2»»*fc-i*fc) fe F k- 1 es un camino en G, llamaremos coste o longitud de w a c(w) = ]T) c i + 1 j =o Sea V un conjunto finito no vacío y sea A una familia finita de pares ordenados (i,j) (no necesariamente distintos) de elementos de V ordenados (no necesariamente distintos). Llamaremos grafo dirigido al par G = (V, A), vértices de G a los elementos de V y arcos de G a los elementos de A. Sea V un conjunto finito no vacío, E una familia finita de pares no ordenados (no necesariamente distintos) ( i,j) de elementos de V (no necesariamente Mostrar más
w n ;:k s i t a t d e valencia BIBLIOTECA CIÉNCIES N- rv.gisír- * $ 01'^ ' DATA í (O,.#5., SIGNATURA \5g TZD ZG C v i / i5,
w n ;:k s i t a t d e valencia BIBLIOTECA CIÉNCIES N- rv.gisír- * $ 01'^ ' DATA í (O,.#5., SIGNATURA \5g TZD ZG C v i / i5, Rutas de Vehículos con Demanda Compartida. M. Carmen Martínez Blázquez Dpto. Más detalles Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas).
Apuntes de Matemática Discreta 14. Grafos Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 14 Grafos Contenido 14.1 Generalidades..................................... Más detalles MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13. Carlos Ivorra
MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13 Carlos Ivorra Índice 1 Introducción a la optimización 1 2 Programación entera 18 3 Introducción a la programación lineal 24 4 El método símplex Más detalles Programación Lineal Entera
Programación Lineal Entera P.M. Mateo y David Lahoz 2 de julio de 2009 En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción Más detalles Apuntes de Matemática Discreta 6. Relaciones
Apuntes de Matemática Discreta 6. Relaciones Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 6 Relaciones Contenido 6.1 Generalidades..................................... Más detalles Tema 2. Espacios Vectoriales. 2.1. Introducción
Tema 2 Espacios Vectoriales 2.1. Introducción Estamos habituados en diferentes cursos a trabajar con el concepto de vector. Concretamente sabemos que un vector es un segmento orientado caracterizado por Más detalles Tema III. Capítulo 2. Sistemas generadores. Sistemas libres. Bases.
Tema III Capítulo 2 Sistemas generadores Sistemas libres Bases Álgebra Lineal I Departamento de Métodos Matemáticos y de Representación UDC 2 Sistemas generadores Sistemas libres Bases 1 Combinación lineal Más detalles Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración
5053 Martes, 9 de abril Ramificación y acotamiento () Entregas: material de clase Resumen de técnicas para resolver problemas de programación entera Técnicas de enumeración Enumeración completa hace una Más detalles ESPACIO VECTORIAL ESPACIO VECTORIAL SUBESPACIO VECTORIAL BASE Y DIMENSIÓN N DE UN
Tema 5.- ESPACIOS VECTORIALES ESPACIO VECTORIAL SUBESPACIO VECTORIAL BASE Y DIMENSIÓN N DE UN ESPACIO VECTORIAL Fundamentos Matemáticosde la Ingeniería 1 Aunque históricamente el primer trabajo de Álgebra Más detalles Apuntes de Matemática Discreta 7. Relaciones de Orden
Apuntes de Matemática Discreta 7. Relaciones de Orden Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 7 Relaciones de Orden Contenido Más detalles Desarrollo de un nuevo algoritmo para resolver programas lineales enteros y su aplicación práctica en el desarrollo económico.
Desarrollo de un nuevo algoritmo para resolver programas lineales enteros y su aplicación práctica en el desarrollo económico. 7071 Febrero, 2014 Resumen Es importante señalar que en un entorno social Más detalles INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA
INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA Dentro del campo general de la teoría de la optimización, también conocida como programación matemática conviene distinguir diferentes modelos de optimización. Más detalles Problema de Programación Lineal
Problema de Programación Lineal Introducción La optimización es un enfoque que busca la mejor solución a un problema. Propósito: Maximizar o minimizar una función objetivo que mide la calidad de la solución, Más detalles Universidad de Costa Rica Escuela de Matemática ALGEBRA LINEAL. x x1 n. θ y. 1 n x1 n ȳ1 n. Carlos Arce S. William Castillo E. Jorge González V.
Universidad de Costa Rica Escuela de Matemática ALGEBRA LINEAL x x x1 n θ y y ȳ1 n 1 n x1 n ȳ1 n Carlos Arce S. William Castillo E. Jorge González V. 2003 Algebra Lineal Carlos Arce S., William Castillo Más detalles GRAFOS. Prof. Ing. M.Sc. Fulbia Torres
ESTRUCTURAS DE DATOS 2006 Prof. DEFINICIÓN Un grafo consta de un conjunto de nodos(o vértices) y un conjunto de arcos (o aristas). Cada arco de un grafo se especifica mediante un par de nodos. Denotemos Más detalles ÁLGEBRA LINEAL - Año 2012
UNIVERSIDAD NACIONAL DE RÍO CUARTO FACULTAD DE CIENCIAS ECONÓMICAS ÁLGEBRA LINEAL - Año 0 Notas de Cátedra correspondientes a la UNIDAD SIETE PROGRAMACIÓN LINEAL * INECUACIONES Se denomina inecuación a Más detalles Investigación Operacional I EII 445
Investigación Operacional I EII 445 Programación Lineal Método Simple Gabriel Gutiérrez Jarpa. Propiedades Básicas de Programación Lineal Formato Estándar Un problema de programación lineal es un programa Más detalles Estructuras algebraicas
Tema 2 Estructuras algebraicas básicas 2.1. Operación interna Definición 29. Dados tres conjuntos A, B y C, se llama ley de composición en los conjuntos A y B y resultado en el conjunto C, y se denota Más detalles Algoritmos sobre Grafos
Sexta Sesión 27 de febrero de 2010 Contenido Deniciones 1 Deniciones 2 3 4 Deniciones sobre Grafos Par de una lista de nodos y una lista de enlaces, denidos a su vez como pares del conjunto de nodos. Más detalles BASES Y DIMENSIÓN. Propiedades de las bases. Ejemplos de bases.
BASES Y DIMENSIÓN Definición: Base. Se llama base de un espacio (o subespacio) vectorial a un sistema generador de dicho espacio o subespacio, que sea a la vez linealmente independiente. β Propiedades Más detalles Complejidad - Problemas NP-Completos. Algoritmos y Estructuras de Datos III
Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teoría de Complejidad Un algoritmo eficiente es un algoritmo de complejidad polinomial. Un problema está bien resuelto si se conocen Más detalles Matemáticas 2º BTO Aplicadas a las Ciencias Sociales
Matemáticas 2º BTO Aplicadas a las Ciencias Sociales CONVOCATORIA EXTRAORDINARIA DE JUNIO 2014 MÍNIMOS: No son contenidos mínimos los señalados como de ampliación. I. PROBABILIDAD Y ESTADÍSTICA UNIDAD Más detalles 3.- ALGUNOS CONCEPTOS BÁSICOS DE ÁLGEBRA DE BOOLE 4.- TRANSFORMACIÓN DE EXPRESIONES LÓGICAS A EXPRESIONES ALGEBRAICAS
TEMA 12: MODELADO CON VARIABLES BINARIAS 1.- MOTIVACIÓN 2.- INTRODUCCIÓN 3.- ALGUNOS CONCEPTOS BÁSICOS DE ÁLGEBRA DE BOOLE 4.- TRANSFORMACIÓN DE EXPRESIONES LÓGICAS A EXPRESIONES ALGEBRAICAS 5.- MODELADO Más detalles Espacios de Hilbert. 10.1. Producto Escalar y Norma. Tema 10
Tema 10 Espacios de Hilbert Vamos a desarrollar en lo que sigue los resultados básicos acerca de los espacios de Hilbert, un tipo muy particular de espacios de Banach con propiedades especiales que están Más detalles 1. Producto escalar, métrica y norma asociada
1. asociada Consideramos el espacio vectorial R n sobre el cuerpo R; escribimos los vectores o puntos de R n, indistintamente, como x = (x 1,..., x n ) = n x i e i i=1 donde e i son los vectores de la Más detalles ALGEBRA LINEAL. Héctor Jairo Martínez R. Ana María Sanabria R.
ALGEBRA LINEAL Héctor Jairo Martínez R. Ana María Sanabria R. SEGUNDO SEMESTRE 8 Índice general. SISTEMAS DE ECUACIONES LINEALES.. Introducción................................................ Conceptos Más detalles Máster Interuniversitario en Técnicas Estadísticas. Cooperación en los problemas del viajante (TSP) y de rutas de vehículos (VRP): una panorámica.
Máster Interuniversitario en Técnicas Estadísticas Cooperación en los problemas del viajante (TSP) y de rutas de vehículos (VRP): una panorámica. AIDA CALVIÑO MARTÍNEZ JUNIO 2011 Autorización de entrega Más detalles Tema 3. Espacios vectoriales
Tema 3. Espacios vectoriales Estructura del tema. Definición y propiedades. Ejemplos. Dependencia e independencia lineal. Conceptos de base y dimensión. Coordenadas Subespacios vectoriales. 0.1. Definición Más detalles Subespacios vectoriales en R n
Subespacios vectoriales en R n Víctor Domínguez Octubre 2011 1. Introducción Con estas notas resumimos los conceptos fundamentales del tema 3 que, en pocas palabras, se puede resumir en técnicas de manejo Más detalles Espacios vectoriales y aplicaciones lineales
Capítulo 3 Espacios vectoriales y aplicaciones lineales 3.1 Espacios vectoriales. Aplicaciones lineales Definición 3.1 Sea V un conjunto dotado de una operación interna + que llamaremos suma, y sea K un Más detalles L A P R O G R A M A C I O N
L A P R O G R A M A C I O N L I N E A L 1. INTRODUCCIÓN: la programación lineal como método de optimación La complejidad de nuestra sociedad en cuanto a organización general y económica exige disponer Más detalles Modelado de flujo en redes. Jhon Jairo Padilla A., PhD.
Modelado de flujo en redes Jhon Jairo Padilla A., PhD. Conceptos básicos Demanda o volumen de Demanda: Es el tráfico que están requiriendo los usuarios de una red. Para transportar el volumen de demanda Más detalles 6 PBE. MODELOS EN MATEMÁTICAS
6 PBE. MODELOS EN MATEMÁTICAS Esta unidad tiene como objetivo continuar con la resolución de problemas a través de la modelización y simulación siguiendo el patrón PBE (P systems By Example) empleado en Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de 2003 1. Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema Más detalles Un programa entero de dos variables. 15.053 Jueves, 4 de abril. La región factible. Por qué programación entera? Variables 0-1
15.053 Jueves, 4 de abril Un programa entero de dos variables Introducción a la programación entera Modelos de programación entera Handouts: material de clase maximizar 3x + 4y sujeto a 5x + 8y 24 x, y Más detalles Algoritmos Heurísticos en Optimización Combinatoria
Algoritmos Heurísticos en Optimización Combinatoria Rafael Martí Cunquero Departament d Estadística i Investigació Operativa Programa 1. Introducción 2. Calidad de los Algoritmos 3. El Problema del Viajante Más detalles Desarrollar y aplicar estrategias para resolver problemas Determinar si un gráfico es lineal dibujando puntos en una situación dada
MANEJO DE DATOS Analizar gráficos o diagramas de situaciones dadas para identificar información específica Recoger datos, dibujar los datos usando escalas apropiadas y demostrar una comprensión de las Más detalles Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero
Fundamentos de Investigación de Operaciones y Vendedor Viajero 23 de mayo de 2004 Si bien la resolución del problema de transporte mediante tableau parece ser muy expedita, existen ciertos tipos de problemas Más detalles Problemas de Rutas. Vicente Campos Aucejo Dpt. Estadística i Investigació Operativa Universitat de València vicente.campos@uv.es
Problemas de Rutas Vicente Campos Aucejo Dpt. Estadística i Investigació Operativa Universitat de València vicente.campos@uv.es Resumen El objetivo de este trabajo es el de divulgar la existencia de un Más detalles Tema 2. Aplicaciones lineales y matrices.
Tema 2 Aplicaciones lineales y matrices. 1 Índice general 2. Aplicaciones lineales y matrices. 1 2.1. Introducción....................................... 2 2.2. Espacio Vectorial..................................... Más detalles Dualidad y Análisis de Sensibilidad
Universidad de Chile Facultad de Ciencias Físicas y Matemáticas Departamento de Ingeniería Industrial IN34A: Clase Auxiliar Dualidad y Análisis de Sensibilidad Marcel Goic F. 1 1 Esta es una versión bastante Más detalles Una heurística para la asignación de máquinas a trabajos fijos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Una heurística para la asignación de máquinas a trabajos fijos José Manuel García Sánchez, Marcos Calle Suárez, Gabriel Más detalles Optimización combinatoria poliédrica: problemas de rutas-localización
Curso 1995/96 CIENCIAS Y TECNOLOGÍAS JUAN JOSÉ SALAZAR GONZÁLEZ Optimización combinatoria poliédrica: problemas de rutas-localización Directores PAOLO TOTH MATTEO FISCHETTI SOPORTES AUDIOVISUALES E INFORMÁTICOS Más detalles CAPÍTULO II. 2 El espacio vectorial R n
CAPÍTULO II 2 El espacio vectorial R n A una n upla (x 1, x 2,..., x n ) de números reales se le denomina vector de n coordenadas o, simplemente, vector. Por ejemplo, el par ( 3, 2) es un vector de R 2, Más detalles TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS 1
Técnicas de planificación y control de proyectos Andrés Ramos Universidad Pontificia Comillas http://www.iit.comillas.edu/aramos/ Andres.Ramos@comillas.edu TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS Más detalles Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de
Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de vértices o nodos conectados con arcos y/o aristas. Diseñar Más detalles METAHEURISTICAS Ideas, Mitos, Soluciones
METAHEURISTICAS Ideas, Mitos, Soluciones OPTIMIZACION COMBINATORIA Qué es un problema de optimización combinatoria? Cómo se modela matemáticamente un problema de optimización combinatoria? Minimizar (o Más detalles Introducción a la Teoría de Grafos
Introducción a la Teoría de Grafos Flavia Bonomo fbonomo@dc.uba.ar do. Cuatrimestre 009 Árboles Un árbol es un grafo conexo y acíclico (sin ciclos). Un bosque es un grafo acíclico, o sea, una unión disjunta Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1
Fundamentos de Investigación de Operaciones Investigación de Operaciones de agosto de 200. Estandarización Cuando se plantea un modelo de LP pueden existir igualdades y desigualdades. De la misma forma Más detalles Probabilidad y sus aplicaciones en ingeniería informática
Probabilidad y sus aplicaciones en ingeniería informática Víctor Hernández Eduardo Ramos Ildefonso Yáñez c Víctor Hernández, Eduardo Ramos, Ildefonso Yánez EDICIONES CDÉMICS Probabilidad y sus aplicaciones Más detalles Fascículo 2. Álgebra Lineal. Cursos de grado. Gabriela Jeronimo Juan Sabia Susana Tesauri. Universidad de Buenos Aires
Fascículo 2 Cursos de grado ISSN 1851-1317 Gabriela Jeronimo Juan Sabia Susana Tesauri Álgebra Lineal Departamento de Matemática Facultad de Ciencias Exactas y Naturales Universidad de Buenos Aires 2008 Más detalles CURSO CERO. Departamento de Matemáticas. Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre
CURSO CERO Departamento de Matemáticas Profesor: Raúl Martín Martín Sesiones 18 y 19 de Septiembre Capítulo 1 La demostración matemática Demostración por inducción El razonamiento por inducción es una Más detalles 7. Conclusiones. 7.1 Resultados
7. Conclusiones Una de las preguntas iniciales de este proyecto fue : Cuál es la importancia de resolver problemas NP-Completos?. Puede concluirse que el PAV como problema NP- Completo permite comprobar Más detalles Cómo?: Resolviendo el sistema lineal homógeneo que satisfacen las componentes de cualquier vector de S. x4 = x 1 x 3 = x 2 x 1
. ESPACIOS VECTORIALES Consideremos el siguiente subconjunto de R 4 : S = {(x, x 2, x 3, x 4 )/x x 4 = 0 x 2 x 4 = x 3 a. Comprobar que S es subespacio vectorial de R 4. Para demostrar que S es un subespacio Más detalles Dependencia lineal de vectores y sus aplicaciones a la resolución de sistemas de ecuaciones lineales y de problemas geométricos.
Dependencia lineal de vectores y sus aplicaciones a la resolución de sistemas de ecuaciones lineales y de problemas geométricos. Prof. D. Miguel Ángel García Hoyo. Septiembre de 2011 Dependencia lineal Más detalles EN INFORMÁTICA DE SISTEMAS
INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS Curso Académico 2009/2010 Proyecto Fin de Carrera PLANIFICACIÓN CUALITATIVA DE CAMINOS DE ROBOTS MÓVILES EN ENTORNOS POLIGONALES BASADA EN LA TEORÍA DE MATROIDES Más detalles OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA. Tema 2 Programación Lineal
OPTIMIZACIÓN Y SIMULACIÓN PARA LA EMPRESA Tema 2 Programación Lineal ORGANIZACIÓN DEL TEMA Sesiones: Introducción, definición y ejemplos Propiedades y procedimientos de solución Interpretación económica Más detalles PROCEDIMIENTO HEURÍSTICO PARA MINIMIZAR EL C max EN CELDAS ROBOTIZADAS CON BUFFERS FINITOS Y PIEZAS DISTINTAS
27 Congreso Nacional de Estadística e Investigación Operativa Lleida, 8 11 de abril de 2003 PROCEDIMIENTO HEURÍSTICO PARA MINIMIZAR EL C max EN CELDAS ROBOTIZADAS CON BUFFERS FINITOS Y PIEZAS DISTINTAS Más detalles RESUMEN INFORMATIVO PROGRAMACIÓN DIDÁCTICA CURSO 2015 /2016
RESUMEN INFORMATIVO PROGRAMACIÓN DIDÁCTICA CURSO 2015 /2016 DEPARTAMENTO: MATEMÁTICAS MATERIA: MATEMÁTICAS ACADÉMICAS CURSO: 3º ESO OBJETIVOS DEL ÁREA DE MATEMÁTICAS A LAS ENSEÑANZAS ACADÉMICAS 3º ESO Más detalles Transparencias de Matemática Discreta Doble Grado en Ingeniería en Informática y. Administración de Empresas Curso 2013 2014
ESCUELA POLITÈCNICA SUPERIOR UNIVERSIDAD CARLOS III DE MADRID Transparencias de Matemática Discreta Grado en Ingeniería en Informática Doble Grado en Ingeniería en Informática y Administración de Empresas Más detalles IES CANARIAS CABRERA PINTO DEPARTAMENTO DE MATEMÁTICAS CONTENIDOS MÍNIMOS 1º ESO SEPTIEMBRE 2015
CONTENIDOS MÍNIMOS 1º ESO SEPTIEMBRE 2015 UNIDAD 1: LOS NÚMEROS NATURALES. OPERACIONES Y RELACIONES El sistema de numeración decimal Estimación y redondeo de un número natural Las operaciones con números Más detalles Análisis III. Joaquín M. Ortega Aramburu
Análisis III Joaquín M. Ortega Aramburu Septiembre de 1999 Actualizado en julio de 2001 2 Índice General 1 Continuidad en el espacio euclídeo 5 1.1 El espacio euclídeo R n............................... Más detalles TEMA 2: Grupos. El grupo Simétrico.
Álgebra y Estructuras Discretas Grupo B de la Ingeniería Técnica de Sistemas TEMA 2: Grupos. El grupo Simétrico. 1. Definición de Grupo. Propiedades Básicas. Definición 1. Dado un conjunto no vacío G, Más detalles E. T. S. de Ingenieros Industriales Universidad Politécnica de Madrid. Grado en Ingeniería en Tecnologías Industriales. Grado en Ingeniería Química
E. T. S. de Ingenieros Industriales Universidad Politécnica de Madrid Grado en Ingeniería en Tecnologías Industriales Grado en Ingeniería Química Apuntes de Álgebra ( Curso 2014/15) Departamento de Matemática Más detalles Universidad Autónoma de Nuevo León
Universidad Autónoma de Nuevo León Facultad de Ingeniería Mecánica y Eléctrica División de Estudios de Posgrado Optimización de la producción en máquinas en paralelo de inyección de plástico por I.Q. Miguel Más detalles Introducción al Análisis Complejo
Introducción al Análisis Complejo Aplicado al cálculo de integrales impropias Complementos de Análisis, I.P.A Prof.: Federico De Olivera Leandro Villar 13 de diciembre de 2010 Introducción Este trabajo Más detalles DIRECTRICES Y ORIENTACIONES GENERALES PARA LAS PRUEBAS DE ACCESO A LA UNIVERSIDAD
Curso Asignatura 2009/2010 MATEMÁTICAS APLICADAS A LAS CIENCIAS SOCIALES II 1º Comentarios acerca del programa del segundo curso del Bachillerato, en relación con la Prueba de Acceso a la Universidad INTRODUCCIÓN Más detalles ALGORITMICA III Capitulo I ANALISIS DE ALGORITMOS
Universidad Nacional de San Antonio Abad del Cusco Departamento Académico de Informática ALGORITMICA III Capitulo I ANALISIS DE ALGORITMOS Iván Medrano Valencia ANALISIS DE ALGORITMOS Un algoritmo es un Más detalles 1 Espacios y subespacios vectoriales.
UNIVERSIDAD POLITÉCNICA DE CARTAGENA Departamento de Matemática Aplicada y Estadística Espacios vectoriales y sistemas de ecuaciones 1 Espacios y subespacios vectoriales Definición 1 Sea V un conjunto Más detalles Producto Interno y Ortogonalidad
Producto Interno y Ortogonalidad Departamento de Matemáticas, CSI/ITESM 15 de octubre de 2009 Índice 8.1. Contexto................................................ 1 8.2. Introducción............................................... Más detalles Programación lineal. En esta Unidad didáctica nos proponemos alcanzar los objetivos siguientes:
UNIDAD 3 Programación lineal a programación lineal es parte L de una rama de las matemáticas relativamente joven llamada investigación operativa. La idea básica de la programación lineal es la de optimizar, Más detalles Espacios vectoriales
Espacios vectoriales Natalia Boal María Luisa Sein-Echaluce Universidad de Zaragoza 1 Concepto de espacio vectorial y propiedades 1.1 Definición Se llama espacio vectorial sobre K (IR o C a toda terna Más detalles Apuntes sobre algunos teoremas fundamentales de análisis complejo, con 20 ejemplos resueltos (2007-08)
Variable Compleja I (3 o de Matemáticas) Apuntes sobre algunos teoremas fundamentales de análisis complejo, con ejemplos resueltos (7-8) En estos apuntes, consideraremos las funciones anaĺıticas (holomorfas) Más detalles Matemáticas. Si un error simple ha llevado a un problema más sencillo se disminuirá la puntuación.
UNIVERSIDAD POLITÉCNICA DE CARTAGENA PRUEBAS DE ACCESO A LA UNIVERSIDAD DE LOS MAYORES DE 25 AÑOS CONVOCATORIA 2014 CRITERIOS DE EVALUACIÓN Matemáticas GENERALES: El examen constará de dos opciones (dos Más detalles Parte I. Iniciación a los Espacios Normados
Parte I Iniciación a los Espacios Normados Capítulo 1 Espacios Normados Conceptos básicos Sea E un espacio vectorial sobre un cuerpo K = R ó C indistintamente. Una norma sobre E es una aplicación de E Más detalles Leonard Euler y la Teoría de Grafos
Leonard Euler y la Teoría de Grafos Qué tienen en común un pasatiempo de los habitantes de una ciudad europea del siglo XVIII; Colorear el mapa de Colombia; Planear un viaje de vacaciones; Evitar problemas Más detalles Espacios vectoriales con producto interno
Capítulo 8 Espacios vectoriales con producto interno En este capítulo, se generalizarán las nociones geométricas de distancia y perpendicularidad, conocidas en R y en R 3, a otros espacios vectoriales. Más detalles El proyecto realizado consiste en un resolutor de sudokus mediante CSP.
Introducción El proyecto realizado consiste en un resolutor de sudokus mediante CSP. El problema del sudoku fue inventado por Howard Garns en 1979 y se volvió muy popular en Japón en 1986. En España ha Más detalles + 7 es una ecuación de segundo grado. es una ecuación de tercer grado.
ECUACIONES Y DESIGUALDADES UNIDAD VII VII. CONCEPTO DE ECUACIÓN Una igualdad es una relación de equivalencia entre dos epresiones, numéricas o literales, que se cumple para algún, algunos o todos los valores Más detalles Ejemplo 1.2 En el capitulo anterior se demostró que el conjunto. V = IR 2 = {(x, y) : x, y IR}
Subespacios Capítulo 1 Definición 1.1 Subespacio Sea H un subconjunto no vacio de un espacio vectorial V K. Si H es un espacio vectorial sobre K bajo las operaciones de suma y multiplicación por escalar Más detalles Investigación de operaciones en acción: Heurísticas para la solución del TSP
Investigación de operaciones en acción: Heurísticas para la solución del TSP Roger Z. Ríos Mercado* José Luis González Velarde** Abstract One of the most common and difficult problem in the theory of optimization Más detalles Espacios vectoriales y Aplicaciones lineales
Espacios vectoriales y Aplicaciones lineales Espacios vectoriales. Subespacios vectoriales Espacios vectoriales Definición Sea V un conjunto dotado de una operación interna + que llamaremos suma, y sea Más detalles Grupos. 2.1 Introducción. Capítulo
Capítulo 2 Grupos 2.1 Introducción La estructura de grupo es una de las más comunes en toda la matemática pues aparece en forma natural en muchas situaciones, donde se puede definir una operación sobre Más detalles Este es un ejemplo muy sencillo, un esquema de empleados que trabajan en proyectos, en una relación muchos a muchos.
28/04/2012 La teoría de la normalización va perdiendo peso con el paso de los años como herramienta de diseño de bases de datos relacionales en favor de modelos de datos más ricos en su representación, Más detalles Bachillerato. Matemáticas. Ciencias y tecnología
Bachillerato º Matemáticas Ciencias y tecnología Índice Unidad 0 Números reales........................................... 7. Evolución histórica................................... 8. Números reales...................................... Más detalles Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING
Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING 6.1. HEURÍSTICAS CONVENCIONALES El problema de job shop scheduling (JSSP) es un problema muy importante [69]; está entre los problemas de optimización Más detalles Listas de vectores y conjuntos de vectores
Listas de vectores y conjuntos de vectores La explicación de los temas Dependencia lineal y Bases en el curso de Álgebra Lineal se puede basar en uno de los siguientes dos conceptos (o en ambos): ) listas Más detalles Descripción inicial del sistema. Descripción final del sistema. Estado 1 Estado 2 Estado n
Búsqueda en Inteligencia Artificial Fernando Berzal, berzal@acm.org Búsqueda en I.A. Introducción Espacios de búsqueda Agentes de búsqueda Uso de información en el proceso de búsqueda Búsqueda sin información Más detalles MATEMÁTICAS EMPRESARIALES II:
MATEMÁTICAS EMPRESARIALES II: FUNCIÓN REAL DE VARIAS VARIABLES ÓPTIMOS DE UNA FUNCIÓN ESCALAR MATERIAL DIDÁCTICO DE SOPORTE González-Vila Puchades, Laura Ortí Celma, Francesc J. Sáez Madrid, José B. Departament Más detalles Análisis de una variable real I. Tijani Pakhrou
Análisis de una variable real I Tijani Pakhrou Índice general 1. Introducción axiomática de los números 1 1.1. Números naturales............................ 1 1.1.1. Axiomas de Peano........................ Más detalles La conjetura de Stanley sobre el h-vector de una matroide
La conjetura de Stanley sobre el h-vector de una matroide José Alejandro Samper 21 de junio de 2011 1 Agradecimientos Quiero darle las gracias a Federico Ardila por mostrarme e problema y guiarme todo Más detalles Repaso de matrices, determinantes y sistemas de ecuaciones lineales
Tema 1 Repaso de matrices, determinantes y sistemas de ecuaciones lineales Comenzamos este primer tema con un problema de motivación. Problema: El aire puro está compuesto esencialmente por un 78 por ciento Más detalles Espacios vectoriales
Espacios vectoriales Problemas teóricos Muchos de estos problemas me los han enseñado mis colegas: profesores Flor de María Correa Romero, Carlos Domínguez Albino, Sergio González Govea, Myriam Rosalía Más detalles Juan Antonio González Mota Profesor de Matemáticas del Colegio Juan XIII Zaidín de Granada
FUNCIONES CONTINUAS. La mayor parte de las funciones que manejamos, a nivel elemental, presentan en sus gráficas una propiedad característica que es la continuidad. La continuidad de una función definida Más detalles Aplicaciones Lineales
Aplicaciones Lineales Primeras definiciones Una aplicación lineal de un K-ev de salida E a un K-ev de llegada F es una aplicación f : E F tal que f(u + v) = f(u) + f(v) para todos u v E f(λ u) = λ f(u) Más detalles Ortogonalidad y Series de Fourier
CONTENIDOS MÍNIMOS BACHILLERATO I.E.S. Vasco de la zarza Dpto. de Matemáticas CURSO 2013-14 ÍNDICE Primero de Bachillerato de Humanidades y CCSS...2 Primero de Bachillerato de Ciencias y Tecnología...5 Más detalles MATEMÁTICA DISCRETA: Conjuntos, combinatoria y grafos. Roberto J. de la Fuente López. Versión 20110923. (corrección de erratas a versión 20100712)
MATEMÁTICA DISCRETA: Conjuntos, combinatoria y grafos Roberto J. de la Fuente López Versión 20110923 (corrección de erratas a versión 20100712) Índice general PRESENTACIÓN... 5 AVISO DE DERECHOS DE AUTOR... Más detalles Capítulo 4 MEDIDA DE MAGNITUDES. Autor: Santiago Ramírez de la Piscina Millán
Capítulo 4 MEDIDA DE MAGNITUDES Autor: Santiago Ramírez de la Piscina Millán 4 MEDIDA DE MAGNITUDES 4.1 Introducción El hecho de hacer experimentos implica la determinación cuantitativa de las magnitudes Más detalles 2016 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución