Descripción del método de rentas diferenciales. Restricciones adicionales al problema del transporte. Método de anualidad diferencial

Si, al determinar el plan óptimo para un problema de transporte utilizando el método potencial, primero se encontró algún plan básico y luego se mejoró consistentemente, entonces al encontrar una solución a un problema de transporte utilizando el método de rentas diferenciales, primero la mejor manera distribuir parte de la carga entre destinos (la llamada distribución condicionalmente óptima) y en iteraciones posteriores reducir gradualmente la cantidad total de suministros no distribuidos. La opción de distribución de carga inicial se determina de la siguiente manera. En cada una de las columnas de la tabla de datos de la tarea de transporte se encuentra la tarifa mínima. Los números encontrados se encierran en círculos y se completan las celdas que contienen los números indicados. En ellos están escritos los máximos números posibles. Como resultado, se obtiene una cierta distribución de los suministros de carga a los destinos. Esta distribución generalmente no satisface las restricciones del problema de transporte original. Por lo tanto, los próximos pasos deberían ser reducir gradualmente los suministros de carga no asignados para que coste total el tráfico siguió siendo mínimo. Para ello, primero determine las filas redundantes e insuficientes.

Se consideran insuficientes las líneas que corresponden a proveedores cuyo inventario está totalmente asignado y cuya demanda de los destinos asociados a los envíos planificados de esos clientes no se satisface. Estas líneas a veces también se denominan líneas negativas. Las líneas que no están completamente agotadas se consideran excedentes. A veces también se les llama positivos.

Una vez determinadas las filas excedentes e insuficientes, para cada una de las columnas se encuentran las diferencias entre el número en el círculo y la tarifa más cercana escrita en la fila excedente. Si el número en el círculo está en la línea positiva, entonces la diferencia no está determinada. Entre los números obtenidos, encuentra el más pequeño. Este número se llama anualidad intermedia. . Después de determinar la anualidad intermedia, pasan a una nueva tabla. Este cuadro se obtiene del cuadro anterior sumando la renta intermedia a las tarifas correspondientes en filas negativas. Los elementos restantes siguen siendo los mismos. En este caso, todas las celdas de la nueva tabla se consideran libres. Después de construir una nueva tabla, sus celdas comienzan a completarse. Ahora el número de celdas llenas es una más que en la etapa anterior. Esta celda adicional está en la columna en la que se registró la anualidad intermedia. Todas las demás celdas están ubicadas una en cada una de las columnas y contienen los números más pequeños para una columna determinada, encerrados en círculos. Entre círculos hay dos números idénticos en la columna en la que se registró la anualidad intermedia en la tabla anterior.

Dado que en la nueva tabla el número de celdas a llenar es mayor que el número de columnas, al completar las celdas se debe utilizar una regla especial, que es la siguiente. Seleccione una determinada columna (fila) en la que haya una celda con un círculo colocado en ella. Esta celda se completa y esta columna (fila) se excluye de la consideración. Después de esto, tome una determinada fila (columna), en la que hay una celda con un círculo colocado en ella. Esta celda se completa y se excluye de la consideración. esta línea(columna). Siguiendo así, después de un número finito de pasos, se van rellenando todas las celdas en las que están colocados los círculos con los números encerrados. Si además es posible distribuir toda la carga disponible en los puntos de salida entre los puntos de destino, entonces obtenemos plan optimo tarea de transporte. Si no se obtiene el plan óptimo, se pasa a una nueva tabla. Para ello, busque líneas sobrantes e insuficientes, alquiler intermedio y construya sobre esta base. nueva mesa. En este caso, pueden surgir algunas dificultades a la hora de determinar el signo de una cadena cuando su resto no asignado es cero. En este caso, la fila se considera positiva siempre que la segunda celda llena, ubicada en la columna asociada a esta fila por otra celda llena, esté ubicada en la fila positiva.

Después de un número finito de iteraciones descritas anteriormente, el resto no asignado se vuelve cero. Como resultado, se obtiene un plan óptimo para una tarea de transporte determinada.

El método descrito anteriormente para resolver el problema del transporte tiene una forma más sencilla. circuito lógico cálculos que el método potencial discutido anteriormente. Por ello, en la mayoría de los casos, para encontrar soluciones a problemas concretos de transporte utilizando un ordenador, se utiliza el método de los alquileres diferenciales.

Ejemplo (4):

Para el problema de transporte, cuyos datos iniciales se dan en la Tabla 11, encuentre el plan óptimo utilizando el método de rentas diferenciales.

Solución. Pasemos del Cuadro 11 al Cuadro 12, agregando una columna adicional para indicar exceso y deficiencia por fila y una fila para registrar las diferencias correspondientes.

Tabla 10.

Tabla 11.

En cada una de las columnas del Cuadro 12 encontramos los aranceles mínimos y los encierramos en un círculo. Complete las celdas que contienen los números indicados. Para hacer esto, escriba el número máximo permitido en cada celda. Por ejemplo, en la celda ubicada en la intersección de la fila y la columna, escribimos el número 120. No se puede colocar un número mayor en esta celda, ya que en este caso se excederían las necesidades del destino.

Como resultado de completar las celdas mencionadas anteriormente, se obtiene el llamado plan condicionalmente óptimo, según el cual se satisfacen plenamente las necesidades de los destinos y parcialmente las necesidades del destino. . Al mismo tiempo, las reservas del punto de salida se distribuyeron en su totalidad, parcialmente, los suministros del punto de salida, y las existencias del punto de salida permanecieron completamente sin distribuir.

Después de obtener un plan condicionalmente óptimo, determinamos las líneas redundantes e insuficientes. Aquí la línea es insuficiente. , ya que las reservas del punto de partida se utilizan en su totalidad y las necesidades del destino se satisfacen parcialmente. La cantidad de deficiencia es de 80 unidades.

Instrumentos de cuerda Y son redundantes porque las existencias en los orígenes Y no completamente distribuido. En este caso, la cantidad de exceso de línea es igual a 60 unidades, y la línea es igual a unidades. El monto total del exceso coincide con el monto total del déficit, igual a.

Después de determinar las filas excedentes e insuficientes para cada una de las columnas, encontramos las diferencias entre los aranceles mínimos escritos en las filas excedentes y los aranceles en las celdas llenas. EN en este caso estas diferencias son respectivamente iguales a 5, 4, 2, 1 (Tabla 11). La diferencia no está definida para la columna porque el número encerrado en un círculo en esa columna está en la fila positiva. En una columna, el número en el círculo es igual, y en las filas redundantes de las celdas de una columna determinada, el número más pequeño es el número. Por lo tanto, la diferencia para esta columna es igual a. De manera similar encontramos las diferencias para otras columnas: para; Para; Para. .

Elegimos la menor de las diferencias encontradas, que es la renta intermedia. En este caso, la renta intermedia es igual y está en la columna . Habiendo encontrado la renta intermedia pasamos a la Tabla 11.

En esta tabla, en las filas y (que son redundantes) reescribimos las tarifas correspondientes de la fila Tabla 10. Los elementos de la línea (que resultó insuficiente) se obtienen sumando a las tarifas correspondientes ubicadas en la tabla de líneas. 10, anualidad intermedia, es decir.

En mesa 11, el número de celdas llenas aumentó en uno. Esto se debe a que el número de aranceles mínimos en cada una de las columnas de este cuadro ha aumentado en uno, es decir, la columna ahora tiene dos elementos mínimos. Encerramos estos números en círculos; las celdas en las que se encuentran deben llenarse. También es necesario completar las celdas que contienen las tarifas más bajas para otras columnas. Estas son las celdas de la tabla. 11 en el que se encierran en círculos las tarifas correspondientes.

Tabla 11.

Una vez identificadas las celdas especificadas, establecemos la secuencia para llenarlas. Para ello, buscamos columnas (filas) en las que solo queda una celda para llenar. Habiendo identificado y completado una determinada celda, excluimos de la consideración la columna (fila) correspondiente y pasamos a completar la siguiente celda. En este caso, llenamos las celdas en la siguiente secuencia. Primero llenamos las celdas. ,,,, ya que son las únicas celdas para completar las columnas. Después de llenar las celdas especificadas, complete la celda, ya que es la única que completa la fila. . Habiendo completado esta celda (Tabla 2.16), excluimos la línea de la consideración. . Entonces solo queda una celda en la columna para llenar. esto es una jaula , que completamos. Después de llenar las celdas, configuramos líneas redundantes e insuficientes (Tabla 11). Como se puede observar en el Cuadro 11, aún existe un saldo no distribuido. En consecuencia, se ha obtenido un plan condicionalmente óptimo para el problema y debemos pasar a una nueva tabla. Para ello, para cada una de las columnas encontramos las diferencias entre el número escrito en el círculo de esta columna y el número más pequeño con relación a ella, ubicado en las filas redundantes (Tabla 11). Entre estas diferencias, la más pequeña es . Este es un alquiler intermedio. Pasemos a una nueva tabla (Tabla 12).

Si, al determinar el plan óptimo para un problema de transporte utilizando el método potencial, primero se encontró algún plan básico y luego se mejoró constantemente, entonces al encontrar una solución a un problema de transporte utilizando el método anualidades diferenciales En primer lugar, parte de la carga se distribuye entre destinos de la mejor manera posible (el llamado distribución condicionalmente óptima) y en iteraciones posteriores reducir gradualmente la cantidad total de suministros no asignados. La opción de distribución de carga inicial se determina de la siguiente manera. En cada una de las columnas de la tabla de datos de la tarea de transporte se encuentra la tarifa mínima. Los números encontrados se encierran en círculos y se completan las celdas que contienen los números indicados. En ellos están escritos los máximos números posibles. Como resultado, se obtiene una cierta distribución de los suministros de carga a los destinos. Esta es la distribución en caso general no satisface las restricciones del problema de transporte original. Por lo tanto, los próximos pasos deberían ser reducir gradualmente los suministros de carga no asignados para que el costo total del transporte siga siendo mínimo. Para ello, primero determine las filas redundantes e insuficientes.

Se consideran insuficientes las líneas que corresponden a proveedores cuyo inventario está totalmente asignado y cuya demanda de los destinos asociados a los envíos planificados de esos clientes no se satisface. Estas líneas a veces también se denominan líneas negativas. Las líneas que no están completamente agotadas se consideran excedentes. A veces también se les llama positivos.

Después de determinar las filas excedentes e insuficientes, para cada una de las columnas se encuentran las diferencias entre el número en el círculo y la tarifa más cercana escrita en la fila excedente. Si el número en el círculo está en la línea positiva, entonces la diferencia no está determinada. Entre los números obtenidos, encuentra el más pequeño. este numero se llama alquiler intermedio. Después de determinar la anualidad intermedia, pasan a una nueva tabla. Este cuadro se obtiene del cuadro anterior sumando la renta intermedia a las tarifas correspondientes en filas negativas. Los elementos restantes siguen siendo los mismos. En este caso, todas las celdas de la nueva tabla se consideran libres. Después de construir una nueva tabla, sus celdas comienzan a completarse. Ahora el número de celdas llenas es una más que en la etapa anterior. Esta celda adicional está en la columna en la que se registró la anualidad intermedia. Todas las demás celdas están ubicadas una en cada una de las columnas y contienen los números más pequeños para una columna determinada, encerrados en círculos. Entre círculos hay dos números idénticos en la columna en la que se registró la anualidad intermedia en la tabla anterior.

Dado que en la nueva tabla el número de celdas a llenar es mayor que el número de columnas, al completar las celdas se debe utilizar una regla especial, que es la siguiente. Seleccione una determinada columna (fila) en la que haya una celda con un círculo colocado en ella. Esta celda se completa y esta columna (fila) se excluye de la consideración. Después de esto, tome una determinada fila (columna), en la que hay una celda con un círculo colocado en ella. Esta celda se completa y esta fila (columna) se excluye de la consideración. Siguiendo así, después de un número finito de pasos, se van rellenando todas las celdas en las que están colocados los círculos con los números encerrados. Si además es posible distribuir toda la carga disponible en los puntos de salida entre los puntos de destino, entonces se obtiene un plan óptimo para la tarea de transporte. Si no se obtiene el plan óptimo, se pasa a una nueva tabla. Para hacer esto, busque filas redundantes e insuficientes, alquiler intermedio y cree una nueva tabla basada en esto. En este caso, pueden surgir algunas dificultades a la hora de determinar el signo de una cadena cuando su resto no asignado es cero. En este caso, la fila se considera positiva siempre que la segunda celda llena, ubicada en la columna asociada a esta fila por otra celda llena, esté ubicada en la fila positiva.

Después de un número finito de iteraciones descritas anteriormente, el resto no asignado se vuelve cero. Como resultado, se obtiene un plan óptimo para una tarea de transporte determinada.

El método para resolver el problema de transporte descrito anteriormente tiene un esquema de cálculo lógico más simple que el método potencial discutido anteriormente. Por ello, en la mayoría de los casos, para encontrar soluciones a problemas concretos de transporte utilizando un ordenador, se utiliza el método de los alquileres diferenciales.

5.6 Determinación del plan óptimo para problemas de transporte que tengan algunas complicaciones en su formulación.

Al encontrar una solución a una serie de problemas de transporte específicos, a menudo es necesario tener en cuenta restricciones adicionales que no se encontraron anteriormente al considerar opciones simples estas tareas. Detengámonos con más detalle en algunas posibles complicaciones en la formulación de problemas de transporte.

1. Para algunos condiciones reales transporte de mercancías desde un punto de partida específico , a tu destino , no se puede implementar. Para determinar planes óptimos para tales problemas, se supone que la tarifa por transportar una unidad de carga de un punto a otro , es arbitrariamente grande METRO, y bajo esta condición, se encuentra una solución a un nuevo problema de transporte utilizando métodos conocidos. Con este supuesto, la posibilidad de transportar carga de un punto a otro queda excluida según el plan óptimo de la tarea de transporte. . Este enfoque para encontrar una solución a un problema de transporte se llama prohibición de transporte o bloqueando la celda correspondiente en la tabla de datos de la tarea.

2. En determinadas tareas de transporte, una condición adicional es garantizar el transporte por las rutas adecuadas. una cierta cantidad carga Supongamos, por ejemplo, que desde el punto de salida hasta el punto de destino sea necesario transferir unidades de carga. Luego, el número especificado se escribe en la celda de la tabla de datos de la tarea de transporte ubicada en la intersección de la fila y la columna, y en el futuro esta celda se considera gratuita con una tarifa de transporte arbitrariamente grande. METRO. Para el nuevo problema de transporte obtenido de esta manera, se encuentra un plan óptimo, que determina el plan óptimo. problema original.

3. En ocasiones es necesario encontrar una solución a un problema de transporte en el que se debe entregar al menos una determinada cantidad de carga desde el punto de salida hasta el destino. Para determinar el plan óptimo para tal tarea, se considera que las reservas del artículo y las necesidades del artículo son menores que las reales por unidades. Después de esto, se encuentra el plan óptimo para el nuevo problema de transporte, a partir del cual se determina la solución al problema original.

4. En algunos problemas de transporte, es necesario encontrar el plan de transporte óptimo, siempre que no se transporten más de unidades de carga desde el punto de salida al destino, es decir,

El problema formulado se puede resolver de la siguiente manera. En la tabla de datos de la tarea inicial, para cada restricción (1), se proporciona una columna adicional, es decir, se ingresa un destino adicional. EN esta columna Anote las mismas tarifas que en la columna, a excepción de la tarifa ubicada en la octava fila. En la columna adicional de esta línea, el arancel se considera igual a algunos arbitrariamente un número grande. En este caso, las necesidades del punto se consideran iguales y las necesidades del destino recién introducido se consideran iguales. La solución al problema de transporte resultante se puede encontrar mediante el método de los potenciales y, de este modo, se determinará el plan óptimo o se establecerá la irresolubilidad del problema original. Tenga en cuenta que el problema de transporte original sólo se puede resolver si existe al menos un plan de referencia para ello.

El problema anterior se puede resolver de esta manera. Teniendo en cuenta la restricción (1), se construye un plano de referencia utilizando la regla del elemento mínimo. Además, si el valor registrado en Este paso en la celda correspondiente del número está determinado solo por la restricción (1), posteriormente solo se excluye de la consideración la celda llena. En otros casos de estas consideraciones excluyen una fila o una columna (una u otra).

Si como resultado de la elaboración de un plan de suministro se distribuyen todas las existencias disponibles en los puntos de salida y se satisfacen las necesidades en los puntos de destino, se obtiene un plan básico para la tarea de transporte.

Si en alguna fila (y por tanto en una columna) hay un saldo no asignado igual a , luego se introducen un destino adicional y un punto de partida adicional con necesidades y suministros iguales a . En una celda ubicada en la intersección de una columna. punto adicional destino y la línea del punto de salida adicional, la tarifa se considera igual a cero. En todas las demás celdas de una fila y columna determinadas, se supone que los aranceles son iguales a algún número arbitrariamente grande. METRO. El problema de transporte resultante se resuelve mediante el método potencial. Después de un número finito de pasos, se establece que el problema original no tiene plan de referencia, o encontrar su plan óptimo. Donde – plan óptimo para el problema original si