Problema de transporte Solución de soporte [parte 2]

Teorema 38.1 Una condición necesaria y suficiente para la solvencia del problema del transporte

Para que la tarea de transporte de la programación lineal tenga una solución, es necesario y suficiente que el suministro total de proveedores sea igual a las demandas totales de los consumidores, es decir La tarea debe ser con el equilibrio correcto.

Teorema 38.2. La propiedad del sistema de restricción del problema del transporte

El rango de las condiciones vector-sistema del problema del transporte es N = m + n-1 (m - proveedores, n-consumidores)

La solución básica del problema del transporte

La solución de soporte del problema de transporte es cualquier solución admisible para la cual los vectores de condición correspondientes a coordenadas positivas sean linealmente independientes.

En vista del hecho de que el rango del sistema de vectores de condición del problema de transporte es m + n - 1, la solución de soporte no puede tener coordenadas distintas de cero más que m + n-1. El número de coordenadas distintas de cero de una solución de soporte no degenerada es m + n-1, y para una solución de soporte degenerada menor que m + n-1

Ciclo

Un ciclo es una secuencia de celdas en la tabla del problema de transporte (i 1 , j 1 ), (i 1 , j 2 ), (i 2 , j 2 ), ..., (i k , j 1 ), en la cual dos y solo dos las celdas vecinas están ubicadas en una fila o columna, con la primera y la última celda también en una fila o columna.

El ciclo se representa como una tabla de tareas de transporte en forma de una polilínea cerrada. En un ciclo, cualquier celda es angular, en la cual el enlace de la polilínea gira 90 grados. Los ciclos más simples se muestran en la Figura 38.1

Teorema 38.3

Una solución admisible del problema de transporte X = (x ij ) es una solución de soporte si y solo si no se puede formar un ciclo a partir de las celdas ocupadas de la tabla.

Método de Strikeout

El método de eliminación permite verificar si la solución dada del problema de transporte es la de soporte.

Supongamos que se escribe en la tabla una solución admisible del problema de transporte que tiene m + n-1 coordenadas distintas de cero. Para que esta solución sea un soporte, los vectores de condición correspondientes a coordenadas positivas, así como los ceros básicos, deben ser linealmente independientes. Para hacer esto, las tablas ocupadas por la decisión de la celda deben organizarse de modo que sea imposible formar un ciclo a partir de ellas.

Una fila o columna de una tabla con una celda ocupada no puede entrar en ningún ciclo, ya que el ciclo tiene dos y solo dos celdas en cada fila o columna. Por lo tanto, para eliminar primero todas las filas de la tabla que contiene una celda ocupada o todas las columnas que contienen una celda ocupada, vuelva a las columnas (filas) y continúe la eliminación.

Si, como resultado de la eliminación, se eliminan todas las filas de la columna, significa que la parte que forma el ciclo no puede seleccionarse de las celdas ocupadas de la tabla, y el sistema de vectores de condición correspondientes es linealmente independiente y la solución es la de soporte.

Si, después de la eliminación, una parte de las células permanece, estas células forman un ciclo, el sistema de las correspondientes condiciones vectoriales es linealmente dependiente, y la solución no es de soporte.

Ejemplos de "tachado" (referencia) y "no tachado" (soluciones no compatibles):

Lógica de negociación :

  1. Eliminar todas las columnas en las que solo una celda ocupada (5 0 0), (0 9 0)
  2. Elimina todas las líneas en las que solo una celda ocupada (0 15), (2 0)
  3. Repita el ciclo (7) (1)

Métodos para construir una solución de soporte inicial

Método del ángulo del noroeste

Hay una serie de métodos para construir una solución de soporte inicial, la más simple de las cuales es el método del ángulo noroeste.
En este método, las existencias de la siguiente por el número del proveedor se utilizan para garantizar las solicitudes de la siguiente por el número de consumidores hasta que se agoten por completo, después de lo cual se utilizan las existencias del próximo proveedor.

El llenado de la tabla de tareas de transporte comienza desde la esquina superior izquierda, por eso se llama al método de la esquina noroeste.

El método consiste en una serie de pasos del mismo tipo, en cada uno de los cuales, basándose en las existencias del próximo proveedor y las solicitudes del próximo consumidor, solo se llena una celda y, en consecuencia, se excluye a un proveedor o consumidor.

Ejemplo 38.1

Cree una solución de soporte utilizando el método de la esquina noroeste.

Solución:

1 . Distribuya las existencias del primer proveedor.
Si las existencias del primer proveedor son mayores que las solicitudes del primer consumidor, anotamos el monto de la solicitud del primer consumidor en la caja (1,1) y pasamos al segundo consumidor. Si las existencias del primer proveedor son inferiores a las solicitudes del primer consumidor, anotamos el monto de las existencias del primer proveedor en la jaula (1,1), excluimos al primer proveedor de la consideración y pasamos al segundo proveedor.

Ejemplo : dado que sus stocks a 1 = 100 es menor que las solicitudes del primer consumidor b 1 = 100, entonces en la celda (1,1) registramos el transporte x 11 = 100 y excluimos de la consideración del proveedor.
Determine las solicitudes insatisfechas restantes del primer consumidor b 1 = 150-100 = 50.

150 200 100 100
100 100 100 fue -100 necesario = 0 izquierda
250
200

150 must -100 was = 50 left
Se mantuvo satisfecho
solicitudes de 50 artículos

2. Distribuimos las reservas del segundo proveedor.
Dado que sus reservas a 2 = 250 son más que las del primer cliente b 1 = 50 insatisfecho con las solicitudes del primer cliente, registramos el transporte x 21 = 50 en la celda (2,1) y excluimos al primer cliente de la consideración.
Determine las reservas restantes del segundo proveedor a 2 = a 2 - b 1 = 250-50 = 200. Como las existencias restantes del segundo proveedor son iguales a las solicitudes del segundo consumidor, escribimos x 22 = 200 en la jaula (2,2) y excluimos, a nuestro criterio, el segundo proveedor o el segundo consumidor. En nuestro ejemplo, excluimos al segundo proveedor.
Calcule las solicitudes no satisfechas restantes del segundo consumidor b 2 = b 2 -a 2 = 200-200 = 0.

150 200 100 100
100 100
250 50
200

250-50 = 200 200-200 = 0
200
150-100-50 = 0

3. Distribuimos los suministros del tercer proveedor.
¡Importante! En el paso anterior, tuvimos la opción de excluir al proveedor o al consumidor. Como excluimos al proveedor, las solicitudes del segundo consumidor aún permanecen (aunque son iguales a cero).
Debemos escribir las solicitudes restantes igual a cero en la celda (3.2)
Esto se debe al hecho de que si la siguiente celda de la tabla (i, j) necesita ser transportada, y el proveedor con el número i o el consumidor con el número j tiene cero existencias o solicitudes, entonces el carro es igual a cero (el cero base) en la celda, y Después de esto, el proveedor relevante o el consumidor quedan excluidos de la consideración.
Por lo tanto, solo se ingresan ceros básicos en la tabla, las celdas restantes con transporte cero permanecen vacías.

Para evitar errores después de construir la solución de soporte inicial, es necesario verificar que el número de celdas ocupadas es m + n-1 (el cero base también se considera una celda ocupada), y los vectores de condición correspondientes a estas celdas son linealmente independientes.

Como en el paso anterior excluimos de la consideración del segundo proveedor, escribimos x 32 = 0 en la celda (3,2) y excluimos al segundo consumidor.

Las existencias del tercer proveedor no cambiaron. En el clack (3.3), escriba x 33 = 100 y excluya al tercer consumidor. En la celda (3,4) escribimos x 34 = 100. En vista del hecho de que nuestra tarea tiene el equilibrio correcto, las existencias de todos los proveedores están agotadas y las solicitudes de todos los consumidores se satisfacen completa y simultáneamente.

Solución base
150 200 100 100
100 100
250 50 200
200 0 100 100

4. Verificamos la corrección de la construcción de la solución de soporte.
El número de celdas ocupadas debe ser igual a N = m (proveedores) + m (consumidores) - 1 = 3 + 4 - 1 = 6.
Al aplicar el método de eliminación, estamos convencidos de que la solución encontrada está "tachada" (el asterisco indica una base cero).

Consecuentemente, los vectores de condición correspondientes a las celdas ocupadas son linealmente independientes y la solución construida es de hecho una solución de soporte.

El método del costo mínimo

El método de costo mínimo es simple y permite construir una solución de soporte lo suficientemente cercana a la óptima, ya que utiliza la matriz de costo del problema de transporte C = (c ij ).

Al igual que el método de la esquina noroccidental, consta de una serie de pasos del mismo tipo, en cada uno de los cuales solo se rellena un cuadrado de la tabla, correspondiente al valor mínimo:

y solo una fila (vendedor) o una columna (consumidor) queda excluida de la consideración. La siguiente celda correspondiente a , complete de acuerdo con las mismas reglas que en el método de la esquina noroeste. El proveedor queda excluido de la consideración si su carga de existencias se utiliza en su totalidad. El consumidor queda excluido de la consideración si sus solicitudes están completamente satisfechas. En cada paso, se excluye un proveedor o un consumidor. Al mismo tiempo, si el proveedor aún no está excluido, pero sus existencias son cero, en la etapa en que el proveedor debe entregar las mercancías, el cero base se ingresa en la celda de la tabla correspondiente y solo entonces se excluye al proveedor. Del mismo modo con el consumidor.

Ejemplo 38.2

Utilizando el método de costo mínimo, construya una solución de soporte inicial para el problema de transporte.

Solución:

1. Escribimos por separado la matriz de valores para que sea más conveniente elegir los valores mínimos.

2. Entre los elementos de la matriz de valores, elija el costo más bajo C 11 = 1, márquelo con un círculo. Este valor tiene lugar cuando las mercancías se transportan del primer proveedor al primer consumidor. En la celda apropiada registramos el volumen máximo posible de transporte:
x 11 = min {a 1 ; b 1 } = min {60; 40} = 40 i.e. mínimo entre las existencias del primer proveedor y las solicitudes del primer consumidor.

2.1. Reducimos las existencias del primer proveedor en 40.
2.2. Excluimos de la consideración del primer consumidor, ya que sus solicitudes están completamente satisfechas. En la matriz C, tachamos la primera columna.

3. En la parte restante de la matriz C, el costo mínimo es el costo C 14 = 2. El máximo transporte posible que se puede hacer desde el primer proveedor hasta el cuarto consumidor es x 14 = min {a 1 '; b 4 } = min {20; 60} = 20 , donde a 1 con el primo es el inventario restante del primer proveedor.
3.1. Las existencias del primer proveedor están agotadas, por lo que lo excluimos de la consideración.
3.2. Reducimos las solicitudes del cuarto consumidor por 20.

4. En el resto de la matriz C, el costo mínimo es C 24 = C 32 = 3. Llenamos una de las dos celdas de la tabla (2,4) o (3,2). Supongamos que escribimos x 24 = min {a 2 ; b 4 } = min {80; 40} = 40 .
4.1. Las solicitudes del 4º consumidor están satisfechas. Lo excluimos de la consideración eliminando la cuarta columna en la matriz C.
4.2. Reducimos las reservas del segundo proveedor 80-40 = 40.

5. En el resto de la matriz C, el costo mínimo es C 32 = 3. Escribimos el transporte x 32 = min {a 3 ; b 2 } = min {100; 60} = 60 .
5.1. Excluimos de la consideración del segundo consumidor. De la matriz C excluimos la segunda columna.
5.2. Reduciremos las reservas del tercer proveedor 100-60 = 40

6. En el resto de la matriz C, el costo mínimo es C 33 = 6. Escribimos el carro x 33 = min {a 3 '; b 3 } = min {40; 80} = 40
6.1. Excluimos de la consideración del tercer proveedor, y de la matriz C, la tercera fila.
6.2. Determine las solicitudes restantes del tercer consumidor 80-40 = 40.

7. En la matriz C solo había un elemento C 23 = 8. Grabamos en una celda de la tabla (2,3) el transporte X 23 = 40.

8. Verificamos la corrección de la construcción de la solución de soporte.
El número de celdas ocupadas de la tabla es N = m + n - 1 = 3 + 4 -1.
Usando el método de eliminación, verificamos la independencia lineal de las condiciones del vector correspondientes a las coordenadas positivas de la solución. El procedimiento para eliminar se muestra en la matriz X:

Conclusión: La decisión por el método del costo mínimo (Tabla 38.3) está "tachada" y, por lo tanto, es la referencia.

You May Also Like

New Articles

Reader's Choice

© 2023 pomilm.com