Método de TransporteEl problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.

Representación de una red de transporte

Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. Adicionalmente, se tienen varios supuestos:

1. Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.

2. Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas. 

3. Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos. 

4. Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros. 

Debido a la particularidad del modelo de transporte la forma tabular Símplex adquiere una estructura que facilita el proceso de asignación a las variables básicas, tal se muestra a continuación:

Forma Tabular Símplex Transporte

En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). En las columnas se ubican los distintos destinos indicando en el último renglón los totales demandados. En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.

Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:1. Regla de la esquina noroeste.

2. Método de la ruta preferente.

3. Método de aproximación de Vogel 

Antes de explicar el procedimiento para cada uno de estos criterios de asignación para encontrar la solución inicial BF, se debe conocer el número de variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo anterior 3 + 2 - 1 = 4 variables básicas. Regla de la esquina noroeste: la primera elección X11, es decir, se inicia la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al reglo debajo hasta realizar todas las asignaciones.

Método de la ruta preferente: se fundamenta en la asignación a partir del costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la asignación de recursos máxima posible y luego se identifica el siguiente costo menor realizando el mismo procedimiento hasta realizar todas las asignaciones. 

Método de asignación de Vogel:  para cada reglón y columna, se calcula su diferencia, que se define como la diferencia aritmética entre el costo  unitario más pequeño y el costo menor que le sigue en ese renglón o columna. En el renglón o columna con la mayor diferencia, se le asigna al menor costo unitario. Los empates se pueden romper de manera arbitraria. 

De estos 3 modelos para encontrar la solución inicial BF, el método de Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los costos de distribución de forma más eficaz, ya que la diferencia representa el mínimo costo adicional que se incurre por no hacer una asignación en la celda que tiene el menor costo ya sea columna o renglón.

Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.

Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero. 

En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. Paso 1: la variable de entrada se determina a partir de la relación  Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de

menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a  la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras. 

Para los fines de ejemplo, se selecciona el problema 8.2-8 ubicado en la página 325 del libro de texto. La Cost-Less Corp., surte sus cuatro (4) tiendas desde sus cuatro (4) plantas y

desea minimizar los costos de distribución. A continuación se muestra la tabla con las informaciones de los costos de distribución:

s 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 recursos4.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.

Leer más: http://www.monografias.com/trabajos102/aplicacion-formulacion-modelos-investigacion-operaciones/aplicacion-formulacion-modelos-investigacion-operaciones2.shtml#ixzz3delr9w4L

METODO ASIGNACION

Un problema de asignación es un problema de transporte balanceado, en el cual todas las

ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problema

de asignación m x m mediante el método Húngaro.

Un problema de asignación es un problema de transporte balanceado en el que todas las

ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de

asignación de cada punto de oferta a cada punto de demanda. La matriz de costos del

problema de asignación se llama: matriz de costos.

Como todas las ofertas y demandas para el problema de asignación son números enteros,

todas las variables en la solución óptima deben ser valores enteros.

1.- ESCOGER EL NUMERO MENOR DE LA COLUMNA Y SE LE RESTA A TODA LA COLUMNA

2.- SE COLOCA UNA LINEA DONDE HAYA

QUEDADO CERO EN FILAS

3.-EL MENOR DE CADA FILA SE RESTA ENTRE

CADA FILA SE ASIGANAN NUMEROS NUEVOS

4.-ENCERRAR CADA CERO DE FILA Y COLUMNA

5.-SE MARCAN LAS FILAS CON CEROS

6.-MARCA COLUMNA QUE TENGA CUADRO TACHE Y FILA QUE NO TENGA CERO

SE CLASIFICA:

A) CRUZADOS POR 2 LINEA (2, 0,3)

B)CRUZADOS POR 1 LINEA(2,6,7,2,5,15,1,11,15)

C)NADA LOS CRUZA(4,13,3,7,5,15,9,2,7,15)

7.- SE ELIGE EL MENOR DE (C) Y SE SUMA A (A)

8.-LOS VAN IGUAL

9.-SE LES RESTA EL MENOR DE (C) A ELLOS MISMOS (C)

10.- EL PROBLEMA TERMINA CUANDO TENEMOS EL MISMO NUMERO CEROS QUE DE FILAS Y

COLUMNAS.

Z=4+1+5+3+4=17 Hrs.

TRANSPORTE Y ASIGNACIÓN

5.1  Definición del problema de transporte

Método de TransporteEl método de transporte analiza los costos de transporte tanto de la materia prima como de los productos terminados. El método consiste en reducir al mínimo posible los costos destinados a satisfacer los requerimientos totales de demanda y abastecimiento de materiales.

5.2 Método de Aproximación de Vogel (MAV)Este método es un método de transporte en el cual todos los datos se llevan a una matriz oferta-demanda u origen-destino, se escogerá aquel sitio que cause los mínimos costos totales.

Oferta /Origen

Demanda/Destino

W X Y Z

C11 C12 C13 C14 n1

X11 X12 X13 X14

C21 C22 C23 C24 n2

X21 X22 X23 X24

C31 C32 C33 C34 n3

X31 X32 X33 X34

m1 m2 m3 m4

m1+m2 + m3 + m4  = n1 + n2 + n3

La oferta en todos los orígenes debe igualar a la demanda de todos los destinos. Esta restricción se impone porque es fundamental para desarrollar la técnica de transporte. Sin embargo, cualquier sistema real puede balancearse artificialmente convirtiéndolo en un a un problema con igual oferta y demanda, mediante la añadidura de orígenes o destinos ficticios. Si la demanda excede a la oferta se aumenta un destino ficticio que suministrará la cantidad faltante. Si existe un exceso de oferta se utiliza un destino ficticio para absorber la cantidad excedente. Los costos de transporte por unidad desde el origen ficticio a todos los destinos son ceros ya que esto es equivalente a no transportar desde el origen ficticio. En forma semejante los costos de transporte por unidad desde todas las fuentes a los destinos ficticios es cero. Físicamente las cantidades enviadas desde un origen ficticio pueden interpretarse como escasez de la demanda, mientras que los asignados a un destino ficticio pueden interpretarse como capacidades no utilizadas en el origen.

El MAV es un método heurístico y la mayor parte del tiempo produce soluciones óptimas o muy cercanas a la óptima.

Pasos del MAV1.    Evalúe una penalización para cada renglón (columna) restando el elemento de

costo más pequeño en el renglón (columna) del siguiente elemento de costo más pequeño en el mismo renglón (columna).

2.    Identifique el renglón o columna con la penalización mayor, rompiendo arbitrariamente los empates. Asigne tanto como sea posible a la variable con el costo mínimo en el renglón o columna, si se satisfacen simultáneamente, únicamente uno de ellos se tacha y al renglón (columna) restante se le asigna una

oferta (demanda) cero. Cualquier renglón o columna con oferta o demanda cero no deberá ser utilizado al calcular penalizaciones futuras.

3.    Si exactamente un renglón o columna esta sin tachar pare o deténgase. Si únicamente un renglón (columna) con oferta (demanda) positiva permanece sin estar tachada, determine las variables básicas por el método de costo mínimo (asignar tanto como sea posible a la variable con el costo unitario más pequeño). En cualquier otro caso calcule las penalizaciones para los renglones y columnas no tachadas y vaya al paso dos.Nota: el número de variables básicas tiene que ser m + n – 1

5.4 Procedimiento de optimización

Método del Banquillo (Stepping Stones)Este método sirve para probar si ya se alcanzó la optimización en el método de transporte. Una vez que se tiene una buena solución al método de transporte usando el MAV, es necesario probar si esta es óptima, cambiando unas unidades a otras rutas, para evaluar cada cuadro abierto (sin número asignado). Siga estos pasos:

1. Determine una trayectoria cerrada. Empezando con el cuadro abierto a ser evaluado y saltando a otros cuadros cerrados (con asignaciones), hasta regresar al cuadro original abierto. Cada elemento de la esquina de la trayectoria debe ser un cuadro cerrado (con asignaciones).

2. Empezando con el cuadro abierto a ser evaluado, asigne un signo más (+) alterne signos menos (-) y más (+). A las esquinas (cuadros) de la trayectoria. Es indiferente si el circuito se recorre en el sentido de las manecillas del reloj o en sentido contrario.

3. Sume los costos por unidad en los cuadros con el signo más (+), reste los costos por unidad en los cuadros con el signo menos (-). Si el resultado es negativo, significa que se puede obtener una disminución de los costos con una nueva asignación.

4. Si el resultado del punto 3 fue negativo, entonces la variable que sale es aquel cuadro cerrado que tiene el valor más pequeño ya que será la primera que llegue al valor cero y cualquier disminución adicional causará se negatividad. El cuadro deberá tener el signo menos (-).

5. Cuando la suma de todos los cuadros abiertos sea positiva, entonces se ha llegado a la solución óptima.

Nota: recuerde que el número de variables básicas (cuadros cerrados) debe ser m+n-1.

Definición del problema de asignación

Considere  la situación de asignar m trabajos o trabajadores a n máquinas. Un trabajo i (i=1, 2, 3…, m) cuando se asigna a la máquina j (j=1, 2, 3,…, n) incurre en un costo Cij. El objetivo es asignar los trabajos a las máquinas (un trabajo por máquina) con el costo mínimo total. Este caso es conocido con el nombre de asignación.

La formulación de este problema puede considerarse como un caso especial del método de transporte. Aquí los trabajos representan “orígenes” y las máquinas representan “destinos”. La oferta disponible en cada fuente es 1. De igual manera la demanda requerida en cada destino es 1. El costo de “transportar” (asignar) el trabajo i a la máquina j es C ij. Si un trabajo no puede asignarse a una cierta máquina, el Cij correspondiente se toma igual a M, es decir, un costo muy alto.

MáquinaTrabaj

o

1 2 ……………… n1 C11 C12 ……………… C1n 12 C21 C22 ………………. C2n 1...

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.m Cm1 Cm2 ………………. Cmn 1

1 1 ………………. 1

Nota: las columnas o renglones ficticios tienen costos M.Antes de que el modelo pueda resolverse, es necesario balancear primero el problema, añadiendo trabajos ficticios o máquinas ficticias, dependiendo si m<n o m>n. Por consiguiente, se supondrá que m=n. Para resolver el problema de asignación se siguen estos pasos:

Pasos en  el Método de Asignación1.    Encuadre el elemento mínimo en cada renglón de la matriz. Construya una nueva

matriz, restando de cada costo, el costo mínimo de su renglón. Para esta nueva

matriz encuentre el costo mínimo en cada columna. Construya una nueva matriz, llamada la matriz de costo reducida, restando de cada costo el costo mínimo en su columna.

2.    Dibuje el mínimo número de líneas, horizontales y verticales que son necesarias para cubrir todos los ceros en la matriz de costo reducida. Si m líneas son requeridas para cubrir todos los ceros, entonces se tiene una solución óptima disponible dentro de los ceros cubiertos en la matriz. Si existen menos de m líneas que cubren todos los ceros entonces proceda al paso 3.

3.    Encuentre el elemento más pequeño diferente a cero (llamado valor k). En la matriz de costo reducida que no está cubierto por las líneas del paso 2. Reste k de cada elemento no cubierto de la matriz de costos reducida y sume k a cada elemento cubierto por 2 líneas de la matriz de costo reducida. Regrese al paso 2.