Embed Size (px)
Citation preview
EL PROBLEMA DE
TRANSPORTE
EL PROBLEMA DEL TRANSPORTE.
INTRODUCCIÓN.
Una de las primeras formulaciones de una aplicación de programación lineal, anterior incluso al desarrollo de su planteamiento general y resolución, la constituye el "Problema de Transporte".
En general, se trata de la distribución de un producto homogéneo desde unos orígenes hasta unos destinos, teniendo en cuenta las limitaciones de capacidad de aquéllos y
estos, así como el coste de transportar una unidad del producto desde cada origen hasta cada destino, esto es, por "ruta". El objetivo reside en determinar el plan de distribución más económico, es decir, los envíos por cada ruta haciendo mínimo el coste total de transporte.
DEFINICION DEL PROBLEMA DE TRANSPORTE
Sean m puntos de origen , donde cada origen i ( i= 1,2,.....m) tiene una capacidad de oferta de a
i unidades de un cierto artículo (o producto). Ademas existen n puntos de destino,
donde cada destino j ( j= 1,2,...n) tiene una capacidad de demanda de bj unidades del
producto, como se puede reflejar en el siguiente esquema gráfico:
Se trata de determinar las cantidades xij del producto homogéneo a transportar por
cada ruta (i,j) de manera que se minimice el coste total de transporte, teniendo en cuenta que el coste unitario c
ij por ruta (coste en unidades monetarias por transportar una unidad
de producto desde "i" hasta "j" ), así como las siguientes restricciones de capacidad ( ai ,b
j 0):
Como quiera que un envío negativo carece de sentido, una restricción adicional
será:
2
Obj100
x = a i = x = b , ij
j=1
n
i , 1, 2 , . . . . . m ij j j = 1, 2 , . . . . . . ni=1
m
∑ ∑∀ ∀
x 0, ij i , j≥ ∀
Para que el sistema de restricciones resulte consistente (equilibrado), añadimos la
necesidad de que
Esta aparente restricción no es realmente limitativa desde un punto de vista
operativo, toda vez que puede conseguirse, en todo caso, mediante la inclusión de variables de holgura. O sea, si la oferta total excede a la demanda total, entonces se puede introducir un destino ficticio con demanda y , para i = 1,2,...m. O en el caso de que la demanda total fuese superior a oferta total, entonces se introduciría un origen ficticio con oferta y
, para
j = 1,2...n. Suponiendo el primer caso, o sea que la oferta total es igual a la demanda total,
El modelo de programación lineal para el problema de transporte es el siguiente:
Los vectores y la matriz de restricciones:
3
a = bi
i=1
m
j
j=1
n
∑ ∑
b = a - bn + 1 i
i=1
m
j
j=1
n
∑ ∑c =i , n + 1 0a = b - am + 1 j
j=1
n
i
i=1
m
∑ ∑c =m + 1, j 0
Obj108
Obj109
= .x x11 .. ..x1nx21 x2n xmn =( ;….. ; ;…. ;c c11 c1n c21 c2n…….. )cmn ;
= .b a1 .. ...amb1 bn =( ;……. ; …… ;……; …….. )A a11 a1n a21 a2n am1 amn
aij = e
i + e
m+j , i= 1,....m; j= 1,.....n
ei y e
m+j son vectores unitarios en un espacio Em+n con unos en la i-ésima y la (m+j)-ésima
posiciones, respectivamente. Nótese que ai es un escalar, mientras que a
ij es un vector
columna.
Luego el problema se puede poner como: :
Minimizar cx
Sujeta a: Ax = b x 0
La matriz A, con dimensión (m+n)mn, tiene la siguiente forma especial.
mn columnas
1 0 ........ 00 1 ........ 0
A=...
.
.
.m+n filas
0 0 ........ 1I I ........ I
donde 1 es un n-vector fila de componentes todas iguales a 1, e I una matriz identidad nn.
La matriz A es la que da al problema de transporte su estructura especial.
4
Se puede observar que cada elemento de la matriz A toma sólo el valor 1 ó 0, y además cada columna contiene dos elementos con valor 1 (uno correspondiente a la restricción de un origen y otro a la de un destino) y los restantes con valor 0. Va ser esta estructura especial la que va a permitir las propiedades que posteriormente se verán.
Considérese por ejemplo un problema de transporte con 2 orígenes , 3 destinos, y con los datos siguientes ( esta disposición se denomina "tabló de transporte en forma de matriz"):
Destino1 2 3 a
i
Origen 1 c11
= 2 c12
= 4 c13
= 3 302 c
21= 3 c
22= 1 c
23= 7 20
bj
10 15 25
La matriz de restricciones A es:
1 1 1 0 0 0
0 0 0 1 1 1
A= 1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
O bien: A = ( a11
,a12
,a13,
a21
,a22
,a23
)
Así por ejemplo, la primera columna de la matriz de A es a11
= e1 + e
m+1 en Em+n = E5
1
0a
11 = 1
5
0
0
PROPIEDADES:
a)Factibilidad.
Cuando la oferta se iguala a la demanda, el problema de transporte siempre tiene
una solución factible:
xij= a
ib
j /d i= 1,2,......m; j=1,2,.....n
Donde , y 0
xij
Mínimo ( a
i,b
j ).
Del ejemplo anterior , se obtiene la solución , x11
= 9; x12
= 6; x13
= 15; x21
= 6; x22
= 4 y x
23= 10; que es factible (aunque no básica).
La solución anterior indica que cualquier problema de transporte siempre tiene solución y además con valor objetivo finito. Lo que contrasta con otro tipo de problema lineal donde puede que no tenga solución o la solución pueda ser no acotada.
b)Enterabilidad.Como las restricciones de origen y de destino, tienen como coeficientes unos y si
las capacidades de oferta ai y de demanda bj son enteras, entonces las soluciones de las variables del sistema de ecuaciones serán siempre enteras.
PROPIEDADES DE LA MATRIZ A .
Se van a exponer algunas propiedades de la matriz A que dan al problema de transporte su estructura especial, que van a permitir una aplicación simple y eficiente del método simplex para el problema de transporte.
6
d = a = bi
i=1
m
j
j=1
n
∑ ∑
c)Rango de la matriz A.Supongase m≤n, y para m,n≥2 , entonces , rango A≤ mínimo (m+n,m.n)=m+n. Si
utilizamos el ejemplo anterior, la suma de las filas de origen y de destino, dan una fila de unos, lo que demuestra que el rango no es completo, es decir, rango A≤ m+n-1.
En el ejemplo la matriz A (m+n;m.n)= A(2+3,2.3)=A(5,6). Si se elige una base de rango m+n-1=2+3-1=4, por ejemplo: =( ; ; ; )= B a13 a23 a11 a12 1 0 1 10 1 0 0 0 0 1 00 0 0 11 1 0 0
Suprimiendo la última fila queda una matriz cuadrada que es triangular superior con determinante 1, es decir, las filas o las columnas son linealmente independientes entre si, luego el rango de A es igual m+n-1=2+3-1=4:
1 0 1 10 1 0 00 0 1 00 0 0 1
Conlusión : Rango A = m+n-1
d)Unimodulariadad total de la matriz A .
Se trata de la propiedad más importante que tiene la matriz de restricciones del problema de transporte, que el determinante de toda submatriz cuadrada de ella toma el valor de -1,0 ó +1.
e)Triangularidad de la matriz básica.
Tal como se ha elegido la base en el apartado c) es una matriz triangular superior (se podria conseguir una matriz triangular superior, tomando una matriz básica cualquiera de A, intercambiando filas y/o columnas).
El que una B se pueda poner como una matriz triangular, permite resolver el sistema básico Bx
B =b de forma sencilla mediante la reducción gausiana, es decir, multiplicando el
último vector fila de la matriz triangular por el vector de variables, obteniéndose el valor de la primera variable, si ahora se hace con la 2ª se obtiene el valor de la 2ª variable y asi
7
sucesivamente hacia atrás, quedando las últimas variables a resolver en función de las variables anteriores. Es decir.
a13 a23 a11 a12
1 0 1 1 x13 a1 300 1 0 0 x23 = a2 = 200 0 1 0 x11 b1 100 0 0 1 x12 b2 15
Es decir, primero, x12=15, segundo x11=10; tercero x23= 20, mientras que la 1ª queda x13+x11+x12=a1=30, y habrá que despejar x13 =30-x11-x12=30-10-15=5.
Sin embargo el hecho de que la matriz no sea de rango completo, no permite calcular por ejemplo el vector columna yij que contiene n+m componentes.
Si consideramos ahora la matriz seleccionada anteriormente pero sin eliminar la última fila y le añadimos una columna artificial de valor cero en todos los componentes y un 1 en la posición m+n, que representa el vector asociado a una variable artificial, la matriz asi contemplada es de rango completo, es decir, una matriz cuadrada de dimensión (m+n). Entonces el sistema anterior :
B.xB=ba
13a
23a
11a
12em+n b
1 0 1 1 0 x13 300 1 0 0 0 x23 200 0 1 0 0 x12 = 150 0 0 1 0 x11 101 1 0 0 1 ea 25
Permutando las filas y columnas de A' (o sea, colocando la última columna como la
primera, y luego como primera fila,la última fila anterior obtenida) se obtiene asi la siguiente matriz triangular superior:
xa
x13
x23
x11
x12
b1 1 1 0 0 250 1 0 1 1 30
A'= 0 0 1 0 0 200 0 0 1 0 150 0 0 0 1 10
8
Resolviendo este sistema triangular como se describió antes, se obtiene la solución básica:
x12
= 10x
11 = 15
x23
= 20x
13 = 30-x
11-x
12 = 30-15-10
= 5
xa = 25-x13
-x23
= 25-5-20 = 0
El mismo resultado anterior para las m+n-1 variables básicas, y además la variable artificial xa es nula (que siempre lo va a ser).
Con esta base de rango completo de m+n filas y columnas ya se puede calcular yij
que tiene m+n componentes (como se verá posteriormente).
f) Una base B es un arbol de mínima expansión.
El ejemplo anterior con m=2 orígenes y n=3 destinos, la base B tiene m+n-1=2+3-1=4 componentes básicas (y dos no básicas, el resto de variables), tal como se determinó anteriormente. Representando (el número en la celda indica que la celda es básica) en forma de matriz:
D1 2 3
O 1 10 15 52 20
Nota:observese que en la matriz la base tiene al menos una celda básica en cada fila y/o columna sin formar ciclos, luego es una cadena abierta.
O en forma de red (el arco saliente representa a la variable artificial que siempre vale 0)
1
1
9
15
5
2
2
xa=0
raiz
20
3
10
Una base B es un arbol de mínima expansión. En términos de redes, un árbol tiene ramas, es decir, no contiene ciclos, y además permite conectar todos los nodos utilizando el mínimo número de arcos. La base de rango completo es un árbol enraizado, aunque la raíz (indica la variable artificial) sólo se representa en la forma de red. En la forma de matriz se observa que es una cadena abierta como muestra los enlaces (en rojo) que unen las celdas básicas.
10
g) Vector yij. .Cálculo
…… xij ….…… zij-cij ….…… yij1
…… .…… yijk
…… .…… yijm+n
B—1 aij = yij , ó bien B y
ij = a
ij
es un sistema de ecuaciones donde las incognitas son las componetes de vector yij . Luego
para resolverlo se puede utilizar la regla de Cramer, donde el k-ésimo elemento desconocido de y
ij se obtiene por:
donde Bk se obtiene de B, reemplazando la k-ésima columna por a
ij . Luego B
k es una
submatriz de A ( al serlo B y aij ), y como A es totalmente unimodular, entonces detB
k = 1 ó
0. Como además det B = 1 (al ser una matriz triangular superior con unos en la diagonal):
yijk
= 1 ó 0.
Es decir, cada componente del vector columna yij es un 1 ó -1 ó 0 .
Al ser B una base, permite expresar cualquier vector no básico aij de forma única según la
combinación lineal aij =B y
ij , y al ser 1 ó 0 los valores de la combinación lineal, la relación
anterior permite obtener cualquier vector aij no básico mediante una suma y resta de
vectores básicos (lógicamente los escalares 0 no afectan), de ahi que se considere al vector y
ij como el vector de los coeficientes de representación de un vector no básico aij. Luego:
11
y det Bdet B
ijkk =
(1)aij= B y
ij
Además cualquier vector aij de la matriz A se puede poner como:
(2)aij = e
i + e
m
Por ejemplo un problema de transporte con m=8 orígenes y n=10 destinos, luego una base tendrá m+n-1=8+10-1=17 componentes básicas (supongamos la base siguiente):
1 2 3 4 5 6 7 8 9 101
a13
a14a11 a12
2a24
3a34
4 a45
a46 a47 a48 a49a44
5a59
6a69
7 a79 a710
8a810
12
Se trata efectivamente de una base al ser un árbol de mínima expansión. Si ahora se considera por ejemplo la celda no básica (7,1), entonces las celdas básicas con esta celda no básica si forman un ciclo al cerrarse la cadena:
1 2 3 4 5 6 7 8 9 101 +1 0 0
a13
-1 a14a11 a12
2 0a24
3 0a34
4 +1 0a45
0a46
0a47
0a48
-1a49a44
5 0a59
6 0a69
7 a71 +1a79
0a710
8 0a810
Si en el ciclo, las celdas básicas con dos enlaces (uno horizontal y otro vertical) se les asigna un coeficiente de representación +1 ó -1 y 0 en las que contienen un solo enlace (bien horizontal o bien vertical), comenzando con el primer doble enlace adjunto a la celda no básica con un coeficiente +1 y alternando con el siguiente doble enlace adjunto con un coeficiente -1, y asi sucesivamente, para terminar con +1. El resto de las celdas básicas con un solo tipo de enlace tanto dentro del ciclo como fuera se les asigna un coeficiente de representación 0.Con los coeficientes definidos gráficamente anteriormente, se puede representar el vector no básico según (1) como:
a71
= a79
-a49
+ a44
-a14
+a11
Ahora teniendo en cuenta la expresión (2) se va a comprobar que son ciertos los coeficientes de representación obtenidos según el procedimiento gráfico:
13
a71
= a79
-a49
+ a44
-a14
+a11
=( e7+e
8+9)- ( e
4+e
8+9)+ ( e
4+e
8+4)- ( e
1+e
8+4)+( e
1+e
8+1)= a
71
Luego, efectivamente la representación anterior es cierta y en definitiva, permite obtener los coeficientes de representación de forma gráfica en la matriz de transporte.
EL METODO SIMPLEX PARA PROBLEMAS DE TRANSPORTE.
Los pasos del método simplex de un programa lineal son los siguientes:PASO INICIAL:
Encontrar una solución básica inicial.PASO PRINCIPAL:
1.Calcular z
ij - c
ij para cada variable no básica.
-Si zks
- cks
=máximo( zij - c
ij )≤ 0, para ij no básicos, la solución básica actual
es óptima. En caso contrario, el paso 2.2. Entra en la base x
ks y sale x
βrl según la razón mínima.
Como los coeficientes de representación positivos elegidos para determinar la razón minima son unos, entonces el cociente es el menor valor de la celda básica con coeficiente +1:
Entra xks
=∆=minimo(valor de la celda básica con coeficiente de representación +1) y sale de la base x
rl .
El algoritmo simplex aplicado a un problema de transporte, tiene la particularidad respecto a cualquier otro tipo de problema lineal, que siempre va a tener una solución y además va a ser entera y el valor objetivo finito.
PASO INICIAL:
Determinación de una solución básica factible inicial
Se ha expuesto anteriormente que una base contiene m+n-1 componentes básicas, así como un procedimiento que permite obtenerla, y en consecuencia, una solución básica factible inicial.
Sin embargo se van a describir diferentes métodos que permiten lograr una solución básica factible inicial, aunque con diferente efectividad.
14
Ejemplo ilustrativo.Destino
1 2 3 ai
Origen 1 c11
= 2 c12
= 4 c13
= 3 302 c
21= 3 c
22= 1 c
23= 7 20
bj
10 15 25
Se van indicar algunos de los métodos que permiten obtener una solución básica factible inicial. En todos ellos se seleccionan celdas de asignación, según un criterio, y le damos a la variable el valor mínimo entre la capaciadad de oferta y de demanda, para luego descontar de dichas capacidades la cantidad asignada a la celda de asignación elegida. A continuación se elige una nueva celda de asignación, repiendo el proceso indicado, hasta que se consiga asignar todas las unidades de oferta disponibles.
a) Esquina Noroeste
Se trata de un método geométrico para poder obtener una solución básica factible inicial. No puede considerarse eficiente por cuanto no se apoya en criterio económico alguno. Únicamente presenta la ventaja de su sencillez.
La denominación se debe a que comienza los cálculos por la casilla situada en la esquina noroeste, y luego a la inmediada adjunta y asi sucesivamente, luego la 1ª celda de asignación, es la esquina superior izquierda, y de ahí su nombre. Como el mínimo (10,30) = 10 , se asigna a la celda (1,1) el valor 10, descontando a las capacidades la cantidad asignada, quedando como:
1 2 3 ai
1 2 4 3 2010
2 3 1 7 20
bj 15 25
A continuación se accede a la celda adjunta, en este caso a la celda (1,2), ya que la primera columna ya está saturada (se satisface la demanda). Luego la cantidad a asignar a la (1,2) es el mínimo(15,20)=15, y descontando la cantidad asignada, el cuadro queda como:
15
1 2 3 ai
1 2 4 3 510 15
2 3 1 7 20
bj 25
Ahora de la misma forma la celda de asignación es la (1,3) con x13=mínimo (25,5)=5.
1 2 3 ai
1 2 4 310 15 5
2 3 1 7 20
bj 20
Y por último, la celda de asignación es (2,3), con x23= mínimo(20,20)=20, quedando el cuadro de la siguiente forma.
1 2 3 ai
1 2 4 3 2510 15 5
2 3 1 7 2020
bj 10 15 25
Como se puede observar tanto la suma de cada fila como de cada columna da respectivamente las cantidades enviadas de cada fábrica y la recibida en cada almacén.Si se consideran métodos con un criterio económico (no gráfico como el de esquina noroeste), se selecciona como celda de asignación aquella que se ajusta al criterio, asignando a la celda seleccionada los valores tal como se hizo en el método anterior y descontando las capacidades asignadas.
b) Mínimo fila
16
Se comienza la asignación por la celda de la primera fila que tenga el coste más bajo. En el caso de que el mínimo se presente en varias celdas (rutas), se puede seleccionar cualquiera del empate. La siguiente es eligiendo las celdas restantes de la primera fila, hasta que se sature toda la fila, luego se hace lo mismo con la 2ª fila, y así con las siguientes, hasta saturar todas las filas (al repartir toda la oferta).Así la 1ª celda de asignación es la (1,1) por ser la de la 1ª fila que menor coste tiene, luego x11=mínimo(15,30)=15, quedando:
1 2 3 ai
1 2 4 3 2010
2 3 1 7 20
bj 15 25
Se continua con la 1ª fila ya que aún no está saturada, se selecciona la celda de asignación (1,3), o sea x13=mínimo(25,20)=20, quedando:
1 2 3 ai
1 2 4 310 20
2 3 1 7 20
bj 15 5
Al saturarse la 1ª fila, se selecciona ahora la 2ª fila y la celda de asignación es (2,2), donde x22=mínimo(15,20) = 15, quedando:
1 2 3 ai
1 2 4 310 20
2 3 1 7 515
bj 5
Y por último la celda de asignación (2,3), donde x23=mínimo(5,5)=5.1 2 3 ai
17
1 2 4 3 2510 20
2 3 1 7 2015 5
bj 10 15 25
c) Mínimo columna
El criterio es similar al anterior (ahora con columnas), comenzando por la 1ª columna.
La 1ª celda de asignación es (1,1), donde x11=mínimo (10,30)=10.
1 2 3 ai
1 2 4 3 2010
2 3 1 7 20
bj 15 25
Luego la 2ª columna al saturarse la 1ª, donde la celda de asignación es (2,2) y x22=
mímimo(15,20)=15.
1 2 3 ai
1 2 4 3 2010
2 3 1 7 515
bj 25
18
Saturada la 2ª columna, se pasa a la 3ª columna, donde se selecciona (1,3), x13=mínimo
(25,20)= 20.
1 2 3 ai
1 2 4 310 20
2 3 1 7 515
bj 5
Quedando por último la celda (2,3), con x23=mínimo(5,5)=5.1 2 3 ai
1 2 4 3 3010 20
2 3 1 7 2015 5
bj 10 15 25
d) Mínimo matriz
Este método opera igual que los anteriores, pero considerando como 1ª celda de asignación el mínimo c
ij de la matriz, y las celdas de asignación sucesivas seleccionando
las submatrices restantes después de ir saturando las celdas seleccionadas, hasta que se asigne toda la oferta.
1 2 3 ai
1 2 4 3 30
19
2 3 1 7 515
bj 10 25
1 2 3 ai
1 2 4 3 2010
2 3 1 7 515
bj 25
1 2 3 ai
1 2 4 310 20
2 3 1 7 515
bj 5
1 2 3 ai
1 2 4 3 3010 20
2 3 1 7 2015 5
bj 10 15 25
PASO PRINCIPAL:
1. Cálculo de zij -c
ij para cada variable no básica.
Una vez obtenida la solución básica inicial, hay que determinar si es la solución óptima. Para ello se realizará en las variables “no básicas”, el cálculo siguiente:
20
zij - c
ij = c
B B-1a
ij= wa
ij - c
ij
Como w= cB B-1 , y al ser w la variable del problema dual, se le denomina el método de la
variable dual.Si se considera como primal el problema de transporte que tiene m restricciones de origen y n restricciones de destino, luego el problema dual tendrá m+n variables duales; a las primeras m variables se denominan por u1…ui…..um, mientras a las n restantes por v1…vj….vn, es decir, w=( u1…ui…..um, v1…vj….vn). Además al ser las restricciones del primal en igualdad entonces todas las variables del dual son “no restringidas” .
zij - c
ij = wa
ij - c
ij =( u1…ui…..um, v1…vj….vn)aij-cij=(ui+vj)-cij
Luego: zij=(ui-vj)
Como el vector aij es un vector columna de m+n componentes con 1 en la posición i y un 1 en la posición m+j y el resto ceros, de ahí que el producto de wa
ij sea la suma de
ui+vj, es decir el valor de zij. Al método se le denomina de la variable dual (ui,vj) (al final del archivo se puede ver el Primal y el Dual de Transporte, más ampliamente).
Falta por calcular los valores de las variables duales ui, vj, para ∀ ij. Si se tiene una base B, entonces:
w = cB B-1
o bien wB=cB
dondew = (u
1 ,u
2 ,...,u
m , v
1 , v
2 ,...,v
n)
B = (apq
,....,ast ,
e
m+n)
cB = (c
pq ,....,c
st ,
c
a)
apq
,....,ast son m+n-1 columnas básicas, pero como la base tiene que ser de rango
completo (al ser m+n el nº de variables duales), hay que añadir el vector columna em+n, que
21
tiene un 1 en la posición m+n y el resto ceros, lo mismo al vector de m+n-1 costos unitarios c
pq ,....,c
st hay que añadir el coste de la variable artificial ca . Además como el valor de la
variable artificial es siempre xa=0, y el coste por utilizar la varible artificial es caxa=0, luego el coste unitario de la variable artificial puede ser cualquiera, y por conveniencia se toma ca=0 para operar con valores pequeños.
En resumen :
wB = cB=( u1 ,u
2 ,...,u
m , v
1 , v
2 ,...,v
n )( a
pq ,....,a
st ,
e
m+n ) = ( c
pq ,....,c
st ,
0)
y como aij = e
i + e
m+j , es un m+n vector columna con unos en las i-ésima y m+j-ésima
posiciones, respectivamente, y ceros en las restantes posiciones. Luego resulta el sistema de determinado con m+n ecuaciones y m+n variables :
up + v
q = c
pq
.
.u
s + v
t = c
st v
n = 0
La variable vn
= 0 (siempre, al ser ca). Operando sobre celdas básicas, partiendo de vn=0, se obtienen los restantes valores de las ui y vj., y en definitiva, se puede calcular:z
ij - c
ij = u
i + v
j - c
ij correspondientes a las celdas no básicas.
Resumiendo:
-Cálculo de ui y vj sobre celdas básicas: ui + v
j = c
ij
cij
uj
vj
-Mientras sobre celdas no básicas: zij - c
ij = (ui+vj)-cij
22
cij
uj
vj
Considerese la solución básica factible inicial obtenida del ejemplo según el método Esquina Noroeste..
1 2 3 ui
1 2 4 3 310 15 5
2 3 1 7 720
vj -1 1 0
Sobre celdas básicas : vi+vj= cij
partiendo de vn=v3= 0, se obtienen los restantes valores de ui y vj de la tabla anterior (color rojo), y a continuación sobre celdas “no básicas”, los costes reducidos z
ij – c
ij= (u
i + v
j) –
cij
(en colo verde):
1 2 3 ui
1 2 4 3 310 15 5
2 3 1 7 73 7 20
vj -1 1 0
Es decir:z
21 – c
21 = ( u
2 + v
1 ) – c
21 = ( 7 -1 ) - 3 = 3
z22
– c22
= ( u2 + v
2 ) – c
22 = ( 7 + 1 ) - 1 =7
Como zks
– cks
= min(zij – c
ij ) = z
22 – c
22 = 7 ≥ 0
La solución actual no es óptima. Luego el paso 2.
23
2. Determinación de la columna que sale.
Una vez seleccionada la variable xkl
= x22
para entrar a la base, hay que seleccionar que variable que va a salir. Saldrá la que cumpla la razón mínima.
Pero antes hay que determinar los coeficientes de representación y22
para el vector no básico a
22 . Para ello hay que determinar primero el ciclo que forma la base actual con el
vector no básico a22
correspondiente a la variable anterior como en el cuadro siguiente:
1 2 31 2 0 4 +
13 -1
10 15 52 3 1 7 +1
a22 20
A continuación determinamos el valor ∆ de la variable que va entrar y la variable que sale de la base según la razón mínima:x
ks=∆=minimo ; > , = = xijyij yij 0 como yij 1 xij con
+ = = ( , )=coeficiente 1 x12 min 15 20 15
Entonces sale de la base x12 y entra x22. Como el flujo en la red no puede aumentar ni disminuir (unidades que circulan por la red), luego si por la ruta (1,2) circulaban 15 unidades, y ahora lo hacen por la ruta (2,2), en el ciclo habrá que aumentar un flujo de ∆=15 en los arcos de las variables con coeficiente -1 y disminuir en los arcos con coeficiente +1, tal como muestra la siguiente matriz.
1 2 31 2 4 3
10 15-15 5+152 3 1 7
15 20-15
Habrá que comprobar que la solución actual es óptima (operar del mismo modo que antes).
1 2 3 ui
24
1 2 4 3 310 -7 20
2 3 1 7 73 15 5
vj -1 -6 0
Como zks
– cks
= min(zij – c
ij ) = z
21 – c
21 = 3 >0. La solución no es óptima. Luego entra
en la base x21 y habrá que determinar el ciclo asociado al vector no básico a21. Para ello:
1 2 3 ui
1 2 +1 4 3 -110 20
2 3 1 0 7 +1a21 15 5
vj
x21
=∆=minimo ; > , = = + = =xijyij yij 0 como yij 1 xij con coeficiente 1 x23 5Sale de la base x23 y entra x21 , el cuadro queda como:
1 2 3 ui
1 2 4 3 35 -4 25
2 3 1 7 45 15 -3
vj -1 -3 0
Como zks
– cks
= min(zij – c
ij ) = z
23 – c
23 = -3 <0. La solución es óptima y además única
al ser menor que 0.
x*= = = = =x11 5x13 25x21 5x22 15 ; z*=2*5+3*25+3*5+1*15=115 u.m.
25
EL PROBLEMA DE ASIGNACION.
Cuando el problema de transporte tiene m=n y ai= b
j= 1, se llama "el problema de
asignación". Por ejemplo, supóngase que hay m individuos y n trabajos. Si asignar el individuo i al trabajo j da lugar a un coste cij. Entonces se trata de asignar los individuos a los trabios de la forma más económica. Cada solución básica factible x
ij = 1 significa que el
individuo i ha sido asignado al trabajo j, y xij = 0 significa que el individuo i no está
asignado al trabajo j.Si se plantea el problema de asignación como un problema de transporte, resulta:
El número de variables básicas (al ser m= n) es m+m-1 = 2m-1. Como en cada una
de las restriccciones, tanto de origen como destino; ai= 1 = b
j= 1, con x
ij = 1 ó x
ij = 0, y al
ser la suma de variables de cada fila y/o columna igual 1, entonces sólo una de las variables vale 1 y el resto 0 en cada restricción, luego sólo es posible que de las 2m-1 variables básicas, m sean positivas, mientras que las restantes variables básicas son nulas, es decir m-1 ( 2m-1-m = m-1) variables. Si se utiliza el algoritmo de transporte para resolver el problema de asignación, al tener una solución básica con m-1 de sus componentes nulas, se trataría de un problema altamente degenerado. En consecuencia, teniendo en cuenta la estructura especial del problema de asignación, se puede obtener un algoritmo más eficiente, como se va a ver a continuación.
Considerese ahora al problema dual del problema de asignación, es decir:
PROBLEMA PRIMAL
Minimizar cx
Sujeta a: Ax = 1x 0
PROBLEMA DUAL
26
Minimizar z = c .x
Sujeto a x = 1
x = 1
x 1 ó 0 ,
i=1
m
ij
j=1
m
ij
ij
i=1
m
ij
j=1
m
ij i , j = 1, . . . , m
∑ ∑
∑
∑=
Teniendo en cuenta las condiciones de Khun-Tucker, una solución primal x es óptima si es factible, si existen variables duales u, v (no restringidas al ser las restricciones en igualdad en el primal) factibles, y que cumplan la condición de holgura complementaria, es decir:
( cij - u
i - v
j ) x
ij = 0; i, j = 1,....m
Por lo tanto, si se puede encontrar un conjunto de variables u, v y x factibles que
satisfagan la holgura complementaria, entonces u, v y x son óptimas.La elección de variables u,v deben de cumplir para todo i,j=1…m: u i+vj≤ cij, para
que sean factibles, es decir, la suma de ui y de vj no debe ser mayor que el coste unitario cij
de la variable xij, luego en la matriz de costes unitarios de las variables primales, si se eligen:
cij ; i = 1,.....m
cij - ; j = 1,.....m
es el mínimo cij de la fila i, y es el mínimo c
ij - de la columna j.
Como se cumplen las restricciones duales, entonces la solución es factible dual.
La matriz de asignación reducida
27
max. z = u + v
u + v c , u v no restrigidas
i
i=1
m
j
j=1
n
i j ij i , j = 1, . . . m
i, j ; i, j = 1, . . m
∑ ∑
≤
Obj115
Obj116Obj117
Obj118Obj119Obj120
Obj121Obj122Obj123Obj124
Consideremos ahora, una matriz de coeficientes de costos reducidos, en donde cij se
reemplaza por (cij - u
i - v
j). Es decir, la matriz de costos reducidos se obtiene restando
primero en cada fila el mínimo de en esa fila (o sea ); y después , sobre la matriz resultante, se resta de cada columna el mínimo de esa columna (o sea ). Por lo tanto, la matriz resultante tendrá un cero en todas las filas y en todas las columnas y todos sus elementos serán no negativos. En realidad, la matriz reducida es la matriz de las variables de holgura duales, ya que (c
ij - u
i - v
j), es decir, el valor de cada una de las variables de holgura duales
para conseguir que las desigualdades correspondientes a las restricciones duales se conviertan en igualdades.
Tal como se ha analizado anteriormente, el número de variables básicas con valor 1 es m, uno por cada fila y por cada columna, y teniendo en cuenta la condición de la holgura complementaria, para que la variable xij tenga valor 1 sólo es posible si la holgura correspondiente en el problema dual es nula:
( cij - u
i - v
j ) x
ij = 0; si x
ij = 1 0; ( c
ij - u
i - v
j ) = 0, es decir 0
Por lo tanto una solución se puede encontrar si en todos las filas y en todas las columnas de la matriz de costes reducidos existen ceros de forma que sólo una variable primal correspondiente xij tome valor 1 en cada fila y en cada columna.
Considérese el siguiente ejemplo para ilustrar los conceptos anteriores. Sea la siguiente matriz de coeficientes de costo para un problema de asignación:
1 2 3 4 MINIMO FILA1 3 2 5 4 22 0 1 2 3 03 4 1 -1 3 -14 2 5 3 4 2
28
Obj125
Obj126
Restando a cada elemento de cada fila el mínimo en esa fila, se obtiene el siguiente tabló:
1 2 3 41 1 0 3 2 2 0 1 2 3 3 5 2 0 4 4 0 3 1 2
0 0 0 2 MINIMO COLUMNA
Restando ahora el mínimo de cada columna en la nueva matriz a cada elemento a cada elemento en la columna, se obtiene la matriz reducida siguiente:
1 2 3 4
1 1 0 3 0
2 0 1 2 1
( =)
3 5 2 0 2
4 0 3 1 0
29
Obj127
Ahora, si se toma x*12
= x*21
= x*33
= x*44
= 1 y se toman los restantes x*ij = 0, se
tienen entonces una solución factible con los xij positivos asociados a celdas con ceros en la
matriz reducida, produciendo así una solución óptima. No siempre es fácil encontrar una solución óptima. Por ejemplo, la siguiente matriz
de costos:
1 2 31 2 5 72 4 2 1 ( = c
ij )
3 2 6 5
La matriz reducida está dada por:
1 2 31 0 2 52 3 0 0
( = )3 0 3 3
Aquí no es posible tomar tres xij iguales a 1 de tal forma que todos los tres x
ij positivos ocurran en celdas cero y que no ocurran dos x
ij en la misma fila ó columna.
En la matriz reducida anterior, el número máximo de las xij que ocurren en las
celdas cero, que se pueden igualar a 1 sin que dos de los xij positivos ocurran en la misma
fila o columna es 2. Por ejemplo, podría tomarse x11
= x22
= 1, x11
= x23
= 1, x22
= x31
= 1, ó x
31 = x
23 = 1. En este caso, el máximo número de celdas con cero tales que dos de
estas celdas no están en la misma fila o columna es 2. Las celdas correspondientes se llaman independientes. Nótese también que si trazara un conjunto de lineas sobre las filas y columnas para cubrir los ceros de tal manera que hay al menos una linea sobre cada cero,
30
Obj128
Obj129
entonces el número mínimo de tales líneas para esta matriz es 2, a saber, una línea sobre la columna 1 y una línea sobre la fila 2.
1 2 31 0 2 52 3 0 03 0 3 3
Se ve en este ejemplo que el número máximo de celdas cero independientes y el número mínimo de líneas requeridas para cubrir los ceros son iguales. Este resultado, el cual es cierto en general, está dado por el teorema siguiente ( que se dá sin demostración):
Teorema.
"El número máximo de celdas cero independientes en una matriz de asignación reducida es igual al mínimo número de líneas que cubren todos los ceros en la matriz."
Modificación de la matriz reducida.
Como aún no se ha obtenido la solución óptima del problema anterior, es decir, no se puede encontrar un conjunto factible de las x
ij positivos de entre las celdas cero de la
matriz reducida. Entonces hay que modificar la matriz de costes reducidos. Para ello, se considera la matriz cubierta, es decir, la matriz reducida con los ceros cubiertos por el menor número de líneas. A continuación se elige el menor de los valores de la matriz de costes reducidos no cubiertos y se le resta a todos los elementos no cubiertos mientras se suma sólo a los elementos cubiertos que estén en el cruce de líneas, y de nuevo se vuelven a trazar el menor número de líneas que cubran los ceros para ver si ahora dicho número coincide con el de m orígenes ( o destinos), en caso contrario hay que modificar de nuevo la matriz anterior de la misma forma , para que cuando el número de líneas coincida con m orígenes, ya podrá obtenerse la solución óptima que cumpla la condición de holgura complementaria.
31
1 2 3
1 0 0 3 2 5 0 0
3 0 1 1
Obsérvese que ahora existe un conjunto factible de varias xij con los x
ij positivos
asociados con las celdas cero ( variables de holgura duales cero ).Como se puede observar, se alcanza la factibilidad primal, y la factibilidad dual se
mantiene (pues los elementos en la matriz reducida de costos son nonegativos), y finalmente, se cumple la holgura complementaria (pues x
ij = 1 sólo si la variable dual
correspondiente es cero). Por lo tanto, se cumplen las condiciones de Kuhn-Tucker y se cuenta con la solución óptima x*
12 = x*
23 = x*
31 = 1 ( todas las otras x*
ij son iguales a cero).
Resumiendo, el problema de asignación que es un caso particular del problema de transporte, se trata entonces de un problema lineal, y que como tal podría ser resuelto por el método simplex , pero como se analizó anteriormente, no era muy conveniente, al existir el algoritmo simplex para problemas de transporte que es más eficiente. Sin embargo, el problema de asignación considerado como un problema de transporte, al ser altamente degenerado, tampoco es muy conveniente aplicarle el citado algoritmo de transporte. Entonces, como se ha analizado, debido a la estructura especial del problema de asignación, se utilizará el algorítmo siguiente, denominado el "método ó algoritmo hungaro", que resume, de una forma sencilla,los pasos seguidos anteriormente. El algoritmo es debido a Kuhn.
Método (algoritmo) hungaro o algoritmo de asignación.
Este sencillo algoritmo consta de los pasos siguientes:
PASO INICIAL
32
Para cada fila de la matriz de costos, se resta el mínimo de sus elementos a cada elemento en esa fila. Para cada columna de la matriz resultante, se resta ahora a cada elemento en esa columna el mínimo de sus elementos. El resultado es una matriz reducida.
PASO PRINCIPAL
1. Se traza el mínimo número de líneas sobre las filas y las columnas para cubrir todos los ceros en la matriz reducida. Si el mínimo número de líneas es m, se dispone entonces de una solución óptima. En caso contrario, se sigue el paso 2.
2. Se selecciona el mínimo elemento no cubierto. Se resta este elemento a cada elemento no cubierto y se suma a cada elemento cubierto por dos líneas. Se regresa al paso 1.
Ejemplo de aplicación:
Considérese la siguiente matriz de costos.
1 2 3 4 51 2 3 5 1 42 -1 1 3 6 23 -2 4 3 5 04 1 3 4 1 45 7 1 2 1 2
La matriz reducida con el mínimo número de líneas que cubre los 0
1 2 3 4 51 1 2 3 0 22 0 2 3 7 23 0 6 4 7 14 0 2 2 0 25 6 0 0 0 0
33
Como se puede obsevar el mínimo número de líneas que cubren todo los ceros es 3. Al ser 3 m = 5, se busca el mínimo elemento no cubierto de la matriz anterior y es 1. Entonces se resta 1 de cada elemento no cubierto y se suma a cada elemento cubierto dos veces ( el elemento del cruce de las dos lineas ), y se obtiene la siguiente matriz reducida, donde se traza el mínimo número de líneas para cubrir todos los ceros:
1 2 3 4 51 1 1 2 0 12 0 1 2 7 13 0 5 3 7 04 0 1 1 0 15 7 0 0 1 0
De nuevo se observa que la solución no es la óptima ya que el mínimo número de líneas es 4. Se busca entonces el mínimo elemento no cubierte de esta matriz reducida que es 1, el cuál se resta como siempre de cada elemento no cubierto y se suma a cada elemento cubierto dos veces, resultando la siguiente matriz reducida, que si ya contiene cinco líneas para cubrir todos los ceros:
1 2 3 4 5
1 1 0 1 0 1
2 0 0 1 7 1
3 0 4 2 7 0
4 0 0 0 0 1
5 8 0 0 2 1
34
Luego en esta matriz una solución óptima está dada por x*14
= x*21
= x*35
= x*42
=
x*53
= 1 y todas las otras x*ij son iguales a cero, es decir se cumplen la condiciones de
Kuhn-Tucher. Otras soluciones alternativas, pueden ser x*14
= x*21
= x*35
= x*43
= x*52
= 1 ó
x*12
= x*21
= x*35
= x*42
= x*53
= 1, en todas ellas el valor objetivo es z*=5 u.m.
VARIACIONES EN UN PROBLEMA DE TRANSPORTE.
Se ha visto la formulación y resolución de un problema de transporte como el plan de distribución más económico de un producto entre unos orígenes y unos destinos teniendo en cuenta los costes unitarios de transportar una unidad desde cada origen a cada destino y, las ofertas y demandas de los citados orígenes y destinos. Tal plan económico se lograba minimizando el coste total incurrido en trasladar las unidades de los orígenes a los destinos, es decir:
Además, para que el problema tenga solución es necesario que esté equilibrado (que la oferta total sea igual a la demanda total), y en caso contrario se equilibraba tal como se indicó anteriormente, para lograr la factibilidad. También se supuso que existen todas las rutas entre cada origen y cada destino, y además el coste de producción de cada unidad es el mismo para todos los orígenes, así como también que el precio de venta de cada unidad también es el mismo para todos los destinos, y por último, se supuso que el flujo en cada ruta (i,j) era ilimitado, es decir, xij ≥ 0.
Sin embargo, se van a contemplar variaciones en el problema anteriormente enunciado y como se incorporan al problema de transporte.
A). Rutas prohibidas.
35
Obj130
Cuando no es posible realizar un envio desde un origen a un destino determinado, entonces la ruta (o rutas si existieran más de una) deben de prohibirse, es decir, en la solución óptima su flujo (valor de la variable xij ) es cero. Por ejemplo, si la distribución se realiza por ferrocarril y no existe una vía que comunique un nodo origen con un destino , o por ejemplo, cuando el transporte se realiza por carretera, y en el periodo que se está estudiando la carretera está cortada por obras, etc.¿ Cómo se pueden contemplar situaciones que contienen una o más rutas prohibidas para obtener soluciones?.Existen dos procedimientos para lograrlo:
1.Hacer que el costo unitario de transporte de la ruta prohibida sea muy grande
comparado con el valor de las restantes rutas. Se toma el valor M, lo que va a provocar que al ser una ruta muy cara, el algoritmo no seleccione esta ruta para enviar alguna cantidad del producto.
2.Asignar una capacidad cero a la ruta prohibida y cualquier coste unitario a esa
ruta.
La ventaja del primer procedimiento es que el problema se puede resolver por el algoritmo de transporte expuesto, aunque puede tener la desventaja cuando se resuelve mediante el ordenador, ya que el programa asigna un valor antes de resolverlo, y entonces si el valor asignado a M no es muy grande, podría dar una solución con el paso de alguna unidad por la ruta prohibida, mientras que si el valor de M es muy grande podría dar problemas al ordenador. Sin embargo, normalmente no suele dar problemas con poner M.
La ventaja del 2º procedimiento es que es irrelevante el valor del coste unitario de la ruta prohibida, aunque en este caso habría que utilizar el algoritmo del problema de flujo con costo mínimo, por ser el problema de transporte un caso particular de este.
B). Costes de producción desiguales.
Los costes unitarios de producción son diferentes en cada planta de producción i.En este caso lo que se hace, es considerar como costes unitarios de cada ruta la suma del coste de cada unidad producida en la planta (origen) i y el coste de transportar cada unidad el origen i a cada destino j.
cij = ( coste de producción de una unidad en el origen i)+ (coste de envio de una unidad del origen i al destino j)
36
Luego al problema de transporte original (con costes unitarios de envío) se le suman los costes unitarios de producción, es decir, en la matriz de costes unitarios de distribución se le suma a cada fila el coste unitario de producción del origen (el que está en la misma fila), y se resuelve tal como se hizo para el caso con sólo costes unitarios de transporte.
En el caso de que la oferta total sea superior a la demanda total y que los costes unitarios de producción sean diferentes, para poder resolverlo se añadiría un nodo destino ficticio con demanda, la diferencia entre la oferta total y la demanda total, y arcos entre todos los orígenes y el destino ficticio, con costes unitarios cero (para ser un problema equilibrado), y luego como costes unitarios en los restantes arcos la suma de los costes unitarios de transporte y de los de producción (tal como se comentó anteriormente). Si en esta situación se pretende realizar una programación de la producción y distribución de un determinado producto entre unas plantas de producción y unos destinos, la solución óptima nos dará en las variables de holgura ( variables de los arcos entre las plantas y el destino ficticio) las cantidades del producto que no se van a producir en la respectiva planta de producción. Luego las capacidades de las plantas de producción que se dan antes de resolver el problema representan capacidades máximas de cada planta, y que lógicamente sólo se debe de producir en cada planta una cantidad igual a la diferencia entre de la capacidad máxima de ella y la cantidad de la variable de holgura de esa planta al destino ficticio, ya que el valor de las variables de holgura no va a ser absorbida. Intuitivamente se sabe que primero se absorberá la producción procedente de las plantas que tienen un coste unitario de producción más bajo. Sin embargo, en el caso de que se ponga restricciones sobre la mínima producción en cada planta para que la producción en la misma sea rentable (situación bastante normal si se tiene en cuenta que para realizar una determinada producción hay que tener en cuenta costes fijos, de preparación, etc, antes de obtener una unidad, y que a medida de que el número de unidades sea mayor el citado coste fijo se repartirá entre las unidades obtenidas) , entonces la situación puede cambiar, como se verá posteriormente, cuando existe un límite inferior para capacidad productiva, es decir, cuando la producción en una planta no puede ser inferior a una cantidad determinada.
C). Precios de venta desiguales.
Si cada unidad del producto tiene un precio de venta diferente en cada destino, entonces en cada ruta se establece ahora sobre cada arco (i,j), como coeficiente unitario, la diferencia entre precio de venta de cada unidad en el destino j y el costo unitario de distribución(transporte) del origen i al destino j ( en el supuesto de que también los costes unitarios de producción fueran diferentes, habría que restar también el coste unitario de producción del origen i).
37
Ahora el citado coeficiente unitario representa una ganancia unitaria, es decir, la ganancia de cada unidad distribuida entre el origen i y el destino j.
Luego con esta transformación , la solución se encontraría MAXIMIZANDO la función objetivo, es decir, el problema sería ahora:
Donde los gij son ganancias unitarias, y el problema trata entonces de obtener el máximo beneficio (recordar que antes al ser costes, era MINIMIZAR)
En el caso de que la demanda total sea mayor que la oferta total y que los precios de venta sean desiguales, la oferta total se a distribuir (supone que se utiliza la capacidad máxima de producción de cada planta) y, además se puede intuir que será satisfecha la primero demanda en los destinos con mayor precio de venta para el producto, mientras que en el de menor precio no va a ser satisfecha parcial o totalmente. Para encontrar la solución del problema habrá que equilibrarlo primero, es decir, estableciendo un origen ficticio, con capacidad productiva la diferencia entre la demanda total y la oferta total, con arcos (variables de holgura) entre el origen ficticio y cada destino, con costes nulos, y en el resto de los arcos asignando las ganancias unitarias (diferencia entre el precio de venta y el coste unitario de distribución del origen i al destino j, y el coste unitario de producción si este fuese diferente al de otras plantas). En la solución óptima, los valores de las variables de holgura ( correspondientes a los arcos entre el origen ficticio y los destinos) representan la demanda insatisfecha en cada destino. Sin embargo, si se imponen restricciones de que algún destino tiene que satisfacerse al menos con una cantidad determinada, la situación cambia lógicamente, al imponer las esas restricciones, y el beneficio será inferior a la situación anterior. Este caso lo trataremos posteriormente.NOTA: El problema de transporte donde se maximiza la función objetivo se resuelve de la misma forma que se hace cuando se emplea el método simplex general, es decir, transformando la función objetivo en forma de minimizar. O sea el problema anterior quedaría como:
38
Obj131
Obj132
Obj133
Es decir se obtimizará
Luego lo que se hace en el tabló de transporte es simplemente cambiar de signo los coeficientes unitarios ( ganancias unitarias), operar de la misma forma ya conocida, y en la solución óptima lo único que hay que hacer es cambiar de signo el valor objetivo alcanzado en el tabló óptimo, o lo que es lo mismo, D). Capacidad máxima y mínima de un arco.
Hasta ahora se ha considerado que el flujo de un arco era ilimitada, es decir, x ij ≥ 0 . Sin embargo, el flujo en un arco ( unidades desde el origen i al destino j) puede estar acotado superiormente, inferiormente ( para un valor mayor a 0 ), es decir, x ij ≤ uij ; o xij ≥ lij ; o bien o lij ≤ xij ≤ uij . En estos casos se pueden utilizar cambios de variables, aunque la forma de resolverlo es más eficiente utilizando el algoritmo del problema de flujo con costo mínimo, para variables acotadas, por ser el problema de transporte un caso particular del anterior.
Vamos a ver como se hace para el caso de que el arco esté acotado inferiormente.Sea:
xij ≥ lij ; entonces: xij - xij´ = lij ; o sea xij = xij
´ + lij ; donde xij´ ≥ 0 ;
Si ahora sustituimos la variable xij por xij´ + lij , y pasamos el valor de lij al lado
derecho de la restricción del origen i , la capacidad se ve disminuida en una cantidad lij , es decir, pasa a tomar como capacidad reducida, el valor de ai
- lij . Realizando la misma operación en la restricción del destino j, la capacidad de demanda del destino j, también se ve disminuida en la cantidad lij , es decir, pasa a tomar una demanda reducida, bj
- lij .En resumen, cuando un arco está acotado inferiormente, se resta la cota inferior a la capacidad de oferta y a la capacidad de demanda, y se resuelve el problema con estas capacidades reducidas; y el valor de la variable del arco (i,j) es en realidad el valor de x ij
´ , con lo cuál el valor buscado de xij = xij
´ + lij. Para las restantes variables, el valor obtenido es el que les corresponde, es decir, sólo para aquellas que se hizo el cambio de variables, hay volver a deshacer el cambio para que nos dé el valor real.
En el caso de que se quiera que el valor de una ruta sea un valor determinado, por ejemplo p, se hace el cambio xij = xij
´ + p, donde la variable de holgura es x ij´ =0, con
sustituyendo el valor de la variable en las restricciones donde figura, y pasándolo al lado derecho, restaría a la capacidad del origen i la cantidad p, así como en el nodo destino j, también se restaría p, y a continuación se hace que el coste de la citada variable sea igual a M, para provocar que el valor optimo xij
´ sea 0 . Luego en la solución óptima se deshace el
39
Obj134
cambio de xij´ por xij = xij
´ + p= 0+p=p (nótese que xij´ =0, ya que después de calcular las
capacidades reducidas al incluir la variable xij´ , se impone el valor M como coste unitario
para impedir que la misma tenga un valor positivo, con lo cual en la solución óptima, la variable tendrá el valor p. valor que fue descontado anteriormente).
E). Limites inferiores en las ofertas y/o demandas.
Recordar la situación donde los costes unitarios de producción eran desiguales, la oferta total es mayor que la demanda total y se exige que exista una capacidad mínima de oferta. Al existir mayor oferta que demanda y ser los costes unitarios de producción desiguales, recordar que los destinos satisfarían su demanda mientras fuera posible de los orígenes donde el producto es más barato, lógicamente, pudiendo ocurrir que la producción de algún/os origen/es fuese inferior a la cantidad rentable (recordar los costes fijos y variables). Evidentemente, es conveniente no producir por debajo del citado limite.
Para resolver el problema, habrá que equilibrarlo primero, es decir, colocando un nodo destino ficticio para absorber el excedente de producción, con arcos desde todos los orígenes al nodo destino con costes unitarios 0, y en el resto la suma de los costes unitarios de distribución y de los costes unitarios de producción. Ahora al establecer los límites mínimos de producción de cada origen, y calculando las diferencias entre las capacidades máximas de cada origen y las citadas cotas mínimas de producción, nos darían las cantidades máximas de excedentes que estarían en los arcos de cada origen al citado destino ficticio. Es decir, serían los flujos máximos permitidos por citados arcos desde el origen al destino ficticio. Estaríamos en el caso del flujo máximo permitido en un arco, y se utilizaría el algoritmo de flujo con costo mínimo.
En el caso de que la demanda total fuese mayor que la oferta total, los precios de venta desiguales, y que la demanda en cada destino tuviese que ser satisfecha al menos en una cierta cantidad, es decir, la demanda tiene un límite inferior (cota mínima). La situación sería similar al procedimiento visto anteriormente. Se equilibraría el problema, colocando un nodo origen ficticio, con capacidad igual a la diferencia entre la demanda total y la oferta total, y arcos entre el origen ficticio y cada destino, con costes 0, y asignando capacidades máximas a los citados arcos ficticios por la diferencia entre la demanda total de cada destino y el límite mínimo de demanda en cada destino (cantidad mínima que debe ser enviada).
40
NOTA: En clase se realizaran ejercicios que contemplen las situaciones anteriores, así como la utilización del modelo de transporte en aplicaciones en donde sin ser un problema de transporte, sin embargo, puede plantearse como tal y lógicamente resolverlo fácilmente.
Apendice: PROBLEMA PRIMAL
PROBLEMA DUAL
41
Minimizar z = c .x
Sujeto a x = b
x = a
a = b x 0 ,
i=1
m
ij
j=1
n
ij
ij
i=1
m
j
ij
j=1
n
i
i
i=1
m
j
j=1
n
ij i , j
∑ ∑
∑
∑
∑ ∑ ≥ ∀
Obj136
