sábado, 26 de noviembre de 2011
lunes, 14 de noviembre de 2011
Egon Balas
Estudios: Tiene un Doctorado en Economía por la Universidad de Bruselas y un Doctorado en Matemáticas de París
Trabajos: Profesor de Administración Industrial y Matemáticas Aplicadas (1968 -),
Señor Thomas Profesor de Investigación de Operaciones (1996 -), la Universidad Carnegie Mellon.
- Profesor, Instituto de Ciencias Económico y Planificación, Bucarest(1949 -1958), Ingeniero de Proyectos (1959-1961), Jefe de la
- Grupo de Programación Matemática (1962 -1964), Instituto de Diseño de Bosques y la Industria de la Madera (ISPF), Bucarest, Jefe de la
- Sector de Programación Matemática, Centro de Estadística Matemática de la rumanaAcademia de Bucarest (1964-1965), Ford Distinguido Profesor de Investigación (1967-1968),
- Profesor de la Cátedra GSIA Alumni (1980 -1996), profesor de la Universidad (1990 -), Carnegie Mellon University.
Conocido por: Programación matemática, en particular de programación entera, la optimización combinatoria, gráficos, redes, teoría poliédrica, la programación disyuntiva, la proyección y elevación, la teoría de la programación, ubicación de las instalaciones, la logística. Técnicas de solución para el embalaje de vértice y los problemas de máxima camarilla, viajando problemas de vendedores y afines, establece que cubren y la partición, los problemas de la mochila, en general 0-1 problemas de programación, la secuencia de la máquina, la programación de los satélites de comunicaciones, de las asignaciones de la tripulación.
sábado, 29 de octubre de 2011
Ralph E. Gomory
Fecha y Lugar de nacimiento:nació 07 de mayo 1929, en Brooklyn Heights, Nueva York
Estudios:estudió en la Universidad de Cambridge , y recibió su doctorado en matemáticas de la Universidad de Princeton en 1954.
Trabajos: Gomory trabajó en IBM como investigador y más tarde como ejecutivo.Durante ese tiempo, la investigación llevó a la creación de nuevas áreas de las matemáticas aplicadas.
Después de su carrera en el mundo corporativo, Gomory se convirtió en el presidente de la Fundación Alfred P.Sloan , donde supervisó los programas dedicados a mejorar la comprensión del público en tres áreas clave: la importancia económica de la ciencia y la investigación, los efectos de la globalización en los Estados Unidos y el papel de la tecnología en la educación.
Conocido por: 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
Referencias
miércoles, 19 de octubre de 2011
Participación 11, Redes de Actividad
Considere la red de proyecto para cada actividad, se dan las estimaciones de a, b y m en la tabla 18. Determine la trayectoria crítica para esta red, el tiempo libre total para cada actividad, el tiempo libre para cada actividad y la probabilidad de que el proyecto se complete en 40 días. También prepare el PL que se pueda utilizar para encontrar la trayectoria crítica.
Planteando la red y Realizando Revisión hacia adelante y Revisión hacia atrás obtenemos lo siguiente:
La ruta critica será:
Modelo de Programación Lineal
Min Z= x9-x1
s.a.
x2≥x1+6
x3≥x1+4.33
x4≥x2+3.33
x4≥x3+9
x5≥x3+10
x6≥x3+12.167
x7≥x4+8.83
x7≥x5+2
x8≥x6+3.33
x9≥x7+15
x9≥x8+8.833
xi≥0
Probabilidad de terminar en 40 días
µ=36.66
δ=4.837
x=40
Z=(x-µ)/δ=0.6905
P(x<0.6905)=.7549
La probabilidad de terminar en 40 dias es de 75%
lunes, 17 de octubre de 2011
viernes, 14 de octubre de 2011
viernes, 7 de octubre de 2011
domingo, 2 de octubre de 2011
Unidad 2. Participación 3
Encuentre la trayectoria más corta del nodo 1 al nodo 6
Resolviendo por el metodo de Dijkstra:
La trayectoria más corta del nodo 1 al nodo 6 es: 1-2-4-6 con un costo de 31
La trayectoria más corta del nodo 1 al nodo 6 es: 1-2-4-6 con un costo de 31
Unidad 2. Participación 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.
Plantear la red y resolver como un problema de ruta más corta.
Red:
Resolviendo por el método de Dijkstra
La ruta que maximice la probabilidad de una buena transmisión será: 1-2-4-3-6-7 y la probabilidad es de 0.52326
Red:
Resolviendo por el método de Dijkstra
Unidad 2. Participación 1
1. Las distancias en millas entre ciudades de Indiana: Gary, Fort Wayne, Evansville, Terre Haute y South Bend, se muestran en la siguiente tabla. Es necesario construir un sistema estatal de carreteras que una todas estas ciudades. Suponga que por razones políticas no es necesario construir una carretera a Gary y Fort ¿Cuál es la longitud mínima de la carretera requerida?
Resolviendo por Prim, obtenemos la siguiente red:
Las lineas marcadas por naranja son las carreteas que se deben construir , y el costo será de 414
Planteando la red:
Resolviendo por Prim, obtenemos la siguiente red:
Las lineas marcadas por naranja son las carreteas que se deben construir , y el costo será de 414
lunes, 26 de septiembre de 2011
Lester Randolph Ford, Jr.
Fecha y lugar de nacimiento: nacido el 23 de septiembre 1927, Houston
Trabajos: Se le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.
Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo.
Conocido por: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, 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.
Referencias
http://en.wikipedia.org/wiki/L._R._Ford,_Jr.
http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
Delbert Ray Fulkerson
Fecha y lugar de nacimiento: 14 de agosto de 1924 en Estados Unidos
Estudios: Recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951
Trabajos: En 1956, su importante artículo científico fue publicado. Desde 1979, la Sociedad 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
Conocido por: desarrolló como co-autor, y junto con Lester 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
Fecha de muerte: 10 de enero de 1976
Referenciashttp://es.wikipedia.org/wiki/D._R._Fulkerson
miércoles, 21 de septiembre de 2011
Robert W. Floyd
Fecha y lugar de nacimiento: Nacio en Nueva York el 8 de junio de 1936
Estudios: Floyd culminó bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958
Trabajos: Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford
Conocido por: Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en un grafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967«Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos
Fecha de muerte: 25 de septiembre de 2001
Referencias
http://es.wikipedia.org/wiki/Robert_W._Floyd
http://histsoc.stanford.edu/pdfmem/Floyd_Robert.pdf
viernes, 16 de septiembre de 2011
jueves, 15 de septiembre de 2011
Dénes König
Estudios: En 1907, recibió su doctorado en, y se unió a la facultad de la Escuela Superior Técnica de Budapest (hoy Universidad Técnica de Budapest ). Sus clases fueron visitadas por Paul Erdős , que, como estudiante de primer año, resolvió uno de sus problemas. König se convirtió en catedrático en 1935
Trabajos: Fue un judío húngaro matemático que trabajó y escribió el primer libro de texto en el campo de la teoría de grafos.
Conocido por: En la matemática área de teoría de grafos , el teorema de König , probado por Dénes König en 1931, describe una equivalencia entre el máximo juego problema y el mínimo problema de cobertura de vértices en grafos bipartitos
Fecha de muerte: 19 de octubre 1944 (60 años) en Budapest
Referencias
http://en.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nig
http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_(graph_theory)
http://es.wikipedia.org/wiki/Algoritmo_h%C3%BAngaro
Edsger Dijkstra
Lugar y fecha de nacimiento: Rotterdam, Paises Bajos, 11 de mayo de 1930
Estudios: Dijkstra estudió física teórica en la Universidad de Leiden.
Trabajos: 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.
Conocido por: 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 Dijkstra, la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero 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.
Lugar y fecha de muerte: Países Bajos, 6 de agosto de 2002
Algoritmo de Dijkstra
También llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con costos en cada arista.
El algoritmo de dijkstra determina la ruta más corta desde un nodo origen s hacia los demás nodos, las distancias se almacenan en un vector D. Básicamente, el algoritmo toma en la i-ésima iteración al nodo que tiene la menor distancia, Vi, y ve si es posible disminuir la distancia de sus nodos adyacentes, para hacerlo se verifica si la distancia hasta Vi más el costo para ir de i al nodo adyacente, w(i,j), es menor a la distancia actual en el nodo adyacente.
Referencias
miércoles, 14 de septiembre de 2011
Robert C. Prim
Fecha y lugar de nacimiento: En 1921, Sweetwater, Estados Unidos
Estudios: En 1941 se licenció en ingenieria electrica 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.
Trabajos: 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
Conocido por: 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.
Algoritmo de Prim
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 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.
Referencias
lunes, 12 de septiembre de 2011
viernes, 9 de septiembre de 2011
Jenő Egerváry
Fecha y lugar de nacimiento: nació en Debrecen en 1891.
Estudios: En 1914, recibió su doctorado en la Universidad Pázmány Péter en Budapest, donde estudió bajo la supervisión de Lipón Fejér
Trabajos: trabajó como asistente en el Observatorio Sismológico en Budapest, y desde 1918 como profesor en la Escuela Superior Industrial en Budapest. En 1938 fue nombrado Privatdozen en la Universidad Pázmány Péter en Budapest.
En 1941 se convirtió en catedrático de laUniversidad Técnica de Budapest, y en 1950 fue nombrado Presidente del Consejo Científico del Instituto de Investigación de Matemática Aplicada de la Acadmia Húngara de Ciencias.
Conocido por: Egerváry abarcó la teoria de las ecuaciones algebraicas, geometria, ecuaciones diferenciales y teoría de matrices.
En lo que más tarde se convirtió en un resultado clásico en el campo de la optimizacion combinatoria, Egerváry generalizado teorema de o y publicado en 1955 por Harold W. Kuhn, que también mostró cómo aplicar Konig s 'y el método Egerváry para resolver el problema de asignación, el algoritmo resultante ha sido conocido como el método Húngaro.
Fecha de muerte: 30 de Noviembre de 1958
Referencias
martes, 6 de septiembre de 2011
Participación 8
Resolución de problemas de transporte
Red
Modelo de programación
- 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.
Refinería \ Área de Distribución | 1 | 2 | 3 |
1 | 120 | 180 | -- |
2 | 300 | 100 | 80 |
3 | 200 | 250 | 120 |
Red
Min Z= 1.2x11+1.8x12+3x21+1x22+.8x23+2x31+2.5x32+1.2x33
s.a x11+x12=6000000
x21+x22+x23=5000000
x31+x32+x33=8000000
x11+x21+x31=4000000
x12+x22+x32=8000000
x23+x33=7000000
xij≥o
Tabla
Obteniendo la solución inicial por el método de Vogel, se llega a la siguiente tabla
Con Z=24300000
Aplicando el metodo de multiplicadores :
Como Zj-Cj≤0 se tiene la solución optima con Z=24300000
y
X11=4000000
X12=2000000
X22=5000000
X32=1000000
X33=7000000
La refinería 1 enviará 4 millones de galones a el área de distribución 1
La refinería 1 enviará 2 millones de galones a el área de distribución 2
La refinería 2 enviará 5 millones de galones a el área de distribución 2
La refinería 3 enviará 1 millón de galones a el área de distribución 2
La refinería 3 enviará 7 millones de galones a el área de distribución 3
La refinería 1 enviará 2 millones de galones a el área de distribución 2
La refinería 2 enviará 5 millones de galones a el área de distribución 2
La refinería 3 enviará 1 millón de galones a el área de distribución 2
La refinería 3 enviará 7 millones de galones a el área de distribución 3
lunes, 5 de septiembre de 2011
Biografía de Vogel
William R.Vogel
Fecha y lugar de nacimiento: nació en Sac City, Iowa, el 15 de noviembre de 1941
Estudios: se graduó en 1959 como mejor alumno. Asistió a la AIB durante un año, y después sirvió en la Reserva del Ejército durante seis años
Fecha de muerte: William R. Vogel murió Jueves, 26 de agosto 2010, en el Mercy Hospice, Johnston
Trabajó en un banco en Storm Lake por un año. Trabajó en la Northwestern Bell / Qwest por 25 años, y en Principal Financial de 12 años como analista de telecomunicaciones. Después de su retiro a los 62 años, vivió la vida al máximo, manteniendo su superficie y unos cuantos más.
Participación 7
Problema de Maximización
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:
1 | 2 | 3 | Oferta | |
1 | $55 | $65 | $80 | 35 |
2 | $10 | $15 | $25 | 50 |
Demanda | 10 | 10 | 10 |
1. ¿Cómo cambian los criterios de los métodos que generan solución inicial?
Esquina noroeste: El criterio no cambia, ya que aquí solo se eligen en inicio las esquinas y después la casilla más cercana, sin tomar en cuenta nada más. Z=2000
Costos mínimos: Se identifica en cada iteración la casilla con el costo más grande y esta se satura igual por renglón o columna. Z=2000
Vogel: Para obtener las penalizaciones se calculan haciendo las restas de los costos ya sea por renglón o por columna más grandes, y se escoge la casilla con mayor costo. Z=2000
¿Qué criterio se utilizaría para determinar la variable de entrada?
Se busca el Zj-Cj más negativo
¿Cómo es criterio para variable de salida?
Es el mismo que en minimización
Encontrar la solución óptima.
Solución optima, se parte de la solución inicial que brinda el método de Vogel, y al realizar el método de multiplicadores nos damos cuenta de que Zj-Cj≥0, asi que llegamos a la solución optima con
X11=10,
X12=10
X13=10
Z=2000
La planta 1 enviara 10 suministros médicos al cliente, 10 suministros médicos al cliente 2 y 10 suministros cedimos al cliente 3
jueves, 1 de septiembre de 2011
Tabla resumen: Problema de Asignación
Características | Observación | Pagina |
Historia del modelo | Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, como lo es la demanda en cada destino. El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o a trabajos de maquinas), con la condición de que cada hombre puede ser asignado a un trabajo y cada trabajo tendrá asignada una persona. La condición necesaria suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir que los recursos totales sean iguales a las demandas totales. El modelo de asignación tiene sus principales aplicaciones en: Trabajadores, oficinas de personal, vehículos de rutas, vendedores a regiones, productos a fabricar, etc. El algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo. La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres | |
Elementos | Minimizar el costo total de la operación de modo que: Cada tarea se asigne a una y solo una maquina Cama maquina realice una y solo una tarea Xij= 1 si la tarea i se realiza con la maquina j Cij= costo de realizar la tarea i con la maquina j n tareas m maquinas Si hay mas maquinas que tareas se formula con desigualdades y se resuelve con tareas ficticias  | |
| Ejemplo | Ejemplo: Vendedores-Terrenos Tareas-Máquinas Empleados-Trabajadores | |
Método de solución |
Método húngaro 1. Reste el valor más pequeño de la fila en cada una de las filas 2. Reste el valor más pequeño en la columna de cada una de las columnas. 3. trazar segmentos: este es el criterio de decisión de asignación, es decir A) Sí el número de segmentos es = m, entonces podemos asignar, recuerda que m=n asignaciones. Un Segmento es una línea vertical u Horizontal que se va a trazar a lo largo de toda la fila o toda la columna, no se pueden trazar segmentos en forma diagonal. B) Caso contrario ir al paso 4 4. Atender los siguientes incisos: A) Seleccione la posición del dato menor de los no segmentados y restelo a los no segmentados, (esto hará que se generen nuevos ceros) B) Localizar los datos en donde se INTERSECTAN los segmentos, y sumar el dato menor seleccionado. C) El resto de los datos segmentados quedan exactamente igual. 5. Repita el paso 3 | |
Programas existentes | WinQSB Lingo QM2 Lindo Tora PHPSimplex |
jueves, 25 de agosto de 2011
Participación 6
Método de Costos mínimos
Universidad Politécnica de Cataluña
Métodos cuantitativos de organización industrial 1
Problemas de transporte
Método de mínimos costes
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
10) El método termina hasta que todas las casillas estén saturadas
Resultados del modelo propuesto:
X11=5
X12=45
X21=15
X23=20
X33=10
X34=30
Min Z= 1015
La diferencia con el Min Z obtenido en la participación 5 y este es de 75 , lo que implica que hay un menor costo al empezar a trabajar con la solución inicial que nos brinda el método de costos mínimos,ya que al final lo que queremos minimizar son costos así que si este método si los toma en cuenta nos brindara una mejor solución básica factible lo que ayudara a que se realicen menos iteraciones para encontrar la solución optima.
Suscribirse a:
Entradas (Atom)