Programación Entera y Modelo de Transporte #2

Los siguientes apuntes fueron tomados el viernes 13 de enero de 2017.

Pasos para resolver un problema con ramificación y acotamiento:

1. Resolver relajación lineal y obtener solución optima.
2. Elegir entre las variables de decisión la que mas impacto brinda a la función objetivo y sus restricciones, tiene que ser fraccionaria.
3. Incorporar dos restricciones con la variable de decisión, una mayor que el valor entero derecho y otra menor que el valor entero izquierdo de la variable.
4. Obtener solución optima del problema lineal y repetir los pasos 1 y 2 hasta que el problema sea in factible o no haya variables enteras en el estado de la rama.
5. Resolver los ejercicios en forma de LIFO (Last in first out), es decir, resolver el primero de la izquierda y luego sus hijos, luego el segundo y así.

Modelo de transporte

Se utiliza para resolver problemas en los que exista el factor de transporte en el modelo lineal y involucra también suministros y demandas de elementos, ejemplos transporte de agua potable de una planta a una ciudad, transporte de energía eléctrica entre otros.

La siguiente tabla representa tres plantas que pueden suministrar electricidad a cuatro ciudades, estas ciudades poseen una demanda y las plantas pueden suministrar una cierta cantidad de KWH.

	Ciudad 1	Ciudad 2	Ciudad 3	Ciudad 4	Suministros
Planta 1	8	6	10	9	35
Planta 2	9	12	13	7	50
Planta 3	14	9	16	5	40
Demanda	45	20	30	30

Las variables de decisión en un problema de transporte involucra una matriz.

Xij = Cantidad de KWH que suministra la planta i a la ciudad j

Restricciones: la suma de todas las inversiones de la planta i a todas las ciudades no deben ser mayor al suministro.

Lo siguientes son las restricciones por parte de los suministros a las plantas (la suma de todas las inversiones a las ciudades j no deben ser mayor a lo que puede suministrar la planta i)

x11 + x12 + x13 + x14 <= 35

x21 + x22 + x23 + x24 <= 50  

x31 + x32 + x33 + x34 <= 40

Y los siguientes son las restricciones por parte de la demanda de las ciudades (la sumatoria de los suministros de las plantas i debe ser igual o mayor a la demanda de la ciudad j)

x11 + x21 + x31 >= 45

x12 + x22 + x32 >= 20

x13 + x23 + x33 >= 30

x14 + x24 + x34 >= 30

Por ultimo las restricciones de signos:

xij >= 0 i = 1, 2, 3 y j = 1, 2, 3, 4

La formulación para la función objetivo seria la siguiente:

min z ∑i=m i=1 ∑ j=n j=1 cij xij

Pasos para ejecutar correctamente el método simplex de transporte

1.  Si el problema esta desequilibrado, se debe equilibrar.
2. Hallar la solución básica inicial (sfb), se puede hacer con alguno de los siguientes métodos:
1. Esquina Noroeste
2. Costo Mínimo 
3. Vogel
3. Calcular Cij para la sfb actual.
4. Si Cij <= 0 para las variables no básicas, entonces la sfb actual es optima. 
5. Con la nueva sfb, se vuelve a los pasos 3 y 4
6. 4' Si cij > = 0 para las variables no básicas, la sfb actual es optima.

En cuanto a el primer paso, se dice que un problema esta equilibrado cuando el valor la sumatoria de la demanda es igual a la sumatoria del suministro.

Los datos que están en el recuadro pequeño, son las capacidades que pueden suministrar la planta i a la ciudad j, los valores que aparecerán en el recuadro externo serán las inversiones que actualmente se realizaran.

Como nota, todos los elementos en blanco serán cero, sin embargo se le pueden incorporar. 

Equilibrar un problema desequilibrado:

Ahora, existen dos casos en el que el problema no este equilibrado:

Cuando el suministro es mayor que la demanda: cuando la cantidad que se puede proveer es mayor a la que necesita, podemos agregar un punto de equilibrio ficticio. Este punto se representara como una nueva ciudad que demande el suministro sobrante.

Cuando el suministro es menor que la demanda: este caso es mas complicado, debido a que en este caso no hay exceso, sino que existe una demanda que no se puede satisfacer, por lo que es infactible (no posee una solución factible). 

La solución para ese caso es el manejo de escasez, que se realiza solo cuando expresamente se indique un valor de penalizacion al no satisfacer la demanda (el enunciado debe indicarlo), de lo contrario se indica que el problema es infactible y no se puede resolver mas.

Se puede observar como si se agregara una planta 4 al problema, que satisfaga las necesidades que faltan.

Los tres métodos:

Método esquina noroeste: básicamente es el mismo recuadro de transporte pero sin los costos. Consiste en representar en el recuadro externo el valor que puede satisfacer el suministro i a la demanda j, luego los valores de la demanda y el suministro son restados.

• Una vez satisfecho una demanda o utilizado un suministro, se coloca "X".
• Si en la esquina noroeste que no es la ultima, tanto el suministro como la demanda es igual, se coloca en el suministro X y en la demanda 0, luego se coloca en la siguiente celda el menor entre el cero y el valor que le sigue.
• Como observación o razonamiento, tanto el suministro como la demanda en la ultima celda deben de ser iguales, de lo contrario hubo un error durante el proceso.

Costo mínimo: toma importancia en los costos y se enfoca en el de menor valor.

• Se toma el menor de todos los costos.
• Se toma el menor entre el suministro y la demanda, se coloca debajo del recuadro con el menor costo y se restan ambos.
• Se tacha la fila o columna satisfecha.

Vogel: 

• Tomar un valor penalizacion por cada fila y columna, lo cual se hace restando los dos valores mas pequeños de la fila (o columna cual sea el caso).
• De entre todas las penalizaciones, tomar la penalizacion con mayor valor.
• Tomar el costo con el valor mas pequeño de la columna/fila de la penalizacion
• Tomar el valor mas pequeño del suministro y la demanda de la celda de costo, y aplicar el mismo procedimiento que costo minimo.
• Se vuelve a calcular las penalizaciones, calculando solo aquellas que no se encuentren en el renglon o no se hayan calculado.

Siguiente clase: 

• Continuación del 3, 4 y 5 paso.