Un banco ha decidido conectar terminales de computadora de cada sucursal a la computadora central de su oficina matriz mediante líneas telefónicas especiales con dispositivos de telecomunicaciones. No es necesario que la línea telefónica de una sucursal esté conectada directamente con la oficina matriz. La conexión puede ser indirecta a través de otras sucursales que esté conectada (directamente o indirectamente) a la matriz. El único requisito es que exista alguna ruta que conecte a todas las sucursales con la oficina matriz.
El cargo por las líneas telefónicas especiales es directamente proporcional a la distancia cableada, en donde esta distancia en millas es:
Principal
Sucursal. 1
Sucursal. 2
Sucursal. 3
Sucursal. 4
Sucursal. 5
Principal
--
190
70
115
270
160
Sucursal. 1
190
--
100
110
215
50
Sucursal. 2
70
100
--
140
120
220
Sucursal. 3
115
110
140
--
175
80
Sucursal. 4
270
215
120
175
--
310
Sucursal. 5
160
30
220
80
310
--
La administración desea determinar qué pares de sucursales conectar directamente con las líneas telefónicas especiales para que todas queden conectadas ( de modo directo o indirecto) a la oficina matriz con un costo total mínimo.
La red nos queda de la siguiente forma:
Siguiendo el algoritmo de PRIM la red nos queda de la siguiente forma:
Resultado:
Las líneas rojas indican que sucursales se deben de conectar para que todas puedan estar conectadas directa o indirectas.
La sucursal 2 debe estar conectada con la principal y la 4
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 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. 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 recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».
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. Sus Contribuciones 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.
Su Vida 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.
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".
lunes, 12 de septiembre de 2011
Tabla de resumen: Problema de asignación
Características
Observaciones
Referencias
Historia del modelo
El más antiguo de estos métodos fue propuesto, para el parlamento de los Estados Unidos, por Thomas Jeffersonen 1792, quien lo sugiriera para asignarrepresentantes por estado. Este método (también conocidocomo el de los divisores grandes o el método de D’Hont) ha sido usado extensivamente en Europa. En Estados Unidos fue aplicado entre 1790 y 1830, a partir de los censos ocurridos en ese periodo.En nuestro país también fue usado por mucho tiempo, pero conocido bajo otro nombre: el método de cifra repartidora. En 1792 no hubo una única propuesta de método de asignación:Alexander Hamilton propuso uno alternativo al propuesto por Jefferson, también para asignar sillas a los estados de la Unión.
www.mat.puc .cl/archivos/ Filesistprop _vf.pdf
<>
<>
Elementos
1) El número de asignados es igual al número de tareas.(este numerose denota por n). 2) Cada asignadoseasigna a una tarea. 3) Cada tareadebe realizarlaexactamenteun asignado. 4) Existe un costo cij asociado con el asignadoi ( i = 1,2...,n)que realiza la tarea j(j = 1,2...n). 5) El objetivo es determinar como deben hacerse las nasignaciones para minimizarlos costos totales.
William R. Vogel nació el 15 de noviembre 1941 y murió el 26 de agosto 2010, después de una larga batalla con el cáncer. Él creció en una granja al oeste de Wall Lake, Iowa. Se casó con Karaan el 13 de septiembre de 1964 y vivió en Storm Lake por un año, luego se mudó a Des Moines en 1966.
Educación y Trabajo:
En 1959 se graduó con honores. Asistió a la AIB durante un año, y después sirvió en la Reserva del Ejército durante seis años, luego 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 por 12 años como analista de telecomunicaciones.
Aportaciones:
Desarrollador de “El Método de aproximación de Vogel” .Método heurístico que sirve para obtener una solución óptima para el problema de transporte.
<!--[if !supportLists]-->1.1. <!--[endif]-->Identificar la casilla con el costo mínimo, si hay otra casilla se selecciona arbitrariamente.
<!--[if !supportLists]-->2.2. Saturar la fila o columna con el mínimo entre la oferta y la demanda colocándolo en la casilla.
<!--[if !supportLists]-->3.<!--[endif]--> 3. Marcar la fila o columna saturada. Si se tiene el mismo valor en oferta o demanda se marca la que tenga mayores costos.
<!--[if !supportLists]-->4.4. Identificar la siguiente celda con menor costo y no saturada.
<!--[if !supportLists]-->5.5. Intentar saturar la fila o columna, tomando en cuenta que ya se uso cierta cantidad de oferta o demanda, por lo que esa cantidad se le resta al total de la oferta y de la demanda, colocando el mínimo entre estas dos diferencias.
<!--[if !supportLists]-->6.6. Repetir los pasos 3, 4 y 5 hasta que falte una sola fila o columna por saturar.
Solución del problema en base al método propuesto:
1) Situarnos en la celda superior izquierda (esquina noroeste) e intentar saturar la fila o columna (para saturar la fila se observa la oferta y para saturar la columna la demanda).
2) Elegir el valor más pequeño entre la oferta y la demanda, colocarlo en la casilla para saturar la fila o columna según sea el caso.
3) Marcar la fila o columna saturada (la que en oferta o demanda se tenga 0).
4) Situarse en la siguiente celda más cercana a la esquina superior izquierda.
5) Intentar saturar la fila o columna, tomando en cuenta que ya se uso cierta cantidad de oferta o demanda, por lo que esa cantidad se le resta al total de la oferta y de la demanda, colocando el valor más pequeño entre estas dos diferencias.
6) Realizar el paso 3, 4 y 5 hasta concluir el método obteniendo la solución final.
Solución del problema obtenida a partir del método propuesto:
Americano matemático y físico notable para el análisis vectorial, nacido el 6 de marzo de 1875, en Nueva York, E. U. Su madre fue Ida Susan Porter y su padre era Eliseo Pike Hitchcock. Se casó con Margaret Johnson Blakely (m. 22 de mayo 1925) en París, Francia el 25 de mayo de 1899. Muere a los 82 añosel 31 de mayo de 1957 en Los Angeles, E. U.
Educación y Trabajo:
Recibió su licenciatura de Harvad en 1896. Antes de su doctorado fue profesor en París y en Kenyon College en Gambier, Ohio. En 1910 completó su doctorado en Harvard con una tesis titulada, Funciones vectoriales de un punto.
También fue un experto en la química matemática. En 1904-1906 fue profesor de química en la Universidad Estatal de Dakota del Norte, Fargo, y luego se trasladó a convertirse en un profesor de matemáticas en el Massachusetts Institute of Technology.
Aportaciones:
Una de sus aportaciones más importantes y por la cual se le conoce es la formulación del problema de transporteen 1941. Sin embargo hizo otras aportaciones matemáticas.
Nació el 4 de septiembre de 1917 en Hopewell, VA, USA. Murió el 19 de diciembre de 1992, a los 75 años, en Austin, TX, USA.
Educación y Trabajo:
Abraham Charnes, profesor emérito de ciencias de la gestión y los sistemas de información. Obtuvo licenciatura, maestría y doctorado de la Universidad de Illinois en 1938, 1939 y 1947, respectivamente.
Dr. Charnes enseñó en el Instituto Carnegie de Tecnología, y las universidades de Purdue y del noroeste. En el noroeste fue Walter P. Murphy profesor de Matemática Aplicada. Profesor Charnes incorporó a la Universidad de Texas en Austin en 1968.Ocupó el Jesse H. Jones cátedra y fue profesor del Sistema Universitario. Que más tarde fue nombrado profesor John P. Harbin en la Facultad de Administración de Empresas.
En 1975 el profesor Charnes era un finalista para el Premio Nobel de Economía. Él era el destinatario de los honores, incluyendo la teoría de John von Neumann Premio del Instituto de Ciencias de la Administración y la Sociedad de Investigación de Operaciones de América, y el Premio en Memoria de Harold Lardner de la Sociedad de Investigación de Operaciones en Canadá. También recibió la medalla de Servicio Público Distinguido de la Marina de los EE.UU. por sus contribuciones como un físico de investigación y analista de operaciones durante la Segunda Guerra Mundial.
Aportaciones:
Contribuidor fundamental de muchas aéreas de programación matemática, incluyendo programación lineal. Profesor Charnes era una autoridad reconocida internacionalmente en el desarrollo de nuevos métodos matemáticos y avanzados que se utilizan para resolver problemas de gestión en el gobierno, industria, ingeniería y medicina.
El profesor Charnes publicado más de 200 artículos en revistas especializadas y coautor de siete libros. Una de sus obras más conocidas, Introducción a la Programación Lineal , fue traducido al ruso, chino, y japonés. Otra publicación, Modelos de Gestión y Aplicaciones Industriales de la programación lineal , fue traducido al checo.
Nació en Birmingham, Alabama en 1914. Su padre era un contador y después de un distribuidor de Anheuser-Busch. Cuando tenía tres años, la familia se mudó a Chicago, donde su padre era dueño de una cadena de estaciones de gasolina que había perdido en la Gran Depresión.
Educación y trabajo:
Continuó en la escuela secundaria sólo hasta el final de su segundo año. Con su padre en la mala salud y no los ingresos de la familia, tuvo que trabajar en lo que pudo encontrar. Esto incluye todo, desde el boxeo profesional para detectar clavijas en boliches y caddie en campos de golf. Mientras trabajaba en un campo de golf se reunió con miembros de Salón de la Fama, Eric Kohler, quien después se convirtió en su larga vida de mentor. Esto incluyó un préstamo de los fondos que le permitió iniciar un camino sin diploma de la Universidad de Chicago. Rápidamente aprendió a gustar el ambiente académico y pronto tomaron los exámenes de ingreso a la universidad, con la intención de convertirse en un físico-químico, ya que parecía ofrecer la mejor oportunidad de un trabajo. A finales de 1944, con la guerra llegando a su fin, dejó de enseñar en la Universidad de Chicago.
En 1946, regresó a Washington para presidir un comité para decidir el destino de los diferentes tiempos de guerra-los programas de las estadísticas financieras.
William W. Cooper fue el primer (la fundación) Presidente de TIMS.Él es el profesor Parker Foster, de Finanzas y Administración, Emérito, en la Red McCombs School Graduate School of Business y la Nadja Kozmetsky Scott, miembro del Centenario y Janie Masacre Fellow Brisco y Janie Masacre Centennial Fellow Briscoe en el Instituto IC2 de la Universidad de Texas en Austin.Antes de trasladarse a la Universidad de Texas en Austin en 1980 fue profesor de la Universidad de Ciencias de la Gestión y Políticas Públicas (desde 1.946 hasta 1.975) y Decano de la Facultad de Asuntos Urbanos y Públicos (l969-l975) de la Carnegie-Mellon University, y el Arthur Lowes Dickinson Profesor de Contabilidad en la Universidad de Harvard (l975-l980). En 1990, fue nombrado Educador contables pendientes por la misma organización. Fue Profesor Visitante Internacional para la AAA, que viajan al extranjero en 1986 para dar conferencias sobre temas de contabilidad y visitar a los estudiosos de América Latina.
Es autor o coautor de más de 500 artículos y co-autor o co-editor de 27 libros en Ciencias Contables y de Gestión.Entre sus libros seModelos de Gestión y Aplicaciones Industriales de la programación lineal,Estudios de Planificación de Recursos Humanos,Nuevas perspectivas en Organización, Gestión de la Ciencia y la Calidad de Vida,Ciencias de la Administración Métodos de Planificación de Recursos Humanos y Diseño de la organización,economía computacional,y cuatro libros sobre laenvolvente de datos Análisis:Se ha desempeñado como consultor para más de 200 empresas privadas y agencias gubernamentales.
Aportaciones y Reconocimientos:
Él ha sido un catalizador del cambio de forma en todo el mundo durante más de 50 años: en su investigación, con su enseñanza inspirada, como editor de numerosos periódicos, y como asesor de las instituciones privadas, gubernamentales y públicas. Con su antiguo colaborador, el matemático Abraham Charnes, era conocido en todas partes, "El señor de programación lineal", en parte debido a que, en conjunto, desarrollaron nuevas áreas de uso y la investigación como "programación meta", "posibilidades limitadas de programación, "y, más recientemente," Análisis Envolvente de Datos ".
El profesor Cooper ha participado activamente en varias sociedades profesionales, además de ser el primer presidente del Instituto de Ciencias de la Administración, se desempeñó en los consejos editoriales deCiencia de la Administración,Investigación de Operaciones,Logística Naval Research Quarterly,yThe Accounting Review, y fue el fundador Editor en Jefe deAuditoría: Un diario de la práctica y teoría.En la actualidad es parte del consejo editorial dela Revista Europea de Investigación Operativa,OmegayCiencias Socio-Económicas de Planificación.
Ha sido galardonado doctor honoris causa en ciencias por la Universidad Estatal de Ohio, la Universidad Carnegie-Mellon University, y pronto se le otorgará el grado de doctor honoris causae por la Universidad de Alicante en España. En 1945, recibió el premio al artículo más valioso en la contabilidad, el primero que ha sido otorgado por el Instituto Americano de Contadores (ahora el AICPA).
En 1982, fue co-ganador de la medalla John Von Neumann teoría, otorgado conjuntamente por la Sociedad de Investigación de Operaciones de América y el Instituto de Ciencias de la Administración. En 1988, recibió el Premio por Servicios Distinguidos a la auditoría de la Sección de Auditoría de la AAA, así como un premio a la calidad de editor y fundador de Auditoría, una revista de práctica y teoría .También ha recibido tres premios de la Fundación McKinsey para el artículo más valioso del año en un tema de gestión, y ha sido consultor para más de 200 instituciones, entre ellas el Plan Marshall, la Oficina de Contabilidad General de EE.UU., la UNESCO, y otros.
.jpg){kind=link}
