El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.
ALGORITMO DE VOGEL
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
PASO 1
Determinar para cada fila y columna una medida de penalización restando los dos costos menores en filas y columnas.
PASO 2
Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).
PASO 3
De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).
PASO 4: DE CICLO Y EXCEPCIONES
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
- Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.
Por medio de este método resolveremos el ejercicio de transporte resuelto en módulos anteriores mediante programación lineal.
EL PROBLEMA
Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.
Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.
www.ingenieriaindustrialonline.com
Formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.
SOLUCIÓN PASO A PASO
El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como se muestra a continuación.
www.ingenieriaindustrialonline.com
El paso siguiente es escoger la mayor penalización, de esta manera:
www.ingenieriaindustrialonline.com
El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es "2" y que a esa celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la planta 3".
www.ingenieriaindustrialonline.com
Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.
www.ingenieriaindustrialonline.com
Se ha llegado al final del ciclo, por ende se repite el proceso
www.ingenieriaindustrialonline.com
Iniciamos una nueva iteración
www.ingenieriaindustrialonline.com
Continuamos con las iteraciones,
www.ingenieriaindustrialonline.com
Iniciamos otra iteración
www.ingenieriaindustrialonline.com
Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con valores positivos, por ende asignamos las variables básicas y hemos concluido el método.
www.ingenieriaindustrialonline.com
Los costos asociados a la distribución son:
www.ingenieriaindustrialonline.com
www.ingenieriaindustrialonline.com
De esta manera hemos llegado a la solución a la cual también llegamos mediante programación lineal, definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse de una buena herramienta como WinQSB, STORM, LINGO, TORA etc. termina siendo mucho más eficiente que la utilización de los métodos heurísticos para problemas determinísticos;
Sin embargo, cabe recordar que uno de los errores más frecuentes en los que caen los ingenieros industriales es en tratar de adaptar sus organizaciones a los modelos establecidos, cabe recordar que son los modelos los que deben adaptarse a las organizaciones, lo cual requiere de determinada habilidad para realizar de forma inmediata cambios innovadores para sus fines.
El Método del Transporte es una aplicación singular de la programación lineal cuyo objetivo es determinar el esquema de transporte que minimice el coste total de éste, conocidos los costes unitarios desde el origen i hasta el destino j. Además, se sabe que el producto está disponible en una determinada cantidad bien cada uno de los m orígenes, y es necesario que sea llevado a cada uno de los n destinos posibles en una cantidad demandada dj.
La formulación de un problema de transporte, siguiendo un modelo de programación lineal será:
Donde:
- Z: función de costes totales que se desea minimizar.
- cij: coste de transportar una unidad de producto desde el origen i (i=1, 2,..., m) hasta el destino j (j=1, 2,..., n).
- xij: cantidad transportada de producto desde el origen i hasta el destino j.
- bi: cantidad disponible de producto en cada origen i.
- dj: cantidad demandada de producto en cada destino j.
Los problemas de transporte pueden ser resueltos mediante el Algoritmo del Simplex. Sin embargo, dadas las peculiaridades de este problema han aparecido otros algoritmos específicos que facilitan el proceso. Para su implementación se representa el problema en una tabla de doble entrada:
Método de la esquina noroeste:
El método de la esquina noroeste consta, de manera resumida, de los siguientes pasos:
1. Obtener la tabla inicial del problema de transporte.
2. Asignar en la celda de la esquina noroeste de la tabla, celda (1,1), tantas
unidades de producto como sea posible.
Ejemplo 2
170 Unidad 5 ▪ Modelo de transporte
3. Ajustar la oferta y demanda según corresponda y cancelar las celdas restantes
de la la o columna que ya está satisfecha.
4. Trasladarse hacia la celda de la derecha (si se canceló la columna) o hacia la celda
de abajo (si se canceló la la) y asignar tantas unidades como sea posible. Si es la
última celda disponible termina, en otro caso, continuar en el paso tres.
5. Interpretar la solución factible del modelo con el valor de las variables ij x .
6. Calcular los costos marginales de las celdas no básicas. Si los costos marginales
son cantidades positivas, la solución es óptima y el proceso termina. Si los
costos marginales son cantidades negativas, se requiere formar otra tabla.
Método de Vogel
El método de aproximación de Vogel o simplemete Método de Vogel, tiene la
siguiente estructura:
1. Obtener la tabla inicial del problema de transporte.
2. Anexar a la tabla inicial una la y una columna con la etiqueta Penalidad i en
ambas.
3. Calcular la penalidad para toda la y columna colocando este valor en la
columna y la anexadas.
a) La penalidad es el valor absoluto de la diferencia de los dos costos menores
por cada la y cada columna.
4. Seleccionar la penalidad mayor de todas las calculadas y ubicar la celda con
el menor costo de la la o columna de la penalidad seleccionada (los empates
entre penalidades de mayor valor se rompen arbitrariamente). En la celda de menor
costo ubicada, asignar tantas unidades como sea posible y ajustar la oferta y
demanda correspondientes.
5. Cancelar la la o columna que se haya satisfecho. Si sólo queda una la o
columna sin asignación, distribuir las cantidades restantes de la oferta en las
celdas disponibles. En caso contrario, volver al paso 3.
6. Toda vez concluida la asignación de todas las unidades disponibles, calcular
el costo del modelo de transporte e interpretar la solución.
7. Calcular los costos marginales de las celdas no básicas. Si se tienen costos
marginales mayores o iguales a cero, la solución es óptima. En otro caso, se
requiere ajustar la asignación con otra tabla.
Método de Modi:
El Método de Modi nos ofrece la oportunidad de calcular costos marginales
basados en los valores de las variables de decisión del modelo, pero aunado a esto
también nos indica la celda no básica en la cual se deben realizar los ajustes para
obtener una mejor solución. Es por esta razón que después de presentar los métodos
de la esquina noroeste y de Vogel, cerramos este capítulo con el Método de Modi.
Método de Modi
A partir de una tabla inicial con la primera solución factible calculada por
cualquier método (esquina noroeste o Vogel):
Paso 1. Calcular los multiplicadores ( ) ,
i j
u v y los costos marginales ( ) c.m.
Los multiplicadores ( ) ,
i j
u v están asociados a toda celda básica y su expresión es:
Celda i j ( ) , ; i j ij u + v = c
Esto es un sistema de m+n–1 ecuaciones y m+n incógnitas. Los valores
de los multiplicadores se obtienen suponiendo un valor arbitrario para
uno de los multiplicadores y se calcula el resto, resolviendo los m+n–1
multiplicadores restantes.
Los costos marginales están asociados a toda celda no básica, con la expresión:
Celda i j ( ) , ; . .
ij i j cm c u v = − −
Si todos los costos marginales son no negativos, la solución es óptima. Termina.
Paso 2. Si existe por lo menos un c.m. negativo, tomar la celda con mayor valor
negativo. Crear un circuito con todos los vértices en celdas de variables
básicas. Es decir, encontrar la trayectoria de la variable “no básica” que
entrará a la solución.
Paso 3. Ajustar el valor de xij en las celdas del circuito, comenzando por sumar
la variable θ a la celda seleccionada en el Paso 2, en el sentido de las
manecillas del reloj, y alternando una resta y suma de θ en cada celda de
la trayectoria hasta regresar a la celda primera, resolver una desigualdad
( 0 ij x ≥ ) para θ y ajustar la solución. En todo caso volver al Paso 1.
El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.
El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.
Este popular método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.
¿QUE ES UNA MATRIZ IDENTIDAD?
Una matriz puede definirse como una ordenación rectangular de elementos, (o listado finito de elementos), los cuales pueden ser números reales o complejos, dispuestos en forma de filas y de columnas.
La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo número tanto de columnas como de filas) de orden n que tiene todos los elementos diagonales iguales a uno (1) y todos los demás componentes iguales a cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:
Matriz identidad
La importancia de la teoría de matrices en el Método Simplex es fundamental, dado que el algoritmo se basa en dicha teoría para la resolución de sus problemas. Método Simplex Divertido xd
