• Author / Uploaded
• Fabian Bello

Citation preview

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

TRABAJO COLABORATIVO NO. 1

FABIAN ALBERTO BELLO SARMIENTO CODIGO 80545865 EDISONALEXANDER MELO CODIGO 80396405 NELSON BELTRAN CODIGO 80439937 GONZALO ALFONSO MELO CODIGO 80513298

GRUPO 100404-132

ANTONIO MERCHAN TUTOR

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA - UNAD ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA PROGRAMACION LINEAL BOGOTA 2012

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

DERARROLLO DE ACTIVIDADES



ACTIVIDADES GRUPALES En la primera fase se debe realizar las actividades propuestas en la lectura autoregulada “Los modelos Matemáticos en la IO”. Esta lectura la pueden bajar del tópico 1 del curso. Tenga en cuenta que debe hacerla con mucha atención pues en ella encontrará probablemente algunos términos desconocidos pero que a medida que usted prosigue en la lectura irán definiéndose, esta lectura le permitirá clasificar los modelos matemáticos en determinísticos, híbridos y estocásticos y dentro de ellos posicionar a la programación Lineal materia de estudio en este curso, al mismo tiempo que le permitirá valorar la importancia que tienen los modelos matemáticos y la investigación operativa en su vida profesional y cotidiana.

1. Elabore una síntesis de cada modelo clasificándolo de acuerdo al cuadro 2. Ilustre con un ejemplo cada modelo MODELOS DE INVESTIGACION DE OPERACIONES DETERMINISTICOS Los modelos determinísticos son aquéllos donde se supone que todos las variables pertinentes se conocen con certeza. Es decir, en ellos se supone que cuando el modelo sea analizado se tendrá disponible toda la información necesaria para tomar las decisiones correspondientes. Un ejemplo de modelo determinísticos sería la asignación de la tripulación de una aerolínea para cada uno de sus vuelos diarios del mes próximo, conociendo los horarios de vuelos, el personal disponible, las restricciones legales sobre las horas de trabajo, las reglas del sindicato y así sucesivamente. Optimización lineal Es necesario que las restricciones y la función sean de tipo lineal, formulándose a través de ecuaciones e inecuaciones lineales donde se hallan series de soluciones o un conjunto factible. Los casos especiales de la programación lineal son, los modelos de transporte y asignación Programación lineal Se caracteriza por minimizar o maximizar su función objetivo lineal y conocer sus restricciones lineales. Como en cualquier modelo de investigación de operaciones el método para su desarrollo se llama método Simplex y tiene tres componentes básicos: 1. Las variables de decisión que se trata de determinar.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

2. El objetivo (la meta) que se trata de optimizar. 3. Las restricciones que se deben satisfacer La estructura matemática general de la programación lineal es la siguiente:

Transporte y Asignación El modelo de transporte busca determinar un plan de transporte de una mercancía de varias fuentes a varios destinos. Los datos del modelo son: 1. Nivel de oferta en cada fuente y la cantidad de demanda en cada destino. 2. El costo de transporte unitario de la mercancía a cada destino. Como solo hay una mercancía un destino puede recibir su demanda de una o más fuentes. El objetivo del modelo es el de determinar la cantidad que se enviará de cada fuente a cada destino, tal que se minimice el costo del transporte total. La suposición básica del modelo es que el costo del transporte en una ruta es directamente proporcional al número de unidades transportadas. La definición de “unidad de transporte” variará dependiendo de la “mercancía” que se transporte. Ejemplo: MG Auto Company tiene plantas en Los Ángeles, Detroit y Nueva Orleáns. Sus centros de distribución principales son Denver y Miami. Las capacidades de las plantas durante el trimestre próximo son 1 000, 1 500, y 1 200 automóviles. Las demandas trimestrales en los dos centros de distribución son de 2 300 y 1 400 vehículos. El costo del transporte de un automóvil por tren es de 8 centavos por milla. El diagrama de las distancias recorridas entre las plantas y el centro de distribución son: Denver

Miami

Los Ángeles

1 000

1 690

Detroit

1 250

1 350

Nueva Orleans

1 275

850

Esto produce en costo por automóvil a razón de 8 centavos por milla recorrida. Produce los costos siguientes (redondeados a enteros), que representan el modelo original:

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

Denver Los Ángeles 80 Detroit 100 Nueva Orleans 102

Miami 215 108 68

Mediante el uso de códigos numéricos que representan las plantas y centros de distribución, hacemos que X i j represente el número de automóviles transportados de la fuente i al destino j. Como la oferta total (1.000 + 1.500 + 1.200 = 3.700) es igual a la demanda (2.300 + 1.400 = 3.700), el modelo de transporte resultante está equilibrado. Por lo tanto, el siguiente modelo de PL que representa el problema tiene todas las restricciones de igualdad. Minimizar Z = 80X 11 + 215X 12 + 100X 21 + 108X 22 + 102X 31 + 68X 32

Sujeto a:

X 11

X 12 X 21

X 11

X 21 X 12 X ij

X 22 X 31 X 31

X 32

X 22 X 32 para todas las i y j

= 1 000 = 1 500 = 1 200 = 2 300 = 1 400

Programación Entera y 0-1: Los programas lineales enteros son aquellos en los que algunas o todas las variables están restringidas a tener valores enteros (o discretos). La programación lineal entera tiene aplicaciones prácticas importantes. Desafortunadamente hasta esta fecha no existe un programa de cómputo para programas lineales enteros que pueda resolverlos en forma consistente. Algunas de sus variables están compuestas de valores enteros. Su obtención se hace analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de soluciones obtenidas, considerando las variables reales. Muchas veces la solución del programa lineal truncado está lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero. Ejemplo: Un Árabe excéntrico dejó un testamento para distribuir un hato de camellos entre sus tres hijos: Tarek recibe al menos la mitad del hato. Sharif recibe al menos un tercio y Maisa recibe al menos un noveno, y el resto va a una institución de beneficencia. El testamento no especifica el tamaño del hato y sólo dice que es una cantidad impar de camellos y que la institución mencionada reciba exactamente un camello. ¿Cuántos camellos dejó el sheikh en su testamento, y cuántos recibió cada hijo?

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

Redes Hay una multitud de situaciones en investigación de operaciones que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas encuestas recientes informan que hasta el 70% de los problemas de programación matemática en el mundo real se pueden re-presentar como modelos relacionados con redes. Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para describir una red es (N.A), donde N es el conjunto de nodos y A es el conjunto de arcos con cada red se asocia algún tipo de flujo; En general el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos. un arco es dirigido u orientado si permite un flujo positivo en una dirección y flujo cero en la dirección opuesta. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Los arcos forman un bucle o circuito cerrado. Un ciclo es dirigido si consiste en una ruta dirigida. Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta. Un árbol es una red conectada que puede consistir sólo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos y un árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos. Los métodos CPM (método de la ruta crítica o del camino crítico, “critical path method”) PERT (técnica de evaluación y revisión de programa, “program evaluation and review technique”) se basan en redes y tienen por objeto auxiliar en la planeación, programación y control de proyectos. Se define un proyecto como conjunto de actividades interrelacionadas, en la que cada actividad consume tiempo y recursos. El objetivo del CPM y del PERT es contar con un método analítico para programar las actividades. Ejemplos: 1. Diseño de una red de gasoductos marinos para conectar bocas de pozos en el Golfo de México con un punto de entrega en tierra. El objetivo del modelo es minimizar el costo de construcción del gasoducto. 2. Determinación de la ruta más corta entre dos ciudades, en una red de carreteras. 3. programa de flujo con costo mínimo desde los campos petroleros hasta las refinerías a través de una red de oleoductos. 4. Determinación del cronograma (fechas de inicio y terminación) de las actividades en la construcción de un proyecto. Optimización no lineal Los métodos de solución de la programación no lineal se pueden clasificar por su método de solución y como contraposición de la programación lineal, sujeta a una serie de restricciones lineales. Asume también valores óptimos (máximos o mínimos). Ejemplo: Sea .La función ingreso total, por venta de el ingreso marginal cuando se venden 20 artículos?

artículos. ¿Cuál será

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

Métodos Clásicos Este método aplica cálculo diferencial en sus operaciones. Método de Búsqueda Los Métodos de Búsqueda utilizan técnicas gradientes y ramificación, y los Métodos de Programación no Lineal aplican algoritmos especiales (procedimientos de solución) para explotar ciertas estructuras matemáticas en las relaciones funcionales. Programación no lineal Aplican algoritmos especiales (procedimientos de solución) para explotar ciertas estructuras matemáticas en las relaciones funcionales. ESTOLASTICOS En los modelos estocásticos algunos elementos no se conocen con certeza. Es decir, en los modelos probabilísticos se presupone que algunas variables importantes, llamadas variables aleatorias, no tendrán valores conocidos antes que se tomen las decisiones correspondientes y que ese desconocimiento debe ser incorporado al modelo. Un ejemplo de modelo probabilístico podría ser la decisión de establecer una compañía de Internet mediante la venta pública de acciones de capital, antes de saber si el mercado para nuestra oferta será favorable (mercado en alza) y rendirá un alto precio de las acciones, o desfavorable (mercado sostenido) y el precio de éstas será bajo. Programación estocástica La Programación estocástica (PE) es la resolución de problemas de programación matemática en los que algunos o todos los parámetros se consideran variables aleatorias pues se conoce la distribución de probabilidad asociada a ellos, suponiendo que son independientes a la solución. La programación estocástica tiene que ver con situaciones en las que algunos o todos los parámetros del problema son variables aleatorias. Esos casos son típicos en los problemas de la vida real, donde puede ser difícil determinar con certidumbre los valores de los parámetros. La idea de la programación estocástica es convertir el problema probabilístico en un caso determinísticos equivalente.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

Colas Se forman debido a un desequilibrio temporal entre la demanda del servicio y la capacidad del sistema para suministrarlo. En las formaciones de colas se habla de clientes, tales como máquinas dañadas a la espera de ser rehabilitadas. Los clientes pueden esperar en cola debido a que los medios existentes sean inadecuados para satisfacer la demanda del servicio; en este caso, la cola tiende a ser explosiva, es decir, a ser cada vez más larga a medida que transcurre el tiempo. Los clientes puede que esperen temporalmente, aunque las instalaciones de servicio sean adecuadas, porque los clientes llegados anteriormente están siendo atendidos. Ejemplo: Aplicación a la telefonía; Las redes telefónicas se diseñan para acomodar la intensidad ofrecida del tráfico con solamente una pequeña pérdida. El funcionamiento de los sistemas depende de si la llamada es rechazada, de si está pérdida, etc. Normalmente los sistemas de desbordamiento hacen uso de rutas alternativas e incluso estos sistemas tienen una capacidad de carga finita o máxima de tráfico. Sin embargo, el uso de las colas permite que los sistemas esperen por las peticiones de su cliente hasta que los recursos libres estén disponibles. Esto significa que si los niveles de la intensidad del tráfico exceden de la capacidad disponible, las llamadas del cliente se perderían. La disciplina de colas determina la manera de cómo manejar las llamadas de los clientes. Define la manera en que les servirán, la orden de las cuales se sirven, y la manera en la que los recursos se dividen entre los clientes. Proceso Estocástico Es un proceso azaroso que se desarrolla a través del tiempo y se muestra por medio de un conjunto de funciones aleatorias, como distribución de probabilidad y el tiempo. Teorías de decisiones y juegos En el análisis de decisiones se usa un proceso racional para seleccionar la mejor de varias alternativas. La “bondad” de una alternativa seleccionada depende de la calidad de los datos que se usen para describir el caso de la decisión. Desde este punto de vista, un proceso de toma de decisión puede caer en una de las tres categorías siguientes: 1. Toma de decisiones bajo certidumbre, en la que los datos se conocen en forma determinista. 2. Toma de decisiones bajo riesgo, en la que los datos se pueden describir con distribuciones de probabilidades. 3. Toma de decisiones bajo incertidumbre, en donde a los datos no se les puede asignar pesos o factores de ponderación que representen su grado de importancia en el proceso de decisión. De hecho bajo certidumbre, los datos están bien definidos y bajo incertidumbre, los datos son ambiguos. La toma de decisiones bajo riesgo representa entonces el caso de “la mitad del camino”.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

Ejemplo: Kevin y June Park (K y J) están comprando casa nueva. Hay disponibles tres casas, A,B y C .Los Park concuerdan en dos criterios para seleccionar la casa: acabado (Y ) y cercanía al trabajo(W) y han formulado matrices de comparación. Clasifique las tres casas por prioridad, y calcule la relación de inconsistencia para cada matriz.

HIBRIDOS Programación dinámica La programación dinámica encuentra la solución óptima de un problema con n variable descomponiéndolo en n etapas, siendo cada etapa un subproblema de una sola variable. Sin embargo, como la naturaleza de la etapa difiere de acuerdo con el problema de optimización, la programación dinámica no proporciona los detalles de cómputo para optimizar cada etapa. Tres elementos básicos de un modelo de programación dinámica: 1. Definición de las etapas. 2. Definición de las alternativas en cada etapa. 3. Definición de los estados para cada etapa. En la programación dinámica tenemos unas variables que interactúan unas con otras, de acuerdo a ciertas razones de cambio entre ellas, porcentajes y constantes de interacción. Este tipo de problemas se resuelven con herramientas cómo las ecuaciones diferenciales o los diagramas de fase. Uno de los ejemplos más encontrados es el del modelo LotkaVolterra. Ejemplo: Un explorador debe cargar tres artículos: alimentos, botiquín y ropa. La mochila tiene 3 pies cúbicos de capacidad. Cada unidad de alimento ocupa 1 pie cúbico. Un botiquín ocupa de pie cúbico y cada prenda de vestir ocupa pie cúbico. El excursionista asigna los factores de prioridad 3, 4 y5 al alimento, botiquín y ropa, lo que significa que la ropa es el más valioso de esos artículos. De acuerdo con la experiencia, el excursionista debe llevar al menos 1 unidad de cada artículo, y nomás de dos botiquines. ¿Cuánto de cada artículo debe cargar el excursionista? Inventarios Uno de los métodos de optimización de inventarios es el método de costeo ABC. El análisis ABC es una manera de clasificar los productos de acuerdo a criterios preestablecidos en los textos de estudio toman como criterio el valor de los inventarios y dan porcentajes relativamente arbitrarios para hacer esta clasificación. Los modelos que se presentan se clasifican, en el sentido amplio, en situaciones de revisión continua y periódica (incluyen tanto casos de un solo periodo como de varios periodos). Las soluciones pro-puestas van desde el uso de una versión probabilística de la cantidad económica de pedido (CEPo EOQ, de economic order quantity) determinística hasta casos

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

más complejos que se resuelven con programación dinámica. La naturaleza probabilística de la demanda conduce a modelos complejos que quizá no sean útiles en la práctica. Sin embargo, en las publicaciones se han reportado buenas implementaciones de inventario probabilístico. Ejemplo: El 10% de los productos representan el 60% de las compras de la empresa por lo tanto esta es la zona A, un 40% de los productos el 30%, que serian los que están ubicados en la zona B, el resto (50% de los productos y 10% de las compras) son productos C. Los valores anteriores son arbitrarios, cada empresa tiene sus particularidades, si alguien decide utilizar este criterio debe ser consciente de las realidades de su empresa. Se debe pensar no solo en los costos, es importante ver otros criterios, lo que es sin duda la principal dificultad en este tipo de análisis. Es innegable, sin embargo que un pequeño porcentaje de productos, desde cualquier criterio, es indispensable para el funcionamiento de la empresa y/o para mejorar su rentabilidad, estos serian clasificados como productos A típicos, y de acuerdo a este punto de vista se van seleccionando los productos de las demás zonas; si uno considera oportuno podría pensarse en la posibilidad de agregar una zona D, para productos realmente intrascendentes y de costo muy bajo. Simulación La simulación es la mejor alternativa de la observación de un sistema. Nos permite recopilar información pertinente acerca del comportamiento al paso del tiempo. La simulación no es una técnica de optimización. Más bien se usa para estimar las mediciones del desempeño de un sistema modelado. Ésta es la razón por la que la simulación ha gozado de aplicaciones tan tremendas en las redes de comunicaciones, manufactura, control de inventario, comportamiento del cliente, pronósticos económicos, sistemas biomédicos, estrategias y tácticas bélicas Ejemplo: El tiempo de entrega de un pedido puede ser 1 o 2 días, con probabilidades iguales. La demanda por día puede tomar los valores 0, 1 y 2 y tienen las probabilidades respectivas de 0.2, 0.7 y 0.1. A partir de la distribución conjunta estime la función de distribución de probabilidades de la demanda durante el tiempo de entrega Pert Ruta critica Es la serie de elementos terminales de la red de proyectos con la mayor duración entre ellos, determinando el tiempo más corto en el que es posible complementar el proyecto. Ejemplo: Grafica de grantt, Red de actividades, Heurísticos Aplican reglas del pulgar a los problemas que sin esto no podrían ser resueltos de manera factible, eficaz y óptima, sirve para descubrir o resolver problemas mediante la

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

experimentación y los métodos de ensayo y error. También son representaciones gráficas de un sistema para explicar mejor y poder entender de una manera simple. Ejemplo de ellos son; gráficos, esquemas, mapas, etc.; Todos son imágenes que explican algo.

3. IMPORTANCIA QUE TIENE LA INVESTIGACIÓN DE OPERACIONES EN MI CARRERA PROFESIONAL. Los modelos anteriormente descritos de forma breve me permiten observar cómo puedo modelar las diferentes situaciones que se me presentan en la empresa. Estos modelos me ayudarán a reducir costos mediante la restricción de mi presupuesto, o me permitirán desarrollar un modelo que me dé una idea de cómo se verá afectada la empresa dónde trabajo por los cambios en la economía mundial mediante la formulación de un problema de carácter dinámico Dentro del ámbito de la ingeniería de sistemas, se presenta un sin número de situaciones que requieren ser objeto de análisis, para optimizar los recursos disponibles, empleando la información existente para definir a través de modelos matemáticos la mejor utilización de los mismos, para el logro de las condiciones, metas u objetivos propuestos, bien sea en manejo de datos, diseño o implementación de recursos, tiempos de respuesta, velocidad de transmisión de la información, entre otras. En una empresa existen productos a fabricar u ofrecer dependiendo del tipo de empresa que sea (manufacturera, de servicios, etc.) con una cantidad de recursos (maquinaria, equipos, personas, dinero, etc.) limitados y en los cuales se hace necesario utilizar al máximo para obtener el mayor beneficio de la empresa. Considerando que como administradores somos los encargados de dichos productos y recursos se hace necesario tener un conocimiento de la programación lineal y encontrar mediante modelación matemática soluciones óptimas.

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA Escuela de ciencias básicas tecnologías e Ingeniería PROGRAMACION LINEAL 2012

BIBLIOGRAFIA

          

Guzman Aragón, Gloria Lucia (2010), Módulo Programación lineal, Universidad Nacional Abierta y a Distancia UNAD, Bogotá-Colombia Guía Didáctica Programación Lineal, UNAD Escuela de Ciencias básicas Tecnología e Ingeniería, Gloria Lucia Guzmán Aragón, Junio de 2010. – Colombia http://pisis.unalmed.edu.co/vieja/cursos/analisis_decisiones/AD_16_Programacion%20 estocastica.pdf http://es.wikipedia.org/wiki/Programaci%C3%B3n_lineal http://148.204.211.134/polilibros/portal/Polilibros/P_terminados/InvOperChave/DOCU MENTOS/Unidad1/referencias.htm http://es.scribd.com/doc/82723612/Investigacion-de-Operaciones-Taha-Handy http://es.scribd.com/doc/82723612/Investigacion-de-Operaciones-Taha-Handy http://books.google.com.co/books?id=HnT_F3MCST4C&pg=PA13&hl=es&source=gbs _selected_pages&cad=3#v=onepage&q&f=false http://148.204.211.134/polilibros/portal/Polilibros/P_terminados/InvOperChave/DOCU MENTOS/Unidad1/referencias.htm http://es.wikipedia.org/wiki/Teor%C3%ADa_de_juegos http://es.wikipedia.org/wiki/Teor%C3%ADa_de_colas