Método multiplicadores

INVESTIGACION DE OPERACIONES I

unidad iv: transporte y asignacion mÉtodo multiplicadores

El método de los multiplicadores es utilizado para obtener soluciones óptimas en el problema de transporte partiendo de una solución inicial. Recuerda, vimos que los métodos de solución factible inicial para el problema de transporte son: - Esquina noroeste -Costo mínimo -Aproximación de Vogel

+ info

MÉTODO DE LOS MULTIPLICADORES En este método es necesario asociar los multiplicadores, es decir, las variables ui y vj con el renglón i y columna j de la tabla de transporte, respectivamente. Para cada variable básica xij de la solución actual, los multiplicadores ui y vj deben satisfacer la ecuación siguiente: ui + vj = cij, para cada variable básica xij Los valores de los multiplicadores se pueden determinar haciendo cero u generalmente, para calcular las ecuaciones.

- Evaluación de variables no básicas Esta evaluación esta dada por la ecuación ui + vj – cij, para cada variable no básica xij Después de esta evaluación es posible determinar la variable no básica que entra, seleccionando la variable con cij más positivo

Ejemplo 1 Para ejemplificar el método de los multiplicadores utilizaremos el ejemplo de la tabla de transporte mostrado abajo. Esta tabla representa la solución inicial al problema utilizando el método de equina noroeste. Esta solución tiene un costo de $410. Variables básicas: x11, x12, x22, x23, x24, x34 Variables no básicas: x13, x14, x21, x31, x32, x33

Las ecuaciones asociadas a las variables básicas son: ui + vj = cij, para cada variable básica xij Variables básicas: x11, x12, x22, x23, x24, x34 X11 : u1 + v1 = c11 = 10, Haciendo u1 = 0, v1=10 X12 : u1 + v2 = c12 = 0 , u1 = 0, v2= 0 X22 : u2 + v2 = c22 = 7, u2 = 7, v2= 0 X23 : u2 + v3 = c23 = 9 , u2= 7, v3 = 2 X24 : u2 + v4 = c24 = 20 , u2= 7, v4 = 13 X34 : u3 + v4 = c34 = 18, u3 = 5, v4= 13,

-Evaluación de las variables no básicas Cij = ui + vj – cij, para cada variable no básica xij Variables no básicas: x13, x14, x21, x31, x32, x33 C13= u1 + v3 - c13 = 0 + 2 - 20 = -18 C14= u1 + v4 - c14 = 0 + 13 - 11 = 2 C21= u2 + v1 - c21 = 7 + 10 - 12 = 5 C31= u3 + v1 - c31 = 5 + 10 - 0 = 15 C32= u3 + v2 - c32 = 5 + 0 - 14 = -9 C33= u3 + v3 - c33 = 5 + 2 - 16 = -9 La solución evaluada no es óptima puesto que existen positivos en el resultado de las ecuaciones de las variables no básicas. X31 es el mayor positivo y tiene que formar parte de la solución entrando como variable básica

-Determinación de la variable que saliente de la solución Construcción de ciclos. El ciclo empieza y termina con la variable no básica designada para entrar, e inicia el ciclo con un ( + ). Toda esquina del ciclo debe ser una variable básica, es decir, casillas asignadas. -La variable que sale se debe seleccionar de las variables de las esquinas ( - ) del ciclo.

-Modificación de la tabla Empezaremos indicando en la tabla de transporte, la variable que se determinó como variable entrante, esta es x31.

De las esquinas con signo (-) determinaremos la variable saliente de la solución como la variable con la asignación más pequeña. En este ejemplo, todas estas esquinas (x11, x22 y x34), tienen un valor de 5, por lo que rompemos el empate de formaarbitraria y selccionaremos x34 como variable saliente.

El circuíto empieza con un signo (+) en la variable que se determinó como entrante a la solución, en este caso es x31.El circuito sólo puede continuar en las casillas de las variables básicas. El siguiente signo es (-) para mantener el equilibrio, por lo que es necesario poner ambos signos (+) y (-) por renglón y por columna. Si existen algunas casillas que no permiten acompletar el par de signos, debe ser brincada y buscar otra que si lo permita. Una vez de regreso a la casilla inicial, el circuito queda cerrado.

"Ajustamos la tabla sumando en todas las esquinas con signo (+), la cantidad asignada en la variable saliente y la restamos de las esquinas con signo (-). Eliminamos o borramos la varaible saliente. La nueva solución se muestra en la tabla siguinete. El costo de esta nueva solución es $350. Las variables básicas son ahora: x11, x12, x22, x23, x24, y x3 Variables no básicas: x13, x14, x21, x32, x33, x34

Las ecuaciones asociadas a las variables básicas son: ui + vj = cij, para cada variable básica xij Variables básicas: x11, x12, x22, x23, x24, x31 X11 : u1 + v1 = c11 = 10, Haciendo u1 = 0, v1=10 X12 : u1 + v2 = c12 = 0 , u1 = 0, v2= 0 X22 : u2 + v2 = c22 = 7, u2 = 7, v2= 0 X23 : u2 + v3 = c23 = 9 , u2= 7, v3 = 2 X24 : u2 + v4 = c24 = 20 , u2= 7, v4 = 13 X34 : u3 + v1 = c31 = 0, u3 = -10, v4= 10

-Evaluación de las variables no básicas Cij = ui + vj – cij, para cada variable no básica xij Variables no básicas: x13, x14, x21, x32,x33, x34 C13= u1 + v3 - c13 = 0 + 2 - 20 = -18 C14= u1 + v4 - c14 = 0 + 13 - 11 = 2 C21= u2 + v1 - c21 = 7 + 10 - 12 = 5 C32= u3 + v2 - c32 = 10 + 0 - 14 = -24 C33= u3 + v3 - c33 = -10 + 2 - 16 = -24 C34= u3 + v4 - c34 = -10 + 13 - 18 = -15 La solución evaluada no es óptima aún existen positivos en el resultado de las ecuaciones de las variables no básicas. X21 es el mayor positivo y tiene que formar parte de la solución entrando como variable básica

El circuíto empieza con un signo (+) en la variable que se determinó como entrante a la solución, en este caso es x21. Continua hasta cerrarse lo más pronto posible. La variable saliente presenta un empate puesto que el menor valor asignado en las variables básicas es 0, rompiendo el empate arbitrariamente, seleccionamos a x11, como variable saliente. A Ajustamos la tabla sumando y restando la cantidad asignada en la variable salliente y la borramos de la solución.

Ajustamos la tabla sumando y restando la cantidad asignada en la variable salliente y la borramos de la solución. La nueva solución es mostrada en la tabla, cuyo costo es $335. Las variables básicas son ahora: x12, x21, x22, x23, x24, y x31 Variables no básicas: x11, x13, x14,, x32, x33, x34

Las ecuaciones asociadas a las variables básicas son: ui + vj = cij, para cada variable básica xij Variables básicas: x11, x12, x22, x23, x24, x31 X12 : u1 + v2= c12 = 0, Haciendo u1 = 0, v2=0 X21 : u2 + v1 = c21 = 12 , u12= 7, v1= 5 X22 : u2 + v2 = c22 = 7, u2 = 7, v2= 0 X23 : u2 + v3 = c23 = 9 , u2= 7, v3 = 2 X24 : u2 + v4 = c24 = 20 , u2= 7, v4 = 13 X34 : u3 + v1 = c31 = 0, u3 = 5, v1= -5

-Evaluación de las variables no básicas Cij = ui + vj – cij, para cada variable no básica xij Variables no básicas: x13, x14, x21, x32,x33, x34 C11= u1 + v1 - c11 = 0 + 5 - 10 = -5 C13= u1 + v3 - c13 = 0 + 2 - 20 = -18 C21= u1 + v4 - c14 = 0 + 13 -11 = 2 C= u3 + v2 - c32 = -5 + 0 - 14 = -19 C33= u3 + v3 - c33 = -5 + 2 - 16 = -19 C34= u3 + v4 - c34 = --5 + 13 - 18 = -10 La solución evaluada no es óptima aún existen positivos en el resultado de las ecuaciones de las variables no básicas. X14 es el mayor positivo y tiene que formar parte de la solución entrando como variable básica

El circuíto empieza con un signo (+) en la variable que se determinó como entrante a la solución, en este caso es x14 Continua hasta cerrarse lo más pronto posible. La variable saliente presenta un empate puesto que el menor valor asignado en las variables básicas es 10,y corresponde a la variable x24.

Ajustamos la tabla sumando y restando la cantidad asignada en la variable salliente y la borramos de la solución. La nueva solución es mostrada en la tabla, cuyo costo es $315. Las variables básicas son ahora: x12, x14, x21, x22, x23, y x31 Variables no básicas: x11, x13,, x24, x32, x33, x34.

Las ecuaciones asociadas a las variables básicas son: ui + vj = cij, para cada variable básica xij Variables básicas: x12, x14, x21,x22, x23, x31 X12 : u1 + v2= c12 = 0, Haciendo u1 = 0, v2=0 X14 : u1 + v4 = c14 = 14 , u1= 0, v4= 11 X21 : u2 + v1 = c11 = 12, u2 = 7, v1= 5 X22 : u2 + v2 = c22 = 7 , u2= 7, v2 = 0 X23 : u2 + v3 = c23 = 9, u2= 7, v3 = 2 X34 : u3 + v1 = c31 = 0, u3 = -5, v1= 5

-Evaluación de las variables no básicas Cij = ui + vj – cij, para cada variable no básica xij Variables no básicas: x11,x13, x24, x32,x33, x34 C11= u1 + v1 - c11 = 0 + 5 - 10 = -5 C13= u1 + v3 - c13 = 0 + 2 - 20 = -18 C24= u2 + v4 - c24 = 7 + 11 -20 = -2 C32= u3 + v2 - c32 = -5 + 0 - 14 = -19 C33= u3 + v3 - c33 = -5 + 2 - 16 = -19 C34= u3 + v4 - c34 = --5 + 11 - 18 = -12 La solución evaluada es óptima dado que ya no existen positivos en el resultado de las ecuaciones de las variables no básicas.

Gracias !!

¿Tienes una idea?

Usa este espacio para añadir una interactividad genial. Incluye texto, imágenes, vídeos, tablas, PDFs… ¡incluso preguntas interactivas! Tip premium: Obten información de cómo interacciona tu audiencia:

• Visita las preferencias de Analytics;
• Activa el seguimiento de usuarios;
• ¡Que fluya la comunicación!