Investigación de Operaciones en Redes

Vista previa del material en texto

Investigación de Operaciones en Redes
1. MÉTODO DEL TRANSPORTE
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 
	DESTINO
ORIGEN
	 
1 2 3 ... 
	 
OFERTA 
	
	
	
	DEMANDA 
	
	 
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:
	 DESTINO
ORIGEN
	Columna 
agregada 
	OFERTA
	
	
	
	DEMANDA 
	
	 
 
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.
	DESTINO
ORIGEN
	 
1 2 ... n
	OFERTA
	
	
	
	DEMANDA 
	
	 
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)
1.2 MÉTODOS UTILIZADOS EN LA PRIMERA FASE 
1.2.1 Método de la Esquina Noroeste.
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 :
1.2.2 Método de Vogel
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.
1.2.3 Método de Coste Mínimo
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.
1.2.4 Ejercicio de Aplicación Métodos Primera Fase
Dada la tabla de transporte:
	 
	 
	1
	2
	3
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	45
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	50
	D
	 
	 
	 
	 
	 
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	30
	Dem.
	40
	60
	30
	 
	 
Donde los elementos interiores representan costes, se desea determinar una solución inicial básica factible y su coste asociado con:
a) El MEN.
b) El método de Vogel.
c) El método de Coste Mínimo.
d) Comentar la calidad relativa de las soluciones obtenidas en los apartados anteriores.
SOLUCIÓN
Como la disponibilidad total es de 150 y la demanda total es de 130, el problema no es equilibrado. Para equilibrarlo, introducimos un destino ficticio (columna F) con demanda 150-30=20 y costes nulos en las posiciones de sus columnas. Tenemos entonces, la tabla:
	 
	 
	1
	2
	3
	F
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	45
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	 
	 
	
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	 
	20
	 
	 
a) El MEN comienza tomando la posición de la tabla situada más al noroeste (A,1) y situando en ella el máximo número posible de unidades, que será el mínimo entre la disponibilidad del origen A y la demanda del destino 1. En este caso, XA1=min(45,40)=40. A continuación, se reducen, en ese valor asignado, la disponibilidad de A y la demanda de 1. Se obtiene así la tabla de la que se elimina la fila y/o columna que quede satisfecha.
	 
	 
	1
	2
	3
	F
	Disp.
	A
	40
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	5
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	 
	 
	
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	0
	60
	30
	 
	20
	 
	 
En este caso, la columna 1 pasa a tener demanda 0, así que la eliminamos, teniendo ahora la tabla reducida y con bordes (disponibilidades y demandas) revisados,
	 
	 
	2
	3
	F
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	9
	 
	6
	 
	0
	5
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	
	 
	
	 
	
	 
	8
	 
	5
	 
	0
	30
	Dem.
	60
	30
	 
	20
	 
	 
Se repite elprocedimiento con esta tabla. Ahora, la esquina noroeste corresponde a la (A,2). El número de unidades que asignamos a esta aposición es XA2=min(5,60)=5. Una vez reducidas la disponibilidad de A y la demanda de 2, se obtiene:
	 
	 
	2
	3
	F
	Disp.
	A
	5
	 
	 
	 
	 
	 
	 
	 
	
	 
	9
	 
	6
	 
	0
	0
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	
	 
	
	 
	
	 
	8
	 
	5
	 
	0
	30
	Dem.
	55
	30
	 
	20
	 
	 
Prescindiendo de la fila A, que ha quedado satisfecha al convertirse en nula su disponibilidad, tenemos la nueva tabla reducida con la asignación XB2=25.
	 
	 
	2
	3
	F
	Disp.
	B
	25
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	4
	 
	0
	0
	C
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	
	 
	
	 
	
	 
	8
	 
	5
	 
	0
	30
	Dem.
	30
	30
	 
	20
	 
	 
Prescindiendo de la fila B, ya queda satisfecha, y reiterando el procedimiento, tenemos la solución básica factible que mostramos en la tabla:
	 
	 
	1
	2
	3
	F
	Disp.
	A
	40
	 
	5
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	45
	B
	 
	 
	25
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	30
	 
	20
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	10
	 
	20
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	 
	20
	 
	 
Esta solución es no degenerada, ya que el número de posiciones básicas es 7 igual al número máximo posible que es m + n – 1 = 4 + 4 – 1 = 7, donde m = número de filas y n = número de columnas de la tabla de transporte equilibrada, de posiciones básicas que puede tener una solución básica factible. El coste asociado a esta solución es:
C = 40*8 + 5*9 +25*7 +30*5 + 20*7 + 10*5 + 20*0 = 880
b) El método de Vogel comienza determinando las penalizaciones de la fila (PFi) y columna (PCj), obtenidas como el valor absoluto de la diferencia entre los dos costes menores de cada fila y cada columna, respectivamente. Situamos estos valores a la derecha y en la parte inferior de la tabla, obteniendo la tabla ampliada
	 
	 
	1
	2
	3
	F
	Disp.
	PFi
	A
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	45
	6*
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	4
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	3
	D
	 
	 
	 
	 
	 
	 
	
	
	 
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	
	0
	30
	5
	Dem.
	40
	60
	30
	20
	 
	 
	 
	 
	PCj
	2
	2
	1
	0
	 
	 
A continuación, consideramos la mayor penalización entre filas y columnas, que es 6 (marcada con un *) y corresponde a la fila A. Elegimos la posición de menor coste en esta fila, que es la (A , F), y situamos en ella el mayor número posible de unidades dado por XAF = min (45,20) = 20. Reduciendo la disponibilidad de la fila A y la demanda de la fila F en ese valor, tenemos la tabla:
	 
	 
	1
	2
	3
	F
	Disp.
	A
	 
	 
	 
	 
	 
	 
	20
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	25
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	 
	 
	
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	0
	 
	 
Eliminamos la fila y/o columna que haya quedado satisfecha, que en este caso es la columna F, y repetimos el proceso con la tabla reducida y sus bordes revisados. Las penalizaciones son ahora
	 
	 
	1
	2
	3
	Disp.
	PFi
	A
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	25
	2
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	1
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	50
	2
	D
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	30
	2
	Dem.
	40
	60
	30
	 
	 
	 
	 
	PCj
	2
	2*
	1
	 
	 
Y la mayor es 2. Como hay empate, lo rompemos arbitrariamente y tomamos, por ejemplo, la columna 2. En esta columna, el menor coste es 5, que corresponde a la posición (C , 2). Hacemos XC2 = min (50,60) = 50 y reducimos la disponibilidad de C y la demanda de 2 en tal número de unidades
	 
	 
	1
	2
	3
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	25
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	C
	 
	 
	50
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	0
	D
	 
	 
	 
	 
	 
	 
	
	 
	
	 
	7
	 
	8
	 
	5
	30
	Dem.
	40
	10
	30
	 
	 
eliminamos la fila C. La nueva tabla reducida, con las penalizaciones, es
	 
	 
	1
	2
	3
	Disp.
	PFi
	A
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	25
	2
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	1
	D
	 
	 
	 
	 
	30
	 
	 
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	30
	2*
	Dem.
	40
	10
	30
	 
	 
	 
	 
	PCj
	2
	1
	1
	 
	 
Tomamos como mayor penalización la correspondiente a la fila D, pues hay empates. En ella, la posición de menor coste es (D , 3). Hacemos XD3 = min (30 , 30) = 30 y reducimos la disponibilidad de D y la demanda de 3 en ese valor. Esto nos lleva a eliminar simultáneamente la fila D y la columna 3, indicación de degeneración en la solución inicial. Continuando con el procedimiento llegamos a la solución básica factible
	 
	 
	1
	2
	3
	Fict.
	Disp.
	A
	15
	 
	10
	 
	 
	 
	20
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	45
	B
	25
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	50
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	30
	 
	
	
	 
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	20
	 
	 
que es degenerada, ya que tiene 6 posiciones básicas, una menos que el número máximo que es 7. El coste asociado es 
C = 15*8 + 10*9 + 20*0 + 25*5 + 50*5 + 30*5 = 735
c) Método del Coste Mínimo 
En nuestra tabla, el menor coste es 0, que corresponde a toda las posiciones de la columna F. Elegimos una arbitrariamente, por ejemplo, la posición (A , F) y el mayor número de unidades que podemos asignar es XAF = min (45,20) = 20. Reducimos la disponibilidad de la fila A y la demanda de la columna F en ese número de unidades y tenemos la tabla
	 
	 
	1
	2
	3
	F
	Disp.
	A
	 
	 
	 
	 
	 
	 
	20
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	25
	B
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	 
	 
	 
	 
	
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	0
	 
	 
Eliminamos la columna F, que ha quedado satisfecha. La nueva tabla reducida con bordes revisados es:
	
 
	 
	1
	2
	3
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	25
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	C
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	50
	D
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	30
	Dem.
	40
	60
	30
	 
	 
La posición de menor coste es (C , 1). Le asignamos XC1 = min (50,40) = 40. La tabla con la disponibilidad de la fila C y la demanda de la columna 1 reducidas en ese número de unidades es:
	 
	 
	1
	2
	3
	Disp.
	A
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	25
	B
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	25
	C
	40
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	10
	D
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	30
	Dem.
	0
	60
	30
	 
	 
Y eliminando la columna 1, ya que satisfecha, se obtiene la tabla reducida:
	 
	 
	2
	3
	Disp.
	A
	 
	 
	 
	 
	 
	 
	
	 
	9
	 
	6
	25
	B
	 
	 
	 
	 
	 
	 
	
	 
	7
	 
	4
	25
	C
	 
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	10
	D
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	5
	30
	Dem.
	60
	30
	 
	 
La posición de menor coste es (B,3). Le asignamos XB3 = min (25,30) =25. Continuando con el procedimiento, se llega a la solución dada en la tabla que es no degenerada, ya que tiene 7 posiciones básicas. 
	 
	 
	1
	2
	3
	F
	Disp.
	A
	 
	 
	25
	 
	 
	 
	20
	 
	 
	 
	
	 
	8
	 
	9
	 
	6
	 
	0
	45
	B
	 
	 
	 
	 
	25
	 
	 
	 
	 
	 
	
	 
	5
	 
	7
	 
	4
	 
	0
	25
	C
	40
	 
	10
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	5
	 
	7
	 
	0
	50
	D
	 
	 
	25
	 
	5
	 
	
	 
	 
	 
	
	 
	7
	 
	8
	 
	5
	 
	0
	30
	Dem.
	40
	60
	30
	20
	 
	 
C = 25*9 + 20*0 + 25*4 +40*3 + 10*5 + 25*8 + 5*5 = 720
d) Los métodos de Vogel y de Coste mínimo han proporcionado una solución inicial básica factible, bastante mejor que el MEN. En generalesto era de esperarse, ya que el MEN distribuye las unidades en la tabla de transporte sin tener en cuenta los costes, mientras que los otros dos métodos tienen una lógica basada en ellos.
1.3 MÉTODOS UTILIZADOS EN LA SEGUNDA FASE
1.3.1 Ejercicio de Aplicación del Método de Stepping-Stone
 Dada la tabla de transporte:
	 
	 
	1
	2
	3
	4
	Disp.
	1
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	11
	 
	5
	 
	7
	400
	2
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	9
	 
	5
	 
	6
	 
	11
	700
	3
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	12
	 
	4
	 
	8
	 
	10
	100
	Dem.
	500
	400
	100
	200
	 
	 
Obtener la solución óptima con el método de Stepping-Stone a partir de la solución inicial obtenida con el MEN. 
SOLUCIÓN
La disponibilidad total (1200) coincide con la demanda total, por lo que el problema es equilibrado. Determinamos la solución inicial básica factible con el MEN. Esta es:
	 
	 
	1
	2
	3
	4
	Disp.
	1
	400
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	8
	 
	11
	 
	5
	 
	7
	400
	2
	100
	 
	400
	 
	100
	 
	100
	 
	 
	 
	
	 
	9
	 
	5
	 
	6
	 
	11
	700
	3
	 
	 
	 
	 
	 
	 
	100
	 
	 
	 
	
	 
	12
	 
	4
	 
	8
	 
	10
	100
	Dem.
	500
	400
	100
	200
	 
	 
Con coste C = 8800. Esta solución inicial es no degenerada, pues tiene 6 posiciones básicas. Podemos, entonces, comenzar el procedimiento de Stepping-Stone calculando primero el coste relativo ij de cada posición no básica a partir de la construcción de un ciclo para cada una (un ciclo para una posición no básica es un camino que comienza y termina en la posición no básica elegida, formado por segmentos alternativamente verticales y horizontales, o viceversa, con extremos en posiciones básicas. Se designarán alternativamente las posiciones del ciclo con ^+ y ^-, comenzando con ^+ en la posición no básica de partida).
Consideramos inicialmente la posición no básica (1,2). La tabla muestra el ciclo construido para ella, con el efecto sobre el objetivo debido al incremento de una unidad para las posiciones con designación ^+ y la disminución de una unidad para las posiciones con designación ^-, y el coste relativo 12.
	Posición 
	Designación
	Efecto sobre
	(i,j)
	
	el objetivo
	(1,2)
	^+
	11
	(1,1)
	^-
	-8
	(2,1)
	^+
	9
	(2,2)
	^-
	-5
	(1,2)
	^+
	-
	 Coste relativo 
	7
Procediendo de modo análogo con el resto de las posiciones no básicas, podemos determinar los demás costes relativos.
	Posición 
	Coste relativo
	(i,j)
	ij)
	(1,2)
	7
	(1,3)
	0
	(1,4)
	-3
	(3,1)
	4
	(3,2)
	0
	(3,3)
	3
Situamos éstos sobre los costes de transporte por unidad dentro de la tabla. Se obtiene así:
	 
	 
	1
	2
	3
	4
	Disp.
	1
	400
	 
	 
	7
	 
	0
	 
	-3
	 
	 
	
	 
	8
	 
	11
	 
	5
	 
	7
	400
	2
	100
	 
	400
	 
	100
	 
	100
	 
	 
	 
	
	 
	9
	 
	5
	 
	6
	 
	11
	700
	3
	 
	4
	 
	0
	 
	3
	100
	 
	 
	 
	
	 
	12
	 
	4
	 
	8
	 
	10
	100
	Dem.
	500
	400
	100
	200
	 
	 
Si todos los costes relativos fueran no negativos, la solución actual sería óptima. No es este el caso. Tomamos la posición con coste relativo más negativo, la única en este caso es (1,4), con 14 = -3. Generamos a continuación una nueva solución determinando previamente, a partir del ciclo construido con la posición (1,4), que es 
	Posición 
	Valor de
	Designación
	(i,j)
	Xij)
	
	(1,4)
	 -
	^+
	(1,1)
	400
	^ -
	(2,1)
	100
	^+
	(2,4)
	100
	^ -
la cantidad = min {Xij} = min {400,100} = 100.
 ^ -
Esta cantidad es el mayor valor que se puede asignar a la posición (1,4). Se modifica la solución actual, sumándola a las posiciones del ciclo con designación ^+, restándola a aquellas con designación ^ - y permaneciendo igual los valores del resto de las variables. Así, la nueva solución, con los nuevos costes relativos es:
	 
	 
	1
	2
	3
	4
	Disp.
	1
	300
	 
	 
	7
	 
	0
	100
	 
	 
	 
	
	 
	8
	 
	11
	 
	5
	 
	7
	400
	2
	200
	 
	400
	 
	100
	 
	 
	3
	 
	 
	
	 
	9
	 
	5
	 
	6
	 
	11
	700
	3
	 
	1
	 
	-3
	 
	0
	100
	 
	 
	 
	
	 
	12
	 
	4
	 
	8
	 
	10
	100
	Dem.
	500
	400
	100
	200
	 
	 
Sigue siendo no degenerada, ya que tiene de nuevo 6 posiciones básicas. El coste asociado será de C = 8800 + (-3)*100 = 8500, como puede también comprobarse de forma directa a partir de la tabla. Ahora, el coste relativo más grande (i único) corresponde a la posición (3,2), con 32 = -3. El ciclo para esa posición es 
	Posición 
	Valor de
	Designación
	(i,j)
	Xij)
	
	(3,2)
	 -
	^+
	(3,4)
	100
	^ -
	(1,4)
	100
	^+
	(1,1)
	300
	^ -
	(2,1)
	200
	^+
	(2,2)
	400
	^ -
la cantidad = min {100,300,400} = 100, y la nueva solución, que permanece no degenerada, es
 
	 
	 
	1
	2
	3
	4
	Disp.
	1
	200
	 
	 
	7
	 
	0
	200
	 
	 
	 
	
	 
	8
	 
	11
	 
	5
	 
	7
	400
	2
	300
	 
	300
	 
	100
	 
	 
	3
	 
	 
	
	 
	9
	 
	5
	 
	6
	 
	11
	700
	3
	 
	4
	100
	 
	 
	3
	 
	3
	 
	 
	
	 
	12
	 
	4
	 
	8
	 
	10
	100
	Dem.
	500
	400
	100
	200
	 
	 
Esta tabla contiene, además, los nuevos costes relativos. Como todos son no negativos, el procedimiento termina al haberse alcanzado la solución óptima. Esta es 
X*11 = 200, X*14 = 200, X* 21 = 300, X*22 = 300, X*26 = 100, X*32 = 100
Con coste C* = 8200.
Finalmente, observamos que en esta tabla final la posición no básica (1,3) tiene coste relativo 13 = 0, lo que significa que existen óptimas alternativas. 
1.3.2 Ejercicio de Aplicación del Método de Distribución Modificado
 
Dada la tabla de transporte
	 
	 
	1
	2
	3
	Disp.
	1
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	4
	 
	3
	 
	5
	8
	2
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	2
	 
	3
	 
	6
	5
	3
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	3
	 
	1
	 
	2
	6
	Dem.
	8
	3
	9
	 
	 
determinar la solución óptima con el método MODI a partir de la solución inicial obtenida por el procedimiento MEN.
SOLUCIÓN
La disponibilidad total es 19, menor que 20, la demanda total. El problema no es equilibrado. Añadimos un origen ficticio (F) con disponibilidad 20 – 19 = 1, que proporciona el exceso de demanda, con costes 0 en las posiciones de esta nueva fila. La solución básica factible inicial con el MEN es
	 
	 
	1
	2
	3
	Disp.
	1
	8
	 
	 
	 
	 
	 
	 
	 
	
	 
	4
	 
	3
	 
	5
	8
	2
	 
	 
	3
	 
	2
	 
	 
	 
	
	 
	2
	 
	3
	 
	6
	5
	3
	 
	 
	 
	 
	6
	 
	 
	 
	
	 
	3
	 
	1
	 
	2
	6
	F
	 
	 
	 
	 
	1
	 
	
	 
	
	 
	0
	 
	0
	 
	0
	1
	Dem.
	8
	3
	9
	 
	 
Tal solución tiene 5 posiciones básicas, si prescindimos por el momento del que aparece en la posición (1,2), siendo el máximo posible m + n – 1 = 4 + 3 – 1 = 6. Hay que añadir una posición. Las posiciones independientes son (1,2), (1,3), (2,1), (3,1) y (F,1). Elegimos de forma arbitraria la posición (1,2) como -posición, como aparece en la tabla anterior. 
Al haber convertido la solución inicial en no degenerada, podemos aplicar el método MODI, para saber si tal solución es óptima o, si no lo es, mejorarla. Comenzamos calculando los números MODI de fila ( Si, i = 1,2,3,F) y columna (Tj, j = 1,2,3) con la condición
ij = 0 = Si + Tj + Cij (i , j) básica
donde los ij son los indicadores, o costes relativos, de las variables Xij, con un significado análogo al de los indicadores en el método simples; observemos que Sij = ui + Tj = -vj, donde = ui y –vj son los valores de las variables duales del problema de transporte en formato estándar. De la condición anterior, tenemos el sistema de 6 ecuaciones lineales con 7 incógnitas, compatible indeterminado, 
S1 + T1 + 4 = 0, S1 + T2 + 3 = 0, S2 + T2 + 3 = 0
S2 + T3 + 6 = 0, S3 + T3 + 2 = 0, SF + T3 + 0 = 0
Tomando arbitrariamente la variable S1 y haciéndola, por ejemplo, igual a 0, se tiene la solución que aparece en la columna de la derecha, bajo Si, y en la fila inferior, a la derecha de Tj, de la tabla. 
	 
	 
	1
	2
	3
	Disp.
	Si
	1
	8
	 
	 
	 
	 
	-1
	 
	 
	
	 
	
	 
	4
	 
	3
	 
	5
	8
	0
	2
	 
	-2
	3
	 
	2
	 
	 
	 
	
	 
	
	*
	2
	 
	3
	 
	6
	5
	0
	3
	 
	3
	 
	2
	6
	 
	 
	 
	
	 
	
	 
	3
	 
	1
	 
	2
	6
	4
	F
	 
	2
	 
	3
	1
	 
	
	 
	
	 
	
	 
	0
	 
	00
	1
	6
	Dem.
	8
	3
	9
	 
	
	
	 
	Tj
	-4
	-3
	-6
	 
	 
	 
	 
Calculamos los indicadores de las variables o posiciones no básicas a partir de la relación
ij = 0 = Si + Tj + Cij (i , j) no básica
que también aparecen en la tabla (números sobre los costes). Puesto que existen indicadores negativos, es posible la mejora de la solución actual. Elegimos el más negativo, que corresponde a la posición (2,1), marcada con *, con 21 = -2 y construimos un ciclo para ella. Este es
	Posición 
	Valor de
	Designación
	(i,j)
	Xij)
	
	(2,1)
	 -
	^+
	(1,1)
	8
	^ -
	(1,2)
	
	^+
	(2,2)
	3
	^ -
Con valor
 = min {Xij} = min {8,3} = 3.
^ -
La nueva solución, que se mantiene no degenerada, es:
	 
	 
	1
	2
	3
	Disp.
	1
	5
	 
	
	 
	 
	 
	 
	 
	
	 
	4
	 
	3
	 
	5
	8
	2
	3
	 
	 
	 
	2
	 
	 
	 
	
	 
	2
	 
	3
	 
	6
	5
	3
	 
	 
	 
	 
	6
	 
	 
	 
	
	 
	3
	 
	1
	 
	2
	6
	F
	 
	 
	 
	 
	1
	 
	 
	 
	
	 
	0
	 
	0
	 
	0
	1
	Dem.
	8
	3
	9
	 
	 
Para esta tabla, calculamos los números MODI de fila y columna a parir del sistema
S1 + T1 + 4 = 0, S1 + T2 + 3 = 0, S2 + T1 + 2 = 0
S2 + T3 + 6 = 0, S3 + T3 + 2 = 0, SF + T3 + 0 = 0
Y los indicadores ij de las posiciones no básicas, que podemos ver en la tabla
	 
	 
	1
	2
	3
	Disp.
	Si
	1
	5
	 
	
	 
	 
	-3
	 
	 
	 
	 
	
	 
	4
	 
	3
	*
	5
	8
	0
	2
	3
	 
	 
	2
	2
	 
	 
	 
	 
	 
	
	 
	2
	 
	3
	 
	6
	5
	2
	3
	 
	5
	 
	4
	6
	 
	 
	 
	 
	 
	
	 
	3
	 
	1
	 
	2
	6
	6
	F
	 
	4
	 
	5
	1
	 
	
	
	
	 
	
	 
	0
	 
	0
	 
	0
	1
	8
	Dem.
	8
	3
	9
	 
	
	 
	 
	Tj
	-4
	-3
	-8
	 
	 
Existe un indicador negativo, así que aún es posible la mejora. Este corresponde a la posición (1,3), con 13 = -3. El ciclo para esta posición es 
	Posición 
	Valor de
	Designación
	(i,j)
	Xij)
	
	(1,3)
	 -
	^+
	(1,1)
	5
	^ -
	(2,1)
	3
	^+
	(2,3)
	2
	^ -
 
con valor = min {5,2} = 2. La nueva solución, que es no degenerada, junto con los números MODI e indicadores, se muestra en la tabla siguiente:
	 
	 
	1
	2
	3
	Disp.
	Si
	1
	3
	 
	
	 
	2
	 
	 
	 
	 
	 
	
	 
	4
	 
	3
	 
	5
	8
	0
	2
	5
	 
	 
	2
	 
	3
	 
	 
	 
	 
	
	 
	2
	 
	3
	 
	6
	5
	2
	3
	 
	2
	 
	1
	6
	 
	 
	 
	 
	 
	
	 
	3
	 
	1
	 
	2
	6
	3
	F
	 
	1
	 
	2
	1
	 
	
	
	
	 
	
	 
	0
	 
	0
	 
	0
	1
	5
	Dem.
	8
	3
	9
	 
	
	 
	 
	Tj
	-4
	-3
	-5
	 
	 
Puesto que todos los indicadores son no negativos, se ha alcanzado la optimalidad. Hacemos entonces y la solución óptima es
X*11 = 3, X*12 = 3, X*13 = 2, X*21 = 5, X*33 = 6, X*F3 =1
con coste C* = 53. Observemos que el óptimo es único, pues todos los indicadores de las posiciones no básicas son positivos.
1.4 PROBLEMA DE ASIGNACIÓN (MÉTODO HÚNGARO)
Paso1.
Deberá haber una matriz balanceada de costos, donde será restado tanto en la columna como en la fila el número más pequeño de esa columna o fila. O sea,
 con j = 1,...,n y i = 1,...,m.
Paso2.
Seleccionar un cero en cada renglón y columna de la nueva matriz de costos. Se elimina la columna y el renglón al que pertenece el cero seleccionado.
Tenemos una solución óptima, si al finalizar este paso, se ha hecho una asignación completa de ceros, en otras palabras, cada origen tiene su destino y viceversa.
Si no se ha llegado al óptimo, se continúa con el paso 3.
Paso3.
Se encuentra la condición de Köning, donde el índice cuadrado (donde concuerdan el máximo número de ceros) es igual al índice de diseminación (el número mínimo de filas y columnas, tal que si se omiten desaparecen los ceros de la matriz).
Este paso de subdivide en los siguientes:
3a) Marcar cada una de las filas que no contenga un cero asignado.
3b) Marcar cada columna que contenga un cero, (que no es necesario que esté asignado), de la fila descrita en el paso 3a).
3c) Marcar cada fila que contenga un cero asignado en la columna del paso anterior 3b).
3d) Repetir los pasos 3b) y 3c), has que no se puedan marcar más columnas o más filas.
3e) Tachar las filas que no se encuentren marcadas y las columnas que sí lo están.
3f) Seleccionar el número más pequeño de los elementos no considerados en ningún aspecto. Este elemento se restará a los demás elementos no tachados, y se sumará a los que tengan doble marca, o que estén tachados.
Los elementos que tengan una sola marca, no cambian.
1.4.1 Ejercicio de Aplicación
Una empresa de alimentación tiene en plantilla 4 ejecutivos Ei, i = 1,2,3,4, que debe asignar a cuatro grandes clientes Cj, j = 1,2,3,4. Los costes estimados (en millones de pesetas) de la asignación de cada ejecutivo a cada cliente son 
 
	 
	C1
	C2
	C3
	C4
	E1
	15
	19
	20
	18
	E2
	14
	15
	17
	14
	E3
	11
	15
	15
	14
	E4
	21
	24
	26
	24
resolverlo con el método húngaro.
SOLUCIÓN
Resolvemos el problema con el método Húngaro, un algoritmo específico para el problema de asignación, computacionalmente más eficiente que los procedimientos anteriores. 
 Como la tabla tiene todos los costes no negativos, podemos comenzar la aplicación del algoritmo cuyo primer paso consiste en generar ceros restando el menor elemento de cada fila de todos los elementos de su fila y haciendo lo mismo para las columnas con la tabla obtenida. La nueva tabla es
	 
	C1
	C2
	C3
	C4
	E1
	0
	3
	2
	3
	E2
	0
	0
	0
	0
	E3
	0
	3
	1
	3
	E4
	0
	2
	2
	3
Para ver si es posible una asignación independiente de ceros, es decir, que exista al menos un cero por fila y columna, aplicamos la heurística que consiste en buscar la fila y columna con menor número de ceros en la tabla obtenida, marcar uno de los ceros de la fila (aparece en negrita en la siguiente tabla) y tachar el resto de ceros (se indica poniendo X) que se encuentran en la misma fila y columna que el cero marcado. La fila con menor número de ceros es la primera (rompemos empates tomando la fila superior), así que marcamos el cero de la posición (1,1) y tachamos los ceros de las posiciones (2,1), (3,1) y (4,1). Ahora, la fila con menor número de ceros (no tachados) es la segunda. Marcamos, por ejemplo, el cero de la posición (2,2) y tachamos los de las posiciones (2,3) y (2,4). La tabla es
	 
	C1
	C2
	C3
	C4
	E1
	0
	3
	2
	3
	E2
	X
	0
	X
	X
	E3
	X
	3
	1
	3
	E4
	X
	2
	2
	3
Como N hemos conseguido un cero marcado por fila, no tenemos una asignación independiente, y el algoritmo debe continuar generando ceros adicionales sobre la tabla obtenida. Para ello, aplicamos el siguiente procedimiento: 
1) Marcar todas las filas (con a la derecha de la fila) que no contienen un cero marcado, que serán la tercera y cuarta.
2) Marcar columnas (con ) que tienen un cero tachado en filas marcadas, que sólo será la primera columna.
3) Marcar toda la fila que tenga un cero marcado en una columna marcada, que será la primera fila.
4) Repetir 2) y 3) hasta que no haya más filas y columnas que marcar. La tabla con las filas y columnas marcadas es
	 
	C1
	C2
	C3
	C4
	 
	E1
	0
	3
	2
	3
	
	E2
	X
	0
	X
	X
	 
	E3
	X
	3
	1
	3
	
	E4
	X
	2
	2
	3
	
	 
	
	 
	 
	 
	 
A continuación, debemos pasar líneas a través de las filas no marcadas y las columnas marcadas, que indicaremos con flechas como se puede observar en la tabla y que es el menor número de líneas verticales y horizontales (L. C.) que cubren todos los ceros de la matriz (hemos quitado la marca de los ceros y restituido los ceros tachados).
	 
	C1
	C2
	C3
	C4
	L. C.
	E1
	0
	3
	2
	3
	
	E2
	0
	0
	0
	0
	
	E3
	0
	3
	1
	3
	
	E4
	0
	2
	2
	3
	
	L. C. 
	
	 
	 
	 
	 
Ahora, seleccionamos el menor de los costes no cubiertos por las líneas anteriores, siempre será un valor positivo al estar todos los ceros cubiertos, que es c^m = 1 que corresponde a la posición (3,3). Esta cantidad la restamos a todos los elementos no cubiertos, la sumamos a los elementos cubiertos que estén en la intersección no cubiertos, la sumamos a los elementos cubiertos que estén en la intersección de una línea vertical y horizontal, y permanece igual el resto. La nueva tabla es
	 
	C1
	C2
	C3
	C4
	E10
	2
	1
	2
	E2
	1
	0
	0
	0
	E3
	0
	2
	0
	2
	E4
	0
	1
	1
	2
De nuevo, comprobamos si es posible marcar un cero por fila. Tenemos
	 
	C1
	C2
	C3
	C4
	E1
	0
	2
	1
	2
	E2
	1
	0
	X
	X
	E3
	X
	2
	0
	2
	E4
	X
	1
	1
	2
Como no hay un cero marcado por fila, no hemos alcanzado una asignación óptima y debemos generar nuevamente ceros adicionales. Aplicando el procedimiento de antes, el menor número de líneas que cubren todos los ceros está indicado en la tabla
	 
	C1
	C2
	C3
	C4
	L. C.
	E1
	0
	2
	1
	2
	
	E2
	1
	0
	0
	0
	
	E3
	0
	2
	0
	2
	
	E4
	0
	1
	1
	2
	
	L. C. 
	
	 
	 
	 
	 
El menor elemento no cubierto es c^m = 1, y la nueva tabla de asignación que también contiene los ceros marcados y tachados, es
	 
	C1
	C2
	C3
	C4
	E1
	0
	1
	X
	1
	E2
	2
	X
	X
	0
	E3
	1
	2
	0
	2
	E4
	X
	0
	X
	1
Esta tabla tiene un cero marcado por fila. Por tanto, se ha alcanzado la optimalidad. La solución es la misma
2. MÉTODO DE REDES
Aunque muchos de los problemas de optimización de redes pueden formularse como programas lineales o enteros y resolverse con los algoritmos correspondientes, existen métodos específicos que aprovechan la estructura especial de cada problema y su representación en una red, permitiendo procedimientos de solución más eficientes.
Existen un gran número de situaciones en investigación de operaciones que se pueden modelar y resolver adecuadamente como redes (nodos conectados por ramas). A manera de ilustración considere las siguientes situaciones:
a) El diseño de una re de ductos de gas natural mar adentro, que conectan las fuentes en el golfo de México con un punto de entrega cerca de la orilla. El objeto del modelo es minimizar el costo de construcción del ducto. 
 b) La determinación de la ruta más corta entre dos ciudades en una red de carreteras existente.
c) La determinación de la capacidad máxima (en toneladas por año) de una red de ductos de suspensión de carbón, que une las minas de carbón en Wyoming con las plantas de energía eléctrica en Houston. (Los ductos de suspensión transportan el carbón bombardeando agua a lo largo de ductos especialmente diseñados).
d) La determinación del programa de flujo de costo mínimo de los campos petroleros a las refinerías a través de una red de ductos.
e) La determinación del programa de tiempo (fechas de inicio y de terminación) para las actividades de un proyecto de construcción.
La solución de estas situaciones y de otras semejantes se logran por medio de una variedad de algoritmos de optimización de redes. Algunos de estos algoritmos son:
· Árbol de expansión mínima.
· Algoritmo de la ruta mas corta.
· Algoritmo del flujo máximo.
· Algoritmo de redes capacitadas de costo mínimo.
· Algoritmo de la ruta crítica.
2.1 ARBOL DE EXPANSIÓN MINIMA
Un problema de recorrido mínimo involucra a un conjunto de nodos y a un conjunto de ramas propuestas, ninguna de las cuales es orientada. Cada rama propuesta tiene un costo no negativo asociado a ella. El objetivo es construir una red conexa que contenga a todos los nodos y que sea tal que la suma de los costos asociados con las ramas realmente empleadas sea mínima. Debe suponerse que hay suficientes ramas propuestas para asegurar la existencia de una solución.
No es difícil ver un problema de recorrido mínimo se resuelve siempre mediante un árbol . (si dos nodos en una red conexa están unidos mediante dos rutas, una de estas rutas debe contener una rama cuya eliminación no desconecte a la red. El eliminar la rama puede solamente abatir el costo total). Una árbol de recorrido mínimo puede encontrarse al seleccionar inicialmente cualquier nodo y determinar cual de las ramas que coinciden con el nodo seleccionado tiene el menor costo. A esta rama se le acepta como parte de la red final. Después se completa la red iterativamente. En cada etapa del proceso iterativo, la atención se centra en aquellos nodos que ya se han eslabonado. Todas las ramas que conectan a estos nodos con nodos inconexos se consideran y se identifica a la mas barata de las ramas. Los empates se resuelven arbitrariamente. A esta rama se le acepta como parte de la red final. El proceso iterativo termina cuando se han eslabonado todos los nodos.
Si todos los costos son diferentes ( esto siempre se puede obtener mediante cambios infinitesimales ), se puede probar que el árbol de recorrido mínimo es único y que es un producto del algoritmo anterior para cualquier selección de nodo inicial.
2.1.1 Ejercicio de Aplicación
El servicio de Parques Nacionales planea desarrollar una zona campestre para el turismo. Se han señalado cuatro sitios en el área para llegar a ellos en automóviles. Estos sitios y las distancias ( en millas ) entre ellos, se presentan en la tabla. 
	 
	Entrada al parque
	Cascada
	Formación rocosa
	Mirador
	Pradera
	Entrada al parque
	....
	7.1
	19.5
	19.1
	25.7
	Cascada
	7.1
	....
	8.3
	16.2
	13.2
	Formación rocosa
	19.5
	8.3
	....
	18.1
	5.2
	Mirador
	19.1
	16.2
	18.1
	....
	17.2
	Pradera
	25.7
	13.2
	5.2
	17.2
	....
 
Para dañar lo menos posible al medio ambiente, el Servicio de Parques desea minimizar el número de millas de caminos necesario para proporcionar el acceso deseado. Determínese cómo deberán construirse los caminos para lograr este objetivo. 
SOLUCION
Los nodos son los cuatro sitios que van a desarrollarse y la entrada del parque, mientras que las ramas propuestas son los posibles caminos para unir los sitios. Los costos son el número de millas. La red completa se muestra en la siguiente figura, en donde cada sitio está representado por la primera letra de su nombre.
C
7.1
16.2
19.11
E
P
F
M
13.2
8.3
19.51
25.7
17.2
18.1
	5.2
Se selecciona arbitrariamente la entrada del parque como nodo inicial. Los costos de las ramas que llegan a este nodo se enlistan en el primer renglón de la tabla. Ya que el menor costo es 7.1, se agrega a la red la rama que va de la entrada del parque a la cascada. 
Se considerarán ahora todas las ramas que unen a la entrada del parque o a la cascada con un nuevo lugar. Estas son las ramas que van de la entrada del parque a la formación rocosa, al mirador y a la pradera; así como aquellas que van de la cascada a los mismos tres sitios. De estas, la rama más barata es aquella que va de la cascada a la formación rocosa así que se agrega a la red.
Después se consideran todas aquellas ramas que vayan hacia el mirador o la pradera, desde la entrada del parque, la cascada o la formación rocosa. De estas, la rama que va de la formación rocosa a la pradera tiene el menor costo, así que se agrega a la red. 
En esta etapa, el único sitio no comunicado es el mirador. La rama más barata que une al mirador con cualquiera de los otros sitios, es la que corresponde a la cascada. Agregando esta rama a la red, se llega a la siguiente figura la cual tiene un costo mínimo de
Z* = 7.1 + 8.3 + 5.2 + 16.2 = 36.8 millas
7.1
8.3
5.2
F
P
E
M
C
16.2
	
2.2 
ALGORITMO DE LA RUTA MAS CORTA
Un problema de la ruta más corta involucra una red conexa con un costo no negativo asociado a cada rama. A un nodo se le denomina fuente y a otro nodo se le denomina destino. El objetivo es determinar una ruta que una a la fuente con el origen, de manera que la suma de los costos asociados con las ramas en la ruta sea mínima.
Los problemas de la ruta más barata se resuelven mediante el siguiente algoritmo, en cuya aplicación todo empate será resuelto arbitrariamente.
Paso 1.
Constrúyase una lista maestra tabulando bajo cada nodo, en orden ascendente según el costo, las ramas que llegan a él. Cada rama bajo un nodo dado, se escribe con ese nodo como su primer nodo. Omítase en la lista cualquier rama que tenga a la fuente como su segundo nodo o que tenga al destino como su primer nodo.
Paso 2.
Márquese con un asterisco a la fuente y asígnese el valor 0. Localícese la rama más barata que coincida con la fuente y enciérrese en un círculo. Márquese con un asteriscoal segundo nodo de esta rama y asígnese a este nodo un valor igual al costo de la rama. Elimínense de la lista maestra todas aquellas otras ramas que tengan como segundo nodo al que se acaba de marcar con asterisco
Paso 3
Si el nodo que acaba de marcarse con asterisco es el destino continúese en el paso 5. Si no, continúese en el paso 4.
Paso 4.
Considérense en la lista maestro actual, todos los nodos marcados con asterisco que tengan bajo ellos ramas muy cerradas en un círculo. Para cada uno de ellos, agréguese el valor asignado al nodo, al costo de la rama sin círculo mas barata bajo él. Denótese a la menor de estas sumas con M y enciérrese en un círculo la rama cuyo costo contribuyó a M. Márquese con un asterisco el segundo nodo de esta rama y asígnesele el valor M. Elimínense de la lista maestra todas las otras ramas que tengan al nodo que acaba de marcarse con asterisco como segundo nodo. Continúese en el paso 3.
Paso 5.
Z* es el valor asignado al destino. Una ruta de costo mínimo se obtiene recursivamente, iniciando con el destino, al incluir en la ruta cada rama encerrada en círculo cuyo segundo nodo pertenece a la ruta.
2.2.1 Ejercicio de Aplicación.
Smart conduce diariamente a su trabajo. Debido a que acaba de terminar un curso en análisis de redes, él puede determinar la ruta más corta al trabajo. Desafortunadamente, la ruta seleccionada está excesivamente patrullada por la policía y con todas las multas pagadas por exceso de velocidad, la ruta más corta no es la mejor elección. Por consiguiente, Smart ha decidido elegir una ruta que maximice la probabilidad de no ser detenido por la policía.
La red en la figura muestra las posibles rutas entre su hogar y el trabajo y las probabilidades asociadas de que no lo detengan en cada segmento. Por consiguiente, la probabilidad de que no lo detengan camino al trabajo es el producto de las probabilidades asociadas con los segmentos sucesivos de la ruta seleccionada. Por ejemplo, la probabilidad de que no lo multen en la ruta 1 3 5 7 es 0.9 * 0.3 * 0.25 = 0.0675. El objetivo de Smart es seleccionar la ruta que maximice la probabilidad de que no lo multen.
0.8
0.35
6
4
2
0.5
0.2
0.4
0.6
7
1
0.25
0.1
0.3
0.9
5
3
El problema se puede formular como un modelo de la ruta más corta, utilizando una transformación logarítmica que convertirá el producto probabilidad en la suma de los logaritmos de probabilidades, es decir, si p1k = p 1 * p 2 * ..... * p k es la probabilidad de que no lo detengan, entonces 
log p 1k = log p 1 + log p 2 + ….. + log p k
Matemáticamente la maximización de p 1k es equivalente a la maximización de log p 1k .
Debido a que log p 1k < = 0, la maximización de log p 1k , a su vez, es equivalente a la minimización de – log p 1k . Utilizando ésta transformación, las probabilidades individuales p la figura anterior se reemplazan con –log p, para todas las j en la red, por tanto da la red de la ruta más corta en la figura siguiente:
0.45593
0.09691
1.
5
3
7
6
1
4
2
0.30103
0.69897
0.22185
0.39794
0.04576
0.60206
0.52288
Utilizando TORA, la ruta más corta en la figura anterior, está definida por los nodos 1, 3, 5 y 7, con una “longitud” correspondiente de 1.1707 ( = - log p 17 ) . Por tanto, la probabilidad máxima de que no lo detengan es p 17 = 0.0675.
2.3 ALGORITMO DE FLUJO MÁXIMO
El objetivo en un problema de flujo máximo es desarrollar un programa de embarque que maximice la cantidad de material enviado entre dos puntos. Al punto de origen se le denomina fuente; al punto final se le denomina destino. Existen varias vías de embarque que unen a la fuente con el destino, directamente o pasando por lugares intermedios denominados empalmes. Se considera que no es posible almacenar material en los empalmes, es decir, que cualquier material que llega a un empalme es embarcado inmediatamente a otro sitio.
Una red puede ser el modelo para un problema de flujo máximo. La fuente, el destino y los empalmes se representan mediante nodos, mientras que las ramas representan los conductos a través de las cuales se transportan materiales. Asociado a cada nodo N y a cada rama NM que salga de N, hay un número no negativo, o capacidad, que representa la cantidad máxima de material que puede embarcarse de N a través de NM.
0
4
B
5
10
Destino
Fuente
4
7
5
0
0
0
8
10
C
D
A
EJEMPLO:
La figura anterior es una red que tiene A como fuente, a D como destino y a B y C como empalmes. Cerca de los extremos de cada rama se indican las capacidades de flujo en ambas direcciones. Nótese que pueden embarcarse 7 unidades de A a C a lo largo de AC, pero en la dirección opuesta sólo pueden embarcarse 0 unidades, ésta asimetría permite, de desearse definir una orientación para AC. En contraste, los flujos a lo largo de BC pueden moverse en ambas direcciones, con una capacidad de 5 unidades en ambos sentidos.
Los problemas de flujo máximo se resuelven mediante el siguiente algoritmo:
Paso 1
Encuéntrese una ruta que permita el flujo positivo de material de la fuente al destino. Si no existe alguna, continúese en el paso 5.
Paso 2
Determínese el flujo máximo que puede embarcarse a lo largo de esta ruta y denótese k.
Paso 3
Disminúyase la capacidad directa (es decir, la capacidad en la dirección de flujo de las k unidades) de cada rama de ésta ruta en k y auméntese la capacidad en sentido inverso en k. Agréguense k unidades a la cantidad enviada al destino.
Paso 4
Continúese en el paso 1.
Paso 5
El flujo máximo es la cantidad de material entregada en el destino. El programa óptimo de embarque se determina comparando la red original con la red final. Cualquier reducción en capacidad significa un embarque. 
2.3.1 Ejercicio de Aplicación
Determínese el flujo máximo de material que puede ser enviado de la fuente A al destino D, a través de la red planteada en el ejemplo anterior.
Una ruta que va de la fuente al destino es la rama AD, la cual une a estos nodos directamente. Puede permitir 8 unidades. Embarcando ésta cantidad, se envían 8 unidades a D, disminuyendo en 8 la capacidad de AD y aumentando en 8 la capacidad de DA. La red resultante se muestra en la figura siguiente:
0
C
D
B
A
5
0
10
0
10
5
4
0
8
7
4
Destino
 (+8)
Fuente
 (-8)
	
Otra ruta de la fuente al destino que puede permitir el flujo positivo es { AC, CB, BD }. La cantidad máxima de material que puede ser enviado a lo largo de ésta ruta es de 4 unidades, es decir, la capacidad de BD. Haciendo este embarque, se incrementa en cuatro unidades el suministro en D, con lo cual se tiene 8+4 = 12. simultáneamente, se disminuyen en 4 unidades las capacidades de AC, CB y BD y se incrementan en esta misma cantidad las capacidades de CA, BC y DB. Entonces, la figura anterior se convierte en la siguiente figura:
8
0
8
0
3
0
C
D
B
A
9
4
10
0
10
Fuente
 (-12)
Destino
 (+12)
1
	
La ruta { AC, CD } de la figura anterior, puede permitir 3 unidades de A a D. Haciendo este embarque se aumenta en 3 unidades el suministro e D, teniéndose 12 + 3 = 15, y se disminuyen en 3 las capacidades de AC y CD. También se incrementas en 13 unidades las capacidades de CA y DC. La nueva red es la figura siguiente.
0
C
D
B
A
9
7
7
3
10
Fuente
 (-15)
Destino
 (+15)
1
8
0
0
0
8
La ruta { AB, BC, CD } de la figura anterior, puede permitir 7 unidades de la fuente al destino. Haciendo este embarque se aumenta el suministro en 15 + 7 = 22 unidades y se disminuye en 7 las capacidades de AB, BC y CD. También se incrementan en 7 unidades las capacidades de BA, CB y DC. El resultado es la figura siguiente:
0
C
D
B
A
2
7
0
10
3
Fuente
 (-22)
Destino
 (+22)
8
8
7
8
0
0
	
2.4 
ALGORITMO DE REDES CAPACITADAS DE COSTO MINIMO
El problema del flujo restringido de costo mínimo generaliza el modelo de flujo máximo en cuatro aspectos:
a) Todos los arcos son direccionales(un sentido).
b) Un costo de flujo por unidad ( no negativo ) está asociado con cada arco.
c) Los arcos pueden tener límites positivos de capacidad inferior.
d) Cualquier nodo en la red puede actuar como un punto de origen o un pozo.
El nuevo modelo determina lo flujos en los diferentes arcos que minimizan el costo total, al mismo tiempo que satisfacen las relaciones del flujo en los arcos y las cantidades de la oferta y la demanda en los nodos.
2.4.1 Ejercicio de Aplicación
GrainCo proporciona maíz de tres sitios a tres granjas avícolas. Las cantidades de la oferta en los tres sitios son 100, 200 y 50 mil bushels y la demanda en las tres granjas es de 150, 80 y 120 mil bushels. En su mayor parte GrainCo utiliza ferrocarriles para transportar el maíz a las granjas, con excepción de tres rutas en las cuales se utilizan camiones.
La figura siguiente resume la ruta disponible entre los silos y las granjas.
[-150]
$2
$1
[100]
4
1
(50,80)
$1
(70,120)
(100,120)
$4
[50]120)
6
$2
$5
$3
[-120]
3
2
5
$4
[200]
$6
[-80]
Los silos están representados por los nodos 1, 2 y 3, cuyas cantidades de oferta son [100], [200] y [50], respectivamente. Las granjas están representadas por los nodos 4, 5 y 6, cuyas cantidades de demandas son [-150], [-80] y [-120], respectivamente. Las rutas permiten el transbordo entre los silos. Los arcos (1,4), (3,4) y (4,6) son rutas de camiones. Estas rutas tienen capacidades mínimas y máximas. Por ejemplo la capacidad de la ruta (1,4) es entre 50 y 80 mil bushels. Todas las otras rutas utilizan transbordos cuya capacidad máxima es prácticamente ilimitada. Los costos de transporte por bushel se indican en los respectivos arcos.
2.5 ALGORITMO DE LA RUTA CRITICA (CMP)
El método de la ruta crítica fue diseñado para ayudar en la planificación, la programación y el control de proyectos. Un proyecto se define como una colección de actividades interrelacionadas, en la cual cada actividad requiere tiempo y recursos. El objetivo de este método es proporcionar medios analíticos para programar las actividades. Los pasos de ésta técnica son: 
a) Definir las actividades del proyecto, sus relaciones de precedencia y sus requerimientos de tiempo.
b) Después el proyecto se traduce a una red que muestra las relaciones de precedencia entre las actividades.
c) El tercer paso indica hacer cálculos específicos de red que faciliten el desarrollo del programa de tiempo para el proyecto.
Esta técnica supone relaciones deterministas de la actividad.
2.5.1 Ejercicio de Aplicación
Cierto programa se compone de 12 subrutinas A, B, ..., L. La concepción del proyecto hace que su ejecución implique el siguiente cuadro de precedencia, costes en miles de pesetas y tiempos de compleción de las subrutinas en días.
	 
	 
	Tiempo
	Tiempo
	Coste
	Coste
	Actividad
	Predecesor
	Normal
	Reducido
	Normal
	Reducido
	A
	-
	5
	3
	200
	250
	B
	-
	4
	4
	300
	300
	C
	-
	8
	7
	400
	500
	D
	A
	3
	2
	120
	150
	E
	A
	7
	5
	200
	300
	F
	C
	5
	5
	300
	300
	G
	C
	4
	3
	300
	370
	H
	B, D
	3
	3
	800
	800
	I
	F, H
	9
	6
	70
	160
	J
	F, H
	11
	7
	150
	200
	K
	E, I
	8
	6
	60
	150
	L
	G, J
	10
	9
	100
	105
a) Dibujar la red CPM.
b) Determinar el camino crítico y su duración.
c) Reducir la duración del proyecto en dos días en la forma más económica.
SOLUCION
a) La red CPM de ejecución de este proyecto con el criterio actividad – arco es:
E,7
K,8
6
2
D,3
I,9
A,5
H,3
L,10
J,11
B,4
8
7
1	
5
3
F,5
G,4
C,8
4
b) Utilizando el algoritmo CPM determinamos para cada actividad los valores PC, PT, TC y TT, que se muestran en la tabla
	Actividad
	Etiquetas
	Holgura
	Nombre
	Duración
	PC
	PT
	TC
	TT
	TT - TC
	A
	5
	0
	5
	2
	7
	2
	B
	4
	0
	4
	6
	10
	6
	C
	8
	0
	8
	0
	8
	Crítica
	D
	3
	5
	8
	7
	10
	2
	E
	7
	5
	12
	19
	26
	14
	F
	5
	8
	13
	8
	13
	Crítica
	G
	4
	8
	12
	20
	24
	12
	H
	3
	8
	11
	10
	13
	2
	I
	9
	13
	22
	17
	26
	4
	J
	11
	13
	24
	13
	24
	Crítica
	K
	8
	22
	30
	26
	34
	4
	L
	10
	24
	34
	24
	34
	Crítica
El tiempo de compleción es T = 34 días, el camino crítico C F J L, y el coste C es la suma de los costes normales de todas las actividades, 3´000.000 pesetas. 
c) Determinamos inicialmente el incremento de costes Cij por día reducido para cada actividad (i,j), a partir de la expresión 
 
Coste reducido – Coste normal
 Cij =
Tiempo Normal - Tiempo reducido
Para la actividad A asociada al arco (1,2), este coste es, en miles de pesetas:
250 – 200
 Cij = = 25
				 5 - 3
y, análogamente, para las restantes actividades. La tabla siguiente recoge tales costes:
	Actividad
	Coste reducción
	 
	Actividad
	Coste reducción
	Nombre
	(i,j)
	Cij (* 10^3 ptas)
	 
	Nombre
	(i,j)
	Cij (* 10^3 ptas)
	A
	(1,2)
	25
	 
	G
	(4,7)
	70
	B
	(1,3)
	0
	 
	H
	(3,5)
	0
	C
	(1,4)
	100
	 
	I
	(5,6)
	30
	D
	(2,3)
	30
	 
	J
	(5,7)
	12.5
	E
	(2,6)
	50
	 
	K
	(6,8)
	45
	F
	(4,5)
	0
	 
	L
	(7,8)
	5
Realizamos una representación del proyecto en un diagrama horizontal dibujando cada actividad con una barra de longitud igual a su duración y con origen en el valor de su etiqueta PC. Dibujamos el camino crítico como una línea continua sobre el eje de tiempos y el resto de actividades en diferentes niveles, utilizando líneas punteadas para indicar los enlaces entre actividades de la red CPM . El esquema es:
 A , 5 E , 7 
 D , 3 H , 3 I , 9 K , 8 
 B , 4
 
 C , 8		F , 5		 J , 11		 L , 10	 
			G , 4	
0 5 10 15 20 	25	 30 35
El procedimiento de reducción se lleva a cabo unidad a unidad. Las actividades que consideramos inicialmente para su reducción serán las actividades críticas con coste Cij > 0. Estas son C, J y L. La que conlleva menor incremento de coste el L, así que reducimos esta actividad en 1 día, teniendo el proyecto una nueva duración T = 33 y un coste C = 3005000. El camino crítico sigue siendo el mismo, aunque la duración L es de 9 días. Ahora, intentamos reducir en otro día la duración del proyecto. Observemos que L no admite una nueva reducción, pero la actividad crítica que permite reducir un día con menor incremento en el costo es J. La nueva duración de la actividad J es 10 días y el incremento de costo12500. De nuevo, permanece el mismo camino crítico.
	A , 5		E , 7
		 D , 3 H , 3 I , 9 K , 8				
 B , 4
 
 C , 8	 F , 5		J , 10		 I , 9
 G , 4
 		 		
 
 0		5	 10	 15	 15 20 	 30 	 35
 
CONCLUSIONES
· El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Entre los datos del modelo se encuentran: a) Nivel de oferta en cada fuente y la demanda en cada destino y b) El costo de transporte unitario de la mercancía de cada fuente a cada destino.
· El problema del árbol de extensión mínima consiste en encontrar las conexiones más eficientes entre todos los nodos de la red, las que por definición no deben incluir ningún lazo.
· El problema de la ruta más corta tiene que ver con la determinación de las ramas conectadas en una red de transporte que constituyen, en conjunto, la distancia más corta entre una fuente y un destino.
· La idea básica del algoritmo de flujo máximo es encontrar una trayectoria de penetración que conecte el nodo fuente con el nodo destino en modo tal, que la capacidad de cada rama en esta trayectoria sea positiva. El flujo máximo a lo largo de esta rama debe ser igual a la capacidad mínima de todas las ramasque constituyen la trayectoria.
BIBLIOGRAFÍA
BRONSON, Richard y FOURNIER, María. TEORÍA Y PROBLEMAS DE INVESTIGACIÓN DE OPERACIONES. Ed. McGraw-Hill. México,1983. P. 167-178.
RÍOS, Sixto; INSUA, David y otros. PROGRAMACIÓN LINEAL Y APLICACIONES. Ed. Alfaomega. Santafé de Bogotá, 1998. P. 193-320.
TAHA, Hamdy. INVESTIGACIÓN DE OPERACIONES: UNA INTRODUCCIÓN. Sexta Edición. Ed. McGraw-Hill. México, 1998. P. 215-279.
image6.png
image7.png
image8.png
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.png
image28.png
image29.png
image30.png
image31.png
image32.png
image33.png
image34.png
image35.png
image36.png
image37.png
image38.png
image39.png
image40.png
image41.png
image42.png
image43.png
image44.png
image45.png
image1.png
image46.png
image47.png
image2.png
image3.png
image4.png
image5.png