viernes, 18 de abril de 2008
Ejercicio del Método de Vogel
Metodo de Vogel (VAM)
miércoles, 16 de abril de 2008
Ejercicio de Asignaciòn

Los valores mas pequeños son 0,0,5,21





Interpretacion:
Asignaciòn
m= n
ai = 1 para todas las (i)
bj = 1 para todas ls (j)
Lo anterior significa que el número de orígenes o el numero de recursos debe ser igual al numero de destinos o de asignaciones, y que cada origen o recurso con relación al destino o asignación debe corresponder a uno. Igualmente se requiere que:
Xij = 0 o Xij = 1
Es decir, que cada origen o recurso tiene que estar "asignado" o seleccionado exclusivamente a un destino o auna utilizacion única. Por lo tanto, el problema consiste en determinar como se debe hacer la asignación de recursos para minimizar ya sea el costo, el tiempo, las perdidas, la falta de eficiencia etc.
La técnica mas recomendable para solucionar este tipo de problemas es a través del Método Húngaro el cual consiste en:
1. Balancear el modelo (filas, columnas)
2.Para todo renglón escogemos el menor valor y restarlos a todos los demás en el mismo renglón
3.Para cada columna escogemos el menor valor y restarlos de todos los demás en la misma columna
4. Tachar el mínimo numero de lineas verticales y horizontales de forma que todos los ceros quedan tachados
5. Usar el criterio de optimizacion
6.Seleccionar el menor valor no tachado de toda la matriz. El valor restarlo de todo elemento no tachado y sumarlo a los elementos en al interacción de dos lineas.
7. Hacer los pasos en forma sucesiva buscando tachar todos los ceros, regresar al paso 4 hasta que cada renglón y cada columna tengan una sola asignación.
Para caso de maximizacion:
Seleccionamos el mayor elemento de toda la matriz, este valor restarlo de todos los elementos, los valores negativos representan los costos de oportunidad, lo que indica que se deja de ganar o producir.
Ejercicio del Mètodo Dual
Sea Max: z= 3x+5y
Sujeta a:
x≤ 4
y ≤ 6
3x + 2y ≤ 18
x + 4y ≤ 10
Entonces:
z Min = 4z1 + 6z2 + 18z3 +10z4
Ponemos los coeficentes disponibilidad en forma de vector columna (matriz) Primal.
b=
4
6
18
10
bT= 4 6 18 10
Restricciones:
A=
1 0
0 1
3 2
1 4
AT=
1 0 3 1
0 1 2 4
Funcion Objetivo
C= 3 5
CT=
3
5
El resultado, como consecuencia de un sistema primal a un sistema dual queda de la sigueinte manera:
AT=
1 0 3 1
0 1 2 4
BT= 4 6 18 10
CT=
3
5
domingo, 13 de abril de 2008
Método Dual
El problema primal puede tener más restricciones que variables esto significa la solución "Dual". Y debe resolverse por nuevas restricciones.
1. Si el primal se refiere a maximizar el problema Dual sera minimizar
2. Los coeficientes de la funcion objetivo del primal seran los coeficientes del vector de disponibilidad de recursos en el Dual.
3. Asi los coeficientes del vector disponibilidad de recursos del problema primal seran los coeficientes de la funcion objetivo (vector costos, precios o utilidad) en el problema Dual
4. Los coeficientes de las restricciones en el primal (transpuesta de la matriz), sera la matriz de los coeficientes en el Dual.
5.Los signos de desigualdad del problema dual son contrarios a los del problema primal.
6.Las variables "x" del primal se convierten en nuevas variables "y" en el Dual.
Ejercicio de Esquina Noroeste
La planta 1 tiene 7 autos en stock, l aplanta 2 tiene 13 y la planta 3 tiene 3. El costo de enviar un auto de la planta a la agencia se puede ver en la tabla.


M+n-1 = 3+5-1= 7 casillas asignadas

Ejercicio del Método de Transporte
*Cuando no se cubren todas las cantidades de Demanda u Oferta, se agrega una columna ficticia
Método de Transporte
a) Oferta = Demanda
b) Debe haber linealidad
c) n= filas m= columnas n+m-1
*Basandose en el Método de la Esquina Noroeste
Método de las 2 Fases
Fase 1. Formula un nuevo problema reemplazando la funcion objetivo por la suma de variables artificiales
La nueva funcion objetivo se minimiza sujeta a las restricciones del problema original. Si el problema tiene un espacion factible el valor mínimo de la F.O. óptima cera cero, lo cual indica que todas las variables artificiales son cero. En este momento pasa a la fase 2.
*Si el valor mínimo de la F.O. óptima es mayor que cero el problema no tiene solución y termina anotándose que no existen soluciones factibles.
Fase 2. Utilice la solución óptima de la fase 1 como solución de inicio para el problema original. En este caso la F.O original se expresa en términos de las variables no básicas utilizando las eliminaciones usuales , Gauss- Jordan.
Ejercicio del Método de la gran "M"
1. Pasar a la forma Estandar el Modelo Matemático
2. Agregar variable artificial donde no hay variable de holgura
3.Penalizar las variables artificiales en la funcion objetivo asignando coeficiente positivo muy grande "M" (minimizar = +M, maximizar= -M)
4.Quitar las "m" de la columna artificial, ya teniendo solucion inicial
5.Se aplica el Método Simplex
Maximizar z= 3x1 + 5x2
x1 ≤ 4
2x2 ≤ 12
3x1+2x2=18
x1, x2 ≥ 0
*La funcion objetivo se debe penalizar con -M, por ser maximizacion y para hacer z=0 por lo tanto:
z= 3x1 + 5x2 -M, entonces: z-3x1-5x2+M= 0
x1 + H1 = 4
2x2 +H2 = 12
3x1 + 2x2 + A1 = 18
(-MR4+R1)
-3R2+R4; (3M+3)R2+R1
R4(-2)+R3 ; R4 (2M+5)+R1
R3(-1)+R2 ; R3 (9/2)+R1 ; R3(3/2)+R4
Solucion:
x= 2
x2=6
H1=2
x1 + H1 = 4
2x2 + H2 = 12
3x1+2x2 +A1 = 18
Entonces:
2+2 = 4
2(6) + 0 = 12
3(2) + 2(6) +0 =18
sábado, 12 de abril de 2008
Método de la Gran "M"
Llgara el momento en uqe "w" salga de la base, en este momento W= 0 y esto indica hber regresado al problema original, pero si se llega a w›0, entonces el problema no tiene solucion.
Min z= Cx + Mw
Sujeta a restricciones y penalizando a Zw1 - Cw1
Condicion de introduccion de las variables
≥ Resta
≤ Suma
Minimización
Para el caso de Minimizacion (Simplex o Tabular)
Los sistemas de inecuaciones que no tengan solucion se deben resolver por los metodos siguientes:
El Metodo de la Gran M
Metodo de las Dos Fases