Transporte y Asignaci n
Páginas: 9 (2208 palabras)
Publicado: 30 de agosto de 2015
Transporte y Asignación (Prawda pag. 245)
Existen estructuras especiales de la programación lineal que se generan con bastante frecuencia en los problemas reales. Estas estructuras reciben el nombre de estructuras de transporte. A su vez, estas formas especiales de programas lineales pueden dividirse en varias sub-categorías. Estas sub-categorías son: estructuras de asignación, estructura detransbordo o transportes con nodos intermedios, estructura de transportes con capacidad limitada y estructura de transportes generalizados. Todas estas estructuras lineales pueden resolverse por el método simplex. Sin embargo, existen métodos propios asociados a cada estructura que hacen que el método simplex resulte muy ineficiente.
La estructura de transportes
Se supone que m orígenes tienen quesurtir a n centros de consumo con un cierto producto. La capacidad de oferta del origen i es ai (i = 1, …, m) y la demanda en el centro de consumo j bj (j = 1, …, n). Se supone que cij es el costo de enviar una unidad del producto del origen i al centro de consumo j (i = 1, … , n). El problema se reduce a determinar cuántas unidades del producto deben enviarse del origen i al centro de consumo j,tal que minimicen los costos totales de distribución, se satisfaga la demanda del centro de consumo j y no se exceda la capacidad de oferta del origen i. Sea Xij esta variable de decisión. Entonces la formulación del problema lineal es
s.a.
Con la adición de variables de Holgura y superfluas, el problema anterior puede escribirse como
s.a. (PT)
La restricción (1) indica que todoel flujo del producto que emana del origen i y que se envía a todos los posibles m destinos, no puede exceder a la oferta del origen i que es ai. Existe una restricción de ese tipo por cada origen. La restricción (2) indica que todo el flujo del producto que llega al centro de consumo j de todos los posibles n orígenes debe satisfacer la demanda del centro de consumo bj. Existe una restricción deeste tipo por cada centro de demanda. Por último las restricciones de no-negatividad (3) indican que el sentido del flujo del producto es de los orígenes a los destinos únicamente.
Teorema
Una condición necesaria y suficiente para que la estructura de transporte (PT) tenga solución es que la oferta total sea igual a la demanda total, es decir:
El algoritmo de transporte
El problema que sequiere resolver es
Donde ai y bi son números enteros positivos, i = 1, … , m; j = 1, … , n. La explicación se facilita si se establecen dos matrices, una de costos y otra de flujos, tal como se muestra a continuación
Destinos
1
2
.
.
.
n
Of
1
c11
c12
.
.
.
c1n
a1
2
c21
c22
.
.
.
c2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
am
Dem
b1
b2
.
.
.
bn
CostosEn inglés este algoritmo se conoce con el nombre de stepping Stone algotithm, que significa algoritmo de las piedras de paso.
Destinos
1
2
.
.
.
n
Of
1
x11
x12
.
.
.
x1n
a1
2
x21
x22
.
.
.
x2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
xm1
xm2
.
.
.
xmn
am
Dem
b1
b2
.
.
.
bn
Flujos
En el caso de que la oferta total sea mayor que la demanda total, es decir , entoncesse añade un centro de consumo artificial n+1 cuya demanda bn+1 es y cuyos costos unitarios ck,n+1, k = 1, …, m son todos ceros.
En forma tabular se tiene
Destinos
1
2
.
.
.
n
n+1
Of
1
c11
c12
.
.
.
c1n
0
a1
2
c21
c22
.
.
.
c2n
0
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
0
am
Dem
b1
b2
.
.
.
bn
Costos
Por el otro lado, si la demanda totalexcede a la oferta total, es decir , entonces se añade un centro de oferta artificial m+1, cuya capacidad de oferta am+1 es , y cuyos costos unitarios cm+1,k; k = 1, … , n son todos ceros.
Destinos
1
2
.
.
.
n
Of
1
c11
c12
.
.
.
c1n
a1
2
c21
c22
.
.
.
c2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
am
M+1
0
0
.
.
.
0
Dem
b1
b2
.
.
.
bn
Costos
Cuando...
Existen estructuras especiales de la programación lineal que se generan con bastante frecuencia en los problemas reales. Estas estructuras reciben el nombre de estructuras de transporte. A su vez, estas formas especiales de programas lineales pueden dividirse en varias sub-categorías. Estas sub-categorías son: estructuras de asignación, estructura detransbordo o transportes con nodos intermedios, estructura de transportes con capacidad limitada y estructura de transportes generalizados. Todas estas estructuras lineales pueden resolverse por el método simplex. Sin embargo, existen métodos propios asociados a cada estructura que hacen que el método simplex resulte muy ineficiente.
La estructura de transportes
Se supone que m orígenes tienen quesurtir a n centros de consumo con un cierto producto. La capacidad de oferta del origen i es ai (i = 1, …, m) y la demanda en el centro de consumo j bj (j = 1, …, n). Se supone que cij es el costo de enviar una unidad del producto del origen i al centro de consumo j (i = 1, … , n). El problema se reduce a determinar cuántas unidades del producto deben enviarse del origen i al centro de consumo j,tal que minimicen los costos totales de distribución, se satisfaga la demanda del centro de consumo j y no se exceda la capacidad de oferta del origen i. Sea Xij esta variable de decisión. Entonces la formulación del problema lineal es
s.a.
Con la adición de variables de Holgura y superfluas, el problema anterior puede escribirse como
s.a. (PT)
La restricción (1) indica que todoel flujo del producto que emana del origen i y que se envía a todos los posibles m destinos, no puede exceder a la oferta del origen i que es ai. Existe una restricción de ese tipo por cada origen. La restricción (2) indica que todo el flujo del producto que llega al centro de consumo j de todos los posibles n orígenes debe satisfacer la demanda del centro de consumo bj. Existe una restricción deeste tipo por cada centro de demanda. Por último las restricciones de no-negatividad (3) indican que el sentido del flujo del producto es de los orígenes a los destinos únicamente.
Teorema
Una condición necesaria y suficiente para que la estructura de transporte (PT) tenga solución es que la oferta total sea igual a la demanda total, es decir:
El algoritmo de transporte
El problema que sequiere resolver es
Donde ai y bi son números enteros positivos, i = 1, … , m; j = 1, … , n. La explicación se facilita si se establecen dos matrices, una de costos y otra de flujos, tal como se muestra a continuación
Destinos
1
2
.
.
.
n
Of
1
c11
c12
.
.
.
c1n
a1
2
c21
c22
.
.
.
c2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
am
Dem
b1
b2
.
.
.
bn
CostosEn inglés este algoritmo se conoce con el nombre de stepping Stone algotithm, que significa algoritmo de las piedras de paso.
Destinos
1
2
.
.
.
n
Of
1
x11
x12
.
.
.
x1n
a1
2
x21
x22
.
.
.
x2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
xm1
xm2
.
.
.
xmn
am
Dem
b1
b2
.
.
.
bn
Flujos
En el caso de que la oferta total sea mayor que la demanda total, es decir , entoncesse añade un centro de consumo artificial n+1 cuya demanda bn+1 es y cuyos costos unitarios ck,n+1, k = 1, …, m son todos ceros.
En forma tabular se tiene
Destinos
1
2
.
.
.
n
n+1
Of
1
c11
c12
.
.
.
c1n
0
a1
2
c21
c22
.
.
.
c2n
0
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
0
am
Dem
b1
b2
.
.
.
bn
Costos
Por el otro lado, si la demanda totalexcede a la oferta total, es decir , entonces se añade un centro de oferta artificial m+1, cuya capacidad de oferta am+1 es , y cuyos costos unitarios cm+1,k; k = 1, … , n son todos ceros.
Destinos
1
2
.
.
.
n
Of
1
c11
c12
.
.
.
c1n
a1
2
c21
c22
.
.
.
c2n
a1
Orígenes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
m
cm1
cm2
.
.
.
cmn
am
M+1
0
0
.
.
.
0
Dem
b1
b2
.
.
.
bn
Costos
Cuando...
Leer documento completo
Regístrate para leer el documento completo.