domingo, 5 de junio de 2011

transporte

MODELO DE TRANSPORTE

DEFINICIÓN Y APLICACIÓN DEL MODELO DE TRANSPORTE

El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son:

1.      Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.
2.      El costo de transporte unitario de la mercancía a cada destino.

Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total.

La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al numero de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte.








 

El esquema siguiente representa el modelo de transporte como una red con m fuentes y n destinos. Una fuente o un destino esta representado por un nodo, el arco que une  fuente y un destino representa la ruta por la cual se transporta la mercancía. La cantidad de la oferta en la fuente i es ai, y la demanda en el destino j es bj. El costo de transporte unitario entre la fuente  i  y el destino j es Cij.

Si Xi j representa la cantidad transportada desde la fuente i al destino j, entonces, el modelo general de PL que representa el modelo de transporte es:

               Minimiza  Z= S i=1 m    S j=1 n  C i j X i j
                       
               Sujeta a:

S j=1 n  X i j <= ai ,         i=1,2,…, m
S i=1 m X I j >= bj ,         j=1,2,…, n

X i j >=0         para todas las i y j
  
El primer conjunto de restricciones estipula que la suma de los envíos desde una fuente no puede ser mayor que su oferta; en forma análoga, el segundo conjunto requiere que la suma de los envios a un destino satisfaga su demanda.

El modelo que se acaba de escribir implica que la oferta total Si=1 m ai debe ser cuando menos igual a la demanda total Sj=1 n bj.  Cuando la oferta total es igual a la demanda total, la formulación resultante recibe el nombre de modelo de transporte equilibrado. Este difiere del modelo solo en el hecho de que todas las restricciones son ecuaciones, es decir: 
               SX i j = ai,        i=1,2,..., m
               SX i j = bj,        j=1,2,..., n 
En el mundo real, no necesariamente la oferta debe ser igual a la demanda o mayor que ella. Sin embargo, un modelo de transporte siempre puede equilibrarse. El equilibrio, además de su utilidad en la representación a través de modelos de ciertas situaciones prácticas, es importante para el desarrollo  del método de solución que explote completamente la estructura especial del modelo de transporte. Los dos ejemplos que siguen presentan la idea del equilibrio y también sus implicaciones prácticas.

Ejemplo 1 (Modelo de transporte estándar)

MG Auto Company  tiene plantas en Los Ángeles, Detroit y Nueva Orleáns. Sus centros de distribución principales son Denver y Miami. Las capacidades de las plantas durante el trimestre próximo son 1 000, 1 500, y 1 200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2 300 y 1 400 vehículos. El costo del transporte de un automóvil por tren es de 8 centavos por milla. El diagrama de las distancias recorridas entre las plantas y los centro de distribución son:




Denver
Miami

Los Ángeles

1 000
1 690
Detroit
1 250
1 350

Nueva Orleans

1 275
850



Esto produce en costo por automóvil a razón de 8 centavos por milla recorrida. Produce los costos siguientes (redondeados a enteros), que representan a C i j del modelo original:



Denver
Miami

Los Ángeles

80
215
Detroit
100
108

Nueva Orleans

102
68






 Mediante el uso de códigos numéricos que representan las plantas y centros de distribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta  total ( = 1 000 + 1 500 + 1 200 = 3 700) es igual a la demanda ( = 2 300 + 1 400 = 3 700), el modelo de transporte resultante esta equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones  de igualdad. 

      Minimizar Z = 80X 11 + 215X 12  + 100X 21 + 108X 22 + 102X 31 + 68X 32

Sujeto a:


X 11
X 12




= 1 000


X 21
X 22


= 1 500




X 31
X 32
= 1 200
X 11

X 21

X 31

= 2 300

X 12

X 22

X 32
= 1 400



X i j                                               para todas las i y j


Un método mas resumido para representar el modelo de transporte consiste en utilizar lo que se llama tabla de transporte. Esta es una forma de matriz donde sus renglones representan las fuentes y sus columnas los destinos. Los elementos de costo C i j se resumen en la esquina noroeste de la celda de la matriz (i, j). Por lo tanto, el modelo de MG se puede resumir en la tabla siguiente:












Ejemplo 2 (Modelo de transporte con equilibrio)

En el ejemplo anterior suponga que la capacidad de la planta de Detroit es de 1 300 automóviles (en vez de 1 500). Se dice que la situación esta desequilibrada debido a que la oferta total (=3 500) no es igual a la demanda total (=3 700).Nuestro objetivo consiste en volver a formular el modelo de transporte de manera que distribuya la cantidad faltante(=3 700 – 3 500 = 200) en forma optima entre los centros de distribución.

Como la demanda es mayor que la oferta se puede agregar una planta ficticia con una capacidad de 200. Se permite que dicha planta, en condiciones normales, envíe su “producción“ a todos los centros de distribución. Físicamente, la cantidad de unidades enviadas a un destino desde una planta ficticia representará la cantidad faltante en ese destino.

La única información que falta para completar el modelo son los “costos de transporte” unitarios de  la planta ficticia a los destinos. Como la planta no existe, no habrá ningún envío físico y el costo de transporte unitario es cero. Sin embargo, podemos enfocar la situación desde otro ángulo diciendo que se incurre en un costo de penalización por cada unidad de demanda insatisfecha en los centros de distribución. En este caso los costos de transporte unitarios serán iguales a los costos de penalización unitarios en los diversos destinos.



Denver
Miami

Los Ángeles
80
215
1 000
Detroit
100
108
1 300
Nueva Orleáns
102
68
1 200
Planta ficticia
0
0
200


De manera análoga, si la oferta en mayor que la demanda podemos añadir un destino ficticio que absolverá la diferencia. Por ejemplo, suponga que la demanda en Denver disminuye a 1 900cualquier automóvil enviado de una planta a un centro de distribución ficticio representa un excedente en la planta.
  


Denver
Miami
Destino
Ficticio

Los Ángeles
80
215
0
1 000
Detroit
100
108
0
1 500
Nueva Orleans
102
68
0
1 200


La aplicación del modelo de transporte no se limita al problema de “transporte”.

 El siguiente ejemplo ilustra el uso del modelo del transporte en otros campos.  

Ejemplo 3 (Modelo de inventario de producción)

Una compañía construye una planta maestra para la producción de un articulo en un periodo de cuatro meses. Las demandas en los cuatro meses son: 100, 200, 180 y 300 unidades. Una demanda para el mes en curso puede satisfacerse a través de:

1.      Producción excesiva en un mes anterior almacenada para su consumo posterior.
2.      Producción en el mes actual.
3.      Producción excesiva en un mes posterior para cubrir pedidos de meses anteriores.

El costo de producción variable por unidad en un mes cualquiera es de $4.00. una unidad producida para consumo posterior incurrirá en un costo de almacenamiento razón de $0.50 por unidad por mes. Por otra parte, los artículos ordenados en meses anteriores incurren en un costo de penalización de $2.00 por unidad por mes. La capacidad de producción para elaborar el producto varía cada mes. Los cálculos de los cuatro meses siguientes son 50, 180, 280 y 270 unidades, respectivamente. 

El objetivo es el de formular el plan de inventario de producción a costo mínimo. Este problema se puede formular como un modelo de “transporte”. La equivalencia entre los elementos de los sistemas de producción y transporte se establece de la manera siguiente:


Sistema de Transporte

Sistema de Producción
1. Fuente i
1. Periodo de producción i
2. Destino j
2. Periodo de demanda j
3. Oferta en la fuente i
3. Capacidad de producción del periodo i
4. Demanda en el destino j
4. Demanda del periodo j
5. Costo de transporte de la fuente i al destino j
5. Costo de producto e inventario del periodo i al j



En tabla de abajo se presenta un resumen del problema como un modelo de transporte:



Periodo

1
2
3
4
Capacidad
Demanda
1
4
4.5
5
5.5
50
2
6
4
4.5
5
180
3
8
6
4
4.5
280
4
10
8
6
4
270

Demanda:
100
200
180
300




El costo de “transporte” unitario del periodo i al  j es:
                   Costo de producción en i,                                                   i=j

C i j =            Costo de producción en i / costo de almacenamiento en i a j    i<j


                   Costo de producción en i / costo de penalización en i a j          i>j





 La definición de C i j indica que la producción en el periodo   i   para el mismo periodo (i = j) sólo iguala el costo unitario de producción. Si el periodo i se produce para periodos futuros j (i < j), se incurre en un costo de almacenamiento adicional. De la misma manera, la producción en i para cubrir j pedidos  hechos con anterioridad (i > j) incurre en un costo de penalización adicional. 

PROBLEMAS DE ASIGNACIÓN (Método Hungaro)

         Un problema de asignación es un problema de transporte balanceado, en el cual todas las ofertas y todas las demandas son iguales a uno. Se puede resolver eficientemente un problema de asignación m x m mediante el método Húngaro:

o                              Paso 1.- Empiece por encontrar el elemento mas pequeño en cada renglón de la matriz de costos. Construya una nueva matriz, al restar de cada costo, el costo mínimo de su renglón. Encuentre, para esta nueva matriz el costo mínimo en cada columna. Construya una nueva matriz ( la matriz de costos reducidos ) al restar de cada costo el costo mínimo de su columna.

o                              Paso 2.- Dibuje el mínimo numero de líneas (horizontales o verticales ) que se necesitan para cubrir todos los ceros en la matriz de costos reducidos. Si se requieren m líneas para cubrir todos los ceros, siga con el paso 3.

o                              Paso 3.- Encuentre el menor elemento no cero (llame su valor k en la matriz de costos reducidos, que no esta cubiertos por las líneas dibujadas en el paso 2. Ahora reste k de cada elemento no cubierto de la matriz de costos reducidos y sume k a cada elemento de la matriz de costos reducidos  cubierto por dos líneas.  Regrese al paso 2.

Un problema de asignación es un problema de transporte balanceado en el que todas las ofertas y demandas son iguales a 1; así se caracteriza por el conocimiento del costo de asignación de cada punto de oferta a cada punto de demanda.  La matriz de costos del problema de asignación se llama: matriz de costos.

Como todas las ofertas y demandas para el problema de asignación son números enteros, todas las variables en la solución óptima deben ser valores enteros.
  
EJEMPLOS DE PROBLEMAS DE ASIGNACION

1.                 Una empresa ha contratado a 4 individuos para 4 trabajos, los 4 individuos y 4 trabajos pueden mostrarse en una tabla que indique las clasificaciones obtenidas, analizando al individuo para cada trabajo.  Los renglones se refieren a los hombres, mientras que las columnas se refieren a los trabajos; el problema consiste en maximizar las calificaciones para asignar los 4 trabajos. 
Se supone que las calificaciones de un individuo es directamente proporcional a la ganancia que obtendría la compañía si ese individuo se encargara del trabajo.

2.                 Otro problema que utiliza la misma estructura del modelo de transporte, es la asignación de camiones para reducir al mínimo los costos de un problema de asignación.

3.                 Una empresa cubre el territorio nacional con dos camiones especialmente equipados para funcionar en condiciones climatológicas específicas.  La empresa ha dividido en cinco regiones geográficas.  Se compra el camión A y se modifica para que funcione eficientemente en las regiones uno y dos, y para que funcione bastante bien en las regiones tres y cuatro.  El mismo camión no funciona bien en la región cinco.  Los gastos de gasolina, mantenimiento y otros costos directos de operación, serían mínimos en las regiones uno y dos, promedio en las regiones tres y cuatro, y altos en la región cinco.  Se tiene esa misma información con respecto a los demás camiones de la compañía, o sea, los tipos B, C y D.

SOLUCION DEL PROBLEMA DE TRANSPORTE.

En esta sección presentamos los detalles para resolver el modelo de transporte.  

TECNICA DE TRANSPORTE.

Los pasos básicos de la técnica de transporte son:

Paso 1: determínese una solución factible.

Paso 2: determínese la variable que entra, que se elige entre las variables no básicas. Si todas estas variables satisfacen la condición de optimidad (del método simplex), deténgase; de lo contrario, diríjase al paso 3.

Paso 3: determínese la variable que sale (mediante el uso de la condición de factibilidad) de entre las variables de la solución básica actual; después obténgase la nueva solución básica. Regrese al paso 2. 

OBTENCIÓN DE SOLUCIONES BÁSICAS FACTIBLES PARA PROBLEMAS DE TRANSPORTES 
         Podemos obtener una solución básica factible (sbf) para un problema de transporte balanceado mediante el método de la esquina Noroeste, el método de costo mínimo, o el método de Vogel.
Para obtener una sbf mediante el método de la esquina noroeste, empiece en la esquina superior izquierda del cuadro del transporte y haga a  X11 lo más grande posible.

 Naturalmente, X11 no puede ser mayor que el menor valor Si y así  X11    S1 tache el primer renglón del cuadro de transporte; Esto indica que si habrá más variables básicas del renglón 1 del cuadro.  También d1-S1 . Si X11=d1, tache la primera la columna del cuadro de transporte y cambie S1 – d1.

Si X11= S1 = d1, tache o el renglón 1, o la columna 1 (pero no ambos), del cuadro de transporte. Si tacha el renglón 1, cambie d1 por cero; si tacha columna 1, cambie S 1  por 0.

Continúe aplicando este procedimiento a la celda mas noroeste del cuadro que no cae en un renglón eliminado o en una columna eliminada.

Finalmente, llegara un momento en el cual solo queda una celda a la cual se puede asignar un valor.
 Asigne a esta celda un valor igual a la oferta de su renglón o a la demanda de su columna, y tache el renglón y la columna de la celda. Se obtiene de esta manera una solución básica factible.

OBTENER LA SOLUCIÓN ÓPTIMA PARA UN PROBLEMA DE TRANSPORTE

q                Paso 1:  Si el problema no está balanceado, balancéelo.

q                Paso 2: Utilice uno de los métodos descritos anteriormente para obtener una solución básica factible.

q                Paso 3:  Utilice el hecho de que U1=0, y Ui+Vj=Cij en todas las  variables básicas para encontrar (U1,U2...Um V1,V2...Vn) para la sbf actual.

q                Paso 4: Si Ui + Vj – Cij  es menor o igual  a cero, para todas las variables no básicas, entonces la sbf actual es óptima. Si no es así se introduce la variable con valor más positivo de Ui + Vj –Cij en la base. Para hacer esto, encuentre un circuito cerrado (se puede demostrar  que solamente existe un circuito cerrado) que contiene la variable que entra y algunas de las variables básicas. Después, tomando en cuenta solamente las celdas en el circuito cerrado marque las que se encuentren alejadas en número par (0,2,4,6,...) de celdas de la variable que entra  como celdas pares. También marque las celdas en el circuito cerrado, que se encuentra un número impar de celdas de la variable que entra como celdas impares. Ahora encuentre la celda impar cuya variable toma el menor valor. Llame este valor teta. La variable correspondiente a esta celda impar saldrá de la base. Para realizar el pivoteo, disminuye el valor de cada celda impar en teta y aumenta el valor de cada celda par en teta. Los valores de las variables que no se encuentran en el circuito cerrado permanecen sin cambio. Ahora se completó el bloqueo. 
 Sí teta es igual a cero, la variable que entra será igual a cero, y una variable impar que tiene un valor actual de cero, saldrá de la base. En este caso, existía un sbf degenerada antes del pivoteo y resultará después del pivoteo.  

Si más de una celda impar en el circuito cerrado es igual a teta. Puede escoger arbitrariamente una de estas celdas impares para que salga de la base; se obtendrá una vez más una sbf degenerada. El pivoteo produce una nueva sbf.

q                Paso 5: Regrese a los pasos 3 y 4, utilizando la nueva sbf. Para un problema de maximización, proceda como se especificó, pero cambie el paso 4 por el paso 4’.

q                Paso 6: Si Ui + Vj –Cij es mayor o igual a cero, para todas las   variables no básicas, entonces, la sbf actual es óptima. De otra manera, coloque la variable con el valor más negativo de Ui + Vj – Cij  en la base mediante el procedimiento de pivoteo.

 METODO DE ESQUINA NOROESTE

     Determinación general del modelo de transporte requiere que:

                        m                                 n         
           å     ai    =        å bj  
                 i=1                              j = 1

     Este requisito da origen a una ecuación dependiente, lo que significa que el modelo de transporte tiene sólo m + n –1 ecuaciones independientes. Por lo tanto, como en el método simplex, una solución factible básica inicial debe incluir m + n – 1 variables básicas.

    Normalmente, si el  modelo de transporte se formula como una tabla simplex, sería necesario utilizar variables artificiales para asegurar una solución básica inicial. Sin embargo, cuando se utiliza la tabla de transporte, una solución factible básica inicial se puede obtener fácil y directamente. Presentamos un procedimiento llamado regla de la esquina noroeste para este fin.





Destino



1
2
3
4

Oferta

Fuente
1

10

0

20

11
15

X11
X12
X13
X14
2

12

7

9

20
25

X21
X22
X23
X24
3

0

14

16

18
5

X31
X32
X33
X34

Demanda

5
15
15
10



     El método de la esquina noroeste comienza con la asignación de la máxima cantidad admisible através de la oferta y la demanda de la variable x11 (la de la esquina noroeste de la tabla). Después se tacha la columna (renglón) satisfecha, lo que indica que las variables restantes de la columna (renglón) tachada son iguales a cero. Si se satisfacen una columna y un renglón al mismo tiempo, sólo una (una u otro) puede ser tachado. (Esta condición garantiza la ubicación automática de variables básicas cero, si las hay). Después de ajustar las cantidades de oferta y demanda de todos los renglones y columnas no tachados, la cantidad factible máxima se asigna al primer elemento no tachado de la nueva columna (renglón). El proceso se completa cuando se deja sin tachar exactamente un renglón o una columna.
  
     El procedimiento que se acaba de describir se aplica ahora en el ejemplo:

1.      x11 = 5, se tacha la columna 1. Por lo tanto, no se puede hacer otra asignación en la columna 1. La cantidad que falta en el renglón 1 son 10 unidades.
2.      x12 = 10, se tacha el renglón 1 y faltan 5 unidades en la columna 2.
3.      x22 = 5, se tacha la columna 2 y faltan 20 unidades en el renglón 2.
4.      x23 = 15, se tacha la columna 3 y faltan 5 unidades en el renglon 2.
5.      x24 = 5, se tacha el renglón 2 y faltan 5 unidades en la columna 4.
6.      x34 = 5, se tacha el renglón 3 o la columna 4. Como sólo un renglón ouna columna se mantiene sin tachar, el proceso llega a su fin.
   La solución básica inicial resultante se presenta a continuación.
Las variables básicas son x11 = 5, x22 =10, x23 =15, x24 =5 y x34 = 5. Las variables restantes son no básicas en el nivel cero. El costo de transporte asociado es:
5 x 10 +10 x 0 + 5 x 7+ 15 x 9 + 5 x 20 +5 x 18 = $410.


1
2
3
4

1
5
10


15
2

5
15
5
25
3



5
5

5
15
15
10



    Cuando se satisfacen al mismo tiempo una columna y un renglón, la siguiente variable que se agregará a la solución básica estará necesariamente en el nivel cero. La siguiente tabla ilustra este aspecto.  La columna 2 y el renglón 2 se satisfacen simultáneamente.



1
2
3
4


1
5
5


10
5
2

5
0

5
0
3


8
7
15


5
10
8
7
15



5






     Si se tacha la columna 2, x23 se vuelve básica en el nivel cero en el paso siguiente, ya que la demanda restante del renglón 2 vale ahora cero.(Este caso se presenta en la tabla anterior). Si en cambio se cruza el renglón 2, x32 sería la variable básica cero.

     Las soluciones iniciales de las dos últimas tablas incluyen el número adecuado de variables básicas, o sea, m + n-1 = 6. La regla de la esquina noroeste produce siempre el número adecuado de variables básicas. 

DETERMINACION DE LA VARIABLE DE ENTRADA
(METODO DE MULTIPLICADORES)

La variable que entra se determina mediante el uso de la condición de optimalidad del método simplex. Los cálculos de los coeficientes de la función objetivo están basados en las relaciones primales-duales. Primero presentamos la mecánica del método y después damos una explicación con base en la teoría de la dualidad. Otro método, llamado procedimiento Saltando Piedras, también sirve para determinar la variable que entra.

En el método de multiplicadores asociamos los multiplicadores ui y vj con el renglon i y la columna j de la tabla de transporte. Para cada variable basica xij ed la solucion actual, los multiplicadores ui y vj deben satisfacer la ecuacion que sigue:

ui + vj = cij , para cada variable basica xij

Estas ecuaciones producen m+n-1 ecuaciones con m+n incognitas. Los valores de los multilicadores se pueden determinar a partir de estas ecuaciones suponiendo un valor arbitrario para cualquiera de los multiplicadores  y resolviendo las m+n-1 multipilicadores desconocidos restantes.

Al hacer esto, la evaluacion de cada variable no basica Xpq  esta dada por:

Cpq = up – vq - cpq

Después se selecciona la variable que entra como la variable no basica con la variable no basica con la variable cpq mas positiva.

Si aplicamos este procedimiento a las variables no basicas estan dadas como:


X11:
U1
+
V1
=
C11
=
10

X12:

U1
+
V2
=
C12
=
0
X22:
U2
+
V2
=
C22
=
7
X23:
U2
+
V3
=
C23
=
9
X24:
U2
+
V4
=
C24
=
20
X34:
U3
+
V4
=
C34
=
18



Haciendo u1= 0 los valores de los multiplicadores se determinan sucesivamente como V1=10, V2=0, U2=7, V3=2, V4=13, y U3=5. Las evaluaciones de las variables no basicas estan dadas de la manera siguiente:

                             X13: c13 = u1 + v3 – c13 = 0+2-20 = -18

                             X14: c14 = u1+ v4 – c14 = 0+13-11 = 2
                             X21: c21 = u2 + v1 – c21 = 7+10-12 = 5

                             X31: c31 = u3+v1 – c3 = 5+10-0 = 15

                             X32: c32 = u3+v2 – c32 = 5+0-14 = -9

                             X33: c33 = u3 +v3 – c33 = 5+2-16 = -9


Como x31 tiene la variable cpq mas positiva, esta se selecciona como la variable que entra.

Las ecuaciones ui+vj = cij que utilizamos para determinar los multiplicadores, tienen una estructura tan sencilla que es necesario escribirlos en forma explicita.

DETERMINACION DE LA VARIABLE QUE SALE
(Construccion de un ciclo)

Este paso es equivalente  a aplicar la condicion de factibilidad del metodo simplex.Sin embargo, como todos los coeficientes de restriccion del modelo de transportes original son cero o uno, las razones de condicion de factibilidad tendran siempre su denominador igual a uno .Por lo tanto los valores de las variables basicas producuran dirfectamente las razones asociadas.

Para el fin de determinar la razon minima, construimos un ciclo cerrado para la variable actual que entra. El ciclo empieza y termina en la variable no basica designada. Este consta de los segmentos sucesivos horizontales y verticales cuyos puntos extremos deben de ser variables basicas salvo para los puntos extremos que estan asociados con la variable que entra. Esto significa que todo elemento de esquina del ciclo debe ser una celda que contenga una variable basica. La tabla 6-10 ilustra un ciclo para la variable que entra dada en la solucion basica de la tabla 6-8.Observese que para la solucion basica dada solo se puede construir un ciclo unico para cada variable no basica.

La variable que sale se selecciona de entre las variables de esquina del ciclo que disminuiran cuando las variables del ciclo que entra aumente arriba del nivel cero. Estas situaciones se indican en la tabla siguiente a travez de las variables contenidas en el cuadro etiquetado con los signos menos.


1
2
3
4


10

0

20

11
15
5    -
10    +   



12

7

9

20
25

5    -
15
5    +

0

14

16

18
5
X 31    0


5    -
5
15
15
10












La solucion basica de la tabla de abajo es degenerada, ya que las variables basicas x11 y x22 son cero.Ahora se revisa la optimidad de la nueva solucion basica de la tabla 6-11 calculando los nuevos multiplicadores como se indica en la tabla 6-12. Los valores de cpq estan dados por los numeros de la esquina de cada celda no basicaLa variable no basica x21 con la variable cpq positiva mayor entra en la solucion. El ciclo cerrado asociado con x21 muestra que x21 o x22 pueden ser la variable que sale. Seleccionamos arbitrariamente x11 como la que sale de la solucion.




1
2
3
4

1

10

0

20

11
15

0
15


2

12

7

9

20
25


0
15
10
3

0

14

16

18
5

5




5
15
15
10






V1=10
V2=0
V3=2
V4=13

U1=0


10

0

20

11
15

0    -
15    +
-18

+2

U2=7

12

7

9

20
25

+5
X 21    +
0    -
15
10

U3=-10


0

14

16

18
5

5   
-24

-24

-15


5
15
15
10




La tabla de arriba muestra la nueva solucion basica que sigue de la tabla siguiente. Los nuevos valores de ui, vj y cpq se vuelven a calcular. La tabla  muestra la variable que entra y la que sale como x14 y x24, respectivamente.
Al efectuar este cambio en la tabla de abajo obtenemos la nueba solucion de la tabla final. Como todas las variables cpq de la tabla final son no positivas se ha llegado a la solucion optima.



V1=5
V2=0
V3=2
V4=13

U1=0


10

0

20

11
15

-5

15    -
-18

+2
X 14   +
U2=7

12

7

9

20
25

0
0    +
15
10    -

U3=-5


0

14

16

18
5

5
-19

-19

-10


5
15
15
10






V1=5
V2=0
V3=2
V4=11

U1=0


10

0

20

11
15

-5

5   
-18

10
U2=7

12

7

9

20
25

0
10   
15
-2

U3=-5


0

14

16

18
5

5
-19

-19

-12


5
15
15
10



  
EXPLICACION DEL METODO DE MULPIPLICADORES CON UN METODO SIMPLEX

La relecion que existe entre el metodo multiplicadores y el metodo simplex se puede establecer demostrando que cpq  según se define, es igual directamente a los coeficientes de la funcion objetivo de la tabla simplex asociada con la iteracion actual.

Para mostrar como se obtiene el problema dual para el metodo de transporte, considerese primero el caso especial de ,=2 y n=3 que se indica en la tabla 6-15. Sean las variables duales u1 y u2 para las restricciones de las fuentes y v1,v2, y v3 para las restricciones de los destinos. El problema dual se convierte en:

Maximizar w = (a1u1+a2u2) + (b1v1+b2v2+b3v3)

Sujeto a:

 U1       +v1    <= c11

 U1       +v2     <=c12
 U1       +v3       <=c13
 U2+v1            <=c21
 U2+v1            <=c22

 U2       +v3    <=c23

Ui, U2, v1, v2, v3, irrestrictas
  
El problema dual correspondiente esta dado por:

Maximizar w = åm i-1  a1 u1   +  ån  bi vj       

sujeto a:

ui + vj <=cij para todas las i y j
ui y vj irrestrictas

La evaluacion de las variables no basicas se determinan mediante la sustitucion de los valores actuales de las variables duales en las restricciones duales y despues tomando la diferencia entre sus miembros primero y segundo. Los valores de las variables duales se pueden determinar observando que las restricciones deuales correspondientes a una variable basica se deben satisfacer  como ecuaciones escritas.
En realidad en la iteracion optima los multiplicadores producen los valores duales optimos directamente.

En lo antes expuesto se asigna un valor arbitrario a una de las variables duales que indica que los multiplicadores simplex asociados con una solucion basica dada no son unicos. Esto puede parecer inconsistente con los resultados donde los multiplicadores deben ser unicos.


SOLUCION INICIAL MEJORADA

En esta seccion presentamos dos procedimientos que determinan la solucion inicial a travez de la seleccion de las rutas “economicas”del modelo.

A.                   MODELO DEL COSTO MINIMO

Asignese el mas grande valor posible a la variable con el menor costo unitario de toda la tabla. Tachese el renglon o columna satisfecho.Despues de ajustar la oferta y la demanda de todos los renglones y columnas no tachados, repitase el proceso asignando el valor mas grande posible a la variable con el costo unitario no tachado mas pequeño. El procedimiento esta completo cuando queda exactamente un rebglon o bien una columna sin tachar.



1
2
3
4

1

10

0

20

11
15

0
15

0
2

12

7

9

20
25



15
10
3

0

14

16

18
5

5




5
15
15
10



  
B.                   METODO DE APROXIMACION DE VOGEL (VAM)

Este metodo es heuristico y suele producir una mejor solucion inicial que los dos metodos antes descritos. De hecho, VAM suele producir una solucion inicial optima, o proxima al nivel optimo.
Los pasos del procedimiento son los siguientes:

Paso1: Evaluese una penalizacion para cada renglon restando el menor elemento del costo del renglon del elemento de costo menor siguiente en el mismo renglon.

Paso2: Identifiqueze el renglon o columna con la mayor  penalizacion, rompiendo empates en forma arbitraria. Asignese el valor mayor posible a la variable con el costo mas bajo del renglon o columna seleccionado. Ajustese la oferta y la demanda y tachese el renglon o columna satisfecho. Si un renglon o columna se satisfacen al mismo tiempo, solo uno de ellos se tacha y al renglon restante se le asigna una oferta cero.Cualquier renglon o columna con oferta o demanda cero no debe utilizarce para calcular penalizaciones futuras.

Paso 3:
a.-si solo hay un renglon o columna sin tachar, detengase.
b.-si solo hay un renglon conoferta positiva sin tachar, determinense las variables basicas del renglon a travez del metodo del costo minimo.
c.-si todos los renglones y columnas sin tachar tienen oferta o demanda cero asignadas, determinese las variables basicas cero a travez del metodo del costo minimo. Detengase.
d.-de lo contrario, calculense las penalizaciones de las renglones y columnas no tachados y despues dirijase al paso 2. 
  


1
2
3
4
PR
1

10

0

20

11
15
10





2

12

7

9

20
25
2





3

0

14

16

18
5
14

5



PC
5
15
15
10

10
7
7
7



PR = Penalización de Renglón
PC = Penalización de Columna



1
2
3
4
PR
1

10

0

20

11
15

11









2

12

7

9

20
25
10
2





15


3

0






5
0
-

5






PC
5
15
15
10


-
7
11
9