El plano de referencia es el método de la esquina noroeste. Problema de transporte: método de la esquina noroeste. Solución de referencia al problema del transporte.
Cree un modelo económico y matemático y resuelva el problema utilizando el complemento "Búsqueda de soluciones".
Solución:
Modelo económico y matemático:
Función objetivo:
la función objetivo tenderá al mínimo ya que nos esforzamos por minimizar nuestros costos de realización del trabajo.
Restricciones:
x ij – igual a 1 indica que el i-ésimo empleado debe ser asignado para realizar el j-ésimo trabajo.
Se ha elaborado un modelo económico y matemático del problema. Resolvamos este problema usando el complemento de Excel "Buscar una solución".
La Figura 1 muestra el progreso de la utilidad "Buscar solución".
Figura 1 – Flujo de trabajo de la utilidad Buscar una solución
La Figura 2 muestra el resultado de resolver el problema.
Figura 2 – Resultado de la resolución del problema
Conclusión: De la Figura 2 se deduce que para que el costo total sea mínimo, es necesario asignar al empleado B4, A2 - B3, A3 - B5, A4 - B1, A5 - B2 para realizar el trabajo A1, mientras que los costos totales serán Mínimo y asciende a 25 unidades.
Problema 2 Problema de transporte
Información previa problema de transporte presentado en la Tabla 2.
Tabla 2 - Datos iniciales
| B1 | B2 | B3 | B4 | Reservas | |
| A1 | |||||
| A2 | |||||
| A3 | |||||
| Necesidades |
Definir:
1. plano aproximado, esquema de transporte, así como su costo utilizando el método noreste esquina occidental;
2. plano aproximado, esquema de transporte, así como su costo utilizando el método del elemento mínimo;
3. plan óptimo, esquema de transporte, así como su costo utilizando el complemento "Búsqueda de soluciones".
Método esquina noroeste
Comprobemos qué se necesita y condición suficiente Solubilidad del problema.
Como puede ver, la demanda total de carga en los destinos es menor que las reservas de carga en las bases. Por tanto, el modelo del problema de transporte original es abierto. Para obtener un modelo cerrado, introducimos una demanda adicional (ficticia) igual a 3 (120-117). Suponemos que las tarifas por transportar una unidad de carga desde la base a todos los almacenes son cero.
Ingresemos los datos iniciales en la tabla de distribución 3.
Tabla 3 – Tabla de distribución
| B1 | B2 | B3 | B4 | B5 | Reservas | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Necesidades |
El primer plano de referencia comienza a rellenarse desde la esquina superior izquierda (Tabla 4).
Tabla 4 - Plan de referencia 1
| B1 | B2 | B3 | B4 | B5 | Reservas | ||||
| A1 | tu 1 =0 | ||||||||
| A2 | tu 2 =-2 | ||||||||
| A3 | tu 3 =-4 | ||||||||
| v 1 = 3 | v 2 = 6 | v 3 = 10 | v 4 = 5 | v 5 = 4 | |||||
| Necesidades |
Como resultado se obtuvo el primer plan de referencia, el cual es aceptable, ya que toda la carga fue retirada de las bases, las necesidades de los almacenes están satisfechas y el plan corresponde al sistema de restricciones de la tarea de transporte.
Contamos el número de celdas ocupadas de la tabla, hay 7, pero debería ser m + n - 1 = 7. Por lo tanto, el plan de soporte no es degenerado.
Significado función objetivo para este plan de referencia es igual a:
F(x) = 3*30 + 6*10 + 4*17 + 8*23 + 6*7 + 1*30 + 0*3 = 474
tu 1 + v 2 = 6; 0 + v2 = 6; v2 = 6
u 2 + v 2 = 4; 6 + tu 2 = 4; tu 2 = -2
u 2 + v 3 = 8; -2 + v 3 = 8; v3 = 10
u 3 + v 3 = 6; 10 + u 3 = 6; tu 3 = -4
u 3 + v 4 = 1; -4 + v 4 = 1; v4 = 5
u 3 + v 5 = 0; -4 + v 5 = 0; v5 = 4
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
(1;3): 0 + 10 > 5; ∆ 13 = 0 + 10 - 5 = 5
(1;4): 0 + 5 > 2; ∆ 14 = 0 + 5 - 2 = 3
(1;5): 0 + 4 > 0; ∆ 15 = 0 + 4 - 0 = 4
(2;5): -2 + 4 > 0; ∆ 25 = -2 + 4 - 0 = 2
máx(5,3,4,2) = 5
Elegir puntuación máxima celda libre (1;3): 5
Para hacer esto, coloque un signo “+” en la celda de perspectiva (1;3) y alterne los signos “-”, “+”, “-” en los vértices restantes del polígono (Tabla 5).
Tabla 5 – Ciclo 1
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| - | + | ||||||||
| A2 | tu 2 =-2 | ||||||||
| + | - | ||||||||
| A3 | tu 3 =-4 | ||||||||
| v 1 = 3 | v 2 = 6 | v 3 = 10 | v 4 = 5 | v 5 = 4 |
El ciclo se muestra en la tabla (1.3 → 1.2 → 2.2 → 2.3).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (1, 2) = 10. Sume 10 a los volúmenes de carga en las celdas positivas y reste 10 de X ij en las celdas negativas. Como resultado obtenemos un nuevo plan de referencia (Tabla 6).
Tabla 6 - Plan de referencia 2
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| A2 | tu 2 = 3 | ||||||||
| A3 | tu 3 = 1 | ||||||||
| v 1 = 3 | v 2 = 1 | v 3 = 5 | v 4 = 0 | v 5 =-1 |
Comprobemos la optimización del plan de referencia. Encontremos los potenciales preliminares u i, v j. según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3
u 2 + v 3 = 8; 5 + tu 2 = 8; tu 2 = 3
u 2 + v 2 = 4; 3 + v 2 = 4; v2 = 1
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
(2;1): 3 + 3 > 3; ∆ 21 = 3 + 3 - 3 = 3
(2;5): 3 -1 > 0; ∆ 25 = 3 -1 - 0 = 2
Seleccione la puntuación máxima para una celda libre (2;1): 3
Para hacer esto, coloque un signo “+” en la celda de perspectiva (2;1) y alterne los signos “-”, “+”, “-” en los vértices restantes del polígono (Tabla 7).
Tabla 7 – Ciclo 2
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| - | + | ||||||||
| A2 | tu 2 = 3 | ||||||||
| + | - | ||||||||
| A3 | tu 3 = 1 | ||||||||
| v 1 = 3 | v 2 = 1 | v 3 = 5 | v 4 = 0 | v 5 =-1 |
El ciclo se muestra en la tabla (2.1 → 2.3 → 1.3 → 1.1).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (2, 3) = 13. Sume 13 a los volúmenes de carga en las celdas positivas y reste 13 de X ij en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia 3 (Tabla 8).
Tabla 8 - Plan de referencia 3
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| A2 | tu 2 =0 | ||||||||
| A3 | tu 3 = 1 | ||||||||
| v 1 = 3 | v 2 = 4 | v 3 = 5 | v 4 = 0 | v 5 =-1 |
Comprobemos la optimización del plan de referencia. Encontremos los potenciales preliminares u i, v j. según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3
tu 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5
u 3 + v 3 = 6; 5 + tu 3 = 6; tu 3 = 1
u 3 + v 4 = 1; 1 + v 4 = 1; v4 = 0
u 3 + v 5 = 0; 1 + v 5 = 0; v5 = -1
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
(3;2): 1 + 4 > 3; ∆ 32 = 1 + 4 - 3 = 2
Elegimos la puntuación máxima para una celda libre (3;2): 3
Para hacer esto, coloque un signo “+” en la celda de perspectiva (3;2) y alterne los signos “-”, “+”, “-” en los vértices restantes del polígono (Tabla 9).
Tabla 9 – Ciclo 3
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| - | + | ||||||||
| A2 | tu 2 =0 | ||||||||
| + | - | ||||||||
| A3 | tu 3 = 1 | ||||||||
| + | - | ||||||||
| v 1 = 3 | v 2 = 4 | v 3 = 5 | v 4 = 0 | v 5 =-1 |
El ciclo 3 se muestra en la tabla (3.2 → 3.3 → 1.3 → 1.1 → 2.1 → 2.2).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (3, 3) = 7. Sumamos 7 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 7 de X ij que se encuentran en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia 4.
Tabla 10 - Plan de referencia 4
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| A2 | tu 2 =0 | ||||||||
| A3 | tu 3 =-1 | ||||||||
| v 1 = 3 | v 2 = 4 | v 3 = 5 | v 4 = 2 | v 5 = 1 |
Comprobemos la optimización del plan de referencia. Encontremos los potenciales preliminares u i, v j. según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3
u 2 + v 1 = 3; 3 + tu 2 = 3; tu 2 = 0
u 2 + v 2 = 4; 0 + v2 = 4; v2 = 4
u 3 + v 5 = 0; -1 + v 5 = 0; v5 = 1
tu 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
(1;5): 0 + 1 > 0; ∆ 15 = 0 + 1 - 0 = 1
(2;5): 0 + 1 > 0; ∆ 25 = 0 + 1 - 0 = 1
Seleccione la puntuación máxima para una celda libre (1;5): 0
Para hacer esto, coloque un signo “+” en la celda de perspectiva (1;5) y alterne los signos “-”, “+”, “-” en los vértices restantes del polígono (Tabla 11).
Tabla 11 – Ciclo 4
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| - | + | ||||||||
| A2 | tu 2 =0 | ||||||||
| + | - | ||||||||
| A3 | tu 3 =-1 | ||||||||
| + | - | ||||||||
| v 1 = 3 | v 2 = 4 | v 3 = 5 | v 4 = 2 | v 5 = 1 |
El ciclo 4 se muestra en la tabla (1,5 → 1,1 → 2,1 → 2,2 → 3,2 → 3,5).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (3, 5) = 3. Sumamos 3 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 3 a X ij que se encuentra en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia 5 (Tabla 12).
Tabla 12 – Plan de referencia 5
| B1 | B2 | B3 | B4 | B5 | |||||
| A1 | tu 1 =0 | ||||||||
| A2 | tu 2 =0 | ||||||||
| - | |||||||||
| A3 | tu 3 =-1 | ||||||||
| v 1 = 3 | v 2 = 4 | v 3 = 5 | v 4 = 2 | v 5 = 0 |
Comprobemos la optimización del plan de referencia. Encontremos los potenciales preliminares u i, v j. según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3
u 2 + v 1 = 3; 3 + tu 2 = 3; tu 2 = 0
u 2 + v 2 = 4; 0 + v2 = 4; v2 = 4
u 3 + v 2 = 3; 4 + tu 3 = 3; tu 3 = -1
u 3 + v 4 = 1; -1 + v 4 = 1; v4 = 2
tu 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5
tu 1 + v 5 = 0; 0 + v 5 = 0; v5 = 0
El plan de soporte 5 es óptimo, ya que todas las estimaciones de celdas libres satisfacen la condición u i + v j ≤ c ij.
Costos mínimos será:
F(x) = 3*7 + 5*30 + 0*3 + 3*23 + 4*17 + 3*10 + 1*30 = 368
Esquema de transporte:
desde el 1er almacén es necesario enviar la carga al 1er consumidor por la cantidad de 7 unidades, al 3er consumidor por la cantidad de 30 unidades;
desde el segundo almacén es necesario enviar la carga al primer consumidor - 23 unidades, al segundo consumidor - 17 unidades;
desde el tercer almacén es necesario enviar la carga al segundo consumidor - 10 unidades, al cuarto consumidor - 30 unidades.
En el primer almacén quedaron 3 unidades de carga sin reclamar.
plan optimo es degenerada, ya que la variable básica x 15 =0.
©2015-2019 sitio
Todos los derechos pertenecen a sus autores. Este sitio no reclama la autoría, pero proporciona uso gratuito.
Fecha de creación de la página: 2017-08-26
Declaración del problema
Cuatro empresas de la región económica utilizan materias primas homogéneas para la producción de productos cuya demanda es b j (cu).
El volumen de suministro de materias primas de tres proveedores es, respectivamente, a i (cu). Se conocen los precios de venta de los proveedores p i (unidades/cu) y las tarifas de transporte con ij (unidades/us) de cada proveedor A i a cada empresa B j. Es necesario encontrar planes para el transporte de materias primas a las empresas que minimicen los costos en efectivo:
1) únicamente para la compra de materias primas;
2) únicamente para el transporte de materias primas;
3) para la compra y transporte de materias primas.
Encuentre estimaciones del enfoque logístico para resolver el problema de compra de materias primas por parte de una empresa.
Datos iniciales
Opción 4.
Método del ángulo noroeste
Hay tres proveedores A i y cuatro consumidores B j. Las ofertas de los proveedores (a i), las demandas de los consumidores (b j), así como los costos de transportar una unidad de carga (ci ij) desde el punto A i al punto B j se especifican en la matriz C (unidades/unidad).
Encuentre la primera solución de soporte al problema de transporte utilizando el método de la esquina noroeste. Solución: Verifique la condición de equilibrio (cerrado) del problema.
Porque luego introducimos una columna adicional (consumidor) con la necesidad b 5 = 70 - 48 = 22 (unidades).
Creemos una mesa de transporte:
Tabla 2
|
Proveedores |
Consumidores |
|||||
|
B 1 |
B 3 |
B 5 |
||||
|
A 1 |
||||||
|
A 2 |
||||||
|
A 3 |
||||||
Empezamos a rellenar la tabla desde la celda superior izquierda: anota todo lo que puedas posible significado x 11 =mín(30;12)=12. Se satisface la demanda del consumidor B 1 y se excluye de la consideración la primera columna. El inventario del primer proveedor es 30-12 = 18.
En la tabla encontramos la nueva esquina noroeste: celda A 1 B 2 y escribimos x 12 =min(18;10)=10.
Al proveedor A 1 le quedan 8 en stock.
Encuentra la siguiente esquina noroeste x 13 =min(8;15)=8. Por lo tanto, el stock del primer proveedor está agotado: excluimos de la consideración la primera línea.
En la tabla restante encontramos “esquina noroeste”, etc. Como resultado, obtenemos la distribución de suministros (ver Tabla 2). En cada paso (excepto el último), se eliminó de la consideración una fila o una columna, y en el último, tanto una fila como una columna.
Por lo tanto, el número de celdas llenas (pasos) es uno menos que la suma de los números de filas y columnas, es decir el plan no es degenerado.
encontraremos solución óptima problema de transporte eligiendo el primer plano de referencia utilizando el método del elemento mínimo.
Solución: Tarifa mínima c 33 =2; x 33 =mín(22;15) =15.
La tercera columna está tachada (puesta a cero). La tarifa mínima para las celdas restantes con 22 =4, x 22 =min(18;10) =10. Tacha la segunda columna.
Para el resto de celdas, la tarifa mínima es de 34 =4, x 34 =min(22 - 15; 11) =7. Tacha la tercera línea.
Para el resto de celdas, la tarifa mínima es 24 =5, x 24 =min(18-10;11-7) = 4.
Tacha la cuarta columna. De las celdas restantes de la tabla principal, la tarifa mínima es de 11 = 6, x 11 = min (30; 12) = 12. Tacha la primera columna.
De manera similar, complete la columna ficticia x 15 = 18, x 25 = 4. Obtenemos el primer plano de referencia. El número de celdas cargadas es 3+5-1=7, es decir correr condición necesaria no degeneración del plan.
Tabla 3
|
Proveedores |
Consumidores |
||||||
|
B 1 |
B 3 |
B 5 |
|||||
|
A 1 |
|||||||
|
A 2 |
|||||||
|
A 3 |
|||||||
|
V j |
El costo del transporte bajo este plan será:
L 1 =6*12 + 0*18 + 4*10 + 5*4 + 0*4 + 2*15 + 4*7 = 190 (un.). El número de celdas cargadas es m+n-1=3 + 5- 1 = 7, es decir se cumple la condición necesaria para la no degeneración del plan. Consecuentemente, a partir de las ecuaciones compiladas para las celdas cargadas, determinamos los potenciales de proveedores y consumidores:
U3 =0; V 1 = C 31 - U 3 = 5 - 0 = 5; U2 = C21 - V1 = 11 - 5 = 6;
V2 = C22 - U2 = 4-6 = -2; V3 = C23 - U2 = 8 - 6 = 2;
U3 = C33 - V3 = 2 - 2 = 0; V4 = C34 - U3 = 4 - 0 = 4;
V5 = C25 - U2 = 0 - 6 = -6
Hagamos las diferencias para celdas libres:
12 = U 1 + V 2 - C 12 = 0 - 2 - 8 = -10
13 = U 1 + V 3 - C 13 = 0 + 2 - 13 = -11
14 = U 1 + V 4 - C 14 = 0 + 4 - 15 = -11
21 = U 2 + V 1 - C 21 = 6 + 5 - 11 = 0
23 = U 2 + V 3 - C 23 = 6 + 2 - 8 = 0
31 = U 3 + V 1 - C 31 = 0 + 5 - 5 = 0
32 = U 3 + V 2 - C 32 = 0 - 2 - 9 = -11
35 = U 3 + V 5 - C 35 = 0 - 6 - 0 = -6
Dadas todas las diferencias, el plan resultante es óptimo.
El costo mínimo será de 190 (CU)
Etapa I. Búsqueda del primer plan de referencia..
1. Utilizando el método de la esquina noroeste, construiremos el primer plano de referencia del problema de transporte.
El plan comienza a completarse desde la esquina superior izquierda.
El elemento requerido es igual a c 11 =7. Para este elemento, los suministros son 20, los requisitos son 25. Como el mínimo es 20, lo restamos.
x 11 = mín(20,25) = 20.
El elemento requerido es igual a c 22 =7. Para este elemento, los inventarios son 55, las necesidades son 40. Como el mínimo es 40, lo restamos.
x 22 = mín(55,40) = 40.
El elemento requerido es igual a c 23 =0. Para este elemento, los suministros son 15, los requisitos son 50. Como el mínimo es 15, lo restamos.
x 23 = mín(15,50) = 15.
El elemento requerido es igual a c 33 =10. Para este elemento, los suministros son 45, las necesidades son 35. Como el mínimo es 35, lo restamos.
x 33 = mín(45,35) = 35.
El elemento requerido es igual a c 34 =2. Para este elemento, los suministros son 10, los requisitos son 30. Como el mínimo es 10, lo restamos.
x 34 = mín(10,30) = 10.
El elemento requerido es igual a c 44 =7. Para este elemento, los inventarios son 70, las necesidades son 20. Como el mínimo es 20, lo restamos.
x 44 = mín(70,20) = 20.
El elemento requerido es igual a c 45 =8. Para este elemento, los inventarios son 50, las necesidades son 45. Como el mínimo es 45, lo restamos.
x 45 = mín(50,45) = 45.
|
Necesidades |
Como resultado se obtuvo el primer plan de referencia, el cual es aceptable, ya que toda la carga fue retirada de las bases, las necesidades de los almacenes están satisfechas y el plan corresponde al sistema de restricciones de la tarea de transporte.
2. Contemos el número de celdas ocupadas de la tabla, hay 9, pero debe ser m + n - 1 = 9. Por lo tanto, el plan de soporte no es degenerado.
El valor de la función objetivo para este plan de referencia es:
F(x) = 7*20 + 5*5 + 7*40 + 0*15 + 10*35 + 2*10 + 7*20 + 8*45 + 0*5 = 1315
Etapa II. Mejora del plan de referencia..
potenciales preliminares
u 4 + v 4 = 7; -6 + u 4 = 7; tu 4 = 13
u 4 + v 5 = 8; 13 + v 5 = 8; v5 = -5
u 4 + v 6 = 0; 13 + v 6 = 0; v 6 = -13
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
- (3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
- (3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
- (4;1): 13 + 7 > 3; ? 41 = 13 + 7 - 3 = 17
- (4;2): 13 + 9 > 4; ? 42 = 13 + 9 - 4 = 18
- (4;3): 13 + 2 > 2; ? 43 = 13 + 2 - 2 = 13
máx(6,14,13,17,18,13) = 18
Elegimos la puntuación máxima para una celda libre (4;2): 4
Para hacer esto, coloque un signo “+” en la celda de perspectiva (4;2) y alterne los signos “-”, “+”, “-” en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (4,2 > 4,4 > 3,4 > 3,3 > 2,3 > 2,2).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (4, 4) = 20. Sume 20 a los volúmenes de carga en las celdas positivas y reste 20 de X ij en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7
u 2 + v 1 = 5; 7 + tu 2 = 5; tu 2 = -2
tu 2 + v 2 = 7; -2 + v 2 = 7; v2 = 9
u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2
u 3 + v 3 = 10; 2 + tu 3 = 10; tu 3 = 8
u 3 + v 4 = 2; 8 + v 4 = 2; v4 = -6
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
- (1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
- (1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
- (2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
- (2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3
- (3;1): 8 + 7 > 1; ? 31 = 8 + 7 - 1 = 14
- (3;2): 8 + 9 > 4; ? 32 = 8 + 9 - 4 = 13
- (3;5): 8 + 13 > 6; ? 35 = 8 + 13 - 6 = 15
- (3;6): 8 + 5 > 0; ? 36 = 8 + 5 - 0 = 13
máx(6,7,5,8,3,14,13,15,13) = 15
Seleccione la puntuación máxima para una celda libre (3;5): 6
Para hacer esto, coloque un signo "+" en la celda de perspectiva (3;5) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (3,5 > 3,3 > 2,3 > 2,2 > 4,2 > 4,5).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (3, 3) = 15. Sumamos 15 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 15 de X ij que se encuentran en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7
u 2 + v 1 = 5; 7 + tu 2 = 5; tu 2 = -2
tu 2 + v 2 = 7; -2 + v 2 = 7; v2 = 9
u 4 + v 2 = 4; 9 + tu 4 = 4; tu 4 = -5
u 4 + v 5 = 8; -5 + v 5 = 8; v5 = 13
u 3 + v 5 = 6; 13 + u 3 = 6; tu 3 = -7
u 3 + v 4 = 2; -7 + v 4 = 2; v4 = 9
u 4 + v 6 = 0; -5 + v 6 = 0; v 6 = 5
u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (1;2): 0 + 9 > 3; ? 12 = 0 + 9 - 3 = 6
- (1;4): 0 + 9 > 8; ? 14 = 0 + 9 - 8 = 1
- (1;5): 0 + 13 > 6; ? 15 = 0 + 13 - 6 = 7
- (1;6): 0 + 5 > 0; ? 16 = 0 + 5 - 0 = 5
- (2;4): -2 + 9 > 2; ? 24 = -2 + 9 - 2 = 5
- (2;5): -2 + 13 > 3; ? 25 = -2 + 13 - 3 = 8
- (2;6): -2 + 5 > 0; ? 26 = -2 + 5 - 0 = 3
máx(6,1,7,5,5,8,3) = 8
Seleccione la puntuación máxima para una celda libre (2;5): 3
Para hacer esto, coloque un signo "+" en la celda de perspectiva (2;5) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (2,5 > 2,2 > 4,2 > 4,5).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (2, 2) = 5. Sumamos 5 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 5 a X ij que se encuentra en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7
u 2 + v 1 = 5; 7 + tu 2 = 5; tu 2 = -2
u 2 + v 3 = 0; -2 + v 3 = 0; v 3 = 2
tu 2 + v 5 = 3; -2 + v 5 = 3; v5 = 5
u 3 + v 5 = 6; 5 + tu 3 = 6; tu 3 = 1
u 3 + v 4 = 2; 1 + v 4 = 2; v4 = 1
u 4 + v 5 = 8; 5 + u 4 = 8; tu 4 = 3
u 4 + v 2 = 4; 3 + v 2 = 4; v2 = 1
u 4 + v 6 = 0; 3 + v 6 = 0; v 6 = -3
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (3;1): 1 + 7 > 1; ? 31 = 1 + 7 - 1 = 7
- (4;1): 3 + 7 > 3; ? 41 = 3 + 7 - 3 = 7
- (4;3): 3 + 2 > 2; ? 43 = 3 + 2 - 2 = 3
Elegimos la puntuación máxima para una celda libre (3;1): 1
Para hacer esto, coloque un signo "+" en la celda de perspectiva (3;1) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (3.1 > 3.5 > 2.5 > 2.1).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (2, 1) = 5. Sumamos 5 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 5 a X ij que se encuentran en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7
u 3 + v 5 = 6; -6 + v 5 = 6; v5 = 12
tu 2 + v 5 = 3; 12 + u 2 = 3; tu 2 = -9
u 2 + v 3 = 0; -9 + v 3 = 0; v3 = 9
u 4 + v 5 = 8; 12 + u 4 = 8; tu 4 = -4
u 4 + v 2 = 4; -4 + v2 = 4; v2 = 8
u 4 + v 6 = 0; -4 + v 6 = 0; v 6 = 4
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (1;2): 0 + 8 > 3; ? 12 = 0 + 8 - 3 = 5
- (1;3): 0 + 9 > 4; ? 13 = 0 + 9 - 4 = 5
- (1;5): 0 + 12 > 6; ? 15 = 0 + 12 - 6 = 6
- (1;6): 0 + 4 > 0; ? 16 = 0 + 4 - 0 = 4
- (4;3): -4 + 9 > 2; ? 43 = -4 + 9 - 2 = 3
máx(5,5,6,4,3) = 6
Seleccione la puntuación máxima para una celda libre (1;5): 6
Para hacer esto, coloque un signo "+" en la celda de perspectiva (1;5) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (1,5 > 1,1 > 3,1 > 3,5).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (3, 5) = 10. Sume 10 a los volúmenes de carga en las celdas positivas y reste 10 de X ij en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 1 = 7; 0 + v 1 = 7; v 1 = 7
u 3 + v 1 = 1; 7 + u 3 = 1; tu 3 = -6
u 3 + v 4 = 2; -6 + v 4 = 2; v4 = 8
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (2;4): -3 + 8 > 2; ? 24 = -3 + 8 - 2 = 3
- (4;1): 2 + 7 > 3; ? 41 = 2 + 7 - 3 = 6
- (4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3
- (4;4): 2 + 8 > 7; ? 44 = 2 + 8 - 7 = 3
máx(3,6,3,3) = 6
Elegimos la puntuación máxima para una celda libre (4;1): 3
Para hacer esto, coloque un signo "+" en la celda de perspectiva (4;1) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (4.1 > 4.5 > 1.5 > 1.1).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (1, 1) = 10. Sume 10 a los volúmenes de carga en las celdas positivas y reste 10 de X ij en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
u 1 + v 5 = 6; 0 + v 5 = 6; v5 = 6
tu 2 + v 5 = 3; 6 + tu 2 = 3; tu 2 = -3
u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3
u 4 + v 5 = 8; 6 + tu 4 = 8; tu 4 = 2
u 4 + v 1 = 3; 2 + v 1 = 3; v 1 = 1
u 3 + v 1 = 1; 1 + tu 3 = 1; tu 3 = 0
u 3 + v 4 = 2; 0 + v 4 = 2; v4 = 2
u 4 + v 2 = 4; 2 + v 2 = 4; v2 = 2
u 4 + v 6 = 0; 2 + v 6 = 0; v 6 = -2
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
(4;3): 2 + 3 > 2; ? 43 = 2 + 3 - 2 = 3
Elegimos la puntuación máxima para una celda libre (4;3): 2
Para hacer esto, coloque un signo "+" en la celda de perspectiva (4;3) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (4,3 > 4,5 > 2,5 > 2,3).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (4, 5) = 15. Sumamos 15 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 15 de X ij que se encuentran en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
u 1 + v 5 = 6; 0 + v 5 = 6; v5 = 6
tu 2 + v 5 = 3; 6 + tu 2 = 3; tu 2 = -3
u 2 + v 3 = 0; -3 + v 3 = 0; v 3 = 3
u 4 + v 3 = 2; 3 + tu 4 = 2; tu 4 = -1
u 4 + v 1 = 3; -1 + v 1 = 3; v 1 = 4
u 3 + v 1 = 1; 4 + tu 3 = 1; tu 3 = -3
u 3 + v 4 = 2; -3 + v 4 = 2; v4 = 5
u 4 + v 2 = 4; -1 + v 2 = 4; v2 = 5
u 4 + v 6 = 0; -1 + v 6 = 0; v 6 = 1
El plan de referencia no es óptimo, ya que existen estimaciones de celdas libres para las cuales u i + v j > c ij
- (1;2): 0 + 5 > 3; ? 12 = 0 + 5 - 3 = 2
- (1;6): 0 + 1 > 0; ? 16 = 0 + 1 - 0 = 1
Seleccione la puntuación máxima para una celda libre (1;2): 3
Para hacer esto, coloque un signo "+" en la celda de perspectiva (1;2) y alterne los signos "-", "+", "-" en los vértices restantes del polígono.
|
Necesidades |
El ciclo se muestra en la tabla (1,2 > 1,5 > 2,5 > 2,3 > 4,3 > 4,2).
De las cargas x ij que se encuentran en las celdas negativas, elegimos la más pequeña, es decir y = min (1, 5) = 20. Sumamos 20 a los volúmenes de carga que se encuentran en las celdas positivas y restamos 20 a X ij que se encuentran en las celdas negativas. Como resultado, obtenemos un nuevo plan de referencia.
|
Necesidades |
Comprobemos la optimización del plan de referencia. encontraremos potenciales preliminares u i , v j . según las celdas ocupadas de la tabla, en las que u i + v j = c ij, suponiendo que u 1 = 0.
tu 1 + v 2 = 3; 0 + v 2 = 3; v2 = 3
u 4 + v 2 = 4; 3 + tu 4 = 4; tu 4 = 1
u 4 + v 1 = 3; 1 + v 1 = 3; v 1 = 2
u 3 + v 1 = 1; 2 + tu 3 = 1; tu 3 = -1
u 3 + v 4 = 2; -1 + v 4 = 2; v4 = 3
u 4 + v 3 = 2; 1 + v 3 = 2; v 3 = 1
u 2 + v 3 = 0; 1 + tu 2 = 0; tu 2 = -1
tu 2 + v 5 = 3; -1 + v 5 = 3; v5 = 4
u 4 + v 6 = 0; 1 + v 6 = 0; v 6 = -1
El plan de referencia es óptimo, por lo que todas las estimaciones de celdas libres satisfacen la condición u i + v j ? cij.
Los costes mínimos serán: F(x) = 3*20 + 0*15 + 3*45 + 1*15 + 2*30 + 3*10 + 4*20 + 2*35 + 0*5 = 450
Análisis del plan óptimo.
Desde el 2º almacén es necesario enviar la carga al 3º almacén (15), al 5º almacén (45)
Desde el 3er almacén es necesario enviar la carga al 1er almacén (15), al 4to almacén (30)
Desde el 4º almacén es necesario enviar la carga al 1º almacén (10), al 2º almacén (20), al 3º almacén (35)
En el cuarto almacén quedaron 5 unidades de carga sin reclamar.
El plan óptimo es degenerado, ya que la variable base x 46 =0.
MÉTODO DE LA ESQUINA NOROESTE
Según este método, las existencias del siguiente proveedor se utilizan para abastecer las solicitudes de los siguientes consumidores hasta que se agoten por completo, después de lo cual se utilizan las existencias del siguiente proveedor por número.
El llenado de la tabla de tareas de transporte comienza desde la izquierda. esquina superior y consta de una serie de pasos similares. En cada paso, en función de las existencias del siguiente proveedor y las solicitudes del siguiente consumidor, solo se llena una celda y, en consecuencia, se excluye de la consideración a un proveedor o consumidor. En este caso, se acostumbra ingresar cero transporte en la tabla solo cuando caen en la celda (i,j) a completar, es decir Solo se ingresan ceros de base en la tabla, las celdas restantes con transporte cero permanecen vacías.
Para evitar errores, después de construir la solución de referencia inicial, es necesario comprobar que el número de celdas ocupadas es igual a m+n-1 y que los vectores de condición correspondientes a estas celdas son linealmente independientes.
Hay que tener en cuenta que el método de la esquina noroeste no tiene en cuenta el coste de transporte, por lo que la solución de referencia construida con este método puede estar lejos de ser óptima.
Cree una solución de soporte utilizando el método de la esquina noroeste para un problema de transporte en el que hay 5 proveedores y 5 consumidores. Los datos se registran en la tabla 6.
Tabla 6
Distribuimos las existencias del primer proveedor. Dado que sus reservas son menores que las solicitudes del primer consumidor, escribimos transporte en la celda (1,1) y excluimos al primer proveedor de nuestra consideración. Determinamos las restantes solicitudes insatisfechas del primer consumidor.
Distribuimos el inventario del segundo proveedor. Dado que sus reservas son menores que las solicitudes del primer consumidor, escribimos transporte en la celda (2,1) y excluimos al segundo proveedor de nuestra consideración. Determinamos las restantes solicitudes insatisfechas del primer consumidor.
Distribuimos stocks de un tercer proveedor. Dado que sus reservas son mayores que las solicitudes del primer consumidor, escribimos transporte en la celda (3,1) y excluimos al primer consumidor de nuestra consideración. Identificamos las restantes solicitudes insatisfechas del tercer proveedor.
Distribuimos stocks de un tercer proveedor. Dado que sus reservas son menores que las demandas del segundo consumidor, escribimos el transporte en la celda (3,2) y excluimos al tercer proveedor de nuestra consideración. Determinamos las solicitudes restantes insatisfechas del segundo consumidor.
Distribuimos las existencias del cuarto proveedor. Dado que sus reservas son mayores que las demandas del segundo consumidor, escribimos el transporte en la celda (4,2) y excluimos al segundo consumidor de nuestra consideración. Identificamos las solicitudes restantes insatisfechas del cuarto proveedor.
Distribuimos las existencias del cuarto proveedor. Dado que sus reservas son menores que las solicitudes del tercer consumidor, escribimos el transporte en la celda (4,3) y excluimos al cuarto proveedor de nuestra consideración. Determinamos las restantes solicitudes insatisfechas del tercer consumidor.
Distribuimos el inventario del quinto proveedor. Dado que sus reservas son mayores que las solicitudes del tercer consumidor, escribimos el transporte en la celda (5,3) y excluimos al tercer consumidor de nuestra consideración. Determinamos los inventarios restantes insatisfechos del quinto proveedor.
Distribuimos el inventario del quinto proveedor. Dado que sus reservas son mayores que las solicitudes del cuarto consumidor, escribimos el transporte en la celda (5,4) y excluimos al cuarto consumidor de nuestra consideración. Determinamos los inventarios restantes insatisfechos del quinto proveedor.
Distribuimos el inventario del quinto proveedor. Dado que sus reservas son iguales a las demandas del quinto consumidor, escribimos transporte en la celda (5,5) y excluimos de la consideración al quinto proveedor y al quinto consumidor.
Debido a que el problema es el equilibrio adecuado, las existencias de todos los proveedores se agotan y las demandas de todos los consumidores están satisfechas.
Los resultados de la construcción de la solución de referencia se muestran en la Tabla 7.
DIAGRAMA DE BLOQUES (ALGORITMO DE SOLUCIÓN)
Occidental
Para que la tarea de transporte programación lineal tenía una solución, es necesario y suficiente que los inventarios totales de los proveedores igualen las demandas totales de los consumidores, es decir la tarea debe realizarse con el equilibrio adecuado.
Teorema 38.2 Propiedad del sistema de restricciones del problema de transporte
El rango del sistema de vectores-condiciones del problema del transporte es igual a N=m+n-1 (m - proveedores, n-consumidores)
Solución de referencia al problema del transporte.
Una solución de referencia a un problema de transporte es cualquier solución factible, para lo cual los vectores de condición correspondientes a las coordenadas positivas son linealmente independientes.
Debido a que el rango del sistema de vectores-condiciones del problema de transporte es igual a m+n - 1, la solución de referencia no puede tener más de m+n-1 coordenadas distintas de cero. El número de coordenadas distintas de cero de una solución de referencia no degenerada es igual a m+n-1, y para una solución de referencia degenerada es menor que m+n-1
CicloCiclo dicha secuencia de celdas en la tabla del problema de transporte se llama (i 1 , j 1),(i 1 , j 2),(i 2 , j 2),...,(i k , j 1), en la que hay son dos y sólo dos celdas adyacentes dispuestas en una fila o columna, con la primera y la última celda también en la misma fila o columna.
El ciclo se representa como una tabla del problema de transporte en forma de línea discontinua cerrada. En un ciclo, cualquier celda es una celda de esquina en la que un enlace de polilínea gira 90 grados. Los ciclos más simples se muestran en la Figura 38.1.
Teorema 38.3Una solución admisible al problema de transporte X=(x ij) es una solución de referencia si y sólo si no se puede formar ningún ciclo a partir de las celdas ocupadas de la tabla.
Método de tachado
El método de tachado le permite comprobar si esta decisión referencia de la tarea de transporte.
Sea escrita en una tabla una solución admisible al problema de transporte, que tiene m+n-1 coordenadas distintas de cero. Para que esta solución sea una solución de referencia, los vectores de condición correspondientes a las coordenadas positivas, así como los ceros de base, deben ser linealmente independientes. Para esto ocupado decidiendo Las celdas de la mesa deben estar dispuestas de modo que sea imposible formar un ciclo a partir de ellas.
Una fila o columna de una tabla con una celda ocupada no se puede incluir en ningún ciclo, ya que un ciclo tiene dos y solo dos celdas en cada fila o columna. Por lo tanto, primero tache todas las filas de la tabla que contengan una celda ocupada cada una, o todas las columnas que contengan una celda ocupada cada una, luego regrese a las columnas (filas) y continúe tachando.
Si, como resultado de la eliminación, todas las filas y columnas están tachadas, significa que de las celdas ocupadas de la tabla es imposible seleccionar una parte que forme un ciclo, y el sistema de vectores-condiciones correspondientes es linealmente independiente. y la solución es de referencia.
Si, después de eliminar, quedan algunas celdas, entonces estas celdas forman un ciclo, el sistema de vectores-condiciones correspondientes es linealmente dependiente y la solución no es de referencia.
Ejemplos de “tachado” (referencia) y “no tachado” (soluciones sin referencia): 
Lógica de tachado:
- Tacha todas las columnas que tengan solo una celda ocupada (5 0 0), (0 9 0)
- Tacha todas las líneas que tengan solo una celda ocupada (0 15), (2 0)
- Repetir ciclo (7) (1)
Métodos para construir una solución de referencia inicial.
Método del ángulo noroeste
Existen varios métodos para construir una solución de referencia inicial, el más simple de los cuales es el método de la esquina noroeste.
EN este método Los inventarios del siguiente proveedor por número se utilizan para abastecer las solicitudes de los siguientes consumidores numerados hasta que se agoten por completo, después de lo cual se utilizan los inventarios del siguiente proveedor por número.
El llenado de la tabla de tareas de transporte comienza desde la esquina superior izquierda, por eso se llama método de la esquina noroeste.
El método consta de una serie de pasos similares, en cada uno de los cuales, en función de las existencias del siguiente proveedor y las solicitudes del siguiente consumidor, solo se completa una celda y, en consecuencia, se excluye de la consideración a un proveedor o un consumidor. .
Ejemplo 38.1Cree una solución de soporte utilizando el método del ángulo noroeste.
1. Distribuimos las existencias del 1er proveedor.
Si las reservas del primer proveedor son mayores que las solicitudes del primer consumidor, entonces escriba en la celda (1,1) el monto de la solicitud del primer consumidor y pase al segundo consumidor. Si las reservas del primer proveedor son menores que las solicitudes del primer consumidor, entonces escribimos en la celda (1,1) el monto de las reservas del primer proveedor, excluimos al primer proveedor de la consideración y pasamos al segundo proveedor. .
Ejemplo: dado que sus reservas a 1 =100 son menores que las solicitudes del primer consumidor b 1 =100, entonces en la celda (1,1) anotamos el transporte x 11 =100 y excluimos al proveedor de la consideración.
Determinamos las solicitudes restantes insatisfechas del 1er consumidor b 1 = 150-100 = 50.
2.Distribuimos las existencias del 2º proveedor.
Dado que sus reservas a 2 = 250 son mayores que las solicitudes restantes insatisfechas del primer consumidor b 1 =50, en la celda (2,1) anotamos el transporte x 21 =50 y excluimos al primer consumidor de la consideración.
Determinamos los inventarios restantes del segundo proveedor a 2 = a 2 - b 1 = 250-50 = 200. Dado que los inventarios restantes del segundo proveedor son iguales a las demandas del segundo consumidor, escribimos x 22 = 200 en la celda (2,2) y excluimos, a nuestra discreción, al segundo proveedor o al segundo consumidor. En nuestro ejemplo, excluimos al segundo proveedor.
Calculamos las solicitudes restantes insatisfechas 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 las existencias del 3er proveedor.
¡Importante! EN paso anterior teníamos la opción de excluir al proveedor o al consumidor. Como excluimos al proveedor, las solicitudes del segundo consumidor aún permanecieron (aunque iguales a cero).
Debemos escribir las solicitudes restantes iguales a cero en la celda (3,2)
Esto se debe a que si se requiere que el transporte se coloque en la siguiente celda de la tabla (i, j), y el proveedor con el número i o el consumidor con el número j tiene cero inventarios o solicitudes, entonces el transporte es igual a cero ( cero básico) se coloca en la celda, y entonces se excluye de la consideración al proveedor relevante o al consumidor.
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 referencia inicial, es necesario verificar que el número de celdas ocupadas sea igual a m+n-1 (la base cero también se considera una celda ocupada), y los vectores de condición correspondientes a estas celdas son linealmente independientes.
Dado que en el paso anterior excluimos al segundo proveedor de la consideración, escribimos x 32 =0 en la celda (3.2) y excluimos al segundo consumidor.
Los inventarios del proveedor 3 no han cambiado. En la celda (3.3) escribimos x 33 =100 y excluimos al tercer consumidor. En la celda (3,4) escribimos x 34 =100. Debido a que nuestra tarea es lograr el equilibrio adecuado, las existencias de todos los proveedores se agotan y las demandas de todos los consumidores se satisfacen total y simultáneamente.
| Solución de referencia | ||||
| 150 | 200 | 100 | 100 | |
| 100 | 100 | |||
| 250 | 50 | 200 | ||
| 200 | 0 | 100 | 100 | |
4. Comprobamos la corrección de la construcción de la solución de referencia.
El número de celdas ocupadas debe ser igual a N=m(proveedores)+m(consumidores) - 1=3+4 - 1=6.
Usando el método de tachado, nos aseguramos de que la solución encontrada sea “tachada” (el cero básico está marcado con un asterisco). 
En consecuencia, los vectores de condición correspondientes a las celdas ocupadas son linealmente independientes y la solución construida es efectivamente una solución de referencia.
Método de costo mínimo
El método del costo mínimo es simple y permite construir una solución de referencia bastante cercana a la óptima, ya que utiliza la matriz de costos del problema de transporte C=(c ij).
Al igual que el método de la esquina noroeste, consta de una serie de pasos similares, en cada uno de los cuales solo se completa una celda de la tabla, correspondiente al costo mínimo:
y sólo se excluye de la consideración una fila (proveedor) o una columna (consumidor). La siguiente celda correspondiente a se completa de acuerdo con las mismas reglas que en el método de la esquina noroeste. Un proveedor queda excluido de la consideración si su inventario de carga está totalmente utilizado. El consumidor queda excluido de la consideración si sus solicitudes son plenamente satisfechas. En cada paso, se elimina un proveedor o un consumidor. Además, si el proveedor aún no ha sido excluido, pero sus inventarios son iguales a cero, entonces en el paso en el que este proveedor debe entregar la carga, se ingresa una base cero en la celda correspondiente de la tabla y solo entonces el proveedor es excluidos de la consideración. Lo mismo con el consumidor.
Utilizando el método del costo mínimo, construya una solución de referencia inicial al problema de transporte.
1. Anotemos la matriz de costos por separado para que sea más conveniente elegir los costos mínimos. 
2. Entre los elementos de la matriz de costos, seleccione el costo más bajo C 11 =1, márquelo con un círculo. este costo ocurre cuando se transporta carga del primer proveedor al primer consumidor. En la casilla correspondiente anotamos el volumen máximo de transporte posible:
x 11 = mín (a 1; b 1) = mín (60; 40) =40 aquellos. el mínimo entre las existencias del 1er proveedor y las solicitudes del 1er consumidor.
2.1. Reducimos los inventarios del 1er proveedor en 40.
2.2. Excluimos de nuestra consideración al primer consumidor, ya que sus solicitudes quedan plenamente satisfechas. En la matriz C tachamos la 1ª columna.
3. En la parte restante de la matriz C, el costo mínimo es el costo C 14 =2. Máximo posible transporte, que se puede realizar desde el primer proveedor hasta el cuarto consumidor es igual a x 14 = mínimo (a 1 "; b 4 ) = mínimo (20; 60) = 20, donde un 1 con número primo es el inventario restante del primer proveedor.
3.1. Las existencias del 1er proveedor están agotadas, por lo que lo excluimos de nuestra consideración.
3.2. Reducimos en 20 las solicitudes del 4º consumidor.
4. En la parte restante de la matriz C, el costo mínimo es C 24 =C 32 =3. Complete una de las dos celdas de la tabla (2.4) o (3.2). Escribámoslo en una jaula. x 24 = mín (a 2; b 4) = mín (80; 40) =40 .
4.1. Las solicitudes del cuarto consumidor han sido satisfechas. Lo excluimos de nuestra consideración tachando la cuarta columna de la matriz C.
4.2. Reducimos el inventario del 2º proveedor 80-40=40.
5. En la parte restante de la matriz C, el costo mínimo es C 32 =3. Escribamos transporte en la celda (3,2) de la tabla. x 32 = mín (a 3; b 2) = mín (100; 60) =60.
5.1. Excluyamos de nuestra consideración al segundo consumidor. Excluimos la segunda columna de la matriz C.
5.2. Reduzcamos los inventarios del 3er proveedor 100-60=40
6. En la parte restante de la matriz C, el costo mínimo es C 33 =6. Escribamos transporte en la celda (3,3) de la tabla. x 33 = mín (a 3 "; b 3 ) = mín (40; 80) =40
6.1. Excluyamos de la consideración al tercer proveedor y a la tercera fila de la matriz C.
6.2. Determinamos las solicitudes restantes del tercer consumidor 80-40=40.
7. El único elemento que queda en la matriz C es C 23 =8. Escribimos en la celda de la tabla (2.3) transporte X 23 =40.
8. Comprobamos la corrección de la construcción de la solución de referencia.
El número de celdas ocupadas en la tabla es N=m+n - 1=3+4 -1.
Comprobamos tachando el método. independencia lineal vectores de condición correspondientes a las coordenadas positivas de la solución. El orden de eliminación se muestra en la matriz X:
Conclusión: La solución por el método del costo mínimo (Tabla 38.3) está “tachada” y, por tanto, es referencia.
