Para poder ver el proyecto da clic al siguiente enlace:
Proyecto Final
Este proyecto trata sobre una aplicación de redes de optimización, este trabajo incluye el planteamiento, su solución, la interpretación y sus conclusiones.
martes, 13 de diciembre de 2011
viernes, 25 de noviembre de 2011
Boletín: Programación Dinámica
Este enlace es para ir un boletín que servirá de ayuda para comprender la programación Dinámica
http://www.calameo.com/read/0010291958b09fd93839c
http://www.calameo.com/read/0010291958b09fd93839c
martes, 22 de noviembre de 2011
Ailsa H. Land y Alison G. Doig
Ailsa H. Land y Alison G. Doig
En 1960 ,Land y Doig presentan el algoritmo de Ramificación y acotamiento que estaba basado en el procedimiento sobre la base de una enumeración inteligente del espacio de búsqueda. 1965 RJ Dakin se le hizo fácil implementar el algoritmo y más tarde, Rama y atado con métodos de reducción de avión a la rama y corte combinado, permitiendo que la solución significativamente más grandes programas lineales enteros.
En el libro 50 YEARS OF INTEGER PROGRAMMING 1958-2008, Land y Doig escribieron su artículo en 1960 "Un método automático de la solución de problemas discretos de programación" (An Automatic Method for Solving Discrete Programming Problems). En: Econometrica, Bd. 28 (1960), S. 497 a 520.
Este contiene una introducción de Land y Doig:
A finales de 1950 había un grupo de profesores y asistentes de investigación en la London School of Economics interesado en la programación lineal y sus extensiones, en particular Makower Helen, George Morton, Ailsa Land y Alison Doig. Se había considerado el problema "Servicio de lavandería Van" hasta que se descubrió que era conocido como el problema del viajante, y se habían mirado horarios de aviones, este problema superaba su capacidad fue entonces que Alison Doig (ahora Harcourt) ya había estudiado el problema de corte de papel para su proyecto final de carrera en Melbourne antes de llegar a Inglaterra.
Información Obtenida de:
http://www.springerlink.com/index/w37378vx8145465l.pdf
http://www.or.ms.unimelb.edu.au/index.php?page_ref_id=157
http://de.wikipedia.org/wiki/Ganzzahlige_lineare_Optimierung
Biografía de Balas
Egon Balas
Nacido en Rumania de una familia húngara, Egon Balas se ha unido a las filas del partido comunista húngaro y de la resistencia anti-nazi durante la Segunda Guerra Mundial. Su autobiografía narra su detención por los nazis, su encarcelamiento, las sesiones de tortura que sufrió, y su fuga poco antes de la llegada de las tropas rusas.
Después de la guerra, Egon Balas rápidamente ascendió en las filas de los ministerios de Rumania, y ocupaba un puesto diplomático en Londres, antes de ser detenido nuevamente, esta vez por las autoridades rumanas comunistas inspirados por el mal ejemplo de las purgas estalinistas en la URSS.Dos años de confinamiento solitario y de los tratamientos bárbaros no fueron capaces de romper esa personalidad de acero duro, que obstinadamente se negó a cooperar en la puesta en escena de un juicio falso. Liberado después de la muerte de Stalin, pero desencantado por los excesos del régimen comunista, Egon Balas comenzó su nueva vida como economista y matemático hecho a sí mismo en Bucarest. Después de varios intentos infructuosos, se le permitió por fin a salir de Rumanía en los años 1960 y emigrar a los EE.UU., donde desarrollaría su prolífica producción científica en la optimización matemática.
Egon Balas es profesor en la Escuela de Negocios Tepper de Carnegie Mellon University, donde se lleva el título de "Profesor de la Universidad Industrial de Administración y Matemática Aplicada" y "Señor Thomas Profesor de Investigación de Operaciones". Tiene un Doctorado en Economía por la Universidad de Bruselas y un Doctorado en Matemáticas de París. Sus obras se encuentran en la encrucijada de estas dos disciplinas, en el campo de la investigación de operaciones, más precisamente en la optimización matemática y sus aplicaciones en el mundo económico. Durante más de 40 años, Egon Balas ha sido uno de los pioneros de todos los desarrollos teóricos más importantes y de los enfoques más innovadores algoritmos de optimización. Su nombre está ligado a la diversidad de enfoques con nombres esotéricos - programación disyuntiva, los métodos poliédricos, «de elevación y proyecto", "cuello de botella cambiando heurístico», entre otras, su investigación ha sido de más de 200 publicaciones científicas.
Egon Balas ha contribuido ampliamente a demostrar la utilidad de los modelos matemáticos en la práctica de la gestión, mediante la realización de numerosos estudios relacionados con la optimización de la producción en la industria del acero, en el transporte, las telecomunicaciones, en la industria petrolera o en las finanzas. Los desarrollos algorítmicos que ha iniciado, o con la que estaba estrechamente asociado, son hoy en día integrada en muchos paquetes de software empresarial que permiten a los administradores a optimizar la eficiencia de sus procesos de producción, con mayor frecuencia sin una plena comprensión de los complejos algoritmos de los que dependen .
Su liderazgo intelectual en todos estos campos le llevó, entre otras muchas distinciones de prestigio científico, la teoría de John Von Neumann Premio del Instituto de Investigación de Operaciones y las Ciencias de la Gestión y la Medalla de Oro de la Asociación Europea de Sociedades de Investigación Operativa.
Obtenido de:
http://tepper.cmu.edu/news-multimedia/tepper-stories/egon-balas-awarded-honorary-doctorate/index.aspx
viernes, 18 de noviembre de 2011
miércoles, 2 de noviembre de 2011
Biografía de Gomory
Ralph E. Gomory
Ralph E. Gomory, nació 07 de mayo 1929, en Brooklyn Heights, Nueva York. Se graduó del Williams College en 1950, estudió en la Universidad de Cambridge, y recibió su Ph.D. en matemáticas de la Universidad de Princeton en 1954. Gomory después sirvió en la Marina de Guerra (1954-57) y luego fue Profesor Higgins y profesor adjunto de matemáticas en Princeton antes de incorporarse a la recién creada División de Investigación de IBM en 1959 como investigador matemático.
En sus años de estudiantes y el estudiante graduado (Williams, Cambridge, Princeton), Gomory realizó investigaciones sobre ecuaciones diferenciales no lineales, pero sus años en la Marina volvió su atención a la matemática aplicada de la investigación de operaciones. De regreso en Princeton, obtuvo el primer plano de corte general de los algoritmos, que estableció el campo de la programación entera.Sigue siendo un área activa de investigación hoy en día.
En la investigación de IBM en la década de 1960, Gomory publicado trabajos con Paul Gilmore en el vendedor de la mochila, viajar y problemas de stock de corte, y con TC Hu sobre los flujos en redes multi-terminal y continua. A finales de la década de 1960, desarrolló la teoría asintótica de la programación entera e introdujo el concepto de la esquina de poliedros. A principios de la década de 1970, colaboró con Ellis Johnson en la investigación de las funciones relacionadas con los poliedros subaditiva esquina que también podrían desempeñar un papel en la producción de tecnología de los aviones.
Gomory se desempeñó como Presidente del Departamento de Matemática de Ciencias de Investigación de IBM 1965-67 y 1968-70 durante un período importante de su crecimiento y evolución.
Gomory ha sido director de varias compañías, incluyendo el Washington Post Company y el Banco de Nueva York. En la actualidad es director de Lexmark International, Inc., y de dos pequeñas empresas start-up. Fue nombrado uno de los diez mejores directores de Estados Unidos por la revista Alerta de Director en el año 2000.
Al tiempo que continúa sus investigaciones sobre Gomory programación entera se ha escrito sobre la naturaleza del desarrollo tecnológico, la competitividad de la investigación en la industria, e industrial, y en los modelos de comercio internacional en relación con los cambios tecnológicos y las economías de escala.Él es el autor, con el profesor William Baumol, de la industria del libro Global intereses nacionales en conflicto (MIT Press, 2001).
Gomory trabajó durante 30 años para IBM, comenzando como un investigador y el aumento en las filas para convertirse en jefe de la División de Investigación y, finalmente, vicepresidente senior de la ciencia y la tecnología. Se retiró de este último cargo en 1989 para convertirse en presidente de la Fundación Sloan.
En los intereses de investigación de Gomory han incluido programación entera y lineal, la teoría del flujo de red, las ecuaciones diferenciales no lineales, y las computadoras. En los últimos años se ha escrito sobre la naturaleza de la tecnología y el desarrollo de productos, investigación en la industria, la competitividad industrial, el cambio tecnológico, así como los modelos económicos de economías de escala.
Información tomada de:
domingo, 23 de octubre de 2011
Participación 11. Redes de Actividad.
1.- Una compañía esta planeando fabricar un producto que consiste en tres partes (A, B, C). La compañía anticipa que toma 5 semanas diseñar las tres partes y determinar la forma en que se deben ensamblar estas partes para conformar el producto. Entonces la compañía estima que tomara 4 semanas hacer la parte A, 5 semanas hacer la parte B y 3 semanas la parte C. la compañía debe probar la parte A después de su terminación (esto toma 2 semanas).así, el proceso de la línea de ensamblado procederá como sigue: ensamblar las partes A y B (dos semana) y luego añadir la parte C (una semana). Luego el producto final debe experimentar una semana de prueba. Trace la red de proyecto y encuentre la trayectoria crítica, el tiempo libre total y el tiempo libre para cada actividad. También prepare el PL que pudiera ser utilizado para determinar la trayectoria crítica.
| Actividad | Descripción | Act. antecesor | Tiempo (semanas) |
| a | Diseñar y determinar forma | --- | 5 |
| b | Hacer parte A | a | 4 |
| c | Hacer parte B | a | 5 |
| d | Hacer parte C | a | 3 |
| e | Probar A | b | 2 |
| f | Ensamblar A y B | c , e | 2 |
| g | Añadir C | d , f | 1 |
| h | Pruebas | g | 1 |
Tiempos de holgura:
a -> 0, b -> 0, c -> 1, d -> 5, e -> 0, f -> 0, g -> 0, h -> 0
Entonces como tiempo de holgura tenemos 6 semanas.
Modelo de Programación Lineal:
Participación 6. Flujo Máximo.
2. Tres refinerías envían un producto de gasolina a dos terminales de distribución a través de una red de ductos. Cualquier demanda que no se pueda satisfacer por medio de la red se adquiere de otras fuentes. Hay tres estaciones de bombeo que sirven a la red de ductos, como se muestra a continuación:
El producto fluye en la red en la dirección que muestran las flechas. La capacidad de cada segmento del ducto (que se muestra directamente en los arcos) es en millones de bbl al día. Determine lo siguiente:
a) La producción diaria en cada refinería que iguale la capacidad máxima de la red.
b) La demanda diaria en cada terminal que iguale la capacidad máxima de la red.
c) La capacidad diaria de cada bomba que iguale la capacidad máxima de la red.
d) Supongamos que la capacidad máxima diaria de la bomba 6 en la red se limita a 50 millones de bbl. Remodele la red para que incluya esta restricción. Después, determine la capacidad máxima de la red.
a) Refinería 1 = 20
Refinería 2 = 80
Refinería 3 = 10
b) Terminal 7 = 60
Terminal 8 = 50
c) Bomba 4 = 30
Bomba 5 = 30
Bomba 6 = 50
Refinería 2 = 80
Refinería 3 = 10
b) Terminal 7 = 60
Terminal 8 = 50
c) Bomba 4 = 30
Bomba 5 = 30
Bomba 6 = 50
d)
Participación 3. Ruta más corta de problemas no Clásicos.
2) Se tiene una red de comunicaciones entre dos estaciones 1 y 7. Las probabilidades de que un enlace de la red funcione sin fallar se muestran en la siguiente tabla. Los mensajes se mandan de la estación 1 a la estación 7 y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisión.
Estaciones | probabilidad | Estaciones | Probabilidad |
1,2 | 0.8 | 1,4 | 0.65 |
1,3 | 0.3 | 2,5 | 0.5 |
2,4 | 0.9 | 3,6 | 0.95 |
4,5 | 0.7 | 4,6 | 0.6 |
4,3 | 0.85 | 5,7 | 0.8 |
5,6 | 0.5 | 6,7 | 0.9 |
Plantear la red y resolver como un problema de ruta más corta.
R = { (1,2), (2,4), (4,3), (3, 6), (6, 7) }
Con una probabilidad del 52%
Participación 2. Problemas de ruta más corta.
3).- Encuentre la trayectoria más corta del nodo 1 al nodo 6.
Participación 1. Problemas de árbol de expansión mínima.
2. La maderera Wirehouse talará árboles en ocho zonas de la misma área. Para esto debe desarrollar un sistema de camiones de tierra para tener acceso a cualquier zona desde cualquier otra. La distancia ( en millas) entre cada par de zona es:
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | -- | 1.3 | 2.1 | 0.9 | 0.7 | 1.8 | 2.0 | 1.5 |
| 2 | 1.3 | -- | 0.9 | 1.8 | 1.2 | 2.6 | 2.3 | 1.1 |
| 3 | 2.1 | 0.9 | -- | 2.6 | 1.7 | 2.5 | 1.9 | 1.0 |
| 4 | 0.9 | 1.8 | 2.6 | -- | 0.7 | 1.6 | 1.5 | 0.9 |
| 5 | 0.7 | 1.2 | 1.7 | 0.7 | -- | 0.9 | 1.1 | 0.8 |
| 6 | 1.8 | 2.6 | 2.5 | 1.6 | 0.9 | -- | 0.6 | 1.0 |
| 7 | 2.0 | 2.3 | 1.9 | 1.5 | 1.1 | 0.6 | -- | 0.5 |
| 8 | 1.5 | 1.1 | 1.0 | 0.9 | 0.8 | 1.0 | 0.5 | -- |
El problema es determinar los pares de zonas entre los que deben construirse caminos para conectar todas con una longitud total mínima de caminos.
Suscribirse a:
Entradas (Atom)