Definiciones Basicas II

UNIVERSIDAD APEC.




Definiciones Básicas II.













Por:
Jehisson M. Corporan Mateo (2005-0069)
Elaisy Contreras (2005-1626)
Felix Manuel (2002-1539)
Yamayco Sanchez (2007-0155)
Antonio Cabrera (2001-3203)
INDICE

I. Variables Básicas
II. Variables No Básicas
III. Tabla de Transporte
IV. Problema de Asignación
a. Método Húngaro
V. Definición del Problema de Transporte
VI. ProblemaEquilibrado o Balanceado
VII. Qué hacer cuando el problema no está balanceado?
VIII. Solución Inicial
a. Esquina noroeste
b. Costo Mínimo
c. Método Aproximación de Vogel
IX. Criterio de Optimalidad






I. Variables básicas: las correspondientes a las columnas de A que forman la matriz básica B. Variables no básicas: las restantes.
II. A las variables no básicas se las da el valor cero.
III. La tablade Transporte: Es la que permite encontrar solución a los problemas de transporte a los fines de minimizar los costos de abastecimiento a una serie de puntos de demanda a partir de un grupo de puntos de ofertas.
Crear tabla de transporte

Proveedor 1
Proveedor 2
Proveedor n

Punto de oferta 1
costo(i,j)
costo(i,j+1)
costo(i,j+m)
Oferta 1
Punto de oferta 2
costo(i+1,j)
costo(i+2,j+1)costo(i+n,j+m)
Oferta 2
Punto de oferta n
costo(i,j)
costo(i+1,j+1)
costo(i+n,j+m)
Oferta n

Demanda 1
Demanda 2
Demanda m


IV. MODELOS DE ASIGNACIÓN
Introducción al modelo de asignación.
Los problemas de asignación presentan una estructura similar a los de transporte, pero con dos diferencias: asocian igual número de orígenes con igual número de demandas y las ofertas en cada origen es de valor uno, comolo es la demanda en cada destino.
El problema de asignación debe su nombre a la aplicación particular de asignar hombres a trabajos (o trabajos a máquinas), con la condición de que cada hombre puede ser asignado a un trabajo y que cada trabajo tendrá asignada una persona.
La condición necesaria y suficiente para que este tipo de problemas tenga solución, es que se encuentre balanceado, es decir,que los recursos totales sean iguales a las demandas totales.
El modelo de asignación tiene sus principales aplicaciones en: Trabajadores, Oficinas al personal, Vehículos a rutas, Máquinas, Vendedores a regiones, productos a fabricar, etc.
a) EL algoritmo Húngaro: es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro,fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en 1957, y ha sido conocido desde entonces como el algoritmo Húngaro, el algoritmo de la asignación de Munkres, o el algoritmo de Kuhn-Munkres.
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 ventajadel método de Kuhn es que es fuertemente polinómico (ver Complejidad computacional para más detalles).
El algoritmo construye una solución del problema primal partiendo de una solución no admisible (que corresponde a una solución admisible del dual) haciéndola poco a poco más admisible.
V. Problema de transporte
En matemáticas y economía, un problema de transporte es un caso particular de problemade programación lineal en el cual se debe minimizar el coste del abastecimiento a una serie de puntos de demanda a partir de un grupo de puntos de oferta —posiblemente de distinto número—, teniendo en cuenta los distintos precios de envío de cada punto de oferta a cada punto de demanda.
VI. Modelos Equilibrado Y Balanceados
Un modelo de transporte se llama balanceado cuando:
S i ai = S j bEsto significa que la suma de los suministros de todas las plantas debe ser igual a la suma de las demandas de todos los almacenes.
VII. Cuando el problema no está balanceado
Lo que se hace entonces es balancear el problema.
Si los requerimientos exceden a los suministros, se agrega una planta ficticia, que suministrará la diferencia.
El costo de transporte desde la planta ficticia hacia cualquier...