Aplicación a la Formulación de los Modelos de Investigación de operaciones (página 2)

Antes de describir este procedimiento, es necesario establecer que el número de variables básicas en cualquier solución básica de un problema de transporte es una menos de lo que se espera. Normalmente en los problemas de programación lineal, se tiene una variable básica por cada restricción funcional. En los problemas de transporte con m recursos y n destinos el número de restricciones funcionales es m+n. Sin embargo,

el número de variables básicas = m + n ( 1.

Esto se debe a que se manejan restricciones de igualdad y este conjunto de m + n ecuaciones tiene una ecuación adicional o (redundante) que se puede eliminar. La razón es que se sabe que la cantidad total que se manda desde todos los orígenes debe ser igual que la cantidad total que se recibe en todos los destinos. Por lo tanto, cualquier solución básica factible en una tabla de transporte debe aparecer con exactamente m + n ( 1 asignaciones no negativas, en donde la suma de las asignaciones en cada renglón o columna es igual a su demanda o sus recursos

4.2. Métodos para encontrar soluciones factibles.

Al iniciar, todos los renglones de los orígenes y las columnas de destinos de la tabla símplex de transporte se toman en cuenta para proporcionar una variable básica (asignación).

• 1. Se selecciona la siguiente variable básica (asignación) entre los renglones y columnas en que todavía se puede hacer una asignación de acuerdo a algún criterio.

• 2. Se hace una asignación lo suficientemente grande como para que use el resto de los recursos en ese renglón o la demanda restante en esa columna (cualquiera que sea la cantidad más pequeña).

• 3. Se elimina ese renglón o columna (la que tenía la cantidad más pequeña en los recursos odemanda restantes) para las nuevas asignaciones.(Si el renglón y la columna tiene la misma cantidad de recursos y demanda restante, entonces arbitrariamente se elimina el renglón. La columna se usará después para proporcionar una variable básica degenerada, es decir, una asignación con cero unidades.)

• 4. Si sólo queda un renglón o una columna dentro de las posibilidades, entonces el procedimiento termina eligiendo como básicas cada una de las variables restantes (es decir, aquellas variables que no se han elegido ni se han eliminado al quitar su renglón o columna) asociadas con ese renglón o columna que tiene la única asignación posible. De otra manera se regresa al paso 1.

4.2.1. Método de la esquina noroeste.

• 1. Regla de la esquina noroeste: la primera elección es x11 (es decir, se comienza en la esquina noroeste de la tabla símplex de transporte). De ahí en adelante, si xij fue la última variable básica seleccionada, la siguiente elección es xi,j+1 (es decir, se mueve una columna a la derecha) si quedan recursos en el origen i. De otra manera, se elige xi+1,j (es decir, se mueve un renglón hacia abajo).

Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando la regla de la esquina noroeste en el siguiente ejemplo:

Lo primero que debemos hacer al resolver cualquier problema de transporte es comprobar que esté balanceado, si no lo estuviera, agregamos un origen o un destino artificial según sea el caso para conseguir que el problema quede balanceado y podamos comenzar a resolverlo. En nuestro ejemplo, la sumatoria de los recursos de los tres orígenes es de 10 unidades que es igual a la sumatoria de las demandas de los destinos, por lo que nuestro problema está balanceado y podemos iniciar con la resolución.

Comenzamos asignando en la esquina noroeste de la tabla, es decir, en la celda correspondiente a la variable básica x11 (paso 1), podemos observar que en la primera columna se demandan 3 unidades del bien y en el primer renglón disponemos de 5 unidades, entonces enviamos las 3 unidades demandadas desde el origen 1 hacia el destino 1 (ya que hay los recursos suficiente para satisfacer toda la demanda) y decrementamos a 2 los recursos restantes en ese origen (paso 2). Con esto cubrimos toda la demanda del primer destino (ó almacén) y lo cancelamos para las próximas asignaciones (paso3):

La siguiente asignación será en la celda correspondiente a la variable x12 (paso 1) ya que todavía le quedan recursos al origen 1 (además es la esquina noroeste de la tabla restante después de haber eliminado la primera columna). Notemos que en el segundo destino se demandan 4 unidades del bien y ahora solamente se disponen de 2 unidades en el origen 1, entonces se envían las 2 unidades del origen 1 al destino 2 para satisfacer 2 de las 4 unidades demandadas en este destino quedando 2 por satisfacer (paso 2) y cancelamos el origen 1 ya que no tiene más unidades del bien para enviar a otro destino(paso 3):

La siguiente asignación será en la celda correspondiente a la variable x22 (paso 1) ya que no le quedan unidades del bien al origen 1 (notemos también que esa celda es la que se encuentra en la esquina noroeste de la tabla restante después de haber eliminado el primer renglón y la primera columna y no olvidemos que estamos aplicando la regla de la esquina noroeste). Ya que solamente faltan 2 unidades para satisfacer por completo la demanda del segundo destino y se disponen exactamente de 2 unidades en el segundo origen, entonces enviamos 2 unidades del bien del origen 2 al destino 2 (paso 2) y cancelamos el segundo renglón ya que no le quedan más unidades para enviar a otro destino. Dejamos pendiente la eliminación de la segunda columna ya que nos servirá más adelante para hacer la asignación de una variable básica degenerada, es decir, una asignación con cero unidades (paso 3):

La siguiente asignación será en la celda correspondiente a la variable x32 (paso1) ya que no le quedan más unidades al origen 2. Notemos que "se demandan cero unidades del bien en el segundo destino", en este momento es cuando hacemos una asignación de cero unidades convirtiendo así a la variable x32 en una variable básica degenerada (paso 2) y ahora sí podemos cancelar la segunda columna para ya no considerarla más en las siguientes asignaciones (paso 3). Notemos que esta demanda de cero unidades es satisfecha sin ningún problema por el origen 3 ya que éste dispone todavía de 3 unidades del bien:

Como solamente queda un renglón dentro de las posibilidades (el renglón 3 no ha sido cancelado), entonces aplicando el paso 4 del procedimiento general para construir una solución inicial básica factible, la siguiente asignación será en la celda que corresponde a la variable x33 (paso 1). Ya que la demanda del tercer destino (2 unidades) puede ser satisfecha muy bien por el tercer origen, entonces enviamos 2 unidades del bien del origen 3 al destino 3 quedando solamente 1 unidad en el tercer origen (paso 2) para enviarlo al cuarto destino y con eso cubrir su demanda de una unidad, cancelando de esta manera tanto el destino 3 como el destino 4 y el tercer renglón ya que la demanda de todos los destinos ya ha sido satisfecha y no quedan más unidades del bien en ningún origen:

Es necesario aclarar que esta no es la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor "política de transporte" que minimice todavía más el costo total.

4.2.2. Método de aproximación de Vogel.

Método de Aproximación de Vogel: para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño (cij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0). En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden romper de manera arbitraria).

Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método de aproximación de Vogel. para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina noroeste: Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera columna. En esa columna encontramos el costo unitario (cij) menor y en esa celda realizamos la primera asignación:

Nota: Marcaremos a la mayor de las diferencias seleccionada encerrándola en un círculo y escribiéndole como superíndice el número que le corresponda en la secuencia de selección.

Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la tercera columna nos servirá después para hacer la asignación de una variable básica degenerada. Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:

Como siguiente paso deberíamos calcular las nuevas diferencias de columnas, pero ya que solamente queda un renglón dentro de las posibilidades (ésto no significa que solamente un renglón quede bajo consideración ya que podemos observar que ninguna de las cuatro columnas (destinos) ha sido eliminada y todas quedan todavía bajo consideración), no es posible encontrar la diferencia aritmética entre el costo menor y el que le sigue, por lo tanto vamos tomando una a una las celdas que quedan comenzando con la de menor costo unitario hasta que todas hayan sido asignadas.

Es necesario aclarar que ésta puede o no ser la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor "política de transporte" que minimice todavía más el costo total.

Comparación de criterios alternativos para el paso 1.

Se compararán estos dos criterios para elegir la siguiente variable básica. La virtud principal de la regla de la esquina noroeste es la facilidad y rapidez con que se aplica. Sin embargo, como no le da importancia a los costos unitarios cij, por lo general la solución que se obtiene distará mucho de la óptima. Si se realiza un esfuerzo un poco mayor para encontrar la solución inicial básica factible, es posible que se reduzca mucho el número de iteraciones que después necesita el método símplex de transporte para encontrar la solución óptima. El objetivo del otro criterio es precisamente encontrar una solución así.

El método de aproximación de Vogel ha sido el más popular durante muchos años, en parte porque es relativamente fácil hacerlo a mano. Este criterio toma en cuenta los costos unitarios en forma efectiva ya que la diferencia representa el mínimo costo adicional en que se incurre por no hacer una asignación en la celda que tiene el menor costo en esa columna o renglón.

Podemos decir, que el método de aproximación de Vogel proporciona una mejor solución inicial que el criterio de la esquina noroeste, en otras palabras es más cualitativo.

El siguiente paso después de hallar una solución inicial básica factible (por cualquiera de los dos criterios expuestos anteriormente) es verificar si esta solución inicial es efectivamente óptima aplicando la prueba de optimalidad.

La prueba de optimalidad estándar del método símplex para el problema de transporte, se puede reducir de la siguiente manera:

Una solución básica factible es óptima si y sólo si cij(ui(vj ( 0 para toda (i,j) tal que xij es no básica.

Así, lo único que hay que hacer para realizar esta prueba es obtener los valores de ui y vj para la solución básica factible actual y después calcular los valores cij(ui(vj según se describe enseguida.

Como el valor de cij(ui(vj debe ser cero si xij es una variable básica, ui y vj satisfacen el conjunto de ecuaciones:

cij = ui + vj para cada (i,j) tal que xij es básica.

Existen m+n(1 variables básicas y por tanto hay m+n(1 ecuaciones de este tipo. Como el número de incógnitas (las ui y vj) es m+n, se puede asignar un valor arbitrario a cualquiera de estas variables sin violar las ecuaciones. La elección de esta variable y su valor no afecta el valor de ningún cij(ui(vj, aun cuando xij sea no básica, por lo que la única diferencia (menor) estriba en la facilidad para resolver estas ecuaciones. Una elección conveniente para lograr esto es seleccionar la ui que tiene el mayor número de asignaciones en su renglón (los empates se rompen de manera arbitraria) y asignarle un valor de cero. Gracias a la sencilla estructura de estas ecuaciones, resulta muy fácil obtener algebraicamente los valores del resto de las variables.

Para ejemplificar la prueba de optimalidad, consideremos la solución inicial básica factible obtenida por la regla de la esquina noroeste para nuestro ejemplo en cuestión:

Observemos que resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres de las ui y cuatro de las vj), por lo que este sistema de ecuaciones no es cuadrado. La forma de resolverlo es dando un valor arbitrario a una de las incógnitas, para que, a partir de él encontremos el valor de las demás. La regla para hacer esta asignación arbitraria nos dice que sea para la ui (ó renglón) que haya tenido el mayor número de asignaciones. En nuestro ejemplo, el renglón 1 tuvo dos asignaciones, el renglón 2 tuvo una asignación y por último el tercer renglón tuvo tres asignaciones, por lo que asignamos el valor de cero a la incógnita u3. De esta asignación resulta lo siguiente:

De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:

Ahora calculemos los valores cij(ui(vj para las variables no básicas, ya que para las básicas, este valor es cero (por la forma de las ecuaciones con que se hallaron los valores de las incógnitas ui y vj), y coloquemos estos valores en la esquina inferior izquierda de cada celda:

Para la celda (1,3): 6 ( 4 ( 8 = (6

Para la celda (1,4): 4 ( 4 ( 5 = (5

Para la celda (2,1): 2 ( 1 ( ((1) = 2

Para la celda (2,3): 3 ( 1 ( 8 = (6

Para la celda (2,4): 2 ( 1 ( 5 = (4

Para la celda (3,1): 4 ( 0 ( ((1) = 5

En este momento se puede aplicar la prueba de optimalidad para verificar los valores de cij(ui(vj obtenidos. Como cuatro de estos valores (c13(u1(v3= (6, c14(u1(v4= (5, c23(u2(v3= (6, c24(u2(v4= (4), son negativos, se concluye que la solución básica factible actual no es óptima. Entonces, el método símplex de transporte debe proceder a hacer una iteración para encontrar una mejor solución básica factible.

Una iteración.

Igual que para método símplex estándar, una iteración del método símplex de transporte debe determinar una variable básica entrante (paso 1), una variable básica que sale (paso 2) y después identificar la nueva solución básica factible que resulta (paso 3).

Paso 1: como cij(ui(vj representa la tasa a la que cambia la función objetivo si se incrementa la variable no básica xij, la variable que entra debe tener un valor de cij(ui(vj negativo, para que el costo total Z disminuya. Entonces, los candidatos en la tabla anterior son x13, x14, x23 y x24 . Entre ellos se elige el valor negativo más grande (en términos absolutos) de cij(ui(vj como la variable básica entrante, que en este caso corresponde a x13 y x23. En los casos en que haya empate para la elección de la variable básica entrante, este empate se rompe de manera arbitraria, ya que tarde o temprano llegaremos a la misma solución independientemente de la elección de la variable. Pero, observemos lo siguiente: ya que debemos elegir la variable básica "entrante, es decir, aquella que comenzará a tener un valor (ya que antes no lo tenía porque era variable no básica), entonces, es conveniente que elijamos aquella que tenga el costo menor, ya que el valor de la variable entrante multiplicado por su respectivo costo será la contribución al costo total. En nuestro caso, el costo asociado a x13 es 6 y el costo asociado a x23 es 3, por lo que la variable que debemos elegir como entrante es x23.

Paso 2: si se incrementa el valor de la variable básica entrante, se establece una reacción en cadena de cambios compensatorios en otras variables básicas (asignaciones) para seguir satisfaciendo las restricciones de recursos y demanda. La primera variable básica que disminuya su valor hasta cero será la variable básica que sale. En general, siempre existe sólo una reacción en cadena (en cualquier dirección) que se puede completar con éxito para conservar la factibilidad, cuando la variable básica entrante aumenta su valor. Esta reacción en cadena se puede identificar si se hace una selección entre las celdas que tienen variables básicas: primero, la celda donadora en la columna que tiene la variable básica; después, la celda receptora en el renglón que corresponde a la celda donadora; luego, la celda donadora en la columna en que se encuentra esta celda receptora, y así sucesivamente, hasta que la reacción en cadena conduce a una celda donadora en el renglón que tiene a la variable básica entrante. Cuando una columna o renglón tiene más de una celda adicional con variable básica, puede ser necesario explorar el camino que se va aseguir para averiguar cuál debe seleccionarse como celda donadora o receptora. (Todas las demás menos la adecuada llegarán tarde o temprano a un camino sin salida en un renglón o columna que no tiene otra celda con una variable básica). Después de identificar la reacción en cadena. La celda donadora que tiene la asignación menor proporciona en forma automática la variable básica que sale. (En caso de un empate para la celda donadora, se puede elegir cualquiera para proporcionar la variable básica que sale).

Si x23 es la variable básica entrante, la reacción en cadena de la tabla anterior se resume enseguida. (Siempre se indicará la variable básica entrante colocando un signo + encuadrado dentro de su celda):

Al aumentar x23 debe disminuir x33 en la misma cantidad para conservar la demanda de 2 en la columna 3; esto a su vez requiere que se aumente x32 en esa cantidad para mantener la oferta de 3 en el renglón 3 y esto a su vez exige una disminución en el valor de x22 para conservar la demanda de 4 en la columna 2. Esta disminución en x22 completa con éxito la reacción en cadena ya que también conserva la oferta del renglón 2.

El resultado final es que las celdas (2,3) y (3,2) se convierten en celdas receptoras, cada una con su asignación adicional proveniente de las celdas donadoras (2,2) y (3,3). Estas celdas están indicadas en la tabla anterior por medio de los signos + y (). Observe que tuvo que elegirse la celda (3,2) como celda receptora para el renglón 3 y no la (3,4), ya que esta última no hubiera tenido celda donadora en la columna 4 para continuar la reacción en cadena. Note además que, a excepción de la variable básica entrante, todas las celdas receptoras y donadoras en la reacción en cadena deben corresponder a variables básicas en la solución básica factible actual.

Cada celda donadora disminuye su asignación en una cantidad exactamente igual al aumento que tiene la variable básica entrante (y las otras celdas receptoras). Entonces, la celda donadora que comienza con la asignación más pequeña (en este caso las celdas (2,2) y (3,3)( debe ser la primera en llegar a una asignación de cero conforme se incrementa la variable entrante x23. Así, x22 ó x23 se pueden convertir en la variable básica que sale. Cuando existe empate para la variable básica que sale, éste puede romperse de manera arbitraria, es decir, eligiendo cualquiera de las variables donadoras con la asignación más pequeña como variable básica saliente. Como una regla empírica, podemos seleccionar como variable básica saliente aquélla que tenga asociado el mayor costo unitario, ya que como esta variable perderá completamente su valor (es decir, se convertirá de variable básica a variable no básica), esperaríamos que el costo total de transporte disminuya. Así, escogeríamos a x33 como variable básica saliente.

Paso 3: la nueva solución básica factible se identifica sumando el valor (antes de los cambios) de la variable básica que sale a las asignaciones de cada celda receptora y restando esta misma cantidad de las asignaciones de cada celda donadora. En la tabla anterior se observa que el valor de la variable básica que sale x33 es 2, por lo que esta porción de la tabla símplex de transporte cambia, como se ilustra en la siguiente tabla para la nueva solución. (Como x33 es no básica en la nueva solución, su nueva asignación es cero y ya no se muestra en la tabla).

es decir, el costo total de transporte se decrementa en 12 unidades con respecto al costo anterior que era de 52 unidades. Notemos que hemos obtenido una nueva política de transporte, la cual podemos resumir así:

La nueva solución básica factible es x11=3, x12=2, x22=0 (variable básica degenerada), x23=2, x32=2 y x34=1 y el costo total de transporte asociado es de:

Antes de completar la solución del problema ejemplo, se hará un resumen de las reglas del método símplex de transporte.

Resumen del método símplex de transporte

Inicialización: Se construye una solución inicial básica factible. Se realiza la prueba de optimalidad.

Prueba de optimalidad: Se obtiene ui y vj eligiendo el renglón con el mayor número de asignaciones y estableciendo su ui = 0, y después resolviendo el sistema de ecuaciones cij = ui+vj para cada (i,j) tal que xij es básica. Si cij(ui(vj ( 0 para toda (i,j) tal que xij es no básica, entonces la solución actual es óptima por lo que el proceso se detiene. De lo contrario, se regresa a una iteración.

Iteración:

• 1. Se determina la variable básica entrante: se elige la variable no básica xij que tiene el valor negativo más grande (en términos absolutos) para cij(ui(vj.

• 2. Se determina la variable básica que sale identificando la reacción en cadena (encontrar un circuito) que se necesita para conservar la factibilidad cuando se aumenta el valor de la variable básica entrante. Entre las celdas donadoras se selecciona la variable básica que tiene el menor valor.

• 3. Se determina la nueva solución básica factible: se suma el valor de la variable básica que sale a las asignaciones de las celdas receptoras y se resta este valor a las asignaciones de las celdas donadoras.

Continuando con la aplicación de este procedimiento a nuestro problema, tenemos que calcular los nuevos valores de las ui y vj y después los valores cij(ui(vj correspondientes a las variables no básicas para determinar si todos cumplen con la prueba de optimalidad: Nuevamente existen m+n(1=3+4(1=6 variables básicas, que dan origen al siguiente conjunto de ecuaciones:

3 = u1+v1

7 = u1+v2

4 = u2+v2

3 = u2+v3

3 = u3+v2

5 = u3+v4

Observemos que nuevamente resultaron ser 6 ecuaciones que involucran 7 incógnitas (tres de las ui y cuatro de las vj). Ya que hay empate en el número de asignaciones que tiene cada renglón (2 asignaciones en cada renglón), asignemos el valor de cero a la incógnita u1. De esta asignación resulta lo siguiente:

Hemos obtenido el valor de dos incógnitas más, v1, y v2, los cuales nos ayudarán para hallar el valor de las incógnitas restantes:

De esta forma hemos obtenido el valor de todas las incógnitas y procedemos a colocarlos en la tabla como sigue:

Ahora calculemos los valores cij(ui(vj para las variables no básicas y coloquemos estos valores en la esquina inferior izquierda de cada celda:

Para la celda (1,3): 6 ( 0 ( 6 = 0

Para la celda (1,4): 4 ( 0 ( 9 = (5

Para la celda (2,1): 2 ( ((3) ( 3 = 2

Para la celda (2,4): 2 ( ((3) ( 9 = (4

Para la celda (3,1): 4 ( ((4) ( 3 = 5

Para la celda (3,3): 8 ( ((4) ( 6 = 6

Aplicando la prueba de optimalidad para verificar los valores de cij(ui(vj obtenidos, vemos que dos de estos valores ( c14(u1(v4= (5, c24(u2(v4= (4) son negativos, se concluye que la solución básica factible actual no es óptima. Entonces, el método símplex de transporte debe proceder a hacer una iteración para encontrar una mejor solución básica factible. Aplicando el procedimiento descrito anteriormente, se llega al siguiente conjunto de tablas símplex de transporte que se muestra enseguida y que dan solución al problema planteado:

Como en esta última tabla todas las cij(ui(vj son no negativas (¡comprobarlo!), la prueba de optimalidad identifica este conjunto de asignaciones como óptimo, lo cual concluye el algoritmo.

Programación lineal – Problema del transporte

Generalidad: El administrador debe determinar cómo hacer llegar los productos de sus diversos almacenes, plantas de producción o bodegas a sus consumidores o clientes, con el objeto de satisfacer la demanda o pedidos a un costo mínimo de transporte o de envío.

Propósito: El modelo de transporte debe determinar un plan de transporte o envío de una mercancía de varias fuentes a varios destinos, es decir, cantidad de unidades de productos que se enviará de cada fuente a cada destino tal que se minimice el costo de transporte total.

Datos:

1. Nivel de oferta en cada fuente y cantidad de demanda en cada destino.

2. El costo de transporte unitario de la mercancía de cada fuente a cada destino.

Planteamiento del Modelo de Transporte:

En este modelo general implica que la oferta total debe ser cuando menos igual a la demanda total.

Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de Modelo de Transporte Balanceado. Este difiere del modelo general sólo en el hecho de que todas las restricciones son ecuaciones, es decir.

En la realidad se puede encontrar que la oferta no sea igual a la demanda, sin embargo, un modelo de transporte siempre puede balancearse.

Propiedades de los Problemas de Transporte:

1. Propiedad de soluciones Enteras.

Para los problemas de transporte en donde las ofertas Oi y las demandas Dj tienen un valor entero, todas las variables básicas Xij (asignaciones), en toda solución básica inicial factible (incluyendo la óptima), tienen también valores enteros.

2. Propiedad de soluciones Factibles.

Una condición necesaria y suficiente para que un problema de transporte tenga soluciones factibles es que:

Los recursos totales disponibles (ofertas) deben ser iguales a las exigencias totales (demanda), lo que exige entonces que el problema debe estar balanceado.

Si no se cumple, entonces significa que Oi ó Dj están indicando que hay un requerimiento que no es exacto; por esta razón se debe introducir en el modelo un origen o destino "imaginario" o "ficticio".

Interpretación de las fuentes y destinos ficticios:

i. La cantidad de unidades enviadas a un destino desde una fuente ficticia, representará la cantidad faltante en ese destino.

ii. La cantidad de unidades enviadas a un destino ficticio desde una fuente, representará una cantidad excedente en esa fuente.

El costo de transporte unitario asociado es cero (0), puesto que en el caso i. no se están enviando las unidades ya que no existen; en el caso ii. las unidades permanecen en la fuente ya que el destino es ficticio.

TÉCNICA DEL MODELO DE TRANSPORTE

Los pasos básicos de la técnica del transporte son:

I. Determinación de la solución básica inicial.

Por lo tanto, como en el método simplex, una solución factible básica inicial debe incluir m + n – 1 variables básicas.

Para la formulación del problema de transporte se utiliza como base la Tabla de Transporte (fig. 1) en la que se obtiene de manera fácil y directa una solución básica inicial, en donde todas la filas y las columnas son tenidas en cuenta para proporcionar una variable básica (asignación). Cuando se ha realizado una asignación, se debe tachar (no tener en cuenta para asignación) la fila (columna) con la oferta (demanda) satisfecha; lo que indica que las variables restantes de la fila (columna) son iguales a cero (variables no básicas).

Si se satisfacen una fila y una columna al mismo tiempo, sólo una (fila o columna) puede ser tachada; lo que indica la ubicación automática de variables básicas iguales a cero (variable básica degenerada).

Los métodos utilizados para originar una solución básica inicial son los siguientes:

1. MÉTODO DEL COSTO MÍNIMO:

Procedimiento:

Se asigna la mayor cantidad posible de las ofertas o las demandas al menor costo unitario Cij de toda la tabla (Los empates se rompen arbitrariamente), se ajusta la oferta y la demanda de la fila y columna, se tacha la fila o columna satisfecha; se repite el proceso asignando la cantidad más grande posible a la variable con el costo unitario no tachado más pequeño. El procedimiento termina cuando queda exactamente una fila o una columna sin tachar.

2. MÉTODO DE LA ESQUINA NOROESTE.

Procedimiento:

Se comienza con la asignación de la máxima cantidad posible de las ofertas o las demandas a la variable X11 ( la de la esquina Noroeste de la tabla). Después se tacha la fila o columna satisfecha, lo que indica que las variables restantes de la fila (columna) son iguales a cero (variables no básicas). Después de ajustar las cantidades de la oferta y la demanda de todos las filas y columnas no tachadas; se repite el proceso asignando al primer elemento no tachado de la nueva fila o columna. El procedimiento termina cuando queda exactamente una fila o una columna sin tachar.

3. MÉTODO DE APROXIMACIÓN DE VOGEL (MAV).

Procedimiento:

a. Para cada fila y columna se calcula la diferencia aritmética entre el costo mínimo unitario Cij y el que le sigue, de los que quedan en esa fila o columna (cuando hay empates cualquiera).

b. Se identifica la fila o columna con la mayor diferencia, rompiendo empates de forma arbitraria. Luego se asigna la máxima cantidad posible de las ofertas o las demandas a la variable Xij con el costo unitario Cij más bajo de la fila o columna seleccionada. Después se ajustan las cantidades de la oferta y la demanda de todos las filas y columnas, tachando la fila o columna satisfecha. Si se satisfacen una fila y una columna al mismo tiempo, sólo una (fila o columna) puede ser tachada, y a la fila o columna se le asigna una oferta (demanda) igual a cero (lo que indica una variable básica degenerada). Se repite el proceso para las filas o columnas no tachadas.

c. Cuando sólo queda una fila o columna sin tachar y existe una cantidad de oferta o demanda positiva sin asignar, se determina la variable básica por el método del Costo Mínimo.

De ésta manera termina el procedimiento.

NOTA: Cuando se tiene una fila o columna sin tachar y existe una variable básica con asignación igual a cero, no se tiene en cuenta (la fila o columna) para el paso a. Se determina la variable básica con valor cero (0) a través del método del Costo Mínimo.

II. Prueba de Optimidad.

Para la realización de la prueba de OPTIMIDAD se debe determinar la variable no básica que debe entrar a la base; por lo tanto se considera que una solución básica factible es OPTIMA si y sólo sí se cumple:

Cij – Ui – Vj 0 para toda (i,j) tal que Xij sea una variable no básica.

Donde para cada variable básica Xij de la solución actual, los multiplicadores (variables duales asociadas) Ui y Vj deben satisfacer la siguiente ecuación:

Cij = Ui + Vj

ya que toda variable básica tiene coeficiente cero (0) en la función objetivo.

Como se tienen m + n – 1 variables básicas, por lo tanto deben existir m + n – 1 ecuaciones con m+n incógnitas.

Los valores para cada Ui y Vj se pueden determinar a partir de la solución de las m + n – 1 ecuaciones, suponiendo un valor arbitrario para cualquiera de las incógnitas Ui y Vj (por lo general se toma un valor para Ui = 0, en la fila donde se encuentre el mayor número de asignaciones).

Ahora, Cij – Ui – Vj se interpreta como la tasa a la que Z cambiaría si se aumentara el valor de Xij (variable no básica).

Es decir, que si Cij – Ui – Vj 0 determina la variable no básica que debe entrar a la base, ya que disminuye el costo total de Z (costo total de transporte) y se elige el valor negativo más grande para entrar.

Si se incrementa el valor de la variable no básica que entra de cero a un valor positivo, se produce una reacción en cadena de cambios compensatorios en otras variables básicas (asignaciones) con el fin de seguir satisfaciendo las restricciones de oferta y demanda. Se debe encontrar una celda donadora (en la cual se disminuye la cantidad asignada) y otra receptora (se le aumenta la cantidad asignada) formando así la reacción en cadena.

* El propósito de éstas celdas es dar la capacidad de llevar una variable básica (asignación) con valor Positivo a cero (0) y aumentar una variable no básica de valor cero (0) a un valor positivo.

** La variable básica que debe salir de la base será aquella que disminuya su valor a cero (0) más rápido al realizar los cambios en las asignaciones escogidas según la anterior observación.

Entonces, la nueva solución básica factible se identifica con sumar el valor (antes de los cambios) de la variable básica que sale a las asignaciones de cada celda receptora y restar esta misma cantidad a las asignaciones de cada celda donadora.

Teniendo la nueva solución básica factible se realiza de nuevo la prueba de OPTIMIDAD, para lo cual se repite el proceso de determinar los nuevos valores para las incógnitas Ui y Vj

Tal que Cij – Ui – Vj 0 para toda (i,j) con la condición de que Xij sea una variable no básica.

MODELO DE REDES

La importancia del análisis de flujo de redes, en los últimos años ha crecido de una manera progresiva en todos los campos de la planificación; de procesos tareas y recursos tanto económicos como físicos y del tiempo de los proyectos que requieren de este tipo de planificación.

La aplicación de estos tipos de modelos tiene infinidades campos de acción en los diferentes proyectos de inversión tales como:

• En los proyectos de diseños de tuberías de acueducto, gas natural, electrificación, vías, tanto férreas como carrete hables.

• En la determinación del camino más corto entre dos lugares o ciudades de acuerdo a una red existente.

• En la determinación de las capacidades máximas que deben fluir a través de una red, de un recurso especifico.

• La determinación del programa de flujo de costo mínimo de los campos de origen a los centros de distribución de un recurso especial.

Un estudio de esta lista representativa, revela que los problemas de optimización de redes se pueden representar en términos generales a través de los siguientes modelos.

• Modelo del flujo máximo

• Modelo de la ruta más corta.

• Modelo del árbol de extensión mínima.

• Modelo de red de capacidad de costo mínimo.

• Modelo de la ruta critica.

• Modelo de la técnica de evaluación y revisión de proyectos (PERT.

Para la comprensión de los diferentes modelos, se deben tener en cuenta las siguientes definiciones.

DEFINICIÓN DE RED. Es un conjunto de nodos conectados por arcos o ramas, a veces los nodos reciben el nombre de "vértices" y los ramales de "arcos".

CADENA : Una cadena es una secuencia de ramales que conectan dos nodos que al especificarles dirección forman lo que se llama un camino o ruta.

RED SIMÉTRICA: Significa que un vértice "x" esta conectado a uno "y"; entonces "y", esta conectado a "x".

RED ASIMÉTRICA: Significa que un vértice "x" esta conectado a uno "y"; entonces "y", no esta conectado a "x".

CAPACIDAD: Es el flujo que circula por una determinada red y puede ser finita o infinita.

RAMA DIRIGIDA U ORIENTADA: Cuando se permite el paso de un flujo positivo en una determinada dirección y cero en la dirección opuesta.

TRAYECTORIA: Es una secuencia de ramas que conectan dos nodos sin considerar su orientación de las demás ramas individuales.

LASO O CICLO: Se presenta cuando un nodo se conecta consigo mismo.

LASO DIRIJIDO U CIRCUITO: Es un lazo donde todas las ramas tienen las mismas dirección u orientación.

PROBLEMA DEL FLUJO MÁXIMO

Este problema determina el estado factible de flujos a través de la red, que maximiza el flujo total desde el origen hasta el destino en forma tal, que la capacidad de cada rama en esta trayectoria sea mínima.

El flujo máximo a lo largo de esta trayectoria debe ser igual a la capacidad mínima, de todas las ramas que constituyen la trayectoria.

FORMULACION DEL MODELO

Para resolver este tipo de modelos se presentan los siguientes métodos.

• 1. Formulación de un problema de programación lineal.

• 2. Algoritmo del flujo máximo.

El primer método de plantea de la siguiente manera:

Supongamos que existen "n" nodos, donde los nodos 1 y n son el origen y el destino respectivamente como se representa en la red.

El flujo que circula por la red debe cumplir la siguiente restricción:

0 < Xij < Cij

Además debe cumplir la siguiente restricción de conservación de flujo.

Formulación de un problema de programación lineal

• 1. Se define la variable de decisión Xn.

XIJ = La cantidad de flujo que circula de la fuente i al destino j.

• 2. Se define la función objetivo.

• 3. Se define las restricciones.

• 4. restricción de no negatividad

Xij > 0.

Formulación del modelo de flujo máximo.

Para la formulación del modelo del flujo máximo se debe seguir los siguientes pasos.

• 1. Buscar una ruta con capacidad positiva

• 2. Buscar la capacidad mínima en esta ruta y disminuir el flujo por este valor en sentido de izquierda a derecha. Y aumentarlo en sentido contrario.

Ejemplo.

Modelo del algoritmo de la ruta más corta

Para la solución de este problema se tiene el método del algoritmo de DIJKSTRA, el cual se estudiara para resolver dos tipos de problemas de redes las aciclicas y cíclicas.

ALGORITMO ACICLICO

Este algoritmo se basa en el uso de cálculos recursivos que son la base para los cálculos de la programación dinámica. Para un mejor entendimiento del algoritmo desarrollaremos sus pasos de solución a través de un ejemplo.

Luego realizaremos las iteraciones pertinentes:

solución optima

ruta optima = 7-5-2-1

distancia optima = 2+5+6=13

EJERCICIOS: APLICACIÓN FLUJO MÁXIMO

Gloria vera está a cargo de la comisión de Planeación de Desarrollo Urbano, un grupo de estudio ad hoc de interés especial. La responsabilidad actual del grupo consiste en coordinar la construcción de un nuevo sistema de vías subterráneas con el departamento de mantenimiento de caminos. En virtud de que el nuevo sistemas de vías subterráneas se construirá cerca del circuito periférico de la ciudad, el tráfico de que éste se dirige al oriente deberá ser desviado. La desviación planeada es en realidad una red de rutas alternas propuestas por el departamento de mantenimiento de caminos. Los diferentes límites de velocidad y los patrones de tráfico producen distintas capacidades de flujo de los diferentes arcos de la red propuesta como se presenta en la siguiente figura. Determine el flujo máximo de la red y tanto de nodo 1 (empieza la desviación y el nodo 6 termina la desviación), de sus recomendaciones,

Algoritmo del árbol generador mínimo.

La figura que a continuación se detalla muestra la longitud de los enlaces factibles que conectan nueve fuentes de gas natural mar adentro con un punto de reparto en tierra. Como la ubicación de la fuente 1 es la más próxima a la costa, está equipada con la capacidad de bombeo y almacenaje suficiente para bombear la producción de las ocho fuentes o pozos restantes al punto de reparto. Determine la red de tubería que enlaza todas las fuentes al punto de reparto que minimizará la longitud total de los gaseoductos.

Algoritmo de la más corta.

Un camión debe repartir concreto de una planta de mezcla preparada a un sitio de construcción. La red que muestra la figura representa las rutas disponibles entre la planta y el sitio de construcción. Cada ruta está designada con dos piezas de información (d, t), donde d es la longitud de la ruta y t es el tiempo que tarda el camión en atravesar el segmento de camino. La velocidad del camión en cada segmento esta decidida por la condición del camino y también por el número y duración de las paradas del camión. ¿Cuál es la mejor ruta de la planta a la construcción y su tiempo de duración?.

ALGORITMO CICLICO

El anterior algoritmo no funciona si existen en la red lazos dirigidos (circuitos).

El algoritmo cíclico se diferencia del aciclico en el sentido que permite tantas oportunidades como sean necesarias para revaluar un nodo.

Cuando resulta evidente que se ha alcanzado la distancia más corta a un nodo, este se excluye de cualquier consideración posterior. El proceso culmina cuando se ha evaluado el nodo destino.

Para su solución nos valemos del algoritmo de Dijkstra.

Pasos para la solución.

Los nodos en el algoritmo Dijkstra son de dos tipos temporales y permanentes.

Paso 0

Clasifique el nodo de punto de origen con la clasificación permanente {0,-} y determine i=1.

Paso 2

• a. calcule las clasificaciones temporales {ui+dij,i} para todo nodo j, al que se puede llegar desde el nodo i, siempre y cuando "j" no esté clasificado con {ui,k} a través de otro nodo k y si ui+dij

• b.  Si todos los nodos están clasificados permanentes deténgase. De lo contrario seleccione la clasificación {ur,s} con la distancia más corta entre todas las distancias temporales; si hay un empate seleccione arbitrariamente.

PROBLEMAS PARA RESOLVER

PROBLEMA 1: En una fábrica grande de productos de jabón los inspectores de control de calidad muestran diversos productos, en diversas áreas de producción, y después entregan las muestras para su análisis en el laboratorio. El proceso de inspección lento, y los inspectores invierten una cantidad considerable de tiempo transportando las muestras desde las áreas de producción hasta el laboratorio. La compañía está evaluando la instalación de un sistema de conductor mediante tubos neumáticos que se podrían utilizar para transportar las muestras entre las áreas de producción y el laboratorio. La red que aparece en seguida muestra las ubicaciones del laboratorio y las áreas de producción (nodos) en donde se recolectan las muestras. Las ramas son las alternativas que se están considerando para el sistema conductor. ¿Cuál es la longitud total mínima del diseño del sistema de conducción que permitirá que todas las áreas de producción envíen sus muestras al laboratorio?

PROBLEMA 2: Recientemente el estado de Ohio adquirió terreno para un nuevo parque estatal. Las personas que están elaborando los planes para el parque han identificado las ubicaciones ideales para la casa club, las cabañas, los espacios para días de campo, el muelle para embarcaciones y los puntos escénicos de interés. Estos espacios están representados mediante los nodos de la red que aparece en seguida. Las ramas de la red representan las posibles alternativas de caminos en el parque. Si los diseñadores del parque estatal desea minimizar el total de millas de caminos que se deben construir en el parque y al mismo tiempo ofrece acceso a todas las instalaciones (nodos) ¿Qué caminos en alternativas se deben construir?

PROBLEMA 3: El sistema de carreteras norte – sur que pasa por Albany, New York, tiene las capacidades que se muestran en la siguiente grafica.

Significa que por ejemplo de la localidad 5 a la localidad 6 tiene un flujo de 6000 vehículos por hora

¿Considere que el sistema de carreteras puede dar cabida a un flujo de norte – sur de 10000 vehículos por hora?

Investigación de operaciones – simulación

Se considera un modelo como una abstracción que permite reemplazar la parte del universo bajo consideración por un modelo de estructura similar pero más simple.

En un modelo determinístico, los parámetros del modelo son conocidos con certeza. Por ejemplo podría estimarse que un tractor recorre 10 Kms. En una hora. Pero si no estamos ciertos del parámetro, debemos introducir la incertidumbre, y decir, por ejemplo, que la probabilidad de que el tractor recorra diez Kms. En una hora es de 0.75. En este caso se estará hablando de un modelo estocástico.

Los modelos estáticos se definen para un punto fijo en el tiempo y asumen que las condiciones del modelo no cambian para el periodo del tiempo en el cual se quiere obtener la solución al modelo. Los modelos dinámicos se diferencian de los estáticos en que la acción óptima es determinada al examinar varios periodos de tiempo.

Un modelo de simulación es una técnica que cada vez se utiliza más en la IO para abstraer una situación o problema de la vida real en tal forma que dicha situación o problema sea manipulado fuera de su contexto (predicción del futuro, imitar la realidad).

RAZONES PARA ESCOGER LA SIMULACIÓN POR COMPUTADORA

• Hace posible estudiar y experimentar con las interacciones complejas que ocurren en el interior de un sistema dado

• A través de la simulación se pueden estudiar los efectos de ciertos cambios en la operación del sistema.

• La observación detallada del sistema que se está simulando conduce a un mejor entendimiento del mismo y proporciona sugestiones para mejorarlo.

• La simulación puede emplearse para experimentar con situaciones nuevas acerca de las cuales tenemos muy poca o ninguna información con el objeto de estar preparados para alguna eventualidad.

• La simulación puede servir como prueba para ensayar nuevas políticas y reglas de decisión en la operación de un sistema, antes de tomar el riesgo de experimentar con el sistema real

PASOS PARA LA SIMULACIÓN

• 1. Identificación del Problema: recopilación de datos (descripción de variables de entrada, límites o cotas del sistema), componentes e interrelaciones.

• 2. Planteamiento del Modelo: construcción del modelo de simulación y la definición de los procesos estadísticos que se utilizaran para aplicar el modelo. Los resultados obtenidos se consideran observaciones muéstrales.

• 3. Validación: se debe asegurar que las entradas al modelo de simulación sean adecuadas y que el modelo responda a esas entradas de manera similar al problema real.

• 4. Proceso de Simulación: este proceso implica la generación de entradas al sistema, ejecución del modelo y obtención de datos simulados. Cada corrida de la simulación es análoga a una sola observación (muestra). En términos estadísticos, la media de una muestra sirve para hacer inferencias con respecto a la media de la población, sólo si emplea un tamaño de muestra adecuado.

LA SIMULACIÓN Y LA IO

La simulación se diferencia significativamente de otras técnicas de modelado de la IO, en las cuales el esfuerzo se realiza en la formulación y desarrollo de modelos matemáticos y la solución analítica matemática de los modelos.

La simulación no hace énfasis en ningún algoritmo particular. Es un proceso descriptivo.

Generalmente el proceso de simulación involucra la recolección de datos que describen las entradas, los factores operativos, la interrelación de los factores (variables) y otros componentes del problema objeto de estudio.

La salida de un modelo de simulación se presenta en forma e indicadores de ejecución. Utilizando el modelo se pueden explorar las características del problema.

MUESTREO MONTECARLO

Se refiere a un proceso que se utiliza en forma aleatoria para elegir valores muestrales a partir de una distribución probabilística. Después, esos valores muestrales se utilizan como entradas para el modelo de simulación. Sin embargo para aceptar que el proceso es correcto desde el punto de vista estadístico, debemos asegurarnos que los números aleatorios tengan en realidad una distribución aleatoria uniforme entre 0 y 1.

NÚMEROS ALEATORIOS

Los números aleatorios uniformes se utilizan para introducir el comportamiento estocástico en el sistema bajo estudio. Son un ingrediente básico en la simulación de casi todos los sistemas discretos. Algunas de sus propiedades son:

Uniformidad: cada número aleatorio es un valor muestral extraído de una distribución uniforme continúa entre cero y uno. El valor esperado de cada número aleatorio esta dado por:

La probabilidad de observar un valor, en un intervalo en particular es independiente de los valores previamente extraídos.

Los números generados en un computador no son totalmente aleatorios, por que se obtienen de fórmulas preestablecidas que cumplen con una serie de pruebas estadísticas. Por esta razón de les ha llamado seudoaleatorios. La mayoría de los métodos para generar números aleatorios son iterativos, donde un número seudoaleatorio se genera a partir de su antecesor.

El periodo del método es el número de generaciones que se debe esperar hasta repetir la secuencia. Es deseable que este periodo sea lo mayor posible. Para garantizar la independencia entre números aleatorios, debe asegurarse que no exista correlación alguna entre los números generados. Además su distribución ha de ser estable, es decir esta distribución no debe cambiar con el tiempo.

Casi todos los algoritmos para generar secuencias de números aleatorios son dados a través de la siguiente fórmula recursiva.

Donde el número inicial se conoce como semilla y debe ser definido con anterioridad. La escogencia de la función, en la ecuación anterior debe hacerse de tal manera que los criterios matemáticos, antes enunciados, sean satisfechos.

Método del cuadrado medio (propuesto en 1946 por J. von Newman)

• 1. Seleccione el número aleatorio (arbitrario cualquiera) de n dígitos (semilla del generador de números aleatorios)

• 2. Eleve al cuadrado el número del paso 1 y agregue ceros al lado derecho, si se necesitan, para producir un número de 2n dígitos

• 3. El nuevo número aleatorio se determina seleccionando los n dígitos de la mitad del número obtenido en el paso 2

• 4. Repita los pasos 2 y 3 para obtener números aleatorios adicionales.

Ejemplo: semilla = 2173; 1er número aleatorio = 2192; 2do número aleatorio = 486; 4to número aleatorio = 6196

Como se requieren números aleatorios entre 0 y 1, basta con colocar un punto decimal a la izquierda, los cuatro números serán: 0.2173, 0.2192; 0.486; 0.3619. Al parecer el método del cuadrado medio tiene un periodo muy corto.

Bibliografía

• 1. INVESTIGACIÓN DE OPERACIONES EN LA CIENCIA ADMINISTRATIVA

Eppen, G. D / Gould F. J. / Schmidt, C.P. / Moore, Jeffrey H, / Weathrford, Larry R.

Prentice – Hall 5ª Edición México 1999 – 1987

• 2. INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES

Hiller S. Frederick / Lieberman J. Gerald – Mc Graw Hill Séptima Edición

• 3. ANÁLISIS CUANTITATIVOS PARA LOS NEGOCIOS

Bonini Ch. E./ Hausman W. H./ Bierman H. – Mc Graw Hill Novena Edición 2000

• 4. ADMINISTRACIÓN DE PRODUCCIÓN Y OPERACIONES

Chase – Aquilano – Jacobs – Irwin Mc Graw Hill – Octava Edición

• 5. INVESTIGACIÓN DE OPERACIONES

Taha Hamdy A. Prentice Hall Omega México 1992 – 1998

• 6. INVESTIGACIÓN DE OPERACIONES

Kamlesh Mathur – Daniel Solow – Prentice Hall

• 7. INVESTIGACIÓN DE OPERACIONES

Bronson, Richard – Mc Graw Hill (Colección Schaum) México 1982

• 8. INVESTIGACIÓN DE OPERACIONES

Herbert Moskowitz / Gordon C. Wright – Prentice / Hall Carvajal Calí 1982

• 9. MÉTODOS Y MODELOS DE INVESTIGACIÓN DE OPERACIONES

Prawda Witenberg, Juan (Tomos I y II) – Límusa México 1982

• 10. INTRODUCCIÓN A LOS MODELOS CUANTITATIVOS PARA ADMINISTRACIÓN

Anderson David R. / Sweeney Dennis J. / William Thomas A.

Grupo Editorial Iberoamérica México 1993

• 11. MODELOS CUANTITATIVOS PARA ADMINISTRACIÓN

Davis Roscoe K. / Mckeown Patrick G. – Grupo editorial Iberoamérica México 1986

• 12. MÉTODOS CUANTITATIVOS EN ADMINISTRACIÓN

Ullamn John E. – Mc Graw Hill (Colección Schaum) México 1982

• 13. PROGRAMACIÓN LINEAL Y FLUJO EN REDES

Bazaraa, Mokhtar y Jarvis, Jhon – Límusa México 1989

Autor:

Ing. +Lic. Yunior Andrés Castillo S.

Santiago de los Caballeros,

República Dominicana

2014.