optimizacion transporte

UNIVERSIDAD CATÓLICA DE SANTA MARÍA
PROGRAMA PROFESIONAL DE INGENIERÍA DE SISTEMAS



SESIÓN 9: SOLUCIÓN ÓPTIMA DEL MODELO DE TRANSPORTE



I
OBJETIVOS

Resolver problemas de transporte balanceados con el Método de la Esquina Noroeste.
Encontrar la solución optima de un modelo de transporte balanceado.

II
TEMAS A TRATAR

Modelos de programación lineal de transporte
Métodode la Esquina Noroeste para transporte balanceado
Método de los multiplicadores

III
MARCO TEORICO

Una vez que se ha determinado una solución inicial con cualquiera de los 3 métodos vistos en la clase pasada (esquina noroeste, coste mínimo), se usa el siguiente algoritmo para determinar la solución óptima:

Primer paso: Validar la condición de optimalidad símplex, para determinar lavariable de entrada como variable no básica que permita mejorar la solución. Si la condición de optimalidad se satisface, detenerse, sino seguir al segundo paso.

Segundo paso: Determinar la variable de salida con la condición de factibilidad símplex. Regresar al primer paso.

Tomando como ejemplo el ejercicio de la práctica anterior, por el método de la esquina noroeste se llegó a esta primerasolución:

Molino


1
2
3
4
Oferta
Silo
1
10
5
2
10
20

11

15

2
12

7
5
9
15
20
5
25

3
4

14

16

18
10
10
Demanda

5
15
15
15





Para este caso hay 12 variables, desde x11 hasta x34:

Molino


1
2
3
4
Oferta
Silo
1
10
X11
2
X12
20
X13
11
X14
15

2
12
X21
7
X22
9
X23
20
X24
25

3
4
X31
14
X32
16
X33
18X34
10
Demanda

5
15
15
15


Las variables básicas, son aquellas que forman parte de la solución (x11, x12, x22, x23, x24 y x34).
Para determinar la variable de entrada del primer paso, se utiliza el método de los multiplicadores, donde se asocian los multiplicadores ui y vj a cada fila y columna de la tabla de transporte, de tal manera que satisfagan las ecuaciones siguientes:

ui +vj = cij, para cada xij básica, cij es el costo de la celda ij

En el ejemplo tenemos 6 variables básicas, para hallar la variable de entrada y resolver estas ecuaciones con el método de los multiplicadores, arbitrariamente u1 = 0 y a partir de allí se empieza a despejar el resto de variables.

Variable básica Ecuación (u,v) Solución
X11 u1 + v1 = 10 si u1 = 0 entonces v1 = 10
X12u1 + v2 = 2 u1 = 0 entonces v2 = 2
X22 u2 + v2 = 7 como v2 = 2 entonces u2 = 5
X23 u2 + v3 = 9 como u2 = 5 entonces v3 = 4
X24 u2 + v4 = 20 u2 = 5 entonces v4 = 15
X34 u3 + v4 = 18 como v4 = 15 entonces u3 = 3

Resumiendo tenemos que u1 = 0, u2 = 5, u3 = 3, v1 = 10, v2 = 2, v3 = 4, v4 = 15
Con estos resultados, evaluamos las variables no básicas (x13, x14, x21, x31, x32,x33) para hallar la variable de entrada, y se hace calculando:
ui + vj – cij para cada variable no básica, cij es el costo de la celda ij

Por lo tanto:
Variable no básica ui + vj – cij
X13 u1 + v3 – c13 = 0 + 4 – 20 = -16
X14 u1 + v4 – c14 = 0 + 15 – 11 = 4
X21 u2 + v1 – c21 = 5 + 10 – 12 = 3
X31 u3 + v1 – c31 = 3 + 10 – 4 = 9
X32 u3 + v2 – c32 = 3 + 2 – 14 = -9
X33u3 + v3 – c33 = 3 + 4 – 16 = -9

Estos cálculos se reflejan en las esquinas sureste de cada celda de la tabla de transporte:

Molino


1
2
3
4
Oferta
Silo
1
10
5
2
10
20

-16
11

4
15

2
12

3
7
5
9
15
20
5
25

3
4

9
14

-9
16

-9
18
10
10
Demanda

5
15
15
15


Así la variable de entrada es aquella de mayor valor, en este caso x31 (9),ahora debemos determinar la variable de salida. La variable de entrada nos indica que para el modelo de transporte es conveniente ir por esa ruta (x31) porque reduce el costo total del transporte, lo que hay que hacer ahora es disminuir la cantidad transportada en otras rutas para poder asignarle a ésta que acabamos de hallar, manteniendo las dos siguientes condiciones del modelo de transporte:...