Unidad i

UNIDAD IAPLICACIONES DE LA PROGRAMACIÓN LINEAL

EL MÉTODO DE TRANSPORTE

Este método se utiliza para minimizar tiempo y los cotos al crear guías de rutas.

Para cualquiera de los métodos de resolución, es fundamental que la matriz del problema mantenga su oferta y demanda equilibrada; caso contrario será necesario equilibrarla aumentando ficticias (filas o columnas) en la oferta o en la demanda según se requiera para cada ejercicio.

Se lo puede resolver mediante:

1. MCM, Método del Costo Mínimo.2. MEN, Método de la Esquina Noroeste3. MAV o VAM, Método de Aproximación de Vogel

Estos métodos proporcionan una solución básica factible, y para resolver cada uno se debe conocer el algoritmo.

También se resuelve por los siguientes métodos:

1. MODI, Método de distribución modificada2. Método de Pasos Secuenciales3. Método del Trampolín

Estos últimos nos proporcionan solución óptima; como también es el caso del método simplex.

|

1 2 3 OFERTA

A 300

B 100

C200

6001500

600500400DEMANDA

Existe una diferencia en la suma de O y D; por lo que

debemos agregar una oferta con costos 0.

1 2 3 OFERTA

A 300

B 100

C200

f 0 0 0900

1500

1500600500400DEMANDA

Ahora si está lista para poder resolver


MÉTODO DE COSTO MÍNIMO

ALGORITMO DE RESOLUCIÓN

1. De la matriz se elige la ruta menos costosa (en caso de empate, rompa arbitrariamente) y se le asigna la mayor cantidad de unidades posibles, cantidad que se verá restringida por las restricciones de oferta o demanda. Aquí mismo ajuste la oferta y la demanda restando la cantidad asignada.

2. Elimine la fila cuya oferta o demanda sea cero, si dado el caso, ambas son cero, arbitrariamente elija cual eliminar y la restante se deja con demanda u oferta cero, según sea el caso.

3. Una vez en este paso, existen dos posibilidades. La primera es que quede un solo renglón o columna; si este es el caso, se llega al

final del método. La segunda es que quede más de un renglón o columna, si este es el caso, inicie

nuevamente el paso uno.

EJERCICIO 1

1

A 6 8 12 5500

B 7 9 10 6800

C 4 5 13 9300

1600

1600

OFERTAORIGEN

DEMANDA 700 200400300

32 4

DESTINOS

MCM=C1+A2+A4+B2+B3MCM=2400+1000+900+7000+1200MCM=12500 SOLUCIÓN BÁSICA FACTIBLE

COMPROBACIÓN

i+ j−1≤ Número de celdas ocupadas

m+n−1≤3+4−1≤6

EJERCICIO 2

MCM=1A+1B+2B+2C+2D+3B+4AMCM=1000+1500+1400+1200+200+5600+400

|

A 6300

8 12200

5500

B 7100

9700

10 6800

C 300 4 5 13 9300

1600

1600

OFERTAORIGEN

DEMANDA 700 200400300

32 4

DESTINOS

1

1 4 6 8 12500

2 6 14 4 1600

3 5 16 16 20350

4 2 16 8 9200

1650

1650

OFERTAORIGEN

DEMANDA 300 200700450

CB D

DESTINOS

A

1 250 4 250 6 8 12500

2 6 100 14 300 4 200 1600

3 5 350 16 16 20350

4 200 2 16 8 9200

1650

1650

OFERTAORIGEN

DEMANDA 300 200700450

CB D

DESTINOS

A


MCM=1130 0 SOLUCIÓN BÁSICA FACTIBLE

COMPROBACIÓN

m+n−1≤4+4−1≤7

MÉTODO DE LA ESQUINA NOROESTE

Proporciona una solución básica factible. Empieza en la celda 11

EJERCICIO 1

La Panadería Granis con sucursales en la Dolorosa, Circunvalación y Plaza Giralda oferta 30, 40 y 10 unidades de panes a la Condamine, TIA, AKÍ y Sp-Maxi, que demandad de 20, 10, 30 y 20 unidades de pan respectivamente.

Z=240+80+270+120+100 Z=810

EJERCICIO 2

|

DOLOROSA 20 12 10 8 4 830

CIRCUNVALACIÓN 5 7 30 9 10 1240

PLAZA GIRALDA 10 2 7 10 1010

80

80

OFERTAORIGEN

DEMANDA 30 201020

AKÍTÍA SP-MAXI

DESTINOS

CONDAMINE

DOLOROSA 12 8 4 830

CIRCUNVALACIÓN 5 7 9 1240

PLAZA GIRALDA 10 2 7 1010

80

80

OFERTAORIGEN

DEMANDA 30 201020

AKÍTÍA SP-MAXI

DESTINOS

CONDAMINE


1 100 2 100 6 2 10 5200

2 3 100 1 100 3 2 10200

3 5 4 100 6 8 5100

4 9 5 100 4 100 3 100 2300

800

800

OFERTAORIGEN

DEMANDA 300 100200100

CB E

DESTINOS

A D

100

Z=200+600+100+300+600+400+300+200 Z=2700

EJERCICIO 3

|

1 2 6 2 10 5200

2 3 1 3 2 10200

3 5 4 6 8 5100

4 9 5 4 3 2300

800

800

OFERTAORIGEN

DEMANDA 300 100200100

CB E

DESTINOS

A D

100

1 630 3 7 9 630

2 120 6 395 12 10 515

3 0 25 0 205 0 230

1375

1375

OFERTAORIGEN

DEMANDA 205420750

CB

DESTINOS

A

1 3 7 9 630

2 6 12 10 515

1145

1375

OFERTAORIGEN

DEMANDA 205420750

CB

DESTINOS

A


Z=1890+720+4740Z=7350

MÉTODO DE APROXIMACIÓN DE VOGEL (VAM)(MAV)

Proporciona Solución Factible Básica


1. Determinar para cada fila y columna una medida de penalización restando los 2 costos menores en filas y columnas.

2. Seleccione la fila o columna con la mayor penalización.3. De la fila o columna de mayor penalización escojo la celda con el menor costo y

asigne la cantidad posible de unidades.4. Si queda sin tachar una fila o columna, deténgase.

Si queda sin tachar una fila o columna con oferta o demanda positiva aplique el método de costo mínimo y termine.

Si todas las filas y columnas que no se tacharon tienen oferta cero o demanda cero determine las variables básicas cero utilizando el MCM y termine.

Si no se presenta ninguno de los casos anteriores, vuelva al paso 1 hasta que las ofertas se hayan agotado.

EJERCICIO

|

ANGEL 12 13 300 4 5300

MATEO 6 5 10 11100

1

CARLOS 10 9 11 4200

5

600

6004 4 7

OFERTAORIGEN

DEMANDA 30010050

INFANTILMALDONADO

DESTINOS

SUCRE BELLAVISTA

150

ANGEL 12 13 300 4 5300

MATEO 50 6 50 5 10 11100

CARLOS 10 50 9 11 150 4200

600

600

OFERTAORIGEN

DEMANDA 30010050

INFANTILMALDONADO

DESTINOS

SUCRE BELLAVISTA

150

ANGEL 12 13 4 5300

1

MATEO 6 5 10 11100

1

CARLOS 10 9 11 4200

5

600

6004 4 6 1

OFERTAORIGEN

DEMANDA 30010050

INFANTILMALDONADO

DESTINOS

SUCRE BELLAVISTA

150

ANGEL 12 13 300 4 5300

MATEO 6 5 10 11100

1

CARLOS 10 9 11 150 4200

5

600

6004 4

OFERTAORIGEN

DEMANDA 30010050

INFANTILMALDONADO

DESTINOS

SUCRE BELLAVISTA

150


Z=1200+300+250+450+600

Z=2700

MÉTODO DE ASIGNACIÓN O HÚNGARO

Para su aplicación debemos tener igual número de filas que de columnas No se integra con oferta ni demanda

EJEMPLO PARA MINIMIZAR

S. ALFONSO

DOLOROSA

BELLAVISTA

LA MERCED

9137

9 8 4 12

3 5 46

8 3 2 8

ORIGENDESTINOS

GUANO PENIPE COLTA PALLATANGA

5 4 0 8

REDUCCIÓN DE FILAS

6 1 0 6

6 2 0 8

0 2 3 1

6 1 0 75 3 0 7

0 1 3 06 0 0 5

ASIGNACIÓN

Z=4+1+3+9

Z=17

EJEMPLO PARA MAXIMIZAR

E1

E2

E3

E4

10151613

14 11 9 7

15 9 1413

12 14 17 9

ORIGENDESTINOS

A B C D

E1

E2

E3

E4

10151613

14 11 9 7

15 9 1413

12 14 17 9

ORIGENDESTINOS

A B C D

3 6 8 10

MATRIZ REDUCIDA PARA MINIMIZAR

5 3 0 8

4 1 2 7

2 8 4 3

0 3 5 7

5 3 0 83 0 1 6

REDUCCIÓN DE FILAS0 6 2 1

|

S. ALFONSO

DOLOROSA

BELLAVISTA

LA MERCED

9137

9 8 4 12

3 5 46

8 3 2 8

ORIGENDESTINOS

GUANO PENIPE COLTA PALLATANGA

5 3 0 7

6 0 0 56 1 0 7

REDUCCIÓN DE COLUMNAS0 1 3 0

0 3 0 2

1 0 0 01 1 0 2

ASIGNACIÓN0 6 8 0


REDUCCIÓN DE COLUMNAS0 6 2 05 3 0 73 0 1 50 3 5 6

3 0 1 50 3 5 6

0 6 2 05 3 0 7

ASIGNACIÓN

Z=14+17+16+14

Z=61

MÉTODO DE PASOS SECUENCIALES

Este método comienza con una solución inicial factible (como el que produce el MEN, MCM, MAV). En cada paso se intenta enviar artículos por una ruta que no se haya usado en la solución factible actual, en tanto se elimina na ruta usada actualmente. En cada cambio de ruta debe cumplirse que:

La solución siga siendo factible. Que mejore el valor de la función objetivo.

El procedimiento termina cuando no hay cambio de rutas que mejore el valor de la función.

Problema degenerado.- es cuando una solución factible usa menos de m+n-1 rutas

Callejones sin salida.- cuando no se encuentran trayectorias apropiadas.


1. Usar la solución actual (MEN, MCM, MAV) para crear una trayectoria única del paso secuencial. Usar estas trayectorias para calcular el costo marginal de introducir a la solución cada ruta no usada.

2. Si todos los costos marginales son iguales o mayores que cero, terminar. Se tendrá la solución óptima; sino, elegir la celda que tenga el costo marginal más negativos (empates se resuelven arbitrariamente)

3. Usando la trayectoria del paso secuencial determine el máximo número de artículos que se pueden asignar a la ruta elegida en el punto 2 y ajustar la distribución adecuadamente.

4. Regrese al paso 1.

EJERCICIO

|


1 12 13 4 6400

2 6 4 10 11600

3 10 9 12 4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1 300 12 100 13 4 6400

2 6 600 4 10 11600

3 10 100 9 200 12 400 4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

MEN=12200

1 300 12 100 13 4 6400

2 6 600 4 10 11600

3 10 100 9 200 12 400 4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1C= 4-12+9-13 -12

1D= 6-4+9-13 -2

2A= 6-12+13-4 3

2C= 10-12+9-4 3

2D= 11-4+9-4 12

3A= 10-12+13-9 2

1 300 12 13 100 4 6400

2 6 600 4 10 11600

3 10 200 9 100 12400

4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1B= 13-9+12-4 12

1D= 6-4+12-4 10

2C= 10-12+9-4 3

2D= 11-4+9-4 12

3A= 10-12+4-12 -10

Z=2400+800+2400+1000+1800+1600Z=10000

MÉTODO DE DISTRIBUCIÓN MODIFICADA

En este método se elabora el circuito en dirección de las manecillas del reloj.

EJERCICIO

A 12 13 4 6500

B 6 4 10 11700

C 10 9 12 4800

2000

2000

OFERTAORIGEN

DEMANDA 200900400

32

DESTINOS

1 4

500

A 400 12 100 13 4 6500

B 6 700 4 10 11700

C 10 100 9 200 12 500 4800

2000

2000

OFERTAORIGEN

DEMANDA 200900400

32

DESTINOS

1 4

500

MEN Z=12200

|

1 300 12 13 100 4 6400

2 6 600 4 10 11600

3 10 200 9 100 12400

4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1 200 12 13 200 4 6400

2 6 600 4 10 11600

3 100 10 200 9 12400

4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1 200 12 13 200 4 6400

2 6 600 4 10 11600

3 100 10 200 9 12400

4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400

1B= 13-9+10-12 2

1D= 6-4+10-12 0

2A= 6-10+9-4 1

2D= 11-4+9-4 12

3C= 12-10+12-4 10

1 200 12 13 200 4 6400

2 6 600 4 10 11600

3 100 10 200 9 12400

4700

1700

1700

OFERTAORIGEN

DEMANDA 200800300

CB

DESTINOS

A D

400


Z= 12000

MÉTODO DEL CRUCE DEL ARROYO

Aquí los ceros constan como celdas llenas.

EJERCICIO

MEN Z=410

|

U1+V1 = 12 U1=0 V1=12 CA3= 4-(U1+V3)= 4-(0+16) = -12

U1+V2 = 13 U2=-9 V2=13 CA4= 6-(U1+V4)= 6-(0+8) = -2

U2+V2 = 4 U3=-4 V3=16 CB1= 6-(U2+V1)= 6-(-9+12) = 3

U3+V2 = 9 V4=8 CB3= 10-(U2+V3)= 10-(-9+16) = 3

U3+V3 = 12 CB4= 11-(U2+V4)= 11-(-9+8) = 12

U3+V4 = 4 CC1= 10-(U3+V1)= 10-(-4+12) = 2

CELDAS LLENAS DONDE: COSTOS EN CELDAS VACÍAS

A 400 12 - 13 100 4 6500

B 6 700 4 10 11700

C 10 200 9 100 12 500 4800

2000

2000

OFERTAORIGEN

DEMANDA 200900400

32

DESTINOS

1 4

500

U1+V1 = 12 U1=0 V1=12 CA2= 13-(0+1) = 12

U1+V3 = 4 U2=3 V2=1 CA4= 6-(0-4) = 10

U2+V2 = 4 U3=8 V3=4 CB1= 6-(3+12) = -9

U3+V2 = 9 V4=-4 CB3= 10-(3+4) = 3

U3+V3 = 12 CB4= 11-(3-4) = 12

U3+V4 = 4 CC1= 10-(8+12) = -10


A 300 12 13 200 4 6500

B 6 700 4 10 11700

C 100 10 200 9 12 500 4800

2000

2000

OFERTAORIGEN

DEMANDA 200900400

32

DESTINOS

1 4

500

U1+V1 = 12 U1=0 V1=12 CA2= 13-(0+11) = 2

U1+V3 = 4 U2=-7 V2=11 CA4= 6-(0+6) = 0

U2+V2 = 4 U3=-2 V3=4 CB1= 6-(-7+12) = 1

U3+V1 = 10 V4=-6 CB3= 10-(-7+4) = 13

U3+V2 = 9 CB4= 11-(-7+6) = 12

U3+V4 = 4 CC1= 12-(-2+4) = 10


1C = 18

1D = -2

2A = -5

3A = -15

3B = 9

3C = 9

1 0 10 15 0 20 1115

2 12 0 7 15 9 10 2025

3 5 0 14 16 0 185

45

45

OFERTAORIGEN

DEMANDA 15155

CB

DESTINOS

A D

10

1 5 10 10 0 20 1115

2 12 5 7 15 9 5 2025

3 0 14 16 5 185

45

45

OFERTAORIGEN

DEMANDA 15155

CB

DESTINOS

A D

10

1C = 18

1D = -2

2A = 10

3B = 24

3C = 9

1 0 10 5 0 20 10 1115

2 12 10 7 15 9 0 2025

3 5 0 14 16 0 185

45

45

OFERTAORIGEN

DEMANDA 15155

CB

DESTINOS

A D

10

1C = 18

2A = 14

3B = 7

3C = 9


Z= 315 Solución óptima

Como se puede apreciar, este método es el que nos ofrece una solución óptima.

|

Documents

Unidad i