¿Quién inventó el Algoritmo de Prim?

¿Quién inventó el Algoritmo de Prim?

*Robert Prim Clay *

Robert Prim Clay (nacido en 1921 en Sweetwater , Texas, ) es un americano matemático y científico de la computación.

En 1941, Prim obtuvo su licenciatura en ingeniería eléctrica de la Universidad de Princeton . Más tarde, en 1949, recibió su Ph.D. en Matemáticas allí también. Prim Robert trabajó en la Universidad de Princeton desde 1948 hasta 1949 como investigador asociado.

Durante el apogeo de la Segunda Guerra Mundial (1941-1944), Prim trabajó como ingeniero para General Electric.

Desde 1944 hasta 1949, fue contratado por el Laboratorio de Artillería Naval de los Estados Unidos como un ingeniero y un matemático posterior.

En los Laboratorios Bell , se desempeñó como director de investigación de matemáticas 1958 a 1961. Allí, Prim desarrollo el algoritmo de Prim. Después de los Laboratorios Bell, Prim se convirtió en vicepresidente de investigación de los Laboratorios Nacionales Sandia.

Durante su carrera en los Laboratorios Bell, Robert Prim junto con un compañero de trabajo José Kruskal desarrollado dos algoritmos diferentes (ver algoritmo codicioso ) para encontrar un árbol de expansión mínimo en un promedio ponderado gráfico , un bloque básico de tropiezo en diseño por ordenador de la red. Su algoritmo propio nombre, el algoritmo de Prim, fue descubierto originalmente en 1930 por el matemático Vojtěch Jarnik más tarde y de forma independiente por Prim en 1957. Fue redescubierto después por Edsger Dijkstra en 1959. Se refiere a veces como el algoritmo DJP o el algoritmo de Jarnik.

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.

Referencias:

v Significado de PRIM. [en línea]. < http://es.wikipedia.org/wiki/Algoritmo_de_Prim >. Consulta: Octubre, 2012
v  "Robert C. Prim." Wikipedia. Wikimedia Foundation, 22 Mar. 2012. Web. 09 Sept. 2012 <http://en.wikipedia.org/wiki/Robert_C._Prim> 

v Robert C. Prim. Digital image. N.p., n.d. Web. 9 Sept. 2012. <http://tinyurl.com/9ntfcgh>.

Participación 8_Unidad I

Participación 8

*Resolución de Problemas de Transporte*

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.

SOLUCIÓN:

Primeramente plantearemos la Tabla de Transporte:

Ahora, teniendo en cuenta que para encontrar la solución inicial tenemos 3 métodos (Esquina Noroeste, Costos Mínimos y Vogel), utilizaremos EL MÉTODO DE VOGEL debido a que es el más eficiente y más cercano a la solución óptima y además por el tamaño de la tabla permitirá ahorrarnos iteraciones en el método de multiplicadores.

La siguiente tabla muestra las penalizaciones:

Ahora bien, teniendo la solución inicia procederemos a aplicar el método de multiplicadores para encontrar la variable de entrada y variable de entrada.

Como todos los valores de las variables NO BÁSICAS son < 0 (criterio de variable de Entrada para el Caso de Minimización), podemos decir que hemos llegado a la solución óptima.

X11=200	X12=180	X13=300	X24=198	X35=230	X46=290
X17=718	X27=1000	X37=788	X47=428	X57=520	X67=290
Z=97230

COMPARACIÓN DE RESULTADOS CON PAQUETE COMPUTACIONAL:

Se utilizó el paquete computacional WinQSB.

Con la aplicación de la Tabla de transporte:

Procesando los datos se obtuvieron los siguientes resultados:

Con lo cual comprobamos que nuestra solución es correcta ya que es la misma.

INTERPRETACIÓN:

Se debe dar mantenimiento a:

  v  200 motores el mes 1 para el mes 1

  v  200 motores el mes 1 para el mes 2

  v  200 motores el mes 1 para el mes 3

  v  200 motores el mes 2 para el mes 4

  v  200 motores el mes 3 para el mes 5

  v  200 motores el mes 4 para el mes 6

Con un Costo Mínimo de: $97 230.00

Participación 2_Unidad I

Participación 2 

“Problema de Transporte Adicional”

Joshop desea asignar cuatro categorías diferentes de maquinas a cinco tipos de tareas. La cantidad de maquinas disponibles en las cuatro categorías son 25, 30, 20 y 30. La cantidad de operaciones en las cinco tareas son 20, 20, 30, 10 y 25. A la categoría de la máquina 4 no se le pude asignar la tarea de tipo 4. La siguiente tabla proporciona el costo unitario (en dólares) de asignar una categoría de máquina a un tipo de tarea. El objetivo del problema es determinar la cantidad óptima de máquinas en cada categoría que se ha de asignar a cada tipo de tarea. Plantear los tres modelos.

Categoría de Máquina	Tarea1	Tarea 2	Tarea 3	Tarea 4	Tarea 5
1	10	2	3	15	9
2	5	10	15	2	4
3	15	5	14	7	15
4	20	15	13	--	8

Red:

Modelo de Programación Lineal:

X_ij: # de máquinas de la Tarea i a asignar a la tarea j

F.O   

Min z=10x₁₁+2x₁₂+3x₁₃+15x₁₄+9x₁₅+5x₂₁+10x₂₂+15x₂₃+2x₂₄+4x₂₅+

           15x₃₁+5x₃₂+14x₃₃+7x₃₄+15x₃₅+20x₄₁+15x₄₂+13x₄₃+8x₄₅

S.A:

Restricciones que me limitan la Oferta	Restricciones que me limitan la Demanda
x11+x12+x13+x14+x15=25	x11+ x21+ x31+x41=20
x21+x22+x23+x24+x25=30	x12+ x22+ x32+x42=20
x31+x32+x33+x34+x35=20	x13+ x23+ x33+x43=30
x41+x42+x43          +x45=30	x14+ x24+ x34      =10
	x15+ x25+ x35+x45=25

Restricciones Estructurales

xij ≥ 0   ;   xij € Z

 Tabla de Transporte:

Participación 7 (Unidad I)

*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	$35	$45	$70	35
2	$20	$25	$35	50
Demanda	10	10	10

Como podemos darnos cuenta, en el problema se nos habla de GANANCIAS, lo cual implica asociarlo a un problema de Maximización.

Como aquí nos estamos refiriendo a un problema de transporte que regularmente se refiere a un problema de Minimización de costos, la pregunta es:

¿Cómo cambian los criterios de los métodos que generan solución inicial?

Primero que nada plantearemos la tabla de transporte asociada al problema para ir analizando los diferentes puntos propuestos:

Como vemos, se tuvo que incluir una columna ficticia (4), debido a que el Problema no estaba equilibrado y había más oferta que demanda.

Método de la Esquina Noroeste:

Recordando como trabaja este Método, se hará la siguiente Analogía:

Para el Caso de Minimización, los valores asignados a cada casilla se iniciaban desde cualquier esquina, se saturaba sin tomar en cuenta los COSTOS.

Para el Caso de Maximización, para este caso, no se toma en cuenta las ganancias que puede producir el transporte del bien, por lo tanto decimos que SE UTILIZA EL MISMO CRITERIO.

En nuestro problema este sería:

Produciendo una ganancia de: Z=1500

Método de Costos Mínimos:

Las diferencias de trabajar con este método en el caso de maximización y minimización son:

Para el Caso de Minimización, se toma en cuenta el menor costo de las casillas para ir saturando la oferta o la demanda, según corresponda.

Para el Caso me Maximización, se aplicara lo contrario del nombre del Método, se revisará la ganancia mas alta que proporcione la casilla no saturada.

En nuestro problema esto es:

Aunque se realizó aplicando esta técnica que renombro como “Máximas Ganancias”, no es notorio debido a la naturaleza del problema ya que el resultado es el mismo: Las ganancias máximas Z=1500

Método de Vogel:

Para este caso hay más consideraciones que en los dos anteriores:

Para el Caso de Minimización, como en el apunte hecho en clase dice: “para cada renglón y columna evaluar una penalización entre los dos costos más pequeños de cada renglón y columna, se elegirá el renglón o columna con la penalización más grande, tomar a la casilla de ese renglón o columna que tenga el menor costo y asignar la oferta o demanda más grande posible, posteriormente actualice datos”

Para el Caso de Maximización, para cada renglón y columna, se evaluará una penalización entre las GANANCIAS MÁS GRANDES de cada renglón y columna, se elegirá la columna o renglón con la penalización MAS GRANDE, tomar la casilla de ese renglón o columna que tenga LA MAYOR GANANCIA y asignar la oferta o demanda más grande posible , posteriormente Actualizar Datos.

Para nuestro problema, el método se aplica de la siguiente forma:

Tampoco notamos mucho cambio debido a la naturaleza del problema. Las ganancias son de:

Z=1500

Criterio para determinar la Variable de Entrada:

Con el Método de Multiplicadores se obtiene el zj-cj , y tomado en cuenta que para obtenerlos se manejan de dos formas:

Para las Variables Básicas: u_i+v_j=c_ij

Para las Variables  NO Básicas: u_i+v_j-c_ij=0

Para el Caso de Minimización: De las variables NO Básicas, se escoge la casilla con el valor más positivo, así se ira determinando la variable de entrada hasta que todos los valores de las variables NO básicas sean <=0. Si se encuentra un cero implica que hay solución múltiple.

Para el Caso de Maximización: De las Variables NO Básicas, se escogerá la casilla con el valor MÁS NEGATIVO, así se irá determinando la variable de entrada, usando el mismo criterio que el método Simplex. Este proceso terminará hasta que los valores de las variables NO básicas sean >=0. Si se encuentra un cero implica que hay solución Múltiple.

La variable de entrada de nuestro problema se ilustra a continuación:

Como observamos todos lo valores de las Variables NO Básicas son Positivos, lo cual implica que la solución Actual es la Óptima.

Criterio para determinar la Variable de Salida:

Para el Caso de Minimización: Se realiza la construcción de un ciclo que inicia y termina en la variable de entrada, se toma un valor theta, que es el mínimo de los valores de las variables no básicas que tengan un  -theta. Entonces la variable de salida será aquella a la que corresponda dicho valor mínimo.

Para el Caso de Maximización: Se sigue exactamente el mismo proceso debido a que no afecta para nada el que se trate de un caso de maximización, análogamente con el método simplex.

Solución Óptima:

X11=10	X12=10	X13=10	X14=5
X21=0	X22=0	X23=0	X24=50
Z=1500

Interpretación:

Se deben enviar:

   v  10 suministros médicos de la planta 1 al cliente 1

   v  10 suministros médicos de la planta 1 al cliente 2

   v  10 suministros médicos de la planta 1 al cliente 3

Las columna ficticia de la tabla de transporte con valores: X₁₄=5 y X₂₄=50 son los 55 suministros médicos que tienen de más las plantas (oferta).