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 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.

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, 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.

Su trabajo 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.

Referencias:

• "Algoritmo_ford_fulkerson â Grafos -???? Software Para La construccià ³ n, Edicià ³ n Anà ¡lisis Y De Grafos". Algoritmo_ford_fulkerson â???? Grafos . Np, nd Web. 17 de septiembre 2012. <http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_ford_fulkerson>.
• "Delbert Ray Fulkerson." - Wikipedia, La Enciclopedia Libre. N.p., n.d. Web. 17 Sept. 2012. <http://es.wikipedia.org/wiki/Delbert_Ray_Fulkerson>.

Imagen obtenida: 

• N.p., n.d. Web. 17 Sept. 2012. <http://arodrigu.webs.upv.es/grafos/lib/exe/fetch.php?media=delbertrayfulkerson_foto.jpg>.

Lester Randolph Ford Jr.

Lester Randolph Ford, Jr. (nacido el 23 de septiembre 1927, Houston ) es un americano matemático especializado en redes de flujo problemas, uno de los pioneros en el campo de la programación de flujos en grafos. Él es el hijo del matemático Lester R. Ford, padre (quién también es un matemático distinguido) .

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ó el máximo de flujo min de corte teorema. Con Richard Bellman , Ford también ha desarrollado el algoritmo de Bellman-Ford para encontrar los caminos más cortos en grafos que tienen bordes negativamente ponderados.

 L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. También 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. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. 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. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.

Referencias:

• "LR Ford, Jr." Wikipedia . Wikimedia Foundation, 09 de julio de 2012. Web. 17 de septiembre 2012. <http://en.wikipedia.org/wiki/L._R._Ford,_Jr.>.
• "Algoritmo_bellman_ford â Grafos -???? Software Para La construccià ³ n, Edicià ³ n Anà ¡lisis Y De Grafos". Algoritmo_bellman_ford â???? Grafos . Np, nd Web. 17 de septiembre 2012. <http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford>.
• "OEDKARINA." : Lester Randolph Ford Jr. N.p., n.d. Web. 17 Sept. 2012. <http://oedkarina.blogspot.mx/2011/09/lester-randolph-ford-jr.html>.

Imagen obtenida: 

• N.p., n.d. Web. 17 Sept. 2012. <https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_Tt9A8hU0e3tkYQN783_d8eCTKX4-BofK8dLhXMUjeYlOHManq6tVBxLQM7yQYlYnid1S3WlRB37aSAcnA_HucXm_BOgWUxLL7RgnUXo5MDEYLPkmJAJk0UxZgGwhlwBrGszxmHgXaMk/s1600/Lester+R+Ford+Jr.jpg>.

Robert W. Floyd

Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática.

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 a los 17 años y una segunda licenciatura en 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 la computadora en la década de 1960, comenzó a publicar numerosos trabajos notables y fue nombrado profesor asociado en la Universidad Carnegie Mellon en el momento en que tenía 27 años y se convirtió en profesor titular en la Universidad de Stanford seis años después. Él obtuvo esta posición sin un Ph.D.

Recibió el Premio Turing de la ACM en 1978 "por tener una clara influencia sobre las 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 del análisis , las semántica de los lenguajes de programación , automático programa verificación , automático síntesis de programas , y análisis de algoritmos".

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.

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.

Floyd trabajó en estrecha colaboración con Donald Knuth , en particular por lo que el revisor principal para el libro seminal de Knuth El arte de programar ordenadores , y es la persona más citada en este trabajo. 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-0-7167-8266-7 ). Floyd supervisados ​​7 doctorados.

Floyd se casó y se divorció dos veces, incluso con equipo científico Christiane Floyd , y tenía cuatro hijos. Sus pasatiempos incluyen senderismo y era un ávido backgammon jugador.

En una ocasión estaban 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, "¿sabes cómo jugar al backgammon?", Respondí yo conocía las reglas, pero ¿por qué quieres saber? Bob dijo que desde que tuvimos que esperar varias horas tal vez deberíamos jugar algunos juegos, con apuestas pequeñas, 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 imaginé que este consejo generalizado a todo el que viajaron con su propio set de backgammon. Le dije a Bob que yo no iba a jugar por dinero, ni hablar.Empujó un poco, pero finalmente dijo bien. 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 con é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 aprender el juego. Él tomó muy en serio a jugar al backgammon, estudió el juego y sus matemáticas, y era un profesional cercano. Creo que fue más que un hobby. Al igual que su investigación, Bob tomó en serio lo que él hizo, y es totalmente coherente que sería genial en backgammon.

Referencias:

• "Robert W. Floyd." - Wikipedia, La Enciclopedia Libre . Np, nd Web. 16 de septiembre 2012. <http://es.wikipedia.org/wiki/Robert_W._Floyd>.
• "Robert W. Floyd." Wikipedia . Wikimedia Foundation, 09 de junio de 2012. Web. 16 de septiembre 2012. <http://en.wikipedia.org/wiki/Robert_W._Floyd>.

Imagen obtenida: 

• Np, nd Web. 16 de septiembre 2012.<http://cs.stanford.edu/system/files/memoriam/hhfffhcc_0.png?1330125978>.

Edsger Dijkstra Wybe

Edsger Wybe Dijkstra nació el 11 de mayo de 1930 en Rotterdam, Holanda, hijo de un químico y una matemática. Estudio física y matemáticas en la Univ. de Leyden  terminando en 1951. Más tarde, un doctorado en física teórica en la misma universidad en 1956,  seguido de un Ph.D. en 1959 en la Univ. de Amsterdam. En 1952 comenzó a trabajar en el Centro Matemático de Amsterdam donde aprendió a programar, siendo el primer programador en Holanda. En 1962 pasó a ser profesor en la Univ. Tecnológica de Eindhoven hasta 1984. En paralelo, desde 1973 a 1984 fue investigador para Burroughs. Finalmente, en 1984 aceptó la cátedra Schlumberger en la Univ. de Texas at Austin, hasta que jubiló en 1999. Finalmente, el mes pasado, enfermo de cáncer, murió en Nuenen, Holanda. Dijkstra se casó en 1957 con Maria Debets (más conocida como Ria) y tuvo tres hijos: Marcus, Femke y Rutger, el único que siguió sus pasos en la computación. 

Poco después de su muerte en el 2002, recibió la distinción ACM PODC Influential Paper Award en computación distribuida por su trabajo en la auto-estabilización en programas computacionales. Este premio fue renombrado a Premio Dijkstra el siguiente año en su honor.

El trabajo de Dijkstra siempre se ha caracterizó por su elegancia y simplicidad, sin comprometer el rigor de su investigación con consideraciones económicas, políticas o administrativas. Contaba el mismo que al preguntarle a su madre cuán difícil eran las matemáticas, ella le contestó: "aprende todas las fórmulas y que si alguna vez necesitaba 
más de cinco líneas para demostrar algo, estaba en el camino equivocado". En 1972 recibió el premio Turing, y su discurso fue publicado en un artículo titulado "The Humble Programmer" (el programador humilde) ese mismo año en Communications of the ACM. Recientemente, en esta misma revista, publicaba un artículo corto titulado "The End of Computing Science?" (El Fin de la Computación), donde recalcaba que el objetivo principal de la computación, ¿Cómo no convertir un programa en un caos?, todavía no se había logrado.

A veces Dijkstra criticaba en forma franca y directa, para muchos de manera arrogante, incluso en público. Para los que lo conocían mejor, sabían que no era nada personal, sólo su forma de ser. Por dar un ejemplo, según el, la pregunta de si los computadores podían aprender a pensar, era como preguntar si los submarinos podían aprender a nadar. Dijkstra gustaba de viajar por parques nacionales en un bus que llamaba el Touring Machine junto a su familia y tocar a Mozart en el piano. Para terminar, otra cita de Dijkstra (introducción a un curso de cálculo en 1995):  “Si en 10 años más, cuando ustedes estén haciendo algo rápido y sucio, repentinamente visualizan que yo estoy mirando por sobre sus hombros y se dicen a si mismos, - a Dijkstra no le hubiera gustado esto -, eso sería suficiente inmortalidad para mi". 

El premio Turing otorgado por la ACM (Association for Computing Machinery, EEUU) es considerado el equivalente al premio Nobel de la computación. El primero de ellos fue entregado en 1966 y hasta la fecha diez de nuestros próceres 
ya no nos acompañan. Casualmente, cuatro de ellos fallecieron en un lapso menor a 45 días: el 29 de Junio, Ole-Johan Dahl; el 16 de Julio, John Cocke; el 6 de Agosto, Dijkstra; y el 10 de Agosto, Kristen Nygaard. John Cocke fue uno de los principales diseñadores de las arquitecturas RISC. Ole-Johan y Kristen fueron los desarrolladores de Simula, el precursor de los lenguajes de programación orientados a objetos,  tema del próximo mes. Hoy dedicaremos estas líneas a Dijkstra, quién contribuyó al desarrollo de la computación en muchas áreas distintas.

Dijkstra escribió más de 1300 artículos, pero indudablemente hay tres contribuciones cuyo impacto está presente en numerosos ámbitos de la computación moderna:

Algoritmo para encontrar el camino más corto en un grafo: este fue el primer problema de grafos que resolvió Dijkstra en 1956 y publicado en 1959 por que en esa época un algoritmo era difícilmente considerado un logro científico. Hoy en día, este algoritmo ha sido usado como la base para protocolos de enrutamiento en Internet, sistemas de posicionamiento global o simplemente para itinerarios de viaje.
 
El concepto de abrazo mortal (deadlock) y su solución a través de semáforos y regiones de código con acceso exclusivo. Dijkstra describió el problema con la cena de los famosos cinco filósofos que sólo tenían cinco palillos para comer arroz (ver figura). Si ellos no se ponían de acuerdo y tomaban un palillo cada uno, creaban un deadlock y morían de hambre pues se necesitaban dos palillos para comer. Esta es la base de la programación concurrente y una parte fundamental de cualquier sistema operativo.

Su aporte a la programación estructurada. Dijkstra participó en el comité que diseño Algol 60, el primer lenguaje de programación estructurado, y lo promovió intensamente fomentando la verificación formal de programas y la eliminación del goto. En este tema fue autor y coautor de varios libros, además de su artículo corto  "Go To statement considered harmful" (La instrucción go to es considerada dañina) publicado en Communications of ACM en 1968, que es legendario.

Referencias:

• "Edsger Dijkstra." - Wikipedia, La Enciclopedia Libre. N.p., n.d. Web. 10 Sept. 2012. <http://es.wikipedia.org/wiki/Edsger_Dijkstra>.
• "Edsger Wybe Dijkstra (1930-2002)." Edsger Wybe Dijkstra (1930-2002). N.p., n.d. Web. 10 Sept. 2012. <http://users.dcc.uchile.cl/~rbaeza/inf/dijkstra.html>. 

Imagen obtenida 

• "Edsger Wybe Dijkstra (1930-2002)." Edsger Wybe Dijkstra (1930-2002). N.p., n.d. Web. 10 Sept. 2012. <http://users.dcc.uchile.cl/~rbaeza/inf/dijkstra.html>. 

¿Quién inventó el algoritmo de Kruskal?

Joseph Bernard Kruskal

Joseph Bernard Kruskal, Jr. (29 en junio 1928 a 19 septiembre 2010).era un americano matemático, estadístico, informático y de psicometría. El era un estudiante de la Universidad de Chicago y en la Universidad de Princeton, donde completó su doctorado en 1954, nominalmente bajo Albert W. Tucker y Lyndon Roger, pero de facto en Erdős Pablo, con quien tuvo dos conversaciones muy cortas. Kruskal ha trabajado en bien cuasi-ordenamientos y el escalamiento multidimensional .

El era un miembro de la American Statistical Association, expresidente de la Sociedad psicométrica, y expresidente de la Sociedad de Clasificación de América del Norte. También inició y fue el primer presidente del Consejo de Vivienda Justa de South Orange y Maplewood en 1963, y apoyó activamente los derechos civiles en varias otras organizaciones.

En las estadísticas, la obra más influyente de Kruskal es su contribución fundamental a la formulación de escalamiento multidimensional . En informática, su trabajo más conocido es el algoritmo de Kruskal para el cálculo del árbol de expansión mínima (MST) de un grafo ponderado . Las órdenes primer algoritmo de los bordes en peso y luego procede a través de la lista ordenada añadir un borde para el MST parcial, siempre que la adición de la nueva ventaja no se crea un ciclo. Árboles de expansión mínima tiene aplicaciones en la construcción y los precios de las redes de comunicación. Kruskal también se aplica a su trabajo en lingüística, en un experimental lexicostatistical estudio de la Indo-Europea idiomas, junto con los lingüistas Dyen Isidoro y Pablo Negro. Su base de datos sigue siendo ampliamente utilizado (disponible en el enlace de abajo).

Kruskal nació en Nueva York a un mayorista de pieles con éxito, Joseph B. Kruskal, Sr. Su madre, Lillian Rose Vorhaus Kruskal Oppenheimer , se convirtió en un promotor conocido de Origami en la época temprana de la televisión. Murió en Princeton .

Joseph Kruskal no se debe confundir con sus dos hermanos Martin David Kruskal (1925-2006, co-inventor de solitones y números surreales) y William Kruskal (1919-2005, desarrolló la prueba de Kruskal-Wallis de una vía de análisis de varianza).

Referencias:

• "Joseph Kruskal." Wikipedia. Wikimedia Foundation, 17 Aug. 2012. Web. 10 Sept. 2012. <http://en.wikipedia.org/wiki/Joseph_Kruskal>. .

Imagen obtenida:

•  Joseph Bernard Kruskal. N.p., n.d. Web. 10 Sept. 2012. <http://memorod.blogspot.mx/2011/10/joseph-bernard-kruskal.html>.  

¿Quién inventó el algoritmo de Prim?

Robert C. Prim

Robert C. Prim (1921, Sweetwater, Estados Unidos) es un matemático e ingeniero informático. 

En 1941 se licenció en ingeniería 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 desde1948 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.

Referencias:

• "Robert C. Prim." - Wikipedia, La Enciclopedia Libre. N.p., n.d. Web. 10 Sept. 2012. <http://es.wikipedia.org/wiki/Robert_C._Prim>.
• N.p., n.d. Web. 10 Sept. 2012. <http://es.wikipedia.org/wiki/Algoritmo_de_Prim>.

Imagen obtenida:

• "Robert C Prim." Magick, Wicca, Paganism and Other Esoteric Knowledge. N.p., n.d. Web. 10 Sept. 2012. <http://www.realmagick.com/robert-c-prim/>. 

Tarea 1 Tríptico de un Problema de Transporte

Tarea 1 Tríptico de un Problema de Transporte

Participación 12 Resolución de problemas de asignación

Doc Concillman reúne a un equipo de relevos para el relevo de 400 metros. Cada nadador debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc cree que cada nadador obtendrá los tiempos en segundos dados en la tabla. ¿Qué nadador debe nadar que estilo?

Nadador	Libre	Pecho	Mariposa	Dorso
Gary	54	54	51	53
Mark	51	57	52	52
Jim	50	53	54	56
Chet	56	54	55	53

Participación 10 Resolución de problemas de transbordo

Un problema de transporte consiste ñeque dos fábricas abastecen cierto artículo a tres tiendas. La cantidad de unidades ofrecidas en las fuentes 1 y 2 es 200 y 300; la que piden las tiendas 1,2 y 3 es de 100,200 y 50 respectivamente. Las unidades se pueden transbordar entre las fábricas y las tiendas, antes de llegara su destino final. Determinar el programa óptimo de transporte con base a los costos unitarios que se muestran a continuación: (Resuelve ejercicio)

Fábrica			Tienda
	1	2	1	2	3
Fábrica 1	$0	$6	$7	$8	$9
Fábrica 2	$6	$0	$5	$4	$3
Tienda 1	$7	$2	$0	$5	$1
Tienda 2	$1	$5	$1	$0	$4
Tienda 3	$8	$9	$7	$6	$0

Balanceamos la tabla:

Encontramos la solución inicial mediante Vogel

Buscamos la v. de entrada

Buscamos la v. de salida creando un ciclo

Encontramos que la variable de salida es X32 y continuamos con el algoritmo hasta encontrar que la solución es:

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. 

Planteamos la tabla de transporte

Aplicamos Vogel para encontar la solución básica

Aplicamos el método de multiplicadores para encontrar la variable de entrada

Como todos los valores de las variables son negativos, quiere decir que encontramos la solución optima que es:

Comparamos los resultados con los de un paquete computacional en esta caso WINQSB

Los resultados son iguales lo cual quiere decir que:

200 motores el mes 1 para el mes 1
200 motores el mes 1 para el mes 2
200 motores el mes 1 para el mes 3
200 motores el mes 2 para el mes 4
200 motores el mes 3 para el mes 5
200 motores el mes 4 para el mes 6

Con un costo de: $97 230.00

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

1. ¿Cómo cambian los criterios de los métodos que generan solución inicial?
   
   
   Esquina Noroeste:  Este método se puede tomar de la misma manera tanto para minimización como maximización ya que no toma en cuenta los costos.
   
   
   Costos Mínimos: En este método se inicia asignando todo lo posible a la celda con el máximo costo unitario.
   
   
   Vogel: En este método cambian las penalizaciones ya que estas se obtienen usando la diferencia entre los costos mayores y eligiendo el numero mayor que se obtuvo en estas para después elegir la casilla con mayor costo.
2. ¿Qué criterio se utilizaría para determinar la variable de entrada?
   
   Para obtener la variable de entrada utilizamos el criterio de los multiplicadores usando la celda con el coeficiente mas negativo.
3. ¿Cómo es criterio para variable de salida?
   
   Se utiliza el criterio de construcción de un ciclo que inicia en la variable de entrada.
4. Encontrar la solucción
   
   
   
   Solución básica: 
   
   
   Para escoger la variable de entrada aplicamos el método de multiplicadores
   
   
   
   Como no hay variable negativas esta es la solución optima: