lunes, 26 de septiembre de 2011

Delbert Ray Fulkerson



Delbert Ray Fulkerson (*14 de agosto de 1924 - †10 de enero de 1976) fue un matemático estadounidense que desarrolló como co-autor, y junto conLester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.
Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. En 1956, su importante artículo científico fue publicado.1 Desde 1979, laSociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta.

Lester Randolph Ford Jr. al continuar los pasos de su padre Ford Sr. también hizo una enorme contribución al campo de las matemáticas. Su trabajo con Delbert RayFulkerson (14 agosto de 1924 - 10 Enero de 1976) ha puesto la base de casi toda la investigación en flujos de grafos. El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas (Leyes de Kirchhoff), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio de conservación de energía), excepto para el nodo fuente y el nodo sumidero.
Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Una red de flujo es un grafo dirigido G=(V,E) donde cada arco (u,v) perteneciente a E el número de arcos del grafo; tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. Este algoritmo depende de tres conceptos principales:
  • Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo.
  • La capacidad residual es la capacidad adicional de flujo que un arco puede llevar c_f (u,v) = c(u,v) - f(u,v)
  • Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
El algoritmo es iterativo, se comienza con f(u,v)=0 para cada par de nodos y en cada iteración se incrementa el valor del flujo buscando un camino de aumento. El proceso se repite hasta no encontrar un camino de aumento.

Lester Randolph Ford, Jr




Lester Randolph Ford, Jr. (nacido el 23 de septiembre 1927, Houston ) es un americano matemático especializado en el flujo de red problemas. Él es el hijo del matemático Lester R. Ford, padre .
El papel de Ford con DR Fulkerson en el problema de flujo máximo y el algoritmo de Ford-Fulkerson para resolverlo, publicado como un informe técnico en 1954 y en un diario en 1956, estableció elmáximo de flujo min de corte teorema . Con Richard Bellman , Ford también desarrolló el algoritmo de Bellman-Ford para encontrar los caminos más cortos en los gráficos que tienen bordes negativamente ponderado.

Lester R Ford fue educado en la Escuela Normal del Estado de Missouri (donde se graduó Pd.B., es Licenciado en Pedagogía) y luego asistió a la Universidad Estatal de Missouri. Se graduó con una licenciatura en 1911, luego continuó sus estudios de grado de Maestro.
Fue galardonado con una maestría en el Departamento de Matemáticas de la Universidad de Missouri-Columbia en 1912 con una tesis sobre el punto-sabio funciones discontinuas. A continuación, realizó una investigación en la Universidad de Harvard con Maxime Bôcher como su consejero, y se graduó en 1913, MA. Desde 1914 fue profesor en la Universidad de Edimburgo en Escocia, donde fue nombrado como profesor junior en Matemáticas por la muerte de John Urquhart. El siguiente artículo apareció en una revista estudiantil de Edimburgo llamado El Gambolier [ 2 ]: -
No es frecuente que se llenan las vacantes, o aumentar el personal de nuestra Universidad a través del Atlántico. De hecho, es más bien para que los recursos de América cuando se requiere un hombre particularmente brillante o de las autoridades de una de sus instituciones educativas. No pocos de nuestros mejores hombres han ido allí y han entrado en las cátedras de inmediato. Tal estado de cosas dice mucho de la eficiencia general de nuestro personal docente, y el hecho de que en esta ocasión nos hemos ido a los Estados Unidos para nuestro nuevo profesor de matemáticas implica brillantez excepcional en el caballero que ha sido elegido.
Sr. Lester R Ford, el profesor en cuestión, fue nombrado en la sucesión del fallecido John Urquhart, MA, cuya repentina y lamentó la muerte durante las vacaciones de verano, que era nuestro deber melancolía para grabar en la primera edición de 'El Gambolier' de la presente sesión.
Sr. Ford, como la nación proverbial, es feliz en el hecho de que no tiene historia. Por lo que hemos podido descubrir, él nunca ha matado a un hombre, o se rompe en un banco, o incluso intentó suicidarse, pero se ha logrado desde 1886, cuando se lanzó por primera vez en este mar tempestuoso de la vida, en la acumulación una colección de títulos raros, y una colección aún más extraño de la tradición matemática que ahora está ocupada con pala en el cráneo de los estudiantes no demasiado entusiasta.
El Sr. Ford nació en el Estado de Missouri, EE.UU., y la mayor parte de su educación fue adquirida en dicho Estado. En la Escuela del Estado de Missouri normal que comenzó su carrera triunfal de honores académicos por graduarse Pd.B., que traducido, significa Licenciatura en Pedagogía. A partir de ese seminario, pasó a la Universidad del Estado de Missouri, en la que se graduó de licenciatura en 1911, y AM en 1912. A continuación, procedió a la Universidad de Harvard, donde pasó dos años, se graduó MA en 1913, y ganar una beca que le faculta para estudiar en el extranjero. Y aquí está él, y me alegro de hecho vamos a darle la bienvenida como un maestro en nuestra Universidad.
El Sr. Ford no se jacta de cualquier destreza como deportista, a menos de ajedrez puede ser colocado en esa categoría. Después de las matemáticas, el ajedrez es su hobby, y que jugó ese juego en el equipo de ajedrez de Harvard. Si la gran Universidad Americana otorga un "azul" para la competencia en ese juego o no, no lo sé, pero no tenemos ninguna duda de que nuestro nuevo profesor se merecía al menos uno. Como un hombre al Sr. Ford con su amable sonrisa de bienvenida y la disposición genial, es una gran adquisición para nuestra Alma Mater, y como ya ha expresado su gusto por la ciudad en la que se encuentra su casa actual, confiamos en que siempre será capaz de mantenerlo en nuestro medio.
Fue durante su período en Edimburgo que se unió a la Sociedad Matemática de Edimburgo en diciembre de 1914. Ford leer el periódico en las raíces de un derivado de una función racional en la reunión de la Sociedad el viernes 14 de mayo de 1915, el documento sobre las funciones de oscilación derivada de una función discontinua a la reunión del 11 de junio de 1915, y el papel de un método de resolución de ecuaciones algebraicas a la reunión del 12 de enero de 1917.
Ha publicado una introducción a la teoría de funciones automorfas como un tracto Matemática de Edimburgo n º 6 en 1915. AC Dixon escribe en un comentario: -
Se comprende fácilmente que cualquiera por escrito una extensión de noventa páginas sobre un tema con tan amplias ramificaciones debe elegir entre la compresión y la compresión excesiva juiciosa. El Sr. Ford ha optado por esta última, y ​​ha dedicado la mayor parte de su espacio a un tratamiento cuidadoso de las materias de introducción, con lo que, probablemente, haciendo su libro más útil, para el estudiante que quiere ir más allá, que nos ha proporcionado una bibliografía muy completa.
Ford leyó un documento a la Sociedad Matemática de Edimburgo en una clase de las fracciones continuas en la segunda reunión de la sesión 1916-1917. Ford volvió a los Estados Unidos y terminó el trabajo de doctorado en la Universidad de Harvard. Obtuvo su doctorado en 1917 por su tesis en aproximaciones racionales para un número complejo irracional. Un papel importante basado en su tesis de aproximaciones racionales a irracionales números complejos fue publicado en la operaciones de la American Mathematical Society en 1918. El documento, presentado en 1917, da la dirección de Ford en la Universidad de Edimburgo. En 1919 publicó Matemática elemental para la artillería de campo que se ha preparado y publicado por la dirección del Jefe de Artillería de Campaña, la Escuela de Oficiales de Artillería de Campaña Centro de Formación, el campamento de Zachary Taylor, Kentucky. Fue un curso muy útil: -
Acerca de 15 000 estudiantes tomaron el curso de los tres meses anteriores a la firma del armisticio. El personal de instructores, reclutados principalmente entre los candidatos con formación matemática, de ordinario más de un centenar, y en un momento eran tantos como ciento sesenta y nueve.
Después de su contribución al esfuerzo de guerra, Ford se unió a la facultad en el Instituto Rice, Houston, Texas, y aunque publicó documentos tales como la cercanía de enfoque de la complejidad fracciones racionales de un número complejo irracional (1925), la solución de ecuaciones por el método de aproximaciones sucesivas (1925), en los movimientos que responden a la primera y segunda de Kepler (1927-1928), y los puntos límite de un grupo (1929). Se casó con Margarita Leonor John (nacido el 26 de enero de 1890 a un Robert John y Margaret Morrow Houston) el 15 de junio de 1924; sus hijos son Lester Randolph Ford (nacido el 23 de septiembre de 1927 en Houston), Houston y Margaret Ford (nacido el 03 de septiembre 1930 ). Lester Randolph Ford, Jr. se convirtió en un destacado matemático que trabajaba para la RAND Corporation.
Dos libros importantes publicados por Ford son las funciones automorfas (1929) y Ecuaciones Diferenciales (1933, segunda edición 1955).

Además de su trabajo en el punto sabio funciones discontinuas que hemos mencionado anteriormente, Ford es conocida por una "interpretación geométrica absolutamente maravilloso de la serie Farey". Esta interpretación geométrica vino de la introducción de los círculos de Ford. Introdujo el concepto en un artículo de 1938 llamado "fracciones" [Ford, LR (1938) las fracciones. La American Mathematical Monthly. vol. 45, N º 9, páginas 586-601].
A fines de 1930 Ford se trasladó del Instituto de arroz al Instituto Armour of Technology en Chicago, Illinois, donde fue nombrado Profesor y Director del Departamento de Matemáticas. En 1940 el Instituto de Tecnología de blindaje se fusionó con el Instituto de Lewis (que había sido fundada en 1896) para formar el Instituto de Tecnología de Illinois. Él había ganado una reputación como un excelente expositor y escribió artículos pendientes, así como contribuyendo muchos problemas matemáticos y sus soluciones.
De 1942 a 1946 Ford fue editor de la American Mathematical Monthly. Cuando cumplió cinco años de servicio escribió Retrospect (Amer. Matemáticas. mensual 53 (10) (1946), 582 hasta 585) en la que describía la experiencia. Escribió: -
Este es el último número de la revista mensual que aparecen bajo mi dirección editorial. Como hago una pausa y mirar hacia atrás en los últimos cinco años, y mientras que los detalles están frescos en mi mente, parece oportuno establecer una relación de los lectores algo de la historia de este período lleno de acontecimientos. Mi editorial se ha extendido por los años de guerra. El ataque japonés a Pearl Harbor ocurrió mientras el primer número se está estableciendo en el tipo. Somos la prueba de lectura en el último número, mientras que los tratados de paz se están debatiendo en un mundo roto. Los cuatro docenas de problemas entre ellos se produjeron en medio de toda clase de dificultades engendradas por la guerra. Si el editor que tomó posesión de su cargo tan alegremente hace cinco años podía haber previsto el futuro, ¿habría retrocedido de la tarea? No estoy seguro.


http://www.gap-system.org/~history/Biographies/Ford.html
http://en.wikipedia.org/wiki/L._R._Ford,_Jr.
http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford


miércoles, 21 de septiembre de 2011

Biografía Robert W. Floyd

ROBERT W. FLOYD

Robert W (Bob) Floyd (8 jun 1936 a 25 sept 2001) fue un eminente científico de la computación.
Sus contribuciones incluyen el diseño del algoritmo de Floyd-Warshall (independientemente de Stephen Warshall), que se encuentra de manera eficiente todas las trayectorias más cortas en un gráfico , el ciclo de investigación de Floyd algooritmo para detectar ciclos en una secuencia, y su trabajo en el análisisEn un documento aislado que introdujo el concepto importante de difusión de errores para las imágenes de la representación, también llamado Floyd-Steinberg tramado (a pesar de que distinguidos tramado de difusión). Un logro importante fue pionero en el campo de la verificaciín de programas con afirmaciones lógicas con el artículo de 1967 asignar significados a los programas . Esta fue una importante contribución a lo que más tarde se convirtió en la lógica de Hoare.

Nacido en Nueva York, Floyd terminó la escuela a los 14 años. En la Universidad de Chicago, recibió una licenciaturaen artes liberales en 1953 (cuando todavía sólo 17) y una licenciatura en segundo la física en 1958.
Floyd se convirtió en un miembro del personal de la Fundación Armour Research (ahora IIT Research Institute) en el Illinois Institute of Technology en 1950. Convertirse en un operador de computadoras en la década de 1960, comenzó a publicar numerosos trabajos dignos de mención y fue nombrado profesor adjunto en la Universidad Carnegie Mellon en el momento en que tenía 27 años y se convirtió en catedrático en la Universidad de Stanford, seis años después. Obtuvo este puesto de trabajo sin Ph.D.
Recibió el Premio Turing en 1978 "para tener una clara influencia sobre las metodologías para la creación de software eficiente y fiable, y para ayudar a encontrar los siguientes subcampos importantes de la informática: la teoría del análisis, la semántica de los lenguajes de programación, automático programa verificación, automática síntesis de programas y análisis de algoritmos".
Floyd trabajó en estrecha colaboración con Donald Knuth, en particular, como el usuario principal para el libro seminal de Knuth The Art of Computer Programming, y es la persona más citada en este trabajo. Él fue el co-autor, junto con Richard Beigel, del libro de texto El lenguaje de las máquinas: una Introducción a la Computabilidad y lenguajes formales (1994, WH Freeman and Company,ISBN 978-0716782667).
Floyd casado y divorciado dos veces, incluso con equipo científico Floyd Christiane, y tuvo cuatro hijos. Sus pasatiempos incluyen ir de excursión y que era un ávido backgammon jugador:
Que una vez quedamos atrapados en el aeropuerto O'Hare de Chicago durante horas, esperando nuestro vuelo para salir, debido a una tormenta de nieve. Cuando nos sentamos en nuestra puerta, Bob me preguntó, de manera casual ", que saben cómo jugar al backgammon?" Yo le respondí que sabía las reglas, pero ¿por qué quieres saber? Bob dijo que ya que teníamos que esperar varias horas tal vez deberíamos jugar algunos juegos, en pequeñas cantidades, por supuesto. Luego buscó en su maletín y sacó un juego de backgammon.
Mi papá me enseñó muchas cosas. Uno de ellos fue a desconfiar de cualquiera que sugiera una partida de billar por dinero, y luego se abre un estuche negro y comienza a atornillar un palo de billar. Me di cuenta de que este consejo generalizado a todo el que viajaba con su juego de backgammon propia. Le dije a Bob que yo no iba a jugar por dinero, no hay manera.Empujó un poco, pero finalmente la multa. Se procedió en lugar de darme una lección libre en el arte y la ciencia de jugar backgammon.
Yo tenía razón para pasar a jugar él por dinero en cualquier juego. La lección fue muy divertido. Más tarde me enteré que durante años había estado trabajando en el aprendizaje del juego. Él tomó muy en serio a jugar backgammon, estudiado el juego y sus matemáticas, y fue casi un profesional. Creo que fue más que un pasatiempo. Al igual que su investigación, Bob tuvo lo que él hizo en serio, y es totalmente coherente que iba a ser terrible en el backgammon.
http://en.wikipedia.org/wiki/Robert_W._Floyd
http://www.systemcomputing.org/turing%20award/robert_1978/Robert.htm 

miércoles, 14 de septiembre de 2011

Edsger Dijsktra



Dijkstra estudió física teórica en la Universidad de Leiden . Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de Texas en Austin,Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.

Entre sus contribuciones a la informática está la solución del problema del camino más corto, también conocido como el algoritmo de Dijsktra, la notación polaca inversa y el relacionado algoritmo shunting yard, The mulripeogramming system, el algoritmo del baquero y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema. El algoritmo de Dijkstra es usado en la ruta más corta primero(SPF) que es usado en el protocolo de enrutamiento Open Shoetest Path First(OSPF). También se le debe la autoría de la expresión "Crisis del software", aparecida en su libro The Humble Programmer y usada ampliamente en la famosa reunión de la OTAN de 1968 sobre desarrollo del software. Recibió el Premio Turing en 1972.

Era conocido por su baja opinión de la sentencia GOTO en programación, que culminó en 1968 con el artículo Go To Statement Considered Harmful, visto como un paso importante hacia el rechazo de la expresión GOTO y de su eficaz reemplazo por estructuras de control tales como el bucle while. El famoso título del artículo no era obra de Dijkstra, sino de Niklaus Wirth, entonces redactor de Comunicaciones del ACM. Dijkstra era un aficionado bien conocido de ALGOL, y trabajó en el equipo que desarrolló el primer compilador para este lenguaje. En ese mismo año creó el primer sistema operativo con estructura jerárquica, de niveles o capas. Fue denominado THE (Technische Hogeschool, Eindhoven) que se utilizó con fines didácticos.

Desde los años 1970, el principal interés de Dijkstra fue la verificación formal. La opinión que prevalecía entonces era que uno debe primero escribir un programa y seguidamente proporcionar una peueba matemática de su correccion. Dijkstra objetó que las pruebas que resultan son largas e incómodas, y que la prueba no da ninguna comprensión de cómo se desarrolló el programa. Un método alternativo es la derivación de programas, «desarrollar prueba y programa conjuntamente». Uno comienza con una especificación matemática del programa que se supone va a hacer y aplica transformaciones matemáticas a la especificación hasta que se transforma en un programa que pueda ser ejecutado. El programa que resulta entonces es sabido correcto por la construcción. Muchos de los últimos trabajos de Dijkstra tratan sobre las maneras de hacer fluida la argumentación matemática.

Respecto a su caracter árido y ácido, conocidas son su oposición a la instrucción GO TO y al lenguaje BASIC ("mutila la mente más allá de toda recuperación"). Alan Kay expuso que "en informática, la arrogancia se mide en nanodijsktras".

Dijkstra murió el 6 de agosto de 2002 después de una larga lucha contra el cáncer.

martes, 13 de septiembre de 2011

Algoritmo de Prim






Robert C. Prim (n 1921, Sweetwater, Estados Unidos) es un matemático e ingeniero informático. En 1941 se licenció en ingenieria eléctrica en la Universidad de Princeton. Más tarde, en 1949 recibe su doctorado en matemáticas en la misma universidad. Trabajó en dicha universidad desde 1948 hasta 1949 como investigador asociado. En plena Segunda Guerra Mundial, Prim trabajó como ingeniero para General Electric. Desde 1944 hasta 1949 fue contratado por la United States Naval Ordnance Lab como ingeniero y más tarde como matemático. En los laboratorios Bell, trabajó como director de investigación matemática desde 1958 hasta 1961. Allí Prim desarrolló el conocido Algoritmo de Prim. Después de su estancia en los laboratorios Bell, Prim pasó a ser vicepresidente de investigación en Sandia National Laboratories. Durante su carrera en los laboratorios Bell, Robert Prim junto a su compañero Joseph Kruskal desarrolló dos algoritmos diferentes para encontrar los árboles abarcadores mínimos en un grafo ponderado. El algoritmo que lleva su nombre fue originalmente descubierto por el matemático Vojtech Jarnik y más tarde e independientemente por Prim en 1957. Dos años más tarde fue redescubierto por Edsger Dijkstra.

El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.
http://es.wikipedia.org/wiki/Algoritmo_de_Prim

miércoles, 7 de septiembre de 2011

Participación 8

  1. Hay tres refinerías con capacidad diarias de 6, 5 y 8 millones de galones, respectivamente, que abastecen a tres áreas de distribución cuyas demandas diarias son 4, 8 y 7 millones de galones, respectivamente. La gasolina se transporta por una rede de oleoductos a las tres áreas de distribución. El costo de transporte es de 10 centavos por 1000 galones por milla de oleoducto. En la siguiente tabla se ven las distancias entre refinerías y las áreas de distribución. La refinería 1 no está conectada con el área de distribución 3.

Modelo de Programación Líneal

Min z= 1.2X11 + 1.8Z12 + 3X21 + X22 + .8X23 + 2X31 + 2.5X32

Sujeto a:
X11 + X12 = 6
X21 + X22 + X23 = 5
X31 + X32 + X33 = 8
X11 + X21 + X31 = 4
X12 + X22 + X32 = 8
X23 + X33 = 7

Xij ≥ 0


RED


Solución Inicial
Z= 24,300,000

X11=4,000,000
X12=2,000,000
X22=5,000,000
X32=1,000,000
X33=7,000,000

Participación 7

Dos plantas abastecen a tres clientes con suministros médicos. Las GANANCIAS unitarias, junto con los suministros y demandas se dan en la siguiente tabla:


Esquina Noroeste

Z= 2000
X11=10
X12=10
X13=10
X1f=5
X2f=50

Costos Mínimos
Z= 2000
X21=10
X22=10
X23=10
X1f=5
X2f=50


Vogel


Z= 2000
X21=10
X22=10
X23=10
X1f=5
X2f=50




Participación 6

Pasos para el metodo de costos minimos:

1)      Revisar que el problema este equilibrado
2)     Identificar la celda con costo mínimo
3)    Se satura la fila o columna donde este el coto mínimo, para saturarla se escoge entre el     valor más pequeño entre oferta y demanda de la casilla que hayamos escogido, y el valor   mínimo de oferta o demanda escogido lo escribimos en la casilla seleccionada
4)    Se marca o se tacha la fila o columna que hayamos saturado
5)    Restamos el valor mínimo escogido al valor de la oferta y demanda
6)    Identificamos la siguiente celda con costo menor y que no haya sido marcada
7)     Repetir a partir del paso 2
8)     Si existen dos celdas o más no marcadas y el costo mínimo es el mismo , se escoge            arbitrariamente cualquiera de estas y se sigue el procedimiento
9)    Si una columna y renglón se saturan a la vez solo se marca o tacha la columna o el renglón
     El método termina hasta que todas las casillas estén saturadas







Tabla de Solución Inicial:

Solución
X11= 5
X12=45
X21=15
X23=20
X33=10
X34=30                                  Z=1015

La diferencia esta en la Z, en la participacion 5 Z=1090 y en esta Z=1015, lo que se puede decir es que es mejor este método, ya que, como nuestro objetivo es minimizar costos, con este método se logra más rapido sin hacer tantas iteraciones y es más fácil llegar a la solución óptima.

martes, 6 de septiembre de 2011

Tabla Resumen

Tabla resumen: Problema de Asignación
Características
Observación
Página
Historia del modelo

En 1941 F. L. Hitchcock publica una solución analítica a este problema
En 1972 Thomas Jefferson quien lo sugirió para asignar a cada representante por estado.
Debe su nombre a asignar hombres a trabajos
La estructura particular del problema hace que las soliciones  sean degeneradas y permitió a los matematicos húngaros Köning y Egerváry demostrar un teorema esencial para el desarrollo del Método Húngaro.
Elementos
·         Consiste en asignar recursos a tarea en función de un objetivo ligado a la eficiencia del sistema
·         Minimizar el costo total de operación de modo que: cada tarea asigne a una y sólo una máquina, cada máquina realice una y sólo una tarea
·        
·         Matriz de costos
·         Debe ser balanceado para que la matriz de costos sea cuadrada
Ejemplo
Un ejemplo típico es el de asignación de personas a turnos horarios, o el de asignar personas a maquinas.
En un cierto punto del algoritmo tenemos el grafo G \, y la matriz C^\prime\,.
http://upload.wikimedia.org/wikipedia/commons/6/63/Matching_maximo.PNG
matching máximo del grafo de las igualdades.
C'=\begin{pmatrix}
  1 & 2 & 7 & 3 & 0    \\
  3 & 4 & 1 & 0 & 2    \\
  2 & 3 & 6 & 0 & 0    \\
  0 & 6 & 1 & 1 & 0    \\
  2 & 0 & 0 & 4 & 5    \end{pmatrix}

En G \, tengo un arco \Longleftrightarrow \; tengo un 0 \, enC^\prime\,.

M =\{ (1,5'), (2,4'), (4,1'), (5,3') \}\, es matching máximo pero no es perfecto, pues la fila 3 está sin asignar. \Rightarrow \; volvemos al paso (3) \, del algoritmo.

(a) \,
\begin{pmatrix}
          &   &   &   &        &         \\
          & 1 & 2 & 7 & 3      & 0       \\
          & 3 & 4 & 1 & 0      & 2       \\ 
 \star \; & 2 & 3 & 6 & 0      & 0       \\
          & 0 & 6 & 1 & 1      & 0       \\
          & 2 & 0 & 0 & 4      & 5       \end{pmatrix} \Rightarrow \;
(b) \,
\begin{pmatrix}
          &   &   &   & \star\;&  \star\;\\
          & 1 & 2 & 7 & 3      & 0       \\
          & 3 & 4 & 1 & 0      & 2       \\ 
 \star \; & 2 & 3 & 6 & 0      & 0       \\
          & 0 & 6 & 1 & 1      & 0       \\
          & 2 & 0 & 0 & 4      & 5       \end{pmatrix} \Rightarrow \;

(c) \, El matching de las columnas 4'\, y 5'\, esta acopladas al de las filas 1\, y 2 \Rightarrow \;

(d) \,
\begin{pmatrix}
          &   &   &   & \star\;&  \star\;\\
 \star \; & 1 & 2 & 7 & 3      & 0       \\
 \star \; & 3 & 4 & 1 & 0      & 2       \\ 
 \star \; & 2 & 3 & 6 & 0      & 0       \\
          & 0 & 6 & 1 & 1      & 0       \\
          & 2 & 0 & 0 & 4      & 5       \end{pmatrix} \Rightarrow \;
(e) \,
\begin{pmatrix}
          &   &   &   & \star\;&  \star\;\\
 \star \; & 1 & 2 & 7 &       &        \\
 \star \; & 3 & 4 & 1 &       &        \\ 
 \star \; & 2 & 3 & 6 &       &        \\
          &   &   &   &       &        \\
          &   &   &   &       &        \end{pmatrix} \Rightarrow \;
(f) \,
\delta =min \begin{pmatrix}
                   1 & 2 & 7 \\
                   3 & 4 & 1 \\
                   2 & 3 & 5 \end{pmatrix}= 1
(g) \, Resto \delta\, a los elementos no borrados de C^\prime\, y sumo \delta\, a los elementos doblemente borrados de C^\prime\,.

C'=\begin{pmatrix}
 0 & 1 & 6 & 3 & 0    \\
 2 & 3 & 0 & 0 & 2    \\
 1 & 2 & 5 & 0 & 0    \\
 0 & 6 & 1 & 2 & 1    \\
 2 & 0 & 0 & 5 & 6    \end{pmatrix}  \Rightarrow \;

(h) \, Volvemos al paso (1) \,, para recrear el grafo de las igualdades y calcular de nuevo el matching máximo.



Método de Solución
Método Simplex
Técnica del transporte
Método Húngaro
(1) \, Dada la matriz de costes C \,, se construye C^\prime\, encontrando el valor mínimo de cada fila y restando ese valor a cada elemento de la fila.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C}_{i,j}-\min \mathit{C}_{i,j}
 ( 2 ) \, Se encuentra el valor mínimo de cada columna y se resta a cada elemento de la columna.
\Rightarrow \; \mathit{C'}_{i,j}=\mathit{C'}_{i,j}-\min \mathit{C}_{i,j}
(3) \, A partir de \mathit{C'}\, se considera "grafo de las igualdades" a G=(N1,N2,A) \, tal que A \, está constituido por todas las copias ({i,j})\, tales que \mathit{C'}_{i,j}=0 \,. En otras palabras, verificamos si para todas las filas existe una columna con costo 0 que no ha sido asignada a otra fila.
Determinar sobre G\, un matching M\, de cardinalidad máxima.

si |\mathit{M}| = |N_1| = |N_2| \Rightarrow \;  STOP
Si todas las filas tienen a lo menos una intersección con costo cero que no ha sido ocupada por otra fila, estamos en el óptimo. Termina el algoritmo.

(a) \, Considero C^\prime\, y se etiquetan las filas que no han sido acopladas o asignadas por el algoritmo de matching máximo.
(b) \, Se etiquetan en C^\prime\, las columnas que tienen los ceros en correspondencia o asignadas a las filas etiquetadas (con *).
(c) \, Etiquetar las filas que no han sido ya etiquetadas y acopladas o asignadas por el algoritmo de matching máximo con las columnas ya etiquetadas (con *).
(d) \, Repetir los pasos (b) \, y (c) \, hasta que no halla más filas o columnas que etiquetar.
(e) \, Borrar las filas etiquetadas y las columnas NO etiquetadas. Para esto puede trazar una línea recta en las columnas y filas borradas.
(f) \, Sea \delta\, el elemento de C^\prime\, de valor mínimo entre aquellos costos no borrados (o tarjados) en el paso anterior.
(g) \, Restar \delta\, a cada elemento no borrado y sumarlo a los elementos doblemente borrados (o donde haya intersección o cruces entre las líneas marcadas en el paso (e) \, )
(h) \, Volver al paso (1) \,.





Programas existentes
El programa InvOp (361 kb)
Win QSB
TORA
LINDO
SB2