Aproximación de Vogel
En
este apartado estudiaremos un poco sobre el método de vogel como un método de
aplicación de la investigación de operaciones, que nos permitirá analizar los
problemas y llegar a un resultado óptimo para la obtención de las máximas
ganancias. es un método 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 numero 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
Este
procedimiento trata de eliminar casi toda la tabla simplex además de los datos
de entrada, para llegar a la única información necesaria que es la solución
básica factible actual, los valores actuales y los valores resultantes de las
variables no básicas. Es posible apreciar de manera global la gran diferencia
en eficiencia y conveniencia entre los métodos simplex de transporte y simplex
si ambos se aplican al mismo problema pequeño.
MÉTODO
DE VOGEL
Este método tiene como
objetivo obtener una solución inicial BF[1]. Como todas las
restricciones funcionales de los problemas de transporte son igualdades, el
método simplex obtendría esta solución mediante la introducción de variables
artificiales y su utilización como variables básicas iniciales. La solución básica
que resulta sólo es factible para la versión revisada del problema, por lo que
se necesita un buen número de iteraciones[2] para hacer que el valor de
estas variables sea igual a cero y se obtengan las soluciones BF reales. Este
procedimiento es más sencillo ya que construye de manera directa una solución
BF real en la tabla simplex de transporte. (Introduccion a la Investigacion
de Operaciones, pág. 297)
Tabla
1
8.15 Tomada de Introducción a la Investigación de operaciones pág. 296
Procedimiento general para construir una
solución inicial BF.
Al
inicio, todos los renglones de los orígenes y las columnas de destinos de la
tabla simplex de transporte se toman en cuenta para proporcionar una variable
básica (asignación).
1.
Se selecciona la siguiente variable básica (asignación) entre los renglones y
columnas en que todavía se puede hacer una asignación de acuerdo con algún
criterio.
2.
Se hace una asignación que sea tan grande como para que use el resto de los
recursos en ese renglón o la demanda restante en esa columna (lo que resulte
menor).
3.
Se elimina ese renglón o columna —la que tenía la cantidad más pequeña de los
recursos o demandas restantes— para las nuevas asignaciones. (Si el renglón y
la columna tienen la misma cantidad de recursos y demanda restantes, de manera
arbitraria se elimina el renglón. La columna se usará después para proporcionar
una variable básica degenerada, es decir, una asignación con cero unidades
encerradas en un círculo.)
Se han propuesto varios criterios diferentes para elegir las variables básicas, uno de ellos es el Método de aproximación de Vogel que dice que Para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño cij y el que le sigue de los que quedan en ese renglón o columna. (Si se tiene un empate entre el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0.) En el renglón o columna que tiene la mayor diferencia, se elige la variable que tiene el menor costo unitario que queda. (Los empates en el caso de la mayor de estas diferencias se pueden romper de manera arbitraria.)
Ejemplo.
Ahora se aplicará el procedimiento general al problema del Metro Water District
con el criterio del método de aproximación de Vogel para seleccionar la siguiente
variable básica en el paso 1. En cada iteración, después de calcular y escribir
las diferencias en cada renglón y columna que quedan bajo consideración, se
encierra en un círculo la mayor de ellas y se enmarca en un cuadro el costo
unitario menor en ese renglón o columna. La variable con este costo unitario
menor se selecciona como la siguiente variable básica y su valor se indica en
la esquina inferior derecha de la tabla actual, junto con el renglón o columna
que se elimina (vea los pasos 2 y 3 del procedimiento general). La tabla de la
siguiente iteración es la misma, pero se elimina este renglón o columna y se
resta la cantidad asignada de la demanda o los recursos correspondientes
(cualesquiera que sean los sobrantes).
La aplicación de este
procedimiento al problema del Metro Water District resulta en la serie de
tablas de parámetros que se muestran en la tabla 8.17, en donde la solución BF
inicial consiste en las ocho variables básicas (asignaciones) dadas en la
esquina inferior derecha de las tablas de parámetros respectivas.
Este ejemplo ilustra dos
características sutiles del procedimiento general que merecen atención
especial. Primero, observe que la iteración final elige tres variables (x31,
x32 y x33) para entrar a la base, en lugar de una sola que se elige en las
iteraciones anteriores. La razón es que en este punto queda sólo un renglón (el
renglón 3) sin eliminar. Por tanto, el paso 4 del procedimiento general impone
que se deben seleccionar como básicas todas las variables restantes asociadas
con el renglón 3.
Segundo, observe que la
asignación x23 5 20 en la penúltima iteración agota tanto los recursos restantes
de ese renglón como la demanda que queda en esa columna. Sin embargo, en lugar
de eliminar los dos, el paso 3 dispone que se elimine sólo el renglón y se deje
la columna para que más tarde proporcione una variable básica degenerada. En
realidad, la columna 3 se usa para este propósito en la iteración final cuando
se selecciona x33 5 0 como una de las variables básicas. Vea en la tabla 8.16
otro ejemplo de este fenómeno, donde después de hacer la asignación x12 5 20 se
elimina sólo el renglón 1, y la columna 2 se conserva para proporcionar la
variable básica degenerada x22 5 0, en la siguiente iteración.
Aunque una asignación de
cero puede parecer irrelevante, en realidad juega un papel importante, pues
como se verá pronto, el método simplex de transporte debe conocer todas las m 1
n 2 1 variables básicas, incluso aquellas que tienen un valor de cero, que
constituyen la solución BF actual. (Introduccion a la Investigacion
de Operaciones, pág. 300)
Tabla 2 8.17 Tomada de Introducción a la
Investigación de operaciones pág. 301
[1] Soluciones
Básicas Factibles
[2]
Iteración: acto de repetir un proceso con el objetivo de alcanzar una
meta deseada, objetivo o resultado.
Referencias
PRUEBA DE OPTIMALIDAD
Se obtiene ui y vj al elegir
el renglón con el mayor número de asignaciones y establecer su u1 = 0; después
se resuelve el sistema de ecuaciones cij = ui + vj para cada (i, j) tal que xij
es básica. Si cij - ui - vj ≥ 0 para toda (i, j) tal que xij es no básica,
entonces la solución actual es óptima, por lo que el proceso se detiene. De lo
contrario, se realiza una iteración. (Introduccion a la Investigacion de Operaciones, pág.
304/305)
Partiendo de una
solución inicial factible (Vogel, Esquina Noroeste, etc.) es necesario probar
la optimización de la asignación evaluando todas las celdas no asignadas
(vacías) y determinando la conveniencia de asignar en ellas. En la evaluación
de las celdas vacías para un posible mejoramiento, una ruta cerrada (ciclo) es
seleccionada. La ruta tiene movimientos horizontales y verticales, considerando
que las celdas asignadas y no asignadas pueden ser brincadas en el movimiento
para localizar una celda adecuada.
La adición y la resta
asegura que las restricciones de la unidad de capacidad y la unidad de
requerimientos no serán violadas.
Para evaluar la celda
vacía se realiza la sumatoria de los costos de cada una de las celdas en la
ruta.
Si alguna de estas
evaluaciones arrojará un signo negativo (para un problema de minimización),
entonces se deberá asignar en aquella celda con la evaluación más negativa.
Esto indicará que una reducción en el costo total puede lograrse transfiriendo
tantas unidades como sea posible a esa celda.
El número de unidades
posibles a ser transferido será igual a la mínima cantidad que se encuentra
asignada en las celdas de la ruta con costo negativo. Al realizarse
esta transferencia debe asegurarse que las restricciones de la capacidad y
de requerimientos no sean violadas (esto se hace agregando las unidades
encontradas a asignar en las celdas con signo positivo y restando estas
unidades de las celdas con signo negativo).
Si las
evoluciones de todas las celdas vacías arrojan valores positivos, entonces
se dice que la asignación es óptima.
Iteración:
1. Se determina la variable básica entrante: se elige la
variable no básica sij que tiene el valor más negativo —en términos absolutos—
para cij - ui - vj.
2. Se determina la variable básica saliente: se identifica
la reacción en cadena que se necesita para conservar la factibilidad cuando
aumenta el valor de la variable básica entrante. Entre las celdas donadoras se
selecciona la variable básica que tiene el menor valor.
3. Se determina la nueva solución BF: se suma el valor de la
variable básica saliente a las asignaciones de las celdas receptoras y se resta
a las asignaciones de las celdas donadoras. (Introduccion
a la Investigacion de Operaciones, pág. 304)
A continuación te presentamos algunos mapas mentales y ejemplos que te ayudarán a entender mejor estos temas.
No hay comentarios.:
Publicar un comentario