CONTENIDO

INTRODUCCIÓN

1. MÉTODO DEL TRANSPORTE

1.3.1 Ejercicio de Aplicación del Método de Stepping-Stone

1.3.2 Ejercicio de Aplicación del Método de Distribución Modificado

1.4.1 Ejercicio de Aplicación

2. MÉTODO DE REDES

2.1 ARBOL DE EXPANSIÓN MINIMA

2.1.1 Ejercicio de Aplicación

2.2 ALGORITMO DE LA RUTA MÁS CORTA

2.2.1 Ejercicio de Aplicación

2.3 ALGORITMO DEL FLUJO MÁXIMO

2.3.1 Ejercicio de Aplicación

2.4 ALGORITMO DE REDES CAPACITADAS DE COSTO MÍNIMO

2.4.1 Ejercicio de Aplicación

2.5 ALGORITMO DE LA RUTA CRÍTICA (CPM)

2.5.1 Ejercicio de Aplicación

CONCLUSIONES

BIBLIOGRAFÍA

INTRODUCCIÓN

En este trabajo se tratan dos aplicaciones especiales de la programación lineal: los problemas de transporte y de asignación y problemas de redes.

En el primer capítulo, se abarcará el problema de transporte que estudia la distribución de un producto homogéneo desde un conjunto de fábricas a un conjunto de almacenes o puntos de venta de modo que se satisfagan las demandas de los almacenes y no se superen las disponibilidades de las fábricas, con coste mínimo. Se identifican dos fases en la solución de los problemas; en la primera encontramos los métodos de la esquina noroeste (MEN), de Vogel y de coste mínimo. En la segunda fase se utilizan los métodos de Stepping-Stone y MODI (distribución modificada, también denominada u-v).

Por su parte, en el segundo capítulo, analizaremos el problema de redes. Dentro de los métodos que veremos aquí encontramos: árbol de expansión mínima, algoritmo de la ruta más corta, algoritmo del flujo máximo, algoritmo de redes capacitadas de costo mínimo y el algoritmo de la ruta crítica.

El modelo de transporte tiene notable interés por sus importantes aplicaciones que, como se vera en varios ejercicios, no se restringe únicamente a la distribución de mercancías.

Su procedimiento especifico de solución, llamado algoritmo de transporte consta de dos fases y es rápido y eficiente. La primera fase consiste en obtener una solución factible inicial. Se pasa después a la segunda fase, en la que se comprueba si la solución obtenida en la primera fase es óptima, y si no lo es, como mejorarla.

1.1 FORMULACIÓN DEL PROBLEMA GENERAL DE TRANSPORTE.

El problema de Transporte presenta una estructura especial de programación lineal, que requiere de la programación entera y de la no-negatividad.

Puede decirse que, existen m orígenes que surten a n centros de consumo (destinos) para cierto producto.

La capacidad de oferta del origen (i) es
filas.

La demanda del centro de consumo ( j ) es
con j = 1,2,3,...,n columnas.

Teniendo en consideración el costo unitario de enviar el producto
del origen (i) al centro de consumo ( j ).

Y de esto resulta la siguiente cuestión: ¿Cuántas unidades del producto se deben enviar del origen ( i ) al centro de consumo ( j ), de manera que comúnmente se minimicen los costos totales de Transporte, se esté satisfecha la demanda del centro de consumo sin exceder la capacidad de la oferta del origen ( i)?

El problema de transporte se representa a continuación como una matriz, que puede estar en función a los costos
o a los flujos

Expresado en forma general queda:

de donde

para j = 1, 2, 3, ..., n

donde
es la cantidad de recursos (x) asignados al destino ( j ) con su costo unitario (i).

Desarrollando la función objetivo, se tiene

Aunque la matrices de Transporte pueden presentarse de la siguiente manera:

Caso 1.

Que la oferta total sea mayor que la demanda total

Es decir,
.

Se tendrá que añadir un centro de consumo artificial(n+1) cuya demanda
en los cuales los costos unitarios
, son todos ceros con

k= 1,2,...,m que de forma matricial se expresa de la siguiente manera:

Caso2.

Que la demanda total sea mayor que la oferta total, o sea:

para lo cual se añadirá una fila a la matriz, que será (m+1), con capacidad de oferta
, los costos unitarios
son ceros, quedando la matriz de costos como sigue.

El objetivo de aumentar una columna o agregar una fila es el de balancear el problema de Transporte. Una vez hecho esto, se requerirá que la solución inicial sea básica y factible.

Para esto, los métodos de resolución al problema de Transporte para obtener la solución inicial son:

1. PRIMERA FASE:

• Método de la Esquina Noroeste

• Método Vogel.

• Método del Coste Mínimo

2. SEGUNDA FASE

• Método de Stepping - Stone

• Método Distribución Modificada (MODI)

3. PROBLEMA DE ASIGNACIÓN (MÉTODO HÚNGARO)

También llamado noroccidental o de extremos, presenta la construcción de una matriz de flujos de la siguiente manera.

Paso1

En la posición (1, 1) que es el extremo Noroeste , se decide a
, por lo tanto alguno de los valores se hacen cero.

Paso 2.

Si
es CERO, se pasa a la posición que le sigue ( "abajo" en la columna) que es la (2, 1), para hacer
Se cancela el resto de la fila con ceros; además no se considerarán estas posiciones en un futuro, exceptuando la posición
.

Por otro lado, si
, en el paso anterior, se pasa a la posición contigua (que en este caso sería (1, 2), tal que
Se cancela lo restante de la columna con ceros, y se descarta de consideración futura alguna, con excepción de la posición

Paso3.

Continuar con la misma lógica hasta llegar a la posición (m, n) de la matriz de flujos.

En esta forma se obtendrá una solución inicial factible, básica; pero bastante distante del óptimo para el problema del transporte.

Donde :

El algoritmo del Método Vogel para obtener una solución básica factible de un problema de Transporte es el que se muestra a continuación:

Paso 1.

Construcción de una matriz de costos y flujos en relación a un problema balanceado.

Ir al paso 3.

Paso2.

Usar el remanente de costos y flujos de la matriz, hasta que los flujos estén asignados.

Paso3.

Calcular las diferencias de las filas y de las columnas de la matriz de costos. Esta diferencia resulta entre los números más pequeños (tanto de filas como de columnas).

Paso4.

Seleccionar a la fila o a la columna que tenga la mayor diferencia. En caso de empate, se decide arbitrariamente.

Paso 5.

Localizar el costo más pequeño en la matriz de costos en la fila o la columna seleccionada en el paso anterior. Esta será la posición

Paso 6.

En la matriz de flujos , decidir
, con ( i, j ) identificado en el paso anterior.

Se considerará determinar la oferta con
, y la demanda será
.

Paso7.

• Si
  , llénese la fila i con ceros, exceptuando la posición
  , eliminando la fila de cualquier consideración futura.

• De resultar
  , se llenará la columna j con ceros, con excepción de la posición
  , las posiciones restantes se descartadas de tomarse en cuenta.

Continuar con el paso 2 del algoritmo.

El método del coste mínimo asigna el mayor número posible de unidades a la posición de menor coste eliminando la fila y/o columna que quede satisfecha, y repite el proceso hasta eliminar todas las filas y columnas.

Dada la tabla de transporte: