Modelos Y Optimizacion

PROBLEMA 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.

Una solución al PT queda definido por un conjunto de mxn número Xij, donde:

Xij : Número de unidades a enviar desde el origen i al destino j

Siendo Xij ≥ 0

El programa lineal del Problema del transporte queda expresado de la siguiente manera:

Sujeto.

DEFINICIÓN DEL PROBLEMA

1. Se tienen m lugares de origen. Cada lugar de origen tiene una capacidad de producción Si

2. Se tienen n destinos. Cada destino j demanda Dj

3. Objetivo: Minimizar el costo de transporte de la carga al lugar de destino cumpliendo con las restricciones de los lugares de origen.

El modelo de transporte tiene notable interés por sus importantes aplicaciones que, como se vera en varios ejercicios, no se restringe únicamente a la distribución de mercancías.

Su procedimiento especifico de solución, llamado algoritmo de transporte consta de dos fases y es rápido y eficiente. La primera fase consiste en obtener una solución factible inicial. Se pasa después a la segunda fase, en la que se comprueba si la solución obtenida en la primera fase es óptima, y si no lo es, como mejorarla.

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

• ai: oferta en bodega i

• bj: demanda de vendedor j

• cij: costo de envio de i a j

• Sea xij la cantidad enviada de i a j

• Formule el LP

EL PROBLEMA DE TRANSPORTE

• En general, la formulación es

• Min

FARMACÉUTICA CARLTON

La farmacéutica Carlton abastece de drogas y otros suministros médicos.

Esta tiene tres plantas en: Claveland, Detroit, Greensboro.

Tiene cuatro centros de distribución en: Boston, Atlanta, St Louis.

La gerencia de Carlton desea realizar el trnsporte de sus productos de la manera más económica posible.

DATOS

Costo de transporte por unidad, oferta y demanda.

SUPUESTOS

* El costo de transporte por unidad es constante

* Todos los transportes ocurren simultáneamente.

* Solo se considera el costo de transporte entre el lugar de origen y el de destino

* La oferta total es igual a la demanda total.

RED QUE REPRESENTA EL PROBLEMA

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

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

...