Costo Minimo

PROGRAMACION DE REDES. MODELOS DE TRANSPORTE
El modelo de transporte o modelo de distribución es un ejemplo de un
problema de optimización de redes. Se aplican para resolver ciertos tipos de
problemas de P.L.
Un problema típico es el de una Empresa que tienen varias plantas que
producen el mismo producto. Estas plantas deben enviar sus productos a
varios destinos. Cada planta tiene una capacidadlimitada y cada destino tiene
una demanda. Cada planta puede enviar sus productos a cualquiera de los
destinos, pero el costo de transporte varia con las diferentes combinaciones.
La meta de un modelo de transporte es minimizar el costo total del envío del
producto desde los puntos de existencia hasta los puntos de demanda
satisfaciendo las siguientes restricciones:
1. Cada punto de demanda recibesu requerimiento
2. Los embarques desde un punto de suministro no exceden su capacidad
disponible.

Hay muchas situaciones que no tienen relación con el transporte físico, pero
su estructura es la misma y por lo tanto es aplicable el método.

Programación de redes
Modelos de transporte

CARACTERISTICAS
 Su estructura: “de…hacia…” (de un origen hacia un destino;
de
una fuente a un usuario; delpresente al futuro; de aquí hacia alla; etc.).
 Se conocen:
i.
ii.
iii.

Las fuentes y los destinos
Las capacidades y demandas
Los costos de cada trayectoria

 Debe haber una combinación optima ( minimizar costos o maximizar
ganancias)
 Si se expresa como un problema de P.L.( programación lineal)
 Los coeficientes de las restricciones son 1 ó 0.
 Los totales de las restricciones de losorígenes son iguales a los
totales de las restricciones de los destinos.
 Si hay m orígenes y n destinos, habrán m + n restricciones (una de
ellas es redundante). El numero de restricciones independientes
es m+n-1.
 En cualquier problema de P.L. el # de variables en la
solución final no pueden exceder el # de restricciones
independientes

METODO
Básicamente el método consta de tres fases: 1) Laconstrucción de la matriz. 2) Encontrar una solución inicial
y 3) Por iteración buscan la solución óptima.

1. Construcción de la matriz:

 Es importante adoptar cierto orden en la construcción de
la matriz, de manera tal que facilite las siguientes fases.
Uno de ellos es el siguiente:
 A cada origen le corresponde una fila y a cada
destino una columna.
 La demanda de cada destino se escribe debajo dela
columna correspondiente y la capacidad de cada
origen se escribe a la derecha de la fila
correspondiente.
Estos totales se conocen como condiciones de
frontera. Cuando el total de las demandas coincide con el total
de las capacidades, decimos que el problema esta balanceado.
En caso contrario que esta desbalanceado, para balancearlo se
crean fuentes o destino ficticio.
 En cada celda, en laesquina superior
izquierda se anota el costo unitario de
transporte, desde casa origen a cada destino.
EJEMPLO:
A partir de los siguientes datos construya la matriz se transporte
correspondiente.
Destino

Demanda

Origen

Capacidad

D1

150

O1

100

D2

150

O2

200

D3

120

O3

300

D4

80

Total

600

Total

500

Costos ($/unidad)
hacia
De D1 D2 D3 D4
O1 7 3 8 8
O2 5 5 6 8
O3 7 4 9 10Solución: Primeramente vemos que se trata de un problema no balanceado.
Dado que la demanda es menor que la capacidad, se crea un destino ficticio,
con costo de transporte de $0
O1
O2
O3

D1
7
5 150
7
150

D2
3 100
5
4 50
150

D3
8
6 50
9 70
120

D4
8
8
10 80
80

D5
0
0
0 100
100

100
200
300
600

2. BUSQUEDA DE UNA SOLUCION INICIAL:
Se cuentan con varios métodos: Método de la esquina N.O. (fácil
perosolución muy pobre); Método del costo mínimo; Método de
aproximación de Vogel,…
 Método del costo mínimo: ( Como el objetivo es
minimizar los costos de transporte, buscamos
inicialmente las rutas menos costosas estando
claros que no necesariamente es la solución
optima)
1) Buscamos la celda de costo mínimo y la
llenamos hasta el máximo que las condiciones
de frontera lo permitan( sin considerar...