Published using Google Docs
Tarea 1. Nube de Palabras
Updated automatically every 5 minutes

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE ESTUDIOS SUPERIORES ACATLÁN

MATEMÁTICAS APLICADAS Y COMPUTACIÓN

OPTIMIZACIÓN ENTERA Y DINÁMICA

Maestra Guadalupe del Carmen Rodríguez Moreno

PROBLEMA DE TRANSPORTE Y ASIGNACIÓN

TAREA 1. Nube de Palabras

                                                                                 Ruelas Flores Fernanda Dicé

Índice

        - Problema de Transbordo ……………………………………………… 6

        - Problema de Asignación ……………..………………………………. 7

Introducción

Problema de transporte

El modelo de transporte es una clase especial de programación lineal que tiene que ver con transportar un artículo desde sus fuentes hasta sus destinos. El objetivo es determinar el programa de transporte que minimice el costo total de transporte y que al mismo tiempo satisfaga los límites de la oferta y la demanda. En el modelo se supone que el costo de transporte es proporcional a la cantidad de unidades transportadas en determinada ruta. En general, se puede ampliar el modelo de transporte a otras áreas de operación, entre otras el control de inventarios, programación de empleos y asignación de personal.

Aunque el modelo de transporte se puede resolver como una programación lineal normal, su estructura especial permite desarrollar un algoritmo de cómputo, basado en el símplex, que usa las relaciones primal-dual para simplificar los cálculos.

El problema de transporte requiere de alguna información para ser planteado y resuelto. La información necesaria es:

Un destino recibe la demanda de una o más fuentes. Una fuente envía la oferta a uno o más destinos. El objetivo es determinar la cantidad de bienes que se deben enviar de cada fuente a cada destino de tal manera que se minimice el costo total de transporte.

 

Existen 3 formas de plantear el problema de transporte:

Red

m fuentes y n destinos

Ofertas ai

Demandas bj

Costo unitario de transporte cij

Se tienen n(m) arcos y m+n nodos.

Modelo de Programación Lineal

Las restricciones son de igualdad ya que el la oferta es igual a la demanda.

En caso de que la oferta sea mayor a la demanda, las restricciones que representan a la oferta deberán de tener menor-igual (≤) y las restricciones de demanda permanecerán con igualdad.

En caso de que la demanda sea mayor a la oferta, las restricciones que representan a la demanda deberán de tener menor-igual (≤) y las restricciones de oferta permanecerán con igualdad.

Tabla de Transporte

Para equilibrar la tabla tenemos dos casos posibles:

  1. Si la oferta total es mayor a la demanda total entonces se agrega una columna con el valor de la demanda que hace falta para igualarla a la oferta.
  2. Si la demanda total es mayor a la oferta total, entonces se agrega un renglón con el valor de la oferta que hace falta para igualarla a la demanda.

Para resolver los problemas de transporte se utiliza el método Simplex para problemas de transporte, comenzando con la solución inicial (método de la esquina noroeste, costos mínimos, método Vogel) y obteniendo la solución óptima (método de multiplicadores, construcción de un ciclo).

Problema de transbordo

El problema de transbordo es un tipo de problema de transporte. A diferencia del  problema de transporte, el de transbordo tiene nodos de paso y en algunos casos se permiten envíos entre nodos de demanda o entre nodos de oferta. Para la solución de este tipo de problemas se sigue un algoritmo para convertirlo en un problema de transporte y así utilizar el mismo método que se utiliza para la resolución de los problemas de transporte.

                     

  Nodo Origen Puro            Nodo Destino Puro         Nodo de transbordo/paso

Red del Problema de Transbordo

Para convertir el problema de transbordo a uno de transporte:

Para resolver los problemas de transbordo se utiliza el método Simplex para problemas de transporte, comenzando con la solución inicial (método de la esquina noroeste, costos mínimos, método Vogel) y obteniendo la solución óptima (método de multiplicadores, construcción de un ciclo).

Problema de Asignación

El problema de asignación es un caso particular del problema de transporte. En este tipo de problemas se tendrán asignados (trabajadores) y tareas. Los asignador no siempre serán personas, pueden ser máquinas, plantas, vehículos, etc.

Un problema de asignación debe cumplir lo siguiente:

  1. El número de asignados es igual al número de tareas.
  2. Cada asignado debe cumplir con una sola tarea.
  3. Cada tarea debe ser realizada por solamente un asignado.
  4. Existe un costo asociado en el asignado i que realiza la tarea j.
  5. El objetivo es determinar cómo deben hacerse las n asignaciones para minimizar el costo total.

Red

m=n

Modelo de Programación Lineal

Matriz de Costos

Para la resolución del problema de asignación es necesario que la matriz de costos sea cuadrada. En caso de que la matriz no lo sea, entonces decimos que el modelo no esta balanceado. Para balancear el modelo se le deben de agregar las columnas o renglones que sean necesarios para lograr balancearlo.

Para la solución del problema de asignación se utiliza el método Húngaro.

Planteamiento

El mantenimiento preventivo periódico se lleva a cabo en los motores de los aviones de un componente importante debe ser reemplazado. El número de aviones programados para ese mantenimiento durante los seis meses próximos se calcula en 280, 180, 300, 198, 230 y 290 respectivamente. Todo el trabajo de mantenimiento se hace durante los dos primeros días del mes y un componente usado puede reemplazarse con un componente nuevo o con un reparado. La reparación de los componentes usados se hace en una instalación local, en donde estarán listos para utilizarse a principios del siguiente mes, o bien se envían a un taller de reparación central, donde se espera una demora de tres meses (incluyendo mes en el cual ocurre el mantenimiento). El costo de la reparación en el taller local es de 120 dólares por componente. En la instalación central, el costo es de sólo 35 dólares por componente. Un componente reparado que se utiliza en un mes posterior, incurrirá en un costo mensual de almacenamiento adicional de 1.50 dólares por unidad. Los componentes nuevos se pueden comprar a 200 dólares cada uno el primer mes, con un incremento de 5% en el precio cada dos meses. Formule el problema como un modelo de transporte y resuélvalo a fin de determinar el programa óptimo para satisfacer la demanda de componentes durante los próximos 6 meses.

Planteando el modelo obtenemos la siguiente tabla, donde se tienen los 6 meses en los que se planea programar el número de aviones a los que se le dará mantenimiento.

Solución

Aplicando el Método de la Esquina Noroeste obtenemos la siguiente solución inicial.

Iteración 1

Comenzamos a aplicar el método simplex para problemas de transporte. Obtenemos los valores de ui y vj.

Obtenemos los valores de las variables no básicas. Como se puede observar, la variable de entrada será x17.

Creamos un ciclo, dándole valor de +θ a la variable de entrada y rotando los signos alrededor del ciclo.

El valor de teta será el mínimo de los valores de las casillas que contengan -θ. En este caso θ = 280, así notamos que la variable de salida será x27. Actualizamos la tabla sumando y restando teta donde corresponde.

Iteración 2

De nuevo, obtenemos los valores de ui y vj.

Obtenemos los valores de las variables no básicas. Observamos que la variable de entrada será x35.

Creamos un ciclo, dándole valor de +θ a la variable de entrada y rotando los signos alrededor del ciclo.

Tomamos teta como el valor mínimo de las casillas que contienen -θ. Entonces tenemos que θ = 180 y la variable de salida será la casilla correspondiente, x37. Actualizamos la tabla sumando y restando teta donde corresponde.

Iteración 3

Una vez más, obtenemos los valores de ui y vj.

Obtenemos los valores de las variables no básicas. En este caso la variable de entrada es x46.

Creamos un ciclo, dándole valor de +θ a la variable de entrada y rotando los signos alrededor del ciclo.

Tomamos teta como el valor mínimo de las casillas que contienen -θ. Entonces tenemos que θ = 10 y la variable de salida será la casilla correspondiente, x16.

De esta manera seguimos el algoritmo del método simplex para problemas de transporte y en la iteración número 10 llegamos a la solución óptima que se muestra a continuación.

Conclusiones

De la tabla óptima concluimos lo siguiente:

Interpretando nuestra solución tenemos que

Referencias