• Author / Uploaded
• Eduard Chara

Citation preview

El método del cruce del arrollo también llamado algoritmo de Stepping –Stone, es un método de programación lineal que consiste en calcular cuál sería la variación del costo del envio de una unidad de cierto producto por cada una de las ruta posibles, es decir asignar cierta cantidad de artículos desde varios origines (fabricas) a un conjunto de destinos (clientes) de tal manera que se disminuyan los costos, hasta optimizar la función objetivo. Para mostrar el funcionamiento de este método Vamos a determinar la solución optima del siguiente modelo con el método del cruce del arrollo DESTINOS Fuentes

1

1

10

2

3

4

Oferta

0

20

11

15

2

12

7

9

20

25

3

0

14

16

18

5

Demanda

5

15

15

10

45

Tenemos 4 destinos y 3 fuentes cada fuente es de donde va a salir el material, y los destinos serian los clientes. En la parte inferior de la tabla tenemos la demanda de cada cliente y en la parte derecha la oferta de cada fuente Queremos determinar cuánto material enviar de cada fuente a cada destino minimizando los costos, en la parte superior derecha están el costo de envió cada celda, por ejemplo por cada artículo que se envié de la fuente dos al cliente dos tendrá un costo de 7 unidades monetarias. 1. El primer paso es verificar que la oferta y la demanda son iguales, en cuanto a la oferta15+25+5 serian 45 y la demanda seria 5+15+15+10 igual a 45, es decir que son iguales 2. Hallar la solución inicial factible ya sea por el método de la esquina noroeste, costo mínimo o aproximación de vogél, una vez hallada, se calcula la solución es decir Z y verificamos si la solución es degenerada con la formula numero de columnas mas

numero de filas menos uno debe ser menor o igual al numero de celda vacias ( #C + #F – 1 ≤ # celdas vacias) DESTINOS Fuentes

1

1

10

2

3

4

Oferta

0

20

11

15

2

12

7

9

20

25

3

0

14

16

18

5

Demanda

5

15

15

10

45



Z= 410



F+C-1 ≤numero de casillas llenas 4+3-1 ≤6 si se cumple 1. Luego pasamos esta solución a una nueva tabla para hacer la primera iteración iniciamos colocando el número 10 en la parte derecha de la primera fila, también puedes ser un cero por ejemplo y dará el mismo resultado, El numero 10 va a representar toda la primera fila, así que procedemos a restar el costo de las casillas llenas menos el numero 10.10 menos 10, cero, este número se coloca en la parte arriba, luego 0 menos 10… Menos 10, no continuamos porque las siguientes son vacías, así que continuamos con el -10 que representa la segunda columna 2.

1. Debido a que se necesita hallar una solución optima mejor que la anterior hay que asignarle una cantidad de material a una de las celdas vacías, así que comenzamos a sumar los números que hayamos, en cada casilla vacia se suma el numero de la fila mas el de la calumna.

Se marca con un punto las casillas en que la cantidad de material sea mayor al costo en este caso son 17, 15 y 13, a la casilla que le vamos a asignar el material es a la que tenga el menor costo de trasporte, en este caso es el 15 , pero si le asignamos un valor a esta casilla la primera columna y la última fila quedan con material de sobra, por esto le restamos esta misma cantidad a la fila y la columna, luego la primera fila queda con menos material, por esto se le suma esta misma cantidad a la casilla del 10, entonces la segunda columna queda con exceso de material, así q se le resta esta misma cantidad a la celda siguiente que sería el 5 y finalmente para equilibrar la segunda fila se suma este valor a la casilla del5 y de esta manera cerramos el ciclo, y la cantidad de material asignado que se sumara y restara en las casillas será el menor valor de las casillas con signo negativo, en este caso sería el 5

Luego repetimos una vez más el ciclo desde el paso 3, hallamos la solución Z y si la solución es degenerada: Hallamos el costo en esta solución optima y obtenemos Z= 15(9)+10(20)= 335 De lo cual podemos observar que el costo mínimo es menor al hallado anteriormente. Luego procedemos a verificar si la solución es degenerada

#F + #C-1≤ casillas llenas de lo

cual tenemos: 4+3-1 ≤ 4 Debido a que no se cumple al inecuación podemos deducir que esta solución si es degenerada por lo cual necesitaremos una cantidad muy pequeña llamada épsilon (E ) su valor tiende a cero , serian dos para cumplir la desigualdad. Al finalizar obtenemos la siguiente tabla y repetimos el ciclo. Sabremos que hemos terminado una vez el costo mínimo (Z) deja de disminuir o deja de haber casillas marcadas con *

Z=7(10)+15(9)+10(11)=315 es decir que el costo disminuyo Verificamos si la solución es degenerada y obtenemos 4+3-1≤5 no se cumple la inecuación, por lo cual necesitamos un épsilon, Al finalizar obtenemos la siguiente solución.

Si embargo en este caso no hay ninguna casilla en la que se pueda marcar * por lo cual la respuesta con un costo de Z=315 es:

Es un método de programación lineal para la asignación de artículos de un conjunto de origines a un conjunto de destinos de tal manera que se optimice la función objetivo. Esta técnica es particularmente usada en organizaciones que producen el mismo producto en numerosas plantas y que envía sus productos a diferentes destinos (Centros de distribución, almacenes). También se aplica en distribución, análisis de localización de plantas y programación de la producción. Se han desarrollado diferentes enfoques para resolver este problema de distribución, tales como: El método de la esquina noroeste, el método modificado de la esquina noroeste (celda mínima), método del trampolín (Cruce de arroyo, stepping stone), método de la distribución modificada (MODI), método de aproximación de Vogel y el método simplex.

Para que un problema pueda ser solucionado por el método de transporte, este debe reunir tres condiciones: 1) La función objetivo y las restricciones deben de ser lineales. 2) Los artículos deben de ser uniformes e intercambiables, los coeficientes de todas las variables en la ecuación deben de ser 0 o 1. 3) La suma de las capacidades de las fuentes debe ser igual a la suma de los requerimientos de los destinos, si alguna desigualdad existe una variable de holgura deberá ser añadida.

. METODO DE LA ESQUINA NOROESTE. Este método comienza asignando la cantidad máxima permisible para la oferta y la demanda a la variable X11 (la que está en la esquina noroeste de la tabla). La columna o renglón satisfechos se tacha indicando que las variables restantes en la columna o renglón tachado son igual a cero. Si la columna y el renglón se satisfacen simultaneamente, únicamente uno (cualquiera de los dos) debe tacharse. Esta condición garantiza localizar las variables básicas cero si es que existen. Después de ajustar las cantidades de oferta y demanda para todos los renglones y columnas no tachados, la cantidad máxima factible se asigna al primer elemento no tachado en la nueva columna o renglón. El procedimiento termina cuando exactamente un renglón o una columna se dejan sin tachar. Ejemplo: Una compañía tiene 3 almacenes con 15, 25 y 5 artículos disponibles respectivamente. Con estos productos disponibles desea satisfacer la demanda de 4 clientes que requieren 5, 15, 15 y 10 unidades respectivamente. Los costos asociados con el envío de mercancía del almacén al cliente por unidad se dan en la siguiente tabla.

ALMACEN 1 2 3

1 10 12 0

CLIENTES 2 0 7 14

3 20 9 16

4 11 20 18

Se construye la solución básica inicial por el método de la esquina noroeste.