sábado, 24 de julio de 2010

PRESENTACION


INVESTIGACION DE OPERACIONES



MARTHA OYUELA MORALES




PRESENTADO A:
ALEXANDER LEAÑO






CORPORACION NACIONAL UNIFICADA CUN

INGENIERIA DE SISTEMAS

2010




viernes, 23 de julio de 2010

ORIGEN DE INVESTIGACION DE OPERACIONES


En los siglos XVII y XVIII, grandes matemáticos, como Newton, Leibnitz, Bernoulli y, sobre todo, Lagrange, que tanto habían contribuido al desarrollo del cálculo infinitesimal, se ocuparon de obtener máximos y mínimos condicionados de determinadas funciones.

Posteriormente, el matemático francés Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los métodos de lo que actualmente llamamos programación lineal y la potencialidad que de ellos se deriva.

Si exceptuamos al matemático Gaspar Monge (1746-1818), quien en 1 776 se interesó por problemas de este género, debemos remontarnos al año 1 939 para encontrar nuevos estudios relacionados con los métodos de la actual programación lineal. En ese año, el matemático ruso Leonid Vitalevich Kantorovitch publica una extensa monografía titulada Métodos matemáticos de organización y planificación de la producción en la que por primera vez se hace corresponder a una extensa gama de problemas una teoría matemática precisa y bien definida, llamada hoy en día programación lineal.

En 1941-1942 se formula por primera vez el problema de transporte, estudiado independientemente por Koopmans y por Kantorovitch, razón por la cual se suele conocer con el nombre de problema de Koopmans-Kantorovftch.

Tres años más tarde, G. Stigler plantea otro problema particular conocido con el nombre de régimen alimenticio optimal.

En los años posteriores a la Segunda Guerra Mundial, en Estados Unidos se asumió que la eficaz coordinación de todas las energías y recursos de la nación era un problema de tal complejidad, que su resolución y simplificación pasaba necesariamente por los modelos de optimización que resuelve la programación lineal.

Paralelamente a los hechos descritos se desarrollan las técnicas de computación y los ordenadores, instrumentos que harían posible la resolución y simplificación de los problemas que se estaban gestando.

En 1947, G. B. Dantzig formula, en términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de programación lineal. Dantzig, junto con una serie de investigadores del United States Departament of Air Force, formarían el grupo que dio en denominarse SCOOP (Scientific Computation of Optimum Programs).

método simplex su estudio comenzó en 1951 y fue desarrollado por Dantzig en el United States Bureau of Standards SEAC COMPUTER, ayudándose de varios modelos de ordenador de la firma International Business Machines (IBM).

Los fundamentos matemáticos de la programación lineal se deben al matemático norteamericano de origen húngaro John (Janos) Von Neumann (1903-1957), quien en 1928 publicó su famoso trabajo Teoría de juegos. En 1947 conjetura la equivalencia de los problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos. La influencia de este respetado matemático, discípulo de Dávid Hilbert en Gotinga y, desde 1 930, catedrático de la Universidad de Princeton de Estados Unidos, hace que otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta disciplina.

Cuando comenzó la Segunda Guerra Mundial, había un pequeño grupo de investigadores militares, encabezados por A.P. Rowe, interesados en el uso militar de una técnica conocida como radio ubicación (o radio-localización), que desarrollaron científicos civiles.

No mucho después de que estallara la Segunda Guerra Mundial, la Badswey Research Station, bajo la dirección de Rowe, participó en el diseño de utilización óptima de un nuevo sistema de detección y advertencia prematura, denominado radar (Radio Detection And Ranging – Detección y medición de distancias mediante radio). Poco después este avance sirvió para el análisis de todas las fases de las operaciones nocturnas, y el estudio se constituyó en un modelo de los estudios de investigación de operaciones.

Que es La Programación Lineal (PL)


Es una de las principales ramas de la Investigación Operativa. En esta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión.

Los modelos de Programación Lineal por su sencillez son frecuentemente usados para abordar una gran variedad de problemas de naturaleza real en ingeniería y ciencias sociales, lo que ha permitido a empresas y organizaciones importantes beneficios y ahorros asociados a su utilización.

INVESTIGACION DE OPERACIONES HERRAMIENTAS PARA LA ADMINISTRACCION, LA ECONOMIA Y LAS INGENIERIA


En este artículo y en los próximos entraremos en detalles más puntuales con relación a los diferentes modelos más utilizados como herramientas dentro de la investigación de operaciones. Los modelos de redes tipo CPM-PERT y el MS-PROJET como métodos gerenciales para la planificación, ejecución y control de proyectos.

Pese a que para poder leer e interpretar adecuadamente una red CPM-PERT sólo se necesita saber leer y escribir, esta técnica para la planificación de proyectos es un instrumento gerencial por excelencia, ya que permite al ejecutivo mantener un control muy preciso durante la ejecución de los mismos.

Este ingenioso y elegante método para la optimización de tiempos y minimización de costos es la mezcla de dos instrumentos creados hace algunos años; el CEMP (Crithical Path Method) y el PERT (Program Evaluation on Review Technique).

El primero fue diseñado en el segundo lustro de los años 50, por los investigadores de Dupont: J.E. Kelly y M.R. Walker y originalmente fue denominado CPPSM (Crithical Path Planing and Scheduling Method), se usó para la programación y control de la factoría química en Kentuky y demostró sus grandes ventajas respecto a los métodos clásicos por su aptitud de integrar modificaciones sin dificultad.

El segundo método fue diseñado en la misma época por Naval Special Project Office, con la colaboración de la Lockhead Aircraft y de la firma Booz-Allen & Hamilton. Lo extraordinario es que habiendo sido diseñados por grupos diferentes que buscaban resultados diferentes (uno la minimización de costos y el otro la optimización de los tiempos), y que el primero fuera de tipo determinístico y el segundo probabilístico, las coincidencias gráficas fueran tan notables en ambos métodos. Puede decirse que a primera vista no existe ninguna diferencia desde el punto de vista gráfico.

Estos dos métodos aportaron los elementos administrativos necesarios para formar el método actual CPM-PERT que definitivamente es de más difícil lectura y más elegante y poderoso que sus antecesores, se usa para el control de los tiempos de ejecución y los costos de operación buscando que el proyecto sea realizado en tiempo óptimo y al menor costo posible.

Los métodos de redes, en general, habían estado siendo manejados como secretos militares por la NASA, que como ahora sabemos había tenido una serie de sonados fracasos en sus lanzamientos de satélites artificiales. Fue en el momento de la desesperación y angustia (1957), cuando los soviéticos colocaron el primer Sputnik en órbita, cuando dieron mayor abertura a otras personas e instituciones para que les ayudaran a poner a punto a su cohete Polaris y a recuperar el tiempo perdido por haber trabajado aislados.

De ese momento en adelante toda la programación de NASA se hizo usando redes y esto les permitió, como lo hace con cualquier proyecto, manejar simultáneamente la enorme cantidad de actividades desarrolladas por subcontratistas ligadas entre sí pero desarrolladas en lugares diferentes por personas que no tenían relación directa.

La administración y las ingenierías fueron las grandes ganadoras ya que en forma casi natural comenzaron a utilizar CPM y PERT como instrumentos.

Al principio el PERT se utilizó para evaluar la programación de un proyecto de investigación y desarrollo, en la actualidad se usa para controlar el avance de otro tipo de proyectos como:

1. Programación de proyectos de construcción de edificios, autopistas, puentes, etcétera.

2. Programación de la mudanza de grandes instituciones como bancos, hospitales, industrias, etcétera.

3. Creación de procedimientos para la cuenta regresiva y la suspensión del lanzamiento de los vuelos espaciales (de todos los vuelos de todos los países que compiten en la era espacial).

4. Instalaciones de sistema de cómputo, de maquinaria y equipo de grandes industrias.

5. Diseño y distribución de productos nuevos.

6. Inicio, proceso y conclusión de fusiones de instituciones en corporaciones y de corporaciones mismas.

7. Construcción de equipo, maquinaria estacionaria y vehículos automotores.

8. Flujos de costos mínimos, etcétera.

Características importantes a tener en cuenta para usar la metodología CPM-PERT

METODO GRAFICO

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en 2variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio depuntos factibles. Es decir, si luego de gráficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

Consideremos un Ejemplo Introductorio en 2 variables:

· D) MIN 8X + 6Y

· S.A. 2X + Y >= 10

· ...... .2X + 2Y >= 16

· ..... ..X>= 0, Y>= 0

Comentario: Nótese que corresponde al Problema Dual de P) cuya resolución se presenta en nuestro sitio como ejemplo introductorio en la utilización de Solver de MS Excel. Para ver el detalle de la resolución gráfica de P) se recomienda al usuario Para resolver el problema D) graficamos el dominio de puntos factibles y las curvas de nivel asociadas a la función objetivo:





El área achurada en color verde representa el dominio de puntos factibles del problema D), es decir, son las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no acotado, lo que no implica que el problema no tenga solución.

Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del dominio de puntosfactibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y (X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con V(P)=52, el cual resulta ser la Solución Óptima de D). Sin embargo, una forma más eficiente para obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6) (dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento, cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 2 RESTRICCIONES

Una vez resuelto un modelo de Programación Lineal resulta útil hacer un análisis de sensibilidad que permita identificar cómo afecta en los resultados del problema variaciaciones en los parametros de éste, sin que esto pase por resolver el problema nuevamente. Nuestro sitio considera una sección aparte llamada "Sensibilidad" cuyos resultados principales se pueden consultar AQUI.

1. Variación en los Coeficientes de la Función Objetivo: La pregunta que buscamos responder es cuál es el intervalo de variación para los coeficientes de la función objetivo (cada coeficiente se analiza por separado) que mantiene la actual Solución Óptima.

Un primer acercamiento es considerar las pendientes de las restricciones activas en el óptimo, es decir, aquellas restricciones que se cumplen en igualdad (en nuestro caso restricción 1 y 2). La restricción 1 (2X + Y >=10) tiene pendiente -2. La restricción 2 (2X + 2Y >=16) tiene pendiente -1. Por otra parte la pendiente de la función objetivo dado C1=8 y C2=6 es -4/3.

En consecuencia, se mantiene la actual Solución Óptima si la pendiente de la función objetivo (curvas de nivel) varían en el intervalo de las pendientes de las actuales restricciones activas. Esto es:

-2 <= -C1/C2 <= -1 (Multiplicamos por -1)

2 >= C1/C2 >= 1

Si fijamos C2=6.

2 >= C1/6 >= 1

12 >= C1 >= 6 (Garantiza la actual Solución Óptima con C2 fijo)

Si fijamos C1=8.

2 >= 8/C2 >= 1

8 >= C2 >= 4 (Garantiza la actual Solución Óptima con C1 fijo)

Nótese que en los extremos de los intervalos además de incluir la actual Solución Óptima se consideran nuevas combinaciones deldominio que mantienen el Valor Óptimo y también son Solución Óptima de D). Esta situación determina que el problema tieneinfinitas soluciones óptimas.

METODO SIMPLEX


En geometría, un simplex o n-simplex es el análogo en n dimensiones de un triángulo. Es la envoltura convexa de un conjunto de (n + 1) puntos independientes afines en un espacio euclídeo de dimensión n o mayor, es decir, el conjunto de puntos tal que ningún m-plano contiene más que (m + 1) de ellos. Se dice de estos puntos que están en posición general. Un 0-símplex es un punto; un 1-símplex un segmento de una línea; un 2-símplex un triángulo; un 3-símplex es un tetraedro; y un 4-símplex es un pentácoron (en cada caso, con su interior).
El método simplex es un método que sirve para resolver problemas de programación lineal. Este método fue inventado por George Dantzig en el 1947. La primera formulación del método simplex fue en el verano de 1947. El primer problema práctico que se resolvió con este método fue uno de nutrición.
Método Simplex
Es una técnica popular para dar soluciones numéricas del problema de la programación lineal. Es un método numérico para optimización de problemas libres multidimensionales perteneciente a la clase más general de algoritmos de búsqueda. Según Rodríguez (2009) este Método “…comienza con alguna solución factible, y sucesivamente obtiene soluciones en las intersecciones que ofrecen mejores funciones de la función objetivo. Finalmente, este método proporciona un indicador que determina el punto en el cual se logra la solución óptima...” (p. 1)
Permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono. Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
Se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
El método simplex es muy eficiente en la práctica, en general, teniendo 2m a 3m iteraciones en la mayor parte (donde m es el número de restricciones de igualdad), y que convergen en la hora prevista para el polinomio de ciertas distribuciones de insumos al azar.
La aplicación del método del Simplex, se utiliza cuando el problema es de un tamaño suficientemente grande.
Está diseñado para problemas de programación lineal cuya matriz tiene la propiedad de diseminación (el número de no-cero es pequeño).
Hay implementaciones del método simple para la solución de problemas de programación lineal con las matrices de restricción escasa.
Se han desarrollado diversas variantes del método simplex que tienen en cuenta las particularidades de las diversas clases especiales de problemas de programación lineal (problemas de bloque, los problemas de transporte y otros).
Formulación.
La representación matemática de un modelo de programación lineal (llamada Forma General de representación) es:
Max (ó Min) Z = C1 X1 + C2 X2 + . . . + Cj Xj
sa:a11 x1 + a12 x2 + . . . + a1j xj <= (>= ó =) b1
a21 x1 + a22 x2 + . . . + a2j xj <= (>= ó =) b2
. . . . . . . .
. . . . . . . .
. . . . . . . .
ai1 x1 + ai2 x2 + . . . + aij xj <= (>= ó =) bi
3.X1 , X2 , … , Xj >= 0 j = 1, 2, 3, ... n
Fuente: http://mathworld.wolfram.com/SimplexMethod.html (2010)
Como podemos ver, el Modelo consta de las TRES partes fundamentales que son:
Función Objetivo (FO).
Matriz de Restricciones Funcionales ó Tecnológicas.
Restricción de Factibilidad o de No-Negatividad.
Para en el que:
Z =valor de la medida global de efectividad (objetivo por lograr).
Xj =nivel de la actividad j (para j = 1,2,...,n).
Cj =incremento (o decremento) en Z que resulta al aumentar (o disminuir) una unidad enel nivel de la actividad j.
bi =cantidad de recurso i disponible para asignar a las actividades (para i = 1,2,...,m).
aij =cantidad del recurso i consumido por cada unidad de la actividad j
En la representación de ambos Modelos, Canónico y Estándar, hay que hacer notar que los coeficientes de la función objetivo cambiarán de signo pues dicha función se iguala con cero antes de proceder a su solución por medio del método Simplex, es decir, de su representación clásica en Forma General:
Max (ó Min) Z = C1 X1 + C2 X2 + . . . + Cj Xj
Pasaríamos a su representación en Canónico o Estándar de la siguiente manera:
Max (ó Min) Z – C1 X1 – C2 X2 – . . . – Cj Xj = 0
Condiciones
El objetivo es de la forma de maximización o de minimización.
Todas las restricciones son de igualdad.
Todas las variables son no negativas.
Las constantes a la derecha de las restricciones son no negativas.
Proceso
El sistema es típicamente no determinado (el número de variables excede el número de ecuaciones)
La diferencia entre el número de variables y el número de ecuaciones nos da los grados de libertad asociados con el problema. Cualquier solución, óptima o no, incluirá un número de variables de valor arbitrario. El algoritmo simplex usa cero como valor arbitrario, y el número de variables con valor cero es igual a los grados de libertad.
Valores diferentes de cero son llamados variables básicas, y valores de cero son llamadas variables no básicas en el algoritmo simplex.
Esta forma simplifica encontrar la solución factible básica inicial, dado que todas las variables de la forma estándar pueden ser elegidas para ser no básicas (cero), mientras que todas las nuevas variables introducidas en la forma aumentada, son básicas (diferentes de cero), dado que su valor puede ser calculado trivialmente (para ellas, dado que la matriz problema aumentada en diagonal es su lado derecho)
En cada una de las desigualdades que se plantean en el modelo matemático de programación lineal, se plantean desigualdades de <, >, ≤, ≥, ó =

Funciones y dominios

Una función real f de una variable es una regla que asigna a cada número real x en un conjunto especificado de números reales llamado el dominio de f, un número real único f(x).

La variable x se llama la variable independiente. Si y = f(x) llamamos a y la variable dependiente.

Una función puede ser especificado:

  • numéricamente: por medio de una tabla
  • algebraicamente: por medio de una formula
  • gráficamente: por medio de una gráfica.

Nota acerca de los dominios
El dominio de una función no es siempre explícitamente especificado; cuando no se especifica algún dominio para una función f, supondremos que el dominio está el conjunto más grande de los números x para los cuales tiene sentido f(x). Esta "dominio más grande posible" se le llama a veces el dominio natural.

Pulse aquí para ir a una página que se deja evaluar y dibujar a las curvas de funciones.
Pulse aqui para descargar una graficador Excel.

Inicio de página

http://www.zweigmedia.com/MundoReal/blank.gif
Ejemplos

Función especificado numéricamente Sea f la función especificada por la siguiente tabla:


x

0

1

2

3

f(x)

3.01

-1.03

2.22

0.01

Entonces, f(0) = 3.01, f(1) = -1.03, y así sucesivamente.

Función especificado algebraicamente: Sea f la función especificada por f(x) = 3x2 - 4x + 1. Entonces

f(2) = 3(2)2 - 4(2) + 1 = 12 - 8 + 1 = 5,

f(-1) = 3(-1)2 - 4(-1) + 1 = 3 + 4 + 1 = 8.

Como f(x) se defina para toda x, el dominio de f es el conjunto de todos números reales.

Función especificado gráficamente: Sea f la función especificada por la siguiente gráfica.

Modelos demanda y oferta

Una función (de) demanda expresa la demanda q (el número de artículos solicitados) como una función del precio unidad p (el precio por artículo). Una función de oferta expresa la oferta q (el número de articulos un proveedor está dispuesto a llevar al mercado) como una función del precio unidad p (el precio por artículo). Es normalmente el caso que la demanda disminuye y la oferta sube a medida que el precio sube.

La demanda son en equilibrio cuando son iguales. Los valores correspondientes de p y q se llaman precio de equilibrio y demanda de equilibrio. Para hallar el precio de equilibrio, determine el precio unitario p donde cruzan las curvas de demanda y oferta (a veces podemos determinar este valor analíticamente por igualar las funciones de demanda y oferta y despejar a p). Para hallar la demanda de equilibrio, evalúe la demanda (o oferta) con el precio equilibrio.


Inicio de página

Example

Si la demanda para las Botas Wellington de Ludington es pares vendidos por semana y la oferta es pares por semana (vea la gráfica más abajo), entonces se obtiene el precio de equilibrio cuando la demanda = la oferta:



que se da p = 5995/54.5 = $110. Sigue que el precio equilibrio es $110 y la demanda de equilibrio es q = −4.5(110) + 4000 = 3505 pares por semana. Lo que ocurre a precios distintos del precio de equilibrio se puede ver en la figura siguiente:







  • Cuando el precio es debajo del precio de equilibrio, es mayor la demanda que la oferta, y se resulta una escasez.
  • Cuando el precio es igual al precio de equilibrio, no hay escasez ni excedente, y decimos que el mercadoes liquido o está despejado.
  • Cuando el precio es arriba del precio de equilibrio, es mayor la oferta que la demanda, y se resulta una excedente.