Investigación de operaciones
UNIDAD V. ALGORITMOS ESPECIALES 5.4. Métodos de aproximación para obtener una solución básica inicial Para resolver problemas de transporte se debe crear una solución básica inicial, la obtención de esta solución inicial forma parte del método de solución más amplio para resolver problemas de transporte con el método de salto de piedra en piedra (que se verá mas adelante). Es decir, para un problema de transporte tenemos: 1. Plantear la tabla simplex (visto en el tema anterior). 2. Revisar si la oferta y la demanda son iguales, de lo contrario se debe equilibrar la oferta y la demanda con destinos y fuentes ficticias. 3. Encontrar una solución básica inicial (lo cual es la idea de éste tema). 4. Optimizar la solución básica con el método de salto de piedra en piedra (se verá en el tema siguiente) Como puede notarse, debemos aprender como equilibrar la oferta y la demanda antes de explicar como obtener una solución básica inicial.
5.4. Métodos de aproximación para obtener una solución básica inicial
Equilibrar problemas de transporte: Si la oferta es mayor a la demanda Suponga que el problema de transporte dispone de la siguiente tabla simplex. Fuente 1
Destino 3
2 $10
1 2 3 Total demanda
4
$0
$20
$11
$12
$7
$9
$20
$0
$14
$16
$18
5
15
15
Total oferta 15 25 10
10
Oferta total = 50 artículos. Demanda total = 45 artículos (FALTAN 5 artículos demandados). Entonces como la oferta es mayor a la demanda, debemos crear un destino ficticio, que nos demande 5 artículos más. (NUNCA se pueden reducir las cantidades totales, solo podemos aumentarlas). Entonces la tabla simplex debemos modificarla de la siguiente forma:
Si en el problema de transporte ya es igual la oferta a la demanda, entonces podemos continuar, si no lo es, debemos equilibrarla antes con orígenes y destinos ficticios según nos convenga.
Fuente 1 1 2 3 Total demanda
Elaboró: MC. Marcel Ruiz Martínez
Destino 3
2 $10
5
$0
$20
4
5 $11
$0
$12
$7
$9
$20
$0
$0
$14
$16
$18
$0
15
15
10
Total oferta 15 25 10
5
1
Investigación de operaciones
5.4. Métodos de aproximación para obtener una solución básica inicial
Equilibrar problemas de transporte: Si la oferta es menor a la demanda Suponga que el problema de transporte dispone de la siguiente tabla simplex. Fuente 1
Destino 3
2 $10
1 2 3 Total demanda
4
$0
$20
$11
$12
$7
$9
$20
$0
$14
$16
$18
5
15
15
Total oferta 15 20 5
Encontrar la solución básica inicial Hay tres métodos para encontrar la solución básica inicial en problemas de transporte. 1. Esquina noroeste 2. Método del costo mínimo 3. Aproximación de Vogel Método de la esquina noroeste Usaremos la siguiente tabla de transporte:
10
Fuente 1
Oferta total = 40 artículos. (FALTAN 5 artículos de oferta). Demanda total = 45 artículos. Entonces debemos modificar la tabla simplex de transporte de la siguiente forma: Fuente 1 1 2 3 4 Total demanda
Destino 3
2 $10
5
4
$0
$20
$11
$12
$7
$9
$20
$0
$14
$16
$18
$0
$0
$0
$0
15
15
Total oferta 15 20 5 5
10
Puedes ver el siguiente video para aprender a equilibrar la oferta y demanda: http://youtu.be/lgzTxswfF1k
Elaboró: MC. Marcel Ruiz Martínez
1 2 3 Total demanda
Destino 3
2
5
4
$10
$0
$20
$11
$12
$7
$9
$20
$0
$14
$16
$18
15
15
Total oferta 15 25 5
10
Los pasos del algoritmo son: 1. Disponer de la tabla simplex de transporte equilibrada. 2. Iniciar en la esquina noroeste. 3. Asignar lo máximo posible (Lo menor entre la oferta y la demanda, respectivamente) 4. Actualizar la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó Columnas) en donde la oferta ó la demanda halla quedado satisfecha. 5. Moverse a la derecha o hacia abajo, según halla quedado disponibilidad para asignar. 6. Repetir los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior derecha en la que se elimina fila y columna al mismo tiempo
2
Investigación de operaciones
5.4. Métodos de aproximación para obtener una solución básica inicial
Método del costo mínimo.
Método de aproximación de Vogel
El algoritmo para obtener una solución factible inicial con el método del costo mínimo es la siguiente:
El algoritmo de vogel para obtener la solución factible inicial se explica con los siguientes pasos:
1. Disponer la tabla simplex con oferta y demanda equilibradas. 2. En la casilla que tenga el menor costo de toda la tabla asignar la máxima producción posible, si hay empate, escoja arbitrariamente (Cualquiera de los empatados). 3. Asigne lo máximo posible entre la disponibilidad y el requerimiento. 4. Actualizar la disponibilidad y el requerimiento, restándoles lo asignado. 5. Moverse a la casilla con el costo mínimo de la tabla resultante reducida (Sin tener en cuenta la fila o columna satisfecha). 6. Regrese a los puntos 2, 3, 4 y 5 sucesivamente, hasta que todas las casillas queden asignadas.
1. Disponer la tabla simplex con oferta y demanda equilibradas. 2. Para cada renglón o columna en el que quede alguna oferta o alguna demanda, se calcula su penalización, que es la diferencia no negativa entre los 2 costos más pequeños de transporte Cij asociados con las variables no asignadas en ese renglón o en esa columna. 3. Identificar el renglón o la columna para la mayor diferencia (en caso de empate se selecciona uno arbitrariamente). 4. En este renglón o columna se localiza la variable no asignada (celdilla) que tenga el costo unitario más pequeño de transporte y se le asignan tantas unidades como sea posible sin ir en contra de las restricciones 5. Se calculan las nuevas diferencias y se repite el procedimiento anterior hasta satisfacer todas las demandas.
Puedes ver este video para aprender a aplicar el método del costo mínimo como solución factible inicial: http://youtu.be/n5cXI10tZMw
Elaboró: MC. Marcel Ruiz Martínez
Puedes ver este video para aprender a aplicar el método de aproximación de Vogel como solución factible inicial: http://youtu.be/oH4mxLFZw58
3
Investigación de operaciones
5.4. Métodos de aproximación para obtener una solución básica inicial
Ejemplo 1. Considere una mercancía elaborada por una empresa que tiene dos fábricas (F1 y F2) situada en dos ciudades distintas, la producción mensual de dichas fábricas es de 18 y 15 unidades respectivamente y que el número de unidades requeridas al mes por los tres mercados o almacenes (M1, M2 y M3) es de 16, 10 y 7 respectivamente, la siguiente figura indica el costo de transportación desde cualquiera de las fábricas hasta cualquiera de los mercados. Oferta (Orígenes)
Mercado
Knoxville
Jersey City
Total oferta por Fábrica (Recursos)
Planta 1
$9
$ 11
Planta 2
$ 11
$ 14
M1
M2
M3
Fábrica 1
$6
$5
$1
18
Fábrica 2
$4
$2
$4
15
Total demanda por destino
16
10
7
Determine: a) Equilibre el problema en caso de ser necesario b) Obtenga una solución factible inicial por el método de: b1) Esquina noroeste b2) Costo mínimo b3) Aproximación de Vogel
Elaboró: MC. Marcel Ruiz Martínez
Ejemplo 2: Knoxville y Jersey City. Un gerente de materias primas piensa ubicar almacenes, en Knoxville y Jersey City para absorber 30 y 60 unidades por día respectivamente de las dos plantas de la empresa, cada una de las cuales produce 45 unidades diariamente. Los costos unitarios de transporte ($) se muestran en la siguiente tabla. Oferta
Demanda Determine: a) Equilibre el problema en caso de ser necesario b) Obtenga una solución factible inicial por el método de: b1) Esquina noroeste b2) Costo mínimo b3) Aproximación de Vogel
4
Investigación de operaciones
5.4. Métodos de aproximación para obtener una solución básica inicial
Práctica 5.4. Modelo de transporte: solución factible inicial La Protac Inc. Tiene cuatro plantas ensambladoras en Europa . Las máquinas usadas en éstas plantas llegan de Estados Unidos a Europa a los puertos de Ámsterdam (A) Amberes (B) y El Havre (C) Los requerimientos de la demanda y la cantidad disponible de las máquinas en los puertos así como los costos se muestran en la siguiente tabla: Destino Origen 1 2 3 4 12 13 4 6 A 6 4 10 11 B 10 9 12 4 C 400 900 200 500 Demanda Determine: a) Equilibre el problema en caso de ser necesario b) Obtenga una solución factible inicial por el método de: b1) Esquina noroeste b2) Costo mínimo b3) Aproximación de Vogel
Oferta 500 700 800
Entrega tus resultados en forma de PRÁCTICA DE EJERCICIOS, siguiendo las rúbricas indicadas en la dirección: http://marcelrzm.comxa.com/Rubricas/Rubricas.htm Enviar el documento final por correo electrónico a las siguientes direcciones:
[email protected];
[email protected];
[email protected] y
[email protected] con copia a usted mismo. En asunto colocar: “ACTIVIDAD 5.4 MODELO DE TRANSPORTE: SOLUCIÓN FACTIBLE INICIAL”
Elaboró: MC. Marcel Ruiz Martínez
5