domingo, 25 de septiembre de 2011

Robert W. Floyd

Robert W. Floyd(1936-2001)

Nació el 08 De junio de 1936 y murió el 25 de septiembre de 2001; fue un eminente científico informático.
Nacido en Nueva York, Floyd terminó la escuela a los 14 años. En la Universidad de Chicago, recibió una licenciatura en artes liberales en 1953 (cuando aún tenía sólo 17 años) y una segunda licenciatura en física en 1958.
Floyd se convirtió en un miembro del personal de la Fundación de investigación de blindaje (ahora IIT Research Institute) en Illinois Institute of Technology en la década de 1950. Convertirse en un operador de equipo en la década de 1960, comenzó a publicar muchos papeles notables y fue nombrado profesor asociado en la Universidad Carnegie Mellon por el momento a los 27 y se convirtió en profesor en la Universidad de Stanford seis años más tarde.
Recibió el Premio Turing en 1978 "para tener una clara influencia sobre metodologías para la creación de software eficiente y confiable y para ayudar a encontrar los siguientes subcampos importantes de la informática: la teoría de análisis, la semántica de lenguajes de programación automática, verificación de programa automático, síntesis del programa y análisis de algoritmos".
Sus contribuciones incluyen el diseño del algoritmo de Floyd-Warshall (independientemente de Stephen Warshall), que considera eficaz todas las rutas de menor en un gráfico, ciclo algoritmo Floyd de detección de ciclos en una secuencia y su trabajo en analizar. En un documento aislado introdujo el concepto importante de difusión de error para imágenes de representación, también llamado Floyd–Steinberg tramado (aunque distinguió el tramado de difusión). Un logro importante fue pionero en el campo de la verificación del programa mediante aserciones lógicos con el papel de 1967 Asignar significados a programas. Esto fue una importante contribución a lo que más tarde se convirtió en lógica de Hoare.

Obtenido de:
* http://www.microsofttranslator.com/BV.aspx?ref=IE8Activity&a=http%3A%2F%2Fwww.freebase.com%2Fview%2Fen%2Frobert_floyd
* http://www.microsofttranslator.com/bv.aspx?from=&to=es&a=http%3A%2F%2Fen.wikipedia.org%2Fwiki%2Findex.html%3Fcurid%3D301900


viernes, 16 de septiembre de 2011

PARTICIPACIÓN: Biografía de Dijkstra


Edsger Dijkstra Wybe (1930-2002)

Edsger Dijkstra Wybe nació en Rotterdam, los Países Bajos en 1930. Both of his parents were intellectual people and had received good educations. Sus dos padres eran gente intelectual de los cuales recibió una buena educación. His father was a chemist, and his mother was a mathematician. Su padre era químico, y su madre era un matemático. In 1942, when Dijkstra was 12 years old he entered the Gymnasium Erasminium, a high school for extremely bright students, and he was educated in a number of different subjects including: Greek, Latin, French, German, English, biology, mathematics, and chemistry. En 1942, cuando Dijkstra tenía 12 años entró en el Gymnasium Erasminium, una escuela secundaria para estudiantes muy brillantes, y fue educado con una serie de temas diferentes, incluyendo: griego, latín, francés, alemán, Inglés, biología, matemáticas, y química.
In 1945, Dijkstra thought that he might study law and possibly serve as a representative for the Netherlands at the United Nations. En 1945, Dijkstra pensó que podría estudiar la ley y posiblemente servir como un representante de los Países Bajos en las Naciones Unidas. However, due to the fact that he had scored so well in chemistry, mathematics, and physics, he entered the University of Leiden, where he decided to study theoretical physics. Sin embargo, debido al hecho de que él había sobresalido en la química, las matemáticas y la física, entró en la Universidad de Leiden, donde decidió estudiar física teórica. He went to summer school on the subject of programming at Cambridge University, during the summer of 1951. Fue a la escuela de verano sobre el tema de la programación de la Universidad de Cambridge, en el verano de 1951. He began part-time work at the Mathematical Centre in Amsterdam in March 1952, which further helped fuel his growing interest in programming. Empezó a trabajar a tiempo parcial en el Centro Matemático en Amsterdam en marzo de 1952, que además ayudó a impulsar su creciente interés en la programación. He finished the requirements for his theoretical physics degree as quickly as possible and began to pursue his interests in progamming. Terminó con los requisitos para obtener su título de física teórica lo más rápidamente posible y comenzó a perseguir sus intereses en programación desde. One of the problems that he ran into, however was that programming still was not officially recognized as a profession. Uno de los problemas que se encontró con, sin embargo, fue que la programación todavía no fue oficialmente reconocida como una profesión. In fact, when he applied for a marriage license in 1957, he had to put down "theoretical physicist" as his profession. De hecho, cuando solicitó una licencia de matrimonio en 1957, tuvo que dejar "físico teórico", como su profesión.
Dijkstra continued to work at the Mathematical Centre until he accepted a job as a research fellow for Burroughs Corporation, in the United States, in the early 1970s. Dijkstra continuó trabajando en el Centro de Matemáticas hasta que aceptó un trabajo como investigador para Burroughs Corporation, en Estados Unidos, a principios de 1970. He was awarded the ACM Turing Award in 1972. Fue galardonado con el Premio Turing ACM en 1972. He was given the AFIPS Harry Goode Memorial Award in 1974. Se le dio el AFIPS Harry Goode Memorial Award en 1974. Dijkstra moved to Austin, Texas in the early 1980s. Dijkstra se trasladó a Austin, Texas en la década de 1980. In 1984 he was appointed to a chair in Computer Science at the University of Texas, Austin, where he has been ever since. En 1984 fue nombrado catedrático en Ciencias de la Computación en la Universidad de Texas, Austin, donde ha estado desde entonces.
En 1956, Dijkstra se le ocurrió la "ruta más corta de algoritmo", después de que se le había asignado la tarea de mostrar los poderes de ARMAC, el equipo que el Centro de Matemática él tenía en su posesión, un algoritmo que ayuda en la búsqueda de la mejor manera de viajar entre dos puntos. 
Muere el 8 de agosto del 2002 a causa del cáncer.
Obtenida de:
http://translate.google.com.mx/translate?hl=es&sl=en&u=http://www.thocp.net/biographies/dijkstra_edsger.htm&ei=J11xTpWwGq-LsAKMp7noCQ&sa=X&oi=translate&ct=result&resnum=16&sqi=2&ved=0CIYBEO4BMA8&prev=/search%3Fq%3Dedsger%2Bdijkstra%26hl%3Des%26biw%3D1024%26bih%3D571%26prmd%3Dimvnso
El día 15 de septiembre de 2011


martes, 13 de septiembre de 2011

Unidad II. ¿Que es PRIM?

Algoritmo de Prim es un algoritmo de la teoría de grafos que encuentra un árbol de expansión mínimo para un grafo conexo ponderado. Esto significa que encuentra un subconjunto de las aristas que forma un árbol que incluye todos los vértices, donde se minimiza el peso total de todas las aristas en el árbol. El algoritmo fue desarrollado en 1930 por el matemático checo Vojtech Jarník y posteriormente de forma independiente por el científico Robert C. Prim equipo en 1957 y redescubierto por Edsger Dijkstra en 1959. Por lo tanto, es a veces llamado el algoritmo DJP, el algoritmo Jarník, o el algoritmo de Prim-Jarník. 

Obtenido de: http://translate.google.com.mx/translate?hl=es&langpair=en|es&u=http://wiki.answers.com/Q/Can_you_give_the_prim's_algorithm_program_in_c 

Durante su carrera en los Laboratorios Bell, Robert Prim, junto con un compañero de trabajo José Kruskal desarrollaron dos algoritmos diferentes para encontrar un árbol de expansión mínimo en un promedio ponderado gráfico, un bloque básico de tropiezo en el diseño de redes informáticas. El algoritmo con su propio nombre, el algoritmo de Prim, fue descubierto originalmente en 1930 por el matemático Vojtěch Jarník y posteriormente de forma independiente por Prim en 1957. Fue redescubierto después por Edsger Dijkstra en 1959. A veces se conoce como el algoritmo DJP o algoritmo de Jarník.

Obtenido de: http://translate.google.com.mx/translate?hl=es&langpair=en|es&u=http://en.wikipedia.org/wiki/Robert_C._Prim


domingo, 11 de septiembre de 2011

Participación 10.

Suponga la red, plantee el modelo de programación lineal y tabla de transporte:









Xij = Cantidad a enviar del nodo i al nodo j

Min z= X13+4X14+3X23+2X24+X34+6X35+3X43+5X45+8X46+X56
S.A.
       X13+X14=100
       X23+X24=200
       X34+X35=X13+X23+X43
       X43+X45+X46=X14+X24+X34
       150+X56=X35+X45
       X46+X56=150
               Xij >=0


TABLA DE TRANSPORTE

sábado, 10 de septiembre de 2011

Participación 8.

Se hace un mantenimiento preventivo periódico a motores de aviones, donde se debe cambiar un componente importante. La cantidad de motores programados para ese mantenimiento, durante los seis meses siguientes, se estima en 200, 180, 300, 198, 230 y 290 respectivamente. Todo el trabajo de mantenimiento se hace durante los dos primeros días del mes, cuando se puede cambiar un componente usado por uno nuevo, o por un componente reconstruido. La reconstrucción de los componentes usados se puede hacer en un taller local, y cuando salen están listos para usarse al principio del mes siguiente, o bien se pueden mandar a un taller central y en ese caso hay una espera de tres meses (que incluye al mes en que se hace el mantenimiento). El costo de reparación en el taller local es de $120 por componente. En el taller central el costo sólo es de $35 por componente. Un componente reconstruido que se usa en algún mes posterior causará un costo adicional de almacenamiento de $1.50 por unidad y por mes. Los componentes nuevos se pueden comprar a un costo de $200 cada uno, en el mes 1 y con 5% de aumento en el precio cada dos meses. Formular el problema, resolverlo utilizando algún paquete computacional.


Red:

Problema de Programación Lineal

Min Z= 200X11 + 120X12 + 121.5X13+ ... + 120X56 + 220.5X66
S.A.
       X11+X12+X13+X14+X15+X16+X17=1398
                X22+X23+X24+X25+X26+X27=1398
                         X33+X34+X35+X36+X37=1398
                                  X44+X45+X46+X47=1398
                                           X55+X56+X57=1398
                                                    X66+X67=1398
      X11                                                       =200
      X12+X22                                              =180
      X13+X23+X33                                     =300
      X14+X24+X34+X44                            =198
      X15+X25+X35+X45+X55                   =230
      X16+X25+X36+X46+X56+X66          =290
      X17+X27+X37+X47+X57+X67+X77=6990
                        Xij>=0;   Xij E Z

SOLUCIÓN:
X11=200
X12=180
X14=198                   Z= 122730
X23=300
X25=230
X36=290




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:


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: Los criterios no cambian porque este método no toma en cuenta los costos.

Costos Mínimos: Cambia al momento de elegir el costo mínimo, en este caso se elige el costo máximo y todos los demás pasos son iguales.

Vogel: Cambia al momento de hacer las penalizaciones, las diferencias en este casos son entre los costos mayores.

2. ¿Qué criterio se utilizaría para determinar la variable de entrada?
En los multiplicadores se elige la variable mas grande.

3. ¿Cómo es criterio para variable de salida?
El criterio es el mismo.


4. Encontrar la solución óptima.










Solución Optima:
X11= 10
X12= 10
X13= 10

Z=2000

jueves, 8 de septiembre de 2011

TABLA DE RESUMEN DE PROBLEMAS DE ASIGNACIÓN

Características
Observación
Página
Historia del modelo
 Es una caso especial del problema de transporte que debe su nombre a la aplicación de asignar hombres a trabajos.
En 1955 Kuhn ideó el método húngaro para los problemas de asignación. El método húngaro es llamado así debido a que fueron dos matemáticos húngaros, König (1916) y Egervary (1931), los que apartaron la teoría que sirve de base a este método.
 http://antiguo.itson.mx/dii/
elagarda/apagina2001/PM/
asignación.html
Elementos
 Objetivo: Determinar como deben hacerse las n asignaciones para que el costo total de la asignación sea mínima.
Un costo unitario (o ganancia) Cij es asociado al trabajador i que realiza el trabajo j.
Minimizar el costo total de la asignación de trabajadores a sus respectivos empleos que corresponden a cada uno, tratando de que la asignación sea la mas optima posible.
La oferta y la demanda son 1's.
El problema debe estar balanceado.
 http://www.angelfire.com/
ak6/invo_escom2/clase12.pdf
Ejemplo
 La siguiente matriz contiene los costos para operar n=4 máquinas, por n=4 personas así calificadas en su empresa. Optimice la asignación idónea.


Paso 1 .Seleccione en cada renglón i de la matriz, el menor costo C i j, (menor C i j = U i ), luego réstelo en cada elemento del renglón.

Paso 2. Seleccione en cada columna j de la matriz resultante en el paso 1, el costo menor C i j, (menor Cij=Vj) y réstelo en cada elemento de la misma columna.


Paso 3.Sombree los renglones y/o columnas de la matriz, de tal modo que sean los mínimos necesarias para cubrir todos los ceros.


Paso 4. Seleccione entre los costos no sombreados, el número menor C i j, (= U i j) o bien, el menor C i j,(= V i j), y réstelo a todos los costos no sombreados; después, sume el mismo a los costos ubicados en la intersección de los renglones y columnas sombreados. Este paso se repite hasta lograr la solución óptima.



Se tiene la solución óptima cuando el mínimo necesario de renglones y columnas sombreadas para cubrir los ceros es n. En este problema el mínimo es n =4.



Entonces la asignación óptima es la que muestra la tabla siguiente:



Solución óptima: X11 = 1, X23 = 1, X32 = 1, X44 = 1
Z = C11 X11 + C23 X23 + C32 X32 + C44 X44 = 1(1) + 10(1) + 5(1) + 5(1) = 21
 http://148.204.211.134/polilibros/
portal/Polilibros/P_Terminados/
Investigacion_de_Operaciones_
Careaga/Common/IO-modulo4asignacionpura.htm
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 MAS 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


 http://antiguo.itson.mx/dii/
elagarda/apagina201/PM/
asignacion.html#define

Programas existentes
TORA
WINQSB
LINGO
GAMS
SOLVER (EXEL)