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