Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Untitled Prezi

No description
by

carlos narvaez

on 14 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

UNIDAD III, Programación Dual
MODELO DE TRASPORTE
El problema del transporte o distribución es un problema de redes especial en programación lineal que se funda en la necesidad de llevar unidades de un punto específico llamado Fuente u Origen hacia otro punto específico llamado Destino. Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado por las rutas escogidas.
MODELO DE ASIGNACION
Los problemas de asignación se ocupan de asignar trabajadores a tareas sobre una base de uno a uno. Se considera el número de trabajadores igual al número de tareas (condición que puede garantizarse creando trabajadores o tareas ficticias) y se conoce el tiempo Cij que necesita el trabajador i para terminar la tarea j. El objetivo es asignar a cada trabajador una tarea de manera que todas las tareas se terminen en un tiempo total mínimo.
El problema de asignación puede transformarse en un problema de transporte al considerar a los trabajadores como orígenes y a las tareas como destinos con todos los suministros y demandas igual a uno. Método húngaro

CONSTRUCCIÓN DE LOS MODELOS DE HOLGURA COMPLEMENTARIA
CARACTERISTICAS DE UN MODELO DE TRASPORTE
1. Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
2. Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas.
3. Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos.
4. Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución óptima), asumen también valores enteros.
Autores - Agenda
PROGRAMACIÓN DUAL
CONSTRUCCIÓN DE LOS MODELOS DE HOLGURA COMPLEMENTARIA
MODELO DE TRASPORTE
CARACTERISTICAS DE UN MODELO DE TRASPORTE
MODELO DE ASIGNACION
MODELO DE TRASBORDO
SOLUCIÓN BÁSICA INICIAL FACTIBLE – S.B.I.F.
METODO REGLAS DE LA ESQUINA
METODO MINIMO COSTO
APROXIMACIONES DE VOGUEL
EJEMPLO DEL MÉTODO DE APROXIMACIÓN DE VOGEL
EL PROBLEMA
SOLUCIÓN PASO A PASO
BUSQUEDA DE LA SOLUCIÓN ÓPTIMA
AFIRMACIONES SOBRE UNA SOLUCIÓN ÓPTIMA
Celis Luisa
Franco, Jeancarlos
Landaez, Zolangely
Mauricio, Patricia
Mayan, Mayerlis
Morales, Rodny
Narváez, Carlos
Pérez Erika
PROGRAMACIÓN DUAL
MODELO DE TRASBORDO
SOLUCIÓN BÁSICA INICIAL FACTIBLE – S.B.I.F.
METODO REGLAS DE LA ESQUINA
METODO MINIMO COSTO
APROXIMACIONES DE VOGUEL
BUSQUEDA DE LA SOLUCIÓN ÓPTIMA
AFIRMACIONES SOBRE UNA SOLUCIÓN ÓPTIMA
Cada problema de programación lineal se le asocia otro problema de programación lineal, llamado el problema de programación dual. La solución óptima del problema de programación dual, proporciona la siguiente información respecto del problema de programación original:

1. La solución óptima del problema dual proporciona los precios en el mercado o los beneficios de los recursos escasos asignados en el problema original.

2. La solución óptima del problema dual aporta la solución óptima del problema original y viceversa.
Una variable en el primal está asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) está en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).
El Problema de Transbordo, Intertransporte o Reembarque es una variación del modelo original de transporte que se ajusta a la posibilidad común de transportar unidades mediante nodos fuentes, destinos y transitorios, mientras el modelo tradicional solo permite envíos directos desde nodos fuentes hacia nodos destinos. Existe la posibilidad de resolver un modelo de transbordo mediante las técnicas tradicionales de resolución de modelos de transporte y este procedimiento se basa en la preparación del tabulado inicial haciendo uso de artificios conocidos con el nombre de amortiguadores, los cuales deben ser iguales a la sumatoria de las ofertas de los nodos de oferta pura y de coeficiente cero (0) en materia de costos.
1. Se obtiene una Solución Básica Inicial por medio de la Forma Estándar del modelo, es decir, convertir las desigualdades en igualdades introduciendo variables de holgura (<=) ó variables de exceso (>=).

UNA SOLUCIÓN BÁSICA ES UNA SOLUCIÓN BÁSICA FACTIBLE SÍ Y SÓLO SÍ LAS VARIABLES BÁSICAS TIENEN VALORES NO NEGATIVOS, ES DECIR, MAYORES O IGUALES A CERO (>=).

2. DEBE EXISTIR EN CADA ECUACIÓN UNA VARIABLE CON COEFICIENTE +1 Y QUE NO ESTÉ EN NINGUNA OTRA RESTRICCIÓN; LAS OTRAS VARIABLES CON COEFICIENTE CERO (0) PARA FORMAR EL CANÓNICO O BASE DEL SISTEMA DE ECUACIONES. SE OBTIENE UNA SOLUCIÓN BÁSICA FACTIBLE INICIAL inicializando n-m variables adecuadas (no básicas) al nivel de cero.
Donde: n = Número de incógnitas
m = Número de restricciones o ecuaciones
m < n
La función Objetivo no se tiene en cuenta para determinar el sistema de ecuaciones, aunque hace parte del Canónico.
El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte o distribución mediante la consecución de una solución básica inicial que satisfaga todas las restricciones existentes sin que esto implique que se alcance el costo óptimo total.
Este método tiene como ventaja frente a sus similares la rapidez de su ejecución, y es utilizado con mayor frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.
Algoritmo de resolución esquina Noroeste
Su nombre se debe al génesis del algoritmo, el cual inicia en la ruta, celda o esquina Noroeste. Es común encontrar gran variedad de métodos que se basen en la misma metodología de la esquina Noroeste, dada que podemos encontrar de igual manera el método e la esquina Noreste, Sureste o Suroeste.
El método del costo mínimo o de los mínimos costos es un algoritmo desarrollado con el objetivo de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos. El diagrama de flujo de este algoritmo es mucho más sencillo que los anteriores dado que se trata simplemente de la asignación de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda menos costosa de toda la matriz hasta finalizar el método.
El método de aproximación de Vogel es un método heurístico de resolución de problemas de transporte capaz de alcanzar una solución básica no artificial de inicio, este modelo requiere de la realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos existentes con este fin, sin embargo producen mejores resultados iniciales que los mismos.
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
La solución óptima del problema se encuentra en uno de los vértices de esta área de soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del problema.
Ejemplo:
Una compañía de auditores se especializa en preparar liquidaciones y auditorías de empresas pequeñas. Tienen interés en saber cuántas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales disponibles es de 60.
OBJETIVO: Maximizar el ingreso total.
1. Si una restricción del primal es sobre satisfecha (Variable Holgura > 0) entonces la correspondiente variable dual es cero.
2. Si una variable real del dual es positiva, la restricción correspondiente en el primal es exactamente satisfecha (Variable Holgura primal = 0)
3. Si una de las restricciones del dual es sobre satisfecha (Variable Holgura-exceso del dual > 0) entonces la correspondiente variable en el primal es cero.
4. Si una variable real del primal es positiva, la restricción correspondiente en el dual es exactamente satisfecha (Variable Holgura-exceso del dual = 0)
Full transcript