Metodo esquina noroeste

PRESENTADO POR:

2.1.2 Método de la esquina noroeste y Procedimiento de optimización.
 Determinación general del modelo de transporte 
 



requiere que: m n ai =  bj i=1 j=1 Este requisito da origen a una ecuación dependiente, lo que significa que el modelo de transporte tiene sólo m + n –1 ecuaciones independientes. Por lo tanto, como en el método simplex, una solución factiblebásica inicial debe incluir m + n – 1 variables básicas.

 Normalmente, si el modelo de transporte se formula

como una tabla simplex, sería necesario utilizar variables artificiales para asegurar una solución básica inicial. Sin embargo, cuando se utiliza la tabla de transporte, una solución factible básica inicial se puede obtener fácil y directamente. Presentamos un procedimiento llamadoregla de la esquina noroeste para este fin.

Destino 1 Fuente 1 X11 2 X21 3 X31 0 X32 15 12 X22 14 X33 15 10 X12 7 X23 16 X34 10 2 0 X13 9 X24 18 5 3 20 X14 20 25 4 11

Oferta
15

Demanda

5

 El método de la esquina noroeste comienza con la

asignación de la máxima cantidad admisible a través de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla).Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero.

 Si se satisfacen una columna y un renglón al mismo

tiempo, sólo una (una u otro) puede ser tachada. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay).

 Después de ajustar las cantidades de oferta ydemanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso se completa cuando se deja sin tachar exactamente un renglón o una columna.

 El procedimiento que se acaba de describir se aplica

ahora en el ejemplo:  1. x11 = 5, se tacha la columna 1. Por lo tanto, no se puede hacer otraasignación en la columna 1. La cantidad que falta en el renglón 1 son 10 unidades.  2. x12 = 10, se tacha el renglón 1 y faltan 5 unidades en la columna 2.  3. x22 = 5, se tacha la columna 2 y faltan 20 unidades en el renglón 2.

 4.

x23 = 15, se tacha la columna 3 y faltan 5 unidades en el renglón 2.  5. x24 = 5, se tacha el renglón 2 y faltan 5 unidades en la columna 4.  6. x34 = 5, se tachael renglón 3 o la columna 4. Como sólo un renglón o una columna se mantienen sin tachar, el proceso llega a su fin.

 La solución básica inicial resultante se presenta a

continuación.  Las variables básicas son x11 = 5, x22 =10, x23 =15, x24 =5 y x34 = 5. Las variables restantes son no básicas en el nivel cero. El costo de transporte asociado es:  5 x 10 +10 x 0 + 5 x 7+ 15 x 9 + 5 x 20+5 x 18 = $410.

1 1 2 3 5 5

2 10 5

3

4 15

15

5 5

25 5

15

15

10

 Cuando se satisfacen al mismo tiempo una columna

y un renglón, la siguiente variable que se agregará a la solución básica estará necesariamente en el nivel cero. La siguiente tabla ilustra este aspecto. La columna 2 y el renglón 2 se satisfacen simultáneamente.

1 1 2 3 5 5

2 5 5

3

410 5 0

0 8 7 7

5 15 15

10 5

8

 Si se tacha la columna 2, x23 se vuelve básica en el

nivel cero en el paso siguiente, ya que la demanda restante del renglón 2 vale ahora cero.(Este caso se presenta en la tabla anterior). Si en cambio se cruza el renglón 2, x32 sería la variable básica cero.

 Las soluciones iníciales de las dos últimas tablas

incluyen el número adecuadode variables básicas, o sea, m + n-1 = 6. La regla de la esquina noroeste produce siempre el número adecuado de variables básicas.

DETERMINACIÓN DE LA VARIABLE DE ENTRADA (MÉTODO DE MULTIPLICADORES)
 La variable que entra se determina mediante el uso

de la condición de Optimalidad del método simplex. Los cálculos de los coeficientes de la función objetivo están basados en las relaciones...