Problema de transbordo

Participación 10

Suponga las siguientes redes, plantear el modelo de programación lineal y la tabla

Modelo de Programación Lineal

MinZ=5X12+3X13+4X23+X24+7X25+6X32+X34+X35+2X36+9X45+4X47+2X54+5X56+8X57+3X63+7X65+3X67

Nodo 1   X12+X13 = 1                                 Nodo puro de origen

Nodo 2   X23+X24+X25 = X32                        Nodo de transbordo

Nodo 3   X32+ X34+X35+X36 = X13+X23       Nodo de transbordo

Nodo 4   X45+4X47 = X24+X34+X54              Nodo de transbordo

Nodo 5   X54+X56+X57 = X25+X35+X45        Nodo de transbordo

Nodo 6  X63+X65+X67 = X36+X56                 Nodo de transbordo

Nodo 7  X47+X57+X67 =1                           Nodo puro de destino

Tabla

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: El criterio no cambia

Costos Mínimos: Como es de maximización se toma el de mayor costo y se inicia el método.

Vogel: Después de sacar la penalización con la resta de los costos mayores en el renglón y columna, se toma el de mayor número de penalización y se escoge la casilla con mayor costo. 

2.       ¿Qué criterio se utilizaría para determinar la variable de entrada?
El    El método de los multiplicadores. Elegimos el mas negativos y terminamos las iteraciones hasta que tengamos todo positivo.


  ¿Cómo es criterio para variable de salida?
        Construir un ciclo

4.       Encontrar la solución óptima.

X₁₁=10, X₁₂=10 y X₁₃=10 por lo tanto Z=2000

Tabla Problema de Asignación

Características	Observación
Historia del modelo	El algoritmo desarrollado por Kuhn está basado fundamentalmente en los primeros trabajos de otros dos matemáticos Húngaros: Dénes König y Jenő Egerváry. La gran ventaja del método de Kuhn es que es fuertemente polinómico). La primera versión del metodo Hungaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y a sido conocedo desde entonces como el metodo Hungaro.
Elementos	Es un caso particular del problema de transporte. Matriz de costos cuadrada (problema balanceado). La restricción más importante es que para cada agente se le asigna una y solo una tarea. El modelo de Asignación, requiere que que la matriz de costos sea cuadrada, es por ello que podemos agregar renglones o columnas con costos cero( para que sea cuadrada). Tiene que estar balanceado. Este consiste en determinar la asiganción óptima de agentes u objetos visibles a n tareas. Son indivisibles en el sentido de que ningún agente se puede dividir en varias tareas. La restricción importante, para que cada agente es que será designado a una y solo una tarea. Tratamos de minimizar los costos por asignación de recursos para el desempeño de las actividades. Xi,j=0 o Xij=1 Estos pueden ser : ·         Oficinas a personal ·         Vehiculos a rutas ·         Vendedores a regiones ·         Productos a fabricas
Ejemplo	En el problema siguiente, el objetivo es asignar personas a labores particulares mientras se minimiza el costo total. La función objetivo considera el costo que implica que cada persona realice una actividad en particular. La restricción dice que cada persona debe ser asignada a una actividad, y cada actividad debe ser asignada a solo una persona. Luego de correr el problema en cualquier paquete que proporcione soluciones de programación lineal, los resultados son: Persona 1 debería ir al trabajo 3 Persona 2 debería ir al trabajo 4 Persona 3 debería ir al trabajo 5 Persona 4 debería ir al trabajo 1 Persona 5 debería ir al trabajo 2 El costo total es $55.
Método de Solución	Los metodos de solucion son: ·         Metodo simplex ·         Tecnica de transporte ·         Metodo Hungaro Los Pasos del metodo Hngaro son: Paso 1.- Empiece por encontrar el elemento mas pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz ( la matriz de costos reducidos ) al restar de cada costo el costo mínimo de su columna. Paso 2.- Dibuje el mínimo numero de líneas (horizontales o verticales ) que se necesitan para cubrir todos los ceros en la matriz de costos reducidos. Si se requieren m líneas para cubrir todos los ceros, siga con el paso 3. Paso 3.- Encuentre el menor elemento no cero (llame su valor k en la matriz de costos reducidos, que no esta cubiertos por las líneas dibujadas en el paso 2. Ahora reste k de cada elemento no cubierto de la matriz de costos reducidos y sume k a cada elemento de la matriz de costos reducidos  cubierto por dos líneas.  Regrese al paso 2. Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda.  La matriz de costos del problema de asignación se llama: matriz de costos. Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros.
Programas existentes	·         Tora ·         Lingo ·         Goms ·         Matlab ·         QMZ ·         Solver (Excel) ·         INVOP

Referencias:

http://es.wikipedia.org/wiki/Algoritmo_h%C3%BAngaro

http://home.ubalt.edu/ntsbarsh/opre640S/SpanishIN.htm#rassipr

http://www.investigacion-operaciones.com/modelo_de_transporte.htm

Vogel

Wiliam R. Vogel

• 
  
• NACIMIENTO: 15 de noviembre 1941
• MURIÓ: 26 de agosto 2010
• 
  
• Nació Sac City ,Iowa, el 15 de noviembre de 1941. Él creció en una granja al oeste de Wall Lake, Iowa, y se graduó en 1959 como mejor alumno. Asistió a la AIB durante un año, y después sirvió en la Reserva del Ee noviembre de 1941. Él creció en una granja al oeste de Wall Lake, Iowa, y se graduó en 1jército durante seis años, luego trabajó en un banco en Storm Lake por un año. Él y Karaan se casaron 13 de septiembre 1964 y vivió en Storm Lake por un año, luego se mudó a Des Moines en 1966. 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. Él y Karaan viajado, y llevó a la familia en los viajes a la Florida. Después de unirse a la Iglesia Luterana de la Esperanza, se unió al grupo de los hombres y disfrutaron de la camaradería y la amistad de todos. Le gustaba el golf y había varios trofeos.
• William R. Vogel murió Jueves, 26 de agosto 2010, en el Mercy Hospice, Johnston, Iowa después de una batalla larga y valiente con el cáncer.

Referencia: http://hosting-24625.tributes.com/show/William-R.-Vogel-89227895

COSTOS MINIMOS

Referencia: http://www.youtube.com/watch?v=Um9FhTUcx0I

Paso 1: Identificar las celdas con el menor costo (en caso de empate se escoge una arbitrariamente), asignar  el valor mas pequeño entre la oferta y la demanda para saturar la columna o renglón, tachar el renglón o columna satisfecha.

Paso 2: Ajustar la oferta y la demanda de los renglones y columnas no tachadas regresar al paso 1 el procedimiento llega a su fin cuando quede un renglón o columna sin tachar.


Min z: 20(9)+45(6)+5(10)+15(13)+10(16)+30 (5)=1005 Solución inicial


Con Esquina Noroeste z=1090,  con Costos Mínimos z=1005 


Como podemos ver con costos mínimos salio una mejor solución esto se debe a que el método toma en cuenta los costos y en esquina noroeste no son tomados en cuenta lo cual hace que la solución sea mas grande.

ESQUINA NOROESTE

Referencia: http://www.youtube.com/watch?v=FNDKTe-ZCco&feature=player_embedded

Paso 1: Situarnos en la parte superior izquierda (1,1) saturar la columna o fila restando el valor mas pequeño de la oferta o demanda.

Paso 2: Situarnos a la siguiente celda a la parte superior izquierda y saturar la columna o renglón.

                Si se saturo la columna pasar a (1,2) y si se saturo la fila pasar a (2,1)

Paso 3: Repetir paso 2 hasta saturar  las columnas y renglones.

                Pasar a la posición (m,n)


Resultado del problema de participación 5:
Min z=20(8)+30(6)+15(12)+20(13)+10(16)+30(5)=1090 Solución inicial

PERSONAJES IMPORTANTES

Frank Lauren Hitchcock (1875-1957)

era un americano matemático y físico notable para el análisis vectorial . Él formuló el problema de transporte en 1941. También fue un experto en la química matemática y cuaterniones .

Educación

La primera vez que asistió a la Academia Phillips de Andover . Él recibió su licenciatura de Harvard en 1896. Antes de su doctorado fue profesor en París y en Kenyon Collegeen Gambier, Ohio . En 1910 completó su doctorado en Harvard con una tesis titulada,Funciones vectoriales de un punto.

Carrera

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 .

Muere el 31 de Mayo de 1957 en Los Ángeles, Estados Unidos.

Referencia:
http://translate.google.com.mx/translate?hl=es&langpair=en|es&u=http://en.wikipedia.org/wiki/Frank_Lauren_Hitchcock

ABRAHAM Charnes (1917-1992)

Abraham Charnes, profesor emérito de ciencias de la gestión y los sistemas de información, murió el 19 de diciembre de 1992. Tenía 75 años.

Profesor Charnes nació el 4 de septiembre de 1917, en Hopewell, Virginia. 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.

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

Hay sus muchos logros incluyen un trabajo pionero en la optimización matemática. Su descubrimiento básico de la asociación de la independencia lineal de los puntos extremos de los poliedros convexos fue particularmente notable. Se trasladó a Purdue en 1955 y de la Universidad de Northwestern en 1957. Al noroeste de la investigación que realizó con éxito en muchas disciplinas, como la programación estocástica, inversas generalizadas, la teoría de juegos y la programación no lineal.

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.

Referencia:
http://translate.google.com.mx/translate?hl=es&langpair=en|es&u=http://www.utexas.edu/faculty/council/2000-2001/memorials/AMR/Charnes/charnes.html
http://www.informs.org/About-INFORMS/History-and-Traditions/Miser-Harris-Presidential-Portrait-Gallery/Abraham-Charnes

William Cooper

Cooper nació en Birmingham, Alabama en 1914.

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


Un autor prodigioso, sus escritos, a menudo centrada en los enfoques cuantitativos y creativa a la gestión. Igualmente importantes han sido sus contribuciones a la gestión de la educación como se señala en los informes de Ford y la Fundación Carnegie. Trabajar con otros, es autor de 17 libros y más de 450 artículos, incluyendo los que tienen los miembros de Salón de la Fama Robert Trueblood, Eric Kohler, y Ijiri Yuji. 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 ".

Referencia:

http://fisher.osu.edu/departments/accounting-and-mis/the-accounting-hall-of-fame/membership-in-hall/william-wager-cooper/