Problema de transporte con QM

Ejercicio 1.- Transporte de Vogel

Método de transporte de Vogel

El método de Vogel, o aproximación de Vogel, es un método que permite llegar a una solución inicial factible del problema de transporte.

El procedimiento de este método es el siguiente:

1. Tener los valores de costos de envíos desde cada origen a cada destino tabulados (matriz de costos). En caso de que la matriz no este equilibrada (el numero de filas es diferentes del numero de columnas), agregar una fila o columna de ceros según corresponda. Esto quiere decir que según sea el caso se creara un origen o un destino ficticio.
2. Realizar el cálculo de las penalizaciones para cada fila y columna. Las penalizaciones se calculan restando los dos valores más pequeños de cada fila y cada columna. Las penalizaciones tienen valor absoluto.
3. Identificar la fila o columna con la mayor penalización (en caso de que exista un empate en las penalizaciones, se puede elegir cualquiera de las que tiene el mayor valor), y asignar la mayor cantidad de material posible a la casilla con el menor costo en esa fila o columna.
4. Se sombrean (eliminan) las filas o columnas que hayan sido satisfechas, reduciendo así la matriz.
5. Se repite el procedimiento desde en paso 2.
6. Una vez satisfechos todos los orígenes y destinos (sombreadas todas las filas y columnas) se puede proceder a calcular el costo del programa de envió encontrado mediante este método (cabe resaltar que la solución factible encontrada con este método no es necesariamente la optima).

EL PROBLEMA

Una empresa energética colombiana dispone de cuatro plantas de generación para satisfacer la demanda diaria eléctrica en cuatro ciudades, Cali, Bogotá, Medellín y Barranquilla. Las plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente. Las necesidades de las ciudades de Cali, Bogotá, Medellín y Barranquilla son de 70, 40, 70 y 35 millones de Kw al día respectivamente.

Los costos asociados al envío de suministro energético por cada millón de KW entre cada planta y cada ciudad son los registrados en la siguiente tabla.

formule un modelo de programación lineal que permita satisfacer las necesidades de todas las ciudades al tiempo que minimice los costos asociados al transporte.

SOLUCIÓN PASO A PASO

El primer paso es determinar las medidas de penalización y consignarlas en el tabulado de costos, tal como se muestra a continuación.

El paso siguiente es escoger la mayor penalización, de esta manera:

El paso siguiente es escoger de esta columna el menor valor, y en una tabla paralela se le asigna la mayor cantidad posible de unidades, podemos observar como el menor costo es "2" y que a esa celda se le pueden asignar como máximo 60 unidades "que es la capacidad de la planta 3".

Dado que la fila de la "Planta 3" ya ha asignado toda su capacidad (60 unidades) esta debe desaparecer.

Se ha llegado al final del ciclo, por ende se repite el proceso

Iniciamos una nueva iteración

www.ingenieriaindustrialonline.com

Continuamos con las iteraciones,

www.ingenieriaindustrialonline.com

Iniciamos otra iteración

Al finalizar esta iteración podemos observar como el tabulado queda una fila sin tachar y con valores positivos, por ende asignamos las variables básicas y hemos concluido el método.

Los costos asociados a la distribución son:

www.ingenieriaindustrialonline.com

De esta manera hemos llegado a la solución a la cual también llegamos mediante programación lineal, definitivamente desarrollar la capacidad para modelar mediante programación lineal y apoyarse de una buena herramienta como WinQSB, STORM, LINGO, TORA etc. termina siendo mucho más eficiente que la utilización de los métodos heurísticos para problemas determinísticos

Problemas de transporte

Un problema de transporte surge cuando se necesita un modelo costo-efectividad que permita transportar ciertos bienes desde un lugar de origen a un destino que necesita aquellos bienes, con ciertas restricciones en la cantidad que se puede transportar

El PT es un caso particular de la PL

• Se debe determinar un esquema óptimo de transporte que se origina en los lugares de oferta donde la existencia de cierta mercancía es conocida, y llega a los lugares de donde se conoce la cantidad requerida. El costo de cada envió es proporcional a la cantidad transportada y, el costo total es la suma de los costos individuales.
• 

EL PROBLEMA DE TRANSPORTE

• Corresponde a un problema de flujo de mínimo costo
• Supongamos que deseamos enviar productos desde las bodegas a los lugares de venta

Ejemplo:

• 3 bodegas
• 4 puntos de venta
• a_i: oferta en bodega i
• b_j: demanda de vendedor j
• c_ij: costo de envio de i a j
• Sea x_ij la cantidad enviada de i a j
• Formule el LP
• 
• 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
  Paso 1: Si el problema no está balanceado, balancéelo.
  Paso 2: Utilice uno de los métodos descritos anteriormente para obtener una solución básica factible.
  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.
  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.
  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’.
  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.

• 
  

Ejercicios método simplex

Ejercicio 1.
Un negocio se dedica a la fabricación de sillas y mesas para fabricar cada una de ellas se consume una determinada cantidad de recursos en los departamentos de corte y ensamble. Los recursos están eh horas hombres y son 120 horas, para corte y 90 horas para el ensamble. Cada unidad fabricada ofrece la siguiente ganancia: 50 pesos para las mesas y 80 pesos para una silla.

Ejercicio 2.
Una empresa vitivinicultora ha adquirido recientemente un terreno de 110 hectáreas. Se puede vender toda la producción de uvas blanck y chardonai. Se desea conocer cuanto plantar de cada variedad en las 110 hectáreas, dados los costos, beneficios netos y requerimientos de mano de obra según los datos.

Ejercicio 3.
Un taller tiene 3 tipos de maquina A, B Y C; puede fabricar dos productos 1 y 2 , todos los productos tienen que ir a cada maquina y cada uno va en el mismo orden, primero a la A luego a la B y C. Que permita la máxima ganancia del taller.

Método Simplex

Método Simplex

El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción en el número de variables.

El Método Simplex es un método iterativo que permite ir mejorando la solución en cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro a un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo, sea maximizar o minimizar), dado que el número de vértices que presenta un poliedro solución es finito siempre se hallará solución.

Este popular método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de solucionar problemas de m restricciones y n variables.

Ejemplo:

Un paso preliminar consiste en incorporar las denominadas variables de holgura. De modo de comprender este concepto consideremos la primera restricción:

Para cada solución factible , el valor del lado izquierdo será a lo más el valor del lado derecho; o eventualmente existirá una diferencia (holgura) entre estos 2 valores.

De esta forma definimos  como variable de holgura de dicha restricción, la cual se puede denotar por , donde . De forma análoga se pueden definir las variables de holgura (no negativas)  y  para las restricciones 2 y 3, respectivamente. Finalmente podemos describir la función objetivo  utilizando  de forma compacta.

Mapa mental de Investigación de Operaciones